# (ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 26 references that are in the map.
- First posted on arXiv 4 Oct 2023.

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

- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Adaptation to the Range in K-Armed Bandits](https://mlsanity.com/paper/2006.03378/) (2020)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [Bounded regret in stochastic multi-armed bandits](https://mlsanity.com/paper/1302.1611/) (2013)
- [A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis](https://mlsanity.com/paper/1703.08937/) (2017)

## Abstract (arXiv)

Heavy-tailed distributions naturally arise in several settings, from finance to telecommunications. While regret minimization under subgaussian or bounded rewards has been widely studied, learning with heavy-tailed distributions only gained popularity over the last decade. In this paper, we consider the setting in which the reward distributions have finite absolute raw moments of maximum order 1+ε, uniformly bounded by a constant u<+∞, for some ε ∈ (0,1]. In this setting, we study the regret minimization problem when ε and u are unknown to the learner and it has to adapt. First, we show that adaptation comes at a cost and derive two negative results proving that the same regret guarantees of the non-adaptive case cannot be achieved with no further assumptions. Then, we devise and analyze a fully data-driven trimmed mean estimator and propose a novel adaptive regret minimization algorithm, AdaR-UCB, that leverages such an estimator. Finally, we show that AdaR-UCB is the first algorithm that, under a known distributional assumption, enjoys regret guarantees nearly matching those of the non-adaptive heavy-tailed case.