Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise

In this study, we propose a new method for constructing UCB-type algorithms for stochastic multi-armed bandits based on general convex optimization methods with an inexact oracle. We derive the regret bounds corresponding to the convergence rates of the optimization methods. We propose a new algorithm Clipped-SGD-UCB and show, both theoretically and empirically, that in the case of symmetric noise in the reward, we can achieve an O(log T√KTlog T) regret bound instead of Oleft (T^frac11+α K^fracα1+α right) for the case when the reward distribution satisfies mathbbEX ∈ D[|X|1+α] ≤ σ1+α (α ∈ (0, 1]), i.e. perform better than it is assumed by the general lower bound for bandits with heavy-tails. Moreover, the same bound holds even when the reward distribution does not have the expectation, that is, when α<0.