An agent can learn what each state is worth without knowing the rules

The test problem is a grid whose exact values are known

Both methods are tested on a problem small enough to solve exactly, so every estimate can be graded against the right answer.

An agent moves around a 4×4 grid whose cells are numbered 0 to 15, row by row from the top left. Arriving at cell 3, the goal, pays +10. Arriving at cell 6, the pit, pays −20. Any other move pays −1. Reaching the goal or the pit ends the episode, which is one walk from a starting cell to an ending cell.

Moves are slippery. A move goes where it is aimed with probability 0.8 and to each side with probability 0.1. A move into an edge leaves the agent where it is.

The arrows in Fig. 1 are a policy, a fixed choice of move for each cell. The policy does not change in anything below. The question is how good each cell is if the agent follows these arrows. Finding better arrows comes later.

How good a cell is depends on the rewards that follow it. The return from any point in an episode adds them up, with each later reward multiplied by one more factor of \gamma = 0.9, so a reward counts for less the further away it is. Splitting off the first reward gives a recursion that both methods rely on.¹

The value of a cell is its average return over all the episodes the policy could produce from there: v_\pi(s) = \mathbb{E}_\pi[\,G_t \mid S_t = s\,].¹ The exact value of cell 13 is −2.01, and that average combines two very different outcomes. About 80% of episodes from cell 13 reach the goal, with an average return of +1.67. The other 20% fall in the pit, with an average return of −16.78.

The numbers in Fig. 1 come from solving one linear equation per cell, which requires the move probabilities and the rewards. The first lesson derives that solve. Here it only supplies the answer key used to grade the estimates.

The agent sees only episodes

The agent in this lesson does not know the move probabilities or the rewards. It can only play episodes and read what each one reports: a list of steps, each holding the cell, the move, the reward and the next cell. One step might read (13, up, −1, 9).

Estimating the value of every cell from such lists, for a fixed policy, is called prediction.¹ Write V(s) for the agent's current estimate for cell s, and v_\pi(s) for the exact value it is trying to reach.

Both methods keep one number V(s) per cell and change it with the same line.¹

The two methods differ only in what they use as the target.

Monte Carlo waits for the episode to end and uses the actual return

Monte Carlo methods estimate a quantity by averaging random samples. Here the quantity is a cell's value, which by definition is an average return, so the target is the return that actually followed the cell.¹

Take one real episode from cell 13. It visits cells 13, 9, 5, 4, 0, 1 and 2, then reaches the goal. The first six moves pay −1 and the last pays +10. The recursion computes each cell's return by working backward from the end. Cell 2's return is 10. Cell 1's is -1 + 0.9 \times 10 = 8. Cell 0's is -1 + 0.9 \times 8 = 6.2. Continuing back, cell 13's return is 0.63.

That 0.63 is above the exact −2.01, because the average also includes the episodes that fall in the pit. The estimate improves by averaging many returns, and the average does not need a stored list. If V_{n-1} is the mean of the first n-1 returns and G_n is the next return, then:

So averaging is the shared update with step size \alpha = 1/N(s), where N(s) counts the returns averaged into cell s so far. The first step size is 1, so the first return replaces the starting estimate completely.

First visits and every visit

A slip can send the agent back to a cell it already left, and 33% of episodes from random starting cells repeat at least one cell. So Monte Carlo comes in two versions. First-visit uses only the return after a cell's first appearance in each episode. Every-visit uses the return after every appearance.¹

Each first-visit return has mean v_\pi(s), so their average is unbiased: repeated from scratch many times, it averages to the exact value for any number of returns. Returns from different episodes are also independent, so the standard deviation falls as 1/\sqrt{n} for n returns.¹ Every-visit divides by a visit count that depends on how the episode went, which biases its average when there are few episodes, although it also converges.² On this grid the two versions stay close: after 6,000 episodes their errors across the grid differ by less than 0.01. Everything below uses first-visit Monte Carlo.

What Monte Carlo costs

Monte Carlo has two costs. It cannot update a cell until the episode ends, because the return is not known until the last reward arrives.¹ And each return contains the randomness of every move through to the end of the episode. Returns from cell 13 run from −18.10 to +3.12. Averaging reduces that noise slowly, since cutting the error in half takes four times as many returns.

TD updates after one move, using its own estimate of the next cell

Temporal-difference learning does not wait for the end of the episode. It starts from a property of values: a cell's value equals the average of the next reward plus the discounted value of the next cell.¹ The first lesson derives this from the return's recursion.

TD turns this property into a target. After one move the agent has a real reward and a real next cell, and it already holds an estimate for the next cell.¹

