Bounded regret in stochastic multi-armed bandits

Sébastien Bubeck, Vianney Perchet, Philippe Rigollet

We study the stochastic multi-armed bandit problem when one knows the value ${\mu }^{(\star )}$ of an optimal arm, as a well as a positive lower bound on the smallest positive gap $\Delta$. W…