Meta Reinforcement Learning with Autonomous Inference of Subtask Dependencies
Authors: Sungryull Sohn
Hyunjae Woo
Jongwook Choi
Honglak Lee
Venue:  (2020)
Keywords: Meta reinforcement learning
subtask graph

Abstract: We propose and address a novel few-shot RL problem, where a task is characterized by a subtask graph which describes a set of subtasks and their dependencies that are unknown to the agent. The agent needs to quickly adapt to the task over few episodes during adaptation phase to maximize the return in the test phase. Instead of directly learning a meta-policy, we develop a Meta-learner with Subtask Graph Inference (MSGI), which infers the latent parameter of the task by interacting with the environment and maximizes the return given the latent parameter. To facilitate learning, we adopt an intrinsic reward inspired by upper confidence bound (UCB) that encourages efficient exploration. Our experiment results on two grid-world domains and StarCraft II environments show that the proposed method is able to accurately infer the latent task parameter, and to adapt more efficiently than existing meta RL and hierarchical RL methods.

Published as a conference paper at ICLR 2020
META REINFORCEMENT LEARNING WITH AUTONOMOUS INFERENCE OF SUBTASK DEPENDENCIES
Sungryull Sohn'
Hyunjae Woo'
Jongwook Choi
Honglak Lee?:
University of Michigan
Google Brain
(srsohn, hiwoo, jwook J@umich. edu
honglak@googles com
ABSTRACT
We propose and address novel few-shot RL problem, where a task is characterized by a subtask graph which describes set of subtasks and their dependencies that are unknown to the agent. The agent needs to quickly adapt to the task over few episodes during adaptation phase maximize the return in the test phase. Instead of directly learning a meta-policy, we develop a Meta-learne with Subtask Graph Inference (MSGI), which infers the latent parameter of the task by interacting with the environment and maximizes the return given the latent parameter. To facilitate learning, we adopt an intrinsic reward inspired by upper confidence bound (UCB) that encourages efficient exploration. Our experiment results two grid-world domains and StarCraft II environments show that the proposed method is able accurately infer the latent task parameter, and to adapt more efficiently than existing meta RL and hierarchical RL methods
INTRODUCTION
Recently, reinforcement learning (RL) systems have achieved super-human performance on many complex tasks (Mnih et al.) 2015 Silver et al. [0166] Van Seijen et al.) 2017). However, these works mostly have been focused on a single known task where the agent can be trained for a long time (e.g.. Silver et al. (2016). We argue that agent should be able to solve multiple tasks with varying sources of reward. Recent work in multi-task RL has attempted to address this; however, they focused on the setting where the structure of task are explicitly described with natural language instructions (Oh) eet al. (2017] [Andres et al. 2017]] Yu et al. [2017] Chaplot et al.) 2018), programs (Denil et al.) (2017). or graph structures (Sohn al.) 2018). However, such task descriptions may not readily available. A more flexible solution is to have the agents infer the task by interacting with the environment. Recent work in Meta RI. (Hochreiter et al., 2001 Duan et al. 2016 Wang et al.) 2016: Finn et al., 2017) (especially in few-shot learning settings) has attempted to have the agents implicitly infer tasks and quickly adapt to them. However, they have focused on relatively simple tasks with a single goal (e.g., multi-armed bandit, locomotion, navigation, etc.).
We argue that real-world tasks often have hierarchical structure and multiple goals, which require long horizon planning or reasoning ability (Frol) 1996 Xu et al., 20177] Ghazanfari & Taylor] [017] Sohn et al. 2018). Take, for example, the task of making a breakfast in Figure 1 A meal can be served with different dishes and drinks (e.g., boiled egg and coffee), where each could be considered as a subtask. These can then be further decomposed into smaller substask until some base subtask (e.g., pickup egg) is reached. Each subtask can provide the agent with reward; if only few subtasks provide reward, this is considered a sparse reward problem. When the subtask dependencies are complex and reward sparse, learning an optimal policy can require large number of interactions with the environment. This is the problem scope we focus on in this work: learning to quickly infer and adapt to varying hierarchical tasks with multiple goals and complex subtask dependencies.
To this end, we formulate and tackle a new few-shot RL problem called subtask graph inference problem, where the task is defined as a factored MDP (Boutilier et al., 1995 Jonsson & Barto 2006) with hicrarchical structure represented by subtask graph (Sohn et a 20118) where the task is not known a priori. The task consists of multiple subtasks, where each subtask gives reward when completed (see Figure 1). The complex dependencies between subtasks (i.e., preconditions) enforce agent to execute all the required subtasks before can execute certain subtask. Intuitively, the agent can efficiently solve the task by leveraging the inductive bias of underlying task structure (Section 2.2)
'The demo videos are available at

---

Published as a conference paper at ICLR 2020
Adaptation (exploration) udapt mg
Subtask Graph Inference é = ILP(r)
Test (expioitation)
~ test
Tir TK
FK
2
H
Pickup
Pickup
Pickup
Put
Use
T
Put
FK
in
Pickup
Pickup
Pickup
Boll
Preseettion
Put
Put
Use
F1
Suttos
in
Update
Inferred subtask graph G
C= Σn
+ 0 VoL
Figure 1: Overview of our method the context of prepare breakfast task. This task can be broken down into subtasks (e.g.. pickup mug) that composes the underlying subtask graph G. (Left) To learn about the unknown lask, the agent collects trajectories over K episodes through parameterized adaptation policy sdapi that learns explore the environment. (Center) With each new trajectory, the agent attempts infer the task's underlying ground- truth subtask graph G with G. (Right) separate test policy "G uses the inferred subtask graph G produce a trajectory that attempts to maximize the agent's 's reward > rz (e.g.. the green trajectory that achieves the boil egg subtask). The more precise G, the more reward the agent would receive, which implicitly improves the adaptation policy %0
degu to hetter explore the environment and therefore better infer G in return.
Inspired by the recent works on multi-task and few-shot RI., we propose a meta reinforcement learning approach that explicitly infers the latent structure of the task (e.g., subtask graph). The agent learns its adaptation policy to collect as much information about the environment as possible in order to rapidly and accurately infer the unknown task structure. After that, the agent's test policy is contextual policy that takes the inferred subtask graph as an input and maximizes the expected return (See Figure Th. We leverage inductive logic programming (ILP) technique derive efficient task inference method based on the principle of maximum likelihood. To facilitate learning, we adopt an intrinsic reward inspired by upper confidence bound (UCB) that encourages efficient exploration. We evaluate our approach on various environments ranging from simple grid-world (Sohn et al.) (2018) to StarCraft (Vinyals al., 2017). In all cases, our method can accurately infer the latent subtask graph structure, and adapt more efficiently to unseen tasks than the baselines.
The contribution of this work can be summarized as follows:
We propose new meta-RL problem with more general and richer form of tasks compared to the recent meta-RL approaches.
We propose an efficient task inference algorithm that leverages inductive logic programming, which accurately infers the latent subtask graph from the agent's experience data.
We implement a deep meta-RL agent that efficiently infers the subtask graph for faster adaptation.
We compare our method with other meta-RL. agents on various domains, and show that our method adapts more efficiently to unseen tasks with complex subtask dependencies.
2 PROBLEM DEFINITION
2.1 BACKGROUND: FEW-SHOT REINFORCEMENT LEARNING
task is defined by an MDP MG = (8, A. Pc, RG) parameterized by a task parameter G with a set of states S, a set of actions A. transition dynamics Pc. reward function Rg. In the K-shot RL formulation (Duan et al. 2016 Finn et al., 2017). each trial under a fixed task Mg consists of an adaptation phase where the agent learns task-specific behavior and a test phase where the adapted behavior is evaluated. For example, RNN-based meta-learners (Duan et al. 2016 Wang et al. 2016) adapt task Mg by updating its RNN states (or fast-parameters) d.,, where the initialization and update rule of Φ: is parameterized by a slow-parameter 0: de = g(0), Φ = fØr; (). Gradient- based meta-learners (Finn et al.) 20177] Nichol al. 2018) instead aim learn good initialization of the model so that it can adapt to a new task with few gradient update steps. In the test phase, the agent's 's performance on the task Mg is measured in terms of the return:
RMa (TTn)
EmEEy Ma
Σ H'
11=1
(1)
2

---

