Generalized Policy Iteration
The apparent conflict is temporary. The long-run purpose of both processes is to reach one joint solution: an optimal policy together with an optimal value function.
Two Processes, One Search
Generalized Policy Iteration, or GPI, is a search conducted by two interacting processes. Policy evaluation asks the value function to match the current policy. Policy improvement asks the policy to become greedy with respect to the current value function. Because each process changes one side of the policy-value pair, progress by one process can temporarily disturb the condition that the other process was establishing.
The apparent conflict is temporary. The long-run purpose of both processes is to reach one joint solution: an optimal policy together with an optimal value function.
Tracing the First Interaction
An Abstract P-V Trace
Trace what happens when improvement changes policy P and evaluation then responds.
- 1Start
Begin with a policy P and a value function V. At this point, V represents the current policy to the extent established by evaluation.
- 2Improve
Improvement examines the current value function and changes P so that the policy becomes greedy with respect to that value function.
- 3Disturb
The changed policy is not necessarily the policy that the existing V evaluated. The previous V can therefore become inaccurate for the changed policy.
- 4Evaluate
Evaluation responds to the changed P by making the value function consistent with that policy.
- 5Continue
The updated value function can affect whether P is still greedy. The two processes continue interacting until their requirements are satisfied together.
Improvement responds to the value function, while evaluation responds to the policy. Neither process can be understood as permanently independent of the other.
The important direction of dependence is simple: improvement reads the value function and changes the policy; evaluation reads the changed policy and adjusts the value function. A policy change can invalidate the value function's fit to that policy, so evaluation is needed again.
Two Requirements in Tension
Evaluation and improvement impose different requirements on the same pair of objects. Evaluation requires the value function to be consistent with the current policy. Improvement requires the policy to be greedy with respect to the current value function. These requirements can temporarily pull in opposing directions because satisfying one can disturb the other.
When One Side Disturbs the Other
Suppose evaluation has made V consistent with policy P. Improvement then uses V to change P. The existing V has not automatically been recomputed for the changed policy. It may therefore describe the old policy rather than the new one. This is the first form of temporary conflict: improvement makes progress toward greediness, but its policy change can make the current value function inaccurate.
The reverse disturbance is also possible. Evaluation can make V consistent with the current policy, but the updated V can change the policy's relationship to the values. A policy that was greedy with respect to an earlier value function may no longer be greedy with respect to the newly evaluated one. Thus evaluation can remove the condition that improvement was trying to establish.
The Stabilized Pair
GPI stabilizes when the policy is greedy with respect to its own evaluation function. This condition links the two objects rather than declaring one process complete in isolation: the value function is the evaluation of the policy, and the policy is greedy with respect to that value function.
From Stability to Optimality
At stabilization, the Bellman optimality equation, identified in the source as equation (4.1), holds. The equation is the mathematical confirmation of the joint solution: the stabilized value function and policy are optimal. The interaction between evaluation and improvement explains how the pair reaches this condition; the equation identifies what is true once the condition has been reached.
Common Reasoning Errors
Common mistake Treating policy improvement as a permanent final step.
What it looks likeA changed policy is assumed to remain fully supported by the value function that existed before the change.
Why it failsChanging the policy can make the current value function inaccurate for that changed policy.
Do this insteadRecognize that evaluation must respond to the changed policy.
Common mistake Assuming evaluation can only help improvement.
What it looks likeOnce the value function has been made consistent with a policy, the policy is assumed to remain greedy automatically.
Why it failsThe updated value function can cause the policy to stop being greedy with respect to it.
Do this insteadCheck the relationship between the policy and its updated evaluation.
Common mistake Describing GPI as two independent procedures.
What it looks likeEvaluation and improvement are treated as if one can finish without affecting the other.
Why it failsEach process changes the conditions used by the other.
Do this insteadTrack the feedback: improvement responds to V, and evaluation responds to P.
Common mistake Confusing temporary disagreement with the final goal.
What it looks likeThe disturbances caused by alternating processes are taken to mean that GPI seeks two permanently opposing outcomes.
Why it failsThe processes cooperate toward an optimal value function and an optimal policy.
Do this insteadSeparate local disruption from the eventual joint solution.
Common mistake Defining convergence as one process completing first.
What it looks likeA policy is called converged immediately after one improvement step.
Why it failsConvergence requires the policy to be greedy with respect to its own evaluation function.
Do this insteadLook for simultaneous satisfaction of both requirements.
Check Your Reasoning
A value function V is consistent with policy P. Improvement changes P into a new policy. Explain why V may now be inaccurate, what evaluation must do next, and why the newly evaluated V might require another improvement check.
Hints
- Start with the fact that V represented the earlier policy.
- Identify which process responds to the changed policy.
- Finish by checking whether the policy is greedy with respect to the updated value function.
What do you think happens?
If evaluation has made V consistent with P, does that alone guarantee that P is greedy with respect to the updated V?
Reveal answer
No, evaluation can change the value function and remove the policy's greediness.
Evaluation makes the value function consistent with the policy. Improvement separately asks whether the policy is greedy with respect to that value function. Because the updated value function can alter that relationship, both requirements must be checked together.
Key Takeaways
- 1Evaluation makes the value function consistent with the current policy.
- 2Improvement makes the policy greedy with respect to the current value function.
- 3Changing either side can temporarily disturb the requirement established by the other side.
- 4GPI stabilizes when the policy is greedy with respect to its own evaluation function.
- 5At stabilization, the Bellman optimality equation holds, so the policy-value pair is optimal.
At a glance
- Generalized Policy Iteration is the repeated interaction of policy evaluation and policy improvement.
- Improvement can make the current value function inaccurate by changing the policy it should describe.
- Evaluation can remove a policy's greediness by changing the value function against which greediness is judged.
- The processes stabilize when the policy is greedy with respect to its own evaluation function.
- That stabilized pair satisfies the Bellman optimality equation and is optimal.