# A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms arXiv: https://arxiv.org/abs/2106.02126 · HTML: https://mlsanity.com/paper/2106.02126/ ## Key facts - Cited by 30 papers in the map (data through 14 Oct 2026). - Builds on 14 of its 46 references that are in the map. - First posted on arXiv 3 Jun 2021. ## Builds on (most cited first, 14 of 14) - [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019) - [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014) - [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015) - [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019) - [Inference for Batched Bandits](https://mlsanity.com/paper/2002.03217/) (2020) - [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016) - [Accurate Inference for Adaptive Linear Models](https://mlsanity.com/paper/1712.06695/) (2017) - [On the bias, risk and consistency of sample means in multi-armed bandits](https://mlsanity.com/paper/1902.00746/) (2019) - [Are sample means in multi-armed bandits positively or negatively biased?](https://mlsanity.com/paper/1905.11397/) (2019) - [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021) - [On conditional versus marginal bias in multi-armed bandits](https://mlsanity.com/paper/2002.08422/) (2020) - [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021) - [Diffusion Approximations for a Class of Sequential Testing Problems](https://mlsanity.com/paper/2102.07030/) (2021) - [Asymptotic Convergence of Thompson Sampling](https://mlsanity.com/paper/2011.03917/) (2020) ## Built on by (most cited first, 30 of 30) - [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) - [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) - [Risk and optimal policies in bandit experiments](https://mlsanity.com/paper/2112.06363/) (2021) - [reBandit: Random Effects based Online RL algorithm for Reducing Cannabis Use](https://mlsanity.com/paper/2402.17739/) (2024) - [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) - [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023) - [Oralytics Reinforcement Learning Algorithm](https://mlsanity.com/paper/2406.13127/) (2024) - [MiWaves Reinforcement Learning Algorithm](https://mlsanity.com/paper/2408.15076/) (2024) - [A characterization of sample adaptivity in UCB data](https://mlsanity.com/paper/2503.04855/) (2025) - [Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability](https://mlsanity.com/paper/2512.20368/) (2025) - [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026) - [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022) - [Risk Preferences of Learning Algorithms](https://mlsanity.com/paper/2205.04619/) (2022) - [Efficient Inference after Directionally Stable Adaptive Experiments](https://mlsanity.com/paper/2602.21478/) (2026) - [Design Experiments to Compare Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2603.05919/) (2026) - [Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards](https://mlsanity.com/paper/2604.14876/) (2026) - [Complexity Analysis of a Countable-armed Bandit Problem](https://mlsanity.com/paper/2301.07243/) (2023) - [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023) - [Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors](https://mlsanity.com/paper/2309.06349/) (2023) - [Zero-Inflated Bandits](https://mlsanity.com/paper/2312.15595/) (2023) - [Reciprocal Learning](https://mlsanity.com/paper/2408.06257/) (2024) - [Conformal bandits: bringing statistical validity and reward efficiency under weak arm separability](https://mlsanity.com/paper/2512.09850/) (2025) - [MINTS: Minimalist Thompson Sampling](https://mlsanity.com/paper/2606.01655/) (2026) - [Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits](https://mlsanity.com/paper/2608.17841/) (2026) - [Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime](https://mlsanity.com/paper/2610.06213/) (2026) ## Abstract (arXiv) One of the key drivers of complexity in the classical (stochastic) multi-armed bandit (MAB) problem is the difference between mean rewards in the top two arms, also known as the instance gap. The celebrated Upper Confidence Bound (UCB) policy is among the simplest optimism-based MAB algorithms that naturally adapts to this gap: for a horizon of play n, it achieves optimal O(log n) regret in instances with "large" gaps, and a near-optimal O(√n log n) minimax regret when the gap can be arbitrarily "small." This paper provides new results on the arm-sampling behavior of UCB, leading to several important insights. Among these, it is shown that arm-sampling rates under UCB are asymptotically deterministic, regardless of the problem complexity. This discovery facilitates new sharp asymptotics and a novel alternative proof for the O(√n log n) minimax regret of UCB. Furthermore, the paper also provides the first complete process-level characterization of the MAB problem under UCB in the conventional diffusion scaling. Among other things, the "small" gap worst-case lens adopted in this paper also reveals profound distinctions between the behavior of UCB and Thompson Sampling, such as an "incomplete learning" phenomenon characteristic of the latter.