# Contextual Bandits with Large Action Spaces: Made Practical

arXiv: https://arxiv.org/abs/2207.05836 · HTML: https://mlsanity.com/paper/2207.05836/

## 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 (most cited first, 30 of 35)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Semi-Parametric Efficient Policy Learning with Continuous Actions](https://mlsanity.com/paper/1905.10116/) (2019)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [Efficient Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2006.06040/) (2020)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Policy Gradients for Contextual Recommendations](https://mlsanity.com/paper/1802.04162/) (2018)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)

## Built on by (most cited first, 30 of 33)

- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Efficient Sequential Decision Making with Large Language Models](https://mlsanity.com/paper/2406.12125/) (2024)
- [Sample-Efficient Alignment for LLMs](https://mlsanity.com/paper/2411.01493/) (2024)
- [Exponential Smoothing for Off-Policy Learning](https://mlsanity.com/paper/2305.15877/) (2023)
- [Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2306.07923/) (2023)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Embedding-Aligned Language Models](https://mlsanity.com/paper/2406.00024/) (2024)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning](https://mlsanity.com/paper/2402.12711/) (2024)
- [Bayesian Off-Policy Evaluation and Learning for Large Action Spaces](https://mlsanity.com/paper/2402.14664/) (2024)
- [Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback](https://mlsanity.com/paper/2510.09127/) (2025)
- [Why Keep Your Doubts to Yourself? Trading Visual Uncertainties in Multi-Agent Bandit Systems](https://mlsanity.com/paper/2601.18735/) (2026)
- [Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits](https://mlsanity.com/paper/2602.09456/) (2026)
- [Unified PAC-Bayesian Study of Pessimism for Offline Policy Learning with Regularized Importance Sampling](https://mlsanity.com/paper/2406.03434/) (2024)
- [DISCO: An End-to-End Bandit Framework for Personalised Discount Allocation](https://mlsanity.com/paper/2406.06433/) (2024)
- [Contextual bandits with concave rewards, and an application to fair ranking](https://mlsanity.com/paper/2210.09957/) (2022)
- [Conditionally Risk-Averse Contextual Bandits](https://mlsanity.com/paper/2210.13573/) (2022)
- [Learning to Generate All Feasible Actions](https://mlsanity.com/paper/2301.11461/) (2023)
- [Infinite Action Contextual Bandits with Reusable Data Exhaust](https://mlsanity.com/paper/2302.08551/) (2023)
- [Optimizing Novelty of Top-k Recommendations using Large Language Models and Reinforcement Learning](https://mlsanity.com/paper/2406.14169/) (2024)
- [Optimal Regret for Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2602.13700/) (2026)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback](https://mlsanity.com/paper/2606.01081/) (2026)
- [Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation](https://mlsanity.com/paper/2607.13686/) (2026)
- [RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits](https://mlsanity.com/paper/2603.11276/) (2026)
- [Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts](https://mlsanity.com/paper/2606.09802/) (2026)

## 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.