Learning Linear Utility Functions From Pairwise Comparison Queries

## Abstract

Abstract We study learnability of linear utility functions from pairwise comparison queries.
In particular, we consider two learning objectives. The first objective is to predict out-of-sample responses to pairwise comparisons, whereas the second is to approximately recover the true parameters of the utility function.
We show that in the passive learning setting, linear utilities are efficiently learnable with respect to the first objective, both when query responses are uncorrupted by noise, and under Tsybakov noise when the distributions are sufficiently “nice”.
In contrast, we show that utility parameters are not learnable for a large set of data distributions without strong modeling assumptions, even when query responses are noise-free.
Next, we proceed to analyze the learning problem in an active learning setting.
In this case, we show that even the second objective is efficiently learnable, and present algorithms for both the noise-free and noisy query response settings.
Our results thus exhibit a qualitative learnability gap between passive and active learning from pairwise preference queries, demonstrating the value of the ability to select pairwise queries for utility learning.

## 1 Introduction

Guiding machines in accordance with human values is a fundamental principle in technology, commonly referred to as “alignment" in the field of Artificial Intelligence (AI).
A common approach for achieving alignment involves learning a utility function (or *reward model*) from a large collection of human responses to *pairwise comparison queries*, that is, queries about their preferences between pairs of options.
A notable example of this is the collection of such data in training large language models (LLMs) to increase helpfulness and reduce harm [, ] as part of a *reinforcement learning from human feedback (RLHF)* framework, in which learned reward models are used as reward functions in a reinforcement learning loop to fine-tune LLMs.
Indeed, utility models learned from pairwise comparison queries have been used in a broad array of domains quite apart from LLMs, such as to train human-aligned controllers [], develop human-aligned kidney exchange algorithms [], and personalize recommendation systems [, ].

Despite the centrality of utility function estimation from pairwise comparison data across a broad array of domains, understanding of what is learnable in this context remains relatively limited, even when utility functions are linear.
Theoretical consideration of this problem has been largely in the context of *random utility model (RUM)* learning based on complete preference information about a fixed set of candidates (outcomes) [, , , ].
Issues such as identifiability [] and social choice properties of learned utility models [, , ] have been extensively studied.
However, few have considered the issue of learning utility models over a vector space of outcomes, where observed preference data constitutes a negligible fraction of possible preference ranking data, and generalization beyond what is observed is key (a notable exception is Zhu et al. [], which we discuss below).
As such settings constitute an important new horizon in social choice as it is integrated into modern AI, a deeper understanding of the issue is needed.

We consider the problem of learning linear utility functions from pairwise comparison data.
Our fundamental question is *under what conditions is sample-efficient learning possible*.
Aside from a recent positive result by [], who showed that parameters of a linear utility function can be efficiently estimated in the covariance norm when data follows the Bradley-Terry (BT) random utility model [], this question remains largely open.
We consider the problem for a general preference noise model of which BT, and many other common RUMs are a special case, with respect to two natural measures of generalization error:
1) accuracy in *predicting* responses to unseen pairwise comparison queries, and
2) efficacy (which we capture as Euclidean distance) in *estimating* parameters of the utility function.

We first investigate the “passive” Probably Approximately Correct (PAC) learning model in which pairs of inputs (outcomes) are generated according to an unknown distribution $\mathcal{P}$, and responses to these comparison queries may be corrupted by noise that comes from a given distribution $\mathcal{Q}$.
We show that when there is no noise in query responses, we can indeed efficiently learn to predict responses to unseen pairwise comparison queries with respect to the true utility function in the PAC sense.
However, the presence of noise *with any c.d.f. continuous at 0 0* leads to an exponential lower bound on sample complexity in this model.
Nevertheless, we show that if the input distribution is well-behaved and the query noise satisfies the Tsybakov noise condition, linear utilities are efficiently learnable in this model.

Turning next to the goal of estimating utility function parameters, we show that it is impossible to do so effectively with polynomial sample complexity *even when there is no query noise*.
This is in contrast to the positive result by [] which implies that we can efficiently learn linear utility functions when the smallest eigenvalue of the covariance matrix of the input distribution is bounded from below, and query responses follow the Bradley-Terry noise model.

While the “passive” setting is conventional in learning theory, the practice of reward model learning, particularly in the context of RLHF, is often to carefully select the outcome pairs for which human preferences are queried.
To study this systematically, we therefore consider an active learning problem whereby we can select arbitrary pairs of inputs to query interactively in order to learn the parameters of a linear utility function.
Our main results are that in the active learning model we can efficiently estimate parameters of the linear utility model, whether or not query responses are corrupted by noise.

## 2 Related Work

Learning Utility Models from Pairwise Comparisons:
The fundamental framework that we build on is random utility model learning, in which utility information is provided indirectly through ranking (e.g., pairwise) comparisons [, , ].
A common approach for learning random utility models from pairwise comparisons is by using maximum likelihood estimation (MLE) [, , ].
Unlike our setting, these typically investigate problems with a finite set of alternatives [, ].
Our focus, in contrast, is to learn a utility function over a continuous vector space.
This problem has been considered by Zhu et al. [], who show that linear utilities can be efficiently learned using maximum likelihood estimators in the Bradley-Terry noise model.

PAC Learning of Halfspaces With Noise:
Common models of noise in random utility models have the property that the closer the pair’s difference is to the halfspace defined by the linear utility function, the higher the chance that this comparison is flipped. This kind of noise has been previously studied as boundary consistent noise in [, , ]. The possibility of an arbitrarily small difference between noise and $\frac{1}{2}$ makes learning very challenging, even for learning halfspaces [].
Consequently, proposals for tractable learning often rely on assumptions regarding distributions of noise.
The spectrum of such noise models starts from the easiest version called random classification noise (RCN) [] – where each label is flipped independently with equal probability exactly $\eta<\frac{1}{2}$ – where efficient algorithms exist [].
At the other end are malicious noise [] and agnostic learning [, , , ], where an adversarial oracle can flip any small constant fraction of the labels, typically making these models less tractable. Additionally, active learning has been proposed as a solution to reduce the number of samples the learner needs to query before approximately learning the concept class with high probability. While active learning requires exponentially fewer labeled samples than PAC-learning for simple classes such as thresholds in one dimension, it fails in general to provide asymptotic improvement for broad classes such as halfspaces [].

Robust Parameter Estimation: Learning a linear classifier has also been a classical problem beyond learning theory, with *empirical risk minimisation* the most popular paradigm, with a range of tools including Bayes classifiers, perceptron learning, and support vector machines (SVM).
Most directly related is the connection between robustness (to input noise) and regularization in SVM [].
However, this robustness is with respect to *input* noise, whereas our consideration is noise in pairwise comparison responses (outputs).

## 3 Preliminaries

Our goal is to learn utility functions from pairwise comparison queries.
To this end, we consider the hypothesis class $\mathcal{U}$ of weight-normalized monotone linear utility functions $u(x)=w^{T}\phi(x)$ with respect to a known continuous embedding of candidate profiles $\phi(x):\mathbb{R}^{d}\xrightarrow{}\mathcal{X}\equiv[0,1]^{m}$, where $\mathbb{R}^{d}$ is the original space the candidates lie in, and $w\geq 0$ and $\|w\|_{1}=1$.

