The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

Aurélien Garivier · Olivier Cappé

363 citations0/0 files storedarXiv (Cornell University)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Optimization and Search Problems

Abstract

This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satisfies a uniformly better regret bound than UCB or UCB2; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specific classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, UCB2, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 363 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem 1979Bandit Processes and Dynamic Allocation Indices 2009Exploration–exploitation tradeoff using variance estimates in multi-armed bandits 1995Sample mean based index policies byO(logn) regret for the multi-armed bandit problem

Cited by

2013KULLBACK-LEIBLER UPPER CONFIDENCE BOUNDS FOR OPTIMAL SEQUENTIAL ALLOCATION 2013Bandits With Heavy Tail 2012Optimistic bayesian sampling in contextual-bandit problems 2014Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms 2013Kullback–Leibler upper confidence bounds for optimal sequential allocation 20121 1 Online Learning of Rested and Restless Bandits 2017Near-Optimal Regret Bounds for Thompson Sampling 2012Online Learning of Rested and Restless Bandits

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.