Programmable Agents

arXiv:1706.06383v1 [] 20 Jun 2017

Misha Denil Sergio Gómez Colmenarejo
Serkan Cabi David Saxton Nando de Freitas
DeepMind
{mdenil,sergomez,cabi,saxton,nandodefreitas}@google.com

Abstract
We build deep RL agents that execute declarative programs expressed in formal language. The agents learn to ground the terms in this language in their environment,
and can generalize their behavior at test time to execute new programs that refer to
objects that were not referenced during training. The agents develop disentangled
interpretable representations that allow them to generalize to a wide variety of
zero-shot semantic tasks.

1

Introduction

This paper shows how to build agents that can execute declarative programs expressed in a simple
formal language. The agents learn to ground the terms of the language in their environment through
experience. The learned groundings are disentangled and compositional; at test time we can ask the
agents to perform tasks that involve novel combinations of properties and they will do so successfully.
The agents learn to distinguish distinct properties that are referenced together during training; when
trained on tasks that always reference objects through a conjunction of shape and color the agents can
generalize at test time to tasks that reference objects through either property in isolation.
Completely novel object properties can be referenced through the principle of exclusion (i.e. the
object whose color you have not seen before), and our agents are able to successfully complete tasks
that reference novel objects in this way. This works even when the agents have never encountered
programs involving this type of reference during training. Referring to objects that possess multiple
novel properties is also successful, as is referring to objects through combinations of known and
unknown properties.
Our agents are robust to catastrophic forgetting. If we train on a subset of tasks then not only can the
agents accomplish novel tasks zero-shot, but if we switch to training only on the novel tasks then
performance on the original tasks does not degrade.
Our agents are implemented as deep neural networks, and trained end to end with reinforcement
learning. The agents learn how programs refer to properties of objects and how properties are assigned
to objects in the world entirely through their experience interacting with their environment. Natural
and interpretable assignments of properties to objects emerge without any direct supervision of how
these properties should be assigned. No auxiliary prediction or control tasks are required for good
performance (although exploring their effects in this setting is a nice possibility for future work).
The representations learned by our agents are extremely interpretable. There is an explicit mapping
between activation maps in the programmable layers of our agents and terms in the programs they
execute. Visualizing these activation maps provides an immediately interpretable picture of how the
agents assign properties to objects in their world.
The extremely powerful generalization our agents achieve is made possible by our novel “Programmable Network” architecture. Programmable Networks impose a sophisticated bottleneck on
the agent’s representations whose structure ensures that their representations will generalize.
Submitted to 31st Conference on Neural Information Processing Systems (NIPS 2017).

2

Related work

The work in this paper builds on two recent lines of work in deep learning. One is the resurgence of
modular networks that can be decomposed and recomposed to compute different functions. Neural
Module Networks [2, 1], which use modularity in visual question answering, have been particularly
influential on our thinking. This type of approach has also recently seen great success in answering
questions that involve relational reasoning [15, 16].
The second recent trend we follow is the rise of relational neural network architectures, particularly
Interaction Networks [4] and the Neural Physics Engine [8]. At a high level these works on relational
architectures are subsumed by the various neural approaches to graph processing. A nice overview of
recent techniques can be found in Gilmer et al. [12].
Compositionality has become a topic of great interest in machine learning, robotics and cognitive
science [20, 30, 19, 9, 35, 26], and it has been central to research in language [32, 25, 33, 36].
Compositional neural architectures paired with different forms of attention have led to impressive
results in natural language interfaces for database tables, and language acquisition in 2D navigation
environments [28, 37]. Yu et al. [37] present a different deep RL approach to grounding symbols on
perception, and introduce a visual question answering auxiliary task to improve zero-shot generalization. Use of programs to specify hard deterministic gating is also reminiscent of PAQ8 [24, 18].

3

Tasks as declarative programs

