Venue: NeurIPS 2022 Conference

Reviews:

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: Inverse Reinforcement Learning (IRL) seeks to infer a reward function from demonstrations sampled from an agent acting (approximately) optimally. Unfortunately, the IRL problem is under-determined: an infinite number of reward functions will lead to exactly the same optimal policy. However, it is possible to obtain additional information when observing demonstrations from multiple experts, acting in environments that differ in transition dynamics or discount factor (but which have the same state and action space, and reward function).

This paper characterizes when this multi-expert IRL problem is or is not identifiable. The characterizations are in terms of the rank of matrices formed from the transition matrices of the different environments. In particular, Theorem 3 provides a charcterization in the two-expert, distinct dynamics case that is equivalent to that of Cao et al [1] but which is more amenable to direct validation. They derive corollaries for the three-expert case (Corollary 4) and two different discount rate (Corollary 5). There is also a key negative result (Corollary 6), showing that when there are exogeneous variables then the reward function can only be determined up to an additive function of the exogeneous variable (not a constant). They also derive stronger results in the case of a linear reward function (Theorem 7), and provide a condition suitable for estimated transition matrices (Theorem 8).

The paper concludes with Theorem 11 providing a condition for a reward function to generalize. This and other theorems are then illustrated in a brief empirical section.

 Some of these transformations -- such as potential shaping, or rescaling by a positive constant -- we might
strengths_and_weaknesses: Originality: moderate. The key result, Theorem 3, is equivalent to an earlier result due to Cao et al. Most of the other results are relatively simple applications of this theorem. However, Theorem 3 is a non-trivial restatement, and the corollaries although not technically deep are a useful set of results.

Quality: all the claims seem plausible although I have not had time to validate the proofs in detail.

Clarity: comprehensible but significant room for improvement. The actual technical description was fairly clear. But there is little to signpost the reader in the introduction, and I even found the introduction misleading in places, e.g. you refer to "reward shaping" but later it is clear you are talking specifically about *potential shaping* (but for some reason do not cite the Ng et al, 1999 paper until later).

The motivation in the introduction focusing on economics & finance also felt rather odd. With the benefit of hindsight, I suppose this is meant to foreshadow the empirical results, and perhaps rewards linear in features are also more plausible in this setting. But in general, I do not think of this as being a major application of IRL. Indeed, it seems relatively easy to hand-design a passable reward function for many financial applications, e.g. PnL minus lambda*CVAR. By contrast, it seems far more challenging to work in settings that do not have directly measurable metrics of success, such as "help the user build a house in Minecraft" (BASALT benchmark, etc).

Moreover, citations [5]-[8] seem only tangentially related (prospect theory, VnM utility theorem, etc). At best they establish the "fundamental importance" of reward functions. But not any difficulty in specifying them.

Paper would also benefit from having a conclusion section, and limitations and future work.

Significance: moderate. The matrix rank conditions are more amenable to empirical validation than prior work -- especially given the approximation condition of Theorem 8. The results for generalization are also a useful application, and notably can give guarantees of generalization even when the reward is not perfectly identifiable (depending on the environment to be transferred to).

Minor typos/grammar points I'd suggest fixing:
  - "However, [1] showed that" -- [1] is not a proper noun, should read "However, Cao et al [1] showed that". (This misuse occurs many times later on in related work, as well.)
  - "This work starts by" -- is this work [1], or your paper?
  - "maximized by the agent" -- agent is ambiguous, could refer to the policy you learn, call it demonstrator instead?
  - Line 94: R should be r (lowercase) for consistency with line 91 and 97.
  - References: some words in titles need to be capitalized, plae inside {...} in the TeX, e.g. monte carlo->Monte Carlo.

# Update after rebuttal

Thanks to the author for their detailed response. I understand the Econ motivation better now, IRL is certainly relevant for understanding human behaviour in financial transactions. I still find spotlighting this application a bit strange given that as the authors say themselves "IRL has not (yet) been used in revealed preference analysis". It'd be interesting to see work applying IRL to human financial decisions and see if it's more predictive than existing Econ models --- but this paper does not do that, so why focus on it?

I'm still not sure in what setting we'd care about reward functions up to a constant rather than up to potential shaping as we know potential shaping does not change the ranking of policies. The author response doesn't really address this point.
questions:   - Most of the results in the paper describe whether or not IRL can characterize the reward function up to a constant. But why should we care about this? Isn't it sufficient to identify it up to potential shaping, since that never changes the optimal policy or ranking of policies?
  - How might these results change if expert is not MaxEnt RL? E.g. no entropy bonus (hard optimal policy), or a different kind of suboptimality (epsilon-greedy)?
limitations: I did not see any substantive discussion of limitations of this work. One obvious limitation is it assumes a particular model of the demonstrator (MaxEnt RL). Humans, unfortunately, do not follow this idealized mathematical model. This is a limitation common with much work in this area -- but it'd be nice to at least see some discussion of how the results might vary with different demonstrator models, to get a sense of how robust these results are.

No discussion of ethical implications but I also don't see any significant negative ethical implications from this work.
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 IRL theory paper presents a new statement of an identifiability result (first shown in [1]) for recovering a reward function given observations of multiple experts with different discount factors and/or acting under different transition dynamics in tabular MDPs. This paper improves the previous result from [1] by stating the main indentifiability result as a more practically useful matrix rank condition which can be easily verified (Thm. 3). This allows the authors to extend the result to several interesting cases - such as more than 2 experts (Corr. 4), MDPs with 'exogenous variables' (Corr. 6), Linear reward features (Thm. 7), and sample estimated transition dynamics matrices (Thm. 8). The authors also show how their result can be used to derive a reward generalization result (Thm. 11) under weaker conditions, and present numerical experiments on synthetic tabular MDPs to verify their theoretical results.

I have checked the in-text derivations fairly closely and am familiar with prior theory in this area. I have not checked the proofs or extended derivations in the appendices.
strengths_and_weaknesses: # Originality

