==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 14 . FUNCTION APPROXIMATION . PART 3 OF 4
Letting the Car Choose: Sarsa Control by Pencil
============================================================================================
The world is a car in a valley, too
weak to climb straight out. A spot = where the car is (its position along the
valley). A move = one of three pushes: left, coast, right. A reward = a number the
world pays on a move (here a fine of -1 every step until the car escapes). A worth
= a number saying how much reward is still coming from a choice onward.
The previous post built a worth for a SPOT by tile coding: lay two coarse rulers
over the position line, shifted against each other; a spot lights ONE tile per
ruler; its worth is the sum of the lit tiles' weights. To keep every number on the
page, the same tiny stand-in is used here: one dial, position on [0,1], two rulers.
Ruler A has tiles A0=[0,0.5), A1=[0.5,1.0); ruler B is shifted a quarter-unit,
tiles B0=[-0.25,0.25), B1=[0.25,0.75), B2=[0.75,1.25). (The real car reads two
dials -- position AND speed -- with eight shifted grids; the arithmetic below is
the same, just longer.)
But a worth per SPOT cannot rank the pushes: it hands back one number for "here,"
and the car needs three -- one per push -- to choose. The spot-worth is the wrong
shape. We need a worth for the PAIR (spot, move). Everything else -- the rulers,
the lit tiles, the sum, the nudge -- carries over untouched. Only the bookkeeping
grows one notch.
SO GIVE EACH MOVE ITS OWN ROW OF WEIGHTS
One row of weights (one weight per tile) was enough to grade spots. Stack THREE
such rows -- one per push -- into a table. Same five tiles across the top; a
separate weight in each move's row:
move \ tile : A0 A1 B0 B1 B2
----------------------------------------------------
left : -2.0 -3.0 0.0 -2.5 0.0
coast : -1.0 -2.0 0.0 -1.5 0.0
right : -0.5 -1.0 0.0 -0.8 0.0
(The weights are negative because the car is fined -1 every step until it escapes,
so a worth here counts the fines still to come -- read them as "how good,"
less-negative is better.)
A worth is still a sum of lit tiles -- you just read it along the chosen MOVE's
row. At position 0.3 the two lit tiles are A0 and B1 (0.3 sits in A0=[0,0.5) and in
B1=[0.25,0.75)). So:
worth(0.3, left ) = w[left ][A0] + w[left ][B1] = -2.0 + (-2.5) = -4.5
worth(0.3, coast) = w[coast][A0] + w[coast][B1] = -1.0 + (-1.5) = -2.5
worth(0.3, right) = w[right][A0] + w[right][B1] = -0.5 + (-0.8) = -1.3
Three rows, three worths, same two tiles -- one number per push, exactly what
choosing needs.
The three worths at position 0.9. Position 0.9 lights tiles A1 (0.9
sits in [0.5,1.0)) and B2 (0.9 sits in [0.75,1.25)). Read the table above. Which
push wins?
CHECK: worth(0.9, left ) = -3.0 + 0.0 = -3.0
worth(0.9, coast) = -2.0 + 0.0 = -2.0
worth(0.9, right) = -1.0 + 0.0 = -1.0 -> right wins (least negative)
WHICH LETS THE CAR RANK ITS MOVES AND PICK -- BUT KEEP WANDERING
With a worth per push, the car ranks and grabs the best. At 0.3 the three worths
are -4.5, -2.5, -1.3, so "right" (least negative) wins. That is the GREEDY pick.
But greedy alone is a trap: a push that has never been tried keeps a stale worth,
so the car never tries it, so it never finds out. The fix: wander a small slice of
the time. Roll a spinner from 0 to 1 before each pick: under epsilon (0.1 here)
push a RANDOM one of the three, all equally likely; otherwise push the greedy one.
Ties are split by a coin.
0 0.1 1
|--- wander -----|-------------- greedy ----------------|
This wandering is not noise to be tolerated -- in a moment it turns out to be part
of what the car is learning to grade.
SO THE NUDGE CHASES THE MOVE IT WILL ACTUALLY MAKE NEXT -- THAT IS SARSA
The one-sample nudge (TD, rebuilt right here) aims a (spot, move) worth at a
target and crawls a fraction of the way there. You are AT a spot, you PUSH a move,
you collect a reward, you LAND on the next spot, and -- here is the one new beat --
you pick the move you will ACTUALLY push next, and grade against that:
target = reward + dilute x worth(next spot, next move)
how wrong = target - worth(this spot, this move)
each lit tile of (this spot, this move):
w[this move][tile] = w[this move][tile] + size x (how wrong)
Here dilute is the future-shrinker (0.9 here) and size is the crawl fraction. The
"next move" in the target is the move the spinner-and-rank habit ACTUALLY hands you
at the next spot -- wander and all. That is the whole meaning of the name: State,
Action, Reward, next State, next Action -- SARSA -- the five things the nudge
needs, the last being the move you are about to make, not the best move you could
imagine. And because several tiles are lit at once, split the step across them --
size = alpha / rulers (here 0.2 / 2 = 0.1) -- so the lit tiles together move the
worth by the one step you meant.
WHOLE STEP BY HAND -- ONE FOOTSTEP, EVERY NUMBER
Start AT position 0.3, and the car pushes RIGHT (its greedy pick, worth -1.3 from
the readout above). The world fines it -1 and rolls it to position 0.6. alpha 0.2
over 2 rulers, so size 0.1; dilute 0.9.
First, what move will the car push NEXT, at 0.6? Read all three worths there.
Position 0.6 lights tiles A1 and B1 (0.6 sits in A1=[0.5,1.0) and in B1=[0.25,0.75)):
worth(0.6, left ) = w[left ][A1] + w[left ][B1] = -3.0 + (-2.5) = -5.5
worth(0.6, coast) = w[coast][A1] + w[coast][B1] = -2.0 + (-1.5) = -3.5
worth(0.6, right) = w[right][A1] + w[right][B1] = -1.0 + (-0.8) = -1.8
Greedy at 0.6 is RIGHT (-1.8 wins), and the spinner did not call a wander this
time, so the next move is right. Now the Sarsa target and the miss:
target = reward + dilute x worth(0.6, right)
= -1 + 0.9 x (-1.8)
= -1 - 1.62
= -2.62
how wrong = target - worth(0.3, right)
= -2.62 - (-1.3)
= -1.32
The car's old worth for (0.3, right) was -1.3, too rosy; the harsher target -2.62
pulls it down. Nudge the two lit tiles of (0.3, right) -- A0 and B1 in the RIGHT
row only -- each by size x how-wrong = 0.1 x (-1.32) = -0.132:
w[right][A0] : -0.5 + (-0.132) = -0.632
w[right][B1] : -0.8 + (-0.132) = -0.932
Drawn, before and after -- only two cells in the RIGHT row moved; the left and
coast rows, and the other tiles, never lit:
right row: A0 A1 B0 B1 B2
BEFORE: -0.5 -1.0 0.0 -0.8 0.0
AFTER: -0.632 -1.0 0.0 -0.932 0.0
^^^^^^ ^^^^^^ (left & coast rows untouched)
New worth(0.3, right) = -0.632 + (-0.932) = -1.564, down 0.264 from -1.3 -- two
tiles, -0.132 each, the one step you asked for, toward the target. And the sharing
ramp still pays out, but now ONLY in the right row: a neighbour at 0.4 (also tiles
A0,B1) sees worth(0.4, right) drop to -1.564 in full; a spot at 0.1 (tiles A0,B0)
shares only A0, so worth(0.1, right) slips from -0.5 + 0.0 = -0.5 to -0.632 + 0.0 =
-0.632; and worth(anything, left) and worth(anything, coast) do not budge. The
lesson spread across nearby SPOTS but stayed inside the move it was about.
The next footstep of the same drive. The table is exactly as drawn
above (right row [-0.632, -1.0, 0.0, -0.932, 0.0]; left and coast rows unchanged).
At 0.6 the car pushes RIGHT as decided; the world fines it -1 and rolls it to 0.9
(tiles A1, B2). At 0.9 the spinner stays greedy. size 0.1, dilute 0.9. What is the
next move, the target, the miss, and the two new weights?
CHECK: at 0.9: left -3.0+0 = -3.0, coast -2.0+0 = -2.0, right -1.0+0 = -1.0
-> next move = right (least negative)
target = -1 + 0.9 x (-1.0) = -1.9
worth(0.6, right) is NOW -1.0 + (-0.932) = -1.932 (B1 moved above!)
how wrong = -1.9 - (-1.932) = +0.032 -- a small PLUS: the old guess
was a touch too gloomy, so the crawl nudges it back UP
each lit tile of (0.6, right): +0.1 x 0.032 = +0.0032
w[right][A1] = -1.0 + 0.0032 = -0.9968
w[right][B1] = -0.932 + 0.0032 = -0.9288
AND AT THE FLAG THERE IS NO NEXT MOVE -- THE ANCHOR
The episode ends when the car tops the hill. There is no next spot, so no next
move, so the "dilute x worth(next, next move)" piece has nothing to point at. Drop
it. The target becomes the reward alone -- the anchor, the one target with no guess
inside it:
target = reward alone
how wrong = reward - worth(this spot, this move)
Every escape pins the worths of the last push to the bare reward, and that truth
then crawls backward, footstep by footstep, into the pushes that led there.
WHY THIS IS CALLED "ON-POLICY" -- AND WHERE Q-LEARNING WOULD DIFFER
Look again at the target: it used worth(0.6, RIGHT) because right is the move the
car will actually push next -- the move its own spinner-and-rank habit handed it.
It grades each push against the habit it really follows, wander included. That is
what ON-POLICY means: the worths it learns are the worths of the policy it is
actually running, jitter and all.
Two sibling machines differ by one peek. Swap "the move actually taken next" for
the BEST next worth --
Sarsa : target = reward + dilute x worth(next, the move actually taken next)
Q-learning: target = reward + dilute x max over moves of worth(next, move)
-- and you are learning the worths of a car that always plays perfectly, even
while this car is still wandering (that is OFF-policy). Same tiles, same table,
same nudge; the only change is which next worth you reach for. (A third sibling,
Expected Sarsa, reaches for the odds-weighted average of the next worths --
another single swap.)
EPISODE, MOVE BY MOVE -- THREE HANDLES AND TWO STICKY NOTES
The world runs the drive by calling three handles, and between calls the car
remembers exactly two things -- call them the sticky notes: the lit tiles of the
spot it stood on, and the push it made there.
START(spot) : read the spot's tiles, pick a push (spinner-and-rank),
write BOTH on the sticky notes, hand the push back.
STEP(reward, spot) : read the NEW spot's tiles, pick the NEXT push,
nudge the sticky-note pair toward
reward + dilute x worth(new tiles, next push),
then OVERWRITE the notes with the new pair, hand it back.
END(reward) : nudge the sticky-note pair toward the bare reward. Stop.
On Mountain Car the world pays -1 every single step until the car escapes, so
EVERY worth is deeply negative -- a stand-in for how many -1's still lie between
here and freedom -- and less-negative means closer to free. Pushing toward the
hill when too slow only stalls, so at first the car flails and every worth sinks.
But the anchor leaks the truth backward, the tiles share it across near-identical
spots, and the greedy pick slowly bends into the only thing that works: push WITH
the motion to pump the swing higher each pass, until one rock carries it over.
LEAST NEGATIVE WINS, AND THREE MORE LESSONS THE CLIFF CHARGED FOR
"-4.5 is the biggest number here, so left wins." All the worths are negative, and
my eye kept grabbing the longest bar. But at 0.3 the worths are -4.5, -2.5, -1.3,
and the fines-still-to-come reading says -1.3 means "about one fine left" while
-4.5 means "about four and a half" -- so -1.3 is the GOOD one. With all-negative
worths, greedy means LEAST negative. Read worths as distances-to-freedom, not
sizes.
"The target should use the BEST next worth -- surely I grade against perfection."
Suppose at 0.6 the spinner HAD called a wander and handed the car LEFT (worth
-5.5). Sarsa's target would truly be -1 + 0.9 x (-5.5) = -5.95 -- not the greedy
-2.62 -- because the car really is about to push left, and honest grading counts
it. Use the max instead and you have quietly built the other machine (Q-learning).
The second A in SARSA is the move you actually make. The wander belongs in the
target.
"I nudged the pair I am standing on." The fresh spot is the one in my hand, so I
graded it -- but the reward -1 was paid for the push OUT of 0.3, the sticky-note
pair (0.3, right). Nudging (0.6, right) instead writes the fine onto a push that
has not been graded yet and leaves the guilty one untouched. The nudge always
lands on the sticky notes; the fresh pair only feeds the target.
"I forgot to overwrite the sticky notes," and every step kept nudging the SAME
first pair. Without the overwrite, footstep two nudges (0.3, right) again --
0.1 x (its new miss) onto tiles A0, B1 -- while (0.6, right), the pair that
actually just acted, never learns at all. One line of bookkeeping, and skipping it
makes the whole drive teach a single pair. Nudge first, THEN slide: the new tiles
and the new push become the notes before the world is answered.
SEAM. Pencil ends here; below, the same numbers in Python.
dilute, alpha, T = 0.9, 0.2, 2
size = alpha / T # 0.2/2 = 0.1
# weights[move][tile]: move 0=left 1=coast 2=right; tile A0=0 A1=1 B0=2 B1=3 B2=4
w = [
[-2.0, -3.0, 0.0, -2.5, 0.0], # left
[-1.0, -2.0, 0.0, -1.5, 0.0], # coast
[-0.5, -1.0, 0.0, -0.8, 0.0], # right
]
# ruler A: A0=[0,0.5) -> idx 0, A1=[0.5,1.0) -> idx 1
# ruler B: B0=[-0.25,0.25) -> idx 2, B1=[0.25,0.75) -> idx 3, B2=[0.75,1.25) -> idx 4
def tA(pos):
return 0 if pos < 0.5 else 1
def tB(pos):
return 2 if pos < 0.25 else (3 if pos < 0.75 else 4)
def worth(pos, move):
return w[move][tA(pos)] + w[move][tB(pos)]
# initial worths at 0.3 (tiles A0, B1)
print(worth(0.3, 0), worth(0.3, 1), worth(0.3, 2)) # -4.5 -2.5 -1.3
# worths at 0.9 (tiles A1, B2) -- YOUR TURN check
print(worth(0.9, 0), worth(0.9, 1), worth(0.9, 2)) # -3.0 -2.0 -1.0
# worths at 0.6 (tiles A1, B1) -- used in Sarsa target
print(worth(0.6, 0), worth(0.6, 1), worth(0.6, 2)) # -5.5 -3.5 -1.8
# Sarsa step 1: leave (0.3, right), reward=-1, land 0.6, next=right
w_left = worth(0.3, 2) # -0.5+(-0.8) = -1.3
w_next = worth(0.6, 2) # -1.0+(-0.8) = -1.8
target = -1 + dilute * w_next # -1 + 0.9*(-1.8) = -2.62
how_wrong = target - w_left # -2.62-(-1.3) = -1.32
w[2][tA(0.3)] += size * how_wrong # w[right][A0]: -0.5+0.1*(-1.32) = -0.632
w[2][tB(0.3)] += size * how_wrong # w[right][B1]: -0.8+0.1*(-1.32) = -0.932
print(target, how_wrong) # -2.62 -1.32
print(w[2][0], w[2][3]) # -0.632 -0.932
# fallout: neighbour 0.4 (A0+B1 both moved), 0.1 (A0 only)
print(worth(0.4, 2)) # -0.632+(-0.932) = -1.564
print(worth(0.1, 2)) # -0.632+0.0 = -0.632
# YOUR TURN step: leave (0.6, right), reward=-1, land 0.9, next=right
w_left2 = worth(0.6, 2) # -1.0+(-0.932) = -1.932 (B1 moved above)
w_next2 = worth(0.9, 2) # -1.0+0.0 = -1.0
target2 = -1 + dilute * w_next2 # -1+0.9*(-1.0) = -1.9
how_wrong2 = target2 - w_left2 # -1.9-(-1.932) = +0.032
w[2][tA(0.6)] += size * how_wrong2 # w[right][A1]: -1.0+0.1*(0.032) = -0.9968
w[2][tB(0.6)] += size * how_wrong2 # w[right][B1]: -0.932+0.1*(0.032) = -0.9288
print(target2, round(how_wrong2, 6)) # -1.9 0.032
print(round(w[2][1], 4), round(w[2][3], 4)) # -0.9968 -0.9288
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 14 -- Function Approximation):
Part 1 -- State Aggregation by Pencil .
Part 2 -- Tile Coding by Pencil .
Part 3 (this post) .
Part 4 -- A Q-Network by Pencil
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================