Actor-critic and advantage estimation

You are learning to balance a pole on a cart. You last 140 steps, then the pole falls. REINFORCE (Chapter 7) now goes back over all 140 actions and nudges each one by the same kind of signal: “from here on, you collected this much reward.” Step 12, where you made a fine correction, and step 135, where you made the fatal lurch, get credit through numbers that differ only because one is computed over a longer stretch of the future. To learn which steps were good, you need many, many episodes, because only averaging can separate the two.

Now imagine a coach standing next to you. The coach never touches the cart, but after every single step says “that went better than I expected” or “that went worse.” Step 12: better. Step 135: much worse. You would learn far faster. This chapter builds that coach. It is a second learned function, the critic, that predicts how well things will go from each state, so that every step can be judged against a prediction instead of against the noisy return of the whole episode. The policy being trained is called the actor. Together they make an actor-critic method.

This is not a modern idea. In 1983, Barto, Sutton and Anderson balanced a simulated pole with an “adaptive critic element” that learned to predict trouble and turned that prediction into an internal reward for a separate action-selecting element. The cartpole.py file you will use in the lab simulates the same physics they used. What is modern is the question this chapter spends most of its time on: given a critic that is wrong (and it always is), how should you combine its predictions with the real rewards you observed? The answer, generalized advantage estimation (GAE), has one knob, $\lambda$. It is the advantage estimator inside PPO (Chapter 9) and inside PPO-based RLHF for language models (Chapter 12).

Where REINFORCE leaves us

From Chapter 7, the policy gradient has this shape:

$$\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\Big[\sum_{t} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, \Psi_t\Big].$$

The score $\nabla_\theta \log \pi_\theta(a_t \mid s_t)$ says which way to move $\theta$ to make $a_t$ more likely. The weight $\Psi_t$ says how much, and whether to make it more likely or less. Everything in this chapter is about choosing $\Psi_t$. Here is the menu (the GAE paper by Schulman et al. opens with this same list):

Weight $\Psi_t$	Name	Unbiased?	Needs
$G_0$	total return of the episode	yes	nothing
$G_t$	reward-to-go	yes	nothing
$G_t - b(s_t)$	reward-to-go with a baseline	yes	a baseline
$Q^\pi(s_t, a_t)$	action value	yes	the true $Q^\pi$
$A^\pi(s_t, a_t)$	advantage	yes	the true $A^\pi$
$r_t + \gamma V^\pi(s_{t+1}) - V^\pi(s_t)$	TD error	yes	the true $V^\pi$

Chapter 7 took you down to the third row. You saw that a baseline $b(s_t)$ can be subtracted without adding bias, and that a good baseline cuts variance a lot. You also saw that the best simple baseline is close to the expected return from $s_t$, which is $V^\pi(s_t)$. So the third row with the best baseline is $G_t - V^\pi(s_t)$. That is already an estimate of the advantage, the fifth row. This chapter makes that connection explicit and then goes further. In the last three rows the weights are “true” functions we don’t have, so we will learn them, and then decide how much to trust what we learned.

The advantage: was that action better than usual?

Recall the two value functions from Chapter 3. $V^\pi(s)$ is the expected return if you start in $s$ and follow $\pi$. $Q^\pi(s, a)$ is the expected return if you start in $s$, take action $a$ once, and then follow $\pi$. The advantage is their difference:

$$A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s).$$

In words: how much better is action $a$ than what the policy does in $s$ on average? Positive means “better than my usual”, negative means “worse than my usual”.

A worked example

Take one state $s$ with three actions. The policy picks them with probabilities $\pi = (0.5,\ 0.3,\ 0.2)$, and their action values are $Q^\pi = (1,\ 3,\ 0)$. Then

$$V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a) = 0.5 \cdot 1 + 0.3 \cdot 3 + 0.2 \cdot 0 = 1.4,$$

and the advantages are $A^\pi = (1 - 1.4,\ 3 - 1.4,\ 0 - 1.4) = (-0.4,\ +1.6,\ -1.4)$.

Two things to notice:

• The advantages average to zero under the policy: $0.5(-0.4) + 0.3(1.6) + 0.2(-1.4) = -0.2 + 0.48 - 0.28 = 0$. This always holds, because $V^\pi(s)$ is by definition the $\pi$-weighted average of $Q^\pi(s, \cdot)$. So the advantage is the action value with its “typical level” removed.
• The most likely action has a negative advantage. The policy picks action 1 half the time, yet action 2 is much better. A gradient step weighted by $A^\pi$ lowers the probability of action 1 every time it is sampled and raises action 2’s whenever it is sampled. That is exactly the correction you want.

Now compare with weighting by $Q^\pi$ instead. All three $Q$-values are $\ge 0$. Every sampled action gets pushed up, just by different amounts. On average the pushes still come out right: $Q^\pi$ is $A^\pi$ plus the constant $1.4$, and a constant added to every weight averages out (shown in the box below). But single samples are misleading. When action 1 is drawn (half the time), the update pushes it up with weight 1, although it should go down. When action 3 is drawn (20% of the time), the weight is 0 and nothing happens, although action 3 should go down too. So on 70% of samples the update is wrong or useless, and only averaging over many samples sorts it out. That is variance.

The critic: learning V

To use advantages we have to estimate them, and the cheapest route needs only one learned function, the state value. Here is why. You never need $Q^\pi(s_t, a_t)$ as a separate function, because you watched what actually happened after $a_t$: you got $r_t$ and landed in $s_{t+1}$. The one-sample estimate $r_t + \gamma V^\pi(s_{t+1})$ of $Q^\pi(s_t, a_t)$ is right there. So the plan is:

• Learn $V_\phi(s) \approx V^\pi(s)$, a network with parameters $\phi$. This is the critic.
• Use it to turn observed rewards into advantage estimates $\hat{A}_t$ for the actor $\pi_\theta$.

Learning $V_\phi$ is a regression problem you have already solved twice. In Chapter 5 you estimated values by Monte Carlo (target $G_t$) and by TD(0) (target $r_t + \gamma V(s_{t+1})$). In Chapter 6 you did it with a neural network and the semi-gradient rule: compute a target $\hat{R}_t$, treat it as a constant, and minimize

$$L_V(\phi) = \tfrac{1}{2}\big(V_\phi(s_t) - \hat{R}_t\big)^2 .$$

With the TD(0) target, the gradient step on this loss is $\phi \leftarrow \phi + \alpha_\phi\, \delta_t \nabla_\phi V_\phi(s_t)$, where

$$\delta_t = r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)$$

is the TD error. Remember this quantity. In the next section it becomes the actor’s weight too.

Why learn $V$ rather than $Q$? $V$ is a function of the state only, so it is a smaller object to learn, and it does not need one output per action. With two actions (CartPole) that hardly matters. With a vocabulary of 100,000 tokens it matters a lot: Chapter 6 explained why per-action value methods are rarely used for LLMs.

The TD error is a one-sample advantage

Here is the key fact. Suppose for a moment the critic is perfect, $V = V^\pi$. Average the TD error over what can happen after $a_t$, namely the reward $r_t$ and the next state $s_{t+1}$:

$$\mathbb{E}\big[\delta_t \mid s_t, a_t\big] = \mathbb{E}\big[r_t + \gamma V^\pi(s_{t+1}) \mid s_t, a_t\big] - V^\pi(s_t) = Q^\pi(s_t, a_t) - V^\pi(s_t) = A^\pi(s_t, a_t).$$

The middle equality is the Bellman equation for $Q^\pi$ from Chapter 3: the action value is the expected immediate reward plus the discounted value of where you land. So with a perfect critic, the TD error is an unbiased one-sample estimate of the advantage. It is noisy only through one step of randomness (one reward, one transition). Compare $G_t - V^\pi(s_t)$, which is noisy through every reward and every action for the rest of the episode.

