JAO equation (35) for a two-class MDP: from any initial state the reference reward and the total plays of the plantable pairs are at most $\frac{T}{2} + \frac{D'}{2}$

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$, every horizon $T$, every policy $\pi$ and every initial state $s_0$, in the reference MDP

where $\mathrm{arm}$ is any injection of $m$ plantable pairs into the class-$0$ state-action pairs.

This is equation (35) of JAO (p. 1583) with $D' = 1/\delta$, in the direction the assembly needs. In the reference MDP all actions have the same transition law, so the policy is irrelevant and the class process is the two-state chain with both crossing probabilities equal to $\delta$: writing $W_0(n)$ for the probability that round $n+1$ has class $1$, the recursion $W_0(n+1) = \delta + (1-2\delta)W_0(n)$ solves to $W_0(n) = \tfrac12 + (\rho(s_0) - \tfrac12)(1-2\delta)^n$. Summing the geometric remainder gives $\sum_{n<T} W_0(n) \le \tfrac{T}{2} + \tfrac{1}{4\delta}$ from either class, which is the first bound.

The second is the consequence JAO record just after (37). The pairs $\mathrm{arm}(i)$ are distinct and all lie at class-$0$ states, so the counts $N_{\mathrm{arm}(i)}$ are supported on disjoint events and their sum is at most the number of rounds spent in class $0$, whose expectation is $T - \sum_{n<T} W_0(n) \le \tfrac{T}{2} + \tfrac{1}{4\delta}$. Injectivity of $\mathrm{arm}$ is exactly what makes the counts disjoint, and it is why the plantable pairs may be spread over many states without the bound degrading — this is the point at which the composite MDP behaves like a $m$-armed bandit rather than an $A'$-armed one.