Title: Plan2Vec: Unsupervised Representation Learning by Latent Plans

Abstract: Creating a useful representation of the world takes more than just rote memorization of individual data samples. This is because fundamentally, we use our internal representation to plan and solve problems. In this paper, we introduce Plan2Vec, an unsupervised representation learning objective inspired by graph-planning algorithms and value-based reinforcement techniques. By abstracting away low-level control with a learned local metric, we show that it is possible to learn representations that inform long-range structures, entirely passively from high-dimensional sequential datasets that assume no access to action data or an expert policy. Plan2vec learns a latent space through value iteration on the graph formed by the data points, connected via a local metric function trained contrastively from context. We show that the global metric on this learned embedding can be used to plan with O(1) complexity by linear interpolation. This exponential speedup is critical for planning with a learned representation on any problem containing non-trivial global topology. We demonstrate the effectiveness of Plan2Vec on simulated as well as two real-world image datasets, showing that Plan2Vec can effectively acquire representations that carry long-range structure to accelerate planning. Additional results and videos can be found at https://sites.google.com/view/plan2vec.

1. Introduction:

Unsupervised representation learning is often motivated by the goal of reducing human involvement in the learning loop, such that an algorithm can learn directly from streams of unlabeled data. Much focus has been placed on an algorithm's transfer performance across supervised learning tasks. However, for control tasks, where an agent is planning on the learned representation space, performance is often poor (Watter et al., 2015) . A quick glance at the representation learned by a variational auto-encoder (VAE) reveals that the learned embedding often contains local patches that are quite reasonable by themselves, but the global structure of the learned embedding is often "crumpled", such that Euclidean lines between points that are sufficiently far-apart either cross domain-boundaries, or otherwise detach from the support of the learned manifold (see Fig. 4 ). This observation implies that although the VAE objective encourages embeddings that behave well locally, memorizing individual image samples by reconstruction is insufficient to attain meaningful global structure. This raises an interesting and important question: if rote memorization is insufficient, what else do we need in order to build an agent that can make good plans?

Various works in learning representations for planning attempt to address this issue by learning locally constrained generative models (Banijamali et al., 2017; Watter et al., 2015; Kurutach et al., 2018) . One line of work, motivated by controlling complex dynamic systems directly from high-dimensional input, attempts to learn generative models that explicitly impose a reduced local linearity constraint on the learned dynamic manifold (Watter et al., 2015; Banijamali et al., 2017) . Such methods contain three major shortcomings. First, some of these formulations rely on learning a forward model, which can not be applied to datasets where action data is unavailable or ill-defined. Second, these generative models rely heavily on the inductive prior within image generation, that images nearby in pixel space are semantically similar, which limits the applicability of these methods to domains where visual similarities map well to the conceptual space. Finally, the linear constraint and the optimization objective are both local, yet making plans involves non-local concepts of distances and direction. How to learn from streams of observation data to attain a cognitive map of the problem domain without relying on the image similarity priors provided by generative models remains an open problem.

In this work, we pose the problem of unsupervised learning a plannable representation as learning a map of the domain without access to the underlying sampling process and the environment. Such a map has two main properties: First, the map informs conceptual distance between any pair of observations, beyond the typical limit of a short spatiotemporal window (Perozzi et al., 2014; Caron et al., 2018) . Second, this map has to be consistent with a local metric1 , which is easily attained via self-supervision. Motivated by this problem, we propose Plan2Vec, a method for unsupervised representation learning that incorporates planning as part of the learning objective. The technical challenges of this work are threefold: First, the standard formulation of reinforcement learning requires substantial human supervision in the form of meticulously shaped, dense rewards. Different tasks usually require different reward functions, making it difficult to scale across multiple tasks. The second issue is that reinforcement learning is active, as it requires access to an environment between optimization phases to receive trajectories in order to learn. Third, to plan on a continuous state and action space, one usually needs to learn a closed-form behavior policy that outputs actions, or a forward model of the environment with actions as an input.

The main contributions of this paper is to overcome all three of these problems by formulating the problem of learning the global structure of a data manifold as a goal-directed reinforcement learning task. To solve the issue of offering a reward, we train a local metric function from local context without supervision, and use it as a sparse reward for reaching the goal with hind-sight relabeling. To address the necessity of active RL and extending RL to a passive setting, we remove the need for either action data, or a model of the world, by planning entirely in the latent configuration space on a graph. Goal-directed planning can be done with a 1-step greedy policy in the learned representation space. We call our method Plan2Vec, for learning an embedding space for planning.

