Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs

In linear stochastic bandits, it is commonly assumed that pa yoffs are with sub-Gaussian noises. In this paper, under a weaker assumption on noises, we study the problem of lin ear stochastic b andits with he avy-t ailed payoffs (LinBET), where the distributions have finite moments of order 1+ ϵ,f o rs o m e ϵ (0, 1] .W e rigorously analyze the regret lower bound of LinBET as Ω( T