From the archives
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
Historical material. Affiliations, schedules and roles on this page describe their original context.
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 and its variants; 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, MOSS,
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.
COLT presentation on videolectures
