Program Guided Agent
Authors: Shao-Hua Sun
Te-Lin Wu
Joseph J. Lim
Venue:  (2020)
Keywords: Program Execution
Program Executor
Program Understanding
Program Guided Agent
Learning to Execute
Deep Learning

Abstract: Developing agents that can learn to follow natural language instructions has been an emerging research direction. While being accessible and flexible, natural language instructions can sometimes be ambiguous even to humans. To address this, we propose to utilize programs, structured in a formal language, as a precise and expressive way to specify tasks. We then devise a modular framework that learns to perform a task specified by a program – as different circumstances give rise to diverse ways to accomplish the task, our framework can perceive which circumstance it is currently under, and instruct a multitask policy accordingly to fulfill each subtask of the overall task. Experimental results on a 2D Minecraft environment not only demonstrate that the proposed framework learns to reliably accomplish program instructions and achieves zero-shot generalization to more complex instructions but also verify the efficiency of the proposed modulation mechanism for learning the multitask policy. We also conduct an analysis comparing various models which learn from programs and natural language instructions in an end-to-end fashion.

Published as a conference paper at ICLR 2020
PROGRAM GUIDED AGENT
Shao-Hua Sun, Te-Lin Wu, Joseph J. Lim University of Southern California
(shaohuas, telinww, limjj] ) @usc.edu
ABSTRACT
Developing agents that can learn to follow natural language instructions has been an emerging research direction. While being accessible and flexible, natural lan- guage instructions can sometimes be ambiguous even to humans. To address this, we propose to utilize programs, structured in formal language, as a precise and expressive way to specify tasks. We then devise a modular framework that learns to perform a task specified by a program as different circumstances give rise to diverse ways accomplish the task, our framework can perceive which circumstance it is currently under, and instruct a multitask policy accordingly to fulfiill each subtask of the overall task. Experimental results on 2D Minecraft enviromment not only demonstrate that the proposed framework learns to reliably accomplish program instructions and achieves zero-shot generalization to more complex instructions but also verify the efficiency of the proposed modulation mechanism for learning the multitask policy. We also conduct analysis compar- ing various models which learn from programs and natural language instructions in an end-to-end fashion.
INTRODUCTION
Humans are capable of leveraging instructions to accomplish complex tasks. A comprehensive instruction usually comprises a set of descriptions detailing variety of situations and the correspond- ing subtasks that are required to be fulfilled. To accomplish task, we can leverage instructions to estimate the progress, recognize the current state, and perform corresponding actions. For example, to make a gourmet dish, we can follow recipes and procedurally create the desired dish by recognizing what ingredients and tools are missing, what alternatives are available, and what corresponding preparations are required. With sufficient practice, we can improve our ability to perceive (e.g. knowing when food is well-cooked) as well as master cooking skills (e.g. cutting food into same-sized pieces), and eventually accomplish difficult recipes.
Can machines likewise learn to follow and exploit comprehensive instructions like humans? Utilizing expert demonstrations to instruct agents has been widely studied in (Finn et al.) 2017: Yu al.
2018b Xu et al. 2018; Pathak et al.] 2018 Stadie et al. 2017]] Duan et al. 2017 Wang et al. 2017b However, demonstrations could be expensive obtain and are less flexible (e.g. altering
subtask orders in demonstrations nontrivial). On the other hand, natural language instructions are
flexible and expressive (Malmaud et [2014] Jermsurawong Habash 2015 Kiddon al.) 2015
Misra et al. 22018) Fried et al. 2018 8 Kaplan et al. 2017]] Bahdanau et al. (019). Yet, language has the caveat of being ambiguous even humans, due
lacking of structure as well unclear coreferences and entities. Andreas et al. 70): Oh et al. (2017) investigate a hierarchical approach, where the instructions consist of set of symbolically represented subtasks. Nonetheless, those instructions are not a function of states (i.e. describe variety of circumstances and the corresponding desired subtasks), which substantially limits their expressiveness.
We propose to utilize programs, written in formal language, as structured, expressive, and unambiguous representation to specify tasks. Specifically, we consider programs, which are composed of control flows (e.g. if/else and loops), environmental conditions, well as corresponding subtasks, as shown in Figure I Not only do programs have expressiveness by describing diverse situations (e.g. river exists) and the corresponding subtasks which are required to be executed (e.g. mining wood), but they are also unambiguous due to their explicit scoping. To study the effectiveness of using programs task specifications, introduce new problem, where we aim develop a framework

---

Published as a conference paper at ICLR 2020
Program def run()
Program
whilefe) (+) (oop(f) (s)
ran():
[i((c) (s) elseii(e)) (s) clse
if in thert Riverj]:
Item = Gold Wood Iron
(Wood)
build bridgef1
Terran Bridge River Morchant Wall Flat
if agent[Tronjeh)
Operators o = 2 == <
mine (Iron)
place(Izon, 1,
Numbers positive inleger
alam:
Perception à : agent[t] env[t] is [o_there(]] is therefo]
goto 21
Behavior mine(t) goto(i,
while env[Gbld]=0 minw(Gold)
placet), i) build bridge() (xell()
x3
x1
xO
Conditions ht[d] o A[u) o
Figure An illustration of the proposed problem. We are interested in learning to fulfill tasks speci- fied by written programs. A program consists of control flows (e.g. if, while), branching condi- tions (e.g. is s__thre [River]) ]), and subtasks (e.g. mine (Wood)),
Figure 2: The domain- speccifcc language (DSL) con- structing programs. Each program is composed of do- main dependent perception, subtasks, and control flows.
which learns to comprehend task specified by program as well as perceive and interact with the environment accomplish the task.
To address this problem, we propose a modular framework, program guided agent, which exploits the structural nature of programs to decompose and execute them well as learn to ground pro- gram tokens with the environment. Specifically, our framework consists of three modules: (I) program interpreter that leverages grammar provided by the programming language to parse and execute program, (2) perception module that learns to respond to conditional queries (e.g. is_ theteeeeeeeeeeeeee [River]) produced by the interpreter, and (3) policy that learns to fulfill variety of subtasks (e.g. mine (Wood)) extracted from the program by the interpreter. To effectively instruct the policy with symbolically represented subtasks, we introduce a learned modulation mechanism that leverages subtask to modulate the encoded state features instead of concatenating them. Our framework (shown in Figure| 33 utilizes a rule-based program interpreter to deal with programs as well as learning perception module and policy when it is necessary to perceive or interact with the environment. With this modularity, our framework can generalize to more complex program-specified tasks without additional learning.
To evaluate the proposed framework, we consider Minecraft-inspired 2D gridworld environment, where agent can navigate itself across different terrains and interact with objects, similar to Andreas et al. 70)7 Sohn et al. (2018). A corresponding domain-specific language (DSL) defines the rules of constructing programs for instructing an agent to accomplish certain tasks. Our proposed frame- work demonstrates superior generalization ability learning from simpler tasks while generalizing to complex tasks. We also conduct extensive analysis on various end-to-end learning models which learns from not only program instructions but also natural language descriptions. Furthermore, our proposed learned policy modulation mechanism yields better learning efficiency compared to other commonly used methods that simply concatenate state and goal.
RELATED WORK
Learning from language instructions. Prior works have investigated leveraging natural languages to specify tasks on a wide range of applications, including navigation (Misra et al., 2018 Tellex
et al.
2011 Fried et al. 2018 Vogel & Jurafsky 2010, (Shimizu & Haas 2009 Branavan et al.
2009
2012 Misra et al. 2017 Tellex et al. [201 1). spatial reasoning for goal reaching (Janner et al.
2018
game playing KKalann et al. 2017 Fried et al. 2017 Co-Reyes et al. 2019), and grounding
visual concepts Kaplan et al. 2017 Bahdanau et al. 2019 Andreas et al.] (017b)) However, natural language descriptions often be ambiguous end learning agents trained with simpler instructions can generalize well to much more complex ones. In contrast, propose utilize precise and structured representation, programs, specify tasks.
to humans. Moreover, it not clear how end-to-
2

---

