Year: 2020

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 1.

heading: 1 INTRODUCTION
text: Recently, reinforcement learning (RL) systems have achieved super-human performance on many complex tasks (Mnih et al., 2015; Silver et al., 2016; 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 et al., 2017; Andreas et al., 2017; Yu et al., 2017; Chaplot et al., 2018), programs (Denil et al., 2017), or graph structures (Sohn et al., 2018). However, such task descriptions may not readily be available. A more flexible solution is to have the agents infer the task by interacting with the environment. Recent work in Meta RL (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 a hierarchical structure and multiple goals, which require long horizon planning or reasoning ability (Erol, 1996; Xu et al., 2017; Ghazanfari & Taylor, 2017; 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 is sparse, learning an optimal policy can require a 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 hierarchical structure represented by subtask graph (Sohn et al., 2018) 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 it can execute a certain subtask. Intuitively, the agent can efficiently solve the task by leveraging the inductive bias of underlying task structure (Section 2.2).
1The demo videos are available at https://bit.ly/msgi-videos.
Inspired by the recent works on multi-task and few-shot RL, 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 a contextual policy that takes the inferred subtask graph as an input and maximizes the expected return (See Figure 1). We leverage inductive logic programming (ILP) technique to derive an 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 II (Vinyals et 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 a 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.

heading: 2 PROBLEM DEFINITION

heading: 2.1 BACKGROUND: FEW-SHOT REINFORCEMENT LEARNING
text: A task is defined by an MDPMG = (S,A,PG,RG) parameterized by a task parameter G with a set of states S, a set of actions A, transition dynamics PG, reward functionRG. In the K-shot RL formulation (Duan et al., 2016; Finn et al., 2017), each trial under a fixed taskMG consists of an adaptation phase where the agent learns a 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 to a taskMG by updating its RNN states (or fast-parameters) φt, where the initialization and update rule of φt is parameterized by a slow-parameter θ: φ0 = g(θ), φt+1 = f(φt; θ). Gradientbased meta-learners (Finn et al., 2017; Nichol et al., 2018) instead aim to learn a 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 performance on the taskMG is measured in terms of the return:
RMG(πφH ) = EπφH ,MG [∑H′ t=1 rt ] , (1)
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 {Gi}Mi=1 ∼ p(G) 3: for all Gi in the batch do 4: Rollout K episodes τ = {st,ot, rt, dt}Ht=1 ∼ π adapt θ in taskMGi . adaptation phase 5: Compute rUCBt as in Eq.(7) 6: Ĝi = ILP(τ) . subtask graph inference 7: Sample τ ′ ∼ πexe
Ĝi in taskMGi . test phase 8: Update θ ← θ + η∇θ ∑M i=1RPG+UCBMGi ( πadaptθ ) usingRPG+UCBM in Eq.(9)
where πφH is the policy after K episodes (or H update steps) of adaptation, H ′ is the horizon of test phase, and rt is the reward at time t in the test phase. The goal is to find an optimal parameter θ that maximizes the expected return EG[RMG(πφH )] over a given distribution of tasks p(G).

heading: 2.2 THE SUBTASK GRAPH INFERENCE PROBLEM
text: We formulate the subtask graph inference problem, an instance of few-shot RL problem where a task is parameterized by subtask graph (Sohn et al., 2018). The details of 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 goal is to quickly adapt to the given task (i.e., MDP) in the adaptation phase to maximize the return in the test phase (see Figure 1). A task consists of N subtasks and the subtask graph models a hierarchical dependency between subtasks. Subtask: A subtask Φi can be defined by a tuple (completion set Sicomp ⊂ S, precondition Gic : S 7→ {0, 1}, subtask reward function Gir : S → R). A subtask Φi is complete if the current state is contained in its completion set (i.e., st ∈ Sicomp), and the agent receives a reward rt ∼ Gir upon the completion of subtask Φi. A subtask Φi is eligible (i.e., subtask can be executed) if its precondition Gic is satisfied (see Figure 1 for examples). A subtask graph is a tuple of precondition and subtask reward of all the subtasks: G = (Gc, Gr). Then, the task defined by the subtask graph is a factored MDP (Boutilier et al., 1995; Schuurmans & Patrascu, 2002); i.e., the transition model is factored as p(s′|s, a) = ∏ i pGic(s ′ i|s, a) and the reward function is factored as R(s, a) = ∑ iRGri(s, a) (see Appendix for the detail). The main benefit of factored MDP is that it allows us to model many hierarchical tasks in a principled way with a compact representation such as dynamic Bayesian network (Dean & Kanazawa, 1989; Boutilier et al., 1995). For each subtask Φi, the agent can learn an option Oi (Sutton et al., 1999b) that executes the subtask2. Environment: The state input to the agent at time step t consists of st = {xt, et, stept, epit,obst}. • Completion: xt ∈ {0, 1}N indicates whether each subtask is complete. • Eligibility: et ∈ {0, 1}N indicates whether each subtask is eligible (i.e., precondition is satisfied). • Time budget: stept ∈ R is the remaining time steps until episode termination. • Episode budget: epit ∈ R is the remaining number of episodes in adaptation phase. • Observation: obst ∈ RH×W×C is a (visual) observation at time t. At time step t, we denote the option taken by the agent as ot and the binary variable that indicates whether episode is terminated as dt.

heading: 3 METHOD
text: We propose a Meta-learner with Subtask Graph Inference (MSGI) which infers the latent subtask graph G. Figure 1 overviews our approach. Our main idea is to employ two policies: adaptation policy and test policy. During the adaptation phase, an adaptation policy πadaptθ rolls out K episodes
2As in Andreas et al. (2017); Oh et al. (2017); Sohn et al. (2018), 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 Ii = {s|Gic(s) = 1} and βi = I(xi = 1)
of adaptation trajectories. From the collected adaptation trajectories, the agent infers the subtask graph Ĝ using inductive logic programming (ILP) technique. A test policy πtest
Ĝ , conditioned on the
inferred subtask graph Ĝ, rolls out episodes and maximizes the return in the test phase. Note that the performance depends on 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 to the ILP module, which results in more accurate inferred subtask graph. Algorithm 1 summarizes our meta-training procedure. For meta-testing, see Algorithm 2 in Appendix D.

heading: 3.1 SUBTASK GRAPH INFERENCE
text: Let τH = {s1,o1, r1, d1, . . . , sH} be an adaptation trajectory of the adaptation policy πadaptθ for K episodes (or H steps in total) in adaptation phase. The goal is to infer the subtask graph G for this task, specified by preconditions Gc and subtask rewards Gr. We find the maximum-likelihood estimate (MLE) of G = (Gc, Gr) that maximizes the likelihood of the adaptation trajectory τH : ĜMLE = arg maxGc,Gr p(τH |Gc, Gr). The likelihood term can be expanded as
p(τH |Gc, Gr) = p(s1|Gc) H∏ t=1 πθ (ot|τt) p(st+1|st,ot, Gc)p(rt|st,ot, Gr)p(dt|st,ot) (2)
∝ p(s1|Gc) H∏ t=1 p(st+1|st,ot, Gc)p(rt|st,ot, Gr), (3)
where we dropped the terms that are independent of G. From the definitions in Section 2.2, precondition Gc defines the mapping x 7→ e, and the subtask reward Gr determines the reward as rt ∼ Gri if subtask i is eligible (i.e., eit = 1) and option Oi is executed at time t. Therefore, we have
ĜMLE = (ĜMLEc , Ĝ MLE r ) =
( arg max
Gc H∏ t=1 p(et|xt, Gc), arg max Gr H∏ t=1 p(rt|et,ot, Gr)
) . (4)
We note that no supervision from the ground-truth subtask graph G is used. Below we explain how to compute the estimate of preconditions ĜMLEc and subtask rewards Ĝ MLE r .
Precondition inference via logic induction Since the precondition function fGc : x 7→ e (see Section 2.2 for definition) is a deterministic mapping, the probability term p(et|xt, Gc) in Eq.(4) is 1 if et = fGc(xt) and 0 otherwise. Therefore, we can rewrite Ĝ MLE c in Eq.(4) as:
ĜMLEc = arg max Gc H∏ t=1 I(et = fGc(xt)), (5)
where I(·) is the indicator function. Since the eligibility e is factored, the precondition function fGci for each subtask is inferred independently. We formulate the problem of finding a boolean function
that satisfies all the indicator functions in Eq.(5) (i.e., ∏H t=1 I(et = fGc(xt)) = 1) as an inductive logic programming (ILP) problem (Muggleton, 1991). Specifically, {xt}Ht=1 forms binary vector inputs to programs, and {eit}Ht=1 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 fGc 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 {xt, et}. Then, we convert it to a logic expression (i.e., precondition) in sum-of-product (SOP) form to build the subtask graph. Figure 2 summarizes the overall logic induction process.
Subtask reward inference To infer the subtask reward function ĜMLEr in Eq.(4), we model each component of subtask reward as a Gaussian distribution Gir ∼ N (µ̂i, σ̂i). Then, µ̂iMLE becomes the empirical mean of the rewards received after taking the eligible option Oi in the trajectory τH :
ĜMLE,ir = µ̂ i MLE = E [ rt|ot = Oi, eit = 1 ] = ∑H t=1 rtI(ot = Oi, eit = 1)∑H t=1 I(ot = Oi, eit = 1) . (6)

heading: 3.2 TEST PHASE: SUBTASK GRAPH EXECUTION POLICY
text: Once a subtask graph Ĝ has been inferred, we can derive a subtask graph execution (SGE) policy πexe Ĝ
(o|x) that aims to maximize the cumulative reward in the test phase. Note that this is precisely the problem setting used in Sohn 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 a 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 to space limitation, we give a detail of the GRProp policy in Appendix I.

heading: 3.3 LEARNING: OPTIMIZATION OF THE ADAPTATION POLICY
text: We now describe how to learn the adaptation policy πadaptθ , or its parameters θ. We can directly optimize the objectiveRMG(π) using policy gradient methods (Williams, 1992; Sutton et al., 1999a), such as actor-critic method with generalized advantage estimation (GAE) (Schulman et al., 2016). However, we find it 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 rUCBt to agent in addition to the extrinsic environment reward, where rUCBt is the upper confidence bound (UCB) (Auer et al., 2002)-inspired exploration bonus term as follows:
rUCBt = wUCB · I(xt is novel), wUCB = N∑ i=1 log(ni(0) + ni(1)) ni(eit) , (7)
where N is the number of subtasks, eit is the eligibility of subtask i at time t, and n i(e) is the visitation count of ei (i.e., the eligibility of subtask i) during the adaptation phase until time t. The weight wUCB is designed to encourage the agent to 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 I(xt is novel) encourages the adaptation policy to visit novel states with a previously unseen completion vector xt (i.e., different combination of completed subtasks), since the data points with same xt input will be ignored in the ILP module as a duplication. We implement I(xt is novel) using a hash table for computational efficiency. Then, the intrinsic objective is given as follows:
RUCBMG ( πadaptθ ) = Eπadaptθ ,MG [∑H t=1 r UCB t ] , (8)
where H is the horizon of adaptation phase. Finally, we train the adaptation policy πadaptθ using an actor-critic method with GAE (Schulman et al., 2016) to maximize the following objective:
RPG+UCBMG ( πadaptθ ) = RMG ( πGRProp Ĝ ) + βUCBRUCBMG ( πadaptθ ) , (9)
whereRMG(·) is the meta-learning objective in Eq.(1), βUCB is the mixing hyper-parameter, and Ĝ is the inferred subtask graph that depends on the adaptation policy πadaptθ . The complete procedure for training our MSGI agent with UCB reward is summarized in Algorithm 1.

heading: 4 RELATED WORK
text: Meta Reinforcement Learning. There are roughly two broad categories of meta-RL approaches: gradient-based meta-learners (Finn et al., 2017; Nichol et al., 2018; Gupta et al., 2018; Finn et al., 2018; Kim et al., 2018) and RNN-based meta-learners (Duan et al., 2016; Wang et al., 2016). Gradientbased meta RL algorithms, such as MAML (Finn et al., 2017) 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-RL methods (Duan et al., 2016; Wang et al., 2016) updates the hidden states of a RNN as a 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, 1991) learn a set of rules from examples. (Xu et al., 2017) 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 to deal with noisy and erroneous data and seek data efficiency, such as (Hu et al., 2016; Evans & Grefenstette, 2017; Dong et al., 2019). 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 & Taylor, 2017; Liu et al., 2016)) such that the task structure can be constructed from the successful trajectories. In contrast, we tackle a more general and challenging setting, where each subtask gives a reward (i.e., multi-goal 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) or graph (Huang et 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.

heading: 5 EXPERIMENTS
text: In the experiment, we investigate the following research questions: (1) Does MSGI correctly infer task parameters G? (2) Does adaptation policy πadaptθ improve the efficiency of few-shot RL? (3) Does the use of UCB bonus facilitate training? (See Appendix H.1) (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 a random eligible subtask that has not been completed. • RL2 is the meta-RL agent in Duan et 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., 2018) provided with the ground-truth subtask
graph as input. This is roughly an upper bound of the performance of MSGI-based approaches. • MSGI-Rand (Ours) uses a random policy as an adaptation policy, with the task inference module. • MSGI-Meta (Ours) uses a meta-learned policy (i.e., πadaptθ ) as an adaptation policy, with the task
inference module.
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 J. The domains on which we evaluate these approaches include two simple grid-world environments (Mining and Playground) (Sohn et al., 2018) and a more challenging domain SC2LE (Vinyals et al., 2017) (StarCraft II).

heading: 5.1 EXPERIMENTS ON MINING AND PLAYGROUND DOMAINS
text: Mining (Sohn et al., 2018) is inspired by Minecraft (see Figure 3) where the agent receives reward by picking up raw materials in the world or crafting items with raw materials. Playground (Sohn et al.,
2018) is a more flexible and challenging domain, where the environment is stochastic and subtask graphs are randomly generated (i.e., precondition is an arbitrary logic expression). We follow the setting in Sohn et al. (2018) for choosing train/evaluation sets. We measure the performance in terms of normalized reward R̂ = (R−Rmin)/(Rmax−Rmin) averaged over 4 random seeds, whereRmin and Rmax correspond to the average reward of the Random and the GRProp+Oracle agent, respectively.
5.1.1 TRAINING PERFORMANCE
Figure 4 shows the learning curves of MSGI-Meta and RL2, 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 a 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 RL2 agent improves over time, eventually outperforming the HRL agent. This indicates that RL2 learns 1) a 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.

