# Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2020.

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

- [Topology-Imbalance Learning for Semi-Supervised Node Classification](https://mlsanity.com/paper/2110.04099/) (2021)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Imbalanced Graph Classification via Graph-of-Graph Neural Networks](https://mlsanity.com/paper/2112.00238/) (2021)
- [Towards Robust Offline Reinforcement Learning under Diverse Data Corruption](https://mlsanity.com/paper/2310.12955/) (2023)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Graph Classification by Mixture of Diverse Experts](https://mlsanity.com/paper/2103.15622/) (2021)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [Knowledge Learning with Crowdsourcing: A Brief Review and Systematic Perspective](https://mlsanity.com/paper/2206.09315/) (2022)
- [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)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Tackling the Imbalance for GNNs](https://mlsanity.com/paper/2110.08690/) (2021)
- [NodeTrans: A Graph Transfer Learning Approach for Traffic Prediction](https://mlsanity.com/paper/2207.01301/) (2022)
- [Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update](https://mlsanity.com/paper/2503.00419/) (2025)
- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)
- [Catoni Contextual Bandits are Robust to Heavy-tailed Rewards](https://mlsanity.com/paper/2502.02486/) (2025)
- [Graph Convolutional Network for Multi-Target Multi-Camera Vehicle Tracking](https://mlsanity.com/paper/2211.15538/) (2022)
- [Tight Complexity of Muon under Heavy-Tailed Noise](https://mlsanity.com/paper/2605.18528/) (2026)
- [Fast and Accurate Graph Learning for Huge Data via Minipatch Ensembles](https://mlsanity.com/paper/2110.12067/) (2021)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)
- [Graph Decipher: A transparent dual-attention graph neural network to understand the message-passing mechanism for the node classification](https://mlsanity.com/paper/2201.01381/) (2022)
- [Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise](https://mlsanity.com/paper/2603.15596/) (2026)
- [Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set](https://mlsanity.com/paper/2607.23679/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of stochastic linear bandits with finite action sets. Most of existing work assume the payoffs are bounded or sub-Gaussian, which may be violated in some scenarios such as financial markets. To settle this issue, we analyze the linear bandits with heavy-tailed payoffs, where the payoffs admit finite 1+ε moments for some ε∈(0,1]. Through median of means and dynamic truncation, we propose two novel algorithms which enjoy a sublinear regret bound of widetildeO(d^frac12T^frac11+ε), where d is the dimension of contextual information and T is the time horizon. Meanwhile, we provide an Omega(d^fracε1+εT^frac11+ε) lower bound, which implies our upper bound matches the lower bound up to polylogarithmic factors in the order of d and T when ε=1. Finally, we conduct numerical experiments to demonstrate the effectiveness of our algorithms and the empirical results strongly support our theoretical guarantees.