To help illustrate our method, we lead the introduction of Plan2Vec with a set of toy tasks on simulated navigation domains, and show visualization of the components and learned manifold. We then evaluate Plan2Vec under two challenging task settings: First, we show that we can learn representations on deformable objects such as a piece of rope, which is otherwise hard to model. Moreover, we show qualitative results on visual plans between pairs of rope configurations that are randomly selected from the dataset. Second, we tackle real-world navigation on StreetLearn (Mirowski et al., 2018) , where we learn to embed a map directly from videos of a car driving through the streets, with no access to the ground-truth GPS location data. We show quantitatively that under a constrained planning computation budget, the embedding that Plan2Vec learns using a globally consistent planning objective outperforms baselines that only plan with the local metric.

2. Related Works:

The work most similar to ours from the manifold learning community is DeepWalk (Perozzi et al., 2014) . DeepWalk aims to embed a social graph by randomly sampling trajectories, then use skip-gram (Mikolov et al., 2013) to embed each graph node contrastively from its contrast. This is related to the contrastive learning objective we use to train our local metric function. Despite of this, the random walk DeepWalk employs to sample those trajectories is limited in terms of distance of travel. As a result it falls under the category of representation learning algorithms that only learn from a localized context. Similarly there is a strong connection between our value-iteration learning objective and the diffusion map literature. In diffusion map, the distance on the learned manifold measures the "diffusion distance" between two points on a graph G under a markovian transition kernel (Socher & Hein, 2008) . One can consider value-iteration as a non-parametric version of diffusion map using neural networks for the kernel. A critical difference is that the transition kernel in diffusion maps is not condition on a goal whereas the policy does. As a consequence, the diffusion distance fall-off exponentially as the number of steps increases, just like with DeepWalk. Locally linear embeddings (LLE) could be considered a "stronger" version of skip-gram, where linear contributions of each neighbor is preserved. However, LLE enforces global structure, and prevent volume collapse via addition of a global volume regularization term. This is similar to the variational prior in a variational auto-encoder (VAE) in that both lack meaningful alignment with planning semantics. Recent work in "robust features" point to a connection between the injected noise and the alignment between the input and output manifoldsIlyas et al. ( 2019) that might be an interesting direction to explore.

Other works look at planning over a graph with various assumptions (Savinov et al., 2018; Zhang et al., 2018; Eysenbach et al., 2019) . With semi-parametric topological memory (SPTM) Savinov et al. (2018) the focus is on solving navigation instead of learning a vector embedding. All of these methods use Dijkstra's shortest path first (SPF) search (Dijkstra, 1959) on the graph to plan, resulting in a worst case bound of O(|E| + |V | log |V |) in computation time where |E| is the number of edges on the graph and |V | the number of vertices. In our experiment, we show quantitatively that the local embedding SPTM uses to make plans is insufficient if the hard-coded planner has a restricted planning budget, whereas the globally consistent representation that Plan2Vec learns via value iteration still plans well. Our result illustrates the importance for an agent to acquire such a global view of the domain and use it as heuristic for planning.

There are also gradient-based planning methods that require expert trajectories, which is a strong assumption that we do not require. Universal Planning Networks and Distributional Planning Networks (Srinivas et al., 2018; Yu et al., 2019) rely on supervised learning to get to the reward through a differentiable forward model, trained end-to-end by grounding through expert actions. Gupta et al. (2019) ; Tamar et al. (2016) assume that the feature vectors live on a 2D grid world with known environment dynamics and well-defined local connectivity between states.

There have also been Laplacian methods to learn representations efficient for planning (Wu et al., 2019) , using a spectral graph objective for approximating the Laplacian eigenfunctions and using L2 distance in this space as a dense reward for goal-directed tasks. This learns a similar type of space that is a compression of the original graph, but assumes the original graph is fully given through acting in the environment as opposed to a disjoint set of trajectories which are connected via a learned local metric.

Embed to control (E2C), RCE, L-SBMP and causal InfoGAN (Watter et al., 2015; Banijamali et al., 2017; Ichter & Pavone, 2018; Kurutach et al., 2018) are a line of generative model that explicitly incorporate forward modeling in the latent space. They show that the learned representation is plannable, without directly incorporating a planner as part of their learning objective. Our goal is drastically different -Plan2Vec learns a representation by planning, as opposed to just showing one can plan with a learned representation. Plan2Vec explicitly acquires the concept of "reachability" conditioned on an optimal policy as part of the representation. This results in a semantically meaningful and locally consistent global structure.

Another branch of work coming from the reinforcement learning community are selfsupervised or task-agnostic RL (Florensa et al., 2019; Kahn et al., 2017; Pong et al., 2019) . These work aim to reduce the amount of human involvement in designing reinforcement learning algorithms for individual tasks. Plan2Vec is distinguished from these proposals in that we do not aim to learn a policy distribution π(a|o). Instead, we want to learn generalizable representations of the environments that makes learning such a low-level policy, or running classical control algorithms more efficient. By abstracting away the actions, Plan2Vec is able to plan over much longer horizons, as demonstrated in Sec. 5.

