mlsanityData to 7 Oct 2026

Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles

arXiv 2102.13240 ↗First posted 26 Feb 2021cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

Computationally efficient contextual bandits are often based on estimating a predictive model of rewards given contexts and arms using past data. However, when the reward model is not well-specified, the bandit algorithm may incur unexpected regret, so recent work has focused on algorithms that are robust to misspecification. We propose a simple family of contextual bandit algorithms that adapt to misspecification error by reverting to a good safe policy when there is evidence that misspecification is causing a regret increase. Our algorithm requires only an offline regression oracle to ensure regret guarantees that gracefully degrade in terms of a measure of the average misspecification level. Compared to prior work, we attain similar regret guarantees, but we do no rely on a master algorithm, and do not require more robust oracles like online or constrained regression oracles (e.g., Foster et al. (2020a); Krishnamurthy et al. (2020)). This allows us to design algorithms for more general function approximation classes.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 11 of its 19 references that are in the map. First posted on arXiv 26 Feb 2021.

Builds on

11 of 19 references.

References · 11

  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  2. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  3. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  4. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  5. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  6. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  7. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  8. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 42
  9. 2017Misspecified Linear Banditscited by 41
  10. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
  11. 2020Tractable contextual bandits beyond realizabilitycited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 6; 2024: 1; 2025: 1; 2026: 4.

21 papers.

Sort:

By area:

  1. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  2. 2021Metadata-based Multi-Task Bandits with Bayesian Hierarchical Modelscited by 24
  3. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  4. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  5. 2022Leveraging Initial Hints for Free in Stochastic Linear Banditscited by 7
  6. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  7. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  8. 2022Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learningcited by 6
  9. 2026Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directionscited by 5
  10. 2021Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspectivecited by 4
  11. 2021Dealing with Expert Bias in Collective Decision-Makingcited by 4
  12. 2022Robust Contextual Linear Banditscited by 4
9 more
  1. 2023Robust Causal Bandits for Linear Modelscited by 4
  2. 2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
  3. 2026Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Banditscited by 2
  4. 2022Flexible and Efficient Contextual Bandits with Heterogeneous Treatment Effect Oraclescited by 1
  5. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  6. 2026Direction-Aware Offline-to-Online Learning in Linear Contextual Banditscited by 1
  7. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 1
  8. 2023Federated Offline Policy Learningcited by 0
  9. 2025Co-Exploration and Co-Exploitation via Shared Structure in Multi-Task Banditscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits
  2. 2026Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
  3. 2026Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
  4. 2023Bad Values but Good Behavior: Learning Highly Misspecified Bandits and MDPs
  5. 2023Contextual Bandits and Imitation Learning via Preference-Based Active Queries
  6. 2025Statistical Inference for Misspecified Contextual Bandits
  7. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
  8. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis