Communicating MDPs have a common optimal average reward

Set $V_0(s)=0$ for every state. Backward induction over the finite horizon gives the Bellman recurrence $V_{n+1}(s)={\max }_{a\in A(s)}[r(s,a)+{\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V_n(s^{\mathrm{\prime }})]\mathrm{.}$ For the induction step, suppose that from every state the $n$-step supremum is attained by a deterministic Markov policy and equals $V_n$. Any history-dependent $(n+1)$-step policy may randomize its first action and may condition later actions on the first reward as well as the next state. Conditional on a first action $a$ and one-step outcome $(s^{\mathrm{\prime }},\rho )$, its continuation has expected reward at most $V_n(s^{\mathrm{\prime }})$ by the induction hypothesis, which is independent of the earlier history and reward. Thus its total expected reward is at most $r(s,a)+{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)V_n(s^{\mathrm{\prime }})$, averaged over its first-action distribution, and this average is at most the displayed maximum. A maximizing action exists because $A(s)$ is finite; choosing it and then using an attaining $n$-step policy from each possible next state attains equality. The base case $V_0=0$ is attained by the empty policy. This proves both the recurrence and that history dependence cannot improve $V_n$; the joint reward/next-state law is handled by its mean reward and next-state marginal. For any $0\le j\le n$, splitting an $n$-step policy into its first $n-j$ and last $j$ rewards gives $V_n(y)\le V_{n-j}(y)+j$: the first part is at most the optimal $(n-j)$-step value and the last part is at most $j$ because rewards lie in $[0,1]$. For any $x,y$ and $\epsilon >0$, [F2] gives a policy from $x$ whose hitting time ${\tau }_y$ has expectation at most $D_0+\epsilon$. Follow it until $y$ is hit, then use an optimal policy for the remaining $n-{\tau }_y$ steps if ${\tau }_y\le n$. On $\{{\tau }_y=j\}$ for each $0\le j\le n$, the conditional expected total reward given the history through time $j$ is at least $V_{n-j}(y)\ge V_n(y)-j$, since pre-hit rewards are nonnegative. On ${\tau }_y>n$, the total reward is nonnegative and $V_n(y)\le n<{\tau }_y$. Summing over the hitting-time events and taking expectations using [F5]–[F8] gives $V_n(x)\ge V_n(y)-\mathbb{E}[{\tau }_y]\ge V_n(y)-D_0-\epsilon$. Letting $\epsilon \downarrow 0$ and interchanging $x,y$ proves ${\max }_s{V}_n(s)-{\min }_s{V}_n(s)\le D_0$.

Put $a_n={\max }_s{V}_n(s)$; the maximum exists because $S$ is finite, and $0\le a_n\le n$ by [F1,F8]. For any $(m+n)$-step policy from $s$, the expected first $m$ rewards are at most $V_m(s)$, while conditional on the complete history through state $S_m$ the remaining $n$-step rule is an admissible policy from $S_m$ and its conditional expected reward is at most $V_n(S_m)\le a_n$. By [F4,F5,F6,F7], the unconditional expected total is therefore at most $V_m(s)+a_n\le a_m+a_n$, so $a_{m+n}\le a_m+a_n$. Conversely, choose $s_{\ast }$ attaining $a_m$ and use an optimal $m$-step policy from it; after observing $S_m=z$, continue with an optimal $n$-step policy from $z$. By step 1.1, $V_n(z)\ge a_n-D_0$ for every $z$, so [F4,F6,F7] give total expected reward at least $a_m+a_n-D_0$. Hence $a_{m+n}\ge a_m+a_n-D_0$, and $\mathrm{\mid }{a}_{m+n}-a_m-a_n\mathrm{\mid }\le D_0$.

Apply [F3] to $(a_n)$ with $C=D_0$ to obtain $a_n\mathrm{/}n\to {\rho }^{\ast }$ for some finite ${\rho }^{\ast }$. Step 1.1 gives $a_n-D_0\le V_n(s)\le a_n$ for every $s$, so division by $n$ proves $V_n(s)\mathrm{/}n\to {\rho }^{\ast }$ for every state. The bounds $0\le V_n(s)\le n$ imply ${\rho }^{\ast }\in [0,1]$.