Suppose the agent is in cell 13 and V(13) = -3.00. It moves up to cell 9 and receives −1. Its estimate for cell 9 is V(9) = -1.00. The target is -1 + 0.9 \times (-1.00) = -1.90. With a step size of 0.1, the new estimate is -3.00 + 0.1 \times (-1.90 + 3.00) = -2.89. All of this happens one move after leaving cell 13, while the rest of the episode is still unknown.

The bracket in the update is called the TD error.¹

In the example it is +1.10, which means the move went 1.10 better than the old estimate predicted. A positive TD error raises the estimate and a negative one lowers it.

Using an existing estimate inside a target is called bootstrapping. TD's target is an approximation in two ways: it samples one next cell instead of averaging over all of them, and it uses V where the exact property has v_\pi.¹ Because it updates after every move, TD can also learn on very long episodes and on tasks that never end, where a return would never be finished.¹

Fig. 2 runs both methods on the episode from the last section, with every estimate starting at 0 and a step size of 1.

Monte Carlo gives all seven cells information from the goal at once, because each cell's return includes the +10. TD gives it to cell 2 only. Every other cell updates while its next cell's estimate is still 0, so it ends at −1. Playing the same episode again carries the +10 back one more cell, to cell 1. Under TD, information moves back through the estimates about one cell per pass.

The TD errors add up to Monte Carlo's correction

If V stays fixed during an episode, Monte Carlo's whole correction for a cell equals the discounted sum of the TD errors along the rest of the episode.¹ Adding and subtracting \gamma V(S_{t+1}) shows why.

Monte Carlo moves V(S_t) using the whole sum at the end of the episode. TD(0) moves V(S_t) using only the first term, \delta_t. The later terms update later cells, and they reach S_t only on later passes, through the next cell's estimate. In Fig. 2, the whole sum for cell 13 is 0.63 and its first term is −1.¹

The updates in code

estimators.py holds the three updates. It imports nothing from the environment, so it cannot read the grid's rules. td0 receives a finished list so that every method can be compared on the same episodes, but it reads one step at a time and could run during the episode with the same result.

# /// script
# requires-python = ">=3.10"
# dependencies = []
# ///
"""Estimate state values from episodes.

An episode is a list of (cell, action, reward, next cell). That list is the only
thing these functions see. They import nothing from the environment.
"""

GAMMA = 0.9


def first_visit_mc(steps, V, count, step=None):
    """Move each cell toward the return that followed its first visit."""
    returns, G = {}, 0.0
    for cell, _, reward, _ in reversed(steps):
        G = reward + GAMMA * G
        returns[cell] = G  # walking backward, the last write is the first visit
    for cell, G in returns.items():
        count[cell] += 1
        V[cell] += (step or 1 / count[cell]) * (G - V[cell])


def every_visit_mc(steps, V, count):
    """Move each cell toward the return after every visit."""
    G = 0.0
    for cell, _, reward, _ in reversed(steps):
        G = reward + GAMMA * G
        count[cell] += 1
        V[cell] += (G - V[cell]) / count[cell]


def td0(steps, V, count, step=None, decay=0.7):
    """After each move, move the cell toward reward + GAMMA * V[next cell]."""
    for cell, _, reward, next_cell in steps:
        count[cell] += 1
        target = reward + GAMMA * V[next_cell]
        V[cell] += (step or count[cell] ** -decay) * (target - V[cell])

TD's target has less noise and inherits errors from other estimates

Fig. 3 shows every value one target from cell 13 can take.

The top two rows have the same mean and very different spreads. A Monte Carlo return from cell 13 has a standard deviation of 7.57. TD's target, with exact estimates, has a standard deviation of 0.22, about 34 times smaller. TD replaces everything after the next move, including whether the agent ends up in the pit, with one number. Sutton made this argument in 1988, in the paper that introduced TD methods: the next state's estimate is free of the random events that later affect the final outcome, and dropping those events drops their noise.³

TD cannot remove randomness in the next move itself. In the four cells next to the pit, cells 2, 5, 7 and 10, the next move can pay −20. There, TD's target has a standard deviation of 6.75 to 8.96, against 9.35 to 10.00 for the return. In the other ten cells it is at most 1.83, against 5.89 to 8.66 for the return.

The bottom row shows the cost of using an estimate. With every estimate at 0, the target from cell 13 is always −1, which has no spread and sits 1.01 from the exact value. Monte Carlo's target contains no estimate, so it cannot have this error.¹ TD's estimate for one cell inherits the errors in other cells' estimates, both their bias and their noise, until those are corrected.

At cell 13, Monte Carlo is centered and TD is steadier

A training run starts every estimate at 0, plays episodes from random non-terminal cells, and feeds the same episodes to both methods. Monte Carlo uses \alpha = 1/N(s). TD uses \alpha = N(s)^{-0.7}, where N(s) counts that cell's updates so far. TD's results depend on this schedule, and a later section compares others.

