PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Diego Alovisetti, Marco Mussi, Alberto Maria Metelli

arXiv:2610.07973v1cs.LG

TL;DR

The paper asks how many ordinal feedback signals are needed to recover rankings when human scalar scores are unavailable or unreliable. It develops algorithms for full-ranking and winner-only feedback under log-concave random utility models, establishes matching lower bounds up to order, and identifies minimum winning probability as a winner-only bottleneck.

  • Problem

    The paper asks how many ordinal feedback signals are needed to recover rankings induced by latent utilities, since human scalar scores may be unavailable or unreliable.

    Source: §1 · pp. 1–2

  • Method

    The Variance-aware Utility Ranker uses two PAC algorithms for full-ranking and winner-only signals under log-concave random utility models, needing an upper bound on noise variance rather than its exact distribution.

    Source: §1 · pp. 1–2, §5 · p. 6

  • Results

    The paper establishes information-theoretic lower bounds and reports that its algorithms are order-optimal, with minimum winning probability Pmin the informational bottleneck for winner-only feedback.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework quantifies the intrinsic learning difficulties of full-ranking and winner-only feedback, with winner-only difficulty tied to Pmin.

    Source: §1 · p. 2

    The analysis relies on log-concavity to define the utility-to-probability mappings, and whether the approach works under milder noise assumptions remains open.

    Source: §6 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies how to recover rankings from ordinal human feedback when the underlying utilities are latent and scalar scores are unavailable or unreliable. It formalizes an ε-accurate PAC objective and presents a unified, distribution-agnostic approach to full-ranking and winner-only feedback.

1 INTRODUCTION

  • Human evaluators may provide ordinal rankings more reliably than scalar scores, even though the target ranking is induced by latent numerical utilities.The paper models feedback as a noisy partial ranking generated from perturbed utilities.Source: §1 · p. 1
  • The paper considers full-ranking feedback, which reveals the complete noisy ordering, and winner-only feedback, which reveals only the top-ranked item.Source: §1 · p. 1
  • The PAC objective uses ε-accuracy, a ranking distance that depends on the utilities rather than treating every ordering error alike.It is distinguished from standard discrete distances such as Kendall tau.Source: §1 · pp. 1–2
  • The central question is how many ordinal feedback signals are needed to recover the ranking induced by items’ scalar utilities.Source: §1 · p. 2
  • The Variance-aware Utility Ranker (VUR) provides two algorithms across the feedback types, requiring log-concavity and an upper bound on noise variance rather than the exact noise distribution.The paper reports information-theoretic lower bounds and identifies minimum winning probability Pmin as a bottleneck for winner-only feedback.Source: §1 · pp. 1–2

2 PRELIMINARIES

The preliminaries establish notation for asymptotic bounds, permutations, and directed graphs, then introduce log-concavity as a property of probability distributions.

2 PRELIMINARIES

  • The notation ˜O suppresses logarithmic factors, except for the confidence-dependent term log(1/δ).Source: §2 · p. 2
  • For k items, [k] denotes {1, . . . , k}, and S_k denotes the set of permutations on [k].A permutation σ assigns position σ(i) to item i.Source: §2 · p. 2
  • A strict partial order on a finite set has a linear extension, and an acyclic directed graph induces a strict partial order through its transitive closure.Source: §2 · p. 2
  • A log-concave distribution on the real line is either a Dirac measure or absolutely continuous, and its density and cumulative distribution function are log-concave in the latter case.Source: §2 · p. 2

3 PROBLEM FORMULATION

The formulation assigns each item a utility and models observed feedback as rankings of independently perturbed utilities. It defines ranking accuracy and PAC learning in terms of utility gaps and the probability of returning an accurate ranking.

3 PROBLEM FORMULATION

  • Each of k items has a scalar utility, and the utility ranking is the permutation induced by those utilities.Source: §3 · p. 3
  • The noise is centered, log-concave, absolutely continuous, and has bounded variance V, while its exact distribution remains unknown.The variance bound is a parameter of the algorithms and is described as a reliability constraint.Source: §3 · p. 3

