Covariance Adaptive Best Arm Identification

Summary

This work focuses on best arm identification, that is, determining the arm with highest average return within a small number of samples (sample complexity). The twist is that authors propose a framework where sets of arms (of arbitrary size) can be queried at the same time, and the set of corresponding rewards is observed. This setting goes beyond classical frameworks, as observations in a set of simultaneously queried arms are dependent. Moreover, the arm pairwise covariances are unknown to the bandit algorithm. Authors propose an algorithm tackling this problem, which nearly matches associated lower bounds, and empirically evaluate it.

Strengths

- Originality: Authors introduce a novel best arm identification setting which might have interesting real-life applications. Differences with prior works are thoroughly discussed and the discussion covers a large set of related settings. - Quality: The results in this paper seem technically sound, although I did not check the proofs in detail. The experimental study is convincing and supports theoretical claims. The code is available, which helps reproducibility and potential future follow-up. - Significance: The setting tackled in this paper introduces new technical challenges (in particular to derive lower bounds), and the technical tools used in proofs can be of independent interest.

Weaknesses

- Clarity: I appreciated the many examples provided in order to illustrate intuitions behind the papers, although I believe the section from Line 59 to Line 123 is a bit messy and hard to follow. Adding more structure to this section and clearly highlighting the different points covered in that paragraph would really help. - Significance: The number of rounds after which an arm can be safely eliminated from the set of “queriable” arms seems really large and not very practical. However, this weakness has been identified in this paper and properly discussed (notably by providing a version of the upper bound when elimination happens when an arm is not more considered a candidate).

Questions

- What would be the main hurdles in extending the lower bound theorems to any one-dimensional exponential family?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Authors have adequately addressed the issue related to the number of rounds after which an arm is completely eliminated from future queries. This paper deals with very theoretical guarantees, and, as such, do not present significant direct negative societal impacts.

Summary

Authors investigate the stochastic Best Arm Identification (BAI) problem when the arms have an unknown correlation structure. In contrast, the majority of BAI literature focuses on independent arms with unknown variances. Authors propose algorithms for BAI in two settings (bounded random variables and gaussian random variables) and analyze the sample complexity of these algorithms. In order to leverage the correlation structure, multiple arms are allowed to be sampled at each round. They show that improved sample complexity can be achieved by estimating the correlation structure; moreover, the sample complexity is within a constant factor of the sample complexity for independent arms (even when independence is unknown in advance). Simulations are run to demonstrate the method on a synthetic dataset.

Strengths

The main strength of the paper is an investigation into the stochastic BAI problem where independence between the arms is not assumed. Authors develop algorithms where the covariance structure is estimated and used to help quickly eliminate suboptimal arms. Of course, multiple arms must be sampled simultaneously in order to estimate the covariance between them. On one hand, the analysis (and simulations) show that nice speed-ups in sample complexity can be obtained when the covariance structure is taken into account. On the other hand, the analysis seems to indicate that the asymptotic rate of the sample complexity does not increase even when the arms are independent (but this dependence is unknown). This has exciting implications for a variety of real-world settings where arms may be expected to be correlated.

Weaknesses

