# Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and Beyond

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 61 references that are in the map.
- First posted on arXiv 19 Aug 2025.

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

- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)

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

- [Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Bandits](https://mlsanity.com/paper/2510.22819/) (2025)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)
- [Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader](https://mlsanity.com/paper/2606.06043/) (2026)
- [Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?](https://mlsanity.com/paper/2608.15365/) (2026)

## Abstract (arXiv)

Heavy-tailed bandits have been extensively studied since the seminal work of citetBubeck2012BanditsWH. In particular, heavy-tailed linear bandits, enabling efficient learning with both a large number of arms and heavy-tailed noises, have recently attracted significant attention citepShaoYKL18,XueWWZ20,ZhongHYW21,Wang2025heavy,tajdini2025improved. However, prior studies focus almost exclusively on stochastic regimes, with few exceptions limited to the special case of heavy-tailed multi-armed bandits (MABs) citepHuang0H22,ChengZ024,Chen2024uniINF. In this work, we propose a general framework for adversarial heavy-tailed bandit problems, which performs follow-the-regularized-leader (FTRL) over the loss estimates shifted by a bonus function. Via a delicate setup of the bonus function, we devise the first FTRL-type best-of-both-worlds (BOBW) algorithm for heavy-tailed MABs, which does not require the truncated non-negativity assumption and achieves an widetildeO(T^frac1varepsilon) worst-case regret in the adversarial regime as well as an widetildeO(log T) gap-dependent regret in the stochastic regime. We then extend our framework to the linear case, proposing the first algorithm for adversarial heavy-tailed linear bandits with finite arm sets. This algorithm achieves an widetildeO(d^frac12T^frac1varepsilon) regret, matching the best-known worst-case regret bound in stochastic regimes. Moreover, we propose a general data-dependent learning rate, termed textitheavy-tailed noise aware stability-penalty matching (HT-SPM). We prove that HT-SPM guarantees BOBW regret bounds for general heavy-tailed bandit problems once certain conditions are satisfied. By using HT-SPM and, in particular, a variance-reduced linear loss estimator, we obtain the first BOBW result for heavy-tailed linear bandits.