If \(w_1 = w_2 = 0\), both sides vanish. Otherwise \(m\) is a mean of the family, and it minimizes \(z \mapsto w_1 d(\mu _1, z) + w_2 d(\mu _2, z)\) by the compensation identity \(w_1 d(\mu _1, z) + w_2 d(\mu _2, z) = w_1 d(\mu _1, m) + w_2 d(\mu _2, m) + (w_1 + w_2) d(m, z)\).

The weighted mean is continuous there and is a mean of the family, which is open, and \(d\) is continuous on pairs of means.

Write \(A_b = d(\mu _a, m_b)\) and \(B_b = d(\mu _b, m_b)\), which is positive since \(w_a {\gt} 0\) and \(\mu _b {\lt} \mu _a\) give \(m_b \ne \mu _b\), and \(D\) for the common value of the costs. For every \(x \in \Sigma _K\), \(\sum _{b \ne a} (x_a A_b + x_b B_b) / B_b = x_a F + \sum _{b \ne a} x_b = 1\). At \(x = w\) this is \(\sum _{b \ne a} D / B_b = 1\). Let \(v \in \Sigma _K\). By lemma 17 with \(z = m_b\), the cost of the pair \((a, b)\) at \(v\) is at most \(v_a A_b + v_b B_b\). If all of them exceeded \(D\), then \(1 = \sum _{b \ne a} D / B_b {\lt} \sum _{b \ne a} (v_a A_b + v_b B_b) / B_b = 1\). So some pair costs at most \(D\) at \(v\), and by lemma 5 the cost of the alternatives at \(v\) is at most its value \(D\) at \(w\).

