Eluder Dimension and the Sample Complexity of Optimistic Exploration

2013-12-01 · NeurIPS 2013 12 · Daniel Russo, Benjamin Van Roy

This paper considers the sample complexity of the multi-armed bandit with dependencies among the arms. Some of the most successful algorithms for this problem use the principle of optimism in the face of uncertainty to guide exploration. The clearest example of this is the class of upper confidence bound (UCB) algorithms, but recent work has shown that a simple posterior sampling algorithm, sometimes called Thompson sampling, also shares a close theoretical connection with optimistic approaches. In this paper, we develop a regret bound that holds for both classes of algorithms. This bound applies broadly and can be specialized to many model classes. It depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Thompson Sampling

Optimistic Policy Optimization with General Function Approximations

2021-01-01 · Qi Cai, Zhuoran Yang, Csaba Szepesvari, Zhaoran Wang

Although policy optimization with neural networks has a track record of achieving state-of-the-art results in reinforcement learning on various domains, the theoretical understanding of the computational and sample effic…

reinforcement-learning Reinforcement Learning (RL)

GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond

2022-11-03 · Han Zhong, Wei Xiong, Sirui Zheng, LiWei Wang 외

We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making, which includes Markov decision process (MDP), partially observable Markov decision process (POMDP), and pr…

Decision Making Reinforcement Learning (RL)

Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL

2023-05-18 · NeurIPS 2023 11 · Qinghua Liu, Gellért Weisz, András György, Chi Jin 외

While policy optimization algorithms have played an important role in recent empirical success of Reinforcement Learning (RL), the existing theoretical understanding of policy optimization remains rather limited -- they …

Reinforcement Learning (RL)

Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization

2013-07-18 · Zheng Wen, Benjamin Van Roy

We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient ex…

Efficient Exploration reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Randomized Exploration for Reinforcement Learning with General Value Function Approximation

2021-06-15 · Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub 외

We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm as well as the optimism principle. Unlike existing upper-confidence-bound (UCB) …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)