Covariance-adaptive best arm identification
Authors: El Mehdi Saad
Gilles Blanchard
Nicolas Verzelen
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-armed bandits
Best-arm identification
Adaptive identification
TL;DR: In this paper, we introduce and analyze novel algorithms that exhibit adaptability to the unknown covariance between arms in the context of the fixed confidence best arm identification problem.

Abstract: We consider the problem of best arm identification in the multi-armed bandit model, under fixed confidence. Given a confidence input $\delta$, the goal is to identify the arm with the highest mean reward with a probability of at least $1 - \delta$, while minimizing the number of arm pulls. While the literature provides solutions to this problem under the assumption of independent arms distributions, we propose a more flexible scenario where arms can be dependent and rewards can be sampled simultaneously. This framework allows the learner to estimate the covariance among the arms distributions, enabling a more efficient identification of the best arm. The relaxed setting we propose is relevant in various applications, such as clinical trials, where similarities between patients or drugs suggest underlying correlations in the outcomes. We introduce new algorithms that adapt to the unknown covariance of the arms and demonstrate through theoretical guarantees that substantial improvement can be achieved over the standard setting. Additionally, we provide new lower bounds for the relaxed setting and present numerical simulations that support their theoretical findings.

Covariance adaptive best arm identification
EI Mehdi Saad
Université Paris-Sacalay, CentraleSupéléc Laboratoire des Signaux et Systèmes
Paris, France
el-mehdi el-mehdi. www.dcoontralesseeee...... fr
Gilles Blanchard
Institut de Mathématique O'Orayy
Université Paris-Saclay Paris, France
gilles blaachaardeun..erraieeeerrii-ss fr
Nicolas Verzelen
Mistea, INRAE
Institut Agro, Université de Montpellier
Montpellier, France
nicolass.errzelendinre...
Abstract
We consider the problem of best arm identification in the multi-armed bandit model, under fixed confidence. Given confidence input 8, the goal is to identify the with the highest mean reward with a probability of at least 1 - 8, while minimizing the number of arm pulls. While the literature provides solutions to this problem under the assumption of independent arms distributions, we propose a more flexible scenario where arms can be dependent and rewards be sampled simultaneously. This framework allows the learner to estimate the covariance among the arms distributions, enabling more efficient identification of the best arm. The relaxed setting we propose is relevant in various applications, such as clinical trials, where similarities between patients drugs suggest underlying correlations in the out- comes. We introduce new algorithms that adapt to the unknown covariance of the arms and demonstrate through theoretical guarantees that substantial improvement can be achieved over the standard setting. Additionally. we provide new lower bounds for relaxed setting and present numerical simulations that support their theoretical findings.
Introduction and setting
Best arm identification (BAI) is sequential learning and decision problem that refers to finding the arm with the largest mean (average reward) among a finite number of arms stochastic multi-armed bandit (MAB) setting. An MAB model is set of K distributions in R: V1...., VKK with means #1.... РK. An "arm" identified with the corresponding distribution index. The observation consists in sequential draws (" ("queries" or "arm pulls") from these distributions, and each such outcome a "reward". The leamner's goal is to identify the optimal arm i := Arg Max [x] Ps. efficiently. There are two main variants of BAI problems: The fixed budget setting [1, 8), where given fixed number of queries T, the learner allocates queries candidates arms and provides
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

