==============================================================================================
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 4 OF 4
A Clock for Curiosity: Dyna-Q+ by Pencil
============================================================================================
A spot = one place in a small
world where you can stand. A move / arrow = a direction you pick there (four: up,
left, down, right). A reward = a number the world pays on a move. A worth = a number
saying how much reward you expect to gather from a choice onward, kept in a table --
one cell q[spot][move] per stand-here-pick-this, all starting at 0. A cell is fixed
by the crawl rule: slide it 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 )
with size the crawl fraction (say 0.1) and dilute the future-shrinker (1.0 = the
future counts in full). On top of that sits a NOTEBOOK (the textbook's "model"): a
page per spot, a line per move, each line holding the (landing, reward) that move
once produced. A REHEARSAL is a free correction: pick a remembered (spot, move) at
random, read its stored pair, run the same crawl -- no real footstep spent. That
machine -- correct, record, rehearse -- is Dyna-Q.
Dyna-Q has one blind spot. Once it finds a decent path, it stops poking around -- it
keeps walking the route it already trusts. If the world then CHANGES -- a wall falls
and a brand-new shortcut opens -- Dyna-Q never notices, because it has no reason to
wander back toward the spots it long ago wrote off.
WHICH NEEDS A WAY TO MAKE STALE MOVES TEMPTING AGAIN: A CLOCK
Add a third piece of paper -- a clock sheet. One number per (spot, move), the same
shape as the worth table, all starting at 0. Each clock counts the turns since that
move was last actually walked in the real world:
clock tau[spot][move] = turns since this move was last REALLY taken
Two rules keep it ticking:
every turn : every move's clock ticks up by 1
the move you just
really walked : its clock resets to 0
So a move you took a moment ago has a tiny clock; a move you have not touched in
ages has a big one. Drawn, one turn in which you really walk spot 7's "right":
BEFORE this turn: tau[7][right] = 5 tau[7][up] = 40 tau[3][down] = 12
tick every clock +1, then reset the one you walked:
AFTER: tau[7][right] = 0 tau[7][up] = 41 tau[3][down] = 13
The clock measures staleness -- exactly the thing Dyna-Q ignores.
One turn of clock-keeping. The sheet reads tau[5][left] = 24,
tau[5][right] = 3, tau[8][up] = 99, and this turn you really walk (5, right).
What do the three clocks say after?
CHECK: tick all three: 25, 4, 100. Reset only the walked one:
tau[5][left] = 25 , tau[5][right] = 0 , tau[8][up] = 100
SO TURN STALENESS INTO A FAKE REWARD: THE BONUS
During a rehearsal ONLY (never a real move), a recalled move gets a small fake
reward for being stale, on top of the real reward the notebook stored. The staler
the move, the bigger the fake bonus:
bonus = kappa x sqrt( tau[spot][move] )
target = ( reward + bonus ) + dilute x ( best worth at the landing )
Here kappa is a tiny knob (say 0.001) that sets how strong curiosity is, and the
square root keeps a huge clock from exploding the bonus. Worked, a recalled move
whose stored reward is 1, untried for tau = 9 turns, kappa = 0.001:
bonus = 0.001 x sqrt(9) = 0.001 x 3 = 0.003
target = ( 1 + 0.003 ) + dilute x peek = 1.003 + dilute x peek
Tiny at tau = 9. But the bonus grows with the square root of the clock, so a move
left untried far longer gets a real push -- at tau = 2500, sqrt(2500) = 50, and the
bonus is 0.001 x 50 = 0.05, fifty times larger. Rehearsing that stale move again and
again pumps its worth up, until the chooser -- which picks the biggest worth in the
row -- finally re-tries it in the real world. That real re-try is when a newly
opened shortcut gets discovered.
One rehearsal with the bonus. A recalled move stored (landing, reward)
where the reward is -1; its clock reads tau = 100; kappa = 0.001; the landing's best
worth is 2; dilute = 1.0; the cell being fixed holds 0; size = 0.1. Compute the
bonus, the target, and the new cell.
CHECK: bonus = 0.001 x sqrt(100) = 0.001 x 10 = 0.01
target = ( -1 + 0.01 ) + 1.0 x 2 = -0.99 + 2 = 1.01
cell = 0 + 0.1 x ( 1.01 - 0 ) = 0.101
BUT A NEVER-TRIED MOVE HAS NO NOTEBOOK LINE TO REHEARSE
The bonus only helps moves the notebook remembers. A move never tried has no line,
so a rehearsal can never pick it, so curiosity can never reach it. The fix: the
first time you ever visit a spot, record ALL of its moves at once -- the one you
really took with its real result, and the others as harmless placeholders that just
say "this move leads back here for reward 0":
first visit to spot 0, arrow 2 really taken (landed 0, reward 1):
model[0] = { 2 -> (0, 1), <- the real one: arrow 2's true landing + reward
0 -> (0, 0), -.
1 -> (0, 0), | placeholders: back to spot 0, reward 0
3 -> (0, 0) } -'
Now the notebook has a line for every move at spot 0, even the three never walked.
A rehearsal can grab one of those placeholders, find its clock ticking up turn after
turn (it is never reset, because it is never really walked), and pile the growing
stale-bonus onto it -- until the chooser re-tries it for real. Without the
placeholders, an untried move stays invisible to curiosity forever.
WHY THE SQUARE ROOT -- NOT tau ITSELF, NOT ITS LOGARITHM
The bonus was kappa x sqrt(tau): kappa the tiny curiosity knob (0.001 here), tau the
turns since a move was last really walked. Why a square root? Line up the three
obvious "grows with staleness" shapes at a spread of clocks and read off what each
does. kappa = 0.001:
tau 1 4 25 100 2500
----------- ---- ---- ---- ----- ------
tau itself 1 4 25 100 2500 x kappa -> up to 2.5
sqrt(tau) 1 2 5 10 50 x kappa -> up to 0.05
log(tau) 0.0 1.4 3.2 4.6 7.8 x kappa -> up to 0.008
Now weigh each against a real reward of about 1:
tau itself : bonus reaches 2.5 -- it DWARFS the reward. The agent ditches a good
path to re-check anything slightly old. It thrashes.
log(tau) : bonus reaches 0.008 -- it FLATTENS. A move untried for 2500 turns
barely twitches, so a shortcut that opened long ago is never re-found.
sqrt(tau) : bonus reaches 0.05 -- it keeps GROWING (so any move, however stale,
eventually earns a push big enough to re-try) yet stays well under a
real reward of 1 (so it never swamps the true signal).
Drawn, the three from the same start:
bonus
| . tau (explodes -- swamps the real reward)
| .
| . ____ sqrt(tau) (grows, but gently)
| . ____/
| . ___----/ . . . . . . . log(tau) (flattens -- stale moves ignored)
+------------------------------------- tau
The square root is the only one of the three that does BOTH: unbounded (every stale
move is re-checked some day) and sub-linear (it never drowns the real rewards). The
deeper reason it is a ROOT: how SURE you are of a stored value fades like
1 / sqrt(turns-since-checked), so how UNSURE you are -- which is what the bonus pays
for -- grows like sqrt(turns-since-checked). The bonus is a confidence-width. (The
bandit post on this blog meets the same square root under the name UCB; nothing from
there is needed here.)
DAY THE WALL FALLS: WHAT EACH MACHINE ACTUALLY DOES
Here is the experiment that shows the whole point, drawn. A grid world, start S,
goal G, a wall (#) with one gap at its far LEFT. Each move pays 0 except reaching G,
which pays +1 and restarts the walk at S. For the first 3000 turns the world looks
like the left picture; from turn 3000 on, a second gap quietly opens at the far
RIGHT -- a shortcut:
first 3000 turns: from turn 3000 on:
. . . . . . . . G . . . . . . . . G
. # # # # # # # # . # # # # # # # . <- gap opens here
. . . . . . . . . . . . . . . . . .
. . . . S . . . . . . . . S . . . .
Count the two routes on the picture. The long way -- left to the old gap, up, then
all the way right along the top -- is 15 steps from S to G. The new shortcut -- right
and straight up through the fresh gap -- is 7 steps.
Both machines learn the 15-step route in the first 3000 turns. Then:
Dyna-Q : keeps walking the 15-step route to the end of the experiment. Its
worths say the right side is a dead end -- written back when that was
TRUE. The odd 10% wander does poke that way, but one lucky step barely
lifts one cell, and the next greedy pick goes back the old way -- the
discovery cannot hold.
Dyna-Q+ : the never-walked cells near the right gap have clocks in the
thousands. At tau = 2500 the bonus is 0.001 x 50 = 0.05, and rehearsals
keep pumping those worths until the chooser re-tries the right side for
real -- and finds the 7-step way.
Seen as total reward collected over time, the two curves split at the change:
total reward
| _/ Dyna-Q+ (a goal every 7 steps
| ______/ after re-discovery)
| ____-----/
| ____-----/ ......... Dyna-Q (still a goal every 15 steps)
|____-----/ . . . . . . ...
+--------------------|--------------------- turns
turn 3000
The price is honest: in a world that never changes, Dyna-Q+ wastes a few real moves
re-checking paths that are exactly as dead as remembered, and its curve sits a hair
below Dyna-Q's. The bonus buys insurance, and insurance costs a premium.
BONUS LIVES IN IMAGINATION ONLY, AND THREE MORE BURNS THAT TAUGHT ME
"A bonus is a bonus" -- so I added it to real moves too. The damage showed up as
one number: a real move paying 1 with tau = 9 got taught as 1.003, and the crawl's
resting point (where size x (target - q) = 0) moved to 1.003 with it -- a permanent
lie of 0.003, growing with every clock. The bonus lives in the imagination only.
Real target: reward + dilute x peek. Rehearsal target: (reward + kappa x sqrt(tau))
+ dilute x peek. Two different lines, never merged.
"Reset the walked move's clock, then tick everything." That order leaves the move
you JUST walked at tau = 1, not 0 -- so the freshest move in the world already
earns a bonus of 0.001 x sqrt(1) = 0.001, and every move you walk, forever after,
reads 1 at its freshest instead of 0. Tick every clock +1 first, THEN reset the one
move actually walked to 0.
"I rehearsed (3, down) fifty times, surely its clock resets." Follow that belief to
its end: if rehearsals reset clocks, a much-rehearsed move would keep tau ~ 0,
bonus ~ 0 -- and the exact moves curiosity most needs to chase are the ones it
would silence. Rehearsing (3, down) fifty times leaves tau[3][down] exactly where
feet left it. Clocks obey FEET only. Paper corrections never touch them.
"The bonus will find the new shortcut by itself." I waited; it never did, and the
reason was structural: the never-walked move had no notebook line, so the rehearsal
lottery could not even name it -- no line, no rehearsal, no bonus, no matter how
big its clock grew. On the FIRST visit to a spot, file all four moves -- the real
one plus three back-to-here-reward-0 placeholders -- so curiosity has a line to
grab.
CHAPTER MAP, ONE LINE EACH
Four posts, one thread -- learn a worth from a sample, then squeeze more from
memory:
TD(0) : worth per SPOT, corrected from one real sample (no die)
Q-learning : worth per (spot, move); target peeks the MAX of the landing's row
Expected Sarsa : same, but the peek is the AVERAGE weighted by pick-odds (honest)
Dyna-Q : + a notebook + rehearsal -- free imaginary corrections from memory
Dyna-Q+ : + a clock + a stale-bonus -- re-tries old moves, finds new shortcuts
And the deeper split: a model-based machine (Dyna) learns faster per real footstep
than a model-free one (Q-learning alone) -- but only as far as its notebook is true.
SEAM. Pencil ends here; below, the same numbers in Python.
No loops, no functions -- one clock update, the bonus at two staleness levels,
the YOUR TURN rehearsal, and the sqrt vs log vs tau table. Per rehearsal:
1 sqrt, 1 multiply (bonus), 1 add, 1 max, 1 add (target), 4 strokes.
import math
kappa, size, dilute = 0.001, 0.1, 1.0
# CLOCK UPDATE: tick all +1, reset walked move
tau = {(7,'right'): 5, (7,'up'): 40, (3,'down'): 12}
for k in tau: tau[k] += 1 # every clock up 1
tau[(7,'right')] = 0 # walked -> reset to 0
# tau = {(7,'right'):0, (7,'up'):41, (3,'down'):13}
# YOUR TURN clock: start {(5,'left'):24, (5,'right'):3, (8,'up'):99}
tau2 = {(5,'left'):24, (5,'right'):3, (8,'up'):99}
for k in tau2: tau2[k] += 1
tau2[(5,'right')] = 0
print(tau2) # {(5,'left'):25, (5,'right'):0, (8,'up'):100}
# BONUS at tau=9 and tau=100 (kappa=0.001)
bonus9 = kappa * math.sqrt(9) # 0.001*3 = 0.003
bonus100 = kappa * math.sqrt(100) # 0.001*10 = 0.01
print(bonus9, bonus100) # 0.003 0.01
# YOUR TURN rehearsal: tau=100, reward=-1, landing best=2, old cell=0
target = (-1 + bonus100) + dilute * 2 # -0.99 + 2 = 1.01
cell = 0 + size * (target - 0) # 0.1 * 1.01 = 0.101
print(target, cell) # 1.01 0.101
# SQRT vs LOG vs TAU table (kappa=0.001, natural log)
for tv in [1, 4, 25, 100, 2500]:
lv = math.log(tv) if tv > 1 else 0.0
print(tv, tv*kappa, math.sqrt(tv)*kappa, round(lv*kappa,4))
# 1 0.001 0.001 0.0
# 4 0.004 0.002 0.0014
# 25 0.025 0.005 0.0032
# 100 0.1 0.01 0.0046
# 2500 2.5 0.05 0.0078
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 13 -- Sample-based Learning):
Part 1 -- TD(0) Built by Pencil .
Part 2 -- Q-Learning and Expected Sarsa .
Part 3 -- Dyna-Q by Pencil .
Part 4 (this post) .
Reference -- The Sample-based Map
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================