Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper approaches long horizon planning by learning a sparse graphical representation. The proposed algorithm, L3P, proceeds by learning a latent space which enforces a distance measure, where this distance is learned to mimic the number of steps between states via a goal conditioned Q-function. A clustering algorithm is then used to represent this latent space through only a small, efficient set of latent landmarks. These landmarks are then connected if nearby via the distance, the estimate of which is refined via soft value iterations over the graph. L3P is demonstrated on a number of environments to be both data efficient and high performing compared to baselines.

The paper is clear and well written. The topic of graphical representations of state spaces to plan long horizons over via local predictions holds significant promise, as does sparsifying this representation. The latent space construction and sparsification procedures are reasonable, particularly tying the distance to the policy Q-function as in SoRB. A few notes on clarity:
- The algorithm should be moved to the main body of the paper. (to reduce space, potentially remove a row of images in Fig. 4, stretch figure 1 to use the full width)
- A video would be helpful of the full process, including the soft value iterations.
- What algorithmic parameters (e.g., latent space dimensionality, network sizes, training data and number of states from which the latent space was constructed) were used?
- How are L_rec and L_latent traded off?
- The tasks, e.g., Fig 2 and 5, should be shown before the results in Fig. 3.
- More intuition on the soft value iteration would be helpful. 

The results on the shown tasks show clear benefits of L3P, particularly on the tasks where HER has most difficulty (likely the more long range tasks) L3P outperforms substantially. However, the results are somewhat lacking (1) on ablation, (2) demonstrating new environment generalization, and (3) showing significantly complex tasks.
1) The authors show ablation for number of landmarks and d_max, but not for algorithmic changes like the soft value iteration. How much does this procedure help versus the use of latent marks to sparsify the space? It would also be interesting (though not fully necessary) to see comparison to Savinov 2018a (SPTM), which uses a learned distance predictor rather than the Q-function as in SoRB and L3P.
2) It is not clear how this method would generalize to new environments, e.g., Section 5.5 in SoRB. This to me is key (particularly with generalization in the title, which I believe currently only refers to task length) and may be a challenge for L3P due to finding landmarks from limited coverage of a new scene.
3) L3P should be shown on higher dimensional and longer horizon problems, as the maze is fairly short and simple , as is the box task (as can be seen by HER’s performance). These do not push the boundaries of the algorithm. Higher dimensional problems may particularly challenge the landmark learning (e.g., if the landmarks must be learned too in a higher dimensional latent space)


__________

After author response:
I appreciate the author’s response. Previous topics:
1) The author’s add ablations on the hard vs. soft min during the graph search, the additional results are informative, but not conclusive. Given that the overall performance is similar, the authors need to demonstrate the soft-min’s benefits for each experiment and over more training seeds. 
2) For generalization, the author’s confirm that this method is unable to generalize to new environments, though clearly it has other benefits in terms of data efficiency and robustness of solutions. I believe these are still important benefits, though it would be useful to discuss how generalization may be achieved.
3) For harder experiments, the authors note that the baselines perform poorly there and thus these tasks were not considered. Though reasonable that the baselines are unable to perform in such cases, harder experiments would show the limit of the proposed algorithm. It would be useful to see for instance how well it scales with dimensionality, how quickly the success rate falls off.

New comments:
a) I believe the title change away from Generalization is an improvement, though the algorithm name "WORLD MODEL AS A GRAPH" seems to not capture the novel aspects of this work. This name I believe would be more readily applied to search on the replay buffer or semi-parametric topological memory.
b) R2's point that much of the robustness may be a factor of choosing states further from the wall is an interesting one. It would be interesting to examine exactly *why* the method is robust.
Overall, I believe the paper is interesting and proposes some novel ideas that have benefit, it requires more thorough analysis, and thus I am leaving my score unchanged.

review_title: Useful and efficient approach, but more ablations, generalizations, and environments should be examined.

final_score: rating: 5: Marginally below acceptance threshold
review_content: #### Summary:
This paper presents a method for learning a sparse set of latent subgoal states during training. Using a goal-conditioned policy and the latent states, a simple planning algorithm that performs soft value iteration between the subgoal states is proposed to facilitate within-dataset generalization. The proposed method outperforms competing approaches on multiple simulated navigation and robotics tasks.

##### Pros:
- The results seem strong.
- The method is straightforward and nice, and it seems to work more efficiently than previous methods.

##### Cons:
- Overall, the paper is incomplete. It’s very difficult to understand the whole system, how training proceeds, what the hyperparameters are, etc. There is very little detail about how this all works. The specific components of the latent landmark learning and the planning are mostly fleshed out (albeit with some missing details still) but the rest of the setup is mostly not described. How are the losses combined? Are there multiple learners or does the DDPG agent also do the latent space learning? How is training done? What are the hyperparameters used? 
- The generalization claims are a bit oversold as the generalization achieved is weak. In particular, the method requires that the test goal distribution have sufficient overlap with the train goal distribution for latent landmarks to be created near the desired test goals. 
- Are the experiment domains created here or existing work? If the former, more details are required. If the latter, citations are required.
- Given the multiple changes with respect to prior work, additional ablations and experiments are needed to better understand why this method is performing well, and what contributions are important.

