Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates learning better representations for deep reinforcement learning algorithms using bisimulation metric (BSM), such that the representations are more efficient and robust from distraction (e.g. noise). The proposed method improves the Deep Bisimulation for Control (DBC) algorithm for tasks with uninformative rewards and the authors show their method is competitive in those environments.


main_review: This paper focuses on learning more robust and efficient representations for deep reinforcement learning algorithms. The analysis and resulting method build on previous work of the Deep Bisimulation for Control (DBC) algorithm but improves for environments with sparse rewards in particular. The authors analyzed theoretically embedding collapse and explosion could happen with sparse rewards and proposed remedies to fix them. The authors showed that the resulting algorithm was not only better with sparse rewards but also more stable when the observations are noisy. The topic is definitely closely related and significant to the community. Although it builds on DBC, the analysis and proposed algorithm are novel to the best of my knowledge. The paper is also well-written and easy to follow in general. Some questions: 1.can you talk more about embedding collapsing and exploration? 2.the experiments are conducted on sparse cartpole and continuous mountain cars, which are relatively low-dimension, maybe evaluate and compare the methods in MuJuCo tasks with sparse rewards? 3. fig.3, why the proposed method is a bit worse or almost the same as sac? could you explain more? especially for cartpole-swingup-sparse, why with IR it is still a bit worse than SAC?
limitations_and_societal_impact: See the main review.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper analyzes properties of bisimulation metrics, identifies potential issues in learning with sparse rewards, and proposes methods to fix the issues.
main_review: Learning good latent representation is important for RL problems with high dimensional observations, and recent approaches based on bisimulation metrics have shown promising results. This paper analyzes the existence of unique on-policy bisimulation metrics and their connection to value function bounds. Based on the properties, the paper proposes a normalization method to fix some embedding issues of prior methods in sparse reward environments, and it further proposes improvements using intrinsic rewards and inverse dynamics.

The ideas to analyze on-policy bisumlation metrics is very reasonable, and the proposed methods seem to be both theoretical and practical appealing, but the paper (particular Section 3) is very difficult to read, and many key concepts are either missing or hard to follow. Below are some issues with the paper in the current status.

As the paper claimed, one of the key contributions is the convergence condition of bisimulation metric in learning. However, there is never a formal statement of what is the "sufficient condition for the existence of a unique bisimulation metric". This condition seems to be mentioned after Theorem 3, but the discussion is very confusing. From the statement of Theorem 3, "the sufficient conditions" seem to refer to cT<1, p=1, and the support of the approximate dynamics is closed. But later in (11) the main condition seems to refer to the boundedness of the metric. The boundedness of the unique metric is mentioned in Theorem 3, but as a property instead of a sufficient condition. After checking the proof of Theorem 3, the boundedness is indeed not used in proving the existence of the metric. So why does the boundedness of metric becomes the sufficient condition? Does the boundedness have any relationship to the closedness of the support? Even more confusing, in all discussions after Section 3 the condition is referred to "embedding normalization" without any definition nor explanation. Does normalization mean the requirements (11)? How does the normalization actually work in learning with parameterized embedding functions?

There are some missing definitions and typos which highly affect readability. There is no definition of the diameter before Lemma 1, no definition for the different forms of metrics used in Theorem 4 besides in the appendix. In the paragraph before Theorem 3, one metric d with hat but another one without hat. What is the metric d appearing in (11)? There is no indication on what the sup in (14) over on which doesn't seem to be over policies.

The idea of investigating the danger of on-policy bisimulation with sparse rewards in 3.2.3 is very interesting, but the discussion is very unclear and may need further explanation. The section claims that the challenges of degeneration is only an issue with on-policy bisimulation, but there is no comparison with policy-independent bisimulation. If policy-independent bisimulation doesn't have the issue, then why prior methods don't work? The paper also claims that this degeneration might be the reason for poor performance of DBC and the proposed methods fix the degeneration, but the simulation results actually show exploding behaviors instead of collapsing. How does the analysis explains exploding behaviors of DBC? The proposed intrinsic rewards and inverse dynamics methods seem reasonable, but there does not seem to have any connection to the analysis in 3.2.3 and why these methods can resolve the degeneration issue.

