--- title: 'Function Approximation and Experience Replay' source: 'https://academia.sh/en/courses/reinforcement-and-recommender/function-approximation-and-experience-replay' course: 'Reinforcement Learning and Recommender Systems' language: en updated: '2026-10-21T05:03:29+00:00' license: 'CC BY-SA 4.0' objectives: - 'Counts which cells of the action value table stay empty as the number of states grows' - 'Replaces the table with a small network and compares the number of parameters of the network with the number of cells of the table' - 'Measures what training on sequential transitions breaks and writes the difference the replay buffer makes with two runs' --- # Function Approximation and Experience Replay Measuring, in numbers, a small network that replaces the table and the experience replay: of the 1,458 cells formed by 243 states and 6 actions, only 780 are updated after 9,000 transitions, 37 states are never seen, and only 60 states have all six actions tried. A sequential batch of six comes from 1.16 distinct episodes on average, a batch of six drawn from the buffer from 5.50. The baselines are 0.000 and 10.432, the rule policy 20.621, the table 24.495. The network with 126 parameters gives 23.211 and 23.071 with online single steps, 22.259 and 20.146 with sequential batches of six, 26.233 and 25.302 with the replay buffer; the run band falls from 2.113 to 0.930. 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. ```python # 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. ```python 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. ```python 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.