Although this paper is a re-statement of an existing result from [1] (as the author's acknowledge), this re-statement is more practically useful and enables multiple extensions, as well as numerical validation and application of the result.

# Quality

The authors have done a good job engaging with prior work. Overall, this paper is of high quality and feels solid and complete, although the paper is presently missing a conclusion section / paragraph - I encourage the authors to add one to their final submission.

# Clarity

This paper is clearly written, although some of the notation, language and definitions could be tidied up. For instance;

 * The language switches between "Markov Decision Process' (ex. line 91) and '... Problem' (ex. Line 117). Please be consistent unless these imply different things in your writing, in which case both terms should be defined.
 * Line 92 - it may clarify the definitions to explicitly state that $\mathcal{S}$ and $\mathcal{A}$ are finite.
 * Line 115 - Do you mean '[additive] constant'?
 * On line 119 and elsewhere $v$ denotes a _function_, whereas on line 137 and following it now denotes a _vector_. Please clarify the notation to disambiguate these if possible.
 * Consider annotating matrix expressions (e.g. Eq. 4) with the dimensions of each term, to help the reader understand the notation. Alternately, I suggest adding a 'bar' between the columns of block matrices such as the leftmost term in Eq. 4 to clarify the matrix contents.

The inclusion of an 'intuition' for the proof of Def. 10 (Lines 225-229) is very helpful. Please consider adding similar intuition / proof sketch text for more of your other results. This will aid less-technical readers in following the material.

Please ensure figures are legible in greyscale. E.g. consider using a log color scale for Fig 1d and 1e, as well as Fig 3e. Please include x and y axis labels for Figs 1 and 3 (I believe the axes are states and actions?).

# Significance

This paper contributes a well scoped and executed body of theory work to the IRL literature, and creates multiple opportunities for future authors to build on the results. For instance, by extending the tabular MDP results to derive probabilistic bounds in approximate IRL settings, or by applying the results in practical applications of IRL to real-world MDP problems.
questions:  * The generalization pattern from 2 experts to 3 (and beyond) is not clear to my by comparing Eq 5. and Eq. 6. I.e. I would not be able to predict the structure of the equivalent rank condition for 4 experts. Can you please clarify exactly how the rank condition generalizes as the number of experts increases beyond 3? This is particularly important as other results (Thm. 7, 11) build on this expression.

 * Line 28 - 'highly parameterized and represented by a low-dimensional set of parameters' is a little unclear - are you alluding to Deep Neural Network reward representations here?

 * Line 121 - the main advance beyond [1] is that the identifiability result is easy to verify in practice (as stated on Line 121). Can you please include a brief sketch / outline in your paper illustrating why the result in [1] is _not_ easy to verify in practice, for readers not familiar with this work.

 * Line 243 - "$T_{a_0}$ commutes with $T_a ~~\forall a \in \mathcal{A}$". It is difficult to intuit / conceptualize what this condition implies for the structure of the MDPs. Can you please provide a brief explanation of what this commutativity requirement implies for the MDP dynamics? Perhaps with a small example?
limitations: Nil comments here.
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: This paper investigates the problem of identifying a reward function (up to a constant) having access to (entropy-regularized) optimal policies of multiple experts on different environments and with different discount factors (this result was previously known only with two experts). In addition to this theoretical result, the authors provide a practical method for identifying such a reward. Finally, when assuming the reward is a linear combination of features, the authors demonstrate an interpretable reward function can be identified.
The authors present some empirical results on random matrices and grid worlds that showcase and confirm their theoretical results.
strengths_and_weaknesses: # Originality
The work seems to be largely a followup of [1], but as far as I can tell, the work is original (including theory and experiments). I went through the proofs and as far as I can tell they appear to be novel and non-trivial (e.g. not just a direct application of prior results).

# Quality
The theoretical results and proofs are of high quality and clarity. The empirical validations were done very well and properly highlighted and confirmed the theoretical results of the paper.

# Clarity
The paper was in general very well written and presented. The motivating paragraphs before each Theorem were very clear and useful in giving a high-level intuition for the results.
A few suggestions to help make the paper clearer:
* In Definition 2 I'd suggest using subscripts (instead of superscripts) for the $v^1$, $v^2$s and $T^1$, $T^2$s, as otherwise they can be confused with exponents.
*  The paragraph describing the Strebulaev-Whited environment is quite difficult to follow. Although I appreciate the authors want to add a real-world-like environment, I feel it is mostly a distraction from the paper's flow and fails to effect its intended purpose (due to lack of clarity). Indeed, the actual figures are relegated to the appendix, so the main paper only contains a (too terse) description of this non-standard environment. I would suggest moving the environment's description to the appendix as well.

# Significance
This is probably the weakest point of the paper for me. Although the authors present some high-level motivations in the first paragraph of the introduction, and then position it as resolving some of the issues with IRL, it remained unclear to me _when_ such a situation as explored by the authors would be useful. The Strebulaev-Whited environment, although less toy-ish than the grid worlds, is still quite artificial and unclear whether the situation considered (with different values of $\sigma_{\epsilon}$ has any ties to any real world situation.

These issues could have perhaps been addressed in a concluding section, but the authors chose not to include one. I would suggest removing the Strebulaev-Whited environment description (as suggested above) and adding a conclusion instead. In particular, I would suggest they clarify _when_ these methods can be useful and ideally give examples of situations where you have multiple experts operating under different environments/discount factors but with the same reward function.
questions: 1. A high-level question I had is: wouldn't it be more realistic to assume that you have multiple experts operating with different _rewards_ as opposed to different environments/discounts? I realize this is a completely different problem, but I feel it should at least be discussed when motivating the problem (see points on significance above).
2. In line 157 it says that the condition of Theorem 3 "is easier to check in practice" than Definition 2, why is this? Is it because there's no need of the $v$s? It would be good to clarify.
3. In the proof of Theorem 3 the statement "is an eigenvector of A with eigenvalue 0, and corresponds to the invariance of the optimal policy under addition of a constant to the reward function." is not clear).
4. The statement in line 586 in Appendix ("This is hence equivalent...") is not clear at all. Please add some more clarifying text or a reference to an established result (it's fine if it points to a chapter in a textbook, say).

In general, statements of the form above (which are not trivially true) should be clarified or referenced rather than left "as an exercise to the reader".

5.  In line 313, is $\beta$ essentially just the standard $\gamma$ discount factor?
limitations: I don't feel the authors added much discussion around limitations of their work; most of the discussions and results served only to highlight how their results improved on prior results. From a practical perspective it would have been nice to have a bit more of a nuanced discussion here (see points above regarding significance).

No negative societal impact of the work was provided.
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: The authors propose an approach to solving the ill-posedness of IRL by exploiting multiple experts. In particular, a necessary and sufficient condition on the expert environments is derived, and further extended in different scenarios (e.g. approximated dynamics, linearly parametrized reward). Besides a negative result, a milder generalization requirement is given such that any recovered reward suffices to train an optimal policy in a given other environment.

The work is mainly theoretical (even though the conditions are numerically verifiable), and limited by a number of strong requirements, but the results are clearly stated, their impact is well described, and the findings constitute a good contribution to the literature.
strengths_and_weaknesses: The paper is well written, and it is mathematically sound. The theoretical results are well described, their requirements clearly stated, and their impact properly discussed.

questions: 1) In Theorem 7, does the real reward need to belong to the same parametrized space of the recovered reward? Please clarify this in the text

2) The work offers only theoretical conditions to check if the expert's reward con be properly reconstructed but does not comment on how this can be done. Which IRL algorithm can be used to be sure that the recovered reward is actually compatible with the expert's demonstrations?
For example, in the numerical results, how was the reward identified?
limitations: N/A
review_title: null

Meta-review: metareview: The paper provides an investigation of conditions for recovering the reward function up to a constant from multiple experts. While the assumption that observations from multiple (entropy regularized experts) acting in different environments is quite strong, the authors did a good job in justifying and further explaining the setting in the rebuttal. While the paper is incremental, I agree with the reviewers that the paper is solid and interesting.
confidence: Less certain
Decision: Accept