==============================================================================================
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
Worth and Bellman from Zero: What a Spot Is Worth When the Future Branches
============================================================================================
A shopkeeper who never leaves his counter has the easiest learning job there is: pull a
lever, read a payout, fold it into an average. One place to stand, and each choice's worth
is just its average payout -- nothing stands behind the choice.
Now let the agent MOVE. Many spots, arrows between them, and suddenly a spot's worth
cannot be pinned down alone: what this spot is worth leans on what the next spot is worth,
and the next leans on the one after. Before anyone can grade a plan or improve one, "worth"
itself has to be built -- what it means when spots chain together, when a move lands by
chance, and when the future refuses to end. Build it piece by piece, each piece forced by a
hole in the last.
A RETURN IS A PILE OF REWARDS, NOTHING MORE
A reward is one number you grab on one move. Three moves, grabbing +2, then +1, then +3:
now ──(+2)──► ──(+1)──► ──(+3)──► done
pile = 2 + 1 + 3 = 6
That pile -- every reward grabbed from a moment on, added straight up -- is called the
return. An addition, nothing fancier. And a spot's worth will be a measure of that pile:
stand here, keep moving under some rule, how big a pile do you collect? Four holes stand
between that sentence and a number you can compute: rewards can be unsure, piles can run
forever, some tasks end and some don't, and something has to say where each move lands.
One hole at a time.
A REWARD CAN BE UNSURE, SO AVERAGE IT
Some moves roll a die for their reward. To know what such a move gives you PER TRY, run it
many times and split the pile evenly.
One move that pays +1 (chance 1/2) or +3 (chance 1/2). Run it 10 times:
runs: 1 1 1 1 1 3 3 3 3 3 <- five 1s, five 3s
pile = 5 x 1 + 5 x 3 = 5 + 15 = 20
per try = 20 / 10 = 2
A shortcut skips the 10 runs -- each value times its chance, added:
1 x 1/2 + 3 x 1/2 = 0.5 + 1.5 = 2
Same 2. That per-try number is the average, and "value x chance, added" is how it is
computed everywhere below. (Textbooks call it the expected value.)
A move pays 0 (chance 1/4) or +4 (chance 3/4). Work its average on your slate.
Check: 0 x 1/4 + 4 x 3/4 = 0 + 3 = 3.
Here is why ONLY the average will matter. Every worth formula below has exactly one slot
for a move's reward, and the average is what fills it -- so two moves with the same average
but different noise drop the same number into that slot and produce the same worth. Proof
in numbers (both moves land on a spot worth 10; a future worth counts 0.9 of itself, the
fade defined next):
story A: pays +2 (chance 1/2) or 0 (chance 1/2) -> average = 1
story B: pays +1 flat, every time -> average = 1
story A worth: 1 + 0.9 x 10 = 10.0
story B worth: 1 + 0.9 x 10 = 10.0
Same 10.0. Noise pattern irrelevant; only the mean enters.
AN ENDLESS PILE IS NOT A NUMBER, SO FADE IT
A reward arriving later counts for less than the same reward now. How much less per move
is one dial: gamma, written g here, set to 0.9 in these posts. A +10, by arrival time:
+10 right now = 10
+10, one move off = 0.9 x 10 = 9.0
+10, two moves off = 0.9 x 9 = 8.1
+10, three moves off = 0.9 x 8.1 = 7.29
Each move of distance multiplies by 0.9 once more: a reward k moves away counts
(0.9)^k x reward.
And the reason is not impatience -- it is survival of the arithmetic. Without fading, a
task that runs forever grabbing +1 a move piles up
1 + 1 + 1 + ... -> no limit. not a number.
With the fade, that same endless +1 stream becomes
1 + 0.9 + 0.9^2 + 0.9^3 + ...
Call the whole pile S and subtract its own 0.9-copy from it:
S = 1 + 0.9 + 0.9^2 + 0.9^3 + ...
0.9 x S = 0.9 + 0.9^2 + 0.9^3 + ...
S - 0.9S = 1 (every later term cancels against its twin)
S x 0.1 = 1
S = 1 / 0.1 = 10
A +1 every move forever, faded at 0.9, is worth exactly 10 right now. In general an
endless +1 stream at fade g is worth 1 / (1 - g). So g is not a mood knob; it is the thing
that turns an endless pile into a number at all. (Textbooks: the discount factor, and the
cancelling trick is the geometric series.)
SOME TASKS END ON THEIR OWN; SOME NEVER DO
Two shapes of task:
EPISODIC : start ──► ──► ──► [done] pile ends when the task ends
CONTINUING : start ──► ──► ──► ──► ... pile grows without stopping
A drone that must touch down: episodic -- landing ends the flight, the pile is finite by
itself, no fade strictly required.
My air-conditioner: continuing. Its situations drift forever -- cooling, off, waiting for
low mains voltage to pass, flashing a warning, once even "a rat has gotten inside it" --
and my moves (switch on, switch off, clean it, throw out the rat) never finish the job,
because there is no finish. Paint how much I like each situation as a reward (+1000 for
cooling, minus plenty for the rat) and the pile grows without end. Only a fade under 1
keeps that pile a number.
And one degenerate shape ties back to a familiar game: a task with ONE spot and ONE move
that ends it. No future at all -- the pile is just that single reward, and a choice's worth
is its average payout. That is exactly a shopkeeper at a counter of faulty machines. Hold
the thought; it returns at the end with algebra.
ONE DIE DECIDES BOTH WHERE YOU LAND AND WHAT YOU GRAB
When you pick an arrow at a spot, the world rolls one die, and that single roll fixes two
things at once: where you land, and what reward you grab. Its chances are written
p( landing, reward | spot, arrow )
^ the two outcomes ^ what you chose
-- read: "given this spot and this arrow, the chance of landing THERE with THAT reward."
One spot, arrow ->, drawn:
┌──────────────────────────────────────────────────┐
│ spot HERE, arrow -> │
│ │
│ chance 1/2 -> land on spot X, reward +2 │
│ chance 1/2 -> land on spot Y, reward +2 │
│ │
│ p( X, +2 | HERE, -> ) = 0.5 │
│ p( Y, +2 | HERE, -> ) = 0.5 │
└──────────────────────────────────────────────────┘
This die is the ONLY place randomness lives in the world's model. Whenever a formula
below says "averaged over the die", it means the shortcut from earlier: each outcome's
value times its chance, added. And when a world happens to be certain -- every arrow lands
in exactly one spot -- that is just a die with one face: one outcome, chance 1.0. Same
formula, easiest case.
YOUR SIDE OF THE RANDOMNESS: A MAP, FIXED OR DICED
A map (textbooks: a policy) is your rule for picking an arrow at each spot. Two kinds:
┌──────────────────────────────────────────────────────────┐
│ FIXED: one arrow per spot, always │
│ spot S -> always left (no dice) │
│ │
│ DICED: a die over your own arrows │
│ spot S -> left 70%, right 30% │
└──────────────────────────────────────────────────────────┘
A fixed map has no randomness in the choice; a diced map rolls for its own arrow. One
fact worth flagging now and proved by a picture further down: chasing the best possible
worth never forces you into dice -- some fixed map always achieves it.
TWO WORTH-MACHINES: V TAKES ONE INPUT, Q TAKES TWO
Two machines hand back a worth. They differ only in what you must feed them:
┌────────────────────────────────────────────────────────────┐
│ │
│ V : spot ────────────────────────► worth │
│ one thing in: where am I? │
│ │
│ Q : spot + arrow ────────────────► worth │
│ two things in: where am I, which move first? │
│ │
└────────────────────────────────────────────────────────────┘
V(spot) = worth of standing here and following the map at every spot from now on.
Q(spot, arrow) = worth of taking THAT arrow first, then following the map afterward.
Not one machine with an optional argument -- two machines. Asked "does a value function
take 1 or 2 inputs?", the clean answer is: there are two of them; V takes 1, Q takes 2.
ONE RECIPE DEFINES BOTH: REWARD NOW, PLUS FADED WORTH NEXT
For a fixed map, a worth obeys one recipe (textbooks: the Bellman equation):
Q( spot, arrow ) = reward grabbed now + 0.9 x worth of where you land,
averaged over the world's die
"Averaged over the die" is the same value-x-chance-added shortcut as always: one term per
die face. Worked, using the die drawn two sections up -- arrow -> lands on spot X (worth
10) or spot Y (worth 0), chance 1/2 each, reward +2 either way, fade 0.9:
Q( HERE, -> )
= chance of X x [ reward + 0.9 x worth(X) ]
+ chance of Y x [ reward + 0.9 x worth(Y) ]
= 0.5 x [ 2 + 0.9 x 10 ]
+ 0.5 x [ 2 + 0.9 x 0 ]
= 0.5 x 11
+ 0.5 x 2
= 5.5 + 1.0
= 6.5
Same setup, one change: landing spot X is now worth 5, not 10 (Y still worth 0, reward
still +2 at chance 1/2 each, fade 0.9). Compute Q(HERE, ->) on your slate.
Check: outcome X: 0.5 x (2 + 0.9 x 5) = 0.5 x 6.5 = 3.25
outcome Y: 0.5 x (2 + 0.9 x 0) = 0.5 x 2.0 = 1.00
Q( HERE, -> ) = 3.25 + 1.00 = 4.25
Note what you did with the two landings: you AVERAGED over them. You never get to max
over the die -- the world rolls it, not you.
WANT THE BEST WORTH, NOT A MAP'S? SWAP THE AVERAGE FOR A MAX
Everything above grades a FIXED map. For the best possible worth, replace "follow the
map" with "take the best arrow" -- a max over your own choices (the one place maxing is
yours to do):
V*( spot ) = max over arrows [ reward now + 0.9 x average V* of the landing ]
V* is the optimal worth: the pile under the best possible behaviour. Worked -- one spot,
two arrows, both landing on a spot worth 5, fade 0.9:
arrow left : reward 1 -> 1 + 0.9 x 5 = 1 + 4.5 = 5.5
arrow right: reward 2 -> 2 + 0.9 x 5 = 2 + 4.5 = 6.5
V*( spot ) = max( 5.5, 6.5 ) = 6.5 <- right is best
One catch, worth stating sharply. That max-equation is a statement about V* itself -- it
names no map. Taking maxes over a WRONG worth table does not make the table right: go
max-picking over an all-zeros table and you just grab the biggest immediate reward,
which has nothing to do with V*. Later posts earn V* by climbing toward it; the equation
only says what the summit looks like once reached.
TWO ARROWS CAN TIE; THE BEST WORTH NEVER SPLITS
Draw a tie:
spot T
/ \
left right
| |
worth 5 worth 5 <- equal
Four facts off this one picture:
one unique best map? NO -- "always left" and "always right" both win
a FIXED best map exists? YES -- "always left" is fixed, and it is best
one unique best worth? YES -- both arrows give 5; T's best worth is 5
ever forced into dice? NO -- a fixed winner exists, so never
Many best maps can share one best worth. Maps may tie; the worth is a single number at
every spot, not a range. (True in every finite world of spots and arrows, not just here.)
ONLY THE MEAN REWARD EVER ENTERS
From the noise-stories earlier: two moves, same average reward, same worth. So the recipe
can name that average once and split cleanly -- write r(s, a) for the mean reward of
taking arrow a at spot s:
worth = r(s, a) + 0.9 x ( each landing's worth x its chance, added )
^ mean reward ^ faded future, averaged over the die
Naming r(s, a) separately earns its keep in worlds where what you earn does not depend on
where you end up -- the split makes that independence visible instead of buried.
THE FADE IS NOT A DETAIL: g PICKS THE WINNER
Set up one decision spot with two arrows:
left : grabs +1 now and +1 every move after, forever
right : grabs +2 once, then nothing
From the endless-pile section: a forever +1 stream at fade g is worth 1/(1-g). Right is
worth 2 at any fade. Now turn the dial:
g = 0.0 : left = 1/(1-0.0) = 1/1.0 = 1.0 right = 2 -> RIGHT wins
g = 0.5 : left = 1/(1-0.5) = 1/0.5 = 2.0 right = 2 -> TIE
g = 0.9 : left = 1/(1-0.9) = 1/0.1 = 10.0 right = 2 -> LEFT wins
Same world, same rewards -- and the best arrow flips with the fade. Short-sighted g takes
the big-now; far-sighted g takes the small-forever. Choosing g is choosing which
behaviour you are paying for, not tuning a rounding error.
V IS Q AVERAGED BY THE MAP -- AND NO SECOND FADE
V at a spot and Q at that spot's arrows connect through the map:
V( spot ) = ( chance the map picks arrow ) x Q( spot, arrow ), added over arrows
Worked. From the recipe section: Q(HERE, ->) = 6.5. Given: Q(HERE, <-) = 5.5. Map flips
a fair coin between them:
V( HERE ) = 0.5 x 6.5 + 0.5 x 5.5
= 3.25 + 2.75
= 6.0
No 0.9 appears in that line -- on purpose. Each Q already carries the fade inside it;
fading again would shrink the future twice and land on the wrong number. And the OPTIMAL
V swaps that map-average for a max over your own arrows:
V*( HERE ) = max( 6.5, 5.5 ) = 6.5
A BANDIT IS THIS WHOLE MACHINE WITH ONE SPOT
Now cash in the held thought. Take a world with one spot and moves that end the task
immediately -- one pull, done. No landing, no future, so an arrow's worth collapses to
just its mean reward:
Q( the one spot, arm ) = average payout of that arm
That is a shopkeeper at a counter of faulty machines: one spot, a row of arms, Q = each
arm's average. His greed-lock (first decent guess captures every patient) was a
best-arrow failure in a one-spot world; his 10%-random fix was a diced map. Smallest
possible case of everything on this page.
So when are two arms EQUALLY best? Let arm LEFT pay +1 (chance p) or +3 (chance 1-p):
average of LEFT = 1 x p + 3 x (1 - p) = p + 3 - 3p = 3 - 2p
Let arm RIGHT pay 0 (chance q) or +10 (chance 1-q):
average of RIGHT = 0 x q + 10 x (1 - q) = 10 - 10q
Set the two averages equal and solve:
3 - 2p = 10 - 10q
3 - 2p + 10q = 10 <- add 10q to both sides
10q = 10 - 3 + 2p <- move 3 and 2p across
10q = 7 + 2p
Verify with p = 0.5: q = (7 + 2 x 0.5) / 10 = 8.0 / 10 = 0.8
average of LEFT = 3 - 2 x 0.5 = 3 - 1.0 = 2.0
average of RIGHT = 10 - 10 x 0.8 = 10 - 8.0 = 2.0 same. tied arms.
Every piece is now on the table: piles, averages, the fade, the die, maps, V and Q, one
recipe with an average, one summit with a max. Grading a whole map's worths by hand is
the next post's job; improving the map after that; and then doing both with the max and
no map at all.
Pencil work done. Below, the same numbers in Python -- hard-coded, no loops, every
intermediate value shown as the actual number.
# =================================================================
# a return is a pile
# =================================================================
r_move1 = 2
r_move2 = 1
r_move3 = 3
pile = r_move1 + r_move2 + r_move3 # 2 + 1 + 3 = 6
print("return:", pile) # 6
# =================================================================
# average of an unsure reward: value x chance, added
# move pays +1 (chance 0.5) or +3 (chance 0.5)
# =================================================================
avg_reward = 1 * 0.5 + 3 * 0.5 # 0.5 + 1.5 = 2.0
print("average reward:", avg_reward) # 2.0
# =================================================================
# fade: +10 by distance; endless +1 stays finite
# =================================================================
worth_now = 10 * (0.9 ** 0) # 10 x 1.000 = 10.0
worth_1_off = 10 * (0.9 ** 1) # 10 x 0.900 = 9.0
worth_2_off = 10 * (0.9 ** 2) # 10 x 0.810 = 8.1
worth_3_off = 10 * (0.9 ** 3) # 10 x 0.729 = 7.29
print(worth_now, worth_1_off, worth_2_off, worth_3_off)
endless_plus_one = 1 / (1 - 0.9) # 1 / 0.1 = 10.0
print("endless +1 at fade 0.9:", endless_plus_one) # 10.0
# =================================================================
# Q from the recipe: two die faces, averaged
# face X (chance 0.5): land on worth-10 spot, reward +2
# face Y (chance 0.5): land on worth-0 spot, reward +2
# =================================================================
term_X = 0.5 * (2 + 0.9 * 10) # 0.5 x (2 + 9.0) = 0.5 x 11 = 5.5
term_Y = 0.5 * (2 + 0.9 * 0) # 0.5 x (2 + 0.0) = 0.5 x 2 = 1.0
Q_here_right = term_X + term_Y # 5.5 + 1.0 = 6.5
print("Q(HERE, ->):", Q_here_right) # 6.5
# =================================================================
# V from Q: averaged by the map -- and no second fade
# =================================================================
Q_right = 6.5 # from above
Q_left = 5.5 # given
V_here = 0.5 * Q_right + 0.5 * Q_left # 3.25 + 2.75 = 6.0
print("V(HERE):", V_here) # 6.0
V_star_here = max(Q_right, Q_left) # max(6.5, 5.5) = 6.5
print("V*(HERE):", V_star_here) # 6.5 <- optimal: take right
# =================================================================
# best-arrow version: one spot, two arrows, both land on a worth-5 spot
# =================================================================
Q_left_opt = 1 + 0.9 * 5 # 1 + 4.5 = 5.5
Q_right_opt = 2 + 0.9 * 5 # 2 + 4.5 = 6.5
V_star = max(Q_left_opt, Q_right_opt) # 6.5
print("V*(spot):", V_star) # 6.5
# =================================================================
# the fade flips the winner
# left = +1 forever = 1/(1-g) right = +2 once = 2 at any g
# =================================================================
left_at_00 = 1 / (1 - 0.0) # 1 / 1.0 = 1.0 -> right wins
left_at_05 = 1 / (1 - 0.5) # 1 / 0.5 = 2.0 -> tie
left_at_09 = 1 / (1 - 0.9) # 1 / 0.1 = 10.0 -> left wins
print(left_at_00, left_at_05, left_at_09)
# =================================================================
# equal arms: LEFT pays 1 (chance p) or 3; RIGHT pays 0 (chance q) or 10
# tie condition derived above: 10q = 7 + 2p. verify at p = 0.5:
# =================================================================
p = 0.5
q = (7 + 2 * p) / 10 # (7 + 1.0) / 10 = 0.8
avg_left = 3 - 2 * p # 3 - 1.0 = 2.0
avg_right = 10 - 10 * q # 10 - 8.0 = 2.0
print("p =", p, " q =", q, " left =", avg_left, " right =", avg_right) # tied
----------------------------------------------------------------------------------------------
<- prev: Chapter 12, Part 1: Bandits and Exploration
-> next: Chapter 12, Part 3: Grading a Plan by Pencil
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================