Robust Learning with Heavy Tailed Reward Distributions

353 concepts206 papers2 proposals

Standard multi-armed bandit and reinforcement learning algorithms rely on a comfortable mathematical fiction: the assumption that reward noise is sub-Gaussian or strictly bounded (Abbasi-Yadkori et al.). In this idealized world, the probability of encountering an extreme event decays exponentially, making the empirical mean a highly efficient and reliable estimator of an action's true value.

In real-world domains such as financial markets, web traffic, and network routing, this assumption breaks down completely. Rewards in these environments frequently exhibit heavy tails—such as power-law or $\alpha$-stable distributions—where extreme outliers occur with disruptive frequency and variance may be infinite (Dubey et al.; Tao et al.). When algorithms optimized for light-tailed noise encounter these distributions, their core engine—the exploration-exploitation balance—fails catastrophically.

The Fragility of the Empirical Mean

To understand why heavy tails break standard sequential decision-making, consider how an algorithm like Upper Confidence Bound (UCB) or Thompson Sampling operates. These algorithms maintain an estimate of each action's expected reward alongside a confidence interval that shrinks as more samples are gathered.

When an action yields a massive, heavy-tailed outlier, a standard empirical mean estimator spikes violently. Because the algorithm assumes sub-Gaussian noise, it interprets this spike as evidence of a genuinely high-performing action rather than a rare, low-probability anomaly (Dubey et al.). The agent becomes trapped, repeatedly exploiting a suboptimal choice based on a single distorted observation, which leads to linear regret.

In reinforcement learning (RL), this sensitivity propagates through Bellman updates. A single extreme reward outlier can permanently distort the value estimation of an entire sequence of states. As a result, Zhuang et al. and Han Zhong et al. demonstrate that heavy-tailed rewards fundamentally invert the complexity of RL. In standard settings, the primary bottleneck is mapping the environment's transition dynamics. In heavy-tailed settings, accurately filtering reward noise becomes the dominant driver of regret, rendering traditional transition-centric models insufficient.

Relaxing the Assumptions

To design algorithms capable of surviving heavy-tailed environments, researchers relax the requirement for exponential tail decay. Instead of assuming finite variance or a well-behaved moment-generating function, they assume only that a lower-order moment exists—specifically, a bounded $(1+\epsilon)$-th moment for some $\epsilon \in (0, 1]$ (Lee et al.; Juneja et al.).

Sub-Gaussian Noise (Standard)      Heavy-Tailed Noise (Real-World)
       |      .---.                       |          |
       |     /     \                      |          |
       |    /       \                     |         / \
_______|___/_________\_______      _______|________/   \________
       |  Exponential Decay               |     Heavy Tails 
       |  (Outliers impossible)           |     (Outliers frequent)

This minimal assumption accommodates distributions with infinite variance while providing just enough mathematical structure to guarantee convergence. The challenge then shifts to replacing the fragile empirical mean with robust statistical estimators that can extract the true signal from a stream of highly volatile data.

The Mechanics of Robust Estimation

The core strategy in heavy-tailed bandit and RL literature is to process incoming rewards through a mathematical filter that dampens or discards outliers before updating the agent's policy. Three primary mechanisms drive this robustness:

1. Median-of-Means (MoM)

The Median-of-Means estimator bypasses outliers by leveraging a simple geometric truth: while an outlier can easily corrupt a mean, it cannot easily shift a median.

To estimate the value of an action, the agent divides its collected reward observations into $k$ distinct blocks. It calculates the standard empirical mean for each individual block, and then takes the median of those block means.

$$\hat{\mu}_{\text{MoM}} = \text{median}\left( \bar{X}_1, \bar{X}_2, \dots, \bar{X}_k \right)$$

If a massive outlier occurs, it can completely ruin the average of the specific block it lands in. However, it can only corrupt that single block. As long as extreme outliers are sparse enough that they do not contaminate more than half of the blocks, the median of the blocks remains completely unaffected. This technique allows algorithms like those analyzed by Yang and Zhu et al. to maintain stable value estimates and enforce reliable pessimism in offline reinforcement learning.

2. Truncation and Trimmed Means

An alternative approach is to explicitly censor the incoming data stream. Under dynamic truncation, any observed reward that exceeds a time-varying threshold is capped (Yang; Yu et al.). As the agent gathers more samples, the truncation threshold expands, allowing the agent to learn the true mean asymptotically while shielding it from early, catastrophic outliers.

Similarly, a trimmed mean estimator sorts the collected rewards and discards a fixed percentage of the highest and lowest observations before calculating the average (Chen et al.; Genalti et al.). By slicing off the wild tails of the empirical distribution, the remaining data behaves as if it were bounded, restoring the validity of standard concentration inequalities and confidence intervals.

3. Adaptive Huber Regression

For complex environments that require function approximation (such as linear or generalized linear bandits), simple block-sorting or data-dropping becomes mathematically intractable. In these settings, researchers replace ordinary least-squares regression with Huber regression (Huang et al.; Li et al.).

The Huber loss function acts quadratically for small errors, treating them like standard Gaussian noise. However, for errors that exceed a certain threshold, the loss transitions to a linear penalty:

$$\mathcal{L}_{\delta}(e) = \begin{cases} \frac{1}{2}e^2 & \text{for } |e| \le \delta \\ \delta(|e| - \frac{1}{2}\delta) & \text{for } |e| > \delta \end{cases}$$

By penalizing large errors linearly rather than quadratically, Huber regression drastically dampens the gradient updates caused by extreme outliers. By adaptively tuning the threshold $\delta$ over time, agents achieve "variance-aware" regret bounds that scale with the actual underlying noise of the environment rather than worst-case limits.

Shifting the Optimization Target

When the heavy-tailed nature of an environment is exceptionally severe, the expected value (mean) of a reward distribution may be highly volatile or mathematically undefined. In these scenarios, the research direction pivots away from mean estimation entirely.

Instead of forcing the agent to maximize an unstable average, frameworks such as those proposed by Jiang et al. introduce quantile-based policy optimization. By shifting the target to specific risk-adjusted quantiles or modes, the agent optimizes for predictable performance targets, ensuring stable policy updates even when the underlying reward distribution possesses infinite variance.

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 2, frozen text):

@misc{lacuna_heavy_tailed_reward_distributions_905866ea_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake