mlsanityData to 7 Oct 2026

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

arXiv 2010.03104 ↗First posted 7 Oct 2020cs.LG math.ST stat.MLcited by 78

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 78 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 14; 2023: 18; 2024: 11; 2025: 9; 2026: 7.

78 papers.

Sort:

By area:

  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  5. 2021Adapting to Misspecification in Contextual Banditscited by 81
  6. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  7. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  8. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  9. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  10. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  11. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  12. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
38 more
  1. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  2. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  3. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  4. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  5. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  6. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 29
  7. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  8. 2022Efficient Active Learning with Abstentioncited by 21
  9. 2021Understanding the Eluder Dimensioncited by 19
  10. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  11. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  12. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 17
  13. 2022Instance-optimal PAC Algorithms for Contextual Banditscited by 16
  14. 2022Fast Rates in Pool-Based Batch Active Learningcited by 15
  15. 2022Active Learning with Neural Networks: Insights from Nonparametric Statisticscited by 13
  16. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  17. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
  18. 2023Selective Sampling and Imitation Learning via Online Regressioncited by 12
  19. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 11
  20. 2023Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximationcited by 9
  21. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  22. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  23. 2021Top-k eXtreme Contextual Bandits with Arm Hierarchycited by 8
  24. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  25. 2021A Short Note on the Relationship of Information Gain and Eluder Dimensioncited by 7
  26. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  27. 2023Smoothed Analysis of Sequential Probability Assignmentcited by 7
  28. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  29. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  30. 2024The Real Price of Bandit Information in Multiclass Classificationcited by 7
  31. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  32. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  33. 2024The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regretcited by 6
  34. 2022Integrating Reward Maximization and Population Estimation: Sequential Decision-Making for Internal Revenue Service Audit Selectioncited by 5
  35. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  36. 2021Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspectivecited by 4
  37. 2023Provably Efficient Reinforcement Learning via Surprise Boundcited by 4
  38. 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learningcited by 4

50 most cited of 78 All 78 (JSON)