Almost Asymptotically Optimal Active Clustering Through Pairwise Observations
Abstract
We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses. At each time step, an agent is allowed to query pairs of items and observe bandit binary feedback. If the pair of items belongs to the same (resp.\ different) cluster, the observed feedback is $1$ with probability $p>1/2$ (resp.\ $q
Fields of Study & Subjects
Advanced Bandit Algorithms Research
Machine Learning and Algorithms
Advanced Clustering Algorithms Research
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 5 February 2026
- Document type
- Preprint