Contextual Bandits with Large Action Spaces: Made Practical

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

Overview

This paper introduces SpannerIGW, the first computationally efficient, general-purpose algorithm for contextual bandits with large or continuous action spaces. By combining "barycentric spanners"—a method to find a representative set of actions—with inverse gap weighting, the authors achieve optimal $\sqrt{T}$ regret while keeping runtime and memory completely independent of the total number of actions.

The Challenge of Large Action Spaces

In the contextual bandit problem, an agent observes a context (like a user profile), chooses an action (like recommending a news article), and receives a reward (a click). While highly effective algorithms exist for scenarios with a few dozen actions, many real-world problems involve millions of choices, such as every possible image in a database or every product in a massive catalog.

Existing "general-purpose" algorithms, which can leverage flexible models like neural networks or random forests, typically suffer from a fatal flaw: their computational cost and sample requirements grow linearly with the number of actions. For a million actions, these algorithms become practically unusable. Previous attempts to solve this either required specific, restrictive models or incurred costs that exploded exponentially with the dimension of the actions. This paper seeks a "best of both worlds" solution: an algorithm that is statistically efficient, computationally practical, and compatible with flexible models.

Methodology: Spanners and Inverse Gap Weighting

The authors propose two main algorithms based on the assumption that rewards are linearly structured in the action space: $f(x, a) = \langle \phi(x, a), g(x) \rangle$, where $\phi$ is a known feature map and $g$ is a context embedding learned online.

  1. SpannerGreedy (The Warm-up): This algorithm uses a G-optimal design—a small, representative subset of actions that "spans" the entire space. It explores by picking actions from this subset and exploits by picking the best-predicted action. While simple, its regret (error rate) scales as $T^{2/3}$, which is sub-optimal.
  2. SpannerIGW (The Main Event): To achieve the optimal $\sqrt{T}$ regret, the authors combine optimal design with Inverse Gap Weighting (IGW). IGW typically assigns probabilities to actions based on how close their predicted reward is to the "best" action.
  3. The "Spanner" Secret Sauce: The key technical challenge is finding that representative subset of actions efficiently. The authors use Barycentric Spanners, which allow them to approximate an optimal design using only a "linear optimization oracle" (a tool that can find the best action for a given linear weight).
  4. Reweighted Spanner: For SpannerIGW, the "effective" action space changes based on the model's current uncertainty. The authors developed a novel "ReweightedSpanner" algorithm to handle this context-dependent geometry without losing efficiency.

Key Insights

  • Independence from Action Count: The most significant breakthrough is that by using a barycentric spanner, the algorithm only scales with the dimension ($d$) of the action features, not the total number of actions. This makes it truly viable for large-scale applications.
  • Redundancy Invariance: Unlike standard algorithms, SpannerIGW is mathematically invariant to duplicate actions. If you add 1,000 identical "Buy" buttons, SpannerIGW won't waste time exploring them 1,000 times more; it treats them as a single point in the feature space.
Performance of SpannerIGW vs. SquareCB with duplicate actions.
  • Lifting Optimal Design: The paper successfully "lifts" classical experimental design—traditionally used for simple linear models—into the realm of complex, general-purpose function approximation like deep learning.

Datasets and Results

The authors evaluated their approach on three large-scale datasets:

  • oneshotwiki-311 & oneshotwiki-14031: Named-entity recognition tasks converted into bandit problems, with up to 14,031 actions.
  • amazon-3m: An extreme multi-label dataset involving text phrases and item tags, serving as a massive benchmark with 2.8 million possible actions.
  • Synthetic Redundancy: A modified version of the wiki dataset where actions were duplicated to test algorithm efficiency against redundant choices.

Superior Performance: On the oneshotwiki-14031 dataset, SpannerIGW achieved significantly higher rewards than standard baselines like $\epsilon$-Greedy and SquareCB, especially when paired with deep learning models.

Reward comparison of algorithms using Bilinear and Deep regression functions.

Scalability and Efficiency: In the amazon-3m experiment, the spanner-based approach outperformed state-of-the-art tree-based bandit methods by a factor of 2 in terms of reward. Furthermore, while SpannerIGW is more complex than a simple greedy search, its inference time remains highly practical. On a commodity CPU, it took roughly 25ms per example—fast enough for many real-time applications.

Limitations and Future Work

  • Linear Action Structure: The algorithm assumes that the reward is linear with respect to the action features $\phi(x, a)$. While $\phi$ can be complex, the final "layer" must be a dot product. Extending this to fully non-linear action dependencies remains an open challenge.
  • Initialization: The "ReweightedSpanner" requires an initial set of actions with a non-zero determinant to start. While the authors provide ways to find this, it adds a layer of pre-processing.
  • Reinforcement Learning: The authors suggest that these computational tools (the spanners and oracles) could eventually be extended to full Reinforcement Learning (RL) problems with large action spaces, moving beyond the "one-shot" bandit setting.

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