基于成对比较的最优Top-$k$识别

# 基于成对比较的最优Top-k识别
来源：https://arxiv.org/html/2607.08979
###### 摘要
我们研究了从含噪成对比较中进行固定置信度Top-k识别的主动学习问题。在该问题中，算法依次选择物品对进行比较，观察结果，并在能够以不超过δ的误差概率返回Top-k物品集时停止。目标是设计一种δ-正确程序，以最小化期望的比较次数（样本复杂度）。该问题属于赌博机模型中固定置信度纯探索的更广泛文献范畴，其常见目标是渐近最优性：算法的期望样本复杂度在δ→0时匹配信息论下界。针对一系列固定置信度纯探索问题，已开发出渐近最优的程序，但据我们所知，对于潜效用模型下基于成对比较的Top-1或更一般的Top-k识别，尚未建立渐近最优的算法。在此设定下，我们开发了这样一种算法。我们刻画了下界的结构，并将其表述为一个鞍点问题。这种结构使得一种计算高效的原始-对偶过程成为可能，该过程在线学习渐近最优的比较分配。然后，我们构建了一个自适应比较分配算法，该算法追踪由原始-对偶过程学习到的分配，并证明其是渐近最优的。

## 1 引言
在许多场景中，都出现了利用含噪成对比较从候选集中识别Top-k物品的目标。假设一位实践者想要确定哪种大型语言模型最适合其任务。他们打开Arena（Chiang等人，2024（https://arxiv.org/html/2607.08979#bib.bib10））（前身为Chatbot Arena），这是一个通过众包成对人类偏好来评估LLM的公共平台，并浏览排行榜。排行榜对所有相关模型进行排序，但实践者只希望考虑列表中的前几个。使用成对比较进行Top-k识别的其他场景包括：众包成对比较以识别最佳照片、翻译或注释（Narimanzadeh等人，2023（https://arxiv.org/html/2607.08979#bib.bib27）；Kou等人，2017（https://arxiv.org/html/2607.08979#bib.bib24）；Chen等人，2013（https://arxiv.org/html/2607.08979#bib.bib6））；通过成对反馈来识别一小部分物品展示给用户的推荐系统（Kalloori等人，2018（https://arxiv.org/html/2607.08979#bib.bib20））；以及体育锦标赛。Top-k识别在两种不同设定下作为自然目标出现。在第一种设定中，Top-k集本身就是期望的输出。例如，选择单个最佳LLM（k=1），资助计划支持前五个提案，或流媒体服务显示前十名列表。在第二种设定中，Top-k识别是两阶段过程的第一阶段，第二阶段使用不同且/或更昂贵的信号。例如，Arena可用于将候选模型的范围缩小到k个，之后对入围者进行更仔细的特定应用评估。当对所有物品进行第二阶段所需的时间和资源过大时，第一阶段的Top-k识别变得至关重要。在这两种设定中，比较都会消耗金钱、时间和/或稀缺的人类注意力，这使得自适应性具有价值。实验设计者不必事先固定静态采样计划，而是可以根据迄今为止观察到的结果自适应地选择接下来比较哪一对，将努力分配到对区分Top-k物品与其余物品最富信息的比较上。我们在固定置信度设定下研究该问题：实验设计者自适应地选择接下来比较哪一对，观察结果，并且只有当能够以至少1−δ的概率返回正确的Top-k集时才停止。目标是设计这样一种程序，最小化期望的比较次数。

一个关键的建模决策是关于物品的相对排序与其成对获胜概率之间的关系做出何种假设。一些工作做出最小假设，允许出现i≻j但P(i击败j)<1/2的情况；例如，Haddenhorst等人（2021（https://arxiv.org/html/2607.08979#bib.bib14））；Xu等人（2019（https://arxiv.org/html/2607.08979#bib.bib36））。其他工作假设某种形式的随机传递性，排除了这种逆转；例如，Braverman等人（2019（https://arxiv.org/html/2607.08979#bib.bib4））；Shah等人（2017（https://arxiv.org/html/2607.08979#bib.bib33））。最后，潜效用模型假设物品由未观测到的效用θ=(θ1,...,θn)排序。在该模型下，存在一个非递减的连接函数f，使得对于每一对(i,j)，P(i击败j)=f(θi−θj)；例如，Saha & Gopalan（2020（https://arxiv.org/html/2607.08979#bib.bib32），2019（https://arxiv.org/html/2607.08979#bib.bib31））。在本文中，我们假设一个潜效用模型。与许多仅考虑二元结果的成对比较和决斗赌博机文献不同，我们的算法也适用于比较结果是基数的情形。在这种情况下，比较返回一个数值，指示一个物品被偏好的程度，例如，分数差异或测量性能的差异。