Building neural networks that infer or execute computer programs has been a popular topic of recent
research. Different approaches to this problem focus on networks that infer programs [3, 10, 22], on
networks that execute programs [39, 30, 5] and on networks that jointly do both [14, 17, 38, 29, 13];
although there is much overlap between many of these approaches. The majority of these works
model their networks after an imperative programming style, although researchers have also begun to
explore structuring their networks as functional (recursive) programs as well [7, 30].
In this work we depart from previous work by considering networks that execute a simple declarative
language. Paradigmatic examples of declarative languages are PROLOG [6, 5] and SQL. The
declarative paradigm provides an appealing and flexible way to describe tasks for agents [23].
Our general framework is as follows: A goal is specified as a state of the world that satisfies a relation
between two objects. Objects are associated with sets of properties (e.g. their color and shape). The
vocabulary of properties gives rise to a system of base sets which are the sets of objects that share
each named property (e.g. RED is the set of red objects, etc). The full universe of discourse is then the
Boolean algebra generated by these base sets.
We require two things for each program. The verifier has access to the true state of the environment,
and can inspect this state to determine if it satisfies the program. We also need a search procedure
which inspects the program as well as some summary of the environment state and decides how to
modify the environment to bring the program closer to satisfaction.
These components correspond directly to components of the standard RL setup. Notably, the verifier
is a reward function (which has access to privileged information about the environment state) and the
search procedure is an agent (which may have a more restrictive observation space).
There are several advantages to thinking in this way. The first is that building semantic tasks becomes
straightforward, we need only specify a new program to obtain a new reward function that depends
on semantic properties of objects in the environment. Consequently, we can easily specifiy diverse,
combinatorial tasks.
Another advantage is that this framing places the emphasis squarely on generalization to new tasks.
A program interpreter is not very useful if you must enumerate all programs you might want to run
up front. Our goal is not only to perform combinatorial tasks, but to be able to specify new behaviors
at test time, and for them to be accomplished successfully without additional training.
This type of generalization is quite difficult to achieve with deep RL. In this paper we focus on
reaching for blocks, but the simplicity of the individual tasks belies the complexity of what we
achieve. The challenge here is to have agents ground the terms of the programming language in their
environment and, at test time, to be able to execute new programs that use these terms in novel ways.
2

Figure 1: The programmable reaching environment consists of a square arena with a robot arm in
the center. Blocks are scattered randomly and the task in each episode is to reach towards a specific
block, identified by a combination of shape and color. The leftmost frame shows a training episode,
and the remaining frames show various types of generalization that agents trained in this setting are
capable of, including operating on single properties, varying numbers of objects, and novel shapes.

4

Programmable reaching environment

Figure 1 shows several visualizations of our programmable reaching environment, which consists of
a mechanical arm in the center of a large table. The arm is a simplified version of the Jaco arm, where
the body has been stereotyped to basic geoms (rigid body building components [34]), and the finger
actuators have been disabled. In each episode a fixed number of blocks appear at random locations
on the table. Each block has both a shape and a color, and the combination of both are guaranteed
to uniquely identify each block within the episode. The programmable reaching environment is
implemented with the MuJoCo [34] physics engine, and hence the objects are subject to friction,
contact forces, gravity, etc.
Each task in the reaching environment is to put the “hand” of the arm (the large white geom) near
the target block, which changes in each episode. The task is communicated to the agent with two
integers specifying the target color and shape, respectively.
The complexity of the environment can be varied by changing the number, colors and shapes that
blocks can take. In this work we consider 2x2 (two colors and two shapes) and 3x3 variants. We can
also control the number of blocks that appear on the table in each episode, and we fix it to four blocks
during training to study generalization to other numbers. When there are more possible blocks than
are allowed on the table the episode generator ensures that the reaching task is always achievable (i.e.
the agent is never asked to reach for a block that is not present).
The arm has 6 actuated rotating joints, which results in 6 continuous actions in the range [0, 1]. The
observable features of the arm are the positions of the 6 joints, along with their angular velocities.
The joint positions are represented as the sin and cos of the angle of the joint in joint coordinates.
This results in a total of 18 (6 × 2 + 6) body features describing the state of the arm.
Objects are represented using their 3d position as well as a 4d quaternion representing their orientation,
both represented in the coordinate frame of the hand. Each block also has a 1-hot encoding of its
shape (4d) and its color (5d), for a total of 16 object features per block. We provide object features for
all of the blocks on the table as well as the hand, but not for the other bodies that compose the arm.
We can write a reaching program in this environment as
NEAR(HAND, AND(RED, CUBE))

(1)

which specifies that the hand should be near the red cube. This condition can be checked automatically
by the verifier to produce a reward function that takes on the values ±1. The verifier interprets NEAR
by thresholding the distance between its arguments, but this is exposed to the agent only through the
values the reward function takes in different states.
To show zero-shot generalization we partition the set of possible target blocks into train and test
conditions. We train an agent by choosing a target randomly from the train conditions in each episode,
and evaluate the agent on its performance reaching for blocks from the test conditions, which were
never targets during training. We call an assignment of targets to train and test conditions a design.
The left panel in Figure 2 shows the designs we consider for the 2x2 and 3x3 variants of the reaching
environment. Rows and columns of each matrix correspond to different shapes and colors, respectively
and each cell of each matrix corresponds to a different task. The cells are color coded so that yellow
3

Objects
2-L

2-C

Program
Red

Properties

3-D

Blue
White

∧

Cube
Sphere

⌦

Hand

∨

Relevant Objects Vector (p)

Figure 2: Left: Different designs for 2x2 and 3x3 environments. Center: Relationship between Ω
and Φ. The features in Ω have detectors applied to them to produce the disentangled representation
Φ. Right: Example of how the detectors interact with the program. The property detector outputs Φ
are shown as binary to ease interpretation, but in practice they are learned continuous values.
indicates train conditions, and magenta indicates conditions only seen at test time. The magenta tasks
are used to evaluate zero-shot generalization after the agent is trained.