3. Technical Background:

We now overview methods that learn a local metric between pairs of images that are closeby, and proximal dynamic programming under a standard Markov decision process (MDP) formalism (Sutton & Barto, 1998) .

Learning a Local Metric. Intuitively, a metric is a bivariate function that gives a measure of similarity between two points. Formally, f a,b∼D : (a, b) → R + is a symmetric, real-valued, and positive-definite function over its domain D × D. When distance labels are available one can learn such a function via supervised learning. In reality, however, we often need to work with sequential datasets without access to a sampling policy that is jointly optimized, in which case one cannot assume long-horizon optimality in the sequences we want to learn from. As a result, the distance information between frames of observations is only good up to a limited temporal window, beyond which noise dominates.

In language modeling and unsupervised representation learning domains, it is often easy to construct positive and negative examples, and pose a binary classification objective as a Noise-Contrastive Density Estimator (NCE) (Gutmann & Hyvärinen, 2010) ,

EQUATION

)

where f is a convex function proportional to the density p(x, c). Minimizing the NCE loss can be mapped to maximizing a lower-bound on the mutual information between the latent code c and the data distribution X (Oord et al., 2018; Hjelm et al., 2018) ,

I(X, c) = E [ log P (X|C) P (X) ] ≥ log(N ) -L NCE .

(2)

Rather than directly learning a representation this way (Sermanet et al., 2017) , Plan2Vec extends the standard binary NCE objective to learn a local metric function, and uses it as a reward function.

Universal Value Function Approximator as a Metric. We formulate value iteration under the Markov decision process (MDP) formalism (Bellman, 1957) . The MDP is parameterized by the tuple ⟨S, A, P, r⟩. S and A are the sets of states and actions, P (s ′ |s, a) is the transition model of the environment, and r(s, a, s ′ ) is the reward function. An agent is represented by its policy distribution π(a|s). The state value function V π : S → R represents the expected sum of discounted future rewards for being at state s, conditioned on the reward r and the policy π. In sample-based value iteration with neural networks, we can learn the value function by minimizing the empirical Bellman-residual

EQUATION

where the Bellman optimality operator is defined as

EQUATION

)

Universal Value Function Approximators (UVFAs) (Schaul et al., 2015) extend this taskspecific reward to learn a "universal" value function by generalizing to all goals g ∈ S.

The reward now conditions on the goal r(s, a, s ′ , g). Assuming that the goals are uniformly sampled from S and the value function is symmetric, UVFA becomes a metric on S up to a correction constant. If we further assume that the MDP is deterministic, the sample-based Bellman residual can be reduced to

EQUATION

which we use to learn our latent space, as detailed in Sec. 4.2.

4 Learning Representations by Latent Planning minimize ∥f ϕ (x, x * ) -y * ∥2 for x, x ±,I , y ±,I 7: end for In many representation learning problems, one has access only to noisy binary or categorical learning signals.

It is often easy to find symmetry transformations in a particular problem that make it trivial to define a binary or ordered categorical relationship between data-points. In skipgrams (Mikolov et al., 2013; Jozefowicz et al., 2016) the classifier decides whether a word belongs to a certain context. In time-contrastive networks (Sermanet et al., 2017) classifiers decide whether two views correspond to the same scene. In our case, we extend this dichotomy to one of {identical, close, or far-apart}. Formally this can be considered as a natural extension of the standard definition of a metric from the positive real-line to a directed set where each element in the set corresponds to one of the categories. To reflect the order between the category labels, we use a regression objective. The labels are designated 0 for identity, k/K for true neighbors that are k steps apart if k ≤ K, and 2 for negative samples for other trajectory or the same trajectory but more thank K steps apart. Alg. 1 explains the procedure in detail. Fig. 3 illustrates the well-behaved distribution of local distance scores for one of our experimental domains. Visualization of pairs show new transitions that are not present in the training trajectories.

4.2. Extrapolating Local Metric to A Globally Consistent Embedding By Planning:

To extrapolate the local metric information to a globally consistent embedding that can speed up planning, we first connect those disjoint trajectories in the dataset using the new connections found by the trained local metric function f ϕ (see Alg. 1 and Fig. 3c ). One can use this graph defined by f ϕ to perform planning at inference time with a path finding algorithm. Instead, we can move this computation to training time to achieve fast inference by learning a representation that distills shortest path information from this graph. Our goal is to learn an embedding on which there exists a metric that correctly reflects the difference in reachability between points in the neighborhood of the current observation, and the goal. Now formulated as an reinforcement learning problem, this is equivalent to learning a goal-conditioned value function V Φ (s, g) := ∥Φ(s) -Φ(g)∥ p at state s towards the goal g, where in practice we take p = 2. Hence, the value function is defined as the Euclidean distance between the two states in the learned embedding space. Similarly, the local metric f becomes the cost to travel the distance between state s and the next step s ′ . The action set A(s) for the agent consists of a flexible number 1-step neighbors, sourced from the local metric function f ϕ for each node s in the graph. As a reminder, f ϕ is a regression function that outputs a score designating "closeness" between a pair of states x, x ′ . In practice, we select a subset x ′ ∈ X where

