Action values let an agent improve its policy from episodes alone

Without the slip rule, state values cannot rank the moves at cell 14

Cell 14 is in the bottom row of the slippery grid, one cell left of the bottom-right corner, and the fixed policy aims up there. Policy iteration found that aiming right is better, worth 0.32 against up's −1.08. It priced right by weighting each cell the move can land in by the chance of landing there, as the first panel of Fig. 1 shows.

An agent that learned state values from episodes has the three values in that sum. It does not have 0.8, 0.1 and 0.1, because those come from the slip rule and the agent only sees what happened. Without them it cannot score right, or any other move, from state values.¹

It can score a move by trying it. Suppose the agent in cell 14 aims right once and then follows the fixed policy. The table shows one such episode.

The returns come from the backward pass of first-visit Monte Carlo, with one change: each step is labeled by its (cell, move) pair instead of its cell. Cell 14 appears twice, aimed right and then up, so the episode gives a return to each of those moves, −17.29 to right and −19.00 to up.

One return is noisy, and this one ended in the pit. The average of many returns after a pair estimates the pair's action value, the expected return from taking move a in cell s and following \pi afterward.¹

Each return after (14, right) is a sample of q_\pi(14, \text{right}), so their average converges to 0.32 without the agent using any probability.

The greedy step over action values reads no probabilities

Policy iteration improved a policy with the greedy step. Written out, the step uses the model.

The sum is q_\pi(s, a), so the same step reads as follows.

Every use of P and R now sits inside q_\pi, and an agent can estimate q_\pi by averaging returns. An agent holding estimates of the action values picks the greedy move in a cell by comparing four numbers. In Sutton and Barto's words, with an action-value function "no model is needed to construct the greedy policy".¹

The greedy policy is also no worse than \pi. The policy improvement theorem says that if q_\pi(s, \pi'(s)) \ge v_\pi(s) in every cell, then v_{\pi'}(s) \ge v_\pi(s) in every cell. The greedy step meets that condition, and checking it takes only action values.¹

The first equality is what greedy means. The inequality holds because the largest of four values is at least the value of any one of them, the policy's own move included. The last equality holds because \pi picks one move per cell, so taking \pi's move and then following \pi is just following \pi.

Exploring starts give every move returns of its own

Averages exist only for moves the agent has tried. A greedy agent takes one move in each cell, so after an episode's first move every pair it visits is the policy's own. The other three moves in each cell get no returns, and their estimates never change.¹ In the code below a move with no returns has no estimate yet, and the greedy step skips it, so the policy could never switch to such a move.

This lesson supplies the missing returns with exploring starts: each episode begins from a random (cell, move) pair, and every pair has some chance of being picked.¹ Here the pick is uniform over the 56 pairs, and after the first move the agent follows its policy.

Exploring starts needs an environment that can open an episode at any (cell, move) pair, and play below takes the start pair as an argument. Sutton and Barto note that the assumption "cannot be relied upon in general, particularly when learning directly from actual interaction with an environment".¹ The usual alternative, a policy that keeps some chance on every move, needs a lesson of its own.

The runs below depend on the assumption. With explore=False, each episode starts in a random cell with the policy's own move, and none of the 20 runs reaches the optimal policy in 10,000 episodes. Every average then belongs to a move the policy already takes, so each greedy step returns the policy it started from.

Monte Carlo ES improves the policy after every episode

Policy iteration evaluated each policy completely before improving it. From samples, a complete evaluation would take infinitely many episodes. Sutton and Barto call the general scheme generalized policy iteration (GPI): evaluation and improvement interact at any granularity, and neither has to finish before the other runs.¹ Value iteration was one case of it, with an improvement folded into every sweep.

Monte Carlo ES, short for Monte Carlo with exploring starts, takes the episode as its unit. After each episode it adds the episode's returns to the averages of the pairs it visited, then makes the policy greedy, which can change only the cells the episode visited. The averages are never reset, so a pair's average mixes returns earned under every policy the agent has used.¹