#### Decision:
Overall, I find it too hard to know exactly what is happening in this work. It would be very difficult, if not impossible, to reproduce this work from this paper alone. Without sufficient details about the system, it’s hard to evaluate, which means that I default to a reject, especially in conjunction with the other weaknesses listed above.

#### Questions:
1. What is the goal space G? Is it the state space? This should be defined.
2. What exactly is \Psi? Is it learned or is it given? This should be explained better.
3. How is the autoencoder for the latent space learned within the overall system?
4. The connection between D and Q is poorly explained. From the text, it reads as if you get Q from D. However, it makes more sense if the DDPG agent estimates Q and then you use eq(3) to compute D from Q. Which is it?
5. Are both V and D really necessary? It seems like they encode the same thing, essentially. 
6. Why do you use soft value iteration? Is it a good choice? Is there a reason for this choice? Would other choices be better or worse? It seems likely that the need for the dist_max penalty is due to the use of the soft value iteration with a poorly set soft value iteration temperature. Is this true?
7. Are the domains from Duan et al 2016 or some other existing work? Or did you create them from scratch (unlikely). Why are they labeled “-hard”? What is hard about them? These need to be cited and described. You have tons of space in the appendix to use freely. 
8. In Figure 3, is the x axis training timesteps? 
9. Figure 5 caption says the agent has learned landmarks that help avoid collision with the box. Where are these? Is there a figure? Any sort of information on these? Wouldn’t any landmark away from the box accomplish this?
10. For Figure 6, why is choosing the maximum distance bound important? Why would the planning algorithm choose subgoals that are near the max distance bound given that the planner is finding the argmin subgoal? It seems likely that this hacky distance bound is unnecessary.
11. The “planning algorithm” seems trivial. Am I missing something? Given the latent landmarks and the estimates for $d_{c \rightarrow g}$, the planner just gets the next estimated subgoal and the distance to it, executes the goal-conditioned policy for that subgoal for that many steps, crosses out that subgoal, and then goes to the next subgoal. Is it non-trivial because $d_{s \rightarrow c}$ gets updated after each step (not included in the pseudocode)?
12. Is the GLS algorithm a contribution of this work or something from a previous work? Again, it's neither described sufficiently nor cited sufficiently.

#### Comments:
- The introduction uses unnecessary hyperbole and insufficient citations to make its points. It comes off as less compelling as a result.
- Section 3 is called Background but really it contains the preliminaries and definitions of this work. It should not be called Background.
- Should the variance vector of the centroids appear in equation (5)? It is mentioned once and then never discussed again. What values of it are learned? Is it important? 
- Similarly, the temperature for the soft value iteration is mentioned once and then never discussed again. What role does it play? Is it important? Would tuning this better remove the need for the dist_max penalty?
- The notation $f_D(c_i)$ is unnecessarily complicated. These values correspond to states, no? So define them as $s_{c_i}$ or something similar to make the math and text more clear. As it is, equation (6) is unnecessarily cluttered.
- I assume that the argmax in the subgoal computation at the end of section 4 should be an argmax over c? 
- There is a typo in the Figure 3 caption (PointmMaze). Further, the text in the subfigures is illegibly small.
- Break lines 11 and 13 of algorithm 2 into two lines each.


*****************
After author response:

I appreciate the updates you've made to the paper to better flesh it out, including the diagrams, pseudocode, and additional ablations. I've increased my score accordingly. Regarding generalization, I fully agree that it can be difficult to show. That said, when it's advertised in the title of the paper, I expect it to be clearly shown in the paper itself. It seems that the language has been greatly toned down in the updated version. However, without entirely re-reviewing the paper, I am unable to fully recommend acceptance.

Aside: I would have appreciated responses to my questions directly so that I don't need to dig through the rewritten paper to find the answers to my questions.
review_title: Official review

final_score: rating: 7: Good paper, accept
review_content: This paper proposes an approach for automatically learning state abstraction on a RL problem, which can then be used for temporally extended planning using a search algorithm. The main contribution is introducing the concept of latent *landmarks*, a clustering of low dimensional state embeddings. Landmarks are defined on a latent space wherein the distance between two latents code is small if their corresponding high-dimensional states can reach each other in few environment steps. The paper proposes to cluster latent states, so that each cluster contains states that are easy to reach from each other; the landmarks correspond to the centers of these clusters. An algorithm for automatically learning this clustering is introduced in the paper.  With landmarks in hand, the paper proposes a soft-value iteration method to compute shortest path distances to the problem's goal. The approach is evaluated in a variety of domains, and compares favorably with recent state-of-the-art methods.

In general, I found the paper interesting and the key ideas intuitive and sensible. The paper is reasonably well-written, but there are some important points that are unclear (see below). The experimental section compares with very recent algorithms for planning over learned value functions (SORB and MSS), and the results on five continuous control task show substantial improvement over these methods.

