3 The optimal allocation
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)\).
In LMLExplore.
At the optimal allocation, the costs of all the pairs \((a^*, b)\) are equal.
In LMLExplore.
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).
The paper-level form of Part II, theorem 21: for \(w\) optimal, \(x = w / w_a\) and \(y\) the common cost of the pairs divided by \(w_a\); conversely, \(w = x / \sum _c x_c\), whose pairs all cost \(y / \sum _c x_c\) by homogeneity, with the same weighted means as \(x\).
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 )\).
Parts (1) and (2) are in LMLExplore (pos_of_mem_optAlloc_baiTask_restrict, continuousAt_of_mem_optAlloc_baiTask_restrict); part (3) is theorem 23. The paper proves part (3) with the scalar equation of theorem 7. The proof here uses only lemma 6 and the monotonicity of the pair costs.