TOMA: Topological Map Abstraction for Reinforcement Learning
Authors: Zhao Heng Yin
Wu-Jun Li
Venue:  (2021)
Keywords: Planning
Reinforcement Learning
Representation Learning

Abstract: Animals are able to discover the topological map (graph) of surrounding environment, which will be used for navigation. Inspired by this biological phenomenon, researchers have recently proposed to learn a graph representation for Markov decision process (MDP) and use such graphs for planning in reinforcement learning (RL). However, existing learning-based graph generation methods suffer from many drawbacks. One drawback is that existing methods do not learn an abstraction for graphs, which results in high memory and computation cost. This drawback also makes generated graph non-robust, which degrades the planning performance. Another drawback is that existing methods cannot be used for facilitating exploration which is important in RL. In this paper, we propose a new method, called topological map abstraction (TOMA), for graph generation. TOMA can learn an abstract graph representation for MDP, which costs much less memory and computation cost than existing methods. Furthermore, TOMA can be used for facilitating exploration. In particular, we propose planning to explore, in which TOMA is used to accelerate exploration by guiding the agent towards unexplored states. A novel experience replay module called vertex memory is also proposed to improve exploration performance. Experimental results show that TOMA can outperform existing methods to achieve the state-of-the-art performance.

Under review as a conference paper at ICLR 2021
TOMA: TOPOLOGICAL MAP ABSTRACTION FOR REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Animals are able to discover the topological map (graph) of surrounding environ- ment, which will be used for navigation. Inspired by this biological phenomenon, researchers have recently proposed to learn a graph representation for Markov decision process (MDP) and use such graphs for planning in reinforcement learn- ing (RL). However, existing learning- based graph generation methods suffer from many drawbacks. One drawback is that existing methods do not learn an abstraction for graphs, which results in high memory and computation cost. This trawback also makes generated graph non-robust, which degrades the planning performance. Another drawback is that existing methods cannot be used for facilitating explo- ration which is important in RL. In this paper, we propose new method, called topological map abstraction (TOMA), for learning-basee graph generation. TOMA can learn abstract graph representation for MDP, which costs much less memory and computation cost than existing methods. Furthermore, TOMA can be used for facilitating exploration. In particular, we propose planning to explore, in which TOMA is used to accelerate exploration by guiding the agent towards unexplored states. novel experience replay module called vertex memory is also proposed to improve exploration performance. Experimental results show that TOMA can outperform existing methods to achieve the state-of-the-an performance.
INTRODUCTION
Animals are able to discover topological map (graph) of surrounding environment Oeeeee and Dostrovsky 1971 Moser et al. 2008), which will be used as hints for navigation. For example, previous maze experiments on rats (O Keefe and Dostrovsky, 1971) reveal that rats can create mental representation of the maze and use such representation to reach the food placed in the maze. In cognitive science society, researchers summarize these discoveries in cognitive map theory [Tolman 1948), which states that animals can extract and code the structure environment in a compact and abstract map representation.
Inspired by such biological phenomenon, researchers have proposed to generate topological graph representation for Markov decision process (MDP) and use such graphs for planning in reinforcement learning (RL). Early graph generation methods (Mannor et al. 2004 are usually apply some human prior to aggregate similar states to generate vertices. Recently, researchers propose some learning-basse
which
graph generation algorithms which learn such state aggregation automatically. Such methods have been proved be better than prior-based methods (Metzen) (013). These methods generally treat the states in a replay buffer as vertices. For the edges of the graphs, some methods like SPTM (Savinov et al. 2018)) train a reachability predictor via self-supervised learning and combine it with human experience to construct the edges. Other methods like SoRB (Eysenbach al. 2019) exploit a gond-conditioned agent to estimate the distance between vertices, based on which edges are constructed. These existing methods suffer from the following drawbacks. Firstly, these methods do not learn an abstraction for graphs and usually consider all the states in the buffer as vertices (Savinov et al. 2018), which results in high memory and computation cost. This drawback also makes generated graph non-robust, which will degrade the planning performance. Secondly, existing methods cannot be used for facilitating exploration, which is important in RL. In particular, methods like SPTM rely on human sampled trajectories to generate the graph, which is infeasible in RI. exploration. Methods like SoRB require training another goal-conditioned agent. Such training

---

Under review as a conference paper at ICLR 2021
procedure assumes knowledge of the environment since it requires generate several goal-reaching tasks to train the agent. This practice is also intractable in RL exploration.
In this paper, propose new method, called TOpological Map Abstraction (TOMA), for learning- based graph generation. The main contributions of this paper are outlined as follows:
TOMA can learn to generate an abstract graph representation for MDP. Different from existing methods in which each vertex of the graph represents state, each vertex in TOMA represents a cluster of states. As result, compared with existing methods TOMA has much less memory and computation cost, and can generate more robust graph for planning.
TOMA can be used to facilitate exploration. In particular, we propose planning to explore, in which TOMA is used to accelerate exploration by guiding the agent towards unexplored states. A novel experience replay module called vertex memory is also proposed to improve exploration performance.
Experimental results show that TOMA can robustly generate abstract graph representation several 2D world environments with different types of observation and outperform previous learning--ee bbased graph generation methods to achieve the state-of-the-ae perfor- mance.
ALGORITHM
2.1 NOTATIONS
In this paper, we model a RL problem as Markov decision process (MDP), A MDP is a tuple M(S, A, R, 7; P), where
state space, is the action space, R: A + is a reward function, y is discount factor and P(s 18t, ax) is the transition dynamic. p(x, y) = || y|l denotes Euclidean distance. G(V, F.) denotes a graph, where its vertex set and E. is edge set. For any set X, we define its indicator function 1x (z) as follows: 1x(x) if X, 1x(x)) x & X.
2.2 TOMA
Figure gives illustration of TOMA, which tries map states to abstract graph. A landmark set L is a subset of and each landmark E L is a one-to-one correspondence to a vertex U; in the graph. Each 4; and v; will represent cluster of states. In order decide which vertex state 8 E corresponds to, we first use a locality sensitive embedding function th to calculate its latent representation (s) in the embedding space Z. Then if z's nearest neighbor in the embedded landmark set dg (L) = [do(1) E L} is de (44), we will map s to vertex E V.
Landmark 4
ov(k)
Vertex-labeled trajectory
Veriex 1/
Embed Φn
State Space
Emhedding Space Z
Graph Representation G(V.E) E)
12
Figure 1: Illustration of TOMA. We will pick up some states landmarks (colored triangles) in the state space the original MDP M. Each landmark (colored circles) in graph G and covers some areas in S. Embedding Φe is trained by self-supervised learning. We will label each state on a trajectory with a corresponding vertex and use to generate the graph dynamically.
a one-to-one correspondence to vertex v;
2

---

Under review as a conference paper at ICLR 2021
2.2.1 LOCALITY SENSITIVE EMBEDDING
locality sensitive embedding is local distance preserving mapping Φy from state space S to an embedding space Z, which is an Euclidean space Rn in our implementation. Given a trajectory T = (Su, ag, $1, d1,.....sn we can use dy = j il/r to estimate the distance between s; and 8j. to re-seale the distance and we will further explain its meaning later. In practice, however, dij is a noizy estimation for shortest distance and approximating directly won't converge in most cases. Hence, we propose to estimate which interval the real distance lies in. First, we define three indicator functions:
Here is radius
(x) 10.)
(2 (x))
(2)
xa(2) 03,+ (2),
which mark three disjoint regions [0. 1]. (1. 3), (3. +o0), respectively. Then we define an anti-bump
function (x) = Relu(- + a) + Relu b). Here, Relu(z) max(0, the rectified linear
unit (ReL.U) function (Glorot et al. 2011). With this {(x), we can measure the deviation from the
above intervals. Let
(x(x) {- (x) Relu(x 1);
(4)
C2(x) = (1,((z) = Relu(-z x + 1) + Relu(z - -3),
(5)
Cz(z) (3 (2) Relu( 3),
(6)
and let d' = (sx)) do (s,)) denote the distance between s; and 8j in the embedding space. Our embedding loss is defined as
[()) )~.,
+ (ixe(de) + (exs(ds)<s(dd)))
(7)
Here Ps is sample distribution which will be described later, A₁ and X2 are two hyper-parameters to balance the importance of the estimation for different distances. We find that good choice is to pick X 0.5, A2 = 0.2 to ensure that our model focuses on the terms with lower variance. this equation, there are some critical components to notice:
Radius As we will see later, the hyper-parameter will determine the granularity each graph vertex, which we term as radius. If we define the k-ball neighborhood of E S to be
Bx(s) = {s' E S)p(cooss), do(s)) < k),,
(8)
then (s) will cover more states when is larger. During the graph generation process, will remove redundant vertices by checking whether Bi (1:) and B, (1,) intersect too much. Re-scaling by makes it easier to train the embedding function.
Sample Distribution P. The state pair 8y) in the loss function is sampled from neighborhood biased distribution P.. We will sample St) (i < j) with probability a, j < 4r. And we will sample (st, sz) (i < j) with probability 1 1 a, if - i > 4r. We simply take a = 0.5 and the choice of a is not sensitive in our experiment.
the implementation, we use this sample distribution to draw samples from trajectory and put them into replay pool. Then we train the embedding function by uniformly drawing samples from the pool.
Anti-Bune Bump Functions The idea of anti-bump function is inspired by the partition of unity theorem in differential topology (Hirsch) 1997). where bunch of bump functions are used to glue the local charts of manifold together as to derive global properties of differential manifolds. In proofs of many differential topology theorems, one crucial step is to use bump function to segregate each local chart into three disjoint regions by radius 1, 2 and 3, which is analogous to method. The loss function is crucial in our method, as in experiment we find that training won't converge if we replace this loss function with commonly used L2 loss.
2.2.2 DYNAMIC GRAPH GENERATION
An abstract graph representation G(V, E) should satisfy the following basic requirements:
Simple: For any 2 2y E V, if Us + Uj. (1) n Bi(4) should not contain too many elements.
3

---

Under review as a conference paper at ICLR 2021
Accurate: For any U, U/ V and i # Vy. (tr, (y) E if and only if the agent can travel from some E (1))) to some E Bi(y) in a small number steps.
Abundant: Us ev B1 (44) should cover the states as many as possible.
Dynamic: G grows dynamically, by absorbing topology information of novel states.
In the following content, we show a dynamic graph generation method fulfilling such requirements. First, we introduce the basic operations in our generation procedure. The operations can be reduced to the following three categories:
Initializing
[II: Initialize] Vf 0. we will pick a landmark from currently sampled trajectories and add vertex into V accordingly, In our implementation, this landmark is the initial state of the agent.
Adding
[AT: Add Labels] For each state on trajectory, label it with its corresponding graph vertex. Let = arg minj:a, (()) (o((,) and d = ((rb(s) (4))) There are three possible [0, 1.5]. We label s with u4- (2) E [2, 3]. We consider as an appropriate landmark candidate. Therefore, we label s with NULL but add it to candidate queue. (3) Otherwise, s simply labelled with NULL.
cases: (1)
[A2: Add Vertices] We move some states from the candidate queue into the landmark set and update V accordingly. Once state added to the landmark set, we will relabel it from NULL to its vertex identifier.
[A3 Add Edges] Let the labelled trajectory to be (Vig Uiy..... U..)).
). If we find ui and 1 are different vertices in the existing graph, we will add an edge (U42 U4241) into the graph.
Checking
[C1: Check Vertices] If p())(L)), oo(l)) 1.5, then we will merge i and Fy.
[C2: Check Edges] For any edge (Dy, 0y), if (l0)())),o(())) >> 3, we will remove this edge.
For efficient nearest neighbor search, we use Kd-tree (Bentley 1975) to manage the vertices. Based on the above operations, we can get our graph generation algorithm TOMA which is summarized in Algorithm
Algorithm Topological Map Abstraction (TOMA)
1: Pool P t- 6. Vertex set V <- (). Edge set E < D. Graph G(V, E).
2: for = 1, ... do
3: Sample trajectory T using some policy or by random.
4: Sample state pairs from T using distribution P. and put them to P.
5: Training the embedding function
using samples from P.
6: Initialize G using (I1) if it's empty.
7: Add vertices and edges using (A1) (A3).
8: Check the graph using (C1) to (C2).
9:
end for
2.2.3 INCRFASING ROBUSTNESS
In practice, we find TOMA sometimes provides inaccurate estimation on image domains without rich visual information. This is similar to the findings of (Eysenbach al. 2019), which uses an ensemble of distributional value function for robust distance estimation. To increase robustness, we can also use an ensemble embedding functions to provide reliable neighborhood relationship estimation on these difficult domains. The functions in the ensemble are trained with data drawn from the same pool. During labelling, each function will vote a nearest neighbor for the given observation and TOMA will select the winner the label. To evaluate the distance between states, use the average of the distance estimation of all embedding functions. In (Eysenbach et al., 2019), the authors find that ensemble is an indispensable component in their value function based method for all applications. On the contrary, TOMA does not require ensemble to increase robustness on applications with rich information.
4

---

Under review as a conference paper at ICLR 2021
2.3 PLANNING TO EXPLORE
Since the graph of TOMA expands dynamically as agent samples in the environment, it can be fitted into standard RL settings to facilitate exploration. We choose the furthest vertex or the least visited vertex as the ultimate goal for agent in each episode. During sampling we periodically run Dijkstra's algorithm figure out the path towards the goal from the current state, and the vertices on the path are used as intermediate goals. To ensure that the agent can stably reach the border, we further introduce the following memory module.
Vertex Memory We observe that the agent usually fails to explore efficiently simply because it forgets how to reach the border explored area as training goes on. In order to make agent recall the way the border, we require that each vertex 2; should maintain small replay buffer to record successful transitions into the cluster of 24 Then, our agent is going towards goal g and the vertices will draw
on the shortest path towards the corresponding landmark of g are U1, U2, ... Uk, then some experience from the replay pool of U1, U2,.., Uk to inform the agent of relevant knowledge during training. In the implementation, data are drawn from experience of vertex memory which provides task-specific knowledge, while the other half are drawn from normal hindsight experience replay (HER) (Andrychowicz et al., 2017) which provides general knowledge. We will use the sampled trajectory to update the memory of visited vertices the end of each epoch. The overall procedure summarized Algorithm 2.
use the following replay strategy: half of the training
Algorithm 2 Planning to Explore with TOMA
1: for 2,. do
2: Set goal g using some criterion. Sample a trajectory I' under the guidance of intermediate goals.
4: Update graph using T (Algorithm 1).
5: Update vertex memory and HER using T.
6: Train the policy ı using experience drawn from vertex memory and HER.
7: end for
EXPERIMENTS
In the experiments, we first show that TOMA can generate abstract graphs via visualization and demonstrate that such graph is suitable for planning. Then we carry out exploration experiment in some sparse reward environments and show that TOMA can facilitate exploration.
3.1
GRAPH GENERATION
3.1.1 VISUALIZATION
In this section, we test whether TOMA can generate abstract graph via visualization. In order to provide intuitive visualization, we use several 2D world environments to test TOMA, which are shown in Figure a). The scale of these planar worlds is 100 x 100. In these worlds, there are some walls which agent can not cross through. The agent can take 4 different actions at each step: going up. down, left or right for unit distance. To simulate various reinforcement learning domains, we test the agent on four different types of observation respectively: sensor, noisy sensor, MNIST digit (LeCun and Cortes 2010) and top-down observation. Sensor observation is simply the (2r,y) coordinates of the agent and the noizy sensor observation is the coordinates with 8 random features. Both MNIST digit and top-down observation are image observations. MNIST digit observation is mixture of MNIST digit images. which is similar to the reconstructed MNIST digit image of variational auto-encoders (Kingma and Welling, 2014). The observed digit is based on the agent's position and varies continuously as agent moves in this world. Top-down observation is blank image with a white dot indicating the agent's 's location. We use three different maps: "Empty", "Lines" and "Four rooms". Since in this experiment we only care about whether TOMA can generate abstract graph representation from enough samples, we spawn a random agent at a random position in the map at the beginning of each episode. Each episode lasts 1000 steps and run 500 episodes in each experiment. We use ensemble to increase robustness only for the top-down observation. The visualization result of the graph is provided in the Figure bb). Despite very few missing edges
5

---

Under review as a conference paper at ICLR 2021
Sensor
Noizy Seasor
MIIST Digri
Top-down
Empty
Sensor
MNIST I Digit
Top-down
Lines
Fourr Rooms
Empty
Lines
Four Rooms
Figure 2: (a) 2D world observations (above) and maps (below). (b) The generated graph of different 2D world environments under different types of observation. Each connected colored segment indicates vertex with its state coverage. The blue line connecting two segments denotes edge connecting the corresponding two vertices.
Table 1: Performance of different graph generation algorithms
Sensor
MNIST Digit
Top-down
Algorithm
Suc.
Size
Time
Suc.
Size
Time
Suc.
Size
Time
SPTM
73.4%
10k
> 1s
60.3%
10k
> 1s
61.5%
10k
> 1s
SoRB
77.6%
1k
> 0.5s
56.3%
1k
> 0.5s
52.0%
1k
0.5s
TOMA
87.5%
0.1k
< 0.1s
77.2%
0.1k
< 0.1s
75.3%
0.1k
< 0.1s
or wrong edges, the generated graphs are reasonable in 12 cases. The successful result on various observation domains suggest that TOMA reliable and robust abstract graph generation algorithm.
3.1.2 PLANNING PERFORMANCE
Since learning-basee based graph generation methods are better than those prior-based methods (Metzen 2013), we only compare TOMA with recent state-of-the learning- baselines including SPTM and SoRB. We first pretrain a coal-conditioned agent which can reach nearby goals. Then we use the generated graph of TOMA in Section 3.1.1 and SPTM and SoRB to plan for agent respectively. We randomly generate goal-reaching tasks in Four Rooms on three different types of observation. Table shows the average success rate of navigation, the size the generated graph and the planning time. The agent using the graph of TOMA has higher success rate in navigation. The main reason behind this is that the generated graph of TOMA can capture more robust topological structure. SPTM and SoRB maintain too many vertices and result, we find that they usually miss neighborhood edges or introduce false edges since the learned model is not accurate on all the vertex pairs. Moreover, TOMA also consumes less memory and plans faster compared with other methods. To localize the agent, TOMA only needs to call the embedding network once, and uses the efficient nearest neighbor search find out the corresponding vertex Oloo [V]) time. Since TOMA maintains less vertices and edges, the Dijkstra algorithm applied in planning also returns the shortest path faster. The efficiency of planning crucial since significantly reduces the training time of Algorithm) 2 which requires iterative planning during online sampling.
3.2
UNSUPERVISED EXPLORATION
3.2. SETTING
In this section, we test whether TOMA can explore the sparse-reward environments. The environments for test are MountainCar and another 2D world called Snake maze, which are shown in Figure 3 MountainCar is classical RL experiment where the agent tries drive car up to the hill on the right. Snake maze is 2D world environment where the agent tries to go from the upper-left corner to the bottom-right corner. In this environment, reaching end of the maze usually requires 300-400 steps.

---

Under review as a conference paper at ICLR 2021
In these environments, set the reward provided by environment to O. We use DQN (Mnih et al. 22155) as the agent for Mountain- Car and Snake maze they are tasks with discrete actions. In MountainCar, we set the goal of each episode to be the least visited landmark since the agent needs explore and the furthest vertex will sometimes guide the agent into local minima. In Snake maze, we simply set the goal be the furthest vertex in the graph. Since HER makes up part of our memory, we use DQN with HER as the baseline for comparison. We test two variants of TOMA: TOMA with vertex memory (TOMA-VM) and TOMA without vertex memory (TOMA). For fair compari-
acceleration skill
Figure 3: Environments used to test the exploration perfor- mance. (Left) Mountain car. (Right) Snake maze.
son, these three methods share the same DQN and HER parameters. For MountainCar, we train the agent for 20 iterations and each iteration lasts for 200 steps. For Snake maze on sensor ob- servation, we train the agent for 300 iterations. For Snake maze on MNIST digit and top-down observation, we train the agent for 500 iterations. Each iteration lasts for 1000 steps. In each iteration, record the max distance the agent reached in the past history. We additionally caleulate a mean reached distance for experiments in Snake maze, which is the average reached distance in the past 10 iterations. We repeat the experiments for times, and report the mean results.
3.2.2 RESULT
The results are shown in Figure 5] We can find that TOMA-VM and TOMA outperform the baseline HER in all these experiments. In MountainCar experiment, we find that the HER agent fails to discover the acceleration skill and gets stuck at the local minima. In contrast, both TOMA-V VM and TOMA agents discover the acceleration skill within 3 iterations and successfully climb up to the right hill. Figure 4 (a) shows some intermediate goals of the agent of TOMA-VM, which intuitively demonstrates the effective- ness of TOMA-VM. In Snake maze with sensor observation, the HER agent cannot learn any meaningful action while our TOMA- VM agent can successfully reach the end of the maze. Though the TOMA agent cannot always successfully reach the border of the exploration states in every iteration, there still over 50% probability of reaching the final goal. In the image based experiments, however, we find that the learning process of goal-conditioned DQN on such a domain is not stable enough. Therefore, our agent can only reach the left or middle bottom corner of the maze average. A typical example of the generated graph representation during exploration in Top-down Snake maze is shown Figure (b). This generated graph does provide correct guidance, but the agent struggles to learn the right action across all states. In these experiments, TOMA-VM constantly performs better than TOMA. The reason behind is discussed in next section.
(h)
Figure 4: (a) Intermediate goals in MountainCar. (b) The gen- erated graph top-down Snake maze during exploration.
3.2.3 DYNAMICS
We visualize the trajectory and the generated graph during training the Snake maze with sensor observation in Figure 6 We render the last 10 trajectories and the generated graph every 50 iterations. We find that TOMA will get stuck at the first corner simply because it fails to realize that it should go left, as the past experience from HER pool are mainly for going right and down. In contrast, since TOMA-VM recall the past experience of reaching the middle of the second corridor, it can successfully go across the second corridor and reach the bottom.
4 RELATED WORK
Studies animals (O Keeee and Dostrovsky 1971 Moser et al., 2008 Collett 1996) reveal that animals are able to build an mental representation to reflect the topological map (graph) of the surrounding environment and aninals will use such representation for navigation. This mental representation is usually termed as mental map (Lynch and for Urban Studies, 1960) or cognitive map (Tolman| [1948). Furthermore, there exists evidence (Gillner and Mallot 1998) Driscoll et al.) 2000) showing that the mental representation is based on landmarks, which serve as an abstraction of the real environment.
7

---

Under review as a conference paper at ICLR 2021
(a) MountainCar (Max)
(b) Maze sensor (Max)
(c) Maze sensor (Mean)
(d) Maze MNIST (Max) (c) Maze MNIST (Mean) (f) Maze top-down (Max) (g) Maze top-down (Mean)
Figure 5: Reached distance of TOMA-VM, TOMA and HER. We also plot the mean of the reached distance for Snake maze experiments. TOMA-VM consistently performs better than the baseline method HER which gets stuck at local minima due to the lack of graph guidance.
(a) TOMA with vertex memory
(b) TOMA without vertex memory
Figure 6: The generated graphs and last 10 trajectories of TOMA-VM and TOMA every 50 iterations.
Graph is natural implementation of this mental representation. Researchers have proposed learning to generate graph representation for RL. Existing methods such as SPTM (Savinov et al., 2018) and SoRB (Eysenbach et al. 2019) propose to generate graph representations for planning and they treat the states in the replay buffer as vertices. SPTM learns a reachability predictor and a locomotion model from random samples by self-supervised learning and it applies them of human experience to compute paths towards goals. SoRB considers the value function of goal- conditioned policy as distance metric and it to determine edges between vertices. SoRB requires to train the agent on several random generated goal reaching tasks the environment during learning. Compared with these approaches which do not adopt abstraction, TOMA generates an abstract graph which has less memory and computation cost and can increase the planning performance. Also, since TOMA is free from constraints such as human experience and training another RI. agent, can be used in RL exploration.
replay buffer
Graph generation methods are related model-based RL methods (Sutton 1990) which plan in latent space (Hafner et al., 2019 Kurutach et al., 2018). Recent research (Kara et al. (020) suggests that model-based overcome by using a graph. TOMA is also related to state abstraction methods like (Sutton et al.
methods in latent space are hard train practice and such drawback can be
1999 Singh et al. 1994, Andre and Russell 2002 Mannor et al., 2204 Ferns et al.) 2004 ct al.
2006 Abel et al.
2016 Roderick al.) 2018) but these methods are prior-based. (Metzen 2013 points out that learning- based methods perform better than these prior- prior-based methods.
CONCLUSION
In this paper, we propose a novel graph generation method called TOMA for reinforcement learning, which can generate abstract graph representation for MDP. Experimental results show that TOMA costs much less memory and computation cost than existing methods and can be used for facilitating exploration. In the future, will further explore other potential applications of TOMA.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
David Abel, D. Ellis Hershkowitz, and Michael L. Littman. Near optimal behavior via approxi- mate state abstraction. In Proceedings of the 33nd International Conference on Machine Learn- ing (ICML), 2016.
David Andre and Stuart J. Russell. State abstraction for programmable reinforcement learning agents. In Proceedings of the 18th National Conference on Artificial Intelligence and the 14th Conference on Innovative Applications of Artificial Intelligence (AAAI), 2002.
Marcin Andrychowicz, Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong. Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2017.
Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517, 1975.
Thomas Collett. Insect navigation route to the goal: Multiple strategies for the use of landmarks. The Journal of Experimental Biology, 199:227-35, 02 1996.
Ira Driscoll, Derek Hamilton, and Robert Sutherland. Limitations on the use of distal cues in virtual place learning. Journal of Cognitive Neuroscience, page 21, 01 2000.
Ben Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2019.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In Proceedings of the 20th Conference Uncertainty in Artificial Intelligence (UAI), page 162-169, 2004.
Sabine Gillner and Hanspeter Mallot. Navigation and acquisition of spatial knowledge in a virtual maze. Journal of Cognitive Neuroscience, 10:445-600 63, 08 1998.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. volume 97 of Proceedings of Machine Learning Research, pages 2555-2565, 2019.
M.W. Hirsch. Differential Topology. Graduate Texts in Mathematics. Springer New York, 1997.
Liu Kara, Kurutach Thanard, Tung Christine, Abbeel Pieter, and Tamar Aviv. Hallucinative topo- logical memory for zero-shot visual planning. In Proceedings of the International Conference on Machine Learning (ICML), pages 8642-8653, 2020.
Diederik Kingma and Max Welling. Auto-encoding variational bayes. Proceedings of the 2nd International Conference Learning Representations (ICLR), 2014.
Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart J Russell, and Pieter Abbeel. Learning plannable representations with causal infogan. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pages 8733-8744. 2018.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
Lihong Li, Thomas J. Walsh, and Michael L. Littman. Towards unified theory of state abstraction for mdps. In Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics (ISAIM). 2006.
K. Lynch and Joint Center for Urban Studies. The Image of the City. Harvard-MIT Joint Center for Urban Studies Series. Harvard University Press, 1960.

---

Under review as a conference paper at ICLR 2021
Shie Mannor, Ishai Menache, Amit Hoze, and Uni Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the 21st International Conference on Machine Learn- ing (ICML), 2004.
Jan Hendrik Metzen. Learning graph-based representations for continuous reinforcement learning domains. In Proceedings of the European Conference on Machine Learning (ECML), pages 8 81-96, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Human-level control through deep reinforcement learning. Nature, 518:529- 533, 2015.
Edvard I. Moser, Emilio Kropff, and May-Britt Moser. Place cells, grid cells, and the brain's spatial representation system. Annual Review of Neuroscience, 31(1):69-88) 2008.
O' Keefe and J. Dostrovsky. The hippocampus as spatial map. preliminary evidence from unit activity in the freely-moving rat. Brain Research, 34(1):171 - 175, 1971.
Melrose Roderick, Christopher Grimm, and Stefanie Tellex. Deep abstract q-networks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), page 131-138, 2018.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi- cerimerrametric topological memory for navigation. In Proceedings of the 6th International Conference on Learning Representa- fions (ICL.), 2018.
Satinder P. Singh, Tommi S. Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 1994.
Richard S. Sutton. Integrated architectures for learning, planning, and reacting based on approxi- mating dynamic programming. In Proceedings of the 7th International Conference Machine Learning (ICML), 1990.
Richard S. Sutton, Doina Precup, and Satinder P. Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2)1811-11, 1999.
Edward C. Tolman, Cognitive maps in rats and men. Psychological Review, 55:189 208, 1948.
10


Reviews:
[{"review_id": "gLNIRUfCIVR", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThe paper aims at achieving learning-based graph representations of MDPs with the goal of improving results in sparse-reward RL problems via better exploration. Experimens are mostly done on synthetic environments proposed by the paper itself (besides MountainCar environment). Baselines are SPTM, SoRB and HER.\n\n\n##########################################################################\n\nReasons for score:\n\nExperimental evidence in the paper is insufficient to estimate the value of the approach.\n\n\n##########################################################################\n\nPros:\n\n1. Interesting ideas about planning for exploration and learnable graph representations for MDPs.\n2. Visually the paper looks nice.\n\n##########################################################################\n\nCons:\n\n1. Test environments/tasks don't look persuasive. Why not pick some more established setups from prior work (e.g., SPTM or SoRB or HER papers) and show advantage on their ground? Creating new setups is only justified if the existing ones are not sufficient with respect to the goals of the paper.  \n2. The main algorithm idea is not clear. There are many components and the description does not comprehensively show how they fit together and what motivated those design choices. \n3. Some statements in the paper would profit from softening/more accurate formulation. To give a few examples:\n- \"SPTM rely on human sampled trajectories to generate the graph, which is infeasible in RL exploration\" - collecting human demonstrations/trajectories is indeed costly but it's not infeasible. In fact, it is a common recipe for kick-starting RL which powered the first versions of AlphaGo and AlphaStar.\n- \"Another drawback is that existing methods cannot be used for facilitating exploration which is important in RL.\" - it is worth keeping in mind a paper \"Episodic Curiosity through Reachability\" https://arxiv.org/pdf/1810.02274.pdf. While it doesn't plan for exploration, it still keeps some kind of topological map in memory, although without explicitly storing edges.\n- \"In cognitive science society, researchers summarize these discoveries in cognitive map theory (Tolman, 1948), which states that animals can extract and code the structure of environment in a compact and abstract map representation.\" - that paper came many years earlier than those previously mentioned, so it can't possibly summarize them. In fact, O'Keefe was sceptical about cognitive maps from what I read in those papers. \n\n##########################################################################\n\nQuestions during rebuttal period: \n\nUnfortunately, to make paper meet high ICLR standards would require too large a change in my opinion. I would encourage the authors to fix the cons mentioned above and resubmit.\n\n#########################################################################\n\nMinor suggestions and typos: \n\n(1) \"which mark three disjoint regions [0; 1]; (1; 3]; (3;+1),\" - how did the magical constant 3 come to be?", "extra_scores": {}, "extra_text": {}}, {"review_id": "dVWOGTs7cwl", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**: This paper studies nonparametric planning in RL, building on prior work in two ways. First, the proposed method creates graph vertices corresponding to *clusters* of observations, rather than single observations. The motivation for this decision is that it leads to sparser graphs, making planning easier. The second idea is to use the graph for exploration by sampling goal states that are near the \"fringe\" of the graph. Experimental results suggest that the first idea increases performance (success rate and wall-clock time) on 2D navigation tasks. Additional experiments show that the second idea improves exploration.\n\n**Significance**: Nonparametric planning methods have gained traction in the RL community in recent years, and hold the promise of bridging the RL community with the motion planning community. The problems that this paper addresses, increasing the robustness/efficiency of graph construction and improving exploration, are indeed important problems to solve in this area. While this paper makes some progress on these problems, it's unclear how big the improvement is (especially compared with other recent methods, see below), and whether this improvement transfers to tasks beyond 2D navigation.\n\n**Novelty**: Both of the problems that this paper aims to address (building a better graph and using the graph for exploration) have been studied in recent papers. For graph construction, see \"Hallucinative Topological Memory for Zero-Shot Visual Planning\" [Liu 2020] and \"Sparse Graphical Memory for Robust Planning\" [Laskin 2020]. For exploration, see \"Episodic Curiosity through Reachability\" [Savinov 2018], \"Skew-Fit: State-Covering Self-Supervised Reinforcement Learning\" [Pong 2019], and \"Maximum Entropy Gain Exploration\" [Pitis 2020]. The paper does not discuss these (very related) papers in any depth, nor does it compare against any of them in the experiments.\n\n**Experiments**: The experimental setup seems reasonable. I especially appreciated that a variety of environment layouts and observation types were used. For the experiments in S3.1, it makes sense that SPTM and SoRB require more time, but it isn't clear to me why they should have lower success rates. In addition, I'd recommend comparing against [Liu 2020] or [Laskin 2020]. It'd be great to include some analysis, visualizations, or ablation experiments to understand why these baselines have lower success rates. For the experiments in S3.2, the plots of the intermediate goals (Fig 4) were quite nice. I'd recommend adding comparisons with at least one exploration bonus method (e.g., RND [Burda 2018]) and one goal-sampling exploration method (e.g., [Savinov 18, Pong 19, Pitis 20]).\n\n**Clarity**: The writing clarity of the paper could be improved, especially in the sections describing the method. See \"Minor comments\" below.\n\nOverall, I give this paper a score of 4 / 10, primarily because of a lack of comparisons with prior work. I would consider increasing my score if the comparisons suggested above were added. Improving the writing clarity would also help convince me to increase my score.\n\n**Questions for discussion**:\n* How are goals sampled for transitions from the vertex memory, and which transitions are used for HER?\n* \"To increase robustness, we can also use an ensemble ... TOMA does not require ensemble to increase robustness\" -- So, does the method use ensembles or not? Do the SoRB and SPTM baselines use ensembles?\n* Table 1: Does \"size\" refer to the number of edges or vertices? What *exactly* does \"time\" correspond to?\n*  In S3.1, do you have any intuition for why SPTM and SoRB should have lower success rates than the proposed method?\n* S3.2.1: Why were different environments used in this experiment, as compared with the experiment in S3.1?\n* \"TOMA is free from constraints such as human experience and training another RL agent\" -- In what way do prior methods (e.g., SPTM, SoRB) depend on human experience? It's not clear to me why any of these methods require training another RL agent for exploration.\n* \"Costs much less memory\" -- Where is this shown? (I believe that it's true.)\n\n**Minor comments**:\n* There are a number of grammar errors. I'd recommend putting the paper through a grammar checker.\n* \"This drawback also makes generated graph non-robust\" -- Please clarify why nonparametric representations are less robust.\n* \"existing methods cannot be used for facilitating exploration\" -- Can this be clarified?\n* \"assumes knowledge of the environment\" -- SoRB and SPTM *don't* require knowledge of the transition function.\n* \"This practice is also intractable in RL exploration.\" -- Exactly what aspect is intractable?\n* S2.1: Generally avoid starting sentences with inline math.\n* S2.2.1: It's unclear if distance in this section refer to shortest path distances, random walk distances, Euclidean distances, or something else.\n* S2.2.1: Throughout this section it's unclear what exactly being learned (I'm assuming it's the parameters $\\theta$ of the embedding function $\\phi_\\theta$). I'd recommend stating at the start what is going to be learned. E.g., \"The aim of this section is to learn a latent-space representation of observations $x$ s.t. distances in latent space reflect the Euclidean(?) distance in observation. To this end, we will learn an embedding function $\\phi_\\theta(x)$ with parameters $\\theta$...\" \n* Eq 1 - 6: I think it'd be helpful to include a plot illustrating these equations.\n* \"neighborhood biased function $P_s$\" -- Where is $P_s$ defined?\n* \"Anti-Bump Functions\" -- This discussion doesn't seem particularly important, and could be cut or moved to the appendix.\n* S2.2.2 on the graph generation is pretty hard to follow. Renaming \"checking\" -> \"pruning\" might help, as might removing some of the inline math from the three boxes and putting it in the main text (outside the boxes).\n* Vertex Memory -- I found this part hard to follow, partially because the method for training the policy hasn't been introduced yet. Also, L6 of Alg 2 seems to have a \"type error,\" as the vertex memory contains \"transitions\" but HER is a method for sampling \"goals.\"\n* \"MNIST digit\" -- Which digits are shown in which states?\n\n----------------------------------------\n**Update after author response**: I appreciate that the authors answered some of my questions, but they did not address my two main concerns: insufficient baselines and writing clarity. I therefore am inclined to maintain my vote to reject the paper (score = 4).", "extra_scores": {}, "extra_text": {}}, {"review_id": "JFMJryvdwo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work presents a method for learning topological representations for MDPs, encoded as a graph, which could then be used to guide exploration/learning via a goal-conditioned RL mechanism.\n\nThe basic idea is appealing, as a form of an intermediate method between model-based and model-free RL. Such intermediate methods which are scalable for large problems are, in principle, of great interest to the community. The paper is overall well-written and easy to follow. However, I have some concerns regarding the approach.\n\n* **Planning**: The authors use the term 'planning' but it should be emphasized that the method does not actually facilitate planning in the \"full\" sense (as it is commonly understood in RL / control), not even in the aggregated/abstracted state-space. The learned graph only represents *possible* transitions, without representing their probabilities (the behavior of TOMA in non-deterministic environments is not discussed) and, more crucially, without modelling the effect of *actions* on the transitions. On its own this is a valid approach (being kind of a \"hybrid\" between model-based and model-free), but the use of the term 'planning' (starting from the abstract) is misleading. I think the paper would benefit from a discussion of this point, making the modelling choices more clear/explicit.\n\n* **State Embedding**: The loss function used to train the embedding measures distance between (raw) states by how far apart they were visited in sampled trajectories. However this measure could (and probably will) drastically change when the behavioral policy changes. Particularly in more 'constrained' environments, some states might be seen \"far apart\" when acting in random, whereas they are in fact closer when a better policy is learned. It is not clear how TOMA handles this issue, and this relates once more to the fact that actions are not being modeled (I believe the 'merge vertices' operator is helpful here, but this is just an intuition). The 'vertex-memory' is a heuristic to overcome this limitation, but it has to go through the policy optimization itself (as it is only affecting the \"replay\" mechanism) which seems wasteful.\n\n* Another issue, somewhat related to the previous one, is that the method aggregates states uniformly (in term of the clustering \"resolution\"/granularity, regulated by the parameter $r$). In practice, it could be beneficial to encode in such a way that compresses different parts of the space to different degrees. For example, if there are boundaries/walls with narrow doorways, it would be important for the agent to know its location more accurately when next to such a doorway. \n\n* Finally, the loss function for the embedding seems rather arbitrary. How important is the partition to the particular segments of (-inf,1), (1,3), (3,inf)? How sensitive the model is to the choice of the hyperparameters $\\lambda_1,\\lambda_2$ (Also, the comment about \"ensure that our model focuses on the terms with lower variance\" is completely unclear to me. Which variance? where does it come from?). The fact that similar (?) technique is used to prove differential geometry theorems is not very helpful, in my eyes, to understand this method in the context of learning and approximation from samples.\n\n* **Prior work**: Overall this work presents a novel contribution in my eyes. But I think the discussion of its place within the context of prior work could be improved. The (non-exhaustive) references here should not be understood as a criticism for lack of novelty, rather as a suggestion for the authors to provide a more detailed context.\n\n* The idea of dynamically increasing/expanding the learned graph such that it represents the topological structure of the data/environment is closely related to some ideas stemming from the classic Self Organized Feature Maps by Kohonen (e.g Kohonen, 1982, Fritzke 1995, Martinetz and Schulten 1991). Perhaps surprisingly, these ideas or methods haven't been extensively explored in the context of RL and planning (although some work has been done, e.g: Karimpanal & Bouffanais *adaptive behavior* 2019, Smith *Neural networks* 2002 , Lo and Ghiassian *arxiv* 2019).\n\n* Guiding exploration by sampling goals from memory which are \"far away\" from current/initial state resembles the recent work on \"Episodic curiosity through reachability\" (Savinov et al.  *ICLR* 2019) which is rather relevant for the current paper. Similar ideas have been studied from several perspectives under \"goal conditioned RL\" in general.\n\n* I think the \"biological\" motivation is not too helpful for the paper. The first paragraph in the paper is not accurate (and somewhat outdated). The cited papers (and most of the original place-cells and grid-cells literature) which didn't show that animals can \"use such representation to reach the food placed in the maze\", but rather studied the way in which space is represented. In any regards, the importance of planning can be explained and justified from computational perspectives which are more relevant for the actual content of this work. It would be better, in my view, to discuss the place of the proposed method on the model-free vs. model-based \"extremes\" of RL. \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "22iKghz1Ju1", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new method for learning graph representations of RL problems. The proposed method, named TOMA, creates a set of *landmarks*, each of which is a representatives state associated with a cluster of states in the original problem.  The clustering is induced via a locality sensitive embedding function. With this embedding, a graph of landmarks is created by sampling state trajectories, and then mapping each state to existing vertices (if a nearby vertex already exist), or creating a new vertex otherwise. To add robustness, an ensemble of embedding functions is used rather than a single estimator. Once the graph is build, the shortest-path to goals can be computed using a search algorithm (e.g., Dijkstra's algorithm). The proposed approach is evaluated on a set of benchmarks, and compares favorably in this problem with recent state-of-the-art graph learning algorithms for RL. \n\nIn terms of pros, the proposed approach is interesting and novel, to the best of my knowledge. It presents a suitable addition to recent approaches exploring connections between graph-search and reinforcement learning, as I'm not aware of this particular embedding function being proposed before. I did note that the embedding bears some resemblance to that used in Eq. (5) of Plan2Vec, Yang. et al. 2020 (which is not discussed in the paper, although the paper is cited). Another useful contribution of this paper is the simple exploration technique proposed, of always trying to reach the least explored vertex, and adding a per vertex memory for the agent to keep knowledge of how to reach the graph border. Finally, the experiments illustrate the ability of the approach to construct sound graph representations of the environment, even when given high dimensional noisy observations. \n\nIn terms of cons, I think the writing can be improved in some places. For example, the locality sensitive embedding is introduced without explaining any high level intuitions about why this particular embedding should be preferred over others. Another example, is the lack of explanation for case (3) in A1 (why a state d > 3 cannot be a candidate?). Additionally, the environments considered, even accounting for high-dimensional observations, seem relatively simple (SORB considers, for instance, a visual navigation task from RGB images of 3D houses). \n\nFinally, there are some missing references:\n\n- An important one is *Huang, Z., Liu, F., & Su, H. (2019). Mapping state space using landmarks for universal goal reaching. In Advances in Neural Information Processing Systems (pp. 1942-1952).*, which samples far away landmarks (states) using either the euclidean distance, or an estimate provided by a learned value function.\n\n- Another relevant reference is *Corneil, D., Gerstner, W., & Brea, J. (2018, July). Efficient Model-Based Deep Reinforcement Learning with Variational State Tabulation. In International Conference on Machine Learning (pp. 1049-1058)*. This paper builds a discrete representation of the environment (akin to a graph), which is solved using prioritized sweeping. \n\nOverall, I'm inclined towards acceptance, but it would be useful if the authors could clarify some of the aforementioned points, and explain how this approach differs from the references mentioned above.\n\nMinor issues:\n\n- \"noizy\" --> noisy\n- The left panel of Fig. 2 doesn't add much. The bottom left part is redundant (can be seen on right), and the top left could be explained in the text (or as a small vertical column in the image). This would give more space for seeing the generated graph, which I think would be more useful.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a technique called TOMA to learn abstract graph representations of MDPs. Such an approach is said to be more efficient both in terms of memory and computation. Despite this being an interesting research topic, the reviewers unanimously recommend rejecting the paper. They all agree that the writing needs to be improved for clarity, that some of the algorithmic choices seem arbitrary, and that there are relevant baselines missing. Moreover, the authors didn’t submit a response to most reviewers.

Decision: Reject