Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids

Thank you for your insightful comments. We have a few clarifying questions regarding your concerns and would appreciate your feedback.

1. In certain cases, IS-SE can have fewer batches than $\log(1/\Delta)$. Why is this the case, and when would this happen?

   Could you clarify your concern here? Are you questioning why IS-SE can achieve a batch complexity lower than $\log(1/\Delta_2)$, or are you uncertain about the calculation of the batch complexity for IS-SE? Additionally, regarding the question of "when would this happen," would you like us to provide more examples where IS-SE’s batch complexity outperforms $\log(1/\Delta_2)$?

2. Does this truly imply $\mathcal{O}(1)$ batches (since SE still needs $\log(1/\Delta_2)$)? This is not entirely clear.

   Are you seeking further details on the calculation of IS-SE's batch complexity as it pertains to Examples 1-3?

Thank you, and we look forward to your guidance on these points.

Thank you for your comments.

Q1: A significant issue is that the two algorithms lack empirical support, making it challenging to convince readers of their practical value.

A1: Thank you for your feedback. We would like to emphasize that our original submission included experimental results for the MAB setting in Section 3.3, demonstrating the advantages of IS-SE in terms of the sample complexity-batch complexity trade-off. To strengthen the empirical support, we have added experiments in our revision for both linear bandits and real-world datasets in Section 5 of the new version. The results consistently show that our frameworks improve the sample complexity-batch complexity trade-off, providing further evidence of their practical value.

Q2: Breaking the $\log (1/\Delta_2)$ barrier appears to be conditional, depending on the number of arms with nearly optimal means being relatively limited compared to the total number of arms. In such cases, the allocation may rapidly focus on only a few arms. I am uncertain whether these algorithms offer any advantage over the original SE under these conditions.

A2: The reviewer is correct that “breaking the $\log (1/\Delta_2)$ barrier appears to be conditional.” Indeed, as mentioned in the abstract of our paper, the batch complexities of our algorithms depend on the input instance, particularly the mean gaps of the suboptimal arms. This instance dependency is precisely why we describe our batch complexity as instance-sensitive. Compared to SE (which achieves a $\log (1/\Delta_2)$ batch bound), the advantage of our algorithm lies in its continuous estimation of the instance sample complexity $H_I$, which is then used to allocate the sample budget for the next round.

However, we are unclear about what the reviewer meant by “whether these algorithms offer any advantage over the original SE under these conditions.” If the reviewer wanted to see more explanations on the examples that we provide in our submission, we would like to use Ex. 2 as an example to demonstrate why our algorithms have advantage over SE.

Recall the definition of $R_I$. We start with $\bar{L}\_0=1$ and $U\_{0}=\emptyset$, and recursively define for $r=1,2,\cdots$ the quantities

$\bar{L}\_{r}=4\bar{L}\_{r-1} +\frac{1}{n-|U\_{r-1}|}\sum\_{j\in U\_{r-1}} \frac{1}{\Delta\_j^2}$ and $U\_{r}=\{j: \Delta\_j\geq \sqrt{\frac{1}{\bar{L}\_r}} \}.$

We stop when $U\_r = [n]\backslash \{\text{best arm}\}$. Let $R_I$ be the value of $r$ when we stop. (We have set $C=1$ here for simplicty in the calculation. This choice does not affect the asymptotic complexity of $R_I$)

In Ex. 2, the best arm has mean $\frac{1}{2}$; $(n-\log_2 n+1)$ arms have mean $(\frac{1}{2}-\frac{1}{2})$; $1$ arm has mean $(\frac{1}{2}-\frac{1}{4})$; $1$ arm has mean $(\frac{1}{2}-\frac{1}{8})$; $\ldots$, and $1$ arm has mean $(\frac{1}{2}-\frac{1}{\sqrt{n}})$.

We have $\bar{L}\_{1}=4$, $U\_{1}=\{ \text{arms with gap at least } 1/2 \}$. Then we have

$\bar{L}\_{2}= 4 \cdot \bar{L}\_{1} + \frac{1}{\log_2 n - 1}\cdot (n-\log_2n+1) \cdot 4 = \frac{4n}{\log n} + o(\frac{n}{\log n}),$ and $U_2= [n] \backslash \{\text{best arm}\}$. Therefore, $R_I = 2$. On the other hand, the batch complexity of SE is $\log (1/\Delta_2) = \log\sqrt{n} = \Theta(\log n)$.

Q3: The issue of a small gap $\Delta_2$ is more serious in the fixed-budget setting and has been observed in Bayesian Best Arm Identification (BAI). For example, the paper Exploration for Fixed-Budget Bayesian Best Arm Identification (arXiv: 2408.04869) discusses this. More related work should be considered.

