Lecture 06 · Part 2

Actor-Critic Algorithms

Policy gradients get their variance from single-sample reward-to-go estimates. Levine replaces them with learned value functions: fit the value function, bootstrap an advantage, and you have the actor-critic family. Along the way comes the discount factor as fear of death, online and parallel variants, off-policy actor-critic with a replay buffer and a Q-function, and a bias-variance dial running from one-step advantages through n-step returns to generalized advantage estimation.

▶ Lecture videos (5 parts) Slides (current revision, PDF) ↗

The variance hiding in reward-to-go

Actor-critic algorithms “build on the policy gradient framework… augmented with learned value functions and Q-functions.” Levine’s choice of the symbol $\hat{Q}_{i,t}$ for REINFORCE’s reward-to-go last lecture “was deliberate”: it estimates the expected reward from taking $a_{i,t}$ in $s_{i,t}$ and then following the policy. But it’s computed by summing rewards along the one trajectory you happened to get. The policy and the MDP are both random; landing in the same state again, the rollout might end completely differently. The reward-to-go is “a single sample estimate of a very complex expectation” — and fewer samples means higher variance. That single-sample estimate is the high variance of the policy gradient. With the true expected reward-to-go — the Q-function — plugged in place of $\hat{Q}_{i,t}$ , the variance drops dramatically.

Baselines improve too. The baseline may depend on the state (not the action — that adds bias, for now), and the natural state-dependent choice is the average Q-value over the actions the policy would take there — which is, by definition, the value function.

Definition — Q-function, value function, advantage

