Revisiting Prioritized Experience Replay: A Value Perspective

Ang A. Li, Zongqing Lu, Chenglin Miao

Abstract

Experience replay enables off-policy reinforcement learning (RL) agents to utilize past experiences to maximize the cumulative reward. Prioritized experience replay that weighs experiences by the magnitude of their temporal-difference error ($|\text{TD}|$) significantly improves the learning efficiency. But how $|\text{TD}|$ is related to the importance of experience is not well understood. We address this problem from an economic perspective, by linking $|\text{TD}|$ to value of experience, which is defined as the value added to the cumulative reward by accessing the experience. We theoretically show the value metrics of experience are upper-bounded by $|\text{TD}|$ for Q-learning. Furthermore, we successfully extend our theoretical framework to maximum-entropy RL by deriving the lower and upper bounds of these value metrics for soft Q-learning, which turn out to be the product of $|\text{TD}|$ and "on-policyness" of the experiences. Our framework links two important quantities in RL: $|\text{TD}|$ and value of experience. We empirically show that the bounds hold in practice, and experience replay using the upper bound as priority improves maximum-entropy RL in Atari games.

Introduction

In reinforcement learning (RL), "experience replay" allows agents to learn from past transitions stored in a buffer, breaking temporal correlations and improving sample efficiency. Since not all memories are equally useful, Prioritized Experience Replay (PER) was developed to sample transitions with high $|\text{TD}|$ errors more frequently. While PER is a staple of modern deep RL, the community has largely treated $|\text{TD}|$ as a useful heuristic rather than a theoretically grounded metric for "importance."

This paper asks a fundamental question: Why is $|\text{TD}|$ the right metric? By approaching this from an economic perspective, the authors define the "value of experience" as the actual increase in expected cumulative reward an agent gains after updating its policy based on a specific transition. This work bridges the gap between this first-principles definition of value and the common practice of using $|\text{TD}|$ errors.

Theoretical Framework: Defining the Value of Experience

The researchers decompose the "value of experience" into three distinct metrics that capture different aspects of learning:

  1. Expected Value of Backup (EVB): The total utility gained from an update.
  2. Policy Improvement Value (PIV): Gains specifically from changing the agent's actions.
  3. Evaluation Improvement Value (EIV): Gains from more accurately estimating the value of current actions.

The Bound for Q-Learning

A key contribution is the mathematical proof that in standard Q-learning, all three value metrics are upper-bounded by $\alpha|\text{TD}|$ (where $\alpha$ is the learning rate). This confirms that $|\text{TD}|$ is not just a measure of surprise, but a rigorous proxy for the potential reward gain.

Extension to Maximum-Entropy RL

The framework is extended to "Soft Q-learning" (Max-Ent RL). In this setting, $|\text{TD}|$ alone is found to be a loose bound. The authors derive a tighter bound: the product of $|\text{TD}|$ and a term called "on-policyness" ($\rho_\pi$). This term measures how likely the agent is to actually take the action described in the experience. Based on this, they propose Valuable Experience Replay (VER), which uses these tighter theoretical upper bounds as the priority for sampling.

Key Insights: TD vs. Value

The core insight of this research is the proof that $|\text{TD}|$ is a measure of potential improvement. However, $|\text{TD}|$ can be "distracted" by updates to non-optimal paths. In a Linear Grid-World example, $|\text{TD}|$ might prioritize updates for actions that do not lead to the goal, whereas the Value of Experience (EVB) correctly prioritizes only the transitions that contribute to the objective.

Figure 1: (a-c) Comparison of prioritization strategies in a Linear GridWorld. While TD-based prioritization spreads updates, EVB-based prioritization focuses on the path to the goal. (d) Efficiency comparison showing that value-based replay requires significantly fewer replays to reach a performance threshold as the environment size N increases.

Empirical Validation and Results

The authors validated their theory across three tiers of complexity: toy grid-worlds, classic control (CartPole), and 9 diverse Atari 2600 games.

Theoretical Bounds in Practice

Experimental scatter plots confirm that the value metrics in both tabular and deep RL stay strictly below the identity line of the proposed $|\text{TD}|$-based bounds. This empirical evidence supports the theoretical claim that $|\text{TD}|$ acts as a reliable upper bound for the value of experience.

Figure 2: Empirical validation of the theoretical bounds. Scatter plots of |EVB|, |EIV|, and |PIV| against |TD| show that the value metrics are consistently upper-bounded by the magnitude of the TD error, as they all fall below the red identity line.

Performance and Efficiency

In Atari games, VER outperformed standard PER by an average of 8.47% and outperformed vanilla Soft DQN (uniform replay) by 18.0%. Furthermore, VER showed higher convergence speeds in most games, suggesting that a tighter bound on experience value leads to more sample-efficient learning. By incorporating "on-policyness," VER avoids wasting time on highly surprising but irrelevant "outlier" experiences.

Conclusion

This work provides a long-overdue theoretical justification for Prioritized Experience Replay. By linking $|\text{TD}|$ to the economic value of an experience, the authors transform a heuristic into a grounded principle. The resulting VER algorithm demonstrates that tighter theoretical bounds can lead to tangible improvements in the performance and efficiency of modern reinforcement learning agents.

Summary updated

Abstract

Experience replay enables off-policy reinforcement learning (RL) agents to utilize past experiences to maximize the cumulative reward. Prioritized experience replay that weighs experiences by the magnitude of their temporal-difference error ($|\text{TD}|$) significantly improves the learning efficiency. But how $|\text{TD}|$ is related to the importance of experience is not well understood. We address this problem from an economic perspective, by linking $|\text{TD}|$ to value of experience, which is defined as the value added to the cumulative reward by accessing the experience. We theoretically show the value metrics of experience are upper-bounded by $|\text{TD}|$ for Q-learning. Furthermore, we successfully extend our theoretical framework to maximum-entropy RL by deriving the lower and upper bounds of these value metrics for soft Q-learning, which turn out to be the product of $|\text{TD}|$ and "on-policyness" of the experiences. Our framework links two important quantities in RL: $|\text{TD}|$ and value of experience. We empirically show that the bounds hold in practice, and experience replay using the upper bound as priority improves maximum-entropy RL in Atari games.
BibTeX
@misc{li2021revisiting,
  author = {Ang A. Li and Zongqing Lu and Chenglin Miao},
  title = {{Revisiting Prioritized Experience Replay: A Value Perspective}},
  year = {2021},
  eprint = {2102.03261},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.03261},
}
Figure