There is a catch, and it is the theme of the rest of the chapter. The critic is not perfect. With $V_\phi \ne V^\pi$, $\delta_t$ is a biased advantage estimate. If the critic wrongly thinks $s_{t+1}$ is a great state, every action leading there looks great.

A running example

We will use one short episode for the rest of the chapter, so you can check every formula by hand. It has four steps and a single reward of 1 at the very end (think of a four-token answer that is graded correct). Take $\gamma = 1$. The critic’s values along the way are shown below. $s_4$ is terminal, so $V(s_4) = 0$.

$t$	$r_t$	$V(s_t)$	$V(s_{t+1})$	$\delta_t = r_t + V(s_{t+1}) - V(s_t)$
0	0	0.5	0.4	$-0.1$
1	0	0.4	0.8	$+0.4$
2	0	0.8	0.6	$-0.2$
3	1	0.6	0 (terminal)	$+0.4$

Read the critic’s values as its running forecast of success. It starts at 50%. After step 0 it drops to 40%, so that move looked slightly bad. Step 1 raised it to 80%, which looks like a good move. Step 2 lowered it to 60%. Step 3 got the reward, a pleasant surprise of 0.4 relative to the forecast. The TD errors are exactly these changes of mind: they blame steps 0 and 2 a little and credit steps 1 and 3.

Monte Carlo sees it differently. The return from every step is $G_t = 1$, so $G_t - V(s_t) = (0.5,\ 0.6,\ 0.2,\ 0.4)$: every step gets positive credit, because the episode succeeded. Which assignment is right? It depends on whether the critic is right. If its forecasts are accurate, the TD errors point at the moves that actually changed the odds. If its forecasts are garbage, the TD errors are garbage too, and Monte Carlo is the only honest signal.

A first actor-critic

You now have enough for a complete algorithm. The actor’s weight is $\delta_t$, the critic learns by TD(0), and both update after every step:

One-step actor-critic (online)
Initialise actor parameters θ and critic parameters φ
for each episode:
    s ← initial state
    while s is not terminal:
        sample a ~ π_θ(· | s);  take it; observe r and s′
        δ ← r + γ V_φ(s′) − V_φ(s)          # V_φ(s′) = 0 if s′ is terminal
        φ ← φ + α_φ · δ · ∇_φ V_φ(s)          # critic: semi-gradient TD(0)
        θ ← θ + α_θ · δ · ∇_θ log π_θ(a | s)  # actor: policy gradient, Â = δ
        s ← s′

(Sutton & Barto’s version also multiplies the actor step by $\gamma^t$, which is what the discounted objective strictly requires. Almost every deep-RL implementation drops that factor.)

Compared with REINFORCE, this algorithm:

• learns during the episode. It needs no complete return, so it works for very long or never-ending tasks.
• has much lower variance per update, because each weight involves one step of randomness.
• is biased whenever the critic is wrong, which is always, especially early in training.
• has two learners chasing each other. As the actor changes, $V^\pi$ changes, so the critic’s target moves. This is generalized policy iteration from Chapter 4: the critic does approximate policy evaluation and the actor does approximate policy improvement, interleaved at a fine grain.

The bias is the real problem. One step of real reward and everything else from the critic is a lot of trust to put in a network that started out as random weights. You want a way to use more real rewards when the critic is untrustworthy, and fewer when it is good.

n-step advantages: a dial between TD and Monte Carlo

The middle ground is to look ahead $n$ real steps and then hand over to the critic. You met this dial in Chapter 5 as a target for learning values (written $G_{t:t+n}$ there). Here it becomes an advantage estimate for the actor. The n-step return is

$$G^{(n)}_t = r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1} + \gamma^n V(s_{t+n}),$$

and the n-step advantage is $\hat{A}^{(n)}_t = G^{(n)}_t - V(s_t)$. If the episode ends before step $t + n$, use the rewards up to the end and $V(\text{terminal}) = 0$. That is just the Monte Carlo return.

There is a neat identity that makes this easy to compute and reason about. The n-step advantage is the discounted sum of the next $n$ TD errors:

$$\hat{A}^{(n)}_t = \sum_{l=0}^{n-1} \gamma^l \delta_{t+l}.$$

∂ Why the n-step advantage is a sum of TD errors

Write out the sum and group terms. With $\delta_{t+l} = r_{t+l} + \gamma V(s_{t+l+1}) - V(s_{t+l})$:

$$\sum_{l=0}^{n-1} \gamma^l \delta_{t+l} = \sum_{l=0}^{n-1} \gamma^l r_{t+l} \;+\; \sum_{l=0}^{n-1} \gamma^{l+1} V(s_{t+l+1}) \;-\; \sum_{l=0}^{n-1} \gamma^l V(s_{t+l}).$$

Shift the index in the middle sum ($m = l + 1$): it becomes $\sum_{m=1}^{n} \gamma^m V(s_{t+m})$. The last sum is $\sum_{m=0}^{n-1} \gamma^m V(s_{t+m})$. They share the terms $m = 1, \dots, n-1$, which cancel, leaving $\gamma^n V(s_{t+n})$ from the middle sum and $-V(s_t)$ from the last. So

$$\sum_{l=0}^{n-1} \gamma^l \delta_{t+l} = \sum_{l=0}^{n-1} \gamma^l r_{t+l} + \gamma^n V(s_{t+n}) - V(s_t) = G^{(n)}_t - V(s_t).$$

Every intermediate value appears once with a plus sign (as “next state” of one step) and once with a minus sign (as “current state” of the next step), so the intermediate values all cancel.

Two limits:

• $n = 1$: $\hat{A}^{(1)}_t = \delta_t$, the one-step TD error.
• $n \to \infty$ (or $n$ reaching past the end of the episode): $\hat{A}^{(\infty)}_t = G_t - V(s_t)$, Monte Carlo with a baseline. This is REINFORCE with the critic as its baseline.

In the running example with $n = 2$ and $\gamma = 1$: $\hat{A}^{(2)}_0 = \delta_0 + \delta_1 = -0.1 + 0.4 = 0.3$. Check against the definition: $r_0 + r_1 + V(s_2) - V(s_0) = 0 + 0 + 0.8 - 0.5 = 0.3$. Both give 0.3.

Why $n$ trades bias for variance. Look at where the critic enters $\hat{A}^{(n)}_t$: only through $V(s_t)$ and $\gamma^n V(s_{t+n})$. The first is a state-only baseline and is harmless (more on this below). The second is discounted by $\gamma^n$ and, if the critic is wrong, contributes bias. Larger $n$ pushes the critic further away and reduces its influence. But each extra step adds one more random reward and one more random action to the sum, which adds variance. Small $n$: low variance, high bias. Large $n$: low bias, high variance.

The A3C algorithm of Mnih et al. (2016) used exactly this. Each worker ran the policy for up to $t_\text{max} = 5$ steps, then gave every state in that segment the longest n-step return available inside the segment (5 steps for the first state, 4 for the next, and so on).

Generalized advantage estimation

Which $n$ should you use? There is no single right answer: the best $n$ depends on how good the critic is, and that changes during training. GAE (Schulman et al., 2015) avoids the choice. It takes all the n-step estimates and averages them with exponentially decaying weights:

$$\hat{A}^{\text{GAE}(\gamma, \lambda)}_t = (1 - \lambda)\big(\hat{A}^{(1)}_t + \lambda \hat{A}^{(2)}_t + \lambda^2 \hat{A}^{(3)}_t + \cdots\big), \qquad 0 \le \lambda \le 1.$$

The weights $(1-\lambda)\lambda^{n-1}$ sum to one, so this is a proper weighted average. Plug in the TD-error form of each $\hat{A}^{(n)}_t$ and the average collapses to something very simple.

∂ From the average of n-step advantages to the sum of TD errors

