Learning World Graph Decompositions To Accelerate Reinforcement Learning
Authors: Wenling Shang
Alex Trott
Stephan Zheng
Caiming Xiong
Richard Socher
Venue:  (2020)
Keywords: environment decomposition
subgoal discovery
generative modeling
reinforcement learning
unsupervised learning

Abstract: Efficiently learning to solve tasks in complex environments is a key challenge for reinforcement learning (RL) agents.  We propose to decompose a complex environment using a task-agnostic world graphs, an abstraction that accelerates learning by enabling agents to focus exploration on a subspace of the environment.The nodes of a world graph are important waypoint states and edges represent feasible traversals between them.  Our framework has two learning phases: 1) identifying world graph nodes and edges by training a binary recurrent variational auto-encoder (VAE) on trajectory data and 2) a hierarchical RL framework that leverages structural and connectivity knowledge from the learned world graph to bias exploration towards task-relevant waypoints and regions. We show that our approach significantly accelerates RL on a suite of challenging 2D grid world tasks: compared to baselines, world graph integration doubles achieved rewards on simpler tasks, e.g. MultiGoal, and manages to solve more challenging tasks, e.g. Door-Key, where baselines fail.

Under review as a conference paper at ICLR 2020
LEARNING WORLD GRAPH DECOMPOSITIONS TO ACCELERATE REINFORCEMENT LEARNING
An Anonymous authors
Paper under double-blind review
ABSTRACT
Efficiently learning to solve tasks in complex environments is key challenge for reinforcement learning (RL) agents. We propose to decompose a complex environment using task-agnostic world graphs, an abstraction that accelerates learning by enabling agents to focus exploration on a subspace of the environment. The nodes of world graph are important waypoin! states and edges represent feasible traversals between them. Our framework has two learning phases: 1) identifying world graph nodes and edges by training binary recurrent variational autoencoder (VAE) on trajectory data and 2) a hierarchical RL framework that leverages structural and connectivity knowledge from the learned world graph to bias exploration towards task-relevant waypoints and regions. We thoroughly evaluate our approach on a suite of challenging maze tasks and show that using world graphs significantly accelerates RL, achieving higher reward and faster learning.
INTRODUCTION
Many real-world applications, c.g., self-driving and in-home robotics, require autonomous agent to execute different tasks within a single environment that features, c.g. high-dimensional state space, complex world dynamics structured layouts. In these settings, model-free reinforcement learning (RL) agents often struggle to learn efficiently, requiring a large amount of experience collections to converge to optimal behaviors. Intuitively, agent could learn more efficiently by focusing its exploration in lask-relevant regions, if it has knowledge of the high-level structure of the environment.
We propose method to 1) learn and 2) use an environment decomposition in the form of a world graph, a task-agnostic abstraction. World graph nodes are waypoint states, set of salient states that can summarize agent trajectories and provide meaningful starting points for efficient explo- ration (Chatzigiorgaki & Skodras) 2009 Jayaraman et al., [0188] ( Ghosh et al., 2018). The directed and weighted world graph edges characterize feasible traversals among the waypoints. To leverage the world graph, we model hierarchical RL (HRL) agents where high-level policy chooses a waypoint state goal to guide exploration towards task-relevant regions, and a low-level policy strives to reach the chosen goals.
Our framework consists of two phases. In the task-agnostic phase, we obtain world graphs by training a recurrent variational auto-encoder (VAE) (Chung et al., 2013: Gregor et al. 2013 Kingma & Welling 2013) with binary latent variables (Nalisnick & Smyth 2016) over trajectories collected using a random walk policy (Ha & Schmidhuber, 2018) and a curiosity
goal-conditioned
policy (Ghosh et al.) 2018 Nair 2018). World graph nodes are states that most frequently selected by the binary latent variables, while edges are inferred from empirical transition statistics between neighboring waypoints. In the task-specific phase, taking advantage of the learned world graph for structured exploration, we efficiently train an HRL model (Taylor & Stone, 2009).
In summary, our main contributions are:
A task-agnostic unsupervised approach to learn world graphs, using a recurrent VAE with binary latent variables and vuriosity-driver goal-conditioned policy.
An HRL scheme for the task- phase that features multi-goal selection (Wide-then- Narrow) and navigation via world graph traversal.

---

