Articles

Kullback-Leibler upper confidence bounds for optimal sequential allocation

O. CAPPE, A. GARIVIER, O.-A. MAILLARD, R. MUNOS, G. STOLTZ

Annals of Statistics

June 2013, vol. 41, n°3, pp.1516-1541

Departments: Economics & Decision Sciences, GREGHEC (CNRS)

Keywords: Multi-armed bandit problems, Upper confidence bound, Kullback–Leibler divergence, Sequential testing

http://projecteuclid.org/euclid.aos/1375362558


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 [J. R. Stat. Soc. Ser. B Stat. Methodol. 41 (1979) 148–177], 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 [Adv. in Appl. Math. 6 (1985) 4–22] and Burnetas and Katehakis [Adv. in Appl. Math. 17 (1996) 122–142], 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


JavaScriptSettings