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

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

## Key facts

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

## Built on by (most cited first, 30 of 31)

- [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)
- [No-Regret Reinforcement Learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2102.12769/) (2021)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (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)
- [Trustworthy Distributed AI Systems: Robustness, Privacy, and Governance](https://mlsanity.com/paper/2402.01096/) (2024)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards](https://mlsanity.com/paper/2306.11455/) (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)
- [Robust Offline Reinforcement learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2310.18715/) (2023)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm](https://mlsanity.com/paper/2203.03186/) (2022)
- [Learning pure quantum states (almost) without regret](https://mlsanity.com/paper/2406.18370/) (2024)
- [Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update](https://mlsanity.com/paper/2503.00419/) (2025)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)
- [Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise](https://mlsanity.com/paper/2402.07062/) (2024)
- [Catoni Contextual Bandits are Robust to Heavy-tailed Rewards](https://mlsanity.com/paper/2502.02486/) (2025)
- [On solutions of the distributional Bellman equation](https://mlsanity.com/paper/2202.00081/) (2022)
- [Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits](https://mlsanity.com/paper/2305.06743/) (2023)
- [Safe Bayesian optimization across noise models via scenario programming](https://mlsanity.com/paper/2512.11580/) (2025)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)
- [Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.08302/) (2022)
- [Batched Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2510.03798/) (2025)
- [Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise](https://mlsanity.com/paper/2603.15596/) (2026)
- [Learning Pure Quantum States in Any Dimension (Almost) Without Regret](https://mlsanity.com/paper/2605.09019/) (2026)
- [Nonlinear Bandit](https://mlsanity.com/paper/2607.07304/) (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 linear stochastic bandits, it is commonly assumed that payoffs are with sub-Gaussian noises. In this paper, under a weaker assumption on noises, we study the problem of underlinelinear stochastic underline bandits with hunderline eavy-underline tailed payoffs (LinBET), where the distributions have finite moments of order 1+ε, for some ε∈ (0,1]. We rigorously analyze the regret lower bound of LinBET as Omega(T^frac11+ε), implying that finite moments of order 2 (i.e., finite variances) yield the bound of Omega(√T), with T being the total number of rounds to play bandits. The provided lower bound also indicates that the state-of-the-art algorithms for LinBET are far from optimal. By adopting median of means with a well-designed allocation of decisions and truncation based on historical information, we develop two novel bandit algorithms, where the regret upper bounds match the lower bound up to polylogarithmic factors. To the best of our knowledge, we are the first to solve LinBET optimally in the sense of the polynomial order on T. Our proposed algorithms are evaluated based on synthetic datasets, and outperform the state-of-the-art results.