2020

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

Foster, Dylan J., Rakhlin, Alexander, Simchi-Levi, David et al.

Understand

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.

Built on

Provably efficient RL with rich observations via latent state decoding
Original
Simon S Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, and John Langford · 1901
Earlier work this paper cites.
Asymptotically efficient adaptive allocation rules
Tze Leung Lai and Herbert Robbins · 1985
Earlier work this paper cites.
The central limit theorem for weighted empirical processes indexed by sets
Kenneth S Alexander · 1987
Earlier work this paper cites.
On learning sets and functions
Balas K Natarajan · 1989
Earlier work this paper cites.
Optimal adaptive policies for sequential allocation problems
Apostolos N Burnetas and Michael N Katehakis · 1996
Earlier work this paper cites.
Associative reinforcement learning using linear probabilistic concepts
Naoki Abe and Philip M Long · 1999
Earlier work this paper cites.
Beating the hold-out: Bounds for k-fold and progressive cross-validation
Avrim Blum, Adam Kalai, and John Langford · 1999
Earlier work this paper cites.
Smooth discrimination analysis
Enno Mammen and Alexandre B Tsybakov · 1999
Earlier work this paper cites.
Agnostic Q-learning with function approximation in deterministic systems: Tight bounds on approximation error and sample complexity
Original
Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang · 2002
Earlier work this paper cites.
Reinforcement learning with immediate rewards and linear hypotheses
Naoki Abe, Alan W Biermann, and Philip M Long · 2003
Earlier work this paper cites.
Optimal aggregation of classifiers in statistical learning
Alexander B Tsybakov · 2004
Earlier work this paper cites.
Concentration inequalities and asymptotic results for ratio type empirical processes
Evarist Giné and Vladimir Koltchinskii · 2006
Earlier work this paper cites.
Fast learning rates for plug-in classifiers
Jean-Yves Audibert, Alexandre B Tsybakov, et al · 2007
Earlier work this paper cites.
A bound on the label complexity of agnostic active learning
Steve Hanneke · 2007
Earlier work this paper cites.
Progressive mixture rules are deviation suboptimal
Jean-Yves Audibert · 2008
Earlier work this paper cites.
Stochastic linear optimization under bandit feedback
Varsha Dani, Thomas P Hayes, and Sham M Kakade · 2008
Earlier work this paper cites.
The epoch-greedy algorithm for multi-armed bandits with side information
John Langford and Tong Zhang · 2008
Earlier work this paper cites.
Optimistic linear programming gives logarithmic regret for irreducible MDPs
Ambuj Tewari and Peter L Bartlett · 2008
Earlier work this paper cites.
Introduction to Nonparametric Estimation
Alexandre B Tsybakov · 2008
Earlier work this paper cites.
Active learning for smooth problems
Eric Friedman · 2009
Earlier work this paper cites.
The true sample complexity of active learning
Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan · 2010
Earlier work this paper cites.
A contextual-bandit approach to personalized news article recommendation
Lihong Li, Wei Chu, John Langford, and Robert E Schapire · 2010
Earlier work this paper cites.
Nonparametric bandits with covariates
Philippe Rigollet and Assaf Zeevi · 2010
Earlier work this paper cites.
Improved algorithms for linear stochastic bandits
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári · 2011
Earlier work this paper cites.

Similar

Contextual bandits with linear payoff functions
Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire · 2011
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer · 2011
Cited alongside, same era.
Rates of convergence in active learning
Steve Hanneke · 2011
Cited alongside, same era.
Online importance weight aware updates
Nikos Karampatziakis and John Langford · 2011
Cited alongside, same era.
Lower bounds for passive and active learning
Maxim Raginsky and Alexander Rakhlin · 2011
Cited alongside, same era.
Contextual bandit learning with predictable rewards
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert E. Schapire · 2012
Cited alongside, same era.
Active and passive learning of linear separators under log-concave distributions
Maria-Florina Balcan and Phil Long · 2013
Cited alongside, same era.
The multi-armed bandit problem with covariates
Vianney Perchet and Philippe Rigollet · 2013
Cited alongside, same era.
Normalized online learning
Stéphane Ross, Paul Mineiro, and John Langford · 2013
Cited alongside, same era.
Eluder dimension and the sample complexity of optimistic exploration
Daniel Russo and Benjamin Van Roy · 2013
Cited alongside, same era.
Taming the monster: A fast and simple algorithm for contextual bandits
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire · 2014
Cited alongside, same era.
Thompson sampling with the online bootstrap
Original
Dean Eckles and Maurits Kaptein · 2014
Cited alongside, same era.

Then

Active learning for cost-sensitive classification
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford · 2017
Later among the works it cites.
From ads to interventions: Contextual bandits in mobile health
Ambuj Tewari and Susan A. Murphy · 2017
Later among the works it cites.
Efficient reinforcement learning in deterministic systems with value function generalization
Zheng Wen and Benjamin Van Roy · 2017
Later among the works it cites.
A contextual bandit bake-off
Original
Alberto Bietti, Alekh Agarwal, and John Langford · 2018
Later among the works it cites.
On oracle-efficient PAC RL with rich observations
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire · 2018
Later among the works it cites.
Practical contextual bandits with regression oracles
Dylan J Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert E. Schapire · 2018
Later among the works it cites.
Refining the confidence level for optimistic bandit strategies
Tor Lattimore · 2018
Later among the works it cites.
Exploration in structured reinforcement learning
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos · 2018
Later among the works it cites.
Explore first, exploit next: The true shape of regret in bandit problems
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz · 2019
Later among the works it cites.
Adaptive exploration in linear contextual bandit
Original
Botao Hao, Tor Lattimore, and Csaba Szepesvari · 2019
Later among the works it cites.
Kinematic state abstraction and provably efficient rich-observation reinforcement learning
Original
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford · 2019
Later among the works it cites.
Non-asymptotic gap-dependent regret bounds for tabular MDPs
Max Simchowitz and Kevin G Jamieson · 2019
Later among the works it cites.
Optimism in reinforcement learning with generalized linear function approximation
Original
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy · 2019
Later among the works it cites.
FLAMBE: Structural complexity and representation learning of low rank MDPs
Original
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun · 2020
Closest in time.
Model-based reinforcement learning with value-targeted regression
Original
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin F Yang · 2020
Closest in time.
Online decision making with high-dimensional covariates
Hamsa Bastani and Mohsen Bayati · 2020
Closest in time.
Provably efficient exploration for RL with unsupervised learning
Original
Fei Feng, Ruosong Wang, Wotao Yin, Simon S Du, and Lin F Yang · 2020
Closest in time.
Beyond UCB: Optimal and efficient contextual bandits with regression oracles
Dylan J Foster and Alexander Rakhlin · 2020
Closest in time.
Smooth contextual bandits: Bridging the parametric and non-differentiable regret regimes
Yichun Hu, Nathan Kallus, and Xiaojie Mao · 2020
Closest in time.
Provably efficient reinforcement learning with linear function approximation
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan · 2020
Closest in time.
Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability
Original
David Simchi-Levi and Yunzong Xu · 2020
Closest in time.
Provably efficient reinforcement learning with general value function approximation
Original
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang · 2020
Closest in time.
Upper counterfactual confidence bounds: a new optimism principle for contextual bandits
Original
Yunbei Xu and Assaf Zeevi · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…