mlsanityData to 14 Oct 2026

Contextual Bandits with Large Action Spaces: Made Practical

arXiv 2207.05836 ↗First posted 12 Jul 2022cs.LG stat.MLcited by 33

Not on the map. Why?

Abstract (arXiv)

A central problem in sequential decision making is to develop algorithms that are practical and computationally efficient, yet support the use of flexible, general-purpose models. Focusing on the contextual bandit problem, recent progress provides provably efficient algorithms with strong empirical performance when the number of possible alternatives ("actions") is small, but guarantees for decision making in large, continuous action spaces have remained elusive, leading to a significant gap between theory and practice. We present the first efficient, general-purpose algorithm for contextual bandits with continuous, linearly structured action spaces. Our algorithm makes use of computational oracles for (i) supervised learning, and (ii) optimization over the action space, and achieves sample complexity, runtime, and memory independent of the size of the action space. In addition, it is simple and practical. We perform a large-scale empirical evaluation, and show that our approach typically enjoys superior performance and efficiency compared to standard baselines.

Key facts. Cited by 33 papers in the map (data through 14 Oct 2026). Builds on 35 of its 78 references that are in the map. First posted on arXiv 12 Jul 2022.

Builds on

35 of 78 references.

References · 35

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  2. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,170
  3. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  4. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  5. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  6. 2020Neural Thompson Samplingcited by 128
  7. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  8. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  9. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  10. 2014Best-Arm Identification in Linear Banditscited by 100
  11. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  12. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
23 more
  1. 2021Adapting to Misspecification in Contextual Banditscited by 81
  2. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  3. 2020Neural Contextual Bandits with Deep Representation and Shallow Explorationcited by 71
  4. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  5. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 64
  6. 2018A Contextual Bandit Bake-offcited by 64
  7. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  8. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  9. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  10. 2019Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adaptingcited by 42
  11. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 40
  12. 2021Neural Contextual Bandits without Regretcited by 40
  13. 2019Semi-Parametric Efficient Policy Learning with Continuous Actionscited by 26
  14. 2013Volumetric Spanners: an Efficient Exploration Basis for Learningcited by 24
  15. 2020Efficient Contextual Bandits with Continuous Actionscited by 24
  16. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
  17. 2018Policy Gradients for Contextual Recommendationscited by 21
  18. 2017Nearly Optimal Sampling Algorithms for Combinatorial Pure Explorationcited by 19
  19. 2020Experimental Design for Regret Minimization in Linear Banditscited by 11
  20. 2013Word Emdeddings through Hellinger PCAcited by 10
  21. 2019Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithmcited by 9
  22. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 9
  23. 2014On largest volume simplices and sub-determinantscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 5; 2023: 6; 2024: 10; 2025: 2; 2026: 10.

33 papers.

Sort:

By area:

  1. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  2. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  3. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  4. 2024Efficient Sequential Decision Making with Large Language Modelscited by 16
  5. 2024Sample-Efficient Alignment for LLMscited by 16
  6. 2023Exponential Smoothing for Off-Policy Learningcited by 15
  7. 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Banditscited by 15
  8. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  9. 2024Embedding-Aligned Language Modelscited by 9
  10. 2024Contextual Bandits for Unbounded Context Distributionscited by 8
  11. 2025Strategic Scaling of Test-Time Compute: A Bandit Learning Approachcited by 8
  12. 2024Diffusion Models Meet Contextual Banditscited by 5
21 more
  1. 2024Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learningcited by 5
  2. 2024Bayesian Off-Policy Evaluation and Learning for Large Action Spacescited by 5
  3. 2025Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedbackcited by 5
  4. 2026Why Keep Your Doubts to Yourself? Trading Visual Uncertainties in Multi-Agent Bandit Systemscited by 4
  5. 2026Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Banditscited by 4
  6. 2024Unified PAC-Bayesian Study of Pessimism for Offline Policy Learning with Regularized Importance Samplingcited by 3
  7. 2024DISCO: An End-to-End Bandit Framework for Personalised Discount Allocationcited by 3
  8. 2022Contextual bandits with concave rewards, and an application to fair rankingcited by 2
  9. 2022Conditionally Risk-Averse Contextual Banditscited by 2
  10. 2023Learning to Generate All Feasible Actionscited by 2
  11. 2023Infinite Action Contextual Bandits with Reusable Data Exhaustcited by 2
  12. 2024Optimizing Novelty of Top-k Recommendations using Large Language Models and Reinforcement Learningcited by 2
  13. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 2
  14. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  15. 2026Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedbackcited by 1
  16. 2026Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximationcited by 1
  17. 2026RIE-Greedy: Regularization-Induced Exploration for Contextual Banditscited by 0
  18. 2026Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Driftscited by 0
  19. 2026Personalizing Large Language Model Agents with Small Policy Modelscited by 0
  20. 2026Human-inspired, Task-Dimension-Guided Exploration for Efficient Learning in High Dimensionscited by 0
  21. 2026Accelerating Linear Bandits with Persistent Candidate Setscited by 0