JAO Section 6, equations (34)-(37) and Lemma 13, run directly on a two-class MDP with $m$ plantable actions: regret $\Omega(\sqrt{mT/\delta})$ from every initial state

The two-class planted gadget. Both children speak about the same class of MDPs, described 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 the MDP $M$ satisfies

• the reward is the class, $r(s,b) = \rho(s)$ for every action $b$;
• 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.

Since each row is supported on two states and the two masses sum to $1$, these equations pin the transition function down completely. For $\varepsilon = 0$ this is the reference MDP $M_0$; for the planting at $(s^*,b^*)$ it is $M$. When $S = 2$, $\rho = \mathrm{id}$ and $\mathrm{nav}$ is constant, this is exactly the gadget of JAO Figure 3 with $D' = 1/\delta$; for $S > 2$ it is the composite MDP of Figure 4, whose class-$0$ states are the $s_\circ^{(i)}$, whose class-$1$ states are the $s_p^{(i)}$, and whose navigation map moves between the copies.

Statement. There is a universal $c > 0$ with the following property. Let $m \ge 20$, $0 < \delta \le \tfrac13$ and $16m \le \delta T$, and set $\varepsilon = \tfrac15\sqrt{\delta m/T}$. Suppose given a two-class gadget shape on $S$ states and $A$ actions together with an injection $\mathrm{arm} : \{1,\dots,m\} \to S \times A$ whose image consists of class-$0$ pairs, each of which is a fixed point of the navigation map, and each of whose states returns to itself, $\mathrm{down}(\mathrm{up}(s)) = s$. Let $M_0$ be the reference MDP and $M_i$ the MDP planted at $\mathrm{arm}(i)$. Then for every learning algorithm $\pi$ there is a planting $i$ such that, from every initial state,

Why this shape. JAO argue the composite MDP by reducing it to the collapsed two-state MDP in which all $s_\circ^{(i)}$ are identified (p. 1583, "we may as well consider the simpler MDP"). That reduction cannot be carried out as an inequality between the two regrets. The collapsed MDP always starts in the reward-$0$ state, whereas the composite must be bounded from every initial state; starting in a class-$1$ state collects $\sum_{n<T}(1-2\delta)^n \le \tfrac{1}{2\delta}$ more reward than starting in a class-$0$ state, and at $T = 1$ the discrepancy is already fatal, since the composite has regret $\rho^*(M) - 1 \le 0$ from a class-$1$ state while the collapsed MDP has regret $\rho^*(M') > 0$. Worse, a policy for the collapsed MDP must be produced from a policy for the composite before the planting is chosen and uniformly in the initial state, and it observes neither which copy the composite is in nor which of the $A$ actions was played -- information the composite's policy uses. The statement above therefore keeps the argument on the composite MDP itself: nothing is collapsed, and the initial state is universally quantified.

Proof. All of JAO's Section 6 goes through with the class in place of the state. Write $W(n)$ for the probability that the state of round $n+1$ has class $1$. Conditioning on one step gives $W(n+1) = \delta + (1-2\delta)W(n) + \varepsilon\,Q(n)$, where $Q(n)$ is the probability that round $n+1$ plays the planted pair, and the reward is $\sum_{n<T} W(n)$. Comparing with the reference recursion $W_0(n+1) = \delta + (1-2\delta)W_0(n)$ started at the same $W_0(0) = \rho(s_0)$, the difference $d(n) = W(n) - W_0(n)$ obeys $d(0) = 0$ and $d(n+1) = (1-2\delta)d(n) + \varepsilon Q(n)$, which telescopes on summation to $2\delta \sum_{n<T} d(n) \le \varepsilon\sum_{n<T} Q(n)$; this is equation (34), and it needs no coupling. The reference recursion is solved explicitly, giving $\sum_{n<T} W_0(n) \le \tfrac{T}{2} + \tfrac{1}{4\delta}$ from either class, which is equation (35). Since $\mathrm{arm}$ is injective and lands in class-$0$ pairs, the counts $N_{\mathrm{arm}(i)}$ are disjoint and their sum is at most the time spent in class $0$, so their reference expectations sum to at most $\tfrac{T}{2} + \tfrac{1}{2\delta}$. The planted and reference MDPs differ in exactly one row, so the divergence decomposition and Pinsker's inequality bound $\mathbb{E}_i[N_{\mathrm{arm}(i)}]$ by its reference expectation plus $\tfrac{T}{2}\tfrac{\varepsilon}{\sqrt\delta}\sqrt{2\,\cdot}$, which is Lemma 13; the two rows are two-point distributions with masses $\delta$ and $\delta + \varepsilon$, so their relative entropy is the Bernoulli one. The optimal gain is at least $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$ because the planted pair is a navigation fixed point, so always playing it from the planted state reproduces the two-state gadget. Averaging over the $m$ plantings and choosing $\varepsilon = \tfrac15\sqrt{\delta m/T}$ leaves a positive multiple of $\sqrt{Tm/\delta}$, exactly as in the collapsed case.