The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regret
Authors: Lukas Fluri
Leon Lang
Alessandro Abate
Patrick Forré
David Krueger
Joar Max Viktor Skalse
Venue: ICML 2025 poster (2025)
Keywords: Reward learning
RLHF
RL
Safety
Distributional shift
Generalization
Learning Theory
Primary area: social_aspects->safety
TL;DR: We study the relationship between the expected error of a reward model on some data distribution and the the reget of policies trained using the reward model.

Abstract: In reinforcement learning, specifying reward functions that capture the intended task can be very challenging. Reward learning aims to address this issue by *learning* the reward function. However, a learned reward model may have a low error on the data distribution, and yet subsequently produce a policy with large regret. We say that such a reward model has an *error-regret mismatch*. The main source of an error-regret mismatch is the distributional shift that commonly occurs during policy optimization. In this paper, we mathematically show that a sufficiently low expected test error of the reward model guarantees low worst-case regret, but that for any *fixed* expected test error, there exist realistic data distributions that allow for error-regret mismatch to occur. We then show that similar problems persist even when using policy regularization techniques, commonly employed in methods such as RLHF. We hope our results stimulate the theoretical and empirical study of improved methods to learn reward models, and better ways to measure their quality reliably.

The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regret
Lukas Fluri" 1
Leon Lang"
2 Alessandro Abate 3 Patrick Forré?
David Krueger*
Joar Skalse
Abstract
True Reward Function
Learned Reward Function
In reinforcement learning, specifying reward func- tions that capture the intended task can be very challenging. Reward learning aims to address this issue by learning the reward function. However, a Iearned reward model may have a low error on the data distribution, and yet subsequently produce policy with large regret. We say that such a reward model has an error-regret mismafch. The main source of an error-regret mismatch is the distributional shift that commonly occurs during policy optimization. In this paper, we mathemat- ically show that a sufficiently low expected test error the reward model guarantees low worst- case regret, but that for any fixed expected test error, there exist realistic data distributions that allow for error-regret mismatch to occur. We then show that similar problems persist even when us- ing policy regularization techniques, commonly employed in methods such as RLHF. We hope our results stimulate the theoretical and empiri- cal study of improved methods to learn reward models, and better ways to measure their quality reliably.
bistrisuton
Optinal
Polley pistributtin
Figure I. Reward models (red function) are commonly trained by supervised learning to approximate some latent, true reward (blue function). Given enough data, one can hope that the reward model is close to the true reward function average over the training data distribution (upper gray layer) - the expected error is low. However, low expected error only guarantecs good approxima- tion to the true reward function in areas with high coverage by the data distribution! Optimizing learned reward model then induces a distribution shift which can lead the policy to exploit uncertaintics of the learned reward model in low-probability areas of the transition space (lower gray layer). In the worst case, this can lead to high regret. We refer to this phenomenon as error-regret mismatch.
RL policy maximize the
algorithms (e.g. Ng & Russell (2000); Tung et al. (2018) Brown & Niekum 2019): Palan et al, (2019). ), with one of
1. Introduction
the most popular being reinforcement learning from human
feedback (RLHF) (Christiano et al. 2017 Ibarz et al. 2018).
To solve a sequential decision problem with reinforcement learning (RL), we must first formalize that decision problem using a reward function (Sutton & Barto 2018). However, for complex tasks, reward functions are often hard to spec- ify correctly (Krakovna 2020). To solve this problem, it is increasingly popular to learn reward functions with reward learning algorithmss, instead of specifying the reward func- tions manually. There are many different reward learning
For any learning algorithm, it is erucial question whether not that learning algorithm is guaranteed converge "good" solution. For example, in the case of supervised learning for classification, it can be shown that a learning algorithm that produces a model with a low empirical error (i.e., training error) is likely to have a low expected error (i.e., test error), given a sufficient amount of training data and assuming that both the training data and the test data is drawn i.i.d. from single stationary distribution (Kearns) & Vazirani 1994). In the case of supervised learning and standard assumptions, we can therefore be confident that learning algorithm will converge to a good model, provided that is given a sufficient amount of training data.
'Equal contribution 'ETH Zurich Universityy of Amster- dam *Oxford University "University of Cambridge. Correspon- dence to: Lukas Fluri <lukas, fluri @ eth.cchh. Leon Lang I.laag@uva.nl-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
Since reward models are also typically learned by supervised

---

