Contextual Bandits with Large Action Spaces: Made Practical

Yinglun Zhu, Dylan J. Foster, John Langford, Paul Mineiro

Abstract

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.

Introduction

Contextual bandit algorithms are the backbone of modern personalized systems, ranging from news recommendation to targeted advertising. In these scenarios, an agent observes a context (e.g., a user profile), selects an action (e.g., a specific article), and receives a reward (e.g., a click). While standard algorithms perform well when the action space is small, they often fail in modern production environments where the number of actions can reach millions or even exist in a continuous space.

Historically, general-purpose algorithms have suffered from a complexity that scales linearly with the number of actions, making them computationally prohibitive at scale. This paper introduces SpannerIGW, a novel algorithm that bridges the gap between theoretical efficiency and practical large-scale deployment by decoupling computational complexity from the size of the action space.

The Large Action Space Problem

The primary bottleneck in contextual bandits is the "Large Action Space" problem. If an algorithm must evaluate every possible action to make a decision, its runtime and memory usage grow linearly with the action count ($K$). In systems like the amazon-3m dataset, which contains nearly 3 million tags, a linear dependency makes real-time inference impossible. Previous attempts to solve this either relied on overly restrictive mathematical assumptions or resulted in exponential sample complexity, rendering them impractical for real-world applications.

Methodology

The authors propose a framework where the reward is linearly structured in the action space but can remain non-linear in the context space. Specifically, the reward for a context-action pair $(x, a)$ is modeled as the inner product of a known action feature $\phi(x, a)$ and a learned context embedding $g(x)$. To solve this, the paper introduces two primary algorithmic components:

1. SpannerGreedy

As a foundational step, the authors utilize Barycentric Spanners. This approach identifies a small, representative subset of actions that "span" the geometry of the entire action space. By exploring only this basis, the algorithm avoids the need to iterate through every action. While SpannerGreedy provides a starting point, it achieves a sub-optimal regret of $T^{2/3}$.

2. SpannerIGW

The core innovation, SpannerIGW, combines the spanner concept with Inverse Gap Weighting (IGW). IGW is a sampling strategy that prioritizes actions with high predicted rewards while maintaining enough exploration of uncertain actions to ensure learning. By performing this weighting over the reweighted geometry of the action space, SpannerIGW achieves the optimal $\sqrt{T}$ regret.

Crucially, the algorithm is oracle-efficient. it reduces the bandit problem to two "black box" operations:

  • Supervised Learning Oracle: For regression to estimate rewards.
  • Optimization Oracle: For finding the best action given a linear score.

This design allows the algorithm to leverage existing high-performance tools like deep neural networks and Maximum Inner Product Search (MIPS) libraries.

Empirical Evaluation

The researchers conducted a large-scale evaluation across three benchmarks to test the algorithm's limits:

  • oneshotwiki-311 & oneshotwiki-14031: Named-entity recognition tasks converted into bandit problems with up to 14,000 actions.
  • amazon-3m: A multi-label dataset featuring 2.8 million actions, serving as a stress test for extreme scale.

Key Results

  • Scalability: On the amazon-3m dataset, SpannerIGW achieved a reward of approximately 0.44, more than doubling the performance of previous state-of-the-art tree-based methods (~0.19).
  • Performance: In the Wiki datasets, SpannerIGW consistently outperformed standard baselines like $\epsilon$-Greedy and SquareCB, particularly when paired with deep neural network context models.
  • Efficiency: While more computationally intensive than a simple greedy approach (25ms vs 2ms inference time), the algorithm remains well within the requirements for production systems, and its memory footprint remains independent of the action space size.

Key Insights

  • Geometric Exploration: The research demonstrates that if actions have a linear structure, one only needs to explore a "basis" of $d$ actions (where $d$ is the feature dimension), regardless of whether the total pool contains thousands or billions of items.
  • Redundancy Robustness: Unlike algorithms like SquareCB, which can be misled by duplicate actions, SpannerIGW is invariant to redundant actions because it focuses on the underlying geometry of the action space.
  • Production Readiness: By reducing the problem to a linear optimization oracle, the approach is natively compatible with industry-standard MIPS libraries, making it ready for immediate integration into existing recommendation pipelines.

Conclusion and Future Work

SpannerIGW represents a significant step forward in making contextual bandits practical for massive action spaces. By achieving sample complexity and runtime independent of the number of actions, it removes a major barrier to using sophisticated bandit algorithms in the real world. Future research may explore extending these geometric spanner techniques to full Reinforcement Learning (multi-step decision making) and relaxing the linearity assumption for even more complex action-reward relationships.

Summary updated

Abstract

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.
BibTeX
@inproceedings{zhu2022contextual,
  author = {Yinglun Zhu and Dylan J. Foster and John Langford and Paul Mineiro},
  title = {{Contextual Bandits with Large Action Spaces: Made Practical}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=N-NHyF5wwFC},
}
Figure