Published as a conference paper at ICLR 2020
Learning from demonstrations. When task cannot be easily described in languages (e.g. object texture or geometry), expert demonstrations offer an alternative way to provide instructions. Prior works have explored learning from video demonstrations (Finn et al. 2017: Yu et al.) 2018b; Xu Pathak et al. 2018: Stadie et al. 2017;; Aytar et al. 2018) or expert trajectories (Duan 2017 Wang et al. 2017b). However, demonstrations can be expensive to obtain and are less expressive about diverging behaviors of a complex task, which are better captured by control flow in programs. Moreover, editing demonstrations such as rearranging the order of subtasks is often difficult.
eet al. al.
2018:
Program induction and synthesis. To learn acquire programmatic skills such as digit addition and
string transformations and achieve better generalization, program induction methods (Xu et al. 20188)
Devlin et al. 2017a Neelakantan et al. 201 5 Graves et al., 2014 Kaiser & Sutskever] [016]] Reed &
De Freitas 2016 Cai et al. 2017: Xiao et al. 2018) aim to implicitly induce the underlying programs
to mimic the behaviors demonstrated in task specifications (e.g. input/output pairs, demonstrations).
On the other hand, program synthesis methods (Bošnjak et al. 2017 Parisotto al. 2017 Devlin
al. [l 20017b Chen et al. 2019 Shin et al. 2018 Bunel et al.] [018]] et al. 2019] |un et al. 2018]
Chen
Lin et al. [2018] Liao et al. 2019) explicitly synthesize the underlying programs and execute the ex programs to perform the tasks. Instead of trying to infer programs from task specifications, we are
interested in explicitly executing programs. Also, our framework can potentially be leveraged to
obtain program execution results for evaluating program synthesis frameworks when no program executor is available (e.g. programs describe real-world activities instead of behaviors in simulation).
Symbolic planing and programmable agent. Classical symbolic planning concerns the problem of achieving goal state from an initial state through series of symbolically represented execu- tions (Ghallab et al,; Konidaris et al., 2018). Our work shares similar spirit but assume a task (i.e. a program) is given, where the agent required to learn to ground symbolic concepts (Mao et al.) 2019) Han et al. 2019) and follow the control flow. Executing programs with reinforcement learning has been studied in programmable hierarchies of abstract machines (Parr & Russell 1998 Andre Russell| 2001] 2002). which provide partial descriptions and subroutines of the desired task. Denil ct al. (2117); GrerolGr et al. (0188) train agents to execute declarative programs by grounding these well-structured languages in their learning environments. In contrast, our modular framework consists of modules for perceiving the environment and interacting with it by following an imperative program which specifies the task. An extended discussion the related work can be found in Section
3 PROBLEM FORMULATION
We are interested in learning to comprehend and execute an instruction specified by program to fulfill the desired task. In this section, we formally deseribe our definition of programs, the family of Markov Decision Processes (MDPs), and the problem formulation.
Program.
The programs considered in this work are defined based on Domain Specific Lan- guage (DSL) as shown in Figure 2 The DSL is composed of perception primitives, action prim- itives, and control flow. A perception primitive indicates circumstances in the environment (e.g. is there (River), , and agent [Gold] <3) that can be perceived by agent, while an action primitive defines a subtask that describes a certain behavior (e.g. mine (Gold). , and goto (1, 1)). Control flow includes i f el se statements, loops, and Boolean/logical operators compose more sophisticated conditions. A program is a deterministic function that outputs a desired behavior (i.e. subtask) given history of states o, = p (H₂)). where H,, {.,,... 8t) is state history with S denoting a state of the environment, and E O denotes an instructed behavior (subtask). We denote a program as p ~ P, an infinite program set containing all executable programs given a DSL. Note that a discussion on the DSL design principle can be found in Section B
MDPs We consider family of finite-horizon discounted MDPs in shared environment, specified by a tuple (S, A, P. T, T, p, 7),, where S denotes a set of states, AA denotes set of low-level actions an agent can take, P denotes a set of programs specifying instructions, T : S x A xxx -+ IR denotes a transition probability distribution, 'R denotes task task-specific reward function, P denotes an initial state distribution, and 7 denotes a discount factor. For a fixed sequence {(50, an), ..., (st, at)) of states and actions obtained from a rollout of given policy æ, the performance of the policy is evaluated based discounted return Elz 7/r,, where T is the horizon of the episode.
3

---