3.1 Feedback-generation Process

  • At each interaction, independent identically distributed noise perturbs the utilities to form a random utility vector, and a fixed feedback filter produces the observation.The sequence of independent vectors is denoted RUM(u, ν).Source: §3.1 · p. 3
  • The full-ranking filter returns the complete ordering of perturbed utilities, whereas the winner-only filter returns the item with the highest perturbed utility.Source: §3.1 · p. 3

3.2 The PAC Objective

  • The objective measures ranking error through misordered item pairs in relation to their latent utility gaps, rather than requiring explicit utility reconstruction.The paper contrasts this focus with approaches where ranking estimation is a byproduct of utility estimation.Source: §3.2 · p. 3
  • An algorithm is a stopping time and an output permutation measurable from the feedback observed by that stopping time.Source: §3.2 · p. 3

3.1 Feedback-generation Process

  • With absolutely continuous noise, ties occur with probability zero, although the winner-only filter specifies minimum-index tie-breaking.Source: §3.2 · p. 3

3.2 The PAC Objective

  • An algorithm is (ε, δ)-PAC when its output is ε-accurate with probability at least 1 − δ; sample complexity is the expected stopping time.Source: §3.2 · p. 4

4 FULL-RANKING FEEDBACK

Under full-ranking feedback, FR-VUR estimates pairwise preferences to recover an ε-accurate utility ranking. Its sample complexity has matching V/ε² scaling up to logarithmic factors, with the lower bound establishing linear dependence on variance.

4.1 The Pairwise-Preference Probabilities

  • Rank-breaking converts each complete ranking into pairwise comparisons, estimating Pij = P[Ui > Uj]; independent noise makes Pij > 1/2 exactly when ui > uj.Source: §4.1 · p. 4

4.2 The Full-Ranking Resolution Factor

  • The full-ranking resolution factor η(ε) quantifies how strongly an item with utility ε above another is preferred, supporting an algorithm agnostic to the exact noise distribution.Source: §4.2 · p. 4

4.3 The FR-VUR Algorithm

  • FR-VUR forms a graph from estimated preferences and returns a linear extension when that graph is acyclic; with probability at least 1 − δ, ε-separated items are correctly ordered.If the graph contains a cycle, the algorithm chooses a ranking arbitrarily.Source: §4.3 · p. 5
  • ˜O(V/ε²) upper-bound scaling is matched by a worst-case lower bound up to logarithmic factors, establishing the optimal full-ranking rate.The algorithm uses a variance upper bound but does not require exact knowledge of the noise distribution.Source: §4.3 · pp. 4–5, §4 · p. 4, §4.4 · pp. 5–6

4.4 Information-theoretic Lower Bound

  • The lower bound uses a hard Gumbel-noise instance with one utility gap equal to ε and a change-of-measure argument.The result identifies V/ε² scaling as a fundamental learning cost.Source: §4.4 · pp. 5–6

5 WINNER-ONLY FEEDBACK

WO-VUR estimates winning probabilities and relates their ratios to utility gaps. Its sample complexity reflects how rarely the least-likely item wins.

5.1 Observability Assumption

  • A lower bound inversely proportional to Pmin reflects that pairwise order is observed only when one of the two items wins.If both items rarely win, their winning frequencies require many samples to estimate reliably.Source: §5.1 · p. 6, §5.5 · p. 8
  • WO1 requires the utility range to be smaller than the noise-support width, ensuring every item has positive winning probability.This observability condition avoids a regime in which some item cannot win.Source: §5.1 · p. 6

5.2 The Winner-Only Resolution Factor

  • Log-concavity yields a mapping from winning-probability ratios to utility gaps, extending the Plackett-Luce approach to broader random utility models.The resulting resolution factor is bounded below by a quantity defined using the known variance bound, not the specific noise distribution.Source: §5.2 · pp. 6–7

5.3 The Winning-Probability Estimators

  • The learner estimates each item's winning probability from winner indicators using an unbiased empirical estimator.The section also defines an unbiased sample variance for these estimates.Source: §5.3 · p. 7

5.4 The WO-VUR Algorithm

  • WO-VUR is (ε, δ)-PAC under (V) and (WO1), using empirical winning frequencies without knowing the noise density or support.The algorithm requires the variance bound V as input.Source: §5.4 · p. 7

