REASONING FROM SCRATCH · CHAPTER 04

MDPs &
the Bellman equations

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.

~18 min readThe lantern walkTested Python

What you'll learn

  • The MDP five-tuple \((S, A, P, R, \gamma)\)
  • How to write a discounted return \(G_t\) by hand
  • The Bellman expectation and optimality backups
  • Why a language-model prefix is a state, and why \(P\) is deterministic

Before you start

A cave with a lantern

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.

Start Hall Window +1 Alcove Pit −1 Ledge
The lantern walk. Window and Pit are terminals. This grid is reused in the next chapter.

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.

States, actions, transitions, rewards, discount

SymbolMeaningLantern walk
Sstates6 cells; Window and Pit are terminals
AactionsN, S, E, W
Ptransition kerneldeterministic: walls bounce you back
Rreward−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

MANIM MDP lantern: Bellman backs up reward + discounted next value.

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.

Add the future, then shrink it

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.

One backup is the whole theory

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.

Prefix is state, token is action

MDP objectIn an LLM
StateThe prompt plus tokens so far
ActionThe next token
TransitionDeterministic: the token is appended
RewardUsually 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\).

Mistakes learners make

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.

What to remember

  • An MDP adds state. The lantern walk is a 2×3 cave with Window +1 and Pit −1.
  • Start → Hall → Window returns 0.80. Start → Alcove → Pit returns −1.00.
  • Hall with East 0.7 / South 0.3 backups to \(V = 0.40\).
  • For an LLM, the prefix is the state and the next token is the action. \(P\) is deterministic.

Check yourself

1. Rewards −0.1 then +1, \(\gamma = 0.9\). What is \(G\)?

0.80.

2. Why is \(V(\mathrm{Window}) = 0\)?

The episode is over. The +1 already arrived as \(R_{t+1}\) on the way in.

3. Hall policy East 0.7, South 0.3. What is \(V(\mathrm{Hall})\)

0.40.

4. What is random in the LLM MDP — the transition or the policy?

Only the policy. Appending a token is deterministic.

The code

lantern_mdp.pyreturns 0.80 and −1.00; Hall backups to 0.40
"""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")

Go to the source

Keep going