Two standard conditions on the step sizes guarantee that the estimates settle on the exact values with probability 1. Their sum must be infinite, so the estimates can always move as far as they need to. The sum of their squares must be finite, so the steps eventually become small enough to stop the estimates moving.¹ N(s)^{-0.7} meets both. Fig. 4 tracks V(13) across 1,000 independent training runs.

Monte Carlo's mean stays near the exact value, at −1.89 after 50 episodes and −2.07 after 100. After 10 episodes, 39% of training runs have not reached cell 13 and still hold the starting 0, which pulls both methods' means toward 0.

TD's mean then moves past the exact value. It reaches −2.79 at 50 episodes, about 0.8 below, and climbs back to −2.03 by 1,000 episodes. The difference between the mean and the exact value is the bias.

At this cell TD is also steadier. At 100 episodes the estimate's standard deviation across training runs is 2.69 for Monte Carlo and 1.39 for TD. At 1,000 episodes it is 0.79 and 0.36. That is about half of Monte Carlo's spread. One target in Fig. 3 was 34 times narrower, but only with exact estimates. During training, most of the noise at cell 13 comes from the four cells next to the pit and reaches it through the estimates in between. Giving those four cells true averages in place of sampled targets cuts TD's standard deviation at cell 13 from 1.39 to 0.37 at 100 episodes and leaves its mean at −2.59.

Squared error equals the bias squared plus the variance, so a biased estimate can still be the better one. At 100 episodes, TD's squared error at cell 13 is 0.58^2 + 1.39^2 = 2.27, and Monte Carlo's is 0.06^2 + 2.69^2 = 7.24. At this cell TD has the lower squared error at every checkpoint in Fig. 4.

TD dips because the goal's reward arrives late

TD's estimates learn about nearby rewards before distant ones. An exact calculation shows this without sampling noise. A sweep applies the TD update to every cell at once, with a step of 1 and true averages in place of samples.¹ After k sweeps from 0, an estimate holds the expected discounted reward of the next k moves and nothing beyond them.

Cell 13 reads −1.00, −1.90, −3.94, −4.61, −3.03, −2.88 and −2.37 over the first seven sweeps, and −2.01 by sweep 12. The first two sweeps hold only step costs. Sweep 3 brings in the pit, three moves from cell 13. Sweep 5 brings in the goal, five moves away.

So after k sweeps from 0, an estimate's error is the expected reward still to arrive, with the sign reversed. TD behaves the same way with samples, and more slowly, because each update moves only part of the way to its target and a cell updates only when an episode passes through it. Rewards do not change which moves happen, and each update is linear in the rewards, so on the same episodes the error splits exactly into one part per kind of reward.

Step costs and the pit that have not arrived yet leave the estimate too high. A goal that has not arrived yet leaves it too low. The goal's part of the error is the largest and it shrinks the most slowly, because the goal is the furthest away. From 10 to 50 episodes it shrinks by 40%, against 61% for the pit and 67% for the step costs. That is why the error turns from positive to negative.

Running each update backward through the episode carries the +10 all the way back in one pass, and the dip disappears. The cost is spread: the standard deviation at 50 episodes rises from 1.93 to 2.77, so the squared error rises too. Starting from the exact values removes most of the bias.

On the whole grid, the leader depends on TD's step size

Fig. 5 compares the methods across all 14 non-terminal cells, using root-mean-square (RMS) error averaged over 100 training runs of 6,000 episodes. Each line is TD's error divided by Monte Carlo's.

TD starts ahead under all four schedules. What happens next depends on how fast its step shrinks. The step has to stay large enough for the estimates to keep up as their targets improve, and it has to shrink enough to average away noise.

N(s)^{-0.5} stays too large. It fails the second condition, because its squares are 1/N and the sum of 1/N is infinite. Its error still falls, slowly, and at 6,000 episodes it is almost all spread across training runs, with a standard deviation of 0.605 and a bias below 0.05.

N(s)^{-1} shrinks too fast. It meets both conditions, which guarantee that the estimates settle eventually and say nothing about how soon. It makes each estimate the plain average of all its targets so far, and the earliest targets, built on poor estimates, keep their full weight. Those targets are noisy as well as biased, and at 6,000 episodes it has a standard deviation of 0.530 and a bias of about 0.2, the largest of the four. Using N(s)^{-0.7} for the first 1,000 episodes and N(s)^{-1} after that cuts its error at 6,000 episodes from 0.493 to 0.297.

Monte Carlo can use exactly that step because a return contains no estimate. Its first return is as good a sample as its thousandth, so equal weights are right.

