EconBase
← Back to paper

Learning Correlated Reward Models: Statistical Barriers and Opportunities

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

46,472 characters · 10 sections · 25 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

Learning Correlated Reward Models: Statistical Barriers and Opportunities

abstractRandom 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 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 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 fundamentally insufficient to learn correlational information, explaining the lack of statistical and computational guarantees in this setting. Next, we demonstrate that 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.

Introduction

Random Utility Models (RUMs) train2009discrete are the leading framework for modelling human preferences. Classical applications dating back to the 1960s include mathematical psychology luce1959individual, transportation science ben1973structure, econometrics mcfadden1980econometric, and marketing rust1993customer. More recently, they are a core component of the Reinforcement Learning from Human Feedback (RLHF) pipeline 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 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 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) What data is needed to learn them? and ii) 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 identifiability results, disregarding any statistical considerations, did not exist. Hence, we establish the first identifiability guarantees and complement them with a near-optimal polynomial-time estimator.

Related work

A wealth of ideas exists for modeling rewards. However, we focus on choice modeling, where subjective preferences between items are expressed. Consequently, we find a treatment of reward models like step-wise reward models havrilla2024glore and process reward models luo2023wizardmath beyond the scope of this work. We are interested in models that can make counterfactual choices from preference data. Outside of machine learning, choice models have been successfully applied to planning problems like public transport scheduling wei2022transit, effect of price markups gallego2014multiproduct, airline scheduling wei2020airline, EV charging station placement lamontagne2023optimising, and toll placement osorio2021efficient.

Random Utility Models (RUMs) are among the most common models of human behavior in mathematical psychology, econometrics, transportation, and marketing mcfadden2001economic. RUMs impose structure on the choice model by assuming that the agents are rational, meaning that when confronted with a finite set of 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

equation*[equation* omitted — 67 chars of source]

Given observations of the form $(\mathcal{R}^t,I_{\mathcal{R}^t}^t)$, $t=1,\ldots,T$, a common challenge is to 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 logit 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 independence of irrelevant alternatives (IIA) 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 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 benson2016relevance, many datasets do not satisfy the IIA assumption. We continue our discussion on choice modeling in Appendix (ref)

Problem Setup, and the Need for Best-Of-Three Observations

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 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 any $t > 0$, induces the same ranking probabilities. Hence, we adopt the following necessary normalization $\mu, \Sigma$.

assumptionFor $X\thicksim\mathcal{N}(\mu,\Sigma)$, we assume, without changing the choice distributions, that \begin{equation*} \inp{\mu}{\Ind}=0, \quad \Sigma\Ind = 0, 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$.

Unfortunately, the classical paradigm of pairwise comparisons ($|\mathcal{R}|=2$) is insufficient for recovering $(\mu, \Sigma)$, even accounting for (ref). Its proof is deferred to (ref).

restatable{theorem}{twonotenough} For any $n \geq 3$ and $\mu, \Sigma$ satisfying (ref), 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*}

(ref) indicates that pairwise comparison data is fundamentally unable to account for correlations in the probit model. While the full proof of (ref) is somewhat involved, the particular setting with $\mu = 0$ is instructive. Here, observe that for any pair of distinct alternatives, $i, j$, the probability that $X_i \geq X_j$ is $1/2$ irrespective of the value of $\Sigma$. Hence, correlational information is fundamentally impossible to learn given only access to pairwise comparisons.

Identifiability

(ref) prompts the natural question: can higher order preference data help? We answer the question in the affirmative and show that best-of-three observations ((ref)) are sufficient and from (ref), necessary to recover $\mu, \Sigma$. Observing that:

equation*[equation* omitted — 154 chars of source]

we may assume access to three-way ranking probabilities.

The Case of Three Alternatives

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.

theorem$(\mu, \Sigma)$ are uniquely identifiable from the three-way observation probabilities.

This result will serve as the basis for the general case in (ref). A probit model satisfying the constraints in (ref) defines a 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:

equation[equation omitted — 570 chars of source]

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 :=

bmatrix[bmatrix omitted — 33 chars of source]

,\qquad c_2 :=

bmatrix[bmatrix omitted — 43 chars of source]

,\qquad c_3 :=

