Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of active reward learning in reinforcement learning. The objective is to design an algorithm that  allows the user, after limited access to a few reward queries, to not only reconstruct the reward function but also use it to produce an $\epsilon$-optimal policy. The authors assume the rewards are in $\{ 0,1\}$ and that the human feedback is random such that for any state action pair and episode step  $s,a,h$  the observed human feedback $Y$ satisfies, 

$$\mathbb{P}(Y | s,a,h) = f_h^*(s,a,h)$$

Such that $f_h^* \in \mathcal{F}$ for some known function class $\mathcal{F}$. It is further assumed that the true rewards are a thresholded version of the human feedback so that the reward of $s,a,h$ equals $1$ if $f_h^*(s,a,h) > 1/2$ and $0$ otherwise. They make use of a Massart noise assumption to ensure the learnability of this threshold function. It is possible to show that sufficient samples from the human labeler are enough to learn the thresholded reward even over all state actions in a data pool. The number of labels needed depends only on the gap $\Delta$ (from the Massart noise assumption), and the complexity of the function class $\mathcal{F}$. In short even if the dataset is large, a dataset size independent number of samples are needed to learn the reward function over all of it.

The authors then combine this result with a reward free exploration scheme to first collect sufficient data from either a tabular or a linear MDP and use it for the purpose of reward labeling. The reward labeling results described above imply that in order to learn the reward function over all the datapoints in the data batch generated by free exploration it is enough to query the rewards over a number of state action pairs only dependent on the noise condition and the size of the function class. 

They complement their discussion with some commentary on how to extend their results to the setting of offline RL.

strengths_and_weaknesses: 1) Strengths. The setting studied by the paper seems novel, and the discussion that these results may bring about would represent a welcome addition to the reinforcement learning literature. Developing theoretical understanding of HiL algorithms and how it is that in practice these algorithms do not require massive amounts of data is very important. Thus, the assumptions used in this work are not to be thought as limiting but instead as ways of developing understanding of these issues.

2) Weaknesses. The technical contribution of this work is limited. The algorithms presented and their analysis in my understanding is mainly lifted from the existing literature. The Active Reward Learning guarantees are not really novel or surprising. The reward free section lacks citations but these results are already present in the literature. 

Despite 2) I think the paper has merit because of the introduction of this setup. 




questions: I think there should be some citations in the reward free section that are missing. For example "Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation" by Weitong Zhang, Dongruo Zhou, Quanquan Gu discusses the reward free setting for linear MDPs. 