5.4.1 Sample Complexity Upper Bound

  • The upper bound scales as V/(ε^2Pmin); its inverse-linear dependence on Pmin comes from a Bernstein-type stopping rule.A Hoeffding-based approach would instead give a suboptimal quadratic dependence on 1/Pmin.Source: §5.4.1 · pp. 7–8

5.5 Information-theoretic Lower Bound

  • Theorem 4 establishes the V/(ε^2Pmin) dependence as an information-theoretic limit for winner-only ranking.The upper bound has the same scaling, up to logarithmic factors.Source: §5.4.1 · p. 8, §5.5 · p. 8

6 OPEN CHALLENGES

The paper identifies open questions about feedback types, noise assumptions, and interaction protocols. It situates ε-accuracy among objectives for best-item identification, parameter estimation, and ranking.

6 OPEN CHALLENGES

  • Learning across feedback types between full-ranking and winner-only, such as top-m, remains open; so do milder noise conditions, subset selection, and ranking-feedback regret.The VUR utility-to-probability mappings rely on log-concavity.Source: §6 · p. 8

A RELATED WORKS

  • Unlike best-item or parameter-estimation objectives, ε-accuracy targets a full utility ranking while tolerating order errors only for small utility gaps.The paper contrasts this utility-based objective with ε-best ranking, which uses Plackett-Luce parameter gaps and can be more tolerant of low-utility items.Source: A RELATED WORKS · p. 11
  • The analysis extends winning-probability-ratio methods beyond the Plackett-Luce model by using log-concavity rather than a noise-specific constant.Saha and Gopalan (2019) used such ratios to approximate rankings induced by Plackett-Luce parameters.Source: A RELATED WORKS · p. 12

B.1 Distribution Table

The appendix lists noise-family conditions for the algorithms and provides their pseudocode.

B.1 Distribution Table

  • For the five listed noise families, the stated parameter conditions satisfy both algorithms' noise assumptions; WO additionally requires WO1 for uniform noise.The other four families have full support, so WO1 holds automatically for any utility set.Source: Table 1 · p. 12, §B.1 · p. 12

B.2 Pseudocode for Variance-aware Utility-Rankers

  • The appendix provides pseudocode for the full-ranking and winner-only VUR algorithms.Source: §B.2 · p. 12

C TECHNICAL RESULTS AND PROOFS FOR SECTION 4

The technical appendix supports FR-VUR by establishing pairwise-preference consistency, concentration bounds, a uniform resolution bound, and its PAC property.

C.1 The Pairwise-preference Probabilities

  • For the pairwise-preference probability Pij = P[Ui > Uj] defined in Section 4, Lemma 5 states that Pij > 1/2 if and only if ui > uj.Source: §C.1 · p. 12

C.2 Concentration Bounds

  • The appendix gives anytime concentration bounds for the unbiased estimators used in the full-ranking analysis.The bounds hold simultaneously across pairs and times with probability at least 1−δ.Source: §C.2 · p. 14

C.3 Uniform Lower Bound on the Resolution Function

  • A uniform lower bound on the full-ranking resolution function is established for noise distributions satisfying the bounded-variance condition.This bound is used in the appendix's proof of the PAC property.Source: §C.3 · p. 15, §C.4 · p. 16

C.4 The PAC Property

  • With probability at least 1−δ, the pairwise-preference graph is a subgraph of the utility graph, and items separated by at least ε are correctly ordered.Source: §C.4 · p. 16

C.5 Sample Complexity Upper Bound

The proof bounds the expected stopping time by the point at which both stopping-rule conditions hold, plus a universal additive constant. It uses simultaneous concentration conditions and controls the tail when the good event fails.

C.5 Sample Complexity Upper Bound

  • On event E, the stopping rule is satisfied when the two stated conditions hold simultaneously for every distinct item pair.The argument first finds n0 for one condition, then n1 so both conditions hold from n2 := n0 + n1 onward.Source: §C.5 · pp. 17–18
  • If stopping has not occurred by time n, at least one of the two conditions failed for some item pair, an event bounded by a union bound.The proof bounds this probability by k(k−1)δn−1.Source: §C.5 · p. 18
  • E[T] ≤ n2 + C2, where n2 is chosen so both stopping-rule conditions hold for every later time.The proof bounds the contribution from the event where the conditions fail using a union bound over item pairs and conditions.Source: §C.5 · p. 18

