ε-greedy control settles for the best policy that keeps exploring

Forty-two moves with no returns

We run Monte Carlo control from the hand-drawn policy with ordinary starts, where each episode begins in a random cell with the policy's own move. In 20 runs of 10,000 episodes, none reaches the optimal policy. Fig. 1 shows run 0 at the end. Each cell is four triangles, one per move, shaded by the average return after that move.

Only 14 of the 56 (cell, move) pairs have any returns, one in each cell. At cell 14, up has 976 returns and the other three moves have none. Right is the move that policy iteration switched cell 14 to in its first round, and the agent has never tried it there.

The greedy step cannot supply the missing returns. It would switch cell 14 to right only if right's average beat up's. Right has no average yet, so greedy in mc_control.py skips it. The agent would have to take right to give it returns, and the agent takes only the policy's move. Each episode adds returns to the same 14 pairs, so after 10,000 greedy steps the policy is still the hand-drawn one. Sutton and Barto state the general case: with no returns to average, the estimates of the other moves “will not improve with experience”.¹

So the agent has to take every move in every cell now and then, whatever its averages say. Exploring starts arranged that from outside the agent, by choosing each episode's first move. A policy that sometimes moves at random can arrange it instead.

A floor of ε/4 on every move

An ε-greedy policy usually makes the greedy move, the one with the largest average. With a small probability ε it instead picks one of the moves uniformly at random, the greedy move included.¹ In a cell whose greedy move is a^*, each move gets the following probability.

Every cell here has four moves, so with ε = 0.1 the greedy move gets 0.925 and each other move gets 0.025. A policy that gives every move in every cell at least \varepsilon/|\mathcal{A}(s)| is called ε-soft. The ε-greedy policy is the ε-soft policy closest to greedy, since every move gets the floor and the greedy move gets the rest.¹

The ε-greedy policy that makes the moves is also the policy whose action values the agent averages and then improves. Control of this kind is called on-policy.¹

In soft_control.py, soft_play draws each move ε-greedily. It replaces play in mc_control.py, a function that can follow only one move per cell. The loop in soft_control is the one in mc_control.py without exploring starts: each episode starts in a random cell, its returns join the averages, and the policy turns greedy. The array policy holds the greedy move in each cell. The file imports the grid from gridworld.py, action_values from control.py, the averaging from estimators.py, and the environment, pairs and greedy from mc_control.py, all unchanged.

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
"""On-policy first-visit Monte Carlo control with an epsilon-greedy policy.

Only the episodes differ from mc_control.py. In every cell the agent makes a
uniformly random move with probability eps, and the policy's move otherwise.
best_soft finds the best eps-soft policy exactly, to grade the runs.
"""

import numpy as np
from control import action_values
from estimators import first_visit_mc
from gridworld import N, TERMINAL, transitions
from mc_control import CAP, LIVE, SLIP, greedy, pairs, step


def soft_play(policy, eps, start, rng):
    """One episode from cell `start` under the eps-greedy policy around
    `policy`. It stops at a terminal cell or after CAP moves."""
    s, steps = start, []
    while s not in TERMINAL and len(steps) < CAP:
        a = rng.integers(4) if rng.random() < eps else policy[s]
        reward, s_next = step(s, a, rng)
        steps.append((s, a, reward, s_next))
        s = s_next
    return steps


def soft_control(policy, eps, episodes, rng, watch=None):
    """Each episode starts in a random cell and follows the eps-greedy policy.
    Its returns join the averages, and `policy` turns greedy after it."""
    q, count = np.zeros(4 * N), np.zeros(4 * N)
    for k in range(1, episodes + 1):
        start = LIVE[rng.integers(len(LIVE))]
        steps = soft_play(policy, eps, start, rng)
        first_visit_mc(pairs(steps), q, count)
        policy = greedy(q, count, policy)
        if watch:
            watch(k, policy, q, count, steps)
    return policy, q, count


def best_soft(eps, tol=1e-10):
    """The best eps-soft policy, exactly. It is the optimal policy of a grid
    that replaces the agent's aim with a random one with probability eps, so
    value iteration on that grid finds its value v. Also returns q[s, a], the
    expected return after move a in the real grid, following that policy."""
    P = transitions(SLIP)
    P_eps = (1 - eps) * P + eps * P.mean(axis=1, keepdims=True)
    v = np.zeros(N)
    while True:
        nxt = v.copy()
        nxt[LIVE] = action_values(v, P_eps)[LIVE].max(axis=1)
        if np.abs(nxt - v).max() < tol:
            return nxt, action_values(nxt, P)
        v = nxt

Random moves end the stall

We start 20 runs of soft_control from the hand-drawn policy, with ε = 0.1, no averages and seeds 0 to 19. A run counts when every arrow is an optimal move. After 10,000 episodes 6 of the 20 runs count, and after 200,000, 19 do. Setting ε to 0 in the same code removes the random moves, and then no run counts at 10,000 episodes.

