==============================================================================================
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
Grading a Plan by Pencil: A Table of Lies That Heals Into the Truth
============================================================================================
Every reinforcement-learning writeup hands you the Bellman equation -- V(s) = R(s) +
g x V(next) -- names it after a dead mathematician, and says "now just iterate until it
converges." Two things almost all of them skip. First: WHY starting every value at 0 -- a
flat lie -- ever crawls to the right answer. Begin wrong, end right, no reason given: that
smells like astrology. Second: WHY the 0.9 in there is not a "care less about tomorrow"
mood knob but, for a flight that might never land, the only thing keeping the point-total
finite at all. Both get shown below, digit by digit, and the formula arrives only after
you have already used it.
Here is the obstacle in two lines. Two spots lean on each other:
worth(A) = reward + worth(B)
worth(B) = reward + worth(A)
^__________| each needs the other already solved
No first spot exists to compute -- the definitions chase each other in a circle, so no
bare number can be written for either spot up front.
So lie. Write 0 in every spot, then lay the rule over the whole table anyway, reading each
spot's neighbour as-is -- lie or not -- and rewriting the spot. First pass is mostly lies
feeding on lies, but every spot also touches a real painted reward, and that scrap of
truth seeps one spot further each pass (sketch numbers here, only to show the shape --
every real digit is worked below):
start: A = 0 B = 0
pass 1: A = 2.0 B = 1.0 (the rewards bite first)
pass 2: A = 2.9 B = 2.4
pass 3: A = 3.3 B = 2.9
... settling toward what the circular
stop: A = 3.6 B = 3.2 equations would give, if solvable directly
A table of lies, healing one sweep at a time, frozen when nothing moves. That single move
turns a circular formula into plain arithmetic. Now the real thing, every digit shown.
A DRONE, A RUNWAY, AND POINTS PAINTED ON THE GROUND
A drone hangs in the air over a patch of enemy ground, and someone hands you a flight
PLAN to grade.
a SPOT = a place the drone can be: a position with a height.
GROUND = the lowest spots. Touching the ground ENDS the flight.
RUNWAY = one special ground spot. Touch it -> +5 points. (the prize)
DIRT = any other ground spot. Touch it -> -2 points. (a crash)
AIR = any spot above the ground. No stopping here; the drone must move on.
FUEL = one move in the air costs -0.1 points. (the meter always runs)
an ARROW = the PLAN: at every air spot, "from here, go THIS way."
the SHRINK = a worth one move in the future counts as 0.9 of itself.
Painted facts, all of them: +5, -2, -0.1, 0.9. Handed over, fixed, never argued with.
(Textbook names, pinned once: a spot is a state; the plan a policy; a spot's worth its
value V(s); painted points rewards; the shrink the discount factor gamma; touching ground
a terminal state.)
Drawn, 3 wide x 3 tall, with every plan-arrow pointing DOWN:
height 2 [ air ] [ air ] [ air ] <- drone starts up here, pays fuel each move
| | |
v v v (arrows = the fixed plan under grading)
height 1 [ air ] [ air ] [ air ]
| | |
v v v
height 0 [DIRT ] [RUNWY] [DIRT ] <- ground: touching ends the flight
-2 +5 -2
And one single stack -- the column directly above the runway -- as the worked example:
height 2: T (top air spot) arrow points down to M
|
v
height 1: M (middle air spot) arrow points down to G
|
v
height 0: G (ground = runway) painted +5, no lookup
WORTH MEANS DISCOUNTED -- SO 4.8 RAW POINTS GRADE AS 3.86
You are asked one thing per spot, and it is NOT "how many raw points does the drone bag
from here." Worth = the DISCOUNTED sum: a reward collected k moves from now counts as
0.9^k of itself. One +5, seen from different distances:
distance shrink factor discounted value
0 0.9^0 = 1.00 1.00 x 5 = 5.00 (standing on the runway)
1 0.9^1 = 0.90 0.90 x 5 = 4.50 (one move away)
2 0.9^2 = 0.81 0.81 x 5 = 4.05 (two moves away = spot T)
3 0.9^3 = 0.729 0.729 x 5 = 3.645 (three moves away)
Work spot T in the runway stack -- two moves of fuel, then the prize:
worth(T) = -0.1 (fuel now, shrunk 0.9^0 = not at all)
+ 0.9 x (-0.1) (fuel at M, one move off, shrunk once)
+ 0.9^2 x (+5) (runway at G, two moves off, shrunk twice)
= -0.1 - 0.09 + 4.05
= 3.86
Raw points bagged from T: -0.1 - 0.1 + 5 = 4.8. Graded worth: 3.86. That gap
(4.8 - 3.86 = 0.94) is no loss in the world -- it is the discount eating future rewards
in the measuring stick we chose, and that stick is what makes the circular equation below
consistent. Fill every spot's worth and the plan is graded: good plans score high tables,
bad plans score low ones. Nothing here re-aims an arrow. Scoring only.
ONE LAW, DERIVED FROM WHERE A SPOT SITS
A ground spot first. Touching ground ends the flight -- nothing comes after, no future to
count, so its worth is just the points painted on it:
worth(ground) = its painted points (+5 runway, -2 dirt)
No lookup, no neighbour, no arithmetic. Burn this in: a ground spot's worth is TRUE the
instant it is written, and can never be wrong.
An air spot next. No stopping there: it pays fuel now, then rides its arrow onward, and
whatever the landing spot is worth counts 0.9 of itself from here:
worth(air) = -0.1 + 0.9 x worth(next)
Two lines. That is the entire law. ("next" = the one spot this plan's arrow points to.
One honest note, so nothing is smuggled: in a chancier world an arrow can land on SEVERAL
spots by chance, and the future term becomes each landing's worth x its chance, added.
This plan's arrows land on exactly one spot -- chance 1.0 -- so that sum collapses to the
single term above. Everything below survives putting the sum back.)
A CIRCLE WITH NO FIRST SPOT
Look hard at the air line:
worth(air) = -0.1 + 0.9 x worth(next)
Computing this spot needs worth(next). If "next" is also an air spot, ITS worth needs the
worth of ITS next, and on it goes -- a worth leaning on a worth leaning on a worth. No air
spot can be written down first. Your gut is right to balk: with a pencil, running down a
column, there is no one-shot formula.
(One honest aside for the sharp reader: this circle is a set of linear equations, and
linear equations CAN be solved in one shot by matrix inversion. Real method, not pencil
work, and it scales badly -- a million spots means a million-by-million matrix. What
follows is what you actually do by hand and what scales, which is why it is what everyone
builds.)
BREAK THE CIRCLE: START FROM A LIE AND WALK
One new word, defined by a picture:
a WALK = run a finger over the list of spots ONCE, in some fixed order, rewriting
each spot from the law -- using whatever number the table holds RIGHT NOW
for its neighbour, even if that number is still a lie.
(Like a shopping list: one finger-trip over it = one walk; over it again = a second walk.)
Walk order is a free choice -- top-to-bottom, bottom-to-top, any fixed sweep, same final
answer, different walk-count. Below, the trace runs TOP-TO-BOTTOM on purpose: that order
forces the worst case (reading stale neighbours) so the healing is slow enough to watch.
One more choice hides in "whatever the table holds right now": a neighbour rewritten
EARLIER THIS SAME WALK is read fresh, not from last walk's frozen copy. Reading in place
like this is called Gauss-Seidel (frozen-copy reading is Jacobi; both settle to the same
answer) -- and reading in place is exactly why, with a good walk direction, truth can jump
a whole spot per walk instead of crawling.
Full recipe:
write 0 in every spot <- the deliberate lie, just to have a table
do a walk. do another. do another.
stop when a walk moves nothing.
No line checks "is the neighbour ready." No junk detector. One measurement exists in the
whole engine -- "did this walk move anything" -- and it only decides when to stop.
WHY A LIE SITTING NEXT TO ONE TRUTH MUST HEAL
Two facts do it. Neither is magic; both are arithmetic.
First: the law's "+" lays a SOLID layer every pass. Its reward part (the -0.1 fuel) is
painted -- no lookup -- so it goes down no matter how junky the neighbour term is. Even
reading a stale 0:
worth = -0.1 + 0.9 x 0 = -0.1 <- not 0. a solid -0.1 got laid down.
Junk cannot multiply into junk forever, because addition keeps stacking painted truth on
top of it. That "+" is the floor under the "x".
Second: ground spots are ANCHORS. Painted, lookup-free, correct from walk one, never
junk. Every air spot is chained (through its arrow) to some anchor, and the walks drag it
there.
Watch it, digit by digit. Runway stack: T (top, air) -> M (middle, air) -> G (ground,
runway, +5). Finger runs top to bottom: T first, then M, then G -- so T and M are written
BEFORE the spot each leans on. Everything starts at 0.
WALK 1 (table: T=0, M=0, G=0)
T: reads M = 0 (stale!) worth = -0.1 + 0.9 x 0 = -0.1
M: reads G = 0 (stale!) worth = -0.1 + 0.9 x 0 = -0.1
G: ground worth = +5 <- anchor lands. true forever.
table now: T = -0.1 M = -0.1 G = +5
WALK 2 (table: T=-0.1, M=-0.1, G=+5)
T: reads M = -0.1 worth = -0.1 + 0.9 x (-0.1) = -0.19
M: reads G = +5 (true!) worth = -0.1 + 0.9 x 5 = 4.4 <- M is now TRUE
G: +5
table now: T = -0.19 M = 4.4 G = +5
WALK 3 (table: T=-0.19, M=4.4, G=+5)
T: reads M = 4.4 (true!) worth = -0.1 + 0.9 x 4.4 = 3.86 <- T is now TRUE
M: reads G = +5 worth = 4.4 (no change)
G: +5
table now: T = 3.86 M = 4.4 G = +5
WALK 4 nothing moves. 3.86, 4.4, +5 stay put. STOP.
Follow just the top spot:
T: 0 -> -0.1 -> -0.19 -> 3.86 -> 3.86
start walk1 walk2 walk3 walk4 (frozen)
Junk read off a stale 0 -- healed. And the mechanism is bare:
G, the anchor, is correct from walk 1.
M leans on G -> M turns true one walk later (walk 2).
T leans on M -> T turns true one walk after that (walk 3).
Truth climbs ONE spot per walk, outward from the anchor -- a gift of reading in place
while walking toward the lean, not a law of the algorithm (walk the other way and the
same truth climbs slower; the final table is identical). As tall as a stack is, that many
walks, then frozen.
> No lie-and-hope here. A lie sits next to ONE painted truth, and plain arithmetic drags
> every spot to that truth, one spot closer per pass.
NO GROUND AT ALL: A FOREVER-BOUNCE
"Fine," you say, "it heals because a +5 anchor exists to climb to. What if the drone
never lands?" Good -- stage the case that looks impossible.
spot A <────+
| |
| arrow | arrow
v |
spot B ─────+
Two air spots, arrows pointing at each OTHER. Bounce A, B, A, B... forever; no ground,
no anchor. Both start at 0, and each walk reads in place (B sees the A just written):
WALK 1 A = -0.1 + 0.9 x (0) = -0.1
B = -0.1 + 0.9 x (-0.1) = -0.19
WALK 2 A = -0.1 + 0.9 x (-0.19) = -0.271
B = -0.1 + 0.9 x (-0.271) = -0.3439
WALK 3 A = -0.1 + 0.9 x (-0.3439) = -0.40951
... -0.1 -> -0.271 -> -0.41 -> -0.52 -> ... -> -1
It crawls to -1 and holds. No ground was ever touched, yet a real number came out. How
does an endless bounce cost a finite amount?
BECAUSE 0.9 FORCES THE SUM FINITE -- CRACKED FROM SCRATCH
Bouncing forever pays -0.1 a move, with one more shrink stacked per move:
total = -0.1 + 0.9 x (-0.1) + 0.9^2 x (-0.1) + 0.9^3 x (-0.1) + ...
= -0.1 x ( 1 + 0.9 + 0.9^2 + 0.9^3 + ... )
Call the bracket S and build its value from nothing -- no recalled formula:
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 (each later term cancels against its twin)
S x 0.1 = 1
S = 1 / 0.1 = 10
So total = -0.1 x 10 = -1. Endless moves, finite total -- far terms shrink to nothing.
Cross-check straight off the circle itself: by symmetry A = B = x, and the law says
x = -0.1 + 0.9x, so 0.1x = -0.1, so x = -1. Two roads, same -1.
Now the punchline, fenced honestly. This drone world is episodic -- every flight lands
eventually -- so even with shrink 1.0 its sums stay finite (T would grade 4.8, M 4.9,
G 5). But drop the shrink in the BOUNCE -- a task that never ends -- and the bracket
becomes 1 + 1 + 1 + ... = no limit; worth = negative infinity; the walks never settle.
For any task that might run forever, 0.9 < 1 is not a mood. It is the floor that forbids
the sum from blowing up. And almost every real control problem runs forever -- the robot
does not stop, the server does not close -- which is why the shrink sits in the standard
setup as load-bearing equipment, not taste.
WHEN TO STOP: DELTA UNDER THETA
Two more words, defined:
delta = the biggest move any spot made this walk: largest |new - old|.
theta = a tiny line in the sand, e.g. 0.00000001 -- "near enough."
stop rule: delta < theta -> no spot moved more than a hair -> stop.
Say precisely what that does and does not promise. It does NOT certify the table obeys
the law perfectly -- every spot could sit a hair off and still pass. It says the LAST walk
barely nudged anything, and here is why that bounds the error: each walk multiplies
whatever error remains by at most 0.9 -- the same shrink -- so error can only shrink, walk
after walk, never grow. (A good walk direction kills it faster still; the full grid below
settles in one filling walk.) Pick theta small enough and "barely moved" and "basically
correct" become the same thing for any use you have. That geometric squeeze is the whole
reason the walks land at all; textbooks call the property a contraction mapping, and the
0.9 is all of it.
(A cap on walk-count is just a seatbelt against bugs. Delta under theta is the real
stop.)
ONE MEASUREMENT, AND THE SETTLING IS EMERGENT
This is the part that feels too small to work. No code spots junk. No code waits for a
neighbour to be ready. No code certifies a spot correct. One measurement exists -- delta,
the biggest move this walk -- and it only decides when to STOP. Healing, the finite
bounce, truth climbing spot by spot: all of it is a CONSEQUENCE of repeating "+ then
x 0.9", coded nowhere. Simple-looking code deserving a strong result -- correct: the work
lives in the repetition and in the 0.9, not in any clever check.
NINE STACKS, FILLED BY HAND
Now the whole 3 x 3 x 3 world -- spots are (x, y, height), each coordinate in {0, 1, 2},
27 spots total. Runway = the middle ground spot (1,1,0) -> +5; all eight other ground
spots are dirt -> -2; the plan is still "always nudge DOWN", so an air spot (x, y, h)
leans on (x, y, h-1), the spot below it.
Here is the shape that makes 27 spots cheap: this plan never moves sideways, so the world
splits into 9 independent vertical stacks -- one per (x, y) column -- and only two kinds
of stack exist:
the stack over the RUNWAY (1,1,*):
(1,1,0) ground, runway -> +5
(1,1,1) -0.1 + 0.9 x (+5) = 4.4
(1,1,2) -0.1 + 0.9 x (4.4) = 3.86
any stack over DIRT (eight of them):
(x,y,0) ground, dirt -> -2
(x,y,1) -0.1 + 0.9 x (-2) = -1.9
(x,y,2) -0.1 + 0.9 x (-1.9) = -1.81
(Walked bottom-to-top, each spot reads a neighbour already true this same walk -- so one
filling walk settles a stack, plus one walk to notice nothing moved. Walked top-to-bottom
it would take one walk per height, like the slow trace above. Same table either way.)
Finished table, read at a glance:
runway stack (1,1,*): +5 , 4.4 , 3.86 <- hanging over the runway pays
every other stack: -2 , -1.9 , -1.81 <- this plan dives into bare dirt
And there is the grade. "Always Down" is brilliant in exactly ONE column -- over the
runway -- and a disaster in the other eight, where Down means crashing into dirt. That
worth table is the scorecard a NEXT job would read to re-aim arrows (head for the runway
column first, THEN drop). Re-aiming is the next post's job. Grading the handed plan is
done.
Pencil work done. Below, the same numbers in Python -- hard-coded spot by spot, no loops,
so every digit can be checked against the walks above.
# -----------------------------------------------------------------
# painted facts (handed over, fixed)
# runway -> +5 dirt -> -2 fuel in the air -> -0.1
# shrink -> 0.9
# -----------------------------------------------------------------
RUNWAY = 5.0
DIRT = -2.0
FUEL = -0.1
SHRINK = 0.9
# =================================================================
# case 1: the runway stack heals -- top-down, stale reads forced.
# spots: T (top air) -> M (middle air) -> G (ground, runway).
# finger order T, M, G: both air spots written before what they
# lean on, so walk 1 reads junk -- and it still heals by walk 3.
# =================================================================
print("=== case 1: the lie heals ===")
T, M, G = 0.0, 0.0, 0.0 # the deliberate lie
# walk 1 -- T and M read stale 0s; the anchor lands last.
T = FUEL + SHRINK * M # -0.1 + 0.9 x 0 = -0.1 (M was stale 0)
M = FUEL + SHRINK * G # -0.1 + 0.9 x 0 = -0.1 (G was stale 0!)
G = RUNWAY # +5 <- anchor. true forever from here.
print("walk 1:", T, M, G) # -0.1 -0.1 5.0
# walk 2 -- M reads the true anchor and snaps true; T still trails.
T = FUEL + SHRINK * M # -0.1 + 0.9 x (-0.1) = -0.19
M = FUEL + SHRINK * G # -0.1 + 0.9 x 5 = 4.4 <- M true
G = RUNWAY
print("walk 2:", T, M, G) # -0.19 4.4 5.0
# walk 3 -- T reads the true M and snaps true.
T = FUEL + SHRINK * M # -0.1 + 0.9 x 4.4 = 3.86 <- T true
M = FUEL + SHRINK * G # 4.4 (no change)
G = RUNWAY
print("walk 3:", T, M, G) # 3.86 4.4 5.0
# walk 4 -- nothing moves: settled. anchor climbed one spot per walk.
print("walk 4: no move -> stop")
# =================================================================
# case 2: forever-bounce, no ground at all. A and B point at each
# other; the drone never lands. it still settles -- to -1.
# =================================================================
print("=== case 2: bounce ===")
A, B = 0.0, 0.0 # both start at the lie
A = FUEL + SHRINK * B # -0.1 + 0.9 x 0 = -0.1
B = FUEL + SHRINK * A # -0.1 + 0.9 x (-0.1) = -0.19 (reads the NEW A)
print("walk 1:", A, B) # -0.1 -0.19
A = FUEL + SHRINK * B # -0.1 + 0.9 x (-0.19) = -0.271
B = FUEL + SHRINK * A # -0.1 + 0.9 x (-0.271) = -0.3439
print("walk 2:", A, B) # -0.271 -0.3439
A = FUEL + SHRINK * B # -0.1 + 0.9 x (-0.3439) = -0.40951
print("walk 3:", A) # -0.40951 ... crawling toward -1
closed_form = FUEL / (1 - SHRINK) # -0.1 / 0.1 = -1.0
print("closed form:", closed_form) # -1.0 <- where the bounce lands
# drop the shrink (use 1.0): 1 + 1 + 1 + ... has no limit -> never settles.
# 0.9 is the floor that makes an answer EXIST, not a "care less" knob.
# =================================================================
# case 3: all 27 spots, no loop needed -- the plan never moves
# sideways, so the grid is 9 independent stacks and only two kinds
# of stack exist. one filling walk each, bottom to top.
# =================================================================
print("=== case 3: the full grid, as two stacks ===")
# runway stack (1,1,*) -- bottom-to-top: each line reads a value
# already true this same walk.
g_run = RUNWAY # (1,1,0) +5 painted
m_run = FUEL + SHRINK * g_run # (1,1,1) -0.1 + 0.9 x 5 = 4.4
t_run = FUEL + SHRINK * m_run # (1,1,2) -0.1 + 0.9 x 4.4 = 3.86
print("runway stack:", g_run, m_run, t_run) # 5.0 4.4 3.86
# dirt stack -- the other EIGHT columns are all this one, repeated.
g_dirt = DIRT # (x,y,0) -2 painted
m_dirt = FUEL + SHRINK * g_dirt # (x,y,1) -0.1 + 0.9 x (-2) = -1.9
t_dirt = FUEL + SHRINK * m_dirt # (x,y,2) -0.1 + 0.9 x (-1.9) = -1.81
print("dirt stack :", g_dirt, m_dirt, t_dirt) # -2.0 -1.9 -1.81
# full table: one column reading 5.0/4.4/3.86, eight reading -2/-1.9/-1.81.
# the grade of "always Down": brilliant over the runway, a crash everywhere else.
----------------------------------------------------------------------------------------------
<- prev: Chapter 12, Part 2: Worth and Bellman from Zero
-> next: Chapter 12, Part 4: Finding the Best Plan
----------------------------------------------------------------------------------------------
home . archive . source on GitHub
==============================================================================================