5

Programmable networks

Due to space constraints we describe only the main components of the Programmable Network
architecture in this section. Full details of how everything comes together can be found in Appendix A.
5.1

Executing programs

We begin by explaining how the program operates when given a mapping between objects and
properties, denoted by Φ and explained below. In later sections we expand on this to explain how
the assignment of properties to objects can be learned, and how the assignment process can be made
differentiable to enable end to end training from a behavioural objective; however, for clarity of
presentation it is easiest to begin under the simplifying assumption that the assignments of properties
to objects are crisp (i.e. 0-1) and known.
The input to the program is a matrix Φ whose columns are objects and rows are properties. The
elements of this matrix are in {0, 1} (this will be relaxed later) where Φij = 1 indicates that the
object j has property i.
Figure 2 shows how the set of relevant objects are identified for the example reaching program in
Equation 1. In this example the environment contains four blocks and the robot hand, for a total
of five objects. Each object has two properties, a color and a shape, which are together enough to
uniquely identify it. The set of relevant objects for this program can be expressed as
OR(HAND, AND(RED, CUBE))

(2)

and an indicator function for this set can be obtained by combining the rows of Φ, as explained below.
Each row of Φ corresponds to a particular property that can be referenced in a program, and the
values in the rows serve as indicator functions over subsets of objects that have the corresponding
property. These can be used to select new groups of objects by standard Boolean operations, which
can be implemented by applying elementwise operations to the rows of Φ.
Figure 2 shows how the set in Equation 2 is obtained. The functions AND and OR in the specification
(shown as ∧ and ∨ in the figure) correspond to the set operations of intersection and union, respectively.
The result is a vector whose elements form an indicator function over objects. The set corresponding
to the indicator function contains both the robot hand and the red cube and excludes the remaining
objects.
We call the result of this operation the relevant objects vector and denote it with p (for “presence” in
the set of relevant objects). This vector will play a role in the down stream reasoning process of our
agents.
The order of rows and columns of Φ is arbitrary. We take advantage of this to assign indexes to
named properties in an arbitrary (but fixed) order. This is the same type of assignment that is done
4

for language models when words in the model vocabulary are assigned to indexes in an embedding
matrix, and imposes no loss of generality beyond restricting our programs to a fixed “vocabulary” of
properties.
Note that none of the operations described in this section depend on the number of objects. We will
take advantage of this flexibility in the experiments to show that the behaviors we learn can generalize
to different numbers of objects in the environment.
5.2

Differentiating through program execution

The program execution described in the previous section makes use of set operations on indicator
functions, which are uniquely defined when the sets are crisp; however, this uniqueness is lost if the
sets are soft. We would like to apply programs to soft sets so that the assignment of properties to
objects can be learned by backprop. This requires not only that our set operations apply to soft sets,
but also that they be differentiable.
There are many ways to meet both of these requirements; for our purposes it is convenient to choose
the following assignment:
not(x) = 1 − x

and(x, y) = xy

or(x, y) = x + y − xy

(3)

It can be verified that these operations are self-consistent (e.g. x = not(not(x))), and reduce to
standard Boolean operations when x, y ∈ {0, 1}. This particular assignment is convenient because
each operation always gives non-zero derivatives to all arguments.
5.3

Learned grounding

The discussion in Section 5.1 assumed that the assignment of properties to objects is given; however,
it is much more interesting if our agents can learn to create the matrix Φ rather than having it provided
by the environment. In our architecture learning to populate the elements of Φ is the role of detectors.
A detector operates on a matrix of features Ω. Similar to Φ, the columns of Ω correspond to objects
but the rows of Ω are opaque vectors, populated by whatever information the environment provides
about objects.
We create one detector for each property in our vocabulary. Each detector is a small neural network
that maps columns ωj of Ω to a value in [0, 1]. Detectors are applied independently to each column
of the matrix Ω, and each detector populates a single row of Φ. Groups of detectors corresponding to
sets of mutually exclusive properties (e.g. blocks can only have one color in our experiments) have
their outputs coupled by a softmax. For example, when learning the matrix in Figure 2 each column
is the output of two softmaxes, one over colors and one over shapes.
These columns of Ω are filled with whatever features the environment provides, position, orientation,
etc. These features must have enough information to identify the properties in our vocabulary, but
this information is permitted to be entangled with other features in Ω, while it must be disentangled
in Φ. This relationship is diagrammed in Figure 2.
It would be simple to pre-train the detectors for each property and provide those to the agent. However,
one of the contributions of this paper is to show that with our network architecture we do not need
to do this. Our agents learn to identify meaningful properties of objects and to reason about sets of
objects formed by combinations of these properties in a completely end to end way.
5.4

