Bandits with heavy tail

Sébastien Bubeck, Nicolò Cesa-Bianchi, Gábor Lugosi

The stochastic multi-armed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper we examine the bandit problem under the weaker assumption…