Agent, Environment and Reward

Across thirty-eight lessons, the previous course kept a single arrangement: the model was given an input, the model produced an output, and the correctness of the output was read either from a label already in hand or from a criterion that described the output. The input was independent of the model’s decision. Whatever the model said, the next row, the next sentence, the next image did not change; the set was there from the start and stayed there.

This course steps outside that arrangement. Here the result of a decision becomes visible only after the decision is made, and the decision itself changes the next input. Visiting a subscriber reveals its condition and at the same time removes that condition; a subscriber that is not visited keeps deteriorating. In such a setup a “performance” number cannot be read without writing down which data it was measured on, because the policy itself collected the data. The job of this lesson is to build the loop and put the course’s three numbers in place: the baseline, the method’s number, the collected data.

• RL1. The setup is field visit planning, and it is generated. In one region of the regional measurement network setup there are five subscribers (A1–A5). No number comes from a real record; all of them are generated inside the lesson with seed 20260218.
• RL2. One crew goes out each period. The action set has six elements: visiting one of the five subscribers, or not dispatching the crew at all.
• RL3. A subscriber’s field condition is hidden and has three levels — clean, suspicious, faulty. A visit reveals this level, and it resets because the fault is repaired.
• RL4. A subscriber that is not visited deteriorates. Each period, with a probability specific to that subscriber, its level rises by one; the probabilities from A1 to A5 are 0.30, 0.05, 0.60, 0.15 and 0.45.
• RL5. The state the agent sees is the delay class. For each subscriber, the number of periods since the last visit is split into three buckets: 0–2, 3–5, and 6 and above. The state space has $3^5 = 243$ elements.
• RL6. The reward is what the visit finds. The value of the level found is 0, 3 and 9 respectively, and every visit costs 2 units. If the crew is not dispatched, the reward is exactly 0.
• RL7. An episode is 30 periods and the discount factor is 0.9. The return is the discounted sum of the rewards in the episode; a near-term reward outweighs a distant one.
• RL8. The baseline is random action. Never dispatching the crew is also measured, but it cannot be the baseline: its return is zero by definition, and zero is the starting point of the measure, not of choosing actions.
• RL9. The measure is the mean return over 300 episodes and larger is better. The episode seeds are fixed; all policies see the same 300 starting points.

The Environment, Action and Reward Loop

# environment.py — FICTIONAL. Field visit planning: five subscribers in a region
# and one crew going out each period. All numbers are generated, none comes
# from a record.
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):
    """Hand-written generator; the seed is fixed, so the output is the same on every run."""
    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:
    """The field level is hidden; the state the agent sees is the delay class."""

    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 episode(policy, seed, trace=None):
    env = Environment(seed)
    s, G, c = env.state(), 0.0, 1.0
    for _ in range(HORIZON):
        a = policy(s, env)
        s2, r = env.step(a)
        if trace is not None:
            trace.append((s, a, r, s2))
        G, c, s = G + c * r, c * DISCOUNT, s2
    return G


def run(policy, n=300, trace=None):
    return [episode(policy, SEED + 1000 * k, trace) for k in range(n)]


def random_policy(seed):
    draw = rng(seed)
    return lambda s, env: int(draw() * ACTIONS)


env = Environment(SEED)
draw = rng(SEED + 7)
print("period  state            action  reward  contribution to return")
G, c = 0.0, 1.0
for t in range(8):
    s, a = env.state(), int(draw() * ACTIONS)
    _, reward = env.step(a)
    G, part = G + c * reward, c * reward
    print(f"{t:>4}   {str(s):<17}{LABELS[a]:<6}{reward:>6.1f}{part:>13.3f}")
    c *= DISCOUNT
print(f"return over eight periods {G:.3f}")

period  state            action  reward  contribution to return
   0   (1, 0, 0, 1, 0)  A5       1.0        1.000
   1   (2, 0, 0, 1, 0)  A3       7.0        6.300
   2   (2, 0, 0, 2, 0)  A1      -2.0       -1.620
   3   (0, 1, 0, 2, 0)  A2      -2.0       -1.458
   4   (0, 0, 0, 2, 1)  A3       7.0        4.593
   5   (0, 0, 0, 2, 1)  A5       7.0        4.133
   6   (1, 0, 0, 2, 0)  A4       1.0        0.531
   7   (1, 1, 0, 0, 0)  A3       7.0        3.348
return over eight periods 16.828

