Learning a Ranking from Human Feedback in Log-Concave Random Utility Models
The study addresses recovering item rankings from noisy human feedback using a Random Utility Model with log-concave noise. It develops algorithms for both full-ranking and winner-only feedback, defining $\epsilon$-accuracy based on utility gaps. The key finding is that winner-only feedback is significantly harder than full-ranking because its sample complexity depends critically on the minimum winning probability across all items.