Course contentsShow
← Machine Learning and Deep Learning
Lesson 2228 of 3,53848. Deep Reinforcement Learning: Value-BasedFree lesson

Prioritized Experience Replay: Implementation

Sum-tree data structures, importance sampling weights, and bias correction for prioritized replay.

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:

  1. Pick a random value between 0 and the root's total priority
  2. Navigate down: if the value exceeds the left child's sum, go right (subtracting left sum); otherwise go left
  3. 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))^(-β) where P(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.