Reverse Bellman inequality lower-bounds the optimal gain

Let $M$ be a finite MDP with at least one state, $f : \mathcal{S} \to \mathcal{A}$ a deterministic memoryless policy, and $(\rho, v)$ with $v$ bounded satisfying the reverse Bellman inequality along $f$,

Then $\rho \le \rho^{*}$, where $\rho^{*} = \max_{s} \sup_{\pi} \bar\rho^{\,s}_{\pi}$ is the optimal gain of $M$.

This is the optimality half of Theorem 38.2 of Lattimore and Szepesvári, complementing the verification half (a solution of the Bellman optimality inequality $r_a(s) + \langle P_a(s), v\rangle \le \rho + v(s)$ bounds $\rho^{*}$ from above). A pair $(\rho, v)$ solving the optimality equation satisfies both, so $\rho = \rho^{*}$ and the greedy policy $f$ is optimal.

The proof is the finite-horizon bound $\mathbb{E}^{f}[\sum_{t \le n} r_{A_t}(S_t)] \ge n\rho - \mathrm{span}(v)$ divided by $n$: the lower bounds $\rho - \mathrm{span}(v)/n$ converge to $\rho$, so the $\limsup$ defining the gain of $f$ from any state is at least $\rho$. The passage from the gain of one policy to the optimal gain is the elementary bound of a supremum by one of its terms; the supremum is finite because every gain is at most one, the rewards being in $[0,1]$, so the conditional supremum is well behaved.