Core idea. Policy evaluation answers the question How good is the current policy? Policy improvement answers the next question: How can we use the value function to make better decisions? Policy iteration alternates these two ideas:
\[
\boxed{\text{evaluate }\pi_k \quad \longrightarrow \quad \text{improve greedily to get }\pi_{k+1}.}
\]
For a finite discounted Markov decision process, exact policy iteration is a mathematically clean algorithm: every nontrivial improvement produces a policy whose value is at least as large in every state, and the algorithm reaches an optimal policy after finitely many policy changes.
10.1 Learning goals
After reading this chapter, students should be able to:
define the action-value function induced by a fixed policy;
derive the greedy policy improvement rule from the one-step lookahead principle;
state and prove the policy improvement theorem;
explain the role of the advantage function in policy improvement;
implement exact policy iteration for a finite discounted MDP;
prove finite termination of exact policy iteration under a fixed tie-breaking rule;
be a finite discounted Markov decision process with \(0\leq \gamma<1\). A stationary deterministic policy is a function
\[
\pi:\mathcal S\to \mathcal A,
\]
where \(\pi(s)\) is an admissible action in state \(s\). More generally, a stationary randomized policy is a conditional distribution \(\pi(a\mid s)\) over actions.
In Chapter 6, we studied policy evaluation. For a fixed policy \(\pi\), the value function \(V^\pi\) is the unique solution of
Now suppose we know \(V^\pi\). If the agent is currently in state \(s\), should it still choose the action prescribed by \(\pi\), or should it switch to another action for the first step and then follow \(\pi\) afterward? The expected return from taking action \(a\) once and then following \(\pi\) is
This quantity is the one-step lookahead value of action \(a\) under the continuation value \(V^\pi\). If some action \(a\) satisfies
\[
q_\pi(s,a)>V^\pi(s),
\]
then taking \(a\) now and following \(\pi\) afterward is better than following \(\pi\) immediately, at least from state \(s\). Policy improvement turns this local comparison into a new global policy.
Policy improvement is the mathematical step that converts value information into decision information. The value function tells us how good it is to be in a state. The one-step lookahead calculation tells us which action best moves us toward valuable future states.
10.3 7.2 The action-value function for a fixed policy
For randomized policies, a greedy policy can place all mass on maximizing actions. If several actions tie, any probability distribution supported on the set of maximizing actions is greedy.
Tie-breaking matters in implementations. In theory, any greedy choice is valid. In code, inconsistent random tie-breaking can cause apparent cycling among equally good policies. For reproducible policy iteration, use a fixed deterministic tie-breaking rule, such as choosing the first maximizing action.
A greedy policy selects actions with maximal advantage. If
\[
\max_a A^\pi(s,a)>0,
\]
then the current policy can be improved at state \(s\) by choosing an action with positive advantage.
The advantage function is central in modern reinforcement learning. It appears in actor-critic methods, policy gradient methods, and PPO. In this chapter, it has a simpler role: it is a diagnostic for whether policy improvement has found a better action.
10.6 7.5 The policy improvement theorem
The main mathematical result is the policy improvement theorem.
Theorem 7.1: Policy improvement theorem. Let \(\pi\) and \(\pi'\) be two stationary policies for a finite discounted MDP. Suppose that
\[
Q^\pi(s,\pi'(s))\geq V^\pi(s)
\]
for every state \(s\). Then
\[
V^{\pi'}(s)\geq V^\pi(s)
\]
for every state \(s\). If the inequality is strict in at least one state and that improvement can be reached with positive probability under \(\pi'\), then the new policy is strictly better for some states.
10.6.1 Proof
The assumption says that taking the \(\pi'\) action for one step and then following \(\pi\) is no worse than following \(\pi\) immediately:
\[
(T^{\pi'})^kV^\pi\geq V^\pi
\qquad\text{for all }k\geq 1.
\]
Because \(T^{\pi'}\) is a \(\gamma\)-contraction, the sequence \((T^{\pi'})^kV^\pi\) converges to the unique fixed point of \(T^{\pi'}\), namely \(V^{\pi'}\). Taking the limit yields
\[
V^{\pi'}\geq V^\pi.
\]
This proves the theorem. \(\square\)
The proof uses only two structural properties of Bellman operators: monotonicity and contraction. This pattern appears repeatedly in dynamic programming and stochastic control.
10.7 7.6 Greedy policies and optimality
A policy \(\pi\) is greedy with respect to its own value function if
Thus \(V^\pi\) satisfies the Bellman optimality equation. Since the optimal Bellman operator is also a contraction, its fixed point is unique. Therefore,
\[
V^\pi=V^*.
\]
This proves the following result.
Theorem 7.2: Greedy self-consistency implies optimality. If a policy \(\pi\) is greedy with respect to \(V^\pi\), then \(\pi\) is optimal and \(V^\pi=V^*\).
This theorem explains the stopping rule for policy iteration. If the improvement step does not change the policy, the current policy is already optimal.
10.8 7.7 Policy iteration
Policy iteration alternates policy evaluation and policy improvement.
Exact policy iteration for a finite discounted MDP
Initialize a stationary deterministic policy \(\pi_0\).
The evaluation step is linear algebra. The improvement step is local maximization over actions. For finite state and action spaces, both steps are explicit and deterministic once a tie-breaking rule is chosen.
10.8.1 Interactive demonstration: values during policy iteration
10.9 7.8 Why policy iteration terminates
For a finite MDP with finite action sets, there are only finitely many deterministic stationary policies. Exact policy iteration produces a sequence
\[
\pi_0,\pi_1,\pi_2,\ldots
\]
with nondecreasing values:
\[
V^{\pi_{k+1}}\geq V^{\pi_k}.
\]
If \(\pi_{k+1}\neq \pi_k\) and ties are handled consistently, the new policy has strictly better value for at least one relevant state, so the algorithm cannot return to a strictly worse policy. Since only finitely many policies exist, the algorithm must stop after finitely many improvements. When it stops, the policy is greedy with respect to its own value function, hence optimal by Theorem 7.2.
Theorem 7.3: Finite convergence of exact policy iteration. In a finite discounted MDP, exact policy iteration with deterministic tie-breaking terminates after finitely many policy improvements at an optimal deterministic stationary policy.
This is a strong result: policy iteration is not merely asymptotically correct in the exact finite setting. It reaches an optimal policy after a finite number of policy changes.
10.10 7.9 Running example: study-planning MDP
We continue the three-state study-planning MDP. The states are
The action \(C\) is safer and steadier. The action \(H\) is more aggressive: it may produce larger reward in some states, but it can also increase instability. Policy iteration will decide which action is best in each state after accounting for future consequences.
10.10.1 Python example: exact policy evaluation
import numpy as npimport pandas as pdstates = ["Review", "Practice", "Mastery"]actions = ["C", "H"]gamma =0.90P = {"C": np.array([ [0.70, 0.25, 0.05], [0.15, 0.70, 0.15], [0.05, 0.10, 0.85] ]),"H": np.array([ [0.45, 0.45, 0.10], [0.20, 0.40, 0.40], [0.10, 0.20, 0.70] ])}r = {"C": np.array([1.0, 2.0, 5.0]),"H": np.array([0.0, 4.0, 6.0])}def evaluate_policy(policy, gamma=0.90):"""Exact policy evaluation for a deterministic policy.""" P_pi = np.vstack([P[policy[i]][i] for i inrange(len(states))]) r_pi = np.array([r[policy[i]][i] for i inrange(len(states))]) V = np.linalg.solve(np.eye(len(states)) - gamma * P_pi, r_pi)return Vinitial_policy = np.array(["C", "C", "C"])V_initial = evaluate_policy(initial_policy, gamma)pd.DataFrame({"state": states, "policy": initial_policy, "V^pi": V_initial})
state
policy
V^pi
0
Review
C
23.707692
1
Practice
C
27.288112
2
Mastery
C
36.267133
10.10.2 Python example: one-step lookahead and greedy improvement
def q_from_v(V, gamma=0.90):"""Compute Q(s,a) from a value vector V.""" Q = np.zeros((len(states), len(actions)))for i, s inenumerate(states):for j, a inenumerate(actions): Q[i, j] = r[a][i] + gamma * P[a][i] @ Vreturn Qdef improve_policy(V, tie_break="first"):"""Greedy improvement with deterministic tie-breaking.""" Q = q_from_v(V, gamma) best_indices = np.argmax(Q, axis=1) improved = np.array([actions[j] for j in best_indices])return improved, Qimproved_policy, Q_initial = improve_policy(V_initial)advantage = Q_initial - V_initial[:, None]pd.DataFrame( np.column_stack([Q_initial, advantage]), index=states, columns=["Q(C)", "Q(H)", "A(C)", "A(H)"])
The table shows which states are changed by the greedy improvement step. A positive advantage for \(H\) means that switching from \(C\) to \(H\) improves the one-step lookahead value in that state.
10.11 7.10 Full policy iteration in Python
The full exact algorithm is short because the mathematical structure is strong.
def policy_iteration(initial_policy, gamma=0.90, max_iter=20): policy = np.array(initial_policy, dtype=object) history = []for k inrange(max_iter): V = evaluate_policy(policy, gamma) new_policy, Q = improve_policy(V) history.append({"iteration": k,"policy": policy.copy(),"value": V.copy(),"Q": Q.copy() })if np.array_equal(new_policy, policy):break policy = new_policyreturn policy, V, historyoptimal_policy, optimal_value, history = policy_iteration(["C", "C", "C"], gamma)summary_rows = []for item in history: row = {"iteration": item["iteration"],"policy": "".join(item["policy"]) }for state, val inzip(states, item["value"]): row[f"V({state})"] = val summary_rows.append(row)pd.DataFrame(summary_rows)
Value iteration instead applies the optimal Bellman operator repeatedly:
\[
V_{k+1}=TV_k.
\]
Policy iteration may require solving a linear system at each iteration, but it often needs very few policy improvements. Value iteration avoids exact linear solves but may need many Bellman backups, especially when \(\gamma\) is close to \(1\).
Method
Main update
Computational character
Mathematical view
Policy evaluation
\(V^{\pi}=T^\pi V^{\pi}\)
linear solve or fixed-point iteration
prediction under fixed policy
Policy improvement
\(\pi'(s)\in\arg\max_a Q^\pi(s,a)\)
local maximization
greedy one-step lookahead
Policy iteration
evaluation + improvement
few outer iterations, heavier inner step
Newton-like dynamic programming
Value iteration
\(V_{k+1}=TV_k\)
many cheap Bellman backups
fixed-point iteration
The phrase Newton-like is informal but useful: policy iteration uses an exact solution for the current policy before updating the decision rule, while value iteration makes smaller repeated fixed-point updates.
10.13 7.12 Modified policy iteration
Exact policy iteration can be expensive when the state space is large because policy evaluation requires solving
\[
(I-\gamma P_\pi)V=r_\pi.
\]
Modified policy iteration replaces exact evaluation by a limited number of Bellman expectation updates.
Modified policy iteration
Given a policy \(\pi_k\) and an approximate value vector \(V_k\):
In exact policy iteration, evaluation and improvement are cleanly separated. Modern reinforcement learning often interleaves approximate versions of both steps. This broader idea is called generalized policy iteration.
The two forces are:
Evaluation pressure: make \(V\) more consistent with the current policy \(\pi\).
Improvement pressure: make \(\pi\) greedier with respect to the current value estimates.
Symbolically,
\[
V \approx V^\pi,
\qquad
\pi \approx \operatorname{Greedy}(V).
\]
Temporal-difference control, SARSA, Q-learning, actor-critic algorithms, and many deep RL algorithms can be viewed as approximate generalized policy iteration schemes.
Generalized policy iteration is not one algorithm. It is a structural principle: estimate values and improve decisions repeatedly, even if neither step is exact.
10.15 7.14 Statistical viewpoint
For MS Statistics students, policy improvement should raise an important question: what if the value function is estimated from data?
Suppose \(\widehat V\) estimates \(V^\pi\). The greedy policy based on \(\widehat V\) is
If \(\widehat A^\pi(s,a)\) is positive but close to zero, the improvement may be dominated by estimation noise. This is one motivation for conservative policy improvement and trust-region methods studied later in the book.
10.16 7.15 AI-assisted learning components
AI tools can help students study policy iteration, but the mathematical responsibilities should remain explicit.
AI-assisted derivation prompt
Ask an AI system:
Prove the policy improvement theorem for a finite discounted MDP. Use only monotonicity and contraction of the Bellman policy operator. Clearly identify where the assumption \(Q^\pi(s,\pi'(s))\geq V^\pi(s)\) is used.
Then check:
Did the proof define \(T^{\pi'}\) correctly?
Did it use componentwise inequality?
Did it justify convergence to \(V^{\pi'}\)?
Did it confuse \(V^\pi\) with \(V^{\pi'}\)?
AI-assisted coding prompt
Ask an AI system:
Write Python code for exact policy iteration for a finite discounted MDP with transition array P[a, s, s_next], reward array r[s, a], and discount factor gamma. Include deterministic tie-breaking and a Bellman residual check.
Then test the code on a two-state MDP whose optimal policy can be verified by hand.
Common AI mistakes. AI-generated explanations sometimes claim that policy improvement works because the greedy action is better only in the current state. The theorem is stronger: local one-step improvement in every state, combined with Bellman monotonicity and contraction, implies global value improvement.
10.17 7.16 Summary
Policy improvement is the step that turns value functions into better decisions. Given \(V^\pi\), the one-step lookahead value
compares actions using both immediate reward and future value. A greedy policy chooses actions that maximize this quantity. The policy improvement theorem proves that such a policy is no worse than the old policy. Exact policy iteration alternates exact evaluation and greedy improvement, and for finite discounted MDPs it terminates at an optimal policy after finitely many improvements.
Explain in words why \(Q^\pi(s,a)\) is a one-step lookahead quantity.
Why does policy improvement require \(V^\pi\) rather than only immediate rewards?
Give an example where an action has lower immediate reward but higher long-term value.
Explain why a policy that is greedy with respect to its own value function must be optimal.
Compare policy iteration and value iteration from the viewpoint of fixed-point computation.
Why can random tie-breaking make policy iteration output look unstable even when all policies are optimal?
10.19 7.18 Mathematical exercises
Prove that the Bellman policy operator \(T^\pi\) is monotone: if \(U\geq W\), then \(T^\pi U\geq T^\pi W\).
Prove the policy improvement theorem for randomized policies.
Show that if \(\pi'\) is greedy with respect to \(V^\pi\), then \(T^{\pi'}V^\pi=TV^\pi\).
Prove that if \(V^\pi=TV^\pi\), then \(V^\pi=V^*\).
For a two-state, two-action MDP, write out all deterministic policies and show how policy iteration moves among them.
Suppose \(\|\widehat V-V^\pi\|_\infty\leq \epsilon\). Bound the error in the one-step lookahead values \(Q^\pi(s,a)\) computed from \(\widehat V\).
Derive a sufficient condition involving the action gap under which the greedy policy based on \(\widehat V\) agrees with the greedy policy based on \(V^\pi\).
10.20 7.19 Computational exercises
Implement exact policy iteration for the study-planning MDP and run it from all \(2^3\) deterministic initial policies.
Modify the reward vector \(r^H\) and determine when action \(H\) becomes optimal in every state.
Implement randomized tie-breaking and compare the sequence of policies with deterministic tie-breaking.
Implement modified policy iteration with \(m=1,2,5,10\) evaluation sweeps and compare convergence.
Compute and plot the Bellman residual at each iteration.
Add small noise to value estimates before the improvement step and study how often the greedy action changes.
Build a random finite MDP with five states and three actions. Compare policy iteration and value iteration in terms of number of Bellman backups.
10.21 7.20 AI-assisted exercises
Ask an AI tool to produce a proof of the policy improvement theorem. Identify any missing assumptions or unclear inequalities.
Ask an AI tool to generate a two-state MDP where the action with the largest immediate reward is not optimal. Verify the example by computing values.
Ask an AI tool to explain the difference between policy iteration and value iteration for a statistics audience. Rewrite the explanation using conditional expectations.
Ask an AI tool to debug a policy iteration implementation with an intentionally incorrect transition matrix normalization.
Ask an AI tool to generate a small MDP where two actions tie under the optimal policy. Discuss how tie-breaking affects the returned policy but not the value function.
10.22 7.21 Notes for instructors
For MA Applied Math students, emphasize Bellman operators, monotonicity, contraction, and finite termination. The policy improvement theorem is an excellent place to connect order-preserving maps and fixed-point theory.
For MS Statistics students, emphasize that policy improvement is sensitive to estimation error when action gaps are small. This prepares students for sample-based control, off-policy evaluation, conservative improvement, and offline RL.
A useful lecture sequence is:
define \(Q^\pi\) from \(V^\pi\);
derive the greedy improvement rule;
prove policy improvement using monotonicity and contraction;
implement exact policy iteration on a three-state MDP;
discuss statistical uncertainty and approximate policy iteration.