JAO Theorem 5 per initial state, small-diameter regime $D < 12$

The regime $D < 12$, i.e. $\delta = 4/D > \tfrac13$, of the per-initial-state form of JAO Theorem 5, which the main construction of Section 6 excludes.

JAO handle it in footnote 11 (p. 1582) with a different instance. In this regime the hypothesis $D \ge 20\log_A S$ forces $A > 2S$, so there are plenty of spare actions: one uses $S-1$ of them to connect all states directly, producing an MDP of diameter $1$, and sets up an independent two-state gadget in each state with the remaining actions, exactly one state carrying a better action. The bandit lower bound of Auer et al. (2002b) then gives regret $\Omega(\sqrt{SAT})$, which suffices because $D < 12$ here, so $\sqrt{SAT}$ and $\sqrt{DSAT}$ agree up to a constant.

Note that rewards in this formalisation are a deterministic function of the state-action pair, so the per-state bandit must be built from transition probabilities, as in Figure 3, rather than from stochastic rewards.

On the quantifier. JAO Theorem 5 reads "there is an MDP $M$ with $S$ states, $A$ actions, and diameter $D$, such that for any initial state $s \in S$ the expected regret ... is $\ge 0.015\sqrt{DSAT}$", i.e. $\exists M\,\forall s$. Section 6 proves something weaker: on p. 1583 it says "we will consider the simpler MDP where all $s_\circ$-states are identified. We set this state to be the initial state", and the argument never leaves that state. The two readings are genuinely different, and JAO's construction cannot support the stronger one: let $\pi_0$ read the initial state, let $i$ be its copy, and never leave copy $i$, running a minimax-optimal bandit algorithm over that copy's $A'$ gadget actions. Staying is possible, since the gadget actions at $s_\circ^{(i)}$ lead to $s_p^{(i)}$ or stay and $s_p^{(i)}$ returns; and the global optimal gain $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$ is attainable inside a single copy. So from $s_\circ^{(i^*)}$, $\pi_0$ faces exactly the two-state gadget with $A'$ arms and suffers only $\Theta(\sqrt{TA'/\delta})$, a factor $\asymp\sqrt{k}$ below $\sqrt{TkA'/\delta} \asymp \sqrt{DSAT}$. Whichever copy carries the planted action, the initial state in that copy is the cheap one.

Nor is it a matter of bookkeeping: the argument needs a plantable action that the reference algorithm plays rarely, and averaging over the $m$ actions gives $\frac1m(\frac T2 + \frac1{2\delta})$ for a fixed start but only $\frac Sm(\cdots)$ for one action good at all $S$ starts simultaneously, which turns $\sqrt{DSAT}$ into $\sqrt{DAT}$.

This node therefore states the per-initial-state form, $\forall s\,\exists M$: the hard MDP may depend on the initial state, which costs nothing, since the construction is simply relabelled so that $s$ plays the role of $s_\circ$. That is the standard reading of "for any initial state there is a hard MDP", it is exactly what Section 6 establishes, and it is what the $\tilde O(DS\sqrt{AT})$ upper bound of the same paper is compared against. Note that the stronger $\exists M\,\forall s$ form is not known to be false: it quantifies existentially over MDPs, and refuting it would mean showing that every MDP with these parameters admits a cheap initial state. Camping is cheap only because JAO's optimal gain lives inside one copy; an MDP whose optimal gain needs correct actions at many states, or one that mixes in $O(D)$ steps, could plausibly satisfy it. Only the route through this construction is closed.