Value Functions and Action Value

In the previous lesson the number kept in the table was the immediate reward: what an action brought in a state in that period. This number cannot capture the whole effect of a visit. The repaired subscriber stays clean for a few more periods, the neglected subscriber costs more a few periods later, and which subscriber we send the crew to today determines which options we will have tomorrow. In the first lesson the return was defined as the discounted total of thirty periods; the number in the table was keeping a single period.

This lesson turns the number in the table from the immediate reward into the return. In doing so it does not use the environment’s deterioration probabilities or the reward table — it behaves as if none of that information were at hand and works only from lived quadruples. Then it reads the third number of the course on the table: how many cells are still empty at the end of 9,000 steps.

• RL26. The setup, horizon, discount factor, measure and seed continue unchanged from 01–03. 243 states, 6 actions, an episode of 30 periods, discount factor 0.9, a measurement of 300 episodes.
• RL27. Learning requires no model. The deterioration probabilities and the reward table are both treated as unknown; all that is at hand are lived (state, action, reward, next state) quadruples.
• RL28. The value of a state is the expected sum of the discounted rewards the policy will collect starting from that state. The reward is one period long, the value carries the whole future.
• RL29. The update has the form of a temporal difference: $r + \gamma V(s') - V(s)$ is computed and added to the table with a step size of 0.1. The end of the episode is not awaited; an update is made at every step.
• RL30. The trace is collected once, and the table is swept 40 times over the trace. The data budget is fixed at 9,000 steps; the number of sweeps is a computation budget and brings no new data.
• RL31. Value is defined over an infinite horizon, whereas the measurement is cut off at 30 periods. The difference between the two numbers comes from the tail of 0.0424, the thirtieth power of the discount factor.
• RL32. The action value is the value of a state-action pair; in the target the best action value of the next state is used, so that the table looks for something better than the policy that collected the data.
• RL33. The initial value of the table is 0.0. A cell that was never updated stays at this value and greedy selection counts it as a candidate too; an empty cell is read not as absence but as zero.
• RL34. The measure is three numbers: how many of the 1,458 cells were updated, how many were never updated, and how many of the filled ones were filled with fewer than five samples.

The Value of a State

# environment.py — FICTIONAL. Field visit planning continues unchanged from the previous three
# lessons: five subscribers, one crew each period, seed 20260218.
import statistics

SEED, M32 = 20260218, 0xFFFFFFFF
SUBSCRIBERS, PAYOFF, COST = 5, (0, 3, 9), 2
DETERIORATION = (0.30, 0.05, 0.60, 0.15, 0.45)
LABELS = ("A1", "A2", "A3", "A4", "A5", "idle")
ACTIONS, HORIZON, DISCOUNT = SUBSCRIBERS + 1, 30, 0.9


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


class Environment:
    def __init__(self, seed):
        self.draw = rng(seed)
        self.level, self.delay = [0] * SUBSCRIBERS, [0] * SUBSCRIBERS
        for i in range(SUBSCRIBERS):
            self.delay[i] = int(self.draw() * 6)
            for _ in range(self.delay[i]):
                if self.level[i] < 2 and self.draw() < DETERIORATION[i]:
                    self.level[i] += 1

    def state(self):
        return tuple(min(2, x // 3) for x in self.delay)

    def step(self, a):
        reward = 0.0
        if a < SUBSCRIBERS:
            reward = PAYOFF[self.level[a]] - COST
            self.level[a] = 0
            self.delay[a] = 0
        for i in range(SUBSCRIBERS):
            if i != a:
                self.delay[i] += 1
                if self.level[i] < 2 and self.draw() < DETERIORATION[i]:
                    self.level[i] += 1
        return self.state(), reward


def run(policy, n=300):
    G = []
    for k in range(n):
        env = Environment(SEED + 1000 * k)
        s, g, c = env.state(), 0.0, 1.0
        for _ in range(HORIZON):
            s, r = env.step(policy(s, env))
            g, c = g + c * r, c * DISCOUNT
        G.append(g)
    return G


def rule(s, env):
    """Visit the subscriber with the largest delay class; if all are 0, do not dispatch the crew."""
    top = max(s)
    return SUBSCRIBERS if top == 0 else s.index(top)


def collect_trace(explore, n=300, seed=SEED + 11):
    """Behavior policy: without discrimination at the exploration rate, the rule otherwise."""
    draw = rng(seed)
    trace = []
    for k in range(n):
        env = Environment(SEED + 1000 * k)
        s = env.state()
        for _ in range(HORIZON):
            a = int(draw() * ACTIONS) if draw() < explore else rule(s, env)
            s2, reward = env.step(a)
            trace.append((s, a, reward, s2))
            s = s2
    return trace


TRACE = collect_trace(0.00)
STARTS = [Environment(SEED + 1000 * k).state() for k in range(300)]
V = {}
for s, a, r, s2 in TRACE:
    V.setdefault(s, 0.0)
    V.setdefault(s2, 0.0)
print(f"trace {len(TRACE)} steps, {len(V)} states in the table")
print(f"{'sweep':>8}{'mean of V(s0)':>19}{'largest update':>21}")
for sweep in range(1, 41):
    largest = 0.0
    for s, a, r, s2 in TRACE:
        delta = 0.1 * (r + DISCOUNT * V[s2] - V[s])
        V[s] += delta
        largest = max(largest, abs(delta))
    if sweep in (1, 2, 5, 10, 20, 40):
        print(f"{sweep:>8}{statistics.mean(V[s] for s in STARTS):>19.3f}{largest:>21.4f}")
ranked = sorted(V.items(), key=lambda kv: -kv[1])
print("highest three states: " + ", ".join(f"{s} {v:.3f}" for s, v in ranked[:3]))
print("lowest three states:  " + ", ".join(f"{s} {v:.3f}" for s, v in ranked[-3:]))

trace 9000 steps, 103 states in the table
   sweep      mean of V(s0)       largest update
       1             12.632               2.4467
       2             15.944               2.3325
       5             19.119               1.8443
      10             20.608               1.4240
      20             21.345               1.2717
      40             21.562               1.2700
highest three states: (1, 0, 1, 0, 2) 29.060, (1, 0, 1, 2, 1) 29.030, (0, 0, 2, 1, 2) 28.964
lowest three states:  (1, 2, 0, 0, 0) 17.801, (0, 2, 0, 0, 1) 16.573, (0, 2, 0, 1, 0) 16.075

The whole update is in one line: $V(s) \leftarrow V(s) + \alpha\,[\,r + \gamma V(s') - V(s)\,]$. The quantity inside the square brackets is the temporal difference: on one side the reward actually received in that step and the current estimate of the next state, on the other the current estimate of the present state. The two estimates belong to successive times, and the inconsistency between them is used to correct the table. The environment’s deterioration probabilities appear nowhere; the code reads only lived quadruples. This is what it means for learning to require no model.

The number settles into place step by step. In the first sweep the mean value of the starting states is 12.632, because the information has so far spread only one step backward. At the tenth sweep it is 20.608, at the fortieth 21.562. The independent measurement is at hand: the 30-period return of the same rule, measured over 300 episodes, is 20.621. The two numbers are not the same, and they should not be. Value is defined over an infinite horizon, while the measurement is cut off at 30 periods; the weight of the cut-off tail is $\gamma^{30} = 0.0424$. When the tail is taken into account, $20.621 / (1 - 0.0424) = 21.534$ comes out, and the difference from the learned 21.562 is 0.028. The table, knowing no probabilities, reproduced the measured return on its own.

The right-hand column does not fall to zero, and it should not. Since the step size is a fixed 0.1, the table does not freeze; as the rewards arriving at the same cell vary among $-2$, 1 and 7, the estimate oscillates around the mean. The largest update stops at 1.2700; that is, the table has settled at a point but its jitter continues.

The bottom two lines show what the value says. The highest state is $(1, 0, 1, 0, 2)$: A3 and A5 have been kept waiting, both fast-deteriorating subscribers, and A5 has moreover passed six periods. In this state there is a lot of work awaiting the crew and its value is 29.060. The lowest state is $(0, 2, 0, 1, 0)$: the longest-waiting subscriber is A2, whose deterioration probability is 0.05, so its waiting means almost nothing — the rule sends the crew there all the same. Its value is 16.075, and in all three of the lowest states the longest-waiting subscriber is A2. The gap of 12.985 between them measures how different a future the same policy sees depending on the state it starts in.

The Value of an Action

# action_value.py — The same trace, the same form of temporal difference; what changes is that the table is keyed
# by the state-action pair instead of the state, and the best action in the target.
def q_sweep(trace, rounds=40, alpha=0.1, initial=0.0):
    Q, N = {}, {}
    for s, a, r, s2 in trace:
        for x in (s, s2):
            Q.setdefault(x, [initial] * ACTIONS)
            N.setdefault(x, [0] * ACTIONS)
        N[s][a] += 1
    for _ in range(rounds):
        for s, a, r, s2 in trace:
            Q[s][a] += alpha * (r + DISCOUNT * max(Q[s2]) - Q[s][a])
    return Q, N


def greedy_policy(Q, initial=0.0):
    def pol(s, env):
        q = Q.get(s, [initial] * ACTIONS)
        return max(range(ACTIONS), key=lambda i: q[i])
    return pol


Q, N = q_sweep(TRACE)
filled = [(s, i) for s in N for i in range(ACTIONS) if N[s][i] > 0]
print(f"updated cells {len(filled)}/1458, never updated {1458 - len(filled)}")
print(f"return of the policy read from the table "
      f"{statistics.mean(run(greedy_policy(Q))):.3f}")
example = sorted(N, key=lambda s: -sum(N[s]))[0]
print(f"example state {example}: " + ", ".join(
    f"{LABELS[i]} {Q[example][i]:.3f} (n={N[example][i]})" for i in range(ACTIONS)))

updated cells 103/1458, never updated 1355
return of the policy read from the table 20.621
example state (0, 0, 1, 1, 0): A1 0.000 (n=0), A2 0.000 (n=0), A3 23.183 (n=1057), A4 0.000 (n=0), A5 0.000 (n=0), idle 0.000 (n=0)

The value function says how good a state is but does not say which action to choose; to say that, the environment would have to know which action leads where, and that information is not at hand. The action value closes this gap: the table is keyed not by the state but by the state-action pair, and the choice is read directly from the largest in the row. The $\max$ in the target, on the other hand, forces the table to look for something better than the policy that collected the data: in the next state the value of the action that looks best is used, not of the one that policy would take.

The example row is a summary of the whole lesson. State $(0, 0, 1, 1, 0)$ was lived 1,057 times and only one of its six cells is filled: 23.183 for A3. The other five are 0.000 and the sample count beside them is zero. These zeros do not say “this action is bad”, they say “this action was never tried” — but the table does not tell the two apart, because whatever the initial value is, that is what sits in an empty cell.

The return line closes the result: the policy read from the table gets 20.621, exactly the number of the rule that produced it. This is not surprising, it is inevitable. The rule is deterministic, it chooses a single action in every state it sees, so only 103 of the 1,458 cells are updated, and in each state the single filled cell automatically becomes the largest. A table fed by its own data can recommend nothing other than the policy that produced it. In the first lesson of the course the number 103 was printed as an observation; here it turns directly into a ceiling.

The Empty Places of the Table

# coverage.py — As exploration is added to the behavior policy, how many cells of the table
# get filled, and how many of the filled cells stay thin.
print(f"{'rate':>6}{'updated':>13}{'empty':>9}{'thin (<5)':>11}"
      f"{'states':>8}{'return':>9}")
for explore in (0.00, 0.05, 0.20, 0.40, 1.00):
    trace = collect_trace(explore)
    Qk, Nk = q_sweep(trace)
    d = [(s, i) for s in Nk for i in range(ACTIONS) if Nk[s][i] > 0]
    thin = sum(1 for s, i in d if Nk[s][i] < 5)
    print(f"{explore:>6.2f}{len(d):>13}{1458 - len(d):>9}{thin:>11}"
          f"{len(Nk):>8}{statistics.mean(run(greedy_policy(Qk))):>9.3f}")

  rate      updated    empty  thin (<5)  states   return
  0.00          103     1355         47     103   20.621
  0.05          222     1236        122     114   15.176
  0.20          488      970        307     165   24.317
  0.40          749      709        437     196   21.703
  1.00         1237      221        468     235   24.419

As exploration is added to the behavior, the filled part of the table grows: from 103 to 1,237. The cells left entirely empty fall from 1,355 to 221. The return column, however, does not move in one direction — 20.621, then 15.176, then 24.317, then 21.703, then 24.419. Coverage grows, the result does not improve steadily.

The comparison baselines continue from the first lesson: the random policy 10.432, the hand-written rule 20.621. All five rows are above random but only three pass the hand-written rule, and the 0.05 row falls below the rule at 15.176. Adding a little exploration to the rule’s data can directly spoil the result.

The answer is in the fourth column. The number of cells filled with fewer than five samples rises from 47 to 468; at an exploration rate of 0.20, 307 of the 488 filled cells, that is 0.629, are thin. The number a thin cell carries is the mean of one or two draws, and the $\max$ in the target brings exactly these numbers to the front: a cell that came out high by mistake is both chosen in its own state and leaks into the target of the states neighboring it. Coverage alone is not a measure of quality; besides how many cells were filled, how many samples fell on each cell must also be written down.

This is the form of the course’s rule on the table. The number 24.317 holds on 488 cells, and on 307 of them it rests on fewer than five observations; concerning the 970 cells the only thing the table says is 0.000, and this is not information, it is a starting value. A table that does not write down the data it collected counts as unmeasured.

Summary

• The value of a state is the expected sum of the discounted rewards the policy will collect starting from that state; the temporal difference update learns this number from the difference of two successive estimates and requires none of the environment’s probabilities.
• Over a 9,000-step trace, in 40 sweeps the mean value of the starting states rises from 12.632 to 21.562; the independently measured 30-period return is 20.621 and, with the tail correction, comes to 21.534, a difference of 0.028.
• With a fixed step size the table does not freeze: since the reward varies between $-2$ and 7 in the same cell, the largest update keeps jittering at 1.2700.
• State values spread between 29.060 and 16.075; in the highest state two fast-deteriorating subscribers are waiting, in the lowest a single subscriber with a deterioration probability of 0.05.
• Of the 1,458 cells of the action value table fed by the rule’s own data, 103 are updated, 1,355 are never touched, and the policy read from the table gives exactly 20.621: a table fed by its own data can recommend nothing other than the policy that produced it.
• As exploration is added, the filled cells rise from 103 to 1,237 but the thin cells with fewer than five samples also rise from 47 to 468; the return does not move in one direction, because choosing the best action in the target carries the noise of the thin cells to the front.

Next Step

For four lessons the table carried everything: 243 states, 1,458 cells, all in memory, all updatable one by one. This is thanks to the smallness of the number of states, and that smallness was not free. In the second lesson, when a single history field was added to the state, the return rose from 20.621 to 23.148; the same addition carries the state space from 243 to 1,215 and the table from 1,458 cells to 7,290 cells. With the data budget staying at 9,000 steps, even if every step fell on a different cell there would be 1.23 samples per cell — yet in this lesson 307 of 488 cells were already counted thin with fewer than five samples. If the number of subscribers went from five to eight, the state space would be 6,561 and the table 59,049 cells. As the table grows it does not fill, and a table that does not fill decides with zeros. The next lesson leaves the table: instead of keeping a separate number for each cell, it uses a function that takes the state as input and computes the value, and its first job is to make similar states learn from one another.