The Batch Complexity of Bandit Pure Exploration

We thank the reviewer for their insightful suggestions.

The suggested paper, ``Optimal $\delta$-correct best arm selection for heavy tailed distributions'', contains a BAI algorithm for a different class of non-parametric distributions (given by a moment constraint). They also use batches in a Track-and-Stop method. The main motivation for the batches seems to be to reduce the computational cost of the algorithm, and minimizing the expected batch complexity is not a goal they consider (and no bound is given). They mostly use constant batch sizes, which would lead to a batch complexity that is proportional to $\log(1/\delta)$, which should not be the case according to the lower bound. Thank you for the reference: we will include discussion of that paper in our revision.

On the usage of an $l$-norm instead of a KL divergence, it is first due to our goal of tackling the non-parametric sub-Gaussian setting, in which this is the natural distance measure. If we were to consider parametric families of distribution, we would want to use a KL divergence. However a hurdle with that lies in Lemma 3.10. Indeed, we would need to have guarantees about the variation of the KL in a confidence region around a mean estimate. Investigating how to get past this problem and generalize the results for $\tilde{T}^*$ instead of $T^*$ would be interesting future work.

We do not understand the last question about recovering the results of Garivier and Kaufmann 2016 by imposing structure on the batches. Could you expand on what you mean by that question? Their algorithm is not batched (or rather has all batches of size 1), so we don't see what the structure on the batches would be.

We are thankful to the reviewer for their helpful comments.

Firstly, we'd like to redirect the reviewer to the two last paragraphs of our response to reviewer yvDd: the bound on the sample complexity in Theorem 3.11 was not accurate in the regime of big $T_0$. The parameter $T_0$ impacts the size of the first batch, and needs to strike a balance between sample optimality for easy instances, and round complexity for hard instances. We have not tried varying $T_0$ in the experiments, to try and keep all the compared algorithms with the same initial batch size so none would be particularly penalized by how easy/hard the tested instance was.

We have thought of a few ways to replace uniform exploration. One would be to try and generalize BAI arm elimination schemes (see for example Algorithm 2 of Jin et al 2023), in which suboptimal arms stop being sampled. In general pure exploration, one could imagine stopping an arm $i$ once $N_i\geq \overline{w}^*_i(B)\overline{T}^*(B)$, since no instance in the confidence set would require more samples of that arm. We could also forgo uniform sampling altogether, only sampling according to $\overline{w}^*(B)\overline{T}^*(B)$ at each batch. However, either of those methods would make the confidence set $B$ behave in more complex ways.

In the most general setting we consider, there is no obvious way of computing $\overline{w}^*(B)$ and $\overline{T}^*(B)$. Under Assumption 3.9, one would need to compute $w^*(\mu)$ and $T^*(\mu)$ over $B$ and find the supremum of $T^*$ (heuristically, finding the most difficult instance in $B$). However, in BAI and thresholding this is much easier, since we know precisely where the hardest instance $b$ lies. In BAI, it is the instance in which the best arm is moved down as much as possible, and the other arms moved up as much as possible. In thresholding, it is the instance in which every arm is moved closer to the threshold. See Appendix C.5 for the proofs, and line 1330 for definition of $b$ in the BAI case. Because of this, computing $\overline{w}^*(B)$ and $\overline{T}^*(B)$ has exactly the same cost as computing $w^*(\hat{\mu}_t)$ and $T^*(\hat{\mu}_t)$ in Track-and-Stop, and any method used to compute those also applies to our algorithm.

We are grateful for the reviewer's insights and corrections.

Thank you for pointing out a few unclear passages. In Assumption 2.2, $y$ (in normal font) is a scalar, and $\bf{y}$ (in bold) is the vector $(y,y,...,y)$. We will make sure to clarify this. In Algorithm 1, we indeed did not detail where $r$, $t$ and $N_i$ (respectively the round count, the timestep count, and the number of samples of arm $i$) are updated. We will add a line to explicitly mention their update.

In Lemma 2.1, $T_{\min}$ and $T_{\max}$ are indeed specific to the algorithm - and to the degree of optimality considered, impacting the values of $\gamma$ and $c$ - all algorithms are not uniformly optimal everywhere. While $T_{\max}$ could be set to $+\infty$ for some algorithms, fixing some $T_{\min}$ is necessary to guarantee the finiteness of $\gamma$, as explained around line 209. No algorithm can achieve a sample complexity that is withing a constant multiple of $T^*$ if $T^* \approx 10^{-10}$, as every arm must be sampled at least once: $T_{\min}$ should be at least of order 1. That Lemma should also indeed use $S_N$ instead of $S_n$, thank you for noticing that typo.

It is correct that $T_0$ should have more of an impact on the bound of Theorem 3.11. This bound is indeed only valid for $T_b^*(\mu)$ big enough compared to $T_0$. More precisely, in the Appendix, line 1173, $r_0$ and $r_1$ are necessarily strictly positive, which we forgot to reflect in the final bound. To account for the case of large $T_0$, the batch complexity bound should be modified to be the maximum of 4 and the expression in Theorem 3.11. In the sample complexity bound, one needs to replace every instance of $T_b^*(\mu)$ with $\max\{ T_b^*(\mu),32KT_0\ln(2\sqrt{2K}T_0)\}$. We are very thankful to the reviewer for pointing out this mistake.

With that correction, one can see the need to balance $T_0$: a very small $T_0$ will lead to a small initial batch size, so we can efficiently solve even easy instance without wasting sample complexity, but at the cost of way more batches for complex instances. A very big $T_0$ will minimize the number of batches required, but the initial batch might be way bigger than necessary, requiring more samples than would be optimal.

We thank the reviewer for their helpful suggestions.

The inequality on line 94 comes from Donsker-Varadhan duality, and can more precisely be found in Lemma 2 of Wang 2021, upper bounding the difference of means by the square root of the KL divergence for two sub-Gaussian variables.

Lemma 3.1 is a version of the Chernoff stopping rule (relaxed with the same inequality as above), which can be found for BAI in Garivier and Kaufmann 2016. One can find a generalization of the Chernoff stopping rule for any pure exploration problem for example in Theorem 1 of Degenne et al. 2019 (Non-asymptotic Pure Exploration by Solving Games). Our concentration result is in Lemma 3.2. While this specific threshold beta is a new result, it employs the classic techniques used to derive such Chernoff stopping rule thresholds (we were surprised not to find such a threshold for the sub-Gaussian case in the literature).