Decision Process Formalization

The previous lesson built the loop and used four names: state, action, transition, reward. None of them was defined. When the names do have a definition, it rests on a single condition, and that condition was already being strained in the last line of the previous lesson: when the delay class of A1 was 2, the level found had come out clean and the reward had been $-2$, yet in another episode the same class could have given 7.

This lesson sets the setup into a formal five-tuple, writes down the defining condition of the five-tuple, and measures that the condition does not hold exactly in the setup. Then it makes the cost payable: what the policy loses when the condition weakens, and how much of it comes back when a history field is added to the state.

• RL10. The setup continues unchanged from 01. Five subscribers, one crew, the same deterioration probabilities, the same reward table, the same 30-period horizon, the same discount factor 0.9 and the same seed. It is stated again that it is a setup: no number comes from a real record.
• RL11. The decision process is a five-tuple: the state set $S$, the action set $A$, the transition, the reward and the discount factor $\gamma$. In the setup $\lvert S \rvert = 243$, $\lvert A \rvert = 6$, $\gamma = 0.9$.
• RL12. The transition and the reward are each a distribution, not a single number. In the same state the same action can give different next states and different rewards.
• RL13. The defining condition: the distribution of the next state and the reward depends only on the current state and the chosen action; older states, older actions and elapsed time add nothing. This condition is called a memoryless transition.
• RL14. The condition does not hold exactly in the setup, and this lesson measures it. The environment’s hidden level vector carries the condition; the delay-class vector the agent sees is a projection of it and does not carry it.
• RL15. The form of the test: the reward samples in the same state-action cell are split in two by a history field the state does not carry. If the means diverge, the condition is broken in that cell.
• RL16. The history field is the number of the subscriber that has gone the longest without a visit. When it is added, the state space grows from 243 to 1,215.
• RL17. The upper reference is the policy that sees the hidden level directly. It is not attainable; it is printed only to bound how much the projection costs. The trace is 600 episodes, 18,000 steps.

The Five-Tuple

# environment.py — FICTIONAL. Field visit planning continues unchanged from the previous
# lesson: five subscribers in a region, one crew each period, seed 20260218.
import statistics
from collections import Counter, defaultdict

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(policy, n=600):
    """At every step, also records the FULL delay of the visited subscriber."""
    trace = []
    for k in range(n):
        env = Environment(SEED + 1000 * k)
        s = env.state()
        for _ in range(HORIZON):
            a = policy(s, env)
            delay = env.delay[a] if a < SUBSCRIBERS else -1
            s2, r = env.step(a)
            trace.append((s, a, r, s2, delay))
            s = s2
    return trace


TRACE = collect_trace(rule)
S, A = (0, 0, 1, 1, 0), 2
samples = [(r, s2, d) for s, a, r, s2, d in TRACE if s == S and a == A]
print(f"state set {3 ** SUBSCRIBERS}, action set {ACTIONS}, horizon {HORIZON}, discount {DISCOUNT}")
print(f"trace {len(TRACE)} steps; example cell {S} action {LABELS[A]}, {len(samples)} samples")
print("next-state distribution (first four):")
for s2, n in Counter(x[1] for x in samples).most_common(4):
    print(f"   {s2}  {n / len(samples):.4f}")
print("reward distribution:")
for r, n in sorted(Counter(x[0] for x in samples).items()):
    print(f"   {r:>5.1f}  {n / len(samples):.4f}")

state set 243, action set 6, horizon 30, discount 0.9
trace 18000 steps; example cell (0, 0, 1, 1, 0) action A3, 2113 samples
next-state distribution (first four):
   (1, 0, 0, 1, 0)  0.4307
   (0, 0, 0, 2, 1)  0.2239
   (0, 1, 0, 1, 0)  0.1770
   (0, 0, 0, 1, 1)  0.1046
reward distribution:
    -2.0  0.0516
     1.0  0.2347
     7.0  0.7137

The five-tuple consists of five objects. The state set $S$: all of the delay-class vectors, 243 elements. The action set $A$: six elements. The transition: to a state-action pair it assigns a distribution over next states. The reward: to the same pair it assigns a distribution over numbers. The discount factor $\gamma = 0.9$: the present weight of future rewards.