f ϕ (x, x ′ ) ∈ N (1, ϵ) := [1 -ϵ, 1 + ϵ]

with tuned hyperparameter ϵ and X is the set of all states from the dataset. Choosing small ϵ leads to shorter steps between states and longer paths, and vice versa. We have now created a reinforcement learning task and can learn this value function with multi-step value iteration using transitions sampled from the graph (see Alg. 2). To improve rate of learning, we use hindsight experience re-labeling (Andrychowicz et al., 2017) to insert positive reaching examples.

5. Experimental Evaluation:

In this section, we experimentally answer the following questions: 1) Can we build a graph from sequential datasets using a contrastively trained local metric? 2) Can we extrapolate this local metric to a global embedding, and make planning easier? 3) Would Plan2Vec work in domains other than navigation, and learn features that are not visually apparent? To answer these questions, we show quantitative results on simulated 2D navigation. Then we extend Plan2Vec to the challenging deformable object manipulation tasks. Finally, we show that Plan2Vec can learn non-visual features of the domain where other methods perform poorly, on a real-world large-scale street view dataset. Our first domain is a room with a continuous, 2dimensional state space. A camera looks down on a square arena with a robot (blue block). The trajectory data consist of top-down images of the arena. We use ground-truth coordinates for evaluation only. Our experiment covers three room layouts with increasing level of difficulty: an open room, a room with a table in the middle, and a room with a wall separating it into two corridors that resembles a C-shaped maze (see Fig. 2 ).

5.1. Simulated Navigation:

Connecting The Dots by Generalization. We first investigate if the contrastively trained local metric function generalizes. To train the local metric contrastively on this domain, we restrict K = 1, such that only observations that are 1-step away are considered neighbors. The local metric predicts a distance score that is between 0 and 2, where 0 corresponds to identical observations, 1 to neighbors, and 2 to observations that are further apart. Fig. 3a shows the distribution of the score against ground-truth distance. In short ranges, the learned model is able to recover the local metric but saturates as distances increase. The score is well-behaved enough that it is easy to pick suitable values for the neighbor threshold (indicated by the ceiling of the red points). We plot new transitions found by the local metric against those in the dataset (blue). Fig. 3b visualizes the sampled trajectories (in blue, of length 4), whereas Fig. 3c shows the new ones found by the learned local metric function. 1 shows the success rates on the 2D navigation domains when the planning horizon is limited to a single step in the future. Under this regime, SPTM fails to succeed most of the time. This is because the local similarity function used in the parametric memory does not contain long-range information about the domain, and hence is insufficient as a planning heuristic for a memoryless planner. The VAE learned embedding does better on the Open Room domain, but falls short on more complex room arrangements. In comparison, the representation learned by Plan2Vec succeeds most of the time. To investigate this further, we visualize the learned global embedding for VAE versus that of Plan2Vec (Fig. 4 ). With the Open Room, Plan2Vec learns a latent space that looks flat. With Table and C-Maze, two points that are close in Euclidean space but separated by the wall appear far away in the learned latent space, reflecting the reduced reachability in between. For latent space higher dimension than 3, we can directly visualize the value function as shown in Fig. 5 .

We also include comparison to full SPTM, and find that Plan2Vec performs better at varying planning lengths, compare sample complexity with DQN (Mnih et al., 2015) using the local metric as a reward function, and computation time for planning of Dijkstra's and Plan2Vec to empirically validate the asymptotic bounds given in Section 4.2, all shown in Figure 6 . These are all run on state space of the Open Room domain.

5.2. Manipulation of Deformable Objects:

While we have made strides in controlling rigid bodies with reinforcement learning, manipulating deformable objects still remains an open problem. Methods so far rely on learning a generative model over the image sample (Kurutach et al., 2018) . To learn a plannable representation in a purely discriminative manner we now apply our method to the rope dataset (Wang et al., 2018) . The rope dataset is composed of 18 independent trajectories with 14k images total. Each image is a gray scale photo of a piece of rope wrapped around two pegs that are fixed on the table surface. The two pegs help define distinct topology for the configuration of the rope that needs to be respected for reasonable transitions. The challenge with the rope dataset is that it does not have a well-defined low-dimensional configuration space, making it difficult to design quantitative evaluation metrics. To get around this issue, we evaluate our method with planning on single trajectories, where the original sequences of observation can be used as qualitative baselines. We do find that our local metric generates a connected graph over all 18 trajectories, therefore there exists a viable plan from any image o s to any goal image o g . The difficulty of the planning problem varies with the connectivity of the graph, which is in turn dictated by the threshold set on local metric ϕ. 8 shows the distribution of neighbors for a set threshold T = 1.1, with both in and out-trajectory neighbors. This highlights the difficulty of the rope manipulation task and learning a latent representation that reflects a sparse connectivity graph. Fig. 9 shows an example of a plan generated by Plan2Vec for a given start and goal state, where we can see that each transition only perturbs the configuration of the rope locally.

5.3. Beyond Visual Similarity: Real-world Navigation:

To answer the question of whether Plan2Vec is able to learn nonvisual features of the domain, we evaluate on a visual navigation task using the real world dataset StreetLearn (Mirowski et al., 2018) . In comparison to the previous two tasks, the StreetLearn dataset offers an interesting alternative because the spatial re- lationship between views at different locations is not visually apparent. One can not easily tell that Union Square is to the north of Washington Square Park from street views alone. Yet a city resident knows exactly which general direction to turn to. This is in stark contrast to both the Room domain and the rope domain, where visual similarity is easily mapped to being close in the configuration space. We quantitatively evaluate the planning performance of Plan2Vec versus the VAE baseline in Table 2 using generated datasets (Fig. 7 ). This result shows that the planning performance of VAE on the StreetLearn dataset is barely above that of a random baseline. This is a common short-coming with unsupervised models that rely on the inductive prior of the generator to learn. Plan2Vec, on the other hand, uses planning as a general framework to extend any type of local and semantically meaningful signal to a consistent global embedding. We interpret these results by hypothesizing that Plan2Vec is successful in learning non-visual concepts of reachability (in this case an idea of the map), whereas VAE only clusters the images by visual similarity. In Table 2 , we also include comparisons with SPTM, where the agent is only allowed to plan 1-step ahead. This computation-constrained regime is interesting because a good planning heuristic is critical for good search performance. The result shows that in this regime, Plan2Vec performs well above SPTM, which backs our intuition that a good representation can and should alleviate some of the computational cost of planning at test time.

Formally, Plan2Vec's 1-step greedy planning is O(1) at test time, whereas SPTM is O(E) where E is the size of the graph. This also shows that Plan2Vec memorizes information that is computationally more valuable. Lastly, we observe that Plan2Vec generalizes -despite the agent never having seen a particular combination of starts and goals in the original dataset -by successfully navigating using the values acquired during training time as evidenced by the large jump in performance compared to other methods in Table 2 .

6. Conclusion:

We have presented an approach to attain a globally consistent representation from streams of observation data in a purely unsupervised fashion without generating images. Integral to our approach is the incorporation of planning as part of our learning objective, to enforce the semantic notion of reachability between any pair of images on the learned embedding. This differs our approach from previous work in learning plannable representations -in that the plannability is a consequence of the planning objective, instead of local linearity constrains.

In addition, we realize that formulating unsupervised learning as a reinforcement learning problem has the added benefit of allowing one to insert arbitrary local information about the domain as the reward R(s, s ′ ), and the explicit including of a maximizing inner step.

:

This can be relaxed into a pseudo metric, allowing different images to have zero conceptual distances in-between. This does not affect the applicability of our approach.

Figures and Tables:

Figure 1: Example of a path (black dashed arrow) found across independent trajectories (colored lines) from an initial state (gray circle) to a goal state (blue square), with learned local metric creating new connections.

Noise-Contrastive Learning the Local Metric Algorithm 1 Contrastive Local Metric Learning Require: set of observation sequences {τ = x [0:T ] } 1: Initialize f ϕ 2: Sample xt and x I = xt, y I = 0 3: Sample xt, x + t+1 where xt, xt+1 ∈ τi, y + = 1 4: Sample xt, x -where x -∼ τj, xt / ∈ τj, y -= 2 5: for each epoch do 6:

Figure 2: Simulated 2D navigation environments. We use these domains to illustrate the various properties of our method. left: Open, middle: Table, right: C-Maze. The blue block is the agent, and the red circle indicates the desired goal.

