Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Summary:
=============================
This paper aims to solve the long-term goal-conditioned planning problem by tackling strategies to explore state-goal pairs. The proposed methods improve the exploration performance by formulating successor features as landmark graphs and in exploration, use three key steps: (1) select the frontier graph node; (2) use a random policy to explore; (3) extend the landmark graph by a successor feature similarity metric.

Overall, this paper is well written, with methodology clearly explained and evaluation done in detail. So I recommend a clear acceptance.
main_review: Strength:
=========================
The proposed method is convincible for me, both in intuitions and experiments. Regarding intuition, successor features represent the local traversity of states, which describes the system dynamics using value predictions. So using SF to represent landmarks and to explore the state-goal pairs is reasonable. Regarding experiments, various baselines, including graph-based planning baselines  (SGM, SPTM) and UVFS based baseline (MSS) are implemented and compared, showing the proposed method’s supreme performance. Results are not surprising, but I appreciate the author’s effort for due diligence.

Minor concerns:
=========================
However, here are some minor concerns, with the hope to help improve the paper:

(1.) While I agree using SF similarity metric is a good one to measure how novelty a state is since SF only considers the environment’s system dynamics, I am still wondering why? Considering SF represents the expected state traversity, the dot product (Page 5, equation 4) between two SF vectors is projecting on SF on the other. Then what does such projection mean?

(2.) While I also agree using a random policy as a fixed policy in your SF training is a good choice since as explained, it is uniformly random so that only dynamic of environment will dictate which states the agent will visit, but this will also make the SF pre-training hard. For example, it may require a huge data corpus in order to accurately approximate the SF since the use of uniformly random policy to explore and to represent SF. Any explanations for that?

(3.) While I agree as well using the frontier of the graph node is a good choice to set as the exploration anchor point, but compared to graph sparsity [SGM] and graph Laplacian methods, this selection ignores the interconnection nature inside a graph, will that give a clue to better improve the frontier selection?

(4.) Goal-conditioned tasks, as shown in the paper demoed in navigation tasks, assume the goal can be defined as a target state. This assumption enables exploring state-goal pairs by adding new states as the new goals. However, many RL tasks can not represent the goal as a reachable state. For example, the goal is to survive in VizDoom, which has no relationship with any state reaching. Or the goal is to set some preference to some states while reaching the goal. As you can see, the SF landmark structure introduced here is not a general framework. There are other general methods [Bagaria et al. 2021], however, that can not handle high-dimensional state-action space. Expecting to see more works done here.

Reference:
Bagaria, Akhil, Jason K. Senthil, and George Konidaris. "Skill Discovery for Exploration and Planning using Deep Skill Graphs." International Conference on Machine Learning. PMLR, 2021.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents Successor Feature Landmarks (SFL), a new graph-based planning framework based on successor features for long-horizon goal-conditioned RL (GCRL). The key idea is to use successor features to define a new metric, Successor Feature Similarity (SFS), to estimate the distance between two states or state-action pairs in high-dimensional environments, such as 3D visual environments. By leveraging SFS, a landmark-based graph is built to represent the explored state space. Both guided/directed exploration and random exploration are deployed to help the agent traverse between landmarks and explore unseen states of the environment respectively. Combining all the components, SFL is more efficient and scalable than previous graph-based methods for long-horizon GCRL.   
main_review: Measuring the distance between states using similarity between the corresponding successor features is a new and interesting idea. This design not only considers the actual transition dynamics in the environment but also makes it feasible to estimate distances in high-dimensional state spaces. The resulting framework SFL with landmark-based non-parametric graph and goal-conditioned exploration is well designed and presented in the paper. Figures 1, 2 and Algorithms 1, 2 are extremely helpful to illustrate the details of the framework in my opinion. Empirically, the authors have included a set of extensive experiments, and the performance of SFL looks quite promising for long-horizon GCRL. 

Overall, the paper is well-written and organized, and the proposed method is technically sound. I am generally satisfied with the submission, but I listed some items below which I believe if revised could further improve the overall clarity of the paper. 

