从人类反馈中学习对数凹随机效用模型下的排序

arXiv:2610.07973v1 公告类型：新 摘要：我们研究根据未知数值效用恢复一组固定项目排序的问题。在每次与环境交互时，学习者将项目集合呈现给人类，并接收两种类型之一的比较反馈。在全排名反馈下，每次交互都会揭示所有项目的带噪排序；而在仅胜者反馈下，只会揭示排名第一的项目。在这两种设置中，我们都使用带有对数凹噪声的随机效用模型对人类反馈进行建模，并研究以高概率恢复 $\epsilon$-准确排序所需的观测数量。这一新颖的标准只允许效用差异小于 $\epsilon$ 的项目之间出现排序错误。针对这两种反馈类型，我们建立了最坏情况下的样本复杂度下界，并设计了在对数因子范围内达到这些下界的算法。两种算法都不需要知道噪声分布，只需知道其方差的一个上界。我们的结果表明，仅胜者反馈下的排序问题在本质上更加困难，因为其样本复杂度取决于项目集合中的最小获胜概率。