Policy Iteration · aiwiki.page

Policy iteration is a dynamic programming algorithm for solving Markov decision processes (MDPs). It alternates between calculating the long-term consequences of a policy and replacing its decisions with actions that improve those consequences. In finite, discounted problems with known dynamics, exact policy iteration obtains an optimal policy after finitely many improvement steps. It is also a foundational organizing principle in reinforcement learning, where evaluation and improvement may instead use experience and approximation. (andrew.cmu.edu)

Mathematical setting

The standard setting is a discrete-time MDP with a finite state set $S$ , a finite set of available actions $A(s)$ , transition probabilities $P(s' \mid s,a)$ , and expected immediate rewards $r(s,a)$ . The Markov property means that the next-state distribution depends on the current state and action rather than the entire preceding history. A discount factor $0\leq\gamma<1$ weights later rewards less heavily. (introml.mit.edu)

A stationary deterministic policy selects an action $\pi(s)$ whenever state $s$ occurs. Its value function is the expected value of the discounted reward sequence:

V^\pi(s)= \mathbb E_\pi\!\left[ \sum_{t=0}^{\infty}\gamma^tR_{t+1} \,\middle|\,S_0=s \right].

For bounded rewards, discounting makes this infinite sum well defined. The objective is to find a policy whose value is maximal from every state. In this finite discounted setting, a stationary deterministic optimal policy exists; randomizing actions is not necessary to attain optimality. (introml.mit.edu)

Policy evaluation

Policy evaluation computes $V^\pi$ for the current policy without changing its decisions. The value satisfies the Bellman equation

V^\pi(s)=r(s,\pi(s)) +\gamma\sum_{s'}P(s'\mid s,\pi(s))V^\pi(s').

Writing rewards as a vector $r^\pi$ and policy-dependent transition probabilities as a transition matrix $P^\pi$ gives

(I-\gamma P^\pi)V^\pi=r^\pi.

Here $I$ is the identity matrix. Because $\gamma<1$ , the coefficient matrix is invertible, and evaluation reduces to solving a system of linear equations. The formal solution is $V^\pi=(I-\gamma P^\pi)^{-1}r^\pi$ , although implementations can solve the system without explicitly forming an inverse. (gradml.mit.edu)

Alternatively, evaluation repeatedly applies the fixed-policy update

v_{j+1}=r^\pi+\gamma P^\pi v_j.

This update is a contraction mapping in the maximum norm and converges to the unique fixed point $V^\pi$ . A numerical implementation usually stops when successive values or the Bellman residual fall below a tolerance. Such truncated evaluation differs from the exact evaluation assumed in the simplest convergence theorem. (web.mit.edu)

Policy improvement and algorithm

Policy improvement compares actions using the evaluated policy:

Q^\pi(s,a)=r(s,a) +\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s').

This quantity includes the immediate reward from action $a$ , followed by the value of continuing with $\pi$ . The improved policy chooses

\pi_{\mathrm{new}}(s)\in \operatorname*{arg\,max}_{a\in A(s)}Q^\pi(s,a).

Although this is a one-step comparison, its continuation term incorporates future rewards rather than only immediate gains. (gradml.mit.edu)

The procedure can be expressed in pseudocode as follows:

Choose an initial deterministic policy π.
Repeat:
    Evaluate π to obtain Vπ.
    For every state s:
        Choose an action maximizing Qπ(s, a).
        Retain π(s) if it is already a maximizer.
    If no action changed:
        Return π and Vπ.
    Replace π with the improved policy.

Retaining an existing maximizing action prevents unnecessary switching between equally valuable decisions. Evaluation and improvement then repeat until the policy is stable. (andrew.cmu.edu)

Improvement and termination

The policy improvement theorem states that the greedy replacement satisfies

V^{\pi_{\mathrm{new}}}(s)\geq V^\pi(s) \qquad\text{for every }s.

Thus an improvement step cannot reduce any state's value. If the current policy is nonoptimal, exact greedy improvement produces a strict increase at some state. If it is already greedy with respect to its own value, that value satisfies the Bellman optimality equation, establishing optimality. (web.mit.edu)

There are only finitely many stationary deterministic policies: precisely $\prod_{s\in S}|A(s)|$ . With exact evaluation and consistent handling of ties, policy iteration therefore terminates after finitely many improvements. This argument does not imply that every problem requires only a small number of iterations. Nor does it automatically apply to undiscounted problems: terminating and average-reward formulations require their own assumptions and evaluation equations. (web.mit.edu)

Relationship to value iteration

Value iteration repeatedly applies the optimality update directly to a value estimate, without fully evaluating a policy between updates. Policy iteration instead invests more computation in evaluation before changing decisions. For dense transitions, an improvement sweep considers every state, action, and possible successor; evaluation additionally requires a linear solve or repeated fixed-policy sweeps. Sparse transitions can substantially reduce this work. Consequently, iteration counts alone do not establish which method is faster. (airr.mit.edu)

Modified policy iteration performs only a limited number of evaluation sweeps before improving the policy again. It interpolates between the inexpensive updates of value iteration and the more complete evaluations of policy iteration. The amount of evaluation becomes a computational trade-off rather than an all-or-nothing choice. (airr.mit.edu)

Approximation and reinforcement learning

Classical policy iteration assumes access to transition probabilities and expected rewards. Generalized policy iteration describes the broader interaction of evaluation and improvement, including processes that operate concurrently or at different levels of precision. Evaluation may use Monte Carlo methods or temporal-difference learning, while actor–critic methods separate policy adjustment from value estimation. (andrew.cmu.edu)

Large state spaces may require function approximation rather than a table of values. Approximation and sampling errors can invalidate the simple monotonic-improvement guarantee, so approximate policy iteration requires separate performance analysis. Research on related algorithms provides bounds connecting evaluation errors to the performance of the resulting policies. (jmlr.csail.mit.edu)

References

Reinforcement Learning: An Introductionandrew.cmu.edu
Neuro-Dynamic Programmingweb.mit.edu
Value functions and Bellmangradml.mit.edu
11 Markov Decision Processes – 6.390 - Intro to Machine Learningintroml.mit.edu
Performance Bounds for λ Policy Iteration and Application to the Game of Tetrisjmlr.csail.mit.edu