KULLBACK-LEIBLER UPPER CONFIDENCE BOUNDS FOR OPTIMAL SEQUENTIAL ALLOCATION

• 成果类型: Article
• 署名作者: Cappe, Olivier; Garivier, Aurelien; Maillard, Odalric-Ambrym; Munos, Remi; Stoltz, Gilles
• 署名单位: Centre National de la Recherche Scientifique (CNRS); IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; University of Leoben; Inria; Centre National de la Recherche Scientifique (CNRS); Hautes Etudes Commerciales (HEC) Paris; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/13-AOS1119
• 发表日期: 2013
• 页码: 1516-1541
• 关键词: optimal adaptive policies; regret

摘要

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.