Prioritized Experience Replay (PER)

The core innovation of PER is using the absolute Temporal-Difference (TD) error as a proxy for an experience's learning potential. A high TD error indicates the agent's current value estimate was significantly wrong, making that transition more informative for an update.

• Priority Calculation: For a transition (s, a, r, s'), priority p = |δ| + ε, where δ is the TD error and ε is a small positive constant to ensure all transitions have a non-zero chance of being sampled.
• Dynamic Updates: After a transition is sampled and its Q-values are updated, its TD error is recalculated and its priority is updated in the buffer, ensuring the sampling distribution reflects the agent's current knowledge gaps.

Pure greedy selection based on the highest TD error is problematic—it focuses on a small set of experiences, is sensitive to noise, and reduces diversity. PER uses stochastic prioritization to balance priority with randomness.

• Sampling Probability: The probability of sampling transition i is P(i) = p_i^α / Σ_k p_k^α, where p_i is the priority and α is a hyperparameter controlling the prioritization strength (α=0 yields uniform random sampling).
• Annealing Alpha: In practice, α is often annealed from an initial value (e.g., 0.6) down to 0 over training, starting with more focused learning and ending with more uniform sampling for convergence stability.

Prioritized sampling introduces a bias because it changes the expected distribution of updates. To correct this and ensure convergence, PER employs importance sampling (IS) weights.

• Weight Calculation: The IS weight for transition i is w_i = (1/N * 1/P(i))^β, normalized by the maximum weight in the batch to scale the update. β is annealed from an initial value (e.g., 0.4) to 1 over training.
• Bias-Variance Trade-off: The β parameter controls the correction's strength. A low β does less correction (higher bias, lower variance), while β=1 fully corrects the bias. Annealing β to 1 gradually shifts the focus from fast initial learning (biased) to stable convergence (unbiased).

Efficient sampling proportional to priority is non-trivial for large buffers. PER is implemented using a SumTree (a binary heap variant), enabling O(log N) sampling and update operations.

• Structure: Each leaf node stores a transition's priority. Each internal node stores the sum of its children's priorities. The root contains the total sum of all priorities.
• Sampling: To sample, a value is drawn uniformly from [0, total_sum). The tree is traversed from root to leaf by comparing the value to node sums, efficiently finding the corresponding transition.
• Update: After a priority change, the leaf node and all its ancestor sums are updated, maintaining O(log N) efficiency.

PER introduces key hyperparameters that interact with the core RL algorithm:

• Priority Exponent (α): Controls prioritization intensity. High α accelerates learning early but can lead to instability or plateaus later.
• Importance Sampling Exponent (β): Controls bias correction. Must be annealed in tandem with α for stable convergence.
• Replay Ratio: PER often allows a higher replay ratio (more updates per new experience) because each sampled batch is more informative, improving sample efficiency.
• Buffer Size Interaction: In large buffers, very old experiences may have stale, low priorities and are rarely revisited, effectively creating a sliding window of relevant experiences.

PER is not algorithm-specific and has been successfully integrated into many advanced architectures:

• Rainbow DQN: PER is one of six components in the Rainbow agent, combining with Distributional RL, Multi-step learning (n-step returns), and others.
• Soft Actor-Critic (SAC): Modern implementations often use PER with the absolute TD error from the critic networks to accelerate off-policy learning in continuous action spaces.
• Model-Based RL: In algorithms like MuZero, PER is applied to sequences of real trajectories stored in the replay buffer, prioritizing sequences where the model's predictions were inaccurate.
• Continual Learning: Variants of PER are used in Gradient Episodic Memory (GEM) to prioritize replay of examples critical for mitigating catastrophic forgetting.

Efficient sampling from a discrete distribution over millions of experiences is enabled by a SumTree (a binary segment tree).

• Structure: A binary tree where each leaf node stores the priority of an experience, and each internal node stores the sum of its children's values.
• Sampling (O(log N)): To sample, a random value s is generated up to the total sum (root node). The tree is traversed from root to leaf by comparing s to the left child's sum, selecting the corresponding leaf.
• Update (O(log N)): When a TD error is updated for a leaf, the change is propagated up the tree to the root. This makes PER computationally efficient despite the dynamic priorities.

While pioneered for discrete-action DQN, PER is effectively adapted to actor-critic methods for continuous control like DDPG and SAC.

• Priority Metric: For actor-critic methods, the priority is typically the absolute TD error from the Q-function (critic) update: p = |Q(s,a) - (r + γ Q(s',a'))|.
• Impact: Dramatically improves sample efficiency in sparse-reward or complex physics environments (e.g., MuJoCo, PyBullet). The agent replays rare successful transitions or large prediction errors more often, accelerating policy refinement.
• Implementation Note: The experience tuple must store (s, a, r, s', d) and its associated priority, which is updated after each Q-function learning step.

Successful PER deployment requires careful tuning of key hyperparameters:

• α (Priority Exponent): Controls prioritization intensity. Typical range: [0.4, 0.7]. Higher α gives more aggressive prioritization.
• β (IS Exponent): Controls bias correction. Annealed from ~0.4-0.6 to 1.0 over the course of training (e.g., 1M steps).
• ε (Small Constant): Prevents zero priority for unseen transitions. A small value like 1e-6.
• Replay Ratio: The number of gradient updates per environment step. PER often allows for a higher replay ratio (e.g., 4-8) as it selects more informative batches.
• Buffer Size: Remains critical. Too small a buffer loses diverse old experiences; too large can slow priority updates.

An Experience Replay Buffer is the foundational data structure that stores past experiences (state, action, reward, next state) as transition tuples. It decouples the data generation process (acting in the environment) from the learning process (updating the model).

• Core Function: Breaks harmful temporal correlations in sequential data by randomly sampling old experiences.
• Implementation: Typically a circular buffer (FIFO) with a fixed buffer capacity.
• Key Parameter: The replay ratio determines how many times, on average, a stored experience is reused for training.

Temporal-Difference Error is the scalar signal used by PER to assign priority. It quantifies how "surprising" or incorrect the agent's current value estimate was for a given transition.

• Calculation: δ = r + γ * V(s') - V(s), where r is reward, γ is discount factor, and V is the value estimate.
• Role in PER: Transitions with a larger absolute TD error are sampled with higher probability, focusing learning on poorly understood parts of the environment.
• Dynamic: The TD error for each transition is recalculated every time it is sampled, as the agent's value estimates improve.

Importance Sampling is the statistical correction applied in PER to counteract the bias introduced by non-uniform sampling. Without it, the agent's updates would be skewed toward high-priority experiences.

• Problem: Sampling by priority changes the expected distribution of data, biasing gradient updates.
• Solution: Each gradient is weighted by (1 / P(i))^β, where P(i) is the sampling probability and β is a hyperparameter annealed from 0 to 1.
• Effect: Ensures the update is unbiased relative to uniform sampling, preserving convergence guarantees in expectation.

Hindsight Experience Replay is a complementary technique for goal-conditioned reinforcement learning. It repurposes failures as successful learning experiences by relabeling past transitions with alternative goals.

• Mechanism: After an episode, transitions are stored a second time with the actually achieved final state as the goal, not the original intended goal.
• Synergy with PER: HER can be combined with PER, where the priority of a hindsight-relabeled transition is based on its TD error with respect to the new goal.
• Primary Use: Drastically improves sample efficiency in sparse-reward environments where the original goal is rarely achieved.

The Deep Q-Network algorithm is the canonical application that popularized experience replay for stabilizing deep reinforcement learning. The original DQN used a uniform replay buffer.

• Historical Context: PER was introduced as a direct enhancement to the DQN architecture, replacing uniform sampling with prioritized sampling.
• Key Components: DQN combines a replay buffer with a target network (a periodically updated copy of the Q-network) to further stabilize training.
• Foundation: Understanding DQN is essential to grasp the performance improvements and implementation details of PER.

Multi-Step Learning generalizes Temporal-Difference learning by looking ahead more than one step to compute a target value. It is often integrated with PER for improved credit assignment.

• n-step return: G_t = r_t + γ * r_{t+1} + ... + γ^{n-1} * r_{t+n-1} + γ^n * V(s_{t+n}).
• Integration with PER: The TD error used for prioritization can be calculated using these multi-step returns, providing a richer, less biased learning signal.
• Trade-off: Increases bias (compared to Monte Carlo) but reduces variance (compared to 1-step TD), often leading to faster learning when combined with prioritization.