==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 12 . REINFORCEMENT LEARNING FROM ZERO
Bandits and Exploration: The Greedy Shopkeeper and His Faulty Machines
============================================================================================
A greedy shopkeeper runs a medical-testing clinic at a busy railway station. He rents
testing machines from a factory down the road -- dozens of them, some accurate, some not.
Only the factory owner knows which is which. (Textbooks stage this same game with slot
machines and call it the multi-armed bandit -- one machine is an arm. This page keeps the
clinic.)
Money enters like this. When a patient goes through a machine and the result is clean and
fast, the hospital down the road pays the shopkeeper. Better machines get cleaner results,
fewer repeats, fewer refunds -- so better machines earn more per patient ON AVERAGE.
And that average is hidden. After each patient, the shopkeeper sees one number: the payout
for that one test. Same machine, different patients, different number each time -- the
machine is faulty, it wobbles. Over many patients the wobble cancels and the true average
shows through. Machine A might truly average 1.2 per patient; right now, after one patient,
all the shopkeeper has seen is 1.6. He can never read 1.2 off a label. He can only send
patients through and watch.
(For now the machines are stable -- same true average all month, same wobble every patient.
Machines that change overnight arrive further down this page.)
He has three machines. Before any patient, his records:
machine: A B C
q (guess): 0.0 0.0 0.0 <- his guess of each machine's true average
n (count): 0 0 0 <- how many patients each machine has served
All guesses start at 0.0. He sends the first patient to a randomly picked machine: A.
ONE NUMBER ARRIVES, WITH NO NAME ON IT
Patient 1 goes through machine A. Payout arrives: 1.6.
That payout arrives as a bare number -- nothing links it to a machine. So before sending
the patient, the shopkeeper wrote one word on a scrap: "last = A". That scrap is the only
thread. Without it, 1.6 is just 1.6, not "1.6 from machine A".
Update machine A's records:
n[A] = 0 + 1 = 1
nudge = 1 / n[A] = 1 / 1 = 1.0
q[A] = 0.0 + 1.0 x (1.6 - 0.0) = 1.6
Nudge size is 1 divided by the count of patients through A. First patient: nudge = 1, so
the entire 1.6 becomes the guess -- fair, since it is the only data point in existence.
machine: A B C
q (guess): 1.6 0.0 0.0
n (count): 1 0 0
scrap: "last = A"
Next patient -- which machine? Highest guess: A (1.6 beats 0.0 twice). Send to A again.
Patient 2 through machine A. Payout arrives: 0.9.
n[A] = 1 + 1 = 2
nudge = 1 / 2 = 0.50
q[A] = 1.6 + 0.50 x (0.9 - 1.6)
= 1.6 + 0.50 x (-0.7)
= 1.6 - 0.35
= 1.25
machine: A B C
q (guess): 1.25 0.0 0.0
n (count): 2 0 0
A second patient pulled the guess down from 1.6 toward the truth, and the nudge shrank to
0.50 because two data points exist now -- fresh data earns less weight than it did when it
was all there was. A still highest (1.25 beats 0.0). Third patient to A.
Patient 3 through machine A. Payout arrives: 1.4.
n[A] = 2 + 1 = 3
nudge = 1 / 3 = 0.333
q[A] = 1.25 + 0.333 x (1.4 - 1.25)
= 1.25 + 0.333 x 0.15
= 1.25 + 0.050
= 1.30
machine: A B C
q (guess): 1.30 0.0 0.0
n (count): 3 0 0
AN AVERAGE KEPT WITHOUT STORING THE PILE
That two-line habit -- q = old + (1/n) x (payout - old) -- IS the plain average, kept
without a pile of old receipts. Verify: average of 1.6, 0.9, 1.4 = 3.9 / 3 = 1.30. Same
number the nudges produced. (Textbooks call this the sample-average update.)
Full check across four patients, both routes side by side:
patient 1, payout 1.6: q = 0.00 + (1/1) x (1.6 - 0.00) = 1.60 avg(1.6) = 1.60
patient 2, payout 0.9: q = 1.60 + (1/2) x (0.9 - 1.60) = 1.25 avg(1.6,0.9) = 2.5/2 = 1.25
patient 3, payout 1.4: q = 1.25 + (1/3) x (1.4 - 1.25) = 1.30 avg(1.6,0.9,1.4) = 3.9/3 = 1.30
patient 4, payout 1.2: q = 1.30 + (1/4) x (1.2 - 1.30) = 1.275 avg(1.6,0.9,1.4,1.2)= 5.1/4 = 1.275
Guess creeps toward the true average (1.2) with no old payout stored anywhere. Two records
per machine do all the work: the count feeds the nudge size; the payout feeds the
(payout - old) part. And the count counts PATIENTS, never money -- a patient paying 900
would still add 1 to the count, not 900.
A TIE AT PATIENT ONE DECIDES EVERYTHING
To pick the next machine, find the highest guess and hand back its slot number -- the
index, not the value. (Textbooks write this pick-the-biggest-index as argmax.)
q = [1.30, 0.0, 0.0] -> biggest sits at index 0 -> machine A
Now two machines tie:
q = [1.0, 1.0, 0.5]
lazy pick: read left to right, return the first winner -> always 0. B ignored forever.
fair pick: collect every tied slot -> [0, 1]. flip a fair coin. 0 or 1 equally.
Why this matters: at the very start q = [0.0, 0.0, 0.0] -- ALL THREE tied. A lazy pick
returns 0 every single time, machine A absorbs a thousand patients, and B and C are never
tried once. Three lines of care fix it: collect the tied indexes, pick one at random.
GREED LOCKS ONTO THE FIRST WINNER
That fair pick solves the tie. It does not save a greedy shopkeeper. Say the three true
averages (known only to the factory) are A = 1.2, B = -0.3, C = 0.8. Watch a
pick-the-highest-guess-always shopkeeper across 1000 patients:
after patient 1: q = [ 1.60, 0.00, 0.00 ]
after patient 10: q ~ [ 1.28, 0.00, 0.00 ]
after patient 100: q ~ [ 1.21, 0.00, 0.00 ]
after patient 1000: q ~ [ 1.20, 0.00, 0.00 ]
Whichever machine first earns a positive payout captures nearly every patient after it.
Here A went first, paid 1.6, and 1.6 beats the untouched 0.0s -- so the highest-guess rule
returns A forever. B and C stay mysteries the shopkeeper chose not to solve.
This flaw is structural, not bad luck. Only the machine just played gets an update; every
unplayed machine sits at 0.0; a settled positive guess beats 0.0 forever. Machine B's true
average could be 2.0 -- the shopkeeper would earn 1.2 per patient while 2.0 sat idle,
and his own books would show nothing wrong.
Scale the same disease. Say 100 machines, and only 10 patients so far:
machines 1-4: tested. guesses are real numbers.
machines 5-100: never tested. guesses sit at 0.0 -- not "bad", UNKNOWN.
Patient 11 arrives; greed picks the best tested machine; tested beats untested from here
to eternity. Machine 47 might earn triple. Finding that out has exactly one price: send a
patient through machine 47 -- a patient who probably earns less than the current best.
That wasted patient is not optional waste. It is the only admission fee the truth accepts.
A 10% TAX THAT BUYS THE TRUTH
So build the waste in, on purpose. Before each pick, the shopkeeper rolls a number
between 0.0 and 1.0:
roll < 0.10 -> EXPLORE: send the patient to a RANDOM machine
roll >= 0.10 -> EXPLOIT: send the patient to the highest-guess machine
Ten percent of patients go to random machines; ninety percent go to the current best.
(Textbooks call the 0.10 epsilon, and the whole rule epsilon-greedy.)
A few patients under this rule:
patient 2, roll = 0.07: EXPLORE -> random -> machine C (first patient ever on C)
patient 4, roll = 0.54: EXPLOIT -> machine A (highest guess)
patient 9, roll = 0.03: EXPLORE -> random -> machine B (payout low: B is a loser)
patient 17, roll = 0.91: EXPLOIT -> machine A
After 1000 patients, about 100 of them scattered at random:
q ~ [ 1.20, -0.31, 0.79 ] true averages: 1.2, -0.3, 0.8
All three truths discovered. That is what the 10% tax bought.
Turn the dial too far and it backfires: at 0.4, the shopkeeper keeps feeding the known
loser 40% of the time and earnings sag. At 0.0 the tax vanishes and greed locks on, as
above. Small and nonzero is the working zone.
A FACTORY SWAP, AND A NUDGE GONE DEAF
One question remains inside the update itself: should the nudge shrink as data piles up,
or hold steady?
Shrinking nudge, 1/n:
n: 1 2 3 10 100 1000
nudge: 1.000 0.500 0.333 0.100 0.010 0.001
Early patients pull hard, late ones barely register, the guess settles and stays. Exactly
right for machines that never change.
Fixed nudge, 0.1 every patient (textbooks: constant step size):
n: 1 2 3 10 100 1000
nudge: 0.1 0.1 0.1 0.1 0.1 0.1
Guess never fully settles -- it always moves 10% of the gap toward the latest payout.
Slightly noisier in a stable world. Now watch why anyone would accept that noise.
Overnight, the factory swaps machine A's internals. True average drops from 1.2 to -1.0
(a recalibration gone wrong, never corrected). Next payout from A: -0.8. Both shopkeepers
have served 10,000 patients and hold q[A] = 1.20.
shrinking nudge: nudge = 1/10000 = 0.0001
q[A] = 1.20 + 0.0001 x (-0.8 - 1.20) = 1.20 - 0.0002 = 1.1998
barely moved. thousands more patients to unlearn 1.2.
fixed nudge 0.1:
q[A] = 1.20 + 0.1 x (-0.8 - 1.20) = 1.20 - 0.20 = 1.00 after 1 patient
q[A] ~ -0.23 after 10 patients -- heading down fast
q[A] ~ -0.73 after 20
q[A] ~ -0.91 after 30 -- close enough to stop trusting A
A shrunk nudge is a shopkeeper gone deaf: he heard plenty in his youth and now nothing
reaches him. Fixed 0.1 keeps one ear open forever. That is the whole trade: shrinking
settles on a frozen truth; fixed tracks a moving one.
THREE SHOPKEEPERS, SAME MACHINES
Same three machines (true averages 1.2, -0.3, 0.8), one thousand patients each:
greedy:
nudge = 1/n, pick = highest guess always
q after 1000: [ 1.20, 0.00, 0.00 ] B and C never touched
epsilon-greedy (0.1):
nudge = 1/n, pick = random 10% / highest 90%
q after 1000: [ 1.20, -0.31, 0.79 ] all three found; keeps paying the 10% tax
fixed-nudge (0.1) + epsilon (0.1):
q after 1000: [ ~1.2, ~-0.3, ~0.8 ] guesses jitter, never fully settle
stable world: slightly worse than epsilon-greedy (noisier guesses, more wrong picks)
changed world: adapts in ~30 patients where the shrunk nudge needs hundreds
One run proves nothing -- an early lucky or unlucky payout can make the best machine look
bad for a while. Averaging many runs shrinks that luck (it never fully removes it) and the
pattern above is what remains.
Pencil work done. Below, the same three shopkeepers in Python -- every patient hard-coded,
payouts fixed to the walkthrough's numbers (1.6, 0.9, 1.4: made-up wobble around A's true
1.2, chosen to teach; a live machine would roll fresh ones), no loops, so every update is
one visible line.
# ---------------------------------------------------------------
# factory side, hidden in real life: true averages
# A = 1.2 B = -0.3 C = 0.8
# shopkeeper side: q = guesses, n = patient counts
# ---------------------------------------------------------------
# =================================================================
# greedy shopkeeper -- highest guess always, nudge = 1/n
# =================================================================
print("=== greedy ===")
q_A, q_B, q_C = 0.0, 0.0, 0.0
n_A, n_B, n_C = 0, 0, 0
# patient 1 -> all tied at 0.0, random pick lands A. payout 1.6.
n_A = n_A + 1 # 1
nudge = 1 / n_A # 1/1 = 1.0
q_A = q_A + nudge * (1.6 - q_A) # 0.0 + 1.0 x 1.6 = 1.6
print(q_A, q_B, q_C) # 1.6 0.0 0.0
# patient 2 -> highest guess is A (1.6). payout 0.9.
n_A = n_A + 1 # 2
nudge = 1 / n_A # 1/2 = 0.5
q_A = q_A + nudge * (0.9 - q_A) # 1.6 + 0.5 x (-0.7) = 1.25
print(q_A, q_B, q_C) # 1.25 0.0 0.0
# patient 3 -> highest guess is A (1.25). payout 1.4.
n_A = n_A + 1 # 3
nudge = 1 / n_A # 1/3 = 0.333...
q_A = q_A + nudge * (1.4 - q_A) # 1.25 + 0.333 x 0.15 = 1.30
print(q_A, q_B, q_C) # 1.30 0.0 0.0
# ...and so on forever: A's guess beats the untouched 0.0s every time.
# after 1000 patients: q ~ [1.20, 0.00, 0.00]. B and C never move.
# =================================================================
# epsilon-greedy shopkeeper -- roll first, then pick
# =================================================================
print("=== epsilon-greedy ===")
q_A, q_B, q_C = 0.0, 0.0, 0.0
n_A, n_B, n_C = 0, 0, 0
# patient 1 -> all tied, random pick lands A. payout 1.6.
n_A = n_A + 1 # 1
q_A = q_A + (1 / n_A) * (1.6 - q_A) # 0.0 + 1.0 x 1.6 = 1.6
print(q_A, q_B, q_C) # 1.6 0.0 0.0
# patient 2 -> roll 0.07 < 0.10: EXPLORE. random machine: C. payout 0.9.
n_C = n_C + 1 # 1
q_C = q_C + (1 / n_C) * (0.9 - q_C) # 0.0 + 1.0 x 0.9 = 0.9
print(q_A, q_B, q_C) # 1.6 0.0 0.9 <- C sampled at last
# patient 3 -> roll 0.54 >= 0.10: EXPLOIT. highest guess: A (1.6). payout 0.9.
n_A = n_A + 1 # 2
q_A = q_A + (1 / n_A) * (0.9 - q_A) # 1.6 + 0.5 x (-0.7) = 1.25
print(q_A, q_B, q_C) # 1.25 0.0 0.9
# patient 4 -> roll 0.02 < 0.10: EXPLORE. random machine: B. payout -0.4.
n_B = n_B + 1 # 1
q_B = q_B + (1 / n_B) * (-0.4 - q_B) # 0.0 + 1.0 x (-0.4) = -0.4
print(q_A, q_B, q_C) # 1.25 -0.4 0.9 <- B found out as a loser
# after 1000 patients: q ~ [1.20, -0.30, 0.80]. all three truths found.
# =================================================================
# fixed-nudge shopkeeper -- nudge = 0.1 always, no counts needed
# =================================================================
print("=== fixed nudge 0.1 ===")
q_A, q_B, q_C = 0.0, 0.0, 0.0
# patient 1 -> lands A. payout 1.6. only 10% of the gap is taken.
q_A = q_A + 0.1 * (1.6 - q_A) # 0.0 + 0.1 x 1.6 = 0.16
print(q_A, q_B, q_C) # 0.16 0.0 0.0
# patient 2 -> highest guess A (0.16). payout 0.9.
q_A = q_A + 0.1 * (0.9 - q_A) # 0.16 + 0.1 x 0.74 = 0.234
print(q_A, q_B, q_C) # 0.234 0.0 0.0
# creeps up slowly, never fully settles -- and that is the feature:
# swap day. q_A sits at 1.20 after thousands of patients; the factory
# quietly drops A's true average to -1.0. next payout: -0.8.
q_A = 1.20
q_A = q_A + 0.1 * (-0.8 - q_A) # 1.20 + 0.1 x (-2.0) = 1.00
print(q_A) # 1.00 -- one patient, already falling
# ten more patients near -1.0 drag it to ~ -0.23; thirty land it near -0.91.
# a 1/n shopkeeper at n = 10000 would have moved 0.0002 on that first patient.
----------------------------------------------------------------------------------------------
<- prev: Chapter 12 intro: Five Cats, One New Power Each
-> next: Chapter 12, Part 2: Worth and Bellman from Zero
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================