Substitute $\hat{A}^{(n)}_t = \sum_{l=0}^{n-1} \gamma^l \delta_{t+l}$:

$$(1-\lambda)\sum_{n=1}^{\infty} \lambda^{n-1} \hat{A}^{(n)}_t = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \sum_{l=0}^{n-1} \gamma^l \delta_{t+l}.$$

Swap the order of summation. A given $\delta_{t+l}$ appears in every $\hat{A}^{(n)}_t$ with $n \ge l + 1$, so

$$= \sum_{l=0}^{\infty} \gamma^l \delta_{t+l} \cdot (1-\lambda) \sum_{n=l+1}^{\infty} \lambda^{n-1} = \sum_{l=0}^{\infty} \gamma^l \delta_{t+l} \cdot (1-\lambda) \frac{\lambda^{l}}{1-\lambda} = \sum_{l=0}^{\infty} (\gamma\lambda)^l \delta_{t+l}.$$

The inner sum is a geometric series: $\sum_{n=l+1}^{\infty} \lambda^{n-1} = \lambda^l (1 + \lambda + \lambda^2 + \cdots) = \lambda^l / (1 - \lambda)$, valid for $\lambda \lt 1$. The case $\lambda = 1$ follows as a limit, or directly from the Monte Carlo identity below.

Finite episodes. If the episode ends at step $T$, define $\delta_{k} = 0$ for $k \ge T$ (no rewards, and $V(\text{terminal}) = 0$). Every $\hat{A}^{(n)}_t$ with $t + n \ge T$ is then the same Monte Carlo advantage, the formula above still holds, and the sum stops at $l = T - t - 1$.

The two ends of the dial:

• $\lambda = 0$: only the $l = 0$ term survives. $\hat{A}_t = \delta_t$, the one-step TD error. Lowest variance, and the most trust in the critic.
• $\lambda = 1$: $\hat{A}_t = \sum_l \gamma^l \delta_{t+l} = G_t - V(s_t)$ by the telescoping identity. This is Monte Carlo with the critic as a baseline: no trust in the critic beyond its role as a baseline, and the most variance. (Exercise 8.3 asks you to prove it.)

Computing it: one backward pass

You never evaluate the infinite sum. Peel off the first term and the rest is the same quantity one step later:

$$\hat{A}_t = \delta_t + \gamma\lambda\, \hat{A}_{t+1}.$$

So you start at the end of the rollout and walk backward. This is an exponential filter run in reverse time: the sequence of TD errors goes in, and each output is the current input plus a decayed copy of the next output. How far ahead does it look? The weights $(\gamma\lambda)^l$ fall by a factor $e$ in about $1/(1 - \gamma\lambda)$ steps. PPO’s default settings, $\gamma = 0.99$ and $\lambda = 0.95$, give $\gamma\lambda \approx 0.94$, a look-ahead of roughly 17 steps.

The running example with $\lambda = 0.5$ ($\gamma = 1$), walking backward from the last step:

$$\hat{A}_3 = \delta_3 = 0.4, \quad \hat{A}_2 = -0.2 + 0.5 \cdot 0.4 = 0.0, \quad \hat{A}_1 = 0.4 + 0.5 \cdot 0.0 = 0.4, \quad \hat{A}_0 = -0.1 + 0.5 \cdot 0.4 = 0.1 .$$

All the estimators side by side:

$t$	$\delta_t$ ($\lambda = 0$)	2-step	GAE, $\lambda = 0.5$	MC, $\lambda = 1$
0	$-0.1$	$0.3$	$0.1$	$0.5$
1	$0.4$	$0.2$	$0.4$	$0.6$
2	$-0.2$	$0.2$	$0.0$	$0.2$
3	$0.4$	$0.4$	$0.4$	$0.4$

Look at step 2. One-step TD blames it (the critic’s forecast dropped). Monte Carlo credits it (the episode succeeded). GAE with $\lambda = 0.5$ sits in between and calls it neutral. The last row is the same in every column, because from step 3 only one step remains, so every estimator sees the same thing.

Episode boundaries and the critic’s target

In practice a rollout is a block of consecutive steps that can contain the end of one episode and the start of the next. The recursion must not leak advantage across that boundary. With $d_t = 1$ when the episode ended at step $t$:

$$\delta_t = r_t + \gamma (1 - d_t) V(s_{t+1}) - V(s_t), \qquad \hat{A}_t = \delta_t + \gamma\lambda (1 - d_t)\, \hat{A}_{t+1}.$$

GAE also hands you the critic’s regression target for free. $\hat{R}_t = \hat{A}_t + V(s_t)$ is the λ-return, an exponentially weighted average of all the n-step returns. If you have read about TD($\lambda$) in Sutton & Barto (chapter 12), this is the same object: GAE is TD($\lambda$)‘s weighting applied to advantages. Using $\hat{R}_t$ as the critic’s target means the critic and actor see the same blend of real rewards and bootstrapped values.

compute_gae(rewards, values, last_value, dones, γ, λ):     # arrays of length T
    A_next ← 0
    for t = T−1 down to 0:
        V_next ← last_value if t = T−1 else values[t+1]
        δ ← rewards[t] + γ · V_next · (1 − dones[t]) − values[t]
        A_next ← δ + γ · λ · (1 − dones[t]) · A_next
        advantages[t] ← A_next
    returns ← advantages + values           # λ-returns: the critic's targets
    return advantages, returns

Here last_value is the critic’s value of the state reached after the final row, $V(s_T)$. When the rollout stops in the middle of an episode (dones[T−1] = 0), the last step has no next row to read a value from, so it bootstraps from last_value instead.

This is Task 2 of the lab, and it runs in $O(T)$ time.

Seeing the trade-off

The claims so far are qualitative: small $\lambda$ trusts the critic, large $\lambda$ trusts the rewards, and the right choice depends on how good the critic is. The demo below lets you measure all of this exactly.

The world. Nothing is learned in this demo. The policy is fixed, and the only question is how well each estimator measures that policy’s advantages. A walker starts at height $x = 0$ and takes 12 steps. At each step the policy flips a fair coin: up (+1) or down (−1). The only reward is $r = 1$ on the last step, if the walker finishes at $x \ge 2$. With a fair coin that happens about 39% of the time. The world is small enough that we can compute $V^\pi$ and $Q^\pi$ exactly for every state, and also the exact mean and variance of any GAE estimate over all $2^{12} = 4{,}096$ possible episodes. There is no sampling noise in the readouts.

The critic. The demo’s critic is the true $V^\pi$ plus a fixed random mistake in every state, with size set by the “critic error σ” slider. At σ = 0 the critic is perfect. “New critic mistakes” draws a different set of mistakes of the same size.

The top panel shows one sampled episode: the path, then for each step a bar with this episode’s estimate $\hat{A}_t$, a whisker showing the mean ± one standard deviation you would get if you re-rolled the future from that step, and a thick dark tick for the target. Tap a column (or focus the plot and use the arrow keys) to see that step’s numbers. The bottom panel shows bias², variance and their sum, the mean squared error, averaged over every step of every possible episode, as a function of $\lambda$. The green triangle marks the best $\lambda$ for the current critic, and the dashed vertical line is the $\lambda$ you have selected.

λ (GAE)

0.90

γ (discount)

1.00

critic error σ

0.15

PlayNew episodeNew critic mistakesPerfect critic

this episode's Â_tmean ± 1 std over all futurestarget Q^π(s_t,a_t) − V(s_t)

bias²varianceMSE = bias² + variance

What to try: (1) Press Perfect critic. Every λ is unbiased and the best λ is 0. Why is the variance at λ = 0 exactly zero in this world? (2) Drag the critic error up to 0.4 and watch the green triangle slide right: a worse critic means you should lean on the real rewards. (3) At error 0.15, press Play at λ = 0 and then at λ = 1, and watch the bars at step 0 from episode to episode. (4) Lower γ to 0.9 and see what happens to the variance at λ = 1.

