Fast UCB-type Algorithms for Stochastic Bandits with Heavy and Super Heavy Symmetric Noise

This paper considers stochastic multi-armed bandit problems (MAB) and presents a novel framework for constructing UCB-type algorithms. The main ingredient of UCB-type algorithms is the estimate of the confidence bound typically derived from statistical assumptions. On the opposite, our approach derives the confidence bounds from the convergence rate of the base convex optimization method, which helps to solve auxiliary optimization problems in every round. To show the relations between the convergence of the optimization method and the novel UCB-type algorithm, we derive the regret bounds corresponding to the convergence rates of the selected optimization method. To illustrate the proposed framework, we introduce a new algorithm, Clipped-SGD-UCB, for the MAB with heavy-tailed reward distribution, where Clipped-SGD is used as a base convex optimization method since its convergence for the heavy-tail inexact oracle is known. We show theoretically and empirically that in the case of symmetric noise in the reward distribution, one can achieve an 𝑂 (log𝑇 √︁ 𝐾𝑇 log𝑇) regret bound instead of 𝑂 𝑇 1 1+𝛼 𝐾 𝛼 1+𝛼. These bounds correspond to the cases where the reward distribution satisfies E 𝑋 ∈ D [|𝑋 | 1+𝛼 ] ≤ 𝜎 1+𝛼 (𝛼 ∈ (0, 1]), i.e. perform better than it is assumed by the general lower bound for bandits with heavy-tails.