# Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 22 references that are in the map.
- First posted on arXiv 9 Jun 2024.

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

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Boltzmann Exploration Done Right](https://mlsanity.com/paper/1705.10257/) (2017)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards](https://mlsanity.com/paper/1906.00569/) (2019)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [Sign-Perturbed Sums: A New System Identification Approach for Constructing Exact Non-Asymptotic Confidence Regions in Linear Regression Models](https://mlsanity.com/paper/1807.08216/) (2018)
- [Semi-Parametric Uncertainty Bounds for Binary Classification](https://mlsanity.com/paper/1903.09790/) (2019)
- [Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case](https://mlsanity.com/paper/2401.15792/) (2024)

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

- [Parameter-Free Heavy-Tailed Bandits](https://mlsanity.com/paper/2607.29460/) (2026)
- [Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem](https://mlsanity.com/paper/2512.18409/) (2025)
- [Reliable Scale-Free Bandits via Empirical Likelihood](https://mlsanity.com/paper/2610.18055/) (2026)

## Abstract (arXiv)

Stochastic multi-armed bandits (MABs) provide a fundamental reinforcement learning model to study sequential decision making in uncertain environments. The upper confidence bounds (UCB) algorithm gave birth to the renaissance of bandit algorithms, as it achieves near-optimal regret rates under various moment assumptions. Up until recently most UCB methods relied on concentration inequalities leading to confidence bounds which depend on moment parameters, such as the variance proxy, that are usually unknown in practice. In this paper, we propose a new distribution-free, data-driven UCB algorithm for symmetric reward distributions, which needs no moment information. The key idea is to combine a refined, one-sided version of the recently developed resampled median-of-means (RMM) method with UCB. We prove a near-optimal regret bound for the proposed anytime, parameter-free RMM-UCB method, even for heavy-tailed distributions.