A Theoretical Framework for Partially-Observed Reward States in RLHF

We are happy that you appreciate many aspects of our paper:

1. Our generalization of current RLHF models to incorporate internal states and intermediate feedback.
2. The novelty of our algorithms and the improvement our guarantees provide over existing guarantees.
3. Our new regret guarantee for GOLF and the exponential improvement that we demonstrate over existing guarantees and guarantees for model based methods under a recursive structure on internal states.
4. Our demonstration that a naive blackbox reduction fails and our whitebox reduction from cardinal regret guarantees to dueling regret guarantees.

We would like to address your qualms below. If you feel that our responses adequately address your qualms, we implore you to consider increasing your score.

Weaknesses

1. Writing: We agree with your prioritization of good writing. Despite the wealth of content in the paper, we have tried our best to fit in all relevant information in the main paper in a structured manner, while also being readable and welcoming. We try to complement every mathematically heavy definition or result with an intuitive explanation either just before or just after it. We feel that we have managed to strike a good balance between content and writing, but we are very open to feedback. Are there specific paragraphs that you found hard to follow? We are happy to address any specific concerns that you have.

2. Experiments and practicality: We would like to address your concern in three ways:

   a. Practical implications: Despite the theoretical nature of our work, we provide concrete practical takeaways in lines 522-536 in section 5.

   b. Theoretical focus: As the reviewer must have noticed, this is primarily a theoretical paper providing insights for future practical work. So, we believe that discussing the implications of our theory already completes the arc of the paper’s story. Adding a practical algorithm would be both beyond the scope of the paper and would also take too much space in an already crowded paper. While we agree that ML research should eventually lead to some real-life contributions, we believe that a theoretical paper that opens the door for future practical work is an important first step towards such a goal.

   c. Ongoing follow-up work: However, we would like to reassure the reviewer that we have ongoing practical work extending online iterative RLHF under DPO and PPO to intermediate feedback. In the intermediate feedback setting, it turns out that PPO learns the raw rewards and serves as a model-based algorithm and DPO implicitly goes through the Q function and serves as a model-free algorithm.

3. Motivation, examples and necessity are discussed in the paper: We would like to make three points:

   a. We are not combining POMDPs and RLHF: We would like to first emphasize that the paper is not combining POMDPs and RLHF at all. We work with partially-observed rewards, but as we discuss in lines 303-310, our setting is emphatically different from POMDPs and cannot be addressed using POMDP frameworks and algorithms. We discuss this further in point 4 too.

   b. Motivation and examples for PORRL are given in the paper: Figure 1 as well as lines 140-157 and lines 178-196 in section 2 are all examples of the PORRL problem, making a total of 7 fairly general examples as well as one specific example of the combination lock. The strongest example of partially-observed rewards (addressed in figure 1 and lines 140-157) is that of a human interacting with an LLM, where the internal state is the human’s emotions about the LLM’s responses or the human’s level of confidence in the correctness of the response. Feedback is received in a preferential or good/bad fashion. We also mention in lines 178-196 that the PORRL framework subsumes traditional RL, other models of once-per-episode feedback, learning reward machines, etc.

   c. Need for new algorithms discussed in the paper: We discuss in the paper why existing work cannot apply to the PORRL setting in lines 301-321. Traditional RL, POMDPs, naive history summarization, all either do not apply or are statistically inefficient. Further there does not exist an understanding of general methods that can satisfactorily utilize additional structure to internal states, like we show for model-based methods.

Thank you for your response.

I understand this paper is a theoretical work. The proposed algorithms in this paper are mainly based on algorithms in prior theoretical RL works, e.g., GOLF, which are not very implemental. Given that the motivating and application scenario of this paper is LLMs, even for a theoretical work, it is also helpful and important to provide simulations to validate their algorithms or ideas. The practical takeaways provided in this paper still look like some conjectures. It is unclear how the proposed algorithms and theoretical results can be applied to or provide insights and guidence for practice.

I tend to maintain my score currently, and will participate in the discussion with other reviewers and AC.

Thank you for engaging with our response, we are grateful for your reply. We are glad that you seem satisfied with the motivation behind our framework and the technical novelty of our work after our response. It seems like your main remaining concern is that this is theoretical work. We would like to emphasize a few additional points, and hope that you have productive discussion with other reviewers and the AC:

1. Other purely theoretical published work on RLHF: There exists other purely theoretical work (e.g. [1,2,3]) in RLHF and preference-based reinforcement learning, published at ICLR and NeurIPS previously. The work also has no experiments, and unlike us, they do not even discuss practical implications of their work. Nevertheless, the value of their theoretical contributions has been considered enough to make them worthy of publication.
2. This is an already crowded paper, cannot add experiments: As you pointed out in your own review, the paper is currently packed with a lot of content, theory and insights. It would be near impossible to add and discuss experiments, given the page constraints of ML conference papers.
3. Application of this paper to current experimental work and ongoing follow-up work: As we mentioned in our response above, we have ongoing experimental follow-up work that already demonstrates the potential of this paper to impact future practical work. While adding that experimental work to this paper would be near impossible due to space constraints, we noted in our comment that using PPO with a reward model that updates iteratively would behave like a model-based method. The experimental papers [4,5] learn such a reward model from intermediate feedback in an offline setting. We are trying to demonstrate that in the realistic online iterative setting, it is statistically (exponentially) more efficient to use DPO, which behaves like a model-free method by implicitly learning a Q-function. This insight is derived from our theoretical work in this paper, and should help us understand future experimental observations in RLHF under intermediate feedback. Such insights from our paper will help researchers make careful algorithmic choices in practice.

References

1. Is RLHF More Difficult than Standard RL? A Theoretical Perspective. Wang et al, NeurIPS 2023.
2. Provable Reward-Agnostic Preference Based Reinforcement Learning. Zhan et al, ICLR 2024.
3. Provable Offline Preference-Based Reinforcement Learning. Zhan et al, ICLR 2024.
4. Enhancing Multi-Step Reasoning via Process-Supervised Reinforcement Learning from Human Feedback. Anonymous Authors, 2024 (ACL Rolling Review submission).
5. STEP-RLHF: Step-wise Reinforcement Learning from Human Feedback. Anonymous Authors, 2024 (ACL Rolling Review submission).

We are happy that you appreciate many aspects of our paper:

1. The generality of our framework.
2. The improvement that we provide over existing regret bounds.
3. The fact that we propose the first explicit reduction converting guarantees from cardinal to dueling regret.
4. The novelty of our proposed complexity measure HABE, and its exponential improvement over existing complexity measures.

We would like to address your qualms below. If you feel that our responses adequately address your qualms, we implore you to consider increasing your score.

Weaknesses

1. Computational efficiency: We appreciate your concern about practicality, and we would like to address your concerns in three ways:

   a. Practical implications: Despite the theoretical nature of our work, we provide concrete practical takeaways in lines 522-536 in section 5.

   b. Theoretical focus: As the reviewer must have noticed, this is primarily a theoretical paper providing insights for future practical work. So, we believe that discussing the implications of our theory already completes the arc of the paper’s story. Adding a practical algorithm would be both beyond the scope of the paper and would also take too much space in an already crowded paper. While we agree that ML research should eventually lead to some real-life contributions, we believe that a theoretical paper that opens the door for future practical work is an important first step towards such a goal.

   c. Ongoing follow-up work: However, we would like to reassure the reviewer that we have ongoing practical work extending online iterative RLHF under DPO and PPO to intermediate feedback. In the intermediate feedback setting, it turns out that PPO learns the raw rewards and serves as a model-based algorithm and DPO implicitly goes through the Q function and serves as a model-free algorithm.

2. The g functions can be stochastic: We thank the reviewer for pointing this out. While the $g$ function was assumed to be deterministic for simplicity of exposition, all the theory follows verbatim if we assume that $f(\tau[h]) - E[f(\tau[h])$ is $\eta_h$ subgaussian given $\tau[h]$, even if $g$ is stochastic. We have added a footnote to this effect in line 322.

Questions

1. We are happy to answer how we tackle each challenge:

   a. Non markovian rewards and markovian transitions: In Appendix C, we decompose regret for generic model-based algorithms in a way that allows us to separate the error arising from probability transitions and that from reward models.

   b. Uniform bonus across all policies: This involves a telescoping sum trick borrowed from Lemma B.2 of [1].

   c. General function approximation for f: We adapt ideas from existing proofs involving the eluder dimension to our non-Markovian reward setting, noticing that the core notion of the eluder dimension still applies to the function classes $\mathcal{F}_h$ for $h = 1 \to H$.

2. Adding the Bellman completeness assumption: We thank the reviewer for pointing this out. We do indeed need Bellman completeness and we have modified the statement of Theorem 2 to explicitly mention this in lines 415-416.

3. Our cardinal feedback model is much more general than Bernoulli: Our cardinal feedback model is not just restricted to Bernoulli feedback. As you can see in Definition 1, our feedback is $\eta_h$ subgaussian with mean $\sigma_h(r_h)$. This includes Bernoulli 0/1 feedback, Gaussian numerical feedback, bounded stochastic feedback, and most reasonable feedback models. This subsumes feedback models in all previous papers that mention an explicit cardinal feedback model in RLHF. Our model is a direct generalization of such a model in [1, 2]. The KTO paper [3] doesn’t explicitly mention a generative model for cardinal feedback - it mentions a generative model only for preferential feedback, saying that it is emitted according to the Bernoulli distribution. The paper then defines a loss function for cardinal feedback.

References

1. Chatterji et al, 2021. On the theory of reinforcement learning with once-per-episode feedback.
2. Efroni et al, 2021. Reinforcement learning with trajectory feedback.
3. Ethayarajh et al, 2024. KTO: Model Alignment as Prospect Theoretic Optimization.

Thank you for your review! We are grateful to you for your confidence in our work, and we are glad that you appreciate:

1. The generality and novelty of our framework and modeling.
2. The technical strength of our paper.
3. The quality of our contribution to theoretical guarantees for learning from human feedback.
4. The comprehensive nature of our study of model-free and model-based approaches under both cardinal and dueling feedback.

We would like to address the two qualms raised in your review:

Weaknesses

1. Practical algorithms: We appreciate that the reviewer noticed the practical takeaways in our paper. We would like to address their concerns in two ways:

   a. Theoretical focus: As the reviewer has noticed, this is primarily a theoretical paper providing insights for future practical work. So, we believe that discussing the implications of our theory already completes the arc of the paper’s story. Adding a practical algorithm would be both beyond the scope of the paper and would also take too much space in an already crowded paper.

   b. Ongoing follow-up work: However, we would like to reassure the reviewer that we have ongoing practical work extending online iterative RLHF under DPO and PPO to intermediate feedback. In the intermediate feedback setting, it turns out that PPO learns the raw rewards and serves as a model-based algorithm and DPO implicitly goes through the Q function and serves as a model-free algorithm.

Questions

1. Query complexity: We have three parts to our response:

   a. We improve over the query complexity guarantees of [1]: In their setting, due to the known featurization $\phi$ determining rewards $r_h(s,a)$, we can show that $d_{HABE} = d_E = d$ and all covering dimensions are $d$ up to logarithmic terms. In that case, our model-free guarantees are $H^2d^2/\epsilon^2$, while theirs are $H^4d^2/\epsilon^2$. So, our guarantees are an improvement over them. On the other hand, our model-based guarantees have an extra $HS^2A/\epsilon^2$ term.

   b. We match the query complexity guarantees of [2]: Crucially, the rewards in [2] are a linear function of a featurization of the prompt $x$ and the full response $y$, without any dependence on the horizon or on the intermediate states and actions that come up while generating response. The dimension $d$ of the reward parameter in their setting would thus be much larger than $d_{E}$ or $d_{HABE}$ in our setting. If we were to restrict to their linear model and work in their once-per-episode feedback setting, then we can argue that $d = Hd_{HABE}$ and $d = Hd_E$ are the appropriate relations, in which case we recover the same query complexity guarantees as them using our analysis of GOLF. For our model-based methods, we have an extra $HS^2A/\epsilon^2$ term coming from model-learning.

   c. General query complexity: Outside of our comparison with algorithms in [1,2], the query complexity for getting feedback at $p$ points in a trajectory for $1<p\leq H$ is merely $p$ times the sample complexity of our algorithms. This is often much less than the query complexity of a once-per-trajectory feedback algorithm. For example, in the combination lock, the analysis of the model-free approach shows that we can reduce the query complexity from $H^3A^H/\epsilon^2$ for P-OMLE to $AH^6/\epsilon^2$, ignoring logarithmic terms.

References

1. Zhan et al, 2023. How to Query Human Feedback Efficiently in RL?
2. Ji et al, 2024. Reinforcement Learning from Human Feedback with Active Queries.