Experience replay: Exercises — AI-ML deep dive

This page assumes only what the parent note built: a transition $e_{t} = (s_{t}, a_{t}, r_{t}, s_{t + 1})$ , the replay buffer $D$ , the TD target $y = r + γ max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'})$ , and the TD error $δ = y - Q_{θ} (s, a)$ . Every symbol below is used exactly as defined there.

Level 1 — Recognition

Exercise 1.1

Match each symbol to its plain-English meaning: $γ$ , $d_{i}$ , $θ^{-}$ , $D$ .

Recall Solution

$γ$ = the discount factor, a number in $[0, 1]$ that says how much a reward one step in the future is worth now. $γ = 0.9$ means "future rewards count 90% as much per step".
$d_{i}$ = the terminal flag: $d_{i} = 1$ if $s_{i}^{'}$ ended the episode (game over), else $0$ . It switches off the future-value term.
$θ^{-}$ = the weights of the target network, a slow-changing frozen copy of $θ$ (see Target Networks).
$D$ = the replay buffer, the FIFO memory of past transitions.

Exercise 1.2

The parent note lists three diseases naive online deep RL suffers. Name them in one phrase each.

Recall Solution

Correlated samples — consecutive states are near-duplicates, violating the i.i.d. assumption of SGD.
Data inefficiency — a rare informative transition is seen once and thrown away.
Non-stationary target chasing — the incoming data distribution shifts as the policy changes.

Exercise 1.3

True or false: "Experience replay requires the transitions to be replayed in the order they occurred." Explain.

Recall Solution

False. The whole point is to sample uniformly at random, $B \sim U (D)$ (the operator you met above). In-order replay preserves the temporal correlation you were trying to destroy.

Level 2 — Application

Exercise 2.1

A non-terminal transition has $r = 2$ , $γ = 0.95$ , and $max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'}) = 8$ . The current estimate is $Q_{θ} (s, a) = 6$ . Compute the target $y$ and the TD error $δ$ .

Recall Solution

What/Why: the target injects the discounted best future value — the one-step bootstrap of the Bellman optimality equation $Q^{*} (s, a) = E [r + γ max_{a^{'}} Q^{*} (s^{'}, a^{'})]$ , with $Q^{*}$ replaced by our frozen copy $Q_{θ^{-}}$ . $y = r + γ max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'}) = 2 + 0.95 \cdot 8 = 2 + 7.6 = 9.6.$ $δ = y - Q_{θ} (s, a) = 9.6 - 6 = 3.6.$ The figure below reads this off a number line: the current estimate sits at $6$ , the target at $9.6$ , and $δ$ is the gap the gradient step closes.

Exercise 2.2

A terminal transition has $r = - 1$ , $γ = 0.9$ , $max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'}) = 4$ , and $Q_{θ} (s, a) = 0.5$ . Compute $y$ and $δ$ . Which factor makes the $γ \cdot 4$ term vanish?

Recall Solution

Terminal $\Rightarrow d = 1 \Rightarrow (1 - d) = 0$ , so the bootstrap term is killed: $y = r + γ (1 - d) max_{a^{'}} Q_{θ^{-}} (s^{'}, a^{'}) = - 1 + 0.9 \cdot 0 \cdot 4 = - 1.$ $δ = - 1 - 0.5 = - 1.5.$ The == $(1 - d)$ factor== zeroes the future value: a terminal state has no future.

Exercise 2.3

A mini-batch $B = {e_{a}, e_{b}}$ has TD errors $δ_{a} = 3.6$ and $δ_{b} = - 1.5$ . Compute the mean-squared batch loss $\frac{1}{∣ B ∣} \sum δ^{2}$ .

Recall Solution

$L = \frac{1}{2} (3. 6^{2} + (- 1.5)^{2}) = \frac{1}{2} (12.96 + 2.25) = \frac{1}{2} (15.21) = 7.605.$

Level 3 — Analysis

Exercise 3.1

Four transitions have TD errors of magnitude $∣ δ ∣ = (2.0, 0.5, 0.5, 1.0)$ . Using PER with $ϵ = 0.01$ and $α = 0.5$ , compute the sampling probabilities $P (i)$ . (Priority $p_{i} = ∣ δ_{i} ∣ + ϵ$ .)

Recall Solution

Step 1 — priorities: $p = (2.01, 0.51, 0.51, 1.01)$ . Step 2 — raise to $α = 0.5$ (square root): $p^{0.5} = (2.01, 0.51, 0.51, 1.01) = (1.4177, 0.7141, 0.7141, 1.0050) .$ Step 3 — normalise. Sum $= 1.4177 + 0.7141 + 0.7141 + 1.0050 = 3.8509$ . $P = (0.3681, 0.1855, 0.1855, 0.2610) .$ Interpretation: the highest-error transition is sampled about $0.3681/0.1855 \approx 1.98 \times$ more often than a low-error one. Here $δ$ is the same TD error you meet in Temporal-Difference Learning — big $∣ δ ∣$ means "my prediction is far from the target," so PER studies it more. Figure s03 shows how the bar heights sharpen as $α$ grows.

Exercise 3.2

For the same four transitions, take the buffer size $N = 4$ and $β = 0.5$ . Compute the importance-sampling weight $w_{i} = (\frac{1}{N} \cdot \frac{1}{P ( i )})^{β}$ for the highest-priority transition ( $P = 0.3681$ ) and the lowest ( $P = 0.1855$ ), then normalise by $max_{j} w_{j}$ .

Recall Solution

What/Why: biased sampling ⇒ biased gradient; the IS weight from Importance Sampling down-weights the frequently-picked (high-priority) transitions to restore an unbiased average. High-priority: $w = (\frac{1}{4} \cdot \frac{1}{0.3681})^{0.5} = (0.6792)^{0.5} = 0.8241$ . Low-priority: $w = (\frac{1}{4} \cdot \frac{1}{0.1855})^{0.5} = (1.3477)^{0.5} = 1.1609$ . Normalise by the max ( $= 1.1609$ , the low-priority one — largest weight goes to the rarest-sampled): $w_{high}^{norm} = 0.8241/1.1609 = 0.7099, w_{low}^{norm} = 1.0.$ The often-sampled hard transition is scaled down to $\approx 0.71$ ; the rarely-sampled easy one keeps weight $1$ . That is exactly the correction.

Exercise 3.3

A student runs DQN with a buffer of 1 million transitions on a task where the good policy is found in the first 50k steps but the optimal policy needs fine-tuning near the end. They notice adaptation is slow late in training. Diagnose using the parent's bias–freshness idea.

Recall Solution

A 1M buffer keeps stale transitions from a much worse early policy. Late in training, most sampled data reflects behaviour the agent has already outgrown, so gradients pull toward outdated targets and fine-tuning stalls. Fix: shrink the buffer (or bias sampling toward recent data) so fresh, near-optimal transitions dominate — the bias–freshness trade-off. Bigger is not always better.

Level 4 — Synthesis

Exercise 4.1

Show that setting $α = 0$ in PER exactly recovers uniform replay. Then show that as $α \to 0$ , the IS weights $w_{i}$ all become equal (before normalisation) so the correction becomes a no-op. Assume $β$ fixed.

Recall Solution

Uniform recovery: with $α = 0$ , every $p_{i}^{0} = 1$ , so $P (i) = \frac{p _{i}^{0}}{\sum _{k} p _{k}^{0}} = \frac{1}{N} for all i .$ That is exactly $U (D)$ . IS weights collapse: substitute $P (i) = 1/ N$ : $w_{i} = (\frac{1}{N} \cdot \frac{1}{1/ N})^{β} = (1)^{β} = 1 for all i .$ All weights equal ⇒ after normalising by the max, each is $1$ ⇒ multiplying every $δ_{i}$ by $1$ changes nothing. So plain replay needs no IS correction — consistent with the fact that uniform sampling is already unbiased.

Exercise 4.2

You have TD errors magnitude $∣ δ ∣ = (1.5, 0.3, 0.3, 0.9)$ , $ϵ = 0.01$ . Compute the ratio of $P (highest)$ to $P (lowest)$ for $α = 0$ , $α = 0.5$ , and $α = 1$ . What does the trend tell you about $α$ 's role?

Recall Solution

Priorities $p = (1.51, 0.31, 0.31, 0.91)$ ; highest $= 1.51$ , lowest $= 0.31$ . The normalisation constant cancels in a ratio, so $\frac{P _{m a x}}{P _{m i n}} = (\frac{1.51}{0.31})^{α} = (4.871)^{α}$ .

$α = 0$ : $(4.871)^{0} = 1.000$ (uniform — no preference).
$α = 0.5$ : $(4.871)^{0.5} = 2.207$ .
$α = 1$ : $(4.871)^{1} = 4.871$ (fully greedy). Reading: $α$ is a sharpness knob. At $0$ all transitions are equal; as $α \to 1$ the highest-error transition is preferred ever more aggressively. It smoothly interpolates between uniform and greedy prioritisation.

Exercise 4.3

Explain why raw experience replay is valid for Deep Q-Networks (DQN), DDPG, and Soft Actor-Critic but breaks vanilla policy-gradient (A2C). Tie it to Off-policy vs On-policy.

Recall Solution

Replay stores transitions generated by old policies. DQN/DDPG/SAC are off-policy: their learning target (the Bellman backup) is defined for any behaviour data — the $max_{a^{'}}$ (DQN) or a separately-trained critic (DDPG/SAC) evaluates the current greedy/actor policy regardless of who collected the sample. Vanilla policy gradient is on-policy: its gradient $E_{π_{θ}} [\nabla lo g π_{θ} \hat{A}]$ is an expectation under the current policy $π_{θ}$ . Feeding it stale data estimates the gradient of the wrong distribution. Remedy if you must: apply Importance Sampling ratios $π_{θ} / π_{old}$ to reweight — the same correction principle PER uses.

Level 5 — Mastery

Exercise 5.1

Prove that uniform sampling from $D$ gives an unbiased estimate of $\nabla_{θ} L (θ) = E_{e \sim ρ} [\nabla_{θ} ℓ (e; θ)]$ when $D$ 's empirical distribution equals $ρ$ , and explain in one sentence why PER breaks this and needs $w_{i}$ .

Recall Solution

Let $D = {e_{1}, \dots, e_{N}}$ with empirical distribution matching $ρ$ . Draw one index $i$ uniformly ( $i \sim U (D)$ ): $Pr (i) = \frac{1}{N}$ . The expected gradient of a single uniform draw is $E_{i \sim U} [\nabla_{θ} ℓ (e_{i}; θ)] = \sum_{i = 1}^{N} \frac{1}{N} \nabla_{θ} ℓ (e_{i}; θ) = \frac{1}{N} \sum_{i} \nabla_{θ} ℓ (e_{i}; θ),$ which is precisely the empirical mean = Monte-Carlo estimate of $E_{e \sim ρ} [\nabla_{θ} ℓ]$ . So the estimate is unbiased. Why PER breaks it: PER draws $i$ with probability $P (i) \neq = \frac{1}{N}$ , so $E [\nabla ℓ] = \sum_{i} P (i) \nabla ℓ_{i} \neq = \frac{1}{N} \sum_{i} \nabla ℓ_{i}$ — a biased mean; multiplying by $w_{i} \propto \frac{1}{N P ( i )}$ rescales each term back so the weighted expectation again equals the uniform mean.

Exercise 5.2

Design. Under PER with $α = 1$ , a transition with a large one-off $∣ δ ∣$ (caused by a noisy reward, not genuine learning value) gets sampled repeatedly and dominates the buffer's compute. Propose two concrete mechanisms from the parent's toolbox that mitigate this, and justify each.

Recall Solution

Mechanism 1 — lower $α$ (e.g. $0.5$ ). Since $P (i) \propto p_{i}^{α}$ , reducing $α$ flattens the distribution, capping how much any single noisy transition can dominate (Ex 4.2 showed the ratio is $(\cdot)^{α}$ ). It trades focus for robustness. Mechanism 2 — the additive $ϵ$ and periodic priority refresh. The $ϵ$ floor keeps every transition sample-able so a spuriously-high one is eventually re-evaluated; when it is resampled its priority is recomputed with the current $θ$ , and if the large error was noise, $∣ δ ∣$ drops and its priority collapses back to normal. Together they prevent permanent lock-on to one noisy sample.

Exercise 5.3

Edge case — new transitions. A brand-new transition has just been inserted into a PER buffer; the network has never computed a TD error for it, so it has no $δ$ . (a) What initial priority does standard PER assign it, and why? (b) A buffer holds $N = 5$ transitions with priorities $p = (4, 1, 1, 1, 1)$ (the $4$ is such a freshly-inserted transition given max priority; $ϵ$ already included). With $α = 1$ compute its sampling probability. (c) With $β = 1$ compute the raw IS weights of the high- and a low-priority transition and show that $P (i) w_{i}^{raw}$ is equal across them — the hallmark of a fully-corrected ( $β = 1$ ) estimate.

Recall Solution

(a) Initial priority = the current maximum priority in the buffer, $p_{new} = max_{j} p_{j}$ . Why: with no $δ$ we cannot rank it, and we want to guarantee it is sampled at least once soon (so its real $δ$ gets measured). Giving it the maximum priority makes it maximally likely to be picked next; after that first visit its priority is overwritten with the true $∣ δ ∣ + ϵ$ . Initialising to $0$ or the mean would risk a genuinely important transition never being seen. (b) Sampling probability. Sum of priorities $= 4 + 1 + 1 + 1 + 1 = 8$ . With $α = 1$ , $p_{i}^{α} = p_{i}$ , so $P_{high} = \frac{4}{8} = 0.5, P_{low} = \frac{1}{8} = 0.125.$ (c) Raw IS weights ( $β = 1$ ): $w_{i}^{raw} = (\frac{1}{N} \cdot \frac{1}{P ( i )})^{1} = \frac{1}{N P ( i )}$ . $w_{high}^{raw} = \frac{1}{5 \cdot 0.5} = 0.4, w_{low}^{raw} = \frac{1}{5 \cdot 0.125} = 1.6.$ Normalising by the max ( $= 1.6$ ): $w_{high}^{norm} = 0.4/1.6 = 0.25$ , $w_{low}^{norm} = 1.0$ . The check: compute $P (i) \cdot w_{i}^{raw}$ for each: $high: 0.5 \cdot 0.4 = 0.2, low: 0.125 \cdot 1.6 = 0.2.$ They are equal ( $= 0.2$ ). At $β = 1$ the sampling frequency times the weight is constant across transitions, i.e. the weighted estimate reproduces the uniform (unbiased) mean exactly. That is the whole purpose of the IS weight.

Recall One-line summaries to self-quiz

$U (D)$ means what? ::: The uniform sampling operator — pick each stored transition with equal probability $1/ N$ . $α$ controls what? ::: The sharpness of prioritisation — $0$ uniform, $1$ fully greedy. $β$ controls what? ::: How fully the importance-sampling bias is corrected — anneal to $1$ . Initial priority of a brand-new transition? ::: The current maximum priority, so it is sampled at least once soon. Why normalise $w_{i}$ by $max_{j} w_{j}$ ? ::: To keep every weight in $(0, 1]$ so updates only shrink, preserving stability. Terminal-state target formula? ::: $y = r$ (the $(1 - d)$ factor zeroes the bootstrap). Replay is valid for which method class? ::: Off-policy (DQN, DDPG, SAC).