Part VI · Decisions | the policy gradient theorem, REINFORCE and baselines, actor–critic and generalised advantage estimation, the performance difference lemma, TRPO and PPO, maximum-entropy RL and Soft Actor-Critic, Monte Carlo tree search, AlphaZero, MuZero and Dreamer, offline RL, importance sampling and conservative Q-learning | reading: Sutton & Barto (2018), ch. 13; Schulman et al. (2015, 2016, 2017); Haarnoja et al. (2018); Silver et al. (2018); Schrittwieser et al. (2020); Levine et al. (2020) | RL for language models follows in Lecture 22b
Lecture 21b learned action values and acted greedily on them. This page learns the policy itself: a network that outputs a probability for each action, or the parameters of a distribution over continuous actions, adjusted directly to increase the expected return. It then adds the ideas that make modern deep RL work: small, safe policy steps; entropy for exploration; search with a model; and learning from a fixed data set without interacting at all.
By the end you should be able to prove the policy gradient theorem and explain why baselines reduce variance without adding bias; derive GAE; prove the performance difference lemma and explain PPO's clipped objective; derive the softmax form of the maximum-entropy policy; explain how MCTS, AlphaZero and MuZero plan; and say why offline RL needs conservatism.
Value-based methods choose \(\arg\max_aQ(s,a)\). That is easy with a handful of actions and hard when actions are continuous (the torque of a robot joint, the steering angle of a car): every decision becomes an optimisation problem. A parametrised policy \(\pi_\theta(a\mid s)\) outputs actions directly, for example the mean and standard deviation of a Gaussian. It can also represent genuinely random behaviour, which is optimal in games such as rock–paper–scissors and useful whenever the state is only partly observed. And a small change in \(\theta\) changes the policy smoothly, whereas a small change in \(Q\) can flip the greedy action.
For an episodic task, let \(\tau=(s_0,a_0,r_1,s_1,a_1,\dots)\) be a trajectory generated by following \(\pi_\theta\). The objective is the expected return,
$$J(\theta)=\mathbb E_{\tau\sim\pi_\theta}\big[G_0\big],\qquad G_t=\sum_{k\ge0}\gamma^kr_{t+k+1}.$$The gradient of the objective is an expectation over trajectories of the policy's own score function, weighted by the return that follows each action:
$$\nabla_\theta J(\theta)=\mathbb E_{\tau\sim\pi_\theta}\Big[\sum_{t\ge0}\gamma^t\,G_t\,\nabla_\theta\log\pi_\theta(a_t\mid s_t)\Big].$$The environment's transition probabilities do not appear, so the gradient can be estimated from sampled episodes alone.
Write \(p_\theta(\tau)\) for the probability of a trajectory and \(R(\tau)=G_0\). Using \(\nabla p=p\,\nabla\log p\),
$$\nabla_\theta J=\nabla_\theta\int p_\theta(\tau)R(\tau)\,d\tau=\mathbb E_\tau\big[R(\tau)\,\nabla_\theta\log p_\theta(\tau)\big].$$The trajectory probability is a product of the start distribution, the policy and the transitions; only the policy depends on \(\theta\):
$$\log p_\theta(\tau)=\log\rho(s_0)+\sum_t\Big[\log\pi_\theta(a_t\mid s_t)+\log p(s_{t+1}\mid s_t,a_t)\Big],\qquad\nabla_\theta\log p_\theta(\tau)=\sum_t\nabla_\theta\log\pi_\theta(a_t\mid s_t).$$Finally, a reward received before time \(t\) is independent of the action at time \(t\) given the past, and \(\mathbb E[\nabla\log\pi_\theta(a_t\mid s_t)\mid s_t]=0\) (Theorem 22.2 with \(b=1\)). So those rewards contribute nothing, and only the rewards from \(t\) on remain: \(\sum_{k\ge t}\gamma^kr_{k+1}=\gamma^tG_t\). \(\square\)
REINFORCE (Williams, 1992) estimates this expectation with sampled episodes and takes a gradient step. In practice the factor \(\gamma^t\) is usually dropped, which slightly changes the objective but works well. The update has an intuitive form: make the actions that were followed by a high return more likely, and those followed by a low return less likely.
For any function \(b(s)\) that does not depend on the action,
$$\mathbb E_{a\sim\pi_\theta(\cdot\mid s)}\big[b(s)\,\nabla_\theta\log\pi_\theta(a\mid s)\big]=0 .$$So \(G_t\) in Theorem 22.1 can be replaced by \(G_t-b(s_t)\) without changing the expected gradient.
Using \(\pi\,\nabla\log\pi=\nabla\pi\) and pulling \(b(s)\) out of the sum over actions,
$$\sum_a\pi_\theta(a\mid s)\,b(s)\,\nabla_\theta\log\pi_\theta(a\mid s)=b(s)\,\nabla_\theta\sum_a\pi_\theta(a\mid s)=b(s)\,\nabla_\theta1=0 .$$For continuous actions the sum is an integral and the same argument holds. \(\square\)
Why bother? The raw return mixes two things: how good the action was, and how good the situation already was. If every return is large and positive, every sampled action is pushed up, and the signal is the small difference between large pushes. Subtracting a baseline, ideally close to \(v_\pi(s)\), leaves only the part that depends on the action, the advantage. The variance falls; the mean does not move.
# REINFORCE on CartPole, with and without a learned baseline (a one-hidden-layer network in numpy) import numpy as np, gymnasium as gym, time, warnings; warnings.filterwarnings('ignore') class Net: """x -> tanh(x W1 + b1) -> h W2 + b2, with Adam.""" def __init__(self, n_in, n_h, n_out, g, out_scale=0.01, lr=0.01): self.p = [g.standard_normal((n_in, n_h)) * np.sqrt(1 / n_in), np.zeros(n_h), g.standard_normal((n_h, n_out)) * out_scale, np.zeros(n_out)] self.m = [np.zeros_like(x) for x in self.p]; self.v = [np.zeros_like(x) for x in self.p]; self.t = 0; self.lr = lr def forward(self, x): h = np.tanh(x @ self.p[0] + self.p[1]); return h, h @ self.p[2] + self.p[3] def backward(self, x, h, dz): # gradients of a loss whose derivative w.r.t. the output is dz dh = dz @ self.p[2].T * (1 - h ** 2); return [x.T @ dh, dh.sum(0), h.T @ dz, dz.sum(0)] def step(self, grads): self.t += 1 for i, gr in enumerate(grads): self.m[i] = 0.9 * self.m[i] + 0.1 * gr; self.v[i] = 0.999 * self.v[i] + 0.001 * gr ** 2 self.p[i] -= self.lr * (self.m[i] / (1 - 0.9 ** self.t)) / (np.sqrt(self.v[i] / (1 - 0.999 ** self.t)) + 1e-8) def softmax(z): e = np.exp(z - z.max(-1, keepdims=True)); return e / e.sum(-1, keepdims=True) def rollouts(env, pol, n_ep, g, gamma=0.99): S, A, G, lens = [], [], [], [] for _ in range(n_ep): s, _ = env.reset(seed=int(g.integers(1 << 30))); rs, done = [], False while not done: a = int(g.random() < softmax(pol.forward(s)[1])[1]); S.append(s); A.append(a) s, r, term, trunc, _ = env.step(a); rs.append(r); done = term or trunc ret, acc = np.zeros(len(rs)), 0.0 for t in range(len(rs) - 1, -1, -1): acc = rs[t] + gamma * acc; ret[t] = acc # return-to-go G_t G.append(ret); lens.append(len(rs)) return np.array(S), np.array(A), np.concatenate(G), lens def pg_grads(pol, S, A, adv): """Gradient of -mean(adv * log pi(A|S)): the REINFORCE estimate (sign flipped for a minimiser).""" h, z = pol.forward(S); dz = softmax(z); dz[np.arange(len(A)), A] -= 1; return pol.backward(S, h, dz * adv[:, None] / len(A)) def reinforce(seed, baseline, iters=150, batch=8): env = gym.make('CartPole-v1'); g = np.random.default_rng(seed) pol, vf = Net(4, 32, 2, g), Net(4, 32, 1, g, out_scale=1.0); curve = [] for it in range(iters): S, A, G, lens = rollouts(env, pol, batch, g); curve.append(np.mean(lens)) if baseline: h, v = vf.forward(S); adv = G - v[:, 0] # subtract b(s): the critic's prediction of the return for _ in range(5): h, v = vf.forward(S); vf.step(vf.backward(S, h, 2 * (v - G[:, None]) / len(G))) else: adv = G pol.step(pg_grads(pol, S, A, adv)) return np.array(curve) t0 = time.time(); curves = {} for b in (False, True): curves[b] = np.array([reinforce(seed, b) for seed in range(5)]) c = curves[b]; print(f"REINFORCE {'with' if b else 'without'} a learned baseline: mean return over updates 1-10 / 71-80 / 141-150: " f"{c[:, :10].mean():.0f} / {c[:, 70:80].mean():.0f} / {c[:, -10:].mean():.0f} (5 seeds, 8 episodes per update)") # variance of single-episode gradient estimates at a fixed, partly trained policy, with three baselines pol = Net(4, 32, 2, np.random.default_rng(0)); env = gym.make('CartPole-v1'); g = np.random.default_rng(1) for it in range(25): S, A, G, lens = rollouts(env, pol, 8, g); pol.step(pg_grads(pol, S, A, G)) eps_ = [rollouts(env, pol, 1, g) for _ in range(300)]; Tm = max(len(e[2]) for e in eps_); bt, ct = np.zeros(Tm), np.zeros(Tm) for e in eps_: bt[:len(e[2])] += e[2]; ct[:len(e[2])] += 1 bt /= np.maximum(ct, 1); bconst = np.mean(np.concatenate([e[2] for e in eps_])) def estimates(kind): # one gradient estimate per episode: sum over its time steps return np.array([np.concatenate([x.ravel() for x in pg_grads(pol, S, A, G if kind == 0 else (G - bconst if kind == 1 else G - bt[:len(G)]))]) * len(A) for S, A, G, _ in eps_]) E_ = [estimates(k) for k in range(3)]; tv = [e.var(0).sum() for e in E_]; cos = lambda u, v: u @ v / np.linalg.norm(u) / np.linalg.norm(v) print(f"\nsingle-episode gradient estimates at a partly trained policy (mean episode length {np.mean([len(e[2]) for e in eps_]):.0f}; 300 episodes):") for k, lab in enumerate(['no baseline', f'constant baseline b = {bconst:.0f}', 'time-dependent baseline b_t (average return-to-go at step t)']): print(f" {lab:58s} total variance {tv[k]:9.3g} ({tv[0] / tv[k]:.2f} times smaller) cosine of mean gradient with no-baseline mean {cos(E_[k].mean(0), E_[0].mean(0)):.2f}") print(f"time {time.time() - t0:.0f} s")
REINFORCE without a learned baseline: mean return over updates 1-10 / 71-80 / 141-150: 40 / 402 / 484 (5 seeds, 8 episodes per update) REINFORCE with a learned baseline: mean return over updates 1-10 / 71-80 / 141-150: 40 / 491 / 499 (5 seeds, 8 episodes per update) single-episode gradient estimates at a partly trained policy (mean episode length 143; 300 episodes): no baseline total variance 7.86e+05 (1.00 times smaller) cosine of mean gradient with no-baseline mean 1.00 constant baseline b = 51 total variance 4.14e+05 (1.90 times smaller) cosine of mean gradient with no-baseline mean 0.98 time-dependent baseline b_t (average return-to-go at step t) total variance 3.06e+05 (2.57 times smaller) cosine of mean gradient with no-baseline mean 0.98 time 219 s
Both versions learn to balance the pole, but the baseline makes learning faster and steadier: after 71–80 updates the mean return is 491 with the learned baseline and 402 without, and after 150 updates 499 against 484. The variance experiment isolates the reason. At a fixed policy (mean episode length 143), subtracting the constant baseline \(b=51\) makes single-episode gradient estimates 1.90 times less variable, and a baseline that depends on the time step (a crude state-dependent baseline) 2.57 times. The mean gradient stays the same direction (cosine 0.98 and 0.98 with the no-baseline mean; it would be 1 with infinitely many episodes), as Theorem 22.2 promises.
An actor–critic method keeps two networks: the actor \(\pi_\theta\) and a critic \(V_\phi(s)\approx v_\pi(s)\) that serves as the baseline. The weight on \(\nabla\log\pi\) is then an estimate of the advantage \(A_\pi(s,a)=q_\pi(s,a)-v_\pi(s)\). Which estimate to use is the bias–variance question of Lecture 21b once more. The one-step estimate is the TD error
$$\delta_t=r_{t+1}+\gamma V_\phi(s_{t+1})-V_\phi(s_t),$$low in variance but biased if \(V_\phi\) is wrong. The Monte Carlo estimate \(G_t-V_\phi(s_t)\) is unbiased but noisy.
For \(0\le\lambda\le1\), the GAE estimate is an exponentially weighted sum of future TD errors:
$$\hat A_t^{\mathrm{GAE}(\gamma,\lambda)}=\sum_{l\ge0}(\gamma\lambda)^l\,\delta_{t+l}.$$\(\lambda=0\) gives the TD error \(\delta_t\); \(\lambda=1\) gives \(G_t-V_\phi(s_t)\), the Monte Carlo advantage.
Let
$$\begin{aligned}\hat A_t^{(k)}&=r_{t+1}+\gamma r_{t+2}+\cdots+\gamma^{k-1}r_{t+k}\\ &\quad+\gamma^kV_\phi(s_{t+k})-V_\phi(s_t)\end{aligned}$$be the \(k\)-step estimate. Then
$$\hat A_t^{(k)}=\sum_{l=0}^{k-1}\gamma^l\delta_{t+l},\qquad\hat A_t^{\mathrm{GAE}}=(1-\lambda)\sum_{k\ge1}\lambda^{k-1}\hat A_t^{(k)} .$$In \(\sum_{l\lt k}\gamma^l\delta_{t+l}\) the value terms telescope: each \(+\gamma^{l+1}V(s_{t+l+1})\) cancels the \(-\gamma^{l+1}V(s_{t+l+1})\) of the next term, leaving the rewards, \(\gamma^kV(s_{t+k})\) and \(-V(s_t)\). That is \(\hat A_t^{(k)}\).
Substitute this into the weighted sum and collect the coefficient of each \(\delta_{t+l}\). It appears in every \(\hat A_t^{(k)}\) with \(k>l\), with weight
$$(1-\lambda)\sum_{k>l}\lambda^{k-1}\gamma^l=\gamma^l\lambda^l .$$This is the GAE coefficient. Small \(\lambda\) trusts the critic (bias); large \(\lambda\) trusts the rewards (variance). \(\square\)
A policy-gradient step is only accurate close to the current policy: the gradient was estimated with data from \(\pi_{\text{old}}\). A step that is too large can collapse performance, and with it the quality of the next batch of data. The following identity says exactly how a new policy's return relates to the old one's.
For any two policies \(\pi\) and \(\pi'\) in a discounted MDP with start distribution \(\rho\),
$$J(\pi')-J(\pi)=\frac1{1-\gamma}\;\mathbb E_{s\sim d^{\pi'}}\,\mathbb E_{a\sim\pi'(\cdot\mid s)}\big[A_\pi(s,a)\big],$$where \(d^{\pi'}(s)=(1-\gamma)\sum_t\gamma^t\Pr(s_t=s\mid\pi')\) is the discounted state distribution of the new policy.
Follow \(\pi'\) from \(s_0\sim\rho\). Since \(A_\pi(s_t,a_t)=\mathbb E[r_{t+1}+\gamma v_\pi(s_{t+1})-v_\pi(s_t)\mid s_t,a_t]\), the sum telescopes:
$$\mathbb E_{\pi'}\Big[\sum_t\gamma^tA_\pi(s_t,a_t)\Big]=\mathbb E_{\pi'}\Big[\sum_t\gamma^tr_{t+1}\Big]+\mathbb E_{\pi'}\Big[\sum_t\big(\gamma^{t+1}v_\pi(s_{t+1})-\gamma^tv_\pi(s_t)\big)\Big]=J(\pi')-\mathbb E_{\rho}\big[v_\pi(s_0)\big].$$The last term is \(J(\pi)\). Rewriting the left side with the discounted state distribution gives the factor \(1/(1-\gamma)\). \(\square\)
The trouble is that \(d^{\pi'}\) is the state distribution of the policy we have not yet run. Replacing it by the old policy's \(d^{\pi}\) gives a surrogate objective \(L_\pi(\pi')\) that can be estimated from old data with importance weights. It is accurate only if the two policies are close.
With \(\varepsilon=\max_{s,a}|A_\pi(s,a)|\) and \(D^{\max}_{\mathrm{KL}}=\max_s\mathrm{KL}\big(\pi(\cdot\mid s)\,\Vert\,\pi'(\cdot\mid s)\big)\),
$$J(\pi')\;\ge\;L_\pi(\pi')-\frac{4\varepsilon\gamma}{(1-\gamma)^2}\,D^{\max}_{\mathrm{KL}}(\pi,\pi').$$(Statement.) Maximising the right-hand side can never make the policy worse. TRPO replaces the penalty by a constraint on the average KL divergence and solves it approximately with conjugate gradients.
Let \(r_t(\theta)=\pi_\theta(a_t\mid s_t)/\pi_{\text{old}}(a_t\mid s_t)\) be the probability ratio and \(\hat A_t\) an advantage estimate. Proximal policy optimisation maximises
$$L^{\mathrm{CLIP}}(\theta)=\mathbb E_t\Big[\min\big(r_t(\theta)\hat A_t,\ \operatorname{clip}(r_t(\theta),1-\epsilon,1+\epsilon)\,\hat A_t\big)\Big]$$for several epochs of minibatch gradient ascent on the same batch. Once the ratio has moved more than \(\epsilon\) in the helpful direction, the gradient of that sample is zero.
# PPO with generalised advantage estimation (GAE) on CartPole, in about 50 lines of numpy def gae(rew, val, done, last_val, gamma=0.99, lam=0.95): """A_t = sum_k (gamma lam)^k delta_(t+k), with delta_t = r_t + gamma V(s_(t+1)) - V(s_t), cut at episode ends.""" adv, acc = np.zeros(len(rew)), 0.0 for t in range(len(rew) - 1, -1, -1): nxt = last_val if t == len(rew) - 1 else val[t + 1] delta = rew[t] + gamma * nxt * (1 - done[t]) - val[t]; acc = delta + gamma * lam * (1 - done[t]) * acc; adv[t] = acc return adv def ppo(seed, total=100_000, n_steps=2048, epochs=10, mb=64, clip=0.2, lam=0.95, lr=3e-4, return_policy=False): env = gym.make('CartPole-v1'); g = np.random.default_rng(seed); pol, vf = Net(4, 64, 2, g, lr=lr), Net(4, 64, 1, g, out_scale=1.0, lr=1e-3) s, _ = env.reset(seed=seed); ep_ret, rets, curve, steps = 0.0, [], [], 0 while steps < total: S, A, R, D, LP = [], [], [], [], [] for _ in range(n_steps): # 1. collect a batch with the current policy p_ = softmax(pol.forward(s)[1]); a = int(g.random() < p_[1]); S.append(s); A.append(a); LP.append(np.log(p_[a])) s, r, term, trunc, _ = env.step(a); R.append(r); D.append(float(term or trunc)); ep_ret += r if term or trunc: rets.append(ep_ret); ep_ret = 0.0; s, _ = env.reset(seed=int(g.integers(1 << 30))) steps += n_steps; S, A, R, D, LP = np.array(S), np.array(A), np.array(R), np.array(D), np.array(LP) V = vf.forward(S)[1][:, 0]; adv = gae(R, V, D, vf.forward(s)[1][0], lam=lam); ret = adv + V for _ in range(epochs): # 2. several epochs of minibatch updates on the same batch for idx in np.array_split(g.permutation(n_steps), n_steps // mb): a_ = (adv[idx] - adv[idx].mean()) / (adv[idx].std() + 1e-8); h, z = pol.forward(S[idx]); pr = softmax(z) ratio = pr[np.arange(len(idx)), A[idx]] / np.exp(LP[idx]) active = ~(((ratio > 1 + clip) & (a_ > 0)) | ((ratio < 1 - clip) & (a_ < 0))) # where the clipped objective has a gradient dlogp = -ratio * a_ * active / len(idx) # d loss / d log pi(a|s) dz = -pr * dlogp[:, None]; dz[np.arange(len(idx)), A[idx]] += dlogp; pol.step(pol.backward(S[idx], h, dz)) h, v = vf.forward(S[idx]); vf.step(vf.backward(S[idx], h, 2 * (v - ret[idx, None]) / len(idx))) curve.append(np.mean(rets[-20:]) if rets else 0.0) return (pol, vf) if return_policy else np.array(curve) t0 = time.time(); ppo_runs = {} for label, kw in [('PPO, clip 0.2, lambda 0.95', {}), ('no clipping (clip = infinity)', {'clip': 1e9}), ('GAE lambda = 0 (one-step TD advantages)', {'lam': 0.0}), ('GAE lambda = 1 (Monte Carlo advantages)', {'lam': 1.0}), ('learning rate x10, clip 0.2', {'lr': 3e-3}), ('learning rate x10, no clipping', {'lr': 3e-3, 'clip': 1e9})]: c = np.array([ppo(seed, **kw) for seed in range(3)]); ppo_runs[label] = c print(f"{label:42s} mean return (last 20 episodes) after 20k / 50k / 100k steps: {c[:, 9].mean():5.0f} / {c[:, 24].mean():5.0f} / {c[:, -1].mean():5.0f}" f" (seeds at 100k: {', '.join(f'{x:.0f}' for x in c[:, -1])})") print(f"time {time.time() - t0:.0f} s; the maximum return in CartPole-v1 is 500")
PPO, clip 0.2, lambda 0.95 mean return (last 20 episodes) after 20k / 50k / 100k steps: 296 / 494 / 500 (seeds at 100k: 499, 500, 500) no clipping (clip = infinity) mean return (last 20 episodes) after 20k / 50k / 100k steps: 379 / 496 / 500 (seeds at 100k: 500, 500, 500) GAE lambda = 0 (one-step TD advantages) mean return (last 20 episodes) after 20k / 50k / 100k steps: 16 / 100 / 334 (seeds at 100k: 398, 313, 292) GAE lambda = 1 (Monte Carlo advantages) mean return (last 20 episodes) after 20k / 50k / 100k steps: 251 / 475 / 499 (seeds at 100k: 500, 500, 496) learning rate x10, clip 0.2 mean return (last 20 episodes) after 20k / 50k / 100k steps: 397 / 494 / 495 (seeds at 100k: 494, 500, 491) learning rate x10, no clipping mean return (last 20 episodes) after 20k / 50k / 100k steps: 204 / 205 / 251 (seeds at 100k: 258, 340, 156) time 434 s; the maximum return in CartPole-v1 is 500
With the standard settings PPO solves CartPole: the mean return reaches 494 after 50,000 steps and 500, the maximum, after 100,000. Two ablations behave as theory suggests. With \(\lambda=0\) the advantages are one-step TD errors of a critic that starts out wrong, and learning is far slower (334 after 100,000 steps); with \(\lambda=1\) (Monte Carlo advantages) it is a little slower than at 0.95 early on (251 against 296 after 20,000 steps). Removing the clip changes nothing at the standard learning rate (500): the steps are already small. Raise the learning rate tenfold and the clip earns its keep: with it PPO still reaches 495, without it the policy lurches and ends at 251. Clipping is insurance against steps that are too large, and on an easy task with careful settings the insurance is not needed.
An agent that becomes certain too early stops exploring. Maximum-entropy RL rewards the policy for staying random where randomness costs little: it maximises
$$J_\alpha(\pi)=\mathbb E_\pi\Big[\sum_t\gamma^t\big(r_{t+1}+\alpha\,\mathcal H(\pi(\cdot\mid s_t))\big)\Big],\qquad\mathcal H(p)=-\sum_ap(a)\log p(a),$$where the temperature \(\alpha\) sets the price of certainty. The value functions become "soft": the soft Bellman equation for the optimal policy reads
$$Q(s,a)=r(s,a)+\gamma\,\mathbb E_{s'}\big[V(s')\big],\qquad V(s)=\alpha\log\sum_a\exp\!\big(Q(s,a)/\alpha\big).$$In each state, the policy that maximises \(\sum_a\pi(a)Q(s,a)+\alpha\mathcal H(\pi)\) is the Boltzmann policy
$$\pi^*(a\mid s)=\frac{\exp\big(Q(s,a)/\alpha\big)}{\sum_{a'}\exp\big(Q(s,a')/\alpha\big)}=\exp\!\Big(\frac{Q(s,a)-V(s)}{\alpha}\Big),$$and the maximum value is \(V(s)=\alpha\log\sum_a\exp(Q(s,a)/\alpha)\). As \(\alpha\to0\) it becomes the greedy policy.
Write \(q_a=Q(s,a)/\alpha\) and \(\sigma_a=e^{q_a}/\sum_be^{q_b}\). For any distribution \(\pi\),
$$\sum_a\pi(a)q_a-\sum_a\pi(a)\log\pi(a)=\log\sum_be^{q_b}-\sum_a\pi(a)\log\frac{\pi(a)}{\sigma_a}=\log\sum_be^{q_b}-\mathrm{KL}(\pi\,\Vert\,\sigma).$$The KL divergence is non-negative and zero only at \(\pi=\sigma\). Multiplying by \(\alpha\) gives both claims. \(\square\)
Soft Actor-Critic (SAC; Haarnoja et al., 2018) applies this to continuous actions. Two critics learn the soft Q-function by bootstrapping from slowly moving target copies (the smaller of the two is used, to curb overestimation). The actor, a squashed Gaussian, is trained to minimise \(\mathbb E[\alpha\log\pi(a\mid s)-Q(s,a)]\), the per-state KL divergence of Theorem 22.6 up to a constant. SAC is off-policy, so it reuses a replay buffer, and it is among the most sample-efficient model-free methods for robot control.
# Soft Actor-Critic on Pendulum: the effect of the temperature alpha (JAX) import jax, jax.numpy as jnp def jinit(key, sizes): ps = [] for a, b in zip(sizes[:-1], sizes[1:]): key, k = jax.random.split(key); ps.append((jax.random.normal(k, (a, b)) * jnp.sqrt(1 / a), jnp.zeros(b))) return ps def jmlp(ps, x): for W, b in ps[:-1]: x = jax.nn.relu(x @ W + b) return x @ ps[-1][0] + ps[-1][1] def actor_sample(pa, s, key): # tanh-squashed Gaussian policy; returns action in [-1, 1] and log-probability out = jmlp(pa, s); mu, log_std = out[..., :1], jnp.clip(out[..., 1:], -5, 2) u = mu + jnp.exp(log_std) * jax.random.normal(key, mu.shape); a = jnp.tanh(u) logp = (-0.5 * ((u - mu) / jnp.exp(log_std)) ** 2 - log_std - 0.5 * jnp.log(2 * jnp.pi)).sum(-1) - jnp.log(1 - a ** 2 + 1e-6).sum(-1) return a, logp def jadam_step(p, g, st, lr=3e-4): m, v, t = st; t = t + 1 m = jax.tree.map(lambda m, g: 0.9 * m + 0.1 * g, m, g); v = jax.tree.map(lambda v, g: 0.999 * v + 0.001 * g * g, v, g) return jax.tree.map(lambda p, m, v: p - lr * (m / (1 - 0.9 ** t)) / (jnp.sqrt(v / (1 - 0.999 ** t)) + 1e-8), p, m, v), (m, v, t) def jadam_init(p): return (jax.tree.map(jnp.zeros_like, p), jax.tree.map(jnp.zeros_like, p), 0) @jax.jit def sac_update(P, O, batch, key, log_alpha): s, a, r, s2, d = batch; k1, k2 = jax.random.split(key); alpha = jnp.exp(log_alpha) a2, lp2 = actor_sample(P['a'], s2, k1); sa2 = jnp.concatenate([s2, a2], -1) q_next = jnp.minimum(jmlp(P['t1'], sa2)[:, 0], jmlp(P['t2'], sa2)[:, 0]) - alpha * lp2 # soft value of s' y = jax.lax.stop_gradient(r + 0.99 * (1 - d) * q_next); sa = jnp.concatenate([s, a], -1) def qloss(pq): return jnp.mean((jmlp(pq, sa)[:, 0] - y) ** 2) def aloss(pa): an, lp = actor_sample(pa, s, k2); san = jnp.concatenate([s, an], -1) return jnp.mean(alpha * lp - jnp.minimum(jmlp(P['q1'], san)[:, 0], jmlp(P['q2'], san)[:, 0])), lp P = dict(P); O = dict(O) for q in ('q1', 'q2'): P[q], O[q] = jadam_step(P[q], jax.grad(qloss)(P[q]), O[q]) (al, lp), ga = jax.value_and_grad(aloss, has_aux=True)(P['a']); P['a'], O['a'] = jadam_step(P['a'], ga, O['a']) for t_, q in (('t1', 'q1'), ('t2', 'q2')): P[t_] = jax.tree.map(lambda x, y_: 0.995 * x + 0.005 * y_, P[t_], P[q]) # slowly moving targets return P, O, log_alpha act_j = jax.jit(lambda pa, s, k: actor_sample(pa, s, k)[0]) def sac(alpha, seed, steps=12_000): env = gym.make('Pendulum-v1'); key = jax.random.PRNGKey(seed); ks = jax.random.split(key, 6); g = np.random.default_rng(seed) P = {'a': jinit(ks[0], [3, 64, 64, 2]), 'q1': jinit(ks[1], [4, 64, 64, 1]), 'q2': jinit(ks[2], [4, 64, 64, 1])}; P['t1'], P['t2'] = P['q1'], P['q2'] O = {k: jadam_init(P[k]) for k in ('a', 'q1', 'q2')}; log_alpha = jnp.log(alpha) buf = {k: np.zeros((steps, n), np.float32) for k, n in (('s', 3), ('a', 1), ('r', 1), ('s2', 3), ('d', 1))} s, _ = env.reset(seed=seed); rets, ep = [], 0.0 for t in range(steps): key, k = jax.random.split(key) a = g.uniform(-1, 1, 1) if t < 1000 else np.asarray(act_j(P['a'], jnp.asarray(s[None]), k))[0] s2, r, term, trunc, _ = env.step(2 * a); ep += r for n_, val in (('s', s), ('a', a), ('r', r), ('s2', s2), ('d', float(term))): buf[n_][t] = val s = s2 if term or trunc: rets.append(ep); ep = 0.0; s, _ = env.reset(seed=int(g.integers(1 << 30))) if t >= 1000: i = g.integers(0, t + 1, 256); batch = (buf['s'][i], buf['a'][i], buf['r'][i, 0], buf['s2'][i], buf['d'][i, 0]) key, k = jax.random.split(key); P, O, log_alpha = sac_update(P, O, batch, k, log_alpha) i = g.integers(0, steps, 2000); _, lp = actor_sample(P['a'], jnp.asarray(buf['s'][i]), key) return np.mean(rets[-10:]), float(-jnp.mean(lp)) # return, and the policy's entropy (estimated) t0 = time.time(); sac_res = {} for alpha in (0.01, 0.2, 5.0, 50.0): sac_res[alpha] = [sac(alpha, seed) for seed in range(2)] print(f"SAC, temperature alpha = {alpha:<5}: mean return of the last 10 training episodes {np.mean([x[0] for x in sac_res[alpha]]):7.0f}" f" (seeds: {', '.join(f'{x[0]:.0f}' for x in sac_res[alpha])}); policy entropy {np.mean([x[1] for x in sac_res[alpha]]):+.2f} nats") env = gym.make('Pendulum-v1'); g = np.random.default_rng(0); rr = [] for k in range(20): s, _ = env.reset(seed=k); done, tot = False, 0.0 while not done: s, r, term, trunc, _ = env.step(g.uniform(-2, 2, 1)); tot += r; done = term or trunc rr.append(tot) print(f"random actions: mean return {np.mean(rr):.0f} over 20 episodes; time {time.time() - t0:.0f} s")
SAC, temperature alpha = 0.01 : mean return of the last 10 training episodes -140 (seeds: -158, -123); policy entropy -4.44 nats SAC, temperature alpha = 0.2 : mean return of the last 10 training episodes -140 (seeds: -157, -122); policy entropy -1.22 nats SAC, temperature alpha = 5.0 : mean return of the last 10 training episodes -300 (seeds: -378, -223); policy entropy +0.45 nats SAC, temperature alpha = 50.0 : mean return of the last 10 training episodes -1075 (seeds: -1090, -1060); policy entropy +0.68 nats random actions: mean return -1246 over 20 episodes; time 598 s
SAC learns to swing the pendulum up and hold it within 12,000 steps (random actions score −1246). At small temperatures the result hardly depends on \(\alpha\): \(\alpha=0.01\) gives −140 and \(\alpha=0.2\) gives −140. Rewards here are large in size (as low as about −16 per step), so a small entropy bonus barely changes the best policy. Make the temperature large and the trade-off shows: at \(\alpha=5\) the return is −300, and at \(\alpha=50\) it is −1075, while the policy's entropy rises from −4.44 to +0.68 nats. The agent is paid so much for randomness that it stops trying to balance. Haarnoja et al. (2018b) therefore tune \(\alpha\) automatically, to hold the entropy near a target.
Maximum-entropy RL has a probabilistic reading (Levine, 2018). Add to each time step a binary "optimality" variable with \(p(\mathcal O_t=1\mid s_t,a_t)\propto\exp(r_t/\alpha)\), and ask for the posterior over trajectories given that every step was optimal. With a uniform action prior and deterministic dynamics, the exact posterior over actions is the soft-optimal policy of Theorem 22.6. With random dynamics exact inference becomes over-optimistic (it assumes the dice will fall favourably), and the fix is variational inference (Lecture 16b's ELBO) with the policy as the approximate posterior, which recovers maximum-entropy RL. The temperature plays the part of the noise level in the likelihood. Lecture 22b meets the same structure again: a KL-regularised objective whose optimum is the prior reweighted by \(\exp(r/\beta)\).
When a model of the environment is available, as in board games, an agent can plan: look ahead before acting. Monte Carlo tree search (MCTS; Coulom, 2006; Kocsis and Szepesvári, 2006) builds a search tree one simulation at a time. Each simulation has four steps:
After many simulations, the move with the most visits is played. Promising lines are explored deeply, poor ones only lightly, and no evaluation function is needed.
# Monte Carlo tree search (UCT) on Connect Four: playing strength grows with the number of simulations import math H1 = 7 # bitboard: 7 columns x (6 rows + 1 sentinel) TOP = sum(1 << (c * H1 + 5) for c in range(7)) def won(b): for d in (1, H1, H1 - 1, H1 + 1): # vertical, horizontal, two diagonals m = b & (b >> d) if m & (m >> 2 * d): return True return False class C4: def __init__(s): s.b = [0, 0]; s.h = [c * H1 for c in range(7)]; s.p = 0; s.n = 0 def moves(s): return [c for c in range(7) if not (1 << s.h[c]) & TOP << 1 and s.h[c] < c * H1 + 6] def play(s, c): s.b[s.p] |= 1 << s.h[c]; s.h[c] += 1; s.n += 1; s.p ^= 1 def copy(s): t = C4(); t.b = s.b[:]; t.h = s.h[:]; t.p = s.p; t.n = s.n; return t def winner(s): return 0 if won(s.b[0]) else (1 if won(s.b[1]) else (-1 if s.n == 42 else None)) def rollout(st, g): st = st.copy() while (w := st.winner()) is None: mv = st.moves(); st.play(mv[g.integers(len(mv))]) return w def uct_move(st, sims, g, c=1.4): """UCT: select by upper confidence bounds, expand one node, simulate randomly to the end, back up the result.""" root = {'N': 0, 'W': 0.0, 'kids': {}, 'untried': st.moves(), 'player': st.p} for _ in range(sims): node, s, path = root, st.copy(), [root] while not node['untried'] and node['kids'] and s.winner() is None: # 1. selection node = max(node['kids'].values(), key=lambda k: k['W'] / k['N'] + c * math.sqrt(math.log(node['N']) / k['N'])) s.play(node['move']); path.append(node) if node['untried'] and s.winner() is None: # 2. expansion mv = node['untried'].pop(g.integers(len(node['untried']))); mover = s.p; s.play(mv) kid = {'N': 0, 'W': 0.0, 'kids': {}, 'untried': s.moves() if s.winner() is None else [], 'move': mv, 'mover': mover} node['kids'][mv] = kid; path.append(kid) w = rollout(s, g) # 3. simulation for nd in path: # 4. backup: reward from the view of the player who moved into nd nd['N'] += 1 if 'mover' in nd: nd['W'] += 1.0 if w == nd['mover'] else (0.5 if w == -1 else 0.0) return max(root['kids'].values(), key=lambda k: k['N'])['move'] def match(sims_a, sims_b, games, seed): g = np.random.default_rng(seed); score = 0.0 for k in range(games): st = C4(); a_first = k % 2 == 0 while (w := st.winner()) is None: a_turn = (st.p == 0) == a_first; sims = sims_a if a_turn else sims_b mv = st.moves(); st.play(mv[g.integers(len(mv))] if sims == 0 else uct_move(st, sims, g)) a_player = 0 if a_first else 1; score += 1.0 if w == a_player else (0.5 if w == -1 else 0.0) return score / games t0 = time.time() for a, b, n_ in [(25, 0, 50), (100, 25, 50), (400, 100, 50), (1600, 400, 50)]: print(f"UCT with {a:3d} simulations per move against {'random play' if b == 0 else f'UCT with {b} simulations'}: " f"scores {match(a, b, n_, a + b):.0%} over {n_} games (win 1, draw 0.5; first move alternates)") print(f"time {time.time() - t0:.0f} s")
UCT with 25 simulations per move against random play: scores 88% over 50 games (win 1, draw 0.5; first move alternates) UCT with 100 simulations per move against UCT with 25 simulations: scores 86% over 50 games (win 1, draw 0.5; first move alternates) UCT with 400 simulations per move against UCT with 100 simulations: scores 88% over 50 games (win 1, draw 0.5; first move alternates) UCT with 1600 simulations per move against UCT with 400 simulations: scores 71% over 50 games (win 1, draw 0.5; first move alternates) time 185 s
Search is strength. UCT with 25 simulations per move scores 88% against random play; UCT with 100 simulations per move scores 86% against UCT with 25 simulations; UCT with 400 simulations per move scores 88% against UCT with 100 simulations; UCT with 1600 simulations per move scores 71% against UCT with 400 simulations (50 games each, alternating who moves first). Each fourfold increase in search buys a clear gain, with no knowledge of Connect Four beyond its rules: the random play-outs discover threats and wins by themselves. The last step gains less than the earlier ones, and the gains would keep flattening, because random play-outs are a poor judge of quiet positions, which is what AlphaZero's value network fixes.
Random play-outs are a weak evaluation. AlphaZero (Silver et al., 2018) replaces them with a neural network that outputs a value for the position and prior probabilities for the moves; the priors steer selection (the PUCT rule) and the value replaces the play-out. The network is trained on games of self-play: towards the search's visit distribution (a better policy than the network's own) and towards the final result. Search improves the network, and the network improves the search. Starting from the rules alone, AlphaZero beat the strongest programs at chess, shogi and Go. MuZero (Schrittwieser et al., 2020) goes further and does not need the rules: it learns a model of the environment's dynamics in a latent space, trained only to predict rewards, values and policies, and searches inside that model, which also let it play Atari. Dreamer (Hafner et al., 2020, 2023) learns a world model from pixels and trains an actor–critic entirely on imagined trajectories, so that most learning happens without touching the real environment.
Ronald Williams introduced REINFORCE in 1987 and gave its standard account in 1992. Gerald Tesauro's TD-Gammon (1992) and Rémi Coulom's Monte Carlo tree search (2006) were milestones in games, and MCTS took computer Go from beginner to strong amateur within a few years. In March 2016 DeepMind's AlphaGo, which combined MCTS with policy and value networks trained on human games and by self-play, beat Lee Sedol 4–1 in Seoul. Its 37th move in the second game, a shoulder hit on the fifth line that commentators first took for a mistake, became a symbol of machine creativity. AlphaGo Zero (2017) dropped the human games, AlphaZero (2018) applied the same recipe to chess and shogi, and MuZero (2020) dropped the rules. In 2019 OpenAI Five beat the world champions at Dota 2 and DeepMind's AlphaStar reached Grandmaster level in StarCraft II, both with large-scale policy-gradient training.
Often the agent cannot experiment: medical treatments, driving and industrial control come with logs of past behaviour, and new trials are expensive or dangerous. Offline RL learns a policy from a fixed data set collected by some behaviour policy \(\pi_b\). Two questions arise: how good would a new policy be (evaluation), and how to find a good one (control).
Let trajectories be collected by \(\pi_b\), and let \(\pi\) take an action only where \(\pi_b\) can. With per-step ratios \(\rho_t=\pi(a_t\mid s_t)/\pi_b(a_t\mid s_t)\),
$$\mathbb E_{\tau\sim\pi_b}\Big[\Big(\prod_{t=0}^{T-1}\rho_t\Big)G_0\Big]=\mathbb E_{\tau\sim\pi}\big[G_0\big]=J(\pi).$$The doubly robust estimator (Jiang and Li, 2016; Thomas and Brunskill, 2016) adds a learned model \(\hat Q\) as a control variate. It is unbiased if the ratios are correct, whatever \(\hat Q\) is, and consistent if \(\hat Q\) is correct, even when the ratios are wrong: two chances to be right. (Second part: statement.)
The probability of a trajectory under a policy is \(\rho(s_0)\prod_t\pi(a_t\mid s_t)p(s_{t+1}\mid s_t,a_t)\). Dividing the two, the start distribution and the transitions cancel:
$$\frac{p_\pi(\tau)}{p_{\pi_b}(\tau)}=\prod_t\frac{\pi(a_t\mid s_t)}{\pi_b(a_t\mid s_t)}=\prod_t\rho_t .$$Hence \(\mathbb E_{\pi_b}[\prod_t\rho_t\,G_0]=\sum_\tau p_{\pi_b}(\tau)\frac{p_\pi(\tau)}{p_{\pi_b}(\tau)}G_0(\tau)=\mathbb E_\pi[G_0]\). The condition on supports ensures no division by zero where \(p_\pi>0\). \(\square\)
The product of ratios makes the variance grow exponentially with the horizon, which is why importance sampling is used mainly for short horizons and bandits (the ZOZOTOWN example of Lecture 21a). For control, the danger is different. Q-learning on a fixed data set evaluates \(\max_aQ(s',a)\), including actions that never appear in the data. Their values are pure extrapolation, often wildly optimistic, and the greedy policy steers straight towards them, with no new data to correct the mistake. Conservative Q-learning (CQL; Kumar et al., 2020) adds a penalty that pushes down the values of all actions and pushes up those actually in the data:
$$\mathcal L_{\mathrm{CQL}}=\mathcal L_{\mathrm{TD}}+\alpha\,\mathbb E_{s\sim\mathcal D}\Big[\log\sum_a\exp Q(s,a)-\mathbb E_{a\sim\mathcal D}\,Q(s,a)\Big].$$A different route treats offline RL as supervised sequence modelling: the Decision Transformer (Chen et al., 2021) is a GPT-style model trained to predict the next action given past states, actions and the return still to come; at test time one asks for a high return and lets it act.
# Offline RL on CartPole: behaviour cloning, offline Q-learning and conservative Q-learning (CQL) from a fixed data set import copy def run_policy(act, n_ep, g, env=gym.make('CartPole-v1')): out = [] for _ in range(n_ep): s, _ = env.reset(seed=int(g.integers(1 << 30))); done, tot = False, 0.0 while not done: s, r, term, trunc, _ = env.step(act(s)); tot += r; done = term or trunc out.append(tot) return np.mean(out) g = np.random.default_rng(5) expert, critic = ppo(7, total=60_000, return_policy=True) # a good policy, trained online with PPO greedy = lambda net: (lambda s: int(net.forward(s)[1].argmax())) eps_behaviour = lambda s: int(g.integers(2)) if g.random() < 0.5 else greedy(expert)(s) # behaviour: half random, half expert env = gym.make('CartPole-v1'); D = {k: [] for k in 'SARNT'} for ep in range(100): # the fixed data set: 100 episodes of the noisy behaviour policy s, _ = env.reset(seed=int(g.integers(1 << 30))); done = False while not done: a = eps_behaviour(s); s2, r, term, trunc, _ = env.step(a) for k, v in zip('SARNT', (s, a, r, s2, float(term))): D[k].append(v) s = s2; done = term or trunc D = {k: np.array(v) for k, v in D.items()}; n_data = len(D['A']) print(f"offline data: 100 episodes, {n_data:,} transitions; behaviour policy return {run_policy(eps_behaviour, 20, g):.0f}; expert return {run_policy(greedy(expert), 20, g):.0f}") def behaviour_cloning(steps=3000): net = Net(4, 64, 2, np.random.default_rng(0), lr=1e-3) for _ in range(steps): i = g.integers(0, n_data, 256); h, z = net.forward(D['S'][i]); dz = softmax(z); dz[np.arange(256), D['A'][i]] -= 1; net.step(net.backward(D['S'][i], h, dz / 256)) return net def offline_q(cql_alpha, steps=6000, gamma=0.99): q = Net(4, 64, 2, np.random.default_rng(0), out_scale=0.1, lr=1e-3); qt = copy.deepcopy(q) for t in range(steps): i = g.integers(0, n_data, 256); S, A, R, S2, T = D['S'][i], D['A'][i], D['R'][i], D['N'][i], D['T'][i] y = R + gamma * (1 - T) * qt.forward(S2)[1].max(1); h, Qs = q.forward(S); dz = cql_alpha * softmax(Qs) dz[np.arange(256), A] += 2 * (Qs[np.arange(256), A] - y) - cql_alpha # TD error, plus the CQL push-down on unseen actions q.step(q.backward(S, h, dz / 256)) if t % 200 == 0: qt = copy.deepcopy(q) return q res_off = {'behaviour cloning': run_policy(greedy(behaviour_cloning()), 20, g)} for a in (0.0, 1.0, 5.0): qn = offline_q(a); qs = qn.forward(D['S'])[1] res_off[f"offline Q-learning{'' if a == 0 else f' + CQL (alpha = {a:g})'}"] = run_policy(greedy(qn), 20, g) print(f" {'offline Q-learning' if a == 0 else f'CQL, alpha = {a:g}':22s} mean Q on the data's own actions {qs[np.arange(n_data), D['A']].mean():7.1f}; " f"on the other action {qs[np.arange(n_data), 1 - D['A']].mean():7.1f}") for k, v in res_off.items(): print(f"{k:34s} return of the learned policy {v:5.0f} (20 episodes)")
offline data: 100 episodes, 17,214 transitions; behaviour policy return 210; expert return 500 offline Q-learning mean Q on the data's own actions 27.6; on the other action 27.1 CQL, alpha = 1 mean Q on the data's own actions 27.8; on the other action 27.2 CQL, alpha = 5 mean Q on the data's own actions 28.1; on the other action 27.6 behaviour cloning return of the learned policy 500 (20 episodes) offline Q-learning return of the learned policy 436 (20 episodes) offline Q-learning + CQL (alpha = 1) return of the learned policy 463 (20 episodes) offline Q-learning + CQL (alpha = 5) return of the learned policy 500 (20 episodes)
The data set holds 17,214 transitions from a behaviour policy that scores 210 (the expert alone scores 500). Behaviour cloning scores 500: in every state the expert's action is the more common one in the data (it is chosen three times in four), so imitating the majority recovers the expert. Plain offline Q-learning scores 436, below what the data allow, and CQL raises this to 463 at \(\alpha=1\) and 500 at \(\alpha=5\). This data set is a kind one, since both actions appear in every region of the state space, so extrapolation does little harm; Exercise 6 removes the random half and makes the problem much harder.
CartPole's data set is kind, and it is home-made. Offline RL papers report results on shared benchmarks instead, above all D4RL (Fu et al., 2020), now maintained in the Minari library. The next box takes one of them: a point mass in a U-shaped maze, pushed by a two-dimensional force, rewarded at every step by \(e^{-\text{distance to the goal}}\). The million logged steps come from a controller that follows waypoints to a series of random goals, with noise added to its actions; the test is to reach one fixed goal within 300 steps. Scores are normalised so that 0 is a random policy and 100 is the controller that made the data. Beside behaviour cloning we run TD3 (Fujimoto, van Hoof and Meger, 2018), an off-policy actor–critic for continuous actions (a deterministic actor, twin critics, smoothed targets and actor updates every second step; much like SAC without the entropy), first unconstrained and then with the one-line conservative fix of TD3+BC (Fujimoto and Gu, 2021): the actor maximises \(\lambda Q(s,\pi(s))-(\pi(s)-a)^2\), with \(\lambda=2.5/\overline{|Q|}\), so it is penalised for moving away from the logged action \(a\).
13,210 episodes and 1,000,000 transitions collected in PointMaze_UMazeDense-v3 (Gymnasium-Robotics, MuJoCo physics) by a PD controller following waypoints from Q-iteration, with noise on the actions (Fu et al., 2020; Farama Foundation's Minari release D4RL/pointmaze/umaze-dense-v2, from the Hugging Face Hub). Each state is the point's position and velocity plus the goal's position.
# A standard offline benchmark: D4RL PointMaze U-maze (dense reward), 1 million logged steps from a noisy waypoint controller (Minari) import h5py, json, gymnasium as gym, gymnasium_robotics; gym.register_envs(gymnasium_robotics) from functools import partial f5 = h5py.File('data/minari/umaze-dense-v2/main_data.hdf5', 'r'); S_, A_, R_, S2_, D_ = [], [], [], [], [] for ep in f5.values(): # state = position, velocity and goal (6 numbers); action = force (2) o = np.hstack([ep['observations/observation'][:], ep['observations/desired_goal'][:]]).astype(np.float32) S_.append(o[:-1]); S2_.append(o[1:]); A_.append(ep['actions'][:]); R_.append(ep['rewards'][:]); D_.append(ep['terminations'][:]) S_, A_, R_, S2_, D_ = (np.concatenate(x).astype(np.float32) for x in (S_, A_, R_, S2_, D_)) mu_s, sd_s = S_.mean(0), S_.std(0) + 1e-3; nz = lambda s: (s - mu_s) / sd_s data = tuple(jnp.asarray(x) for x in (nz(S_), A_, R_, nz(S2_), D_)); N5 = len(S_) print(f"{len(f5):,} episodes, {N5:,} transitions; mean reward per step {R_.mean():.3f}") @partial(jax.jit, static_argnames=('bc', 'actor')) def td3_step(P, O, batch, key, bc, actor): s, a, r, s2, d = batch; O = dict(O) noise = jnp.clip(0.2 * jax.random.normal(key, a.shape), -0.5, 0.5); a2 = jnp.clip(jnp.tanh(jmlp(P['ta'], s2)) + noise, -1, 1) sa2 = jnp.concatenate([s2, a2], -1); y = r + 0.99 * (1 - d) * jnp.minimum(jmlp(P['t1'], sa2)[:, 0], jmlp(P['t2'], sa2)[:, 0]) y = jax.lax.stop_gradient(y); sa = jnp.concatenate([s, a], -1) lq = lambda q: jnp.mean((jmlp(q, sa)[:, 0] - y) ** 2) def la(pa): # TD3+BC: maximise lambda Q, lambda = 2.5 / mean|Q|, minus (pi(s) - a)^2 pi = jnp.tanh(jmlp(pa, s)); q = jmlp(P['q1'], jnp.concatenate([s, pi], -1))[:, 0] lam = (2.5 if bc else 1.0) / jax.lax.stop_gradient(jnp.mean(jnp.abs(q))) return -lam * jnp.mean(q) + (jnp.mean((pi - a) ** 2) if bc else 0.0) new = dict(P) for k in ('q1', 'q2'): g = jax.grad(lq)(P[k]); new[k], O[k] = jadam_step(P[k], g, O[k]) if actor: # TD3: the actor and the targets move every second step g = jax.grad(la)(P['a']); new['a'], O['a'] = jadam_step(P['a'], g, O['a']) for k, t in (('q1', 't1'), ('q2', 't2'), ('a', 'ta')): new[t] = jax.tree.map(lambda x, y_: 0.995 * x + 0.005 * y_, new[t], new[k]) return new, O @jax.jit def bc_step(pa, O, s, a): g = jax.grad(lambda pa: jnp.mean((jnp.tanh(jmlp(pa, s)) - a) ** 2))(pa); return jadam_step(pa, g, O) meta = json.load(open('data/minari/umaze-dense-v2/metadata.json')); spec = json.loads(meta['eval_env_spec']) env5 = gym.make(spec['id'], max_episode_steps=spec['max_episode_steps'], **spec['kwargs']) # the evaluation task: a fixed goal cell, 300 steps act = jax.jit(lambda pa, s: jnp.tanh(jmlp(pa, s))) def score(pa, q=None, n=30): tot, disc, pred = [], [], [] for i in range(n): ob, _ = env5.reset(seed=1000 + i); ret, dret, k, done = 0.0, 0.0, 0, False while not done: s = nz(np.hstack([ob['observation'], ob['desired_goal']]).astype(np.float32)) if k == 0 and q is not None: pred.append(float(jmlp(q, jnp.concatenate([s, act(pa, s)]))[0])) # the critic's forecast at the start ob, r, term, trunc, _ = env5.step(np.asarray(act(pa, s))); ret += r; dret += 0.99 ** k * r; k += 1; done = term or trunc tot.append(ret); disc.append(dret) lo, hi = meta['ref_min_score'], meta['ref_max_score'] return 100 * (np.mean(tot) - lo) / (hi - lo), np.mean(disc), (np.mean(pred) if pred else None) # 0 = random, 100 = the controller def run(method, steps=30_000, seed=0): key = jax.random.PRNGKey(seed); ks = jax.random.split(key, 6); g = np.random.default_rng(seed) if method == 'BC': pa = jinit(ks[0], [6, 256, 256, 2]); O = jadam_init(pa) for t in range(steps): i = g.integers(0, N5, 256); pa, O = bc_step(pa, O, data[0][i], data[1][i]) return score(pa)[0] P = {'a': jinit(ks[0], [6, 256, 256, 2]), 'q1': jinit(ks[1], [8, 256, 256, 1]), 'q2': jinit(ks[2], [8, 256, 256, 1])} P.update(ta=P['a'], t1=P['q1'], t2=P['q2']); O = {k: jadam_init(P[k]) for k in ('a', 'q1', 'q2')} for t in range(steps): i = g.integers(0, N5, 256); P, O = td3_step(P, O, tuple(x[i] for x in data), jax.random.fold_in(key, t), method == 'TD3+BC', t % 2 == 1) return score(P['a'], P['q1']) t0 = time.time(); sc_bc = run('BC'); (sc_td3, r_td3, q_td3), (sc_tb, r_tb, q_tb) = run('TD3'), run('TD3+BC') print(f"normalised score (0 = random, 100 = the controller that made the data), 30 evaluation episodes, 30,000 updates each:") print(f" behaviour cloning {sc_bc:6.1f}") print(f" TD3, no constraint {sc_td3:6.1f} critic's forecast at the start {q_td3:6.1f}; discounted return actually obtained {r_td3:5.1f}") print(f" TD3+BC (Fujimoto & Gu 2021) {sc_tb:6.1f} critic's forecast at the start {q_tb:6.1f}; discounted return actually obtained {r_tb:5.1f}") print(f" (rewards are at most 1, so no discounted return can exceed 1 / (1 - 0.99) = 100); time {time.time() - t0:.0f} s")
13,210 episodes, 1,000,000 transitions; mean reward per step 0.243 normalised score (0 = random, 100 = the controller that made the data), 30 evaluation episodes, 30,000 updates each: behaviour cloning 55.6 TD3, no constraint -11.7 critic's forecast at the start 16.3; discounted return actually obtained 12.6 TD3+BC (Fujimoto & Gu 2021) 54.1 critic's forecast at the start 5.8; discounted return actually obtained 36.1 (rewards are at most 1, so no discounted return can exceed 1 / (1 - 0.99) = 100); time 868 s
Unconstrained TD3 fails outright: it scores −11.7, below a random policy. Its critic is too optimistic about it: at the start of each test episode it forecasts a discounted return of 16.3, and the policy collects 12.6. The actor has steered towards actions the data rarely or never contain, where the critic's values are guesses that no data correct, the extrapolation error that motivated CQL. TD3+BC keeps the actor near the logged actions and scores 54.1; its critic errs the other way, forecasting 5.8 where the policy obtains 36.1. Conservatism bought a safe policy, not an accurate value function: the behaviour-cloning term, not the critic, is doing most of the work. Behaviour cloning alone scores 55.6. On this data set, as on CartPole's, imitation is a strong baseline because the data come from a competent controller; with one seed and 30,000 updates the two differ by less than one would trust from a single run, and both fall short of the controller itself, which planned with a map of the maze. Published D4RL comparisons point the same way: conservative methods win clearly on data sets of mixed or poor quality, and barely on expert data.
Evaluating a new policy from logs asks what would have happened under different actions: a counterfactual. Importance weighting is inverse propensity weighting (Lecture 13 and Lecture 21a), and the doubly robust estimator is the same object as in causal effect estimation, with the same double protection. The assumptions are also the same: the logged probabilities must be known, every action the new policy might take must sometimes have been taken (overlap), and nothing that influenced both the logged action and the outcome may be missing from the state (no unmeasured confounding). A doctor who treated sicker patients more aggressively, on the basis of signs not recorded in the data, makes the treatment look harmful in the logs. No amount of offline RL can undo that without extra assumptions or experiments.
RL has become a tool for controlling quantum systems, where accurate models are expensive and every measurement disturbs the state. Bukov et al. (Physical Review X, 2018) used RL to design pulse sequences that prepare target quantum states, and found protocols competitive with optimal control. Fösel, Tighineanu, Weiss and Marquardt (Physical Review X, 2018) trained networks with RL to discover feedback strategies that protect qubits against noise, a form of quantum error correction found without being told the textbook codes. AlphaTensor-Quantum (Ruiz et al., Nature Machine Intelligence, 2025) adapted AlphaZero-style search to reduce the number of costly T gates in quantum circuits. The speed-up here is classical: RL makes quantum hardware better, rather than quantum hardware making RL faster.
The same algorithms now act outside games. Policies trained with PPO and SAC in simulation, with randomised physics so that they transfer, control legged robots and robot hands in the real world. Degrave et al. (Nature, 2022) shaped the plasma of the TCV tokamak in Lausanne with an RL controller. AlphaTensor (Fawzi et al., Nature, 2022) found faster matrix-multiplication algorithms for some sizes, and AlphaDev (Mankowitz et al., Nature, 2023) found sorting routines now in the LLVM C++ standard library. RL for chip floorplanning (Mirhoseini et al., Nature, 2021) has been contested: later studies could not reproduce its advantage over established tools, and the debate over evaluation is itself a lesson in the critical reading of Lecture 23. The most widespread use of RL today is in Lecture 22b: shaping the behaviour of language models.
\(\log\pi_\theta(a)=\theta_a-\log\sum_be^{\theta_b}\), whose derivative with respect to \(\theta_j\) is \(\mathbf 1[a=j]-e^{\theta_j}/\sum_be^{\theta_b}\). The estimate is \(r\,(\mathbf 1[a=j]-\pi_\theta(j))\). If every reward is shifted by a constant \(c\), each estimate shifts by \(c\,(\mathbf 1[a=j]-\pi_\theta(j))\), which has mean zero but large variance when \(c\) is large: the effect shown in the variance lab.
The mean does not depend on \(b\) (Theorem 22.2), so minimise \(\mathbb E[(r-b)^2g^2]\). Setting the derivative to zero gives
$$b^*=\frac{\mathbb E[r\,g^2]}{\mathbb E[g^2]},$$a weighted average of rewards, weighted by \(g^2\). In practice the plain expected reward (or \(v_\pi(s)\)) is used; it is close to optimal and easy to learn.
Inside the interval, clipping does nothing, so both arguments equal \(rA\). For \(A>0\) and \(r>1+\epsilon\), the clipped term is \((1+\epsilon)A\lt rA\), so the minimum is the constant \((1+\epsilon)A\), with zero gradient. The sample no longer pulls the policy further in that direction. If instead the ratio has moved the wrong way (\(r<1-\epsilon\) with \(A>0\)), the minimum is \(rA\) and the full gradient remains: PPO corrects bad moves but limits good ones.
At \(\alpha=1\): \(V=\log(e+1)\approx1.313\), and \(\pi=(e/(e+1),1/(e+1))\approx(0.731,0.269)\). At \(\alpha=0.1\): \(V=0.1\log(e^{10}+1)\approx1.000\), and \(\pi\approx(0.99995,0.00005)\). A low temperature gives almost the greedy policy and \(V\approx\max_aQ\).
Each ratio is \(0.9/0.5=1.8\), so the weight is \(1.8^{50}\approx5.8\times10^{12}\). Most episodes, in which the target policy would have chosen differently at some steps, get weights close to zero instead (each such step contributes a factor \(0.1/0.5=0.2\)). The estimate rests on a few astronomically weighted episodes. Per-decision importance sampling weights each reward \(r_{t+1}\) only by the ratios up to time \(t\), since later actions cannot affect it, which reduces the variance; doubly robust estimators reduce it further.
Behaviour cloning becomes nearly perfect: it copies an expert. Offline Q-learning has no examples of the other action at all, so its value comes entirely from the network's extrapolation, and errors there are never corrected. This is the case CQL was designed for: its penalty keeps the unseen action's value below the seen one's, and its policy then stays close to the data. Narrow, expert-only data sets are where conservatism matters most.
Each project uses this lecture's methods and public environments, and has a clear result.
Environments. CartPole-v1 and Pendulum-v1: Gymnasium (Farama Foundation). Connect Four and noughts and crosses are implemented in the lecture. The offline data set is generated in the lecture from a PPO policy mixed with random actions. The offline benchmark is D4RL PointMaze U-maze (dense) from Minari (Farama Foundation), via the Hugging Face Hub, evaluated in Gymnasium-Robotics with MuJoCo. The plan's LunarLander was replaced by CartPole: PPO on LunarLander needs about a million environment steps, beyond this lecture's CPU budget. The AlphaZero-style self-play network for Connect Four was replaced by pure UCT search with random play-outs, to keep the training within minutes on a CPU.
numbers in the text not printed by a code box are computed in verify_L22a.py, figures and widget data in figs_L22a.py; code-box outputs are pasted from actual runs (numpy, Gymnasium and JAX on two CPU cores)