The Perils of Optimizing Learned Reward Functions: Low Training Error Does Not Guarantee Low Regret

The paper studies learning-theoretic challenges related to reward modeling in RL. More specifically, it examines how the regret of an RL algorithm responds to errors in the reward model. It demonstrates that the regret diminishes as the error vanishes. Conversely, with a fixed error, the regret can become large. The authors refer to this property as error-regret mismatch. The analysis extends to RL with regularization techniques, including RLHF.

The paper studies the problem of reward learning: given a data distribution, and assuming that the learner enjoys a guarantee bounding the error over the data distribution of the form

$E[|R(s,a)-\widehat R(s,a)|/R_{max}] \le \varepsilon,$

the authors are interested in understanding how good the policy $\widehat \pi$ corresponding to $\widehat R$ is w.r.t. the true MDP.

To this aim, the authors provide several results, most of the negative. Indeed, since the visiting distribution of the optimal policy may be very different from the distribution of $D$ from which state-actions are sample during the learning of the reward, having a relatively small $\varepsilon$ does not guarantee small "regret" (as the authors define it). Controversely, there are examples where, in order to get a small regret, $\varepsilon$ needs to be of order $(S\times A)^{-1}$.

The authors then study the case of deriving, from $\widehat R$, a policy that is regulared, rather than the optimal one relative to $\widehat R$. Also in this case, a low reward error does not guarantee low regret, as proved in Theorem 4.2.

The paper closes with a discussion about the impact of these results the RLHF, and in particular to Large Language Models.

This paper theoretically studies the conditions that when learned reward models in RL will and will not lead to large regret in policy optimization. It shows that if the reward model's expected test error is suffient small (with respect to a threshold provided), then it would lead to low regret during policy optimization; otherwise, there are cases it would lead to large regret. The theoretical results highlight the need for careful consideration when employing learned reward functions in policy learning and underscore the importance of advanced reward function design.

This paper investigates the theoretical challenges of using a learned reward function in policy optimization, particularly focusing on the "error-regret mismatch" problem—where a learned reward function has low expected error on a given data distribution. Yet, the resulting policy incurs high regret when evaluated against a true reward function. This issue primarily arises from the distributional shift. To frame the problem, the authors define "safe" and "unsafe" data distribution for any given MDP. A data distribution is classified as safe if any reward function with low expected error will reliably produce a low-regret policy. They provide theoretical analysis across both unregularized and regularized policy optimization scenarios, reaching consistent conclusions. The paper’s key theoretical insights are: (1) ensuring low regret may require prohibitively low expected error on the learned reward function, and (2) in certain large MDPs, all data distributions might inherently be unsafe.

Dear reviewers,

We would like to thank you all again for your extensive feedback! We have just uploaded a major revision of our paper in which we have tried to incorporate all of your feedback. For your convenience, we marked all the parts we changed with blue font. Some highlights:

• The "Related work" section has been completely rewritten.
• The "Discussion" section has been substantially revised.
• Appendix B3 has been newly added and contains a discussion about using the mean-squared error as an alternative distance measure.
• Appendix B4 has been newly added and contains a conceptual example of overoptimization concerns.

We have aimed to carefully address each of the concerns raised while preserving the underlying methodology and findings. We welcome your feedback and are happy to answer any questions you may have.

Kind regards, the authors

Dear reviewers,

we want to remind you to please respond to our rebuttals before the reviewer-deadline in around 26 hours. We have tried our best to respond to all concerns and would like to hear how this affects your view of our work.

We especially want to encourage reviewers Ap9u and e9u2 to respond, sind you have not reacted yet to any points in our rebuttals. Additionally, we encourage nHaB and ATno to respond to the continued discussion and new information.

Best wishes, the authors.

Summary This work investigates how reward learning errors impact policy optimization regret, addressing a critical issue in the current reinforcement learning (RL) literature. Specifically, the authors identify conditions under which low reward learning errors can ensure low policy optimization regret. These conditions, while conceptually significant, have not been formally summarized in previous works.

Strengths

• The problem studied is well-motivated, and its intuition is clearly conveyed.
• The technical proofs supporting the results are rigorous and sound.

Weaknesses: A significant limitation of the paper is the lack of a clear connection to existing literature on hardness results in offline and inverse RL. Several reviewers have raised this concern. The classical concept of "coverage" is a well-established measure of learning difficulty in offline RL. While this work introduces a "safety distribution" notion to derive its hardness results, it implicitly relies on several coverage-related conditions. However, the relationship between the proposed safety distribution and the existing coverage assumptions is not explicitly or comprehensively discussed. Since this work is primarily theoretical, the absence of a detailed comparison with prior approaches undermines its contribution and makes it harder to justify its acceptance.

Decision: Reject. While the technical content is solid, the lack of formal comparisons and connections to existing notions like coverage detracts from the paper’s completeness and impact.

Reject