Prioritized Experience Replay

Prioritized Experience Replay (PER) is an improvement to DQN's replay buffer that samples transitions proportionally to their temporal difference (TD) error — focusing replay on the most surprising, informative transitions rather than sampling uniformly.

PER Mechanism

• Priority: $p_i = |\delta_i| + \epsilon$ where $\delta_i$ is the TD error — higher error = higher priority.
• Sampling: $P(i) = p_i^\alpha / \sum_j p_j^\alpha$ — $\alpha$ controls prioritization strength (0 = uniform, 1 = fully prioritized).
• Importance Sampling: Weight updates by $w_i = (N \cdot P(i))^{-\beta}$ to correct for the non-uniform sampling bias.
• SumTree: Efficient implementation using a sum tree data structure for $O(\log N)$ priority-based sampling.

Why It Matters

• Efficient Learning: Replaying informative transitions accelerates learning — no time wasted on already-learned transitions.
• 3-5× Speedup: PER typically improves DQN convergence speed by 3-5×.
• Rare Events: Rare but important transitions (like rewards) are replayed more frequently.

PER is replay what surprised you — prioritizing the most informative experiences for efficient reinforcement learning.