Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this work, the authors present a method to perform planning from pixels in environments that exhibit a hard combinatorial search space. They consider procedurally generated environments that can be modeled by a goal-conditioned MDP.  They present a method that first learns to represent the environment as a latent graph, in which nodes represent latent states and the edges represent actions, and then use a graph search algorithm to plan over this graph. They learn a state encoder model, parameterized by a ResNet, to project a pair of environment's states and actions to a d-dimensional hypersphere. They also learn a transition model over the latent space as well as an inverse model that is trained to prevent the loss of the forward model to collapse to a trivial solution. The authors also introduce an extra loss that enforces an epsilon margin between encodings of non-bisimilar states to ensure that the latent exhibits a discrete structure to enable planning. Then, they use the breadth-first search algorithm to find in the latent graph, for a given episode, the sequence of actions that lead from the initial state to the goal. They also use a Model Predictive Control approach to mitigate the prediction error propagation during planning. Finally, the authors introduce three visual environments that exhibit a combinatorial hard search space. They show that their method outperforms strong baselines on these environments and obtain good generalization.
main_review: First I would like to thank the authors for their work. I believe that learning to plan from pixels to solve combinatorial problems is very important and that this paper steps forward in that direction. My comment on the soundness of the claims, significance and novelty of the contribution, and relevance to the NeurIPS community are below:

The paper is very clear, well written and overall easy to follow. Notably,  I really enjoyed sections 1, 2 and 3 that are well motivated and didactic.

The method is sound and the design choices are clearly explained and motivated.

The experimental section is well-structured. The environments are clearly described.

The choice of the baselines makes sense and the supplementary material justifies this choice clearly.

The method seems to work really well and these environments compared to the baselines.

Limitations of this work:

In the related work, I would recommend the authors to additionally cite and compare their method to LEAP (Nasiriany et al.) that is really close to this method. LEAP would also be a good candidate for additional baselines.

While the way the model is trained and how the planning is performed are clearly described, I think this paper lacks a section to discuss how both are intertwined. Notably, if my understanding is correct, the model is first trained on randomly sampled transitions, then frozen and then the authors perform planning on this frozen model for all their experiments. This setting is interesting as it validates the representation capabilities of the model however it is limited. For instance, in some environments, some states and thus some transitions can't be visited by a random policy. Therefore, I think that it is important to also consider settings where the model is improved iteratively on transitions found during the search.

While these environments are complex along some axes, they remain simple along others. Notably, the dynamics seems simple enough to be learned from a few randomly sampled transitions. Therefore, I would recommend the authors test their method on other environments to strengthen their claims. For instance, the authors might consider the environments used in GLAMOR and assess if their method still outperforms GLAMOR on these.

The paper mentions several times the issue of generalization. While the authors addressed generalization on levels, it would be very interesting to address as well generalization on goals as the method allows for it. In this form, it is surprising when starting to read the experimental sections, to learn that the goals are not sampled but fixed. It would be great if the authors run additional experiments to assess generalization over goals. In this case, to ensure a FAIR comparison, they should also add the goal as an input to PPO's policy and DREAMER's model and use HER (Andrychowicz et al.) in addition.

To conclude, I think that this work is very promising and I really liked the paper. In this form, the paper is marginally above the acceptance threshold. However, I would be happy to increase my score if the authors address the limitations I mentioned.


limitations_and_societal_impact: This paper doesn't add limitations or potential negative societal impact to existing reinforcement learning and classical planning methods.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a model-based planning method for pixel-based control in difficult-to-plan environments in which the full environment is observed through a high-dimensional image. The method proceeds by proposing a particular learning objective for learning image representations that can be used for localization ("reidentification") and planning. After this encoder is learned, the representations are used inside a graph-based planner that observes the current image and target goal image and uses receding-horizon control ("Full Planner") to control the agent. Experiments on an existing set of difficult environments, as well as two newly-proposed environments that satisfy the desired properties (difficulty and observability) compare the method to model-based baselines, a model-free baseline, and a simple learning-free planning baseline. These experiments show the method outperforming the baselines in all key settings, and exhibiting better performance relative to a model-free approach in low-sample regimes.
main_review: The setting is an interesting and highly-relevant: model-based control from pixels in a particular class of difficult environments. The proposed method is straightforward (fairly intuitive) and performs well. The proposed evaluation does a reasonable job of highlighting the strengths of the method and deficiencies of existing methods in the setting. I have a few concerns about the problem setup, importance of training objective components, and experiments that I think are important (hence, my initial rating of 6 instead of 7), but I believe should be straightforward to address.

