==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 13 . SAMPLE-BASED LEARNING . PART 2 OF 4
Max or Honest Average: Q-Learning and Expected Sarsa by Pencil
============================================================================================
Here is the whole game, from a blank sheet. There is a tiny world of three places you
can stand -- call each one a spot. At every spot you can walk one of four directions --
call each a move. When you make a move, the world pays you a number -- the reward --
and drops you on a new spot. Drawn:
move0 (up)
^
move1 | move3 three spots: [ spot0 ] [ spot1 ] [ spot2 ]
(left)<-+->(right) at each spot, the same four moves are on offer
v
move2 (down)
One job exists in two strengths. The gentle version: someone HANDS you a plan (an
arrow drawn at every spot) and you only grade it -- fill in, for each spot, how much
reward following the arrows from there will gather. One number per spot is enough for
that. (The previous post in this chapter does exactly that, but nothing from it is
needed here -- this page rebuilds everything it uses.)
The hard version -- this post -- is that NOBODY hands you the arrows. You must FIND
the best move at every spot, by walking, getting paid, and writing down what you
learn. And that breaks the one-number-per-spot bookkeeping immediately: a spot is not
good or bad on its own -- it depends on which move you pick there. You need a worth
per spot AND per move. A worth = a number saying how much reward you expect to gather
from that choice onward.
WHICH FORCES A TABLE, NOT A ROW: ONE WORTH PER (SPOT, MOVE)
Grading a handed plan needs one number per spot -- a row:
spot: 0 1 2
V [ 0 , 0 , 0 ]
Finding a plan needs one number per spot AND per move -- a table. Three spots, four
moves: 12 numbers, all starting at the lie of 0 (a guess written before any evidence):
move0 move1 move2 move3
spot0 [ 0 , 0 , 0 , 0 ]
spot1 [ 0 , 0 , 0 , 0 ]
spot2 [ 0 , 0 , 0 , 0 ]
Call this table q. One cell is one (spot, move) worth:
q[0][1] = the worth of: stand at spot 0, pick move 1
q[spot] = a whole ROW = the four move-worths at that spot
This table is the machine's ENTIRE memory. No diary of past rewards, no list of
visited spots -- twelve numbers, nothing else. (The full-size version of this game is
a 4x12 cliff grid, drawn near the end of this post -- 48 spots x 4 moves = 192 cells.
The 3-spot world keeps every number checkable by pencil.)
SO HOW DO YOU PICK A MOVE? MOSTLY THE BIGGEST, SOMETIMES A WANDER
At a spot you read its row of four worths and pick the biggest -- the greedy move.
But always picking the biggest known worth locks you onto a decent-but-maybe-not-best
move, and you may never discover better. Pure greed freezes on the first thing that pays;
a little randomness keeps you looking. So before each pick, roll a number between
0 and 1 on a fair spinner:
0 0.1 1
|--- wander ------|------------- greedy ----------------|
roll < 0.1 --> pick a move at RANDOM, all four equally likely
roll >= 0.1 --> pick the biggest worth in the row
That 0.1 is epsilon -- the wander share. Note the order of operations: the spinner is
rolled FIRST, blind; only the greedy branch reads the row. "Biggest in the row" hands
back the INDEX of the largest worth (ties broken by a fair pick among the tied).
NUDGE: FIX THE MOVE YOU JUST MADE
You stood at a spot (call it `prev`), picked a move (call it `move`), got paid a
reward, and landed on a new spot (call it `landing`). Drawn:
q[prev][move] --(reward)--> landing
(we fix THIS cell) (we only READ its row)
You fix the worth of the move you JUST MADE -- the cell q[prev][move] -- by the crawl
rule: move the old number a fraction `size` of the way toward a target,
q[prev][move] = q[prev][move] + size x ( target - q[prev][move] )
where size is the crawl fraction (0.1 here: take 10% of the gap each time, so one
loud lucky sample cannot overwrite everything) and the target is a NUMBER -- an
estimate of what the cell should have said, built from what just happened:
target = reward + dilute x ( future worth read at the landing )
Here dilute is the future-shrinker (1.0 here: the future counts at full weight;
0.9 would mean each step into the future counts 10% less). Everything above is one
machine. The whole remaining question is the last piece -- the "future worth read at
the landing" -- and it is the ONE place the two machines in the title split.
FORK: A DREAMED MAX, OR AN HONEST AVERAGE
The landing has a whole row of four move-worths. What single number stands for "the
future from here"? Two answers, and that is the entire difference between the two
machines:
Q-LEARNING future = the BIGGEST worth in the landing's row (max)
-- dreams you will play the best move next.
EXPECTED SARSA future = the AVERAGE worth in the landing's row,
weighted by how often you would actually pick each move
-- honest that you wander 10% of the time.
Q-learning is optimistic: it assumes the next move is the best one. Expected Sarsa
is honest: it knows the spinner will send it wandering 10% of the time, so it
averages the row by the real pick-odds. Same nudge, same size, same target shape --
only this "future" number differs. Now both, by hand, on the same trace.
Q-LEARNING BY HAND -- THE MAX
size (the crawl fraction) = 0.1, dilute (the future-shrinker) = 1.0.
World contract for this trace:
from spot 0, move 1 -> reward +2, land at spot 1
from spot 1, move 3 -> reward 0, land at spot 0
Table starts all 0:
move0 move1 move2 move3
spot0 [ 0 , 0 , 0 , 0 ]
spot1 [ 0 , 0 , 0 , 0 ]
spot2 [ 0 , 0 , 0 , 0 ]
Stand at spot 0, pick move 1. So prev = 0, move = 1.
FIRST MOVE -- reward 2 (from the contract above), land at spot 1. The landing's row is q[1] = [0,0,0,0], so its
biggest is 0:
target = reward + dilute x max(q[1])
= 2 + 1.0 x 0 = 2
q[0][1] = 0 + 0.1 x ( 2 - 0 ) = 0.1 x 2 = 0.2
The table now:
spot0 [ 0 , 0.2 , 0 , 0 ]
spot1 [ 0 , 0 , 0 , 0 ]
spot2 [ 0 , 0 , 0 , 0 ]
Now stand at spot 1, pick move 3. So prev = 1, move = 3.
SECOND MOVE -- reward 0, land at spot 0. The landing's row is q[0] = [0, 0.2, 0, 0],
so its biggest is 0.2:
target = reward + dilute x max(q[0])
= 0 + 1.0 x 0.2 = 0.2
q[1][3] = 0 + 0.1 x ( 0.2 - 0 ) = 0.1 x 0.2 = 0.02
The table now:
spot0 [ 0 , 0.2 , 0 , 0 ]
spot1 [ 0 , 0 , 0 , 0.02 ]
spot2 [ 0 , 0 , 0 , 0 ]
The +2 reward that spot 0's move 1 earned has begun crawling backward: spot 1's
move 3 now knows that move leads somewhere worth 0.2.
The third move. The table is exactly as drawn above. You stand at
spot 0 and pick move 1 again (prev = 0, move = 1); the world pays reward 2 and drops
you on spot 1 again. With size 0.1 and dilute 1.0: what is the target, and what does
the cell q[0][1] (currently 0.2) become? Do it on your slate before reading on.
CHECK: the landing's row is q[1] = [0, 0, 0, 0.02], so its biggest is 0.02.
target = 2 + 1.0 x 0.02 = 2.02
q[0][1] = 0.2 + 0.1 x ( 2.02 - 0.2 ) = 0.2 + 0.1 x 1.82 = 0.2 + 0.182 = 0.382
EXPECTED SARSA BY HAND -- THE SAME TRACE, ONLY THE FUTURE CHANGES
Same world, same trace, size 0.1, dilute 1.0, table reset to all 0. The only swap:
the "future read at the landing" is now the weighted average of the row, not its max.
The weights are the real pick-odds at the landing -- the spinner rule from the top of
this post (roll < 0.1 wander over ALL FOUR moves equally; otherwise take the biggest
in the row). With epsilon = 0.1 and 4 moves, every move gets a base share of
epsilon/4 = 0.1/4 = 0.025 from the wander, and the greedy move (the biggest in the
row) gets an extra 1 - epsilon = 0.9 on top. Drawn as a bar of odds:
move0 |=| 0.025
move1 |=====================================| 0.925 <- greedy: 0.9 + 0.025
move2 |=| 0.025
move3 |=| 0.025 check: 0.925 + 3 x 0.025 = 1.000
FIRST MOVE -- prev = 0, move = 1, reward 2, land at spot 1. Row q[1] = [0,0,0,0]:
every worth is 0, so the weighted average is 0 whatever the weights:
target = reward + dilute x 0 = 2 + 0 = 2
q[0][1] = 0 + 0.1 x ( 2 - 0 ) = 0.2
Same as Q-learning here, because an all-zero row has the same max and average.
SECOND MOVE -- prev = 1, move = 3, reward 0, land at spot 0. Row q[0] = [0, 0.2, 0, 0].
The biggest is move 1's 0.2, so move 1 is greedy and weighs 0.925; the others weigh
0.025 each:
average = 0.925 x 0.2 + 0.025 x 0 + 0.025 x 0 + 0.025 x 0
= 0.185 + 0 + 0 + 0
= 0.185
target = reward + dilute x 0.185 = 0 + 0.185 = 0.185
q[1][3] = 0 + 0.1 x ( 0.185 - 0 ) = 0.0185
The table now:
spot0 [ 0 , 0.2 , 0 , 0 ]
spot1 [ 0 , 0 , 0 , 0.0185 ]
spot2 [ 0 , 0 , 0 , 0 ]
Q-learning wrote 0.02 into that same cell; Expected Sarsa wrote 0.0185. The honest
average sits a touch lower than the dreamed max, because it mixes the best move's 0.2
with a small chance of the three zeros -- it does not assume you will always play
the best.
One fresh landing. You make a move that pays reward 0 and lands on a
spot whose row reads:
landing row [ 1 , 3 , 1 , 1 ] epsilon = 0.1, so weights: greedy 0.925,
^ biggest others 0.025 each
With dilute 1.0 and size 0.1, the cell being fixed currently holds 0. Compute the
weighted average, the target, and the new cell.
CHECK: average = 0.925 x 3 + 0.025 x 1 + 0.025 x 1 + 0.025 x 1
= 2.775 + 0.025 + 0.025 + 0.025 = 2.85
target = 0 + 1.0 x 2.85 = 2.85
new cell = 0 + 0.1 x ( 2.85 - 0 ) = 0.285
BUT THE GAME ENDS SOMETIMES: THE ANCHOR
Reach the goal and the game ENDS -- there is no landing to read a row from. Drawn:
q[prev][move] --(reward)--> [ GAME OVER -- no landing, no row, no future ]
So the future piece has nothing to grab. Drop it. The target becomes the reward
alone, and it is identical for both machines:
mid-game: target = reward + dilute x (future read at the landing)
game over: target = reward
q[prev][move] = q[prev][move] + size x ( reward - q[prev][move] )
This last update is the anchor: the one target with no guess inside it -- a plain
paid fact. Every other cell's worth is a guess leaning on a guess; the chain of
leaning ends here, which is what lets the whole table heal toward truth.
WHICH TABLE DO YOU END UP WITH? THE PEEK DECIDES
The peek at the landing is not just a number inside one update -- it decides WHICH
table the whole process settles on. Take one landing row where move 0 is great and
the other three are poor:
q[landing] = [ 10 , 2 , 2 , 2 ]
^move 0 great ^moves 1-3 poor
Q-learning's peek is the max, 10. It leans on the BEST move every single time, no
matter what you actually do next. So whatever wandering you behave with, the number
it keeps climbing toward is "the worth IF you always played the best move":
Q-learning peek = max = 10 -> learns the BEST-PLAY table
A third machine exists, plain Sarsa (no "Expected"): its peek is the worth of the
single move it really does take next -- it waits, sees its own next pick, and reads
that one cell. With the 10% wander over 4 moves, the greedy move 0 gets picked with
odds 0.9 + 0.1/4 = 0.925 and each poor move with 0.1/4 = 0.025 (three of them =
0.075 together). So over many visits plain Sarsa's peek averages out to:
0.925 x 10 + 0.075 x 2 = 9.25 + 0.15 = 9.4 -> learns the YOUR-ACTUAL-PLAY table
and Expected Sarsa computes that same 9.4 in ONE stroke -- it IS that average, taken
with a pencil instead of waited for. Drawn, the same landing, two futures leaned on:
Q-learning : always grabs the 10 -> 10.0 (dreams the perfect next move)
(Expected) Sarsa: weighs what you'll really do -> 9.4 (counts the 10% fumbles)
That 0.6 gap is the whole on-policy / off-policy split. Q-learning is OFF-policy:
the table it learns (best-play, worth 10) is NOT the wandering it follows -- it
learns perfect-play worths while behaving randomly. Sarsa, plain or Expected, is
ON-policy: it learns the worth of the very wandering it does, fumbles and all (9.4).
One landing row, both peeks. epsilon = 0.1, four moves:
q[landing] = [ 8 , 4 , 0 , 0 ]
What future does Q-learning lean on? What future does Expected Sarsa lean on?
CHECK: Q-learning: max = 8.
Expected Sarsa: greedy is move 0 (worth 8), weight 0.925; others 0.025 each:
0.925 x 8 + 0.025 x 4 + 0.025 x 0 + 0.025 x 0 = 7.4 + 0.1 + 0 + 0 = 7.5
The famous consequence lives on the full-size cliff world -- a 4x12 grid where each
step pays -1, and stepping on the cliff pays -100 and drags you back to the start:
. . . . . . . . . . . .
. . . . . . . . . . . . <- the SAFE path runs along this row
. . . . . . . . . . . . <- the SHORT path runs along this row
S C C C C C C C C C C G S = start, C = cliff (-100), G = goal
The shortest path hugs the cliff edge. Q-learning learns that the edge path is best
-- its peek dreams you never slip -- yet while wandering, 10% random moves sometimes
step it off the edge, and it keeps crashing as it learns. Sarsa's table COUNTS those
slips: the edge cells' worths come out below the row-above cells' worths, so Sarsa
walks the safe route. Same world, two honest answers: optimal-if-perfect
(Q-learning) vs best-for-who-you-actually-are (Sarsa).
FIVE WALLS: A TARGET THAT IS NOT A PLACE, A TABLE THAT IS NOT A DIARY
"The target is... a spot? an arrow? I think it is a reward." I asked this three
times, and the arithmetic feeds the confusion: the first target above came out 2,
and there IS a spot 2. One later number ended it. When the landing's best cell holds
2.02, the same move's target = 2 + 1.0 x 2.02 = 4.02 -- and no spot 4.02 exists. A
target is a worth, a number of reward-to-come; it could never name a place.
"Why would I update the spot I LEFT? I'm not there anymore." It felt like paying
rent on a house after moving out. So I tried writing the reward 2 somewhere else --
at the landing, q[1][?] -- and the question collapsed on its own: which move column?
You have made no move AT spot 1 yet. The reward 2 was paid FOR the jump out of spot
0 by move 1; exactly one cell earned it, and that cell is q[0][1]. A reward belongs
to the (spot, move) pair that caused it -- always the one just left.
"So the table remembers my history, right? Values are last-reward history?" Count
what exists after two moves: the whole machine is [0, 0.2, 0, 0 / 0, 0, 0, 0.02 /
0, 0, 0, 0] -- twelve numbers. Which spot you came from, what was paid when: gone.
The table IS the memory, all of it. Each cell is a running summary, not a diary;
the crawl (size 0.1) is what folds each new fact into the summary without keeping
the fact.
"The 10% wander picks among the three NON-greedy moves... so each gets 0.1/3." I
split the wander over the losers only. But the spinner is rolled BEFORE looking at
the row -- wander means all FOUR moves equally -- so greedy gets 0.9 + 0.025 =
0.925, not 0.9. On the row [0, 0.2, 0, 0] my broken weights gave an average of
0.9 x 0.2 = 0.18; the true one is 0.925 x 0.2 = 0.185. An error of 0.005: too small
to see in one update, and carried into every update whose landing row is not all
equal. Wander is blind. The greedy move also gets its wander share.
"Who even tells me the game ended? Maybe I didn't notice I reached the goal." Here
there was nothing to compute -- that was the answer. The WORLD announces the ending;
there is simply no landing spot in its message, and that announcement is what
switches the target from reward + dilute x future to reward alone. The ending is
the world's news, not your deduction; your only job on hearing it is to drop the
future piece.
SEAM. Pencil ends here; below, the same numbers in Python.
No loops, no functions -- Q-learning (3 moves) then Expected Sarsa (2 moves),
every number hard-coded. Per move: 1 max or weighted-sum, 1 add, 1 subtract,
1 multiply = 4 strokes.
size, dilute, eps = 0.1, 1.0, 0.1
q = [[0,0,0,0],[0,0,0,0],[0,0,0,0]] # q[spot][move], 3 spots x 4 moves, start 0
# Q-LEARNING move 1: prev=0 move=1 reward=2 land=1
future = max(q[1]) # max([0,0,0,0]) = 0
target = 2 + dilute * future # 2 + 1.0*0 = 2
q[0][1] = q[0][1] + size*(target - q[0][1]) # 0 + 0.1*(2-0) = 0.2
# move 2: prev=1 move=3 reward=0 land=0
future = max(q[0]) # max([0,0.2,0,0]) = 0.2
target = 0 + dilute * future # 0 + 1.0*0.2 = 0.2
q[1][3] = q[1][3] + size*(target - q[1][3]) # 0 + 0.1*(0.2-0) = 0.02
# move 3 (YOUR TURN): prev=0 move=1 reward=2 land=1
future = max(q[1]) # max([0,0,0,0.02]) = 0.02
target = 2 + dilute * future # 2 + 1.0*0.02 = 2.02
q[0][1] = q[0][1] + size*(target - q[0][1]) # 0.2 + 0.1*(2.02-0.2) = 0.382
print(q[0][1], q[1][3]) # 0.382 0.02
# EXPECTED SARSA: greedy weight 0.925, each other move 0.025
w_g, w_o = 1 - eps + eps/4, eps/4 # 0.925, 0.025
q2 = [[0,0,0,0],[0,0,0,0],[0,0,0,0]]
# move 1: row all-zero, avg = 0 whatever the weights
q2[0][1] = 0 + size*(2 - 0) # 0.2 (same as Q-learning)
# move 2: land=0, row [0,0.2,0,0], greedy=move1
avg = w_g*q2[0][1] + w_o*q2[0][0] + w_o*q2[0][2] + w_o*q2[0][3]
# = 0.925*0.2 + 3*0.025*0 = 0.185
q2[1][3] = 0 + size*(0 + dilute*avg - 0) # 0.1*0.185 = 0.0185
print(q2[0][1], q2[1][3]) # 0.2 0.0185
# YOUR TURN check: row [1,3,1,1] greedy=move1 (worth 3), reward=0, old cell=0
avg3 = w_g*3 + w_o*1 + w_o*1 + w_o*1 # 0.925*3 + 0.075 = 2.85
cell3 = 0 + size*(0 + dilute*avg3 - 0) # 0.1*2.85 = 0.285
print(cell3) # 0.285
# off-policy check: row [8,4,0,0]
print(max([8,4,0,0])) # Q-learning peek = 8
print(w_g*8 + w_o*4) # E-Sarsa peek = 7.5
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 13 -- Sample-based Learning):
Part 1 -- TD(0) Built by Pencil .
Part 2 (this post) .
Part 3 -- Dyna-Q .
Part 4 -- Dyna-Q+
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================