Why a second algorithm
The unit on discounted decisions and value iteration computes the optimal value vector as the limit of Bellman updates and then reads off a greedy policy. Value iteration needs infinitely many sweeps for an exact answer. Policy iteration exploits a different fact: a fixed policy can be evaluated exactly by solving a linear system, and a greedy step against that exact value can only help. Because a finite decision problem has finitely many stationary policies, alternating evaluation and improvement must stop after finitely many rounds, at an optimal policy. This unit proves these claims. It uses the notation of the value-iteration unit: a finite state set , finite action sets , transition probabilities , rewards , a discount , and the Bellman operator .
Definitions
Definition 34.1.1
(Stationary policy and its operators)
A stationary deterministic policy is a function with for every state. Write and let be the matrix with entries ; its rows are probability vectors. For a value vector define
Definition 34.1.2
(Policy value, action value and greedy policy)
The value of , , is the expected discounted return . For a vector the action value is . A policy is greedy for if maximizes for every ; equivalently . Inequalities between vectors are componentwise.
Evaluation, monotonicity and improvement
Theorem 34.1.3
(Policy evaluation)
The matrix is invertible, , and is the unique solution of .
Proof
(Invertibility from a norm bound)
If then . Every row of is a probability vector, so and . Since , , so the matrix is invertible and has exactly one solution. Conditioning on the first transition gives , so is that solution.
Concept lensAnalytic
Evaluation as a discounted sum of expected rewards
Because , the inverse is a convergent series,
The entry is the expected reward at time when starting in , so this is the definition of as an expected discounted return, summed over time. The linear-system description is what we compute with; the series description explains why the solution is the value of the policy and why is needed.
Lemma 34.1.4
(Monotonicity of the backups)
If then and .
Proof
(Larger values give larger backups)
The weights are nonnegative, so each ; a maximum of smaller numbers is smaller.
Theorem 34.1.5
(Policy improvement)
Let be greedy for . Then . Moreover, if , then , and hence .
Proof
(Iterate the greedy backup)
Since is greedy, . Apply repeatedly using the monotonicity lemma: for all . By the contraction argument of the value-iteration unit, , the unique fixed point of . Passing to the limit in the inequality gives . If , then , so is the fixed point of , which is .
The theorem is stated for the exact value . Practical variants that evaluate inexactly need their own argument.
The algorithm and its termination
Policy iteration. Start from any policy . For :
- Evaluate: solve for .
- Improve: for each , let . If , set ; otherwise choose any maximizing action.
- If , stop and return .
The rule "keep the current action when it attains the maximum" is essential.
Theorem 34.1.6
(Policy iteration terminates at an optimal policy)
Policy iteration stops after at most evaluations, and the returned policy is optimal with value .
Proof
(Strictly increasing values cannot repeat a policy)
By the policy improvement theorem, . Suppose . If we had , the theorem would give , so and the current action would attain the maximum in every state, whence the keep-on-tie rule would give . This contradicts . So the value vectors are nondecreasing, and strictly different at each change; hence no policy is ever repeated. There are only policies, so the process stops. At the stopping policy, , i.e. , so and attains the optimal value.
Proof X-ray
What each ingredient buys
The non-obvious move is to turn "the policy changed" into "the value strictly increased". Exact evaluation and greedy improvement give . The keep-on-tie rule then guarantees that a change of policy happens only where some action is strictly better, which excludes . A sequence that is nondecreasing and different at every step never returns to an earlier value, so it never returns to an earlier policy, and finiteness of the policy set closes the argument. Drop the tie rule and the middle step fails, as the counterexample below shows; drop and even the evaluation step can fail to have a solution.
Each round costs a linear solve, by Gaussian elimination, plus for the improvement; value iteration costs only the latter per sweep but needs a number of sweeps growing like to reach accuracy . The bound is far from what is typically observed, but it is the bound proved here.
Counterexample mode
Switching among tied maximizers never stops
Claim: any improvement step that picks a maximizing action terminates. Take one state with two actions , each paying and returning to the state, and . For either policy , so , and . Both policies are optimal. A rule that always moves to the other maximizing action produces forever, although every policy is already optimal. The keep-on-tie rule stops at once, since . The repaired claim needs the rule "change an action only when a strictly better one exists".
Worked examples
Worked example 34.1.7
(Two rounds on a two-state problem)
Two states , discount . In state : action pays and moves to or with probability each; action pays and stays at . In state : action pays and stays at ; action pays and moves to or with probability each. Start with .
Evaluate . gives ; gives . So .
Improve. With : and ; and . So .
Evaluate . The equations are and . Subtracting, . Substituting in the first: , so and . Indeed .
Improve. , ; , . The current actions attain the maxima, so and the algorithm stops. Thus and the optimal policy is , after two evaluations.
Worked example 34.1.8
(The same evaluation as a matrix equation)
For in the previous example both rows of equal and . Then
with determinant . Multiplying the system by gives and . From the first, ; then , so and , the same vector as before. The check holds in both rows: and .
Worked example 34.1.9
(The discount zero edge case)
Let in the first example. Then and , so evaluation costs nothing. From we get , and the improvement compares immediate rewards: and . So with , and at the next improvement the current actions attain the maxima, so the algorithm stops after two evaluations. When the future is ignored and greedy improvement is exactly a choice of the largest immediate reward; for it is not, as the next section shows.
Common mistakes and subtle points
Common mistake
(Improving against the reward instead of against the value)
Choosing the action with the largest immediate reward ignores the future and need not improve the policy. Take a state with action (reward , stay at ) and action (reward , move to state ), and a state with a single action (reward , stay at ); . For we have and . Switching to the larger immediate reward gives with . The value-based test compares with and keeps .
Common mistake
(Using the evaluation step with discount one)
Invertibility of used . With , one state and one action that pays and stays, , so is singular and the equation has no solution. Policy iteration as stated is a discounted-case algorithm.
Exercises
Quick check
(In the first worked example, evaluate the policy .)
Solve the state- equation first.
Solution · Answer
For : , so . Then , so and . The value is .
Quick check
(The policy of the first worked example has value . Perform the improvement step. Does the new policy have a larger value?)
Compute all four action values.
Solution · Answer
With : and , so keep . and , so switch to . The new policy is , with value .
Quick check
(Start policy iteration in the first worked example from . How many evaluations are made?)
Use the values found in that example.
Solution · Answer
One. The evaluation gives , and at that value the current actions attain the maxima in both states ( and ), so and the algorithm stops at once.
Exercise 34.1.10
(In the first worked example, evaluate and perform one improvement step.)
Core
Solution(3)
- 1
Evaluate the policy
gives . Then , so and . The value is .
- 2
Compute the action values
Key step
and . Also and .
- 3
Keep or switch each action
At state , , so switch to . At state , , so keep . The new policy is .
Exercise 34.1.11
(Let , and . Show that is invertible and compute .)
Core
Solution(3)
- 1
Show invertibility by a determinant
has determinant , so it is invertible.
- 2
Solve the linear system
Key step
The equations are and . The second gives , so , giving and .
- 3
Check the Bellman equation
, and . Hence .