In the passive learning setting, we assume that we obtain a dataset $\mathcal{D}=\{(x_{i},x_{i}^{\prime},y_{i})\}_{i=1}^{n}$ which contains labels $y_{i}\in\{0,1\}$ associated with responses to pairwise comparison queries $(x_{i},x_{i}^{\prime})$ that are interpreted as preferences.
In particular, $y_{i}=1$ if $x_{i}^{\prime}$ is preferred to $x_{i}$ (which we denote by $x_{i}^{\prime}\succ x_{i}$, and $y_{i}=0$ otherwise.
We assume that input pairs $(x,x^{\prime})\in\mathcal{D}$ are generated i.i.d. according to an unknown distribution $\mathcal{P}$ over $\mathbb{R}^{d}$.
This, in turn, induces a distribution $\mathcal{P}_{\phi}$ over embedded pairs $(\phi(x),\phi(x^{\prime}))$.

We assume that the label $y$ is generated according to the commonly used *random utility model (RUM)* [].
Specifically,
if $u(x)$ is the true utility function, query responses follow a random utility model $\tilde{u}(x)=u(x)+\tilde{\zeta}$, where $\tilde{\zeta}$ is an independent random variable distributed according to a fixed probability distribution $\tilde{\mathcal{Q}}$.
Define $Z_{\tilde{u}}(x,x^{\prime})\equiv\mathrm{sign}(\tilde{u}(x^{\prime})-\tilde{u}
(x))$, where we define $\mathrm{sign}(z)=1$ if $z>0$, 0 0 if $z<0$, and a random variable being 0 0 or $1$ with equal probability $0.5$ if $z=0$.
Then $y=Z_{\tilde{u}}(x,x^{\prime})\in\{0,1\}$.

We further define the difference between a pair $(\phi(x),\phi(x^{\prime}))$ as $\Delta_{\phi}(x)\equiv(\phi(x^{\prime})-\phi(x))\in[-1,1]^{m}$. Since $\tilde{u}(x^{\prime})-\tilde{u}(x)=w^{T}\Delta_{\phi}(x)+\tilde{\zeta}(\phi(x^
{\prime}))-\tilde{\zeta}(\phi(x))$,
it will be most useful to consider $\zeta\equiv\tilde{\zeta}(\phi(x^{\prime}))-\tilde{\zeta}(\phi(x))$ for a pair of feature vectors $(\phi(x),\phi(x^{\prime}))$, so that $Z_{\tilde{u}}(x,x^{\prime})=\mathrm{sign}(w^{T}\Delta_{\phi}(x)+\zeta)$.
Let $\mathcal{Q}$ be the distribution over $\zeta$ induced by $\tilde{\mathcal{Q}}$, and let $F(\zeta)$ be its c.d.f., which we assume is continuous on $\mathbb{R}$ except in the noise-free special case.
Then the probability that $y=1$ for a pair $(\phi(x),\phi(x^{\prime}))$, that is, the probability that $x^{\prime}\succ x$, is $\Pr(x^{\prime}\succ x)=\Pr(\zeta\leq w^{T}\Delta_{\phi}(x))=F(w^{T}\Delta_{
\phi}(x))$.
As we assume $\Pr(x^{\prime}\succ x)+\Pr(x\succ x^{\prime})=1$,
$F(w^{T}\Delta_{\phi}(x))+F(-w^{T}\Delta_{\phi}(x))=1$ leading to $F(x)+F(-x)=1$ and $F(0)=1/2$.

Note that our random utility model is quite general.
For example,
the two most widely-used models are both its special cases: the Bradley-Terry (BT) model [], in which $F$ is the logistic distribution, and the Thurstone-Mosteller (TM) model [], in which $F$ is a Gaussian distribution.
Additionally, we consider an important special case in which there is no noise, i.e., $\zeta=0$.
In this case, $\Pr(x^{\prime}\succ x)\in\{0,0.5,1\}$ depending on whether $w^{T}\Delta_{\phi}(x)$ is negative, zero, or positive.

Broadly speaking, the goal of learning utility functions from $\mathcal{D}$ is to effectively capture the true utility $u(x)$.
In the setting where data provides only information about pairwise preferences, there are a number of reasonable learnability goals.
Here, we consider two.

Our first goal is motivated by a general consideration that a common role of a utility function is to induce a ranking over alternatives, used in downstream tasks, such as reinforcement learning, recommendations, and so on.
Thus, a corresponding aim of learning a utility function is to approximate its ranking over a finite subset of alternatives, so that the learned function is a useful proxy in downstream tasks.
Here, we consider the simplest variant of this, which is to learn a linear function $\hat{u}:\mathcal{X}\xrightarrow{}[0,1]$ from $\mathcal{D}$ with the property that it yields the same outcomes from pairwise comparisons as $u(x)$.
Formally, we capture this using the following error function:

$$ $e_{1}(\hat{u},u)=\Pr_{(x,x^{\prime})\sim\mathcal{P}}\left(Z_{\hat{u}}(x,x^{ \prime})\neq Z_{u}(x,x^{\prime})\right).$ (1) $$

We refer to this goal as minimizing the *error of predicted pairwise preferences*.
Note that this error function has an important difference from conventional learning goals in similar settings: we wish to predict pairwise comparisons with respect to the true utility $u$, rather than the noise-perturbed utility $\tilde{u}$.
This is a consequential difference, as it effectively constitutes a distributional shift when pairwise preference responses are noisy.

Our second goal is to accurately capture the weights of $u$.
Formally, we define it as

$$ $e_{2}(\hat{u},u)=\|\hat{w}-w^{*}\|_{p}^{p}$ (2) $$

where $p\geq 1$ and $w^{*}$ is the true weight.
Henceforth, we focus on Euclidean norm $\ell_{2}$.
Our results generalize to any $p\geq 1$: counterexamples in the impossibility results still work, and the positive results hold by norm equivalence in $\mathbb{R}^{m}$.
Moreover, focusing on $\ell_{2}$ norm facilitates a direct comparison to [], who use a seminorm $\|x\|_{\Sigma}$ where $\Sigma$ is the data covariance matrix that is most comparable with respected to the $\ell_{2}$.
We refer to this model as the *utility estimation error*.

Our learnability discussion will be based on an adaptation of the Probably Approximately Correct (PAC) Learning framework [], with the goal of identifying a utility model $\hat{u}$ that has error at most $\varepsilon$ with probability at least $1-\delta$ for $\varepsilon>0$ and $\delta>0$.
We now formalize this as PAC learnability from pairwise comparisons (PAC-PC).
Let $\mathbb{N}$ be the space of natural numbers.

###### Definition 1 (PAC-PC learnability) .

Given a noise distribution $\mathcal{Q}$, a utility class $\mathcal{U}$ is PAC learnable from pairwise comparisons (PAC-PC learnable) for error function $e(\hat{u},u)$ if there is a learning algorithm $\mathcal{A}$ and a function $n_{A}:(0,1)^{2}\rightarrow\mathbb{N}$ such that for any input distribution $\mathcal{P}$, and $\forall\varepsilon,\delta\in(0,1)$, whenever $n\geq n_{A}(\varepsilon,\delta)$, $\mathcal{A}(\{(x_{i},x_{i}^{\prime},y_{i})\}_{i=1}^{n})$ with $(x_{i},x_{i}^{\prime})\sim\mathcal{P}$ i.i.d. and $y_{i}=\mathrm{sign}(u(x_{i}^{\prime})-u(x_{i})+\zeta_{i})$ for $\zeta_{i}\sim\mathcal{Q}$ i.i.d. returns $\hat{u}$ with probability at least $1-\delta$ such that $e(\hat{u},u)\leq\varepsilon$.
Moreover, if $n_{A}$ is polynomial in $1/\varepsilon,1/\delta,\mathrm{Dim}(\mathcal{U})$, where $\mathrm{Dim}(\mathcal{U})$ is the dimension of $\mathcal{U}$, then we say $\mathcal{U}$ is efficiently PAC-PC learnable.

We stated this definition quite generally, but our focus here is on the class $\mathcal{U}$ of linear functions, in which case Dim($\mathcal{U}$) = $m$.

###### Definition 1 (PAC-PC learnability) .

## 4 Passive Learning

We begin with the conventional learning setting, in which input pairs $(x,x^{\prime})$ in the training data are generated i.i.d. from $\mathcal{P}$, inducing a distribution $\mathcal{P}_{\phi}$ over $(\phi(x),\phi(x^{\prime}))$.
We refer to this as the *passive learning* setting to distinguish it from *active learning* that we consider below.
For convenience, we also define the distribution of $\Delta_{\phi}(x)\sim\mathcal{P}_{\phi}^{\prime}$.
First, we consider the goal of learning to predict results of pairwise comparisons.
Subsequently, we investigate the goal of learning to estimate parameters $w$ of the true utility function $u(x)=w^{*^{T}}\phi(x)$.

### 4.1 Predicting Pairwise Preferences

We begin by considering the error function $e_{1}$, that is, where the goal is to predict outcomes of pairwise comparisons.
In the noise-free setting, we can immediately obtain the following result as a direct corollary of learnability of halfspaces.

###### Theorem 1 .

Suppose $\zeta=0$. Then linear utility functions are efficiently PAC-PC learnable under the error function $e_{1}$.

###### Proof.

Let $y=g(\Delta_{\phi}(x))=\mathrm{sign}(w^{*^{T}}\Delta_{\phi}(x))$.
Then PAC-PC learning under $e_{1}$ and $\mathcal{P}$ is equivalent to PAC learnability of halfspaces $g(\Delta_{\phi}(x))$ under $\mathcal{P}^{\prime}_{\phi}$.
As shown by  [], halfspaces are learnable with sample complexity $\mathcal{O}(\frac{1}{\varepsilon}(m+\log(\frac{1}{\delta})))$.
∎

With this connection between learnability in the sense of $e_{1}$ and learning of halfspaces in mind, we now consider the case in which pairwise preference responses are corrupted by noise.
Surprisingly, adding noise to pairwise preferences makes learning impossible for a natural broad class of distributions.
For the next impossibility result, as well as the discussion that follows, it will be useful to define $\eta(\Delta_{\phi}(x))\equiv F(-|w^{*^{T}}\Delta_{\phi}(x)|)$, the chance of getting a misreported comparison label for $\Delta_{\phi}(x)$.

###### Theorem 2 .

$\mathcal{U}$ is not efficiently PAC-PC learnable under error function $e_{1}$ if the preference noise distribution has a c.d.f. $F$ continuous at zero.

###### Proof.

Following the discussion in Section 3, we know that $\Pr(y=1)=F(w^{*^{T}}\Delta_{\phi}(x)),\Pr(y=0)=F(-w^{*^{T}}\Delta_{\phi}(x))=1
-F(w^{*^{T}}\Delta_{\phi}(x))$ whereas the true label is $\mathrm{sign}(w^{*^{T}}\Delta_{\phi}(x))$. Hence $\eta(\Delta_{\phi}(x))\equiv F(-|w^{*^{T}}\Delta_{\phi}(x)|)$ is indeed the chance of getting a misreported label for $\Delta_{\phi}(x)$.

Due to the continuity of $F$ at 0 0, for any $t>0$, there exists $s>0$ such that for all $|v-0|\leq s$, $|F(v)-F(0)|\leq t$. As $F$ is monotonically increasing, and $-|w^{*^{T}}\Delta_{\phi}(x)|<0$, $\eta(\Delta_{\phi}(x))<F(0)=\frac{1}{2}$. Hence for a fixed $\varepsilon<1$, we can pick $t_{0}=1/\exp(1/\varepsilon)$. Then there exists a corresponding $s_{0}$ such that for a $(\phi(x),\phi(x^{\prime}))$ with $\Delta_{\phi}x$ of norm at most $s_{0}$, for all $w$, $|w^{T}\Delta_{\phi}(x)-0|\leq s_{0}$, $|\eta(\Delta_{\phi}(x))-\frac{1}{2}|\leq t_{0}.$
Now consider the oracle who always chooses one such pair $(\phi(x),\phi(x^{\prime}))$.
With fixed probability at most $\frac{1}{2}+t_{0}$ it outputs the true label and with probability $\frac{1}{2}-t_{0}$ it outputs the false label.
In order to establish the Binomial distribution’s confidence over $1-\delta$, we need sample complexity $\tilde{\Omega}(\frac{1}{t_{0}})=\tilde{\Omega}(\exp(\frac{1}{\varepsilon}))$, which is exponential in $\frac{1}{\varepsilon}$.∎

Notably, all common models of noisy preference responses, such as Bradely-Terry and Thurstone-Mosteller, entail continuity of $F$ at 0 0, so this result yields impossibility of learning linear utilities for these standard RUM settings.

The consequence of Theorem 2 is that to achieve any general positive results we must constrain the distribution over inputs and resulting embeddings.
We now show that we can leverage Tsybakov noise and a condition that the distribution over embeddings is well-behaved to attain sufficient conditions for efficient learnability.

###### Definition 2 (Tsybakov Noise Condition) .

[]
Let $C$ be a concept class of Boolean-valued functions over $X=\mathbb{R}^{d}$, $F$ be a family of distributions on $X$, $0<\varepsilon<1$ be the error parameter, and $0\leq\alpha<1$, $A>0$ be parameters of the noise model.
Let $f$ be an unknown target function in $C$. A Tsybakov example oracle, $EX^{Tsyb}(f,F)$, works
as follows: Each time $EX^{Tsyb}(f,F)$ is invoked, it returns a labeled example $(x,y)$, such that: (a) $x\sim\mathcal{D}_{x}$, where $\mathcal{D}_{x}$ is a fixed distribution in $F$, and (b) $y=f(x)$ with probability $1-\eta(x)$ and $y=1-f(x)$ with probability $\eta(x)$. Here $\eta(x)$ is an unknown function that satisfies the Tsybakov noise condition with parameters $(\alpha,A)$. That is, for any $0<t\leq\frac{1}{2}$, $\eta(x)$ satisfies the condition $\Pr_{x\sim\mathcal{D}_{x}}[\eta(x)\geq\frac{1}{2}-t]\leq At^{\frac{\alpha}{1-
\alpha}}$.

###### Definition 3 (Well-Behaved Distributions) .

[]
For $L,R,U>0$ and $k\in\mathbb{Z}_{+}$, a distribution $\mathcal{D}_{x}$ on $\mathbb{R}^{d}$ is called $(k,L,R,U)$-well-behaved if for any projection ${(\mathcal{D}_{x})}_{V}$ of $\mathcal{D}_{x}$ on a $k$-dimensional subspace $V$ of $\mathbb{R}^{d}$, the corresponding p.d.f. $\gamma_{V}$ on $V$ satisfies the following properties: (i) $\gamma_{V}(x)\geq L$, for all $x\in V$ with $||x||_{2}\leq R$ (anti-anti-concentration), and (ii) $\gamma_{V}(x)\leq U$ for all $x\in V$ (anti-concentration). If, additionally, there exists $\beta\geq 1$ such that, for any $t>0$ and unit vector $w\in\mathbb{R}^{d}$ , we have that $\Pr_{x\sim\mathcal{D}_{x}}[|\langle w,x\rangle|\geq t]\leq exp(1-t/\beta)$ (subexponential concentration), we call $\mathcal{D}_{x}(k,L,R,U,\beta)$ well-behaved.

###### Theorem 3 (Learning Tsybakov Halfspaces under Well-Behaved Distributions) .

[, Theorem 5.1]
Let $\mathcal{D}_{x}$ be a $(3,L,R,U,\beta)$-well-behaved isotropic distribution on $\mathbb{R}^{d}\times\{\pm 1\}$ that satisfies the $(\alpha,A)$-Tsybakov noise condition with respect to an unknown halfspace $f(x)=sign(\langle w,x\rangle)$. There exists an algorithm that draws $N=\beta^{4}(\frac{dUA}{RL\varepsilon})^{O(1/\alpha)}log(1/\delta)$ samples from $\mathcal{D}_{x}$, runs in $poly(N,d)$ time, and computes a vector $\hat{w}$ such that, with probability $1-\delta$, we have $\Pr_{x\sim\mathcal{D}_{x}}[h(x)\neq f(x)]\leq\varepsilon$.

We can leverage this result to obtain an efficient learning algorithm to predict pairwise comparisons for a broad range of distributions.

###### Theorem 4 .

Suppose that $\mathcal{P}_{\phi}$ is a $(3,L,R,U,\beta)$-well-behaved isotropic distribution, and the noise c.d.f. $F^{-1}(\zeta)\leq\mathrm{poly}(\zeta)$ on $(0,\frac{1}{2}]$. Then the linear utility class $\mathcal{U}$ is efficiently PAC-PC learnable.

###### Proof.

Since $\mathcal{P}_{\phi}$ is $(3,L,R,U,\beta)$-well-behaved over $(\phi(x),\phi(x^{\prime}))$, we consider a special 3-dimensional subspace $V$ with its basis being $u_{1}=(w^{*},w^{*}),u_{2}=(v_{2},v_{2}),u_{3}=(v_{3},v_{3})$, where $v_{2}$,$v_{3}$ are two orthonormal vectors lying on the hyperplane defined by our utility parameter $w^{*}$. Since $w^{*^{T}}v_{2}=w^{*^{T}}v_{3}=v_{2}^{T}v_{3}=0$, these three vectors are linearly independent and form a basis.

Recall that for any point $\pi(x)=(\phi(x),\phi(x^{\prime}))$ viewed as in the product space $\mathcal{X}^{2}$, its projected coordinates in $V$ is calculated as
$\pi(x)_{V}=(u_{1}^{T}\pi(x))\frac{u_{1}}{||u_{1}||}+(u_{2}^{T}\pi(x))\frac{u_{
2}}{||u_{2}||}+(u_{3}^{T}\pi(x))\frac{u_{3}}{||u_{3}||}=(u_{1}^{T}\pi(x),u_{2}
^{T}\pi(x),u_{3}^{T}\pi(x)).$

First, by the subexponential concentration property, for any fixed $h>0$, $\Pr_{\pi(x)\sim\mathcal{P}_{\phi}}\left(|u_{2}^{T}\pi(x)|\geq h\right)<\exp(1-
h/\beta)$, and $\Pr_{\pi(x)\sim\mathcal{P}_{\phi}}\left(|u_{3}^{T}\pi(x)|\geq h\right)<\exp(1-
h/\beta)$. So with probability at most $2\exp(1-h/\beta)$, the second or the third coordinate of the projection is not within $[-h,h].$

Next, by the anti-concentration property, the p.d.f. of the projection $\pi(x)_{V}$ is bounded by a constant $\gamma_{V}(\pi(x))\leq U$. Hence the total probability of the projection $\pi(x)_{V}$’s first coordinate between $[-h,h]$ is
$Pr_{\pi(x)\sim\mathcal{P}_{\phi}}\left(|u_{1}^{T}\Delta_{\phi}(x)|\leq h\right
)\leq\int_{-h}^{h}\int_{-h}^{h}\int_{-h}^{h}Udt_{1}dt_{2}dt_{3}+2\exp(1-h/
\beta)=8Uh^{3}+\exp(1-h/\beta)$. Since for any $\phi(x)<1$, $\exp(\phi(x))<1+\phi(x)+\phi(x)^{2}$, and $1-h/\beta<1$, $\exp(1-h/\beta)<1+((1-h/\beta)+(1-h/\beta)^{2}$. So
$Pr_{\pi(x)\sim\mathcal{P}_{\phi}}\left(|u_{1}^{T}\Delta_{\phi}(x)|\leq h\right
)\leq p_{1}(h)$ has a degree-$3$ polynomial upper bound.

Now, consider a $1-D$ projection of this subspace through $\text{Proj}(\phi(x),\phi(x^{\prime}))=\phi(x^{\prime})-\phi(x)$. We get $\text{Proj}(V)=\{(w^{*^{T}}\Delta_{\phi}(x),v_{2}^{T}\Delta_{\phi}(x),v_{3}^{T
}\Delta_{\phi}(x))\}$.
Due to the triangle and Cauchy-Schwartz inequality,
$|w^{*^{T}}\Delta_{\phi}(x)|=|w^{*^{T}}\phi(x^{\prime})-w^{*^{T}}\phi(x)|\leq|w
^{*^{T}}\phi(x^{\prime})|+|w^{*^{T}}\phi(x)|\leq\sqrt{2}|u_{1}^{T}\pi(x)|$. Hence, the probability of the first coordinate of $P(V)$, i.e. the margin $w^{*^{T}}\Delta_{\phi}(x)$ being between $[-\sqrt{2}h,\sqrt{2}h]$ has a polynomial upper bound:
$\Pr_{\Delta_{\phi}(x)\sim\mathcal{P}^{\prime}_{\phi}}\left(|w^{*^{T}}\Delta_{
\phi}(x)|\leq\sqrt{2}h\right)\leq\Pr_{\pi(x)\sim\mathcal{P}_{\phi}}\left(|u_{2
}^{T}\pi(x)|\geq h\right)<p_{1}(h).$

Because $\Pr_{\Delta_{\phi}(x)\sim\mathcal{P}^{\prime}_{\phi}}\left(\eta(\Delta_{\phi}(
x))\geq\frac{1}{2}-t\right)=\Pr_{\Delta_{\phi}(x)\sim\mathcal{P}^{\prime}_{
\phi}}\left(|w^{*^{T}}\Delta_{\phi}(x)|\leq F^{-1}(\frac{1}{2}-t)\right)$,
as long as $F^{-1}(\frac{1}{2}-t)$ has a polynomial upper bound $p_{2}(t)$, we could establish another polynomial upper bound
$\Pr_{\Delta_{\phi}(x)\sim\mathcal{P}^{\prime}_{\phi}}\left(|w^{*^{T}}\Delta_{
\phi}(x)|\leq F^{-1}(\frac{1}{2}-t)\right)<p_{1}(\frac{F^{-1}(\frac{1}{2}-t)}{
\sqrt{2}})\leq p_{1}(\frac{p_{2}(t)}{\sqrt{2}})\in poly(t).$

In other words, we could bound $\Pr_{\Delta_{\phi}(x)\sim\mathcal{P}^{\prime}_{\phi}}\left(|w^{*^{T}}\Delta_{
\phi}(x)|\leq F^{-1}(\frac{1}{2}-t)\right)\leq At^{\frac{\alpha}{1-\alpha}}$ by taking the leading coefficient of $p_{1}(\frac{p_{2}(t)}{\sqrt{2}})$ being $A$, and $\frac{\alpha}{1-\alpha}$ being the degree of $p_{1}(p_{2}(t))+1$.
Our noise model satisfies the $(\alpha,A)-$Tsybakov noise condition, and the algorithm in [] applies.
∎

Next we show that the standard models of noise in RUM settings—Bradley-Terry [] and Thurstone-Mosteller []—both satisfy the condition on the noise c.d.f. in Theorem 4.

###### Proposition 5 .

The inverse of the c.d.f. for the Bradley-Terry model satisfies $F^{-1}(x)\leq\mathrm{poly}(x)$ on $(0,\frac{1}{2}]$.

###### Proof.

The inverse of the standard logistic function $F(x)=\frac{1}{1+\exp(-x)}$ is the logit function
$F^{-1}(x)=logit(x)=\ln(\frac{x}{1-x})$.
Because the derivative of the logit function $\frac{1}{x-x^{2}}$ is monotonically decreasing from $\infty$ to $4$ on $(0,\frac{1}{2}]$, the logit function is concave. Hence, it is bounded above by its gradient at $x=\frac{1}{2}$, which is $4x-2$. We have found a polynomial upper bound for $F^{-1}(x)\leq 4x-2$ for $x\in(0,\frac{1}{2}]$.
∎

###### Proposition 6 .

The inverse of the c.d.f. for the Thurstone-Mosteller model satisfies $F^{-1}(x)\leq\mathrm{poly}(x)$ on $(0,\frac{1}{2}]$.

###### Proof.

The inverse of the standard Gaussian c.d.f function $F(x)=\frac{1}{2}(1+\text{erf}(\frac{x}{\sqrt{2}}))$ is
$F^{-1}(x)=\sqrt{2}\text{erf}^{-1}(2x-1)$, where erf
is the error function.
Again, as the derivative of the inverse error function is
$\frac{\sqrt{\pi}}{2}\exp([\text{erf}^{-1}(x)]^{2})$ , which is
monotonically decreasing on $(-1,0]$, the inverse error function is concave and bounded above the gradient at $x=0$, which is $\frac{\sqrt{\pi}}{2}x$. Hence
$F^{-1}(x)=\sqrt{2}\text{erf}^{-1}(2x-1)\leq\frac{\sqrt{2\pi}}{2}(2x-1)=\sqrt{2
\pi}x-\frac{\sqrt{2\pi}}{2}$ for $x\in(0,\frac{1}{2}]$.
∎

###### Theorem 1 .

###### Proof.

###### Theorem 2 .

###### Proof.

###### Definition 2 (Tsybakov Noise Condition) .

###### Definition 3 (Well-Behaved Distributions) .

###### Theorem 3 (Learning Tsybakov Halfspaces under Well-Behaved Distributions) .

###### Theorem 4 .

###### Proof.

###### Proposition 5 .

###### Proof.

###### Proposition 6 .

###### Proof.

### 4.2 Estimating Utility Parameters

Next, we tackle the more challenging learning goal represented by the error function $e_{2}$, that is, where our goal is to learn to effectively estimate the parameters $w$ of the true linear utility model in the $\ell_{p}$ sense (focusing on $\ell_{2}$ here for clarity of exposition).

We begin with the known positive result.
Specifically,  [] showed that maximum likelihood estimation (MLE) with the common BT noise model achieves efficient utility estimation in the following sense.
With probability at least $1-\delta$, the MLE parameter estimate $\hat{w}$ from $n$ samples can achieve a bounded error measured in a seminorm with respect to $\Sigma=\frac{1}{n}\sum_{i=1}^{n}(\phi(x_{i})-\phi(x^{\prime}_{i})_{i})(\phi(x_
{i})-\phi(x^{\prime}_{i}))^{T}$. With $C$ being constant,

$$ $||\hat{w}-w^{*}||_{\Sigma}=\sqrt{(\hat{w}-w^{*})^{T}\Sigma(\hat{w}-w^{*})}\leq C \cdot\sqrt{\frac{m+\log(1/\delta)}{n}}.$ (3) $$

We are able to extend their positive result to an even bigger class of RUMs. The proof is deferred to the appendix.

###### Theorem 7 .

Consider the loss function, $\ell_{\mathcal{D}}(w)=-\frac{1}{n}\sum_{i=1}^{n}\log\left(1(y^{i}=1)\cdot\Pr(x
^{\prime}\succ x)+1(y^{i}=0)\cdot\Pr(x\succ x^{\prime})\right).$
If there exists $\gamma>0$ such that the noise c.d.f. $F(z)$ satisfies $F^{\prime}(z)^{2}-F^{\prime\prime}(z)\cdot F(z)\geq\gamma$ for all $z$, then with probability $1-\delta$, the MLE estimator $\hat{w}$ for $\ell_{\mathcal{D}}(w)$ can achieve inequality (3).

Consequently, as long as $\Sigma$’s smallest eigenvalue is bounded from below (which excludes the case where $\phi(x),\phi(x^{\prime})$ are consistently close, as $\Sigma$ tends to 0 the bound becomes vacuous),
sample complexity with respect to $e_{2}$ will also be quadratic.
Formally, suppose that the smallest eigenvalue $\lambda_{min}\geq C_{2}>0$.
Then,

$$ $\displaystyle||\hat{w}-w^{*}||_{2}$ $\displaystyle=\sqrt{\frac{C_{2}}{C_{2}}(\hat{w}-w^{*})^{T}(\hat{w}-w^{*})}$ $\displaystyle\leq\sqrt{\frac{1}{C_{2}}(\hat{w}-w^{*})^{T}\Sigma(\hat{w}-w^{*})}$ $\displaystyle\leq\overline{C}\cdot\sqrt{\frac{m+\log(1/\delta)}{n}}$ $$

for a constant $\overline{C}$.

Now we show that *without any structural noise assumption,* learning to estimate linear utility parameters in the $\ell_{2}$ norm is impossible.

###### Theorem 8 .

If there is no noise, the class of linear utility functions $\mathcal{U}$ is not always passively learnable, i.e.
there is a probability distribution $\mathcal{P}$ over $(x,x^{\prime})$, that
no learning algorithm can achieve
$e_{2}\leq\varepsilon$ with probability at least $1-\delta$, for any
$0<\varepsilon,\delta<1$ under a finite set of samples.

###### Proof.

Let $\phi(x)=x$, and
consider an oracle that only provides pairs $(x,x^{\prime})$ with all coordinates satisfying $x^{\prime i}>x^{i}$ on each dimension $i$ .
Then since $w\geq 0$, $w^{T}(x^{\prime}-x)\geq 0$ for every $(x,x^{\prime})$; in other words, the labels are uninformative and any algorithm produces the same distribution on guesses $\hat{w}$ for all $w$.
For $\delta<\frac{1}{2}$, we can consider $w,w^{\prime}\in\mathcal{U}$ with distance equal to $\sqrt{2}$. This is achievable because $\mathcal{U}$ contains segments of length $\sqrt{2}$ defined by $\{w^{i}+w^{j}=1,0\leq w^{i},w^{j}\leq 1\}$ for any distinct pair of $i,j\in\{1,\dots,m\}$ and we know $m\geq 2$ for otherwise there is no need to learn. But the algorithm cannot output $\hat{w}$ with $e_{2}<(\frac{\sqrt{2}}{2})^{2}=\frac{1}{2}$ for both $w$ and $w^{\prime}$ simultaneously, and hence its output must obtain $e_{2}\geq\frac{1}{2}$ with probability $\geq\frac{1}{2}$ for one of these.∎

The reason behind this contrast between the positive and negative results lies precisely in the assumption of the noise model.
Unlike a common intuition that noise makes learning more challenging, a highly structured model assumption like BT actually provides more information to each query.
From a pair where $\Delta_{\phi}(x)>0$, if we can estimate $\Pr(x^{\prime}\succ x)$, since $\Pr(x^{\prime}\succ x)=F(w^{*T}\Delta_{\phi}(x)),$ we obtain information about $w^{*}$ immediately.

Figure: Figure 1: From the label we know $w^{*}$ is below the hyperplane of $\Delta_{\phi}(x)$.
Refer to caption: extracted/5679113/estimating_a.png

To illustrate a necessary and sufficient results for passive learning in the noise-free or noise-agnostic setting, we consider the problem from a geometric perspective.
It is helpful to recall a learning theory concept named *version space*. A version space consists of all “surviving” hypotheses that are consistent with the conclusions we can draw from all labels observed so far.
In our case, our version space denoted as $\mathcal{W}$ will be initialised the same as $\mathcal{U}$.
Now as each datapoint comes along, the label $y$ gives us an (inaccurate) sign of
$w^{*T}\Delta_{\phi}(x)$, indicating whether the vector $w^{*}$ that we are searching for is above, on, or below the hyperplane defined by its normal vector $\Delta_{\phi}({x)}$. The version space will update accordingly.
For example, when $m=3$, the initial version space (hypothesis class) is depicted as the triangle $\{w^{1}+w^{2}+w^{3}-1=0\ |\ 0\leq w^{1},w^{2},w^{3}\leq 1\}$ in Figure 1, with the true parameter labeled as $w^{*}$. Then suppose we receive a noiseless datapoint labeled with $y<0$, we can infer $w^{*}$ is below the segment $AB$ drawn as in Figure 1 since that is the space $\Delta_{\phi}(x)$ is normal to.

Thus, in order to achieve the second learning goal without a model assumption, we have to wish for that the incoming datapoints can help shrink the version space into
a $\varepsilon$-radius ball centred at $w^{*}$. The difficulty with respect to $e_{2}$ is exactly that we don’t have any control over the incoming information. Hence we will see from the following section that active learning is much more advantageous.

###### Theorem 7 .

###### Theorem 8 .

###### Proof.

## 5 Active Learning

Thus far, we noted that passive learning is generally quite challenging, particularly when responses to pairwise comparison queries are noisy.
However, in many practical settings, most notably, RLHF, utility (reward) models are *not* learned passively.
Rather, one first carefully constructs and curates a dataset of input pairs, and only then obtains preference data for these [, ].
This is far more like an *active learning* approach to the problem, for which there has been, to our knowledge, no prior work on learnability in the pairwise comparison model we consider here.
In this section, we demonstrate that the active learning model in this setting is qualitatively different from passive in that we now obtain strong efficient learnability results.

Our investigation falls under the umbrella of an interactive approach, which is considered a more efficient framework than pool and stream-based sampling techniques [, , , ].
A common argument against query synthesis methods is that the artificial queries we thereby generate are uninterpretable.
However, there is evidence that generating highly informative artificial training instances for tasks like text classification is feasible [, ].
Although practical tricks may need to be developed to apply active learning approaches in a practical setting, these can in general save considerable annotation labor.
The second criticism is that if we do not have a distribution in mind, our learning may have limited value in terms of generalization.
In any case, our study of active learning from a theoretical perspective also lends intuition as to why in practice there is considerable effort devoted to generating query inputs for learning utility models.

We structure our investigation in the same way as the passive learning case, considering first the problem of learning to predict responses to pairwise preference queries (the $e_{1}$ error model), and subsequently dealing with the more challenging problem of estimating utility parameters.

### 5.1 Predicting Pairwise Preferences

Just as in the passing learning setting, the positive results for active learning of linear utilities from pairwise comparisons in the $e_{1}$ sense
follow directly from known results for learning halfspaces.
In the noise-free case,
[] and [] provide efficient learning algorithms through query synthesis.
[], in turn, address the setting with Tsybakov noise.
Consequently, we focus on the more challenging problem of estimating utility parameters in the active learning setting.
We tackle this problem next.

### 5.2 Estimating Utility Parameters

Continuing from our discussion in Section 4.2,
the goal in active learning is to ensure that in each step we query the most informative comparison pair inside the current version space in order to reduce the size of the version space as fast as possible.
We first provide an efficient algorithm for this in the noise-free setting, and subsequently in the case with query noise.
Here, a key challenge is an ability to invert the embedding $\phi(x)$.
Since our focus is on *query* or *sample* complexity, our results hold whether or not computing an inverse of $\phi$ (or, equivalently, a zero of $\phi(x)-v$ for a given $v$) is efficient (note that we do not need uniqueness); however, this does, of course, impact *computational* complexity of the algorithms.
In special cases, such as if $\phi(x)=x$, or if $\phi(x)$ is affine (where an inverse can be computed using linear programming), computational complexity is polynomial as well, and more generally, we can in practice use gradient-based methods (such as Newton’s method) to approximately find a zero of $\phi(x)-v$.

Figure: Algorithm 1 Noise-Free Active Learning

The concrete active learning approach for noise-free learning of utility function parameters from pairwise queries is provided as Algorithm 1.
Next, we prove that this algorithm in fact achieves efficient learning.

###### Theorem 9 .

Suppose $\zeta=0$ and we can approximate the inverse of $\phi$ with $\tilde{\phi}^{-1}$ up to arbitrary precision, i.e. $||\phi(\tilde{\phi}^{-1}(x))-x||_{\inf}<c$ for any constant $c$. Then for any $\varepsilon$, there is an active learning algorithm that returns a linear hypothesis $\hat{u}$ with $e_{2}(\hat{u},u)\leq\varepsilon$ after asking the oracle $\mathcal{O}(m\log(\frac{\sqrt{m}}{\varepsilon}))$ queries.

###### Proof.

We would like to trap the true weight $w$ inside a $m-1$ dimensional hypercube with side length $2\varepsilon/\sqrt{m-1}$ so that
the longest possible distance between its centre and any point in the cube is the half diagonal $\frac{\sqrt{m-1}}{2}\cdot\frac{2\varepsilon}{\sqrt{m-1}}=\varepsilon$.
Then picking $\hat{w}$ as the centre of the cube will suffice the bounded error $e_{2}\leq\varepsilon$.

Therefore, our algorithm runs like a binary search on each of the $m-1$ dimensions. In order to shrink the length of the searching space in each dimension, we recursively select the query $(x,x^{\prime})$ with difference $\Delta_{\phi}(x)$ being the normal vector of the hyperplane (approximately) halving the original space along that dimension. Let us call the halving hyperplane $v$. Suppose the width of the version space $\mathcal{W}$ along the current axis is $s.$
By our presumption, we can achieve $||\Delta_{\phi}(x)-v||_{\inf}=||\phi(\tilde{\phi}^{-1}(\phi(x)+v))-(\phi(x)+v)
||_{\inf}<\frac{s}{10}.$

Depending on the noise-free signal, we can cut out at least $\frac{1}{2}-\frac{1}{10}=\frac{2}{5}$ of the space. Repeating the process for the new version space, since we go through the procedure for each dimension, we make $\mathcal{O}(\log(\frac{\sqrt{m-1}}{2\varepsilon})(m-1))$ queries in total. ∎

As before, when the preference labels are corrupted by noise, the problem becomes considerably more challenging, since we can no longer rely on a single label to exhibit an inconsistency among our hypotheses in a give version space.
We address this by repeatedly asking the same query many times, and choosing the majority response.
The resulting algorithm is provided as Algorithm 2.

Figure: Algorithm 2 Active Learning with Noise

We now show that this algorithm is sample-efficient, provided that the noise distribution is “nice” in the sense formalized next.

###### Theorem 10 .

For a fixed $\mathcal{Q}$ with corresponding c.d.f. $F$, suppose we can approximate the inverse of $\phi$ with $\tilde{\phi}^{-1}$ up to arbitrary precision, i.e. $||\phi(\tilde{\phi}^{-1}(x))-x||_{\inf}<c$ for any constant $c$, then there exists an active learning algorithm that outputs $\hat{u}$ with $e_{2}(\hat{u},u)\leq\varepsilon$ with probability at least $1-\delta$ after $\mathcal{O}(\frac{1}{(p_{0}-1/2)^{2}}\log(\frac{1}{\delta}))$ queries where $p_{0}=F(\frac{\varepsilon}{\sqrt{m-1}})>1/2.$

###### Proof.

Consider Algorithm  2, the high level procedure is as followed: for every query we constructed in Algorithm  1, we repeat each query $T$ times. If the majority of the answer is not clear, i.e., $|S_{T}-\frac{T}{2}|\leq\frac{T(p_{0}-1/2)}{2}$ then we know $w$ is close enough to the hyperplane determined by our query with high probability. Otherwise, we opt to trust the majority vote and halve the search space until the distance between our two hyperplanes is smaller than our required length. After looping through every dimension, we complete our hypercube.

Now we start calculating the upper bound of times we need to ask every turn. Let us denote the sum of a query’s labels after $T$ repetitions by $S_{T}.$ Without loss of generality, we assume that the true label of the query on $\Delta_{\phi}x$ is $1$. Then the expected value $\mathbb{E}(S_{T})>T/2$. Additionally, let $p_{0}$ denote the probability of labels flipping at the face of the hypercube to which $w$’s margin is bounded by $\frac{\varepsilon}{\sqrt{m-1}}.$

First, we would like that if we have witnessed $|S_{T}-\frac{T}{2}|\leq\frac{T(p_{0}-1/2)}{2}$, with high probability we have already queried a hyperplane with a small margin with respect to $w.$ By Hoeffiding’s inequality, we have $\Pr\left(|\mathbb{E}(S_{T})-S_{T}|\geq\frac{T(p_{0}-1/2)}{2}\right)\leq\exp(-
\frac{T(p_{0}-1/2)^{2}}{4}).$ So with probability at least $1-\exp(-\frac{T(p_{0}-1/2)^{2}}{4})$, $|\mathbb{E}(S_{T})-S_{T}|\leq\frac{T(p_{0}-1/2)}{2}$. Then the triangle inequality gives us $|\mathbb{E}(S_{T})-\frac{T}{2}|=|\mathbb{E}(S_{T})-S_{T}+S_{T}-\frac{T}{2}|
\leq|\mathbb{E}(S_{T})-S_{T}|+|S_{T}-\frac{T}{2}|\leq\frac{T(p_{0}-1/2)}{2}+
\frac{T(p_{0}-1/2)}{2}=T(p_{0}-\frac{1}{2})$ with probability at least $1-\exp(-\frac{T(p_{0}-1/2)^{2}}{4}).$ In other words, with high probability, $T/2<\mathbb{E}(S_{T})\leq T(p_{0})$. Since $\mathbb{E}(S_{T})$ is determined by the distance between the query and $w$, we deduce that the current query satisfies a small margin as wanted, hence we can stop.

Next, we would like to confirm the majority is the true label with high confidence if we have witnessed a majority vote with significance, i.e., when $|S_{T}-\frac{T}{2}|>\frac{T(p_{0}-1/2)}{2}$. Recall again with our true label being $1$, $\mathbb{E}(S_{T})>\frac{T}{2}.$ The probability of witnessing a false majority is $\Pr\left(S_{T}-\frac{T}{2}<-\frac{T(p_{0}-1/2)}{2}\right)=\Pr\left(\frac{T}{2}
-S_{T}>\frac{T(p_{0}-1/2)}{2}\right)\leq\Pr\left(\mathbb{E}(S_{T})-S_{T}\geq
\frac{T(p_{0}-1/2)}{2}\right)\leq\exp(-\frac{T(p_{0}-1/2)^{2}}{4})$ since $\mathbb{E}(S_{T})-S_{T}>\frac{T}{2}-S_{T}.$

From Theorem 9, we know we will need $\mathcal{O}(\log(\frac{\sqrt{m-1}}{2\varepsilon})(m-1))$ accurate query labels through votes. So the cumulative confidence is to satisfy

$$ $q^{\mathcal{O}(\log(\frac{\sqrt{m-1}}{2\varepsilon})(m-1))}\geq 1-\delta,$ $$

where $q$ is the success rate for each query on a different hyperplane.
Therefore $q\geq(1-\delta)^{\frac{1}{\mathcal{O}(\log(\frac{\sqrt{m-1}}{2\varepsilon})(m-
1))}}$.
And for each turn we just need
$\exp(-\frac{T(p_{0}-1/2)^{2}}{4})\leq 1-q$.
By a simple calculation, we get the sufficient number of repetitions from
$T\geq T_{0}=-\frac{4}{(p_{0}-1/2)^{2}}\log(1-(1-\delta)^{\frac{1}{\mathcal{O}(
\log(\frac{\sqrt{m-1}}{2\varepsilon})(m-1))}}).$

So our sample complexity is $\mathcal{O}(T_{0}m\log(\frac{\sqrt{m-1}}{2\varepsilon})=\mathcal{O}((\frac{1}{
F(\frac{\varepsilon}{\sqrt{m-1}})-1/2)^{2}}\log(\frac{1}{\delta})))$. ∎

The efficiency result in Algorithm 2 thus depends on the noise c.d.f. $F(x)$.
We now show that the condition on the noise in Theorem 2 obtains for the common case of logistic noise (i.e., the Bradley-Terry model).
Thus, we obtain a sample-efficient active learning algorithm for learning utility parameters in the $\ell_{2}$ norm when comparison query responses follow the BT model.

###### Corollary 11 .

For the standard logistic function $F(x)=\frac{1}{e^{-x}+1}$, the sample complexity is polynomial in $(\frac{1}{\varepsilon},\log(\frac{1}{\delta}),m)$.

###### Proof.

Because for $x=\frac{\varepsilon}{\sqrt{m-1}}\in(0,1),\exp(x)\geq 1+x$,
so $\exp(\frac{-\varepsilon}{\sqrt{m-1}})\leq\frac{1}{1+\frac{\varepsilon}{\sqrt{m
-1}}}$.
And $\mathcal{O}(\exp(\frac{-\varepsilon}{\sqrt{m-1}})\log(\frac{1}{\delta}))$ is in
$\mathcal{O}((\frac{\sqrt{m}}{\varepsilon})\log(\frac{1}{\delta})).$
∎

Comparing this result with the passive learning result from inequality (3), whose sample complexity is $\mathcal{O}(\frac{1}{\varepsilon}\log(\frac{1}{\delta})+\frac{m}{\varepsilon})$, our sample complexity bound is much better
since for any $m\in\mathbb{N}$ and $0<\varepsilon<1$, $\varepsilon^{\sqrt{m-1}}<\varepsilon<1<\exp(\varepsilon),$ implying $\frac{1}{\varepsilon}\log(\frac{1}{\delta})>\frac{1}{\exp(\frac{\varepsilon}{
\sqrt{m-1}})}\log(\frac{1}{\delta})$.

###### Theorem 9 .

###### Proof.

###### Theorem 10 .

###### Proof.

###### Corollary 11 .

###### Proof.

## 6 Conclusion

We presented an investigation of learnability of linear utility functions from pairwise comparison queries.
Our results consider both the passive and active learning problems, as well as two objects, the first involving *prediction* while the second concerned with *estimation*.
Overall, we find that estimation is generally more challenging than prediction, and active learning enables qualitatively better sample complexity in this case.
There are a number of directions to extend our work. For example, one can aim to generalize our results to list-wise comparisons described in [].
Specific to active learning, especially related to LLM and RLHF, we acknowledge the challenges of query synthesis, as well as the issue of inverting the embedding $\phi(x)$.
Thus, there is considerable room for follow-up work in this regard.
Finally, our framework is restricted to linear utilities, even accounting for a non-linear embedding.
An important direction for future work is to consider more general classes of utility models, such as those using neural network architecture.

## A: Proof of Theorem 7

###### Proof.

Recall that $\Pr(x^{\prime}\succ x)=F(w^{*^{T}}\Delta_{\phi}(x))=1-F(-w^{*^{T}}\Delta_{\phi
}(x))=1-\Pr(x\succ x^{\prime})$.
First, we show the strong convexity of the loss function

$$ $\ell(w)=-\frac{1}{n}\sum_{i=1}^{n}\log\left(1(y^{i}=1)\cdot\Pr(x^{\prime}\succ x )+1(y^{i}=0)\cdot\Pr(x^{\prime}\prec x)\right)$ $$

$$ $=-\sum_{i=1}^{n}\log\left(1(y^{i}=1)\cdot F(w^{T}\Delta_{\phi}(x))+1(y^{i}=0) \cdot F(-w^{T}\Delta_{\phi}(x))\right).$ $$

Its gradient and Hessian are

$$ $\nabla\ell(w)=-\frac{1}{n}\left[\sum_{i=1}^{n}\left(1(y^{i}=1)\cdot\frac{F^{ \prime}(w^{T}\Delta_{\phi}(x))}{F(w^{T}\Delta_{\phi}(x))}+1(y^{i}=0)\cdot\frac {F^{\prime}(-w^{T}\Delta_{\phi}(x))}{F(-w^{T}\Delta_{\phi}(x))}\right)\right] \Delta_{\phi}(x)$ $$

$$ $\nabla^{2}\ell(w)=\frac{1}{n}\sum_{i=1}^{n}(1(y^{i}=1)\cdot\frac{F^{\prime}(w^ {T}\Delta_{\phi}(x))^{2}-F^{\prime\prime}(w^{T}\Delta_{\phi}(x))\cdot F(w^{T} \Delta_{\phi}(x))}{F(w^{T}\Delta_{\phi}(x))^{2}}$ $$

$$ $+1(y^{i}=0)\cdot\frac{F^{\prime}(w^{T}\Delta_{\phi}(x))^{2}-F^{\prime\prime}(- w^{T}\Delta_{\phi}(x))\cdot F(-w^{T}\Delta_{\phi}(x))}{F(-w^{T}\Delta_{\phi}(x ))^{2}})\cdot\Delta_{\phi}(x)\Delta_{\phi}(x)^{T}$ $$

By assumption, we have $F^{\prime}(z)^{2}-F^{\prime\prime}(z)\cdot F(z)\geq\gamma>0$.
Then we can derive strong convexity of $\ell$:

$$ $v^{T}\nabla^{2}\ell(w)v\geq\frac{\gamma}{n}||Xv||_{2}^{2}\quad\text{for all }v,$ $$

where $X$ has $\Delta_{\phi}(x_{i})$ as its $i$-th row,
yielding

$$ $\ell(\hat{w})-\ell(w^{*})-\langle\nabla\ell(w^{*}),\hat{w}-w\rangle\geq\frac{ \gamma}{n}||X(\hat{w}-w^{*})||_{2}^{2}=\gamma||\hat{w}-w^{*}||^{2}_{\Sigma}.$ $$

Since $\hat{w}$ is the optimal for $\ell$,

$$ $\ell(\hat{w})-\ell(w^{*})-\langle\nabla\ell(w^{*}),\hat{w}-w^{*}\rangle\leq- \langle\nabla\ell(w^{*}),\hat{w}-w^{*}\rangle.$ $$

Then as

$$ $|\langle\nabla\ell(w^{*}),\hat{w}-w^{*}\rangle|\leq||\nabla\ell(w^{*})||_{( \Sigma+\lambda I)^{-1}}||\hat{w}-w^{*}||_{\Sigma+\lambda I},$ $$

we now would like to bound the term $||\nabla\ell(w^{*})||_{(\Sigma+\lambda I)^{-1}}.$

Note the gradient $\nabla\ell(w^{*})$ can be viewed as a random vector $V\in\mathbb{R}^{n}$ with independent component:

$$ $V_{i}=\begin{cases}\frac{F^{\prime}(w^{*^{T}}\Delta_{\phi}(x_{i}))}{F(w^{*^{T} }\Delta_{\phi}(x_{i}))}&\text{w.p.}~{}F(w^{*^{T}}\Delta_{\phi}(x_{i}))\\ \frac{F^{\prime}(-w^{*^{T}}\Delta_{\phi}(x))}{F(-w^{*^{T}}\Delta_{\phi}(x_{i}) )}&\text{w.p.}~{}F(-w^{*^{T}}\Delta_{\phi}(x_{i}))\end{cases}.$ $$

We know that $F(w^{T}\Delta_{\phi}(x_{i}))+F(-w^{T}\Delta_{\phi}(x_{i}))=\Pr(x^{\prime}\succ
x
)+\Pr(x\succ x^{\prime})=1$, taking the derivative of this equation, we can conclude that the expected value is zero $\mathbb{E}[V]=F^{\prime}(w^{T}\Delta_{\phi}(x_{i}))+F^{\prime}(-w^{T}\Delta_{
\phi}(x))=0$.

And because $F$ is the c.d.f., and $F^{\prime}$ is the p.d.f, by definition $F^{\prime}(z)<F(z)$, and
$\frac{F^{\prime}(w^{T}\Delta_{\phi}(x_{i}))}{F(w^{T}\Delta_{\phi}(x_{i}))}<1$, $\frac{F^{\prime}(-w^{T}\Delta_{\phi}(x))}{F(-w^{T}\Delta_{\phi}(x_{i}))}<1.$

Hence all the variables $V_{i}$ are $1$-sub-Gaussian, and the Bernstein’s inequality in quadratic form applies (see e.g. [] (Theorem 2.1)) implies that with probability at least $1-\delta$,

$$ $||\nabla\ell(w^{*})||^{2}_{(\Sigma+\lambda I)^{-1}}=V^{T}MV\leq C_{1}\cdot \frac{d+\log(1/\delta)}{n},$ $$

where $C_{1}$ is some universal constant and $M=\frac{1}{n^{2}}X(\Sigma+\lambda I)^{-1}X^{T}$ .

Furthermore, let the eigenvalue decomposition of $X^{T}X$ be $U\Lambda U^{T}.$
Then we can bound the trace and operator norm of $M$ as

$Tr(M)=\frac{1}{n^{2}}Tr(U(\Lambda/n+\lambda I)^{-1}U^{T}U\Lambda U^{T})\leq
\frac{d}{n}$

$$ $Tr(M^{2})=\frac{1}{n^{4}}Tr(U(\Lambda/n+\lambda I)^{-1}U^{T}U\Lambda U^{T})U( \Lambda/n+\lambda I)^{-1}U^{T}U\Lambda U^{T})\leq\frac{d}{n^{2}}$ $$

$||M||_{op}=\lambda_{max}(M)\leq\frac{1}{n}$

This gives us

$$ $\gamma||\hat{w}-w^{*}||^{2}_{\Sigma}\leq||\nabla\ell(w^{*})||_{(\Sigma+\lambda I )^{-1}}||\hat{w}-w^{*}||^{2}_{\Sigma}$ $$

$$ $\leq\sqrt{C_{1}\cdot\frac{d+\log(1/\delta)}{n}}||\hat{w}-w^{*}||^{2}_{\Sigma}$ $$

Solving the above inequality gives us,

$$ $||\hat{w}-w^{*}||_{\Sigma}\leq C_{2}\cdot\sqrt{\frac{d+\log(1/\delta)}{n}}$ $$

∎

###### Proof.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: It would be nice if the authors could explain the technical novelty of this work.
soundness: 3
strengths: The problem studied is very clean and interesting to the learning theory community.

The writing is very clear.
summary: This paper addresses PAC learning of linear functions using comparison queries. It considers two objectives: predicting the outcome of a comparison between two inputs and learning the true underlying linear parameters. Both noiseless and noisy settings are explored, as well as both active and passive learning.
weaknesses: I believe the primary weakness of this paper lies in its technical contributions. I didn't find anything particularly novel or technically interesting.

For instance, the results in passive learning don't appear to be new. Theorems 1 and 3 have been previously addressed, and the observation in Theorem 2 seems straightforward—naturally, certain noisy models prevent learning. Similarly, the conclusion in Theorem 6 also seems obvious.

In the active learning setting, the problem of active learning for halfspaces with comparison queries appears to have already been solved by [1].

[1] Kane, Daniel M., Shachar Lovett, Shay Moran, and Jiapeng Zhang. "Active classification with comparison queries." In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 355-366. IEEE, 2017.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - in the active learning setting, is the sample complexity optimal?
soundness: 3
strengths: - This paper studied a significant and practical problem of reward learning, when the observations are pairwise comparison queries. This can be a common scenario in real-world examples such as online recommendation platforms. Overall the paper is presented with a good clarity on the model, assumptions and results.
- The theoretical analysis justified an interesting learnability gap between the passive and active learning settings, where the active queries significantly helped with the utility function estimation. This result may be helpful to provide guidance for real-world applications where the active queries may be obtained via incentivization.
summary: This paper studied the learnability of linear utility functions from pairwise comparison queries. The paper considered two settings, including the passive learning setting and the active learning setting, with two objectives: 1) predicting the out-of-sample pairwise preferences; 2) estimating the true parameters of the utility function. Theoretical analysis show that in the passive learning case, the first objective is achievable both when query responses are uncorrupted by noise / under Tsybakov noise when the distributions are sufficiently nice. However the utility function parameters may not be learnable. In contrast, in the active learning setting, both objectives can be efficiently achieved.
weaknesses: In the active learning setting, the estimation of the utility function relies on the ability to invert the embedding function, and obtaining the inverse of the embedding can be computationally challenging or infeasible particularly with neural network models.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 4
questions: 1. What concrete take-aways should a practitioner doing preference-based LLM alignment get from the paper? Which theoretical findings can infrom practice?
2. Much of the theory seems to exploit the fact that learning from pairwise comparisons in linear RUMs is equivalent to linear binary classification. Which insights are unique to the fact that we observe pairwise comparisons?
soundness: 4
strengths: - The paper is particularly well written and easy to follow. The organization is clear, the progression makes sense, and the decisions on what to include in the main text and what to defer to the supplementary material are well thought-through.
- The results appear to be rigorous. I did not check every single proof, but the ones I checked appear to be correct and, in general, the arguments make sense.
- Research on this topic is timely, given the increasing interest in practical applications, and highly relevant to the ICLR community.
summary: Driven by applications in LLM alignment, this paper studies the problem of learning linear utility functions from pairwise comparisons. The authors provide theoretical results that suggest the following.

