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

Abstract

In this study, we propose a new method for constructing UCB-type algorithms for stochastic multiarmed bandits based on general convex optimization methods with an inexact oracle. We derive theregret bounds corresponding to the convergence rates of the optimization methods. We propose anew algorithm Clipped-SGD-UCB and show, both theoretically and empirically, that in the caseof symmetric noise in the reward, we can achieve an O(log T√KT log T) regret bound insteadof OT11+α Kα1+αfor the case when the reward distribution satisfies EX∈D[|X|1+α] ⩽ σ1+α(α ∈ (0, 1]), i.e. perform better than it is assumed by the general lower bound for bandits withheavy-tails. Moreover, the same bound holds even when the reward distribution does not have theexpectation, that is, when α < 0.