Published as a conference paper at ICLR 2020
g
Perception Module
xx + x
State
π
a
def run(1:
while anvidold]
Query
q
h
Response
Policy
Action
Environment
ains]Bold]
therh [River]s
buigd_bridget) place(Hood, 2, 31
O Module
Module Output
Program
Program Interpreter
Goal
Figure 3: Program Guided Agent. The proposed modular framework comprehends and fulfills a desired task specified by program. The program interpreter executes the program altering between querying the perception module with query q when environment condition encountered (e.g. [Gold d =0, is_there [Riv)]) and instructing policy when it needs to fulfill goal/subtask g (e.g. mi (Gold), woild_bris dge ()). The perception module produces a response to answer the query, determining which paths in the program should be chosen. The policy takes a sequence of low-level actions (e.g. meveUp, moveIeft, Pickup) interacting with the environment accomplish the given subtask (e.g. mine (Gold)
Problem Formulation. We consider developing framework which can comprehend and fulfill an instruction specified by a program. Specifically, we consider sampled MDP with program describing the desired task. Addressing this task requires the ability to keep track of which parts of the program are finished and which parts are not, perceiving the environment and deciding which paths the program take, and performing actions interacting with the environment to fulfill subtasks.
4 APPROACH
Accomplishing an instructed task described by program requires (1) executing the program control flow and conditions, (2) recognizing the situations to infer which path in the program should be chosen, and (3) executing a series of actions interacting with the environment fulfill the subtasks. Based on this intuition, we design modular framework with three modules:
Program interpreter (Section 4.1 reads a program and executes by querying a perception module with environment conditions (e.g. env [Gold] >0) and instructing the policy with subtasks (e.g. mine (Gold))
Perception module (Section 4.2 responds to perception queries (e.g. env [Gold] >0 by exam- ining the observation and predicting responses (e.g. true).
Policy (action module) (Section 4.3) performs low-level actions (e-g. moveUp, moveLe ft, pi pipk to fulfill the symbolically represented subtasks (e.g. mine (Gold) provided by the program interpreter.
Our key insight is to only learn a module when its input or output is associated with the environment (i.e. a function approximator needed) the perception module learns to ground the queries its observation and answer them; the policy learns to ground the symbolically represented subtasks and interact with the environment not learn the program interpreter; instead, we utilize rule-based parser to execute programs An overview of the proposed framework is illustrated Figure
trial-and-error way (Section 4.4). On the other hand, do
4.1 PROGRAM INTERPRETER
To execute program instruction, group program tokens into three main categories: (1) subtasks indicate what the agent should perform (e.g. mine (Gold)) ), (2) perceptions the essential informa- tion extracted from the environment (e.g. env [Gold] >0), and (3) control flows determine which paths in a program should taken according to the perceived information (i.e. perceptions). Then, devise program interpreter, which execute and keep track of the progress by leveraging the
4

---

Published as a conference paper at ICLR 2020
structure of programs. Specifically, it consists of a program line parser and program executor. The parser first transforms the program into a program tree by representing each line of a program as a tree node. Each node is either leaf node (subtask) that has various subroutines as children nodes. The executor then performs a pre-order traversal on the program tree execute the program, utilizing the parsed contents alternate between querying the perception module when an environment condition is encountered and instructing the policy when it reaches leaf node (subtask). The details and the algorithm are summarized in section A Note that the program interpreter is a rule-based algorithm instead of a learning module.
non-leaf node (perception control flow)
4.2 PERCEPTION MODULE
Determining which paths should be chosen when executing a program requires grounding a symboli- cally represented query (e-g- is there [Ri [River] can be represented and perceiving the environment. To this end, we employ a perception module & that learns to map a query and current observation corresponding perception output (e.g- ruee ffa se). Note that we focus on Boolean perception outputs in this paper, but a more generic perception type can be used (e.g. object attributes such as color, shape, and size).
sequence of symbols)
response: h i 8), where q denotes query, and h denotes the
4.3 POLICY
When program execution reaches a subtask/leaf node (e.g. mine (Gold)), ), the agent is required to take a sequence of low-level actions (e.g. moveUp, moveLeft, Pickup) to interact with the environment to fulfill it. To enable the execution, we employ a multitask policy π (i.e. action module) which is instructed by symbolic goal (e.g. mine (Gold)) provided by the program interpreter indicating the details of the corresponding subtask. To learn to perform different subtasks, we train the policy using actor-critic reinforcement learning, which takes a goal vector g and an environment state and outputs a probabilistic distribution for low-level actions ~ ( 9t (). The value estimator used for our policy optimization is also goal-conditioned: V* ge) E E 7 Re = s, n. gtl.
While the most common way to feed a state and goal to policy parameterized by a neural network is to concatenate them in raw space or a latent space, we find this less effective when the policy has to learn a diverse set of tasks. Therefore, we propose a modulation mechanism to effectively learn the policy. Specifically, we employ a goal network to encode the goal and compute affine transform parameters and B, which are used to modulate state features e, to é. = modulated features é, are used to predict action a and value V. With the modulation mechanism, the goal network learns to activate state features related to the current goal and deactivate others. An illustration is shown in Figure 4 (a). A more detailed discussion of the related works that utilize similar learned modulation mechanisms can be found in Section
B. Then, the
4.4 LEARNING
To follow program by perceiving the environment and taking actions to interact with it, we employ two learning modules: perception module and a policy. In this section, we discuss how each module is trained, their training objectives, and optimization methods. More training details and the architectures can found section [
4.4.1 PERCEPTION MODULE
We formulate training the perception module as a supervised learning task. Given tuples of (query q- state ground truth perception hyt), we train neural network & to predict the perception output h by optimizing the binary cross-entropy loss: LCE = oog sequence of symbols. Note that when perception such as is s__there [River) is represented describes more than a Boolean, training the perception module can be done by optimizing other losses such categorical cross-entropy loss. We train the perception module only the queries appearing in the training programs with randomly sampled states, requiring it to generalize to novel queries to perform well in executing testing programs.
(1 hog) - h). A query
5

---

Published as a conference paper at ICLR 2020
Concalenation (Raw)
Concalenation (Latent)
Modulation
1.0
guail
0.9
Reward
0.6
Modulation
Modulation conv fc Modulation fc. Concat
0.3
02
Concal raw
Environment steps
(a) Illustration
(b) Training curves
Figure 4: Learning a multitask policy via learned modulation. (a) A multitask policy takes both state a and a goal specification g as imputs and produces an action distribution a ~ TT,. g). Instead of simply concatenating the state and goal in raw space latent space, propose to modulate state features e, using the goal. Specifically, the goal network learns predict affine transform parameters and modulate the state features 7 e, + 3. Then, different ways of feeding a state and goal for learning a multitask policy. The training curves demonstrate that all modulation variants, including modulating state feature maps of convolutional layers (Modulation conv), modulating state feature vectors of fully-connected layers (Modulation fc), both (Modulation conv fc), are efficient than concatenating the and the goal in raw space (Concat raw) latent space (Concat).
final layers use modulated features to predict actions. (b) We experiment
4.4.2 POLICY
We train the policy using Advantage Actor-Critic (A2C) (Mnih et al. 2016 Dhariwal et al. 2017). which is commonly used for gridworld environments with discrete action spaces. A2C computes policy gradients A, Ve log ma (0g]*;,9)) 9t), where A₁ R2 V(*,, 9t) is the advantage function based on empirical return R& starting from s; and learned value estimator V(st, gt) conditioning on the goal vector 9:. We denote the learning rate a, and the policy update rule is as follows:
0 - 0 (A V log To (a.lst. 9:) Hv.)..)>
(1)
where H. denotes the policy entropy, where maximizing it improves overall exploration, and determines the strength of the entropy regularization term.
EXPERIMENTS
Our experiments aim to answer the following questions: (1) Can our proposed framework learn to perform tasks specified by programs? (2) Can our modular framework generalize better more complex tasks compared to end-to-end learning models? (3) How well can variety of end-to-end learning models (e.g. LSTM, Tree-RNN, Transformer) learn from programs and natural language instructions? (4) Is the proposed learned modulation more efficient to learn multitask (multi-goal) policy than simply concatenating a state and goal?
5.1 EXPERIMENTAL SETUPS
5.1.1 ENVIRONMENT
To evaluate the proposed framework in an environment where an agent can perceive diverse scenarios and interact with the environment to perform various subtasks, we construct discrete Minecraft- inspired gridworld environment, similar to Andreas et al. (2017a); Sohn et al. (2018). As illustrated in Figure [ the agent can navigate through grid world and interact with resources (e.g. Wood, Iron, Gold) and obstacles (e.g. River, Wall), build tools (e.g. Bridge), and sell resources to a merchant visualized as an alpaca. The environment gives sparse task completion reward of +1 when an instruction (i.e. an entire program or natural language instruction) is successfully executed. More details can be found in Section E.

---

Published as a conference paper at ICLR 2020
Table 1: Task completion rate. For each method, we iterate over all the programs in testing set by randomly sampling ten initial environment states and running three models trained using different random seeds for this method. The averaged task completion rates and their standard deviations are reported. Note that all the end-to-end learning models learning from natural language descriptions and programs suffer from a significant performance drop when evaluated on the more complex testing set.
Instruction Method
Natural language descriptions Transformrr
Programs Transformer
Soq-LSTM
Soq-LSTM
Tree-RNN
Ours (concat)
Ours
Datasel
54.9118% 32.41.49%
52.51.2.6%
56.71.99%
1..2%
49.4.1..6% 40.9:1..5 1.5%
88. 68.61.8.8%
0..0 0..8
test-complex
2.6%
38.8=1.2%
42.2=2.4%
85.2400.88 8%
Generalization goi
40.9%
27.2%
31.6%
15.8%
17.2%
3.8%
2.3%
5.1.2 TASK INSTRUCTIONS
Programs. We sample 4,500 programs using our DSL and split them into 4,000 training programs (Irain) and 500 testing programs (lest). To examine the framework's ability to generalize to more complex instructions, we generate 500 programs which are twice longer and contains more condition branches on average to construct a harder testing set (test-complex).
Natural language instructions. To obtain the natural language counterparts of those instructions, we asked annotators to construct natural language translations of all the programs. The data collection details, as well as sample programs and their corresponding natural language translations, can be found in Section E.3 and figure respectivey,,. We include brief discussion on how annotated natural language instructions can be ambiguously interpreted as several valid programs.
5.2 TRAINING
During training, we randomly sample programs from the training set as well as randomly sample an enviromment state to execute the program interpreter. The program interpreter produces a goal to instruct the policy when encountering a subtask in the program. The policy takes actions a ~ [ g) and receive reward +1 only when the entire program is completed. While do not explicitly introduce a curriculum like Andreas et al. (2)7 this setup naturally induces a curriculum where the policy first learns solve simpler programs and gain a better understanding of subtasks by obtaining the task completion, which eventually allows the policy to complete more complex programs. Note that the perception module is pre-trained beforehand in supervised manner. More training details can be found in section E.7
5.3 END-TO-END LEARNING MODELS
In contrast to the proposed modular framework, we experiment with variety of end-to-end learning models. Considering programs and natural language instructions as sequences of tokens, we inves- tigate two types of oftee-of-theaare sequence encoders: LSTM (Hochreiter & Schmidhuber 1997) (Seq-LSTM), and Transformers (Vaswani et al.) 2017 Devlin et al. 2018) (Transformer). To leverage the explicit structure of programs, also investigate encoding programs using a generalization of
RNNs for tree-structured input (Tai et al. 2015 Alon et al.) 2019) (Tree-RNN), All the models are trained using A2C. The details of these architectures can be found in Section E.4.2
5.4
RESULTS
5.4.1 TASK COMPLETION
We train the proposed framework and the end-to-end learning models on training programs and evaluate their performances using the percentage of completed instructions on test and test-complex sets (shown in Table I. Our proposed framework achieves satisfactory test performance and only suffers a negligible drop (i.e. generalization gap) when it is evaluated on test-complex set. This can be attributed the modular design, which explicitly utilizes the structure and grammar of programs, allowing the two learning modules (i.e. perception and policy) to focus on their local jobs. more detailed failure analysis can be found in Section E.6

---

Published as a conference paper at ICLR 2020
Program
STM
Transformer
Tree-RNN
Natural Language
Seq-ISTM
Transformer
LSTM
Transfommer
Trandomer
1.0
0.6-
Cragaing
0.2
Nanderoo Tekees
Nanber orCortolFio
Nieber Couted Floe
Pregram
Language
Pregnam
Natural Lanuage
Sardecro
Coetod
(a) Instruction Length
(h) Instruction Diversity
Figure 5: Analysis on end-to-end learning models: (a) Models learning from programs generalize better to longer instructions. Transformer is more robust to longer instructions (Upper). TrNc-RNN exploiting the program structure generalizes the best, but performs worst for shorter programs (Lower). (b) Scq-L.TTM learning from both instructions performs worse as the diversity increases. Transformer learns better from natural language when the instructions are less diverse (Upper). Transformer and Tree-RNN learning from programs are more consistent as the diversity increases, yet perform worse less diverse instructions (Lower).
On the other hand, all the end-to-end learning models suffer significant performance drop between test and test-compler sets, while it less significant for the models learning from programs, potentially indicating that models learning from instructions with explicit structures can generalize to complex instructions better. Among them, Seq-LSTM achieves the best results on test set, but performs the worst the fest-complex set. Transformer has smaller generalization gaps, which could be attributed to their multi-head attention mechanism, capturing the instruction semantics better. By leveraging the explicit structure of programs, Tree-RNN achieves the best generalization performance.
5.4.2 ANALYSIS
analysis on the end-to-end learning models with respect to varying instruction length and com- plexity is shown in Figure 5 where all the instructions from test and test-complex sets are considered.
Instruction length. As shown in Figure 5 (a), both Seq- LSTM and Transformer suffer from performance drop the instruction length increases. Seq-L-TTM performs better when instructions are shorter, but suffers from generalizing to longer instructions. On the other hand, Transformer semantic level, which leads similar overall performances across two types of
may learn instructions. Tree-RNN leverages the structure of programs and achieves a better performance.
Instruction diversity. We define the diversity of program based on the number of control flows it contains (i.e. number of branches). Figure (b) shows a clear trend of performance drop of all the models. Transformer is more robust diverse instructions which could be attributed to its better ability to learn the semantics. While Seq-L.STM learning from programs are consistently better across different levels of diversities, Tree-RN demonstrates the most consistent performances.
5.5 POLICY MODULATION
We investigate learning a multitask policy with the learned modulation mechanism is more effective. We compare against the two most commonly used methods: concatenating a state and goal in raw space (Concat raw) or a latent space (Concat). An illustration is shown Figure (a). Since our state contains environment map, which is encoded by CNN and MLP, experiment modulating convoluted feature maps (Modulation conv) or feature vectors (Modulation fc) or both (Modulation conv fe). Figure 4 (b) demonstrate that the proposed policy modulation mechanism is more sample efficient. Table shows that the multitask policy learning using modulation achieves better performance task completion.
8

---

Published as a conference paper at ICLR 2020
CONCLUSION
We propose to utilize programs, structured a formal language, as an expressive and precise way to specify tasks instead of commonly used natural language instructions. We introduce the problem of developing framework that can comprehend a program as well as perceive and interact with the environment to accomplish the desired task. To address this problem, we devise modular framework, program guided agent, which executes programs with a program interpreter by altering between querying perception module when a branching condition is encountered and instructing policy to fulfill subtasks. We employ policy modulation mechanism to improve the efficiency of learning the multitask policy. The experimental results on a 2D Minecraft environment demonstrate that the proposed framework learns to reliably fulfill program instructions and generalize well to more complex instructions without additional training. We also investigate the performance various models that learn from programs and natural language descriptions in end-to-end fashion.
ACKNOWLEDGMENTS
The authors grateful for the fruitful discussion with Jiayuan Mao, Yuan-Hong Liao, Youngwoon Lee, Karl Pertsch, and Ayush Jain. The authors would like to thank Sriram Somasundaram for contributing to building the environment and Aleksei Petrenko for the A2C implementation.

---

Published as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et Tensorflow: system for large-scale machine learning. In USENIX Symposium on Operating Systems Design and Implementation, 2016.
Amjad Almahairi, Sai Rajeswar, Alessandro Sordoni, Philip Bachman, and Aaron Courville. Aug- mented eyclegan: Learning many-to-me -onnnay mappings from unpaired data. In International Confer- ence on Machine Learning, 2018.
Uri Alon, Omer Levy, and Eran Yahav. code2seq: Generating sequences from structured representa- tions of code. International Conference on Learning Representations, 2019.
David Andre and Stuart J Russell. Programmable reinforcement learning agents. In Advances in Neural Information Processing Systems, 2001.
David Andre and Stuart J Russell. State abstraction for programmable reinforcement learning agents. In National Conference on Artificial Intelligence, 2002.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International Conference on Machine Learning, 2017a
Jacob Andreas, Dan Klein, and Sergey Levine. Learning with latent language. In North American Chapter of the Association for Computational Linguistics, 2017b.
Yusuf Aytar. Tobias Pfaff, David Budden, Thomas Paine, Ziyu Wang, and Nando de Freitas. Playing hard exploration games by watching youtube. In Advances in Neural Information Processing Systems. 2018.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Association for the Advancement of Artificial Intelligence, 2017.
Dzmitry Bahdanau, Felix Hill, Jan Leike, Edward Hughes, Pushmeet Kohli, and Edward Grefenstette. Learning to understand goal specifications by modelling reward. International Conference on Learning Representations, 2019.
Bram Bakker, Jürgen Schmidhuher, et al. Hierarchical reinforcement learning based on subgoal discovery and subpolicy specialization. In Intelligent Autonomous Systems, 2004.
Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel. Programming with a differentiable forth interpreter. In International Conference Machine Learning, 2017.
Satchuthananthavale Branavan, Harr Chen, Luke S Zettlemoyer, and Regina Barzilay. Reinforce- ment learning for mapping instructions to actions. In Association for Computational Linguistics, 2009.
SRK Branavan, Nate Kushman, Tao Lei, and Regina Barzilay. Learning high-level planning from text. In Association for Computational Linguistics, 2012.
Rudy R Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.
Jonathon Cai, Richard Shin, and Dawn Song. Making neural programming architectures generalize via recursion. In International Conference on Learning Representations, 2017.
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In Interna- tional Conference on Learning Representations, 2019.
John D Co-Reyes, Abhishek Gupta, Suvansh Sanjeev, Nick Altieri, John DeNero, Pieter Abbeel. and Sergey Levine. Guiding policies with language via meta-learning International Conference on Learning Representations, 2019.
10

---

Published as a conference paper at ICLR 2020
Misha Denil, Sergio Gómez Colmenarejo, Serkan Cabi, David Saxton, and Nando de Freitas. Pro- grammable agents. arXiv preprint 1rXiv:1706.063300 2017.
Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, Subhajit Roy, et al. Program synthesis using natural language. International Conference on Software Engineering. 2016.
Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural program meta-induucion. In Advances in Neural Information Processing Systems, 2017a.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International Conference on Machine Learning, 2017b.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidi- rectional transformers for language understanding. In North American Chapter of the Association for Computational Linguistics, 2018.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines, 2017.
Bhuwan Dhingra, Hanxiao Liu, Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Gated- attention readers for text comprehension. In Association for Computational Linguistics, 2017.
Nat Dilokthanakul, Christos Kaplanis, Nick Pawlowski, and Murray Shanahan. Feature control as intrinsic motivation for hierarchical reinforcement learning. arXiv preprint 1rXiv:1705.06777
2017.
Yan Duan. Marcin Andrychowicz, Bradly Stadie, OpenAl Jonathan Ho. Jonas Schneider, Ilya Sutskever, Pieter Abbeel, and Wojciech Zaremba. One-shot imitation learning. In Advances in Neural Information Processing Systems, 2017.
Vincent Dumoulin, Jonathon Shlens, and Manjunath Kudlur. learned representation for artistic style. In International Conference on Learning Representations, 2017.
Chelsea Finn, Tianhe Yu, Tianhao Zhang, Pieter Abbeel, and Sergey Levine. One-shot visual imitation learning via meta-learning. In Conference on Robot Learning, 2017.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. In International Conference on Learning Representations, 2018.
Daniel Fried, Jacob Andreas, and Dan Klein. Unified pragmatic models for generating and following instructions. In North American Chapter the Association for Computational Linguistics, 2017.
Daniel Fried, Ronghang Hu, Volkan Cirik, Anna Rohrbach, Jacob Andreas, Louis-Philippe Morency, Kate Saenko, Dan Klein, and Trevor Darrell. Speaker- follower models for vision-and- language navigation. In Neural Information Processing Systems, 2018.
Taylor
Malik Ghallab, Dana Nau, and Paolo Traverso. Automated Planning: theory and practice. Elsevier.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint UrXiv:1410.555 2014.
Chi Han, Jiayuan Mao, Chuang Gan, Josh Tenenbaum, and Jiajun Wu. Visual concept-metaconcept learning. In Neural Information Processing Systems. 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 1997.
Jie Hu, Li Shen, and Gang Sun. Squeeze-and-eexiiatton networks. In IEEE Conference on Computer Vision and Pattern Recognition, 2018.
Minyoung Huh, Shao- Sun, and Ning Zhang. Feedback adversarial learning: Spatial feedback for improving generative adversarial networks. In IEEE Conference on Computer Vision and Pattern Recognition, 2019.
11

---

Published as a conference paper at ICLR 2020
Michael Janner, Karthik Narasimhan, and Regina Barzilay. Representation learning for grounded spatial reasoning. Association for Computational Linguistics, 2018.
Jermsak Jermsurawong and Nizar Habash. Predicting the structure of cooking recipes. In Empirical Methods in Natural Language Processing, 2015.
Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In International Conference Learning Representations, 2016.
Russell Kaplan, Christopher Sauer, and Alexander Sosa. Beating atari with natural language guided reinforcement learning. arXiv preprint arXiv: 05539, 2017.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In JEEE Conference on Computer Vision and Putlern Recognition, 2019.
Chloé Kiddon, Ganesa Thandavam Ponnuraj, Luke Zettlemoyer, and Yejin Choi. Mise place: Unsupervised interpretation of instructional recipes. In Empirical Methods in Natural Language Processing, 2015.
George Komidaris, Leslie Pack Kaelbling, and Tomas Lozano- Perez. From skills to symbols: Learn- ing symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, 2018
Tejas Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In Advances in Neural Information Processing Systems, 2016.
Miguel
Dianhuan Lin, J Swaroop Guntupalli, and Dileep George. Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs. arXiv preprint 1012::1812.0220 027788, 2018.
Yoonho Lee and Seungjin Choi. Gradient-based meta-learning with learned layerwise metric and subspace. In International Conference Machine Learning, 2018.
Youngwoon Lee, Shao-Hua Sun, Sriram Somasundaram, Edward Hu, and Joseph J. Lim. Com- posing complex skills by learning transition policies. In International Conference Learning Representations, 2019.
Yuan-Hong Liao, Xavier Puig, Marko Boben, Antonio Torralba, and Sanja Fidler. Synthesizing environment-awwre activities via activity sketches. In IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D Ernst. NI2bash: A corpus and semantic parser for natural language interface to the linux operating system. In International Conference on Language Resources and Evaluation, 2018
Yunchao Liu, Jiajun Wu, Zheng Wu, Daniel Ritchie William Freeman, and Joshua B. Tenen- baum. Learning to describe scenes with programs. In International Conference on Learning Representations, 2019.
Jonathan Malmaud, Earl Wagner, Nancy Chang, and Kevin Murphy. Cooking with semantics. In Workshop on Semantic Pursing Association for Computational Linguistics, 2014.
Jiayuan Mao, Honghua Dong, and Joseph J. Lim. Universal agent for disentangling environments and tasks. In International Conference on Learning Representations, 2018
Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B Tenenbaum, and Jiajun Wu. The neuro- symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In International Conference Learning Representations, 2019.
Dipendra Misra, John Langford, and Yoav Artzi. Mapping instructions and visual observations to actions with reinforcement learning. In Empirical Methods in Natural Language Processing, 2017.
12

---

Published as a conference paper at ICLR 2020
Dipendra Misra, Andrew Bennett, Valts Blukis, Eyvind Niklasson, Max Shatkhin, and Yoav Artzi Mapping instructions to actions in 3d environments with visual goal prediction. In Empirical Methods in Natural Language Processing, 2018.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillierap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning, 2016.
Katharina Mülling, Jens Kober, Oliver Kroemer, and Jan Peters. Learning to select and generalize striking movements in robot table tennis. International Journal of Robotics Research, 2013.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Neural Information Processing Systems, 2018.
Arvind Neelakantan, Quoc V Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. International Conference on Learning Representations, 2015.
Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli. Zero-shot task generalization with multi-task deep reinforcement learning. In International Conference on Machine Learning, 2017.
Boris N. Oreshkin, Pau Rodriguez, and Alexandre Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning. In Neural Information Processing Systems, 2018.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. International Conference on Learning Representa- lions, 2017.
Taesung Park, Ming-Yt Yu Liu, Ting-Chun Wang, and Jun-Yan Zhu. Semantic image synthesis with adatiive normalization. In IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. In Advances in Neural Information Processing Systems, 1998.
Deepak Pathak, Parsa Mahmoudich, Guanghao Luo, Pulkit Agrawal, Dian Chen, Yide Shentu, Evan Shelhamer, Jitendra Malik, Alexei A Efros, and Trevor Darrell. Zero-shot visual imitation. In International Conference Learning Representations, 2018.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing, 2014.
Ethan Perez, Harm De Vries, Florian Strub, Vincent Dumoulin, and Aaron Courville. Learning visual reasoning without strong priors. 2017.
Ethan Perez, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron Courville. FILM: Visual Reasoning with General Conditioning Layer. In Association for the Advancement of Artificial Intelligence, 2018.
Mohammad Raza, Sumit Gulwani, and Natasa Milic- Milic-Frayling. Compositional program synthesis from natural language and examples. In International Joint Conference on Artificial Intelligence. 2015.
Scott Reed and Nando De Freitas. Neural programmer-interrreees. In International Conference Learning Representations, 2016.
Nobuyuki Shimizu and Andrew Haas. Learning to follow navigational route instructions. In International Joint Conference on Artificial Intelligence, 2009.
Richard Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Neural Information Processing Systems. 2018.
Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hierarchical reinforcement learning for zero-shot generalization with subtask dependencies. Advances in Neural Information Processing Systems, 2018.
13

---

Published as a conference paper at ICLR 2020
Bradly C. Stadie, Pieter Abbeel, and Ilya Sutskever. Third person imitation learning. In International Conference on Learning Representations, 2017.
Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In International Conference on Machine Learning, 2018.
Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. Association for Computational Linguistics, 2015.
Stefanie Tellex, Thomas Kollar, Steven Dickerson, Matthew R Walter, Ashis Gopal Banerjee, Seth Teller, and Nicholas Roy. Understanding natural language commands for robotic navigation and mobile manipulation. In Association for the Advancement of Artificial Intelligence, 2011.
Richard Socher Tianmin Shu, Caiming Xiong. Hierarchical and interpretable skill acquisition in multi-task reinforcement learning. International Conference Learning Representations, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning, arXiv preprint arXiv: 161, 2017.
Adam Vogel and Daniel Jurafsky. Learning to follow navigational directions. In Association for Computational Linguistics, 2010.
Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J. Lim. Toward multimodal model-agnostic
meta-learning. In Meta-Learning Workshop at Neural Information Processing Systems, 2018.
Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim. Multimodal model-agnostic meta-
learning via task-aware modulation. Neural Information Processing Systems, 2019.
Sida Wang, Samuel Ginn, Percy Liang, and Christoper Manning. Naturalizing a programming language via interactive learning. In Association for Computational Linguistics, 2017a
Ziyu Wang, Josh S Merel, Scott E Reed, Nando de Freitas, Gregory Wayne, and Nicolas Heess. Robust imitation of diverse behaviors. In Advances in Neural Information Processing Systems, 2017b.
Da Xiao, Jo-Yu Liao, and Xingyuan Yuan. Improving the universality and learnability of neural programmerr-nteepreeerrs with combinator abstraction. In International Conference on Learning Representations, 2018
Saining Xie, Sainan Liu, Zeyu Chen, and Zhuowen Tu. Attentional shapecontextnet for point cloud recognition. In IEEE Conference Computer Vision and Pattern Recognition, 2018.
Danfei Xu, Suraj Nair, Yuke Zhu, Julian Gao, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Neural task programming: Learning to generalize across hicrarchical tasks. In International Conference Robotics and Automation, 2018
Pengcheng Yin and Graham Neubig. Tranx:
A transition-basee neural abstract syntax parser for semantic parsing and code generation. In Empirical Methods in Natural Language Processing. 2018.
Tao Yu, Rui Zhang. Kai Yang. Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, et al. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task. Empirical Methods Natural Language Processing. 2018a
Tianhe Yu, Chelsea Finn, Annie Xie. Sudeep Dasari, Tianhao Zhang, Pieter Abbeel, and Sergey Levine. One-shot imitation from observing humans via domain addative learnin.... In Robotics: Science and Systems, 2018h. 8h.
14

---

Published as a conference paper at ICLR 2020
A PROGRAM EXECUTION
We describe our program interpreter in Section 4.1 and provide more details in this section. The program instruction considered in this work contains the following three components: (1) subtasks, (2) perceptions, and (3) control flows. Accordingly, our Program Interpreter is designed to consist of (I) parser to parse each line of the program following the grammar defined by our DSL in figure 2 and (2) program executor which executes the program conditioning on the parsed contents. The interpreter transforms the program into tree-like like object by exploiting its structure (i.e. scopes) and then utilizes the parsed contents to traverse it to execute the program.
program tree built by representing each line of program as tree node. Each tree node is data structure containing members: (1) node.line, the original line in the program, (2) node.isLeeafO. if the current node is leaf node (i.e. subtask), and (3) node.children, all the subroutines of the current node (i.e. the processes under the scope of the current line of program). The interpreter will parse according to the original line contained in the node, and decide whether to call the policy it is leaf node (subtask) or produce query to call the perception module, deciding which child node (subroutine) to go into.
The subroutines of node should correspond to proper scoping of the program. For example, in Figure in the main paper, the line if is_there [River] has subroutines mine ne (Wood), bui 1d bridge (), if agent [Iron] <3, and place (Iron, 1, 1), but not mine (Iron), which should be if agent [Iron] <3's subroutine.
Once the program tree is built, the program executor will perform pre-order traversal to initiate the execution. A Algorithm| summarizes the details of the program execution utilizing the transformed program tree.
Algorithm 1 Program Execution
Require: P: program be executed
Require: s: environmental state
Require: agent policy parameterized by 0, Φ: perception module
Require: node: has member node.line as the original program line and children nodes node.children
procedure EXECUTE(node)
2: if' iode.isLeaf(() then
3:
subtask = parse_ tursssssbbassknode.lnng
4:
#(subtask, 0)
> Calls the agent policy to execute the subtask
5:
else
6:
control_flow perception
parse_ _trl__trllll_ (ett___pecepptoddeelle
7:
= @(perceppiion_query 8)
Calls the perception module with query and state e.g. if, while, loop, calls the subroutines depending on h
8:
control flow h
9:
for child in chiedchildeen do EXECUTE(child)
10:
end for
12:
end if
end procedure
B DSL DESIGN PRINCIPLE
Since different domains require different DSLs, we aim to design our DSL by following design principle that would potentially allow us to casily adapt our DSL to different domain. Specifically, we develop a DSL. design principle that considers general setting where an agent can perceive and interact with the environment to fulfill some tasks. Accordingly, our DSL consist of control flows, perceptions, and actions. While control flows are domain independent, perceptions and actions can be designed based the domain of interest, which would require certain expertise and domain knowledge. We aim to design our DSL that is (1) intuitive: the actions and perceptions are intuitively align with human common sense, (2) modular: actions reasonably distinct and can be used to compose more complex behaviors, and (3) hierarchical: a proper level of abstraction that enables describing long-horizon tasks.
15

---

Published as a conference paper at ICLR 2020
C EXTENDED RELATED WORK
We present an extended discussion of the related work in this section.
Multitask reinforcement learning. To achieve multi-task reinforcement learning, previous works devised hierarchical approaches where RI. agent is trained achieve series of subtasks to accomplish the task. In Andreas et al. (2017a), a sequence of policy sketches is predefined to guide an agent towards the desired goal by leveraging modularized neural network policies. Oh al. (2017) propose to learn controller to predict to either proceed, revert, or stay at a current subgoal, which is sampled from a list of simple symbolic instructions. In this paper, hierarchical tasks are described by programs with increased diversity through branching conditions, and therefore our framework required to determine which branches a program should be executed. On the other hand, the framework proposed by [Sohn et al. (2018) requires subtask graph describing set of subtasks and their dependencies and aims to find the optimal subtask to execute. This is different from our problem formulation where the agent is asked to follow given program/procedurc.
Hierarchical reinforcement learning. Our work is also closely related to hierarchical reinforcement learning, where meta-controller learns to predict which sub- sub-policy to take at each time step (Kulkarni
et al.] 2016 |Bacon et al. [2017] Dilokthanakul et al. 2017] Frans et al.) [2018] Vezhnevets et al. 2017]]
Lee al. 2019; Bakker et al. 2004] Nachum al., 2018 Mao al., 2018). Previous works also
investigated in explicitly specitying sub-policy with symbolic representations for meta-controller to
utilize, or an explicit selection process of lower-level motor skills (Mülling et al. 2013 Tianmin Shu
2018).
Programmable agents. We would like emphasize that our work differs from programmable agents (Denil et al. 2017) in motivation, problem formulations, proposed methods, and contributions. First, Denil al. 2017) concern declarative programs which specify what to be computed (e-g. a target object in a reaching task). However, the programs considered in our work are imperative, which how this to be computed (i.e. procedure). Also, Denil et al. (2017) consider only one-liner
programs that contain only AND, OR, and object attributes. On the other hand, we consider programs that are much longer and describe more complex procedures. While Denil et al. (2017) aim to generalize to novel combinations of object attributes, work is mainly interested in generalizing to more complex tasks (i.e. programs) by leveraging the structure of programs.
Programs vs. natural language instructions. In this work, advocate utilizing programs task representation and propose a modular framework that can leverage the structure of programs to address this problem. Yet, natural language instructions enjoy better accessibility and are more intuitive to users who do not have experience in programming languages. While addressing the accessibility of programs converting natural language instruction to beyond the scope of this work, we look forward to future research that leverages the strengths of both programs and natural language instructions by bridging the gap between these two representations, such as synthesizing programs from natural language (Lin et al. 2018 Desal et al. [016 Raza et al. 2015), semantic parsing that bridges unstructured languages and structural formal languages Yuu al. 2018a; Yin & Neubig 2018), and naturalizing program (Wang et al. 2017a).
structural form is
D DISCUSSIONS ON LEARNED MODULATION MECHANISMS
To fuse the information from an input domain (e.g. an image) with another condition domain (e.g. a language query, image such as segmentation map, noise, etc.), a wide range of works have demonstrated the effectiveness of predicting affine transforms based on the condition to scale and bias the input in visual question answering (Perez et al. 201 8 2017), image synthesis (Almahairi et al. 2018 Karras et al. 2019: Park et al., 2019] Huh et al.] 2019). style transfer (Dumoulin et al. 2017 recognition (Hu et al., 2018; Xie et al. 2018). reading comprehension (Dhingra et al. (017)) sho-shot learning (Oreshkin et al. 2018 Lee Choi 2018). etc. Many of those works present an extensive ablation study to compare the learned modulation against traditional ways to merge the information from the input and condition domains.
Recently, few works have employed similar learned modulation technique reinforcement learning frameworks on learning to follow language instruction (Bahdanau et al.) 2019)) and meta- reinforcement learning (Vuorio al. 2018 2019). However, there has not been comprehensive
16

