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

在本文中，我们研究了主动聚类问题（ACP）。一个学习者与具有 d 维亚高斯反馈的 N 臂随机赌博机交互。存在一致维向量的 K 个组将臂分为隐藏分区，同一组中的臂共享相同的均值向量。学习者的任务是以最小的预算发现这个隐藏分区，并且误差概率小于一个预定的常数 δ。在本文中，我们（i）推导了预算的非渐近下界，（ii）提出了计算高效的 ACB 算法，其预算与大多数情况下的下界相匹配。我们改进了统一采样策略的性能。重要的是，与批处理设置不同，我们证明主动设置中不存在计算信息差距。

带挑战反馈的主动聚类

Active clustering with bandit feedback

Finding a hidden partition in a random environment is a general and important
problem, which contains as subproblems many famous questions, such as finding a
hidden clique, finding a hidden coloring, finding a hidden bipartition etc.
In this paper, we provide a simple SVD algorithm for this purpose, answering
a question of McSherry. This algorithm is very easy to implement and works for
sparse graphs with optimal density.

本文提出了一种简单的 SVD 算法，用于在稀疏图中寻找隐藏分区，适用于最佳密度。