Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

2020-10-07 · Dylan J. Foster, Alexander Rakhlin, David Simchi-Levi, Yunzong Xu

In the classical multi-armed bandit problem, instance-dependent algorithms attain improved performance on "easy" problems with a gap between the best and second-best arm. Are similar guarantees possible for contextual bandits? While positive results are known for certain special cases, there is no general theory characterizing when and how instance-dependent regret bounds for contextual bandits can be achieved for rich, general classes of policies. We introduce a family of complexity measures that are both sufficient and necessary to obtain instance-dependent regret bounds. We then introduce new oracle-efficient algorithms which adapt to the gap whenever possible, while also attaining the minimax rate in the worst case. Finally, we provide structural results that tie together a number of complexity measures previously proposed throughout contextual bandits, reinforcement learning, and active learning and elucidate their role in determining the optimal instance-dependent regret. In a large-scale empirical evaluation, we find that our approach often gives superior results for challenging exploration problems. Turning our focus to reinforcement learning with function approximation, we develop new oracle-efficient algorithms for reinforcement learning with rich observations that obtain optimal gap-dependent sample complexity.

📄 PDF Abstract BibTeX arXiv:2010.03104

Code (0)

등록된 구현이 없습니다.

Tasks

Active Learning Multi-Armed Bandits reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Instance-optimal PAC Algorithms for Contextual Bandits

2022-07-05 · Zhaoqi Li, Lillian Ratliff, Houssam Nassif, Kevin Jamieson 외

In the stochastic contextual bandit setting, regret-minimizing algorithms have been extensively researched, but their instance-minimizing best-arm identification counterparts remain seldom studied. In this work, we focus…

Multi-Armed Bandits

Asymptotic Instance-Optimal Algorithms for Interactive Decision Making

2022-06-06 · Kefan Dong, Tengyu Ma

Past research on interactive decision making problems (bandits, reinforcement learning, etc.) mostly focuses on the minimax regret that measures the algorithm's performance on the hardest instance. However, an ideal algo…

Decision Making Multi-Armed Bandits reinforcement-learning Reinforcement Learning+1

Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon

2020-09-28 · Zihan Zhang, Xiangyang Ji, Simon S. Du

Episodic reinforcement learning and contextual bandits are two widely studied sequential decision-making problems. Episodic reinforcement learning generalizes contextual bandits and is often perceived to be more difficul…

Decision Making Multi-Armed Bandits reinforcement-learning Reinforcement Learning+2

On the Complexity of Representation Learning in Contextual Linear Bandits

2022-12-19 · Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric

In contextual linear bandits, the reward function is assumed to be a linear combination of an unknown reward vector and a given embedding of context-arm pairs. In practice, the embedding is often learned at the same time…

Model Selection Multi-Armed Bandits Representation Learning

Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits

2022-05-19 · Avishek Ghosh, Abishek Sankararaman

We prove an instance independent (poly) logarithmic regret for stochastic contextual bandits with linear payoff. Previously, in \cite{chu2011contextual}, a lower bound of $\mathcal{O}(\sqrt{T})$ is shown for the contextu…

Multi-Armed Bandits parameter estimation