# Bandit Allocational Instability

arXiv: https://arxiv.org/abs/2602.07472 · HTML: https://mlsanity.com/paper/2602.07472/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 7 Feb 2026.

## Builds on (most cited first, 20 of 20)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [The Typical Behavior of Bandit Algorithms](https://mlsanity.com/paper/2210.05660/) (2022)
- [Inference with the Upper Confidence Bound Algorithm](https://mlsanity.com/paper/2408.04595/) (2024)
- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025)
- [Optimally Confident UCB: Improved Regret for Finite-Armed Bandits](https://mlsanity.com/paper/1507.07880/) (2015)
- [Thompson sampling: Precise arm-pull dynamics and adaptive inference](https://mlsanity.com/paper/2601.21131/) (2026)
- [On Instability of Minimax Optimal Optimism-Based Bandit Algorithms](https://mlsanity.com/paper/2511.18750/) (2025)
- [The Economics of No-regret Learning Algorithms](https://mlsanity.com/paper/2601.22079/) (2026)
- [A characterization of sample adaptivity in UCB data](https://mlsanity.com/paper/2503.04855/) (2025)

## Built on by (most cited first, 3 of 3)

- [Design Experiments to Compare Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2603.05919/) (2026)
- [Sharp Characterization of Bias in Post-Bandit Inference](https://mlsanity.com/paper/2608.01069/) (2026)
- [Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits](https://mlsanity.com/paper/2608.17841/) (2026)

## Abstract (arXiv)

When multi-armed bandit (MAB) algorithms allocate pulls among competing arms, the resulting allocation can exhibit huge variation. This is particularly harmful in modern applications such as learning-enhanced platform operations and post-bandit statistical inference. Thus motivated, we introduce a new performance metric of MAB algorithms termed allocation variability, which is the largest (over arms) standard deviation of an arm's number of pulls. We establish a fundamental trade-off between allocation variability and regret, the canonical performance metric of reward maximization. In particular, for any algorithm, the worst-case regret RT and worst-case allocation variability ST must satisfy RT · ST=Omega(T^frac32) as Trightarrow∞, as long as RT=o(T). This indicates that any minimax regret-optimal algorithm must incur worst-case allocation variability Theta(T), the largest possible scale; while any algorithm with sublinear worst-case regret must necessarily incur ST= ω(√T). We further show that this lower bound is essentially tight, and that any point on the Pareto frontier RT · ST=tildeTheta(T3/2) can be achieved by a simple tunable algorithm UCB-f, a generalization of the classic UCB1. Finally, we discuss implications for platform operations and for statistical inference, when bandit algorithms are used. As a byproduct of our result, we resolve an open question of Praharaj and Khamaru (2025).