N(s)^{-0.7} and N(s)^{-0.85} sit between those extremes. Late in training both have almost no bias, so the difference between them is noise. N(s)^{-0.7} keeps larger steps and has a standard deviation of 0.284 at 6,000 episodes, so Monte Carlo passes it between 2,000 and 4,000 episodes. N(s)^{-0.85} has 0.211, so TD stays ahead at all ten checkpoints and ends with an RMS error of 0.204 against Monte Carlo's 0.257.

The errors also differ by cell. At 6,000 episodes under N(s)^{-0.7}, TD's four largest errors are at the four cells next to the pit. They are 0.47 at cells 7 and 10, 0.37 at cell 5 and 0.34 at cell 2. Monte Carlo does better in those cells even though its return is noisier than TD's target there, because under this schedule its step is smaller. At cell 2 after 6,000 episodes, Monte Carlo's step is 0.0003 and TD's is 0.003. TD does better in the lower left, with 0.17 against 0.34 at cell 13 and 0.12 against 0.30 at cell 12. TD's steadiness at cell 13 does not hold everywhere: at 1,000 episodes TD has the larger standard deviation at cells 1, 2, 5, 7, 10 and 11.

None of this settles which method is faster in general. Sutton and Barto call that an open question, because no one has proved that either method converges faster. In practice, they report, TD has usually converged faster than Monte Carlo with a constant step size on stochastic tasks.¹

A constant step never settles

A constant step fails the second condition too, and it does worse, because its error stops falling. With a step of 0.05, Monte Carlo levels off at an RMS error of about 1.3 to 1.4 and TD near 0.9, because each new target keeps moving the estimate by 5% of the gap, however long training runs.¹ A constant step does keep tracking a problem that changes over time, which a shrinking step stops doing.¹

What each method learned

Fig. 6 shows the estimates in one typical training run, the one with the median Monte Carlo error at 1,000 episodes. After 100 episodes both methods have the broad shape of Fig. 1, high near the goal and low along the bottom row. One run is noisy: over the three checkpoints, cell 13 reads −4.7, −2.5 and −2.5 under Monte Carlo and −2.1, −2.8 and −2.0 under TD. TD's largest remaining errors in this run at 6,000 episodes are at cells 5 and 10, next to the pit.

The experiment in code

compare.py produces every number measured on this page. It imports estimators.py from above and gridworld.py, which is printed in full in the first lesson. With the three files in one folder, uv run compare.py installs numpy and takes about two minutes on the machine used here.

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
"""Run the estimators on the grid and print every number on the page.

The transition table and the exact solve appear here only to generate episodes
and to grade the estimates. The estimators receive nothing but the episodes.
"""
from functools import partial

import numpy as np

from estimators import GAMMA, every_visit_mc, first_visit_mc, td0
from gridworld import GOAL, N, PI, PIT, R, TERMINAL, discounted, episode
from gridworld import fixed_policy, transitions

SLIP = 0.2
P = transitions(SLIP)
LIVE = [s for s in range(N) if s not in TERMINAL]


def exact_values():
    """The answer key: v = (I - gamma Q)^-1 b, from the current rewards."""
    Q, b = fixed_policy(PI, SLIP)
    return np.linalg.solve(np.eye(N) - GAMMA * Q, b)


def rms(V, v):
    return float(np.sqrt(np.mean((V[LIVE] - v[LIVE]) ** 2)))


def play(rng):
    """One episode from a random non-terminal cell."""
    return episode(P, PI, int(rng.choice(LIVE)), rng)


def train(seed, episodes, methods, after_episode):
    """Feed one stream of episodes to every method."""
    rng = np.random.default_rng(seed)
    V = {name: np.zeros(N) for name in methods}
    count = {name: np.zeros(N) for name in methods}
    for k in range(1, episodes + 1):
        steps = play(rng)
        for name, update in methods.items():
            update(steps, V[name], count[name])
        after_episode(k, V, count)


def one_episode():
    """Both updates on one real episode, from estimates of 0 and a step of 1."""
    steps = episode(P, PI, 13, np.random.default_rng(2))
    print("episode:", *[int(s[0]) for s in steps], "goal")
    mc, td, twice = np.zeros(N), np.zeros(N), np.zeros(N)
    first_visit_mc(steps, mc, np.zeros(N))
    td0(steps, td, np.zeros(N), step=1.0)
    td0(steps, twice, np.zeros(N), step=1.0)
    td0(steps, twice, np.zeros(N), step=1.0)
    for name, V in [("MC", mc), ("TD", td), ("TD, same episode again", twice)]:
        print(f"  {name}:", [round(float(V[s[0]]), 2) for s in steps])


def repeats(n=40_000):
    """How often an episode returns to a cell it already left."""
    rng = np.random.default_rng(1)
    cells = ([int(s[0]) for s in play(rng)] for _ in range(n))
    print(f"\nepisodes repeating some cell: {sum(len(set(c)) < len(c) for c in cells) / n:.3f}")