There are two main weaknesses of the paper. The first main weakness is that the paper seems to not discuss (and sometimes ignore?) what I would consider to be a very important consideration: the "overhead cost" of estimating the covariance. It seems intuitive that a method which places no assumptions on the covariances -- and therefore must estimate them -- must incur some overhead cost when compared to a setting where there are structured assumptions on the covariance (e.g. the independent setting). This overhead cost may not be very large, but I am pretty certain that it should exist. A couple of times throughout the paper (Lines 103, 247) authors claim that the sample complexity bounds they obtain are smaller than the independent case; however, it seems that they are smaller than a constant factor (say, 2) of the sample complexity of the independent case. In terms of the asymptotic rate of the sample complexity, this doesn't matter; however, in terms of finite sample, practical performance, this does seem to matter and it points out exactly this "overhead cost". Overall, I think that the paper would be stronger if authors more appropriately discussed their results in this context, i.e. the existence of the overhead cost of estimating covariance relative to assuming it, but with large gains when dependencies help. The second weakness of the paper is that the exact nature of the guarantees on the sample complexity are not so clear. From what I understand, these algorithms need to contain the best arm with probability $1 - \delta$ for some total number of arm queries $N$ and this stopping time is a random variable. The goal of the algorithm designer is that, under appropriate conditions, $N$ is small in some sense, as a random variable. So what does it mean then in Theorems 4.1 and 5.1 that authors write $N \leq XYZ$? Does this happen with probability 1 (that seems unlikely)? Does this mean that $N$ is order $XYZ$ in probability? Or is $N$ not a random variable? Perhaps there is some convention in the BAI literature so that this is very clear; but to someone in adjcent fields, this could use clarification. I'm hopeful that this can be clarified and the fix is relatively easy. Further comments on clarity and discussion of results are given below. ### Minor Comments 1. (Line 58): What is the $\pi$ subscript in $N$ represent and why does it never appear again in the paper? Moreover, the last sentence in this paragraph seems to be a sentence fragment that is missing a part. 2. (Line 64): Could you describe more precisely what "comparing the means" is referring to here? What is the precise statistical problem i.e. estimation, hypothesis testing etc ? 3. (Line 71): A motivating example of clinical trials is discussed, "whre the effects of drugs on patients with similar traits or comparing drugs with similar components may exhibit underlying correlations". However, the correlation between counterfactual outcomes (arms) can't be simultaneosuly observed in a causal inference setting -- only one outcome may be observed for each patient, often known as the "fundamental problem of causal inference". I recommend rephrasing this motivation so that arms cannot be interpreted to be counterfactual (and thus not simulatenously observable) outcomes, or selecting a different motivating example. 4. (line 103): authors write that "quantity (3) is always smaller (up to a numerical constant) than its independent case counterpart". I think this is phrased in an unfortunately misleading way. I presume that the authors mean "quantity (3) is no larger than a constant times the independent case counterpart". Unfortunately, writing the phrase "always smaller" gives the wrong impression that quantity (3) is at most quantity (2), which does not seem to be true. Great care should be given to statements like this, so they are not misrepresenting what authors have shown. 5. (Line 140, 157) citations appear in parathensis when other citations appear in brackets. A consistent stlye should be used throughout the paper. 6. (Line 142) "The objective is to maximize the cumulative regret..." is this a typo, i.e. "maximize" should be "minimize"? 7. (Line 172): The estimated quantities $V_{i,j,t}$ and $\mu_{i,t}$ should be defined (markdown doesn't like the hat notation, sorry for dropping it). In particular, these quantities are perhaps ill-defined without reference to the algorithm: how should we interpret the sample covariance up to iteration $t$ if arm $i$ was sampled at some round $s \leq t$ but $j$ was not? 8. (Line 7 of Algorithm 2): "Jointly query all the experts in $C$". The terminology "experts" is not defined, so I'd recommend not using it here. 9. (Line 247): Authors write "the sample complexity is on the order $X$ which is larger than both our bounds (5) and (6)". If I understand correctly, it seems that the correct statement is that "(5) and (6) are less than 2 $X$". It seems very important for authors to correctly characterize their contributions so readers do not misinterpret them. 10. (Line 275): the reference (20) is perhaps misplaced. 11. (Line 305): "$\delta$-sound algorithm" is used but not defined. From context clues, I think I understand, but authors should clarify it for the readers. 12. (Line 309): Authors claim that "Algorithm 2 is nearly optimal" but this is up to a $\log(K)$ and $\log(\Lambda)$ factors. I understand $K$, but I think that $\log(\Lambda)$ deserves some discussion. How large should we expect this to be? 13. (Line 319): "Theorem 6.2 demonstrates that our algorithm achieves near-optimal performance...up to a logarithmic factor". Same as above. 14. (Line 329): Authors write that "We stress that both variants guarantee a $\delta$-sound decision on the optimal arm" but it seems that reducing $82 t$ to $2 t$ actually doesn't necessarily satisfy $\delta$-sound? If I am correct in this understanding, then the claim should be modified appropriately. 15. (Line 356): Authors write that there is "an algorithm that compares candidate arms with convex combinations of the remaining arms" but this is not discussed in the main body nor in the simulations. This seems it requires more discussion to better contextualize it within the current work or be removed all together. 16. (Line 347): Authors write "In both experiments, we observe that Pairwise-BAI+ performs worse compared to Pairwise-BAI, indicating that, empirically, in the given scenarios, continuing to sample sub-optimal arms does not contribute to improved performance". There is either a typo here or I am a bit confused. I thought that Pairwise-BAI+ was where the number of extra rounds was reduced, so if it performs worse wouldn't that indicate that we need those extra rounds? I think there is a typo, but I want to bring this to the attention of the authors to confirm or deny.

