Experience replay: Question bank — AI-ML deep dive

Notation reminder so nothing is unearned:

A transition $e = (s, a, r, s^{'})$ — one experienced step: state, action, reward, next state.
$D$ — the replay buffer, a fixed-size FIFO memory of $N$ transitions.
$γ \in [0, 1)$ — the discount factor: how much a reward one step in the future is worth compared to a reward now. $γ = 0$ means "only care about the immediate reward"; $γ$ near $1$ means "value the long-term future almost as much as now."
$θ$ — the parameters (weights) of the online Q-network $Q_{θ}$ we are training.
$θ^{-}$ — the parameters of a target network $Q_{θ^{-}}$ : a slow-moving frozen copy of $θ$ , refreshed only every $C$ steps. We use it to build stable targets so we're not chasing a value that shifts every gradient step. See Target Networks.
$y$ — the bootstrapped target, our best current guess of what $Q_{θ} (s, a)$ should equal: $y = r + γ (1 - d) max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'}) .$ It stacks the immediate reward $r$ onto the discounted best future value estimated by the frozen target network. See Bellman optimality equation.
$δ = y - Q_{θ} (s, a)$ — the TD error, "how wrong my current value guess was" (target minus estimate).
$d$ — the terminal flag: $d = 1$ if $s^{'}$ ended the episode (no future), $d = 0$ otherwise. The $(1 - d)$ factor zeroes the future term at terminals.
i.i.d. = independent and identically distributed — samples that don't lean on each other and all come from the same fixed pool.

Formula Why

$p_{i} = ∣ δ_{i} ∣ + ϵ$ ? (algebraic derivation of $P (i)$ ) Step 1 — pick a "wrongness" score. We want to replay the transitions the network is most wrong about. The cleanest single number for "how wrong" is the magnitude of the TD error, $∣ δ_{i} ∣ = ∣ y_{i} - Q_{θ} (s_{i}, a_{i}) ∣$ — big $∣ δ_{i} ∣$ means a large gradient is waiting to be exploited. Step 2 — turn scores into a probability. A probability distribution must be non-negative and sum to $1$ . Given raw scores $p_{i} > 0$ we get the unique proportional distribution by normalising: divide each by the total, $P (i) = \frac{p _{i}}{\sum _{k} p _{k}} .$ Step 3 — add a sharpness knob. Raising each score to a power $α$ before normalising lets us tune how sharply probability concentrates on high scores. Substituting $p_{i} \to p_{i}^{α}$ : $P (i) = \frac{p _{i}^{α}}{\sum _{k} p _{k}^{α}} .$ Check: $α = 0 \Rightarrow p_{i}^{0} = 1 \Rightarrow P (i) = 1/ N$ (uniform); $α = 1 \Rightarrow$ straight proportionality. Step 4 — patch the zero. With $p_{i} = ∣ δ_{i} ∣$ , a perfectly predicted transition has $∣ δ_{i} ∣ = 0 \Rightarrow p_{i}^{α} = 0 \Rightarrow P (i) = 0$ : it is never sampled again, even if later drift makes it wrong. Adding a floor $ϵ > 0$ gives $p_{i} = ∣ δ_{i} ∣ + ϵ$ , so every $P (i) > 0$ and no transition is starved. Figure s01 traces exactly this pipeline; the questions below reference it.

Figure s01 (PER pipeline). Read it left to right: TD error $\to$ priority (with the $ϵ$ floor) $\to$ raise to $α$ $\to$ normalise into $P (i)$ $\to$ sample a batch, and separately compute the IS weight $w_{i}$ . Question WHY3 and SE7 both point back at this figure.

The next figure is the mental model behind the whole bank — why random draws beat the live stream. Refer back to it whenever a question mentions "correlation."

Figure s02 (correlation picture). The lavender curve is one smooth trajectory; the coral dots are consecutive online picks (clustered = correlated), while the mint dots are random replay picks (spread out = decorrelated). Questions TF1, TF9, WHY2 all analyse this contrast — specifically, notice that clustering hurts variance, not bias.

True or false — justify

TF1. Experience replay's main statistical benefit is reducing gradient bias.

False — decorrelating consecutive samples (figure s02) mainly reduces gradient variance; the bias problem comes from a non-stationary target, which target networks and buffer smoothing address separately.

TF2. Storing the last

N

transitions in a queue is experience replay.

False — storage without uniform random sampling leaves the temporal correlation intact; you must shuffle the draw, not just the storage.

TF3. Uniform experience replay gives an unbiased estimate of the true loss gradient.

True (approximately) — uniform draws from a large diverse buffer approximate i.i.d. samples from the training distribution, so the Monte-Carlo gradient is roughly unbiased. See Temporal-Difference Learning.

TF4. Prioritized Experience Replay (PER) gives an unbiased gradient without any correction.

False — non-uniform sampling skews the expectation, so PER needs importance-sampling weights

w_{i} = (\frac{1}{N P ( i )})^{β}

to correct the bias. See Importance Sampling.

TF5. Experience replay can be bolted onto any RL algorithm.

False — it stores data from old policies, so it only suits off-policy methods like DQN, DDPG, SAC; on-policy methods break. See Off-policy vs On-policy.

TF6. A larger buffer always improves learning.

False — a huge buffer retains stale transitions from much worse past policies, slowing adaptation; it's a diversity-vs-freshness trade-off.

TF7. With

α = 0

(the priority exponent), PER behaves identically to plain uniform replay.

True — every priority raised to the zeroth power is

1

, so

P (i) = 1/ N

, exactly uniform sampling.

TF8. The target network (parameters

θ^{-}

, a frozen slow copy of the online weights

θ

) is what makes replay possible.

False — replay and target networks are separate tricks; replay decorrelates samples, target networks stabilise the bootstrap target

y = r + γ (1 - d) max_{a^{'}} Q_{θ^{-}}

. They pair well but neither requires the other.

TF9. Sampling in temporal order is fine as long as you shuffle mini-batch rows.

False — if the pool you draw from is a short recent window, the rows are still near-duplicates (figure s02); correlation lives in which transitions can be picked, not just their order.

TF10. In PER, transitions with the largest TD error are the ones you're most wrong about, so they're most worth replaying.

True —

∣ δ ∣

measures prediction error, and the 80/20 idea is to spend compute where the network is currently most inaccurate.

Spot the error

SE1. "Correlated samples are fine because SGD averages over the mini-batch anyway."

The mini-batch average of near-identical samples is still near that single state's gradient — averaging duplicates doesn't restore i.i.d.-ness or shrink variance across the whole state space.

SE2. "PER samples hard transitions more, so training converges to the same solution, just faster."

Wrong — biased sampling shifts the fixed point you converge to unless corrected; you can converge to the wrong

Q

without the IS weights

w_{i}

SE3. "For a terminal transition, the target is

y = r + γ max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'})

The bootstrap term must be killed at terminals:

y = r + γ (1 - d) max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'})

with the terminal flag

d = 1

, because a terminal state has no future value.

SE4. "Replay lets us skip the Bellman optimality equation since we just fit stored targets."

The stored target

y = r + γ (1 - d) max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'})

(built from the frozen target-network parameters

θ^{-}

) is a bootstrap of the Bellman equation — so we're still solving Bellman, just with recycled data.

SE5. "We anneal

β \to 0

over training to fully correct PER's bias."

Backwards — bias correction increases with the IS exponent

β

, so we anneal

β \to 1

to fully correct near convergence.

SE6. "Because DQN is off-policy, importance-sampling ratios are needed for the

max

target."

The

max_{a^{'}}

target already evaluates the greedy policy directly, so the standard DQN target needs no IS ratio — IS enters PER only to fix the sampling bias, a different issue.

SE7. "Setting priority

p_{i} = ∣ δ_{i} ∣

(no

ϵ

) is cleaner."

A transition with

δ_{i} = 0

would get priority

0

and never be sampled again (the

P (i) = 0

trap in figure s01), even if the network later drifts; the small

ϵ

keeps every transition reachable.

Why questions

WHY1. Why does online (no-replay) deep RL tend to diverge or oscillate?

Consecutive samples are correlated (raising gradient variance) and the bootstrapped target

y

moves as the policy changes (a bias from non-stationarity) — both destabilise training at once.

WHY2. Why does random sampling from a large buffer approximate i.i.d. draws?

Two random picks from a big diverse pool (figure s02, mint dots) are unlikely to be temporally adjacent, so their statistical dependence drops toward independence.

WHY3. Why do we down-weight frequently-sampled transitions in PER by

1/ P (i)

Over-sampling hard cases skews the empirical average; the weight

w_{i} \propto (1/ P (i))^{β}

re-weights each term back to what a uniform expectation would give — textbook importance sampling, the last stage in figure s01.

WHY4. Why is a rare, informative experience (finally scoring) so valuable in a buffer?

Online RL sees it once and discards it; the buffer lets that high-signal transition be replayed many times so its lesson actually sticks.

WHY5. Why must replay methods be off-policy?

Buffer transitions were generated by older policies, so learning from them means learning about a policy different from the current one — precisely what off-policy learning permits.

WHY6. Why normalise the IS weights by

max_{j} w_{j}

It caps the weights at

1

so no single sample produces a huge gradient step, keeping the update numerically stable.

WHY7. Why doesn't averaging over a big buffer completely eliminate the moving-target problem?

The buffer only smooths the data distribution; the bootstrapped target

y

(built from

Q_{θ^{-}}

) still shifts as

θ^{-}

updates, which is why we also need slow target-network updates.

Edge cases

EC1. Buffer holds exactly one transition — what does replay reduce to?

Pure online learning on that single sample — no decorrelation and no diversity, so all benefits vanish.

EC2. Every transition in the buffer has identical TD error under PER.

All priorities are equal, so

P (i) = 1/ N

and PER collapses to uniform replay regardless of

α

EC3. Reward is always zero and the episode never terminates — is replay still meaningful?

Yes for propagating bootstrapped value through

γ max_{a^{'}} Q_{θ^{-}}

, but with no reward signal there's nothing to bootstrap toward, so learning stalls (a reward-shaping / exploration problem, not a replay one).

EC4.

γ = 0

in the target.

The target becomes

y = r

— the agent learns only immediate reward and ignores the future, so replay just fits a one-step regression.

EC5. Buffer is smaller than the correlation length of the environment (e.g. holds 3 near-duplicate frames).

Random sampling can't decorrelate what's already homogeneous; you'd still feed near-identical gradients and see instability.

EC6. In PER, the priority exponent

α = 1

and the IS exponent

β = 0

Fully greedy priority sampling with zero bias correction — maximally focused on hard cases but with a biased, potentially unstable gradient.

EC7. A transition is stored but its next state's true value later changes drastically (policy improved).

Its cached

δ

is stale, so PER may under- or over-sample it; priorities are refreshed each time a transition is drawn to mitigate this.

EC8. You apply replay to a strictly on-policy A2C without corrections.

The value/advantage estimates become invalid because they're computed on data from a different policy — expect biased, unreliable updates.

Recall One-line summary to carry away

Replay's power = uniform random sampling (cuts variance via decorrelation) + reuse (efficiency); PER adds targeting but must pay for it with importance-sampling weights; and the whole trick only lives in the off-policy world.