# Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 26 references that are in the map.
- First posted on arXiv 18 Aug 2026.

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

- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [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)
- [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)
- [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025)
- [Thompson sampling: Precise arm-pull dynamics and adaptive inference](https://mlsanity.com/paper/2601.21131/) (2026)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [On Instability of Minimax Optimal Optimism-Based Bandit Algorithms](https://mlsanity.com/paper/2511.18750/) (2025)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [A characterization of sample adaptivity in UCB data](https://mlsanity.com/paper/2503.04855/) (2025)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem](https://mlsanity.com/paper/2603.10184/) (2026)

## Abstract (arXiv)

Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs. We study the trade-off between worst-case regret RK,T and instability mathcal SK,T, defined as the largest standard deviation of a terminal pull count, for K arms and T rounds. We prove the finite-time lower bound mathcal RK,Tmathcal SK,T≥ C T3/2, where C is independent of K and T, under a finite-time regret condition and without the regularity assumptions imposed in the prior asymptotic analysis. We also introduce Stabilized Lower-Envelope UCB (textuptextscSLE-UCB), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. textuptextscSLE-UCB satisfies mathcal RK,Tmathcal SK,T=O(T3/2log K), with an implicit constant independent of K and T, matching the lower bound exactly in T and within a logarithmic factor in K. To prove the instability bound, we develop a new offline top-prefix representation that removes path dependence from online decisions. Together with single-reward perturbations and the Efron--Stein inequality, this representation controls pull-count variance. Thus, regret and instability depend reciprocally on K, while their product has no polynomial dependence on K. These results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier.