A minimax and asymptotically optimal algorithm for stochastic bandits

Edition Number: 
28
Date: 
October, 2017
Place: 
Kyoto, Japan
PageStart: 
223
PageEnd: 
237
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.

Arxiv Number: 
1702.07211
Hal Number: 
01475078