- Efficiently PAC-learning utilities that predict pairwise comparison outcomes is possible, except in degenerate cases.
- Learning the utility parameters can fail when the RUM does not satisfy certain conditions. The noiseless case is an example of failure case.

The authors then consider the active learning setting, where queries can be chosen adaptively based on previously observed outcomes. In that setting, it is possible to efficiently PAC-learn utility parameters in the noiseless case.
weaknesses: - While the exact problem studied in the paper does not have a lot of prior work (to my knowledge), there is an extensive literature on learning RUMs from pairwise comparisons over a fixed set of items with an independent utility for each item in the set. This can be recast as sparse "one-hot" features in the model studied in the paper.
    - some of the insights the paper provides are well-known in that literature. For example, sample complexity results for the Bradley-Terry model typically depend on the noise via the dynamic range, i.e., the maximum ratio between item utilities. The case of unbounded dynamic range has been studied before. Some references: [1], [2], [3].
    - making connections to this literature by comparing & contrasting results would improve the paper significantly.
- In general, I find the connection between the theory developed in this paper and LLM alignnment a bit weak. The paper could be incredibly impactful if there were concrete take-aways that could inform practice. Are there any?
    - l 082: "Our results thus suggest that conventional reward model [...] may yield potentially misleading estimates". Backing this claim up with real data or at least realistic experiments would be helpful.