bmatrix[bmatrix omitted — 42 chars of source]

, \] 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 (ref).

figure[figure omitted — 747 chars of source]

We will further transform $V$, rendering the distribution isotropic. Define $\dot{\Sigma}^{-1/2}$ as a solution of

equation*[equation* omitted — 85 chars of source]

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:

equation*[equation* omitted — 119 chars of source]

Setting $x_1 = c_i$ and $x_2 = V$, we now observe:

equation*[equation* omitted — 204 chars of source]

Lastly, note that:

equation*[equation* omitted — 205 chars of source]

Note that $\dot{\Sigma}^{-1/2} V$ is isotropic. Defining,

equation*[equation* omitted — 121 chars of source]

Our first technical result identifies $\alpha_i$ from observational data.

lemmaThe quantities $\alpha_i$ are identifiable from three-way ranking probabilities.
proofNote 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.

\NewDocumentCommand\deins{\alpha_i} \NewDocumentCommand\dzwei{\alpha_j} In the next lemma, we use the values $\alpha_i$ from (ref) to establish a monotonic relationship between $\inp{\wt{c}_i}{\wt{c}_j}$ and the probability of the events in (ref). 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 (ref) 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 (ref).

restatable{lemma}{recangconv} 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} for X \ts \mc{N} (\xi, I). \end{equation*}
proof[Proof of (ref)] 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 (ref), we recover $\alpha_i =\inp{\wt{c}_i}{\wt{\mu}}$ for $i \in [3]$ and from (ref), 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} \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 (ref), we identify $\wt{\mu}$. Noting that $\dot{\Sigma}^{-1/2} \dot{\mu} = \wt{\mu}$, we recover $\dot{\mu}$ and $\mu$ by our previous discussion.

Identifiability: More Than Three Alternatives

We now utilize (ref) to establish identifiability for an arbitrary number of alternatives, $n$. (ref) recovers $\mu, \Sigma$ restricted to tuples of $3$ alternatives up to the symmetries in (ref). 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 unique pair, $\mu, \Sigma$, consistent with the equivalence class of parameters identified by (ref) 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}$.

theorem$\mu, \Sigma$ are uniquely identifiable from the three-way observation probabilities.
proofFirst, note for any distinct indices $i, j, k$, (ref) yields $\wt{\mu}_{ijk}, \wt{\Sigma}_{ijk}$ satisfying: \begin{gather*} t_{ijk} \wt{\mu}_{ijk} = \bar{\mu}_{ijk} 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.

Finite-sample Guarantees: Upper and Lower Bounds

In this section, we extend our identifiability results (ref) to estimation. The key conceptual advancement over (ref) is in the aggregation procedure which combines the standardized estimators of the $3$ item setting ((ref)) into a solution for the $n$ item setting ((ref)). The procedure described in (ref) is wasteful as it requires estimating 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 (ref). We then establish a statistical lower bound demonstrating the near-optimality of our estimator. We start with our estimation guarantees. In addition to (ref), we require the following assumption:

restatable{assumption}{obserabilityestimation}{(Observability)} 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$.

Intuitively, (ref) 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.

restatable{theorem}{estmultitems} Let $(\mu^*, \Sigma^*)$ satisfy (ref) 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 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))$.

Next, we present a lower bound that shows that (ref) 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:

equation*[equation* omitted — 55 chars of source]

As before, we adopt (ref) for normalization and state our main lower bound below.

restatable{theorem}{statlbkl} 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 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 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*}

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 (ref). 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 (ref) in terms of $n, d, \text{ and } \delta$.

figure[figure omitted — 1,669 chars of source]

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 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), 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). 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).

table[table omitted — 4,949 chars of source]

For real data, we use the data from a sushi preference dataset kamishima2003nantonac, the eigen-taste joke dataset goldberg2001eigentaste, Netflix prize netflixprize_data, and the MovieLens dataset 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). 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) 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), we see that sea urchins are very divisive and that a preference for cucumber sushi negatively correlates with preference for toro (fatty tuna) sushi.

table[table omitted — 2,542 chars of source]

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) 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) 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.

figure[figure omitted — 259 chars of source]

Conclusions and Future Directions

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.

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.