2011
COLT
COLT 2011
A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
Abstract
We consider a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit problem in the case of distributions with finite supports (not necessarily known beforehand), whose asymptotic regret matches the lower bound of Burnetas and Katehakis (1996). Our contribution is to provide a finite-time analysis of this algorithm; we get bounds whose main terms are smaller than the ones of previously known algorithms with finite-time analyses (like UCB-type algorithms).
🚀
Conference Pioneer
- COLT 2011
🌉
Interdisciplinary Bridge
- Artificial Intelligence and Mathematics & Optimization
🐣
Hot Topic Early Bird
- regret minimization
Authors
Topics
Machine Learning > Optimization & Theory > Learning Theory
Machine Learning > Optimization & Theory > Optimization
Machine Learning > Learning Types > Online Learning
Machine Learning > Optimization & Theory > Stochastic Methods
Mathematics & Optimization > Optimization > Optimization
Machine Learning > Learning Types > Multi-Armed Bandits