Existence of the hard arena family with diameter $\le 4(\delta^{-1}+d+1)$

The construction step of the $\Omega(\sqrt{DSAn})$ MDP lower bound.

For every $S \ge 3$ and $A \ge 2$ there is a layered arena $E_0$ on $S$ states and $A$ actions, together with a family $(E_p)$ of arenas indexed by the leaf--action pairs of $E_0$, such that:

1. All members share the same skeleton. The rewarding state $s_g$, the unrewarding state $s_b$, the root, the level function, the depth and the child map of $E_p$ agree with those of $E_0$ for every $p$; the members differ only in where the advantage is planted. Member $E_p$ plants it exactly at $p$: its special leaf is the first component of $p$ and its special action the second. This is what makes the family amenable to a change-of-measure argument, since two members then differ in a single transition row.

2. The family is large. Writing $L$ for the number of leaves, the index set has exactly $L\cdot A$ members, and $S - 2 \le 3L + 1$, so $L = \Theta(S)$ and the family has $\Theta(SA)$ members. This is the source of the factor $\sqrt{SA}$ in the final rate.

3. The tree is shallow. $A^{d} < A(S-2)$ for the common leaf depth $d$, i.e. $d \le 1 + \log_A(S-2)$. Shallowness is what lets the diameter be taken as small as $\Theta(\log_A S)$.

4. Every member has small diameter. For every $p$, the MDP induced by $E_p$ has diameter at most $4(\delta^{-1} + d + 1)$, i.e. four expected episode lengths. Travel to a tree node by routing down the path from the root; travel to $s_g$ or $s_b$ by descending and gambling, which succeeds with probability at least $1/4$ per attempt.

All leaves sit at the same depth $d$. This is a deliberate strengthening of the book, which takes a tree of minimum depth: with leaves at two depths an episode through a shallow leaf is one round shorter, worth $\approx\delta/2$ of gain, while the planted advantage is only $\Delta = \Theta(\sqrt{kD/n})$, so for large $n$ the optimal gain would be attained at a leaf carrying no advantage and the regret decomposition of Claim 38.11 would fail.