Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new class of decision problems, the exogenous block-MDP (EX-BMDP), and an algorithm for acquiring minimal state representations for EX-BMDPs. EX-BMDPs are an extension of block MDPs that allows for additional "exogenous" state components that may have arbitrary Markovian dynamics, but cannot be influenced by actions, including through the actions' effects on "endogenous" state. The proposed algorithm, PPE, is able to recover a mapping from observed states to endogenous states (i.e. ignoring the latent distractor variables) in the setting where the endogenous state dynamics and initial state distribution are near-deterministic. It does this by comparing the set of policies that can reach each pair of states: informally, if $p(\pi \mid s_1) = p(\pi \mid s_2)$ for all policies $\pi$ (assuming a uniform $p(\pi)$), then $s_1$ and $s_2$ are treated as equivalent. In the deterministic case, policies reduce to action sequences ("paths"). Illustrative experiments on simple domains show that the proposed approach is able to quickly recover a state representation that depends mostly on the endogeneous component.
main_review: Strengths:

- EX-BMDPs seem to capture several popular simulated distractors that are currently being used in applied RL papers, such as random video backgrounds in MuJoCo tasks. I suspect the fact that the exogenous dynamics are relatively unconstrained will also make them a good model for practical tasks. The requirement for near-determinism in the endogenous dynamics is unfortunate, particularly given that it applies to the initial state distribution as well (often you want to perform well over a distribution of similar-but-not-identical tasks). However, I think this is not a major concern for exploration methods: so long as the possible initial states are reachable from some common starting state within $H$ steps, PPE will eventually explore them.
- The fact that it is possible to obtain a sample complexity bound completely independent of the complexity of $\Xi$ was surprising to me given the relatively complex form of exogenous noise in an EX-BMDP, and shows that the EX-BMDP class is at least tractable.
- The clarity of writing was appreciated, particularly when stating assumptions and comparing against past algorithms.

Weaknesses:

- I noticed that RND is missing from Section 3/Appendix A (shortcomings of existing methods), but does surprisingly well on the combination lock problem. Is it possible to give some intuition for where RND fails in general?
- The visual gridworld experiments are a little confusing. The takeaway seems to be that PPE drives accuracy to \~100% eventually on a less-toy problem. However, there are no baselines, so it is hard to determine how significant this achievement is. It would be useful to see how the baselines from Figure 2 fare in this setting, particularly in terms of sample efficiency.
summary_of_the_review: This paper proposes a general but tractable class of MDPs with exogenous distractors, and proposes a novel algorithm which provably obtains representations that exclude the spurious latent dimensions of the state. Given the technical significance of the work, I am in favour of acceptance.

-----

**Update:** the author response resolves the issue with visual gridworld experiments. I'm still in favour of acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors consider the problem of reinforcement learning using high-dimensional observations (eg, images) that may contain both exogenous and endogenous state information. Seeking to remedy the issues with learning that arise due to the exogenous state information, the authors propose a new model called an Exogenous Block MDP (EX-BMDP) and a new algorithm called Predictive Path Elimination (PPE) to learn a generalization of the inverse dynamics of the EX-BMDP. Additionally, the authors present some experimental evidence that PPE performs well in the EX-BMDP setting compared to alternatives.
main_review: STRENGTHS

(S1) The problem of efficiently learning in high-dimensional observation spaces is a good one, and the authors provided an excellent discussion of the technical components of this problem in the early parts of the paper. I thought the definition and presentation of the EX-BMDP was particularly good.

(S2) I appreciate the authors providing experimental results to show that PPE performs well in some regards.

WEAKNESSES

(W1) I'm afraid I found the discussion of PPE to be a bit difficult to decode. Even looking at Algorithm 1, I find myself with a number of important questions unanswered, chief among them being "what about $\phi^*_e$"? It strikes me as odd that nowhere in this algorithm are the inverse mappings from observation to exogenous/endogenous state represented or used. Why is this?

(W2) I'm a little concerned with the computational tractability of the algorithm. My understanding from the paper is that one seeks some sort of "covering" of the state space--in what sense is it practical to obtain and/or store this covering? If the problem setting consists of high-dimensional observations this seems especially challenging.

(W3) From my naive perspective, it seems that the ultimate goal here is to use PPE and then actually perform reinforcement learning. However, I didn't understand from the brief discussion at the end of Section 4 (or, frankly, from reading the Appendix) how exactly that would be accomplished. I feel this is important enough that it should appear in the main paper.

POST-DISCUSSION COMMENTS

During the discussion, I feel as though the authors adequately addressed each of the issues I raised above, and so I'm happy to raise my score to accept.
summary_of_the_review: While I appreciate the importance of the problem setting and think I understand the general thrust of the paper here, I overall left the paper with a lot of confusion. I'm hoping the authors can provide clarity here--both in their response and by revising the manuscript--during the discussion phase. Indeed, after some discussion and edits to the paper, I feel that the paper is much more clear and recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces a model called the Exogenous Block MDP (EX-BMDP) where the latent state contains both controllable (endogenous) and uncontrollable (exogenous) elements. The paper proposes an algorithm to find a policy cover with sample complexity that depends only on the size of the endogenous state rather than the observation or exogenous state. The algorithm works by training a classifier to predict the actions that were taken to get to a state. Since the exogenous state is not affected by actions, states for which the classifier returns similar results are likely the same endogenous state. The algorithm builds up a set of policies (sequences of actions are sufficient in the near-deterministic setting) which visit unique endogenous states by using the classifier to deduplicate redundant action sequences. Besides proving the sample efficiency of their approach, experiments are provided which show that this algorithm performs better than baseline approaches in terms of performance as well as in ability to decode the state from its representation in a simple combination lock environment as well as a grid world with distractors.
main_review: Strengths:

- The problem setting is important and seems to be relevant to many real-world problems.
- While the idea of using inverse dynamics and even multi-step inverse dynamics [1] to learn representations in these types of environments to learn controllable representations is not novel, this paper provides a theoretical basis for this choice, which I think is valuable.
- I found sections 1 through 5 to be very well written.

Weaknesses:

- In the experiment section, it seems as though you are testing the planning/policy learning abilities with PPE in both of the environments. However, as far as I can tell, there is no indication of how you perform this planning in PPE in the main text. The paper simply switches from talking about learning policy covers to showing regret for environments with only a small mention of the fact that you could plan using the data collected with PPE. The way the experiments are run and the choice to test the planning performance / how the state representations are obtained in experiments should be explained in more detail in my opinion.
- The paper discusses prior works with inverse dynamics seemingly only in the context of their applications in representation learning in two prior works on exploration. I think the application of multi-step inverse dynamics in goal-conditioned environments described in [1] is worth mentioning, since for a fixed goal this algorithm seems like it is doing something similar to PPL. Related is the lack of a "related works" section in the paper, which would be helpful for framing PPL in the context of prior works.
- There is no conclusion section, which I feel would improve the paper.

My major questions are:

1. How is the policy learning done in the experiment section? How are representations found in the decoding accuracy plot?
2. How does this paper relate to prior works on inverse dynamics?

