A minimax and asymptotically optimal algorithm for stochastic bandits


Pierre Ménard, Aurélien Garivier ;
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:223-237, 2017.


We propose the $\text{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 and clear proofs.

Related Material