guess for the optimal am. The theoretical guarantee in this case takes the form of an upper bound on the probability Pr of selecting a sub-optimal arm. The second variant is the fixed confidence setting [14, 20], where confidence parameter å E (0. 1) is given as input to the learner, and the objective to output an arm vo E [K]] such that P( = -)) 2 1 using the least number of arm pulls The complexity in this case corresponds to the total number of queries made before the algorithm stops and gives a guess for the best arm that is valid with probability at least - according to a specified stopping rule. In this paper we specifically focus the fixed confidence setting.
The problem of best-arm identification with fixed confidence was extensively studied and is well understood in the literature [16, 19, 20, 14]. However, in these previous works, the problem was considered under the assumption that all observed rewards are independent. More precisely, in each round t, fresh sample (reward vector), independent of the past, (X1.,..... xx,) ) is secretly drawn from v by the environment, and the learner is only allowed to choose one arm A, out of K (and observe its reward X .). We relax this setting by allowing simultaneous queries. Specifically, we consider the MAB model as a joint probability distribution of the K arms, and each round the learner chooses a subset C. C [K] and observes the rewards (Xe,))ec, (see the Game Protocol 1). The high-level idea of our work that allowing multiple queries per round opens up opportunities to estimate and leverage the underlying structure of the arms distribution, which would otherwise remain inaccessible with one- mee-point feedback. This includes estimating the covariance between rewards at the same time point. It is important to note that our proposed algorithms do not require any prior knowledge of the covariance between arms.
Throughout this paper, we consider two cases: bounded rewards (in Section 4) and Gaussian rewards (in Section 5), with the following assumptions:
Assumption 1. Suppose that:
IID assumption with respect to t: (X1)121 "h,t...,xK,,)ee, independent and identically distributed variables following v.
There is only one optimal arm: Arg Max U4 =
Assumption 2 BB. Bounded rewards:
The support of is in [0, 1]A
Assumption G. Gaussian rewards: v is multivariate normal distribution.
Protocol The Game Protocol
Parameters: 8.
while [condition] do
Choose a subset C' C [K].
The environment reveals the rewards (Xi)ieo end while Output the selected arm: tb.
A round corresponds to iteration in Protocol 1. Denote by i* [K] the optimal arm. The learner algorithm consists of: a sequence of queried subsets (Ct), of [K]. such that subset C, at round t is chosen based on past observations, halting condition to stop sampling (i.e. stopping time written T) and an arm & to output after stopping the sampling procedure. The theoretical guarantees take the form of high probability upper-bound the total number N of queries made through the game:
N
Σ 1=1
C.l.
2 Motivation and main contributions
The query complexity of best arm identification with independent rewards, when arms distributions o-sub-Gaussian characterized by the following quantity:
H(v) = Σ
(2)
RE[KTHE* (44- - 24)
Some 5-PAC algorithms [16] guarantee a total number of queries satisfying 7 = Ō(H(v) (og))
(where (() hides logarithmic factor in the problem parameters).

---

Recall that the number of queries required for comparing the means of two variables, namely X1 ~
((p, 1) and X2 ~ 1), within a tolerance error 6, is approximately (log(L/6))/(4
p22))) An alternative way to understand the sample complexity stated in equation (2) is to view the task of
identifying the optimal arm as synonymous with determining that the remaining arms [A] \ {
are suboptimal. Consequently, the cost of identifying the best arm corresponds to the sum of the comparison costs between each suboptimal arm and the optimal one.
In practical settings, the arms distributions are not independent. This lack of independence can arise in various scenarios, such as clinical trials, where the effects of drugs on patients with similar traits or comparing drugs with similar components may exhibit underlying correlations. These correlations provide additional information that can potentially expedite the decision-makingg process [18].
In such cases, Protocol allows the player to estimate the means and the covariances of arms. This additional information naturally raises the following question:
Can we accelerate best arm identification by leveraging the (unknown) covariance between the arms?
We give two arguments for a positive answer to the last question: When allowed simultaneous queries (more than one arm per round as in Protocol 1), the learner adapt to the covariance between variables. To illustrate, consider the following toy example for arms comparison: X1 ~ NV(1, 1) and X₂ X1 Y where Y (1, 1) for some e 0. BAT algorithms in one query per round framework require ((11 + c)² log(1 ( /0)/ queries, which gives ((log(1/5) (²²) for small In contrast, when two queries per round are possible, the learner can perform the following test Ho : "E[X| - X2] > 0" against Hi "E[X, X2] < 0". Therefore using standard test algorithms adaptive unknown variances, such as Student's (-test, leads to number of queries of the order O(Var(Xi - X2) (og((/8)/e²) = (log((16)). Hence a substantial improvement in the sample complexity can be achieved when leveraging the covariance. We can also go one step further to even reduce the sample complexity in some settings. Indeed, we can establish the sub-optimality of an arm i by comparing it with another sub-optimal arm j faster than when comparing it to the optimal arm i To illustrate consider the following toy example with K = 3: let X1 ~ ~N( 1), X2 = X1 + Y where Y ~ cN(1, 1) and X3 ~ N(i41 + 2c, 1), with X1, Y and X3 independent. X3 is clearly the optimal arm. Eliminating X1 with a comparison with X3 requires (log((1/8) queries, while comparing X, with the sub-optimal arm X2 requires O O(Var(X, X2) log(
(log(1/6)
The aforementioned arguments can be adapted to accommodate bounded variables, such as when comparing correlated Bernoulli variables. These arguments suggest that by utilizing multiple queries per round (as shown in Protocol 1), we can expedite the identification of the best arm compared to the standard serqquurr-ee--ssstee approach. Specifically, for variables bounded by 1, our algorithm ensures that the cost of eliminating a sub-optimal arm i E [4] is given by:
Var(X; (X - X.)
1
min jE[K]: 13>N
(14 - 12) 14
14
The additional term 1/(M, 14) arises due to the sub-exponential tail behavior of the sum of bounded variables. To compare the quantity in (3) with its counterpart in the independent case, it is important to note that the minimum is taken over set that includes the best arm, and that Var(X,- - X,) < 2(V) + Var(X,)). Consequently, when the variables are bounded, the quantity (3) is no larger than numerical constant times (1)) (its independent in 2), with potentially a significant improvements if there is positive correlation between an arm j E [K] with higher mean and arm i (so that Var(X, X,) is small). As result, our algorithm for bounded variables has a sample complexity, up to a logarithmic factor, that corresponds to the sum of quantities (3) over all sub-optimal arms.
counterpart
We expand our analysis to encompass the scenario where arms follow a Gaussian distribution. In this context, our procedure ensures that the cost of eliminating a sub-optimal arm i E [K] is given by:
Var(X, - X1)
min JE[K]:
(P3 - 24
Similar to the setting with bounded variables, the aforementioned quantity is always smaller than its counterpart for independent arms when all variables X, have unit variance.
3

---

In Section 6, we present two lower bound results for the sample complexity of best arm identification in our multiple query setting, specifically when the arms are correlated. Notably. these lower bounds pinpoint how the optimal sample complexity may decrease with the covariance between arms, making them the first of their kind in the context of best arm identification, to the best of our knowledge. The presented lower bounds are sharp, up to logarithmic factor, in the case where all arms are positively correlated with the optimal arm. However, it remains an open question to determine a sharper lower bound applicable to more general class of distributions with arbitrary covariance matrices.
In Section B of the appendix, we introduce a new algorithm that differs from the previous ones by performing comparisons between the candidate arm and convex combination of the remaining arms, rather than pairwise comparisons. We provide theoretical guarantees for the resulting algorithm.
Lastly, we conduct numerical experiments using synthetic data to assess the practical relevance of our approach.
3 Related work
Best arm identification: BAI in the fixed confidence setting was studied by [11], [22], and [12], where the objective to find e-optimal arms under the PAC ("probably approximately correct") model. A summary of various optimal bounds for this problem is presented in [8, 20J. Prior works on fixed confidence BAI [25] and [17] developed strategies adaptive to the unknown variances of the arms. In contrast, our proposed algorithms demonstrate adaptability to all entries of the covariance matrix of the arms. In particular, we establish that in the worst-case scenario, where the arms are independent, our guarantees align with the guarantees provided by these previous approaches.
Covariance in the Multi-Armed Bandits model: Recently, the concept of leveraging arm de- pendencies the multi-armed bandit (MAB) model for best-arm identification was explored in [15]. However, their framework heavily relies on prior knowledge, specifically upper bounds on the conditional expectation of rewards from unobserved arms given the chosen arm's 's reward. In a similar vein, game protocol that allows simultaneous queries was examined in [21]. However, their objective differs from ours as their focus is on identifying the most correlated arms, whereas our primary goal is to identify the arm with the highest mean reward.
The extension of the standard multi-armed bandit setting to multiple- point bandit feedback was also considered in the stochastic combinatorial semi-bandit problem (2, 9, 10 and 13). At each round l 121 1, the learner pulls m out of K arms and receives the sum of the pulled arms rewards. The objective is to minimize the cumulative regret with respect to the best choice of arms subset. [27] proposed an algorithm that adapts to the covariance of the covariates within the same arm. While this line of research shares the intuition of exploiting the covariance structure with our paper, there are essential differences between the two settings, In the combinatorial bandib problem, the learner receives the sum of rewards from all selected arms in each round and aims to minimize cumulative regret, necessitating careful exploration during the game. In contrast, our approach does not impose any constraint on the number of queried arms per round, and our focus is purely on exploration.
Simultaneous queries of multiple arms was also considered in the context of graph- based bandit problems [7). However, in these studies, it is assumed that the distributions of arms are independent.
Model selection racing: Racing algorithms for model selection refers to the problem of selecting the best model out of a finite set efficiently. The main idea consists of early elimination of poorly performing models and concentrating the selection effort on good models. This idea was seemingly first exploited in [23] through Hoeffding Racing. It consists of sequentially constructing a confidence interval for the generalization error of each (non-eliminated) model. Once two intervals become disjoint, the corresponding sub-optimal model is discarded. Later [25] presented an adaptive stopping algorithm using confidence regions derived with empirical Bernstein concentration inequality (3, 24). The resulting algorithm is adaptive to the unknown marginal variances of the models. Similarly, [4] presented a procedure centered around sequential hypothesis testing to make decisions between two possibilities. In their setup, they assume independent samples and use Bernstein concentra- tion inequality tailored for bounded variables to adapt to the variances of the two variables under consideration.
While the idea of exploiting the possible dependence between models was shown [6, 26] to empirically outperform methods based on individual performance monitoring, there is an apparent lack of theoretical guarantees. This work aims to develop a control on the number of sufficient queries for

---

reliable best arm identification, while being adaptive to the unknown correlation of the candidate arms.
4 Algorithm and main theorem for bounded variables
In this section, we focus on the scenario where the arms are bounded by 1. Let us establish the notation will be using throughout. For each arm E [K]] associated with the reward variable X;, we denote by (4; the mean of X, Additionally, for any pair of arms i. E [K]. we denote Viz as the variance of the difference between X; and X,. i.e. Vi= = Var(X; Xz). We remind the reader that the quantities Vig are unknown to the learner.
Algorithm/ 2 is developed based on the ideas introduced in Section 2, which involves conducting
sequential tests between every pair (i,j) E [K] x [K] of arms. The key element to adapt to the covariance between arms is the utilization of the empirical Bernstein's 's inequality [24] for the sequence of differences (X,,t - Xg,a)e he for i.J E [K]] To that end, we introduce the following quantity:
3 (1, = u3 - Pr.. 2 (l. 8) 2V 9 (1,
where, As.. represents the empirical mean of the samples obtained from arm i up to round i, and Vis,e denotes the empirical variance associated with the difference variable (X; Xx) up to round t. The
term att, 6) is defined as a(t, 8) :- /log(1/6))/(C 1), and 6, is given by 6/(2K
1)).
By leveraging the empirical Bernstein's s inequality (restated Theorem K. I), we can establish that Â. (t, 6) > 0 at any time t. then with a probability of at least - 6, we have H4, < 14- This observation indicates that arm is sub-optimal. Furthermore, when j4j b4 for i, E [K]. sufficient sample sizes ensuring that the quantity (t, 6) is positive is proportional to:
Aij = (
Vy (44 12)
1
log (ny
m.)5): (mz-
(4)
(1)))
Py-
Moreover, we show in Lemma E.5 in the appendix that the last quantity is necessary, up to smaller numerical constant factor, in order to have (t,(t, 8) > O.
Algorithm 2 follows a successive elimination approach based on the tests (t, > O. Our objective to ensure that any sub-optimal arm i is queried most min, Aij times, where the minimum is taken over arms with means larger than (4g However, this approach poses challenge: the arm j' that achieves the minimum of A, may be eliminated early in the process, and the algorithm is then constrained to compare arm i with other arms costing larger complexity Aij. To address this limitation, is useful to continue querying arms even after deciding their sub-optimality through the pairwise tests.
In Algorithm 2, we introduce be optimal, initialized as S1 = [K]] and C., which represents the set of arms queried at round t. Naturally, C, contains S, and also includes arms that were freshly eliminated from S,, as hope that these arms will help in further eliminating candidate arms from S, more quickly.
at round t: S,, which contains arms that are candidates to
An important consideration is how long the algorithm should continue sampling an arm that has been eliminated from S, Theorem E.2, we prove that when arm j is eliminated at round t, it is sufficient to keep sampling it up to round 82t (the constant 82 is discussed in Remark 1). The rationale behind this number of additional queries is explained in the sketch of the proof of Theorem 4. It suggests after round 821, then the arm that eliminated, from St
that if arm fails to eliminate another can ensure faster eliminations for the remaining arms in St-
Theorem 4.1. Suppose Assumption I and -B holds. Consider Algorithm 2, with input E (0. 1). We have with probability at least - ö: the algorithm identifies the best arm and the total number of queries N satisfies:
N S clog(KA8
Σ
min JELK]
Vij [14 11,)2
1 14j
(5)
p4
where A max minze[R]:
Vy
Pp- f and is numerical constant.
((--1)) 12
15244
5

---

Algorithm 2 Pairwise-BAl
1: Input
2: Initialization:
3:
Query all arms for 2 rounds and compute the empirical means vector fa,, 1 4- 3.
4:
St [K]] C+ []]
S*tt candidate arms*/
5:
r*Set of queried arms*/
6: while |8| do
7:
Jointly query all arms in C.
8:
Update fú, and compute maxjec (i) for each i E S.
9:
for E S do
10:
if maxjec (1,(1,) 6) > 0 then
11:
Eliminate from S 5 5 {i}.
j is sub-optimal */
12:
Mark i for elimination from C at round: 82 t. 13: end
14: end for
15:
Increment t.
16: end while
17:
Return S.
Moreover, if we omit line 12 from Algorithm 2, that is we do not query non-candidate arms, we have with probability at least 8: the algorithm identifies the best arm and the total number of queries N satisfies:
Vi- (H.-
S clog((888
Σ REA
us) ui)²
ps Mi
where A is defined above and e is a numerical constant.
Summary the proof for bound (5): Let denote a sub-optimal arm and T. := Arg Miny Agy First, we show that at round I, i E S, then necessarily we have n, C, +f 0. We proceed by contradiction argument: assume T; C, 0, let denote the element of Y. with the largest mean. Let & denote the arm that eliminated, j from S at round 8 < L. Lemma E.3 shows that, since Á 6) > O, we necessarily have log(1/6)A,x/44 S s. Morcover, j was kept up to round 82s and in this last round we had Â. (82s, 8) < 0, which gives by Lemma E.3: 82s S 2) (gg(1/62e)) Asy. Combining the two bounds on s, gives: Aya Aij. Finally, we use the ultra-metric property satisfied by the quantities Aue (Lemma E.6), stating that: As S max(AAj Ayx Combining the last inequality with the latter, we get Au I Aij. which means that k E Y, The contradiction arises from the fact that j is the element of the largest mean in Y; and arm eliminated, j (hence 14 > {tz). We conclude that necessarily Y, C. o 0. therefore by Lemma E.3, at round of the order of miny Aij- we will necessarily have (i, 8) > O for some j E C..
Remark From a practical standpoint, to keep sampling an arm eliminated at t for additional 81 t rounds is conservative approach. The stated value of 81 is determined by specifics the proof. but we believe that it can be optimized to a smaller constant based on the insights gained from from numerical simulations. Furthermore, even we omit the oversampling step, presented in Theorem 4. I,, the algorithum is still guaranteed to identify the best arm with probability 1 55 Only the query complexity guarantee is weaker, but the algorithm may still lead to effective arm elimination, although with potentially slightly slower convergence.
Remark 2. The idea of successive elimination based on evaluating the differences between variables was previously introduced in [28], in the context of model selection aggregation. Their analysis allows having a bound slightly looser than bound (6) (with the distances between variables instead of variances). On the other hand, Theorem 4.1 in our paper provides sharper bound in (5).
First, it is important to note that bound (5) is always sharper (up to a numerical constant factor) than bound (6) because the optimal arm is included the set over which the minimum in bound (5) is taken. On the other hand, bound (5) can be smaller than bound (6) by factor of 1/K. This situation can arise scenarios where the - sub-optimal arms, which have close means, are highly correlated, while the optimal arm is independent of the rest. In such situation, the terms in

---

the sum in (5) corresponding to the correlated sub-optimal arms are relatively small, except for the arm (denoted 1) with the largest mean among the K 1 correlated suboptimal rewards. That last remaining arm will be eliminated by the optimal arm, incurring a potentially large cost, but for that arm only. On the other hand, each term in the second bound (6) would be of the order of the last cost.
To provide perspective on our guarantees compared to those developed in the independent one query per round setting, it is worth noting that the standard guarantees in that setting provide sample complexity corresponding to Lizs 1og(1/5)/(4a) pz)²². Since variables are bounded by 1, their variances are bounded by 1. Therefore, in the worst case, we recover the previous guarantees with a numerical constant factor of 2.
refined adaptive algorithm presented in [25] also utilizes a successive elimination approach using confidence intervals for the arm means based on the empirical Bernstein's 's inequality. However, unlike our algorithm, they use the concentration inequality to evaluate each arm's 's mean independently of the other arms. Their approach allows for adaptability to individual arm variances, and is particularly beneficial are small, i.e., Var(X,) << 1. The sample complexity of their algorithm is of the order of:
Var(X,) + Var(X;))
Σ EF
(1i- ((x )2
where r := maxi (Var(X,, + Var(X.-) //4,)- - ). Neglecting numerical constant factors, the last bound larger than both our bounds (5) and (6). This is because the variance of the differences can be bounded as follows: Vi+- < 2(Var(X;, + Var(X..)).
5 Algorithms and main theorem for Gaussian distributions
In this section, address the scenario where arms assumed to follow Gaussian distribution. We consider a setting where the learner has no prior knowledge about the arms' distribution parameters, and we continue using the notation introduced in the previous section. The main difference between this case and the bounded variables setting, other than the form of the sample complexity obtained, is the behavior of the algorithm when variances of differences between variables tend to 0, displayed by the second bound in Theorem 5.1.
Our algorithm relies on the empirical Bernstein inequality, which was originally designed in the literature for bounded variables [3, 24). We have extended this inequality to accommodate Gaussian variables by leveraging existing Gaussian concentration results. Note that extending such inequalities more generally for sub-Gaussian variables a non-trive non-trivial task. One possible direction is to suppose that arms follow sub-Gaussian distribution and satisfy Bernstein moment assumption (such extensions were pointed by works on bounded variables c.g., ? ). Given the last class of distributions, build on the standard Bernstein inequality with known variance, then plug in an estimate of the empirical variance leveraging the concentration of quadratic forms (see 5). However, remains uncertain whether extension for nub-Gaussian variables (without additional assumptions) is practically feasible.
We extend the previous algorithm to the Gaussian case by performing sequential tests between pairs of arms (i.j) E [K]. We establish a confidence bound for the difference variables (X, - X,) (Lemma D.1 in the appendix) and introduce the following quantity:
(t,(t,) = Pg.e- Pa. 2
_a 8) 2f(a(tt Vigae
where the f is defined by: f(x) = exp(2x + 1) if 2 1/3, and f(x) = 1/(1 22x) otherwise.
Using the empirical confidence bounds on the differences between arms, we apply the same procedure as in the case of bounded variables. We make one modification to Algorithm 2: we use the quantities (t, 6) instead of Å., (t, 6).
By following the same analysis in the bounded setting, establish that the sample complexity ViJ
required for the comparison tests between arms i and j is characterized by the quantity (p:-ny)² 1. The following theorem provides guarantees on the algorithm presented above:
Theorem 5.1. Suppose Assumptions and -G holds. Consider the algorithm described above, with input 8 E (0, 1). We have with probability at least 1 - ö; the algorithm identifies the best arm
7

---

and the total number of queries N satisfies:
N S clog(KAö
E
min jE[K]
Vis (p= pg)2
v
(8)
(E(
where A = [ mi]je[K]: 11214
Vi (1s-1ー}²² V v1] and is numerical constant.
Moreover, if we omit line 12 from Algorithm 2, that we do not query non-candidate arms, we have with probability at least 1 ô: the algorithm identifies the best arm and the total number of queries N satisfies:
KO-1 log(1 + 1/A)
E
N & 3K + clog
(9)
(E[KTTe) log (1+ [a: m.)
where A = maxifi Vis/(us- p4) is defined above and e is a numerical constant.
Remarks. On the sample complexity cost of being adaptive to the variance: If the sample size larger than log(1/5), the cost of plugging in the empirical variance estimate into the Cher- noff's concentration inequality is only a multiplicative constant slightly larger than one (nearly 1 + 2//ogg(188//)) However, in the case of a small sample regime (n < (loo(1/6)) the cost is a multiplicative factor of expí / Vlogoooo (ogg(/6)// //))/// / due to the nature of the left tail of the chi-squared distribution (see Sections and K of the appendix for detailed calculations). For most natural regimes, the number of queries made for each arm is larger than log(1/8), hence the last described effect does not arise. However, in some specific regimes (such as the case of very small variances of the arms) optimal algorithm should query less than log(1/8) samples, which necessitates introducing the exponential multiplicative term above into the concentration upper bound. This translates into different form of guarantee presented in Theorem 5.1, inequality (9). It is important to note the cost in this regime cannot be avoided as highlighted by our lower bound presented in Theorem 6.2.
Theorem 5.1 above shows that Algorithm 2 is applied to Gaussian distribution guarantees that each sub-optimal arm i is eliminated after roughly min, / m4y) queries. Bounds (8) and (9) derived from our algorithm are smaller than the standard complexity bound in the independent case, which is given by ii /²/ /(1; - (4,)) when all arms have variances smaller than x², It is important note that unlike most existing procedures in the literature that achieve the standard complexity bound, our algorithm does not require knowledge of the parameter o².
About the upper bound (9): This bound can be further bounded by log(ó ' Eies' (m:-A,,) V The form presented in Theorem 5.1 is particularly sharp when the variances Vu- tend to zero, resulting in a constant upper bound. Recently, in the independent setting where variances are unknown, [17] analyzed the comparison of two arms i and j. They derived a complexity of the order 1/ log [ (14 p.)²
V::-
where of and o3 are the variances of arms and respectively. This result is reflected in our bound (9), where instead of the sum of variances, our bound considers the variance of the difference, leading to a sharper bound. In Section 6, we provide lower bound that nearly matches (9).
(a?+
Lower bounds
In this section, we present lower bounds for the problem of best arm identification with multiple queries per round, following Protocol 1. We provide lower bounds for both the bounded distributions setting (Theorem 1. and the Gaussian distributions setting (Theorem 6.2). It is important note that our lower bounds are derived considering class of correlated arm distributions. Therefore, the results obtained in the standard
-eruuerr-----ruuddd setting [20] do not hold in our setting.
Our first lower bound is derived for the case where arms follow a Bernoulli distribution. Let μ (p4)se|K] be a sequence of means in [1/4, 3/4], denote by i" the index of the largest mean. Consider a sequence of positive numbers V (Vi- ]ie[ We define Bx (p, V) the set of Bernoulii arm distributions such that: (i) [[ μ45 (ii) Var(X, X,+) < Va- for all [K].
8

---

For Bernoulli distributions, the variances and means are linked. Specifically, Lemma K.8 demonstrates
that for any pair of Bernoulli random variables (B,, B₂) with means (b), b2). the following inequality
holds: (b) b2) (b1 bz)² S Var B] B2) S min (b) + b2); bj + b2) - (b) 12)²
We assume that the sequences V and la satisfy the aforementioned condition for (X,, X²- ]{[[K]- as otherwise the class Bx (μ, V) would be an empty set. Theorem 6.1 provides lower bound on the sample complexity required for best arm identification in the worst-case scenario over the class B& (1. V).
Theorem 6.1. Let K 2 2 and ò E (0,1), 1). For any d-sound algorithm, we have
Vi:
max (,
[ 2 log(1/46) (E[K]\(*
Σ
max
(mu - pa)2² pe p4
where N is the total number of queries.
The presented lower bound takes into account the correlation between arms by incorporating the quantities Vi+. as upper bounds for the variances of the differences between arm and the optimal arm 8 This lower bound indicates that for class Bx (H,, V). Algorithm 2 is nearly optimal.
Next, we provide lower bound the Gaussian case. Let μ4 = (Ju) (es)) be a sequence of means, where 8" denotes the index of the largest mean. We also consider a sequence of positive numbers V = =(v-- )=tk] We define Gx (ju, V) as the set of Gaussian arm distributions satisfying the following conditions: (i) [[X 14: (ii) Var(X, - x,,) = V and (iii) Var(X; 2 for all i E [K]] Theorem 6.2 provides a lower bound on the sample complexity required for best arm
identification in the worst-case scenario over the class Gx (H. V).
Theorem 6.2. Let K 2 2 and ó E (0, 1). For any d-sound algorithm, have
Eg [N] 2 (og(1/)0)
Σ
max GEG
&EIKT(E>) log
1
(mi ( V2a
where N is the total number of queries.
Theorem 6.2 demonstrates that our algorithm achieves near-optimal performance over CK(H, V). up to logarithmic factor.
7 Numerical simulations
We consider the Gaussian rewards scenario. We compare our algorithm Pairwise- BAI (Algorithm 2) to 3 benchmark algorithms: Hoeffding race [23], adapted to the Gaussian setting (consisting of successive elimination based on Chernoff's s bounds) and LUCB [19], which is an instantiation of the upper confidence bound (UCB) method. We assume that the last two algorithms have prior knowledge the variances of the arms. The third benchmark algorithm consists of using a successive climination approach using the empirical estimates of the variances. We evaluated two variations of our algorithm. The first one, Pairwise-BALl
implemented Algorithm 2 for Gaussian variables. In this instance, we modified line 12 by continuing to sample sub-optimal arms that were eliminated at round t until round 2t instead of 82t. We stress that both variants guarantee 8-sound decision on the optimal arm (see Theorem 5.1). The second instance involved removing the last instruction, meaning we directly stopped querying sub-optimal arms. Figure 1 displays the average sample complexities for each considered algorithm. As expected, the larger the correlation between arms, the better Pairwise-BAl performs.
The second experiment aims to demonstrate that Algorithm adapts to the covariance between sub- optimal arms, as indicated by bound (8) in Theorem 4.1 rrather than solely adapting to the correlation with the optimal arm as shown by (9). In this experiment, we consider that the arms are organized into clusters, where each pair of arms within the same cluster exhibits a high correlation (close to 1), while arms from different clusters are independent. According to bound (8) (see also discussion after Theorem 4.1) expect observe a gain of up factor corresponding cluster compared to algorithms that do not consider covariance. (Since the total number of arms is kept fixed, the number of arms per cluster scales as the inverse of the number of clusters.)
the number of arms per
Figure illustrates the results, showing that the performance of Pairwise-BAr improves as the number of clusters decreases (indicating larger number of correlated arms). This suggests that increasing

---

Sample complexity for BAI
Sample complexity for BAI
Hoefleling
Hoeffeling
00000
50000
Furindaa
Parivsse
100000
Ferwiree
of q,00na
600000
40000
20000
20000
P-0.5 p-C7 p-0.9
fumber custers
Figure 1: Left figure: the average sample complexities, in 4 scenarios with K arms with means
H4 = i/10. The covariance matrix C' is defined as follows: for E [K]. Ci = 1 and for i * j: Cj p. We consider scenarios with the correlation: P E {0, 0.5, 0.7. 0.9). Right figure: the average sample complexities with K = 16 arms with means (4; = i/10. Arms in the same cluster have a correlation of 0.99, and arms from different clusters are independent. We consider 4 scenarios with different number of clusters: Viel E (8, 4, 2, }.. All clusters are of the same size.
the number of correlated sub-optimal arms, which are independent from the optimal arm, still leads significant performance improvement. These findings support the idea that Pairwise-BAl and Bairwise-BALe exhibit behavior that aligns more closely with bound (8) in Theorem 4.1, rather than bound (9).
In both experiments, we observe that Pairwise-Ban 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. While this modification provides better theoretical guarantees, it may not lead to empirical performance improvements in general scenarios.
Conclusion and future directions
This work gives rise several open questions. Firstly, the presented lower bounds take into account partially the covariance between arms. It would be interesting to explore the development of a more precise lower bound that can adapt to any covariance matrix of the arms. Additionally, in terms of the upper bound guarantees, our focus has been on pairwise comparisons, along with an algorithm that compares candidate arms with convex combinations of the remaining arms (Section B). An interesting direction for further research would involve extending this analysis to an intermediate setting, involving comparisons with sparse combinations.
This work is supported by ANR-21-CE23-002 (ASCAI) and ANR-19- CHIA-0021-4 (BISCOTTE). This work was conducted while EM Saad was INRAE Montpellier.
Acknowledgements:
10

---

References
[1] Jean-Yve Audibert and Sébastien Bubeck. Best arm identification multi- nulti-armed bandits. In Conference Learning Theory, 2010.
[2] Jean- Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial optimization. Mathematiccs of Operations Research, 39(1):31-45, 2014.
[3] Jvan-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In International conference algorithmic learning theory, pages 150-165. Springer, 2007.
[4] Akshay Balsubramani and Aaditya Ramdas. Sequential nonparametric testing with the law of the iterated logarithm. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, pages 42-51, 2016.
[5] Pierre C Bellec. Concentration quadratic forms under a Bernstein moment assumption. arXiv preprint arXiv: /0101990900777 2019.
[6] Mauro Birattari, Zhi Yuan, Prasanna Balaprakash, and Thomas Stützle. F-race and iterated F-race: An overview. Experimental methods for the analysis of optimization algorithms, pages 311-336, 2010.
[7] Stephane Caron, Branislav Kveton, Mare Lelarge, and Bhagat. Leveraging side observations in stochastic bandits. In UAI, 2012.
[8] Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference Learning Theory, pages 590-604. PMLR, 2016.
[9] Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1404-1422,, 2012.
[10] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages 151-159. PMLR, 2013.
[11] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory, pages 255-270. Springer, 2002.
[12] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[13] Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armes bandits with linear rewards and individual observations. JEEE/ACM Transactions on Networking. 2066): 1478, 2012.
[14] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 1027. PMLR, 2016.
[15] Samarth Gupta, Gauri Joshi, and Osman Yağan. Best-arm identification in correlated multi- armed bandits. IEEE Journal on Selected Areas in Information Theory, 2(2):549-563, 2021.
[16] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. Lil'uch An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439. PMLR, 2014.
[17] Mare Jourdan, Rémy Degenne, and Emilie Kaufmann. Dealing with unknown variances in best-arm identification. In International Conference on Algorithmic Learning Theory, pages 776-849. PMLR, 2023.
[18] Brennan Kahan and Tim Morris. Improper analysis of trials randomised using stratified blocks or minimisation. Statistics in medicine, 31(4):328-344 2012.
11

---

[19] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC subset selection stochastic multi-armed bandits. ICML, volume 12, pages 655-662 2012.
[20] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42) 42, 2016.
[21] Che- Yu Liu and Sébastien Bubeck. Most correlated arms identification. In Conference on Learning Theory, pages 623 637. PMLR, 2014.
[22] Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):63-648, 2004.
[23] Oded Maron and Andrew Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. Advances neural information processing systems, 6, 1993.
[24] Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample- cample-variance penalization. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
[25] Volodymyr Mnih, Csaba Szepesvári, and Yves Audibert. Empirical Bernstein stopping. In Proceedings of the 25th international conference on Machine learning, pages 672-679, 2008.
[26] Andrew W Moore and Mary S Lee. Efficient algorithms for minimizing cross validation error. In Machine Learning Proceedings 1994, pages 190-198. Elsevier, 1994.
[27] Pierre Perrault, Michal Valko, and Vianney Perchet. Covariance-adaptioo algorithm for semi- bandits with application to sparse outcomes. In Conference on Learning Theory, pages 3152- 3184. PMLR, 2020.
[28] El Mchdi Saad and Gilles Blanchard. Fast rates for prediction with limited expert advice. Advances in Neural Information Processing Systems, 34, 2021.
[29] Alexandre Tsybakov. Optimal rates of aggregation. In Learning theory and kernel machines, pages 303-313. Springer, 2003.
[30] Nicolas Verzelen. Minimax risks for sparse regressions: Ultra-high dimensional phenomenons. Electronic Journal of Statistics, 6:38 90, 2012.
[31] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
12


Reviews:
[{"review_id": "sLq1C2lGEO", "reviewer": "Reviewer_THM3", "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.", "questions": "- In line 81, what does $\\epsilon\\mathcal{N}(1, 1)$ denote?\n- 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). \n- 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.\n- 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.\n- 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?\n- 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.\n- 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.\n- 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?\n\nBalsubramani and Ramdas, Sequential nonparametric testing with the law of the iterated logarithm, UAI 2016.   \nKato and Ariu, The Role of Contextual Information in Best Arm Identification, 2021.", "limitations": "None.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n* **On Question 1**: The notation $\\epsilon \\mathcal{N}(1,1)$ stands for $\\epsilon X$, where $X \\sim \\mathcal{N}(1,1)$.  We can write $\\mathcal{N}(\\epsilon,\\epsilon^2)$ if it appears clearer, though we wanted to emphasize $\\epsilon$ as a scaling factor.\n* **On Questions 2 and 3**: We absolutely agree that there are indeed many existing approaches based on arm elimination, which are all akin to performing sequential tests. What we want to emphasize here is that with 2 simultaneous queries, conceptually we can use a _paired samples_ $t$-test which is not possible in standard BAI. As noted by the reviewer, this allows for variance reduction. The work by Balsubramanu and Ramdas (2016) focuses on sequential hypothesis testing to make decisions between two possibilities. In their setup, they assume independent samples and utilize the empirical Bernstein concentration inequality tailored for bounded variables to adapt to the variances of the two variables under consideration. Similar adaptive approaches have been explored in other studies, and achieving adaptivity to arm variances is not a novel concept, as highlighted in our related work discussion. However, our main contribution lies in addressing the multiple arms case with arbitrary dependence. In this scenario, as explained in the introductory discussion (lines 78-99), certain intuitions from the standard setting no longer hold. For instance, it is possible that a sub-optimal arm may be eliminated by another sub-optimal arm more rapidly than by the optimal arm, which presents new challenges when dealing with multiple arms. Our approach is designed to tackle this situation and provide a solution in such settings. We will add a discussion in the related work section on Balsubramanu and Ramdas (2016) highlighting the common points of our procedure to theirs.\n* **On Question 4 (part 1)**: The 2-armed bandits case discussed in lines 78-99 serves as an illustrative example and does not represent a stand-alone contribution. Our primary objective is to address the more general $K$-armed bandit case. It is crucial to note that in the standard Best Arm Identification (BAI) setting, only one query per round is allowed. Therefore, the reduction involving comparing the difference arm \"$X_1-X_2$\" and $0$ is not feasible, as the learner lacks access to samples of the variable $Y_t = X_{1,t}-X_{2,t}$ directly. Instead, the learner has access to samples from $Y' \\sim X_{1,t}-X_{2,s}$, where $s\\neq t$ (resulting in $X_{1,t}$ and $X_{2,s}$ being independent). In this context, it is important to observe that $\\text{Var}(Y') = \\text{Var}(X_{1,t}-X_{2,s}) = \\text{Var}(X_1) + \\text{Var}(X_2)$, which can be much larger than $\\text{Var}(Y) = \\text{Var}(X_{1,t}-X_{2,t}) = \\text{Var}(X_1-X_2)$. Achieving adaptivity to the latter variance is only possible with two queries per round, which is a crucial component for our results in addition to treating two arms as one in the 2-armed setting. In summary, being adaptive to the last variance is only possible with two queries per round, which is an important ingredient for our results besides treating two arms as one in the 2 armed setting.\n* **On Question 4 (part 2)**: Concerning the lower bound in the 2-arm setting: we are uncertain what the reviewer means with the 'one-arm bandit problem'. At any rate, reducing the (full) observation of the two arms $(X_1,X_2)$ to that of $(X_1-X_2, 0)$ results in a loss of information. Thus, a lower bound for the latter reduced setting does not (at least not without additional arguments) logically entail a lower bound for the initial setting. This is, however, somewhat beside the point we want to make, which is that\n if we adhere to the standard BAI setting with one query per round, Kaufmann's lower bound is applicable and yields a sample complexity of $\\mathcal{O}(\\log(1/\\delta)/\\epsilon^2)$. However, it is essential to note that this lower bound does not extend to the multiple query case. In our work, we have presented a new lower bound specifically addressing the multiple query scenario in the $K$-armed bandits setting (Section 6).\n* **On Question 5: Bandits on graphs**: Previous studies on graph-based bandit problems with side observations in the stochastic setting (such as Caron et al., 2012) also explore the potential of simultaneously observing rewards from multiple arms. However, in these investigations, it is assumed that the distributions of arms are independent. We are not aware of any existing research on bandit problems in graph-based scenarios where the learner successfully attains adaptability to covariance among arms. \n* **On Question 8**: The study by Kato and Ariu (2021) examines the scenario where arms are correlated through contextual information. The primary distinction between their setting and ours lies in how the dependency between arms is accessed. In their work, the dependency between arms is accessible only through the context variable $X$, whereas in our approach, we directly obtain samples of the correlations between candidate's arms by jointly querying two arms. Additionally, another notable difference is in the context samples $X_t$ received at each round $t$. In their work, these context samples are independent of the arms chosen. However, in our case, the \"observed dependency\" between candidate arms is directly related to the specific arms queried in each round, allowing us to have direct access to correlations among the queried arms.\n\nCaron, Stéphane, Branislav Kveton, Marc Lelarge, and Smriti Bhagat. “Leveraging side\nobservations in stochastic bandits.” UAI 2012.\n"}, {"review_id": "xpczrV9Nem", "reviewer": "Reviewer_ZvwR", "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. ", "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). \n2. If the assumption of arm independence holds, can we still use the proposed algorithms? Would there be a trade-off between complexity and generalization?\n3. Could you provide a concrete example of the failure case mentioned in line 183? And how probably will this kind of failure happen?", "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. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n* **About the reviewer's summary and Question 1:** Please note that our objective in this paper is not identifying $\\epsilon$-optimal arms (also known as $(\\epsilon,\\delta)$-PAC setting) but identifying the (exact) best arm with probability at least $1-\\delta$.\n* **About the first point raised in the weaknesses section:** It is unclear to us what the reviewer suggests by \"it can only solve the same covariance between all arms (correct me if I were wrong)\". We would like to emphasize that we make no structural assumptions on the covariance between arms and our guarantees hold for any arbitrary covariance matrix of the joint distribution of the arms variables. In the bounded case, of course, the possible covariance matrix is implicitly constrained by the boundedness assumption.\n* **About Question 2:** In case the arms are independent our guarantees recover the standard known sample complexity up to a constant factor. However, whenever the arms variables have a strong correlation, our guarantees show that a significant improvement is made.\n* **About Question 3:** The failure case mentioned in line 183 may occur in some very specific scenarios. To illustrate consider the following toy example with $3$ arms: $X_1 \\sim \\mathcal{N}(\\epsilon+\\epsilon^{3/2},1)$, $X_2 = X_1-Z_2$ where $Z_2 \\sim \\mathcal{N}(\\epsilon, \\epsilon)$ and $X_3 = X_2-Z_3$ where $Z_3\\sim  \\mathcal{N}(\\epsilon^{3/2}, (\\epsilon/\\kappa)^2)$, $\\kappa>1$ is a constant to be specified and $X_1, Z_2$ and $Z_3$ are independent. Denote $\\Lambda_{ij} = \\frac{\\text{Var}(X_i-X_j)}{\\mathbb{E}[X_i-X_j]^2}$. Hence, in the previous example: $\\Lambda_{12} = 1/\\epsilon$, $\\Lambda_{23} = 1/(\\kappa^2\\epsilon)$ and $\\Lambda_{13} = (\\epsilon+(\\epsilon/\\kappa)^2)/(\\epsilon+\\epsilon^{3/2})^2$. For $\\epsilon$ very small we have $\\Lambda_{12}, \\Lambda_{13} \\sim 1/\\epsilon$ and $\\Lambda_{23} \\sim 1/(\\kappa^2 \\epsilon)$. Observe that the stopping time for comparing arms $i$ and $j$ (based on the test we considered) is a random variable $\\tau$. We showed (Lemma E.4) that with high probability it belongs to the interval $[c_{\\inf}\\log(1/\\delta_{\\tau}) \\Lambda_{ij}, c_{\\sup}\\log(1/\\delta_{\\tau})\\Lambda_{ij}]$ (where $c_{\\inf}<c_{\\sup}$ are numerical constants). Therefore, in this example, arm $2$ eliminates arm $3$ faster than arm $1$. However, we may have that arm $1$ eliminates arm $2$ first at round $\\sim c_{\\inf} \\Lambda_{12}$ (this can happen if we choose $\\kappa^2 < c_{\\sup}/c_{\\inf}$), then we need to compare arm $1$ with arm $3$ paying a cost higher in average than the cost of comparing arms $2$ and $3$."}, {"review_id": "dd1OGQ1Rro", "reviewer": "Reviewer_19g5", "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.", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe considered problem is interesting and well-motivated.\n2.\tThe theoretical analysis looks sound. Both upper and lower bounds are provided.\n", "weaknesses": "1.\tWhat 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.\n2.\tCould you compare Theorems 4.1 and 5.1with the results of existing covariance-adaptive bandit works?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n* **On Question 1 (part 1):** Comparison of Theorems 4.1 and 5.1: Theorem 4.1 deals with bounded variables. Here, the sum of bounded variables may exhibit a sub-exponential tail, which leads to the additional $1/(\\mu_i-\\mu_j)$ term in the complexity of comparing two variables. This additional term does not appear for Gaussian variables in Theorem 5.1. Hence the guarantees for the two classes of variables are different.\n* **On Question 1 (part 2):** Recall that we provided an additional guarantee (that was proved specifically for Gaussian variables) in Theorem 5.1 inequality (8), which is sharper than inequality (7) in the regime where variances are very small.\n* **On Question 1 (part 3):** Regarding the extension to sub-Gaussian variables, we would like to clarify that our algorithm relies on the empirical Bernstein inequality, which was originally designed in the literature for bounded variables. However, we have extended this inequality to accommodate Gaussian variables by leveraging existing concentration results. As noted previously, the result in this setting has a somewhat neater form, since it eschews the additional sub-exponential term. It is essential to note that developing such inequalities for sub-Gaussian variables is generally a non-trivial task. One possible direction to extend the considered class of distributions is to suppose that arms follow a sub-Gaussian distribution and satisfy a Bernstein moment assumption (such extensions were pointed out by works on bounded variables e.g., Balsubramani and Ramdas 2016). Given the last class of function, we can build on the standard Bernstein inequality with known variance, then plug in an estimate of the empirical variance leveraging the concentration of quadratic forms --see Bellec (2019). However, it remains uncertain whether an extension for sub-Gaussian variables (without additional assumptions) is practically feasible.\n* **On Question 2 (part 1):** about comparison with existing covariance-adaptive bandits works. While covariance-adaptive approaches have been explored in the context of combinatorial semi-bandits, it is important to note that the setting and objectives of this class of problems differ from ours. In our setting (Protocol 1), the learner has the flexibility to query any subset of arms, and the ultimate goal is to identify the single best arm. On the other hand, in combinatorial semi-bandits, the learner selects a subset from a predetermined set of subsets $\\mathcal{M} = \\left\\lbrace M_1, \\dots, M_d \\right\\rbrace$ at each round $t$, where $M_i \\subset \\[K\\]$ and $\\lVert M_i \\rVert_1=m$ for a specific problem parameter $m$. However, the objective in the latter case is not to identify the best arm individually but rather to find the subset $M_i$ with the largest sum of rewards. Given these differences, we refrained from comparing the guarantees obtained in our work with those of combinatorial semi-bandits. The dissimilarities in problem structures and primary objectives lead us to believe that such a comparison would not be meaningful.\n* **On Question 2 (part 2):** As mentioned in the related work section, various works in the literature have focused on developing strategies that adapt to the variances of the arms. In contrast, our guarantees go beyond being solely adaptive to arm variances; they also incorporate adaptivity to the covariances between different arms\nIn lines 242-248, we have provided a comparison of these two types of guarantees. Specifically, when arms are independent, our guarantees exhibit adaptivity to variances, though with a numerical factor of $2$. However, when arms are correlated, the improvement achievable with our procedure can be an arbitrary factor, favoring our approach.\n\nBalsubramani and Ramdas, Sequential nonparametric testing with the law of the iterated logarithm, UAI 2016.\n\t\nP. C. Bellec. Concentration of quadratic forms under a Bernstein moment assumption. arXiv preprint 2019."}, {"review_id": "TvmpiN6iS8", "reviewer": "Reviewer_pLAq", "summary": "Authors investigate the stochastic Best Arm Identification (BAI) problem when the arms have an unknown correlation structure.\nIn contrast, the majority of BAI literature focuses on independent arms with unknown variances.\nAuthors propose algorithms for BAI in two settings (bounded random variables and gaussian random variables) and analyze the sample complexity of these algorithms.\nIn order to leverage the correlation structure, multiple arms are allowed to be sampled at each round.\nThey 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).\nSimulations are run to demonstrate the method on a synthetic dataset.", "questions": "I think this paper makes some interesting and strong contributions.\nUnfortunately, 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\".\nHowever, 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.\n\n1. 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.\n2. 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?\n3. Can Assumption 3 be relaxed to subgaussian? If the answer is no, then why not?\n4. 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?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main strength of the paper is an investigation into the stochastic BAI problem where independence between the arms is not assumed.\nAuthors develop algorithms where the covariance structure is estimated and used to help quickly eliminate suboptimal arms.\nOf course, multiple arms must be sampled simultaneously in order to estimate the covariance between them.\nOn 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.\nOn 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).\nThis 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.\n\nThe 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.\nIt 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).\nThis overhead cost may not be very large, but I am pretty certain that it should exist.\nA 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.\nIn 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\".\nOverall, 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.\n\nThe second weakness of the paper is that the exact nature of the guarantees on the sample complexity are not so clear.\nFrom 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.\nThe goal of the algorithm designer is that, under appropriate conditions, $N$ is small in some sense, as a random variable.\nSo 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)?\nDoes this mean that $N$ is order $XYZ$ in probability? \nOr is $N$ not a random variable?\nPerhaps there is some convention in the BAI literature so that this is very clear; but to someone in adjcent fields, this could use clarification.\nI'm hopeful that this can be clarified and the fix is relatively easy.\n\nFurther comments on clarity and discussion of results are given below.\n\n### Minor Comments\n\n1. (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.\n2. (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 ?\n3. (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.\n4. (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.\n5. (Line 140, 157) citations appear in parathensis when other citations appear in brackets. A consistent stlye should be used throughout the paper.\n6. (Line 142) \"The objective is to maximize the cumulative regret...\" is this a typo, i.e. \"maximize\" should be \"minimize\"?\n7. (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?\n8. (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.\n9. (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.\n10. (Line 275): the reference (20) is perhaps misplaced.\n11. (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.\n12. (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?\n13. (Line 319): \"Theorem 6.2 demonstrates that our algorithm achieves near-optimal performance...up to a logarithmic factor\". Same as above.\n14. (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.\n15. (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.\n16. (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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n* **On Question 1:** about the formulation of our results. We apologise for not being clear. Please note that such presentation of the guarantees is standard in the literature of best arm identification with fixed confidence, see for instance: Karnin et al. (2013) and Jamieson et al. (2014). Allow us to clarify that the total number of queries, $N$, is a random variable depending on the learner's strategy and the observed samples. The guarantees we present in Theorems 4.1 and 5.1 take the form of an upper bound on the variable $N$, which holds with a probability of at least $1-\\delta$. The statement of these theorems says that with probability at least $1-\\delta$: [the algorithm finds the best arm --and-- the total number of queries satisfies $N\\le f(\\delta)$].\n* **On Question 2:** Regarding the overhead cost of unknown covariances, we acknowledge that there two different costs depending on the variables' distributions:\n   + For bounded variables: If variances were known, we could carry the same analysis using the standard Bernstein inequality (exposed in Boucheron et al 2013, Theorem 2.10) with exact variances. However, since variances are not known, we use the empirical Bernstein inequality (Maurer and Pontil 2009), in which the true variance is replaced by its empirical counterpart. The (accuracy) cost when we plug the empirical estimate appears in the numerical constant of the sub-exponential tail term (the $\\mathcal{O}(1/n)$ term) where we obtain a constant of $7/3$ instead of $1/3$ in the standard Bernstein version. This cost, as pointed out by the reviewer, is merely a numerical factor when compared to the sample complexity of algorithms designed explicitly for independent arms. On the other hand, when arms are dependent, our guarantee demonstrates that being adaptive to covariance can result in a substantial improvement, possibly by an arbitrary factor, in certain scenarios as highlighted in the introductory examples in lines 78-107.\n  + For Gaussian variables the overhead of unknown variances takes a different form: if the sample size is larger than  $\\log(1/\\delta)$, the cost of plugging in the empirical variance estimate into the Chernoff's concentration inequality is only a multiplicative constant slightly larger than one (nearly $1+2\\sqrt{\\log(1/\\delta)/n}$). However, in the case of a small sample regime ($n<\\log(1/\\delta)$), the cost is a multiplicative factor of $\\exp(\\sqrt{\\log(1/\\delta)/n}+1/2)$ due to the nature of the left tail of the chi-squared distribution (we refer the reviewer to the Sections D and K of the appendix for detailed calculations). We would like to draw the reviewer's attention that, for most natural regimes, the number of queries made for each arm is larger than $\\log(1/\\delta)$, hence the last described effect does not arise. However, in some specific regimes (such as the case of very small variances of the arms) an optimal algorithm should query less than $\\log(1/\\delta)$ samples, which necessitates introducing the exponential multiplicative term presented above into the concentration upper bound. This translates into a different form of guarantee presented in Theorem 5.1, inequality (8). It is important to note the cost in this regime cannot be avoided as highlighted by our lower bound presented in Theorem 6.2.\n  + In summary, the overhead cost of unknown covariance is rather mild except in very specific regimes.\n* **On Question 3:** Regarding the extension to sub-Gaussian variables, we would like to clarify that our algorithm relies on the empirical Bernstein inequality, which was originally designed in the literature for bounded variables. However, we have extended this inequality to accommodate Gaussian variables by leveraging existing concentration results. It is essential to note that developing such inequalities for sub-Gaussian variables is generally a non-trivial task. One possible direction to extend the considered class of distributions is to suppose that arms follow a sub-Gaussian distribution and satisfy a Bernstein moment assumption (such extensions were pointed out by works on bounded variables e.g., Balsubramani and Ramdas 2016). Given the last class of function, we can build on the standard Bernstein inequality with known variance, then plug-in an estimate of the empirical variance leveraging the concentration of quadratic forms (see Bellec 2019). However, it remains uncertain whether an extension for sub-Gaussian variables (without additional assumptions) is practically feasible.\n* **On Question 4:** The algorithm that compares candidate arms with convex combinations of the remaining arms is developed in Section B of the appendix. It was not included in the main body due to the limitation on the maximum number of pages allowed. In this algorithm, we compare candidate variables with a convex combination of other variables. In some cases, it can lead to improved guarantees. We refer the reviewer to the paragraph between lines 464 and 471 in the appendix for the motivation behind introducing this algorithm.\n* We thank the reviewer for pointing out the minor remarks and identifying typos. We will certainly consider and address these observations in the final version.\n\nZ. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. ICML, 2013.\t\n\nK. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil’UCB: an optimal exploration algorithm for multi-armed bandits. COLT, 2014.\n\t\nBalsubramani and Ramdas, Sequential nonparametric testing with the law of the iterated logarithm, UAI 2016.\n\t\nP. C. Bellec. Concentration of quadratic forms under a Bernstein moment assumption. arXiv preprint 2019.\n\t\nBoucheron S., Lugosi G.  Massart P. (2013). Concentration Inequalities: A Nonasymptotic\nTheory of Independence. Univ. Press, Oxford.\n\t\nAndreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization, 2009. "}, {"review_id": "1Q0UmX30ML", "reviewer": "Reviewer_XxU8", "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.", "questions": "- What would be the main hurdles in extending the lower bound theorems to any one-dimensional exponential family?", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n- 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.\n- 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.\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.       \n\nIn the context of developing lower bounds, the conventional approach involves creating two distributions of the arms that are identical except for one arm, which is made optimal in one of the distributions. Subsequently, a lower bound is established on the number of queries necessary to differentiate between these distributions, yielding a lower bound for the number of queries for the specific arm i. However, this method proves insufficient for deriving precise lower bounds in our particular scenario. As an alternative direction, we propose exploring the creation of alternative distributions in which all arms are modified instead of just one."}]

Author rebuttal:
We thank the reviewers for the valuable feedback. We address below some points raised by the reviewers:

* **Link with bandits literature with dependent arms:** 
     + **Bandits on graphs:** Previous studies on graph-based bandit problems with side observations in the stochastic setting (such as Caron et al., 2012) also explore the potential of simultaneously observing rewards from multiple arms. However, in these investigations, it is assumed that the distributions of arms are independent. We are not aware of any existing research on bandit problems in graph-based scenarios where the learner successfully attains adaptability to covariance among arms.
     + **Combinatorial semi-bandits:** about comparison with existing covariance-adaptive bandits works. While covariance-adaptive approaches have been explored in the context of combinatorial semi-bandits, it is important to note that the setting and objectives of this class of problems differ from ours. In our setting (Protocol 1), the learner has the flexibility to query any subset of arms, and the ultimate goal is to identify the single best arm. On the other hand, in combinatorial semi-bandits, the learner selects a subset from a predetermined set of subsets $\mathcal{M} = \\{ M_1, \dots, M_d \\}$ at each round $t$, where $M_i \subset \[K\]$ and $\lVert M_i\rVert_1 \le m$ for a specific problem parameter $m$. However, the objective in the latter case is not to identify the best arm individually but rather to find the subset $M_i$ with the largest sum of rewards. Given these differences, we refrained from comparing the guarantees obtained in our work with those of combinatorial semi-bandits. The dissimilarities in problem structures and primary objectives lead us to believe that such a comparison would not be meaningful.
* **On extending the assumptions to include sub-Gaussian variables:** We would like to clarify that our algorithm relies on the empirical Bernstein inequality, which was originally designed in the literature for bounded variables. However, we have extended this inequality to accommodate Gaussian variables by leveraging existing concentration results. It is essential to note that developing such inequalities for sub-Gaussian variables is generally a non-trivial task. One possible direction to extend the considered class of distributions is to suppose that arms follow a sub-Gaussian distribution and satisfy a Bernstein moment assumption (such extensions were pointed by works on bounded variables e.g., Balsubramani and Ramdas 2016). Given the last class of function, we can build on the standard Bernstein inequality with known variance, then plug in an estimate of the empirical variance leveraging the concentration of quadratic forms (see Bellec 2019). However, it remains uncertain whether an extension for sub-Gaussian variables (without additional assumptions) is practically feasible.
* **Position of our contributions with respect to the standard bandits setting and variance adaptive A/B testing:** Please refer to the second and third point of the rebuttal on reviewer THM3 for a more detailed discussion. In the standard BAI setting (one query per round) previous works (Mnih et al 2008, see our related work section) developed strategies that are adaptive to the variances of arms. In our setting, by allowing simultaneous queries we developed strategies that are adaptive to the variances of arms and covariances between arms. As shown by our introductory toy examples in lines 78-107, some basic intuitions in the standard setting no longer hold: for instance, we show that a sub-optimal arm may be eliminated by another sub-optimal arm much faster than by the optimal arm. Our main contribution is to develop strategies taking into account such observations among others, leading to guarantees that improve substantially the guarantees of the algorithms developed in the standard setting.
* **Regarding the cost of not knowing the variances:** Please refer to the second point of the rebuttal on reviewer pLAq for a more precise discussion. Regarding the overhead cost of unknown covariances, we acknowledge that in the scenario of independent arms, there is indeed a cost associated with being adaptive to covariances. However, we agree that this cost is merely a numerical factor when compared to the sample complexity of algorithms designed explicitly for independent arms. On the other hand, when arms are dependent, our guarantee demonstrates that being adaptive to covariance can result in a substantial improvement, possibly by an arbitrary factor, in certain scenarios. This improvement highlights the significance of considering covariance information in such situations and justifies the usefulness of our approach in dealing with dependent arms.

Volodymyr Mnih, Csaba Szepesvári, and Jean-Yves Audibert. Empirical Bernstein stopping. ICML 2008.
	
Balsubramani and Ramdas, Sequential nonparametric testing with the law of the iterated logarithm, UAI 2016.
	
P. C. Bellec. Concentration of quadratic forms under a Bernstein moment assumption. arXiv preprint 2019.

Caron, Stéphane, Branislav Kveton, Marc Lelarge, and Smriti Bhagat. “Leveraging side observations in stochastic bandits.” UAI 2012.

Meta-review: This paper examines the best arm identification problem with a fixed confidence level, where arm distributions are dependent and multiple queries are allowed. The problem under study is both innovative and intriguing as it extends the practical application of Best Arm Identification methods in real-world scenarios. The authors present algorithms capable of discerning the exact best arm in this context, and provide both an upper and lower bound for sample complexity, demonstrating the optimality of the algorithm. 

The paper has received unanimous acceptance recommendations. In accordance with the reviewers' viewpoints, I encourage the authors to incorporate all the points raised during the discussions into their final, camera-ready version of the paper. Congratulations on this commendable work.
Decision: Accept (poster)