Optimal Posterior Sampling for Fixed-Budget Cluster Identification through Pairwise Observations

We study fixed-budget cluster identification from noisy pairwise observations. A collection of items is partitioned into an unknown number of clusters. Querying a pair produces a Bernoulli response with an unknown mean $p>1/2$ if the items belong to the same cluster and $q<1/2$ otherwise. We establish an instance-dependent lower bound on the posterior probability of an incorrect clustering that holds for every adaptive sampling rule. Its exponent is given by a max–min allocation problem that maximizes the minimum weighted Bernoulli KL divergence between the true instance and alternatives with incorrect clusterings. We propose an adaptive algorithm that combines posterior sampling over neighboring alternatives, an exponential-weights learner over pairs, and vanishing uniform exploration. We prove an upper bound on the algorithm's posterior error probability that matches the lower bound at the exponential scale. The algorithm therefore achieves the optimal instance-dependent posterior error exponent almost surely. Experiments on synthetic instances and real-world datasets demonstrate competitive cluster identification performance against existing baselines.