Fig. 2: policy iteration terminates at a stationary policy of maximal gain rate (B 7)

Let a Markov-renewal program have $N \ge 1$ states, a finite nonempty set of alternatives, positive mean sojourn times $\nu^z_i$, and an irreducible chain for every stationary policy (standing assumption 2). Consider any run of the algorithm of Fig. 2: policies $z_0, z_1, z_2, \dots$ (with $z_0$ arbitrary) and pairs $(g_k, v_k)$ such that, for every $k$,

1. $(g_k, v_k)$ solves the value-determination equations (13) of $z_k$, with $v_{k,N} = 0$, and
2. in each state $i$, $z_{k+1}(i)$ maximizes the test quantity $\frac{1}{\nu^z_i}\{\rho^z_i + \sum_j p^z_{ij} v_{k,j} - v_{k,i}\}$ over the alternatives $z$, and $z_{k+1}(i) = z_k(i)$ whenever $z_k(i)$ already attains the maximum.

Then the algorithm terminates: there is a $K$ with $z_{K+1} = z_K$. Moreover, whenever $z_{K+1} = z_K$, the number $g_K$ is the gain rate of $z_K$, and $z_K$ is an optimal stationary policy: for every stationary policy $z'$ and all stationary probability vectors $\pi$ of $z_K$'s chain and $\pi'$ of $z'$'s chain,

This is the main algorithmic claim of the paper for the infinite-time undiscounted Markov-renewal program: policy iteration with the ratio test quantity finds a stationary policy whose gain rate is at least that of any other stationary policy.

Formalization Note The theorem quantifies over every run, i.e. over every choice among tied maximizers; only the retain-on-tie rule is imposed. The gain rate is the closed form (B 7); its interpretation as the long-run return per unit time (B 6) is not part of the statement.