mlsanityData to 7 Oct 2026

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

arXiv 1402.0555 ↗First posted 4 Feb 2014cs.LG stat.MLcited by 200

Not on the map. Why?

Abstract (arXiv)

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only tildeO(√KT/log N) oracle calls across all T rounds, where N is the number of policies in the policy class we compete against. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We further conduct a proof-of-concept experiment which demonstrates the excellent computational and prediction performance of (an online variant of) our algorithm relative to several baselines.

Key facts. Cited by 200 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Feb 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 36; 2022: 42; 2023: 40; 2024: 31; 2025: 23; 2026: 27.

200 papers.

Sort:

By area:

  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  3. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  4. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  5. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  6. 2021Adapting to Misspecification in Contextual Banditscited by 81
  7. 2019Provably Efficient Imitation Learning from Observation Alonecited by 78
  8. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  9. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  10. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  11. 2021Distributionally Robust Learningcited by 44
  12. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
38 more
  1. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  2. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  3. 2022Making Decisions under Outcome Performativitycited by 32
  4. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  5. 2022Chain of Thought Imitation with Procedure Cloningcited by 30
  6. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  7. 2025FOCUS: Efficient Keyframe Selection for Long Video Understandingcited by 30
  8. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  9. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  10. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  11. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  12. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  13. 2021Logarithmic Regret in Feature-based Dynamic Pricingcited by 22
  14. 2021Online Multi-Armed Bandits with Adaptive Inferencecited by 21
  15. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  16. 2022Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noisecited by 21
  17. 2022Efficient Active Learning with Abstentioncited by 21
  18. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  19. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  20. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  21. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  22. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 17
  23. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  24. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  25. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  26. 2022Contextual Information-Directed Samplingcited by 16
  27. 2022Instance-optimal PAC Algorithms for Contextual Banditscited by 16
  28. 2024Efficient Sequential Decision Making with Large Language Modelscited by 16
  29. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  30. 2023Model-based Constrained MDP for Budget Allocation in Sequential Incentive Marketingcited by 15
  31. 2023Exponential Smoothing for Off-Policy Learningcited by 15
  32. 2023Importance-Weighted Offline Learning Done Rightcited by 15
  33. 2021Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descentcited by 14
  34. 2021On component interactions in two-stage recommender systemscited by 14
  35. 2023Multi-channel Autobidding with Budget and ROI Constraintscited by 14
  36. 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Banditscited by 14
  37. 2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 13
  38. 2022Active Learning with Neural Networks: Insights from Nonparametric Statisticscited by 13

50 most cited of 200 All 200 (JSON)