Successor Feature Landmarks for Long-Horizon Goal-Conditioned Reinforcement Learning
Authors: Christopher Hoang
Sungryull Sohn
Jongwook Choi
Wilka Torrico Carvalho
Honglak Lee
Venue: NeurIPS 2021 Poster (2021)
Keywords: successor features
goal-conditioned RL
graph-based planning

Abstract: Operating in the real-world often requires agents to learn about a complex environment and apply this understanding to achieve a breadth of goals. This problem, known as goal-conditioned reinforcement learning (GCRL), becomes especially challenging for long-horizon goals. Current methods have tackled this problem by augmenting goal-conditioned policies with graph-based planning algorithms. However, they struggle to scale to large, high-dimensional state spaces and assume access to exploration mechanisms for efficiently collecting training data. In this work, we introduce Successor Feature Landmarks (SFL), a framework for exploring large, high-dimensional environments so as to obtain a policy that is proficient for any goal. SFL leverages the ability of successor features (SF) to capture transition dynamics, using it to drive exploration by estimating state-novelty and to enable high-level planning by abstracting the state-space as a non-parametric landmark-based graph. We further exploit SF to directly compute a goal-conditioned policy for inter-landmark traversal, which we use to execute plans to "frontier" landmarks at the edge of the explored state space. We show in our experiments on MiniGrid and ViZDoom that SFL enables efficient exploration of large, high-dimensional state spaces and outperforms state-of-the-art baselines on long-horizon GCRL tasks.

Successor Feature Landmarks for Long-Horizon Goal-Conditioned Reinforcement Learning
Christopher Hoang
Sungryull Sohn 12
Jongwook Choi
Wilka Carvalho
Honglak Lee 12
University of Michigan [choang, srsohn, juook, wcarvalh, honglak @umi ch. edu
LG Al Research
Abstract
Operating in the real-world often requires agents to learn about a complex envi- ronment and apply this understanding to achieve breadth of goals. This problem, known as goal-conditioned reinforcement learning (GCRL), becomes especially challenging for long-horizon goals. Current methods have tackled this problem by augmenting goal-conditioned policies with graph-based planning algorithms. However, they struggle to scale to large, high-dimensional state spaces and assume access exploration mechanisms for efficiently collecting training data. In this work, we introduce Successor Feature Landmarks (SFL), a framework for exploring large, high- -igh-dimensional environments any goal. SFL leverages the ability of successor features (SF) to capture transition dynamics, using it to drive exploration by estimating state-novelty and to enable high-level planning by abstracting the state-space as a non-parametric landmark- based graph. We further exploit SF to directly compute goal-conditioned policy for landralan traversal, which we use to execute plans to "frontier" landmarks the edge of the explored state space. We show in our experiments on MiniGrid and ViZDoom that SFL enables efficient exploration of large, high-dimensional state spaces and outperforms state-of-the-ar baselines long-horizon GCRL tasks'
to obtain policy that is proficient for
Introduction
Consider deploying self-driving car to new city. To be practical, the should be able to explore the city such that can learn to traverse from any starting location to any destination, since the destination may vary depending the passenger. In the context of reinforcement learning (RL), this problem known as goal-conditioned RL (GCRL) [12, 13]. Previous works [31, 1, 1,,4, 26, 17] have tackled this problem by learning coal-conditioned policy (or value function) applicable to any reward function or "goal." However, the goal-conditioned policy often fails to scale to Long-horizon goals [11] since the space of state-goal pairs grows intractably large over the horizon of the goal.
To address this challenge, the agent needs to (a) explore the state-goal space such that is proficient for any state-goal pair might observe during test time and (b) reduce the effective goal horizon for the policy learning to be tractable. Recent work [25, 11] has tackled long- horizon GCRL by leveraging model-bascd approaches form plans consisting of lower remporal-resolution subgoals. The policy is then only required to operate for short horizons between these subgoals. One line of work learned a universal value function approximator (UVFA) [31] to make local policy decisions and to estimate distances used for building a mondmark-based map, but assumed a low-dimensional state space where the proximity between the state and goal could be computed by the Euclidean distance [11]. Another line research focused on visual navigation tasks conducted planning over
'The demo video and code can be found at https::/2016ccheat github. io/sfl.
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

1. Select frontier landmark
2. Plan path to frontier landmark
3. Execute planned path with goal conditioned policy 5i
Initaal state
Landmarks
Planned Path
landmark
Explored region
Planned path
Edge
Goul-cunditoned policy
5. Update graph SF with trajectory
Random policy
Trajectory
Graph +
Graph + SF
4. Use random policy
Update
it to explore
Figure I: High-level overview of SFL. 1. During exploration, select a frontier landmark (red circled dot) lying at the edge of the explored region as the target goal. During evaluation (not shown in the figure), the actual goal is selected as the target goal. Use the graph plan landmark path (green lines) to the target goal. 3. Execute the planned path with the goal-conditioned policy (black dotted arrow). 4. During exploration, upon reaching the frontier landmark, deploy the random policy (red dotted arrow) to reach novel states in unexplored areas. 5. Use each transition in the trajectory to update the graph and SF (see Figure 2). Note: The agent is never shown the top-down view of the maze and only uses first-person image observations (example on left) to carry out these steps. Goals are also given as first- first-person images.
graph representations of the environment [29, 9, 16, 4]. However, these studies largely ignored the inherent exploration challenge present for large state spaces, and either assumed the availability of human demonstrations of exploring the state space [29], the ability to spawn uniformly over the state space [9, 16], or the availability of ground-truth map information [4].
In this work, we aim to learn an agent that can tackle long- long-horizon GCRL tasks and address the associated challenges in exploration. Our key idea is use successor features (SF) [15, 2] representation that captures transition dynamics - to define a novel distance metric, Successor Feature Similarity (SFS). First, we exploit the transfer ability of SF to formulate a goal-conditioned value function in terms of SFS between the current state and goal state. By just learning SF via self-supervised representation learning, we can directly obtain coal-conditioned policy from SFS without any additional policy learning. Second, we leverage SFS to build landmark-bass graph representation of the environment; the agent adds observed states as landmarks based on their SFS- predicted novelty and forms edges between landmarks by using SFS as distance estimate. SF as an abstraction of transition dynamics is natural solution for building this graph when we consider the MDP directed graph of states (nodes) and transitions (edges) following [1]]. We use this graph to systematically explore the environment by planning paths towards landmarks at the "frontier" of the explored state space and executing each segment of these planned paths with the goal-conditioned policy. In evaluation, we similarly plan and execute paths towards Klng-horizan goals. We call this framework Successor Feature Landmarks (SFL), illustrated in Figure 1.
Our contributions are as follows: (i) We use a single self-supervised learning component that captures dynamics information, SF, to build all the components of graph-based planning framework, SFL. (ii) We claim that this construction enables knowledge sharing between each module of the framework and stabilizes the overall learning. (iii) We introduce the SFS metric, which serves as a distance estimate and enables the computation goal-conditioned Q-value function without further learning. We evaluate SFL against current graph-based methods in long-horizon goal-reaching RL and visual navigation on MiniGrid [6], 2D gridworld, and ViZDoom [37], visual 3D first-person view environment with large mazes. We observe that SFL outperforms state-of saate-of-hhe-ard art navigation baselines, most notably when goals are furthest away. In a setting where exploration is needed to collect training experience, SFL significantly outperforms the other methods which struggle to scale in ViZDoom's high-dimensional state space.

