# Active clustering with bandit feedback

arXiv: https://arxiv.org/abs/2406.11485 · HTML: https://mlsanity.com/paper/2406.11485/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 17 Jun 2024.

## Builds on (most cited first, 19 of 19)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Better Agnostic Clustering Via Relaxed Tensor Norms](https://mlsanity.com/paper/1711.07465/) (2017)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering](https://mlsanity.com/paper/1610.02918/) (2016)
- [Online k-means Clustering](https://mlsanity.com/paper/1909.06861/) (2019)
- [The Influence of Shape Constraints on the Thresholding Bandit Problem](https://mlsanity.com/paper/2006.10006/) (2020)
- [Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM](https://mlsanity.com/paper/2101.00575/) (2021)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [Adaptive Sampling for Coarse Ranking](https://mlsanity.com/paper/1802.07176/) (2018)
- [Optimal Clustering from Noisy Binary Feedback](https://mlsanity.com/paper/1910.06002/) (2019)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)

## Built on by (most cited first, 7 of 7)

- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [Clustering Items through Bandit Feedback: Finding the Right Feature out of Many](https://mlsanity.com/paper/2503.11209/) (2025)
- [Online Clustering of Data Sequences with Bandit Information](https://mlsanity.com/paper/2501.11421/) (2025)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)
- [Locally Differentially Private Thresholding Bandits](https://mlsanity.com/paper/2507.23073/) (2025)
- [Nonparametric Kernel Clustering with Bandit Feedback](https://mlsanity.com/paper/2601.07535/) (2026)
- [Efficient Clustering in Stochastic Bandits](https://mlsanity.com/paper/2601.09162/) (2026)

## Abstract (arXiv)

We investigate the Active Clustering Problem (ACP). A learner interacts with an N-armed stochastic bandit with d-dimensional subGaussian feedback. There exists a hidden partition of the arms into K groups, such that arms within the same group, share the same mean vector. The learner's task is to uncover this hidden partition with the smallest budget - i.e., the least number of observation - and with a probability of error smaller than a prescribed constant δ. In this paper, (i) we derive a non-asymptotic lower bound for the budget, and (ii) we introduce the computationally efficient ACB algorithm, whose budget matches the lower bound in most regimes. We improve on the performance of a uniform sampling strategy. Importantly, contrary to the batch setting, we establish that there is no computation-information gap in the active setting.