The Perils of Optimizing Learned Reward Functions
learning, we might assume that classical Sarming-theorete guarantees carry over. However, these guarantees only en- sure that the reward model is approximately correct relative to the training distribution. But after reward learning, we optimize a policy to maximize the learned reward, which effectively leads to a distributional shift. This raises the worry that the trained policy can exploit regions of the state space with abnormally high learned rewards if those regions have low data coverage during training. In this case, we can have reward models that have both low error the training distribution and an optimal policy with large regret, a phenomenon we call error-regret mismatch. We visualize this concern in Figure
1. As the error of learned reward model on a data distri- bution goes to zero, the worst-case regret of optimizing a policy according to that reward model also goes to zero (Theorems 3.1 and 3.2
2. However, for any > O, whenever a data distribution has sufficiently low coverage of some bad policy, it is unsafe; in other words, there exists a reward model that achieves an expected error of but has a high-regret optimal policy (Theorem 3.3 case of error-regret mismatch.
3. As consequence, when an MDP has a large number of independent bad policies, every data distribution is unsafe (Theorem 3.4.
To illustrate this concern, imagine training a chatbot to be helpful, honest, and harmless (Askell et al., (02T). We know that the chatbot will face various unsafe queries during deployment (e.g- "how to build a bomb") and so such queries we train a reward model to penalize helpful answers and highly reward refusals.
4. More precisely, we derive set of linear constraints that precisely characterize the safe data distributions for a given MDP (Theorem 3.5
We then investigate the case of regularized policy optimiza- tion (including KL-regularized policy optimization, which is commonly used in methods such as RLHF). We derive regularized versions of Thehrees 3.1 and 3.3 in Theorem and Theorem 4.2 This shows that regularization alone is no principled solution to error-regret mismatch.
Unfortunately, all unsafe prompts can be answered in var- ious distinct "styles" (e.g.. different languages (Verma & Bharadwaj| 2.25)). Consequently, least one specific harm- ful answer will likely be very rare in the reward model's training data. The learned reward model can then erro- neously assign high reward to this rare, harmful answer without a significant increase in its training error (as this answer is infrequent in training). During policy optimiza- tion, the policy may exploit this flaw, choosing the harmful answer the reward model mistakenly prefers. This can result in harmful chatbot with high true regret, despite the reward model having low error on the training data distribution, an example of error-regret mismatch. We illustrate this concern in detail in Appendix B.4
We then develop several generalizations of our results for different types of data sources for reward model training. such as preferences over trajectories and trajectory scoring (Section 5). Lastly, motivated by the recent success of large language models [OpenAl] 2022 Gemini Team| 2023 Anthropic 2023). we provide an analysis for the special case of RLHF in the contextual bandit case where we prove a stronger version (Theorem 6.1 of the failure mode already discussed in Theorem 4.2 for general MDPs.
To single out the issue of error-regret mismatch in our the- oretical analysis, we take the goals of classical learning theory as a given and show that they are not enough to en- sure low regret. More precisely, in probably approximately correct (PAC) learning (Kearns& & Vazirani 1994) the goal is to derive sample size that guarantees a certain likelihood ("P"") of an approximately correct ("AC"") model on new data points sampled from the training distribution. In our results, we assume that we already have an approximately correct reward model on data distribution, and then investigate what we can or not conclude about the regret of policies trained to maximize the modeled reward.
1.1. Related work
Note: We provide a more extensive related work section in Appendix A
In offline reinforcement learning, we aim learn low-regret policies for an MDP (S, A, T, Moo R, ?) where the only in- formation about the reward function R (and sometimes tran- sition distribution т (Wang et al., 2022b; Uchara & Sun 2021 stems from a dataset ((s a, r)& sampled from some data distribution D E ( A key research ques- tion is understanding which conditions on D allow learn- ing a near-optimal policy (i.e., a policy with regret smaller than some L [0, 1)) with an efficient sample complexity, where sample-efficient usually means polynomial in 7,-1 and some other parameters of the MDP and D. Existing the- oretical work primarily falls into two categories, covering
Our theoretical analysis shows that guarantees in policy regret are very sensitive to the data distribution used to train the reward model, leading to our notions of safe and unsafe data distributions. Moreover, we find evidence that some MDPs are in a certain sense "too large" allow for safe data distributions. We establish for general MDPs:
both MDPs (Foster et al., 2021 Wang et al. 2022b 2020
Amortila et al.) 2020
Uehara & Sun 2021
Uehara et al.
2

---

The Perils of Optimizing Learned Reward Functions
2021
and contextual bandits
Nika al.
2024
Cen al.
when using the mean squared error metrie. Their Theorem 4.2 demonstrates that Regret E O v where Cov is some measure of coverage and the error in the reward function, and where the square root emerges from using the mean squared error during the reward learning step (see Appendix [B.]] for how this relates to our results).
2024
Lower bound results prove that various data-coverage con- ditions are insufficient for sample-efficient offline RL by establishing a lower bound on the number of samples re- quired to achieve low policy regret. In particular, research in this area (Foster et al., 2021; Wang et al. 2022b; 2020 Amortila al. 2020 Nika et al. 2024) identifies adversarial MDPs that satisfy specific data- coverage conditions and yet for which achieving low regret is either computationally in- tractable due to excessive sample requirements (Foster et al.
While Song et al. (2024) focus on RLHF with mean-square error metric, we provide similar results for general classes of regularized and unregularized policy optimization (for both MDPs and contextual bandits), and show how these regret guarantees automatically generalize to a wide range of different error metrics for different reward learning methods.
2021
Wang et al. 20226] 2020; Nika et al., (2024) or fun-
damentally impossible regardless of sample size (Amortila
For our initial guarantees (Theorems 3.1 3.2 and 4.1 we use the coverage condition min(,.a) D (s, the required reward learning error in terms of this coverage. Since we assume that all states of our MDPs are reachable, this is equivalent to a full coverage condition (see Table of [eehara & Sun (202T) for an overview of different coverage conditions). We then show that for fixed e, a too small coverage leads to possibly high regret (Theorems 3.3 4.2 and T.T.. Finally, we fully generalize our results from Theorems 3.1 to 3.4 into single theorem (Theorem 3.5 which allows to determine for arbitrary data distributions whether they give rise to worst-case safety for fixed error e and required regret L. To the best of our knowledge, we are the first work to achieve such fine-grained safety results.
et al. 2020).
D(s, a) > and phrase
Upper bound results, on the other hand, establish positive guarantees under specific structural assumptions. Research
in this category (Wang et al. 2022b 2020 Uehara & Sun Nika et al. 2024] Cen et al. 2024 Song et al. (024)
2021
develops algorithms with provable boper-bounds on the number of required samples to achieve low policy regret. This is usually done by making structural assumptions about the MDP, reward learning process, or policy optimization approach.
In reward learning, compared to offline RL, one first learns a reward model from a dataset, which is typically sampled via various strategies from a data distribution D E AA) (cf. Section 2.1]. Intuitively, as in offline RL, the quality of a reward model is influenced by two key factors: the dataset size n and the dataset quality, specifically how well the data distribution D covers the data space SxA. Indeed, prior work confirms this intuition, with most works (see|Nika Nika et al. (2024) for a recent example) showing that the regret is de- pendent on a) the inverse dataset size vi b) some measure of the coverage of D, and c) some structural assumptions of the specific approach. Such structural assumptions may include:
Several approaches have been proposed to address the issue of out-of ditto--disttibutionn robustness in reward learning, such as ensembles of conservative reward models (Coste et al. 2023), averaging weights of multiple reward models (Ramé et al. 2024), iteratively updating training labels (Zhu et al. 2024 on on-policy reward learning (Lang et al. 2024a). and
distributionally robust planning (Zhan et al. 2023). Re- cently, Kwa et al. (2024) show that RLHF and Conditioning can be provably safe under fairly strong structural assump- tions-suct as deterministic transitions. light-tailed reward errors, and independence between true and proxy rewards. Furthermore, Laidlaw et al. (2024) consider a setting where the learned and true reward functions are positively corre- lated under a reference policy. They prove that maximizing the proxy reward with a chi-squared divergence penalty yields regret no worse than that of the reference policy. In experiments, they approximate this regularized objective and report favorable results.
realizability of function classes (Wang et al., 2022b Uchara
& Sun 2021 Foster et al.) 2021 Nika al. 2024). linear
function approximation (Nika et al.) 2024 Cen et al. 2024
Wang et al. 20226), and various constraints on reward- or
policy functions (Wang et al. 2020 Uehara & Sun 2021
Nika et al. 2024).
Our paper differs from these works in key aspect: We explicitly analyze how the reward modeling error related to the final policy regret, rather than focusing the number of samples. This also allows us to study adversarial guaran- tees of low policy regret (given low reward modeling error), whereas prior work considers probabilistic guarantees when sampling from the data distribution. The most relevant work studying a similar setup to ours is [Song et al.) (2024). Their setup in section 3. combined with their Assumption 4.3, perfectly recovers our safe distribution definition (see The- orem 2.1) when applied to the special case of RLHF and
2. Preliminaries
A Markov Decision Process (MDP) is a tuple (S,A,T, Ho, where S is set of states, A is a set of actions, T SSA - A(S) is a transition function, No E A(S) is an initial state distribution, R Sxx + R is a reward function, and 7 E (0, 1) is a discount rate. We define the range of reward function R as range R == max R(s,0) a) min R(s,a).
3

---

The Perils of Optimizing Learned Reward Functions
A policy is function π S - (AA). We denote the set of all policies by IT. A trajectory & (50; 0o, $1; 01; a1:..) is a possible path in an MDP. The return function G gives the cumulative discounted reward of a trajectory.
approximately correct, we abstract away the data sources and training procedures and assume that learn a reward
model R which satisfies
[f(ssa) R(s, a)l range R
G({) = Ei= 70 R(s), at), and the evaluation function J gives the expected trajectory return given a policy, J(T) ) Eg [G{ A policy maximizing J is an optimal policy. We define the regret of a policy x with respect to reward
B(s,a)~D
S
(I)
for some e > 0 and stationary distribution D over transitions Sx Note that this is the true expectation under D, rather than an estimate of this expectation based on some finite sample. We divide by range R, since the absolute error c is only meaningful relative to the overall scale of the reward R.
function R as
Reg R (x) = max EEn J JN(TT)
max Jn(x') enn Jn(Tr) E [0, 1].
To be clear, most reward learning algorithms cannot guar- antee a bound as in Equation ( since most realistic data sources do not determine the true reward function, even for infinite data (Skalse et al. 2023). Instead, we choose Equa- tion (T because serves as an upper bound to many com- mon reward learning training objectives (see Appendix CC.5) Thus, when we show in later sections that high regret is possible even when this inequality holds, then this prob- lem can be expected to generalize to other data sources. We make this generalization precise for some data sources in Section 5 In particular, we will show that Equation (I) implies a low cross-entropy error between the choice distri- butions of the true reward function and the reward model, as is commonly used for RLHF, e.g. in the context of language models (Ziegler et al. 2019
Here, Jn is the policy evaluation function for R. We choose the regret Reg" as our main performance metric of poli- cies in this paper, which is justified by the fact that it is a normalized version of the policy evaluation Jn.
In this paper, we assume that S and A are finite, and that all states are reachable under T and po. We also assume that max Jn min Jn # 0 (since the reward function would otherwise be trivial). Note that this implies that range R > 0, and that Reg (Tr) is well-defined.
The state-action occupancy measure is a function II + R sxAl mapping each policy π E II to the cor- responding "state-action occupancy measure", describing the discounted frequency that each state-action tuple is visited by policy. Formally, (s,a)
17" (s)
Ei P(s,- s, a | 5~~0~ TT) Note that by writing the reward function R as a vector R E R|SxAI, we can split into a function that is linear in R: ((z) = 17th R. By normalizing state-action occupancy measure 17t we obtain policy-induced distribution D = 7) 17"
Policy optimization Given it, we then learn a policy म by solving the MDP (S,A, T, No: R, 7)) In the most straight- forward case, we do this by simply finding policy that is optimal according to Rt However, it also common to perform regularized optimization. In that case, we make use of an additional regularization function w(T) 2 0 for all π E II. Given R, a regularization function w, and a regularization weight À E [0, 20), we say that # is (A, ooptimll if
II + I. with
2.1. Problem formalization of RL with reward learning
In RL with reward learning, we assume that we have an MDP (S, A, T, Mo, R, 7) where the reward function R is unknown. We may also assume that T and μl are unknown, as long as we can sample from them (though S, A, and y must generally be known, least implicitly). We then first learn reward model R that approximates the true reward R and then optimize a policy â to maximize R. The aim of this two-step procedure is for ने to achieve low regret under the true reward function R. We now formalize these aspects in detail for our theoretical analysis, with a visualization provided in Figure 2
A E arg max Ja JT(T)) - -WW(T).
(2)
Typically, À punishes large deviations from some reference policy Tref, e.g. with the regularization function given by the KL-divergence w(T) = DaL (T Tret). Nzel may also be used to collect training data for the reward learning al- gorithm, in which case we may assume D = neet in Equation (I). However, most of our results do not depend on these specific instantiations.
Reward learning We first learn a reward model i from data. There many possible data sources for reward leamn ing, like demonstrations (Ng & Russell 2000), preferences over trajectories (Christiano et al. (017). ), or even the initial environment state (Shah et al.] 2019); a taxonomy can be found in (Jeon et al. 2020). Since we are concerned with problems that remain even when the reward model is already
Regret minimization The aim of the previous two steps is for the policy स to have low regret Reg" R (#) under the true reward function R. Our question is thus if and when it is sufficient to ensure that R satisfies Equation ① in order to guarantee that a policy Ω optimal according to Equation has low regret Reg (f).
4

---

The Perils of Optimizing Learned Reward Functions
Optimaliy
Thus, unsafe( e, I, w) consists of the data distribu- tions D for which there exists reward model R that is e-close to R and policy Ā that is (A, -opptimal with re- speet to R. but such that स has large regret Reg" R (#) 2 L. In this sense, we are operating under a worst-case frame- work for the reward model and policy learned by our training algorithms. Note that and L are free parameters in our definition; they are a measure of how well we can approx- imate the true reward function R, and what regret we find acceptable, respectively.
arg mix d1(a)= A xxx
Reward weaming
R
Palky Opriminntion
π
Duta
Low Expected Error
Low Regret Reg" (f)
Fa [R. R)]
Guaranteed by Safe Data Distributions 1
Figure 2. An abstract model of the classical reward learning pipeline. A reward model R is trained to approximate the true reward function R under some data distribution D. The train- ing process converges when R is similar to R in expectation (see the second step, a policy á is trained to achieve high learned reward, possibly involving regularization (see We are interested the question of when exactly this training process guarantees that á has low regret. More formally, we call data holds for
Whenever we consider the unregularized case (A = 0 or w = 0), we drop the and w to ease the notation and just use safe R, e, L) and unsafe (R, c, L) instead. Lastly, we mention that while we use the mean absolute error (MAB) in condition I, one could in principle also work with the mean-squared error. All our results then have analogous versions. We explain this in Appendix B33
distribution D safe whenever the implication all reward models R that satisfy
Note: Throughout this paper, we will use the terminol- ogy that a data distribution D "allows for error-regret mismatch" " as a colloquial term to express that D E unsafc R, c, W.
2.2. Safe data distributions
We now make the elaborations from the previous subsec- tions more concrete by providing a formal definition of safe data distribution. In particular, we say that a data dis- tribution D is safe, whenever it holds that for every reward model R that satisfies Equation (1) for D, all optimal poli- cies of R have low regret. We provide a visualization of this concept in Figure and a formal definition in Theorem 2.
3. Error-regret mismatch for unregularized policy optimization
In this section, we investigate the case where no regulariza- tion is used in the policy optimization stage. We seek to determine if it is sufficient for reward model to be close to the true reward function on a data distribution in order to ensure low regret for the learned policy.
Definition 2.1 (Safe- and unsafe data distributions). For given MDP (S,A, T, Po, 7,,), let c > 0, L E [0, 1]. and À E [0, oo). Let w be a continuous function with w(T) 2 0 for all E II. Then the set of safe data dis- tributions safe(R, e, L, X, w) is the set of all distributions D E A(SxA) such that for all possible reward models R: fxAxA= + R and policies + S + ((A) that satisfy the following two properties:
In our first result, we show that under certain conditions, a low expected error e does indeed guarantee that policy optimization will yield a policy with low regret.
Proposition 3.1. Let AS,A, N,,, R, 7) be an arbitrary MDP, let L E (0, 11. and let D E (SSxA) be positive data distribution (i.e., distribution such that D(s, a) > O for all (8,a) E A). Then there exists an > 0 such that D E s,
1. Low expected error:
is e-close to I under D, i.e., B(s,a)=D [[(s.a)) (a(ss.a-R(ssa))) R(s.a)] S <.
range It
The proof of Theorem can be found in Appendix D.I (see Theorem D.7p and is based on application of Berge's s maximum theorem (Berge 1963), and the fact that the ex- pected distance between the true reward function and the learned reward model under D is induced from a norm. See Theorem D. 15 for a similar result in which the expected error in rewards replaced by an expected error in choice probabilities.
2. Optimality: is (A, (o optimal with respect to R, i.c. â E arg max, (n( (T).
we can guarantee that से has regret smaller than L, i.e.:
3. Low regret: से has a regret smaller than I. with respect to R, i.c., Reg" (+) < L.
One might be inclined to conclude that the guarantee of Theorem 3.T allows one to practically achieve low regret by ensuring a low error c (as measured by Equation (I). However, in the following result we provide a more detailed analysis that shows that low regret requires a prohibitively
Similarly, we define the set of unsafe data distributions to be the complement of safe R, L, w))
unsafe( R, c, I,, A)) = A(SxA) \ safe(R, L, w))
5

---

The Perils of Optimizing Learned Reward Functions
low E:
Corollary 3.4. Let M AS, T, R, be an MDP,
<> 0, and I. E [0. Assume there exists a set of policies I1, with:
Proposition 3.2. Let the setting be as in Theorem 3.7 If 0 satisfies
1 1-7 7 range JR <<
Reg R (T) for all π E III:
min (x.4)ESxA
a(s,a)
V2 range R
supp D Ssupp D = 0 for all n, E [[,; and
then D E safe(
|1ll| 2 1/E.
The proof can be found in Theorems D.11 and D.12 Ap- pendix D.2] Theorem D.14 shows that the bound on is tight up to factor of v2. This result is problematic in practice due to the dependence on the minimum of D. Re- alistic MDPs usually contain a massive amount of states and actions, which necessarily requires to give very small support to least some transitions. The dependence of the upper bound on D also shows that there is for which every distribution D is guaranteed to be safe, as min(s..) D(s, a) can be arbitrarily small. We con- cretize this intuition by showing that in every MDP and for every e > O, there exist weak assumptions for which a data distribution allows for large error regret mismatch.
Then unsafe( R c, T) A(S x A), ie:: all distributions are unsafe.
The proof of Theorem 3.4 can be found in Appendix C.2 (see Theorem C.6).
Theorem 3.4 outlines sufficient conditions for a scenario where all possible data distributions unsafe for given MDP. This happens when there exist many different policies with large regret and disjoint support, which requires there to be a large action space. This could for example happen in the case of a language model interacting with a user if there are many mutually distinct styles to answer unsafe queries. We illustrated this concern in slightly more detail in the introduction, and in full detail in Appendix [B.4] More generally, we believe this intuition could be turned into concrete theoretical result for general MDPs by assuming that for each state, there are many actions that are equally bad under the true reward function but induce the same transition-dynamice This could be studied in the context of MDPs with symmetries (van der Pol et al., 202T) and might allow to prove the existence of the bad policy т from The- orem 3.3 or the set of bad policies II, from Theorem 3.4 We leave such an investigation to future work.
Proposition 3.3. Let M = (S, No: R. 7) be an MDP, D AA) a data distribution, e > O, and L E [0, 1]. Assume there exists a policy ftr with the property that Reg" R (f) 2 L and D(supp D*) < e, where supp D* is defined as the set of state-action pairs (s, a) E SxA such that D* a) > O. In other words, there is a "bad" policy for R that is not very supported by D. Then, D allows for error-regred mismatch to occur, ie.,, E unsafe( R, e, L.).
The proof of Theorem 3.3 can be found in Appendix C.2 (see Theorem C. The intuition is straightforward: There exists reward model I that is very similar to the true re- ward function R outside the support of D but has very large rewards for the support of D Because D(supp D
We conclude by stating the main result of this section, which unifies all previous results and derives the most general conditions, i.e. necexsary and sufficient conditions, for when exactly a data distribution allows for error-regret mismatch to occur:
is very small, this still allows Å to have a very small ex- pected error w.r.t. to D, while ft, the optimal policy for R, will have regret at least L. To avoid confusions, we show in Theorem C.7 that the assumptions on in Theorem 3.22 and Theorem 3.3 cannot hold simultaneously. This is pected since otherwise the conclusions of these propositions would imply that data distribution can be both safe and unsafe.
Theorem 3.5. For all MDPs (S,A,T, po. R, 2) and L [0, 1]. there exists matrix M such that for all 0 and D A(SxA) we have;
D E safe(R,
-M.D> raaagg R- 1, (3)
Note that the conditions for unsafe data distributions in Theorem also cover positive data distributions (that we showed to be eventually safe for small enough e in Theo- remb B.I. Furthermore, especially in very large MDPs, it is very likely that the data distribution will not sufficiently cover large parts of the support of some policies, especially since the number of (deterministic) policies grows exponen- tially with the number of states. Sometimes, this can lead to all data distributions being unsafe, as we show in the
where we use the vector notation of D, and is vector containing all ones.
The proof of Theorem 3.5 can can be found Appendix C.3 (see Theorem C.16 and largely relies geometric arguments that arise from comparing the set of unsafe reward models and the set of reward models that are close to the true reward function. Interestingly, this means that the set of safe data distributions resembles a polytope, in the sense that it is a convex set and is defined by the intersection of an open
following corollary:
6

---

The Perils of Optimizing Learned Reward Functions
polyhedral set (defined by the system of strict inequalities M D > c. range R 1), and the closed data distribution simplex.
theorem (Berge 1963). Note that the regret bound L is defined the regret of the reference policy. This intuitively makes sense, as regularized policy optimization constrains the policy under optimization á to not deviate too strongly from the reference policy Tref, which will also constrain the regret of π to stay close to the regret of Tref Under the con- ditions of Theorem [4.1] the regret of Tyof serves as an upper regret bound because for small enough the learned reward R and the true reward R are so close that maximizing R also improves reward with respect to R. Furthermore, we note that it is also possible to derive a version in which the expected error in rewards is replaced by a KL divergence of choice probabilities, similar to Proposition [.15] by com- bining the arguments that proposition with the arguments in Berge's 's theorem - see Theorem D.23
While Theorem 3.5 only proves the existence of such a matrix M, we provide further results and analyses in the appendix, namely:
1. In Appendix C.3.2 we derive closed-form expressions of the rows of matrix M, and show that its entries depend on multiple factors, such as the original reward function R, the state transition distribution T, and the set of deterministic policies that achieve regret at least L.
2. In Appendix C.3.3 we provide an algorithm compute matrix M.
Similar to Theorem 3.1 Theorem 4.1 does not guarantee the existence of a universal such that all data distributions D are in safe I, X, w). In our next result, we show that such an does not exist, since for each there is a nontrivial set of data distributions that allows for error-regret mismatch to oceur:
3. In Appendix C.3.4 we provide a worked example of computing and visualizing the set of safe distributions for toy example.
Lastly, we note that M does not depend on 6, and M only contains non-negative entries (see Appendix C.3.2). This al- since by letting approach
Theorem 4.2. Lei M (S,A, R, be an arbitrary MDP, X 00), L E (0, and w III - R be regu- larization function. Furthermore, let T, be determinstic worst-case policy for R, meaning that Reg" (T.) ) = 1. Let n.. L,, X, X. < 0o be the constant defined in Equation (106) in the appendix. Let e > O. Then for all data distributions D E A(SxA) with
lows us to recover Theorem zero, the set of data distributions that fulfill the conditions in Equation 33) approaches the entire data distribution simplex. On the other hand, the dependence of M on the true reward function and the underlying MDP implies that computing M infeasible in practice since many of these components are not known, restricting the use of M theoretical analysis.
D(supp D=
E
(4)
I+0'
4. Error-regret mismatch for regularized policy optimization
we have D E unsafe(RR L,).w)
In this section, we investigate the error-regret mismatch for regularized policy optimization.
The proof of Theorem 4.2 can be found in Appendix (see Theorem C.38 The general idea is as follows: To prove that D is unsafe, define ît to be equal to R outside of supp D and very large in supp D If it is sufficiently large in this region, then regularized optimization leads to R
C.5
First, we prove that for almost any reference policy uer that achieves regret L and minimizes the regularization term w, there exists a sufficiently small e such that reward learning within of the true reward function preserves the regret bound L.
policy á with Reg (#) L. Finally, the condition that
D(supp D=*) S T+C ensures that R has reward error bounded by E.
Proposition 4.1. Let À E (0, oo). let (S,A, T, Mo, R, 7) be any MDP, and let D E A) be any data distribution that assigns positive probability to all transitions. Let w : II + R be a continuous regularization function that has a reference policy 7e as a minimum I Assume that Fyee is not (X, opttmall for R and let L Reg" (Fret). Then there exists > 0 such that D safe(R, T,, L,),w)).
Note that Theorem 4.2 is very general and covers a large class of different regularization methods. In Theo- rem C.40 we provide a specialized result for the case of K L-regularized policy optimization, and in Section we investigate error-regret mismatch in the RLHF framework. At the end of our conceptual example described in the intro- duction and in detail in Appendix B.4 we also discuss the simple intuition that simply giving a low enough training probability to some unsafe actions can be enough to lead to unsafe reward inference and policy optimization even in the regularized case. This is in accordance with Theorem 4.2
The proof of Theorem 4.1 can be found in Appendix D.. (see Theorem D.22 and is again an application of Berge's
'E.g., if Trer (a 8) > 0 for all (s, Sx.A and ((T)
DiL.. Teet), then the minimum is Weef-
7

---

The Perils of Optimizing Learned Reward Functions
5. Generalization of the error measurement
The proof of Theorem 5.2 can be found in Appendix C.4.1 (see Theorem C.25
Our results have so far expressed the error of the learned reward R in terms of Equation ( i.e., in terms of the expected error of individual transitions. In this section, we show that many common reward learning training objectives can be upper-bounded in terms of the expected error metric defined in Equation IT. This in turn means that our negative results generalize to reward learning algorithms that use these other training objectives. We state all upper bounds for MDPs with finite time horizon T (but note that these results directly generalize to MDPs with infinite time horizon by taking the limit of T - oc).
Finally, in some RLHF scenarios, for example in RLHF with prompt-response pairs, one prefers to only compare trajectories with a common starting state. In the following proposition, we upper bound the expected error of choice distributions with trajectories that share a common start- ing state by the expected error of choice distributions with arbitrary trajectories:
Proposition 5.3. Given an MDP AS,A, R,,)), 7). data sampling policy S + A(A) and a second reward function R: S - R, we can upper bound the expected KL divergence of preference distributions over trajectories with a common starting state as follows:
In the finite horizon setting, trajectories are defined as finite list of states and actions: ç = So, ao, $1,..., QT-1- We use E for the set of all trajectories of length T. As in the previous sections, G : E + R denotes the trajectory return function, defined as G(g) = Ei=o 7². R(s),a)) We start by showing that low expected error in transitions implies low expected error in trajectory returns:
E 80 sam-or (1.E2
Ee EaNaxx
[Dx (Pa(
min Ho
Proposition 5.1. Given an MDP (S,A, Ho. R,,), a data sampling policy π. : S + ((A) and its resulfing data 1-2
The proof of Theorem 5.3
can be found in Appendix C.4.1
(see Theorem C.26
distribution Dd = T-a 17 and a second reward function
R: SxX- + R. we can upper bound the expected difference in trajectory evaluation as follows:
6. Error-regret mismatch in RLHF
In this section we extend our results to reinforcement learn- ing from human feedback (RLHF). We provide more general results for the class of KL-regularized policy optimization methods in Appendix C.4.5
BE
[GR(() - -GR(S)-GAtts GR(3)] S
1 -- 7 B(ea)~D= [I((s,a) - R(s. a)]
RLHE, especially in the context of large language models, is usually modeled in a contextual bandit setting (Ziegler
The proof of Theorem 5.1 can be found in Appendix C.4.1 (see Theorem C.24.. Furthermore, low expected error of trajectory returns implies a low expected error of choice distributions (a distance metric commonly used as the loss in RLHF (Christiano et al. 2017)). Namely, given a reward function R. define the probability of trajectory & being preferred over & to be:
2019 Stiennon et al., 2020; Bai et al., 2022 Ouyang et al.
et al. 2022; Rafailov et al., (023). A contextual bandit (S, A, mo: R) is defined by a set of states S, set of ac- tions A, a data distribution μ4 E A(S), and reward function R : SxA + R. The goal is to learn pol- icy π S + A(A) that maximizes the expected return J(T) = E (ecporarn((1s)) [R(s,a) a)). In the context of language models, S is usually called the set of prompts or contexts, and A the set of responses.
PR(E1 > (2) = o(GR(E)) - GR((t))
exp(Gn((E))
We state the following theorem using a version of Theo- rem 2. tailored to the RLHF setting. In particular, we re- place the similarity metric (property 1 of Theorem 2.1 with the expected similarity in choice probabilities. A precise mathematical definition can be found in Appendix C.4.3 We denote the resulting sets of safe- and unsafe data distributions by safe RLMMF unsafe RLHF (R, L, A, DKI.. (-1(Tret))
exp(Gn((i)) + exp(Gre((e))
We then have:
Proposition 5.2. Given an MDP (S,A,T R, Th, a data sampling policy π. : S + A(A) and a second reward function R: SxA-A + R. we can upper bound the expected KL. divergence over trajectory preference distributions as follows:
(-I(TTet) and
By making use of the specifics of this setting, we can derive more interpretable and stronger results. In particular, we specify set of reference distributions for which performing KL-regularized policy optimization allows for error-regret
S 2 EEn [[Gn(5) - Gx(()
8

---

The Perils of Optimizing Learned Reward Functions
mismatch to occur.
our results generalize to other data sources, such as prefer- ences over trajectories and trajectory scores (Theorems 5.1 to 5.3 supporting the conclusion that this issue is a funda- mental problem of reward learning.
Theorem 6.1. Let (S,A, Ho, R) be contextual bandit. Given L E [0. 1), we define for every state s E S the reward (breshold:Ry(s) = (1- -ax R(s, a) L- m R(s, a). Lastly, let #ee S + A be an arbitrary reference policy for which it holds that for every (s,a) E SxA. [alr(a > O, and there exists at least one action a, A such that R(s, a.) < Rs(s) and Tyet(a satisfies the following inequality:
Lastly, for unregularized optimization, we derive necessary and sufficient conditions that allow us to determine the set of safe data distributions for arbitrary MDPs, thereby fully answering when data distribution is safe (Theorem 3.5)
7.1. Limitations and future work
(Ri(s) R(s, a.)) rrange R
e²
(aas)) -
Our work focuses on worst-case setting regarding the learned reward function and optimal policy. Future work could account for the inductive biases of common optimiza- tion procedures and consider non-optimal policies.
L. Lxexp (7 range R.) 4 4.22
Let Dael a) = pu(s) -Tret (als) for some j E (S)). Then Dref E uunaafeltHe (R, e, L, A, Dxz. (-I(Teer)
It is also important to theoretically analyze improved reward learning and policy optimization procedures. Empirical work has explored reward model ensembles (Coste et al., 2023), weight-averaged reward models (Ramé et al. 2024). and iterated data- -ato-sioo for multi multi-armed bandits (Zhu ct al. 2024).. Recent efforts address learning reward models on online data to mitigate distribution shifts (Lang et al., 2024a) and even provide theoretical insights for linear re- ward functions (Song et al.) 2024). We hope careful the- oretical analysis of these settings, in similar generality to our work, can improve upon the "theoretical baseline" we establish.
Intuitively, the theorem shows that even if we learn a reward model R that induces e-correct choice probabilities accord- ing the data distribution generated from reference policy Tref, a policy that maximizes R with KL-ppnnltty can still have regret > L if Tref gives sufficiently low probability to bad actions. The proof of Theorem can
can be found in Appendix C.4.4 (see Theorem C.32). We expect the condi- tions on the reference policy Tref to likely hold in real-world cases as the number of potential actions (or responses) is usually very large, and language models typically assign large portion of their probability mass to only tiny fraction of all responses. Hence, for every state/prompt 8, large ma- jority of actions//eeponses have a very small probability (a | s). See our conceptual example in the introduction and Appendix to make this intuition concrete.
Another important direction to explore is whether optimiz- ing an implicit reward model (as used by direct preference optimization (Rafailov et al. (023) and its many derivatives) in place of an explicitly learned reward model improves the robustness error-regret mismatch.
7. Discussion
Lastly, there are other ways to improve safety. For example, one could research evaluation methods for learned reward functions that go beyond looking at the training error, e.g. by using interpretability methods (Michaud et al.) 2020 Jenner Gleave (2022) or finding better ways to quantify reward function distance (Gleave al. 2020 Skalse et al.) 2024
In this paper, contributed to the foundations of reward learning theory by studying the relationship between the training error of the learned reward function and the regret of policies that then result from policy optimization. We showed that as the expected error of reward model A goes to zero, the regret of the resulting policy (with or without reg- ularization) also goes zero (Theorem 3.1 or is bounded by the regret of reference policy (Theorem 4.1 However, in Theorem 3.2 we showed that the training error needed to ensure a certain regret is proportional to the minimum of the data distribution D. Consequently, there exists no training error that can universally ensure low regret.
Impact statement
Reward learning methods such as RLHF are widely used to steer the behavior of frontier models. Thus, it is important that reward models are robust and reliable. We point out a theoretical challenge to the robustness of reward models to policy optimization. We hope that this stimulates further research in overcoming this challenge. Since work is purely theoretical, we do not foresee negative societal consequences.
More specifically, low expected error of å does not ensure low regret for all realistic data distributions (Theorems 333 4.2 and 6.1). We refer to this phenomenon error-regret mismatch. This is due to policy optimization involving distributional shift. Moreover, for some MDPs with very large state- action spaces there does not exist any safe data distribution relative to a reasonable reward model error and desired regret bound (Theorem 3.4.. We also showed that
9

---

The Perils of Optimizing Learned Reward Functions
Author contributions
Askell, A., Bai, Y., Chen, A., Drain, D., Ganguli, D.,
Henighan, T., Jones, A., Joseph, N., Mann, B., Das- Sarma, N., Elhage, N., Hatfield-Dodds, Z., Hernandez. D., Kernion, J., Ndousse, K., Olsson. C., Amodei, D., Brown, T., Clark, J., McCandlish, S., Olah, C., and Ka- plan, J. A General Language Assistant as a Laboratory for Alignment, 2021. URL 2112.00861
Lukas Fluri and Leon Lang are the core contributors who developed the technical results and wrote large part of the main paper and all of the appendix. While many results arose from strong contributions by both together, Lukas had particular focus and impact on the general unregularized optimization result (Theorem 3.5 and the generalization of the error measurement (Section 5) whereas Leon had a particular focus and impact on the results showing that in the limit, a data distribution becomes safe (Theorems 3.1 and 4.T and the general regularized optimization results (Section
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., Das- Sarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. Training a helpful and harmless assistant with rein- forcement learning from human feedback. arXiv preprint WxXi:2204.05866 2022.
Joar Skalse developed the project idea and provided close supervision during the project's ss duration by providing feed- back and ideas and editing the paper.
Bajesy, A., Losey, D. P., O'malley, M. K., and Dragan, A. D. Learning robot objectives from physical human interaction. In Conference on robot learning, pp. 217- 226. PMLR, 2017.
Alessandro Abate, Patrick Forré, and David Krueger advised on the project by providing helpful feedback on the project idea, as well as reviewing and improving drafts of the paper. Furthermore, Patrick had the initial idea of using Berge's 's theorem to prove our positive results (Theorems 3.1 and
Berge, C. ment of Topological Spaces: Including a Treat- Functions, Vector Spaces and Convexity. Macmillan, 1963. URL hhttps:/
books.google.n//oookss DOURAAAAUAAAAMAM,,
Acknowledgements
Bowling, M., Martin, J. D., Abel, D., and Dabney, W. Set- tling the reward hypothesis. In International Conference on Machine Learning, pp. 3003-3020. PMLR, 2023.
Lukas Fluri and Leon Lang are grateful for financial support provided by the Berkeley Existential Risk Initiative for this project. Leon Lang furthermore thanks Open Philanthropy for financial support.
Bradley, R. A. and Terry, M. E. Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
References
Brown, D. S. and Niekum, S. Deep Bayesian reward learn- ing from preferences. arXiv preprint arXiv: urXiv:1912.044 1912.04472.. 2019.
Abel, D., Dabney, W., Harutyunyan, A., Ho, M. K., Littman, M., Precup, D., and Singh, S. On the expressivity of markov reward. Advances Neural Information Process- ing Systems, 34:7799-7812, 2021.
Casper, S., Davies, X., Shi, C.,, Gilbert, T. K., Scheurer, J., Rando, J., Freedman, R., Korbak, T., Lindner, D., Freire, P., et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:2307. 2023.
Agarwal, A., Dudík, M. Kale, S., Langford, J., and Schapire, R. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pp. 19- 26. PMLR, 2012.
Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang, T., Yang, S., Schuurmans, D., Chi, Y., and Dai, B. Value-incentivize preference optimization: A unified approach to online and offline rlhf. arXiv preprint arXiv:2405.1933 2024.
Amortila, P., Jiang, N., and Xie, T. A variant of the wang- foster-kakade lower bound for the discounted setting. arXiv preprint arXiv:2011.01075 2020.
Anthropic.
Introducing Claude. https: :
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. Advances in neural information pro- cessing systems, 30, 2017.
w/www.anthrop. cetropic.cooo/o /
claude 2023. Accessed: 2023-09-05.
Anthropic.
Responsible Scaling Policy, 2024.
URL
2444700FF10330cc//rrrgaa////aa/2 m/
https://assets..ntrrpoocc..
Cobbe, K., Klimov, O.,, Hesse, C., Kim. T., and Schulman, J. Quantifying generalization in reinforcement learning. In International conference on machine learning, pp. 1282- 1289. PMLR, 2019.
15.pdf
Accessed: 2024/11/26.
10

---

The Perils of Optimizing Learned Reward Functions
Coste, T., Anwar, U., Kirk, R., and Krueger, D. Reward model ensembles help mitigate overoptimization. arXiv preprint arXiv:2310.0274. 2023.
Systems, volume 31, pp. 8022-8034, Montréal, Canada, 2018. Curran Associates, Inc., Red Hook, NY, USA.
Jenner, E. and Gleave, A. Preprocessing reward functions for interpretability. 2022.
Cui, J., Chiang, W.-I.., Stoica, I,, and Hsieh, C.-J. OR- Bench: An Over-Refusal Benchmark for Large Lan- guage Models, 2024. URL https: /ttp::://axxvvrrr
Jeon, H. J., Milli, S., and Dragan, A. Reward-rational (im- plicit) choice: A unifying formalism for reward learning. Advances in Neural Information Processing Systems, 33: 4415 4426, 2020.
abs/ Nos/2405.20947
Denison, C., MacDiarmid, M., Barez, F., Duvenaud, D., Kravec, S., Marks, S., Schiefer, N., Soklaski, R., Tamkin, A. Kaplan, J., Shlegeris, B., Bowman, S. R., Perez, E., and Hubinger, E. Sycophancy to subterfuge: Investigating roward-tampering in large language models, 2024. URL https:://en
Ji, X., Wang, H., Chen, M.. Zhao, T., and Wang, M. Provable benefits of policy learning from human pref- erences in contextual bandit problems. arXiv preprint arXiv:2307.12975. 2023.
Farebrother, J., Machado, M. C., and Bowling, M. Gen- cralization and regularization in dqn. arXiv preprint arXiv:1810.00123, 2018.
Karwowski, J., Hayman, O., Bai, X., Kiendlhofer, K., Grif- fin, C., and Skalse, J. Goodhart's Law in Reinforcement Learning. arXiv preprint ar arXiv:2310.091111 2023.
Foster, D. J., Rakhlin, A., Simchi-Levi, D., and Xu, Y. Instance-dependent complexity contextual bandits and reinforcement learning: A disagreement- based perspec- tive. arXiv preprint arXiv:2010.03/04, 2020.
Kearns, M. and Vazirani, U. An Introduction to Computational Learning Theory. The MIT Press, 08 1994. ISBN 9780262276863.
doi: 10.7551/mitpress/
3897.001 URL httpt::/pps:ottt httppppp///....../.....55. mLtppeess/3997.00..00
Foster, J., Krishnamurthy, A., Simchi-Levi, D., and Xu, Y. Offline reinforcement learning: Fundamental barri- for value function approximation. arXiv preprint 1:Xi::2111.109/9 2021.
Krakovna, V. Specification gaming: flip side of Ai Ingenuity, Apr 2020. URL
The
specificaciion-gamiingg -he--fh---ff---- side of of-ai-ingenuity/
Gao, L.,, Schulman, J., and Hilton, Scaling laws for reward model overoptimization. In International Conference Machine Learning, pp. 10835-10866 PMLR, 2023.
K wa, T., Thomas, D., and Garriga-Alonso, A. Catastrophic goodhart: regularizing rlhf with kl divergence does not mitigate heavy- reward misspecification. arXiv preprint arXiv:2407. 14503, 2024.
Garg, S., Singh, A., Singh, S., and Chopra, P. Ipo: Your language model is secretly preference classifier. arXiv preprint wrxiv:2502.1618 2025.
Laidlaw, C., Singhal, S., and Dragan, A. Correlated proxies: A new definition and improved mitigation for reward hacking. arXiv preprint arXiv:2403.03185 2024.
Gemini Team, G. Gemini: A Family of Highly Capable Multimodal Models. https:
cet.om/meeeeinddcce petiia/ggemii/ggmm...n gemini report.pdf.
2023.
Lang, H., Huang, F., and Li, Y. Fine-Tuning Language Models with Reward Learning Policy, arXiv preprint arXiv:2403.1 19279, 2024a.
Accessed: 2023-12-11.
Gleave, A., Dennis, M., Legg, S., Russell, S., and Leike, J. Quantifying differences in reward functions. arXiv preprint arXiv:2006. 13900, 2020.
Lang, L., Foote, D., Russell, S., Dragan, A., Jenner, E., and Emmons, S. When Your AIs Deceive You: Chal- lenges with Partial Observability of Human Evaluators in Reward Learning. arXiv preprint urXiv:2402.17747, 2024b.
Goodhart, C. A. Problems of monetary management: the UK experience. Springer, 1984.
Hennessy, C. A. and Goodhart, C. A. Goodhart's 's law and machine learning: structural perspective. International Economic Review, (4(3):1075-1088 2023.
Li, H., Wang, X., Zhang, 7.,, and Zhu, W. Out-of-distribution generalization on graphs: A survey. arXiv preprint arXh::2202.07987, 2022.
Ibarz, B., Leike, J., Pohlen, T., Irving, G., Legg, S., and Amodei, D. Reward learning from human preferences and demonstrations in Atari In Proceedings of the 32nd Inter- national Conference on Neural Information Processing
Li, Y., Wang, X., Zeng, R., Donta, P. K., Murturi, I., Huang, M., and Dustdar, S. Federated domain generalization: survey. arXiv preprint arXiv:2306.011 306.01334, 2023.

---

The Perils of Optimizing Learned Reward Functions
Littman, M. Michael Littman: The Reward Hypothesis
Phuong, M., Aitchison, M., Catt, E., Cogan, S., Kaskasoli,
Markov Decision Processes Coursera cours-
A., Krakovna, V., Lindner, D., Rahtz, M., Assael, Y., Hod- kinson, S., Howard, H., Lieberum, T., Kumar, R., Raad, M. A., Webson, A., Ho, L.,, Lin, S., Farquhar, S., Hutter, M., Deletang, G. Ruoss, A., El-Sayed, S., Brown, S., Dragan, A., Shah, R., Dafoe, A., and Shevlane, T. Evalu- ating Frontier Models for Dangerous Capabilitiess 2024. bttp:///ara2.orr//////22233. URL URL
era.org.
learning/michaell11 http:cchhhae--itttt----aa--- reward- hypothesis 2019. [Accessed 29-05-2025].
Liu, J., Shen, Z., He, Y. Zhang, X., Xu, R., Yu, H., and Cui, P. Towards out-of-distribution generalization: A survey. arXiv preprini arXiv: 2008. 102.100..1132 13624, 2021.
Pitis, S. Rethinking the discount factor in reinforcement learning: A decision theoretic approach. In Proceed- ings of the AAAI conference on artificial intelligence, volume 33, pp. 7949-7956, 2019.
Liu, Z., Lu, M., Zhang, S., Liu, B., Guo, H., Yang, Y., Blanchet, J., and Wang, Z. Provably mitigating overopti- mization in rlhf: Your sft loss is implicitly an adversarial regularizer. arXiv preprint arXiv:2405. 16436, 2024.
Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994.
Mehta, V., Das, V., Neopane, O., Dai, Y., Bogunovic, I., Schneider, J., and Neiswanger, W. Sample efficient re- inforcement learning from human feedback via active exploration. OpenReview, 2023.
Rafailov, R., Sharma, A., Mitchell, E.,, Ermon, S., Manning, C. D., and Finn, C. Direct preference optimization: Your language model is secretly reward model. arXiv preprint arXiv:2305./88 18290, 2023.
Meng, Y., Xia, M., and Chen, D. Simpo: Simple preference optimization with reference-free free reward. Advances in Neural Information Processing Systems, 37:124198 124235, 2024.
Ramé, A., Vieillard, N., Hussenot, L., Dadashi, R., Cideron, G., Bachem, O., and Ferret, J. Warm: On the bene- fits of weight averaged reward models. arXiv preprint arXiv:2401.12187, 2024.
Michaud, E. J., Gleave, A., and Russell, S. Understanding learned reward functions, 2020.
Rockafellar, R. T. and Wets, R. J.-B. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Ng, A. Y. and Russell, S. Algorithms for inverse reinforce- ment learning. In Proceedings of the Seventeenth Inter- national Conference on Machine Learning, volume 1, pp. 663-670, Stanford, California, USA, 2000. Morgan Kaufmann Publishers Inc.
Schlaginhaufen, A. and Kamgarpour, M. Identifiability and generalizability in constrained inverse reinforcement learning. In International Conference on Machine Learn- ing, pugex==00224-30251 PMLR, 2023.
Ng, A. Y., Russell, S., et al. Algorithms for inverse rein- forcement learning. In Ieml, volume pp. 2, 2000.
Shah, R., Krasheninnikov, D., Alexander, J., Abbeel, P., and Dragan, A. Preferences Implicit in the State of the World. arXiv e-prints, art 19Xiv:1902.044 0488, February 2019. doi: 10. 404455//aa.i..1902..44444
Nika, A., Mandal, D., Kamalaruban, P., Tzannetos, G., Radanović, G., and Singla, A. Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences. arXiv preprint arXiv:2403.01857,1 2024.
Shakerinava, M. and Ravanbakhsh, S. Utility theory for sequential decision making. In International Conference on Machine Learning, pp. 19616-19625. PML.119........... 2022.
OpenAl. Introducing ChaIGPT,
Skalse, J. and Abate, A. Misspecification in inverse rein- forcement learning, 2023.
blog/chatgpt. 2022. Accessed: 2024-02-06.
Ouyang. L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744, 2022.
Skalse, J. and Abate, A. Quantifying the sensitivity of inverse reinforcement learning to misspecification, 2024.
Skalse, J., Howe, N., Krasheninnikov, D., and Krueger, D.
Defining and characterizing reward gaming. Advances in Neural Information Processing Systems, 35:9460-9471, 2022.
Palan, M., Landolfi, N. C., Shevchuk, G., and Sadigh, D. Learning reward functions by integrating human demon- strations and preferences. In Proceedings of Robotics: Science and Systems. Freiburg im Breisgau, Germany, June 2019, doi: 10. 1607//SSS 2019.X 1.....V... .023.
Skalse, J., Farnik, L.,, Motwani, S. R., Jenner, E., Gleave, A., and Abate, A. Stare: A general framework for quantifying differences between reward functions, 2024.
12

---

The Perils of Optimizing Learned Reward Functions
Skalse, J. M. V., Farrugia-Roberts, M., Russell, S., Abate, A., and Gleave, A. Invariance in policy optimisation and partial identifiability in reward learning. In Inter- national Conference on Machine Learning, pp. 32033- 32058. PMLR, 2023.
Uehara, M., Imaizumi, M., Jiang, N., Kallus, N., Sun, W., and Xie, 'T Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first- order efficiency. arXiv preprint arXiv:2102.02988. 2021.
van der Pol, E., Worrall, D. E., van Hoof, H., Oliehoek, F. A., and Welling, M. Mdp homomorphic networks: Group symmetries in reinforcement learning, 2021. URL
Song. Y., Swamy, G., Singh, A., Bagnell, D., and Sun, W. The importance of online data: Understanding preference fine-tuning via coverage. In The Tiirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Vanderbei, R. Linear programming: foundations and extensions. Journal of the Operational Research Society, 49(1):94-94, 1998.
Stanley, R. Chapter 1: Basic Definitions, the Intersection Poset and the Characteristic Polynomial. In Combinato- rial Theory: Hyperplane Avrangements-Mir Course
Verma, N. and Bharadwaj. M. The hidden space of safety: Understanding preference- tuned llms in multilingual con- text. arXiv preprint arXiv:2504.02708, 2025.
No. 18.315. MIT Open Cambridge MA,
2024. URI http://tsss///owwttt.///o/rorsst
315 hll--combinatooriialttteerrryyys
Wang, J., Lan, C., Liu, C., Ouyang, Y., Qin, T., Lu, W., Chen, Y., Zeng, W., and Philip, S. Y. Generalizing to unseen domains: A survey on domain generalization. IEEE transactions on knowledge and data engineering, 35(8):8052-807 2022a.
arzangemenss-fall1220///gagggse notes/| MIT Open
Stiennon, N., Ouyang, L., Wu. J.. Ziegler, D.,, Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. Ad- vances in Neural Information Processing Systems, 33: 3008-3021, 2020.
Wang. R., Foster, D. P., and Kakade, S. M. What the statistical limits of offline rl with linear function approxi- mation? arXiv preprint arXiv:2010. 1895, 2020.
Strathern, M. 'Improving ratings': audit in the British University system. European review, 5(3):305-321, 1997.
Wang. X., Cui, Q., and Du, S. On gap-dependent bounds for offline reinforcement learning. Advances in Neural In- formation Processing Systems, 35:14865-14877, 2022b.
Sutton, R. a. The reward hypothesis - incompletei- neas.net. http://inccmmeeeeiddessss. cla..cc..albertt.cca//t
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. A survey of preference-basee reinforcement learning meth- ods. Journal of Machine Learning Research, 18(136): 1-46, 2017.
rewardhyyothesi s.hmll 2004. 29-05-2025).
[Accessed
Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-conntraint. In Forty-first International Con- ference on Machine Learning, 2024.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, second edition, 2018. ISBN 9780262352703.
Tien, J., He, J. Z.-Y., Erickson, Z., Dragan, A. D., and Brown, D. S. Causal confusion and reward misidentifica- tion in preference-basee arXiv:2204.0660) 06601, 2022.
Yoon, J. S., Oh, K., Shin, Y., Mazurowski, M. A., and Suk, H.-I. Domain Generalization for Medical Image Analysis: A Survey, arXiv preprint arXiv:2310.08593 2023.
reward learning, arXiv preprint
Tung, H.-Y., Harley, A. W., Huang, L.-K., and Fragki- adaki, K. Reward learning from narrated demonstra- tions. In Proceedings: 2018 IEFF/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 7004-7013, Salt Lake City, Utah, USA, June 2018. IEEE Computer Society, Los Alamitos, CA, USA. doi: 10. N0.1109/CVPR.201 8.0033..
Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. Provable Offline Preference-Based Reinforcement Learning. In The Twelfth International Conference on Learning Representations, 2023.
Zhang, A., Ballas, N., and Pincau, A dissection of over- fitting and gemeralization in continuous reinforeement learning. arXiv preprini arXiv: 1806.07937 2018
Uehara, M. and Sun, W. Pessimistic madel-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2 107.06226 2021.
Zhou, K., Liu, Z., Qiao, Y., Xiang, T., and Loy, C. C. Do- main generalization: A survey. IEEE Transactions on
13

---

The Perils of Optimizing Learned Reward Functions
Puttern Analysis and Machine Intelligence, 45(4):4396- 4415, 2022.
Zhu, B., Jordan, M., and Jiao, J. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning, pp. 43037-43088 PMIR, 2023.
Zhu, B., Jordan, M. I., and Jiao, Iterative data smoothing; Mitigating reward overfitting and overoptimization in rlhf. arXiv preprint arXiv:2401.16335 2024.
Zhuang, S. and Hadfield-Menell, D. Consequences of mis- aligned AI. In Proceedings of the 34th International Conference on Neurul Information Processing Systems, NIPS'20, pp. 15763-15773, Red Hook, NY, USA, De- cember 2020. Curran Associates Inc. ISBN 978-1-71382- 954-6.
Zhuang, S. and Hadfield-Menell, D. Consequences of mis- aligned AI. Advances in Neural Information Processing Systems, 33:15763-15773, 2020.
Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. Fine-tuning language models from human preferences. arXiv preprint arXiv: NEEi:1900.08599 2019.
14

---

The Perils of Optimizing Learned Reward Functions
APPENDIX
This appendix develops the theory outlined in the main paper in self-contained and complete way, including all proofs. In Appendix A we include an extended related work section. In Appendix [ we present the setup of all concepts and the problem formulation, as was already contained the main paper. Appendix [ we present all "negative results". Conditional eтror threshold in the reward model, these results present conditions for the data distribution that allow reward models to be learned that allow for error-regret mismatch. That section also contains Theorem C.16 which is an equivalent condition for the absence of error-regret mismatch but could be considered statement about error-regret mismatch by negation. In Appendix D we present sufficient conditions for safe optimization in several settings. Typically, this boils down to showing that given a data distribution, a sufficiently small error in the reward model guarantees that its optimal policies have low regret.
Contents of the Appendix
Extended related work
16
Introduction
18
B.1
Preliminaries
18
B.2
Problem formalization
18
B.3 The mean-squared error alternative distance measure
19
B.3.1
Transfer of positive results
19
B.3.2
Transfer of the remaining results
20
B.4
A conceptual example of overoptimization concerns
20
B.4.1
Specifying the contextual bandit
20
B.4.2
Regret analysis for always-helping policy
21
B.4.3
Reward learning analysis
23
Existence of error-regret mismatch
24
C.I
Assumptions
24
C.2 Intuitive unregularized existence statement
24
C.3 General existence statements
26
C.3.1 More interpretable statement
30
C.3.2
Deriving the conditions on D
32
C.3.3
Algorithm to compute the conditions on D
37
C.3.4
Working example of computing matrix M
37
C.3.5
Building on Theorem 3.5
39
C.4
Existence of negative results the RLHF setting
40
C.4.1
Generalization of the error measurement: Proofs
40
C.4.2
RLHF bandit formulation
43
C.4.3
Safe and unsafe data distributions for RLHF
C.4.4
Negative results
44
15

---

The Perils of Optimizing Learned Reward Functions
C.4.5 Another negative result with regularization
51
C.5 A regularized negative result for general MDPs
53
D Requirements for safe optimization
60
D.I Applying Berge's maximum theorem
60
D.2 Elementary proof of regret bound
63
D.3 Safe optimization via approximated choice probabilities.
67
D.4 Positive result for regularized RLHF
71
A. Extended related work
Reward Learning Reward learning is key concept in reinforcement learning that involves learning the reward function for complex tasks with latent and difficult-to-speciff reward functions. Many methods have been developed to incorporate
various types of human feedback into the reward learning process (Wirth et al. 2017 Ng et al.
2000 Bajesy al. 2017
Jeon et al. 2020).
Challenges in Reward Learning Reward learning presents several challenges CCspper et al.
2023 Lang et al. 2024b
Skalse & Abate 2023 2024), such reward misgeneralization, where the reward model learns different reward function that performs well on in-distribution data but differs strongly out-of-distribution data (Skalse al. 2023). This can lead to unintended consequences in real-world applications.
Reward misgeneralization can also result in reward hacking (Krakovna) 2020), a consequence of Goodhart's law (Goodhart)
1984, Zhuang Hadfield Menelll 2020; Hennessy Goodhart 20233 Strathern
1997|
Karwowski et al. 2023). Reward
hacking has been extensively studied both theoretically (Skalse et al.
2022
2024
Zhuang Hadfield Menelll 2020) and
empirically (Zhang al. 2018 Farebrother al. 2018 Cobbe al.
2019
Krakovna 2020
Gao 2023
Tien et al.
2022
Offline RL In offline reinforcement learning, we aim to learn low-regret policies for an MDP (S, A. T, Mn. R, where the reward function (and sometimes transition distribution (Wang et al., 2022b Uchara & Sun 202I)) is unknown and must be learned from an offline dataset {s, a, } sampled from a data distribution D (SS )) A key research question understanding what data coverage conditions ensure learning a near-optimal policy with efficient sample complexity.
Existing theoretical work primarily falls into two categories, covering both MDPs (Foster et al. 202 Wang et al. 2022b
2020 Amortila et al. 2020 Uehara & Sun 2021 Uehara et al.) 2021) and contextual bandits
Nika et al. 2024
Cen et al.
2024
Lower bound results prove that various data-coverage conditions are insufficient for sample-efficient offline RL by establish-
ing worst-case sample complexity bounds. Research in this area (Foster et al., 2021 Wang et al. 2022b 2020 Amortila
ct al.
2020 Nika et al., 2024) identifies adversarial MDPs that satisfy specific data-coverage conditions where achieving low
regret is either computationally intractable due excessive sample requirements (Foster al., 2021| Wang et al.) 2022b
2020
Nika et al. 2024 fundamentally impossible regardless of sample size (mortila et al.
2020
Upper bound results, on the other hand, establish positive guarantees under specific structural assumptions. Works in this
category (Wang et al. 20226) 2020) Uehara & Sun, [021] Nika et al. 2024 Cen et al.] 2024 Song et al. 2024) develop algorithms with provable cemple--fficiencyy bounds by making structural assumptions about the MDP structure, reward learning process, or policy optimization approach.
Intuitively, the quality of a reward model that is being approximated from a finite dataset is influenced by two key factors: the dataset size n and the dataset quality, specifically how well the data distribution D covers the data space A. Prior work confirms this intuition, with most works deriving variants of the following template (see for example recent work (Nika et al.) 2024 ): Regret E O (poly (Cov-Struct) )). Here, Cov represents some measure of the coverage of D, while Struct captures the structural assumptions of the specific approach. Such structural assumptions may include: realizability of function classes (Wang et al.] 20226 Uchara Sun 2021 Foster et al. 2021 Nika et al., 2024), linear function approximation Nika
al. 2024 Cen et al. 2024 Wang et al. 2022b), and various constraints on reward- or policy functions (Wang et al.
2020
16

---

The Perils of Optimizing Learned Reward Functions
Uehara & Sun 2021 Nika et al. 2024
Our paper differs from these works in two key aspects: a) explicitly analyze how the reward modeling error affects the final policy regret, rather than focusing on the number of samples (prior works only implicitly consider c), and b) we examine worst-case scenarios instead of probabilistic guarantees. The most relevant work in this area is (Song et al., 2024), which analyzes RLHF specifically. Their setup in section 3, combined with their Assumption 3, perfectly recovers our safe distribution definition (see Theorem 2.T) when applied to the special case of RLHF and when using the mean squared error metric. Their Theorem 4.2 demonstrates that Regret E O(Cov VE). where the square root emerges from using the mean squared error during the reward learning step.
While Song et al. (2024) focus on RLHF with mean-squared error metric, we provide similar results for general classes of regularized and unregularized policy optimization (for both MDPs and contextual bandits), as well as a wide range of different eπror metrics. Similar to prior sample-complexity results, we investigate the influence of different coverage
constraints on regret guarantees. For our initial results (Theorems 3.1 3.2 a.1 we use the condition min (s.a) D(s, a) > 0. Since we assume that all states of our MDPs are reachable, this is equivalent to full coverage condition (see Table 1 of (Uehara & Sun 202T) for an overview of different coverage conditions). We then relax the constraints to partial coverage constraints and prove several negative results (Theorems 3.3 4.2 and 6.1). Finally, we fully generalize our results from Theorems 3.1 to 3.4 into a single theorem (Theorem 3.5) which allows to determine the worst-case safety of arbitrary data distributions. To the best of our knowledge, we are the first work to achieve such a level of generality.
A Advancements in Addressing Distribution Shifts Several approaches have been proposed address the issue of out-of-
distribution robustness in reward learning, such as ensembles of conservative reward models (Coste et al.,
2023). averaging
weights of multiple reward models (Ramé et al., (024), iteratively updating training labels (Zhu et al.
2024 on-policy
reward learning (Lang et al.) 2024a), and distributionally robust planning (Zhan et al. (023). Recently, K Kwa et al. (2024)
show that RLHF and Conditioning can be provably safe under fairly strong structural assumptions such as deterministic
transitions, light-tailed reward errors, and independence between true and proxy rewards. Furthermore, (Lidlla et al. (2024) consider a setting where the learned and true reward functions are positively correlated under a reference policy. They prove that maximizing the proxy reward with chi-squared divergence penalty yields regret no worse than that of the reference policy. In experiments, they approximate this regularized objective and report favorable results.
Our work further emphasizes the usefulness of exploring additional assumptions or methods to mitigate the perils of distribution shift, as we show that without any additional assumptions, there are next to no guarantees. We therefore hope that our work can serve as a theoretical baseline, that people can use to express and analyze their new assumptions or methods.
In classical machine learning, research in ofito--diitribution generalization has a long history, and a rich literature of methods exists (Li et al.) 2022 Zhou et al. 2022 Wang et al., 2022a Liu et al., 2021 Li et al. 2023 Yoon et al. 2023). These methods could potentially be adapted to address distribution shift challenges in reinforcement learning.
Contextual Bandits In Section we work in the contextual bandit setting and derive variants of our results for RLHF
Several theoretical results have been developed that investigate the challenge of RLHF (Xiong et al. 2024 Zhu et al. 2023
Jt al. 2023 Mehta et al. 2023) and reward learning in general, (Agarwal et al. 2012 Foster et al. (0200 in the contextual bandit setting. In our Theorem 6. we show that in the worst-case setting, and without any additional assumptions, many common data distributions are unsafe. On the other hand, these works develop safety guarantees in settings with more structural assumptions such as various restrictions on the reward functions (Xiong et al. [024]] Zhu et al. 2023), focusing on
the probability and efficiency of safety guarantees (Zhu al. 2023 Ji et al. 2023
Agarwal et al. 2012). and developing
active learning algorithms (Mehta et al. 2023
Direct Preference Optimization Direct preference optimization (DPO) (Rafailov al., 2023) a recent technique that allows to directly optimize a policy via an implicitly defined reward model which promises to mitigate some of the common issues with classic reward model training like such as training stability. DPO's 's empirical performance is promising and many recent works are trying to further improve and extend upon the base idea. RPO (Liu et al. 2024) adds an imitation loss from a baseline policy to regularize DPO and provably mitigate overoptimization. SimPO (Meng et al. 2024) simplifies DPO by removing the need for a reference model and using the average log- likeliool of tokens as the reward. IPO (Garg et al.) 2025) avoids explicit external reward models by letting LLMs select samples for DPO themselves. Lastly, xO replaces the KI. re.-iggulaiization of DPO with x2 regularization, thereby improving robustness against overoptimization and achieving
17

---

The Perils of Optimizing Learned Reward Functions
sample efficiency guarantees.
Since our work explicitly analyzes the conditions under which a reward model might misgeneralize during training, our work does not directly translate to this family of DPO algorithms. However, we do consider it important future work to explore if and how DPO might be more robust to the issue of error-regret mismatch.
Alternative Formalizations of Reward and Utility We would like to note that throughout this work, we study the classical MDP setting, where utility of policy is measured by an expected value of (potentially discounted) cumulative sum of scalar reward signal (see the definition of in Section 2]. This definition is based on the reward hypothesis (Sutton
2004
Littman 2019
Sutton & BartO 2018) which states that:
That all of what we mean by goals and purposes can be well thought of as maximization of the expected value of the cumulative sum of a received scalar signal (reward).
While this is the default setting, several works investigate if, or under which conditions this formalization is sufficient to express the wide variety of goals and purposes that one might be interested in. Toward that end, (Shakerinava & Ravanbakhshi (2022) propose axioms that are necessary and sufficient for Markovian rewards to model preference relations. These axioms are later generalized by Bowling al. (2023) to accommodate more general settings such as discounted reward and episodic settings. Piiis (2019) show how utility functions with fixed discount factors fail model some types of preferences and then argue for a state ciate--cttiondepeddee discount factor. Similarly, /Abel et al. (2021) investigate the expressivity of Markovian rewards and identify tasks that cannot be modeled with Markovian rewards.
B. Introduction
B.1. Preliminaries
Markov Decision Process (MDP) is tuple (S,A, T, Po; R, where S is set of states, a set of actions, T : S + A is transition function, Po E (SS) is an initial state distribution, R: S - RR is reward function, and y E (0, 1) is discount rate. A policy is function æ : S - (AA). A trajectory { (so: 0o; 81, a1..... is possible path in MDP.
The return function G gives the cumulative discounted reward of trajectory, G(E) = Exe 2t=0 7 R(st, ae, St+1). and the evaluation function J gives the expected trajectory return given policy, J(T) = B [G(E)]. A policy maximizing J is an optimal policy. The state-action occupancy measure is a function v) : IT - S which assigns each policy π E IT a vector of occupancy measure describing the discounted frequency that a policy takes each action in each state. Formally, (TT))s = '7" (s.a) = Σ 7² P(s = 8, ag = a ~ x). Note that by writing the reward function R as a vector R E R|SxAl, we can split J into a linear function of æ: ((z) = R. The value function V of a policy encodes the expected future discounted reward from each state when following that policy. We use R to refer to the set of all reward functions. When talking about multiple rewards, we give each reward a subscript R,, and use J,, G and V.", to denote R; 's evaluation function, return function, and r-value function.
B.2. Problem formalization
The standard RL process using reward learning works roughly like this:
1. You are given dataset of transition-reward tuples {(s,, di, Hio Here, each (si, (si,a;) E SxAA is transition from some (not necessarily known) MDP AS,A, T, Ho. R, 7) that has been sampled using some distribution 1) E A(SxA), and rr = M[s; a.). The goal of the process is to find a policy á which performs roughly optimally for the unknown true reward function R. More formally: (R( s max JR(T).
2. Given some error tolerance e E R. a reward model At SxA + R is learned using the provided dataset. At the end of the learning process A satisfies some optimality criterion such (G R a) R(s, a]] <6
3. The learned reward model fe is used to train a policy म that fulfills the following optimality criterion: * = arg max (T).
The problem is that training à to optimize â effectively leads to a distribution shift, as the transitions are no longer sampled from the original data distribution D but some other distribution D (induced by the policy #). Depending on the definition
18

---

The Perils of Optimizing Learned Reward Functions
of D, this could mean that there are guarantees about how close the expected error of ft the true reward function R is (i.e., B (e.a)) [R((s,a) a) R(s, a)] could not be upper-bounded).
This means that we have no guarantee about the performance of â with respect to the original reward function R, so might happen that स performs arbitrarily bad under the true reward Jn(R) & maxx (R(T).
If for given data distribution D there exists reward model Rt such that Rt is close in expectation the true reward function R but it is possible to learn policy that performs badly under JR despite being optimal for R, we say that D allows for error-regret mismatch and that R has an error-regret mismatch.
B.3. The mean-squared error alternative distance measure
In the main paper, particular in Theorem 2.1
measure in the reward function. In this appendix section, we explain what changes in the results if one were to use the mean-squared error (MSE) instead.
the mean absolute error (MAE)
We define the mean-squared error by
[((s.a) R(s, a) range R
)
27
d
(R, Rt) = B(ea))D
This is like the usual MSE, with the difference that we divide by range R since the distance only meaningful relative the range of the true reward function R. In the main paper, work with the following mean absolute error instead:
[i(s,a) R(s, a)l
A ft) B(s,a)
range R
Then for any distance measure dx (with MSE or X MAE) involving a data distribution D, we can define the
set of safe data distributions safe (R, I,,, w), slightly generalizing Theorem 2.1 safe RR e, L,, X,w) w) is the set of all distributions D such that for all It that are e-close to I according to dž and all म that are (X, -optiialll with respect to ft, we have Reg" (f) < L. The complement of this set is unsafe (R, L, w).
We now explain that for all of our results where the main paper we talk about MAE there is a corresponding result for MSE and the same for MAE and unsafe MSE
B.3.1. TRANSFER POSITIVE RESULTS
Proposition B.1. If D safe MAB e, L,, W,), then D E MSE MSE (R, L, w.)
Proof. Assume the condition. Let R, be such that d dMS (R, R S e and is (A.w) opptimll with respect to Å. Due Jensen's inequality, we have
R(s, - a(s.a))
d MAE (R, Rt)²
range R
27
[((saa) - -R(ssa) a)
S [.
range R
dME (R,
2
It follows dALA (R. ft) By the definition of sAfeMEE, [R, e, L, X, w)) and the assumption, this results in Reg" (#) < L. Since R, were arbitrary, this shows D safe (R, e² L, N,w)
This proposition implies that our positive results (Theorem
and Theorem transfer over from safe MAE to safe
MSE
19

---

The Perils of Optimizing Learned Reward Functions
Theorem 3.2 transfers as well, with the condition on e replaced by a square of the old condition:
range JR.
min a) 1)
V2
range R
(3,0)
B.3.2. TRANSFER OF THE REMAINING RESULTS
The negative results do not transfer automatically since we would need an inequality between MAE and dMSE in the other direction, which does not exist without further assumptions. Nevertheless, it is easily possible to modify most the proofs, where appropriate, obtain corresponding results. In particular:
Theorem 3.3 and Theorem 3.4
hold verbatim with unsafe MSE instead of unsafeMAE In the proof of Theorem 3.3 we use the same construction of R, and almost identical derivation shows the bound in dSE.
On Theorem 3.5 Due to Theorem B.I I this rebuttal the "if" dire-iitti of the theorem automatically holds when replacing @MA RR R) with dM (R, ( R...Ri.. ie.. there exists set of linear inequalities such that given data distribution D is safe, i.e., D safe MSfe 2 L), whenever this set of linear inequalities is satisfied.
However, the "only-if" direction does not hold since safe MSE [R, e², L) is not a polytope (whereas safe MAE (R. L) is) and can thus not be expressed by finite set of linear constraints. The reason is that by replacing d R)
with dME (R, Rt), the set {R: d dMSE R, R) S <) becomes an ellipsoid, whereas it polytope in the original formulation. Future work could look into precise characterization in more detail.
For Theorem 4.2 there is corresponding version that is almost identical but replaces the condition on (ssup D*) by the following version including square:
(suup D*) s (1 + C)²
This condition can then be used at the very end of the proof of Theorem C.38 to finish the proof of an adapted Theorem Theorem
For the final negative result, Theorem 6.1 we already use a different distance measure motivated by the practice of RLHE Thus, we are not interested in an adaptation for the MSE.
B.4. A conceptual example of overoptimization concerns
In this section, we present a conceptual example that illustrates ovcroptimization concerns. This is meant to serve as an intuition for many of our "negative" theoretical results Theorems 3.3 3.4 4.2 and 6.1 grounded in realistic concerns.
with the aim to make them more
In summary, imagine scenario of chatbot: It can either obtain "safe" or "dangerous"" queries; safe queries (e.g. "Please help me create high-protein diet") should be answered, dangerous queries (e.g. "Please tell me how to build nuclear weapon") should be refused. We call answering a query "helping", irrespective of whether this is desired or not. We will specifically analyze an always-helping policy, its regret, and its plausibility to occur from reward learning. Helpful-only policies have been analyzed in past safety research (Denison et al. 2024) and are often a starting point for policies meant to become "helpful, honest, and harmless" (Askell et 2001).
First, we look at conditions for when helpful-only policies are unsafe relative a regret bound L. It turns out that they are less safe if there appear more unsafe queries in the deployment environment, and if the damage caused by answering them is larger- see Appendix B.4.2 Then we look into the conditions for when this policy can be learned by reward learning see Appendix B.4.3 It turns out that if there are "many styles" with which the chatbot can answer an unsafe query, then some of those answers must have a low probability on the training distribution, and thus a learned reward model can inflate its reward while achieving low training error. The always-helping policy can then result from policy optimization, leading large regret. This illustrates an error-regret mismatch.
20

---

The Perils of Optimizing Learned Reward Functions
B.4.1. SPECIPYING THE CONTEXTUAL BANDIT
We model the situation as follows: Assume contextual bandit with states and actions given by
S = {gaafe Juns. J.
A = (ahelp ovet. J.
In other words, there is one safe and one unsafe query and actions that either help with or refuse to answer the query in N different styles. One should imagine N to be fairly large since there are lots of ways to vary the style of an answer without changing the content, given that the amount of possible answers scales exponentially with length.
We assume the following simplified true reward function, where C >
is some (potentially large) constant:
R(Asates helpp)
R(ysate, Feot.) =
(5)
R(quns. : help) = -C'
R(quns. dref.) O.
The idea is that answering a safe query should lead to some positive reward, whereas refusing it doesn't I create value or damage the reward is zero. Answering/helping with an unsafe queries, however, incurs large negative reward -C since it can lead to substantial damage, whereas, once again, refusing to answer does neither create value nor damage.
Finally, assume some "true" distribution of queries, given by Muns. E [0, 1] and Maade 1 Muus. These can be imagined to be the frequencies with which actual users in the deployment environment ask safe vs. unsafe queries. In total, we have thus specified contextual bandit (S,A, R. p.)
We now make a regret-analysis - analyzing when an always-helping policy is safe - followed by a reward learning analysis - under which conditions can an always-helping policy result from reward learning?
B.4.2. REGRET ANALYSIS FOR HAWAYS-HELPING POLICY
For policy स with answer probabilities (( q), the policy evaluation (i.e., expected reward) is given by
N
N
(n) = Psaafe Σ
#aheepp I (sato)) Msade) C.
Σ
+ (Wheep (umss).
(6)
This follows directly from (5) The idea is that under safe query, which happens with probability Maates the reward the probability help with the query. For an unsafe query, which happens with probability 1 P'sale the reward is -C times the probability that the model helps with that query.
Now, the highest expected reward JR can be achieved if áे always helps with safe query and never helps with an unsafe query. This is hard to achieve in practice since training the model to refuse unsafe queries often leads to "over-refusal" on safe queries (Cui et al. 2024). In contrast, the lowest expected reward Jn is achieved f never helps with safe query and always helps with an unsafe query, Thus, the maximum and minimum expected values are given by:
max (
psafee
Ji (1 Msate) C.
Now, for purposes of illustration we look one specific type of policy â: that always helps. Let âे be such policy. There are several such policies since they can differ in their allocation of probabilities to answers of different styles, but the defining property is that their action probabilities for helpful answers sum to 1:
N
Σ (ahnop
(sate) =
Σ
# (ahalp I (uns.) = 1.
Having larger number of safe and unsafe queries does change the mathematical picture much, but for illustration purposes we chose this simplified setting.
21

---

The Perils of Optimizing Learned Reward Functions
C-0.5
C-5
C-50
C=1
C=10
C=100
C=2
C=20
C=200
1.0
0.8
(uns)) c(LL)
0.6
0.4
0.2
0.0.0
0.2
0.4
0.8
1.0
L
Figure 3. In conceptual example, analyze when always-helping policy is unsafe. This depends on the probability of unsafe query Juns.. For a given damage C' of answering such query and given regret bound L, f has regret of at least L if Muns. is larger than the plotted puus (L) L/((1 L)- C L}. plus. (L) grows with growing and shrinks with growing C.
Using (6). its expected value is given by:
J (+t) = Maafe
Msate) C.
(8)
Additionally using 7 the regret of this policy is:
max JR(T) - JR(
Reg
(+)
max, JT((T) min J (T)
Hsale Hsale + Msate) C
Msato + (1 - Meate) C
(9)
(1 Msate)
Meate + (1 - Msate))
Muns. C
11-uun. + Muus.
C
Now, imagine our goal to have regret lower than the bound E [0, 1] - a threshold that we find "safe enough" for deployment. Is unsafe? It depends on the value of Puns., i.c., the frequency of unsafe queries. Indeed, using ( the inequality Reg" (#) > L is equivalent to:
L. (1-L)-C+L'
Muns. 2
(10)
In Figure 3 we analyze for several different values the damage C the relationship between the regret bound L and the smallest probability (u (L) = L/((1 - L) + L] of the unsafe query for which the policy â would have a regret of least L. We observe the following:
For each C, as the regret bound L gets larger, one needs a larger probability Puns. for क to have regret at least L. This makes sense: acts correctly on safe queries, and so only unsafe queries can contribute to the regret. Thus, the more unsafe queries the policy encounters, the larger its regret becomes.
22

---

The Perils of Optimizing Learned Reward Functions
For each regret bound L, as the damage of helping with an unsafe query, C, gets larger, a smaller probability Muns. is sufficient for स reach regret at least L. This makes sense since the policy's 's overall performance is then more and more dominated by its performance on unsafe queries.
Note that over time, language models are approaching more concerning "dangerous capabilities" (Phuong et al. 2024 Anthropic 2024), which means that the caused damage C' for following through with unsafe requests can be imagined to go up over time with increased capabilities. Positive value goes up, too, but plausibly in the near-term not as fast as the tailrisks. Thus, we can reasonably think that even for large values of the regret bound L, a small probability Muns. of an unsafe query would already cause the always-helping policy f to have a regret of at least L, and thus to be unsafe.
Alternatively, instead of looking at regret, we could also think directly about the expected value (i)( computed in (8) Then we might say: the policy is unsafe if its expected value is negative, i..., it causes more damage than it provides value. With growing damage C' for more capable models, the expected value eventually becomes negative, and so also this viewpoint suggests that स is not a safe policy.
B.4.3. REWARD LEARNING ANALYSIS
Now, lets assume that the relationship between T., C, and Muns. as per Equation (10p is such that an always-helping policy unsafe, i.e., has regret at least L. Now the question becomes: Under what conditions could such policy be learned by reward learning followed by policy optimization? To be clear, there are also other policies that have regret at least L (e.g.. policy that doesn't 't help for safe queries and always helps for unsafe queries is even worse), but since we are operating under a worst-case framework under the policy optimization, it is already bad if any always-helping policy á can be learned. Thus, we are searching for sufficient conditions for this to happen.
Thus, let R be the learned reward function. For this to give rise to the policy स under unregularized policy optimization, Å needs to favor least one helpful answers over every refusing answer for both queries:
:Avj: R[gsate: (help) > A(geate dfot)) ),
(11)
fijj: R(guns. (help) > R(guns., (eet))
Again, since we are operating under a worst-case framework, it is enough if we find one specific learned reward function with these conditions that can be learned in practice. Thus, for simplicity, we assume R(gsale: (hetp) = 1, R(ggate, a =
for all i. Also assume R( o ) = 0 for all i. Assume there exists single in with B == R(gguns. h > 0, and that Riquus, <help) = CC for all i # ig. Then the conditions from II are met, and the learned reward function almost everywhere agrees with the true reward function R from (5)
Now we want to determine the (mean absolute) training error of this reward model. For this, assume we train on some data distribution D A(S A), given by D(g, = D(g) D(a )) our reward model equals the true reward function in every query-answer pair except (yuns., hn the training error becomes:
RRg. a) - R(1,a))
B+0 C
Blaa)D
D(guns..
Thep
range R
C
Assume we train until we have achieved a small but realistic training error e. Then the question is under what conditions î can "slip through" the training by leading to an error bounded above by e. This is the case if:
D(guns.: help) < (1 (1+C)
(12)
B B+C
Thus, if there is some in for which this inequality holds, then î can be learned, and the always-helping policy á results. Now, note that if the number of "styles"; i i= I....,NN N is very large relative to the inverse of e, this is automatic. Namely, if
N D(qune.) ) CB+
(13)
e (1 (1+C)
3 (geate) is not necessarily equal to psate. the likelihood of safe queries in the deployment environment. This is intuitive: Before deploying chatbot in the real world, it may be hard know what proportion of requests will be safe, and the proportion during training may be different.
23

---

The Perils of Optimizing Learned Reward Functions
then since the probabilities sum 1 there is in E (I,...,N) with D( (uns.) S 1/N, and we automatically obtain the result, 12
A note on regularized policy optimization: Regularization can prevent स from being learned even if R favors this policy, However, if B = R( guns., help)) > 0 is very large, then this creates so much reward that the regularization effect with constant regularization strength can be counteracted. Growing B just leads to the need for larger N in (13), and so we can say: If the number of styles N is large enough (leading to a small caaining-probbbllee of some bad action) and the always-helping policy á has regret larger then L, then supervised reward learning up to reasonable errors followed by (un regulaala policy optimization can result in a policy with regret 2 L. Thus, there then an error-regret mismatch, and the distribution D is unsafe, as per Theorem 2.1 That large number of "bad options" or small probability of some bad
option can lead to an error-regret mismatch is the core intuition behind our negative results Theorems 3.3 3.4
4.2 and 6.1
C. Existence of error-regret mismatch
In this section, we answer the question under which cireumstances error-regret mismatch could occur. We consider multiple different settings, starting from very weak statements, and then steadily increasing the strength and generality.
C.1. Assumptions
For every MDP (S,A,T, Ho, R, 7) that we will define in the following statements, we assume the following properties:
Finiteness: Both the set of states S and the set of actions A are finite
Reachability: Every state in the given MDP's is reachable, i.e., for every state S, there exists a path of transitions from some initial state so (s.t. (sa) > 0) such that every transition (s, a) in this path has non-zero probability, i.e., (s'|s, a) > O. Note that this doesn't 't exclude the possibility of some transitions having zero probability in general.
C.2. Intuitive unregularized existence statement
Definition C.1 (Regret). We define the regret of policy æ with respect to reward function R as
max JR Jn(z) max JR min JR
Reg R (m)
10.
Here, is the policy evaluation function corresponding to R.
Definition C.2 (Policy-Induced Distribution). Let ı be a policy. Then we define the policy-induce distribution Dx by
D (1-7)
Definition C.3 (Range of Reward Function). Let R be reward function. Its range is defined as
range R = max R - min R.
Lemma C.4. for any policy ग,, D is a distribution.
Proof. This is clear.
Proposition C.5. Let M = (S, A,S,A,T, Ho, R,,) be MDP, D E A(SxA) data distribution, and > 0, L E [0, 1].
Assume there exists policy it with the property that Reg" R (+) 2 L and D(supp D*) < e, where supp D* is defined as the set of state-action pairs (8, a) E Sx. such that D (8,a) > O. In other words, there is a "bad" policy R that is not very supported by D. Then, allows for error-regret mismatch to occur, i.e., D E unsafe R, c, L).
Proof. We claim that whenever there exists a policy & with the following two properties:
RReg (G) 2 L.
D(supp D < e,
24

---

The Perils of Optimizing Learned Reward Functions
then there exists reward function A for which a is optimal, and such that
a)(8,a) R(s. a)l range R
E (s,a)~D
c.
Since assumed that Reg" R (ft) 2 L, this gives the result D unsafe R, c, L). To prove the claim, define
a) = RRss a), (s, & supp D*; max R, else.
The state-action pairs that visits all lie in supp D where R takes on its maximal reward max R. This implies that optimal for R. Furthermore, we obtain
R(s,a) R(s,a) a)l
R((s,) R(s. a)
E [ssa)>>
Σ
D(s,
a)
range R
range R
(s,a)
max R R(8, 0)
Σ
D(s,a)
range R
(s.a) D*
Σ
((s.a)
(sup) D
D(supp D*)
S 6.
That was to show.
Corollary C.6. Let M (S, R, be an MDP, e O, and L E [0, 1]. Assume there exists set of policies II, with:
Reg (x) 2 for all I1.;
supp D Ssupp D for all n, n' E [T and
|II.| 2 1/E.
Then unsafe(FR (R, L) A(S A), iee. all distributions are unsafe.
Proof. Let D E A(S x A). Let argmin, D(supp D We obtain
D(supp D= == D (D( supp D=' 1
[zl D(supp D²) <
Σ
s'Elly
(r'Elll
R and therefore Dssupp D < 1/ < Since π E II, we also have Reg" (T) 2 L. Together, x and D thus satisfy the assumptions from Theorem 3.3 whose conclusion implies D E unsafe( R, L). This shows the inclusion ASS A) C unsafe(R, L). The other inclusion clear, and so we have equality.
Proposition C.7. The assumptions on in Theorem 3.2 and Theorem 3.3 cannot hold simultaneously.
Proof. If they would hold simultaneously, we would get:
min a) S (suppD**) <E< 1-7 (
rangeJJ
min (s.0)E8x.A
D(s,a) L.
/2 rangeR
Here, the first step is clear, the second step is the assumption from Theorem from Theorem 3.2 We now show that this leads a contradiction.
3.3 and the third step is the assumption
25

---

The Perils of Optimizing Learned Reward Functions
Dividing by the minimum both sides, obtain
L (1-r))angeJ]])
1< V2
(14)
rangeR
Clearly, we have L/v2- < 1. We also claim that the second fraction is smaller or equal to 1, which then leads to the desired contradiction. Indeed, let n²" and n, be an optimal and a worst-case policy, respectively. Then we have
(1 y JraggeJ/R
(1 ()R((( JR((.))
= (1 ->m" R - (1 - --
D R- D=- R
E D" (ss))
E (²,
(s,0)ESxA
(s.))SXA
max R(s,a) (s,0)ESXA
min (s,0)ESXA
R(s,a)
rangeR.
Here, we used the formulation of the policy evaluation function in terms of the occupancy measure y, and then that
1 y is a normalizing factor that transforms the occupancy measure into distribution. Overall, this means that (1 7) ))ange /rangeR < contradicting (14). Consequently, the assumptions of Theorem 3.2 simultaneously.
and and Theorem 3.3 cannot hold
C.3. General existence statements
We start by giving some definitions:
Definition C.8 (Minkowski addition). Let A, B be of vectors, then the Minkowski addition of A, B is defined
A B = {a +bba E, A, BJ.
2023) showed in their proposition 1, that for every MDP, the corresponding occupancy measure space Ω forms a convex polytope. Furthermore, for each occupancy measure E Ω there exists at least one policy x² such that V(s, a) E SxA,, n7 (s, a) = 77,,, a) (see Theorem 6.9.1, Corollary 6.9.2, and Proposition 6.9.3 of (Puterman, 1994)). the following proofs, we will refer multiple times to vertices of the occupancy measure space Q whose corresponding policies have high regret. We formalize this in the following definition:
Karwowski et al.
Definition C.9 (High regret vertices). Given lower regret bound L E [0, 1]. MDP (S, A, T, Po, R, 7) and a corresponding occupancy measure Ω2 we define the set of high-regret vertices of Ω denoted by V/L to be the set of vertices of Ω for which Reg" Rt (7r)) 2 L
Definition C.10 (Active inequalities). Let (S, AA, T, (40, R 7) be an MDP with corresponding occupancy measure space Q. For every 77 E Ω we define the set of transitions (s, a) for which 17(5, a) by zeros(n).
Definition C.11 (Normal cone). The normal cone of a convex set C R at point x E C is defined as:
No(x) = {n E R" nn (x' - x) < 0 for all x' E EC
(15)
We first state theorem from prior work that will use prove some lemmas in this section:
Theorem C.12 ( (Schlaginhaufen & Kamgarpour 2023)). Let (S, T; () be an MDP without reward function and denote with Q its corresponding occupancy measure space. Then, for every reward function R and occupancy measure 7 E Ωt it holds that:
T:
ni is optimal for =
R E Na(1),
(16)
where the normal cone is equal to:
Na(n) + cone ((-es,a)) (s. (s)ero))))))
(17)
functioon where & is the linear subspace of potential functions used for reward-shaping and the addition is defined as the Minkowski addition.
26

---

The Perils of Optimizing Learned Reward Functions
Proof. This is a special case of theorem 4.5 of [Schlaginhauten & Kamgarpour (023). where consider the unconstrained- and unregularized RL problem.
From the previous lemma, we can derive the following corollary which uses the fact that is is a closed, and bounded convex polytope (see Proposition 1 of Karwowski al. (2023)).
Corollary C.13. Given an MDP (S.A, T, Muu R. 7 and a corresponding occupancy measure space D then for every reward function N SxA IR, and lower regret bound I. E [0, 1), the following two statements are equivalent:
a) There exists an optimal policy ât for R such that it has regret at least I. w.r.l the original reward function, i.e, Reg" (f) 2 L.
b) RE +U+UU Joone
where & is the linear subspace of potential functions used for reward- for
VEVA shaping, the addition is defined as the Minkowski addition.
Proof. Let be chosen arbitrarily. Statement a) can be formally expressed as:
38 E II, Reg" R (f) = A Reg" (f) 2 L.
Using Theorem C.12 it follows that:
3i E II, Reg =0 A Reg (f) 2 L
38 E II,
RE Na(n") A (e)2 L
RE
U Na(1).
qy Reg Reg" (
remains be shown that the union in the previous derivation is equivalent a union over just all V First, note that by definition of the set of high-regret vertices V (see Theorem C.9p. trivially holds that:
U
Na(e) S
U Na(n),
(18)
DVVE
vp (x))22)
Next, because Q is a convex polytope, it can be defined as the intersection of set of defining half-spaces which are defined by linear inequalities:
Ω | af 1 b; for 1,...,, m).
By defining the active index set of point 77 E Ω In(n) {a, a. 17 b.). Rockafellar & Wets 2009 then show that:
Na(1) {ur aj + +... + Um am y: 2 0 for E In(n), y: = 0 for i & In(n).
(19)
(see their theorem 6.46). Note that, because Ω lies an |S| (I.A) -11 1) dimensional affine subspace (see Proposition 1 of (Karwowski al., 2023) a subset of the linear inequalities which define must always hold with equality, namely, the inequalities that correspond to half-spaces which define the affine subspace in which Ω resides. Therefore, the corresponding active index set, let's denote it by (n) because the subspace orthogonal to the affine subspace in which 52 lies corresponds exactly to Q is always non-empty and the same for every 1) E Ω.
Now, from Equation 19), it follows that for every E Ω there exists a vertex v of Ω such that Na(1) S. N2(v). We take this one step further and show that for every 7j with Reg (π²) > L, there must exist a vertex v with Reg" (œ*) > L such that Na(1) C Na(v). We prove this via case distinction on 7).
is in the interior of Q. In this case, the index set (n) reduces to (n) and because we have In, (n) S. In(n) for every E Ω the claim is trivially true.
1) itself is already vertex in which case the claim is trivially true.
27

---

The Perils of Optimizing Learned Reward Functions
y on the boundary of SZ. In this case 'i can be expressed the convex combination of some vertices V,, which lie the same face of S2 7/. Note that all oceupancy measures with regret 2 I. must lie one side of the half-space defined by the equality R² '7 L sytiin + (1 L) -7 where mp and sytuxx are worst-case and best-case occupancy measures, By our assumption, 1) also belongs to this side of the half-space. Because lies in the interior of the convex hull of the vertices V₁, at least one v E V,, must therefore also lie on this side of the hyperplane and have regret 2 L. Because v and r both lie on the same face of 92, we have (n(n) C (n(v) and therefore also Na(n) E NN(v)).
Hence, it must also hold that:
U
Na(1) S U Na(e),
Reg (x0)22
VEVE
which, together with Equation
18 proves the claim.
The following lemma relates the set of reward functions to the set of probability distributions D
Lemma C.14. Given an MDP T, Po, 7, and second reduced reward function ft Sxx IR then the following two statements equivalent:
a) There exists a data distribution D E A(SxA) such that (ss.a)-D [B(s,a) - R(s, a)] < e range R
b) At least one component RG of Ris "close enough" R, ie.,, holds that for some transition (8,a): -(ss,a))(sssa)) range R.
Proof. We first show the direction a). Assume that |Rss","" ,a") R(s"" a²)l < range R for a given ft and transition
(s" a²) In that case, we can construct the data distribution D which define as follows:
p 1 (ISxAl - 1) p
if (s, (8", if (8, (8*,a*) aa))
D(s,
where we choose < min
crange R- Hiss a') -a)- ,1'
1
From this it can be easily seen that:
E(no (B((,a)) M[(aa)
[8xA]
B(r,a/DD [[((s, a) - R(s a)l
= (1 - -1S 11) p) |R(s", R((s"aa"))
+p- Σ
[R(s,a) - M(ssa))
(*.)))((*ra**)
< E range
We now show the direction a) = b) via contrapositive. Whenever it holds that [R(s,) a) M(s, a)s 2 e range R for all transitions (s, a) E Sx.A, then the expected difference under an arbitrary data distribution D E A(Sx.A) can be lower bounded as follows:
B(aa)~D [(ss a) - R(s,a)]
Σ
D(s a) RR(s a) R(s,a))
(s,0)ESXA
c. range R
Σ (s,
(s,a)SSxA
range R
Because this holds for all possible data distributions we have -b) + -a) which proves the result.
28

---

The Perils of Optimizing Learned Reward Functions
Theorem C.13 describes the of reward functions R for which there exists optimal policy स that achieves worst-case regret under the true reward function R. Theorem C.14 the other hand, describes the set of reward functions R, for which there exists a data distribution D such that R is close the true reward function R under D. We would like to take the intersection of those two sets of reward functions, and then derive the set of data distributions D corresponding to this intersection. Toward this goal we first present the following lemma:
Lemma C.15. For all 0, L [0, MDP M (S,A, T, po, R2 7) and all data distributions D A))x),, there exists system of linear inequalities, such that D unsafe R. e, L) if and only if the system of linear inequalities is solvable.
More precisely, let Vi be the set of high-regret vertices defined as in Theorem C.9 Then, there exists a matrix C, as well as a matrix (v) and a vector b(v) for every v E Vk such that the following two statements are equivalent:
1. D unsafe(R, e, D), i.e. there exists a reward function R and a policy â such that:
(a) ((a,)>D [R(s.e)-R(s.d)
S c;
range R
(b) Reg" R (f) 2 L
Reg R (+)
(c)
2. There exists vertex V such that the linear system
[[ U(v) C .Odiiag (D)
1
b(O) E range R 1
B
(20)
has a solution B. Here, we use the vector notation of the data distribution D.
Proof. We can express any reward function it as f = R B, i.e. describing as deviation SxA + R from the true reward function. Note that this case, we get R R = B. Next, note that the expression:
E E(say> [[s a)ll
range R
(21)
describes a "weighted L ball" around the origin in which B must lie:
(aaa)D (B(s,a)) 6 range R
(22)
Σ
D(s,)) [B(s,a) S e range R
(23)
(sa)ESxA
BEC(D) = IXAI
Σ
D(s,a) - |Fs,al S e c-range R
(24)
(s,0)S8xA
This "weighted L ball" a polyhedral set, which can be described by the following set of inequalities:
D(s1,a1) ((s,, a1) - 02)) B(s), 02) + ... S e range R
-D(81, B(8),a)) 02)) B(81, 02) + S 6 range R
D(si,a)) B(si,a)) D(81,00 u2) B(s), u2) + S e range R
D() B() D(s1. B(s), 02) + ... S r-ragee R
This can be expressed more compactly in matrix form, as:
C. diag (D) B S 6- range R 1,
(25)
where C 221 diag (D) E RISxAIX|SxAI B SXAA 1 (1]18xA) and the individual matrices defined as follows:
D(s1, a1)
-
1
c
diag (D) =
(26)
D(sn; Um))
29

---

The Perils of Optimizing Learned Reward Functions
Next, from Theorem C.13 know that reward function R = -R+ + has an optimal policy with regret larger or equal L if and only if:
R+ B+BES ++ U cone
VEVA
-E-R + + U vEVA
cone (1-cs (a)))aaa)))))))))(
(27)
We rephrase the above statement bit. Let's focus for moment just single vertex E V First, note that because & and cone (f-e,,al (s.a) are polyhedral, o + cone (s.a)(a)))))araaa( must be polyhedral as well (this follows directly from Corollary 3.53 of (Rockafellar & Wets 2009 ). Therefore, the sum on the right-hand side can be expressed by set of linear constraints (v)) < b(v).
Hence, a reward function, R R + close in expected LI distance to the true reward function R, and has an optimal policy that has large regret with respect R, if and only if there exists least one vertex v Vi such that:
[c
U(o) diag (D)
b(u) range R 1
B s
(28)
holds.
In the next few subsections, we provide more interpretable version of the linear system of inequalities in Equation 20 and the conditions for when it is solvable and when not.
C.3.1. MORE INTERPRETABLE STATEMENT
Ideally, we would like to have more interpretable statement about which classes of data distributions D fulfill the condition of Equation (20). We now show that for arbitrary MDP and data distribution D, D is a safe distribution, i.c., error-regret mismatch is not possible, if and only if D fulfills fixed of linear constraints (independent of D).
Theorem C.16. For all MDPs (S,A,TT,,, R27) and E [0, 1]. there exists matrix M such that for all and
D E A(SxA) we have:
D E safe(R, = M range R 1,
(29)
where we use the vector notation of D, and 1 is vector containing all ones.
Proof. Remember from Theorem C.15 that a data distribution D is safe, i.e., D E safe(R, e, L), if and only if for all unsafe vertices v E V the following system linear inequalities:
[c
U(w) . diag (D)] B <
b(v)
(30)
raangee R-
has no solution. Let V be chosen arbitrarily and define U, == (B E S all B e [g|SxAl, such that R + has optimal policy with regret at least L. Then, Equation (30) has no solution if and only if:
(v)) B < (()))) i... . U. is the set of
wB Uv C. di (D) B $ range R
(31)
vB Un abs(B)² D e range R
(32)
where we used the definition of the matrices C, and diag (D) (see Equation (5) and abs(-) denotes the element-wise absolute value function. Now, will finish the proof by showing that there exists a finite set of vectors X c U, (which independent of the choice of D), such that for every X, Equation (32) holds if and only if it is true for all B, i.c. more formally:
abs(B) D> c range R VB E X,
VB Uo abs(BBr D > range R.
30

---

The Perils of Optimizing Learned Reward Functions
And since X is finite, we can then summarize the individual elements of X as rows of matrix M and get the desired statement by combining the previous few statements, namely:
E safe e, L)
D e range R.
(33)
Towards this goal, we start by reformulating Equation 32 problem:
condition on the optimal value of convex optimization
Vr E Eo: abs(x)) D > c. range R
min abs(z)) - > E range R
zell
abs(x")) D 6 range R.
where x² =
arg min zell, abs(x)) D
abs(x")) D>> E range R,
where x²
arg min abs(z)) D,
(34)
subject to U(v) x < b(u)
Note that the optimal value x' of this convex optimization problem depends on the precise definition of the data distribution D. But importantly, the set over which we optimize (i.c.. Ur defined as the set of all æ, such that U(v) S 6) does not depend on D! The goal of this part of the proof is to show that for all possible 1) the optimal value of the optimization problem Equation (34) is always going to be one the vertices of U, Therefore, we can transform the optimization problem Equation (34) into new optimization problem that does not depend on / anymore. will then be possible to transform this new optimization problem into simple set of linear inequalities which will form the matrix M in Equation (33
Towards that goal, we continue by splitting up the convex optimization problem into set of linear programming problems. For this, we partition RISxAl into its different orthants Og for e E { [_1,1] (a high-dimensional generalization of the quadrants). More precisely, for every x E Oc. we have diag (c) x = ab)( Using this definition, we can reformulate the constraint on the convex optimization problem as follows:
min (diag (c) Iz) D range R, CE{ 11(-1,1)isxA
(35)
where the individual ve defined as the solution of linear programming problems:
Te == arg min
(diag (c) - =>²"
(36)
subject to
U(v) S b(v)
diag (c) x 2 0,
or xe = case the linear program is infeasible. Finally, by re-parametrizing each linear program using the variable transform x' diag (c) we can convert these linear programs into standard form:
Te = diag (c)
arg min min xr
L
(37)
subject to U(v)- diag (c) x < b(v)
z' 2 0,
where used twice the fact that diag (c) - diag (c), and hence, diag (c) x'. Because it was possible to transform these linear programming problems described in Equation (36) into standard form using a simple variable transform, we can apply standard linear programming theory to draw the following conclusions (see Theorem 3.4 and Section 6 of Chapter 2 of /Vanderbei 1998) for reference):
1. The set of constraints in Equations 366 and 37 are either infeasible or they form a polyhedral set of feasible solutions.
2. If the set of constraints in Equations (36 and 37 are feasible, then there exists an optimal feasible solution that corresponds to one of the vertices (also called basic feasible solutions) of the polyhedral constraint sets. This follows from the fact that the objective function is bounded from below by zero.
31

---

The Perils of Optimizing Learned Reward Functions
Let's denote the polyhedral of feasible solutions defined by the constraints in Equation 36p by Fe(v). Because ((()) does not depend the specific choice of the data distribution, this must mean that for every possible data distribution D, we have either 0 or Te is one of the vertices of Fe) denoted by vertices(F.(u)) Note that, by definition of æ it holds that:
Vo E vertices(Fa.1)) (diag (c) xe)" & (diag (c) xx)". D.
(38)
Therefore, we can define:
(abs(a1)
X(u)= = U
vertices(F.(v)) = oxh and Mx(e) =
(39)
eE(-1,1)1sx4
abs(
where Mx (v) contains the clement-wise absolute value of all vectors of (()) as row vectors. Let D be an arbitrary data distribution. Then, we've shown the following equivalences:
B E Up
abs(B)) D > e e-range
(see Equation 32)
min
(diag (c) xze²
D > e rangge
(see Equation (35)
CE (-11) sxAl
2.70
abs(z)" D > 6 e-range R xEX(e)
min
(due to Equation 38
1
Mx D) > 6 range R
Now, by combining the individual sets of vertices (v), as follows:
(abs(x1)" ) abs(z;)T
= U X(o) = 151. and
(40)
VVVA
we are now ready to finish the proof by combining all previous steps:
D safe c,
Vu Vi, VB Uu
abs(B)T. D > e range R
Vu E V
Mx (v) D > c range R
M D > c. range R 1.
That was to show.
C.3.2. DERIVING THE CONDITIONS ON
In Theorem C.16 we' 'e shown that there exists a set of linear constraints D > e range R 1, such that whenever a data distribution satisfies these constraints, is safe. In this subsection, we derive closed-form expressions for the individual rows of M get a general idea about the different factors determining whether an individual data distribution is safe.
In the proof of Theorem C.16 we showed that M has the form:
Tabs(2)) x1)
M =
a
for some set X following class of system of linear inequalities:
{I1, }. where each x e X belongs to a vertex of the set linear constraints defined by the
[
U(v) -diag (c)
[b(b] [o]
(Corresponds to the set of unsafe reward functions) (Corresponds to the orthant O.)
(41)
for some V (the set of unsafe vertices of Q), and some E {-1, 131x (defining the orthant O.).
32

---

The Perils of Optimizing Learned Reward Functions
To ease the notation in the following paragraphs, will the notation Ue for the polyhedral of x such that U(v)- b(u), and Fe(1)) for the set of solutions to the full set of linear inequalities in Equation (4Tp. Furthermore, will use = [S] and m == [|].
We start by giving small helper definition.
Definition C.17 (General position, (taanlyy 2024)). Let H. be a set of hyperplanes in IR. Then H is in general position if:
[1 ................................ Hp) H. psn [H Hp) H. H.P.P.. p>n
dim(H1 n... Hp) H1 0h.... Hp=00 =
We will use this definition in the next few technical lemmas. First, we claim that each of the vertices of Fo(v) must lie on the border of the orthant Oe.
Lemma C.18 (Vertices lie on the intersection of the two constraint sets.). All vertices of the polyhedral set, defined by the system of linear inequalities:
U(w) ] x x b(0) [ -diag (c)
(42)
must satisfy some of the inequalities of -diag (c) x S with equality.
Proof. U,, be the set of solutions of the upper part of the system of linear equations in Equation (42) and Og be the set of solutions of the lower part of the system of linear equations in Equation (42). The lemma follows from the fact that Ue can be expressed follows (see Equation (27) and the subsequent paragraph):
Up = R + + cone (eaeaaaa)))))))errat)))
(43)
where a linear subspace. Hence, for every x that satisfies the constraints b(()). x lies on the interior of the line segment spanned between x' x + Φ. and x" x 6 for some b, * Note that every point on this line segment also satisfies the constraints (vv) < b(v). Therefore, x can only be vertex if it satisfies some of the additional constraints, provided by the inequalities - diag (c) S O, with equality.
b(v).
Consequently, every vertex of (u) is the intersection of some k-dimensional surface of and standard hyperplanes (hyperplanes whose normal vector belongs the standard basis).
Lemma C.19 (Basis for & (Schlaginhaufen Kamgarpour 2023)). The linear subspace &b of potential shaping transfor- mations can be defined as:
span(A - y P),
where A, P.P. E R (w for n (8), m = |A| are matrices defined as:
1
0
mm
T( $1, a1) 7( 11,
0
m
m
A
P =
T(. sny am)
0
m
m
where 0" 1 are column vectors and T(118;, ) is row vector of the form [T(s1 s;,a;),... T(m si az)
Furthermore, we have dim &- = n.
Proof. This has been proven by (Schlaginhaufen & Kamgarpour 2023) (see their paragraph "Identifiability" of Section
4). The fact that dim = n follows from the fact that & is the linear space orthogonal to the affine space containing the occupancy measure space Q2 i.e. Φ- = L where L is the linear subspace parallel to span([) (see the paragraph Convex Reformulation of Section 3 of (Schlaginhaufen Kamgarpour 2023)) and the fact that dim sIan(() n (m 1) (see
Proposition 1 of (Karwowski al. 2023)).
Lemma C.20 (Dimension of U..) dim U, = n m.
33

---

The Perils of Optimizing Learned Reward Functions
Proof. Remember that U, can be expressed as follows (see Equation 27 and the subsequent paragraph):
Ur R + + cone ({ (t. (=.)))
(44)
From Theorem C.T9 know that dim + We will make the argument that:
a) dim [cone
2 n (m
b) There exist exactly (m basis vectors of cone ((=Gs.a) such that the combined set of these vectors and the basis vectors of & is linearly independent.
From this, must follow that:
dim ④ + cone ((=esal((sn)ssrrott)) dim ① + n (m - 1) m
For a), remember that v a vertex of the occupancy measure space and that each vertex v of Ω corresponds to at least one deterministic policy x" (see Proposition of (Karwowski et al. (023)). And since every deterministic policy is zero for exactly (m - 1) transitions, must follow that also zero at least (m 1) transitions, since whenever x² (als) for some (s) SxA,, we have:
as) = r' P(st 8,0, =a =a = (als) Σn
P(st = =8 =s n
0.
t=
t=
Therefore, it follows that dim ccone (1-e ( (s..))seroos())) (m 1).
For b), (Puterman 1994) give necessary and sufficient conditions for point R=' to be part of Q (see the dual linear
program in section 6.9.1 and the accompanying explanation), namely:
x e
(A (A- 7 (A-7.
P) == no and 1 1x220
where / is the identity matrix and can be described as the intersection of supporting hyperplanes of Ω that general position. Because (A - 7 P) has rank n (see Theorem C.19 this must mean that for at least n (m 1) inequalities of the system 7 u 2 0 hold with equality and the combined set of the corresponding row vectors and the row vectors of (A P)T is linearly independent (as the vectors correspond to the normal vectors of the set of n m hyperplanes in general position).
the vector notation of the initial state distribution μoo- Because is vertex of Q it
Note that the set of unit vectors that are orthogonal to v precisely defined by ( since, by definition of zv)os(v) (see Theorem C.10), we have
Vo {-Cs,e x7 0.
From this, it must follow that the polyhedral set Us has dimension m.
Lemma C.21 (Defining the faces of Ucy). Each k-diimensioal face F of (with 2 n) can be expressed as:
R + cone (Er), where Ep C
(45)
such that Fr and the combined of vectors of Er and the columns of A --7 P is linearly independent.
Proof. Remember that Uy can be expressed as follows (see Equation 27 and the subsequent paragraph):
Uo R + + cone (( ([-es,a ( (eeo)
(46)
This means that express U, polyhedral cone, spanned by non-negative combinations of:
The column vectors of the matrix - 7 P.
34

---

The Perils of Optimizing Learned Reward Functions
The column vectors of the matrix -(A y P). Since & is a linear subspace and cone is spanned by only the positive combinations of its set of defining vectors also have include the negative of this matrix allow arbitrary linear combinations.
The set of vectors (eeaaoss-t
Consequently, each face of UG of dimension & spanned by subset of the vectors that span U2 and therefore also a cone of these vectors. Because the face has dimension span face of dimension l with less than k linearly independent vectors, and every additional linearly independent vector would increase the dimension of the face. Furthermore, since Φ is linear subspace that is unbounded by definition, it must be part of every face. Therefore, every face of Ug has dimension of at least (the dimension of Φ).
require exactly k linearly independent vectors, as it's not possible
Note that the converse of Theorem C.21 doesn't necessarily hold, i.c., not all sets of the form described in Equation 45 are necessarily surfaces of the polyhedral set U(v) x S b(v).
We now ready to develop closed-form expressions for the vertices of Fe(v). Note that it is possible for 0 E T be vertex of Fe(v). But in this case, according to Theorem C.16 this must mean that the linear system of inequalities M D > range R 1 is infeasible (since M would contain a zero row and all elements on the right-hand side are negaaiegi,,,.. which means that in this case safe(R, L) = 0. We will therefore restrict our analysis to all non-zero vertices Fu()..
Proposition C.22 (Vertices of Folv).) Every vertex UFG of Fe(u), with DFG O. lies on the intersection of some face F of the polyhedral set Uy and some face G of the orthant O₂ and is defined as follows:
UFG RR P, EF (Eo - -,E EE R,
where Ep, Eg are matrices whose columns contain standard unit vectors, such that:
F = - R + + + cone (Ep), G = {i E Rm EG x== 0}.
for Ep C ((-Esaa)e
Proof. We start by defining the faces of the orthant Oc. Remember that O₂ is the solution set to the system of inequalities diag (c) xr 2 Therefore, each defining hyperplane of O. defined by one row of diag (c), i.e. diag (c); x = O. Note that since e E (-1,1)"*0 this is equivalent to the equation ea" x where e is either the i'th standard unit vector or its
negative. And because every I-dimensional face G of O₂ is the intersection of standard hyperplanes {e,, ... e₁ }. this must mean that G' is defined the set of solutions to the system of equations Eg 0 where EG is the matrix whose row vectors are the vectors (Ciy:..,, Ci,)
Next, let UFG be an arbitrary non-zero vertex of Fe(v). As proven in Theorem C.18 every vertex of Fo(v) must satisfy some of the incqualities diag (c) x 2 for c {-1, 13 with equality. This means that UFG must lie on some face G of the orthant Oz. The non-zero property guarantees that not all inequalities of the system of inequalities diag (c) x 2 0 are satisfied with equality, i.e. that G is not vertex. Assume that k inequalities are not satisfied with equality. Therefore. G must have dimension k and Eg Ra.mxk
Since UFG is vertex of the intersection of the orthant O2 and the polyhedral set Uv and it only lies on a k-dimensional face of O.. it must also lie on m dimensional face F of Ut such that the combined set of hyperplanes defining F and G in general position. The condition that the combined set of hyperplanes is in general position is necessary, to guarantee that UFG has dimension 0 and is therefore a proper vertex.
From Theorem C.21 we know that F can be expressed as:
R + + + cone (Er),
where EP C (eaa)eaon))))))
(47)
such that |Epl= = n (m - 1) - & and the combined set of vectors of EF and the columns of A 7 P are linearly independent.
35

---

The Perils of Optimizing Learned Reward Functions
Because VFG is part of both, F and G, we can combine all information that we gathered about F and G and deduce that it must hold that:
EG : UFG
and
3 E R Rummk
VFG - R [A y P. P.Erl-
(48)
equivalent vrGEG
equivalent to oFGEr
where for x: in Equation (48) it additionally must hold that Vi E + 1.,,,.. m k). 2, 2 0. This must hold because these last entries of x should form convex combination of the vectors in Ep (as F is defined to lie in the cone of Ep, Equation (47). We briefly state the following two facts that will be used later in the proof:
a) VFG is the only vector in R that fulfills both conditions in Equation (48) This is because we defined F in such a way that the intersection of F and is single point. And only points this intersection fulfill both conditions in Equation (88).
b) For every non-zero vertex UnG, there can only exist a single x: that satisfies the conditions in Equation (48). This follows directly from the assumption that the combined set of vectors of EF and the columns of A -- P are linearly independent (see Equation (47 and the paragraph below).
We can combine the two conditions in Equation (48) to get the following, unified condition that satisfied for every non-zero vertex UyG:
Fi Te FG (- R [A- P,Fr) Frr. .x) O
(49)
From this, it is easy to compute the precise coordinates of UFG:
x = (Eo 1A-7- [A- - EG R
(50)
UFG = R + [A - -, PF (EG |A 1A-7 P,Er)
EG R.
(51)
We finish the proof by showing that the matrix inverse in Equation 50) always exists for every non-zero vertex UFG- Assume, for the sake of contradiction, that the matrix FGG [A - 7 P, Er is not invertible. We will show that in this case, there exists a I with A UFG such that = fulfills both conditions in Equation (48). As we've shown above in fact a) this is not possible, hence this is a contradiction.
Assuming that EGG [4 7 P. Er] is not invertible, we know from standard linear algebra that in that case the kernel of this matrix has a dimension larger than zero. Let f1, V2. be two elements of this kernel with y11 * V/-
Earlier this proof, we showed that for every non-zero vertex UFG, Equation (49 is satisfiable. Let x be a solution to Equation (49.. From our assumptions, it follows that both + y1 and x + y/2 must also be solutions to Equation (49) as:
Vy E 82), EG (- R [A 7. P, Frrl (xr + v))
Ea R + Eg [A - 7 P, EF]
(x +
- EG R + Eg [A 1 P, Ep]
Eg - + [A - - P.Er]
And from this, it will follow that both, x + ø1 and y2 must satisfy both conditions in Equation 48 V1 # + V22 it must also hold that:
Because
R + A 7. P. Fr) (x + 91)
# - R P, Ep] (x + y2),
see fact b) above for a proof of this. And this would mean that there exists at least one z E R with 2 * UPG such that 2 fulfills both conditions in Equation 448. But as we have shown in fact a), this is not possible. Therefore, the matrix Fa [A - 7 P. Er) must be invertible for every non-zero vertex UrG-
36

---

The Perils of Optimizing Learned Reward Functions
We ready provide specific information about the exact conditions necessary for data distribution D be safe.
Corollary C.23 (Vertices of Fo(o))). For all > 0, E [0, 1] and MDPs (S,A, T; po, R, 7), there exists a matrix M such that:
D E safe R,
M D > range R 1,
(52)
for all E AS)x),, where we use the vector notation of D, and is a vector containing all ones.
The matrix M defined as:
(abs(v1) )² abs(x;)²
M
where an individual row 2; of M can either be all zeros, or
- 7- En) (Exz [A 1A-7. P. P,
Es2 R.
(53)
where Es, Esg are special matrices whose columns contain standard unit vectors.
Proof. This is simple combination of Theorem C.16 and Theorem C.22
In particular, Equation (53) shows that whether a particular data distribution D safe or not depends on the true reward function R, as well as the transition distribution (encoded by the matrix P).
C.3.3. ALGORITHM TO COMPUTE THE CONDITIONS ON D
The derivations of Appendix C.3.2 can be used to define simple algorithm that constructs matrix M. An outline of such an algorithm is presented in Algorithm|] set of vectors and arrange them as rows/columns of a matrix.
| We use the terms Row Matrix and ColumnMatrix to denote functions that take
To give brief explanation of the algorithm:
Line follows from the definitions of VHi (() and X (see Theorem C.9 and Equations 39 and (40
Lines 6 and 7 are taken from the definition of Ep in Equation 47 (except that we don't 't take the negative of the vectors and instead negate Ep in the final formula).
Lines
We additionally ensure that Er is subset of Eg otherwise, the matrix EG [A 7 P, -Er] is not invertible (due the multiplication of Eg EF) and we know that the matrix must be invertible for every vertex.
& and and are taken from the definition of EG (see the first two paragraphs of Theorem C.22
Lines 20 and 22 compute the row of the matrix M. The formulas are a combination of the definition of the sets X(v), X (see Equations (39h and 40)) the matrix Mx (Equation (40)) and Theorem C.22
Line 19 checks whether the matrix Eg [A 7- P, Pf- is invertible. This is always the case for the rows of M (see the last few paragraphs of the proof of Theorem C.22 but might not be true for other candidates.
To explain Line 21 remember that every of the matrix M corresponds to the element- wise absolute value of vector that lies on the intersection of two polyhedral sets F, and G (see Theorem C.22). The polyhedral set F is defined via convex cone. To check that our solution candidate lies in this convex cone, we have to check whether the last entries of x = (Eg [A - 7- P. Er]) EG R, the entries belonging to the vectors in Ep, are non-negative.
The asymptotic runtime of this naive algorithm is exponential in |S A due to the iterations over all subsets in Lines 7 and R However, better algorithms might exist and we consider this an interesting direction for future work.
37

---

The Perils of Optimizing Learned Reward Functions
Algorithm I Computes the of conditions used determine the safety of data distribution.
1: Input: MDP = (S, A. T, (o, R, 7), LE [0, 1]
2: I + the ser of all unit vectors of dimension S Ax.A.. Create a fixed ordering of and A and denote each vector of by ((s,a] for a unique tuple (s, a) SxA.
3: candidates []
4: II. Set of deterministic policies of MDP
5: % Create set of potential row candidates.
6: for ( E aaa Reg" (x') 2 レ} do
7: E (e(,)) E <alss) = 0}
8: for EF C E do
9:
for subset C \ Ep, |subset| = |S| do
10:
EG +- Ep subset E ColumnMatrix(Es), RowMatrix(Ed)
candidates.appeed((E Ec))
13: end for
14: end for
15: end for
16: % Find the valid rows amongst the candidates.
17: rows +
18: for (Ef, FG) E candidates do
19: + ++num__ coum_colums([L (EF)
if rank rank(EG [A 7- -FF] n + k then
21:
Eg R if vi E [n, n + 1 1,..., k) vi 2 0 then
x+ FE [A 9- -FF]
22:
T
23:
row - abs + |A 7 P, -F x)
24:
rows.appont (row)
25: end if
end if
end for
M +- RowMatrix(rows)
29: return M
C.3.4. WORKING EXAMPLE OF COMPUTING MATRIX M
Figure shows simple toy-MDP with single state and three actions, for which we then compute matrix M using Algorithm Due to the simple structure of the MDP, the auxiliary matrix A and the state-transition matrix / (both used in Algorithm become trivial:
A and p=
The resulting four constraints that given data distribution over the state-action space of this MDP has to fulfill to three-
be in safe( e, T.) then visualized in the right-most column of Figure 4 Note that the constraints dimensional vectors. However, because D is a probability distribution, it must live in two-dimensional subspace of this three-dimensional space, and using the identity ds = 1 d1 - d2 we can transform the constraints as follows:
di
d1 d2
m1
m22
m73
d2
m1
m3
m2
m3
m33
d3
38

---

The Perils of Optimizing Learned Reward Functions
2
0.
0.8
1.18
a
3
MDP
0.8
0
0.38
M
S
1.18
0.38
0
0
1.18
R(a, [s) 2.78
0.6
R(ag s) 1.98
Reward
data distribution D (d1, d2, d3) is safe if and only if:
R(a, s) 1.6
0.2
0
0.8
1.18
0.2 1.18
Y 0.4
(Discount factor)
ddy
0.8
0
0.38
0.2 1.18
L= 0.8
(Largest allowed norm. regret)
1.18
0.38
dg
0.2 1.18
0.2
(Largest reward model train error)
0
0
1.18
dg
0.2-1.18 6
-02
Setup
Result
Visualization
Figure 4. A working example of how compute the matrix M very simple MDP with a single state and three actions. Given the information in Setup column, matrix M can computed using Algorithm The constructed matrix M contains four linear constraints that a data distribution D has to fulfill in order to be in safe( R, L.). The four constraints are plotted in the right-most column.
The brown triangle in Figure depictt the 2d- 2d-probability simplex of all distributions over the three actions of the MDP.
Note that constraint @ is redundant constraint that is already covered by the constraint @ and the border of the simplex. It would therefore be possible to disregard the computation of such constraints entirely, which could speed up the execution of Algorithm In the next section, we discuss this possibility, as well as other potential directions in which we can extend Thcorem 3.5
C.3.5. BUILDING UP ON THEOREM 3.5
There are multiple ways how future work can build up on the results of Theorem 3.5
Finding sufficient conditions for safety that require less information about the true reward function: It would be very interesting to investigate whether there exists some subset of the set of safe data distributions for which it is possible to more easily determine membership. This could be helpful in practice, as knowing that a provided data distribution is safe directly yields safety guarantees for the resulting optimal policy.
Developing fasterr methods to construct M: While the algorithm we provide above runs in exponential time it is unclear whether this has to be the case. The set of vectors that are computed by our algorithm redundant in the sense that some elements can be dropped as the conditions they encode are already covered by other rows of M. Depending on what fraction of computed elements are redundant it might be possible to develop an algorithm that prevents the computation of redundant rows and can therefore drastically reduce computation time. Alternatively, it would be interesting to develop fast algorithms to compute only parts of M. This could be especially interesting to quickly prove the unsafety of data distribution, which only requires that single constraint is violated.
Extending Theorem 3.5 to the regularized policy optimization case: This would allow one to extend the use case we described above to an even wider variety of reward learning algorithms, such as RLHE
theoretical baseline (a broader view on the previous point): Most of the options above reveal the properties of the "baseline algorithm" of reinforcement learning under unknown rewards: First, reward model is trained, and second, policy is optimized against the trained reward model. The matrix M is valid for the simplest such baseline algorithms without any regularization in either the reward model or the policy. As we mentioned in comments to other reviewers, it would be valuable to study other training schemes (e.g.. regularized reward modeling, or switching back and forth between policy optimization and reward modeling on an updated data distribution), for which the set of safe data distributions (or "safe starting conditions") is likely more favorable than for the baseline case. Then, similar to how empirical work compares
39

---

The Perils of Optimizing Learned Reward Functions
new algorithms empirically against baseline algorithms, hope our work be basis theoretically study improved RL algorithms under unknown rewards, e.g. by deriving favorable analog of the matrix M and comparing it with work.
C.4. Existence of negative results in the RLHF setting
C.4.1. GENERALIZATION OF THE ERROR MEASUREMENT: PROOFS
In this subsection we test the extent to which the results of the previous section generalize different distance definitions. To ensure compatibility with the positive results of Appendix D.3 consider MDPs with finite time horizon T. In this setting, trajectories are defined finite list of states and actions: Ç = 80, 40: .., Let E bet the set of all trajectories of length T. As in the previous sections, G = + IR denotes the trajectory return function, defined as:
T-1 G(E) = Σ 1=0
r. R(s,, at)
Proposition C.24. Given an MDP (8, A,,AA,T, T, Ho, R,Y), 7), , a data sampling policy π 8 - ((A) and second reward function R: SxA- R, can upper bound the expected differennc in trajectory evaluation as follows:
1-7" 1 1-7
EE [[G((E) - GR(E)]]
B( [In(s,a) i((ssa))) a)]
(54)
where D = 1-y I-q" 177
Proof. This follows from the subsequent derivation:
B [Gn((E) GR(EE)]
Σ
P(E
Σ 7/ (R(s), R((se ar))
EEE
P(g| T)
7 R(se, oz) - R(ss, at)
EE
=
Σ
Σ
r P(s: = s, =,,
[((s,c) M(s,a)
(x.))SXA
1=
Σ
17th (s,
[((s,a) -R((s
(x.0)SxAA
1
R((saa - P((s,a)
1-7
Given some reward function define the probability of trajectory & being preferred over trajectory &a be:
exp(Gn((Ei)
PR(EI > E2) oGGR(E)) - GR(E2)) = (
Then, the following statement holds:
Proposition C.25. Given an MDP (S, A, T, Ho. R, , a data sampling policy π. : S + ((A) and second reward function R: S + R, we can upper bound the expected KL divergence over trajectory preference distributions as follows:
Egg [Tk (r < 2 Egg. [[Gn(E) -
(55)
40

---

The Perils of Optimizing Learned Reward Functions
Proof. The right-hand-side of Equation (55) be lower bounded follows:
2. Ee-w [GR(E) - GR(E)]]
(56)
[Gn((5)) GA(()) (G(l))) G
(57)
fe [GR((E))
- -
(58)
R [ VEI.Ezl),
(59)
where from Equation 157p to Equation (58) we used the triangle inequality and did some rearranging of the terms, and
from Equation (58) to Equation (59) simplified the notation bit by defining F6 Gn((i) Gn(Ez) and
& G (G GE2(
Similarly, we can reformulate the beft-hand-side of Equation (55 as follows:
Eg, &aNTxx
[XL
(60)
PR(Ci E2)
=
Σ
PR(Ei > E2)) llog
(61)
Pa(E: E2)))1
(JE(1
(GGn(E)) Gn((s))
Σ (E)()))
(Cnl(t)-GR(6e log
(62)
(G - GR(E)))
(o(
Σ ( log
(63)
o(VELs)))
(1E()
We will now prove the lemma by showing that for all (2) E
= we have:
Σ (Fc.)) log a (
[ - Mel
(64)
(.))
$
from which it directly follows that Equation 66 is smaller than Equation (59
Let (E1, E2) E E E be chosen arbitrarily. We can then upper bound the left-hand side of Equation (64 as follows:
(xE))&)) log (o( [(VEre)))
+ o (xEs.s)) log
(65)
< log
+ log
(66)
(VEi.E))
a ( .0 (
log
(67)
o(Ver.52) :0 (-NE,
+ exp(UEi.sa))
log
(68)
exp(us, .2)
(1 (xpparg,.su )2
+ exp(
-3 V6r.s +2. log
(69)
+ exp(
where we used the fact that 0gr.ez = GR((Ei) - G GR(E2) and therefore, -I = Iea. (similar for Ve..E)) We now claim
that for all (2) e E x it holds that:
1 + exp(ssss) $ 1rer Ven.sal
2E Ve,.c + 2 2o
(70)
1 1 exp((x (25p))))).))))

---

The Perils of Optimizing Learned Reward Functions
We prove this claim via proof by cases:
E1 > &2i In this case have [ggiif VELiE2 = TEr &2 &2
and Equation 70
becomes:
exp(Uer 1 exp(1e118)
2 log
S 0.
And since 26,.62 > &2 the fraction inside the logarithm is smaller than 1, this equation must hold.
Si Men In this case, Equation (70) reduces to 0 2 O which is trivially true.
S < Ug, .2 f In this case, we have [g,,E Cc = UC 26, La and we can reformulate Equation 770 as follows:
1 + exp(Veii)))
TELia Mer.e + log
S Mer &2
1 + exp(ses)t))
+ exp(Us 5z)
exp(Us
S
+ exp [2))
exp(#Er
exp(x S exp(Ue)
Because assume that Eçi.& C2 the last equation, and therefore also the first, must be true. Combining all the previous statements concludes the proof.
Finally, in some RLHF scenarios, one prefers to only compare trajectories with common starting state. In the last lemma, we upper-bound the expected error in choice distributions with trajectories that share a common starting state by the expected error in choice distributions with arbitrary trajectories:
Proposition C.26. Given an MDP (S, A, T, Ho: 7), a data sampling policy क S + ((A) and second reward function R: A R, we can upper bound the expected KL divergence of preference distributions over trajectories with a common starting state as follows:
1
DKa
min po(s') Es, Ea [Dx (pa(l (71) s'es pots'1>0
40~1A0. (1,E2~<T(So)
Proof. Let 8g : define the function which outputs the starting state of trajectory & E E. We can then prove
42

---

The Perils of Optimizing Learned Reward Functions
the lemma by directly lower-bounding the right-hand side of Equation
[T&L (2n(-15i,,2)llppd (2).
E
po(s1) (o((2))
Σ
Pa.r (5i1(11(81) PPr,r(alss) Dxi. (pa(((ki.6))llpa((kk...)))
&
=
=0l8x)=82
Σ (o($1) Ho((2)
Σ
(fil(()1)1)) (5,l((2)82) DaL. (patt/b..
"o({>)
+ Σ (o(81) ((o1))))0(82)
Pr,,(Ei181) (521((2))2)) DeK (pml(St..6)lllan((Hi.... x
Σ
=0(E1)=a1 c0(52)=#2
Σ (u(s1) (2(32))
Σ
(Eil(())))) (E,l((2)s2)) DxL (3al))5s.
=82
E E
(o(E))=
=8
z min mo(s') Σ Ho(s) d'ES no(e'>>0
Σ
pa.s (Eils) Pan (E2ls) DKL (ar(((
$ x
)=(
(o(E2)=s
min LES
Ho(s') E 80--p0 (s)))
[KL (pallls.
no(s)>>0
where we used the fact that the KL divergence is always positive.
C.4.2. RLHF BANDIT FORMULATION
RLHF, especially in the context of large language models, is usually modeled in a contextual bandit setting (Ziegler et al.
2019 Stiennon et al. 2020 Bai et al. 2022 Ouyang et al. 2022 Rafailov et al. 2023)). ). A contextual bandit (S, AS R)
defined by a set of states S, set of actions A, data distribution μ40 E (S). and a reward function Sx.A - R.
The goal to learn a policy π S > (AA) which maximizes the expected return J(T) Bs-no.a<x(-1e) [R(s, a)]. In the context of language models, S is usually called the of prompts/contexts, and A the set of responses. Just for the MDP case, will assume for all our contextual bandits that max J min J since the reward function would otherwise be trivial. We model the human preference distribution over the set of answers A using the Bradley-Terry model (Bradley) & Terry] 1952). Given prompt s E S and two answers 01, 02 E A, then the probability that human supervisor prefers answer (1 to answer 02 is modelled as:
exp(R(s,a1) Pn(a1 > 02l 8) = exp(R(s,a1)) + exp(R(s.o2))
(72)
where R: SxAAA + R assumed to be the true, underlying reward function of the human.
RLHF usually done with the following steps:
1. Supervised finetuning: Train/Fine-tune language model Tref using supervised training.
2. Reward learning: Given data distribution over prompts μ A(S), use a and Nuet to sample a set of transitions (x, ag. (1) E Sx.A x A where lr and do, ai Wrar(:ls) Use this set of transitions to train reward model π which minimizes the following loss:
[R(
-B(sson.onn.)ppm..a... [og(o((A(ss R((s, a1-)
(73)
where e E {0, 1) and p(c 0|8, ag, a1) = prelap > a1ls).
43

---

The Perils of Optimizing Learned Reward Functions
3. RL finetuning: Use the trained reward model ft further finetune the language model "ee using reinforcement learning. Make sure that the new model does not deviate much from the original model by penalizing the KL divergence between the two models. This can be done by solving the following optimization problem for some À >> 0:
= arg max (11 [ À
DRI.. (T[
(74)
C.4.3. SAFE AND UNSAFE DATA DISTRIBUTIONS FOR RLHF
Definition C.27 (Safe- and unsafe data distributions for RLHF), For a given contextual bandit (S, Po. R), let e > 0, L E [0, 1]. E [0, oo), and Tref S + ((A) an arbitrary reference policy. Similarly to Theorem 2.1 we define the set of safe data distributions safe RLHF (R, E, L, A, Dxx.. (-l(Tret)) ) for RLHF as all D E A(SxA) such that for all reward functions R: SxA- + R and policies â S + (A) that satisfy the following two properties:
1. Low expected error: R is similar to R in expected choice probabilities under D, i.e.:
(s 02) (TL (pn(+1s, a1 a2).) (2, 02))] & range R.
2. Optimality: á is optimal with respect to R, i.c.:
π E arg max J ( X- DKL (T(als)
we can guarantee that स has regret smaller than L, i.c.:
3. Low regret: à has a regret smaller than I. with respect to R, i.e., Reg (#) < T.
Similarly, we define the set of unsafe data distributions to be the complement of safe RLHI (R, L, A, DxLL (-1(Tret)): ):
unsafe RLHF (R, L, DeL (-1(Tee)) = { D safe RLHP L, (-1(Tret) }
Note: Property 1 of Theorem C.27 is commonly phrased as minimizing (with respect to R) the loss - (2)0 D.PR (og((o(R(s,n)) - R(s, a2))) (which includes PR. the probability that a₁ is the preferred action over ag the expectation). Our version of Property is equivalent to this and can be derived from the former by adding the constant (w.rt. R)) term E(s.a1,2)~D.p (R(s a2))))))))
C.4.4. NEGATIVE RESULTS
rihf In the following proofs, will define T,, to be the optimal policy after doing RLHF on Tref with some reward function R. i.e..:
Definition C.28 (RLHF-optimal policy). For any À E R4, reward function R and reference policy Tref, we define the policy maximizing the RLHF objective by:
rhh R.A
arg max Esspaax((ee) [R(s, a)] Dxx (a(a)s)][
(75)
rilbf does have the following analytical definition (see Appendix A.I of (Rafailov et al. 2023) for a derivation):
RR,
Trer(als) exp ( R(s,a))
ellif (als) = EveA (rle ()) exp ( R(s,aa))
(76)
Before stating the next negative result, we prove small helper lemma which states that doing RLHF with some reward function R on a policy Nee is guaranteed improve the policy return concerning R:
Lemma C.29. For any X R,, function R and reference policy Teet it holds that:
Jn
Flhl RRA
2 Jn neef
(77)
44

---

The Perils of Optimizing Learned Reward Functions
Proof. Define:
RR [KT, Tree) = JR(IT) - -ALL (Te(
Then we have
(1)
(2) 2
JR
ellaf R.A)
( R (# R. Trat)
thhf
JL (Tret, Tyoo) (n(
where (1) follows from the non-negativity of the KL divergence and (2) follows from the fact that rihf maximizes
R,A
JR. (T,, Wref) (see Equation 75
We begin by proving helper lemma that we are going to use in subsequent proofs.
Lemma C.30. Let (S, A, Po, R) be contextual bandit.
Given lower regret bound I. E [0, 1), we define for every state E S the reward threshold:
Rs(s) (1 (1- L) max R(s,a) L min R(s,
aEA
aEA
and define 0g E A to be an action such that R(s,a.) < Rs(.).
Let Tret : S S be an arbitrary reference policy for which holds that for every state s we have Fret(als) >
Then, performing KL-regularized policy optimization with some regularization constant [0, oo), starting from Tref and using the reward function:
ifa + a. c. E. ifa = a.
R(s,a)
R(s.a)
(78)
results in an optimal (w.rt. the regularized optimization objective) policy such that Reg" (#) 2 L, whenever the constants Cy are larger than the following lower bound:
Eapo, (R(s,a) - R[(ss) )) Tree (als) exp (t R(ss
C. 2 A.oo
(R2(s) - R(s, a.)) (apls)
Proof. Denote by π thi the optimal policy for the following KL-regularized opppriaaaatzzeoooopiiiiiaiiooo problem: At,
rlbi R.
E arg max (T(TT) - A Dxx
The closed-form solution for this optimization problem known (see Theorem C.28 We prove the statement by assuming rihf has regret least L, and then working backward the specific definition of i (see Equation 788). as well that T RRA derive a necessary lower bound for the individual constants Cy.
start by defining a small helper policy. Let का be a deterministic optimal policy for and m be deterministic worst-case policy for R. We then define = (als) as a convex combination of πт and πi:
(als) = (1 L) т. (a|s) + L (a(s))
if R(s, a) mina E.A R(s,a' a') max R(s,a')
1 1- L
if R(s, a) = m R(s. a')
(79)
L
R(s,a) = min, R(s,
0
Otherwise
Next, we show that the regret of nT is Let tfr and 1 be the corresponding occupancy measures of क and T. Then, we have:
Jn((z) 1)- R. mパ L. R. 71
45

---

The Perils of Optimizing Learned Reward Functions
from which it directly follows that:
Rd AT [1- L) R
o9 + L. R 71
Reg P (TT))
L.
R 1/T
1 -79
R Now, having defined TL, we start the main proof. Assume that Reg By using the definition of the policy evaluation function, we get:
2 L, which is equivalent to J(m
A2 S J(L)).
R2,
J(T
R2 S J(TL)
rhat R (1 RA
mT < 0
Σ
R(s,a) po(s) ( R. (als) (a(a)s)) S 0
(s,4)ESxA
We will prove the sufficient condition, that for every S have:
Σ R(s,a) a)
(11hh(()s)) =I(als)) s
(80)
aEA
Before continuing, note that with our definition of Tı (see Equation 79 we have:
Σ
R(s,a) (a(a)s) = (1 - L) max R(s, a) + L min R(s,a) = Rs)s).
aEA
aEA
aEA
Now, using this fact as well as the definitions of Ty and rlllf (see Theorem C.28 we prove under which conditions Equation (80 holds:
RRA
Σ R(s,a)
(rlli (al) - (a(sss) s 0
aEA
(re((a)s) exp (2 A(ssa))
R(s
(n(a(s) 5
EnEE (ror(a exp (t M(s,aa)
R(s, a) a) Tree(als) exp ()- R((3,a)
Σ aEA
Σ R(s, (a(ss)
Σ Trer(alls) (F-
LaEA
a'Ed
(R(s -R(())))RR(s)) (als) exp (2.R(s.a)) 0
Σ
aEA
(R(s,a) Ry(s)) Tre((als) -exp (+.R(s.o) A(s.a))
Σ
aEA ((x
Σ
(Rt R(s, a)) mror(als) -epp exp -((s,a)
R(s.a)<B....)
Now, according to the assumptions of the lemma, we know that there exists some action a, for which R(s, a.) < Ry(s) and Noot (agls) > According to our definition of R (see Equation (88), we have R((s, a.) C, and R((s, a) R(s, a) for
46

---

The Perils of Optimizing Learned Reward Functions
all other actions. We can this definition to get lower bound for Gg:
(R(s,a) - RR((8) [rer(alb) exp ( R(3.a))
Σ
aEA (e))
(81)
(Ri(s) R(s,a)) Teer(als) . exp (1 R(s.0)
WI
Σ
aEA
(R
(n(ss, Rg(s)) (alr exp (+ 18(s.a))
(82)
$ (RL(s) R(s, az)) [ra((aols) exp ( R(s,as)
Eaza, (R(s, a) - RI((s)) Teee (als) exp ( R(s,a))
A log
R(s,a,))
(83)
(RL(s) R(s, a,)) (Txls))
We can now use this lemma to prove a more general result: Proposition C.31. Let (S,A, po, R) be contextual bandit. Given lower regret bound L E [0, 1), we define for every state S the reward threshold:
Ri = (1 - L) max R(s,a) + L min R(s,a),
aEA
aEAA
Lastly, Tret S + A be an arbitrary reference policy for which it holds that for every state E S, (re(() > 0 and there exists at least one action 0, E A such that:
a) (rot(aa)s) (s) is small enough, that the following inequality holds:
log
Σ
Teee (als)) exp ( -R((s)))) (R(s,a)
R(s,aa))) (R(s,.))R((saa))))
a) (s)
range R
log (ax))(a))))
Rs(()) R(s, as)
2 X Tref (agls)
aza
(84)
b) as) < (x)
for some > 0 and X E [0, oo). Let Drel = μ (als) be data distribution based on the reference policy and some p E (SS). Then Dret unsafe
ILLH (R, L, Dxl (-1(Frot)
Proof. According the definition of safe data distribution for RLHF (see Theorem C.27
Dref
unsafe RLHE (R, A, DxL (+l(=eet) if there exists a reward function R S + H, and a policy क S - A(A) such that:
1. Eg,an,asruitted
ar a., (s s e range
2. à E Earg max, (T(TT) DxL (m(als))
3. Reg ( L.
We will prove the lemma by construction. Namely, given the assumptions a) and b) of Theorem C.3
we choose:
R(s,a) = [((saa)
if a +
(85)
Cs E T2
if = a,
47

---

The Perils of Optimizing Learned Reward Functions
where the different C are some positive constants defined follows:
R(s,as) (s), = Go 2 La == max [R(s,ad), A A.log Eaza, (R(s, RL((s) Trer(als) exp (1 Ris,, ( ))
(86)
(RL(s) R(s, as)) Tret (a,ls)
Furthermore, the closed-form of the optimal policy & of the KL-reeglarrzzd optimization problem is known to be rtlhf (see "R.A Theorem C.28). We now claim that this choice of R and a fulfills properties (1) and (3) of the above list (property (2) is true by assumption).
Property (3) is true because every reference policy "ro and corresponding reward function R that fulfills the conditions of this proposition also fulfills the conditions of Theorem C.30 Hence, we can directly apply Theorem C.30 and get the guarantee that Reg" (f) 2 L.
All that remains to be shown, is that condition (1) be satisfied by using the definition of R and the lower bounds in Equation Equation (86). First, note that we can reformulate the expected error definition in condition (1) as follows:
E 02 Feet [TL (pn(.1s, 18, an, a2)llp (1,,,,)) a2))]
[[((s, 0,) R(s, a,)) [(((s, a,) R(s, a,))
= Σ m()).
Σ
Tnrr(ai (2218))
Σ
a(R(s,as) - R(8, log
SES
01Aa
1.
[R((s, R(s, 02)) a(R(s, a1) R((s, a2))
= 2. Σ
u(s))
Σ
[rer(a1(s)- (eyl))))s) o(R(s, 01) - R(s,a2)) log
SES
a AAAAEAAA
IS(aras))
2 Σ (s))
Σ
Tref (a1ls) Tret (a2))) a2)
#ES
Next, note that for every tuple (a1,a)) E A, the sum IS(ai, 02) + IS(a2, a1) can reformulated as follows:
IS(a1, a2) + (S()).a1)
((((s,))) R(s,a2))
=o(R(s, a1) R(s, a2)) log
(((((s,a)) (((s
+ +o((ss)))) R(s,aa))) log a (R(s,0)) R(s,a1))
a ((((s R(s,a1))
o(R(s,a)) R(5, (2),
[(((sa))) R(s, (2)) log
a(((s,))) R(s, a2),)2))
()(((s)))) R(s, a1)) o(((s,a0)) A(ss a1))
1 1- a1) R(s. (2). log
[(R(s,a)) R(s,a2)) a2))
(o(((s,02) - R(s,ai))
<(((s,a)) R(ss
log
log
a(H(s,a1) R(s, az))
o(R(s,02) - R(s,ai))
(A)
[(((s, (((s
log
a(R((sa2) R(s, 01))
(B)
48

---

The Perils of Optimizing Learned Reward Functions
The term (A) now be simplified follows:
( R(s, 02)) log
[({(s, R(s,ai))
log
o(R(s,a1) ((s,02))
a(R(s, R(s,a1))
a(((s,a)) R(s,a2))
( ((s
log
+ log
(l-o(R((s,o) 01) - R(s, a2)
o(((s, - R(s,az))
= [R(s, a1) R2), [R(s,a) a1) R(s,
where used the definition of the inverse of the logistic function. Similarly, the term (B) be simplified follows:
o (R(s, 02) R(s, a1))
log
((((s,02) R(s, a1))
(sp(R((s R(s,a1)) cx+cxp(A(ss 02) - a1) exp(A(ss
1 1 exp((((ss)))) R(s,a1)
log
- R(s, a1)
1 + exp( R(s,, 02) R(s,01))
02) R(s,0r)) [R(s, 02) R(s. + log
02) - R(s,a1))
These expressions, together with the fact that [S a) = 0 for all a E A, allow us to choose an arbitrary ordering x on the set of actions A, and then re-express the sum:
Σ
Are((a11s) Tret (a2ls) IS(a1,
Σ
(rc((a1)s) Tret(a2/5) (IS(a), a2) IS a1)). (87)
0L.0EEAXA
a142EAAA 01 RB2
Summarizing all the equations above, we get:
Es Bs,, [DxI. (pR(-1s, a1 (2) ai a2))]
2.
Σ p(s).
Σ
Trer(ails) (re(())s)) IS(ai, 02)
SES
AAAA
Tre((a (ae())))s) [ R(s, a2)) [R(s, [ R(s, az)]
= 2 Σ u(s)
Σ
(88)
#ES
AAXA -aa
((B(s,a))) R(s,a2)) -1) + log
cxp((((()) R(s,a1)) e a2) R(s, a1))
Now, by using our particular definition of it (see Equation (85 ), we notice that whenever both aj + as and ag # a. the inner summand of Equation is zero. What remains of Equation 88) can be restated as follows:
(A(s) co) (o(R(s,a)) R(s, -1)
2- Σ p(s) (a,
Σ (als) aEAA
(89)
1 exp(R(s, c.) 1 [++ex(([(s,.. R(s, a.))
+ log
To prove property (1), we must show that Equation 89 is smaller or equal to c range R. We do this in two steps. First, note that for all states s it holds that c2 2 R(s, a,) (this is obvious from the definition of c.. see Equation (6)). This allows us simplify Equation 88 by dropping the logarithm term.

---

The Perils of Optimizing Learned Reward Functions
[KLL (1, a2)]
R(s,a)) (R(S)aa) -c)) (o(R(s,a.)) -((s)))) -
2.
Σ (u(s) (rst(a
Σ [alr(a
#ES
aEA
1+ exp(((((s,a) -ca)
+ log
(x))((((s)))) R(s, (.))
2. Σ u(s) (rer(a (cs R(s,,a))
Σ Tror(als)
(1-0( - R(s.a))
(90)
8E8
aEd
1+ a) caa
+ 2: Σ (u()) Trer(a,))) (8).
Σ (alr())s) log 1 expe((ssss R((s
aE8
aEA
Now, we choose to define
Co =1 1, + 8, where Ig is defined in Equation (66) and 6g 2 such that:
2. Σ ((s) (a.ls) (l. + R(s,as)) Σ (al()
1 (1-o(R(s,an) as) R(s, a))
SES
<1
1 + exp([((s)))
5.)
+ 2 Σ u(s) Tre((aals)
Σ
(aee(als)) log
+ exp( R a2))
SES
aEA
50 (because c, ((s,a,))
1 2 c- range R.
< 2. Σ u(s) (ar(s) (1--R(s,on)
R(R,
(91)
SES
Note that the first inequality is always feasible, as we could just choose 8, = 0 for all E S in which case the inequality must hold due to the last term in the first line being smaller than one and the last term in the second line being negative. Now, to prove Equation (91), we prove the sufficient condition that for every state E
rangge R 2
Teet (a,ls) (L. - R(s,,,))
(92)
In case that 4, R(s, a.). the left-hand side of Equation (92) cancels and the inequality holds trivially. We can therefore focus on the case where 1, > R(s. a.). In this case, we get:
Eaza, (R(s, a) (s)) Mal((a)s) exp ( R(s,a)) (Ri(s) R(s, a.)) Trel (a.ls) exp ($: R(s,
range R
Tmr((als) A log
2
Σ Tree (als) exp (1 (B((s,)-R(ssaa)))) -R(()))) aya,
R(s a) Rs(s)
log
Ry(s) R(s, az)
E range
+ (ng(aro((agss))
2. A Tree (a.ls)
which holds by assumption (a) of the lemma. Therefore, property (1) of the lemma must hold as well which concludes the proof.
Theorem C.32. Let (S, Pu, R) be a contextual bandit. Given L E 1), we define for every state E S the reward threshold: (x) = (1 L.) max R(s a) + L. minae, R(s, a). Lastly, let कee S + A be an arbitrary reference policy for which it holds that for every (s, a) E SxA,, (ret(als) > O, and there exists at least one action a A such that R(s, 0,) R2 (s) and (ror(a,)s) satisfies the following inequality:
(rel(a < (Ri(s) R(s,aa)) range R
2
L Leexp ( range R) 4 X2
Let Dref (s, = u(s) Tret(a)s) for some μt E A(S). Then unsafe" RLHF (R,e, e, I., X, Dexe (:1(Trot))
Dref
50

---

The Perils of Optimizing Learned Reward Functions
Proof. We begin by showing that every "ref that fulfiils the conditions of the theorem also satisfies properties a) and of Theorem C.31 Let be arbitrary state and ag the corresponding action that fulfills the conditions stated in the theorem.
We show that condition a) of Theorem C.31 C.31 holds via direct derivation:
(s) R(s, as)
range R
22
(a,
L
exp ( range R)
4 X2
Tref(0,l10) L. exp ( range R)
Vrange A .
RI((s) R(s,a.) as)
2
L range R exp (3 range R)
range R
(rsr(a X
(Ry(+) R(s, a.)) (a
We continue by (ower-bounding the square-root term as follows:
range R exp (+ range R)) A
(s)(s) R(s, a,)) Tzef (a,]s)
L rangee R exp (3 rrange R)
log
(Rr( M(x a.)) Troo (as ())
L range R.exp (3 maxxe R(s,a) R(s, az))) (Rı(s) R(s, as)) (res(0))s)
A log
(maxaed R(s, a) - Rs)s)) exp ( maxaed R(s,a))
A log
(RL(s) - R(s, s, (R))))))) Trell (1 (s) exp ( R(s,a,))
Eapa, (R(s, a) - R& (s)) To exp ( R((s (Ri(s) - a.)) (rrr(a exp ( (((s,a)))
À log
By applying this lower bound, we can finish the derviation of condition a) of Theorem C.31
Rs(s) R(s,aa) az)
range R
e²
(agls)
L
cxp ( range R) 4 X2
L rangee R exp (t range R)) (Ri(s) - R(s, az)) Tret(a
E range R
Tref (re (aols) A. .V
Eato. (R(s, a) Rs)s)) Tree(als) exp (} R(s,a)) (Ri(s) - R(s, Trot (a,ls) cxp (2 R(ssa,.)
E: range R
Tref (a.ls) A Aloo
2
exp ( 5 (R(s, a) - RR(s,a)))
R(s, a) Rs(s)
log
Σ a
(als)
Rs(s) R((, (x)
C range R
+ (ro(Tror(aa)))
2 À (re
Before moving on, note that condition b) of Theorem C.31 holds directly by assumption of this theorem. Therefore, we have shown that every Tref that fulfills the conditions of this theorem also fulfillss the two conditions of Theorem C.31 This must mean that Dref E unsafe
RLHP (R, e, L., X, TDK.. (-I(Tret) for arbitrary ja E ASS) thereby concluding the proof.
C.4.5. ANOTHER NEGATIVE RESULT WITH REGULARIZATION
Proposition C.33. Let (S, Pu, R) be a contextual bandit.
Given a lower regret bound I. E [0, 1), we define for every state s E the reward threshold:
Rr. = (1 (1-1) ()- max R(s, a) + L min R(s, a), aEA
aEA
51

---

The Perils of Optimizing Learned Reward Functions
Lastly, let Fest S - A be an arbitrary reference policy for which holds that for every state E (ee 0 and there exists at least one action Og such that:
a) (re((ayls) (s) is small enough, that the following inequality holds:
(Re(s) R(s, as))
range R
e²
(a))( 2
(93)
L
exp (x range R) X2
b) R(s,as) < (s)
Let (s, a) = (o(s) (re s). Then Dref unsafe(R, L, W,).
Proof. To prove the proposition we show that there exists some reward function R, well as a policy such that the following properties hold:
RRle.a)R((e.n R(c.all S e.
1. Deer
range R
2. it E arg max, (T( (T)
3. Reg" (f) L.
In particular, we choose:
R(s,a) if + a,
R(s,a)
(94)
E 12 if a as
where the different es are some positive constants defined as follows:
A Aloog Enya, (R(s,a) R2(s)) Trtt(als) exp (1 R(s,a)) a))
R(s, a.) = = max
(95)
(Ri(s) ((ss,,))) (a.
Furthermore, the closed-form of the optimal policy á of the KL-regularized optimization problem is known be tllff (see R.A
Theorem C.28 now claim that this choice A and क fulfills properties (1) and (3) of the lemma (property (2) is true by assumption).
Property (3) is true because every reference policy Neo and corresponding reward function R that fulfills the conditions of this proposition also fulfills the conditions of Theorem C.30 Hence, we can directly apply Theorem C.30 and get the guarantee that Reg" R (#) 2 L.
All that remains to be shown, is that condition (1) can be satisfied by using the definition of Åt and in particular, the definition of the individual c, (see Equation (95). The expected error expression condition (1) can be expanded as follows:
[R(s, a) ((s,
Ho(s) (alr( [R(s,a) Ris, a)l & e.
Dist
Σ
range R
range R
(s.a)ESxA
We show the sufficient condition that for each state S it holds:
(als) [R(s,a) range R
M((s)))
By using our definition of Å. (see Equation 94)). this further simplifies as follows:
Trer(a)s) [R(s a) ft,s, a)l
(ree(a,)s). A(s, a.) R(s, as)
Σ
5 c.
(96)
range R
range R
AEA
52

---

The Perils of Optimizing Learned Reward Functions
In the last equation, were able to drop the absolute value sign because our definition of the constants C2 (see Equation (95) guarantees that R(s, a.) a,s,
Next, note that whenever a,) = R(s, ag) the left-hand side of Equation 96) cancels out and so the inequality holds trivially. In the following, we will therefore only focus on states where R(s, a.) > R(s, az). Note that this allows us to drop
the max statement in the definition of the C, constants (see Equation (95))
continue by upper-bounding the difference M((sas) - R(s,us), Uz). By making use of the following identity:
A log exp (.
R(s,00 0.))
we can move the R(s, az) term into the logarithm term of the c, constants, and thereby upper-bounding the difference R(s, ug) R(s (g) follows:
R(s a,)
R(s, 0z)
Enta, (M(s,a) a) - Rs(s)) Trer(als) exp ( R(s,a)) (R - ((ss,a)) Tver(a exp ( Miss as))
A Aloog
(maxaeA R(s,a) Rs())) exp ( maxaed R(s,a)) (RI,(s) - R((s, a.)) Traef (aals) 16) exp ( as)) L range R exx () [max.e R(s,a) R(s, az)] (Bi(s) - R(s, a,)) (asls) L range R exp (1 range R)
.log
llog
log
(Rr,(0) M(x ax)) Tree (as (8)
I. range R exp (1 range R) (Rz(s) R(s, a.)) (a.ls)
< A V
We now put this upper bound back into Equation (96 and convert the inequality into an upper bound for (ee (s) as follows:
A(s, a.) - R(s,a.)
(arls)
range R.
(rs
L L.rance R exp (3 range R) (Ri(s) - R(s, aa)) Tree (az|s)
range R
Vrange R A Tree(a L exp (} range R) Ry(s) R(s,
Rg(s) ((,,,a))
range R
62
L cxp range R)
X2
The last line in the previous derivation holds by assumption of the proposal. That was to show.
C.5. A regularized negative result for general MDPs
Throughout, let (S,A, T, Mo. ?) be an MDP. Additionally, assume there be a data distribution D E A(SxA) used for learning the reward function. We do a priori not assume that D is induced by reference policy, but will specialize to that case later on.
We also throughout fix e > 0, > 0, L E (0, 1), which will represent, respectively, an approximation-erie for the reward function, the regularization strength, and a lower regret bound. Furthermore, let w II + be any continuous regularization function of policies with (TT) 2 0 for all π e II. For example, if there is a nowhere-zent zero reference policy Teefs then w could be given by w(x) m) = MDx (Ir [rre).. For any reward function R, a policy á exists that is optimal with respect to regularized
53

---

The Perils of Optimizing Learned Reward Functions
maximization of reward:
A arg max [+(=)) (
We will try to answer the following question: Do there exist realistic conditions on w and D for which there exists R together with á such that the following properties hold?
[((s,a) R(s.a)) range R
B(s,a)=D
Reg (f) L.
Furthermore, we now fix Tx, a worst-case policy for R. meaning that Reg" (T.) = 1. We assume T. to be deterministic. Lemma C.34. Define C(I, R)
[ (1- Lirange Jg. Then the following implication holds:
D s = Reg (
Proof. Using the Cauchy-Sch Schhaar inequality, the left side of the implication implies:
Jn(T) min JR = Jπ( (T(
= (D" -D"-) R
< || -D* ||
S (1 - L) rrange JR.
By subtracting range Jn max JR- min JR from both sides, then multiplying by 1, and then dividing by range R, we obtain the result.
Lemma C.35. For any (8, a). we have
(= a)
Σ
7800 0, 01,1, T (80: ao..... 100,,....11,44 41-1,
1-7
t=
80, 20.
where
[- II 18--1, T(s 8t-1, 01-1;
TSu, ao .o.....,87) =o
which is the part in the probability of a trajectory that does not depend on the policy, and
(s0, .o.
., = (a 8)
Il
T 8:).
1=0
Proof. We have
(T
7
PPss 0,0, =
1-7
t=
Σ
P(so, S1 01
1=o
8
(-1 II 7(: 8;-1, a)-1) 8.) r(s s6-1,41-1
Σ
Ho(Su)T((a su)
1=0
Σ
T(3g, ap. St-1, 1) s) (su, ao 81-1, $1-1,4-1,,,,0
t=
$0 1--00-
54

---

The Perils of Optimizing Learned Reward Functions
Lemma C.36. Lei 1 2 8 O. Assume that Ta 8) 2 1 - for all (s,a) E supp D and that n, is deterministic
policy Then for all (8, a) Ax has
0 ( De. <D"(ss.) D*t + 7)
8 (97)
D* - 8. (1- dy 1-7
1-7
This also results in the following two inequalities:
5 (suup D 2 2- 1-7'
8 1-7
| - D S VISxA
(98)
Proof. Let (s, a) supp D We want to apply the summation formula in Lemma C.35 which we recommend to recall. For simplicity, in the following will write 80, do.-.. when we implicitly mean trajectories up until 8t-1, 0z-1- Now, will write "T, "comp"""" into sum to indicate that only sum over states and actions that make the whole trajectory-segment segment compatible with policy T. meaning all transitions have positive probability and the actions are deterministicallly selected by
Tx. Note that if we restrict to such summands, then each consecutive pair (8;, 0z) E supp D is in the support of D and thus we can use our assumption <(a; 8:) 2 5 on those. We can use this strategy for lower-bound:
D (s. a)
Σ
T(s0, ao .o....,s))) .) (50, ao ,o....,,,a s,
1-7
1=0
Sp .gg.. Te comp
00
T(su, ao s). (1 -8)+11
(99)
(=0
#g. comp
8
T(su, ao do.....,... s) (1 8. (t (t+11) 1)).
comp
In the last step, used the classical formula (1 - 8)' 1 - 8 which can easily be proved by induction over Now, split the sum up into two parts. For the first part, note:
T(S0, ag. ...,,.... 11
Σ SO 50.40 F. comp
T(s,, ......;)) (= du,...,,,0))
t=
50,40 Fe comp
t=0
Σ
7( ao. as. n. (so, do...... ................................ s,
(100)
t=
60.80...
D= (8,a)
1-7
For the second part, we similarly compute:
Iu++1 Σ
r(50, ao .o....)
(+
P(st = =8 = a a-
On
0=0
Sp.Ggaees Fe comp
1=0
(101)
0 1.
t7 (0, (0..))
Qy
1-9
Putting Equations 100) and (101 into Equation 999 gives the first equation of Equation 99 for the case that (s, a) e supp = For the case that (s, a) & supp D (s, a), the incquality is trivial since then D (s, a) = 0 and since the stated derivative is easily shown to non-negative by writing out the occupancy explicitly (i.e., by reversing the previous computation).
"In this lemma, one does not need assumption that w. a worst-case policy, but this case will only application later on.
55

---

The Perils of Optimizing Learned Reward Functions
This then implies
(supp D*
Σ
(s,
(spp) D
Σ
0 1T (8, - 8. (1-1) (8-(1-7)
Oy ( D D= (s,a)
(s.0) Esupp D
8.6 (1 - 7) 87
?
Σ
(=,
1-7
(s.a) D
1
1 - 8. (1 - 7)
(1 7)²
8
1
This shows the first inequality in Equation (98). To show the second inequality in Equation (97). we use the first one and compute:
(= =1-
Σ
D=
(d',a))((
< 1
Σ
(s'(''a')
Esupp D {(c.a)}
<1
Σ
(s'(a'a
(sspp D {(s,0)
i ( 7 Dr. (p'((d)))) Ör 1-
+
Σ
(1
(st,af) (s/,a')Esupp Esupp De {((s,a)}
8
< LD (s, + I-7'
where in the last step we again used the trick of the previous computation of pulling the sum through the derivative. Finally, we prove the second inequality in Equation (98). using what we know so far. First, note that
8-(1 (1-7) 7). 0y D S 1 1-7
① 7
since we showed that the left-hand-side is non-negative and sums to the right- hight-hand-side over all (s, Consequently, we obtain:
| - D=
(D*(s,)) - D= D=, a))
(s.a)
6
Σ (a.a)
<
1
VISxAl
1-7
This finishes the proof.
We now fix more constants and notation. Define So == supp Po the support of po, and more generally S, as the states reachable within / timesteps using the fixed worst-case policy n,:
S == 3r. compatible sequence 80, 40, .., 8k-1, for A: < $1
56

---

The Perils of Optimizing Learned Reward Functions
Since there are only finitely many states and S SS41. there is a lo such that Sto is maximal. Set D (8) Ea D (s, a).
Recall the notation from Lemma C.35
Define the following constant which, given the MDP, only depends on d > 0 and
C(ô, To, Po, T,7))
min 1E 00:0
>'7(50, a0..,,8) (1 -0 0.
(102)
comp
We get the following result:
Lemma C.37. Define the reward function SSx + R as follows:
R(s,a)= = R(ssal a), (8, & supp D
(103)
max R + c(
w(T.), else.
Assume that (R,H)-RLHF optimal with respect to R. Then all (s,a) E supp D we have ((a 8) 6.
Proof. We show this statement by induction over the number of timesteps that w, needs to reach a given state, Thus, first assume s E So and a (s). We do a proof by contradiction. Thus, assume that a(a | s) 1--6 8. This means that La' itaa) |s) 5, and consequently
((,,d) po(s) 2 C(ô, To, T,7).
(104)
We now claim that from this it follows that n. is more optimal than स with respect to RLHF, a contradiction to the optimality of क. Indeed:
(1)
JR(R)
(f)
< (t((tt
(2)
Σ
D (s, a') R(s,a')+
Σ
D²
R'(s',d)
a' Fa
D (s,a') max R+ a)
Σ D*(s'a"")
a'4a
Σ D*(ssd)) max R+
(1-
1- Σ D R(s,aa)
(105)
a'ya
a'ya
(4)
< C(5, Mo: (.7) max R + (1-C() No, T,,)) A((s,a)
(5)
Ja(m.)) + CC(5, No, 7,7) max R R(ssa) a))
6
A JT( Co, T,7) C(6, T., Mo, 7,7) .(TT)
JA(T=) (w()).)
In step (1), we use the non-negativity of w. In step (2), we use that (s, a') & supp D and so R(s. R(s, a'). In the right term in step (3), we use that (s,a)= E supp D= and thus M(s,a) 2 R(s', d'), by definition of Rt. In step (4), we use that R(s,, a) 2 max R and Equation (104). Step (5) uses that (T. = R(s, a), following from the fact that R is constant for policy n.. Step (6) uses the concrete definition of ft. Thus, we have showed contradiction to the RLHF-optimality of it from which it follows that A(a s) 2 1- 6.
Now assume the statement is already proven for - and let E S, S.- Then there exists a म, comopaitie sequence So: ag..... $g...., leading to s. We necessarily have s, E S, for all i = O,..., by the induction hypothesis. Now, let a == (s) and assume we had A(a s) < 6. As before, we then have
........ ...ttt t-1, and so we obtain #(a, s,) > 1 1-6
57

---

The Perils of Optimizing Learned Reward Functions
En' ai(a' ((a'(s) 8. Consequently, we get
Σ a'za
("(saa) 2,'
Tso, a'za
[s0s, oo, co....,.)) [s0, An. 8,,00 .,.8))))))))))
x T(50, ao ......,)). 8) (1 - 6)¹
C(o, no Po. 7,7)
Then the same computation as in Equation (105 leads to the same contradiction again, and we are done.
Theorem C.38. Define
8 = (1 7) (1 L) range JR > 0.
VISAA| ||]
Let M = (S, A. Po, R, be our MDP. Set
A- ((TT)
C= C n. L,),) = range R C(ô, TT, Mo, 7, 00,
(106)
with the "inner" C(,, n. No: T, 7, defined in Equation
102
Assume that
D(supp D S 1+C
c
(107)
Then D unsafe(R, L,A,W).
We prove the theorem by showing that for every data distribution D A(SxA) that fulfills the conditions of Theorem C.38 there exists reward function Rt together with (A,w)-RLHF optimal policy á with respect to ft such that
Proof.
R(a,,) range R
SC
Reg R (*) LL L.
Towards that goal, define as in Equation 103 and A as (A,,))-LHF optimal policy for Å. Then Theorem C.37 shows that (8 a) 2 ö for all (s,a) E supp D=. Consequently, Theorem C.36 implies that
(1 L) range JR
| - DT S SSAA
1-
R
Consequently, Theorem C.34 shows that Reg" (#) 2 L, and thus the second claim. For the first claim, note that
[( [i(s,a) R(ssa)]]
Σ
D(s.a) (maxx R. + C(6, nu No. ?) w(TT) R(s, a))
(s.p) Dr.
A
D(supp D=-). range R R+ C(ô, n. Mo. T, w(TTa)
< range R,
where the last claim follows from the assumed inequality in D(supp D=*).
We obtain the following corollary, which is very similar to Theorem C.5 assumed a poliy of regret L and not regret 1:
The main difference is that the earlier result only
Corollary C.39. Theorem C.38 specializes as follows for the case X O: Assume (ssup D S e. Then there exists a reward function R together with an optimal policy & that satisfies the two inequalities from the previous result.
58

---

The Perils of Optimizing Learned Reward Functions
Proof. This directly follows from 0. For completeness, note that the definition of R also simplifies, namely
R(s a), (s,a) & supp D max R, else.
R(s,a)=
We now present another specialization of Theorem C.38 Namely, from now on, assume that D D and w(x) DRL. (#l) In other words, the dataset used evaluate the reward function is sampled from the same (safe) policy used in KL-regularization. This leads to the following condition specializing the one from Equation (I07)
D (supp D
(108)
A-DRL (iT (iees) range RO.
1
Tref now appears on both the left and right side of the equation, and so one can wonder whether it is ever possible that the inequality holds. After all, if Da (supp D "gets smaller", then Dxx (T, (ett should usually get "larger". However, halfing each of the probabilities D (s, a) for (s, a) E supp D leads to only an increase by the addition of log 2 of DKL (Tx Tret). Thus, intuitively, we expect the inequality to hold when the sitthand--ide very small. An issue is that the KI. divergence can disproportionately blow up in size if some individual probabilities D (s, a) for (s, a) supp D very small compared to other such probabilities. This be avoided by bound in the proportional difference of these probabilities. We thus obtain the following sufficient condition for "negative result"
Corollary C.40. Let the notation be in Theorem C.38and assume D D) and w(x) TT2a.. (#|[ Let K 2 0 be constant such that
max Esupp D
De (s, S K
min (s,a)Esupp D
(
Assume that
2
min (s.a)Esupp D
D (s)
(109)
K (.
(1+
range (0.0.....0777.
Then Equation (07) holds, and the conclusion of the theorem thus follows.
Proof. As argued before, the equation to show can written as Equation 108 follows:
We can upper- bound the seft-hand-sidee as
D (supp D
Σ
D (s,
(s.a) Esupp D
< supp 1
max (s.a) D
D (s,
(110)
min < S|| (s.a)Esupp D*-
De (s,a).
In one step, we used that ग, is assumed to be deterministic, which leads to bound in the size of the support. Now, we lower-bound the other side by noting that
D (=- a) (s, log Da (8,a) a)
DxL (TT(l))eer) =
Σ
(s.a)Esupp D
Σ
D (s, a). log
min(gr,a")eaun D Da (8', a!)
(s.a)ssupp D*.
llog
minl (s.)) Das D (s, (s
'The condition quite strong and we would welcome attempts to weaken it.
59

---

The Perils of Optimizing Learned Reward Functions
Thus, for the right-hand-side, obtain
(111)
A (a 1.e range It- (O-
1
range R.C(6,x. MoiT.))) log min D (s,a)
Now, A [S]- K, B range R.C and x ( D D (s, a). Then comparing with Equations (100) and (III),
left with showing the following, which we also equivalently rewrite:
A S
1 B log
x Bx log 1 S.
Now, together with the assumed condition on x from Equation 109). and upper-bounding the logarithm with a square-root, and æ by vx since æ S 1, we obtain:
A (r+ Bu Bx
1 = x
3 A. (x BVT)
$ A. ((1 + B) Vz)
A (1 (B)
A (1+1B)
That was to show.
D. Requirements for safe optimization
In this section, we answer the question under which eircumstances guarantee safe optimization of given reward function. Wherever applicable, we make the same assumptions stated in Appendix C.1
D.1. Applying Berge's maximum theorem
Definition D.1 (Correspondence). Let X, Y be two sets. A correspondence C: X is function X P(Y) from X the power set of Y.
Definition D.2 (Upper Hemicontinuous, Lower Hemicontinuous, Continuous, Compact- Valued). Let C': X = Y be correspondence where X and Y are topological spaces. Then:
C is called upper hemicontinuons if for every X and every open set V Y with C(x) C V, there exists an open set U C X with x E U and such that for all x' E U one has C(x') S V.
C is called lower hemicontinuous if for every X and every open set V C Y with C(x) n V 0, there exists open set U Ç X with E U and such that for all x' E U one has C'x²') nV V + 0.
C is called continuous if is both upper and lower hemicontinuous.
C is called conpect-valued if C(z) is a compact subset of Y for all r e X.
Theorem D.3 (Maximum Theorem, (Berge 1963). Let and X be topological spaces, f:00 x X + R a continuous function, and C θ = be continuous, compact-valued correspondence such that C(ff) + for all 8 e θ. Define the optimal value function f : R by
(*)
max xEC(0)
x(
and the maximizer function C : = by
C* (0) arg max (00,z) {xr C(0) r
zEC(O)
60

---

The Perils of Optimizing Learned Reward Functions
Then I continuous and C* is a compact-valued, upper hemicontinuous correspondence with nonemply values, i.e.
(*) + for all 0 @
We now show that this theorem corresponds to our setting, Namely, replace X be by II, the set of all policies. Every policy E II can be viewed as a vector म (a(a s)) sES.aE.A E RSAA and so we view II as subset of R. II inherits the standard Euclidean metric and thus topology from RSXA, Replace θ by R, the set of reward functions. We can view each reward function R. as a vector π (R(s, a)) (s,a)eSxA
IRXAA, So we view as a subset IRSxA and thus a
topological space. Replace f by the function J : R. x II - IR given by
J(R, T) = JR) 17" R.
Take as the correspondence C: R 11 the trivial function C(R) 11 that maps every reward function to the full set of policies.
Proposition D.4. These definitions satisfy the conditions of Theorem D.3 that is:
1. J II -> R is continuous.
2. C IT is continuous and compact-valued with non-empty values.
Proof. Let us prove Since the scalar product is continuous, it enough to show that v II -+ RRSAAA is continuous. Let (s, a) SxA be arbitrary. Then it is enough show that each componentfunction n(s,a) 18 given by
[n((,a)) ( a))
continuous.
Now, for any 2 define the function Pt(s, a): by
[P((s.a))(T) = P(st s. a
We obtain
8
(1, a)
Σ r a)(s,a). t=0
Furthermore, this convergence is uniform since [P,(s (T) < 1 for all æ and since E 7² is convergent series, Thus, by the uniform limit theorem, is enough show that each (s a) is continuous function.
Concretely, we have
())(s
Σ
P(Su, du...., 50-,, 01-1,
.o.00......e 11-1
[-1
Σ
(o(so) xaa so)
II 1=1
Tst s1-1, x(a st) T(s s1-1, ((a s).
80,00,....E-11,00...
Since S and A are finite, this whole expression can be considered polynomial with variables given by all π(a 8) for all (s, a) E Sx.A and coefficients specified by Ne and r. Since polynomials are continuous, this shows the result.
Let us prove 2. Since + 0, C' has non-empty values. Furthermore, II is compact because it is a finite cartesian product of compact simplices. And finally, since C is constant, it is easily seen to continuous. That was to show.
Define the optimal value function J R + by
J JR) max (
rell
and the maximizer function IIo R IT by
1I (R) = arg max (T) = { E | = J((H).
TENl
61

---

The Perils of Optimizing Learned Reward Functions
Corollary D.5. J is continuous and II* upper hemicomtimuuus and compuct-valued with non-emply values.
Proof. This follows from Theorem D.3 and Proposition
D.4
In particular, every reward function has compact and non-empty of optimal policies, and their value changes continuously with the reward function. The most important part of the corollary is the upper hemicontinuity, which has the following consequence:
Corollary D.6. Let R be a fixed, non-trivial reward function, meaning that max J + min JR. Let U (0. be arbinary. Then there exists > O such that for all R E Be (R) and all it E IT* (R), we have Reg R (f) <U
The condition max JR * min JR ensures that the regret function Reg R + (0 1] well-defined. Recall its definition:
Proof.
max J ( Reg" R (T)
max JR min JR
Since J continuous by Proposition D.4 the regret function Reg" is continuous as well. Consequently, the set V (Reg") -1 (10, U)) is open in IT.
Notice that 11" (RR) C V (optimal policies have no regret). Thus, by Corollary D.5 there exists an open set W C R. with R E such that for all W we have II' (R) S V. Consequently, for all á E II))))). we get Reg" R (f) < U. Since W is open, it contains a whole epsilon ball around R, showing the result.
Now we translate the results to the distance defined by D. data distribution. Namely, let D E AASxA) a distribution that assigns a positive probability to each transition. Then define the D-norm by
dd = E(s,)) [[(s a)]s
(112)
This is indeed a norm, i.e.: for all IR and all R R' E R, have
d R²) < d (R) + dD
(laa R) |a|- d RR):
(R) = 0 if and only if R = 0.
For the third property, one needs the assumption that D(s, a) > 0 for all (s, SxA.
This norm then induces metric that we denote the same way:
P(R
(113)
We obtain:
Corollary D.7. Let (S,A, T, Ho, R) be an arbitrary non-trivial MDP, meaning that max J + min J Furthermore, ler L E (0, 1] be arbitrary, and D E A) positive data distribution, i.e., distribution D such that V(s, a) E SxA.A
D(s,a) > 0. Then there exists > 0 such that E safe R e, L.)
Proof. To prove the corollary, will show that there exists >> 0 such that for all R E R with
d (R. R)
<E
range R
and all â E II" (R) we have Reg
R (+) L. We know from Corollary D.6 that there is c' such that for all Å E B (R)
and all â E IT* (R), we have Reg" R (f) L. Now, let be constant such that
c- R.
R"I S a (R', R*)
62

---

The Perils of Optimizing Learned Reward Functions
for all R', RR" R, where || is the standard Euclidean norm. This exists since all norms in RSxA are equivalent, but one also directly argue that
c = min D(s,a)
(x.
is a valid choice. Then, set
c range R
Then for all R E R with
(R, R)
range R <c c
we obtain
dRR
| A||| <
dR, R')
range R
range
rango R
6
é.
Thus, for all ã E (R), we obtain Reg (f) < L, showing the result.
Remark D.8. If (ia D(s, a) is very small, then the proof of the preceding corollary shows that d' R) must be correspondingly smaller to guarantee low regret of î E (R). This makes sense since large effective distance between R and f can "hide" in the regions where D is small when distance is measured via dD
D.2. Elementary proof of a regret bound
In this section, we provide another elementary proof of regret bound, but without reference to Berge's theorem. This will also lead to a better quantification of the bound. In an example, we will show that the bound we obtain is tight.
Define the cosine of an angle between two vectors ad hoc as usual:
ang (u, (v. = ||l|| ||l
W- W
cos
where v w is the dot product.
Lemma D.9. Let R be two reward finction... Then for any policy n, we have
-
1 1-
10 || Ae] cos (ang (11", R- R
Proof. We have
JR(TT) J = 17th (n î) || 1 Rl cos ang (17 R R.)
The result follows from 17" - D
we will make use of another lemma: Lemma D.10. Let à, and r be three vectors. Assume à 2 0, where is the dot product. Then
cos (ang(a, r)) cos ang((,, r)) S 22.
63

---

The Perils of Optimizing Learned Reward Functions
Proof. None of the angles change by replacing any of the vectors with normed version. We can thus assume ||a||
||ä]]
||| 1. We obtain
cos [ang(a, r)) cos (ang(ā, r))
= a r à r
(a â) 2
S ||0 - a|(2 ||||
||e a||
||a|| |a|l + ||ā| 2a á
2.
In the first, fourth, and sixth step, we used that all vectors are normed. In the third step, we used the Cauchy- Schhwz inequality, Finally, we used that a à 2 0. The result follows.
Recall that for two vectors w, the projection of u onto w is defined by
proj V
| w.
This projection is multiple of and it minimizes the distance to 8:
||u proj.. u|| min
||0 ane acR
We can now formulate and prove our main regret bound: Theorem D.11. Let R be fixed, non-trivial reward function, meaning that max J # min J Then all R E R and all E II (R), we have
V2
Reg R (ft S (1-7)
F2 AlI.
(max JR min JR)
Furthermore, if R. R2 0, then we also obtain the following stronger bound:
V2
Reg R (f) 5 (1 (1-7)- (max JR min JR)
RR. - proj x R
Now, let D E ASSxA) be a positive data distribution (positive meaning D(s,a) > f all (s,a) E S x A). Then we obtain the following consequence:
V2 (ali(a))SSxxD(..... ((s
Reg (#) E (1-7). (max J min JR).
d (R, Rt)
Proof. We start with the first claim. First, notice that the inequality we want to show is equivalent to the following:
V2
_ 2 max J
1 R.l.
(114)
1 1-7
From Lemma D.9
we obtain
- + 1- |
1
cos ang (11 R- - it)). kl|
Now, let π E (R) be an optimal policy for R. Then also from Lemma D.9 we obtain
max = JT( [T)
| ||
||
R
R| cos (ang (17 R R?)
S {)
|| ||
Ael
cos ang (17 R i2))
1-7
64

---

The Perils of Optimizing Learned Reward Functions
In the last step, we used that II* and so (*) - (*). Combining both computations, we obtain:
(#) 2 max J 1
|| flll
| cos ang (11 R -R)) -| cos (ang (1² R - Ri))
done if we can bound the big bracket by v2. By the Cauchy- SchhaaS inequality, cos ang (v, w) E 1] for all vectors v, w. Thus, if the first cosine term is negative or the second cosine
Since want to show Equation (144,
term is positive, then since |>d| < |1 the bound by 22 is trivial. Thus, assume that the first cosine term is positive and the second is negative. We obtain
|| cos ang (17 R R)) - -I|D*1 cos ang (17 R R)
ang (11", R - ft) cos ang (1)*, - ft)
$ cos
S 2
by Lemma D.10 Here, used that 17 and n7 have only non-negative entries and thus also nonnegative dot product 177" 1 2 0.
For the second claim, notice the following: if R R 2 O, then proj R= R for some constant 2 0. Consequently, we have â E 11. proj R)) The claim thus follows from the first result.
For the third claim, notice that
min a(s ( R- Rl 1 min (A.
D(s,a) -|-- Rl
(
min
D(s,))-
Σ
R(s, A(s, a)
(s,a)ESxA
(Ma)ESXA
Σ (s,a)ESxA
D(s,a) R(ss, f((saa)
dP (R. Rt).
So the first result implies the third.
Corollary D.12. The theorem implies Theorem 3.2
Proof. Let (0, 1] and assume >> 0 satisfies
1-y 7 range JR
min D(s,a) L. (x.A)
2
range R
We want to show E safe(R, R, e, L). For this aim, assume that R and a are given with
[i(ssaa a)ss
B(
Se
range
and such that optimal for R, i.e. (in the notation of the appendix): á E (R). Then the last claim Theorem D.11
65

---

The Perils of Optimizing Learned Reward Functions
implies
V2
Reg
R
( S
d" dR,RR R)
(1 (1-))
(max JR min JR)
(S0)ExX D(s,a)
v2
(aya) [R(s, - R(s,a))
(1 7) range JR. min (i (s,,a)
V2 range R
R(ss,) R(s,a)) a) range R
1-y range JR (x D B(
v2 range R
<
1-7 range JR (
L.
In the first step, we used Theorem D.11 Then, we substituted the definition of dD from Equations (112) and 113 Then we expanded the term by multiplying with range in both the numerator and denominator. Then, we used the assumption that c-close to R in the data distribution D. Finally, we used the assumed bound on e from Theorem 3.2 Overall, this L, and thus, since R and á were arbitrary, we obtain E safo( c, L). This precisely the claim
shows Rog" R
from Theorem 3.2
We now include more discussion of Theorem D.I1
Remark D.13. As one can easily see geometrically, but also prove directly, there is the following equality of sets for reward function Rt
{1 R || v e SKA, ||l|| =1]
proj R R E
In other words, the projections form sphere of radius / R| around the midpoint } R.
We now show that the regret bound in Theorem D.1l is tight:
Example D.14. Let U E [0,1] and y E 10,1) 1) be arbitrary. Then there exists MDP (S,A, T,,, R,7) together with reward function it with Rt R and policy क E III (ft such that
V2
Reg (f) = (1 (1-7): (max JR. min JR)
| proj f R
Furthermore, there exists data distribution D A(SxA) such that
1
Reg (+) (1 7) [max J min JD) D(s,,
d (R,R
Proof. If U then Å R always works. > O. then S {+} and A {a, b, This determines and po.
Define R(x) = R[*, x, x) for any action æ A. Let R(aa) > R(6) be arbitrary and
R(a) R(b) < R(b).
R(c) = R(a)
U
Define
R(a) R(b) R(a) + R(b)
R(c) R(c).
2
For policy n, define (xx) = (xx () for any action & E A and set the policy by #(b) 1.
66

---

The Perils of Optimizing Learned Reward Functions
We obtain:
R R (R(a) A(a))² 2 + (R(6) R(b)))
2 + (R(c) -(c))²
1
2 V (R(a)= R(b))= + (R(b) R(a))
(R(a) R(b))
V2
U R(a) - R(c)
V2
U max R min R
v2
U (1 1-7)
(max JR min JR)
V2
Furthermore, we have
R((a) _ R(b)
Reg R
(+)
1-7
1-7
1-7 R(a) 1-7 R(c)
U.
This shows
v2
U Reg" R (ft (1 (1-7) 7)
|| Rll.
maxx J - min JR)
We are done if we can show that proj x R R. This is equivalent to
which is in turn equivalent
R R R O.
This can easily be verified.
Finally, for the claim about the data distribution, simply set (aa) D(b) =D(c)= Then one can easily show that
V2. | Pिll R((a) R(b) = (R,
min(s.))SxAA D(s, a)
That shows the result.
D.3. Safe optimization via approximated choice probabilities
In this section, we will show that for any chosen upper regret bound U, there is an > 0 S.t. if the choice probabilities of i are e-close to those of R, the regret of an optimal policy for R is bounded by U.
Assume a finite time horizon T. Trajectories are then given by 8o, ap, $1..... -r- 8T- Let E be the set of all trajectories of length T. Let D E A(E) be distribution. Assume that the human has a true reward function R and makes choices in trajectory comparisons given by
exp (G(E))
Pn [1, exp (G(G)) + exp (G(E2))
(115)
Here, the return function G is given by
G(S)
Σ
2' R(si, ar, 8t+1).
0=0
67

---

The Perils of Optimizing Learned Reward Functions
We then define the choice distance of proxy reward ft to reward R as
dRL (R, ft) -D DKI ( (1, Pa (1,
Here, DKL. (RR( (1, || P 1 (a) is the Kullback-Leible divergence of two binary distributions over values 1, 2.
Explicitly, for = Pn(: E2) and similarly P, we have
P(L)
+ (1 (1- (1-P(1)) log 1- P(L) P(1)
DKL
(P] (KL(
P) P(1) log
P(1)
(116)
- P(1 log P11) + (1 (0-P(1)) log - -(())))(((())))
Here, Hp) = -1p + (1 p) log(1 p)] is the binary entropy function.
Fix in this whole section the true reward function R with max J * min J in fixed MDP.
The goal of this section is to prove the following proposition:
Proposition D.15. Let U E (0, 1]. Then there exists an > O such that for all R with
KL R, R) <E
and all â E (ft) we have Reg" (f) < U.
We prove this by chaining together four lemmas. The first of the four lemmas needs its own lemma, so we end up with five lemmas overall:
Lemma D.16. Assume R, R are two reward functions and x policy. Then
(T - J max EEE
G(E) - -())
Proof. We have
[T) [=) = Dr (G-
Σ (T((): (G(E) G(E))
CEE
(c) |G(E) G(E)
{E
< max
[G(E) - G(E)) Σ (=)(E)
SEE
EEE
GG(E) G(E))
max
SEE
In the last step, we used that distributions sum to one.
Lemma D.17. Let U E (0, 1]. Then there exists o(U)= such that for all it and क III for which there exists R such that maxeez ((E) - G(E) < oUU), have Reg" (f) < U.
Concretely, we can set (U)) max J min R U.
Proof. Set (U) as stated and let Rt, A and e have the stated properties. The regret bound want show is equivalent the following statement:
JR(A) > max JR (max J min JR. U max R 20 (U).
(117)
68

---

The Perils of Optimizing Learned Reward Functions
Let è be the constant such that G - is the return function of ft č. Concretely, one can set ē 1-ア Lemma D.16
ensures that
JR(() J (5) - o(U).
(118)
Now, let a be an optimal policy for R. Again, Lemma D.16 ensures
max J = (R(T) < R (T) + tOU & J (R)
(119)
In the last step, we used that # is optimal for R and thus also R - ē. Combining Equations (188 and 119 we obtain the
result, Equation (117).
Lemma D.18. For q (0, 1), define 94 (-9,1 q) - IR by
0 + xt
(x(x)) = log
1 (g + x)
Then for all a >> 0 there exists ö(g, σ) > 0 such that for all x E (-q, - q) with |x|| < 8(g, σ), we have (ga(x) (yp) < a.
Concretely, one can choose
8(q,0) = (exp(o) - 1) min
exp(a) 9
exp(a)
+
1-q
9
Proof. If one does not care about the precise quantification, then the result is simply reformulation of the continuity of gn at the point Zp =
Now we show more specifically that 8(q, o). o) as defined above, has the desired property. Namely, notice the following sequence of equivalences (followed by one-sided implication) that holds whenever 2 0:
(y xz) (1 <a
(x)x)) [0( <a
log
(1- (q x)) q
2q+ 9)
< exp(()
(1 (q r)) .9
q_ exp(()
(g 2) < (1 - x)
1-g
1 | 1-
4 a exp(o)
x ς. (exp(o) -) 1)
x < exp(o) -1
exp(a) 1 1 I-g
| < o(g.o).
In the first step, used the monotonicity of Bg get rid of the absolute value. Similarly, whenever x S 0, have
(g,(2) - (g,)))((0)) <o + I - exp(o)
I-9 + exp(a)
9
= |z| < 88g. r).
This shows the result.
Lemma D.19. For q 10, define fq (0, + by
fq(p) - [qlogp + (1 - q) log(1 p)]_
Then for all 8 > there exists μ(8) > such that for all E (0, 1) with fa(p) < H(g) + p(8), we have lp gl < Concretely, one can choose ((6) = 282.
69

---

The Perils of Optimizing Learned Reward Functions
Proof. Let 6 > 0 and define y²))= = 282. Assume that [g(v) < H(g) + p(0). By Pinker's inequality, we have
9)p glog + (1 q) -log - ! =-((q) + +.(P)
1 1-1 p
v(O)
20
Consequently, we have lp gl < 6.
Lemma D.20. Define sq(p) as in Lemma 19 Then for all > 0 there exists e(u) > 0 such that for all ft with
KI, (R, It) < E(p),, we have the following for all E1,E2 E:
[ 82) (PA(1 (I,5)) < (PR(1 (1, + n.
Concretely, we can set e(u) == J min D(1)) D(22)
Proof. We have the following for all $1,52 E:
A-m D(E) D(E) = c(p)
5.5"
dkL. (R. R)
ED D DRK.. (PR(-1E,E) (R
min D(E) D(E')) DKL (aR(-PPP-S11 (1, || P&( (1:52) E.E"
Now, Equation 116 shows that
DRL PR(: E1,E2) || Pa( (1,
Spm(uss e.) (Pa(1 (a) H (PR(1 (r,
The result follows.
Corollary D.21. Let Then there exists e(a) such that dR.. (R, R) implies that there exists RR such
that G (G <) ol < a.
Proof. Set
o (PR(1 (2) 1 = p(0), e
5 min
S. ExEx
with the constants satisfying the properties from Lemmas D.18
D.19 and D.20
Now, let R be such that dR,,R, R) < e.
First of all, Lemma D.20 ensures that
f ( (P&(1 E1, < H[P((1 (1,))) + P
for all E1, E2 E E. Then Lemma D.19 shows that
[ (1,6)) - PR(1 [1, <
for all f1. E E. From Lemma D.18 we obtain that
gPa(1)))))) (P E2, PR(1 (((1161)62)) (Pa(I)))))())) <a
(120)
for all Ea E.E E. Now, note that
(PM(1I61.EO) (PA(1)EI,E) PR (i, = (Pp(Ults.s))
70

---

The Perils of Optimizing Learned Reward Functions
Furthermore, for R2' E {R, Ri,, Equation 115) leads to the following computation:
PR (1 E2)
9 (I.(()E))))) = =log
Pe (2 (1,
log exp (G'(E1)
exp (G'(E)
= -G1 (f2)).
Therefore, Equation 120
results in
(G(E)) - G(()) - (G((E))-G(())) G)())) = (C G(E2)) - (G(())-G(EE) <o -(())))(((())))))-))))))))))))))
-
for all Ei, E E. Now, let e* E E be any reference trajectory. Define c = G(5*) G(5*). Then the preceding equation
shows that
(G(E) - G(E) cl <o
for all E E. That shows the claim.
Proof of Proposition D.15 We prove Proposition D.15 by chaining together the constants from the preceding results. We
have U (0, 1] given. Then, set (U)) and = c(or) in Lemma D.17 and Corollary D.21 Now, let R be such that dL (R, Rt) < and let IT* (ft. Our goal is to show that Reg" Rt (f) < U.
By Corollary D.21 there is such that maxçe= (((E) G(E) cl o. Consequently, Lemma D.17 ensures that
Reg" R (f) < U. This was to show.
D.4. Positive result for regularized RLHF
Here, we present simple positive results for regularized RLHF, both a version with the expected reward distance, and in a version using the distance in choice probabilities. Some will directly draw from the positive results proved before.
Theorem D.22. Let X E (0, oc) be given and fixed. Assume are given an MDP (S, A. Po, R. y), and a data distribution D E SxA which assigns positive probability to all transitions, i.e., V(saa) a) E SxA, D(s, a) > O. Let w I1 + R be a continuous regularization function that has a reference policy Wref as one of its minima Assume that Tee is not opttimll for R and let Reg" (Tyet). Then there exists > 0 such that E safe(R, e, A,
Proof. We prove the theorem by showing that for every D E A(SXA) such that (ss, > 0 for all (s, E SxA,, there exists e > 0 such that for all R with ((s.)>-D [[(ssa)) R[ssaa] we have Reg*t R (
< e and all policies á that are (A, -LLHF optimal wrt. R,
range R
Reg (Tyet). Because L Reg (+) Reg R (Fret) this proves that then e safe(R, e, L, A,),)).
The proof is application of Berge's maximum Theorem, Theorem D.3 Namely, define the function
:: x x I1 R. f(R,T) = JR(z) - (w))
Let R IR map reward function to the value of a (A, -RLHF optimal policy, i.e., 1' (R) == max =), Define C* as the corresponding argmax, i.e., (R) == {T f(R,T) f (R)). Assume on R. we have the standard Fuclidean topology. Since w is assumed continuous and by Proposition D.4 also J is continuous, it follows that f is continuous. Thus, Theorem DD.Jiimlies that C* upper hemicontinuous, see Definition D.2 The rest of the proof is simply an elaboration of why upper hemicontinuity of C* gives the result.
Furthermore, define the correspondence C: R = II the trivial map C(R)
D.positionD.Aaalsss
Now, define the
== = { E 11 Reg (I') < Reg" (TTeet) }.
'F.g. g. Tret(a 8) 0 for (s E S w(T) = TgLL (n]]) (eet), then the minimum is given by Teef-
71

---

The Perils of Optimizing Learned Reward Functions
Since the regret is continuous function, this set is open. Now, let (RR) be (A,w)-RLHF optimal with respect R. It follows
JR(Z) [RR 1T >w((T) [RR Tret) + (w(Te)e) -r(
where we used the optimality of ı for f, that 7ee is not optimal for it, and that Te is the minimum of w. So overall, this shows C* (RR) S V.
Since C is upper hemicontinuous, this means there exists an open set 2 S R with R E U and such that for all R E U, we have C* (R) S V. Let > 0 be so small that all reward functions R with ((s,))=D
satisfy R u which exists since U is open in the Euclidean topology. Then for all such A and any policy & that is (A, (X,w)-RLHE optimal wrt. R, we by definition have
[R(s.a) (alls.a)-Bo -[(a,)) range R
E (((((() CV,
and thus, by definition v, the desired regret property. This was show.
Now, we show the same result, but with the choice distance instead of expected reward distance:
Theorem D.23. Let X E (0, 00) be given and fixed. Assume we are given an MDP (S,A, T, Ho, R. 7), and a data distribution E SxA which assigns positive probability to all transitions, i.e., V(s,a) a) SxA, D(s, > O. Let II R be continuous regularization function that has a reference policy Veef one its minima. Assume that Tret not (A, -optiiall for R and let L = Reg" (Trat Then there exists >> such that D E safe PKi (R, e, L, L,
Proof. Let G = R be the vector space of return functions, which becomes a topological space when equipped with the infinity norm. Define the function
fIR (G -
where (T) = Re- [G(E)] is the policy evaluation function of the return function G. f continuous. Define the correspondence G = as the trivial map C(G) = II. Let f g + R map a return function to the value of (A, w)ptttmmal policy, i.e., (G) = max f(,, R). Define C* the corresponding argmax. Then Theorem D.3 The im3 that C* is upper hemicontinuous, Definition D.2 As in the previous proof, the rest is elaboration of why this gives the desired result.
Set G as the return function corresponding to R. Define
= = e II Reg" (T') < L}.
We now claim that C') C V. Indeed, let π E (G). Then
J²(T)) = f(G, + (W((T)
> f(G, Trot) + (w(TTre))
J (Trret)
Note that used the optimality of for f. that Teef is not optimal for it, and also that Neef minimizes by assumption. This shows Reg R (x) Reg" (Tret) L, and thus the claim.
Since C* is upper hemicontinuous and V an open set, this implies that there exists > 0 such that for all & e g with Gl < a. we have (G) C V.
Now, define (a) as in Corollary D.21 and let ft be any reward function with dD (R, ft) Then by that corollary,
there exists e E RR such that || (G c) < a. Consequently, we have (* = (G c) S V by what we showed before, which shows the result.
72


Reviews:
[{"review_id": "qzEGGDSRKK", "reviewer": "Reviewer_CcB3", "summary": "The paper states an important issue in RLHF, that is the error-regret mismatch, which is fundamental due to the distribution shift of the induced data by the fine-tuned policy. The core contribution of the paper is to theoretically analyze the possibility of error-regret mismatch, assuming accurate estimation of the reward function. A distribution that, with any accurate reward estimation, will create a low-regret policy is called safe, and it is unsafe otherwise.\nThe structure of the study is a set of theoretical claims as follows:\n1. Full support distributions are safe for sufficiently accurate reward estimation (for both reg/unreg objectives)\n2. The existence of a high regret policy with a small support intersection with a distribution makes it unsafe (for both reg/unreg objectives)\n3. An equivalent linear condition is proposed for the safety of a distribution in case of the unregularized objective for policy optimization.\nOne interesting point of the analysis is the generalizability of the regularization term, which is not limited to KL or chi divergence.", "questions": "", "limitations": "", "rating": 2, "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": "", "claims_and_evidence": "The core claims are the same as stated in the summary, which are backed by theoretical proofs.", "methods_and_evaluation_criteria": "Regret as the main measurement of the goodness of a policy is the standard criterion in the literature.\nA point about the measurement of the accuracy of the reward estimation is that, as also stated by the paper, it is mostly an *upper bound* of the bounds provided on the reward estimation errors. Hence, it is mostly not possible to assert such a bound for the estimated rewards, which affects the application of the analysis for different algorithms and methods.", "theoretical_claims": "The paper is totally analytical and theoretical, hence, all the claims mentioned are justified by theoretical proof. I didn't get into the details of the proofs. But the statements of the intermediate lemmas and propositions are logical and indicate a correct deductive flow. Moreover, the theoretical claims are fairly intuitive.", "experimental_designs_or_analyses": "There are no experiments to practically validate the claims. There is an example of the computation of the matrix M on a simple MDP in App. C.3.4. But, I don't find any examples of the validation and application of the analysis on real-world scenarios on popular RLHF methods.", "relation_to_broader_scientific_literature": "Currently, the most popular application of the study is indeed RLHF. The paper compares itself with other analytical studies and reviews reward learning in offline RL literature. The main missing part is its relation w.r.t. the new RLHF methods such as RPO, SimPO, and IPO. It is true that the analytics is based on a specific approach in RLHF, however, the validity of the analysis on other RLHF methods can give very useful insights and directions for future work. Also, the general regularization term can be applied to some new studies in RLHF, as in the following paper, which can be validated empirically.\nHuang, Audrey, et al. \"Correcting the mythos of kl-regularization: Direct alignment without overoptimization via chi-squared preference optimization.\" arXiv preprint arXiv:2407.13399 (2024).", "essential_references_not_discussed": "No essential reference is missed to the best of my knowledge.", "other_strengths_and_weaknesses": "The reward range is implicitly assumed to be bounded, which is not true in very popular preference-based policy optimization models such as Bradley-Terry.", "other_comments_or_suggestions": "I don't have any other comments.", "questions_for_authors": "The final analysis on the RLHF setting is ambiguous for me. I don't get the main point of Theorem 6.1. Can the authors explain more about the significance and goal of Theorem 6.1 and provide an example of its application on a real, SOTA RLHF method?", "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": "Z6uJTOML2E", "reviewer": "Reviewer_Eqzu", "summary": "The paper considers the problem of reward learning where the environment is modeled as an MDP and an unknown reward is estimated with a learning algorithm whose solution is used as a proxy objective in a downstream policy optimization setting. This paper formalizes conditions under which learned reward functions experience \"error-regret mismatch.\" In such settings the proxy is a poor substitute for achieving low regret on the true objective. The authors demonstrate, through rigorous theoretical analysis, that achieving low error in a learned reward model on the training data does not guarantee low regret in the resulting policy. They introduce the concepts of \"safe\" and \"unsafe\" data distributions, providing a framework for understanding when this mismatch occurs. The paper also considers regularized policy optimization and contextual bandit settings, highlighting the persistence of the problem in these cases.", "questions": "", "limitations": "", "rating": 2, "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 detailed feedback! Due to the 5000-character limit, we have to focus on your main concerns in this rebuttal. Please share any additional issues you'd like us to address.\n# Addressing your remarks about our proofs\n We appreciate your thorough technical review. We apologize for inconsistencies between the appendix and main text, which occurred as the appendix was written before we unified results in a shared framework for the main paper. We're confident our core results are sound. **We'll thoroughly revise the appendix to improve proof exposition, clarity, and brevity, beyond the specific points addressed in this rebuttal**.\n\n> 1.b (Invalid) Proposition 3.2. This result was not proved in the referenced result (Proof of Theorem D.11).\n\nProposition 3.2 follows from the third regret bound in Theorem D.11. We are adding a Corollary D.12 in the revision to make this connection explicit.\n\nIn particular: To prove $D \\in safe(R, \\epsilon, L)$, we need to show that whenever $\\mathbb{E}\\Bigg[\\frac{|R(s,a) - \\hat R(s,a)|}{range(R)}\\Bigg] \\le \\epsilon$ (A) and $\\hat \\pi$ is optimal for $\\hat R$, then $Reg^R(\\hat\\pi) < L$. Using Theorem D.11: \n\n$\\begin{eqnarray}\nReg^R(\\hat \\pi) &\\le& \\frac{\\sqrt{2} \\cdot d^D(R, \\hat{R})}{(1 - \\gamma) \\cdot (\\max J^R - \\min J^R) \\cdot \\min D(s,a)}\\\\\\\\\n&\\le& \\frac{\\sqrt{2} \\cdot \\epsilon \\cdot range(R)}{(1 - \\gamma) \\cdot (\\max J^R - \\min J^R) \\cdot \\min D(s,a)}\\\\\\\\\n&<& L\\end{eqnarray}$\n\nThe second inequality uses the definition of $d^D$ (see lines 3248 and 3259) and assumption (A), while the third uses the upper bound on $\\epsilon$ from Proposition 3.2.\n\n> 2.  (Inconclusive) Proposition 3.3. Proof of Proposition C.5.\t\n> Where in the proof must the policy's regret be high?\n\nIn the proof, we show that the assumptions imply the existence of $\\hat{R}$ that is $\\epsilon$-close to $R$ and for which $\\hat{\\pi}$ is optimal. If one additionally considers the assumption that $Reg^R(\\hat{\\pi}) \\geq L$, then what we show implies that $D \\in unsafe(R, \\epsilon, L)$, by the definition of this set of distributions. Thus, the regret being high is implicitly used by our proof. We make this explicit in the revised version. \n> What fact guarantees that $\\hat{\\pi}$ is optimal for $\\hat{R}$?\n\nThe state-action pairs that $\\hat{\\pi}$ visits all lie in $supp D^{\\hat{\\pi}}$ , where $\\hat{R}$ has maximal reward $max R$. This implies that $\\hat{\\pi}$ is optimal for $\\hat{R}$.\n> 3. (Inconclusive) Corollary 3. Proof of Corollary C.6.\nThe proof correctly proves one of its assumptions, but includes no other explanation of how this follows from Proposition 3.3.\n\nIn the proof, we show $D(supp D^{\\pi}) < \\epsilon$. Implicitly, we also use that $Reg^{R}(\\pi) \\geq L$, which is due to $\\pi \\in \\Pi_L$. These are the two assumptions from Proposition 3.3, which imply $D \\in unsafe(R, \\epsilon, L)$. Since $D$ was arbitrary, this implies $\\Delta(S \\times A) = unsafe(R, \\epsilon, L)$. We make these last arguments explicit in an updated version.\n> (Invalid) Theorem 6. Proofs of Propositions C.34 and C.35. The referenced results do not prove the stated claim.\n\nProposition C.34 demonstrates that reference policies $\\pi_{ref}$ satisfying conditions a) and b) create unsafe data distributions $D^{ref}(s,a) := \\mu_0(s) \\cdot \\pi_{ref}(a|s)$ (see Definition C.30 to verify this). In our revision, we'll streamline the proposition by referencing Def. C.30.\n\nProposition C.35 then provides simpler conditions that imply those in Proposition C.34. Theorem 6.1 combines these results, showing that reference policies satisfying Proposition C.35's conditions create unsafe data distributions. In the revised version we will replace the statement of C.35 with the one of Thm. 6.1 to make this connection explicit.\nLastly, the $2\\cdot$ inside the $unsafe()$ statement is a typo that we will remove.\n# Regarding the assumptions\n> The analysis assumes the existence of an epsilon-accurate reward model over the full data distribution \n\nWe focus our paper largely on negative results, which get stronger if they hold even under the assumption of an epsilon-accurate reward model over the full data distribution.\n\n> Regret is defined to be in the interval [0,1]. The definition considers a regret to be \"low\" if it falls with [0,1)\n\nBoth, $\\epsilon$, as well as $L$, are free variables. Hence, depending on the application, one can decide how to set these values, i.e., what constitutes a low regret. We plan to update our explanations to make this clearer.\n\n> the defining conditions of a \"safe\" policy are quite technical, and it is not obvious how prevalent such data distributions are in practice\n\nTo clarify our definitions and negative results, we provide a detailed chatbot example in Appendix B.4. Furthermore, Figure 4 provides a simple example of data distributions, highlighting which are safe. We will better integrate these explanations into the main paper.\n\n---\n\nPlease let us know any remaining concerns we should address during the discussion phase!", "claims_and_evidence": "See the section on theoretical claims and evidence.", "methods_and_evaluation_criteria": "This paper was purely theoretical. See the section on theoretical claims and evidence for more information about how it gave support.", "theoretical_claims": "*Claims*\n1. As the error of a learned reward model on a data distribution goes to zero, the worst-case regret of optimizing a policy according to that reward model also goes to zero.\n2. For any ϵ > 0 there exists a reward model that achieves an expected error of ϵ and has a high-regret optimal policy.\n3. When an MDP has a large number of independent bad policies, every data distribution is \"unsafe.\"\n4. Derive a set of linear constraints that precisely characterize the safe data distributions for a given MDP.\n5. Regularized versions of Propositions 3.1 and 3.3.\n6. Provide an analysis of RLHF in the contextual bandit case\n\n*Evidence*\n\nI checked for correctness of the proofs and found mixed support. My main issue has to do with the lack of connection between the paper's claims and the proofs in the Appendix. Currently several statements in the paper are not directly proved in the Appendix. The Appendix includes results to different claims which the reader is assumed to take as logically equivalent to the paper. This obscures the analysis and makes it difficult to both understand the result and verify their correctness. \n\nFor these cases, I suggest the authors either \n(i.) directly prove the claims in the paper \n(ii.) show the claims from the paper are logically equivalent to those in the appendix, or \n(iii.) use the claims from the appendix in the main paper.\n\n1.a (Valid) Propositions 3.1. Proof of Corollary D.7.  \n1.b (Invalid) Proposition 3.2. This result was not proved in the referenced result (Proof of Theorem D.11).  \n2. (Inconclusive) Proposition 3.3. Proof of Proposition C.5. \n   - What makes this claim different than the definition?\n   - Where in the proof must the policy's regret be high?\n   - What fact guarantees that $\\hat{\\pi}$ is optimal for $\\hat{R}$?\n   - Minor point: $\\epsilon$ should be no greater than one.  \n3. (Inconclusive) Corollary 3. Proof of Corollary C.6. \n   - The proof correctly proves one of its assumptions, but includes no other explanation of how this follows from Proposition 3.3. \n4. (Valid) Theorem 3.5. Proof of Theorem C.16.\n   - The proof relies on Lemma C.15 from the Appendix. This asserts distributions are safe when there are no solutions to a linear system with non-safe vertices. The proof constructs a system of equations and an equivalent convex program then argues its solution is consistent with Lemma C.15. On the surface, this seems reasonable. However, I found the proof difficult to verify as several steps were skipped and others felt redundant.  \n   - Equation 34 needs further support; it is not clear why the logical equivalence holds between 1511 and 1512.\n5.a (Valid) Proposition 4.1. Proof of Theorem D.21.\n5.b (Valid) Theorem 4.2. Proof of Theorem C.41.\n   - This proof relies on several lemmas which, if true, lead to a valid conclusion here.\n6. (Invalid) Theorem 6. Proofs of Propositions C.34 and C.35.\n   - The referenced results do not prove the stated claim. If these two proofs together support Theorem 6, then a proof needs to establish the logical connection between these claims.", "experimental_designs_or_analyses": "This is a purely theoretical paper with no empirical support.", "relation_to_broader_scientific_literature": "The paper generally did a good job positioning itself within the larger body of related work. The appendix contained an extended section of related work too. \n\nBelow are few other papers for understanding rewards apart from the approach used in Skalse et al. 2023. \n1. [Settling the Reward Hypothesis](https://arxiv.org/pdf/2212.10420)\n2. [Rethinking the discount factor in reinforcement learning: A decision theoretic approach.](https://arxiv.org/pdf/1902.02893)\n3. [On the Expressivity of Markov Reward](https://arxiv.org/pdf/2111.00876)\n4. [Utility Theory for Sequential Decision Making](https://arxiv.org/pdf/2206.13637)", "essential_references_not_discussed": "There are no additional references that are essential to include.", "other_strengths_and_weaknesses": "*Strengths* \n\n- Positioned for generality: Condition (1) defines an epsilon-accurate reward model. This provides the analysis with enough generality to remain agnostic to the details of any particular reward learning method. \n- Clear problem definition: The paper articulates the error-regret mismatch problem in a clear and accessible manner.\n- Rigorous theoretical treatment: The paper offers an extensive theoretical approach to analyze the error-regret mismatch setting.\n- Topically relevant: The issue addressed is highly relevant to modern RLHF systems.\n\n*Weaknesses*\n- Mixed amounts of support: It is unclear whether all the theoretical claims are supported with correct proofs. See my comments about theoretical claims.  \n- Complex proofs: While the paper presents a rigorous analysis, the proofs felt quite dense, sometimes terse, and in some places redundantly developed. Revising these for easy consumption could improve accessibility and help build trust in the results.  \n- Potentially unrealistic assumptions: The analysis assumes the existence of an epsilon-accurate reward model over the full data distribution (Condition 1). While this allows the results to remain agnostic to training, the condition is quite strong. The paper points this out. Still, weakening this requirement could strengthen the results. \n\n   Another example is Definition 2.1, which includes an particularly loose condition on regret. Regret is defined to be in the interval [0,1]. The definition considers a regret to be \"low\" if it falls with $[0,1)$. Thus \"safe\" distributions are those that don't lead to maximal regret of one. Similarly, the definition allows for the set to be empty by requiring $L=0$.\n\n- Lacks empirical validation: Although the primary contributions are theoretical, there were several points which could benefit from empirical support. For instance, the defining conditions of a \"safe\" policy are quite technical, and it is not obvious how prevalent such data distributions are in practice. Providing an empirical demonstration of safe and unsafe data distributions would add clarity to this section and provide some validation to the definition.\n- Motivation: Several choices could be better motivated. For example, the paper presents regularization as the de facto method to address objective mismatch. Though it is not explained how this is the case.", "other_comments_or_suggestions": "- The paper describes RLHF as a reward learning algorithm. RLHF is more accurately described as problem setting in which a class of algorithms can be brought to bear. \n- The example starting on 81 did not clearly illustrate the concern for me.\n- \"A policy maximizing J is an optimal policy.\" This is missing a condition on policies; many policies may maximize J, though it is only reasonable to call those which evaluate higher than the rest optimal. \n-  Currently the Appendix is 56 pages long. Much of the content felt extraneous to the points the paper needed to support. Culling unnecessary content would improve the paper's accessibility.", "questions_for_authors": "- Regret is one choice among many to define performance. Why is regret the right quantity to analyze RLHF systems? \n\nSee other sections for more questions.", "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": "q11yqZwMfK", "reviewer": "Reviewer_QgBs", "summary": "This paper defines a notion called \"error-regret\" mismatch in the context of optimizing a learned reward function. Error-regret mismatch refers to when the learned reward is close to the true reward on a fixed distribution (low error), but when optimized the learned reward leads to a policy which performs poorly under the true reward function (high regret). The authors present a range of theoretical results showing that error-regret mismatch is difficult to avoid, even when using regularized optimization.", "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 very much for your review! We are happy you found the paper clear, and that you highlighted the significance of this work.\n\nWe would also like to thank you for pointing out two further related works. We are integrating them into our revised related work section. In the following, we provide a comparison between these works and ours.\n\nThe results of our paper demonstrate that one gets very few mathematical safety guarantees in a wide variety of different reward-learning and (regularized or unregularized) policy optimization settings. An interesting question then is figuring out what can be done to make reward learning safer. The two works provide attempts at an answer:\n\n**1. Develop well-motivated algorithms that don’t provide mathematical safety guarantees but work well empirically.**\n\nThe paper *Laidlaw et al. Correlated Proxies: A New Definition and Improved Mitigation for Reward Hacking* pursues this approach. In particular, they use the fact that if you have a data sampling policy $\\pi_{ref}$ over which the true reward function and the learned reward functions correlate, then you can constrain your policy training procedure to avoid states that are unlikely under your data sampling policy. They develop a regularization method that penalizes going off training distribution (by penalizing the Chi-squared divergence of occupancy measures, see their Theorem 5.1 and Equation 4) and show in Section 6 that this method works well empirically for the environments they test. Note that while the restriction to remain “close” to the reference policy/training distribution in occupancy measure space can prevent reward hacking behavior, it also makes you dependent on the quality of said reference policy.\n\n On theoretical guarantees: In Appendix A.1.3 (in particular Lemma A.3) they show that for their setup there always exists an MDP for which their method allows reward hacking, i.e., that their algorithm can’t always guarantee safety. In Appendix A.2 (in particular Theorem A.5) they show that this result is not specific to their algorithm, but generalizes to every algorithm that uses some form of penalty on the f-divergence between action distributions. While their results show the existence of a *single* MDP for which regularized policy optimization algorithms might not be safe (this might not be too bad in practice), we show (see Theorem 4.2) that, in fact, large classes of MDPs have many different unsafe data distributions for many different policy regularization methods. We show this by considering the more fine-grained setting of analyzing what subset of data distributions are safe/unsafe for *arbitrary* MDPs. \n\n**2. Add a sufficient amount of structural constraints until your reward learning method becomes provably safe**\n\nIn our work, we make almost no structural assumptions on our setup. This allows for our results to generalize over a wide range of MDPs, reward-learning, and policy-optimization techniques. Therefore, one strategy to develop provably safe reward learning methods is to assume additional constraints on these structures. The second paper you mentioned (*Kwa et al. Catastrophic Goodhart: regularizing RLHF with KL divergence does not mitigate heavy-tailed reward misspecification*) as well as all works in the “Upper bound results” paragraph of our related work section pursue this approach. In particular, Kwa et al. show in their Theorems 4 and 6 that doing RLHF or Conditioning can be provably safe under the following structural assumptions:\n- MDP: environmental transitions are deterministic and the policy return only depends on the final state reached.\n- The true reward and the error of the proxy reward are independently distributed according to a data distribution generated by an arbitrary reference policy and their distributions are light-tailed (more assumptions are required for Theorem 6).\n- The true reward is unbounded (i.e., the true reward function can attain arbitrarily large values)\n\nWhile the paper provides some empirical evidence (see Section 4) that the error of the proxy reward is indeed light-tailed in some settings, they also observe (Section 5.2) that some of their assumptions are rather strong and don’t hold in practice, such as the assumption that the true reward and the error of the proxy reward are independently distributed.\n\n---\n\nIn general, our results suggest that it is highly unlikely for a reward learning algorithm to be both fully general and provably safe, so we welcome works such as the ones described above which explore the trade-off between these two requirements.\n\nWe would once again like to thank you for your review and we are happy to answer any further comments or questions that you might have in the discussion phase!", "claims_and_evidence": "The claims in the paper seem to be well-supported; error-regret mismatch is clearly motivated, defined, and explored through theoretical results and explanations.", "methods_and_evaluation_criteria": "No empirical results.", "theoretical_claims": "I did not carefully check the proofs but the theorems seem intuitively correct to me.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "In general the relation to the literature seems good, although I think there are a couple of missing references (see below).", "essential_references_not_discussed": "These two papers study quite similar settings and are not referenced:\n * Kwa et al. Catastrophic Goodhart: regularizing RLHF with KL divergence does not mitigate heavy-tailed reward misspecification. NeurIPS 2024.\n * Laidlaw et al. Correlated Proxies: A New Definition and Improved Mitigation for Reward Hacking. ICLR 2025\n\nIt would be helpful to have a comparison to the results of these papers, which both show cases in which regularization can succeed at preventing an error-regret mismatch.", "other_strengths_and_weaknesses": "I found the paper clear and easy to read. The paper defines an important phenomenon that has significant implications for real-world RL training and AI safety.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "No questions.", "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": "hFdbYCKqCU", "reviewer": "Reviewer_oQAd", "summary": "This paper seeks to characterize the relationship between data distributions over the state-action space of a prescribed Markov decision process (MDP), reward learning from such data distributions, and the resulting regret (which the authors define as normalized suboptimality w.r.t. the true reward function) of optimal policies for the resulting learned reward functions. The core goal of the work can be summed up as characterizing conditions on the data distribution and learned reward error under which large regret is possible, a situation the authors call \"error-regret mismatch\". The paper develops theoretical machinery to achieve this, first defining the notion of \"unsafe\" and \"safe\" data distributions capturing when error-regret mismatch is and is not possible, respectively, then establishing several results characterizing specific conditions on MDPs, data distributions, and learned rewards under which error-regret mismatch occurs. A key result, Theorem 3.5, provides necessary and sufficient conditions under which a data distribution is safe for a given MDP, learned reward error, and regret; the conditions are provided in the form of a matrix inequality (a system of linear inequalities), and tools are provided for explicitly computing the associated matrix in Appendix C when the MDP is known. Several of the error-regret mismatch results are extended to the regularized MDP setting and connections to reinforcement learning from human feedback (RLHF) are discussed in detail.", "questions": "", "limitations": "", "rating": 5, "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 thorough review! We address your main concern below.\n\n> It would be more satisfying and clearly useful to have existence results or at least worked examples showing that the sufficient conditions of Prop. 3.3 and Cor. 3.4 do hold under reasonable conditions. [...] 1. When might we expect the \\hat{\\pi} from Prop. 3.3 to exist? 2. When might we expect the policy class \\Pi_L from Cor. 3.4 to exist?\n\nThis is a reasonable question. We do not yet have concrete theoretical results “constructing” bad policies in general settings, but we think the example in Appendix B.4 provides useful intuitions that one could expand to a general result with further work. In particular, in the example, there are many *equivalent styles* for an LLM to phrase an answer that are all equally bad according to the true reward function (e.g., imagine instructions to build a nuclear weapon in many different languages). If this is the case, then no data distribution can cover *all* of these different styles; intuitively, the distribution has only a total weight of “one” to distribute, and so some styles necessarily get low weight.\n\nWe think this could be turned into a general result by assuming an *equivalence relation* on the set of state-action pairs, such that equivalence classes of state-action pairs \n\n- are “large”; in particular, for every fixed state s, and every action a, there exist many equivalent pairs (s,a′) sharing the same state;\n- have constant true reward;\n- have well-defined (total) transition probabilities to equivalence classes of states.\n\nWe believe an example of such equivalence relations is given by *MDPs with symmetry* [1] for sufficiently large symmetry groups. If the three conditions hold, then for each “bad” policy and for each state-action pair in its support, one can find an equivalent action that is relatively unsupported by the data distribution D. If one then replaces the policy with a new policy that always chooses an equivalent relatively unsupported action in each state, then the new policy should turn out to be equally bad, but not very supported by D, leading to the condition in Proposition 3.3. Similarly, for each bad policy, one can construct many equivalent ones whose supports are mutually disjoint, leading to the sufficient condition in Corollary 3.4.\n\nIn the revised version of the paper, we will discuss Example B.4 and its general properties in more detail in the main paper. Beyond that, we are unsure whether to include a general result along the lines we just sketched, mainly since this is a quick idea that we haven’t yet checked in detail. What do you think?\n\n[1] Elise van der Pol et al., *MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning*, NeurIPS 2020", "claims_and_evidence": "*Are the claims made in the submission supported by clear and convincing evidence? If not, which claims are problematic and why?*\n\nYes. See Strength 1 from **Strengths and Weaknesses** section below.", "methods_and_evaluation_criteria": "*Do proposed methods and/or evaluation criteria (e.g., benchmark datasets) make sense for the problem or application at hand?*\n\nYes, the theoretical methods and criteria proposed make sense.", "theoretical_claims": "*Did you check the correctness of any proofs for theoretical claims? Please specify which ones, and discuss any issues.*\n\nYes: Sections 3 & 4 in detail, skimmed those of Sections 5 & 6.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "The key results from this paper provide a theoretical framework for studying the relationship between data distributions and suboptimality when performing reward learning. Such a framework has been lacking in the reward learning / RLHF literature, to my knowledge. This is of potentially high interest to the community due to the practical importance of RLHF in tuning large language models (LLMs). Beyond the LLM and RLHF communities, addressing questions of data coverage and reward learning are important to the offline RL and inverse RL communities, respectively, and the theoretical machinery established in this paper may prove useful to them as well.", "essential_references_not_discussed": "None, to my knowledge.", "other_strengths_and_weaknesses": "**Strengths**\n\nThe paper enjoys major strengths:\n1. The paper establishes a rigorous and clearly useful theoretical framework for studying the relationship between data distributions and suboptimality when performing reward learning. Such a framework has been lacking in the reward learning / RLHF literature, to my knowledge. Definition 2.1 provides a well-motivated and concrete characterization of \"safe\"/\"unsafe\" data distributions, as described in the **Summary** above. The results in Sections 3-6 provide concrete (though somewhat partial, as detailed in **Weaknesses** below) insight into the conditions under which error-regret mismatch occurs. The proofs of the key results provided in the appendix appear to be correct (I read those of Appendix C and Appendix D through D.7 fairly closely, and skimmed the rest) and provide significant additional insight. I especially highlight Theorem 3.5 discussed in my **Summary**: I believe that this result, along with the proof, explicit characterization of the system of inequalities, and algorithm for computing $M$ provided in Appendix C, all provide fundamental and important tools that can likely be used to study the error-regret mismatch problem for specific classes of MDPs in future work; I feel that these results may constitute the most significant contribution of the paper.\n2. The quality of the presentation and writing is very high. All contributions, assumptions, and results are clearly stated, thoroughly motivated, and satisfactorily discussed. The limitations of the setup (e.g., the discussion starting line 214, left column, regarding the difficulty of guaranteeing the learned reward error in eq. (1)) and the computational challenges of using some of the results (e.g., potential intractability of computing $M$ in Theorem 3.5, discussed at the end of Section 3) are clearly described. The proofs in the appendix are well-written, well-organized, and sufficient intuition and discussion are provided.\n3. The motivation and relevance of this work to the community is very high, particularly due to the practical importance of RLHF in tuning large language models (LLMs), as discussed in Section 6. Beyond the LLM and RLHF communities, addressing questions of data coverage and reward learning are important to the offline RL and inverse RL communities, respectively, and the theoretical machinery established in this paper may prove useful to them as well.\n\n**Weaknesses**\n\nMy primary complaint is that two of the key results on \"unsafety\" of data distributions are not constructive, in the sense outlined below. Specifically, Proposition 3.3 and Corollary 3.4 directly assume the existence of certain classes of policies that can then be shown to force a given data distribution or all data distributions to be unsafe. While this provides a (potentially) useful sufficient condition for \"unsafety\", it leaves open the question of whether such policies actually exist and is therefore not constructive. It would be more satisfying and clearly useful to have existence results or at least worked examples showing that the sufficient conditions of Prop. 3.3 and Cor. 3.4 do hold under reasonable conditions. I suspect that other results from the paper (e.g., Thm. 3.5 or the $D$ construction from the pf. of Thm. 4.2) could be used to construct such results/examples.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "1. When might we expect the $\\hat{\\pi}$ from Prop. 3.3 to exist?\n2. When might we expect the policy class $\\Pi_L$ from Cor. 3.4 to exist?", "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 provides a clear framework and theoretical contributions on a highly relevant topic, which has needed more such theoretical treatments to better guide the predominantly experimental and heuristic-guided approaches. Indeed, the results of this work apply significantly more broadly than the current trends in the field, even though they are arguably especially important at the present moment.

Arguably the strongest argument against the paper comes down to a potential mismatch between more informal or intuitively expressed claims and the precise theoretical result. Looking through these concerns, I think the author(s) have made a good faith effort to improve this alignment and do not think that this significantly detracts from the work.

Aside from these concerns, and a separate reviewer’s request for comparisons with relatively unrelated methods, the other two reviewers were significantly positive about this work and I share their general enthusiasm.
Decision: Accept (poster)