---

2 Related Work
Goal-conditioned RL. Prior work has tackled GCRL by proposing variants of goal-conditioned value functions such as UVFAs which estimate cumulative reward for any given state-goal pair [23, 34, 31, 26]. HER [1] improved the sample efficiency in training UVFAs by relabeling reached states as goals. Mapping State Space (MSS) [1 then extended UVFAs to long-horizon tasks by using a UVFA as both a goal-conditioned policy and a distance metric to build a graph for high-level planning. MSS also addressed exploration by selecting graph nodes to be at edge of the map's 's explored region via farthest point sampling. However, this method was only evaluated in low-dimensional state spaces. LEAP [25] used goal-conditioned value functions to form and exccute plans over latent subgoals, but largely ignored the exploration question. Conversely, other works [27, 5] have worked on exploration for goal-reaching policies, but do not tackle the long-horizon case. ARC [10] proposed learning representations that measure state similarity according the output of maximum entropy goal-conditioned policy, which can be utilized towards exploration and long-horizon hierarchical RL. However, ARC assumes access to the goal-conditioned policy, which can be difficult to obtain in large-scale environments. Our method can achieve both efficient exploration and long-horizon goal-reaching in high-dimensional state spaces with SF-based metric that acts goal-conditioned value function and distance estimate for graph- building.
Graph-based planning. Recent approaches have tackled long-horizon tasks, often in the context of visual navigation, by conducting planning on high-level graph representations and deploying a low-level controller locally move between nodes; our framework also falls under this paradigm of graph- baaedbbaedddee planning. Works such as SPTM [29] and SoRB [9] used a deep network as a distance metric for finding shortest paths on the graph, but rely human demonstrations sampling from the replay buffer to populate graph nodes. SGM [16] introduced a two-way consistency check to promote sparsity in the graph, allowing these methods to scale to larger maps. However, these methods rely on assumptions about exploration, allowing the agent to spawn uniformly random across the state space during training. To address this, HTM [19] used a generative model to hallucinate samples for building the graph in zero-shot manner, but was not evaluated in 3D visual environments. NTS [4] achieved exploration and long-horizon navigation as well as generalization to unseen maps by learning a geometric-basee
graph representation, but required access to a ground-truth map to train their supervised learning model. In contrast, our method achieves exploration by planning and executing paths towards landmarks near novel areas during training. SFL also does not require any ground-truth data; only needs to learn SF in a self-supervised manner.
Successor features. Our work is inspired by recent efforts in developing successor features (SF) [15, 2]. They have used SF decompose the Q-value function into SF and the reward which enables efficient policy transfer [2, 3] and to design transition- exploration. SF has also been used in the options framework [35]; Eigenoptions [21] derived options from the cigendecomposition of SF, but did not yet apply them towards reward maximization. Successor Options [28] used SF to discover landmark states and design a latent reward for learning option policies, but was limited to low-dimensional state spaces. Our framework leverages SF-based similarity metric to formulate a coal-conditioned policy, abstract the state space as a landmark graph for Long-horizor planning and to model state-novelty for driving exploration. While the options policies proposed in these works have to be learned from a reward signal, we can obtain our goal-conditioned policy directly from the SF similarity metric without any policy learning. To our knowledge, this is first work that uses SF for graph-based planning and long-horizon GCRL tasks.
intrinsic rewards [20, 39] for efficient
3 Preliminaries
3.1 Goal-Conditioned RL
coullconditioned reinforcement learning (GCRL) tasks [12] are Markov Decision Processes (MDP) extended with set of goals G and defined by a tuple (S, G, Rg, T, T,7), where S is state space, A an action set, Rg : S x A x g - IR a goal-conditioned reward function, T the transition dynamics, and y a discount factor. Following [11. 36), we focus on the setting where the goal space & is a subset of the state space S, and the agent can receive non-trivial rewards only when it can reach the goal (i.e., sparse-reward setting). We aim to find an optimal goal goal-conditioned policy π S x G - A to maximize the expected cumulative reward, V (5o) E" I 7're); i.e., goal-conditioned value function. We are especially interested in long-horizon tasks where goals are distant from the agent's starting state, requiring the policy to operate over longer temporal sequences.
3

---

Algorithm 1 Training
Initialize: Graph G (L, (L, E), parameter of SFS replay buffer D, hyperparameter Texp-
landmark transition count N
2: while env not done do
3: Iteatt Softmax(( Count(L)
(Choose frontier landmark via count-based sampling)
4: while luurr o Froms do
5: lurget - PLAN(G, (L,ANG Teurr (iron))
(Plan path to frontier landmark]
6: Tiraverse; Auurr f- Traverse IT, lurget)
(Traverse to lurget with xı (Algorithm {H))
7:
G, No 4 Graph--pppteeec Tiraverse; SFS No)
(Update graph (Algorithm 2))
8:
end while
9: Trand = {8t, az, rt Top
St,
(Explore with random policy for Texp steps)
10:
G, t Graph--UpdteeG; Trand, SFS NY)
(Uddtee graph (Algorithm 2))
+ DU Trandom
12: Update 0 from TD error with mini-batches sampled from D
(Update SF parameters]
end while
3.2 Successor Features
In the tabular setting, the successor representation (SR) [8, 15] is defined as the expected discounted occupancy of futures state s' starting in state and action and acting under policy
as, = Ee "I( s s, a
(1)
The SR (s, a) is then a concatenation of Mss, a, s'), Vs S. We may view SR as a representation of state similarity extended over the time dimension, as described [21]. In addition, we note that the SR is solely determined by and the transition dynamics of the environment p(st-1/5e, 0z).
Successor features (SF) [2, 15] extend SR [8] high-dimensional, continuous state spaces in which function approximation is often used. SF's formulation modifies the definition of SR by replacing enumeration over all states s' with feature vector ds. The SF thtt of a state-action pair (s, a) is then defined as:
2 as) = E
DP
St = A,
In addition, SF can be defined in terms of only the state, 1h" (s) (e) [16 (s, a))
SF allows decoupling the value function into the successor feature (dynamics-relevan) information) with task (reward function): if we assume that the one-step reward of transition (s, a, s') with feature
ø(s, a, s') can written as r(s, a, s') = o(s, o, s') w, where w are learnable weights to fit the write the Q-value function follows [2, 15]:
reward function,
("(sa))=1 = 1T
Av, S = A, =
E
S₁ Ar
= 3/ (
Consequently, the Q-value function separates into SF, which represents the policy-dependent transition dynamics, and the reward vector for a particular task. Later Section 4.3, we will extend this formulation to the goal-conditioned setting and discuss our choices for w.
Successor Feature Landmarks
We present Successor Feature Landmarks (SFL), a graph- based planning framework for supporting exploration and Long-horizon GCRL. SFL is centrally built upon our novel distance metric: Successor Feature Similarity (SFS, 14. We maintain a non non-parametric graph of state "landmarks," using SFS as a distance metric for determining which observed states add as landmarks and how these landmarks should be connected ($4.2). To enable traversal between landmarks, we directly obtain local goal-conditioned policy from SFS between current state and the given landmark ($4.3). With these components, tackle the long-hood horizon setting by planning the landmark graph and finding

---

Edge Formation
Agent
Lecalization
trajectory
argmna SES,
fudge
Landmaris
them:
Currenlyy localized
Previonsly localized
policy
Adding Landmarks
Ageni trajectury'
if:
SFS, < fast
them:
Random Transition
Train SF' ale
Buffer
The Graph + SF Update step occurs after every transition (s, a). The agent computes SFS between current state (black dot) and all landmarks (blue dots). It then localizes itself to the nearest landmark (red circled dot). The agent records transitions between the previously localized landmark (green circled dot) and this landmark. If the number of transitions between landmarks is greater than Sedges then an edge is formed between them. If SFS between the current localized landmark and is less than dadd then is added landmark. Finally, transitions generated by the random policy are added to the random transition buffer, and SF is trained on batch samples from this buffer.
Figure 2:
the shortest path to the given goal, which decomposes the long-horizon problem into sequence of short-horizon tasks that the local policy can then more reliably achieve ($4.4). In training, our agent focuses on exploration. We set the goals as "frontier" landmarks lying at the edge of the explored region, and the planner and local policy to reach the frontier landmark. Upon reaching the frontier, the agent locally explores with a random policy and uses this new data to update its SF and landmark graph ($4.5). In evaluation, we add the given goal the graph and follow the shortest path to Figure illustrates the overarching framework and Figure 2 gives further detail into how the graph and SF are updated. Algorithm describes the procedure used to train SFI.
4.1 Successor Feature Similarity
SFS, the foundation of our framework, is based SF. For context, estimate SF v as the output of a deep neural network parameterized by 8 (s, a) x vig (Ø(s), a). where á is a feature embedding of state and is a fixed policy which choose to be uniform random policy denoted as म. We update 9 by minimizing the temporal difference (TD) error [15, 2]. Details on learning SF are provided in Appendix C.3.
Next, to gain intuition for SFS, suppose we wish to compare two state-action pairs (81,a1) and (82, (2), in terms of similarity. One option is to compare 81 and 82 directly via some metric such as & distance, but this ignores a1, a2 and dynamics of the environment.
To address this issue, we should also consider the states the agent is expected to visit when starting from each state-action pair, for a fixed policy π. We choose only the dynamics of the environment will dictate which states the agent will visit. With this idea, we can define a novel similarity metric, Successor Feature Similarity (SFS), which measures the similarity of the expected discounted state-occupaney of two action pairs. Using the successor representation M₂ (s, a) as defined in Section 3.2, we can simply define SFS as the dot-product between the two successor representations for each state-action pair:
be uniform random, i.c. so that
SFS ((11, 01), (*2, (2))
> E
~ I = ss) I(S
S, 31,
E
Σ
8
IISS =
S, = 82,
A. = a.
A, a2
(4)
s'ES
l'=t
= Σ
M1(s),01,8)) x (=(22,02,51 = (* TT (x(,
e'ES
We can extend SFS to the high-dimensional case by encoding states in the feature space 6 and replacing Mx a) with 3 (s,a). The intuition remains the same, but we instead measure similarities in the feature space. In practice we normalize s (x, before computing SFS to prevent high-value feature dimensions from dominating the similarity metric, hence defining SFS as the cosine similarity between SF. In addition, may define SFS between just two states by getting rid of the action
5

---

dimension in SF:
SFS* 02)) = x0 ($1,01) TT (52,
(5)
SFS ($1,82) = 30 (s1) " (s2)
(6)
4.2 Landmark Graph
The landmark graph G serves as a compact representation of the state space and its transition in an online fashion as the agent explores more of its
dynamics. G is dynamically-pooulaat environment. Formally, landmark graph G = (L, E) is tuple of landmarks L and edges E. The landmark set L = ( + is of states representing the explored part of the state-space.
The edge set E is a matrix R| F.,, where Et.; = 1 if 4 and 1 is connected, and otherwise. Algorithm 2 outlines the graph update process, and the following paragraph describes this process in further detail.
Agent Localization and Adding Landmarks At every time step closest to the agent under SFS metric: leurr = argmax SFS (s,, If SFS (st, leurr) < 6add- the add threshold, then we add 8, to the landmark set L. Otherwise, if SFS* (St, laur) > òiocal. the localization threshold, then the agent is localized to leur- If the agent was previously localized to a different landmark /prev. then we increment the count of the landmark transition N (kar)) by where N' E N!El is the landmark transition count, which is used to form the graph edges.
compute the landmark
Since we progressively build the landmark set, maintain all previously added landmarks. As described above, this enables us to utilize useful landmark metrics such as how many times the agent has been localized to each landmark and what transitions have occurred between landmarks to improve the connectivity quality of the graph. In comparison, landmarks identified through clustering schemes such as in Successor Options [28] cannot be used in this manner because the landmark set is rebuilt every few iterations. See Appendix B.3 for a detailed comparison on landmark formation.
Edge Formation We form edge Eig if the number of the landmark transitions is larger than the edge threshold, Le., NY.
Algorithm 2 Graph-Update (64.2)
with weight W., = exp(-(N), -1 > dedge: ))- We apply filtering improvements to F. in ViZ- Doom to mitigate the perceptual aliasing problem where faraway states can appear vi- sually similar due to repeated use of textures. See Appendix D for more details.
input Graph G = L)) SFS trajectory T,
landmark transition count N'
output updated graph G and N fprev + 0
(Previously localized landmark]
2: for E do
3: leur argmax (s,
(Localize)
4: if SFS (s. Tour) &oad then
4.3 Local Goal-Condi Policy
5:
-+LUs
[Add landmark]
6: end if
We want to learn a local goal-conditioned policy क. S x + A to reach tran- sition between landmarks. To accomplish this, Mi should maximize the expected return (s.gg = E 7"r(s,, ar, g)], where r(s, a, is a reward function that captures how close s (or more precisely s, a) is to the goal g in terms of feature similarity:
7:
if SFS (s, leurr) > Stocat then
8:
if "peey * and lprev * lour then No
N! (pm (lam))
(1om Hanr) + (Record
landmark transition]
10:
if N (mma)) > dedge then
11:
E+ t E (prer + leurr) {Form edge)
12:
end if
13:
end
r(s, a, g) = o(s, a) T 15 (g),
14: Lprev + leur
15: end if
where 8º is the SF with respect to the ran- decouple
16: end for
dom policy म. Recall that the Q-value function into the SF represen- tation and reward weights Eq. (3). The reward function Eq. (7) is our deliberate choice rather than learning a linear reward regression model [2], so the value function can be instantly computed. If we let be ()"()))) (g), can
17: return G, N
shown in
'Zhang et al. [38] proposed similar idea of recording the transitions between sets of user-defined attributes. We extend this idea to the function approximation setting where landmark attributes are their SFs.

---

have the Q-vauue function (s, for the goal-conditioned policy (.)ss being equal to the SFS between s and g:
() (s,a) (g) -SSSSFSS (s as)
(8)
The coal-conditioned policy is derived by sampling actions from the goal-conditioned Q-value function greedy manner for discrete actions. In the continuous action case, we can learn the goal-conditioned policy by using a compatible algorithm such as DDPG [18]. However, extending SF learning to continuous action spaces beyond the scope of this work and is left for future work.
4.4 Planning
Given the landmark graph G. we can plan the shortest-path from the landmark closest the agent luur to a final target landmark haaget by selecting a sequence of landmarks [lo. 11....... .. [R] in the graph G with minimal weight (see $4.2) sum along the path, where lo = leurr l Lunget and is the length of the plan. In training, we use frontier landmarks Iiont which have been visited less frequently as hurget- In evaluation, the given goal state is added to the graph and set as lurget. See Algorithm for an overview of how planning is used to select the agent's s low-level policy in training.
4.5 Exploration
We sample frontier landmarks from proportional to the inverse of their visitation count (i.e., with count-based exploration). We use two policies: a local policy m for traversing between landmarks and random policy π for exploring around frontier landmark. Given target frontier landmark 4rom we construct a plan [lg, 11....... [ When the agent localized to landmark 4, the policy at time defined as Tr(a|s:; 441). When the agent is localized to landmark that is not included in the current plan (o, 4 ...... ] then it re-plans a new path to front- Such failure cases transition between the landmarks are used to prevent edge between those landmarks from being formed (see Appendix D for details). We run this process until either (treut reached or until the step-limit Nireat is reached. At that point, random policy मे is deployed for exploration for Nexplore steps. adding novel states to our graph as a new landmark. While the random policy is deployed, its trajectory t ~ म is added to the random transition buffer. SF 2 is updated with batch samples from this buffer.
The random policy is only used to explore local neighborhoods frontier regions for a short horizon while the goal-conditioned policy and planner are responsible for traveling to these frontier regions. Under this framework, the agent is able to visit a diverse set of states a relatively efficient manner. Our experiments large ViZDoom maps demonstrate that this strategy is sufficient for learning SF representation that ultimately outperforms baseline methods on goal-reaching tasks.
5 Experiments
In our experiments, we evaluate the benefits of SFL for exploration and long-horizon GCRL. We first study how well our framework supports reaching long- horg-oorizon goals when the agent's start state is randomized across episodes. Afterwards, we consider how SFL performs when efficient exploration required to reach distant areas by using setting where the agent's 's start state is fixed in training.
5.1 Domain and Goal-Specification
ViZDoom is a visual navigation environment with 3D first-person observations. In ViZDoom, the large- scale of the maps and reuse of similar textures make it particularly difficult to learn distance metrics from the first-pent first-person observations. This is due to percep- tual aliasing, where visually similar images geographically far apart. We use mazes from SPTM in our experiments, with one example shown in Fig- ure 3 [29].
Start Position
Easy
Medium
Hard
Hardest
be
MiniGrid is 2D gridworld with tasks that require the agent to overcome different obstacles to access portions of the map. We experiment on FourRoom, a basic 4-room map, and MultiRoom, where the agent needs to open doors to reach new rooms.
Figure 3: Top-down view of ViZDoom maze used in fixed spawn with sampled goal locations. Examples of image goals given to the agent are shown at the bottom. Note that the agent cannot access the top-down view.
7

---

We study two settings:
1. Random spawn:
In training, the agent is randomly spawned across the map with no given goal. In evaluation, the agent is then tested on pairs of start and goal states, where goals are given as images. This enables start-goal pairs. Following [16], we evaluate on easy, medium, and hard tasks where the goal is sampled within 200m, 200-400m, and 400-600m from the initial state, respectively.
study how well the landmark graph supports traversal between arbitrary
2. Fixed spawn: In training. the agent is spawned at a fixed start state Sstart with no given goal. This enables us study how well the agent can explore the map given limited step budget per episode. In evaluation, the agent is again spawned at Sttart and is given different goal states to reach. In ViZDoom, we sample goals of varying difficulty accounting for the maze structure as shown in Figure 3. In MiniGrid, a similar setup is used except only one goal state is used for evaluation.
5.2 Baseline Methods for Comparison
Random spawn experiments. We compare SFL against baselines used in SGM, as described below. For each difficulty, we measure the average success rate 5 random seeds. We evaluate on the map used in SGM, SGM-Map, and two more maps from SPTM, Test-2 and Test-6.
1. Random Actions: random acting agent. Baseline shows task difficulty.
2. Visual Controller: model-free visual controller learned via inverse dynamics. Baseline highlights how low-level controllers struggle learn long- nogghhoizzon policies and the benefits of planning to create high-level paths that the controller can follow.
3. SPTM [29]: planning module with reachability network to learn distance metric for localization and landmark graph formation. Baseline is used to measure how the SFS metric can improve localization and landmark graph formation.
4. SGM [16]: data structure used to improve planning by inducing sparsity in landmark graphs. Baseline represents recent landmark- approach for long-horizon navigation.
Fixed spawn experiments. In the fixed spawn setting, we compare SFL against Mapping State Space (MSS) [1]], UVFA and landmark-based approach for exploration and long-horizon goal- conditioned RL, as well as SPTM and SGM. Again, we measure the average success rate over random seeds. We adapt the published code to work ViZDoom and MiniGrid. To evaluate SPTM and SGM, we populate their graphs with exploration trajectories generated by Episodic Curiosity (EC) [30]. EC learns an exploration policy by using reachability network to determine whether an observation is novel enough to be added to the memory and rewarding the agent every time one is added. Appendix C further discusses the implementation of these baselines.
5.3 Implementation Details
SFL is implemented with the ripyr codebase [33]. For experiments in ViZDoom, we the pretrained ResNet-18 backbone from SPTM as a fixed feature encoder which is similarly used across all baselines. For MiniGrid, train convolutional feature encoder using time-contrastive metric learning [32]. Both feature encoders are trained in a self-supervised manner and aim to encode temporally close states as similar feature representations and temporally far states dissimilar representations. We then approximate SF with a fully-connected neural network, using these encoded features as input. See Appendix for more details on feature learning, edge formation, and hyperparameters.
5.4 Results
Random Spawn Results. As shown in Table 1, method outperforms the other baselines all settings. SFL's performance on the Hard setting particularly illustrates its ability to reach long-horizon goals. In terms of sample efficiency, SFL utilizes total of 2M environment steps to simultaneously train SF and build the landmark graph. For reference, SPTM and SGM train their reachability and low-level controller networks with over 250M environment steps of training data collected on SGM-Map, with SGM using an additional 1 14K steps to build and cleanup their landmark graph. For Test-2 and Test-6, we fine-tune these two networks with 4M steps of training data collected from each new map to give a fair comparison.
'https://githnnn http:/twwww....eooeeceeeaaaaa/ap
8

---

Method
SGM-Map Medium
Test-2 Medium
Test-6
Easy
Hard
Easy
Hard
Easy
Medium
Hard
Random Actions
58%
22%
12%
70%
39%
16%
80%
31%
18%
Visual Controller
75%
35%
19%
83%
51%
30%
89%
39%
20%
SPTM [29]
70%
34%
14%
78%
48%
18%
88%
40%
18%
SGM [16]
92%
64%
26%
86 %
54%
32%
83%
43%
27%
SFL [Ours]
92%
82%
67%
82%
66%
48 %
92%
66 %
60%
Table 1: (Random spawn)
The success rates of compared methods on three ViZDoom maps.
Method
Test-1
Test-4
Easy
Medium
Hard
Hardest
Easy
Medium
Hard
Hardest
MSS [11]
23%
9%
1%
1%
21%
7%
7%
7%
EC [30] SPTM [29]
48%
16%
2%
0%
20%
10%
4%
0%
EC [30] + SGM [16]
43%
3%
0%
0%
28%
7%
4%
1%
SFL [Ours]
85%
59 %
62%
50%
66%
44%
27 %
23 %
Table 2: (Fixed spawn) The success rates of compared methods on three ViZDoom maps.
Fixed Spawn Results. We see in Table that SFL reaches significantly higher success rates than the baselines across all difficulty levels, especially Hard and Hardest. Figure 4 shows the average success rate over the number of environment steps for SFL (red) and MSS (green). We hypothesize that MSS struggles because its UVFA is unable capture geodesic distance in ViZDoom's high- dimensional state space with first-person views. The UVFA in MSS has to solve the difficult task of approximating the number of steps between states, which conjecture requires larger sample complexity and more learning capacity. In contrast, we only use SFS to relatively compare states, i.e. SFS of state A higher than SFS of state B with respect reference state C? EC-augmented SPTM and SGM partially outperform MSS, but cannot scale to harder difficulty levels. We suggest that these baselines suffer from disjointedness exploration and planning: the EC exploration module is less effective because it does not utilize planning to efficient reach distant areas, which in turn limits the training of policy networks. See Appendix F and Appendix G for more analysis on the baselines.
Figure 5 shows the average success rate on MiniGrid enviromments, where SFL (red) overall outperforms MSS (green). States in MiniGrid encode top-down views of the map with distinet signatures for the agent, walls, and doors, making it easier to learn distance metrics. In spite of this, the environment remains challenging due to the presence of doors obstacles and the limited time budgel per episode.
100
Easy
100
Medium
100
FourRoam
Tio-Raom MultiReom
M
Success Rate
Success Rate
Success Rate
75
Success
50
50
50
50
25
25
25
200
400
800
800
%
200 400 600
800
%
100 150 200 50
100 200 300 400 500 Steps (Thousands)
Steps (Thousands)
(Thousands)
Steps (Thousands)
100
Herd
100
Hardest
100
Three-Room MultiRoom
100
Four-Room MultiReom
Success Rate
SFL
Success Rate
Success Rate
SFL
75
75
75
75
Success
50
50
50
25
25
%
200 400
600
800
%
200
400
600
800
100 200 300 400 500
200 (Thousaans)
400
600
800
Steps (Thousards)
Steps
(Thousands)
Steps (Thousands)
Steps
Figure 4: Fixed spawn experiments on ViZ.Doom comparing SFL (red) to MSS (green) over number of environment steps for varying difficulty levels.
Figure 5: Fixed spawn experiments on MiniGrid comparing SFL (red) to MSS (green) over number of environment steps for varying difficulty levels.

---

Reference State
0.0
0.2
0.4
0.6
0.8
1.0
Successor Feature Similarity
Figure 6: SFS values relative reference state (blue dot) in the Tèst-I ViZDoom maze. The left two heatmaps use the agent's start state as the reference state while the right two use a distant goal state the reference state. The first and third (colorful) heatmaps depict all states while the second and fourth (darkened) heatmaps only show states with SFS > òiocal 0.9.
5.5 SFS Visualization
SFL primarily relies on SFS and its capacity to approximate geodesic distance imposed by the map's structure. To provide evidence of this ability, we compute the SFS between reference state and of randomly sampled states. Figure 6 visualizes these SFS heatmaps in a ViZDoom maze, In the first and third panels, we observe that states close the reference state (blue dot) exhibit higher SFS values while distant states, such as those across a wall, exhibit lower SFS values. The second and fourth panels show states in which the agent would localized the reference state, i.c. states with SFS > 6jocal- With this SFS threshold, we reduce localization errors, thereby improving the quality of the landmark graph. We provide additional analysis of SFS-derived components, the landmark graph and goal-cone condiiontt policy, in Appendix E.
Conclusion
In this paper, we presented Successor Feature Landmarks, a graph- based planning framework that leverages SF similarity metric, as an approach to exploration and long-horizon goal-conditioned RL. Our experiments in ViZDoom and MiniGrid, demonstrated that this method outperforms current graph-based approaches on long-horizon goal-reaching tasks. Additionally, we showed that our framework can be used for exploration, enabling discovery and reaching of goals far away from agent's starting position. Our work empirically showed that SF can be used to make robust decisions about environment dynamics, and hope that future work will continue along this line by formulating new uses of this representation. Our framework is built upon the representation power of SF, which depends good feature embedding to be learned. We foresee that our method can be extended by augmenting with an algorithm for learning robust feature embeddings facilitate SF learning.
Acknowledgements
This work was supported by the NSF CAREER IIS 1453651 Grant. JC was partly supported by Korea Foundation for Advanced Studies. WC was supported by NSF Fellowship under Grant No. DGE1 88600 Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies. We thank Yunseok Jang and Anthony Liu for their valuable feedback. We also thank Scott Emmons and Ajay Jain for sharing and helping with the code for the SGM [16] bascline.
10

---

References
[1] Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems 30, pages 5048-5058, Curran Associates, Inc., 2017.
[2] Andre Barreto, Will Dabney, Remi Munos, Jonathan Hunt, Tom Schaul, David Silver, and Hado van Hasselt. Successor Features for Transfer in Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), pages I 1-24, 2017.
[3] Diana Borsa, Andre Barreto, John Quan, Daniel Mankowitz, Remi Munos, Hado van Hasselt, David Silver, and Tom Schaul. Universal Successor Features Approximators. In ICLR, 2019.
[4] Devendra Singh Chaplot, Ruslan Salakhutdinov, Abhinav Gupta, and Saurabh Gupta. Neural topological slam for visual navigation. In CVPR, 2020.
[5] Tao Chen, Saurabh Gupta, and Abhinav Gupta. Learning exploration policies for navigation. In Proceedings of (ICLR) International Conference on Learning Representations, May 2019.
[6] Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environ- ment for openai gym. https: httpp////ggthhhb...cmamaiieeete wttpaaawwwiineemmmmiiiimieeeeeee
gym-minigrien 2018.
[7] Sumit Chopra, Raia Hadsell, and Yann Lecun. Learning a similarity metric discriminatively, with application to face verification. volume 1, pages 539- 546 vol. 1, 07 2005.
[8] Peter Dayan. Improving generalization for temporal difference learning: The successor repre- sentation. Neural Computation, 5(4):613-624, 1993.
[9] Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In Advances Neural Information Processing Systems, volume 32, 2019.
[10] Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal-conditioned policies. In Proceedings of (ICLR) International Conference on Learning Representations, May 2019.
[11] Zhiao Huang. Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching. In Advances in Neural Information Processing Systems (NeurIPS, pages 1940- 1950, 2019.
[12] L. Kaelbling. Learning to achieve goals. In IJCAI, 1993.
[13] Leslie Pack Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In In Proceedings of the Tenth International Conference on Machine Learning, pages 167-173. Morgan Kaufmann, 1993.
[14] Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations (ICLR), 2015.
[15] Tejas D. Kulkarni, Ardavan Sacedi, Simanta Gautam, and Samuel J. Gershman. Deep successor reinforcement learning, 2016
[16] Michael Laskin, Scott Emmons, Ajay Jain, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning, 2020.
[17] Andrew Levy, Robert Platt, and Kate Saenko. Hierarchical reinforcement learning with hindsight. In International Conference on Learning Representations, 2019.
[18] Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Repre- sentations, JCLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. 2016.
11

---

[19] Kara Liu, Thanard Kurutach, Christine Tung, P. Abbeel, and Aviv Tamar. Hallucinative topological memory for zero-shot visual planning. Proceedings of the 37th International Conference on Machine Learning, volume abs/2002. 2020.
[20] Marlos C Machado, Mare G Bellemare, and Michael Bowling. Count- Baate Exploration with the Successor Representation. 2018.
[21] Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption Discovery through the Deep Successor Representation. In ICLR, 2018.
[22] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 5 518(7540):5295333 February 2015.
[23] Andrew W. Moore, Leemon C. Baird, and Leslie Kaclbling. Multi-value-fuman functions: Efficient automatic action hierarchies for multiple goal mdps. In Proceedings of the 16th International Joint Conference on Artificial Intelligence Volume 2, IJ,AI'9,, page 1316-1321, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
[24] Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual reinforcement learning with imagined goals. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Pro- cessing Systems, volume 31. Curran Associates, Inc., 2018.
[25] Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal- conditioned policies. 2019.
[26] Vitchyr Pong, Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal difference models: Model-free deep RL for model-based control. ICLR, abs/1 802.09981 2018.
[27] Vitchyr H. Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering self-supervised reinforcement learning. ICML, abs/1903.03699 2020.
(28) Rahul Ramesh, Manan Tomar, and Balaraman Ravindran. Successor options: An option discov- ery framework for reinforcement learning. In Proceedings of the Twenty-Fighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 3304-3310. International Joint Conferences on Artificial Intelligence Organization, 7 2019.
[29] Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. In International Conference on Learning Representations (ICLR). 2018.
[30] Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Marc Pollefeys, Timothy Lillicrap, and Sylvain Gelly. Episodic curiosity through reachability. In International Conference on Learning Representations (ICLR), 2019.
[31] Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function ap- proximators. Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1312-1320, Lille, France, 07-09 Jul 2015. PMLR.
[32] Pierre Sermanet, Corey Lynch, Yevgen Chebotar, Eric Hsu, Jasmineand Jang, Stefan Schaal, and Sergey Levine. Time-contrastive networks: Self-supervised learning from video. Proceedings of International Conference in Robotics and Automation (ICRA).
[33] Adam Stooke and Pieter Abbeel. rlpyt: A research code base for deep reinforcement learning in pytorch. CoRR, htss/1999.01000 2019.
[34] Richard Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick Pilarski, Adam White, and Doina Precup. Horde: scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction categories and subject descriptors. volume 2, 01 2011.
12

---

[35] Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1):181
211, 1999.
[36] 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.
[37] Marek Wydmuch, Michal Kempka, and Wojeiech Jaškowski. Vizdoom competitions: Playing doom from pixels. IEEE Transactions on Games, 2018.
[38] Amy Zhang, Sainbayar Sukhbaatar, Adam Lerer, Arthur Szlam, and Rob Fergus. Composable planning with attributes. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5837-5844 5876. PMLR, 2018
[39] Jingwei Zhang. Niklas Wetzel, Nicolai Dorka, Joschka Boedecker, and Wolfram Burgard. Scheduled Intrinsic Drive: A Hierarchical Take on Intrinsically Motivated Exploration. 2019.
13


Reviews:
[{"review_id": "wb_VDIjQJwP", "reviewer": "Reviewer_YnN2", "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.   ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "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. \n\nOverall, 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. \n\n(1)\tIs 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))? \n\n(2)\tLine 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. \n\n(3)\tIn 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)? \n\n(4)\tIs 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. \n\n(5)\tExperiments on MultiRoom in Figure 5 are of high variance. It could be helpful to add more elaboration on this part to explain the variance.  \n\n(6)\tExploration 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.  \n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitation in Section 6 and social impact (both positive and negative) in Appendix H. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "sZRYPFIS7bw", "reviewer": "Reviewer_66Ma", "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. ", "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": "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:\n\n- 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. \n\n- (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. \n \nQuality: The overall quality of the work is quite high. The experiments are well executed and observations are nicely reported.\n\nClarity: The paper reads quite clearly overall. The flow of content is pretty nice as well.\n\nSignificance: 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.\n\nQuestions: 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nI do not think there any explicit negative societal impacts of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not think there any explicit ethical concerns raised by this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}, {"review_id": "cEcYofzCxR9", "reviewer": "Reviewer_RwVV", "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.", "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": "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.\n\nMy 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].\n\nAnother 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.\n\nLastly, 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.\n\n\n[1] Ghosh, Dibya, Abhishek Gupta, and Sergey Levine. \"Learning Actionable Representations with Goal Conditioned Policies.\" International Conference on Learning Representations. 2018.\n[2] Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer:\n350 Bridging planning and reinforcement learning. In Advances in Neural Information Processing Systems, volume 32, 2019.\n[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. \n[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\n[5] SPTM", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "YNVdgSuRD_Q", "reviewer": "Reviewer_V86Z", "summary": "Summary:\n=============================\nThis 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.\n\nOverall, this paper is well written, with methodology clearly explained and evaluation done in detail. So I recommend a clear acceptance.", "questions": "", "limitations": "", "rating": 8, "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": "Strength:\n=========================\nThe 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.\n\nMinor concerns:\n=========================\nHowever, here are some minor concerns, with the hope to help improve the paper:\n\n(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?\n\n(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?\n\n(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?\n\n(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.\n\nReference:\nBagaria, Akhil, Jason K. Senthil, and George Konidaris. \"Skill Discovery for Exploration and Planning using Deep Skill Graphs.\" International Conference on Machine Learning. PMLR, 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

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)