"For twenty-one chapters I was asked one thing and one thing only: what happens next. I forecast the demand, I filtered the state, I quantified my own uncertainty about tomorrow, and tomorrow arrived whether or not I had spoken, indifferent to me, untouched by my prediction. Then one day they changed the question. They did not ask what will happen. They asked what should I do, and they let my answer change the future. It is a different kind of vertigo. A forecast that is wrong costs you nothing but pride; a decision that is wrong costs you the world it created. Now every state I land in is partly my own fault, every reward a verdict on a choice I made three steps ago, and the future is no longer a thing I watch but a thing I am on the hook for. They handed me a steering wheel after twenty-one chapters of being a very confident passenger, and the first thing I learned is that knowing where the road goes is not the same as knowing how to drive."
A Reinforcement Learner Still Exploring
Chapter Overview
Every chapter before this one taught the model to predict. It forecast the next value, filtered the hidden state, attached an honest distribution to its own uncertainty, and in every case the world rolled forward on its own, unmoved by anything the model said. This chapter, which opens Part VI, changes the question and with it the entire enterprise of the book: it is the pivot from prediction to action. We stop asking what will happen and start asking what should I do, and the moment the model's output is allowed to act on the world, a forecast becomes a decision and a decision becomes a sequence of decisions, each one reshaping the situation the next must confront. The Markov decision process (MDP) is the mathematical object that makes this precise. It is the foundational model of sequential decision making, the shared grammar beneath optimal control, operations research, and the whole of reinforcement learning, and the rest of Part VI is, in one way or another, the story of how to solve it when its pieces are unknown, partially observed, or too large to write down.
An MDP names five things: a set of states, a set of actions available in each state, a transition rule that says how the world responds when you act, a reward that scores each step, and a discount that trades present reward against future reward. The single assumption that makes the whole framework tractable is the Markov property, and it is the same idea that ran through the state-space models of Chapter 7: the state is a sufficient statistic, a summary so complete that the future depends on the past only through the present state. Where Chapter 7 used that property to filter and smooth an observed signal, here it does heavier work. If the current state truly captures everything relevant, then the best action depends only on where you are now and not on the entire history of how you arrived, which collapses the search for a good behavior from a search over infinite histories to a search over states. The latent-state thread of this book returns here as the ground on which optimal decision making stands or falls: choose your state poorly and the Markov property fails, and with it every guarantee in the chapter.
Given an MDP, the goal is a policy, a rule for choosing actions, that maximizes expected discounted return over the long run. The machinery that finds it is built on value functions: the state-value function $V(s)$, the expected return from a state under a policy, and the action-value function $Q(s,a)$, the expected return from taking an action and following the policy thereafter. The Bellman equations are the heart of the chapter, a self-consistency condition stating that the value of a state equals the immediate reward plus the discounted value of where you land next, turning a daunting long-horizon optimization into a recursive local relationship. The Bellman optimality equation sharpens this into a fixed-point characterization of the best possible behavior, and from it fall the two exact algorithms that close the chapter: value iteration, which repeatedly applies the Bellman optimality operator until the values converge, and policy iteration, which alternates evaluating a policy and acting greedily with respect to it. Both are dynamic programming, and both converge to the same optimal policy.
It is worth being honest about what this chapter delivers and what it defers. Value iteration and policy iteration solve an MDP exactly, but only when the transition and reward functions are fully known and the state space is small enough to sweep. That is the rare luxury, and almost everything that follows in Part VI is reinforcement learning, which is what you do when you must learn to act well without that knowledge, by interacting, sampling, and approximating. So treat the dynamic programming of this chapter not as the practical endpoint but as the exact ideal that reinforcement learning approximates. Every temporal-difference update in Chapter 24, every deep Q-network and policy gradient in the chapters after, is a sampled, function-approximated shadow of the Bellman backups you will perform exactly here. You cannot understand the approximations until you have seen the thing they approximate, and that thing is the MDP solved by dynamic programming.
Prerequisites
This chapter assumes you are ready to cross the line the book has been building toward, from predicting the world to acting in it. The conceptual frame comes from the very first chapter: the prediction, reasoning, and decision triad of Chapter 1, Introduction to Temporal Intelligence named decision as the third and hardest mode of temporal intelligence, and this chapter is where the book finally makes good on it, so a reader who recalls that 1.3 distinction will see exactly which promise is being kept. The technical spine is the Markov property and the idea of a state as a sufficient statistic, developed for filtering in Chapter 7, State-Space Models and Filtering; the MDP reuses that exact notion of state but puts it to work choosing actions rather than estimating a signal, so the bridge from Chapter 7 is the single most useful thing to carry in. The mathematics is probability: expectations, conditional distributions, Markov chains, and the geometric series that makes a discounted infinite horizon converge to a finite value. Readers wanting to refresh expectations and Markov chains will find them in Appendix B, Probability and Statistics Refresher, and the full path through the book in the Table of Contents.
If you keep one idea from this chapter, keep this: a Markov decision process turns acting over time into a search for a policy that maximizes expected discounted return, and when the model is known the Bellman equations make that search exact, solvable by value iteration or policy iteration as dynamic programming. The Markov property earns its keep by making the optimal action depend only on the current state, not the whole history; the value functions $V(s)$ and $Q(s,a)$ measure how good a state or action is under a policy; the Bellman equations express value as immediate reward plus discounted future value, a recursive self-consistency that converts a long-horizon optimization into local backups; and value iteration and policy iteration both converge to the one optimal policy. Everything reinforcement learning does for the rest of Part VI is an approximation of these exact dynamic-programming backups performed when the model is unknown or too large to sweep.
Chapter Roadmap
- 22.1 Sequential Decision Problems What changes when an output is allowed to act: the book's pivot from prediction to decision, the agent-environment loop of states, actions, and rewards, the five components of an MDP, the discounted return, and why a decision that reshapes the world is a fundamentally harder object than a forecast that merely watches it.
- 22.2 The Markov Property The assumption that makes the whole framework tractable: the state as a sufficient statistic so complete that the future depends on the past only through the present, the same idea that powered state-space filtering in Chapter 7, and what goes wrong, and how to repair it by augmenting the state, when the property fails.
- 22.3 Policies, Value Functions, and Bellman Equations The objects that define and measure good behavior: policies as rules for choosing actions, the state-value $V(s)$ and action-value $Q(s,a)$ functions as expected discounted return, and the Bellman equations, including the optimality equation, that express value recursively as immediate reward plus discounted future value.
- 22.4 Dynamic Programming Solving a known MDP exactly: value iteration as repeated application of the Bellman optimality operator, policy iteration as alternating policy evaluation and greedy improvement, the contraction-mapping argument that proves both converge, and the framing of dynamic programming as the exact ideal that all of reinforcement learning approximates.
Once you have worked through the four sections, the Hands-On Lab below chains them into a single experiment on one small world. Each lab step maps to a section, so the lab doubles as a review: by the time you finish you will have specified an MDP with the components of Section 22.1, leaned on the Markov property of Section 22.2 to justify a stationary policy, evaluated that policy with the Bellman equations of Section 22.3, and found the optimal policy with the two dynamic-programming algorithms of Section 22.4, confirming they agree.
Hands-On Lab: Solve a Gridworld
Objective
Take the MDP out of the equations and make it run. You will define a small gridworld from scratch, its states, its actions, its transition probabilities (including a slippery world where intended moves sometimes fail), its rewards, and a discount factor, assembling the five components of Section 22.1 into a concrete object you can solve. With the MDP specified, you will first evaluate a fixed policy by solving the Bellman expectation equations of Section 22.3, computing the value of every state under a behavior you choose so that "this policy is worth this much from here" becomes a number rather than an intuition. You will then find the best behavior two different ways using the dynamic programming of Section 22.4: value iteration, sweeping the Bellman optimality backup until the values stop moving, and policy iteration, alternating policy evaluation with greedy improvement until the policy stops changing. The single payoff of the lab is the confirmation that the two algorithms, which look nothing alike step to step, converge to the very same optimal policy and the very same optimal values, the practical proof that the Bellman optimality equation has one fixed point and dynamic programming finds it.
What You'll Practice
- Specifying an MDP as states, actions, transition probabilities, rewards, and a discount factor, following Section 22.1.
- Justifying a stationary, history-independent policy by appeal to the Markov property, following Section 22.2.
- Evaluating a fixed policy by solving the Bellman expectation equations for its value function, following Section 22.3.
- Finding the optimal policy with value iteration and with policy iteration, and confirming they agree, following Section 22.4.
- Reading an optimal value function and its greedy policy as a map of how to act from every state.
Setup
You need only NumPy and a few dozen lines; the whole lab fits in a single script with no deep-learning framework required, which is itself the point that dynamic programming is exact arithmetic on a known model, not learning. Define a small grid (a 4-by-4 world with a goal cell, an optional trap, and walls is plenty), encode the transition function (deterministic to start, then slippery so that an intended move succeeds with probability 0.8 and slips sideways otherwise), set a per-step reward and a discount factor below one so the infinite horizon converges, and you have an MDP. The one discipline that governs the lab is to keep the state, the action set, and the transition and reward tables explicit and separate, because every Bellman backup is just a weighted sum over next states drawn from those tables, and a bug in the transition table will quietly produce a confident, wrong optimal policy that still looks like a valid map. The code below runs value iteration to convergence in a handful of lines and returns both the optimal values and the greedy policy read off them.
import numpy as np
def value_iteration(P, R, gamma=0.95, tol=1e-8):
# P[s, a, s2] transition probs, R[s, a] expected reward.
n_states, n_actions, _ = P.shape
V = np.zeros(n_states)
while True:
Q = R + gamma * np.einsum("sat,t->sa", P, V) # Bellman optimality backup
V_new = Q.max(axis=1) # value = best action's value
if np.max(np.abs(V_new - V)) < tol: # contraction has converged
break
V = V_new
policy = Q.argmax(axis=1) # greedy policy from optimal V
return V, policy
Steps
Step 1: Define the MDP
Build the gridworld as the five components of Section 22.1: enumerate the states, list the actions (up, down, left, right), fill the transition table for the deterministic world and then the slippery one, assign rewards (a positive reward at the goal, a small negative reward per step to encourage short paths), and pick a discount factor. Sanity-check that every row of every transition slice sums to one before you solve anything.
Step 2: Evaluate a fixed policy
Choose a simple policy (for example, always move toward the goal in row-then-column order, or a uniform random policy) and solve the Bellman expectation equations of Section 22.3 for its value function, either by iterating the expectation backup to convergence or by solving the linear system directly. Read the resulting values as the expected discounted return from each state under that fixed behavior, and note where the policy wastes return.
Step 3: Solve with value iteration
Run value iteration from Step's setup code, applying the Bellman optimality backup of Section 22.4 until the maximum value change falls below tolerance, and read off the greedy policy. Watch the number of sweeps to convergence and confirm that the optimal values dominate the fixed-policy values from Step 2 everywhere, as they must.
Step 4: Solve with policy iteration
Now solve the same MDP the other way: alternate full policy evaluation (Step 2's machinery) with greedy policy improvement, repeating until the policy stops changing, the second dynamic-programming algorithm of Section 22.4. Count how few iterations policy iteration needs compared with value iteration's many sweeps, the classic trade of more work per iteration for far fewer iterations.
Step 5: Confirm the two agree
Compare the optimal value function and the optimal policy from value iteration against those from policy iteration. They should match to numerical tolerance, the practical confirmation that the Bellman optimality equation has a single fixed point and both dynamic-programming routes find it. Where ties between equally good actions break differently, confirm the tied actions have equal value.
Expected Output
The lab produces one small MDP solved three ways and a clean agreement that makes the chapter's theory tangible. Step 2 yields a value function for your chosen fixed policy, and on the slippery world you should see lower values than on the deterministic one because the world sometimes overrules your action, the discount and the slip together pricing in the cost of imperfect control. Steps 3 and 4 each yield an optimal value function and an optimal policy, drawn as arrows on the grid pointing the way to the goal, and the optimal values should dominate the fixed-policy values at every state, the unmistakable signature of having actually optimized. The headline result is Step 5: value iteration and policy iteration, despite converging through entirely different intermediate sequences and despite policy iteration finishing in far fewer outer iterations, agree on the same optimal values and the same optimal policy to numerical tolerance. That agreement is the whole point made concrete, that a known MDP has one optimal behavior and dynamic programming computes it exactly. The reader finishes able to take any small, fully specified sequential decision problem and solve it to optimality by hand, the exact baseline against which every approximate reinforcement-learning method in the rest of Part VI will be measured.
Once you have written value iteration and policy iteration from scratch and watched them agree, you rarely write them again, because the exact dynamic-programming solvers of Section 22.4 are a configured call in pymdptoolbox: hand it a transition array and a reward array and mdptoolbox.mdp.ValueIteration or mdptoolbox.mdp.PolicyIteration returns the optimal values and policy with the convergence bookkeeping already handled. For the slippery-grid environment itself, Gymnasium ships a FrozenLake world that is a gridworld MDP out of the box, the standard sandbox the rest of Part VI builds on. The discipline the chapter teaches still governs the libraries: a solver fed a transition table whose rows do not sum to one, a discount set to one on an infinite horizon, or a reward attached to the wrong state will each return a confident and wrong optimal policy in exactly the same few lines. The library makes the backup free; it does not make your MDP correct.
Stretch Goals
- Sweep the discount factor from near zero toward one and watch the optimal policy change from myopic (grab the nearest small reward) to far-sighted (endure step costs to reach the distant goal), making the role of discounting in Section 22.1 a picture rather than a parameter.
- Break the Markov property on purpose by hiding part of the state (make the reward depend on a feature the agent cannot see) and confirm that a stationary policy can no longer be optimal, the failure mode Section 22.2 warns about and the exact gap that Chapter 23 opens to address.
- Replace exact policy evaluation in Step 4 with a few sweeps of approximate evaluation (modified policy iteration) and observe that the algorithm still converges to the optimal policy with less work per iteration, the bridge between the two methods of Section 22.4.
What's Next?
This chapter opened Part VI: Sequential Decision Making, and it changed what the book is about. Every model before it predicted; from here on, the model acts, and the Markov decision process gave that turn a precise language of states, actions, rewards, value functions, and the Bellman equations that dynamic programming solves exactly when the model is known. But that last clause hides the catch the rest of Part VI is built to remove, that we assumed the agent can see the true state. Real agents rarely can. A robot reads noisy sensors, a clinician sees symptoms not the disease, a trader observes prices not the regime, and in each case the Markov property holds for a state the agent cannot directly observe. Chapter 23: Partial Observability and POMDPs confronts exactly this, generalizing the MDP to the case where the state is hidden behind observations, where the agent must act on a belief, a distribution over states maintained by the very filtering machinery of Chapter 7, and where the clean fixed point of this chapter becomes a far harder problem over belief space. The sufficient statistic that made everything tractable here returns there as a thing you must infer rather than read. The full path through Part VI and the rest of the book is laid out in the Table of Contents.
Bibliography & Further Reading
Foundational Texts
Sutton, R. S., Barto, A. G. "Reinforcement Learning: An Introduction." 2nd ed., MIT Press, 2018. incompleteideas.net/book/the-book.html
The standard reference for the entire arc of Part VI, whose early chapters develop MDPs, value functions, the Bellman equations, and dynamic programming exactly as this chapter does, then build reinforcement learning on top; the single most important book to read alongside this part.
Bellman, R. "Dynamic Programming." Princeton University Press, 1957. press.princeton.edu/books/paperback/9780691146683
The founding work that introduced dynamic programming and the principle of optimality, the recursive self-consistency that bears Bellman's name and underlies every value-iteration and policy-iteration backup in Section 22.4.
Howard, R. A. "Dynamic Programming and Markov Processes." MIT Press, 1960. mitpress.mit.edu/9780262080095
The work that introduced policy iteration, the alternate dynamic-programming algorithm of Section 22.4 that converges in remarkably few iterations by alternating exact policy evaluation with greedy improvement.
Theory of Markov Decision Processes
Puterman, M. L. "Markov Decision Processes: Discrete Stochastic Dynamic Programming." Wiley, 1994. onlinelibrary.wiley.com/doi/book/10.1002/9780470316887
The definitive and rigorous treatment of MDP theory, including existence of optimal stationary policies, the contraction-mapping proofs of convergence for value and policy iteration, and the full taxonomy of finite and infinite horizon criteria behind Sections 22.3 and 22.4.
Bertsekas, D. P. "Dynamic Programming and Optimal Control." Athena Scientific. athenasc.com/dpbook.html
The authoritative control-theoretic companion to the MDP, developing dynamic programming, the Bellman operator as a contraction, and approximate dynamic programming, the bridge from the exact methods of this chapter to the function-approximation methods of later chapters.
Courses and Tutorials
Silver, D. "Reinforcement Learning Course." University College London. davidsilver.uk/teaching
A widely used lecture series whose early lectures cover MDPs, Bellman equations, and dynamic programming with exceptional clarity, an ideal video companion to this chapter before the reinforcement learning of the rest of Part VI.
Achiam, J., et al. "Spinning Up in Deep RL." OpenAI. spinningup.openai.com
An accessible introduction to reinforcement learning whose background section frames the MDP, return, and value functions exactly as this chapter does, the recommended on-ramp from these exact methods to the deep RL of later chapters.
Tools and Environments
Towers, M., et al. "Gymnasium: A Standard Interface for Reinforcement Learning Environments." 2024. arXiv:2407.17032. arxiv.org/abs/2407.17032
The paper describing Gymnasium, the maintained successor to OpenAI Gym and the standard environment interface for the rest of Part VI, including the FrozenLake gridworld MDP used in the lab.
Farama Foundation. "Gymnasium Documentation." gymnasium.farama.org
The reference documentation for Gymnasium environments and the agent-environment API, the practical sandbox where the MDPs of this chapter become runnable worlds for the rest of the part.
Cordwell, S. "Python Markov Decision Process Toolbox (pymdptoolbox)." github.com/sawcordwell/pymdptoolbox
A compact Python library implementing value iteration, policy iteration, and their variants for known MDPs, the off-the-shelf solver behind the library-shortcut version of the lab.