# Regret Minimization in Heavy-Tailed Bandits

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 30 references that are in the map.
- First posted on arXiv 7 Feb 2021.

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

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Optimal Best-Arm Identification Methods for Tail-Risk Measures](https://mlsanity.com/paper/2008.07606/) (2020)
- [A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis](https://mlsanity.com/paper/1703.08937/) (2017)
- [An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support](https://mlsanity.com/paper/1505.01918/) (2015)

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

- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm](https://mlsanity.com/paper/2203.03186/) (2022)
- [Multi-Armed Bandits with Self-Information Rewards](https://mlsanity.com/paper/2209.02211/) (2022)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits](https://mlsanity.com/paper/2302.01544/) (2023)
- [Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise](https://mlsanity.com/paper/2402.07062/) (2024)
- [Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits](https://mlsanity.com/paper/2406.05710/) (2024)
- [A Black Swan Hypothesis: The Role of Human Irrationality in AI Safety](https://mlsanity.com/paper/2407.18422/) (2024)
- [CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption](https://mlsanity.com/paper/2309.16563/) (2023)
- [Asymptotically Optimal Sequential Testing with Markovian Data](https://mlsanity.com/paper/2602.17587/) (2026)
- [Multi-Armed Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2603.17925/) (2026)
- [Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards](https://mlsanity.com/paper/2604.14876/) (2026)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (2023)
- [(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2310.02975/) (2023)
- [Batched Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2510.03798/) (2025)
- [Learning When Not to Learn: Risk-Sensitive Abstention in Bandits with Unbounded Rewards](https://mlsanity.com/paper/2510.14884/) (2025)
- [Nonlinear Bandit](https://mlsanity.com/paper/2607.07304/) (2026)
- [SGHA: Evidence-Grounded Research Problem Discovery with Local Language Models](https://mlsanity.com/paper/2608.17501/) (2026)
- [Reliable Scale-Free Bandits via Empirical Likelihood](https://mlsanity.com/paper/2610.18055/) (2026)

## Abstract (arXiv)

We revisit the classic regret-minimization problem in the stochastic multi-armed bandit setting when the arm-distributions are allowed to be heavy-tailed. Regret minimization has been well studied in simpler settings of either bounded support reward distributions or distributions that belong to a single parameter exponential family. We work under the much weaker assumption that the moments of order (1+ε) are uniformly bounded by a known constant B, for some given ε > 0. We propose an optimal algorithm that matches the lower bound exactly in the first-order term. We also give a finite-time bound on its regret. We show that our index concentrates faster than the well known truncated or trimmed empirical mean estimators for the mean of heavy-tailed distributions. Computing our index can be computationally demanding. To address this, we develop a batch-based algorithm that is optimal up to a multiplicative constant depending on the batch size. We hence provide a controlled trade-off between statistical optimality and computational cost.