JAO Section 6: a two-class planted gadget has optimal average reward at least $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$

The two-class planted gadget. The MDP is given by its defining equations rather than through an auxiliary definition. The data are a class map $\rho : S \to \{0,1\}$, an escape map $\mathrm{up}$, a return map $\mathrm{down}$ and a navigation map $\mathrm{nav}$, and $M$ satisfies: the reward is the class, $r(s,b) = \rho(s)$; from a class-$0$ state $s$ every action $b$ goes to the class-$1$ state $\mathrm{up}(s)$ with probability $\delta + \varepsilon\,[\,(s,b) = (s^*,b^*)\,]$ and to the class-$0$ state $\mathrm{nav}(s,b)$ otherwise; from a class-$1$ state $s$ every action goes to the class-$0$ state $\mathrm{down}(s)$ with probability $\delta$ and stays at $s$ otherwise. Every row is supported on two distinct states whose masses sum to $1$, so the transition function is pinned down completely. The reference MDP $M_0$ is the same shape with $\varepsilon = 0$. For $S = 2$ and $\rho = \mathrm{id}$ this is JAO Figure 3 with $D' = 1/\delta$; for $S > 2$ it is the composite of Figure 4, its class-$0$ states being the $s_\circ^{(i)}$.

The whole of JAO Section 6 is run at this level of generality, on the composite MDP itself rather than on the collapsed two-state MDP they pass to on p. 1583. That reduction is not available as an inequality between regrets: the simulating policy would have to be produced before the planting is chosen, and it sees neither which copy the composite is in nor which of the $A$ actions was played. Working with the class in place of the state avoids it, and no step of the argument is lost.

Throughout, the initial state $s_0$ is arbitrary and of either class.

Statement. For $0 < \delta \le \tfrac13$, $0 < \varepsilon \le \delta$, and a planted pair $(s^*,b^*)$ at a class-$0$ state which is a fixed point of the navigation map, $\mathrm{nav}(s^*,b^*) = s^*$, and satisfies $\mathrm{down}(\mathrm{up}(s^*)) = s^*$, the optimal gain satisfies $\rho^*(M) \ge \frac{\delta+\varepsilon}{2\delta+\varepsilon}$.

This is the quantity JAO compute on p. 1586 ("Calculating the stationary distribution, we find that the optimal average reward for the MDP $M'$ is $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$"). Only the lower bound is needed: regret is $T\rho^* - \text{reward}$, so a large $\rho^*$ is what makes the bound strong.

Proof. The optimal gain is a supremum over initial states and over all policies, so one policy from one state suffices. Take the memoryless deterministic policy playing $b^*$ everywhere, started at $s^*$. The two hypotheses on the planted pair are exactly what confines the resulting chain to $\{s^*, \mathrm{up}(s^*)\}$: the navigation fixed point keeps a failed escape at $s^*$, and $\mathrm{down}(\mathrm{up}(s^*)) = s^*$ returns there. So the chain is the two-state gadget with escape probability $\delta+\varepsilon$ and return probability $\delta$, whose stationary mass on the class-$1$ state is $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$. Writing $w(n)$ for the probability that round $n+1$ is in class $1$, one step gives $w(n+1) = (\delta+\varepsilon) + (1 - 2\delta - \varepsilon)w(n)$ with $w(0) = 0$; since the reward is the class indicator, the expected reward over $n$ rounds is the partial sum of $w$, so it is $\rho n$ minus a bounded geometric remainder, the Cesàro averages converge to $\rho$, and the $\limsup$ defining the gain equals it. Both suprema are then entered with le_ciSup, the boundedness coming from every reward lying in $[0,1]$.