==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 14 . FUNCTION APPROXIMATION . PART 1 OF 4
Too Many Spots for a Table: State Aggregation by Pencil
============================================================================================
A spot = one place in a world where
you can stand. A move = a direction you pick. A reward = a number the world pays on
a move. A worth = one number saying how good a spot is, counting the rewards you
expect from there on. Until now, on this blog, worths lived in a table: spot 1's
worth, spot 2's worth, all the way down.
That table is fine for a 48-square grid. But picture a long line of 500 spots:
worth: [ V[1] , V[2] , V[3] , ... , V[500] ] 500 separate numbers
Two problems, both fatal once the world gets big. First, 500 numbers is a lot to
learn -- and a real world (a board position, a screen of pixels) has millions or
more. Second, each spot learns ALONE: visiting spot 250 teaches you nothing about
spot 251, even though they are next-door neighbours. The table has no way to share.
SO GROUP THE SPOTS: ONE NUMBER PER GROUP, NOT PER SPOT
Take the 500 spots and bundle them into 10 groups of 50. Keep ONE number per group:
spots 1.. 50 --> group 0
spots 51..100 --> group 1
spots 101..150 --> group 2
...
spots 451..500 --> group 9
keep one number per group: weights = [ w0, w1, ..., w9 ] only 10 numbers
500 worths collapse to 10 weights. Every spot in a group SHARES its group's number,
so the moment you learn anything about one spot, all 50 of its group-mates move with
it. That sharing -- 50 spots learning together -- is the whole speed-up. (The
textbook word is generalization.)
WHICH NEEDS A WAY TO SAY "WHICH GROUP": A ONE-HOT POINTER
How does a spot point at its group? With a feature: a row of 10 numbers, all 0
except a single 1 in its group's slot. Drawn for three spots:
spot 1 (group 0): feature = [ 1,0,0,0,0,0,0,0,0,0 ]
spot 51 (group 1): feature = [ 0,1,0,0,0,0,0,0,0,0 ]
spot 250 (group 4): feature = [ 0,0,0,0,1,0,0,0,0,0 ]
The feature is a row of switches, one per group, with exactly ONE switch on. Its
length is the number of GROUPS (10), never the number of spots. The 1's position
says which group; the value is always just 1, a marker -- never the spot number.
To turn a feature into a worth, dot it with the weights (multiply slot by slot,
then add):
worth(spot 51) = weights . feature
= [w0,w1,...,w9] . [0,1,0,0,0,0,0,0,0,0]
= w0*0 + w1*1 + (rest)*0
= w1
The one-hot just PICKS OUT that group's weight. So the feature is a selector; the
weight is the value.
Which group does a spot land in? Floor-divide (spots are numbered from 1, so
subtract 1 first):
group of a spot = (spot - 1) // (spots per group)
Worked on a tiny world -- 10 spots, 5 groups, 2 spots per group:
spot 1 -> (1-1)//2 = 0 -> [1,0,0,0,0]
spot 3 -> (3-1)//2 = 1 -> [0,1,0,0,0]
spot 6 -> (6-1)//2 = 2 -> [0,0,1,0,0]
spot 10 -> (10-1)//2 = 4 -> [0,0,0,0,1]
Back on the 500-spot line (10 groups of 50). Which group holds spot
337? Which holds spot 500? Draw spot 337's feature.
CHECK: spot 337 -> (337-1)//50 = 336//50 = 6 -> group 6
spot 500 -> (500-1)//50 = 499//50 = 9 -> group 9
feature(337) = [0,0,0,0,0,0,1,0,0,0] (ten slots, the 1 in slot 6)
WHICH MEANS THERE IS NO TABLE OF WORTHS ANY MORE
This is the real break from every earlier post on this blog. There is no list of
500 worths to look up. There are only 10 weights, and a spot's worth is BUILT from
them on the spot:
OLD (a table): look up V[120] in a 500-long list.
NEW (here): worth(120) = weights . feature(120) = the weight of 120's group.
Worked, with weights = [-1.5, 0.5, 1.0, -0.5, 1.5, -0.5, 1.5, 0.0, -0.5, -1.0]:
worth(50) : spot 50 is group (50-1)//50 = 0 -> w0 = -1.5
worth(120) : spot 120 is group (120-1)//50 = 2 -> w2 = 1.0
worth(337) : spot 337 is group (337-1)//50 = 6 -> w6 = 1.5
Ten weights GENERATE all 500 worths. Change one weight and all 50 spots that share
it move at once.
SO HOW DO THE WEIGHTS LEARN? THE SAME ONE-SAMPLE NUDGE, AIMED AT A WEIGHT
The one-sample nudge (TD(0), built earlier on this blog and rebuilt right here):
you left a spot, grabbed a reward, landed on a next spot, and you crawl the LEFT
spot's worth a fraction of the way toward a target:
target = reward + dilute x worth(next)
how wrong (the TD error) = target - worth(left)
worth(left) = worth(left) + size x (how wrong)
Here size is the crawl fraction (0.1 here) and dilute is the future-shrinker (0.9
here: the future counts 10% less per step). Nothing changes except the last line:
there is no worth(left) cell to write into any more -- worth(left) is
weights . feature(left). So instead of writing a cell, we nudge the WEIGHTS, and
the one-hot feature steers the nudge onto exactly one weight:
how wrong = reward + dilute x worth(next) - worth(left)
weights = weights + size x (how wrong) x feature(left)
Because feature(left) is a one-hot, "x feature(left)" zeroes out every weight
except the left spot's group -- only that one weight moves. At a terminal spot (the
game ended, there is no next spot to read) the target loses its future piece and
becomes the reward alone -- the anchor, the one target with no guess inside it.
WHOLE STEP BY HAND -- EVERY NUMBER
weights = [-1.5, 0.5, 1.0, -0.5, 1.5, -0.5, 1.5, 0.0, -0.5, -1.0], size 0.1,
dilute 0.9. You leave spot 50, grab reward 10, land on spot 120.
First, the two worths, each a dot of weights with a one-hot (so each is just one
weight):
spot 50 is group (50-1)//50 = 0 -> worth(left) = w0 = -1.5
spot 120 is group (120-1)//50 = 2 -> worth(next) = w2 = 1.0
Then the TD error:
how wrong = reward + dilute x worth(next) - worth(left)
= 10 + 0.9 x 1.0 - ( -1.5 )
= 10 + 0.9 + 1.5
= 12.4
Then the nudge -- the left spot's feature is the group-0 one-hot [1,0,0,...], so
only w0 moves:
w0 = w0 + size x (how wrong) x 1
= -1.5 + 0.1 x 12.4 x 1
= -1.5 + 1.24
= -0.26
Drawn, before and after (only group 0's weight changed):
group: 0 1 2 3 4 ...
BEFORE: -1.5 0.5 1.0 -0.5 1.5 ...
AFTER: -0.26 0.5 1.0 -0.5 1.5 ...
^^^^^ moved (every other weight untouched)
And because spots 1..50 ALL share w0, all fifty of their worths just rose from -1.5
to -0.26 in one step. That is the generalization, paid for.
The next step of the same walk. The weights now read
[-0.26, 0.5, 1.0, -0.5, 1.5, -0.5, 1.5, 0.0, -0.5, -1.0] (only w0 changed above).
You leave spot 120, grab reward -3, land on spot 480. size 0.1, dilute 0.9. Which
weight moves, and to what?
CHECK: spot 120 is group (120-1)//50 = 2 -> worth(left) = w2 = 1.0
spot 480 is group (480-1)//50 = 9 -> worth(next) = w9 = -1.0
how wrong = -3 + 0.9 x (-1.0) - 1.0 = -3 - 0.9 - 1.0 = -4.9
w2 = 1.0 + 0.1 x (-4.9) x 1 = 1.0 - 0.49 = 0.51 (only w2 moves --
and all fifty spots 101..150 just dropped from 1.0 to 0.51 together)
WHY IT IS CALLED "SEMI"-GRADIENT -- THE PIECE WE THROW AWAY
The honest name for this update is semi-gradient TD, and "semi" -- half -- is a
confession worth unpacking, because it is the one genuinely subtle thing here.
We are trying to make worth(left) match its target, reward + dilute x worth(next).
The miss is (target - worth(left)). To shrink that miss by tweaking the weights,
you ask how the miss changes as each weight changes -- its slope. The miss has TWO
parts that ride on the weights, not one:
worth(left) = weights . feature(left) -- rides on the weights (slope = feature(left))
worth(next) = weights . feature(next) -- ALSO rides on the weights! it is inside
the target, and the target is reward +
dilute x worth(next)
So a TRUE gradient step would move the weights by size x (how wrong) x BOTH slopes:
true step = size x (how wrong) x ( feature(left) - dilute x feature(next) )
With the step worked above (left = group-0 one-hot, next = group-2 one-hot,
how wrong 12.4, size 0.1, dilute 0.9):
w0 piece : +0.1 x 12.4 x 1 = +1.24 (from feature(left))
w2 piece : +0.1 x 12.4 x ( -0.9 x 1 ) = -1.116 (from -dilute x feature(next))
Semi-gradient KEEPS the first piece and THROWS AWAY the second. It pretends the
target is a fixed label -- a number to chase -- and ignores that worth(next) also
slides when the weights slide. So it moves only w0 by +1.24 (to -0.26) and leaves
w2's -1.116 on the floor:
true gradient : w0 += 1.24 , w2 -= 1.116 (chases a target that is moving too)
semi-gradient : w0 += 1.24 (treats the target as standing still)
\____ the dropped -1.116 on w2 is the "missing half" ____/
Why drop a real piece of the slope on purpose? Because chasing a target while also
differentiating it -- letting the thing you aim at shift toward you as you move --
is unstable and tangled; treating the target as a fixed label is simpler, steadier,
and is what works in practice. The "semi" is just the blunt admission: we took the
worth(left) half of the gradient and skipped the target half.
EVERY SPOT'S WORTH AT ONCE -- A STACK OF SWITCHES
To read out all 500 worths together, stack every spot's one-hot into one block (a
row per spot) and dot the block with the weights. A tiny 4-spot, 3-group version:
weights = [ 2, 5, -1 ] (group 0, 1, 2)
spot 1: [1,0,0] -> peek group 0 -> 2
spot 2: [1,0,0] -> peek group 0 -> 2 (same group, same worth)
spot 3: [0,1,0] -> peek group 1 -> 5
spot 4: [0,0,1] -> peek group 2 -> -1
-> worths = [ 2, 2, 5, -1 ]
On the real 500-spot line the stack is RUNS of identical rows -- the first 50 rows
are all [1,0,...], then 50 rows of [0,1,0,...], and so on -- so the 500 worths come
out as ten distinct numbers, each repeated fifty times: [ w0 x50, w1 x50, ..., w9 x50 ].
WHERE ARE MY 500 WORTHS? -- THE HUNT THAT TAUGHT ME WHAT A WEIGHT IS
"Weights is what? Where are my 500 worths?" I kept hunting for the big list, until
one computation showed me there is none: worth(120) = w2 = 1.0 was COMPUTED the
moment I asked -- a pick, not a lookup. There is no list; there are 10 weights and
a recipe. A weight is not a worth. Worths are built on demand: weights . feature,
fresh every time you need one.
"For spot 120 the feature must be 500 long... or hold the number 120 somewhere."
Write it out and the belief dies on the page: feature(120) = [0,0,1,0,0,0,0,0,0,0]
-- TEN slots (one per group), and the entry is a plain 1 sitting in slot
(120-1)//50 = 2. No 120 anywhere, no 500 anywhere. The feature's length counts
GROUPS, and its 1 is a marker, never a value.
"The game ended, the reward goes away, there is no going back -- so no update,
right?" Backwards, and it cost me an evening. The ending kills the FUTURE piece,
not the update. Leave a group-6 spot (w6 = 1.5) and the game ends with reward -35:
how wrong = -35 - 1.5 = -36.5, and w6 = 1.5 + 0.1 x (-36.5) = -2.15. The last
update still runs -- it is the anchor, the one built from plain paid fact. Game
over means target = reward alone, never "no target".
"Spots 1 to 50 are in the same group, so they all have the same worth... wait,
ALWAYS?" Yes -- worth(1) = worth(50) = w0, forever, even if the TRUE worths climb
steadily from spot 1 to spot 50. The guess is a staircase; the truth is a ramp:
true worth ___
___/ <- the guess: one flat step per group
____/
___/. . . . . . . <- the truth: rising smoothly inside each group
(the step can only match its AVERAGE)
Sharing buys speed and pays in blur. Inside a group the machine is blind. That
blur is not a bug to fix here -- it is the price, and the NEXT post (tile coding)
is the machine that buys the speed without going blind.
SEAM. Pencil ends here; below, the same numbers in Python.
No loops, no functions -- group assignments, worth lookups, two TD steps, the
semi-gradient breakdown, and the terminal anchor. Per step: 1 floor-divide,
1 subtract, 1 multiply, 1 add = 4 strokes.
size, dilute = 0.1, 0.9
w = [-1.5, 0.5, 1.0, -0.5, 1.5, -0.5, 1.5, 0.0, -0.5, -1.0]
# GROUP: (spot-1)//50 picks the group in a 500-spot, 10-group world
g50 = (50 - 1) // 50 # 49//50 = 0
g120 = (120 - 1) // 50 # 119//50 = 2
g337 = (337 - 1) // 50 # 336//50 = 6 (YOUR TURN check)
g500 = (500 - 1) // 50 # 499//50 = 9 (YOUR TURN check)
g480 = (480 - 1) // 50 # 479//50 = 9
# WORTH: one-hot dot = just pick the group's weight
worth_50 = w[g50] # w[0] = -1.5
worth_120 = w[g120] # w[2] = 1.0
worth_337 = w[g337] # w[6] = 1.5
print(worth_50, worth_120, worth_337) # -1.5 1.0 1.5
# STEP 1: leave spot 50 (w0=-1.5), reward=10, land spot 120 (w2=1.0)
how_wrong = 10 + dilute*worth_120 - worth_50 # 10+0.9*1.0-(-1.5) = 12.4
w[g50] = w[g50] + size * how_wrong * 1 # -1.5 + 0.1*12.4 = -0.26
print(how_wrong, w[g50]) # 12.4 -0.26
# YOUR TURN: leave spot 120 (w2=1.0), reward=-3, land spot 480 (w9=-1.0)
how_wrong2 = -3 + dilute*w[g480] - w[g120] # -3+0.9*(-1.0)-1.0 = -4.9
w[g120] = w[g120] + size * how_wrong2 * 1 # 1.0 + 0.1*(-4.9) = 0.51
print(how_wrong2, w[g120]) # -4.9 0.51
# SEMI-GRADIENT: step-1 numbers (how_wrong=12.4, left=g0, next=g2, dilute=0.9)
w0_piece = size * 12.4 * 1 # 0.1*12.4*1 = +1.24 (kept)
w2_piece = size * 12.4 * (-dilute * 1) # 0.1*12.4*(-0.9) = -1.116 (dropped)
print(w0_piece, round(w2_piece, 4)) # 1.24 -1.116
# TERMINAL: leave group-6 spot (w6=1.5), game ends, reward=-35
w6_old = 1.5
how_wrong_t = -35 - w6_old # -35 - 1.5 = -36.5 (no future piece)
w6_new = w6_old + size * how_wrong_t # 1.5 + 0.1*(-36.5) = -2.15
print(how_wrong_t, w6_new) # -36.5 -2.15
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 14 -- Function Approximation):
Part 1 (this post) .
Part 2 -- Tile Coding by Pencil .
Part 3 -- Sarsa Control by Pencil .
Part 4 -- A Q-Network by Pencil
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================