# Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 11 references that are in the map.
- First posted on arXiv 20 Dec 2025.

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

- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards](https://mlsanity.com/paper/2506.16658/) (2025)
- [Breaking the √T Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2205.09899/) (2022)
- [Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits](https://mlsanity.com/paper/2406.05710/) (2024)
- [No-Regret Linear Bandits under Gap-Adjusted Misspecification](https://mlsanity.com/paper/2501.05361/) (2025)

## Abstract (arXiv)

Several optimism-based stochastic bandit algorithms -- including UCB, UCB-V, linear UCB, and finite-arm GP-UCB -- achieve logarithmic regret using proofs that, despite superficial differences, follow essentially the same structure. This note isolates the minimal ingredients behind these analyses: a single high-probability concentration condition on the estimators, after which logarithmic regret follows from two short deterministic lemmas describing radius collapse and optimism-forced deviations. The framework yields unified, near-minimal proofs for these classical algorithms and extends naturally to many contemporary bandit variants.