Finite-budget Howard policy iteration for a discounted generator Bellman system

For the finite system of Finite-state discounted generator Bellman system, order each finite set $A_i$ by its declared indices and put $P={\prod }_{i\in S}\mathrm{\mid }{A}_i\mathrm{\mid }$. The procedure takes a positive integer evaluation budget $K\in \mathbb{N}$, $K\ge 1$ (default $K=P$), and proceeds as follows.

1. Initialize ${\pi }_0(i)$ to the least-index action in $A_i$.
2. For the current policy ${\pi }_k$, solve exactly $A^{{\pi }_k}{V}^k=r^{{\pi }_k}$.
3. Form the strict-improvement set $J_k=\{i:{\max }_{a\in A_i}(Q_i^a{V}^k+r_i^a)>Q_i^{{\pi }_k(i)}{V}^k+r_i^{{\pi }_k(i)}\},$ where $Q_i^{a}V={\sum }_j{q}_{ij}^a{V}_j$.
4. If $J_k=\mathrm{\varnothing }$, return $(\mathtt{\text{converged}},{\pi }_k,V^k)$.
5. If $J_k\mathrm{\ne }\mathrm{\varnothing }$ and $k+1=K$, return $(\mathtt{\text{budget\_exhausted}},{\pi }_k,V^k)$; this status makes no Bellman-solution claim.
6. Otherwise, at each $i\in J_k$ switch to the least-index maximizing action in $A_i$; retain ${\pi }_k(i)$ at every state outside $J_k$ and continue.

The policy matrix solve is well-defined by Inverse positivity of discounted finite-state policy matrices. A budget of $P$ policy evaluations is sufficient by the theorem below.