Dependencies

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)\).

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.

At the optimal allocation, the costs of all the pairs \((a^*, b)\) are equal.

The asymptotic lower bound for every identification task.

For every \(w \in \Sigma _K\), \(\inf _{\lambda \in \mathrm{Alt}(\mu )} \sum _a w_a d(\mu _a, \lambda _a) = \min _{b \ne a^*} \bigl( w_{a^*} d(\mu _{a^*}, m_b) + w_b d(\mu _b, m_b) \bigr)\), with \(m_b = (w_{a^*}\mu _{a^*} + w_b\mu _b) / (w_{a^*} + w_b)\).

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 )\).

For every identification task, every \(\delta \)-correct strategy with \(\delta \le 1/2\) and every admissible model with a single correct answer, \(\mathbb {E}[\tau ] \ge T^*(\mu ) \mathrm{kl}(\delta , 1 - \delta )\).

For the GLRT with thresholds \(\beta _t(h, \delta ) \le \log (1/\delta ) + f(t)\), \(f(t) = o(t)\), if almost surely the estimates converge to the model and the proportions of pulls to a set \(W\) of allocations, then almost surely \(\tau _\delta \le c \log (1/\delta )\) for all small \(\delta \), for every \(c {\gt} (\inf _{w \in W} D(\mu , w, \neg a^*))^{-1}\) [ GK16 , Proposition 13 ] . If the infimum is positive, the GLRT stops almost surely at every \(\delta \) at which the thresholds have this form. LMLRoadmaps: Identification 4.4.

Along a sequence of histories on which the GLR statistic of the recommended answer after \(t\) rounds is at least \(\kappa t\) for all large \(t\), consider the GLRTs with thresholds \(\beta _t(h, \delta ) \le \log (1/\delta ) + f(t)\), \(f(t) = o(t)\). If \(\kappa {\gt} 0\), the GLRT stops at every \(\delta \) at which the thresholds have this form, and \(\tau _\delta \le c \log (1/\delta )\) for all small \(\delta \), for every \(c {\gt} 1/\kappa \).

For best arm identification restricted to an open set of vectors of means, such as the vectors of means of a nondegenerate exponential family, the models with unique best arm \(a\) form an open set. For arms in a nondegenerate exponential family and best arm identification restricted to the vectors of means of the family, at every model \(\mu \) with unique best arm \(a\), \((\mu ', w) \mapsto D(\mu ', w, \neg a)\) is continuous within \(\mathbb {R}^K \times \Sigma _K\) at \((\mu , w)\) for every \(w \in \Sigma _K\). These are the continuity hypotheses of LMLExplore’s sample complexity bounds for Track-and-Stop. LMLExplore proves the continuity as a private lemma; LMLExplore pull request #242 makes it public and adds the openness.

For every identification task on vectors of means, arms dominated by exponential families, every sampling rule, \(p {\gt} 0\), \(\delta \in (0, 1]\) and \(C \ge \delta e^{c_{p,K} + 2x_\delta }\), where \(x_\delta = \log (1/\delta ) + 2K(1 + \log (1 + \log (1/\delta )))\) is LMLExplore’s level, the GLRT with the threshold \(\log (C t^p / \delta )\) is \(\delta \)-correct [ GK16 , Proposition 12 ] , and it is \(\delta \)-PAC when it stops almost surely. LMLRoadmaps: Identification 4.2.

For every identification task on vectors of means, arms dominated by exponential families, every sampling rule, \(p {\gt} 0\) and \(x \ge K\), the GLRT with the generalized likelihood ratio evidence and thresholds at least \(p \log n + c_{p,K} + 2x\) at every round \(n \ge 1\), with \(c_{p,K} = 2K \log (2/(1 - e^{-p\log 2/(2K)}))\), stops with an incorrect answer with probability at most \((x/K)^K e^{K-x}\).

