Scaling Bandit Guarantees Beyond Two Arms

20 concepts11 papers1 proposal

In the theoretical study of multi-armed bandits (MAB) and online decision-making, there is a hidden boundary that completely changes the nature of the problem: the transition from two options to three or more.

When an algorithm only has to choose between two alternatives (a classic A/B test), the mathematical landscape is remarkably well-behaved. Every sample from Arm A implicitly provides information about its performance relative to Arm B. The uncertainty is one-dimensional, captured by a single reward gap $\Delta$.

However, when we scale to multi-arm environments ($K > 2$), this clean geometry shatters. Recent research reveals that many fundamental guarantees—ranging from the optimality of uniform sampling to the very possibility of achieving universal instance-dependent regret bounds—are strictly limited to the two-armed case. Understanding why these guarantees break down exposes a deep Pareto frontier in multi-scale online learning.

The Two-Arm Illusion

In traditional industry A/B testing, uniform sampling (allocating equal traffic to both variations) is standard practice. In On the Complexity of A/B Testing, Emilie Kaufmann et al. demonstrate that uniform sampling is mathematically optimal for identifying the best arm under very specific, symmetric conditions (such as Gaussian outcomes with equal variances). This idea is extended by Po-An Wang et al. in On Universally Optimal Algorithms for A/B Testing, confirming that proofs of universal optimality for uniform sampling are fundamentally constrained to two-armed scenarios.

The moment a third arm is introduced, uniform sampling becomes highly inefficient. To find the single best option, an algorithm must dynamically allocate more samples to competitive arms and quickly discard clear losers. Yet, designing these adaptive strategies introduces severe process-level complexities that do not exist in binary choices.

Structural Friction in Multi-Arm Spaces

Why does adding more arms break our mathematical tools? The friction manifests across several dimensions:

1. Elimination Complexity in Batched Settings

In many real-world applications, feedback is delayed or collected in batches rather than sequentially. In Batched Bandit Problems, Vianney Perchet et al. show that while batched policies can be cleanly optimized for two arms, scaling them to many arms drastically increases the complexity of the statistical elimination tests required to maintain efficiency. Similarly, Cem Kalkanli et al. note in Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits that while adaptive batching schemes like iPASE preserve optimal regret, proving these feedback-efficiency bounds for an arbitrary number of arms remains an open theoretical challenge.

2. Unpredictable Sampling Paths

In a two-armed setting, the sampling paths of standard algorithms are relatively predictable. However, when scaled up, the choice of algorithm dictates severe behavioral differences. In A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms, Anand Kalvit et al. prove that in worst-case scenarios where arm rewards are nearly identical, the Upper Confidence Bound (UCB) algorithm maintains stable, deterministic sampling rates. Conversely, Thompson Sampling can suffer from "incomplete learning," resulting in highly imbalanced data collection across multiple arms that compromises post-experiment statistical inference.

3. Action-Switching Penalties

When an agent incurs a penalty for changing its choice from one round to the next, moving beyond two actions introduces a structural gap. As shown by Idan Amir et al. in Better Best of Both Worlds Bounds for Bandits with Switching Costs, theoretical regret bounds lose their tightness when moving from two actions to a multi-action setting, leaving a discrepancy between upper and lower limits that obscures the true fundamental limits of learning with switching costs.

The Multi-Scale Impossibility and Pareto Frontiers

The most profound divergence between two-armed and multi-armed environments lies in the concept of instance-dependent regret.

In a two-armed bandit, there is only one sub-optimality gap ($\Delta$). An algorithm can easily adapt to this single scale. In a multi-armed bandit, however, there is an entire spectrum of gaps: some arms are catastrophically worse than the optimum, while others are nearly indistinguishable from it.

This variance introduces a fundamental impossibility. In The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication, Allen Liu et al. map out this phenomenon in decentralized environments. The authors prove that achieving universally optimal instance-dependent regret across all possible reward gap scales simultaneously is mathematically impossible.

Instead, algorithms face a strict Pareto frontier:

$$\text{Optimizing for a specific reward gap size } \Delta_1 \implies \text{Forcing sub-optimal performance for another gap size } \Delta_2$$

This trade-off means that an algorithm tuned to rapidly identify and exploit large differences between options will inherently fail to optimize its regret when faced with subtle, fine-grained differences among a large pool of choices.

Regret for Gap Scale B
       ^
       |  * (Algorithm tuned for Scale A)
       |   \
       |    \  Pareto Frontier (Universal Optimality Impossibility)
       |     \
       |      * (Algorithm tuned for Scale B)
       +----------------------------------------> Regret for Gap Scale A

This multi-scale bottleneck is not unique to decentralized settings. In Online Auctions and Multi-scale Online Learning, Sebastien Bubeck et al. explore environments with limited bandit feedback. They find that while it is possible to protect the regret of the single best action, attempting to force the regret to scale locally for every possible action simultaneously results in a much weaker overall convergence guarantee. Fine-grained local optimization across an entire action set inherently dilutes global efficiency.

The Open Frontier

Because the multi-arm setting introduces these fundamental geometric and statistical hurdles, many advanced branches of bandit theory remain anchored to the two-armed case.

Whether exploring risk-aware frameworks like the privacy-protected mean-volatility utility proposed by Shanshan Zhao et al. in Responsible Bandit Learning via Privacy-Protected Mean-Volatility Utility, non-stationary environments analyzed by Andres Munoz medina et al. in Online Learning for Non-Stationary A/B Tests, or fixed-budget best-arm identification for multiple top options studied by Emilie Kaufmann et al. in On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models, the core challenge remains identical.

Recognizing that universal optimality is an illusion in high-dimensional action spaces shifts the goal of algorithm design. Instead of searching for a single "perfect" multi-armed bandit strategy, the objective becomes navigating the inherent Pareto frontiers of scale, budget, and instance-dependent complexity.

Key Foundational Work

Batched Bandit Problems (2015) — contributed 1 concept elements to this direction.
On the Complexity of A/B Testing (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_instance_dependent_regret_trade_offs_add8b6a3,
  title = {instance-dependent regret trade-offs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/instance-dependent-regret-trade-offs/rdr_add8b6a3c5bd418c842e67e9bd41fc4b},
  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_instance_dependent_regret_trade_offs_add8b6a3_v1,
  title = {instance-dependent regret trade-offs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/instance-dependent-regret-trade-offs/rdr_add8b6a3c5bd418c842e67e9bd41fc4b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake