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 Miinecrfft-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 salshows 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 C 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 Network
(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
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 (or, 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 -ie. 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 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, žt- 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
Table 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 httptttts/s/opeeeeiiiiii 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:://operrevie
[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:///0/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.aaiwww...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 201559933111
[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/
FiL06445544112200866650066666662 Paper. .dff
[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 owgoooo//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. 12964, 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//aarae
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 htpp:////////o 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:/ wttppperrrreee..tt/trrrrrrro h.t.rrmmmid-HHxxaFCCKKKK
[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": "ae1dDDiFyR", "reviewer": "Reviewer_1PbL", "summary": "The authors introduce MPPS, which stands for model predictive program synthesis, a method to leverage programs to guide reinforcement learning in partially observable problems that require planning over long-horizon. MPPS  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. The authors illustrate the performance of their algorithm on a variety of benchmarks including a 2D Minecraft-inspired environment.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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 warmly thank the authors for their work.\n\nI think that the domain covered by this paper is very exciting and that this type of approach is a very promising direction for Reinforcement Learning. However, in this current form this paper exhibits several limitations:\n\n- This paper was very difficult for me to follow. I think it would require more care to introduce the concepts, position the method with respect to the literature, and better detail the examples.\n\n- I did not get in the introduction what is precisely the problem that the authors aim to solve and why the current methods fail to do so. \n\n- At the very beginning of the paper, both concepts Domain-specific language and Task-specific program remain unclear to me. Especially, the example “gather wood” is used for both.\n\n- The authors often mention that their method alleviates the user burden to provide a guiding program for every new task. What the authors mean here remains unclear to me and I believe an example would help to better understand.\n\n- Many concepts are mentioned without being introduced first. For instance, in the very beginning, the authors talk about options without explaining what options are.\n\n- Many mathematical notations are also not properly introduced.  For instance, on page 2 in the definition of the executor, p = c 1 ; ...; c k, the variables c_1, …, c_k are not introduced and I do not understand what they refer to.\n\n- Section 2 covers a motivating example that remains unclear to me. I think that this section is very abstract for a motivating example and that most of the mathematical notations might be kept for later in the paper and replaced here by concrete examples.\n\n- In the related work, the authors missed the literature about Neural Programmer Interpreters and notably AlphaNPI that is also an RL method guided by programs that would be relevant as a baseline in this study.\n\n- The authors mention several times options but do not cover them properly in the related nor compare to them. I think that at least the Option-Critic and HAC should be mentioned, and even compared to, in this study. I understand the point made by the authors that work over options does not cover the partially observed setting however, a simple baseline to validate that this method is more relevant than using options might be to consider an option algorithm such as HAC and add a recurrent core to the high-level policy to handle partial observability.\n\n- The different neural networks architecture as well as the RL agent used to train MPPS remain unclear to me. I think that the paper lacks a section that carefully details these points to enable reproducibility.\n\n- The experiments and the environments considered seem impressive but should be better introduced. The authors might dedicate more space to explain what is the observation space, action space, and reward function. For instance, the Ant-Craft environment is very briefly introduced and it remains unclear to me what it really consists of.\n\n- The authors compare their methods only to ablations. It would be important to consider baselines such as the ones mentioned in the previous points (AlphaNPI, Options method, …).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This method does not add limitations or potential negative societal impact to existing reinforcement learning methods. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "W_I0qpq-lLc", "reviewer": "Reviewer_kENU", "summary": "This paper proposes a neurosymbolic, hierarchical agent architecture which uses program synthesis at the top level of abstraction to generate a symbolic plan. The plan is executed using learned options, which are trained via supervision. To address partial observability, a generative model of symbolic states given observations is trained and used to sample possible states of the world, which the program synthesizer optimizes with respect to. Replanning (i.e. re-running the synthesizer) is performed every so often in order to update the plan/program with newly observed information.\n\nI really like the idea of learning a generative model over states and performing program synthesis with respect to that. This idea has close ties to other approximately Bayes-optimal methods for handling partial observability, and seeing it successfully instantiated in the program synthesis setting is an important contribution. More generally, the topic of the paper is timely and important, as program synthesis and neurosymbolic methods more generally are an important area of current AI research.\n\nHowever, my sense is that this paper is not ready for publication at NeurIPS. This is primarily due to (1) a lack of clarity and (2) inappropriate and poorly-tuned baselines; secondarily, I am also concerned by the (3) overreliance on privileged information, and (4) lack of grounding in the automated planning / TAMP literature (though to a lesser degree than points 1 and 2).", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "**Clarity**\n\nThe paper suffers from a major lack of clarity. I had to re-read the methods multiple times before I felt like I understood what was really being done, and I’m still confused about many things. There are many details missing which make it hard to understand exactly what experiments were run, how they were evaluated, how the baselines are implemented, and so on. I list below some things that particularly confused me, but as a more general recommendation, I would suggest including much more information in the appendix and referring to it liberally. There should be enough information in the paper for someone to be able to reimplement it in entirety, and that is currently far from the case.\n\n* What exactly is included in the observations that the hallucinator is trained on? The paper says “we assume the observation o on the current step already encodes all observations so far”. One part of the paper led me to believe that o was the count of state features (e.g. the number of gems), rather than the full map itself. But after a while longer of combing through the paper, now I’m back to thinking that observation is the more typical use of the word (i.e. the map). But how is this encoded? Is it an image? Is it a more symbolic representation? Also, what does “all observations so far” mean? Is that a matrix of observations from all previous timesteps? Or do you just mean you assume the Markov property here?\n* It sounds like the hallucinator is trained using ground-truth state information, but this is not explicitly stated. Is this true? If not, how do you deal with the fact that a random policy is unlikely to be able to actually observe the full state (since for long-horizon tasks this will be exponentially unlikely)?\n* It’s not clear to me if the hallucinator and executor are trained simultaneously or not, and it’s not clear what the x-axis of Figure 3 shows. Are those episodes required by the executor? Does it include the data required to train the hallucinator, too?\n* There are almost no details given about the baselines, which makes it hard to evaluate whether they are appropriate. For example, with the End-to-End baseline, the paper states there is “one DNN policy per goal”. What does this mean? How are the separate policies trained? How many policies does that amount to? \n* What are the goal specifications that the agent is evaluated on? In your results, are you averaging across different types of goals? Are these evaluated in equal proportion? On line 230, the paper says the goal can be “one of 10 possibilities” but as far as I can tell it is not stated anywhere what these possibilities are. It would help to include this type of detail in the appendix.\n* Do all agents (including baselines) get to see the fully-observed environment during training? The paper states that “just for training [the executor], we use the ground truth program p synthesized based on the fully observed environment (since we can explore the entire map and post-hoc generate p)”. However, this seems to me to put the program synthesis agent at a very unfair advantage compared to the other agents, which presumably don’t get to see the fully-observed environment during training in any capacity. The other agents should either also get to see the fully-observed environment, or you need to explicitly include the data cost for exploring the entire map to generate p. (It’s also not clear to me that all maps can even be fully explored in a reasonable amount of time, given that part of the map may be blocked off by rocks/water).\n\n**Quality**\n\nThere are two issues that pertain to quality: baselines and privileged information.\n\nFirst, the baselines seem poorly chosen and poorly tuned. Given the main contribution of the paper is a method for dealing with partial observability via program synthesis, it would seem to me the more appropriate comparisons would be with either (1) other approaches to program synthesis that don’t account for partial observability or (2) neural approaches that do account for partial observability. However, the paper only compares to neural approaches that don’t deal with partial observability, which seems inappropriate.\n\nBut assuming the choice of baselines themselves is ok, I had a lot of confusion about how they were even implemented (see above), which makes it hard for me to evaluate whether they are fair. From what I was able to gather, I get the impression that they are not. For example, the paper says on Line 266 that “We use the same actor (resp., critic) network architecture 267 across all approaches—i.e., an MLP with 128 (resp., 32) hidden units”, but this seems like a very poor baseline: it is probably not deep enough (the number of layers is not stated, but I’m assuming just 1?), 32 hidden units is almost certainly too small for the critic, and the architecture should probably be a CNN, not an MLP, as MLPs typically do not perform very well in visual/grid-world settings. Similarly, for Box World, where a CNN is used, the paper states that only one 3x3 conv layer is used, which is also probably not the best choice. Why was a different architecture chosen than what was used in the RRL paper (which is two 2x2 convs followed by ReLU)? It is suspicious to me that the relational approach does *worse* on Box World than the other neural approaches, which is the reverse of what was found in the RRL paper. Including experiments in the appendix indicating that these baselines are correctly implemented (e.g., that they succeed at the fully-observed version of the task) would help me have more confidence that they aren’t a strawman comparison.\n\nSecond, the method relies on a lot of privileged information and domain knowledge. Specifically, from what I could tell, the method requires: a DSL, counts of state features (which may include information above and beyond the DSL, e.g. zones, boundaries, etc.), transition operators (referred to as “components” in the paper), a logical goal specification, and access to the fully-observed environment during training. I’m certainly willing to allow for some amount of this; I think it’s hard to make progress with program synthesis and other symbolic approaches without at least allowing access to a DSL (and in much of the TAMP literature, transition operators and goal specifications are also given). But the choice that pushes it over the threshold for me, at least, is to allow the agent to see the fully-observed environment during training, which really just seems like it defeats the purpose. Isn’t the whole point of the paper to have a learning algorithm which can deal with partial observability? \n\n**Originality & Significance**\n\nAs far as I am aware, applying the Thompson sampling technique to program synthesis in order to account for partial observability hasn’t been explored. As I said previously, I think this is a great idea and it’s important to demonstrate how to get it to work in practice.\n\nHowever, the paper tries to lay claim to another contribution which I don’t think is justified: ”the user only needs to provide a high-level specification for the goal of the task; then, the agent automatically synthesize a suitable program that is used to guide the policy” (Line 34). In particular, the method is not really doing program synthesis but rather task planning—which is an area that has been highly studied in the context of task and motion planning (TAMP). Like the proposed method, TAMP relies on having access to the DSL, goal specification, and transition operators. Yet, TAMP isn’t even mentioned in the paper at all. Perhaps the authors aren’t aware of this area of research, in which case, here is a recent review of such methods [1]. Moreover, while TAMP is not my area of expertise, from a quick literature search, I found a few papers that propose to deal with partial observability in TAMP [2, 3]. I think that TAMP at least deserves a mention in the related work section, and I think that the paper should tone down its claims about the program synthesis in and of itself being a novel contribution.\n\n**Minor comments:**\n\n* Typically when comparing learning curves of RL agents, the x-axis should report the number of environment transitions, not the number of episodes.\n* What does the *1000 mean in Figure 3? Is that indicating that the x-axis actually goes from 0 to 200k or 400k episodes?\n* “We leverage program synthesis [27] with the world models approach [9] to address these issues” → this statement isn’t really accurate, your generative model of states given observations isn’t really what world models does. I would recommend being more precise and just saying you train a generative model over states given observations.\n* The approach of sampling a realization of an MDP and planning optimally with respect to it—i.e. essentially the Thompson sampling approach—is approximately Bayes optimal in some settings, e.g. see [4]. Your approach is quite similar and it might be worth discussing this.\n* Figure 7 is very hard for me to interpret. I would suggest not having two scales on the same plot but instead plot the variance as error bars around the mean.\n* “Significantly” is used a number of times throughout the paper to indicate a substantial effect. However, “significant” has a precise statistical meaning, which is that we can be confident one value is higher than another. Since you perform no statistical tests in the paper, I would recommend avoiding the use of the term “significant” and stick to more general terms like “much higher/lower” or “substantially”.\n\n[1] Garrett, C. R., Chitnis, R., Holladay, R., Kim, B., Silver, T., Kaelbling, L. P., & Lozano-Pérez, T. (2021). Integrated task and motion planning. Annual review of control, robotics, and autonomous systems, 4, 265-293.\n[2] Phiquepal, C., & Toussaint, M. (2019, May). Combined task and motion planning under partial observability: An optimization-based approach. In 2019 International Conference on Robotics and Automation (ICRA) (pp. 9000-9006). IEEE.\n[3] Kaelbling, L. P., & Lozano-Pérez, T. (2013). Integrated task and motion planning in belief space. The International Journal of Robotics Research, 32(9-10), 1194-1227.\n[4] Guez, Silver, & Dayan (2013) “Scalable and Efficient Bayes-Adaptive Reinforcement Learning Based on Monte-Carlo Tree Search”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have discussed a number of limitations above, such as the assumption of full observability during training. There are a few other less important limitations as well. For example, environments must be static (i.e. once something is observed, it is assumed to not change unless it is within the agent’s field of view), and actions are deterministic. The proposed method would not work well if either of these assumptions were violated. I don’t necessarily expect the paper to address this, because it can’t be expected to solve all problems at once, but these limitations should be more explicitly called out.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "VrxQPx0E5X5", "reviewer": "Reviewer_aK3Q", "summary": "This paper aims to address the problem of solving long-horizon tasks in a partially observable environment by introducing a program-guided reinforcement learning framework. Specifically, given a task specification, this paper proposes to first synthesize a high-level instruction (i.e. a program) that consists of a sequence of subgoals and then execute the instruction to fulfill the task. To this end, the paper proposes a framework that comprises three components: (1) a generative model that can hallucinate the unobserved portions of the environment, (2) a program synthesizer that can produce a program that would fulfill the task specification, and (3) a program executor that can execute the program. The experiments show that the proposed framework outperforms the baselines including an end-to-end learning model and world models in terms of sample efficiency, obtained rewards, and the number of steps to finish a task. I believe this work studies a promising research direction (i.e. program-guided RL) and proposes an interesting framework to address the task. I would like to see this paper included in the conference while also hope the authors address my questions, including providing more comprehensive analyses are required to justify some design choices and adding missing relevant works.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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 and contributions\n**Motivation**\n- The motivation for solving a long-horizon task in a partially observable environment by first synthesizing a high-level plan is convincing.\n- The idea of utilizing programs as a representation to describe high-level plans that need to be executed to fulfill a given task specification is intuitive. This paper presents an effective way to implement this idea.\n- The limitations of prior works are explicitly mentioned, which strengthens the motivation of this work: (1) most of symbolic planning works cannot deal with continuous state and action spaces or partially observable environments, and (2) deep RL methods struggle at learning long-horizon tasks.\n\n**Technical contributions**\n- Hallucinating observable parts of the environment by predicting abstract state variables instead of concrete states seems effective.\n- Formulating the problem of fulfilling a given task specification as a MaxSAT problem and utilizing a MaxSAT solver to synthesize the plan is convincing.\n\n**Clarity**\n- The overall writing is very clear. The organization is easy to follow. The authors utilize figures well to illustrate the ideas.\n- Motivating Example Section not only provides a clear description of the family of problems considered in this paper but also presents the intuitions of the proposed framework. This writing flow makes the paper easier to read.\n\n**Related work**\nThe authors give a clear description of the related prior works from both the perspectives of reinforcement learning and planning.\n\n**Ablation study**\nAblation studies are helpful for understanding some design choices and the effectiveness of submodules. \n- Table 6 verifies the advantage of using a learned hallucinator.\n- Figure 7 justifies the proposed CVAE which allows for sampling multiple possible outcomes, while the margins are small.\n\n**Experimental results**\n- The experimental results demonstrate that the proposed framework outperforms a DRL baseline and a world model baseline and performs similarly to an oracle method (program guided agent) which utilizes a given ground truth program.\n- The authors, instead of evaluating on a single domain like most of the related works, evaluated the proposed framework and the baselines in two domains (I consider the 2D-craft environment and Ant-craft environment the same), making the results more convincing. \n\n**Reproducibility**\nThe code is provided, which is helpful for understanding the details of the proposed framework.\n\n## Paper weaknesses & questions\n\n**The performance breakdown**\nOnly the overall performance of the proposed framework is shown in the paper. It is not clear how well each module (i.e. the hallucinator and the executor) performs. It would be insightful to break down the overall performance.\n- For the hallucinator, I would like to see how accurate (in %) it can predict the unobserved parts of the environments so that I would know better how much error comes from the prediction. With this measurement, it would be easier to justify the design choice of the hallucinator (see below).\n- For the executor, I would like to see if the option policy can always complete a given component so that the failure can be attributed to either the predictions of the hallucinator or the execution.\n\n**Design choices of the hallucinator**\nOnly the comparisons of the proposed hallucinator, an optimistic hallucinator, and a random hallucinator are provided in Table 6. This only justifies the necessity of learning the hallucinator. However, it is not clear if training a CVAE for this task would yield the best results. I would like to see the performance of the following:\n- A deterministic baseline: instead of predicting a distribution allowing sampling, it would make sense to compare against a naive auto-encoder model that produces deterministic predictions so that we can verify the intuition of using CAVE to handle multiple possible outcomes.\n- VQ-VAE: I am wondering if using a conditional VQ-VAE would yield better results especially given the state features are discrete which aligns well with VQ-VAE discrete latent codes.\nI understand the tight timeline of the rebuttal so I am not demanding the abovementioned results. I simply believe including it would make the paper stronger and more convincing.\n\n**Predict concrete states**\nWhile it is intuitive to predict abstract feature states in this case, it would be informative to justify this choice (i.e. train a hallucinator that predicts raw states).\n\n**Design choices of the executor**\nThe authors proposed to use modular networks for the executor. I wonder if it actually yields better results compared to a simple multitask policy trained to solve all options. Again, I am not asking the results for the rebuttal.\n\n*Executor training*\nWhy not training the executor by simply sampling a subgoal from all the possible subgoals instead of training it to solve the entire episode, especially given that the reward signal is given whenever a subgoal is completed? \n\n**Missing related work: program synthesis**\nThe related work covers two lines of works: reinforcement learning and planning. However, I feel an important line of prior works is missing: program synthesis. Program synthesis methods aim to automatically synthesize programs from high-level task specifications. The program synthesis problems considered in this work can be cast as solving MaxSAT problems with a solver. Yet, this is not always the case and this is also when program synthesis works play a role - to search a program or learn to synthesize a program. Therefore, I believe it would be important to discuss this line of work. Some example papers are as follows:\n- RobustFill: Neural Program Learning under Noisy I/O\n- Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis\n- Synthetic Datasets for Neural Program Synthesis\n- Learning to Describe Scenes with Programs\n- Neural Program Synthesis from Diverse Demonstration Videos\n- Learning to Infer and Execute 3D Shape Programs\n- Improving Neural Program Synthesis with Inferred Execution Traces\n- Execution-Guided Neural Program Synthesis\n\n**MaxSAT assumption**\nThis paper assumes the program synthesis problem can be cast as a MaxSAT problem, which is not always the case. I would like to know what authors think about how the proposed framework can be modified to solve problems that do not fulfill this assumption. \n\n**Ant-craft**\nSince the low-level controller of the ant is pre-trained. I am not sure what the difference between the Minecraft environment and the ant craft environment. But, maybe it is helpful for the readers who do not understand the intuition (i.e. decouple the symbolic part and the neural network policies) which allows the proposed framework to deal with continuous state and action space\n\n**Code**\nWhen I tried to reproduce the results, there are some missing dependencies that are not mentioned in the README, including pyyaml, matplotlib, tqdm. It would be easier to provide a requirement text file to include those.\n\n**Minor**\nFigure 6: should be Table 6\n\n## Other metrics\n\n### Relevance and significance\n- Solid contribution to a relevant problem\n\n### Novelty\n- One idea that surprised me by its originality, solid contributions otherwise\n\n### Technical quality\n- Technically adequate for its area, solid results\n\n### Experimental evaluation\n- Sufficient evaluation w.r.t. most criteria\n\n### Clarity\n- Very clear, only minor flaws", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Described in the main review section.", "review_text": "", "extra_scores": {"ethical_concerns": "I currently do not recognize any potential negative impact or ethical concerns for this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "11"}, "extra_text": {}}, {"review_id": "O8gdIRWPHWT", "reviewer": "Reviewer_EBwR", "summary": "Authors address a class of RL challenges where the main task implicitly consists of a sequence of subtasks, and the main goal of an agent can be split into two parts: to decompose the tasks into a sequence of subtasks (planner module) and to perform each subtask individually. They consider a scenario where the current state (map of the world) is not fully observable. The key idea of this paper is to use a model of the map to supply a planner module with a hypothetical map of the world so that it can devise an on-average well-working plan. The authors applied their method to several environments including a 2D Minecraft-inspired environment and show that it is able to outperform prior methods. Their method eliminates the need for the human user to produce a demo solution of the ultimate goal but still requires the user to specify the logical predicates of the ultimate goal and goals of micro-tasks that serve as milestones in planning. These predicates are based on some DSL also specified by the user.\n\nAlthough this paper has some weaknesses (see below), it makes a step towards a promising direction, so I slightly lean towards accepting.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Overview.\n_____\n\nThe proposed three-piece approach helps RL agents in goal-oriented partially observed environments to complete complex multi-step tasks. Unlike other methods, which require that solution strategies are supplied, the approach needs only the specifications of sub-goals and the ultimate goal from the user.\n\nA quite peculiarly named `hallucinator` piece is a conditional generative world model (C-VAE) trained on random exploration data, to predict realizations of unobserved sectors of the world map (in terms of their features) and hallucinate objects located therein, given the observations made so far.\n\nThe program `synthesizer` piece samples possible worlds conditional on the current observation history and applies a MaxSAT solver to compose a shortest program, i.e. a series of \"components\" (milestone micro-tasks) that guides the agent to the ultimate goal.\n\nThe final piece is the \"executor\", which traces the synthesized program by executing RL options associated with each \"component\" micro-task. The hallucinatory program synthesis step is repeated, should the agent fail to complete the goal or halt on running out of the allotted time, this time, however, leveraging newly collected observations.\n\nEach option, i.e. a policy with a particular termination criterion, is pre-trained in the environment to complete the user-specified micro-task. For speedup, the rollouts during option pre-training are collected by leveraging the \"ground truth program synthesized based on the fully observed [version of the] environment\" (L217) for the ultimate goal.\n\nStrong points.\n_____\n\nLike its predecessors Sun et al. (2020) and Andreas et al. (2017), the method produces a nice inductive hierarchical structure of goals and subgoals. A policy option is learnt for each specified zero-tier micro-task in the environment, and then the program synthesizer creates a script for a specified higher-tier task by composing lower-tier tasks and packaging this into an associated composite option.\n\nThis paper's method itself completes an important `micro-task` on the path to program-guided exploration, preferably synthesized on-the-fly, which would be capable of generating milestones from prior knowledge and micro-tasks, or a curiosity-based point of Interest detection method, that produces such micro-tasks for which the options are also learnt on-the-go.\n\nWeak points / criticism.\n______\n\n\n1)\tExperiments are set on some tasks composed especially the particular paper, and this is not obvious what should be SOTA for them. Also, five replications of each experiment seems to be on the side of being too few.\n\n2)\tExploration: the proposed method of exploration is exploitative (goal-oriented) and do not have any curiosity features. Such approach seems to be limited to the environments with finitely explorable map. It is unlikely that their method would be successful for such challenges like obstacle tower challenge (Unity Technologies).\n\n3)\tSome important details of the paper are not clear:\n- What maps S (should be) used to sample training data for a VAE hallucinator? Can we make sure that the (information from the) maps where the agents are tested do not leak to that training data for VAE?\n- A connected question is: what does mean “the actual distribution P(s\\mid o)”, how can it be defined and how can we sample it?\n- What is “a randomly generated map” (L99). What is a generative model?\n\n4) Although the proposed program synthesis approach is interesting, I am concerned that the variability and feature simplicity of the 2d-craft environment have played a significant role in the success of the presented experimental results. Indeed, the pre-trained micro-task options could memoize the peculiarities of this procedurally generated environment.\n\n5) Another limitation of the particular instance of the presented method is the need for the full state to be accessible (or relevant features thereof). There are environments, e.g. the [NetHack](https://arxiv.org/abs/2006.13760), which have feature-rich observation space and very long branching exploration paths, and the full state of the “world” is unavailable, and has to be discovered. In this situation the hallucinator, which is trained on random exploration, will be extremely unlikely to ever stumble upon the ultimate goal, let alone be able to reconstruct the entire state. It will face the same challenge with feature-rich states, so there is a need to devise a method to limit the scope of the generative model to only the likely relevant locations.\n\n\nCorrections, typos and RFCs\n_______\n\n- L291: It is unclear what is meant by “random hallucinator. Is it untrained, is not conditioned on the observations at all, or not updated with new exploration information?\n- L290: It is also unclear what is meant by a synthesizer that makes “the best-case assumptions on about the unobserved parts” on?\n- L107: “final state s_{-}” should be “final state s_{+}”?\n- L 153: the conjunction sign should be rather conjunction?\n- L35: “the agent automatically [sythesizeS]”\n- according to NeurIPS style the captions should precede the tables.\n- figure 6 should be table 2.\n- increasing DPI on the included figures would enhance their accessibility\n\n\n__________\nAfter rebuttal\n\nSumming up, in order to automatically find a program, which achieves the main goal of the agent, the MPPS method requires that we\n\n* know the predicate specifications of micro-tasks (options) and the main goal;\n* have well pre-trained policies that can explore well and complete micro-goals (options);\n* have a generative model that reconstructs abstract state descriptions from partially observed data\n\nThe main contribution is an approach to automatically synthesize guiding programs for reinforcement learning policies under partial observability.\n\nHaving read all discussion, I slightly lower my score (6 -> 5). On one hand, the idea is promising, the direction seems important, and the authors addressed many important questions. On the other hand, I agree with kENU that many important details regarding training, ablations, and baselines are needed in the paper. Further, as detailed below, I think the paper needs additional experiments. The proposal about “interweaved hallucinator training with executor learning” should be discussed in the paper.\n\nNow, although I am convinced that pre-training the component options under full observability is a way too privileged in the partially observed settings, I believe that such privileged setting still can give valuable proof-of-concept results for the core method: program synthesis with a help of a generative model for states. The availability of well-trained options can be considered as an assumption for the applicability of the method, and I believe that this assumption is reasonable for future RL systems, which will share options among tasks and environments.\n\nHowever, I have additional concerns about baselines. Currently, the End-to-end baseline, the one with many micro-actor DNNs, is severely handicapped: (1) it does not have access to a hallucinator (mentioned in the response to Wt3P, `experiments/craft_nn.yaml#L7`, and `models/simple_nn.py#L59-66`), and (2) it is not recurrent (judging from a quick regex over the supplied codebase), contrary to the provided response to kENU. Point (2) is rather concerning since it is unclear how the non-markovian dependence on the full history is handled.\n\nAt the same time, the World Model baseline (recurrent) does not have access to pre-trained options, which makes the comparison unfair. Thus, the baselines do not allow us to separate the effect of good micro-goal options from the synergy between the hallucinator and the synthesizer.\n\nI want to reiterate: in the codebase the ”hallucinator” is a CVAE with a Bernoulli decoder (`models/cvae.py#L122-124` and `train_cvae.py#L198`) trained on random rollouts (`train_cvae.py#L418-420`) to reconstruct full one-hot encoded (`train_cvae.py#L395-411`) abstract states (`environment/box.py#L444-470` and `environment/craft.py#L953-990`) from partial observations overlain on an empty binary grid map (`environment/box.py#L542-615` and `environment/craft.py#L953-990`).\n\nIn light of the claimed benefits of synthesized programs, I think a good baseline/ablation experiment would be to replace the synthesizer with a recurrent neural policy on pre-trained options, which __also has access__ to the hallucinator or an equivalent world model (also pre-trained on a fully observable environment). To fairly judge the benefit of program synthesis here it may be necessary to compare the number of requests each approach makes to the world model.\n\nAs for the claims of reduced user supervision, I suspect that identifying micro-goals and specifying them as logical predicates still demands that the user thoroughly analyzes the environment (L32). So the toning down of the contributions of the paper seems appropriate. Besides, micro-goals' logical predicates as they are described in the paper do not seem to be very high-level (L35): one has to tinker with the before- and after- states, enumerate positions, and zones in the grid, and compose conjunctive forms (L496). Despite this, I am inclined to agree that such specifications are more basic than a program description of an optimal solution as in Sun et al. (2017).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential negative societal impact ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "D61dVEa6PU", "reviewer": "Reviewer_Wt3P", "summary": "The algorithm is set in a problem where the grid for exploration is not fully observable. The authors introduce a new approach called model predictive program synthesis (MPPS) that involves a hallucinator, a synthesizer and an executor. The hallucinator predicts the state features with CVAE, the synthesizer provides programs through optimization of a MAXSAT problem. And the executor executes the programs. \n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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 shown to outperforms the other comparison methods. However, I think it’s missing some discussions and comparisons that help put the problem and method in the bigger context. \n\nI’d like to see a bit more discussion on why this particular model is able to outperforms the other methods. Is it because of the SAT solver? or the hallucinator? Or because it didn’t specify goals? A more in-depth discussion would add more weight and clarity to the paper.\n\nHow a hallucinator is trained is not very clear to me. A diagram or an example input/output would be nice. This would facilitate understanding of the method. \n\nExplanation of the end-to-end method is not clear. Does it also have a hallucinator? \n\nIt seems like some of the maze or corridor environments in deep rl also have the same problem of not having full observability. There are already solutions exist for those types of problems without program guidance. Can you explain why program synthesis is necessary for this type of problems? Or at least are there any quantitative comparisons that show improvements or such? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don’t think there are any ethical concerns regarding this paper. And some limitations are also addressed. For specific problems, please refer to the last section. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the paper tackles an interesting research problem, ie long-term planning in POMDPs. However, multiple issues were raised and remain after the discussion, among these are clarity of exposition and mostly importantly novelty of contribution. Concerning the latter, introduction of a generative model into the architecture for modeling belief states in partially observed environments has been addressed more thoroughly in the literature before (eg see [1] and references therein) mostly without the need for privileged information during training. The problem of planning in POMDPs has an even richer history, eg the method proposed in [2] would be directly applicable to the setting considered here. However the method is not referenced nor compared to in experimental results. The paper is therefore not accepted in its current form.

[1] Temporal Difference Auto-Encoder. Gregor at al. 
[2] Monte-Carlo Planning in Large POMDPs. Silver, Veness.
Decision: Accept (Spotlight)