From the archives
A minimax and asymptotically optimal algorithm for stochastic bandits
Historical material. Affiliations, schedules and roles on this page describe their original context.
ConferenceName: Algorithmic Learning Theory
url: ALT 2017
Edition Number: 28
Date: October, 2017
Place: Kyoto, Japan
PageStart: 223
PageEnd: 237
Authors: Pierre MénardAurélien Garivier
Abstract:
We propose the kl-UCB ++ algorithm for regret minimization in stochastic bandit models with exponential families of distributions. We prove that it is simultaneously asymptotically optimal (in the sense of Lai and Robbins' lower bound) and minimax optimal. This is the first algorithm proved to enjoy these two properties at the same time. This work thus merges two different lines of research, with simple proofs involving no complexity overhead.
Direct link: published in Proceedings of Machine Learning Research (PMLR) vol. 76 Arxiv Number: 1702.07211 Hal Number: 01475078 Keywords: