5 No Complexity in Best Arm Identification

We have investigated the possible values for the difficulty ratio over different identification tasks. We now focus on best arm identification, with \(\mathcal I = [K]\) and \(i^\star \) the arm with highest mean. We show that for several values of \(\mathcal D\), \(\inf _{\mathcal A \in \mathcal C_{\infty }}\sup _{\lambda \in \mathcal D} R_{H_{\mathcal C}, \infty }(\mathcal A, \lambda ) {\gt} 1\) for any class \(\mathcal C\) that includes the static proportions algorithms. We conclude that these classes don’t admit a complexity.

5.1 Gaussian best arm identification

Theorem 7

Consider the BAI task with Gaussian distributions with variance 1. For any class \(\mathcal C\) containing the static proportions algorithms, \(\inf _{\mathcal A \in \mathcal C_\infty } \sup _{\lambda \in \mathcal D} R_{H_{\mathcal C},\infty }(\mathcal A, \lambda ) \ge (3/80)\log (K)\) .

This proves that for \(K\) large enough, no algorithm class containing the static proportions admits a complexity in Gaussian BAI. It applies to (exponentially) consistent algorithms and to algorithms that have a difficulty ratio to the complexity of the uniform allocation which is uniformly bounded.

Proof ▼

First, since \(\mathcal C^{sp} \subseteq \mathcal C\), for any algorithm \(\mathcal A\) and \(\mu \in \mathcal D\), \(R_{H_{\mathcal C}, T}(\mathcal A, \mu ) \ge R_{H_{\mathcal C^{sp}}, T}(\mathcal A, \mu )\). It suffices to give a lower bound for \(H_{\mathcal C^{sp}}\).

Let \(H_{\Delta }(\mu ) = \frac{2}{\min _{k : \Delta _k{\gt}0} \Delta _k^2} + \sum _{k:\Delta _k{\gt}0} \frac{2}{\Delta _k^2}\). It was shown by [ GK16 ] that for all \(\mu \in \mathcal D\), this function satisfies the inequalities \(H_\Delta (\mu ) \le H_{C^{sp}}(\mu ) \le 2 H_\Delta (\mu )\) . Thus \(R_{H_{\mathcal C}, T}(\mathcal A, \mu ) \ge R_{H_\Delta , T}(\mathcal A, \mu ) / 2\). From this point on, we use a construction similar to the one that was used by [ CL16 ] to prove a lower bound on the ratio to \(H_\Delta \) for Bernoulli bandits. We define a Gaussian problem \(\mu \) by \(\mu _1 = 0\) (or any arbitrary value) and \(\mu _k = \mu _1 - k \Delta \) for all \(k \in \{ 2, \ldots , K\} \) and some \(\Delta {\gt} 0\). We apply Corollary 1 to \(\mu \) and \(\lambda ^{(2)}, \ldots , \lambda ^{(K)}\) where each \(\lambda ^{(j)}\) is identical to \(\mu \) except that \(\lambda ^{(j)}_j = \mu _1 + (\mu _1 - \mu _j)\). The details can be found in appendix D.

The closest existing result is the lower bound of [ CL16 ] . They don’t consider the difficulty of fixed proportions but \(H_\Delta \), the sum of inverse squared gaps. That function was hypothesized to be a complexity for fixed budget at the time. They present a set of Bernoulli problems and show that for all algorithms that return \(\hat{i}_T = i^\star (\hat{\mu }_T)\), there is a lower bound on the probability of error on one problem in the set. Their lower bound can be rewritten as a bound on \(\sup _{\lambda \in \mathcal D} R_{H_\Delta ,T}(\mathcal A, \lambda )\). It is not asymptotic in \(T\), but we could also obtain a non-asymptotic bound by using Theorem 2 instead of Theorem 3 when deriving Corollary 1 at the cost of additional low order terms. Their result is valid only for algorithms that return the empirical correct answer and does not for example apply to Successive Rejects, while we derive a result for any algorithm.

5.2 Two arms best arm identification with Bernoulli distributions

In BAI with two arms and Gaussian distributions with known variances (possibly different for each arm), there is a unique static proportions oracle, independent of the means (see [ KCG16 ] ). Thus that same algorithm matches the lower bound on all \(\mu \in \mathcal D\) and fixed budget BAI with two Gaussian arms has a complexity. We showed that as \(K\) becomes large, this is no longer the case. In Bernoulli bandits, we show that there is no complexity even for \(K = 2\).To prove that result, we will apply Corollary 1 to well chosen mean vectors. In order to do so, we first compute explicitly the oracle difficulty of static proportions algorithms.

Lemma 1

In a two arms BAI problem with Bernoulli distributions,

\begin{align*} (H_{\mathcal C^{sp}}(\mu ))^{-1} & = \mathrm{KL}\Big(\frac{\log \frac{1 - \mu _2}{1 - \mu _1}}{\log \frac{\mu _1(1 - \mu _2)}{(1 - \mu _1)\mu _2}}, \mu _1\Big) = \mathrm{KL}\Big(\frac{\log \frac{1 - \mu _2}{1 - \mu _1}}{\log \frac{\mu _1(1 - \mu _2)}{(1 - \mu _1)\mu _2}}, \mu _2\Big) \: . \end{align*}

Theorem 8

In BAI for Bernoulli bandits with two arms, for any class \(\mathcal C\) containing the static proportions algorithms, \( \inf _{\mathcal A \in \mathcal C_\infty } \sup _{\lambda \in \mathcal D} R_{H_{\mathcal C}, \infty }(\mathcal A, \lambda ) {\gt} 1 \) .

The lemma is a special case of a more general result which applies to all exponential families: Lemma 7 in Appendix D. The proof is an explicit computation. We now apply Corollary 1 to \(\mu = (x(1+x), x)\) for some \(x\in (0,1/2)\), \(\lambda ^{(1)} = (x/2, x)\) and \(\lambda ^{(2)} = (x(1+x), 1/2)\). This gives an explicit lower bound, function of \(x\). The limit of that bound at 0 is approximately \(1.22\), which means that there exists \(x\) small enough for which it is greater than 1. Theorem 8 is proved (see Appendix D for details). Values \(x\) for which we get a lower bound greater than 1 are very small, \(10^{-9}\) and lower. We used Corollary 1 and not Theorem 3 because it allows a closed form computation of the bound, but by doing so we may have lost constants. It is possible that we could show a lower bound greater than 1 for \(x\) which is not so close to 0.