Part VI · Decisions | Monte Carlo and temporal-difference prediction, n-step returns and TD(λ), SARSA, Q-learning and Expected SARSA, cliff walking, function approximation and the deadly triad, Baird's counterexample, deep Q-networks, experience replay, target networks, double DQN | reading: Sutton & Barto (2018), ch. 5–7, 9–11; Watkins & Dayan (1992); Mnih et al. (2015); van Hasselt, Guez & Silver (2016) | bandits, MDPs and dynamic programming are in Lecture 21a
Lecture 21a solved MDPs whose transition probabilities were known. Usually they are not: a robot does not know the physics of its gripper, a game-playing program does not know its opponent. The agent must learn values from experience, sampled transitions \((S_t,A_t,R_{t+1},S_{t+1})\). This page builds up from estimating the value of a fixed policy to learning an optimal policy, and then to learning with neural networks.
By the end you should be able to compare Monte Carlo and TD estimates in terms of bias and variance; explain n-step returns as a dial between them; contrast SARSA, Q-learning and Expected SARSA and predict their behaviour near a cliff; explain the deadly triad and demonstrate it on Baird's counterexample; and explain what experience replay, target networks and double Q-learning each fix in DQN.
To estimate \(v_\pi(s)\) without a model, run the policy and average what happens. The question is what to average towards.
After visiting \(S_t\), both methods move the estimate a step \(\alpha\) towards a target. Monte Carlo waits until the episode ends and uses the actual return:
$$V(S_t)\leftarrow V(S_t)+\alpha\big[G_t-V(S_t)\big].$$Temporal-difference learning, TD(0) (Sutton, 1988), updates after one step, using its own estimate of the next state in place of the rest of the return:
$$V(S_t)\leftarrow V(S_t)+\alpha\big[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\big].$$The bracket in TD(0) is the TD error \(\delta_t\). Using an estimate inside the target is called bootstrapping.
The Monte Carlo target \(G_t\) is unbiased, since its expectation is exactly \(v_\pi(S_t)\), but it sums many random rewards and so has high variance. The TD target depends on one random step plus an estimate: low variance, but biased whenever the estimate is wrong. In practice TD usually learns faster, and it can learn before an episode ends, or in tasks that never end.
For a finite MDP and a fixed policy \(\pi\), if every state is visited infinitely often and the step sizes satisfy
$$\sum_t\alpha_t=\infty,\qquad\sum_t\alpha_t^2<\infty,$$then tabular TD(0) converges to \(v_\pi\) with probability 1. (Statement; Sutton, 1988; Dayan, 1992; Jaakkola, Jordan and Singh, 1994.)
The n-step return uses \(n\) real rewards and then bootstraps:
$$G_{t:t+n}=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^nV(S_{t+n}).$$\(n=1\) is TD(0); \(n=\infty\) is Monte Carlo. TD(λ) averages all of them, with weights decaying geometrically in \(n\):
$$G_t^\lambda=(1-\lambda)\sum_{n\ge1}\lambda^{n-1}G_{t:t+n}.$$\(\lambda=0\) gives TD(0) and \(\lambda=1\) Monte Carlo. Eligibility traces compute this average online, one step at a time.
# Monte Carlo against temporal-difference learning on a random walk (Sutton and Barto, Examples 6.2 and 7.1) import numpy as np, gymnasium as gym, warnings; warnings.filterwarnings('ignore') NS = 19; true_v = np.arange(-(NS - 1), NS, 2) / (NS + 1) # states 1..19; exit left: reward -1, exit right: +1 def episode(g): s, traj = NS // 2, [] while 0 <= s < NS: s2 = s + (1 if g.random() < 0.5 else -1); r = 1.0 if s2 == NS else (-1.0 if s2 < 0 else 0.0); traj.append((s, r)); s = s2 return traj def nstep_td(n, alpha, episodes, g): """n-step TD prediction with gamma = 1; n = None means Monte Carlo (wait for the whole return).""" V = np.zeros(NS); errs = [] for _ in range(episodes): traj = episode(g); Tn = len(traj) for t in range(Tn): m = Tn - t if n is None else min(n, Tn - t) G = sum(r for _, r in traj[t:t + m]) # sum of the next m rewards if t + m < Tn: G += V[traj[t + m][0]] # ... plus the current estimate of where we land (bootstrapping) V[traj[t][0]] += alpha * (G - V[traj[t][0]]) errs.append(np.sqrt(np.mean((V - true_v) ** 2))) return np.array(errs) g = np.random.default_rng(0); runs = 100 print("RMS error over the 19 states, averaged over the first 10 episodes and 100 runs, at the best step size for each method:") best = {} for n in [1, 2, 4, 8, 16, None]: res_ = {a: np.mean([nstep_td(n, a, 10, g).mean() for _ in range(runs)]) for a in [0.01, 0.02, 0.05, 0.1, 0.2, 0.3, 0.4, 0.6, 0.8, 1.0]} a_best = min(res_, key=res_.get); best[n] = (a_best, res_[a_best]) print(f" {'Monte Carlo' if n is None else f'{n}-step TD':12s} best alpha {a_best:.2f}: RMS error {res_[a_best]:.3f}")
RMS error over the 19 states, averaged over the first 10 episodes and 100 runs, at the best step size for each method: 1-step TD best alpha 0.80: RMS error 0.344 2-step TD best alpha 0.60: RMS error 0.271 4-step TD best alpha 0.40: RMS error 0.258 8-step TD best alpha 0.20: RMS error 0.276 16-step TD best alpha 0.20: RMS error 0.318 Monte Carlo best alpha 0.02: RMS error 0.493
Each method is shown at its own best step size, since a fair comparison must tune it. Monte Carlo is worst (RMS error 0.493, with the tiny step size 0.02 that its noisy targets require). One-step TD is much better (0.344), and an intermediate 4-step TD is best (0.258). After only ten episodes, neither extreme is right: one-step TD spreads information slowly, one state per visit, while Monte Carlo's targets carry the noise of a whole episode.
# The bias-variance dial: n-step targets for one state, from an imperfect value estimate V_hat = np.zeros(NS); g5 = np.random.default_rng(7) # an imperfect estimate: 30 episodes of TD(0) for _ in range(30): for t, (s, r) in enumerate(traj := episode(g5)): nxt = V_hat[traj[t + 1][0]] if t + 1 < len(traj) else 0.0; V_hat[s] += 0.1 * (r + nxt - V_hat[s]) s0 = 14; print(f"state {s0 + 1}: true value {true_v[s0]:.2f}, estimate after 30 episodes of TD(0) {V_hat[s0]:.2f}") def targets_from(s0, n, m, g): out = np.zeros(m) for k in range(m): s, G, steps = s0, 0.0, 0 while 0 <= s < NS and (n is None or steps < n): s2 = s + (1 if g.random() < 0.5 else -1); G += 1.0 if s2 == NS else (-1.0 if s2 < 0 else 0.0); s = s2; steps += 1 out[k] = G + (V_hat[s] if 0 <= s < NS else 0.0) return out gt = np.random.default_rng(11); tg = {} print("n bias of the target variance mean squared error") for n in [1, 2, 4, 8, 16, 32, None]: x = targets_from(s0, n, 20_000, gt); tg[n] = x; b = x.mean() - true_v[s0] print(f"{'MC' if n is None else n!s:8s} {b:+.3f} {x.var():.3f} {b * b + x.var():.3f}")
state 15: true value 0.50, estimate after 30 episodes of TD(0) 0.07 n bias of the target variance mean squared error 1 -0.431 0.001 0.186 2 -0.417 0.003 0.177 4 -0.385 0.022 0.170 8 -0.321 0.075 0.178 16 -0.218 0.155 0.202 32 -0.096 0.237 0.246 MC -0.010 0.760 0.760
The estimate of state 15 is still poor (0.07 against a true value of 0.50), so short targets inherit its error. The one-step target is almost deterministic (variance 0.001) but biased by -0.431. The Monte Carlo target is unbiased (-0.010) but has variance 0.760. In between, bias shrinks and variance grows steadily with \(n\), and the mean squared error, bias squared plus variance, is smallest at \(n=4\) (0.170). This is the bias–variance trade-off of Lecture 5, with \(n\) (or \(\lambda\)) as the dial. As the estimate improves, the bias of short targets would fall and the best \(n\) would move down.
To improve a policy without a model, learn action values \(Q(s,a)\) rather than state values: then acting greedily needs no model, only \(\arg\max_aQ(s,a)\). The agent must keep exploring, usually with ε-greedy actions, and the three classic methods differ in what they assume about the next action.
After a transition \((S_t,A_t,R_{t+1},S_{t+1})\), each method updates
$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha\big[\,\text{target}-Q(S_t,A_t)\big],$$with the target:
SARSA is on-policy: it learns the value of the policy it follows, exploration included. Q-learning is off-policy: it learns the value of the greedy policy while following an exploratory one. Expected SARSA removes the randomness of the next action from the target, which lowers its variance.
In a finite MDP with step sizes as in Theorem 21.5:
(Statements.)
With a fixed ε, the two methods learn different things, and the cliff-walking task of Sutton and Barto (Example 6.6) shows it. The agent walks from the bottom-left corner of a 4 × 12 grid to the bottom-right. Each step costs 1; the cells between start and goal along the bottom are a cliff, and stepping into it costs 100 and sends the agent back to the start.
# Cliff walking (Sutton and Barto, Example 6.6): SARSA, Q-learning and Expected SARSA with epsilon-greedy exploration env = gym.make('CliffWalking-v1'); nS, nA = 48, 4 # 4 x 12 grid; stepping into the cliff costs -100 and sends you back to the start def run(method, episodes=500, eps=0.1, alpha=0.5, seed=0): g = np.random.default_rng(seed); Q = np.zeros((nS, nA)); rets = [] pol = lambda s: g.integers(nA) if g.random() < eps else int(g.choice(np.flatnonzero(Q[s] == Q[s].max()))) for ep in range(episodes): s, _ = env.reset(seed=int(g.integers(1 << 30))); a = pol(s); G, done = 0, False while not done: s2, r, term, trunc, _ = env.step(a); done = term or trunc; G += r; a2 = pol(s2) if method == 'sarsa': nxt = Q[s2, a2] # the action actually taken next (on-policy) elif method == 'q': nxt = Q[s2].max() # the best action, whatever is taken (off-policy) else: pi = np.full(nA, eps / nA); pi[np.flatnonzero(Q[s2] == Q[s2].max())] += (1 - eps) / np.sum(Q[s2] == Q[s2].max()); nxt = pi @ Q[s2] Q[s, a] += alpha * (r + (0 if term else nxt) - Q[s, a]); s, a = s2, a2 rets.append(G) return np.array(rets), Q def greedy_path(Q): s, _ = env.reset(seed=0); path = [s]; done = False while not done and len(path) < 100: s, r, term, trunc, _ = env.step(int(Q[s].argmax())); path.append(s); done = term or trunc return path cliff = {} for m, label in [('sarsa', 'SARSA'), ('q', 'Q-learning'), ('expected', 'Expected SARSA')]: out = [run(m, seed=k) for k in range(50)]; R = np.array([o[0] for o in out]); Qm = np.mean([o[1] for o in out], 0); path = greedy_path(Qm) cliff[m] = {'curve': R.mean(0), 'path': path} print(f"{label:15s} mean return per episode while learning (episodes 101-500, 50 runs): {R[:, 100:].mean():7.1f}; " f"falls into the cliff in {np.mean(R[:, 100:] < -100):.1%} of those episodes;\n{'':16s}greedy path of the run-averaged Q: {len(path) - 1} steps, " f"most of it {3 - int(np.median([p // 12 for p in path[1:-1]]))} row(s) above the cliff")
SARSA mean return per episode while learning (episodes 101-500, 50 runs): -27.5; falls into the cliff in 5.1% of those episodes;
greedy path of the run-averaged Q: 17 steps, most of it 3 row(s) above the cliff
Q-learning mean return per episode while learning (episodes 101-500, 50 runs): -49.7; falls into the cliff in 24.7% of those episodes;
greedy path of the run-averaged Q: 13 steps, most of it 1 row(s) above the cliff
Expected SARSA mean return per episode while learning (episodes 101-500, 50 runs): -21.1; falls into the cliff in 3.7% of those episodes;
greedy path of the run-averaged Q: 15 steps, most of it 2 row(s) above the cliff
The classic result appears. Q-learning learns the shortest path, 13 steps along the edge of the cliff, because it values the greedy policy. But the agent still explores, and on that path a random step falls in: it falls in 24.7% of episodes and earns -49.7 per episode while learning. SARSA values the exploring policy it actually follows, so it learns a longer path (17 steps, 3 rows above the cliff), falls in only 5.1% of episodes and earns -27.5. Expected SARSA, with its lower-variance target, does best of all (-21.1), on a path 2 rows from the edge. Neither SARSA nor Q-learning is wrong: they answer different questions.
The agent follows ε-greedy with \(\varepsilon=0.1\). Which method's \(Q\)-values account for the 10% of random steps it will take?
Tables do not scale: Atari screens, board positions and robot joint angles have far too many states to list. Instead, approximate \(v(s)\approx\hat v(s;\mathbf w)\) with a parametric function, linear in features \(\hat v(s;\mathbf w)=\mathbf x(s)^\top\mathbf w\) or a neural network. The semi-gradient TD update treats the target as a constant:
$$\mathbf w\leftarrow\mathbf w+\alpha\,\big[R_{t+1}+\gamma\hat v(S_{t+1};\mathbf w)-\hat v(S_t;\mathbf w)\big]\,\nabla_{\mathbf w}\hat v(S_t;\mathbf w).$$It is not the gradient of any fixed loss, because the target moves with \(\mathbf w\). On-policy with linear features it still converges (Tsitsiklis and Van Roy, 1997). But Sutton and Barto identify three ingredients that together can make it diverge, the deadly triad:
Baird (1995) gave a seven-state example where all three meet. Every reward is zero, so the true value of every state is 0 and the weights could simply go to zero; yet off-policy semi-gradient TD drives them to infinity.
# The deadly triad: Baird's counterexample (Sutton and Barto, Example 11.1) X = np.zeros((7, 8)) # linear features: v(s) = X[s] @ w for i in range(6): X[i, i], X[i, 7] = 2, 1 # six upper states: 2 w_i + w_8 X[6, 6], X[6, 7] = 1, 2 # lower state: w_7 + 2 w_8 def baird(steps=1000, alpha=0.01, gamma=0.99, offpolicy=True, bootstrap=True, feats=X, seed=0): g = np.random.default_rng(seed); w = np.ones(feats.shape[1]); w[6 if feats.shape[1] == 8 else 0] = 10; s = g.integers(7); norms = [] for t in range(steps): dashed = offpolicy and g.random() < 6 / 7 # behaviour: dashed (to a random upper state) 6/7 of the time s2 = g.integers(6) if dashed else 6 # target policy: always solid (to the lower state) rho = 0.0 if dashed else (7.0 if offpolicy else 1.0) # importance ratio pi / b target = gamma * feats[s2] @ w if bootstrap else 0.0 # all rewards are zero, so the true value of every state is 0 w += alpha * rho * (target - feats[s] @ w) * feats[s] # semi-gradient TD(0) s = s2; norms.append(np.linalg.norm(w)) return np.array(norms) print(f"length of the weight vector after 1,000 / 5,000 steps (it starts at {np.sqrt(6 + 100 + 1):.1f}; the true values are all 0):") cases = {'all three: linear features, bootstrapping, off-policy': {}, 'on-policy (follow the target policy)': {'offpolicy': False}, 'no bootstrapping (Monte Carlo target)': {'bootstrap': False}, 'tabular features (one weight per state)': {'feats': np.eye(7)}} baird_norms = {} for label, kw in cases.items(): nrm = baird(5000, **kw); baird_norms[label] = nrm print(f" {label:52s} {nrm[999]:12.4g} {nrm[-1]:12.4g}")
length of the weight vector after 1,000 / 5,000 steps (it starts at 10.3; the true values are all 0): all three: linear features, bootstrapping, off-policy 416.3 4.59e+06 on-policy (follow the target policy) 9.425 8.838 no bootstrapping (Monte Carlo target) 8.631 8.629 tabular features (one weight per state) 4.687 2.477
With all three ingredients, the length of the weight vector grows from 10.3 to 416 after 1,000 updates and about \(4.6\times10^{6}\) after 5,000, although every true value is zero. Remove any one ingredient and it stays bounded: following the target policy (8.8 after 5,000 updates), using the Monte Carlo target (8.6) or giving each state its own weight (2.5). The on-policy and Monte Carlo runs do not reach zero, because some weights are never corrected, but they do not diverge. The failure comes from the combination, not from any one ingredient.
A deep Q-network (DQN; Mnih et al., 2015) is Q-learning with a convolutional neural network for \(Q(s,a;\mathbf w)\). It has all three ingredients of the deadly triad, and early attempts were unstable. Two changes made it work, and a third made it better.
Store each transition \((s,a,r,s')\) in a replay buffer and train on random minibatches from it, which breaks the strong correlation between consecutive steps and reuses each experience many times. Compute targets with a target network, a copy \(\mathbf w^-\) of the weights refreshed only every \(C\) steps, and minimise
$$L(\mathbf w)=\mathbb E_{(s,a,r,s')\sim\text{buffer}}\Big[\ell\big(r+\gamma\max_{a'}Q(s',a';\mathbf w^-)-Q(s,a;\mathbf w)\big)\Big],$$with \(\ell\) the squared or Huber loss. Between refreshes the target stays still, so each phase is an ordinary regression problem.
Double DQN (van Hasselt, Guez and Silver, 2016) lets the online network choose the next action and the target network evaluate it, \(r+\gamma\,Q\big(s',\arg\max_{a'}Q(s',a';\mathbf w);\mathbf w^-\big)\). This reduces the upward bias that the maximum of noisy estimates introduces.
The Atari games of the original DQN paper need days of GPU time. MinAtar (Young and Tian, 2019) reproduces five of them on a 10 × 10 grid with a few binary channels (here: paddle, ball, trail and bricks), so that DQN experiments run on a laptop CPU. In Breakout the agent moves a paddle left or right (or stays) to bounce a ball into a wall of bricks, scoring 1 per brick; the episode ends when the ball is missed. We use the minatar package (PyPI) with its default sticky actions (10% of the time the previous action repeats) and the network of Young and Tian: one 3 × 3 convolution with 16 channels and a hidden layer of 128 units. The plan's Atari-scale experiment is replaced by this CPU-sized one.
# Deep Q-network on MinAtar Breakout (10 x 10 x 4 frames, 3 actions): with a target network, without one, and double DQN import jax, jax.numpy as jnp, time from minatar import Environment def qinit(key): k1, k2, k3 = jax.random.split(key, 3) return {'c': jax.random.normal(k1, (3, 3, 4, 16)) * np.sqrt(2 / 36), 'cb': jnp.zeros(16), 'w1': jax.random.normal(k2, (1024, 128)) * np.sqrt(2 / 1024), 'b1': jnp.zeros(128), 'w2': jax.random.normal(k3, (128, 3)) * np.sqrt(1 / 128), 'b2': jnp.zeros(3)} def qnet(p, s): # conv 3x3x16 -> dense 128 -> one Q-value per action h = jax.nn.relu(jax.lax.conv_general_dilated(s, p['c'], (1, 1), 'VALID', dimension_numbers=('NHWC', 'HWIO', 'NHWC')) + p['cb']) return jax.nn.relu(h.reshape(len(s), -1) @ p['w1'] + p['b1']) @ p['w2'] + p['b2'] huber = lambda x: jnp.where(jnp.abs(x) < 1, 0.5 * x * x, jnp.abs(x) - 0.5) def make_update(double): @jax.jit def update(p, pt, m, v, t, s, a, r, s2, d): def loss(p): if double: a2 = qnet(p, s2).argmax(1); nxt = qnet(pt, s2)[jnp.arange(len(a)), a2] # online net picks, target net evaluates else: nxt = qnet(pt, s2).max(1) tgt = jax.lax.stop_gradient(r + 0.99 * (1 - d) * nxt) return jnp.mean(huber(qnet(p, s)[jnp.arange(len(a)), a] - tgt)) L, g = jax.value_and_grad(loss)(p) 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 - 2.5e-4 * (m / (1 - 0.9 ** t)) / (jnp.sqrt(v / (1 - 0.999 ** t)) + 1e-8), p, m, v), m, v, L return update qact = jax.jit(qnet) def dqn(seed, steps, target_every, double=False, buf=100_000, B=32, start=5_000): env = Environment('breakout'); env.seed(seed); acts = env.minimal_action_set(); g = np.random.default_rng(seed) p = qinit(jax.random.PRNGKey(seed)); pt = p; m = jax.tree.map(jnp.zeros_like, p); v = jax.tree.map(jnp.zeros_like, p) S = np.zeros((buf, 10, 10, 4), np.float32); S2 = np.zeros_like(S); A = np.zeros(buf, np.int32); R = np.zeros(buf, np.float32); D = np.zeros(buf, np.float32) upd = make_update(double); env.reset(); s = env.state().astype(np.float32); ep, rets, curve, k = 0.0, [], [], 0 for t in range(1, steps + 1): eps = max(0.1, 1 - 0.9 * t / 100_000) # explore: epsilon from 1 down to 0.1 over 100,000 steps a = g.integers(3) if g.random() < eps else int(np.asarray(qact(p, s[None])).argmax()) r, done = env.act(acts[a]); s2 = env.state().astype(np.float32); i = k % buf S[i], A[i], R[i], S2[i], D[i] = s, a, r, s2, float(done); k += 1; ep += r; s = s2 if done: rets.append(ep); ep = 0.0; env.reset(); s = env.state().astype(np.float32) if t > start: # experience replay: learn from a random minibatch of the past b = g.integers(0, min(k, buf), B); p, m, v, L = upd(p, pt if target_every else p, m, v, t - start, S[b], A[b], R[b], S2[b], D[b]) if target_every and t % target_every == 0: pt = p # target network: a frozen copy, refreshed every 1,000 steps if t % 10_000 == 0: curve.append(float(np.mean(rets[-50:])) if rets else 0.0) return np.array(curve) t0 = time.time(); runs = {} for label, te, dbl in [('DQN (target network)', 1000, False), ('no target network', 0, False), ('double DQN', 1000, True)]: runs[label] = np.array([dqn(seed, 150_000, te, dbl) for seed in (1, 2)]) c = runs[label]; print(f"{label:22s} mean return over the last 50 episodes at 50k / 100k / 150k steps: " + " / ".join(f"{c[:, k].mean():.1f}" for k in (4, 9, 14)) + f" (seeds: {', '.join(f'{x:.1f}' for x in c[:, -1])})") def random_return(n_ep=200): env = Environment('breakout'); env.seed(0); g = np.random.default_rng(0); acts = env.minimal_action_set(); out = [] for _ in range(n_ep): env.reset(); tot, done = 0.0, False while not done: r, done = env.act(acts[g.integers(3)]); tot += r out.append(tot) return np.mean(out) print(f"random policy: mean return {random_return():.2f} over 200 episodes") print(f"training time {time.time() - t0:.0f} s for 6 runs of 150,000 steps")
DQN (target network) mean return over the last 50 episodes at 50k / 100k / 150k steps: 1.2 / 3.9 / 4.6 (seeds: 5.0, 4.2) no target network mean return over the last 50 episodes at 50k / 100k / 150k steps: 1.1 / 3.5 / 4.6 (seeds: 4.9, 4.2) double DQN mean return over the last 50 episodes at 50k / 100k / 150k steps: 1.1 / 3.9 / 4.2 (seeds: 4.7, 3.7) random policy: mean return 0.46 over 200 episodes training time 1683 s for 6 runs of 150,000 steps
All three agents learn: a random policy scores 0.46 per episode, while after 150,000 steps DQN with a target network scores 4.6 (seeds 5.0 and 4.2), double DQN 4.2 (seeds 4.7 and 3.7) and DQN without a target network 4.6 (seeds 4.9 and 4.2). At this budget the three are indistinguishable: their differences are no larger than the gap between two seeds of the same method. The problems that the target network and double Q-learning address build up over long training (targets chasing their own updates, overestimates feeding on themselves), and 150,000 steps may be too short for them to matter here. Two seeds per method and 28 minutes of CPU training are far below what a reliable comparison needs (Exercise 6 and the first project), so these numbers show what the methods do on this budget, not which is best in general.
DQN was the first agent to learn many different games from pixels with one architecture, and its ingredients (replay, target networks, double Q-learning, later prioritised replay and distributional value estimates) remain standard. Deep RL more broadly has since been used to cool data centres, to lay out computer chips and to shape the plasma in a fusion reactor (Degrave et al., Nature, 2022), and recommendation systems use it to optimise long-term rather than immediate engagement. Its limits are equally clear: it needs huge amounts of experience, it is sensitive to hyperparameters and random seeds, and it handles continuous actions poorly. Lecture 22 turns to policy-gradient methods, which address the last of these, and to RL for language models.
Write \(G_t-V(S_t)=R_{t+1}+\gamma G_{t+1}-V(S_t)=\delta_t+\gamma\big(G_{t+1}-V(S_{t+1})\big)\), where \(\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)\). Repeat until the end of the episode, where \(G_T-V(S_T)=0\). Monte Carlo therefore makes the sum of all future TD corrections at once; TD makes them one at a time, as they arrive.
\((1-\lambda)\sum_{n\ge1}\lambda^{n-1}=1\). If the episode ends at \(T\), every \(G_{t:t+n}\) with \(n\ge T-t\) equals \(G_t\), so these terms merge, with total weight \((1-\lambda)\sum_{n\ge T-t}\lambda^{n-1}=\lambda^{T-t-1}\). With \(\lambda=1\) all the weight is on the full return: Monte Carlo.
For random variables \(X_a\) with means \(\mu_a\), \(\mathbb E[\max_aX_a]\ge\max_a\mathbb E[X_a]\) (Jensen's inequality, since the maximum is convex). With several actions of equal true value and independent noise, the maximum picks whichever happened to be overestimated.
Double Q-learning keeps two estimates: one picks \(a^*=\arg\max_aQ_1(s',a)\), the other evaluates it, \(Q_2(s',a^*)\). If the noise in \(Q_2\) is independent of the choice, \(\mathbb E[Q_2(s',a^*)]=\mathbb E[q(s',a^*)]\le\max_aq(s',a)\): the upward bias is removed (at the cost of a possible small downward bias).
Along the cliff edge, each step has probability about \(\varepsilon/4\) of a random move downwards, costing 100. Over about a dozen steps that is a large expected loss, so for an agent that keeps exploring the longer, safer route is better, and SARSA, which evaluates the exploring policy, finds it. Q-learning evaluates the greedy policy, for which the edge is safe and shortest; once exploration stops, its path is optimal.
Under the behaviour policy, the updates come from transitions into the lower state (the only ones with non-zero importance weight). Their targets bootstrap from the lower state's value \(w_7+2w_8\), discounted only slightly. Raising \(w_8\) to fit one state raises every other state's value too, and the off-policy weighting never applies the updates that would pull the upper states back down in the right proportion. Each update overshoots in a direction that increases the next target: the expected update matrix has an eigenvalue with positive real part, so the weights grow exponentially. Any one of on-policy weighting, Monte Carlo targets or separate features per state breaks this loop.
Keep an array of priorities alongside the buffer, set new transitions to the current maximum, sample indices with g.choice(k, B, p=prio / prio.sum()), update the priorities of the sampled transitions with their new \(|\delta|\), and multiply each loss term by \((N\,P(i))^{-\beta}\), normalised by its maximum. Schaul et al. (2016) found large gains on Atari; on a small, quickly learned game the effect is smaller, and with two seeds per variant differences of a few points are within the seed-to-seed spread. Run at least five seeds before drawing conclusions.
Each project uses this lecture's methods and public environments, and has a clear result.
Environments. CliffWalking: Gymnasium (Farama Foundation), CliffWalking-v1. MinAtar Breakout: the minatar package (PyPI), K. Young and T. Tian (2019). The random walk and Baird's counterexample are simulated as in Sutton and Barto (2018).
numbers in the text not printed by a code box are computed in verify_L21b.py, figures and widget data in figs_L21b.py; code-box outputs are pasted from actual runs (numpy, Gymnasium, MinAtar and JAX on two CPU cores)