Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning
Authors: Junsu Kim
Younggyo Seo
Jinwoo Shin
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Hierarchical Reinforcement Learning

Abstract: Goal-conditioned hierarchical reinforcement learning (HRL) has shown promising results for solving complex and long-horizon RL tasks. However, the action space of high-level policy in the goal-conditioned HRL is often large, so it results in poor exploration, leading to inefficiency in training. In this paper, we present HIerarchical reinforcement learning Guided by Landmarks (HIGL), a novel framework for training a high-level policy with a reduced action space guided by landmarks, i.e., promising states to explore. The key component of HIGL is twofold: (a) sampling landmarks that are informative for exploration and (b) encouraging the high level policy to generate a subgoal towards a selected landmark. For (a), we consider two criteria: coverage of the entire visited state space (i.e., dispersion of states) and novelty of states (i.e., prediction error of a state). For (b), we select a landmark as the very first landmark in the shortest path in a graph whose nodes are landmarks. Our experiments demonstrate that our framework outperforms prior-arts across a variety of control tasks, thanks to efficient exploration guided by landmarks.

Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning
Junsu Kim
Younggyo Seo Jinwoo Shin
Kim Jaechul Graduate School of AI Schooo of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) jjunsu. jjunsu.kim, younggyo. seo, Himwoos)(kaise ac.kr
Abstract
Goal-conditineed hierarchical reinforcement learning (HRL) has shown promising results for solving complex and long-horizon RL tasks. However, the action space of high-level policy in the goal-conditioned HRI. is often large, so it results in poor exploration, leading inefficiency training. this paper, we present Hlerarchi- cal reinforcement learning Guided by Landmarks (HIGL), a novel framework for training high-level policy with reduced action space guided by landmarks, i.c., promising states to explore. The key component of HIGL is twofold: (a) sampling landmarks that are informative for exploration and (b) encouraging the high-level policy to generate a subgoal towards selected landmark. For (a), we consider two criteria: coverage the entire visited state space (i.e., dispersion of states) and novelty of states (i.e., prediction error of state). For (b), we select landmark the very first landmark the shortest path graph whose nodes are landmarks. Our experiments demonstrate that our framework outperforms prior-arts across a variety of control tasks, thanks to efficient exploration guided by landmarks.
Introduction
Deep reinforcement learning (RL) has demonstrated wide success in a variety of sequential decision- making problems, i.e., board games [38, 42], video games [1, 26, 38], and robotic control tasks [15, 30, 53]. However, solving complex and Long-horizon tasks has still remained major challenge RL, where hierarchical reinforcement learning (HRL) provides a promising direction by enabling control at multiple time scales via a hierarchical structure. Among HRL frameworss,, goal-conditioned HRL has long been recognized as an effective paradigm [5. 20, 29, 37], showing significant success in variety of long and complex tasks, e.g., navigation with locomotion [21, 54]. The framework comprises a high-level policy and a low-level policy; the former breaks the original task into series of subgoals, and the latter aims reach those subgoals.
The effectiveness of goal-conditioned HRL depends on the acquisition of effective and semantically meaningful subgoals. To this end, several strategies have been proposed, e.g., learning the subgoal representation space [6, 11, 21, 29, 31. 32, 35, 44, 50] or utilizing domain-specifi knowledge for pre-defining subgoal space [28, 54]. However, the learned or pre-defined subgoal space is often too large. which results in poor high-level exploration, leading to inefficient training. To address this issue, Zhang et al. [54] recently proposed a reduction of the high-level action space into the k-step adjacency region around the current state. This approach, however, is limited in that considers all the states within the k-step adjacency region equally the candidate actions for the high-level policy, without considering the novelty of states, which crucial for exploration.
'Code available https: attpp://githhi ctt. junsu-unnuuaaee
httpjjjnnsukkm////H11 kim.k/mmm999./...... /H
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Collect trajectories
Sample landmarks
Select landmark (via shortsst algoritmm
Train high-level policy
Build landrarks
Genarate paeedo- landmark
from trajectorins
State
Landmark by "Novelty"
Graph
Pasudo-
Trajectory
Landmark by 'Coverage"
Shortest path
high-lovel
space
action space
Figure I: Illustration of Hlerarchical reinforcement learning Guided by Landmarks (HIGL). (1) We collect trajectories using high-level and a low-level policy. (2) Sample landmarks from visited states based on "coverage" and "novelty" criteria, respectively, and merge them. (3) Select a single landmark among the sampled landmarks in graph constructed by landmarks, a goal, and current state. (i.c., select the very first landmark in the shortest path to the goal). (4) Train a high-level policy to generate subgoal toward the selected landmark.
Contribution. In this paper, we present Hlerarchical reinforcement learning Guided by Landmarks (HIGL), a novel framework training high-level policy that generates subgoal toward landmarks, ie., promising states to explore. HIGL consists of the following key ingredients (see Figure I):
Landmark sampling: To effectively sample landmarks that represent promising states to explore, it is important sample landmarks that cover wide area of state space and contain novel states. To this end, we propose two sampling schemes: (a) coverage-based sampling scheme that samples located far away from each other possible and (b) novelty-based sampling scheme that stores novel states encountered during training and utilizes them as landmarks. We find that our method successfully samples diverse and novel landmarks.
Landmark-guided subgoal generation: Among the sampled landmarks, we select the most urgent landmark by our landmark selection scheme with the shortest path planning algorithm. Then we propose to shift the action space of high-level policy toward selected landmark. Because HIGL constructs a high-level action space that both (a) reachable from the current state and (b) shifted towards promising landmark state, we find that the proposed method can effectively guide the subgoal generation of a high-level policy.
We demonstrate the effectiveness of HIGL various long-horizon continuous control tasks based on MuJoCo simulator [48], which is widely used the HRL literature [9, 16, 28, 29]. In our experiments, HIGL significantly outperforms the prior state-of-the-arr method, i.e., HRAC [54], especially in complex environments with sparse reward signals. For example, HIGL achieves the success rate of 65.1% in Ant Maze (sparse) environment, where HRAC only achieves 17.6%.
Related work
Goal-conditioned HRL. By introducing hierarchy consisting of high-level policy and low- level policy, goal-conditiones HRL has been successful in a wide range of tasks. Notably, Nachum al. [28] proposed an off-policy correction method for goal-conditioned HRL, and Levy et [19] successfully trained multiple levels of policies in parallel with hindsight transitions. However, the acquisition of effective and semantically meaningful subgoals still remains a challenge. Several works have been proposed to address this problem, including learning-basee approaches [6, 11, 21, 29, 31, 32, 35, 44, 50] and domain knowledge- based approaches [28, 54]. The work closest to ours is HRAC [54] that reduces the high-level action space to the k-adjacent region of the current state. Our work differs in that we explicitly consider the novelty of each state within the region instead of treating all states in an equal manner.

---

Subgoal discovery. Identifying useful subgoals to guide training (low-level) policy has long been recognized as an effective way to solve complex RL problems [23-25, 43]. Recent works provide a subgoal by (1) constructing an environmental graph and (2) planning in the graph [8, 14, 17, 22, 36, 41, For (I), one important point is to build graph that represents the entire map enough with limited number of nodes. To this end, several approaches such as farthest point sampling [14] and sparsification [17] were proposed. For (2), traditional planning algorithms, c.g., the Bellman-Ford algorithm, are usually used for offering the most emergent node to reach the final goal. These works have shown promising results in complex RL tasks but have a scalability issue due to increasing planning time with a larger map. Meanwhile, our framework differs from this line of works since ours "train" high-level policy rather than hard-coded high-level planning to generate a subgoal.
3 Preliminaries
We formulate a control task with a finite-horizon, goal-conditioned Markov decision process (MDP) [45] defined tuple (S, A, H), where S is the state space, 9 is the goal space, A is the action space, p (s'[s, a) is the transition dynamics, T (s, a) is the reward function, E [0, 1) is the discount factor, and H is the horizon.
Goal-conditioned HRL. We consider framework that consists of two hicrarchies: high-level policy T[gls; Bnigh) and a low-level policy π (als,, gi (lov), where cach policy parameterized by neural networks whose parameters are thigh and 01om. respectively. At each timestep t. The high- level policy generates a high-level action, i.c., subgoal 9, E G, by either sampling from its policy Ir [[g]< Baigh) when t = 0 (mod k)), otherwise using pre-defined goal transition process St = h St-1 st). i.e., h(g:-1, St-1. = 9t-1 + S St for relative subgoal scheme [28, 54], h(g--1, 1: st) -t-1 for absolute subgoal scheme." The low-level policy observes the state 8 and goal gr. and performs low-level atomic action 0e ~ (al 8t; St; 010z). Then, the reward function for the high-level policy is given as the sum of m external rewards from the environment as follows:
high T1.m)
r(s,, a;),
(I)
1=0
where Tt.m [(8e, It. oz),... (#t+mm 9t+tm-1, mt+m-1)) } denotes a trajectory segment of size m. The goal of high-level policy is to maximize the expected sum of b by providing the low-level policy with an intrinsic reward proportional to the distance in the goal space G. Specifically, in relative subgoal scheme [28, 54], the reward function for a low-level policy is defined as:
1 (81s St; Qt; 81+1) = -199t, (p(++1 s1)112,
where y : S + G is a goal mapping function that maps a state to a goal. Instead, one replaces with an absolute subgoal scheme, the reward function is substituted as follows:
1. (st, It, at. St+1) - 119,, (p$++1)
Random network distillation. One line of exploration algorithms introduce novelty of a state, that calculated by prediction errors [3, 13, 34, 39], visit-counts [2, 33, 47], or state entropy estimate [12, 18, 27, 40]. One well-known method is Random Network Distillation (RND) [3], which utilizes the prediction error of a neural network as a novelty score. Specifically, 1et f be a neural network with fixed parameters 9 and ff be a neural network parameterized by A. RND updates by minimizing the expected mean squared prediction error of f, El fs; 11 Then the novelty score of state is defined as:
n(s) [I] (s; 112
(4)
The novelty score n((s) is likely to be higher for novel states dissimilar to the ones the predictor network has been trained on.
In relative subgoal scheme, the high-level policy gives a subgoal representing how far the low-leve policy should move from its current state. Whereas, in an absolute subgoal scheme, the high-level policy provides an absolute position where the low-level policy should reach.
3

---

Adjacency network. Let (st s') be the shortest transition distance from state to state s' i.e., dat(8 (s. s') the expected number of steps an optimal agent should take reach the state s' from 'To estimate dst. Zhang et al. [54] introduce an adjacency network to parameterized by ø. that discriminates whether two states are k-step adjacent or not. The network learns a mapping from a goal space to an adjacency space by minimizing the following contrastive-like loss:
Laay (6) = ess (Ixx ( l Ek, 0)
(5)
+(1 (1-1) 1) max(Ex: + - (9:) th (g1) O)],
where 5 > O is a margin between embeddings, Ej is a scaling factor, and 1 E {0, 1} represents the label indicating k-step adjacency derived from the k-step adjacency matrix .M that stores the adjacency information of the explored states. The equation (5) penalizes adjacent state embeddings = 1) with large Euclidean distances, while non-adjacent state embeddings (1 0) with small Euclidean distances. Then the shortest transition distance can be estimated as follows:
k
(s, =
(11)) (92) (o = dec
(6)
Ek
4 Hierarchical reinforcement learning guided by landmarks (HIGL)
In this section, we propose HIGL: Hlerarchical reinforcement learning Guided by Landmarks, a novel framework for training high-level policy with reduced action space guided by landmarks. We describe HIGL with three parts sequentially: (1) landmark sampling in Section 4.1, (2) landmark selection in Section 4.2, and (3) training in Section 4.3. We provide illustration and an overall description of our framework in Figure and Algorithm ??, respectively.
4.1 Landmark sampling
To effectively guide the subgoal generation of high-level policy, it is important to construct set of landmarks that covers a wide area of state space and contains novel states promising to explore. To this end, we consider two criteria for landmark selection: (1) the coverage of the entire visited state space and (2) the novelty of a state.
Coverage-basse based sampling. We propose sample landmarks that cover a wide range of visited states from a replay buffer B. To this end, we utilize Farthest Point Sampling (FPS) [49], which samples a pool of states from B and chooses states which pool. Specifically, we sample set of coverage-based landmarks T, (1. Mar by applying FPS
far as possible from each other in the
J==
where the distance between two states s and s' is measured in the goal space as ||ş[(s (2s following Huang et al. [14]. We note that FPS implicitly samples states at the frontier of visited state space, which implies that coverage-bar based landmarks implicitly mean promising states to explore as well (see Figure for supporting experimental results).
Novelty-basee sampling, To explicitly sample novel landmarks, we propose to store the novel states encountered during the environment interaction and utilize them as landmarks, To this end, we introduce a priority queue Q of fixed size K where the priority of each element (state) is defined as the novelty state n(s) in (4); the queue stores a state in with priority of ns).. One important thing here is that the novelty of state decreases as the exploration proceeds, so the priority of constantly updated. For this reason, we propose similarity
stored states in Q should update scheme that discards previously-stored samples that are similar to the newly encountered state. Specifically, when we encounter state 8, we measure the similarity of s between all stored states s' E Q and discard similar states, i.e., {s' E Q [|(p(s) (p(s))ll2 A). where is similarity threshold. Then we store a state s in Q. and sample a set of hovelty-based landmarks Man from Q
_ov (m MM
4.2 Landmark selection
Since all the landmarks in L. oov U 1o are not equally valuable reach a goal from a current state 8, i.e., some landmarks may be irrelevant or even impeditive to arrive at the goal, we propose a landmark selection scheme to select the most urgent landmark among the sampled landmarks. To

---

this end, we introduce a two-stage scheme: (a) we first build graph of landmarks, and (b) we run the shortest path planning to goal the graph.
Building a graph. For landmark selection, we build a graph whose nodes consist of a current state St, (final) goal 9. and landmarks L. First, we connect all the nodes and assign the weight of each edge with a distance between two nodes, where distance is estimated by a low-level (goal- conditioned) value function (s,, g). i.e.. (51 (51) 51)) for state $1, 52 in a relative subgoal scheme, following prior works [8, 14, 32]. As the distance estimation via value function is locally accurate but unreliable for far states, we disconnect two nodes when the weight of the corresponding edge is larger than preset threshold "aist following Huang et al. [14].
Planning. After building graph, we run the shortest path planning algorithm to select the most urgent state to visit, 15e2, from a current state & to a goal g. Since the general value iteration for RL problems is exactly the shortest path algorithm on the graph, we utilize the value iteration as the shortest path planning. following the prior work of Huang et al. [14]. By selecting the very first landmark in the shortest path to the goal, HIGL can focus on the most urgent landmark, ignoring landmarks that may be irrelevant to reach the goal from the current state.
4.3 Training high-level policy guided by landmark
Using the selected landmark, HIGL trains high-level policy to generate subgoals that satisfy both desired properties: (1) reachable from the current state and (2) toward promising states to explore. Since the raw selected landmark may be placed far from the current state, using the raw landmark would be suboptimal; is likely not to satisfy the property (1). To acquire both properties, we introduce aveudo-landmart which is located near the current state but also directed toward the selected landmark (promising state to explore) in the goal space. To be specific, we make pseudo- landmark be placed between the selected landmark and the current state in the goal space follows:
gedl Deur
g peoudo
9t + Spsoudo
11
g0
where ōpsendo is the shift magnitude, and سو (( ), D6 cur (s(s) are the corresponding points for the selected landmark ygel and the current state s; in the "goal" space, respectively.
Then, we encourage high-level policy to generate subgoal adjacent to the pseudo-landmark. To discriminate the adjacency, we employ the adjacency network proposed in Zhang et al. [54]. Instead of a strict adjacency constraint, which may cause instability in training, we "encourage" hige-level policy to generate a subgoal near pseudo-landmark via landmark loss, motivated by the prior work [54]. The landmark loss is calculated using the adjacency network as follows:
Liandnaru (Onsgn) = max() Wo (o ( - vh )l2 - Ex, 0),
where 9: x [g]|s Ohigh) is generated subgoal by the high-level policy, & is adjacency degree (how far we admit as adjacency), and E is a corresponding scaling factor. Then, we train high-level policy by incorporating Liandnrrx into the goal-condiiioned HRL framework:
Cnign(Onagh)) -Eg
E (i (1 (Tr,m) 11 Liandnark),
where 17 is the balancing coefficient. In practice, we plug Liandmark an extra loss term into the original policy loss term of a specific high-level RL algorithm, c.g., TD error for learning methods. We remark that the low-level policy is trained usual without any modification.
5 Experiments
In this section, we designed our experiments to answer the following questions:
How does HIGL compare to the state-of-the-art HRL method [54] across various long-horizon continuous control tasks (see Figure 3)?
How do the coverage and novelty for landmark sampling improve the performance, respectively (see Figure 4a, 4b)?
5

---

(a) Point Maze
(b) Ant Maze (U-shape)
(c) Ant Maze (W-shape)
(d) Reacher
(e) Pusher
Figure 2: Environments used in our experiments. maze tasks, the red arrow indicates the goal in each task, and the black line represents the desired trajectory from the current state to the goal. In (a) Point Maze and (b) Ant Maze (U-shape), an agent is born at the bottom-left corner at the start of the episode. In (c) Ant Maze (W-sappe),
agent is born at random point in the maze except for the goal point. In (d) Reacher and (e) Pusher, a robotic arm aims to make its end-effector and (puck-shaped) gray object reach the target position, which is marked red ball, respectively.
How does the pseudo-landman affect the performance instead of using the selected landmarks (see Figure 4c)?
How do the hyperparameters: (1) the number of landmarks M, (2) the shift magnitude Spsendo and (3) the adjacency degree k affect the performance (see Figure 5a, 5b, 5c)?
5.1 Experimental setup
Environments. We conduct our experiments
of challenging long-hooe nogghorizoon continuous control tasks based on MuJoCo simulator [48]. Specifically, we consider the following environments evaluate our framework (see Figure 2 for the visualization of environments).
Point Maze [7]: A simulated ball starts at the bottom left corner in a "5"-shaped maze and aims to reach the top left corner.
Ant Maze (U-shape) [7]: A simulated ant starts the bottom left corner in a """"shaped maze and aims to reach the top left corner.
Ant Maze (W-shape) [54]: A simulated ant starts from a random position in the "h"-shaped maze and aims to reach the target position located at the middle left corner.
Reacher [4]: robotic arm aims to make its end-effector reach the target position.
Pusher [4]: robotic arm aims make a (puck-shaped) object plane reach a goal position by pushing the object.
Stochastic Ant Maze (U-shape) [54]: Gaussian noise with standard deviation a (i.e., 0.05) is added to the (z. y) position of the ant robot at every step.
Moreover, we evaluate HIGL with two different reward shapings dense and sparse. In the dense reward shaping. the reward is the negative L2 distance from the current state to the target position (final goal) in the goal space. In the sparse setting, the reward is O if the distance to the target position is lower than pre-set threshold, otherwise -1. In maze environments, we 2-dimensional goal space that represents the (x., y) position of the agent following prior works [28, 54]. In Reacher, we use 3-dimensional goal space that represents the (x, y, z) position of the end-effector. In Pusher, we use 6-dimensional space, which additionally includes the 3D position of the (puck-shaped) object. We employ a relative subgoal scheme for Maze tasks and an absolute one for Reacher and Pusher. We provide more environmental details in the supplementary material.
pre-defined
Implementation. We use TD3 algorithm [10] the underlying algorithm for training both high- level policy and low-level policy for all considered methods. For the number of coverage-based landmarks Moov and the number novelty-base landmarks Moov. we use Moov 20 and Ma 20 in all the environments except Ant Maze (W-shape). We use Moos = 40 and Mao 40 in the more complex Ant Maze (W-shape) environment. to the noisy peeudo-landdart in the early phase of training, we use &psoudo O for the initial 60K timesteps, i.e., k-step adjacent region to the "current state" instead of iipseudo-landmartt that this stabilizes the training by avoiding inaccurate planning at the early phase; under-trained value function causes inaccurate distance estimation at landmark selection. All of the experiments were processed using single GPU (NVIDIA TITAN Xp) and 8 CPU cores (Intel Xeon E5-2630 v4). We evaluate five test episodes without an exploration factor for every 5000th time step. We provide further implementation details used for experiments in the supplementary material.
order to avoid the instability in training due
We find

---

1.0
HIGL (Ouns)
3.0
HIGI (Durs)
0.8
HIGL (Ours)
0.8
0.0
HRAC
Succes 1226
Succes roce
0.6
0.
02
02
0.4
0.0
0.0
0.0
0x:00
1x30
2x30"
3x10
Axtot
5xIo
Dxia
2x301
4x.00 Bxto
Exto!
10cc0"
0x301
2x:30
fxto
Sxie
Timesteps
Timessleps
Timesteps
(a) Point Maze (dense)
(b) Ant Maze (U-shape, donse)
(c) Ant Maze (W-shape, dense)
1.0
(Ours)
(Ours)
HIGL rOurs)
HRAC
HRAC
Succes rate
0.8
0.6
0.6
Succas
Succos
0.4
0.2
0.2
0x000
1x20
2x30f 3x10" 4xtof
5xI0f
0x10"
2x1e1
4x:00 6xin'
Ex1of
0x107
2x100
4x100 SxIe!
Rx20" 1OKIo"
Timesteps
Timesteos
Timesteps
(d) Point Maze (sparse)
(e) Ant Maze (U-shape, sparse)
(1) Ant Maze (W-shape, sparse)
HIGL (Ours)
0.8
HIGL (Uurs)
0.6
HIGL (Ours)
HRAC
HRAC
HRAC
Sucoes rate
0.6
0.4
Succos
0.6
0.4
0.4
0.2
0.
2x10 3x10f
Swisf
ANLoP
Swlof
0x307
4vi0"
LDK10"
Timesteps
Timesteps
Timesteps
(g) Reacher (sparse)
(h) Pusher (sparse)
ii) Stoachastic Ant Maze (sparse)
Figure 3: The average success rate in various continuous control tasks of HIGL and HRAC [54]. We observe that HIGL consistently outperforms HRAC, especially in more complex and long- morizon environments. The solid lines and shaded regions represent mean and standard deviation, respectively, across four runs. All curves are smoothed equally for visual clarity.
5.2 Comparative evaluation
We compare HIGL to the prior state-of-the-ar method HRAC, which encourages high-level policy to generate subgoal within the k-step adjacent region of the current state. As shown in Figure HIGL is very effective in hard-exploration tasks (i.e., Ant Maze (U-shape and W-shape)) thanks to its efficient exploration guided by landmarks. To be specifie, instead of treating all the adjacent states equally (as HRAC did), HIGL considers both reachability and the novelty of a state. HIGL recognizes promising directions explore via planning and trains high-level policy to generate subgoal toward the direction. We understand that such differences in our mechanism made a large gain over ARAC. In particular, HIGL achieves success rate of 65.1 %, whereas HRAC performs about 17.6% at timesteps 10 x 10 in Ant Maze (U-shape. sparse) task. We emphasize that HIGL is more sample-efficient when the task is much difficult: HIGL shows a larger margin in performance in (1) Ant Maze (U-shape) than Point Maze, and (2) sparse reward setting than dense reward setting.
Moreover, We find that HIGL also outperforms HRAC in stochastic environments, as shown in Figure 3i. We remark that HIGL is applicable to stochastic environments without any modification since our algorithmic components (including the novelty priority queue and aedmaar-graphh are built visited states, regardless of transition dynamics.
5.3 Ablation studies
We conduct ablation studies on HIGL. to investigate the effect of (1) coverage-based and novelty-based sampling Figure 4a, 4b, (2) pseudo-landmarks (compared to raw selected landmarks) in Figure 4c, and (3) hyperparameters (i.c., number of landmarks M, shift magnitude ōpeeudos and adjacency
7

---

2.6
88
Mic
MeRr 20
Pseudo landmarks
Mis 10
Mey 10
Raw landmarks
Succes rate
Mee
Succes rate
Mezr
0.
02
0.0
0.0
0.0
2x.00
3x101
5xto
2xi0
3x:10
1xto
5x30
0x301
2x30
fxto
1DKID"
Timestegs
Timesseeps
Timesteps
(a) Coverage- based sampling
(b) Novelty-based sampling
(c) Pscudo-landmarrs
Figure 4: Ablation studies on our algorithmic components: (a) coverage- sampling, (b) novelty- based sampling, and (c) number of (a) coverage-base and (b) novelty-based landmarks in Ant Maze (U-shape, dense). For (c), we compare HIGL with pseudo-landmarks and raw landmarks in Ant Maze (W-shape, dense).
We measure the performance of HIGI by varying the
degree k) Figure 5. For all the ablation studies except for the pseudo-landmarks, we use Ant Maze we employ Ant Maze (W-shape dense),
(U-shape, dense). For experiments the which has a larger maze size (i.e., W-shape has a size of 20 x 20, while U-shape has 12 x 12) because the effectiveness of the ppcudo-landmarks is more remarkable in such large map.
Coverage-basse based sampling. We evaluate HIGL with varying numbers of samples from coverage- based sampling in Figure 4a. We evaluate HIGL with MaVv 20 and varying Meor E {0. 10, 20). We observe that using coverage-base based landmarks affects the performance of HIGL, indeed. This because severage-based landmarks play an important role as waypoints toward novel states or even as promising states themselves; coverage-baser sampling implicitly samples states at the frontier of visited state space (See Figure 6 for supporting qualitative analysis).
Novelty- sampling. Analogously, we evaluate HIGL with varying numbers of samples from avelty-basee sampling in Figure 4b. Specifically, we report the performance of HIGL with Meov- = 20 and varying Maov E {0, 10, 20). We observe that utilizing our proposed novelty-based sampling improves the performance as well. For example, we emphasize that HIGL with Maoo = 10 novelty- based landmarks significantly improves over Maov = O, which corresponds HIGL with only coverage- based sampling. This demonstrates the importance of considering the novelty of each state crucial for efficient exploration.
lseudo-landmarks. To recogmize the effectiveness of pseudo-landmarks, compared to raw selected landmarks, we conduct ablative experiments in Ant Maze (W-shape, dense). As shown in Figure 4c, we observe that using lanudo-landmarrs achieves better performance than using raw selected landmarks. This is because pseudo-landmarks have both desired properties: (1) "reachable" from the current state and (2) toward promising states to explore, while the "raw" selected landmarks may only have the latter property. When a selected landmark is placed too far from the current state, using the selected one would be suboptimal because it would make high-level policy generate unreachable subgoals from the current state; providing such subgoal makes faint reward signal for low-level policy. Instead, pseudo- landda-s so it accelerates training even in such a large environment like Ant Maze (W-shape), where selected landmarks are more likely to be located far from the current state.
effectively guide high-level policy with both desired properties,
Hyperparameters. We conduct experiments to verify the effectiveness of hyperparameters, (1) number of landmarks M- Meoy + Maor. (2) shift magnitude ōgsouáo and (3) adjacency degree k.
Number of landmarks M. To demonstrate the effectiveness of the number of landmarks, we conduct experiments using the different number of landmarks M = Mcev + Maov in Figure 5a. We sample the same number of landmarks for each criterion, i.e., Moov = Maov- The results show that the performance of HIGL is improved with the increased number of landmarks since it is more capable of containing more information about an environment. In addition, one can understand that increasing the number makes planning in the landmark- -graph more reliable; remark that distance estimation via (low-level) value function is more accurate in the local area.
Shift magnitude &psoudo- In Figure 5b, we conduct experiments with varying values of âpsando- which determines the location of pseudo-landmate The results demonstrate the location of the
8

---

0.8
M 60
Spectt
36
Speest
0.6
M 30
Succes rate
Speesdo #
Succes
Speeto
20
0.4
0.2
0.0
0.0
0.0
2x.00
3x101
1x301
5xt0
2xtn
3x.00
1xto
Sx30
2x301
3x10'
Ax30
5xI0
Timesteps
Timesslepo
Timestteps
(a) Number of landmarks M
(b) Shift magnitude Spenddo
(c) Adjacency degree k
Figure 5: Performance of HIGL on Ant Maze (U-shape, dense) environment with varying (a) the number of landmarks M, (b) shift magnitude Apsouda and (c) adjacency degree k.
pseudo landmark can affect the performance. If pseudo is small, the high-level policy tends to be trained to generate subgoal near the current state rather than the selected landmark; this may cause the high-level policy to not fully enjoy the benefits efficient exploration guided by the selected landmark. On the other hand, if paaado is too large, the high-level policy is promoted to generate a subgoal that is unreachable from the current state, which leads to performance in Figure 5b.
degradation, i.e., dpaudd
Figure Sc, we investigate the effectiveness of the adjacency degree k. which determines the size of the region where high-level policy is encouraged to generate subgoal. One can observe that adjusting adjacency degree does not influence critically to achieve superior performance over HRAC. However, understand that setting the degree too large is not appropriate because it is allowed for high-level policy to generate subgoal that is quite far from the pseudo landmark; the generated subgoal may be located unreachable region, which gives a faint signal to low-level policy, i.e., 20 in Figure 5c.
Adjacency degree
5.4 Qualitative analysis on landmark sampling
In Figure qualitatively analyze how our landmarks sampling method works in the Ant Maze (U-shape, dense) task. We sample 20 coverage-base based landmarks (blue dots) and 20 novelty- based landmarks (red dots); then, we visualize them the goal space (i.e., 2D space). One can find that coverage- based landmarks are dispersed across visited space, and novelty- -baeed ones are concentrated to the frontier of the visited space. In particular, at the early phase of training, the coverage-based landmarks are scattered in the bottom-left region of the maze since an agent is born at the bottom-left corner the beginning an episode, As training proceeds, the agent visits wider regions, so coverage based-landmarrs more scattered across the map. Remarkably, the novelty- -baeed landmarks are concentrated at the frontier the visited space throughout the training phase.
10
Timesteps 100000
Timesteps 200000
Timesteps 300000
Figure 6: Qualitative analysis on the landmark sampling scheme in HIGL. The blue dots and the red dots denote coverage-bant based landmarks and novelty-based landmarks the goal space (i.e., 2D space), respectively. One can observe that the coverage-based landmarks are dispersed across the visited state space, and novelty-base landmarks are concentrated the frontier of the visited space, which is likely to be novel. The analysis is conducted on the Ant Maze (U-shape, dense).

---

Discussion and conclusion
We present HIGL, a new framework for training a high-level policy with reduced action space guided by landmarks. Our main idea is (a) sampling landmarks that are informative for exploration and (b) training the high-level policy to generate a subgoal toward selected landmark. Experiments show that HIGL outperforms the prior state-of-the-ane method thanks to efficient exploration by landmarks. We believe that our framework would guide new interesting direction the HRL: high-level action space reduction into the promising region to explore.
One interesting future work of HIGL would be application to environments with high-dimensional state spaces (i.e., image-based environments). In principle. HIGL is applicable to such environments, but one potential issue is that the required number of landmarks would be increased. The increased number of landmarks can lead to spending more time in planning over a landmark-graph. To alleviate this issue, one can build the priority queue and the landmark-grapy graph in "goal space" instead of "state space"; goal space typically has a lower dimension. The reason why one can build them in "goal space" comes from the fact that HIGL eventually utilizes landmarks in "goal space" rather than "state space," as equation 8 shows. We expect that HIGL combined with subgoal representation learning (which learns state to goal mapping function) would be successful since has shown promising performance on environments with high-dimensional state spaces [21, 29, 46).
Limitation. While our experiments demonstrate that HIGL is effective for solving complex control tasks, we only consider the setup where the final goal of a task is given. An interesting future direction to develop landmark selection scheme that works without the final goal, i.c., selecting the very first landmark in the shortest path to pseudo final goal, (i.e., hindsight goal).
Also, one may point out that the cost consumed for planning may cause scalability issue, perform the shortest path planning at every training step. To be specific, for 1M training timesteps, HIGL takes 13 hours, and HRAC takes 6 hours using a single GPU (NVIDIA TITAN Xp) and 8 CPU cores (Intel Xeon E5-2630 v4). However, given that (i) our method does not utilize planning at deployment time where the execution response time is important, and (ii) environment interaction for sample collection is often dangerous and expensive, we believe that incurring such costs to improve the response time and the sample-efficiency of the algorithm is a reasonable and appropriate direction.
Potential negative impacts. This work would promote the research in the field of HRL and has potential real-world applications such as robotics. However, there could be potential negative consequences of developing an algorithm for autonomous agents. For example, a malicious user specifies reward function that corresponds to harmful behavior for a society, an RL agent would just learn such behaviors without considering the expected results. Specifically, developing an HRL agent for solving complex and long-term task would facilitate the development of the real-world deployment of malicious robots, which could perform a long-horizon operation in an autonomous way without the direction of human. For this reason, in addition to developing an HRL and RL algorithms for improving the sample efficiency and performance, it is important to devise a method that could consider the consequence of its own behaviors to society.
Acknowledgments and Disclosure of Funding
We thank Kimin Lee and anonymous reviewers for providing helpful feedback and suggestions in improving our paper. This work was supported by Institute of Information communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) 2No. 0-00075, Artificial Intelligence Graduate School Program (KAIST)) and the Engineering Research Center Program through the National Research Foundation of Korea (NRF) funded by the Korean Government MSIT (NRF-2018R ASA
10

---

References
[1] Badia, Adrià Puigdomenech, Piot, Bilal, Kapturowski, Steven, Sprechmann, Pablo, Vitvitskyi, Alex, Guo, Zhaohan Daniel, and Blundell, Charles. Agent57: Outperforming the atari human benchmark. In International Conference on Machine Learning, pp. 507-517. PMLR, 2020.
[2] Bellemare, Marc, Srinivasan, Sriram, Ostrovski, Georg, Schaul, Tom, Saxton, David, and Munos, Remi. Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 29: 29:1471-1479, 2016.
[3] Burda. Yuri, Edwards, Harrison, Storkey, Amos, and Klimov, Oleg. Exploration by random network distillation. In International Conference on Learning Representations, 2018.
[4] Chua, Kurtland, Calandra, Roberto, McAllister, Rowan, and Levine, Sergey. Deep reinforce- ment learning in handful of trials using probabilistic dynamics models. arXiv preprini 1805. 121 24,4,, 2018.
[5] Dayan, Peter and Hinton, Geoffrey E. Feudal reinforcement learning. Advances in Neural Information Processing Systems, 1993.
[6] Dilokthanakul, Nat, Kaplanis, Christos, Pawlowski, Nick, and Shanahan, Murray. Feature control as intrinsic motivation for hierarchical reinforcement learning. IEEE transactions on neural networks and learning systems, (111))3349341111 2019.
[7] Duan, Yan, Chen, Xi. Houthooft, Rein, Schulman, John, and Abbeel, Pieter. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pp. 1329-1338. PMLR, 2016.
[8] Eysenbach, Ben, Salakhutdinov, Russ R, and Levine, Sergey. Search on the replay buffer: Bridging planning and reinforcement learning. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httttps://ppoceedinng neurips. cc/paperr/219/fileee
pdf.
[9] Florensa, Carlos, Duan, Yan, and Abbeel, Picter. Stochastic neural networks for hicrarchical reinforcement learning. In International Conference on Learning Representations, 2017.
[10] Fujimoto, Scott, Hoof, Herke, and Meger, David. Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning, pp. 1587-1596.
PMLR, 2018.
[11] Ghosh, Dibya, Gupta, Abhishek, and Levine, Sergey. Learning actionable representations with goal conditioned policies. In International Conference on Learning Representations, 2019.
URL https: //tp:///////eeiiex// net wewt//orreiideeeeeeeeeeeeeeeeeee -iyyenntt..
[12] Hazan, Elad, Kakade, Sham, Singh, Karan, and Van Soest, Abby. Provably efficient maximum entropy exploration. In International Conference Machine Learning, pp. 2681-2691. PMLR, 2019.
[13] Houthooft, Rein, Chen, Xi, Duan, Yan, Schulman, John, De Turck, Filip, and Abbeel, Picter. Vime: Variational information maximizing exploration. arXiv preprint 60X1v:/605.09674, 2016.
[14] Huang, Zhiao, Liu, Fangchen, and Su, Hao. Mapping state space using landmarks for universal goal reaching. Advances in Neural Information Processing Systems, 32:1942-1953 2019.
[15] Kalashnikov, Dmitry, Irpan, Alex, Pastor, Peter, Ibarz, Julian, Herzog, Alexander, Jang, Eric, Quillen, Deirdre, Holly, Ethan, Kalakrishnan, Mrinal, Vanhoucke, Vincent, al. Qt-opt: Scalable deep reinforcement learning for vision-based robotic manipulation. arXiv preprint arXiv:1806. 10293, 2018.
[16] Kulkarni, Tejas D, Narasimhan, Karthik R, Saeedi, Ardavan, and Tenenbaum, Joshua B. Hierar- chical deep reinforcement learning: integrating temporal abstraction and intrinsic motivation. In Proceedings of the 30th International Conference on Neural Information Processing Systems,
pp. 3682-3690, 2016.
11

---

[17]
Laskin, Michael, Emmons, Scott. Jain, Ajay, Kurutach, Thanard, Abbeel, Pieter, and Pathak, Deepak. Sparse graphical memory for robust planning. arXiv preprint arXiv:2003.064/ 2020.
[18] Lee, Lisa, Eysenbach, Benjamin, Parisotto, Emilio, Xing, Eric, Levine, Sergey, and Salakhutdi- nov, Ruslan. Efficient exploration via state marginal matching, arXiv preprint arX:v:190..05274, 2019.
[19] Levy, Andrew, Konidaris, George, Platt, Robert, and Saenko, Kate. Learning multi-level hierarchies with hindsight. In International Conference on Learning Representations, 2018.
[20] Li, Siyuan, Wang, Rui, Tang, Minxue, and Zhang, Chongjie. Hierarchical reinforcement learning with advantage-based auxiliary rewards. In Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpttt/////prceeeeee hnrpp////.p.oeedd......i...ipipp neurips. cc cc/paper/2019/fi10 (tt.:ieee1177777781811 /tt1////675511111777777000011111 Paper påf.
[21] Li. Siyuan, Zheng. Lulu, Wang, Jianhao, and Zhang, Chongjie. Learning subgoal representations with slow dynamics. In International Conference on Learning Representations, 2021. URL
https://openrevvie:: wtw.ae.e.......oraaaraaasaaaaaaa 1dwwxRuhSdORKK..
[22] Liu, Kara, Kurutach, Thanard, Tung, Christine, Abbeel, Pieter, and Tamar, Aviv. Hallucinative topological memory for zero-shot visual planning. In International Conference on Machine Learning, pp. 6259-6270. PMLR, 2020.
[23] Mannor, Shie, Menache, Ishai, Hoze, Amit, and Klein, Uri Dynamic abstraction in reinforce- ment learning via clustering. In Proceedings of the twenty-first international conference on Machine learning, pp. 71, 2004.
[24] McGovem, Amy and Barto, Andrew G. Automatic discovery of subgoals in reinforcement learning using diverse density. 2001.
[25] Menache, Ishai, Mannor, Shie, and Shimkin, Nahum. aout-dynamic discovery of sub-goals in reinforcement learning. In European Conference on Machine Learning, pp. 295-306. Springer, 2002.
[26] Mnih, Volodymyr, Kavukcuoglu, Koray, Silver, David, Rusu, Andrei A, Veness, Joel, Bellemare, Mare G. Graves, Alex, Riedmiller, Martin, Fidjeland, Andreas K. Ostrovski. Georg, al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015.
[27] Mutti, Mirco, Pratissoli, Lorenzo, and Restelli, Marcello. A policy gradient method for task- agnostic exploration. 2020.
[28] Nachum, Ofir, Gu, Shixiang, Lee, Honglak, and Levine, Sergey. Data-efficient hierarchical reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 3307-3317, 2018.
[29] Nachum, Ofir, Gu, Shixiang, Lee, Honglak, and Levine, Sergey. Near-optimal representation learning for hierarchical reinforcement learning. In International Conference on Learning Representations, 2019.
[30] Nagabandi, Anusha, Clavera, Ignasi, Liu, Simin, Fearing, Ronald S, Abbeel, Pieter, Levine, Sergey, and Finn, Chelsea. Learning to adapt in dynamic, real-world environments through meta-reinforrement learning. In ICLR, 2019.
[31] Nair, Suraj and Finn, Chelsea. Hierarchical foresight: Self-supervised learning of long-horizon tasks via visual subgoal generation. In International Conference Learning Representations, 2019.
[32] Nasiriany, Soroush, Pong, Vitchyr, Lin, Steven, and Levine, Sergey. Planning with goal- conditioned policies. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: / htttop://proceeedigg www..ne.....c.... cctppper/ppp1//////////ppp (i11//8cdd000aff4000221211111111
pdf.
[33] Ostrovski, Georg, Bellemare, Mare G, Oord, Aäron, and Munos, Rémi. Count-based exploration with neural density models. International conference on machine learning, pp. 2721-2730. PMLR, 2017.
12

---

[34] Pathak, Deepak, Agrawal, Pulkit, Efros, Alexei A, and Darrell, Trevor. Curiosity-drive driven exploration by self-supervised prediction. In International Conference on Machine Learning. pp. 2778-2787. PMLR, 2017.
[35] Péré, Alexandre, Forestier, Sébastien, Sigaud, Olivier, and Oudeyer, Pierre- Unsupervised learning of goal spaces for intrinsically motivated goal exploration. In International Conference on Learning Representations, 2018.
[36] Savinov, Nikolay, Dosovitskiy, Alexey, and Koltun, Vladlen. Semi-parametric topological memory for navigation. In International Conference on Learning Representations, 2018. URL https://openrevies: www.::/tt/fo.mmmmmeeee wor.ooidouusporrr SyggwwwGW..
[37] Schmidhuber. Jürgen and Wahnsiedler, Reiner. Planning simple trajectories using neural subgoal. In From Animals to Animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behavior, volume 2, pp. 196. MIT Press, 1993.
[38] Schrittwieser, Julian, Antonoglou, Ioannis, Hubert, Thomas, Simonyan, Karen, Sifre, Laurent, Schmitt, Simon, Guez, Arthur, Lockhart, Edward, Hassabis, Demis, Graepel, Thore, al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839): 604-609, 2020.
[39] Sekar, Ramanan, Rybkin, Oleh, Daniilidis, Kostas, Abbeel, Pieter, Hafner, Danijar, and Pathak, Deepak. Planning to explore via supersspe world models. In International Conference on Machine Learning, pp. 3583-8592. PMLR, 2020.
[40] Seo, Younggyo, Chen, Lili, Shin, Jinwoo, Lee, Honglak, Abbeel, Pieter, and Lee, Kimin. State entropy maximization with random encoders for efficient exploration. arXiv preprint arXivv2102.09440. 2021.
[41] Shang, Wenling, Trott, Alex, Zheng, Stephan, Xiong, Caiming, and Socher, Richard. Learning world graphs to accelerate hierarchical reinforcement learning, arXiv preprint 97.0666,,, 2019.
[42] Silver, David, Hubert, Thomas, Schrittwieser, Julian, Antonoglou, Ioannis, Lai, Matthew, Guez, Arthur, Lanctot, Marc, Sifre, Laurent, Kumaran, Dharshan, Graepel, Thore, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 140-64419)1140-1111 2018
[43] Şimzek, Özgür and Barto, Andrew G. Using relative novelty to identify useful temporal abstrac- tions in reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 95, 2004.
[44] Sukhbaatar, Sainbayar, Denton, Emily, Szlam, Arthur, and Fergus, Rob. Learning goal embed- dings via self-play for hicrarchical reinforcement learning. arXiv preprint 1..i::8811.0999 2018.
[45] Sutton, Richard S and Barto, Andrew G. Reinforcement learning: An introduction. MIT Press, 2018.
[46] Tang, Da, Li, Xiujun, Gao, Jianfeng, Wang, Chong, Li, Lihong, and Jebara, Tony. Subgoal discovery for hierarchical dialogue policy learning. In EMNLP, pp. 2298-2309, 2018. URL inf wnfoopapers/DDee 1-01-11---11/1111
[47] Tang, Haoran, Houthooft, Rein, Foote, Davis, Stooke, Adam, Chen, Xi, Duan, Yan, Schulman, John, De Turck, Filip, and Abbeel, Pieter. # exploration: A study of count-based exploration for deep reinforcement learning. In 3 Conference on Neural Information Processing Systems (NIPS), volume 30, pp. 1-18, 2017.
[48] Todorov, Emanuel, Erez, Tom, and Tassa, Yuval. Mujoco: A physics engine for model-based control. In 2012 IEEF/RSJ International Conference on Intelligent Robots and Systems, pp- 5026-5033. IEEE, 2012.
13

---

[49] Vassilvitskii.
Sergei and Arthur, David. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1027-1035, 2006.
[50] Vezhnevets, Alexander Sasha, Osindero, Simon, Schaul, Tom, Heess, Nicolas, Jaderberg. Max, Silver, David, and Kavukcuoglu, Koray. Feudal networks for hierarchical reinforcement learning. In International Conference on Machine Learning, pp. 1540-35499 PMLR, 2017.
[51] Zhang. Amy, Sukhbaatar, Sainbayar, Lever, Adam, Szlam, Arthur, and Fergus, Rob. Composable planning with attributes. In International Conference on Machine Learning, pp. 5842-5851.
PMLR, 2018.
[52] Zhang, Lunjun, Yang, Ge, and Stadie, Bradly C. World model graph: Learning latent landmarks for planning. In International Conference on Machine Learning, pp. 12611-12620.
PMLR, 2021.
[53] Zhang, Marvin, Vikram, Sharad, Smith, Laura, Abbeel, Pieter, Johnson, Matthew J, and Levine, Sergey, Solar: deep structured representations for model-based reinforcement learning. In ICML, 2019.
[54] 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.
14


Reviews:
[{"review_id": "zn5uD0w_tfN", "reviewer": "Reviewer_RGnx", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong:\n* I like Figure 1: really strong illustration of the overall method, very clear as well. \n* 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. \n* 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).\n\nWeak/comments:\n* 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)?).\n* For the coverage based approach to hierarchy, I think you missed an important early reference [1].\n* 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. \n* 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?\n* Alg 1: Is the subgoal transition function h() learned, or given? It seems to be given, but how is it specified?\n* Alg 1: on what loss is the lower level trained? Just a standard goal-conditioned value-based loss?\n* 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? \n* The evaluation environments are rather small.\n* Fig 4a: I do not see a difference between 40 and 60 really? Only 20 does not work?\n* L241-253: And the other way around, what does coverage add over novelty? \n* There are some typo’s in your document, double words, etc.\n* 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. \n\nConclusion:\nIn 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Accurately addressed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "g-1XT2q4e8", "reviewer": "Reviewer_HpCw", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.   \n\nOverall, 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. \n\n(1)\tMore 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?     \n\n(2)\tSparse 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?    \n\n(3)\tParameter 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.\n\n(4)\tNovelty-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? \n\n(5)\tComputation complexity: it would be interesting to compare the computation time (HIGL vs. HRAC), so the readers understand how much computational overhead is needed. \n\n(6)\tHigh-dimensional imagery inputs: any ideas on how to generalize the framework to handle image inputs or image-based goals? This could be another limitation? \n\nMinor comments:\n\n(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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed adequately limitation and social impact in Section 6. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.25"}, "extra_text": {}}, {"review_id": "57WXGnIGbCQ", "reviewer": "Reviewer_zAqr", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The following questions need to be addressed.\n\nQ.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.\n\nReferences:\n\n[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.\n\n[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.\n\nQ.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.\n\nQ.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}$. \n\nQ.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.\n\nQ.5 Does HIGL suffer from performance degeneration when landmarks are insufficient? Do high-dimensional state spaces need a large number of landmarks?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.25"}, "extra_text": {}}]

Author rebuttal:

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)