Step 2 of the MDP minimax lower bound, with truncated counts

Step 2 of the proof of the $\Omega(\sqrt{DSAn})$ minimax regret lower bound for average-reward Markov decision processes (Lattimore--Szepesv'ari, Bandit Algorithms, Theorem 38.7), in the form the truncated visit counts actually supply.

Here $V^t_j=\mathbb E_0[T_j]$ are the truncated per-pair counts — visits to the $j$-th leaf--action pair among the first $N$ leaf visits — with total $T_0=\mathbb E_0[T_\sigma]$, bounded below by Claim 38.10 in its truncated form; $V_j=\mathbb E_0[T_j^{\mathrm{full}}]$ are the full counts, which is what the divergence decomposition (eq. 38.22) produces, and only their total $T_0^{\mathrm{full}}$ needs an upper bound. The parameter $\mathrm{cap}$ is the pathwise bound on the observable $T_\sigma-T_j$ and enters the Pinsker penalty as $\mathrm{cap}\cdot\Delta$.

Under Claim 38.10 in the two-sided form $c_1n/D\le T_0$, $T_0^{\mathrm{full}}\le c_2n/D$, the change-of-measure bound, Claim 38.11 in the form $R_j\ge c_3\Delta D\,W_j-\mathrm{slack}$, and the tuning $\Delta=\frac{c_1(k-1)}{2}\sqrt{D/(2c_2nk)}$, some alternative $j$ satisfies

Compared with the single-total form, the roles of $c_1$ and $c_2$ have separated — $c_1$ bounds the truncated total below, $c_2$ bounds the full total above — so the two constants need no relation to each other. The parameter $D$ is a free scale, not necessarily the diameter.