mc_control.py is the complete method. It imports the grid from gridworld.py, printed with the exact solve, and first_visit_mc from estimators.py, printed with Monte Carlo prediction. pairs numbers each pair as 4 × cell + move, so first_visit_mc averages returns per pair as it averaged them per cell. greedy is the improvement step, and step, the environment, is the only function that reads the grid's rules.

A greedy policy in mid-training can press the bottom row into the wall, like the stuck policy, and an episode under it never ends. play stops every episode after 200 moves, so a cut episode's returns leave out whatever would have come later. In the main runs, 84 of 2,000,000 episodes were cut.

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
"""Monte Carlo control with exploring starts on the slippery grid.

The agent's side is pairs, greedy and the call to first_visit_mc. It sees
only episodes. Only step reads the grid's rules, to play them out.
"""

import numpy as np
from estimators import first_visit_mc
from gridworld import N, R, TERMINAL, move

SLIP = 0.2
LIVE = [s for s in range(N) if s not in TERMINAL]
CAP = 200  # an episode stops after this many moves


def step(s, a, rng):
    """The environment: the aimed move with probability 1 - SLIP, otherwise a
    slip to either side, as in transitions(). Returns the reward and next cell."""
    u = rng.random()
    aim = a if u < 1 - SLIP else (a + 1) % 4 if u < 1 - SLIP / 2 else (a + 3) % 4
    s_next = move(s, aim)
    return R[s_next], s_next


def play(policy, start, first, rng):
    """One episode that opens with the move `first` in cell `start`, follows
    `policy` after that, and stops at a terminal cell or after CAP moves."""
    s, a, steps = start, first, []
    while s not in TERMINAL and len(steps) < CAP:
        reward, s_next = step(s, a, rng)
        steps.append((s, a, reward, s_next))
        s, a = s_next, policy[s_next]
    return steps


def pairs(steps):
    """Label each step by its (cell, move) pair, numbered 4 * cell + move, so
    that first_visit_mc averages returns per pair instead of per cell."""
    return [(4 * s + a, a, r, s_next) for s, a, r, s_next in steps]


def greedy(q, count, policy):
    """The move with the largest average return in each cell. A move with no
    returns has no estimate yet, and a cell with none keeps its move."""
    Q = np.where(count > 0, q, -np.inf).reshape(N, 4)
    return np.where(count.reshape(N, 4).any(axis=1), Q.argmax(axis=1), policy)


def control(policy, episodes, rng, explore=True, every=1, forget=False,
            watch=None):
    """Monte Carlo ES. Each episode starts from a random (cell, move) pair, or
    from a random cell and the policy's move if explore is False. The policy
    turns greedy every `every` episodes, and forget clears the averages then."""
    q, count = np.zeros(4 * N), np.zeros(4 * N)
    for k in range(1, episodes + 1):
        start = LIVE[rng.integers(len(LIVE))]
        first = rng.integers(4) if explore else policy[start]
        steps = play(policy, start, first, rng)
        first_visit_mc(pairs(steps), q, count)
        if k % every == 0:
            policy = greedy(q, count, policy)
            if forget:
                q[:], count[:] = 0.0, 0.0
        if watch:
            watch(k, policy, q, count, steps)
    return policy, q, count

experiment.py plays 20 runs of 100,000 episodes, one per seed, each starting from the fixed policy with no averages. A run counts as optimal when every arrow is an optimal move, either up or right at cells 9 and 12, where the two tie. After 10,000 episodes half the runs are optimal, and after 100,000, 18 of 20 are. The two still short are wrong at cell 5, beside the pit, where the best move beats the next by only 0.35. Twenty other seeds repeat the half at 10,000 and do better at 100,000.

Run 0 has three arrows wrong after 1,000 episodes, at cells 9, 10 and 13. By 10,000 only cell 10 is wrong. It aims down, whose exact action value is −0.29, against 0.06 for right. By 100,000 every arrow is optimal.

uv run experiment.py needs gridworld.py, control.py from the policy iteration lesson, estimators.py and mc_control.py in one folder. It installs numpy and takes a little over two minutes on the machine used here.

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
"""Run Monte Carlo ES on the grid and print every number on the page. The
exact values from control.py appear only to grade the learned policy."""

