Markov Decision Processes and Dynamic Programming

Where we are. This is the first chapter, and it states the object the whole curriculum orbits: the finite Markov decision process and the two equations that pin down optimal behaviour in it. The claim is small and load-bearing — the optimal value function is the unique fixed point of a $\discount$-contraction, and value iteration and policy iteration are two ways of reaching that fixed point. Everything later — LQR, MPC, model-based and model-free RL — computes, approximates, or learns this same fixed point when the MDP is too large, too continuous, or unknown.

Notation and conventions

We use the case convention of Sutton & Barto Sutton & Barto (2018) throughout: lowercase names a true object we want ($\valuefn_\policy$), and uppercase names an estimate we hold and update ($V_k$).

| Symbol | Meaning | |---|---| | $\statespace,\ \actionspace$ | finite state and action sets; $\lvert\statespace\rvert, \lvert\actionspace\rvert < \infty$ | | $\transition(s',r \mid s,a)$ | dynamics — joint probability of next state $s'$ and reward $r$ | | $\policy(a \mid s)$ | policy — probability of action $a$ in state $s$ | | $\discount \in [0,1)$ | discount factor (strict inequality is load-bearing) | | $\valuefn_\policy,\ \qfn_\policy$ | state- and action-value functions of $\policy$ (true) | | $\optvaluefn,\ \optqfn$ | optimal value functions | | $V_k \in \R^{\statespace}$ | the $k$-th value iterate (an estimate of $\optvaluefn$) | | $\bellman^\policy,\ \bellmanopt$ | Bellman expectation / optimality operators | | $\norm{\cdot}_\infty$ | sup norm on $\R^{\statespace}$: $\norm{v}_\infty \defeq \max_{s} \lvert v(s)\rvert$ |

A value function on a finite state set is a vector in $\R^{\statespace}$, a point in $\lvert\statespace\rvert$-dimensional space.

The finite Markov decision process

A Markov decision process is a controlled Markov chain: at each step the agent sees a state, picks an action, and the environment returns a reward and a next state, with the Markov property that the future depends on the past only through the current state.

The Markov property is the modelling commitment that earns us everything that follows: because the next state and reward depend only on $(S_t, A_t)$, a value function needs only one argument — the current state — and the recursion below closes on itself.

Value functions

A value function answers one question: starting here and acting under $\policy$, how much discounted reward do I expect? The state-value fixes the starting state; the action-value also fixes the first action.

The Bellman expectation equation

Everything recursive about value functions comes from one move: split the return into the immediate reward and the discounted return from the next state, then condition on what happens in one step. That conditioning is the law of total expectation, the single most-used tool in RL theory.

Read as a system of $\lvert\statespace\rvert$ linear equations in the unknowns $\{\valuefn_\policy(s)\}$, the Bellman expectation equation defines $\valuefn_\policy$. Collecting it into a single map on $\R^{\statespace}$ gives the operator we will iterate.

In vector form $\bellman^\policy v = \reward_\policy + \discount P_\policy v$ with $P_\policy$ the $\lvert\statespace\rvert\times\lvert\statespace\rvert$ transition matrix — an affine map, so its fixed point solves the linear system $(I - \discount P_\policy)\valuefn_\policy = \reward_\policy$. We will use that closed form for policy evaluation below.

Optimality: the Bellman optimality equation

So far $\policy$ was fixed. Optimal control asks for the best achievable value, and — remarkably — a single policy attains it simultaneously in every state.

The $\max$ over actions makes this equation nonlinear — there is no matrix inverse to solve it.

The contraction that makes it all work

Both operators share one property, and it is the technical heart of the chapter. Recall a map $T$ is a $\discount$-contraction in a norm if $\norm{Tu - Tv} \le \discount\,\norm{u-v}$ for all $u,v$.

The discount $\discount < 1$ is doing all the work: it is literally the contraction modulus. With $\discount = 1$ the bound is vacuous and the fixed-point theory needs extra structure (proper policies, average cost) — the subject of later asides.

This corollary is the payoff. It converts an existence question (“is there a best policy?”) into a convergent algorithm (“iterate the operator”), and it tells us the error shrinks by a factor $\discount$ every sweep.

Value iteration

Value iteration is now nothing more than iterate $\bellmanopt$ to its fixed point.

V ← 0  (any initial vector in ℝ^𝒮)
repeat:
    V ← 𝒯* V            # one sweep of the optimality operator
until ‖ΔV‖∞ < ε(1−γ)/γ   # stopping rule, justified below
return V, and the greedy policy π(s) = argmax_a [ r(s,a) + γ Σ p(s'|s,a) V(s') ]

Corollary 1.1 guarantees convergence. The stopping rule deserves a word: a small Bellman residual $\norm{V_{k+1} - V_k}_\infty$ bounds the true error, because

This telescopes from the contraction — write $V_k - \optvaluefn = \sum_{j\ge k}(V_{j+1} - V_j)$ and bound each term geometrically (Exercise 5). So stopping when $\norm{\Delta V}_\infty < \varepsilon(1-\discount)/\discount$ certifies $\norm{V - \optvaluefn}_\infty < \varepsilon$ — a guarantee we can check at runtime without knowing $\optvaluefn$. The companion experiments/python/week01/dp.py implements exactly this loop with the explicit operator as a standalone function, as the roadmap’s Week-1 task asks.

Policy iteration

Value iteration improves the value every sweep and reads off a policy at the end. Policy iteration instead alternates two exact steps on the policy, and was Howard’s original 1960 algorithm Howard (1960) :

1. Policy evaluation. Given $\policy$, solve the linear system $(I - \discount P_\policy)\,\valuefn_\policy = \reward_\policy$ for $\valuefn_\policy$ (the affine fixed point of $\bellman^\policy$ — Def. 1.4).
2. Policy improvement. Set $\policy'(s) = \argmax_a \qfn_\policy(s,a)$, greedy w.r.t. the freshly evaluated values.

Repeat until the policy stops changing. The step that makes this work is:

Because the MDP is finite there are finitely many deterministic policies, each iteration strictly improves until none does, so policy iteration terminates at an exact optimum in finitely many steps. Value iteration and policy iteration are the two poles of what Sutton & Barto Sutton & Barto (2018) call generalized policy iteration: any interleaving of “make the value consistent with the policy” and “make the policy greedy for the value” converges to the same fixed point. Week 2 studies what happens between the poles — asynchronous, Gauss–Seidel, and prioritized sweeps.

The dynamic-programming bridge

whose $\rho J$ term is the continuous-time echo of the discount $\discount$ that drove the contraction above (set $\rho = 0$ for the undiscounted limit). Value iteration is the fixed-point solver for the discrete equation; the LQR Riccati recursion (Ch. 13) is the closed-form solver for the HJB equation when $f$ is linear and $\ell$ is quadratic. Holding this identity in view is the point of the whole curriculum: control theory and RL are two dialects for the same fixed point.

What’s next

• Week 2 opens up the iteration itself: asynchronous and Gauss–Seidel value iteration, prioritized sweeping, real-time DP, and residual scheduling — the practical face of “iterate the contraction.”
• Week 3 replaces the known model $\transition$ with sampled returns (Monte Carlo), the first step away from dynamic programming toward learning.

Exercises

1. (Prove) Show that the Bellman expectation operator $\bellman^\policy$ is a $\discount$-contraction in $\norm{\cdot}_\infty$. (This is the no-$\max$ case of Theorem 1.3.)

   Solution

   For any $s$, $(\bellman^\policy u)(s) - (\bellman^\policy v)(s) = \discount \sum_{s'} \transition_\policy(s'\mid s)\,(u(s') - v(s'))$ since $\reward_\policy(s)$ cancels. Taking absolute values and using the triangle inequality with $\sum_{s'}\transition_\policy(s'\mid s)=1$, $\lvert(\bellman^\policy u)(s) - (\bellman^\policy v)(s)\rvert \le \discount \sum_{s'}\transition_\policy(s'\mid s)\norm{u-v}_\infty = \discount\norm{u-v}_\infty$. Maximizing over $s$ gives the claim. (No $\max$-nonexpansiveness step is needed, because $\bellman^\policy$ is affine.)

2. (Derive) State and prove the Bellman expectation equation for the action-value $\qfn_\policy(s,a)$.

   Solution

   Conditioning on the first transition and then the next action,

   $$\qfn_\policy(s,a) = \sum_{s',r}\transition(s',r\mid s,a)\Big[\,r + \discount \sum_{a'}\policy(a'\mid s')\,\qfn_\policy(s',a')\,\Big].$$

   The derivation is identical to Theorem 1.1 with the first action held fixed at $a$ and the recursion closing on $\qfn_\policy$ via $\valuefn_\policy(s') = \sum_{a'}\policy(a'\mid s')\qfn_\policy(s',a')$.

3. (Compute) Take the two-state MDP $\statespace=\{A,B\}$, actions $\{\text{stay},\text{switch}\}$, $\discount=0.9$, with deterministic dynamics: in $A$, stay $\to A$ ($r=0$) and switch $\to B$ ($r=0$); in $B$, stay $\to B$ ($r=1$) and switch $\to A$ ($r=0$). Evaluate the always-stay policy by solving $(I-\discount P_\policy)\valuefn_\policy = \reward_\policy$.

   Solution

   Under always-stay, $P_\policy = I$ and $\reward_\policy = (0, 1)$, so $(I - 0.9 I)\valuefn_\policy = (0,1)$ gives $0.1\,\valuefn_\policy = (0,1)$, i.e. $\valuefn_\policy = (0, 10)$. State $B$ self-loops collecting $1$ forever ($1/(1-\discount)=10$); state $A$ self-loops collecting $0$. This is the exact case the companion test asserts.

4. (Prove) Derive the geometric error bound of Corollary 1.1(2), $\norm{V_k - \optvaluefn}_\infty \le \discount^{k}\norm{V_0 - \optvaluefn}_\infty$, from the contraction property and $\bellmanopt\optvaluefn=\optvaluefn$.

   Solution

   $\norm{V_k - \optvaluefn}_\infty = \norm{\bellmanopt V_{k-1} - \bellmanopt \optvaluefn}_\infty \le \discount\norm{V_{k-1}-\optvaluefn}_\infty$ by Theorem 1.3 and the fixed-point identity. Iterating the inequality $k$ times gives the bound.

5. (Implement) Add the certified stopping rule to value iteration: stop when $\norm{\Delta V}_\infty < \varepsilon(1-\discount)/\discount$ and verify empirically that the returned $V$ satisfies $\norm{V-\optvaluefn}_\infty < \varepsilon$ on the two-state MDP (using the analytic $\optvaluefn=(9,10)$). Run against experiments/python/week01/dp.py.

   Solution

   The bound follows by writing $V_k - \optvaluefn = \sum_{j\ge k}(V_{j+1}-V_j)$ and bounding each term by the contraction: $\norm{V_{j+1}-V_j}_\infty \le \discount^{\,j-k}\norm{V_{k}-V_{k-1}}_\infty$, a geometric series summing to $\frac{\discount}{1-\discount}\norm{\Delta V}_\infty$. The companion’s value_iteration(..., tol=ε) implements this and its test asserts the resulting error is below $\varepsilon$.

6. (Extend) Show the optimal value function is the solution of the linear program $\min_{v}\sum_s v(s)$ subject to $v(s) \ge \reward(s,a) + \discount \sum_{s'}\transition(s'\mid s,a)v(s')$ for all $s,a$.

   Solution

   Feasibility means $v \ge \bellmanopt v$ pointwise; by monotonicity of $\bellmanopt$ this implies $v \ge \optvaluefn$, so $\optvaluefn$ is the smallest feasible point and minimizing $\sum_s v(s)$ selects it. The constraints linearize the $\max$ (one inequality per action), turning the nonlinear optimality equation into an LP — the basis of the dual/occupancy-measure view revisited with safe RL in Week 25.

Companion code

The Week-1 companion lives at experiments/python/week01/ (the repo’s three-language convention). It is pure NumPy at the core — the algorithms and the correctness test carry no environment dependency — with an optional Gymnasium adapter for the canonical FrozenLake showcase.

• dp.py — the Bellman optimality operator as an explicit function, plus value_iteration, policy_evaluation (exact linear solve), policy_improvement, and policy_iteration, all on a generic finite MDP (P, R, gamma).
• test_dp.py — mathematical-correctness tests: convergence to the analytic $\optvaluefn=(9,10)$ on the two-state MDP of Exercise 3, the contraction inequality of Theorem 1.3, the fixed-point identity, the geometric bound, and VI/PI agreement (FrozenLake checks run only when gymnasium is installed).
• frozenlake.py — builds (P, R, gamma) from gymnasium’s FrozenLake-v1 and runs VI and PI as a worked showcase.

# core algorithms + correctness tests (no Gymnasium needed)
PYTHONPATH=. pytest experiments/python/week01/test_dp.py -q

# canonical FrozenLake showcase (optional extra: pip install "gymnasium")
PYTHONPATH=. python experiments/python/week01/frozenlake.py