A Theoretical Framework for Partially-Observed Reward States in RLHF

Authors: Chinmaya Kausik, Mirco Mutti, Aldo Pacchiano, Ambuj Tewari
Primary area: reinforcement learning
Keywords: reinforcement learning, learning theory, reinforcement learning theory, reinforcement learning from human feedback, eluder dimension, partial observability

Abstract:
The growing deployment of reinforcement learning from human feedback (RLHF) calls for a deeper theoretical investigation of its underlying models. The prevalent models of RLHF do not account for neuroscience-backed, partially-observed "internal states'' that can affect human feedback, nor do they accommodate intermediate feedback during an interaction. Both of these can be instrumental in speeding up learning and improving alignment. To address these limitations, we model RLHF as reinforcement learning with partially observed reward-states (PORRL). We accommodate two kinds of feedback &mdash; cardinal and dueling feedback. We first demonstrate that PORRL subsumes a wide class of RL problems, including traditional RL, RLHF, and reward machines. For cardinal feedback, we present two model-based methods (POR-UCRL, POR-UCBVI). We give both cardinal regret and sample complexity guarantees for the methods, showing that they improve over naive history-summarization. We then discuss the benefits of a model-free method like GOLF with naive history-summarization in settings with recursive internal states and dense intermediate feedback. For this purpose, we define a new history aware version of the Bellman-eluder dimension and give a new guarantee for GOLF in our setting, which can be exponentially sharper in illustrative examples. For dueling feedback, we show that a naive reduction to cardinal feedback fails to achieve sublinear dueling regret. We then present the first explicit reduction that converts guarantees for cardinal regret to dueling regret. In both feedback settings, we show that our models and guarantees generalize and extend existing ones.

Decision: accept (poster)
Reviewer scores: 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1730257581164

thread_type:
official_review

<thread_object>
creator: reviewer_exhp

<content>
summary:
This paper studies the problem of reinforcement learning with partially observed reward-states (PORRL). The authors accommodate two kinds of feedback – cardinal and dueling feedback. The authors first demonstrate that PORRL subsumes a wide class of RL problems, including traditional RL, RLHF, and reward machines. For cardinal feedback, the authors present two model-based methods (POR-UCRL, POR-UCBVI). The authors give both cardinal regret and sample complexity guarantees for the methods, showing that they improve over naive history-summarization. The authors then discuss the benefits of a model-free method like GOLF with naive history-summarization in settings with recursive internal states and dense intermediate feedback. For this purpose, the authors define a new history aware version of the Bellman-eluder dimension and give a new guarantee for GOLF in the setting of this paper, which can be exponentially sharper in illustrative examples. For dueling feedback, the authors show that a naive reduction to cardinal feedback fails to achieve sublinear dueling regret. The authors then present the first explicit reduction that converts guarantees for cardinal regret to dueling regret. In both feedback settings, the authors show that the proposed models and guarantees generalize and extend existing ones.

strengths:
1.	The authors introduce PORRL, which generalizes current RLHF models to incorporate “internal states” and intermediate feedback.
2.	The authors design model-based optimistic algorithms that, POR-UCRL and POR-UCBVI, and provide regret guarantees under naive history-summarization. The authors further show that their guarantees subsume and improve over past results. 
3.	The authors study the model-free algorithm GOLF, applied using history-summarization. The authors establish a regret guarantee for GOLF. The authors also show that when internal states have a recursive structure, their guarantee can be exponentially smaller than existing guarantees and guarantees for their model-based methods.
4.	The authors show that a naive blackbox reduction from dueling to cardinal PORRL always fails. They design a whitebox reduction from dueling PORRL to a large class of optimistic algorithms for cardinal PORRL.

weaknesses:
1.	The writing of this paper needs improvement. This paper is too dense, and hard to follow.
2.	There is no experiment provided. It is hard to validate the effectiveness and implementability of the proposed algorithm, and the provided theoretical results.
3.	The authors should elaborative more on the motivation of combining POMDPs and RLHF, e.g., give 1-2 concrete application scenarios.
4.	The authors should discuss more on the technical novelty in combining POMDPs and RLHF. It looks like a combination of existing POMDP works and preference feedback.