(1)	Is the successor feature $\psi(s)$ or $\psi(s, a)$ normalized? I don’t think this is mentioned in the paper, but I believe it is important to clarify this. Accordingly, is the distance measure SFS bounded (eqn. (5) or (6))? 

(2)	Line 201-202 says “If we let $w$ be $\psi^{\bar{\pi}}(g)$, … being equal to the SFS between $s$ and $g$”. However, if strictly following eqn.(3) and letting $w$ be $\psi^{\bar{\pi}}(g)$, eqn.(8) seems not correct to me. Conditioned on policy $\pi$, $Q^{\pi}(s, a, g) = \psi^{\pi} (s, a)^T \psi^{\bar{\pi}}(g)$, which is then not equal to the SFS between $s$ and $g$ that follows a random policy. I could understand the idea here, but probably revising the wording a bit can improve the clarity. In addition, how does the local goal-conditioned policy $\pi_l$ be derived? I assume that $\pi_l$ is extracted from $ Q^{\pi}(s, a, g)$ rather than separately learned. It could be helpful to explicitly state the derivation of $\pi_l$ and how actions are sampled from $\pi_l$ in Section 4.3. 

(3)	In Algorithm 2, line 2, do you actually mean for $s \in \tau$ do? Line 11, do you also need to check if $l_{prev} \neq \emptyset$ and $l_{prev} \neq l_{curr}$? In addition, any suggestions on how to select a reasonable combination of parameters $\delta_{add}, \delta_{local}$ and $\delta_{edge}$ in practice when applying SFL to a new environment (not included in the paper)? 

(4)	Is there any limit on the total number of landmarks $|L|$ tracked in the graph? I believe it could be interesting to have some mechanisms to remove or update/replace landmarks in the set $L$. SFS is being constantly updated during learning. Even if $l$ and $l’$ are very close to each other, $l’$ can be easier to reach than $l$ when used as a goal conditioning. Therefore, it could be interesting to replace $l$ with $l’$ in the graph. 

(5)	Experiments on MultiRoom in Figure 5 are of high variance. It could be helpful to add more elaboration on this part to explain the variance.  

(6)	Exploration in unseen state space is conducted via random action sampling, which is in general quite inefficient. I understand that this is needed in the framework to learn SF, but it could be another limitation of the current algorithm.  
 

limitations_and_societal_impact: The authors discussed the limitation in Section 6 and social impact (both positive and negative) in Appendix H.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper deals with the goal conditioned reinforcement learning problem (GCRL). It proposes an incremental approach to learning good landmark states through successor features so as to enhance exploration and in turn improve the success rate of reaching arbitrary goal states. The authors discuss learning in navigational tasks, both tabular and pixel based, where the goal state changes randomly and exploration is hard. The idea is to learn a landmark graph, each landmark being a state itself which is sufficiently distanced from other landmark states. The notion of distance is provided by the successor representation (features in the pixel case). Planning policies to reach between different landmark states alleviates the exploration issue, and thus helps in improving GCRL performance. 
main_review: Originality: The motivation of the work is solid in my opinon. However, the proposed solution lacks originality. This is my main complaint with the paper. I roughly boil them down to two main points:

- Unnecessary emphasis on 'novel' nomenclature: The paper introduces two definitions, of Successor Feature Similarity (SFS) and Successor Feature Landmark (SFL) , both claiming novelty. In my opinon, this does more harm than good, in that it hampers the readibility/understanding of the paper. Both these ideas are not new in any sense, and I claim that any reader with prior knowledge of this area would recongnize this instantly. Successor Feature Similarity (SFS) aims to be a distance metric based on the successor representation. This idea dates back to the Proto-value functions work, or at the very least, is as old as the learning eigen options from the successor representation paper by Machado et. al. Similarly, the idea of landmark states for better exploration probably dates back to the multi-value functions paper by Moore et. al. 

