--- title: 'Reinforcement Learning and Recommender Systems' source: 'https://academia.sh/en/courses/reinforcement-and-recommender' language: en updated: '2026-10-21T05:03:27+00:00' license: 'CC BY-SA 4.0' lessons: 14 outcomes: - 'Formally defines a reinforcement learning problem with state, action, transition and reward' - 'Distinguishes value-based and policy-based methods and counts the data each one collects' - 'Builds recommender systems with their cold-start and evaluation problems and measures the feedback loop' --- # Reinforcement Learning and Recommender Systems How to read a measurement in a setup where the system making the decision changes its own data: the return of a random policy against that of a learning policy and which states are never seen, the return moving when the assumption that a transition depends only on the current state breaks, the regret that accumulates and the action never tried as the exploration rate is swept, the cells of the value table that are never updated, consecutive samples corrupting training and what experience replay fixes, the variance of the gradient estimate by episode count, where the actor goes when the critic is bad, the surprising strength of recommending the most popular item to everyone, the coverage of content-based recommendation, the number of subscribers for whom no neighbor is found, the difference between counting an unobserved cell as zero and skipping it, the cost of warming up a cold subscriber, offline ranking not telling online behavior, and the coverage that the feedback loop narrows. ## Reinforcement Learning Measuring an agent that learns the result only after the action and collects its own data: in the field visit setup, the return of the random policy against that of the learning policy and the states never seen; the change in return when a history field is added to the assumption that the transition depends only on the current state; the regret that accumulates as the exploration rate is swept and the action the always-exploiting policy never tries; the cells never updated in a table learned with the temporal difference update; how correlated consecutive samples spoil training and the difference experience replay makes; how many distinct directions the gradient estimate gives under the same budget and how the baseline lowers this; the gain brought by the advantage estimate and where the actor goes when the critic is bad. ### Agent, Environment and Reward Source: https://academia.sh/en/courses/reinforcement-and-recommender/agent-environment-and-reward Reading three numbers in a setup where the decision produces its own data: in the field visit setup, the policy that never dispatches the crew gets a return of 0.000, random action, the baseline, gets 10.432, and the rule that goes to the subscriber with the largest delay gets 20.621. The third number is the collected data: the random policy sees 234 of the 243 states and 1,251 of the 1,458 state-action pairs, while the rule, which earns the better return, sees only 103 states and 103 pairs. In the same period the six actions would give rewards of -2, -2, 1, -2, 1 and 0, and the agent learns only one of them; this is what takes the place of the label in supervised learning. 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 ```python # 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 ```python # 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 ```python # 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. ### Decision Process Formalization Source: https://academia.sh/en/courses/reinforcement-and-recommender/decision-process-formalization Writing down the five-tuple of state, action, transition, reward and discount factor, and measuring its defining condition in the setup: in the same state-action cell the next state spreads over four distinct values with probabilities 0.4307, 0.2239, 0.1770 and 0.1046, and the reward over -2, 1 and 7 with 0.0516, 0.2347 and 0.7137. The memoryless-transition test shows that the condition does not hold exactly: in the most frequent cell, for the same state and the same action, the mean reward is 4.518 when the delay is 3 and 5.944 when the delay is 4 or more; the difference is 1.425 and positive in five cells out of five. The same hand-written rule gets a return of 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 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 ```python # 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 ```python # 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 ```python # 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**. ### The Exploration and Exploitation Trade-Off Source: https://academia.sh/en/courses/reinforcement-and-recommender/exploration-and-exploitation-trade-off Counting the price paid when learning requires trying and winning requires repeating what is known: the agent that never explores, starting from a pessimistic initial value, never tries five of the six actions, sees 95 of the 243 states and gets a return of -16.492, while its regret is exactly 0.0. When the exploration rate is swept from 0.00 to 1.00 the return is -16.492, 16.716, 22.210, 23.606, 25.659, 25.997 and 23.000; the accumulated regret is 0.0, -76.0, 402.0, 1,210.0, 3,545.0, 8,358.0 and 33,811.0. A return 0.338 below the best return can be had at a rate of 0.20 with a regret of 3,545. When the initial value of the estimates is moved from pessimistic to optimistic, the agent that never explores rises to 26.212 and its regret stays at 0.0. In the previous two lessons the policy was written by hand. The rule knew from the start what to do, no number was learned from data, and so learning had no cost. When the policy starts to be learned, a constraint counted in the first lesson of the course turns directly into a conflict: in one step the agent sees only the outcome of the action it chose and hears nothing about the five it did not choose. The only way to learn how good an action is is to try it, and every trial is deducted from that period's return. **Exploitation** is choosing the action with the highest estimate; it turns current knowledge into money. **Exploration** is choosing an action whose estimate is low or missing; it turns today's return into information. This lesson turns the conflict into a knob, sweeps the knob and counts both directions: how many steps are lost for how many steps gained. - **RL18. The setup, horizon, discount factor and seed continue unchanged from 01–02.** Five subscribers, one crew, the same deterioration probabilities, 243 states, 6 actions, an episode of 30 periods. - **RL19. In this lesson the estimate is the mean of the immediate reward.** For each state-action pair the mean of the rewards seen in that pair is kept; the return and the temporal difference are left to the next lesson. - **RL20. The form of exploration is a single rate.** With probability $\varepsilon$ the action is chosen without discrimination, and in the remaining cases the one with the highest estimate is chosen; ties are broken by the smallest number. - **RL21. Regret is the immediate cost of exploration steps:** at every step, the difference between the reward the greedy action would have given at that step and the reward actually received is accumulated. In exploitation steps this difference is exactly zero, while in exploration steps it **can also come out negative**. - **RL22. The initial value of the estimates is a choice, and this lesson measures it too.** The pessimistic initial value is $-5.0$ and is below all possible rewards; the optimistic initial value is $0.0$ and is above $-2$, the reward of a wasted visit. - **RL23. Training is 300 episodes, that is 9,000 steps.** Then the table is frozen and the learned greedy policy is measured on the same 300 episode seeds as in 01; the numbers are on the same scale as 10.432 and 20.621. - **RL24. The swept exploration rates are seven candidates:** 0.00, 0.02, 0.05, 0.10, 0.20, 0.40 and 1.00. - **RL25. The measure is a triple and is always printed side by side:** the return of the frozen policy, the accumulated regret and the number of actions never tried. When a state never seen in training is met, all estimates are equal and the action with the smallest number is chosen. #### The Always-Exploiting Agent ```python # environment.py — FICTIONAL. Field visit planning continues unchanged from the previous two # 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 train(explore, initial, n_episodes=300, seed=SEED + 11): """For each state-action pair the mean of the IMMEDIATE reward is kept.""" draw = rng(seed) Q, N, regret, explore_steps = {}, {}, 0.0, 0 for k in range(n_episodes): env = Environment(SEED + 1000 * k) s = env.state() for _ in range(HORIZON): q = Q.setdefault(s, [initial] * ACTIONS) n = N.setdefault(s, [0] * ACTIONS) greedy = max(range(ACTIONS), key=lambda i: q[i]) a = int(draw() * ACTIONS) if draw() < explore else greedy expected = PAYOFF[env.level[greedy]] - COST if greedy < SUBSCRIBERS else 0.0 s2, reward = env.step(a) regret += expected - reward explore_steps += (a != greedy) n[a] += 1 q[a] += (reward - q[a]) / n[a] s = s2 return Q, N, regret, explore_steps def freeze(Q, initial): """Learning ends, the table freezes; the policy is now greedy.""" def pol(s, env): q = Q.get(s, [initial] * ACTIONS) return max(range(ACTIONS), key=lambda i: q[i]) return pol INITIAL = -5.0 Q0, N0, regret0, explore0 = train(0.00, INITIAL) tried = [sum(N0[s][a] for s in N0) for a in range(ACTIONS)] print(f"exploration rate 0.00, initial value of estimates {INITIAL}") print(f" return of the learned policy {statistics.mean(run(freeze(Q0, INITIAL))):.3f}") print(f" accumulated regret {regret0:.1f}; exploration steps {explore0}") print(f" states seen {len(N0)}/243; state-action pairs tried " f"{sum(1 for v in N0.values() for x in v if x > 0)}/1458") print(" trials per action: " + ", ".join(f"{LABELS[a]}={tried[a]}" for a in range(ACTIONS))) ``` ``` exploration rate 0.00, initial value of estimates -5.0 return of the learned policy -16.492 accumulated regret 0.0; exploration steps 0 states seen 95/243; state-action pairs tried 95/1458 trials per action: A1=9000, A2=0, A3=0, A4=0, A5=0, idle=0 ``` The agent that never explores spends all 9,000 of its steps on a single action. The reason can be read in one line: at the start all estimates are $-5.0$, ties are broken by the smallest number, the first action is A1, and whatever A1's real reward comes out as, it is above $-5.0$. The estimate rises, A1 is now alone at the top and nothing can ever overtake it, because the estimates of the other five actions stay at $-5.0$ since they were never tried. **A2, A3, A4, A5 and the option of not dispatching the crew are never tried**: five of the six actions. The result shows in the return. The policy gets $-16.492$; far below the 0.000 of never dispatching the crew and the 10.432 of random action. The agent goes to A1 every period, A1 is mostly found clean because it was repaired a period earlier, and every visit writes down 2 units. The number confirms this: the discounted total of getting $-2$ without a break for thirty periods is $-19.152$, and the measured $-16.492$ owes the difference to A1 occasionally deteriorating and giving 1 or 7. The collected data narrows as well: 95 of the 243 states are seen, and of the 1,458 pairs only 95 are tried. These 95 pairs mean a single action in each of 95 states — always the same action. Regret, meanwhile, is **exactly 0.0**. This is not an achievement, it is the definition of the measure: regret counts the immediate cost of exploration steps, and there are no exploration steps. That a system's regret is zero does not say the system is good, it says it **learned nothing**. The two numbers carry meaning only side by side. #### Sweeping the Exploration Rate ```python # sweep.py — Seven exploration rates, the same budget (300 episodes, 9,000 steps), the same # horizon, the same pessimistic initial value. The learned policy is then frozen and measured. print(f"{'rate':>6}{'return':>9}{'regret':>10}{'explore steps':>15}" f"{'states':>8}{'pairs':>7}{'actions never tried':>22}") for explore in (0.00, 0.02, 0.05, 0.10, 0.20, 0.40, 1.00): Q, N, regret, steps = train(explore, INITIAL) count = [sum(N[s][a] for s in N) for a in range(ACTIONS)] never = [LABELS[a] for a in range(ACTIONS) if count[a] == 0] pairs = sum(1 for v in N.values() for x in v if x > 0) print(f"{explore:>6.2f}{statistics.mean(run(freeze(Q, INITIAL))):>9.3f}{regret:>10.1f}" f"{steps:>15}{len(N):>8}{pairs:>7}{(','.join(never) if never else '-'):>22}") ``` ``` rate return regret explore steps states pairs actions never tried 0.00 -16.492 0.0 0 95 95 A2,A3,A4,A5,idle 0.02 16.716 -76.0 150 127 237 - 0.05 22.210 402.0 364 143 335 - 0.10 23.606 1210.0 748 176 472 - 0.20 25.659 3545.0 1500 185 578 - 0.40 25.997 8358.0 2945 217 839 - 1.00 23.000 33811.0 7494 235 1237 - ``` The return column draws a single-peaked curve. At zero exploration $-16.492$, at 0.40 the highest value 25.997, at 1.00 again 23.000. The two ends are bad for two different reasons. On the left the agent does not learn, because it does not try. On the right the agent chooses every step without discrimination, so the data it collects is good but its behavior is bad; even so the frozen table gives 23.000, that is, **good data can be collected with bad behavior** — the basic tension of the next course sits here in seed form. The real reading is between two columns. A rate of 0.20 gives a return of 25.659 at a cost of 3,545 regret. A rate of 0.40 gives only 0.338 more return but costs 8,358, more than double. The return bought with exploration rises with diminishing increments; each additional exploration step brings less information than the one before, yet its cost stays the same. Going to 1.00, a regret of 33,811 is paid and the return drops. The minus sign in the 0.02 row is not an error, it is the measure itself. The total cost of the 150 exploration steps is $-76.0$: on average the exploration steps brought **better** rewards than the greedy action. The reason is that the greedy action was locked onto A1 at that stage; while going to A1 mostly writes $-2$, the action chosen without discrimination has often found something better. While a bad policy is being exploited, the cost of exploration falls below zero. The cost turns positive only when the exploited policy is actually good, and the rise in the table follows exactly this. The pairs-tried column carries a warning too. Even at the most generous exploration, 1,237 of the 1,458 pairs are tried, so 221 are never tried and the states seen stay at 235. If the frozen policy meets the remaining 8 states it finds all estimates equal and chooses the action with the smallest number. This also defines where the learned number holds: as far as the region where the table is full. The two columns on the right carry the third number of the course. As the exploration rate grows, the states seen rise from 95 to 235, and the pairs tried from 95 to 1,237. Exploration is not merely paying a cost; it **widens the data it collects** and the widening data ensures that more cells of the frozen table hold a number. The hyperparameter search lies outside this measure and is not repeated: in the candidate sweep built in the model evaluation topic of the Supervised Learning course, what was paid when the number of candidates was increased was the computation budget; the data stood fixed from start to finish and no loss remained after the search ended. Here what is paid is **the return itself**: every exploration step is a period that was actually lived, cannot be taken back, and also permanently changes the data collected in that period. #### Exploration Does Not Have to Come from Randomness ```python # initial.py — The same sweep, two different initial values. A pessimistic initial value # makes an untried action look bad; an optimistic initial value makes it look worth trying. print(f"{'initial value':>14}{'rate':>7}{'return':>9}{'regret':>10}{'pairs':>7}") for initial in (-5.0, 0.0): for explore in (0.00, 0.05, 0.20): Q, N, regret, steps = train(explore, initial) pairs = sum(1 for v in N.values() for x in v if x > 0) print(f"{initial:>14.1f}{explore:>7.2f}" f"{statistics.mean(run(freeze(Q, initial))):>9.3f}{regret:>10.1f}{pairs:>7}") ``` ``` initial value rate return regret pairs -5.0 0.00 -16.492 0.0 95 -5.0 0.05 22.210 402.0 335 -5.0 0.20 25.659 3545.0 578 0.0 0.00 26.212 0.0 356 0.0 0.05 26.155 772.0 496 0.0 0.20 26.378 4147.0 636 ``` The bottom three rows make the whole table above be read again. With the exploration rate again 0.00, the return is not $-16.492$ but **26.212**, the regret is again exactly 0.0, and the pairs tried are not 95 but 356. Exploration happened without a single random step being taken. The reason is in the initial value. The estimate of an untried action is $0.0$; the real reward of a wasted visit is $-2$. When the agent tries an action and gets $-2$, that action's estimate falls below those of the untried actions and the greedy choice shifts by itself to the next one. As long as the estimates start above the truth, greediness itself produces exploration; disappointment brings the next action onto the agenda. With a pessimistic initial value the opposite happens: whatever the first tried action gives, it rises above the untried ones and the door closes. This is an exploration mechanism that keeps regret at zero, but it is not free. The initial value has to be above the real rewards, which requires prior knowledge about the scale of the rewards; that 0.0 works in the setup is because we know a wasted visit writes $-2$. Its effect is also temporary: once each cell has been tried one time the optimism is spent, and if the environment changes over time exploration is needed again. Exploration done by rate is permanent and is paid at every step. The difference between 4,147 and 0.0 in the table puts the cost of these two mechanisms side by side in the same unit. #### Summary - Exploitation chooses the action with the highest estimate, exploration tries the uncertain one; since the agent sees the outcome of only the action it chose in a step, the two cannot be done at the same time. - The agent that never explores, with a pessimistic initial value, spends all 9,000 steps on A1, never tries five of the six actions, sees 95 of the 243 states and gets a return of $-16.492$. - A regret of 0.0 is not a good sign: because there are no exploration steps it is zero by definition, and it says nothing unless read side by side with the return. - When the exploration rate is swept from 0.00 to 1.00 the return rises from $-16.492$ to 25.997 and falls to 23.000; the cost climbs from 0.0 to 33,811.0. A rate of 0.20 stays 0.338 below the best return while paying only 0.424 of the cost. - At a low exploration rate regret can fall below zero ($-76.0$), because the exploited policy is bad at that stage and the action chosen without discrimination turns out on average better than it. - The initial value of the estimates is also an exploration mechanism: with an optimistic start, without a single random step, the return rises to 26.212, the pairs tried from 95 to 356, and regret stays at 0.0. #### Next Step The number kept in this lesson was the mean of the **immediate reward**: what an action in a state brought in that period. In the first lesson, however, the return was defined as the discounted total of thirty periods, and the real effect of a visit does not end in that period — the repaired subscriber stays clean for a few more periods, the neglected subscriber costs more a few periods later. An estimate that looks at the immediate reward never sees this chain, which is why it gets stuck at 26.378. The next lesson turns the number kept in the table from the immediate reward into **the return**: the value of a state is the sum of the discounted rewards that can be collected from there on, and this number can be learned step by step from the difference between two successive estimates. The measure will again be read from the collected data: how many cells of the table remain **never updated** at the end of 9,000 steps. ### Value Functions and Action Value Source: https://academia.sh/en/courses/reinforcement-and-recommender/value-functions-and-action-value Learning value only from lived quadruples, without knowing the environment's probabilities, and counting the empty places of the table: when the temporal difference update is swept 40 times over a 9,000-step trace, the mean value of the starting states rises from 12.632 to 21.562, and its gap to the measured 30-period return of 20.621 sits on the 0.0424 tail, the thirtieth power of the discount factor. State values spread between 29.060 and 16.075. Of the 1,458 cells of the action value table fed by its own data only 103 are updated, 1,355 stay untouched, and the policy read from the table gives exactly the rule that produced it, 20.621. As exploration is added to the behavior, the filled cells rise from 103 to 1,237, but the thin cells with fewer than five samples also rise from 47 to 468, and the return does not move in one direction. 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 ```python # 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 ```python # 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 ```python # 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. ### Function Approximation and Experience Replay Source: https://academia.sh/en/courses/reinforcement-and-recommender/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. ### Policy Gradient Source: https://academia.sh/en/courses/reinforcement-and-recommender/policy-gradient Measuring the cost of parameterizing the policy directly: with the same policy and the same budget of 120 episodes, the 120 update directions read from single episodes make a mean angle of 86.1 degrees and the agreement stays at 0.290; with six estimates of twenty episodes each, the angle rises to 44.0 degrees and the agreement to 0.878. When the baseline built from the step-by-step mean return is subtracted, the same numbers become 81.2 degrees with 0.389 and 39.8 degrees with 0.892; two episodes with baseline subtraction give the agreement of four raw episodes. In training with 240 episodes, the two-episode estimate gives 15.840 and 19.962 with raw return and 22.866 and 22.190 with baseline subtraction; the run band falls from 4.122 to 0.675. In the previous five lessons the policy was always built indirectly: a value was estimated for each action and the largest was chosen. In this arrangement the policy is a by-product of the value estimate — if the estimated values of two actions are close to each other, a small drift in the estimate turns the choice completely around. The choice is also sharp: the action with the largest value is always chosen, the second best action never. This lesson takes another path. The policy is parameterized **directly**: each action is given a weight row, a probability distribution is produced from the state, and the weights are shifted in the direction that will increase the return. The direction is no longer read from a table; it is **estimated from sampled episodes** — and what this lesson measures is how much that estimate wobbles. - **RL49.** The environment is the setup built in `01` and continues as it was: five subscribers, one crew per period, horizon 30, discount factor 0.9. The measurement is on the same 300 episodes as in `01`. - **RL50.** The features of the policy are the five delay classes and a constant, that is, six numbers. The weight array is $6 \times 6 = 36$ numbers; throughout the lesson "direction" describes a shift of these 36 numbers. - **RL51.** The action probabilities come from the exponential normalization of the weighted sums. When all weights are zero the distribution is equiprobable; this is the policy at which the measurement starts, and it is the same as the random action baseline of `01`. - **RL52.** The direction read from one episode is, at every step, the product of the return after that step and the shift that increases the probability of the chosen action. The discount factor is not applied separately as a step weight; the return itself is already discounted. - **RL53.** The variability is written with two numbers: the **mean pairwise angle** between the estimates and the **agreement ratio** — the length of the mean estimate divided by the mean length of the individual estimates. If the agreement is near 1 the estimates point to the same place, if it is near 0 they cancel one another. Both measures are independent of the number of estimates. - **RL54.** The baseline is the step-by-step mean return read from **separate** 200 episodes of the same policy. It has to be read from separate episodes; if the own return of the measured episode is subtracted, the direction is by definition zeroed. - **RL55.** The baseline is independent of the action, so it does not shift the place the estimate is going to: when the probability shifts of all the actions in a state are summed the result is zero, and therefore the multiplier of a constant number is zero as well. The only thing that changes is the wobble of the estimate. - **RL56.** In training the budget is 240 episodes and the learning step is held constant at 0.01; the only things that change are the batch size and whether baseline subtraction is used. #### Writing the Policy Directly The block below rebuilds the environment, defines the policy and computes the direction read from one episode. The logic of the direction is one sentence: if the return that comes after an action is chosen is large, the probability of that action is increased, if it is small it is decreased. ```python # policy.py — FICTIONAL. The same setup: five subscribers, one crew, horizon 30, discount 0.9. 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 FEATURES = SUBSCRIBERS + 1 # number of features: five delay classes + a constant 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 probabilities(th, s): # exponential normalization; th[a] is the weight row of the action x = [v / 2.0 for v in s] + [1.0] z = [sum(t * v for t, v in zip(th[a], x)) for a in range(ACTIONS)] e = [math.exp(v - max(z)) for v in z] total = sum(e) return [v / total for v in e], x def choose(th, s, r): p, _ = probabilities(th, s) u, t = r(), 0.0 for a in range(ACTIONS): t += p[a] if u < t: return a return ACTIONS - 1 def run(policy, n=300): # the same 300 episodes as in 01 returns = [] for k in range(n): env, r = Environment(SEED + 1000 * k), rng(SEED + 90000 + k) s, total, factor = env.state(), 0.0, 1.0 for _ in range(HORIZON): s2, reward = env.step(policy(s, r)) total, factor, s = total + factor * reward, factor * DISCOUNT, s2 returns.append(total) return statistics.mean(returns) def episode_trace(th, seed): env, r = Environment(seed), rng(seed + 5) s, trace = env.state(), [] for _ in range(HORIZON): a = choose(th, s, r) s2, reward = env.step(a) trace.append((s, a, reward)) s = s2 return trace def returns_to_go(trace): # the discounted return after each step G, g = [0.0] * len(trace), 0.0 for t in range(len(trace) - 1, -1, -1): g = trace[t][2] + DISCOUNT * g G[t] = g return G def episode_gradient(th, trace, G, baseline=None): # the update direction read from a single episode e = [0.0] * (ACTIONS * FEATURES) for t, (s, a, _) in enumerate(trace): p, x = probabilities(th, s) w = G[t] - (baseline[t] if baseline else 0.0) for b in range(ACTIONS): k = w * ((1.0 if b == a else 0.0) - p[b]) for j in range(FEATURES): e[b * FEATURES + j] += k * x[j] return e def value_baseline(th, seeds): # the step-by-step mean return, from SEPARATE episodes total = [0.0] * HORIZON for sd in seeds: G = returns_to_go(episode_trace(th, sd)) for t in range(HORIZON): total[t] += G[t] / len(seeds) return total def angle(u, v): nu = math.sqrt(sum(x * x for x in u)) nv = math.sqrt(sum(x * x for x in v)) c = sum(a * b for a, b in zip(u, v)) / (nu * nv) return math.degrees(math.acos(max(-1.0, min(1.0, c)))) def measure(estimates): n = len(estimates) mean = [sum(v[j] for v in estimates) / n for j in range(len(estimates[0]))] length = statistics.mean(math.sqrt(sum(x * x for x in v)) for v in estimates) return (statistics.mean(angle(estimates[i], estimates[j]) for i in range(n) for j in range(i + 1, n)), math.sqrt(sum(x * x for x in mean)) / length) TH = [[0.0] * FEATURES for _ in range(ACTIONS)] # all weights zero: equal-probability policy rp = rng(SEED + 7) print(f"{'baseline: no dispatch':<30}{run(lambda s, r: SUBSCRIBERS):8.3f}") print(f"{'baseline: random action':<30}{run(lambda s, r: int(rp() * ACTIONS)):8.3f}") print(f"{'measured policy (weights 0)':<30}{run(lambda s, r: choose(TH, s, r)):8.3f}") BUDGET = 120 BASELINE = value_baseline(TH, [SEED + 700000 + i for i in range(200)]) RAW, BASELINED = [], [] for i in range(BUDGET): trace = episode_trace(TH, SEED + 200000 + i) G = returns_to_go(trace) RAW.append(episode_gradient(TH, trace, G)) BASELINED.append(episode_gradient(TH, trace, G, BASELINE)) def group_mean(items, B): return [[sum(v[j] for v in items[i * B:(i + 1) * B]) / B for j in range(ACTIONS * FEATURES)] for i in range(len(items) // B)] print(f"\nbaseline: first step {BASELINE[0]:.2f}, tenth {BASELINE[9]:.2f}, last {BASELINE[-1]:.2f}") print(f"{'episodes/estimate':>17}{'estimates':>10}{'angle':>8}{'agreement':>11}" f"{'angle (baseline)':>18}{'agreement (baseline)':>22}") for B in (1, 2, 4, 10, 20): h, t = measure(group_mean(RAW, B)), measure(group_mean(BASELINED, B)) print(f"{B:>17}{BUDGET // B:>10}{h[0]:>8.1f}{h[1]:>11.3f}{t[0]:>18.1f}{t[1]:>22.3f}") ``` ``` baseline: no dispatch 0.000 baseline: random action 10.432 measured policy (weights 0) 10.177 baseline: first step 9.88, tenth 11.18, last 1.63 episodes/estimate estimates angle agreement angle (baseline) agreement (baseline) 1 120 86.1 0.290 81.2 0.389 2 60 83.1 0.386 74.8 0.511 4 30 77.9 0.508 67.0 0.636 10 12 62.4 0.736 53.1 0.790 20 6 44.0 0.878 39.8 0.892 ``` The third row gives the measure of the policy: the policy with zero weights returns 10.177, that is, it is at the same place as the 10.432 of the random action. This is what is expected — equiprobable choice is random choice and the 0.255 difference between the two numbers is only a sampling detail. The first row of the table is the number of the lesson. When the budget of 120 episodes is used one by one, **120 distinct update directions** come out and these directions make a mean angle of **86.1 degrees**: they are almost perpendicular to one another. The agreement ratio is 0.290, that is, seven tenths of the directions cancel one another when summed. Shifting the weights by looking at a direction read from a single episode is writing noise into the policy. When the budget is not divided, the table smooths out: six estimates of twenty episodes each give 44.0 degrees and 0.878 agreement. But this has a cost — the same budget falls to six updates. This is the tension measured throughout the lesson: the more reliable the direction is wanted, the fewer updates can be made. #### Subtracting the Baseline The baseline row shows the source of the problem: in this environment the returns are between 9.88 and 11.18 in the first steps and 1.63 at the last step. Nearly all of them are positive. When the return is used directly as the multiplier, **the probability of every chosen action is increased**; the distinction between actions comes only from the size of the increase. A bad action, too, since the return that follows it is positive, ends up increasing its probability. Baseline subtraction corrects this. The **mean** return of each step is subtracted from the return of that step; an action that stays above the mean is increased, one that stays below it is decreased. The number is in the right half of the table: for a single episode 86.1 degrees becomes 81.2 degrees, and the agreement rises from 0.290 to 0.389. A more readable form is this — **two** episodes with baseline subtraction give 0.511 agreement, four raw episodes 0.508. The same agreement is obtained with half the budget. The effect shrinks as the budget grows: with twenty episodes 44.0 degrees falls to 39.8 degrees, and the agreement rises from 0.878 to 0.892. If the estimate is already sampled enough, baseline subtraction has little left to correct. #### The Same Budget, Four Setups The variability measure gains meaning only when it is turned into learning. The block below spends the same budget of 240 episodes in four ways: a batch of two or ten episodes, with baseline subtraction or with raw return. ```python def train(seed, baselined, batch, budget=240, rate=0.01): th = [[0.0] * FEATURES for _ in range(ACTIONS)] baseline = [0.0] * HORIZON for t in range(budget // batch): direction, mean_G = [0.0] * (ACTIONS * FEATURES), [0.0] * HORIZON for i in range(batch): trace = episode_trace(th, seed + 1000 * t + i) G = returns_to_go(trace) e = episode_gradient(th, trace, G, baseline if baselined else None) for j in range(ACTIONS * FEATURES): direction[j] += e[j] / batch for u in range(HORIZON): mean_G[u] += G[u] / batch if baselined: baseline = mean_G # the baseline comes from the previous batch for b in range(ACTIONS): for j in range(FEATURES): th[b][j] += rate * direction[b * FEATURES + j] return th print(f"{'setup':<28}{'updates':>11}{'run 1':>9}{'run 2':>9}{'band':>7}") FINAL = {} for batch in (2, 10): for baselined in (False, True): name = f"{batch} episodes, {'with baseline' if baselined else 'raw return'}" g = [run(lambda s, r, th=train(SEED + 300000 + k * 7919, baselined, batch): choose(th, s, r)) for k in (1, 2)] FINAL[(batch, baselined)] = g print(f"{name:<28}{240 // batch:>11}{g[0]:>9.3f}{g[1]:>9.3f}{max(g) - min(g):>7.3f}") h2, t2 = FINAL[(2, False)], FINAL[(2, True)] print(f"\nbaseline subtraction at a two-episode estimate: {min(h2):.3f} -> {min(t2):.3f} and " f"{max(h2):.3f} -> {max(t2):.3f}, band {max(h2) - min(h2):.3f} -> {max(t2) - min(t2):.3f}") ``` ``` setup updates run 1 run 2 band 2 episodes, raw return 120 15.840 19.962 4.122 2 episodes, with baseline 120 22.866 22.190 0.675 10 episodes, raw return 24 17.121 17.853 0.732 10 episodes, with baseline 24 16.808 16.900 0.093 baseline subtraction at a two-episode estimate: 15.840 -> 22.190 and 19.962 -> 22.866, band 4.122 -> 0.675 ``` The four rows confirm how the table is read. The two-episode estimate gives 15.840 and 19.962 with raw return; both exceed the 10.432 of the random action but the run band is 4.122 — a number that moves by more than four units only because the starting episodes change. When the baseline is subtracted in the same setup, 22.866 and 22.190 come out and the band falls to 0.675. Here baseline subtraction both raises the level and brings stability, because a two-episode estimate is too wobbly to be used without a baseline. With the ten-episode estimate the table turns around: 16.808 and 16.900 against 17.121 and 17.853. Baseline subtraction brings no gain here. The reason is in the table — at ten episodes the agreement is already 0.736 and baseline subtraction carries it to 0.790; this improvement does not make up for the number of updates, which falls to a tenth of the budget. The best number comes from where **many updates and an agreeing direction** meet. No setup of this lesson approaches the 26.233 of the previous lesson. Here the policy gradient is weaker than the action value, and this needs to be written down: a linear policy of 36 numbers learns as much as it can by weighting the delay classes and choosing; the action value built by the network also carries the nonlinear distinctions between states. #### Summary - Parameterizing the policy directly removes the action value from the middle: each action is given a weight row, the probabilities are produced by exponential normalization, the weights are shifted in the direction that will increase the return. - The direction is now estimated from sampled episodes and it wobbles: when the budget of 120 episodes is used one by one, 120 distinct directions come out, the mean angle between them is 86.1 degrees and the agreement ratio 0.290. - One way to bring the estimate into agreement is not to divide the budget — with twenty episodes the angle comes to 44.0 degrees and the agreement to 0.878 — but then the same budget falls to six updates. - Because the baseline is independent of the action, it does not shift the place the estimate is going to, it only lowers its wobble: two episodes with baseline subtraction give 0.511 agreement, four raw episodes 0.508. - In the same budget of 240 episodes the two-episode estimate gives 15.840 and 19.962 with raw return and 22.866 and 22.190 with baseline subtraction; the band falls from 4.122 to 0.675. With the ten-episode estimate the gain of baseline subtraction disappears. #### Next Step In this lesson the baseline remained a fixed list: the step-by-step mean return read from separate episodes of the same policy. It does not use the state at all — it gives the same number for every state at the thirtieth step, although some states are clearly better than others. The next lesson replaces the fixed baseline with a **learned value function** and trains two components together: the side that chooses the action and the side that evaluates it. Two things will be measured — the gain brought by the difference read against the value of the state itself, and the situation in which the two components spoil each other: where the choosing side goes when the evaluating side gives a wrong number. ### Actor–Critic Methods Source: https://academia.sh/en/courses/reinforcement-and-recommender/actor-critic-methods Measuring the joint training of the component that chooses and the component that evaluates, and how they spoil each other: under the same budget of 240 episodes, with a step of 0.01 the raw return gives 15.840 and 19.962, the fixed baseline 22.866 and 22.190, the advantage estimate of the learned critic 21.154 and 21.100. When the learning step is raised to 0.06, the two methods that rely on the full return break down — one run of the fixed baseline falls to the never-dispatch baseline with 0.029, its band 15.953 — while the advantage gives 23.401 and 23.755 and keeps the band at 0.354. When the learning step of the critic is raised to 0.50, the values diverge to the order of 10 to the power of 102, the actor piles onto a single action, four of the five subscribers are never visited and the return falls to -18.772. The previous lesson measured that baseline subtraction brings the gradient estimate into agreement, but the baseline that was subtracted was a crude list: the step-by-step mean return read from separate episodes of the same policy. It did not use the state at all. A state in which all five subscribers are waiting at the thirtieth step and a state in which all are freshly visited were compared with the same number, although the two are clearly different places. This lesson replaces the fixed baseline with a **learned state value**. A two-component arrangement emerges: the **actor** that chooses the action and the **critic** that says how valuable the current state is. The update of the actor is now scaled not by the return itself but by the **advantage** — by how much better the action turned out than what was expected in that state. Two things will be measured: the difference the advantage estimate makes, and the situation in which the two components spoil each other. - **RL57.** The environment is the setup built in `01`: five subscribers, one crew per period, horizon 30, discount factor 0.9. The weight array of the actor is 36 numbers as in `06`, and the measurement is on the same 300 episodes. - **RL58.** The critic uses the same six features as the actor and is a single weight row — six numbers. It is kept linear because what this lesson measures is not the capacity of the critic but the **interaction** of the two components. - **RL59.** The advantage is one-step: the reward received, plus the discounted value of the next state, minus the value of the current state. At the last step of the episode the value of the next state is taken as zero. - **RL60.** The critic is updated in the temporal difference form and the same advantage is used in the update; that is, the actor and the critic share a single number. This sharing is also the reason the two can spoil each other. - **RL61.** Three methods are compared under the same budget: 240 episodes, a batch of two episodes, 120 updates. The only thing that changes is the number that scales the update of the actor — the raw return, the return with a fixed baseline subtracted, or the advantage. - **RL62.** The comparison is made at **two learning steps**: 0.01 and 0.06. Measuring at a single step is misleading, because the real difference between the methods is which step they can carry. - **RL63.** The own learning step of the critic is a separate hyperparameter and is swept; the number of candidates tried is four. - **RL64.** Every measure is printed with two runs; between the runs only the seed of the training episodes changes. The evaluation episodes are the same in every run. #### The Difference the Advantage Makes The block below rebuilds the environment and the policy, gathers the three methods in a single training procedure and measures at two learning steps. The three methods differ only in the number `A`. ```python # actor_critic.py — FICTIONAL. The same setup: five subscribers, one crew, horizon 30, discount 0.9. 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 FEATURES = SUBSCRIBERS + 1 # number of features: five delay classes + a constant 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 probabilities(th, s): # ACTOR: exponential normalization, the policy of 06 x = [v / 2.0 for v in s] + [1.0] z = [sum(t * v for t, v in zip(th[a], x)) for a in range(ACTIONS)] e = [math.exp(v - max(z)) for v in z] total = sum(e) return [v / total for v in e], x def state_value(w, s): # CRITIC: the value of the state, a row of six numbers return sum(a * b for a, b in zip(w, [v / 2.0 for v in s] + [1.0])) def choose(th, s, r): p, _ = probabilities(th, s) u, t = r(), 0.0 for a in range(ACTIONS): t += p[a] if u < t: return a return ACTIONS - 1 def run(policy, n=300): # the same 300 episodes as in 01 returns = [] for k in range(n): env, r = Environment(SEED + 1000 * k), rng(SEED + 90000 + k) s, total, factor = env.state(), 0.0, 1.0 for _ in range(HORIZON): s2, reward = env.step(policy(s, r)) total, factor, s = total + factor * reward, factor * DISCOUNT, s2 returns.append(total) return statistics.mean(returns) def episode_trace(th, seed): env, r = Environment(seed), rng(seed + 5) s, trace = env.state(), [] for _ in range(HORIZON): a = choose(th, s, r) s2, reward = env.step(a) trace.append((s, a, reward)) s = s2 return trace def returns_to_go(trace): G, g = [0.0] * len(trace), 0.0 for t in range(len(trace) - 1, -1, -1): g = trace[t][2] + DISCOUNT * g G[t] = g return G def train(seed, mode, rate, beta=0.05, budget=240, batch=2): th, w, baseline = [[0.0] * FEATURES for _ in range(ACTIONS)], [0.0] * FEATURES, [0.0] * HORIZON for t in range(budget // batch): grad_th, grad_w, mean_G = [0.0] * (ACTIONS * FEATURES), [0.0] * FEATURES, [0.0] * HORIZON for i in range(batch): trace = episode_trace(th, seed + 1000 * t + i) G = returns_to_go(trace) for u, (s, a, reward) in enumerate(trace): p, x = probabilities(th, s) if mode == "raw return": A = G[u] elif mode == "fixed baseline": A = G[u] - baseline[u] else: # learned critic: one-step advantage v2 = 0.0 if u == HORIZON - 1 else state_value(w, trace[u + 1][0]) A = reward + DISCOUNT * v2 - state_value(w, s) for j in range(FEATURES): grad_w[j] += A * x[j] / batch for b in range(ACTIONS): k = A * ((1.0 if b == a else 0.0) - p[b]) for j in range(FEATURES): grad_th[b * FEATURES + j] += k * x[j] / batch for u in range(HORIZON): mean_G[u] += G[u] / batch baseline = mean_G for b in range(ACTIONS): for j in range(FEATURES): th[b][j] += rate * grad_th[b * FEATURES + j] for j in range(FEATURES): w[j] += beta * grad_w[j] return th, w print(f"{'method':<22}{'step 0.01':>20}{'step 0.06':>20}") FINAL = {} for mode in ("raw return", "fixed baseline", "learned critic"): row = "" for rate in (0.01, 0.06): g = [run(lambda s, r, th=train(SEED + 300000 + k * 7919, mode, rate)[0]: choose(th, s, r)) for k in (1, 2)] FINAL[(mode, rate)] = g row += f"{g[0]:>10.3f}{g[1]:>10.3f}" print(f"{mode:<22}{row}") for rate in (0.01, 0.06): h, u = FINAL[("raw return", rate)], FINAL[("learned critic", rate)] c = FINAL[("fixed baseline", rate)] print(f"step {rate}: gain of the advantage over the raw return {min(u) - min(h):+.3f} / " f"{max(u) - max(h):+.3f}; band raw {max(h) - min(h):.3f}, " f"baseline {max(c) - min(c):.3f}, advantage {max(u) - min(u):.3f}") ``` ``` method step 0.01 step 0.06 raw return 15.840 19.962 14.207 17.218 fixed baseline 22.866 22.190 0.029 15.982 learned critic 21.154 21.100 23.401 23.755 step 0.01: gain of the advantage over the raw return +5.260 / +1.192; band raw 4.122, baseline 0.675, advantage 0.053 step 0.06: gain of the advantage over the raw return +9.194 / +6.537; band raw 3.011, baseline 15.953, advantage 0.354 ``` Reading the table by looking at a single column is misleading. At the small step (0.01) the best number is given by the **fixed baseline**: 22.866 and 22.190. The learned critic stays below it with 21.154 and 21.100, and the finding of `06` is not broken — a crude baseline does its job in this environment too. The difference the advantage makes over the raw return is still marked: +5.260 and +1.192. The distinction appears at the large step. When the learning step is raised to 0.06, both methods that rely on the full return break down: the raw return falls to 14.207 and 17.218, one run of the fixed baseline gives **0.029** — that is, almost nothing above the never-dispatch baseline — and its band rises to 15.953. The advantage estimate gives 23.401 and 23.755 at the same step and its band stays at 0.354. This is what the advantage really brings. It does not raise the level a little, it lowers the **wobble**; because the wobble falls, a larger learning step can be carried; and the large step extracts more progress from the same budget. The full return is the sum of thirty steps and carries the noise of thirty steps; the one-step advantage carries only one reward and two value estimates. This trade is not free. The full return, however much it wobbles, is an outcome that was actually lived. The one-step advantage hands twenty-nine of the thirty steps over to the estimate of the critic. If the critic is wrong, the advantage is not only wobbly but **systematically wrong**, and the error looks in the same direction in every run. This is not visible in the table above, because the critic works. The next block makes it stop working. #### When the Critic Breaks The two components share a single number: the same advantage updates both the actor and the critic. When the critic gives a wrong value, the actor shifts in the wrong direction; when the actor shifts, the distribution the critic is trying to learn changes as well. The block below sweeps the learning step of the critic and counts where this loop breaks. ```python LABELS = ("A1", "A2", "A3", "A4", "A5", "idle") ALL_STATES = [(a, b, c, e, f) for a in range(3) for b in range(3) for c in range(3) for e in range(3) for f in range(3)] def action_distribution(th, n=300): counts = [0] * ACTIONS for k in range(n): env, r = Environment(SEED + 1000 * k), rng(SEED + 90000 + k) s = env.state() for _ in range(HORIZON): a = choose(th, s, r) counts[a] += 1 s = env.step(a)[0] return counts print(f"{'critic step':>17}{'run 1':>9}{'run 2':>9}{'mean |V|':>14}" f"{'most chosen':>16}{'never visited':>15}") for beta in (0.00, 0.05, 0.50, 2.00): g = [] for k in (1, 2): th, w = train(SEED + 300000 + k * 7919, "learned critic", 0.06, beta) g.append(run(lambda s, r: choose(th, s, r))) if k == 1: d = action_distribution(th) mean_v = statistics.mean(abs(state_value(w, s)) for s in ALL_STATES) total, top = sum(d), d.index(max(d)) print(f"{beta:>17.2f}{g[0]:>9.3f}{g[1]:>9.3f}{mean_v:>14.3g}" f"{LABELS[top] + ' ' + format(max(d) / total, '.3f'):>16}" f"{sum(x == 0 for x in d[:SUBSCRIBERS]):>15}") ``` ``` critic step run 1 run 2 mean |V| most chosen never visited 0.00 22.506 22.620 0 A3 0.305 0 0.05 23.401 23.755 22.2 A3 0.258 0 0.50 -16.492 -18.772 2.6e+102 A1 1.000 4 2.00 -15.332 -14.622 5.84e+180 A5 1.000 4 ``` The first row is the form without a critic: because the step is zero the values stay at zero and the advantage reduces to the one-step reward. The result is 22.506 and 22.620 — not bad, because in this environment the reward mostly comes immediately. When the critic works (0.05) the number rises to 23.401 and 23.755; the mean value the critic produces is 22.2, that is, on the order of the measured return. What the critic gains is about one unit, and it should not be written down without being measured. The last two rows show the break. When the step of the critic is raised to 0.50 the values diverge to the order of $10^{102}$. The advantage no longer carries the reward but the own error of the critic; its sign becomes fixed independently of the state and all the probability of the actor shifts onto **a single action**: the share of `A1` is 1.000. **Four of the five subscribers are never visited.** The return is −18.772 — not only bad, but also below the 0.000 of never dispatching a crew, because every period the crew cost is paid and almost nothing is received in return. At step 2.00 the same collapse happens to another subscriber, `A5`; which action it piles onto is not even a result, it is an accident. This is the sharpest form of the rule of the course. Someone looking at the return column sees that both runs are bad but cannot know why. The fourth column — **the number of subscribers never visited** — states the reason directly: the policy collects its own data, and once it piles onto a single action nothing more is learned about four subscribers, and the critic can never estimate the states of those four subscribers correctly. A system that does not write down the collected data counts as unmeasured. #### Summary - In the actor–critic arrangement the actor chooses the action, the critic says the value of the state, and the update of the actor is scaled not by the return but by the **advantage**: the reward plus the discounted next state value minus the current state value. - Under the same budget of 240 episodes, with a step of 0.01 the raw return gives 15.840 and 19.962, the fixed baseline 22.866 and 22.190, the advantage 21.154 and 21.100. A crude baseline does not fall behind the learned critic at this step. - The distinction shows when the learning step is raised to 0.06: one run of the fixed baseline falls to the never-dispatch baseline with 0.029 and its band becomes 15.953, while the advantage gives 23.401 and 23.755 and keeps the band at 0.354. What the advantage brings is not level but stability, and stability makes the larger step carryable. - The own learning step of the critic is a hyperparameter: four candidates were tried, 0.05 gave the best and brought about one unit over the form without a critic. - When the step of the critic is raised to 0.50 the values diverge to the order of $10^{102}$, all the probability of the actor piles onto a single action, four of the five subscribers are never visited and the return falls below inaction with −18.772. #### Next Step In seven lessons the agent chose its own action and learned its result directly from the environment: a reward came from the subscriber to whom it sent the crew, and the subscribers it did not send to kept deteriorating. The response came at every step, right after the choice, and the choice changed the next state. The numbers were written above the same two baselines — never dispatching a crew 0.000 and a random action 10.432 — and the 20.621 of the rule policy was the threshold to be passed: the table of `05` 24.495, the replay-buffer network of the same lesson 26.233, the actor with the advantage estimate of this lesson 23.755. The third number of the measure was always in the same form — which states were never seen, which action was never tried. The next topic breaks the same loop at one point. The action is no longer something the agent **does**, it is **an option offered** to a person: which service item to recommend to a subscriber. The recommendation is shown, but its result is seen only if that person chooses it — an item that is not shown is never scored, and an item that is not scored is never shown again. The collected data is no longer the states the agent has wandered through but **the items it showed, and the items never learned because they were never shown**. The next lesson builds the baseline of this arrangement and measures the surprisingly high baseline of the field: recommending the most used item to everyone. ## Recommender Systems Measuring recommendation in a setup where an item that is not shown is not scored and an item that is not scored is not shown: how surprisingly high recommending the most popular item to everyone is in a sparse subscriber-item matrix and the difference between implicit and explicit feedback, the number of subscribers for whom content-based recommendation cannot produce any recommendation and how much the recommendations resemble one another, the ranking that moves with the number of neighbors and the subscribers left without neighbors as sparsity grows, the two separate rankings that come from counting an unobserved cell as zero versus skipping it, how many subscribers and items are cold and how many each remedy warms up and at what cost, a ranking that looks good offline giving a different number when it collects data with its own decisions, and the number of items that are never shown and the growth of popularity bias when the system is fed with its own recommendations. ### The Recommendation Problem Source: https://academia.sh/en/courses/reinforcement-and-recommender/recommendation-problem Measuring recommendation in a fictional subscriber-item interaction matrix: 360 subscribers and 24 service items meet in only 577 of 8,640 cells, the sparsity is 0.9332, and 80 subscribers have no interaction at all. The baseline is to offer everyone the item chosen most often in training; its hit rate at five is 0.6527, against 0.2036 for a random order. When the same data is read implicitly and read with explicit scores, the two top fives share only one item, recommending by average score gives a hit rate of 0.1497, 16 of the 24 items have fewer than ten scores, and the 5,638 cells that were never shown have a score count of zero. In seven lessons the agent chose its own action and learned the result from the environment: what happened when a crew was sent to a subscriber and what happened when it was not was recorded step by step. Now the action changes hands. The only thing the system can do is to **offer one option** to a subscriber, and the result becomes visible only if that subscriber chooses it. The result of an option that is not offered is never born; why an option that was offered but not chosen was not chosen is not recorded. The collected data is the trace of the system's own offering decisions. This lesson builds the data of that setup and produces two numbers: the hit rate at five of the baseline that offers everyone the same item, and how far apart the two rankings are that come from reading the same data implicitly and explicitly. The rule of the course is paid for here for the first time: **an item that is not shown is not scored, and an item that is not scored is not shown.** - **RS1.** The dataset is **fictional**, seed 20260218: 360 subscribers, 24 service items, 8,640 cells. The items are service applications of the regional measurement network (such as a tariff change, a meter replacement, an installment plan, a remote reading application). - **RS2.** Three events are generated separately: **impression**, **selection**, **score**. An item cannot be selected without being shown and cannot be scored without being selected. The chain was put into the setup on purpose. - **RS3.** A subscriber's true propensity toward an item is inside the generator and is read **only for measurement**; no method sees it. - **RS4.** **Implicit feedback** is the selection itself and is 0/1. **Explicit feedback** is a score between 1 and 5 and is left in only some of the selections. - **RS5.** Which item was shown to whom in the past is **biased by its share**: an item that is applied for often was offered a lot, a rare one little. This bias was put into the setup on purpose. - **RS6.** Held-out set: the **last** interaction of every subscriber with at least two interactions. The rest is the training set. - **RS7.** The measure is the **hit rate at k**: whether the subscriber's held-out item is within the first k recommendations. The definitions of precision and recall were set up in the Supervised Learning course and are not repeated here. - **RS8.** Two baselines are built: the **random order** and the **order of the items chosen most often in training**. The second is the real baseline, because it contains no personalization and still feeds on the curve of the catalog. #### The Interaction Matrix and Sparsity The row of the matrix is a subscriber, the column a service item. A cell being filled says that the subscriber selected that item; being empty is a mixture of two separate things and cannot be told apart: the item may have been offered but not selected, or it may never have been offered. The setup generates the two separately, so during measurement it can be counted how much of each there is. ```python # COMMON -- FICTIONAL. The subscriber x service item interaction matrix is built inside the lesson. # Impression, selection and score are generated separately: an item is first SHOWN, then # it can be selected, and only if it is selected can it be scored. SEED, M32 = 20260218, 0xFFFFFFFF 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 ITEMS = [ # (name, domain, channel, paid, commitment, appointment, base_share) ("auto_payment_instruction", "billing", "online", 0, 0, 0, 0.90), ("e_invoice_switch", "alert", "online", 0, 0, 0, 0.85), ("payment_reminder_sms", "alert", "online", 0, 0, 0, 0.78), ("installment_plan", "billing", "branch", 0, 1, 0, 0.62), ("remote_reading_application", "meter", "field", 0, 1, 1, 0.55), ("outage_alert_subscription", "alert", "online", 0, 0, 0, 0.50), ("debt_restructuring", "billing", "branch", 0, 1, 0, 0.44), ("address_update", "subscription", "online", 0, 0, 0, 0.40), ("meter_replacement", "meter", "field", 1, 0, 1, 0.36), ("consumption_report_subscription", "alert", "online", 0, 0, 0, 0.32), ("invoice_dispute_record", "billing", "branch", 0, 0, 0, 0.28), ("subscription_transfer", "subscription", "branch", 0, 0, 0, 0.25), ("illicit_use_check_appointment", "meter", "field", 0, 0, 1, 0.22), ("installation_maintenance_package", "technical", "field", 1, 1, 1, 0.19), ("second_meter_request", "meter", "field", 1, 0, 1, 0.16), ("business_tariff_switch", "subscription", "branch", 0, 1, 0, 0.14), ("pressure_regulator_mounting", "technical", "field", 1, 0, 1, 0.12), ("garden_irrigation_tariff", "subscription", "branch", 0, 1, 0, 0.10), ("meter_relocation", "meter", "field", 1, 0, 1, 0.09), ("common_area_sharing_record", "subscription", "branch", 0, 1, 0, 0.08), ("installation_compliance_report", "technical", "field", 1, 0, 1, 0.07), ("late_interest_waiver", "billing", "branch", 0, 0, 0, 0.06), ("mobile_access_permission", "alert", "online", 0, 0, 0, 0.05), ("extra_line_installation", "technical", "field", 1, 1, 1, 0.04), ] SEGMENT = { # propensity of the segment toward the domains; used only inside the generator "saver": {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6}, "payer": {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3}, "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9}, "new": {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7}, } SEGMENT_NAMES = list(SEGMENT) rq = rng(SEED + 101) QUALITY = [0.25 + 0.70 * rq() for _ in ITEMS] # the item's own satisfaction N_SUBSCRIBERS, N_ITEMS = 360, len(ITEMS) SUBSCRIBERS, IMPRESSIONS, INTERACTIONS, SCORES, PROPENSITY = [], {}, {}, {}, {} for i in range(N_SUBSCRIBERS): r = rng(SEED + 7919 * i) a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)] activity = 0.35 + 1.15 * r() ** 1.6 SUBSCRIBERS.append(a) for j, (name, domain, channel, paid, commitment, appointment, share) in enumerate(ITEMS): propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55) PROPENSITY[(a, j)] = propensity if r() < min(0.95, share ** 0.55 * 0.72): # was it shown IMPRESSIONS[(a, j)] = 1 if r() < propensity: # was it selected INTERACTIONS[(a, j)] = r() # value: sequence stamp if r() < 0.32: # did it leave a score raw = (0.16 + 0.50 * SEGMENT[segment][domain] / 1.9 + 0.42 * QUALITY[j] + 0.26 * (r() - 0.5)) SCORES[(a, j)] = max(1, min(5, int(round(raw * 5)))) else: r(), r(), r() CELLS = N_SUBSCRIBERS * N_ITEMS counts = {} for (a, j) in INTERACTIONS: counts[a] = counts.get(a, 0) + 1 print("matrix", N_SUBSCRIBERS, "subscribers x", N_ITEMS, "items =", CELLS, "cells") for name, d in (("impression", IMPRESSIONS), ("interaction", INTERACTIONS), ("score", SCORES)): print(f" {name:12s} {len(d):5d} fill {len(d)/CELLS:.4f} sparsity {1-len(d)/CELLS:.4f}") print("subscribers with no interaction", N_SUBSCRIBERS - len(counts), " mean per subscriber", round(len(INTERACTIONS) / N_SUBSCRIBERS, 3), " max", max(counts.values())) ``` ``` matrix 360 subscribers x 24 items = 8640 cells impression 3002 fill 0.3475 sparsity 0.6525 interaction 577 fill 0.0668 sparsity 0.9332 score 218 fill 0.0252 sparsity 0.9748 subscribers with no interaction 80 mean per subscriber 1.603 max 7 ``` The three fill rates describe three separate problems. The impression matrix is 0.3475 full, the selection matrix 0.0668, the score matrix 0.0252. The sparsity at the selection level is 0.9332: out of every hundred cells, sixty-seven were offered but not selected and twenty-six were never offered. An average of 1.603 interactions falls to each subscriber, and 80 of the 360 subscribers have no interaction at all. Deciding what to recommend to a subscriber in this table means drawing a decision from a matrix in which most rows are almost entirely empty. #### Offering Everyone the Same Item The baseline of the recommendation field is a procedure without personalization: ranking the items chosen most often in the training set and offering everyone the same list. This baseline does not tell any subscriber apart from another, yet it feeds on the skew of the catalog and, surprisingly, climbs high. A second baseline is placed next to it: ordering the items the subscriber has not seen in a random order. ```python # Split: the LAST interaction of every subscriber with at least two interactions goes to the held-out set. TRAIN, HELD_OUT, SEEN = {}, {}, {} log = {} for (a, j), stamp in INTERACTIONS.items(): log.setdefault(a, []).append((stamp, j)) for a, entries in log.items(): entries.sort() if len(entries) >= 2: HELD_OUT[a] = entries[-1][1] entries = entries[:-1] for stamp, j in entries: TRAIN[(a, j)] = 1 SEEN.setdefault(a, set()).add(j) n_chosen = [0] * N_ITEMS for (a, j) in TRAIN: n_chosen[j] += 1 ranked = sorted(range(N_ITEMS), key=lambda j: -n_chosen[j]) def hit_rate(recommend, K): return sum(1 for a in HELD_OUT if HELD_OUT[a] in recommend(a)[:K]) / len(HELD_OUT) def baseline_popularity(a): return [j for j in ranked if j not in SEEN.get(a, set())] rg = rng(SEED + 31) def baseline_random(a): candidates = [j for j in range(N_ITEMS) if j not in SEEN.get(a, set())] for i in range(len(candidates) - 1, 0, -1): t = int(rg() * (i + 1)) candidates[i], candidates[t] = candidates[t], candidates[i] return candidates print("training", len(TRAIN), "interactions / held-out", len(HELD_OUT), "subscribers") print("five items chosen most often in training:") for j in ranked[:5]: print(f" {ITEMS[j][0]:32s} {n_chosen[j]:3d}") for K in (3, 5): p, s = hit_rate(baseline_popularity, K), hit_rate(baseline_random, K) print(f"hit rate at {K}: popularity {p:.4f} random {s:.4f} ratio {p/s:.2f}") print("catalog coverage of the popularity baseline", len({j for a in HELD_OUT for j in baseline_popularity(a)[:5]}), "/", N_ITEMS) ``` ``` training 410 interactions / held-out 167 subscribers five items chosen most often in training: payment_reminder_sms 68 e_invoice_switch 64 auto_payment_instruction 47 installment_plan 39 debt_restructuring 27 hit rate at 3: popularity 0.5509 random 0.1437 ratio 3.83 hit rate at 5: popularity 0.6527 random 0.2036 ratio 3.21 catalog coverage of the popularity baseline 9 / 24 ``` The baseline without personalization catches the held-out item of 109 of the 167 subscribers in the first five: hit rate 0.6527. The random order stays at 0.2036 on the same measure, a ratio of 3.21. Going down to the first three, the baseline gives 0.5509 and the ratio rises to 3.83. This number is a threshold for the rest of this course: if a recommendation method does not exceed 0.6527, it is no better than a list that makes no distinction between subscribers. The price the baseline pays is in the fourth line: a total of **9 distinct items** appear in the first-five lists of the 167 subscribers, while there are 24 items in the catalog. Fifteen items are never recommended to any subscriber. The baseline buys its high hit rate by making fifteen items of the catalog completely invisible, and an item that is not visible does not enter the data of the next period either. #### Implicit and Explicit Feedback Implicit feedback is the selection itself: the subscriber applied or did not. Explicit feedback is the score the subscriber left. The two look as if they measure the same catalog, but they count different things. The implicit signal measures **volume** and carries the impression count inside it; the explicit signal measures **satisfaction after selecting** and comes only from a part of those who selected. ```python imp, sel, n_scores, total = ([0] * N_ITEMS for _ in range(4)) for (a, j) in IMPRESSIONS: imp[j] += 1 for (a, j) in INTERACTIONS: sel[j] += 1 for (a, j), p in SCORES.items(): n_scores[j] += 1 total[j] += p mean_score = [total[j] / n_scores[j] if n_scores[j] else 0.0 for j in range(N_ITEMS)] rank_implicit = sorted(range(N_ITEMS), key=lambda j: -sel[j]) rank_explicit = sorted([j for j in range(N_ITEMS) if n_scores[j] > 0], key=lambda j: -mean_score[j]) print(f"{'item':32s} {'impressions':>11s} {'selections':>10s} {'scores':>6s} {'average':>9s}") for j in rank_implicit[:3] + rank_explicit[:3]: print(f"{ITEMS[j][0]:32s} {imp[j]:11d} {sel[j]:10d} {n_scores[j]:6d} {mean_score[j]:9.2f}") print("implicit top 5 and explicit top 5 intersection", len(set(rank_implicit[:5]) & set(rank_explicit[:5]))) print("items never selected", sum(1 for j in range(N_ITEMS) if sel[j] == 0), " items with fewer than ten scores", sum(1 for j in range(N_ITEMS) if n_scores[j] < 10)) print("cells never shown", CELLS - len(IMPRESSIONS), " their score count", sum(1 for k in SCORES if k not in IMPRESSIONS)) print("subscribers who left no score", N_SUBSCRIBERS - len({a for (a, j) in SCORES})) rank_score = sorted(range(N_ITEMS), key=lambda j: -mean_score[j]) print(f"hit rate at 5 -- by average score {hit_rate(lambda a: [j for j in rank_score if j not in SEEN.get(a, set())], 5):.4f}") ``` ``` item impressions selections scores average e_invoice_switch 215 93 30 3.27 payment_reminder_sms 236 89 31 3.06 auto_payment_instruction 242 73 24 3.83 address_update 158 37 14 4.79 second_meter_request 96 9 3 4.33 business_tariff_switch 91 5 4 4.25 implicit top 5 and explicit top 5 intersection 1 items never selected 1 items with fewer than ten scores 16 cells never shown 5638 their score count 0 subscribers who left no score 205 hit rate at 5 -- by average score 0.1497 ``` The number of items common to the first five of the two rankings is **1**. The three items at the top of the implicit ranking each received more than two hundred impressions and their average scores lie between 3.06 and 3.83; two of the items at the top of the explicit ranking have score counts of 3 and 4. Recommending by average score drops the hit rate at five to 0.1497, which is even below the 0.2036 of the random order. The source of the number is in the third and fourth lines. 16 of the catalog's 24 items have fewer than ten scores, because an item shown little is selected little, and an item selected little is scored little. The 5,638 cells that were never shown have a score count of zero; this is not a finding but the definition of the chain. 205 of the subscribers left no score at all. Explicit feedback carries a richer signal, but it carries it where it carries it: on the items the system showed before. **An item that is not shown is not scored**, and a list ranked by average score says nothing about the part of the catalog that is not visible. The collected data is the third number of this lesson and consists of two parts: the 5,638 cells that were never shown and the 15 items outside the lists the baseline recommends. If these two numbers are not written when a recommendation method is measured, it is not known which catalog the measure belongs to. #### Summary - The fictional matrix meets 360 subscribers and 24 service items in 8,640 cells; the impression fill rate is 0.3475, the selection 0.0668, the score 0.0252. At the selection level the sparsity is 0.9332 and 80 subscribers have no interaction at all. - The baseline offers everyone, in the same order, the items chosen most often in training; its hit rate at five is 0.6527 and at three 0.5509. The random order gives 0.2036 and 0.1437 on the same measures. - The price of the baseline is coverage: only 9 distinct items appear in the first-five lists of 167 subscribers, and fifteen items are recommended to no subscriber. - Implicit and explicit feedback produce two separate rankings in the same catalog; the intersection of their first fives is one, and recommending by average score gives a hit rate of 0.1497. - The explicit signal is sparse and depends on impressions: 16 of the 24 items have fewer than ten scores, 205 subscribers left no score, and the 5,638 cells that were never shown have a score count of zero. #### Next Step The baseline set a threshold with 0.6527, but it did so by never showing fifteen items of the catalog, and it has no separate word for the 80 subscribers who have no interaction. The first question is this: even when no data has come from the subscriber, is there something known about the item itself. In the catalog each item's domain, channel, whether it is paid, and whether it requires a commitment and an appointment are written down. The next lesson extracts a profile per subscriber from these features, ranks the recommendations by similarity to the profile, and measures two numbers: for how many subscribers no recommendation can be produced at all, and how similar the recommendations produced are to one another. ### Content-Based Recommendation Source: https://academia.sh/en/courses/reinforcement-and-recommender/content-based-recommendation Measuring a recommendation that builds a subscriber profile from the features of the item: with an eleven-component binary feature vector a profile is built for 280 of the 360 subscribers, and no recommendation can be produced at all for 80. The hit rate at five is 0.4431, below the 0.6527 of the popularity baseline, but the catalog coverage is 24 instead of 9. The price is similarity: the intra-list similarity of the top-five lists is 0.6769 and 0.715 of the items in a list come from a single domain. A new item that has never been shown is ranked for all 280 subscribers, enters the top ten of 191 of them, and has an average position of 11.55 among 25 items; the same item is last in the popularity ranking. The baseline of the previous lesson raised the hit rate at five to 0.6527, but it did so by showing only 9 of the catalog's 24 items, and to the 80 subscribers with no interaction it said the same thing it said to everyone. Both shortcomings come from the same place: the baseline looks only at the **interaction counts**; it does not look at what the item is. The catalog has written information per item: which domain it belongs to, which channel it runs through, whether it is paid, and whether it requires a commitment and an appointment. This lesson builds a similarity from those columns, describes the subscriber as the average of the items they selected, and measures two numbers: **for how many subscribers no recommendation can be produced at all** and **how similar the recommendations produced are to one another**. - **RS9.** The setup and the seed are the same as in the previous lesson; the matrix, the split and the popularity baseline are rebuilt exactly and give the same numbers. - **RS10.** The feature vector has **eleven components**: five domains, three channels and three binary flags. The components are 0/1 and the vector is brought to unit length. - **RS11.** The subscriber profile is the sum of the feature vectors of the items the subscriber **selected** in the training set, brought to unit length. Scores are not used; the profile comes from the implicit signal. - **RS12.** The similarity of two unit vectors is their dot product and lies between 0 and 1. In case of a tie the catalog order breaks it; floating-point values are not compared directly but used as a sort key. - **RS13.** Coverage is **two separate numbers**: for how many subscribers a recommendation could be produced and how many distinct items entered the list of at least one subscriber. - **RS14.** The **intra-list similarity** of a list is the average similarity of all item pairs in the list. - **RS15.** At the end there is a new item in the catalog: its features are written, it has never been shown, and it has no interaction. #### Rebuilding the Matrix If the measurement is not done on the same data, the numbers of the two lessons cannot be compared. The block below rebuilds the setup, the split and the popularity baseline with the same seed; its two-line output must be exactly the same as the sparsity and hit rate numbers of the previous lesson. ```python # COMMON -- FICTIONAL. The matrix of the previous lesson is rebuilt with the same seed; this time # the feature columns of the catalog will be read too. SEED, M32 = 20260218, 0xFFFFFFFF 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 ITEMS = [ # (name, domain, channel, paid, commitment, appointment, base_share) ("auto_payment_instruction", "billing", "online", 0, 0, 0, 0.90), ("e_invoice_switch", "alert", "online", 0, 0, 0, 0.85), ("payment_reminder_sms", "alert", "online", 0, 0, 0, 0.78), ("installment_plan", "billing", "branch", 0, 1, 0, 0.62), ("remote_reading_application", "meter", "field", 0, 1, 1, 0.55), ("outage_alert_subscription", "alert", "online", 0, 0, 0, 0.50), ("debt_restructuring", "billing", "branch", 0, 1, 0, 0.44), ("address_update", "subscription", "online", 0, 0, 0, 0.40), ("meter_replacement", "meter", "field", 1, 0, 1, 0.36), ("consumption_report_subscription", "alert", "online", 0, 0, 0, 0.32), ("invoice_dispute_record", "billing", "branch", 0, 0, 0, 0.28), ("subscription_transfer", "subscription", "branch", 0, 0, 0, 0.25), ("illicit_use_check_appointment", "meter", "field", 0, 0, 1, 0.22), ("installation_maintenance_package", "technical", "field", 1, 1, 1, 0.19), ("second_meter_request", "meter", "field", 1, 0, 1, 0.16), ("business_tariff_switch", "subscription", "branch", 0, 1, 0, 0.14), ("pressure_regulator_mounting", "technical", "field", 1, 0, 1, 0.12), ("garden_irrigation_tariff", "subscription", "branch", 0, 1, 0, 0.10), ("meter_relocation", "meter", "field", 1, 0, 1, 0.09), ("common_area_sharing_record", "subscription", "branch", 0, 1, 0, 0.08), ("installation_compliance_report", "technical", "field", 1, 0, 1, 0.07), ("late_interest_waiver", "billing", "branch", 0, 0, 0, 0.06), ("mobile_access_permission", "alert", "online", 0, 0, 0, 0.05), ("extra_line_installation", "technical", "field", 1, 1, 1, 0.04), ] SEGMENT = { "saver": {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6}, "payer": {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3}, "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9}, "new": {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7}, } SEGMENT_NAMES = list(SEGMENT) rq = rng(SEED + 101) QUALITY = [0.25 + 0.70 * rq() for _ in ITEMS] N_SUBSCRIBERS, N_ITEMS = 360, len(ITEMS) SUBSCRIBERS, INTERACTIONS = [], {} for i in range(N_SUBSCRIBERS): r = rng(SEED + 7919 * i) a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)] activity = 0.35 + 1.15 * r() ** 1.6 SUBSCRIBERS.append(a) for j, (name, domain, channel, paid, commit, appt, share) in enumerate(ITEMS): propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55) if r() < min(0.95, share ** 0.55 * 0.72): # was it shown if r() < propensity: # was it selected INTERACTIONS[(a, j)] = r() if r() < 0.32: r() # score draw: not read here else: r(), r(), r() TRAIN, HELD_OUT, SEEN, log = {}, {}, {}, {} for (a, j), stamp in INTERACTIONS.items(): log.setdefault(a, []).append((stamp, j)) for a, entries in log.items(): entries.sort() if len(entries) >= 2: HELD_OUT[a] = entries[-1][1] entries = entries[:-1] for stamp, j in entries: TRAIN[(a, j)] = 1 SEEN.setdefault(a, set()).add(j) n_chosen = [0] * N_ITEMS for (a, j) in TRAIN: n_chosen[j] += 1 ranked = sorted(range(N_ITEMS), key=lambda j: -n_chosen[j]) def hit_rate(recommend, K): return sum(1 for a in HELD_OUT if HELD_OUT[a] in recommend(a)[:K]) / len(HELD_OUT) def baseline(a): return [j for j in ranked if j not in SEEN.get(a, set())] print("interaction", len(INTERACTIONS), " sparsity", round(1 - len(INTERACTIONS) / (N_SUBSCRIBERS * N_ITEMS), 4)) print("held-out subscribers", len(HELD_OUT), " baseline top 5 hit rate", round(hit_rate(baseline, 5), 4)) ``` ``` interaction 577 sparsity 0.9332 held-out subscribers 167 baseline top 5 hit rate 0.6527 ``` The two lines are exactly the same as the previous lesson: 577 interactions, 0.9332 sparsity, 167 held-out subscribers and a baseline hit rate of 0.6527. This repetition is not a ceremony but a precondition of the measurement: the numbers of two methods are comparable only when they are read on the same split, the same held-out set and the same baseline. Because the setup is regenerated from the same seed, every difference in between comes from the method. #### From Feature to Profile Every item turns into an eleven-component vector and is brought to unit length; this way an item with many features does not stand out for that reason alone. A paid, commitment-bound, appointment-bound field item carries 1 in six components, a free online item in only two; without the scaling the first would look closer to every profile. Because the components are binary, many equal similarities come out, and ties are broken by the catalog order; this is an arbitrary rule and was written to keep the result constant from run to run. The profile of a subscriber is the sum of the vectors of the items they selected: the profile of a subscriber who made two field applications stretches in the field direction. The recommendation is to rank the items that are closest to the profile and have not been selected before. If the subscriber has no selection at all there is no vector to add up and the profile cannot be built. ```python import math DOMAINS = ["billing", "meter", "subscription", "alert", "technical"] CHANNELS = ["online", "field", "branch"] def features(k): v = [1.0 if k[1] == x else 0.0 for x in DOMAINS] v += [1.0 if k[2] == x else 0.0 for x in CHANNELS] v += [float(k[3]), float(k[4]), float(k[5])] n = math.sqrt(sum(x * x for x in v)) return [x / n for x in v] def similarity(u, v): return sum(x * y for x, y in zip(u, v)) FEAT = [features(k) for k in ITEMS] DIM = len(FEAT[0]) PROFILE = {} for a in SUBSCRIBERS: seen = SEEN.get(a, set()) if not seen: continue # profile cannot be built p = [sum(FEAT[j][d] for j in seen) for d in range(DIM)] n = math.sqrt(sum(x * x for x in p)) PROFILE[a] = [x / n for x in p] def content_based(a): if a not in PROFILE: return [] # no recommendation can be produced return sorted((j for j in range(len(FEAT)) if j not in SEEN.get(a, set())), key=lambda j: (-similarity(PROFILE[a], FEAT[j]), j)) def coverage(recommend, K=5): return len({j for a in HELD_OUT for j in recommend(a)[:K]}) def intra_similarity(recommend, K=5): t = n = 0 for a in HELD_OUT: entries = recommend(a)[:K] for x in range(len(entries)): for y in range(x + 1, len(entries)): t += similarity(FEAT[entries[x]], FEAT[entries[y]]) n += 1 return t / n print("subscribers with a profile", len(PROFILE), "/", N_SUBSCRIBERS, " without", N_SUBSCRIBERS - len(PROFILE)) for K in (3, 5): print(f"top {K}: content {hit_rate(content_based, K):.4f} baseline {hit_rate(baseline, K):.4f}") print("catalog coverage content", coverage(content_based), " baseline", coverage(baseline), "/", N_ITEMS) print(f"top 5 intra-list similarity content {intra_similarity(content_based):.4f} baseline {intra_similarity(baseline):.4f}") t = 0 for a in HELD_OUT: domains = [ITEMS[j][1] for j in content_based(a)[:5]] t += max(domains.count(x) for x in set(domains)) print("mean share of the most frequent domain in the top 5", round(t / len(HELD_OUT) / 5, 4)) ``` ``` subscribers with a profile 280 / 360 without 80 top 3: content 0.2874 baseline 0.5509 top 5: content 0.4431 baseline 0.6527 catalog coverage content 24 baseline 9 / 24 top 5 intra-list similarity content 0.6769 baseline 0.3827 mean share of the most frequent domain in the top 5 0.715 ``` Content-based recommendation stays below the baseline: its hit rate at five is 0.4431, 0.2096 behind the baseline's 0.6527; at three the gap is bigger, 0.2874 against 0.5509. The source of the gap is what the method sees. The probability of an item being selected comes in the setup from two factors: the subscriber's propensity toward that domain and the item's own prevalence. The feature vector carries only the first; the second, that is how many subscribers selected that item, is not written in the feature columns at all. The method replaces the question "what will this subscriber select" with the question "what resembles what this subscriber selected" and drops the prevalence. The coverage column looks the other way. The baseline put only 9 items into the lists of 167 subscribers; content-based recommendation puts **all 24 items** into at least one list. On the other hand the lists narrow within themselves: the intra-list similarity of the top five is 0.3827 for the baseline and 0.6769 for content-based recommendation, and on average 0.715 of the items in the top five come from a single domain. To a subscriber who made a field application, four more field applications are recommended. Diversity increases at the catalog level and decreases at the subscriber level, and if the two numbers are not written separately, coverage alone misleads. Subscriber coverage is the other half of coverage: a profile can be built for 280 of the 360 subscribers, and **no recommendation can be produced at all for 80**. These 80 subscribers will see nothing in the next period either, will select nothing, and their rows will keep staying empty. Three numbers answer three separate questions and none replaces another. The hit rate asks "is the held-out item in the list" and the content-based method loses here. The catalog coverage asks "how many items never appear" and it wins here. The intra-list similarity asks "are the five items in the list repetitions of one another" and it loses here. A report that writes only the hit rate makes the method look needless; a report that writes only the coverage makes it look better than it is. #### New Item and New Subscriber Cold start has two directions and content-based recommendation gives two separate answers to them. Think of an item in the catalog that has never been shown: its interaction count is zero, but its features were written together with the catalog. Think also of a subscriber who has no interaction: there are no features, because features belong to the item, not to the subscriber. ```python # A new item that has never been shown is added to the catalog: it has no interaction, # only features. NEW = ("mobile_meter_reading", "meter", "online", 0, 0, 0, 0.0) FEAT.append(features(NEW)) NJ = len(FEAT) - 1 top5 = sum(1 for a in PROFILE if NJ in content_based(a)[:5]) top10 = sum(1 for a in PROFILE if NJ in content_based(a)[:10]) position = sum(content_based(a).index(NJ) + 1 for a in PROFILE) / len(PROFILE) print(f"{NEW[0]}: content-based top 5 -> {top5} subscribers, top 10 -> {top10} subscribers") print("mean position", round(position, 2), "/", len(FEAT), " position in the baseline ranking", len(FEAT), "(interaction count 0)") print("subscribers without a profile", N_SUBSCRIBERS - len(PROFILE), " content-based recommendation count", sum(len(content_based(a)) for a in SUBSCRIBERS if a not in PROFILE), " given by the baseline", 5 * (N_SUBSCRIBERS - len(PROFILE))) ``` ``` mobile_meter_reading: content-based top 5 -> 13 subscribers, top 10 -> 191 subscribers mean position 11.55 / 25 position in the baseline ranking 25 (interaction count 0) subscribers without a profile 80 content-based recommendation count 0 given by the baseline 400 ``` The new item is ranked for **all** 280 subscribers: although it has never been shown, its average position is 11.55 among 25 items, and it enters the top ten of 191 subscribers and the top five of 13. In a ranking that relies on interaction counts the same item is last for everyone, and as long as it stays last it cannot collect interactions because it is not shown. The feature is what breaks this loop: it carries a piece of information about the item that is known **before the interaction**. The same help is not there on the subscriber side. For the 80 subscribers without a profile the content-based method produces a total of **zero** recommendations; the baseline without personalization gives the same subscribers 400 recommendations, all the same five items. The asymmetry comes from the definition of the method: the features of the item are written in the catalog, those of the subscriber are not. The only thing known about a subscriber is their past selections, and about a subscriber with no past selection nothing is known. This is the collected data of this lesson: 80 subscribers receive no recommendation, and because they cannot receive one they add no row to the interaction matrix of the next period either. #### Summary - The feature vector has eleven components; the subscriber profile is the sum, brought to unit length, of the vectors of the items selected, and it can be built for 280 of the 360 subscribers. - The hit rate at five of content-based recommendation is 0.4431 and at three 0.2874; the popularity baseline gives 0.6527 and 0.5509 on the same measures. The feature columns do not carry the prevalence of the item. - The catalog coverage rises from 9 to 24, but the intra-list similarity of the lists rises from 0.3827 to 0.6769 and 0.715 of the items in the top five come from a single domain. - Coverage is two numbers: no recommendation can be produced for 80 subscribers, and because nothing is shown to these subscribers their rows keep staying empty. - A new item that has never been shown is ranked for all 280 subscribers, enters the top ten of 191 of them and has an average position of 11.55; in the ranking that relies on interaction counts the same item is last. #### Next Step Content-based recommendation counts two items as close because their feature columns are similar. That is why it can rank the new item from the first day, and that is why it recommends five items from the same domain to a subscriber. One thing was never used in the measurement: the **similarity of subscribers to one another**. Two subscribers who selected the same three items share something that has no trace in the feature columns; a fourth item that one has selected and the other has not yet selected is a recommendation candidate. The next lesson builds the similarity not from the features of the item but from the **rows and columns of the interaction matrix**, measures how much the number of neighbors moves the ranking, and counts the subscribers for whom no neighbor can be found at all as sparsity grows. ### Collaborative Filtering Source: https://academia.sh/en/courses/reinforcement-and-recommender/collaborative-filtering Measuring recommendation that is produced not from the features of the item but from subscribers resembling one another, and where this similarity breaks in sparsity: in a matrix with 410 training interactions the baseline of the most chosen item gives 0.6527 hit rate@5 and shows 9 of the 24 items, while user-based filtering with three neighbors gives 0.6946 and shows 16 items, but 4.07 of its top five already belong to the baseline list. The number of neighbors is a hyperparameter and moves between 0.5988 and 0.6946 across seven candidates; the item-based setup stays at 0.6467 at its best setting and falls below the baseline. When the training sparsity is raised from 0.9525 to 0.9888, the number of held-out subscribers with no neighbor at all goes from 0 to 105, and the measure staying in place comes not from the method but from the order of the catalog. The previous lesson produced the recommendation **from the features of the item**. The domain, channel and whether it was paid for were written in the catalog for every item. A profile was extracted from the subscriber's history and the items were ranked by their similarity to it. In that setup every subscriber is on their own: whatever is in their own file is looked at, and no other subscriber's file is looked at. Yet there is a table of 360 subscribers at hand, and inside it is information that was never used: **subscribers resemble one another.** If two subscribers have both applied for an installment plan and debt restructuring, a third item that one applied for is a candidate for the other as well, and this prediction can be made without looking at the features of the items at all. This is **collaborative filtering**: the recommendation is produced not from what the item is but from **who uses it together with whom**. This lesson measures how much the number of neighbors moves the ranking, and where the neighborhood breaks as the matrix gets sparser: between two subscribers with no common item the similarity is not defined, and sparsity produces exactly this. - **RS21.** The setup, the dataset, the split rule and the measure carry on exactly from the first lesson: **360 subscribers, 24 service items**, seed 20260218, and the **last** interaction of a subscriber with at least two interactions goes to the held-out set. The code is rebuilt here and the numbers do not change. - **RS22.** From the item catalog only the **domain** and the **base share** are read in this lesson; collaborative filtering never looks at the features. - **RS23.** The measure is **hit rate@5** and next to it the **mean rank**. Larger is better for the first, smaller for the second. The candidate set is the items the subscriber has not seen in training. - **RS24.** The baseline is **the order of the most chosen item** from the first lesson; it makes no distinction between subscribers and is the threshold a method has to pass. - **RS25.** Similarity is **the number of common items of two binary vectors divided by the square root of the product of their lengths**. A pair with no common item **never enters** the similarity list; a zero similarity is not recorded, and this is the definition of having no neighbor. - **RS26.** The number of neighbors $K$ is a **hyperparameter**. **7** candidates were tried on the user-based side and **6** on the item-based side; no separate hyperparameter-selection set was set aside, because what is measured is not the best setting but how much the setting moves the ranking. - **RS27.** Among items with equal scores the order is resolved by the **catalog index**. The catalog is in decreasing order of base share, so for a subscriber whose scores are all zero the ranking silently falls to the popularity order. The last section measures this. - **RS28.** The **number of items shown** is the union of the top fives of the held-out subscribers and is the third number of the course: an item that is never shown is never selected. - **RS29.** In the sparsity sweep a **share** of the training interactions is kept and the held-out items never change; this way the five rows are read on the same 167 subscribers. #### No Neighbor Without a Common Item The first block builds the setup, the split and the baseline. ```python # The setup catalog comes from the first lesson; here only the item's domain and base share are needed. SEED, M32, N_SUBSCRIBERS = 20260218, 0xFFFFFFFF, 360 ITEMS = [("billing", 0.90), ("alert", 0.85), ("alert", 0.78), ("billing", 0.62), ("meter", 0.55), ("alert", 0.50), ("billing", 0.44), ("subscription", 0.40), ("meter", 0.36), ("alert", 0.32), ("billing", 0.28), ("subscription", 0.25), ("meter", 0.22), ("technical", 0.19), ("meter", 0.16), ("subscription", 0.14), ("technical", 0.12), ("subscription", 0.10), ("meter", 0.09), ("subscription", 0.08), ("technical", 0.07), ("billing", 0.06), ("alert", 0.05), ("technical", 0.04)] SEGMENT = { "saver": {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6}, "payer": {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3}, "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9}, "new": {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7}} SEGMENT_NAMES, N_ITEMS = list(SEGMENT), len(ITEMS) 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 SUBSCRIBERS, INTERACTIONS = [], {} for i in range(N_SUBSCRIBERS): r = rng(SEED + 7919 * i) a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)] activity = 0.35 + 1.15 * r() ** 1.6 SUBSCRIBERS.append(a) for j, (domain, share) in enumerate(ITEMS): propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55) if r() < min(0.95, share ** 0.55 * 0.72): # was it shown if r() < propensity: # was it selected INTERACTIONS[(a, j)] = r() # value: sequence stamp if r() < 0.32: r() # a score was left; not used here else: r(), r(), r() LOG, TRAIN, HELD_OUT = {}, {}, {} for (a, j), stamp in INTERACTIONS.items(): LOG.setdefault(a, []).append((stamp, j)) SEEN = {a: set() for a in SUBSCRIBERS} for a, entries in LOG.items(): entries.sort() if len(entries) >= 2: # the split rule is from the first lesson HELD_OUT[a] = entries[-1][1] entries = entries[:-1] for stamp, j in entries: TRAIN[(a, j)] = 1 SEEN[a].add(j) EVAL_SUBS = sorted(HELD_OUT) N_CHOSEN = [sum(1 for (a, j) in TRAIN if j == jj) for jj in range(N_ITEMS)] def measure(score, seen=None, who=None, k=5): seen, who = seen or SEEN, who or EVAL_SUBS hit, rank, shown = 0, 0, set() for a in who: s = score(a) candidates = sorted((j for j in range(N_ITEMS) if j not in seen[a]), key=lambda j: (-s[j], j)) shown.update(candidates[:k]) p = candidates.index(HELD_OUT[a]) hit, rank = hit + (p < k), rank + p + 1 return hit / len(who), rank / len(who), len(shown) print("interaction", len(INTERACTIONS), "-- training", len(TRAIN), "-- held-out subscribers", len(HELD_OUT)) print("sparsity of the training matrix", round(1 - len(TRAIN) / (N_SUBSCRIBERS * N_ITEMS), 4)) print("baseline -- most chosen item: hit rate@5 %.4f, mean rank %.2f, shown %d/24" % measure(lambda a: N_CHOSEN)) ``` ``` interaction 577 -- training 410 -- held-out subscribers 167 sparsity of the training matrix 0.9525 baseline -- most chosen item: hit rate@5 0.6527, mean rank 4.74, shown 9/24 ``` Once the held-out items are removed, the sparsity of the training matrix rises to 0.9525. Three hundred sixty rows, twenty-four columns and **410 filled cells**: all the material the method has for neighborhoods. #### User-Based: The Number of Neighbors Moves the Ranking The similarity routine is written once: given the item sets of the subscribers it yields subscriber similarity, and given the subscriber sets of the items it yields item similarity. A subscriber's score for an item is the sum of the similarities of those among their $K$ most similar neighbors who have that item. ```python def similarities(sets, keys): n = {u: max(1e-9, len(sets[u])) ** 0.5 for u in keys} result = {} for u in keys: b = [(len(sets[u] & sets[v]) / (n[u] * n[v]), v) for v in keys if v != u and sets[u] & sets[v]] b.sort(key=lambda t: (-t[0], t[1])) result[u] = b return result def user_based(B, seen, K): def score(a): s = [0.0] * N_ITEMS for w, v in B[a][:K]: for j in seen[v]: s[j] += w return s return score def top_k(score, a, seen, k=5): s = score(a) return set(sorted((j for j in range(N_ITEMS) if j not in seen[a]), key=lambda j: (-s[j], j))[:k]) SIM = similarities(SEEN, SUBSCRIBERS) BASE5 = {a: top_k(lambda x: N_CHOSEN, a, SEEN) for a in EVAL_SUBS} print(f"{'K':>4} {'hit rate@5':>10} {'mean rank':>9} {'items shown':>11} " f"{'prev K':>9} {'overlap':>8}") previous = None for K in (3, 5, 10, 20, 40, 80, 160): p = user_based(SIM, SEEN, K) h, s, cov = measure(p) cur = {a: top_k(p, a, SEEN) for a in EVAL_SUBS} o = ("%.2f" % (sum(len(cur[a] & previous[a]) for a in EVAL_SUBS) / len(EVAL_SUBS)) if previous else "--") t = sum(len(cur[a] & BASE5[a]) for a in EVAL_SUBS) / len(EVAL_SUBS) print(f"{K:>4} {h:>10.4f} {s:>9.2f} {cov:>11} {o:>9} {t:>8.2f}") previous = cur ``` ``` K hit rate@5 mean rank items shown prev K overlap 3 0.6946 4.66 16 -- 4.07 5 0.6886 4.64 18 4.89 4.01 10 0.6707 4.80 19 4.71 3.85 20 0.6168 5.25 20 4.51 3.62 40 0.5988 5.54 20 4.14 3.49 80 0.6467 5.28 18 4.08 3.96 160 0.6647 5.18 14 4.72 4.12 ``` The best setting is **0.6946** at three neighbors, **0.0419** above the baseline. But the worst candidate of the same column is **0.5988** at forty neighbors, that is **0.0539 below** the baseline. The movement across the seven candidates is 0.0958 and is **more than twice** the margin by which the method beats the baseline at its best setting. The number of neighbors here is not a detail of the method but the thing that determines its result: with a badly chosen $K$, collaborative filtering is worse than a list that makes no distinction between subscribers. The sixth column says how narrow the gain is. At the best setting **4.07** of the top-five list is already an item of the baseline list; the method gains 0.0419 by changing only one of five items. At forty neighbors the overlap drops to 3.49, the most personalized list, and the hit rate is lowest there. At one hundred sixty the overlap climbs back to 4.12, because with neighbors near half the subscribers the weighted sum converges to the average of the whole set, that is to popularity. **The hyperparameter goes up to the baseline at both ends.** The fifth column counts the volatility directly: when the number of neighbors changes by one step, 4.89 of the top five stay in place in the best case and 4.08 in the worst — on average one item changes place at every step. The place where the gain is actually seen is the fourth column. The baseline showed only **9 distinct items** to all 167 subscribers. The user-based setup shows 16 items at its best setting and 20 at twenty neighbors. While gaining 0.0419 in hit rate the method nearly doubles the visible part of the catalog, and since an item that is not shown does not enter the next period's data either, this second number is longer-lived than the first. #### Item-Based: The Same Routine, the Other Edge of the Matrix The same similarity routine is applied to the columns of the matrix: every item is represented by the set of subscribers who selected it, and two items resemble each other by the number of their common subscribers. A subscriber's score is distributed to the $K$ most similar neighbors of their own items. This count uses the same raw material as the **lift** measured in the Unsupervised Learning course, the number of times two items are seen together, but there a rule was being extracted, here a ranking is being produced, and the rule extraction routine is not repeated. ```python ITEM_SEEN = {j: set(a for a in SUBSCRIBERS if j in SEEN[a]) for j in range(N_ITEMS)} ITEM_SIM = similarities(ITEM_SEEN, list(range(N_ITEMS))) def item_based(K): def score(a): s = [0.0] * N_ITEMS for i in SEEN[a]: for w, j in ITEM_SIM[i][:K]: s[j] += w return s return score print(f"{'K':>4} {'hit rate@5':>10} {'mean rank':>9} {'items shown':>11} {'overlap':>8}") for K in (2, 3, 5, 8, 12, 23): h, s, cov = measure(item_based(K)) cur = {a: top_k(item_based(K), a, SEEN) for a in EVAL_SUBS} t = sum(len(cur[a] & BASE5[a]) for a in EVAL_SUBS) / len(EVAL_SUBS) print(f"{K:>4} {h:>10.4f} {s:>9.2f} {cov:>11} {t:>8.2f}") ``` ``` K hit rate@5 mean rank items shown overlap 2 0.6467 5.20 18 3.37 3 0.6467 5.21 18 3.32 5 0.5329 5.75 21 2.93 8 0.5329 6.03 21 3.00 12 0.5329 6.50 21 2.95 23 0.5449 6.48 21 2.92 ``` The best candidate of the item-based setup is **0.6467**, that is **below** the baseline. None of the six candidates exceeds 0.6527. This is the reverse of the user-based result, and its cause can be counted: the held-out subscribers have on average **1.78 items** in the training set. The item-based score is distributed over the neighborhoods of these one or two items, so the sum is almost the neighbor list of a single item, while the user-based sum adds up the whole history of three subscribers. In a sparse matrix the edge with more observations decides the order of the methods, and here that edge is the rows. The place where the setup wins is again the fourth column: it shows 21 items and its overlap with the baseline list does not exceed 3.37 at any setting. The item-based ranking is more personalized and has wider coverage, and pays for that in hit rate. **On the same data, two setups move in two separate directions on the same measure.** #### As Sparsity Grows, No Neighbor Is Left Both setups rest on a single thing: the **direct common observation** of two subscribers or two items. A share of the training interactions is kept and the rest is thrown away, which pulls the sparsity up; the held-out items do not change, so the five rows are read on the same 167 subscribers. The number of neighbors is fixed at its best setting, that is at three. ```python PAIRS = sorted(TRAIN) print(f"{'share':>5} {'train':>7} {'sparsity':>10} {'neighborless':>12} " f"{'hit rate@5':>10} {'neighbored':>10} {'neighborless':>12} {'baseline':>8}") for frac in (1.00, 0.75, 0.55, 0.40, 0.25): r = rng(SEED + 9100) G = {a: set() for a in SUBSCRIBERS} for a, j in PAIRS: if r() < frac: G[a].add(j) B = similarities(G, SUBSCRIBERS) counts = [sum(1 for a in SUBSCRIBERS if j in G[a]) for j in range(N_ITEMS)] ub = user_based(B, G, 3) with_nbrs = [a for a in EVAL_SUBS if B[a]] without = [a for a in EVAL_SUBS if not B[a]] t = sum(len(v) for v in G.values()) wh = "%.4f" % measure(ub, G, without)[0] if without else "--" print(f"{frac:>5.2f} {t:>7} {1 - t / (N_SUBSCRIBERS * N_ITEMS):>10.4f} {len(without):>12} " f"{measure(ub, G)[0]:>10.4f} {measure(ub, G, with_nbrs)[0]:>10.4f} {wh:>12} " f"{measure(lambda a: counts, G)[0]:>8.4f}") ``` ``` share train sparsity neighborless hit rate@5 neighbored neighborless baseline 1.00 410 0.9525 0 0.6946 0.6946 -- 0.6527 0.75 308 0.9644 20 0.6886 0.6803 0.7500 0.6467 0.55 221 0.9744 52 0.6587 0.6783 0.6154 0.6347 0.40 167 0.9807 75 0.6587 0.6739 0.6400 0.6407 0.25 97 0.9888 105 0.6407 0.6613 0.6286 0.6347 ``` As the sparsity goes from 0.9525 to 0.9888, the number of held-out subscribers left with no neighbor goes **from zero to 105**, **more than half** of the 167 subscribers. The score vector of these subscribers is zero from end to end: collaborative filtering produces nothing for them. In spite of this, the fifth column goes down only from 0.6946 to 0.6407. The measure dropping this little does not show that the method is robust to sparsity; the seventh column gives the reason. The hit rate among the neighborless subscribers is **0.6286**, only 0.0327 below the 0.6613 among those with neighbors. Yet the method did not work at all for those subscribers. The number comes from the tie resolution written in RS27: when all scores are zero the ranking falls to the **catalog index**, and the catalog is in decreasing order of base share. So the neighborless subscriber silently receives the same list as the baseline, and the measure prints the number of a baseline that looks like the number of the method. This is another face of the rule of the course. If **for how many subscribers it really works** is not written when reading the number of a method, the measure is produced not by the method but by the measurement setup. When the columns are printed separately the loss becomes visible: at the 0.25 share the method works for 62 of the 167 subscribers and gives 0.6613 there, and for the remaining 105 the catalog order gives 0.6286. The baseline stays between 0.6527 and 0.6347 across the five rows. #### Summary - Collaborative filtering produces the recommendation not from the features of the item but from the subscribers who select the items together; a single similarity routine works on both edges of the matrix. - The training matrix is 0.9525 sparse with 410 interactions; the baseline, the order of the most chosen item, gives 0.6527 hit rate@5 and shows only 9 of the 24 items. - The user-based setup gives 0.6946 with three neighbors, 0.0419 above the baseline; but 4.07 of its top five already belongs to the baseline list, and the real gain is showing 16 items instead of 9. - The number of neighbors is a hyperparameter: seven candidates move between 0.5988 and 0.6946, and this band of 0.0958 is more than twice the margin by which the method beats the baseline. - The item-based setup stays at 0.6467 at its best setting and falls below the baseline, because the average number of training items per held-out subscriber is 1.78; in return it shows 21 items. - When the sparsity is raised from 0.9525 to 0.9888 the neighborless subscribers go from 0 to 105; the measure staying at 0.6407 comes not from the method but from the catalog order that comes into play when the scores are zeroed. #### Next Step The neighborhood rests on a single thing: the **direct common observation** of two subscribers or two items. If there is none, the similarity never enters the list, and the last table showed the price of this. Yet two subscribers with no common item need not be truly dissimilar: if one has applied for an installment plan and the other for debt restructuring, both stand in the billing domain, but their similarity comes out zero. To capture this commonality the similarity has to be read through a representation that places every subscriber and every item on a few **latent factors**. The next lesson writes the matrix as the product of two such small matrices, and the decision to be measured is this: will the **unobserved cells** enter the computation as zero, or not at all. The two setups produce two separate rankings on the same data. ### Matrix Factorization Source: https://academia.sh/en/courses/reinforcement-and-recommender/matrix-factorization Measuring the difference between counting an unobserved cell of an interaction matrix with missing entries as zero and leaving it out of the computation altogether: the same routine, with a one-line change, produces two separate rankings from the same 410 training interactions. The skipping setup gives 0.7006 hit rate@5 with four factors and beats the 0.6527 baseline, but shows only 9 of the 24 items; the zero-counting setup falls to 0.2395 with eight factors while showing 20 items, and lowers the share of the top-five lists falling on the five most shown items from 0.7868 to 0.4467. The number of factors is a hyperparameter, six candidates were tried, and the number of items shared by the top fives of the two setups falls from 4.02 to 0.86. The previous lesson built similarity directly from common observation: between two subscribers with no common item the similarity was not defined, and as sparsity rose, 105 of the 167 held-out subscribers were left with no neighbor. Yet two subscribers, one of whom applied for an installment plan and the other for debt restructuring, may carry the same billing behavior; the neighborhood routine cannot see this, because the only thing it looks at is the overlap of cells. **Matrix factorization** removes this restriction: every subscriber and every item is represented by a vector on a small number of **latent factors**, and the prediction for a cell is the product of two vectors. Two subscribers with no common item can take high values in the same factor direction, so the similarity is read not from the cells but from the **representation**. The low-rank approximation of a full matrix was measured in the dimensionality reduction topic of the Unsupervised Learning course and is not repeated here. The only thing added is the **missing entries**, and it gives rise to a decision: of the 8,640 cells 8,230 are empty, and an empty cell either **enters the computation as zero** or **does not enter at all**. This lesson measures that decision. - **RS30.** The setup, the split rule, the baseline and the measure carry on exactly from the previous two lessons: 360 subscribers, 24 items, 410 training interactions, 167 held-out subscribers, the measure **hit rate@5**, the baseline **the order of the most chosen item**. - **RS31.** Factorization is the **model** and is written in the lesson with only the standard library: the subscriber matrix $P$ and the item matrix $Q$ are updated **alternately**, and at every step the **penalized least squares** is solved in closed form; the gradient descent of the Supervised Learning course is not repeated. - **RS32.** The only difference between the two setups is **which cells enter the sum** in the update. In the **zero-counting** setup all 24 cells of the row enter and the target of the unobserved ones is 0. In the **skipping** setup only the observed cells enter and the unobserved ones are never written. - **RS33.** The penalty coefficient is **1.0 in both setups** and is not swept; what is measured is the difference made by the decision about the unobserved cell, not by the penalty coefficient. - **RS34.** The number of factors $f$ is a **hyperparameter**; **six candidates** were tried (1, 2, 3, 4, 6, 8). The number of parameters is $384f$ and the observed interactions are 410; from $f=2$ on the number of parameters exceeds the number of observations. - **RS35.** The alternating update runs for **10 rounds** and the two setups start from the same initial point. The small square systems are solved by elimination; a threshold of $10^{-12}$ is written for the diagonal, because floating-point equality is not tested. - **RS36.** Two errors are printed: the **observed-cell error** over the 410 filled cells and the **all-cell error** over all 8,640 cells, both root mean square deviation. Each setup is built to minimize one of them. - **RS37.** The **number of items shown** and the **share of the top-five lists falling on the five most shown items** are the third number of the course; an item that is not shown does not enter the data of the next period. #### One-Line Difference: Which Cells Enter the Computation The first block builds the setup and the split in the form of the previous lessons; the numbers do not change. ```python # The setup catalog comes from the first lesson; here only the item's domain and base share are needed. SEED, M32, N_SUBSCRIBERS = 20260218, 0xFFFFFFFF, 360 ITEMS = [("billing", 0.90), ("alert", 0.85), ("alert", 0.78), ("billing", 0.62), ("meter", 0.55), ("alert", 0.50), ("billing", 0.44), ("subscription", 0.40), ("meter", 0.36), ("alert", 0.32), ("billing", 0.28), ("subscription", 0.25), ("meter", 0.22), ("technical", 0.19), ("meter", 0.16), ("subscription", 0.14), ("technical", 0.12), ("subscription", 0.10), ("meter", 0.09), ("subscription", 0.08), ("technical", 0.07), ("billing", 0.06), ("alert", 0.05), ("technical", 0.04)] SEGMENT = { "saver": {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6}, "payer": {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3}, "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9}, "new": {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7}} SEGMENT_NAMES, N_ITEMS = list(SEGMENT), len(ITEMS) 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 SUBSCRIBERS, INTERACTIONS = [], {} for i in range(N_SUBSCRIBERS): r = rng(SEED + 7919 * i) a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)] activity = 0.35 + 1.15 * r() ** 1.6 SUBSCRIBERS.append(a) for j, (domain, share) in enumerate(ITEMS): propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55) if r() < min(0.95, share ** 0.55 * 0.72): if r() < propensity: INTERACTIONS[(a, j)] = r() if r() < 0.32: r() else: r(), r(), r() LOG, TRAIN, HELD_OUT = {}, {}, {} for (a, j), stamp in INTERACTIONS.items(): LOG.setdefault(a, []).append((stamp, j)) SEEN = {a: set() for a in SUBSCRIBERS} for a, entries in LOG.items(): entries.sort() if len(entries) >= 2: HELD_OUT[a] = entries[-1][1] entries = entries[:-1] for stamp, j in entries: TRAIN[(a, j)] = 1 SEEN[a].add(j) EVAL_SUBS = sorted(HELD_OUT) N_CHOSEN = [sum(1 for (a, j) in TRAIN if j == jj) for jj in range(N_ITEMS)] ITEM_SEEN = {j: set(a for a in SUBSCRIBERS if j in SEEN[a]) for j in range(N_ITEMS)} def measure(score, k=5): hit, rank, shown = 0, 0, set() for a in EVAL_SUBS: s = score(a) candidates = sorted((j for j in range(N_ITEMS) if j not in SEEN[a]), key=lambda j: (-s[j], j)) shown.update(candidates[:k]) p = candidates.index(HELD_OUT[a]) hit, rank = hit + (p < k), rank + p + 1 return hit / len(EVAL_SUBS), rank / len(EVAL_SUBS), len(shown) print("training", len(TRAIN), "interactions -- empty cell", N_SUBSCRIBERS * N_ITEMS - len(TRAIN), "-- held-out subscribers", len(EVAL_SUBS)) print("baseline -- most chosen item: hit rate@5 %.4f, mean rank %.2f, shown %d/24" % measure(lambda a: N_CHOSEN)) ``` ``` training 410 interactions -- empty cell 8230 -- held-out subscribers 167 baseline -- most chosen item: hit rate@5 0.6527, mean rank 4.74, shown 9/24 ``` The difference between the two setups is the single sum opened by the `count_zero` flag. When the flag is on, the square system is built over all items and is the same for every subscriber; when it is off, only over the observed items of the subscriber. The target vector is the same in both, because cells with a zero target add nothing to the sum. ```python def solve(A, b): # elimination on a small square system; f is at most 8 n = len(b) M = [A[i][:] + [b[i]] for i in range(n)] for i in range(n): p = max(range(i, n), key=lambda t: abs(M[t][i])) M[i], M[p] = M[p], M[i] if abs(M[i][i]) < 1e-12: # threshold: the penalty term keeps the diagonal away from zero continue d = M[i][i] for k in range(i, n + 1): M[i][k] /= d for t in range(n): if t != i and M[t][i]: c = M[t][i] for k in range(i, n + 1): M[t][k] -= c * M[i][k] return [M[i][n] for i in range(n)] def factorize(f, count_zero, rounds=10, penalty=1.0): # THE MODEL: matrix factorization by alternating updates, standard library only. r = rng(SEED + 5100 + f) P = {a: [0.1 + 0.2 * r() for _ in range(f)] for a in SUBSCRIBERS} Q = [[0.1 + 0.2 * r() for _ in range(f)] for _ in range(N_ITEMS)] blank = [[0.0] * f for _ in range(f)] for _ in range(rounds): G = ([[sum(q[x] * q[y] for q in Q) for y in range(f)] for x in range(f)] if count_zero else blank) for a in SUBSCRIBERS: idx = SEEN[a] A = [[G[x][y] + (0 if count_zero else sum(Q[j][x] * Q[j][y] for j in idx)) + (penalty if x == y else 0) for y in range(f)] for x in range(f)] P[a] = solve(A, [sum(Q[j][x] for j in idx) for x in range(f)]) H = ([[sum(P[a][x] * P[a][y] for a in SUBSCRIBERS) for y in range(f)] for x in range(f)] if count_zero else blank) for j in range(N_ITEMS): users = ITEM_SEEN[j] A = [[H[x][y] + (0 if count_zero else sum(P[a][x] * P[a][y] for a in users)) + (penalty if x == y else 0) for y in range(f)] for x in range(f)] Q[j] = solve(A, [sum(P[a][x] for a in users) for x in range(f)]) return P, Q def predict(P, Q): return lambda a: [sum(P[a][x] * Q[j][x] for x in range(len(Q[0]))) for j in range(N_ITEMS)] def errors(P, Q): f, so, sa = len(Q[0]), 0.0, 0.0 for a in SUBSCRIBERS: for j in range(N_ITEMS): d = (1.0 if j in SEEN[a] else 0.0) - sum(P[a][x] * Q[j][x] for x in range(f)) sa += d * d if j in SEEN[a]: so += d * d return (so / len(TRAIN)) ** 0.5, (sa / (N_SUBSCRIBERS * N_ITEMS)) ** 0.5 def top5(score, a): s = score(a) return set(sorted((j for j in range(N_ITEMS) if j not in SEEN[a]), key=lambda j: (-s[j], j))[:5]) for flag, label in ((True, "zero counted"), (False, "skipped ")): P, Q = factorize(3, flag) oe, ae = errors(P, Q) print(f"f=3, unobserved {label}: hit rate@5 {measure(predict(P, Q))[0]:.4f} " f"observed-cell error {oe:.4f} all-cell error {ae:.4f}") ``` ``` f=3, unobserved zero counted: hit rate@5 0.4731 observed-cell error 0.7168 all-cell error 0.1614 f=3, unobserved skipped : hit rate@5 0.6826 observed-cell error 0.2125 all-cell error 0.5055 ``` The observed-cell error of the skipping setup is **0.2125**, that of the zero-counting one **0.7168**, more than three times as much. In the all-cell error the order reverses: 0.1614 for the zero-counting setup, 0.5055 for the skipping one. Each setup reduces the sum it tries to reduce and loses under the other's measure: the skipping setup sees no constraint on the unobserved cells and leaves a value around 0.5 there, while the zero-counting setup, pulling 8,230 empty cells to 0, finds no capacity to pull the 410 filled cells to 1. The real number is the third. **The setup with the smaller reconstruction error gives the worse ranking:** 0.6826 for the skipping, 0.4731 for the zero-counting. #### The Number of Factors Is a Hyperparameter The number of factors is swept over six candidates; next to it are printed the number of parameters, the two errors, the number of items shown, the overlap with the baseline list and the overlap of the two setups **with each other**. ```python BASE5 = {a: top5(lambda x: N_CHOSEN, a) for a in EVAL_SUBS} print(f"{'f':>2} {'par':>5} | {'A hit':>6} {'A obs':>7} {'A all':>6} {'A shw':>5} {'A ovl':>5}" f" | {'B hit':>6} {'B obs':>7} {'B all':>6} {'B shw':>5} {'B ovl':>5} | {'A~B':>5}") for f in (1, 2, 3, 4, 6, 8): row, lists = [f"{f:>2} {(N_SUBSCRIBERS + N_ITEMS) * f:>5}"], [] for flag in (True, False): P, Q = factorize(f, flag) sc = predict(P, Q) oe, ae = errors(P, Q) hit, rank, shw = measure(sc) L = {a: top5(sc, a) for a in EVAL_SUBS} lists.append(L) row.append(f"| {hit:>6.4f} {oe:>7.4f} {ae:>6.4f} {shw:>5} " f"{sum(len(L[a] & BASE5[a]) for a in EVAL_SUBS) / len(EVAL_SUBS):>5.2f}") row.append(f"| {sum(len(lists[0][a] & lists[1][a]) for a in EVAL_SUBS) / len(EVAL_SUBS):>5.2f}") print(" ".join(row)) ``` ``` f par | A hit A obs A all A shw A ovl | B hit B obs B all B shw B ovl | A~B 1 384 | 0.6707 0.8377 0.1930 10 4.23 | 0.6707 0.2161 0.5207 9 4.34 | 4.02 2 768 | 0.6048 0.7667 0.1760 11 4.16 | 0.6766 0.2124 0.5072 9 4.37 | 3.65 3 1152 | 0.4731 0.7168 0.1614 12 3.43 | 0.6826 0.2125 0.5055 9 4.35 | 3.10 4 1536 | 0.4251 0.6591 0.1479 15 2.68 | 0.7006 0.2115 0.5000 9 4.31 | 2.60 6 2304 | 0.3593 0.5466 0.1263 20 1.45 | 0.6886 0.2113 0.4940 9 4.46 | 1.44 8 3072 | 0.2395 0.4758 0.1066 20 0.82 | 0.6826 0.2107 0.4937 9 4.54 | 0.86 ``` The last column is the headline of the lesson. With one factor the top-five lists of the two setups share **4.02 items**, with eight factors **0.86**. Same data, routine, penalty and starting point, and a one-line difference changes nearly all of the lists. The decision about the unobserved cell is not an implementation detail; it is **the definition of what the model learns**. The zero-counting setup degrades with the number of factors: from 0.6707 to 0.2395. The reason is in the second column. The number of parameters is $384f$; with one factor it is 384, while the observed interactions are 410. **From two factors on, the number of parameters exceeds the number of observations**, and the model starts to carve out per-subscriber exceptions among the 8,230 zeros. The overlap with the baseline list falls from 4.23 to 0.82: the list breaks away from the baseline, but the place it breaks away to is not the right place. The skipping setup is almost insensitive to the number of factors: its best is **0.7006** with four factors, **0.0479** above the baseline and 0.0060 above the best neighborhood setup of the previous lesson. The reason is structural: the unobserved cell is never looked at, so the extra factors have nothing to learn wrongly, and a subscriber's ranking remains the items that lie close to their own items in the latent factor space. This is the item-based neighborhood of the previous lesson written over factors. #### The Catalog Shown by the Two Rankings Hit rate ranks the two setups in one direction; the items shown, the third number of the course, rank them in the other. The top-five lists of both setups are counted next to the baseline. ```python def distribution(score): counts = [0] * N_ITEMS for a in EVAL_SUBS: for j in top5(score, a): counts[j] += 1 d = sorted(counts, reverse=True) return sum(1 for v in counts if v == 0), d[0], sum(d[:5]) / sum(d) print(f"{'setup':>13} {'f':>2} {'never shown':>18} {'most shown':>18} " f"{'top-5 item share':>19}") for label, f, flag in (("zero counted", 1, True), ("zero counted", 8, True), ("skipped", 1, False), ("skipped", 8, False)): print("%13s %2d %18d %18d %19.4f" % ((label, f) + distribution(predict(*factorize(f, flag))))) print("%13s %2s %18d %18d %19.4f" % (("baseline", "--") + distribution(lambda a: N_CHOSEN))) ``` ``` setup f never shown most shown top-5 item share zero counted 1 14 150 0.7904 zero counted 8 4 84 0.4467 skipped 1 15 146 0.7940 skipped 8 15 146 0.7856 baseline -- 15 146 0.7868 ``` The skipping setup shows the **same** catalog as the baseline at both numbers of factors: 15 items never appear, the most shown item reaches 146 of the 167 subscribers, and **0.7856** of the impressions fall on five items. The setup with the highest hit rate does not widen the visible part of the catalog at all; it amounts to reordering the baseline list a little. With eight factors the zero-counting setup does the opposite: the items never shown go **from 15 to 4**, the number of subscribers reached by the most shown item from 146 to 84, and the share of the top five items from 0.7904 to **0.4467**. Only counting the unobserved cell as zero pushes the tail of the catalog up, because the zeros of popular items also enter the sum and the direction of popularity is suppressed. The price is paid in hit rate: 0.2395, which is 0.4132 below the baseline. No choice is made between the two numbers; choosing the setup determines both. An item that is not shown is not chosen, and an item that is not chosen does not enter the training set of the next period: a setup that never shows 15 items today has also decided which items tomorrow's 410 interactions will come from. #### Summary - Matrix factorization places every subscriber and every item on a small number of latent factors; two subscribers with no common item can meet in the same factor direction. In a matrix with missing entries the single decision is what the unobserved cell is counted as, and the rest of the routine is exactly the same in the two setups. - With three factors the observed-cell error of the skipping setup is 0.2125 and that of the zero-counting one 0.7168; in the all-cell error the order reverses (0.5055 and 0.1614). A small error does not mean a better ranking. - The number of factors is a hyperparameter and six candidates were tried: the zero-counting setup degrades from 0.6707 to 0.2395, and the skipping setup gives its best with four factors (0.7006). - The number of items shared by the top-five lists of the two setups is 4.02 with one factor and 0.86 with eight: two separate rankings from the same data. - Coverage moves in the opposite direction: the skipping setup never shows the same 15 items as the baseline; the zero-counting setup lowers this to 4 and pulls the share of the top five items from 0.7868 to 0.4467. #### Next Step In four lessons the recommendation was always produced from the same place: **from the existing interactions**. The baseline counted the items chosen in training, the content-based setup extracted a profile from what the subscriber chose, the neighborhood looked for the common choices of two subscribers, and factorization placed the 410 filled cells on factors. The silent assumption of all four is that at least one interaction has come from the subscriber. Yet in the same setup 80 of the 360 subscribers have no interactions at all and the 15 items in the last table are shown to no subscriber; for these two groups the four methods produce the same thing. The next lesson takes up these two gaps by name, the subscriber with no interactions and the item never shown, and counts how many subscribers and how many items each solution brings into coverage and which measure it gives up in return. ### Cold Start Source: https://academia.sh/en/courses/reinforcement-and-recommender/cold-start Building the recommendation for a subscriber with no interactions and an item never selected: of 360 subscribers 80 have none and 113 have a single interaction, and once the single interaction is hidden 193 subscribers count as cold; in the training set of 464 interactions one item was never selected and eight items are below five. The popularity fallback warms all 193 subscribers but gives all of them the same five items, the feature bridge brings the one cold item to 114 subscribers but warms no cold subscriber, and the three-question intake warms 71 subscribers with 339 questions and raises coverage from 5 to 13 items while lowering the top-five hit rate from 0.5752 to 0.5487. In four lessons the recommendation was always produced from existing interactions: the content-based approach from the features of the item, collaborative filtering from the history of neighboring subscribers, matrix factorization from latent factors. All three had a silent common condition: the subscriber has a filled row. What to do for a subscriber whose row is entirely empty and an item whose column is entirely empty was never asked. What this lesson measures is not accuracy but **warming**: how many subscribers and how many items are cold, and how many of them each solution makes able to produce a recommendation. Every warming has a price, and the price is counted on the same line. - **RS41. The setup is the same block built in the first lesson** and gives the same numbers: 360 subscribers, 24 service items, 8,640 cells, seed 20260218; 3,002 impressions, 577 interactions, 218 scores. - **RS42. A cold subscriber is a subscriber with no interaction in the training set.** A cold item is an item never selected in the training set. - **RS43. The cold protocol changes the split.** A subscriber with no interaction has no correct answer either and cannot enter the measure. For a subscriber with a single interaction that single interaction is hidden: the row is emptied and the correct answer is known. The remaining interactions are the training set. - **RS44. The baseline is offering the five items most chosen in training to everyone.** This is the baseline built in the first lesson; since nothing else is at hand for a cold subscriber, it is the one chosen here too. - **RS45. Warming is a solution making a cold subscriber or a cold item able to produce a recommendation**, and its number is how many subscribers, how many items. - **RS46. The price is written with three numbers:** the number of questions asked, the number of subscribers left unanswered and the number of distinct items the recommendations spread over. - **RS47. The three-question intake is fictional:** the domain you are interested in, the second domain, application frequency. The answer rate is 0.62 and is a parameter of the setup. - **RS48. The measure is the top-five hit rate**; its definition was built in the first lesson and is not repeated here. #### Counting What Is Cold ```python # COMMON -- FICTIONAL. The subscriber x service item interaction matrix is built inside the lesson. # Impression, selection and score are generated separately: an item is first SHOWN, then # it can be selected, and only if it is selected can it be scored. SEED, M32 = 20260218, 0xFFFFFFFF 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 ITEMS = [ # (name, domain, channel, paid, commitment, appointment, base_share) ("auto_payment_instruction", "billing", "online", 0, 0, 0, 0.90), ("e_invoice_switch", "alert", "online", 0, 0, 0, 0.85), ("payment_reminder_sms", "alert", "online", 0, 0, 0, 0.78), ("installment_plan", "billing", "branch", 0, 1, 0, 0.62), ("remote_reading_application", "meter", "field", 0, 1, 1, 0.55), ("outage_alert_subscription", "alert", "online", 0, 0, 0, 0.50), ("debt_restructuring", "billing", "branch", 0, 1, 0, 0.44), ("address_update", "subscription", "online", 0, 0, 0, 0.40), ("meter_replacement", "meter", "field", 1, 0, 1, 0.36), ("consumption_report_subscription", "alert", "online", 0, 0, 0, 0.32), ("invoice_dispute_record", "billing", "branch", 0, 0, 0, 0.28), ("subscription_transfer", "subscription", "branch", 0, 0, 0, 0.25), ("illicit_use_check_appointment", "meter", "field", 0, 0, 1, 0.22), ("installation_maintenance_package", "technical", "field", 1, 1, 1, 0.19), ("second_meter_request", "meter", "field", 1, 0, 1, 0.16), ("business_tariff_switch", "subscription", "branch", 0, 1, 0, 0.14), ("pressure_regulator_mounting", "technical", "field", 1, 0, 1, 0.12), ("garden_irrigation_tariff", "subscription", "branch", 0, 1, 0, 0.10), ("meter_relocation", "meter", "field", 1, 0, 1, 0.09), ("common_area_sharing_record", "subscription", "branch", 0, 1, 0, 0.08), ("installation_compliance_report", "technical", "field", 1, 0, 1, 0.07), ("late_interest_waiver", "billing", "branch", 0, 0, 0, 0.06), ("mobile_access_permission", "alert", "online", 0, 0, 0, 0.05), ("extra_line_installation", "technical", "field", 1, 1, 1, 0.04), ] SEGMENT = { # propensity of the segment toward the domains; used only inside the generator "saver": {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6}, "payer": {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3}, "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9}, "new": {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7}, } SEGMENT_NAMES = list(SEGMENT) rq = rng(SEED + 101) QUALITY = [0.25 + 0.70 * rq() for _ in ITEMS] # the item's own satisfaction N_SUBSCRIBERS, N_ITEMS = 360, len(ITEMS) SUBSCRIBERS, IMPRESSIONS, INTERACTIONS, SCORES, PROPENSITY = [], {}, {}, {}, {} for i in range(N_SUBSCRIBERS): r = rng(SEED + 7919 * i) a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)] activity = 0.35 + 1.15 * r() ** 1.6 SUBSCRIBERS.append(a) for j, (name, domain, channel, paid, commitment, appointment, share) in enumerate(ITEMS): propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55) PROPENSITY[(a, j)] = propensity if r() < min(0.95, share ** 0.55 * 0.72): # was it shown IMPRESSIONS[(a, j)] = 1 if r() < propensity: # was it selected INTERACTIONS[(a, j)] = r() # value: sequence stamp if r() < 0.32: # did it leave a score raw = (0.16 + 0.50 * SEGMENT[segment][domain] / 1.9 + 0.42 * QUALITY[j] + 0.26 * (r() - 0.5)) SCORES[(a, j)] = max(1, min(5, int(round(raw * 5)))) else: r(), r(), r() log = {} for (a, j), stamp in INTERACTIONS.items(): log.setdefault(a, []).append((stamp, j)) ZERO_SUBS = [a for a in SUBSCRIBERS if a not in log] SINGLE_SUBS = sorted(a for a in log if len(log[a]) == 1) MULTI_SUBS = [a for a in log if len(log[a]) >= 2] HIDDEN = {a: log[a][0][1] for a in SINGLE_SUBS} # COLD PROTOCOL: the single interaction is hidden TRAIN = dict(((a, j), 1) for a in MULTI_SUBS for _, j in log[a]) chosen = [0] * N_ITEMS for (a, j) in TRAIN: chosen[j] += 1 COLD_ITEMS = [j for j in range(N_ITEMS) if chosen[j] == 0] FEWEST = sorted(range(N_ITEMS), key=lambda j: (chosen[j], j)) RANKED = sorted(range(N_ITEMS), key=lambda j: (-chosen[j], j)) print(f"{N_SUBSCRIBERS} subscribers: {len(ZERO_SUBS)} zero interactions, {len(SINGLE_SUBS)} single interaction, " f"{len(MULTI_SUBS)} two or more") print(f"cold subscribers {len(ZERO_SUBS) + len(SINGLE_SUBS)}; measurable {len(SINGLE_SUBS)} subscribers, " f"training set {len(TRAIN)} interactions") print(f"cold items {len(COLD_ITEMS)}: {', '.join(ITEMS[j][0] for j in COLD_ITEMS)}; " f"below five interactions {sum(1 for j in range(N_ITEMS) if chosen[j] < 5)} items") print("baseline list (five most chosen items in training):") for j in RANKED[:5]: print(f" {ITEMS[j][0]:26s} {chosen[j]:3d}") ``` ``` 360 subscribers: 80 zero interactions, 113 single interaction, 167 two or more cold subscribers 193; measurable 113 subscribers, training set 464 interactions cold items 1: mobile_access_permission; below five interactions 8 items baseline list (five most chosen items in training): e_invoice_switch 76 payment_reminder_sms 71 auto_payment_instruction 58 installment_plan 46 remote_reading_application 31 ``` Three numbers describe three separate groups of subscribers. **80** subscribers have no interaction; for them there is neither a history nor a correct answer, so they cannot enter any measure, yet they arrive at the system every day. **113** subscribers have a single interaction, and the cold protocol hides that single interaction: their rows are emptied and their correct answers stay at hand. The total of cold subscribers is **193**, a little more than half of the 360 subscribers; the measurable part is **113**. The item side is much narrower: **1** item was never selected in the training set, and **8** items remain below five interactions. The baseline list reflects the skew of the catalog as it is: five items collect 282 of the 464 interactions. Being cold and not being recommended are separate things: the previous lessons measured that the baseline list recommended **15** of the 24 items to no subscriber, yet those items have interactions and are not cold; they merely never enter the ranking. The two faces of cold start do not carry the same weight either: in this setup the cold subscriber problem is much larger than the cold item problem. #### Warming the Item: The Feature Bridge A cold item has no interaction but **has features**: which domain it belongs to, which channel it runs through, whether it is paid, whether it asks for a commitment, whether it needs an appointment. The bridge uses these features to connect the cold item to its warm neighbors, and the item enters the list of the subscribers who have interacted with those neighbors. ```python import math DOMAINS = ["billing", "meter", "subscription", "alert", "technical"] CHANNELS = ["online", "field", "branch"] def features(j): """Item features: domain, channel and three binary flags. Needs no interaction.""" name, domain, channel, paid, commitment, appointment, p = ITEMS[j] return ([1.0 if domain == x else 0.0 for x in DOMAINS] + [1.0 if channel == x else 0.0 for x in CHANNELS] + [float(paid), float(commitment), float(appointment)]) def similar(i, j): x, y = features(i), features(j) return sum(p * q for p, q in zip(x, y)) / ( math.sqrt(sum(p * p for p in x) * sum(q * q for q in y)) + 1e-9) warm = [j for j in range(N_ITEMS) if chosen[j] > 0] print("content-based bridge; last column number of subscribers who interacted with its neighbors") for j in FEWEST[:4]: nbrs = sorted(warm, key=lambda t: (-similar(j, t), t))[:2] if j in nbrs: nbrs = [t for t in nbrs if t != j] + [sorted(warm, key=lambda t: (-similar(j, t), t))[2]] reach = set(a for (a, t) in TRAIN if t in nbrs) print(f" {ITEMS[j][0]:32s}{chosen[j]:2d} neighbors: {ITEMS[nbrs[0]][0]}, " f"{ITEMS[nbrs[1]][0]} -> {len(reach):>3}") print(f"bridge puts {len(COLD_ITEMS)}/{len(COLD_ITEMS)} cold items into the recommendation pool, " f"warms 0/{len(ZERO_SUBS) + len(SINGLE_SUBS)} cold subscribers") ``` ``` content-based bridge; last column number of subscribers who interacted with its neighbors mobile_access_permission 0 neighbors: e_invoice_switch, payment_reminder_sms -> 114 installation_compliance_report 1 neighbors: pressure_regulator_mounting, installation_maintenance_package -> 10 late_interest_waiver 1 neighbors: invoice_dispute_record, installment_plan -> 53 extra_line_installation 1 neighbors: installation_maintenance_package, pressure_regulator_mounting -> 10 bridge puts 1/1 cold items into the recommendation pool, warms 0/193 cold subscribers ``` The bridge solves the cold item problem: **1/1**. The width of the reach depends on who the neighbor is, and this is the hidden price of the bridge. `mobile_access_permission` reaches **114** subscribers because its closest neighbors are online alert items; `installation_compliance_report` and `extra_line_installation` reach **10** subscribers each because they neighbor field technical items. The bridge warms an item only as much as the prevalence of its own neighbors: a cold item with a prevalent neighbor warms at once, one with a sparse neighbor stays cold. Warming an item borrows not the popularity of the column itself but that of its neighbor. The last line writes the real limit: the bridge warms **0/193** cold subscribers. In the setup the item has features, the subscriber does not; the only thing known about a subscriber is their history, and the history of a cold subscriber is empty. The content-based approach sees only one face of cold start. #### Warming the Subscriber: The Three-Question Intake On the subscriber side two options remain: to fall back to the baseline, offering everyone the same five items, or to ask the subscriber. The second **produces** data that is not in the log, and its price is the question. ```python SEGMENT_OF = dict((20001 + i, SEGMENT_NAMES[int(rng(SEED + 7919 * i)() * 4)]) for i in range(N_SUBSCRIBERS)) ANSWERS = {} for a in SINGLE_SUBS: # three questions: domain, second domain, activity q = rng(SEED + 555000 + a) if q() < 0.62: # the answer rate is fictional s = sorted(SEGMENT[SEGMENT_OF[a]], key=lambda x: -SEGMENT[SEGMENT_OF[a]][x]) ANSWERS[a] = (s[0], s[1], 0.35 + 1.15 * rng(SEED + 7919 * (a - 20001))() ** 1.6) def baseline(a): return RANKED[:5] def intake(a, third=False): """Domain order if answered, baseline list if not. THE MODEL.""" if a not in ANSWERS: return RANKED[:5] d1, d2, activity = ANSWERS[a] mult = activity if third else 1.0 # the third answer multiplies every item equally return sorted(range(N_ITEMS), key=lambda j: ( -mult * (chosen[j] + 1) ** 0.35 * (3.0 if ITEMS[j][1] == d1 else 1.8 if ITEMS[j][1] == d2 else 1.0), j))[:5] print(f"three-question intake: {3 * len(SINGLE_SUBS)} questions asked, {len(ANSWERS)} subscribers answered, " f"{len(SINGLE_SUBS) - len(ANSWERS)} subscribers fell to the baseline list") for name, f in (("baseline (popularity)", baseline), ("intake, two answers", intake), ("intake, three answers", lambda a: intake(a, True))): hit = sum(1 for a in SINGLE_SUBS if HIDDEN[a] in f(a)) / len(SINGLE_SUBS) cov = len(set(j for a in SINGLE_SUBS for j in f(a))) print(f" {name:<22} hit rate@5 {hit:.4f} coverage {cov:>2}/{N_ITEMS}") ``` ``` three-question intake: 339 questions asked, 71 subscribers answered, 42 subscribers fell to the baseline list baseline (popularity) hit rate@5 0.5752 coverage 5/24 intake, two answers hit rate@5 0.5487 coverage 13/24 intake, three answers hit rate@5 0.5487 coverage 13/24 ``` What the three solutions warm can now be read side by side. The popularity fallback warms **193/193** subscribers and **0/1** items; the feature bridge **0/193** subscribers and **1/1** items; the three-question intake **71** of the 113 measurable subscribers and **0/1** items. None warms both faces at once. Cold start is not a single problem; it is two separate problems and asks for two separate solutions. The prices also stand side by side. For the intake **339** questions were asked and **42** subscribers gave no answer and fell back to the baseline; the answer rate being 0.62 is a choice of the setup, and a lower rate pulls the number of warmed subscribers down directly. The price of the third question is of a special kind: since the application frequency answer multiplies every item by **the same coefficient**, it does not change the ranking at all, and both hit rate and coverage come out exactly the same as in the setup with two answers. In return for this third question asked of each of 113 subscribers, the system gets no change in ranking. Whether an answer carries information depends on whether it **separates the options from one another**. The price of the baseline is not in the question but in the uniformity: a total of **5** distinct items were recommended to 113 subscribers. The intake raises this number to **13**. In return, the top-five hit rate read from the log is **0.5752** at the baseline and **0.5487** at the intake: when the question is asked, the measure **falls**. It matters which log these numbers are read from: the single hidden interaction is the one interaction that subscriber had with a **shown** item, and the impression order largely presented the top end of the catalog. The baseline recommends exactly that top end. #### Summary - Cold start is two separate problems: in the fictional matrix 80 subscribers have no interaction and 113 have a single one, and once the single interaction is hidden 193 subscribers count as cold; on the item side, in the training set of 464 interactions 1 item was never selected and 8 items are below five. - The popularity fallback warms 193/193 subscribers, warms no item and gives all of them the same 5 items; the feature bridge warms 1/1 items, warms no cold subscriber and carries the item only as far as the prevalence of its neighbor: 114 subscribers against 10. - The three-question intake warms 71 subscribers for 339 questions, 42 subscribers stay unanswered and coverage rises from 5 to 13 items; since the third question multiplies every item by the same coefficient, it does not change the ranking at all. - The top-five hit rate read from the log is 0.5752 at the baseline and 0.5487 at the intake; this log consists only of interactions with shown items. #### Next Step The last table of this lesson says something odd: asking the cold subscriber questions and turning the recommendations toward the domain they themselves named **lowered** the number read from the log. There are two explanations. Either the questions do not work, or the measure is read from the wrong place, because every interaction in the log was born at a moment when the decision was made not by the system but by the **impression order**, and the interaction of an item that was not shown never appears in the log. The next lesson builds ranking measures: top k, the cutoff and positional discount. Then it measures the same ranking twice, once on this log and once while the ranking itself decides what is shown. The two numbers are printed side by side. ### Recommendation Evaluation Source: https://academia.sh/en/courses/reinforcement-and-recommender/recommendation-evaluation Building ranking measures and showing that the same ranking gives two different numbers: hit rate at k reorders three setups depending on the cutoff, the setup that is last at k=3 is first at k=5 and at k=10 all three are indistinguishable, and positional discount drops the first place of k=5 to last. The setup that is first on the offline log with 0.6886 falls last, below the baseline, with 1.4563 interactions per subscriber once it starts collecting data with its own decisions; 0.6305 of the held-out cells were never shown, 0.5868 of the held-out items come from five items, and three items never appear in the held-out set. The previous lesson asked the cold subscriber questions, turned the recommendations toward the domain the subscriber named, and the number read from the log **fell**. There were two explanations: either the questions did not work, or the measure was read from the wrong place. This lesson first builds the measure itself, then measures the same ranking in two separate places. Three things will be built. **Hit rate at k** counts whether a ranking finds the correct item within its first k recommendations. The **cutoff** is k itself and is a measurement decision, not a property of the data. **Position discount** also takes the position within the first k into account: a hit at the first rank is not the same as a hit at the fifth rank. - **RS49. The setup is the same block built in the first lesson** and gives the same numbers: 360 subscribers, 24 items, 3,002 impressions, 577 interactions. The split is also the split of the first lesson: for a subscriber with at least two interactions, the interaction with the largest sequence stamp goes to the held-out set. - **RS50. The three compared setups come from the same family** and are separated by a single hyperparameter: the score is the product of the item's selection count in training and the subscriber's past share in that domain. `w = 0` is the pure baseline — there is no personalization; `w = 1` and `w = 2` weight the domain share lightly and strongly, respectively. - **RS51. The baseline is `w = 0`**, that is, the order of the items most chosen in training. Since the family is single, the difference between the three numbers comes only from the weight. - **RS52. The positional discount weight is `1 / log2(1 + position)`**; the position starts at one. The measure is read over the whole ranking, and the cutoff is not applied. - **RS53. The offline measure is on the log:** the setup ranks, and the held-out item counts as the correct answer. The log holds only the interactions of items that were shown. - **RS54. In the online measure the ranking itself decides what is shown.** Each setup shows each of the 360 subscribers their own top five, the outcome is drawn from the true propensity of the simulated setup, and the measure is the mean interactions per subscriber over twenty periods. Higher is better. - **RS55. The true propensity of the simulated setup is not a method, it is a ceiling.** It is read only for measurement and gives the limit the online number can reach. - **RS56. Experiment design is not done in this lesson.** Sample size, early stopping and multiple comparison calculations were built in the Measurement topic of the User Experience and Behavior Design course and in the Applied Statistics course; here only the difference arising from feedback is measured. #### Hit Rate at k, the Cutoff and Position Discount ```python # COMMON -- FICTIONAL. The subscriber x service item interaction matrix is built inside the lesson. # Impression, selection and score are generated separately: an item is first SHOWN, then # it can be selected, and only if it is selected can it be scored. SEED, M32 = 20260218, 0xFFFFFFFF 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 ITEMS = [ # (name, domain, channel, paid, commitment, appointment, base_share) ("auto_payment_instruction", "billing", "online", 0, 0, 0, 0.90), ("e_invoice_switch", "alert", "online", 0, 0, 0, 0.85), ("payment_reminder_sms", "alert", "online", 0, 0, 0, 0.78), ("installment_plan", "billing", "branch", 0, 1, 0, 0.62), ("remote_reading_application", "meter", "field", 0, 1, 1, 0.55), ("outage_alert_subscription", "alert", "online", 0, 0, 0, 0.50), ("debt_restructuring", "billing", "branch", 0, 1, 0, 0.44), ("address_update", "subscription", "online", 0, 0, 0, 0.40), ("meter_replacement", "meter", "field", 1, 0, 1, 0.36), ("consumption_report_subscription", "alert", "online", 0, 0, 0, 0.32), ("invoice_dispute_record", "billing", "branch", 0, 0, 0, 0.28), ("subscription_transfer", "subscription", "branch", 0, 0, 0, 0.25), ("illicit_use_check_appointment", "meter", "field", 0, 0, 1, 0.22), ("installation_maintenance_package", "technical", "field", 1, 1, 1, 0.19), ("second_meter_request", "meter", "field", 1, 0, 1, 0.16), ("business_tariff_switch", "subscription", "branch", 0, 1, 0, 0.14), ("pressure_regulator_mounting", "technical", "field", 1, 0, 1, 0.12), ("garden_irrigation_tariff", "subscription", "branch", 0, 1, 0, 0.10), ("meter_relocation", "meter", "field", 1, 0, 1, 0.09), ("common_area_sharing_record", "subscription", "branch", 0, 1, 0, 0.08), ("installation_compliance_report", "technical", "field", 1, 0, 1, 0.07), ("late_interest_waiver", "billing", "branch", 0, 0, 0, 0.06), ("mobile_access_permission", "alert", "online", 0, 0, 0, 0.05), ("extra_line_installation", "technical", "field", 1, 1, 1, 0.04), ] SEGMENT = { # propensity of the segment toward the domains; used only inside the generator "saver": {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6}, "payer": {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3}, "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9}, "new": {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7}, } SEGMENT_NAMES = list(SEGMENT) rq = rng(SEED + 101) QUALITY = [0.25 + 0.70 * rq() for _ in ITEMS] # the item's own satisfaction N_SUBSCRIBERS, N_ITEMS = 360, len(ITEMS) SUBSCRIBERS, IMPRESSIONS, INTERACTIONS, SCORES, PROPENSITY = [], {}, {}, {}, {} for i in range(N_SUBSCRIBERS): r = rng(SEED + 7919 * i) a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)] activity = 0.35 + 1.15 * r() ** 1.6 SUBSCRIBERS.append(a) for j, (name, domain, channel, paid, commitment, appointment, share) in enumerate(ITEMS): propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55) PROPENSITY[(a, j)] = propensity if r() < min(0.95, share ** 0.55 * 0.72): # was it shown IMPRESSIONS[(a, j)] = 1 if r() < propensity: # was it selected INTERACTIONS[(a, j)] = r() # value: sequence stamp if r() < 0.32: # did it leave a score raw = (0.16 + 0.50 * SEGMENT[segment][domain] / 1.9 + 0.42 * QUALITY[j] + 0.26 * (r() - 0.5)) SCORES[(a, j)] = max(1, min(5, int(round(raw * 5)))) else: r(), r(), r() import math # The split of lesson 01: for a subscriber with at least two interactions, the interaction with the largest sequence stamp is held out. log = {} for (a, j), stamp in INTERACTIONS.items(): log.setdefault(a, []).append((stamp, j)) TRAIN, HELD_OUT, SEEN = {}, {}, {} for a, entries in log.items(): entries.sort() if len(entries) >= 2: HELD_OUT[a] = entries[-1][1] entries = entries[:-1] for stamp, j in entries: TRAIN[(a, j)] = 1 SEEN.setdefault(a, set()).add(j) EVAL_SUBS = sorted(HELD_OUT) chosen = [0] * N_ITEMS for (a, j) in TRAIN: chosen[j] += 1 DOMAIN_OF = [ITEMS[j][1] for j in range(N_ITEMS)] def make_ranker(w): """Popularity x the subscriber's past domain share. w=0 is the pure baseline. THE MODEL.""" def score(a): counts = {} for i in SEEN.get(a, set()): counts[DOMAIN_OF[i]] = counts.get(DOMAIN_OF[i], 0) + 1 return [chosen[j] * (1.0 + w * counts.get(DOMAIN_OF[j], 0)) for j in range(N_ITEMS)] return score def rank(score, a): s = score(a) return sorted((j for j in range(N_ITEMS) if j not in SEEN.get(a, set())), key=lambda j: (-s[j], j)) SETUPS = (("baseline, w=0", make_ranker(0.0)), ("light, w=1", make_ranker(1.0)), ("strong, w=2", make_ranker(2.0))) print(f"training {len(TRAIN)} interactions, held-out {len(EVAL_SUBS)} subscribers; offline on the log") print("setup k=1 k=3 k=5 k=10 pos. disc. coverage@5") for name, ranker in SETUPS: ranked = [rank(ranker, a) for a in EVAL_SUBS] hits = [sum(1 for t, a in zip(ranked, EVAL_SUBS) if HELD_OUT[a] in t[:n]) / len(EVAL_SUBS) for n in (1, 3, 5, 10)] disc = sum(1.0 / math.log2(2 + t.index(HELD_OUT[a])) for t, a in zip(ranked, EVAL_SUBS)) / len(EVAL_SUBS) cov = len(set(j for t in ranked for j in t[:5])) print(f"{name:<13} {hits[0]:.4f} {hits[1]:.4f} {hits[2]:.4f} {hits[3]:.4f} {disc:.4f} " f"{cov:>2}/{N_ITEMS}") ``` ``` training 410 interactions, held-out 167 subscribers; offline on the log setup k=1 k=3 k=5 k=10 pos. disc. coverage@5 baseline, w=0 0.2575 0.5509 0.6527 0.9162 0.5736 9/24 light, w=1 0.2635 0.5569 0.6647 0.9162 0.5766 12/24 strong, w=2 0.2635 0.5090 0.6886 0.9102 0.5727 13/24 ``` The order of the three setups **changes with the cutoff**. At `k = 3` the strong setup is last (**0.5090**) and the baseline is ahead of it. At `k = 5` the strong setup is first (**0.6886**) and beats the baseline by 0.0359. At `k = 10` the three become indistinguishable: 0.9162, 0.9162 and 0.9102. The same three rankings, the same log, three different orders at three different cutoffs. The cutoff is not a part of the reported number but the decision that produces it; unless it is written down, hit rate at k cannot be read. Position discount gives a fourth order. In this measure the strong setup is last with **0.5727**, though at `k = 5` it was first. The reason is what hit rate at k does not see: the strong setup does put the correct item into the top five, but places it **lower within the five**. Hit rate at k counts every position inside the cutoff as equal; positional discount does not. The two measures end the same ranking in two different orders, and neither is wrong — they measure different things. Beside the fifth column stands a sixth: coverage. The baseline recommends a total of **9** distinct items to 167 subscribers, the strong setup **13**. In all three setups at least eleven items of the catalog never appear in the top five of any subscriber. #### The Same Ranking, While Collecting Its Own Data All the numbers so far were read from a single log, and that log was not collected by any of these three setups. Now the decision changes hands: each setup shows its own top five and sees the outcome. ```python PERIODS = 20 def online(score, k=5): """The ranking itself decides what is shown; the outcome is drawn from the setup.""" total, shown = 0, set() for a in SUBSCRIBERS: top = rank(score, a)[:k] shown.update(top) for day in range(PERIODS): r = rng(SEED + 880000 + a * 37 + day * 911) for j in top: if r() < PROPENSITY[(a, j)]: total += 1 return total / (len(SUBSCRIBERS) * PERIODS), len(shown) print(f"online: each setup shows its own top five, {PERIODS} periods, {len(SUBSCRIBERS)} subscribers") for name, ranker in SETUPS: e, g = online(ranker) expected = sum(sum(PROPENSITY[(a, j)] for j in rank(ranker, a)[:5]) for a in SUBSCRIBERS) / len(SUBSCRIBERS) print(f" {name:<13} interactions per subscriber {e:.4f} (expected {expected:.4f}) " f"items shown {g}/{N_ITEMS}") ``` ``` online: each setup shows its own top five, 20 periods, 360 subscribers baseline, w=0 interactions per subscriber 1.4581 (expected 1.4519) items shown 9/24 light, w=1 interactions per subscriber 1.4788 (expected 1.4795) items shown 12/24 strong, w=2 interactions per subscriber 1.4563 (expected 1.4560) items shown 13/24 ``` The offline order was this: baseline 0.6527, light 0.6647, strong 0.6886 — strong first. The online order is this: strong **1.4563**, baseline **1.4581**, light **1.4788** — strong **last** and below even the baseline. The setup that was first on the offline log cannot even beat the baseline, which does not personalize at all, once it starts making its own decisions. The differences are small and it must be written that they are: between the best and the worst online there are 0.0225 interactions per subscriber. What is measured is not the size of the difference but the **order not carrying over**. Since the number drawn over twenty periods stayed within five parts per thousand of the expected value, this order does not come from sampling noise; it comes from the setups themselves. #### What the Log Cannot See ```python from collections import Counter held_counts = Counter(HELD_OUT.values()) unshown = sum(1 for a in EVAL_SUBS for j in range(N_ITEMS) if (a, j) not in IMPRESSIONS) print(f"what the log can see: {len(EVAL_SUBS)} subscribers x {N_ITEMS} items = {len(EVAL_SUBS) * N_ITEMS} " f"cells, {unshown} ({unshown / (len(EVAL_SUBS) * N_ITEMS):.4f}) never shown") top_five = sorted(range(N_ITEMS), key=lambda j: (-chosen[j], j))[:5] print(f"{sum(held_counts[j] for j in top_five) / len(HELD_OUT):.4f} of the held-out items come from the " f"five items most chosen in training; {sum(1 for j in range(N_ITEMS) if held_counts[j] == 0)} items " f"never appear in the held-out set") def setup_propensity(a): """Not a method: the true propensity of the simulated setup itself. Gives the online ceiling.""" return [PROPENSITY[(a, j)] for j in range(N_ITEMS)] e, g = online(setup_propensity) ranked = [rank(setup_propensity, a) for a in EVAL_SUBS] print(f"setup propensity (online ceiling): online {e:.4f}, items shown {g}/{N_ITEMS}") print(f" offline hit rate@5 of the same ranking " f"{sum(1 for t, a in zip(ranked, EVAL_SUBS) if HELD_OUT[a] in t[:5]) / len(EVAL_SUBS):.4f}") ``` ``` what the log can see: 167 subscribers x 24 items = 4008 cells, 2527 (0.6305) never shown 0.5868 of the held-out items come from the five items most chosen in training; 3 items never appear in the held-out set setup propensity (online ceiling): online 1.6606, items shown 13/24 offline hit rate@5 of the same ranking 0.7485 ``` The divergence comes from here. **0.6305** of the held-out set consists of cells never shown: for those cells the log holds neither a selection nor a rejection, only a blank. The offline measure has to count this blank **as a rejection**, because it has no other reading at hand. The more never-shown items a setup recommends, the more it is penalized offline — even if that item suits the subscriber. The second line shows the same thing from the correct-answer side: **0.5868** of the held-out items come from the five items most chosen in training, and **3** items never appear in the held-out set. A setup that recommends those three items can never score offline. The correct answer itself is a trace of past impression decisions. The third line gives the ceiling of the measure. Ranking by the true propensity of the simulated setup gives **1.6606** online; the baseline stands at 1.4581, the best setup at 1.4788. The best of the three setups closes one tenth of the gap between the ceiling and the baseline. The offline hit rate@5 of the same ranking is **0.7485**, so the offline measure cannot take even the ceiling to 1 — the log can score even the best possible ranking only over items that were shown. #### Summary - Hit rate at k cannot be read without the cutoff being written: the strong setup is last at k=3 (0.5090), first at k=5 (0.6886), and at k=10 the three setups are indistinguishable (0.9162 / 0.9162 / 0.9102). - Position discount sees what the first k does not: the setup that is first at k=5 is last on position weight with 0.5727, because it puts the correct item lower within the top five. - The setup that is first offline (0.6886) is last online (1.4563) and falls below the baseline that does not personalize at all (1.4581); the order does not carry over. - The cause of the divergence is the log itself: 0.6305 of the held-out cells were never shown, 0.5868 of the held-out items come from five items, and 3 items never appear in the held-out set. - The online ceiling is 1.6606; the difference between the baseline at 1.4581 and the best setup at 1.4788 is about one tenth of the gap between the ceiling and the baseline. #### Next Step In this lesson each setup looked at the log **once** and made its decision **once**. In a real system the decision repeats: the item shown produces an interaction, the interaction grows the log, and the growing log determines the next impression. The coverage column already says where this loop is going — the baseline shows 9 of 24 items, the strong setup 13, and an item that is not shown will be shown with even fewer reasons in the next round. The next lesson runs this loop for a few dozen periods: how many items end up never shown, how much popularity bias grows, and in which period the short-term cost of increasing diversity and its long-term gain become equal. ### Diversity and the Echo Chamber Source: https://academia.sh/en/courses/reinforcement-and-recommender/diversity-and-echo-chamber The narrowing of coverage and the growth of popularity bias when the system is fed by its own recommendations: over forty-eight periods the narrow setup after the eighth period never shows 8 of 24 items in any period, six items appear in none of the last twenty-four periods, and the impression share of the top five items rises from 0.4711 to 0.5461. The setup that gives the fifth slot to diversity loses 1.0000 interactions per subscriber in the first eleven periods, finds the item whose conditions changed in the twelfth period and moves ahead, breaks even cumulatively in the twenty-seventh period and finishes the forty-eighth period 1.2250 ahead. The previous lesson had each setup look at the log once. In a real system the decision repeats: the item shown produces an interaction, the interaction grows the log, and the growing log determines the next impression. This lesson runs that loop for forty-eight periods and counts where the coverage goes. - **RS57. The setup is the same block built in the first lesson**; the starting log of the loop is the 3,002 impressions and 577 interactions of that setup. - **RS58. Each period the system shows each subscriber five items** and estimates the score as the interaction rate per impression of that item within the subscriber's group: `(interactions + 0.5) / (impressions + 5)`. The group is the dominant domain in the subscriber's past and is the only subscriber feature the system sees. - **RS59. Two setups are compared.** The narrow setup gives all five slots to the estimate and is **the baseline**, since it contains no diversity rule. The wide setup gives four to the estimate and reserves the fifth for the item shown least until then. - **RS60. In the twelfth period the response rate of one item rises eightfold** and hits the 0.95 ceiling; this is the moment the environment changes, and no setup is told. - **RS61. Three numbers are written each period:** interactions per subscriber (higher is better), the number of items not shown at all that period (lower is better) and the share of impressions on the five most shown items (lower is better) — the last is the measure of **popularity bias**. Selection bias is in the Applied Statistics course. #### The Setup Fed by Its Own Log ```python # COMMON -- FICTIONAL. The subscriber x service item interaction matrix is built inside the lesson. # Impression, selection and score are generated separately: an item is first SHOWN, then # it can be selected, and only if it is selected can it be scored. SEED, M32 = 20260218, 0xFFFFFFFF 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 ITEMS = [ # (name, domain, channel, paid, commitment, appointment, base_share) ("auto_payment_instruction", "billing", "online", 0, 0, 0, 0.90), ("e_invoice_switch", "alert", "online", 0, 0, 0, 0.85), ("payment_reminder_sms", "alert", "online", 0, 0, 0, 0.78), ("installment_plan", "billing", "branch", 0, 1, 0, 0.62), ("remote_reading_application", "meter", "field", 0, 1, 1, 0.55), ("outage_alert_subscription", "alert", "online", 0, 0, 0, 0.50), ("debt_restructuring", "billing", "branch", 0, 1, 0, 0.44), ("address_update", "subscription", "online", 0, 0, 0, 0.40), ("meter_replacement", "meter", "field", 1, 0, 1, 0.36), ("consumption_report_subscription", "alert", "online", 0, 0, 0, 0.32), ("invoice_dispute_record", "billing", "branch", 0, 0, 0, 0.28), ("subscription_transfer", "subscription", "branch", 0, 0, 0, 0.25), ("illicit_use_check_appointment", "meter", "field", 0, 0, 1, 0.22), ("installation_maintenance_package", "technical", "field", 1, 1, 1, 0.19), ("second_meter_request", "meter", "field", 1, 0, 1, 0.16), ("business_tariff_switch", "subscription", "branch", 0, 1, 0, 0.14), ("pressure_regulator_mounting", "technical", "field", 1, 0, 1, 0.12), ("garden_irrigation_tariff", "subscription", "branch", 0, 1, 0, 0.10), ("meter_relocation", "meter", "field", 1, 0, 1, 0.09), ("common_area_sharing_record", "subscription", "branch", 0, 1, 0, 0.08), ("installation_compliance_report", "technical", "field", 1, 0, 1, 0.07), ("late_interest_waiver", "billing", "branch", 0, 0, 0, 0.06), ("mobile_access_permission", "alert", "online", 0, 0, 0, 0.05), ("extra_line_installation", "technical", "field", 1, 1, 1, 0.04), ] SEGMENT = { # propensity of the segment toward the domains; used only inside the generator "saver": {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6}, "payer": {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3}, "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9}, "new": {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7}, } SEGMENT_NAMES = list(SEGMENT) rq = rng(SEED + 101) QUALITY = [0.25 + 0.70 * rq() for _ in ITEMS] # the item's own satisfaction N_SUBSCRIBERS, N_ITEMS = 360, len(ITEMS) SUBSCRIBERS, IMPRESSIONS, INTERACTIONS, SCORES, PROPENSITY = [], {}, {}, {}, {} for i in range(N_SUBSCRIBERS): r = rng(SEED + 7919 * i) a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)] activity = 0.35 + 1.15 * r() ** 1.6 SUBSCRIBERS.append(a) for j, (name, domain, channel, paid, commitment, appointment, share) in enumerate(ITEMS): propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55) PROPENSITY[(a, j)] = propensity if r() < min(0.95, share ** 0.55 * 0.72): # was it shown IMPRESSIONS[(a, j)] = 1 if r() < propensity: # was it selected INTERACTIONS[(a, j)] = r() # value: sequence stamp if r() < 0.32: # did it leave a score raw = (0.16 + 0.50 * SEGMENT[segment][domain] / 1.9 + 0.42 * QUALITY[j] + 0.26 * (r() - 0.5)) SCORES[(a, j)] = max(1, min(5, int(round(raw * 5)))) else: r(), r(), r() DOMAIN_OF = [ITEMS[j][1] for j in range(N_ITEMS)] COUNTS = {a: {} for a in SUBSCRIBERS} for (a, j) in INTERACTIONS: # subscriber group: dominant domain in the past COUNTS[a][DOMAIN_OF[j]] = COUNTS[a].get(DOMAIN_OF[j], 0) + 1 GROUP_OF = {a: (max(sorted(counts), key=lambda x: counts[x]) if counts else "none") for a, counts in COUNTS.items()} PERIODS, K, SHIFT, RISING = 48, 5, 12, 9 # in period 12 the response of item 9 changes def run_loop(wide): """The system is fed by its own log: it measures what it shows, it shows what it measures.""" shown, selected = {}, {} for (a, j) in IMPRESSIONS: shown[(GROUP_OF[a], j)] = shown.get((GROUP_OF[a], j), 0) + 1 for (a, j) in INTERACTIONS: selected[(GROUP_OF[a], j)] = selected.get((GROUP_OF[a], j), 0) + 1 total, rows = [0] * N_ITEMS, [] for d in range(1, PERIODS + 1): period_shown, period_inter = [0] * N_ITEMS, 0 for a in SUBSCRIBERS: g = GROUP_OF[a] order = sorted(range(N_ITEMS), key=lambda j: (-(selected.get((g, j), 0) + 0.5) / (shown.get((g, j), 0) + 5.0), j)) top = order[:K] if not wide else order[:K - 1] + [ # fifth slot to diversity min((j for j in range(N_ITEMS) if j not in order[:K - 1]), key=lambda j: (total[j], (j + a + d) % N_ITEMS))] r = rng(SEED + 660000 + a * 53 + d * 1301) for j in top: period_shown[j] += 1 total[j] += 1 shown[(g, j)] = shown.get((g, j), 0) + 1 e = PROPENSITY[(a, j)] if j == RISING and d >= SHIFT: e = min(0.95, e * 8.0) if r() < e: period_inter += 1 selected[(g, j)] = selected.get((g, j), 0) + 1 top5 = sorted(range(N_ITEMS), key=lambda j: -period_shown[j])[:5] rows.append((period_inter / len(SUBSCRIBERS), [j for j in range(N_ITEMS) if period_shown[j] == 0], sum(period_shown[j] for j in top5) / sum(period_shown), period_shown[RISING])) return rows NARROW = run_loop(False) print(f"narrow setup: top {K} every period, {PERIODS} periods, {len(SUBSCRIBERS)} subscribers") print(f"in period {SHIFT} the response rate of {ITEMS[RISING][0]} rises eightfold") print("period interactions/subscriber items never shown that period top-five impression share") for d in (1, 8, 24, 48): e, never, p, n = NARROW[d - 1] print(f" {d:>2} {e:.4f} {len(never):>2}/{N_ITEMS} {p:.4f}") LOCKED = set(range(N_ITEMS)) for x in NARROW[PERIODS // 2:]: LOCKED &= set(x[1]) print(f"items not shown in ALL of the last {PERIODS - PERIODS // 2} periods: {len(LOCKED)}/{N_ITEMS}") ``` ``` narrow setup: top 5 every period, 48 periods, 360 subscribers in period 12 the response rate of consumption_report_subscription rises eightfold period interactions/subscriber items never shown that period top-five impression share 1 1.2250 0/24 0.4711 8 1.3917 8/24 0.5461 24 1.4583 8/24 0.5461 48 1.3194 8/24 0.5461 items not shown in ALL of the last 24 periods: 6/24 ``` In the first period all 24 items are shown. In the eighth period eight items drop out; the number freezes at **8/24** there and does not move until the forty-eighth period. Six items are shown in **none** of the last twenty-four periods. Popularity bias is the other face of the same movement: the impression share of the top five items rises from 0.4711 to **0.5461** and stays there. The loop closes on itself. No new information is born about an item that is not shown, its estimate stays low, and the low estimate leaves it out again in the next period: the item stays out not because it is bad but because it **is not measured**. In the twelfth period the environment changes but the narrow setup cannot see it, because the only way to tell the system is for that item to be shown. #### Giving the Fifth Slot to Diversity ```python WIDE = run_loop(True) WIDE_LOCKED = set(range(N_ITEMS)) for x in WIDE[PERIODS // 2:]: WIDE_LOCKED &= set(x[1]) print(f"wide setup: top {K - 1} by model, fifth slot to the least shown item") print("period interactions/subscriber items never shown that period top-five impression share shifted item") for d in (1, 8, 24, 48): e, never, p, n = WIDE[d - 1] print(f" {d:>2} {e:.4f} {len(never):>2}/{N_ITEMS} " f"{p:.4f} {n:>3}") cost = sum(WIDE[d][0] - NARROW[d][0] for d in range(SHIFT - 1)) gain = sum(WIDE[d][0] - NARROW[d][0] for d in range(SHIFT - 1, PERIODS)) equal = [d + 1 for d in range(PERIODS) if sum(x[0] for x in WIDE[:d + 1]) > sum(x[0] for x in NARROW[:d + 1])] print(f"short-term cost (total of periods 1-{SHIFT - 1}): per subscriber {cost:+.4f}") print(f"long-term gain (total of periods {SHIFT}-{PERIODS}): per subscriber {gain:+.4f}") print(f"cumulative break-even period: {equal[0] if equal else 'none'}; at period {PERIODS} the " f"cumulative difference is {sum(x[0] for x in WIDE) - sum(x[0] for x in NARROW):+.4f}") print(f"the shifted item at period {PERIODS}: narrow setup {NARROW[-1][3]} impressions, " f"wide setup {WIDE[-1][3]}") print(f"data collected -- narrow: {len(LOCKED)} items never shown, top-five impression share " f"{NARROW[-1][2]:.4f}; wide: {len(WIDE_LOCKED)} items, {WIDE[-1][2]:.4f}") ``` ``` wide setup: top 4 by model, fifth slot to the least shown item period interactions/subscriber items never shown that period top-five impression share shifted item 1 1.1833 0/24 0.4611 37 8 1.2722 0/24 0.5011 81 24 1.4806 0/24 0.4989 97 48 1.3889 0/24 0.4989 97 short-term cost (total of periods 1-11): per subscriber -1.0000 long-term gain (total of periods 12-48): per subscriber +2.2250 cumulative break-even period: 27; at period 48 the cumulative difference is +1.2250 the shifted item at period 48: narrow setup 17 impressions, wide setup 97 data collected -- narrow: 6 items never shown, top-five impression share 0.5461; wide: 0 items, 0.4989 ``` The cost is paid in the first eleven periods: the wide setup finishes **1.0000** interactions per subscriber behind, because one of the five slots goes not to the best estimate but to the least known item. In return coverage never narrows and the share of the top five items stays at **0.4989**. In the twelfth period the account turns. Since the wide setup already shows the item whose response changed in its rotating slot, it notices the change in the **same period**. In the forty-eighth period that item receives **97** impressions in the wide setup and **17** in the narrow setup. The total gain between the twelfth and the forty-eighth is **+2.2250** per subscriber; together with the **−1.0000** cost of the first eleven periods, the cumulative difference reaches zero in the **twenty-seventh period** and becomes **+1.2250** in the forty-eighth. Diversity is not a matter of taste but **a measurement budget**: a system that never measures wins as long as the environment stays constant and loses every time it changes. "Echo chamber" is a **metaphor** that describes this table and has no number of its own; its counterpart is the number of items not shown and the impression share of the top five. The place where it misleads is this: in the setup no subscriber's propensity changes. What narrows is not the interest of the subscriber but **the domain the system measures**, and an item that is not measured being counted as bad is not a belief but a gap in the record. #### Summary - After the eighth period the narrow setup does not show 8 of 24 items in any period, 6 items appear in none of the last twenty-four periods, and the impression share of the top five rises from 0.4711 to 0.5461. - The short-term cost of diversity is −1.0000 per subscriber in the first eleven periods and its long-term gain is +2.2250 between the twelfth and forty-eighth; the cumulative difference breaks even in the twenty-seventh period. - The echo chamber is a metaphor; in this setup what narrows is not the interest of the subscriber but the domain the system measures. #### Course Wrap-Up The account of fourteen lessons is in a single table, and each number was read from its own lesson. The rows do not carry a common unit; the last column writes the metric and its direction. **The difference is given in a single sign convention: the method's number minus the baseline** and is in parentheses in the third column. The fourth column is the course's own number: the unseen state, the untried action, the item not shown. | Lesson | Baseline | Method's number | Data collected | Metric | |---|---|---|---|---| | Reinforcement 01 | random action 10.432 | hand-written rule 20.621 (+10.189) | 1,355 of 1,458 pairs unseen | return, higher is better | | Reinforcement 02 | random action 10.432 | rule with history field 23.148 (+12.716) | state space from 243 to 1,215; no count | return, higher is better | | Reinforcement 03 | agent without exploration −16.492 | exploration rate 0.20 gives 25.659 (+42.151) | 880 of 1,458 pairs untried | return, higher is better | | Reinforcement 04 | rule policy 20.621 | table with exploration 24.419 (+3.798) | 221 of 1,458 cells not updated | return, higher is better | | Reinforcement 05 | random action 10.432 | replay buffer 26.233 / 25.302 (+15.801) | 678 of 1,458 cells not updated | return, higher is better | | Reinforcement 06 | zero weights 10.177 | baseline subtraction 22.866 / 22.190 (+12.689) | agreement 0.290; no count | return, higher is better | | Reinforcement 07 | raw return 14.207 / 17.218 | advantage 23.401 / 23.755 (+9.194) | 0 of 5 subscribers left unvisited | return, higher is better | | Recommender 01 | random order 0.2036 | most chosen item 0.6527 (+0.4491) | 15 of 24 items never recommended | top-five hit rate, higher is better | | Recommender 02 | popularity 0.6527 | content-based 0.4431 (−0.2096) | 0 of 24 items not shown | top-five hit rate, higher is better | | Recommender 03 | popularity 0.6527 | user-based 0.6946 (+0.0419) | 8 of 24 items not shown | top-five hit rate, higher is better | | Recommender 04 | popularity 0.6527 | skipping setup 0.7006 (+0.0479) | 15 of 24 items not shown | top-five hit rate, higher is better | | Recommender 05 | popularity fallback 0.5752 | three-question intake 0.5487 (−0.0265) | 11 of 24 items not shown | cold-start top-five hit rate, higher is better | | Recommender 06 | online baseline 1.4581 | light setup 1.4788 (+0.0207) | 12 of 24 items not shown | interactions per subscriber, higher is better | | Recommender 07 | narrow setup, 48 periods | wide setup (+1.2250) | 8 of 24 items not shown | cumulative interactions, higher is better | **The rule of the course is this: the measure of a system that makes decisions cannot be read without accounting for the fact that those decisions change its own data; a system that does not write down the data it collected counts as unmeasured.** The fourth column reduces to a single number: the total of the unseen pairs, the cells not updated, the subscribers left unvisited and the items not shown in the twelve lessons that print a count is **3,203 units**. The units are not the same and the total is a count, not a mean: behind every performance number measured in this course stand more than three thousand units about which the method learned nothing. Reinforcement 02 and 06 print no count and do not enter the sum. The second claim of the course is read from the same table: **a number measured offline does not tell online behavior.** In four lessons the two numbers diverged. In Recommender 06 the setup that was first offline with 0.6886 was last with 1.4563 when it made its own impression decisions, and fell below the baseline. In Recommender 07 the narrow setup that looked good on the log finished forty-eight periods 1.2250 behind. In Recommender 05 the hit rate read from the log fell from 0.5752 to 0.5487 once questions were asked. In Reinforcement 03 the divergence appeared in the opposite direction: the **behavior** of the agent with exploration rate 1.00 was bad but **the data it collected** was good, and the frozen table gave 23.000. There is a single source: the log the number is read from is a log whose decisions were made by another setup. In fifty-two lessons the baseline was written beside every number, and in the last fourteen it was counted that the system changes its own data. The only thing never asked is **for whom** it is measured. Every number in the table is the mean over all subscribers: if the same number says two different things in two subgroups, which one is reported; what is the **basis** on which the system shows an item to one person and not to another, and can it be read; and with which number is the harm written that a system with a good measure does to a group that never enters the measure. The next course, Model Evaluation, Interpretability and Ethics, opens with these three questions.