Some numbers to check against the demo, for its default critic: at σ = 0.15 and γ = 1, the MSE is 0.018 at $\lambda = 0$ (all bias, no variance) and 0.139 at $\lambda = 1$ (all variance, no bias). The minimum is about 0.012, near $\lambda \approx 0.4$. At σ = 0.4 the best $\lambda$ moves to about 0.7.

What the target is, and where bias comes from

You may have noticed that the target tick is $Q^\pi(s_t, a_t) - V(s_t)$, using the critic’s $V$ rather than the true $V^\pi$. Here is why that is the right target. Write the critic as the truth plus an error, $V = V^\pi + e$. Then each TD error splits into the true TD error plus error terms:

$$\delta_t = \delta^\pi_t + \gamma\, e(s_{t+1}) - e(s_t),$$

and summing with GAE’s weights gives (Exercise 8.5 walks through it)

$$\hat{A}_t = \underbrace{\sum_l (\gamma\lambda)^l \delta^\pi_{t+l}}_{\text{unbiased for } A^\pi(s_t, a_t)} \;-\; \underbrace{e(s_t)}_{\text{harmless}} \;+\; \underbrace{\sum_{m \ge 1} \gamma^m \lambda^{m-1}(1-\lambda)\, e(s_{t+m})}_{\text{the bias that matters}} .$$

• The $-e(s_t)$ term depends only on the state, so it acts like a baseline and cannot bias the policy gradient (Chapter 7’s argument again). That is why the demo measures error against $Q^\pi - V$ and not against $A^\pi$: a wrong baseline can cost some variance, but it adds no bias.
• The real bias comes from the critic’s mistakes at future states, weighted by $\gamma^m \lambda^{m-1}(1 - \lambda)$. At $\lambda = 1$ every weight is zero: Monte Carlo is unbiased no matter how bad the critic is. At $\lambda = 0$ the whole weight lands on $e(s_{t+1})$: one-step TD inherits the critic’s next-state mistake in full. In between, the mistakes of many future states are averaged, and in the demo (where mistakes in different states are independent) they partly cancel.

Where variance comes from. $\hat{A}_t$ adds up the random TD errors $\delta_t, \delta_{t+1}, \dots$ with weights $(\gamma\lambda)^l$. Each one carries the randomness of one more reward and one more action, so the variance grows as the effective window $1/(1 - \gamma\lambda)$ grows. In the demo’s world, transitions are deterministic and the reward depends only on the final position, so $\delta_t$ is fully determined by $(s_t, a_t)$, and the variance at $\lambda = 0$ is exactly zero. In most environments it isn’t, but the shape of the curve is the same.

A2C: the practical algorithm

The one-step actor-critic updates after every single transition. That is slow on modern hardware, and consecutive transitions are strongly correlated, which is the problem Chapter 6 solved with a replay buffer. The standard deep-RL recipe instead runs many environments in parallel and updates on batches.

A3C (Asynchronous Advantage Actor-Critic, Mnih et al., 2016) ran many CPU threads, each with its own copy of the environment. Each thread computed gradients on its own short rollout and applied them to shared parameters without locks. Because the threads were in different parts of their episodes, a batch of their data was far less correlated than one long trajectory. That made a replay buffer unnecessary and kept the method on-policy. A3C used n-step advantages with $t_\text{max} = 5$ and an entropy bonus (below). A2C is the synchronous version: step all $N$ environments together, wait for every one, then make one batched update. OpenAI’s Baselines team reported in 2017 that their synchronous A2C performed at least as well as their asynchronous implementation, and it uses a GPU much better. A2C is what people usually implement today, and it is what you will build in the lab.

A2C with GAE
Initialise actor π_θ, critic V_φ, and N environments
repeat:
    # 1. Rollout: n_steps in each of N environments with the current policy
    for k = 1..n_steps:
        a ~ π_θ(· | s) in every environment;  record s, a, r, done, V_φ(s)
    # 2. Advantages and targets (no gradients here)
    Â, R̂ ← compute_gae(rewards, values, V_φ(last states), dones, γ, λ)
    Â ← (Â − mean(Â)) / (std(Â) + 1e-8)          # advantage normalization
    # 3. One gradient step on the combined loss over the N · n_steps samples
    loss ← policy_loss + c_v · value_loss − c_e · entropy
    take one optimizer step on (θ, φ); throw the batch away

The loss, term by term

For a batch of $B$ transitions, with $\hat{A}_b$ and $\hat{R}_b$ treated as constants:

$$L(\theta, \phi) = \underbrace{-\frac{1}{B}\sum_b \log \pi_\theta(a_b \mid s_b)\, \hat{A}_b}_{\text{policy loss}} \;+\; c_v \underbrace{\frac{1}{B}\sum_b \big(V_\phi(s_b) - \hat{R}_b\big)^2}_{\text{value loss}} \;-\; c_e \underbrace{\frac{1}{B}\sum_b \mathcal{H}\big(\pi_\theta(\cdot \mid s_b)\big)}_{\text{entropy bonus}} .$$

• Policy loss. Its gradient is minus the policy-gradient estimate, so gradient descent on it is gradient ascent on $J$. It is a “loss” only in the sense that differentiating it gives the right update. Its value is not a measure of how well you are doing.
• Value loss. Regression of the critic onto the λ-returns, weighted by $c_v$ (often 0.5).
• Entropy bonus. $\mathcal{H}(\pi(\cdot \mid s)) = -\sum_a \pi(a \mid s) \log \pi(a \mid s)$ is largest for a uniform policy and zero for a deterministic one. Rewarding it slightly ($c_e \approx 0.01$) slows the policy’s collapse onto one action before it has explored enough. A deterministic policy also stops producing varied data, and its score $\nabla \log \pi$ goes to zero, so learning stalls. The idea goes back to Williams & Peng (1991). The same collapse is a central problem in RL for reasoning models (Chapter 19).

Detach the targets. $\hat{A}_b$ and $\hat{R}_b$ were computed from $V_\phi$, but they must be treated as constants. If gradients flowed into $\hat{A}_b$ through the policy loss, the actor’s loss could be lowered by changing the critic to make advantages look different. That would be nonsense. If they flowed into $\hat{R}_b$, you would get a full-gradient TD method with different behavior from the semi-gradient method we analyzed (Chapter 6 explains why semi-gradient is the standard).

Advantage normalization

Almost every implementation rescales each batch of advantages to mean 0 and standard deviation 1 before the policy loss. There are two reasons, and both are worth understanding.

1. Scale. The size of the policy step is (learning rate) × (advantage size). Advantage sizes vary hugely across tasks and over training. In CartPole they can be dozens of reward units early on and much smaller later. Normalizing makes the learning rate mean roughly the same thing throughout.
2. Sign. Subtracting the batch mean is one more baseline. Early in training the critic outputs about 0 while true values are large and positive. Then every $\hat{A}_t$ is positive and every sampled action gets pushed up, which is the high-variance situation from the worked example. After centering, roughly half the actions are pushed up and half down.

It is not free. Strictly, the normalized estimator is no longer an unbiased policy gradient: the batch statistics depend on the samples, and the effective step size changes from batch to batch. In practice the gain in stability far outweighs this. Keep the idea in mind: GRPO’s “subtract the group mean, divide by the group std” (Chapter 15) is the same normalization done per prompt. Whether to divide by the std at all is one of the debates in Chapter 16.

Shared or separate networks?

	Separate actor and critic	Shared trunk, two heads
Compute and memory	two networks	one network, cheaper
Features	each learns its own	the critic’s features can help the actor, and vice versa
Interference	none	the value loss’s gradients flow into the shared trunk and can swamp the policy’s, so $c_v$ needs tuning
Typical use	small control tasks; the lab default	Atari-style pixel inputs (A3C shared a convolutional trunk)

