REASONING FROM SCRATCH · CHAPTER 05

Learning values
from experience

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.

~20 min readSame 2×3 caveTested Python

What you'll learn

  • Synchronous policy evaluation (DP) on the lantern walk
  • First-visit Monte Carlo versus one-step TD on the same episode
  • n-step returns as the bridge that GAE will turn into a dial
  • Q-learning as off-policy control, and why GRPO is still Monte Carlo

Before you start

Four ways to name a room

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.

Sweep the map

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

MANIM Value learning: MC / TD / Q / SARSA name the same rooms differently.
  1. Sweep 1. Hall looks East into Window: \(V(\mathrm{Hall}) \leftarrow 1.0\). Start looks East into a still-zero Hall: \(V(\mathrm{Start}) \leftarrow -0.1\).
  2. Sweep 2. Hall is already 1.0. Start now sees that: \(V(\mathrm{Start}) \leftarrow -0.1 + 0.9 \times 1.0 = 0.80\).

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.

Wait until the lantern dies or the Window opens

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))\).

Guess, then correct the guess

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.

Start → Hall

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.

Hall → Window

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.

Act with one policy, learn about another

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, off-policy, and the deadly triad

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.

Mistakes learners make

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.

What to remember

  • DP sweep 2 gives \(V(\mathrm{Start}) = 0.80\) under “always East.”
  • MC on Start → Hall → Window writes 0.80 and 1.00. TD writes −0.1 then 1.0.
  • n-step returns interpolate. GAE will mix them. GRPO will not.
  • Q-learning: \(Q(\mathrm{Hall}, \mathrm{East}) = 0.50\) after one \(\alpha = 0.5\) step from 0.

Check yourself

1. After a synchronous sweep from zeros, what is \(V(\mathrm{Hall})\)? \(V(\mathrm{Start})\)

1.0 and −0.1.

2. Why is the first TD update of Start −0.1, not 0.80?

It bootstraps \(V(\mathrm{Hall}) = 0\). MC waits for the real return.

3. What makes Q-learning off-policy?

The target uses \(\max_{a'} Q\), not the action the behavior policy will take next.

4. Is GRPO closer to MC or to TD?

Monte Carlo. The group mean is a completed-episode baseline.

The code

lantern_learn.pyDP 0.80, MC 0.80/1.00, TD −0.1/1.0, Q 0.50
"""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")

Go to the source

Keep going