REASONING FROM SCRATCH · CHAPTER 05
Bellman is a fixed point. This chapter is four ways to walk toward it on the lantern cave: a known model, a finished episode, a one-step guess, and a Q-table.
You still have the lantern. You still want the value of Start. If you own a map of every transition, you can sweep Bellman until the numbers stop moving. If you only have walks you took, you can average the returns (Monte Carlo) or peek one step ahead and steal the current guess of the next room (TD).
DP needs a model. MC waits for the Window or the Pit. TD updates after every step. That bias–variance line is the same line GAE will let you slide in chapter 07, and the same line GRPO will refuse to slide: GRPO is a Monte-Carlo baseline, not a bootstrap.
Fix a policy: go East if you can, otherwise North. Start every \(V\) at 0, including terminals (they stay 0). Synchronous sweep: write a new table from the old one, then swap.
rooms · four · bootstrap · tables
Policy improvement then picks, in each room, the action with the best one-step backup. Iterate (policy iteration) or fold both steps into one \(\max\) (value iteration). Generalized policy iteration is the name for “evaluate a bit, improve a bit.” We do not need more of it for language models. We need the idea that a target can be a backup of our own table.
Episode: Start → Hall → Window. Rewards −0.1, +1. Working backwards:
first-visit MC writes those returns into V. No model. No bootstrap. High variance if the episode had been long and lucky.
First-visit uses the first time you entered the room. Every-visit averages every visit in the episode. Incremental MC is the chapter-03 update with the return as the target: \(V(s) \leftarrow V(s) + \alpha(G - V(s))\).
the target is one reward plus our current value of the next room. δ = target − V(s) is the TD error.
Same episode, \(V\) starts at 0, \(\alpha = 1\) so the first visit writes the target in full.
Target \(= -0.1 + 0.9 \cdot 0 = -0.1\). MC would have written 0.80. TD is early and low, because Hall is still 0.
Target \(= 1.0\). Now \(V(\mathrm{Hall}) = 1.0\). The next episode’s Start update will see it.
That is the bias: TD bootstraps a wrong table. It is also the variance win: you do not wait for the Window. n-step returns sit between them. A 2-step target is \(R_{t+1} + \gamma R_{t+2} + \gamma^2 V(s_{t+2})\). GAE (chapter 07) averages many n with a \(\lambda\) dial. Chapter 06 of the old notes promised n-step and did not deliver it. Here it is, short, because PPO needs it.
Prediction estimates \(V^\pi\). Control also changes \(\pi\). Store \(Q(s,a)\). SARSA is on-policy: the next action \(A'\) is the one you will actually take (including the ε that might walk into the Pit). Q-learning is off-policy: the target uses \(\max_{a'} Q(s', a')\), the best action, not the exploratory one.
move Q toward “this reward, plus the best next Q”. The behavior policy can be ε-greedy; the target policy is greedy.
From Hall, take East into the Window, \(\alpha = 0.5\), all Q start at 0. Target is 1.0. New \(Q(\mathrm{Hall}, \mathrm{East}) = 0.50\).
Tables die at LLM scale. A neural net that takes a state and emits Q or V is function approximation. The target still moves (semi-gradient). That instability is one reason GRPO drops the critic: no bootstrap, no moving \(V\) head. GRPO’s group mean is a Monte-Carlo baseline, not a TD target. Do not call it “TD-style.”
On-policy data comes from the policy you are evaluating. Off-policy data comes from some other behavior policy. Importance sampling (chapter 07) is how you reuse old data. The deadly triad is function approximation + bootstrapping + off-policy data. DQN survives it with replay and a frozen target net. We will not need DQN. We need the words “behavior policy” and “target policy”: they become \(\pi_{\mathrm{old}}\) and \(\pi_\theta\) in PPO.
Synchronous vs in-place. After sweep 1 of a synchronous update, every non-terminal that cannot see a terminal yet is just the step cost. Hall is 1.0. Start is −0.1, not −1.9.
Assigning a value to the Window. \(V(\mathrm{Window}) = 0\). The +1 is the reward on the way in.
“GRPO uses a TD advantage.” No. Group-relative advantages are Monte Carlo. There is no bootstrap and no value head.
1.0 and −0.1.
It bootstraps \(V(\mathrm{Hall}) = 0\). MC waits for the real return.
The target uses \(\max_{a'} Q\), not the action the behavior policy will take next.
Monte Carlo. The group mean is a completed-episode baseline.
"""Learn values on the lantern walk — the same 2×3 cave as chapter 04.
Four algorithms, one grid:
DP — iterative policy evaluation with a known model
MC — first-visit Monte Carlo on a finished episode
TD — one-step temporal difference
Q — off-policy Q-learning
"""
from copy import deepcopy
# Re-state the cave so this file runs alone. Same numbers as lantern_mdp.py.
ROWS, COLS = 2, 3
START, WINDOW, PIT = (0, 0), (0, 2), (1, 1)
TERMINALS = {WINDOW, PIT}
STEP_COST, GAMMA = -0.1, 0.9
DELTA = {"N": (-1, 0), "S": (1, 0), "E": (0, 1), "W": (0, -1)}
ACTIONS = ("N", "S", "E", "W")
def step(state, action):
if state in TERMINALS:
return state, 0.0, True
dr, dc = DELTA[action]
nxt = (state[0] + dr, state[1] + dc)
if not (0 <= nxt[0] < ROWS and 0 <= nxt[1] < COLS):
nxt = state
if nxt == WINDOW:
return nxt, 1.0, True
if nxt == PIT:
return nxt, -1.0, True
return nxt, STEP_COST, False
def zeros():
return { (r, c): 0.0 for r in range(ROWS) for c in range(COLS) }
# A simple policy: go East if that cell exists, otherwise go North.
def east_then_north(state):
nxt, _, _ = step(state, "E")
return "E" if nxt != state or state[1] == COLS - 1 else "N"
def policy_evaluation(sweeps=2):
"""Synchronous DP. V of terminals stays 0. Returns every sweep."""
history = []
v = zeros()
for _ in range(sweeps):
nxt = deepcopy(v)
for s in v:
if s in TERMINALS:
continue
a = east_then_north(s)
sp, r, _ = step(s, a)
nxt[s] = r + GAMMA * v[sp]
v = nxt
history.append(v)
return history
# First-visit MC on the episode Start → Hall → Window.
# Rewards: −0.1, +1. Return at Start is 0.80; at Hall is 1.00.
MC_EPISODE = [START, (0, 1), WINDOW]
MC_REWARDS = [STEP_COST, 1.0]
def first_visit_mc(states, rewards, gamma=GAMMA):
"""G_t from each first visit, working backwards."""
g, returns = 0.0, {}
seen = set()
for t in range(len(rewards) - 1, -1, -1):
g = rewards[t] + gamma * g
s = states[t]
if s not in seen:
returns[s] = g
seen.add(s)
return returns
# TD(0) on the same episode, V starts at 0, α = 1 so the first visit writes
# the one-step target in full. That makes the contrast with MC visible.
def td0_episode(states, rewards, alpha=1.0, gamma=GAMMA):
v = zeros()
updates = []
for t, s in enumerate(states[:-1]):
sp, r = states[t + 1], rewards[t]
target = r + gamma * v[sp]
v[s] = v[s] + alpha * (target - v[s])
updates.append((s, target, v[s]))
return v, updates
# One Q-learning step from Hall, taking East into the Window.
# Q starts at 0, α = 0.5, so Q(Hall, East) ← 0.5 * 1.0 = 0.50.
def q_learning_step(q, state, action, reward, nxt, alpha=0.5, gamma=GAMMA):
max_next = 0.0 if nxt in TERMINALS else max(q[(nxt, a)] for a in ACTIONS)
target = reward + gamma * max_next
q[(state, action)] = q[(state, action)] + alpha * (target - q[(state, action)])
return q[(state, action)], target
if __name__ == "__main__":
sweeps = policy_evaluation(2)
# Sweep 1: Hall ← 1.0 (East into Window). Start ← −0.1 (East into Hall at 0).
assert abs(sweeps[0][(0, 1)] - 1.0) < 1e-12
assert abs(sweeps[0][START] - STEP_COST) < 1e-12
# Sweep 2: Start ← −0.1 + 0.9*1.0 = 0.80. Hall stays 1.0.
assert abs(sweeps[1][START] - 0.80) < 1e-12
assert abs(sweeps[1][(0, 1)] - 1.0) < 1e-12
mc = first_visit_mc(MC_EPISODE, MC_REWARDS)
assert abs(mc[START] - 0.80) < 1e-12
assert abs(mc[(0, 1)] - 1.00) < 1e-12
_, td_updates = td0_episode(MC_EPISODE, MC_REWARDS)
# First TD step: V(Start) ← −0.1 + 0.9*0 = −0.1 (bootstraps a zero Hall).
# Second: V(Hall) ← 1.0.
assert abs(td_updates[0][2] - STEP_COST) < 1e-12
assert abs(td_updates[1][2] - 1.0) < 1e-12
q = { (s, a): 0.0 for r in range(ROWS) for c in range(COLS)
for a in ACTIONS for s in [(r, c)] }
q_he, tgt = q_learning_step(q, (0, 1), "E", 1.0, WINDOW)
assert abs(tgt - 1.0) < 1e-12
assert abs(q_he - 0.50) < 1e-12
print("lantern learn ok")