# Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 26 Oct 2021.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [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)

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

- [Towards Robust Offline Reinforcement Learning under Diverse Data Corruption](https://mlsanity.com/paper/2310.12955/) (2023)
- [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)
- [Robust Offline Reinforcement learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2310.18715/) (2023)
- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)
- [Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits](https://mlsanity.com/paper/2305.06743/) (2023)
- [Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach](https://mlsanity.com/paper/2511.03074/) (2025)
- [Nonlinear Bandit](https://mlsanity.com/paper/2607.07304/) (2026)

## Abstract (arXiv)

Despite a large amount of effort in dealing with heavy-tailed error in machine learning, little is known when moments of the error can become non-existential: the random noise η satisfies Prleft[|η| > |y|right] ≤ 1/|y|α for some α > 0. We make the first attempt to actively handle such super heavy-tailed noise in bandit learning problems: We propose a novel robust statistical estimator, mean of medians, which estimates a random variable by computing the empirical mean of a sequence of empirical medians. We then present a generic reductionist algorithmic framework for solving bandit learning problems (including multi-armed and linear bandit problem): the mean of medians estimator can be applied to nearly any bandit learning algorithm as a black-box filtering for its reward signals and obtain similar regret bound as if the reward is sub-Gaussian. We show that the regret bound is near-optimal even with very heavy-tailed noise. We also empirically demonstrate the effectiveness of the proposed algorithm, which further corroborates our theoretical results.