Experience Replay

Experience replay stores past transitions in a circular memory buffer and trains on random mini-batches, breaking time correlations for stable deep network training.

Five transitions stream into a four-slot ring buffer that overwrites the oldest, and a random batch of two distant transitions gives loss 1.0125 instead of a correlated update

Why Does This Exist?

The first attempts to combine RL with deep networks in the early 2010s kept collapsing. Value estimates swung wildly and agents failed on rudimentary games. Two properties of sequential data caused it.

First, correlation. Gradient descent assumes training samples are independent and identically distributed, but an RL agent collects data in order: $S_{t+1}$ depends strongly on $S_t$ . Thirty seconds of open highway trains the network only on straightaways, and when the sharp curve finally arrives, the cornering weights are gone. That is catastrophic forgetting wearing a racing suit.

Second, waste. In online RL each transition $(s_t, a_t, r_{t+1}, s_{t+1})$ trains once and is discarded. Robot actuators wear out and game engines run at fixed frame rates, so throwing away hard-won experience after one update squanders the training signal.

Long-Ji Lin proposed the fix in 1992, and Mnih and co-authors revived it in the 2015 Deep Q-Network paper. Store transitions in a circular buffer $\mathcal{D}$ and train on randomized mini-batches drawn from it. Shuffling breaks the time correlations, restoring near-independent samples, and each transition gets reused dozens of times.

This page covers the buffer mechanics, the sampling rule, and the off-policy catch. For the algorithm that made replay famous, read deep Q-networks. For sampling surprising transitions first, read prioritized experience replay. For the second stabilizing trick DQN paired with replay, read target networks.

The one idea you need first: a transition tuple. Each step produces $e_t = (s_t, a_t, r_{t+1}, s_{t+1}, d_{t+1})$ , where $d_{t+1}$ in $\{0, 1\}$ flags whether the episode ended. The buffer stores these tuples; everything else is machinery for reusing them well.

Think of It Like This

Film review instead of sideline shouting

A basketball player who learns only from the last play is doomed. Miss a three and the next five minutes go to shooting form while defense and passing rot. The latest event dictates all learning, so performance swings wildly.

A coaching staff with a video archive does it differently. They record every possession all season, then build each review reel by shuffling: a turnover from three weeks ago, a box-out from last night, an inbound play from two months back, a clutch free throw, a foul from yesterday. Because the reel mixes opponents, months, and situations, the player builds balanced habits instead of overreacting to whatever happened five seconds ago.

Where it stops: human coaches hand-pick the embarrassing clips, biasing review toward mistakes. Uniform replay gives every stored transition an equal shot regardless of surprise, which is exactly what prioritized experience replay changes.

How It Actually Works

Each step appends its tuple $e_t$ to a fixed-capacity store:

$\mathcal{D} = \{ e_1, e_2, \dots, e_{|\mathcal{D}|} \}, \quad |\mathcal{D}| \le N$

with $N$ typically $10^5$ to $10^6$ in deep RL. Memory is a circular queue: when full, the newcomer overwrites the oldest entry at index $t \bmod N$ . Training draws a mini-batch $\mathcal{B}$ of size $B$ (commonly 32, 64, or 256) uniformly at random:

$P(e^{(i)} = e_k) = \frac{1}{|\mathcal{D}|}$

and minimizes the mean squared error against a semi-static target network $\theta^-$ :

