Plan2Vec: Unsupervised Representation Learning by Latent Plans
Authors: Ge Yang
Amy Zhang
Ari Morcos
Joelle Pineau
Pieter Abbeel
Roberto Calandra
Venue:  (2020)
Keywords: Unsupervised Learning
Reinforcement Learning
Manifold Learning

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, to solve problems, and to navigate the world. For a representation to be amenable to planning, it is critical for it to embody some notion of optimality. A representation learning objective that explicitly considers some form of planning should generate representations which are more computationally valuable than those that memorize samples. In this paper, we introduce \textbf{Plan2Vec}, an unsupervised representation learning objective inspired by value-based reinforcement learning methods. By abstracting away low-level control with a learned local metric, we show that it is possible to learn plannable representations that inform long-range structures, entirely passively from high-dimensional sequential datasets without supervision. A latent space is learned by playing an ``Imagined Planning Game" on the graph formed by the data points, using 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 speed-up is critical for planning with a learned representation on any problem containing non-trivial global topology. We demonstrate the effectiveness of Plan2Vec on simulated toy tasks from both proprioceptive and image states, as well as two real-world image datasets, showing that Plan2Vec can effectively plan using learned representations. Additional results and videos can be found at \url{https://sites.google.com/view/plan2vec}.

Under review as a conference paper at ICLR 2020
PLAN2VEC: UNSUPERVISED REPRESENTATION LEARNING BY LATENT PLANS
Anonymous authors Paper under double-blind review
A ABSTRACT
Creating 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, introduce Plan2 unsupervised representation learning objective inspired by graph-planning algorithms and based reinforcement tech- niques. 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 la- tent space through value iteration on the graph formed by the data points, connected via local metric function trained contrastively from context. We show that the global metric on this learned embedding can be used plan with O(1) complexity by linear interpolation. This exponential speed- up 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 Plan2 Vec can effectively acquire representations that carry long-range structure to accelrratc planning. Additional results and vidcos can be found at https://sites. gow.sllleesggooleeee...ooo hoom/view/plan2vee
INTRODUCTION
Unsupervised representation learning is often motivated by the goal of reducing human in- volvement 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 's transfer performance across supervised lcarning tasks. However, for control tasks, where an agent is planning on the learned representation space, performance is often poor (Watter al. 20F). A quick glance at the representation learned by a variational aulo-encoder (VAE) reveals that the learned embedding often contains local patches that quite reasonable by themselves, but the global structure of the learned embedding is often "crumpled", such that Euclidean lines otherwisg
between points that are sufficiently far-apart either cross Nomain-boundaries detach from the support of the learned manifold (see Fig. 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 struc- ture. This raises an interesting and important question: if rote memorization is insufficient, what elsc 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,, p0n, Watter et all, 20m Kurntach ef all, 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 all 2018; [Banjamali et aL. 2017). Such methods contain three major shortcomings. First, some of those formulations rely on learning a forward model, which can not be applied to ill-defined. Second, these generative models rely heavily on the inductive prior within image generation, that images nearby in pixel space semantically similar, which limits the applicability of these methods to domains
datasets where action data is unavailable

---

Under review as a conference paper at ICLR 2020
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 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 enviromment. Such a map has two main properties: First, the map informs conceptual dis- tance between any pair of observations, beyond the typical limit of a short spatiotemporal window (Peroozi et all, 2me, Caron et al 2mT)) Second, this map has to be consistent with a local metric"; which easily attained via self=supervision. Motivated by this problem, we propose Plan2Vec, a method for unsupervised representation learning that incorpo- rates planning as part of the learning objective. The technical challenges of this work are threefold: First, the standard formulation of reinforcement learning requires substantial hu- man 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 inntun 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 formu- lating 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 as sparse reward for reaching the goal with hind-sight relabeling. To address the necessity of active RL and extending RL to 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 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, tackle real-world navigation on StreetLearn @Uirowskiet.al 2018), where we learn to embed a map directly from videos of car driving through the streets, with no access the ground-trute 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.
RELATED WORKS
The work most similar to ours from the manifold learning community is DeepWalk (Perozzi all, 2014). DeepWalk aims to embed a social graph by randomly sampling trajectories, then use skip-gred gram (Mikoloy et all, 2 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 Walk employs to sample those trajectorics is limitod in terms of distance of travel. As a result it falls undor 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 graph & under a markovian transition kernel (Socher Hein, 2008). One can consider value-iteration as non-parametric version of diffusion
'This can be relaxed into pseudo metric, allowing different images to have zero conceptual distances in-between. This does not affect the applicability of our approach.
2

---

Under review as a conference paper at ICLR 2020
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 mumber of steps increases, just like with WeepWalk. 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 variational auto-encoder (VAE) in that both lack mcaningful alignment with planning scmantics. Recent work in "robust fcatures" point to a connection between the injected noise and the alignment between the input and outpul manifolds[Ivas et al. (20119 that might be interesting direction to explore.
Other works look at planning over a graph with various assumptions (Savinov et all, 2018 Zhang et all, 2018; EEsenbach et all, 20TH). With semi-parametric topological memory (SPTM) Savinov of all (2018) the focus on solving navigation instead of learning a vector embedding, All of these methods use Dijkstra's s shortest path first (SPF) search (Diikstra [45%] on the graph to plan, resulting in a worst case bound of O([E] + |o|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 lo make plans is insufficient. if the hard-coded planner has 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 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 strong assumption that we do not require. Universal Planning Networks and Distributional Planning Networks (Srinivas et all, 201& all 2019) rely on supervised learning to get to the reward through a differentiable forward model, trained end-to-end by grounding through expert actions. Gupla el al. (2019); [amar et all (20лG) 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 (WW el all 2013), using a spectral graph objective for approximating the Laplacian eigenfunc- tions and using L2 distance in this space as 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 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 of all 2015; Bane jamali et all 2017 lchter & Pavond, 20& Kurnttach of all 201) 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 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 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 self- supervised or task-agnostic RL (Elorensa all 201; Kahn-eiall elall, 2017; [Pnng el all, 2019). These work aim to reduce the amount of hurman vement in designing reinforcement learning algorithms for individual tasks. Plan2Vec is distinguished from these proposals in that do not aim to learn policy distribution (alo). Instead, we want to learn gen- eralizable representations of the environments that makes learning such a low-level policy, or running classical control algorithms more efficient. By abstracting away the actions, Plan2Ved Vec is able to plan over much longer horizons, as demonstrated in Sec. E.
3

---

Under review as a conference paper at ICLR 2020
3 TECHNICAL BACKGROUND
We now overview methods that learn local metric between pairs of images that are close- by, and proximal dynamic programming under a standard Markov decision process (MDP) formalism (Sutton Bartd, 1998).
Learning a Local Metric. Intuitively, a metric is a bivariate function that gives a mea- sure of similarity between two points. Formally, fabnD (a. b) - R+ is symmetric, real-valued, and positive-defnite function over its domain D x D. When distance labels are available one can learn such a function via supervised learning. Tn 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 result, the distance information between frames of obscrvations 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 Noise-Contrastivg Density Estimator (NCE) (Gutmaan Hyvärinen, 2010),
f(In,c)
LNCF = -llog Σx M
(1)
where f is a convex function proportional to the density p(x, c). Minimizing the NCE loss can be mapped to maximizing a fower-bound on the mutual information between the latent code and the data distribution X (Oord el al, 2018 Hjelm el all, 2018).
P(XIC) P(X)
I(X, c) = log
2 log(N) - LNCE
(2)
Rather than directly learning a representation this way (Sermanet et all, 2017), Plan2Vec extends the standard binary NCE objective learn a local metric function, and uses it as a reward function.
Universal Value Function Approximator as Metric. We formulate value iteration under the Markov decision process (MDP) formalism (Bellmar [amn). The MDP is param- eterized by the tuple (S, A, P,r). S and A are the sets of states and actions, P(s'[s, [s, a) the transition model of the environment, and r(s, a') is the reward function. An agent is represented by its policy distribution (a(s). The state value function V S - IR repre- sents 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
8 = Vs: 0) V],,
(3)
where the Bellman optimality operator defined as
B
= max ag
R(st, at, 8t41) + Σ P(s41118, (
(4)
Universal Value Function Approximators (UVFAs) (Schanl of all 2016) extend this task- specific reward to learn "universal" value function by generalizing to all goals E S. The reward now conditions on the goal r(s,a, (,,,a, Assuming that the goals are uniformly sampled from S and the value function is symmetric, UVFA becomes metric S up to correction constant. If we further assume that the MDP is deterministic, the sample- based Bellman residual can be reduced to
V(s, 0) + r(s, a, a' 9) + +VV(s's .):
(5)
which to learn our latent space, detailed in Sec. 1.2.
4 LEARNING REPRESENTATIONS BY LATENT PLANNING
4

---

Under review as a conference paper at ICLR 2020
Our goal is to learn representation that goes be- yond rote memorization of the dataset, which con- sists of disjoint temporal sequences. Critically, we want, the structure of the embedding to capture the global topology of the dataset, such that for any ob- servation o in the domain, we can make useful infer- another sample Ogoal, no mat- ter how far away Ogoal is. Having access to such a global metric, Yo, Ogoal 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 be- tween states through a local metric function trained in self-supervised manner with contrastive loss. Different from Watler el all (2111) [anijamali et al. (20TT) and similar to Kurntach
ence with respect
......***.
Figure 1: Example of a path (black dashed arrow) found across indepen- dent trajectories (colored lines) from initial state (gray circle) to a goal state (blue square), with learned lo- cal metric creating new connections.
all (2UTS)) 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 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.
4.1 HOISE-CONTRASTIE LEARNING THE LOCAL METRIC
In many representation learning prob- lems, one has access only to noisy bi- nary or categorical learning signals.
Algorithm 1 Contrastive Local Metric Learning
Require:
set observation sequences {T = x(0:r] 1: Initialize fe
It is often easy to find symmetry transformations in a particular prob-
2: Sample z; and 21 It, y²=
3: Sample æt, x where æe, 21-1 E Ts y
lem that make it trivial to define binary or ordered categorical relation- ship between data-points. In skip-
4: Sample zz, x where x' ~ Ty 2t $ T₁ y
5: for each epoch do
6: minimize [=(,)²") - y²lla for xt e.t
grams (Mikollo et all, 2013; Nozelows
7: end for
icz alla 2016) the classifier decides
whether word belongs to a certain context. In time-contrastive networks (Sermanct et all 201) 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 consid- ered as a natural extension of the standard definition of metrie from the positive real-line to 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 K for true neighbors that are k steps apart if h K, and 2 for negative samples for other trajectory or the same trajectory but more thank steps apart. Alg. M explains the procedure in detail. Fig. Y 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 globally consistent embedding that can speed up planning, we first connect those disjoint trajectories in the dataset us- ing the new connections found by the trained local metric function fo (see Alg. and Fig. Bc). One can use this graph defined by fo to perform planning at infer- ence time with a path finding algorithm. However, this takes O(EE) + V log [V] time (Fredman & Tarjan, [لо]) where [E] is the number of edges and [V] is the number of vertices in the graph. This quickly becomes intractable for large graphs.
5

---

Under review as a conference paper at ICLR 2020
Instead, we move this compu- tation to training time to achieve fast inference by learning repre- sentation 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 obser- vation, and the goal. Now formu- lated as reinforcement learning
Algorithm Unsupervised Learning by Latent Plans
Require: planning horizon H
Require: set of observation sequences {T mp.r)) Require: local metric function o(z, R Require: reward function r(z, 2g) -- (2,
Initialize global embedding 4(x) = R
2: repeat
3:
start and goul repeat (h=0, h++}
sample æo, 2g
5:
find set n {x' s.t. o( x') E N(1,)))
6:
find x arg ainginn olx, ((x,)gg)
7:
compute r(x" ;gg)
problem, this is equivalent to learn- ing goal-conditioned value fune- tion (s, == (s) ((g)lpp pp at state towards the goal 9, where in practice we take 2. Hence, the
8:
add (a, Fg) to buffer B
9:
until r or
10:
Sample (x, x', [g) from B
11:
(2, + Vo(e', (x)),, where (z( (xx) (rr))lp
minimize
the value function is defined 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 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 fo for each node in the graph. As a reminder, fs is regression function that outputs a score designating "closeness" between pair of states x,2', In practice, select subset x' E X where c] with tuned hyperparameter and
12:
until convergence
fo(xxx') E c(1,,) == [1 -1-c, 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 2017) to insert positive reaching examples.
the set all
EXPERIMENTAL EVALUATION
In this section, we experimentally answer the following questions: 1) Can we build graph from sequential datasets using a contrastively trained local metric? 2) Can we extrapolate this local metric to global embedding, and make planning casier? 3) Would Plan2Vec work in domains other than navigation, and learn features that are not visually apparent? To answer these questions, extend Plan2Vec to the challenging deformable object manipulation tasks. Finally, we show that Plan2Vec can learn non-visus features of the domain where other methods perform poorly, on a real-world large-scale street view dataset.
show quantilative results on simulated 2D navigation. Then
5.1 SIMULATED NAVIGATION
Our first domain is room with continuous, 2- dimensional state space. A camera looks down on a square arena with robot (blue block). The trajectory data consist of top-down im- ages of the arena. We use ground-truth coordi- nates for evaluation only. Our experiment cov- three room layouts with increasing level of difficulty: an open room, room with a table in the middle, and room with wall separating into two corridors that resembles a C-shaped maze (see Fig. D
Figure 2: Simulated 2D navigation envi- romments. We use these domains to illus- trate the various properties of our method. left: Open, middle: Table, right: C-Maze. The blue block the agent, and the red circle indicates the desired goal.
Connecting The Dots by Generalization. We first investigate if the contrastively trained local metric function generalizes. To train the local metric contrastively this

---

Under review as a conference paper at ICLR 2020
6.0 005
<i
Ground
Figure 3: (1) Local metric score in comparison to ground-truth L2 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-sot 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 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.
(left and middle) Difference in learned global metric Open Room and C-Maze. The goal used to query the value map is in- dicated by the dashed cir- clc. (right) shows the agent Figure Learned Embedding with VAE (top row) vs getling around the wall with Plan2Vec (bottom row). The columns correspond to the the learned embedding (blue), Open Room, Table, and C-Maze domains. Representation whereas Fuclidean planner learned by the VAE is wrapped globally. Whereas Plan2Vec gets stuck. learns a globally coherent embedding. C-Maze, the two ends of the tunnel are further apart, correctly reflecting the decrease reachability between those points.
Figure 5:
D2-
60
domain, restrict K = 1, such that only observations that are 1-step away considered neighbors. The local metric predicts a distance score that is between 0 and 2, where corresponds to identical observations, 1 to neighbors, and to observations that further apart. Fig. &a 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 distances increase. The score is well-behaved enough that it is casy 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. Tb visualizes the sampled trajectories (in blue, of length 4), whereas Fig. Be shows the new ones found by the learned local metric function.
Accelerating Planning with Learned Cognitive Map. To evaluate
Table 1: Planning Performance 2D Navigation
Plan2vec, we compare with SPTM (Savi
State Input
Open Room
Table
C-Mase
nov ct all 2018) and VAE (Kingma. &
Buelidean
100.0 + 0.0
96.3 + 1.4
88.7 +: 3.6
Plan2ve: (L22
100.0 + 0.0
96.6 + 0.9
86.0 +
Welling 2013 learned representations under
Plau2vec (pseudo)
96.9 0.5
96.7 2.0
83.1 3.0
restricted planning budget.
Image Input
Table M 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
Plan2vec (L2)
90.0 2.0
76.4 9.2
80.2 : 6.3
SPTM (1-step) VAE
39.7 6.1
6.1
31.4
73.9
30.2 6.5
52.7
Random
3.2 +: 2.5
3.5 + 2.5
4.7 + 2.8
7

---

Under review as a conference paper at ICLR 2020
Plenning Success
Sample Compledty
Planring Cood vs Planning Daprh
1029
14:00
di-trs partve
Buecaa fee
75%
Plar 9PTM random
RarSiv DOV
6096
00%
2314
0%
100
1000
Planring Stapa
Planiing
Comparison of Plan2Vec with full SPTM and random baseline for varying plan lengths. Center: Comparison of Plau2Vec with DQN in terms of sample elficiency. Right: Comparison of computation time of Plan2Vec and Dijkstra's. 's
Figure 6: Left:
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, that of Vean2Vec (Fig, B)). 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. G.
visualize the learned global embedding for VAE versus
We also include comparison to full SPTM, and find that Plan2Vec performs better at varying planning lengths, compare sample complexity with DQN (Mnih et all, 20E) using the local metric as a reward function, and computation time for planning of Dijkstra's 's and Plan2Vec to empirically validate the asymptotic bounds given in Section 222, all shown in Figure F. 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, manip- ulating deformable objects still remains an open problem. Methods so far rely on learning a generative model over the image sample (Kurrtach et all, 2018). To learn a plannable representation in a purely discriminative manner we now apply our method to the rope dataset (Wang et all 2018). The rope dataset is composed of 18 independent trajectorics with 14k images total. Each image is gray scale photo of 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 din-dimeniional con- figuration space, making it difficult to design quantitative evaluation metrics. To get around this issuc, we evaluate our method with planning on single trajectorics, where the original so- quences of obscrvation can be used as qualitative basclines. 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, any goal image Og- The difficully of the planning problem varies with the connectivity of the graph, which is in turn dictated by the threshold set on local metric ø. Fig. shows the distribution of neighbors for set threshold T 1.1, with both in and out- out-trajectory neighbors. This highlights the difficulty of the rope manipulation task and learning a latent representation that reflects sparse connectivity graph. Fig. g shows an example of 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 Plau2Vec is able to learn non- visual features of the domain, we evaluate on a visual navigation task using the real world dataset StreetLearn (Wirrowski et all 201). In comparison to the previous two tasks, the Street dataset offers an interesting alternative because the spatial re-
Figure 7: A visualization the three datasets Tiny, Small, and Medium used in our experiments.
8

---

Under review as a conference paper at ICLR 2020
Neighbor sets
1400
1463
bear
1200
Number of nodes
1000
VALESIS
800
600
400
200
50
100
150
200
250
300
Number of neighbors
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.
8:748
trajaa7332
traj.8.720
3.36
traj
traj.32259
traj:33358
Summary of Plan (4255, 1417)
0.46
Query Image
Visual Plans
Goal Image
Figure 9: Example of visual plan generated by Plan2Vec on the Rope Domain showing steps coming from two different trajectories (8 and 3). Each transition only perturbs the configuration the rope locally. The numbers above denote the trajectory and time step the image is from, the number below represents the score by the local metric fa-
lationship between views at different locations is not visually apparent. One can not easily tell that Union Square is to the north Washington Square Park from street views alone. Yet a city resident knows exactly which general dircction to turn to. This is in stark contrast to both the Room domain and the rope domain, where visual similarity is casily mapped to being close in the configuration space. We quantitatively evaluate the planning performance of Plan2Vec versus the VAE baseline in Table @ using generated datasets (Fig. M). This result shows that the planning performance of VAE on the StreetLearn dataset is barely above that of random base- line. This is 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 scmantically meaningful signal to consistent global embedding. We interpret these results by hypothesizing that Plan2Vec 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 B we also include compar- isons with SPTM, where the agent is only allowed to plan 1-step ahead. regime
Table 2: 1-step Planning Performance on StreetLearn. Numbers are percentage of success for reaching goals that are within 50 steps the starting point. Full Graph Search methods succeed 100% of the time.
This computation-constrainni is interesting because good planning heuristic is critical for good search per- formance. The result shows that in this regime, Plan2Vec: performs well above SPTM, which backs our intu- ition that a good representation can and should alleviate some of the compu- tational cost of planning at test time.
Success Rate (%)
StreetLearn
Tiny
Small
Medium
Plan2vec (Ours)
92.2 = 2.9
57.2 = 4.3
51.4 + 6.9
SPTM (1-step)
31.5 5.8
1.8
20.2 5,2
VAE Random
25.5 5.6
14.4
16.9 5.5
19.9+5.4
+.20
12.7 4.6
Formally, Plan2Vec's 1-step greedy planning is O()) at test time, whereas SPTM is O(E)
where E is the size of the graph. This also shows that Plan2Vec memorizes information that computationally more valuable. Lastly, we observe that Plan2Vec generalizes - despite the agent never having seen 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 Z.
9

---

Under review as a conference paper at ICLR 2020
6 CONCLUSION
We have presented an approach attain a globally consistent representation from streams of observation data in purely unsupervised fashion without generating images. Integral to our approach the incorporation of planning as part of our learning objective, to enforce the semantic notion of roachability between any pair of images on the learned embedding. This that the
differs our approach from previous work in learning plannable representations 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, 8'), and the explicit including of maximizing inner step.
REFERENCES
Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welin- der, Bob McGrew, Josh Tobin, OpenAT Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, pp. 5048 5058, 2017.
Ershad Banijamali, Rui Shu, Mohammad Ghavamzadch, Hung Bui, and Ali Ghodsi. Robust locally-linear controllable embedding. arXiv preprint Xiv:::177 100::710.00 05373, 2017.
Richard Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, pp. 679-684, 1957.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. arXiv preprint vrXii:1807.055222 3, 2018.
Edsger W Dijkstra. A note two problems in connexion with graphs. Numerische mathe- mabik, 1(1):269 271, 1959.
Benjamin Eysenbach, Ruslan Salakhutdinor, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. ArXiv, abs/ 190..09956, 2019.
Carlos Florensa, Jonas Degrave, Nicolas Heess, Jost Tobias Springenberg, and Martin A. Riedmiller. Self-supervised learning of image embedding for continuous control. CoRR, abs/ bbss/191.00044,, 2019. URL http::/aarai ha/pivxxivvvvoo.. http//abb/91110009431
Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596 615, July 1987. ISSN 0004-5411. doi: 11.1145/2 2144/28869 (8869.288744 URL http://doi.... acm. org/ 10. 1145/ 28869/ 28874.
Saurabh Gupta, Varun Tolani, James Davidson, Sergey Levine, Rahul Sukthankar, and Jitendra Malik. Cognitive mapping and planning for visual navigation. International Journal of Computer Vision, Oct 2019.
Michael Gutmann and Aapo Hyvärinen. Nonte-contrestive estimation: new estimation principle for unnormalized statistical modcls. In Proceedings of the Thirteenth Interna- tional Conference on Artificial Intelligence and Statistics, pp. 297-304, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchillon, Karan Grewal, Adain Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint XrXi::1808.00 06670, 2018.
Brian Ichter and Marco Pavone. Robot motion planning in learned latent spaces. arXiv preprint arxiv:1877. 10000701366, 2018.
10

---

Under review as a conference paper at ICLR 2020
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry, Adversarial examples are not bugs, they are features. arXiv preprint arXio:1905.021 00..0000.2155. 75, 2019.
Rafal Jozefowicz, Oriol Vinyals, Mike Schuster, Noam Shazecr, and Yonghui Wu. Exploring 2016.
the limits of language modeling. Xiv preprint
Gregory Kahn, Adam Villaflor, Bosen Ding, Pieter Abbeel, and Sergey Levine. Self- supervised deep reinforcement learning with generalized computation graphs for robot navigation. CoRR,, abs/ 1049, 2017. URL http://arxiy: http:///axxivv..g/bbbbs/s// htwgg/bbb//0// 10049
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 1312. 6114,, 2013.
Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart Russell, and Pieter Abbeel. Learn- ing plannable representations with causal infogan. In Advances in Neural Informalion Processing Systems, pp. 8747-8758, 2018.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. ar preprint arXiv:1301.3781, 2013.
Piotr Mirowski, Matthew Koichi Grimes, Mateusz Malinowski, Karl Moritz Hermann, Keith Anderson, Denis Teplyashin, Karen Simonyan, Koray Kavukcuoglu, Andrew Zisserman, and Raia Hadsell. Learning to navigate in citics without map. In Neural Information Processing Systems (NeurIPS), 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Ku- maran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540)::59-533 February 2013. ISSN 00280836. URL.
org/10.. 1ttp://1..03///attrreee 1038//attre1422233
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint ar arXi::1807.0374 2018.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Vitchyr H. Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering self-supervised veinforcement. learning. CoRR, hts/19933006998, 2019. URL http:://aaxt..orrr/a///100000
03698.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. arXiv preprint ar Xiv: 110: 803. 000.00 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International Conference on Machine Learning, pp. 1312-1320, 2015.
Pierre Sermanet, Corey Lynch, Yevgen Chebotar, Jasmine Hsu, Eric Jang, Stefan Schaal, and Sergey Levine. Time-contrastive networks: Self-supervised learning from pixels. 2017.
Richard Socher and Matthias Hein. Manifold learning and dimensionality reduction with diffusion maps. In Seminar report, Saarland University, 2008
Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal planning networks: Learning generalizable representations for visuomotor control. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4732 4741, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Richard S. Sutton and Andrew G. Barto. Introduction to Reinforcement Learning. MIT Press, Cambridge, MA, USA, 1st edition, 1998. ISBN 0262193981.
11

---

Under review as a conference paper at ICLR 2020
Aviv Tamar, YI WU, Garrett Thomas, Sergey Levine, and Picter Abbeel. Value iteration networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 2164-2162. Curran Associates, Inc., 2016.
Angelina Wang, Thanard Kurutach, Aviv Tamar, and Pieter Abbeel. Learning robotic manipulation through visual planning and acting. In Deep RL Workshop at NeurIPS, 2018.
Manuel Watter, Jost Springenberg, Joschka Boedecker, and Martin Riedmiller. Embed to control: A locally linear latent dynamics model for control from raw images. In Advances in newral information processing systems, pp. 1746-2754, 2015.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in RL: Learning represcntations with efficient approximations. In International Conference on Learning Represenlations, 2019. URL
Tianhe Yu, Glcb Shevchuk, Dorsa Sadigh, and Chelsca Finn. Unsupervised visuomotor control through distributional planning networks. CoRR, abs/1902.05542,, 2019. URL 05542.
Amy Zhang, Sainbayar Sukhbaatar, Adam Lerer, Arthur Szlam, and Rob Fergus. Com- posable planning with attributes. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 5837 5846, 2018. URL http://proceeding...kk wwwps/v80///appee whaggg/000.aa.kk. html.
12

---

Under review as a conference paper at ICLR 2020
APPENDIX
A IMPLEMENTATION DETAILS
A.1 ARCHITECTURE AND PARAMETER TUNING
In our experience, found that it is substantially easier to learn the local metric function, versus the global metric. This reflected in the network architecture that is needed for the network to converge. For the local metrie function, typically achieve high-90% testing accuracy on the fixed dataset. For the global metric function, we conduct architecture search with supervised training. Results averaged over 3 seeds that are not hand-picked.
A.1.1 SIMULATED NAVIGATION WITH PROPRIOCEPTIVE INPUTS
The local metric function simple 4-layer perceptron. To learn the local metric, we run 20 environment simulation in parallel, collect 50 rollouts each (1000 in total). Each rollout has 10 timesteps. We then generate data pairs that are 1-step apart. We use a mini batch size of 32, and learning rate of 3 x 10-4, The rest of the Adam optimizer hyper parameters are stock ones from Torch.
LocalMetric(
(embed) : Linear featureet,,,,, out_ fut_featuree=50, bias=True)
(head) Sequential
(0): Linear fen_feetuure=1000, out_ fet_features=50, bias=True)
(1): ReLU()
(2) : Linear (in_features=50, out out_features=500 bias=True)
(3) ReLU()
(4): Linear(in (in_feeeuures500, out fee_ffeuure==00, bias=True)
(5): ReLU()
(6) Linear (in_feature==50, out let_feature==1, bias=True)
)
In order for the global metric function to converge on the same dataset, it needs to be wider than the local metric function. This tangentially shows that the global metric is learning more complex information than the local metric.
GiobalMetricDistaance
(embed): Sequential(
(0): Linear (in_features=2, out feaatuueee==000, bias=True)
(1): ReLU()
(2) : Linear (in_features-200 out out_ featuueetrees00 bias=True)
(3): ReLU()
(4): : Linear (in_features=200, out featuresee0 bias=True)
(5) : ReLU()
(6) Linear (in (in_features=200, out mut_ffatuues=100, bias=True)
(7): ReLU()
(8) Linear (in foattreuurss000, out out_features=2, bias=True)
(head): (self head (lambda a, b: (a b).nor (2, dim=-1))
)
A.1.2 NETWORK ARCHITECTURE USED SIMULATED NAVIGATION IMAGE INPUTS
The local metric function is stacked five-layer convolution network. To make learning casier, we stack the two input images channel wise, so that there is maximum flexibility for the local metric function.
13

---

Under review as a conference paper at ICLR 2020
LocalleetricCon/Large (trunk) Sequential(
(0): Conv2d 32, kernel_size=(( 4), stride= (2, 2))
(1) BatchNorm2d eps=1e-05, momentum=0.1. affine=True)
(2) ReLU()
(3) Conv2d 64, kernel sizel_size=(4, 4) stride= (2, 2))
(4) BatchNorm2dd64,, eps=1e-05, momentun=0.1, affine=True)
(5) ReLU()
(6) : Conv2d 64, kernel_size (4, 4), stride= (2, 2))
(7) BatchNorm2dd64, eps=1e-05, momentum=0.1, affine=True)
(8) : ReLU()
(9) Conv2d 32, kernel_size=(4 4), stride= 2))
(10) BattchNorm2d32,, eps=1e-05, momentum=0.1, affine=True)
(11) ReLU()
(12): V-ew(-1, (128,))
(13): Linear (in featuressss out 1ut_featuues==28, bias=True)
(14): ReLU()
(15): Linear (in_feetuures=-128 out out_features=100,
bias=True)
(16): ReLU()
(17): Linear (in_feaitte)e features=s-100 out fut_feature==1,
bias=True)
)
We increase the capacity of the network for the global metric.
GlobalMetricConv122.2
(embed): Sequential
(0): Conv2d 128, kernel_size= (7, 7), stride= (1, 1))
(1): BatchNorm2ad128, eps=1e-05, momentum=0.1, affine=True)
(2) : ReLU()
(3) : Conv2d 256, kernel_size= 7), stride=(1, 1))
(4) BatchNorm2d eps=1e-05, momentum=0.1, affine=True)
(5) : ReLU()
(6) Conv2d 256, kernel_sizer sizesize= (7, 7), stride= (2, 2))
(7) BatchNorm2d (256,
eps=1e-05, momentum=0.1. affine=True)
(8) ReLU()
(9): (256 256,
kernel (inee_sizze(7, 7), stride= 2))
(10): BatchNormm2d eps=1e-05, momentum=0.1. affine=True)
(11): ReLU()
(12) C2n6 256, ternel_size-(1 7), stride=(2, 2))
(13) BatchNorm2d (256, aps=1e-05, momentum=0.1. affine=True)
(14): ReLU()
(15): Conv2d 256, sarnel_size-ee 2), stride=(1, 1))
(16): ReLU()
(17): (iew(-1, (256,))
(18): Linear fel__fatuure=2,,, out_ f bias=True)
(head): (self, head (lambda a, b: (a b) norm (2, dim=-1))
A.1.3 NETWORK ARCHITECTURE USED IN ROPE AND STREETLEARN
To obtain good performance the vision task, we found that is it helpful to introduce the ResNet18 architecturdHe..o of all (201).. We verify the learning capacity of this architecture by running supervised learning the StreetLearn dataset. For the local metric function, regular convolution network that is deeper and wider sufficient.
LocalMeetricConvDeeg(
14

---

Under review as a conference paper at ICLR 2020
(trunk) Sequential(
(0): (onv2d 128, kernel_size= (4, 4), stride= (2, 2))
(1): : BatchNormm2d128,, eps-1e-05, momentum=0.1, affine-True)
(2) : ReLU()
(3) Conv2d(128, 128, kernel size= kernel_size-44, 4), stride= (2, 2))
(4) : BatchNorm2d eps=1e-05, momentum=0.1, 1, affine=True)
(5) : ReLU()
(6): : Conv 128, gernel_size- (4, 4), stride= 1))
(7) : BatchNorm2d(128, eps=1e-05, momentum=0.1, affine-True)
(8) ReLU()
(9) : Conv2d(128, 128,
kernel (4ze=_, 4), stride=(1, 1))
(10) Batchlorrm2d128,, eps=1e-05, momentum=0.1, affine=True)
(11) ReLU()
(12) Conv2d(128, 128,
kernel_ (4 4), stride= 1))
(13) BatchNorrm2d128, eps=1e-05, momentum=0.1, affine=True)
(14) ReLU()
(15) C1nv 128, kernel_ (ize__,, 4), stride=(1, 1))
(16) BatchNorm22d128,, eps=1e-05, momentum=0.1. 1, affine=True)
(17): ReLU()
(18): View(-1, (512,))
(19): Linear Linear(in_ fe1tureeurs out out_features-128, bias=True)
(20): ReLU()
(21): Linear (in 1i__feature=-18, out ytt_features=100,
bias=True)
(22): ReLU()
(23) Linear (in featuresse, out vut_features=1, bias=True)
)
The global metric function uses R8sNet18 trunk.
Realeet8LL1
(embed) ResNet18( (conv_1);
nn. Conv2d(1,, 64, ternel_size=1 stride=2, padding-3, bias=False) (ResNet18): : ResNet18([2, 2, 2, 2])
(head): (self, head (lambda a, (a b) norm dim=-1))
15


Reviews:
[{"review_id": "S1x9U4-I5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper aims at learning a latent representation of images in the setting of sequential decision making. The representation are learned such that there exists a metric that correctly reflects the difference in reachability between points in the neighborhood of the current observation and the goal.\n\nI'm struggeling to understand the core approach of the paper. More specifically, while learning the local metric (Alg. 1) seems clear, I can not understand the details of Alg.2 (which btw. is never referenced in the text). The surrounding paragraph is not detailed enough. Why is \\Phi(x, x') denoted a global embedding? \\Phi has two inputs, shouldn't that be some sort of a metric? How is \"find n\" done? There is a lot of talk about embeddings, but they are actually not occuring in section 3. What is a 'plannable representation'?\n\nSome of the experiments compare to VAE and its learned embedding space. Shouldn't the comparision be to models that think about the Riemannian geometry of a VAE, e.g. \"Latent space oddity: on the curva-ture of deep generative models\". There are a several citations missing in that direction, going back to at least \"Metrics  for  probabilistic geometries\" by Tossi et al. in 2014. As it was also pointed out in a public comment, relevant citations related to \"Learning for planning\" seem to be missing, too. Finally, a wider set of experiments needs to demonstrate the method (again, considering the scope of the as-of-now-not-cited papers).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeuCKuCtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Paper Summary\n\nWhile 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. \n\n## Strengths\n\n- bootstrapping a learned local distance metric to a global distance metric to reduce test-time planning cost is an interesting problem\n- the paper has nice visualizations / analysis on the toy dataset\n- the learning procedure for the local distance metric is clearly described\n- the paper uses a large variety of different visualizations to make concepts and results clearer \n\n## Weaknesses\n\n(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. \n\n(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\".\n\n(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).\n\n(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)\n\n(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) \n\n(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).\n\n(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.\n\n\n## Questions\n\n(A) What policy is used to collect the training data on each environment?\n(B) What is the relation between the \"global embedding\" \\Phi and the \"goal-conditioned value function\" V_\\Phi(x, x_prime) in Algorithm 2? \n(C) What is the difference between the local metric function \\phi and the reward function in Algorithm 2? Are they the same?\n(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?\n(E) What does the notation N(1, \\eps) in line 5 of Algorithm 2 mean?\n(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)?\n\n\n## Suggestions to improve the paper\n\n(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.\n\n(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. \n\n(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.\n\n(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.\n\n(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.\n\n(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\".\n\n(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.\n\n\n## Minor Edit Suggestions\n- 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\n- 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\n\n\n[Novelty]: minor\n[technical novelty]: minor\n[Experimental Design]: Okay\n[potential impact]: minor\n\n################\n[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.\n[Confidence]: High\n\n\n[1] Cognitive Planning and Mapping, Gupta et al., 2017\n[2] Universal Planning Networks, Srinivas et al., 2018\n[3] Search on the Replay Buffer: Bridging Planning and Reinforcement Learning, Eysenbach et al., 2019\n[4] Semi-Parametric Topological Memory for Navigation, Savinov et al., 2018\n[5] Time-Contrastive Networks, Sermanet et al., 2017\n\n\n### Post-rebuttal reply ###\nI 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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1g_F7Z0KB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to learn a representation space that is useful for planning. This is done by a 2-step process: (1) learn a metric to reflect locality, (2) utilize that metric to learn a global metric by utilizing UVFAs from Reinforcement Learning literature. While the idea may be an interesting direction to improve sample efficiency of planning, it is not the first work that proposes to combine planning with representation learning, and I do not think the work is clearly presented/motivated/validated sufficiently to deem it acceptable.\n\nAs presented, there are many details that are unclear or imprecise. I list them below.\n\nFeedback:\n(1) The contrast between learning playable representations vs. planning via representation learning (as proposed) is  poorly motivated. The presentation ignores well recognized works in the latter in terms of UPNs [1], VINs [2].\n(2) The RL background section is poorly presented -- as written Equation (4) seems incorrect. Further, is a dynamics model learned to be able to utilize the correct form of Equation (4)? It is never specified. How exactly is a plan extracted for any of the experiments?\n(3) Possibly wrong citation for Equation (2) -- maybe cite the Oord et. al. paper? Further, c vs C -- the notation in general in the paper is inconsistent and poor.\n(4) Algorithm 1, line 4 -- typos for x. Further for Contrastive learning methods to be effective, the negative sampling needs to be much higher. What ratio of samples is used for local metric learning?\n(5) If an actual forward dynamics model is not used (Section 3 end), then as given in Algorithm 2 from pseudocode I'm completely unsure how a plan is extracted -- How is the UVFA used to extract a plan? What is N(1,\\epsilon)? P-norm?\n(6) The Dijkstra psuedocode is rather incomplete.\n(7) How is sampling done with the local metric function? How is a plan generated? These important details are missing.\n(8) Figure 4 is poorly presented/annotated. In the description \"Plan2Vec correctly stretched out learned..\" -- no it doesn't, visually it seems wrapped too. \n(9) There exists literature in RL to combine the 2 step metric learning process to 1 step. This is relevant. [3].\n(10) What is the action space of these domains? Based on visualization in Figure 3 (2), are the actions continuous? What is the action space for Figure 7? These details details are missing.\n(11) Description of the StreetLearn dataset would be useful. Further an example of why Plan2Vec generalizes (last para, Section 4.3) would be useful. Just statement based claims seem rather vacuous.\n(12) The last statement in Conclusion - why? The paper has made an argument against utilizing generative modelling in an unsupervised manner. So why would including it improve it? Such unexplained statements reflect poorly.\n\nQuestions:\n(1) What do you see as the contribution of the work? Why is it new/different from existing literature?\n(2) How exactly do you generate a plan?\n(3) How is the UVFA V used?\n(4) When to use UVFA? When to use Dijkstra? Why are the choices in the experiments as made?\n\n\nSome typos to help future version of the paper:\n(1) Section 2 -- We now overview --> We now review.\n(2) Section 2, UVFAs -- expected discounted future value --> expected sum of discounted future rewards.\n(3) Section 2 completely ignores the discount factor/horizon of an MDP, although the utility here I suppose relies on the horizon aspect.\n(4) Figure 6 explanation is very sloppy (description and body).\n(5) The Zhang et. al. reference in Section 4.2 is unclear.\n\nWhile I am not from the planning community, I am from the RL community - and as presented the paper is ignoring a lot of details, and was extremely difficult to piece together for me.\n\n[1] Srinivas, Aravind, et al. \"Universal planning networks.\" arXiv preprint arXiv:1804.00645 (2018).\n[2] Tamar, Aviv, et al. \"Value iteration networks.\" Advances in Neural Information Processing Systems. 2016.\n[3] Wu, Yifan, George Tucker, and Ofir Nachum. \"The laplacian in rl: Learning representations with efficient approximations.\" arXiv preprint arXiv:1810.04586 (2018).\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a representation learning objective that makes it 
amenable to planning, 

The initial submission contained clear holes, such as missing related work and only containing very simplistic baselines. The authors have substantially updated the paper based on this feedback, resulting in a clear improvement.

Nevertheless, while the new version is a good step in the right direction, there is some additional work needed to fully address the reviewers' complaints. For example, the improved baselines are only evaluated in the most simple domain, while the more complex domains still only contain simplistic baselines that are destined to fail. There are also some unaddressed questions regarding the correctness of Eq. 4. Finally, the substantial rewrites have given the paper a less-than-polished feel.

In short, while the work is interesting, it still needs a few iterations before it's ready for publication.
Decision: Reject