Garivier–Kaufmann Proposition 13: a rule with integrable settling time

Proposition 13. There is a single sampling rule -- one policy, chosen before the environment and before the confidence level -- such that for every unit-variance Gaussian bandit $\nu=\mathcal N(\mu,I)$ with a unique best arm there is an optimal allocation $\alpha^*$ of Lattimore--Szepesv'ari Eq. (33.4), with all weights strictly positive, for which the following holds at every accuracy $\xi>0$. Writing

the empirical allocation and the empirical means settle within $\xi$ almost surely, and $\mathbb E[T_\xi]<\infty$.

The integrability, not merely the almost-sure finiteness, is the whole content. Almost-sure convergence of the empirical allocation does not bound $\mathbb E[\tau_\delta]$: a rule may delay its second arm to round $M$, where $M$ is a function of the first reward with $M<\infty$ almost surely but $\mathbb E[M]=\infty$; while one arm is unplayed the generalised-likelihood-ratio statistic carries the factor $T_{\hat\imath}T_j/(T_{\hat\imath}+T_j)=0$ and so cannot cross any threshold, giving $\tau_\delta\ge M$ and $\mathbb E[\tau_\delta]=\infty$, and this uniformly in $\delta$. A node asserting the sample-complexity bound from almost-sure convergence alone was retired for exactly this reason.

For D-Tracking the quantitative input is the forced-exploration floor. Playing at each round an arm maximising the shortfall $\sum_{s<t}p_j(s)-T_j(t)$, with $p(s)=(1-k\varepsilon_s)\alpha^*(\hat\mu(s))+\varepsilon_s\mathbf 1$ and $\varepsilon_s=1/(2\sqrt{k^2+s})$, forces $T_j(t)\ge\sqrt{k^2+t}-2k+1$ for every arm deterministically, with no hypothesis on the estimates. Gaussian deviations at that many samples give $\mathbb P(\max_i|\hat\mu_i(t)-\mu_i|>\varepsilon)\le 2k\exp(-\tfrac12\varepsilon^2(\sqrt t-2k))$, which is summable against the extra factor $t$ that turns a tail sum into an expectation. Continuity of $\alpha^*$ at $\mu$ -- available from uniqueness of the optimal allocation, with no modulus needed, since $\varepsilon$ may depend on $\xi$ arbitrarily -- transfers this to the allocation through the tracking bound $|T_i(t)-\sum_{s<t}p_i(s)|\le k$.