The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
46,472 characters
Learning Correlated Reward Models: Statistical Barriers and Opportunities
\maketitle
\begin{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.
\end{abstract}
\section{Introduction}
\label{sec:introduction}
Random Utility Models (RUMs) \citep{train2009discrete} are the leading framework for modelling human preferences. Classical applications dating back to the 1960s include mathematical psychology \citep{luce1959individual}, transportation science \citep{ben1973structure}, econometrics \citep{mcfadden1980econometric}, and marketing \citep{rust1993customer}. More recently, they are a core component of the Reinforcement Learning from Human Feedback (RLHF) pipeline \citep{christiano2017deep}, used to align Large Language Models (LLMs) with human preferences. Unfortunately, many classical RUMs adopt the Independence of Irrelevant Alternatives (IIA) assumption. In the context of LLMs, the IIA posits a universal underlying utility function for all users of a system. A growing body of work highlights the limits of this approach in capturing the full range of human preferences \citep{constitutional_ai,open_problems_rlhf,pluralistic_alignment,foundational_challenges_rlhf,social_choice_rlhf}.
Formally, a RUM models utilities over a set of $n$ items as a high-dimensional random vector, $X$\footnote{For RLHF, the items correspond to (prompt, response) pairs}. A classical choice is the \emph{logit} model, where each component $X_i$ is independent and distributed according to a Gumbel distribution $X_i \ts \mrm{Gumbel} (\mu_i)$. The IIA assumption implies that for any unobserved item (or response), the model assigns the same average utility irrespective of the user's past preferences.
In this paper, we investigate the statistical challenges of learning correlated utility models, focusing in particular on the correlated probit model where $X \ts \mc{N} (\mu, \Sigma)$. By explicitly modeling correlations, these techniques allow past user behavior to inform future responses, providing a more accurate representation of human preferences. However, in contrast to the logit model, little is known about the statistical and computational challenges of learning these models: i) \emph{What data is needed to learn them?} and ii) \emph{How many samples do we need?}
We make key advancements on several fronts: 1) We show that the conventional paradigm of pairwise preference data is fundamentally insufficient to learn these models, 2) On the other hand, three-way-preference data is both necessary and sufficient and finally, 3) Validate the efficacy of higher-order preference data in accurately modelling correlated user preferences. Our results highlight fundamental drawbacks in conventional data collection pipelines and suggest deliberate amendments to address these shortcomings. Prior to our work, even \emph{identifiability} results, disregarding any statistical considerations, did not exist. Hence, we establish the \emph{first} identifiability guarantees and complement them with a near-optimal polynomial-time estimator.
\section{Related work}
A wealth of ideas exists for modeling rewards. However, we focus on choice modeling, where subjective \emph{preferences} between items are expressed. Consequently, we find a treatment of reward models like step-wise reward models \citep{havrilla2024glore} and process reward models \citep{luo2023wizardmath} beyond the scope of this work. We are interested in models that can make \emph{counterfactual} choices from preference data. Outside of machine learning, choice models have been successfully applied to planning problems like public transport scheduling \citep{wei2022transit}, effect of price markups \citep{gallego2014multiproduct}, airline scheduling \citep{wei2020airline}, EV charging station placement \citep{lamontagne2023optimising}, and toll placement \citet{osorio2021efficient}.
\emph{Random Utility Models (RUMs)} are among the most common models of human behavior in mathematical psychology, econometrics, transportation, and marketing \citep[e.g., see][a Nobel Prize lecture on RUMs]{mcfadden2001economic}. RUMs impose structure on the choice model by assuming that the agents are rational, meaning that when confronted with a finite set of \emph{alternatives}, they choose the one that maximizes their (latent) utility. The agent's unobserved utility is commonly modeled as a random variable to acknowledge the heterogeneity of utilities. Formally, an agent is assumed to have a random utility vector $X$, where $X_i$ is the utility of choosing some alternative $i$ from the set of all possible alternatives $\mathcal{C}$, and, when presented with a subset $\mathcal{R}\subseteq\mathcal{C}$ of alternatives, the agent chooses the alternative $I_\mathcal{R}$ satisfying
\begin{equation*}
I_\mathcal{R} \in \arg \max_{i\in\mathcal{R}} X_i.
\end{equation*}
Given observations of the form $(\mathcal{R}^t,I_{\mathcal{R}^t}^t)$, $t=1,\ldots,T$, a common challenge is to \emph{learn} the distribution of the latent $X$. Obtaining an estimate $\tilde{X}$ of $X$ not only gives us an estimate $\tilde{I}_\mathcal{R}$ of $I_\mathcal{R}$ for any subset of alternatives $\mathcal{R}$, but it also allows making predictions about the welfare of $\mathcal{R}$, $G(\mathcal{R}):=\max_{i\in\mathcal{R}} X_i$. It is important to note that learning the distribution of $X$ from preference data is inherently underconstrained as adding the same potentially stochastic value to all components of $X$ yields no change in the distribution of $I$.
The most popular RUM is the \emph{logit}~\citep[Chapter 3]{train2009discrete} or also sometimes referred to as Luce -Shephard-McFadden model, or, in the binary case (i.e. $|\mathcal{C}|=2$), the Bradley-Terry model. The logit is the only RUM that satisfies \emph{independence of irrelevant alternatives (IIA)}~\citep{luce1959individual}, that is, the ratio of the probabilities of choosing two alternatives is independent of the presence of other alternatives. The logit enjoys many useful properties, for instance, it can be learned using pairwise comparisons, it can learn any distribution over the set of full alternatives\footnote{by setting the utilities to the log probabilities}, and is easy to calculate via a softmax. Unfortunately, if the utilities are correlated, the logit cannot be used to make correct counterfactual predictions. A classical example showcasing this impossibility is the red bus/blue bus problem introduced by \cite{debreu1960individual}. If half of the populations prefer red buses over blue buses and half of the population prefers red buses made by company A over those made by company B, then IIA implies that 2/3 of the population prefers red buses made by A or B over blue buses, a contradiction. In practice, as shown by \citet{benson2016relevance}, many datasets do not satisfy the IIA assumption. We continue our discussion on choice modeling in Appendix~\ref{sec:prior_work}
\section{Problem Setup, and the Need for Best-Of-Three Observations}
\label{sec:prob_setup}
Here, we avoid the restrictive IIA assumption and assume, instead, that the utilities follow the classical probit model with $X \ts \mc{N} (\mu, \Sigma)$. We aim to recover $(\mu, \Sigma)$ from only the \emph{choices} $\arg\max_\lbrb{i\in\mathcal{R}} X_i$ made for various subsets $\mathcal{R} \subset \lsrs{n}$. For binary choice, $\mathcal{R}$ is pairs of elements $(i, j) \in \lsrs{n}^2$. Similarly, for the three-way choice setting, $\mathcal{R}$ is triplets $(i, j, k)\in \lsrs{n}^3$. Note that $(\mu, \Sigma)$ are not fully identifiable in this setting: for any $X \ts \mc{N} (\mu, \Sigma)$, $X'$ defined as $$t\lprp{X - \frac{1}{n}\sum_i X_i},$$ for \emph{any} $t > 0$, induces the same ranking probabilities.
Hence, we adopt the following necessary normalization $\mu, \Sigma$.
\begin{assumption}
\label{def:universal_symmetries}
For $X\thicksim\mathcal{N}(\mu,\Sigma)$, we assume, without changing the choice distributions, that
\begin{equation*}
\inp{\mu}{\Ind}=0, \quad \Sigma\Ind = 0\text{, and} \quad \Tr(\Sigma)=n.
\end{equation*}
Consequently, $X$ lives on the hyperplane $\Ind^\top X=0$. Furthermore, we assume $\Sigma$ has rank $n-1$.
\end{assumption}
Unfortunately, the classical paradigm of pairwise comparisons ($|\mathcal{R}|=2$) is insufficient for recovering $(\mu, \Sigma)$, even accounting for \cref{def:universal_symmetries}. Its proof is deferred to \cref{ssec:proof_two_not_enough}.
\begin{restatable}{theorem}{twonotenough}
\label{thm:two_not_enough}
For any $n \geq 3$ and $\mu, \Sigma$ satisfying \cref{def:universal_symmetries}, there exists an infinite set $\mathcal{S}$:
\begin{equation*}
\forall i, j \in [n], \mu', \Sigma' \in \mathcal{S}: \Pr_{X \ts \mc{N} (\mu, \Sigma)} \lbrb{X_i \geq X_j} = \Pr_{X \ts \mc{N} (\mu', \Sigma')} \lbrb{X_i \geq X_j}.
\end{equation*}
\end{restatable}
\cref{thm:two_not_enough} indicates that pairwise comparison data is fundamentally unable to account for correlations in the probit model. While the full proof of \cref{thm:two_not_enough} is somewhat involved, the particular setting with $\mu = 0$ is instructive. Here, observe that for \emph{any} pair of distinct alternatives, $i, j$, the probability that $X_i \geq X_j$ is $1/2$ \emph{irrespective} of the value of $\Sigma$. Hence, correlational information is fundamentally impossible to learn given only access to pairwise comparisons.
\section{Identifiability}
\label{sec:ident}
\cref{thm:two_not_enough} prompts the natural question: \emph{can higher order preference data help?}
We answer the question in the affirmative and show that best-of-three observations (\cref{thm:mu_sigma_ident_multiple_items}) are sufficient \emph{and} from \cref{thm:two_not_enough}, necessary to recover $\mu, \Sigma$. Observing that:
\begin{equation*}
\Pr \lbrb{X_i \geq X_j \geq X_k} = \Pr \lbrb{X_j \geq X_k} - \Pr \lbrb{X_j \geq X_i, X_k}, \tag{RANK-PROB} \label{eq:rank_probs}
\end{equation*}
we may assume access to three-way \emph{ranking} probabilities.
\subsection{The Case of Three Alternatives}
\label{ssec:ident_three_comp}
As a stepping stone towards identifying probit models with an arbitrary number $n$ of alternatives, we focus on the case $n=3$ and establish the following theorem.
\begin{theorem}
\label{thm:mu_sigma_ident_three_items}
$(\mu, \Sigma)$ are uniquely identifiable from the three-way observation probabilities.
\end{theorem}
This result will serve as the basis for the general case in \cref{ssec:ident_multiple_comp}.
A probit model satisfying the constraints in \cref{def:universal_symmetries} defines a \emph{bivariate} normal distribution that lies in the plane defined by $\bm 1^\top X = 0$. We start by projecting the utilities onto a lower-dimensional space:
\begin{equation}\label{eq:projection}
\begin{bmatrix}
V_1 \\ V_2
\end{bmatrix} \coloneqq \underbrace{\begin{bmatrix}
1/\sqrt{6} & 1/\sqrt{6} & -2/\sqrt{6}\\
1/\sqrt{2} & -1/\sqrt{2} & 0
\end{bmatrix}}_{=:\ P} \begin{bmatrix}
X_1 \\ X_2 \\ X_3
\end{bmatrix} \quad \leftrightarrow \quad
\begin{bmatrix}
X_1 \\ X_2 \\ X_3
\end{bmatrix} = \underbrace{\begin{bmatrix}
1 / {\sqrt 6} & 1 / {\sqrt 2} \\
1 / {\sqrt 6} & - 1 / {\sqrt 2} \\
-2/{\sqrt 6} & 0\\
\end{bmatrix}}_{=:\ P^\top}\begin{bmatrix}V_1 \\ V_2\end{bmatrix}.
\end{equation}
Under the transformation $P$, the probit model $X \sim \mc N (\mu, \Sigma)$ is mapped to some bivariate normal distribution $V \sim \mc N (\dot{\mu}, \dot{\Sigma})$.
Upon identification of the parameters $\dot{\mu}$ and $\dot{\Sigma}$ in two dimensions, we recover the original parameters $\mu$ and $\Sigma$ through the transformation:
\[
\mu = P^\top \dot{\mu}, \qquad \text{and}\quad \Sigma = P^\top \dot{\Sigma} P.
\]
Defining,
\[
c_1 := \begin{bmatrix}
0 \\ 1
\end{bmatrix},\qquad
c_2 := \begin{bmatrix}
\sqrt3/2 \\ -1/2
\end{bmatrix},\qquad
c_3 := \begin{bmatrix}
\sqrt3/2 \\ 1/2
\end{bmatrix},
\]
the probability of the events $\{X_i \geq X_j\}$, are satisfy the following:
\[
\Pr\{X_1 \ge X_2\} = \Pr\{c_1^\top V \ge 0\}, \quad
\Pr\{X_2 \ge X_3\} = \Pr\{c_2^\top V \ge 0\}, \quad
\Pr\{X_1 \ge X_3\} = \Pr\{c_3^\top V \ge 0\},
\]
with each three-way permutation corresponding to the intersections of the corresponding halfspaces. The projection and the partitioning of the 2-dimensional space are illustrated in \cref{fig:cones}.
\begin{figure}[t]
\centering
\includegraphics[width=.7\linewidth]{figures/three_choices.pdf}
\raisebox{2.4cm}{\scalebox{.8}{\begin{tabular}{ll}
& \bf Event \\
\toprule
\circled{1} & $X_1 \ge X_2 \ge X_3$ \\
\circled{2} & $X_1 \ge X_3 \ge X_2$ \\
\circled{3} & $X_3 \ge X_1 \ge X_2$ \\
\circled{4} & $X_3 \ge X_2 \ge X_1$ \\
\circled{5} & $X_2 \ge X_3 \ge X_1$ \\
\circled{6} & $X_2 \ge X_1 \ge X_3$ \\
\end{tabular}}}
\caption{The probabilities $\Pr \lbrb{X_i \geq X_j \geq X_k}$, for permutations, $(i,j,k)$, of $\{1,2,3\}$, correspond to the probability mass in each of the six slices of the plane denoted \circled{1} through \circled{6}.}
\label{fig:cones}
\end{figure}
We will further transform $V$, rendering the distribution \emph{isotropic}. Define $\dot{\Sigma}^{-1/2}$ as \emph{a} solution of
\begin{equation*}
\dot{\Sigma}^{-1/2} \dot{\Sigma} (\dot{\Sigma}^{-1/2})^\top = I.
\end{equation*}
Note that $\dot{\Sigma}^{-1/2}$ is unique up to an orthonormal transformation on the left. We will fix a convenient choice subsequently. For now, observe that $\dot{\Sigma}^{-1/2}$ and $\dot{\Sigma}^{1/2} \coloneqq ((\dot{\Sigma}^{-1/2})^{-1})^\top$ satisfy:
\begin{equation*}
\forall x_1, x_2 \in \R^2: \inp{x_1}{x_2} = \inp{\dot{\Sigma}^{1/2} x_1}{\dot{\Sigma}^{-1/2} x_2}.
\end{equation*}
Setting $x_1 = c_i$ and $x_2 = V$, we now observe:
\begin{equation*}
\inp{\dot{\Sigma}^{1/2} c_i}{\dot{\Sigma}^{-1/2} V} \text{ with } \dot{\Sigma}^{-1/2} V \thicksim \mc{N} (\wt{\mu}, I) \text{ where } \wt{\mu} \coloneqq \dot{\Sigma}^{-1/2} \dot{\mu}.
\end{equation*}
Lastly, note that:
\begin{equation*}
\forall i \in [3]: \inp{c_i}{V} \geq 0 \iff \inp{\wt{c}_i}{\dot{\Sigma}^{-1/2} V} \geq 0 \text{ where } \wt{c}_i \coloneqq \frac{\dot{\Sigma}^{1/2} c_i}{\norm{\dot{\Sigma}^{1/2} c_i}}.
\end{equation*}
Note that $\dot{\Sigma}^{-1/2} V$ is isotropic. Defining,
\begin{equation*}
\alpha_i \coloneqq \wt{c}_i^\top \wt{\mu} \text{ and } \alpha_{ij} \coloneqq \wt{c}_i^\top \wt{c}_j,
\end{equation*}
Our first technical result identifies $\alpha_i$ from observational data.
\begin{lemma}
\label{lem:rec_ct_proj}
The quantities $\alpha_i$ are identifiable from three-way ranking probabilities.
\end{lemma}
\begin{proof}
Note that
\begin{equation*}
\P \lbrb{c_i^\top V \geq 0} =
\P \lbrb{\inp{\Sigma^{-1/2} V}{\wt{c}_i} \geq 0} =
\P_{g \thicksim \mc{N} (0, 1)} \lbrb{g + \inp{\wt{c}_i}{\wt{\mu}} \geq 0} = \Phi (\inp{\wt{c}_i}{\wt{\mu}}).
\end{equation*}
As $\Phi(\cdot)$ is a strictly increasing function, $\inp{\wt{c}_i}{\wt{\mu}}$ is recoverable from the observables.
\end{proof}
\NewDocumentCommand\deins{}{\alpha_i}
\NewDocumentCommand\dzwei{}{\alpha_j}
In the next lemma, we use the values $\alpha_i$ from \cref{lem:rec_ct_proj} to establish a monotonic relationship between $\inp{\wt{c}_i}{\wt{c}_j}$ and the probability of the events in \cref{fig:cones}. However, the precise choice of events depends on the $\alpha_i$. Note that for any distinct $i, j \in [3]$, there exist signings $s_i, s_j \in \{\pm 1\}$ such that $s_i \inp{\wt{c}_i}{\wt{\mu}}, s_j \inp{\wt{c}_j}{\wt{\mu}} \geq 0$ and the events $\lbrb{s_i \inp{\wt{c}_i}{\dot{\Sigma}^{-1/2} V}, s_j \inp{\wt{c}_j}{\dot{\Sigma}^{-1/2} V} \leq 0}$ correspond to combinations of one or more events in \cref{fig:cones} and is hence, observable. By instantiating the subsequent lemma with the signed vectors $s_i \wt{c}_i, s_j \wt{c}_j$, we recover the $\alpha_{ij}$ by relating it to the probability of the event $\lbrb{s_i \inp{\wt{c}_i}{\dot{\Sigma}^{-1/2} V}, s_j \inp{\wt{c}_j}{\dot{\Sigma}^{-1/2} V} \leq 0}$. Its proof is deferred to \cref{ssec:proof_recangconv}.
\begin{restatable}{lemma}{recangconv}
\label{lem:rec_ang_conv}
Let $v_1, v_2 \in \R^2$ be two independent unit vectors and $\xi \in \R^2$ be such that $d_1 \coloneqq \inp{v_1}{\xi}, d_2 \coloneqq \inp{v_2}{\xi} \geq 0$. Then,
\begin{equation*}
\alpha_{12} \coloneqq \inp{v_1}{v_2}
\end{equation*}
is identifiable from $d_1, d_2,$ and
\begin{equation*}
\gamma_{12} \coloneqq \P \lbrb{\inp{X}{v_1}, \inp{X}{v_2} \leq 0} \text{ for } X \ts \mc{N} (\xi, I).
\end{equation*}
\end{restatable}
\begin{proof}[Proof of \cref{thm:mu_sigma_ident_three_items}]
We will show that $\dot{\Sigma}^{1/2}$ is recoverable from the observation probabilities. $\dot{\Sigma}$ is then obtainable from the fact that $\dot{\Sigma} = (\dot{\Sigma}^{1/2})^\top \dot{\Sigma}^{1/2}$. From \cref{lem:rec_ct_proj}, we recover $\alpha_i =\inp{\wt{c}_i}{\wt{\mu}}$ for $i \in [3]$ and from \cref{lem:rec_ang_conv}, we recover $\alpha_{ij}=\inp{\wt{c_i}}{\wt{c_j}}$ for $i\neq j \in [3]$.
Without loss of generality, we assume that for some $s, t > 0$ by relaxing the scale constraint $\Tr \dot{\Sigma}=1$:
\begin{equation}
\label{eq:wtc_wlog_rep}
\dot{\Sigma}^{1/2} c_1 =
\begin{bmatrix}
1 \\
0
\end{bmatrix},\quad
\dot{\Sigma}^{1/2} c_2 = s
\begin{bmatrix}
\alpha_{12} \\
\sqrt{1 - \alpha^2_{12}}
\end{bmatrix},\quad
\dot{\Sigma}^{1/2} c_3 = t
\begin{bmatrix}
\alpha_{13} \\
\sqrt{1 - \alpha_{13}^2}
\end{bmatrix}.
\end{equation}
The signs of the second component of the vector are determined by fixing the sign of $\dot{\Sigma}^{1/2} c_2$ (this is an orthonormal transformation) and for $\dot{\Sigma}^{1/2} c_3$, follows from the fact that $c_3 = c_1 + c_2$. Noting that $\alpha_{13} \neq \alpha_{12}$ (as otherwise, we obtain permutation observations with $0$ probability), we obtain:
\begin{equation*}
\begin{bmatrix}
1 \\
0
\end{bmatrix} +
s
\begin{bmatrix}
\alpha_{12} \\
\sqrt{1 - \alpha^2_{12}}
\end{bmatrix} = t
\begin{bmatrix}
\alpha_{13} \\
\sqrt{1 - \alpha_{13}^2}
\end{bmatrix}
\implies
\begin{bmatrix}
1 \\
0
\end{bmatrix} =
\begin{bmatrix}
\alpha_{13} & \alpha_{12} \\
\sqrt{1 - \alpha_{13}^2} & \sqrt{1 - \alpha^2_{12}}
\end{bmatrix}
\begin{bmatrix}
t \\
-s
\end{bmatrix}.
\end{equation*}
Since the above forms an invertible system, we obtain the values of $s, t > 0$. This now enables the recovery of $\dot{\Sigma}$ (and consequently, $\Sigma$) via the invertible system:
\begin{equation*}
\dot{\Sigma}^{1/2} \cdot
\begin{bmatrix}
c_1 & c_2
\end{bmatrix}
=
\begin{bmatrix}
1 & s\alpha_{12} \\
0 & s \sqrt{1 - \alpha_{12}^2}
\end{bmatrix}
\end{equation*}
To recover $\dot{\mu}$, note that $\wt{c}_1$ and $\wt{c}_2$ form a basis for $\R^2$ and observing that these are determined by \cref{eq:wtc_wlog_rep}, we identify $\wt{\mu}$. Noting that $\dot{\Sigma}^{-1/2} \dot{\mu} = \wt{\mu}$, we recover $\dot{\mu}$ and $\mu$ by our previous discussion.
\end{proof}
\subsection{Identifiability: More Than Three Alternatives}
\label{ssec:ident_multiple_comp}
We now utilize \cref{thm:mu_sigma_ident_three_items} to establish identifiability for an arbitrary number of alternatives, $n$. \cref{thm:mu_sigma_ident_three_items} recovers $\mu, \Sigma$ restricted to tuples of $3$ alternatives up to the symmetries in \cref{def:universal_symmetries}. However, the sub-matrices of $\mu, \Sigma$ (or more precisely, $\mu$ and $\Sigma$ restricted to these alternatives) could potentially violate these assumptions. Hence, we establish that there is a \emph{unique} pair, $\mu, \Sigma$, consistent with the equivalence class of parameters identified by \cref{thm:mu_sigma_ident_three_items} for all choices of $3$ alternatives. In what follows, we will use $\bar{\mu}_{ijk}$ and $\bar{\Sigma}_{ijk}$ to denote the parameters $\mu$ and $\Sigma$ restricted to the tuple $i, j$ and $k$, projected onto the two-dimensional subspace orthogonal to $\bm{1}$.
\begin{theorem}
\label{thm:mu_sigma_ident_multiple_items}
$\mu, \Sigma$ are uniquely identifiable from the three-way observation probabilities.
\end{theorem}
\begin{proof}
First, note for any distinct indices $i, j, k$, \cref{thm:mu_sigma_ident_three_items} yields $\wt{\mu}_{ijk}, \wt{\Sigma}_{ijk}$ satisfying:
\begin{gather*}
t_{ijk} \wt{\mu}_{ijk} = \bar{\mu}_{ijk} \text{ and }
t_{ijk}^2 \wt{\Sigma}_{ijk} = \bar{\Sigma}_{ijk}
\end{gather*}
for some scaling $t_{ijk} > 0$. Denoting $c_{ij} = e_i - e_j$, we have:
\begin{equation*}
c_{ij}^\top t_{ijk}^2 \wt{\Sigma}_{ijk} c_{ij} = c_{ij}^\top \bar{\Sigma}_{ijk} c_{ij} = c_{ij}^\top \Sigma c_{ij} \implies t_{ijk}^2 = \frac{c_{ij}^\top \Sigma c_{ij}}{c_{ij}^\top \wt{\Sigma}_{ijk} c_{ij}}.
\end{equation*}
The first step uses the fact that $c_{ij}^\top\bar{\Sigma}_{ijk}c_{ij}=c_{ij}^\top\Sigma_{ijk}c_{ij}$. Since scaling $\Sigma$ (and $\mu$) produces the same solution, we may assume without loss of generality that $t_{123} = 1$. Noting that this allows the recovery of $c_{12}^\top \Sigma c_{12}$, the above equality enables determination of the $t_{12k}$ for all $k \in [n]$. This further enables the determination of $t_{1jk}$ for all distinct $k, j \in [n]$. Another application of the argument finally yields the values of $t_{ijk}$ for all distinct $i, j, k \in [n]$.
Furthermore, observe that for all distinct $i, j, k \in [n]$ with $\sigma_{ij} \coloneqq \Sigma_{ij}$:
\begin{equation*}
c_{ij}^\top t_{ijk}^2 \wt{\Sigma}_{ijk} c_{ij} = c_{ij}^\top \Sigma c_{ij} = \sigma_{ii} + \sigma_{jj} - 2 \sigma_{ij}.
\end{equation*}
Furthermore, noting that $c_{ii} = \bm{0}$, we determine $\alpha_{ij} = c_{ij}^\top \Sigma c_{ij}$ for all $i, j \in [n]$. Observe that
\begin{equation*}
\sum_{j = 1}^n c_{ij}^\top \Sigma c_{ij} = n \sigma_{ii} + \Tr (\Sigma) - 2 \sum_{j = 1}^n \sigma_{ij} = n \sigma_{ii} + \Tr (\Sigma).
\end{equation*}
where the last step is due to fact that $\bm{1}^\top\mu = 0, \Sigma \bm{1} = \bm{0}$. By further summing over $i$, we get
\begin{equation*}
\sum_{i = 1}^n \sum_{j = 1}^n c_{ij}^\top \Sigma c_{ij} = n \Tr (\Sigma) + n \Tr (\Sigma)
\end{equation*}
which now enables recovery of $\Tr (\Sigma)$ and from the above discussion $\sigma_{ii}$ and consequently, $\sigma_{ij}$ for all $i, j$. Hence, we have identified $\Sigma$. For the mean, observe again the following:
\begin{equation*}
c_{ij}^\top (t_{ijk} \wt{\mu}_{ijk}) = c_{ij}^\top \bar{\mu}_{ijk} = \mu_{i} - \mu_{j}.
\end{equation*}
The last step is valid because all of the elements of $\mu_{ijk}$ were shifted by the same amount to obtain $\bar{\mu}_{ijk}$, and consequently, their difference did not change.
Since $t_{ijk}$ are determined, this determines $\mu_1 - \mu_j$ for all $j$ (note the choice of $\mu_1$ is arbitrary). Letting $\beta_j = \mu_1 - \mu_j$, we have:
\begin{equation*}
\sum_{j = 1}^n \beta_j = n \mu_1 - \sum_{j = 1}^n \mu_j = n \mu_1.
\end{equation*}
This determines $\mu_1$ and, consequently, the remaining $\mu_j$. This concludes the proof as $(\mu, \Sigma)$ have been recovered up to the universal symmetries previously described.
\end{proof}
\section{Finite-sample Guarantees: Upper and Lower Bounds}
\label{sec:finite_sample}
In this section, we extend our \emph{identifiability} results \cref{sec:ident} to \emph{estimation}. The key conceptual advancement over \cref{sec:ident} is in the aggregation procedure which combines the standardized estimators of the $3$ item setting (\cref{ssec:ident_three_comp}) into a solution for the $n$ item setting (\cref{ssec:ident_multiple_comp}). The procedure described in \cref{ssec:ident_multiple_comp} is wasteful as it requires estimating \emph{all} $3 \times 3$ sub-matrices of $\Sigma$, resulting in a total of $O(n^3)$ total $3 \times 3$ matrices. We show that this can be substantially improved upon using a much smaller number ($\wt{O}(n^2)$) of sub-matrices in \cref{thm:est_multiple_items}. We then establish a statistical \emph{lower bound} demonstrating the near-optimality of our estimator. We start with our estimation guarantees. In addition to \cref{def:universal_symmetries}, we require the following assumption:
\begin{restatable}{assumption}{obserabilityestimation}{(Observability)}
\label{as:observability_estimation}
For any three alternatives $i, j, k \in [n]$ and $X \ts \mc{N} (\mu, \Sigma)$:
\begin{equation*}
\Pr \lbrb{i > j > k} \geq \gamma
\end{equation*}
for some $\gamma > 0$.
\end{restatable}
Intuitively, \cref{as:observability_estimation} avoids worst-case scenarios where an overwhelming difference in utilities renders a choice unobservable, making some parameters impossible to estimate.
We now state our main estimation guarantee for the general $n$-item setting.
\begin{restatable}{theorem}{estmultitems}
\label{thm:est_multiple_items}
Let $(\mu^*, \Sigma^*)$ satisfy \Cref{def:universal_symmetries,as:observability_estimation} with $\Tr (\Sigma^*) = n$. Then, for any $\eps, \delta \in (0, 1/2]$, given there is a polynomial time algorithm which when allowed $N$ observations of rank-$3$ permutations from $\mrm{Choice} (\mu^*, \Sigma^*)$ of its choice, returns estimates, $(\wb{\mu}, \wb{\Sigma})$, satisfying:
\begin{gather*}
\norm{\wb{\mu} - \mu^*}_\infty \leq \eps \text{ and } \norm{\wb{\Sigma} - \Sigma^*}_\infty \leq \eps
\end{gather*}
with probability at least $1 - \delta$ as long as $N \geq C n^2 \eps^{-2} \gamma^{-24} \log (n / \delta) \log^6 (n / (\gamma\eps))$.
\end{restatable}
Next, we present a lower bound that shows that \cref{thm:est_multiple_items} is near-optimal. We introduce some notation before proceeding. An estimator, $T$, is parameterized by a set of tuples $\{((i, j, k), N_{ijk}): i, j, k \in [n],\, i \neq j \neq k \neq i\}$. The estimator then obtains $N_{ijk}$ samples from $\mrm{Choice} (\mu^*_{ijk}, \Sigma^*_{ijk})$ for each $i, j, k$ and outputs estimates $(\wb{\mu}, \wb{\Sigma})$. Furthermore, we denote:
\begin{equation*}
N_{ij} \coloneqq \sum_{k} N_{ijk}.
\end{equation*}
As before, we adopt \cref{def:universal_symmetries} for normalization and state our main lower bound below.
\begin{restatable}{theorem}{statlbkl}
\label{thm:stat_lb_kl}
Let $n \in \N$, $\delta, \eps \in (0, 2^{-4})$. For any estimator $T$ parameterized by $\{((i, j, k), N_{ijk})\}_{i \neq j \neq k \neq i}$ such that $N_{i^*, j^*} \leq \eps^{-2} \log (1 / \delta) / 4$ for \emph{some} $i^* \neq j^* \in [n]$, there exist two choice models, parameterized by $(\bm{0}, \Sigma^1)$ and $(\bm{0}, \Sigma^2)$ with:
\begin{equation*}
\Tr (\Sigma^1) = \Tr (\Sigma^2) = n \text{ and } \norm{\Sigma^1 - \Sigma^2}_\infty \geq \eps,
\end{equation*}
satisfying:
\begin{equation*}
\max_{\Sigma \in \{\Sigma^1, \Sigma^2\}} \P_{\bm{X} \ts (T, \mrm{Choice} (\bm{0}, \Sigma))} \lbrb{\norm{T(\bm{X}) - \Sigma}_\infty \geq \frac{\eps}{4}} \geq \delta.
\end{equation*}
\end{restatable}
We pause for a few remarks. Firstly, note that each pair $(i, j)$ must appear in at least $\Omega(\eps^{-2})$ experiments. Since each sample only accounts for $O(1)$ pairs, this result implies a lower bound of $\Omega (n^2)$ on the number of unique experiments for any successful estimator matching \cref{thm:est_multiple_items}. Finally, note that this argument also implies that the total number of samples is at least $\Omega (n^2 \eps^{-2} \log (1 / \delta))$ again matching \cref{thm:est_multiple_items} in terms of $n, d, \text{ and } \delta$.
\begin{figure}
\centering
\includegraphics[width=0.18\linewidth]{figures/probit2_syn_mu_0-si_rI_8_0_2025-09-22-00_56_21-7b9d4d54-9770-11f0-8eac-83e8fce7dfe9-00003-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/probit2_syn_mu_0-si_rI_8_0_2025-09-23-13_59_13-0394cafc-98a7-11f0-b0a3-ffe7a0390291-00003-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/mu_0-si_rI_8_0-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/probit3_syn_mu_0-si_rI_8_0_2025-09-22-03_34_34-95b672a4-9786-11f0-ad8d-993a936f12e9-00003-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/probit3_syn_mu_0-si_rI_8_0_2025-09-23-04_08_12-7318ed2a-9854-11f0-9442-5dd5eabf6598-00003-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/probit2_syn_mu_r-si_r_8_0_2025-09-22-03_13_31-a506fb82-9783-11f0-a4a7-41fe62f2c2bc-00003-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/probit2_syn_mu_r-si_r_8_0_2025-09-23-01_59_00-66b0c358-9842-11f0-9e61-6d31acc2e1cb-00003-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/mu_r-si_r_8_0-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/probit3_syn_mu_r-si_r_8_0_2025-09-22-01_44_18-2e3a302a-9777-11f0-9bc8-1d3cd0a6473b-00003-si.pdf}
\includegraphics[width=0.18\linewidth]{figures/probit3_syn_mu_r-si_r_8_0_2025-09-23-01_59_00-66affa0e-9842-11f0-8959-fdd628edd2c6-00003-si.pdf}
\caption{Center: ground truth covariance matrix, two figures on the right, covariance matrix learned from best-of-three observations, two figure on the left, covariance matrix learned from pairwise comparisons. We reproduce larger version these plots in Appendix~\ref{sec:impl}.}
\label{fig:syn}
\end{figure}
\section{Experiments}
We empirically evaluate modeling correlations\footnote{Code is available at \url{https://github.com/SobhanMP/lcorr}}. We use datasets of ratings and rankings. In rating datasets users are asked to assign a numerical value to alternatives. In contrasts, ranking datasets contain the ordered list of preferences. We convert rankings to ratings and vice versa by using the index as rating and assuming alternatives with higher ratings are preferred over alternatives with lower ratings. The data gathering process can either be organic i.e., users rate movies they watch, or structured, every user ranks all food items on the menu.
We use two types of models on these datasets: RUMs and matrix completion models, both trained with gradient based methods. For RUMs, we use logit and probit models learned from two way comparisons and probit models learned from three way comparisons. In all cases we use the maximum likelihood estimate. RUMs do not take the user as input and directly create a model for the population. Matrix completion \citep{koren2009matrix} learns the ratings for all users in the training set, we then use the counts of users in the training set to approximate the probability of certain events. For sanity checks, we include a model we refer to as direct, which is similar to matrix completion, except we compute the desired quantities directly on the training set. We argue that this model is unrealistic in some scenarios, for instance where the set of alternative and user is large or when the ratings are grouped but anonymous. Still, since these matrix completion models the whole population, we expect them to be able to learn correlated preferences.
In the first set of experiments we sample six choices from a user, we present the ranking of four of the alternatives as context and predict the preference over the remaining two alternatives.
We start with synthetic data sampled from probit model as we can compare our results to the ground truth. In Figure~\ref{fig:syn}, we show the recovered covariance matrices with pairwise and best-of-three observations using a probit RUM. We can see that the model learned from pairwise comparisons learns nonexistent correlations in the uncorrelated case while in the correlated case, initialization can play an important role as apparent by the change in value in the first cell of the second row. We report the performance in Table~\ref{tab:syn}. The location $\mu$ can either be zero or sampled randomly, the covariance matrix can either be the identity matrix I, diagonal random rI, plus minus one bin, and random r. In all cases the best-of-three probit matches the performance direct method (with simulation).
\begin{table}[]
\centering
\tiny
\begin{tabular*}{\linewidth}{@{\extracolsep{\fill}}llrrrrrrrrrrrr}
\toprule
\multicolumn{2}{c}{structure} &
\multicolumn{3}{c}{logit} &
\multicolumn{3}{c}{matrix completion} &
\multicolumn{3}{c}{probit (pairwise)} &
\multicolumn{3}{c}{probit (best-of-three)} \\
\multicolumn{2}{c}{} &
\multicolumn{3}{c}{accuracy quantile} &
\multicolumn{3}{c}{accuracy quantile} &
\multicolumn{3}{c}{accuracy quantile} &
\multicolumn{3}{c}{accuracy quantile} \\
\cmidrule(lr){3-5}
\cmidrule(lr){6-8}
\cmidrule(lr){9-11}
\cmidrule(lr){12-14}
$\mu$ & $\Sigma$ & 0.25 & 0.50 & 0.75 & 0.25 & 0.50 & 0.75 & 0.25 & 0.50 & 0.75 & 0.25 & 0.50 & 0.75 \\
\midrule\addlinespace[2.5pt]
0 & I & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 \\
0 & bin & 0.50 & 0.50 & 0.50 & 0.78 & 0.78 & 0.78 & 0.45 & 0.50 & 0.54 & 0.79 & 0.79 & 0.79 \\
0 & rI & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.51 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 & 0.50 \\
0 & r & 0.50 & 0.50 & 0.50 & 0.67 & 0.67 & 0.67 & 0.47 & 0.51 & 0.55 & 0.67 & 0.67 & 0.67 \\
r & I & 0.70 & 0.70 & 0.71 & 0.68 & 0.70 & 0.70 & 0.66 & 0.66 & 0.67 & 0.68 & 0.70 & 0.70 \\
r & bin & 0.79 & 0.79 & 0.80 & 0.94 & 0.95 & 0.95 & 0.95 & 0.95 & 0.95 & 0.94 & 0.95 & 0.95 \\
r & rI & 0.72 & 0.72 & 0.72 & 0.71 & 0.71 & 0.72 & 0.69 & 0.70 & 0.71 & 0.70 & 0.70 & 0.72 \\
r & r & 0.63 & 0.63 & 0.64 & 0.71 & 0.71 & 0.71 & 0.67 & 0.68 & 0.69 & 0.71 & 0.71 & 0.71 \\
\bottomrule
\end{tabular*}
\caption{Accuracy of different methods on the synthetic dataset. Notice how the direct method matches best-of-three probit.}
\label{tab:syn}
\centering
\small
\begin{adjustbox}{width=1\textwidth}
\begin{tabular}{lrlrrrrrrrrrrrrrrr}
\toprule
\multicolumn{3}{c}{} & \multicolumn{3}{c}{logit} & \multicolumn{3}{c}{matrix completion} & \multicolumn{3}{c}{direct} & \multicolumn{3}{c}{probit (pairwise)} & \multicolumn{3}{c}{probit (best-of-three)} \\
\multicolumn{3}{c}{} & \multicolumn{3}{c}{accuracy quantile} & \multicolumn{3}{c}{accuracy quantile} & \multicolumn{3}{c}{accuracy quantile} & \multicolumn{3}{c}{accuracy quantile} & \multicolumn{3}{c}{accuracy quantile} \\
\cmidrule(lr){4-6} \cmidrule(lr){7-9} \cmidrule(lr){10-12} \cmidrule(lr){13-15} \cmidrule(lr){16-18}
dds. & var. & feat. & 0.25 & 0.50 & 0.75 & 0.25 & 0.50 & 0.75 & 0.25 & 0.50 & 0.75 & 0.25 & 0.50 & 0.75 & 0.25 & 0.50 & 0.75 \\
\midrule\addlinespace[2.5pt]
jokes & onehot & onehot & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.62 & 0.63 & 0.59 & 0.59 & 0.59 & 0.61 & 0.61 & 0.61 \\
ml & 1k & llm & 0.57 & 0.57 & 0.57 & 0.59 & 0.59 & 0.60 & 0.57 & 0.57 & 0.58 & 0.56 & 0.56 & 0.56 & 0.57 & 0.57 & 0.57 \\
ml & 10k & llm & 0.59 & 0.59 & 0.59 & 0.60 & 0.60 & 0.60 & 0.60 & 0.60 & 0.60 & 0.57 & 0.57 & 0.57 & 0.59 & 0.59 & 0.59 \\
ml & 50k & llm & 0.59 & 0.59 & 0.59 & 0.58 & 0.58 & 0.58 & 0.59 & 0.59 & 0.60 & 0.55 & 0.55 & 0.56 & 0.59 & 0.59 & 0.59 \\
ml & 1k & onehot & 0.62 & 0.62 & 0.62 & 0.60 & 0.60 & 0.60 & 0.57 & 0.58 & 0.58 & 0.60 & 0.60 & 0.60 & 0.61 & 0.61 & 0.62 \\
ml & 10k & onehot & 0.61 & 0.61 & 0.61 & 0.60 & 0.60 & 0.60 & 0.58 & 0.59 & 0.59 & 0.59 & 0.59 & 0.59 & 0.61 & 0.61 & 0.61 \\
ml & 50k & onehot & 0.59 & 0.59 & 0.59 & 0.58 & 0.58 & 0.58 & 0.58 & 0.58 & 0.59 & 0.55 & 0.55 & 0.56 & 0.59 & 0.59 & 0.60 \\
nf & 10k & llm & 0.59 & 0.59 & 0.59 & 0.59 & 0.59 & 0.59 & 0.56 & 0.56 & 0.57 & 0.58 & 0.58 & 0.58 & 0.59 & 0.59 & 0.59 \\
nf & 100k & llm & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.59 & 0.59 & 0.59 & 0.61 & 0.61 & 0.61 \\
nf & 150k & llm & 0.61 & 0.61 & 0.61 & 0.60 & 0.60 & 0.60 & 0.60 & 0.60 & 0.61 & 0.56 & 0.56 & 0.56 & 0.61 & 0.61 & 0.61 \\
nf & 10k & onehot & 0.61 & 0.61 & 0.62 & 0.59 & 0.59 & 0.59 & 0.57 & 0.57 & 0.57 & 0.59 & 0.59 & 0.60 & 0.61 & 0.61 & 0.61 \\
nf & 100k & onehot & 0.62 & 0.62 & 0.62 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.61 & 0.59 & 0.59 & 0.59 & 0.62 & 0.62 & 0.62 \\
nf & 150k & onehot & 0.61 & 0.61 & 0.61 & 0.60 & 0.60 & 0.61 & 0.59 & 0.60 & 0.60 & 0.56 & 0.56 & 0.56 & 0.61 & 0.61 & 0.61 \\
sushi & B & default & 0.65 & 0.65 & 0.65 & 0.66 & 0.66 & 0.66 & 0.51 & 0.51 & 0.51 & 0.64 & 0.64 & 0.64 & 0.65 & 0.65 & 0.65 \\
sushi & A & onehot & 0.65 & 0.66 & 0.66 & 0.67 & 0.67 & 0.68 & 0.68 & 0.68 & 0.68 & 0.65 & 0.65 & 0.65 & 0.68 & 0.68 & 0.68 \\
sushi & B & onehot & 0.67 & 0.67 & 0.68 & 0.67 & 0.68 & 0.68 & 0.50 & 0.50 & 0.50 & 0.66 & 0.66 & 0.66 & 0.67 & 0.67 & 0.68 \\
\bottomrule
\end{tabular}
\end{adjustbox}
\caption{Prediction accuracy for different model and datasets. The column labeled ``var.'' denotes the variants. For movie datasets, nf (Netflix) and ml (MovieLens) the number denotes the number of ratings a movie needed to be included. For the sushi dataset, the dataset is split into 2 categories. The column labeled ``feat.'' denotes the features fed to the model. Rows marked with llm use the embedding of \texttt{Qwen3-Embedding-0.6B}~\citep{qwen3embedding}.}
\label{tab:res:real}
\end{table}
For real data, we use the data from a sushi preference dataset \citep{kamishima2003nantonac}, the eigen-taste joke dataset \citep{goldberg2001eigentaste}, Netflix prize \citep{netflixprize_data}, and the MovieLens dataset \citep{harper2015movielens}. The sushi dataset is the only ranking dataset. It's A variant is the only dataset where every user rank every alternative. The results are presented in Table~\ref{tab:res:real}. We observe that training with best-of-three observations lead to great improvement over probit models trained with best-of-two observations. The mean effect are strong in these datasets and the improvement over the logit is modest. Table~\ref{tab:nf:cor} lists some movies with strong correlations in the Netflix and MovieLense datasets. In particular we note that we find sequels like Spider-Man (2002) and Spider-Man 2 (2004) or Kill Bill Vol. 1 (2003) and Kill Bill Vol. 2 (2004) to have strong positive correlations while we find a strong negative correlation between more critically acclaimed movies like Memento (2000) and Eternal Sunshine of the Spotless Mind (2004) compared to Hollywood comedy and blockbusters like Perl Harbor (2001) or Cheaper by the Dozen (2003). In Figure~\ref{fig:sushi-probit}, we see that sea urchins are very divisive and that a preference for cucumber sushi negatively correlates with preference for toro (fatty tuna) sushi.
\begin{table}[]
\centering
\tiny
\begin{adjustbox}{width=1.1\textwidth,center=\textwidth}
\begin{tabular}{llrllr}
\toprule
\multicolumn{6}{c}{Netflix} \\\midrule
& & cor. & & & cor.\\
\midrule
Independence Day (1996) & Lost in Translation (2003) & -0.45 & Spider-Man (2002) & Spider-Man 2 (2004) & 0.56 \\
Maid in Manhattan (2002) & The Royal Tenenbaums (2001) & -0.42 & Adaptation (2002) & Lost in Translation (2003) & 0.57 \\
Miss Congeniality (2000) & The Matrix (1999) & -0.41 & Kill Bill: Vol. 1 (2003) & Kill Bill: Vol. 2 (2004) & 0.57 \\
Memento (2000) & Pearl Harbor (2001) & -0.41 & Fight Club (1999) & The Usual Suspects (1995) & 0.59 \\
Double Jeopardy (1999) & Eternal Sunshine of the Spo... & -0.40 & Lord of the Rings: The Retu... & Lord of the Rings: The Two ... & 0.64 \\
Cheaper by the Dozen (2003) & Memento (2000) & -0.40 & Finding Nemo (Widescreen) (... & Shrek (Full-screen) (2001) & 0.65 \\
Independence Day (1996) & The Royal Tenenbaums (2001) & -0.40 & American Beauty (1999) & Being John Malkovich (1999) & 0.66 \\
Anchorman: The Legend of Ro... & Speed (1994) & -0.40 & Lord of the Rings: The Fell... & Lord of the Rings: The Two ... & 0.66 \\
\midrule
\multicolumn{6}{c}{MovieLens}\\
\midrule
Much Ado About Nothing (1993) & Truth About Cats \& Dogs, Th... & -0.46 & Braveheart (1995) & Little Women (1994) & 0.53 \\
Much Ado About Nothing (1993) & What's Eating Gilbert Grape... & -0.42 & Crow, The (1994) & Muriel's Wedding (1994) & 0.53 \\
Dangerous Minds (1995) & Snow White and the Seven Dw... & -0.42 & Clerks (1994) & Father of the Bride Part II... & 0.54 \\
Mrs. Doubtfire (1993) & Nightmare Before Christmas,... & -0.39 & Johnny Mnemonic (1995) & Robin Hood: Men in Tights (... & 0.55 \\
Little Women (1994) & Seven (a.k.a. Se7en) (1995) & -0.39 & Congo (1995) & Speed (1994) & 0.55 \\
Ace Ventura: When Nature Ca... & Little Women (1994) & -0.39 & City Slickers II: The Legen... & Little Women (1994) & 0.59 \\
Congo (1995) & Get Shorty (1995) & -0.38 & Father of the Bride Part II... & GoldenEye (1995) & 0.61 \\
Johnny Mnemonic (1995) & Much Ado About Nothing (1993) & -0.38 & Hudsucker Proxy, The (1994) & True Romance (1993) & 0.61 \\
\bottomrule
\end{tabular}
\end{adjustbox}
\caption{Left to right, movies with the lowest and highest correlations in a probit learned from the Netflix (top) and MovieLens (bottom) datasets. A table with more movie pair is produced in Appendix~\ref{sec:impl}.}
\label{tab:nf:cor}
\end{table}
We finish this section with a welfare maximization experiment. We evaluate the welfare maximizing subset of alternatives given a fixed size, i.e., solve the following equation for some fixed $N$, $\max_{\mathcal{R}\subseteq \mathcal{C}: |\mathcal{R}| = N} \mathbb{E}\left[\max_{i\in \mathcal{R} }X_i\right].$ We use the models from the previous experiments to generate welfare maximizing subsets of size 1 to 3 in the sushi-A dataset. Figure~\ref{fig:optimal_sushi} illustrates what percentage of the test population have their $i$th preferred alternative in the set, e.g., the bar with $x=4$ corresponds to the ratio of people who have at least their third favorite alternative in the set. We acknowledge that this quantity does not directly correlate with welfare as welfare is sensitive to the magnitude of utility change whereas this plot is not. It might not make significant utility difference for someone if their second or third choice are present but it affects this plot. Nonetheless, we see that for subsets of size 2 and 3, more people have their preferred sushi on the menu. The optimal size one menu, for all RUMs, is toro (fatty tuna), the optimal size 2 menu according to the logit is toro (fatty tuna) and maguro (tuna) while our probit suggests uni (sea urchin) and maguro (fatty tuna) instead. Looking at the output of the model in Figure~\ref{fig:sushi-probit} we see that the utility of uni (sea urchin) has high variance and correlates negatively with the utility of toro (fatty tuna) and maguro (tuna). This difference in menu highlights the problem with not modeling correlations properly, a menu of two alternatives that are high utility is not much better than one with only one alternative if they are very correlated. The probit learned from pairwise comparisons instead suggests anago (eel) and toro (fatty tuna) instead.
\begin{figure}
\centering
\vspace{-1em}
\includegraphics[width=\linewidth]{figures/sushi.pdf}
\vspace{-2em}
\caption{Preference of the welfare maximizing choices, left to right for $N=1,2,3$.}
\vspace{-1em}
\label{fig:optimal_sushi}
\end{figure}
\section{Conclusions and Future Directions}
\label{sec:conc}
In this paper, we investigated the methodological shortcomings of learning correlated reward models from simple preference data. We established the statistical deficiency of pairwise comparisons for identifying correlation and showed that best-of-three preferences are provably sufficient. Our analysis culminated in a statistically and computationally efficient estimator for this setting, complete with finite-sample guarantees. Ultimately, our findings show that modeling preference correlations is not only feasible but essential for enabling more advanced applications like in-context learning and the strategic sampling of alternatives.
\section*{Acknowledgments}
CD is supported by a Simons Investigator Award, a Simons Collaboration on Algorithmic Fairness, ONR MURI grant N00014-25-1-2116, ONR grant N00014-25-1-2296. GF are supported by NSF Award CCF-244306, ONR grant N00014-25-1-2296, and an AI2050 Early Career Fellowship. SM is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), 599271-2025.
\bibliographystyle{ACM-Reference-Format}
\bibliography{refs}