Relational reasoning

Up to this point we have described completely separate processing for each object. The agent receives
a matrix Ω whose rows are features and columns are objects. We apply a battery of detectors to
each column Ω to create the matrix Φ where rows are properties and columns are again objects. The
program then applies elementwise operations to the rows of Φ to create the relevant objects vector p.
In order to allow reasoning over relationships between objects we introduce a message passing scheme
to exchange information between the objects selected by the relevant objects vector. Our message
passing operation closely resembles an Interaction Network [4] with some additional features.
5

1.0
0.5
0.0
0.5
1.0

Canonical
2-L Train
2-L Eval
2-C

Programmable 2-L

1.0
0.5

0.5

0.0

0.0

2-L Train
2-L Eval

0.5

0

2

4
6
8
Steps (millions)

10

1.0

1.0

0

0.5
1.0
1.5
Steps (millions)

Programmable 3-D

0.5
0.0

3-D Train
3-D Eval

0.5
1.0
0.0

2.0

Distilled 3-D

1.0

1.0

2.0 3.0 4.0
Steps (millions)

3-D Train
3-D Eval

0.5
5.0

1.0
0.0

1.0

2.0 3.0 4.0
Steps (millions)

5.0

Figure 3: Left: Performance of the canonical and programmable architectures on the 2-C and 2-L
environment variants. Center: Training and generalization curves for programmable agents with
learned detectors trained on the 2-L and 3-D reaching variants. Learning is somewhat unstable in
these cases, but successful agents learn to generalize perfectly. Right: Training and generalization
curves for distilled agents trained on the 3-D variant (results for 2-L are similar). Exploiting ground
truth property information at training time substantially stabilizes learning.
Using ωi and ωj to represent columns of Ω, we can write a single round of message passing as
X
ωi0 = f (ωi ) +
αij r(ωi , ωj )
(4)
j

ωi0

where is the resulting transformed features of object i. This operation is applied to each column
of Ω, and the resulting vectors are aggregated into the columns of a new matrix Ω0 . The function
f (ωi ) produces a local transformation of the features of a single object, and r(ωi , ωj ) provides a
message from object j → i. We implement the functions f and r with small MLPs, and structurally
the message passing operation is similar to that of Interaction Networks [4] and the Neural Physics
Engine [8].
Messages between objects are mediated by edge weights αij which are determined using a modified
version of the neighborhood attention operation of Duan et al. [11],
pj exp α̃ij
ci = Linear(ωi )
qi = Linear(ωi )
α̃ij = wT tanh(qi + cj )
αij = P
k pk exp α̃ik
Recall that p is the relevant objects vector (which is a result of the program, see Figure 2), and that its
elements lie in the interval [0, 1]. To understand why they are included in this way, consider what
happens if pj = 0, which means that object j is not a relevant object for the current task. In this
case the resulting αij = 0 also, and the effect is that the message from j → i in Equation 4 does not
contribute to ωi0 . In other words, task-irrelevant objects do not pass messages to task-relevant objects
during relational reasoning.
If we were to consider different types of relations in our programs (beyond NEAR), we would do so
by parameterizing the message passing operation based on the relation to be achieved. Since we
consider only reaching tasks, this extra complexity is not needed in the present work.
After message passing an output can be produced by computing a = MLP(tanh(hΩ0 , pi)). For full
details see Appendix A.

6

Experiments

In this section we look at various ways that agents implemented as Programmable Networks can
generalize. Throughout this section we refer to different variants of the programmable reaching
environment using the names indicated in the left panel of Figure 2. All of our agents are trained
using Deterministic Policy Gradient [31, 21], where both the actor and the critic are Programmable
Networks. See Appendix A for full details of our training setup.
6.1

Standard methods fail to generalize

We start by showing that the programmable reaching environment poses a non-trivial challenge. This
is perhaps not immediately obvious, because the individual tasks (i.e. reaching for a single block)
are very simple. The 2-C design, where all possible target blocks are seen during training, is readily
solved by standard deep architectures. Where standard architectures fail (and do so catastrophically)
is in generalization to unseen combinations of properties.
6

1.0
0.5
0.0
0.5
1.0

train

eval

only only not not three five nine ignore new new new random
color shape color shape blocks blocks blocks new color shape color agent
and shape

Figure 4: Generalization experiments. Each column shows the performance distribution of a single
agent on zero-shot tasks under different conditions. See text for a full description.
For the standard architecture we compare against an architecture similar to the one of Lillicrap et al. [21], modified for feature based observations. We call this the “canonical” architecture as
it has been shown to achieve good performance on many continuous control tasks.
Performance of the canonical architecture on the 2-C and 2-L designs is shown in the left plot of
Figure 3. Reward per step of ~0.6 is effectively perfect performance in these environments.
What we see from these curves is that the canonical architecture achieves good performance on all of
the tasks it was trained on, but in the 2-L case it completely fails to generalize its behavior to reaching
for the held out target. Good performance on 2-C verifies that this is not merely a capacity problem;
when the network is trained on all four tasks it is able to achieve all four.
6.2

