Prioritized Experience Replay
Replay transitions in proportion to how surprising they are, so the agent learns fastest from its biggest errors.
Not all experience is equal
Uniform experience replay samples past transitions with equal probability. But some transitions carry far more learning signal than others. Prioritized experience replay (PER) samples in proportion to a measure of surprise, the magnitude of the temporal-difference (TD) error, so informative transitions are revisited more often.
Priorities from TD error
Each transition's priority is p = |TD error| + epsilon, with a small epsilon so nothing has zero chance. The sampling probability is P(i) proportional to p_i^alpha, where alpha in [0,1] interpolates between uniform (alpha = 0) and greedy prioritization (alpha = 1). A sum-tree data structure makes proportional sampling and priority updates efficient at scale.
# proportional variant
P_i = (priority_i ** alpha) / sum(priority_j ** alpha for j)
# importance-sampling weight to correct the bias
w_i = (1 / (N * P_i)) ** beta
w_i /= max_w # normalize for stabilityCorrecting the bias
Non-uniform sampling biases the expected update, so PER multiplies each update by an importance-sampling weight w = (1/(N P))^beta. beta is annealed from a small value toward 1 over training, fully correcting the bias by the end when accurate estimates matter most. Priorities are refreshed with the latest TD error each time a transition is used.
Effect and caveats
- Faster learning: high-error transitions drive most of the improvement
- Noise sensitivity: in stochastic environments large TD errors may be irreducible noise, not learning signal
- Stale priorities: transitions not recently sampled keep outdated priorities
PER was one of the largest single contributors in the Rainbow ablation. It is broadly applicable to any off-policy method with a replay buffer, and its combination with n-step returns and distributional targets is now standard practice.