def target_spread(v, n=50_000):
    """How much one target varies by cell, when the estimates are exact."""
    Q, _ = fixed_policy(PI, SLIP)
    P_pi = P[np.arange(N), PI]
    targets = R + GAMMA * v
    second = np.linalg.solve(np.eye(N) - GAMMA**2 * Q, P_pi @ (R**2 + 2 * GAMMA * R * v))
    print("\ncell  exact  return sd  TD target sd")
    for s in LIVE:
        td_sd = np.sqrt(P_pi[s] @ (targets - P_pi[s] @ targets) ** 2)
        print(f"{s:4d} {v[s]:6.2f} {np.sqrt(second[s] - v[s] ** 2):10.2f} {td_sd:13.2f}")
    rng = np.random.default_rng(3)
    runs = [episode(P, PI, 13, rng) for _ in range(n)]
    G = np.array([discounted(run, GAMMA) for run in runs])
    pit = np.array([run[-1][3] == PIT for run in runs])
    print(f"\n{n} returns from cell 13: mean {G.mean():.2f}, sd {G.std():.2f},"
          f" range {G.min():.2f} to {G.max():.2f}")
    print(f"  pit {pit.mean():.3f} of episodes, mean return {G[pit].mean():.2f};"
          f" goal mean return {G[~pit].mean():.2f}")
    print("  share per unit bin from -19 to 4:",
          np.round(np.histogram(G, np.arange(-19, 5))[0] / n, 3).tolist())
    print("  TD targets:", [(c, round(float(P[13, PI[13], c]), 1),
                             round(float(targets[c]), 2)) for c in (9, 12, 14)])


def cell_13(v, runs=1000, episodes=1000):
    """Bias and spread of V(13) across independent training runs."""
    points = [10, 20, 50, 100, 200, 500, 1000]
    seen = {name: {k: [] for k in points} for name in ("MC", "TD")}

    def record(k, V, _):
        if k in points:
            for name in seen:
                seen[name][k].append(V[name][13])

    for seed in range(runs):
        train(seed, episodes, {"MC": first_visit_mc, "TD": td0}, record)
    print(f"\nV(13) over {runs} training runs, exact {v[13]:.2f}")
    print("episodes     mean     sd    p10    p90  still at 0")
    for name in seen:
        for k in points:
            x = np.array(seen[name][k])
            print(f"{name} {k:5d} {x.mean():8.2f} {x.std():6.2f}"
                  f" {np.percentile(x, 10):6.2f} {np.percentile(x, 90):6.2f}"
                  f" {np.mean(x == 0):8.3f}")


def inherited_noise(runs=1000, episodes=100):
    """TD at cell 13 when the four cells by the pit use true averages as targets."""
    seen = []
    for seed in range(runs):
        rng = np.random.default_rng(seed)
        V, count = np.zeros(N), np.zeros(N)
        for _ in range(episodes):
            for cell, _, reward, next_cell in play(rng):
                count[cell] += 1
                target = reward + GAMMA * V[next_cell]
                if cell in (2, 5, 7, 10):
                    target = P[cell, PI[cell]] @ (R + GAMMA * V)
                V[cell] += count[cell] ** -0.7 * (target - V[cell])
        seen.append(V[13])
    print(f"\nTD at {episodes} episodes, true averages by the pit: mean of V(13)"
          f" {np.mean(seen):.2f}, sd {np.std(seen):.2f}")


def sweeps(n=12):
    """V(13) after each exact pass from 0: the expected reward of k moves."""
    Q, b = fixed_policy(PI, SLIP)
    V, values = np.zeros(N), []
    for _ in range(n):
        V = b + GAMMA * Q @ V
        values.append(round(float(V[13]), 2))
    return values


def td_dip(runs=1000):
    """TD's error at cell 13 as the rewards, the start or the update order change."""
    points = [10, 20, 50, 100, 200, 500]
    print("\nV(13) after each of 12 sweeps:", sweeps())
    print("TD mean minus exact at cell 13, by episodes", points)
    built = R.copy()
    goal_only, pit_only, steps_only = 0 * built, 0 * built, built.copy()
    goal_only[GOAL], pit_only[PIT] = built[GOAL], built[PIT]
    steps_only[TERMINAL] = 0.0
    cases = [("the full grid", built, 0.0, False), ("only the goal pays", goal_only, 0.0, False),
             ("only the pit pays", pit_only, 0.0, False),
             ("only the step costs", steps_only, 0.0, False),
             ("start at exact values", built, None, False),
             ("start at +100", built, 100.0, False),
             ("update backward", built, 0.0, True)]
    for label, rewards, start, backward in cases:
        R[:] = rewards
        v = exact_values()
        seen = {k: [] for k in points}
        for seed in range(runs):
            rng = np.random.default_rng(seed)
            V, count = v.copy(), np.zeros(N)
            if start is not None:
                V[LIVE] = start
            for k in range(1, points[-1] + 1):
                steps = play(rng)
                td0(steps[::-1] if backward else steps, V, count)
                if k in seen:
                    seen[k].append(V[13])
        print(f"  {label:22s} exact {v[13]:6.2f} ",
              *[f"{np.mean(seen[k]) - v[13]:6.2f}" for k in points],
              f"  sd at 50: {np.std(seen[50]):.2f}")
    R[:] = built