The optimal allocation \(w\) has positive entries (in LMLExplore). Suppose \(F \ne 1\), and let \(S = \sum _{b \ne a} 1 / B_b {\gt} 0\). The direction \(u\) with \(u_a = S / (F - 1)\) and \(u_b = (1 - A_b u_a) / B_b\) for \(b \ne a\) has \(\sum _c u_c = u_a + S - F u_a = 0\) and \(u_a A_b + u_b B_b = 1\) for every \(b \ne a\). Let \(v = w + t u\), with \(m'_b\) the weighted mean of \(\mu _a\) and \(\mu _b\) at \(v\). The cost of the pair \((a, b)\) at \(v\) is \(v_a d(\mu _a, m'_b) + v_b d(\mu _b, m'_b)\), and its cost at \(w\) is at most \(w_a d(\mu _a, m'_b) + w_b d(\mu _b, m'_b)\) (lemma 17), so the difference is at least \(t\, (u_a d(\mu _a, m'_b) + u_b d(\mu _b, m'_b))\). As \(t \to 0\), the second factor tends to \(u_a A_b + u_b B_b = 1\) (lemma 18). So for some small \(t {\gt} 0\), \(v\) is in the simplex and every pair costs more at \(v\) than at \(w\): by lemma 5, the cost of the alternatives is larger at \(v\), which contradicts the optimality of \(w\). The proof needs neither a derivative of \(d\) nor the inverses of the costs of the pairs, which the paper uses.

The optimal allocation has positive entries (in LMLExplore), equalizes the costs of the pairs (lemma 6) and satisfies \(F = 1\) (lemma 20). Conversely, lemma 19.

Let \(\mu _2' {\lt} \mu _2 \le \mu _1\) and let \(m'\) be the weighted mean of \(\mu _1\) and \(\mu _2'\), so that \(\mu _2' {\lt} m' \le \mu _1\). The pair cost of \((\mu _1, \mu _2)\) is the minimum of \(w_1 d(\mu _1, x) + w_2 d(\mu _2, y)\) over the means \(x \le y\). If \(\mu _2 \le m'\), take \(x = y = m'\): then \(d(\mu _2, m') {\lt} d(\mu _2', m')\), since \(d(\cdot , m')\) decreases below \(m'\). If \(m' {\lt} \mu _2\), take \(x = m'\) and \(y = \mu _2\): then \(d(\mu _2, \mu _2) = 0 {\lt} d(\mu _2', m')\). In both cases the result is at most \(w_1 d(\mu _1, m') + w_2 d(\mu _2', m')\), the pair cost of \((\mu _1, \mu _2')\), and strictly less when \(w_2 {\gt} 0\). If a weight vanishes, both costs are zero.

Let \(w\) be \(\beta \)-optimal, so that the costs \(C_b(w_b)\) of the pairs \((a, b)\), with \(C_b(x) = \beta d(\mu _a, m_b) + x d(\mu _b, m_b)\), are all equal (lemma 6 and its \(\beta \) form). Let \(b, c \ne a\) with \(\mu _c \le \mu _b\). If \(w_b {\lt} w_c\), then \(C_b\) increases, so \(C_b(w_b) {\lt} C_b(w_c)\). By lemma 22, \(C_b(w_c) \le C_c(w_c)\). This contradicts \(C_b(w_b) = C_c(w_c)\). If \(\mu _c {\lt} \mu _b\) and \(w_b \le w_c\), then \(C_b(w_b) \le C_b(w_c) {\lt} C_c(w_c)\), using \(w_c {\gt} 0\), a contradiction again. The optimal allocation is \(\beta \)-optimal for \(\beta = w^*_a \in (0, 1)\); the two implications give the equivalences.

The moments of the beta laws give the closed form, and the recursion of the beta function \(\mathrm{kt}(k, m + 1) = \mathrm{kt}(k, m)\, (m + \tfrac 12)/(n + 1)\). By induction on \(m\) (from \(\mathrm{kt}(0, 1) = \tfrac 12\) and the symmetry in \(k\) and \(m\)), the claim \(k^k m^m \le 2\sqrt n\, n^n\, \mathrm{kt}(k, m)\) propagates from \(m\) to \(m + 1\) when \((m+1)^{m+1}\sqrt n\, n^n \le \sqrt{n+1}\, (m + \tfrac 12)\, m^m (n+1)^n\), which in logarithms is \((m+1)\log (m+1) - m\log m - \log (m + \tfrac 12) \le 1 \le (n + \tfrac 12)\log (1 + 1/n)\). The right inequality is the first term of the series of \(\log (1 + 1/n)\) in powers of \(1/(2n+1)\); the left one, for \(m \ge 1\), says that \(t \mapsto (1+t)\log (1+t) - t - t\log (1 + t/2)\), whose derivative is \(\log \frac{1+t}{1+t/2} - \frac{t}{2+t} \le 0\), is nonpositive at \(t = 1/m\) [ WST95 , Appendix ] . The maximum likelihood bound is \(n\, d(k/n, u) \ge 0\), and \(n\, d(k/n, p) = \log \bigl((k/n)^k (m/n)^m / (p^k (1-p)^m)\bigr)\).

Given the history and the action of round \(n\), the observation \(Y_n\) has law \(\nu _{A_n}\), so the conditional expectation of \(e^{z(A_n, Y_n)}\) is at most \(1\). Mixtures of nonnegative supermartingales are supermartingales (in LMLExplore), with initial value \(1\) here, and Ville’s inequality (in LMLExplore) concludes.

Take \(z_{(u, v)}(c, y)\) the log-likelihood ratio of the observation \(y\) of the arm \(c\) under the bandit whose means on \(a\) and \(b\) are \(u\) and \(v\) against the true one, and \(\rho = \mathrm{Beta}(\tfrac 12, \tfrac 12)^{\otimes 2}\). Its sum over the rounds is \(S_a \log (u/p_a) + (N_a - S_a)\log ((1-u)/(1-p_a))\) plus the same for \(b\), so the mixture is the product \(\Lambda _a \Lambda _b\) of the Krichevsky–Trofimov likelihood ratios \(\Lambda _c = \mathrm{kt}(S_c, N_c - S_c) / (p_c^{S_c} (1-p_c)^{N_c - S_c})\), the observations being in \(\{ 0, 1\} \) almost surely. By lemma 24, \(N_c\, d(\hat\mu _c, p_c) \le \log (w_c \Lambda _c)\) with \(w_c = 2\sqrt{N_c}\), or \(w_c = 1\) when \(N_c = 0\). On the event, one of the two arms has an observation (the right side is positive), and then \(w_a w_b \le 2n\), so \(\log (2nx) {\lt} \log (2n\Lambda _a\Lambda _b)\) and \(x {\lt} \Lambda _a \Lambda _b\): lemma 25 with \(c = x\) concludes. The paper applies Lemma 11 also to an arm with no observation, where it fails (notes/paper-errata.md, E4).

The cost of the alternatives to \(i\) is the infimum of the transportation cost from the empirical means over the vectors \(\lambda '\) of \((0, 1)^K\) with \(\lambda '_i \le \lambda '_b\) for some \(b \ne i\), since the cost is continuous there (in LMLExplore). Take \(\lambda '\) with \(\lambda '_i = \lambda _i\), \(\lambda '_j = \lambda _j\), and \(\lambda '_c = (1 - t)\hat p_c + t/2\) on the other arms, where \(\hat p_c\) is \(\hat\mu _c\) clamped to \([0, 1]\): by the \(\chi ^2\) bound, \(d(\hat p_c, \lambda '_c) \le t\), and \(t \to 0\).

