On the Convergence of Policy Iteration in Stationary Dynamic Programming

Authors

Martin L. Puterman, Shelby L. Brumelle

Year

1979

Journal Paper

Algorithm

Policy Iteration

Source

Mathematics of Operations Research

Identifiers

DOI 10.1287/moor.4.1.60

Abstract¶

The policy iteration method of dynamic programming is studied in a general setting. It is shown to be equivalent to the Newton-Kantorovich iteration procedure applied to the functional equation of dynamic programming. This equivalence is used to obtain the rate of convergence and error bounds for the sequence of values generated by policy iteration. These results are discussed in the context of the finite state Markovian decision problem with compact action space. An example is analyzed in detail.

Summary¶

Proves that policy iteration in stationary dynamic programming is equivalent to Newton-Kantorovich iteration on the Bellman operator, yielding superlinear (quadratic) convergence rates. Provides error bounds for finite-state MDPs and establishes a foundational connection between policy iteration and Newton-type numerical methods.