From the archives
Kullback-Leibler Upper Confidence Bounds for Optimal Sequential Allocation
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: Annals of Statistics
Date: June, 2013
PageStart: 1 516
PageEnd: 1 541
Arxiv Number: 1210.1136
Hal Number: 00738209
Authors: Olivier CappéAurélien GarivierOdalric-Ambrym MaillardRémi MunosGilles Stoltz
Abstract: We consider optimal sequential allocation in the context of the
so-called stochastic multi-armed bandit model. We describe a generic index policy, in the
sense of Gittins (1979), based on upper confidence bounds of the arm payoffs computed using
the Kullback-Leibler divergence. We consider two classes of distributions for which
instances of this general idea are analyzed: The kl-UCB algorithm is designed for
one-parameter exponential families and the empirical KL-UCB algorithm for bounded and
finitely supported distributions. Our main contribution is a unified finite-time analysis of
the regret of these algorithms that asymptotically matches the lower bounds of Lai and
Robbins (1985) and Burnetas and Katehakis (1996), respectively. We also investigate the
behavior of these algorithms when used with general bounded rewards, showing in particular
that they provide significant improvements over the state-of-the-art.
Direct link: accessible on Projet Euclid
Issue: 3
Volume: 41
Keywords:
