Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents MICo - a behavioural metric to learn representations for deep RL agents and shows its effectiveness - both theoretically and empirically (on the Arcade Learning Environment benchmark).
main_review: ## Strengths

1. The paper tackles an interesting, relevant and impactful problem in RL.
2. The paper is very well written. I am not much familiar with the convergence proof techniques etc but I did not have much trouble understanding the paper.
3. The paper provides both theoretical and empirical results. The empirical results show that MICo can be combined with a large number of baselines.

## Suggestions for improvement

1. Figure 4 is very hard to parse. Maybe the lines could be thinner and "...."can be used in place of "----". Alternatively, consider moving some of the results to the appendix. Also consider adding error bars to show the variance.
2. Why arent other bisimulation metric based methods reported in the experiment section? I understand they have additional assumptions baked in (line 82) but some of them should still be evaluated and reported results with.


An additional comment (Note that I am not holding this as a weakness for the paper): If the authors have resources, they should consider reporting the results over at-least 10 seeds. They should also consider releasing the metrics as a csv/json file. I expect this paper to be well-cited and several other future works to use this as a baseline. 
limitations_and_societal_impact: Limitations And Societal Impact are addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a new formulation for quantifying the similarity of states based on rewards and next states. It points out three limitations of the bisimulation metric, and introduces the MICo distance. Given a specific policy, the MICo distance is defined with the MICo update operator, which the authors prove is a contraction mapping. They demonstrate some properties of it especially as a solution to the issues of the bisimulation metric. The authors suggest a specific form of approximation to the unique fixed point of the contraction mapping, so that it can be used for shaping state representations in environments with large state spaces. Empirically, the authors performed experiments to show the usefulness of a modified version of the MICo distance's learned approximation equipped with UMAP for predicting value functions and how the scores are improved with the state representations trained jointly with the MICo loss.
main_review: **Originality**

They suggest the new operator for defining the MICo distance. While it can be thought of as a simplified version of the bisimulation operator with the eliminated need for the Wasserstein metric, they describe how it differs from previous approaches, importantly addressing some issues of the bisimulation operator. Also, they suggest the learned approximation to the MICo distance for practical use.
I think the proposed methods and derivations are meaningfully novel.

**Quality**

I find the theory up to Sec. 4 (including the MICo distance with its operator $T_M^\pi$, equivalence to the Bellman operator in the auxiliary MDP, the online approximation of the solution, upper-bounding of the value function difference, etc.) technically sound.

In Sec. 5, I think the definition of $U_{\omega}$ (L259) is somewhat abrupt. Despite the usefulness of $\Pi U^\pi$ shown throughout Sec. 5 and its connection to $U_{\omega}$, I believe addressing why the parametrized approximation of $U^\pi$ should be (or at least can reasonably be) the form at L259 will be a good addition to the paper.

Regarding the experiments in Sec. 6, while it is extensive that the various RL algorithms with or without the MICo loss are evaluated on the large number of Atari environments, including some additional comparison with other baseline representation shaping methods would be great.

**Clarity**

The paper is overall easy to follow and well-organized.

Typo "oppoosed" at 328.

**Significance**

The theoretical results in this work, despite providing the diffuse metric not a metric, seem to have a good chance to be used in future literatures, thanks to the nice properties it has (bounding on an arbitrary policy's value function gaps, the approximation schemes, and the reduced computational complexity).
limitations_and_societal_impact: I think the authors have fairly covered the limitations of their work.
Please see my main review, as well.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new behavioral distance over the state space of an MDP, which can be used to learn representations in deep RL tasks. The proposed distance has three advantages over the existing bisimulation metric: (1) it has better computational complexity; (2) it allows for online approximation; and (3) it has a close connection to the underlying policy. Empirical evidence on toy examples shows the informativeness of the representations learned by using the proposed distance, and large-scale experiments show improvements of deep RL agents when incorporating the proposed distance to learn representations.

main_review: ### Strengths
- The paper is very relevant to the representation learning / (deep) RL community.
- The proposed MICo distance is a natural extension of the existing on-policy bisimulation metric, which removes the restriction to only deterministic MDPs. In addition, the theoretical analyses and proofs in Section 4 and Section 5 are novel to the best of my knowledge.
- I appreciate the paper's technicality level. The authors start by mentioning the inherent limitations of the bisimulation metric, propose the MICo distance, and then provide theoretical results to show how it overcomes these limitations. The results of the paper are significant, and the analyses and proofs are thorough and accurate.
- The paper is very well written. I enjoyed reading the paper.

### Weaknesses
- In my opinion, the lack of connection to the optimal policy is actually a disadvantage of MICo against the bisimulation metric. Imagine when the observation contains a lot of rich but task-irrelevant information, using the bisimulation metric will result in representations that are informative of the value similarities under the *optimal* policy. In other words, the resulting representations can successfully capture task-relevant information while filtering out redundant information.
- Using MICo as an additional loss only improves the performance of M-IQN and Rainbow. The results with and without MICo in other methods are fairly the same. Moreover, in some Atari games, using MICo makes the performance drop significantly. Why is this the case?
- While the authors have experimented MICo on many Atari games and with many different RL methods, the paper is lacking comparisons with other distances. I would like to see at least the comparison between MICo and the bisimulation metric used in [1].

### Other comments and questions
- Between lines 259 and 260, how did the authors come up with this specific way of parameterizing the MICo distance? There must be other parameterizations that are positive and symmetric.
- The first equation between lines 161 and 162, there should be a sum over all actions $(a,b)$.

I am willing to raise my score if these concerns are addressed.

[1] Zhang, Amy, et al. "Learning invariant representations for reinforcement learning without reconstruction." arXiv preprint arXiv:2006.10742 (2020).
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces MICo, a new behavioural distance over the state space of an MDP. Compared to previous works on behavioural metrics such as bisimulation metrics, MICo is compatible with sample-based algorithms and therefore can be easily integrated with deep RL methods. Empirical results demonstrate that learning this distance improves performance on the Atari benchmark.
main_review: Overall, I think the paper is of high quality. The proposed method is well motivated and theoretically sound. The structure and writing are very clear. Nevertheless, I have some questions and hope the authors can help address.

* The flow of the paper is to first identify the drawbacks of the bisimulation metrics and then propose MICo to resolve them. However, it seems to me that it is more like proposing a new behavioural distance that "bypasses" the drawbacks of the bisimulation metrics. "Addressing the drawbacks" sounds like MICo can achieve the exactly same results as bisimulation metrics without suffering the drawbacks. I guess this is not what the authors want to convey. I would like to see some more discussion on comparing MICo and bisimulation metrics. For example, with the advantages of MICo being said, what does it lose (or fail to capture) compared to bisimulation metrics? In addition to Section 5.2, it would be better to add some visualizations of the MICo and bisimulation metrics (on a small grid world env), so that readers may get a more intuitive understanding.
* I do not quite agree with the description in Line 85 that explicitness means not using additional network parameters. Whether or not using additional network parameters is more on the implementation side.
* The fixed point $U^\pi$ is defined w.r.t. a policy $\pi$. However, when learning together with TD loss (as in Atari experiments), the policy keep changing. I am wondering how to deal with such non-stationarity.

Possible typos (please correct me if I am wrong):

* Line 163: "functional $T_K$ of $T_K$"
* Line 59: "$d$ symmetric", missing "is"?
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This seems like a solid paper that develops new approach to the interesting problem of inducing bias in learning through a notion of state similarity.  The notion overcomes some limitations of previous notions that were based on bisimulation concepts.  The reviewers are aligned in their ratings of the paper.
Decision: Accept (Poster)