When Can Proxies Improve the Sample Complexity of Preference Learning?
Authors: Yuchen Zhu
Daniel Augusto de Souza
Zhengyan Shi
Mengyue Yang
Pasquale Minervini
Matt Kusner
Alexander Nicholas D'Amour
Venue: ICML 2025 poster (2025)
Keywords: AI safety; preference learning; RLHF; reward hacking; learning theory; proxy feedback
Primary area: theory->domain_adaptation_and_transfer_learning
TL;DR: We clarify conditions and propose a model parameterisation to allow proxy data to aid the learning of a target function, and analyse sample complexity.

Abstract: We address the problem of reward hacking, where maximising a proxy reward does not necessarily increase the true reward. This is a key concern for Large Language Models (LLMs), as they are often fine-tuned on human preferences that may not accurately reflect a true objective. Existing work uses various tricks such as regularisation, tweaks to the reward model, and reward hacking detectors, to limit the influence that such proxy preferences have on a model. Luckily, in many contexts such as medicine, education, and law, a sparse amount of expert data is often available. In these cases, it is often unclear whether the addition of proxy data can improve policy learning. We outline a set of sufficient conditions on proxy feedback that, if satisfied, indicate that proxy data can provably improve the sample complexity of learning the ground truth policy. These conditions can inform the data collection process for specific tasks. The result implies a parameterisation for LLMs that achieves this improved sample complexity. We detail how one can adapt existing architectures to yield this improved sample complexity.