The output shows in a single cell why the transition and the reward are each a distribution. When A3 was visited in state $(0, 0, 1, 1, 0)$, 2,113 samples were collected and the next state took at least four distinct values: the most frequent is $(1, 0, 0, 1, 0)$ with a share of 0.4307. The difference comes from which of the other four subscribers changed class that period, and this is the result of a draw. The reward also spreads over three values: 7 with a share of 0.7137, 1 with 0.2347, $-2$ with 0.0516. The agent’s choice is the same; the outcome is three different numbers.

What the three reward values mean is read from the setup: 7 stands for a subscriber found faulty and repaired, 1 for one found suspicious, and $-2$ for one found clean. The deterioration probability of A3 is 0.60 per period, and delay class 1 means at least three periods have passed; so a fault is found in 0.7137 of the visits. If the same class were read for A2, the shares would move, because A2’s probability is 0.05. The reward distribution depends both on the identity of the action and on the content of the state.

The list of next states also follows from the setup. Since A3 is visited, its delay is reset to zero and its class drops to 0; the delay of the other four subscribers rises by one. An increment changes a class only at a bucket boundary, so which component the next states differ in depends on which subscribers cross a bucket boundary that period. The four rows total 0.9362; the remaining share is spread over the rarer successors.

These distributions are not a defect. The definition of the five-tuple asks not for the reward to be constant but for its distribution to be constant. The defect lies where the distribution is not constant.

Independence from History

# history.py — Test: the reward samples in the same (state, action) cell are split in two
# by a history field the state does not carry. If the means diverge, the reward
# does not sit on a single distribution in that cell.
cell = defaultdict(list)
for s, a, r, s2, d in TRACE:
    cell[(s, a)].append((r, d))

print(f"{'state':<17}{'action':<7}{'count':>7}{'mean reward':>12}"
      f"{'delay 3':>11}{'delay 4+':>12}{'diff':>8}")
for (s, a), v in sorted(cell.items(), key=lambda kv: -len(kv[1]))[:5]:
    d3 = [r for r, d in v if d == 3]
    d4 = [r for r, d in v if d >= 4]
    print(f"{str(s):<17}{LABELS[a]:<7}{len(v):>7}"
          f"{statistics.mean(r for r, _ in v):>12.3f}"
          f"{statistics.mean(d3):>11.3f}{statistics.mean(d4):>12.3f}"
          f"{statistics.mean(d4) - statistics.mean(d3):>8.3f}")

state            action   count mean reward    delay 3    delay 4+    diff
(0, 0, 1, 1, 0)  A3        2113       5.127      4.518       5.944   1.425
(1, 0, 0, 1, 0)  A1        1945       1.540      1.198       2.436   1.238
(0, 1, 0, 1, 0)  A2        1899      -1.455     -1.502      -1.341   0.162
(1, 0, 0, 0, 1)  A1        1659       1.204      1.132       2.154   1.022
(0, 1, 0, 0, 1)  A2        1613      -1.481     -1.530      -0.971   0.558

The design of the test is as follows. Delay class 1 means “3, 4 or 5 periods have passed since the last visit”; three values are folded into a single class. The state is what remains after this folding, so the agent cannot see whether the delay is 3 or 5. The environment can, though: the deterioration is redrawn every period, so a subscriber that has waited 5 periods is more likely to be found faulty than one that has waited 3.

The table turns this into a number. In the most frequent cell — state $(0, 0, 1, 1, 0)$, action A3, 2,113 samples — the mean reward is 5.127. When the same cell is split by delay, it comes out as 4.518 and 5.944: a difference of 1.425. In five cells out of five the difference is positive, the smallest 0.162, the largest 1.425. With the state and the action held fixed, the mean of the reward shifts according to a piece of history the state does not carry. The condition does not hold exactly in this setup, and the amount by which it fails can be read in reward units.

That the difference varies from cell to cell also deserves reading. The two smallest differences, 0.162 and 0.558, are in the cells where A2 is visited; A2’s deterioration probability is 0.05, so waiting one more period hardly moves its level, and the folded information carries almost nothing. The largest difference is at A3, the subscriber whose probability is 0.60. So how much information the projection throws away is not a fixed number: the same bucket of the state hides a lot for a fast-deteriorating subscriber and little for a slow one.

Two things should not be confused. The environment itself is memoryless: the hidden level vector is enough to determine the next level and the reward, and what came before it adds nothing. What is broken is not the environment but the agent’s state definition. The delay-class vector is a coarse projection of the hidden vector, and the information discarded in the projection does not vanish because it was discarded — it stays in the history and from there moves the reward. This is exactly the form met in practice: the five-tuple usually holds in the environment and does not hold in the observation the agent is handed.

