6 Conclusion

We prove that in most fixed budget identification tasks, if a class containing the static proportions algorithms admits a complexity then it is \(H_{\mathcal C^{sp}}\). However, even in simple tasks like Positivity or BAI with two Bernoulli arms, we showed that there is no such complexity. For other classes like Thresholding bandits the question is still open. We know that the maximal difficulty ratio of APT [ LGC16 , ODGP21 ] for Gaussian thresholding bandits is less than an absolute constant, so there is no lower bound that depends on \(K\). Another open question is whether there exists a complexity in Gaussian BAI for small \(K{\gt}2\). We conjecture that there is none.

An important question remains: is there a meaningful class for which there exists a complexity in BAI? We showed that it would need to exclude some static proportions algorithms. A candidate could be algorithms with difficulty ratio to the uniform allocation less than \(n{\gt}1\). That class contains \(\mathcal C_{1/n}^{sp}\), static proportions with \(\min _k \omega _k \ge 1/n\). We can show \((1 - 1/n) H_{\mathcal C^{sp}}^{-1} \le H_{\mathcal C^{sp}_{1/n}}^{-1} \le H_{\mathcal C^{sp}}^{-1}\), which means that a lower bound of 1 for \(H_{\mathcal C^{sp}}\) would give a \((1 - 1/n)\) bound here: an adaptive algorithm could possibly beat all such static allocations everywhere, but only by that constant factor.

If there is no complexity, there can be many “good” algorithms. First, we should look for algorithms with smallest maximal difficulty ratio, as pioneered by [ KTH22 ] . Successive Rejects is such an algorithm for Gaussian BAI. Then we may want to design methods that are better than the minimax lower bound on some parts of the space (and necessarily worse elsewhere). Can we design an algorithm that sacrifices performance on very easy problems in order to beat the lower bound on more interesting instances?