Successor Feature Landmarks for Long-Horizon Goal-Conditioned Reinforcement Learning
Year: 2021

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 landmarkbased 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 tasks1.

heading: 1 Introduction
text: Consider deploying a self-driving car to a new city. To be practical, the car should be able to explore the city such that it can learn to traverse from any starting location to any destination, since the destination may vary depending on the passenger. In the context of reinforcement learning (RL), this problem is known as goal-conditioned RL (GCRL) [12, 13]. Previous works [31, 1, 24, 26, 17] have tackled this problem by learning a goal-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 it is proficient for any state-goal pair it 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-based approaches to form plans consisting of lower temporal-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 landmark-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 of research focused on visual navigation tasks conducted planning over
1The demo video and code can be found at https://2016choang.github.io/sfl.
35th Conference on Neural Information Processing Systems (NeurIPS 2021)
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-horizon GCRL tasks and address the associated challenges in exploration. Our key idea is to use successor features (SF) [15, 2] — a 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 a goal-conditioned policy from SFS without any additional policy learning. Second, we leverage SFS to build a landmark-based graph representation of the environment; the agent adds observed states as landmarks based on their SFSpredicted novelty and forms edges between landmarks by using SFS as a distance estimate. SF as an abstraction of transition dynamics is a natural solution for building this graph when we consider the MDP as a directed graph of states (nodes) and transitions (edges) following [11]. 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 (long-horizon) 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 a 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 of a 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], a 2D gridworld, and ViZDoom [37], a visual 3D first-person view environment with large mazes. We observe that SFL outperforms state-of-the-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.

heading: 2 Related Work
text: 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) [11] 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 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 execute 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 to the output of a 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 a SF-based metric that acts as a 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 to locally move between nodes; our framework also falls under this paradigm of graph-based 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 on human demonstrations or 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 a 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-based 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; it 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 to decompose the Q-value function into SF and the reward which enables efficient policy transfer [2, 3] and to design transition-based intrinsic rewards [20, 39] for efficient exploration. SF has also been used in the options framework [35]; Eigenoptions [21] derived options from the eigendecomposition 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 a SF-based similarity metric to formulate a goal-conditioned policy, abstract the state space as a landmark graph for long-horizon 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.

heading: 3 Preliminaries

