# Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 10 Feb 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [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)
- [Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits](https://mlsanity.com/paper/2305.06743/) (2023)

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

- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Functional multi-armed bandit and the best function identification problems](https://mlsanity.com/paper/2503.00509/) (2025)
- [Managing Self-Learning Experts under Per-Round Budget Constraints](https://mlsanity.com/paper/2510.22654/) (2025)

## Abstract (arXiv)

In this study, we propose a new method for constructing UCB-type algorithms for stochastic multi-armed bandits based on general convex optimization methods with an inexact oracle. We derive the regret bounds corresponding to the convergence rates of the optimization methods. We propose a new algorithm Clipped-SGD-UCB and show, both theoretically and empirically, that in the case of symmetric noise in the reward, we can achieve an O(log T√KTlog T) regret bound instead of Oleft (T^frac11+α K^fracα1+α right) for the case when the reward distribution satisfies mathbbEX ∈ D[|X|1+α] ≤ σ1+α (α ∈ (0, 1]), i.e. perform better than it is assumed by the general lower bound for bandits with heavy-tails. Moreover, the same bound holds even when the reward distribution does not have the expectation, that is, when α<0.