When Can Proxies Improve the Sample Complexity of Preference Learning?
Yuchen Zhu' Daniel Augusto de Souza' Zhengyan Shi! Mengyue Yang? Pasquale Minervini
Matt J. Kusner 45 Alexander D'Amour
Abstract
In many cases, this preference data is a proxy for the ground truth. For example, humans raters tend to prefer longer answers to a question, even if the answer less informative (Zhou al., 2024). In this case, 'response length' a proxy for the true helpfulness of an answer. If an LLM is trained this proxy data alone it leads to 'length-bias' (Shen et al., 2023; Singhal et al., 2023), as LLMs tnnettned with this preference data generate longer and better formatted responses to appear more helpful (Chen et al., 2024). This is an example of the well-known phenomenon of reward hacking': a model optimised to perform well with respect to proxy reward function, performs poorly with respect to a ground truth reward function (Casper et al., 2023). Reward hacking is fundamental problem in learning that has been observed in optimised circuits listening in on the oscilla- tors of other computers when instead tasked to build their own (Bird & Layzell, 2002), universities rejecting the most qualified applicants to boost their ratings (Golden, 2001), and many other cases in game playing (Clark & Amodei, 2016), autonomous driving (Knox et al., 2023), and text summarisation (Paulus et al., 2018).
We address the problem of reward hacking, where maximising a proxy reward does not necessarily increase the true reward. This is a key concern for Large Language Models (LLMs)) as they are often fine-tuned on human preferences that may not accurately reflect true objective. Existing work uses various tricks such as regularisation, tweaks to the reward model, and reward hacking detectors, to limit the influence that such proxy preferences have on a model. Luckily, in many contexts such as medicine, education, and law, a sparse amount of expert data is often available. In these cases, it is often unclear whether the addi- tion of proxy data can improve policy learning. We outline feedback that, if satisfied, indicate that proxy data can provably improve the sample complexity of learning the ground truth policy. These condi- tions can inform the data collection process for specific tasks. The result implies a parameterisa- tion for LLMs that achieves this improved sample complexity. We detail how one can adapt exist- ing architectures to yield this improved sample complexity.
of sufficient conditions on proxy
To address reward hacking in LLMs, prior work largely de- signs tweaks to the model, data, and optimization procedure. This includes regularisation towards an initial policy (Schul- man et al., 2017; Rafailov et al., 2023; Huang et al., 2024), changing properties of the reward model (Gao al., 2023;
Coste et al., 2024), using soft labels (Zhu et al., 2024), ad- justing optimization hyperparameters (Singhal et al., 2023), reward hacking detection mechanisms (Pan et al., 2022; Miao et al., 2024), and introducing additional tools spe- cialised to counteract length bias (Chen et al., 2024). The reasoning behind this comes from the makeup of proxy data. We can think of proxy data as having two parts: (i) true part that brings a policy closer to the ground truth policy during learning and (ii) a false part that moves it farther away. Prior work limits learning to reduce the impact that the false part has on the final model.
1. Introduction
Large Language Models (LLMs) have revolutionised ma- chine learning with their surprising capabilities, surpassing human-level performance in law, medicine, and other exam- inations (Achiam et al., 2023; Amin et al., 2023). large part of their success is their ability to incorporate human preferences to learn complex objectives such trustworthi- ness (Yu et al., 2024), sentiment preferences (Chakraborty et al., 2024), and value alignment (Ji et al., 2023).
'Department of Computer Science, University College London University of Bristol 'University of Edinburgh 'Polytechnique Montréal "Mila- Quebee Al Institute 'Google Deepmind. Corre- spondence to: Yuchen Zhu <yuchen.zhu, 18@ ack.uckkk
Without any further information on proxy preferences or the ground truth, we are restricted to methods such as these, i.c., methods that are blind to the true and false parts of proxy data, to reduce the impact of reward hack-
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
'This also sometimes referred as reward over-optimissation.

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
Figure 1. condition for useful proxy feed- back. (Illustrative purposes only. Not med- ical advice.) An expert (ground truth) doctor preseribes a different treatment compared with student (proxy) doctor. However, Patients and 2 are identified as lying within the same level set of patients by both doctors, based on their key characteristics age. lifestyle and symptoms. Patient has sufficiently different characteristics from Patient and and is identified to lic within different level set by both doctors.
True policy 7t (egg experienced doctor)
Proxy policy & (eg student doctoc)
[ Miv1 N. Mis th Mi 1,2
gh+1 Xy Ua.
Del 1,2
Patient X1
Patienl
Ages 23
Age: 23
Kowp
bring down Idoold
Sswey brog dows evet
pataiiles
Lifoutyles
Lifestyles
MSe student
PhD stackant
Sympiami:
Symplem:
"Houducio alter bing dowa could octioms preeeibee blood test."
"Houlacia with your job is cansed by preserbbe polnkillees.
Mocuing hoadache
Morning headache
E 2ov1 Ny,
Paticut X5
Age: A0
Xirep
beatt sttad
BCG
beart wtrack
Bin
dit daapp
Lifeetyle: Yearher
Symptome
Fever nineeo book pain
Lot's BDG could related.
"Rest well, healthy diet. exeedao.
ing (Pan et al., 2022). Luckily, in many settings, we also have access to sparse observations of high-quality prefer- ences (Daniels-Kood & Freedman, 2022). For instance, in demonstration
useful information to extract from the prolific proxy data. A natural question is: When can proxy data ever provably improve preference learning?
reinforcement learning, expert data is added to improve sample efficiency (Rajeswaran et al., 2017) and to guide exploration (Nair et al., 2018). Recent work has shown that including such expert information can help counter reward hacking in LLMs (Rita et al., 2024).
In this paper we outline a set of sufficient conditions on proxy feedback that, if satisfied, indicate that the proxy can provably improve the sample complexity of learning the ground truth policy. As not all proxies will satisfy these conditions, they can be used guide data collection pro- cess for a specific task. We show that as long as the col- lected proxy feedback shares certain properties with the true feedback, the sample complexity of learning with true preference data is provably improved by first training on large amounts of proxy preference data. The key idea be- hind this is that if the proxy and true policies share certain structure, characterised Condition 2-1, then is possible to express the true policy as con-dimensional adaptation of the proxy policy (Theorem 3). This relationship implies that certain parameters of the ground truth policy can be identified solely from proxy data, reducing the number of ground truth samples needed to learn the ground truth policy (Theorem 5, 6). This result immediately implies parametri- sation for L.MSs that achieves improved sample complexity. Our contributions are:
Consider the following medical example depicted in Fig- ure 1. Patient and Patient 2 consult the expert doctor and the student doctor about condition they have. They have similar characteristics and essentially the same problem: recurring morning headache that lasted a few days, but their exact phrasings can be different. Meanwhile, Patient 3 has different characteristics and a different condition to Patient 1 and 2. We think of the experienced doctor as representing true policy and the student as proxy policy. The two doctors both assign Patient 1 and 2 to the same group and Patient 3 to a different group, but the two doctors' recom- mendations for a given group are different, since the expert doctor can correctly recognised some easily misdiagnosed symptoms while the student doctor cannot.
We assume access to sparse prescriptions from an experi- enced doctor (ground truth) and plentiful prescriptions from less experienced student doctors (proxy). Even with ground truth data, If we naively learn policy on the union of the dataset, we will learn a policy close to the proxy policy, as this data is more abundant. However, given the success of preference learning methods for LLMs, there is often
We characterise set of sufficient conditions on proxy feedback such that the sample complexity of learning the true policy is reduced through learning on the proxy.
We show that if proxy feedback satisfies the sufficient conditions, it implies a specific model parametrisation
2

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
and learning procedure to extract information from the proxies. We detail these and describe how one can adapt existing architectures to improve sample complexity.
the one that maximises the following optimisation objective: arg max, Bawppe yoor(- (n(rr v) [KL(((y) ()) Terly zt)),
2. Preliminaries
where the regularisation parameter f controls how close to the reference the optimum should be. Under this objective, the optimal policy is given by:
Consider the set of all prompts X' and completions y, the elements of these sets are discrete sequences of tokens with By considering
arbitrary length, e.g. x [.1..... : NN..
Tt a:) xx merly ()) exp { (g)(,r)))
enumeration of all completions )/ the space of distributions Py is equivalent to the subset of non-negative and unit norm sequences in the sequence space el." 2
(2)
The target policy we aim to learn is thus denoted æ² satisfy- ing (2) with respect to GJ = (r², Tee,, Px)
We think about a policy т as a map from prompt space X' to the distribution space Py. Starting from an initial policy Teer. we want to find a target policy πl X' + Py which aligns with the preferences of an ideal actor in given scenario. To Iearn this policy, we have preference data directly from the ideal actor, denoted Dt, as well as preference data from a proxy actor, D. The central question we consider is: under what assumptions can D improve the sample complexity of learning क. ?
Direct preference optimisation (DPO) and implicit re- wards. Following Rafailov et al. (2023), by optimising the following objective:
arg max, B. [oo (oogor(80 (Blog x.w ax)
e.lu.. 1 B log
a(s Ia)
mwi (
we recover the same optimal policy as described in Equa- tion 2 without directly using any reward function. Thus, DPO avoids the need for reward modelling.
Human preference feedback. We aim to align Teet using preference data of the form {(xr you )² where You and yı are candidate completions for prompt æ. and where yo is preferred to yı- We assume these preferences are generated from a underlying scalar reward function r raz y) according to Bradley& & Terry (1952):
We note that the policy implicitly defines reward function,
(y x)
r(æ, y) = =Blog
yer (
ar)
We can therefore define nl, क as the policies that (implicitly) define rf and f. respectively.
x px; y1, U2 ~ Tze( | a); lid. ~ Bern[o(r(z, 81) - r(z, y2))];
True and proxy preference data For many interesting tasks, sampling a dataset DI x* := {(E,, Bu, Je. from Gt = (r), Tref, Pxx can be costly; therefore, the size n of the dataset might not be large enough for adequate training. In these cases, it is common to use a larger proxy dataset DA := ((ē., Gu Hr where each data point is sampled i.i.d. from a proxy data-gener distribution G (F, Tre. Px). where G and G only differ in the reward.
(11,y2) i = 1,
(y y1)
(y2. i = O."
where (-) is the sigmoid logistic function. We assume that yi and y/2 are sampled from Tref for simplicity, whereas in practice they can be sampled from other distributions over Py. In this model, higher relative rewards increase the chance of a completion being picked as the winner Yov
Nonetheless, if we do not have data from G+, then even if we have access to infinitely many data samples from G. and even if it allows us to learn the perfect reward model 7*, we can at best only learn the optimal proxy policy â which differs from the optimal true policy in a², by construction due to the difference in rewards.
We assume that the true and proxy preference data, Dt and D, are generated by distinct reward functions rt and A.
Bandit problem setting. Given a data-generating process G= (r, Wee Px) with reward function r. a reference policy Tiet and a distribution of prompts px, the optimal KL- regularised policy ae for the data generating process G is
3. Sufficient Conditions for Proxy Feedback
2gl is the space of sequences {y:}: such that Ee |yil < co. The suhset we consider is the subset of such sequences where all y, are non-negative and _x [96] 1.
Theory and survey papers point out the difficulty of align- ment under mismatch between the true reward function and
'In practice, The is obtained from the supervised finetuning stage of language model training (Rafailov et al., 2023).
"The technical condition for this to be possible is be provided Px and The have full support.
3

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
the one reflected by the human labelers (Skalse al., 2022; Casper al., 2023). In other related fields such vision, (Chi et al., 2022) shows the impossibility of leveraging pre- pre-training data for unseen tasks unless some similarity between the two tasks is given.
have: x (-1=1)= = (-1
(1122) (f
= # x22).
Proof that Condition 1 iimplee Condition 2. 7(- x1)
T(- x2) implies that dpy ( (+11111,, (((x2))) = 0. Then no-
tice 0 2 dpy ( (-121), x (1122) 2 0, which then implies
ot (+121) = x (-122).
From these observations we can draw two conclusions. (i) We must have at least some data from Gf to learn oī; this motivates the need for both D., and Dg. (ii) In order for A inform us something about I²,, they must share some similarities. Thus, we ask the following research question:
Condition 2 says that two distinct prompts are mapped to the same response distribution under the true policy whenever they are under the proxy policy, and vice versa; mathemati- cally, the two policies share level sets (Figure 2. left).
What conditions allow for improved G -sample efficiency in learning n² after first training on D? By how much?
In the context of the running example (Figure 1), Condi- tion 2 corresponds to the experienced doctor and the student doctor classifying the symptoms of patients in the same way. We could reasonably expect this because comprehending the relevant details of a patient's query is part of the basic train- ing for a doctor. On the other hand, if the proxy preferences were sourced from generic crowd workers with no medi- cal background, we would not expect this condition to be satisfied. Practically, survey instruments could be designed to directly assess this assumption, for example, by asking raters to rate the equivalence between different prompts.
With the following conditions, we show that, when we have access to large amounts of proxy data, I can be expressed as fow-dimension adaptation of म, and hence the sample complexity of learning x is drastically improved, superex- ponential in the data manifold dimension.
In practice, these conditions can be helpful in guiding the design of the proxy data collection procedure. In particular, the conditions correspond to the expertise we might require proxy raters and true raters to share.
Our first technical condition concerns the similarity between the policy functions æ² and ăt
Since मे and n² share the same level sets, as supposed in Condition 2, it can be shown that n² o + is a well- defined function, where it should be noted that #= "ax(2) (p) maps a point p E (X)) to its pre-image under म. The proof is provided in Appendix B.
Condition 1. For a given metric dpy on the space of dis- tributions on y, there is some positive scaler I. such that dp, (T (-I=1), T (-(x2)) S Ldpy(f(-(xr)) (((1=11),(((11))))
Lemma 1. Suppose Condition 2 is satisfied, n o " is well defl-de function, where o denotes function compo- sition.
Informally, this says that if two prompts are mapped to very similar completion distributions by मं then they cannot get mapped to very different completion distributions by , for a unit difference of the former, the difference for the latter must not exceed L for some positive scaler L.
Lemma allows us to describe the 'difference' between the proxy and true policy as function: given distribution of completions p. лr o f (x)) maps all input prompts which share the response distribution p by म to distinct response distribution, say p', assigned by æ². This justifies learning an 'adapter' function which reassigns p to the correct value p'. Had Condition not held, then attempting to learn a function which assigns p to p' no longer makes sense since there could be some values of p for which the corresponding p' aren't unique.
This condition applies to situations where the proxy rater is within reasonable ballpark from the true rater: for example, for some medicines the correct dosage can vary by a large amount depending on the patient; if the expert doctor pre- scribes a certain dosage, and the student doctor preseribes a dosage different but close to that, then the condition can be considered satisfied. The condition also generalises to broader situation: if the expert doctor's change in pre- scription, for instance, after observing some improvements in a patient, is similar to the change in prescription of a student doctor, then the condition can also be considered satisfied. However, in situations of crowdsourcing human preference from general populations, such as with Amazon Mechanical Turk, we cannot consider this condition to be satisfied; likewise, if we suspect that some proxy raters are adversarial, then we also cannot expect it satisfied.
Our next condition says that the set of expert response dis- tributions is contained within the set of proxy response distributions (Figure 2, middle):
Condition 3 (Image inclusion). xt xx()) S #(2).
In the context of the running example (Figure 1), Condi- tion 3 says that the student doctor could, in principle, express any valid medical advice distribution, even if the student doctor may not know how to assign them to appropriate symptoms with high accuracy. This is again a reasonable assumption when the proxy feedback comes from a student
Condition I implies another, easier-to-visualise, condition: Condition (Shared level sets). Given 1 322 E X, we
4

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
Prompt Space
Generation Distributions
Prompe Space
Generation Distributions
Generation Distributions
X
Py
X
Py
R
Py
(((2))
X]
7(Z)
#(x)
(1
moming Tagdache"
"I have heodacho as l'wake up."
Figure 2. Illustrations of Conditions 2-4, Left, middle, right: Condition 2, 3, 4, respectively.
doctor, but is less plausible if the proxy feedback comes from rater without general knowledge of core concepts that underlic medical advice. Practically, surveys could in- clude questions to test the breadth of the rater's knowledge, or to gauge their educational background.
Proof. Proof in Appendix A.
In practical LLM training regimes, maximum sequence length is implemented, but the dimension of Py grows ex- ponentially with I. In situations where the true and proxy policies generate responses from a small subset of all token sequences, it could be reasonable expect Condition to hold for example, only small subset of all token se- quences form valid sentences, and those form valid medical advice, so we expect that for med- ical imestion-answerrie tasks the responses distributions can be encoded with fewer dimensions than for general tasks. The low-dimensional encoding can be viewed as some intermediate representation of the prompt that sufficient for determining the response distri- bution. We can thus think of o policy decoder.
Finally, need a technical condition similar common assumption underpinning many modern deep learning ar- chitectures: that data lie on lower-dimensional manifold (Figure 2, right).
smaller subset of
Condition 4 dimens-aimnsio encoding of (x))). There exists an injective function Φ: V - Py, where V C RD is a bounded convex polytope with D + vertices, such that:
1. The image Φ(V) contains the image of the policies: at x((x) S (x)))= C (VV);
2. 11 is bbi--)-bi-ippschitt with its left inverse V: (L/Lg 1)(le ozllp
4. Adapting ग to πl
11; Py (((lv), Lollvi - vallg. where d is metric Py. discussed later in Section
Now, we derive an algorithm for learning n| leveraging conditions 2-1. The algorithm hinges on decompositon of the policy म into an encoder म, a linear layer θ, and decoder o, respectively. Importantly,
Note that the condition that V is a convex polytope be- nign, since we can extend any bi-Lipschitz function which bijects compact subset of - with (X)) bi-Lipschitz function from bounded convex polytope with the same Lipschitz constants to a set containing # (2*).
show that nt can be expressed reusing these components from learning f using D, with the addition of low-dimensional adapter function between known spaces. This reduction to learning an adapter function allows us to derive a drastic sample complexity improvement (Theorem 5).
Condition 4 says that although the topological dimension of Py can be extremely large, the image of से is identified with Euclidean subset only of dimension D & dim] In particular, we provide proof that the topological dimension of Py can be large as oo; since any finite n-dimmensional Euclidean space has topological dimension n, this shows that Py is not a knite-dimensions. Euclidean space.
We outline the main steps of the derivation now:
First, from Condition and 4, we can show that both and 1 map prompts into a common lower-dimensional space before decoding into response distributions.
Then, by Condition 2 and 1, it can be shown that and 11 differ only by a Lipschitz continuous function mapping A AD.
Proposition (Topological dimension of Py is oc). Let K= =1 (1..... k} denote a set of k tokens. Let y be the set of all finite length token sequences with tokens from K., and Py the set of probability mass functions over y, then the topological dimension of Py = co. y is instead the set of token sequences with length then (Py] (I:)).
4.1. Factorising I| and क through V.
Notation. In this section, we make heavy use of the math- ematical concept of function composition; o denotes ff
5

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
composes y', and is function which first maps an input x through g. and then maps g(ø) through f to f(((=))
modules that can be reused to express n/. 2. It further establishes that for any satisfactory decomposition, there exists adapter म|, This suggests that in practice we can then learn an adapter.
By Condition 4, the proxy policy स factors through V: that is, it maps from the space of prompts to the space of re- sponse distributions via some intermediate representation of the prompt (i.e.. V) sufficient for determining the response distribution. Specifically, there is bi- bi-Lipschitz injective decoder o from V the image of the proxy policy (X)). Additionally, Condition says that the image of xt is in- cluded in the image of R.
first find a suitable triplet (0, Q )0).
4.3. Model Parametrisation and Learning
We now sketch our learning algorithm. Theorem 3 gives rise to a two-step procedure to learn the true policy n firstly we recover the functional components using a large proxy dataset Dj and then, secondly, D to learn the low-dimensional adapter.
small true dataset
Therefore, we can view I as a function composition of some decoder o: V - # and some encoder function X' + V, such that
Stage 1 Based on Theorem 3, we model the proxy policy I with parametric model composed of three functions: (i) Tg. an embedding function from the prompts X' to the D-simplex AD, (ii) θ E Dxxx a linear map from the simplex to a convex polytope V, and (iii) és. an injec- tive function from the latent space V to a distribution of completions Py. Therefore, our model is expressed as:
T X
S # (x²
(4)
Analogously, म can be viewed also
: v - (())
(5)
No = 60 o G7g.
(6)
Next, we show that rt can be expressed by inserting transformation into a function decomposition of न. This transformation can be shown to be a Lipschitz map between two known D-dimensional spaces. We can thus think of this transformation as an 'adapter' function.
Based on the DPO loss (Eq. 3), 0e. θ, and ig are learned using the empirical preference learning objective with the proxy dataset Dr::
La(R)) = - Ei log logo ( (Blog
fia m.)) Tra (Ba (.)
3 log
Kn (Mo. 22)
(Mt (2)
4.2. π and ग differ by a function between D-simplices.
In the large sample limit, the optimal parametrised model oe o θ* O' 70.* minimises the population proxy preference loss, and due to Theorem 3, we know that the optimal KI--
It is now possible to show that .t and सt differ only by a transformation on the representation space V. However, for the sample complexity arguments that follow, it is conve- nient to map V to D-simplex A then to show that t and स differ only by transformation on AD
regularised proxy policy मे = oz @r thus, justifying our parametrization.
To this end, since V is D-polytope with D ++ 1 vertices, every point in V can be expressed as a convex combination of the vertices. Then, it can be shown that and T' can be further factored through a D-simplex, AD. With this formalism in hand, we now state our result. The proof is provided in Appendix B.
Following this, we then model the true policy of using the same pre-trained components from our model of the proxy policy 7. with the addition of low-dimensional adapter function म. which maps a latent representation in the simplex A to another A D
Stage 2
as follows:
T = 3o o θ o 7/.
(8)
Theorem 3. We work under Conditions 2, 3, 4 and 1. For some D, there exists Lipschitz invertible function funcriibleuucctio Φ b::00 V ->
(X') satisfying Condition 4, Ô E [x++()+ and 70 :
The adapter #/ is learned by optimization of the empiri- cal preference learning objective with the true dataset D n. while keeping de. θ, and F3 fixed based their previously optimised values:
X' - A s.I. के = ② O7%
(7. 6,7) such that के To 07% there exists a Lipschitz continuous function #t A D A s.t. - 3o θ 7
Moreover, for any
Di (+t) En's lugo (Bog 611821126m0))00.. Varlyo (86) Blug
Theorem 3 has two important implications for learning. 1. It establishes that there exists decomposition of ã with
There may be more efficient algorithms which learn the
triplet c 6 fo by using the proxy and true data simul- taneously. Nonetheless, by splitting the learning into two
SStrictly, after a still need to go through an inclusion to land in Py, but to simplify notation we omit this technicality.
6

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
stages, the first using only proxy data, and the second using only true data, we make direct sample complexity comparison between learning s from scratch, and learning the adapter øt in Stage 2, in terms of the size of the true data D =²
implicit reward as:
a:) Tet (y x+)
T (x, log
(10)
Using Tx we can define a metric on the set of policies, and we express in the next lemma. The proof is Appendix C.
5. Convergence Rates Analysis
Lemma 4 (Metric on policies through rxy). For any policies T,, π X + Py, so that Σy < x)) Σy for any X, define the function
To illustrate the benefit of learning n² using the outlined algorithm, we analyse its soundness by showing the sample complexity improvement given that we have identified the true é, Ô and F from the proxy dataset in the first stage. This can be a reasonable approximation of the properties of the learning procedure in cases where the proxy dataset is much larger than the true dataset. To this end, we analyse the generalisation error bound for the second stage given access to true o, θ and 7 Following the approaches of Elesedy (2022), Mohri et al. (2012, Exercise 3,31), the generalisation error can be shown to be linear in the covering number of the hypothesis class. Our insight here is that the hypothesis class of T² is made smaller by having knowledge of é, Ô and 79, hence the covering number is also smaller. In order define covering numbers, first define notion of metric on all relevant spaces and the hypothesis classes we consider.
x '' x) =
(T, = 1|r T 11
(11)
Then, if the rewards are bounded, 1|r < || llo < co, it is metric in the space of policies.
and
Metric on the completion distribution space. Addition- ally, we define a metric on the space of distributions com- pletions, py. Motivated by the metric on policies through the rewards, we define the function dp,, : Py Py + R U foo}:
dpy = Blog P((n) ((.0)
(12)
20
Now define the hypothesis class of c as: Definition (Hypothesis class i')). Let 11 be a set of policies
5.1. Metries and Hypothesis Classes
f X + Py, so that, for all x, E, π [(y = and have reward at most C, meaning that || S C.
Metric on finite-dimensional spaces. For any subset of the Euclidean space, we use the p-norm-induced metrie; for simplex A we denote its metric by da and for any other finite dimensional space UI we use du-
From Lemma 4, IT and all its subsets metric spaces when endowed with d,. Later on, we will show that the cover- ing number of hypothesis class depends on the smallest Lipschitz constant of the class.
Metric on the prompt space. The prompt space X, is a discrete and unstructured space, so we define a metric, dx based on some fixed embedding function f. which maps a prompt to a vector space with finite but high dimensions: dx x') = dx(x) (f(r), f(x))) (z) fz'))lp-
Meanwhile, based on the exitance of o O,0, 79, we define a subset of TT:
Definition 2 (Hypothesis class fixing d, θ, 70 and Lipschitz- constant Lz). Fix Φ. θ, 79. Ler II ④ 0, Lz) S the
Intuitively, can think about f as some general-purpose embedding, such as one obtained by retrieving some in- termediate layer from a large model such as CLIP (Rad- ford et al., 2021). Importantly, this metric is only relevant when considering the complexity of the hypothesis class when we learn the target policy without proxy data, which one expects to be large; this intuition is confirmed since general-purposs embedding may not work well across all tasks, and can result in large Lipschitz constant for the target function.
set containing all x E it which can be written as
T (- = & θz o 7 (x)
(13)
for some I. -ipsciitt म, with respect to da
Finally, we define the loss functions of our setup Definition 3 (True and empirical DPO risks). Following Rafailov et al. (2023), we define the true risk as
[log (3log Rei (m) = EEGI
x(Yal)) (.,(Y..
x 3 log
Tay Y(IX)
(14)
where Gt= (r+, Fifff Px) is the true data generating process.
Metric on a policy space. Defining metric on a space of policies is more involved, and we begin by relating a policy and the reward function under which it is the KL-regularised optimal policy. Given a policy и X - Py, define the
The empirical risk is the Monte Carlo estimate of Re (TT),
Rept_, (T) = + Σe [Log g log s(geslas) (e.
99 log mer [R)
m slre)
(15)
7

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
5.2. Main Results
Experiments. While this work focuses on theory and ver- ifies the claims through mathematical proofs, we provide in Appendix D small-scale experiment on over-smoothing in reward learning, as well as an empirical validation of Theorem 5 and Theorem 6.
Now we are ready to state our main sample complexity result. The proof is given in Appendix C.I.
Theorem 5 (Sample complexity of learning with proxy). The covering number of the class of adapted policies IT is bounded by a function of the latent space's 's dimension D:
6. Related Work
Cov (n(2) m, Lxx) dr, 3x +
Reward hacking theory. Initial work on the theory of re- ward hacking considered the setting where the proxy reward was function of a subset of true reward features (Zhuang & Hadfield-Menell, 2020). This work demonstrates that optimising the proxy can lead to arbitrarily low true reward. Similarly, Tien et al. (2022) give theoretical results for re- ward hacking when learned reward uses nuisance variables that correlate with true causal variables. These ideas were extended to arbitrary MDPs by (Skalse et al., 2022) who define a proxy reward as hackable if it prefers policy over when the true reward has the opposite preference. Recent work has sought to develop scaling laws for reward hacking that describe how the true reward changes as the proxy re- ward is optimised (Gao et al., 2023). Rafailov et al. (2024) show similar over-optimisation patterns in DPO at higher KI -i-diiereence budgets, even without an explicit reward model. In contrast to these works, our theoretical results suggest a new model parametrisation and training scheme which achieves improved sample complexity for learning the true policy; hence, our results are constructive.
D 2
20 | p DVD D
(16)
K
where is is a free parameter. Iewe set
48. then we need
n(e,w) ( ( D.
log
(8LL)1111.VD logw w
samples to generalise. That is, whenever ni 2 :n(e.w)
P sup (1,6,
(G) Rop,,t nt (T)] S w
(17)
So, with probability at most w. the worse gap between the true and empirical risks is at least e.
For comparison, we also state the sample complexity result for learning without adapting a proxy policy. The proof is in Appendix C.2.
Theorem 6 (Sample complexity of learning without proxy). Let D' be the dimension of a given embedding function f of X, and let il (ool@11>Lar) be the subset of il where w is 1oll@11p Lipschitz. We need
Addressing reward hacking in LLMs. One of the classic examples of reward hacking in LLMs is their propensity for verbose responses that are not more helpful, often called the 'length bias', or 'length hacking' of LLMs (Singhal et al., 2023). To address this, Singhal et al. (2023) modified vari- ous aspects of PPO (increasing KL regularisation, omitting outputs beyond certain length, and reward scaling), as well as the training data, with mixed success. Chen et al. (2024) conducted a large-scale evaluation of the impact of hyper- parameters and the above modifications on reward hacking. They further introduce a model that decorrelates preference predictions with length. Miao et al. (2024) formulate reward modelling as optimising a variational information bottle- neck and then use this to filter out less important features in latent space. Huang et al. (2024) mitigates reward over- optimisation by replacing the KL. regularisation with an alternative term which implicitly implements the principle of pessimism in the face of uncertainty. Yang et al. (2024) addresses form of reward misalignment due to distribution shift of the prompts and responses seen in training versus test time. To the best of our knowledge, reward hacking due to a difference in the reward functions in training and test time is not discussed explicitly in existing work. More im- portantly, the impossibility of target policy recovery without some data from the target reward, is not yet acknowledged.
m(c,)) ( ( (1 D'
log 181,101, (p WTF
logw
samples to generalise, where D' > D, and E' (p, D') >
That is, whenever n' 2 n() we have
P
sup
|Re (T) Rot,,, (T) 2 88
T (
(18)
So, with probability at most w, the worse gap between the true and empirical risks is at least 6.
Discussion. Theorem 6 says that if we learn n' directly from expensive samples of Gf, then the sample complex- ity scales with D', which is the dimension of the embed- ding space; ; this can be extremely large. However, if we parametrise I using क. Ô, 7 which compose to be म,, and can be learned from cheap samples of G. then Theorem 5 asserts that the number of expensive samples we need from G scale with the latent space dimension D which can be much smaller than the embedding dimension D'.
8

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
RLHF with expert feedback. Human feedback often varies in quality, and one key challenge is how incorpo- rate these different feedbacks into learning (Daniels-Kode Koch & Freedman, 2022). Freedman et al. (2023) formulate se- lecting which human to query for feedback as a bandit prob- lem. Yamagata et al. (2024) uses the settzmannn-aationa model to account for varying levels of expertise. Our model parametrisation leverages certain invariances between proxy and expert/true feedback, allowing identification of the true policy as low-dimensional adaptation of the proxy policy.
knowledge of the shared component functions; in particular, it is seen that under knowledge of the shared component functions the sample complexity bound is much lower than without such knowledge. In future work we aim to further investigate these findings empirically, as well as investigate relaxations of the conditions above.
ACKNOWLEDGGENTS
YZ acknowledges support by the Engineering and Phys- ical Sciences Research Council with grant number EP/S021566/1.
Domain adaptation in the wider transfer learning and domain adaptation literature. Reward hacking describes the general problem of adapting to a new domain from what's represented by training data, and appears in many sub-fields of transfer learning and domain adaptation. For instance, poisoning attacks in RL often consider data dis- tributions polluted by an adversary, meaning that the data distribution represented by adversary is chosen in order to minimise rewards obtained by the targeted agent (Pinto et al., 2017), but this differs from our setup since we do not consider the adversarial aspect. Close to us is a class of subspace methods, where a common subspace between target and training environments is learned (Gopalan et al., 2011; Gong et al., 2012; Fernando et al., 2013), but this line of works do not analyse sample complexity of the target environment, and can be computationally expensive. A line of research directly considering how regrets scale with the number of samples seen considers multi-fidelity bandits. Analysis in this case assumes that the absolute difference in rewards between the low and high fidelity bandits is bounded by a known quantity (Kandasamy et al., 2016), whereas in our work the difference between the proxy and true rewards need not be bounded at all, let alone by known quantity.
Impact Statement
Preference learning lies at the core of RLHE, Additionally, due to the costliness of high-quality data collection, proxy data is frequently used in practice. In this setting, our work clarifies conditions and suggests model parameterisation for guaranteed nigh-quality-sampl complexity improve- ment, and therefore can be used to guide the model archi- tecture design and data collection procedure for finetuning large generative models particularly for usage in specialised domains such as healthcare, where collecting high-quality samples is difficult.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L.,, Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint urXiv:2303.08774 2023.
Amin, K. S., Davis, M. A., Doshi, R., Haims, A. H., Khosla, P., and Forman, H. P. Accuracy of chatgpt, google bard, and microsoft bing for simplifying radiology reports. Ra- diology, 303(2),, 2023.
7. Conclusion
Bird, J. and Layzell. P. The evolved radio and its implica- tions for modelling the evolution of novel sensors. In Proceedings of the 2002 Congress on Evolutionary Com- putation. CEC*02 (Cat. No. 02TH8600), volume 2, pp- 1836-1841. IEEE, 2002.
We study the problem of reward hacking due to distribution shifts. Specifically, an abundance of preference rankings is generated by a proxy reward function, different from the true reward function, which is costly query. We thus consider the setting where we have a large proxy dataset and small true dataset; to the best of our knowledge, we are the first to consider this setting. We formulate conditions motivated by a real-world example, under which we prove that the optimal proxy policy can be decomposed into component functions shared with the optimal true policy, and that the true policy only one tow-dimensional adapter function away from the proxy policy given the shared component functions. We then observe that in the large sample limit of proxy data, one set of such component functions can be identified from minimising the preference loss. Leveraging this, we provide a characterisation of the sample complexity bound for learning the hypothesis class both with and without
Bradley, R. A. and Terry, M. E. Rank analysis of incom- plete block designs: I. the method of paired comparisons. Biometrika, 1952.
Casper, S., Davies, X., Shi, C., Gilbert, T. K., Scheurer, J.,
Rando, J., Freedman, R., Korbak, T., Lindner, D., Freire, P., Wang, T. T., Marks, S., Segerie, C.-R., Carroll, M., Peng, A., Christoffersen, P., Damani, M., Slocum, S., Anwar, U. Siththaranjan, A., Nadeau, M., Michaud, E. J., Pfau, J., Krasheninnikov, D.,, Chen, X., Langosco, L., Hase, P., Biyik, E., Dragan, A., Krueger, D., Sadigh, D., and Hadfield- D. Open problems and fundamental

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
limitations of reinforcement learning from human feed- back. Transactions on Machine Learning Research, 2023. Survey Certification.
Gong, B., Shi, Y., Sha, F., and Grauman, K. Geodesic flow kernel for unsupervised domain adaptation. In 2012 IEFE Conference on Computer Vision and Pattern Recognition, 2012.
Chakraborty, S., Qiu, J., Yuan, H., Koppel, A., Huang, F,, Manocha, D., Bedi, A. S., and Wang, M. Maxmin- rlhf: Towards equitable alignment large language models with diverse human preferences. arXiv preprint arXiv:2402. 08925, 2024.
Gopalan, R., Li, R., and Chellappa, R. Domain adapta- tion for object recognition: An unsupervised approach. 2011 International Conference on Computer Vision, 2011.
Huang. A., Zhan, W., Xie, T., Lee, J. D., Sun, W., Krishna- murthy, A., and Foster, D. J. Correcting the mythos of kl-regularization: Direct alignment without overoptimiza- tion via chi- -quarre preference optimization, 2024. URL https: aaaaaaaxvvv.......aaaaaaaaa....a wtt.://gggb...........
Chen, L., Zhu, C., Chen, J., Soselia, D., Zhou, T., Goldstein, T., Huang, H., Shoeybi, M., and Catanzaro, B. ODIN: Disentangled reward mitigates hacking in RLHF. In forty-first International Conference on Machine Learn- ing, 2024.
Ji, J., Qiu, T., Chen, B., Zhang, B., Lou, H., Wang, K., Duan, Y., He, Z., Zhou, J., Zhang, Z., et al. Ai alignment: comprehensive survey. arXiv preprint arXiv:2310.1990 2023.
Chi. H., Liu, F., Yang, W., Lan, L., Liu, T., Han, B., Niu, G., Zhou, M., and Sugiyama, M. Meta discovery: Learning to discover novel classes given very limited data. In International Conference on Learning Representations, 2022. URL /
Kandasamy, K., Dasarathy, G., Poczos, B., and Schnei- der, J. The multi-fidelity multi-armed bandit. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016. URL httpss:/prooceedingg... neurips.. cc cc//ppper_filleespppe/////////// (la1646scaa022031222441144444 pdf.
id=MEpKGLSY8E.
Clark, and Amodei, Faulty reward functions in the wild, 2016. URL htttp:://ppnaa www.eoo////oo//.. index/ sraltyy-reward-funtiiooo
Coste, T., Anwar, U., Kirk, R., and Krueger, D. Reward model ensembles help mitigate overoptimization. In The Twelfth International Conference on Learning Represen- tations, 2024. URL https:/ http///pppneeeeee/eeeeeeeesmeeee Forum?id=dd dide--dddddd-eet-. jtMykXXx.
Paper.
Knox, W. B., Allievi, A., Banzhaf, H., Schmitt, F., and
Stone, P. Reward (mis) design for autonomous driving. Artificial Intelligence, 316: 103829, 2023.
Daniels-Koch, O. and Freedman, R. The expertise prob- lem: Learning from specialized feedback. arXiv preprint arXiv:2211.065/9 2022.
Miao, Y., Zhang, S., Ding, L.,, Bao, R., Zhang, L.., and Tao, D. Mitigating reward hacking via infommation-theoeee reward modeling. arXiv preprint arXiv:2402.093455 2024.
Elesedy, B. Group symmetry in pac learning. In ICLR 2022 workshop on geometrical and topological representation learning, 2022.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Foun- dations of Machine Learning. Adaptive Computation and Machine Learning series. MIT Press, 2012. ISBN
Fernando, B., Habrard, A., Sebban, M., and Tuytelaars, T. Unsupervised visual domain adaptation using subspace alignment. In 2013 IEEE International Conference Computer Vision, 2013.
9780262018258. URL https: /books...ss////////oo.......kk.. google. co.uk/ No.ukbbor www/bboooo bbok/book (ttpkkss2ddmaaaaaaagggg...
Nair, A., McGrew, B., Andrychowicz, M., Zaremba, W.,
and Abbeel, P. Overcoming exploration in reinforcement learning with demonstrations. 2018 IEEE international conference on robotics and automation (ICRA), pp. 6292- 6299. IEEE, 2018.
Freedman, R., Svegliato, J., Wray, K., and Russell, S. Active teacher selection for reinforcement learning from human feedback. arXiv preprint 1xXiv2230..55 15288, 2023.
Gao, L., Schulman, J., and Hilton, J. Scaling laws for reward model overoptimization. In Proceedings of the 40th International Conference on Machine Learning, pp. 10835-10866. PMLR, 2023.
Pan, A., Bhatia, K., and Steinhardt, J. The effects of reward misspecification: Mapping and mitigating misaligned models. arXiv preprint arXiv: 2201:5201,.3544,, 2022.
Paulus, R., Xiong, C., and Socher, R. A deep reinforced model for abstractive summarization. In International Conference on Learning Representations, 2018.
Golden, D. Glass floor colleges reject top applicants, ac- cepting only the students likely to enroll, 2001.
10

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. Ro- bust adversarial reinforcement learning. In Proceedings of the 34th International Conference on Machine Learn- ing, 2017.
Yamagata, T., Oberkofler, T., Kaufmann, T., Bengs, V., Hüllermeier, E.,, and Santos-Rodriguez, R. Relatively rational: Learning utilities and rationalities jointy from pairwise preferences. In ICML 2024 Workshop on Models of Human Feedback for Al Alignment, 2024.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., and Sutskever, Learning transferable visual models from natural language supervision. CoRR, abs/2103.00022 2021. URL https: https: /ttp:////axxvvv///e/ abs/2103.0002
Yang, A. X., Robeyns, M., Coste, T., Shi, Z.,, Wang, J., Bou- Ammar, H., and Aitchison, L. Bayesian reward models for Ilm alignment, 2024. htthttps: http:s///aaavvvrraaeeeeee abs/ 24022 13210.
Yu, T., Yao, Y., Zhang, H., He, T., Han, Y., Cui, G., Hu, J., Liu, Z., Zheng, H.-T., Sun, M., et al. Rlhf-v: To- wards trustworthy milms via behavior alignment from fine-grained correctional human feedback. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13807-13816, 2024.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. Direct preference optimization: Your language model is secretly reward model. In Thirty- seventh Conference on Neural Information Processing Systems, 2023. URL httph::t///c htt.tt/s:/oppeeeeeiii http///ppeeeeeeee///e/eeee net/ us USHPPPSI.
Zhou, L.,, Schellaert, W., Martinez-Plumed, F., Moros- Daval, Y., Ferri, C., and Hernández-Orallo, J. Larger and more instructable language models become less re- liable. Nature, 634(8032), Sep 2024. ISSN 1476-4687. doi: 10. 10010388/441586-024---90333 doi ori.org//i 10. 1 1038 848888/41186--11 020- 07930-730000
Rafailov, R., Chittepu, Y., Park, R., Sikchi, H., Hejna, J., Knox, B., Finn, C., and Nickum, S. Scaling laws for reward model overoptimization in direct alignment algo- rithms. arXiv preprint arXiv:2406.02900 2024. URL https: /tts://arvv..../ aaaiviiii. wwwxiiv.ogg/aae htg/abs////// //////////22....// 2406. 02900.
URL http: : dxx
Rajeswaran, A., Kumar, V., Gupta, A., Vezzani, G., Schul- man, J., Todorov, E., and Levine, Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. arXiv preprint 2017.
Zhu, B., Jordan, M. I., and Jiao, J. Iterative data smoothing: Mitigating reward overfitting and overoptimization in rlhf. arXiv preprint arXiv:2401. 16335, 2024.
Zhuang, S. and Modfield-Menelle D. Consequences of mis-
aligned ai. Advances in Neural Information Processing Systems, 13:15763-15773 2020.
Rita, M., Strub, F., Chaabouni, R., Michel, P., Dupoux, E., and Pietquin, O. Countering reward over-optimization in Ilm with demonstration-guidde reinforcement learning. arXiv preprint arXiv:2404. /9409, 2024.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06:33 2017.
Shen, W. Zheng, R., Zhan, W., Zhao, J., Dou, S., Gui, T., Zhang, Q., and Huang, X. Loose lips sink ships: Mitigating length bias in reinforcement learning from human feedback. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
Singhal, P., Goyal, T., Xu, J., and Durrett, G. A long way to go: Investigating length correlations rlhf. arXiv preprint arXiv:2310.03716, 2023.
Skalse, J., Howe, N., Krasheninnikov, D., and Krueger, D.
Defining and characterizing reward gaming. Advances in Neural Information Processing Systems, 35:9460-9471, 2022.
Tien, J., He, J. Z.-Y., Erickson, Z., Dragan, A. D., and Brown, D. S. Causal confusion and reward misidentifica- tion in preference- based reward learning, arXiv preprint arXiv:2204.00 006600, 2022.

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
A. Proof of Proposition 2
Proposition Let K = (1.... :k} denote a set of k tokens. Let y be the set of all finite length token sequences whose tokens all come from K. Then y has a one-to-one identification with the natural numbers. Let Py be the set of probability mass functions over y, then the topological dimension dim(Py) cc. y is instead the set of token sequences with length S I, then dim(Py) ((k).
Proof of Proposition 2. We can identify Y' with the natural numbers follows. Let I denote the length of token sequence. Since for each token in the sequence there are k options, there are ke' distinct sequences of length I.
We can define a bijective mapping from the set of k. sequences to the subset of natural numbers S = {(E+)
(Ei= kt) -1] for I 2 2 and S == (0, , 13. This is possible since the number of ele-
ments in S is (2 k*) -1 (2 k²) + k., Denote one such mapping fi. Then define f y - N:
f(y) = f((y) if length of y=
(19)
is well-defined because every has a unique length 1. f is invertible because fi is invertible for every I and St ns = 0 and Ui=1 5'= N.
Thus, Py is the set of probability mass functions whose sample space is = N. That is, an element Py E Py is an infinite positive sequence which sums to
Let A be the d-dimensional simplex. Note that Py U A4, where A is viewed as a subset of A d+11 via the inclusion (Pi,... P + (pI.-.. .P441,0,
A > A
For each d, the topological dimension of the d-simplex A is d 6 this is to say, d is the smallest number such that every open cover of A has an open refinement of order d+I 1. Therefore, the smallest number n such that every open cover of Ub Ad has an open refinement of order n + 1 is D. Hence, there is no finite N such that the any open cover of Py == 20 A has an open refinement with order N + 1. Therefore the topological dimension of Py is co.
When the maximum sequence length is / the cardinality of Y is finite and equal to E ks - k(I-k()
Py thus contains
the set of positive sequences of length k(1-x') which sum to 1, so Py is a 1-k 1-k
1-dimensional simplex, and therefore
the topologiaal dimension of Py is k(1-k') = -k-)(k).
1-K
B. Proof of Theorem 3
Lemma Under Condition 2, nt o -- la(x) is a well-defined function.
Proof.
Inverse of non-injective functions. In general, unless function is injective its inverse is not a function, but only set map. For instance, since is many-to-one, so not injective, # would take an element from Py and return a subset of X, rather than a single element. Let मे - "lxxx) denote the inverse of restricted to its image (X)).
rt # (1x()) is a well-defined function. It follows that 1 o - |F(x)) takes a point Py in the image of म, # (X'), map it to its preimage # (Py),, and map all points in the preimage # (Pyr through n/ to n ( (Pr)). For any two points #1, x2 E 7 -Py),
), we have ( = # and then Condition 2 implies n (œ = ग (xz). Therefore, for any Py E Py, T ( (H is a set containing exactly one element, so न. मे - ([(2)) is a well-defined function.
Theorem 3 We work under Assumptions 2, 3, 4 and 1. For some D. there exists a Lipschitz invertible functionn T: 5 (()). Ô E (D++1) and 70 X - A
S.I. f = Φ 077, and there is a Lipschitz continuous function मो
AD - A s.t.
- = = o.
'Theorem 5, https:/ppessoall.ollyy cowby.edu/ sat.ycaressiigg///////////gggaan
Injective essentially means one-to-one. Formally, a function f is injective f(x) # f(x2) whenever a # #22
12

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
Proof of Proposition 3. Step 1. Show that there exists Ô, 7 and Lipschitz क such that = δ 67%
By Condition 4, there is some invertible Læ-Lipschitz function Ø V (2²), where V is some convex polygon. Therefore, there is finite set VD+1 = (va) such that every e E V can be expressed as v Edd Pata for some p E A Let E R (x(++1 be the matrix such that its d-th column, i.,d, is equal to Da. Then every E V can be written as v = Op for some E A..
Since 3-
a function V. then for every x, Φ- o (2:) V. Therefore, there exists some pa E A D such that
o ((:) = Op.
(20)
Let :0: :X - A be s.t.
(1))) Pr
(21)
then
(x)) 67 (x) *(x) = 5 67
(22)
(23)
Step 2. Let (xx) = (x). We show that under the shared-level-sets assumption, æt (F(2)) is well-defined. have the following equalities:
We
# (a(x) = (0or) -1
1x(2)
(24)
7 11 1
(25)
# [x(x) o 7-111 lv
(26)
- ((--(
(27)
(28)
Therefore,
# l o = = # o lxx) o n- (((x)
(29)
(30)
(31)
By Condition 2 and Lemma mf o (=(x) is well-defined. Since ml न (e(x)) is well-defined, so is क8 o o
Step 3. Show that under Assumptions 3, 4 and 1, n can be decomposed o tb 7 for some Lipschitz function v: F(x) + o- (x)). Note that 1. is invertible restricted its image, 2. by Condition 3 and 4 Ø is defined on the image of nt, and 3. nt a ==)le( is well-defined. Therefore, we can factor πf as
मं -o o F |F(x) oF
(32)
Therefore, define:
: ((X) + - - C F(X)
(33)
v = o 1x(x) = - मे |xx) o
(34)
(35)
a composition of Lipschitz functions (by Assumptions 4 and 1) so is Lipschitz.
13

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
Step 4. Finally show the assertion, that 1 o O 70 for some Lipschitz # :A AP.
Substituting in
+(x)= 67% (x), obtain:
x (z) = ã o (x)
(36)
Let Ps = (x) E A.. We want to show that there a Lipschitz continuous function #ो A D A such that
((p..) = Ō 1
(37)
For a given Pas we can try to solve the linear system in terms of (p). We know that it must be an element of the set:
@Px) + Ker(O),
(38)
where Ô denotes the pseudoinverse.
Take the intersection between this set and A ;; the intersection is non-emply because vb lands in V. Now we describe a procedure to choose a point in this intersection that is Lipschitz continuous wrt px: we let ø map Pa to the centroid the intersection between A D and @+p.)..) - Ker(O). The intersection one two convex sets, so it is convex; so the centroid lie in this set.
We now proceed show that #ं is Lipschitz continuous, in two steps. 1. First we show that the centroid of the intersection smooth function of the location of its vertices. 2. Then we show that the location of the vertices is a piecewise smooth function of p...
We show the centroid of the intersection is generically smooth function of the location of its vertices. Note that the intersection of A and @up (Op.)) Ker( ()) is convex high-dimensional polyhedron, denote it S(px).
The centroid of a convex high-ding sigh-dimensional polyhedron can be computed as follows: every convex polyhedron admits a triangulation. Let the triangulation of S(p,), denote it by (PS()))). For the ith simplex in T(S(p=)). take its vertices (ui,, Zin) where n is the dimension of the polyhedron. The centroid of the simplex given by C(i) = vio too and n+1
(
the volume Vol(i) is given by 1
Un 1
The centroid of S(px), denoted C(S(p:)) is given by Σ, C(1) Vol(
since the determinant function a polynomial in the matrix entries, this is a vector field where each entry a polynomial. Moreover, every vertex in the triangulation but not on S(zz) such that we can draw an e-ball around each such vertex such that the closure of the balls are all disjoint and still lie in the polyhedron. So, perturb move each vertex point the boundary of its ball; this gives new triangulation, but the centroid is not changed. Since we can do it for any e' S e, C(S(p.)) is constant in the interior vertices. Therefore, C(S(p.)) is a polynomial of its vertices.
the interior of S(p.). There is some small enough
The limiting case is when two vertices overlap; in this case, at least one element in the triangulation will collapse onto a face, which has volume zero, so its centroid will not contribute to the calculation C(S(p.)) through the formula. Therefore, the centroid of a polyhedron is polynomial of its vertices, including when two or more vertices overlap.
We show that the location of the vertices is piecewise-smooth function of pa- Note that the set of points in S(p..) is described as follows: Suppose dim(S(p)) = J < D, and choose an orthonormal basis in RD+ whose span contains the direction vectors in Sp))
b,. b,
(39)
Extend this to an orthonormal basis whose span contains A:
b b by,b,41," bp
(40)
And finally extend this to R P:
bi...., by, b..1, bbbb....,,,,,b
(41)
14

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
So can express
81 4 0. D. = ====1_==-(((t(00))
S(xx) E
(42)
where (ID+1 - B) B is the matrix whose rows are the D basis vectors, and B, is the one taking its first rows.
Note that DD1 B, = B_ where B- is the matrix containing b b. .bp-1 rows. But 1 is orthogonal to the row space of j so it is contained in the row space of B and hence B Therefore, we can remove Σ, & = from the set of conditions.
Therefore, the set of conditions contains D ++1
linearly independent conditions and D inequalities.
An extrema, i.e. a vertex, is the solution of D + linearly independent equations where all D + - linearly independent equality constraints are included, together with J equations from saturating the inequality constraints. Since ID+1 - Bj has rank + J, there is subset of + 1 - J rows, call the new matrix constructed from these rows BD+1-J. Select vectors from the standard basis which are linearly independent of the rows of BD+1-J, and stack them into an invertible matrix C. Then any vertex is solution of one such equation
( (BDILO (op:))
v" ='=c-1 -'=
(43)
0
provided it still satisfies the remaining inequality constraints. Here it is clear that any o" varies smoothly with Pa. When all vertices S(px) are the interior of a 1-dimensional face of A they vary locally smoothly with p.. Since the centroid of S(x)) varies smoothly with its vertices, whenever its vertices vary smoothly with pa, the centroid also vary locally smoothly with pz. The only di-iifferentiability happens when one vertex moves out of A and another moves in. But around those points of Ps, the centroid is still continuous wrt pz. म is piecewise differentiable function compact domain, and therefore is Lipschitz continuous.
C. Convergence rates proofs
Lemma 4. (Metric policies through rx) Define rn (x, 3) 3 log
x [+) Forly [w) for some fixed constant B >> 0, and let
d, x') ||r= Trr lloo
(44)
Then de (.,)) defines metric over any set II of functions X' x y + [0.1] (..1ss. S.T. Vx Ey x x)) = 1, and satisfies (x 8) < C over X' and y.
Proof of Lemma 4. d, is well-defined on II since for any ग, n² E II. (T) < In + || 10:0 2C < oo.
We can verify that d a metric on II. Clearly, symmetry and positivity holds, and d( X') = + π = n', so we just need to check triangle inequality. Fix n" E II,
dx( + d (T', n²)
I|Ia Tx" 1lo0 + || - 1oo
(45)
2 !|r Fx" -xx rx"r
(46)
|| Tx
(47)
dx(
(48)
Proposition 7
7C (Concentration bound). Let G be a measure on (X, Y... Yi) and for any E II f (Def. let
(Yanl X)
π XVi
Ro(T) = E6 logo
Boog
3 log
(49)
(u]l) (X) Tre Toe (YI)))
15

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
be the preference loss. Further, let (X w. Y1,)==1 be i..dd samples from G, and let G, denote the empirical measure given by the samples, then
O6 ) P sup RG(T) - RG, (T)) 26) S inf Cov II, dT,)), Tell
20 20-a)Bae
402
(50)
aE(0,1)
4
where d, xT) = 1|r loo
Proof of Proposition 7. Adapted from Elesedy (2022).
Fix n, n' E TT.
(X)
B log x
[Rc(T) Rc(T))] = LEc log B Blog
Tear Y [x)X)
Teael (Y) IX)
x x'(Yu|X)
a' ((Vi)
logo Bloo
3 log
(51)
Tietl TTe((Nnr (x))x)
Tee((Vi
x (X)
*(Yi(x)
$ Eg
logo
B Blog
B log
rear( X Xw|X)
Toael (Y) ())
n/ x((])X)
llogo
Blog
3 log
(52)
Tref Teer(Y (X
Teel (Yil()))
When is the sigmoid, log is concave, so the above is upper bounded:
(Vvul (X)
S Eg
3 log
$ log
Teer(Y (Y XX)
Teal Terr (YilX)
n/ (Yvxox)) B log
Blog
(53)
Neetl (X
Fier( (
< Eg (( 3 9l0g
(YV X))
TYY
8 log
Tiee( (w (X)
(Yol(Y
Blog 17 (Vilx) 3 log
n' xV(()
(54)
Need (Y|X)
Eol((r (X,Yw) - Tx (X, Yw)) - (x, Yi) - rx, (X)
(55)
Eall(r=(X) Yvo) - Tw (X, Y=) + Ball(ra Y) - - (X,
(56)
S rT - 1lo
(57)
Now let Gr be the empirical measure of (X, Y.s Yi) with samples. And define
LG. (T) = -RR, (T) - Ro(T)
(58)
Then
La. (T) Lo, (z))
RG, (σ) Ro(x)) Ro, (I') + RG(
(59)
R&. (अ)) RRg (7') + Ro(x') R
(60)
R& (x)) Rái (7') + (RG(T') RG((T)
(61)
4 - 1oo
(62)
So now let K. be a w-cover of IT in d.())). Define the sets D(TT)) {IT E TI d,(TE, 1)) S Sx). Then
16

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
P sup nell
LG (T) 26) 26)= =
U
sup FED(SE)
La.. (T) 2 E
(63)
TEE
P
sup TED(TT)
L (T) 26
(64)
EK
Set 4 for 0 < < 1. Using the above, for any ((TT)) we have
T.G. (x) -oo, (TT)
4|rra Fxellx
(65)
4d, (Tk, T)
(66)
4k
(67)
By triangle inequality:
La. (m)) - LG (Tx) $ Le, (T) Lon (Tk)
(68)
So
G. (1) S 4n + T. (T&) G. (7)) S ar + [ (TT)
(69)
Since the probability of the supremum of over cover is greater than implies that the upper bound over the cover is greater than 6, we have that the probability of the latter is at least the probability of the former:
P sup =enl
LG. (T)
20){
20)
Σ P
sup (ED(NE)
Lo. (T)) (m)
26
(70)
<
Σ P CrE + Lec (TTK) (TT))6)
(71)
#EEK
Σ
P([ (Te)) 2 2 (1) a))
(72)
KLEK
(73)
Then Hoeffding's inequality gives
sup LG, (T) 2() S Feel
20)s
> Σ p([T (TH) (TT) 2 c - a))
(74)
E
2(1 - n12
< 2// exp
(75)
120
Proposition 8 (Covering number in terms of that of domain and range). Fix T. θ, 40 and Lop For E (X') 12),4 let
11p {9l() ((0F())) [-]
F 0, LB) PPy
(76)
17

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
and recall the metric py:
(py(p,9) 9) = blog p(,))
(77)
g(
Then for K. 8 > O, denoting as 2g the ò-cover of A under metric daD:
C 0, Lix) dr,3k 3x 3Lg (1 || pb)
(78)
S sup Cov(Ilp) dpy, 12) corlls d2.5) p'Eag
(79)
Proof of Proposition 8. We wish to find the covering number of with the metric dy.
Take covers of the domain and range of n. Take 8-cover of (2)) with metric da, denote it Af. For every p' E Ag. take k-cover of Up with metric dpy. Denote it by II pp....
Construct a of maps from the domain of the range of n, via the covers. Let hap be a map from A s.t. for
every p', hag(p') E lp.... For every such hag. extend it to h, function whose domain is A as follows: for p E AP. let:
hap (p), hap (p') where p' is selected randomly from A(p).
if A if g A
h(p))
(80)
(D. ) D'Eap
A(p)
min p' E A8 ds"(p.p')
(81)
Construct set of maps X' x x [0, 1], denoted by Hss. This set will be proved to cover II. For every h, define h: X x y + 10, 1]:
h(x, v)
(82)
Let Na denote all such h. It can be checked that Ho.r II:
1. M(F(())) E Uy for some p' so is in py; therefore, E, (xF =
2. Since p' E (2)), take x' so that p' = Fxx". Then wlog for every there is some p' and x' such that,
[(F(()))[)) ((p))
(83)
hap (p') lvl
(84)
=ō (m(p'))
(85)
3o θZ (z))))))
(86)
where the third equality holds since hap (p)) Hp- Therefore for every s', |3 Blog (res(y(2)
(xi"(l)))y)) S C.
3. Now let us show that for some Th. h oo θT,, 7 e ii. For every p E (X), h(p) e II for some p', i.c. there is some T. s.t. h(p) = ò (GT()')) Construct 7 (p) = (p')..
We need to show that Hoss covers II with metric d,. To this end we need to show that for every æ E II, there is a ha E H5 such that d, (IT, hz) c(5, x) for some small value which depends monotonically on 5 and K, and <(0, 0)
18

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
So consider (T, 1o) for some и E II and h Ha,x:
d, (TT, It) || Talloc
(87)
sup xEX,
(r, -r (x(
(88)
sup =EX.EE
3 log Tre
(x, Blog h
(2r (2)
(89)
Jeet
sup sup (yE)
B log
π (x, v) - blog Jree
(I,
(90)
=ex
Jeef
sup sup 313 log x (I, Blog bor xEx yyE)
(91)
So it is sufficient to show that for every there is some h, such that for every
sup
[13 log π (ar, y) 3 log h y) vy) - 8 log h (x, x)l
(92)
vEy
=
(93)
$ ( k)
(94)
Decompose the distance between a general and Ha, for a fixed x. This helps us later choose the h which makes the bound small enough. Let π E II, h Ha, x E X and x' E X s.t. p' = (0 (())
|| To, v) - Blog h(z, "y)
(95)
< || log n ((x, :n) - 3 log T(' :w)loo
(96)
+ || log n('',"> yn) - Blog voooo
(97)
+ 1og h(x'.-) - -llog (x)..))l
(98)
Consider |18log (1, w) B log wl) Let x' E (p') be s.t.
We can show this term is bounded by L8.
|| log n (I,, v) 3 log a
(99)
3 log [(.,;) ;y)
(100)
7(,, yy) 00
s dpy (T(2, w) ( )))
(101)
(F) (+))))
(102)
$ T6
(103)
Consider ||3 1,8logr(s (2', -v) 3 log h(r', bgg; we show that can choose fg to make this be upper bounded by k.
Since π E IT, it can be written as ((..; y) = o θ o 7 (<x)) for some मे A + AD
Note that [Ta,, -y) Naaar And since 70 (a') Ap, there some he E ( s.t. dry (T (+((22)) s k.
But expanding this,
x 2 dpy (T(2', ar(l''''),, (x(((())))
(104)
a(I',,g)
B log (+((f(x'))(
(105)
= || logoo( a :) hr o 7 (2
(106)
So choose hy := h 70. From now on replace by hz-
19

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
Consider ||3 log hy (x', ()) - 3 log (x, (x)s::)))l We show that this is bounded above by 2x 2L8. Let p/,p4
(x)), then let of E (p,).
3 log ( (v) - log Ne (1/2 v)
- ||3 log h vv) y)- log x (| v)ll + | (o'' .v) - 3 log Txz2 v)) + 1,3 ( w) - 3 log he (122 3y0 S * || log (<), 3 log r (2 ol +
(107)
(108)
2x + 8 log <(pl.'))
(109)
s 2x + 1111 (f)))) 7 (x2))
(x1)
(110)
$ 2x Lg 1011 (f (z1), 4 (x)) (f (22))
(111)
2x + 2/ | 1
(112)
(f) & A. Mxx (x)) = (p") h(x") with some p" E A()) and 7 (9 = p", therefore
||3 log (x', .n) log he (x, wl log n (x', (n) The (x", 1l)l
(113)
- 2x + 2 | p
(114)
Therefore,
[x, w) 3 log h (2, 'v)ll 33x +3 (1
(115)
Since the upper bound is constant in x, we can conclude that (T, hx)) S 3x 3LD /| 11 So Hs, covers II in d, with radius 3k 3 ||@11p ō. Therefore, we have that
Cov [I, dr, +3boll11nbba
[H6
(116)
[p
(117)
P'EA?
cor(Ap cor(AP.d2o.5) d2o.5)
S sup Cov CIp dpy, 13) P'EAP
(118)
C.1. Proof of Theorem 5
Theorem 5(Bounding sample complexity in terms of dimension) We remain in the set up of Proposition 8, The covering number of is bounded above by a function of D:
Cov II, dr, 3k + 30.1|
D( (2
2Tt 2T.e111lpVDD
(119)
Set K
18. we need
D
D @6 VD
n(c,w) Ω
log
log w
(120)
c
c
20

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
samples to generalise. That is, whenever n' n))eww, have
sup RT(TT) - R (T) (6) S w
(121)
xEll
Proof of Theorem 5. We will bound both (Tv(TT k) and cov(AP, in terms of D.
First consider Cov p ,, dpy, r)). Recall Npr:
Up = {o(-)) = ão @n(p')lv T (xx]ll E
(122)
Now we create a Lipschitz function such that the image is Hy: note that o θ is that Lg is the Lipschitz constant for é and ||0l|p is the operator-p-norm of θ A For given p', let K(p') { (#(')) の Ôn o (ww) u} C AA. Then Φo K(p') 11p'.
where we recall
Now use the covering number of (p'') to bound that of lIp'
x Cov(IIp,dyy: s Cov K(p'), da, Lo1lO11) s cov A dd,ds, do. Lo
K
(123)
Finally, since all vectors on A have bounded p-norm, we can bound, for some constant E(p, D) depending on the norm:
2E((, 1) D
(o(A,,da,n) s
(124)
K
This gives us:
Cov dy; 3x + 3T 3 11111p
(125)
Cov (Ip doy, k) cou( (D (da
sup p'eap
(126)
Cov(Ap.de
soov
A da, L 1o11@
(127)
D 2EinDWD 2E(p, D)
(128)
K
And let n = I. p
Then the covering number bound becomes
Cov
GoV(II, [I, dr, 6L. (LL s Cov(AP,ae ds. (d,,,,,,aaaaaa L covlA ,da..5)
(129)
D (2EI..DiI))
2F(p, D)VD
(130)
Lgd
Recall that the generalisation error bound is
P sup RR(TT) - R&. (T) (T))
< inf Cov dr, ac ae(0.1)
4 ) 102
(131)
mell
21

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
For simplicity let 3.2 So,
61p
(132)
So
8
(133)
48 181p1|@11pTtr
and
L 1:01@11p..n
(134)
48T. 1111 Tux
(135)
48
We have
P sup (T)
Ro (T) (,,((T)) 2c)
(136)
FEll
ne?
I Cov(II, dr. c/8)e
(137)
E(p.
96L 3
E(p, DVvD
S e
(138)
For simplices, Elp, DI S 1.
So let's say want the probility upper bound be w, then the number of samples need to generalise is
962, 302 cg vD
96
+
VD
3
802
p
(139)
D
9696
6/ 1
VD
n Ω
log
log w
(140)
C.2. Proof of Theorem
Theorem (Bounding sample complexity of learning without proxy) Let li [Loll0lloo be the subset of ii where x 1oll La L= Lipschitr. Set 21' we need
D' 48L E E' (p. E'D''''''''
1
log 1 (p.''''D'
log
(141)
samples to generalise, where D' D. and E' (p, D') > That is, whenever n' nl(eww) we have
P
sup (Lo((ll)))))
[Ro(T) R&, (T) 2 58
(142)
22

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
Proof of Theorem 6. For learning u (,) O F Lx), the covering number bound is as in Eq 138.
For learning If with the same Lipschitz constant (i.e. [+) above but without proxy data, the covering number bound can be read off from Elesedy (2022). Since X' is discrete space, use the p-norm-induced metric in the embedding space of X'; denote the embedding function f. Additionally denote the feasible subset in Py by P. Denote the hypothesis class as il Lo 1 to mean the subset with smallest Lipschitz-constai the argument,
Cov 1611l1)) (10(11116))))) dr, 1101 +x)
(143)
= =ov (cov(V,dyy,... 13) (0
(144)
D' (2 o' (p. D'
(145)
Setting 1
Cov [T( ,d, 2h 1 T. x)
(146)
D' (2E(nngooe Dr
2E (B'(DD')vV
$
(147)
5
then setting e/8 3Ld 1ô11 (i.e. setting 2
P sup [R(T) - Ro. (T) (T)
(148)
well
$ Cov [i Loo1@11ooon dr. 21 Lo + m))e =
(149)
D' 488 (4 ('..'') o²
48L0|1011 E' D'IVD'
S E
(150)
similar analysis show that need
D' D'IVD' log
D'
48L 00l
E', Ep,
18Lo||1lppLz2' D'vVD'
n Ω
log
(151)
2
D. Experiments
D.1. Tempered Reward
We include a simple experiment to demonstrate the efficacy of our method on common real-world scenario regularisation in learned rewards from tempered softmax. We set the environment as follows:
= R Px = (V 1s)
y 1,,,3, so Py- = 2 two-simplex.
23

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
π
g
π
mean
0.63
0.0
0.33
0.34
0.32
std
0.00
0.0
0.00
0.014
0.096
Table 1. Results for the Tempered Reward experiment
D= 1.
nt R
+ A
log (vx = log( (va [m))
Temperature 7 7== 5.
2
Teel
Uniform (1,2,3)
The proxy policy and true policy are implemented as follows. # is initialised as neural network with two linear layers followed by an injective softmax layer; all weights and biases are sampled from Uniform
input features
Vnnput l'eatures
# + Linear(dim(22), D) - Linear(1) |01 - InjectiveSoftMax + #(-lxr)
(152)
logits layer
The true policy is initialised by scaling the logits layer of by T.
π : x + Linear()im(()), D) + Linear Linear(D,1D2 (D,13 - + T + InjectiveSoftMax + 7+(xx)
(153)
logits layer
The proxy policy model itg is parameterised as concatenation of 79, θ and ø, where the injectivity of θ and are ensured by forcing θ to be full-rank and parameterising & with leaky-relu activation (which is injective) and full-rank linear layers. parameterise the true policy model n using the trained fo.", θ and o", together with म parameterised as a linear layer. The parameterisation of सty and ot
to x + 3² - (0)70((x))
(154)
x + e (Ō (7 (I))
(155)
We train the proxy policy model on 8000 proxy samples { Vur,s U1. i1,)) 2000 generated from म,, then only finetune from 35 true samples
{ { (z) gl vl.s) }
generated from .t. We compare the KL. divergences KL(T), aro) and KL(x #) to see the learned π o robust against distribution shift nt + म. We repeat the experiments times. The results are shown in Table 1.
D.2. Empirical verification of Theorem 5 and Theorem 6
To help wider understanding, we attempt to empirically show the results of our theorem that the number of samples n scales differently wrt the generalisation enror for a model constructed with and without our proposed parameterisation. The setup as follows, have the prompt space X 5 and completion space y 21, 4), that is Py A R44, we set D again.
In this case, construct the true and proxy policies to explicitly follow our parameterisation:
The proxy policy # X A e D 2 Py.
So, by Theorem the true policy is भ+ x
A D
A R 2 Py
Py.
24

---

When Can Proxics Improve the Sample Complexity of Preference Learning?
model type:
model type: arbitrary
999
1.000
0.857
251
0.714
slope
0.571
0.429
0.000
-2.5
-2.0
-1.5
-1.0
-0.5
0.5
1.0
Figure Log-log graph of number of samples n against the maximum gap c.
The components 70, Ô are parameterised as neural networks such that the Lipschitz constants are all 1, in other words, ||0l|2 = 1, Lg = 1 and L = 1.
Given this setup, results show that, for fixed w, O for models using our parameterisation and O for arbitrary model. To verify this, we use the following policy models:
For our parameterisation, we obtain samples {=] from the hypothesis class of क8 by fixing 70, Õ, and sampling the different adapters मे from the class of I-Lipschitz functions from A to A
For arbitrary model, we obtain samples { } by using general neural network parameterisation and sampling them from the class of I-Lipschitz functions from X' to Py.
Although the actual bounds Theorems and 6 uses the supremum over or मt, to verify with supremum is computationally expensive, so we settle for only using the samples of #t and directly.
Given all of this, make a log-log graph with the number of samples n and the maximum gap axis and show the possible values of w color; the figure is shown in As this is log-log graph, theoretical results says that the contour lines for specific w should have slope 3 and for the arbitrary parametrisation should have slope 5, we have ploted these lines in black and It can be seen from the plots that the contours are either in rough agreement with the plots, or the slope is slightly below the that of the plots, which is expected as the result is an upper bound.
25


Reviews:
[{"review_id": "V4jnLqnG7C", "reviewer": "Reviewer_6uLY", "summary": "The paper provides a theoretical framework for aligning policies under two different preference models—one “proxy” preference (e.g., from a reward model) and one “true” preference (e.g., from actual human judgments). The main contribution is a set of conditions under which the optimal policy derived from the proxy preference is (or is not) guaranteed to coincide with the optimal policy under the true preference. The authors present formal definitions, propose assumptions about how these preferences interact across prompts, and outline proofs showing how certain alignment guarantees hold when the stipulated conditions are satisfied. The paper’s conceptual focus is on identifying robust criteria for policy alignment, with theoretical arguments anchoring the central claims.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments, we hope to address your main concerns below.\n\n**Strong conditions; Hard-to-verify assumptions:**\n\nFirst we point out that while our conditions may be stringent, there exist a lot of ground truth -> proxy shifts that do meet our criteria; our results show that you can still get gains even under those shifts. For instance, increased temperature (from tempered softmax) is a common bias in learned (proxy) policy models; this prevalent form of bias satisfies our conditions 1-4.\n\nOn the other hand, since the submission, we have managed to relax the conditions in the following ways:\n\n1. Condition 1 can be relaxed from iff (i.e. if and only if) to just if, with the following revised statement:\n    \n    Given $x_1, x_2 \\in \\mathcal X$ , we have: $\\pi^\\dagger(\\cdot|x_1) = \\pi^\\dagger(\\cdot | x_2) \\text{ if } \\tilde\\pi(\\cdot | x_1) = \\tilde\\pi(\\cdot | x_2)$ \n    \n    Moreover, Condition 4 can be shown to be equivalent to\n    \n    $d_{\\mathcal{P_Y}}(\\pi^\\dagger(\\cdot|x_1), \\pi^\\dagger(\\cdot|x_2) ) \\leq L d_{\\mathcal{P_Y}}(\\tilde\\pi(\\cdot|x_1), \\tilde\\pi(\\cdot|x_2))$.\n    \n    Notice that this equivalent condition implies Condition 1. This means we can simplify our presentation and combine Conditions 1 and 4 to a single condition about distributional distance, conducive to future work using distribution metrics to verify this condition.\n    \n2. Instead of requiring that (the revised) Condition 1 (which subsumes the original Conditions 1 and 4) holds for all $x_1, x_2 \\in \\mathcal X$, we only need to require them for $x_1, x_2$, $P_\\mathcal{X}$-almost surely and all proofs go through. This helps future work verify the conditions as one can approximate with samples from $P_{\\mathcal X}$.\n\nAdditionally, as far as we are aware this is the first work that describes sufficient conditions on proxy preferences that allow them to be used to learn a (different) ground truth reward function. In general this problem is as hard as establishing guarantees for RLHF under distribution shifts. Given the prevalence of reward hacking and its impact (e.g., alignment faking [Greenblatt et al., [Alignment faking in large language models](https://arxiv.org/abs/2412.14093), 2024], rare behaviour [Jones et al., [Forecasting rare language model behaviors](https://arxiv.org/abs/2502.16797), 2025], sabotage [Benton et al., [Sabotage evaluations for frontier models](https://arxiv.org/abs/2410.21514), 2024]) we argue that steps towards a principled framework for proxy rewards is crucial for future LLM models. \n\n**Uncertain applicability to reward models vs. human preferences.**\n\nThank you for this. One way to apply our conditions in the real world is as follows. Consider the following example: the true reward function can be described as some (unknown) linear combination of (unknown) functions $r^\\dagger(\\cdot) := g(f_1(\\cdot), \\ldots, f_n(\\cdot))$ and the proxy reward function is an (unknown) combination a subset of these unknown functions $\\tilde{r}(\\cdot) := h(f_1(\\cdot), \\ldots, f_i(\\cdot))$, where $i < n$ and $g$ may or may not be equal to $h$. Note that many of the reward hacking examples mentioned in the introduction can be described using this example:\n\n- **Oscillator performance (ground truth) and output amplitude & frequency (proxy)** [Bird & Layzell, 2002]: This proxy is missing factors that are needed to learn an oscillator of a specific frequency, as the proxy also rewards amplifiers that output noise. This resulted in learning a radio instead of an oscillator.\n- **Race ranking (ground truth) and player score (proxy)** [Clark & Amodei, 2016]: This proxy is missing key properties such as race finish time which led to agents that drove in circles to collect powerups, increasing their player score.\n- **Student success (ground truth) and accepting admissions offer (proxy)** [Golden, 2001]: The percentage of students accepting admissions offers is used by university ranking systems to indicate overall interest and selectivity. However, a university can maximize offer acceptance by rejecting highly-qualified applicants that they believe will attend another university, and so the proxy is clearly missing factors of student success.\n\nIn cases such as these, Conditions 1 and 2 generically do not hold. This is because if functions are missing in the proxy reward then the ground truth and proxy policies cannot have the same level sets. There is also no guarantee that the image of the proxy policy contains the image of the ground truth policy. In general, our conditions can be used to invalidate potential proxies, given (incomplete) prior knowledge of the structure of true and proxy policies.\n\n**….more empirical or real-world studies….**\n\nWhile the time constraint of the rebuttal did not allow us to run real-world experiments, we provide a simple experiment addressing the case with tempered proxy policy, a common form of bias in practice. Please find it in our response to **pBxw** (addressing Weakness 3)", "claims_and_evidence": "The submission claims that if certain conditions—particularly ones ensuring that both the proxy-optimal policy and the true-optimal policy produce the same or comparable outputs across prompts—are met, then the two policies essentially align. While the authors do offer formal theorems and illustrative examples, the practical relevance of these conditions is not entirely clear:\n\n- Hard-to-verify assumptions:  The conditions are implicitly about the induced policy instead of the preference data distribution itself.  These  seem potentially unrealistic to check in real-world scenarios.\n- Strong conditions: The conditions, especially the requirement in condition 1 that policies share the same level set across all prompts, seem very strong. It requires that for all prompts, as long as the proxy policy gives the same distribution for a pair of prompt, the same shall hold for the true distribution. \n- Uncertain applicability to reward models vs. human preferences: Even if the theory holds in a simplified setting, it is unclear whether these conditions translate to real-life systems where the proxy preference model is learned from data while the true preference model is from human, which is hard to characterize in general.\n\nBeyond these concerns, it would also help if the paper provided more empirical or real-world studies to demonstrate whether these theoretical conditions have any identifiable footprint in practical alignment tasks (e.g., under approximate or partial compliance).", "methods_and_evaluation_criteria": "The paper’s methods revolve around formal proofs and theoretical derivations rather than extensive empirical tests. While the authors propose evaluations based on comparing policies derived from proxy versus true preferences, this approach might not account for complexities in real-world settings, such as noisy data or imperfect model assumptions. \n\nThe paper might benefit from outlining a more concrete evaluation pipeline or set of benchmarks where one can empirically assess how well the proposed conditions correspond to measurable alignment in practice.", "theoretical_claims": "The theoretical claims, especially the sample complexity analysis, look good to me.", "experimental_designs_or_analyses": "It would be nice if the authors could provide some discussions on how to verify the conditions empirically, especially when the reward is trained as a neural network from noisy human preference data, while the true preference is aggregated real human preference.", "relation_to_broader_scientific_literature": "The paper contributes to ongoing discussions in the reinforcement learning and AI alignment communities about bridging the gap between a learned reward model (proxy preference) and the underlying human values or intentions (true preference).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tJR6auZQmv", "reviewer": "Reviewer_pBxw", "summary": "The paper investigates how leveraging abundant proxy data---feedback from less (proxy) expert sources---can pre-train a model to obtain a low-dimensional representation, which then serves as a warm-start for learning a true policy from limited high-quality (true) expert data. Here, the true policy refers to the decision-making strategy that is directly aligned with the expert’s behavior, and it is the target in an imitation learning setting where the expert data are costly and scarce. Without incorporating proxy data, directly learning the true policy would require a much larger number of samples due to the high-dimensional nature of the task. The paper provides four key conditions on true expert policy and proxy-expert policy and a two-stage algorithm to allow improved sample efficiency. \n\nThe four conditions collectively ensure that the proxy data can be effectively adapted into the true policy: first, the true and proxy policies must share level sets (Condition 1), meaning that if two prompts yield the same output under one policy, they do so under the other; second, the output range of the true policy must be contained within that of the proxy policy (Condition 2), ensuring the proxy policy is sufficiently expressive; third, the proxy policy’s outputs must lie on a low-dimensional manifold (Condition 3), allowing them to be captured by a compact, finite-dimensional encoding; and finally, the transformation from proxy outputs to true policy outputs must be Lipschitz continuous (Condition 4), guaranteeing that small variations in the proxy representation result in only small changes in the true policy.\n\nIn the first stage of the two-stage learning algorithm, the model is trained on the abundant proxy data by decomposing the proxy policy into an encoder, a linear mapping, and a decoder, effectively capturing the essential low-dimensional structure. In the second stage, this pre-trained structure is fine-tuned using the limited expert data by learning a low-dimensional “adapter” function that corrects the proxy policy toward the true expert policy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging comments and insightful questions. We hope to address your main concerns below.\n\n**Weakness 1 & 2: The derived bounds appear to be vacuous at first glance…**\n\nThis is a good question. Note that in the number of samples bound in Theorem 5 and 6, there are three constants in front of $D$: the lipschitz constants $L_\\phi$ and $L_{\\bar\\pi}$, and the matrix $p$-norm of $\\|\\tilde{\\Theta}\\|_p$; the lipschitz contant of a function intuitively sets its smoothness, and matrix norm can be seen as the lipschitz constant of the linear map given by the matrix. The **power** $D$ is applied the product of all terms inside the brackets (including $1/\\epsilon$), and in particular if the product $= 1$ then raising to $D$ would remain it at $1$. Morally, with the same amount of training data, the higher the dimension of the input and output spaces of the hypothesis functions, the more we have to regularise the hypothesis space (i.e. the more smooth we need the functions) to achieve the same generalisation error. So here, the final bound is not necessarily an astronomically large number - it depends on how much we are willing to regularise (i.e. lower the constants of ) the hypothesis space. \n\n**Weakness 3: …a toy example or a simple experiment…**\n\nWe include a simple experiment to demonstrate the efficacy of our method on a common real-world scenario - regularisation in learned rewards from tempered softmax. We set the environment as follows:\n\n- $\\mathcal X = \\mathbb R^5$\n- $\\mathcal Y = \\{1,2,3\\}$, so $\\mathcal{P_Y} = \\Delta^2$ a two-simplex.\n- $D = 1$\n- $\\pi^\\dagger: \\mathbb{R}^5 \\to \\mathbb R \\to \\Delta^2$\n- $\\text{logit}(\\tilde\\pi(y_k|x))=\\frac{\\big(\\log(\\pi^\\dagger(y_k|x))+\\log(\\sum_k\\pi^\\dagger(y_k|x))\\big)}{T}$. Temperature $T=5$.\n\nWe parametrise the policy model using our proposal, where in particular the final injective component is implemented using a combination of full-rank matrices and leaky-relu activation (which is injective); for more detailed discussion on how to implement the architecture please refer to our response to aNgX. We train a policy model using our proposed parameterisation, first on $8000$ proxy samples $(\\tilde  x, \\tilde   y_w, \\tilde  y_l)$ generated from $\\tilde{\\pi}$, then only finetune $\\bar\\pi$ from $\\pi^\\dagger$ on $35$ true samples $(x^\\dagger, y_w^\\dagger, y_l^\\dagger)$ generated from $\\pi^\\dagger$. We compare the KL divergences $KL(\\pi^\\dagger, \\pi^\\dagger_\\theta)$ and $KL(\\pi^\\dagger, \\tilde\\pi)$ to see if the learned $\\pi^\\dagger_\\theta$ is robust against distribution shift $\\pi^\\dagger \\mapsto \\tilde\\pi$. We repeat the experiments $6$ times. The results are the following:\n\n|  | ref | true | proxy | pi_til | pi_dag |\n| --- | --- | --- | --- | --- | --- |\n| mean | 0.63 | 0.0 | 0.33 | 0.34 | 0.32 |\n| std | 0.00 | 0.0 | 0.00 | 0.014 | 0.096 |\n\nWe see that the mean with $\\pi^\\dagger$(pi_dag) is closer to 0 than $\\tilde\\pi$(proxy), having learned on only 35 true samples.\n\nDue to the time constraints of the rebuttal, we were not able to fully tune the $\\tilde\\pi_\\theta$ and $\\pi^\\dagger_\\theta$ models. In the final version we will run larger experiments and include also comparisons with fully blackbox models for $\\pi^\\dagger$.\n\n\n**Line 116 (left col): What is the definition of sequence space ℓ1.**\n\nThis is the space of (possibly infinite) sequences $\\mathbf x$ such that $\\sum_i^\\infty |x_i| < \\infty$. We will include this as a footnote in the paper for completeness.\n\n**I believe \\ocircle is the composition operator, but defining it somewhere early might avoid confusion.**\n\nYes it is, thanks for pointing it out. We will define it to help with clarity.\n\n**Equation 9: $\\bar\\pi^\\dagger_\\theta \\to \\pi^\\dagger_\\theta$ (let me know if I am wrong) ?**\n\nThat is right! Thank you for the catch.", "claims_and_evidence": "Claim: Pre-training on proxy data yields a low-dimensional representation that, when adapted, reduces the sample complexity of learning the true policy.\n\nEvidence: Theorem 3 establishes the decomposition of the proxy policy into shared components and a low-dimensional adapter, while Theorems 5 and 6 provide sample complexity bounds that compare learning with and without proxy data.", "methods_and_evaluation_criteria": "No algorithm evaluation was performed on benchmarks or datasets.", "theoretical_claims": "I didn't check the proofs, as all of the proofs are in the appendix.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "The ideas in the paper are interesting because they relate to the widely followed paradigm of pre-training followed by fine-tuning, which is currently prevalent in large language models. The paper builds on this concept by showing, with a solid theoretical basis, how abundant proxy data can be used in pre-training to learn a low-dimensional representation, which is then fine-tuned using limited high-quality expert data.", "essential_references_not_discussed": "Not aware of.", "other_strengths_and_weaknesses": "Strengths:\nI think the paper generally has nice presentation. There is a slight overload of notation, which makes parts of the paper hard to read, the broad claims and the different conditions are understandable, even for readers who are not deeply versed in theory.\n\nWeakness 1:\nThe derived bounds appear to be vacuous at first glance. For instance, Theorem 5 seems to require a number of proxy data samples on the order of greater than $ \\sqrt{D}^{D} $. For any reasonable value of $D$ (e.g., $D = 128$), this results in an astronomically large number, which raises concerns about the practical relevance of the bounds.\n\nWeakness 2:\nIt is not entirely clear how the scale of $D’$ compares to $D$. The paper mentions that $D’ \\gg D$, but given that the sample complexity is already extremely high with the current bounds, any further increase due to $D’$ seems to make the requirements even less feasible. This point might be a misunderstanding on my part, but it needs clarification.\n\nWeakness 3:\nSince the algorithm and theoretical results are intended for practical applications, it would be beneficial to include a toy example or a simple experiment. Such an example would help validate the conditions and demonstrate the practical improvement in sample complexity.", "other_comments_or_suggestions": "Line 116 (left col): What is the definition of sequence space $\\ell^1$. \n\nI believe $\\ocircle$ is the composition operator, but defining it somewhere early might avoid confusion. \n\nEquation 9: $\\bar \\pi^\\dagger_\\theta \\rightarrow \\pi^\\dagger_\\theta $  (let me know if I am wrong) ?", "questions_for_authors": "I believe my questions are primarily mentioned in the weakness section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OysaMXKj71", "reviewer": "Reviewer_tZK8", "summary": "The paper studies the problem of reward hacking — eg training an agent when one only has access to proxy reward (and can maximize it) during training, but it leads to the true/gold reward going down. Concretely, the paper studies the setup where one has access to abundant proxy labels, but only few true/gold labels, and one wants to reduce the sample complexity of gold labels by using data with proxy labels.\n\nThis paper gives a theoretical analysis of this problem. It underpins 4 conditions between gold and proxy rewards that, if satisfied, can lead to possible sample complexity reduction. The paper then gives an algorithm to obtain such sample complexity reduction and proves convergence rates of their algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We hope to address your main concerns below.\n\n**…says “distinct prompts”, but in the stated condition 1, we do not enforce x1≠x2…**\n\nThanks for pointing this out, note that we have also relaxed the conditions 1 and 4:\n\nCondition 1 can be relaxed from iff (i.e. if and only if) to just if, with the following revised statement:\n\nGiven $x_1, x_2 \\in \\mathcal X$ , we have: $\\pi^\\dagger(\\cdot|x_1) = \\pi^\\dagger(\\cdot | x_2) \\text{ if } \\tilde\\pi(\\cdot | x_1) = \\tilde\\pi(\\cdot | x_2)$ \n\nMoreover, Condition 4 can be shown to be equivalent to\n\n$d_{\\mathcal{P_Y}}(\\pi^\\dagger(\\cdot|x_1), \\pi^\\dagger(\\cdot|x_2) ) \\leq L d_{\\mathcal{P_Y}}(\\tilde\\pi(\\cdot|x_1), \\tilde\\pi(\\cdot|x_2))$.\n\nNotice that this equivalent condition implies Condition 1. This means we can simplify our presentation and combine Conditions 1 and 4 to a single condition.\n\nGiven this, perhaps the following version flows better:\n\n‘Our first condition says that if two prompts are mapped to very different response distribution under the true policy then they cannot be mapped to very similar responses under the proxy policy.’\n\n**…relevance of this paper’s theory in guiding practice… if the Lipschitz continuity conditions make sense...**\n\nUsing the medical example in the paper, (the revised) Condition $1$ (subsuming Conditions $1$ and $4$ from) means that if the gold/expert doctor thinks two symptoms are very different (i.e. they map to very different prescriptions), e.g., $|\\pi^\\dagger(\\cdot|x_1) -  \\pi^\\dagger(\\cdot|x_2)| = d$, then the proxy/student cannot believe the two symptoms are similar, at least there should be some constant $L$ such that the student should not think that the difference between two prescriptions is less than $d/L$ for any $d$. This essentially requires that the proxy policy has the correct (within a constant scaling factor) idea of ‘distance’ in the output (response distribution) space. \n\nIn general any continuously differentiable function is Lipschitz continuous, what makes the difference is the constant $L$. Notice that we did not assume a fixed value for $L$ - it can be seen from the proof of Theorem $3$ that $L$ will impact the lipschitz constant of $\\bar\\pi$, which then by Theorem $5$ impact the sample complexity of learning with the proposed model parameterisation; this means that if the proxy data is ‘good’ at understanding the distance in the output space, then we need fewer samples to converge. \n\nWe have also provided a simple experiment to illustrate a case when all four conditions are satisfied, please see our answer to reviewer pBxw for the description, under ‘Weakness 3’.\n\n**…toy 1D bandit..**\n\nWe have provided a simple experiment. Please see our answer to reviewer pBxw for the description, under ‘Weakness 3’.\n\n**…the low dimensional encoding condition (condition 3)…**\n\nThe low-dimensional encoding is similar to the standard low-dimensional manifold condition typically used in deep learning. For example, the last token embedding in a LLM represents, in a lower dimension, the next-token prediction distribution. The key difference here is that we assume the encoding to be bi-Lipschitz; note that this can be considered a mild condition since all invertible, continuously differentiable functions whose inverse is also continuously differentiable satisfy this condition. In most deep learning tasks, we assume that data can be fitted to a deep neural network, which are continuously differentiable, satisfying the condition; in a typical low-to-high-dimension decoder, the neural network can be implemented as an injective function, and its inverse is also typically continuously differentiable.\n\n**…offline model-based RL…most common use of RLHF is: (1) collect a lot of gold reward labels from humans, (2) train a reward model against these labels, which will be our proxy reward model, (3) train an agent against this proxy reward model.**\n\nThis could be best explained in the context of our simple experiment: the experiment can be readily adapted to the RLHF pipeline you described: 1) collect gold or noisy reward labels from humans, 2) train a biased reward model **(biased since temperature is increased)**, (3) train a proxy policy from the biased reward model using our parameterisation (4) finetune on a small number of additional gold reward labels from humans. \n\nIn general, our framework applies to contextual bandits, the subclass of RL problems relevant to current LLM training. The extension to full sequential RL is left outside the scope.\n\n**How would the encoder/decoder setup look in real-world LLM cases?**\n\nDue to space constraint, we have written the detailed explanation to this question in our response to **aNgX.** Please kindly refer there, thank you.", "claims_and_evidence": "Yes, the claims are supported by proofs.", "methods_and_evaluation_criteria": "The paper is theoretical and has no experimental results.", "theoretical_claims": "> Our first condition says that two distinct prompts are mapped to the same response distribution under the true policy whenever they are under the proxy policy.\n\nThe above says “distinct prompts”, but in the stated condition 1, we do not enforce $x_1 \\neq x_2$. This is nit-picking, not a serious flaw (since the case $x_1 = x_2$ is trivial if we assume the policy maps the same prompt to the same probability distribution deterministically).\n\n# Conditions 1 - 4\n\nI have tried to check the proofs in the paper (though not in absolute details), they look mostly okay to me. My main concern is the relevance of this paper’s theory in guiding practice. Could the authors provide one real use case/simulation to show why conditions 1-4 are reasonable? Eg I am uncertain if the Lipschitz continuity conditions make sense in the real world. Also, even experiments on a toy 1D bandit similar to would strengthen the paper a lot.\n\nAnother assumption that is probably hard to hold is the low dimensional encoding condition (condition 3). Could the authors give a real-world example of this?\n\n**Disclaimer**: My research expertise is not theory, so if the other reviewers agree that the theory presented in this paper is relevant, than I would request the area chair to put more weight on those reviews.\n\n# Offline model-based RL version\n\nHow does this paper’s theory hold for the more practical use case of offline model-based RL, which is the predominant use case of RLHF? More concretely, the most common use of RLHF is: (1) collect a lot of gold reward labels from humans, (2) train a reward model against these labels, which will be our proxy reward model, (3) train an agent against this proxy reward model.\n\nThis is the most common scenario where one studies reward hacking, to the best of my knowledge, as studied most prominently in [2], [3]. Could the authors extend the theory to this setup as well/could we make any useful predictions here?\n\nHow would the encoder/decoder setup look in real-world LLM cases?\n\n# References\n\n[1] Scaling Laws for Reward Model Overoptimization in Direct Alignment Algorithms, https://arxiv.org/abs/2406.02900\n\n[2] Scaling Laws for Reward Model Overoptimization, https://arxiv.org/abs/2210.10760\n\n[3] Reward Model Ensembles Help Mitigate Overoptimization, https://openreview.net/forum?id=dcjtMYkpXx", "experimental_designs_or_analyses": "The paper has no experimental results.", "relation_to_broader_scientific_literature": "The paper is related to reward hacking, as described in [2], [3].", "essential_references_not_discussed": "I am unaware of any such references.", "other_strengths_and_weaknesses": "None to note.", "other_comments_or_suggestions": "None.", "questions_for_authors": "Please look at the section **Theoretical Claims** for my questions/concerns.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w4qR1Fgu2D", "reviewer": "Reviewer_aNgX", "summary": "This paper discusses the sample complexity of optimizing LLMs with proxy rewards to improve the true policy. The authors give sufficient conditions, under which the proxy data is guaranteed to improve the sample complexity of learning the true policy. In general, I think this is an important topic as we are usually unsure of whether the data for fine-tuning LLMs is reliable enough to reflect the true objective, this paper gives us insight on how to address this important and practical problem.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging that our work addresses an important problem and for asking the interesting questions. We answer your questions below.\n\n**Questions For Authors:**\n\n**1. I understand this is a paper focusing on theories. But I am curious about the parameterization part in section 4.3. How are we able to constitute the three functions, i.e. the embedding function, the linear map and the injective function? Will they be possible to integrate into current architecture of LLMs? This may be crucial in transferring theory into practice.**\n\nThis is an important question. Here is one example for how to instantiate each function.\n\n- Function (i): Softmax(NN(x)), where NN(x) is any arbitrary neural network, including fully connected networks or encoder architectures for language modelling such as attention mechanism.\n- Function (ii): A linear layer. This can be implemented by any weight matrix which maps from a lower to a higher-than-or-equal-to dimension, since a randomly generated matrix almost surely has full rank.\n- Function (iii). This can be composed of injective attention mechanisms, injective linear layers, injective fully-connected networks, and injective softmax layers. We explain them one-by-one: attention mechanisms can be implemented as injective by using the softmax attention, since applying softmax to a matrix will generically make it full rank (see e.g. [Bridging the Divide: Reconsidering Softmax and Linear Attention](https://arxiv.org/abs/2412.06590)  Han et al 2024). Injective linear layers as explained for function (ii) can be implemented as injective. Injective fully connected layers can be implemented by using a combination of full-rank weight matrices and injective activations such as leaky ReLU; see also references [Furuya et al., [Globally injective and bijective neural operators](https://proceedings.neurips.cc/paper_files/paper/2023/hash/b40d5797756800c97f3d525c2e4c8357-Abstract-Conference.html), 2023] and [Puthawala et al, [Globally injective relu networks](http://www.jmlr.org/papers/v23/21-0282.html), 2022]. Injective Softmax can be implemented as follows: x → [x, 0] → softmax([x,0]).\n\n**2. How will the level of distributional shift between proxy data and true data affect the results of this paper?**\n\nThis is an interesting question! We just want to point our that distribution shift between proxy and true data can be large, so long as the conditions still hold. \n\nHowever, it is very interesting to consider the case where certain assumptions hold but others do not, or assumptions hold approximately. We have had a deeper look at our conditions and can relax them in two ways, please see our answer to reviewer 6yLU in ‘Strong conditions; hard-to-verify assumptions’. \n\nThe in-between area of approximate but not full compliance with our conditions is indeed interesting to explore but require empirical evaluations, but as this paper focusses on theory, empirical evaluation is left outside the scope. We are currently working on extending the project to empirically test the sensitivity of the conditions in large-scale experiments.\n\n**3. Minors: writing issues, e.g. “iff” in condition 1**\n\nPlease note that this is not a typo, iff is a mathematical shorthand for if and only if. However, we have since relaxed this condition, see our answer above.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "This paper discusses a practical problem in LLM fine-tuning that widely exist. Prior works tend to ignore the optimizad policy is actually a proxy policy.", "essential_references_not_discussed": "I don't see any.", "other_strengths_and_weaknesses": "See in questions.", "other_comments_or_suggestions": "No", "questions_for_authors": "1.\tI understand this is a paper focusing on theories.  But I am curious about the parameterization part in section 4.3. How are we able to constitute the three functions, i.e. the embedding function, the linear map and the injective function? Will they be possible to integrate into current architecture of LLMs? This may be crucial in transferring theory into practice.\n2.\tHow will the level of distributional shift between proxy data and true data affect the results of this paper?\n3.\tMinors: writing issues, e.g. “iff” in condition 1", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the question of when maximizing a proxy reward is sufficient to learn the optimal policy. There appear to be a general consensus in favor of acceptance.

However, many aspects of the paper can be improved. For instance, as brought up by reviewer Reviewer 6uLY, the conditions defined in the paper are hard to verify and therefore it's unclear how useful the findings in this paper would be in practice.

Another drawback not brought up by reviewers is the missing of other related works. The effect of optimizing a proxy reward/model is studied widely in RL literature, including those concerning with poisoning attacks (reward is hacked by adversaries), sim-to-real transfer, model-based RL, etc. Sufficient conditions in similar flavors to those in this paper show up quite frequently in these works. A thorough literature review is needed to understand the connection and differences in these techniques.

I encourage the authors to improve the paper on these aspects for the camera ready version.
Decision: Accept (poster)