def whole_grid(v, runs=100, episodes=6000):
    """RMS error over the 14 cells, including TD at several step-size rules."""
    points = [10, 20, 50, 100, 200, 500, 1000, 2000, 4000, 6000]
    methods = {"first-visit MC": first_visit_mc, "every-visit MC": every_visit_mc}
    for decay in (0.5, 0.7, 0.85, 1.0):
        methods[f"TD N^-{decay}"] = partial(td0, decay=decay)
    methods["first-visit MC, step 0.05"] = partial(first_visit_mc, step=0.05)
    methods["TD, step 0.05"] = partial(td0, step=0.05)
    shown = ("first-visit MC", "TD N^-0.7")
    error = {name: {k: [] for k in points} for name in methods}
    final = {name: [] for name in methods}
    grids, updates = {}, []

    def record(k, V, count):
        if k in points:
            for name in methods:
                error[name][k].append(rms(V[name], v))
            grids[seed, k] = {name: V[name].copy() for name in shown}
        if k == episodes:
            for name in methods:
                final[name].append(V[name].copy())
            updates.append([count[name][2] for name in shown])

    for seed in range(runs):
        train(seed, episodes, methods, record)
    print(f"\nRMS error over 14 cells, mean of {runs} training runs")
    print(" " * 26, *[f"{k:6d}" for k in points])
    for name in methods:
        print(f"{name:26s}", *[f"{np.mean(error[name][k]):6.3f}" for k in points])

    print("\nAt 6000 episodes, over the 14 cells: bias, standard deviation")
    for name in methods:
        grid = np.array(final[name])
        variance = np.mean(grid.var(axis=0)[LIVE])
        # The mean of the runs is itself noisy, so its squared gap overstates bias.
        bias = np.sqrt(max(np.mean((grid.mean(axis=0) - v)[LIVE] ** 2) - variance / runs, 0))
        sd = np.sqrt(variance)
        print(f"{name:26s} {bias:6.3f} {sd:6.3f}")

    errors = []
    for seed in range(runs):
        rng = np.random.default_rng(seed)
        V, count = np.zeros(N), np.zeros(N)
        for k in range(1, episodes + 1):
            td0(play(rng), V, count, decay=0.7 if k <= 1000 else 1.0)
        errors.append(rms(V, v))
    print(f"TD N^-0.7 for 1000 episodes, then N^-1.0: {np.mean(errors):.3f}")

    def spread(name, k):
        return np.std([grids[s, k][name] for s in range(runs)], axis=0)

    print("\nTD variance over MC variance across the 14 cells, by episodes")
    ratios = [np.mean(spread(shown[1], k)[LIVE] ** 2) / np.mean(spread(shown[0], k)[LIVE] ** 2)
              for k in points]
    print(" " * 26, *[f"{ratio:6.2f}" for ratio in ratios])
    for k in (1000, 6000):
        print(f"TD sd over MC sd by cell at {k}, cells {LIVE}:")
        print("  ", np.round(spread(shown[1], k)[LIVE] / spread(shown[0], k)[LIVE], 2).tolist())
    mc_updates, td_updates = np.mean(updates, axis=0)
    print(f"cell 2 at 6000: MC {mc_updates:.0f} updates, step {1 / mc_updates:.5f};"
          f" TD {td_updates:.0f} updates, step {td_updates ** -0.7:.5f}")

    print("\nRMS error by cell at 6000 episodes", LIVE)
    for name in shown:
        gaps = [grids[s, 6000][name] - v for s in range(runs)]
        by_cell = np.sqrt(np.mean(np.square(gaps), axis=0))[LIVE]
        print(f"  {name}:", np.round(by_cell, 2).tolist())

    # Fig. 6 shows a typical run: the median Monte Carlo error at 1000 episodes.
    typical = int(np.argsort(error["first-visit MC"][1000])[runs // 2])
    print(f"\ntypical training run: seed {typical}")
    for k in (100, 1000, 6000):
        for name in shown:
            print(f"  {name} @ {k}:", np.round(grids[typical, k][name], 1).tolist())


def main():
    v = exact_values()
    print("exact values:", np.round(v, 2).tolist())
    one_episode()
    repeats()
    target_spread(v)
    cell_13(v)
    inherited_noise()
    td_dip()
    whole_grid(v)


if __name__ == "__main__":
    main()

exact values: [2.16, 4.04, 6.48, 0.0, 0.61, 0.06, 0.0, 6.48, -0.72, -1.03, -0.1, 4.02, -1.86, -2.01, -1.08, 1.98]
episode: 13 9 5 4 0 1 2 goal
  MC: [0.63, 1.81, 3.12, 4.58, 6.2, 8.0, 10.0]
  TD: [-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, 10.0]
  TD, same episode again: [-1.9, -1.9, -1.9, -1.9, -1.9, 8.0, 10.0]

episodes repeating some cell: 0.330

cell  exact  return sd  TD target sd
   0   2.16       7.58          1.00
   1   4.04       8.58          1.79
   2   6.48       9.35          8.96
   4   0.61       7.04          0.66
   5   0.06       9.86          6.75
   7   6.48       9.35          8.96
   8  -0.72       6.47          0.54
   9  -1.03       8.64          0.21
  10  -0.10      10.00          6.77
  11   4.02       8.61          1.83
  12  -1.86       5.89          0.44
  13  -2.01       7.57          0.22
  14  -1.08       8.66          0.80
  15   1.98       7.81          1.42

50000 returns from cell 13: mean -2.01, sd 7.58, range -18.10 to 3.12
  pit 0.200 of episodes, mean return -16.78; goal mean return 1.67
  share per unit bin from -19 to 4: [0.081, 0.0, 0.064, 0.035, 0.015, 0.004, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.001, 0.003, 0.016, 0.02, 0.044, 0.061, 0.157, 0.082, 0.0, 0.415]
  TD targets: [(9, 0.8, -1.93), (12, 0.1, -2.68), (14, 0.1, -1.97)]

V(13) over 1000 training runs, exact -2.01
episodes     mean     sd    p10    p90  still at 0
MC    10    -1.26   5.44  -8.66   3.12    0.391
MC    20    -1.65   5.45  -8.74   3.12    0.141
MC    50    -1.89   4.05  -7.31   2.50    0.009
MC   100    -2.07   2.69  -5.54   1.56    0.000
MC   200    -1.95   1.80  -4.30   0.34    0.000
MC   500    -1.96   1.15  -3.46  -0.57    0.000
MC  1000    -1.99   0.79  -3.02  -0.97    0.000
TD    10    -1.07   1.35  -2.28   0.00    0.391
TD    20    -2.14   2.20  -4.48   0.00    0.141
TD    50    -2.79   1.93  -5.26  -0.66    0.009
TD   100    -2.59   1.39  -4.45  -0.92    0.000
TD   200    -2.29   0.92  -3.52  -1.12    0.000
TD   500    -2.07   0.53  -2.74  -1.41    0.000
TD  1000    -2.03   0.36  -2.51  -1.57    0.000

TD at 100 episodes, true averages by the pit: mean of V(13) -2.59, sd 0.37

V(13) after each of 12 sweeps: [-1.0, -1.9, -3.94, -4.61, -3.03, -2.88, -2.37, -2.2, -2.09, -2.05, -2.02, -2.01]
TD mean minus exact at cell 13, by episodes [10, 20, 50, 100, 200, 500]
  the full grid          exact  -2.01    0.93  -0.13  -0.79  -0.58  -0.28  -0.06   sd at 50: 1.93
  only the goal pays     exact   4.67   -4.63  -4.25  -2.78  -1.52  -0.64  -0.13   sd at 50: 1.09
  only the pit pays      exact  -2.70    2.57   1.98   1.00   0.48   0.19   0.03   sd at 50: 1.66
  only the step costs    exact  -3.98    2.99   2.14   0.99   0.46   0.18   0.04   sd at 50: 0.60
  start at exact values  exact  -2.01   -0.01  -0.20  -0.19  -0.08  -0.02  -0.00   sd at 50: 1.95
  start at +100          exact  -2.01   89.93  73.63  41.87  21.60   8.87   1.77   sd at 50: 17.84
  update backward        exact  -2.01    0.86   0.32   0.02   0.04   0.03   0.01   sd at 50: 2.77

RMS error over 14 cells, mean of 100 training runs
                               10     20     50    100    200    500   1000   2000   4000   6000
first-visit MC              5.281  4.406  2.933  1.942  1.361  0.853  0.598  0.447  0.314  0.257
every-visit MC              5.350  4.476  3.009  2.008  1.404  0.876  0.622  0.459  0.321  0.263
TD N^-0.5                   3.960  3.477  2.487  1.810  1.432  1.121  0.927  0.796  0.641  0.581
TD N^-0.7                   3.624  3.145  2.218  1.530  1.093  0.746  0.541  0.436  0.320  0.271
TD N^-0.85                  3.477  3.027  2.209  1.602  1.175  0.771  0.524  0.379  0.260  0.204
TD N^-1.0                   3.396  2.987  2.296  1.821  1.472  1.120  0.893  0.721  0.569  0.493
first-visit MC, step 0.05   2.610  2.193  1.690  1.402  1.320  1.313  1.300  1.337  1.373  1.380
TD, step 0.05               2.775  2.497  2.034  1.604  1.161  0.901  0.873  0.902  0.899  0.899

At 6000 episodes, over the 14 cells: bias, standard deviation
first-visit MC              0.000  0.264
every-visit MC              0.007  0.270
TD N^-0.5                   0.040  0.605
TD N^-0.7                   0.014  0.284
TD N^-0.85                  0.022  0.211
TD N^-1.0                   0.225  0.530
first-visit MC, step 0.05   0.033  1.440
TD, step 0.05               0.000  0.937
TD N^-0.7 for 1000 episodes, then N^-1.0: 0.297

TD variance over MC variance across the 14 cells, by episodes
                             0.40   0.44   0.55   0.62   0.65   0.76   0.84   0.98   1.05   1.16
TD sd over MC sd by cell at 1000, cells [0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15]:
   [0.75, 1.32, 1.83, 0.83, 1.31, 1.54, 0.7, 0.69, 1.21, 1.1, 0.49, 0.43, 0.7, 0.57]
TD sd over MC sd by cell at 6000, cells [0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15]:
   [1.03, 1.7, 2.32, 0.97, 1.55, 2.17, 0.56, 0.81, 1.5, 1.3, 0.39, 0.5, 0.79, 0.6]
cell 2 at 6000: MC 3596 updates, step 0.00028; TD 3992 updates, step 0.00301

RMS error by cell at 6000 episodes [0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15]
  first-visit MC: [0.18, 0.14, 0.15, 0.17, 0.24, 0.21, 0.23, 0.28, 0.31, 0.22, 0.3, 0.34, 0.35, 0.41]
  TD N^-0.7: [0.19, 0.24, 0.34, 0.16, 0.37, 0.47, 0.13, 0.23, 0.47, 0.29, 0.12, 0.17, 0.28, 0.24]

typical training run: seed 38
  first-visit MC @ 100: [-0.4, 2.6, 3.6, 0.0, -1.0, -0.4, 0.0, 4.8, -2.9, -1.0, 0.0, 2.6, -1.5, -4.7, -4.0, -0.3]
  TD N^-0.7 @ 100: [1.3, 0.6, 2.5, 0.0, 0.0, -0.1, 0.0, 7.3, -1.4, -1.1, -2.0, 2.8, -2.8, -2.1, -4.2, -0.5]
  first-visit MC @ 1000: [1.5, 3.6, 5.9, 0.0, -0.0, -0.0, 0.0, 5.7, -1.0, -1.2, -0.7, 3.3, -2.0, -2.5, -2.4, 2.0]
  TD N^-0.7 @ 1000: [1.6, 3.8, 6.6, 0.0, 0.0, -0.7, 0.0, 6.7, -1.1, -1.9, 0.3, 4.2, -2.1, -2.8, -1.5, 1.3]
  first-visit MC @ 6000: [2.1, 3.8, 6.3, 0.0, 0.5, -0.3, 0.0, 6.5, -0.7, -1.4, -0.3, 4.1, -1.7, -2.5, -1.0, 2.6]
  TD N^-0.7 @ 6000: [1.8, 3.7, 6.3, 0.0, 0.4, -0.8, 0.0, 6.4, -0.9, -1.3, 0.7, 4.4, -1.9, -2.0, -0.8, 2.5]

A value function cannot yet choose a better move

Everything above scored one fixed policy. Improving a policy means comparing the moves available in a cell, and without the rules a value function cannot do that.¹

Take cell 14, where the fixed policy aims up. The second lesson uses the rules to show that aiming right is better: up is worth −1.08 and right is worth +0.32. That calculation averages over where each move lands, so it needs the move probabilities the agent no longer has.

The fixed policy's episodes do not help, because in cell 14 it always aims up. They never show what aiming right would do. One route is to estimate the move probabilities from experience, which this course reaches later. The more direct route needs two things: an estimate for each move in each cell, called an action value, and a policy that sometimes tries moves other than its current favorite, called exploration.¹ Learning to choose better moves is called control.

TD-Gammon could choose moves from state values because it had backgammon's rules. For each legal move it could work out the position that move leads to, and it played the move whose position its network scored highest.¹ It needed no action values, and its play improved as its estimates did. Tesauro calls this a combined prediction and control task.⁴ He also credits the random dice with making the learner explore more positions than it otherwise would.⁴ An agent without the rules cannot score moves this way.