CS Paper Radar

Learning a Ranking from Human Feedback in Log-Concave Random Utility Models

Diego Alovisetti, Marco Mussi, Alberto Maria Metelli

cs.LG ·submitted 2026-10-06 08:41 UTC · v1
theory

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 $ε$-accurate ranking with high probability. This novel criterion tolerates ordering errors only between items whose utilities differ by less than $ε$. 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Prediction-Powered LLM Ranking with Adaptively Collected Human Feedback

cs.LG stat.ME ·2026-11-09 ·Gabriel Sargent, Will Wei Sun, Zhengwu Zhang, Yufeng Liu
similarity 0.65
Abstract · 35 pages, 4 figures

Ranking large language models (LLMs) through human evaluations is essential for downstream decision-making. Because human feedback is expensive, evaluation platforms often collect it adaptively, prioritizing informative model comparisons using previously observed feedback. To further improve precision with limited human feedback, evaluators can draw on abundant unrated responses and relatively inexpensive LLM judges; however, judge bias and adaptive dependence challenge standard i.i.d. inference frameworks. We propose Prediction-Powered Ranking (PP-Rank), a framework that combines LLM-judge predictions with human feedback to improve precision while providing valid inference under adaptive sampling. Data-driven prediction weights minimize the asymptotic covariance trace within the proposed class. In theory, we establish asymptotic normality for general evaluation targets and simultaneous ranking inference. A joint martingale analysis handles dependence between adaptive human feedback and auxiliary data. We further derive a rule for reducing exploration that prioritizes lower-cost comparisons while matching a conservative variance bound, and characterize allocation limits for regular $\sqrt{T}$-rate estimation of pairwise means. Semi-synthetic experiments on UltraFeedback-Extended show improvements over human-only baselines in score estimation, confidence interval width, and ranking certification. Synthetic experiments demonstrate robustness to judge quality and adaptive allocation, while showing that PP-Rank can substantially reduce evaluation costs without sacrificing precision.

0.15

Sorting from Counterexamples

