Learning Correlated Reward Models: Statistical Barriers and Opportunities

AI summary

Overview

• Research area: Machine learning theory and choice modeling — specifically Random Utility Models (RUMs) as used in reward modeling for Reinforcement Learning from Human Feedback (RLHF).
• Technical level: Advanced. The paper is built around identifiability theorems, a polynomial-time estimator, and matching upper and lower sample-complexity bounds, with supporting experiments on real preference datasets.
• Scope: The paper proves that pairwise preference data cannot identify a correlated probit model, shows that best-of-three preference data can, gives a near-optimal estimation algorithm with matching statistical lower bounds, and validates the approach on synthetic and real preference data.

What This Paper Is About

Many reward models used for RLHF rely on the Independence of Irrelevant Alternatives (IIA) assumption, which effectively collapses all human preferences into a single universal utility function. This paper studies the correlated probit model, a Random Utility Model with utilities drawn as X ~ N(μ, Σ), which drops the IIA assumption and can therefore represent users whose preferences are correlated across items. The authors ask two questions: what data is needed to learn such a model, and how many samples does it take.

Key Contributions

1. A barrier result for pairwise data. The authors prove (Theorem 3.2) that for any n ≥ 3 and any (μ, Σ) satisfying their normalization, there exists an infinite set of alternative parameters producing identical pairwise choice probabilities. Pairwise comparisons therefore cannot recover correlational information at all — not just statistically, but information-theoretically.
2. First identifiability results for the correlated probit. They establish identifiability from three-way (best-of-three) ranking probabilities, first for n = 3 alternatives (Theorem 4.1), then for an arbitrary number of alternatives (Theorem 4.4). The authors state that prior to this work, even identifiability results, disregarding statistical considerations, did not exist.
3. A near-optimal estimator and matching lower bound. They give a polynomial-time estimator (Theorem 5.2) that recovers μ and Σ to ℓ∞ error ε using N ⩾ C n² ε^{-2} γ^{-24} log(n/δ) log⁶(n/(γε)) rank-3 permutation observations, and complement it with a lower bound (Theorem 5.3) showing Ω(n² ε^{-2} log(1/δ)) samples are necessary.
4. Empirical validation. They train logit, matrix completion, direct, pairwise probit, and best-of-three probit models on synthetic data and on the sushi, eigen-taste jokes, Netflix, and MovieLens datasets, and examine the learned correlation structure plus a welfare maximization experiment.

Main Findings

• Pairwise data is fundamentally insufficient: Theorem 3.2 shows an infinite family of (μ′, Σ′) pairs matching the pairwise probabilities of any given (μ, Σ). In the instructive case μ = 0, the probability that X_i ≥ X_j is 1/2 for every pair regardless of Σ, so correlation is unlearnable from pairs alone.
• Best-of-three is both sufficient and necessary: Since Theorem 3.2 rules out pairs, and Theorem 4.4 shows three-way observations identify (μ, Σ), the paper concludes best-of-three data is necessary and sufficient.
• Normalization is required for identifiability: Because adding a common shift to all utilities leaves choice probabilities unchanged, the authors adopt Assumption 3.1: ⟨μ, 1⟩ = 0, Σ1 = 0, and Tr(Σ) = n, with X living on the hyperplane 1ᵀX = 0 and Σ of rank n − 1.
• The three-alternative case reduces to bivariate geometry: For n = 3, the utilities are projected onto a two-dimensional subspace via a fixed matrix P, the distribution is made isotropic, and the three pairwise probabilities are expressed as Φ(⟨c̃_i, μ̃⟩) for sign vectors c₁, c₂, c₃ (Lemma 4.2), while the pairwise angles α_ij = ⟨c̃_i, c̃_j⟩ are recovered from observable events over the six slices of the plane (Lemma 4.3).
• Aggregation avoids enumerating all triples: Naively stitching together all 3 × 3 sub-matrices would require O(n³) of them; Theorem 5.2 shows Õ(n²) sub-matrices suffice.
• An observability assumption is needed: Assumption 5.1 requires Pr{i > j > k} ≥ γ for some γ > 0 for all triples, which rules out worst-case scenarios where a large utility gap makes a choice unobservable and some parameters impossible to estimate.
• Lower bound matches the upper bound in n, ε and δ: Theorem 5.3 shows that if some pair (i*, j*) appears in at most ε^{-2} log(1/δ)/4 experiments, no estimator can distinguish two models with ‖Σ¹ − Σ²‖∞ ≥ ε. Since each sample covers only O(1) pairs, this gives Ω(n²) unique experiments and Ω(n² ε^{-2} log(1/δ)) total samples.
• Synthetic experiments: In the synthetic setting, the best-of-three probit matched the "direct" method, and pairwise probit learned nonexistent correlations in the uncorrelated case. For the zero-mean, binary-correlation structure, best-of-three probit reached accuracy 0.79/0.79/0.79 across the 0.25/0.50/0.75 quantiles, compared with 0.45/0.50/0.54 for pairwise probit.
• Real-data experiments: Training with best-of-three observations gave large improvements over pairwise probit; gains over the logit model were modest because mean effects are strong in these datasets. On the sushi A variant with onehot features, best-of-three probit reached 0.68/0.68/0.68 accuracy, versus 0.65/0.65/0.65 for pairwise probit and 0.65/0.66/0.66 for logit.
• Learned correlations are interpretable: In the Netflix data, Spider-Man (2002) and Spider-Man 2 (2004) correlate at 0.56, Kill Bill: Vol. 1 (2003) and Vol. 2 (2004) at 0.57, and the Lord of the Rings: The Fellowship of the Ring and The Two Towers at 0.66; Independence Day (1996) and Lost in Translation (2003) correlate at −0.45. In MovieLens, Braveheart (1995) and Little Women (1994) correlate at 0.53, and Much Ado About Nothing (1993) with The Truth About Cats & Dogs correlates at −0.46.
• Sushi-specific structure: The authors report that sea urchins are highly divisive and that a preference for cucumber sushi negatively correlates with a preference for toro (fatty tuna) sushi.

