REASONING FROM SCRATCH · CHAPTER 04
A bandit has no next room. A reasoner does. Add state, and the thing you want is a sum of future rewards. Bellman says that sum obeys a one-step backup.
You carry a lantern through a 2×3 cave. The Window at the far end is the way out (+1). The Pit in the middle is a fall (−1). Every ordinary step costs −0.1 of oil. Hitting a wall leaves you in place.
The kiosk forgot each passenger. Here the room you stand in changes which actions are safe. That memory of “where I am” is state. The Bellman equation is just: the value of this room is the reward for leaving it, plus a discounted value of the next room.
| Symbol | Meaning | Lantern walk |
|---|---|---|
| S | states | 6 cells; Window and Pit are terminals |
| A | actions | N, S, E, W |
| P | transition kernel | deterministic: walls bounce you back |
| R | reward | −0.1 per step; +1 Window; −1 Pit |
| γ | discount in [0, 1] | 0.9 on this page |
The Markov property: the next state and reward depend on the current state and action, not on the path that got you here. “I am in the Hall” is enough. “I am in the Hall after visiting the Alcove twice” is not extra information, if the state is well designed.
cave · tuple · Bellman · policy
We write the reward that follows action \(A_t\) as \(R_{t+1}\). That is the Sutton & Barto index. It keeps “reward after the transition” visible. Terminals have value 0: the episode is over.
the return is this step’s reward, plus a discounted return from tomorrow.
Path Start → Hall → Window. Rewards: −0.1, then +1. With \(\gamma = 0.9\):
the cheap step is worth paying because the Window is next.
Path Start → Alcove → Pit. Rewards: −0.1, then −1. \(G = -0.1 + 0.9 \cdot (-1) = -1.00\).
\(\gamma = 0\) is myopic: only the next reward matters. \(\gamma \to 1\) treats a late Window like an early one. For a short episode, \(\gamma = 1\) is legal if every path ends. We keep 0.9 so the arithmetic stays visible.
The value of a policy is \(V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]\). The action-value is the same thing given \(A_t = a\). Because \(G_t = R_{t+1} + \gamma G_{t+1}\), the expectation unfolds into a one-step backup:
average, over the policy and the environment, the immediate reward plus γ times the next value.
Worked backup from the Hall. Policy: East 0.7 (into the Window), South 0.3 (into the Pit). Both terminals have value 0.
seventy percent a sure +1, thirty percent a sure −1.
Bellman optimality replaces the average over \(\pi\) with a \(\max_a\). \(V^*(\mathrm{Hall})\) is then just 1: take East. The next chapter turns these fixed-point equations into algorithms.
| MDP object | In an LLM |
|---|---|
| State | The prompt plus tokens so far |
| Action | The next token |
| Transition | Deterministic: the token is appended |
| Reward | Usually 0 until the end, then a checker or a preference score |
| γ | Typically 1. Sequences are short and episodic |
Deterministic transitions are the key. The environment does not flip a coin after you emit “East”. The next state is the old prefix plus that token. All the randomness is in the policy. That is why later policy-gradient derivations can drop the dynamics.
GRPO, coming in chapter 10, estimates how good a finished chain is without a value head. It still lives in this MDP. It just refuses to learn \(V\).
Giving terminals a value and a reward. \(V(\mathrm{Window}) = 0\). The +1 is the reward on the transition into the Window.
Writing \(\gamma \in [0, 1)\) and then setting \(\gamma = 1\) for episodes. Either bound is fine if every path ends. Say which you are using.
“R1 estimates a value of continuing the chain.” GRPO has no learned \(V\). Do not smuggle a critic into that story.
0.80.
The episode is over. The +1 already arrived as \(R_{t+1}\) on the way in.
0.40.
Only the policy. Appending a token is deterministic.
"""The lantern walk — a 2×3 cave MDP of our own.
Layout (row, col):
(0,0) Start (0,1) Hall (0,2) Window +1, terminal
(1,0) Alcove (1,1) Pit (1,2) Ledge Pit is −1, terminal
Moving into a wall leaves you in place. Every ordinary step costs −0.1.
Entering the Window pays +1. Entering the Pit pays −1. γ = 0.9.
"""
ROWS, COLS = 2, 3
START = (0, 0)
WINDOW = (0, 2)
PIT = (1, 1)
TERMINALS = {WINDOW, PIT}
STEP_COST = -0.1
GAMMA = 0.9
ACTIONS = ("N", "S", "E", "W")
DELTA = {"N": (-1, 0), "S": (1, 0), "E": (0, 1), "W": (0, -1)}
def in_bounds(cell):
r, c = cell
return 0 <= r < ROWS and 0 <= c < COLS
def step(state, action):
"""Deterministic transition. Returns (next_state, reward, done)."""
if state in TERMINALS:
return state, 0.0, True
dr, dc = DELTA[action]
nxt = (state[0] + dr, state[1] + dc)
if not in_bounds(nxt):
nxt = state
if nxt == WINDOW:
return nxt, 1.0, True
if nxt == PIT:
return nxt, -1.0, True
return nxt, STEP_COST, False
def discounted_return(rewards, gamma=GAMMA):
"""G = r0 + γ r1 + γ² r2 + … (rewards already in time order)."""
g = 0.0
for r in reversed(rewards):
g = r + gamma * g
return g
# Path Start → Hall → Window. Rewards: −0.1 then +1.
PATH_SW = [STEP_COST, 1.0]
G_START_WINDOW = discounted_return(PATH_SW) # 0.80
# Path Start → Alcove → Pit. Rewards: −0.1 then −1.
PATH_SP = [STEP_COST, -1.0]
G_START_PIT = discounted_return(PATH_SP) # −1.00
def bellman_expectation(action_probs, rewards, next_values, gamma=GAMMA):
"""One backup: Σ_a π(a) [ r_a + γ V(s'_a) ]."""
return sum(
p * (r + gamma * v)
for p, r, v in zip(action_probs, rewards, next_values)
)
# From Hall: East 0.7 into Window, South 0.3 into Pit. Both next-values are 0.
HALL_PI = (0.7, 0.3)
HALL_R = (1.0, -1.0)
HALL_V_NEXT = (0.0, 0.0)
V_HALL = bellman_expectation(HALL_PI, HALL_R, HALL_V_NEXT) # 0.40
if __name__ == "__main__":
assert step(START, "E") == ((0, 1), STEP_COST, False)
assert step((0, 1), "E") == (WINDOW, 1.0, True)
assert step((0, 1), "S") == (PIT, -1.0, True)
assert abs(G_START_WINDOW - 0.80) < 1e-12
assert abs(G_START_PIT - (-1.00)) < 1e-12
assert abs(V_HALL - 0.40) < 1e-12
print("lantern mdp ok")