The eight rows carry the whole loop. The agent is the side that directs the crew, and the environment is the side that holds the subscribers and their deterioration. The agent sees a state, chooses an action, and the environment returns a reward and transitions to a new state. In the third period A1 is visited and the reward comes out as $-2$: the crew went, the subscriber was found clean, and the cost was written off for nothing. In the eighth period A3 is visited and the reward is 7, because the faulty level was found and repaired.

The reward covers a single step, and a single step is not what the agent wants. The return is the discounted sum of the rewards received over an episode: $G = \sum_{t} \gamma^{t} r_t$, where $\gamma = 0.9$. The right-hand column shows that the same 7 is counted as 4.593 in the fifth period and 3.348 in the eighth. The discount factor is a choice, and the choice becomes part of the measure: the later the same gain arrives, the less it counts. The return over eight periods is 16.828.

One detail of the third period is the subject of a later lesson. In state $(2, 0, 0, 2, 0)$ the delay class of A1 is 2, meaning it has gone at least six periods without a visit, yet the level found is clean and the reward is $-2$. The delay class does not tell the subscriber’s real level; it is only correlated with it.

The Baseline and the Policy’s Number

# policy.py — Same environment, same 300 episode seeds, same horizon; the policy changes.


def idle_policy(s, env):
    """The crew is never dispatched: its return is zero by definition."""
    return SUBSCRIBERS


def rule_policy(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)


print(f"{'policy':<26}{'return':>9}{'lowest':>10}{'highest':>11}")
for name, pol in (("never dispatch", idle_policy),
                  ("random action", random_policy(SEED + 7)),
                  ("go to largest delay", rule_policy)):
    g = run(pol)
    print(f"{name:<26}{statistics.mean(g):>9.3f}{min(g):>10.3f}{max(g):>11.3f}")

policy                       return    lowest    highest
never dispatch                0.000     0.000      0.000
random action                10.432    -6.887     31.159
go to largest delay          20.621     2.370     41.179

A policy is the rule that maps a state to an action. The three policies see the same 300 starting points and give three different numbers. The first never dispatches the crew: its reward is 0 in every period, so its return is exactly 0 as well, and even its lowest and highest episodes are 0. The second picks one of the six actions without discrimination and gets 10.432. The third is a one-line hand-written rule — it learns nothing, it only reads the state — and gets 20.621.

Random action is chosen as the baseline. Although never dispatching the crew gives a lower number, it cannot be the baseline, because its return is the zero point of the measure: a policy exceeding it says not that the policy learned to choose actions, only that moving is better than standing still in this setup. Random action, on the other hand, is a procedure that chooses actions but bases its choice on no information, and this is what makes the comparison meaningful. Both baselines are printed, because the 10.432 gap between them measures how generous the setup itself is.

Where does the rule’s 10.189 margin over random action come from? The random policy treats the five subscribers equally, yet A2 deteriorates with probability 0.05 per period; a visit to it mostly writes $-2$. The rule reduces wasted visits by going to the subscriber with the large delay. The lowest-episode numbers show this too: the worst episode of the random policy is $-6.887$, while the worst of the rule is $+2.370$.

The highest-episode numbers, on the other hand, say the opposite and deserve to be read. The random policy can reach 31.159 in one episode; the rule’s best episode is 41.179. The two distributions overlap, so someone looking at a single episode could have seen the random policy as better than the rule. This is why the mean is taken over 300 episodes: an episode’s return is affected both by the starting state and by the draw of the deterioration, and what separates the two policies shows up not in a single episode but in the mean.

Collected Data

# data.py — The third number: because the policy collects its own data, how much
# of the state space it sees depends on the policy itself.
from collections import Counter

seen = {}
for name, pol in (("random action", random_policy(SEED + 7)),
                  ("go to largest delay", rule_policy)):
    trace = []
    run(pol, 300, trace)
    count = Counter(x[0] for x in trace)
    seen[name] = set(count)
    pairs = {(x[0], x[1]) for x in trace}
    share = sum(n for _, n in count.most_common(3)) / len(trace)
    print(f"{name:<26} states {len(count):>4}/243  pairs {len(pairs):>5}/1458  "
          f"steps {len(trace)}  top-three share {share:.4f}")

RND, RULE = seen["random action"], seen["go to largest delay"]
print(f"seen by random, not by the rule {len(RND - RULE)}, "
      f"reverse {len(RULE - RND)}, seen by neither {243 - len(RND | RULE)}")