Andrychowicz et al. (2020) ran a large ablation study of choices like this for on-policy methods and is worth a look once you have done the lab. For language models the question takes a different form. The “critic” in PPO-RLHF is either a separate full-size model or a scalar head on the policy, and its memory cost is one reason critic-free methods took over (Chapter 15).

One more detail: time limits are not terminal states

CartPole stops every episode at 500 steps. The pole has not fallen; we simply stopped watching. If you mark that step as terminal ($d_t = 1$, no bootstrap), the critic is taught that a perfectly balanced pole at step 500 is worth 0, while the same physical state at step 100 is worth a lot. Its input does not include the time, so it cannot fit both, and the error leaks into the advantages. The fix (Pardo et al., 2018) is to separate termination (a true end: bootstrap with 0) from truncation (a time-out: bootstrap with $V(s_{T})$). The lab’s rollout code does this, and Exercise 8.9 asks you to explain it.

What A2C still gets wrong: each batch is used for one gradient step and then discarded. This wastes data, and the size of a safe step is hard to know in advance: a single overly large step can wreck the policy, and the next batch is then collected by the wrecked policy. Chapter 9 keeps everything from this chapter (GAE, the value loss, the entropy bonus, normalization) and fixes exactly that.

Summary

• The policy gradient weights each $\nabla \log \pi(a_t \mid s_t)$ by some $\Psi_t$. The advantage $A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$ is the ideal weight. It has the same expected gradient as $Q^\pi$, averages to zero under $\pi$, and carries only the “which action was better” signal.
• An actor-critic method learns a critic $V_\phi \approx V^\pi$ by regression (TD or λ-return targets) and uses it to estimate advantages for the actor $\pi_\theta$.
• The TD error $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ is an unbiased one-sample advantage estimate if $V = V^\pi$, and biased otherwise. It is low-variance because it has only one step of randomness.
• n-step advantages satisfy $\hat{A}^{(n)}_t = \sum_{l \lt n} \gamma^l \delta_{t+l}$: more real rewards means less critic bias and more variance.
• GAE averages all n-step estimates: $\hat{A}_t = \sum_l (\gamma\lambda)^l \delta_{t+l}$, computed backward via $\hat{A}_t = \delta_t + \gamma\lambda(1-d_t)\hat{A}_{t+1}$. $\lambda = 0$ is one-step TD, $\lambda = 1$ is Monte Carlo minus a baseline. $\hat{A}_t + V(s_t)$ is the λ-return, the critic’s target.
• Critic error enters GAE’s bias through future states with weight $\gamma^m\lambda^{m-1}(1-\lambda)$. λ sets how much you trust the critic. $\lambda \approx 0.95$ is a robust default.
• A2C: parallel environments, short rollouts, GAE, normalized advantages, and loss = policy loss + $c_v$ × value loss − $c_e$ × entropy. Advantages and targets are detached. Truncation is not termination.
• In LLM training, PPO-RLHF uses a per-token value head and GAE (often $\gamma = 1$). GRPO-style methods drop the critic and use group-average rewards as the baseline.

Exercises

Exercise 8.1Advantages by handPen & paper●○○

In a state $s$ with three actions, $\pi(\cdot \mid s) = (0.2,\ 0.5,\ 0.3)$ and $Q^\pi(s, \cdot) = (2,\ 1,\ 4)$.

1. Compute $V^\pi(s)$ and the three advantages.
2. Check that $\sum_a \pi(a \mid s) A^\pi(s,a) = 0$.
3. The agent samples the most likely action, action 2 (probability 0.5). Does a REINFORCE update weighted by $Q^\pi(s, a_2)$ raise or lower its probability? What about one weighted by $A^\pi(s, a_2)$?

Solution

1. $V^\pi(s) = 0.2 \cdot 2 + 0.5 \cdot 1 + 0.3 \cdot 4 = 0.4 + 0.5 + 1.2 = 2.1$. The advantages are $A = (2 - 2.1,\ 1 - 2.1,\ 4 - 2.1) = (-0.1,\ -1.1,\ +1.9)$.
2. $0.2(-0.1) + 0.5(-1.1) + 0.3(1.9) = -0.02 - 0.55 + 0.57 = 0$. This holds for any policy, because $V^\pi(s) = \sum_a \pi(a \mid s) Q^\pi(s,a)$ by definition, so $\sum_a \pi(a \mid s)\,(Q^\pi(s,a) - V^\pi(s)) = V^\pi(s) - V^\pi(s) = 0$.
3. With weight $Q^\pi(s, a_2) = 1 \gt 0$, the update moves $\theta$ along $+\nabla \log \pi(a_2 \mid s)$, which raises $\pi(a_2 \mid s)$, even though $a_2$ is the worst action. Only other samples (action 3, with weight 4) can undo this on average. With weight $A^\pi(s, a_2) = -1.1$, the update lowers $\pi(a_2 \mid s)$ on this very sample. Same expected gradient, much less variance.

I've done this one

Exercise 8.2TD, n-step and GAE advantages on a short episodePen & paper●○○

A three-step episode with $\gamma = 0.9$ has rewards $r_0 = 1$, $r_1 = 0$, $r_2 = 2$, and then terminates. The critic says $V(s_0) = 2.0$, $V(s_1) = 1.5$, $V(s_2) = 1.0$, and $V(s_3) = 0$ (terminal).

1. Compute $\delta_0, \delta_1, \delta_2$.
2. Compute the Monte Carlo advantages $G_t - V(s_t)$ for $t = 0, 1, 2$, and check that $G_0 - V(s_0) = \delta_0 + \gamma\delta_1 + \gamma^2\delta_2$.
3. Compute the 2-step advantage $\hat{A}^{(2)}_0$ in two ways: from its definition and as $\delta_0 + \gamma\delta_1$.
4. Compute GAE with $\lambda = 0.5$ for all three steps using the backward recursion.

Hint

Work backward for the returns: $G_2 = r_2$, $G_1 = r_1 + \gamma G_2$, and so on. For GAE, $\gamma\lambda = 0.45$.

Solution

1. $\delta_0 = 1 + 0.9 \cdot 1.5 - 2.0 = 0.35$. $\delta_1 = 0 + 0.9 \cdot 1.0 - 1.5 = -0.6$. $\delta_2 = 2 + 0.9 \cdot 0 - 1.0 = 1.0$.
2. $G_2 = 2$, $G_1 = 0 + 0.9 \cdot 2 = 1.8$, $G_0 = 1 + 0.9 \cdot 1.8 = 2.62$. The advantages are $G_t - V(s_t) = (0.62,\ 0.3,\ 1.0)$. Check: $0.35 + 0.9(-0.6) + 0.81(1.0) = 0.35 - 0.54 + 0.81 = 0.62$. They match.
3. Definition: $r_0 + \gamma r_1 + \gamma^2 V(s_2) - V(s_0) = 1 + 0 + 0.81 \cdot 1.0 - 2.0 = -0.19$. Sum of TD errors: $0.35 + 0.9 \cdot (-0.6) = -0.19$. Both give $-0.19$.
4. $\hat{A}_2 = \delta_2 = 1.0$. $\hat{A}_1 = -0.6 + 0.45 \cdot 1.0 = -0.15$. $\hat{A}_0 = 0.35 + 0.45 \cdot (-0.15) = 0.2825$.

Notice how different the estimates for step 0 are: $+0.35$ (TD), $-0.19$ (2-step), $+0.28$ (GAE 0.5), $+0.62$ (MC). They are all “advantage estimates”, and they disagree because they trust the critic to different degrees. The 2-step estimate is the only negative one because it hands over to the critic at $s_2$, where $V(s_2) = 1.0$, while the actual return from $s_2$ was 2. On this episode the critic’s forecast for $s_2$ was too low, and every estimator that leans on it inherits that.

