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

Scott Fujimoto, David Meger, Doina Precup

This research, presented at NeurIPS 2020 by Scott Fujimoto and colleagues, establishes a rigorous theoretical bridge between two fundamental components of deep reinforcement learning: the loss function used for error calculation and the sampling strategy used to select training data.

The Core Problem

Prioritized Experience Replay (PER) is a staple technique in reinforcement learning where transitions with higher temporal difference (TD) errors are sampled more frequently. While effective, PER suffers from two significant issues:

  1. Theoretical Inconsistency: It is largely heuristic. When combined with standard Mean Squared Error (MSE) loss, it can inadvertently bias agents toward outliers, which is particularly detrimental in continuous control tasks.
  2. Computational Overhead: Implementing PER requires complex data structures like sum-trees, which can significantly increase training time.

The authors sought to determine if the benefits of prioritization could be achieved more simply and correctly by re-evaluating the relationship between sampling and the optimization objective.

Theoretical Framework

The paper's primary contribution is Theorem 1, which proves that for any loss function evaluated with non-uniform sampling, there exists a corresponding loss function that, when evaluated with uniform sampling, produces the exact same expected gradient. This equivalence suggests that the "act" of prioritization is mathematically interchangeable with a specific modification of the loss function.

Mathematical equivalence between expected gradients under different sampling distributions.

Key insights from this theory include:

  • Prioritization as Variance Reduction: The primary benefit of non-uniform sampling is reducing gradient variance. The authors prove that using an L1 loss with prioritization is the mathematically optimal way to minimize this variance.
  • The Outlier Bias: Standard PER with MSE loss effectively optimizes the error to a power higher than two, causing agents to fixate on noisy outliers in continuous control environments.

Proposed Methods: LAP and PAL

Based on their theoretical findings, the authors introduced two new approaches:

  • LAP (Loss-Adjusted Prioritized): A corrected version of PER that utilizes a Huber loss, removes unnecessary importance sampling ratios, and clips priorities to ensure all transitions maintain a non-zero probability of being sampled.
  • PAL (Prioritized Approximation Loss): A standalone loss function used with uniform sampling. It acts as a mirrored version of LAP, resembling a weighted Huber loss where high-error transitions are emphasized. This provides the benefits of prioritization without the need for complex sampling machinery.

Empirical Evaluation and Results

The methods were tested on standard benchmarks: MuJoCo (continuous control) and Atari 2600 (discrete actions).

MuJoCo Benchmarks

In continuous control tasks, adding PAL or LAP to the TD3 algorithm consistently outperformed vanilla TD3 and SAC. On the challenging "Humanoid" task, PAL achieved a score of ~8265 compared to TD3’s ~6437. Notably, there was no meaningful performance difference between LAP (prioritized) and PAL (uniform) in these environments, confirming that the complex machinery of prioritized sampling is often unnecessary if the loss function is correctly specified.

Performance of TD3 with LAP and PAL compared to baselines on MuJoCo benchmarks.

Atari Gains

In discrete environments, LAP improved upon standard PER in 9 out of 10 games, yielding a mean performance gain of 53%. However, in games with sparse rewards, the authors found that prioritization (LAP) still outperformed the uniform equivalent (PAL). This suggests that in specific scenarios, the physical act of sampling rare, successful events more frequently provides benefits beyond just the expected gradient.

Conclusion

By proving the equivalence between sampling and loss functions, this work simplifies the reinforcement learning pipeline. For many tasks, researchers can replace computationally expensive prioritized sampling with the PAL loss function and uniform sampling, achieving superior performance with less complexity. For cases where prioritization remains necessary, LAP provides a theoretically grounded and more robust alternative to standard PER.

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