heading: 3.1 Goal-Conditioned RL
text: Goal-conditioned reinforcement learning (GCRL) tasks [12] are Markov Decision Processes (MDP) extended with a set of goals G and defined by a tuple (S,A,G,RG , T , ), where S is a state space, A an action set, RG : S ⇥A⇥ G ! R a goal-conditioned reward function, T the transition dynamics, and a discount factor. Following [11, 36], we focus on the setting where the goal space G 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-conditioned policy ⇡ : S ⇥ G ! A to maximize the expected cumulative reward, V ⇡g (s0) = E⇡[ P t
trt]; 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.
Algorithm 1 Training 1: Initialize: Graph G = (L,E), parameter ✓ of SFS⇡̄✓ , replay buffer D, hyperparameter Texp,
landmark transition count N l 2: while env not done do 3: lfront ⇠ Softmax( 1Count(L) ) {Choose frontier landmark via count-based sampling} 4: while lcurr 6= lfront do 5: ltarget PLAN(G, lcurr, lfront) {Plan path to frontier landmark} 6: ⌧traverse, lcurr Traverse(⇡l, ltarget) {Traverse to ltarget with ⇡l (Algorithm 3 in §H)} 7: G,N l Graph-Update(G, ⌧traverse, SFS⇡̄✓ , N l) {Update graph (Algorithm 2)} 8: end while 9: ⌧rand = {st, at, rt} Texp t ⇠ ⇡̄ {Explore with random policy for Texp steps} 10: G,N l Graph-Update(G, ⌧rand, SFS⇡̄✓ , N l) {Update graph (Algorithm 2)} 11: D D [ ⌧random 12: Update ✓ from TD error with mini-batches sampled from D {Update SF parameters} 13: end while

heading: 3.2 Successor Features
text: In the tabular setting, the successor representation (SR) [8, 15] is defined as the expected discounted occupancy of futures state s0 starting in state s and action a and acting under a policy ⇡:
M⇡(s, a, s 0) = E⇡ hP1 t0=t t0 tI(St0 = s0) St = s,At = a i (1)
The SR M(s, a) is then a concatenation of M(s, a, s0), 8s 2 S. We may view SR as a representation of state similarity extended over the time dimension, as described in [21]. In addition, we note that the SR is solely determined by ⇡ and the transition dynamics of the environment p(st+1|st, at). Successor features (SF) [2, 15] extend SR [8] to 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 s0 with feature vector s0 . The SF ⇡ of a state-action pair (s, a) is then defined as:
⇡(s, a) = E⇡ hP1
t0=t t0 t st0 St = s,At = a i
(2)
In addition, SF can be defined in terms of only the state, ⇡(s) = Ea⇠⇡(s)[ ⇡(s, a)]. SF allows decoupling the value function into the successor feature (dynamics-relevant information) with task (reward function): if we assume that the one-step reward of transition (s, a, s0) with feature (s, a, s0) can be written as r(s, a, s0) = (s, a, s0)>w, where w are learnable weights to fit the reward function, we can write the Q-value function as follows [2, 15]:
Q⇡(s, a) = E⇡ " 1X
t0=t
t 0 tr(St0 , At0 , St0+1) St = s,At = a #
= E⇡ " 1X
t0=t
t 0 t >t0w St = s,At = a # = ⇡(s, a)>w (3)
Consequently, the Q-value function separates into SF, which represents the policy-dependent transition dynamics, and the reward vector w for a particular task. Later in Section 4.3, we will extend this formulation to the goal-conditioned setting and discuss our choices for w.

heading: 4 Successor Feature Landmarks
text: 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, §4.1). We maintain a non-parametric graph of state “landmarks,” using SFS as a distance metric for determining which observed states to add as landmarks and how these landmarks should be connected (§4.2). To enable traversal between landmarks, we directly obtain a local goal-conditioned policy from SFS between current state and the given landmark (§4.3). With these components, we tackle the long-horizon setting by planning on the landmark graph and finding
the shortest path to the given goal, which decomposes the long-horizon problem into a 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 use 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 to the graph and follow the shortest path to it. Figure 1 illustrates the overarching framework and Figure 2 gives further detail into how the graph and SF are updated. Algorithm 1 describes the procedure used to train SFL.