---

Published as a conference paper at ICLR 2020
ablation study that suggests fusing the information from the input domain (e.g. state) and the condition domain (e.g. a goal or a task embedding) for the reinforcement learning setting. In this work, conduct ablation study in our 2D Minecraft environment where agent is required to fulfill a navigational task specified by a program and show the effectiveness of learning to modulate input features with symbolically represented goal as well present a number of modulation variations (i.e. modulating the fully-connected layers or the convolutional layers or both). We look forward to future research that verifies if this learned modulation mechanism effective in dealing with more complex domains such as robot manipulation or locomotion.
E ADDITIONAL EXPERIMENTAL DETAILS
E.I ENVIRONMENT DETAILS
In the following paragraphs, provide some details of the environment used in this work.
Objects in the environment. The major environmental resources that the agent can interact with are: wood, gold, and iron. There is certain probability that the environment will contain river, which the agent cannot go across unless a bridge is built (or pre-built). The environment surrounded by brick walls, which draws the boundaries of the world.
Agent action space. The agent's actions are (1) crafting actions: including mining (collecting resources), placing, building bridge, and selling item; and (2) motor actions: including moving to four directions (up, down, left, right). The crafting actions are only allowed on the current grid cell the agent is standing on, e.g. the subtask mine (gold) requires the agent to navigate to a specific location containing a gold with motor actions, and then perform the crafting action mine at the current location. To build bridge, the agent should consume one of the wood it possesses. To sell an item, the agent needs to travel to merchant. With certain probabilities, there can be 2 to 4 me mercha recahtts s at different locations.
During training, when each training program is sampled, a valid environment will be randomly initialized, where validity refers to the property that the agent will be able to successfully follow the program with sufficiently provided environmental resources. At test time, we pre-sample 20 valid initialization of the environment with 20 different random seeds to ensure the validity of the two test sets.
Initialization.
Agent observation space (state representations). The state used in our reinforcement learning policy consists of an environment map smap and an inventory status of the agent 8inv Smap is of size 10 x 10 x 9, where each channel-wise slice of size 10 x 10 x represents the binary existence of certain objects at specific location, e.g. if (3, 4, 2) is 1, it means there is a gold at location (3, 4) (environment objects in channel dimension are zero-indexed). The objects represented by the channels ordered as follows: wood, iron, gold, agent, wall, goal (2-D representation of intended goal coordinates), river, bridge, and merchant. The agent inventory status Sinv is augmented with the agent location, resulting in 1-d integer vector of size 5. The ordered entry of such vector is as follows: agent's 's wood counts, agent's iron counts, agent's gold counts, agent's s location coordinate x, and then y.
Goal representations. For our proposed framework, we represent the goal of the subtask as an 1-D vector of size 10, produced by the program interpreter. The first five entries of the goal vector is a one-hot representation of the subtask: goto, place, mine, sell, build iild bridge. The 6th to 8th entries are one-hot representation of the resources: wood, iron, and gold. The last two entries are the intended goal locations. For example, place (i ron, 3, 5) will be represented as [0, 1, 0,0,00 O, O, O, 1,0, 3,3,5, 5). For end-to-end learning models, such goal representation is produced by the input encoder as continuous latent vector representation.
Exemplar environment maps. We show several exemplary rendered environment maps in Figure 6 As can be seen, the essential resources such as wood, gold, iron represented as block objects, where the merchant is depicted by an alpaca. The agent is shown as a female human character. River grids, with br i dige blocks built on it is shown the blue grid cells, where the bridge which should be transformed by wood is of wooden texture. The Boundaries can be seen in the surroundings represented brick wall grids.
17

---

Published as a conference paper at ICLR 2020
(b)
(c)
Figure 6: Exemplar rendered environment map. The agent, objects, and stuff are represented blocks with their corresponding textures. Specifically, the agent is represented as female character, gold d is represented as golden block, wood is shown tree, and iron is represented as sliver block. River is shown grid with water texture while bridge is presented as wooden grid. merchant is shown as an alpaca, which supposed to transport the sold objects. Notice that there are 2 merchants in (a) and (b), while (c) and (d) contains and 4 of them, respectively. The boundaries of the map shown as brick walls.
blue
E.2 GROUND TRUTH PERCEPTIONS FOR END-TO-END LEARNING BASELINES
Since train perception module using ground truth information, provide the ground truth perception information to all our baselines yet failed to elaborate this the original paper. Specifically, every time step, we feed the ground truth perception (i.e. the answer the queries such as env [Gold] d.] > and is_there [River]) to the baseline models. The ground truth perception represented vector that has dimension of the number of all possible queries, and each element corresponds to binary answer to query. Therefore, the baseline models can learn to utilize this ground truth information infer the desired subtasks. During testing time, the baseline models can still access to all this ground truth perception information, even though it is usually not possible in practice. On the contrary, during testing time, our perception module predicts the answer to given queries and the performance of the whole framework depends the predicted answers.
E.3 TASK INSTRUCTIONS DETAILS
Programs. We generate the program sets by sampling program tokens with normal distributions, and constructing them according to the DSL grammar we define. The training is composed of on average 32 tokens and 4.6 lines; the more complex test set, i.e. test-complex, contains on average 65 tokens and 9.8 lines. We include the plotted statisties of various essential properties for the three datasets in Figure 11 Figure 12 and Figure [3] respectively. Note that the maximum indent of program is the maximum depth of its scope or the height of its transformed program tree. The number of recurring procedures includes both while and loop.
Natural language instructions. For each of the three program sets, we chunked them into sev- eral subsets of programs and assign them to annotators for their corresponding natural language translations. The annotators were instructed to read the provided DSL to understand the details of program syntax well some exemplary translations before they allowed to start the task. The annotators were encouraged to give diverse and colloquial translations to avoid constantly giving dull line-by-line translations. The collected (translated) natural language instructions were then cleansed with spell checks and grammatical errors fixes. On average, the annotators used 27, 28, and 61 words describe the instructions for the train, test, and test-complex size of the natural language instructions of 448.
respectively. The total vocabulary
Qualitative results on natural language analysis. We show several example data points from our testing sets in Figure I0 The leftmott column displays natural language instructions, the middle column shows our sampled ground truth programs, while the rightmost column illustrates how language can be ambiguous and lead to possible alternatiee interpreted programs.
E.4 NETWORK ARCHITECTURES
The proposed framework and the end-to-end learning baselines are implemented in TensorFlow (Abadi
al. 2016).
18