$Q^\pi(s_t, a_t) = \sum_{t'=t}^{T} \mathbb{E}_{\pi_\theta}[r(s_{t'}, a_{t'}) \mid s_t, a_t]$ is the total expected reward from taking $a_t$ in $s_t$ and then following $\pi$ . $V^\pi(s_t) = \mathbb{E}_{a_t \sim \pi_\theta(a_t \mid s_t)}[Q^\pi(s_t, a_t)]$ is the total expected reward from $s_t$ onward. Their difference $A^\pi(s_t, a_t) = Q^\pi(s_t, a_t) - V^\pi(s_t)$ is the advantage: how much better $a_t$ is than the average action $\pi$ would take in $s_t$ .

The gradient becomes $\frac{1}{N}\sum_{i,t} \nabla_\theta \log \pi_\theta(a_{i,t} \mid s_{i,t})\, A^\pi(s_{i,t}, a_{i,t})$ — raise the probability of better-than-average actions, lower the rest. The better the advantage estimate, the lower the variance. The catch: an approximate critic makes the gradient biased. Usually “the enormous reduction in variance is often worth the slight increase in bias.” The green box of the RL anatomy — estimate returns — now means fitting a function approximator.

What to fit: the case for the value function

Three candidates: $Q^\pi$ , $V^\pi$ , or $A^\pi$ . An identity picks the winner. Since $s_t$ and $a_t$ are known, not random, the current reward pulls out exactly:

$Q^\pi(s_t, a_t) = r(s_t, a_t) + \mathbb{E}_{s_{t+1} \sim p(s_{t+1} \mid s_t, a_t)}\left[V^\pi(s_{t+1})\right]$

Approximate the expectation with the actual next state seen — $Q^\pi(s_t, a_t) \approx r(s_t, a_t) + V^\pi(s_{t+1})$ — a single-sample estimate again, but for just one step; everything after stays integrated out inside $V^\pi$ . Then

$A^\pi(s_t, a_t) \approx r(s_t, a_t) + V^\pi(s_{t+1}) - V^\pi(s_t)$

depends only on $V$ , which takes just a state as input while $Q$ and $A$ need the action too — fewer inputs, fewer samples needed. So: “let’s just fit $V^\pi(s)$ ” with a network $\hat{V}^\pi_\phi(s)$ .

Fitting $V^\pi$ is policy evaluation: $J(\theta) = \mathbb{E}_{s_1 \sim p(s_1)}[V^\pi(s_1)]$ , so the value function at the initial states literally evaluates the policy. Monte Carlo evaluation builds tuples $(s_{i,t}, y_{i,t})$ with $y_{i,t} = \sum_{t'=t}^{T} r(s_{i,t'}, a_{i,t'})$ and regresses: $\mathcal{L}(\phi) = \frac{1}{2}\sum_{i,t} \| \hat{V}^\pi_\phi(s_{i,t}) - y_{i,t} \|^2$ . Ideally you’d average many rollouts from each state, but model-free RL can’t reset the simulator to an arbitrary state — one rollout per visit.

Better targets: the ideal is $r(s_{i,t}, a_{i,t}) + V^\pi(s_{i,t+1})$ ; we don’t know $V^\pi$ , but the previous value network is “probably better than nothing,” so plug it in: $y_{i,t} = r(s_{i,t}, a_{i,t}) + \hat{V}^\pi_\phi(s_{i,t+1})$ . This bootstrap estimate has lower variance ( $\hat{V}$ averages over all futures) but higher bias ( $\hat{V}$ is always wrong somewhere) — the trade running through the whole lecture.

Discount factors: the fear of death

One problem appears immediately in infinite-horizon settings: with, say, all-positive rewards, every bootstrap update grows the value function, which “might become infinite.” The fix is to prefer rewards sooner — you’d take a hundred dollars today over a hundred in a million years, partly because “someday you’re going to die and you’d like to receive the reward before you die.” Multiply the bootstrapped value by a discount factor $\gamma \in [0, 1]$ (“0.99 works really well”):

$y_{i,t} = r(s_{i,t}, a_{i,t}) + \gamma\, \hat{V}^\pi_\phi(s_{i,t+1})$

The interpretation is exact: $\gamma$ changes the MDP, adding a death state entered with probability $1 - \gamma$ at every step, zero reward, no way out — “there’s no resurrection in this MDP.” Surviving transitions become $\gamma\, p(s' \mid s, a)$ .

Worked example — Two ways to discount the Monte Carlo policy gradient

Option 1 puts $\gamma$ inside the reward-to-go: $\sum_{t'=t}^{T} \gamma^{t'-t} r(s_{i,t'}, a_{i,t'})$ — the single-sample version of the discounted critic. Option 2 discounts from the trajectory’s start, weighting the reward at step $t$ by $\gamma^{t-1}$ . They differ: apply causality to option 2 and you get option 1’s reward-to-go times an extra $\gamma^{t-1}$ multiplying grad-log-pi. That factor says later decisions matter less, not just later rewards — correct for a truly discounted problem (you won’t study for an exam scheduled a million years out), but not what we want. For a cyclic running task we want a policy good at every time step; the discount is a mathematically convenient stand-in for the (algorithmically very difficult) average reward. So practice uses option 1 and quietly drops the $\gamma^{t-1}$ .

An alternative reading (Philip Thomas, “Bias in natural actor-critic algorithms”): the discount is variance reduction. Infinite reward sums have infinite variance; $\gamma$ truncates the far future — exactly the high-variance part — at the cost of bias.

Code walkthrough — Batch and online actor-critic with a discount

The batch algorithm replaces REINFORCE’s green box with critic fitting:

# batch actor-critic (one iteration)
trajs = run_policy(pi_theta)                    # 1. orange box: sample {s_i, a_i, s'_i}
y = r + gamma * V_phi(s_next)                   # 2. bootstrap targets
phi = regress(V_phi, states, y)                 # 3. refit V to targets
A_hat = r + gamma * V_phi(s_next) - V_phi(s)    # 4. advantages
g = sum(grad_log_pi(a, s) * A_hat)              # 5. policy gradient
theta = theta + alpha * g                       # 6. gradient ascent

Because the bootstrap needs only one next state — not the rest of the episode — the same loop runs fully online: take a single step, update $\phi$ on that transition, compute its advantage, update $\theta$ , repeat. Every time step is a learning step.

Making it practical: architectures and parallel workers

Two design decisions turn the online recipe into a deep RL algorithm. Architecture: the recommended start is two separate networks, state-to-value and state-to-action-distribution — simple and “fairly stable to train.” A shared trunk with two heads shares representations (attractive from images, where the critic’s features could help the policy), but the shared layers get hit by gradients of different scales and statistics, so it needs more tuning.

Batch size: updating a deep net with single-sample SGD “is not going to work very well.” The classic fix is parallel workers. Synchronous parallel actor-critic steps multiple differently-seeded simulators in lockstep and updates on all threads’ transitions together — batch size equals thread count. The asynchronous version (as in A3C) drops the synchronization point: threads run at their own pace, pulling the latest parameters as they go. Batches then mix transitions from slightly older actors — not mathematically equivalent to the synchronous update, but in practice the speed gains outweigh the small bias, as long as no thread lags far behind.

Off-policy actor-critic: the replay buffer and the Q-trick

If slightly-old transitions are tolerable, why not much older ones from the same actor? Keep a replay buffer — a ring buffer of, say, a million transitions — and update on batches sampled from it. Now the staleness can’t be ignored, and the naive algorithm “is actually quite broken” in two places. First, the target $y_i = r(s_i, a_i) + \gamma \hat{V}^\pi_\phi(s'_i)$ uses an action taken by an old policy, so it estimates the wrong actor’s value. Second, the policy gradient requires actions sampled from the current $\pi_\theta$ — buffer actions don’t qualify.

Fix the critic by learning $Q$ instead of $V$ : the Q-function is a valid question for any action — only subsequent steps must follow $\pi$ — so it can be trained on off-policy actions and queried with on-policy ones. For the target, use $V^\pi(s') = \mathbb{E}_{a' \sim \pi_\theta}[Q^\pi(s', a')]$ :

$y_i = r(s_i, a_i) + \gamma\, \hat{Q}^\pi_\phi\big(s'_i, a'_i\big), \qquad a'_i \sim \pi_\theta(a' \mid s'_i)$

The trick is that $a'_i$ is not from the buffer: we ask the current policy what it would have done at the old state $s'_i$ — no simulator needed, because “we have functional access to our policy.” Fix the actor with the same trick at $s_i$ : sample $a^\pi_i \sim \pi_\theta(a \mid s_i)$ and use $\nabla_\theta \log \pi_\theta(a^\pi_i \mid s_i)\, \hat{Q}^\pi_\phi(s_i, a^\pi_i)$ . In practice the baseline is dropped — plug in $\hat{Q}$ directly. Higher variance, but acceptable: extra action samples cost network evaluations, not environment interaction, so averaging more of them is nearly free.

One flaw remains: $s_i$ follows an old policy’s state distribution, and “there’s basically nothing we can do here” — accept the bias. The intuition: we wanted the optimal policy on $p_\theta(s)$ but get it on a broader distribution — extra work on states we may never visit, but nothing important is missed. This template, plus fancier Q-fitting and the reparameterization trick (both later in the course), underlies soft actor-critic, one of the most widely used actor-critic methods today.

Keeping it unbiased: control variates, n-step returns, and GAE

Can the critic reduce variance without introducing bias? Yes — use it as a baseline rather than as the return estimate.

State-dependent baselines are unbiased

The policy gradient stays unbiased when you subtract any function of the state: $\nabla_\theta J(\theta) \approx \frac{1}{N}\sum_{i,t} \nabla_\theta \log \pi_\theta(a_{i,t} \mid s_{i,t}) \left( \sum_{t'=t}^{T} \gamma^{t'-t} r(s_{i,t'}, a_{i,t'}) - \hat{V}^\pi_\phi(s_{i,t}) \right)$ The proof extends last lecture’s constant-baseline proof almost verbatim: conditioned on $s_t$ , the baseline factors out of the expectation over actions, which integrates to $\nabla_\theta 1 = 0$ . With $\hat{V}$ as the baseline the numbers multiplying grad-log-pi are near zero in expectation — lower variance, no bias. The single-sample reward sum keeps variance above actor-critic, but well below a constant baseline.

Push further and let the baseline depend on the action — a control variate. Subtracting $\hat{Q}^\pi_\phi(s_{i,t}, a_{i,t})$ drives the first term toward zero as the critic improves, but an action-dependent baseline no longer integrates to zero: an error term $\nabla_\theta \mathbb{E}_{a \sim \pi_\theta}[\hat{Q}^\pi_\phi(s_{i,t}, a)]$ must be added back. It looks like the original problem, but it’s evaluable without new environment samples — sum over discrete actions, sample many actions per state for free, or solve analytically (a quadratic $Q$ under a Gaussian policy has a closed form). The result is a very low-variance unbiased gradient — see Q-Prop (Gu et al.).

Between the unbiased Monte Carlo estimator and the biased one-step critic lies a dial. Near-future predictions are low-variance — asked which city he’ll be in in five minutes, Levine answers “Berkeley” confidently; in twenty years, a single sample is nearly meaningless. Trajectories branch out over time, so use the single-sample rewards where they’re reliable and “cut it off before the variance gets too big,” replacing the tail with the value function — the n-step return:

$\hat{A}^\pi_n(s_t, a_t) = \sum_{t'=t}^{t+n} \gamma^{t'-t} r(s_{t'}, a_{t'}) - \hat{V}^\pi_\phi(s_t) + \gamma^n \hat{V}^\pi_\phi(s_{t+n})$

Larger $n$ : less bias (the value term is scaled by $\gamma^n$ ), more variance. Choosing $n$ greater than 1 often beats $n = 1$ , and the sweet spot is usually in between. You don’t have to choose one $n$ : generalized advantage estimation (GAE, Schulman et al.) averages all n-step estimators, $\hat{A}^\pi_{GAE} = \sum_{n=1}^{\infty} w_n \hat{A}^\pi_n$ , with exponential weights $w_n \propto \lambda^{n-1}$ preferring earlier cuts. The infinite sum collapses to

$\hat{A}^\pi_{GAE}(s_t, a_t) = \sum_{t'=t}^{\infty} (\gamma\lambda)^{t'-t}\, \delta_{t'}, \qquad \delta_{t'} = r(s_{t'}, a_{t'}) + \gamma \hat{V}^\pi_\phi(s_{t'+1}) - \hat{V}^\pi_\phi(s_{t'})$

a $(\gamma\lambda)$ -discounted sum of one-step advantage estimates. The $\lambda$ acts like a discount — which retroactively illuminates $\gamma$ itself: even without $\lambda$ , the discount was already trading bias for variance by down-weighting exactly the rewards with the highest variance.

Back of the chalk tray — what to remember

The reward-to-go in policy gradients is a single-sample estimate of $Q^\pi$ ; replacing it with a learned critic slashes variance at the price of some bias — usually a good trade.
The advantage $A^\pi = Q^\pi - V^\pi$ is what should weight grad-log-pi, and $A^\pi(s_t,a_t) \approx r + \gamma V^\pi(s_{t+1}) - V^\pi(s_t)$ means fitting only $V^\pi(s)$ — a function of state alone.
Policy evaluation fits $\hat{V}^\pi_\phi$ by regression: Monte Carlo targets are unbiased but noisy; bootstrap targets $r + \gamma \hat{V}(s')$ have lower variance but inherit the network’s bias.
The discount $\gamma$ keeps infinite-horizon values finite; it’s equivalent to a death state entered with probability $1-\gamma$ , and doubles as a variance-reduction knob.
Online actor-critic needs batches: parallel workers (synchronous or asynchronous) on-policy, or a replay buffer off-policy — the latter requires learning $Q$ instead of $V$ and re-sampling actions from the current policy at buffer states.
The critic can also serve as an unbiased state-dependent baseline, an action-dependent control variate with a correction term, or the anchor of n-step and GAE estimators that dial bias against variance with $n$ or $\lambda$ .

Check yourself

Derivation and debugging exercises in the lecture’s spirit — work them on paper.

Problem 6.1 state-dependent baseline proof

Levine asserts that subtracting any baseline $b(s_{i,t})$ depending only on the state leaves the policy gradient unbiased, and encourages rederiving it. Do so: show $\mathbb{E}\left[\nabla_\theta \log \pi_\theta(a_t \mid s_t)\, b(s_t)\right] = 0$ , and point to the exact step that fails if $b$ also depends on $a_t$ .

Show solution

Condition on the state: $\mathbb{E}_{s_t}\!\left[ \mathbb{E}_{a_t \sim \pi_\theta(a_t \mid s_t)}\left[ \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, b(s_t) \right] \right]$ . Because $b(s_t)$ is constant with respect to the inner expectation over actions, it factors out, leaving $\mathbb{E}_{s_t}\!\left[ b(s_t) \int \pi_\theta(a_t \mid s_t)\, \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, da_t \right]$ . The inner integral is $\int \nabla_\theta \pi_\theta(a_t \mid s_t)\, da_t = \nabla_\theta \int \pi_\theta(a_t \mid s_t)\, da_t = \nabla_\theta 1 = 0$ , so the whole expression vanishes. If $b$ depends on $a_t$ , the factoring-out step fails: $b(s_t, a_t)$ stays inside the integral, which becomes $\nabla_\theta\, \mathbb{E}_{a_t \sim \pi_\theta}[b(s_t, a_t)]$ — generally nonzero. That residual is exactly the correction term control-variate methods like Q-Prop must evaluate and add back.

Problem 6.2 two discounting options

For a three-step trajectory, write the discounted policy gradient weights under option 1 (discount inside the reward-to-go) and option 2 (discount by $\gamma^{t-1}$ from the trajectory start, then apply causality). Identify the differing factor, state what it means, and explain why practice uses option 1 for a continuous running task.

Show solution

Option 1 weights $\nabla_\theta \log \pi_\theta(a_t \mid s_t)$ by $\sum_{t'=t}^{3} \gamma^{t'-t} r_{t'}$ : at $t=1$ the weight is $r_1 + \gamma r_2 + \gamma^2 r_3$ ; at $t=2$ , $r_2 + \gamma r_3$ ; at $t=3$ , $r_3$ . Option 2 starts from weights $\sum_{t'=t}^{3} \gamma^{t'-1} r_{t'}$ after causality, and factoring gives $\gamma^{t-1} \sum_{t'=t}^{3} \gamma^{t'-t} r_{t'}$ — option 1’s weight times an extra $\gamma^{t-1}$ on each grad-log-pi: the $t=2$ term is scaled by $\gamma$ , the $t=3$ term by $\gamma^2$ . The factor says later decisions matter less — the correct gradient of the truly discounted objective, where late decisions influence only heavily discounted rewards. But for a cyclic running task we want a policy that acts well at every time step indefinitely; the discount is only a convenient stand-in for the computationally difficult average-reward objective. The $\gamma^{t-1}$ multiplier would starve late-time-step learning, so practice keeps option 1 and drops it.

Problem 6.3 replay-buffer bug hunt

A colleague adds a replay buffer to online actor-critic: sample transitions $(s_i, a_i, s'_i, r_i)$ from the buffer, compute targets $y_i = r_i + \gamma \hat{V}^\pi_\phi(s'_i)$ , regress $\hat{V}^\pi_\phi$ onto them, then update the policy with $\nabla_\theta \log \pi_\theta(a_i \mid s_i)\, \hat{A}^\pi(s_i, a_i)$ . The algorithm is broken in exactly two places. Find both and give the fixes.

Show solution

Bug 1 is the value target: $a_i$ was taken by an older policy, so regressing onto $r_i + \gamma \hat{V}(s'_i)$ estimates the value of that old actor, not the current one. Fix: learn a Q-function — valid for any action, with only subsequent steps following $\pi$ — and build targets $y_i = r_i + \gamma \hat{Q}^\pi_\phi(s'_i, a'_i)$ with $a'_i \sim \pi_\theta(a' \mid s'_i)$ freshly sampled by querying the current policy network at the old state (no simulation required). Bug 2 is the policy gradient: it must be an expectation under the current $\pi_\theta$ , but $a_i$ came from an old policy — the wrong sampling distribution. Fix: sample $a^\pi_i \sim \pi_\theta(a \mid s_i)$ at the buffer state and use $\nabla_\theta \log \pi_\theta(a^\pi_i \mid s_i)\, \hat{Q}^\pi_\phi(s_i, a^\pi_i)$ , in practice without a baseline since extra action samples are cheap. One bias remains unfixable: $s_i$ follows an old state distribution — accepted, because training on a broader distribution does extra work rather than missing states the current policy visits.

Problem 6.4 GAE limiting cases

Starting from $\hat{A}^\pi_{GAE}(s_t, a_t) = \sum_{t'=t}^{\infty} (\gamma\lambda)^{t'-t} \delta_{t'}$ with $\delta_{t'} = r(s_{t'}, a_{t'}) + \gamma \hat{V}^\pi_\phi(s_{t'+1}) - \hat{V}^\pi_\phi(s_{t'})$ , show that $\lambda = 0$ recovers the one-step actor-critic advantage and $\lambda = 1$ recovers the discounted Monte Carlo estimator with a value-function baseline. What does this say about the role of $\lambda$ ?

Show solution

For $\lambda = 0$ , every term with $t' > t$ carries a factor $0^{t'-t} = 0$ , so only $t' = t$ survives: $\hat{A}^\pi_{GAE} = \delta_t = r(s_t, a_t) + \gamma \hat{V}^\pi_\phi(s_{t+1}) - \hat{V}^\pi_\phi(s_t)$ — the bootstrapped one-step advantage (lowest variance, highest bias). For $\lambda = 1$ the sum is $\sum_{t' \ge t} \gamma^{t'-t} \delta_{t'}$ , and the value terms telescope: the $+\gamma^{t'-t+1} \hat{V}(s_{t'+1})$ contributed at step $t'$ cancels the $-\gamma^{(t'+1)-t} \hat{V}(s_{t'+1})$ contributed at step $t'+1$ . All that survives is $\sum_{t'=t}^{\infty} \gamma^{t'-t} r(s_{t'}, a_{t'}) - \hat{V}^\pi_\phi(s_t)$ (the trailing value term vanishes in the limit under discounting): the discounted single-sample reward-to-go minus a state-dependent baseline — unbiased, highest variance. So $\lambda$ interpolates continuously between the biased low-variance critic estimate and the unbiased high-variance Monte Carlo estimate, softly cutting each trajectory with weight $(\gamma\lambda)^{t'-t}$ — a second discount whose job is purely bias-variance control.