Optimal Regret Bounds for Linear Bandits with Heavy-Tailed Rewards

In heavy-tailed linear bandits, a learner chooses among $N$ actions in the $d$-dimensional unit ball, the mean rewards are linear in an unknown parameter, and the rewards only have bounded centered $p$-th moments for some $p\in (1,2]$. Even for polynomially many actions, the best known upper and lower regret bounds differ by a factor that grows with $d$. Let $q=p/(p-1)$. For fixed $B>0$, sufficiently large $d$, and $2\le N\le d^B$, we show that the minimax regret over $T$ rounds on the hardest set of $N$ actions is $\Theta (\min \{T,\sqrt{d}[\log (1+N/d^{q/2}){]}^{1/q}{T}^{1/p}\})$. Our main contribution is the lower bound, which separates the information shared across actions from the evidence available only at the optimal action. For $N=d^a$ with $a>q/2$, it improves the previous lower bound by a factor of order $d^{1/2-1/q}(\log d{)}^{1/q}$ and matches the known upper bound. We also propose Hybrid FTRL, which estimates the loss of each action by a direct or a linear estimate, whichever has the smaller moment bound. It attains the rate above on every finite action set, including the range where combining existing algorithms falls short. The rate shows that linear structure reduces regret only when $N$ exceeds $d^{q/2}$.