mlsanityData to 7 Oct 2026

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits

arXiv 2602.09456 ↗First posted 10 Feb 2026cs.LG stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that efficiently reduces contextual bandit learning with general reward function approximation to offline regression. The framework allows near-optimal regret for contextual bandits with large action spaces with O(log T) calls to an offline regression oracle over T rounds, and makes O(loglog T) calls when T is known. The design of OE2D algorithm generalizes Falcon~citepsimchi2022bypassing and its linear reward version~citep[][Section 4]xu2020upper in that it finds an action distribution that we term ``exploitative F-design'' that simultaneously guarantees low regret and good coverage, striking a balance between exploration and exploitation. Central to our regret analysis is a new complexity measure, the Decision-Offline Estimation Coefficient (DOEC), which we show is small in many settings, including bounded Eluder dimension per-context and the smoothed regret setting. We also establish a relationship between DOEC and Decision Estimation Coefficient (DEC)~citepfoster2021statistical, bridging the design principles of offline- and online-oracle efficient contextual bandit algorithms for the first time.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 29 of its 57 references that are in the map. First posted on arXiv 10 Feb 2026.

Builds on

29 of 57 references.

References · 29

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2022Training language models to follow instructions with human feedbackcited by 15,712
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  4. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  5. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  6. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  7. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  8. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  9. 2023Is RLHF More Difficult than Standard RL?cited by 96
  10. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  11. 2021Adapting to Misspecification in Contextual Banditscited by 81
  12. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
17 more
  1. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  2. 2018A Contextual Bandit Bake-offcited by 64
  3. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  4. 2019Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adaptingcited by 42
  5. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
  6. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  7. 2019Semi-Parametric Efficient Policy Learning with Continuous Actionscited by 26
  8. 2020Efficient Contextual Bandits with Continuous Actionscited by 24
  9. 2013Empirical entropy, minimax regret and minimax riskcited by 21
  10. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  11. 2022Efficient Active Learning with Abstentioncited by 21
  12. 2021Understanding the Eluder Dimensioncited by 19
  13. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 17
  14. 2015Contextual Semibandits via Supervised Learning Oraclescited by 11
  15. 2024Online Estimation via Offline Estimation: An Information-Theoretic Frameworkcited by 11
  16. 2020Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimalitycited by 7
  17. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 1
  2. 2026Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximationcited by 0