Prioritized Experience Replay

Replay the transitions that still surprise the network first, using a sum tree to draw them fast and weights that undo the sampling bias.

Four transitions with priorities 1.0, 4.0, 0.5, 2.0 sum to 7.5, so the 4.0 item draws 53.3 percent of samples but its update weight drops to 0.3536

Why Does This Exist?

Uniform replay treats every memory as equal. Each stored transition draws with probability $1 / N$ , where $N$ is the buffer size. Most memories are boring: the car kept its lane, the corridor stayed empty, the TD error sits near zero. A few are gold: the crash, the first goal, the trap door. Those carry large TD errors and the most learning signal, but uniform sampling may revisit them once in tens of thousands of draws while relearning solved transitions all day.

Schaul and coauthors (DeepMind, ICLR 2016) fixed the allocation with Prioritized Experience Replay. Sample proportional to surprise, measured by absolute TD error $\lvert \delta_i \rvert$ , so the network spends its limited minibatches where its predictions are worst. New transitions enter at maximum priority so nothing is skipped unseen. Because skewed sampling biases gradients, each update is multiplied by an importance sampling weight that starts partial and anneals to full correction by late training.

This page covers the sampling rule, the sum tree that makes it fast, and the correction. For the uniform baseline underneath, read experience replay. For the network that consumes these batches, read deep Q-networks.

Think of It Like This

A question box that floats the missed cards to the top

You run exam revision with a box of 1,000 cards. Shuffling uniformly means tonight you redraw the 900 you already know and meet the 12 you keep missing about once a month. Progress crawls.

So you score every card by last error and let the box sort itself. Missed cards float up and get drawn nightly; known cards sink and surface rarely. When a hard card is finally answered cold, its score drops and it sinks on its own. Because nights now overweight the hard cards, you also shrink their marks slightly when grading the mock, or the final score would pretend the whole syllabus is as hard as the worst dozen.

Where it stops: cards sit in discrete piles while PER draws from a continuous distribution $P(i) \propto p_i^\alpha$ through a binary sum tree, and no card box anneals a bias exponent toward 1. The float up plus discount part carries over.

How It Actually Works

A transition is $i = (s_i, a_i, r_i, s_i^{\prime}, d_i)$ with $s$ state, $a$ action, $r$ reward, $s^{\prime}$ next state, $d$ done flag, and $\gamma$ discount. The TD error $\delta_i = r_i + \gamma (1 - d_i) \max_{a^{\prime}} Q(s_i^{\prime}, a^{\prime}) - Q(s_i, a_i)$ says how wrong the current values are. Priority is $p_i = \lvert \delta_i \rvert + \epsilon$ with small $\epsilon$ like $10^{-5}$ so zero error items keep a nonzero chance. Sampling probability is $P(i) = p_i^\alpha / \sum_k p_k^\alpha$ with $\alpha$ in $[0, 1]$ . At $\alpha = 0$ this is uniform; the paper uses $\alpha \approx 0.6$ . Importance weight is $w_i = (N P(i))^{-\beta} / \max_k w_k$ with $\beta$ annealed from about $0.4$ to $1.0$ , and the minibatch loss is the weighted mean of $\delta_i^2$ .

The sum tree in O(log N)

Scanning a million priorities per draw costs $O(N)$ and kills training. The sum tree stores the $N$ values $p_i^\alpha$ as leaves in a flat array of $2N - 1$ nodes, with each parent holding the sum of its children and the root holding the total. To draw one sample, split $[0, p_{total}]$ into equal strata, pick one uniform value per stratum, and walk root to leaf going left when the value fits the left sum and right otherwise. That walk takes $\lceil \log_2 N \rceil$ steps. Updating a priority after its TD error changes walks back up the same path, also $O(\log N)$ .

Worked example

Take $N = 4$ with $\alpha = 1.0$ , $\epsilon = 0$ , $\beta = 0.5$ . TD magnitudes are $1.0$ , $4.0$ , $0.5$ , $2.0$ , so priorities equal those numbers and the total is $p_{total} = 1.0 + 4.0 + 0.5 + 2.0 = 7.5$ . The tree array is $[7.5, 5.0, 2.5, 1.0, 4.0, 0.5, 2.0]$ : root $7.5$ , left sum $5.0$ , right sum $2.5$ , then the four leaves.

Probabilities divide by $7.5$ : $P = [0.1333, 0.5333, 0.0667, 0.2667]$ . The $4.0$ item draws more than half the samples. Raw weights $(4P)^{-0.5}$ are $[1.3693, 0.6847, 1.9365, 0.9682]$ ; dividing by the max $1.9365$ gives normalized weights $[0.7071, 0.3536, 1.0000, 0.5000]$ . The most sampled item is discounted hardest at $0.3536$ , which stops frequent updates from dragging the whole surface. After training drops the $4.0$ error to $1.0$ , the leaf becomes $1.0$ , its parent drops from $5.0$ to $2.0$ , and the root drops from $7.5$ to $4.5$ . The diagram draws this exact tree and weight row.

Code

The snippet recomputes the four probabilities and weights from the worked example with the standard library only.

1import math2
3priorities = [1.0, 4.0, 0.5, 2.0]4total = sum(priorities)5probs = [p / total for p in priorities]6print([round(p, 4) for p in probs])  # -> [0.1333, 0.5333, 0.0667, 0.2667]7
8beta = 0.59n = 410raw = [(n * p) ** (-beta) for p in probs]11peak = max(raw)12normed = [w / peak for w in raw]13print([round(w, 4) for w in normed])  # -> [0.7071, 0.3536, 1.0, 0.5]14print(round(total, 4))                # -> 7.5

The prints match the hand derived total $7.5$ , the $53.3$ percent draw rate for the $4.0$ item, and its discounted weight $0.3536$ .

Watch Out For

Zero epsilon locks transitions out forever

The symptom is a slice of the buffer that never replays: its error once hit exactly zero, its priority became $0$ , and its sampling probability stuck at $0$ . Later policy shifts make those states relevant again, but the network never sees them because the tree never routes there.

Keep $\epsilon > 0$ , typically $10^{-6}$ to $10^{-5}$ , so every leaf holds a nonzero floor. Log the fraction of leaves below twice $\epsilon$ ; a growing pile at the floor means the buffer is going stale rather than solved.

Leaving beta low for the whole run

The symptom is a value surface tilted toward dramatic memories: sharp spikes near rare crashes and washed out values elsewhere, even as loss falls. Sampling stayed skewed while the correction never reached full strength, so gradients converged to the wrong fixed point.

Anneal $\beta$ from about $0.4$ toward $1.0$ across training and normalize weights by the batch max for stability. If late training still overreacts to rare items, check the $\beta$ schedule before touching $\alpha$ .

The Quick Version

Priority $p_i = \lvert \delta_i \rvert + \epsilon$ turns TD surprise into sampling probability $P(i) \propto p_i^\alpha$ .
A binary sum tree draws and updates in $O(\log N)$ , which is what makes a million size buffer practical.
Importance weights $(N P(i))^{-\beta}$ undo the skew, with $\beta$ annealed to $1.0$ for unbiased late updates.
With priorities $[1.0, 4.0, 0.5, 2.0]$ the total is $7.5$ and normalized weights are $[0.7071, 0.3536, 1.0, 0.5]$ .
New transitions enter at max priority and $\epsilon$ stays positive so no memory locks out.