# Optimally Confident UCB: Improved Regret for Finite-Armed Bandits

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jul 2015.

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

- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [Adaptive Sampling for Discovery](https://mlsanity.com/paper/2205.14829/) (2022)
- [Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.06247/) (2025)

## Abstract (arXiv)

I present the first algorithm for stochastic finite-armed bandits that simultaneously enjoys order-optimal problem-dependent regret and worst-case regret. Besides the theoretical results, the new algorithm is simple, efficient and empirically superb. The approach is based on UCB, but with a carefully chosen confidence parameter that optimally balances the risk of failing confidence intervals against the cost of excessive optimism.