Experience replay

WHAT is experience replay?

The typical home of this trick is Deep Q-Networks (DQN), so we ground everything there.

WHY do we need it? (the two diseases it cures)

Naive "online" deep RL updates the network from each transition as it arrives. Two problems arise:

Disease 1 — Correlated samples. Consecutive states $s_t, s_{t+1}, s_{t+2}$ are almost identical (the car moved 3 pixels). Stochastic gradient descent assumes your samples are roughly i.i.d. Feeding it a stream of near-duplicate, highly-correlated samples gives high-variance, biased gradient estimates — the net over-fits to whatever it's seeing right now.

Disease 2 — Data inefficiency. A rare, informative experience (you finally scored a point!) is seen once and discarded. With a buffer it can be replayed dozens of times.

Disease 3 — Non-stationary target chasing. The policy changes → the distribution of incoming data changes → the network chases a moving target and can oscillate/diverge. Averaging over a large buffer smooths the training distribution.

HOW does it work? (algorithm, derived step by step)

We want to fit $Q_\theta(s,a)$ to satisfy the Bellman optimality equation: $Q^*(s,a) = \mathbb{E}_{s'}\Big[\, r + \gamma \max_{a'} Q^*(s',a') \,\Big].$

Since we don't know $Q^*$ , we bootstrap: build a target using the current network, $y = r + \gamma \max_{a'} Q_{\theta^-}(s', a'),$ where $\theta^-$ is a (slowly updated) target-network copy. The loss for one transition is the squared TD error: $\ell(e;\theta) = \big(y - Q_\theta(s,a)\big)^2.$

Why sample from a buffer here? The true objective is an expectation over the state–action distribution $\rho$ : $L(\theta) = \mathbb{E}_{e\sim\rho}\big[\ell(e;\theta)\big].$ An unbiased Monte-Carlo estimate of $\nabla_\theta L$ needs samples drawn independently from $\rho$ . Uniform sampling from a large buffer approximates i.i.d. draws far better than the correlated live stream. So: $\nabla_\theta L(\theta) \;\approx\; \frac{1}{|B|}\sum_{e\in B} \nabla_\theta \ell(e;\theta), \qquad B \sim \mathcal{U}(\mathcal{D}).$

Prioritized Experience Replay (the 80/20 upgrade)

Uniform sampling wastes effort on transitions the net already predicts well. Prioritized Experience Replay (PER) samples in proportion to the magnitude of the TD error $\delta_i = y_i - Q_\theta(s_i,a_i)$ — "the transitions I'm most wrong about are the ones I should study."

Formula PER sampling & correction

Priority $p_i = |\delta_i| + \epsilon$ . Sampling probability with exponent $\alpha$ : $P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}}.$

$\alpha=0$ → uniform (recovers plain replay); $\alpha=1$ → fully greedy priority.
Because sampling is now non-uniform, our gradient estimate is biased. We fix it with importance-sampling weights: $w_i = \Big(\tfrac{1}{N}\cdot\tfrac{1}{P(i)}\Big)^{\beta}, \quad \text{used as } w_i\,\delta_i \text{ in the update.}$ $\beta \to 1$ over training fully corrects the bias; each $w_i$ is normalised by $\max_j w_j$ for stability.

Worked examples

Worked example Example 1 — one uniform update

Buffer has 4 transitions; we sample a mini-batch of 2: $B=\{e_2,e_4\}$ . $e_2=(s,a,r{=}1,s')$ , non-terminal, $\gamma=0.9$ , $\max_{a'}Q_{\theta^-}(s',a')=5 \Rightarrow y_2 = 1+0.9\cdot5 = 5.5$ . Why this step? The target injects the discounted future value — that's the bootstrap. Current estimate $Q_\theta(s,a)=4 \Rightarrow \delta_2 = 5.5-4 = 1.5$ . $e_4$ terminal, $r=2 \Rightarrow y_4 = 2 + 0.9\cdot 0\cdot(\cdots) = 2$ ; $Q_\theta=2.3 \Rightarrow \delta_4 = -0.3$ . Why the zero? Terminal states have no future — the $(1-d)$ factor kills the bootstrap term. Batch loss $= \frac12(1.5^2 + 0.3^2) = \frac12(2.25+0.09)=1.17$ . Gradient descent shrinks both $\delta$ 's.

Common mistakes (steel-manned)

Forecast-then-Verify

Recall Forecast before you read the answer

Q: If you set $\alpha=0$ in PER, what algorithm do you recover, and why? A: Plain (uniform) experience replay — every $p_i^0=1$ , so $P(i)=1/N$ for all $i$ . Q: You increase buffer size 100×; does the correlation between two randomly sampled transitions go up or down? A: Down — larger, more diverse pool ⇒ two random picks are less likely temporally adjacent ⇒ more i.i.d.-like.