uv run exploration.py needs gridworld.py, control.py, estimators.py, mc_control.py and soft_control.py in one folder. It installs numpy and takes about four minutes on the machine used here.

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
"""Print every number on the page: the greedy stall, eps-greedy control on 20
seeds, and the price of eps. The exact values from best_soft grade the runs."""

import numpy as np
from gridworld import N, PI
from mc_control import LIVE, control
from soft_control import best_soft, soft_control

SEEDS = range(20)


def best_moves(eps):
    """The moves that tie for best in each cell under the best eps-soft policy.
    eps = 0 gives the optimal moves, with up and right tied at cells 9 and 12."""
    _, q = best_soft(eps)
    return {s: set(np.flatnonzero(q[s] > q[s].max() - 1e-9)) for s in LIVE}


def runs_at_best(eps, checks):
    """At each checkpoint, the number of runs whose every arrow is a best move."""
    best, hits = best_moves(eps), dict.fromkeys(checks, 0)

    def watch(k, policy, q, count, steps):
        if k in hits:
            hits[k] += all(policy[s] in best[s] for s in LIVE)

    for seed in SEEDS:
        soft_control(PI.copy(), eps, max(checks), np.random.default_rng(seed),
                     watch)
    return list(hits.values())


def main():
    _, _, count = control(PI.copy(), 10_000, np.random.default_rng(0),
                          explore=False)
    print("greedy, ordinary starts, run 0 after 10,000 episodes")
    print("  pairs with returns:", int((count > 0).sum()), "of", 4 * len(LIVE))
    print("  cell 14 returns (up, right, down, left):",
          count[4 * 14:4 * 14 + 4].astype(int))

    fewest = {}

    def watch(k, policy, q, count, steps):
        if k == 10_000:
            fewest[k] = int(count.reshape(N, 4)[LIVE].min())

    _, q, _ = soft_control(PI.copy(), 0.1, 200_000, np.random.default_rng(0),
                           watch)
    print("eps 0.1, run 0")
    print("  fewest returns for any pair after 10,000:", fewest[10_000])
    print(f"  average for right at cell 14 after 200,000: {q[4 * 14 + 1]:.2f}")
    v_star, q_star = best_soft(0.0)
    _, q_soft = best_soft(0.1)
    print(f"  exact, best eps-soft policy: {q_soft[14, 1]:.2f}, "
          f"optimal policy: {q_star[14, 1]:.2f}")

    print("\nruns of 20 whose arrows are all best moves")
    print("  eps 0.0 at 10,000 episodes:", runs_at_best(0.0, [10_000]))
    checks = [1_000, 10_000, 100_000, 200_000]
    print(f"  eps 0.1 at {checks}:", runs_at_best(0.1, checks))
    checks = [1_000, 10_000, 100_000]
    print(f"  eps 0.5 at {checks}:", runs_at_best(0.5, checks))

    optimal = best_moves(0.0)
    print("\n  eps  average v* - v  cells whose best moves differ from optimal")
    for eps in (0.01, 0.1, 0.2, 0.3, 0.5):
        v, _ = best_soft(eps)
        differ = [s for s, moves in best_moves(eps).items() if moves != optimal[s]]
        print(f"{eps:5.2f}  {(v_star - v)[LIVE].mean():14.2f}  {differ}")
    first = next(e for e in range(1, 100) if best_moves(e / 100) != optimal)
    print("smallest eps, in steps of 0.01, with other best moves:", first / 100)
    v_half, _ = best_soft(0.5)
    for name, v in (("v* (eps 0)", v_star), ("best eps-soft v, eps 0.5", v_half)):
        print(f"{name}, by row:", v.reshape(4, 4).round(2).tolist())


if __name__ == "__main__":
    main()

greedy, ordinary starts, run 0 after 10,000 episodes
  pairs with returns: 14 of 56
  cell 14 returns (up, right, down, left): [976   0   0   0]
eps 0.1, run 0
  fewest returns for any pair after 10,000: 24
  average for right at cell 14 after 200,000: -0.41
  exact, best eps-soft policy: -0.37, optimal policy: 0.61

runs of 20 whose arrows are all best moves
  eps 0.0 at 10,000 episodes: [0]
  eps 0.1 at [1000, 10000, 100000, 200000]: [0, 6, 14, 19]
  eps 0.5 at [1000, 10000, 100000]: [7, 18, 20]

  eps  average v* - v  cells whose best moves differ from optimal
 0.01            0.10  []
 0.10            1.08  []
 0.20            2.23  []
 0.30            3.46  []
 0.50            6.09  [9]
smallest eps, in steps of 0.01, with other best moves: 0.33
v* (eps 0), by row: [[2.16, 4.04, 6.48, 0.0], [0.61, 0.06, 0.0, 6.48], [-0.71, -1.01, 0.06, 4.04], [-1.73, -0.71, 0.61, 2.16]]
best eps-soft v, eps 0.5, by row: [[-4.05, -2.26, 1.42, 0.0], [-5.67, -7.08, 0.0, 1.42], [-6.64, -7.1, -7.08, -2.26], [-7.1, -6.64, -5.67, -4.05]]