Zero-shot tasks

The center plots in Figure 3 show performance curves for the Programmable Agent on the training and
evaluation conditions of the 2-L and 3-D designs. Learning is not always stable, but is nonetheless
successful in many cases. We emphasize that the difficulty here is stability rather than a performance;
agents that succeed in training perform very well in generalization.
Stability of training can be improved by taking advantage of ground truth property information in the
critic at training time. In this setting the actor still learns detectors, but the critic does not. We call
this the “distilled” model, and learning curves for distilled agents on the 3-D design are shown in the
right of Figure 3.
6.3

Strong generalization

Because our architecture partitions the objects into sets that have different properties we can achieve
very strong generalization. Figure 4 shows zero-shot performance of one of our agents with fully
learned detectors (i.e. no distillation) trained on the 3-D design. Each column summarizes the reward
per step achieved by the agent over 100 testing episodes under different generalization conditions.
Figure 4 also shows two baseline conditions. The train condition corresponds to the agent being
tested on new episodes of the tasks it was trained on, and the random condition corresponds to the
performance of the same agent with random weights.
We only show results for the Programmable Agent because we were not successful in training agents
with the canonical architecture on any of 3x3 design. Even when all tasks are seen during training
(the most informative possible 3x3 setting) the canonical architectures were no better than random.
The zero-shot conditions in Figure 4 are as follows:1
•
•
•
•

eval shows performance on the zero-shot tasks of the 3-D design, as shown in Figure 2.
only color/shape shows performance when only the color or shape is specified.
not color/shape shows performance when the color or shape to not reach for is specified.
# blocks show performance of zero-shot tasks with different numbers of blocks on the
table. All training episodes had exactly four blocks.
• ignore new blocks shows the performance of zero-shot tasks in the presence of new
block shapes and colors.

1

Videos for each condition can be found at: https://goo.gl/UkvWYE

7

3-D Train Conditions

1.0
0.5

0.5

0.0

0.0

Train
Eval

0.5
1.0

3-D Eval Conditions

1.0

0

1

2
3
4
Steps (millions)

Train
Eval

0.5
5

1.0

0

1

2
3
4
Steps (millions)

5

