Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: - This paper proposes one main method EPIC to measure the differences between the reward functions of MDPs, and two weaker baselines methods NPEC, ERC. The methods are useful in directly comparing two different reward functions on a common MDPs, without running RL algorithms and comparing the resulted performance. 
- To me, the proposed approach is novel and interesting, and there is no similar previous work to my best knowledge, so I tend to give it an accept. 
- There are extensive experiments, but most of them are still based on hand-designed reward, and to judge whether the distance measure is good or not, it is still largely based on human judgement.  In Table 2, there is some experiment showing some correspondence between the "distance to ground truth" and the "return". The result shows some effect of all three proposed approaches. 
- You're now comparing the reward functions directly in the "reward space". But very different reward functions might still give similar optimal policies, and make the resulted performance similar.   Is it possible to compare the reward functions by inferring the similarity between the optimal policies (and without resorting to a RL algorithm)?  What's the pros and cons of this direction and your current direction? 

============ after rebuttal =============

Thank you for the response and revision, and I am sorry for my late response.  One experiment that I can think of to get around the issue of failure in RL optimization is to consider simple examples where RL algorithms can surely find the global optima.  This is the case for the tabular setting (like your GridWorld). This can be a proof of concept, but I admit that it might also be limited. So I think it is okay to keep your current presentation. 
review_title: Marginally above acceptance threshold

final_score: rating: 7: Good paper, accept
review_content: Summary:

The paper introduces a pseudometric on reward functions, EPIC (Equivalent-Policy Invariant Comparison), based on the potential-based reward shaping (Ng. 2020). It formally analyzes the EPIC distance in detail and demonstrates its usefulness in comparing learned reward functions without the necessity of optimizing reward-specific policies. The empirical results show that the EPIC is more predictive of the policy returns than some baseline variants and robust to visitation distributions, even in unseen test environments. 


Pros: 

-- This paper proposes and analyzes a theoretically grounded distance metric to evaluate learned rewards. It has several properties appealing to practical RL tasks. The EPIC pseudometric does not rely on policy optimization, which differentiates it from previous approaches. Moreover, EPIC is computable over arbitrary visitation distributions, making EPIC flexible in various practical scenarios. Finally, EPIC provides bounds on the policy performance difference when the visitation distributions meet some constraints. 

-- EPIC can significantly impact the reward learning/design-related communities because it is the first rigorous approach to evaluating candidate reward functions against the ground truth reward function without direct or indirect policy optimization. 


Cons: 

-- The claimed property that EPIC bounds the difference in policy returns relies heavily on the visitation distribution. It seems that the capability of EPIC to provide relevant information mostly comes from the visitation distribution. It would be helpful if there are some additional discussions about the EPIC's predictive power when this kind of reliance could be problematic. Moreover, the claim focuses on the upper bound of the difference. In some cases, it could also be helpful to know the lower bound of the policy-return difference if the EPIC value is big enough.

-- The theoretical derivations and analyses of EPIC are the most substantial parts of the paper.  Some additional experimental studies on domains with high-dimension perceptions would strengthen the paper's contributions and provide more guidance in adapting EPIC.



In section 6.3, all three metrics degenerate significantly in the mixture case. Why does the predictive power of EPIC decrease in this mixture setting?  

review_title: Interesting work on measuring the rewards without policy optimization

final_score: rating: 7: Good paper, accept
review_content: 
##########################################################################

Summary:
 
The paper introduced Equivalent-Policy Invariant Comparison (EPIC) pseudometric to compare different reward functions directly without training a policy function. The authors provide an interesting direction for inverse reinforcement learning. The EPIC distance gives a bound on the regret between policies optimizing for one of the two reward functions relative to the other. The authors also conduct a didactic example to demonstrate efficacy.

##########################################################################

Reasons for score: 
 
Overall, I'd vote for acceptance for the paper. The paper is well written and well-motivated. I find the topic is interesting and worth researching. The paper gives a deep analysis of EPIC in a reasonable setting.  However, my concerns lie on the feasibility : 
1) it is not clear to me what the computation cost of distance in high-dimension environments is. 
2) the visitation distribution D should have adequate support for every state; however, in most IRL settings, the demonstrated policy could be bias. How does EPIC apply under such settings?
  
##########################################################################
Questions during the rebuttal period: 
 
Please address and clarify the concerns above.
review_title: Recommendation to Accept

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: **Summary of decision**

