An Equivalence between Loss Functions and Non-Uniform Sampling in Experience Replay

Scott Fujimoto, David Meger, Doina Precup

Summary

This paper reveals a fundamental mathematical equivalence in reinforcement learning: sampling data non-uniformly (prioritization) is effectively the same as changing your loss function while sampling uniformly. Leveraging this insight, the authors introduce LAP and PAL, two methods that simplify and improve upon the industry-standard Prioritized Experience Replay (PER) by eliminating bias and reducing gradient variance.

The Problem with Prioritized Experience Replay

In Deep Reinforcement Learning (DRL), agents learn from a "replay buffer" of past experiences. Since its introduction in 2015, Prioritized Experience Replay (PER) has been a common practice. It samples "surprising" transitions—those with high Temporal-Difference (TD) error—more frequently to speed up learning.

However, PER suffers from two major issues:

  1. Theoretical Gap: While intuitive, it lacks a solid theoretical foundation. It often requires complex "Importance Sampling" (IS) weights to correct for the bias it introduces into the learning updates.
  2. Empirical Failure in Continuous Control: In continuous control tasks (like those in the MuJoCo simulator), PER often performs poorly or even degrades performance. It tends to over-prioritize outliers, leading to unstable gradients and erratic learning.

The authors set out to understand the mathematical relationship between how we sample data and the objective function we are actually optimizing.

A Mathematical Equivalence and New Methods

The paper’s core contribution proves that for any loss function used with non-uniform sampling, there exists an equivalent loss function that produces the same "expected gradient" when used with uniform sampling.

Based on this equivalence, they propose two new approaches:

  • Loss-Adjusted Prioritized (LAP) Experience Replay: A "corrected" version of PER. It uses a Huber loss, clips priorities to a minimum of 1 (to prevent transitions from "dying" with zero probability), and entirely removes the need for complex importance sampling ratios.
  • Prioritized Approximation Loss (PAL): The uniform-sampling twin of LAP. Instead of changing how you sample, you simply change the loss function to a modified version of the Huber loss. This allows you to get the benefits of prioritization with just a few lines of code, bypassing the computational overhead of a prioritized data structure.

Key Insights: The "Outlier" Trap

The authors show that using PER with standard Mean Squared Error (MSE) is mathematically equivalent to optimizing a loss function raised to a power higher than 2. This explains why PER struggles in noisy environments—it effectively "overfits" to the most extreme outliers.

Furthermore, they prove that the L1 loss, combined with a specific prioritization scheme, provides the lowest possible variance for the gradient. This provides a principled "recipe" for designing future RL algorithms with optimal variance reduction.

Empirical Results

The authors evaluated their methods on two standard benchmarks: the MuJoCo suite of continuous control tasks and Atari 2600 discrete-action games.

MuJoCo Mastery

In MuJoCo environments, the authors found that LAP (sampling-based) and PAL (loss-based) performed almost identically. This suggests that the benefit of PER in these tasks isn't actually the sampling—it’s the change in the gradient direction. You can achieve the same performance boost just by changing your loss function and sampling uniformly.

MuJoCo learning curves comparing TD3, SAC, and new methods.

Notably, in the "Humanoid" task (widely considered the hardest MuJoCo benchmark), both LAP and PAL significantly outperformed state-of-the-art algorithms like TD3 and SAC. PAL achieved a score of ~8265 compared to TD3’s ~6437.

Atari Gains

In the Atari domain, LAP demonstrated substantial improvements over standard baselines.

Atari performance improvements of LAP and PAL versus baselines.

LAP improved upon the standard PER+Double DQN setup in 9 out of 10 games, yielding a mean performance gain of 53%. Because PAL is just a loss function, it is much easier to implement and computationally cheaper than PER, yet it matches or exceeds PER's performance in many scenarios.

Limitations and Future Directions

  • Domain Differences: While the loss-function change (PAL) was sufficient for MuJoCo, prioritization (LAP) still showed a distinct advantage in Atari games. The authors attribute this to Atari's "sparse rewards" and "long horizons," where actually seeing rare, high-error transitions more frequently is still physically necessary for discovery.
  • Fixed Priority Schemes: The paper focuses on TD-error as the basis for priority. Future work could explore if this "equivalence" holds for other types of prioritization, such as those based on the age of the transition or the agent's state distribution.
  • Hyperparameter Sensitivity: Although LAP and PAL simplify the learning process, they still introduce an $\alpha$ hyperparameter (to control the strength of prioritization) that may require tuning for different environments.

Summary updated

Abstract

Prioritized Experience Replay (PER) is a deep reinforcement learning technique in which agents learn from transitions sampled with non-uniform probability proportionate to their temporal-difference error. We show that any loss function evaluated with non-uniformly sampled data can be transformed into another uniformly sampled loss function with the same expected gradient. Surprisingly, we find in some environments PER can be replaced entirely by this new loss function without impact to empirical performance. Furthermore, this relationship suggests a new branch of improvements to PER by correcting its uniformly sampled loss function equivalent. We demonstrate the effectiveness of our proposed modifications to PER and the equivalent loss function in several MuJoCo and Atari environments.
BibTeX
@inproceedings{fujimoto2020equivalence,
  author = {Scott Fujimoto and David Meger and Doina Precup},
  title = {{An Equivalence between Loss Functions and Non-Uniform Sampling in Experience Replay}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=NnLiITzQQ2r},
}
Figure