Methodology in Plain English

The authors model each user's latent utilities over n items as a multivariate normal vector with mean μ and covariance Σ, and assume users pick the item with the highest utility from whatever subset they are shown.

First, they work out what can be learned from the standard data type — comparisons between two items at a time. They show by an explicit construction that infinitely many different (μ, Σ) pairs produce exactly the same pairwise probabilities, so pairs simply do not carry the correlational signal.

Second, they move to three-item comparisons (best-of-three rankings). For the smallest case of three alternatives, they rotate the problem into a two-dimensional space where the distribution becomes isotropic (a standard normal plus a shifted mean). Each of the six possible orderings of three items corresponds to a slice of this plane, so the observable ranking probabilities are exactly the masses of those slices. Knowing which side of each boundary the mean lies on lets them read off the mean projections, and the geometry of the slices lets them read off the angles between the boundary directions. From those pieces they reconstruct the covariance.

Third, they extend this from three items to n items. Each triple of items gives a local estimate up to an unknown positive scaling, and the authors show that these scalings can be pinned down by consistency across overlapping triples until a single global (μ, Σ) remains.

Fourth, they turn these identifiability arguments into an algorithm with a sample-complexity guarantee, and prove a matching lower bound by exhibiting two covariance matrices that no estimator can separate given too few experiments on any single pair.

Finally, they train the models on synthetic data drawn from known probit parameters and on real datasets (sushi, jokes, Netflix, MovieLens), converting rankings to ratings and vice versa, and compare against logit, matrix completion, and a "direct" baseline computed on the training set. For movie datasets they also feed language-model embeddings from Qwen3-Embedding-0.6B.

Why This Matters

The paper explains why the widely used RLHF pipeline — built on pairwise comparisons and IIA-respecting models such as Bradley-Terry/logit — cannot in principle capture correlated, person-specific preferences. It identifies a concrete data-collection fix (collecting best-of-three rather than pairwise data) and shows this fix is not optional but necessary, while quantifying the sample cost.

Real-world applications:

• Personalized recommendation: The MovieLens and Netflix results show that correlated probit models recover meaningful structure, such as sequels being positively correlated and critically acclaimed films being negatively correlated with blockbuster comedies.
• Menu and product design: The sushi dataset demonstrates that certain items (sea urchins) are highly divisive, which is directly relevant to product lines and menu curation.
• LLM alignment: Because best-of-three data captures correlations between responses, reward models trained this way can better represent heterogeneous user populations rather than a single averaged utility function.
• Welfare and assortment decisions: The paper frames the goal as predicting the welfare G(R) = max_{i∈R} X_i of a set of alternatives, which is what a planner needs when choosing which subset of options to offer.

Industry relevance: any organization collecting human preference data — LLM labs running RLHF annotation, streaming services, e-commerce, transportation and marketing teams that already use RUMs — faces the choice of what comparison format to collect. The paper argues this format choice, not just model capacity, determines whether correlation can ever be learned.

Future Directions

• Welfare maximization at scale: The experiments section introduces a welfare maximization experiment that chooses the welfare-maximizing subset of a fixed size, but the provided content truncates the setup and does not report results.
• Relaxing the observability assumption: Assumption 5.1 requires every three-way ordering to have probability at least γ, and the upper bound's dependence on γ is γ^{-24} in the sample complexity. Determining whether this dependence can be improved, or identifiability extended to cases where some orderings are nearly unobservable, is open.
• Practical data-collection design: Given that only Õ(n²) triples are needed rather than all O(n³), how to choose which triples to query to minimize annotation cost in a real pipeline is a natural follow-up.
• Relating the correlated probit to alternative RUMs: The paper contrasts the probit with the logit, which is the only RUM satisfying IIA, leaving open how these guarantees transfer to other correlated RUM families.

Target Audience

This paper is aimed at machine learning theorists and statisticians working on choice models, identifiability, and sample complexity, as well as RLHF and reward-modeling researchers who need to understand the theoretical limits of pairwise preference data. It is also relevant to practitioners in recommendation, marketing, and transportation who already use Random Utility Models and want to know what additional data formats buy them. Readers should be comfortable with multivariate normal distributions, order statistics, and minimax-style lower bound arguments; the proofs in the paper are not accessible to a general audience.

Authors’ abstract

Random Utility Models (RUMs) are a classical framework for modeling user preferences and play a key role in reward modeling for Reinforcement Learning from Human Feedback (RLHF). However, a crucial shortcoming of many of these techniques is the Independence of Irrelevant Alternatives (IIA) assumption, which collapses \emph{all} human preferences to a universal underlying utility function, yielding a coarse approximation of the range of human preferences. On the other hand, statistical and computational guarantees for models avoiding this assumption are scarce. In this paper, we investigate the statistical and computational challenges of learning a \emph{correlated} probit model, a fundamental RUM that avoids the IIA assumption. First, we establish that the classical data collection paradigm of pairwise preference data is \emph{fundamentally insufficient} to learn correlational information, explaining the lack of statistical and computational guarantees in this setting. Next, we demonstrate that \emph{best-of-three} preference data provably overcomes these shortcomings, and devise a statistically and computationally efficient estimator with near-optimal performance. These results highlight the benefits of higher-order preference data in learning correlated utilities, allowing for more fine-grained modeling of human preferences. Finally, we validate these theoretical guarantees on several real-world datasets, demonstrating improved personalization of human preferences.