Published as a conference paper at ICLR 2020
Algorithm 1 Adaptation policy optimization during meta-training
Require: p(G):
distribution over subtask graph
1: while not done do
2: Sample batch of task parameters {G:] p(G)
3: for all G2 in the batch do
4:
Rollout episodes r = (st of, Ft. de ~ no in task Ma.
> adaptation phase
5:
Compute rt as in Eq.
6:
G, = -TI((T) Sample T'
b subtask graph inference
7:
T G.
exe in task Mc.
b test phase
8: Update 0 - 0 + Vo E Ra
udaps
using
RM
PG- in Eq.
where The is the policy after K episodes (or H update steps) of udaptation, H' is the horizon of test phase, and 7; is the reward time in the test phase. The goal is find an optimal parameter 0 that maximizes the expected return EG [R
( (Toy))
over given distribution of tasks p(G).
2.2 THE SUBTASK GRAPH INFERENCE PROBLEM
We formulate the subtask graph inference problem, an instance of few-shot RL problem where task is parameterized by subtask graph (Sohn et al.) 2018). The details how a subtask graph parameterizes the MDP is described in Appendix B Our problem extends the subtask graph execution problem in (Sohn et al. 2018) by removing the assumption that a subtask graph is given to the agent; thus, the agent must infer the subtask graph in order to perform the complex task. Following few-shot RL settings, the agent's 's goal is to quickly adapt to the given task (i.e., MDP) in the adaptation phase maximize the return in the test phase (see Figure D A task consists of N subtasks and the subtask graph models hierarchical dependency between subtasks.
Subtask: A subtask & can be defined by a tuple (completion set Stomp C S. precondition G S + {0, 1}. subtask reward function G S + -R). A subtask d' is complete if the current state is contained in its completion set (i.e., S; E St ). and the agent receives reward rt G upon the completion of subtask Φ' A subtask T' is eligible (i.e., subtask can be executed) if its precondition G is satisfied (see Figure for examples). A subtask graph is a tuple precondition and subtask reward of all the subtasks: G (Ge, G.). Then, the task defined by the subtask graph is factored Patrascu 2002); i.e., the transition model factored as p(s'ls,a) II, Pc: (s s, a) and the reward function is factored as R(s,a) = Σ, RG, (s, a) (see Appendix for the detail). The main benefit factored MDP is that it allows us to model many hierarchical tasks in a principled way with compact representation such dynamic Bayesian network (Dean & Kanazawa
MDP (Boutilier et al.) 1995 Schuurmans
1989 Boutilier et al., 1995). For each subtask T', the agent can learn an option O' (Sutton al. 1999b) that executes the subtask
Environment: The state input to the agent at time step consists of [x,, et, step,, epi,, obs:)-
Completion: x, E {0, 1 indicates whether each subtask complete.
Eligibility: E {0, 1) indicates whether each subtask is eligible (i.e., precondition is satisfied).
Time budget: step, E IR is the remaining time steps until episode termination.
Episode budget: epi, E IR is the remaining number of episodes in adaptation phase.
Observation: obs, E R x is a (visual) observation at time t.
At time step f, we denote the option taken by the agent o and the binary variable that indicates whether episode is terminated as dz.
3 METHOD
We propose Meta-learner with Subtask Graph Inference (MSGI) which infers the latent subtask graph G. Figure overviews our approach. Our main idea is to employ two policies: adaptation policy and test policy. During the adaptation phase, adaptation policy ng
adapt rolls out K episodes
2 As in Andreas et al. 2017 Oh et al. 2017) Sohn et al. (0188). such options are pre-learned with curriculum learning: the policy is learned by maximizing the subtask reward, and the initiation set and termination condition are given as I (s) 1) and 3 T(x²
3

---

MLE = arg max Published as a conference paper at ICLR 2020
Input luu
Agent trajectory
Subtask
00000
X
CART
Decision tree
Precondition A
Inferred subtask graph
10000
Thue
A
11000
Logic expression
Bulld
0
00000
1100
11110
10000
11100
Decision tree of
recondition of
2
11000
1100
Subtask
Input out
3g-0
AB BC
H 11110 11111
ABCDE
00000
CART
Cp=0
Simplity
10000
train
Logic expression
Bulld
11000
X
AB
ABC
A
11110
Figure 2: Our inductive logic programming module infers the precondition G. from adaptation trajectory. For example, the decision tree of subtask E (bottom row) estimates the latent precondition function for e by fitting its input-output data (i.e., agent's trajectory {x, e ) The decision is constructed choosing a variable (i.e., component of x) at each node best splits the data. The learned decision trees of subtasks are represented as logic expressions, and then transformed and merged to form subtask graph.
of adaptation trajectories. From the collected adaptation trajectories, the agent infers the subtask graph G using inductive logic programming (ILP) technique. test policy n/ conditioned on the inferred subtask graph G, rolls out episodes and maximizes the return in the test phase. Note that the performance depends the quality of the inferred subtask graph. The adaptation policy indirectly contributes to the performance by improving the quality of inference. Intuitively, if the adaptation policy completes more diverse subtasks during adaptation, the more "training data" is given the ILP module, which results in more accurate inferred subtask graph. Algorithm summarizes our meta-training procedure. For meta-testing, see Algorithm 2 in Appendix
3.1 SUBTASK GRAPH INFERENCE
Let тH {s1, episodes (or H steps in total) in adaptation phase. The goal is to infer the subtask graph G for this task, specified by preconditions Ge and subtask rewards G,- We find the naximun-likellhood estimate (MLE) of G (Ge, Gr) that maximizes the likelihood of the adaptation trajectory TH: GALL arg maxG.. C, p(TH Gey G,).
01, 01,
d1. .i....,,p1 }h} be adaptation trajectory of the adaptation policy To
udapt for K
The likelihood term can expanded as
P[TH|Ge, p(si
II
To
or, Ge)p(re(ss, Gr)p(d:(ss,
(2)
t=1
H
x G(s
II
p(5 st oz (s, t=1
33)
where we dropped the terms that are independent of From the definitions in Section 2.2 precondi- tion Ge defines the mapping x + and the subtask reward G, determines the reward as r G, if
subtask is eligible (i.e., e; = 1) and option O' executed at time t. Therefore, we have
H p(o./xx Ge), arg max G.
И p(elee. or G.,
MLE
MLLE GMLE)-
arg max G.
(4)
We note that supervision from the ground-truth subtask graph G is used. Below we explain how to compute the estimate of preconditions GMLE and subtask rewards GALE.
Precondition inference via logic induction Since the precondition function fa. x (see Section 2.2 definition) is a deterministic mapping, the probability term p(e, Ge) in Eq is 1 if c; fa. (xx) and ( otherwise. Therefore, we can rewrite GMLE in Eq.04) as:
I I(ee fx.():)). G. 1=1
(5)
where I(-) is the indicator function. Since the eligibility e factored, the precondition function fa. for each subtask is inferred independently. We formulate the problem of finding a boolean function
4

---

Published as a conference paper at ICLR 2020
that satisfies all the indicator functions in Eq. (i.e.. (=1 I[ee = fae (x,) = 1) as an inductive logic programming (ILP) problem (Muggleton, 1991, Specifically. {x+] |i=1 forms binary vector inputs programs, and {e; forms Boolean- valued outputs of the i-th program that denotes the eligibility of the i-th subtask. We use the classification and regression tree (CART) to infer the precondition function fc. for each subtask based on Gini impurity (Breiman 1984). Intuitively, the constructed decision tree is the simplest boolean function approximation for the given input-output pairs (xe, er). Then, we convert form to build the subtask graph. Figure 2 summarizes the overall logic induction process.
logic expression (i.e., precondition) in -um-of-product (SOP)
Subtask reward inference To infer the subtask reward function GALEE in Eq. we model each component of subtask reward as Gaussian distribution G. ~ N N( o²). Then, PMILE becomes the empirical mean of the rewards received after taking the eligible option O² in the trajectory TH:
M...E M'LE = TE [relo; = 0² oe, = =1] Σ Ty ro((o, =
(6)
Σ 21=1 I(o, = Oi = =1)
3.2
TEST PHASE: SUBTASK GRAPH EXECUTION POLICY
Once a subtask graph G has been inferred, we can derive a subtask graph execution (SGE) policy " (o|x) that aims to maximize the cumulative reward in the test phase. Note that this is precisely the problem setting used in |Sonn et al. (2018). Therefore, we employ a graph reward propagation (GRProp) policy (Sohn et al. 2018) as our SGE policy. Intuitively, the GRProp policy approximates subtask graph to a differentiable form such that we can compute the gradient of modified return with respect to the completion vector to measure how much each subtask is likely to increase the modified return. Due space limitation, give detail of the GRProp policy in Appendix
3.3 LEARNING: OPTIMIZATION OF THE ADAPTATION POLICY
adapt or its parameters 0. We can directly We now describe how to learn the adaptation policy Te optimize the objective R. (Iz) using policy gradient methods (Williams) 1992 /utton et al. 1999a).
such actor-critic method with generalized advantage estimation (GAL) (Schulman et al. 2011))
However, we find challenging to train our model for two reasons: 1) delayed and sparse reward (i.e., the return in the test phase is treated as if it were given as a one-time reward at the last step of adaptation phase), and 2) large task variance due to highly expressive power of subtask graph. To facilitate learning, we propose to give an intrinsic reward r UCB to agent in addition to the extrinsic environment reward, where r is the upper confidence bound (UCB) (Auer et al. 2002)-inspired exploration bonus term follows:
log(n' (0) + m())) n²(ett
UCB
WUCB I(x; is novel), WUCB
where N is the number of subtasks, ef is the eligibility of subtask i at time t, and n' n'(e) is the visitation count of ex (i.e., the eligibility of subtask i) during the adaptation phase until time (. The weight wVcB is designed encourage the agent make eligible and execute those subtasks that have infrequently been eligible, since such rare data points in general largely improve the inference by balancing the dataset that CART (i.e., our logic induction module) learns from. The conditioning term Il(x, is novel) encourages the adaptation policy to visit novel states with a previously unseen completion vector x, (i.e., different combination of completed subtasks), since the data points with same X, input will be ignored in the ILP module as duplication. We implement I(x; is novel) using a hash table for computational efficiency. Then, the intrinsic objective is given as follows:
RMG
adapt
E edupe R,,aaar
.Ma
DE=1"
JCB
(8)
where H is the horizon of adaptation phase. Finally, we train the adaptation policy x actor-critic method with GAE (Schulman al. (016)) to maximize the following objective:
adaat using an
R Ma
PG+UCB
T
adapt)
RMa
GRProp)) (
+ SUCB
R
UCB Ma
TT
adapt
and G is the inferred subtask graph that depends on the adaptation policy = The complete procedure for training MSGI agent with UCB reward is summarized in Algorithm
where RMa (-) is the meta-learning objective in Eq. SUCB is the mixing
5

---

Published as a conference paper at ICLR 2020
4 RELATED WORK
Meta Reinforcement Learning. There are roughly two broad categories of meta- meta-RL approaches:
gradient-based meta-learners (Finn et al.) 2017] Nichol et al. 2018 Gupta et al. 2018 Finn et al.) 2018
2018. Kim et al. 2018) and RNN-based meta-learners (Duan al. 20 6 Wang al. 2016). Gradient- based meta RL algorithms, such as MAML (Finn et al. (017) and Reptile (Nichol et al. 2018). learn the agent's policy by taking policy gradient steps during an adaptation phase, where the meta-learner aims to learn a good initialization that enables rapid adaptation to an unseen task. RNN- based meta-RI. methods (Duan et al., (016; Wang et al., 2016) updates the hidden states of a RNN as process of adaptation, where both of hidden state initialization and update rule are meta-learned. Other variants of adaptation models instead of RNNs such as temporal convolutions (SNAIL) (Mishra et al. 2018) also have been explored. Our approach is closer to the second category, but different from existing works as we directly and explicitly infer the task parameter.
Logic induction. Inductive logic programming systems (Muggleton| [991) learn set of rules from examples. (Xu et al. (017) These works differ from ours as they are open-loop LPI; the input data to LPI module is generated by other policy that does not care about ILP process. However, our agent learns a policy to collect data more efficiently (i.e., closed-loop ILP) There also have been efforts to combine neural networks and logic rules deal with noisy and erroneous data and seek data efficiency, such as (Hu et al. 2016 Evans & Grefenstette 2017 Dong et al. (019).
Autonomous Construction of Task Structure. Task planning approaches represented the task structure using Hierarchical Task Networks (HTNs) (Tate) 1977). HTN identifies subtasks for a given task and represent symbolic representations of their preconditions and effects, to reduce the search space of planning (Hayes & Scassellati| 2016). They aim to execute a single goal task, often with assumptions of simpler subtask dependency structures (e.g., without NOT dependency (Ghazanfari Liu
Taylor 2017: Liu et al.) (016)) such that the task structure can be constructed from the successful trajectories. contrast, we tackle a more general and challenging setting, where each subtask gives a reward (iee,, multi setting) and the goal is to maximize the cumulative sum of reward within an episode. More recently, these task planning approaches were successfully applied to the few-shot visual imitation learning tasks by constructing recursive programs (Xu et al. 2017] graph (Huang) ct al., 2018). Contrary to them, we employ an active policy that seeks for experience useful in discovering the task structure in unknown and stochastic environments.
5 EXPERIMENTS
In the experiment, we investigate the following research questions: (1) Does MSGI correctly infer task parameters G? (2) Does adaptation policy mo the of UCB bonus facilitate training? (See Appendix
adupt improve the efficiency of few-shot RL? (3) Does H.T) (4) How well does MSGI perform
compared with other meta-RL algorithms? (5) Can MSGI generalize to longer adaptation horizon, and unseen and more complex tasks?
We evaluate our approach in comparison with the following baselines:
Random is a policy that executes random eligible subtask that has not been completed.
RL2 2 the meta-RI. agent Duan al. (2016). trained to maximize the return over K episodes.
HRL is the hierarchical RL agent in Sohn et al. (2018) trained with the same actor-critic method as our approach during adaptation phase. The network parameter is reset when the task changes.
GRProp+Oracle is the GRProp policy (Sohn et al. 20188) provided with the ground-truth subtask graph as input. This is roughly an upper bound of the performance MSGI-based approaches. MSGI-Rand (Ours) uses a random policy an adaptation policy, with the task inference module. MSGI-Meta (Ours) uses a meta-learned policy (i.e., n inference module.
ddupi as an adaptation policy, with the task
For RL2 and HRL, we use the same network architecture as our MSGI adaptation policy. More details of training and network architecture can be found in Appendix [] The domains which evaluate these approaches include two simple grid-world environments (Mining and Playground) (Sohn)
et al. 2018) and more challenging domain SC2LE (Vinyals al. 2017) (StarCraft IT).
5.1
EXPERIMENTS ON MINING AND PLAYGROUND DOMAINS
Mining (Sohn et al. 2018 is inspired by Minecraft (see Figure where the agent receives reward by picking up raw materials in the world crafting items with raw materials. Playground (Sohn et al.)

---

Published as a conference paper at ICLR 2020
Observation
Subtaak graph
Tonntber
Trandoredd
Transbey
Pick
Thrafom P
Rotums=0.000 Rowardsv0.00
A visual illustration of Playground domain and example of underlying subtask graph. The goal is to execute subtasks in the optimal order to maximize the reward within time budget. The subtask graph deseribes subtasks with the conresponding rewards (c.g., transforming a chest gives 0.1 reward) and dependencies between subtasks through AND and OR nodes. For instance, the agent must first trunsform chest AND transform diamond before executing pick up duck. Right: A warfare scenario in SC2LE domain (Vinyals et al. [017)) The agent must prepare for the upcoming warfare by training appropriate units, through appropriate order of subtasks (see Appendix for more details).
Figure 3: Left:
2018) is a more flexible and challenging domain, where the enviromment is stochastic and subtask graphs are randomly generated (i.e., precondition is an arbitrary logic expression). We follow the setting in Sohn et al. (018)) for choosing train/evaluation sets. We measure the performance in terms of normalized reward R = (R- R /(Raxx Rmin) averaged over 4 random seeds, where Rmin and Rmux correspond to the average reward of the Random and the GRProp+Oracie agent, respectively.
5.1.1 TRAINING PERFORMANCE
Figure shows the learning curves of MSGI-Meta and RL?, trained on the D1-Train set of Playground domain. We set the adaptation budget in each trial to K = 10 episodes. For MSGI-Rand and HRL (which are not meta-learners), we show the average performance after 10 episodes of adaptation. As training goes on, the performance of MSGI-Meta significantly improves over MSGI-Rand with large margin. It demonstrates that our meta adaptation policy learns to explore the environment more efficiently, inferring subtask graphs more accurately. We also observe that the performance of RL agent improves over time, eventually outperforming the HRL agent. This indicates that RL3 learns 1) good initial policy parameter that captures the common knowledge generally applied to all the tasks and 2) an efficient adaptation scheme such that it can adapt to the given task more quickly than standard policy gradient update in HRL.
Playground (D1)
0.8
Meta-Meta(Gur))
0.6
(Ourss)
0.4
RL
0.3
0.2
0.1
0.0
0
2
4 5
7
Trial (thousand)
Figure 4: Learning curves the Playground domain. We mea- sure the normalized reward (y- axis) in test phase, after a certain number of training trials (x-axis).
5.1.2 ADAPTATION AND GENERALIZATION PERFORMANCE
Adaptation efficiency. In Figure we measure the test performance (in terms of the normalized reward R) by varying episode budge K (i.e., how many episodes are used in adaptation phase), after 8000 trials of meta-training (Figure 4). Intuitively, it shows how quickly the agent can adapt to the given task. Our full algorithm MSGI-Meta consistently outperforms MSGI-Rand across all the tasks, showing that our meta adaptation policy can efficiently explore informative states that are likely to result in more accurate subtask graph inference. Also, both of our MSGI-bbaedd models perform better than HRL and RL2 baselines in all the tasks, showing that explicitly inferring underlying task structure and executing the predicted subtask graph is more effective than learning paraameters and tast-parameters (e.g., RNN states) on those tasks involving complex subtask dependencies.
Generalization performance. We test whether the agents can generalize over unseen task and longer adaptation horizon, as shown in F For Playground, we follow the setup of (Sohn et al., 2018): we train the agent on D1-Train with the adaptation budget of 10 episodes, and test on unseen graph distributions D1-Eval and larger graphs D2-D4 (See Appendix for more details about the tasks in Playground and Mining). We report the agent's 's performance as the normalized reward with up to 20 episodes of adaptation budget. For Mining, the agent is trained on randomly generated graphs with 25 episodes budget and tested on 440 hand-designed graphs used in (Sohn et al., 2018), with up to
7

---

Published as a conference paper at ICLR 2020
1.0
Playground (D1)
1.0
Playground (D2)
1.0
Playground (D3)
0.8
0.8
0.8
0.6
0.6
0.6
22
0.2
0.2
0.0
0.0
0.0
10
15
20
5
10
15
20
10
15
20
Budget (episodes)
Budget (episodes)
Budget (episodes)
Playground (D4)
1.0
Mining
1.0
0.8
0.8
MSGl-Meta(Ours) (Ours)
0.6
0.6
0.4
HRL
0.2
0.2
RL
0.0
5
0.0
0
Budget (episodes)
Budget (episodes)
Figure 5: Generalization performance on unseen tasks (D1-Eval, D2, D3, D4, and Mining-Evar with varying adaptation horizon. We trained agent with the fixed adaptation budget (K 10 for Playground and K 25 for Mining) denoted by the vertical dashed line, and tested with varying unseen adaptation budgets. We report the average normalized return during test phase, where GRProp+Oracle the upper bound (i.e., R = 1) and Random is the lower bound (i.e., R = 0). The shaded area in the plot indicates the range between R + and a where a is the standard error of normalized return.
R
Build BattieCrulsse
Zerglings
Defeat Hydralisks
Defeat Hydra- Ultra-lisks
Jig successs rate
1.0
1.0
1.0
1.0
0.8
0.8
0.8
0.8
0.6
Avg. win
0.6
Avg. wih
0.6
0.4
MSGI-GRProp (Ours)
HRL
0.2
0.2
0.2
0.2
Random
0.0
0.0
0.0
0.0
10
20
10
15
20
10
15
20
20
Adaptation (episodes)
Adaptation (episodes)
Adaptation (episodes)
Adaptation (episades)
Figure 6: Adaptation performance with diffcrent adaptation horizon on SC2LE domain.
50 episodes of adaptation budget. Both of our MSGI-baser models generalize well to unseen tasks and over different adaptation horizon lengths, continuingly improving the agent's performance. It demonstrates that the efficient exploration scheme that our meta adaptation policy can generalize to unseen tasks and longer adaptation horizon, and that task execution policy, GRop, generalizes well to unseen tasks as already shown in (Sohn et al. 2018). However, RL3 fails to generalize to unseen task and longer adaptation horizon: on D2-D4 with adaptation horizons longer than the length the heea-eearmer was trained for, the performance of the RL* agent is almost stationary or even decreases for very long-horizon case (D2, D3, and Mining), eventually being surpassed by the HRL agent. This indicates (1) the adaptation scheme that RL2 learned does not generalize well to longer adaptation horizons, and (2) a common knowledge learned from the training tasks does not generalize well to unseen test tasks.
5.2 EXPERIMENTS ON STARCRAFT II DOMAIN
SC2LE (Vinyals al. 2017) is a challenging RL domain built upon the real-time strategy game StarCraft II. We focus on two particular types of scenarios: Defeat Enemy and Build Unit. Each type of the scenarios models the different aspect of challenges in the full game. The goal of Defeat Enemy is to eliminate various enemy armies invading within 2,400 steps. We consider three different combinations of units with varying difficulty: Defeat Zerglings, Defeat Hydralisks, Defeat Hydralisks & Ultraisks (see Figure | and demo videos at https: / /btt..itttt... httpyy/mmmmaaaaeeeee visaiiiviin vedos)).. The goal of Build Unit scenario is to build a specific unit within 2,400 steps. To showcase the advantage of MSGI infering the underlying subtask graph, we set the target unit as Battlecruiser, which is at the highest rank in the technology tree of Terran race. In both scenarios, the agent needs to train the workers, collect resources, and construct buildings and produce units in correct sequential order to win the game. Each building or unit has a precondition as per the technology tree of the player's 's race (see and Appendix B for more details).
Figure and
8

---

Published as a conference paper at ICLR 2020
Agents. Note that the precondition of each subtask is determined by the domain and remains fixed across the tasks. we train the meta agents (MSGI-Meta and RL²). the agents memorize the subtask dependencies (i.e., over-fitting) and does not learn any useful policy for efficient adaptation. Thus, we only evaluate Random and HRL as our baseline agents. Instead of MSGI-Meta, we used MSGI- GRProp. MSGI-GRProp uses the GRProp policy as an adaptation policy since GRProp is good approximation algorithm that works well without meta-training as shown in (Sohn et al. (0118). Since the environment does not provide any subtask-specift reward, we set the subtask reward using the UCB bonus term in Eq. 7 to encourage efficient exploration (See Appendix for detail).
Subtask graph inference. We quantitatively evaluate the inferred subtask graph in terms of the precision and recall of the inferred precondition function fa x é. Specifically, we compare the inference output ē with the GT label generated by the GT precondition function fe X + e for all possible binary assignments of input (i.c.. completion vector x). For all the tasks, our MSGI-GRProp agent almost perfectly infers the preconditions with more than 94% precision and 96% recall of all possible binary assignments, when averaged over all 163 preconditions in the game, with only 20 episodes of adaptation budget. We provide the detailed quantitative and qualitative results the inferred subtask graph in supplemental material.
Adaptation efficiency. Figure 6 shows the adaptation efficiency of MSGI-GRProp, HRL agents, and Random policy on the four scenarios. We report the average victory or success rate over episodes. MSGI-GRProp consistently outperforms HRL agents with a high victory rate, by (1) quickly figuring out the useful units and their prerequisite buildings and (2) focusing on executing these subtasks in correct order. For example, our MSGI-GRProp learns from the inferred subtask graph that some buildings such as sensor tower or engineering buy are unnecessary for training units and avoids constructing them (see Appendix F for the inferred subtask graph).
6 CONCLUSION
We introduced and addressed a few-shot RL problem with complex subtask dependencies. We proposed to learn the adaptation policy that efficiently collects experiences in the environment, infer the underlying hierarchical task structure, and maximize the expected reward using the execution policy given the inferred subtask graph. The empirical results confirm that our agent can efficiently explore the environment during the adaptation phase that leads to better task inference and leverage the inferred task structure during the test phase. In this work, we assumed that the option is pre- learned and the environment provides the status of each subtask. In the future work, our approach may be extended to more challenging settings where the relevant subtask structure is fully learned from pure observations, and options to execute these subtasks are also automatically discovered.
ACKNOWLEDGMENTS
We would like to thank Wilka Carvalho for valuable feedback on the manuscript. This work was partly supported by Institute for Information & communications Technology Promotion (ITPP) grant funded by the Korea government (MSIT) (No. 2016-0-00563, Research on Adaptive Machine Learning Technology Development for Intelligent Autonomous Digital Companion) and Korea Foundation for Advanced Studies.
REFERENCES
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In ICML, 2017.
Peter Auer, Nicolo Cesa-Bianchi. and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-256 2002.
M.K. Bloch. Hierarchical reinforcement learning in the taxicab domain. (Report No. CCA-TR-2009. 02). Ann Arbor, MI: Center for Cognitive Architecture, University of Michigan, 2009.
Craig Boutilier, Richard Dearden, Moises Goldszmidt, et al. Exploiting structure in policy construc- tion. In IJCAI, volume 14, pp. 1104-1113, 1995.
Leo Breiman. Classification and regression trees. Routledge, 1984.

---

Published as a conference paper at ICLR 2020
Devendra Singh Chaplot, Kanthashree Mysore Sathyendra, Rama Kumar Pasumarthi, Dheeraj Rajagopal, and Ruslan Salakhutdinov. Gated-attention architectures for task-oriented language grounding. In AAAI, 2018.
Thomas Dean and Keiji Kanazawa. A model for reasoning about persistence and causation. Compu- tational intelligence, 5(2):142-150, 1989.
Misha Denil, Sergio Gómez Colmenarejo, Serkan Cabi, David Saxton, and Nando de Freitas. Pro- grammable agents. arXiv preprint
2017.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In ICLR, 2019.
Yan Duan, John Schulman, Xi Chen, Peter Bartlett, llya Sutskever, and Pieter Abbeel. RI 2: Fast reinforcement learning via slow reinforcement learning, arXiv preprint arXiv:1611.0277,, 2016.
Kutluhan Erol. Hierarchical task network planning: formalization, analysis, and implementation. PhD thesis, 1996.
Richard Evans and Edward Grefenstette. Learning Explanatory Rules from Noisy Data. arXiv preprint arXiv:1711. 171.044444 2017.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1126-1135. JMLR. org, 2017.
Chelsea Finn, Kelvin Xu, and Sergey Levine. Probabilistic model-agnostic meta-lcarning. In NeurIPS, pp. 9516-9527, 2018
Behzad Ghazanfari and Matthew Taylor. Autonomous extracting hicrarchical structure of tasks in reinforcement learning and multi-task reinforcement learning. arXiv preprint (tf:::1700.047777. 2017.
Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, and Sergey Levine. Meta- reinforcement learning of structured exploration strategies. arXiv preprint 1rXiv:1802.00245. 2018.
Bradley Hayes and Brian Scassellati. Autonomously constructing hierarchical task networks for planning and human-robot collaboration. In 2016 IEEE International Conference Robolics and Automation (ICRA). pp. 5469-5476. IEEE, 2016.
Sepp Hochreiter, A Steven Younger, and Peter R Conwell. Learning to learn using gradient descent. In International Conference on Artificial Neural Networks, pp. 87-94. Springer, 2001.
Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing. Harnessing deep neural networks with logic rules. arXiv preprint 18X 2016.
De-An Huang, Suraj Nair, Danfei Xu, Yuke Zhu, Animesh Garg, Li Fei-Fei, Silvio Savarese, and Juan Carlos Niebles. Neural task graphs: Generalizing to unseen tasks from single video demonstration. arXiv preprint 188vv:887.00348. 2018.
Anders Jonsson and Andrew Barto. Causal graph based decomposition of factored mdps. Journal of Machine Learning Research, 7(Nov) 2006.
Taesup Kim, Jaesik Yoon, Ousmane Dia, Sungwoong Kim, Yoshua Bengio, and Sungjin Ahn. Bayesian model-agnostic meta-learning, arXiv preprint arXiv:1806.03836 2018
Eric Kolve, Roozbeh Mottaghi, Winson Han, Eli VanderBilt, Luca Weihs, Alvaro Herrasti, Daniel Gordon, Yuke Zhu, Abhinav Gupta, and Ali Farhadi. A12-THOR: An Interactive 3D Environment for Visual AI. arXiv, 2017.
Changsong Liu, Shaohua Yang, Sari laba-Sadiya, Nishant Shukla, Yunzhong He, Song-chun Zhu, and Joyce Chai. Jointly learning grounded task structures from language instruction and visual demonstration. In EMNLP, 2016.
10

---

Published as a conference paper at ICLR 2020
Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel. A simple neural attentive meta- learner. In ICLR, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-5333 2015.
Stephen Muggleton. Inductive logic programming. New Gen. Comput. 8(4):295-318, Fobruar 1991. ISSN 0288-3635. doi: 10.1007/BF03037088, UtLbttp://dd http:///00..oll..o/100000000 BFC3037089
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-lcariing algorithms. arXiv preprint arXiv: arXiv:/803.000 1803.02999 2018.
Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli. Zero-shot task generalization with multi-task deep reinforcement learning. In ICML, 2017.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research,
12:2825-2830 2011.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. ICLR, 2016.
Dale Schuurmans and Relu Patrascu. Direct salee-approximation for factored MDPs. In NIPS, pp. 1579-1586, 2002.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484
2016.
Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hierarchical reinforcement learning for zero-shot generalization with subtask dependencies. In NeurlPS, pp. 7156-7166, 2018.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In NIPS, 1999a.
Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and Mimi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):111-1111 1999b.
Austin Tate. Generating project networks. In Proceedings of the 5th international joint conference on Artificial intelligence- Volume 2, pp. 388-893. Morgan Kaufmann Publishers Inc., 1977.
Harm Van Seijen, Mehdi Fatemi, Joshua Romoff, Romain Laroche, Tavian Barnes, and Jeffrey Tsang. Hybrid reward architecture for reinforcement learning. In NIPS, pp. 5392-54022 2017.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets. Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft II: A challenge for reinforcement learning. arXiv preprint arXiv: /708.04787 2017.
Jane X Wang. Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. arXiv preprint 1XXi::611..07666 2016.
Ronald J Williams. Simple statistical mandient-folloiing algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-22) 256, 1992.
Danfei Xu, Suraj Nair. Yuke Zhu, Julian Gao, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Neural task programming: Learning generalize across hierarchical tasks. arXiv preprint
17Xiv=1710.018.. 2017.
Haonan Yu, Haichao Zhang, and Wei Xu. A deep compositional framework for human like language acquisition in virtual environment. arXiv preprint arXiv: 1703.09703.0983 2017.
11

---

Published as a conference paper at ICLR 2020
Appendix: Meta Reinforcement Learning with Autonomous Inference of Subtask Dependencies
A SUBTASK GRAPH AND FACTORED MDP
A.1 BACKGROUND: FACTORED MARKOV DECISION PROCESSES
A factored MDP (FMDP) (Boutilier et al. 1993, Jonsson & Barto 2006) an MDP M (S,A,P, R). where the state space S is defined by a of discrete state variables s = {s} ,...,, 54) Each state variable s E takes on a value in its domain D(s*). The state set S is a (subset of) Cartesian product of the domain of all state variables X X5 Ds')) In FMDP, the state variables s
are conditionally independent, such that the transition probability can be factored as follows:
p(S++1 [8t, a+) = p(s'+1 (S,, Or (((())(((2 6 [st, .x)...p($f++ p(5(++
(S,, dz).
(10)
Then, the model of FMDP can be compactly represented by the subtask graph (Sohn et al.
2018 or
dynamic Bayesian network (DBN) (Dean & Kanazawa 1989 Boutilier et al., 1995). They represent the transition of each state variable p( SS, at) in either a Boolean expression (i.e., subtask graph)
or binary decision tree (i.e., DBN). For more intuitive explanation, see the subtask graph paragraph
in Section 2.2 and Figure D
Jonsson & Barto 2006): [Sohn et al. (2018) suggested that the factored MDP can extended to the option framework. Specifically, the option is defined based on the change in state variable (e.g..
completion of subtask in |Sohn et al. (2018). ). and the option transition model and option reward function are assumed to be factored. Similar to Eq. [0, the transition probability can be factored as follows:
pls'|s, o) = I[((sss,,
R(s, = ER
(11)
In (Sohn al. 2018 the option O' completes the subtask E6 by definition; thus, p(>[|s, 0 and R (s. 0) = 0 +
O By introducing the cligibility vector e, the transition and reward functions are further expanded as follows:
p(a||x,0= 00) = = 1)p(e, = =1xx,
(12)
R'(x, = 0²) G,' 1),
(13)
where pla/le; = 1) indicates that the subtask is completed a/ the subtask is eligible e; = 1, p(e; |x) is the precondition G., and I(e, 1) indicates that the reward is given only if the subtask is eligible.
B DETAILS OF TASK IN SUBTASK GRAPH INFERENCE PROBLEM
For self-containedness, we repeat the details of how the task (i.e., MDP) is defined by the subtask graph G from (Sohn et al. 2018). We define each task as an MDP tuple MM = (S,A, Pa. Ro PG. 7) where S is set of states, A is set of actions, Pa : S x A x S - [0, 1] is task-specific state transition function, Rs : S x A + IR is a task-specific reward function and pa S - [0. 1] is a task-specific initial distribution over states. We describe the subtask graph G and each component of MDP in the following paragraphs.
Subtask and Subtask Graph Formally, subtask कi is tuple (completion S C S, precondition G subtask reward G e R). The subtask 4' is eligible (i.c., subtask can be executed) if the precondition G is satisfied (see the State Distribution and Transition Function paragraph below for detail). The subtask कt is complete if the current state is in the completion set E S and the agent receives the reward r, ~ -(G;)). Subtasks are shared across tasks. The subtask graph is tuple of precondition and subtask reward of N subtasks: G (Ge, G,) (see Appendix B for the detail). One example of subtask graph is given in Figure A subtask graph G a tuple of the subtask reward G2 -. and the precondition Ge of N subtasks.
State The state s, consists of the observation obs, E {0, 1W the completion vector X; {0, 1) the eligibility vector e, {0. 1)N the time budget step, E R and number of episode left during the adaptation epi, E R. An observation obs, is represented as H x W x C' tensor, where H and W are the height and width of map respectively, and C is the number of object types in
12

---

Published as a conference paper at ICLR 2020
the domain. The (h, w, c))th element of observation tensor is if there is an object in (h, w) on the map, and 0 otherwise. The time budget indicates the number of remaining time-steps until the episode termination. The completion vector and eligibility vector provides additional information about N subtasks. The details of completion vector and eligibility vector will be explained in the following paragraph.
State Distribution and Transition Function Given the current state (obs,, Xt, et), the next step state (obs++1, Xx+1, is computed from the subtask graph G. Figure desccrbbs the dependency between subtask graph and MDP. the beginning episode, the completion vector X initialized to zero vector in the beginning of the episode Xo = = .o...... 0] and the observation obsy is sampled from the task-specific initial state dis- tribution Pa- Specifically, the observation is generated by randomly placing the agent and the N objects corresponding to the N subtasks defined the subtask graph G. When the agent executes subtask the i-th element of completion vector updated by the following update rule:
O2
X
X(+1
Tt
1+t
Gr
Figure 7: Dependency between subtask graph and MDP
if
=
(14)
zit
otherwise
The observation is updated such that agent moves on to the target object, and perform corresponding primitive action. The eligibility vector 6++1 is computed from the completion vector X and precondition Go as follows:
4+1
OR jEChild:
(VAND):
(15)
VAND AND jEChild,
(1+1)
(16)
x + (1 - x1+1)(1 w)))), 6+1
(17)
where wish = if there is a NOT connection between i-th node and j-th node, otherwise w 1, and whi's are defined by the Ge. Intuitively, 2. = 1 when j-th node does not violate the precondition of i-th node. Executing each subtask costs different amount of time depending on the map configuration. Specifically, the time cost is given as the Manhattan distance between agent location and target object location in the grid-world plus one more step for performing a primitive action.
Task-specific Reward Function The reward function is defined in terms of the subtask reward vector G2 E IR, and the eligibility vector C₁, where the subtask reward vector G, is the component of subtask graph G the and eligibility vector is computed from the completion vector x; and subtask graph G as Eq. 17 Specifically, when agent executes subtask i, the amount of reward given to agent time step / is given as follows:
Tt n= G
if otherwise
e e
(18)
Learning option The option framework can be naturally applied to the subtask graph-based tasks. Consider the (optimal) option O' = (I', =5 8²) for subtask Φ' Its initiation set is Z' {s/e' = 1}. where s is the state, is the i-th component of eligibility vector e, and e is an element of s. The termination condition is 3 I(x} 1), where x' is the i-th component of completion vector x. The policy n² maximizes the subtask reward G Similar to Andreas et al. (2017): Oh et al. (2017): Sohn al. 20118) the option for each subtask is pre-learned via curriculum learning; i.e., the agent learns options from the tasks consisting of single subtask by maximizing the subtask reward.
13

---

Published as a conference paper at ICLR 2020
C DETAILS OF THE PLAYGROUND AND MINING DOMAIN
For self-containedness, we provide the details of Playground and Mining (Sohn al. 2018 domain. Table [ summarizes the complexity of the subtask graph for each task sets in Playground and Mining domain.
Subtask Graph Setting
Playground
Mining
Task
1>2
1)4
Eval
Depth
4
4
6
4-10
Subtask
15
16
16
10-26
Table 1: (Playground) The subtask graphs in D1 have the same graph structure as training set, hut the graph unseen. The subtask graphs in D2, D3, and D4 have (unseen) larger graph structures. (Mining) The subtask graphs in Eval are during training.
Observation
Subtask graph
Legend
Obji
(OI)
AND:
LOURS
10.00
NOT:
Blgitic
Varee stare chaai
subtask stanus
Ineligible
Bucoess
coo
Light
Seret sliver
Iron
Slap=61/81
Retu m. Flewar==00.73
Mate Vo0 pickaxe
14.55
Figure example observation and subtask graph of the Mining domain (Sohn et al. 2018). The precondition of each subtask has semantic meaning based on the Minecraft game, which closely imitates the real-world tasks.
Subtasks The set of subtasks in Playground and Mining are implemented as Aint X X, where Aint is set of interactions with objects, and X' is set of all types of interactive objects in the domain. execute a subtask (aint, obj) E Aint x X, the agent should move on to the target object obj and take the primitive action dint.
Mining The Mining (Sohn et al. 2018) is a domain inspired by Minecraft (see Figure X for example task). The agent may pickup materials scattered in the world. The obtained raw materials may be used to craft different items on different craft stations. There are two forms of preconditions: 1) item may be ingredient for building other items (e.g. stick and stone ingredients of stone pickaxe), and 2) an item may be a required tool to pick up some objects (e.g. agent need stone pickaxe mine iron ore). To simplify the environment, it assumes that the agent can use the item multiple times after picking it once. The subtasks in the higher layer in task graph are designed to give larger reward. The pool of subtasks and preconditions are hand-coded similar to the crafting recipes in Minecraft, and used as template to generate 640 random task graphs. Following (Sohn et al. 2018). we used 200 for training and 440 for testing.
The Playground (Sohn et al. 2018) domain is more flexible domain (see Figure 3 left) which is designed to evaluate the strong generalization ability of agents on unseen task de- pendencies under delayed reward in stochastic environment. More specifically, the task graph in Playground was randomly generated, hence its precondition can be any logical expression. Some of the objects randomly move, which makes the environment stochastic. The agent trained small
Playground
14

---

Published as a conference paper at ICLR 2020
task graphs that consists of 4 layers of task dependencies, while evaluated on much larger task graphs that consists of up to 6 layers of task dependencies (See Table I]. Following (Sohn et al. (2018), we randomly generated 500 graphs for training and 500 graphs for testing. The task in the playground domain is general such that it subsumes many other hierarchical RI. domains such as Taxi (Bloch 2009), Minecraft (Oh et al. 2017) and XWORLD (Yu et al. 2017).
D ALGORITHM IN
The Algorithm 2
describes the process of our MSGI at meta-testing time for single trial.
Algorithm 2 Process of single trial for a task Mg at meta-test time
Require: The current parameter
Require: A task Mg parametrized by task parameter G (unknown to the agent)
1: Roll out K train episodes
{St, O2, Tt, de }
To adapt in task MG
adaptation phase
2: Infer a subtask graph: G (Ge, G.)
(L((TT),R((TT))
task inference
3: Roll out a test episode r' = {s/, of r/. d/ ~ G in task Mc
> test phase
4: Measure the performance R = E, rk for this task
E DETAILS OF THE SC2LE DOMAIN
The SC2LE domain (Vinyals et al. 2017) provides suite of mini-games focusing on specific aspects of the entire StarCraft II game. In this paper, we custom design two types of new, simple mini-games called Build Unit and Defeat Zerg troops. Specifically, we built Defeat Zerglings, Defeat Hydralisks, Defeat Hydralisks Ultraiikss and Build Battlecruiser nami- that compactly capture the most fundamental goal of the full game. The Build Unit mini-game requires the agent to figure-out the target unit and its precondition correctly, such that can train the target unit within the given short time budget. The Defeat Zerg troops mini-game mimics the full game more closely; the agent is required to train enough units to win a war against the opponent players. To make the task more challenging and interesting, we designed the reward to be given only at the end of episode depending on the success of the whole task. Similar to the standard Melee game in StarCraft II, each episode is initialized with 50 mineral, 0 gas, 7 and 4 SCVs that start gathering mineral and gas, respectively, 1 idle SCV, refinery, and 1 Command Center (See Figure 9). The episode is terminated after 2,400 environment steps (equivalent to 20 minutes in game time). In the game, the agent is initially given 50 mineral, 0 gas, 7 and 4 SCVs that start gathering mineral and gas, respectively, 1 idle SCV, 1 refinery. and Command Center (See Figure 9 and is allowed to prepare for the upcoming battle only for 2,400 environment steps (equivalent to 20 minutes in game time). Therefore, the agent must learn to collect resources and efficiently use them to build structures for training units. All the four custom
share the same initial setup specified in Figure 9
Defeat Zerg troops scenario: At the end of the preparation, different combinations of enemy unit appears: Defeat Zerglings and Defeat Hydralisks has 20 zerglings and 15 hydralisks, respectively, and Defeat Hydralisks & Ultralisks contains combination of total hydralisks and 3 ultralisks. When the war finally breaks out, the units trained by the agent will encounter the army of Zerg units in the map and combat until the time over (240 environment steps or 2 minutes in the game) or either side is defeated. Specifically, the agent may not take any action, and the units trained by the agent perform an auto attack against the enemy units. Unlike the original full game that has ternary reward structure of +1 (win)/ / 0 (draw) / -1 (loss), we use binary reward structure of +1 (win) and -1 (loss or draw). Notice that depending on the type of units the agent trained, a draw can happen. For instance, if the units trained by the agent are air units that cannot attack the ground units and the enemy units are the ground units that cannot attack the air units, then no combat will take place, so we consider this case as a loss. Build unit scenario: The agent receives the reward of +1 1 if the target unit is successfully trained within the time limit, and the episode terminates. When the episode terminates due to time limit, the agent receives the reward of -1. We gave 2,400 step budget for the Build Battlecruiser scenario such that only highly efficient policy can finish the task within the time limit.
15

---

Published as a conference paper at ICLR 2020
The transition dynamics (I.e., build tech-tree) in SC2LE domain has hierarchical characteristic which can be inferred by our MSGI agent (see Figure 9 We conducted the experiment on Terran race only, but our method can be applied to other races as well.
Subtask. There are 85 subtasks: 15 subtasks of constructing each type of building (Supply depot, Barracks, Engineeringbay, Refinery, Factory, Missile turret, Sensor tower, Bunker, Ghost academy, Armory, Starport, Fusioncore, Barrack-techlab, Factory-techlab, Starport-techlab), 17 subtasks of training each type of unit (SCV, Marine, Reaper, Marauder, Ghost, Widowmine, Hellion, Hell- bat, Cyclone, Siegetank, Thor, Banshee, Liberator, Medivac, Viking, Raven, Battlecruiser), one subtask of idle worker, 32 subtasks of selecting each type of building and unit, gathering min- eral, gathering gas, and no-op. For gathering mineral, we set the subtask as (mineral val) where vol E {50, 75, 100, 125, 150, 300, 400). Similarly for gathering gas, we set the subtask (gas2 val) where val {25, 50, 75, 100, 125, 150, 200, 300}. For no-op subtask, the agent takes the no-op ac- tion for 8 times.
Figure 9: (Top) The agent starts game initially with limited resources of minerals, gases. 3 foods, 11 SCVs collecting resources, idle SCV and pre-b Refinery. (Middle) From the initial state, the agent needs to strategically collect resources and build structures in order to be well prepared for the upcoming battle. (Bottom) After 2,400 environment steps, the war breaks; all the buildings in the map removed, and the enemy units appear. The agent's units should climinate the enemy units within 240 environment steps during the war.
16

---

Published as a conference paper at ICLR 2020
Eligibility, The eligibility of the 15 building construction subtasks and 17 training unit subtasks is given by the environment as an available action input. For the selection subtasks, we extracted the number of corresponding units using the provided API of the environment. Gathering mineral, gas, and no-op subtasks are always eligible.
Completion. The completion of the 15 construction subtasks and 17 training subtasks is 1 if the corresponding building or unit is present on the map. For the selection subtasks, the completion is 1 if the target building or unit is selected. For gathering mineral and gas subtasks, the subtask is completed if the condition is satisfied (i.e., gas2 50). The no-op subtask never completed.
Subtask reward. SC2LE domain, the agent does not receive any reward when completing a subtask. The only reward given agent is the binary reward r [+1,-1} at the end of episode (i.e.. t = H. Therefore, the subtask reward inference method described in Eq.(4) may not be applied. Instead, we tried to infer the subtask reward G2 E RV (see Section 3 for definition) from victory reward TH by building binary classifier that predicts the victory reward THe from the option count vector n NW using a logistic model (i.e., logistic regression), where N is the number of subtasks and the option count vector n counts how many times each option had been executed within an episode. Intuitively speaking, we assume that the execution of each subtask (i.e.. option) gives an implicit subtask reward that is un-observable by the agent, and the victory reward is determined by thresholding the sum of subtask rewards within an episode as follows:
TH I(, T B),
(19)
where TI()) is the indicator function and is the threshold. Then, we approximate it using sigmoid function (.) as follows:
TH = -G,
(20)
In the adaptation phase, we randomly sampled the subtask reward vector G, from the uniform distribution in [0. 1jA, and used it for running MSGI-GRRPop agent while recording the option count vector n. Then, the option count vectors n and the victory rewards T. from the K episodes in
adaptation phase form a training data ('g for estimating the parameters of logistic model as follows:
==
log
TH
G T B,
(21)
where Gg E A and | E IR are the weight and bias parameters be learned. Finally, we used the learned G2 as the subtask reward vector for running our MSGI-GRProp agent in test phase, We used the scikit-learn (Pedregosa et al. 2011) implementation of logistic regression.
F MORE RESULTS ON THE SC2LE DOMAIN
Accuracy of inferred subtask graph. Figure 10 shows the accuracy of the subtask graph inferred by MSGI-GRProp agent (Section 5.2 in terms of precision and recall over different adaption horizon.
Defeat Zerglings
Defeat Hydralisks
Defeat Hydra- & Ultra-lisks
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
Precision Recall
Precision Recall
Precision Recall
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
20
10
15
Episodes
Episodes
Episodes
Figure 10: Precision and recall of binary assignments on the inferred subtask graph's 's precondition.
Qualitative Examples. Figure 12 shows a simplified form of the subtask graph inferred by our MSGI- GRProp agent after 20 episodes of adaptation. For better readability, we removed the preconditions of resources (food, mineral, gas); Figure 13 depicts the full subtask graph. Compared to the actual tech-tree of the game, we can see the dependency between buildings and units are correctly inferred.
17

---

Published as a conference paper at ICLR 2020
Supply Depoe
Command Cender
Refinrry
Engineenin og
Gensor Tower
Miasla Turnes
Hilt
Barnecks
Punker Chers
Figure 11: The actual tech-tree of Terran race in StarCraft II. There exists hierarchy in the task, which can be autonomously discovered by our MSGI agent.
EhostArad
Reaper
Ghost
Barracks
satect
TechLab
Marauder
ComCenter
Marine
Thor
Armory
Tcchaa
oeiege
SupDapol
Barracka
ecttory
Eyclone
Selec Scv
Bunked
Starport
VidooMing
Iberotor
Hellion
Redivad
EnginBay
Misssssrrre Turret
Starport
select
c
Viking
SonsTower
FusionCore
Raven
Retneer
Bettlecrulse
Starport
TechLag
Banshed
Figure 12: A simplified version of subtask graph inferred by our MSGI-GRProp agent after 10 episodes of adaptation.
18

---

Published as a conference paper at ICLR 2020
100
100
MENSI
Figure 13: The full subtask graph inferred by MSGI agent.
19

---

Published as a conference paper at ICLR 2020
2.5
AI2THOR
2.0
1.5
HRL MSGI-GRProp(OUrs)
1.0
0.5
Random
0.0
10
15 20
Budget (episodes)
Figure 14: Adaptation performance of MSGI-GRProp, Random, and HRL agents with different adaptation horizon on AI2-THOR domain. The episode terminates after the agent executes 20 subtasks or when there is no subtask available to execute. Our MSGI-GRProp achieves around 2.5 total reward within episode by executing roughly two serve subtasks, while the baseline methods almost never get any reward.
G EXPERIMENT ON AI2-THOR DOMAIN
The A12-THOR (Kolve et al. 2017) is an interactive 3D environment where the agent can both navigate and interact with the objects within the environment through variety of actions that can change the states of the object (i.e., the PickupOhject action changes the object's 's isPickedUp state). Among the several scenes provided by the environment, we focus on the kitchen scene and evaluate agents on the task similar to the breakfast preparation task described in the introduction: The agent is required to prepare the dishes by directly manipulating the objects given in the scene. See Figure 15 for example task.
There are two different types of objects in the scene: The first type is the plain object (i.e., Bread, Apple, Potato, Tomato, Egg, Lettuce Cup, Mug, Plate, Pan, Bowl) that agents can move around with, and the second type the receptacle object (i.e., Pan, Plate, Bowl, Cabinet, Microwave, StoveBurner. CounterTop. tiningTable. SideTable. Toaster, CoffeeMachine. Fridge) which can contain other objects depending on their sizes. With these objects and the subtasks defined, the agent required to cook and serve foods through long sequence of subtasks. For instance, the agent can prepare fried egg dish by (I) placing a Pan object on StoveBurner, (2) placing Egg on Pan, (3) slicing (or, cracking) Egg to EggCrac,ed, (4) turning the StoveKnob to cook the cracked egg, and finally (5) serving the cooked Egg on the Plate. Rewards are given only when the agent successfully serves the cooked object on the appropriate receptacles. Similar to the SC2LE domain (see Section 5.2), the task structure in A12-THOR is fixed as well (i.e., Egg cannot be cooked in the Fridge), and thus instead of training meta agents, we evaluate and compare MSGI-GRProp. HRL, and Random agents on the cooking tasks. The visualization of the subtask graph (i.e., underlying task structure) inferred by MSGI-GRProp agent is available on the Figure 16
Subtask. There are total 148 subtasks: 17 subtasks for picking up all the possible objects in the scene (Tomato. Potato, Lettuce, Apple, Egg. Bread, TomatoSliced, PotatoSliced, SStcuceSliced, AppleSliced, EggCracked! BreadSliced, Pan, Plate, Cup, Mug, Bowl), 113 subtasks for putting down each pickupable objects into pre-defined putdownable receptacles, 6 subtasks for slicing the sliceable objects, 6 subtasks for cooking cookable objects or filling up liquid in the Mug or Cup, and 6 subtasks for serving the cooked or filled objects on the proper receptacles such as Plate, Bowl, and DiningTable.
Completion. The completion of the 17 pick up subtasks is if the corresponding object is in the agent's hand or inventory. For all the put down subtasks, the completion is 1 if the corresponding object is in the target receptacle (i.e.. TomatoSliced on Plate). For slice and cook subtasks, the completion is if the corresponding object is sliced or cooked, respectively. The serve subtasks are complete if the corresponding objects are placed on the target receptacles (i.e., Cooked PotatoSliced on Plate). When the agent executes the serve subtask, the served food is removed to simulate the user eating the served dish, such that the agent can execute the same serve subtask at most once within the episode.
Eligibility. The eligibility of the subtasks is computed based the corresponding subtask completion vector. The eligibility of the pickup subtasks is always set to 1, and the putdown subtasks are eligible the corresponding object is picked up (i.e., Pickup Tomato is complete). The slice subtasks are eligible if the sliceable objects on any receptacle. The cook subtasks are eligible if the cookable
20

---

Published as a conference paper at ICLR 2020
objects placed the corresponding cooking station (i.e., Mug is the CoffeeMachine). The eligibility of the serve subtasks is if the corresponding objects are either cooked or sliced.
Subtask reward. To make the task more challenging and realistic, we assigned non-zero reward only to the six Serve subtasks, that have the most complex precondition (i.e., sparse reward setting). Similar to other environments, we randomly set the subtask reward of each subtask from the predefined range when we sample new task (i.e., trial). Table (ooliffspecifiie the range of subtask reward for the six serve subtasks; intuitively speaking, we set higher subtask reward for the subtask that has more complex precondition.
Subtask name
Min reward
Max reward
Serve cooked potato
0.6
1.2
Serve cooked and sliced potato Serve cooked and sliced bread
1.0
2.0
1.0
2.0
Serve cooked and cracked egg
1.0
2.0
Serve coffee
0.6
1.2
Serve water
0.4
1.0
Table 2: The range from which the subtask reward of subtask sampled, in the A12-THOR environment.
Result. On the A12-THOR environment, we compared our MSGI-GRProp agent with two baseline agents: Random and HRL. Figure [4] summarizes the performance of each agent with varying adaptation budgets. We observed that both the Random and HRL agent almost never receives any non- zero reward during 20 episodes of adaptation, since the serve subtasks have complex precondition that is not easy to satisfy for random policy. In contrast, our MSGI SSSG-GRProp agent achieves around 2.4 total reward on average after 20 episodes of adaptation. As specified in Table 2 each serve subtask gives around 1.0~ 1.5 reward, so it means MSGI-GRProp agent executes around two serve subtasks within an episode. Also, considering that the minimum number of subtasks required for serve subtask around 6, being able to execute around two subtasks within only 20 steps means the agent does not waste its time for executing other subtasks that are irrelevant to the target serve subtasks. The HRL agent's performance does improve during adaptation since it seldom observes any reward. On the other hand, our MSGI-GRProp agent can quickly find a way to execute the serve subtasks by inferring the precondition them: as shown in Figure I6. our ILP module can accurately and efficiently infer the precondition of subtasks in AI2-THOR enviromment after only 20 episodes of adaptation.
21

---

Published as a conference paper at ICLR 2020
(a) Pick up Potato from Fridge.
(b) Slice Potato PotatoSliced.
Place PotatoSliced Pan and cook.
(d) Serve Cooked PotatoSliced on Plate.
Figure 15: (a) (d) demonstrates example task of preparing fried potato in the A12-THOR domain. The serve PotatoSliced pan (e.g.. (c)) before serving the dish. The agent receives reward after finishing the final subtask (e.g.. (d)) of serving the dish on the plate.
Plate subtask requires slicing potato (e.g., (b)) frying sliced potato on
22

---

Published as a conference paper at ICLR 2020
Figure 16: The subtask graph inforred by our MSGI-GRProp agent in the A12-THOR environment after 20 episodes.
23

---

Published as a conference paper at ICLR 2020
Playground (D1)
Mining
0.85
0.85
0.80
0.80
0.75
0.70
0.75
MSGI-Meta MSGI-Meta without UCB
0.65
0.60
0.65
0.50
0.60
3
Trial (thousand)
Trial (thousand)
Figure 17: Comparison meta- meta-training MSGI-Meta agent that was trained with UCB bonus and extrinsic reward. and MSGI-Meta without UCB agent that was trained with extrinsic reward only in the Playground and Mining domain. In both domains, adding UCB honus improves the meta-training performance of our MSGI-Meta agent.
H MORE RESULTS ON MINING AND PLAYGROUND
H.1 ABLATION STUDY ON THE INTRINSIC REWARD
We conducted ablation study comparing
MeGa with and without UCB bonus. We will refer our method with UCB bonus as MSGI-Meta, and our method without UCB bonus as MSGI-Meta without UCB. Figure 17 shows that UCB bonus facilitates the meta-training of our MSGI-Meta agents in both Playground and Mining domains.
H.2 QUALITATIVE RESULT ON THE SUBTASK GRAPH INFERENCE
Figure 18 illustrates a qualitative example of the inferred subtask graphs inferred by MSGI-Meta and MSGI-Rand agents on the Mining-Evar set. The adaptation budget was K 50 episodes and episode length was T = 80 steps. Both of MSGI-Meta and MSGI-Rand correctly inferred most of subtasks the lower hierarchy (e.g., Get stone, Cut wood, Get string) of the subtask graph. However, only MSGI-Meta was successful in inferring the preconditions of subtasks in the highest hierarchy (e.g., Smelt gold, Make goldware, and Craft necklace); MSGI-Rand never had an experience where their preconditions are all satisfied, and thus failed to learn the preconditions of these task. It demonstrates that MSGI-Meta with meta-learned adaptation policy is able to collect more comprehensive experience for accurate subtask graph inference.
H.3 QUANTITATIVE ANALYSIS OF THE ADAPTATION POLICY
We measured the portion of subtasks being eligible or completed at least once (i.c., coverage) during adapta- tion to measure how exploratory MSGI-Meta and ran- dom policy are. We report the averaged coverage over the evaluation graph and 8 random seeds. The table shows that MSGI-MMet can make more
Coverage (%)
Method
D1
D2
D3
D4
Eval
MSGI-Meta
89
87
81
75
90
MSGI-Rand
83
77
68
58
85
diverse subtasks complete and eligible than the random policy thanks to more accurate subtask graph inference.
24

---

Published as a conference paper at ICLR 2020
Get stone
Cut wood
Get string
+0.00
+0.31
+0.31
Make Frewood
Make stick
Make or
Make bow
10.11
10.10
(0/3
Make stame pickuaee
Marc stone piocaun
oig
Make frewood
Get coal
Oet
+0.55 56
10.30
-0.62
Gidl wlewe mo
iight furmac
iron
(C,00
Smrett siiver
-mrek iron
Smeet sliver
Make
A0l: Make pichace
0046
0.48
diamnd
Get +1.35
GGt slamond -2.41
12.35
.2.33
11.70
11.00
goltware
goldware
Craft
-5.00
+3.00
+2.2
(a) A ground-truth subtask graph.
(b) A subtask graph inferred by MSGI-Meta.
stone
Smell gold
Maie goldware
necklace
Make
0.17
Get coal
Make Frewood
Get
+0.02
+0.35
Light Surmice
Out wood
Get string
+0.50
-0.00
-0.15
+0.20
Make iron pklkaxe
Ht
Gct gold
ore
10.29
(c) subtask graph inferred by MSGI-Rand
Figure 18: qualitative example of subtask graph inference, in Mining domain.
25

---

Published as a conference paper at ICLR 2020
1 DETAILS OF GRPROP POLICY
For celf-containedness, we provide the description of GRProp policy from Sohn al. (0188. We
also make a few modifications on OR (x) and AND (x) in Eqs. 29 and 30
Intuitively, GRProp policy modifies the subtask graph to a differentiable form such that we can compute the gradient of modified return with respect to the subtask completion vector in order to measure how much each subtask is likely to increase the modified return. Let X be a completion vector and G, be subtask reward vector (see Section 2 for definitions). Then, the sum of reward until time-step is given as:
U/ = Gr X2.
(22)
We first modify the reward formulation such that gives half of subtask reward for satisfying the preconditions and the rest for executing the subtask to encourage the agent to satisfy the precondition of subtask with a large reward:
Ú. G. (x+ + e2)
(23)
Let SAND be the output of j-th AND node. The eligibility vector can be computed from the subtask graph G and x, as follows:
et
OR (VAND), V'ND
AND &EChild
* x w + NOT whih),
jEChild;
(24)
where wirk = 0 if there is NOT connection between j-th node and k-th node, otherwise with 1.
Intuitively, .4t 1 when k-th node does not violate the precondition of j-th node. The logical AND, OR, and NOT operations in Eq. 24 are substituted by the smoothed counterparts as follows:
p² AarE (1 Xar) x²,
(25)
き OR V jEChild,
(AND)
(26)
VAN VAND
AND (aS.M).
(27)
kEClold
gü.k w. Lh + (1 wilh w (p*).
(28)
where x E Rd is the input completion vector,
OR (x) = softmax worx) x) X,
(29)
AND (x) = C(x, Wand)
(30)
[[1|x]], Wand)
NOT (x) = WnotX
(31)
||x|| = d. ((xx(X B) = 1/2 log(1 + exp(3x)) is a soft-plus function, and Aor = 0.6, wor = 2, Wand = 3, Wast = 2 are the hyper-parameters parameters of GRProp. Note that we slightly modified the implementation of OR and AND from sigmoid and hyper-tangent functions in (Sohn et al. 2018)) to softmax and softplus functions for better performance. With the smoothed operations, the sum of smoothed and modified reward is given as:
ú, G, Tp.
(32)
where p - lp...... pd] and p¹ is computed from Eq, 25 Finally, the graph reward propagation policy is a softmax policy,
=Too Softmax U.) Softmax (TG, ((Aor ē + xxr))))))=
(33)
where we used the softmax temperature T - 40 for Playground and Mining domain, and linearly annealed the temperature from T = 1 to T = 40 during adaptation phase for SC2LE domain. Intuitively speaking. we act more confidently (i.e., higher temperature T') as we collect more data since the inferred subtask graph will become more accurate.
26

---

Published as a conference paper at ICLR 2020
Adaplation (K episodes)
phose
Input
architecture
Env
Env
r,
GNN
GRU
Concat
FC
(TTT)
exe
o|ss)
G
0
B
adapl
(0
ILP
GRU
FC
Concat
FC
-V)(T)
Figure 19: (Left) Our MSGI model and (Right) the architecture of adaptation policy m
IMPLEMENTATION DETAILS
J.1 DETAILS OF MSGI ARCHITECTURE
Figure 19 illustrates the architecture of our MSGI model. Our adaptation policy takes the agent's trajectory Tt (st, o,, rt, d,) at time step t as input, where = {obs, x, c, step, epi}. We used convolutional neural network (CNN) and gated rectifier unit (GRU) encode both the temporal and spatial information of observation input obs. For other inputs, we simply concatenated all of them along the dimension after normalization, and encoded with GRU and fully-connected (FC) layers. Finally, the flat embedding and observation embedding are concatenated with separate heads for the value and policy output respectively (See supplemental material for more detail).
Our MSGI architecture encodes the observation input using CNN module. Specifically, the ob- servation embedding is computed by Convl (16x Other inputs are all concatenated into a single vector, and fed to GRU(512). In turn, we extracted two flat embeddings using two separate FC(512) heads for policy and value outputs. For each output, the observation and flat embeddings and concate- nated into single vector, and fed FC(512)-FCCC for policy output and FC(512)-FCCI for value output, where d the policy dimension. We used ReLU activation function all the layers.
Conv4(32x3x3-11 1lata-a-i///-/aatnn-FFa (C(NN)CCC(111/U////
J.2 DETAILS TRAINING MSGI-META
Algorithm| D describes the code for training our MSGI-Meta model with and without UCB bonus term. In adaptation phase, measured the average performance over 4 episodes with parallel workers (i.e., average over 32
batch of 48 parallel environments. In test phase,
episodes). We used actor-critic method with GAE (Schulman al. 2016) follows:
VoL BGN-GPa
B
Vo log T
II (r))ah
sc+1
(34)
& 5 As (8++1) V77 (s:),
(35)
where we used the learning rate 1 0.002, 7 = 1, and X == 0.9. We used RMSProp optimizer with the smoothing parameter of 0.99 and epsilon of le-5. We trained our MSGI-Meta agent for 8000 trials, where the agent is updated after every trial. We used the best hyper-parametern chosen from the sets specified in Table 4 for all the agents. We also used the entropy regularization with annealed parameter Pen- We started from 8em 0.05 and linearly decreased it after 1200 trials until it reaches Bent 0 at 3200 trials. During training, we update the critic network minimize E[ (s.))) where Rg is the cumulative reward at time / with the weight of 0.03. We clipped the magnitude of gradient to be larger than 1.
J.3 DETAILS OF TRAINING RL AND HRL
For training RL2 and HRL, used the same architecture and algorithm with MSGI-Meta. For RL2 we used the same hyper-parameters except the learning rate = 0.001 and the critic loss weight of 0.005. For HRL, we used the learning rate 7 = 0.001 and the critic loss weight of 0. 12. We used the best hyper- parameters chosen from the sets specified in Table for all the agents.
27

---

Published as a conference paper at ICLR 2020
Hyperparameter
Notation
Methods
MSGI-Meta
RL
HRL
Learning Rate (LR)
"
2c-3
lc-3
le-3
LR multiplier
0.999
0.999
0.999
GAE
X
0.9
0.9
0.9
Critic
Beriiic
0.12
0.005
0.12
Entropy
Ben
0.1
1.0
0.03
UCB
BUCB
1.0
Architecture
(dnar, dgra)
(512, 512)
(512, 512)
(512, 512)
Table 3: Summary of hyper-parameter used for MSGI-Meta, RL and HRL agents.
Hyperparameter
Notation
Values
Learning rate (LR)
7
(1.0, 2.5, 5.0) (e-5 e-4, e-3)
LR multiplier
[0.96, 0.98, 0.99, 0.993, 0.996, 0.999, 1.0)
GAE
A
(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.98, 1.0)
Critic
Beiitic
(0.005, 0.01, 0.03, 0.06, 0.12, 0.25)
Entropy
Bem
[0.02, 0.05, 0.1, 0.5, 1.0, 2.0)
UCB
BUCB
(1.0, 3.0)
Architecture
(deats dgm)
((128, 128), (256, 256), (512, 512))
Table The range of paraeetasameters we searched over. did beam-scarch to find the hest parameter with the priority of 77 A, ,,, Beas (dma, dgm), IR-decay.
28


Reviews:
[{"review_id": "r1l0Qu3nKS", "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": "Summary\n-------------\nThe authors propose a novel meta-rl problem where hierarchical tasks are characterized by a graph describing all sub-tasks and their dependencies. They propose a meta-rl approach to meta-train a policy that quickly infers the subtask graph from new task data. The approach is compared to relevant baselines from both the meta-rl and hierarchical rl literature on complex domains. In particular, the authors consider a large-scale Startcraft II experiment which proves the efficiency and scalability of the proposed methodology.\n\nMajor Comments\n--------------\n\nMeta-rl is a relevant direction for reducing the sample-complexity of rl agents and scaling them to large domains. This work presents interesting and novel ideas in these settings. In particular, the few-shot rl problem with subtask dependencies seems quite interesting for both encoding and solving large hierarchical rl problems. The proposed meta-rl algorithm is sound and simple to understand. The paper is well-organized, though sometimes it is difficult to follow the formalisms due to a large number of different symbols introduced. The experiments are quite interesting and convincing. In particular, the Starcraft domain should address all concerns about the scalability and efficiency of the proposed approach. Some comments/questions follow.\n\n1. The state available to the agent includes the number of remaining time-steps and episodes. When/how are they used?\n\n2. The paper requires the reader to be quite familiar with some previous works (e.g., Section 3.2 requires to know Song et al. 2018 to understand the test phase). It would be good to add more background/details about these works (at least in the supplementary), so that the paper is more self-contained.\n\n3. In the Starcraft experiment, what is the difference between MSGI-meta and MSGI-GRProp? Furthermore, where is the \"oracle\" baseline (introduced in sec. 5) used in the experiments? I did not find any plot reporting it.\n\n4. The main limitation is that this approach requires options for each subtask to be provided before-hand. Do the authors think that the method is easily generalizable to learn such options as well? Furthermore, I realized this limitation only after reading the very last lines of the paper. Since this is of major importance, I believe it should be clearly stated much earlier.\n\nMinor Comments\n--------------\n1. First line of sec. 2.1: R_\\tau should be R_G\n2. I did not find a definition of o_t and d_t which appear, e.g., in Algorithm 1.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1lrmJG2tH", "reviewer": "AnonReviewer1", "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 new meta-reinforcement learning algorithm, MSGI, which focuses on the problem of adapting to unseen hierarchical tasks through interaction with the environment where the external reward is sparse. The authors make use of subtask graph inference to infer the latent subtask representation of a task through interacting with the environment using an adaptation policy and then optimize the adaptation policy based on the inferred latent subtask structure. Each task in the paper is represented as a tuple of subtask precondition and subtask reward, which are inferred via logic induction and MLE of Gaussians respectively. At meta-test time, MSGI rollouts a subtask graph execution (SGE) policy based on the graph inferred from the interactions between the environment and the adaptation policy. The authors also propose a UCB-inspired intrinsic reward to encourage exploration when optimizing the adaptation policy. Experiments are conducted on two grid-world domains as well as StarCraft II.\n\nOverall, this paper is mainly an extension of the prior work [1], which uses a subtask graph for tackling hierarchical RL problems. This work builds upon [1] by extending to meta-learning domains and studying generalization to new hierarchical tasks. While the contribution seems a bit incremental and the experimental setting is a bit unclear and limited to low-dimensional state space, the inference of task-specific subtask graphs based on past experiences and the proposal of a UCB-inspired reward shed some interesting insights on how to approach meta-hierarchical RL where long-horizon tasks and sparse rewards have been major challenges. Given some clarification on the experimental setup and additional results on more challenging domains in the author's response, I would be willing to improve my score.\n\nRegarding the experimental setup, the set of subtasks is a Cartesian product of the set of primitive actions and a set of all types of interactive objects in the domain, while the state is represented as a binary 3-dimensional tensor indicating the position of each type of objects. Such a setup seems a bit contrived and is limited to low-dimensional state space and discrete action space, which makes me doubt its scalability to high-dimensional continuous control tasks. It would be interesting to see how/if MSGI can perform in widely used meta-RL benchmarks in Mujoco. I also wonder how MSGI can be compared to newly proposed context-based meta-RL methods such as PEARL.\n\nAs for the results, the authors don't provide an ablation study on the UCB exploration bonus though they claim they would show it in the paper. Moreover, the result of GRProp+Oracle is also missing in the comparison. I also don't understand why MSGI-Meta and RL2 would overfit in the SC2LE case and are unable to adapt to new tasks. Is that a limitation of the method? The authors also introduce MSGI-GRProp in this setting, which is never discussed before, and claim that MSGI-GRProp can successfully generalize to new tasks. It seems that the authors don't use a meta-RL agent in order to get this domain to work. I believe more discussion on this part is needed.\n\n[1] Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hierarchical reinforcement learning for zero-shot\ngeneralization with subtask dependencies. In NeurIPS, pp. 7156–7166, 2018.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1eAkDUuKH", "reviewer": "AnonReviewer3", "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": "The main problem that is tackled here are tasks that have a main goal that can only be reached by solving prerequisite tasks. They test their method on a simple game and a very complex one. \n\nMethodology and novelty\nThe authors combine various techniques (subtask graph inference, gradient based meta-learning and inductive logic programming). It is not clearly stated if the authors combined techniques and/or if they invented a new one. What is the big difference from the work by Sohn et al. (2018)?\n\nExperiments\nThe authors evaluated one agent. It would have been better if they trained multiple agents and showed a performance distribution, so it is clear that the performance is not just achieved by luck (Fig 5.). \nThe video material showed clearly how the complex game (StarCraft II) was solved much quicker than a baseline model. \n\nPresentation\nFigure 3 does not give a description of the subtask graph (middle) and the StarCraft II. The video material clearly shows the performance of their method. Section 5.1.2 does not clearly explain the different datasets D1-D5 of Playground. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work formulates and tackles a few-shot RL problem called subtask graph inference, where hierarchical tasks are characterized by a graph describing all subtasks and their dependencies. In other words, each task consists of multiple subtasks and completing a subtask provides a reward. The authors propose a meta-RL approach to meta-train a policy that infers the subtask graph from any new task data in a few shots. Empirical experiments are performed on different domains, including Startcraft II, highlighting the efficiency and scalability of the proposed approach.

Most concerns of reviewers were addressed in the rebuttal. The main remaining concerns about this work are that it is mainly an extension of Sohn et al. (2018), making the contribution somewhat incremental, and that its applicability is limited to problems where subtasks are provided. However, all reviewers being positive about this paper, I would still recommend acceptance. 
Decision: Accept (Poster)