from collections import Counter

import numpy as np
from control import action_values, evaluate
from estimators import first_visit_mc
from gridworld import ARROWS, N, PI, draw, transitions
from mc_control import CAP, LIVE, control, pairs, play

PI_STAR = draw("""> > > .
                  ^ ^ . ^
                  ^ ^ > ^
                  ^ > > ^""")  # the optimal arrows from policy iteration
Q_STAR = action_values(evaluate(PI_STAR), transitions(0.2))
BEST = {s: np.flatnonzero(Q_STAR[s] > Q_STAR[s].max() - 1e-9) for s in LIVE}
SEEDS, EPISODES = range(20), 100_000
CHECKS = [1_000, 2_000, 5_000, 10_000, 20_000, 50_000, 100_000]


def wrong(policy):
    """Cells whose move is not optimal. Cells 9 and 12 have two optimal moves."""
    return [s for s in LIVE if policy[s] not in BEST[s]]


def arrows(policy):
    marks = ["." if s not in LIVE else ARROWS[policy[s]] for s in range(N)]
    return " / ".join(" ".join(marks[r:r + 4]) for r in range(0, N, 4))


def one_episode():
    """The return one episode gives each pair it visits."""
    steps = play(PI, 14, 1, np.random.default_rng(1))
    q, count = np.zeros(4 * N), np.zeros(4 * N)
    first_visit_mc(pairs(steps), q, count)
    print("cell, move, reward:", [(s, ARROWS[a], int(r)) for s, a, r, _ in steps])
    print("return per pair:", [(s, ARROWS[a], round(float(q[4 * s + a]), 2))
                               for s, a, _, _ in steps])


def runs(episodes=EPISODES, **options):
    """At each checkpoint, the number of runs with an optimal policy and the
    cells the other runs get wrong, plus run 0's policy and averages."""
    optimal, missed, snaps, cut = Counter(), {k: Counter() for k in CHECKS}, {}, [0]

    def watch(k, policy, q, count, steps):
        cut[0] += len(steps) == CAP
        if k in CHECKS:
            optimal[k] += not wrong(policy)
            missed[k].update(wrong(policy))
            if seed == 0:
                snaps[k] = policy.copy(), q.copy()

    for seed in SEEDS:
        control(PI.copy(), episodes, np.random.default_rng(seed), watch=watch,
                **options)
    return optimal, missed, snaps, cut[0]


def main():
    v_pi = evaluate(PI)
    print("fixed policy: v at cells 10, 13, 14, 15:", v_pi[[10, 13, 14, 15]].round(2))
    print("fixed policy: q at cell 14 (up, right, down, left):",
          action_values(v_pi, transitions(0.2))[14].round(2))
    print("q* at cells 5 and 10 (up, right, down, left):",
          Q_STAR[[5, 10]].round(2).tolist())
    one_episode()
    schedules = {"every episode": runs(),
                 "every 5,600": runs(every=5_600),
                 "every 5,600, cleared": runs(every=5_600, forget=True)}
    print(f"\nruns with an optimal policy, of {len(SEEDS)}, by when it improves")
    print("episodes", *[f"{name:>21s}" for name in schedules])
    for k in CHECKS:
        print(f"{k:8d}", *[f"{s[0][k]:21d}" for s in schedules.values()])
    print(f"episodes cut off at {CAP} moves:",
          {name: s[3] for name, s in schedules.items()})
    optimal, missed, snaps, _ = schedules["every episode"]
    for k in (20_000, 100_000):
        print(f"every episode, wrong cells at {k}: {dict(sorted(missed[k].items()))}")
    for k in (1_000, 10_000, 100_000):
        policy, _ = snaps[k]
        print(f"run 0 at {k:6d}: {arrows(policy)}, wrong {wrong(policy)}")
    optimal, *_ = runs(episodes=10_000, explore=False)
    print("no exploring starts, optimal runs at 10,000:", optimal[10_000])


if __name__ == "__main__":
    main()