---

Published as a conference paper at ICLR 2020
E.4.1 OUR FRAMEWORK
Perception module. The perception module takes a query q and a state as input and outputs response h. A query has a size of 6 x 186, since the longest query has length of 6 and 186 is the dimension of one-hot program tokens. Shorter queries are zero-paddes to this size.
The state map mmap is encoded by CNN with four layers with channel size of 32, 64, 96, and 128. Each convolutional layer has kernel size and stride and is followed by ReL.U nonlinearity. The final feature map is flattened to a feature vector, denoted as fm.
The state inventory Sinv is encoded by a two-layer MLP with a channel size of 32 for both layers. Each fully-connected layer is followed by ReLU nonlinearity. The resulting feature vector is denoted as fi-
Each token in the query is first encoded by a two-layer MLP with channel size of 32 for both layers. Each fully-connecter layer is followed by ReLU nonlincarity. Then, all the query token features are concatenated along the feature dimension to a single vector. This vector is then encoded by another two-layer MLP with a channel size of 32 for both layers. Each fully-connected layer is followed by ReLU nonlinearity. The resulting feature vector is denoted as fq-
All encoded features (fm= ft. and fg) are then concatenated along the feature dimensions to a single vector. This vector is processed by a three-layer MLP with channel size of 128, 64, and 32. Each fully-connected layer is followed by ReL.U nonlinearity. Finally, a linear fully-connected layer produces an output with size of 1, which should have higher value if the response of the query is true and lower otherwise.
Policy. The policy takes goal g and a state as input and outputs an action distribution a, where the state is encoded by two types of modules: (1) a four-layer CNN encoder to encode the state map Smap and (2) a two-layer MLP encode the agent inventory status Sin-
The goal g is encoded by two-layer MLP with a channel size of 64 for both layers. Each fully- connected layer is followed by ReLU nonlinearity. The resulting feature vector is denoted as fg. Given the encoded goal vector, we employ four linear fully-connected layers to predict modulation parameters (7s, (1......)) for the state CNN encoder, where 7/1 and 83 have size 32, "22 and B3 have size 64, 73 and 33 have size 96, and and B4 have size 128. Note that these modulation parameters are predicted for modulating convolutional features (i.e. modulation conv). For modulation fc, a linear fully-connected layer is used to produce 7 and 3 with size 64.
A state map Smap is encoded by four-layer CNN with channel size of 32, 64, 96, and 128. Each convolutional layer has kernel size 3, strides 2, and is followed by ReLU nonlinearity. After each convolutional layer, the produced feature maps e are modulated to ς e + 3, where y and 3 are broadcast along spatial dimensions. The final feature map is flattened feature vector and denoted as fm
A state inventory Sinv is encoded by a two-layer MLP with channel size of 64 for both layers. Each fully-connected layer is followed by ReLU nonlinearity. The resulting feature vector is denoted as JT
The two encoded features (f and f(*) are then concatenated along the feature dimension. Two fully-connected layers are used to process the feature with a channel size of 64 for both layers. Each layer is followed by ReLU nonlinearity. The final encoded feature u is then modulated to f/c f if modulation fc is used.
Finally, the modulated features å are used to produce an action distribution and predicted value V using two separated MLPs. Each MLP has two fully-connected layers with a channel size of 64 for both layers. A linear layer then outputs vector with a size of 8 (the number of low-level actions). Another linear layer outputs a vector with a size of as the predicted value.
E.4.2 END-TO-END LEARNING MODELS
In addition to the input encoder, the end-to-end learning models can utilize a mechanism to remember what subtasks from the instructions have been accomplished. The agent can then explicitly memorize where it stands in the instruction while completing the task. We augment such memorization mechanism utilizing the memory of another LSTM network, taking inputs the encoded states
19

---

Published as a conference paper at ICLR 2020
throughout the execution trajectory. After agent taking each action, the last hidden state encoding the trajectory up to the current step is used to compute attention scores to pool the outputs of the imput encoders. For Tree-RNN encoder, memorization LSTM with the root representation of Tree-RNN before feeding them to subsequent layers. The agent policy network then learns perform task conditioning on this attention- pooled latent instruction vector.
simply concatenate the hidden representation from
We provide details of our various end-to-end learning models in Table Program token embedding is jointly trained with learning the whole module, while GloVe Pennington et al. (2014) (50-D version) used for word embedding when instructions are natural languages.
Model
Parameters
Details
Seq-I.STM
0.62M
LSTM size 128, both program and word embeddings are of dimension 50. Attention LSTM size of 128, Attention weights of size [256 x 128). with bias of size [128]. Word embeddings utilize pre-trained GloVe.
Tree-RNN
0.5IM
Program embeddings are of dimension 128. Attention LSTM size of 128. Composition module (to aggregate all the children repre- sentation of a node) is of size [128 x 128). and output projection weights of size [128 128], with bias of size [128]. The program embeddings are average pooled across the same program line, so that each line will be mapped to a fixed dimension representa- tion. The composition layer is applied when combining pooled embedding from all the children of node.
Transformer 2.63M
Number of hidden layers: 2, with 8 attention heads, and intermedi- atc size of 256. Hidden size is 128, No dropout is applied.
Table 2: Architectural details for end-to-end learning models
E.5 RAW RGB INPUT
To verify if our framework can be extended to using nigh-dimensional raw state inputs (i.e. RGB image) inputs where a hand-crafted policy or perception module might not be easy to obtain, we performed an additional experiment where the perception module and the policy are trained on raw RGB inputs instead of the symbolic state representation. The results suggest that our framework can utilize RGB inputs while maintaining similar performance (93.2% on the test set) and generalization ability (91.4% on the test-complex set).
F.6 FAILURE ANALYSIS
To gain a better understanding of how our proposed framework and the end-to-end learning models work or fail, we conduct detailed failure analysis the exccution traces of our model. The analysis organized as follows:
We first present analysis of our framework the subtasks that appear to be the first failed subtask, which immediately leads to failing the whole task. This analysis sheds some light on which subtasks most commonly cause the failure of task execution. (Section (S..1ionE.661)
We show an analysis of how many time steps each successfully executed subtask takes on average for our framework, through which we explain which subtasks we find be harder than others. (Section [..62)
We show additional visualizations on the completion rates of different end-to-end learning models plotted with metrics not shown in the main paper, where we aim to deliver a more complete view of how these models perform. (Section E.6.3)
E. FIRST FAILURE RATE OF SUBTASKS
As the first step of failure analysis, want get an idea of which subtasks cause the failure of the model in executions more often. To make this possible, we define "first failed subtask" as the first subtask that ends as a failure in unsuccessful execution of a program. Based on this definition,
20

---

Published as a conference paper at ICLR 2020
(x.y
place
place(Gold,x.1)
place(Wood, xxy]
E
0004
0.040
-0.03
ninelTron]
kine(Gald)
wine(Wood)
0.036
build buitd_bridge()
seLLiIron)
sell(Gold)
sell(Wood)
0.033
Figure First failure rate subtasks. Every colored grid shows first failure rate of each subtask. From top- left to bottom-right, cach block of grids show the results for subtask category goto, place, bui quild_br bri dge, mine, and sell. Warmer colors indicate higher first failure rate; while colder colors indicate lower first failure rate. White grids indicate subtasks that either occurs first failed task any execution do exist in the executions that lead figure.
gotolx.yl
place(Tron,xxx x.y)
place(Gold.x.p)
place(Wood.
Avergg Suteadd Time Cov
S.
-48
nine(Iron)
mine(Cold)
vine (Wood)
build bridge()
466
sell(Iron)
Sell(Gold)
(ell(
Figure 8: Average time cost of subtasks. The setup of this plot is similar to that of Figure Warmer colors indicate higher average subtask time cost; while colder colors indicate lower average subtask time cost. White grids indicate subtasks that do not exist in the exccutions that lead to this figure.
further define "first failure rate" as the percentage that an occurrence of a specific subtask turns out to be the first failed subtask of the execution that includes it.
We collect the first failure rate of all subtasks for the result we obtain from running our full model the more complex test set, Lee. test-complex. The results plotted in visually interpretable format in Figure 7 As seen in the figure, subtasks in goto and pllpllccce ace categories are more likely to be the first failed subtask than subtasks in build _ bridge, mine, and sell categories. Within the got and place subtask categories, subtasks requiring the agent to navigate to grid cells nearby the border of the world has a higher first failure rate than ones nearby the center of the world. This shows that these tasks mentioned above are more prone to failure than other subtasks.
E.6.2 AVERAGE TIME COST OF SUBTASKS
Continuing from the previous analysis, we show the average time cost of all successful subtask executions in Figure As can be seen in the figure, subtasks bui dil_biiigeee mi,e, and se categories take relatively smaller number of time steps to complete. In goto and placp ace categories, the closer to border the subtask requires the agent to reach, the more time consuming it gets for the agent complete the subtask. This corresponds to the finding in the analysis of first failure rates that subtasks with destinations close to the border are more likely to fail. In other words, the closer to border the agent has reach, the more likely it is to fail the subtask.
E.6.3 ADDITIONAL ANALYSIS ON END-TO-END LEARNING MODELS COMPLETION RATES
To conclude failure analysis. focus on the variation of completion rates of program executions with respect to different conditioning variables. As shown in Figure 9 plots showing the trends of completion rates while evaluating with different independent variables show that execution failure is
21

---

Published as a conference paper at ICLR 2020
Seq.LSTM
Transfomerr
Tree- RNN
1.0
1.0
1.0
Compbdin Bule
0.8
0.5
Compldun Rate
0.8
0.6
Compleon
9.4
0.1
5.0
7.5
10.0
12.5
15.0
0.0
Number ofEines
Number of Eis
Numbar of Loup on While
1.0
1.0
Compleion Rat
018
Campleiim Rax
0.8
Complciun Bac
0.3
0.6
0.6
9.4
1.0
1.5
2.0
2.5
3.0
2.5
7.5 Namber of Subrasks
5.0
10.0
12.5
15
Max Indest
Namber of Brancees
Figure 9: Additional analysis on completion rates. The results of executing program instructions both datasets used produce the six plots above. In each plot, each color corresponds the two rightmost plots, there is very small number of outliers that extends out of the right boundary of the plot that we omit for visual interpretability reasons, Please note that the use of colors in this figure not the same as that in Figure 5 of the main paper.
different model that we propose.
more common in cases when the program consists of larger number lines, more loops and while statements, and larger number of subtasks. Note that this subtask count is only a summation of the occurrence counts of each subtask in a program, which does not accurately reflect the number of executions each subtask is being invoked (i.e. it does not reflect the repetitive counts when there is loop).
Meanwhile, the effect of the number of if and else statements and the maximum indent values of programs on completion rates seem to vary across different models. For Seq-LSTM model, having larger number of if and else statements or having larger max indent value results in more failures; while for Transformer and Tree-RNN models, having larger values above results instead in fewer failures. This is probably since Transformer and Tree-RNN models designed in way that deals with hierarchical structures with jumps instruction executions better (this point is also mentioned in the main paper). Despite this difference in effects, the overall change in performance when the number of and else statements and the maximum indent value change is much less significant than that in the previous case.
During our analysis, we also designed an algorithm to calculate an estimate to the number of branches program has. Here, the number of branches is defined by the number of distinct sets of lines that program can be executed. For a program without control flows (no if, else-if, else, loop. and while statements), the number of branches is always For if, else-if, and else statements, the exact number of branches these statements incur can be calculated easily. In cases of the loop and while statements, we treat loops as being executed only once and while statements the number of branches. The result shown in the analysis does not reveal clear trend. We attribute this result to two possibilities either the metric we create not accurate enough, or it is not very suitable metric to be inspected.
statements when we calculate
E.7 HYPERPARAMETERS
We use the following hyperparameters to train A2C agents for our model and all the end-to-end learning models: learning rate: 1 x 10-3, number of environment: 64, number of workers: 64, and number of update roll-out steps: 5.
E.8 COMPUTATIONAL RESOURCES
We train all our models on a single Nvidia Titan-X GPU, 40 core Ubuntu 16.04 Linux server.
22

---

Published as a conference paper at ICLR 2020
Language Instructions
Ground Truth Program
Alternative Interpretation
def run():
run():
river, build bridge. Repeat the followings 3 times: mine a gold, and if environment has more than gold, mine iron, and then sell an iron.
is is_there (River)):
us_there[Riverl)
build_bridgel
build_bridgel
loop(3):
loop(3):
(a)
mine(Gold)
nine(Gold)
env (Gold] <
[GolGo 8: nine(Gold)
nine(Go sell(Iron)
sell(Iron)
Place an iron on (7.2) and (b) repeat times, if agent has than 9 iron then sell gold.
def run():
def run():
place(Iron, 7,
loop(5):
loop14): if agent [Iron] 9: selL(Gold)
place(Iron, 7, if agent [Iron] < 9: sell(Gold)
Mine wood first. If agent has more than iron, mine wood. there gold in the environment, place iron at (3.7).
def run():
def run():
mine mine(Wood)
(Wood)
agent [Iron] mine(Wood)
if agent [Ion]] nine (Wood) if is [Gotdee place(Iron, 3, 71
(c)
if is there [Gold]: place(Iron, 3, 7)
Figure 10: Exemplar data and languages ambiguity. The goal of the examples above is to show that natural language instructions while being flexible enough to capture the high-level semantics of the task, can be ambiguous in different ways and thus might lead to impaired performance. In example (a), the modifier "repeat the following 3 times" has an unclear scope, resulting the right side; in example (b). "repeat 4 times" can used to modify either the previous part the description or the latter part of it, resulting in ambiguity; in example (c), the last sentence starting with "If" has unclear scope. In all of the above cases, model that learns to execute instructions presented in natural language format might fail execute the instructions successfully because of the ambiguity of the language instructions.
possible interpretations shown in program format on
Number of Branches
Nax Instent
Number of Subtasks
1.2
2.5
2.0
0.8
0.6
1.0
0.4
Number Lines
Number Recurrin Procodures (Loops)
Number Tokens
0.6
0.4
0.2
1
0.01
0.5
0.00
10
12
40
60
Figure 11: Program set statistics for training set (train).
23

---

Published as a conference paper at ICLR 2020
Number
Max Indlent
Subtasks
2.00
2.4
0.5
1.50
1.0
1.25
0.3
0.6
0.75
0.2
0.25
0.1
0.0
0.00
0.9
1
0.5
1.0
15
2.0
2.5
3.0
3.5
2
Number Lines
Number of Recuriing Procodures (Locps)
Number Tokens
0.5
0.035
2.9
0.025
0.5
9.029
0.019
0.1
0.005
0.5
9.000
Figure 12: Program set statistics for same complexity testing set (test).
1.75
1.50
0.5
1.25
0.4
1.00
10.0
0.3
0.75
7.5
0.2
0.50
0.25
0.1
0.0
0.9
2.0
2.5
3.0
10
12
Number of Line
Number of Recurring Procedures (Loops)
Number Tokons
3.07
1.75
3.06
8.05
0.3
3.04
0.2
0.75
Figure Program set statistics more complex testing set (lest-cumplex).
24


Reviews:
[{"review_id": "rylluKUCtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a reinforcement learning agent that learns to execute tasks specified in a form of programs with an architecture consisting of three modules. The (fixed) interpreter module interprets the program, by issuing queries to a (pre-trained) vision module and giving goals to a policy module that executes them in the environment. The paper also introduces a policy modulation technique, with the goal of modulating the current state with the expected (symbolic) goal. The model is evaluated on a 2D approximation of Minecraft, where it outperforms a set of baselines. In addition, the authors modified the program dataset and re-expressed it in terms of natural language and showed that the baselines perform better with programs than with the natural language instructions.\n\n\nThough I think the general idea of the paper is worth exploring, I find the concrete contribution of the paper a bit thin to the point that I am hesitant to recommend this paper for acceptance. Allow me to explain my objections:\n\nFirst and foremost, this work is very close to work by Denil et al where the execute (in a differentiable fashion) programs in an RL agent. Their work does not have a discrete interpreter per-se, but it does have a differentiable execution of commands. The major difference between these two works would be that Denil et al do not have the vision module (they do mention learning from pixels as future work).\nHowever, that is not entirely true. The model presented here uses a pretrained vision module, which by itself is not a problem and is used in related work [1], but this vision module does not operate on visual input but the symbolic representation of the map. A crucial thing here is that if all of a sudden we want to include a new object on the map, the model won’t be able to use some learned similarity since it would require introducing a new object (slice of the input), as it would should it have been trained on pixels. So technically speaking, this is not a vision module but a symbolic state processing module.\n\nThen, the modulation mentioned in the paper does not seem particularly novel. Sure, the exact architecture of the model is probably unique, but the idea of modulating a state with a goal is not and has been seen in other work such as [2] and [3] among others. The paper does not mention why, for example, this modulation technique is useful and why any other similar architecture would not be as successful, nor does it mention related modulation techniques in other work.\n\nA big issue I have with the evaluation in the paper is that I do not see the benefit of having the experiments with natural language at all. The focal point of the paper are agents able to execute tasks in the form of programs. The (though manually) generated natural language instructions from those same programs cannot even be used by the proposed agent as there is no natural language interpreter, so they are a dangling part of the paper which is there just to showcase that programs should be easier for baselines to learn to execute than natural language (the hypothesis would be that a simpler and more structured/formal language is easier to learn than the natural language). Hence the seq-LSTM results on language which are a tad lower than the results on programs are expected, though the performance of transformers is the opposite---they are better on language, and that is something that is puzzling and left unexplained, as well as the unexpectedly low performance of Tree-RNNs. One would expect them to perform a bit better than LSTMs, but that might be contingent on the size of the dataset more than the structure of the inputs. However, none of these curious findings have been explained.\nMoreover, the comparison to baselines is not particularly fair as these baselines had to learn the symbolic state interpretation, whereas your model did not. You could have provided the same to the baselines for a better comparison.\n\nIn addition to that, 5.4.2 goes into detail of analysing the baselines, and ignoring the proposed model. Why didn’t you include the same statistics for your agent in Figure 5 and said subsubsection?\n\nThe paper is missing some notable related work:\n- S.R.K. Branavan’s work (all but one cited language-instructed agent papers are post 2017) as well as [4]\n- object-oriented and hierarchical RL\n- [5], where they train the neural programmer interpreter from the final reward only, which brings NPI close to this work\n\nQuestions:\n- Figure 5 - There’s a mark for Tree-RNN, but Tree-RNNs are not in any figure. Why didn’t you plot the performance of your model?\n- The setup naturally induces a curriculum - how does it do that if the programs are randomly sampled?\n- You say that your model learns to comprehending the program flow. I’m not sure I would agree with that because what your model learns is to execute single commands. From what it seems, the interpreter is the only part of the model (which is fixed btw) which sees the control flow, whereas the policy just executes singular commands. Did you mean something else by that statement?\n\nMinor issues:\n- You say twice interpreter (i.e. compiler). Given that they’re not the same, and you’re using an interpreter, I suggest omitting the word compiler.\n- Figure 2 is lacking detail. There is no difference between r and i (both being positive integers) other than their descriptions, - operators agent[_], env and is_there lack parameters (non-terminal nodes), and where’s river, bridge, etc?\n\n[1] COBRA: Data-Efficient Model-Based RL through Unsupervised Object Discovery and Curiosity-Driven Exploration\n[2] FeUdal Networks for Hierarchical Reinforcement Learning\n[3] Universal value function approximators\n[4] Vogel et al Learning to follow navigational directions\n[5] Improving the Universality and Learnability of Neural Programmer-Interpreters with Combinator Abstraction", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJgwVEYmcH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 provides a method for instructing an agent using programs as input instructions, so that the agent should learn to contextually execute this program in a specified environment, learning to generalise as needed from perception, and to satisfy concerns that in the language of planning would be called monitoring and execution. The authors provide a method that breaks this problem down into one of interpreting the program (which is crafted separately as a compiler that benefits from a DSL), learning to identify contextual features and then adapting and applying the policy.\n\nThe arguments in this paper are well made but the paper would benefit from better clarifying several points:\n\n1. To start at the very beginning, the authors begin in the first page by giving the impression that the agent has gone directly from an NL instruction and otherwise uninterpreted sensory input to a solution, in the spirit of typical end to end systems, whereas what the authors are proposing is a very different and more pragmatic approach wherein the interpretation of the task is handled prior to learning, so that learning is only applied to smaller subproblems. This could be made clearer in the introduction.\n\n2. In particular, it was unclear how the DSL comes about and what restrictions it places on the problem. The DSL will clearly have an influence because a very different task from MineCraft, say, robot manipulation, would have quite different needs of sensor-driven control and hence the information flows (specifically, the separation between goal identification, context perception and motion execution) would be different. What one puts into the DSL will significantly influence how well the overall framework performs (e.g., the ability to crisply ask is_there is powerful). Have the authors systematically explored this axis of design? Can we hear more in the setup about this?\n\n3. The influence of the domain is once again seen in the modulation mechanism for the goal and the way in which affine transformations enable generalisation. This is of course sensible in 2D spatial navigation but may be less straight forward in other decision making contexts. The authors have been clear enough about what they have done, but I would have found it interesting to understand how much we should expect this particular concept to stretch and where its limitations become more apparent - perhaps in the discussion.\n\nOverall, this is good work and the writing is clear with suitable references. I would note that the authors are revisiting concerns well studied in the planning literature. While the authors do acknowledge HAMs and so on from the HRL literature, they'd make the paper stronger by also tracing the roots of some of these ideas into the rest of planning.\n\nI'll end this review by asking about the relationships between NL instructions and the formal programs. In some domains, the number of realisable programs that map to an ambiguous NL instruction can be large. Equally, not all lay users can write good programs. So, it is worth noting this gap and making clear that this paper does not really address this bit of the overall problem.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Hkx71T7AYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Update: I thank the reviewers for their extensive rebuttal and revision of the paper addressing all of my concerns. I have increased my score.\n\nSummary\nThis paper investigates an important direction: How can RL agents make use of high-level instructions and task decompositions formalized as programs? The authors propose a model for a program guided agent that, conditioned on a program, interprets the program, executes it to query a perception module and subsequently proposes subgoals to a low-level action module. The method outperforms LSTM and Transformer baselines on a Minecraft-like task and generalizes to programs larger than the one seen during training.\n\nStrengths\nContribution in the important direction of training RL agents with instructions and prior knowledge, here in the form of programs\nClearly written paper with good illustrations of the model\nGood performance on generalization task of acting in environments where the programmatic instructions are longer than those seen during training\n\nWeaknesses\nOne of the contributions of the paper is a modulation mechanism (Section 4.3) on the state features that incorporates a goal-conditioned policy. However, a very related approach has been proposed by Bahdanau, Dzmitry, et al. \"Learning to Understand Goal Specifications by Modelling Reward.\" ICLR 2019. They introduced FILM layers that modulate the layers in a ConvNet conditioned on a goal representation. This should be discussed and compared to in the paper.\nI am surprised there is no comparison to other work that conditions on programs or hierarchical RL approaches. For example, the authors mention various works in Section 2, but fail to compare to them or at least explain why a comparison would not be possible.\nAnother point of criticism is that the authors do not use an existing environment, but instead a Minecraft-inspired one similar to Andreas et al, Oh et al. and Sohn et al. This makes a comparison to prior work hard and I would like to understand in what way previous environments were inadequate for the research carried out here.\nOne aspect that I found most interesting in this paper is that the authors also let annotators map the given programs into natural language form. However, there is no discussion of these results. Similarly, there are interesting qualitative analyses in the appendix of the paper that I only stumbled upon by chance. I believe these should be referenced and a short summary should be integrated into the main part of the paper. I would particularly like to see a discussion of limitations already in the main part of the paper.\n\nMinor Comments\np1: I like the motivation of cooking recipes for work on program conditioned learning. There is in fact a paper (probably multiple) from the NLP community that I think could be cited here. The one that comes to my mind is: Malmaud, Jonathan, et al. \"Cooking with semantics.\" Proceedings of the ACL 2014 Workshop on Semantic Parsing. 2014.\np1: I agree with the argument that programs might be favored over natural language to specify goals as they are unambiguous. However, I think this can also be seen as a drawback. Natural language allows us to very efficiently share information, maybe sometimes information that is only disambiguated through observations in the environment. Another advantage is that natural language for instructing learning agents (like people) is abundant on the web, while programs are not.\np2: \"that leverages grammar\" -> \"that leverages a grammar\"\np2: \"we propose to utilize an precise\" -> \"we propose to utilize a precise\"\np2: For learning from video demonstrations, an important prior work is Aytar, Yusuf, et al. \"Playing hard exploration games by watching youtube.\" Advances in Neural Information Processing Systems. 2018.\np3: A deep learning program synthesis work prior to the ones mentioned here is Bošnjak, Matko, et al. \"Programming with a differentiable forth interpreter.\" Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.\np5: Would it make sense to also compare to a purely hand-crafted programmatic policy? I am missing a justification why learning is strictly necessary in the environment considered in this work.\np6 Section 4.4.1: I believe the explanation of the perception module would benefit from a concrete example.\nQuestions to Authors", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a fascinating hybridization approach to incorporating programs as priors over policies which are then refined using deep RL. The reviewers were, at the end of the discussion, all in favour of acceptance (with the majority strongly in favour). An excellent paper I hope to see included in the conference.
Decision: Accept (Spotlight)