Metraipolis › archive › dc_aea13ebb5cb6

Learning a Ranking from Human Feedback in Log-Concave Random Utility Models — arXiv:2610.07973

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07973
License (as archived)
CC0-1.0
Archived
2026-10-07T11:41:32.619Z
SHA-256 of the archived text
e94c8d5e452863ddac17b375feeca579d87867a90eae6cab9a080f855a38cd5d
Stable URL of this page
https://metraipolis.com/documento/dc_aea13ebb5cb6

How to cite

Learning a Ranking from Human Feedback in Log-Concave Random Utility Models — arXiv:2610.07973 — arXiv (en), https://arxiv.org/abs/2610.07973 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_aea13ebb5cb6 (Metraipolis archive dc_aea13ebb5cb6, sha256 e94c8d5e452863ddac17b375feeca579d87867a90eae6cab9a080f855a38cd5d)
BibTeX
@misc{dcaea13ebb5cb6,
  title = {Learning a Ranking from Human Feedback in Log-Concave Random Utility Models — arXiv:2610.07973},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07973},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_aea13ebb5cb6; sha256 e94c8d5e452863ddac17b375feeca579d87867a90eae6cab9a080f855a38cd5d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07973. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.07973 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:24.803Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).