§3, discounted case, behind Theorem 4 (pp. 446–447) — optimal discounted cost = least sigma cost = min over u, k, l of λ + β^k μ/(1 − β^l) (corrected)

Let $0<\beta<1$, let $M$ be a finite deterministic stationary Markov decision process with $n$ states and initial state $s_0$, and let $J^*_\beta(s_0)=\inf_\delta\sum_{t\ge0}\beta^tc(s_t,\delta(s_t,t))$ be its optimal discounted cost, the infimum over all policies $\delta(s,t)$. Then:

1. $J^*_\beta(s_0)$ is the least discounted cost of a sigma from $s_0$, and some sigma attains it;
2. with $B_j=A\otimes\beta A\otimes\cdots\otimes\beta^{j-1}A$ ($B_0$ the min-plus identity),

the minimum being attained.

This is the mathematical content of Theorem 4 of the paper ("the infinite-horizon, discounted deterministic problem is in NC"): the optimum is a minimum of polynomially many closed-form expressions in the entries of the matrix products $B_j$, each of which can be computed in parallel.

Formalization Note The parallel-complexity claim (membership in NC, processor and time bounds) is not formalized. The paper prints the expression as $\lambda+\beta^{k+1}\mu/(1+\beta^l)$; with $\lambda=(B_k)_{u_0u}$ covering times $0,\dots,k-1$ the cycle starts at time $k$, so we state the corrected $\lambda+\beta^k\mu/(1-\beta^l)$, and we exclude $l=0$, for which $1-\beta^0=0$. (One node with a loop of cost $1$ has optimum $1/(1-\beta)$, which the printed expression does not produce.) The paper's "$k,l=0,1,\dots,n$" uses $B_0$, which we take to be the min-plus identity. The optimum is over all time-dependent policies $\delta(s,t)$, not over stationary ones, so the first part includes the existence of a stationary optimal policy.