Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a novel hierarchical reinforcement learning guided by landmarks (HIGL), which can reduce the high-level action space and improve the training and exploration efficiency of hierarchical reinforcement learning (HRL). Empirical results demonstrated that HIGL outperformed one state-of-the-art HRL approach.

main_review: The paper is well written, the motivation is quite clear, and the experiments are diversified. However, some critical issues need to be addressed before I recommend acceptance.

limitations_and_societal_impact: The following questions need to be addressed.

Q.1 Although the work is well-motivated, it might be seen as a combination of the study by Zhang et al. [1] and the study by Huang et al. [2], which weakens the novelty to a large extent. Thus, I encourage the authors to theoretically analyze the advantages of HIGL to improve the paper's contribution.

References:

[1] Zhang, Tianren, Guo, Shangqi, Tan, Tian, Hu, Xiaolin, and Chen, Feng. Generating adjacency- constrained subgoals in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.

[2] Huang, Zhiao, Liu, Fangchen, and Su, Hao. Mapping state space using landmarks for universal goal reaching. Advances in Neural Information Processing Systems, 32:1942–1952, 2019.

Q.2 Some techniques, such as priority queue $\mathcal{Q}$ and a state graph, seem to be difficult to apply to high-dimensional state spaces and stochastic environments. I suspect it is necessary to evaluate HIGL over some stochastic environments.

Q.3 How to automatically set shift magnitude $\delta_{\rm pseudo}$? As shown in Figure 4(b), the HIGL performance is very sensitive to $\delta_{\rm pseudo}$. I believe it is critical to automatically set shift magnitude $\delta_{\rm pseudo}$. 

Q.4 The results shown in Figures 3(e) and 3(f) are quite surprising. I would like to see more discussions about the reason why HIGL largely surpasses HRAC in the two tasks.

Q.5 Does HIGL suffer from performance degeneration when landmarks are insufficient? Do high-dimensional state spaces need a large number of landmarks?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a new algorithm for goal-conditioned HRL, named HIGL, that trains a high-level policy to generate subgoals towards landmarks, i.e., promising states to explore. Two criteria are considered for being a landmark, coverage of the visited state space and novelty of states. Unlike prior work that only considered generating subgoals close to the current state, this work takes both (1) reachability and (2) potential information of subgoals into account. The proposed HIGL outperforms the previous state-of-the-art method in both dense and sparse reward settings thanks to the directed landmark-driven exploration by the high-level policy. 

main_review: Goal-conditioned HRL often suffers from training inefficiency because the high-level goal space can be as large as the state space. To address this well-known issue, the paper proposes a novel framework that conducts directed and landmark-driven exploration at the high-level to improve efficiency by leveraging a set of successful techniques in the literature. The idea is very intuitive, i.e., guiding the agent to promising states by generating reachable subgoals towards those states, but the actual implementation is nontrivial. The experimental results look quite promising, and I like the comparison with HRAC on sparse rewards, showcasing the importance of directed exploration.   

Overall, the methodology is technically sound and the paper is well-written and organized. I am generally satisfied with the paper and enjoyed reading it. Nevertheless, I listed several my suggestions below (ordered by importance) that could further improve the paper if addressed or fully discussed. 

(1)	More experiments: I encourage the authors to evaluate and compare HIGL against HRAC on more environments, such as Key-Chest, Ant Gather (both included in the HRAC paper) or any new environment that requires “directed/guided exploration”. In addition, can HIGL handle stochastic env. well?     

(2)	Sparse env. results: (a) on Point Maze (sparse), why HRAC and HIGL achieved very similar performance? (HRAC slightly better) Is it because the size of the map is small compared to Ant Maze? (b) on both Ant Maze (sparse), the performance of HIGL fluctuated a lot during training and even dropped by the end of learning. Any thoughts on why this happened?    

(3)	Parameter selection: the performance of HIGL varies with different parameter settings as shown in the Ablation studies. In practice, how to select these parameters or a reasonable combination of parameters (say for a new environment)? It seems to me that $\delta_{pseudo}$ is a key parameter, can the same $\delta_{pseudo}$ be used across different env.? In addition, how well HIGL can perform if using directly the selected landmark $l_t^{sel}$ instead of the pseudo-landmark in training the high-level? I would expect to see a performance drop but it can be added to the Ablation studies.

(4)	Novelty-based sampling: (line 132-133) the current approach discards old states based on the L2 norm in the goal space. What if the states are discarded based on the shortest transition distance, e.g., $\hat{d}_{st}(s, s’) < \lambda$? Will this affect the performance? 

(5)	Computation complexity: it would be interesting to compare the computation time (HIGL vs. HRAC), so the readers understand how much computational overhead is needed. 

