mlsanityData to 14 Oct 2026

Adapting to Misspecification in Contextual Bandits

arXiv 2107.05745 ↗First posted 12 Jul 2021cs.LG stat.MLcited by 81

Not on the map. Why?

Abstract (arXiv)

A major research direction in contextual bandits is to develop algorithms that are computationally efficient, yet support flexible, general-purpose function approximation. Algorithms based on modeling rewards have shown strong empirical performance, but typically require a well-specified model, and can fail when this assumption does not hold. Can we design algorithms that are efficient and flexible, yet degrade gracefully in the face of model misspecification? We introduce a new family of oracle-efficient algorithms for varepsilon-misspecified contextual bandits that adapt to unknown model misspecification -- both for finite and infinite action settings. Given access to an online oracle for square loss regression, our algorithm attains optimal regret and -- in particular -- optimal dependence on the misspecification level, with no prior knowledge. Specializing to linear contextual bandits with infinite actions in d dimensions, we obtain the first algorithm that achieves the optimal O(d√T + varepsilon√dT) regret bound for unknown misspecification level varepsilon. On a conceptual level, our results are enabled by a new optimization-based perspective on the regression oracle reduction framework of Foster and Rakhlin, which we anticipate will find broader use.

Key facts. Cited by 81 papers in the map (data through 14 Oct 2026). Builds on 22 of its 48 references that are in the map. First posted on arXiv 12 Jul 2021.

Builds on

22 of 48 references.

References · 22

  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  2. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  3. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  4. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  5. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  6. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  7. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  8. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  9. 2016Corralling a Band of Bandit Algorithmscited by 100
  10. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  11. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  12. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
10 more
  1. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  2. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  3. 2019Model selection for contextual banditscited by 60
  4. 2015Fighting Bandits with a New Kind of Smoothnesscited by 47
  5. 2017Misspecified Linear Banditscited by 42
  6. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 40
  7. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  8. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 33
  9. 2019Semi-Parametric Efficient Policy Learning with Continuous Actionscited by 26
  10. 2015A Chaining Algorithm for Online Nonparametric Regressioncited by 16

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 19; 2023: 21; 2024: 7; 2025: 10; 2026: 14.

81 papers.

Sort:

By area:

  1. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  2. 2021Misspecified Gaussian Process Bandit Optimizationcited by 55
  3. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  4. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  5. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  6. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 33
  7. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  8. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  9. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  10. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
  11. 2022Bayesian Optimization with Conformal Prediction Setscited by 28
  12. 2021Metadata-based Multi-Task Bandits with Bayesian Hierarchical Modelscited by 24
38 more
  1. 2021The Pareto Frontier of model selection for general Contextual Banditscited by 24
  2. 2021Distribution-free Contextual Dynamic Pricingcited by 22
  3. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  4. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  5. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  6. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  7. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 18
  8. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 18
  9. 2022Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum Statescited by 15
  10. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  11. 2024Trustworthy Distributed AI Systems: Robustness, Privacy, and Governancecited by 14
  12. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 12
  13. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  14. 2023Online Clustering of Bandits with Misspecified User Modelscited by 12
  15. 2022Towards Scalable and Robust Structured Bandits: A Meta-Learning Frameworkcited by 11
  16. 2022Best of Both Worlds Model Selectioncited by 11
  17. 2023Practical Contextual Bandits with Feedback Graphscited by 11
  18. 2023Data-Driven Online Model Selection With Regret Guaranteescited by 11
  19. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
  20. 2022Damped Online Newton Step for Portfolio Selectioncited by 9
  21. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  22. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  23. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  24. 2024The Real Price of Bandit Information in Multiclass Classificationcited by 7
  25. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 7
  26. 2025Offline-to-online hyperparameter transfer for stochastic banditscited by 7
  27. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  28. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
  29. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  30. 2024Diffusion Models Meet Contextual Banditscited by 5
  31. 2024Thompson Sampling in Partially Observable Contextual Banditscited by 5
  32. 2025Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?cited by 5
  33. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  34. 2026Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directionscited by 5
  35. 2022Robust Contextual Linear Banditscited by 4
  36. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 4
  37. 2023Robust Causal Bandits for Linear Modelscited by 4
  38. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 4

50 most cited of 81 All 81 (JSON)