Figure 3: (1) Local metric score in comparison to ground-truth L 2 distance with predicted neighbors in red. (2) Trajectories given in the dataset. (3) Points from different trajectories are connected by generalizing the local-metric function. Out-of-training-set Connections shown in red. (4) Step sequence in C-Maze, learned via Plan2Vec. Gray dashed circle is the goal position. Red dot is the planned next step (1-step), greedy w.r.t the global metric function being learned. Blue dots are the neighbors sampled using the local metric function. Gray dot indicates the current and past positions of the agent. Sequence shows the agent getting around the wall in C-Maze. (5) Learned value function for a goal location on the bottom left corner (white dashed circle). Blue color is further away, red is close.

Figure 4: Learned Embedding with VAE (top row) vs Plan2Vec (bottom row). The columns correspond to the Open Room, Table, and C-Maze domains. Representation learned by the VAE is wrapped globally. Whereas Plan2Vec learns a globally coherent embedding. In C-Maze, the two ends of the tunnel are further apart, correctly reflecting the decrease in reachability between those points.

Figure 5: (left and middle) Difference in learned global metric on Open Room and C-Maze. The goal used to query the value map is indicated by the dashed circle. (right) shows the agent getting around the wall with the learned embedding (blue), whereas a Euclidean planner gets stuck.

Figure 6: Left: Comparison of Plan2Vec with full SPTM and a random baseline for varying plan lengths. Center: Comparison of Plan2Vec with DQN in terms of sample efficiency. Right: Comparison of computation time of Plan2Vec and Dijkstra's.

Figure 7: A visualization of the three datasets Tiny, Small, and Medium used in our experiments.

Fig.8shows the distribution of neighbors for a set threshold T = 1.1, with both in and out-trajectory neighbors. This highlights the difficulty of the rope manipulation task and learning a latent representation that reflects a sparse connectivity graph. Fig.9shows an example of a plan generated by Plan2Vec for a given start and goal state, where we can see that each transition only perturbs the configuration of the rope locally.

Figure 8: Histogram of number of neighbors per node, with visualized examples. Original nodes are left of the red dashed line and out of trajectory neighbors are outlined in orange.

Our goal is to learn a representation that goes beyond rote memorization of the dataset, which consists of disjoint temporal sequences. Critically, we want the structure of the embedding to capture the global topology of the dataset, such that for any observation o in the domain, we can make useful inference with respect to another sample o goal , no matter how far away o goal is. Having access to such a global metric, ∀ o, o goal pairs, would enable effective planning on non-trivial, high-dimensional, and/or complex topologies that are otherwise prohibitively slow. In this section we give a high-level overview of Plan2Vec, with implementation details available in Appendix ??. We first define local connectivity between states through a local metric function trained in a self-supervised manner with a contrastive loss. Different fromWatter et al. (2015);Banijamali et al. (2017) and similar toKurutach et al. (2018), our method does not rely on dynamics of the underlying environment in the form of sampled action data, and neither do we learned a forward model, which distracts from long-range planning. Instead, this task occurs on a graph where disjoint temporal sequences are connected by the local metric function. We learn a representation space that encodes paths on the graph such that a 1-step greedy policy on the learned representation is equivalent to a path finding algorithm on the graph.

Table content: <table><tr><td>a path (black</td></tr><tr><td>dashed arrow) found across indepen-</td></tr><tr><td>dent trajectories (colored lines) from</td></tr><tr><td>an initial state (gray circle) to a goal</td></tr><tr><td>state (blue square), with learned lo-</td></tr><tr><td>cal metric creating new connections.</td></tr></table>

Planning Performance on 2D Navigation

Table content: <table><tr><td>Accelerating</td><td>Planning</td><td>with</td><td>a</td><td/></tr><tr><td colspan="4">Learned Cognitive Map. To evaluate Plan2vec, we compare with SPTM (Savi-</td><td>State Input</td><td>Open Room</td><td>Table</td><td>C-Maze</td></tr><tr><td colspan="4">nov et al., 2018) and VAE (Kingma &amp; Welling, 2013) learned representations</td><td>Euclidean Plan2vec (L2) Plan2vec (pseudo)</td><td>100.0 ± 0.0 100.0 ± 0.0 96.9 ± 0.5</td><td>96.3 ± 1.4 96.6 ± 0.9 96.7 ± 2.0</td><td>88.7 ± 3.6 86.0 ± 4.1 83.1 ± 3.0</td></tr><tr><td colspan="4">under a restricted planning budget. Table</td><td>Image Input Plan2vec (L2)</td><td>90.0 ± 2.0</td><td>76.4 ± 9.2 80.2 ± 6.3</td></tr><tr><td/><td/><td/><td/><td>SPTM (1-step)</td><td>39.7 ± 6.1</td><td>23.7 ± 6.1</td><td>31.4 ± 6.5</td></tr><tr><td/><td/><td/><td/><td>VAE</td><td>73.9 ± 4.3</td><td>30.2 ± 6.5</td><td>52.7 ± 5.8</td></tr><tr><td/><td/><td/><td/><td>Random</td><td>3.2 ± 2.5</td><td>3.5 ± 2.5</td><td>4.7 ± 2.8</td></tr></table>

