Program Synthesis Guided Reinforcement Learning for Partially Observed Environments
Authors: Yichen Yang
Jeevana Priya Inala
Osbert Bastani
Yewen Pu
Armando Solar-Lezama
Martin Rinard
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: program synthesis
reinforcement learning
partial observation

Abstract: A key challenge for reinforcement learning is solving long-horizon planning problems. Recent work has leveraged programs to guide reinforcement learning in these settings. However, these approaches impose a high manual burden on the user since they must provide a guiding program for every new task. Partially observed environments further complicate the programming task because the program must implement a strategy that correctly, and ideally optimally, handles every possible configuration of the hidden regions of the environment. We propose a new approach, model predictive program synthesis (MPPS), that uses program synthesis to automatically generate the guiding programs. It trains a generative model to predict the unobserved portions of the world, and then synthesizes a program based on samples from this model in a way that is robust to its uncertainty. In our experiments, we show that our approach significantly outperforms non-program-guided approaches on a set of challenging benchmarks, including a 2D Minecraft-inspired environment where the agent must complete a complex sequence of subtasks to achieve its goal, and achieves a similar performance as using handcrafted programs to guide the agent. Our results demonstrate that our approach can obtain the benefits of program-guided reinforcement learning without requiring the user to provide a new guiding program for every new task.

