Existence of a rule tracking an optimal allocation

There is a single sampling rule -- one policy, not depending on the environment -- such that for every unit-variance Gaussian bandit with a unique best arm, the empirical allocation $T_i(t)/t$ converges almost surely to some optimal allocation of Lattimore--Szepesv'ari Eq. (33.4).

This is the constructive half of the D-Tracking guarantee, separated from the allocation theory. It asserts only that the tracked limit is an optimal allocation; that it is the allocation a given plug-in rule returns is a separate matter, settled by uniqueness of the optimal allocation, and the two are deliberately not bundled here.

What the construction requires is a policy realising a deterministic function of the observed history, together with the two properties of the greedy tracking rule: that no arm is starved, and that the counts follow the cumulative targets. Concretely one plays, at each round, an arm maximising the shortfall $\sum_{s<t}p_j(s)-T_j(t)$, where $p(s)$ is the plug-in optimal allocation at the current empirical means, mixed with a vanishing fraction of the uniform allocation, $p(s)=(1-k\varepsilon_s)\alpha^*(\hat\mu(s))+\varepsilon_s\mathbf 1$ with $\varepsilon_s=1/(2\sqrt{k^2+s})$.

The exploration floor is what breaks the circularity between the estimates and the sampling: it forces $T_j(t)\ge\sqrt{k^2+t}-2k+1$ for every arm, deterministically and with no hypothesis on the estimates, which makes the empirical means consistent, which in turn makes the plug-in targets converge. The remaining content is that the greedy rule is realisable as a Markov kernel on histories, so that the trajectory measure is supported on trajectories following it.