先前关于固定置信度最佳臂（物品）识别的工作建立了渐近样本复杂度的信息论下界（Kaufmann等人，2016（https://arxiv.org/html/2607.08979#bib.bib22）；Garivier & Kaufmann，2016（https://arxiv.org/html/2607.08979#bib.bib13）），该下界易于推广到我们的设定。当δ→0时匹配该下界的算法称为渐近最优。下界由一个最大-最小预言分配问题控制。如果真实参数向量θ已知，人们可以分配成对比较，使得所得数据能够排除所有Top-k集与真实Top-k集不同的参数向量——即所谓的“替代”参数。最优预言分配最大化了最困难替代参数被排除的速率。

贡献。对于基于成对比较的Top-k识别，我们刻画了该预言问题的结构。任何替代参数向量θ′必须至少反转一对(i,j)的排序，其中i在真实Top-k中，j在其外部。我们称这样的对为边界对。我们证明该预言问题可以表述为一个双人博弈。设计者将比较分配在所有(n choose 2)对上，而对手则选择k(n−k)个边界对中的哪一个作为“目标”。均衡刻画了渐近最优采样策略和样本复杂度。我们基于一种在线学习该均衡的原始-对偶算法构建了一个比较分配程序，并证明其是渐近最优的。

组织结构。第2节（https://arxiv.org/html/2607.08979#S2）回顾了基于成对比较的Top-k识别文献以及赌博机模型中最优纯探索的相关工作。第3节（https://arxiv.org/html/2607.08979#S3）形式化了模型和目标，并阐述了信息论下界。第4节（https://arxiv.org/html/2607.08979#S4）分析了预言分配问题。第5节（https://arxiv.org/html/2607.08979#S5）提出了在线比较分配算法，第6节（https://arxiv.org/html/2607.08979#S6）证明了其保证。第7节（https://arxiv.org/html/2607.08979#S7）通过模拟实例展示了算法的性能。

## 2 相关工作
### 2.1 基于成对比较的Top-k识别
关于含噪成对比较的序贯学习有大量工作；参见Bengs等人（2021（https://arxiv.org/html/2607.08979#bib.bib3））的综述。这包括关于Top-1识别的广泛文献，这是固定置信度Top-k识别的一个重要特例，也是我们的焦点。我们将提及固定置信度保证的两种标准概念：*δ-正确*，即以至少1−δ的概率返回精确目标；以及*可能近似正确*（PAC），即以至少1−δ的概率返回一个接近最优的目标。

关于从比较中自适应选择Top-k的早期工作包括Busa-Fekete等人（2013（https://arxiv.org/html/2607.08979#bib.bib5）），他们提出了一种基于偏好的竞速算法，用于使用成对比较选择Top-k物品。他们没有对成对偏好的结构做出假设，并且“Top-k”集通过选定的排名规则（例如，Copeland排名）定义。相比之下，更接近我们工作的是Ren等人（2020（https://arxiv.org/html/2607.08979#bib.bib30）），他们研究了*δ-正确*的Top-k选择，假设强随机传递性（SST）以及随机三角不等式（STI）；参见Ren等人（2020（https://arxiv.org/html/2607.08979#bib.bib30））的正式定义。他们开发了一种算法SEEKS，使用淘汰方案进行Top-k选择。在每一轮中，它首先选择一个“接近”当前第k优物品的枢轴物品，将物品与该枢轴进行比较，然后将它们分为三组：明显高于枢轴、模糊不清和明显低于枢轴。第一组中的物品被“接受”进入Top-k，第三组中的物品被淘汰。这两组中的物品不再考虑用于未来的比较。然后，算法对第二组中未解决的物品重复该过程，并在k个物品被接受或n−k个物品被淘汰时停止。他们证明SEEKS的样本复杂度为O(∑_{i=1}^n Δ_i^{-2} (log(n/δ) + log log Δ_i^{-1}))，其中Δ_i是物品i与第k优（或第(k+1)优）物品的距离度量。他们还推导了任何算法成为δ-正确所需的期望样本数的下界：Ω(∑_{i=1}^n Δ_i^{-2} log(1/δ) + log log Δ_{r_k}^{-1})。然而，虽然他们的模型是在SST和STI下表述的，但下界是在以下假设下证明的：(i) 比较由Thurstone模型生成，即P(i beats j) = P(θ_i + Z_1 > θ_j + Z_2)，其中Z_1和Z_2是独立的高斯噪声，方差为1；(ii) δ ∈ (0,1/100)；(iii) θ_1,…,θ_n ∈ [0,1]。因此，在这些条件下，他们表明SEEKS在log n因子内是最优的，但在更一般的条件下，最优性差距可能更大。相比之下，我们的最优性保证仅在渐近区域δ→0中成立，但我们精确匹配下界（包括乘法常数）。