Under review as a conference paper at ICLR 2020
Waypoint State
Weighted Edge
Inference
Formation
Manager
Worker
Trajectory Collection:
Random Walk Goal- Conditioned Policy
Agent
Proposed Framework
World Graph Discovery
CEAT
Manager goal expires gels updatedd, agent moves lowards new Manager goel and hils (1, 14),
traverses wide goal picks up the key, raachss narrow gool.
wide goal, agent navigotas own and opons the door.
goall agent target cxtts.
agent
waypoints sellcctdd by the manager
waypoints
trajectories from world graph traversal
manager
waypaints
trajectories directly from worker actions
Hierarchical Reinforcement Learning
Figure 1: Top Left: overall pipeline of our 2-phase framework. Top Right (world graph discovery): subgraph exemplifies traversal between waypoint states (in blue), see Section [ for more details. Bottom (Hierarhical RL): example rollout from proposed HRL policy with Wide-then-Namme graph traversals, solving challenging Door-Key task, see Section for more details.
Manager instructions and world
Empirical evaluations multiple tasks in complex 2D grid worlds to validate that our framework produces descriptive world graphs and significantly improves both sample efficiency and final performance on these tasks over baselines, especially thanks to transfer learning from the unsupervised phase and world graph traversal.
RELATED WORK
understanding of the environment and its dynamics is essential for effective planning and control in model-based RL. For example, a robotics agent often locates or navigates by interpreting map (Lowry et al. [hruu (198][Ange) et al. 2008). Our exploration strategy draws inspiration
from active localization. where robots are actively guided to investigate unfamiliar regions (Fox
ctt al.
1998 Li et al. (2016). Besides mapping, recent works (Azar et al, 2019 Ha & Schmidhuber
2018 Guo et al. (218)) learn to represent the world with generative latent states (Tian & Gong 2017]
Haarnoja et al. 2018 Racanière et al., 2017). If the latent dynamics are also extrapolated, the latent
states can assist planning (Mnih et al.) 2016a Hafner et al.) 2018) or model-based RL (Gregor &
Besse
2018
Kaiser et al. 2019).
While also aiming to model the world, we approach this abstracting both the structure and dynamics of the environment in graph representation, where nodes are states from the environment and edges encode actionable efficient transitions between nodes. Existing works (Metzen 2013 Mannor et
2004] Eysenbachh et al. 2019 Entezari et al., 2010) have shown benefits of such graph abstractions but typically select nodes only subject good coverage the observed state space. Instead, we identify parsimonious subset of states that can summarize trajectories and provide more useful intermediate landmarks, i.e. waypoints, for navigating complex environments.
Our method for estimating waypoint states can be viewed as performing automatic (sub)goal discovery. Subgoal and subpolicy learning are two major approaches to identify a set of temporally-extendee actions, "skills", that allow agents to efficiently learn to solve complex tasks. Subpolicy learning identifies policies useful to solve RL tasks, such as option- aption-based methods (Daniel et al. 2016 Bacon
al., 2017) and subtask segmentations (Pertsch al., 2019 Kipf et al. 2018). Subgoal learning, the other hand, identifies "important states" to reach (Şimşek et al. (0055).
Previous works consider various definitions of "important" states: frequently visited states during successful task completions (Digney 1998 McGovern & Barto (2001). states introducing the most regions (Chen
novel information (Goyal al. 2019) bottleneck states connecting
2

---

Under review as a conference paper at ICLR 2020
Fg
Beta (oce0 9
BI.STM
BILSTM
BL.STM
SI.STM
BL.TTM
Generation
Prior Network
BLSTM
BLSSTM
BLSIM
DLSTM
BISSIM
DIS MM
Suddy
NT
Difisentibll Diary Units with Geta: Prior, Hard Kumarsewarry d (K Approximated Posterior
Figure 2: Our recurrent latent model with differentiable binary latent units to identify waypoint states. A prior _t)-- An inference
network (left) learns the state-conditooned prior in Beta distribution, Pe (=(zsss))=Beta(( encoder learns an approximate posterior in HardKuma distribution inferred from the state-action sequence input, (o(2i umaarrKuaam(t 1). A generation network ps reconstructs a from (s1[2==1}.
et al.
2007: Çimşek al.
2005 or environment-speccft heuristics (Ecoffet al. 2019). Our
work draws intuition from unsupervised temporal segmentation (Chatzigiorgaki & Skodras 2009
Jayaraman et al. 2018) and imitation learning (Abbeel & Ng. 2004 Hussein et al. (017). We define "important" states (waypoints) as the most critical states in recovering action sequences generated by some agent, which indicates that these states contain the richest information about the executed policy (Azar et al. 2019).
3 LEARNING WORLD GRAPHS
We propose method for learning world graph Gw, task-agnostic abstraction of an environment that captures its high-level structure and dynamics. In this work, the primary use of world graphs is to accelerate reinforcement learning of downstream tasks. The nodes of 9w. denoted by set of waypoints states Sp Vp. are generically "important" for accomplishing tasks within the environment, and therefore useful as starting points for exploration. Our method identifies such waypoint states from interactions with the environment. In addition, we embed feasible transitions between nearby waypoint states as the edges of Gw.
In this work, we define important states in the context of learning Gw (see Section for alternative definitions). That is, we wish to discover small set of states that, when used as world graph nodes, concisely summarize the structure and dynamics of the environment. Below, we describe 1) how to collect state-action trajectories and an unsupervised learning objective to identify world graph nodes, and 2) how the graph's 's edges (i.e., how to transition between nodes) are formed from trajectories.
3.1 WAYPOINT STATE IDENTIFICATION
The structure and dynamics of an environment are implicit in the state-action trajectories observed during exploration. To identify world graph nodes from such data, we train a recurrent variational autoencoder ( (VAE) that, given a sequence of state-action pairs, identifies subset of the states in the sequence from which the full action sequence can be reconstructed (Figure 2). particular, the VAE infers binary latent variables that controls whether each state in the sequence is used by the generative decoder, i.c., whether a state is "important" or not.
Binary Latent VAE The VAE consists of an inference, generative and prior network. These are structured as follows: the input to the inference network go is trajectory of state-action pairs observed from the environment 7= ((*,. az) )= with s= ) and (a= ) denoting the state and action sequences respectively. The output of the inference network is the approximated posterior over sequence == ! of binary latent variables, denoted as ( (2|a, s). The generative network Pg computes a distribution is masked if 2,=0 (we fix 21 during training), denoted as po z).
the full action sequence a using the masked state sequence, where st
Finally, conditoondi p (2 <elss) given by the prior network Pv for each 8; encodes the empirical average probability that state s, is activated for reconstruction. This choice encourages inference to select within consistent subset of states for use in action reconstruction. In particular, the waypoint
3

---

Under review as a conference paper at ICLR 2020
Algorithm I: Identifying waypoint states V/ and learning goal-conditioned policy "g
Result:
Waypoint states Vp and a goal-conditioned policy #g
Initialize network parameters for the recurrent variational inference model V
Initialize network parameters for the goal-conditioned policy ag Initialize V, with the initial position of the agent, i.c. V/ {50- = (1,
while VAE reconstruction error has not converged do for n 1-110 N do
Sample random waypoint Sp E V, Navigate agent Sp and perform T-step rollout using randow walk policy: T < [[00 Sp; (0), .... (ST, aT))
9n. +- ST
Navigate agent to 8p and perform T'step rollout using Tg with goal gn:
T + {(50- = Sp, ao.,... (ST, @T) (-1a.g)))))
Re-label my rewards with action reconstruction error as curiosity bonus:
2 - 81411 - X po(as =))
end
Perform policy gradient update of my using T" and r*
Update V using 7" and n"
Update V, as set of states with largest prior mean a,+,.
end
states Vp are chosen as the states with the largest prior means and during training, once every few iterations, Vp updated based on the current prior network.
Objective Formally, we optimize the VAE using the following evidence lower bound (ELBO):
ELBO (=)aa.s) [log pogppeass (als, =) DKL (ga(z)a, s)
To ensure differentiablity, we apply a continuous relaxation over the discrete zt. We use the Beta distribution po (=)) Beta 3.) for the prior and the Hard Kumaraswamy distribution (= =) = MlardKumal (., (3,) for the approximate posterior, which resembles the Beta dis- tribution but is outside the exponential family (Bastings et al., 2019). This choice allows us to proce- dure (Bastings et al. 2019 Louizos et al. 2017) and the reparametrization trick (Kingma & Welling 2013). Lastly, to prevent the trivial solution of using all states for reconstruction. we use a secondary objective Lo to regularize the To norm of z at targeted value ls0 (Louizos et al. 2017 Bastings et al. 2019), the desired number of selected states out of T steps, e.g. for when T 25, we set 140 5, meaning ideally out of 25 states are activated for action reconstruction. Another term Lr to encourage temporal separation between selected states by targeting the number of 0/1 switches among z at 2/4a:
sample Os and is without sacrificing differentiability, accomplished via the stretch-and-rectie
T
2
Co (=)s,a) [|o= -oll3
Cr Enote x.a)
Ego(=
Σ
1/2e #
20+1]
2po
(2)
See Appendix A for details on training the VAE with binary 2t, including integration of the Hard Kumaraswamy distribution and how to regularize the statistics of 2.
3.2 EXPLORATION FOR WORLD GRAPH DISCOVERY
Naturally, the latent structure learned by the VAE depends on the trajectories used train Hence, collecting rich set of trajectories is crucial. Here, we propose strategy to bootstrap useful set of trajectories by alternately exploring the environment based on the current itcration's 's V, and updating the VAE and Vp.. repeating this cycle until the action reconstruction accuracy plateaus (Algorithm [
During exploration, we use action replay to navigate the agent to a state drawn from the current iteration's s Vp. Although resetting via action replay assumes our undermeath environment to be deterministic, cases where this resetting strategy infeasible, it may be modified so long as to allow the exploration starting points expand as the agent discovers more of its environment. For
4

---

Under review as a conference paper at ICLR 2020
Vi
I
LSTM
LSTM
V
DEIR
[1
LSTM
S:
S++++1
LSTM
LSTM
St Termination Conditon Met
5:+1
SCL
9L+N+1
using Wide-then-Narrow goals. The Manager first outputs a waypoint state as the wide goal g", then attends to a closer-up area around g" to narrow down the final goal g".
Figure 3: Left: a standard Feudal Network. Right:
each such starting point, we collect two rollouts. In the first rollout, we perform a random walk to explore the nearby region. In the second rollout, perform actions using goal-conditioned policy Ty (GCP), setting the final state reached by the random walk as the goal. Both rollouts are used for trianing the VAE and the latter is also used for training Tg.
GCP provides a venue to integrate intrinsic motivation, such as curiosity (Burda et al. 2018 Achiam & Sastry 2017 Pathak al. 2017 Azar al. 2019) generate more diverse rollouts. Specifically, we use the action reconstruction error of the VAE as an intrinsic reward signal when training Tg. This choice of curioisty also prevents the VAE from collapsing to the simple behaviors of vanilla Tg.
3.3 EDGE FORMATION
The final stage is construct the edges of Gw. which should ideally capture the environment dynamics, i.e. how to transition between waypoint states. Once VAE training is complete and V, is fixed, we collect random walk rollouts from each of the waypoints Sp V, to estimate the underlying adjacency matrix (Biggs) 1993). More precisely, we claim a directed edge Sp - 9, if there exists intersect a third waypoint. We also consider
random walk trajectory from Sp to Sg that does paths taken by Tg (starting at sp and setting 8y as the goal) and keep the shortest observed path from Sp to 8g as world graph edge transition. We use the action sequence length of the edge transition between adjacent waypoints as the weight of the edge. As shown experimentally, a key benefit of our approach the ability to plan over 9.. To navigate from one waypoint to another, we can use dynamic programming (Sutton 1998 Feng et al. 2004) to output the optimal traversal of the graph.
ACCELERATING REINFOR LEARNING WITH WORLD GRAPHS
World graphs present high-level, task-agnostic abstraction of the environment through waypoints and feasible transition routes between them. A key example of world graph applications for task- specific RL is structured exploration: instead of exploring the entire environment, RL agents can use world graphs to quickly identify task-relevant regions and bias low-level exploration to these regions. Our framework leverage world graphs for structured exploration consists of two parts:
1. Hierarchical RL wherein the high-level policy selects subgoals from V,-
2. Traversals using world graph edges.
4.1 HIERARCHICAL RL OVER WORLD GRAPHS
Formally, an RL agent learning to solve task is formulated Markov Decision Process: at time 4 the agent is a state 8t, executes an action a, via policy 7 (a, (5)) and receives a rewards r.. The Ei20 where
agent's goal is to maximize its cumulative expected return E(s.a))=T.p00
1( at).Po(55) (S0) are the transition and initial state distributions.
To incorporate world graphs with RL, we use hierarchical approach based on the Feudal Network (FN) (Dayan & Hinton 1993 Vezhnevets et al. 2017). depicted in Figure 3 A standard FN
5

---

Under review as a conference paper at ICLR 2020
Task MaltiGoaf
Task Description
Environment Characteristies
Collect randomly spawned balls, each ball gives +1 reward. To end an episode, the agent to exit at designated point. Agents receive a single reward S propertional to the number of halls collected upon exiting.
Balls located rundomlly dease roward.
MultiGoat-ppon Sparze
Balls are located randorilyy. sparse reward.
MuliGGou-
Spawn lava blocks random locations each time step that immediutely terminutes the epásode stepped on.
Stochastic environment. Multiple objects: lava and balls are rundomly located, dense reward. Walls, door key located randomly. Agents additional actions: pick and toggle.
Stochastie
Dour-Key Key
Agent has to pick a key open door (reward and reach the exit point on the other side freward +1).
Table I: An overview of tasks used to evaluate the benefit of using world graphs. Visualizations can be found in Appendix D
decomposes the policy of the agent into two separate policies that receive distinct streams of reward: a high-level policy (" ("Manager") learns to propose subgoals; a low-level policy ("Worker") receives subgoals from the Manager as inputs and is rewarded for taking actions in the environment that reach the subgoals. The Manager receives the environment reward defined by the task and therefore must learn to emit subgoals that lead to task completion. The Manager and Worker do not share weights and operate at different temporal resolutions: the Manager only outputs new subgoal if either the Worker reaches the chosen one or a subgoal horizon e exceeded.
For all our experiments, policies are trained using advantage actor-critic (A2C), on-policy RL algorithm Wu & Tian 2016; Pane et al. 2016;; Mnih et al. 2016b). To case optimization, the feature extraction layers of the Manager and Worker that encode 8; initialized with the corresponding layers from ng. the GCP learned during world graph discovery phase. More details are in Appendix B
4.2 WIDE-THEN -NRRROW GOALS AND WORLD GRAPHS
To incorporate the world graph, introduce Manager policy that factorizes subgoal selection fol- lows: a wide policy nt (gt" (st) selects a waypoint state as the wide goal gdd с Vp, and narrow policy
x² ["(a" (r. selects a state within local neighborhood of 9t" i.c. its e-net (Mahadevan & Mag-
gioni 2007), as the narrow goal g" E {s (s,, l() < E}. The Worker policy π " [azl St, D 9i
chooses the action taken by the agent given the current state and the wide and narrow goals from the
Manager. A visual illustration is in Figure 4 and training details in Appendix
4.3 WORLD GRAPH TRAVERSAL
The wide-then--me nharow subgoal format simplifies the search space for the Manager policy. Using waypoints wide goals also makes it possible to leverage the edges of the world graph for planning and executing the planned traversals. This process breaks down as follows:
1. When to Traverse:
When the agent encounters a waypoint state E Vyp, "traversal" is initiated s; has feasible connection in Gur to the active wide goal g;"
2. Planning:
Upon triggering traversal, the optimal traversal route from the initiating state to gt" is estimated from the 9.. edge weights using classic dynamic programming planning (Sutton 1998 Feng al. 2004). This yields sequence of intermediate waypoint states.
3. Execution:
Execution of graph traversals depends on the nature of the environment. If deterministic, the agent simply follows the action sequences given by the edges of the traversal. Otherwise, the agent uses the pretrained GCP Tg to sequentially reach each of the intermediate waypoint states along the traversal (we fine-tune na in parallel where applicable). If the agent fails to reach the next waypoint state within certain time limit, it stops its current pursuit and a new (g",g" g²) pair received from the Manager.
World graph traversal allows the Manager to assign task-relevant wide goals g" that can be far away from the agent yet still reachable, which consequentially accelerates learning by focusing exploration around the task-relevant region near nd
5 EXPERIMENTAL VALIDATION
We now assess each component of our framework on a set of challenging 2D grid worlds. Our ablation studies demonstrate the following benefits of our framework:

---

Under review as a conference paper at ICLR 2020
Task
Size
A2C
FN +5y init
Ours
+u,-Init
-
+ +ag-nit Gu-traversal
MultiGoal
Small
2.04+0.05
2.93+0.74
5.25++013
3.92++0.22
5.05++0.03
Medium
5.15+0.11
2.5620.09
3.00=:0.90
Larger
2.18:10.1 12
2.72:0..6 0999
MuliGool-Spprse
Small
0.3910.00
0,2111001
0.42:0.077
Medium
0.20:10.04
0.25:10.03
Larger
0.16:0.22
0.26::: 11
MuliGool-Stochaate
Small
13811.20
18320
3.0010.31
2,9210,45
Medium
2.99:1.11
2.4210.24
2.644:0.3.
Larger
0.60
Door-Key
Small
0.9910.00
0.3720.15
0.92+00.02
Medium
0.56:10.02
0. 0.76: 0666
Larger
0.26+00119
Table 2: On a variety of tasks and environment setups, we evaluate RI. models trained with GCP x. initialization, with G world graph travresal, and with both. All models on the right are equipped with WN. Left are baselines for additional comparison. We report final rewards for MultiGoal tasks and success rates for Door-Key are reported. no result reported, the agent failed solve the task.
Waypoint type
MudtiGoal
MaliGooo Spurze 0.26=10111 0.19#0.11
MultiGoo MultiGod-Stnchaadd Strchastic 0.60:20.12 0.41+0.25
Door Key
Learned
2. 2.72: 2.30
0.26: 19 0.27=0040
Random
Table 3: Comparing learned VP versus random Veand as wide subgoals on large mazes, all trained with Ny initialization and graph traversal. V, generally is superior in terms of performance and consistency. We report final rewards for MultiGoal tasks and success rates for Door-Ke Key are reported.
It improves sample efficiency and performance over the baseline HRL model.
It benefits tasks varying in envirionment scale, task type, reward structure, and stochasticity.
The identified waypoints provide superior world representations for solving downstream tasks, compared graphs using randomly selected states as nodes.
Implementation details, snippets of the tasks and mazes are in Appendix CD
5.1 ABLATION STUDIES ON 2D GRID WORLDS
For our ablation studies, we construct 2D grid worlds of increasing sizes (small, medium and large) along with challenging tasks with different reward structures, levels of stochasticity and logic (summarized in Table D. In all tasks, every action taken by the agent receives a negative reward penalty. We follow a rigorous evaluation protocol (Wu et al. 2017] Ostrovski et al., 2017 Henderson et al. 2018): each experiment repeated with 3 training seeds. 10 additional validation seeds are used pick the model with the best reward performance. This model is then tested 100 testing seeds. We report mean reward and standard deviation.
We ablate each of the following components in our framework and compare against non-hierarchical (A2C) and hierarchical baselines (FN):
1. initializing the feature extraction layers of the Manager and Worker from Tg-
2. applying Wide-thenNNarow Manager (WN) goal instruction, and
3. allowing the Worker to traverse along G...
Results are shown in Table sum, each component improves performance over the baselines.
Wide and narrow goals Using two goal types is highly effective way to structure the Manager instructions and enables the Worker differentiate the transition and local task-solving phases. We note that for small MultiGoal, agents do not benefit much from Gw traversal: it can rely solely the guidance from WN goals to master both phases. However with increasing maze size, the Worker struggles to master traversals on its own and thus fails solving the tasks.
World Graph Traversal As conjectured in Section 4.3 the performance gain of our framework
be explained by the larger range and more targeted exploration strategy. In addition, the Worker
7

---

Under review as a conference paper at ICLR 2020
Large Mare MuliGoal
Medium Maze MultiSial, Intialication Compars scn
meeco
vogpoei
vegpoet
reedon Wevversa
woppook ViNero
wwy.artrmmaooo
woppost mrc -mannna
Pacodton
Figure Validation performance during training (mean and standard-deviation reward, seeds) for MultiGool, Left: Comparing Vn and Vrand, with or without traversal, all models use WN and Tg initialization. We see that 1) traversal speeds up convergence, 2) Viand gives higher variance and slightly worse performance than Vμ- Right: comparing with without Ty initialization V,. all models use WN. We that initializing the tpec-spe phase with the lask-agnostic goal-conditioned policy significantly boosts learning.
does not have learn long distance transitions with the aid of Jw traversals. Figure confirms that 9 traversal speeds up convergence and its effect becomes more evident with larger mazes. Note that the graph learning stage only need 2.4K iterations converge. Even when taking these additional environment interactions into account, 9,. traversal still exhibits superior sample efficiency, not to mention that the graph is shared among all tasks. Moreover, solving Door-Key involves complex combination of sub-tasks: find and pick up the key, reach and open the door and finally exit. With limited reward feedback, this is particularly difficult to learn. The ability to traverse along Gu enables longer-horizon planning on top of the waypoints, thanks to which the agents boost the success rate on medium Door-Key from 0.56=0.05 0.75-+0.06.
Benefits of Learned Waypoints To highlight the benefit of establishing the waypoints learned by the VAE as nodes for Gw. we compare against results using Gw constructed around randomly selected states (Vrand). The edges of the random-node graph are formed in the same way as described in Section 33 and its feature extractor is also initialized from Tg. Although granting knowledge acquired during the unsupervised phase to Vrand is unfair to Vp. deploying both initialization and traversal while only varying Viand and V, isolates the effect from the nodes the best extent. The comparative results (in Table (3] learning curves for MuliiGoal in Figure 44 suggest V, generally outperforms Vrand- Door-Key is the only task in which the two matches. However, Vrand exhibits a large variance, implying that certain sets of random states can be suitable for this task, but using learned waypoints gives strong performance more consistently.
Initialization with GCP Initializing the weights of the Worker and Manager feature extractors from n, (learned during the task-agnosti phase) consistently benefits learning. In fact, we observe that models starting from scratch fail on almost all tasks within the maximal number training iterations, unless coupled with G., traversal, which is still inferior to using iniiiitializaiion. Particularly, for the small
environment, there a high chance that lava square blocks traversal; therefore, without the environment knowledge from Fy transferred by weight initialization, the interference created by the episode-terminnting lava prevents the agent from learning the task.
CONCLUSION
We have shown that world graphs are powerful environment abstractions, which, in particular, are capable of accelerating reinforcement learning. Future works may extend their applications to more challenging RL setups, such as real-world multi-task learning and navigation. It is also interesting to generalize the proposed framework to lear dynamic world graphs for evolving environments, and applying world graphs to multi-agent problems, where agents become part of the world graphs of other agents.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 1. ACM, 2004.
Joshua Achiam and Shankar Sastry. Surprise-bar -rased intrinsic motivation for deep reinforcement learning. arXiv preprint arXiv:1703.0111 2017.
Adrien Angeli, David Filliat, Stéphane Doncieux, and Jean-Arcady Meyer. A fast and incremental method for loop-closure detection using bags of visual words. IEEE Transactions on Robotics, pp. 1027-1037, 2008.
Mohammad Gheshlaghi Azar, Biala Piot, Bernardo Avila Pires, Lean-Basticn Gril, Florent Altche, and Remi Munos. World discovery model. arXiv, 2019.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option- critic architecture. In Thirty- Firity-Frstt AAAI Conference on Artificial Intelligence, 2017.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado P van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. In Advances in neural information processing systems, pp. 4055-4065, 2017.
Joost Bastings, Wilker Aziz, and Ivan Titov. Interpretable neural predictions with differentiable binary variables. In Proceedings of the 2019 Conference of the Association for Computational Linguistics, Volume (Long Papers). Association for Computational Linguistics, 2019.
Dimitri Bertsekas. Nonlinear Programming. 1999.
Norman Biggs. Algebraic Graph Theory. 1993.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driven learning. arXiv preprint
04335, 2018.
Maria Chatzigiorgaki and Athanassios N Skodras. Real-time keyframe extraction towards video content identification. In 2009 16th International conference on digital signal processing, pp. 1-6. IEEE, 2009.
Fei Chen, Yang Gao, Shifu Chen, and Zhenduo Ma. Connect-based subgoal discovery for options in hierarchical reinforcement learning. In Third International Conference on Natural Computation (ICNC 2007), volume pp. 698-702. IEEE, 2007.
Junyoung Chung, Kyle Kastner, Laurent Dinh, Kratarth Goel, Aaron Courville, and Yoshua Bengio. A recurrent latent variable model for sequential data. In Advances in neural information processing systems. pp. 2980-2988 2015.
John D Co-Reyes, YuXuan Liu, Abhishek Gupta, Benjamin Eysenbach, Pieter Abbeel, and Sergey Levine. Self-consistent trajectory autoencoder: Hierarchical reinforcement learning with trajectory embeddings. arXiv preprint
2018.
Christian Daniel, Herke Van Hoof, Jan Peters, and Gerhard Neumann. Probabilistic inference for
determining options reinforcement learning. Machine Learning, 104(2-3)3337-357, 2016.
Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. In Advances in neural information processing systems, pp. 271-278, 1993.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lec, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv, 2018.
Bruce L Digney. Learning hierarchical control structures for multiple tasks and changing environ- ments. 1998.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In International conference machine learning, pp. 647-655, 2014.

---

Under review as a conference paper at ICLR 2020
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clume. Go-explore: new approach for explooratot problems. arXiv preprint 1901::990..1000 2019.
Negin Entezari, Mohammad Ebrahim Shiri, and Parham Moradi. A local graph clustering algo- rithm for discovering subgoals in reinforeement learning. In International Conference on Future Generation Communication and Networking, pp. 41-50. Springer, 2010.
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search the replay buffer: Bridging planning and reinforcement learning. arXiv preprint arXiv:1903.00660 2019.
Zhengzhu Feng, Richard Dearden, Nicolas Meuleau, and Richard Washington. Dynamic program- ming for structured continuous markov decision problems. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pp. 154-161 161. AUAI Press, 2004.
Dieter Fox, Wolfram Burgard, and Sebastian Thrun. Active markov localization for mobile robots. Robotics and Autonomous Systems, 25((-4))))))) (4:5-44):-5500 1998.
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal- conditioned policies. arXiv preprint arXiv:1811.07819. 2018
Anirudh Goyal, Riashat Islam, Daniel Strouse, Zafarali Ahmed, Matthew Botvinick, Hugo Larochelle, Sergey Levine, and Yoshua Bengio. Infobot: Transfer and exploration via the information 2019.
bottleneck. arXiv preprint
Karol Gregor and Frederic Besse. Temporal difference variational auto-encoder. arXiv preprint wvXiv:1806.03107, 2018.
Karol Gregor, Ivo Danihelka, Alex Graves, Danilo Jimenez Rezende, and Daan Wierstra. Draw: A recurrent neural network for image generation. In JCML, 2015.
Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Bernardo A Pires, Toby Pohlen, and Rémi Munos. Neural predictive belief representations. arXiv preprint (811::0111006400 2018.
David Ha and Jürgen Schmidhuber. World models. arXiv preprint
2018.
Tuomas Haarnoja, Kristian Hartikainen, Pieter Abbeel, and Sergey Levine. Latent space policies for hierarchical reinforcement learning. arXiv preprint arXiv: / 02808, 2018.
Danijar Hafner, Timothy Lillicrap, lan Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. arXiv preprint arXiv: 1811 1,04511, 2018.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Thirty-Second AAAI Conference on Artificial Intelli- gence, 2018.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In ICLR), 2017.
Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: A
survey of learning methods, ACM Computing Surveys (CSUR), 50(2):21, 2017.
Dinesh Jayaraman, Frederik Ebert, Alexei A Efros, and Sergey Levine. ainestin prediction: Predicting predictable video frames. arXiv preprint arXiv: 1808.0888 2018.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Camphell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al. Model-based reinforcement learning for atari. arXiv preprint arXiv: 1903.090300000 1903.00444 2019.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Diederik Kingma and Max Welling, Auto-encoding variational bayes. In ICIR, 2013.
10

---

Under review as a conference paper at ICLR 2020
Thomas Kipf, Yujia Li, Hanjun Dai, Vinicius Zambaldi, Edward Grefenstette, Pushmeet Kohli, and Peter Battaglia. Compositional imitation learning: Explaining and executing one task at a time. arXiv preprint arX.v:1812.01444000 2018.
Quoe Le, Navdeep Jaitly, and Geoffrey E Hinton. simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv: seee::0044094 2015.
Alberto Quattrini Li, Marios Xanthidis, Jason M O'Kane, and Ioannis Rekleitis, Active localization with dynamic obstacles. In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1902-1909. IEEE, 2016.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1_0 regularization. arXiv preprint arXiv:1712.01312 2017.
Stephanie Lowry, Niko Sünderhauf, Paul Newman, John Leonard, David Cox, Peter Corke, and Michael J Milford. Visual place recognition: A survey. IEEE Transactions on Robotics, 32(1): 1-19, 2015.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:161 2016.
Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learning representation and control in markov decision processes. Journal of Machine Learning Research, 8(0ct):2169-22311 2007.
Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the twenty-first international conference on Machine learning, pp. 71. ACM, 2004.
Amy McGovern and Andrew Barto. Automatic discovery of subgoals reinforcement learning using diverse density. 2001.
Jan Hendrik Metzen. Learning graph-based representations for continuous reinforcement learning domains. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 81-96. Springer, 2013.
Dmytro Mishkin and Jiri Matas. All you need is a good init. arXiv preprint arXiv: 2015.
Volodymyr Mnih, John Agapiou, Simon Osindero, Alex Graves, Oriol Vinyals, Koray Kavukcuoglu, et al. Strategic attentive writer for learning macro-actions. arXiv preprint 1rXiv:1606. 2016a.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap. Tim Harley, David Silver. and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning, pp. 1928-1929 1937, 2016b.
Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual reinforcement learning with imagined goals. In Advances in Neural Information Processing Systems, pp. 9191-9200, 2018.
Eric Nalisnick and Padhraic Smyth. btrck-breaking variational autoencoders. arXiv preprint arXiv.1605.06197. 2016.
Georg Ostrovski, Mare G Bellemare, Aaron van den Oord, and Rémi Munos. Count-based exploration with neural density models. ICML., 2017.
Yudha Pane, Subramanya P Nageshrao, and Robert Babuška. Actor-critic reinforcement learning for tracking control in robotics. In Decision and Control (CDC), 2016 IEEE 55th Conference on, pp. 5819-5826. IEEE, 2016.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity- driveen exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 16-17, 2017.

---

Under review as a conference paper at ICLR 2020
Karl Pertsch, Oleh Rybkin, Jingyun Yang, Kost Derpanis, Joseph Lim, Kostas Daniilidis, and Andrew Jeable. Keyin: Discovering subgoal structure with keyframe- based video prediction. arXiv, 2019.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adria Puigdomenech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. Imagination- augmented agents for deep reinforcement learning. In Advances in neural information processing systems. pp. 5690-5701, 2017.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. In JCML, 2014.
Olga Russakovsky. Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-252 2015.
Wenling Shang, Herk van Hoof, and Max Welling, Stochastic activation actor-critic methods. In ECML-PKDDD, 2019.
Özgür Şimşek, Alicia Wolfe, and Andrew Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd international conference Machine learning, pp. 816-823. ACM, 2005.
Richard S Sutton. Introduction to reinforcement learming, volume 135. 1998.
Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(Jul):1333-165, 2009.
Sebastian Thrun. Learning metric-topologicall maps for indoor mobile robot navigation. Artificial Intelligence, 99(1):21-71, 1998.
Yuandong Tian and Qucheng Gong. Latent forward model for real-time strategy game planning with incomplete information. In NIPS Symposium, 2017.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Eearning-Vollume 70, pp. 3540-3549. JMLR. org, 2017.
Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using tronecker-factoree approximation. In NIPS, 2017.
Yuxin Wu and Yuandong Tian. Training agent for first-person shooter game with actor-critic curriculum learning. 2016.
12

---

Under review as a conference paper at ICLR 2020
A RECURRENT VAE WITH DIFFERENTIABLE BINARY LATENT VARIABLES
As illustrated in the main text, the main objective for the recurrent VAE the following evidence lower bound with derivation:
/ plals,
log p(als) log
/ plals, =))(= ((zla,)) s)
log
{(=1a, 8) dz
log / plals; 2) p(z]b)
g(2(a,s) 8) ((2 s)dz
2 Lotsla.) 2) log ((2la,s) s)
p(=[s)
[logslss) 2)] DKL s)][p()|s))
The inference network de takes in the trajectories of state-action pairs and at each time step approximates the posterior the corresponding latent variable 2, The prior network py takes state st at each time step and outputs the cate-condiiioned prior (st)). We choose Beta the prior distribution and the Hard Kuma as the approximated posterior to relax the discrete latent variables to continuous surrogates.
The Kuma distribution Kuma(a, 3) highly resembles the Beta Distribution in shape but does not come from the exponential family. Similar to Beta, the Kuma distribution also ranges from bi- modal (when a x 3) to unimodal (a/3 - 0 or a/3 + oo). Also, when a = 1 or 3 = 1, Kuma( B) Beta(a, B). We observe empirically better performance when fix B 1 for the Kuma approximated posterior. One major advantage of the Kuma distribution is its simple Cumulative Distribution Function (CDF):
FKuma (I, a. B) (1 (1- (1--112200 111xxa) 2)
is therefore amendable to the reparametrization trick (Kingma & Welling 2013
Rezende et al.
2014 Maddison et al. 2016) by sampling from uniform distribution U(0
== P Kuma (w; a, 3) Kuma(a,,8) B)
Lastly, the KL-divergence between the Kuma and Beta distributions can be approximated in closed form (Nalisnick & Smyth 2016):
- (-7- v((b) -
1
DRL. (Kuma(a, B) B))
a
b + (3 - 1)b
1 Beta
m (m..).
+ log(ab) + log Beta(a, 9)
(5)
b
m=1 + ab
where is the Digamma function, y the Euler constant, and the approximation uses the first few terms of the Taylor series expansion. We take the first 5 terms here.
Next, we make the Kuma distribution "hard" by following the steps in Bastings et al. (2019) First stretch the support (r 61, 1 (2), 62 > 0, and the resulting CDF distribution takes the form:
2 (=-1 (r- (-))0.0)
F2(2) = FKuma
(6)
Then, the non-eligible probabilities for O's and I's are attained by rectifying all samples below 0 to and above I to 1, and other value as it is, that is
P( = 0) = FKuma (- و (F-aa,,)).
P(== 1)= 1 FKuma a.-).a.))
Lastly, impose additional regularization terms L, and LT the approximated posteriors. As described in the main text, L, prevents the model from selecting all states reconstruct {a+)7-1 T-1
13