- (Lack of) discussion to previous work: The options literature has looked at the problem of navigation extensively for decades, and yet the authors do not provide a discussion on how these ideas are similar/different from those in the options literature. Successor options by Ramesh et. al. seems to be the closest to this paper, where a clustering scheme (over the successor representation) is used to identify landmark states. I believe the graph based solution, based on looking at distances between states using the SFS metric is doing exactly the same. The authors do not discuss how exactly their approach is beneficial over the clustering scheme. For example, one benefit could be that modelling the states as a graph explicitly allow for better identification of fringe nodes, thus aiding in better directions to explore. If this is the case, an simple experiment to show this would really help in highlighting the main contributions of the paper. 
 
Quality: The overall quality of the work is quite high. The experiments are well executed and observations are nicely reported.

Clarity: The paper reads quite clearly overall. The flow of content is pretty nice as well.

Significance: Overall, I think the main contribution of this work is not the main ideas but the results on pixel based navigation, which I believe are really impressive and shows that these and similar ideas are easily scalable. I do not gain any conceptual insight from this, nor do I think the paper is aiming to provide any.

Questions: My primary question is regarding the similarity to the idea of doing clustering over the built SF to get the landmark states and then learning policies to reach these (also called options). It would be really helpful if the authors can discuss the exact differences and similarities. 
limitations_and_societal_impact: Suggestions: My main suggestion would revolve around fixing the issues I point to in the 'originality' section above. I think that and more experiments in a non-navigational domain can improve this paper massively.

I do not think there any explicit negative societal impacts of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new metric, called the successor feature similarity, that measures the similarity between two states as the dot-product between the respective successor features. The authors then use this metric to guide goal-directed exploration when learning a goal-conditioned policy by choosing a goal with the lowest count. Novel goals are stored by keeping a buffer of visited goals, where new goals are only added if they are beyond a certain distance of any prior goal. Rewards are given by the SFS between a state and a goal (where a state-only SF is computed as the action-averaged SF). The authors compare this overall method to existing graph-based GCRL methods and find that the resulting method outperforms prior work, particularly in challenging first-person maze-navigation VizDoom tasks that require moving around multiple walls.
main_review: Overall, this paper is well written and the experiments convincingly show that the overall method outperforms prior work. The authors clearly explain how their work builds off of prior work, but also clearly presents a novel algorithm.

My main criticism is that the paper proposes a number of contributions, and the experiments would do a better job of demonstrating the impact of each individual contribution, rather than the sum of the components. For example, although the authors compare to [5], it seems that the other components of the algorithm are different. It would be useful to compare to an ablation where the SFS is replaced with the supervised learning model in [5]. The author could also compare to other metrics proposed in prior work such as in [1] which should also be discussed or [2,3,4].

Another example would be to disentangle how important the specific exploration strategy is, involving going to a frontier state and then taking random actions. Running an ablation that uses the same strategy as in SGM or SPTM would help clarify this.

Lastly, one question that is largely unaddressed is how the hyperparameters are chosen. In particular, the thresholds for adding landmarks or recording a landmark transition seem particularly important but difficult to choose.


[1] Ghosh, Dibya, Abhishek Gupta, and Sergey Levine. "Learning Actionable Representations with Goal Conditioned Policies." International Conference on Learning Representations. 2018.
[2] Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer:
350 Bridging planning and reinforcement learning. In Advances in Neural Information Processing Systems, volume 32, 2019.
[3] Vitchyr Pong, Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal difference models: Model-free deep RL for model-based control. ICLR, abs/1802.09081, 2018. 
[4] Srinivas Venkattaramanujam, Eric Crawford, Thang Doan, and Doina Precup. Self-supervised learning of distance functions for goal-conditioned reinforcement learning. arXiv preprint arXiv:1907.02998, 2019
[5] SPTM
limitations_and_societal_impact: No. The authors did not discuss the limitation of this work, even though the checklist says “Yes.” The closest discussion is an acknowledgement that the method "depends on a good feature embedding to be learned." Please discuss the limitations of the work.
review_title: null

Meta-review: All reviewers agree that this is a strong, clearly described empirical work. Although it uses mostly pre-existing concepts, it combines them in an effective way, and its well-executed experiments demonstrate impressive results on pixel-based benchmarks. The ablation studies conducted as part of the discussion with reviewers will further strengthen this paper.
Decision: Accept (Poster)