As said above, I like the ideas of the paper but would not recommend to accept it given the issues mentioned above. I will consider raising the score if the paper can be revised to address the above points.



limitations_and_societal_impact: Parts of the limitations are mentioned in the paper, but most of the analysis are only on the existence of the bisimulation metric, and there is a big gap for practical algorithms to actually converge to the unique metric even if it exists.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the author proposed a robust bisimulation metric that could combat the collapse and explosion issues. The authors analyzed the cause of these issues theoretically and further proposed  a set of remedies including a norm constraint on the representation space, and intrinsic rewards and latent space regularization. The authors did experiments in the gym environment to verify the proposed methods.
main_review: Pros:
1. The authors modify the previous metrics and provide a generalized metric. The analysis of the new metric compared with the old one is solid.
2. In the experiments, the newly proposed method shows better robustness against sparsity compared with DBC.
3. The authors further show the policy-dependence may cause caution collapse in on-policy bisimulation.

Cons:
1. The experiments have simple/similar dynamics. It would be of beneficial for readers to know whether the approach would still gain obvious edges when the dynamics of the task is complex, such as a sparse version of the spider or walker in gym. Now the main challenge seems only coming from the dimension of the noise.
limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of learning good representations for reinforcement learning problems. It approaches this from the perspective of bisimulation metrics, extending earlier work on on-policy bisimulation for control (DBC). The paper identifies issues with DBC that also appear in other types of metric learning, and includes a theoretical analysis of why this happens. To remedy the issues the paper proposes normalizing the representations and including an extension to DBC by including an inverse dynamics model and intrinsic rewards.
main_review: ### Strengths:

* This paper is well written and answers many of the questions that arise while reading it immediately. 
* The analysis of certain issues in DBC is very nice to have. The theoretical section was (mostly) easy to follow and was informative. 
* The theory section has a clear added value in analysing the issues with DBC and proposing improvements. For example, compact spaces are assumed for continuous MDPs and this assumption is violated in DBC. This motivates the authors to propose normalizing the representations to a closed ball. Additionally, there is a degenerate solution when rewards are sparse, which motivates the authors to propose intrinsic rewards to prevent this from occurring. 
* An ablation study is included (though it is incomplete)
* The paper does a good job of reviewing the related work, only missing a few related references (included below). 

### Weaknesses:
* The choice of inverse dynamics as a regularizer is not well-motivated. This choice is not grounded in the same way that the rest of the paper is. For example, why choose an inverse dynamics model and not a different self-supervised loss? Why not a different combination of approaches? The motivation given for inverse dynamics could also be applied to reconstructions or contrastive coding. Additionally, there are no experimental results showing that an inverse dynamics model is best; as such this choice is the weakest part of the paper.
* As there is no experimental comparison to other additions to DBC (e.g. different self-supervised learning approaches), it is unclear why  inverse dynamics is the preferred method to solving the issues with DBC.
* The paper focuses heavily on one method; DBC, and as such is somewhat limited in scope.
* The paper, while well-written, is not fully self-contained - certain terms are used without being defined. A few examples: 
  * What is a ‘compact subset of $\mathcal{S}$’? 
  * What is a diameter of a state space? 
  * What is sup? The supremum? 
  * What is supp? Also the supremum? 
  * What is $\mathcal{H}$ in line 259?
  * What is a low dispersion reward?
* According to the paper, DBC suffers from common metric learning problems, but there are no references included to other metric learning papers that exhibit similar issues.
* If the intrinsic reward is based on the forward model error, it should not be useful under state collapse, as the error would be 0. 
* The non stationarity introduced by IR might be an issue in more complex environments.
* Line 294: Claim: “Hence, we expect less disruption to the BSM encoding than other auxiliary tasks (e.g. reconstruction)”. Reconstruction is not the only possible auxiliary task. What happens when using a better auxiliary loss, such as action-dependent contrastive coding?
* Ablation study is incomplete -- DBC-ID and DBC-normed-ID are not included.
* “(Left) Our method significantly improves upon DBC [36] and is on par with SAC” this looks like it isn’t true, as SAC achieves a higher performance in the end.
* The method isn’t evaluated on the same benchmarks as DBC, with comparable levels of distraction (e.g. natural video). As a result, it is unclear what the performance improvement would be in those settings.


