# The Fragility of Optimized Bandit Algorithms

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 28 Sep 2021.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits](https://mlsanity.com/paper/1401.1123/) (2014)
- [Optimal Thompson Sampling strategies for support-aware CVaR bandits](https://mlsanity.com/paper/2012.05754/) (2020)
- [Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure](https://mlsanity.com/paper/1604.05257/) (2016)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021)
- [Generalized Risk-Aversion in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1405.0833/) (2014)

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

- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [Gaussian Imagination in Bandit Learning](https://mlsanity.com/paper/2201.01902/) (2022)
- [A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits](https://mlsanity.com/paper/2206.02969/) (2022)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [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)
- [Tail Distribution of Regret in Optimistic Reinforcement Learning](https://mlsanity.com/paper/2511.18247/) (2025)
- [Design Experiments to Compare Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2603.05919/) (2026)
- [How Log-Barrier Helps Exploration in Policy Optimization](https://mlsanity.com/paper/2603.15001/) (2026)
- [Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards](https://mlsanity.com/paper/2604.14876/) (2026)
- [Learning Optimal Distributionally Robust Stochastic Control in Continuous State Spaces](https://mlsanity.com/paper/2406.11281/) (2024)
- [UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity](https://mlsanity.com/paper/2511.22273/) (2025)
- [MINTS: Minimalist Thompson Sampling](https://mlsanity.com/paper/2606.01655/) (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)
- [A stochastic subgradient method with optimal failure exponent](https://mlsanity.com/paper/2609.37425/) (2026)
- [Reliable Scale-Free Bandits via Empirical Likelihood](https://mlsanity.com/paper/2610.18055/) (2026)

## Abstract (arXiv)

Much of the literature on optimal design of bandit algorithms is based on minimization of expected regret. It is well known that designs that are optimal over certain exponential families can achieve expected regret that grows logarithmically in the number of arm plays, at a rate governed by the Lai-Robbins lower bound. In this paper, we show that when one uses such optimized designs, the regret distribution of the associated algorithms necessarily has a very heavy tail, specifically, that of a truncated Cauchy distribution. Furthermore, for p>1, the p'th moment of the regret distribution grows much faster than poly-logarithmically, in particular as a power of the total number of arm plays. We show that optimized UCB bandit designs are also fragile in an additional sense, namely when the problem is even slightly mis-specified, the regret can grow much faster than the conventional theory suggests. Our arguments are based on standard change-of-measure ideas, and indicate that the most likely way that regret becomes larger than expected is when the optimal arm returns below-average rewards in the first few arm plays, thereby causing the algorithm to believe that the arm is sub-optimal. To alleviate the fragility issues exposed, we show that UCB algorithms can be modified so as to ensure a desired degree of robustness to mis-specification. In doing so, we also show a sharp trade-off between the amount of UCB exploration and the heaviness of the resulting regret distribution tail.