Function Approximation and Experience Replay

The previous lesson learned the action value in a table and counted how many cells of the table were never updated. This lesson treats that number as a limit. The problem of the table is not memory; it is that each cell is learned only when that cell is visited, and that no information is shared between two neighboring states. What is learned in state (1,0,2,0,1) does not carry over to state (1,0,2,0,0).

The table is replaced by a function approximation: a small network that takes the state as input and returns a number for each action. The network produces an answer even in a state it has never seen, because it carries over what it learned from similar states. The price is that learning is no longer stable, and what this lesson measures is where the instability comes from and how much experience replay corrects it.

• RL41. The environment is the setup built in 01 and continues here as it was: five subscribers, one crew per period, horizon 30, discount factor 0.9. The state the agent sees is the delay class; the deterioration level is hidden.
• RL42. The state is the quintuple of the five delay classes, that is $3^5 = 243$ states; there are six actions: going to one of the five subscribers or not dispatching a crew. The state–action pairs number 1,458.
• RL43. The measurement is made on the same 300 episodes as in 01, so the numbers of this lesson can be compared directly with the numbers of the previous lessons. The return is the sum of the discounted rewards.
• RL44. There are two baselines: never dispatching a crew and a random action. The first is zero by definition and gives the value of inaction, the second that of unordered effort. The rule policy of 01 is written next to them, because it is the number the learning method has to beat.
• RL45. The table is learned over 300 episodes with the temporal difference update; the exploration rate falls linearly from 0.60 to 0.05. With a constant and low exploration the first action tried permanently pulls ahead, so the rate is applied as a decreasing one.
• RL46. The network comes as input from the Deep Learning course and its procedure is not repeated here: five inputs, ten hidden units, six outputs; the hidden layer is hyperbolic tangent, the output layer is linear.
• RL47. The target of the network is the reward divided by ten. Because the action is determined by choosing the largest output, this scale does not change the policy; it only brings the targets closer to the output range of the network.
• RL48. Every measure that uses the network is printed with two runs, and only the training seed changes between the runs; this seed determines together the initial values of the network, the realization of the environment in the training episodes, and the exploration choices. The evaluation episodes are the same in every run.

The Place the Table Cannot Fill

The first block rebuilds the environment, prints three comparison numbers and counts how full the table is.