[1] Paster, Keiran, et al. Planning from Pixels Using Inverse Dynamics Models. 2020. openreview.net, https://openreview.net/forum?id=V6BjBgku7Ro.
summary_of_the_review: In my opinion, the contribution of the paper is strong since it analyzes an important problem setting, presents an analysis of representations learned using inverse dynamics, and shows that it works in practice. The weaknesses, specifically little discussion of prior work and problems with the experiment section seem fixable, and under the condition that these points improve, I will recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a novel algorithm PPE, which they prove efficiently eliminates exogenous noise under certain assumptions (e.g. near deterministic dynamics). PPE works by growing a set of open-loop policies (action sequences) sufficient to reach all possible states for an increasing horizon. This is done by predicting the index of the policy from its final state, and eliminating states that are not sufficiently predictable. They show that both in theory and in practice that popular alternatives (noise contrastive and inverse-dynamics approaches) either fail to ignore exogenous noise or fail to distinguish between actually different states.
main_review: The paper is very well motivated. It has convinced me that being invariant to exogenous noise is important and that the EX-BMDP is useful abstraction for making this problem concrete. It is also very clearly presented. The argumentation is clear, and the flow of the paper is quite natural. Even the lengthy appendix is fairly easy to parse, with straightforward proofs and relevant details (e.g. specific claims about the unsuitability of alternative approaches).

One shortcoming is potential impact / applicability. I'm not convinced that environments with single starting states and near-deterministic dynamics is a very rich problem class. Or more specifically, I'm not convinced that restricting myself to this class would be preferable to working in the full space of MDPs with e.g. the possibility of aliasing a few states with a single-step inverse-dynamics approach. I am aware that impact is very hard to predict in advance, so I won't let this aspect unduly affect my scoring. And I'm convinced that even if PPE is never used in practice, this paper should still be accepted for its useful problem formulation and theoretical results. But a quick read would leave one with the impression that the alternatives (e.g. contrastive learning, inverse dynamics, bisimulation metrics) flaws outweigh their considerable advantages (e.g. applicability with stochastic dynamics) --  explicitly noting where alternative approaches are preferable would be appreciated.

I also noticed what I believe to be an omission in your related works: mutual information / empowerment based methods. "Variational Information Maximisation for Intrinsically Motivated Reinforcement Learning" seems particularly related in its search for predicable action sequences. And the follow-up work "Variational Intrinsic Control" appears to be a multi-step inverse dynamics analog that doesn't require open-loop policies. If you can show that these approaches are flawed in a way that PPE is not, then that would considerably raise my assessment of this work. And even if not, I believe this field (if not these specific works) should be acknowledged, as they similarly attempt to learn what in the environment is controllable.

While I agree that PPE is applicable in no-reward situations whereas bi-simulation metrics are not, your experiments all involve rewards, so I'm surprised a bi-simulation metric method was not included as a baseline.

While this isn't necessary for acceptance, it is worth noting that prior work has established much more challenging benchmarks for evaluating the representation of exogenous noise, and utilizing a pre-existing benchmark would make your empirical results considerably more impressive.

This is a small point, but it is not initially obvious why inverse dynamics fails on the combination lock problem. Does alliasing occur just when e.g. s_2a --> s_3a and s_2b-->s_3b have the same action?
summary_of_the_review: A well-argued paper that sets up an important problem and introduces a novel algorithm (PPE) to solve it. This is somewhat undercut by PPE only working in a restrictive setting. Empirical results would benefit from an additional baseline (bisimulation) and (optionally) a previously published benchmark. Some discussion of mutual information approaches should be made. But some reasonable attempt is made towards these improvements, I'd happily see this work accepted.
review_title: null

Meta-review: The paper presents a new technique that infers the endogenous states of an RL problem, as well as the corresponding model and optimal policy.  A bound is derived that shows that the amount of data needed depends only on the number of endogenous states, while being independent of the number of exogenous states and the complexity of the observation space.  This is remarkable since this is the first technique that is shown to have a complexity that depends only on the number of endogenous states.  Furthermore, the bound derived is not just a theoretical bound.  It is a practical bound in the sense that it is used in the associated algorithm, which is demonstrated effectively on two problems.  Perhaps the main weakness of the paper is that no intuition is provided in the main paper to explain why the sample complexity can be made independent of the number of exogenous states and the complexity of the observation space.  The reader has to look at the proof in the supplementary material.  Nevertheless, this is remarkable work.
Decision: Accept (Oral)