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

This section develops 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.

A Bellman backup for a fixed policy 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.

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.

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.

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.

For Markov decision processes; Bellman equations, 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.

For Markov decision processes; Bellman equations, a robust implementation starts with one inspectable baseline whose artifact records observations, actions, units, timestamps, seeds, termination reasons, and the perturbation applied. The maintained-tool version is useful only if it preserves that schema and lets the comparison remain 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.

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.