Recall Feynman: explain to a 12-year-old

Imagine you're learning a video game. A silly way is to only think about the move you just made and then forget it forever. A smart way: keep a notebook of past moves and what happened. Every practice round you flip to a few random pages and review them. Random pages stop you from getting stuck thinking only about the last thing, and reviewing old pages means a lucky trick you found once isn't forgotten. If some pages are marked "I got this really wrong," you flip to those more often — but you remind yourself they're rare so you don't get an unrealistic idea of how good you are.

Flashcards

What problem in online deep RL does experience replay solve first?

It breaks the correlation between consecutive (near-identical) samples, restoring the ~i.i.d. assumption SGD needs.

What is stored in a replay buffer?

Transitions

(s_t,a_t,r_t,s_{t+1})

(plus a terminal flag), in a fixed-capacity FIFO.

How are mini-batches drawn in plain experience replay?

Uniformly at random from the buffer.

Why does replay improve data efficiency?

Each transition (especially rare informative ones) can be reused in many gradient updates instead of once.

Why is replay only valid for off-policy algorithms?

The buffer contains data from old policies; on-policy methods require samples from the current policy.

What is the TD target in DQN with replay?

y=r+\gamma(1-d)\max_{a'}Q_{\theta^-}(s',a')

In PER, what determines a transition's priority?

The magnitude of its TD error,

p_i=|\delta_i|+\epsilon

Give the PER sampling probability.

P(i)=p_i^{\alpha}/\sum_k p_k^{\alpha}

Why does PER need importance-sampling weights?

Non-uniform sampling biases the gradient estimate;

w_i=(N\,P(i))^{-\beta}

corrects that bias.

What does

\alpha=0

give in PER?

Uniform experience replay (all priorities equal).

What role does the target network

\theta^-

play with replay?

Provides a slowly-changing target so the net isn't chasing a moving objective, adding stability.

Connections

Deep Q-Networks (DQN) — the algorithm replay was designed for
Bellman optimality equation — source of the TD target
Temporal-Difference Learning — the update replay feeds
Off-policy vs On-policy — why replay needs off-policy learning
Importance Sampling — the bias correction used in PER
Target Networks — companion stabiliser
DDPG / Soft Actor-Critic — off-policy actor-critics that also use replay

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, deep RL me agar hum agent ke har experience ko turant, sequence me, ek baar use karke phenk dein, to do problem aati hain. Pehli: lagataar aane wale states almost same hote hain (car sirf 3 pixel hili) — ye samples aapas me bahut correlated hote hain, aur SGD ko chahiye hote hain roughly i.i.d. samples. Correlated data se gradient noisy aur biased ho jaata hai. Doosri: koi rare achha experience (aakhirkaar point mil gaya!) sirf ek baar dikhta hai aur khatam. Experience replay in dono ka ilaaj hai — hum har transition $(s,a,r,s')$ ko ek replay buffer me store karte hain, aur training ke waqt buffer se random mini-batch utha kar seekhte hain. Random uthane se correlation toot jaata hai, aur purane useful experiences baar-baar replay hote rehte hain.

Buffer FIFO hota hai — jab full ho jaaye to sabse purana transition nikal jaata hai. Har step pe target banate hain $y = r + \gamma \max_{a'} Q_{\theta^-}(s',a')$ (agar terminal hai to future term zero), aur loss $(y - Q_\theta(s,a))^2$ pe gradient descent karte hain. Ek important baat: replay sirf off-policy methods (DQN, DDPG, SAC) ke liye valid hai, kyunki buffer me purani policy ka data hota hai; on-policy methods (jaise vanilla policy gradient) ke liye ye seedha kaam nahi karta.

Ek smart upgrade hai Prioritized Experience Replay (PER): jo transitions pe network sabse zyada galat hai (bada TD error $|\delta|$ ), unhe zyada baar sample karo — "jahan sabse zyada galti, wahan zyada practice" (yehi 80/20 hai). Par ek jaal hai: agar aap deliberately hard examples zyada uthaoge to gradient biased ho jaayega. Isliye har sample ko importance-sampling weight $w_i=(N\,P(i))^{-\beta}$ se multiply karte hain, taaki bias theek ho jaaye. Yaad rakho: Store karo, Off-policy Shuffle karke Sample karo — S.O.S.!

WHAT is experience replay?

WHY do we need it? (the two diseases it cures)

HOW does it work? (algorithm, derived step by step)

Prioritized Experience Replay (the 80/20 upgrade)

Worked examples

Common mistakes (steel-manned)

Forecast-then-Verify

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Deep & Advanced RL

Connections