cs.LG cs.CCcs.CGcs.DS+1 ·2026-08-21 ·Noga Alon, Shay Moran, Shlomo Moran
publishedtheory similarity 0.65
Abstract

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ Θ(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

0.37

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

cs.LG stat.ML ·2026-10-21 ·Yashaswini Kaluguri, Nikhil Karamchandani
theory similarity 0.64
Abstract

We propose a novel stochastic cascading bandit setup where probing an ordered shortlist of $K$ out of $L$ arms incurs position-dependent costs, and the learner observes only noisy feedback regarding each arm's true output. We identify a sub-class of noise models for which the optimal shortlist can be found by sorting arms according to a per-arm score: such a score exists for both selection and ordering when the channel has no false positives, and for ordering alone (but not selection) when measurements are costless; however in general neither selection nor ordering is separable once noise and cost are both present. For the case where both selection and ordering scores exist, we provide a UCB-based algorithm with $O((L-K)\log T)$ instance-dependent regret over a time horizon $T$, which matches an algorithm-agnostic lower bound (up to constant factors). For the more challenging scenario where scores don't exist, we develop a new algorithmic template, DP-UCB, that embeds optimism directly inside an exact dynamic program, yielding $O\big(LK\log T\big)$ regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.

0.08

On the Complexity of Preference-Based Bandits

cs.AI cs.LG ·2026-09-30 ·Ahmed Ben Yahmed, Marc Abeille, Clément Calauzènes
top venue similarity 0.63
Abstract

We study preference-based bandits with general reward function classes, where a learner sequentially selects pairs of arms and observes binary preference feedback governed by the Bradley--Terry model. This setting naturally arises in applications such as recommender systems, tournament ranking, and learning from human feedback, where relative preferences are easier to elicit than absolute rewards. The observation model inherits the logistic bandit challenge of handling the problem-dependent constant $κ$, which accounts for the non-linearity of the link function and can grow arbitrarily large. Moreover, prior work has predominantly focused on linear or kernelized reward models, precluding the use of richer function classes. To address these limitations, we consider general reward function classes and introduce the \emph{locally sensitive eluder dimension}, a novel complexity measure tailored to the logistic structure of preference feedback that yields fine-grained regret guarantees without unfavorable dependence on $κ$. Building on this notion, we propose \textbf{GINOP} (Generic INformative OPtimism), an algorithm that constructs log-loss confidence sets and jointly selects arm pairs to balance optimism and informative exploration. We establish a first-order regret bound that, in contrast with what previous results suggest, demonstrates that learning with preference feedback is as statistically efficient as learning from direct reward observation. Finally, we corroborate our theoretical findings with empirical evaluations against competitive baselines.

0.39

Ranking Bandits for Carousel Interfaces with Observable Browsing Depth

cs.LG ·2026-10-04 ·Takuma Yasuda, Atsuyoshi Nakamura, Dai Hai Nguyen
theory similarity 0.61
Abstract · Some mistakes are fixed. One author is added

Carousel interfaces allow a recommender system to directly observe how far a user has browsed. This signal distinguishes displayed but unclicked items from items that were never displayed, whereas conventional ranking-bandit models, including cascade and position-based models, generally treat examination as latent. We formulate a ranking-bandit problem in which a learner presents a list of $L$ items, observes the user's maximum browsing depth, and receives click feedback only for positions up to that depth. The objective is to maximize the expected number of clicks under an unknown item-attractiveness vector and a browsing-depth distribution. We propose three algorithms based on UCB, Thompson Sampling, and DMED, all of which update item statistics only from observed exposures. We derive an instance-dependent logarithmic upper bound for our UCB-based algorithm and an asymptotic upper bound for our DMED-based algorithm that coincides with the lower bound as its parameter $α\downarrow 0$, establishing asymptotic optimality in this limit. Simulations in synthetic shallow- and deep-browsing environments, together with experiments parameterized from RecGaze interaction logs, show that OD-TS attains final mean regret similar to PBM-TS, while the proposed methods achieve lower final mean regret than PBM-UCB.

0.14

Adaptive Doubly Robust Off-Policy Evaluation for Ranking Policies under Diverse User Behavior

cs.LG cs.IR ·2026-08-30 ·Kosuke Iguchi, Ren Kishimoto
published similarity 0.60
Abstract · 14 pages, 4 figures, 7 tables. Accepted at CONSEQUENCES 2026 and selected for oral presentation

Off-policy evaluation (OPE) of ranking policies is challenging be- cause selecting and ordering multiple items from a candidate set makes the number of possible rankings grow combinatorially with the number of candidates and the ranking length. Consequently, Inverse Propensity Scoring (IPS), whose importance weight is the full-ranking probability ratio under the evaluation and logging policies, can have excessive variance. Independent IPS (IIPS) and Reward Interaction IPS (RIPS) reduce variance by imposing fixed assumptions on how users browse rankings, but may introduce bias when those assumptions mismatch actual behavior. Adaptive Inverse Propensity Scoring (AIPS) addresses this trade-off by adap- tively marginalizing importance weights over the actions that affect each position-wise reward. It attains minimum variance within a class of unbiased IPS-based estimators when the true user be- havior model is observed. However, its estimation accuracy may still degrade for longer rankings, and AIPS does not use a reward model for residual correction. We propose Adaptive Doubly Robust (ADR), which combines adaptive importance weighting with re- ward regression through a control-variate correction. We establish its unbiasedness when the true user behavior model is observed and characterize a sufficient condition under which it reduces vari- ance relative to AIPS. Across synthetic experiments with 10,000 simulations per condition, ADR improves mean squared error over AIPS and conventional ranking OPE estimators across a range of logged-data sizes and ranking lengths.

0.46

IncVNM: An Interactive Recommender System with Incremental von Neumann-Morgenstern Utility Learning

cs.IR math.OC ·2026-11-01 ·Jiaxin Wei, Jia Liu
hot direction similarity 0.60
Abstract

In modern recommender systems, users are often presented with products whose outcomes are random. The values of such products depend on their entire outcome distributions and on users' attitudes toward risk, making them difficult to evaluate using traditional product-level recommendation methods. We propose \textsc{IncVNM}, an interactive recommender system that incrementally learns a user-specific von Neumann--Morgenstern (VNM) utility function from ordinal click feedback generated during ordinary webpage browsing. At each interaction, \textsc{IncVNM} converts the click order within a displayed product list into pairwise comparisons between outcome distributions and updates the nominal utility by minimizing its deviation from the previous estimate while incorporating the newly observed pairwise comparisons. To close the interaction loop, an entropy-regularized sampling policy balances exploitation of the learned utility against exploration for additional preference information. We evaluate \textsc{IncVNM} in a rolling-window experiment with different response-error probabilities and show that it substantially outperforms the expected-return, mean--variance, discounted-UCB, and distribution-aware BPR baselines.

0.29

Social Learning of Ranking: Getting the Top Right despite Local Herding

cs.DS ·2026-10-11 ·Shahrzad Haddadan, Jie Gao
hot direction similarity 0.60
Abstract

In sequential learning, a group of agents sequentially receives a noisy private signal and observes the predictions of prior agents to estimate a hidden ground truth. While extensively studied for binary signals, we formalize and analyze sequential learning when the hidden ground truth is an ordering of $n$ items, and both private signals and inferences involve pairwise comparisons. A key focus in sequential learning is herding, where agents disregard their private signals to follow the crowd. We show that, while local herding in our model may lead agents to make incorrect pairwise inferences, the global hidden order can still be approximated. Specifically, by aggregating all pairwise comparison outputs, the highest-ranked items can be retrieved. We investigate top-$k$ retrieval across three scenarios: (1) passive aggregation, where information is gathered from the social learning process without intervention; (2) strategic selection, where agents choose their pairwise comparisons dynamically; and (3) aggregation with stubborn nodes, where a very small set of stubborn agents, who base their inferences solely on their private signals, join the mechanism. With query complexity as the number of agents needed for a high-probability estimation, we propose top-$k$ retrieval algorithms with query complexities sublinear in $O(n^2)$, the total number of pairs.

0.34