Section 2.6: Markov decision processes; Bellman equations

"The Bellman equation is what happens when a robot asks, 'and then what?' with mathematical persistence."

A Recursive Planning Agent

Figure 2.6 traces the closed-loop evidence, decision, consequence pattern that the rest of this section formalizes. A robot arm reaching for a cup faces, in principle, an infinite question: what is the long-term payoff of every torque it could apply, given everything that might happen next, forever? The Bellman equation answers it in one line by noticing that the value of any situation is just the reward you collect now plus the discounted value of wherever you land, a recursion that turns an unbounded lookahead into a single computable step. This recursion is the formal model behind much of reinforcement learning and control. An MDP consists of states, actions, transition dynamics, rewards, and a discount or horizon. Bellman equations then express a powerful idea: the value of a state is immediate reward plus the value of what comes next.

MDPs are not a claim that the real world is simple. They are an approximation tool. The engineering question is whether the state representation is good enough that past history no longer adds important predictive information.

Theory

An MDP is often written as \((\mathcal{S}, \mathcal{A}, P, R, \gamma)\). \(\mathcal{S}\) is the state space, \(\mathcal{A}\) is the action space, \(P(s'|s,a)\) is the transition distribution, \(R(s,a)\) is reward, and \(\gamma\) discounts future reward. The Markov property says the distribution over the next state depends on the current state and action, not on the full past.

The transition distribution \(P(s'|s,a)\) matters in embodied AI because physical dynamics are stochastic. A commanded torque produces a distribution of joint positions, not a single one, due to motor noise, contact slip, and sensor latency. If the planner treats transitions as deterministic, it produces policies that are brittle the moment the real robot deviates even slightly from the nominal path.

Mechanically, \(P(s'|s,a)\) is a conditional probability table (discrete) or density (continuous) that sums or integrates to one over all reachable next states \(s'\). The Bellman backup weights each possible outcome by its probability and sums the discounted future values, so the agent hedges across all likely next states rather than committing to a single predicted outcome.

A Bellman backup for a fixed policy (a policy \(\pi\) is the rule that maps each state to the action the agent takes there) can be written as \(V(s) = R(s,\pi(s)) + \gamma \sum_{s'} P(s'|s,\pi(s))V(s')\). In words: value equals immediate reward plus discounted expected future value. The summation matters because an action may lead to several possible next states, and the transition model weights each next state by its probability. This decomposition is sometimes called the one-step bootstrap trick: instead of rolling out a full trajectory to estimate value, every update needs only the reward at one step and the current estimate of the next state. Without the bootstrap trick, the alternative is a Monte Carlo rollout (running the full episode to its end and averaging the total observed return, with no intermediate bootstrapping from \(V(s')\)); averaging enough full Monte Carlo rollouts to estimate one starting state costs tens of thousands of episodes. With one-step Bellman backups, a tabular three-state grid converges in under 10 sweeps. The same logic, placed inside a neural network, trains a humanoid locomotion policy over millions of steps.

A value function that cannot be decomposed into one reward plus one discounted future is not a value function: it is a lookup table with no theory behind it.

The assumption is the load-bearing part. If \(s\) contains all prediction-relevant information, the backup can ignore the older history. If unobserved contact, actuator wear, or a previous collision still changes what happens next, the state is not Markov enough and the Bellman target is mixing incompatible situations; the partially observable formulation in the next section is the principled response when this happens.

To see the fixed point verified concretely rather than merely asserted: the algorithm below iterates the backup to convergence, and the worked example that follows applies it by hand to a three-state MDP, checks the result against the printed code output, and confirms the fixed-point condition in the algorithm's final step. That combination, hand trace plus convergence check, is what "verify its fixed point" (promised in the Big Picture above) means concretely in this section.

Worked Example

Code Fragment 2.6.1 performs Bellman backups in a tiny three-state MDP. The example is tabular so the recursive target stays visible.

# Section 2.6: runnable checkpoint for MDPs and Bellman equations.
# Keep the output small so the evidence record can be inspected directly.
states = ["far", "near", "done"]
value = {state: 0.0 for state in states}
gamma = 0.9
transition = {
    "far": ("near", -0.1),
    "near": ("done", 1.0),
    "done": ("done", 0.0),
}

for _ in range(3):
    for state in ["far", "near"]:
        next_state, reward = transition[state]
        value[state] = reward + gamma * value[next_state]

print({state: round(score, 3) for state, score in value.items()})

Expected output: the near state reaches value \(1.0\) because it receives the goal reward on the next transition. The far state reaches \(0.8\) because it pays an immediate penalty of \(-0.1\) and then inherits \(0.9 \times 1.0\) from the near state.

The same one-state-per-sweep propagation you just traced by hand scales, unchanged in principle, to systems with astronomically larger state spaces. Consider a specific case from a real deployed system. The AlphaGo training pipeline (Silver et al., 2016) uses an MDP where the state is the full board position and the action is the next stone placement. The reward is \(+1\) for a win and \(-1\) for a loss, delivered only at the terminal state. With \(\gamma = 1\) and a finite horizon of at most 361 moves, every Bellman backup propagates that single terminal signal backward through the game tree. The practical lesson is that sparse, terminal-only reward is viable when the state is fully Markov (the board encodes all prediction-relevant history) and when the horizon is bounded. Change either condition and the backup typically becomes unstable, since the terminal signal must then propagate through an unbounded or non-Markov chain of backups instead of a fixed, fully informative one.

Practical Recipe

1. Define state so it is as close to Markov as the task allows.
2. Specify action set, transition behavior, reward, discount, and horizon.
3. Write one Bellman backup by hand before using a trainer.
4. Check whether omitted history changes next-state prediction.
5. Use simulator diagnostics to test whether the MDP approximation is adequate.

MDPs and Bellman equations become useful when they are tied to a closed-loop contract between policy, world, evaluator, and safety constraints. The contract names the state representation, action space, transition model or sampler, reward definition, discount convention, and result artifact. That is the bridge between a readable concept and a system a skeptical builder can test.

Separate the conceptual claim, the systems claim, and the evidence claim. A good explanation, a clean API, and one successful rollout are different kinds of evidence, and the section should keep them distinct.

A robust MDP implementation starts with one inspectable baseline whose artifact records observations, actions, units, timestamps, seeds, termination reasons, and the perturbation applied. A maintained tool earns its place only if it preserves that schema and keeps the comparison construct-matched.

1. Write a one-paragraph task contract with observation, action, success, failure, and safety fields.
2. Choose the smallest simulator, dataset, or wrapper that exposes the contract faithfully.
3. Run one deterministic smoke test and one perturbation test before scaling.
4. Save one artifact containing configuration, seed, metrics, traces, and failure labels.
5. Compare methods only when the same script evaluates the same panel, split, seed set, and metric.

Diagnosing a Failed MDP

When an MDP model fails, avoid labeling the whole method as weak. First assign the failure to state definition, transition modeling, reward specification, discount choice, sampling coverage, or value-function approximation. Then rerun one controlled perturbation that isolates the suspected cause. This pattern turns a disappointing rollout into a reusable diagnostic asset.