For means \(\mu , \mu _1, \mu _2\) of the family, \((w_1, w_2) \mapsto d(\mu , (w_1\mu _1 + w_2\mu _2)/(w_1 + w_2))\) is continuous at every pair of nonnegative weights with \(w_1 + w_2 {\gt} 0\).

Let \(W\) be a compact set of allocations such that \((\theta ', w) \mapsto D(\theta ', w, \neg i)\) is lower semicontinuous at \((\theta , w)\) on the simplex for every \(w \in W\), and let the recommendation be \(i\) near \(\theta \). Along a sequence of histories on which the estimates converge to \(\theta \) and the proportions of pulls \(N(t)/t\) approach \(W\), the GLR statistic of the plug-in statistic, \(t D(\hat\theta _t, N(t)/t, \neg i)\), is at least \(\kappa t\) for all large \(t\), for every \(\kappa {\lt} \inf _{w \in W} D(\theta , w, \neg i)\).

Let \(Z_0, Z_1, \dots \) be i.i.d. with the law of an integrable \(Y\), with rate function \(I\), and let \(\hat\mu _n\) be the mean of \(Z_0, \dots , Z_{n-1}\). For \(a {\gt} 0\) and \(r \ge 0\), \(\mathbb {P}(\exists n \ge a,\ \hat\mu _n {\gt} \mathbb {E}[Y],\ I(\hat\mu _n) {\gt} r) \le e^{-ar}\). For \(a {\gt} 0\) and \(z {\gt} 0\), \(\mathbb {P}(\exists n,\ a \le n {\lt} b,\ n I(\hat\mu _n) \ge z) \le 2 e^{-az/b}\).

For a sequence of \(n = k + m \ge 1\) observations with \(k\) ones and \(m\) zeros, let \(\mathrm{kt}(k, m) = \int _0^1 u^k (1-u)^m \frac{du}{\pi \sqrt{u(1-u)}} = B(\tfrac 12 + k, \tfrac 12 + m) / B(\tfrac 12, \tfrac 12)\) be its Krichevsky–Trofimov probability, the mixture of the Bernoulli likelihoods over the arcsine law \(\mathrm{Beta}(\tfrac 12, \tfrac 12)\). Then \(u^k (1-u)^m \le (k/n)^k (m/n)^m \le 2\sqrt n\, \mathrm{kt}(k, m)\) for every \(u \in [0, 1]\) [ GK16 , Lemma 11 ] , and for \(p \in (0, 1)\), \(n\, d(k/n, p) \le \log \bigl(2\sqrt n\, \mathrm{kt}(k, m) / (p^k (1-p)^m)\bigr)\). That \(\mathrm{kt}\) is a probability on \(\{ 0, 1\} ^n\) is not formalized: the proof of lemma 26 does not need it.

For best arm identification with Bernoulli arms on the vectors of means in \((0, 1)\), the GLR statistic of the plug-in statistic of the empirical means for the arm \(i\) is at most \(N_i\, d(\hat\mu _i, \lambda _i) + N_j\, d(\hat\mu _j, \lambda _j)\) for every arm \(j \ne i\) and all \(\lambda _i \le \lambda _j\) in \((0, 1)\).

Along a run of any algorithm against a Bernoulli bandit with means \(p \in (0, 1)^K\), for two arms \(a \ne b\) and every \(x {\gt} 0\), \(\mathbb {P}\bigl(\exists n,\ \log (2nx) {\lt} N_a(n)\, d(\hat\mu _a(n), p_a) + N_b(n)\, d(\hat\mu _b(n), p_b)\bigr) \le 1/x\) [ GK16 , proof of Theorem 10 ] .

For best arm identification with Bernoulli arms on the vectors of means in \((0, 1)\) and every \(\delta {\gt} 0\), whatever the sampling and recommendation rules, the GLRT with the plug-in statistic of the empirical means and thresholds at least \(\log (2n(K-1)/\delta )\) stops with an arm that is not the best with probability at most \(\delta \) [ GK16 , Theorem 10 ] . LMLRoadmaps: Identification 4.2.

