4 Track-and-Stop
C-tracking ensures \(N_a(t) \ge \sqrt{t + K^2} - 2K\) and \(\max _a |N_a(t) - \sum _{s {\lt} t} w^*_a(\hat\mu (s))| \le K(1 + \sqrt t)\).
In LMLExplore.
D-tracking ensures \(N_a(t) \ge (\sqrt t - K/2)_+ - 1\), and the proportions of pulls converge to the limit of the targets whenever the targets converge.
In LMLExplore.
Under C-tracking and D-tracking, \(N_a(t)/t \to w^*_a(\mu )\) almost surely.
In LMLExplore, given the almost sure convergence of the targets \(w^*(\hat\mu (t))\), which follows from that of the empirical means and the continuity of \(w^*\).
For Bernoulli arms, whatever the sampling rule, Chernoff’s stopping rule with the threshold \(\beta (t, \delta ) = \log (2t(K-1)/\delta )\) ensures \(\mathbb {P}_\mu (\tau _\delta {\lt} \infty , \hat a_{\tau _\delta } \ne a^*) \le \delta \) for every \(\mu \in \mathcal{S}\).
Lemma 28, which holds for every \(\delta {\gt} 0\) and all thresholds at least \(\log (2t(K-1)/\delta )\). The paper’s prior density in Appendix C.1 has a typo (notes/paper-errata.md, E3).
For every \(\alpha {\gt} 1\) and every \(\delta \in (0, 1)\) there is \(C = C(\alpha , K, \delta )\) such that, whatever the sampling rule, Chernoff’s stopping rule with the threshold \(\beta (t, \delta ) = \log (C t^\alpha / \delta )\) ensures \(\mathbb {P}_\mu (\tau _\delta {\lt} \infty , \hat a_{\tau _\delta } \ne a^*) \le \delta \) for every \(\mu \in \mathcal{S}\).
The paper claims a constant \(C(\alpha , K)\) that does not depend on \(\delta \), which is false (notes/paper-errata.md, E2).
Lemma 33, for best arm identification on the vectors of means of the family, whose arms are dominated by the members of the family with their means, with \(C = \delta e^{c_{\alpha ,K} + 2x_\delta }\). It holds for every \(\alpha {\gt} 0\).