Policy Improvement and Policy Iteration

From values to a better policy

Suppose you have evaluated a policy and now know its value function. Can you do better? Policy improvement says: yes, almost always. In each state, look one step ahead using the action-value function — the value of taking each action and then following the old policy — and switch to whichever action looks best. The new policy that always picks the highest-value action is the greedy policy with respect to those values.

\pi'(s) = \arg\max_a \sum_{s',r} p(s',r \mid s,a)\left[r + \gamma V^\pi(s')\right]

Policy improvement: in each state pick the action that maximizes the one-step lookahead value.

This feels almost too simple — surely greedily switching actions one state at a time could backfire, since changing what you do here changes what is reachable later? The deep result of this guide is that it never backfires.

The policy improvement theorem

The policy improvement theorem guarantees that the greedy policy is at least as good as the original in every state — never worse anywhere. And if the greedy policy is not strictly better somewhere, then both policies are already optimal. So each round of 'evaluate, then go greedy' either improves the policy or proves you are done.

q_\pi\bigl(s,\pi'(s)\bigr) \ge v_\pi(s) \quad\Longrightarrow\quad v_{\pi'}(s) \ge v_\pi(s)\ \ \forall s

The policy improvement theorem: if the greedy action is no worse at every state, the new policy dominates the old one everywhere.

Policy iteration: the evaluate–improve loop

Policy iteration simply alternates the two steps until the policy stops changing. Because there are only finitely many deterministic policies and each round strictly improves (or halts), it reaches the optimal policy in a finite number of iterations — often surprisingly few.

Initialise an arbitrary policy.
Policy evaluation: compute the value function of the current policy (the sweep from guide 2).
Policy improvement: set the new policy greedy with respect to that value function.
If the policy is unchanged, stop — it is optimal. Otherwise go back to step 2.

\pi_0 \xrightarrow{\;E\;} v_{\pi_0} \xrightarrow{\;I\;} \pi_1 \xrightarrow{\;E\;} v_{\pi_1} \xrightarrow{\;I\;} \cdots \xrightarrow{\;I\;} \pi_* \xrightarrow{\;E\;} v_*

Policy iteration: alternate evaluation (E) and improvement (I), and policy and value climb together to the optimal pair.

Generalized policy iteration

Here is the unifying idea that outlives DP entirely. You do not need to evaluate the policy fully before improving it. Generalized policy iteration (GPI) is the loose dance of any evaluation process and any improvement process pulling on each other — a few sweeps of evaluation, a partial greedy update, repeated in any granularity. As long as both keep nudging toward consistency, the pair converges to the optimal value function and policy.