$\mathcal{L}(\theta) = \frac{1}{B} \sum_{i=1}^B \left( y^{(i)} - Q(s^{(i)}, a^{(i)}; \theta) \right)^2, \quad y^{(i)} = r^{(i)} + \gamma (1 - d^{(i)}) \max_{a'} Q(s'^{(i)}, a'; \theta^-)$

Why shuffling stabilizes training

For a batch of size $B$ with lag- $k$ correlations $\rho_k$ , the gradient estimator variance is:

$\operatorname{Var}\left( \frac{1}{B} \sum_{i=1}^B \mathbf{g}_i \right) = \frac{\sigma^2}{B} \left[ 1 + 2 \sum_{k=1}^{B-1} \left(1 - \frac{k}{B}\right) \rho_k \right]$

In a sequential stream $\rho_1$ sits near 0.8 to 0.99, which inflates the bracket far above 1 and shrinks the effective batch. Uniform sampling across thousands of past episodes drives $\rho_k$ toward zero, collapsing the bracket to 1 and restoring standard gradient behavior.

The off-policy catch

Buffered transitions were collected by older policies, so the data distribution lags the current one. That is fine for off-policy methods (Q-learning, DQN, DDPG, TD3, SAC), which evaluate a target policy from arbitrary behavior data. It breaks on-policy methods (REINFORCE, A2C, plain PPO), whose update math assumes fresh data from the current policy. Replay plus on-policy updates without correction drifts and collapses.

Worked example: a four-slot buffer

Capacity $N = 4$ , batch size $B = 2$ . Five transitions arrive:

$e_1 = (s{=}1.0, a{=}0, r{=}0.0, s'{=}2.0, d{=}0)$ into slot 0
$e_2 = (s{=}2.0, a{=}1, r{=}1.0, s'{=}3.0, d{=}0)$ into slot 1
$e_3 = (s{=}3.0, a{=}0, r{=}0.0, s'{=}4.0, d{=}0)$ into slot 2
$e_4 = (s{=}4.0, a{=}1, r{=}2.0, s'{=}5.0, d{=}1)$ into slot 3, buffer full
$e_5 = (s{=}10.0, a{=}0, r{=}0.5, s'{=}11.0, d{=}0)$ overwrites slot 0

Buffer now holds $[e_5, e_2, e_3, e_4]$ with the write pointer at index 1. The sampler draws batch $[e_2, e_5]$ : one early small-state transition, one far-away large-state transition. The chain is broken by construction.

Take a linear model $Q(s, a) = w_a \cdot s$ with $w_0 = w_1 = 0.5$ , matching target weights, and $\gamma = 0.9$ . For $e_2$ : next values are $0.5 \times 3.0 = 1.5$ for both actions, so $y_2 = 1.0 + 0.9 \times 1.5 = 2.35$ ; prediction is $0.5 \times 2.0 = 1.0$ ; error $\delta_2 = 2.35 - 1.0 = 1.35$ . For $e_5$ : next values are $0.5 \times 11.0 = 5.5$ , so $y_5 = 0.5 + 0.9 \times 5.5 = 5.45$ ; prediction is $0.5 \times 10.0 = 5.0$ ; error $\delta_5 = 5.45 - 5.0 = 0.45$ . Loss:

$\mathcal{L} = \frac{1.35^2 + 0.45^2}{2} = \frac{1.8225 + 0.2025}{2} = 1.0125$

Code

A pure-Python transcription of the worked example: the ring buffer, the wrap-around, and the loss on batch $[e_2, e_5]$ .

1capacity = 42buffer = []3pointer = 04
5transitions = [6    (1.0, 0, 0.0, 2.0, False),7    (2.0, 1, 1.0, 3.0, False),8    (3.0, 0, 0.0, 4.0, False),9    (4.0, 1, 2.0, 5.0, True),10    (10.0, 0, 0.5, 11.0, False),11]12
13for t in transitions:14    if len(buffer) < capacity:15        buffer.append(t)16    else:17        buffer[pointer] = t18    pointer = (pointer + 1) % capacity19
20w = [0.5, 0.5]21gamma = 0.922
23
24def td_error(t):25    s, a, r, s_next, done = t26    q_next_max = max(wt * s_next for wt in w)27    target = r + (0.0 if done else gamma * q_next_max)28    return target - w[a] * s29
30
31batch = [buffer[1], buffer[0]]32errors = [td_error(t) for t in batch]33loss = sum(e ** 2 for e in errors) / len(errors)34
35print([t[0] for t in buffer])  # -> [10.0, 2.0, 3.0, 4.0]36print(pointer)  # -> 137print([round(e, 4) for e in errors])  # -> [1.35, 0.45]38print(round(loss, 4))  # -> 1.0125

Watch Out For

Feeding replay data to an on-policy algorithm

The symptom is a policy that improves briefly, then drifts and collapses. The cause: transitions in $\mathcal{D}$ came from older policy versions, but on-policy update math assumes every sample came from the current one. PPO, A2C, and SARSA consume stale distributions they were never derived for.

The fix is architectural, not a hyperparameter. Use replay only with off-policy methods (DQN, DDPG, TD3, SAC). If an on-policy method must reuse data, that reuse needs explicit correction machinery, which is a different algorithm, not a tweak.

Sizing the buffer by guesswork

Too small (under about $10^4$ ) and the buffer cannot decorrelate: consecutive batches still look sequential, forgetting returns, and the agent cycles through local policies. Too large (past about $10^7$ ) and the buffer fills with ancient random-exploration junk that dilutes fresh, competent play and slows convergence to a crawl.

The fix: start near $10^5$ to $10^6$ for Atari-scale or continuous control tasks, then check the age mix. If rare high-value transitions keep getting overwritten before they train, that is the signal to upgrade to prioritized experience replay, not to blindly grow $N$ .

The Quick Version

Replay stores transitions in a fixed-size circular buffer and trains on uniform random mini-batches.
Shuffling breaks time correlations and restores the near-independent samples gradient descent assumes.
Each expensive environment step gets reused across dozens of updates instead of training once and dying.
The five-transition example overwrites slot 0, batches $[e_2, e_5]$ , and computes loss $1.0125$ from errors $1.35$ and $0.45$ .
Replay is strictly off-policy: buffered data comes from older policies, so on-policy methods must stay away.