C.6 Information-theoretic Lower Bound

The appendix develops a full-ranking lower-bound argument and supporting results for concentration and winner probabilities. It bounds information between constructed ranking instances, relates winning-probability differences to utility gaps, and establishes consistency of winner probabilities with utility order.

C.6 Information-theoretic Lower Bound

  • The ranking law is factored as sequential item choices, enabling a conditional-KL analysis of two constructed utility instances.The proof derives a KL bound and uses it with a change-of-measure argument to obtain the full-ranking lower bound.Source: §C.6 · pp. 19, 22

D.1 Concentration Bounds

  • With probability at least 1−δ, the unbiased estimators satisfy the stated concentration bounds simultaneously for every item and every n > 1.The bounds are based on Maurer and Pontil (2009).Source: §D.1 · p. 22

D.2 Uniform Lower Bound on the Winner-Only Resolution Factor

  • For ui > uj, the winning-probability gap Pi−Pj is bounded below in terms of Pi and the utility gap; the resolution factor is defined using the variance upper bound V.The proof also gives a uniform lower bound on the resolution factor in terms of V.Source: §D.2 · pp. 24–25

D.3 Consistency of the Winning Probabilities

  • Under Assumption (WO1), every item has positive winning probability, and ui ≥ uj implies Pi ≥ Pj.Equal utilities yield equal winning probabilities; a strict utility inequality gives the corresponding strict ordering.Source: §D.3 · p. 25

D.4 Sample Complexity Upper Bound

The WO-VUR upper-bound proof controls estimation error and variance before bounding the stopping time. Its threshold depends on the minimum winning probability and the resolution factor, while the expected stopping time is bounded by a threshold term plus a universal constant.

D.4 Sample Complexity Upper Bound

  • The stopping rule and its auxiliary condition can use the true variance in place of the sample variance, at the price of an extra additive term.The proof identifies the relevant quantity as appearing in both the auxiliary condition and the stopping rule.Source: §D.4 · p. 26
  • When n1 > n0 + 1, the passage’s alternative case says the inequality fails at n1 − 1 and bounds n1 by 256 log(4/(δ n1))/(Pmin η⋆²) + 2.Pmin := min_i∈[k] Pi.Source: §D.4 · p. 26
  • E[T] ≤ T0 + C3, with C3 a universal constant.The proof controls the tail contribution from failure of the concentration event.Source: §D.4 · p. 27

D.5 Information-theoretic Lower Bound

The winner-only lower-bound proof constructs two utility instances that swap an ε-close pair while calibrating a high-utility item to set the minimum winning probability. It bounds the divergence between their winner distributions and applies a change-of-measure argument.

D.5 Information-theoretic Lower Bound

  • The lower-bound construction uses centered Gumbel noise with variance V, whose location shift does not affect the winning probabilities.The accuracy level is restricted to be sufficiently small for the construction.Source: §D.5 · p. 28
  • The two instances swap utilities ±ε/2 for items 1 and 2, while a high-utility item is chosen so both instances have minimum winning probability p.The construction assumes k ≥ 3 and chooses ε sufficiently small.Source: §D.5 · pp. 27–28
  • The proof bounds the KL divergence between the two winner distributions, then applies a change-of-measure argument to lower-bound sample complexity.The instances are treated as bandit models with one available arm and winner feedback as the reward.Source: §D.5 · pp. 28–29

E AUXILIARY RESULTS

The appendix collects auxiliary results: a change-of-measure lemma, a technical result used in sample-complexity upper bounds, and a deviation bound for symmetric unimodal distributions.

E.1 Change-of-measure Lemma for Multi-armed Bandit Problems

  • The appendix restates Kaufmann et al. (2016)'s change-of-measure lemma with bandit notation and says the paper's setting is covered by taking one arm.Source: §E.1 · p. 29

E.2 Technical Result for Bounding the Sample Complexity

E.3 Deviation Bound for Symmetric Unimodal Distributions

  • The appendix states a deviation-bound lemma for symmetric unimodal random variables with positive variance, citing Ion et al. (2022), Theorem 7.1, for the standardized version.Source: §E.3 · p. 30
Loading 2610.07973v1…