# On Lai's Upper Confidence Bound in Multi-Armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 48 references that are in the map.
- First posted on arXiv 3 Oct 2024.

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

- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018)
- [On Bayesian index policies for sequential resource allocation](https://mlsanity.com/paper/1601.01190/) (2016)
- [A Note on KL-UCB+ Policy for the Stochastic Bandit](https://mlsanity.com/paper/1903.07839/) (2019)

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

- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)

## Abstract (arXiv)

In this memorial paper, we honor Tze Leung Lai's seminal contributions to the topic of multi-armed bandits, with a specific focus on his pioneering work on the upper confidence bound. We establish sharp non-asymptotic regret bounds for an upper confidence bound index with a constant level of exploration for Gaussian rewards. Furthermore, we establish a non-asymptotic regret bound for the upper confidence bound index of Lai (1987) which employs an exploration function that decreases with the sample size of the corresponding arm. The regret bounds have leading constants that match the Lai-Robbins lower bound. Our results highlight an aspect of Lai's seminal works that deserves more attention in the machine learning literature.