在参数化潜效用模型下，特别是多项式logit（MNL）模型，Top-k识别也得到了研究，其中查询是列表式的。在每一轮中，学习器选择一组ℓ≥2个物品，并观察到该组中最偏好的物品。Chen等人（2018（https://arxiv.org/html/2607.08979#bib.bib7））给出了一种在多项式对数因子内最优的算法，然而，他们的算法保证“高概率”的正确性，但风险水平δ不是输入参数。Ren等人（2018（https://arxiv.org/html/2607.08979#bib.bib29））研究了成对和列表式查询下的PAC Top-k选择。除了Top-k选择之外，还有工作研究用于学习排名的自适应比较策略，其中Top-k识别作为一个特例；例如，Heckel等人（2019（https://arxiv.org/html/2607.08979#bib.bib17））；Mohajer等人（2017（https://arxiv.org/html/2607.08979#bib.bib26））。此外，在Bradley–Terry / Plackett–Luce模型下，有大量的非自适应Top-k恢复文献（例如，Chen等人（2019（https://arxiv.org/html/2607.08979#bib.bib9））；Negahban等人（2017（https://arxiv.org/html/2607.08979#bib.bib28））；Jang等人（2016（https://arxiv.org/html/2607.08979#bib.bib18））；Khetan & Oh（2016（https://arxiv.org/html/2607.08979#bib.bib23））；Chen & Suh（2015（https://arxiv.org/html/2607.08979#bib.bib8））；Hajek等人（2014（https://arxiv.org/html/2607.08979#bib.bib15）））。这些工作研究了在预先指定的采样设计下，计算高效的Top-k物品估计器的准确性。

### 2.2 纯探索与预言追踪方法
在赌博机文献中，*纯探索*问题是指那些收集样本以告知最终决策，而不是最大化采样过程中获得的奖励的问题。对于研究最多的纯探索任务——最佳臂识别，Garivier & Kaufmann（2016（https://arxiv.org/html/2607.08979#bib.bib13））提出了Track-and-Stop框架：一个追踪控制样本复杂度下界的最优分配的采样规则，以及一个停止规则，并证明了其在δ→0时的最优性。Degenne等人（2019（https://arxiv.org/html/2607.08979#bib.bib11））将相同的最大-最小下界程序表述为实验设计者与自然之间的双人博弈，并开发了无需每轮求解完整最大-最小程序即可在线学习鞍点的追踪方案。这些想法已推广到结构化赌博机模型。对于线性赌博机，Degenne等人（2020（https://arxiv.org/html/2607.08979#bib.bib12））通过相同的“博弈化”想法获得了渐近最优的固定置信度算法，Jedra & Proutière（2020（https://arxiv.org/html/2607.08979#bib.bib19））表明，通过惰性更新最优分配，可以使Track-and-Stop方法在计算上可扩展。Wang等人（2021（https://arxiv.org/html/2607.08979#bib.bib35））提出了一种通用的Frank-Wolfe预言追踪方法，可应用于多个纯探索设定。他们的附录包括在非参数偏好矩阵模型下对决斗赌博机Top-k识别的应用。然而，实例化Frank–Wolfe更新需要识别（近）最混淆的替代参数，在他们的情况下，这在物品数量上是组合的。在我们的潜效用模型中，替代参数简化为那些反转边界对排序的参数，从而产生一个具有计算高效更新的在线学习器。

## 3 模型与下界
在本节中，我们形式化序贯比较模型，并陈述一个依赖于实例的期望样本复杂度下界，该下界源于Kaufmann等人（2016（https://arxiv.org/html/2607.08979#bib.bib22））；Garivier & Kaufmann（2016（https://arxiv.org/html/2607.08979#bib.bib13））。

### 3.1 成对比较模型
考虑n个物品，索引为i∈{1,...,n}，每个物品