mlsanityData to 7 Oct 2026

A minimax and asymptotically optimal algorithm for stochastic bandits

arXiv 1702.07211 ↗First posted 23 Feb 2017stat.ML cs.LG math.STcited by 27

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 8; 2024: 6; 2025: 2; 2026: 4.

27 papers.

Sort:

  1. 2022Top Two Algorithms Revisitedcited by 34
  2. 2022Langevin Monte Carlo for Contextual Banditscited by 22
  3. 2024UCB algorithms for multi-armed bandits: Precise regret and adaptive inferencecited by 16
  4. 2021Maillard Sampling: Boltzmann Exploration Done Optimallycited by 13
  5. 2022Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Banditscited by 11
  6. 2023Optimal Batched Best Arm Identificationcited by 8
  7. 2023An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Banditscited by 8
  8. 2023VITS : Variational Inference Thompson Sampling for contextual banditscited by 5
  9. 2024Best Arm Identification with Minimal Regretcited by 5
  10. 2023Optimality of Thompson Sampling with Noninformative Priors for Pareto Banditscited by 3
  11. 2023Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewardscited by 2
  12. 2026Bandit Allocational Instabilitycited by 2
15 more
  1. 2021Tuning Confidence Bound for Stochastic Bandits with Bandit Distancecited by 1
  2. 2023Discovering Multiple Algorithm Configurationscited by 1
  3. 2023Simple Modification of the Upper Confidence Bound Algorithm by Generalized Weighted Averagescited by 1
  4. 2024Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstentioncited by 1
  5. 2024On Lai's Upper Confidence Bound in Multi-Armed Banditscited by 1
  6. 2025Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Samplingcited by 1
  7. 2021Learning to maximize global influence from local observationscited by 0
  8. 2022Truncated LinUCB for Stochastic Linear Banditscited by 0
  9. 2023Generalized Regret Analysis of Thompson Sampling using Fractional Posteriorscited by 0
  10. 2024HELLINGER-UCB: A novel algorithm for stochastic multi-armed bandit problem and cold start problem in recommender systemcited by 0
  11. 2024Efficient and Adaptive Posterior Sampling Algorithms for Banditscited by 0
  12. 2025Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Banditscited by 0
  13. 2026Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floorscited by 0
  14. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0
  15. 2026Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stoppingcited by 0