**Problem setup:**
- L60 I think the set of MDPs need the further assumptions that each $|s_i| = |s_j| \forall i\neq j$, and similarly for actions, otherwise the model will need to be able to handle states and actions of different dimensionalities. Furthermore, I think that the problem assumption might match that of Block MDPs [A] -- which assume that each observation contains enough information to uniquely identify the state and implies the existing of a perfect decoder. If true, this would make the problem setup in this paper clearer, in which each $z_t=f(o_t)$ is meant to approximate a true underlying $s_t$. Particularly, it's peculiar to think of the high-dimensional images as Markovian states; the block-MDP assumption fixes this peculiarity.
- The notion of "combinatorial hardness" is important to the setting in which the algorithm is meant to function well, yet it is never precisely defined, which also means that the environments employed are not conclusively shown to possess combinatorial hardness. I think this needs to be formalized in order for the paper to make its claims precise enough.

**Evaluation concerns:**
- Does the margin loss actually contribute to learning a better latent space? Discretization for the graph search could still be performed using a model trained without the margin loss. It would be good to have evidence to show that the margin loss results in improved planning performance. This evaluation could be added to Table 1 in the appendix, and referenced in the main text when the margin loss is discussed. If the following ends up being true, that could look something like "we found the margin loss to result in representations better-suited to our planning method, see Appendix Table 1." Similar ablations are missing for the $\mathcal L_{\text{FW}}$ and $\mathcal L_{\text{CE}}$ losses.
- Success rate fails to disentangle the efficiency with which approaches achieve the goals. I think the paper would have a more robust evaluation if it included the success weighted by path length metric -- see e.g. Eq. 1 from [B]. For instance, it could be true that PPGS finds very efficient paths relative to the baselines, and the baselines merely do a reasonable job of efficiently exploring the space, rather than exhibiting particularly efficient directed behavior.
- L318 "GS on Images manages to rival other baselines is a testament to the harshness of the environments" I'm not sure there's enough evidence to conclude this. I'd say that GS on Images is performing reasonably well (>40% success in all environments). Given that GS on Images is a "simple" baseline that doesn't employ learning, this suggests to me that the environments are not particularly harsh (or they are well-suited to GS on Images), and that the other baselines are merely underperforming / are not well-suited to the task.
- If computationally feasible, it would be good to extend the X axes of Fig 7 IceSlider and ProcgenMaze (and DigitJump), in order to determine if/when the performance of PPGS and PPO overlap. The trends suggest that PPO may reach PPGS performance at ~$10^4$ training levels. Presumably they would eventually overlap. This evaluation would strengthen our understanding of the performance of the approaches as a function of the available training levels.
- L325 "Note that PPGS uses only 400k samples from a random policy whereas PPO uses 50M on-policy samples" This point is too easy to miss. It's not otherwise clear that the amount of training data available to each approach is different. Isn't the 400k samples only true at one of the x-values in Fig7? The number of training samples available to each approach should be made clear in Fig 7. For example, having stacked x-axes for each method in Fig 7 could work, if the number of training examples available to PPGS and PPO are linear functions of the number of levels (current x-axis).

**Minor comments:**
- L60 There's an extra comma in the set; also, (pedantry to follow) include the tuple parens: $\{(S, A, T, G, R, \gamma)_i\}_{i=1}^n$.
- L280 "the largest disadvantage is arguably given to our own method." More explanation is needed. Is this due to the reward-free learning?
- typo: Eq 6 has an extra parenthesis after $z_h^l$.
- L202 typo "wepsite"
- Alg 1 is missing the pretrained encoder as input.

[A] Provably efficient RL with Rich Observations via Latent State Decoding; ICML 2019 http://proceedings.mlr.press/v97/du19b/du19b.pdf

[B] On Evaluation of Embodied Navigation Agents; https://arxiv.org/pdf/1807.06757.pdf