Questions

I think this paper makes some interesting and strong contributions. Unfortunately, I found some of the results and their discussions to be sufficiently confusing to a broader audience that I have set my score to "borderline reject". However, if authors can answer the following questions to clarify these points (especially the first two), then I am more than happy to raise my score. 1. Can you please respond to my comments on the confusion regarding what $N \leq XYZ$ means if $N$ is a random variable? I'm hopeful that you can clarify this for me. 2. Can you please respond to my comments on the overhead cost of estimating the covariance structure and whether my assessment that the sample complexity bounds are within a factor of two of the independent case is correct? 3. Can Assumption 3 be relaxed to subgaussian? If the answer is no, then why not? 4. Can you comment more on the "algorithm that compares candidate arms with convex combinations of the remaining arms"? Why does it not appear in simulations and does it offer any additional benefits over the proposed algorithms?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

yes

Summary

This paper considers the problem of best arm identification with covariance in the fixed confidence setting, where arms can be dependent and rewards can be sampled simultaneously. The authors design algorithms that adapt to the unknown covariance of arms and prove that substantial improvement can be achieved over the standard setting. The authors also provide lower bounds and experimental results that support their theoretical findings.

Strengths

1. The considered problem is interesting and well-motivated. 2. The theoretical analysis looks sound. Both upper and lower bounds are provided.

Weaknesses

1. What is the additional novelty and contribution of Theorem 5.1 compared to Theorem 4.1. It seems that there is no significant difference between the algorithm design and analysis for the bounded reward setting and that for the Gaussian reward setting. Why not unify them, e.g., present this work in the unified sub-Gaussian setting? Please correct me if my understanding is wrong. 2. Could you compare Theorems 4.1 and 5.1with the results of existing covariance-adaptive bandit works?

Questions

Please see the weaknesses above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Please see the weaknesses above.

Summary

This paper focuses on the question of identifying $\epsilon$-optimal arms given a confidence input $\delta$, or in other words, under the PAC model. Instead of pulling only one arm and observing the rewards, the authors leverage the underlying structure of arm distributions by allowing multiple queries per round (Protocol 1). Compared to related works, this paper looses the assumption of independent arms distributions, Protocol 1 can estimate the means and covariances of arms and accelerate the best arm identification by utilizing the extra information. They propose two algorithms, one for scenario where the arms are bounded, and one for arms follow a Gaussian distribution. The lower bounds for both algorithms are also provided.

Strengths

The idea of exploring the underlying structure of arms by allowing simultaneous queries is attractive. It not only solves the assumption of independent arms distributions, which is not realistic in various scenarios; but also accelerates best arm identification by leveraging the shared information between arms. Based on multiple queries protocol, the authors provide two main theorems for bounded variables and Gaussian distributions along with the corresponded lower bounds. They also manage to notice some failure mode of the algorithm, like shown in line 183, and give some solution. In addition, the paper is well-structured and easy to follow.

Weaknesses

The authors emphasize their results are adaptive to unknown covariance, but based on the algorithms and simulations, it can only solve the type of same covariance between all arms (correct me if I were wrong), which reduces the practical use of this paper. In addition, as stated in the related work part, the topic of best arm identification under PAC-Learning framework is well-studied, so as the stochastic combinatorial semi-bandit problem. The motivation and main contributions of this papers are a little bit unclear. As for the simulation part, It would be helpful to provide some explanation for the three chosen benchmark algorithms to add on reliability. I was expecting to see the comparison of proposed algorithm and old algorithms who assume independent arms on scenarios where the assumption fails.

Questions

1. Under the PAC framework, except for the confidence input $\delta$, the subtle difference $\epsilon$ is also important and related to the sample complexity, but I didn't find the involvement of this parameter in algorithms (like Theorem 4.1, line198). 2. If the assumption of arm independence holds, can we still use the proposed algorithms? Would there be a trade-off between complexity and generalization? 3. Could you provide a concrete example of the failure case mentioned in line 183? And how probably will this kind of failure happen?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