questions:
Please see the weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694307552

thread_type:
official_review

<thread_object>
creator: reviewer_4dew

<content>
summary:
This paper provides a general formulation for RLHF by introducing humans' internal states. This new framework allows reward and policy to be non-Markovian but still tractable. The authors propose algorithms for both cardinal and dueling feedback and obtain improved regret compared with previous methods. Interestingly, to design model-free algorithms for cardinal feedback, the authors introduce a modified Bellman-eluder dimension, which can be exponentially smaller than the standard Bellman-eluder dimension for the combination lock example. In the end, the authors also propose the first explicit reduction that converts guarantees for cardinal regret to dueling regret.

strengths:
1. This paper provides a general RLHF framework covering many important instances.
2. The proposed algorithms lead to improved regret compared with existing results,
3. The authors propose the first explicit reduction that converts guarantees for cardinal regret to dueling regret.
4. A new complexity measure called HABE is proposed, which can be exponentially smaller than the standard Bellman-eluder dimension for the combination lock example.

weaknesses:
1. The proposed algorithms follow existing frameworks, which are generally computationally inefficient.

2. This paper assumes the internal state generation function $g$ is deterministic. Although this seems reasonable for rigorous math reasoning, it may not capture the complexity of human feedback for more ambiguous casual conversations.

questions:
1. On Page 7, three main technical challenges for model-based algorithms are mentioned. Could the authors give brief explanations of how the new design tackles these challenges?

2. The model-free algorithms follow GOLF, which requires Bellman completeness (BC). Does the adaptation here also need BC? If so, I think it is better to explicitly mention it in the main text.

3. For cardinal feedback, the paper assumes it is emitted according to a Bernoulli distribution. Is this assumption also used in previous papers for cardinal feedback? It seems the KTO paper utilizes a more complex feedback model?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730852020164

thread_type:
official_review

<thread_object>
creator: reviewer_rhuq

<content>
summary:
The paper introduces PORRL a framework that adds internal states and intermediate feedback into Reinforcement Learning from Human Feedback, which can speedup alignment. The authors provide two model-based algorithms POR-UCRL, POR-UCBVI for learning with cardinal feedback, and provide regret bounds for GOLF (a prior model-free algorithm) based on a new history aware bellman eluder dimension “HABE”. They also provide a reduction from duelling to cardinal PORRL.

strengths:
- The PORRL framework is novel, and their modelling is highly general with non-Markovian transitions. The paper is technically solid and a good contribution in the space of theoretical guarantees for learning from Human feedback.
- The authors analyse both model-based and model-free algorithms with regret guarantees under cardinal and duelling feedback.

weaknesses:
The practical takeaways in the conclusion are mainly phrased as conjectures, and the authors do not provide a concrete algorithm within the PORRL framework. Given the strong theoretical contributions, a practical algorithm would have strengthened the work further.

questions:
Intermediate feedback at each step requires substantially more human queries than single preferential feedback at the end of an episode. Can you compare your framework's query complexity compared to that in [1, 2]?

[1] How to Query Human Feedback Efficiently in RL?

[2] Reinforcement Learning from Human Feedback with Active Queries
</content>
</thread_object>

</thread>
<thread>
creation date:
1732202488896

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Responses to Reviews Added, Paper Updated on OpenReview

comment:
We are grateful to all the reviewers for taking out time to review the paper. We have responded to all the reviews and we want to highlight that while we explicitly mention this in one review, we have made minor updates the paper on OpenReview. **All line numbers mentioned in our responses to reviews are with respect to the new version of the paper on OpenReview.**

If the reviewers feel that our responses adequately address their qualms, we implore them to consider increasing their scores.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies a formulation for RLHF by considering reinforcement learning with partially observed reward-states. Under cardinal and dueling feedback, the authors propose new algorithms and obtain improved guarantees compared with previous methods. These theoretical contributions could be of interest to the RL theory community. 

The main weakness of the paper is the lack of empirical evaluations. 

Given that this paper is technically solid with strong theoretical contributions, I do not think the lack of empirical evaluations is significant enough to prevent this paper being accepted. Therefore, I would recommend acceptance.