mlsanityData to 7 Oct 2026

Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles

arXiv 2002.04926 ↗First posted 12 Feb 2020cs.LG math.ST stat.MLcited by 195

Not on the map. Why?

Abstract (arXiv)

A fundamental challenge in contextual bandits is to develop flexible, general-purpose algorithms with computational requirements no worse than classical supervised learning tasks such as classification and regression. Algorithms based on regression have shown promising empirical success, but theoretical guarantees have remained elusive except in special cases. We provide the first universal and optimal reduction from contextual bandits to online regression. We show how to transform any oracle for online regression with a given value function class into an algorithm for contextual bandits with the induced policy class, with no overhead in runtime or memory requirements. We characterize the minimax rates for contextual bandits with general, potentially nonparametric function classes, and show that our algorithm is minimax optimal whenever the oracle obtains the optimal rate for regression. Compared to previous results, our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 32; 2022: 36; 2023: 43; 2024: 31; 2025: 25; 2026: 28.

195 papers.

Sort:

By area:

  1. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  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. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  8. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  9. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  10. 2021Heuristic-Guided Reinforcement Learningcited by 41
  11. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  12. 2023Oracle Efficient Online Multicalibration and Omnipredictioncited by 36
38 more
  1. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  2. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  3. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  4. 2023Multicalibration as Boosting for Regressioncited by 32
  5. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  6. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  7. 2022Redeeming Intrinsic Rewards via Constrained Optimizationcited by 24
  8. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  9. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  10. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  11. 2021Distribution-free Contextual Dynamic Pricingcited by 22
  12. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  13. 2022Efficient Active Learning with Abstentioncited by 21
  14. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  15. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  16. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  17. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  18. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  19. 2022Optimistic Whittle Index Policy: Online Learning for Restless Banditscited by 18
  20. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  21. 2021Majorizing Measures, Sequential Complexities, and Online Learningcited by 17
  22. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 17
  23. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  24. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  25. 2022Contextual Information-Directed Samplingcited by 16
  26. 2022Instance-optimal PAC Algorithms for Contextual Banditscited by 16
  27. 2024Efficient Sequential Decision Making with Large Language Modelscited by 16
  28. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  29. 2021On component interactions in two-stage recommender systemscited by 14
  30. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  31. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  32. 2021Model Selection in Batch Policy Optimizationcited by 11
  33. 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
  34. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  35. 2021Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learningcited by 10
  36. 2022Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functionscited by 10
  37. 2023Practical Contextual Bandits with Feedback Graphscited by 10
  38. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10

50 most cited of 195 All 195 (JSON)