This paper trying to utilize the covariances between arms to accelerate best arm identification, what if we step further, using the causal relationship instead of association? I know some research have been done in this area (like Lattimore, 2016) It would be interesting to consider this as a future direction. The proposed algorithms, although allow the dependent arms distributions, still have many constraints, like limited type of variables, only suitable for same covariance, pairwise comparisons, which reduce the practicality of this paper.

Summary

This study addresses the problem of best arm identification (BAI) in the context of dependent arms. Unlike conventional settings, efficiency can be enhanced by exploiting the inherent correlation structure. This setting holds broad applications, including in clinical trials. Specifically, the authors concentrate on bandit scenarios with bounded and Gaussian rewards. The validity of their approach is substantiated through simulation studies.

Strengths

The authors introduce a novel setting for Best Arm Identification (BAI) with fixed confidence. By accommodating correlation, we can devise more efficient strategies for identifying the optimal arm. This setting is intriguing and holds significant practical utility.

Weaknesses

I believe several claims are not sufficiently substantiated. I have detailed these claims in the subsequent 'Questions' section. If the authors fail to adequately address my queries, these unsupported claims would constitute a weakness in the study.

Questions

- In line 81, what does $\epsilon\mathcal{N}(1, 1)$ denote? - In line 83, the authors suggest that since two queries are possible, the learner can perform a $T$-test. However, even in standard BAI, a setting based on such a hypothesis test, as suggested by the authors, exists. For instance, refer to Balsubramani & Ramdas (2016). - Therefore, considering a hypothesis test in itself is feasible even in the standard setting. I believe that the key here is the variance reduction effect facilitated by two queries. - In lines 84-86, the authors present an example of two-armed Gaussian bandits. They argue that the lower bound in standard BAI is $O((1+\epsilon)^2\log (1/\delta) / \epsilon^2)$. This seems to be a lower bound for the one-armed bandit problem. As highlighted by Kaufmann et al. (2016), the lower bound for two-armed Gaussian bandits is given as $O(Var(X_1 - X_2)) \log (1/\delta) / \epsilon^2)$ by assuming there are two arms, $Y_1 \sim N(\epsilon, Var(X_1 - X_2))$ and $Y_2 \sim N(0, 0)$. As I stated earlier, the essence of this example is not two queries, but treating two arms as one and comparing this combined arm to an arm that returns zero. - For the related work section, I suggest considering the literature on BAI on graphs as it also deals with similar problems. Although the authors cite a few studies in this field, could these studies be related to yours? - In line 125, the authors state that "BAI in the fixed confidence setting was studied by [8], [19], and [9], where the objective is to find $\epsilon$-optimal arms under the PAC model." Fixed confidence BAI is not confined to $\epsilon$-best arm identification. For instance, [17] considers a different objective. - Subsequently, the authors claim that "A summary of various optimal bounds for this problem is presented in [5, 17]." Here, [5] considers lower bounds in BAI with a fixed budget, which is a different setting. [17] addresses the fixed-confidence BAI problem, but the objective is not $\epsilon$-optimal arms. - In addition to the related work raised by the authors, it seems that Kato and Ariu (2021) have explored BAI with dependent arms for more specific cases. For example, they consider two-armed Gaussian bandits where rewards are correlated via contextual information. How is their study relevant to yours? Balsubramani and Ramdas, Sequential nonparametric testing with the law of the iterated logarithm, UAI 2016. Kato and Ariu, The Role of Contextual Information in Best Arm Identification, 2021.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

None.

response to authors

I thank the authors for their thoughtful response to my review. **Question 1**: I thank author for their answer. This confusion seems to be entirely mine. **Question 2**: I completely acknowledge that the overhead cost can be mild in typical cases, especially with strong correlations. It just seems like it must be there in the "worst case". By reading other responses, I think authors agree. It would be good to be more transparent in the paper about this. **Question 3**: thanks for the helpful elaboration! **Question 4**: thanks. I will raise my score to reflect the updated answers.

Response to the rebuttal

I thank the authors for their global rebuttal and their answer to my question. As my score is already positive, with respect to potential impact, I will keep the score as it is for now.

Thank the authors for their response

Thank the authors for their response. My concerns were addressed. I raised my score from 5 to 6.