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 a given initial state

The two-class planted gadget. The MDP is 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.

Each row is supported on two states and the two masses sum to $1$, so 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$ and $\rho = \mathrm{id}$ this is 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)}$ 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 whose state satisfies $\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$ and every initial state $s_0$ there is a planting $i$ with

The planting is chosen after the initial state, which is what makes the statement true; see the discussion of the quantifier on the parent. The initial state is otherwise unrestricted -- it may have either class.

Why not reduce to the two-state gadget. JAO argue the composite by reducing it to the collapsed MDP in which all $s_\circ^{(i)}$ are identified (p. 1583, "Note that learning this MDP is easier"). That is an intuition they never make precise, and the natural precise version -- an inequality between the two regrets -- is not available: the simulating policy for the collapsed MDP would have to be produced from the composite's policy before the planting is chosen, and it observes neither which copy the composite is in nor which of the $A$ actions was played, both of which the composite's policy uses. This statement keeps the argument on the composite itself, where every step of Section 6 goes through unchanged.

Proof. 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 unlike JAO's version it needs no stochastic-domination coupling. The reference recursion is solved explicitly, giving $\sum_{n<T} W_0(n) \le \tfrac T2 + \tfrac1{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 bounded by the time spent in class $0$, so their reference expectations sum to at most $\tfrac T2 + \tfrac1{2\delta}$. The planted and reference MDPs differ in exactly one row, and both rows are two-point with masses $\delta$ and $\delta+\varepsilon$, so the divergence decomposition with the Bernoulli relative entropy and Pinsker's inequality give Lemma 13. 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}$.