Kullback–Leibler upper confidence bounds for optimal sequential allocation
Authors:
- Olivier CappéOCOlivier Cappé
- Aurélien GarivierAGAurélien Garivier
- Odalric-Ambrym MaillardOMOdalric-Ambrym Maillard
- Rémi MunosRMRémi Munos
- Gilles StoltzGSGilles Stoltz
Top Cited Papers
Open Access
- 1 June 2013
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Statistics
- Vol. 41 (3) , 1516-1541
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 [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.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- ASYMPTOTIC BAYES ANALYSIS FOR THE FINITE-HORIZON ONE-ARMED-BANDIT PROBLEMProbability in the Engineering and Informational Sciences, 2003
- Sample mean based index policies byO(logn) regret for the multi-armed bandit problemAdvances in Applied Probability, 1995
- On the Gittins Index for Multiarmed BanditsThe Annals of Applied Probability, 1992
- Optimal stopping and dynamic allocationAdvances in Applied Probability, 1987
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952
- Sequential Tests of Statistical HypothesesThe Annals of Mathematical Statistics, 1945
- On the Theory of ApportionmentAmerican Journal of Mathematics, 1935
- ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLESBiometrika, 1933