Visual walkthrough — Experience replay

The one result we are chasing:

${\nabla }_{\theta }L(\theta )\approx \frac{1}{|B|}{\sum }_{e\in B}{\nabla }_{\theta }\ell (e;\theta ),B\sim \mathcal{U}(\mathcal{D}).$

Don't panic at the symbols — we will meet each one the moment we need it, and not a second earlier.

---

Step 1 — What an "experience" even is

WHAT. An agent lives in a loop: it is in a situation, it acts, something happens, it lands in a new situation. We freeze that single moment into four things and call it a transition:

$e_t=(\underset{\text{where I was}}{\underbrace{s_t}},\underset{\text{what I did}}{\underbrace{a_t}},\underset{\text{reward I got}}{\underbrace{r_t}},\underset{\text{where I ended up}}{\underbrace{s_{t+1}}}).$

• $s_t$ — the state, a snapshot of the world (e.g. the game screen).
• $a_t$ — the action the agent chose.
• $r_t$ — the immediate reward, a single number (+1 good, −1 bad, 0 nothing).
• $s_{t+1}$ — the next state, the world after the action.

WHY these four and nothing more? Because they are exactly enough to compute one learning update later — no more, no less. Storing anything else wastes memory; storing less makes the update impossible.

PICTURE. One arrow of time, one transition boxed out of it.

---

Step 2 — The live stream is a chain of near-twins

WHAT. In a real game, consecutive states barely differ: the ball moved three pixels. So $s_t$ and $s_{t+1}$ look almost identical — they are correlated.

WHY it matters. The math tool that trains neural nets — stochastic gradient descent — was built on one promise: the training examples you feed it are drawn i.i.d. (independent and identically distributed). "Independent" means each new sample carries fresh information, not a copy of the last one.

Why "i.i.d." and not some other assumption? Because the honesty of an average rests on independence. Average ten near-duplicate numbers and you learn as much as from one number — but you think you learned ten times as much. That false confidence is exactly what wrecks online RL.

PICTURE. The stream drawn as beads on a string, neighbours almost the same colour — tightly correlated.

---

Step 3 — What we are actually trying to minimise

WHAT. We want the network's guess $Q_{\theta }(s,a)$ — its estimate of "how good is action $a$ in state $s$" — to obey the Bellman optimality equation. We can't reach the true answer $Q^{\ast }$, so we bootstrap: we build a moving target $y$ out of the network's own current estimate.

$y=\underset{\text{reward now}}{\underbrace{r}}+\underset{\text{discount }0<\gamma <1}{\underbrace{\gamma }}\underset{\text{best value we think the future holds}}{\underbrace{\underset{a^{\prime }}{\max }{Q}_{{\theta }^{-}}(s^{\prime },a^{\prime })}}.$

• $r$ — the reward we actually received in this transition.
• $\gamma$ — a knob between 0 and 1 that shrinks future rewards (the future is worth a little less than now).
• ${\max }_{a^{\prime }}$ — over every action $a^{\prime }$ available in the next state, pick the most valuable.
• ${\theta }^{-}$ — a frozen copy of the network weights (a target network), held still so the target doesn't wriggle while we chase it.

The error of one transition is the squared TD error — from Temporal-Difference Learning:

$\ell (e;\theta )=(\underset{\text{what we should have said}}{\underbrace{y}}-\underset{\text{what we did say}}{\underbrace{Q_{\theta }(s,a)}}{)}^2.$

Why squared? Squaring makes every error positive (over- and under-shooting both cost) and punishes big misses harder than small ones. The number inside, $\delta =y-Q_{\theta }(s,a)$, is the TD error — how surprised we were.

PICTURE. A number line: the prediction $Q_{\theta }$, the target $y$, and the gap $\delta$ between them, with the loss as the area of a square built on that gap.

---

Step 4 — The true objective is an average, and averages need honest samples

WHAT. We don't care about one transition's error; we care about the average error over the whole distribution $\rho$ of situations the agent meets:

$L(\theta )={\mathbb{E}}_{e\sim \rho }[\ell (e;\theta )].$

• ${\mathbb{E}}_{e\sim \rho }[\cdot ]$ — the expectation: the long-run average of the thing in brackets, over transitions $e$ drawn from the distribution $\rho$.

WHY the expectation is the whole game. We can never sum over all possible situations — there are too many. So we estimate the average from a handful of samples. This is the Monte-Carlo idea: guess an average by averaging a random sample.

Why does the sample have to be random and independent? Because that is the only condition under which a sample-average is an unbiased estimate of the true average. Correlated samples (Step 2) violate it, so the live-stream average is a liar — it systematically misjudges $L(\theta )$.

PICTURE. A big cloud of all possible transitions (the true landscape) versus a tiny correlated cluster the live stream actually sees — the cluster's average sits far from the cloud's true centre.

---

Step 5 — The buffer: freeze the stream, then shuffle it

