Mathematics – Statistics Theory
Scientific paper
2011-02-12
Mathematics
Statistics Theory
13 pages, 4 figures; Conf. Comput. Learning Theory (COLT) 2011 in Budapest, Hungary
Scientific paper
This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satisfies a uniformly better regret bound than UCB or UCB2; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specific classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, UCB2, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm.
Cappé Olivier
Garivier Aurelien
No associations
LandOfFree
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-84784