(6)	High-dimensional imagery inputs: any ideas on how to generalize the framework to handle image inputs or image-based goals? This could be another limitation? 

Minor comments:

(line 90-91) should eqn. (2) be $-||g_t - \phi(s_{t+1}) ||_2$? I would suggest using $||a-b||_2$ for Euclidean distance as in eqn. (3). Same applies to eqn. (4) to be consistent in notations. 

limitations_and_societal_impact: The authors have discussed adequately limitation and social impact in Section 6.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Paper introduces HIGL, a hierarchical RL framework based on landmarks. The main idea is to limit the higher level action space (which is often taken to be the full state space), by restricting it to specific landmarks. These landmarks are defined bases on two criteria: coverage of the visited state space, and novelty of the visited states. These landmarks are then integrated in an HRL framework. Experiments on three U-maze like environments show that their method performs well. 
main_review: Strong:
* I like Figure 1: really strong illustration of the overall method, very clear as well. 
* The approach to sample landmarks is interesting, especially the combination of both methods (coverage and novelty). Although the authors mention that the coverage method will also mostly sample the frontier (which the novelty method should already do, the coverage method should also cover the interior). Nevertheless, this is a good idea, and Figure 6 gives a really nice illustration that it works. 
* There are good results. I like Fig 4b, since it gives a nice illustration of what the interpolation towards the landmark does, and why shooting too far is suboptimal as well. Nevertheless, it does seem beneficial to shoot a bit beyond the landmark (\delta > 1).

Weak/comments:
* The preliminaries on adjancency networks and random network distillation (L92-105) go too fast, and need some additional explanation for reader who have not read those papers. For example, I think you need some explanation on the contrastive loss, and in Eq. 5, where did \bar{\theta} go (is it in f(s)?).
* For the coverage based approach to hierarchy, I think you missed an important early reference [1].
* I was confused for a while between the \phi and \psi functions. I would change one of these symbols to a more different one for clarity. 
* L144: why do you estimate distance based on the value function? You have just fitted the adjancency network right, why do you not use this here?
* Alg 1: Is the subgoal transition function h() learned, or given? It seems to be given, but how is it specified?
* Alg 1: on what loss is the lower level trained? Just a standard goal-conditioned value-based loss?
* Sec 4.3: I found this quite hard to directly understand. I would first explain the main intuition, that you will construct a loss on the high-level policy to direct the direction in which it will sample a subgoal. Also, why do you not use the raw landmark as a subgoal, or the raw interpolation? 
* The evaluation environments are rather small.
* Fig 4a: I do not see a difference between 40 and 60 really? Only 20 does not work?
* L241-253: And the other way around, what does coverage add over novelty? 
* There are some typo’s in your document, double words, etc.
* There is no report on the run times of generating the landmark trees and running the planning algorithm. In the discussion you do mention that heavy planning budgets are allowed, but still, I would prefer if you reported on them. 

Conclusion:
In general I think this is a decent submission. The topic is relevant: HRL, in particular the way to compress the higher level goal space. The authors extend previous work with a new way to estimate landmarks based on a combination of coverage and novelty. This seems to work well from their results, which is interesting. The integration of these landmarks in the HRL training loop is probably quite computationally heavy (the authors do not report on run times, which I consider one of the bigger issues with this paper), but does show good results (although the environments are rather simple, U-mazes only). Nevertheless, I do think this paper has value to the community, especially in the way the authors generate the landmarks. 
limitations_and_societal_impact: Accurately addressed.
review_title: null

Meta-review: Reviewers found the paper to contain novel ideas with solid justifications. The author response was particularly useful in addressing some of the initially raised issues. We therefore recommend acceptance.

The authors are encouraged to take the reviews into account to improve presentation and results, especially to include some of the new ones that were provided in the rebuttal. I’d also strongly encourage the authors to strengthen the related work section. The paper unfortunately ignores over two decades of significant hierarchical RL work, some of which appear related enough to deserve a discussion. Examples are the following subgoal discovery work that rely on graph structures, and some of them have a notion of novelty (although different from this work):
https://dl.acm.org/doi/abs/10.1007/3-540-36755-1_25
https://dl.acm.org/doi/abs/10.1145/1015330.1015355
https://dl.acm.org/doi/abs/10.1145/1015330.1015353

A potential challenge mentioned by the reviewers is to scale to high-dimensional space, and the authors suggested working in the goal space. The following paper works in the goal space, and relies on successful trajectories to find goals in high-dimensional state spaces: https://aclanthology.org/D18-1253 (https://aclanthology.org/D18-1253/).
Decision: Accept (Poster)