JAO equation (34) for a two-class MDP: the reward collected under a planting exceeds the reference reward by at most $\frac{\varepsilon}{2\delta}$ times the plays of the planted pair

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.

On the two-valuedness hypothesis. The statement carries $\forall s,\ \rho(s) \in \{0,1\}$ explicitly. It is not decoration: the row equations above only constrain states of class $0$ and of class $1$, so without it a state of neither class has a completely unconstrained transition row and an arbitrarily large reward, and the conclusion fails outright from such an initial state. An earlier version of this node omitted it and has been deprecated.

Statement. For $0 < \varepsilon \le \delta \le \tfrac13$, every horizon $T$, every policy $\pi$ and every initial state $s_0$,

where $\mathbb{E}_a$ is the expectation under the planted MDP and $\mathbb{E}_{\mathrm{unif}}$ that under the reference MDP, both run against the same policy from the same initial state, and $N_{(s^*,b^*)}$ counts the rounds in which the planted pair is played.

This is equation (34) of JAO (p. 1583) in the form the rest of the argument consumes, but obtained by a different and shorter route. Write $W(n)$ for the probability that the state of round $n+1$ has class $1$. Since the reward is the class indicator, the total expected reward is $\sum_{n<T} W(n)$. Conditioning on a single step and using that the escape probability is $\delta$ off the planted pair and $\delta + \varepsilon$ on it, while the return probability is $\delta$ everywhere,

with $Q(n)$ the probability that round $n+1$ plays the planted pair. The reference obeys the same recursion with $Q \equiv 0$ and the same initial value $W_0(0) = \rho(s_0)$, so the difference $d(n) = W(n) - W_0(n)$ satisfies $d(0) = 0$ and $d(n+1) = (1-2\delta)d(n) + \varepsilon Q(n)$. Summing that over $n < T$ telescopes, because $\sum_{n<T} d(n+1) = \sum_{n<T} d(n) + d(T) - d(0)$, and gives

using $d(T) \ge 0$, which follows from the recursion by induction. JAO instead bound $\mathbb{E}_a[N_\circ] \le \mathbb{E}_{\mathrm{unif}}[N_\circ]$ by a stochastic-domination coupling between the two MDPs; the telescoping identity removes that step entirely, and it is also what makes the statement work from an arbitrary initial state, since the two recursions start from the same value whatever $\rho(s_0)$ is.