The problem setting is significant and the approach is original. The work provides both clear theory and experiments in favour of EPIC to compare reward functions. I currently am leaning towards a marginal rejection because of theoretical issues I've outlined below, but would happily raise my score if they were addressed. Adding additional experiments that I outline below would increase the score further, but fixing the theoretical issues are primary. 

**Pros**

A gap in the literature of learning and evaluating reward functions is clearly identified and an explicit argument is made in favour of searching for alternatives to the rollout method. 

I really appreciated the serious attempt to develop baselines in section 5, based on a couple of intuitive notions for a desirable pseudometric. A substantial portion of the appendix is devoted to proving properties of the baselines!

The theoretical results are well-presented and comprehensive. I found especially significant the regret bound in Theorem 4.9; in light of this theorem, we have the practical consequence that minimizing EPIC distance closes the gap between optimal policies of different reward functions. I have verified the proofs for correctness and have found issues which I note below. These issues, however, seem quite fixable, and I would certainly increase my score upon seeing a revised version with the fixes.

I enjoyed the discussion of the theory and it's motivation: I especially liked how the validity of the triangle inequality is tied to being able to measure how well one is doing wrt the original reward by using a proxy. 

The experimental questions are precise and the experiments to answer them clearly designed. Rather than focus on chasing some benchmarks, I like that the work analyzes the proposed algorithm in terms of being able to compare equivalent reward functions, predicting policy performance, and the sensitivity to different visitation distributions. 

**Cons**

Table 2 is a little hard to understand; it might be helpful to provide some summary measure of the discrepancy between the uniform and expert policy distances, which would help in interpreting table 2 in light of section 6.3. 

I would have liked to see at least one experiment into examining the failure cases of EPIC, along the lines of the discussion in the last paragraph of section 6.3. The discussion is nice, but it would be even better if a concrete experiment was performed!

The trends in policy performance in table 2 are certainly suggestive and lend credence to the claim that reward distance predicts performance, but I feel the evaluation is still a little lacking. Some more analysis on the probability of achieving the rankings given by each method would be helpful. I also would have liked to see a variant of table 2 where each of the models were treated separately, but measuring the reward distances at various points of training. For example, for the Regression onto reward labels method, the reward distance and episode return could be calculated at selected checkpoints in the Regression training method (e.g., after every x steps in minimizing the mean-squared error). This variant of the experiment would help to give a better idea of the relationship between reward distance and return because it would be "apples to apples". A similar comment applies to the experiment for comparing the reward distances over different visitation distributions.

Being more explicit in the proof of Theorem 4.8 would be helpful. It seems to me to be a result of affine invariance rather than D_\rho being a pseudometric?

The first equality in the proof of invariance under scale on page 24 is incorrect. The expectation is inside of the power 1/p, and the operand is the absolute value of the reward difference to the power of p. I don't see how one can write the term as shown. As far as I can tell, D is also not defined. The same issue permeates the scalable in target proof, and the boundedness proof. It seems though that these proofs still follows through if one uses the proper definition of the L_p norm, so I am willing to discount this issue if it is fixed in a revision. 

In the equation after the definition of the joint distribution in Lemme A.15, it seems that the integral of the joint over y should be \alpha \mu(x) \int_{||x - y|| < r*(y)} \nu(y) dy. Since we are integrating over y here, I'm not sure the expression as given is correct. The overall claim of Lemma A.15 seems plausible to me though given the definition of the relaxed Wasserstein distance, so I think a fix should be straightforward.

**Things which didn't affect my decision**

The D_S(x) notation in proposition 4.3 should be defined; from what I understand, it refers to the probability mass of x under the empirical distribution of D_S.

Typo in first sentence of proof of Lemma 4.5: should be "zero mean and unit variance".

Type in equation 21: should be p(x, y) instead of p(x, x).

** Edit after author response **
I've raised my score after the response from the authors regarding my concerns with the theory. 

** Edit after further author experiments **
I think the paper is now even stronger given the inclusion of additional experiments into the failure cases of EPIC. I have upgraded my score accordingly. 
review_title: Promising work with some issues

Meta-review: The proposed approach for evaluating reward functions is theoretically grounded while having several properties appealing to practical RL tasks. This novel approach fills a gap in the literature. All reviewers agree that this paper has a place at ICLR.
Decision: Accept (Spotlight)