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: