Thank you for your thorough review! We address your main concern below.

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?

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

We 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

• are “large”; in particular, for every fixed state s, and every action a, there exist many equivalent pairs (s,a′) sharing the same state;
• have constant true reward;
• have well-defined (total) transition probabilities to equivalence classes of states.

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

In 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?

[1] Elise van der Pol et al., MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning, NeurIPS 2020

Thank you very much for your review! We are happy you found the paper clear, and that you highlighted the significance of this work.

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

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

1. Develop well-motivated algorithms that don’t provide mathematical safety guarantees but work well empirically.

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

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.

2. Add a sufficient amount of structural constraints until your reward learning method becomes provably safe

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

• MDP: environmental transitions are deterministic and the policy return only depends on the final state reached.
• 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).
• The true reward is unbounded (i.e., the true reward function can attain arbitrarily large values)

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

---

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

We 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!

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.

Addressing your remarks about our proofs

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.

1.b (Invalid) Proposition 3.2. This result was not proved in the referenced result (Proof of Theorem D.11).

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

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

\begin{eqnarray} Reg^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)}\\\\ &\le& \frac{\sqrt{2} \cdot \epsilon \cdot range(R)}{(1 - \gamma) \cdot (\max J^R - \min J^R) \cdot \min D(s,a)}\\\\ &<& L\end{eqnarray}

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

2. (Inconclusive) Proposition 3.3. Proof of Proposition C.5. Where in the proof must the policy's regret be high?

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

What fact guarantees that $\hat{\pi}$ is optimal for $\hat{R}$?

The 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}$.

3. (Inconclusive) Corollary 3. Proof of Corollary C.6. The proof correctly proves one of its assumptions, but includes no other explanation of how this follows from Proposition 3.3.

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

(Invalid) Theorem 6. Proofs of Propositions C.34 and C.35. The referenced results do not prove the stated claim.

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

Proposition 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. Lastly, the $2\cdot$ inside the $unsafe()$ statement is a typo that we will remove.

Regarding the assumptions

The analysis assumes the existence of an epsilon-accurate reward model over the full data distribution

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

Regret is defined to be in the interval [0,1]. The definition considers a regret to be "low" if it falls with [0,1)

Both, $\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.

the defining conditions of a "safe" policy are quite technical, and it is not obvious how prevalent such data distributions are in practice

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

---

Please let us know any remaining concerns we should address during the discussion phase!