If the GLRT stops at round \(n\) with an arm \(i \ne a^*\), then by lemma 27 with \(\lambda = \mu \) on the pair \((i, a^*)\), \(\log (2n(K-1)/\delta ) {\lt} N_i\, d(\hat\mu _i, \mu _i) + N_{a^*}\, d(\hat\mu _{a^*}, \mu _{a^*})\). By lemma 26 with \(x = (K-1)/\delta \), each of the \(K - 1\) wrong arms contributes at most \(\delta /(K-1)\).

Along the filtration of the past variables, \(Z_n\) is independent of the past, so its conditional moment generating function is that of \(Y\), and the first bound is LMLExplore’s time-uniform Chernoff bound with the rate function, with every variable selected. For the second, \(n I(\hat\mu _n) \ge z\) with \(n {\lt} b\) forces \(I(\hat\mu _n) {\gt} z/b\), which vanishes at the mean; above the mean this is the first bound with \(r = z/b\), and below the mean the first bound for \(-Z\) and \(-Y\).

A deviation with \(s \ge 1\) rewards lies on the dyadic slice \(2^k \le s {\lt} 2^{k+1}\) with \(k = \lfloor \log _2 s\rfloor \), and at \(s = 0\) there is none. By lemma 29 with \(a = 2^k\) and \(b = 2^{k+1}\), the slice \(k\) has probability at most \(2 e^{-(\eta k + \kappa _\eta + y)}\), and these sum to \(2 e^{-\kappa _\eta - y} / (1 - e^{-\eta }) = e^{-y}\).

In the stream model the arms are independent, and lemma 30 gives each half statistic \(s I_a(\hat\mu _s)/2\) the exponential tail above the monotone function \(\eta \lfloor \log _2 s\rfloor + \kappa _\eta \) that [ LS20 , Proposition 33.9 ] (in LMLExplore) combines over the arms. LMLExplore’s joint event transfer turns the stream bound into a bound along the run, where \(\sum _a N_a(t) = t\). The rate function of a dominated arm is at least the extended divergence of its family.

The GLRT errs only if the evidence against the true model exceeds the threshold at some round, which does not happen at round \(0\), where the evidence vanishes. With \(\eta = p\log 2/(2K)\), \(2K\eta \lfloor \log _2 n\rfloor \le p \log n\), so the thresholds dominate those of lemma 31.

For \(n \ge 1\), \(\log (C n^p/\delta ) \ge p \log n + c_{p,K} + 2x_\delta \), and \((x_\delta /K)^K e^{K - x_\delta } \le \delta \) with \(x_\delta \ge K\) (LMLExplore).

The models with unique best arm \(a\) are an intersection of finitely many strict inequalities between means, intersected with the open set of the restriction. The closed form of lemma 5 is continuous on the vectors of means of the family with best arm \(a\) and the nonnegative allocations, a neighbourhood of \((\mu , w)\) within \(\mathbb {R}^K \times \Sigma _K\), since the set of means of the family is open.

Take \(1/c {\lt} \eta {\lt} \kappa \) and \(L = \log (1/\delta )\). From the round \(N = \max (M, \lceil L/\eta \rceil )\) on, for a fixed \(M\), the threshold is at most \(L + (\kappa - \eta ) N / 2 {\lt} \kappa N\), so that \(\tau _\delta \le N \le M + L/\eta + 1\), which is at most \(cL\) when \(L\) is large.

By compactness of \(W\) and lower semicontinuity, \(D(\theta ', w', \neg i) {\gt} \kappa \) for \(\theta '\) near \(\theta \) and \(w'\) in the simplex near \(W\), which \(\hat\theta _t\) and \(N(t)/t\) are for all large \(t\).

On the almost sure event of the convergences, lemma 36 gives the linear growth of the statistic, and lemma 35 the bounds on the stopping time.

The rewards of the successive pulls of an arm are i.i.d. with the law of the arm (in LML), and after \(N_a(t)\) pulls the empirical mean is the mean of the first \(N_a(t)\) of them: the strong law of large numbers applies.