heading: 4.1 Successor Feature Similarity
text: SFS, the foundation of our framework, is based on SF. For context, we estimate SF as the output of a deep neural network parameterized by ✓ : ⇡(s, a) ⇡ ⇡✓ ( (s), a), where is a feature embedding of state and ⇡ is a fixed policy which we choose to be a uniform random policy denoted as ⇡̄. We update ✓ 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 (s1, a1) and (s2, a2) in terms of similarity. One option is to compare s1 and s2 directly via some metric such as `2 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 ⇡ to be uniform random, i.e. ⇡̄, so that 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-occupancy of two state-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:
SFS⇡̄((s1, a1), (s2, a2))
= X
s02S E⇡̄
" 1X
t0=t
t 0 tI(St = s0) St = s1, At = a1
# ⇥ E⇡̄ " 1X
t0=t
t 0 tI(St = s0) St = s2, At = a2
#
= X
s02S M⇡̄(s1, a1, s
0)⇥M⇡̄(s2, a2, s0) = M⇡̄(s1, a1)>M⇡̄(s2, a2)
(4)
We can extend SFS to the high-dimensional case by encoding states in the feature space and replacing M⇡̄(s, a) with ⇡̄(s, a). The intuition remains the same, but we instead measure similarities in the feature space. In practice, we normalize ⇡(s, a) 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, we may define SFS between just two states by getting rid of the action
dimension in SF:
SFS⇡̄((s1, a1), (s2, a2)) = ⇡̄(s1, a1)> ⇡̄(s2, a2) (5)
SFS⇡̄(s1, s2) = ⇡̄(s1)> ⇡̄(s2) (6)

heading: 4.2 Landmark Graph
text: The landmark graph G serves as a compact representation of the state space and its transition dynamics. G is dynamically-populated in an online fashion as the agent explores more of its environment. Formally, landmark graph G = (L,E) is a tuple of landmarks L and edges E. The landmark set L = {l1, . . . , l|L|} is a set of states representing the explored part of the state-space. The edge set E is a matrix R|L|⇥|L|, where Ei,j = 1 if li and lj is connected, and 0 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 t, we compute the landmark closest to the agent under SFS metric: lcurr = argmaxl2L SFS
⇡̄(st, l). If SFS⇡̄(st, lcurr) < add, the add threshold, then we add st to the landmark set L. Otherwise, if SFS⇡̄(st, lcurr) > local, the localization threshold, then the agent is localized to lcurr. If the agent was previously localized to a different landmark lprev, then we increment the count of the landmark transition N l(lprev!lcurr) by 1 where N l 2 N|E| is the landmark transition count, which is used to form the graph edges. 2
Since we progressively build the landmark set, we 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.
Algorithm 2 Graph-Update (§4.2) input Graph G = (L,E), SFS⇡̄✓ , trajectory ⌧ ,
landmark transition count N l output updated graph G and N l
1: lprev ; {Previously localized landmark} 2: for s 2 ⌧ do 3: lcurr argmaxl2L SFS⇡̄✓ (s, l) {Localize} 4: if SFS⇡̄✓ (s, lcurr) < add then 5: L L [ s {Add landmark} 6: end if 7: if SFS⇡̄✓ (s, lcurr) > local then 8: if lprev 6= ; and lprev 6= lcurr then 9: N l(lprev!lcurr) N l (lprev!lcurr) + 1 {Record
landmark transition} 10: if N l(lprev!lcurr) > edge then 11: E E [ (lprev ! lcurr) {Form edge} 12: end if 13: end if 14: lprev lcurr 15: end if 16: end for 17: return G, N l
Edge Formation We form edge Ei,j if the number of the landmark transitions is larger than the edge threshold, i.e., N lli!lj > edge, with weight Wi,j = exp( (N lli!lj )). We apply filtering improvements to E in ViZDoom to mitigate the perceptual aliasing problem where faraway states can appear visually similar due to repeated use of textures. See Appendix D for more details.

heading: 4.3 Local Goal-Conditioned Policy
text: We want to learn a local goal-conditioned policy ⇡l : S ⇥ G ! A to reach or transition between landmarks. To accomplish this, ⇡l should maximize the expected return V (s, g) = E[ P1 t=0
tr(st, at, g)], where r(s, a, g) is a reward function that captures how close s (or more precisely s, a) is to the goal g in terms of feature similarity:
r(s, a, g) = (s, a)> ⇡̄(g), (7)
where ⇡̄ is the SF with respect to the random policy ⇡̄. Recall that we can decouple the Q-value function into the SF representation and reward weights w as shown in 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 w be ⇡̄(g), we can
2Zhang et al. [38] proposed a 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-value function Q⇡̄(s, a, g) for the goal-conditioned policy ⇡(a|s, g) being equal to the SFS between s and g:
Q⇡̄(s, a, g) = ⇡̄(s, a)> ⇡̄(g) = SFS⇡̄(s, a, g). (8)
The goal-conditioned policy is derived by sampling actions from the goal-conditioned Q-value function in a 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 is beyond the scope of this work and is left for future work.

heading: 4.4 Planning
text: Given the landmark graph G, we can plan the shortest-path from the landmark closest to the agent lcurr to a final target landmark ltarget by selecting a sequence of landmarks [l0, l1, . . . , lk] in the graph G with minimal weight (see §4.2) sum along the path, where l0 = lcurr, lk = ltarget, and k is the length of the plan. In training, we use frontier landmarks lfront which have been visited less frequently as ltarget. In evaluation, the given goal state is added to the graph and set as ltarget. See Algorithm 1 for an overview of how planning is used to select the agent’s low-level policy in training.

heading: 4.5 Exploration
text: We sample frontier landmarks lfront proportional to the inverse of their visitation count (i.e., with count-based exploration). We use two policies: a local policy ⇡l for traversing between landmarks and a random policy ⇡̄ for exploring around a frontier landmark. Given a target frontier landmark lfront, we construct a plan [l0, l1, . . . , lfront]. When the agent is localized to landmark li, the policy at time t is defined as ⇡l(a|st; li+1). When the agent is localized to a landmark that is not included in the current plan [l0, l1, . . . , lfront], then it re-plans a new path to lfront. Such failure cases of 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 lfront is reached or until the step-limit Nfront 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 ⌧ ⇠ ⇡̄ is added to the random transition buffer. SF ⇡̄✓ is updated with batch samples from this buffer.
The random policy is only used to explore local neighborhoods at 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 in a relatively efficient manner. Our experiments on large ViZDoom maps demonstrate that this strategy is sufficient for learning a SF representation that ultimately outperforms baseline methods on goal-reaching tasks.

heading: 5 Experiments
text: 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-horizon goals when the agent’s start state is randomized across episodes. Afterwards, we consider how SFL performs when efficient exploration is required to reach distant areas by using a setting where the agent’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 largescale of the maps and reuse of similar textures make it particularly difficult to learn distance metrics from the first-person observations. This is due to perceptual aliasing, where visually similar images can be geographically far apart. We use mazes from SPTM in our experiments, with one example shown in Figure 3 [29].
MiniGrid is a 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.
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 us to study how well the landmark graph supports traversal between arbitrary 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. 2. Fixed spawn: In training, the agent is spawned at a fixed start state sstart with no given goal. This enables us to study how well the agent can explore the map given a limited step budget per episode. In evaluation, the agent is again spawned at sstart 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.

heading: 5.2 Baseline Methods for Comparison
text: Random spawn experiments. We compare SFL against baselines used in SGM, as described below. For each difficulty, we measure the average success rate over 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 to learn long-horizon policies and the benefits of planning to create high-level paths that the controller can follow. 3. SPTM [29]: planning module with a reachability network to learn a 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 a recent landmark-based approach for long-horizon navigation.
Fixed spawn experiments. In the fixed spawn setting, we compare SFL against Mapping State Space (MSS) [11], a UVFA and landmark-based approach for exploration and long-horizon goalconditioned RL, as well as SPTM and SGM. Again, we measure the average success rate over 5 random seeds. We adapt the published code3 to work on 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 a 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.

heading: 5.3 Implementation Details
text: SFL is implemented with the rlpyt codebase [33]. For experiments in ViZDoom, we use the pretrained ResNet-18 backbone from SPTM as a fixed feature encoder which is similarly used across all baselines. For MiniGrid, we train a 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 as dissimilar representations. We then approximate SF with a fully-connected neural network, using these encoded features as input. See Appendix C for more details on feature learning, edge formation, and hyperparameters.

heading: 5.4 Results
text: Random Spawn Results. As shown in Table 1, our method outperforms the other baselines on 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 a 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 114K 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.
3https://github.com/FangchenLiu/map_planner
Fixed Spawn Results. We see in Table 2 that SFL reaches significantly higher success rates than the baselines across all difficulty levels, especially on 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 to capture geodesic distance in ViZDoom’s highdimensional state space with first-person views. The UVFA in MSS has to solve the difficult task of approximating the number of steps between two states, which we conjecture requires a larger sample complexity and more learning capacity. In contrast, we only use SFS to relatively compare states, i.e. is SFS of state A higher than SFS of state B with respect to 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 of 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 environments, where SFL (red) overall outperforms MSS (green). States in MiniGrid encode top-down views of the map with distinct 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 as obstacles and the limited time budget per episode.

heading: 5.5 SFS Visualization
text: 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 a reference state and a set 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 to 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 be localized to the reference state, i.e. states with SFS > local. 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-conditioned policy, in Appendix E.

heading: 6 Conclusion
text: In this paper, we presented Successor Feature Landmarks, a graph-based planning framework that leverages a 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 the agent’s starting position. Our work empirically showed that SF can be used to make robust decisions about environment dynamics, and we 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 on a good feature embedding to be learned. We foresee that our method can be extended by augmenting with an algorithm for learning robust feature embeddings to facilitate SF learning.

heading: Acknowledgements
text: 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 an NSF Fellowship under Grant No. DGE1418060. 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] baseline.

Review summaries:
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. 

Summary: ============================= This paper aims to solve the long-term goal-conditioned planning problem by tackling strategies to explore state-goal pairs. The proposed methods improve the exploration performance by formulating successor features as landmark graphs and in exploration, use three key steps: (1) select the frontier graph node; (2) use a random policy to explore; (3) extend the landmark graph by a successor feature similarity metric.  Overall, this paper is well written, with methodology clearly explained and evaluation done in detail. So I recommend a clear acceptance.

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.   

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.