Step 2 of the MDP lower bound: some family member forces regret $\gtrsim \sqrt{Dkn}$

Step 2 of the $\Omega(\sqrt{DSAn})$ MDP lower bound: the change-of-measure core.

Fix a layered arena $E_0$ and a family $(E_p)_{p}$ of arenas that agree with $E_0$ off a single transition row, member $E_p$ planting an advantage $\Delta$ at the leaf--action pair $p$. Let $k$ be the number of members and fix an arbitrary learner $\pi$. If the advantage is tuned to

then some member of the family forces $\pi$ into expected regret at least

the subtracted term being the cost of a single transient episode.

The argument is the classical one. No learner can distinguish $k$ alternatives that differ in one row without paying for it: the counts it allocates to the $k$ planted pairs sum to a fixed budget, so by pigeonhole some pair receives at most a $1/k$ share, and the divergence decomposition then bounds the KL divergence between that alternative and the reference by $\mathbb{E}_0[N] \cdot d(\tfrac12, \tfrac12+\Delta)$, which the tuning of $\Delta$ keeps below a constant.

The hypotheses are exactly the arithmetic facts the parameter tuning must check. hlo, htail1 and htail2 deliver the lower bound of Claim 38.10 through a Chernoff certificate for the truncated leaf counter; hhi gives its upper bound; hcapD says the truncation level $N$ lies below the pathwise cap $n/D$; and hc3D calibrates $c_3$ against $\delta^{-1}$, which plays the role of the diameter in Claim 38.11.

The counting is done with truncated counts rather than a stopping time: truncCount records the visits to a pair among the first $N$ rounds spent at leaves. This yields $\sum_p T_p = \min(\text{total}, N)$ and $T_p \le N_n(p)$ pathwise, which is what licenses the bounded change-of-measure inequality without any measurability side conditions.