arXiv · Machine Learning Theory· Shashaank Aiyer, Han Shao·2026-10-09 12:00· 3 小时前AI 评分27

异质偏好下排序恢复需要多少次重复两两比较

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

AI 导读

该研究在异质 Bradley-Terry 模型下分析按总体平均效用做排序所需的重复两两比较次数，证明朴素 MLE 算法需 Ω(1/Δ²) 次、两种 MLE 变体与 Russian Roulette 随机算法仅需 O(log(1/Δ)) 次且该对数依赖最优。