# table.py — FICTIONAL. The setup built in lesson 01: five subscribers, one crew each period.
import math
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)
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:
    """The deterioration 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 run(policy, n=300):                     # the same 300 episodes as in 01, the same horizon
    returns = []
    for k in range(n):
        env = Environment(SEED + 1000 * k)
        s, total, factor = env.state(), 0.0, 1.0
        for _ in range(HORIZON):
            s2, r = env.step(policy(s))
            total, factor, s = total + factor * r, factor * DISCOUNT, s2
        returns.append(total)
    return statistics.mean(returns)


def train_table(seed, episodes=300, rate=0.20):
    Q, counts, draw = {}, {}, rng(seed)
    for b in range(episodes):
        explore = 0.60 - 0.55 * b / (episodes - 1)
        env = Environment(seed + 100 * b)
        s = env.state()
        for _ in range(HORIZON):
            a = (int(draw() * ACTIONS) if draw() < explore
                 else max(range(ACTIONS), key=lambda e: Q.get((s, e), 0.0)))
            s2, r = env.step(a)
            old = Q.get((s, a), 0.0)
            Q[(s, a)] = old + rate * (r + DISCOUNT * max(Q.get((s2, e), 0.0)
                                                         for e in range(ACTIONS)) - old)
            counts[(s, a)] = counts.get((s, a), 0) + 1
            s = s2
    return Q, counts


Q, COUNTS = train_table(SEED + 900)
STATES, PAIRS = 3 ** SUBSCRIBERS, 3 ** SUBSCRIBERS * ACTIONS
seen = {s for s, _ in COUNTS}
full = sum(all((s, e) in COUNTS for e in range(ACTIONS)) for s in seen)
print(f"states {STATES}, actions {ACTIONS}, state-action pairs {PAIRS}")
print(f"300 episodes x {HORIZON} steps = {300 * HORIZON} transitions; updated pairs {len(COUNTS)}"
      f" ({PAIRS - len(COUNTS)} never updated), states seen {len(seen)}")
print(f"states with all six actions tried {full}, states never seen {STATES - len(seen)}")
print(f"{'baseline: no dispatch':<28}{run(lambda s: SUBSCRIBERS):8.3f}")
rp = rng(SEED + 7)
print(f"{'baseline: random action':<28}{run(lambda s: int(rp() * ACTIONS)):8.3f}")
print(f"{'rule: largest delay':<28}"
      f"{run(lambda s: SUBSCRIBERS if max(s) == 0 else s.index(max(s))):8.3f}")
print(f"{'table':<28}{run(lambda s: max(range(ACTIONS), key=lambda e: Q.get((s, e), 0.0))):8.3f}")

states 243, actions 6, state-action pairs 1458
300 episodes x 30 steps = 9000 transitions; updated pairs 780 (678 never updated), states seen 206
states with all six actions tried 60, states never seen 37
baseline: no dispatch          0.000
baseline: random action       10.432
rule: largest delay           20.621
table                         24.495

The collected data is this: 9,000 transitions were made, 780 of the 1,458 cells were updated, and 678 were left untouched. This number depends on the exploration schedule and comes out differently with another schedule; what is binding here is the order of magnitude. Because the policy collected its own data, 37 of the 243 states were never seen, and only in 60 states were all six actions tried. In those 37 states all six entries of the table are zero; the rule of choosing the largest picks the first action there, and this choice has nothing learned in it.

The table still wins: 24.495, above the 20.621 of the rule policy. The problem is not that the result is bad at this scale, but the scale itself. Five subscribers gave 243 states; seven subscribers give 2,187 states and 17,496 pairs. When the number of transitions stays the same, the share of empty cells grows, because the table shares nothing between neighboring states.

A Function Instead of the Table

The network builds this sharing. Its input is the five delay classes, its output is the six action values; the target is the same as the temporal difference target of the previous lesson — the reward received plus the discounted best next action value. The difference is that the update spreads to all the weights, not to a single cell. The instability also comes from here: a correction made in one state moves the output of other states as well.

The second problem is the order in which the data arrives. The agent produces transitions sequentially; the six sequential steps of an episode are continuations of one another. The block below defines the network and measures this relation with two numbers.

SCALE = 10.0                                # the network target is kept on a reward/10 scale


def initialize(seed, hidden=10):            # small network: 5 -> 10 -> 6; procedure in the Deep Learning course
    draw, net = rng(seed), []
    for a, b in zip((SUBSCRIBERS, hidden, ACTIONS), (hidden, ACTIONS)):
        o = math.sqrt(2.0 / a)
        net.append(([[(draw() * 2 - 1) * o for _ in range(a)] for _ in range(b)], [0.0] * b))
    return net


def forward(net, x):
    (W1, b1), (W2, b2) = net
    h = [math.tanh(sum(w * v for w, v in zip(s, x)) + b) for s, b in zip(W1, b1)]
    return h, [sum(w * v for w, v in zip(s, h)) + b for s, b in zip(W2, b2)]


def features(s):
    return [x / 2.0 for x in s]


def update(net, batch, rate):               # only the chosen action's output is corrected
    (W1, b1), (W2, b2) = net
    n, g = len(batch), len(b1)
    gW1, gb1 = [[0.0] * SUBSCRIBERS for _ in range(g)], [0.0] * g
    gW2, gb2 = [[0.0] * g for _ in range(ACTIONS)], [0.0] * ACTIONS
    for x, a, target in batch:
        h, q = forward(net, x)
        e = q[a] - target
        for p in range(g):
            gW2[a][p] += e * h[p]
            dh = e * W2[a][p] * (1 - h[p] * h[p])
            gb1[p] += dh
            for j in range(SUBSCRIBERS):
                gW1[p][j] += dh * x[j]
        gb2[a] += e
    for j in range(ACTIONS):
        for p in range(g):
            W2[j][p] -= rate * gW2[j][p] / n
        b2[j] -= rate * gb2[j] / n
    for p in range(g):
        for j in range(SUBSCRIBERS):
            W1[p][j] -= rate * gW1[p][j] / n
        b1[p] -= rate * gb1[p] / n


def train_network(seed, buffer_size, batch_size, episodes=120, rate=0.10):
    net, draw, buf = initialize(seed), rng(seed + 77), []
    for b in range(episodes):
        explore = 0.60 - 0.55 * b / (episodes - 1)
        env = Environment(seed + 100 * b)
        s = env.state()
        for _ in range(HORIZON):
            a = (int(draw() * ACTIONS) if draw() < explore
                 else max(range(ACTIONS), key=lambda e: forward(net, features(s))[1][e]))
            s2, r = env.step(a)
            buf.append((s, a, r / SCALE, s2))
            if len(buf) > buffer_size:
                buf.pop(0)
            sample = (buf[-batch_size:] if buffer_size == batch_size       # sequential window
                      else [buf[int(draw() * len(buf))] for _ in range(batch_size)])
            update(net, [(features(ss), sa, sr + DISCOUNT * max(forward(net, features(sn))[1]))
                         for ss, sa, sr, sn in sample], rate)
            s = s2
    return net


def network_policy(net):
    return lambda s: max(range(ACTIONS), key=lambda e: forward(net, features(s))[1][e])


draw = rng(SEED + 3)                        # a 30-episode trace, with the table policy
TRACE = []
for b in range(30):
    env = Environment(SEED + 100000 + b)
    s = env.state()
    for _ in range(HORIZON):
        a = (int(draw() * ACTIONS) if draw() < 0.15
             else max(range(ACTIONS), key=lambda e: Q.get((s, e), 0.0)))
        TRACE.append((s, a, b))
        s = env.step(a)[0]


def spread(group):                          # mean class difference between the states in a batch
    c = [abs(x - y) for i in range(len(group)) for j in range(i + 1, len(group))
         for x, y in zip(group[i][0], group[j][0])]
    return sum(c) / (len(group) * (len(group) - 1) / 2)


WINDOWS = len(TRACE) - 6
sequential = [sum(spread(TRACE[i:i + 6]) for i in range(WINDOWS)) / WINDOWS,
              sum(len({t[2] for t in TRACE[i:i + 6]}) for i in range(WINDOWS)) / WINDOWS]
sampled = [0.0, 0.0]
for _ in range(WINDOWS):
    group = [TRACE[int(draw() * len(TRACE))] for _ in range(6)]
    sampled[0] += spread(group) / WINDOWS
    sampled[1] += len({t[2] for t in group}) / WINDOWS
print(f"{'six-sample batch':<26}{'sequential':>10}{'from buffer':>12}")
print(f"{'mean class difference':<26}{sequential[0]:>10.2f}{sampled[0]:>12.2f}")
print(f"{'distinct episodes':<26}{sequential[1]:>10.2f}{sampled[1]:>12.2f}")

six-sample batch          sequential from buffer
mean class difference           2.71        2.93
distinct episodes               1.16        5.50

The second row states the relation directly: a sequential batch of six comes on average from 1.16 distinct episodes, that is, almost all of it is consecutive steps of a single episode. A batch of six drawn from the buffer comes from 5.50 distinct episodes. The difference on the state side is more modest — the mean delay class difference between two states is 2.71 in a sequential batch of six and 2.93 in the one drawn from the buffer. In the sequential setup the network looks at six nearby samples at every step and shifts its weights according to that narrow region; a few steps later, when it moves on to another region, it undoes the shift.

The Difference the Replay Buffer Makes

Experience replay is a one-line change: transitions are written to a buffer and the update is made with a batch of six drawn at random from the buffer. To separate whether the difference comes from the batch size or from where the sample comes from, a third setup is added — the online form that uses no batch and updates only with the last transition. All three have the same budget: 120 episodes, 3,600 transitions.

RESULTS = {}
print(f"{'setup':<22}{'run 1':>9}{'run 2':>9}{'band':>7}")
for name, buffer_size, batch_size in (("online single step", 1, 1),
                                      ("sequential six", 6, 6),
                                      ("replay buffer", 900, 6)):
    RESULTS[name] = [run(network_policy(train_network(SEED + k, buffer_size, batch_size)))
                     for k in (1, 2)]
    g = RESULTS[name]
    print(f"{name:<22}{g[0]:>9.3f}{g[1]:>9.3f}{max(g) - min(g):>7.3f}")

SEQ, BUF = RESULTS["sequential six"], RESULTS["replay buffer"]
params = SUBSCRIBERS * 10 + 10 + 10 * ACTIONS + ACTIONS
print(f"\nsame batch size, buffer instead of sequential: "
      f"{max(SEQ):.3f} -> {max(BUF):.3f} and {min(SEQ):.3f} -> {min(BUF):.3f}")
print(f"run band {max(SEQ) - min(SEQ):.3f} -> {max(BUF) - min(BUF):.3f}")
print(f"network {params} parameters; table {PAIRS} cells, {PAIRS - len(COUNTS)} of them empty")

setup                     run 1    run 2   band
online single step       23.211   23.071  0.139
sequential six           22.259   20.146  2.113
replay buffer            26.233   25.302  0.930

same batch size, buffer instead of sequential: 22.259 -> 26.233 and 20.146 -> 25.302
run band 2.113 -> 0.930
network 126 parameters; table 1458 cells, 678 of them empty

The three rows are read in order. Using a batch is not a gain by itself: online single steps give 23.211 and 23.071, while sequential batches of six give 22.259 and 20.146, that is, averaging six samples lowers the number. The second run, at 20.146, falls even below the 20.621 of the rule policy. When the same batch size is drawn from the buffer, 26.233 and 25.302 come out. The gain does not come from the batch but from where the sample comes from.

The second number is stability. The run band of the sequential setup is 2.113; that of the replay buffer is 0.930. In the sequential setup, deciding by looking at a single run means looking at a number that moves by more than two units when only the training seed changes. This is why this course has its two-run rule.

The last line closes the scale. The network carries 126 parameters and produces six action values for all 243 states; the table carried 1,458 cells and 678 of them were empty. The answer the network gives in the 37 states it has never seen does not have to be correct, but it is not arbitrary either: it is an estimate carried over from neighboring states.

Summary

• The table shares nothing between neighboring states. After 9,000 transitions, 678 of the 1,458 cells were never updated, 37 of the 243 states were never seen, and only in 60 states were all six actions tried.
• Function approximation puts a network that takes the state as input in place of the table: 126 parameters, against 1,458 cells, and an answer even in a state never seen.
• Sequential transitions are correlated, and this is written as a number: a sequential batch of six comes from 1.16 distinct episodes on average, a batch of six drawn from the buffer from 5.50 distinct episodes.
• With the same budget, online single steps give 23.211 and 23.071, sequential batches of six 22.259 and 20.146, the replay buffer 26.233 and 25.302. The gain comes not from the batch but from where the sample comes from.
• Besides raising the level, experience replay adds stability: the run band falls from 2.113 to 0.930 and the bad run of the sequential setup falls below the rule policy.

Next Step

In five lessons the agent decided always the same way: a value was estimated for each action and the largest was chosen. The policy was a by-product of the value. This means that a small drift in the value estimate can change the policy completely — if the values of two actions are close to each other, a wobble in the estimate wobbles the choice as well. The next lesson parameterizes the policy directly and removes the value from the middle: each action is assigned a probability, and the probabilities are updated in the direction that will increase the return. What will be measured is the cost of this path — the update direction is now estimated from sampled episodes, and with the same policy and the same budget it is counted how many episodes give how many distinct directions.