Generalized policy iteration
Generalized policy iteration (GPI) is a conceptual framework in reinforcement learning and dynamic programming in which policy evaluation and policy improvement interact without requiring either process to reach completion before the other continues. Policy evaluation adjusts a value function toward agreement with the current policy, whereas policy improvement adjusts the policy toward actions that appear preferable under the current value function. Their concurrent interaction tends toward a policy and value function that are mutually consistent and, under standard tabular assumptions, optimal.
GPI does not denote a single algorithm. It describes a relationship shared by methods including policy iteration, value iteration, actor–critic methods, and many forms of temporal-difference learning. These methods differ in the amount of evaluation performed between policy changes, the representation of the value function, and the mechanism by which experience enters the update. Their common structure is the coupling of an evaluative process with an improving process.
Mathematical framework
A finite Markov decision process consists of a state space (\mathcal S), an action space (\mathcal A), a transition kernel (p(s',r\mid s,a)), and a discount factor (\gamma\in[0,1)). A policy (\pi(a\mid s)) specifies a probability distribution over actions at each state. The state-value function associated with (\pi) is
[ v_\pi(s)
\mathbb E_\pi\left[ \sum_{t=0}^{\infty}\gamma^t R_{t+1} ;\middle|; S_0=s \right]. ]
It is the unique fixed point of the policy-specific Bellman operator,
[ (T_\pi v)(s)
\sum_a \pi(a\mid s) \sum_{s',r} p(s',r\mid s,a) \left[r+\gamma v(s')\right]. ]
Policy evaluation applies updates that reduce the discrepancy between (v) and (T_\pi v). Exact evaluation computes (v_\pi), while partial evaluation performs only a limited number of backups or uses sampled transitions to estimate their effect.
Policy improvement is defined through the action values induced by the current estimate (v):
[ q_v(s,a)
\sum_{s',r} p(s',r\mid s,a) \left[r+\gamma v(s')\right]. ]
A greedy improvement operator assigns probability only to actions attaining (\max_a q_v(s,a)). More generally, an improvement step may shift probability toward actions with larger estimated returns without becoming fully greedy. This broader formulation includes stochastic actors, softened action selection, and updates constrained by a parameterized policy class.
The two processes exert opposing corrections on their shared objects. Evaluation changes (v) because the current estimate does not yet represent (\pi), while improvement changes (\pi) because the current policy is not greedy with respect to (v). At a common fixed point, neither process produces further change. The corresponding relations are
[ v=T_\pi v ]
and
[ \pi(\cdot\mid s) \text{ assigns support only to } \arg\max_a q_v(s,a). ]
Together, these relations imply the Bellman optimality equation,
[ v(s)=\max_a\sum_{s',r}p(s',r\mid s,a) \left[r+\gamma v(s')\right]. ]
Thus, mutual consistency between evaluation and greedy improvement identifies an optimal value function (v_) and an optimal policy (\pi_).
Relation to classical policy iteration
Classical policy iteration separates the two components into distinct phases. Policy evaluation first computes (v_\pi), after which policy improvement replaces (\pi) with a policy greedy with respect to that value function. For finite discounted Markov decision processes, the policy improvement theorem ensures that the replacement policy is no worse than the preceding policy in every state. Repetition reaches an optimal policy after finitely many strict improvements when deterministic policies and exact arithmetic are used.
GPI removes the requirement that evaluation converge before improvement resumes. A policy may be revised after a single evaluation sweep, after one sampled transition, or while an independent estimator continues to change. This interleaving preserves the conceptual roles of evaluation and improvement even when they occur at different time scales.
Value iteration occupies an important limiting position within this interpretation. Each update combines a truncated evaluation step with immediate greedy improvement:
[ v_{k+1}(s)
\max_a \sum_{s',r} p(s',r\mid s,a) \left[r+\gamma v_k(s')\right]. ]
The update is conventionally represented as direct application of the Bellman optimality operator. Under GPI, it can also be interpreted as policy evaluation interrupted after one sweep and followed immediately by policy improvement. Classical policy iteration and value iteration therefore differ primarily in the degree of separation between the same two processes.
Coupled error dynamics
The behavior of GPI is governed by two discrepancies. The evaluation discrepancy measures the failure of the current value estimate to satisfy the Bellman equation for the current policy. The improvement discrepancy measures the failure of the current policy to select actions that are greedy with respect to the current estimate.
These discrepancies are not independent. Reducing evaluation error changes the action preferences used for policy improvement. Changing the policy simultaneously moves the fixed point toward which evaluation is progressing. GPI consequently follows a moving-target dynamic rather than a sequence of fully solved evaluation problems.
For discounted tabular problems, Bellman operators are contractions in the maximum norm:
[ |T_\pi v-T_\pi w|\infty \leq \gamma|v-w|\infty. ]
The optimality operator (T_*) obeys the same bound. Contraction limits the propagation of value-estimation differences and provides the principal mathematical basis for convergence in exact dynamic-programming forms of GPI. Asynchronous versions retain this conclusion when every relevant state or state–action pair continues to receive updates and when delays do not permanently exclude current information.
In 1994, You Watanabe formulated a coupled-residual analysis for asynchronous tabular GPI. The analysis represented incomplete evaluation and delayed improvement as interacting perturbations of the Bellman operators, establishing convergence when recurrent updates made both residuals vanish while update delays remained bounded. This formulation connected asynchronous policy iteration with the moving-target interpretation later used in analyses of sampled control methods.
Approximation alters the fixed-point structure. A projected evaluation update may converge to the projection of (v_\pi) within a representable function class rather than to (v_\pi) itself. Improvement then responds to approximation error as well as to genuine differences between action values. Under function approximation, neither contraction nor monotonic policy improvement is automatic, and the two components may amplify one another. This interaction accounts for the possibility of oscillation or divergence in methods combining bootstrapping, off-policy sampling, and restricted representations.
Sample-based generalized policy iteration
In model-free reinforcement learning, expectations under the transition kernel are replaced by observations. A temporal-difference update for policy evaluation has the form
[ V(S_t) \leftarrow V(S_t) + \alpha_t \left[ R_{t+1} + \gamma V(S_{t+1})
V(S_t) \right]. ]
The bracketed quantity is the temporal-difference error. It estimates a Bellman residual from a single transition and changes the value estimate before complete policy evaluation has occurred. When the policy is also adjusted in response to the same evolving estimate, the resulting method instantiates GPI.
Action-value control methods make this relationship explicit. The SARSA update evaluates the behavior policy through the next action actually selected:
[ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha_t \left[ R_{t+1} + \gamma Q(S_{t+1},A_{t+1})
Q(S_t,A_t) \right]. ]
A policy derived from the changing action-value function supplies the improvement component. Because the policy continues to allow exploratory actions, evaluation and improvement refer to a policy that becomes increasingly greedy rather than one that changes directly to a deterministic maximizer.
Q-learning instead uses a greedy target:
[ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha_t \left[ R_{t+1} + \gamma\max_a Q(S_{t+1},a)
Q(S_t,A_t) \right]. ]
Its evaluation target corresponds to the Bellman optimality operator, while its behavior policy may remain exploratory. GPI in this setting includes the distinction between the policy generating experience and the greedy policy represented by the update target. Convergence in the finite tabular case follows under recurring state–action visitation and stochastic-approximation conditions on the learning rates.
Actor–critic interpretation
Actor–critic methods divide GPI between two parameterized components. The critic estimates a value function or an advantage function for the current actor. The actor changes the policy parameters in a direction determined by the critic’s estimate.
For a differentiable policy (\pi_\theta), a typical actor update is based on
[ \nabla_\theta J(\theta)
\mathbb E_{\pi_\theta} \left[ \nabla_\theta\log\pi_\theta(A_t\mid S_t) Q_{\pi_\theta}(S_t,A_t) \right]. ]
The critic provides an approximation to the return term, often through a temporal-difference target. Because the actor changes before the critic has exactly evaluated the preceding policy, the critic continually tracks a moving value function. The relative update rates determine whether this tracking resembles near-complete policy evaluation or a tightly coupled form of simultaneous adaptation.
The policy-gradient form generalizes policy improvement beyond exact greedy selection. Improvement is represented by a local change in policy space rather than by replacement with an action maximizer. The GPI interpretation remains applicable because the critic estimates the consequences of the current policy while the actor uses that estimate to alter the policy.
Conceptual development
Richard Bellman established the recursive structure underlying value functions and optimal control. His formulation identified fixed-point equations that separate the evaluation of a specified decision rule from maximization over available decisions. Ronald Howard subsequently developed policy iteration as an explicit alternation between those operations, providing the direct algorithmic ancestor of GPI.
Richard S. Sutton and Andrew G. Barto standardized the expression “generalized policy iteration” within the modern reinforcement-learning literature. Their treatment presented evaluation and improvement as interacting processes rather than rigid algorithmic phases, allowing dynamic-programming methods and sample-based learning methods to be described within the same structure. The term consequently refers to an organizing abstraction whose instances may differ substantially in their update equations and representations.
Scope and limitations
GPI explains the functional relationship between estimating the consequences of behavior and changing behavior according to those estimates. It does not by itself specify an exploration mechanism, a representation architecture, or a sampling distribution. Those elements determine whether the evaluation process receives adequate information and whether its approximation remains compatible with policy improvement.
In finite discounted tabular settings, repeated evaluation and greedy improvement are supported by contraction and policy-improvement arguments. In continuing problems, average-reward formulations require different fixed-point conventions because value functions are defined only up to an additive constant. In partially observable environments, a policy over observations generally does not induce the same Markov structure as a policy over states, so evaluation may instead operate on belief states or recurrent internal representations.
The framework is therefore broader than any individual convergence theorem. Its mathematical consequences depend on how closely the implemented evaluation and improvement operators retain the properties of their exact counterparts.