Efficient Exploration in Massive Action Spaces

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2351 papers383 conceptsfrozen 2026-10-04

In the classic multi-armed bandit (MAB) problem, an agent chooses between a handful of options—perhaps a few different headlines for a website—and learns which one performs best through trial and error. However, modern applications like search advertising, recommendation engines, and drug discovery operate on a different scale. In these "extreme" scenarios, the number of possible actions (arms) can reach millions or even become infinite.

Standard bandit algorithms like Upper Confidence Bound (UCB) or Thompson Sampling typically exhibit computational and sample complexity that scales linearly with the number of available actions $A$. As noted by Alexander Rakhlin, Dean Foster, and their colleagues in Top-k eXtreme Contextual Bandits with Arm Hierarchy, this linear dependency creates a "computational bottleneck" that makes real-time deployment impossible when the catalog size is massive.

The research direction emerging from these papers focuses on decoupling the cost of learning from the total number of actions, shifting the dependency toward the underlying complexity of the reward function or the dimensionality of the context.

The Linear Bottleneck and Why It Fails

The core problem is that traditional agents must "touch" or score every arm to make a decision. Jianxun Lian and Yu Li point out in Show Me the Whole World that this linear scoring requirement traps users in "filter bubbles" because the system cannot afford to explore the entire item space.

Furthermore, in high-dimensional settings, H. Brendan McMahan and Matthew J. Streeter argue in Tighter Bounds for Multi-Armed Bandits with Expert Advice that traditional regret bounds become practically useless. If your regret scales with $A$, and $A$ is one million, the theoretical guarantees provide no guidance for real-world performance.

Strategy 1: Hierarchical Navigation

One way to bypass the linear scan is to organize the action space into a tree. Instead of picking one of $A$ items, the agent makes a series of $O(\log A)$ decisions to navigate from the root of a hierarchy to a specific leaf.

Rakhlin and Foster demonstrate that this hierarchical approach can achieve a 100x speedup in inference time. Similarly, Lian and Li use tree-based structures to reduce exploration complexity from linear to logarithmic, allowing recommendation systems to explore the "entire item space" efficiently.

Strategy 2: Optimization Oracles and Soft Elimination

Rather than explicitly maintaining a list of viable actions, researchers are moving toward using optimization oracles. In this paradigm, the selection of the "best" action is treated as a mathematical optimization problem over a continuous or structured space.

In Contextual Bandits with Large Action Spaces: Made Practical, Yinglun Zhu, John Langford, and Paul Mineiro introduce SpannerIGW. This algorithm uses "optimal design" theory to select a small, representative subset of actions (a spanner) that allows the agent to infer the rewards of all other actions. This decouples the computational cost from the total number of actions entirely.

A related concept is Soft Elimination, introduced by Osama A. Hanna and Christina Fragouli in SoftBatch. Instead of strictly discarding arms (which is impossible in infinite spaces), they "shape" the action set, focusing the search on promising regions without exhaustively scanning every option.

Strategy 3: Redefining "Winning" via Quantiles

In massive spaces, finding the absolute best arm is often a fool's errand. Arghya Roy Chaudhuri suggests in PAC Identification of a Bandit Arm Relative to a Reward Quantile that we should instead aim to find an arm that is "good enough"—specifically, one that falls within a certain top quantile of the reward distribution.

Wenbo Ren and Ness Shroff expand on this with Quantile Exploration (QE) in Exploring k out of Top ρ Fraction of Arms. By shifting the goal from rank to quantile, they slash sample complexity, removing the dependence on the total number of arms and making exploration feasible even for infinite sets.

Strategy 4: Leveraging Latent Structure

Finally, many researchers achieve scalability by assuming the rewards follow a structure that can be learned.

  • Linearity: Branislav Kveton and Zheng Wen show in Efficient Learning in Large-Scale Combinatorial Semi-Bandits that if rewards are linear functions of features, regret can be independent of the number of items.
  • Side Information: Mengxiao Zhang and Haipeng Luo use feedback graphs in SquareCB.UG to let the agent learn about multiple actions from a single observation, making the regret depend on the graph's complexity rather than the action count.
  • Causality: Qing Zhou uses causal relationships in BA-UCB to infer the outcomes of multiple interventions simultaneously, bypassing the need to test every arm independently.

Summary

The transition from small-scale to massive-scale bandits requires moving away from "arm-counting." Whether through hierarchical trees, optimization oracles, or quantile-based objectives, the goal is the same: to create agents that are smart enough to understand the space of possibilities without having to visit every corner of it.

Papers in this version

Showing 60 of 351 papers.

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 1, frozen text):

@misc{lacuna_efficient_exploration_in_massive_action__69157d62_v1,
  title = {Efficient Exploration in Massive Action Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-exploration-in-massive-action-spaces/rdr_69157d6238e44539a5df1434749a8c2a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}