Figure 5: Left: performance on the off-diagonal and diagonal tasks for the 3x3 environment. Training
begins on the off-diagonal tasks and switches to the diagonal tasks at 2.5m steps (marked by the solid
black line). The dashed black line shows the point where all transitions from off-diagonal task have
been pushed out of the replay buffer. Right: The learned property matrix Φ (actually its transpose)
produced from the adjacent environment state. See Appendix C for additional visualizations.
• reach new shape shows the performance when reaching for blocks with a novel shape
and known color.
• reach new color shows the performance when reaching for blocks with a novel color
and known shape.
• reach new shape and color shows the performance when reaching for a block when
both the color and shape are novel.
We introduce new blocks by adding an additional shape and color to the set of possible blocks that can
appear on the table (for a total of 16 possible combinations). In the ignore new blocks condition
blocks with the new properties can appear on the table as distractors, but are never the target of
a reaching program. In the only shape and only color conditions we modify the environment
generation process to ensure that the target is uniquely identified by the specified color or shape.
Apart from the train and random conditions, every episode of every task in Figure 4 is zero-shot.
Every program specifies the target in a way the agent did not see at training time. When showing
generalization to different numbers of blocks (in the # blocks conditions) and the ability to ignore
novel distractor blocks (in ignore new blocks) we are showing the agent reaching for a zero-shot
target under these conditions.
The right panel of Figure 5 shows the learned detector outputs in a successful agent. This figure shows
that the agent can correctly identify properties of objects referenced by the programs it executes.
6.4

No catastrophic forgetting

Our agents are robust against catastrophic forgetting. To show this we trained a collection of agents
on the 3x3 environment for 5m steps. For the first 2.5m steps we follow the train condition of the 3-D
design, and for the remaining 2.5m steps we switch to training on the test conditions. The plots in
Figure 5 show performance curves for these agents on both the training and test conditions throughout
the full 5m steps of training. Performance on the train condition does not degrade even millions of
steps after the switching to training on new tasks.

7

Conclusion

Our Programmable Network architecture enables us to build agents that execute declarative programs
expressed in formal language. Our agents learn to ground the terms of the programs in their
environment and can leverage these grounded terms to generalize beyond the tasks they were trained
on. Our agents achieve nearly perfect generalization on a variety of zero-shot tasks where standard
deep RL architectures completely fail.
All of this is achieved with only small concessions from the Deep Learning zeitgeist. We assume that
the boundaries between objects in the agent observations are known, and the object properties our
agents can reason over must come from a predefined vocabulary, which is similar to the restriction one
has in word based language modelling. We also use a fixed mapping from programs to architecture.
Future work will focus on improving the robustness of training, and on scaling the method to deal
with more types of properties (e.g. mass, size, texture, etc) and relations. We are also interested in
extending this method to work from vision.

8

References
[1] J. Andreas, M. Rohrbach, T. Darrell, and D. Klein. Learning to compose neural networks for question
answering. In North American Chapter of the Association for Computational Linguistics, 2016.
[2] J. Andreas, M. Rohrbach, T. Darrell, and D. Klein. Neural module networks. In Computer Vision and
Pattern Recognition, 2016.
[3] M. Balog, A. L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow. DeepCoder: Learning to write
programs. In International Conference on Learning Representations, 2017.
[4] P. W. Battaglia, R. Pascanu, M. Lai, D. Rezende, and K. Kavukcuoglu. Interaction networks for learning
about objects, relations and physics. In Neural Information Processing Systems, 2016.
[5] M. Bošnjak, T. Rocktäschel, J. Naradowsky, and S. Riedel. Programming with a differentiable forth
interpreter. Technical report, University College London, 2016.
[6] I. Bratko. Prolog programming for artificial intelligence. Pearson education, 2001.
[7] J. Cai, R. Shin, and D. Song. Making neural programming architectures generalize via recursion. In
International Conference on Learning Representations, 2017.
[8] M. B. Chang, T. Ullman, A. Torralba, and J. B. Tenenbaum. A compositional object-based approach to
learning physical dynamics. In International Conference on Learning Representations, 2017.
[9] C. Devin, A. Gupta, T. Darrell, P. Abbeel, and S. Levine. Learning modular neural network policies for
multi-task and multi-robot transfer. In IEEE International Conference on Robotics and Automation, 2016.
[10] J. Devlin, J. Uesato, S. Bhupatiraju, R. Singh, A. Mohamed, and P. Kohli. RobustFill: Neural program
learning under noisy I/O. In International Conference on Machine Learning, 2017.
[11] Y. Duan, M. Andrychowicz, B. C. Stadie, J. Ho, J. Schneider, I. Sutskever, P. Abbeel, and W. Zaremba.
One-shot imitation learning. Technical report, OpenAI, 2017.
[12] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum
chemistry. Technical report, Google Brain, 2017.
[13] A. Graves, G. Wayne, M. Reynolds, T. Harley, I. Danihelka, A. Grabska-Barwińska, S. G. Colmenarejo,
E. Grefenstette, T. Ramalho, J. Agapiou, et al. Hybrid computing using a neural network with dynamic
external memory. Nature, 538(7626):471–476, 2016.
[14] E. Grefenstette, K. M. Hermann, M. Suleyman, and P. Blunsom. Learning to transduce with unbounded
memory. In Advances in Neural Information Processing Systems, pages 1828–1836, 2015.
[15] R. Hu, J. Andreas, M. Rohrbach, T. Darrell, and K. Saenko. Learning to reason: End-to-end module
networks for visual question answering. Technical report, University of California, Berkeley, 2017.
[16] J. Johnson, B. Hariharan, L. van der Maaten, J. Hoffman, L. Fei-Fei, C. L. Zitnick, and R. Girshick.
Inferring and executing programs for visual reasoning. Technical report, Stanford, 2017.
[17] Ł. Kaiser and I. Sutskever. Neural GPUs learn algorithms. In International Conference on Learning
Representations, 2015.
[18] B. Knoll and N. de Freitas. A machine learning perspective on predictive coding with PAQ8. In Data
Compression Conference (DCC), 2012, pages 377–386. IEEE, 2012.
[19] T. D. Kulkarni, K. Narasimhan, A. Saeedi, and J. Tenenbaum. Hierarchical deep reinforcement learning:
Integrating temporal abstraction and intrinsic motivation. In Advances in Neural Information Processing
Systems, pages 3675–3683, 2016.
[20] B. M. Lake, T. D. Ullman, J. B. Tenenbaum, , and S. J. Gershman. Building machines that learn and think
like people. Behavioral and Brain Sciences, in press.
[21] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous
control with deep reinforcement learning. In International Conference on Learning Representations, 2015.
[22] W. Ling, D. Yogatama, C. Dyer, and P. Blunsom. Program induction by rationale generation: Learning to
solve and explain algebraic word problems. arXiv preprint 1705.04146, 2017.
[23] M. L. Littman, U. Topcu, J. Fu, C. Isbell, M. Wen, and J. MacGlashan. Environment-independent task
specifications via GLTL. Technical report, Brown University, 2017.
[24] M. V. Mahoney. Adaptive weighing of context models for lossless data compression. Technical report,
CS-2005-16, 2005.
[25] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words
and phrases and their compositionality. In Advances in neural information processing systems, pages
3111–3119, 2013.

9

[26] I. Misra, A. Gupta, and M. Hebert. From Red Wine to Red Tomato: Composition with Context. In
Computer Vision and Pattern Recognition, 2017.
[27] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller,
A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature,
518(7540):529–533, 2015.
[28] A. Neelakantan, Q. V. Le, M. Abadi, A. McCallum, and D. Amodei. Learning a natural language interface
with neural programmer. In International Conference on Learning Representations, 2017.
[29] A. Neelakantan, Q. V. Le, and I. Sutskever. Neural programmer: Inducing latent programs with gradient
descent. In International Conference on Learning Representations, 2016.
[30] S. Reed and N. De Freitas. Neural programmer-interpreters. International Conference on Learning
Representations, 2016.
[31] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller. Deterministic policy gradient
algorithms. In ICML, 2014.
[32] R. Socher, B. Huval, C. D. Manning, and A. Y. Ng. Semantic compositionality through recursive matrixvector spaces. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language
Processing and Computational Natural Language Learning, pages 1201–1211, 2012.
[33] R. Socher, A. Perelygin, J. Y. Wu, J. Chuang, C. D. Manning, A. Y. Ng, C. Potts, et al. Recursive deep
models for semantic compositionality over a sentiment treebank. In Proceedings of the conference on
empirical methods in natural language processing, 2013.
[34] E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In International
Conference on Intelligent Robots and Systems, 2012.
[35] D. Tran, M. D. Hoffman, R. A. Saurous, E. Brevdo, K. Murphy, and D. M. Blei. Deep probabilistic
programming. arXiv preprint 1701.03757, 2017.
[36] D. Yogatama, P. Blunsom, C. Dyer, E. Grefenstette, and W. Ling. Learning to compose words into
sentences with reinforcement learning. arXiv preprint 1611.09100, 2016.
[37] H. Yu, H. Zhang, and W. Xu. A deep compositional framework for human-like language acquisition in
virtual environment. Technical report, Baidu Research, 2017.
[38] W. Zaremba, T. Mikolov, A. Joulin, and R. Fergus. Learning simple algorithms from examples. In
International Conference on Machine Learning, pages 421–429, 2016.
[39] W. Zaremba and I. Sutskever. Learning to execute. arXiv preprint 1410.4615, 2014.

10

A

Model and training details

Our agents are trained using DPG [31, 21], where both the actor and critic are programmable networks.
The full architecture of the actor and critic are shown in Figure A. The actor and critic share the same
programmable structure (including the vocabulary of properties), but they do not share weights.

^

_

p

⌦0

⌦

h
+

a

a
Q

The relationship between Ω, Ω0 , Φ is explained in the main text, as is the derivation of the relevant
objects vector p. In both the actor and critic the vector h is produced by taking a weighted sum over
the columns of Ω0 . Using ωi0 to denote these columns, we can write h as
X
h=
pi ωi0
i

The motivation for weighting the columns by p here is the same as for incorporating p into the
message passing weights in Equation 4; we want h to include only information about relevant objects,
and the role of p is precisely to identify these objects. Reducing over the columns of Ω0 fixes the size
of h to be independent of the number of objects.
From this point the architectures of the actor and critic diverge. Recall that there are two networks
here that do not share weights, so there are in fact two different h vectors to consider. We distinguish
between the activations at h in the actor and critic by using ha to denote h produced in the actor and
hc to denote h produced in the critic.
The actor produces an action from ha using a single linear layer, followed by a tanh to bound the
range of the actions
a = tanh(Linear(tanh(ha ))) .
The computation in the critic is slightly more complex. Although hc contains information about
the observation, it does not contain any information about the action, which the critic requires. We
combine the action with hc by passing it through a single linear layer which is then added to hc
Q(Ω, a) = Linear(tanh(hc + Linear(a))) .
No final activation function is applied to the critic in order to allow its outputs to take unbounded
values.
11

A.1

Building the observation matrix

The observations consumed by our agent are collected into the columns of Ω. The matrix Ω has one
column for each object in the environment, where objects include all of the blocks on the table and
also the hand of the robot arm.
As discussed in Section 4, each object is described by its 3d position and 4d orientation, represented
in the coordinate frame of the hand. Each block also has a shape and a color which are represented
to the agent using 1-hot vectors. There are 4 possible colors and 5 possible shapes for a total of 9
property features (and 16 total features) for each object.
We also provide the joint positions of the arm as observations (encoded as sin and cos of the joint
angle). The arm has 6 joints, for a total of 18 features to represent the arm.
The full observation matrix Ω is built by appending the arm positions to each (object) column, which
effectively represents each object in a “body pose relative” way. This means that in an environment
with four blocks we have an observation of shape 34 × 5 (16 + 18 features per object for each of the
4 + 1 objects).
In addition to the above, we also provide the agent with the index of the hand in Ω, so it does not
need to learn to detect its own body.
A.2

Training parameters

Each reaching episode lasts 10 seconds and controls are issued at 0.1 second intervals, for a total
of 101 observations per episode (including the initial observation at t = 0). Our agents are trained
for either 2m or 5m frames (in the 2x2 or 3x3 environments, respectively). We collect experience
into a replay buffer with a capacity of 1m frames, which we use for training. After each action we
sample a batch of 64 transitions from the replay buffer which is used to update both the actor and
the critic. We use a target network [27] for both the actor and the critic to stabilize training, and we
copy the latest parameters to the target networks after each episode (we do not use the soft updates of
Lillicrap et al. [21]).
All agents are trained with a discount factor of γ = 0.99, and when computing updates for the
actor we clip each element of the gradient from the critic to the range [−1, 1]. During training we
use exploration noise that follows a Ornstein–Uhlenbeck process with standard deviation 0.3 and a
damping factor of 1.0.
The programmable networks use a hidden
layer size of 150 units in both the actor and
the critic. The neighborhood attention operation using a context and query size (ci
and qi ) with 64 units. Detectors are implemented as logistic regressions on object
features.

action

Q

The structure of the canonical actor and
critic networks is shown in Figure 6. In
our experiments these networks have 400
units in each hidden layer and use tanh acaction
tivations throughout. Their weights were
initialized following the strategy of Lillicrap et al. [21]. When training the canonical networks we used the same environobservation
observation
ment parameters as for the programmable
networks. Settings for discounting, target
networks and exploration noise were also Figure 6: Structure of the canonical actor and critic netthe same. The canonical networks accept works. Arrows represent linear layers; tanh activations
vectors of observations (rather than the ma- are used throughout both networks.
trices we feed to the Programmable Networks). We obtain observations for the
canonical networks by flattening the Ω matrix into a vector, ensuring that objects with the same
properties always appear at the same locations in the flattened vector.
12

B

Referencing objects by exclusion
Once you eliminate the impossible, whatever remains, no matter how improbable,
must be the truth. — Sherlock Holmes

Referencing objects by properties they do not have (e.g. “the cube that is not red”) works by exclusion.
To reach for an object without a property we can simply write a program that expresses this. The
program
NEAR(HAND, AND(NOT(RED), CUBE)),
directs the agent to reach for the cube that is not red.
This method of referencing the absence of properties highlights yet another type of generalization
that is taking place. We specified three logical operations in Equation 3, and, or and not; however,
training programs are all of the form
NEAR(HAND, AND(shape, color)),
which do not make use of the not operation. Nonetheless, agents are still capable of executing
programs that contain negations.
The reason this works is that the operations in Equation 3 are compatible. DeMorgan’s laws require
that negation interact with and and or in a particular way, and the rules of classical logic require that
these laws hold. The definition of not we have chosen satisfies these relations, and this is enough for
the not operation to acquire negation semantics in our networks.
Referencing novel colors and shapes works in a similar way. For example let us say we have a
vocabulary of five colors (the procedure for referencing novel shapes is completely analogous), but
only three of them have appeared in the training data. We can label the colors
[RED, GREEN, BLUE, A, B],
where we use generic names like a A and B to stand in for color terms that have never been used (and
so, in principle, could be anything). In this case we can express the concept of “novel color” in two
ways. The first is an exclusive expression,
NOT(OR(RED, BLUE, GREEN)),
which says “not any of the colors that have appeared,” and the second is an inclusive expression,
OR(A, B),
which says “any of the colors that have not appeared.” In practice we have found that combining both
methods
OR(NOT(OR(RED, BLUE, GREEN)), OR(A, B))

(5)

to give the best performance, since it leverages our model’s assumption that every object has exactly
one color (i.e. the soft membership values for all color sets must sum to 1).
Using the technique of Equation 5 we can write a program to reach for the block with a new shape
and a new color as
NEAR(
HAND,
AND(
OR(NOT(OR(RED, BLUE, GREEN)), OR(A, B)),
OR(NOT(OR(CUBE, SPHERE, CYLINDER)), C)
)
)
The programs referencing novel objects are much more complex than the training programs, but
agents perform much better than chance in these cases as well.

13

C

Detector output visualizations

The figures show an environment state along with the corresponding Φ (transposed, so objects are in
rows). Columns corresponding to different properties have been annotated with their corresponding
color and shape terms. Generic names (A, B, C) indicate un-grounded concepts.

C.1

Known properties

Property identification is not always perfect.

14

C.2

Behavior with previously unseen properties

The agent has never seen capsules, or any magenta object.

15

