==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 14 . FUNCTION APPROXIMATION . PART 4 OF 4
Two Stages and a Bend: A Q-Network by Pencil
============================================================================================
A worth = a number saying how much
reward is still coming from a choice onward. A weight (a dial) = one learned number.
Every worth in this chapter so far has been a SUM of weights YOU chose where to put
-- one per group of spots, one per hand-laid tile, one per tile-and-move. That is a
straight ruler, and a straight ruler draws only straight walls.
Hand-laid tiles work on a car with two dials of state. But the standard next toy is
a lander -- a little rocket easing onto a pad -- and its state is EIGHT dials at
once: across, up, sideways speed, falling speed, tilt, spin, and a left/right
foot-touch flag. Now the hand-laid tile is trapped both ways. Tile all eight dials
JOINTLY (so one tile can mean "falling fast AND tilted AND low") and the count
explodes -- a dozen bins per dial is 12^8, billions of tiles, one weight each. Tile
each dial on its OWN to dodge the blow-up and the worth can only add per-dial
votes, blind to any such joint condition. Lay them joined and they explode; lay
them apart and they cannot join up. We want a worth that LEARNS its own handful of
features -- few, joint, reshapable -- instead of you laying a fixed grid at all.
That is the whole reason for this post.
(To keep every number on the page, the lander's 8 -> 256 -> 4 shrinks here to a
pencil toy: 2 dials in, 3 middle numbers, 4 engine-worths out. The arithmetic is
identical, just shorter.)
SO STACK TWO STRAIGHT STAGES AND LET THE MIDDLE INVENT FEATURES
Run the state through one straight stage to make a row of MIDDLE numbers, then a
second straight stage to turn those into the four worths. Each stage is a sheet of
dials times the row, plus a nudge row:
state s sheet A middle psi sheet C worths Q
[s1 s2] ---> (2 x 3) ---> [p1 p2 p3] ---> (3 x 4) ---> [Q0 Q1 Q2 Q3]
1 x 2 + b1 (1x3) 1 x 3 + b2 (1x4) 1 x 4
psi = s A + b1 (each middle number = the state dotted with one column of A)
Q = psi C + b2 (each worth = the middle row dotted with one column of C)
The middle row is the network's OWN features -- not handed a single tile from
outside. And it is not fixed: during learning the network changes the sheet A until
those three middle numbers turn into useful combinations of the two input dials,
then grades the engines off those. The features are LEARNED, not chosen by us --
that is the whole point of the middle stage.
BUT A STACK OF STRAIGHT STAGES IS STILL ONE STRAIGHT STAGE -- SO BEND THE MIDDLE
Push the two stages together and watch them collapse. Q = (sA + b1)C + b2 =
s(AC) + (b1 C + b2). The product AC is just one sheet -- multiply our toy's A by C
and a single 2 x 4 falls out:
A (2x3) C (3x4) D = A C (2 x 4)
[ 1 -2 0.5 ] [ 2 -1 0 1 ]
[ 0.5 1 -1 ] x [ 1 1 -1 0 ] = [ -0.5 -2 2.5 0.5 ]
[ -1 2 1 -1 ] [ 3 -1.5 -2 1.5 ]
So Q = sD + e -- a SINGLE straight stage, 2 -> 4, the middle three numbers
vanished. Two straight stages bought nothing; a hundred would buy nothing. Stacking
is wasted unless something between them is NOT straight.
The cheapest bend there is: after the first stage, flatten every negative middle
number to zero and leave the rest alone (the textbook's ReLU):
x = max(psi, 0) -- each middle number kept if positive, knocked to 0 if negative
Now Q = max(sA + b1, 0) C + b2, and there is NO single sheet D that reproduces it --
the flattening cannot be folded into a multiply. The bend is what makes two stages
worth more than one, and what lets the worth turn corners instead of drawing one
flat wall.
FORWARD PASS, EVERY NUMBER
Take the state s = [1, 2]. Sheet A, nudge b1:
A = [ 1 -2 0.5 ] b1 = [ 0.5 -0.5 1.0 ]
[ 0.5 1 -1 ]
First stage, each middle number is the state dotted with a column of A, plus b1:
p1 = (1)(1) + (2)(0.5) + 0.5 = 1 + 1 + 0.5 = 2.5
p2 = (1)(-2) + (2)(1) - 0.5 = -2 + 2 - 0.5 = -0.5
p3 = (1)(0.5) + (2)(-1) + 1.0 = 0.5 - 2 + 1 = -0.5
psi = [ 2.5, -0.5, -0.5 ]
The bend -- flatten the two negatives to zero:
x = max(psi, 0) = [ 2.5, 0, 0 ]
Notice what the bend just did: two of the three middle numbers went DEAD. They will
pass nothing on. Sheet C, nudge b2:
C = [ 2 -1 0 1 ] b2 = [ 0.5 1.0 0.0 -0.5 ]
[ 1 1 -1 0 ]
[ -1 2 1 -1 ]
Second stage, each worth is x dotted with a column of C, plus b2. Because
x = [2.5, 0, 0], only C's FIRST row survives -- the two dead middle numbers erase
their rows:
Q0 = (2.5)(2) + 0 + 0 + 0.5 = 5.0 + 0.5 = 5.5
Q1 = (2.5)(-1) + 0 + 0 + 1.0 = -2.5 + 1.0 = -1.5
Q2 = (2.5)(0) + 0 + 0 + 0.0 = 0.0 + 0.0 = 0.0
Q3 = (2.5)(1) + 0 + 0 - 0.5 = 2.5 - 0.5 = 2.0
Q = [ 5.5, -1.5, 0.0, 2.0 ]
The same net, a different state. Run s = [2, 0] through the same
sheets (A, b1, C, b2 exactly as drawn above): the three middles, the bend, the four
worths. Which engine wins?
CHECK: p1 = (2)(1) + (0)(0.5) + 0.5 = 2.5
p2 = (2)(-2) + (0)(1) - 0.5 = -4.5
p3 = (2)(0.5) + (0)(-1) + 1.0 = 2.0
psi = [2.5, -4.5, 2.0] -> x = [2.5, 0, 2.0] (only p2 died this time)
Q0 = (2.5)(2) + 0 + (2.0)(-1) + 0.5 = 5 - 2 + 0.5 = 3.5
Q1 = (2.5)(-1) + 0 + (2.0)(2) + 1.0 = -2.5 + 4 + 1 = 2.5
Q2 = (2.5)(0) + 0 + (2.0)(1) + 0.0 = 2.0 = 2.0
Q3 = (2.5)(1) + 0 + (2.0)(-1) - 0.5 = 2.5 - 2 - 0.5 = 0.0
Q = [3.5, 2.5, 2.0, 0.0] -> engine 0 wins. Note x has TWO live slots
here, so TWO rows of C spoke -- which middles die changes per state.
WHICH GIVES FOUR ENGINE-WORTHS, COMPUTED NOT LOOKED UP
Q is four numbers -- one worth per engine (0 fire-left, 1 fire-main, 2 fire-right,
3 coast) -- the same shape the car's three pushes had, but now CONJURED from 25
dials (A holds 6, b1 holds 3, C holds 12, b2 holds 4) instead of stored in a table.
Choosing is unchanged: fire the greedy best (here engine 0, worth 5.5), and wander
epsilon of the time so no engine goes stale. There is no table of states anywhere
-- the same 25 dials GENERATE the four worths of EVERY state, including states
never seen (the real lander's 8 -> 256 -> 4 needs 8x256 + 256 + 256x4 + 4 = 3,332
dials).
WHICH LEAVES A DEBT FROM THE BEND SECTION -- PROVE NO SINGLE SHEET MATCHES THE BENT NET
The bend section claimed that once the flattening sits in the middle, NO single
straight stage -- no sheet D with a nudge row e, Q = sD + e -- reproduces the
machine. That was asserted, not shown. Pay the debt with the machine's own
numbers. A single straight stage has a fingerprint it cannot fake: equal steps
in the state buy equal steps in every worth, always -- each +1 on s1 adds
exactly D's first-row entry, every time, no exceptions. So walk s1 by equal
steps through the bent machine and watch Q0. Same sheets as above (A, b1, C,
b2 untouched), s2 pinned at 2:
s = [1, 2]: psi = [2.5, -0.5, -0.5] -> x = [2.5, 0, 0 ] -> Q0 = (2.5)(2) + 0.5 = 5.5
s = [2, 2]: psi = [3.5, -2.5, 0.0] -> x = [3.5, 0, 0 ] -> Q0 = (3.5)(2) + 0.5 = 7.5
s = [3, 2]: psi = [4.5, -4.5, 0.5] -> x = [4.5, 0, 0.5] -> Q0 = (4.5)(2) + (0.5)(-1) + 0.5 = 9.0
Equal state-steps: +1, +1. Worth-steps: 7.5 - 5.5 = +2.0, then 9.0 - 7.5 = +1.5.
UNEQUAL. Between the second and third walk the third middle crossed zero
(psi3: -0.5 -> 0.0 -> +0.5) -- its gate swung open, and row 3 of sheet C woke
up. Each +1 step of s1 raises psi3 by 0.5, and each unit of the now-live x3
pays (-1) into Q0, so the open gate drains (0.5)(-1) = -0.5 per step: the old
slope of +2.0 became 2.0 - 0.5 = +1.5, mid-walk. A straight stage cannot
change slope mid-walk. The bent machine just did. Debt paid.
Now name what the machine has become. On one side of the wall where psi3 = 0,
the machine IS one straight rule (the dead middles erase their rows of C); step
across the wall and a DIFFERENT straight rule takes over (row 3 joins the sum).
One straight rule per region, a wall wherever some middle crosses zero -- and
the machine places those walls itself, by moving sheet A as it learns. The
textbook word for this shape is PIECEWISE-linear: straight pieces stitched at
corners. The bend never buys curviness. It buys the right to switch rules at
walls.
AND STITCHED STRAIGHT PIECES REACH FURTHER THAN ONE RULE EVER COULD
Build the smallest interesting worth-curve by hand: ONE state dial s, two gated
middles, one worth.
middle 1 = max(0, s) -- its wall sits at s = 0
middle 2 = max(0, s - 1) -- its wall sits at s = 1
worth = middle1 - 2 x middle2
s = -1 : 0 - 2(0) = 0 flat
s = 0 : 0 - 2(0) = 0 flat ends here
s = 0.5: 0.5 - 2(0) = 0.5 rising, slope +1
s = 1 : 1 - 2(0) = 1 the peak
s = 1.5: 1.5 - 2(0.5) = 0.5 falling, slope -1
s = 2 : 2 - 2(1) = 0 still falling
s = 3 : 3 - 2(2) = -1 slope -1 continues
Flat, then up at slope +1, then down at slope -1: a roof. No single straight
rule can be a roof -- one rule owns exactly one slope, a roof needs three. Each
gated middle donated one wall (one at s = 0, one at s = 1), and two walls
bought three regions with three different slopes. More middles, more walls,
more regions -- enough short straight pieces shadow any worth-curve as closely
as the lander needs. That is what "the network learns its own features" cashes
out to in the end: sheet A decides where the walls stand, sheet C decides each
region's slopes.
SO WHAT DO WE GRADE Q AGAINST? THE SAME ONE-SAMPLE TARGET, AVERAGED
The net guessed Q(s, engine 0) = 5.5. Was that right? Grade it the one-sample way:
take a real move, see the reward and where you land, and build a target out of what
actually happened plus the net's own read of the next spot. The lander's habit is a
spread of chances over engines (it wanders), so instead of betting on ONE next
move, average the next worths by how likely each move is -- the Expected Sarsa
target:
y = reward + dilute x SUM over next engines a' of chance(a') x Q(next state, a')
Here dilute is the future-shrinker (0.9 here). Worked. We fired engine 0, got
reward 1, and landed at s'. Run the net forward on s' the same way (its own sheets,
its own bend) and read off its four worths; say they come out
Q(s') = [ 3, 5, 1, 2 ] and the habit's chances are [ 0.1, 0.6, 0.1, 0.2 ]
The averaged next-worth, then the target:
averaged next = (0.1)(3) + (0.6)(5) + (0.1)(1) + (0.2)(2)
= 0.3 + 3.0 + 0.1 + 0.4
= 3.8
y = reward + dilute x averaged next
= 1 + 0.9 x 3.8
= 1 + 3.42
= 4.42
(Swap that average for the single best next worth and it is Q-learning; for the one
move actually taken next, plain Sarsa. The averaged form is the one this book's
lander runs all the way to touchdown in Chapter 15.)
AND THE MISS LIVES IN ONE SLOT -- THE ENGINE WE ACTUALLY FIRED
We have a guess and a target, so the miss is their difference -- the same "how
wrong" as every post before:
how wrong = target - worth of the move we took
= y - Q(s, engine 0)
= 4.42 - 5.5
= -1.08
The net was 1.08 too high on engine 0. And it is ONLY about engine 0: the net
offered four guesses, but the world graded just one -- we fired engine 0, so only
engine 0's worth was put to the test. The other three were never tried this step,
so we have nothing to say about them. That is why the miss is a row zero everywhere
except the fired engine's slot:
how-wrong row = [ -1.08, 0, 0, 0 ]
^^^^^ engine 0 only; the other three untested, so 0
A different step, same recipe. This time the lander fired engine 3
(its worth on the main pass above was Q3 = 2.0), the world paid reward -2, and at
the landing the net reads Q(s') = [2, 1, 0, 1] with chances [0.25, 0.25, 0.25,
0.25]. dilute 0.9. Compute the averaged next, the target, the miss, and the
how-wrong row.
CHECK: averaged next = 0.25 x (2 + 1 + 0 + 1) = 0.25 x 4 = 1.0
y = -2 + 0.9 x 1.0 = -1.1
how wrong = -1.1 - 2.0 = -3.1
row = [ 0, 0, 0, -3.1 ] (engine 3's slot, nothing else)
WHICH LEAVES THE HARD QUESTION FOR NEXT TIME
Here is where the table-free machine bites back. On the car, "how wrong" landed on
the two lit tiles and the job was done -- the feature told you EXACTLY which
weights to nudge. Here there is no such pointer. One number, -1.08, has to correct
the whole pile: sheet A (2x3), sheet C (3x4), and the two nudge rows -- 25 dials in
the toy, 3,332 on the real lander. One number cannot tell 3,332 dials how to
move; the correction must somehow spread back through the bend and across both
sheets, each dial getting its own share by how much it pushed the guess. How a
single miss becomes 3,332 separate nudges -- backpropagation, by pencil -- is the
whole of the next post. This one built the machine and weighed its guess; the next
one teaches it.
HUNTING FOR A TABLE THAT DOES NOT EXIST, AND FIVE MORE DEAD ENDS
"s, psi, x... which one is 'the state'?" Three rows wearing similar coats, and I
kept handing sheet C the wrong one. Lay them side by side and the coats come off:
s = [1, 2] is the world's dials; psi = [2.5, -0.5, -0.5] is the middle BEFORE the
bend; x = [2.5, 0, 0] is the middle AFTER the bend -- and only x ever touches
sheet C. Three different rows, three different jobs. Name them out loud every
pass: state in, psi made, x bent, Q out.
"A zeroed middle still passes SOMETHING on, surely." It passes exactly nothing: in
Q1 = (2.5)(-1) + (0)(1) + (0)(2) + 1.0, the two dead middles contribute (0)(1) = 0
and (0)(2) = 0 -- a dead middle erases its entire ROW of C from the sum, as if the
row were not there. After the bend, a dead middle is not "small" -- it is absent.
(Which middles die changes with the state: [1,2] killed p2 and p3; [2,0] killed
only p2.)
"The bend rescued the middle -- so bend the exit too, for symmetry." Bend the
exit and every worth leaves through max(worth, 0). Read the main pass again:
Q1 = -1.5. A bent exit prints max(0, -1.5) = 0 instead. But a worth is a
promise of reward still coming, and the lander's rewards go NEGATIVE -- a crash
pays badly, and -1.5 is an honest reading: "firing engine 1 here ends poorly."
A machine with a bent exit cannot UTTER a negative worth; every crash warning
flattens to 0, and an engine that ends in disaster grades exactly like an
engine that ends at nothing. The middle bend earns its seat by stopping two
stages from collapsing into one. After the LAST stage there is no next stage
to protect -- an exit bend prevents no collapse and only censors answers.
Bends between stages, never on the exit.
"The net made four guesses, so the world graded four." I wanted to correct all
four worths from one move, but the world paid reward 1 for firing engine 0 -- it
said nothing about engines 1, 2, 3. The only honest miss row is [-1.08, 0, 0, 0]:
one tested slot, three untested zeros. A move tests exactly one worth. The other
engines' turn comes when they are fired.
"Somewhere outside sits an answer sheet -- y tells me which engine was RIGHT." I
pictured the target as a verdict mailed in by the world, a 1 stamped under the
correct engine. But look where the -1.1 above actually came from: the machine
built it ITSELF, from a paid fact and its own opinion -- y = -2 + 0.9 x 1.0, a
reward the world paid plus the dilute times a chance-weighted average the machine
computed from its OWN four landing worths. Nobody outside knows the right engine;
there is no answer sheet to be near. Which also kills the twin belief that the
machine "picks the engine closest to y": y exists only at grading time, for the
one engine already fired. Picking always reads the four Q numbers, and grading
always builds y fresh -- two different moments, two different jobs.
"Fine, but WHERE are the worths stored?" I kept hunting for the table, and the
machine answered with two rows: the same 25 dials produced Q([1,2]) =
[5.5, -1.5, 0, 2] AND Q([2,0]) = [3.5, 2.5, 2.0, 0] -- two states, eight worths,
zero cells. Every worth of every state -- infinitely many states -- flows out of
the same 25 numbers. There is no table. The dials ARE the knowledge, and a worth
is a computation, not an address.
SEAM. Pencil ends here; below, the same numbers in Python.
dilute = 0.9
# forward pass s=[1,2]
# sheet A (2x3), nudge b1
p1 = 1*1 + 2*0.5 + 0.5 # 1+1+0.5 = 2.5
p2 = 1*(-2) + 2*1 + (-0.5) # -2+2-0.5 = -0.5
p3 = 1*0.5 + 2*(-1)+ 1.0 # 0.5-2+1.0 = -0.5
print(p1, p2, p3) # 2.5 -0.5 -0.5
# ReLU: flatten negatives to zero
x1 = p1 if p1 > 0 else 0 # 2.5 (kept)
x2 = p2 if p2 > 0 else 0 # 0 (killed)
x3 = p3 if p3 > 0 else 0 # 0 (killed)
print(x1, x2, x3) # 2.5 0 0
# sheet C (3x4), nudge b2 -- only first row of C survives (x2=x3=0)
Q0 = x1*2 + x2*1 + x3*(-1) + 0.5 # 5 + 0 + 0 + 0.5 = 5.5
Q1 = x1*(-1)+ x2*1 + x3*2 + 1.0 # -2.5+0+0+1.0 = -1.5
Q2 = x1*0 + x2*(-1)+x3*1 + 0.0 # 0+0+0+0 = 0.0
Q3 = x1*1 + x2*0 + x3*(-1)+ (-0.5) # 2.5+0+0-0.5 = 2.0
print(Q0, Q1, Q2, Q3) # 5.5 -1.5 0.0 2.0
# YOUR TURN CHECK s=[2,0]
p1b = 2*1 + 0*0.5 + 0.5 # 2+0+0.5 = 2.5
p2b = 2*(-2) + 0*1 + (-0.5) # -4+0-0.5 = -4.5
p3b = 2*0.5 + 0*(-1)+ 1.0 # 1+0+1.0 = 2.0
x1b = p1b if p1b > 0 else 0 # 2.5
x2b = p2b if p2b > 0 else 0 # 0 (killed)
x3b = p3b if p3b > 0 else 0 # 2.0
Q0b = x1b*2 + x2b*1 + x3b*(-1)+ 0.5 # 5+0-2+0.5 = 3.5
Q1b = x1b*(-1)+ x2b*1 + x3b*2 + 1.0 # -2.5+0+4+1.0 = 2.5
Q2b = x1b*0 + x2b*(-1)+x3b*1 + 0.0 # 0+0+2+0 = 2.0
Q3b = x1b*1 + x2b*0 + x3b*(-1)+(-0.5) # 2.5+0-2-0.5 = 0.0
print(Q0b, Q1b, Q2b, Q3b) # 3.5 2.5 2.0 0.0 -> engine 0 wins
# THE WALK PROOF: equal state-steps, UNEQUAL worth-steps (s2 pinned at 2)
# s = [2, 2]
p1c = 2*1 + 2*0.5 + 0.5 # 3.5
p2c = 2*(-2) + 2*1 + (-0.5) # -2.5
p3c = 2*0.5 + 2*(-1)+ 1.0 # 0.0 <- sitting exactly on the fold
x1c = p1c if p1c > 0 else 0 # 3.5
x2c = p2c if p2c > 0 else 0 # 0
x3c = p3c if p3c > 0 else 0 # 0 (the fold scores as shut: 0.0 > 0 is False)
Q0c = x1c*2 + x2c*1 + x3c*(-1) + 0.5 # 7.0 + 0.5 = 7.5
# s = [3, 2]
p1d = 3*1 + 2*0.5 + 0.5 # 4.5
p2d = 3*(-2) + 2*1 + (-0.5) # -4.5
p3d = 3*0.5 + 2*(-1)+ 1.0 # 0.5 <- the gate is now OPEN
x1d = p1d if p1d > 0 else 0 # 4.5
x2d = p2d if p2d > 0 else 0 # 0
x3d = p3d if p3d > 0 else 0 # 0.5
Q0d = x1d*2 + x2d*1 + x3d*(-1) + 0.5 # 9.0 - 0.5 + 0.5 = 9.0
print(Q0c, Q0d) # 7.5 9.0
print(Q0c - 5.5, Q0d - Q0c) # 2.0 1.5 <- the slope changed mid-walk
# THE TENT: two gated middles, worth = max(0,s) - 2*max(0, s-1)
t_a = max(0, -1) - 2*max(0, -1-1) # 0 flat
t_b = max(0, 0) - 2*max(0, 0-1) # 0 flat ends here
t_c = max(0, 0.5) - 2*max(0, 0.5-1) # 0.5 rising, slope +1
t_d = max(0, 1) - 2*max(0, 1-1) # 1 the peak
t_e = max(0, 1.5) - 2*max(0, 1.5-1) # 0.5 falling, slope -1
t_f = max(0, 2) - 2*max(0, 2-1) # 0
t_g = max(0, 3) - 2*max(0, 3-1) # -1 slope -1 continues
print(t_a, t_b, t_c, t_d, t_e, t_f, t_g) # 0 0 0.5 1 0.5 0 -1
# A BENT EXIT WOULD CENSOR THE CRASH WARNING
print(max(0, -1.5)) # 0 <- Q1's honest -1.5, flattened to nothing
# Expected Sarsa target: fired engine 0, reward=1, Q(s')=[3,5,1,2], chances=[0.1,0.6,0.1,0.2]
avg_next = 0.1*3 + 0.6*5 + 0.1*1 + 0.2*2 # 0.3+3.0+0.1+0.4 = 3.8
y = 1 + dilute * avg_next # 1+0.9*3.8 = 4.42
how_wrong = y - Q0 # 4.42-5.5 = -1.08
print(avg_next, y, how_wrong) # 3.8 4.42 -1.08
# YOUR TURN: engine 3, reward=-2, Q(s')=[2,1,0,1], uniform chances
avg2 = 0.25*2 + 0.25*1 + 0.25*0 + 0.25*1 # 0.25*4 = 1.0
y2 = -2 + dilute * avg2 # -2+0.9*1 = -1.1
hw2 = y2 - Q3 # -1.1-2.0 = -3.1
print(avg2, y2, hw2) # 1.0 -1.1 -3.1
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 14 -- Function Approximation):
Part 1 -- State Aggregation by Pencil .
Part 2 -- Tile Coding by Pencil .
Part 3 -- Sarsa Control by Pencil .
Part 4 (this post) -- the chapter closes here; teaching the net opens
Chapter 15: Backpropagation by Pencil.
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================