Machine Learning · Lecture 21b

Lecture 21b
Reinforcement Learning II: TD Learning, Q-learning and Deep Q-Networks

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

Cartoon: the weather forecasterTwo stick figures look at a weather forecast for Friday. One says he will wait until Friday to see if the forecast was right. The other says Thursday's forecast already tells her a lot. Friday? I'll wait for Fridayto check the forecast. Thursday's forecastalready tells me a lot.
Monte Carlo waits for the outcome; temporal-difference learning updates a guess from the next guess
In this lecture
  1. Learning values from experience: Monte Carlo and TD
  2. Control: SARSA, Q-learning and Expected SARSA
  3. Function approximation and the deadly triad
  4. Deep Q-networks
  5. Summary, exercises, projects, reading

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.

1 — Learning values from experience: Monte Carlo and TD

To estimate \(v_\pi(s)\) without a model, run the policy and average what happens. The question is what to average towards.

definition 21.6 — Monte Carlo and TD(0) prediction

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.

theorem 21.5 — TD(0) converges (tabular case)

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.)

definition 21.7 — n-step returns and TD(λ)

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.

code — n-step TD on a 19-state random walk
# 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.

code — bias and variance of n-step targets
# 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.

The n-step dial

The distribution of 20,000 n-step targets for one state of the random walk, computed from an estimate that is still poor. Short targets lean on that estimate and are tightly clustered but in the wrong place. Long targets are centred on the truth but spread out.

2 — Control: SARSA, Q-learning and Expected SARSA

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.

definition 21.8 — SARSA, Q-learning and Expected SARSA

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.

theorem 21.6 — convergence of Q-learning and SARSA (tabular)

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.

code — cliff walking: SARSA, Q-learning and Expected SARSA, 50 runs each
# 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.

Cliff-walking race

SARSA (blue) and Q-learning (red) learn side by side with the same ε. Watch each agent's latest episode, or switch to the greedy path it has learned. The curves show returns per episode (thick: this run, smoothed over 10 episodes; faint: the 50-run averages from the code). Set ε to 0 to see the difference vanish.

spot check 21.2

The agent follows ε-greedy with \(\varepsilon=0.1\). Which method's \(Q\)-values account for the 10% of random steps it will take?

Which target uses the action actually taken next?
SARSA's target uses \(Q(S_{t+1},A_{t+1})\) with \(A_{t+1}\) drawn by the ε-greedy policy, so its values include the risk of random slips. That is why it learns the path away from the cliff edge.

3 — Function approximation and the deadly triad

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.

code — Baird's counterexample, with and without each ingredient of the triad
# 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.

01,0002,0003,0004,0005,0001101e21e31e41e51e61e7update steplength of w (log scale)linear + bootstrapping + off-policyon-policyno bootstrappingtabular
Baird's counterexample: the length of the weight vector over 5,000 semi-gradient TD updates (log scale). Only the run with all three ingredients of the deadly triad diverges.

4 — Deep Q-networks

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.

definition 21.9 — DQN with experience replay and a target network

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.

data — MinAtar Breakout

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.

code — DQN on MinAtar Breakout: target network, no target network, double DQN
# 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.

050,000100,000150,0000123456environment stepsmean return (last 50 episodes)DQN (target network)no target networkdouble DQN
Mean return over the last 50 episodes during training on MinAtar Breakout. Thin lines: the two seeds; thick lines: their average. Exploration ε falls from 1 to 0.1 over the first 100,000 steps.
big picture — from Atari to the real world

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.

5 — Summary, exercises, projects, reading

summary
exercises
  1. Show that the Monte Carlo error is a sum of TD errors: if \(V\) does not change during an episode, then \(G_t-V(S_t)=\sum_{k\ge t}\gamma^{k-t}\delta_k\).

    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.

  2. In the λ-return of Definition 21.7, check that the weights sum to 1 and find the weight on the Monte Carlo return when the episode ends after \(T-t\) steps.

    \((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.

  3. Q-learning's target uses \(\max_aQ(s',a)\). If each \(Q(s',a)\) is an unbiased but noisy estimate of the true value, show that the maximum is biased upwards. How does double Q-learning help?

    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).

  4. Why is SARSA's learned path in the cliff task the better one if the agent will keep exploring with \(\varepsilon=0.1\) forever, and Q-learning's the better one if exploration stops after training?

    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.

  5. In Baird's counterexample, the weights could all be zero, which represents the true values exactly. Explain, using the fact that one weight \(w_8\) appears in every state's value, why off-policy updates still push the weights away from zero.

    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.

  6. (Code.) Add prioritised replay to the DQN code: sample transitions with probability proportional to \(|\delta|^{0.6}\) and correct with importance weights. Does it help on MinAtar Breakout within 150,000 steps?

    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.

student projects

Each project uses this lecture's methods and public environments, and has a clear result.

1. How many seeds does a DQN comparison need?

question
Published deep-RL comparisons often use three to five random seeds. How often would such a comparison pick the wrong winner?
data
MinAtar (all five games), with DQN, double DQN and a variant without a target network, 20 or more seeds each.
method
Learning curves; bootstrap confidence intervals for final return; the probability that a random subset of three seeds ranks the methods differently from all 20 (following Henderson et al., 2018, and Agarwal et al., 2021).
outcome
A measured answer and a recommendation for how to report RL results honestly.

2. Traffic lights that learn

question
Can tabular or linear Q-learning time a single intersection's lights better than a fixed cycle, using arrival rates from New York City traffic counts?
data
NYC Department of Transportation automated traffic volume counts (NYC Open Data) to set arrival rates; a small simulator of one intersection written by the students.
method
State: queue lengths (binned) and current phase; actions: keep or switch; reward: minus total waiting time. SARSA, Q-learning and Expected SARSA against fixed-time and actuated controllers.
outcome
Average delay for each controller, robustness to rush-hour versus night-time traffic, and a discussion of what a real deployment would need.

Reading and sources

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)