5 Sample complexity
Let \(\alpha \in [1, e/2]\), \(r(t) = O(t^\alpha )\) and \(\beta (t, \delta ) = \log (r(t)/\delta )\). For every sampling rule with \(N_a(t)/t \to w^*_a\) almost surely, \(\tau _\delta {\lt} \infty \) almost surely for every \(\delta \in (0, 1)\), and almost surely \(\limsup _{\delta \to 0} \tau _\delta / \log (1/\delta ) \le \alpha T^*(\mu )\).
Lemma 37 with \(W = \{ w^*(\mu )\} \). Every arm gets a positive proportion \(w^*_a(\mu ) {\gt} 0\) of the pulls (proposition 8), so it is pulled infinitely often and its empirical mean converges almost surely to its mean (lemma 38). The cost \(D(\mu ', w', \neg a^*)\) is continuous at \((\mu , w^*(\mu ))\), the recommendation is \(a^*\) near \(\mu \) (lemma 34), and \(D(\mu , w^*(\mu ), \neg a^*) = T^*(\mu )^{-1} {\gt} 0\). The thresholds are \(\log (r(t)/\delta ) \le \log (1/\delta ) + \log r(t)\) with \(\log r(t) = o(t)\). This gives \(\limsup _{\delta \to 0} \tau _\delta / \log (1/\delta ) \le T^*(\mu ) \le \alpha T^*(\mu )\), for every \(\alpha \ge 1\).
Let \(\alpha \in [1, e/2]\), \(r(t) = O(t^\alpha )\) and \(\beta (t, \delta ) = \log (r(t)/\delta )\). Track-and-Stop with C-tracking or D-tracking has \(\limsup _{\delta \to 0} \mathbb {E}_\mu [\tau _\delta ] / \log (1/\delta ) \le \alpha T^*(\mu )\).
LMLExplore proves the stronger bound with \(T^*(\mu )\) for every polynomial \(r\), lemma 16, and \(T^*(\mu ) \le \alpha T^*(\mu )\) since \(\alpha \ge 1\). Near \(\mu \), the vectors of means have the same unique best arm (lemma 34), which the recommendation returns, and the targets are their optimal allocations; the continuity of the targets that D-tracking assumes is proposition 8 (2), and the continuity of the costs that both assume is lemma 34.
Track-and-Stop with D-tracking or C-tracking of optimal allocations has \(\mathbb {E}_\mu [\tau _\delta ] \le c \log (1/\delta )\) for all small \(\delta \), for every \(c {\gt} T^*(\mu )\).
In LMLExplore, through the concentration of the empirical means under tracking [ GK16 , Lemma 19 ] .