Along a run of any algorithm against a stochastic bandit \(\nu \), if \(\int e^{z(a, y)}\, d\nu _a(y) \le 1\) for every arm \(a\), then \(n \mapsto \exp \bigl(\sum _{k {\lt} n} z(A_k, Y_k)\bigr)\) is a supermartingale for the filtration of the history and the next action. If \(z = z_\ell \) depends measurably on a parameter \(\ell \) drawn from a probability measure \(\rho \), then for every \(c {\gt} 0\), \(\mathbb {P}\bigl(\exists n,\ c \le \int \exp (\sum _{k{\lt}n} z_\ell (A_k, Y_k))\, d\rho (\ell )\bigr) \le 1/c\).

For arms in an exponential family and a vector of means with unique best arm \(a\), the optimal allocation is ordered like the means on the arms other than \(a\): for \(b, c \ne a\), \(w^*_c(\mu ) \le w^*_b(\mu )\) if and only if \(\mu _c \le \mu _b\), and \(w^*_c(\mu ) {\lt} w^*_b(\mu )\) if and only if \(\mu _c {\lt} \mu _b\) [ GK16 , Proposition 6 ] . The same holds for the \(\beta \)-optimal allocations, the maximizers of \(D(\mu , w, \neg a)\) among the allocations with \(w_a = \beta \): for \(\beta {\gt} 0\), and in the strict form for \(\beta \in (0, 1)\). No LMLRoadmaps target covers it yet.

For an exponential family with divergence \(d\), a mean \(\mu _1\) of the family and nonnegative weights \(w_1, w_2\), the cost \(w_1 d(\mu _1, m) + w_2 d(\mu _2, m)\) of moving \(\mu _1\) and \(\mu _2\) to their weighted mean \(m = (w_1\mu _1 + w_2\mu _2)/(w_1 + w_2)\) is nonincreasing in the mean \(\mu _2 \le \mu _1\) of the family. It is decreasing when \(w_1, w_2 {\gt} 0\).

For an exponential family with divergence \(d\), means \(\mu _1, \mu _2\) of the family and nonnegative weights \(w_1, w_2\), the cost \(w_1 d(\mu _1, m) + w_2 d(\mu _2, m)\) of moving \(\mu _1\) and \(\mu _2\) to their weighted mean \(m\) is at most \(w_1 d(\mu _1, z) + w_2 d(\mu _2, z)\) for every mean \(z\) of the family. So the cost of a pair is a minimum of functions linear in the weights, and equal to the one with \(z = m\) at the weights \((w_1, w_2)\).

In the reward stream model, for an arm with integrable rewards and rate function \(I_a\), every \(\eta {\gt} 0\) and \(y \ge 0\), with \(\kappa _\eta = \log (2/(1 - e^{-\eta }))\), \(\mathbb {P}(\exists s,\ s I_a(\hat\mu _s) \ge 2(\eta \lfloor \log _2 s\rfloor + \kappa _\eta + y)) \le e^{-y}\).

Along a run of any algorithm, if the rewards of each arm are integrable with rate function \(I_a\), then for \(\eta {\gt} 0\) and \(x \ge K\), \(\mathbb {P}(\exists t,\ \sum _a N_a(t) I_a(\hat\mu _a(t)) \ge 2(K(\eta \lfloor \log _2 t\rfloor + \kappa _\eta ) + x)) \le (x/K)^K e^{K - x}\). For arms dominated by members of exponential families, the same holds with the extended divergences \(\bar d_a(\hat\mu _a(t), \mu _a)\) in place of \(I_a(\hat\mu _a(t))\).

