# Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards

arXiv: https://arxiv.org/abs/2506.04775 · HTML: https://mlsanity.com/paper/2506.04775/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 5 Jun 2025.

## Builds on (most cited first, 18 of 18)

- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/2004.13465/) (2020)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs](https://mlsanity.com/paper/2110.13876/) (2021)
- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update](https://mlsanity.com/paper/2503.00419/) (2025)

## Built on by (most cited first, 4 of 4)

- [Managing Self-Learning Experts under Per-Round Budget Constraints](https://mlsanity.com/paper/2510.22654/) (2025)
- [Safe Bayesian optimization across noise models via scenario programming](https://mlsanity.com/paper/2512.11580/) (2025)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)
- [Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise](https://mlsanity.com/paper/2603.15596/) (2026)

## Abstract (arXiv)

We study stochastic linear bandits with heavy-tailed rewards, where the rewards have a finite (1+ε)-absolute central moment bounded by upsilon for some ε ∈ (0,1]. We improve both upper and lower bounds on the minimax regret compared to prior work. When upsilon = O(1), the best prior known regret upper bound is tildeO(d T^frac11+ε). While a lower with the same scaling has been given, it relies on a construction using upsilon = O(d), and adapting the construction to the bounded-moment regime with upsilon = O(1) yields only a Omega(d^fracε1+ε T^frac11+ε) lower bound. This matches the known rate for multi-armed bandits and is generally loose for linear bandits, in particular being √d below the optimal rate in the finite-variance case (ε = 1). We propose a new elimination-based algorithm guided by experimental design, which achieves regret tildeO(d^frac1+3ε2(1+ε) T^frac11+ε), thus improving the dependence on d for all ε ∈ (0,1) and recovering a known optimal result for ε = 1. We also establish a lower bound of Omega(d^frac2ε1+ε T^frac11+ε), which strictly improves upon the multi-armed bandit rate and highlights the hardness of heavy-tailed linear bandit problems. For finite action sets, we derive similarly improved upper and lower bounds for regret. Finally, we provide action set dependent regret upper bounds showing that for some geometries, such as lp-norm balls for p ≤ 1 + ε, we can further reduce the dependence on d, and we can handle infinite-dimensional settings via the kernel trick, in particular establishing new regret bounds for the Mat'ern kernel that are the first to be sublinear for all ε ∈ (0, 1].