Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Authors: Maximilian Graf
Thuot Victor
Nicolas Verzelen
Venue: ICML 2025 poster (2025)
Keywords: clustering
bandit theory
pure exploration
information-theoretic bounds
machine learning
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We consider a problem of clustering in an adaptive and sequential setting, and provide an efficient and optimal algorithm.

Abstract: We study the problem of clustering a set of items based on bandit feedback. Each of the $n$ items is characterized by a feature vector, with a possibly large dimension $d$. The items are  partitioned into two unknown groups, such that items within the same group share the same feature vector. We consider a sequential and adaptive setting in which, at each round, the learner selects one item and one feature, then observes a noisy evaluation of the item's feature. The learner's objective is to recover the correct partition of the items, while keeping the number of observations as small as possible. 
We provide an algorithm which relies on finding a relevant feature for the clustering task, leveraging the Sequential Halving algorithm. With probability at least $1-\delta$, we obtain an accurate recovery of the partition and derive an upper bound on the required budget . Furthermore, we derive an instance-dependent lower bound, which is tight in some relevant cases.

Clustering Items through Bandit Feedback Finding the Right Feature out of Many
Maximilian Graf"
Victor Thuot" " Nicolas Verzelen
A Absrract
This problem arises in crowdsourcing platforms, where com- plex labeling tasks are decomposed into simpler sub-tasks, typically involving answering specific questions about an item see (Ariu et al., 2024). A motivating example is im- age labeling: a platform sequentially presents an image to a user along with simple question such as "Is this a vehicle?" or "How many wheels can you see?". The learner leverages these answers to classify the images into categories. In this setting, the images correspond items that must be clus- tered, while questions correspond features. This problem is special case of the model studied in (Ariu et al., 2024), where the authors numerically demonstrate the advantage of an adaptive sampling scheme over non-adaptive ones. However, they do not establish the theoretical validity of their adaptive procedure.
We study the problem of clustering set of items based on bandit feedback. Each of the items is characterized by feature vector, with possibly large dimension d. The items are partitioned into two unknown groups, such that items within the same group share the same feature vector. We con- sider a sequential and adaptive setting in which, at each round, the learner selects one item and one feature, then observes a noisy evaluation of the item's 's feature. The learner's 's objective is to recover the correct partition of the items, while keeping the number observations as small as possible. We provide an algorithm which relies on finding relevant feature for the clustering task, leveraging the Sequential Halving algorithm. With probability least 1 6, obtain an accu- rate recovery of the partition and derive an upper bound on the budget required. Furthermore, we obtain an instance- dependeed lower bound, which is tight in some relevant cases.
From a theoretical perspective, our problem consists of clustering n items based sequential and adaptive queries to some of their d features. Intuitively, the difficulty of the clustering task is driven by the differences between items in different groups across these d features. In particular, it depends both on the magnitude of these differences and on their sparsity-that is, the number of features on which the items differ significantly.
1. Introduction
In this work, we precisely characterize the sample complex- ity of the two-group' clustering task, in fully adaptive setting. Our main contributions are as follows:
We consider a sequential and adaptive pure exploration prob- lem, in which a learner aims to cluster a set of items, each represented by feature vector in d&d The items are par- titioned into two unknown groups such that items within the same group share the same feature vector. The learner sequentially selects an item and feature, and then observes noisy evaluation of the chosen feature of that item. Given a prescribed probability 6, the learner's 's objective is to col- lect enough information to recover the partition of the items with a probability of error at most d.
We introduce the Bandit werelicClusteer Clustering procedure- Algorithm 4. On the one hand, it outputs the correct partition of the items with a prescribed probability 1-5. On the other hand, it adapts to the unknown means of the groups in order to sample most the informative features. In Theorem 3.1, we provide a tight, non- asymptotic upper bound on its sample complexity as a function of n, d, log(1 15), and the difference between the means.
'Equal contribution 'Institut für Mathematik, Universität Potsdam, Potsdam, Germany iINRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France. Correspondence to: Maximilian Graf <graf9 @aal9@uunipooeee wouni-ottdaamdee. de>, Victor Thuot <vie- thuot fr
Conversely, we establish in Section 4 an information- theoretic lower bound on the budget, which entails the optimality of Bandi telusteriust,,n
From high-level perspective, our algorithm operates in three steps: first, it identifies pair of representative items
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In the core manuscript, we focus on K 2 groups. We discuss how extend our ideas to K > 2 clusters in Appendix C.

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
belonging to different groups; second, it selects a feature that best discriminates between the groups; and finally, it leverages this discriminative feature to cluster all items.
have previously introduced adaptive clustering problems for crowdsourcing (Ho et al., 2013; Gomes et al., 2011), although their settings does not directly relate to ours.
Connection to good arm identification and adaptive sens- ing literature. One of the key challenges is to achieve the trade-off between the budget used for identifying a good discriminative feature, and the budget used for the clustering task. We borrow techniques from the best-arm identification literature, specifically employing the Sequential Halving algorithm (Karnin et al., 2013) as subroutine, leveraging its strong performance in settings where multiple arms are nearly optimal (Zhao et al., 2023; Katz-Samuels & Jamieson, 2020; Chaudhuri & Kalyanakrishnan, 2019). The first iden- tification step - finding two items belonging to distinct groups - closely related to the adaptive sensing strate- gies for signal detection, studied in (Castro, 2014), where the problem is framed as a sequential and adaptive hypoth- esis testing task. Furthermore, our approach incorporates ideas from (Castro, 2014; Saad et al., 2023) to efficiently identify the most informative features for clustering.
Connection to online clustering of bandits. We point out another line of works (Gentile et al., 2014; Li et al., 2019; Liu et al., 2022; Li et al., 2025) on the so-called online clustering of bandits problem an instance of contextual linear bandit. This problem bears some resemblance to our setting, as it involves exploring a bandit environment with an underlying clustering structure among items. Still, there are two major differences with our problem: (1) the learner has no control over which items are presented at each time step, and (2) the algorithms (such as the CLUB Algorithm and its extensions) are designed and evaluated in cumulative regret setting.
Organization of the manuscript. The model is introduced along with notation in the following Section 2. In Sec- tion 3, we describe our procedure and analyze its sample complexity. Section 4 provides matching lower bounds on the budget that imply the optimality of our procedure. Fi- nally,we present numerical experiments in Section 5 and discuss possible extensions in Section 6.
Connection to dueling bandits literature. Our bandit clustering problem is an instance of pure bandit explo- ration problem, where one can sample interaction between items and features. In that respect, it is also related to rank- ing (Saad et al., 2023) and dueling bandits in the online literature (Ailon et al., 20;4; Chen et al., 2020; Heckel et al., 2019; Jamieson& & Nowak, 2011; Jamieson et al., 2015; Ur- voy et al., 2013; Yue et al., 2012; Haddenhorst et al., 2021) where the goal is to recover partition of the items based on noisy pairwise comparisons. Some of the ranking pro- cedures are based on estimating the Borda count (Heckel et al., 2019), some other procedures, such as (Saad et al., 2023), aim at adapting to the unknown form of the com- parison matrix to reduce the total budget. In essence, our approach is related, as seeks to balance the trade-off be- tween identifying relevant entries and exploiting them for efficient comparisons.
2. Problem formulation and notation
Consider a set of n items, indexed by [n] = -1,...,,11 Each item is characterized by a feature vector of dimension d, where the number of features may be large. Let M e Raxd be the n x matrix such that the i-th row of M contains the feature vector of item i. We denote the feature vector of item i as M,.- (M,.I....MMM.)))) We assume that the items are partitioned into two unknown groups, such that items within the same group share the same feature vector. The groups are assumed to be nonempty and non- overlapping. The objective is to recover these two groups. Assumption 2.1 (Hidden partition). There exist two distinct vectors μ40 E Rd and μ41 E Rd, and a non-constant label vector g E {0, 13" such that for any item i [n].
Connection to other bandit clustering problems. Recent works (Yang et al., 2024; Thuot et al., 2025; Yavas et al., 2025) have investigated clustering in a bandit setting, where items must be clustered based on noisy evaluations of their feature vectors. However, in these settings, the entire feature vector of the chosen item is observed at each sampling step, whereas in our framework, only single feature of given item is observed per step. Our observation scheme enables more efficient allocation of the budget by focusing on the most relevant features - those that best discriminate between groups. The trade-off between exploring relevant features and exploiting them for classification is at the core of our work. This allows us to cluster the items with much lower observation budget than in (Yang et al., 2024; Thuot et al., 2025)- see the discussion section. Other authors
HO
if g = 0
Mi.-
in if g() = 1
As is standard in clustering, (g, /40 (4,111 encodes the same matrix M as (1 (1-9) 9: Pl, Mo). Therefore, we assume without loss of generality that g(1) = 0 in order to make the label vector g identifiable.
We consider bandit setting, in which the learner sequen- tially and adaptively observes noisy entries of the matrix M. At each time step t, based on passed observations, the learner selects one item I, E [n] and one feature J, E [d]. She then receives X,, a noisy evaluation of My,J, Condi- tionally on the pair (Je, Jt), X, is an independent sample
2

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
drawn from an unknown distribution PIc.J, with expectation M... The collection of distributions (Vt.))s is referred to as the environment.
challenging the estimation of g becomes. In particular, we analyze the complexity of the clustering task with respect to the entry of the gap vector A ordered by decreasing absolute value, namely
A 2 A 2 ...... ......22 (
We assume that the noise in observations is I-subGaussian.
Assumption 2.2 (1-subGaussian noise). For any pair (i,j) E [n] x [d] if X ~ Vij. then X - MMi is 1- subGaussian, namely
Most intuitions behind our method rely on the sparse set- ting, where the two groups differ in exactly entries with a constant gap h. This corresponds to the case where the gap vector A has exactly s nonzero entries equal to h >> O and d entries equal to 0. The smaller the sparsity level 8, the more entries must be explored to detect a discriminative feature. The smaller the magnitude h. the more budget is required to distinguish between the two groups
E - S exp (P/2) VEER.
This subGaussian assumption is standard in the bandit litera- ture (Lattimore & Szepesvári, 2020). It covers, for example, the emblematic case where observations follow Gaussian distributions with variance at most 1, as well as bounded random variables such as those following a Bernoulli distri- bution on [0, 1]. By rescaling, the results can be extended to the case of o o-subGaussian noise.
Besides, we define 0 the balancedness of the partition g, that is the proportion of arms in the smallest group
0 := Σ (6(0 - 0) E=1
1 Σ nE 1=1
(((()= = 1)
We tackle this pure exploration problem in the fixed con- fidence setting, a common framework in the bandit litera- ture (Lattimore & Szepesvári, 2020). In this setting, the learner must decide not only which observations to make but also when stop. Given prescribed error probability 6, the learner aims to recover the correct partition of the items with probability at least 1 - 6, while minimizing the total number of observations. The learner sequentially collects observations until a stopping time T, after which it outputs an estimated label vector I E {0, 1 (satisfying ((1) = 0). The total number of observations, given by T, is referred to as the budget of the procedure. Formally, T' is a stopping time with respect to the natural filtration associated to the sequential model.
Intuitively, the smaller is, the more unbalanced the par- tition is, and the more difficult it is discover two items of distinct groups. For identifiability reasons, we assumed in Assumption 2.1 that the groups are nonempty which implies in particular that n > 2, but also that 0 E [1/n; 1/2).
3. Algorithms
3.1. Introduction to our method
We introduce briefly our method, which contains two steps.
First, we fix arbitrary the item ro 1 representative of the first group?. Then, aim to identify second rep- resentative item r1 E [v)] that belongs to the other group, and feature j E [d] such that Mr..j differs from Mr significantly, that is such that [Mr, - Mro.. is large. Our method balances the budget spent on identifying such dis- criminative feature, with the budget required for classifying all items based on this feature. Improving the budget com- pared to non-active settings requires over-sampling certain rows, which we refer to as representatives, following (Thuot et al., 2025). This step is crucial for accurately estimating some entries of the vectors un and µ and, ultimately, for accelerating the clustering task.
For any confidence level 6, we say then that a procedure A is 8-PAC (Probably Approximately Correct) if
PA. - g) > 1-5,
where FA. denotes the probability distribution induced by the interaction between the environment v/ and the algorithm A.
The performance of a 8-PAC algorithm is evaluated through its budget 7', which should be small as possible. In this paper, we derive upper bounds on T that hold with high cabhability-tpiicaal
Importantly, if we detect an entry (r1,5) in the matrix where the gap [Mr Mro.il is sufficiently large, we obtain two complementary pieces of information. This naturally leads us to organize the clustering task as a two-step procedure:
on an event of probability at least 1-ô, ô, under which the algorithm returns correct clustering.
We introduce two key quantities for analyzing the problem. The gap vector is defined as
1. we can test that |Mr Mro.il > O, then item Ti can serve as a representative of the second group. Algo- rithm 2 identifies such item rı, with high probability. Once the two representatives To and r are known, we
A = #1 - pl E Rd
which naturally captures the difficulty of the clustering task. By assumption, we have A # 0 so that there is exactly two disjoint groups. The smaller the norm of A is, the more
By symmetry, any randomly selected row could serve the same purpose.
3

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
allocate a significant portion of the budget to these items in order to identify discriminative feature in the gap-vector A.
Algorithm 3. In Algorithm 2, we explore the entire matrix in order detect row rn that differs from the first row ro 1, for this we use / = [mx] \ Vo. In Algorithm 3, we focus the exploration on two rows ru = 1 and r1 (I = {fr)) aiming at detecting a feature that best separates the two groups represented by To and r1-
2. If we identify& a feature j such that J - Mraal not only differs from zero but also exceeds certain pressoldd-peeiifie later-then feature j is deemed sufficiently discriminative, and we concentrate the clas- sification budget on this feature. We then estimate ر = [Mro.. - .I with samples from entries (ro:j) and (ri,j), and classify the remaining items with budget of order O ( [ log( uniformly allocated over items in the j-th column of M. This second step is detailed in Algorithm 3.
Algorithm 1 Compareesepnnntialllllii
(CSH)
Require: To an item, / C [n]\ro Vro subset of items, L number
of halving steps, 7 2 24+2 budget
Ensure: a couple (i.j) 1 x [d]
I: selects So +- (1) (42, f2)...., (122, )} uni- formly with replacement from / x [d]
2: for 1 = -......L do
3: TI + 1----
3.2. Warm-up: adaptation of Sequential Halving
4: for (1,3)
E S do
x Tou
x (m)
wiid Vraad
As subroutine, we introduce CSH for CompareSequentin a Halinvnng, which is detailed in Algorithm 1. It is a variant of the Sequential Halving (SH) algorithm, introduced in (Karnin et al., 2013), which is very similar to Bracketing Sequential Halving described in (Zhao et al., 2023, Alg. 3). Building on recent advances in the analysis of SH applied to various best arm identification problems (Zhao et al., 2023). we analyze the performance of the method in a specific problem that we introduce we provide an explicit guarantee for CSH in Lemma D.1.
draw
(1)) whidd Vij rois)
store Das +
1 E
(x(()) 1s
x((o)
72
7: end for
8: keep in St indices (i.j) E S corresponding to the
largest Dis
9: end for
10: return (i,j) St.
The algorithm takes 4 entries ro: I, L, T. Given a fixed item ro E [n] and a subset of items C [n]] \ To, CSH outputs an item I and a feature j E [d] for which the absolute difference MM.j Mr is large as possible. Each time run CSH, we allocate a budget T that the algorithm can fully spend. That is, CSH operates under a fixed budget constraint.
3.3. First step: CandidateRow
We start our procedure by solving a sub-problem which consists on detecting an item T1 which is not in the same group as the prefixed representative ro 1. We perform this step in the following Algorithm 2. The guarantees of Algorithm 2 are proved in Appendix E and are gathered in Proposition E.
Following the literature on best arm identification with multiple good arms (Berry et al., 1997; Katz-Samuels & Jamieson, 2020; Jamieson et al., 2016; De Heide et al., 2021), we incorporate a sub-sampling mechanism. Initially, CSH selects randomly So. subset of 2 entries from I x d, where L is a parameter specifying the sub-sampling size. Se- quential Halving is then applied exclusively to the selected subset, rather than to the entire matrix. The optimal choice for L balances two factors. If is small, the algorithm concentrates more budget per entry, enabling the detection of smaller gaps. If L is large, we increase the likelihood of including in Su significant proportion of good entries, en- suring that the quality of the remaining entry is not limited by an unlucky draw.
In Algorithm 2, we perform multiple runs of the CHS sub- routine, iteratively increasing the budget Tj = 2*+1 allo- cated for each run. For a given run of CSH(ro, [m], L. Ts), we obtain an entry (i.j) (Line 4). In Line 5, we use the same amount of observations 2 to estimate the gap [M, - Mro.gl Finally, in Line 8, we perform test based on a Hoeffding's 's bound to decide whether Mr. Mro.il > O or not. If at some point, this test concludes, Algorithm 2 outputs 71 = i. The threshold chosen in the stopping condi- tion from Line 6 is designed to assure that with a probability larger than d, then the selected item r1 belongs another group as ro- 1.
In Line 3, we chose T.max as
We employ CSH as a subroutine in both Algorithm 2 and
Toogo (16dn log
44 (4log(8nd)
I Lmax
'Actually, row ro is sampled half of the time, so that each sample from vij is compared to new one from Prouj. Any more refined book-keeping of samples from row ro would at best improve the budget by 2.
which corresponds to the sub-sampling budget required, according to Lemma D.1, when @ = 1/n takes the smallest
4

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Algorithm 2 CandidateRos (CR)
3.4. Second step: Clusterryyandiicttes
Require: confidence parameter > O, item ro Ensure: row index 71 [n]]
Consider the high probability event on which, after the first step of our procedure, Algorithm 2 provides an item r1 E [n]] such that Mr., # Mr.... Our next goal is to select feature j such that A is large enough to allow quick classification of each of the n items. We propose the pro- cedure Algorithm 3 which shares a similar structure with Algorithm 2. The guarantees of Algorithm 3 are proved in Appendix E. in Proposition F.I.
1: initialize r 0, +
2: while 1i = do
3: for 1 - L S Lima such that L 2
I 2h+1 do
4: (i.j) + CSH((m)) L. 1
5: draw {
x rodt .. x x(2) iid.
mn
~
Vrou
x is
i.d.
Ver
6:
if
Ei [ x
We begin by performing several runs of CSH, with / {ri} in order to detect large entries in the (absolute) gap vector A. As in Algorithm 2, we perform CSH with an increasing sequence of budget Tx = 2*+1, and for each budget Tx, we test all possible sub-sampling sizes = L...., Lmax. In Line 3, we define
V 4- 2* log (Qo.107) then
7:
F1 <-
8:
end if
9:
end for
10: A: k +
(1logg (1lg(8d) )
11: end while
Liax
1ogg
[6d
as the maximum sub-sampling size needed to detect signal when the sparsity level s is the smallest.
possible value.
From Lemma D.I, we know that for (3)) S 128L?, for some constant e, if the condition
In Line 4, we call CSH(ro, {r1 L, 2k+)). We obtain feature j and then estimate |4 |Mro.. - M in Line 6. For that, we take [2 /nj samples from Vrou and Vri.j. and compute the sum of differences D E /nl (Xris) Xro.s). We deduce high probability lower bound راقر 125/n| (B c) < |4yl where is defined in Line 7. Based on ررق we can classify (with high probability) each item by sampling the j-th feature O A log(n/0)) We can then assess whether the classi- fication budget required for feature j is feasible given the budget Tg. If T3
Th = 2 > cLinax d (log(1/6) + log log(nd))
0s4y,
holds, then, with high probability, there exists L < Lmax such that CHS [n], L, Tk) outputs a pair (i,j) with |Maj Mra.jl > | Besides, under this budget condition, the termination condition from Line 8 will be reached w.h.p. This condition is especially true for the sparsity s E [d]. where the inequality above is tightest.
As (Jamieson et al., 2016; Saad et al., 2023), the ex- ponential grid Th 2* allows us adapt the strat- egy, and reach budget that scales up to log terms O min.eld B edge of this quantity by the learner.
< en log(n/5)), it seems that with fea- A
ture j. the classification budget exceeds Tg. we discard this feature and repeat CSH with larger sub-sampling size L or budget T'
d log(1/0) even without prior knowl-
We now bound the budget of our procedure thanks to Lemma D.I. Assume that A S 128L?. If it holds for some constant e that
relate this quantity to the 12 norm of A. For that, we define
Interestingly,
Tx = 2k+11 > cL d (log(1/8) + log log(d))
E argmmx.ee4]** (
sA7
This quantity, s*, appears an effective sparsity parame- ter, as observed in signal detection contexts. Actually, the following bound holds
then, there exists & Lmmxx such that CHS rı, TR) outputs a feature j such that |Mrai - Mrss > | /2. If we also have TІ > C log(n/6), then the algorithm stops, otherwise it would continue sampling.
max s- <E[4]
A <
|| < log(2d) max 8. A7.) sE[d]
(2)
Overall, we prove that the total budget of the procedure, up to logarithmic factors, is no more than
Finally, we prove that Algorithm 2 outputs an item r1 which belongs to the second group with probability larger than 1 - 8, using budget that is smaller, up to logarithmic terms, than the quantity d log(1/8). We will see in मां Theorem 4.1 1 that this bound optimal for both & and A.
(s + +n) sE|d]
( (1 1/,) +1) log(1/8)
min
5

---

T| log(1/6), which correspond to the budget used identify an item belonging to the second group. In the sparse setting, it scales as d ês n2 which is Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Algorithm 3 MalusterByCaddddateee (CBC)
9 with budget of at most
Require: confidence å > 0, representative items Yo, 71 E [n]]
1 H.
T Č logg
Ensure: labels 9 E {0, 13 {0, 13"h k t [n)]
1: 9 f- (O....,0)² .)" "
where there exists a numerical constant C, and an index s" (īd/n] Kj [d] A # #H),, such that Ö is logarithmic factor smaller than
2: while True do
3: for 1 1 L Lmax such that L- 2 = 2h+ do
4:
j C5H,srro, r1, L, 2
x (1)
roj" x (112* /nJ) wiid vroit
C' (log (1/) V 1)*
5: draw
x x(1)
x(12"/1) /nl) wiid veai
ro
log(dn)) log (d (log+ log log(1/A()) V1).
rid right...
D 21-1 /m) (Xris) Xroi)
6:
In order to understand the motivation behind our complexity H, we write our main theorem in the sparse setting A is s-sparse with constant magnitude h.
7:
E Et /4 [2//n /n] log(nk~//000 /0.156)
i 2 3- then
8:
9:
for i [n] do
Corollary 3.2. For 8 E (0, 1/e) and E {0, h3 with 6, Algorithm
x
(al) wild vrod
0 < 1, with a probability of at least
10:
draw
x
x 112 (12%/n) jnl) wiid Vas
returns 9 9 with budget of at most
m2
Ö 1og(1/6)
(
+
11
11:
D. + Σ (Xi,) - Xroo)
B|
h22
1=1
where Ö is logarithmic factor smaller than C (log log(1 (8) V 1)² -log(d)) (log. log(1/h?) V V1).
12:
0(1) 1 Di 26)
13:
end for
14:
output
with a numerical constant C <>> 0.
end if
16:
end for
Compared to the lower bound in Theorem 4.1, we prove that our procedure optimal when the gap vector is s-sparse with a constant magnitude h. For general gap vector A, we have good reasons to think that understanding the optimality of this trade-off for this simple example allows us to understand (at least intuitively) the optimality for general vectors.
17:
end while
3.5. Main Algorithm
To obtain a complete clustering procedure that is adaptive to A and 0, one simply has combine Algorithm and Algorithm 3. The overall clustering procedure is then given in Algorithm 4.
We interpret in (3) as a non asymptotic sampling com- plexity, which depends on the instance-specific parameters of our model 0, A, n, and The complexity H can be decomposed as two terms:
Algorithm 4 Bandit Clustering
Require: confidence parameter 8 >>> 0
First Term:
Ensure: labels O E {0,
I: Fix =
2: ri + C2 ro)
necessary, as we need to explore least Øg entries to find non-zero entry, and need least 1/h² samples from
3: 9 + CBC(6/2,
each of these entries to decide if it is equal to 0 or not with constant probility of error.
Theorem 3.1. For 8 E (0, 1/2e), consider Algorithm 4 with
entry 8. Define
Second Term: min (2+ A +1). This term
represents the best trade-off between the exploration of the gap vector A and its exploitation for clustering. Indeed, the term A
H d 1 0
1
d - + m
+
+ min sE(d]
)
+
||
s*)
A2
log(1/5) is the price for clustering if we use
(8)
(3)
a feature with a gap |A(s)) whereas - log(1/6) corre-
where s" is the effective sparsity defined in (2).
sponds to the price for identifying a feature with a gap at least (()))-
With a probability of least 1 - 6, Algorithm 4 returns
6

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Define the effective sparsity & for which the minimum holds, and define the effective magnitude (z)- In the sparse setting, this is exactly the sparsity level. Intuitively, we can argue that entries significantly larger than (3) are too rare to be detected (otherwise, 8 would be smaller), and entries much smaller than (3) are too weak to be used for classifi- cation with a budget H. Our insight that the problem as hard as if the gap vector were 5-sparse with a constant mag- nitude A (.+), setting where we have matching lower and upper bounds (see Corollary 3.2 and Theorem 4.1), leading to our complexity.
to the unknown structure of the gap vector A. This term matches, up to logarithmic factors, the budget incurred in the first step of our algorithm for identifying relevant item. In particular, it implies that the first step from Algorithm 2 is optimal.
The second term scales as
=h loo and take into ac- A
count the difficulty of clustering all items once discrim- inative feature is identified. Specifically, if the most in- formative feature is provided by oracle-i.e., feature index j [d] such that |رما A(i) is maximal then the problem reduces to performing independent Gaussian hypothesis tests of the form Ho : X ~ A 1) versus H1 X ~ (I), 1).
Finally, we mention that the remaining term d/(Os*) in H only dominates in the very specific setting where the non-zero entries of A are really large so that || 2 8*
In the case where the gap vector A takes two values, this lower bound matches, up poly-logarithmic terms, the upper bound from Corollary 3.2. In summary, when A only takes two values, @ and log(1/5). /6). For more general A, we conjecture that the trade-off in H in (3) is optimal and unavoidable.
4. Lower bounds
In this section, we provide a lower bound on the budget of any 8-PAC algorithm. The bound is instance-dependent, meaning it holds for a specific problem instance defined by the matrix M. We establish this result by constructing a family of alternative environments, each obtained by slightly modifying the original matrix M. We then prove that any algorithm with budget that is too small cannot perform well simultaneously across all these environments. For the lower bound, we consider Gaussian environments, for which Assumption 2.2 holds.
budget is optimal with respect to d, n,
5. Experiments
We support our theoretical results with numerical exper- iments synthetic data. In the first experiment, in- vestigate the sample complexity of our algorithm in sparse regimes. We compare its performance to uniform sam- pling baseline, where each of the n x d entries of the matrix M is sampled an equal number of times, and the resulting data is clustered using the K-means algorithm. In the sec- ond experiment, we evaluate the BanditClusterinn algorithm under fixed sparsity while simultaneously in- creasing the parameters and d, and we compare dif- ferent choices of the confidence parameter > 0. In third experiment, we compare BanditClusterin to Adaptive Clustering (Ariu et al., 2024) and see how a growing number of features impacts both algo- rithms performances. We defer a fourth experiment to Ap- pendix B, which illustrates the influence of on the budget of Bandit t C1 wwllusstiing As shown in Corollary 3.2, the effect of 1 /0 is comparable to that of the sparsity discussed in the first experiment.
We define (M)) as the set of Gaussian environments constructed from M by permuting its rows and columns. Without loss of generality, we assume that 140 and f41
A. Formally, an environment i E (p) is defined using
a permutation of [n] and permutation of [d] as follows:
1) if g(((() D..j 1) if g((((())
(4)
where g E {0,1)" denotes the unknown labels associated matrix M. Intuitively, permuting the rows and columns of M accounts for the fact that (a) the target labels g are not available to the learner, and (b) the structure of the gap vector A is also unknown.
Theorem 4.1. Fix d E (0, 1/4). Assume that A is 8-PAC for the clustering task, then, there exists & E Eper (M) such that the (1 -qquniiee of the budget of algorithm A is bounded as follows
The code we used for the simulations is available in a GitHub repository*.
Experiment In this experiment, we consider small number of items (n 20) and large number of features (d 1000). For s I,..., d, define the vector A 0). where h2 15/ This choice
2(n - 2)
2d
PA.
T>
log
V
log
2 8
2
4.85
|||
65
h hg...., h, 0,....O).
(5)
ensures that A is s-sparse and satisfies || A || = 15 for any
The lower bound contains two terms. The first term scales d as "ा log(1/5), and can be interpreted the budget re- quired identify one item from each group, while adapting
Inttps:/ httpbb/gittubbbb/ com/ clusters
7

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
1+?
2.5
8m0.8
6-0.5
10a
BendiCluseeing
2.0
6u02
15% #854cconliteenee interoal
3y07000 sudpet
Berdiikkattering
20
Kimeans
15% 0sSiicennionnce intervel
1.5
BanditClustenng
1.0
102
10a
6x100
10a
2
3x110 4x2
1000
2,000
3000
4000
5000
sparsiy
number Items A
Figure 1. Different budgets for Experiment 1, depending on the sparsity of A'
Figure 2. Different budgets for Experiment 2, depending on the dimensionality of the problem and d 10 n. plexity of cost of the CBC step, which grows approximately linearly with s. These empirical dependencies on s align with our theoretical results, where the budget of CR in this case is, up to polylogarithmic factors, of order d/O which is constant in for fixed || while CBC requires a budget of order n/ (At)²
iingteiingg is mainly driven by the
8. We construct the matrix M with half its rows equal to O and the other half equal to A and sample observations as Vijj (M; 1). We examine the behavior of our algorithms as varies, which causes the magnitude h, to vary accordingly.
We report separately the budgets required by the two steps of our algorithm. For = 0.8, we run each of the algorithms CR(6/2), (6C i*) and Bandi cCluster(0 (6) total of 5000 times. We provide to CBC a representative item i" in the second group as oracle. In this setting, the ob- served error rate of SanditClustering remains close to 0.01 for all values of s. We depict the average budgets re- quired by Bandit Cec.ustteinnng considering only the runs where the first step CR returns a valid candidate row (otherwise, we emergency stop the algorithm). We also show the average budget required by CR(6/2) and CBC(8/2, in Figure 1. The figure includes the (0.05, 0.95) quantiles across simulations.
Experiment In this experiment, we consider matrices of increasing size, with n 100, 200, 500, 1000, 2000, 5000 and d = 10 so that the number of features grows proportionally with the number of items. For each value of n, we define the vector Á (n) E Rd as Á (n) 5,....,, O.....0) E Rd. We construct a matrix M(n) times d-10 times with n/2 rows equal to 0 and n/2 rows equal to Á(m) and we add Gaussian noise with unit variance. For each 8 E 0.8, 0.5, 0.2, 0.05, we run SanditClusted Clusterin(n over = 5000 independent trials. In Figure 2, we report the average budget required by Bandi ManditClun uster ering for each configuration. For 5 = 0.05, we additionally report the 5th and 95th percentiles across the simulations.
As a benchmark, we compare our algorithm to a strategy that samples uniformly all entries of M and then ap- plics the KMeans algorithm from the Scikit-learn library (Pedregosa et al., 2011). Given a budget T, we sample == TT [T/nd] observations x Liid. N(M;,, 1) per en- try, and compute X,, = Σr x!( We then cluster the items by performing the K-means algorithm with the (Xn))j=1.....d For each sparsity 8, the budget is turned by an oracle, with grid search, so that the observed error rate after x- 5000 runs below 0.01. The resulting budgets reported in Figure 1.
If we allocate budget smaller than 5n2 nd/2 uniformly at random across the nd entries of M, then on average, each item i will have d/2 2 unobserved features. As both and d increase, the probability that some item is only sampled coordinates j such that A (") 0 tends to one, rendering accurate clustering impossible. By contrast, Figure 2 shows that the budget required by our algorithm scales linearly with n. This matches the bounds from Corollary 3.2, which implies that when d' = 10 n and the parameters 0, s, and are fixed, the total budget required (up to polylogarithmic factors) of order n.
vectors (X1y))=1....!d....
From Figure 1 we observe that in the sparse regime, our algorithm requires fewer observations than the uniform sam- pling approach used as baseline. Moreover, the budget required for CR appears to be mostly independent of the sparsity level s. In this setting, the overall sample com-
Experiment 3 our algorithm Bandi sendditclustering with the Adaptive
In this third experiment, we compare
8

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
feature pair. This contrasts with (Yang al., 2024; Thuot et al., 2025; Yavas al., 2025) where the authors have to sample all the features for each item and cannot focus on most relevant features. Rewriting their results in our setting, the optimal budget for the latter problem is, up to poly-logarithmic terms, of the order of
150000
400000
0.5
350000
Error Rates
0.4
rator for Adapiie Clestering
-30000
Entorate
Eroo rate for bandiikkaterinng
-50000
0.3
nd log(1/0) + d3/2 Vn log(/1//)) ||
200000
0.2
-15000
||
Budgets
-.w Avorage budget for BanditClustoinng Bu for Adaptive Clustering
-100000
Comparing this with our main result (Theorem 3.1), we first observe that the ability adaptively select features allows to remove the so-called high-dimensional terms dd/2 V n log (1/5)/IAA that occurs when the number of features is large d 2 n log(1/6). Second, the adaptive queries allow to drastically decrease the budget in situation where the vector A contains a few large entries so that a few feature are especially relevant to discriminate. To illus- trate this, consider e.g. a setting in Corollary 3.2 where A E (0, h14 takes 8 non-zero values where the partition is balanced so that 0 1/2. Then, our budget is of the order of
55000
0.0
5
10
26 Number of features
15
25
30
Figure 3. Comparison of the performance of BanditClustering and Adaptive Clustering in Experiment 3, depending on the number of features dy.
Clustering algorithm introduced as Algorithm 2 in (Ariu et al., 2024). We fix the number of items vary the number of features as d, 2 with y =1,.... -,...,, 5. We set 0= = 0.5, and for each dy, we define 8, = / features j such that M, = 0.25 for items in the first cluster and M2.5 = 0.75 for items in the second cluster, yielding = 0.5. For the remaining features, we set Mr, = 0.5, independent of the item's 's cluster. Observations are sampled from Bernoulli distributions: Vi.j Bern(M,,)) We apply Bandi t Cluutrriinn with 5 = 0.8 over = 500 runs. We then ran the Adaptive Clusterin ig algorithm us- ing the MATLAB code provided by (Ariu et al., 2024), under the same setting and a fixed budget of T = 440,,000, also with x= = 500 runs. In Figure 3, we compare this fixed bud- get the average budget used by SanditCluster and report the corresponding error rates as a function of dy.
30 and
log(1/))
72
8/2
122
which represents a potential reduction by a factor A compared to (Yang et al., 2024; Thuot et al., 2025).
Extension to a larger number of groups. Throughout this work, we have assumed that the items are clustered into K = 2 groups However, our algorithms can be used as sub- routines to address the case where K > 2. In Appendix C, we provide an algorithm that handles this extension, along with (non-optimal) budget that scales with K2. A key challenge in achieving optimality in this setting is determin- ing whether the algorithm should focus on all K(K 1)/2 pairwise discriminative features or on a smaller, more infor- mative subset. It is significantly more difficult to devise a strategy that adapts optimally to the relative positions of the centers of the K groups. We leave this question for future work.
As the number of features increases, we observe that the error of the fixed-budget algorithm Adaptive Clustering also increases. In contrast, the fixed- maintains a
confidence algorithm Bandit consistently low error, and its average required budget re- mains largely unchanged. This behavior aligns with Corol- lary 3.2, as both d., ||| 12 and nı/h2 are constant in our experimental setup. While our algorithm performs better in this specific scenario, it is important to note that the prob- lem addressed in (Ariu et al., 2024) is more complex than the clustering task we consider. We believe their algorithm could be adapted to our setting; however, it remains unclear whether the influence of the number of features on the error rate can be mitigated.
Extension to heterogeneous groups. We also assumed throughout this work that all items within a group are per- fectly similar, meaning their corresponding mean vectors [i are equal. This assumption could be relaxed by allow- ing the μ 's within group to be close, but not necessarily identical. For instance, suppose we have prior knowledge that, for any feature j E [d], the within-group variation satis- fies, max [Ma, -M | & eminn()) [M,. My If c < 1/4, our algorithm remains correct since the search for a single discriminative feature is still meaningful and enables classification. However, if the within-group heterogeneity becomes comparable to or larger than the enter-group differences in some features, our method could fail, and further investigation would be required. Note also that if e = 1/2, the problem becomes unidentifialle.
6. Discussion
Comparison to other active clustering settings and batch clustering. In this work, we consider a bandit clustering setting where the learner can adaptively sample each item-

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Acknowledgements
Gentile, C., Li, S., and Zappella, G. Online clustering of bandits. In Xing, E. P. and Jebara, T. (eds.), Proceed- ings of the 31st International Conference Learning, volume 32 of Proceedings of Machine Learn- ing Research, pp. 757-765, Bejing, China, 22-24 Jun 2014. PMLR. URL https: /tccpp::/prcceeee /ttpppeeceennggssee .mlr. press/ hesss/v32/gge htt/////////ttetteeeeeee html.
We are grateful to the anonymous reviewers for their care- ful reading and constructive feedback, which improved the clarity and the rigor of the paper. We also thank Alexan- dra Carpentier for valuable discussions and insights that contributed to the development of this work.
Machine
The work of V. Thuot and N. Verzelen has been partially sup- ported by grant ANR-21 2-R-21--5 108-21-CELI 21-CE23--0033 (ASCALANN)). The work of M. Graf has been partially supported by the DFG Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age Statistical Efficiency and Compu- tational Tractability". Project TP 02, and by the DFG the French-Germen PRCI ANR ASCAI CA 1488/4-1 "Ak- tive und Batch- seinenSegmeniirrung. Clustering und Seriation: Grundlagen der KI".
Gomes, R., Welinder, P., Krause, A., and Perona, P. Crowdclustering. In Shawe-Taylor, J., Zemel, R., Bartlett P., Pereira, F., and Weinberger, K. (eds.), Advances in Neural Information Process- ing Systems, volume 24. Curran Associates, Inc., 2011. URL https://proceedlnss..o cc c8 6a ( pdf.
/ (ppaper_fieee/ppppr//////LLL
Impact Statement
Haddenhorst, B., Bengs, V., and Hüllermeier, E. Identifica- tion of the generalized condorcet winner in multi-dueling bandits. Advances in Neural Information Processing Sys- tems, 01225904-259111 2021.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Heckel, R., Shah, N. B., Ramchandran, K., and Wainwright, M. J. Active ranking from pairwise comparisons and when parametric assumptions do not help. The Annals of Statistics, 47(6):3099-311 -316,, 2019.
References
Ailon, N., Karnin, Z., and Joachims, T. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, pp. 856-864. PMLR, 2014.
Ho, C.-.,, Jabbari, S., and Vaughan, J. W. Adaptive task assignment for crowdsourced classification. In Inter- national conference machine learning, pp. 534-542. PMLR, 2013.
Ariu, K., Ok, J., Proutiere, A., and Yun, S. Optimal cluster- ing from noisy binary feedback. Machine Learning, 1 113 (5):2733-2764, 2024.
Jamieson, K., Katariya, S., Deshpande, A., and Nowak, Sparse dueling bandits. In Artificial Intelligence and Statisties, pp. 416-424, PMLR, 2015.
Berry, D. A., Chen, R. W. Zame, A., Heath, D. C., and Shepp, L. A. Bandit problems with infinitely many arms. The Annals of Statistics, 25(5):2103-2116, 1997.
Jamieson, K. G. and Nowak, R. Active ranking us- ing pairwise comparisons. In Shawe-Taylor, J., Zemel, R., Bartlett, P., Pereira, F., and Weinberger, K. (eds.), Advances in Neural Information Process- ing Systems, volume 24. Curran Associates, Inc., 2011. URL https::/pproceedngg... neurips. cc oc/saper_fillee/pppr//////11111 pdf.
Castro, R. M. Adaptive sensing performance lower bounds for sparse signal detection and support estimation. Bernoulli, 20(4):2217-2266, 2014.
estmaainn
Chaudhuri, A. R. and Kalyanakrishnan. S. Pac identification of many good arms in stochastic multi-armed bandits. In International Conference on Machine Learning, pp. 991 1000. PMLR, 2019.
Jamieson, K. G., Haas, D., and Recht, B. The power of adaptivity in identifying statistical alternatives. Advances in Neural Information Processing Systems, 29, 2016.
Chen, W., Du, Y., Huang, L., and Zhao, H. Combinatorial pure exploration for dueling bandit. In International Con- ference on Machine Learning, pp. 1551- PMLR, 2020.
Karnin, Z., Koren, T., and Somekh, O. Almost optimal exploration in multi-armed bandits. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th Interna- tional Conference on Machine Learning, volume 28, pp. 1238-1246, Atlanta, Georgia, USA, 17-19 Jun 2013.
De Heide, R., Cheshire, J., Ménard, P., and Carpentier, A. Bandits with many optimal arms. Advances in Neural Information Processing Systems, 34:22457-22469 2021.
PMLR.
10

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Katz-Samuels, and Jamieson, K. The true sample com- plexity of identifying good arms. In Chiappa, S. and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learn- ing Research, pp. 1781-1791. PMLR, 26-28 Aug 2020.
Yang. J., Zhong, Z., and Tan, V. Y. Optimal clustering with bandit feedback. Journal of Machine Learning Research, 25( 251186):1-54, 2024.
Yavas, R. C.,, Huang, Y., Tan, V. Y.Y.F. and Scarlett, gen- eral framework for clustering and distribution matching with bandit feedback. IEEE Transactions on Information Theory, pp. 1-1, 2025. doi: 10.1 10.11099T1.220253355866.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-1)
Li, S., Chen, W., Li, S., and Leung, K.-S. Improved algo- rithm online clustering of bandits. In Proceedings of the 28th International Joint Conference Artificial In- telligence, 19, pp. ISBN 9780999241 141.
2012.
Zhao, Y., Stephens, C.. Szepesvári, C., and Jun, K.-S. Re- visiting simple regret: Fast rates for returning a good arm. In International Conference on Machine Learning, pp. 421 42110-42158, PMLR, 2023.
AAAI Press, 2019.
Li, Z.., Liu, M., Dai, X., and Lui, J. Demystifying line clustering of bandits: Enhanced exploration under stochastic and smoothed adversarial contexts. In ICLR 2025. PMLR, 2025.
Liu, X., Zhao, H., Yu, T., Li, S., and Lui, J. C. Federated online clustering of bandits. In Cussens, J. and Zhang, K. (eds.), Proceedings of the Thirty- Eighth Conference on Uncertainty in Artificial Intelli- gence, volume 180 of Proceedings of Machine Learn ing Research, pp. 1221-1231. PMLR, 01-05 Aug 2022. https: /ptpcceednggs....//ee mlr press// v1 v180/1iu2220 html.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas. J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E.
Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Saad, E. M.. Verzelen, N., and Carpentier. A. Active ranking of experts based on their performances in many tasks. In International Conference Machine Learning, pp. 29593329513.. PMLR, 2023.
Thuot, V., Carpentier, A., Giraud, C., and Verzelen, N. Clus- tering with bandit feedback: breaking down the computa- tion/information gap. In Kamath, G. and Loh, P.-L. (eds.), Proceedings of The 36th International Conference Al- gorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pp. 1221-1284. PMLR, 24-27 Feb 2025. URL https: /ptp//eeecccc.... mlr. press httt://tttottta.aaam.m
Urvoy, T., Clerot, F., Féraud, R., and Naamane, S. Generic exploration and k-armed voting bandits. In International Conference on Machine Learning, pp. 91-99. PMLR, 2013.

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
A. Notation
To ease the reading, we gather the main notation below
number of items, d number of features
Pu # P1 E Rd feature vectors of the two groups
Mr E (1o.H1), E [n] feature vector of item
M matrix with rows (M2.) (with size
g {0, 1) true labels (fixing g(1) 0)
X ~ Miy for (i,j) E [n] x [d] [ = Ma with X - M,j l-sub-Gaussian
(0, 1) prescribed probability of emror
0 = Eis O)) 1(x()==1) balancedness
= 14 No f gap vector
s* E argmax s
(.)) effective sparcity
Moreover, as we repeatedly compare the entries of M with some row of our choice, consider fixed row for the following proofs and define
Di. = Mr Mrost for (i,j) E [n]] [d].
B. Experiment 4: Varying !
In this experiment we consider matrices with dimensions = d = 1000. The gap vector A' is defined as
A = 1.5 i 100
else.
The following simulations are run in 5000 trials: For different values 0, 2 7= 1,,,...,, (I...,[[ogg,((1 1, we run CR and CBC with confidence parameter 8 = 0.4 and Bandi Wel.steringgggo with 5 = 0.8, analogously to experiment 1. The respective budgets are plotted in Figure 4. We also compare our procedure to the K-means algorithm by uniformly allocating budgets T. - t 108) + 10 = O..... 20, by looking for each 0, for the smallest T, such that at most 0.01 (again, approximately the error rate of Bandi mnnnitttnnnt returned an incorrect cluster. We also illustrate these times in Figure 4.
for all 6,)) respective Monte Carlo iterations
Again, one see that the budget of Bandit Ceriiittuuutennnn is mainly spent the CBC part of the algorithm. For small values of 0, our algorithm requires less budget than an equally accurate version of the K-means algorithm. We can see that the budget of CBC is not effected by 8, while the budget of CR seems to be almost proportional to 1/0. Since n, d and A' are fixed, this is in line with the results in Corollary 3.2.
C. Extension to > 2 clusters
In the main part of this manuscript, focused the case of two groups as it serves an informative baseline for understanding the optimal trade-offs in clustering with bandit feedback. We introduce in this section algorithm that extends our method to the general case where K >> 2.
Building on the the ideas of Algorithm 3, we aim to identify a set of representative items (ri,..., rk) E [m]* with one item from each cluster. Given these representatives, the algorithm learns a discriminative feature for each pair clusters, enabling perfect clustering in the general case with > 2 groups. The algorithm described in pseudo-code in Algorithm
12

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
109
10a
107
budget
10
10"
DanditClustering
CBC CR
10a
KMeans
15%, 95%//confideece interval for BandiiClusterinn
10A
101
10a
Figure Different budgets for Experiment 4, depending on 04-
Setting with K > groups In this section, we assume that the items are partitioned into exactly K > 2 clusters, such that items within the same cluster share the same mean-vest vector. Specifically, there exists K centers in R denoted as Pi..... PK such that, for any E [n] then M,. {/1, (f1,..... ...,,,,k,, }. We further assume that all the centers Mı....., ........,'g jKK are pairwise distinct. For each & E [K]. we denote as G := (i [m]; M,,- J and we assume that each cluster G is non-empty. As before, consider sub-Gaussian noise and aim to identify the true partition G .i....,
Gk in the 5-PAC setting.
Note that the partition G = G L... LL is defined only up to permutation of the cluster labels.
Description of Algorithm 5. The algorithm uses the subroutines CR (Algorithm 2) and CBC (Algorithm 3), applied to subset of items.
For any E (0, 1).r [m] and C [n]] we denote as CR(6, r; G) the call Algorithm 2 where the search of representatives restricted to a given set of items (instead of (n)) We recall that CR(ō, G) is designed, to identify, if exists, an item E G such that Ms,, # Mr..
For any 8 E (0, r [n]. [n] and G C [n)] we write CBC(6, 8; G') for the run of CBC restricted to the set of items G. As we will prove later, with high probability 1 5, CRC(O, G) will output partition of G into two groups, such that the items with mean Mr. and M.. are well-separated. When calling CBC(6, s; G), the items from the clusters of r and within G are separated in two distinct sets, while other items might be split anywhere.
The algorithm takes as input the confidence parameter 5 and the number of clusters K. important to note that, in the 6-PAC setting, the number of clusters K must be known in advance. Indeed, even in the simpler case where there are only two items with means μ4 and μ2 there is finite time testing procedure that can decide between the hypotheses μu (22 (i.c., K 1) and μ1 * #2 (i.e., K 2) without any prior knowledge on the separation μ1 122-
First, we start with partition (1)) = [n), where all items are grouped together, and we fix an arbitrary item E ((1) as the first representative.
The algorithm proceeds in K - 1 epochs, indexed by e = I,..., (K - -)). In each epoch e, the algorithm identifies a new representative Te+1 and isolates all items sharing the same mean-vector Mr into new cluster.
At the beginning of the e-th epoch, the algorithm has access to partition of [n] into groups [n]] = G( ((() together with representatives Te.. If all the previous epochs were successful, then the representatives .i.... Te belong to different clusters, and the intermediate cluster G(()) will contain all items with the same mean-vector rk. The remaining items (i.e., those from unrepresented clusters) may be mixed in the current partition G(e) ..... ((e)
To identify new representative, the algorithm calls CR with the representative 7 restricted the group G(c)) for each
13

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
I= e, using confidence level de. These calls - denoted CR(6,, rk; (k - are run parallel. The first returned item from any successful call is selected the new representative
Next, for each [e]. the algorithm runs CBC( Tk, Te+1; G to split the group (( based on the new representative. With high probability, rą and Te+1 come from different clusters. In that case, CBC will divide G(=) into two subgroups: Gle+1) containing all items with mean My,,,, and R ((e-1) containing all items with mean Mre+1,-- We then define the new group G(e+1) c+1 = Uk=1 f((+t), which should contain all items with mean Mr
is the output of the algorithm. With high probability, At the end of the (K 1) epoch, the partition [n] km ( should be exact.
Algorithm 5 BBnddii twlsstrriinsttrr
Require: confidence parameter >> 0, number of clusters K Ensure: Clusters G......GG GK
1: set G(1) < [m]
2: pick a first representative ri uniformly at random from [n]
3: for e K
4: set 6g
c[K-1]
5: Run parallel CR(ó,, rki (( for E [r] until one new representative Te+1 is identified
6: for & E [e] do
7: call CBC(rk, 1 8c: (
to cluster ( into two groups Ge+1 fe+1
(swith E G
8: end for
9: gather Ge+1 e+1 = U Be+1
10: end for
return G(K)
(K) partition of the items
Theorem C.1. Let be an environment with n items. Assume that there exists [m] = = G partition of the items into K nonempty and disjoint groups such that all items in G share the same mean-vector μa- For any E [K], denote as the proportion of items with mean-vector llk.
0₂ [[dE[n]: ; M,.
Define, for any 0 + AERd.
=E|d] (
+1
H(A) = min
4-
For 8 E 1/e), consider Algorithm 5 with entry 8 and K.
With probability larger than 1 - 5, Algorithm returns a partition & of [n] equal to G (up to labelization of the clusters), with budget of at most
Kd
Ò log
max go
Σ
i
(mx))
01:lpa 1
KE
where there exists a numerical constant C, such that Ć' is a logarithmic factor smaller than
C- (log log(1/)) V 1)a
log(dn)" log log(d)(log, log(d/ min ||
14 v111)
kek
The proof of Theorem C. is postponed to Appendix G. The proofs simply exploit the results obtained in the next section of this Appendix about subroutines CR and CBC.
Comments on Algorithm and Theorem C.1 In Algorithm 5, we extend our clustering approach to the general case with K clusters by reducing the problem to sequence of binary classification tasks. This allows us reuse the subroutines
14

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
and CBC, originally designed for the case where there two groups, in a pipeline fashion. As shown in Theorem C.I, this reduction yields Ó-PAC algorithm for the general clustering problem.
The resulting sample complexity scales as K², since the algorithm performs one binary classification for each pair of clusters. This quadratic dependency is unavoidable in the worst case-for example, when the cluster means .1...... PK are positioned such a way that each pair of clusters must be treated independently. However, this approach may be suboptimal in general settings, For instance, certain features allow simultaneous discrimination among all K clusters, then the sample complexity should not need to scale quadratically in K.
In other words, while extension K 2 is straightforward and functional, it remains naive in terms of adaptivity. A more refined approach would aim to capture instance-dependen complexity, leveraging the joint geometry of the cluster centers , jK to potentially reduce the overall budget. Developing such adaptive strategies remains an open and interesting direction for future work.
D. Analysis of Algorithm 1
We analyze here the performance of CSH.
Lemma D.1. Consider E (0,1), E [d] and h > 0 such that
| 2 h. Consider C [ni] and define the relative
proportion of items in the second group as a = H1El; g(0=1H [7]
Consider Algorithm 1- CSH(ro, 1, L,T) -with input
To, I, L.,.T T such that
(16 d log
4 (lg((8/[ld) )
T. log2
(6)
as
8
L3 24
T 516
2
(7)
h2
Then CSH(ro, L, outputs a pair (1,5) such that Ma. - M 2 h/2 with probability 2 6.
Remark that for I = [ri]. then > 0. If = (ri) where s(r1) # s(ro), then = 1.
Throughout this section, we will prove Lemma D.I with - [ [m]. The general result directly follows from the case where contains all items. To see that, we just have to see that a is equal to the balancedness of the matrix M restricted to the rows 1, and we would replace n by //. and / by a.
Therefore, we consider Algorithm with input ro. I [n]. [oog (16 di log 2.+ For simplicity in notation, we also fix ro for the proofs.
(4
4 (lng((nud)
)) and T 516 51644"2 4.2"
We recall that the gap between the entries of M compared to the mean-vector of the fixed item ro 1.
for the proofs the notation Di,; == Mij Mrosi M.,;
Mi. for any couple (i,j) E [n]] [d] as
For the following proofs, define == h/2L, and for any halving step 1 = = 0, 0,1....,4. L, we define Uj as the set of remaining entries (i,j) in St such that the gap |Digl exceeds h - by
U = ((i.)) E St: |Pa.l 17)
Lemma D.1 is direct consequence of following statement:
Lemma D.2. With probability of at least - 8, it holds
Ui S
4 (4log(8nd)
2-1-3 L-3 log
2
1I
8
Proof of Lemma D.1. The first statement follows by Lemma D.2. Indeed, at the last halving step, St, contains only one pair of indices (i.ā). Lemma D.2 implies that Ur C S, is nonempty with probability at least 1 - 6, so that (i, E U.. that is, D13 > Ly = h/2.
Proof of Lemma D.2. We will prove via induction over 1, that
U S
4 1log(8nd)
2 2 L+3
log
4k = 0.1,....
8
15

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
holds with probability at least
8
2
1- 1- +1+
4 (log(8nd)
The statement follows then from
2 (4log(8nd)
(16 d log
( 4 log (ogg)))))))
)) + +1)
( 4llog(8n)) (4log(8nd) )
8
(L + 1)
- 2og
Os
8
(8 (ga))
(1 44 log(8nd)
2
((
(#loss ))
(
5 4 log(8nd)
s 3 log
log log
8²
2 log(Snd)
S
log(8nd)
where we used that [zo] - 2 (l)((x) for x > 5, and the last line is obtained by 8d/0s s 8nd and 2r-log log(1/x) S vz for I E (0, 1).
The base case 1 = 0 The initial set So = ((i1.1))..... j2 constructed by picking 2 entries uniformly at random (with replacement) from [n] x [d), as described in Line in Algorithm 1. In the context of Lemma D.2, the parameter a reduces to 0, since we consider matrix M contains least On- entries such that Daul 2 h. Then, the random variables
[n] for the proof, and s, are such that ( > h. Consequently, the
x (0) = 1 1(D 1 h), == 1...,,, 24
are i..d. Bernoulli random variables with p(X, (0) 1) 2 0g. In particular, we have
2
(4log(8nd)
(4
E
X
(0)
2 2 16 log
d
6
1=U
Applying the second inequality in Lemma I.1 (a standard Chernoff bound for Bernoulli distributions), we obtain:
Σ
x!")
S Slog
4 log 8rd))
)
S P
x S (1)
S sexp
(- _140)
s 4 (lg(8nd))
5
2
8
t=0
1=0
So we have
4log(8nd)
(llg(88d))
UUo| =
Σ x (0)
8 log
|So1
L+3 log
with probability at least
5 Toog(Snd]
Induction step: from to + 1
Consider the event & defined as
Uk
4 (log((nd)
>
2 I.+3 log
A k 0,1,..,,
[&
We want show
5 4log(8nd)
P
( 21 (1+1)
P 2 1- (1+2)
(log(8nd))
Note that E C εt, showing
5
2 )
P (E
{1) 2
(4lo((8nd)
16

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
suffices conclude
)) ( 1 (1-
2
8
(((+1) P (Er+1 (&)= 2
1 - (1 11+1)
(loog(nd))
4 log( (8n))
5
2
2 -1- (1+2
4 (log(8nd)
When we condition on the event ετ, this implies the condition
(llo(8nd)
|vil 2 2 2 log
Recall that in line 5 of Algorithm first sample
Xi.! :......... x( Lid Vi Xijs
(1)
x
(1+ta) wiid Vad
for each (i,j) E Sy and store
T++1
D
(a)
(m)
T+
u=1
Since we assumed that x - Mas E SG(L) and (u) - M1. E SG((). this implies
T++1
x(u) ig
- x Dis) E SSG(2++1)
and we obtain
T111
P (PDrs - Dis 2 2/2 =
Σ
((()) x Dis)) 2 T-17/2
s eexp
=: Pt
(8)
16
1==1
and likewise
IP Dass Di.5 2 2//2) s
For (i,j) E U1, this implies that
IP ((rss) S h2-h-11- (1+1/2 p
So we can construct i.i.d. Bernoulli random variables Big with
P(Bij = 1)
and
Dis S h (1+1/2)
Bij =1
for (1.j) E U.. By Lemma I.1 it follows (by letting k 2pr - 1)
P Σ (K))E,,
Bij 2 11//2 |U =1 exp (mpmn (1 + x)pmn k:)
log(1/pt) llog(2)
exp
1/2 - pt
2
1/2 2xp(-71472/100 - 7+172/116 - (
exp
2
exp(
22
17

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
The last inequality follows, since assumed
T 2 516-22 2
12
v2
2 128 2
L/72
such that
T
21+1
21+1
7+ =
22--++1
L
2
32
72
V
2
2 16
77
(by [x] 2 x/2 for x 2 1), from where we can conclude
74112/16-
log(2)
1/2 exp( (16)
< -21-2
2
for a 2 0. For
4log(8nd)
(Aloo((8rc))
17 2 1.+3 2-++3 1 log
2 1+2 -2-1+2 log
8
8
this implies
Un = n1
8
Σ
Bag 2 U1//2|
4 (8ng)
and therefore
8
P
Σ
Bis 2 11/1/21 & (1)
(9)
4 4log(8nd) (8nd)
(KJ))
Next, define
= = {(i,5) E Ss: IDisl < h (1+ 11}
Note that S4+1 \ U1+1 S Vi. if
V/1 < 1 (Alog(8nd)
this implies
10+1|
|1t1| 18 AU+1l
> |5t11 Vil
4 log (8nd)
|8 2 2-L+31 log
4 1log(8nnl)
(1 - 2- 2-1+2 |St+1 log
5
(loo (8nd)
2 2- log
(10)
since we have T. 2 logz(16) = 4. Therefore, consider the nontrivial case
(4log(Snd)
Vii 2 2- L+3 1+31 |
Like before, we have from (8) that
IP (D..)) 2 h (1+ 1/2)) 1 Pt
for (i.j) E V. Note that we can again define Bernoulli random variables Ci.y with
P(C,, = 1) = Pt
18

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
and
P
112)/2)
Cis
for all (i,j) E V.. We can again show that conditional
[Vi]
with
4 4log(8nd)
77 2 2 L+3
S log
8
it holds
Σ (UIE
Ois 2 112
(II)
with probability
8 (8nd)
Now if A the median of the Di.j- (1, E St, it is either A < - -1+ 1/2)y or Σ h - (1 1/2)y. the case
A (1 + 1/2)y, the bound (9) tells us that U441 contains least half of the indices of Ug, other words,
U441 |8
U
Up
2
2|St+1l
S
with probability at least 1 1-6 In the case 2 h - (1 + 1/2)>, we either directly conclude the induction step from (10), or 1)y is less than half the number of arms in Vi,
we know from (11) that the number of (i,j) E S1+1 with Di,5l S and in particular,
U
V7
V4 S
21
2|5 =
|S
S
with probability at least 1 (Togg(saa)
[Tog(Snd)
Combining both cases yields the claim.
E. Analysis of Algorithm 2
Using the results of Lemma D.I, we can now determine theoretical guarantees for Algorithm 2, CR(Ó, ro). We present the individual guarantees offered by Algorithm 2 in the following proposition.
Proposition E.1. Let 8 E 1/e). Then, with probubility larger than 1 - 8, Algorithm 2- CR(6, ro) -returns an index ris such that it holds that Mr.. # Mro.. and moreover the total budget is upper bounded by
( .d
(1A) + /
Č E.log
where Č is a logarithmic factor smaller than
C (log (og((1))) v 1)a log(dn)) loogd)(log, log (og(1/A2 (s-)) V
with numerical constant C and log, (x) log(æ for E.
Proof of Proposition E.I. Consider [d] and & > 1 minimal, such that for
16 d Os
16 log (md)
L = logz
log
it holds
516 1,324
V v2 L <
(12)
and
log(1/8) + log log 11442))
3714
V 2
(13)
A
The proof consists of three parts:
19

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
1. csH(ro: [n], L, 2%) returns (r1,.) with |Drg 2 A /2, with probability at least 8/2,
2. for Dra 2 (a) /2, if we sample
x ro.s
x x
hid.
and X A......
X(22) widd. Vord
Vrout
it holds with probability of at least 1
8
that
0.3K
2
X11)
A-3
2
ri
you!
> 2
log
0.158
t=1
3. for any 2 1, if Diy' = 0 and we sample
x
ro.
x (22
Lid.
Prouf
and
x
((24)) 'nj'
wiid
it holds with probability of at least 1
0.3k that
2
4
hrr
2
(
X Yow
V 2
log
0.156
From point 1 and one can conclude that Algorithm terminates in the th step of the h iteration at the latest with probability at least 5/2 5/0.3k3. If it has not terminated before, by point we obtain line 4 (r1,5) with [Drisl 2 A /2 and by point that for such (ri,j), the algorithm terminates in line 6, returning ri.
the algorithm terminates for some k' or the tthh round, but for some other T/, by line this means that the algorithm returns some such that for some j' holds
(1)
4
log
A-33
2
You"
2
0.156
So point 3 implies for each iteration k and each L' we iterate over, that we do not return an index with M,. Mr with probability at least 1 - 6/0.3k.3
So by the union bound, Algorithm 2 returns 11 with Mr.... # M with probability at least
0.3 7
1- 8/2
Σ
Σ IST.T Tima
8/(0.3 21- 8/2 8. 0.3
2 1
5/2
8 6
k
6
MS
121
L22 52
So we are left with proving the three points.
Proof of
By Lemma D.1 and inequality (12), calling CSH(ro. [m], L, L,24) in line 4 of Algorithm 2 yields a pair (r1.5)
with Drual 2 //) with probability at least 1 - 5/2.
Proof of 2 Note that for
Drs ==
(t)
x(1)
(14)
Fi
roof
by an application of Hoeffding's inequality we know
4
A-3
4
A3
Dm E Dnu
log
Drij +
+1
log
(15)
2
0.155
2
0.156
20

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
with probability of least 0.38/k.. Note that from inequality (13) we know by the monotonicity of log log(z) /2 for
e² that
16
log
k-3
16
log(1/8) + 3og log(2") + log log(2)
+ log(20/3)
- 80
log(1/6) + log log (2*)
24
0.155
2*
2
want to prove the bound
16
k-3
log
S A
(1)/4
(16)
2
0.158
Let us first consider the case (a) 2 1/e. We can bound
log 1/6) + log 1og(2*)
logí 1/0) + log(2*)
80
I 80
2
2
1og(1/6) + looo (())) log( (4))
80
27-0
2 A²
2 10g(1 + log log( (2 (1))
s 80
2 A
From inequality (12), know
2 A 2 3714 (o141)))118))
and we can therefore use that æ + log(x)/ x is decreasing for 2 to obtain
log(1/0) + log )2
2 logg(1/6) + log(3714 (1g)))
80
80
2
3714 log (1/6)
3 + log(3314))
80
2 - 2,)/4
3714
Next, consider the case 1/) S 1/e. Then we know from inequality(13) that
log(1/0) + log log (1g(1/A)))
2 2 3714
A (
Because x + log ( x is decreasing for x 2 e², we can bound
(og(1/A?)))
log(1/8) + log log
3714
log (1/8) + log (2g)
80
80
2
3714 log((1/) + log log (1/4 (s)
For a, b 2 it holds log log(ab) ab) I log(2) + log log(a) + log log(b), can bound
1og(1/5) + log log 1/4 (o))
log log
3714
A (8)
< log(() + log log (1/A),) + log log (3714 (log(1/8) + log log (1)42,)))
< <log(2 3714) + 2 2og log (1/42)) + +log(1/8)
This allows us to bound
(2+ + log(2 3714)) log (1/6)) + log log (1/4?.)
80 log(1/8) + log log(2*)
80
A
2k
3714
[oog( (1/5) + log log (1/2()))
80(2 + log(2 3714))
A - A
3714
21

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
For Drai 2 A /2, have with high probability according (15) that
Dr..d
4
log
A-3
2
0.158
Proof 3 Analogously to (14) and (15) we can use Hoeffding's ' inequality to show that for
Di.5
x
2 1=1
holds
4
A-3 0.150
log
2
with probability at least
8
0.3
Bounding the budget:
First, we can bound
16 (log(8nd)
Lmax S 2log
16nd log
8
16 166og((nd))
< 10 10
nd log
16 log 8nd)
< 10 log(ndd) + log log
< 10 (log(nd) log ((nd)* + log (1/6))
< 70 (log(nd) + log log
At the same time, have that
16 (6log(Snd)
2 - 32 log
0s
5
$ 32 0s
(log log(nd) + 1og(64/8)
d
< 192
(loglo((nd) + log(1 (1/8)
0s
So, if we define C' = 156 703 192 and K* the minimal 2 such that
(log(nd) + log log(1 (1/)) log(nd) + log(1/8))d As (8)
26+1 2 C' min sE[d]
d(log(nd) + log log (Ig) log(nd) + log log(1/6)) log(1/8) + log log (og(1/4))))
(1)
Os
Os
A
we can see that by (12) and (13) Algorithm 2 terminates and returns r such that My.... # M with a probability of least 1 5. Moreover, on this event of high probability, the algorithm terminates after at most
Σ
Σ
2. 2++1 S 8Tmaax2 2
k= LEl1LLSmaa L-21-22--1
(log(nd) + log log(1 1og(1/8)) (11g)) log(d)) + log(1/8))d
C Tmmax min sEld
As A
d(log(nd) log (og(115)) (log log(nd) + log(1/8)) + Os
d log(1/6) + log, log(1/4?,))
As
A?
22

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
by minimality of kt, where C' is some numerical constant that might change. To obtain the claimed upper bound, note that by (2) know 1/s* A (s*) I (og(2d)/||A]) and therefore
(log(nd) + log 0 (x)
(og( + log(1 (1)))
Limax min sE|d]
d(log(nd) + log log( log(1/0) (18)) log(nd) + (og((16))
log(1/6) + log, log( (1/4
As
As
+ 1
S (log((() + log (P)((1))) + log(1/0)(log, log(1/A3) V1)
||
8*
where C > O is some numerical constant. Reassembling the logarithmic terms yields the claim.
F. Analysis of Algorithm
Now, we prove the correctness and we upper bound the budget of Algorithm 3.
Proposition F.1. Let 8 E (0, 1/e), let ri [n] such that Mr + Mr.... Then Algorithm CBC(O, -returns g (fixing arbitrary g(ro) = 0), with probability at least 1 5, with budget of most
( +1
( 1
+1 +1)]
min sEid]
A2
where Ć a logarithmic factor smaller than
C --llg log log(1/0) v 1)* -lo(dd) log log (1/4
with numerical constant C O, and 3 [d/n] A Kj E [d] A OH|
The proof of Proposition F. does not differ much from the proof of Proposition E. Again, have bound the time where CSH returns index pair for which the stopping condition is fulfilled with high probability. The main difference is, that we also need guarantee for correct clustering using these indices, which also leads to a change of the stopping rule.
Proof. Consider E [d] and l E N, k > logz(n) minimal, such that for
16 d
16 (66lo((d)
L =
loga
log
8
it holds
L324
516
V 2 L < 2
(17)
A
and
(oog(100) + 1og, log (1/4/a)) + logn) nn
34423
V 2n < 2
(18)
A
The proof relies the two following facts:
1. csH(ro. [n], L, 2 returns (F1.5) with Driil 2 A /2, with probability at least 8/2.
2. we have that jointly for all iterations K' and < Imax with 2 2 for some E [d] (chosen each time in line 4) and all 1 < i n, when we draw
x :..;;
x(12 /nJ) widd Vroi3 and x!1) i roul
x((2*'/n) /nj) wid Vs
iy
23

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
holds
1a
/nl
nk:33
x
DeS)) $ $14.1 $4.122
12"h 14.112 122 /m/loo log
1.
0.156
uniformly with probability at least 8/2.
Point 1 is direct consequence of Lemma D.1 and (17). Point 2 follows directly from Hoeffding's inequality and union bound over all k 2 1. L I Lmax such that L2 < 2 and E [n]. Indeed, each inequality for itself holds with probability at least 1 - 0.35/nk ////kk" so the intersection must hold with probability of at least
Σ R21 ISLS Leaax 1.2 1.2g22 g2
Σ
Σ
0.36/nk/3 2 1 0.30
Σ R21
2 1 - 1
k
We will prove that Algorithm 3 terminates at the latest in the 1hh round of the 1tth iteration and clusters correctly with probability at least 1 6, namely on the intersection of the high probability events of point and 2 which we will call Eehe-
Algorithm 3 terminates at the latest in the 4th iteration Assume we are on Écbe- By point 1, we know that at round of iteration it holds [Dr..sl 2 | /2 for j obtained line We want to prove
64
r 0.155
log
S A 2
(19)
Note that by (18), it holds
64
n
128n
(log n + 3lg log 2 + log(20/3)) + loo((16))) < 640n log(1/8) + log + log log 2
log
2
0.158
2
2
Again, consider first the case (0) 1/e. In this case, know from (18) that
34423 (log(1/5) log n) S 2 2
We can use that log(æ)/zr is decreasing for r 2 e and obtain
640n log(1/6) log n + log log(2*)
log( (0/(118)_) + logn n + log(2*)
< 640n
2
2
log(1/8) + log + -og llog(
640n
2º12
llg((1)) + log n + log 2
2
< 640n
(x)
A (8)
2
640
2 log(11/) log + log (34423n(log(L///) + log A
34423
log (1(11/ 1/8) logn
640
2 log(1/8) + 2 n + log 34423 + log(log(1/8) + log n)
A2
34423
log(1/)) + logn
640 (3 + 1og(34423))
A
S A 2
34423
This proves (19) the case 23,) 2 l/e.
24

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Consider (e) 2 1/e. Then, by (18), we know
log(1/6) log n + log log (1/4/.)
2
34423n
We can apply that x log (2) is decreasing for 2 e² and obtain
log(1/6) + log n + log log 344233 lox(1/6)+ n bo 1/A4)))
640n log(1/6) + log n
log log 24
640
(1)
A
2
34423
log(1/6) logn n + loglog (1/2
Note, that
log(1/8) + log + log log (1/A
log log
34423n
A?
(1/4/)) + log log 34423n (log(1/0) + log + log log (1/4 ))
< <log(2) + log log
< <log(2 34423) + log log (1/4):) + log(n) + log (log (1g( + log + loglog (1/4
(log(2 34423) + 1) log(1 ( /6) + 2log log (1/4 + log(n)
where we used log log(a b) < 1o)(2) + log log(a) + log (b) for a, 2 e. Thus, it holds
640n log(1/0) + log n + log log(2*)
640
(2 + log(2 34423)) log
log(1/0) (1/8) + 2 log n + 2 2og log (1/A7))
2
34423
log(1/6) log + log log(1/A
640(2 + 1og(2-33 (44423)
- A / (8)
34423
which proves (19).
Incquality (19) implies
n1k-3
Draj 2
/2
4.
log
2k
0.155
72
and by points and 2 have guarantee that
Dr..
23
4
log
nk33
24
0.158
By line 8 of Algorithm 3, this is sufficient for the algorithm to terminate after the T, round of iteration k.
Algorithm 3 clusters correctly Consider the first & E N with k'' > loog (n) such that for the samples
(()) You
(122 /nl) wiid Vroit and x x(1) x(1221/n (nJ) iidd Vnd rasl
rid
we have that
gh' /n
n
((t) ra.j
>3
log
2 /n]
rı.j
2
0.155
25

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Then by line 8, know that after completing the iteration Algorithm; terminates. From point we know that Eabe holds
4
nk 0.156
D >
log
2 n
So if for each i 2 2 we sample again
x
YOU
(1)
X (12%
/nJ)
wild Var
and X!" ..... 11(22 /n.)
wlid Vis
Pond
then for the averages holds again by point 2 that
2
1 /m]
x
4
log
r2k
22
2
0.155
if and only if Di, * O. So on febe, the labeling in line 12 yields to a perfect clustering Bounding the budget:
Similar to the proof of Theorem 1, we can bound
imax S 70(log(d) + log log log(1/)))
and
2 192 (log log + log(1/6))
So again by defining C = 156 703. 192 and letting k" being minimal such that
(log log (og(1 ( (log log + log(1/5))c
2
min sE[d]
(logd log (10)) (log log log((10))
$
(lo((1/)) + log, log (1/47)) + log n
A (+)
we know from (17) and (18) that with probability at least budget most
Algorithm terminates and clusters correctly, spending a
Σ
2. 2.2 < 8Lmmax2 2
S 1.22 52k+1
(
(logd d + log log(1) (
3 (log log + log(1/8))
+1 d
C'ool d + log log(1/5)) min
sE|d]
(og((16) + log, log 11/4/²)
+ loog n
+
+1
m
A (5)
where C is a numerical constant. Inserting á in the right hand side and gathering the logarithmic terms like in the proof of Proposition E.1 yields the claim.
26

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
G. Proof of Theorem C.1 on the extension to K ~>> 2
Come-back on sub-routines CR and CBC. We can reformulate Proposition E.1 in the following corollary.
Corollary G.1. Let (0,1/e), r e [n] and G C [n]. There exist an event of probability larger than 1 such that
1. M,, Mr. Vi E G, then CR(Ó, r, G) does not stop.
2. if G such that M., # My then CR(6, r, G) returns an item such that Mr, # Ms.., with budget T smaller than
Öloog ( min
d
1 122 + +11
Ex Masl hi]
with Ć poly-logarittmii term defined in Proposition E.I.
Proposition F.I can be formulated as follows:
Corollary G.2. Let E (0,1/e), r E [m], E [n]] and G C [n]. Assume that M,. + M,,,, then there exists an event of probability larger than 5 such that CBC(,, r,8; G) oulputs a partition of G, G = RUS S with budget T such that
1. G M., Mr c and E G:; M..- M.. cs
2. the budget I is smaller than
d [d] :|MrJ Masl > hHll +n) ) [1ISE
(1) h22 +1)
Öllog
with Ò poly-logarithmie term defined in Proposition F.I.
Proof of Theorem C.I. We use the notation from the pseudo-code Algorithm 5 and from Appendix C. The correction of the algorithm is a direct consequence of the following lemma, which states that, with high probability, all epochs behave as expected. The bound on the total budget given in Theorem C.1 follows directly by summing the sample complexities of all CR and CBC calls across the K epochs. These individual complexities are provided in Corollaries G. and G.2.
Lemma G.3. There exists an event of probability larger than 1 - such that for each epoch & e & K -1
1. Epoch terminates using a finite budget.
2. The item Te+1 selected is new representative: Mr $
3. For all k E + 1), (i [n]; M., -r... G(etz)
Let denote the event that, for epochs & = 1,... K 1, each call CR and CBC behaves correctly - i.e. satisfies Points and of Corollaries G.I and G.2. In epoch e, the algorithm makes calls CR and calls to CBC, each with confidence level 8_ e(K-1) By union bound over all calls across all epochs, the probability of event & is at least 1 5.
We prove by induction on e E [K- - 1] that the three points Lemma G.3 hold on E.
Initially, we have trivial partition ((1) = [m]] and representative r is arbitrarily selected. Points 1-3 trivially hold 1=
Assume that, at epoch (ri,..., re) are representatives from e distinct clusters, and for each k E [e]. the set g contains all items with mean Mr....
Since e < K. there exists least one cluster not yet represented, and therefore, there exists some E G(e) and some E [e] such that Mi,, A Mr.... On event E, CR( rx; G( will return item in finite time, and Line 5 of the corresponding algorithm terminates. Denote Tet1 the item returned from this call. Then, by Corollary G.I, we know that M, M, * M
Moreover, for K' + k. G(e) contains all items with mean My so that M,. 1. & {Mr...... Mr.. J. and Point 2 also holds for the e-th epoch. Since all calls terminate in finite time on E, Point also holds.
27

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Now, for each & E [e], Mra1i. + Mr so that on &, the partition of G into two groups G%+1 U feg+! will perfectly separate the items with mean Mrs. and Mr By assumption, the partial cluster G%. already contains all items with mean Mr..", so Ei E [x]] M,, = Mrg..} C Gg. Similarly, as Gi,.... Gee) is a partition of [n]] any item with mean Mr will be set in one of the sets feg so that (i E [n]: Mr.- = Mr-1r C U Ret Ge+1 epoch e,
6+11 Thus, Point 3 also holds for
By induction, all three points in the lemma hold for all e E [K - 1] on event &, which concludes the proof.
H. Proof of the lower bounds
The lower bound in Theorem 4.1 consists of two terms, which we prove separately, In the proofs, use Tig as the number of time a procedure selects the pair (i. E [n] [d].
Lemma H.1. The (1 (1-00 1--))nnuntilee of the budget of any 6-PAC algorithm A is bounded follows
2d
1 66
max FO.A PEEper(M) (M)
T
log
> 8
(20)
0
Proof of Lemma H.1. Fix algorithm A, and let (M) denote the set of Gaussian environments obtained by permuting the rows and columns of M. For the purpose of the proof, we define Pa, 7 as the probability distribution induced by the interaction between algorithm A and the environment defined in (4), where a and are permutations of the rows and columns of M, respectively.
We permute the rows of M to reflect the fact that the learner has no access to the label vector g. In addition, we permute the columns of M to account for the algorithm's 's ignorance of the structure of the gap vector A, in particular, the identity of the feature with the largest gap.
Without loss of generality, assume that μ = 0 and μ A, with the group associated with mean vector A being the smaller of the two.
Define X as the smallest integer such that for all permutations a and 7 of 1, 1,...,, n and 1,...,,, d, respectively, the following inequality holds:
Porr (T > x) <
(21)
Our goal is derive a lower bound x. Intuitively, we show that for small X, there exists permutation of M for which it is impossible to detect nonzero entry.
Introduce Po as the probability distribution induced by A. in an environment where all items belong to a single cluster, i.c., each X, ~ (O, 1). We will prove that under this "null" environment, the algorithm A requires more than x samples with probability least 1 -2.
To this end, consider an environment v(g, μ) consisting of two clusters with means 0 and μ., and let μ - O. Since A is 6-PAC, there exist two distinct partitions 9 # g' and an event A such that
P Pulan) (A,T < x) + F. (n ( 28 28
For example, take g(1) .(2) 1, and g'(1) = 0, g2( the event (0(1) ((2)} suffices. Then, conditionally
T & x. P. (P.(g.)) and P , converge in total variation to 1. + O. consider an environment v(g, j)) consisting of two clusters with means 0 and jr, and let μ + 0.
Po(T < x) < 25
(22)
Applying the Bretagnolle Hubeerrlleeeuerrrreeeee Huber inequality (see Lattimore & Szepesvári. 2020, Thm. 14.2), and combining (21) and (22), we obtain
exp KL, < Po x + P., x) < 35
which implies
1
log
< (L,,o,
(23)
66
28

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Next, using the decomposition of KL divergence for bandit models (see Lattimore & Szepesvári, 2020, Lemma. 15.1), and the Gaussian assumption, we have
A2 Bol Bo(Tiyllatt(0) a(a(1))=1
[L, Pa.))
Σ BolTi,y KL(P))
Pott)
Σ
-()
(24)
2
Averaging both sides of (23) over all permutations o, and using Equations (23) and (24), we get
log
1 n! d!
Σ
A
(25)
66
2
Gr
Now, observe that each element in í {I....,m) the multi-set (o()) (resp. {r(1)rr, so that
n (resp. j E fl.....
.....,d)) d)) appears exactly (n 1)! (resp. (d 1)!) times in
1 0,T 4.
ΣΣ>
Bu T o((()))
47
(n 1)1 (d 1)!
Bu
Tig o(x)=1
A7 2
n!
2
n!
|
1 g(k) =1
E [T)
2d
kE|m]
Since the group associated with A is the smallest, # ExEin) l((k== 0. Using a modified algorithm A' that stops at T A X, we can bound Bo[T] < X. Finally, it follows that:
2d
x
>
log
/||
2
66
Since x is the maximum all permuted environments constructed with M of the (1 -0-unnte of the budget, this inequality concludes the proof of Lemma H.l.
Lemma H.2. Assume that 1/2. If A is 8-PAC for the clustering problem, then for any environment
2(n
2)
EA
log 2.46
(26)
A
where (1)) = maxjeld AA
Proof of Theorem 4.1. Observe that Lemma H.2 does not directly provide high-probability lower bound on the budget. We now show how the expectation bound given by Lemma H.2 implies lower bound on the (1 -u-qunte of the budget.
Let A be any 8-PAC algorithm. Assume, by contradiction, that
2(n 2)
IP Pv..A
T>
log
8.
A
4.85
We modify A such that it stops time
2(n
2)
T T
log
A
4.86
A reaches time 2(n-2) log (1.38) it stops sampling and outputs an error. The resulting algorithm A' is 25-PAC, with a
budget satisfying
2(n 2(n-2)
[T, &
log
A (1)
2.48
However, this contradicts Lemma H.2, applied to 4' with = 25. Thus, we have P Pr,A
T>
2(n-2) log 4.86
28.
29

---

Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Proof of Lemma H.2. Let A be any 6-PAC algorithm for the clustering problem, and consider the matrix M that parametrizes the Gaussian environment We fix for all environments in this proof that g(1) = 0 and g(2) 1. It implies intuitively that we assume that the algorithm knows one item from each group via oracle.
For the Gaussian environment v, let j.j E [n]] x [d]. The observations follow a Gaussian distribution:
[N
if (() = 0, ((IA,, 1), if g() = 1
We aim to show that with budget smaller than from another environment where one item from v has been switched to the other group. We construct now this alternative environment.
en (1g(1/6), a 8-PAC algorithm cannot distinguish the environment (11
For any & E {3....,m), n) define g* as the vector of labels obtained from g by flipping the label of row k, and let D² denote the corresponding Gaussian environment. The lower bound follows from the information-theoreti cost of distinguishing from any D
To handle multiple environments, let Pa+ (resp. Pg) denote the probability distribution induced by the interaction between algorithm A and environment nx (resp. v/).
For any k E (3..... n), note that enviromments v and n differ only on row k. By decomposing the KI. divergence and using the Gaussian KL. formula, we have:
2
KL P.tt
Σ Eg Tu.
Eg
J
11
(27)
2
where we use that [م)) maxye[4] A4yl, and Tk., denotes the number of samples taken from row is and column j. Since is 8-PAC for the clustering task, have:
(0 + g) E
P (g + <
Now, 5 E (0,1/2), by the monotonicity of the binary KL divergence kl, and using the data- processooessing inequality, we obtain:
kl 1 - 8) < kl (P g+), P g²1) KL g. Pgt)
(28)
Combining Equation (27) and Equation (28), and summing over A: E (3....,n}
n). we get:
Eg [ ())
(n 2) kl 1 8) <
E. [
(29)
2
2
A=
Finally, Lemma H.2 follows by combining Equation (29) with the inequality kl 1 - 8) > log
1
2.46
I. Technical Results
Lemma I.1 (Chernoff- Bound for Binomial random variables). For 1,..., n, consider X1, X2,..., Xn wiid Bern(p) with p (0. denote μ == np and consider >> We have
enH
P
Σ x; 2 (1+ 1=1
S (1 x)(+)))a
If K E (0, 1), we also have
x2pp
P
Σ
x, (1 (1=)) x)
S eexp
30


Reviews:
[{"review_id": "W6gLkIciYD", "reviewer": "Reviewer_z8W5", "summary": "This paper considers the problem of classifying $ n $ items into two categories based on bandit feedback. Each item is associated with $ d $ features that vary depending on the class it belongs to. In each observation, an item and a feature are selected, and the corresponding feature value is observed with noise. Under this setting, the paper focuses on the *fixed confidence* regime, evaluating the minimum number $T$ of observations required to achieve a given accuracy level. It proposes an algorithm along with an upper bound and a nearly matching lower bound. Additionally, the proposed algorithm is evaluated through numerical experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank you for your time and effort in reviewing our paper. We corrected the small typo in Section 6 that you pointed out. Besides this, we would like to provide more insights regarding the two limitations you mentioned.\n\n- **Discussion on the optimal trade-off $H$ (Eq. (3)) for general $\\Delta$**\n    \n    In Corollary 3.2, we prove that our procedure is optimal when the gap vector is $s$-sparse with a constant magnitude $h$.  You can find a discussion on the intuitions behind $H$ on this sparse setting in the rebuttal to reviewer RdVc. For a general gap vector $\\Delta$, we have good reasons to think that understanding the optimality of this trade-off for this simple example allows us to understand (at least intuitively) the optimality for general vectors. \n    \n    Our upper bound is constituted of two terms. A first term $\\frac{d\\log(1/\\delta)}{\\theta||\\Delta||^2}$, we proved that this  is optimal (see Thm 4.1) for the sub-problem of identifying an item in the second group. The second term is defined as this minimum  $\\min_{s\\in[d]} \\left[\\frac{d}{s\\Delta_{(s)}^2} + \\frac{n}{\\Delta_{(s)}^2}\\right] \\log(1/\\delta)$. Indeed, the term $\\frac{n}{\\Delta_{(s)}^2} \\log(1/\\delta)$ is the price for clustering if we use a feature with a gap $|\\Delta_{(s)}|$ while $\\frac{d}{s\\Delta_{(s)}^2}\\log(1/\\delta)$ corresponds to the price for selecting a feature with a magnitude at least $|\\Delta_{(s)}|$. Define the effective sparsity $s^*$ for which the minimum holds, and define the effective magnitude as $\\Delta_{(s^*)}$. Intuitively, we can argue that entries significantly larger than $\\Delta_{(s^*)}$ are too rare to be detected (otherwise, $s^*$ would be smaller), and entries much smaller than $\\Delta_{(s^*)}$ are too weak to be used for classification. Our insight is that the problem is as hard as if the gap vector were $s^*$-sparse with a constant magnitude $\\Delta_{(s^*)}$, a setting where we have matching lower and upper bounds (see corollary 3.2), leading to our complexity. \n\n    We believe that proving formally this optimality is difficult in general. We have currently a sketch of proof for which we reduce the problem into a problem of good-arm identification -- we prove that each algorithm that solves the problem should be able to identify a feature larger (up to a constant) than $\\Delta_{(s^*)}$ in the gap-vector. However, we would then need an instance-dependent lower bound for such problem. Unfortunately, contrary to the problem of best-arm identification, such a lower bound does not exist yet in the literature (see [Zhao et al.(2023), Chaudhuri et Kalyanakrishnan(2019),Katz-Samuels et Jamieson(2020),  De Heide et al.(2021)]. We are currently working on such lower bound, we believe that this would be a more valuable contribution in a separate paper fully dedicated to good-arm identification. \n    \n - **Extension to $K>2$ clusters**\n\n     In this manuscript, we focused on the case of two groups because it serves as an informative baseline for analyzing the optimal trade-off in clustering with bandit feedback. This problem had not been studied before, even in the binary setting. Naturally, extending the approach to $K>2$ groups is an important and practical direction. We will add to the appendix an algorithm that extends our method to the general case where $K>2$, together with an analysis of its (non-optimal) budget. However, as you observed, obtaining the optimal dependency with respect to $K$ is significantly more challenging. We invite you to read the detailed discussion on this point in our response to Reviewer RdCv.", "claims_and_evidence": "The main contributions of this paper are theoretical, and all appear to be supported by correct proofs.", "methods_and_evaluation_criteria": "The evaluation metric used in this paper is natural and reasonable.", "theoretical_claims": "I have briefly checked the proofs of Theorem 3.1 and Theorem 4.1.\nNo particular issues were found.", "experimental_designs_or_analyses": "I was not able to spend much time verifying the correctness of the numerical experiments.", "relation_to_broader_scientific_literature": "The problem setting considered in this paper is a special case of the problem studied in (Ariu et al., 2024). However, to the best of my knowledge, this is the first paper to provide theoretical guarantees and analysis for this type of problem.", "essential_references_not_discussed": "I am not aware of any particular relevant literature not discussed.", "other_strengths_and_weaknesses": "As mentioned in Section 4, one limitation is that the matching upper and lower bounds are restricted to specific cases of $ \\Delta $. Additionally, the fact that the number of groups is limited to two poses a practical constraint. While Section 6 outlines a general approach for extending the method to three or more groups, obtaining tight upper and lower bounds in such cases would likely require nontrivial further analysis. That being said, this paper serves as a strong starting point for exploring broader problem settings. Overall, the paper is written in a very clear and readable manner.", "other_comments_or_suggestions": "There seems to be an extraneous period at the end of *Extension to a larger number of groups.* in Section 6.", "questions_for_authors": "At the end of Section 4, it is stated, *\"For more general $ \\Delta $, we conjecture that the trade-off in $ H $ in (3) is optimal and unavoidable.\"* Could you provide any supporting facts or intuitions that lead to this conjecture?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uouPZkBBft", "reviewer": "Reviewer_AdRS", "summary": "This paper addresses the problem of clustering items based on bandit feedback in a sequential and adaptive setting. Each of $n$ items is characterized by a $d$-dimensional feature vector, and the items are partitioned into two unknown groups where items within the same group share the same feature vector. The learner sequentially selects an item and a feature, observes a noisy evaluation, and aims to recover the correct partition with a small number of observations.\n\nThe main contribution is the BanditClustering procedure, which operates in three steps: \n\n- Identifying two items from distinct groups\n- Finding a discriminative feature between them\n- Using this feature to cluster all items. \n\nThe authors provide non-asymptotic bounds on the budget required and prove their algorithm's optimality through matching lower bounds in certain cases. The approach leverages techniques from best arm identification (Sequential Halving) and adaptive sensing strategies.\n\nThe paper presents a theoretically sound algorithm for clustering with bandit feedback that achieves optimal sample complexity by efficiently identifying discriminative features.\n\nThe paper includes theoretical analysis characterizing the sample complexity based on the difficulty of the clustering task, which is quantified by the difference between feature vectors of the two groups. Experimental results demonstrate the advantage of their adaptive approach over uniform sampling, particularly in sparse regimes.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first would like to thank you for your time and effort in reviewing it, and for your insightful questions.  We  now overview the remarks and questions that you formulate in your review: \n- **Oversampling from row 1**\n\n  First, we would like to emphasize that improving the budget compared to non-active settings requires over-sampling certain rows, which we refer to as representatives, following [Thuot et al.(2025) \"Clustering with bandit feedback: breaking down the computation/information gap\"]. This step is crucial for accurately estimating the means $\\mu_1$ and $\\mu_2$ and, ultimately, for accelerating the clustering task. This is not, per se, a weakness of our procedure but rather an essential aspect for achieving order-wise budget optimality (up to logarithmic factors). Notably, we chose row 1 as the first representative, but by symmetry, any randomly selected row could have served the same purpose.\n\n  Second, it may indeed be possible to slightly reduce the budget allocated to the first row by reusing previously sampled data.  For instance, if an index pair $(i,j)$ is identified such that $|\\mu_{ij}-\\mu_{1j}|$ is large, we can allocate $c\\frac{n}{\\hat{\\Delta}^2}\\log(n/\\delta)$ samples to estimate $\\mu_{1j}$ and $\\mu_{ij}$ once and for all. These estimates could then be reused for classifying the remaining rows, reducing the confidence bounds required for perfect classification by a constant factor. However, applying such refinements in other parts of the algorithm would significantly reduce its transparency, both in terms of implementation and theoretical analysis. Moreover, the resulting improvement in the budget would be limited to a factor 2. For the final version, we will keep our method as it is, but we will clarify our motivations, and highlight potential ways to improve numerical constants.\n- **Extension to $K>2$ clusters**\n\n  In this manuscript, we focused on the case of two groups because it serves as an informative baseline for analyzing the optimal trade-off for the problem.  We will add to the appendix an algorithm that extends our method to the general case ($K>2$), together with an analysis of its budget which scales with a factor $K^2$. However, obtaining the optimal dependency with respect to $K$ is significantly more challenging. We invite you to read the detailed discussion on this point in our response to Reviewer RdCv.                               \n- **Robustness to heterogeneity within the clusters**\n\n  As mentioned page 8, our algorithm can be adapted to handle some degree of heterogeneity by appropriately adjusting certain tuning parameters. For instance, assume that we have prior knowledge that, for any feature $j\\in[d]$, the within-group variation satisfies, $\\max_{g(i)=g(i')} |\\mu_{ij}-\\mu_{i'j}|\\leqslant c\\min_{g(i) \\ne g(i')} |\\mu_{ij}-\\mu_{i'j}|$. If $c<1/4$, our algorithm remains correct -- searching a single discriminative feature is still meaningful and enables classification. However, if the within-group heterogeneity is comparable to the inter-group differences in some features, our method could fail, and further investigation would be required. Observe also that if $c=1/2$, the problem is not identifiable anymore. We will expand on this discussion in the final version. \n- **Discussion on the optimal trade-off $H$**\n\n    We appreciate your suggestion and will provide more intuition about the complexity term $H$ (see Eq. (3)), along with a discussion on why we believe it is optimal. Also, we will base our discussion, as for the upper bound, on the simple example of sparse vectors.You can find a discussion on the intuitions about $H$ in the sparse setting in the rebuttal of review RdVc, and a discussion on its optimality for general values of $\\Delta$ in the rebuttal of review z8W5.\n- **Budget comparison with the literature**\n\n  We acknowledge that further quantitative comparisons with other approaches and existing literature are missing. We will add this discussion in the final version, we will in particular discuss about the benefice of our model in high dimension settings. Thank you for pointing this out.\n- **Real-world applications**\n\n  While we described in the introduction that image labeling might be a very natural application for our algorithm, it seems challenging to process existing datasets such that we obtain data for the bandit framework. We agree that the paper would benefit from real-world experiments, but in view of the fact that this work is intended to focus on an in-depth theoretical investigation, we decided to only consider synthetical data. A possibility could be to setup experiments using crowdsourcing platforms or a group of experts. One could use image data (as done in [Herde, Marek, et al. \"dopanim: A Dataset of Doppelganger Animals with Noisy Annotations from Multiple Humans.\" Advances in Neural Information Processing Systems 37 (2024): 51085-51117.]), but ask experts about specific features of depicted animals instead of the concrete class.", "claims_and_evidence": "The main claims of the paper are supported by convincing theoretical and empirical evidence:\n\n- The upper bound on sample complexity (Theorem 3.1) is rigorously proven and demonstrates how the algorithm adapts to the sparsity pattern of the gap vector.\n\n- The lower bounds (Theorem 4.1) establish the optimality of the approach in certain regimes, particularly when the gap vector takes only two values.\n\n- The experimental results in Section 5 supports the theoretical findings, showing the algorithm's superior performance compared to uniform sampling in sparse regimes.\n\nThe claims about the algorithm's adaptivity to unknown structures are well-supported by the theoretical analysis, which shows how the budget scales with problem-dependent parameters without requiring prior knowledge of these parameters.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are generally sound, though there might be room for improving sample efficiency:\n\n- The three stage approach with primary focus on identifying a single feature goes well with the narration of sparse feature distinction vectors. \n\n- The budget (number of observations) is an appropriate metric for evaluating efficiency in the bandit setting.\n\n- The theoretical analysis properly characterizes the algorithm's performance in terms of relevant problem parameters (gap magnitude, sparsity, balancedness).\n\nHowever, there appears to be potential inefficiency in the sampling strategy, particularly regarding samples from row 1. Maybe a better book-keeping of what samples are already present?", "theoretical_claims": "I skimmed through the details of the proof, they did appear correct. My primary focus was on :\n\n- Lemma B.1 (guarantees for CSH algorithm)\n\n- Theorem 3.1 (upper bound)\n\n- Theorem 4.1 (lower bound)\n\nThe theoretical analysis is generally sound. I noticed an issue in Section 3, where there appears to be a typo: $μ_{ij}-μ_{ij}$ should likely be $μ_{ic,j}-μ_{1,j}$ or similar?", "experimental_designs_or_analyses": "Summary of Experimental setup:\n\n- Experiment 1 examines how sparsity affects budget requirements, comparing BanditClustering against uniform sampling with K-means.\n\n- Experiment 2 studies how the budget scales with problem dimension when the sparsity is fixed.\n\nThese experiments showcase support to the theoretical claims about adaptivity to sparsity and scaling with problem dimensions. The comparison with uniform sampling is informative, demonstrating clear advantages of the adaptive approach.\n\nHowever, the experimental section is relatively brief compared to the theoretical analysis. As a proof-of-concept it works, though more detailed experiments wouldn't be a bad addition.", "relation_to_broader_scientific_literature": "The paper appropriately positions its contributions within several related research areas:\n\n- **Best arm identification literature :** The paper builds on Sequential Halving algorithms and extends these techniques to the clustering context.\n\n- **Adaptive sensing strategies :** The three phase approach is definitely a nice novel addition to the sparse sensing literature\n\n- **Dueling bandits :** The cleaver isolation of 1-d dueling bandit setup as a sub-sampler is a good addition. \n\n- **Other bandit clustering problems :** Limited impact here since the setup is of a bipartite graph kind of setup. \n\nThe authors claim their approach allows for more efficient budget allocation by focusing on the most relevant features, leading to lower observation budgets than previous methods, particularly in high-dimensional settings.", "essential_references_not_discussed": "The paper does a good job at comparing with other bandit clustering frameworks but could potentially elaborate more on the quantitative differences in sample complexity. I don't identify any critical omissions in the literature review.", "other_strengths_and_weaknesses": "**Strengths:**\nThe paper's main strengths lie in its theoretical rigor and adaptive approach, while limitations include the restricted problem setup and questions about practical applicability.\n\n- Clearly written paper with well structured arguments and explanation.\n- The paper provides a clear theoretical characterization of the sample complexity, showing how it depends on the sparsity pattern of the gap vector.\n- The algorithm is adaptive to unknown structures without requiring prior knowledge of the problem parameters.\n- The theoretical analysis is rigorous, with matching upper and lower bounds in certain regimes.\n- The three-step approach (finding representatives, identifying discriminative features, clustering) is conceptually clear and intuitive.\n- The experimental results convincingly demonstrate the advantage over uniform sampling approaches.\n\n**Weaknesses:**\n- The setup is limited to binary partitioning (just two clusters) with identical feature vectors within clusters. The scaling up of the computational complexity and regret due to more clusters is something of importance \n- The algorithm seems to oversample from row 1, raising questions about sample efficiency. The paper doesn't explore potential downstream effects or implications for regret bounds.\n- The practical impact of the theoretical findings on real-world applications is not extensively discussed.\n- The experimental section is relatively brief compared to the theoretical analysis. It would be valuable to see how the algorithm performs on a real-world dataset where the feature sparsity pattern is naturally occurring rather than artificially constructed.", "other_comments_or_suggestions": "- The paper would benefit from a more intuitive explanation of why the specific trade-offs in the algorithm design are optimal, perhaps with a simplified example.\n\n- The paper mentions budget comparison with other approaches in the introduction but doesn't provide detailed quantitative comparisons in the main text. (maybe I missed this.)", "questions_for_authors": "- Is there a way to use the samples from row 1 more efficiently? The current approach seems to involve significant oversampling from this row. Could this sampling strategy be optimized, and what would be the impact on the theoretical guarantees?\n\n- How would the algorithm perform in settings with more than two clusters? Would the approach of finding discriminative features scale well, or would the sample complexity increase significantly?\n\n- The paper focuses on the case where items within the same group have identical feature vectors. How robust is the approach to small variations within groups? Could the analysis be extended to allow for some heterogeneity is of the form that there is a linear seperator between the two groups? There is some discussion but would like to know more.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uhc8btyQJA", "reviewer": "Reviewer_RdVc", "summary": "This paper investigates the problem of clustering items via bandit feedback. The items can be partitioned into two unknown groups that share the same feature vector within each cluster. The authors propose a sequential and adaptive setting where the learner can only select one item-feature pair per round. The objective is to accurately recover the correct partition while minimizing the number of observations. The paper presents an algorithm that identifies a relevant feature for clustering by leveraging the Sequential Halving algorithm. With probability at least $1-\\delta$, the algorithm achieves accurate recovery of the partition, and the authors derive an upper bound on the required budget. Additionally, they establish an instance-dependent lower bound that is tight in certain relevant cases.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we thank you for your time and effort in reviewing our paper.  We will correct the typographical errors you identified. Below, we discuss about the different weaknesses that you identified. We will provide intuitions and thorough discussions on these points in the final version of the paper.\n- **Extension to $K>2$ clusters**\n\n  Our algorithm identifies a discriminative feature to separate two groups.  To achieve this. We fix arbitrarily a first item, and find an item from a different cluster (Algorithm 2). Then, we identify a feature that separates the two clusters well, balancing the cost of identifying such a feature with the cost of classification (Algorithm 3). We proved that this requires a budget of $H(\\mu^a-\\mu^b)\\log(1/\\delta)$ (see Thm 3.1 and Eq. (3)).\n\n  Here is a way to extend the method to $K>2$ clusters, assuming $K$ is known. We first identify $K$ representatives from different clusters, one at a time. If $k<K$ items have already been identified from $k$ different clusters, we can run $k$ calls of Algorithm 1 in parallel to identify an item whose mean vector differs from all the previously identified representatives. Repeating this operation $K$ times yields $K$ representatives. Then, we use these representatives to learn $K(K-1)/2$ discriminative features (one for each pair of representatives), ultimately classifying all items. Compared to the case where $K=2$, the total budget then scales by a factor of $K^2 \\times \\min_{k\\ne k'} H(\\mu^k-\\mu^{k'})$, where $\\mu^1,\\dots,\\mu^K$ are the mean vectors of the $K$ clusters. This approach would be order-optimal if $K$ is considered a constant.\n  \nWe will add this procedure for $K>2$ clusters in the Appendix of the final version, along with this (non-optimal) bound.  However, finding a distribution-dependent optimal strategy, taking into account the relative positions of all means $\\mu^1,\\dots, \\mu^K$, remains highly non-trivial and is way beyond the scope of our paper.\n- **Robustness to heterogeneity within the clusters**\n\n  Actually, our method can be adapted to deal with problems where there exists some heterogeneity inside the groups. We invite you to read the answer in the rebuttal to reviewer AdRS.\n- **Intuition on the complexity $H$ for sparse vector**\n\n  We would like to provide more intuition on the trade-off $H$ (see Eq. (3)). In particular, we will explain why a dependency in the dimension $d$ is unavoidable and that $H$ is the optimal trade-off between $d$ and $\\Delta$.\n\n  Most of our intuitions about the problem lies in the simple case (Corollary 3.2), where the gap vector is $s$-sparse with a constant magnitude $h$. In this case, the l2 norm of the gap vector $\\Delta$ (appearing in $H$) becomes $||\\Delta||_2^2=sh^2$. Before explaining the intuition behind this rate, we emphasize that the lower bound matches Theorem 4.1 in this setting thereby showing that our budget is indeed optimal.\n  \n  To perform the clustering task, we need to select a feature that discriminates the two groups. if one item in each cluster are identified , this problem is equivalent to finding a good arm of reward $h$ among $d$. In this case, a simple algorithm --which is at the core of our approach-- proceeds as follows. \n   - First, sub-sample $\\frac{d}{s\\theta}\\log(1/\\delta)$ entries from the matrix, so that, with high probability, a nonzero entry is selected.  If $s=d$, the problem reduces to one dimension; if $s=1$, all features must be explored.\n  - Second, sample all these entries $\\frac{1}{h^2}\\log(1/\\delta)$ times, select the entry with the largest (absolute) mean, and store the associated feature. \n  - Finally, sample  $\\frac{1}{h^2}\\log(1/\\delta)$ each item on this feature and classify the items.\n  \n  In the paper, our algorithm (especially through the use of sequential halving) adapts to the unknown parameters $s$ and $h$, and leads to a budget $\\frac{d}{\\theta sh^2}\\log(1/\\delta)^2+\\frac{n}{h^2}\\log(1/\\delta)$. We can argue that all these steps cannot be improved with respect to $d,s,h$. We will provide more intuition on this optimal trade-off in the final version. Also, you can find a discussion on the optimality of $H$ for general shapes of $\\Delta$ in the rebuttal of reviewer z8W5.\n- **Literature on online clustering of bandits**\n\n  We appreciate your suggestion regarding references on the problem of online clustering of bandits and its extensions. This problem is indeed related to our setting, as it involves exploring a bandit environment where the items exhibit an underlying clustering structure. We will include a discussion on the similarities and differences between our approach and this interesting line of research in the literature review of our paper. Still, we would like to point out there are two major differences with our problem: (1) the learner has no control over which items are presented at each time step, and (2) the algorithms (such as CLUB and its extensions) are evaluated in the cumulative regret setting.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I checked the main content of the paper.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "## Contributions:\n\n1. Introduction of a new bandit cluster model where only one item-feature pair can be selected in each round, distinguishing it from existing works that select an item with all features.\n2. Development of the first lower bound that characterizes the fundamental difficulty of the bandit clustering problem.\n3. Design of a near-optimal bandit clustering algorithm with theoretical guarantees.", "essential_references_not_discussed": "There is another line of clustering of bandits’ works. For example:\n\n1. Gentile, Claudio, Shuai Li, and Giovanni Zappella. \"Online clustering of bandits.\" In International conference on machine learning, pp. 757-765. PMLR, 2014.\n2. Li, Shuai, Wei Chen, and Kwong-Sak Leung. \"Improved algorithm on online clustering of bandits.\" arXiv preprint arXiv:1902.09162 (2019).\n3. Liu, Xutong, Haoru Zhao, Tong Yu, Shuai Li, and John CS Lui. \"Federated online clustering of bandits.\" In Uncertainty in Artificial Intelligence, pp. 1221-1231. PMLR, 2022.\n4. Li, Zhuohua, Maoli Liu, Xiangxiang Dai, and John Lui. \"Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts.\" arXiv preprint arXiv:2501.00891 (2025).", "other_strengths_and_weaknesses": "## Weaknesses:\n\n1. In Section 6, the authors discuss two important extensions: increasing the number of groups ($K>2$) and handling heterogeneous groups, which would better model real-world applications. However, the discussion provides only vague ideas without specific results for each extension. More concrete analysis or preliminary results would strengthen the paper's practical relevance.\n2. Regarding the upper bound result, there appears to be a factor of $d$ in the regret upper bound in Equation (3). It seems possible that fixing one feature to explore could remove this d factor, potentially at the cost of a larger $\\Delta$ term. The paper would benefit from a more thorough discussion of this trade-off, especially in cases where the d improvement might dominate any negative effects on the $\\Delta$ term.", "other_comments_or_suggestions": "## Minor Issues:\n\nThere are several typographical errors throughout the paper. For example, on line 230, a sentence is incomplete.", "questions_for_authors": "Please comment/discuss the weakness part. I am happy to raise my score if these questions are well discussed/solved.\n\n-------------Post-rebuttal----------------\n\nThe reviewer thanks the authors for their detailed responses, including the discussion on extending to more than two groups ($K > 2$), addressing heterogeneous groups, elaborating on the trade-offs between $d$ and $\\Delta$, and discussing the missing references. My concerns have been resolved, and I would like to raise my score. I encourage the authors to incorporate these discussions into the final version to improve clarity and completeness of the current work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oe2VeZUu5l", "reviewer": "Reviewer_D6WK", "summary": "This paper studies a problem of clustering $n$ items into two groups using bandit feedback. This setting considers an $n \\times d$ matrix $M$, where each row represents an item's feature vector. The $n$ rows are partitioned into two unknown groups, such that items within the same group share the same feature vector. The learner sequentially and adaptively an item $I_t \\in [n]$ and a feature $J_t \\in [d]$, and gets a noisy observation drawn from an unknown distribution with mean $M_{I_t,J_t}$. The goal is to recover the correct item partition with minimal observations. The authors propose an algorithm called `BanditClustering`, which operates in two steps: (1) identifying two representative items from different groups, and (2) selecting a discriminative feature to classify all items. The authors provide theoretical results such as a tight upper bound on the required budget and a matching instance-dependent lower bound. Numerical experiments validate the efficiency of the method compared to non-adaptive clustering approaches.\n\n## update after rebuttal\nOverall, I appreciate the technical novelty of this paper. Therefore, I decided to maintain my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank you for your time and effort in reviewing our paper. Below, we address the key remarks and questions raised in your review:\n\n- **Extension to $K>2$ clusters**\n\n  In the paper, we analyze the case of two clusters, as even in this simpler setting, significant challenges appeared to obtain optimality. It happens that it is possible to use our algorithms as subroutines in order to handle the extension to $K$ cluster. To avoid redundancy, we invite you to read the answer to reviewer RdCv where this extension is discussed in detail. When dealing with $K>2$ groups, it is significantly more challenging to find a strategy which adapts optimally to the relative position of the centers of the $K$ groups, we will leave this question for future works. \n- **Dependency on the balancedness $\\theta$**\n\n  Thank you for the question.  From a theoretical point,  we do prove in the paper that the balancedness parameter $\\theta$ has only an impact on the first step of our procedure, i.e., the identification of representatives.  Furthermore, gathering Proposition C.1 (analysis of Algorithm 2), and the lower bound in Lemma E.1, we are able to prove that our procedure exhibits the optimal dependency on the budget with respect to $\\theta$.\n  The only difficulty to deal with very unbalanced clusters is that it is hard to detect a row in the smallest cluster. We will add further discussion about the dependency on $\\theta$ of our method in the final paper.\n\n  We have also run numerical experiments to investigate the influence of $\\theta$. They will be included in the paper. In a first setup, we are able to see that indeed, $\\theta$ mainly influences the CandidateRow-step of our clustering procedure and that the influence on the budget of this step is comparable to a factor $1/\\theta$, which fits in with our theoretical findings. Furthermore we can see that in this setup, our algorithm clearly outperforms uniform allocation strategies for very small values of $\\theta$, while being competitive for larger values of $\\theta$. \n\n- **Suggestions**\n\n  Thank you to your suggestion, we will correct all quotation marks, and improve the explanation and legend of Figure 1. \n- **Motivation**\n\n  We thank the reviewer for pointing out that we should extend the discussion of our motivating example, which comes from image labeling. Recent work about distinguishing \"doppelganger\" animals  uses expert annotators to ensure a correct labeling (see [Herde, Marek, et al. \"dopanim: A Dataset of Doppelganger Animals with Noisy Annotations from Multiple Humans.\" Advances in Neural Information Processing Systems 37 (2024): 51085-51117.]). This works because experts know which features are relevant for a correct distinction. If no experts are available, our approach still provides a solution, because we can find the relevant features without prior knowledge and use non-expert workers for the classification task.\n    \n- **Numerical experiments**\n\n  As mentioned above, we will illustrate the dependency with $\\theta$ in an additional numerical experiment. Besides, we will also compare our method with the method from [Ariu et al.(2024) \"Optimal clustering from noisy binary feedback\"]).", "claims_and_evidence": "All claims are well-supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem.", "theoretical_claims": "I have not checked all the proofs in detail but did not identify any obvious errors.", "experimental_designs_or_analyses": "The experiments rely solely on synthetic data and consider only uniform sampling and K-means as baselines. It would be better to compare other adaptive clustering methods, such as the ones mentioned in the related work. Also, the comparison does not examine performance in highly imbalanced scenarios (when $\\theta$ is small).", "relation_to_broader_scientific_literature": "This work extends the bandit clustering problem studied in prior works, such as Thuot et al. (2024) and Yang et al. (2024). Unlike these studies, where the entire noisy feature vector of an item is observed at each step, the setting introduced in this paper allows only a single noisy feature to be observed per step. This introduces a new and inherently more challenging problem.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Strengths\n1. This paper is well-organized and easy to follow.\n2. This paper studies a new bandit clustering problem where at each step, only a single noisy feature of a given item is observed. This setting is different from previous studies where the entire noisy feature vector is observed.\n3. The authors provide rigorous upper and lower bounds on sample complexity, ensuring that their method is provably efficient.\n\nWeaknesses\n1. The algorithms and theoretical analysis assume only two clusters, which is a strong limitation. While the authors suggest that they could \"straightforwardly extend\" their methodology to multiple clusters, this extension is not formally developed or analyzed.\n2. The paper primarily focuses on theoretical contributions and lacks strong motivation. Although the introduction includes a motivating example, it does not clearly articulate the significance of the problem.", "other_comments_or_suggestions": "Quotation marks in LaTeX should be formatted using `` and '' instead of \" \".\n\nThe legend in Figure 1 is unclear. What does the algorithm \"Cluster\" refer to? Also, it seems that the uniform sampling algorithm is not explicitly labeled. Furthermore, what does the shaded area indicate?", "questions_for_authors": "1. Why do the authors restrict their analysis to only two clusters? What challenges arise when extending the approach to multiple clusters?\n2. How does the proposed algorithm perform when the data is imbalanced (i.e., $\\theta$ is small), and how does it compare to the baselines?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of clustering items under bandit feedback in a fixed-confidence setting. It is assumed that the items are divided into two unknown groups, and items within the same group share the same $d$-dimensional feature vector. At each time step, the agent selects a pair consisting of an item and one feature (out of $d$ features), and receives noisy feedback pertaining to that feature component. The objective is to correctly cluster all items with a confidence guarantee of at least $1 - \delta$, while minimizing the number of samples used.

Previous research on fixed-confidence bandit clustering has typically assumed that the entire feature vector of an item can be observed at each time step. In contrast, this study introduces the challenge of observing only a single feature of the feature vector, leading to the difficulty of “Finding the Right Feature out of Many.” This paper is the first to provide analysis for adaptive algorithms under such a setting.

Several limitations are noted, such as the lower and upper bounds not being tight, optimality being achieved only under restricted values of $\Delta$ ((it would be good to have comparisons with the lower/upper bounds in existing studies such as Yang et al., Thuot et al., Ariu et al., and Yavas et al.), the number of clusters being limited to two, and heterogeneity within the same cluster not being considered. In terms of algorithm design, there appear to be many areas for improvement—for example, they apply an anytime version using the doubling trick from Successive Halving (SH), a method suitable for fixed-budget problems, to the fixed-confidence problem. The experiments were limited, and there was mention of a lack of ablation studies on $\theta$ and comparisons with existing methods (Ariu et al., 2024).

The authors have addressed these concerns to some extent in their rebuttal, and all reviewers seem to have agreed to assign or maintain a positive score in response. I expect these points to be reflected in the revised version.
Decision: Accept (poster)