Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards

Artin Tajdini, Jonathan Scarlett, Kevin Jamieson

We study stochastic linear bandits with heavy-tailed rewards, where the rewards have a finite $(1+\epsilon )$-absolute central moment bounded by $\upsilon$ for some $\epsilon \in (0,1]$. We improv…