Anytime optimal algorithms in stochastic multi-armed bandits


Rémy Degenne, Vianney Perchet ;
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1587-1595, 2016.


We introduce an anytime algorithm for stochastic multi-armed bandit with optimal distribution free and distribution dependent bounds (for a specific family of parameters). The performances of this algorithm (as well as another one motivated by the conjectured optimal bound) are evaluated empirically. A similar analysis is provided with full information, to serve as a benchmark.

Related Material