# Quantum Heavy-tailed Bandits

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 23 Jan 2023.

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

- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits](https://mlsanity.com/paper/2209.02570/) (2022)
- [Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/2004.13465/) (2020)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Quantum exploration algorithms for multi-armed bandits](https://mlsanity.com/paper/2007.07049/) (2020)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [A Multi-Armed Bandit to Smartly Select a Training Set from Big Medical Data](https://mlsanity.com/paper/1705.08111/) (2017)

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

- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (2025)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)
- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization](https://mlsanity.com/paper/2607.01080/) (2026)
- [Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2607.25492/) (2026)
- [Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms](https://mlsanity.com/paper/2608.14319/) (2026)

## Abstract (arXiv)

In this paper, we study multi-armed bandits (MAB) and stochastic linear bandits (SLB) with heavy-tailed rewards and quantum reward oracle. Unlike the previous work on quantum bandits that assumes bounded/sub-Gaussian distributions for rewards, here we investigate the quantum bandits problem under a weaker assumption that the distributions of rewards only have bounded (1+v)-th moment for some v∈ (0,1]. In order to achieve regret improvements for heavy-tailed bandits, we first propose a new quantum mean estimator for heavy-tailed distributions, which is based on the Quantum Monte Carlo Mean Estimator and achieves a quadratic improvement of estimation error compared to the classical one. Based on our quantum mean estimator, we focus on quantum heavy-tailed MAB and SLB and propose quantum algorithms based on the Upper Confidence Bound (UCB) framework for both problems with TildeO(T^frac1-v1+v) regrets, polynomially improving the dependence in terms of T as compared to classical (near) optimal regrets of TildeO(T^frac11+v), where T is the number of rounds. Finally, experiments also support our theoretical results and show the effectiveness of our proposed methods.