Bounded regret in stochastic multi-armed bandits


Sébastien Bubeck, Vianney Perchet, Philippe Rigollet ;
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:122-134, 2013.


We study the stochastic multi-armed bandit problem when one knows the value μ^(⋆) of an optimal arm, as a well as a positive lower bound on the smallest positive gap ∆. We propose a new randomized policy that attains a regret uniformly bounded over time in this setting. We also prove several lower bounds, which show in particular that bounded regret is not possible if one only knows ∆, and bounded regret of order 1/∆is not possible if one only knows μ^(⋆).

Related Material