heading: 5.1.2 ADAPTATION AND GENERALIZATION PERFORMANCE
text: Adaptation efficiency. In Figure 5, we measure the test performance (in terms of the normalized reward R̂) by varying episode budget 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-based 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 slow-parameters and fast-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 Figure 5. 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 C for more details about the tasks in Playground and Mining). We report the agent’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
50 episodes of adaptation budget. Both of our MSGI-based 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 our task execution policy, GRProp, generalizes well to unseen tasks as already shown in (Sohn et al., 2018). However, RL2 fails to generalize to unseen task and longer adaptation horizon: on D2-D4 with adaptation horizons longer than the length the meta-learner was trained for, the performance of the RL2 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.

heading: 5.2 EXPERIMENTS ON STARCRAFT II DOMAIN
text: SC2LE (Vinyals et 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 & Ultralisks (see Figure 9 and demo videos at https://bit.ly/msgi-videos). 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 race (see Figure 11 and Appendix E for more details).
Agents. Note that the precondition of each subtask is determined by the domain and remains fixed across the tasks. If we train the meta agents (MSGI-Meta and RL2), 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 MSGIGRProp. MSGI-GRProp uses the GRProp policy as an adaptation policy since GRProp is a good approximation algorithm that works well without meta-training as shown in (Sohn et al., 2018). Since the environment does not provide any subtask-specific 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 fĉ : x 7→ ê. Specifically, we compare the inference output ê with the GT label e generated by the GT precondition function fc : x 7→ e for all possible binary assignments of input (i.e., 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 on 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 8 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 a correct order. For example, our MSGI-GRProp learns from the inferred subtask graph that some buildings such as sensor tower or engineering bay are unnecessary for training units and avoids constructing them (see Appendix F for the inferred subtask graph).

heading: 6 CONCLUSION
text: We introduced and addressed a few-shot RL problem with a 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 prelearned 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.

heading: ACKNOWLEDGMENTS
text: 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 (IITP) 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.

heading: A SUBTASK GRAPH AND FACTORED MDP
text: A.1 BACKGROUND: FACTORED MARKOV DECISION PROCESSES
A factored MDP (FMDP) (Boutilier et al., 1995; Jonsson & Barto, 2006) is an MDP M = (S,A,P,R), where the state space S is defined by a set of discrete state variables s = {s1, . . . , sd}. Each state variable si ∈ s takes on a value in its domain D(si). The state set S is a (subset of) Cartesian product of the domain of all state variables ×si∈sD(si). In FMDP, the state variables si are conditionally independent, such that the transition probability can be factored as follows:
p(st+1|st, at) = p(s1t+1|st, at)p(s2t+1|st, at) . . . p(sdt+1|st, at). (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(sit+1|st, at) in either a Boolean expression (i.e., subtask graph) or a binary decision tree (i.e., DBN). For more intuitive explanation, see the subtask graph paragraph in Section 2.2 and Figure 1.
Jonsson & Barto (2006); Sohn et al. (2018) suggested that the factored MDP can be 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. 10, the transition probability can be factored as follows:
p(s′|s, o) = ∏ i p(s′i|s, o), R(s, o) = ∑ i Ri(s, o). (11)
In (Sohn et al., 2018), the option Oi completes the subtask Φi by definition; thus, p(s′i|s, o) = 0 and Ri(s, o) = 0 if o 6= Oi. By introducing the eligibility vector e, the transition and reward functions are further expanded as follows:
p(x′i|x, o = Oi) = p(x′i|ei = 1)p(ei = 1|x), (12) Ri(x, o = Oi) = GriI(ei = 1), (13)
where p(x′i|ei = 1) indicates that the subtask is completed x′i if the subtask is eligible ei = 1, p(ei|x) is the precondition Gc, and I(ei = 1) indicates that the reward is given only if the subtask i is eligible.

heading: B DETAILS OF TASK IN SUBTASK GRAPH INFERENCE PROBLEM
text: 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 tupleMG = (S,A,PG,RG, ρG, γ) where S is a set of states, A is a set of actions, PG : S ×A× S → [0, 1] is a task-specific state transition function, RG : S ×A → R is a task-specific reward function and ρG : 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, a subtask Φi is a tuple (completion set Sicomp ⊂ S, precondition Gic, subtask reward G i r ∈ R). The subtask Φi is eligible (i.e., subtask can be executed) if the precondition Gic is satisfied (see the State Distribution and Transition Function paragraph below for detail). The subtask Φi is complete if the current state is in the completion set st ∈ Sicomp, and the agent receives the reward rt ∼ p(Gir). Subtasks are shared across tasks. The subtask graph is a tuple of precondition and subtask reward of N subtasks: G = (Gc, Gr) (see Appendix B for the detail). One example of subtask graph is given in Figure 3. A subtask graph G is a tuple of the subtask reward Gr ∈ RN , and the precondition Gc of N subtasks.
State The state st consists of the observation obst ∈ {0, 1}W×H×C , the completion vector xt ∈ {0, 1}N , the eligibility vector et ∈ {0, 1}N , the time budget stept ∈ R and number of episode left during the adaptation epit ∈ R. An observation obst is represented as H ×W × C tensor, where H and W are the height and width of map respectively, and C is the number of object types in
the domain. The (h,w, c)-th element of observation tensor is 1 if there is an object c 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.
Figure 7: Dependency between subtask graph and MDP
State Distribution and Transition Function Given the current state (obst,xt, et), the next step state (obst+1,xt+1, et+1) is computed from the subtask graph G. Figure 7 describes the dependency between subtask graph and MDP. In the beginning of episode, the completion vector xt is initialized to a zero vector in the beginning of the episode x0 = [0, . . . , 0] and the observation obs0 is sampled from the task-specific initial state distribution ρG. Specifically, the observation is generated by randomly placing the agent and the N objects corresponding to the N subtasks defined in the subtask graph G. When the agent executes subtask i, the i-th element of completion vector is updated by the following update rule:
xit+1 = { 1 if eit = 1 xit otherwise
. (14)
The observation is updated such that agent moves on to the target object, and perform corresponding primitive action. The eligibility vector et+1 is computed from the completion vector xt+1 and precondition Gc as follows:
eit+1 = OR j∈Childi
( yjAND ) , (15)
yiAND = AND j∈Childi
( x̂i,jt+1 ) , (16)
x̂i,jt+1 = x j t+1w i,j + (1− xjt+1)(1− wi,j), (17) wherewi,j = 0 if there is a NOT connection between i-th node and j-th node, otherwisewi,j = 1, and wi,j’s are defined by the Gc. Intuitively, x̂ i,j t = 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 Gr ∈ RN and the eligibility vector et, where the subtask reward vector Gr is the component of subtask graph G the and eligibility vector is computed from the completion vector xt and subtask graph G as Eq. 17. Specifically, when agent executes subtask i, the amount of reward given to agent at time step t is given as follows:
rt =
{ Gir if e i t = 1
0 otherwise . (18)
Learning option The option framework can be naturally applied to the subtask graph-based tasks. Consider the (optimal) option Oi = (Ii, πio, βi) for subtask Φi. Its initiation set is Ii = {s|ei = 1}, where s is the state, ei is the i-th component of eligibility vector e, and e is an element of s. The termination condition is βi = I(xit = 1), where xi is the i-th component of completion vector x. The policy πio maximizes the subtask reward G i r. Similar to Andreas et al. (2017); Oh et al. (2017); Sohn et al. (2018), 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.

heading: C DETAILS OF THE PLAYGROUND AND MINING DOMAIN
text: For self-containedness, we provide the details of Playground and Mining (Sohn et al., 2018) domain. Table 1 summarizes the complexity of the subtask graph for each task sets in Playground and Mining domain.
Subtasks The set of subtasks in Playground and Mining are implemented as O = Aint × X , where Aint is a set of interactions with objects, and X is a set of all types of interactive objects in the domain. To execute a subtask (aint, obj) ∈ Aint ×X , the agent should move on to the target object obj and take the primitive action aint.
Mining The Mining (Sohn et al., 2018) is a domain inspired by Minecraft (see Figure 8) for example task). The agent may pickup raw 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) an item may be an ingredient for building other items (e.g. stick and stone are ingredients of stone pickaxe), and 2) an item may be a required tool to pick up some objects (e.g. agent need stone pickaxe to 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 a template to generate 640 random task graphs. Following (Sohn et al., 2018), we used 200 for training and 440 for testing.
Playground The Playground (Sohn et al., 2018) domain is a more flexible domain (see Figure 3, left) which is designed to evaluate the strong generalization ability of agents on unseen task dependencies under delayed reward in a 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 was trained on small
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 1). 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 RL domains such as Taxi (Bloch, 2009), Minecraft (Oh et al., 2017) and XWORLD (Yu et al., 2017).

heading: D ALGORITHM IN META-TESTING
text: The Algorithm 2 describes the process of our MSGI at meta-testing time for single trial.
Algorithm 2 Process of single trial for a taskMG at meta-test time Require: The current parameter θ Require: A taskMG parametrized by a task parameter G (unknown to the agent)
1: Roll out K train episodes τH = {st,ot, rt, dt}Ht=1 ∼ π adapt θ in taskMG . adaptation phase 2: Infer a subtask graph: Ĝ = (Ĝc, Ĝr) = (ILP(τH),RI(τH)) . task inference 3: Roll out a test episode τ ′ = {s′t,o′t, r′t, d′t}H ′
t=1 ∼ πexeĜ in taskMG . test phase 4: Measure the performance R = ∑ t r ′ t for this task

heading: E DETAILS OF THE SC2LE DOMAIN
text: 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 & Ultralisks and Build Battlecruiser mini-games 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 it 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, 1 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 1 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 mini-games share the same initial setup as specified in Figure 9.
Defeat Zerg troops scenario: At the end of the war preparation, different combinations of enemy unit appears: Defeat Zerglings and Defeat Hydralisks has 20 zerglings and 15 hydralisks, respectively, and Defeat Hydralisks & Ultralisks contains a combination of total 5 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 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.
The transition dynamics (i.e., build tech-tree) in SC2LE domain has a 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, Hellbat, 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 mineral, gathering gas, and no-op. For gathering mineral, we set the subtask as (mineral≥ val) where val ∈ {50, 75, 100, 125, 150, 300, 400}. Similarly for gathering gas, we set the subtask as (gas≥ val) where val ∈ {25, 50, 75, 100, 125, 150, 200, 300}. For no-op subtask, the agent takes the no-op action for 8 times.
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., gas≥ 50). The no-op subtask is never completed. Subtask reward. In SC2LE domain, the agent does not receive any reward when completing a subtask. The only reward given to agent is the binary reward rHepi = {+1,−1} at the end of episode (i.e., t = Hepi). Therefore, the subtask reward inference method described in Eq.(4) may not be applied. Instead, we tried to infer the subtask reward Ĝr ∈ RN (see Section 3 for definition) from a victory reward rHepi by building a binary classifier that predicts the victory reward rHepi from the option count vector n ∈ NN 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:
rHepi = I(Gr>n > β), (19) where I(·) is the indicator function and β is the threshold. Then, we approximate it using a sigmoid function σ(·) as follows:
rHepi = σ(Gr >n− β). (20)
In the adaptation phase, we randomly sampled the subtask reward vector Gr from the uniform distribution in [0, 1]N , and used it for running MSGI-GRProp agent while recording the option count vector n. Then, the option count vectors n and the victory rewards rHepi from the K episodes in
adaptation phase form a training data { ni, rHepi,i }K i=1
for estimating the parameters of logistic model as follows:
log rHepi
1− rHepi = Ĝr
>n− β, (21)
where Ĝr ∈ RN and β ∈ R are the weight and bias parameters to be learned. Finally, we used the learned Ĝr 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.

heading: F MORE RESULTS ON THE SC2LE DOMAIN
text: 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.
Qualitative Examples. Figure 12 shows a simplified form of the subtask graph inferred by our MSGIGRProp 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.

heading: G EXPERIMENT ON AI2-THOR DOMAIN
text: The AI2-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 PickupObject action changes the object’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 an 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 is the receptacle object (i.e., Pan, Plate, Bowl, Cabinet, Microwave, StoveBurner, CounterTop, DiningTable, SideTable, Toaster, CoffeeMachine, Fridge) which can contain other objects depending on their sizes. With these objects and the subtasks defined, the agent is required to cook and serve foods through long sequence of subtasks. For instance, the agent can prepare a fried egg dish by (1) placing a Pan object on StoveBurner, (2) placing Egg on Pan, (3) slicing (or, cracking) Egg to EggCracked, (4) turning on 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 AI2-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, LettuceSliced, 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 1 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 1 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 if the corresponding object is picked up (i.e., Pickup Tomato is complete). The slice subtasks are eligible if the sliceable objects are on any receptacle. The cook subtasks are eligible if the cookable
objects are placed on the corresponding cooking station (i.e., Mug is on the CoffeeMachine). The eligibility of the serve subtasks is 1 if the corresponding objects are either cooked or sliced.
Subtask reward. To make the task more challenging and realistic, we assigned a 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 a new task (i.e., trial). Table 2 specifies the range of subtask reward for the six serve subtasks; intuitively speaking, we set a higher subtask reward for the subtask that has more complex precondition.
Result. On the AI2-THOR environment, we compared our MSGI-GRProp agent with two baseline agents: Random and HRL. Figure 14 summarizes the performance of each agent with varying adaptation budgets. We observed that both the Random and HRL agent almost never receives any nonzero reward during 20 episodes of adaptation, since the serve subtasks have a complex precondition that is not easy to satisfy for random policy. In contrast, our MSGI-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 is 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 not 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 of them; as shown in Figure 16, our ILP module can accurately and efficiently infer the precondition of subtasks in AI2-THOR environment after only 20 episodes of adaptation.

heading: H MORE RESULTS ON MINING AND PLAYGROUND
text: H.1 ABLATION STUDY ON THE INTRINSIC REWARD
We conducted an ablation study comparing our MSGI-Meta 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-Eval 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 in 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 a meta-learned adaptation policy is able to collect more comprehensive experience for accurate subtask graph inference.
H.3 QUANTITATIVE ANALYSIS OF THE ADAPTATION POLICY
Coverage (%) Method D1 D2 D3 D4 Eval
MSGI-Meta 89 87 81 75 90 MSGI-Rand 83 77 68 58 85 We measured the portion of subtasks being eligible or completed at least once (i.e., coverage) during adaptation to measure how exploratory MSGI-Meta and random policy are. We report the averaged coverage over the evaluation graph set and 8 random seeds. The table shows that MSGI-Meta can make more diverse subtasks complete and eligible than the random policy thanks to more accurate subtask graph inference.

heading: I DETAILS OF GRPROP POLICY
text: For self-containedness, we provide the description of GRProp policy from Sohn et al. (2018). We also make a few modifications on ÕR (x) and ÃND (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 xt be a completion vector and Gr be a subtask reward vector (see Section 2 for definitions). Then, the sum of reward until time-step t is given as:
Ut = Gr >xt. (22)
We first modify the reward formulation such that it gives a half of subtask reward for satisfying the preconditions and the rest for executing the subtask to encourage the agent to satisfy the precondition of a subtask with a large reward:
Ût = Gr >(xt + et)/2. (23)
Let yjAND be the output of j-th AND node. The eligibility vector et can be computed from the subtask graph G and xt as follows:
eit = OR j∈Childi
( yjAND ) , yjAND = AND
k∈Childj
( x̂j,kt ) , x̂j,kt = x k tw j,k + NOT(xkt )(1− wj,k),
(24)
where wj,k = 0 if there is a NOT connection between j-th node and k-th node, otherwise wj,k = 1. Intuitively, x̂j,kt = 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:
pi = λorẽ i + (1− λor)xi, (25)
ẽi = ÕR j∈Childi
( ỹjAND ) , (26)
ỹjAND = ÃND k∈Childj
( x̂j,k ) , (27)
x̂j,k = wj,kpk + (1− wj,k)ÑOT ( pk ) , (28)
where x ∈ Rd is the input completion vector, ÕR (x) = softmax(worx) · x, (29)
ÃND (x) = ζ(x, wand)
ζ(||x||, wand) , (30)
ÑOT (x) = −wnotx, (31) ||x|| = d, ζ(x, β) = 1β log(1 + exp(βx)) is a soft-plus function, and λor = 0.6, wor = 2, wand = 3, wnot = 2 are the hyper-parameters of GRProp. Note that we slightly modified the implementation of ÕR and ÃND 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:
Ũt = Gr >p, (32)
where p = [p1, . . . , pd] and pi is computed from Eq. 25. Finally, the graph reward propagation policy is a softmax policy,
π(ot|G,xt) = Softmax ( T∇xtŨt ) = Softmax ( TGr >(λor∇xt ẽt + (1− λor)) ) , (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.
J 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 τt = {st,ot, rt,dt} at time step t as input, where s = {obs,x, e, step, epi}. We used convolutional neural network (CNN) and gated rectifier unit (GRU) to 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 observation embedding is computed by Conv1(16x1x1-1/0)-Conv2(32x3x3-1/0)-Conv3(64x3x3-1/1)Conv4(32x3x3-1/1)-Flatten-FC(512)-GRU(512). 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 concatenated into single vector, and fed to FC(512)-FC(d) for policy output and FC(512)-FC(1) for value output, where d is the policy dimension. We used ReLU activation function in all the layers.
J.2 DETAILS OF TRAINING MSGI-META
Algorithm 1 describes the pseudo-code for training our MSGI-Meta model with and without UCB bonus term. In adaptation phase, we ran a batch of 48 parallel environments. In test phase, we measured the average performance over 4 episodes with 8 parallel workers (i.e., average over 32 episodes). We used actor-critic method with GAE (Schulman et al., 2016) as follows:
∇θL = EG∼Gtrain [ Es∼πθ [ −∇θ log πθ ∞∑ l=0 ( l−1∏ n=0 (γλ)kn ) δt+l ]] , (34)
δt = rt + γ ktV πθ (st+1)− V πθ (st), (35)
where we used the learning rate η = 0.002, γ = 1, and λ = 0.9. We used RMSProp optimizer with the smoothing parameter of 0.99 and epsilon of 1e-5. We trained our MSGI-Meta agent for 8000 trials, where the agent is updated after every trial. We used the best hyper-parameters chosen from the sets specified in Table 4 for all the agents. We also used the entropy regularization with annealed parameter βent. We started from βent = 0.05 and linearly decreased it after 1200 trials until it reaches βent = 0 at 3200 trials. During training, we update the critic network to minimize E[(Rt − V πθ (st)) 2 ], where Rt is the cumulative reward at time t with the weight of 0.03. We clipped the magnitude of gradient to be no larger than 1.
J.3 DETAILS OF TRAINING RL2 AND HRL
For training RL2 and HRL, we 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 η = 0.001 and the critic loss weight of 0.12. We used the best hyper-parameters chosen from the sets specified in Table 4 for all the agents.

Review summaries:
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.

The 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.