Explore with Dynamic Map: Graph Structured Reinforcement Learning
Authors: Jiarui Jin
Sijin Zhou
Weinan Zhang
Rasool Fakoor
David Wipf
Tong He
Yong Yu
Zheng Zhang
Alex Smola
Venue:  (2021)
Keywords: Deep Reinforcement Learning
Graph Structured Reinforcement Learning
Exploration

Abstract: In reinforcement learning, a map with states and transitions built based on historical trajectories is often helpful in exploration and exploitation. Even so, learning and planning on such a map within a sparse environment remains a challenge. As a step towards this goal, we propose Graph Structured Reinforcement Learning (GSRL), which utilizes historical trajectories to slowly adjust exploration directions and learn related experiences while rapidly updating the value function estimation. GSRL constructs a dynamic graph on top of state transitions in the replay buffer based on historical trajectories, and develops an attention strategy on the map to select an appropriate goal direction, which decomposes the task of reaching a distant goal state into a sequence of easier tasks. We also leverage graph structure to sample related trajectories for efficient value learning. Results demonstrate that GSRL can outperform the state-of-the-art algorithms in terms of sample efficiency on benchmarks with sparse reward functions. 

Under review as a conference paper at ICLR 2021
EXPLORE WITH DYNAMIC MAP: GRAPH STRUCTURED REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In reinforcement learning, map with states and transitions built using historical trajectories is often helpful in exploration and exploitation. Even so, learning and planning on such map within sparse environment remains a challenge. As a step towards this goal, we propose Graph Structured Reinforcement Learning (GSRL), which leverages graph structure in historical trajectories to slowly adjust exploration directions and rapidly update value function estimation with related experiences. GSRL constructs dynamic graph on top of state transitions the replay buffer based on historical trajectories and develops attention strategy on the map select an appropriate goal direction, which decomposes the task of reaching distant goal state into sequence of easier tasks. We also leverage graph structure to sample related trajectories for efficient value learning. Results demonstrate that GSRL outperform the state-of-the-ar algorithms in terms of sample efficiency on benchmarks with sparse reward functions.
INTRODUCTION
How humans learn solve tasks with complex structure and delayed and sparse feedback? Take a complicated navigation task as an example in which the goal is to go from start state to an end state. A straightforward approach that one often takes by decomposing this complicated task into a sequence of easier ones, identffyingfforming some intermediate goals that help to get to the final goal, and finally choosing route with the highest return among poll of candidate routes that lead to the final goal. Despite recent success and progress in reinforcement learning (RL) approaches (Mnih) jet al. 2013 Fakoor al. 2020 Hansen al.) 2018 Huang et al., 2019 Silver al. 2016), there still a huge gap between how humans and RL agents learn.
In many real-world applications, an RL agent only has access to sparse and delayed rewards, which by itself leads to two major challenges. (C1) The first one is how can an agent effectively learn from sparse and delayed rewards? One possible solution is to build new reward function, known as an intrinsic reward, that helps expedite the learning process and ultimately solve a given task. Although this may seem like appealing solution, is often not obvious how to formulate an effective intrinsic reward. Recent works have introduced goal-oriented RL (Schaul et al. 2015 Chiang et al., 2019) as way of constructing intrinsic rewards. However, most goal-oriented RL. algorithms require large amounts of reward shaping (Chiang et al.) 2019) or human demonstrations (Nair al. 2018 (C2) The second issue how retrieve relevant past experiences that help to learn faster and improve sample efficiency. Recent attention has focused much on episodic RL (Blundell et al., 2016), which builds non-parametric episodic memory to store past experiences, and thus can rapidly latch onto related ones through search with similarity. However. most episodic RI. algorithms require additional memory space (Pritzel al., 2017).
In this work, we propose Graph Structured Reinforcement Learning (GSRL), which con- structs transitionn graph, leverages struc- tural graph information, and presents solutions for the problems raised above. As shown in Fig- ure [ when we encounter complex task, we draw a map for planning with a long horizon (Eysenbach et al. 2019) and scan through the graph to seek related experiences within a short horizon (Lee et al. 2019).
whew the reperviics
Goel Geneevation
g
massrrd
Cearn Ehe
Co
V
Ensironsment
wher the somple selecied berad bf
Value Edtrvction
Figure 1: An illustration for motivation of GSRL.

---

Under review as a conference paper at ICLR 2021
intial//eminal state
explored state
gool state
current state
transition
groph structured stotes
updote
Temmnna riasa
explonadatate
(a)
(b)
cirrent Hote
ferminal stose
INTAE CUTT
(d))
Figure 2: GSRL allows joint optimization of map construction and agent exploration from scratch. (a) An agent is located at the initial state and aims at the terminal state with an empty map at the beginning. (b) The agent explores the environment and records the explored states on the map, (c) The agent generates goal from previous states to decompose the whole task into a sequence of easier tasks. (d) The agent updates current policy with related trajectories selected by structured map information.
Inspired by this, we propose a method to address the first problem (C1) by learning to generate an appropriate goal ge based on map 9 at episode and form the intrinsic rewards during goal generation. This goal generation can be optimized in hindsight. That is, we can update the goal generation model under the supervision generated by planning algorithms based on map 96-1 at episode e + 1. We can solve the second problem (C2) by updating the value estimation of the current state with the trajectories that include neighborhood states. Note that GSRL draws map to help agents plan an appropriate direction in the long horizon and learn an optimal strategy in the short horizon, which be widely incorporated with various learning strategies such DQN (Mnih it al. 2013), DDPG (Lillicrap et al. 2015), etc.
However, arriving at a well-explored map in terms of state-transitions in the first place from scratch remains challenging problem. In this regard, GSRL should be able jointly optimize map con- struction, goal selection, and value estimation. As illustrated in Figure [ following four steps: (a) At the beginning, an agent is located at the initial state and aims at the ter- minal state with an empty map: (b) The agent then explores the environment with the current policy and records those explored states on the map: (c) Considering the far distance to the terminal state and sparse reward during the exploration, we decompose the whole task into sequence of easier tasks guided by goals; (d) We leverage structured map information to select related trajectories to update the current policy; The agent can repeat procedures (b)-(d) and finally reach the terminal state with a well-expli well-explored map.
we design GSRL mainly
Our primary contribution is novel algorithm that constructs dynamic state-transition graph from scratch and leverages structured information to find appropriate goal in goal selection with long horizon and sample related trajectories in value estimation with a short horizon. This framework provides several benefits: (1) How to balance exploration and exploitation is fundamental prob- lem in any reinforcement learning (Andrychowicz et al.] 2017) Nachum et al.) 2018). GSRL learns an attention mechanism on the graph to decide whether to explore the states with high uncertainty or exploit the states with well estimated value. (2) Almost all the existing reinforcement learning approaches (Paul al. 2019; Eysenbach et al. 2019) utilize randomly sampled trajectories to up- date the current policy leading to inefficiency. GSRL selects highly related trajectories for updates through the local structure in the graph. (3) Unlike previous approaches (Kipí et al. 2020 Shang et al. 2019). GSRI. constructs a dynamic graph through agent exploration without any additional object representation techniques and thus is not limited to several specific environments. Empir- ically, we find that our method constructs a useful map and learns an efficient policy for highly structured tasks. Comparisons with state-of-the- RL methods show that GSRL is substantially more successful for boosting the performance of graph-structured RL algorithm.
2 PRELIMINARIES
Let M = (S, A, P. R) be an Markov Decision Process (MDP) where S is the state space, A is the action space whose size is bounded by constant, T Z4 is the episode length, P S A - A(S) is the transition function which takes a state-action pair and returns a distribution over states, and
R : S x A A(R) is the reward distribution. The rewards from the environment, called extrinsic,
2

---

Under review as a conference paper at ICLR 2021
usually sparse and, therefore, difficult to learn. To address this, goal-oriented RL introduces goal E G to build dense intrinsic rewards Rg x A x G + A ) order to make the learning procedure stable. the goal is limited to be updated episodically. A policy prescribes a distribution over actions for each state and goal. At each timestep. the agent samples an action the agent has reached the goal. The episode terminates only after ' timesteps even when the agent reaches the goal. The agent's ss task to maximize its cumulative discounted future reward. We use an off- policy algorithm to learn such a policy, as well as its associated goal-oriented Q-function and value function:
S G + (AA)
(s; g) and receives corresponding reward rg a) that indicates whether or not
= E
Σ 1=0
r (rg(a, 86) 8, a, (*(8. max Q" (8,
(1)
We use off- off-polliy algorithms named DQN (Mnih al. 2013) for discrete action space and DDPG Lillicrap et al.) 2015) for continuous action space to learn Q-functions and policies by utilizing off off-policy data (i.e., data stored in the replay buffer).
3 GRAPH STRUCTURED REINFORCEMENT LEARNING
As illustrated in Figure T GSRL constructs a dynamic graph on top of state transitions. However, learning and planning algorithms the state transition graph are non-trivial. In this section, provide a theoretical analysis to show that exploration without any constraint would lead to the explosion of the graph. In order to guide the exploration with directions, we develop novel goal- oriented RL framework which incorporates the structure information of the state-transition graph. Specifically, we first divide states into several groups according to their uncertainty and locations in the graph. We then adopt an attention mechanism to select an appropriate group and assign the state with the highest value the graph as a goal encourage further exploration. We also propose to update goal generation hindsightly and value estimation with related trajectories, to help RL agents learn efficiently.
3.1 EXPLORE WITH DYNAMIC GRAPH
We directly build a dynamic and directed graph using sample trajectories from the replay buffer. We denote the state-transition graph at timestep t in episode e by Gi =< Vi, Ef > with relations R2, the node space VE represents state space Sgr, edge space & represents action space Age, and relations R, represents transition Pgt- We denote the graph's boundary by 0g;, which consists of observed but not fully explored states. An illustrated example of these notations above is available at Figure 7 in Appendix A
Let an agent start from an initial state sn- Then GJ grows from single node (i.e., G = {so}) and T-1 t== where
expands itself at each timestep, leading to the sequence ((G)) Jt= (GP)T=) ..... (g.5
denotes episode length and E is the number of episodes. Given that state-transition graph Gj is always a connected directed graph, we describe the expansion behavior consecutive expansion, which means no jumping across neighborhood allowed. We denote the graph increment at timestep t in episode as AG;, and then
ensure that G; U AG; gi+1 G uag
Proposition 1. (adapted from (Xu et al. (0200) We assume that the probability of degree of an arbitrary state in the whole state-transition graph Guhute being less than or equal to is larger than p (i.e., ((de((s) < d) > p. Vs Sg). We then consider sequence of consecutively expanding T-1
sub-graphs ((91)T-) (G2)T-1 1t=0 .--.. (GF)T- T-1)) starting with go {so}, for all t ' 0, e 1.
We can ensure that P([S0; < pf, where d'(d-1) T)-et when d > 2 and = 1,3 when
d d=11 1,2 respectively.
Proof. The basic proof structure follows from (uu et al. 2020); however, because our task and detailed setting are considerably different, several modifications required described in in Ap- pendix D.I
The proposition implies that even if the given assumption of the whole state- tntte-transiton graph Gwhole has small d and a large p (i.e., sparse graph), the guarantee of upper-bounding [Sg; becomes looser and weaker as t, e get larger. other words, randomly appending Gi through exploration would enhance computation complexity for learning and plan the dynamic graph. In order to
3

---

Under review as a conference paper at ICLR 2021
prevent 9i from explosion, we need to constrain A9; by guiding exploration with goals. In this paper, we propose to leverage the graph structure to assist agent exploration. Before the detailed introduction of exploration strategy, we firstly introduce the definition of certainty as
Definition 1. Given a state s. we define its certainty as to the number of candidate actions that have been already taken. In this paper, we build the Halee-ransiiion graph 9 on the replay buffer and thus can adopt the out d each state to approximately measure the certainty. In other words, we can approximate the certainty of state cer((s) R deg(s), (s), where deg(s) demotes the degree of node 8.
Note that certainty of state in Definition I can be served as local measurement to show the extent of exploration on some states, which is actually proportioned to the global measurement (i.e., the number of visited states) in a deterministic environment (See Appendix E. for details). In addition. we also can define uncertainty of state as the number of untaken candidate actions.
Exploration Strategy. A simple but effective way is to do exploration based on goal-oriented RL., which decomposes the whole task into a sequential of goal-oriented tasks. In this case, newly explored states in each episode are guided by a specific goal. Therefore, we constrain the state- transition graph from the explosion and balance the exploration and exploitation through assigning an appropriate goal to the agent. In order to further discuss the definition of an appropriate goal, we here provide the definition of the optimal goal. As shown in Figure 4 once we are accessible to the whole state-transe transitraniiionn graph Gwhole. we can obtain the optimal solution by short path planning algorithm such as Dijkstra's 's Algorithm. We define the optimal goal as the terminal state on the path.
Definition 2. For fully explored state-transition graph Gaal we define the optimal goal Fult as the terminal state (e.g., $10 in Figure Ta)). For any not fully explored state-transiticn graph 9h we define the optimal goal g. hindsightly, where we generate the optimal solution path Pe+1 based on the shortest path planning on the next episode graph g and regard the reachable terminal state included both in 9ā and Pe+1 as ge. (e.g., 86 in Figure fc)).
One should be noted that the optimal goal is hindsight generated and keep approaching the terminal state during exploration. We further analyze and discuss the relations between goals in this paper and previous goal-oriented RL literature in Appendix E.2
Proposition Assume that Q-value of each state is well estimated (i.e.. Q = Q"), then optimal goal g. at the beginning timestep of any episode e is always included in the boundary of the state- transition graph 95 (i.e., 891))
Proof. The proof of Proposition 2 be found in Appendix D.2
The proposition implies that the candidate set for each goal generation can be limited to the boundary. However, learning to generate an ap- propriate goal is non-tn non-trivial with respect to a dynamic and large-scal state-transition graph G. One intuitive solution is to divide the whole candidate goal space (i.e., aG;) into several candidate groups CI...., CN. where N is the number of groups. In order to both cover all the states and control exploration size in these groups, our group segment should follow the principle that UN C, = ag; and Cm CC, = 0 for any m o n; m, n 1,2,...,
Cn
hop neighbors
n-uncertain
last explored state
Figure 3: An illustration of exploration strategy.
Here, we set the last visited state Slast in the previous episodes as Co. since Slast often is both close to the terminal state and has high uncertainty. As shown in Figure 3, based on the last explored state, we build group C,, n = NN...,NN by extending scales in two different perspectives. We list two perspectives, as follows:
Extending from Neighbor Nodes, One perspective is to leverage local structure on graph, where forn = 1, 2, , NN, and CN == ag; - -N C,, \ means
Cn :- {s), E n-hop neighbors of Stast. The intuitive motivation behind this is keep the learning procedure stable by slowly adjusting the goal to explore the surrounding environment.
* In this paper, we use 'degree" represent 'out-degree', unless otherwise stated.
We define the full explored graph Gon as the graph covering the optimal solution, and the whole graph Guhole as the graph covering all the state-transitions. Hence, we have that Gra is a sub-graph of Guhule (i.c., Fiil C Guhule).
4

---

Under review as a conference paper at ICLR 2021
Extending from Uncertain Nodes. The other perspective is to utilize certainty information to guide goal generation, where Cn == { S E -a n ag; for n = 1.2..... .N, and Cy := 0 - 1nn Sa=|d|=n denotes set of states whose degree equals IA|-n, and |A] is the size of action space. The intuitive motivation behind this is eliminate uncertainty in the graph through exploration.
We provide the complexity analysis for two perspectives follows. Let dag; denote the maximum degree of states in a and |S denote the number of states in àge. The complexity to construct ,CN by extending from neighbor nodes is (d and by extending from uncertain nodes is ((S )) The detailed analysis and method are available in Appendix E.3
Attention Strategy. One should be noted that extending from either neighbor or uncertain nodes can guarantee the number of groups .i.-..; CN on dynamic graph 9 is fixed. In order to keep all the groups not empty, we append 8tast to them at the beginning timestep of each episode. However, RL algorithms face an exploration-exxe exxllitttinoooiiiiiinnnnnn dilemma, which requires the agent to makes appro- priate selection rather than random exploration over these groups. In order to the trade-off between exploration and exploitation, we apply an attention mechanism to select an appropriate group on the current situation. For each group, we learn an embedding vector to represent its feature (i.e., cer- tainty for extending from uncertain nodes). In this paper, the attention module runs over N groups at each episode and select the appropriate one, which needs to take the features of other groups into consideration. Therefore, it's natural to adopt self-attention mechanism (Vaswani et al.] 2017) here. For simplicity, we structure embedding vector for each group and denote all the features of E Nxx The self-attention
groups as i fN], and then define Q = K = V == can be defined as
ATT (CI,.,, Cn) = softmax QKT
VN V
where ATT denotes self-attention function parameterized by G. The output of the self-attention is then fed to multi- layer perception (MLP) with ReLU activation function. The output of MLP is in the dimension R N x1 And the selected group can be obtained according to
CATT = arg max o (MLP MMLP(ATTACC......C.. C,,
(3)
where (-) denotes a sigmoid function, and CATT means the group selected according to the atten- tion score. At the beginning timestep of any episode e, we have access to state-transition graph Gā and its boundary aGi. We then divide agj into groups Ci...., Cv and obtain CATT through the aforementioned attention mechanism. We select one state with the highest value CATT as the
goal, which can be formulated
Ie arg max V(s ge-1
F Vs E CATT.
(4)
In this way, we can generate an appropriate goal gr. to guide the agent exploration in the episode e.
3.2 LEARN WITH GRAPH STRUCTURED REINFORCEMENT LEARNING
As illustrated in Figure D we update goal generation under supervised learning and value estimation under reinforcement learning. Specifically, we introduce learning strategies follows:
Goal Learning Strategy. As mentioned above, we learn the goal generation hindsight. As illus- trated in Figure 4 at the beginning timestep of each episode e + 1, we first compute the shortest path distance between initial state (su in (c)) and highest value state (sy in (c)) to obtain the solution path (Pe-1 = (Sg, $1, 83, S6, sy) in (d)). We then find the optimal goal 9 at episode e based on the solution path generated at episode + 1. Specifically, Pa+1 and ag; in the inverse order of the solution path. Given that 8g is unexplored and unreachable in the episode e, we select 86 as the optimal goal g-- We then find the optimal group C* that contains goal ge. With this hindsight supervision on the group selection, we are able to update the attention
search for the intersection state between
Similar (Andrychowicz et al. 2017) we relabel all the rewards when the goal changes. Therefore, (8,99e-1) is used here. 8 Note that we define the target state and the optimal solution path in episode + 1, and the optimal goal in episode e.
5

---

Under review as a conference paper at ICLR 2021
boundary of graph o5i
optimal path e+1
optimal ge
generated
Grall
Intil
(b)
96
estirnl 2 optiesis
96
Stalet spcired
(d)
Figure 4: Illustrations of optimal goals. States surrounded by red circles and connected by red arrows optimal solution path, which can be obtained by the shortest path planning algorithm the fully explored graph Gun in (a). When the graph is not fully explored (9 in (b)), we generate the optimal solution path hindsight, where we regard the state with the highest value in the next episode (9) in (c)) as the target state, and shortest path to it the optimal solution path (Pe+1 (Su, $1, $3, $6, 89) in (d)). We define the optimal goal g as the reachable target state in the optimal solution path in episode e (e.g.. 810 in Grall and 86 9)).
mechanism in Eq. 3) via a standard supervised learning algorithm, where the objective function can be formulated as
Tup (s....g.e'r))) [[c* -CATT) [|
(5)
where ||øl| is regularizer and a is the corresponding hyper--aramettr. This method updating goal generation under the supervision of the group instead of goal can eliminate instability brought from potentially inaccurate value estimation because our group division does not involve the result from value estimation.
Value Learning Strategy. With a generated goal at the beginning of each episode, we can build the critical block of our method, i.e., a goal-conditioned policy and its associated value function. We consider a goal-reaching agent interacting with an environment. The agent observes its current state & E S and a goal state g E G. The dynamics are governed by the distribution P(*++1|& a.). At every timestep, the agent samples ward rg (s, a) that indicates whether the agent has reached the goal. The episode terminates after T timesteps, and the agent reaches the goal. The agent's task is to maximize its cumulative and undiscounted reward. We use an off-policy algorithm to learn such a policy, as well as its asso- ciated conditond Q-function. For example, we obtain a policy by acting greedily, w.r.f,, the Q-function as
action
T[a)s,9) and receives corresponding
as), + (g(ss a) + max ((s.a'.9)
(6)
In order to improve data efficiency and obtain good value estimation, we consider choosing an off- policy RL algorithm with goal relabelling and update parameters with related trajectories. Specif- ically, we choose an off-policy RL algorithm with goal relabelling, such as (Andrychowicz et al.) 2017). We define related data those trajectories that contain neighborhood nodes of the current state. Formally, when we update Q-function of state s, we sample Dielated := {r} from replay buffer D. where denotes the trajectory that contains at least one state in s's neighborhood \ The Q-network is learned by minimizing the following objective function:
Lg Eis.a.g.s' Draned rateed
(Ta + max Qo a.g) g) - Qo(s, a. g))))² + 3 [101|]]
(7)
where 3 is the weight of the regularization term. Besides, as we show in Proposition algorithm can converge to unique optimal point if the Qllearnin strategy is adopted.
3 our GSRL
Proposition 3. Denote the Bellman backup operator in Eq. 6 as B R[SIx|AIx((] + || and a mapping Q : S x G + |2|Si|A|i((]] with |S| < oc and AA| < oc. Repeated applications of the operator B for our graph-based state-action value estimate Qg converges to unique optimal value Q3- with well-explored graph G* (i.e,, fully explored graph Gom)).
Proof. The proof is shown in Appendix D.3
Overall Algorithm. We provide the overall algorithm in Algorithm I in Appendix B and an il- lustrated example in Figure 8 in Appendix C One can that our state-trane transition graph can be

---

Under review as a conference paper at ICLR 2021
applied to both the learning and planning phase. Previous graph-based RL algorithms either focus on learning (Zhu et al. 2019) or planning [Eysenbach et al. 2019) based on structured information of the ttatettransitonn graph.
4 EXPERIMENTS
In this section, we perform an experimental evaluation of our algorithm and compare with other state-of-the- thrt methods. Our experiment environments are based on the standard robotic manipula- tion environments in the OpenAI Gym (Brockman et al. 2016). We provide the experimental results answer the following questions:
Can GSRL obtain better convergence in various environments?
2. Can GSRL tackle -igensiieenional and continuous environment with obstacles? Can GSRL perform higher sample efficiency?
4. What is the influence of group selection for goal generation and related experience for value estimation GSRL?
(4) Maze
(b) Maze
FetchPush
(d) FetchPush with Obstacle
Figure 5: Visualization of robotic manipulation environments.
In order to answer the first question, we demonstrate our method various robotic manipulation tasks including reach task (see Figure ((a) and fetch task (see Figure 5]c).. To answer the sec- ond one, we investigate how our method performs on environment with high-dimensional state and action space (see Figure (() and obstacle (see Figure d))). We answer the third one by compar- ison on the convergence of learning curves in Figure 6 By sample efficiency, we further analysis exploration performance in Appendix F55
Specifically, we conduct experiments with previous ap-
proaches:
HER: AAnrychhoicc et al. 2017 generated imaginary goals in a simple heuristic way to tackle the sparse reward issue.
MAP: Huang et al. (2019) explicitly modeled the environment in a hierarchical manner, with a high-level map abstracting the state space and low-level value network to derive local decisions.
GoaIGAN: Florenss et al. (2018) leveraged Least-Squares GAN (Mao et al. 2018b) to mimic the of Goals of Intermediate Difficulty as an automatic goal generator.
CHER: FFng et al. (2019) proposed to enforce more curiosity in earlier stages and changes to larger goal-proximity later.
One should noted that graph structure GSRL constructed on top of the replay buffer for goal generation and value estimation, which can be closely incorporated with policy networks such as DQN (Mnih al. 2013), DDPG (Lillicrap al., 2015), etc. To demonstrate gain from our GSRL, we set the policy network with DDPG for GSRL and all the baselines. The detailed description of cnvironments, experiment settings, and implementation details can found in Appendix F.1
real performance
Maze. We first test method and other strong baselines in the Maze environment, where the ant agent learns to reach the specified target position (e-ball depicted red) located at the other end of the U-turn shown in Figure a). This environment is quite simple, where most RL approaches can converge with a success rate 1. As Figure ((a) illustrates, GSRL performs with high sample efficiency.
AntMaze. We show that GSRL is efficient in complex environment of robotic agent navigation tasks, as illustrated in Figure bbb), where the state space is of & dimensions and the action space is of 30 dimensions. Duan al. (016) showed that standard RL methods are unable to solve it. As shown in Figure 6 b), GSRL achieves the best asymptotic performance and sample efficiency.
FetchPush. As shown in Figure c)., in the fetch environment, the agent trained to fetch an object from the initial position (rectangle in green) distant position (rectangle in red). Although

---

Under review as a conference paper at ICLR 2021
FetchPush
1.0
1.0
1.0
0.8
nare
0.8
sUicess
0.6
success
0.4
0.4
MEN
0.2
Goardnn CMb
HEh HAP
0.0
0.0
0.0
500
5000
7500
10000
2500
7500
10000
episode
episode
episode
(d) FetciPPush with Obstacle
(e) Complexity Size
(0 Complexity on Structure
1.0
1.0
SUCcess r3ee
0.8
0.8
0.8
0.6
0.6
0.4
0.2
G5RL HCR HAP
SMAL1
VESUUM
0.2
Naze
with
0.0
5.0
5000
7500
10000
500
1500
2500
5000
0.0
500
2500
5000 episode
7500
10000
egisode
[g] Group Selection
(h) Discretization
(0 Related Experience
1.0
1.0
1.0
SUCCess rate
0.8
SucCess ra5t
0.8
0.8
0.6
0.6
0.4
UNCERT2
UNCERT3
UNCERTA
06c0RST1220 926
06SCR2TE20
0.2
RELATED
NERGHO
D6SCRETE10
500
2500
5000
7500
10000
2500
5000
7500
1000X
500
2500
5000
7500
10000
spisade
episode
Figure 6: Learning curves of GSRL, HER, MAP, GoalGAN, and CHER on various environments
with 10 random seeds, where the solid curves depict the mean, the shaded areas indicate the standard deviation, and dashed horizontal lines show the asymptotic performance.
the fetch tasks are more complicated than they reach ones in the maze, GSRL also yields large performance gain, as shown in Figure Gcc.
FetchPush with Obstacle. As 3 d) illustrates, create an environment based on FetchPush with a rigid obstacle, where the brown block a static wall that cannot be moved. Experimental results in Figure d) suggests that the graph structure of state- transitinns can provide additional useful information, which leads to better guidance for goal generation and value estimation.
Impact of Environment Size. In order to investigate whether GSRL can be well adapted in the environments with different complexity sizes, we extend the Maze environment, shown in Fig- ure a). Maze environment with larger size usually means more sparse rewards. We report the performance comparisons the three environments with SMALL, MEDIUM, and LARGE sizes in Figure (c). More details of these environments are available in Appendix F.I. One can see that GSRL can be well address sparse reward issue in various environments.
Impact of Environment Complexity. In order to investigate whether GSRL can be well adapted in the environments with different complexity levels, we extend the Maze environment with a more complex high-dimensional structure. We create AntMaze with Obstacle environment, where we extend the AntMaze environment with an obstacle. The performance of GSRL in this environment illustrated in Figure ff.. More details of these environments are available in Appendix F.T One can see that GSRL can be well adapted in various environments with different complexity levels.
Impact of Group Selection. We provide two strategies to divide the boundary of the graph into sev- eral groups, namely extending from neighbor nodes and extending from uncertain nodes in Section R] We demonstrate the performance of these two strategies in Figure (gg.. We set GSRL without using the attention strategy on the groups as NOGroup. We adopt the first strategy and set the number of groups as 3, which corresponds to NEIGH3. We then show the performance of the second strategy with the number of groups equal to 2,3 and 4, which correspond to UNCERT2, UNCERT3 and UNCERT4. Results show that GSRL without any group selection would lead to inefficiency since the goal generation strategy at the beginning is almost random. Both of these two strategies perform well, as illustrated. We also provide complexity analysis in Appendix E.3 In the main experiment, we adopt extending from uncertain nodes with 3 groups (i.e., UNCERT3).
Impact of Discretization. We apply K-bins discretization technique (Kotsiantis & Kanellopoulos, 2006) to discretize the continuous state and action spaces, where there is wrapper that converts
8

---

Under review as a conference paper at ICLR 2021
Box observation into single integer. DISCRETEIO, DISCRETE20 and DISCRETE30 in Fig- ure h)) denote the performances of K = 10, 20 and 30 respectively. We find that for the simple tasks, the choice of K is not critical. K is set at 20 in the main experiment.
Impact of Related Experience. We further study the impact of using neighborhood structure of the state- tattetrranstion graph to select related experience to efficiently update value estimation. We build variant update value estimation from transitions drawn uniformly from the replay buffer DD denoted as ALL. RELATED is used to denote GSRL, where Drelated is adopted instead of D.
RELATED WORK
Structured Models of Environments. Recent work has investigated leveraging structured environ-
ments to make great strides in improving predictive accuracy (Kipf et al., 2018 Xu et al. 2019]
Chang et al., 2017 Battaglia et al. 2016: Watters et al.] 2017 Sanchez-Gonzale
et al.) 2018) and
accelerating reinforcement learning procedures (Shang et al. 2019 Kipf et al., 2020 Eysenbach
et al. 2019 Wang et al., 2018). These methods mainly first construct some form of graph neural network where node update functions model the dynamics of individual objects, parts, or agents and edge update functions model their interactions and relations through unsupervised object discovery (Xu et al.) 2019), contrastive learning (Kipf et al. 2020) or agent exploration (Eysenbach et al.] 2019). Unlike these previous works based on well-organized graphs, our model GSRL constructs and makes use of the graph from scratch. Specially, GSRL constructs a dynamic map via explo- ration and builds efficient exploration with structured information from this map, which allows our approach to be widely deployed into more complex environments.
Goal-oriented Reinforcement Learning. Goal-oriented RL allows an agent to generate intrinsic rewards, which defined with respect to target subsets of the state space called goals (Florensa al., 2018 Paul et al. 2019). Recently, goal-oriented RL has been investigated widely in various deep RL scenarios such as imitation learning (Pathak et al. 20018] Srinivas et al. 2018), disentangling task knowledge from the environment (Mao et al. [2018a] Ghosh et al. 2019). constituting lower-level controller in hierarchical RL (Shang et al. [2019] Nachum et al. 2018) and organizing cooperation in multi-agent RL (Jin et al.) 2019: Yang et al. 2020). Hence, how to generate appropriate goals is the essential technique in any poal-oriented RL (Andrychowicz et al. 2017: Ren et al.) 2019). Eysen- bach et al. (2019) proposed to utilize the shortest-par path search on replay buffer to generate sequence of goals. Instead of planning goals from a well-explored state-trane transition graph, in this paper, we in- vestigate guiding exploration with structured information from a dynamic graph, which can largely improve the performance in terms of sample efficiency in tasks with sparse reward signals. (Zhao) al. 2019) proposed to maximize entropy of selected trajectories; however, our method utilizes the structure information in the state- state-transition graph to select related trajectories for learning.
Hierarchical Reinforcement Learning. Hicrarchical RL learns a set of primitive tasks that together help an agent learn the complex task. There are mainly two lines of work. One class of algorithms (Shang et al., 2019: Nachum et al., 2018 Bacon et al., 2017 Vezhnevets et al. 2017) jointly learn a low-level policy together with level policy, where the lower-level policy interacts directly with the enviromment to achieve each task, while the higher-level policy instructs the lower-level policy via high-level actions or goals to sequence these tasks into the complex task. The other class of methods (Bagaria & Konidaris] 2019 Fox et al. 2017 Hartikainer et al. 2019: Pitis et al.) 2020) Pong et al. 2019) focus on discovering sub-goals that are easy to reach in a short time, or options which are lower-level control primitives, can be invoked by the meta-control policy. The common idea GSRL shares with Hierarchical RL is to decompose the complex task into several sub-tasks to achieve. In this paper, the key difference is that, we propose to build the state-transition graph and utilize the structure information for goal generation and value estimation.
CONCLUSION
In this paper, we propose a novel framework called GSRL, which leverages structure information of the state-transition graph for efficient goal generation and value estimation. We provide theoretical analysis to show the efficiency and converge property of our method. Results on various challenging robotic manipulation environments demonstrate that GSRL can outperform the state-of-the-as RL algorithms. In the future, this work would shed light on graph-structured RL for efficient learning and planning, where various graph-based algorithms can help RL agents learn and infer in highly structured environments.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Picter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In NeurIPS, 2017.
Puerre-Luc Bacon, Jean Harb, and Doina Precup. The option-critt architecture. In AAAI, 2017.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining, In ICLR, 2019.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In NeurIPS, 2016.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In NeurlPS, 2016.
Richard Bellman. Dynamic programming. Science, 1966.
Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wienstra, and Demis Hassabis. Model-free episodic control. arXiv, 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, arXiv preprint (60..06600005400 2016.
Michael B Chang, Tomer Ullman, Antonio Torralba, and Joshua B Tenenbaum. A compositional object-based approach learning physical dynamics. In ICLR, 2017.
Hao-Tier Lewis Chiang, Aleksandra Faust, Marek Fiser, and Anthony Francis. Learning navigation behaviors end-to-end with autorl. RA-I, 2019.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In ICML, 2016.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search the replay buffer: Bridging planning and reinforcement learning. In NeurlPS, 2019.
Rasool Fakoor, Pratik Chaudhari, and Alexander J Smola. P3o: Policy-on policy-off policy opti- mization. In UAI, 2020.
Meng Fang, Tianyi Zhou, Yali Du, Lei Han, and Zhengyou Zhang. Curriculun-guided hindsight experience replay. In NeurlPS, 2019.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In ICML, 2018.
Roy Fox, Sanjay Krishnan, Ion Stoica, and Ken Goldberg. Multi-level discovery of deep options. In arXiv, 2017.
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal- conditioned policies. In ICLR, 2019.
Steven Hansen, Alexander Pritzel, Pablo Sprechmann, André Barreto, and Charles Blundell. Fast deep reinforcement learning using online adjustments from the past. In NeurIPS, 2018.
Kristian Hartikainen, Xinyang Geng, Tuomas Haarnoja, and Sergey Levine. Dynamical distance learning for semi-supervised and unsupervised skill discovery. In ICLR, 2019.
Zhiao Huang, Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching, In NeurIPS, 2019.
Jiarui Jin, Ming Zhou, Weinan Zhang. Minne Li, Zilong Guo, Zhiwei Qin, Yan Jiao, Xiaocheng Tang, Chenxi Wang, Jun Wang, et al. Coride: Joint order dispatching and fleet management for multi-scale ride-hailing platforms. In CIKM, 2019.
10

---

Under review as a conference paper at ICLR 2021
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang. Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In ICML, 2018.
Thomas Kipf, Elise van der Pol, and Max Welling. Contrastive learning of structured world models. In ICLR, 2020.
Sotiris Kotsiantis and Dimitris Kanellopoulos. Discretization techniques: A recent survey. GESTS International Transactions Computer Science and Engineering, 32(1):47-58, 2006.
Su Young Lee, Choi Sungik, and Sae-Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. In NewrlPS, 2019.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Frez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv, 2015.
Jiayuan Mao, Honghua Dong, and Joseph J Lim. Universal agent for disentangling environments and tasks. In ICLR, 2018a.
Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley. On the effectiveness least squares generative adversarial networks. IEEE transactions on patlern analysis and machine intelligence, (1(22)2997-2290, 2018b.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv,, 2013.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In NeurIPS, 2018.
Ashvin Nair, Bob McGrew, Marcin Andrychowicz. Wojciech Zaremba, and Pieter Abbeel. Over- coming exploration in reinforcement learning with demonstrations. ICRA, 2018.
Georg Ostrovski, Mare Bellemare, Aaron van den Oord, and Rémi Munos. Count-based explo- ration with neural density models. arXiv, 2017.
Deepak Pathak, Parsa Mahmoudieh, Guanghao Luo, Pulkit Agrawal, Dian Chen, Yide Shentu, Evan Shelhamer, Jitendra Malik, Alexei A Efros, and Trevor Darrell. Zero-shot visual imitation. In CVPR Workshops, 2018
Sujoy Paul, Jeroen Vanbaar, and Amit Roy-Chowdhury. Learning from trajectories via subgoal discovery. In NeurlPS, 2019.
Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In ICML, 2020.
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew- fit: State-covering self-supervised reinforcement learning. arXiv preprint #rXiv:190300369) 2019.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adria Puigdomenech, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In ICML, 2017.
Zhizhou Ren, Kefan Dong, Yuan Zhou, Qiang Liu, and Jian Peng. Exploration via hindsight goal generation. NeurlPS, 2019.
Alvaro Sanchez-Gonnzllzz Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks learnable physics engines for inference and control. In ICML, 2018
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In ICML, 2015.
Wenling Shang. Alex Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Learning world graphs accelerate hierarchical reinforcement learning. In ICML Workshop, 2019.
11

---

Under review as a conference paper at ICLR 2021
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 2016.
Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal planning networks. In ICML, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. NeurIPS, 2017.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In ICML, 2017.
Tingwu Wang, Renjie Liao, Jimmy Ba, and Sanja Fidler. Nervenet: Learning structured policy with graph neural networks. ICLR, 2018
Nicholas Watters, Daniel Zoran, Theophane Weber, Peter Battaglia, Razvan Pascanu, and Andrea Tacchetti. Visual interaction networks: Learning physics simulator from video. In NeurlPS, 2017.
Xiaoran Xu, Wei Feng, Yunsheng Jiang, Xiaohui Xie, Zhiqing Sun, and Zhi-Hong Deng. Dynam- ically pruned message passing networks for large-scale knowledge graph reasoning. In ICML, 2020.
Zhenjia Xu, Zhijian Liu, Chen Sun, Kevin Murphy, William T Freeman, Joshua B Tenenbaum, and Jiajun Wu. Unsupervised discovery of parts, structure, and dynamics. ICLR, 2019.
Jiachen Yang, Alireza Nakhaei, David Isele, Kikuo Fujimura, and Hongyuan Zha. Cm3: Coopera- tive multi-goal multi-stage multi-agent reinforcement learning. In ICLR, 2020.
Rui Zhao, Xudong Sun, and Volker Tresp. Maximum entropy-regularizzed multi-goal reinforcement learning. In ICML, 2019.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In ICLR, 2019.
12

---

end for Under review as a conference paper at ICLR 2021
A
NOTATIONS
9i
neighborhood state
explored state
9 graph timertep
9
graph at timestep
tranation
fanika GOO
boundory
AGT
graph increment
denote
3x?
2x?
2x?
explored tmapppp!
(e)
Agi
ox?
2 2x?
G7+1
Figure 7: An illustrated example of notations in Graph Structured Reinforcement Learning (GSRL).
In this paper, we construct a tratestranstion graph on top of the replay buffer. As Figure Za) shows, build the graph 9f based historical explored trajectories at timestep t in episode For any not fully explored state-transition graph, there exist many poorly-explored states. We measure the exploration (i.e., certainty in Defintion 1 of these states according to the number of their untaken candidate actions. As illustrated in Figure b)) we define the boundary of G as a set of states, at least one of whose candidate actions is not readily taken. Each untaken action may lead unvisited states (denoted by icon). We denote the boundary as dgr. As illustrated in Figure Fc)) after each timestep t 1, the agent explored new state denoted as Ag, Then, G and Ag; together make up the dynamic graph at timestep t + denoted as G
B ALGORITHM
Algorithm Graph Structured Reinforcement Learning (GSRL)
1: Initialize replay buffer D = {5o) and state-trainsition graph G = =(s0)
2: for epsiode number e 1,2,... ... E do
3: Select an appropriate group for exploration according to Eq.
4: Generate goal 9. according to Eq. 4 for timestep t = 0, 2. Receive observation 8; from environment
5:
do
6:
7:
0t +- e-greedy policy based on Q(s,, a,
8:
Take action a,, receive reward r; and next state 8t+1 Append (st, de, Tz, S141, 9e) to D
9:
10:
Relabel rewards ry with ge
11:
Append (st, dee $1+1)
if (st, ag, 8141) & & f mod update interval = then
12:
Sample related experience (st, ats 814 1, Tt, ge) to Drelated Update parameter 0 using Eq. 7
14:
end
16:
Compute optimal goal gå according to Definition
18:
Update parameter é using Eq. (5)
end for
We provide the overall algorithm in Algorithm I The key contribution of our paper is leverage structured information in the state-transithe transition graph for efficient goal generation and value estimation, which is represented in line 4ad [3] respectively. We then describe the overall procedure of GSRL
according to Algorithm| aas follows:
There is no graph structure for the agent to support when the task starts. Hence, the agent initializes the replay buffer D and the state-transition graph in line T At the beginning timestep of each
13

---

Under review as a conference paper at ICLR 2021
episode e, divide the boundary of the state-transition graph age into N groups and adopt atten- tion mechanism to select an appropriate one for exploration in line Within the selected group, we choose the state with the highest value the generated goal g. in line 4 The agent tries to reach the goal state through current policy-based Q value in line 7 and record interaction history in the replay buffer in line As goal-oriented RI. provides the agent intrinsic reward conditioned the current goal, the agent is required to relabel reward with T, conditioned on Ie in line IO Then the agent updates the state-transition graph in line I1 In order to efficiently update policy, the agent sample related trajectories that contain at least one neighbor states of the current state in line [3] In line [4] the policy is updated with DDPG (Lillicrap al., (015). At the end of each episode e, the state-transition graph is actually built for episode e denoted as 9 The agent is able to find optimal goal De through planning algorithm on 90+1 in line 17 The attention mechanism is updated by supervised learning line 18
C ILLUSTRATION
56
Construction
Space
Space Discrelaniion
Space
Ietial rarte
Grosp Doitdon
Replay Buffer
Fast Sorte
Gool coli--neeeeell Exploration
ge
Value Network
Attentian
boundary of graph ig?
generated gool g explored stote
beginsing dreetip cabode
Figure 20d)
Figure 4(d)
Figure& 8: An illustrated example of Graph Structured Reinforcement Learning (GSRL).
We provide an illustrated example for GSRL in Figure g When an agent encounters a complex environment, GSRL first discretize the continuous space into a discrete one, as illustrated in (a). We color the last state (i.e., Slast = 37) visited in the previous episodes with red. Mcanwhile, the historical trajectories stored in the replay buffer can be represented with several paths (e.g., (So, $1, $3, s6)). With these paths, we can easily construct state-transition graph at the beginning timestep of episode (i.e., 98). As illustrated in (b), we can find the boundary of the graph (i.e., ög;) as shown in Appendix [ In this case, 85, are in the boundary of the current graph (i.e., 0GE). We then follow extending from uncertain nodes to divide the boundary into several groups. The number groups is the hyper-parametees and we choose 3 here. For each group, is often with high value and close to the terminal state. As shown in (c), we then adopt attention mechanism to select one group CArT and assign the state with the highest value in the sclect group as the goal Je- With the generated goal, the agent can perform goal-oriented exploration to divide the complex task into several sub-tasks to deal with. There two learned parts in GSRL, namely attention network for goal generation, and value network for value estimation. We design a hindsight learning approach update the attention network at the beginning timestep of each episode (as shown in Figure 4h, and use related experiences to update value network at each update interval (as shown in Figure
include Slast since 8last
D PROOFS
D.I PROOF OF PROPOSITION
Proposition 1. (adopted from (uu al. 20200) We assume that the probability of degree of an arbitrary state in the whole state-transition graph Gunote being less than or equal to d is larger than
p (i.e., Pdde((s) < d) > p. Vs E Sz). We then consider sequence of consecutively expanding
sub- sub-graphs (191) ( (-)) ...., { T
[ starting with G {50},, for all 2 e 2 1.
We can ensure that P([Saş) S t) pf, where d'id T.ett when and 1,3 when
d-2
d 1,2 respectively.
14

---

Under review as a conference paper at ICLR 2021
Deresied
[d
Figure 9: An illustrated example of the proof of Proposition and the key difference between the proposition in this paper and the one the previous work.
Proof. In (Xu al. 2020), the new node of the current graph (i.c., 96) can be sampled directly from the neighborhood. As illustrated in Figure considering the graph in this paper is the state-transition graph, we can not directly sample from the neighborhood. We only can obtain the new states by the explored trajectories (e.g., (Su. $1, S3, $6, 8o) in Figure 9 Therefore, we propose to consecutively
expand the sub-graphs at the timestep level (i.e., {(9) [[G]]=- I- 1.m... [GG) - ..... ) ). starting with
S. = }s Although we follow the framework in (Xu et al. 2020 several modifications are required. And, we provide the detailed proof as follows:
We consider the extreme case of greedy consecutive expansion at each timestep in any episode e, where + = 9 Ag; = G äg;, since if this case satisfies the inequality, any case of consecutive expansion
also satisfy it. By definition, all the subgraphs Gf are a connected graph. Here, we use A.5" to denote Sag for short. In each episode, we can ensure that the newly added nodes AS; at timestep only belong to the neighborhood of the last added nodes AS;;
Within each episode length. In this case, each node in AS; already has at least one edge within Ag; due to the definition of connected graphs. We can have
study the sequence {AGs. AGf..... - where T is the episode
P(IASTI S A (d 1)) 1487 21.
(8)
For 1 and f = 0, we have P(IAS) S d) and thus
P[ S 1 + d) > p-
(9)
For 2 1 and t 2 1, we analyze the conseutive expansion of the state- -tate-transition graph G as
g¹_ g² + g
G G +... - + 0 -
G1
GE
(10)
Given that A 2 1, E [0, - 1], we consider the extreme case that A = 1, v e
[0, T - 1], which means that every exploration will result in new explored state and should be
respondes the upper bound of the explosion. Based on ASg;
+
AS + | + +..
AASg;_, +AS |ASg3 ....... |AS9; ....+ A g0
A Sgrl have
P([Sge1 < 1 + d+ d. (d 1) +) +... d (d- (d-1)eottr-) 1) > Idd+ 1)4 4
(11)
When d = 1, there can be only one node, so in this case, = 1. When d = 2, we follow Eq. and derive that this case, e 3. When 2, holds that
(1)
P([Sge < d- (d 1 - 2 d: T
p
(12)
We can find that f also satisfies this inequality.
D.2 PROOF OF PROPOSITION 2
Assume that Q-value of each state is well estimated (i.e., Q Q"). then optimal goal gt at the beginning timestep of any episode e is always included in the boundary of the state- transition graph G5 (i.e., (
Proposition 2.
Proof. According to Definition 2 as shown in Figure a). in the fully explored graph Gtan- the optimal goal Fin is the terminal state in the optimal solution Prun. which is also the terminal state
15

---

Under review as a conference paper at ICLR 2021
boundary of groph d5?
optimal solution path Pa c+1
optiomal gool g
generated gool
Srall
9
Gerescal
inbalabblc
(b)
90
00 aptraci
56
goalla Apliode
(d)
Figure 10: An illustrated example of the relationship between optimal goal and boundary. In the fully explored graph Grm. the red circled states together show the optimal solution path (Prull (50, 81, 83, 8c, 89, 810)) with terminal one (810) for the optimal goal in (a). In any other not fully explored state-transition graph O at the beginning timestep of any episode e in (b), regard the reachable state in the dashed line circle (s6) through planning in the next episode 9 in (c) the optimal goal in (d).
in the environment (i.e., $10). The intuitive explanation behind this is very natural, where the en- vironment in this case fully explored, and thus the agent is ready to target at the terminal state. In the other cases, we generate the optimal goal D.a of episode at the episode + 1. Specially, we find the shortest path to the highest value state in 95+1 as the optimal solution path Pe+1. As Figure 10 illustrates, the episode + the highest value is 8y and the optimal solution path in this case is Pe++ = (so. S1, $3, Sc, sg). We then compare the explored states in 9i with the states in Pett" where Pet1 (s9, 86, 83, 81,80) is the inverse order of Pe+1. As Figure I0 shows, finally we obtain 88 as the optimal goal g². As stated above, it's easy to find that there are two cases in the optimal goal generation. One is the last node of solution path Pe+1- The other is one of the rest nodes in Pe+1 except the last one. We then prove that in both of these cases, optimal goal g is always included in the boundary of the state-transition graph a9i-
Case I: Node at Last. If Q-value of each state is well estimated, i.c., Q = Q", then the optimal solution path P.+1 episode e ++1 +1 should be close to the optimal solution path Prun in the full graph Gim and the last state of the path Pe+11 should be closest to the terminal state. Hence, if g. is not in the boundary, there must be one neighbor node closer the terminal state. Otherwise, g. is the dead end and thus should not be regarded as the optimal goal. And if there is one neighbor node closer to the terminal state, then this state should be regarded the optimal goal. Therefore, we obtain contradiction.
Case I:: Node Not at Last, If the optimal goal is not the last state, then there must exist the state unexplored at episode e. Take Figure 10 as example, if we take se as the optimal goal 9e in (d), state 89 must be unexplored in 96 in (c) and explored in g8+1 in (b). If ge is not included in agg. then there should not exist any unexplored state that is included in its neighborhood. According to the definition of the boundary of the graph, we have proved the proposition by contradiction.
In summary, we have proved the proposition in both two cases by contradiction.
D.3 PROOF OF PROPOSITION 3
Proposition 3. Denote the Bellman backup operator in Eq. 6 as B RISIX|AIXIII - | and a mapping Q S A G + | with |S| < oc and A| <c. Repeated applications of the operator B for our graph- based state-action value estimate Qg converges to a unique optimal value Qi- with well-explored graph g* (i.e. fully explored graph Gaa) including optimal solution path.
oc.
Proof. The proof of Proposition done in two main steps. The first step is to show that our state- transition graph can converge to the well-explored graph G*_ Here, define G* the graph that includes the optimal path (i.c., Pra in Definition 2). In the second step, we prove that given graph 9, our graph method can converge to unique optimal value Qz
16

---

Under review as a conference paper at ICLR 2021
and |A| < oo, state-trane taatettransttonn graph 9 is a dynamic graph, and goals g generated on G are updated at the beginning timestep of each episode. Hence, there is sequence of goals denoted corresponding sequence of graphs denoted as (G), 9 ... - where E here is the number of episodes. Given that |S| oo and |A| co, the number of nodes and edges in the full graph Gra is also bounded. Based on the explore strategy introduced in Section 3 we know that goal-oriented RL will first search for a path leading the terminal state. After that, the terminal state will be included in g. Then the agent will seek the shortest path to the terminal state because the agent is given negative reward each timestep. Hence, the optimal solution path Piun will be involved. Hence, we can obtain that
Step I. Since |S|
obtain that Vg
and Eg < Note that the
.9x) 191.92.... and
go 0 C .... g = G G
(13)
Assume that E is large enough, our state-transition graph G can finally converge to well-explored graph g*.
Step II. Note that the proof of convergence for our graph-based goal-oriented RL is quite similar to Q-learning (Bellman 1966. Bertsekas] 1995; Sutton & Barto (018). The differences between our approach and Q-learning are that Q value ((s, a, g) is also conditioned on goal g. and that the state-transition probability (s a) be reflected by graph G. We provide detailed proof as follows:
For any state-transition graph G, we can obtain goal g E G conditioned on & from Step Based on that, our estimated graph-basen action-valus function Qg can be defined as
BQg(s, a) = R(s, g, + +
max a'EA
Po(s'(s,,)) Qo(s',
(14)
#'ES
For any action-value function estimates Qg. Lg. we study that
(8 a) - Bs,
Σ
Po(s''s,,)) Q3 d'
E Po(''(s,
= max d'EA
max
a'EA
s'ES
Σ Pg(5'ls, Q ,' Σ Po(s'(s,a)- 18 a. s'ES
$ y max d'EA
(15)
S'ES
Σ Po(s'(s,a) ( ,) (s'.''''.
=Y max e'
(3, a. as,
eES,aEA
So the contraction property of Bellman operator holds that
(8Q)(s, a, BQ] a) S T eES,aEA
( -g((,,,,))) (16)
max
max
For the fixed point Qi. we have that
max [BQa(s,0,9) BQ ST max aES,
1do(s, (' -(((:a)))) Qs Qg.
aES,0EA
(17)
Combining Step I and II, we can conclude that our graph-based estimated state-action value Qo can converge to a unique optimal value Qū...
E DISCUSSIONS
E. DISCUSSION ON CERTAINTY OF STATE
In this section, we further discuss the relationship between the certainty of state and the number of states. In the previous exploration RL literature (Ostrovski et al. 2017 Bellemare al.) 2016). the performance of exploration often is measured by the number of the visited states. Namely, given fixed number of episodes, more visited states, better performance. In this paper, propose to utilize a new measurement, i.e., certainty of state as illustrated in Definition [ We conclude the relations between certainty and the number of visited states as Proposition
17

---

Under review as a conference paper at ICLR 2021
Stull
Srull
ictie Chite
Figure 11: An illustrated example for relationship between certainty and number of visited states.
Proposition 4. Given a whole state-transitie graph Guhole. we can regard the certainty of states as the local measurement and the number of states as the global measurement for exploration, which share a similar trend during agent exploration.
Proof. We illustrate and prove the proposition hindsightly. If we have the full observation for states as shown in Figure [a), a). we can model the agent finding new states as connecting new states with visited states. In other words, since the state-transition graph Gi must keep being fully connected graph at any timestep in any episode e. Hence, adding new states into the visited state set can always be regarded as finding new edge between new states and the visited state set. And each directed edge in the state traeetrannstton graph, as shown in Figure (T]bb is determined by action and Sate-transition function. If the environment is determined, we can roughly regard the number of edges as the approximate measurement for exploration. The certainty of states is the local perspective for this measurement.
E.2 DISCUSSION ON OPTIMAL GOAL
In the previous goal-oriented RL literature (Andrychowicz et al. [017 Ren et al. 2019). what kind of generated goals is helpful for the agent to efficiently learn a well-performed policy is one of the key questions to be answered. The basic idea of goal-oriented RL architecture is to generate goals to decompose the complex task into several goal-oriented tasks. In this paper, we analyze our generated goals from two perspectives, namely reachability and curriculum.
Reachability. The first property required in the optimal goal is that the generated goal is guaranteed to be reachable for the agent. To this end, in this paper, the candidate goal set is constrained into the visited states. In other words, the goal generated in the episode e must be visited before the episode e. Therefore, we can guarantee that the generated goal is reachable.
The second property is the curriculum, which means that our optimal goals are re- quired to approach the terminal state during the exploration. If the Q-value of each state is well es- timated, our goal generation under the supervision of forward-looking planning at the next episode will focus the potential highest value states in the future, which is actually the terminal state when the agent has the full observation of states.
Curriculum.
E.3 DISCUSSION ON GROUP DIVISION
Motivation. The intuitive motivation behind the group division very natural. Proposition that exploration on the state-transition graph G; at timestep / in episode without any constraint may lead to explosion of graph and inefficiency of exploration. Therefore, the agent is expected to do exploration within limited domain. Considering that G is always changing and the number of nodes (i.e., [Sgee] \) keeps increasing, is non-trivial for the agent to learn to select state as the goal for further exploration. Hence, we first restrict the exploration within the boundary of transition We then consider partitioning ag; into several groups.
graph ag; according to Proposition 2
We set the last visited state flust as the original point because $iss is likely to be close to the target state and reachable for current policy. As introduced in Section 3 we propose extend groups from Stat following two possible perspectives, namely neighbor and uncertain nodes.
Complexity. Let dags denote the maximum degree of states in ag;, and |Sage denote the number of states in Ögg- Note that ag; is always directed fully connected graph. If we want to find the n- hop neighbors of Stast, we need to iteratively go through related nodes' neighborhood. In other words, the computation complexity should be O(d'g))) Hence, the complexity to construct Ci,..., Cv by extending from neighbor nodes is Oddpsg) + Odhag)) + + Odd Old 1). If we want to find nodes whose uncertainty equals n, we need go through the graph once. In this case,
18

---

Under review as a conference paper at ICLR 2021
the computation complexity should be ( (). Hence, the complexity to construct Cı,..., CN extending from uncertain nodes is ([
EXPERIMENTS
F.1 ENVIRONMENT CONFIGURATION
(x) Maze
(b) Ant Maze
( FetchPush
(d) FetchPush with Obstacle
Figure 12: Visualization of robotic manipulation environments.
Maze. As shown in Figure 12 in the maze environment, point in 2D U-maze aims to reach a goal represented by a red point. The size of maze is 15 15, the state space and in this 2D U-maze, and the goal is uniformly generated on the segment from (0, 0) to (15.0, 15.0). The action space from (-1.0, -1.0) to (1.0, 1.0), which represents the movement in x and y directions.
AntMaze. As shown in Figure b), the AntMaze environment, an ant is put a U-maze, and size of the maze is 12 x 12. The ant is put random location the segment from (-2.0. -2.0) to (10.0, 10.0), and the goal is uniformly generated on the segment from (-2.0, 2.0) to (10.0, 10.0). The state of ant is 30-dimension, including its positions and velocities.
FetchPush. As shown in Figure 12 c), in the fetch environment, the agent is trained fetch an object from the initial position (rectangle depicted in green) to a distant position (rectangle depicted in red). Let the origin (0,0, 0, 0) denote the projection of the gripper's initial coordinate the table. The object is uniformly generated on the segment from (-0.0, -..0, 0) to (,,8,0) 0), and the goal is uniformly generated on the segment from (-0.0, 0..0, to (8, 8, 0).
FetchPush with Obstacle. As shown in Figure 12(d), d), in the fetch with obstacle environment, create an environment based on FetchPush with a rigid obstacle, where the brown block is a static wall that can"t 't be moved. The object is uniformly generated the segment from (-0.0, -0.0, 0) to (8, 8, 0), and the goal is uniformly generated on the segment from (-0.0, 0.0, 0) to (8, (8,8,0)
AntMaze with Obstacle. This environment is an extended version of AntMaze, where a x rigid obstacle is put in U-maze.
F.2
EVALUATION DETAILS
All curves presented in this paper are plotted from 10 runs with random task initialization and seeds.
The shaded region indicates 60% population around the median.
All curves are plotted using the same hyper-parameter (except the ablation section).
Following (Andrychowicz et al. 2017), an episode is considered successful if [|g - Sobjeal/2 S 6, achieved, where Sobject 1s the object position at the end of the episode. 8g the threshold.
The max timestep for each episode is set as 200 for training and 500 for tests.
The average success rate using in the curve is estimated by 102 samples.
F.3 SYPER-PARAMESS
Almost all hyper-parameterr using DDPG (Lillicrap et al. 2015) and HER Andrychowicz et al. (017)) are kept the same as benchmark results, except these:
Number MPI workers:
Actor and critic networks: 3 layers with 256 units and ReLU activation;
Adam optimizer with 5 x 10-4 learning rate;
Polyak-averagee averaiigg coefficient: 0.98;
Action L nonor penalty coefficient: 0.5;
Batch size: 256;
19

---

Under review as a conference paper at ICLR 2021
Probability of random actions: 0.2;
Scale of additive Gaussian noise: 0.2;
Probability of HER experience replay: 0.8;
Number of batches to replay after collecting one trajectory: 50.
in goal generation:
Adam optimizer with 1 x 10 learning rate;
K of K K-bins discretization: 20;
Number of groups to depart the graph: 3.
F.4 IMPACT OF GROUP SELECTION
We provide a separate numerical table of asymptotic performance values besides Figure ((g) here, since the curves of all the models (GSRL and its variants) are close to each other.
Model
NOGroup
UNCERT2
UNCERT3
UNCERT4
NEIGH
Success Rate
0.98 + 0.03
0.98 + 0.02
0.99 + 0.02
0.97 = 0.03
0.97 0.03
Table I: Results of investigation on impact of group selection. Note that the success rate is limited between 0.00 and 1.00.
F.5 COMPARISON ON EXPLORATION
By sample efficiency, we show the comparisons according to the number of states visited and actions taken. other words, given the fix number of episodes, more unique states visited and actions taken usually denote the efficiency of exploration. We report the log files of GSRL and HER in Maze environment here at 10, 50, 100 episodes, which contain the number of visited nodes and actions taken.
Graph Structured Reinforcement Learning (GSRL)
episode 10
nodes: [22, 21, 11, 31, 42, 32, 41, 23, 43, 33, 44, 34, 13, 14, 15, 26, 25, 36, 35, 45, 16, 24, 37, 47, 38, 48, 46 12, 49,
59, 69, 79, 80, 78, 90, 89, 99, 109, 110, 100, 27, 28, 39, 50, 40]
number of nodes: 45
edges: [(22, 22). (22, 21), (22, 23), (22, 32), (22, 33), (22, 13), (22, 31), (22, 12), (21, 21), (21. 11), (21. 31), (21.
32). (21, 22). (11. 11), (11, 21). (11,
31). (31, 42). (31. 41), (31, 22). (31. 32) (31. 21). (42. 42). (42,
32). (42, 43), (42, 41), (42. 31), (32,
31), (32. 32). (32, 42), (32,
43), (32, 33), (32,
23). (32, 22) (41, 41).
(41, 31), (23, 22), (23, 23), (23. 32), (23, 34), (23, 33), (23, 24), (43, 32), (43, 43), (43, 42), (43, 33), (43, 44).
(43, 34), (33, 33), (33, 44) (33, 82), (33, 43), (33, 23), (33, 34), (44, 44), (44, 33), (44, 43), (44, 1.44,38 35), (44, 34)
[44, 45), (34, 43), (34, 33), (34, 34), (34, 24), (34, 35), (34, 44), (34, 45), (13, 18), (13, 14), (13, 23), (14,
15), (14, 25), (14, 14), (15, 15), (15, 26),
14), (15, 16), (26, 26), (26, 25), (26, 36), (26, 16),
37). (26, 27), (25, 26). [25,
00.520000 25). (25, 15), (25. 36), (36. 35), (36, 26), (36, 36), (36, 37) [36, 27). 1.......00 (35. 35).
(35, 45). (35. 26). (35, 34). (35.
25). (45. 35), (45, 44), (45, 45). (16. 26), (24. 35). (24, 34).
(24, 25), (37, 47), (37, 37), (37, 58) (37, 48), (47, 37), (47, 47). (47, 48), (47. 46). (38, 47), (38, 48), (38, 37)
[38, 49), (38. 28), (38. 39) (48, 38) (48,
448, 49), 47), (46, 46), (12, 11), 112, 21), (12, 23),
22). (12, 13), (49, 48), (49, 59) (49, 50) (59. 69) 669, 69), (69, 79), 179, 80), 179, 78), (79, 79). (79. 90), (80.
79), (78, 79), (90, 89), (89, 99), 199, 99), 199, 109), (109, 110), 1109, 109),
1109, 100), (110, 100), (100, 109).
(27, 36), (27, 27), 127. 38),
(28,
28)
38),
(39,
(39, 40),
(39. 39),
150,
39) 550, 40), (50, 50), 49),
(40, 39). (40, 50)]
number edges:
episode is: 50
nodes: [22, 21, 11, 31, 42, 32, 41, 23,
43.
33,
44, 34,
13,
14,
15,
26,
25,
36,
35,
45,
16,
24,
37,
47,
38,
48,
46, 12, 49
59, 69. 79, 80, 78,
90, 89, 99,
109,
110.
100,
27,
28,
39,
50,
40,
29,
30,
51,
57,
18,
19,
58,
68,
17,
60,
20,
67. 70.
71, 61]
number nodes: 60
adges: []22, 22), (22, 21). (22, 23), 122, 32). (22, 33) (22. 13). (22, 31), 122. 12). (22, 11). (21. 21). (21, 11), (21.
31), (21, 32). (21, 22), (21, 12). (11,
(11, 21). (11, 12). (11, 22), (31, 31), (31, 42). (31, 41), (31. 22). (31,
32), (31, 21), (31, 40), (31, 30), (42,
42), (42, 32).
(42, 43), (42,
41), 142, 31), (32,
31), (32, 32). (32, 42),
(32, 43), (32. 33), (32, 23), (32, 22). 132, 41), (32, 21), (41, 411, (41, 31), (41, 40), (41, 32), (23, 22). (23, 23),
(23, 32), (23. 34), (23. 33), (23. 24). (23. 13). (23. 14), 123. 12) (43, 32) (43. 43). (43. 42). (43. 33). (43, 44)
(43, 34), (33, 33), (33, 44), (33, 32), (33, 43), 133, 23) (33 34) (33, 22), (33. 42), (33, 24) (44, 44), (44.
33), (44, 43), (44, 35), (44, 34).
45),
(34,
(34. 34), (34. 24), (34. 35), (34, 44), (34. 45).
25). (13, 13), (13. 14), (13. 231. (13. 12), (18. 22) (13, 24) (14, 15), 114, 25), (1))))(144
(14, 14). [14, 24). (14, 13),
(14, 23), (15. 15), (15, 26), (15, 25),
(15, 16), 126. 26), (26. 25),
126. 36), (26. 16), (26. 37), (26, 27).
(26, 35), (26. 17), (25, 26), (25. 25). 125 15) (26. 36), 125, 24) 125, 35), (25, 16), 125, 34), (36. 35), (36, 28)
(36. 36), (36. 37),
27) 136
136
(36,
35)
26).
34)
36),
44), (35, 25), (35. 46), (35. 010.5.200
24). (45, 00066.000 35). (45. 44). (45. 45). (45. 46), 36), (45. 34),
(16. 26). (16. 16). (16.
27). (16, 17), (16, 15), (16, 25). 124, 35), (24, 34), 124, 25), (24. 24), 124
14), 124, 23)
124 15). (24, 33),
(37. 47), (37. 37). (37, 38).
48)
(37. 46). (37. 271, (47. 37),
47 (47.
481. (47.
(47, 38), (47. 58). (47, 57) (47, 96), (38. 47).4441111 (38. 48) (38. 37). (38. 49) (38. 28)
(38, 39), (38. 98), (38, 27)
(48, 38). (48, 48), (48, 49), (48, 57), (48, 47),
(48, 58),
(48, 59),
(46, 471,
(46, 46),
(46, 37),
(46, 45), (46,
20

---

Under review as a conference paper at ICLR 2021
36), (46, 35). (12. 11), (12, 21). (12, 23), (12, 22). (12, 13). (12. 12). (49, 48). (49. 59), (49, 50), (49. 39). (49.
49), (49, 60), (59, 69), (59, 59), (59, 48), (59, 50), (59, 60), (59. 49), 159, 58), (69, 69), (69, 79), (69. 78),
189, 80), (79, 80), (79, 78), (79, 79), (79, 90), (79, 68), (80, 79), (80, 69), (80, 80), (80, 90), (78. 79), (78, 78),
(78, 68), (78. 69). (78. 89), (90, 89), (90, 79), (90, 90), (89, 99), (89, 79), (99. 99), (99. 109). (109, 110), (109.
109), (109. 100), (110, 100). (100, 109), (27, 36), (27. 27), (27, 38), (27. 28), (27, 26). (27, 37), (27. 18). (27.
16), (27, 17), (28, 28), (28. 58), (28, 27), (28, 18), (28. 19), (28. 37), (28, 39), (28. 29), (39. 50), (39. 40), (99,
39), (39, 29), (39, 38), (50, 39), (50, 40), (50, 50), (50, 49), (50. 59), 150, 80), (50, 51), (40, 49), (40, 39),
(40, 50), (40, 40), (40, 51), (40, 41), (40, 29), (40, 31), (40, 30), (29, 30), (29, 39), (29, 29). (29. 19). (29, 28).
(30, 29), (30, 40), (30, 31), (30, 30), (30, 20): (30. 39), (51, 40), (57, 57), (57. 68), 157, 47), (57. 58), (57, 48)
118, 19), (18, 27), [18, 28 118, 18) [18, 17), (18, 29), (19, 28), (19, 19), (19, 18) [19, 30), (19, 29), (58,
48). (58, 59), (58. 57). (58. 59) (58, 49). (58, 47), (58, 67) (68. 69). (68. 78), (68. 791, (17, 17), (17. 18). (17,
28). (17, 16), (17, 27), (60, 50) 160, 60). (60, 49). (60, 70), (60. 61), (60, 59), 120, 19), (67.
67). (67, 58).
(70. 71), (70, 70), (70, 60). (70. 69),
71).
(71, 70), (61, 7011
number of edges: 336
episode:
nodes: [22, 21, 11, 31, 42, 32, 41, 23, 43, 33, 44, 34, 13, 14, 15, 26, 25,
36,
35,
45, 16, 24,
37, 47, 38, 48, 46, 12, 49.
59, 69. 79, 80, 78, 90, 89, 99, 109.
110.
100, 27, 28, 39,
60,
40,
29,
30,
51, 57,
18, 19, 58, 68, 17, 60, 20, 67. 70.
71, 61. 88, 87, 96. 106, 105,
104, 114. 115, 81, 77, 97. 107. 86,
98,
108,
95.
85,
94, 103]
number of nodes: 79
edges: [[22, 22), (22, 21), (22, 23), (22, 32), (22, 33), (22. 13), (22, 31), (22, 12), (22, 11), (21, 21), (21, 11), (21.
31), (21, 32), (21, 22), (21, 12), (21, 20), (21, 30), (11, 11), (11, 21), (11, 12), (11, 22). (31, 31), (31. 42). (31,
41). (31, 22), (31. 32). (31, 21). (31, 40),
(42, 42) (42. 32).
(42, 43). (42.
41). (42, 31).
33).
(32. 31), (32, 32), (32. 42), (32, 43), (32, 33), (32, 23), (32, 22), (32, 41), (32, 21), (41, 41), (41, 31), (41, 40),
(41. 32), (41, 42), (41, 50), (41, 30), (23, 22), (23. 23), (23. 32), (23. 34), 123 33), 123
24), (23, 13), 123, 14)
123, 12). (43. 32), (43, 43), (43, 42), (43, 53). (43, 44), (43, 34), (33, 331, (33. 44), (33,
32), (33, 49), (33,
28), (33, 34), (33, 22), (33, 42). (33, 24), (44, 44), (44, 33), (44, 43), (44, 35), (44, 34), (44, 451, (34, 43), (34,
(44,
33), (34, 34), (34, 24), (34, 35), (34, (34, 45), (34, 25), (34, 23), 113, 13), (13, 14), [13, 23), (13, 12),
(13, 22). (13, 24). (14, 15), (14, 25) (14, 14), (14, 24), (14, 13), (14, 23), (15, 15) (15, 26). (15. 25). (15. 14),
(15, 16). (15. 24), (26. 26). (26. 25). (26. 36). (26. 16). 126.
(26. 27), (26. 35). (26. 17). (26. 15). (25, 26)
(25, 25), (25. 15), (25, 36), (25, 24), (25, 35). (25, 16), (25. 34), (25, 14), (36. 35), (36, 26), (36, 36), (36.
37). (36, 27), (36, 46), (36, 47). (36, 45), (36. 25). (35, 35), (35. 45), (35, 26), (35. 34), (35, 36), (35, 44), (35,
25), (35, 46), (35, 24), (45, 35). (45, 44), (45, 45). (45, 48), (45. 36), (45, 34), (16, 26). (16, 16). (16, 27),
(16, 17), (16, 15), (16, 25), (24, 35), (24, 34), (24, 25), (24, 24), (24, 14), (24, 23), (24, 15), (24, 33), (24, 13),
(37, 47), (37. 37), (37, 38), (37, 48),
28),
36), (37. 46), (37. 27), (37, 26). (47. 37), (47, 47). (47, 48)
(47. 46). (47. 38), (47. 58). (47. 57), (47. 36). (38, 47), (38. 48), (38. 37), (38. 49). (38, 28), (38. 39). (38.
38), (38, 27). (38, 29), (48, 38), (48, 48), (48, 49). (48, 57), (48, 47), (48, 58), (48. 59). (48, 37), (48, 39). (46,
47). (46, 46), (46, 37), (46, 45). (46, 36), (46. 35). (12, 11), (12. 21), (12, 23), (12. 22), (12, 13). (12, 12).
(49, 48), (49, 59). (49, 50), (49. 39), (49, 49), (49, 60), (49. 58). (49, 40), (49. 38), (59, 69), (59, 59), (59, 48).
(59, 50), (59, 60), (59, 49), (59. 58), (59, 68). (59. 70), (69, 69), (69, 79), (89, 78), (89, 80), (69. 70), (69, 68)
(69, 59), (79, 80), (79, 78), (79, 79), (79, 90), (79, 68), (79, 88), (79, 89), (79, 69), (80, 79), (80, 69), (80.
80). (80, 90), (80, 89), (80,
(80. 70),
(78.
(78. 78), (78, 68), (78, 69). (78, 89), (78.
(78.
67). (78, 77), (78, 88), 190, 89). (90. 79), (90. 90). (90. 80). (89. 99), (89. 79), (89. 80) (89, 89). (89. 88).
(89, 90), (89. 78), (89, 98), (99. 99), (99, 109), (99. 88), 199, 69), 199. 98), (99. 100), (109, 110), (109, 109).
(109, 100), (110, 100), (100, 109), (100. 99), (27. 36), (27.
(27. 38), (27. 28), (27. 26), (27, 37), (27. 18).
(27, 16), (27. 17). (28, 28), (28. 58), (28, 27). (28. 18), (28. 19), (28. 37), (28, 39), (28, 29), (28. 17), (39, 50),
(39, 40), (39, 39), (39, 29), (39. 38), (39,
(39. 48), (39, 30), (50, 39), (50, 40), (50, 50), (50. 49), (50, 59)
(50, 60), (50, 51), (50, 61), (50, 41), (40, 49), (40, 39), (40, 50), (40, 40), (40, 51), (40, 41), (40, 29), (40.
31). (40, 30). (29. 30), (29. 39), (29. 29). (29. 19). (29, 28). (29. 18), (29. 40), (29. 38). (29. 20). (30. 29). (30.
40). (30, 31), (30, 30), (30, 20). (30. 39), (30. 19). (30, 21), (51, 40), (51, 51), (51, 60), (51, 50). (57, 57),
(57, 68), (57. 47), (57. 58), (57, 48), (57, 67). (18, 19), (18, 27), (18, 28), (18, 18), (18, 17), (18, 29), (19, 28),
(19, 19), (19. 18). (19. 30), (19. 29), (19, 20). (58. 48), (58, 58). (58, 57), (58. 59). (58, 49), (58. 47). (58, 67)
(58, 69). (58, 68), (68, 69), (68, 78), (68. 79), (68, 68), (68, 57), (68, 67), (68. 77), (68, 58), (17, 17), (17.
18), (17, 28), (17, 16), (17, 27), (60, 50), (60, 60), (60. 49), (60. 70), (60, 61), (60. 59), (60, 51), (60, 69), (60,
71), (20. 19), (20. 30), (20, 20). (20. 21), (20. 29). (67. 67), (67. 58), (67. 68), (67. 78), (67. 77), (67. 57),
(70, 71), (70. 70). (70. 60). (70. 69). (70, 79). (70. 80). (70, 59), (71. 71). (71. 70) (71. 80). (61. 70). (61. 61).
(61, 50), (61, 60). (88, 87), (88. 79), (88, 89) (88. 88), (88, 99). (88, 98), (88. 78), (88, 97), (87. 78), (87, 88)
187, 96). (87, 87), (87, 97), (87, 77), (87, 86), 196, 108), (96, 97), 198, 87), (96, 86), (96, 96), (96, 95), (106,
105), (106, 107), (106, 96), (105, 105), (105, 104), (105. 114), (105, 115), (104, 114), (104, 104), (104, 105), (114,
114), (114, 104), (114, 105), (115, 105), (81, 80), (77, 77), (77, 67). (77, 68), (77, 88), (77, 78), (97, 96), 197,
106), (97, 107), (97, 87), (107, 96), (107, 106), (107, 107), (107, 108), (86, 96), (86, 86), (98 99), (98, 89), (98,
98). (95, 95). (95. 85). (95. 94). (85, 85). (85, 95). (94. 103), (103, 103)]
number edges:
Hindsight Experience Replay (HER)
episode is: 10
nodes: [22. 21, 31, 41, 42, 32, 23, 43, 33, 44, 34, 35, 45, 46, 36, 37,
47,
13, 12, 14,
15,
16, 17, 26, 25, 24, 48, 11, 27]
number of nodes: 29
edges: [122, 21), (22, 23), (22. 22), (22, 32), (22, 33), (22, 12), (21, 21) (21, 31) (21, 22), (31, 31), (31, 41), (31.
21), (31. 42). (41. 42), (41. 41). (41, 32), (41. 31). (42. 41). (42. 42). 442 32). (42, 43). (42. 31). (32. 91). (32.
32), (32, 42) (32, 33), (32, 431. (32, 23), (32, 41), (23,
22). 123. 13), 123, 14) (23,
33),
(43, 32), (43, 43).
(43, 42), (43, 33), (43, 44) (43, 34), (33, 33), (33. 44), (33, 32), (33, 43), (33.
34), (44, 44), (44, 33), (44, 43).
(44, 34), (44, 35), (44, 45), (34 43), (34, 33) (34. 35), (34, 34), (34, 46) (35 45), 135, 46), (35, 35), (35, 34)
(35, 25). (45. (6), (45, 45). (45, 35), (45, 44) (45, 34), (46, 46), (46, 45). (46. 35) (46, 36) (46. 37), (36.
36), (36, 37), (36, 47), (36. 26) (36. 46), (37, 47). (37, 37), (37, 36), 137, 48 (47, 47), (47, 37), (47, 36), (47,
46), [13, 13), (13, 12). 113 14).
19), (12, 11). (12, 12). (12, 23),
114, 14), (14,
13).
114, 15). (15. 15),
(15, 16), (15, 26). (15, 25), (16. 16), (16, 17), (26. 25), (26. 26), (26.
37).
126.
36),
(26,
27). (25. 24). (25, 36).
(25, 26), (24, 15), (48, 37), (11, 12), 111, 11), (27, 27)]
number of edges: 112
episode is: 50
nodes: [22, 21. 31, 41, 42, 32, 23, 43, 33, 44, 34, 35, 45, 46, 36, 37, 47, 13, 12, 14.
15.
16,
17, 26, 25, 24, 48. 11, 27.
18, 19, 20, 58, 57, 49, 39, 60, 50, 59, 40, 38, 28, 29, 30, 69, 70, 80, 90, 101,
100,
67,
68, 77. 78, 61]
number nodes: 55
21

---

Under review as a conference paper at ICLR 2021
edges: [[22, 21), (22, 23), (22. 22), (22. 32). (22. 33), (22. 12). (22, 13). (22. 11), (21,
21),
(21.
31).
(21,
22) (21.
11), (21. 12), (21, 82), (31, 31), (31, 41), (31, 21). (31, 42), (31, 32), (41, 42), (41, 41). (41, 32). (41. 31), (42,
41), (42, 42), (42, 32), (42, 431, (42, 31), (42, 33), (32, 311, (32. 32), (32, 42) (32,
331 132, 431, (32, 23),
(32. 41), (32. 22). (32, 21), (23. 22), 123, 13), (23. 14), (23, 39), (23. 34), (23. 24), (23. 23), (23. 12). (43, 32),
(43, 43), (43, 42), (43, 33), (43, 44), (43, 34), (93. 39), (33, 44). (33. 32), (33, 43). (33, 34), (33. 23). (33, 22)
[33, 42), (33. 24), (44, 44), (44, 33), (44,
(44, 34), (44, 95),
45), (34, 43), (34, 33), (34, 35), (34,
34), (34, 45), (34, 23), (34, 44), (34, 25), (34, 24), (35, 45), (35, 46), (35, (5,5 35), (35, 34), (35, 25), (35, (665,,44 44), (35,
36), (45, 46), (45, 45), (45, 35),
(45, 44),
34),
36).
46),
[46,
(46, 35), (46,
(46, 37),
(46, 47), (36. 36), (36, 37), (36, 47), (36, 26), (36, 46), (36,
45), (36, 35), (36. 27), (37, 47), (37, 37), (37, 36),
(37, 48), (37, 46), (37, 27), (47, 47), (47, 37), (47, 36),
46)
(47, 48) (47, 38), (47, 57), (47, 58), (13, 13)
(13, 12). (13. 14), (13, 22), [13, 23), (12, 13), (12, 11), (12, 12), (12 29), (12. 22), [12,
(14. 14),
13). (14, 15), (14, 23), (14, 25). (14, 24), (15, 15), (15, 16). (15. 26), (15, 25), (15. 14), (16, 16), (16, 17). (16,
15), (16, 26), (17, 171, (17, 16), (26, 25), (26. 26). 126, 37) (26. 36), 126,
27), (26. 15), 126,
16). (25,
(25, 36), (25, 26), (25, 16), (25, 15), (25, 14), (25, 25), (25, 35), (24, 15), (24, 35), (24,
4, 24), (, (24,
4, 25), (24, 33),
(24, 23), (24, 34), (48, 37), (48, 47), (48, 48), (48. 58). (48, 49). (48, 59), (48, 38), (11, 12), (11, 11), (11,
127, 27), (27, 28), 127, 38), (27, 37), (18, 18), (18, 19), (19, 19), (19, 201, (20 20), 120, 19), (20, 30), (58)
57), (58, 69), (58, 58), (58, 67), (58, 69), (58, 48),
(57, 48), (57, 57), (57, 58), (57. 67), (49, 39), (49, 60). (49.
50), (49, 59), (49. 49), (39. (39, 29). (39. 39). (60, 49), 160. 50), 160, 70), (50. 80), [50, 49). (50. 40).
(59, 49), (59. 59), (59, 69), (59. 58), (59, 80), (40, 49), (38, 47), (38, 28). (38, 38), (38, 39), (38. 48), (28, 29).
[28, 38), (29, 29), 129, 301 129. 39)
30)
(30, 29), 669. 69), (69. 70), 189. 58), (69. 68), (69, 59)
(70. 70) (70, 80), 170, 61), 180, 80),
(80 90) (90, 90), (90, 101), (101, 101), (101, 100), (100, 101), (100, 100)
(100.
(67. 68).
(67. 67), (67. 77), (68. 58)
(68, 69)
(77. 77). (77, 78]
number of edges: 255
episode: 100
nodes: [22, 21, 31, 41, 42, 32, 23,
43,
33,
44, 34,
35, 45,
36,
37,
47,
13, 12, 14. 15. 16,
17,
26,
25. 24, 48. 11, 27.
18, 19, 20, 58, 57, 49, 39,
60,
50,
59,
40,
38,
28, 29, 30, 69, 70,
8D,
90,
101,
100,
67,
68,
77,
78,
61,
B8, 87, 97,
96, 106, 117, 107,
86,
85,
95, 51, 99,
number of nodes: 71
edges: [[22, 21), (22, 23). (22. 22), (22. 32). (22. 33), (22. 12). (22. 13). (22. 11). (22, 31), (21. 21). (21, 31), (21.
22). (21, 11), (21, 12), (21, 32), (21. 20). (31, 31), (31, 41), (31, 21). (31, 42), (31, 32) (31. 30). (31. 40), (31.
22). (41, 42). (41, 41). (41. 52). (41, 31), (42, 41). (42,
42), (42. 32) (42, 43). (42.
31),
142, 33). (32, 31).
(32. 32), (32. 42), (32, 33), (32. 43), (32, 23). (32. 41), (32, 22). (32. 21), (23. 22) (23.
13), (23, 14), (23. 33),
(23, 34), (23, 24), (23, 23), (23, 12), (43, 32), (43, 43), (43, 42). (43, 33), (43, 44), (43, 34), (33, 33), (33, 44)
[33, 32), (33. 43), (33, 34), (33, 23), (33, 22), (33, 42), 24),
(44, 331 (44, 43), (44, 34),
35). (44, 45). (34, 43), (34, 33). (34, 35), (34, 34), 45), (34, 23), (34, 44). (34,
25), (34. (34. (35 (35. 45). (35.
46), (35, 35), (35, 34), (35, 25),
44),
36),
24),
26), (45, 46).
45). (45, 35), 44),
(45, 34), (45, 36). (46, 46), (46, 45). (46. 35). (46, 36), (46, 37), (46, 471, (36. 36), (36, 37), (36. 47). (36, 26).
(36, 46), (36, 45), (36, 35), (36. 27). (36, 25), (37. 47), (37, 37), (37, 36), (37, 48), (37, 46), (37. 01.7720 27). (37, 38)
137, 26). (47, 47), (47, 37), (47, 36), (47. 46), (47, 48), (47. 38),
57),
58), (13, 13), (13,
14), (13, 22), (13, 23), (13, 24), (12, 13), (12, 11), (12, 12), (12, 23), (12, 22), (12, 21), (14, 14), (14, 13), (14,
15). (14, 23), (14, 25), [14, 24),
26).
25). (15, 14),
24)
16), (16,
(16, 15), (16. 26). (16, 27). (17. 17). (17, 18). (17. 16). (17. 28). (17. 27), (17, 26). (26, 25). (26. 26), (26, 37),
(26, 36), (26. 27), (26. 15), (26. 16),
35), (26. 17), 125, 24). (25, 36), (25, 26), (25,
16), (25. 15), (25, 14)
125, 25), (25. 35), (24, 15), (24, 35), (24, 24). (24, 25). (24. 33), 23), 34). (24, 14), (48. (48.
47). (48, 48). (48, 58), (48, 49). (48, 59), (48, 38), (48, 39), (48. 57), (11,
(11. 11), (1,, (77, (27.
28), (27, 38), (27, 37), (27, 15), (27, 26),
18), (18. 19), [18, 17), (19, 19), [19, 20), (19,
(19, 18), (19, 28), (20, 20), (20, 19), (20, 30), (20, 29), (20, 21), (58, 57), (58, 69), (58, 58), (58, 67). (58, 59),
(58, 48), (58. 68), (58, 49), (57. 48). (57. 57).
58), (57.
(57 68), (49, 39) (49, 60),
50). (49, 59)
(49, 49), (49, 58), (49, 48). (39. 49), (39. 29). (39. 39), (39. 38), (39. 30), (39. 40), (60. 49), (60, 50). (60.
70), (60, 60). (60, 69), (60, 59), (60, 61), (50, 60), (50, 49), (50, 40), (50, 61), (50. 50), (50, 51), (59, 49), (59.
59), (59, 69), (59. 58), (59, 60). (59. 68), (40. 49). (40, 40). (40. 39), (40, 29), (40. 30), (40, 31). (4),
(38, 47), (38. 28), (38, 38), (38. 39), (38, 48), (38. 37), (38. 29), (38, 49), (28, 29), (28. 38), (28. 28), (28, 39),
(28, 18), (28, 19), (29, 29), (29, 30),
39),
19), (29,
(29, 38), (29. 40), 130, 30), (30. 20), (30, 29)
(30. 31), (30. 40), (69, 69), (69, 70), (69. 58), (69, 68), (69, 59), (69. (69,
(69, 80), (69, 79), (70, 70), (70.
80). (70, 61). (70. 71), (70, 60).
80),
90). (80. 79). (80. 70), (80, 69),
89), (90. 90), (90, 101).
(90, 79), (90. 89), (101, 101), (101, 100). (100, 101), (100, 100), (100, 90), (100, 110), (0 (67. 68), (67. 67). (67, 77)
167, 57), (68, 58), (68, 69), (68, 68), (68, 67), (68, 78), (77, 77), (77, 78), (77, 67), (77, 87) (78, 88), (78,
77), (78, 68), (78, 69), (61. 61). (61. 60), (61, 50), (61, 70), (88. 87), (87, 97), (87. 86), (97, 96), (96. 106).
(106, 117), (108, 107), (117, 106), (107, 107), (71, 71), (71, 70), (79, 79), (79, 68), (79, 80), (79, 69), (79, 78),
(89, 90), (89, 99), (86, 85), (85, 95), (51, 60), 99), (99, 100
number of edges: 370
22


Reviews:
[{"review_id": "r8PrBs0qS9j", "reviewer": "AnonReviewer3", "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": "This work presents a strategy for improving exploration and efficiency of RL by leveraging the graph structure of an episodic experience buffer. This strategy combines goal-oriented RL with structured exploration. The authors compare their proposed technique to two popular benchmarks for goal-reaching tasks. In addition, the authors provide some theoretical justification for their algorithmic choices.\n\n### Clarity\nThe biggest issue with this paper is clarity. Grammar is a minor part of this issue, but the major clarity issue is that it's simply quite hard to understand what exactly the authors are proposing/doing in this work. It's very unfortunate, because it seems like there might be some interesting ideas here, but it is very hard to say because so many details are not clear. The best resource for understanding what the authors' proposed technique is the algorithm box and accompanying text in Appendix B, but this is still not enough.\nThe lack of clarity is perhaps worst, and most crucial, when it comes to describing how the graph is constructed. How do you go from a set of trajectories to a useful graph representation? In addition, it is difficult to form an intuition around the logic of the algorithm -- for instance, how is the generated goal related to the task goal; or, does the multi-episode graph assume that the task goal is the same across episodes? The result of this confusion is that I would **not** be able to implement their algorithm based on the understanding I gain from the paper.\nTo the authors' credit, they do attempt to provide some high-level descriptions and include several high-quality illustrations of their proposed strategy, but the lack of clarity remains a decisive problem. It's entirely possible that fixing the clarity issues would result in a strong paper, but, unfortunately, it does not currently seem suitable for publication.\n\n\n### Quality and Originality\nThis work fits into a recent trend of work using graph-based representations of the environment for structured exploration and planning. In particular, this work is focused more on graph-based exploration. Overall, the paper's clarity issues prevent a detailed assessment of its broader quality, but the high-level idea seems reasonably original. Certainly, this is not the first paper to recognize that trajectories of experience can reveal the environment's structure and that this structure is conveniently represented as a graph. But I am not aware of another paper that leverages this insight in order to learn to generate a curriculum of goals for good exploration. In addition, the author's technique seems agnostic to the composition of the environment, avoiding some shortcomings of prior work.\n\n\n### Significance\nAgain, clarity issues make it difficult to assess the significance of the work. This should be expected to reduce the significance, though, since I doubt most readers will get a good sense of how to actually implement the paper's core idea. Since the work does not present many broader insights about RL, learning from goals, or structured exploration, its significance is linked to its practical value, which is currently limited by clarity issues.\n\n\n**Pros**\n- New algorithm for improving exploration in goal-oriented RL\n- Experimental validation in complex, continuous domains\n\n**Cons**\n- Very difficult to understand the details\n- Comparison to prior work is mostly unclear\n- Would be difficult to implement based on current description\n\n### Suggestions for improvement\nIf the authors can present a clear plan for how they will improve the clarity of the paper, I will be happy to consider raising my score. I recommend that the authors make use of more concrete examples. This would help to make the great illustrations (like Figures 2 and 7) more useful. Also, it may help to put the Related Work at the end of the paper. The comparison to previous work might be clearer if it is presented after the proposed technique is fully described.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hALfsOI26Yf", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "\n**Summary**\nThis paper proposes graph-structured reinforcement learning (GSRL), which consists of two key components: (1) goal generation, to choose what goals a goal-conditioned agent should follow during an exploration episode, and (2) value estimation, to prioritize experience from highly related trajectories according to local graph structure during value/policy updates. \n\nFor (1), the algorithm maintains a “state-transition graph”, essentially a graph of the observed state transitions in the MDP. At a high level, the goal generation should pick goals in the “boundary” of the current state-transition graph for exploration. This “optimal goal” that should be generated can be trained in hindsight by looking at the best trajectory in the next episode (where the best trajectory terminates at a state that is estimated to be the closest to the goal) and finding in it the reachable state from the current episode. During inference, an attention mechanism is used to identify this optimal goal in the current episode. \n\nFor (2), GSRL selects trajectories that have states that are in the immediate neighborhood of the current state to train on, rather than sampling transitions uniformly. \n\nExperiments were conducted in several (discretized) robotics environments ranging from maze navigation to robotic arm block manipulation, demonstrating improvement to HER and MAP baseline. \n\n**Positives**:\n- I like the idea of using hindsight to assign the target for choosing behavior goals for exploration. Usually, as in HER, hindsight is applied only for the optimization phase to update the value/policy by augmenting the experience data. This approach can directly affect the data collection process itself. \n- The paper presents several theoretical results: (1) to motivate the need for directed exploration, (2) showing that the exploration goals should come from the boundary.\n\n**Negatives**:\n- There are several works that investigate letting the agent choose its own goals during exploration: GoalGAN [1], DDL [2], MEGA [3], Skew-Fit [4]. Rather than constructing a graph to determine the boundaries/frontier, they use either a discriminator or a density estimator. It would be worth discussing these works in relation to GSRL, and perhaps even including some of them as baselines. \n- For prioritizing experience during value estimation, there is also MEP which tries to group trajectories that achieve diverse goals during the update. This should be compared to $\\mathcal{D}_{related}$ in line 13 in Algorithm 1. \n- There are several ablations that can be included to further gain intuition about GSRL (see questions below)\n- Some parts of the paper were confusing to read. In Section 3, the goal-oriented RL framework was introduced, with both discrete and continuous action space. I was confused then later in section 4 as the dynamic graph construction appears to rely on discrete actions in order to have a notion of degree of node $s$. \n\n**Recommendation**:\n \nOverall, I vote for marginally below the acceptance threshold. The motivation and proposed ideas are promising, but I have several concerns about relevant related literature and ablation experiments which would make the paper much stronger and convincing. \n\n**Question**:\n1. Ablations:\n  1. How does the method perform without using the attention strategy on the groups to pick $C_{ATT}$ first, then obtain the optimal goal within $C_{ATT}$? Claimed in 4.2 *Goal Learning Strategy* that supervising for the group instead of the goal can eliminate instability brought from inaccurate value estimation. The “Impact of Group Selection” shows a curve with “no group selection”, how exactly was this done?\n  2. Ablation for the value learning strategy: compare updating from transitions drawn uniformly from the replay buffer, without using $\\mathcal{D}_{related}$. Along with the above, would allow you to show that the various components of GSRL are necessary\n2. Can you clarify/explain more about the self-attention mechanism used in Eq 2? Is this similar to self-attention used in Transformer layers? \n\n**After rebuttal responses**:\n\nThe authors have tried to address my concerns about the baselines and clarifications on some of the details of their implementation during the rebuttal period. After the revision, the additional ablations and GoalGAN/CHER baselines added to the empirical evidence for their algorithm. I updated my score to a weak acceptance.\n\n**References**\n\n[1]. Florensa et al.. Automatic goal generation for reinforcement learning agents. ICML, 2018\n\n[2]. Hartikainen et al. Dynamical distance learning for semi-supervised and unsupervised skill discovery. In ICLR, 2020.\n\n[3]. Pitis et al. Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning. ICML, 2020\n\n[4]. Pong et al. Skew-Fit: State-Covering Self-Supervised Reinforcement Learning. ICML, 2020\n\n[5]. Zhao et al.  Maximum entropy regularized multi-goal reinforcement learning. ICML, 2019\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eP4ecXXLZVs", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 introduces Graph Structured Reinforcement Learning (GSRL) framework, able to balance exploration and exploitation in RL. Actually, GSRL builds a dynamic graph based on historical trajectories. Then in order to learn from sparse or delayed rewards and  be able to reach a distant goal, it decomposes the main task into a sequence of easier and shorter tasks. An attention strategy has also been proposed that is able to select an appropriate goal for each one of the easiest tasks. Experiments have been conducted on various robotics manipulation tasks showing that GSRL performs better compared to HER and MAP algorithms. \n\nThe idea of constructing a dynamic graph on top of the state-space is really interesting. In this case, the agent is able to explore efficiently all the state-space as the graph is expanded at each time-step. Despite the possible merits of this approach on  various robotics manipulation tasks, the applicability of GSRL on other sensitive tasks is not guaranteed. For instance, could GSRL be applied to the task of helicopter controlling where  the safety of the agent is critical? Another point that should be clarified by the authors is the modelling of the self-attention function. It is not clear how does it defined (Eq. 2)? It is not also obvious  for the reader how do you update the attention mechanism (see Eq. 4). I recommend to the authors to give more details about the definition and update of attention strategy and not treat it as blackbox. Moreover, at Eq. 3 the state with the highest value among the states of C_ATT is selected as goal. How do you learn the value function that is not goal-oriented as the Q-function (learned by minimising the objective function of Eq. 6)? Another point that should be discussed is if there is any connection between GSRL and Hierarchical RL. Finally, despite the fact that the paper is well-written, the notation is cluttered in some cases. For instance, $E$ is used both for the episode length and the number of episodes.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZRstfoDF8BQ", "reviewer": "AnonReviewer2", "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 framework, GSRL, to handle the sparse reward challenge and better leverage past experiences. Specifically, it formulates trajectories as a dynamic graph, and generates hindsight-like goals based on sub-group division and attention mechanism. The authors provide theoretical analysis to show the efficiency and converge property of their method. The experimental result shows the proposed method significantly outperforms the baselines. \n\nStrengths:\n+ The general idea is reasonable. \n+ Appropriate theoretical analysis is attached. \n+ The experimental result is good.\n\nWeaknesses:\n+ Is it true that the boundary of a graph consists of all observed states, as defined in Section 4.1? The example in Fig. 4 is misunderstanding. \n+ It is unclear about how the groups are represented during computing the attention values. Are they embedded as representations (e.g., averaging all state representations within one group) or just identified as one-hot group ids?\n+ Can the paper visualize the groups, their assigned attention values, and the selected goal? If a group is selected, is it true that the goal is sampled randomly from this group, or with some priors. If the boundary of a graph consists of too many states, I wonder whether the groups divided from it are still too large, as there are only three groups. \n+ It is better to clarify which episode the s_{last} comes from. According to Fig. 4, the last visited state comes from the \"next\" episode. However, according to the \"Attention Strategy\" in Section 4.1, s_{last} is appended to each group since the beginning of each episode. So is s_{last} here not from the \"future\" episode? Please correct me if I misunderstood your illustration. \n+ Regarding Appendix E.4, is a method regarded as more sample efficient if it can explore more unique nodes and form a larger group given a fixed number of episodes?\n+ Not sure experiments are enough. For example, just comparing to HER. There are some recent works [1, 2] addressing similar problems and tasks. It is better to compare to them or at least mention the difference.\n\n[1] Curriculum-guided Hindsight Experience Replay, NeurIPS-2019\n\n[2] Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning, ICML-2020\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work presents an algorithm - graph-structured reinforcement learning (GSRL)- to address the problem of exploration in sparse reward settings. The core elements of this work are 1) to build a state-transition graph from experienced trajectories in the replay buffer; 2) learn an attention module that chooses a goal from a subset of nodes in the graph and 3) policy learning via DDPG using "related trajectories", where trajectories that are related to the generated goal are sampled from the replay buffer.

Pros:
- all reviewers agree that the idea/work is interesting and valuable to the community
- reviewers appreciate the theoretical graph-based foundation/motivations

Cons:
- clarity: the manuscript still remains hard to follow. Many critical components for understanding are in the appendix. 
-- One of the key steps in this work is the discretization of the state/action space for graph construction. However, this is not mentioned very clearly, which creates a lot of confusion given that you're considering continuous control domains. 
-- Furthermore, the group selection part and training the attention module is expressed in an overly complex manner. Without the reviewers inquiries it would have been impossible to decode the technical details of this key contribution, and unfortunately it remains hard to read/follow. 
-- while the ablation experiments (impact of discretization, group selection ..) are appreciated, but it is not clear on which environment they were generated (average across all? or only one of them?).
-- do you use DQN and DDPG? There are some conflicting statements in your paper, namely first you say "We use off-policy algorithms named DQN (Mnih et al., 2013) for discrete action space and DDPG (Lillicrap et al., 2015) for continuous action space", then in the experiments you say "to demonstrate the real performance gain of our GSRL we set the policy network with DDPG for GSRL and all baselines".  
- I agree with the reviewers that it's not clear why the chosen baselines are very relevant - there seem to be other more relevant baselines. 
- the significance of the attention module is not very clear, and is not analysed properly. What does it really learn? some form of deeper analysis would be useful here. How would a version that simply picks the most uncertain state in the graph? The ablation graph presented is not very convincing.


Overall, I believe that this work will make a valuable contribution in the future, with an iteration to improve clarity and better show-case the significance of the attention module.
Decision: Reject