1-step Planning Performance on StreetLearn. Numbers are percentage of success for reaching goals that are within 50 steps of the starting point. Full Graph Search methods succeed 100% of the time.

Table content: <table><tr><td/><td colspan="3">Success Rate (%)</td></tr><tr><td>StreetLearn</td><td>Tiny</td><td>Small</td><td>Medium</td></tr><tr><td colspan="4">Plan2vec (Ours) 92.2 ± 2.9 57.2 ± 4.3 51.4 ± 6.9</td></tr><tr><td>SPTM (1-step)</td><td>31.5 ± 5.8</td><td>19.3 ± 5.8</td><td>20.2 ± 5.2</td></tr><tr><td>VAE</td><td>25.5 ± 5.6</td><td>14.4 ± 4.8</td><td>16.9 ± 5.5</td></tr><tr><td>Random</td><td>19.9 ± 5.4</td><td>12.0 ± 5.2</td><td>12.7 ± 4.6</td></tr></table>

Peer review (iclr2020):
## Paper Summary While cast slightly differently in the intro, it seems to me that this paper learns a goal-conditioned value function that is used at test time to construct visual plans by selecting an appropriate sequence of data points from the training data. Similar to prior work they learn a local distance metric without supervision using a temporal proximity objective and then construct a graph of the training data points using this metric. The main novelty that this paper introduces seems to be the idea to distill the results of planning algorithms run at training time into a global, goal-conditioned value function, which allows to reduce the required planning time at test time. The authors perform experiments on constructing visual plans for a simulated toy navigation task, a robotic rope manipulation task and the StreetLearn navigation task. The paper reports favorable results under a time-constrained test setting but does not include strong baselines that were designed for this setting. ## Strengths - bootstrapping a learned local distance metric to a global distance metric to reduce test-time planning cost is an interesting problem - the paper has nice visualizations / analysis on the toy dataset - the learning procedure for the local distance metric is clearly described - the paper uses a large variety of different visualizations to make concepts and results clearer ## Weaknesses (1) missing links to related work: the author*s treatment of related work does not address the connections to some relevant papers (e.g. [1-3]) or is only done in the appendix (especially for [4]). It is not clearly delineated between techniques and ideas that are introduced in other papers (see (2) below) and the novel parts of this work. This makes it hard to understand the actual contributions of this paper. (2) only minor contribution: the core parts of this paper build heavily on prior work: time-contrastive objectives for distance learning have been introduced in [5] and also been used in a very similar setup as here in [4], further [4, 3] also use semi-parametric, graph-like representations for planning with a learned local distance metric. The major contribution seems to be to distill the plans derived with either (a) n-step greedy rollout or (b) Dijkstra graph-search into a value-function so that planning does not need to be performed at test time. This somewhat small contribution is in contrast to the claims from the introduction that this paper *pose[s] the problem of unsupervised learning a plannable representation as learning a cognitive map of the domain*. (3) comparison to weak baselines: the main comparison in the experimental section is to a version of [4] where the authors constrain the planning horizon to a single step, which means effectively greedily using the local metric from Sec. 3.1. To be clear: this is in no way the method of [4]: they use Dijkstra-based planning at test time and it is clear that a *version* of [4] that does not use planning is not able to work. To me this seems rather like an ablation of the proposed method than a real baseline. The baseline that plans greedily with embeddings based on visual similarity has even less hope of working. The paper lacks thorough comparison to (a) baselines with the same semi-parametric structure that perform planning at test time (like the real method of [4]) and (b) methods that generate reactive policies without constructing a semi-parametric memory (e.g. off-policy RL). Only then a thorough comparison of pros and cons of planning at training/test time is possible (see detailed suggestions below). (4) lack of qualitative samples for generated plans: for both the rope and the StreetLearn domain the authors do not provide thorough evaluation. For the rope domain only a single qualitative rollout is shown, for the StreetLearn domain no qualitative samples are provided for either the proposed method or the comparisons. (see suggestions for further evaluation below) (5) explanation of core algorithmic part unclear: the explanation of how the local metric is used to learn the global value function is somewhat unclear and the used notation is confusing. Key problems seem to be the double-introduction of symbols for the local metric in Alg. 2 and the confusing usage of the terms *global embedding* and *value function* (see detailed questions below) (6) terms used / writing structure makes paper hard to follow: the connection between used concepts like *global embedding*, *plannable representation* and *goal-conditioned value function* are not clear in the writing of the paper. The authors talk about concepts without introducing them clearly before (e.g. problems of RL are listed in the intro without any prior reference to RL). (7) lacks detail for reproducing results: the paper does not provide sufficient detail for reproducing the results. Neither in the main paper nor in the appendix do the authors provide details regarding architecture and used hyperparameters. It is unclear what policy was used to collect the training data, it is unclear how the baselines are working in detail (e.g. how the 1-step planning works) and how produced plans are checked for their validity. ## Questions (A) What policy is used to collect the training data on each environment? (B) What is the relation between the *global embedding* Phi and the *goal-conditioned value function* V_Phi(x, x_prime) in Algorithm 2? (C) What is the difference between the local metric function phi and the reward function in Algorithm 2? Are they the same? (D) If they are the same, how can the local metric accurately estimate rewards for states x and x_g that are far apart from one another as would naturally be the case when training the value function? (E) What does the notation N(1, eps) in line 5 of Algorithm 2 mean? (F) What is the expectation over the length of trajectories between start and goal on the StreetLearn environment (to estimate what percentage of that the success horizon of 50 steps is)? ## Suggestions to improve the paper (for 1) please add a more thorough treatment of the closest related works on semi-parametric memory + learned visual planning + learned distance functions (some mentioned below [1-5]) to the main part of the paper, clearly stating differences and carving out which parts are similar and where actual novelty lies. (for 2) please explain clearly the added value of distilling the training-plans into a value function for O(1) test-time planning and point out that this is the main difference e.g. to [4] and therefore the main contribution of the paper. (for 3) in order to better understand the trade-offs between doing planning at test time (like [3,4]) or learning an O(1) planner contrast runtime and performance of both options (i.e. compare to the proper method of [4]). This will help readers understand how much speed they gain from the proposed method vs how much performance they loose. It might also make sense to include an off-policy RL algorithm (e.g. SAC) that uses the local metric as reward function (without constructing the graph) to investigate how much planning via graph-search can help at training time. Another interesting direction can be to investigate the generalization performance to a new environment (e.g. new street maze, new rope setup) after training on a variety of environment configurations. [3] showed that explicit test-time planning performs better than *pure* RL, it would be interesting how the proposed *hybrid* approach performs. (for 4) please add randomly sampled qualitative results for both environments and all methods to the appendix. It can additionally be helpful to add GIFs of executions to a website. It might also be interesting to add a quantitative evaluation for the plans from the rope environment as was performed in Kurutach et al. 2018. (for 5) please incorporate answers to questions (B-E) into the text in Sec 3.2 explaining Algorithm 2. It might also help to structure the text in such a way as to follow the flow of the algorithm. (for 6) restructure and shorten the introduction, clarify terms like *inductive prior within image generation* or *non-local concepts of distances and direction* or *conceptual reward* or *planning network*, clarify how the authors connect the proposed representation learning objective and RL. Avoid sentences that are a highly compressed summary of the paper but for which the reader lacks background, like in the intro: *training a planning agent to master an imagined “reaching game” on a graph*. (for 7) add details for architecture and hyperparameters to the appendix, add details for how baselines are constructed to the appendix. add details about data collection and evaluation for all datasets to the appendix (e.g. how is checked that a plan is coherent in StreetLearn). It might also help to add an algorithm box for the test time procedure for the proposed method. ## Minor Edit Suggestions - Fig 2 seems to define the blue square as the target, the text next to it describes the blue square as the agent, please make coherent - for Fig 7: the numbers contained in the figure are not explained in the caption, especially the numbers below the images are cryptic, please explain or omit [Novelty]: minor [technical novelty]: minor [Experimental Design]: Okay [potential impact]: minor ################ [overall recommendation]: weakReject - The exposition of the problem and treatment of related work are not sufficient, the actual novelty of the proposed paper is low and the lack of comparison to strong baselines push this paper below the bar for acceptance. [Confidence]: High [1] Cognitive Planning and Mapping, Gupta et al., 2017 [2] Universal Planning Networks, Srinivas et al., 2018 [3] Search on the Replay Buffer: Bridging Planning and Reinforcement Learning, Eysenbach et al., 2019 [4] Semi-Parametric Topological Memory for Navigation, Savinov et al., 2018 [5] Time-Contrastive Networks, Sermanet et al., 2017 ### Post-rebuttal reply ### I appreciate the author*s reply, the experiments that were added during the rebuttal are definitely a good step forward. The authors added comparison to a model-free RL baseline as well as proper comparison to a multi-step planning version of SPTM. However, these comparisons were only performed on the most simple environment: the open room environment without any obstacle. These evaluations are not sufficient to prove the merit of the proposed method, especially given that it is sold as an alternative to planning methods. The method needs to be tested against fair baselines on more complicated environments; the current submission only contains baselines that *cannot* work on the more complicated tasks. I therefore don*t see grounds to improve my rating.