==============================================================================================
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 3 OF 4
A Notebook and a Rehearsal: Dyna-Q by Pencil
============================================================================================
A spot = one place in a small
world where you can stand. A move = a direction you pick there (four on offer: move0
up, move1 left, move2 down, move3 right). A reward = a number the world pays you on a
move. A worth = a number saying how much reward you expect to gather from a choice
onward. The worths live in a table q -- one cell q[spot][move] per stand-here-pick-
this, all starting at the lie of 0 -- and one cell gets fixed after each move by the
crawl rule: slide the old number a fraction `size` of the way toward a target,
q[spot][move] = q[spot][move] + size x ( target - q[spot][move] )
target = reward + dilute x ( best worth in the landing's row )
where size is the crawl fraction (small, like 0.1, so one loud sample cannot
overwrite everything) and dilute is the future-shrinker (1.0 = the future counts in
full). That machine -- fix one cell per real move -- is Q-learning, and its cost is
hidden in plain sight: EVERY correction costs a real footstep. Footsteps are slow,
and in a robot they are expensive. Dyna-Q squeezes far more learning out of each one
by remembering what the world did, then reliving those moves in its head.
WHICH MEANS A SECOND PIECE OF PAPER: A NOTEBOOK OF WHAT THE WORLD DID
Two papers now, side by side. The first is the worth table q. The second is new -- a
notebook (the textbook calls it the model):
PAPER A -- the worth table q[spot][move] : you CORRECT these (the crawl above)
PAPER B -- the notebook model[spot][move] : you RECORD facts of what the world did
After every real move, you jot one fact into the notebook: from this spot, this move
landed me there and paid that. Later, with no real move at all, you flip the notebook
open, pick a remembered move, and run the SAME crawl again -- a free correction
bought from memory instead of from a footstep.
REAL move: you -> world -> (landing, reward) -> jot it in the notebook
REHEARSAL: flip notebook -> relive an old (landing, reward) -> crawl a worth again
SO WHAT SHAPE IS THE NOTEBOOK? TWO LAYERS, DRAWN IN FULL
The notebook is a page per spot, and a line per move on that page. Each line holds a
PAIR -- where that move landed and what it paid:
model (the whole notebook)
+-----------------------------------------------------------+
| spot 7 --> page: { right -> (8, -1), up -> (7, -1) } | spot 7's page
| spot 3 --> page: { up -> (3, -1) } | spot 3's page
+-----------------------------------------------------------+
^ ^ ^
outer key inner key the answer
(the spot) (the move) (landing, reward)
Read it at two depths. The outer key is the spot -- it picks which PAGE. The inner
key is the move -- it picks which LINE on that page. The line holds a pair: the
landing AND the reward. (Keep BOTH. Drop the reward and a rehearsal has nothing to
crawl toward.)
It feels like a 2D table, model[spot][move], double-indexed. One difference, and it
is the whole reason for the guard below: a real 2D table has every slot waiting from
the start; this notebook holds only the moves you have actually tried, and grows:
a 2D table (every slot pre-made) the notebook (only what you lived)
up left down right spot 7 -> { right:(8,-1), up:(7,-1) }
0 . . . . spot 3 -> { up:(3,-1) }
1 . . . . (spots 0,1,2,4,... not here yet)
...
SO RECORDING IS PURE BOOKKEEPING -- BUT A FRESH PAGE DOES NOT EXIST YET
Writing a fact does no arithmetic at all. You are handed four numbers and you file
them: the spot you left, the move you took, where you landed, what it paid. No
worths, no crawl -- just write the line.
The one snag: the notebook starts empty. The first time you file under spot 7, page
7 does not exist yet, and you cannot write a line onto a missing page:
model = { }
model[7][right] = (8, -1) <- no page "7" yet -> error
So if the page is missing, start a blank page first, THEN write the line. Drawn,
starting from an empty notebook:
write (7, right -> 8, -1):
page 7 missing? yes -> model[7] = {} (start a blank page)
-> model[7][right] = (8,-1) (write the line)
model is now: { 7: { right:(8,-1) } }
write (7, up -> 7, -1): (a wall -- stayed put)
page 7 missing? no -> skip the blank-page start
-> model[7][up] = (7,-1) (a second line, same page)
model is now: { 7: { right:(8,-1), up:(7,-1) } }
Start the blank page ONLY when the page is missing. Do it every time and you wipe
the lines already written -- the guard is what protects spot 7's first line when its
second is filed.
SO NOW THE REHEARSAL: THE SAME CRAWL, FED BY MEMORY
A rehearsal is one correction with no real move. Four beats: grab a remembered spot
and a remembered move at random, read the pair the notebook stored there, then crawl
the worth -- the exact same nudge as a real move, only the reward and landing come
off the page instead of from the world:
(1) grab a remembered spot, then a remembered move on its page (two random picks)
(2) read the line -> (landing, reward)
(3) crawl q[spot][move] toward reward + dilute x (best worth at landing)
(4) the fork: did that remembered move end the game?
Beat 4 is the anchor rule. A move that ended the game has no landing to read a row
from -- the game was over -- so the notebook stored its landing as a dummy -1. On
reading a -1, drop the future piece:
landing is -1 (the move ended the game) : target = reward alone
otherwise (an ordinary landing) : target = reward + dilute x max(q[landing])
One rehearsal by hand. The notebook holds one line and the table is all 0:
model = { 3: { down -> (15, -1) } } q = all 0
size (crawl fraction) = 0.1 dilute (future-shrinker) = 1.0
grab: spot 3, move down
read: (landing 15, reward -1)
ended? landing is 15, not -1 -> ordinary, keep the future piece
peek: max(q[15]) = 0
target = reward + dilute x 0 = -1 + 0 = -1
q[3][down] = 0 + 0.1 x ( -1 - 0 ) = -0.1
No footstep was taken. The worth of "stand at spot 3, go down" moved from 0 to -0.1,
paid for entirely out of memory.
One rehearsal, one already-lit landing. The papers read:
model = { 2: { up -> (0, 3) } }
q[0] = [ 0.5 , 0 , 0 , 0 ] <- a real move earlier paid 5: 0 + 0.1 x 5 = 0.5
size = 0.1, dilute = 1.0 every other q cell = 0
Rehearse the one remembered move (2, up): what is the target, and what does q[2][up]
(currently 0) become?
CHECK: landing 0 is ordinary. peek = max(q[0]) = 0.5
target = 3 + 1.0 x 0.5 = 3.5
q[2][up] = 0 + 0.1 x ( 3.5 - 0 ) = 0.35
WHICH IS WHY IT WINS: THE GOAL'S REWARD SPREADS BACKWARD WITH NO FOOTSTEPS
One real footstep buys dozens of these free corrections, and -- the real prize -- a
reward spreads BACKWARD along remembered moves without walking them again. Watch it,
with size = 1 and dilute = 1 so the crawl jumps the whole way and the spread is
plain.
The notebook holds two remembered moves: from spot 0 going right landed on spot 1
for reward 0; from spot 1 going right ended the game (the goal) for reward 1:
model = { 0: { right -> (1, 0) }, 1: { right -> (-1, 1) } }
^^ -1 = ended the game
q starts all 0. Rehearse the goal move first:
rehearse (1, right): landing is -1 (ended) -> target = reward = 1
q[1][right] = 0 + 1 x ( 1 - 0 ) = 1
Now rehearse the earlier move, which lands on spot 1 -- whose best worth is now 1:
rehearse (0, right): landing 1 (ordinary) -> target = 0 + 1 x max(q[1]) = 0 + 1 = 1
q[0][right] = 0 + 1 x ( 1 - 0 ) = 1
The goal's +1 has crawled all the way back to spot 0 -- two cells lit up, zero real
footsteps. A machine with no notebook would have to physically walk that path twice
to spread the reward two spots back. Dyna-Q walks it once and rehearses the rest.
Stretch the chain one spot further. Add a third remembered move: from
spot 9, going right landed on spot 0 and paid 0. The papers now read:
model = { 0: { right -> (1, 0) }, 1: { right -> (-1, 1) }, 9: { right -> (0, 0) } }
q[0][right] = 1 , q[1][right] = 1 , everything else 0 , size = 1 , dilute = 1
Rehearse (9, right). What does q[9][right] become?
CHECK: landing 0 is ordinary. peek = max(q[0]) = 1
target = 0 + 1 x 1 = 1
q[9][right] = 0 + 1 x ( 1 - 0 ) = 1 -- the +1 is now THREE spots back, no footsteps
SO ONE REAL FOOTSTEP DOES SIX BEATS
Putting the real move and the rehearsals together, a single real footstep runs this
recipe:
(1) CORRECT the move you just made, from the world's fresh reward + landing
(2) RECORD that fact into the notebook
(3) REHEARSE: replay remembered facts, crawling worths again -- no world touched
(4) PICK the next arrow: roll a spinner from 0 to 1; under 0.1 take any of the
four moves at random (the wander), otherwise take the biggest worth in the row
(5) SLIDE the labels: the landing becomes the new "spot you left"
(6) hand the arrow back to the world
Beats 1 and 3 are the SAME crawl. The only difference is where the reward and
landing come from: beat 1 reads them off the world; beat 3 reads them off the
notebook. That is the whole trick -- imaginary corrections are real corrections, fed
by memory.
WHY A REHEARSAL EQUALS A REAL FOOTSTEP: SAME TARGET, SAME DESTINATION
A rehearsal feels like cheating -- you moved a worth without moving in the world.
Here is why it is honest. The notebook stored the very (landing, reward) the world
handed back, so a rehearsal runs the identical nudge with the identical numbers.
Watch one cell q[s][move], start 0. The world gave reward 1 onto a landing whose
best worth is 0; size 0.5, dilute 1.0. The target -- the number the nudge aims at:
target = reward + dilute x (best worth at landing) = 1 + 1.0 x 0 = 1.0
The real correction (numbers from the world):
q[s][move] = 0 + 0.5 x ( 1.0 - 0 ) = 0.5
Now rehearse the SAME move (read (landing, reward) back off the notebook -- still 1):
target = 1 + 1.0 x 0 = 1.0 (same numbers -> same target)
q[s][move] = 0.5 + 0.5 x ( 1.0 - 0.5 ) = 0.75
And once more:
q[s][move] = 0.75 + 0.5 x ( 1.0 - 0.75 ) = 0.875
Drawn, each correction -- real or rehearsed -- halves the gap to the SAME target 1.0:
0 ---> 0.5 ---> 0.75 ---> 0.875 ---> ... ---> 1.0
\real/ \reh/ \reh/ ^ target = reward + dilute x best-at-landing
every step, world or page, aims at the same 1.0
The target never moves: it is always reward + dilute x (best at landing), whether
those numbers came from the world or the page. So one rehearsal does exactly what
one more real visit would do -- the table cannot tell them apart. Rehearsals do not
change WHERE the worth lands (the resting point, where the nudge size x (target - q)
becomes 0, is q = target); they change only HOW FAST it gets there: many corrections
per footstep instead of one.
The one condition: the notebook must still be TRUE. If the world quietly changed and
a page is stale, every rehearsal now drags the worth toward a target that is no
longer real -- which is the exact hole the next post, Dyna-Q+, plugs.
NO NEW FORMULA, NO AIRLIFT, NO 48-PAGE NOTEBOOK -- WHAT I GOT WRONG FIRST
"So how is this machine even different from the last one?" I kept hunting for the
new update formula, and there isn't one. The real correction computed
0 + 0.5 x (1.0 - 0) = 0.5 and the rehearsal computed 0.5 + 0.5 x (1.0 - 0.5) = 0.75
-- the identical crawl, the identical target shape. Dyna-Q adds no new arithmetic.
It adds a notebook and a habit: after each real correction, run the same correction
a few more times from memory. The novelty is the SOURCE of the numbers, never the
formula.
"Rehearse a move? Did the world just airlift me to that spot?" A rehearsal names a
spot I am not standing on, and that felt like teleporting -- until I watched what
actually changed. The rehearsal of (3, down) above changed q[3][down] to -0.1 while
I stood somewhere else entirely, and nothing in the world moved. A rehearsal never
moves you. You are a clerk at a desk re-reading an old receipt; only the PENCIL
side (the worth table) changes, never your feet.
"The notebook looks like a 2D table, so every slot exists." Believing that, I
indexed a page that was never written and the machine fell over. After the two
writes above, the notebook holds exactly 2 pages (spots 7 and 3) -- not 48. Ask
page 5 for anything and there is no page 5. The notebook only holds what you lived.
Start a blank page only when the page is missing -- and never when it exists, or
the fresh blank wipes every line already on it.
"Won't I just bounce between two spots forever at the start?" All worths are 0, I
step right, step back left, and it looked like a loop with no exit. Then I let the
arithmetic run: in a world that pays -1 per step, the bounce writes
q = 0 + 0.1 x (-1 + 0 - 0) = -0.1 onto each bounced move; the next bounce writes
-0.19; the untried moves still sit at 0. The greedy pick reads the row, and -0.19
loses to 0 -- the bounce digs its own grave and the walk moves on. Bad loops punish
themselves in the table; you do not have to break them by hand.
SEAM. Pencil ends here; below, the same numbers in Python.
No loops, no functions -- one recording, one rehearsal on a lit landing, the two-
step backward spread, the YOUR TURN extension, and the convergence trace.
size, dilute = 0.1, 1.0
# RECORDING: spot=7 move='right' landing=8 reward=-1, then a second line
model = {}
if 7 not in model: model[7] = {} # page missing -> start blank page
model[7]['right'] = (8, -1)
if 7 not in model: model[7] = {} # page exists -> guard skips blank start
model[7]['up'] = (7, -1) # wall: stayed at 7
# model = {7: {'right':(8,-1), 'up':(7,-1)}}
# REHEARSAL: model={2:{'up':(0,3)}}, q[0]=[0.5,0,0,0], size=0.1, dilute=1.0
model2 = {2: {'up': (0, 3)}}
q = {0: [0.5,0,0,0], 2: [0,0,0,0]}
landing, reward = model2[2]['up'] # landing=0, reward=3
peek = max(q[landing]) # max([0.5,0,0,0]) = 0.5
target = reward + dilute * peek # 3 + 1.0*0.5 = 3.5
q[2][0] = q[2][0] + size*(target - q[2][0]) # 0 + 0.1*(3.5-0) = 0.35
print(q[2][0]) # 0.35
# BACKWARD SPREAD: size=1, dilute=1; goal reached from spot 1 right
size2 = 1.0
q2 = {0:[0,0,0,0], 1:[0,0,0,0], 9:[0,0,0,0]} # right = index 3
# rehearse (1, right): landing=-1 ended -> target = reward alone
q2[1][3] = q2[1][3] + size2*(1 - q2[1][3]) # 0 + 1*(1-0) = 1
# rehearse (0, right): landing=1 ordinary
peek2 = max(q2[1]) # max([0,0,0,1]) = 1
target2 = 0 + dilute * peek2 # 1
q2[0][3] = q2[0][3] + size2*(target2 - q2[0][3]) # 0 + 1*(1-0) = 1
print(q2[1][3], q2[0][3]) # 1.0 1.0
# YOUR TURN: spot 9 right lands on 0, reward 0
peek3 = max(q2[0]) # max([0,0,0,1]) = 1
target3 = 0 + dilute * peek3 # 1
q2[9][3] = 0 + size2*(target3 - 0) # 1
print(q2[9][3]) # 1.0
# WHY REHEARSAL = REAL STEP: same target, same convergence
size3, qc = 0.5, 0.0
qc = qc + size3*(1.0 - qc) # real step: 0 + 0.5*(1-0) = 0.5
qc = qc + size3*(1.0 - qc) # rehearsal 1: 0.5 + 0.5*(1-0.5) = 0.75
qc = qc + size3*(1.0 - qc) # rehearsal 2: 0.75+0.5*(1-0.75) = 0.875
print(qc) # 0.875
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 13 -- Sample-based Learning):
Part 1 -- TD(0) Built by Pencil .
Part 2 -- Q-Learning and Expected Sarsa .
Part 3 (this post) .
Part 4 -- Dyna-Q+
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================