==============================================================================================
RAHUL'S ML BLOG -- notes on machine learning, worked out by hand est. 2026
==============================================================================================
home | about | archive | glossary | contact
----------------------------------------------------------------------------------------------
CHAPTER 17 . TWO THE SAMPLE-BASED MAP SKIPPED . PART 2 OF 2
Fix the Biggest Surprise First: Priority Sweeping by Pencil
============================================================================================
Chapter 13 kept a second paper beside the worth-table -- a MODEL, a note of what each move once
produced (which spot it landed on, what reward it paid) -- and REHEARSED off it: grab a remembered
move, re-run its stored result as if it had just happened, and let the worth-table learn from the
memory with no real footstep. Grabbing those memories at RANDOM (that was Dyna-Q) wastes almost all
of them early on: a rehearsed move whose landing spot is still worth zero teaches nothing, because
the number it would copy back is zero. This post fixes the waste -- rehearse the move whose worth
would JUMP the most first, and chase that jump backward. That is priority sweeping.
A worth (write it V of a spot) is the total future reward expected from that spot. A model is a
lookup: for a move out of a spot, it hands back the spot you land on and the reward paid. Rehearse
= redo a stored move's result to refresh a worth, no real step taken. Everything here is that same
rehearsal, only chosen by size-of-change instead of at random.
SO DRAW A WORLD WHERE ONE REWARD HAS JUST BEEN FOUND AND MUST TRAVEL BACK
Four spots in a line, 1 to 4, then the GOAL. The only move is rightward; stepping right out of a
spot pays 0, except stepping out of spot 4 reaches the GOAL and pays +1. Fade far-off reward by a
dilute of 0.9 per step (Chapter 12's fade that keeps sums finite). Every worth starts at 0, and the
courier has just taken its first-ever real step out of 4 into the GOAL, so only that one move's
reward is known:
1 --0--> 2 --0--> 3 --0--> 4 --+1--> GOAL
V=0 V=0 V=0 V=0
A worth updates by the best move out of it: new V(spot) = reward + 0.9 x V(landing). The real step
out of 4 just paid +1 into the GOAL (a finished spot, worth 0), so spot 4's worth wants to become:
new V(4) = 1 + 0.9 x V(GOAL) = 1 + 0.9 x 0 = 1
WHICH MEANS THE THING WORTH REHEARSING IS THE ONE WHOSE WORTH WOULD MOVE MOST
Spot 4's worth would jump from 0 to 1. Call that jump its PRIORITY -- how far its worth would move
if you rehearsed it now: priority = | new V - old V |. For spot 4:
priority(4) = | 1 - 0 | = 1
Every other spot right now would move by 0: rehearsing spot 3 gives new V(3) = 0 + 0.9 x V(4) =
0.9 x 0 = 0, no jump, because 4 is still 0. So there is exactly one move worth doing, and a random
grab would most likely miss it. Keep a QUEUE that always hands back the biggest-priority spot first
(a max-heap -- picture a pile that keeps its largest number on top). Right now it holds one spot:
QUEUE (biggest priority on top):
spot 4 priority 1.0
----------------------
SO POP THE BIGGEST, APPLY IT, THEN WAKE WHOEVER LED INTO IT
Take the top of the queue, actually make its update, and then notice: the spot that just changed is
the LANDING for some earlier spot's move, and that earlier spot's worth now wants to move too. Those
earlier spots -- the PREDECESSORS, the ones whose move lands on the spot you just changed -- get their
priorities computed and pushed. Pop 4:
pop spot 4 (priority 1.0):
apply: V(4) = 1
who leads into 4? spot 3 (its right-move lands on 4)
priority(3) = | new V(3) - old V(3) | = | (0 + 0.9 x 1) - 0 | = | 0.9 - 0 | = 0.9
push spot 3 with priority 0.9
QUEUE: spot 3 priority 0.9
Spot 3 is now the only thing waiting, and its worth wants to move by 0.9. Pop it, and its
predecessor (spot 2) wakes in turn:
pop spot 3 (priority 0.9):
apply: V(3) = 0 + 0.9 x V(4) = 0 + 0.9 x 1 = 0.9
who leads into 3? spot 2
priority(2) = | (0 + 0.9 x 0.9) - 0 | = | 0.81 - 0 | = 0.81
push spot 2 with priority 0.81
QUEUE: spot 2 priority 0.81
Same shape again -- pop 2, wake spot 1:
pop spot 2 (priority 0.81):
apply: V(2) = 0 + 0.9 x V(3) = 0 + 0.9 x 0.9 = 0.81
who leads into 2? spot 1
priority(1) = | (0 + 0.9 x 0.81) - 0 | = | 0.729 - 0 | = 0.729
push spot 1 with priority 0.729
QUEUE: spot 1 priority 0.729
Pop the last one. Spot 1 has no predecessor (nothing leads into the start), so nothing new is
pushed and the queue empties:
pop spot 1 (priority 0.729):
apply: V(1) = 0 + 0.9 x V(2) = 0 + 0.9 x 0.81 = 0.729
who leads into 1? no one -- push nothing
QUEUE: empty -> stop
The +1 found at the goal has walked all the way back to the start, and the worths now read:
1 2 3 4
0.729 0.81 0.9 1 (the goal's reward, faded one step per spot back)
Stretch the corridor one spot left. A spot 0 leads into spot 1 (its
right-move lands on 1, paying 0), and the sweep above just finished: V(1) = 0.729,
V(0) still 0. What priority does spot 0 get pushed with?
CHECK: new V(0) = 0 + 0.9 x V(1) = 0.9 x 0.729 = 0.6561
priority(0) = | 0.6561 - 0 | = 0.6561 -- well over the floor, so queued;
one more pop and the goal's reward is five spots from home.
SO EVERY POP DID REAL WORK, WHICH IS THE WHOLE WIN OVER GRABBING AT RANDOM
Four pops, four worths moved, not one wasted. Compare the random grab from Chapter 13: with every
worth starting at 0, rehearsing spot 1's move reads new V(1) = 0 + 0.9 x V(2) = 0.9 x 0 = 0 -- the
worth was 0 and stays 0, a rehearsal spent on nothing. Only the spot next to the goal has anything
to teach at first, and random grabbing finds it by luck, then finds spot 3 by luck, and so on.
Priority sweeping never spends a pop on a no-jump: it works straight down the line of spots whose
worth actually moves, always the biggest jump first, waking each predecessor exactly when its turn
to move arrives.
BUT NOT EVERY NUDGE DESERVES THE QUEUE, SO SET A FLOOR
If a predecessor's jump comes out tiny -- a worth that would move by 0.0004 -- queuing it earns
almost nothing. So keep a small floor theta (say 0.001) and only push a spot whose priority clears
it: push only if priority > theta. In the sweep above every jump (1, 0.9, 0.81, 0.729) towered over
0.001, so all four were queued; deep in a long chain, where the faded jumps shrink below the floor,
the sweep simply stops spending effort on changes too small to matter.
One gatekeeping call. A predecessor's update works out to new V =
0.4213 against an old V of 0.4209; theta = 0.001. Does it enter the queue?
CHECK: priority = | 0.4213 - 0.4209 | = 0.0004 < 0.001 -> no. The change is
real but too small to spend a pop on; the floor is what keeps a long chain from
queueing forever over dust.
FREE WORK IS NOT USEFUL WORK, AND THREE MORE QUEUE MISTAKES
"Random rehearsal was already free -- why rank anything?" Count the useful ones:
on the fresh corridor, only ONE of the four rehearsals teaches anything (spot 4's;
the other three copy 0.9 x 0 = 0 back onto a 0). A random grab finds it one time
in four; the queue finds it every time. Free work is still wasted work if the
number it writes is the number already there.
"I pushed the spot I had just fixed." It felt like the changed spot was the busy
one, but right after applying V(4) = 1, spot 4's own priority is | 1 - 1 | = 0 --
it is DONE. The stale ones are its PREDECESSORS: spot 3's priority is
| 0.9 x 1 - 0 | = 0.9. A change ripples BACKWARD, to the spots whose moves land
on the one that changed -- never to itself.
"Priority is the worth -- rehearse the richest spot first." Two spots settle it:
a spot worth 100 whose update reads 100.0001 has priority 0.0001 -- nothing to do
-- while a spot worth 0 about to become 0.9 has priority 0.9. The queue ranks
SURPRISES (|new - old|), not riches. A rich, settled spot is boring; a poor spot
mid-jump is urgent.
"My model could not answer 'who leads into 4?'" The forward model (spot, move) ->
(landing, reward) was all I kept, and the sweep died after one pop: queue empty,
worths [0, 0, 0, 1]. Priority sweeping needs the model READ BACKWARD too -- keep
a reverse index (landing -> the spots that lead in), filed at the same moment
each forward fact is recorded.
SEAM. Pencil ends here; below, the same numbers in Python.
No loops, no functions -- the sweep above, pop by pop, every number hard-coded. The
model is the deterministic corridor (each spot's right-move lands on the next,
paying 0, and 4 pays +1 into the GOAL); pred[s] is who leads into s. Count one pop:
1 multiply + 1 add (the update), 1 write, then per predecessor 1 multiply + 1 add +
1 subtract + 1 compare (its priority against the floor) -- 8 strokes a pop, and
never a wasted one.
dilute, theta = 0.9, 0.001
V = {1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0, "GOAL": 0.0}
land = {1: 2, 2: 3, 3: 4, 4: "GOAL"} # model: where each right-move lands
rew = {1: 0.0, 2: 0.0, 3: 0.0, 4: 1.0} # model: reward that move pays
pred = {2: 1, 3: 2, 4: 3} # who leads into each spot (1 has none)
# the real step out of 4 found the +1; seed the queue with spot 4's jump
new4 = rew[4] + dilute * V["GOAL"] # 1 + 0.9*0 = 1.0
prio4 = abs(new4 - V[4]) # |1.0 - 0| = 1.0 (> theta, so queue it)
# QUEUE = [(1.0, spot 4)]
# pop spot 4
V[4] = rew[4] + dilute * V["GOAL"] # 1 + 0.9*0 = 1.0
prio3 = abs((rew[3] + dilute * V[4]) - V[3]) # |0 + 0.9*1.0 - 0| = 0.9 -> push spot 3
# pop spot 3
V[3] = rew[3] + dilute * V[4] # 0 + 0.9*1.0 = 0.9
prio2 = abs((rew[2] + dilute * V[3]) - V[2]) # |0 + 0.9*0.9 - 0| = 0.81 -> push spot 2
# pop spot 2
V[2] = rew[2] + dilute * V[3] # 0 + 0.9*0.9 = 0.81
prio1 = abs((rew[1] + dilute * V[2]) - V[1]) # |0 + 0.9*0.81 - 0| = 0.729 -> push spot 1
# pop spot 1 (no predecessor -> push nothing -> queue empties)
V[1] = rew[1] + dilute * V[2] # 0 + 0.9*0.81 = 0.729
print(V[1], V[2], V[3], V[4]) # 0.729 0.81 0.9 1.0
ANCHOR, unchanged since Chapter 13: the GOAL is a finished spot worth 0, so the move into it
fades nothing extra -- spot 4's worth is the bare +1, and every spot behind it is that +1 faded one
more step.
----------------------------------------------------------------------------------------------
IN THIS CHAPTER (Chapter 17 -- Two the Sample-Based Map Skipped):
Part 1 -- Wait for the Whole Trip: Monte Carlo by Pencil .
Part 2 (this post) -- the chapter closes here
NEXT CHAPTER: Four Questions Before Any Arithmetic: Which Machine for Which World
<- Back to all posts
----------------------------------------------------------------------------------------------
home . source on GitHub
==============================================================================================