arXiv：cs.LG· Diego Alovisetti, Marco Mussi, Alberto Maria Metelli·· 4 小时前AI 评分27
在 Log-Concave 随机效用模型中从人类反馈学习排序
Learning a Ranking from Human Feedback in Log-Concave Random Utility Models
AI 导读
研究在 log-concave 噪声的随机效用模型下，从人类比较反馈中恢复物品排序所需的样本复杂度。在完整排序反馈与仅胜者反馈两种设定下，作者给出了最坏情况样本复杂度下界，并提出匹配该下界（至对数因子）且无需知道噪声分布、只需方差上界的算法。结果表明仅胜者反馈的排序问题本质更难，其复杂度依赖物品集合中的最小获胜概率。
正文
Abstract:We study the problem of recovering the ranking of a fixed set of items according to their unknown numerical utilities. At each interaction with the environment, a learner presents the item set to a human and receives comparative feedback of two types. Under full-ranking feedback, each interaction reveals a noisy ranking of all items, whereas under winner-only feedback, it reveals only the item ranked first. In both settings, we model human feedback using a random utility model with log-concave noise and study the number of observations needed to recover an $\epsilon$-accurate ranking with high probability. This novel criterion tolerates ordering errors only between items whose utilities differ by less than $\epsilon$. For both feedback types, we establish worst-case sample-complexity lower bounds and develop algorithms that match these bounds up to logarithmic factors. Neither algorithm requires knowledge of the noise distribution, while only requiring an upper bound on its variance. Our results show that the ranking problem under winner-only feedback is intrinsically harder by exposing the sample complexity dependence on the minimum winning probability across the item set.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07973 [cs.LG] |
| (or arXiv:2610.07973v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07973 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Diego Alovisetti Mr. [view email]
[v1]
Tue, 6 Oct 2026 08:41:20 UTC (51 KB)
来源：arXiv：cs.LG · arxiv.org