Qs
a) The margin $\Delta$ is assumed to be known. What happens if this quantity is unknown? Have the authors thought how to bypass this issue?
b) In Algorithm 1 the underlying true reward is produced by thresholding $\hat{f}$. This is a member of the covering. Is there a reason why $\tilde{F}$ is not enough? This could be better explained in the main. [ I didn't look at the appendix]

limitations: This work poses no negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Summary
-------

To better understand human-in-the-loop RL, this paper aims to provide a
theoretical understanding of the feedback required from a human to learn
a reward function. The authors proposes a provable active-learning RL
algorithm, which queries a human on feedback for its actions. The
proposed algorithm needs to query the reward function for feedback
$O(H dim_R)$ times, in contrast to standard RL algorithm which require
at least $\Omega(\text{poly}(d,
\frac{1}{\epsilon}))$. This is a purely theoretical paper, and there are
no experiments.



strengths_and_weaknesses: 
Decision
--------

Overall, I think this paper is interesting in the problem that it
studies and the theoretical results seem important. I am not an expert
in this area, however, and will tentatively rate the paper at slightly
below the acceptance threshold. The submission is held back by some open
questions, namely the comparison of the bound derived versus the bound
of standard RL algorithms. Experiments in a toy environment, with an
unknown but programmatic reward function that can be queried, would also
be nice and strengthen confidence in the importance of the derived
algorithm.

Strengths
---------

-   The problem studied, that of optimally querying a human on feedback
    for reward, is an interesting line of study that deserves a
    theoretical analysis.
-   The bound derived is surprisingly elegant, and the presentation of
    the theory is mostly readable.

Weaknesses
----------

-   Experiments in a toy environment, with some programmatic reward
    function that can be queried, would help contextualize the proposed
    algorithm and the tightness of the bound.
-   The biggest open question is how to contextualize the bound derived,
    which depends on a measure of complexity of the reward function,
    with the standard bound that depends on the complexity of of the
    transition.

questions: 
Detailed Comments
-----------------

-   Simple synthetic experiments with a programmatic reward function
    that can be queried would help elucidate the main points, and also
    enable comparisons against simple baselines.
-   The order of the number of queries needed for your algorithm depends
    on the complexity of the function class representing the reward,
    whereas the bound on \"typical\" RL algorithms dpeends on the
    complexity of the environment transition. How do these bounds
    compare for different classes of problems? I can imagine some MDPs
    with very simple transitions and complicated reward function (and
    vice-versa). How should these differences be reconciled?

Minor Comments
--------------

-   Line 122: Mistakenly refers to three phases, when it seems there are
    only two.
limitations: The conclusion section, which the authors point to, only discusses future work and not the limitations of the algorithm nor negative societal impact. As a theory paper, societal impact is difficult to ascertain. Limitations in the theoretical analysis are somewhat discussed throughout the paper, but it would be nice to see candid discussion in the conclusion on the overall limitations of this approach.
review_title: null

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: This paper aims to solve the RL problem in a setting where the rewards are initially unknown. The algorithms proceeds in two stages. First, in the exploration phase, the algorithm collects samples form the environment to learn about the transitions from state to state. Then, the algorithm queries the user about rewards for specific state-action pairs and comes up with an approximation to the optimal policy. The paper shows a bound on the sub-optimality gap on the resulting policy. The analysis is restricted to the case where the true reward is binary.

Minor points: 
 - in line 119, the definition of the norm of a function wrt. to the set does not use the set Z on the right hand side. You have to change the definition so that the summation is over the elements of Z.  
- it may make sense to briefly contrast your approach to [1] in the Active Learning paragraph of the "Related Work" section. They solve a related reward active learning problem, although in a slightly different setting (known transition model, unknown reward function). 

[1] Lindner, D., Turchetta, M., Tschiatschek, S., Ciosek, K., Krause, A. (2021) Information Directed Reward Learning for Reinforcement Learning NeurIPS 2021.
strengths_and_weaknesses: Strengths:
- The problem of finding out enough information about the reward function of an MDP to be able to come up with a close-enough idea of what the optimal policy is is a major challenge and crucial to unlock many applications of RL. This paper makes a good attempt directed towards solving this problem. 
- The theoretical results paint a complete picture of the performance of the agent trained using this method.

Weaknesses:
- There is no empirical evaluation in the main paper and evaluation in the supplementary material is very limited. This is not a deal-breaker since good theoretical papers can by viable contributions to NeurIPS even without experiments, but including them would make the submission stronger. 
- Presentation of the material is dry and dense at times. It could be improved by providing more intuitions about what the practical significance of each result is. 
questions: 1. Your analysis is restricted to RL problems where the reward is binary (1 or 0 for every state-action pair). Can you offer any intuitions about how restricted a class of problems this is? In other words, how does the set of RL problems with binary rewards compare to the set of RL problems with rewards bounded in [0,1]?
2. Can you offer any intuitions about how well your method will scale to deep RL / larger-scale benchmarks?
3. The noise margin \Delta plays a huge role when determining the required number of queries. Can you give any insights about what the values of \Delta will be for realistically large MDPs?
limitations: The authors briefly mention limitations of the approach in the conclusion, but do not discuss them at length. In my view, the biggest limitations are: (1) it is unclear how the method scales and (2) it is unclear what the noise margin will be for realistic problems (a small margin makes the required number of queries in Theorem 3 very large).

I do not see any ethical problems with this paper.
review_title: null

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 authors propose a theoretical framework for studying human-in-the-loop RL which splits the problem into a reward-free exploration phase and an active reward learning phase. The agent has no knowledge of the reward function and has to learn about the reward from a human expert. In the first phase the agent explores the environment using standard RFE methods. In the second phase the agent then queries the human about states it has encountered during exploration in order to learn about the reward. The authors study the sample complexity of this problem, comparing the sample complexity of exploration with the sample complexity of learning the reward. They propose an active reward learning algorithm and bound it's sample complexity as a function of the complexity of the reward function class. They then apply this algorithm to linear MDPs and offline RL deriving tighter sample complexity results for these special cases.
strengths_and_weaknesses: **Strengths**
- The paper provides a nice theoretical framework to think about human-in-the-loop RL.
- The theoretical results support the empirical observation that we need much less information about the reward than interactions with the environment, which is encouraging for work on RL that relies on human feedback.
- The theoretical analysis seems strong and the results all seem sound to me (I did not check the proofs)
- The application of the theoretical analysis to offline RL is particularly nice, and supports the generality of the proposed framework.
- The paper is well-written overall and well-structured.
 
**Weaknesses**
- The setup makes some strong and impractical assumptions, such as assuming binary rewards and bounded noise.
- The proposed framework of separating an exploration and an active learning phase is not novel and implicitly assumed in a lot of prior work on active reward learning. Practical work often finds that iterating between exploration and active learning is beneficial, which the theoretical framework does not capture.
- The paper could be clearer about how the theoretical framework connects to practical applications.
- The paper lacks any empirical evaluation. Having at least a small empirical evaluation of the proposed method, to see if the sample complexity results match empirical performance at least in simple experiments, would make the paper much stronger in my opinion.
questions: Would it be possible to extend the proposed framework to rewards that are not binary, and noise models that are not bounded (e.g., sub-Gaussian noise)?


 
**Minor**

- The abstract on OpenReview has an error in the Latex syntax. Also, it should be a single paragraph.
- There are some capitalization issues and inconsistencies in the references ("bellman" -> "Bellman", "markov" -> "Markov", "q-learning" -> "Q-learning", etc.)
- The paper should probably cite other work on active reward learning such as Sadigh et al. 2017
limitations: The paper would benefit from a discussion of the assumptions made for the theoretical results, in particular, binary rewards and bounded noise. It should also discuss if the approach could be extended to nonlinear rewards.

I did not find a discussion of potential broader impact of the paper.
review_title: null

Meta-review: metareview: This paper investigates human-in-the-loop RL. The framework and proposed algorithm allows an agent to reconstruct the reward function and produce a near-optimal policy after limited access to a few reward queries. The primary contributions of the work are the problem formulation, algorithm and formal results. 

All reviewers agreed on acceptance. Most importantly, there was consensus that problem setting is relevant and interesting and the math is correct. The reviewers noted the techniques used are not new and the results not surprising but the formulation is novel. This is not necessarily a bad thing. There was some discussion on some of the assumptions required (binary feedback and bounded noise). In the end there was clear consensus that the paper adds a much needed theoretical framework to HIL-RL and should inspire further algorithmic work.

Things to address for camera ready:
- all the reviewers thought it was a bad idea to have related work in the appendix. The AC agrees 
- the experiments in the appendix are easy to miss; more clearly reference them in the main text
- the text is not great in places; especially in the additions made to the paper in response to the reviewers.     
confidence: Certain
Decision: Accept