Stochastic optimal control problems arise in a variety of applications across different fields [1]}, [2]} and can be compactly expressed in mathematical terms via a recursive functional equation known as the Bellman equation [3]}. Dynamic programming (DP) comprises all methods to solve the Bellman equation, such as value iteration (VI), policy iteration (PI) and their variants [4]}.
Empirical evidence has shown that, among the dynamic programming methods, PI tends to enjoy the fastest rate of convergence. In addition, [5]} have proved that for finite MDPs PI is an instance of the semismooth Newton method and therefore, by exploiting the structural properties of the Bellman equation, it is possible to conclude local quadratic rate of convergence. Even though PI converges in very few iterations, its time performance degrades rapidly with the size of the state space. In fact, at each iteration PI requires the exact solution of a system of linear equations with dimension equal to the number of states. While the total number of iterations is not dependent on the size of the MDP, the computational complexity of the exact policy evaluation step is strongly dependent on it, diminishing the computational advantages of PI.