A3: We thank the reviewer for providing a reference. However, we would like to clarify that our paper focuses on batch bandits for the best-arm identification task in a fixed-confidence setting. In contrast, the paper “Fixed-Budget Bayesian Best Arm Identification” addresses the fixed-budget best-arm identification problem in a Bayesian setting and does not consider batch complexity. As such, we believe this paper is not directly relevant to our work in terms of either techniques or topics. Concrete pointers to the missing works would be very helpful, but we will certainly conduct a more thorough review of the relevant literature.

Thank you for your comments!

Q1: There are some improvements in the experiments, showing roughly a 2x gain, but it's hard to call them impressive, as the experiments are limited in scale and only cover simple problem instances. Additionally, there are no experiments on the linear bandit setting.

A1: Thank you for your valuable feedback. We understand your concerns regarding the scale and scope of the experiments. First, we would like to highlight that the primary contribution of our work lies in introducing and studying the concept of instance-dependent batch complexity for the first time. Through our theoretical analysis, we propose a refined instance-dependent batch complexity measure, $R_I$, which suggests that significant improvements can be achieved for certain bandit instances. As such, we feel it may not be entirely appropriate to evaluate the quality of our work solely based on the experimental setup.

Regarding the performance gains of our proposed algorithms, we believe the observed improvements in the sample complexity-batch complexity trade-off are indeed meaningful and significant. To address your concerns about the experimental settings, we have expanded the scope of our evaluation to include linear bandit settings and real-world datasets, such as Movielens25M. These new experiments introduce more realistic and challenging scenarios, further validating the effectiveness of our proposed algorithms (IS-SE, IS-RAGE) compared to the baselines (SE, RAGE). We hope these additions provide a more comprehensive view of our contributions and results.

Q2: The contribution mainly reduces a logarithmic factor in batch complexity by transferring it to sample complexity. However, it’s difficult to see an absolute impact on the field.

A2: We believe this is a misunderstanding. To clarify, we present the following two points.

1: We would like to refer the reviewer to Remark 3.4, Lines 282-288. The previous work (SE) cannot achieve a batch complexity $O(\log (1/\Delta_2))$ by simply increasing its sample complexity by logarithmic factors.

2: The primary objective of this paper is to show that an $\log(1/\Delta_2)$ batch complexity is not instance-optimal and to propose an algorithm that improves upon this batch complexity. Regarding sample complexity, our goal is to achieve a nearly optimal solution, up to logarithmic factors. This approach aligns with the methodology of many previous works on batched bandits. For instance, in [1] and [2], the proposed algorithms achieve regret or sample complexity that matches the optimal bounds within logarithmic factors.

[1]: Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. In NeurIPS, 2019.

[2]: Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In FOCS, pp. 126–146. IEEE, 2019.

Our work shows that for the best-arm identification task, near-optimal sample complexity can be achieved with a batch complexity lower than $\log(1/\Delta_2)$ for many input instances. In some cases, the batch complexity can even be constant. To the best of our knowledge, this instance-sensitive batch complexity is the first result of its kind in the bandit literature.

Q3: Experiments in terms of RAGE for linear bandits.

A3: In our revision, we have included an empirical comparison between RAGE and IS-RAGE in Figure 2.d to Figure 2.f, Section 5, focusing on examples $B_1(n)$ to $B_3(n)$. The results demonstrate that IS-RAGE offers a better sample complexity-batch complexity trade-off compared to RAGE. However, the magnitude of improvement depends on the specific problem instances, similar to the comparisons we conducted for the MAB setting. For example, in instances $B_1(n)$ and $B_2(n)$, the improvements are clear and significant, while for instance $B_3(n)$, the improvement is more modest. We hope this provides a clearer understanding of the advantages of our proposed algorithm.

Thanks for your positive feedback!

Q1: Some numerical comparisons will strengthen this paper, and also illustrate the improvements of the proposed algorithms.

A1: In response to your suggestion, we have expanded our experimental evaluation. In addition to the previously conducted experiments for multi-armed bandits (MAB), we have now included experiments on linear bandits as well as a real-world dataset, Movielens25M. The results demonstrate that our proposed algorithms (IS-SE, IS-RAGE) outperform the baseline methods (SE, RAGE) in terms of the trade-off between sample complexity and batch complexity.

Q2: Minor writing suggestions.

A2: Thanks for your suggestion. We have added a footnote for $\Delta_2$ to demonstrate its definition, and we also added more discussions about CL during the related work section.

Q3: Any study on the lower bound on sample complexity given the lower bound batch complexity?

A3: While we believe our sample complexity upper bound is tight up to logarithmic factors, proving a corresponding lower bound poses significant challenges. Existing techniques cannot be directly applied in this setting. We think that the proof would share similarities with the lower bound for best-arm identification (BAI) in the collaborative learning model, as presented in [1]. We would like to mention that the proof in [1] is already highly involved, and extending it to account for both sample and batch/round instance-sensitivity would be even more complex. We leave this as a direction for future work.

[1]: Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In FOCS, pp. 126–146. IEEE, 2019.