An intuitive way to improve the time complexity of PI is to solve the system of linear equations inexactly.
This is the main idea behind optimistic policy iteration (OPI), where the policy evaluation is solved approximately with a finite number of VI steps [1]}. Variants of this method include, e.g., the deployment of the Gauss-Seidel and mini-batch versions of VI [2]}. In [3]} the author explores the practical performance of variants of OPI where Krylov methods are used for the approximate policy evaluation step instead of VI. The benchmarks show significant performance improvements with respect to PI and OPI for finite MDPs arising from the discretization of stochastic growth models. Variants of OPI are also studied in [4]}, [5]} for financial pricing problems. Their numerical examples show that OPI-type methods are generally signiﬁcantly faster in terms of CPU time compared to the full
PI scheme. Finally, [6]} study the performance of different OPI-type methods when used in combination with prioritization, partitioning and reordering heuristics.
