# No-Regret Reinforcement Learning with Heavy-Tailed Rewards

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Dopamine: A Research Framework for Deep Reinforcement Learning](https://mlsanity.com/paper/1812.06110/) (2018)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Reinforcement Learning with Perturbed Rewards](https://mlsanity.com/paper/1810.01032/) (2018)
- [Reinforcement Learning with a Corrupted Reward Channel](https://mlsanity.com/paper/1705.08417/) (2017)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/1902.08708/) (2019)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [Optimistic Exploration even with a Pessimistic Initialisation](https://mlsanity.com/paper/2002.12174/) (2020)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [Coordinated Exploration in Concurrent Reinforcement Learning](https://mlsanity.com/paper/1802.01282/) (2018)
- [Thompson Sampling on Symmetric α-Stable Bandits](https://mlsanity.com/paper/1907.03821/) (2019)

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

- [Towards Robust Offline Reinforcement Learning under Diverse Data Corruption](https://mlsanity.com/paper/2310.12955/) (2023)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [A Review of Reinforcement Learning in Financial Applications](https://mlsanity.com/paper/2411.12746/) (2024)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Robust Offline Reinforcement learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2310.18715/) (2023)
- [Optimizing Tensor Network Contraction Using Reinforcement Learning](https://mlsanity.com/paper/2204.09052/) (2022)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [On solutions of the distributional Bellman equation](https://mlsanity.com/paper/2202.00081/) (2022)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)
- [Empirical Risk Minimization for Losses without Variance](https://mlsanity.com/paper/2309.03818/) (2023)
- [Generalized Gaussian Temporal Difference Error for Uncertainty-aware Reinforcement Learning](https://mlsanity.com/paper/2408.02295/) (2024)
- [Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2607.25492/) (2026)

## Abstract (arXiv)

Reinforcement learning algorithms typically assume rewards to be sampled from light-tailed distributions, such as Gaussian or bounded. However, a wide variety of real-world systems generate rewards that follow heavy-tailed distributions. We consider such scenarios in the setting of undiscounted reinforcement learning. By constructing a lower bound, we show that the difficulty of learning heavy-tailed rewards asymptotically dominates the difficulty of learning transition probabilities. Leveraging techniques from robust mean estimation, we propose Heavy-UCRL2 and Heavy-Q-Learning, and show that they achieve near-optimal regret bounds in this setting. Our algorithms also naturally generalize to deep reinforcement learning applications; we instantiate Heavy-DQN as an example of this. We demonstrate that all of our algorithms outperform baselines on both synthetic MDPs and standard RL benchmarks.