# A minimax and asymptotically optimal algorithm for stochastic bandits

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2017.

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

- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits](https://mlsanity.com/paper/2311.05794/) (2023)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [VITS : Variational Inference Thompson Sampling for contextual bandits](https://mlsanity.com/paper/2307.10167/) (2023)
- [Best Arm Identification with Minimal Regret](https://mlsanity.com/paper/2409.18909/) (2024)
- [Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits](https://mlsanity.com/paper/2302.01544/) (2023)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards](https://mlsanity.com/paper/2304.14989/) (2023)
- [Tuning Confidence Bound for Stochastic Bandits with Bandit Distance](https://mlsanity.com/paper/2110.02690/) (2021)
- [Truncated LinUCB for Stochastic Linear Bandits](https://mlsanity.com/paper/2202.11735/) (2022)
- [Discovering Multiple Algorithm Configurations](https://mlsanity.com/paper/2303.07434/) (2023)
- [Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averages](https://mlsanity.com/paper/2308.14350/) (2023)
- [Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention](https://mlsanity.com/paper/2402.15127/) (2024)
- [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)
- [Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling](https://mlsanity.com/paper/2502.14379/) (2025)
- [Learning to maximize global influence from local observations](https://mlsanity.com/paper/2109.11909/) (2021)
- [Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors](https://mlsanity.com/paper/2309.06349/) (2023)
- [Efficient and Adaptive Posterior Sampling Algorithms for Bandits](https://mlsanity.com/paper/2405.01010/) (2024)
- [Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.06247/) (2025)
- [Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors](https://mlsanity.com/paper/2607.22935/) (2026)
- [Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set](https://mlsanity.com/paper/2607.23679/) (2026)
- [Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping](https://mlsanity.com/paper/2609.22690/) (2026)

## Abstract (arXiv)

We propose the kl-UCB ++ algorithm for regret minimization in stochastic bandit models with exponential families of distributions. We prove that it is simultaneously asymptotically optimal (in the sense of Lai and Robbins' lower bound) and minimax optimal. This is the first algorithm proved to enjoy these two properties at the same time. This work thus merges two different lines of research with simple and clear proofs.