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: