Robust Reinforcement Learning for Heavy Tailed Rewards

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2231 papers293 conceptsfrozen 2026-10-04

In the standard playbook of reinforcement learning (RL) and multi-armed bandits, we often assume the world is "well-behaved." We design algorithms under the assumption that rewards are bounded or follow a sub-Gaussian distribution—meaning the probability of seeing an extreme outlier decays at least as fast as a bell curve.

But real-world data is rarely so polite. In financial markets, network traffic, and social media engagement, "black swan" events are not just possible; they are frequent. These environments exhibit heavy-tailed rewards, where the variance can be infinite and a single outlier can be orders of magnitude larger than the mean. When standard algorithms encounter these outliers, their learning process doesn't just slow down—it often breaks entirely.

The Failure of the Empirical Mean

The core of the problem lies in how we estimate value. Most RL agents rely on the empirical mean to estimate the quality of an action. As Abhimanyu Dubey and Alex Pentland point out in Thompson Sampling on Symmetric Alpha-Stable Bandits, when rewards have infinite variance, the empirical mean fails to converge at a useful rate.

Imagine an agent trying to choose between two financial assets. Asset A is steady, while Asset B is volatile but usually mediocre. Suddenly, Asset B yields a massive, one-in-a-million windfall. A standard agent will see its empirical mean skyrocket and conclude that Asset B is superior, potentially spending thousands of iterations chasing a "ghost" reward that will never return. Conversely, in Temporal Difference (TD) learning, Semih Cayci and Atilla Eryilmaz demonstrate in Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards that these outliers cause stochastic gradients to explode, leading to unstable value estimates that never settle.

The Robust Toolkit: Truncation and Smoothing

To survive in heavy-tailed environments, researchers have turned to robust statistics. The goal is to create estimators that are "outlier-resistant"—they should capture the true mean of the distribution without being hijacked by the tails.

Several key mechanisms have emerged:

From Bandits to Deep Reinforcement Learning

While early work focused on simple bandits, recent research has scaled these robust techniques to complex RL settings involving function approximation and deep networks.

In No-Regret Reinforcement Learning with Heavy-Tailed Rewards, Vincent Zhuang and Yanan Sui show that by replacing standard mean estimators with robust versions in algorithms like UCRL2 and DQN, agents can achieve near-optimal regret even when reward variance is infinite. This shift is crucial because, in heavy-tailed RL, the primary challenge is no longer just learning the transition dynamics of the environment, but accurately filtering the "noise" of the reward signal itself.

For offline settings, where we cannot collect new data to verify outliers, Yiding Chen and Qiaomin Xie prove in Exact Policy Recovery in Offline RL with Both Heavy-Tailed Rewards and Data Corruption that it is possible to recover the exact optimal policy. Their insight is that as long as the corruption or tail-noise is smaller than the "action gap" (the difference in value between the best and second-best action), a robust "trimmed-mean" estimator can effectively ignore the mess.

The Cost of Robustness

There is no free lunch. Achieving robustness often requires a trade-off in performance. Anmol Kagrecha, Jayakrishnan Nair 0001, and Krishna P. Jagannathan demonstrate in Bandit algorithms: Letting go of logarithmic regret for statistical robustness that algorithms guaranteeing the standard "logarithmic regret" are inherently fragile. To be truly distribution-oblivious and robust to heavy tails, we must often accept slightly higher, super-logarithmic regret.

This trade-off highlights the fundamental shift in this research direction: moving away from "optimism in the face of uncertainty" toward a more cautious, "robustness in the face of volatility." By explicitly modeling the heavy-tailed nature of rewards—as seen in the work of Chenlu Ye on Catoni Contextual Bandits—modern agents can finally distinguish between a truly high-performing strategy and a rare, deceptive outlier.

Papers in this version

Showing 60 of 231 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 227 papers
  2. Version 1 · 2026-10-04 · 231 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_heavy_tailed_reward_distributions_905866ea,
  title = {heavy-tailed reward distributions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/heavy-tailed-reward-distributions/rdr_905866ea97a34ac796156ea1d2a84bff},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_robust_reinforcement_learning_for_heavy__905866ea_v1,
  title = {Robust Reinforcement Learning for Heavy Tailed Rewards},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-reinforcement-learning-for-heavy-tailed-rewards/rdr_905866ea97a34ac796156ea1d2a84bff/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}