Prioritized Experience Replay: Implementation
What you'll learn: How to efficiently implement prioritized sampling using sum-tree data structures, importance sampling weights, and bias correction.
The Implementation Challenge
You've learned why prioritized replay helps (concept 2227), but naive implementation is slow—searching for high-priority samples in a large buffer takes O(n) time per sample. The solution? A sum-tree data structure that enables O(log n) sampling.
Sum-Tree: The Core Data Structure
A sum-tree is a binary tree where:
- Leaf nodes store transition priorities
- Parent nodes store the sum of their children's priorities
Think of it like a tournament bracket where each level adds up scores. To sample:
- Pick a random value between 0 and the root's total priority
- Navigate down: if the value exceeds the left child's sum, go right (subtracting left sum); otherwise go left
- Reach a leaf in O(log n) steps—your sampled transition!
Updating a priority also takes O(log n): change the leaf, then propagate sum updates upward to the root.
Importance Sampling Weights
Prioritized replay biases training toward high-TD-error transitions. To correct this bias:
- Each sampled transition gets a weight:
w = (N * P(i))^(-β)whereP(i)is the transition's sampling probability andβcontrols correction strength (0 = no correction, 1 = full correction) - Normalize weights by dividing by
max(w)for stability - Multiply the DQN loss by this weight during backpropagation
Bias Correction Over Training
Start with β ≈ 0.4 (less correction early when priorities are rough) and anneal to β = 1.0 by training end. This balances fast early learning with unbiased convergence.
Key Takeaway: Prioritized replay implementation requires sum-trees for efficient O(log n) sampling and importance sampling weights (N * P(i))^(-β) to correct the introduced bias—without these, you'd have either slow training or biased Q-value estimates.