Program Synthesis Guided Reinforcement Learning for Partially Observed Environments
Yichen David Yang" MIT EECS & CSAIL
Jeevana Priya Inala Microsoft Research
Osbert Bastani University of Pennsylvania
Yewen Pu Autodesk Research
Armando Solar-1 ezama MIT EECS CSAIL
Martin Rinard MIT EECS CSAIL
Abstract
A key challenge for reinforcement learning is solving long-horizon planning prob- lems. Recent work has leveraged programs to guide reinforcement learning these settings. However, these approaches impose high manual burden on the user since they must provide a guiding program for every new task. Partially ob- served environments further complicate the programming task because the program must implement strategy that correctly, and ideally optimally, handles every possible configuration of the hidden regions of the environment. We propose new approach, model predictive program synthesis (MPPS), that uses program synthesis automatically generate the guiding programs. It trains generative model to predict the unobserved portions of the world, and then synthesizes a program based samples from this model in way that is robust to its uncer- tainty. our experiments, we show that our approach significantly outperforms non-program-guudeet approaches
of challenging benchmarks, including a 2D tiinecrfft-inspice env where the agent must complete a complex sequence of subtasks to achieve its goal, and achieves similar performance using handcrafted programs to guide the agent. Our results demonstrate that our approach can obtain the benefits of program-guie -uidedd reinforcement learning without requiring the user to provide a new guiding program for every new task.
Introduction
Reinforcement learning is prominent technique for solving challenging planning and control
problems [50] 4 Despite significant recent progress, solving long-horizon problems remains
significant challenge due the combinatorial explosion of possible strategies. One promising approach to addressing these issues is to leverage programs to guide the behavior of the agents 3
39
The approaches in this paradigm typically involve three key elements:
Domaif-specific language (DSL): For given domain, the user defines a set of components that correspond to intermediate subgoals that are useful for that domain (c.g.. "get wood" or "build bridge"), but leaves out how exactly to achieve these subgoals.
Task-specific program: For every new task in the domain, the user provides a sequence of components (i.e. program written in the DSL) that, if followed, enable the agent to achieve its goal the task (e.g., ['get wood"; "build bridge"; "get gem"l).
Low-level neural policy: For a given domain, the reinforcement learning algorithm learns option (3) that implements each component (i.e., achieves the subgoal specified by that component). Typically a neural policy is learned as each option.
"Coreepondencce to yicheny @csail.mit.cuu
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Given a new task in a domain, the user provides a program in the DSL that describes high-level strategy to solve that task. The agent then executes the program by deploying the sequence of learned options that correspond to the components in that program.
A key drawback of this approach is programming overhead: for every new task (a task consists of an instantiation of an environment and goal), the user must analyze the environment, design a strategy to achieve the goal, and encode the strategy into a program, with a poorly written program producing a suboptimal agent. Furthermore, partially observed environments significantly complicate the programming task because the program must implement a strategy that correctly, and ideally optimally, handles every possible configuration of the hidden regions of the environment.
To address this challenge, we propose p new approach, model predictive program synthesis (MPPS), that automatically synthesizes the guiding programs for program guided reinforcement learning.
MPPS works with a conditional generative model of the environment and high level specification of the goal of the task to automatically synthesize a program that achieves the goal, with the synthesized program robust to uncertainty in the model. Because the automatically generated agent, and not the user, reasons about how to solve each new task, MPPS significantly reduces user burden. Given a goal specification o, the agent uses the following three steps to choose its actions:
Hallucinator: First, inspired by world-models [29 the agent keeps track of conditional generative model over possible realizations of the unobserved portions of the environment.
Synthesizer:
Next, the agent synthesizes a program that achieves Φ assuming the hallu- cinator g accurate. Since world predictions are stochastic nature, samples multiple predicted worlds and computes the program that maximizes the probability of success.
Executor:
Finally, the agent executes the options corresponding to the components in the program p = [ei;-.;;c cx] for a fixed number of steps N.
If á is not satisfied after N steps, then the above process is repeated. Since the hallucinator now has more information (because the agent has explored more of the environment), the agent now has better chance of achieving its goal. Importantly, the agent is implicitly encouraged to explore since it must do so discover whether the current program can successfully achieve the goal Φ.
We instantiate our approach in the context of a 2D Minecraft- Minecraft-inspired environment 1 57
which call "craft," and "boxxwoord"" environment (76). We demonstrate that our approach significantly outperforms non grooram-ggudees approaches, while achieving a similar performance as using handcrafted programs guide the agent. In addition, we demonstrate that the policy we learn can be transferred to a continuous variant of the craft environment, where the agent is replaced by MuJoCo (66) Ant. Thus, our approach can obtain the benefits of program-guider reinforcement learning without requiring the user to provide a new guiding program for every new task
Related work. In general, program guidance makes reinforcement learning more tractable in at least two ways: (i) provides intermediate rewards and (ii) reduces the size of the search space of the policy by decomposing the policy into separate components. Previous research in program guided reinforcement learning demonstrates the benefits of this approach to guide reinforcement learning in the craft enviromment (22 This previous research requires the user to provide both a DSL for the domain and a program for every new task. Furthermore, their approach requires that the user includes conditional statements in the program to handle partial observability, which imposes even greater burden on the user. In contrast, we only require the user to provide a specification encoding the goal for each new task, and automatically handle partial observability.
There has been work enabling users to write specifications in a high-level language based on temporal logic (39,, with these specifications then translated into shaped rewards to guide learning. Further- more, recent work has shown that even if the subgoal encoded by each component is omitted, the program (i.c., a sequence of symbols) can still aid learning [3]. Unlike our approach, this previous work requires the user to provide the guiding programs and does not handle partial observability.
More broadly, our work fits into the literature on combining high-level planning with reinforcement learning. In particular, there skills (33), including work on inferring options [6]] Most of these approaches focus on MDPs with discrete state and action spaces and fully observed environments. Recent work
long literature on planning with options [6] (also known as
32 74
"The code is available at: htttss//ggthu...coo/ryydv//////p
guided-

---

Lagand
Program: get gmm
Pr Tragram:
gett wood
Gold
coe tartory
Wooo
gam
Grasa
Hallucinated
Hallucinated
gve the
Agent and
dilavert sones
Factory
Toolahed
(a)
(b)
Figure (a) The initial state of an example task for the craft environment. Bright regions are observed and dark ones are unobserved. This particular map has two zones separated by stone boundary (blue line). The first zone contains the agent, 2 irons, and 2 woods; the second contains grass and 1 gem (the goal). The agent represents the high-level structure of the map (e-g., resources each zone) using state features. The ground truth features are the top-right; we only show the counts of gems, irons, and woods in each zone and the zone containing the agent. The two thought bubbles below are features hallucinated by the agent based on the observed parts of the map. In both, the zone that the agent is in contains gem, so the synthesized program is "get gem" (b) The state after the agent took 20 steps (green arrows), failed to obtain the gem, and is now re-synthesizing the program. Having explored more of the map, it predicts that the gem is in different zone, indicated by its two hallucinations. As a result, it synthesizes a program that includes building and using an axe to break the stone, which leads to successful completion of the task.
77 64 49
addresses the challenge of handling continuous state and action spaces by combining high-level planning with reinforcement learning to handle low-level control, but does not handle the challenge of partial observations, whereas our work tackles both challenges.
Classical STRIPS planning 24 cannot handle uncertainty in the realization of the environment. Replanning [60] can be used to handle small changes to an initially known environment, but cannot handle environments that initially completely unknown. There has been work hierarchical planning in POMDPs
677. but this research does not incorporate predicate abstractions (i.e., state features) that can be used, for example, handle continuous state and action spaces. Given multiple possible environments, generalized planning [7 36
can be used to compute plan that is valid for all of them. However, in our setting, oftentimes such plan exists. We instead synthesize a plan that is valid in a maximal number of hallucinated environments. There is also prior work on planning in partially observable environments (9) [8] Unlike our approach, these approaches assume that the effective state space is small, which enables them to compile the problem into a concrete POMDP which can be efficiently solved using POMDP algorithms. We leverage program synthesis (58) with the world models approach [29] to address these issues; generally speaking, our solver-aided plan synthesis approach more flexible than existing planning algorithms that target
59
34
narrower problem settings.
Finally, there has broadly been recent interest in using program synthesis to learn programmatic policies that are more interpretable [71 72 38). verifiable (8, 70 21, and generalizable (37). In contrast, we are not directly synthesizing the policy, but program guide the policy. Appendix C discusses additional related work in a broader context.
2 Motivating Example
Figure lalshows 2D caneecaff--nnpirre crafting game. In this grid world, the agent can navigate and collect resources (e.g., wood), build tools (e.g., a bridge) at workshops using collected resources, and use the tools to traverse obstacles (e.g.. use bridge to cross water). The agent can only observe the 5 x 5 grid around its current position; since the environment is static, any previously observed cells remain visible. single task consists of a randomly generated map (i.e., the environment) and goal (i.e., obtain certain resource or build a certain tool). We consider the meta-learning setting [25]
3

---

we have a set of training tasks for learning the policy, and our goal is to have policy that works well on new tasks occurring in the future.
DSL. premise of our approach is a user-provided DSL consisting of components useful for the domain. Figure 2a shows the DSL for the craft environment. For each component, the user also specifies what the component is expected to achieve as a logical predicate. To deal with high- dimensional state spaces, the logical predicates are expressed over features (s)) of the state-e.g. the logical predicate for "get wood" is
Ji (s = i a =) = (b = connected) A (pf,wood = Pj,wood - 1) A (4oood = 'wood + 1).
This predicate is over sets of features: (i) features a((s), denoted by -, of the initial state 8 (i.e., where execution of the component starts), and (ii) features (s*)), denoted by a +, of the final state s* (i.e., where the subgoal is achieved and execution of the component terminates). The first feature is the categorical feature 2 that indicates the zone containing the agent. In particular, we divide the map into zones that are regions separated by obstacles such water and stone-e.g. the map in Figure Ta has two zones: (i) the region containing the agent, and (ii) the region blocked off by stones. Now, the feature ds. indicates whether zones i and j are connected, Pt.r denotes the count of resource r in zone i, and 4 denotes the count of resource in the agent's 's inventory.
Thus, this formula says that (i) the agent goes from zone i to j. (ii) and are connected, (iii) the count of wood in the agent's s inventory increases by one, and (iv) the count of wood in zone j decreases by one. Appendix A. describes the full set of components we use.
Approach. Before solving any new tasks, for each component c, we use reinforcement learning to train option è that attempts to achieve the subgoal encoded by Given new task, the user specifies the goal of the task as a logical predicate Φ Encoding the goal is typically simple; for example, the goal of the task in Figure laii is getting gem, which is encoded Φ the agent attempts to solve the task as follows.
4gem 2 1. Then
First, based on the observations so far, the agent uses hallucinator g to predict multiple potential worlds, each of which represents possible realization of the full map. Rather than predicting concrete states, it suffices to predict the state features. For instance, Figure Ta shows two samples of the world predicted by gi here, the only values predicts are the number of zones in the map, the type of the boundary between the zones, and the counts of the resources and workshops in each zone. In this example, the first predicted world contains two zones, and the second contains one zone. Note that in both predicted worlds, there is a gem located in same zone as the agent.
Next, the agent synthesizes a program p that achieves the goal & maximal number of predicted worlds. The synthesized program in Figure [a is a single component "get gem," which refers to searching the current zone (or zones already connected with the current zone) for gem. Note that this program achieves the goal for the predicted worlds shown in Figure Ta
Finally, the agent executes the program p- (c1; :..;.-.;0 cs] for fixed number N of steps. In particular, it executes the policy T. of option & = (T,, 3,) corresponding to C, until the termination condition 3, holds, upon which it switches to executing 1 1. In our example, there is only one component "get gem," " so it executes the policy for this component until the agent finds a gem.
In this case, the agent fails achieve its goal since there is gem in its current zone. Thus, it repeats the above process. Since now has more observations, 9 more accurately predicts the Figure shows the intermediate step when the agent re-plans. Note that it now correctly predicts that the only gem is in the second zone. Thus, the newly synthesized program is
p = Iget wood; use workbench; get iron; use factory; use axe; get gem].
for building axe
That is, it builds an axe to break the stone so it can get to the zone containing the gem. Finally, the agent executes this new program, which successfully finds the gem.
3 Problem Formulation
POMDP. We consider a partially observed Markov decision process (POMDP) with states SC R.. actions A C R." observations O C 1R9, initial state distribution Pp. observation function h : S - O,

---

Agent Sampled completions
Hallucitatoo (C-VAE)
Syntheeizer (MAxAAT)
C get R use T use W
= wood iron grass gold gem
T = bridge axe ladder
W = factory workbench toolshed
Executio
ain frctory
(Modular Networki
(a)
Action
(b)
Figure 2: (a) DSL of components for the craft environment; the three kinds of components are get resource (R), use tool (T), and use workshop (W). (b) Architecture of our agent (the blue box).
and transition function f A S. Given initial state Su ~ Po. policy π 0 and time horizon T E N, the generated trajectory is (Su, ag $1 (....... 8r,, ar), where o, h(ss). ((:)). and S = (*,,, az). We assume the state includes the unobserved parts of the environment-e.33 in the craft environment, it represents both the entire map and the agent's current position and inventory.
We consider meta-learning setting, where we have a of sampled training tasks (world configura- tions and goal) and set of test tasks. Our goal is to learn policy using the training set that achieves good performance on the test set.
User-provided components. We consider programs p = [ei; ck] composed of components G E C. We assume the user provides the set of components C. that are useful for the domain. Importantly, these components only need to be provided once for a domain; they are shared across all tasks in this domain. Each component is specified as a logical predicate that encodes the intended behavior of that component. More precisely, e is a logical predicate over s- and st, where s- denotes the initial state before executing and s+ denotes the final state after executing c. For instance, the component
c= (s 8 = (8 a1)
says that if the POMDP is currently in state so, then should transition it 81, and if it is currently in state 82, then should transition to 83. Rather than defining c over the concrete states, we can define it over features ass)) and axs+) of the states in order handle high-dimensional state spaces.
The goal each task specified with logical predicate & over the final state; with components, may be specified over features (s(s) instead of concrete states. Our objective to design an agent that can achieve any given specification & (i.e., act in the POMDP to reach state that satisfies σ) quickly possible.
User-provided goal specification.
4 Model Predictive Program Synthesis
We describe here the architecture of our agent, depicted in Figure 26 It composed of three parts: the hallucinator g, which predicts possible worlds; the synthexizer, which generates a program p that maximizes the probability of success according worlds sampled from g; and the executor, which follows to act the POMDP These parts are run once every steps to generate a program p to execute for the subsequent N steps, until the user-provided specification is achieved.
Hallucinator. First, the hallucinator is conditional generative model trained to predict the unob- served parts of the environment given the observations. To be precise, the hallucinator & encodes distribution g(s o), which trained to approximate the actual distribution P(s o). Then, at each iteration (i.e.,
every N steps), our agent samples worlds $1...., 8.p g(- o). Our technique can work with any type of conditional generative model as the hallucinator; in our experiments, we conditional variational auto-encoder (CVAB) (56).
When using state features, we can have g directly predict the features; this approach works since the synthesizer only needs to know the values of the features to generate program (see below).
5

---

Synthesizer. The synthesizer computes program that maximizes the probability of satisfying ø:
p arg max Ep(elo) [p solves di for ss arg max Σ 1 pp solves @ for رززر
where the sy are samples from g. The objective 4 can be expressed a MaxSAT problem 48 In particular, suppose for now that we are searching over programs p = [ci:... ca. of fixed length k. Then, consider the constrained optimization problem
arg max fE....E
Σ ==1
3s ST
(2)
M
where & and of (for (1,..., k) and ā {-, +} are the optimization variables. Here, E1, -.... Ex encodes the program = [ci;...; ctl, and V encodes the constraints that solves ø for world 8,-i.e.
k
R-1 A
4 3 start A
A
A
W5,oad:
where (i) staa = (sj = = encodes that the initial state is $j. (ii) U3 = ((E, c) + o(s7,577 encodes that if the the rth component p is 6, = c, then the transition from 87 to of on step r satisfies c(57, ++) (iii) v//rr = (s7 = +1+) encodes that the final state of the rth step equals the initial state the (7 + 1)th step, and (iv) y.nend = ó(s encodes that the final state of the last
component should satisfy the user-provided goal ø. We use a MaxSAT solver to solve (2) 16]. Given solution Ş cr.-., EA Ct. the synthesizer returns the corresponding program
(ci
We incrementally search for longer and longer programs, starting from A = and incrementing k until either we find program that achieves at least minimum objective value, we reach maximum program length kimxx at which point we use the best program found so far.
Executor. For each user-provided component E C, we use reinforcement learning to learn an option ē = (T,, B) that executes the component, where π : is policy and 3 O - {0. is a termination condition. The executor runs the synthesized program
each corresponding option ق = (m,, (3)) sequence, starting from = [ci ...; Cj. by deploying particular, it uses action = (or) at each time step I, where o, is the observation on that step, until (r 1, at which point increments т <- + It continues until either it has completed running the program (3x(o,) 1), or after N steps. In the former case, by construction, the goal ò has been achieved, so the agent terminates. In the latter case, the agent iteratively reruns the hallucinator and the synthesizer based on the current observation to get new program. At this point, the hallucinator likely has additional information about the environment, so the new program has a greater chance of success.
Learning Algorithm
Next, we describe our algorithm for learning the parameters of models used by agent. In partieular, there are two parts that need to be learned: (i) the parameters the hallucinator g and (ii) the options è based the user-provie provided components
Hallucinator. The goal to train the hallucinator g(s o) to approximate the actual distribution P(s] o) of the state given the observation We obtain samples (ot, 82) from the training tasks using rollouts from a random agent and train go (s o) using supervised learning. In our experiments, we take ge to be CVAE and train it using the evidence lower bound (ELBo) on the log likelihood [46).
Executor. Our framework uses reinforcement learning learn options that implement the user- provided components c; these options can be shared across multiple tasks. We use neural module networks [3] as the model for the executor policy; but in general our approach can also work with other types of models. In particular, we take ė = (π,, B), where π O + A is neural module and 3 + {0, 1} checks when to terminate execution. First, 3 is constructed directly from c-i.e., returns whether is satisfied based on the current observation Next, we train on the training tasks, which consist randomly generated initial states and goal specifications d. Just for training, we use the ground truth program p synthesized based on the fully observed environment: this approach

---

POEER
41
pod
(a)
(b)
(c)
(d)
Figure 3: (a) The box-world environment. The grey pixel denotes the agent. The goal is get the white key. The unohserved parts of the map is marked with "x". The key currently held by the agent shown in the top-left corner. In this map, the number of boxes in the path to the goal is 4, and contains 1 distractor branch. (b) The ant-craft environment. The policy needs to control the ant to perform the crafting tasks. (c.d) Comparison of behaviors between the optimistic approach (left) and our MPPS approach (right), in task where the goal is to get gold. (c) The state when the optimistic approach first synthesizes the correct program instead the (incorrect) one "get gold". It only does so after observing all the squares in its current zone. (d) The initial state of our MPPS strategy. It directly synthesizes the correct program, since the hallucinator knows the gold is most likely in the other zone based the observations. Thus, the agent completes the task much more quickly.
avoids the need run the synthesizer repeatedly during training. Given p. we sample a rollout {(01, a1. ri).... (or, @r, rr)} by running the current options = (Tr Br) according to the order specified by p (where m, is randomly initialized). We give the agent reward at each step when achieves the subgoal of the component cr. as well as final reward when it achieves the final goal ø. Then, we use actor-critic reinforcement learning [47] to update и. Finally, we use curriculum learning to speed up training-ian -iee we train using tasks that can be solved with shorter programs first [3].
6 Experiments
We empirically show that our approach significantly outperforms prior approaches that do not leverage programs, and furthermore achieves similar performance as an oracle given the ground truth program.
6.1 Benchmarks
2D-craft. We consider 2D Minecraft-inspiiee game 3 (Figure Lap. A map is a 10 x 10 grid, where each grid cell either empty or contains a resource (c.g., wood), obstacle (c.g., water), or workshop. Each task consists of randomly sampled map, initial position, and goal (one of 10 possibilities, either getting a resource or building a tool), which typically require the agent to achieve several intermediate subgoals. In contrast to prior work, agent does not initially observe the entire map; instead, they can only observe cells within two units. Since the environment static, any previously observed cells remain visible. The actions discrete: moving in one of the four directions, picking up a resource, using a workshop, or using tool. The maximum episode length is T 100.
Next, we consider box-world (76), which requires abstract reasoning. It is 12 x 12 grid world with locks and boxes (Figure Ba). The agent is given a key to get started, and its goal is to unlock white box. Each lock locks box in the adjacent cell containing key. Lock and boxes colored; the key needed to open a look is in the box of the same color. The actions are to move in one of the four directions; the agent opens a lock and obtains the key simply by walking over it. We assume that the agent can unlock multiple locks with each key. The agent can only observe grid cells within distance of 3 (as well as the previously observed cells). Each task consists of randomly sampled map and initial position, where the number of boxes in the path to the goal is randomly chosen between but does not help them reach the goal) also randomly chosen between to 4.
Box-world.
4, and the number of "distractor branches" (i.e., boxes that the agent can open
More details about the environments are described in Appendix B.I
7

---

130
30
30:
Gry Endio-and
0.0
360
200
350
436
300
226
338
432
50
228
354 200
200 300 26
200
(a)
(b)
(c)
(d)
Figure 4: (a.b) Training curves for the 2D-craft environment. (c,d) Training curves for the box-world environment. (a,c) The average reward on the test set over the course of training; the agent gets reward of if it successfully finishes the task within the time horizon, and 0 otherwise. (b,d) The average number of steps taken to complete the tasks in the test set. We run all the training with different random seeds, and report the mean and standard error of each metric. We show our approach ("Ours"), program guided agent ("Oracle"), end-to tod neural policy ("End-to-end") world models ("WM"", and relational reinforcement learning ("Relational"), For our approach, we include the episodes used for training the hallucinator in the starting parts of the training curve; since the number of episodes used for hallucinator training substantially smaller than the number of episodes for executor training, the parts for hallucinator training are hardly noticeable.
Table 1: Average rewards and average completion times on the test set for each approach at the end of training. We report the mean and standard error (in parentheses) over random seeds for training.
2D-craft
wox-world
Ant-craft
Reward
Finish step
Reward
Finish step
Reward
Finish step
End-to-end
0.22 (0.01)
82.3 (1.3)
0.85 (0.02)
44.7 (0.6)
0.12 (0.03)
93.1 (2.2)
World models 29
0.23 (0.01)
81.2 (0.7)
0.80 (0.02)
47.2 (0.9)
0.13 (0.01)
91.3 (1.2)
Relational
76
0.77 (0.02)
51.3 (1.6)
Ours
0.70 (0.03)
56.4 (2.0)
0.90 (0.00)
38.6 (0.4)
0.40 (0.01)
79.2 (1.7)
Oracle
0.76 (0.02)
50.4 (1.1)
0.97 (0.01)
30.8 (0.5)
0.43 (0.02)
77.2 (1.6)
6.2 Baselines
End-to-end. A set of DNN policies that solves the tasks end-to-end. It uses one DNN policy per type of goal, i.e. one network will be used solve all tasks with the goal of "get gem", another network for tasks with the goal of "build bridge". This baseline is trained using the same actor-critic algorithm
and curriculum learning strategy as described in Section [5]
World models [29]. This approach handles partial observability by using a generative model to predict the future. trains VAE model that encodes the current observation o, into latent vector 2,, and trains a recurrent model to predict 2++1 based on 21, 2t- Then, it trains a policy using the latent vectors from the VAE model and the recurrent model as inputs.
Relational reinforcement learning 76).. For box- woold,,,,, we also compare with this approach, which uses relational module based on the multi-head attention mechanism 669 for the policy network to facilitate relational reasoning.
Oracle. Finally, we compare to an oracle, which is our approach but given the ground truth program (i.e., guaranteed achieve Φ). This can be seen as the program-guides agent approach [2] This
baseline is an oracle since it strictly requires more information as input from the user.
6.3 Implementation Details
2D-craft. For our approach, we use a CVAE hallucinator, with MLP (with 200 hidden units) encoder/decoder,, trained on 20K (s,0) pairs collected by a random agent. We use the Z3 [16 solver to solve the MaxSAT problems. We use m 3 hallucinated environments, N 20 steps before replanning in our main experiments, and N' = 5 in the example behaviors we show for better demonstrations. We use the same actor (resp., critic) network architecture for the policies across all

---

299999
(b)
(c)
(d)
Figure 5: Example behavior of our policy in task with the goal of getting gem. (a) The start state. The agent initially hallucinates that there a gem in the same zone, thus starts with a simple program "get gem".. (b) After several steps, the agent observes wood and factory. Hallucinating based on these new observations, the agent synthesizes new program that builds a bridge to cross some water and get gem. This is a reasonable guess since wood, iron and factory are part of the recipe to build bridge, therefore the presence of them hints that the solution might be via building a bridge. (c) After the agent finishes the "get wood" component, it observes that there are stones in the map, for which bridge cannot be used. Hallucinating based on these new observations, the agent synthesizes a new program that builds axe cross the stone. This is correct program for this task. (d) The final state. The agent executes the program and successfully gets the gem.
0.940
0.6
Variance (le
37.6
Mean
Table 2: Comparison to optimistic synthesis and random hallucination strategies on the 2D-craft environment.
0.935
37.4
37.2
Number of samples
Number samples
Avg. reward
Avg. finish step
(c) Reward
(f) Finish time
Ours
0.70 (0.03)
56.4 (2.0)
Figure 6: Effect of varying the number of
Optimistic
0.42 (0.02)
70.2 (1.2)
samples m on our approach, evaluated on the box-world over 5 random seeds. Mean and variance of (a) the average reward, (b) the average finishing time on the test tasks.
Random
0.48 (0.02)
72.6 (0.9)
approaches-i.e., i.e., an MIP with 128 (resp., 32) hidden units. We train the policies of each approach on 400K episodes over randomly sampled training tasks, and evaluate on a test set of 50 tasks. F
Box-world. Following [76]. we use a one-layer CNN with 32 kernels of size 3 x 3 to preprocess the map across all approaches. For our approach, we have component for each color where the subgoal is to get the key of that color; see Appendix A.2 for details. For the hallucinator, we use the same architecture in the craft environment but with 300 hidden units, and trained with 100K (s, o) pairs. For the synthesizer, we use m = 3 and N 10. We train the policies for each approach on 200K episodes, and evaluate on a test set containing 40 tasks.
6.4 Results
Ta two columns) shows the performance of each approach at the end of training. Figure 4 shows the training curves. Our approach significantly outperforms the non-program-guiie both in terms of fraction of tasks solved and in time taken to solve them; it also converges faster, demonstrating that program guidance makes learning significantly more tractable. Our approach also performs comparably to the oracle, delivering comparable performance with significantly less user burden. Figure shows the behavior of our policy an example task in the 2D-craft environment; see Appendix B for more examples.
baselines,
The hallucinator is key in our approach to handle partial observations. Here we study the benefit of the learned hallucinator to our approach. First, we test naive strategy for handling partial observations: the agent first randomly explores the map until the current zone is fully observed, then it synthesizes a program and follows it. This strategy only
Effect of the learned hallucinator:
In our experiments. we train the hallucinator and the executor separately; but in general, one can also interleave the training of the two.

---

achieves an average reward of 0.024(+0.004) in 2D-craft, showing that our benchmarks require effective techniques for handling partial observations. We compare to two ablations without learned hallucinator: (i) an optimistic synthesizer that synthesizes the shortest possible program making best-case assumptions about the unobserved parts of the map, and (ii) a random hallucinator that randomly samples completions of the world (See Appendix [B.3] for more details). Table shows the results on the 2D-craft environment. As can be seen, our approach significantly outperforms both alternatives. Figure Bel & 3d shows the difference in behavior between our approach and the optimistic strategy; by using a learned hallucinator, our approach is able to leverage the current observations effectively and synthesize correct program sooner.
Effect of the number of hallucinator samples. We vary the number of hallucinator samples m on box-world. Figure shows shows the results on the test set over 5 random seeds. As can be seen, varying m does not significantly affect the mean performance, but increasing m significantly reduces variance. Thus, increasing makes the policy more robust to the uncertainty in the hallucinator. This fact shows the benefit of using multiple samples and MaxSAT synthesis.
Transfer to MuJoCo Ant. To demonstrate that our approach can be adapted to handle continuous control tasks, we consider a variant of 2D-craft where the agent is replaced by MuJoCo ant [53] (Figure 3b). We consider a simplified setup where we only model the movements of the ant; the ant automatically picks up resources in the grid cell currently occupies. We focus on transfer learning from 2D-craft. In particular, we pretrain a goal-reaching policy for the ant using soft actor-critic [30]: given random goal position, this policy moves the ant to that position. The actions output by each approach are translated into goal position used as input to this goal-reaching policy. We initialize each policy with the corresponding model for 2D-craft and fine-tune it on ant-craft for 40K episodes. Table [ (rightmost column) shows the results. Our approach significantly outperforms the non-program-guide baselines, both in terms of fraction tasks solved and time taken to solve them. This demonstrates that our approach is also effective on tasks involving continuous control under transfer learning setup.
7 Conclusion
We propose an approach that automatically synthesizes programs to guide reinforcement learning for complex long-horizon tasks. Our model predictive program synthesis (MPPS) approach handles partially observed environments by leveraging an approach inspired by world models, where learns generative model over the remainder of the world conditioned on the observations, and then synthesizes a guiding program that accounts for the uncertainty in this model. Our experiments demonstrate that MPPS significantly outperforms comparably to an oracle given a ground truth guiding program. Our results highlight that MPPS can deliver the benefits of program-guided reinforcement learning without requiring the user provide guiding program for every new task.
program-guid
approaches, while performing
One limitation of our approach is that, as with existing program guided approaches, the user must provide a set of components for each domain. This process only needs to be completed once for each domain since the components can be reused across tasks; nevertheless, automatically inferring these components is an important direction for future work. Finally, we do not foresee any negative societal impacts ethical concerns for our work (outside of generic risks in improving robotics capabilities).
Acknowledgments and Disclosure of Funding
We gratefully acknowledge support from DARPA HR001 12000015, NSF CCF-1917852, NSF CCF- 1910769, and ARO W91 INF-2011-0000. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the Army Research Office, the U.S. Government. We thank the anonymous reviewers for their insightful and helpful comments.
References
[1] David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. Value preserving state-action abstractions. In International Conference on Artificial Intelligence and Statistics, pages 1639-1650. PMLR, 2020.
10

---

[2] Greg Anderson, Abhinav Verma, Isil Dillig, and Swarat Chaudhuri. Neurosymbolic reinforce- ment learning with formally verified exploration. arXiv preprint arXiv:2009.12612, 2020.
[3] Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 166-175, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL httL.tttt////rcceediiiii
. mlr. www.erressssoeoeee http://a///naraa1171aa 17a.mmml
[4] Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38, 2017.
[5] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe V. Le, and Charles Sutton. Program synthesis with large language models. CoRR, abs/2108.07733 2021. URL https://arxiv
org/abs/2108. 02732
[6] Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In Inter- national Conference Learning Representations, 2020. URL https:///openreview neet net/ forum?id-BiggipNYaat
[7] Matej Balog, Alexander L. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs, 2017.
[8] Osbert Bastani, Yewen Pu, and Armando
Verifiable reinforcement learning via policy extraction. In Advances in neural information processing systems, pages 2018.
[9] Blai Bonet. High-level planning and control with incomplete information using pomdp's 1998.
[10] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018. URL httpttttp/s/opeeeeiiiiiie http:/wwwwwwe....uiiie.
1d=H1Xw62kRZ
[11] Laurent Charlin, Pascal Poupart, and Romy Shioda. Automated hierarchy discovery for planning in partially observable environments. Advances in Neural Information Processing Systems, 19:
225, 2007.
[12] Qiaochu Chen, Aaron Lamoreaux, Xinyu Wang, Greg Durrett, Osbert Bastani, and Isil Dillig. Web question answering with neurosymbolic program synthesis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implemenia- tion. pages 328-343, 2021.
[13] Xinyun Chen, Chang Liu, and Dawn Song. Towards synthesizing complex programs from onput-output examples, 2018
[14] Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In International Conference on Learning Representationss 2019. URL HRRLhhtps://// httpp:://pperrevie
[15] Yanju Chen, Chenglong Wang, Osbert Bastani, Isil Dillig, and Yu Feng. Program synthesis using deduction-guicde guiided reinforcement learning. In International Conference on Computer Aided Verification, pages 587-610. Springer, 2020.
[16] Leonardo De Moura and Nikolaj Bjørner. Z3:
An efficient smt solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithmss for the Construction and Analysis of Systems, MACASS08/ETAAA 08, page 337-340, Berlin, Heidelberg, 2008 Springer- Verla.. ISBN 3540787992.
[17] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, page 990-998. JoLR. 2017.
11

---

[18] Denise Draper, S. Hanks, and Daniel S. Weld. Probabilistic planning with information gathering and contingent execution. In AIPS, 1994.
[19] Kevin Ellis, Armando synthesis. Advances in neural information processing systems, pages 973-981, 2015.
and Josh Tenenbaum. Unsupervised learning by program
[20] Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Advances in neural information processing systems, pages 6059-6068, 2018.
[21] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In Advances in Neural Information Processing Systems, pages 9169-9175 2019.
[22] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: bootstrapping inductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. pages 835-850, 2021.
[23] Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. Program synthesis using conffit--rrieen learning, ACM SIGPLAN Notices, 53(():420045 435, 2018.
[24] Richard E Fikes and Nils J Nilsson. Strips: A new approach to the application of theorem proving problem solving. Artificial intelligence, 2(3-4):189-208, 1971.
[25] Chelsea Finn, Picter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126-1135. PMLR, 2017.
[26] Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. Integrated task and motion planning. CoRR, abs/2010.01083, 2020. URL http://://axxv..rrrrreo
01083
[27] Edward Groshev, Maxwell Goldstein, Aviv Tamar, Siddharth Srivastava, and Pieter Abbeel. Learning generalized reactive policies using deep neural networks, 2018.
[28] Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In PoPL'1I, January 26-28, 201 Austin, Texas, USA, January 2011.
[29] David Ha and Jürgen Schmidhuber. World models. CoRR, abs/1803, 2018. URL
10122
[30] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In Jen- nifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1861-1870, Stockholmsmässan. Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http //proceedings.nle mlr pwwps//80/eap//p http://80/haaaojaaa. html
[31] Shivam Handa and Martin Rinard. Inductive program synthesis over noisy data. CoRR, 10272
abs/2009.10272. 2020. URL
[32] Mohammadhosein Hasanbeig, Natasha Yogananda Jeppu, Alessandro Abate, Tom Melham, and Daniel Kroening. Deepsynth: Program synthesis for automatic task segmentation in deep reinforcement learning. CoRR, abs/1911.10224 2019. URL hattp://arxivy www.aaiww....abbbaaaaaa ab111911
1911
10244
[33] Karol Hausman, Jost Tobias Springenberg, Ziyu Wang, Nicolas Heess, and Martin Riedmiller. Learning an embedding space for transferable robot skills. International Conference on Learning Representations, 2018.
12

---

[34] Yuxiao Hu and Giuseppe De Giacomo. Generalized planning: Synthesizing plans that work for multiple environments. In Proceedings of the Syenty-Secooe International Joint Conference on Artificial Intelligence Volume Volume Two, IJCAI'11 page 918-923. AAAI Press, 201 1.
ISBN 9781577355144.
[35] Jiani Huang, Calvin Smith, Osbert Bastani, Rishabh Singh, Aws Albarghouthi, and Mayur Naik. Generating programmatic referring expressions via program synthesis. In International Conference on Machine Learning, pages 4495 4906. PMLR, 2020.
[36] León Illanes and Sheila A. Mcllraith. Generalized planning via abstraction: Arbitrary numbers of objects. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01): (3611))7610-7618 v33.0..33000011110
Jul. 2019, doi: IMATartiicle/view/
https:/: http://sssaaaaaaaaaaaaaaaaaa.aa. aaai org/index, php/
[37] Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Representations, 2020.
[38] Jeevana Priya Inala, Yichen Yang. James Paulos, Yewen Pu, Osbert Bastani, Vijay Kumar, Martin Rinard, and Armando Solar-Lezama. Neurosymbolic transformers for multi-agent communication. In NeurlPS, 2020.
[39] Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. In NeurlPS, 2019.
[40] Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Compositional reinforcement learning from logical specifications. arXiv preprint arXiv:2 /3906 2021.
[41] Kishor Jothimurugan, Osbert Bastani, and Rajeev Alur. Abstract value iteration for hierarchical reinforcement learning. In AISTATS, 2021.
[42] Leslie Pack Kaelbling and Tomás Lozano-Pérez, Hierarchical task and motion planning in the now. In 201/ / IEEE International Conference on Robotics and Automation, pages 1470-1477, 2011. doi: 10.1109/ICR..00 201.59903111
[43] Leslie Pack Kaelbling and Tomás Lozano-Pérez, Integrated task and motion planning in belief space. The International Journal of Robotics Research, 32(9-10): 194-1227, 2013. doi: (11177002783344114444000
[44] Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guided deductive search for real-time program synthesis from examples. In International Conference on Learning Representations, 2018. /ttp:
set/foruu?id=ryaDjj -g-- RW
[45] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
[46] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 131261 14, 2013.
[47] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12, pages 1018-1014. MIT Press, 2000. URL https://proceeding. o
ceourips.cc/pappep /1999 /999/
popper.dd..
[48] M W Krentel. The complexity of optimization problems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC '86, page 69-76, New York, NY, USA,
1986. Association for Computing Machinery. ISBN 0897911938, doi: 10. 10.1145/12130.122333
URL https://dolt orgoooo//oo 10. 1141/1111011..1111 12138
[49] Alexander C. Li, Carlos Florensa, Ignasi Clavera, and Pieter Abbeel. Sub-policy adaptation for hierarchical reinforcement learning, 2020.
[50] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 51897540):599-53,, 2015.
13

---

[51] Maxwell Nye, Yewen Pu, Matthew Bowers, Jacob Andreas, Joshua B Tenenbaum, and Armando Solar-Lezama. Representing partial programs with blended abstract semantics. arXiv preprint arXiv:2012. /2964, 2020.
[52] Camille Phiquepal and Marc Toussaint. Combined task and motion planning under partial observability: An optimization-base approach. In 2019 International Conference on Robotics and Automation (ICRA), pages 9000-9006, 2019. doi: 10. WWT.ICAA..001.779999
[53] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference Learning Representations (ICLR), 2016.
[54] Ameesh Shah, Eric Zhan, Jennifer J.
Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri. Learning differentiable programs with admissible neural heuristics. CoRR, 2as/2007.12100. 2020. cattpps//aaree
12101
[55] David E. Shaw, William R. Swartout, and C. Cordell Green. Inferring lisp programs from examples. In Proceedings of the 4th International Joint Conference on Artificial Intelligence Volume 1, IJCAI'75, page 260-267, San Francisco, CA, USA, 1975. Morgan Kaufmann Publishers Inc.
[56) Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 3483-3491, Curran Associates, Inc., 2015. URL http:///////////c/dddng neeuriii neurips pdf
[57] Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hierarchical reinforcement learning for zero-shot generalization with subtask dependencies. In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, page 7156-7166, Red Hook, NY, USA, 2018. Curran Associates Inc.
[58] Armando Solar-Lezama. Program Synthesis by Sketching. PhD thesis, USA, 2008.
[59] Siddharth Srivastava. Foundations and applications of generalized planning. Al Commun., 24
(4):349-351, December 2011. ISSN 0921-7126.
[60] Anthony Stentz et al. The focussed d** algorithm for real-time replanning. IJCAI, volume 95, pages 1652-1655 1995.
[61] Martin Stolle and Doina Precup. Learning options in reinforcement learning. In International Symposium on abstraction, reformulation, and approximation, pages 212-223. Springer, 2002.
[62] Shao-Hua Sun, Te-Lin Wu, and Joseph J. Lim. Program guided agent. International Conference on Learning Representations, 2020. URL URRphtttps//oopeeeevvee wtwpapperrreeeeeeeeeorrrrr net/forum?
id=BkxUVnEYDD
[63] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2): 181-211, 1999.
[64] Chen Tessler, Shahar Givony, Tom Zahavy, Daniel J. Mankowitz, and Shie Mannor. A deep hierarchical approach lifelong learning in minecraft, 2016.
[65] Yonglong Tian, Andrew Luo, Xingyuan Sun, Kevin Ellis, William T Freeman, Joshua B Tenenbaum, and Jiajun Wu. Learning to infer and execute 3d shape programs. arXiv preprint urXiv:1901.02877 2019.
[66] E. Todorov, Erez, and Tassa. Mujoco: physics engine for model-based control. In 20/2 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 0026-5033, 2012. doi: 10. 10.1109/ 201 2012.6386109.
[67] Mare Toussaint, Laurent Charlin, and Pascal Poupart. Hierarchical pomdp controller optimiza- tion by likelihood maximization. In UAI, volume 24, pages 562-570, 2008.
14

---

[68] Lazar Valkov. Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong learning as program synthesis. In Advances Neural Information Processing Systems, pages 8687-8698, 2018.
[69] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017.
[70] Abhinav Verma. Verifiable and interpretable reinforcement learning through program synthesis. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 9902-99999 2019.
[71] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, pages
PMLR, 2018.
[72] Abhinav Verma, Hoang M Le, Yisong Yue, and Swarat Chaudhuri. Imitation-projected pro- grammatic reinforcement learning. NeurIPS, 2019.
[73] Xinyu Wang, Isil Dillig, and Rishabh Singh. Synthesis of data completion scripts using finite tree automata. Proc. ACM Program. Lang.. 1(0OPSLA), October 2017.
[74] Markus Wulfmeier, Dushyant Rao, Roland Hafner, Thomas Lampe, Abbas Abdolmaleki, Tim Hertweck, Michael Neunert, Dhruva Tirumala, Noah Siegel, Nicolas Heess, and Martin Riedmiller. Data-efficient hindsight off- off-policy option learning, 2021.
[75] Halley Young, Osbert Bastani, and Mayur Naik. Learning neurosymbolic generative models via program synthesis. In ICML, 2019.
[76] Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, Murray Shanahan, Victoria Langston, Razvan Pascanu, Matthew Botvinick, Oriol Vinyals, and Peter Battaglia. Deep reinforcement learning with relational inductive biases. International Conference on Learning Representations, 2019. URL httpps:/ wttppp/rrrreeeeett/trrrrrrro h.t.rrmmmid-HH.xaFOCKKKK
[77] Jesse Zhang, Haonan Yu, and Wei Xu. Hierarchical reinforcement learning by discovering intrinsic options, 2021.
[78] Lisa Zhang, Gregory Rosenblatt, Ethan Fetaya, Renjie Liao, William E. Byrd, Matthew Might, Raquel Urtasun, and Richard S. Zemel. Neural guided constraint logic programming for program synthesis. CoRR, Abs/1809.0284D1 2018. URL htttt://axxii
http:/abb//19..02288 02840
[79] Shangtong Zhang and Shimon Whiteson. Dac: The double actor-critic architecture for learning options, 2019.
15


Reviews:
[{"review_id": "qZ2TaPQfHz", "reviewer": "Reviewer_SkvM", "summary": "The submission proposes a method for program synthesis in partially observable domains in reinforcement learning. The approach aims to handle uncertainty regarding the environment by using three key components: a hallucinator module, a synthesiser module and an executor module.\n\nThe hallucinator is a conditional generative model aiming to predict likely states of the environment. These are used by the synthesiser to generate a program which finally is used by the executor which runs the corresponding subroutines in the order given by the program.\n\nThe method is evaluated on three benchmarks including 2 gridworlds with discrete action space and 1 MuJoCo environment with continuous action space. Across these domains, the proposed method performs better than a set of non-program synthesis baselines. The experiments finish with a set of ablations for the hallucinator.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "The paper is overall well written, clear and easy to follow. The structure is understandable and the problem is well defined. The method performs better than a set of baselines and the additional ablations are quite helpful in understanding the key component of the paper: the hallucinator which enables addressing partially observed environments.\n\nFor the related work, I have to acknowledge that I am less familiar with STRIPS planning in POMDPs but connections to older work relating planning in partially observable domains or in connection with uncertainty such as [1, 2] would be helpful.\nIn addition, the statement about the options framework is not accurate as it has been adapted in many forms to also address partial observability and continuous actions [3,4].\n\nRegarding the experiments, there are a couple of open questions, in particular on the handling of partial observability. Why does the environment automatically store all previously observed states (L99)? This might work into simple 2d environments but would completely break in 3D environments where significant amounts of data would be generated. On a side note, it might make sense to first complete the problem definition before giving an example which uses the formalisms which are only later introduced (Section 2 could be better placed after Section or even later).\n\nFor a more general (and continuous/non-simplified domain) the generation of all options in advance might be challenging or impossible as policies need to be trained for all possible initial conditions in order to prevent distribution shift (and problems with generalisation). Even if skipped in the main paper, it would be relevant to mention this as a shortcoming and point towards future possibilities.\n\nFurther questions focus on the results:\nAre the training episodes for the hallucinator (random agent data) included in the plots? if not then they should be added as this is data not available to other agents.\nIs the state in MuJoCo as abstracted as in the other domains such that the hallucinator does not actually handle continuous spaces? This would be a strong limitation as well.\nWhy is baseline [38] only applied to boxworld?\nWhy no other program synthesis methods were used as baselines in these sections?\nHow do [2] and [31] relate? The question comes up since [2] was already applied to the craftworld domain while [31] is chosen as the oracle baseline here.\nOnly a single paragraph is spent on the main results (beginning 6.4). It would make sense to extend this and elaborate on further details such as why the craft environment seems to be very hard for all non-Oracle baselines. (see later suggestion for freeing space to include these comments.)\n\n(With the assumption of minor corrections) the paper is clear in its contributions, addressed a relevant point and could be a relevant addition to this year’s conference.\n\nMinor suggestions to improve accessibility of the paper\n- Define ‘option’ before using it in line 27.\n- Figure 1 could be moved out of the introduction and into the method section \n- L162 maybe -> may be\n- This is a question of taste but sections 4 and 5 iterate over the same model components and it might be useful to merge the text about learning directly into 4 as well.\n- The implementation details 6.3 could be moved to the appendix to make space for more important points.\n\n\n[1] Bonet, B. (1998). High-Level Planning and Control with Incomplete Information Using POMDP's.\n[2] Draper, D., Hanks, S., & Weld, D. S. (1994, June). Probabilistic planning with information gathering and contingent execution. In AIPS (pp. 31-36).\n[3] Zhang, S., & Whiteson, S. (2019). DAC: The double actor-critic architecture for learning options. arXiv preprint arXiv:1904.12691.\n[4] Wulfmeier, M., Rao, D., Hafner, R., Lampe, T., Abdolmaleki, A., Hertweck, T., ... & Riedmiller, M. (2021, July). Data-efficient hindsight off-policy option learning. In International Conference on Machine Learning (pp. 11340-11350). PMLR.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper adequately mentions limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Gvu4ZLghDXv", "reviewer": "Reviewer_DgEc", "summary": "This paper builds upon previous work using a guiding program over options trained with Reinforcement Learning to solve new tasks in an environment that requires planning.\nIt adds capabilities to deal with partially observable environments and reduces the burden in the user by introducing a world model (hallucinator) and a program synthesiser.\nIn the environments used by the authors, the new method, model predictive program synthesis (MPPS), perform on par with a method that has access to the ground truth program (i.e. requiring extra user intervention) and outperforms baselines that don't use programs.\nFurthermore, the authors demonstrate the capacity of the learned policies and programs to be transferred to a continuous actions domain by replacing the grid world agent with a MuJoCo ant.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "I appreciate this direction of work that brings programs and DNN together to solve new tasks and increase the planning capabilities of current agents. I am particularly excited about the use of MaxSAT solver to optimise over possible programs to solve the current goal.\nThe extensions brought by this work are useful and in the right direction, but I am not satisfied that they are enough to warranty an acceptance to this venue.\n\nTraining world models at the right level of abstraction is still a fairly difficult task and this work uses simplistic setting by having access to the ground truth state of the world the train the generative model. Building the correct state abstraction from observations is crucial in order to plan well. It's unclear how the proposed approach would cope without access to the state privileged information.\n\nAnother unsatisfactory aspect of the approach to handle partially observable environments is the exploration aspect of the policy. The authors assume that by executing one of programs initially proposed, the agent will explore and gather more information about the environment, but this seems to be an artefact of the environments used by the authors. In these environments any policy, even a handcraft exploration policy, will yield good exploration behaviour, gathering useful information to improve future plans. This is not generally true. In certain environments, the optimal way to gather information is by actively exploring the environment and striking the balance between exploration and exploitation is crucial to achieve good performance and data efficiency.\nOne approach is to exploit the uncertainty of the world model to drive exploration, such as in \"Plan To Explore\".\n\nAgain, I am excited about the direction that this work is taking and I look forward to see further improvements and applications in more challenging scenarios.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I appreciate that the authors described related work in good breadth, but my understanding is that some of these other lines of work address different problems to the one that the authors are trying to solve, for example in terms of access to privileged information.\nI would suggest to the authors to introduce a \"Limitations\" session to their work addressing some of the points discussed in my main review. They could then position themselves better with respect to related work in terms of advantages and disadvantages of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "FWTVpfSF7Yv", "reviewer": "Reviewer_F1k5", "summary": "The authors propose to reduce the dependency on user-provided programs for program-guided agents by instead requiring users to submit a goal specification and then automatically synthesizing programs to guide an agent to achieve the given goal specification. The method is novel and a strong technical contribution and the motivation is clear and important. I have some issues with the ablations and experiments that I would like to see addressed in the rebuttal, but I believe this paper should be accepted regardless.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "## Paper Strengths\n**Paper Framing/Motivation**\nThe novelty here is explained well: reducing the supervision/user burden required to create program-guided agents. This is an important motivation, as Program-Guided agents have been shown to be good at performing the types of tasks for the environments tested, but reducing the user burden required to get such approaches to work is important to be able to extend these types of agents to more difficult and realistic environments.\n\n**Technical Contributions**\nThe paper combines generative world models, program synthesis, and reinforcement learning in a cohesive, sensible, and novel manner to tackle the problem setting of automatically synthesizing programs that can guide (option-conditioned) agents to solve tasks. Furthermore, defining the program synthesis task through a MAX-SAT problem reduction and using dedicated MAX-SAT solvers is intuitive, interesting, and sensible.\n\n**Paper Clarity**\nThe paper is well-written and notations are generally clear given the complexity of the method. Introduction is very well-written, and intuitions about what the purpose of each component is and how they’re learned are clear. The paper figures do a good job of describing the method and demonstrating visual examples.\n\n**Experiments**\nHaving 2 different types of environments is great, as a lot of program synthesis works focus on just 1. \n\nThe study of how the number of samples produced by the hallucinator affects the mean and variance of final performance numbers is interesting. It also perhaps signals that a non-sampled hallucinator would work well too. I wonder how many more samples would be needed in non-deterministic environments.\n\n**Results**\nThe method achieves solid performance gains over baselines and manages to perform closely to the oracle on the evaluated tasks.\n\n**Reproducibility**\nIncluded code is comprehensive and comes with a script to reproduce nearly all experiments and plots.\n\n## Paper Weaknesses\n**Experiments**\nI think that the Ant experiment is not that meaningful, especially because the main change is the option policies which are instead trained with Soft-Actor Critic. Once trained with SAC, the policies will do the job of guiding the agent through the environment, therefore negating the difficulty of including the Ant with respect to the interesting parts of the method, namely the hallucinator and program synthesizer. I think a more meaningful transfer experiment would’ve been to transfer the agent to a set of 2D craft environments that are completely unseen during training. In this experiment, the authors would be able to demonstrate the ability of: 1) the hallucinator model to generalize to unseen conditions, and 2) the ability of the program synthesizer guide an agent to solve unseen conditions effectively through inductive biases induced by the design of the hallucinator and programs (compared against naive RL).\n\n**Determinstic environments**\nI believe in non-deterministic environments, the MAX-SAT problem would be more difficult to solve due to it being a probabilistic, constrained optimization problem. It would be great if the authors had a non-deterministic version of one of the environments to see how the performance changes, as non-determinism in the program execution seems to be a hurdle to getting these types of program synthesis works to work on more realistic or more difficult environments.\n\n**Ablations**\nThere should be an ablation where the hallucinator predicts the entire world, not just the state features. This would reveal insights into whether the architecture of the hallucinator is sufficiently powerful to extend this work to more difficult tasks in which these abstract state features are not readily available.\n\n**Related Works**\nRegarding hierarchical RL works: “Recent work has addressed the former [1, 18, 11] by combining high-level planning with reinforcement learning to handle low-level control, but not the latter…” Unless I’m misunderstanding what the authors are stating, this is not true; recent hierarchical RL works can plan with options/skills in partially observed settings by discovering these skills/options automatically through self-supervised objectives or reward-based objectives (even if they don’t directly apply them to POMDPs or call their skills options, they should still work fine). See for example: Hierarchical Reinforcement Learning by Discovering Intrinsic Options (Zhang et al, 2021), Option Discovery using Deep Skill Chaining (Bagaria and Konidaris, 2020), A Deep Hierarchical Approach to Lifelong Learning in Minecraft (Tessler et al, 2016), Sub-policy Adaptation for Hierarchical Reinforcement Learning (Li et al, 2020).\n\n**Minor Issues**\nL107: $s^{-}$ -> $s^{+}$\n\nA couple grammatical issues throughout.\n\n**Questions**\nWhat are the observations given to the learned neural policies $\\pi$? In some environments states become more and more observed as time passes, how are these expanding observations represented and given to $\\pi$ and the CVAE model?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7YECKidkA6t", "reviewer": "Reviewer_456H", "summary": "The paper proposes a framework for program synthesis guided RL that is applicable to partially observable environments. There 3 core components of the proposed approach:\n i) halluncinator - a generative world model approximating p(state | observation) which is pre-trained on the world; \nii) synthesizer - a program synthesizer based on a MaxSAT solver that can generate programs reaching a desired goal from hallucinated states;\niii) executor - a modular neural network that is trained to execute the synthesized programs.\nThe authors demonstrate the capabilities of the proposed framework on 3 problems (2D-craft, box-world, ant-craft) and report better learning performance then other well established methods.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "While the paper does introduce an interesting approach for improving the capabilities of RL agents with program guided synthesis, there are several major issues that I'd like to address.\n\n*Partial Observability.* The authors mention several times that the proposed approach is well suited for partially observable environments and that classic planning methods fail particularly because of the uncertainty in the environment. My biggest concern is that since observations are aggregated and the environment is static it takes very little exploration to turn an initially partially observable environment into a fully observable and completely deterministic environment. For example, one of the considered worlds is 10x10 , the maximum episode time is 100 steps and the agent has 5x5 field of view. In theory, with as little as 10 + 10 + 5 = 25 steps the problem can be turned into perfectly suitable for classical planning. One of the baselines that I feel is missing is an agent that first explores randomly until the full map (or the zone it currently is within) is fully observable and than uses any sort of classical planning. \n\n*State Features.* The considered POMDP model has states its states in R^n, but many of the explanations involve state features \\alpha(s). How is the translation from R^n to a set of logical variables performed? How is the set of these logical variables defined? Does he training of the hallucinator module take into account these logical predicates somehow? If so, how? In many domains beyond grid worlds even just defining these state features requires much more work than writing a short program using these features to solve the problem.\n\n*Executor.* I couldn't really understand what is the role of the executor network. Why is a network needed to execute a policy that follows a synthesized program anyway? Moreover, the Executor section of  5. Learning Algorithm suggests that the executor is pre-trained on trajectories sampled from the program determined from the fully observable environment. This seems to me as a very likely explanation of why the obtained results are so closed to the oracle baseline. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I find the proposed overall architecture quite interesting, but would really like it to be applied to a task beyond symbolic worlds that with a limited amount of effort can be transformed into pure planning problems.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an easy meta-review to write, as the during discussion, the consensus clearly shifted towards a mean of 7 amongst those reviewers who actively responded, with the outlier not having replied to the authors rebuttal. This paper is pretty cool — it proposes a method for program-synthesis guided RL, but does not depend on privileged information in the form of ground truth programs. It performs better than comparable approaches that do not have the inductive bias of program-synthesis within their agents. I'm of the opinion we should see more work in this area at NeurIPS, and the quality of this work definitely warrants it being an exemplar thereof. I recommend acceptance.
Decision: Accept (Spotlight)