---

Under review as a conference paper at ICLR 2020
by restraining the expected Lo norm of (21 212211 approximately be targeted value pi (Louizos et al. [211;; Bastings et al. 2019). other words, this objective adds the constraint that there should be Ho of activated 2, given sequence of length T. The other term LT encourages temporally isolated activation of žt, meaning the number of transition between and among 2 's should roughly be 2/4.- Note that both expectations in Equation have closed forms for HardKuma.
Lo = || (())aa)) [1| - moll" where
(8)
[z)2/a,)) [1|=|||]
E (x [1
T
P (zg =
Σ
FRuma
(
-1 Wee 81))
(9)
1=1
1=1
T-1
LT =
||[ ([[[))))
12tt11 2poll?, where
(10)
t=l
T-1
T-1
Σ
11 (1- 0)) + (1 p(ze (1)
1=1
(11)
The overall optimization objective consists of action sequence reconstruc- tion, KL-divergence between the posterior and prior, Co and CT (Equation 12 We tune the objective weights A; using Lagrangian relaxation (Higgins et al. 2017 Bastings et al. 2019 Bertsekas 1999). treating > learnable parameters and performing alternative optimization between X; 's and the model parameters. We observe that as long as their initialization is within a reasonable range, X 's converge to a local optimum:
Lagrangian Relaxation.
max min -Equ(zia,s) [log (a s, =)] +A₁ DKL (ga(=)a, a, (zls)) + (12) (A12..) (0,0.0)
We observe this approach produce efficient and stable mini- biini-batch training.
B GOAL-COND POLICY INITIALIZATION FOR HRL
2018 is sensitive to weight initialization (Mishkin & Matas 2015 Le et al. 2015), due to its complexity and lack of clear supervision various levels. Therefore, taking inspiration from prevailing pre-training procedures in computer vision (Russakovsky et al. 2015 Donahue et al. (0144) and NLP (Devlin et al. 2018 Radford et al., 2019), we take advantage the weights learned by Ty during world graph discovery when initializing the Worker and Manager policies for downstream HRL, Rg has already implicitly embodied much environment dynamics information.
Optimizing composite neural networks like HRL Coo-Reyes
More specifically, extract the weights of the feature extractor, i.c. the state encoder, and use them as the initial weights for the state encoders of the HRL policies. Our empirical results demon- strate that such weight initialization consistently improves performance and validates the value of skill/knowledge transfer from GCP (Taylor & Stone 2009: Barreto et al. 2017).
C ADDITIONAL IMPLEMENTATION DETAILS
Model code folder including all architecture details is shared in comment.
C.I HYPERPARAMETERS FOR VAE TRAINING
Our models are optimized with Adam Kingmma & Ba 2014) using mini-batches of size 128, thus spawning 1 128 asynchronous agents to explore. We use an initial learning rate of 0.0001. with = 0.001, 3 = 0.9, 82 = 0.999; gradients are clipped to 40 for inference and generation nets. For HardKuma, set I = -0.1 and 1.1. The maximum sequence length for BiL.TMM is 25. The
14

---

Under review as a conference paper at ICLR 2020
total number of training iterations is 3600 and model usually converges around 2400 iterations. We train the prior, inference, and generation networks end-to-end.
We initialize X 's (see Lagrangian Relaxation) to be A 0.01 (KL-divergence)). 0.06 (Co), A = 0.02 (Cr). After each update the latent model, we update X whose initial learning rate is 0.0005, by maximizing the original objective in similar way as using Lagrangian Multiplier. At the end of optimization, X; converge to locally optimal values. For example, with the medium maze, A 0.067 for the KL-term, X2 0.070 for the Lo and X 0.051 for the Lr term. The total number of waypoints Vyl is set to be 20% of the size of the full state space.
C.2 TRAINING HRL MODELS
The procedure of the Manager and the Worker in sending/receiving orders using either traversal paths among v, from replay buffer for deterministic environments or with Zg for stochastic ones follows:
The Manager gives a wide-narrow subgoal pair (gw.gn).
2.
The agent takes action based on the Worker policy xhd conditioned on (g and reaches a new state s'. If s' E Vp, has not yet met, and there exists a valid path basing on the edge paths from the world graph s' + Iw. agent then either follows replay actions or mg to reach Iw. If x still does not reach desired destination in certain steps, then stop the agent wherever stands; also Ty can be finetuned here.
3. The Worker receives positive reward for reaching In for the first time.
4. If agent reaches In. the Worker also receives positive rewards and terminates this horizon.
5. The Worker receives negative for every action taken except for during traversal; the Manager receives negative reward for every action taken including traversal.
6. When either 9n is reached or the maximum time step for this horizon is met, the Manager renews its subgoal pair.
The training of the Worker policy N/ follows the same A2C algorithm as Tg.
The training of the Manager policy n" also follows similar procedure but as operates at a lower temporal resolution, its value function regresses against the -tee discounted reward where Im covers all actions and rewards generated from the Worker.
When using the Mide-then-Naate instruction, the policy gradient for the Manager policy Tm becomes:
(T....)) Am, V log (n² (sw,,ls:) xt (In,el Iw.t, [)] V [ (x**) + 76 (x² (=99:,),:))))
where Am. the Manager's advantage time t, Also, for Manager, the size of the action space scales linearly with (S), the exact entropy for the x can easily become intractable. Essentially there are O (IV) x (N²)) possible actions. To calculate the entropy exactly, all of them has to be summed, making it easily computationally intractable:
Σ
n ""( (80,
log Vx" (wn (ars 88 3 nh (w se).
=
WEV W. Eaw
Thus in practice we resort to an effective alternative H (IT*) H (TT (-19w,))) Psuedo-code for Manager training is in Algorithm 2
C.3 HYPERPARAMETERS FOR HRL
For training the HRL policies, we inherit most hyperparameters from those used when training wy. as the Manager and the Worker both share similar architectures with Ty. The hyperparameters used when training Tr follow those from Shang et al. (2019). Because the tasks used in HRL experiments are more difficult than the generic goal-reaching task, set the maximal number of training iterations to 100K abd training is stopped early if model performance reaches a plateau. The rollout steps for each iteration is 60. Hyperparameters specific HRL are the horizon Manager's 's local attention range (that is, the neighborhood around g" within which g" is selected), which are N 5 for small and medium mazes, and N for the large maze.
20 and the size of the
15

---

Under review as a conference paper at ICLR 2020
Algorithm 2: Training of nh for HRL. models
Initialize network parameters for n" here th refers to the policy at time rollout time step I; Given map of sy;
for iter = 0, 1, 2, ... do
Clear gradients d0 0:
Reset the set of time steps where n. omits a new subgoal Sn 0 and 4 0.; while & <= max or episode not terminated do
Simulate under current policy ",,t-1 π -
if the Worker has met the previous subgoal exceeded the horizon then
Sample new subgoal Im,t from π. nm
2m,t FLSTM (CN((Sm,s Sy), Bm,,t.) Vm,t fo(=m.)) Ti {p(2m,))
end
Sm = Sm U {tm} and fm =
end
0, if terminal
R
Vana +1, otherwise"
for
t tmaxx ... 1 do
R +- rt + R:
if / Sm then
Am, + R Vm.ii
Accumulate gradients from value loss: d0 d8 X 89
Accumulate policy gradients with entropy regularization: d0 d0 V log Tm, (9mm))Amm + 3V H (m,,));
end
end
end
D 2D GRID WORLD VISUALIZATIONS
IAMT
CHPPP
Small
Large
Figure Visualization of the 2D grid environments in our experiments, along with the learned waypoints in blue.
Figure 6: Visualization of tasks in our experiments.
16


Reviews:
[{"review_id": "rkgq0aBAtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes an approach to identifying important waypoint states in RL domains in an unsupervised fashion, and then for using these states within a hierarchical RL approach.  Specifically, the authors propose to use a binary latent variable VAE to identify waypoint states, then an HRL algorithm uses these waypoints as intermediate goals to better decompose large RL domains. The authors show that on several grid world tasks, the resulting policies substantially outperform baseline approaches.\n\nComments: I have mixed opinions on this paper, though ultimately feel that it is below the bar for acceptance.  There are a lot of aspects to the proposed approach, and overall I'm left with the impression that there are some interesting and worthwhile aspects to the proposed method, but ultimately it is hard to disentangle precisely what is the effect of each contribution.\n\nFor example, let's consider the waypoint discovery method.  The basic approach is to use a binary latent variable VAE, using a recently proposed Hard Kumaraswamy distribution to model the latent state.  This seems like a reasonable approach, but there's no real analysis of the actual waypoints that are discovered in the target domains, whether they indeed correspond to intuitively important waypoints in a domain, or whether they are just producing some arbitrary segmentation of the proposed task.\n\nThe other elements of the paper have similar issues for me.  The whole HRL process, using these waypoint states as intermediate goals, seems reasonable, but it's hard to disentangle the performance of this particular approach versus the performance of any approach that would use (any) intermediate states as goals within an HRL approach.  And the impression I'm left with, given the level of detail included I the paper, is that I would have no idea how to apply or extend this process to any other RL domains.\n\nI looked at the provided code hoping it would help to clarify some of the implementation details, but the code is not at all a complete collection of routines that could re-create the experiments.  Rather, the code just includes a few of the model architectures, which aren't really the important aspects of this work.  \n\nThus, I'm overall left with the impression that it's quite difficult to assess the contribution of this approach, and determine precisely which of the different proposed aspects is really contributing most to the improved performance.  I know there is some ablative analysis in the paper comparing the pi_g-init and G_w-traversal independently and together, but I'm more questioning the basic question of what each portion of the network is really learning.\n\nI'd be curious if the authors are able to clarify any of these points during their rebuttal.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyg4isEH9H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an interesting method to construct a world graph of helpful exploration nodes to provide “structured exploration”. This graph is used in an HRL structure based on the feudal net structure. While the method is very interesting the proposed method is designed to help learn good policies via a better exploration structure. This is a very important problem but I find that the environments this method is tested on in the paper can be easily solved using normal RL methods. It would be very important to evaluate the methods progress on more interesting problems with complex temporal structure. Potentially some of the tasks from the HIRO paper or better yet an assembly tasks or version of the clevr objects environment where multiple items need to be rearranged into a goal. One of the more advanced tasks from the Hierarchical Actor-Critic paper would also be a good option. It is also important to include more analysis of the amount of data needed to train the VAE and create the graph. This amount should be included in the evaluation results for the method.\n\nMore detailed comments:\n-\tThe last paragraph of the introduction that begins to explain the method is a bit confusing. More detail here would be helpful. How frequently do binary latent variables need to be selected for them to become nodes? Similar for adding edges.\n-\tIn Figure 1, there are many terms that have not been defined yet, \"pivotal state\", \"world graph traversal\"... It would help in understanding the figure if these were explained beforehand. The figure text is also very small.\n-\tThis work seems very similar to Search on the replay buffer (Eysenbach et al 2019). That work created a graph over the data in the replay buffer based on the Q value of different states. These act as waypoints in planning. Could this method not be used to also construct a more sparse waypoint graph to use such as what is described in this work?\n-\tIt is said that the primary goal of the graph is to accelerate downstream tasks. Yet, the graph is constructed with states that are most critical in recovering action sequences.  Is there some guarantee that this selection criterion will help downstream tasks?\n-\tThe method also seems to have a similarity to the GoExplore paper that keeps around an exploration frontier, that is similar to the world graph, of states as it is making progress on the task. This paper should be discussed in more detail in the related work.\n-\tThe VAE is trained over data that is collected from the policy during exploration. Is there an issue with collecting data that will extrapolate to explore areas of the state space that are outside of the data collected for training the VAE.\n-\tMore detail should be included in the use of \\mu_0. As it is written now it is difficult for the reader to understand how the method works without some of the additional information in the appendix.\n-\tThe method to collect enough data to learn and represent a graph the covers the state space well. How well does this method work? Essentially this method is making progress on the exploration problem. Is there some analysis on how well this method is at collecting enough data to use on downstream tasks?\n-\tThe method uses curiosity to help explore the state space by using the reconstruction error from the VAE as an intrinsic reward. Is a version of this intrinsic reward use for the baseline A2C method in the paper? \n-\tIt is said that the world graph helps accelerate learning via structured exploration. However, there is there a significant amount of compute and environment interaction to compute the world graph? This should be taken into consideration when performing any comparisons.\n-\tCan the graph be updated during the policy training phase? Also, in the first phase where data is collected to fit the VAE, can this data be used to train an off-policy method? It seems like this data would work very well for training a policy.\n-\tTable 3 does not seem to be referenced in the paper. They could also use some additional explination as to what the values represent that are being presented.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeOJlV3FS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel approach to hierarchical reinforcement learning approach by first learning a graph decomposition of the state space through a recurrent VAE and then use the learned graph to efficiently explore the environment. The algorithm is separated into 2 stages where in the first stage random walk and goal conditioned policy is used to explore the environment and simultaneous use a recurrent binary VAE to compress the trajectory. The inference network is given the observation and action and the reconstruction is to, given the hidden state or hidden state+observation, reconstruct the action taken. The approximate posterior takes on the form of a hard Kumaraswamy distribution which can differentiably approximate a binary variable; when the approximate posterior is 0, the decoder must reconstruct the action using the hidden state alone. The nodes of the world graph are roughly states that are used to reconstruct the trajectories in the environment. After the graph is constructed, the agent can use a combination of high-level policy and classical planning to solve tasks with sparse reward.\n\nPersonally, I quite like the idea of decomposing the world into important states -- it is closely related to the concept of empowerment [1] which the authors might want to take a further look into. I believe extracting meaningful abstraction from the environment will be a key component for general purpose RL agent. One concept I really like in the paper is using the reconstruction error as the reward for the RL agent, which has some flavors of adversarial representation learning. Further, I also really like the idea of doing structured exploration in the world graph and I believe doing so can help efficiently solve difficult tasks.\n\nHowever, I cannot recommend accepting this paper in its current draft as there might be potential major technical flaw and I also have worries about the generality of the algorithm. My main concerns are the following:\n    1. The ELBO given in the paper is wrong -- the KL divergence should be negative. I want to give the paper the benefit of doubts since this could be just a typo and some (very rare) researchers use a reverse convention; however, this sign is wrong everywhere in the paper including the appendix yet the KL between Kuma and beta distributions uses the regular convention. I tried to check the source code provided by the authors but the code only contains architecture but not the training objective, training loops or environments. As such, I have to assume that the ELBO was wrongfully implemented, unless the author can provide the full source code, or, if the ELBO is indeed incorrectly implemented, rerun the experiments with the correct implementation.\n\n    2. The proposed method for learning the graph does not have to be a VAE at all. The appendix shows that the paper uses a 0.01 coefficient on the KL, which is an extremely small value for VAE (in fact, most VAE’s have beta larger than 1 for disentanglement). Thus, I suspect the KL term is not actually doing anything; instead, the main reason why the model worked might be due to the sparsity constraints L_0 and L_T. In other words, the model is simply behaving like a sequence autoencoder with some sort of hard attention mechanism on the hidden code, which might explain why the model still worked well even with the wrong ELBO. To clarify, I think this is a perfectly acceptable approach for learning the graph and it would still be very novel, but the manuscript should be revised accordingly to reflect this. If the (fixed) VAE is important, then this comparison (0 KL regularization) would be a nice ablation regardless.\n\n    3. Algorithm 1 requires navigating the agent to the key points from \\mathcal{V}_p. This assumption is quite strong. When the transition dynamic is deterministic and fully reversible like the ones considered in the paper, using the reverse of replay buffer can indeed take the agent back to s_p, but in settings where the transitions are stochastic or the transitions are non-linear or non-reversible, how should the algorithm be used?\n\n    4. It is not clear how \\mathcal{V}_p are maintained. If multiple new nodes are added every iteration, wouldn't there be more than necessary nodes in \\mathcal{V}_p? It seems to me some pruning criteria were used unless the model converged within small number of iterations? Are the older ones are discarded in favor of newer ones?\n\n    5. How are the actions sequences “normalized”?\n\n    6. In what way are the Door-Key environment stochastic? It seems like the other environments also have randomness, so is the only difference the lava pool?\n\nI believe the propose method is sound, so if the revision can address either 1 or 2, I am willing to raise my score to weakly accept. If the revision in addition addresses 3, 4, 5, 6 in a reasonable manner, I am willing to raise my score to accept.\n\n=======================================================================\nMinor comments that did not affect my decision:\n    - I think mentioning the names of the environment in the abstract might be uninformative since the readers do not know what they are a priori.\n\nReference:\n[1] Empowerment -- An Introduction, Salge et al. 2014\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces an approach for structured exploration based on graph-based representations.  While a number of the ideas in the paper are quite interesting and relevant to the ICLR community, the reviewers were generally in agreement about several concerns, which were discussed after the author response. These concerns include the ad-hoc nature of the approach, the limited technical novelty, and the difficulty of the experimental domains (and whether the approach could be applied to a more general class of challenging long-horizon problems such as those in prior works). Overall, the paper is not quite ready for publication at ICLR.
Decision: Reject