limitations_and_societal_impact: The paper didn't really discuss broader limitations or broadly characterize failure cases -- the Checklist 1(b) answer points us to sections that narrowly reference performance issues. One of the main limitations is the observability assumption, furthermore, determinism in the dynamics seems quite limiting. These should be discussed somewhere. An inclusion of potential broader impacts was added in Checklist response 1(c), but it should be included in the appendix (?)
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces a planning method for solving combinatorial environments from pixels called PPGS. PPGS learns a latent space using a ResNet encoder which is trained such that a forward model and inverse model can be learned using the representation. Finally, it is constrained to encourage margins in the latent space. During goal-conditioned planning, visual inputs are mapped into the latent space, discretized, and a BFS-like search algorithm is performed. PPGS achieves strong empirical results on the Procgen maze environment and two 2D Atari-like environments which the authors newly introduce in the paper. 
main_review: Originality: The choices of components in the objective used to learn the latent space are well-motivated and seem sensible. While the idea of planning from pixels using a learned latent space is not novel, to my knowledge the training objective used in this paper contains new elements of combining forward and inverse model training, as well as a discretization step to allow planning on a graph. 

Quality: The method is not compared to other model-based planning methods which are goal-conditioned and do not require a reward signal, for example, SPTM (Savinov 2018). These may be expected to perform better than methods which require rewards due to generalization, better than GLAMOR by performing explicit planning, and better than “GS on images” due to being goal-directed.

In motivating the development of new environments, it’s stated “its dynamics are uniform and actions only cause local changes in the observations. Moreover, ProcgenMaze is a forgiving environments in which errors can always be recovered from. We use these insights to choose the additional environments”. While this seems true, the choice of making new evaluation environments more difficult in these axes (nonlocal changes from actions and irrecoverable errors) could be better justified for example in terms of downstream application.

The relatively weak performance of Dreamerv2 and GLAMOR is explained in the text by lack of generalization across a variety of levels. Can this be verified experimentally, e.g. by looking at the performance of these algorithms on fixed levels?

How sensitive is the method to the choice of $\epsilon$ in Equation 4, and how important is adding the margin loss to performance? Was this value tuned prior to experiments? The ablations do not include an analysis of this aspect.

Clarity: It seems like PPGS can only work if planning towards states which have already been seen in the training data or which have neighboring states which have been seen in the training data. This is confusing to me because it seems that the environments are quite difficult, yet this means the random policy must achieve a reasonable success rate on them to collect data in that range. What is the success rate of the uniformly random policy on each of these three environments? Can state coverage be guaranteed for other environments?

Nitpicks: 
In figure 2, there is a L_hinge which is not described in the text -- did you mean L_margin?.

Typos: L202: “wepsite” -> “website”, L340: “state-of-the-art method” -> “methods”, L210 “envrionments” -> “environment”

Consider citing: 
“Semi-parametric Topological Memory for Navigation”, Savinov et. al 2018

The code for the environments as well as the algorithm are provided and the authors have made efforts to provide details for reproducibility. 

Significance: The empirical results are quite impressive -- the environments in the experiments are quite difficult to solve even for humans, and PPGS achieves an impressive success rate on these tasks. Furthermore, the method is demonstrated only using offline trajectories and does not use any further online rollouts. The experimental environments are a nice contribution and the demo/presentation is quite helpful for understanding their complexity.

Recommendation:

I believe that this work is a nice contribution towards planning from visual observations. While I have concerns about necessary conditions for environments it can perform well on, the generalization performance and state representation learning component of the work seems straightforward and effective.
limitations_and_societal_impact: I was unable to find much discussion in the paper specifically about the limitations of PPGS -- it would be great if the authors could add some discussion. However, I believe that one major limitation as mentioned earlier is that the success rate of a random policy must reach a minimum threshold to be able to build a dataset to learn world models which can be used for planning without any additional data collection.
review_title: null

Meta-review: Learning dynamics models over pixels for model-based RL remains a largely open problem. There is consensus among the reviewers that the empirical results in this paper are impressive, and the approach constitutes a valuable contribution. The reviewers make several suggestions for improvements, e.g., analyzing generalization to goals and clarifying necessary conditions for environments it can perform well on, that can be addressed in a revision.
Decision: Accept (Poster)