# The Typical Behavior of Bandit Algorithms

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 15 references that are in the map.
- First posted on arXiv 11 Oct 2022.

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

- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021)

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

- [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025)
- [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)
- [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)
- [Efficient Inference after Directionally Stable Adaptive Experiments](https://mlsanity.com/paper/2602.21478/) (2026)
- [Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards](https://mlsanity.com/paper/2604.14876/) (2026)
- [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)
- [Uncertainty-Aware Selection of Online Algorithms with Simulator Ensembles](https://mlsanity.com/paper/2609.32170/) (2026)
- [Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime](https://mlsanity.com/paper/2610.06213/) (2026)

## Abstract (arXiv)

We establish strong laws of large numbers and central limit theorems for the regret of two of the most popular bandit algorithms: Thompson sampling and UCB. Here, our characterizations of the regret distribution complement the characterizations of the tail of the regret distribution recently developed by Fan and Glynn (2021) (arXiv:2109.13595). The tail characterizations there are associated with atypical bandit behavior on trajectories where the optimal arm mean is under-estimated, leading to mis-identification of the optimal arm and large regret. In contrast, our SLLN's and CLT's here describe the typical behavior and fluctuation of regret on trajectories where the optimal arm mean is properly estimated. We find that Thompson sampling and UCB satisfy the same SLLN and CLT, with the asymptotics of both the SLLN and the (mean) centering sequence in the CLT matching the asymptotics of expected regret. Both the mean and variance in the CLT grow at log(T) rates with the time horizon T. Asymptotically as T → ∞, the variability in the number of plays of each sub-optimal arm depends only on the rewards received for that arm, which indicates that each sub-optimal arm contributes independently to the overall CLT variance.