Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper deals with the problem of modeling human preferences in a setting where they are presented with two segments and choose to compare the two. Importantly, the authors propose that people compare the segments in terms of their values (measured by a notion of regret) instead of the total reward achieved by each segment. A regret notion---the sum of the negative advantage function value of the segment---is used to summarize the value of a segment. The advantage function is defined under an optimal policy pi^* (optimal wrt the true reward r) and the reward of interest \tilde{r}.
strengths_and_weaknesses: Strength: The paper provides a key insight that preferences are not just a function of the (instantaneous) reward of the segment of interest. Given that humans may care about the goal of a task, their preference towards different segments will necessarily be influenced by their long-term value, i.e., how these segments perform in terms of achieving the goal. The identification results presented in Section 3 nicely summarized the proposed insight. 


Weakness: The biggest weakness to me is how one can utilize this insight in practice. In particular, calculating the regret requires one to know the optimal policy under the true reward r (or at least the value and q-value function of that optimal policy under any reward \tilde{r}). In general, even if one provides an optimal policy \pi^*, the planning problem (and possibly learning problem when the transition matrix is unknown) will make the estimation of the regret very hard. As a related note, in the general framework, the regret definition under a particular optimal policy and L150 ("And regret(\sigma|r) > 0 if and only if \sigma is suboptimal") in the proof seem to only hold if one assumes there is one single optimal policy \pi^*. What if there is a set of optimal policies under the true reward r? How should one adjust the regret notion for that?

questions: Could the authors elaborate more on the setting when there are multiple optimal policies, how one should define regret in such cases, and how the results in Section 3 look like when one chooses different optimal policies to define ther regret?


-----

L63: typo in the mathematical expression
limitations: Yes, the authors have discussed the limitations and societal impact of their work in Appendix A. (When writing the above reviews, I have not read Appendix A of their paper yet.)
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies the issues of reward functions. It considers alignment on the pairs of trajectory segments from human-generated preferences. The paper finds that it is flawed that human preferences are assumed to be informed by partial return. Previous works consider the sum of rewards over a segment. The paper provides an alternative preference model based on the regret of each segment.

strengths_and_weaknesses: The paper addresses an interesting problem about human preferences. It shows that the partial return preference model can prefer suboptimal actions with lucky outcomes.
The paper also provides a method based on the regret of each segment, which is equivalent to the negated sum of an optimal policy’s advantage of each transition in the segment.
The paper also provides theoretical comparisons.

The main weakness is that the experimental results seem not to be enough. The proposed method does not provide comparison with previous methods from [9-16].
The environments are also limited. 
It would be better to provide more results.
Another weakness is that the code is not opened. It would be difficult to reproduce the results by others.

questions: What is the segment’s desirability? 
Figure 1 is a little confusing.  In Figure 1, the right segment should have a higher sum of reward according to humans’ preference.
How to define a start state of a segment? And how to define an end state of a segment?

Regret is computed based on a segment. The segment is also partial. 
What is the advantage of using regret? 
The motivation of using desirability is not clear.

limitations: It would be better to provide more results and more details about experiments.
The paper needs to compare with other baselines, such as methods using (2).
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper studies the problem of learning from human preferences. A new preference model is proposed which compares the advantage on the optimal policy between two trajectory segments. Some theoretical results are given that show the method is consistent under some assumptions and that a popular alternative is potentially not consistent. An algorithm is proposed to make use of this model. A new dataset is collected for a simulated delivery problem where workers provided preference labels for segments given to them. The proposed algorithm and model were compared with a partial return model on both a synthetic dataset and the collected dataset.
strengths_and_weaknesses: Strengths
- The proposed preference model seems new to my knowledge and makes sense algorithmically.
- The theory could be interesting although I have some reservations about correctness and the significance of one of the results.
- The algorithm seems to perform significantly better than the partial return baseline in empirical evaluations.

Weaknesses
- The presentation could be improved. Generally speaking, there are many seemingly out of place paragraphs and sections that do not seem to advance the content of the paper. For example, Section 3 is about theoretical comparisons of the learning objectives but then Section 4 abruptly is about an experimental model, but we do not even know what the algorithm looks like or how we will use the models from Section 3 at this point. This is only explained in Section 6.
- The description of the algorithm is very confusing and way too informal to the point where I am still unclear on what it is actually being done.  
    - What are the input rewards and policies? Why can they be empty sometimes?
    - Why would line 4 already estimate those? What procedure is being done to estimate these?
    - How many feature functions are necessary?
    - For the partial return algorithm, was the same framework used but the model just swapped out? How does this compare with past algorithms that use partial return? This seems important for the experimental comparison.
