In light of the connection between policy iteration and the semismooth Newton method and inspired by the inexact variants of the latter, we propose inexact policy iteration, a new class of dynamic programming methods (Section ). As in OPI, in inexact policy iteration methods the policy evaluation step is carried out only approximately with an iterative solver; however, the number of inner iterations is not fixed a priori, but dictated by a stopping condition which depends on the infinity-norm of the Bellman residual function.
Unlike [1]}, we provide a rigorous analysis of the local contraction properties of the methods in this class (Subsection REF ). In Subsection REF  we design an instance based on the deployment of GMRES [2]}, which we call inexact GMRES policy iteration (iGMRES-PI), and we also give theoretical and empirical insights on the advantages of GMRES with respect to VI for the approximate solution of the policy evaluation step. Finally, in Section  we demonstrate the performance superiority of iGMRES-PI on a large-scale MDP with 10000 states versus the only 500 states MDP used in [1]}. Section  is dedicated to the description of the problem setting and the necessary background material.
