Scaling Bandit Learning to Large Action Spaces

555 concepts390 papers2 proposals

In standard multi-armed and contextual bandit frameworks, algorithms operate under a fundamental assumption: the decision-maker can iterate through, evaluate, and choose from a discrete, manageable set of $K$ actions. This assumption underpins classic exploration strategies like Upper Confidence Bound (UCB) or Thompson Sampling.

However, modern real-world applications break this assumption entirely. A recommendation engine handles millions of products; an ad-placement system selects from vast catalogs; a language model chooses from tens of thousands of tokens at each step. When the action space scales to infinity or millions of candidates, traditional algorithms hit a double wall:

  1. Statistical Bottleneck: If actions are treated as independent, the algorithm must try every action at least once to determine its quality, causing cumulative regret to scale linearly or quadratically with the number of actions.
  2. Computational Bottleneck: Evaluating the expected reward or uncertainty boundary for every single candidate at every decision step requires $O(K)$ time, making real-time inference impossible.

To scale bandit learning to massive action spaces, a major research direction focuses on decoupling both sample complexity and computational complexity from the raw number of actions. The core insight is to stop treating actions as isolated choices and instead exploit the underlying structure—geometric, topological, or hierarchical—that links them together.

Exploiting Shared Feature Spaces and Graphs

The most direct way to bypass the action-capacity bottleneck is to map actions into a lower-dimensional space where learning about one action automatically yields information about its neighbors. If two actions share similar features, their rewards should be highly correlated.

Kveton et al. leverage this intuition in Large-Scale Optimistic Adaptive Submodularity. Instead of tracking the reward of every item independently, they model item states using a Generalized Linear Model (GLM) based on low-dimensional item features. By doing so, the algorithm's regret scales with the number of features ($d$) rather than the number of items ($K$), making it highly effective for massive search spaces like movie catalogs.

When explicit features are unavailable but relationships between actions are known, graph structures can serve a similar purpose. In Spectral Bandits for Smooth Graph Functions, Valko et al. analyze scenarios where rewards vary smoothly across a graph of actions. By utilizing the spectral properties of the graph Laplacian, they show that the algorithm can operate within a small "effective dimension" of the graph. This mathematical compression ensures that accurate recommendations can be made across thousands of nodes after only a handful of total interactions, completely neutralizing the linear action-scaling penalty.

Decoupling Inference from Action Count via Oracles

Even if an algorithm achieves statistical efficiency through features, it may still suffer from a computational bottleneck if it must evaluate a linear model for all $K$ actions at every step. To achieve true scalability, the per-step runtime must also be sublinear or independent of $K$.

One powerful approach is to offload the exhaustive search to an optimization oracle. Zhu et al. demonstrate this in Contextual Bandits with Large Action Spaces: Made Practical. They introduce an algorithm, SpannerIGW, which combines optimal design theory with inverse gap weighting. By querying a base optimization oracle to identify a small, representative subset of actions (a spanner), they decouple the computational overhead from the total action count. This allows the framework to accommodate highly flexible deep learning models even when dealing with continuous or massive action spaces.

Similarly, instead of explicitly maintaining and filtering a massive list of viable candidates, Hanna et al. propose a "soft elimination" strategy in Efficient Batched Algorithm for Contextual Linear Bandits with Large Action Space via Soft Elimination. Rather than exhaustively scanning and dropping individual actions, their algorithm shapes the viable action set implicitly through a linear optimization oracle. This approach achieves near-optimal regret with minimal policy updates, bypassing the need to store or iterate through the entire action space.

Another strategy for scaling to massive action spaces is to structure the action space so that the algorithm can navigate it like a map or a tree, eliminating the need to look at every option.

If the reward landscape possesses a natural geometric structure, such as being unimodal (having a single peak), the algorithm can find the optimal choice purely by exploring local gradients. Proutiere et al. prove in Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms that under a unimodal structure, the cumulative regret can become completely independent of the total number of arms. The algorithm simply climbs the reward peak, rendering the size of the surrounding action space irrelevant.

When the action space lacks a natural topological landscape, researchers can impose an artificial one. The authors of Top-k eXtreme Contextual Bandits with Arm Hierarchy address the "extreme" bandit setting by organizing millions of potential arms into a hierarchical tree structure. Instead of performing a flat scan of $O(K)$ items, the algorithm makes a sequence of routing decisions down the tree. This structural modification collapses the per-step inference cost from $O(K)$ to $O(\log K)$, providing the massive computational speedups required for real-time deployment in production environments.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 417 papers
  2. Version 1 · 2026-10-04 · 351 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_action_space_scalability_69157d62,
  title = {action space scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/action-space-scalability/rdr_69157d6238e44539a5df1434749a8c2a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_action_space_scalability_69157d62_v2,
  title = {action space scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/action-space-scalability/rdr_69157d6238e44539a5df1434749a8c2a/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake