JAO Figure 4: a two-class gadget on $S$ states and $A$ actions with $\lfloor S/2\rfloor\lfloor A/2\rfloor$ plantable actions and diameter $\le D$

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. Let $S, A \ge 10$ and $D \ge 12$ with $D \ge 20\log_A S$, and let $0 \le \varepsilon \le \tfrac{1}{5D}$. Then there is a two-class gadget shape on $S$ states and $A$ actions with $\delta = 4/D$, an injection $\mathrm{arm}$ of $m = \lfloor S/2\rfloor\lfloor A/2\rfloor$ class-$0$ pairs that are navigation fixed points and satisfy $\mathrm{down}(\mathrm{up}(s)) = s$, a reference MDP and, for each planting, a planted MDP, such that every planted MDP has diameter at most $D$.

This is the construction of JAO Figure 4 (p. 1582), with one simplification. JAO give each state $A' + 1$ extra actions inducing an $A'$-ary tree on the reward-$0$ states, separate from the $A'$ bandit actions. Here every action gambles: from a class-$0$ state each of the $A$ actions escapes to that copy's class-$1$ state with probability $\delta$ (or $\delta + \varepsilon$ for the planted pair) and otherwise moves along the navigation graph. The first $\lfloor A/2 \rfloor$ actions are navigation fixed points and are the plantable ones; the remaining $\lceil A/2\rceil \ge 5$ actions drive an expander-free routing graph on the $\lceil S/2\rceil$ class-$0$ states. This keeps every transition row two-point, which is what makes the relative entropy of a planting Bernoulli, and it costs nothing: $m = \lfloor S/2\rfloor\lfloor A/2\rfloor \ge \tfrac{25}{121}SA$, better than the $\lfloor S/2\rfloor\lfloor (A-1)/2\rfloor$ of the paper.

The diameter. Fix a target and let $L$ be the routing depth, so that a memoryless deterministic policy reaches the target copy in at most $L$ navigation steps. Bound the expected hitting time by a Foster-Lyapunov drift function: from a class-$1$ state one waits a $\mathrm{Geom}(\delta)$ time to return, from a class-$0$ state one advances one navigation step per round unless one escapes, in which case one returns to the same copy and resumes, and once at the target copy one waits a $\mathrm{Geom}(\delta)$ time to escape into it. The function $g(s) = 3\,\mathrm{dist}(s) + \tfrac{1}{\delta}\,[\text{class } 1]$ (plus $\tfrac1\delta$ throughout when the target has class $1$) has drift $\le -1$ off the target because $\delta \le \tfrac13$, giving an expected hitting time at most $\tfrac{2}{\delta} + 3L = \tfrac{D}{2} + 3L$. So it suffices that $L \le D/6$, and taking $L = \lfloor D/6 \rfloor \ge 2$ the routing graph on $\lceil S/2 \rceil$ nodes with out-degree $\lceil A/2\rceil$ has depth $\le L$: this is where $D \ge 20\log_A S$ is used, and it holds with room to spare, the binding case being $\lceil S/2\rceil \le \lceil A/2\rceil^2$ when $D$ is near $12$.