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 / ∑_j p_j^alpha — alpha controls prioritization strength (0 = uniform, 1 = fully prioritized).
• Importance Sampling: Weight updates by w_i = (N · 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.