mlsanityData to 7 Oct 2026

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability

arXiv 2003.12699 ↗First posted 28 Mar 2020cs.LG math.ST stat.MLcited by 114

Not on the map. Why?

Abstract (arXiv)

We consider the general (stochastic) contextual bandit problem under the realizability assumption, i.e., the expected reward, as a function of contexts and actions, belongs to a general function class F. We design a fast and simple algorithm that achieves the statistically optimal regret with only O(log T) calls to an offline regression oracle across all T rounds. The number of oracle calls can be further reduced to O(loglog T) if T is known in advance. Our results provide the first universal and optimal reduction from contextual bandits to offline regression, solving an important open problem in the contextual bandit literature. A direct consequence of our results is that any advances in offline regression immediately translate to contextual bandits, statistically and computationally. This leads to faster algorithms and improved regret guarantees for broader classes of contextual bandit problems.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 22; 2023: 24; 2024: 19; 2025: 17; 2026: 15.

114 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  2. 2022Jump-Start Reinforcement Learningcited by 102
  3. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  4. 2021Adapting to Misspecification in Contextual Banditscited by 81
  5. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  6. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  7. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  8. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  9. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  10. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  11. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  12. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
38 more
  1. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  2. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  3. 2022Efficient Active Learning with Abstentioncited by 21
  4. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  5. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  6. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  7. 2024LOLA: LLM-Assisted Online Learning Algorithm for Content Experimentscited by 18
  8. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 17
  9. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  10. 2022Contextual Information-Directed Samplingcited by 16
  11. 2022Instance-optimal PAC Algorithms for Contextual Banditscited by 16
  12. 2024Efficient Sequential Decision Making with Large Language Modelscited by 16
  13. 2021On component interactions in two-stage recommender systemscited by 14
  14. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  15. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  16. 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
  17. 2021Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learningcited by 10
  18. 2022Learning Efficiently Function Approximation for Contextual MDPcited by 10
  19. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  20. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  21. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
  22. 2023Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximationcited by 9
  23. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  24. 2021Top-k eXtreme Contextual Bandits with Arm Hierarchycited by 8
  25. 2021Model Selection for Generic Contextual Banditscited by 7
  26. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  27. 2023Smoothed Analysis of Sequential Probability Assignmentcited by 7
  28. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  29. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  30. 2022Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learningcited by 6
  31. 2023Sequential Counterfactual Risk Minimizationcited by 6
  32. 2024Efficient Contextual Bandits with Uninformed Feedback Graphscited by 6
  33. 2024No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimizationcited by 6
  34. 2025Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functionscited by 6
  35. 2021Universal and data-adaptive algorithms for model selection in linear contextual banditscited by 5
  36. 2022Integrating Reward Maximization and Population Estimation: Sequential Decision-Making for Internal Revenue Service Audit Selectioncited by 5
  37. 2022Breaking the √T Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Banditscited by 5
  38. 2022Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guaranteescited by 5

50 most cited of 114 All 114 (JSON)