For arms in an exponential family, a vector of means \(\mu \) with unique best arm \(a\) and at least one other arm, an allocation \(w\) is optimal if and only if \(w \in \Sigma _K\), \(w_a {\gt} 0\), the costs of the pairs \((a, b)\), \(b \ne a\), are equal, and \(\sum _{b \ne a} d(\mu _a, m_b) / d(\mu _b, m_b) = 1\), with the notation of lemma 19 [ GK16 , Theorem 5 ] . LMLRoadmaps: Identification 3.4.

The paper writes the costs of the pairs as \(w_a g_b(w_b / w_a)\), with the increasing function \(g_b(x) = d(\mu _a, m_b(x)) + x\, d(\mu _b, m_b(x))\), and reduces the optimization to the scalar equation \(F(y) = 1\) in the common value \(y\) of the \(g_b\), through their inverses. The properties of \(g_b^{-1}\) and of \(F\) as a function of \(y\) (monotonicity, limits, the bisection) are not formalized: the characterization above does not need them.

For arms in an exponential family, a vector of means \(\mu \) with unique best arm \(a\) and at least one other arm, the optimal allocation satisfies \(F = 1\), with the notation of lemma 19.

For arms in an exponential family and a vector of means \(\mu \) with unique best arm \(a\), let \(w \in \Sigma _K\) with \(w_a {\gt} 0\) equalize the costs \(C_b(w) = w_a d(\mu _a, m_b) + w_b d(\mu _b, m_b)\) of the pairs \((a, b)\), \(b \ne a\), where \(m_b = (w_a\mu _a + w_b\mu _b)/(w_a + w_b)\), and satisfy \(F = \sum _{b \ne a} d(\mu _a, m_b) / d(\mu _b, m_b) = 1\). Then \(w\) is optimal.

In a run of any algorithm against a stochastic bandit with integrable rewards, almost surely the empirical mean of every arm pulled infinitely often converges to the mean of the arm.

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 )\).

Under C-tracking and D-tracking, \(N_a(t)/t \to w^*_a(\mu )\) almost surely.

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}\).

For \(\mu \in \mathcal{S}\): (1) \(w^*_a(\mu ) {\gt} 0\) for every arm \(a\); (2) \(w^*\) is continuous at \(\mu \); (3) if \(\mu _{a^*} {\gt} \mu _2 \ge \dots \ge \mu _K\), then \(w^*_2(\mu ) \ge \dots \ge w^*_K(\mu )\).

For a family of \(\delta \)-correct strategies and every \(\mu \in \mathcal{S}\), \(\liminf _{\delta \to 0} \mathbb {E}_\mu [\tau _\delta ] / \log (1/\delta ) \ge T^*(\mu )\): for every \(c {\lt} T^*(\mu )\), \(\mathbb {E}_\mu [\tau _\delta ] \ge c \log (1/\delta )\) for all small enough \(\delta \).

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 )\).

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}\).

Let \(\delta \in (0, 1/2]\). For every \(\delta \)-correct strategy and every \(\mu \in \mathcal{S}\), \(\mathbb {E}_\mu [\tau _\delta ] \ge T^*(\mu ) \mathrm{kl}(\delta , 1 - \delta )\).

Let \(K \ge 2\). For \(\mu \in \mathcal{S}\) with best arm \(a\), an allocation \(w\) is optimal if and only if \(w = x / \sum _c x_c\) for weights \(x\) with \(x_a = 1\) and, for some \(y\) and every \(b \ne a\), \(x_b {\gt} 0\) and \(g_b(x_b) = d(\mu _a, m_b) + x_b d(\mu _b, m_b) = y\) with \(m_b = (\mu _a + x_b\mu _b)/(1 + x_b)\), such that \(F(y) = \sum _{b \ne a} d(\mu _a, m_b) / d(\mu _b, m_b) = 1\). The paper writes \(x_b = g_b^{-1}(y)\) and computes the unique solution \(y^*\) of \(F(y) = 1\) by bisection.

The paper leaves \(K \ge 2\) implicit. With a single arm, \(F = 0\), while the allocation \((1)\) is optimal (notes/statement-corrections.md).