# KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2018.

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

- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses](https://mlsanity.com/paper/2205.07704/) (2022)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees](https://mlsanity.com/paper/2209.14414/) (2022)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits](https://mlsanity.com/paper/2210.00895/) (2022)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms](https://mlsanity.com/paper/2304.03056/) (2023)
- [Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards](https://mlsanity.com/paper/2304.14989/) (2023)
- [Query-Reward Tradeoffs in Multi-Armed Bandits](https://mlsanity.com/paper/2110.05724/) (2021)
- [HELLINGER-UCB: A novel algorithm for stochastic multi-armed bandit problem and cold start problem in recommender system](https://mlsanity.com/paper/2404.10207/) (2024)
- [On Lai's Upper Confidence Bound in Multi-Armed Bandits](https://mlsanity.com/paper/2410.02279/) (2024)
- [Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics](https://mlsanity.com/paper/2202.05799/) (2022)
- [Little Exploration is All You Need](https://mlsanity.com/paper/2310.17538/) (2023)
- [Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization](https://mlsanity.com/paper/2407.05704/) (2024)
- [Sharper Perturbed-Kullback-Leibler Exponential Tail Bounds for Beta and Dirichlet Distributions](https://mlsanity.com/paper/2508.07991/) (2025)
- [Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping](https://mlsanity.com/paper/2609.22690/) (2026)

## Abstract (arXiv)

We consider K-armed stochastic bandits and consider cumulative regret bounds up to time T. We are interested in strategies achieving simultaneously a distribution-free regret bound of optimal order √KT and a distribution-dependent regret that is asymptotically optimal, that is, matching the kappaln T lower bound by Lai and Robbins (1985) and Burnetas and Katehakis (1996), where kappa is the optimal problem-dependent constant. This constant kappa depends on the model D considered (the family of possible distributions over the arms). M'enard and Garivier (2017) provided strategies achieving such a bi-optimality in the parametric case of models given by one-dimensional exponential families, while Lattimore (2016, 2018) did so for the family of (sub)Gaussian distributions with variance less than 1. We extend this result to the non-parametric case of all distributions over [0,1]. We do so by combining the MOSS strategy by Audibert and Bubeck (2009), which enjoys a distribution-free regret bound of optimal order √KT, and the KL-UCB strategy by Capp'e et al. (2013), for which we provide in passing the first analysis of an optimal distribution-dependent kappaln T regret bound in the model of all distributions over [0,1]. We were able to obtain this non-parametric bi-optimality result while working hard to streamline the proofs (of previously known regret bounds and thus of the new analyses carried out); a second merit of the present contribution is therefore to provide a review of proofs of classical regret bounds for index-based strategies for K-armed stochastic bandits.