The Cost of the State Definition

# definition.py — The same rule, three state definitions. The text of the rule does not change; what changes is
# the field the rule can read.
def rule_with_history(s, env):
    """History field: the number of the subscriber that has gone the longest without a visit."""
    top = max(s)
    if top == 0:
        return SUBSCRIBERS
    candidates = [i for i in range(SUBSCRIBERS) if s[i] == top]
    longest = max(range(SUBSCRIBERS), key=lambda i: env.delay[i])
    return longest if longest in candidates else candidates[0]


def hidden_policy(s, env):
    """Unattainable upper reference: reads the environment's hidden level vector directly."""
    top = max(env.level)
    return SUBSCRIBERS if top == 0 else env.level.index(top)


print(f"{'state definition':<34}{'space':>7}{'return':>9}")
for name, pol, space in (("delay class", rule, 243),
                         ("delay class + history field", rule_with_history, 1215),
                         ("hidden level (upper reference)", hidden_policy, 243)):
    print(f"{name:<34}{space:>7}{statistics.mean(run(pol)):>9.3f}")

state definition                    space   return
delay class                           243   20.621
delay class + history field          1215   23.148
hidden level (upper reference)        243   29.053

The baseline against which the three rows are read is from the previous lesson and is not re-measured here: random action 10.432, never dispatching the crew 0.000. All three rows are above this baseline; the differences among them are small beside the difference from the baseline, and what this lesson measures is that small difference.

In all three rows the rule is the same: go to the subscriber with the largest delay class. The only thing that changes is what the rule can look at in a tie. In the first row, when the classes are tied the subscriber with the smaller number is chosen, because there is no other information, and the return is 20.621. In the second row a single field is added to the state — the number of the subscriber that has gone the longest without a visit — and the tie is broken by that field. The return becomes 23.148: +2.527, that is a 12.3% increase, for a single field.

The third row bounds the size of the loss. The policy that reads the hidden level directly gets 29.053. The total gap the projection opens is $29.053 - 20.621 = 8.432$; the history field closes 2.527 of it, that is 0.300. The remaining 5.905 cannot be read from the delay, because deterioration is a draw and two subscribers with the same delay can be at two different levels.

The cost of the field is written in the column. The state space grows from 243 to 1,215, fivefold. Because this lesson uses a hand-written rule, the cost is not visible; the rule reads the state and keeps no table. In the next two lessons one number per state will be learned, and then the difference between 243 and 1,215 will turn directly into learning speed: for a cell to be filled, that cell has to be visited. Enriching the state definition is not free; the price paid for approaching memorylessness is that each state is seen more rarely.

Summary

• The decision process is a five-tuple: the state set (243 elements), the action set (6 elements), the transition, the reward and the discount factor (0.9). The transition and the reward are each a distribution, not a number.
• In a single cell — state $(0, 0, 1, 1, 0)$, action A3 — the next state spreads over four distinct values with shares 0.4307, 0.2239, 0.1770 and 0.1046, and the reward over $-2$, 1 and 7 with shares 0.0516, 0.2347 and 0.7137.
• The defining condition is that the distribution of the next state and the reward depends only on the current state and action; this is called a memoryless transition.
• The condition does not hold exactly in the setup: in the same cell the mean reward is 4.518 when the delay is 3 and 5.944 when the delay is 4 and above; the difference is 1.425 and in the same direction in five cells out of five.
• What is broken is not the environment but the agent’s state definition. The hidden level vector carries the condition, and the delay-class vector is a coarse projection of it.
• The same rule gets 20.621 under the 243-state definition, 23.148 under the 1,215-state definition with a history field added, and 29.053 under the upper reference that sees the hidden level; the history field closes 0.300 of the gap.

Next Step

In these two lessons the policy was written by hand: what the rule would do was known from the start and no number was learned from data. When a policy has to be learned, a new contradiction arises. To learn, one has to see what the actions return, to see what an action returns one has to try that action, and every trial is deducted from that period’s return. As seen in the previous lesson, in a step the agent learns only the outcome of the action it chose; about the five actions it did not choose it hears nothing. The next lesson measures this contradiction: the trade-off between repeating the best-known action and trying the unknown is counted as how many steps are lost for how many steps gained — and it is written down which action an agent that does no exploration never tries at all.