- The discussion of related work is quite sparse and it is difficult to place this work in the literature as a result.
- Theorem 3.1 (and Definition 3.1) is dubious. Implicitly there is an assumption that the dataset covers every $\sigma_1$ and $\sigma_2$ pair and infinite data for each one. Not just that it contains infinite data for some distribution over certain segments, which is what Definition 3.1 is ambiguous about. This only becomes apparent in the proof where this unstated fact is used. 
- I am also not convinced that Theorem 3.2 is all that significant. The setting is different from the preliminaries of the paper: to assume noiseless labels is to say that $P(\cdot | r)$ is actually not in the class of models from Section 2.2 since the softmax cannot realize this model for finite rewards. The problem is therefore misspecified, and it’s not surprising that there is an identifiability issue, considering that the KL divergence cannot even be driven to zero if the true reward function is plugged in! Note that Theorem 3.1 crucially made use of the fact that the model is realizable to prove the positive result, so I feel that this is an unfair comparison.
- The computational burden of solving potentially many MDPs to optimize the proposed preference model seems difficult to overcome.


questions: - Can the authors clarify what assumption is being made over the covariates in the dataset $D_{\geq}$ in Definition 3.1?
- In Section 4, it mentions that data was collected via two different methodologies. In the end, was data from only the second used to present the results in the end or was it a mix?
- Can the authors provide more details about how the actual segments that were presented to the labelers were generated? In the appendix it just says that certain trajectories were favored, but it’s unclear to me what that means. Were these generated by demonstrations or an algorithm? Were they generated specifically to have good coverage over the state space?

limitations: See above discussion.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper aims to learn the reward function from preferences between pairs of trajectory segments by introducing a new notion of the segment's regret that is based on the advantage function. Notable, they argue that the existing approach using the partial returns in the literature is flawed due to the lack of an identifiability property: the ability to recover the reward function underlying the preference dataset. As a result, the importance of using the segment's regret in learning the reward function from preference datasets is highlighted.

strengths_and_weaknesses: The main contribution of the paper is to introduce a new preference model based on the advantage function. The derivation of the segment's regret as the advantage function is sound and reasonable.

However, there are several weaknesses in the paper.

1, if I am not mistaken, the proposed regret model is limited to the case of deterministic policies. How is it extended to stochastic policies?

2, compared with existing approaches that use partial returns, computing the advantage function in the segment's regret is computationally expensive (as mentioned in Appendix A1). While the paper shows an approximation to reduce the computation in Section 6.1, it only works for the linear reward function. Hence, a more detailed discussion on the time complexity of the proposed regret vs. that of the partial returns is necessary, and the work needs to illustrate whether the proposed method is scalable to more practical problems, e.g., by including experiments with neural networks and larger state/action spaces.

3, if I am not missing anything, Theorem 3.1 and 3.2 are not comparable. While both partial returns and the segment's regret use the logistic function (Equation 2 and Equation 5), there is a difference in the two theorems: in Theorem 3.1, if $regret(\sigma1|\tilde{r}) < regret(\sigma_2|\tilde{r})$, $P_{regret}(\sigma_1 > \sigma_2|\tilde{r}) > 0.5$, in Theorem 3.2, if $\Sigma_{\sigma_1} \tilde{r} > \Sigma_{\sigma_2} \tilde{r}$, $P_{\Sigma_r}(\sigma_1 > \sigma_2|\tilde{r}) = 1$.
Which existing works assume/imply the latter assumption?
Furthermore, it raises the question of whether $P_{\Sigma_r}$ is indeed nonidentifiable if Theorem 3.2 has the same premise as Theorem 3.1.

4, there is no comparison with IRL methods (which often rely on the value function or the Q function instead of partial returns): intuitively how they are different, and empirically how they are different (e.g., by experimental results).

5, existing works (e.g., [9,10]), the reward function is define as a function of the state and the action or the state only (i.e., r(s,a), r(s)). Do these reward formulations affect the result in the paper?

6, there is only a toy grid world experiment (a very small state and action space, and linear reward functions) which is quite limited.



questions: Please address the weakenesses mentioned above.
limitations: The scalability of the proposed method to a more realistic environment is not demonstrated.
review_title: null

Meta-review: metareview: The submitted paper was reviewed by 4 knowledgable reviewers and the reviewers and authors enganged in intense discussions. The authors clarified many details in these discussion but could not convince the reviewers in all regards (there are still open concerns regardings the proofs and the update proofs came in rather late so that there was insufficient time for the reviewers to further interact; there concerns regarding experiments although I discounted most of those regarding to scalability as I agree with the authors in that regard to some extent; etc.). Moreover, looking at the discussions and the authors' responses, the paper would benefit from making several points more clear/improving their presentation, likely by including parts which came up in the discussions in the paper. Considering all this, I think this paper should go through another round of reviews before it should be accepted and I am recommending rejection of the paper. Please note that it was not easy to come to this decision - there are some important insights and experiments in the paper which should be made available to the community asap. Thus I would honestly encourage the authors to improve their paper considering the reviewers' comments and take-aways from the discussion and submit a revised version of the paper at one of the upcoming conferences. I am already looking forward to seeing an improved version of the paper being published.
confidence: Less certain
Decision: Reject