mlsanityData to 7 Oct 2026

No-Regret Reinforcement Learning with Heavy-Tailed Rewards

arXiv 2102.12769 ↗First posted 25 Feb 2021cs.LG stat.MLcited by 13

Not on the map. Why?

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.

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

Builds on

18 of 42 references.

References · 18

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2017Robust Adversarial Reinforcement Learningcited by 439
  5. 2016#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learningcited by 307
  6. 2018Dopamine: A Research Framework for Deep Reinforcement Learningcited by 121
  7. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  8. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  9. 2018Reinforcement Learning with Perturbed Rewardscited by 76
  10. 2017Reinforcement Learning with a Corrupted Reward Channelcited by 68
  11. 2013Thompson Sampling for 1-Dimensional Exponential Family Banditscited by 41
  12. 2019Distributionally Robust Reinforcement Learningcited by 40
6 more
  1. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  2. 2018Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffscited by 31
  3. 2020Optimistic Exploration even with a Pessimistic Initialisationcited by 25
  4. 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
  5. 2018Coordinated Exploration in Concurrent Reinforcement Learningcited by 17
  6. 2019Thompson Sampling on Symmetric α-Stable Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 7; 2024: 2; 2025: 1; 2026: 1.

13 papers.

Sort:

By area:

  1. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  2. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  3. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 11
  4. 2024A Review of Reinforcement Learning in Financial Applicationscited by 11
  5. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  6. 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
  7. 2022Optimizing Tensor Network Contraction Using Reinforcement Learningcited by 5
  8. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  9. 2022On solutions of the distributional Bellman equationcited by 2
  10. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  11. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  12. 2023Empirical Risk Minimization for Losses without Variancecited by 0
1 more
  1. 2024Generalized Gaussian Temporal Difference Error for Uncertainty-aware Reinforcement Learningcited by 0