I've done this one

Exercise 8.3GAE at λ = 1 telescopes to Monte CarloPen & paper●●○

1. An episode terminates at step $T$ (so $V(s_T) = 0$). Prove that for every $t \lt T$,

$$\sum_{l=0}^{T-t-1} \gamma^l \delta_{t+l} = G_t - V(s_t).$$

2. Now suppose the rollout is cut off at step $T$ without the episode ending, so the last TD error bootstraps from $V(s_T) \ne 0$. What does the same sum equal? Interpret the result in words.

Hint

Expand each $\delta$ and collect the coefficients of each $V(s_k)$. Every intermediate value appears twice with opposite signs.

Solution

1. Expand: $\sum_{l=0}^{T-t-1} \gamma^l \big(r_{t+l} + \gamma V(s_{t+l+1}) - V(s_{t+l})\big)$. The rewards give $\sum_{l=0}^{T-t-1} \gamma^l r_{t+l} = G_t$, the full discounted return, because the episode ends at $T$. For the values, $V(s_k)$ with $t \lt k \lt T$ appears with coefficient $+\gamma^{k-t}$ (as the next state of step $k-1$) and $-\gamma^{k-t}$ (as the current state of step $k$), so it cancels. What survives is $-V(s_t)$ (only ever a current state) and $+\gamma^{T-t} V(s_T)$ (only ever a next state). Since $V(s_T) = 0$, the sum is $G_t - V(s_t)$. This is exactly GAE at $\lambda = 1$, so GAE(γ, 1) is Monte Carlo with $V$ as a baseline.

2. The same cancellation gives

$$\sum_{l=0}^{T-t-1} \gamma^l \delta_{t+l} = \sum_{l=0}^{T-t-1}\gamma^l r_{t+l} + \gamma^{T-t} V(s_T) - V(s_t).$$

In words: use real rewards up to the cut, then let the critic estimate the rest. So $\lambda = 1$ on a truncated rollout is the $(T-t)$-step return, not pure Monte Carlo. It is unbiased only if $V(s_T)$ is. This is why A2C with short rollouts still depends on the critic even at $\lambda = 1$, but only at the rollout’s edge, discounted by $\gamma^{T-t}$.

I've done this one

Exercise 8.4The n-step return recursionPen & paper●●○

Define $G^{(0)}_t = V(s_t)$ and, for $n \ge 1$, $G^{(n)}_t = \sum_{l=0}^{n-1}\gamma^l r_{t+l} + \gamma^n V(s_{t+n})$.

1. Show that $G^{(n)}_t = r_t + \gamma\, G^{(n-1)}_{t+1}$ for $n \ge 1$.
2. Use part 1 to prove by induction that $\hat{A}^{(n)}_t = G^{(n)}_t - V(s_t) = \sum_{l=0}^{n-1}\gamma^l \delta_{t+l}$.
3. From $\hat{A}_t = \sum_{l \ge 0} (\gamma\lambda)^l \delta_{t+l}$, derive the backward recursion $\hat{A}_t = \delta_t + \gamma\lambda \hat{A}_{t+1}$.

Hint

For part 2, add and subtract $\gamma V(s_{t+1})$ in $r_t + \gamma G^{(n-1)}_{t+1} - V(s_t)$.

Solution

1. $r_t + \gamma G^{(n-1)}_{t+1} = r_t + \gamma\Big(\sum_{l=0}^{n-2}\gamma^l r_{t+1+l} + \gamma^{n-1}V(s_{t+n})\Big) = r_t + \sum_{l=1}^{n-1}\gamma^l r_{t+l} + \gamma^n V(s_{t+n}) = G^{(n)}_t$. For $n = 1$ the inner sum is empty and this reads $r_t + \gamma V(s_{t+1}) = G^{(1)}_t$, consistent with $G^{(0)}_{t+1} = V(s_{t+1})$.

2. Base case $n = 0$: $\hat{A}^{(0)}_t = V(s_t) - V(s_t) = 0$, an empty sum. Inductive step: assume the claim for $n - 1$ at every time. Then

$$\hat{A}^{(n)}_t = r_t + \gamma G^{(n-1)}_{t+1} - V(s_t) = \underbrace{r_t + \gamma V(s_{t+1}) - V(s_t)}_{\delta_t} + \gamma\underbrace{\big(G^{(n-1)}_{t+1} - V(s_{t+1})\big)}_{\hat{A}^{(n-1)}_{t+1}} = \delta_t + \gamma \sum_{l=0}^{n-2}\gamma^l\delta_{t+1+l} = \sum_{l=0}^{n-1}\gamma^l\delta_{t+l}.$$

3. $\hat{A}_t = \delta_t + \sum_{l \ge 1}(\gamma\lambda)^l\delta_{t+l} = \delta_t + \gamma\lambda\sum_{k \ge 0}(\gamma\lambda)^k\delta_{t+1+k} = \delta_t + \gamma\lambda\,\hat{A}_{t+1}$, substituting $k = l - 1$.

The recursion in part 2 is the reason “n-step” and “a sum of TD errors” are the same thing. Each step contributes its own surprise, then passes the rest of the estimate one step down the line, discounted.

I've done this one

Exercise 8.5Where the critic's mistakes goPen & paper●●●

Let the critic be $V = V^\pi + e$, where $e(s)$ is its error (with $e = 0$ at terminal states). Write $\delta^\pi_t$ for the TD error computed with the true $V^\pi$.

1. Show $\delta_t = \delta^\pi_t + \gamma e(s_{t+1}) - e(s_t)$.
2. Show that the GAE estimate decomposes as $\hat{A}_t = \sum_{l}(\gamma\lambda)^l\delta^\pi_{t+l} - e(s_t) + \sum_{m \ge 1}\gamma^m\lambda^{m-1}(1-\lambda)\,e(s_{t+m}).$
3. Show that $\mathbb{E}\big[\sum_l(\gamma\lambda)^l\delta^\pi_{t+l} \mid s_t, a_t\big] = A^\pi(s_t, a_t)$ for every $\lambda$.
4. Explain why the $-e(s_t)$ term does not bias the policy gradient, and which $\lambda$ removes the remaining error terms.

Hint

For part 2, split the sum over $l$ into the $\gamma e(s_{t+l+1})$ terms and the $-e(s_{t+l})$ terms, re-index the first so both are sums over $e(s_{t+m})$, and collect coefficients. For part 3, use the tower rule: condition on $(s_{t+l}, a_{t+l})$ first.

Solution

1. $\delta_t = r_t + \gamma(V^\pi + e)(s_{t+1}) - (V^\pi + e)(s_t) = \big[r_t + \gamma V^\pi(s_{t+1}) - V^\pi(s_t)\big] + \gamma e(s_{t+1}) - e(s_t)$.

2. Summing with weights $(\gamma\lambda)^l$, the error part is $\sum_{l \ge 0}(\gamma\lambda)^l\gamma\, e(s_{t+l+1}) - \sum_{l \ge 0}(\gamma\lambda)^l e(s_{t+l})$. In the first sum put $m = l + 1$: $\sum_{m \ge 1}(\gamma\lambda)^{m-1}\gamma\, e(s_{t+m})$. In the second, $m = l$: $e(s_t) + \sum_{m \ge 1}(\gamma\lambda)^m e(s_{t+m})$. The coefficient of $e(s_{t+m})$ for $m \ge 1$ is $(\gamma\lambda)^{m-1}\gamma - (\gamma\lambda)^m = \gamma^m\lambda^{m-1}(1 - \lambda)$. That gives the stated formula. (In an episode all sums stop at the terminal state, where $e = 0$.)

