Example, pp. 961–962 — gains $70, 50, 80, 60$; $(B,A)$ optimal for all $n$ with $V_1(n) = 80n+170+(-1)^{n+1}170$; Cesàro biases $\pm 170$

The paper's two-state machine maintenance-repair example. State 1 is "running", state 2 "broken down". Every alternative moves the machine to the other state with probability one, so under every stationary policy the embedded chain is

With the linear reward structure (8) ($R'_{ij} = R_{ij}$, $R''_{ij} = 0$) the one-step expected reward of an alternative is $R_{ij} + r_{ij}\nu_{ij}$: in state 1, alternative $A$ gives $0 + 100\cdot 4 = 400$ and alternative $B$ gives $0 + 84 \cdot 5 = 420$; in state 2, alternative $A$ gives $0 + (-65)\cdot 4 = -260$ and alternative $B$ gives $-100 + (-200)\cdot 1 = -300$. Let $\rho = (420, -260)$ be the reward vector of the policy $(B,A)$, $V(0) = 0$, and $\pi = (\tfrac12, \tfrac12)$. Then

1. $P$ is ergodic (irreducible, row-stochastic, of period $2$) and $\pi$ is a stationary probability vector;
2. the gains $G = \sum_i \pi_i \rho_i$ of the four stationary policies are $G^{AA} = 70$, $G^{AB} = 50$, $G^{BA} = 80$, $G^{BB} = 60$;
3. $(B,A)$ is optimal for every $n$: the return $V(n)$ of $(B,A)$ satisfies the optimality recursion (I 16),

so it is the optimal $n$-step return; 4. for every $n \ge 0$,

5. the limiting bias vector is $(Z - \Pi)\rho + \Pi V(0) = (170, -170)$;
6. the relative values $V_1 = 340$, $V_2 = 0$ solve equations (5): $V_i + G = \rho_i + \sum_j p_{ij} V_j$ with $G = 80$.

The example shows why the bias limit is a Cesàro limit: $W(n) = V(n) - 80n$ oscillates between two values forever, and only its average converges.

Formalization Note States 1 and 2 are the Lean indices 0 and 1, and the paper's $(-)^{n+1}$ is $(-1)^{n+1}$. The paper's "optimal for all values of $n$" is stated as: the $(B,A)$ return satisfies (I 16) with the maximum over both alternatives in each state, which determines the optimal return uniquely from $V(0) = 0$. The rewards are written as $R + r\nu$ so that each number can be read off p. 961.