fixed policy: v at cells 10, 13, 14, 15: [-0.1  -2.01 -1.08  1.98]
fixed policy: q at cell 14 (up, right, down, left): [-1.08  0.32 -1.78 -2.55]
q* at cells 5 and 10 (up, right, down, left): [[0.06, -15.93, -3.58, -0.29], [-15.93, 0.06, -0.29, -3.58]]
cell, move, reward: [(14, '>', -1), (15, '^', -1), (14, '^', -1), (10, '>', -20)]
return per pair: [(14, '>', -17.29), (15, '^', -18.1), (14, '^', -19.0), (10, '>', -20.0)]

runs with an optimal policy, of 20, by when it improves
episodes         every episode           every 5,600  every 5,600, cleared
    1000                     2                     0                     0
    2000                     3                     0                     0
    5000                     6                     0                     0
   10000                    10                     2                     2
   20000                    12                    15                     3
   50000                    16                    16                     5
  100000                    18                    18                     2
episodes cut off at 200 moves: {'every episode': 84, 'every 5,600': 277, 'every 5,600, cleared': 2902}
every episode, wrong cells at 20000: {5: 4, 9: 1, 10: 3}
every episode, wrong cells at 100000: {5: 2}
run 0 at   1000: > > > . / ^ ^ . ^ / ^ < v ^ / ^ < > ^, wrong [9, 10, 13]
run 0 at  10000: > > > . / ^ ^ . ^ / ^ ^ v ^ / > > > ^, wrong [10]
run 0 at 100000: > > > . / ^ ^ . ^ / ^ ^ > ^ / > > > ^, wrong []
no exploring starts, optimal runs at 10,000: 0

Unfinished evaluation works when the averages carry over

Improving after every episode means each new policy is judged by averages that mix returns from many earlier policies. Fig. 3 compares it with two slower schedules, which make the policy greedy only every 5,600 episodes, about 100 starts per pair. One keeps the averages, as Monte Carlo ES does. The other clears them at each improvement with forget=True, so each policy is evaluated from scratch, as in policy iteration.¹

Waiting 5,600 episodes between improvements gains nothing by the end. It delays the first improvement, catches up by 20,000 episodes, and from 50,000 on has no more runs at the optimal policy than improving after every episode. Clearing the averages is what costs. The cleared schedule never has more than 5 runs at the optimal policy, and it ends with 2. Each of its policies is judged on 5,600 episodes, about 100 returns for each move the policy does not take, while the kept schedule improves at the same episodes and keeps every return.

On this grid evaluation never had to finish before the policy changed, but its averages had to keep their returns.

Only the optimal policy can be a resting point

Sutton and Barto give half an argument that Monte Carlo ES ends at the optimal policy.¹ Suppose the policy and the averages stopped changing. The averages would then be that policy's action values, and the policy would be greedy with respect to them, so in every cell the following holds.

The last line is the Bellman optimality equation, and only v_* solves it, so \pi is optimal. A suboptimal policy cannot be a resting point.

The other half, that the process must come to rest, has not been proved for this algorithm in general. Sutton and Barto call it "one of the most fundamental open theoretical questions in reinforcement learning".¹ Proofs now cover one variant and two classes of problem, each with conditions of its own on step sizes or on long episodes.

• Tsitsiklis proves convergence for a variant that updates only the pair each episode starts from, with every pair used as a start equally often, on any finite problem with a discount below 1.²
• Wang, Yuan, Shao and Ross prove it for first-visit updates to every pair, as in mc_control.py, on problems where an optimal policy never revisits a state.³
• Delattre and Fournier prove it for first-visit Monte Carlo control on any finite problem with a discount below 1/2.⁴

None of the three covers mc_control.py on this grid. Tsitsiklis's variant updates only the start pair, where mc_control.py updates every pair an episode visits. The grid's discount is 0.9, above 1/2, and its optimal policy can revisit a state: cell 2's only optimal move, right, slips up into the edge with probability 0.1 and leaves the agent in cell 2. Wang and colleagues list weaker conditions than theirs as an open problem,³ and Delattre and Fournier write that "only half the way is done".⁴ For this grid the question stays open. The runs show what Monte Carlo ES did on the seeds tried, and no theorem says that every run must end at the optimal policy.