3. For $l = 0$: $\mathbb{E}[\delta^\pi_t \mid s_t, a_t] = A^\pi(s_t,a_t)$, shown in the chapter. For $l \ge 1$: by the tower rule, $\mathbb{E}[\delta^\pi_{t+l} \mid s_t, a_t] = \mathbb{E}\big[\mathbb{E}[\delta^\pi_{t+l} \mid s_{t+l}, a_{t+l}] \mid s_t, a_t\big] = \mathbb{E}\big[A^\pi(s_{t+l}, a_{t+l}) \mid s_t, a_t\big]$. Since $a_{t+l} \sim \pi(\cdot \mid s_{t+l})$ and advantages average to zero under $\pi$, this is $\mathbb{E}\big[\sum_a \pi(a \mid s_{t+l}) A^\pi(s_{t+l}, a)\big] = 0$. So only the $l = 0$ term survives, for any $\lambda$.

4. $-e(s_t)$ depends only on $s_t$, so in the policy gradient it contributes $\mathbb{E}[\nabla\log\pi(a_t \mid s_t)\,e(s_t)] = \mathbb{E}_{s_t}\big[e(s_t)\,\nabla\sum_a \pi(a \mid s_t)\big] = 0$. It is a (bad) baseline: it can add variance but not bias. The remaining terms involve future states, which depend on $a_t$, so they do bias the gradient in general. Their weights $\gamma^m\lambda^{m-1}(1-\lambda)$ are all zero at $\lambda = 1$, so Monte Carlo is unbiased with any critic. At $\lambda = 0$ only $m = 1$ survives, with weight $\gamma$: one-step TD carries the full error of the next state’s value. This is why the demo’s target is $Q^\pi(s_t,a_t) - V(s_t)$, which equals $A^\pi - e(s_t)$: it already contains the harmless baseline term.

I've done this one

Exercise 8.6Why normalize advantages?Concept●●○

Early in CartPole training, a batch of five transitions gets GAE advantages $(12,\ 9,\ 15,\ 10,\ 14)$. The critic still outputs values near 0, and every reward is $+1$.

1. Without normalization, which of the five sampled actions does the policy step make more likely?
2. Normalize the batch (population std). Which actions are now pushed up, and which down?
3. Give two distinct reasons normalization helps, and one thing it costs.

Hint

Mean 12. Deviations $0, -3, 3, -2, 2$.

Solution

1. All five. Every advantage is positive, so every sampled action’s probability goes up. Only the sizes differ. Information about which actions were better lives only in the differences, which is the high-variance situation of the chapter’s worked example.
2. Mean 12, squared deviations $0, 9, 9, 4, 4$, variance $26/5 = 5.2$, std $\approx 2.28$. Normalized: $(0,\ -1.32,\ 1.32,\ -0.88,\ 0.88)$. The actions with advantages 15 and 14 are pushed up. Those with 9 and 10 are pushed down. The one with 12 is left alone.
3. Centering is an extra baseline (the batch mean), which fixes the “everything positive” problem while the critic is still learning. Scaling makes the step size independent of the reward scale and of the training phase, so one learning rate works throughout. Cost: the estimator is no longer exactly the policy gradient. The batch mean and std depend on the samples themselves, and the effective learning rate changes from batch to batch (a batch of nearly identical advantages gets blown up to unit size, which amplifies noise; the $\epsilon$ in the denominator only prevents division by zero). GRPO normalizes per group of responses to the same prompt (Chapter 15), and Dr. GRPO argues that the std division introduces a bias worth removing (Chapter 16).

I've done this one

Exercise 8.7Explore the demo: tuning λ to the criticExplore the demo●●○

Use the GAE demo. Before each step, write down your prediction.

1. Press Perfect critic. Where is the best $\lambda$? The variance at $\lambda = 0$ is exactly zero. Why, in this particular world?
2. Move the critic error to 0.05, 0.15, 0.25 and 0.4, and note the best $\lambda$ each time. Describe the trend in one sentence.
3. At critic error 0.15 and $\lambda = 1$, change $\gamma$ from 1 to 0.9. The variance drops a lot. Give two reasons, one of which is a warning.
4. At critic error 0.15, press Play with $\lambda = 0$, then with $\lambda = 1$. Describe what happens to the bar at step 0 across episodes, compared to its target tick.

Hint

In this world the transitions are deterministic and the only reward depends on the final position. What is random about $\delta_t$ once you know $s_t$ and $a_t$?

Solution

1. Best $\lambda = 0$, with MSE 0. With a perfect critic, every $\lambda$ is unbiased (Exercise 8.5), so you should pick the one with least variance. Here $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ is fully determined by $(s_t, a_t)$: the move is deterministic and the reward depends only on the state reached. So the one-step estimate has no randomness at all. Larger $\lambda$ adds the randomness of future coin flips. At $\lambda = 1$ the variance reaches about 0.139 (with γ = 1).
2. For the demo’s default critic mistakes, the best $\lambda$ is about 0.08, 0.38, 0.56 and 0.72 respectively (a different set of mistakes moves these a little). The worse the critic, the more you should rely on real rewards, so the best $\lambda$ moves toward 1.
3. First, discounting shrinks the weight of distant TD errors (the window $1/(1-\gamma\lambda)$ shrinks from infinite to 10 steps), so fewer random terms enter. Second, and this is the warning: the reward sits up to 11 steps away and is multiplied by up to $0.9^{11} \approx 0.31$, so all the values, advantages and their spread shrink in absolute size. Part of the “variance reduction” is just a change of units, and part is a change of problem: you are now estimating advantages for a more short-sighted objective. $\gamma$ is not a free variance-reduction knob the way $\lambda$ is with a good critic.
4. At $\lambda = 0$ the step-0 bar hardly moves from episode to episode (the start state is always the same, and only the first action varies), but it sits visibly away from the tick. That is bias, coming from the critic’s mistake at $s_1$. At $\lambda = 1$ the bar jumps around a lot, sometimes far above and sometimes far below, but the whisker’s mean dot sits on the tick. That is unbiased but high variance. The best $\lambda$ in between gives bars that move moderately and sit close to the tick.

I've done this one

Exercise 8.8Code: GAE and A2C on CartPoleCode●●○

In the lab 08-actor-critic, implement in actor_critic.py:

• Task 1, td_errors, and Task 2, compute_gae, including episode boundaries inside a rollout and the (T, N) shape for parallel environments. The first GAE test is this chapter’s running example.
• Task 3, normalize_advantages, and Task 4, actor_critic_loss (policy loss, value loss, entropy bonus, with detached targets).

Then run python run.py. It trains A2C for $\lambda \in \{0,\ 0.5,\ 0.95,\ 1\}$ on 3 seeds and saves a2c_lambda.png. In the demo, a good critic favored small $\lambda$. On CartPole, $\lambda = 0$ learns far more slowly than $\lambda = 0.95$ or 1. Explain why. Also look at the very start of the $\lambda = 0$ curve: it drops to about 10, below a random policy (about 22). Run train_a2c(total_steps=30_000, lam=0.0, verbose=True) and watch the printed entropy. What has happened to the policy?

Hint

What does a freshly initialized critic output, and what are the true values in CartPole with $\gamma = 0.99$ and +1 reward per step?

Solution

Key lines (full code in solutions/actor_critic.py):

# Task 1: next_values is values shifted up one row, with last_value as the final row
next_values = np.concatenate([values[1:], last_value[None]], axis=0)
deltas = rewards + gamma * next_values * (1.0 - dones) - values

# Task 2: one backward pass; (1 - dones[t]) stops the carry at episode ends
for t in range(T - 1, -1, -1):
    next_adv = deltas[t] + gamma * lam * (1.0 - dones[t]) * next_adv
    advantages[t] = next_adv
returns = advantages + values

# Task 3
(adv - adv.mean()) / (adv.std(unbiased=False) + eps)