WHAT. Store every transition in a fixed-size FIFO memory, the replay buffer:

$\mathcal{D}=\{e_1,e_2,\dots ,e_N\}.$

When it is full, evict the oldest. Now, instead of learning from the live stream, we draw a mini-batch uniformly at random:

$B\sim \mathcal{U}(\mathcal{D}).$

• $\mathcal{D}$ — the buffer, capacity $N$.
• $\mathcal{U}(\mathcal{D})$ — the uniform distribution over $\mathcal{D}$: every stored transition has the same chance $1/N$ of being picked.
• $B$ — the handful (the mini-batch) we actually train on this step.

WHY this fixes Step 2. Two transitions picked at random from a big, diverse pool are almost never neighbours in time. So they are approximately independent — the i.i.d. promise (Step 4) is approximately restored. The average over $B$ becomes an honest estimate of $L(\theta )$ again.

PICTURE. The correlated stream pours into a box; random hands reach in and pull out scattered, uncorrelated picks (the mini-batch in red).

---

Step 6 — Assemble the central result

WHAT. To improve the network we descend the gradient ${\nabla }_{\theta }L$. Since $L$ is an average (Step 4) and the gradient of an average is the average of the gradients, we estimate it with our honest mini-batch:

${\nabla }_{\theta }L(\theta )\approx \frac{1}{|B|}{\sum }_{e\in B}{\nabla }_{\theta }\ell (e;\theta ),B\sim \mathcal{U}(\mathcal{D}).$

• ${\nabla }_{\theta }$ — the gradient: the direction in weight-space that most increases $L$; we step against it to reduce error.
• $\frac{1}{|B|}{\sum }_{e\in B}$ — the mini-batch average, standing in for the impossible full expectation.
• The "$\approx$" is exactly the Monte-Carlo approximation, and it is a good one precisely because $B$ is uniform (Step 5).

WHY this is the flagship line. It is where all three earlier ideas snap together: the loss (Step 3), the true average we want (Step 4), and the honest sampler that lets a small sum stand in for a giant average (Step 5). This is why off-policy methods like DQN, DDPG and Soft Actor-Critic can reuse old data at all.

PICTURE. Each red mini-batch member contributes a little gradient arrow; the arrows sum to a clean estimate of the true descent direction (dashed).

---

Step 7 — The degenerate cases (never leave a scenario unshown)

WHAT & WHY. Two edges break the clean picture; we handle both.

Edge A — terminal state ($d=1$). If $s^{\prime }$ is the end (game over), there is no future. We multiply the bootstrap term by $(1-d)$:

$y=r+\gamma \underset{=0\text{ if terminal}}{\underbrace{(1-d)}}{\max }_{a^{\prime }}{Q}_{{\theta }^{-}}(s^{\prime },a^{\prime }).$

When $d=1$ the whole future term vanishes and $y=r$. Why: valuing an imaginary future after the game ends would poison the target.

Edge B — tiny or huge buffer.

• $N=1$: the "pool" is one transition — sampling gives back the correlated stream, benefit gone.
• $N$ enormous: the pool holds stale transitions from a much worse past policy, so the average drifts toward outdated behaviour. Neither extreme is honest; buffer size is a freshness ↔ decorrelation trade-off.

PICTURE. Left: a terminal transition with its future term crossed out ($y=r$). Right: the size trade-off as a slider between "too correlated" and "too stale", with a sweet spot in red.

---

The one-picture summary

This single figure compresses all seven steps: the correlated stream (bad average) enters the buffer, uniform sampling pulls a decorrelated mini-batch (red), and that batch's average gradient honestly points down the true loss valley.

Recall Feynman: the whole walkthrough in plain words

You're learning a game and you keep a notebook where every page is one moment: where I was, what I did, what happened, where I ended up. If you only ever re-read the page you just wrote, every page looks like the last one — you fool yourself into thinking you've studied lots when you've studied one thing many times. So instead you flip to a few random pages each practice round. Random pages are all different, so their average is an honest picture of the whole game, and honest averages tell you which way to nudge your brain to get better. Two warnings: if a page says "GAME OVER", don't imagine a future after it — score it by the reward alone. And keep the notebook a sensible size: one page is useless, a thousand ancient pages keep you stuck in your beginner days.

Recall Check yourself

Why must the mini-batch be sampled randomly and not just be "the last few transitions"? ::: Because an honest average needs independent samples; the last few transitions are near-twins (correlated), so their average is biased and lies about the true loss. What does the $(1-d)$ factor do in the target $y$? ::: It zeroes the future value term for terminal states, so a game-over transition uses $y=r$ with no imagined future. In the central result, what stands in for the impossible full expectation ${\mathbb{E}}_{e\sim \rho }$? ::: The mini-batch average $\frac{1}{|B|}{\sum }_{e\in B}$ over uniformly sampled transitions.