### Questions:
* “two states that only differ in rewards far in the future should still not be bisimilar” - Standard bisimilarity is defined over immediate, not future rewards. Could you elaborate?
* The assumption that the reward is normalized between 0 and 1 -- is this taken into account in the experiments?
* The sentences 193-195 are unclear, could you clarify?
* Eq. 11: x \in R^d is this d overloaded?
* Eq. 11: what is B_c? The ball with radius c? It looks like c is not defined.
* Eq. 12: Does M(B_c) mean the space of probability distributions over the ball with radius c?
* Lemma 3 assumes a stationary distribution over states, but this distribution changes as the policy changes. How does this influence the theory/results?
* Figure 1: what is magnitude? The magnitude of the embedding?

### Minor comments:
* Below are some suggested references on state representation learning that could be relevant to include in related work.
* Plots are hard to read in black and white
* While the motivation for requiring more informative rewards is clear (as mentioned in strengths), it is not motivated why this takes the form of intrinsic rewards, as compared to e.g. reward propagation. 
* SAC does not fail in sparse-cartpole with N_m=1, it just takes longer to converge


### Overall:

The score is mostly based on the following:
* The choice of inverse dynamics (vs action-dependent contrastive coding or another type of auxiliary loss) should be properly motivated, either theoretically or experimentally.
* Missing references should be included
* Evaluation should be performed on the same benchmarks as DBC, e.g. with natural video distraction.

I would raise the score if these are addressed.

#### Missing references:
* Biza et al, "Online Abstraction with MDP Homomorphisms for Deep Learning"
* Grimm et al, "The value equivalence principle for model-based reinforcement learning"
* Le Lan et al, "Metrics and continuity in reinforcement learning"
* Ravindran & Barto, "Approximate Homomorphisms: A framework for non-exact minimization in Markov Decision Processes"
* Taylor et al, "Bounding Performance Loss in Approximate MDP Homomorphisms"
* Van der Pol et al, "Plannable Approximations to MDP homomorphisms: equivariance under actions"

#### Suggested references
* Agarwal et al, "Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning"
* Corneil et al,  “Efficient model-based deep reinforcement learning with variational state tabulation”
* Dadashi et al, Offline Reinforcement Learning with Pseudometric Learning
* Francois-Lavet et al, “Combined reinforcement learning via abstract representations”
* Watter et al,  “Embed to control: A locally linear latent dynamics model for control from raw images”

#### Update
Thank you for the rebuttal, and for the update on the experiments. I think adding the new experiments to the paper will make the paper more convincing. 
When reviewing, I only had a few issues with this paper: the lack of motivation for the choice of inverse dynamics (as opposed to another auxiliary loss), the missing evaluations on benchmarks with natural video distractions (for a fair comparison to DBC), the somewhat limited scope (due to the focus on DBC), some missing references, and the paper not being fully self-contained.
In the author response, the authors motivate their choice of inverse dynamics, clarify that their results can be useful for bisimulation metric learning in general, promise to add the references and amend the paper where it is unclear, and in a second reply give an update on benchmarks with natural video distractions, with positive results. 

The authors thus address my original concerns. However, reviewer pEeB raised concerns about the theoretical analysis that are important to address. I have therefore decided keep my original score.

limitations_and_societal_impact: #### Limitations: 
Yes, the authors discuss limitations of their work.
#### Societal: 
Yes, the authors discuss potential societal impact. A minor suggestion would be to add a comment on how improving RL (as this paper aims to do!) could impact society, e.g. in terms of labor markets or autonomous weapons.
review_title: null

Meta-review: Three knowledgable reviewers recommended acceptance of the paper (2x accept, 1x weak accept) and one reviewer recommended (weak) rejection of the paper. The authors addressed most of the reviewers' concerns in their rebuttal but some concerns were not resolved. In the discussion about the paper we came to the conclusion that the paper can provide several interesting insights but needs to address several of the reviewer concerns the camera ready version. I am therefore recommending acceptance of the paper and at the same time strongly advise the authors to carefully adjust the paper to address the remaining reviewers' concerns (in particular reviewer pEeB's concerns regarding clarity and theoretical statements).
Decision: Accept (Poster)