JAO Theorem 5, per initial state: for every algorithm and every initial state there is an MDP of diameter $\le D$ forcing regret $\Omega(\sqrt{DSAT})$

Statement. There is a universal $C > 0$ such that for all $S, A \ge 10$, all $D \ge 20\log_A S$ and all $T \ge DSA$, every learning algorithm $\pi$ and every initial state $s$ admit an MDP $M$ with $S$ states, $A$ actions and diameter at most $D$ on which

This is Theorem 5 of Jaksch, Ortner and Auer (2010), the matching lower bound for their $\tilde O(DS\sqrt{AT})$ UCRL2 upper bound, stated in the form their Section 6 proves. The hypotheses are not cosmetic: the construction places $\lfloor S/2\rfloor$ copies of a two-state gadget with $\lfloor A/2\rfloor$ plantable actions each, connected by a routing graph on the reward-$0$ states, so it does not exist unless $A$ is large enough, and the final constant needs at least $20$ plantable actions.

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.

On the constant. The paper displays $0.015$, but its own Section 6 ends at $0.015\sqrt{D'kA'T}$ in the gadget parameters $D' = D/4$, $k = \lfloor S/2\rfloor$, $A' = \lfloor (A-1)/2\rfloor$, and the substitution $D'kA' \to DSA$ is never justified and is false: the composite must fit in $S$ states and $A$ actions, so $D'kA' \le DSA/16$ and the largest constant the argument can give on $\sqrt{DSAT}$ is $0.015/\sqrt{22} \approx 0.0032$. The statement is therefore given with an existentially quantified $C > 0$.