Prioritized Experience Replay

The core mechanism of PER is sampling transitions with probability proportional to the absolute TD error. A high TD error indicates the agent's value estimate was significantly wrong, representing a high-learning opportunity. The sampling probability is defined as:

• P(i) = p_i^α / Σ_k p_k^α
• p_i is the priority (typically |δ_i| + ε)
• α controls the degree of prioritization (0 = uniform, 1 = full prioritization)
• ε is a small positive constant preventing zero-probability transitions

Prioritized sampling introduces bias because the data distribution no longer matches the true environment distribution. PER corrects this with importance sampling weights:

• w_i = (1/N · 1/P(i))^β
• β anneals from an initial value (e.g., 0.4) to 1 over training
• When β = 1, the bias is fully compensated
• Weights are typically normalized by max_j w_j for stability
• This correction ensures the Q-learning updates remain unbiased in expectation

Efficient sampling requires O(log N) complexity rather than O(N) linear scans. PER implementations use a SumTree binary tree structure:

• Leaf nodes store transition priorities
• Parent nodes store the sum of child priorities
• Sampling: generate a random value, traverse tree by comparing to cumulative sums
• Updates: modify leaf priority and propagate sum changes upward
• This enables efficient proportional sampling at scale with millions of transitions

The hyperparameter α controls the shape of the sampling distribution. Best practices include:

• Start with α = 0 (uniform sampling) during early exploration
• Linearly anneal α toward a final value (e.g., 0.6–0.8) as training progresses
• High α too early can cause overfitting to noise in the value function
• The β parameter for importance sampling should anneal simultaneously toward 1.0
• This dual annealing schedule balances exploration stability with focused learning

New transitions entering the replay buffer have no prior TD error. Strategies for assigning initial priority include:

• Maximum priority: assign the highest current priority to ensure new experiences are sampled at least once
• Optimistic initialization: set initial priority to a high constant value
• This guarantees that every transition is replayed at least once before being potentially forgotten
• Without this, newly observed rare events might never be sampled before being evicted from the buffer

Two primary variants of PER exist:

• Proportional prioritization: p_i = |δ_i| + ε, directly proportional to TD error magnitude
• Rank-based prioritization: p_i = 1 / rank(i), where rank is sorted by |δ_i|
• Rank-based is more robust to outliers because it ignores the scale of TD errors
• Proportional is more theoretically grounded but sensitive to noise spikes
• Both significantly outperform uniform sampling across Atari and continuous control benchmarks

The TD-error is the primary signal used to assign priority. It measures the difference between the current Q-value estimate and the updated target value (observed reward plus discounted future value). A high-magnitude TD-error indicates a surprising transition where the agent's prediction was significantly wrong, marking it as high-priority for replay. This focuses learning on the most information-rich experiences.

To avoid brittle overfitting to a small subset of high-error transitions, PER uses stochastic sampling. The probability of sampling a transition i is proportional to its priority raised to a power α: P(i) = p_i^α / Σ_k p_k^α. This introduces controlled randomness, ensuring that even low-error transitions have a non-zero chance of being replayed, preserving experience diversity and preventing catastrophic forgetting.

Prioritized replay introduces bias because it distorts the original data distribution. To correct this, PER applies importance-sampling (IS) weights during the Q-learning update: w_i = (1/N * 1/P(i))^β. A hyperparameter β is annealed from a low value to 1.0 over training. This ensures updates are unbiased when β=1, maintaining the theoretical guarantees of the Bellman equation.

Efficient sampling from a non-uniform distribution requires a specialized data structure. A SumTree is a binary tree where leaf nodes store transition priorities and parent nodes store the sum of their children. This allows for O(log N) sampling and priority updates. The total priority sum is at the root, enabling efficient proportional sampling by generating a random number and traversing the tree.

The canonical algorithm where PER was first demonstrated. A DQN uses a deep neural network to approximate the optimal action-value function Q*(s,a). PER was shown to dramatically improve DQN performance on Atari benchmarks by focusing replay on high-surprise transitions. In trading, a DQN with PER can learn to identify critical market regime shifts faster than uniform sampling.