# Task 4
log_probs = torch.log_softmax(logits, -1)
logp = log_probs.gather(1, actions.unsqueeze(1)).squeeze(1)
policy_loss = -(logp * advantages.detach()).mean()
value_loss = ((values - returns.detach()) ** 2).mean()
entropy = -(log_probs.exp() * log_probs).sum(-1).mean()

Because every operation in Tasks 1 and 2 indexes only the first (time) axis, the same code handles (T,) and (T, N) arrays.

Why λ = 0 is slow here. A fresh critic outputs about 0, while true values in CartPole are large: an episode that lasts $k$ more steps is worth $\sum_{j \lt k} 0.99^j$, up to about 100. One-step advantages $\delta_t = 1 + 0.99\,V(s_{t+1}) - V(s_t)$ depend entirely on the critic, so early on they are nearly constant (about $+1$ everywhere) and carry almost no information about which actions keep the pole up. That is maximal bias. The policy improves only after the critic has learned decent values, which itself takes a while, since TD(0) targets propagate information one step per update. With $\lambda$ near 1, the advantages use real rewards: a step followed by an early fall has a much smaller return than one followed by a long balance. CartPole’s dynamics and rewards are deterministic, so the variance cost of $\lambda = 1$ is modest. The demo’s lesson still applies: the best $\lambda$ depends on the critic’s quality, and early in training the critic is bad.

Why λ = 0 first gets worse than random. With the reference solution the printed entropy falls from about 0.69 ($\ln 2$, a coin flip) to about 0.1 within 15k steps, and the average return settles near 9.6, which is what you get by pushing the cart the same way every time. The policy has collapsed onto one action. The one-step advantages are nearly constant, so after normalization the actor is fitting unit-sized versions of tiny differences that come from the fresh critic, not from the task (the cost of normalization from Exercise 8.6). Whatever direction the barely trained critic happens to prefer, the actor follows, and nothing in a one-step advantage contradicts it. Only after the critic learns that falling is bad (the value loss rises and then drops back) does the entropy come back up and the return start to climb. This is critic bias at its worst: it does not just slow learning, it points the actor the wrong way.

I've done this one

Exercise 8.9Truncation is not terminationConcept●●○

CartPole episodes end either when the pole falls (or the cart leaves the track), or after 500 steps.

1. Suppose your code treats the 500-step cut-off like a fall: done = 1, no bootstrap. What regression target does the critic see for a well-balanced state at step 499? And for the same physical state at step 100?
2. Why is that a problem for a critic whose input is $(x, \dot{x}, \theta, \dot\theta)$?
3. The lab’s collect_rollout replaces the reward at a truncated step with $r_t + \gamma V(s_{t+1})$ and then marks the step done. Show that this gives the same TD error as bootstrapping normally, while still stopping GAE from leaking into the next episode.
4. When would treating the time limit as terminal be correct?

Hint

Write the TD error at the truncated step both ways.

Solution

1. At step 499 the target is about $r = 1$ (nothing follows). At step 100 the same state’s target reflects many more steps of reward, up to $\sum_j 0.99^j \approx 100$ for a good policy.
2. The critic cannot see the time, so it is asked to output both about 1 and about 100 for the same input. It ends up somewhere in between, wrong for both. Those errors feed into every advantage estimate. Worse, the actor is told that balancing well near step 500 is bad, because the forecast drops sharply there.
3. With the bootstrap folded into the reward and $d_t = 1$: $\delta_t = (r_t + \gamma V(s_{t+1})) + \gamma \cdot 0 - V(s_t) = r_t + \gamma V(s_{t+1}) - V(s_t)$, the normal TD error. Setting $d_t = 1$ also zeroes the $\gamma\lambda(1-d_t)\hat{A}_{t+1}$ carry, so the next row of the rollout, which belongs to a fresh episode, cannot leak into this one. (Note that $s_{t+1}$ here must be the state before the automatic reset, which is why VecCartPole.step also returns final_obs.)
4. When the time limit is a real part of the task (a game that ends at a fixed time, say) and the remaining time is part of the state, so the critic can tell step 100 from step 499. Pardo et al. (2018) discuss both cases.

I've done this one

Exercise 8.10From GAE to critic-free LLM trainingConcept●●○

Consider the token-level view of an LLM response from Chapter 11: state $s_t = (x, y_{\lt t})$, action $y_t$, $\gamma = 1$, no KL penalty, and a single reward $r(x, y)$ given after the last token.

1. Write GAE with $\lambda = 1$ for token $t$ in terms of $r(x,y)$ and the critic.
2. Now replace the per-token critic $V(x, y_{\lt t})$ with one number per prompt: the mean reward $b(x)$ of $G$ responses sampled for the same prompt. What advantage does every token of response $y^{(i)}$ get?
3. Give two reasons why training a per-token critic is harder for an LLM than for CartPole.

Hint

For part 1, Exercise 8.3 already did the work: with $\gamma = 1$ and only one nonzero reward, what is $G_t$ for every token? For part 3, think about what the critic is (its size) and what it must predict (from how little signal).

Solution

1. With $\gamma = \lambda = 1$, GAE telescopes to Monte Carlo: $\hat{A}_t = \sum_l \delta_{t+l} = r(x,y) - V(x, y_{\lt t})$. Each token is credited with the final reward minus the critic’s forecast just before that token.
2. $\hat{A}^{(i)}_t = r^{(i)} - b(x)$ for every token $t$ of response $i$. It is the same number for all tokens in a response. This is the advantage used by RLOO and GRPO (Chapter 15, Chapter 16), up to GRPO’s extra division by the group’s std and RLOO’s leave-one-out mean. You lose per-token credit assignment, but you lose the critic’s bias too, and you save a whole model.
3. (a) Cost: the critic is usually itself a large transformer (often the size of the policy or the reward model), with its own activations, gradients and optimizer state. That roughly doubles training memory and compute. (b) Difficulty: it must predict, from a half-written answer, the eventual reward. That is a hard prediction problem with a sparse, end-of-sequence signal and millions of distinct prefixes, and an inaccurate critic biases every token’s advantage (Exercise 8.5). CartPole has a 4-dimensional state and a dense reward every step.

I've done this one

Further reading

• Schulman, Moritz, Levine, Jordan & Abbeel (2015), High-Dimensional Continuous Control Using Generalized Advantage Estimation. The GAE paper. Sections 2–3 (the $\Psi_t$ menu, “γ-just” estimators, which is the paper’s term for estimators that are unbiased for the γ-discounted advantage, and the derivation) are short and match this chapter closely.
• Sutton & Barto (2018), Reinforcement Learning: An Introduction, sections 13.4–13.5 (REINFORCE with baseline, actor-critic), chapter 7 (n-step bootstrapping) and chapter 12 (λ-returns). The tabular foundations behind everything here.
• Mnih et al. (2016), Asynchronous Methods for Deep Reinforcement Learning. A3C: parallel actor-learners, n-step advantages and an entropy bonus. Read section 4 and Algorithm S3 for the actor-critic version.
• Huang et al. (2022), The 37 Implementation Details of Proximal Policy Optimization. A blog post (ICLR Blog Track) on how real implementations handle GAE, advantage normalization, vectorized environments and truncation. Very useful once you start writing PPO in Chapter 9.
• Andrychowicz et al. (2020), What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study. Over 250,000 training runs ablating choices like GAE λ, normalization and network sharing. Read it for evidence instead of folklore.
• Pardo, Tavakoli, Levdik & Kormushev (2018), Time Limits in Reinforcement Learning. Why a time-out is not a terminal state, and what to do about it.
• Barto, Sutton & Anderson (1983), Neuronlike adaptive elements that can solve difficult learning control problems. The original actor-critic, balancing a pole. It is striking how much of this chapter is already there.

Next: Chapter 9 keeps GAE, the critic and the entropy bonus, and asks how to take bigger, safer policy steps by reusing each batch of data several times.