==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 14 . FUNCTION APPROXIMATION . PART 2 OF 4
Sharp From Blurry: Tile Coding by Pencil
============================================================================================
A spot = one place in a world. A
worth = one number saying how good a spot is, counting the rewards you expect from
there on. A weight = one learned number. The previous post grouped the spots and
kept one weight per group: each spot pointed at its group with a one-hot feature (a
row of switches, exactly one flipped on) and its worth was that group's weight, so
fifty group-mates learned together. It bought speed and paid in blur: coarse groups
learn fast but cannot tell group-mates apart; squeeze the groups down toward
one-spot-each and you are back to a slow table. Sharing OR sharpness -- with plain
grouping, never both. This post is the way out.
BUT THE STATE IS NOW TWO DIALS THAT NEVER LAND TWICE
Forget tidy numbered spots. Take the standard toy, a car in a valley, too weak to
climb straight out -- it must rock back and forth to build speed. Its whole state is
two real-number dials:
position (how far along the valley) -- a real number, e.g. -0.45
velocity (how fast, which way) -- a real number, e.g. 0.02
These are not 500 tidy spots. They are two sliders that can sit at -0.4500001 or
-0.4500002 -- the car is almost never in the *exact* same place twice. A table wants
one cell per state, so first you would have to chop each slider into bins. Say a
thousand position bins and a thousand velocity bins:
position bins x velocity bins = 1000 x 1000 = 1,000,000 cells
A million weights for a crude two-dial toy -- and the chop is still coarse, and it
STILL shares nothing across a bin wall. Make it finer and the count explodes; a real
screen of pixels would need more cells than atoms. The table is dead here before it
starts:
position ---> | one cell per (position, velocity) pair | ---> a worth
velocity ---> | ... a million-plus of them, and rising ... |
We need a worth that is BUILT, not looked up -- and built so that close states
share, far states do not, and nobody pays for a million cells.
SO LAY THE SAME COARSE RULER DOWN TWICE, SHIFTED
Here is the whole trick, and it is small. Take ONE dial first -- position, on a
stretch from 0 to 1 -- and lay a COARSE ruler over it: two fat tiles, each half a
unit wide.
ruler A: [-----A0-----][-----A1-----]
0 0.5 1.0
A0 covers [0, 0.5), A1 covers [0.5, 1.0). Coarse -- only two tiles -- so it
generalises hard: every point in the left half is "A0", indistinguishable. On its
own this ruler is hopelessly blurry; it cannot tell 0.1 from 0.4.
Now lay a SECOND ruler of the same fat tiles, but slide it left by a quarter of a
unit -- a second set of cuts, stacked one half-cut ahead of the first:
ruler A: [-----A0-----][-----A1-----]
0 0.5 1.0
ruler B: [--B0--][-----B1-----][--B2--]
-0.25 0.25 0.75 1.25
Ruler B's walls fall at 0.25 and 0.75 -- right in the MIDDLE of ruler A's tiles.
Same coarseness, just shifted. That offset is the entire idea.
WHICH PINS A POINT WITH TWO TILES AT ONCE
Drop the car at position 0.3 and read off which tile lights up on EACH ruler:
0.3 on ruler A: 0.3 is in [0, 0.5) -> A0
0.3 on ruler B: 0.3 is in [0.25, 0.75) -> B1
So position 0.3 is not one tile, it is the PAIR { A0, B1 } -- one tile per ruler.
Write that as a feature the same switch-row way as before: five tiles exist in all
(A0, A1, B0, B1, B2), so the row is five wide, and now TWO switches are on:
tiles: A0 A1 B0 B1 B2
0.3 -> [ 1 0 0 1 0 ] two switches on, one per ruler
A one-hot has exactly one switch on; this row has two. That is the only change to
the machinery -- and every good thing below falls out of it.
WHICH MEANS TWO BLURRY RULERS READ SHARPER THAN EITHER ALONE
Ruler A alone splits the line into 2 regions. Ruler B alone splits it into 3. But
what a point actually carries is the PAIR of tiles, and the pairs change wherever
EITHER wall falls -- at 0.25, 0.5, and 0.75. Walk the line and list the pair:
[0, 0.25) -> A0, B0
[0.25, 0.5 ) -> A0, B1
[0.5, 0.75) -> A1, B1
[0.75, 1.0 ) -> A1, B2
Four distinct readings -- a quarter-unit resolution -- out of two rulers whose tiles
are each half a unit wide. The blur of each ruler is real, but their WALLS land in
different places, so the overlap pins the point twice as finely as either coarse
ruler could. Two blurry rulers, read together, are sharp. Stack eight and the
overlap gets eighth-of-a-tile sharp -- from eight coarse grids, no fine grid
anywhere.
Two points, read off both rulers (ruler A's walls at 0.5; ruler B's at
0.25 and 0.75). Which pair of tiles does 0.8 light? Which does 0.2 light? Write
both features (five slots: A0 A1 B0 B1 B2).
CHECK: 0.8 -> A: [0.5,1.0) = A1 ; B: [0.75,1.25) = B2 -> { A1, B2 }
feature = [ 0, 1, 0, 0, 1 ]
0.2 -> A: [0,0.5) = A0 ; B: [-0.25,0.25) = B0 -> { A0, B0 }
feature = [ 1, 0, 1, 0, 0 ]
AND IT SHARES EXACTLY THE RIGHT AMOUNT -- BY HOW MANY TILES OVERLAP
Now the other half of the prize, the thing plain grouping could never give. Nudge
the car a little and watch how many of its two tiles stay put:
0.3 -> { A0, B1 }
0.4 -> A: [0,0.5)->A0 , B: [0.25,0.75)->B1 = { A0, B1 } SAME two tiles
0.6 -> A: [0.5,1.0)->A1 , B: [0.25,0.75)->B1 = { A1, B1 } shares B1 only
0.9 -> A: [0.5,1.0)->A1 , B: [0.75,1.25)->B2 = { A1, B2 } shares NOTHING
Read that ladder. 0.3 and 0.4 are practically the same place, and they fire the SAME
two tiles -- so whatever one learns, the other gets in full. 0.6 is a step away and
shares ONE tile -- it gets half the lesson. 0.9 is far and shares NONE -- it is
untouched. The amount two states share is just the count of tiles they have in
common, and that count falls off smoothly with distance. Plain grouping could only
share ALL (same group) or NOTHING (different group) -- a cliff. Tile coding makes a
ramp. That is generalisation you can dial, and it came free with the shift.
SO THE WORTH IS THE SUM OF THE ACTIVE WEIGHTS
Give every tile its own weight, and build a spot's worth by dotting the feature with
the weights (multiply slot by slot, add) -- except now two switches are on, so the
dot ADDS two weights instead of picking one:
weights: wA0 wA1 wB0 wB1 wB2
1.0 -0.5 0.0 0.5 0.0
worth(0.3) = weights . [1,0,0,1,0]
= wA0 + wB1
= 1.0 + 0.5
= 1.5
With one switch on, "the worth is that group's one weight." With two: "the worth is
the sum of the active tiles' weights." A k-hot instead of a one-hot, a sum instead
of a pick. No table of worths exists -- five weights GENERATE the worth of every
point on the line, and points that share tiles share weights.
SO THE WEIGHTS LEARN BY THE SAME ONE-SAMPLE NUDGE, SPLIT ACROSS THE ACTIVE TILES
The one-sample nudge (TD(0), rebuilt right here): you leave a spot, grab a reward,
land on the next spot, and crawl the LEFT spot's worth a fraction of the way toward
a target -- reward + dilute x worth(next), where dilute is the future-shrinker (0.9
here). Because a worth is now weights-dot-feature, the crawl lands on the weights,
steered by the feature:
how wrong = reward + dilute x worth(next) - worth(left)
weights = weights + size x (how wrong) x feature(left)
The feature(left) is the k-hot, so "x feature(left)" lands the nudge on exactly the
active tiles and zeroes the rest. One snag the one-hot never had: with TWO tiles
both adding into the worth, a full-strength step on EACH would move the worth by
twice what you asked -- an overshoot. So split the step across the tiles. With T
rulers, use
size = alpha / T (here alpha = 0.2, T = 2 rulers, so size = 0.1)
so the T active tiles together move the worth by the one step you meant.
Worked, every number. Leave position 0.3 (tiles A0, B1), grab reward 2, land on
position 0.6 (tiles A1, B1). dilute 0.9, size 0.1, weights as drawn above
[1.0, -0.5, 0.0, 0.5, 0.0]:
worth(left = 0.3) = wA0 + wB1 = 1.0 + 0.5 = 1.5
worth(next = 0.6) = wA1 + wB1 = -0.5 + 0.5 = 0.0
how wrong = reward + dilute x worth(next) - worth(left)
= 2 + 0.9 x 0.0 - 1.5
= 0.5
Now nudge the LEFT point's two tiles, each by size x how wrong = 0.1 x 0.5 = 0.05:
wA0 : 1.0 + 0.05 = 1.05
wB1 : 0.5 + 0.05 = 0.55
(wA1, wB0, wB2 never lit for the left point -- untouched)
Drawn, before and after (only the two active tiles moved):
tile: A0 A1 B0 B1 B2
BEFORE: 1.0 -0.5 0.0 0.5 0.0
AFTER: 1.05 -0.5 0.0 0.55 0.0
^^^^ ^^^^ (the other three stand still)
And the worth of 0.3 climbed the right way: worth(0.3) = 1.05 + 0.55 = 1.60, up 0.10
from 1.5 -- two tiles, 0.05 each, the step you asked for. Now read the fallout on
the neighbours, for free:
worth(0.4) -> A0,B1 -> 1.05 + 0.55 = 1.60 rose the full amount (shares both tiles)
worth(0.6) -> A1,B1 -> -0.5 + 0.55 = 0.05 rose half (shares B1 only)
worth(0.9) -> A1,B2 -> -0.5 + 0.0 = -0.5 untouched (shares nothing)
One step taught 0.3, and its lesson spread to the close-by 0.4 in full, to 0.6 in
half, and not at all to the far 0.9 -- weighted by shared tiles. That is the ramp,
paid for in one nudge. (If the move ENDS the game there is no next spot to read, so
the target loses its future piece: target = reward alone -- the anchor, the one
target with no guess inside it.)
The next step of the same walk. The weights now read
[1.05, -0.5, 0.0, 0.55, 0.0]. You leave position 0.6 (tiles A1, B1), grab reward 0,
land on position 0.9 (tiles A1, B2). dilute 0.9, size 0.1. Which two weights move,
and to what?
CHECK: worth(left = 0.6) = wA1 + wB1 = -0.5 + 0.55 = 0.05
worth(next = 0.9) = wA1 + wB2 = -0.5 + 0.0 = -0.5
how wrong = 0 + 0.9 x (-0.5) - 0.05 = -0.45 - 0.05 = -0.5
each active tile of the LEFT point moves by 0.1 x (-0.5) = -0.05:
wA1 = -0.5 - 0.05 = -0.55 , wB1 = 0.55 - 0.05 = 0.50
(note wA1 sits in BOTH points here -- it still moves once, as a
left-point tile; the k-hot of the left point is what steers)
REAL MOUNTAIN CAR -- TWO DIALS, SQUARE TILES, EIGHT RULERS
Stretch the one-line trick to the car's two dials and nothing new happens -- a tile
is just a little SQUARE now (a position band crossed with a velocity band) instead
of a segment, and a shifted ruler is a whole grid nudged diagonally. Picture eight
CCTV cameras over the same car, each grid pinned at a slightly different corner:
camera 1 camera 2 camera 3 ... eight grids, each shifted a little ...
+-+-+-+ +-+-+-+ +-+-+-+
| |*| | |*| | | | | |*| the car (a dot) sits in ONE square per camera
+-+-+-+ +-+-+-+ +-+-+-+ -> eight active tiles, e.g.
| | | | | | | | | | | | [ 19, 3, 44, 8, 27, 61, 12, 7 ]
Eight rulers -> eight switches on -> the feature is eight ones in a long row of
zeros, and a worth is the sum of those eight weights. When the car drifts a hair,
only a camera or two flips its square; the other six read the same -- smooth
sharing, sharp overlap, the same two prizes as the line.
One honest note kept for later. The real coder does not store a grid of named
squares -- even two coarse dials chopped fine would blow past a billion squares. It
HASHES each tile's coordinates into a fixed bank of slots (an index hash table) and
computes the eight numbers by arithmetic every time, never a lookup. And the car has
three real moves -- push left, coast, push right -- so the worth becomes a
worth-per-move; turning these eight-tile features into a machine that CHOOSES is the
next post.
RAW READINGS, GUESSED WALLS, ONE FINE RULER: THE DETOURS BEFORE IT CLICKED
"The ruler reads the raw position, right?" I fed the coder a raw position and it
pointed at a tile that did not exist. The car's track runs from -1.2 to 0.6 (a
stretch of 1.8). Position -0.3 with 4 tiles, fed raw: -0.3 x 4 = -1.2, floor -2 --
tile "minus two". Scaled first: fraction = (-0.3 - (-1.2)) / 1.8 = 0.9 / 1.8 = 0.5,
then 0.5 x 4 = 2 -- tile 2, real. Always squeeze the dial into [0, 1] first --
subtract the LOW end, divide by the STRETCH -- and only then talk to tiles.
"The car starts at -1.2 and ends at 0.5... right?" I asked four times, because
three different numbers were wearing the same coat, and the untangling was the
answer: -1.2 is the LEFT WALL of the track (the far end of the back-swing); 0.6 is
the RIGHT WALL; 0.5 is the GOAL LINE painted just before it; and the car STARTS
each run near the valley floor, around -0.5. Wall, wall, finish line, starting
stall -- four numbers, four different jobs. Before coding any world, write its
numbers down with their JOBS next to them, not just their values.
"Surely I need one FINE ruler -- these fat tiles will never be precise." I kept
trying to chop finer, but the coarse pair was already beating me: two rulers of
HALF-unit tiles read at QUARTER-unit resolution (the walk-the-line table above:
four distinct pair-readings), and eight rulers read at eighth-tile resolution --
while a single fine ruler with the same total tile count shares nothing between
neighbours. Sharpness comes from the OVERLAP of coarse cuts stacked one ahead of
the other, not from fineness. Never build the fine ruler.
"Two tiles are on, so nudge both by the full step." My worths kept jumping past
their targets, and the overshoot was exactly a factor of two: asking for a step of
alpha x how-wrong = 0.2 x 0.5 = 0.1 but moving BOTH live tiles by 0.1 moved the
worth (their SUM) by 0.2 -- double the ask. Split the step: size = alpha / rulers
= 0.2 / 2 = 0.1 per tile, so the team of live tiles together moves the worth by
the one step you meant.
SEAM. Pencil ends here; below, the same numbers in Python.
No loops, no functions -- tile reads for five positions, one TD step with fallout,
the YOUR TURN step, and the raw-to-scaled example. One epsilon note: (-0.3-(-1.2))
/1.8 gives 0.4999... in float; +1e-10 before the floor guards the tile index.
dilute, alpha, T = 0.9, 0.2, 2
size = alpha / T # 0.1 per tile
w = [1.0, -0.5, 0.0, 0.5, 0.0] # [wA0, wA1, wB0, wB1, wB2]
# TILE READING: ruler A walls 0/0.5/1.0; ruler B walls -0.25/0.25/0.75
def tA(p): return 0 if p < 0.5 else 1
def tB(p): return 2 if p < 0.25 else (3 if p < 0.75 else 4)
def wval(p): return w[tA(p)] + w[tB(p)]
# YOUR TURN checks: 0.8 -> {A1,B2} 0.2 -> {A0,B0}
print(tA(0.8), tB(0.8)) # 1 4 feature [0,1,0,0,1]
print(tA(0.2), tB(0.2)) # 0 2 feature [1,0,1,0,0]
# WORTH: worth(0.3) = wA0 + wB1 = 1.0 + 0.5
print(wval(0.3)) # 1.5
# TD STEP: leave 0.3 (A0,B1), reward=2, land 0.6 (A1,B1)
how_wrong = 2 + dilute*wval(0.6) - wval(0.3) # 2+0.9*0.0-1.5 = 0.5
w[tA(0.3)] += size * how_wrong # wA0: 1.0+0.05 = 1.05
w[tB(0.3)] += size * how_wrong # wB1: 0.5+0.05 = 0.55
print(how_wrong, w[0], w[3]) # 0.5 1.05 0.55
# FALLOUT: neighbours share in proportion to tiles in common
print(wval(0.4), wval(0.6), wval(0.9)) # 1.60 0.05 -0.5
# YOUR TURN: leave 0.6 (A1,B1), reward=0, land 0.9 (A1,B2)
how_wrong2 = 0 + dilute*wval(0.9) - wval(0.6) # 0+0.9*(-0.5)-0.05 = -0.5
w[tA(0.6)] += size * how_wrong2 # wA1: -0.5-0.05 = -0.55
w[tB(0.6)] += size * how_wrong2 # wB1: 0.55-0.05 = 0.50
print(how_wrong2, w[1], w[3]) # -0.5 -0.55 0.50
# RAW SCALING: position -0.3, track [-1.2, 0.6], 4 tiles
low, stretch = -1.2, 1.8
fraction = (-0.3 - low) / stretch # 0.9/1.8 -> 0.4999... in float
tile_idx = int(fraction * 4 + 1e-10) # +eps guards floor: 2
print("scaled tile:", tile_idx) # 2
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 14 -- Function Approximation):
Part 1 -- State Aggregation by Pencil .
Part 2 (this post) .
Part 3 -- Sarsa Control by Pencil .
Part 4 -- A Q-Network by Pencil
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================