In terms of clarification, I have a few questions for the authors:
- With regards to the embedding used and $\Psi$:
  - The embedding operates over goals. Are these the goals of the problem? For example, in the AntMaze problem (Fig. 4), is $G = \{ \textit{red-square} \} $? If so, doesn't this mean that  $\forall s \Psi(s) = \textit{red-square}$, and thus $V(\Psi(s), \Psi(s')) = 0$ for all pairs of states?
  - More reasonably, $V$ could be defined over states, so that $V(s_1, s_2)$ indicates the number of steps between $s_1$ and $s_2$. This can be achieved under the current formulation with $G = S$ and $\Psi(s) = s$. Then $D(s_t, a, \Psi(s_t))$ represents the number of steps between $s_{t+1}$ and $s_t$. Is this the case for most experiments? No details of the $\Psi$ function used in the experiments was given, so I find this point somewhat confusing. 
  - If this is not the case, then I think it's important to explain where does this mapping function comes from, since it essentially provides some reward shaping for the problem. 

- Can you explain what is the motivation for using Algorithm 2? A common approach is to use Djikstra on the graph representation. Is there a reason why this can't be done (or is worse) in this case? 

- I don't fully understand Algorithm 1 to create the batch for Eq. (5). Can you explain this algorithm in more details? For example, the definition of $\texttt{dist}$ is ambiguous; is it pairwise distance between all sampled goals? distance between $g_1$ and all the others? something else? In general, I'm having quite a hard time figuring out what this is doing.

In light of above, I think the clarity of the paper can be improved in many places. But, overall, I'm positive towards this work and I think it is a nice contribution, particularly since I'm not aware of other work creating explicit low-dimensional landmarks to be used for search. That being said, one exception that is missing from the literature review is [1], which creates a discrete latent representation of the environment and solves it using prioritized sweeping. 

[1] Corneil, Dane, Wulfram Gerstner, and Johanni Brea. "Efficient Model-Based Deep Reinforcement Learning with Variational State Tabulation." International Conference on Machine Learning. 2018.
review_title: Introduces new method for state abstraction on a latent space with compelling experiments. Writing unclear in some places.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper generalizes the previous graph-based planning algorithm for goal-conditioned RL algorithms by learning a latent metric space and building the graph by clustering. The experiments show that their approach outperforms both the HER and previous MSS/SORB baselines.

Strong points:
1. The paper achieves good performance on the challenging AntMaze and PickAndPlace environments.
2. The clustering methods to find latent landmarks are novel in this setting.

Weak points:
1. The novelty of the paper is limited. Planning on the graph or learning a latent distance embedding for planning are all existing ideas. The combination is straightforward. The robustness of soft-min is well known. 
2. I am confused about why the authors' approach is better than MSS or SORB. It's not obvious that a distance-based clustering will perform significantly better than sampled landmarks (like farthest point sampling). I guess the reason is that clustering helps to avoid the landmarks near the wall (which often appears in the FP sampled methods). Those states are challenging as it has a higher possibility for the ant to collide with the wall. Can the author give some words about this? Moreover, the paper is not clear about the contributions of each component in the improvements. For example, no table or figure shows the benefits of the soft value iteration over the hard version. The author shall provide more ablation studies and explanations.
3. Although the paper presents the overall idea well, there is still a lot of room for improvement in writing. For example, I suggest that the author replaces the hyphen with the comma in the abstract.

~~~Based on the current presentation, the lack of ablation study, and the limited novelty, I think this paper is not good enough to be accepted. ~~~

Here are some questions:
1. Can we build graphs by sampling goal states and cluster them based on the metric space defined by the Q networks? What's the performance of this approach? Will it be worse? Why?
2. Can a sample-based approach work in non-navigation environments? Motion planning algorithms can solve the high-level part of both pick&place or ant maze problem once the geometric model is known. If so, why do we need the expensive RL algorithm?


---

After author response：

The authors have improved the presentation and added the necessary ablation studies. I appreciate the authors' effort. I am glad to raise the score to reflect the changes. I hope this work will inspire future research on hierarchical planning algorithms.
review_title: A better graph-based planning algorithm for goal-conditioned RL, but the presentation is not very clear. 

Meta-review: This paper proposes a model-based RL algorithm which, instead of simply fitting a parameterized transition model and uses rollout for planning, learns latent landmarks via distance-based clustering and conducts planning on the learned graph. Although some of these ideas themselves have appeared in literatures, the overall approach is very nice, novel and sophisticated. The experimental results appear strong and interesting. Most reviewers feel positive about the contributions of the paper, but there remain concerns that need to be addressed.

The proposed approach is highly nontrivial, and more ablation, generalization and environments need to be studied to fully justify what's going on. The authors agree to expand the paper and add the needed results, which would require substantial work thus reviewers recommend that the paper be submitted again to a future conference and receive another round of review. Showing the generalization is nontrivial, and it would be make the paper stronger if the authors put more thoughts into this issue, although it is not a must.

Minor: Another technical comment is that the approach seems heavily rely the choice of embedding distance. Learning the best embedding with meaningful embedding distance has been considered in other scenarios, see eg https://arxiv.org/abs/1906.00302. It would be interesting to try out and compare difference choices of the embedding distance.


Decision: Reject