Planning with a Known Model

From Equation to Iteration

A Bellman equation is a recursive identity, a true statement a value function must satisfy, and not yet a procedure for computing one. This chapter closes that gap, and does it three times: for evaluating a fixed policy, for improving one, and for collapsing both into a single backup.

Everything here assumes the environment’s dynamics $P(s' \mid s,a)$ and $R(s,a)$ are fully known in advance. That assumption matters enough to name up front: this is planning, not yet learning from sampled experience. The first chapter drew that line as the model-based/model-free split, and this chapter lives entirely on the known-model side of it. The last section returns to what happens when the assumption is dropped, which is the reason the rest of this series exists.

One idea carries all three algorithms, and it is worth stating before any of them: each is a fixed-point iteration of an operator that turns out to be a contraction. Once that is established, existence, uniqueness, and convergence all arrive together from a single theorem, and never have to be argued again.

Policy Evaluation

DefinitionPolicy Evaluation

Given a Markov decision process and a fixed policy $\pi$, policy evaluation is the problem of computing $V^\pi(s)$ (or $Q^\pi(s,a)$) for every state. This is the prediction problem: how good is this given policy? Not yet the control problem of finding a better one.

Fixing $\pi$ collapses the MDP back down a rung on the Markov ladder: averaging the action out with $\pi$ turns an MDP into the Markov reward process it induces,

$$P^\pi(s' \mid s) = \sum_a \pi(a \mid s)P(s' \mid s,a), \qquad R^\pi(s) = \sum_a \pi(a \mid s)R(s,a),$$

and $V^\pi$ is exactly the value function of that induced MRP. This is a useful thing to notice, because it means policy evaluation is not a new problem: it is the same fixed-point equation from the previous chapter, just restricted to one fixed policy at a time.

DefinitionBellman Expectation Operator

Define the operator $T^\pi$ acting on any function $V: S \to \mathbb{R}$ by

$$(T^\pi V)(s) = \sum_a \pi(a \mid s) \left[ R(s,a) + \gamma \sum_{s'}P(s' \mid s,a)V(s') \right]$$

The Bellman expectation equation is now a one-line statement: $V^\pi$ is a fixed point of $T^\pi$, i.e. $T^\pi V^\pi = V^\pi$. Restating the equation as a fixed-point condition on an operator is what makes its computability provable, not just plausible.

LemmaThe Bellman Expectation Operator Is a Contraction

For any two functions $V_1, V_2 : S \to \mathbb{R}$, measuring distance by the sup-norm $\lVert V \rVert_\infty = \max_s \lvert V(s) \rvert$,

$$\lVert T^\pi V_1 - T^\pi V_2 \rVert_\infty \le \gamma \lVert V_1 - V_2 \rVert_\infty$$

Proof

For any state $s$,

$$(T^\pi V_1)(s) - (T^\pi V_2)(s) = \gamma \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s,a) \big(V_1(s') - V_2(s')\big),$$

since the reward terms $R(s,a)$ cancel. Bounding each difference $V_1(s')-V_2(s')$ by $\lVert V_1 - V_2\rVert_\infty$ and pulling that bound out of both sums,

$$\big| (T^\pi V_1)(s) - (T^\pi V_2)(s) \big| \le \gamma \lVert V_1 - V_2 \rVert_\infty \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s,a).$$

Both $\pi(\cdot \mid s)$ and $P(\cdot \mid s,a)$ are probability distributions, so both inner and outer sums equal $1$, leaving $\gamma \lVert V_1 - V_2 \rVert_\infty$. This bound holds for every $s$, hence it holds for the maximum over $s$ on the left-hand side as well.

RemarkWhy a Contraction Guarantees Convergence

This is where the payoff arrives. $T^\pi$ is a $\gamma$-contraction with $\gamma \in [0,1)$ on $(\mathbb{R}^{|S|}, \lVert \cdot \rVert_\infty)$, which is a complete metric space. The Banach fixed-point theorem then applies directly: $T^\pi$ has a unique fixed point, and starting from any initial guess $V_0$, the sequence $V_{k+1} = T^\pi V_k$ converges to that fixed point, at the geometric rate $\lVert V_k - V^\pi \rVert_\infty \le \gamma^k \lVert V_0 - V^\pi \rVert_\infty$. This single fact is simultaneously the reason the Bellman expectation equation has a unique solution at all, and the reason repeatedly applying it as an update rule is guaranteed to find that solution.

AlgorithmIterative Policy Evaluation

Initialize $V_0$ arbitrarily. Repeat, for $k = 0, 1, 2, \dots$,

$$V_{k+1}(s) = \sum_a \pi(a \mid s)\left[R(s,a) + \gamma \sum_{s'}P(s' \mid s,a)V_k(s')\right] \qquad \text{for every } s,$$

until $V_k$ stops changing appreciably. The lemma above guarantees $V_k \to V^\pi$.

From Knowing a Policy’s Value to Improving It

Knowing $V^\pi$ is not the same as knowing whether $\pi$ is any good. The next question is how to use $V^\pi$ to produce a strictly better policy, and, remarkably, a purely greedy, one-step-lookahead rule turns out to be enough.

DefinitionPolicy Improvement

Given $Q^\pi$, the greedy policy with respect to it is

$$\pi'(s) = \arg\max_a Q^\pi(s,a)$$

That this greedy policy is never worse, and is strictly better whenever there was any room to improve, is not obvious on its face, since $\pi'$ is defined using only one step of lookahead against a value function that itself already assumes the old policy $\pi$ is followed forever after. The following theorem is the reason it works anyway.

TheoremPolicy Improvement Theorem

If $\pi'(s) = \arg\max_a Q^\pi(s,a)$ for every state $s$, then $V^{\pi'}(s) \ge V^\pi(s)$ for every state $s$.

Proof

Since $V^\pi(s)$ is an average of $Q^\pi(s,a)$ over $a \sim \pi(\cdot \mid s)$, it can never exceed the best available action value at $s$, and by construction $\pi'(s)$ achieves that best value:

$$V^\pi(s) \le \max_a Q^\pi(s,a) = Q^\pi(s, \pi'(s)).$$

Expanding the right-hand side with the action-value Bellman equation, but with the action fixed to $\pi'(s)$,

$$V^\pi(s) \le R(s,\pi'(s)) + \gamma \sum_{s'} P(s' \mid s,\pi'(s))\, V^\pi(s').$$

The same inequality, $V^\pi(x) \le Q^\pi(x,\pi'(x))$, holds at every state $x$, including each $s'$ appearing on the right. Substituting it in for $V^\pi(s')$ replaces the value one step out with the reward earned by following $\pi'$ for one more step, plus a still-looser bound two steps out:

$$V^\pi(s) \le \mathbb{E}_{\pi'}\big[R_{t+1} + \gamma R_{t+2} + \gamma^2 V^\pi(S_{t+2}) \mid S_t = s\big],$$

where the expectation tracks the environment’s transitions while every action along the way is chosen by $\pi'$. Repeating this substitution inductively $k$ times gives, for every $k$,

$$V^\pi(s) \le \mathbb{E}_{\pi'}\left[\sum_{i=1}^{k} \gamma^{i-1} R_{t+i} + \gamma^{k} V^\pi(S_{t+k}) \,\middle|\, S_t = s\right].$$

Assuming $V^\pi$ is bounded (true whenever rewards are bounded and $\gamma < 1$), the tail term $\gamma^{k} V^\pi(S_{t+k}) \to 0$ as $k \to \infty$. Taking the limit turns the finite partial sum into the full discounted return under $\pi'$:

$$V^\pi(s) \le \mathbb{E}_{\pi'}\big[G_t \mid S_t = s\big] = V^{\pi'}(s).$$

CorollaryNo Improvement Means Optimal

If policy improvement produces no change, $\pi' = \pi$, then $V^\pi(s) = \max_a Q^\pi(s,a)$ for every $s$, which is exactly the Bellman optimality equation. Since that equation’s solution is unique, $V^\pi = V^*$, and $\pi$ is an optimal policy.

This corollary is what turns “alternate evaluation and improvement” into a genuine control algorithm with a stopping condition, rather than a heuristic that might loop forever.

AlgorithmPolicy Iteration

Initialize $\pi_0$ arbitrarily. Repeat, for $k = 0, 1, 2, \dots$:

1. Evaluate: compute $V^{\pi_k}$ (via iterative policy evaluation, or exact linear-system solution).
2. Improve: set $\pi_{k+1}(s) = \arg\max_a Q^{\pi_k}(s,a)$ for every $s$.

Stop when $\pi_{k+1} = \pi_k$; by the corollary above, $\pi_k$ is then optimal.

Each intermediate $\pi_k$ in this loop is a genuine, fully-evaluated policy, a meaningful object in its own right, not just scratch work. That property is exactly what the next section deliberately gives up.

Optimality Backups Without Waiting

Policy iteration pays for its clean intermediate policies with an inner loop: full convergence of policy evaluation before every single improvement step. Value iteration collapses evaluation and improvement into a single backup, applied directly to the optimality equation rather than the expectation equation.

DefinitionBellman Optimality Operator

$$(T^* V)(s) = \max_a \left[R(s,a) + \gamma \sum_{s'}P(s' \mid s,a)V(s')\right]$$

$V^*$ is the fixed point of $T^*$. This is just the Bellman optimality equation, restated as $T^*V^* = V^*$. Showing $T^*$ is also a contraction needs one extra piece of machinery beyond the proof for $T^\pi$ above, because a $\max$ over actions is not linear the way an average weighted by $\pi$ is.

LemmaMaxima Do Not Diverge More Than Their Arguments

For any two functions $f, g$ on a common finite domain,

$$\left| \max_a f(a) - \max_a g(a) \right| \le \max_a \left| f(a) - g(a) \right|$$

Proof

Let $a^* = \arg\max_a f(a)$. Then

$$\max_a f(a) - \max_a g(a) = f(a^*) - \max_a g(a) \le f(a^*) - g(a^*) \le \max_a |f(a)-g(a)|,$$

using $\max_a g(a) \ge g(a^*)$ for the middle inequality. Swapping the roles of $f$ and $g$ gives the same bound on $\max_a g(a) - \max_a f(a)$. Combining both directions gives the claimed absolute-value bound.

CorollaryThe Bellman Optimality Operator Is Also a Contraction

$\lVert T^*V_1 - T^*V_2\rVert_\infty \le \gamma \lVert V_1-V_2\rVert_\infty$.

Proof

Fix a state $s$ and apply the lemma just proved, with $f(a) = R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V_1(s')$ and $g(a) = R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V_2(s')$, so that $\max_a f(a) = (T^*V_1)(s)$ and $\max_a g(a) = (T^*V_2)(s)$:

$$\big|(T^*V_1)(s) - (T^*V_2)(s)\big| = \left|\max_a f(a) - \max_a g(a)\right| \le \max_a |f(a) - g(a)|.$$

The reward terms cancel inside $f(a)-g(a)$, leaving $f(a)-g(a) = \gamma\sum_{s'}P(s'\mid s,a)\big(V_1(s')-V_2(s')\big)$ for every fixed $a$, exactly the quantity bounded in the proof that $T^\pi$ is a contraction. The same steps apply verbatim: bound each $V_1(s')-V_2(s')$ by $\lVert V_1-V_2\rVert_\infty$ and use that $P(\cdot\mid s,a)$ sums to $1$, giving $|f(a)-g(a)| \le \gamma\lVert V_1-V_2\rVert_\infty$ for every $a$, and hence $\max_a|f(a)-g(a)| \le \gamma\lVert V_1-V_2\rVert_\infty$. Combining with the first inequality gives $|(T^*V_1)(s)-(T^*V_2)(s)| \le \gamma\lVert V_1-V_2\rVert_\infty$ for every $s$, hence the same bound on the sup-norm.

Because $T^*$ is a $\gamma$-contraction on the same complete metric space, the Banach fixed-point argument applies again, word for word: $T^*$ has a unique fixed point, and it converges to it geometrically from any starting guess, regardless of whether that guess corresponds to the value of any actual policy.

AlgorithmValue Iteration

Initialize $V_0$ arbitrarily. Repeat, for $k = 0, 1, 2, \dots$,

$$V_{k+1}(s) = \max_a \left[R(s,a) + \gamma \sum_{s'}P(s' \mid s,a)V_k(s')\right] \qquad \text{for every } s,$$

until $V_k$ stops changing appreciably; then extract a policy,

$$\pi^*(s) = \arg\max_a \left[R(s,a) + \gamma \sum_{s'}P(s' \mid s,a)V^*(s')\right].$$

Unlike policy iteration, the intermediate $V_k$ produced along the way need not equal the value function of any policy. They are transient planning estimates being pushed toward $V^*$, not evaluations of anything an agent could currently be said to be doing. The trade is explicit: policy iteration keeps a meaningful policy at every step at the cost of a full inner evaluation loop; value iteration runs one backup per outer step at the cost of intermediate values that mean nothing on their own until convergence.

Where Planning Stops Being Enough

Every method in this chapter assumed the transition model $P(s' \mid s,a)$ and reward function $R(s,a)$ were fully known in advance. That is what made backing up an exact expectation, or an exact maximum, over next states a well-defined computation at all.

The moment that assumption is dropped, and the environment must be interacted with and sampled from rather than consulted as a known function, none of these algorithms are directly computable, since none of them can evaluate $\sum_{s'}P(s'\mid s,a)(\cdot)$ without knowing $P$. Notice how total the failure is: it is not that the algorithms get slower or less accurate, it is that a single term in every one of them stops being writable.

This is exactly the gap that sampling-based methods exist to close: estimate the same underlying quantities, returns and values, from rollouts, when a model is not available to back up against directly. Policies as Probability Distributions builds the object those methods optimize, and Policy Gradient derives how.

References

• Datawhale Easy RL, Chapter 2
• Bellman, R. (1957). Dynamic Programming. Princeton University Press.
• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), Chapter 4.