Clustering Items through Bandit Feedback: Finding the Right Feature out of Many

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:

• Extension to $K>2$ clusters

  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.

• Dependency on the balancedness $\theta$

  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$. 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.

  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$.

• Suggestions

  Thank you to your suggestion, we will correct all quotation marks, and improve the explanation and legend of Figure 1.

• Motivation

  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.

• Numerical experiments

  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"]).

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.

• Extension to $K>2$ clusters

  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)).

  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.

We 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.

• Robustness to heterogeneity within the clusters

  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.

• Intuition on the complexity $H$ for sparse vector

  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$.

  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.

  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.

  • 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.
  • 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.
  • Finally, sample $\frac{1}{h^2}\log(1/\delta)$ each item on this feature and classify the items.

  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.

• Literature on online clustering of bandits

  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.

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.

• Discussion on the optimal trade-off $H$ (Eq. (3)) for general $\Delta$

  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.

  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.

  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.

• Extension to $K>2$ clusters

  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.

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:

• Oversampling from row 1

  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.

  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.

• Extension to $K>2$ clusters

  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.

• Robustness to heterogeneity within the clusters

  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.

• Discussion on the optimal trade-off $H$

  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.

• Budget comparison with the literature

  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.

• Real-world applications

  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.