print("\nreward each of the six actions would give in the same period (only the setup owner can see this):")
for a in range(ACTIONS):
    env2 = Environment(SEED)
    s0 = env2.state()
    print(f"  {LABELS[a]:<7}{env2.step(a)[1]:>6.1f}")
print(f"initial state {s0}; the agent sees only one of these six rows")

random action              states  234/243  pairs  1251/1458  steps 9000  top-three share 0.0319
go to largest delay        states  103/243  pairs   103/1458  steps 9000  top-three share 0.3327
seen by random, not by the rule 131, reverse 0, seen by neither 9

reward each of the six actions would give in the same period (only the setup owner can see this):
  A1       -2.0
  A2       -2.0
  A3        1.0
  A4       -2.0
  A5        1.0
  idle      0.0
initial state (1, 0, 0, 1, 0); the agent sees only one of these six rows

The top two rows are this course’s distinguishing number. The two policies spend the same budget: 300 episodes, 30 periods per episode, 9,000 steps in total. The data they collect is not the same. The random policy sees 234 of the 243 states and 1,251 of the 1,458 state-action pairs. The rule, whose return is twice as large, sees only 103 states and 103 pairs — it has not a single observation about 140 states and 1,355 pairs.

The two numbers are equal because the rule is deterministic: in every state it sees, it chooses a single action, so it never learns what the other five actions in that state would give. The policy with the better return collects narrower data. This is a direct consequence of the course’s rule: a system that does not write down the data it collected counts as unmeasured, because the number 20.621 holds on a slice of 103 states, and what the policy would do outside that slice has not been measured.

The right-hand column reads the same narrowing in terms of concentration. The three states the random policy visits most hold only 0.0319 of the 9,000 steps, so its visits spread almost flat across the state space. The three states the rule visits most hold 0.3327 of the steps: one in every three steps is spent in one of the same three states. The third row closes the relationship. The random policy has also seen all 103 states the rule saw, while the reverse is false for 131 states — so the better policy’s dataset is a proper subset of the baseline’s dataset. Neither of them ever saw nine states.

This third number had no counterpart in the previous six courses. There the set was the same whatever was done; a model passing the baseline did not change the set it was measured on. Here, the moment the policy changes the set changes too, so when the returns of two policies are compared, two different datasets are being compared as well. When a policy has to be learned later, this narrowing becomes a problem directly: a procedure with no observation of 1,355 pairs can never learn whether one of those pairs is better.

The bottom block gives the difference from supervised learning as a single ratio. In the initial state $(1, 0, 0, 1, 0)$ the rewards the six actions would give are $-2$, $-2$, $1$, $-2$, $1$ and $0$. These six rows can be printed only because the setup owner can build the environment six times from the same seed; the agent chooses one action and learns only one row, and the others close. In supervised learning every example brought its correct answer with it; here, at every step, one of the six outcomes, that is one in six, becomes visible, and what is more, the outcome of the five actions not chosen cannot be asked for afterwards either, because the environment is now in a different state.

Summary

• The agent sees the state, chooses an action, the environment returns a reward and moves to a new state; the return is the sum of the rewards in an episode discounted with a discount factor of 0.9, and in the example it is 16.828 over eight periods.
• The return of the policy that never dispatches the crew is 0.000 by definition; the baseline is not this but the random action policy, which chooses actions but bases its choice on no information: 10.432.
• The one-line hand-written rule that reads the state gets 20.621; the source of the difference is the reduction in wasted visits to the subscriber whose deterioration probability is 0.05.
• On the same 9,000-step budget, the random policy sees 234 of the 243 states and the rule sees only 103; because it is deterministic, the number of state-action pairs the rule sees also stays at 103.
• The rule’s dataset is a proper subset of the baseline’s: the rule never sees the 131 states the random policy sees, the reverse never happens, and 0.3327 of the rule’s steps pass in only three states.
• At every step the agent learns the outcome of only one of the six actions; the reward of the five actions not chosen cannot be asked for afterwards, because the environment has changed in the meantime.

Next Step

In this lesson state, action, transition and reward were used by name, but none of them was defined. The one thing the definition requires carries all the numbers at once: how the environment moves to the next state and which reward it gives must depend only on the current state and the chosen action. A row printed in this lesson was already straining this condition: when the delay class of A1 was 2, the level found was clean and the reward was $-2$, yet in another episode the same class could have given 7. The next lesson sets the setup into a formal five-tuple, writes down what the condition says, and counts what is lost when the condition is broken: how many more points of return the same hand-written rule gets when a history field is added to the state.