- The motivation for the active learning section could be improved.
    - The authors say: "first [...] curates a dataset of input pairs, and only then obtains preference data for these". This is the exact _opposite_ of active learning, and indeed the two papers cited (OpenAI & Anthropic) are examples of passive learning.
    - However there is work showing that active learning can improve LLM alignment techniques, see e.g. [4] and [5], so I see an opportunity to make the point much more convincingly.

Minor feedback:

- l 046: "... over a vector space of outcomes" -> what does this mean?
- l 095: "the restriction of our utility function is qeuivalent to ..." -> I could not make sense of this sentence.
- l 154: "with probability $1-\delta$ such that ..." I think this should be flipped: "such that ... with probability $1-\delta$"
- Theorem 2 seems kind of obvious: if one can make outcomes arbitrarily noisy, it can get arbitrarily hard to learn. Is there a deeper insight I am missing here?

References:

1. Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model <https://proceedings.mlr.press/v162/bong22a/bong22a.pdf>
2. l-infty-Bounds of the MLE in the BTL Model under General Comparison Graphs <https://proceedings.mlr.press/v180/li22g/li22g.pdf>
3. Active Ranking in Practice: General Ranking Functions with Sample Complexity Bounds <https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=52f514508329c951ef9b417ce5243cf40db136bd>
4. Active Preference Learning for Large Language Models <https://arxiv.org/pdf/2402.08114>
5. Direct Language Model Alignment from Online AI Feedback <https://arxiv.org/pdf/2402.04792>

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Refer to the weaknesses section above and find the additional questions below:
1. Is there a lower bound for the sample complexity in Theorem 3? It seems that the complexity could be exponentially high with respect to $1/\alpha$.
2. Is it possible to extend beyond linear utility functions, particularly for the simpler problem of predicting pairwise comparisons?
soundness: 3
strengths: Please find the strengths below:
1. The problem of learning the linear utility function is important in AI. The paper addresses both passive and active learning settings, which are commonly encountered in practice.
2. For passive learning, the paper presents a negative result regarding the learnability of linear utility function parameters.
3. The proofs in the main paper are clear and intuitive to follow.
summary: The paper explores the feasibility of learning linear utility functions from pairwise comparison queries, proposing that this method can be applied to improve AI alignment with human values. The study addresses two levels of the problem: predicting out-of-sample pairwise comparisons and accurately estimating utility parameters. In the passive learning setting, it demonstrates that predicting comparisons is feasible, but estimating utility parameters is challenging without strong structural noise assumptions. The negative result, indicating that the linear utility function is not PAC-PC learnable, is presented in this setting. In the active learning setting, where comparisons can be strategically selected, estimating utility parameters becomes much more feasible, provided there is the ability to invert the embedding.
weaknesses: Please find the weaknesses below:
1. The paper lacks intuitive explanations for these assumptions, such as examples of cases where the assumptions are satisfied.
2. The paper does not sufficiently discuss the practicality of assumptions, such as those on well-behaved isotropic distributions, $F'(z)^2 - F''(z) \cdot F(z) \geq \gamma$, and the approximation of the inverse of $\phi$. It is unclear how to determine parameters (e.g., $c$ and $\gamma$) in these assumptions in practice.
3. In Theorems 3, 7, and 8, the paper only establishes the existence of an efficient algorithm but does not explain how to find the algorithm within the main text (though pseudo code for Theorems 7 and 8 is provided in the appendix).
4. The paper lacks experiments assessing the complexity of the algorithms. Even some numerical experiments would be beneficial, as would verification of these assumptions on practical datasets.

Meta-review: This paper studies the problems of learning linear utility function from pairwise comparison feedback. This paper gives solid theoretical guarantees in both passive learning and active learning setting, with rigorous sample complexity guarantees. This paper consists a set of solid and interesting theoretical results. However, while the paper motivates the problem from the practical RLHF, how to algorithms and sample complexity derived from this paper are quite unclear. Several algorithms used in this paper are very different from what were used in practice. If authors could also provide a few empirical evidence on the superiority of the proposed methods that can potentially make the work much more impactful. We recommend rejection based on its current form.

Decision: Reject