In run 0 after 10,000 episodes every triangle is shaded, and the rarest pair has 24 returns. Cells 13 and 14 now aim right, as the first panel of Fig. 2 shows.

The returns come from an agent that keeps making random moves, so the averages estimate the action values of the ε-greedy policy itself. After 200,000 episodes run 0's average for right at cell 14 is −0.41. The exact action value is −0.37 under the ε-greedy policy around the optimal arrows, and 0.61 under the optimal policy itself. So each step makes the policy ε-greedy with respect to the action values of an ε-greedy policy. The policy improvement theorem was stated for a policy that makes one move per cell, and nothing yet says such a step cannot make the policy worse.

Why an ε-greedy step never makes the policy worse

The policy improvement theorem covers this step once it is written for a policy that picks moves at random. For a stochastic policy \pi', q_\pi\bigl(s, \pi'(s)\bigr) means the average \sum_a \pi'(a \mid s)\, q_\pi(s, a), the expected return from one move drawn from \pi' followed by \pi. If that average is at least v_\pi(s) in every cell, then v_{\pi'} \ge v_\pi in every cell.¹

Let \pi be any ε-soft policy and \pi' the ε-greedy policy with respect to q_\pi. Sutton and Barto check the theorem's condition in one chain, their equation (5.2).

The second equality splits \pi' into its floor and the remaining 1 - \varepsilon on the greedy move. The inequality replaces the maximum with a weighted average of the same four action values, with weights w(a). Each weight is at least 0 because \pi is ε-soft. The weights sum to 1 because the probabilities of \pi sum to 1 and the floor takes ε of them. A weighted average is never larger than the largest value it averages. In the last equality the floor terms cancel, and what remains is the average of q_\pi(s, a) over the moves of \pi, which is v_\pi(s).

So \pi' is no worse than \pi in any cell. The new policy is also ε-soft, so the step can be repeated.

The only resting point is the best ε-soft policy

Suppose the ε-greedy step stops changing the policy. Then \pi is ε-greedy with respect to its own action values, and in every cell its value is their ε-greedy average.

Sutton and Barto read this as the Bellman optimality equation of a different grid.¹ In that grid the agent picks a move, and with probability ε the environment replaces it with a uniformly random one before the slip. Its transition probabilities mix the real ones.

A policy \mu in the new grid moves exactly like the ε-soft policy (1 - \varepsilon)\,\mu + \varepsilon/|\mathcal{A}(s)| in the real one. Every ε-soft policy arises this way, with \mu equal to the weights w(a) from equation (5.2). So the best policy of the new grid is the best ε-soft policy of the real one, and its value \tilde v_* is the most an ε-soft policy can earn.

In the new grid's Bellman optimality equation, the random part of \tilde P does not depend on the move a, so it comes out of the max.

Here \tilde q(s, a) is the expected return after move a in the real grid, with each landing cell valued at \tilde v_*.

With v_\pi in place of \tilde v_*, \tilde q becomes q_\pi, and the equation is the one an unchanged policy satisfies. The new grid's Bellman optimality equation has only one solution, so a policy the step leaves unchanged has v_\pi = \tilde v_*. It is the best ε-soft policy.¹

best_soft builds \tilde P and runs value iteration on it, which gives \tilde v_*, and its q[s, a] is \tilde q(s, a). The second panel of Fig. 2 draws \tilde q for ε = 0.1, the action values that run 0's averages were estimating.

The argument assumes exact action values: Sutton and Barto say it “does assume that they are computed exactly”.¹ The book gives no proof for the sampled version in soft_control, which steps on averages after every episode, so for that version this lesson has only its runs. A later lesson's method, SARSA, does reach an optimal policy, with suitable step sizes, if ε shrinks toward 0 while every move is still tried infinitely often. Singh and colleagues call a policy like that GLIE, short for greedy in the limit with infinite exploration.²

How much ε costs

Table 1 uses best_soft to compare the best ε-soft value with the optimal value v_*, averaged over the 14 cells an episode can start in.

The loss grows almost in proportion to ε. At ε = 0.1 it is 1.08, about the size of one move's reward of −1. Up to ε = 0.32 the best ε-soft policy keeps the optimal arrows and differs from the optimal policy only in its random moves.

From ε = 0.33 the arrows change at cell 9. Fig. 3 shows why at ε = 0.5. Up and right from cell 9 lead mostly to cells 5 and 10, which border the pit, while left and down lead mostly to cells 8 and 13. Under the optimal policy cells 5 and 10 are worth more, 0.06 against −0.71. Under the best ε-soft policy at ε = 0.5 they are worth less, −7.08 against −6.64, so cell 9 aims left or down.

The runs land there too. With ε = 0.5, 18 of 20 runs have the best ε-soft arrows after 10,000 episodes, against 6 with ε = 0.1. All 20 have them after 100,000, each aiming cell 9 left or down. On this grid, runs with ε = 0.1 reach the optimal arrows from ordinary starts and lose 1.08 per start to their random moves. Runs with ε = 0.5 reach their resting point sooner, and the arrows they rest on are not optimal.