Learning to Synthesize Programs as Interpretable and Generalizable Policies
Authors: Dweep Trivedi
Jesse Zhang
Shao-Hua Sun
Joseph J Lim
Venue: NeurIPS 2021 Poster (2021)
Keywords: Program Synthesis
Neural Program Synthesis
Programmatic Reinforcement Learning
Reinforcement Learning
Deep Reinforcement Learning

Abstract: Recently, deep reinforcement learning (DRL) methods have achieved impressive performance on tasks in a variety of domains. However, neural network policies produced with DRL methods are not human-interpretable and often have difficulty generalizing to novel scenarios. To address these issues, prior works explore learning programmatic policies that are more interpretable and structured for generalization. Yet, these works either employ limited policy representations (e.g. decision trees, state machines, or predefined program templates) or require stronger supervision (e.g. input/output state pairs or expert demonstrations). We present a framework that instead learns to synthesize a program, which details the procedure to solve a task in a flexible and expressive manner, solely from reward signals. To alleviate the difficulty of learning to compose programs to induce the desired agent behavior from scratch, we propose to first learn a program embedding space that continuously parameterizes diverse behaviors in an unsupervised manner and then search over the learned program embedding space to yield a program that maximizes the return for a given task. Experimental results demonstrate that the proposed framework not only learns to reliably synthesize task-solving programs but also outperforms DRL and program synthesis baselines while producing interpretable and more generalizable policies. We also justify the necessity of the proposed two-stage learning scheme as well as analyze various methods for learning the program embedding. Website at https://clvrai.com/leaps.

Learning to Synthesize Programs as Interpretable and Generalizable Policies
Dweep Trivedi*
Jesse Zhang*! Shao-Hua Sun' Universstty of Southern California Idtrivedi, jessez, shaohuas, limjj @uscc edu
Joseph J. Lim
Abstract
Recently, deep reinforcement learning (DRL) methods have achieved impressive performance on tasks in a variety of domains. However, neural network policies produced with DRL methods are not human-interpretable and often have diffi- culty generalizing to novel scenarios. To address these issues, prior works explore learning programmatic policies that are more interpretable and structured for gen- eralization. Yet, these works either employ limited policy representations (e.g. decision trees, state machines, or predefined program templates) or require stronger supervision (e.g. input/output state pairs expert demonstrations). We present framework that instead learns to synthesize a program, which details the procedure solve task in flexible and expressive manner, solely from reward signals. To alleviate the difficulty of learning to compose programs to induce the desired agent behavior from scratch, we propose to first learn program embedding space that continuously parameterizes diverse behaviors in an unsupervised manner and then search over the learned program embedding space yield a program that maximizes the return for a given task. Experimental results demonstrate that the proposed framework not only learns to reliably synthesize aask-solving programs but also outperforms DRL and program synthesis baselines while producing in- terpretable and more generalizable policies. We also justify the necessity of the proposed two-stage learning scheme well as analyze various methods for learning the program embedding. Website at https: //lvrii. com/ leaps.
Introduction
Recently, deep reinforcement learning (DRL) methods have demonstrated encouraging performance on a variety of domains such as outperforming humans in complex games [1-4] or controlling robots [5-11]. Despite the recent progress in the field, acquiring complex skills through trial and error still remains challenging and these neural network policies often have difficulty generalizing to novel scenarios. Moreover, such policies are interpretable humans and therefore are difficult to debug when these challenges arise.
To address these issues, growing body of work aims to learn programmatic policies that structured more interpretable and generalizable representations such as decision trees [12], state- machines [13], and programs described by domain-specifie programming languages [14, 15]. Yet, the programmatic representations employed in these works are often limited expressiveness due constraints the policy spaces. For example, decision tree policies incapable of naively generating repetitive behaviors, state machine policies used in [13] are computationally complex to
"Contributed equally.
Work partially done visiting scholar at USC.
I AI Advisor at NAVER Al Lab.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

scale to policies representing diverse behaviors, and the programs of [14, 15] are constrained to set of predefined program templates. On the other hand, program synthesis works that aim represent desired behaviors using flexible domain-spectie specifie programs often require extra supervision such as input/output pairs [16-20] or expert demonstrations [21, 22], which can be difficult to obtain.
In this paper, we present a framework to instead symthesize human-readable programs in an expressive representation, solely from rewards, to solve tasks described by Markov Decision Processes (MDPs). Specifically, we represent a policy using a program composed of control flows (e.g. if/else and loops) and an agent's perceptions and actions. Our programs can flexibly compose behaviors through prrception-conditioned conditioned loops and nested conditional statements. However, composing individual program tokens (e.g. if, while, move () ) in a rial-and-errov fashion to synthesize programs that can solve given MDPs can be extremely difficult and inefficient.
To address this problem, we propose to first learn latent program embedding space where nearby latent programs correspond to similar behaviors and allows for smooth interpolation, together with a program decoder that can decode latent program a program consisting of a sequence of program tokens. Then, when a task is given, this embedding space allows us to iteratively search over candidate latent programs to find a program that induces desired behavior to maximize the reward. Specifically, this embedding space is learned through reconstruction of randomly generated programs and the behaviors they induce in the environment in an unsupervised manner. Once learned, the embedding space can be reused to solve different tasks without retraining.
To evaluate the proposed framework, we consider the Karel domain [23], featuring agent navigating through a gridworld and interacting with objects to solve tasks such as stacking and navigation. The experimental results demonstrate that the proposed framework not only learns reliably synthesize task-solving programs but also outperforms program synthesis and deep RL baselines. In addition, we justify the necessity of the proposed two-stage learning scheme as well as conduct an extensive analysis comparing various approaches for learning the latent program embedding spaces. Finally, we perform experiments which highlight that the programs produced by our proposed framework can both generalize to larger state spaces and unseen state configurations as well as be interpreted and edited by humans to improve their task performance.
2 Related Work
Neural program induction and synthesis. Program induction methods [20, 24-36] aim to implicitly induce the underlying programs to mimic the behaviors demonstrated given task specifications such as input/output pairs or expert demonstrations. On the other hand, program synthesis methods [16- 19, 21, 37-58] explicitly synthesize the underlying programs and exccute the programs to perform the tasks from task specifications such input/output pairs, demonstrations, language instructions. In contrast, we aim to learn to synthesize programs solely from reward described by an MDP without other task specifications. Similarly to us. two-stage synthesis method is proposed in [46]. Yet, the task is to match truth tables for given test programs rather than solve MDPs. Their first stage requires the entire ground-truth table for each program synthesized during training, which is infeasible to apply to our problem setup (i.e. synthesizing imperative programs for solving MDPs).
Learning programmatic policies. Prior works have also addressed the problem of learning program- matic policies [59-61]. Bastani et al. [12] learns a decision tree as a programmatic policy for pong and cartpole environments by imitating an oracle neural policy. However, decision trees are incapable of representing repeating behaviors on their own. Silver et al. [49] addresses this by including a loop-style token for their decision tree policy, though it is still not as expressive synthesized loops. Inala et al. [13] learns programmatic policies as finite state machines by imitating a teacher policy, although finite state machine complexity can scale quadratically with the number of states, making them difficult to scale to more complex behaviors.
Another line of work instead synthesizes programs structured in Domain Specific Languages (DSLs), allowing humans to design tokens (e.g. conditions and operations) and control flows (e.g- while loops, if statements, reusable functions) to induce desired behaviors and can produce human interpretable programs. Verma et al. [14, 15] distill neural network policies into programmatic policies. Yet, the initial programs are constrained to set of predefined program templates. This significantly limits the scope of synthesizable programs and requires designing such templates for each task. In contrast,
2

---

our method can synthesize diverse programs, without templates, which can flexibly represent the complex behaviors required solve various tasks.
Problem Formulation
We are interested in learning to synthesize program structured in a given DSL that can be exccuted to solve given task described by an MDP, purely from reward. In this section, we formally define our defini- tion of a program and DSL, tasks described by MDPs, and the problem formulation.
Program
mí m)
Repetition n = Number of repetitions
Perception Domain dependent perceptions
Condition b = penception h not perception h
Action Domain dependent actions
Statement = while cf b c) w[ w) #11 |
Program and Domain Specific Language. The pro- grams, or programmatic policies, considered in this work are defined based on a DSL as shown in Fig- ure 1. The DSL consists of control flows and an agent's perceptions and actions. A perception indi- cates circumstances in the environment (e.g. front agent, while an action defines certain behavior that can be performed by agent (e.g. move (), turnlefs ft () ). Control flow includes i e/eels se statements, loops, and boolean/logical operators to compose more sophisticated conditions. A policy considered in this work is described by a program which is executed to produce a sequence of actions given perceptions from the environment.
repent Ren 4 iF be) {(i))
itelse cl be) 81 1) else #2 e)
Figure 1: The domain-specific language (DSL)
for constructing programs.
()) that can be perceived by an
MDP. We consider finite-horizon discounted MDPs with initial state distribution μu(s)) and discount factor y. For a fixed sequence {(00, ( ao),..., (st, a of states and actions obtained from a rollout of a given policy, the performance of the policy is evaluated based on a discounted return Ei 7'T where T' is the horizon of the episode and Tr Rst,, az) the reward function.
Objective. Our objective is maxp Eg-EXEC(e)) so ET >'re]. where EXEC returns the actions induced by executing program policy in the environment, Note that one can view this objective as a special case of the standard RL objective, where the policy is represented as a program which follows the grammar of the DSL and the policy rollout is obtained by executing the program.
4 Approach
Our goal to develop framework that can synthesize a program (i.e. a programmatic policy) structured in given DSL that can be executed to solve task of interest. This requires the ability to synthesize a program that is not only valid for execution (e-g- grammatically correct) but also describes desired behaviors for solving the task from only the reward. Yet, learning synthesize such a program from scratch for every new task can be difficult and inefficient.
To this end, we propose our Learning Embeddings for IAtent Program Synthesis framework, dubbed LEAPS, as illustrated in Figure LEAPS first learns latent program embedding space that continuously parameterizes diverse behaviors and program decoder that decodes a latent program to program consisting of a sequence of program tokens. Then, when a task given, we iteratively search over this embedding space and decode each candidate latent program using the decoder to find a program that maximizes the reward. This two-stage learning scheme not only enables learning to synthesize programs to acquire desired behaviors described by MDPs solely from reward, but also allows reusing the learned embedding space to solve different tasks without retraining.
In the rest of this section, we describe how we construct the model and our learning objectives for the latent program embedding space in Section 4.1. Then, we present how program that describes desired behaviors for a given task can be found through search algorithm in Section 4.2.
4.1 Learning a Program Embedding Space
To learn latent program embedding space, we propose to train a variational autoencoder (VAE) [62] that consists of a program encoder 46 which encodes a program P to latent program and program decoder pe which reconstructs the program from the latent. Specifically, the VAE is trained through
3

---

Cross Entropy Melhod
CP
Latart Program
Lutert Prograni
Program
Program
Reconattuciee Program
No
Po
Sarrpl
p0
Envesement
Enveerment
g
Ena eneemnnt
01,
CL
L
(a) Learning Program Embedding Stage
Latent Program Search Stage
Figure 2: (a) Learning program embedding stage: we propose to learn a program embedding space by training program encoder that encodes program latent program program decoder po that decodes the latent program back reconstructed program P. and policy и that conditions the latent program z and acts neural program executor to produce execution trace of the latent program 2. The model optimizes a combination a program reconstruction loss L" a program behavior reconstruction loss L and latent hehavior reconstruction loss L 01 02;--; denotes actions produced by either the policy и or program execution. (b) Latent program search stage:
the Cross Entropy Method to iteratively search for the best candidatc latent programs that be decoded and exccuted maximize the reward solve given tasks.
reconstruction of randomly generated programs and the behaviors they induce in the environment in an unsupervised manner. Architectural details listed in Section L.6.
Since we aim to iteratively search over the learned embedding space to achieve certain behaviors when task given, we want this embedding space allow for smooth behavior interpolation (i.e. programs that exhibit similar behaviors are encoded closer in the embedding space). To this end, we propose train the model by optimizing the following three objectives.
4.1.1 Program Reconstruction
To learn a program embedding space, we train program encoder and program decoder po to reconstruct programs composed of sequences of program tokens. Given input program p consisting of a sequence of program tokens, the encoder processes the input program one token at time and produces latent program embedding Then, the decoder outputs program tokens one by one from the latent program embedding z to synthesize a reconstructed program P. Both the encoder and the decoder recurrent neural networks and trained optimize the 3-VAE [63] loss:
C (p) -E (log (
4.1.2 Program Behavior Reconstruction
While the loss in Eq. enforces that the model encodes syntactically similar programs close to each other in the embedding space, we also want to encourage programs with the same semantics have similar program embeddings. An example that demonstrates the importance of this is the program aliasing issue, where different programs have identical program semantics (e.g. repeat (2) move () and move () move ()). Thus, we introduce objective that compares the execution traces of the input program and the reconstructed program. Since the program execution process is not differentiable, we optimize the model via REINFORCE [64]]
(P) -Es-gs(elo) RRma (po (po(p)z).
(2)

---

where Rma p). the reward for matching the imput program's 's behavior, is defined as
N
Rmar (p. p) - EE Σ
(EXE)) = EXEC, Vi = 1, ...
(3)
1=1
stays after the lirst é where EXEC, != EXEC,(p)
where N is the maximum of the lengths of the execution traces of both programs, and EXEC; represents the action taken by program p at time i. Thus this objective encourages the model to embed behaviorally similar yet possibly syntactically different programs to similar latent programs.
4.1.3 Latent Behavior Reconstruction
To further encourage learning a program embedding space that allows for smooth behavior inter- polation, we devise another source of supervision by learning program embedding--oonditonee policy. Denoted ( this recurrent policy takes the program embedding produced by the program encoder and learns to predict corresponding agent actions. One view this policy neural program executor that allows gradient propagation through the policy and the program encoder by optimizing the cross entropy between the actions obtained by executing the input program p and the actions predicted by the policy:
M IAI
=) L ((XEC, == log s()],
= -E -E
(4)
where M denotes the length of the execution of Optimizing this objective directly encourages the program embeddings, through supervised learning instead of RL as in L to be useful for action reconstruction, thus further ensuring that similar behaviors are encoded together and allowing for smooth interpolation. Note that this policy is only used for improving learning the program embedding space not for solving the tasks of interest in the later stage.
In summary. we propose optimize three sources of supervision learn the program embedding space that allows for smooth interpolation and can be used to search for desired agent behaviors: (I)
C (Eq. 1), the 3-VAE objective for program reconstruction, (2) C (Eq. 2), an RL environment- state matching loss for the reconstructed program, and (3) - (Eq. 4), supervised learning loss to encourage predicting the ground truth agent action sequences. Thus our combined objective is:
min Yr CI (p) + X2 (p) + (p.
(5)
0,0.5
where d1 λ2, and 0g hyperparameters controlling the importance of each loss. Optimizing the combination of these losses encourages the program embedding to be both semantically and syntactically informative. More training details can be found in Section L.6.
4.2 Latent Program Search: Synthesizing a Task-Solving Program
Once the program embedding space is learned, our goal becomes searching for latent program that maximizes the reward described by given task MDP. To this end, we adapt the Cross Entropy Method (CEM) [65], gradient-fre free continuous search algorithm, to iteratively search over the program embedding space. Specifically, we (1) sample distribution of latent programs, (2) decode the sampled latent programs into programs using the learned program decoder po, (3) execute the programs in the task environment and obtain the corresponding rewards, and (4) update the CEM sampling distribution based on the rewards. This process repeated until either convergence or the maximum number of sampling steps has been reached.
5 Experiments
We first introduce the environment and the tasks in Section 5.1 and describe the experimental setup in Section 5.2. Then, we justify the design of LEAPS by conducting extensive ablation studies in Section 5.3. We describe the baselines used for comparison in Section 5.4, followed by the experimental results presented in Section 5.5. In Section 5.6, we conduct experiments to evaluate the ability of our method to generalize to larger state space without further learning. Finally, investigate how LEAPS' interpretability can be leveraged by conducting experiments that allow humans debug and improve the programs synthesized by LEAPS Section 5.7
5

---

(d)
The Karel problem set: the domain features an agent navigating through a gridworld with walls and interacting with markers, allowing for designing tasks that demand certain behaviors. The tasks are further described Section K with visualizations in Figure 15.
Figure 3:
5.1 Karel domain
To evaluate the proposed framework, we consider the Karel domain [23], as featured in [17, 19, 21], which features agent navigating through gridworld with walls and interacting with markers. The agent has 5 actions for moving and interacting with marker and perceptions for detecting obstacles and markers. The tasks of interest shown in Figure 3. Note that most tasks have randomly sampled agent, wall, marker, and/or goal configurations. When either training or evaluating, we randomly sample initial configurations upon every episode reset. More details can be found in Section K.
5.2 Programs
To produce programs for learning the program embedding space, we randomly generated a dataset of 50,000 unique programs. Note that the programs are generated independently of any Karel tasks; each program is created only by sampling tokens from the DSL, similar to the procedures used in [16-19, 21, 22]. This dataset split into training with 35,000 programs validation set with 7, 7,500 programs, and a testing set with 7,500 programs. The validation set is used to select the learned program embedding space
for the program synthesis stage.
For each program, we sample random Karel states and execute the program on them from different starting states to obtain 10 environment rollouts to compute the program behavior reconstruction loss _ and the latent behavior reconstruction loss C when learning the program embedding space. We perform checks to ensure rollouts cover all exccution branches in the program that they representative of all aspects the program's 's behavior. The maximum length of the programs is 44 tokens and the average length is 17.9. We plot histogram of their lengths in Figure 14 (in Appendix). More dataset generation details can be found in Section
5.3 Ablation Study
We first ablate various components of our proposed framework in order to (1) justify the necessity of the proposed two-stage learning scheme and (2) identify the effects of the proposed objectives. We consider the following baselines and ablations of our method (illustrated Section I).
Naïve: program synthesis baseline that learns to directly synthesize program from scratch by recurrently predicting sequence of program tokens. This baseline investigates if an end-to-end learning method can solve the problem. More details can be found in Section L.4.
LEAPS-P P: the simplest ablation of LEAPS, in which the program embedding space is learned by only optimizing the program reconstruction loss CP (Eq. 1).
LEAPS-P+t ablation of LEAPS which optimizes both the program reconstruction loss LP (Eq. 1) and the program behavior reconstruction loss L (Eq. 2).
LEAPS-P+L: an ablation of LEARS which optimizes both the program reconstruction loss C
(Eq. 1) and the latent behavior reconstruction loss L (Eq. 4).
LEAPS LLEAPS-P+R+L): LEAPS with all the losses, optimizing our full objective in Eq. 5.
LEAPP--anne -eees-ran--- (annd((/65)) [8/64): similar to LEAPS, this ablation also optimizes the full objective (Eq. 5) for learning the program embedding space. Yet, when searching latent programs, instead of CEM, it simply randomly samples 8/64 candidate latent programs and chooses the best performing one. These baselines justify the effectiveness of using CEM for searching latent programs.

---

Table 1: Program behavior reconstruction rewards (standard deviations) across all methods.
WHILE
21F+IFELSE 1
WHILE+21F-1FELSE
Avg Reward
Naive
0.65 (0.33)
0.83 (0.07)
0.61 (0.33)
0.16 (0.06)
0.56
LEAPS-P
0.95 (0.13)
0.82 (0.08)
0.58 (0.35)
0.33 (0.17)
0.67
LEAPS-P+R
0.98 (0.09)
0.77 (0.05)
0.63 (0.25)
0.52 (0.27)
0.72
LEAPS-P+L
1.06 (0.00)
0.84 (0.10)
0.77 (0.23)
0.33 (0.13)
0.75
LEAPS-rand-8
0.62 (0.24)
0.49 (0.09)
0,36 (0.18)
0.28 (0.14)
0.44
LEAPS-rand-66
0.78 (0.22)
0.63 (0.09)
0.55 (0.20)
0.37 (0.09)
0.58
LEAPS
(0.08)
0.87 (0.13)
0.85 (0.30)
(0.23)
0.84
Program Behavior Reconstruction. To determine the effectiveness of the proposed two-stage learning scheme and the learning objectives, we measure how effective each ablation is at recon- structing the behaviors of input programs. We use programs from the test set (shown in Figure 9 in Appendix), and utilize the environment state matching reward Rmar (p: p) (Eq. 3), with a 0.1 bonus for synthesizing syntactically correct program. Thus the return ranges between [0, 1.1]. We report the mean cumulative return, over random seeds, of the final programs after convergence.
The results are reported in Table 1, Each test is named after its control flows (e.g. I has an if-else statement and a while loop). The naive program synthesis baseline fails on the complex WHILE+2IF+IIELS: program, as it rarely synthesizes conditional and loop statements, instead generating long sequences of action tokens that attempt to replicate the desired behavior of those statements (see synthesized programs in Figure 10). We believe that this is because it is incentivized to initially predict action tokens to gain more immediate reward, making it less likely to synthesize other tokens. LEAPS and its variations perform better and synthesize more complex programs, demonstrating the importance of the proposed two-stage learning scheme in biasing program search. We also note that LEAPS-P achieves the worst performance out of the CEM search LEAPS ablations, indicating that optimizing the program reconstruction loss L (the VAE loss) alone does not yield satisfactory results. Jointly optimizing L with either the program behavior reconstruction loss L or the latent behavior reconstruction loss C). improves the performance, and optimizing our full objective with all three achieves the best performance across all tasks, indicating the effectiveness of the proposed losses. Finally, LEAPS outperforms LEAPS-rande randd-/64, suggesting the necessity of adopting better search algorithms such CEM.
Program Embedding Space Smoothness. We investigate if the program and latent behavior reconstruction losses encourage learning behaviorially smooth embedding space. To quantify behavioral smoothness, measure how much change in the em- bedding space corresponds to a change in behavior by comparing execution traces. For all programs we compute the pairwise Fu- clidean distance between their embeddings in each model. We then calculate the environment state matching distance Rma between the decoded programs by executing them from the same initial state.
Table 2: Program embedding space smoothness. For each program, we exccute the ten nearest programs in learned embedding space of each model to calculate the mean state- matching reward Rms against the original program. We report Rmm averaged over all programs in each dataset.
LEAPS-P
LEAPS-P+R
LEAPS-P4L
LEAPS
TRAINING VALIDATION
0.22
0.22
0,31
0.31
0.22
0,21
0.27
0.27
TESTING
0.28
0.27
The results are reported Table LEAPS and LEAPS-P+L perform the best, suggesting that optimizing the latent behavior reconstruction objective L in Eq. 4, is essential for improving the smoothness of the latent space in terms of execution behavior. We further analyze and visualize the leamedd program embedding space in Section A and Figure 4 (in Appendix).
5.4 Baselines
We evaluate LEAPS against the following baselines (illustrated in Figure 13 in Appendix Section I).
DRL: a neural network policy trained on each task and taking raw states (Karel grids) as input.
DRL-abs: a recurrent neural network policy directly trained on each Karel task but taking abstract states as input (i.e. it sees the same perceptions as LEAPS, e.g. IsClear () -- rue)..
DRL-abs-t: DRL transfer learning baseline in which for each task, we train DRL-abs policies all other tasks, then fine-tune them on the current task. Thus it acquires a prior by learning to
7

---

Table 3: Mean return (standard deviation) of all methods across Karel tasks, evaluated over 5 random
seeds. DRL methods, program synthesis baselines, and LEAPS ablations are separately grouped.
STAIRCIIMBER
FOURCORNER
TOPÜFF
MAZE
CLEANHOUSE
HARVESTER
DRL
1.00 (0.00)
0.29 (0.05)
0.32 (0.07)
1.00 (0.00)
0.00 (0.00)
0.90 (0.10)
DRL-abs
0.13 (0.29)
0.36 (0.44)
0.63 (0.23)
1.00 (0.00)
0.01 (0.02)
0.32 (0.18)
DRL-abs-t
0.00 (0.00)
0.05 (0.10)
0.17 (0.11)
1.00 (0.00)
0.01 (0.02)
0.16 (0.18)
HRL
-0.51 (0.17)
0.01 (0.00)
0.17 (0.11)
0.62 (0.05)
0.01 (0.00)
0.00 (0.00)
HRI.-ass
-0.05 (0.07)
0.00 (0.00)
0.19 (0.12)
0.56 (0.03)
0.00 (0:00)
-0.03 (0.02)
Naive
0.40 (0.49)
0.13 (0.15)
0.26 (0.27)
0.76 (0.43)
0.07 (0.09)
0.21 (0.25)
VIPER
0.02 (0.02)
0.40 (0.42)
0.30 (0.06)
0.69 (0.05)
0.00 (0:00)
0.51 (0.07)
LEAPS-rand-8
(0.17)
0.10 (0.14)
0.28 (0.05)
0.40 (0.50)
0.00 (0.00)
0.07 (0.06)
LEAPS-rand-64
0.18 (0.40)
0.20 (0.11)
0.33 (0.07)
0.58 (0.41)
0.03 (0.06)
0.12 (0.05)
LEAPS
1.00 (0.00)
0.45 (0.40)
0.81 (0.07)
1.00 (0.00)
0.18 (0.14)
0.45 (0.28)
first solve other Karel tasks. Rewards are reported for the policies from the task that transferred with highest return. We only transfer DRL-abs policies some tasks have different state spaces.
HRL: a hierarchical RL baseline in which a VAË is first trained on action sequences from program execution traces used by LEAPS. Once trained, the decoder is utilized
low-level policy for learning a high-level policy to sample actions from. Similar to LEAPS, this baseline utilizes the dataset to produce a prior of the domain. It takes raw states (Karel grids) as input.
HRL-abs: the same method as HRL but taking abstract states (i.e. local perceptions) input.
VIPER [12]: A decision-tres programmatic policy which imitates the behavior of deep RL teacher policy via a modified DAgger algorithm [66]. This decision tree policy cannot synthe- size loops, allowing us to highlight the performance advantages of more expressive program representation that LEAPS is able to take advantage of.
All the baselines are trained with PPO [67] or SAC [68], including the VIPER teacher policy. More training details can be found in Section L.
5.5 Results
We present the results of the baselines and our method evaluated on the Karel task set based on the environment rewards in Table 3. The reward functions are sparse for all tasks, and are normalized such that the final cumulative return within [-1, 1] for tasks with penalties and [o, 1] for tasks without; reward functions for each task are detailed in Section K.
Overall Task Performance. Across all but one task, LEAPS yields the best performance. The LEAPS-rand baselines perform significantly worse than LEAPS on all Karel tasks, demonstrating the need for using a search algorithm like CEM during synthesis. The performance of VIPER is bounded by its RL teacher policy, and therefore is outperformed by the DRL baselines on most of the tasks. Meanwhile, DRL-abs-t generally unable to improve upon DRL-abs across the board, suggesting that transferring Karel behaviors with RL from one task to another is ineffective. Furthermore, both the HRL baselines achieve poor performance, likely because agent actions alone provide insufficient supervision for a VAE to encode useful action trajectories on unseen tasks unlike programs. Finally, the poor performance of the naïve program synthesis baseline highlights the difficulty and inefficiency of learning to synthesize programs from scratch using only rewards. In the appendix, we present programs synthesized by LEAPS in Figure 11, example optimal programs for each task in Section F (Figure 9), rollout visualizations in Figure 16, and additional results analysis in Section H.
Repetitive Behaviors. Solving STAIRCLIMBER and FOURCORNER requires acquiring repetitive (or looping) behaviors. STAIRCLIMBER, which can be solved by repeating a short, 4-step stair-climbing behavior until the goal marker is reached, is not solved by DRL-abs. LEAPS fully solves the task given the same perceptions, as this behavior can be simply represented with a while loop that repeats the stair-climbing skill. However VIPER performs poorly as its decision tree cannot represent such loops. Similarly, the baselines are unable to perform as well on FOURCORNER, a task in which the agent must pickup a marker located in each corner of the grid. This behavior takes at least 14 timesteps to complete, but can be represented by two nested loops. Similar to STAIRCLIMBER the bias introduced by the DSL and our generated dataset (which includes nested loops), results in LEAPS being able to perform much better.
8

---

Exploration. TOPOFF rewards the agent for adding markers to locations with existing markers. However, there are no restrictions for the agent to wander elsewhere around the environment, thus making exploration problem for the RL baselines, and thereby also constraining VIPER. L.APPS performs best on this task, as the ground-truth program can be represented by a simple loop that just moves forward and places markers when a marker is detected. MAZE also involves exploration, however its small size (8 X 8) results in many methods, including LEAPS, solving the task.
Complexity. Solving HARVESTER and CLEANHOUSE requires acquiring complex behaviors, result- ing in poor performance from all methods. CLEANHOUSE requires an agent to navigate through house and pick up all markers along the walls on the way. This requires repeated execution of a skill, of varied length, which navigates around the house, turns into rooms, and picks up markers. As such, all baselines perform very poorly. However, LEAPS is able to perform substantially better because these behaviors can be represented by a program of medium complexity with while loop and some nested conditional statements. On the other hand, HARVESTER involves simply navigating to and picking up a marker on every spot on the grid. However, this difficult program to synthesize given our random dataset generation process; the program we manually derive to solve HARVESTER is long and more syntactically complex than most training programs. As a result, DRL and VIPER outperform LEAPS on this task.
Learned Program Embedding Space. More analysis on our learned program embedding space can be found in the appendix. We present CEM search trajectory visualizations in Section B, demonstrating how the search population's 's rewards change over time. To qualitatively investigate the smoothness of the learned program embedding space, we linearly interpolate between pairs of latent programs and display their corresponding decoded programs in Section C. Section D, we illustrate how predicted programs evolve over the course of CEM search.
5.6 Generalization
We are also interested in learning whether the baselines and the programs synthesized by LEAPS can generalize to novel scenarios without further learning. Specifically, we investigate how well they can generalize to larger state spaces. We expand both STAIR CLIMBER and MAZE to 100 x 100 grid sizes (from 12 X 12 and 8 x 8, respectively). We directly evaluate the policies or programs obtained from the original tasks with smaller state spaces for all methods except DRL (its observation space changes), which we retrain from scratch. The results are shown in Table 4. All baselines perform significantly worse than before on both tasks. On the contrary, the programs synthesized by LEAPS for the smaller task instances achieve zero-shot generalization to larger task instances without losing any performance. Larger grid size experiments for the other Karel tasks and additional unseen configuration experiments can be found in Section G.
Table 4: Rewards on 100 100 grids.
STAIRCLIMBER
MAZE
DRL DRL-abs
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.04 (0.15)
VIPER
0.00 (0.00)
(0.12)
LEAPS
1.00 (0.00)
1,00 (0.00)
5.7 Interpretability
Interpretability in machine learning [69. 70] is particularly crucial when it comes to learning a policy that interacts with the environment [71-78). The proposed framework produces programmatic policies that are interpretable from the following aspects as outlined in [70].
Trust: interpretable machine learning methods and models may more easily be trusted since humans tend to be reluctant to trust systems that they do not understand. Programs synthesized by LEAPS can naturally be better trusted since can simply read and interpret them.
Contestability: the program execution traces produce chain of reasoning for each action, providing insights on the induced behaviors and thus allowing for contesting improper decisions.
Safety: synthesizing readable programs allows for diagnosing issues earlier (i.e. before execution) and provides opportunities to intervene, which is especially critical for safety-critical tasks.
In the rest of this section, we investigate how the proposed framework enjoys interpretability from the three aforementioned aspects. Specifically, synthesized programs are not only readable to human users but also interactive, allowing non-expert users with a basic understanding of programming to diagnose and make edits to improve their performance. To demonstrate this, we asked non-expert

---

humans to read, interpret, and edit suboptimal LEAPS policies to improve their performance. Partici- pants edited LEAPS programs on Karel tasks with suboptimal reward: TOPÖFF, FOURCORNER. and HARVESTER. With just 3 edits, participants obtained mean reward improvement of 97. 97,1% and with 5 edits, participants improved by 125%. This justifies how our synthesized policies can be manually diagnosed and improved, a property which DRL methods lack. More details and discussion can be found in Section E.
Discussion
We propose framework for solving tasks described by MDPs by producing programmatic policies that are more interpretable and generalizable than neural network policies learned by deep rein- forcement learning methods. Our proposed framework adopts flexible program representation and requires only minimal supervision compared to prior programmatic reinforcement learning and program synthesis works. Our proposed two-stage learning scheme not only alleviates the difficulty of learning to synthesize programs from scratch but also enables reusing its learned program embedding space for various tasks. The experiments demonstrate that our proposed framework outperforms DRL and programmatic baselines on a set of Karel tasks by producing expressive and generalizable programs that can consistently solve the tasks. Ablation studies justify the necessity of the proposed two-stage learning scheme as well as the effectiveness of the proposed learning objectives.
While the proposed framework achieves promising results, we would like acknowledge two assumptions that are implicitly made in this work. First, we assume the existence of a program executor that can produce execution traces of programs. This program executor needs be able to return perceptions from the environment state as well as apply actions to the environment. While this assumption is widely made in program synthesis works, program executor can still be difficult to obtain when it comes to real-world robotic tasks. Fortunately, in research fields such as computer vision or robotics, great amount of effort has been put into satisfying this assumption such as designing modules that can return high-level abstraction of raw sensory input (e.g. with object detection networks, proximity/tactile sensors, etc.).
Secondly, we assume that it is possible to generate a distribution of programs whose behaviors at least remotely related to the desired behaviors for solving the tasks of interest. It can be difficult to synthesize programs which represent behaviors that are more complex than ones in the training program distribution, although one possible solution employ better program generation process to generate programs that induce more complex behaviors. Also, the choice of DSL plays an important role in how complex the programs can be. Ideally, employing more complex DSL would allow our proposed framework to synthesize more ad advanced agent behaviors.
In the future, we hope to extend the proposed framework to more challenging domains such real- world robotics. We believe this framework would allow for deploying robust, interpretable policies for safety-critical tasks such robotic surgeries. One way make LEAPS applicable to robotics domains would be to simultaneously learn perception modules and action controllers. Other possible solutions include incorporating program execution methods [79-84] that designed to allow program execution or designing DSLs that allow pre-training of perception modules and action controllers. Also, the proposed framework shares some characteristies with works in multi-task RL (79, 80, 85-89] and meta-learning [90-99]. Specifically, it learns a program embedding space from distribution of tasks/programs. Once the program embedding space is learned, it can be be reused to solve different tasks without retraining.
Yet, extending LEAPS to such domains can potentially lead to negative societal impacts. For example, our framework can still capture unintended bias during learning or suffer from adversarial attacks. Furthermore, policies deployed in the real world can create great economic impact by causing job losses in some sectors. Therefore, we would encourage further work to investigate the biases, safety issues, and potential economic impacts to ensure that the deployment in the field does not cause far-reaching, negative societal impacts.
Acknowledgments
The authors appreciate the fruitful discussions with Karl Pertsch, Youngwoon Lee, Ayush Jain, and Grace Zhang. The authors would like to thank Ting- Yu S. Su for contributing to the learned
10

---

program embedding spaces visualizations. The authors are grateful to Sidhant Kaushik, Laura Smith, and Siddharth Verma for offering their time participate the human debugging interpretability experiment.
Funding Transparency Statement
This project was partially supported by USC startup funding and by NAVER Al Lab.
References
[1] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human level control through deep reinforce- ment learning. Nature, 2015.
[2] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieserr, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 2016.
[3] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 2018.
[4] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamnekki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grand- master level starcraft ii using multi-agent reinforcement learning. Nature, 2019.
[5] Alexandre Campeau-Leeoe Lecours, Hugo Lamontagne, Simon Latour, Philippe Fauteux, Véronique Maheu, François Boucher, Charles Deguire, and Louis-Joseph Caron L'Ecuyer. Kinova modular robot arms for service roboties applications. In Rapid Automation: Concepts, Method- ologies, Tools, and Applications. 2019.
[6] Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off- aff-policy updates. International Conference Robotics and Automation, 2017.
[7] OpenAl: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 2020.
[8] Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to con- trol: Learning behaviors by latent imagination. In International Conference on Learning Representations, 2020.
[9] Jun Yamada, Youngwoon Lee, Gautam Salhotra, Karl Pertsch, Max Pflueger, Gaurav Sukhatme, Joseph J Lim, and Peter Englert. Motion planner augmented reinforcement learning for robot manipulation in obstructed environments. In Conference Robot Learning, 2020.
[10] Grace Zhang, Linghan Zhong, Youngwoon Lee, and Joseph J Lim. Policy transfer across visual and dynamics domain gaps via iterative grounding. In Robotics: Science and Systems, 2021.
[11] Youngwoon Lee, Edward S Hu, Zhengyu Yang, and Joseph Lim. To follow not follow: Selective imitation learning from observations. In Conference on Robot Learning, 2019.
[12] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Neural Information Processing Systems, 2018

---

[13] Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Representations, 2020.
[14] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaud- huri. Programmatically interpretable reinforcement learning. In International Conference on Muchine Learning, 2018.
[15] Abhinav Verma, Hoang Le, Yisong Yue, and Swarat Chaudhuri. Imitation-projected program- matic reinforcement learning. In Neural Information Processing Systems, 2019.
[16] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International Conference on Machine Learning, 2017.
[17] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.
[18] Xinyun Chen, Chang Liu, and Dawn Song. Execution-guice neural program synthesis. In International Conference on Leurning Representations, 2019.
[19] Eui Chul Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Neural Information Processing Systems, 2018.
[20] Miguel LizaroGGredill Dianhuan Lin, J Swaroop Guntupalli, and Dileep George. Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs. Science Robotics, 2019.
[21] Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program syn- thesis from diverse demonstration videos. In International Conference on Machine Learning, 2018.
[22] Raphaël Dang-Nhu. Plans: Neuro-symbolic program learning from videos. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Neural Information Processing Systems, 2020.
[23] Richard E Pattis. Karel the robot: a gentle introduction to the art of programming. John Wiley & Sons, Inc., 1981.
[24] Danfei Xu, Suraj Nair, Yuke Zhu, Julian Gao, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Neural task programming: Learning to generalize across hicrarchical tasks. In International Conference on Robotics and Automation, 2018.
[25] Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural program meta-induction. In Advances in Nearal Information Processing Systems, 2017.
[26] Arvind Neelakantan, Quoe Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. In International Conference Learning Representations, 2015.
[27] Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014.
[28] Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In International Conference on Learning Representations, 2016.
[29] Alexander L. Gaunt, Mare Brockschmidt, Nate Kushman, and Daniel Tarlow. Differentiable programs with neural libraries. In International Conference on Machine Learning, 2017.
[30] Scott Reed and Nando De Freitas. Neural programmerr-nteepreeeers.. In International Confer- ence on Learning Representations, 2016.
[31] Jonathon Cai, Richard Shin, and Dawn Song. Making neural programming architectures generalize via recursion. In International Conference on Learning Representations, 2017.
12

---

[32] Da Xiao, Jo-Yu Liao, and Xingyuan Yuan. Improving the universality and learnability of neural prgraammer-mtterreeee with combinator abstraction. In International Conference on Learning Representations, 2018.
[33] Michael Burke, Svetlin Penkov, and Subramanian Ramamoorthy, From explanation to syn- thesis: Compositional program induction for learning from demonstration. arXiv preprint arXiv:/902. /0657, 2019.
[34] Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning to execute subroutines. In Neural Information Processing Systems, 2020.
[35] Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals. Strong generalization and efficiency in neural programs. arXiv preprint arXiv:2007.03629, 2020.
[36] De-An Huang, Suraj Nair, Danfei Xu, Yuke Zhu, Animesh Garg, Li Fei-Fei, Silvio Savarese, and Juan Carlos Niebles. Neural task graphs: Generalizing to unseen tasks from single video demonstration. In IEEE Conference on Computer Vision and Pattern Recognition, 2019.
[37] Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel. Programming with a differentiable forth interpreter. In International Conference on Machine Learning. 2017.
[38] Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. In International Conference Learning Representations, 2017.
[39] Richard Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Neural Information Processing Systems, 2018.
[40] Yunchao Liu, Jiajun Wu, Zheng Wu, Daniel Ritchie, William T. Freeman, and Joshua B. Tenenbaum. Learning to describe scenes with programs. In International Conference on Learning Representations, 2019.
[41] Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D Ernst. NI2bash: A corpus and semantic parser for natural language interface to the linux operating system. In International Conference on Language Resources and Evaluation, 2018
[42] Yuan Hoan-Hong ue Liao, Xavier Puig. Marko Boben, Antonio Torralba, and Sanja Fidler. Synthesizing environment-aware activities via activity sketches. In IEEE Conference on Computer Vision and Pottern Recognition, 2019.
[43] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar- Lezama. Write, execute, assess: Program synthesis with repl. In Neural Information Processing Systems, 2019.
[44] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. arXiv preprint arxiv:2006.08838 2020.
[45] Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tar- low. Deepcoder: Learning to write programs. In International Conference on Learning Representations, 2017.
[46] Pawel Liskowski, Krzysztof Krawiec, Nihat Engin Toklu, and Jerry Swan. Program synthesis as latent continuous optimization: Evolutionary search in neural embeddings. In Genetic and Evolutionary Computation Conference, 2020.
[47] Daniel A Abolafia, Mohammad Norouzi, Jonathan Shen, Rui Zhao, and Quoc V Le. Neural program synthesis with priority queue training. arXiv preprint arXiv: arXiv:/80/.08. 03556, 2018.
[48] Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, and Manzil Zaheer. Latent program- mer: Discrete latent codes for program synthesis. International Conference on Machine Learning, 2021.
13

---

[49] Tom Silver, Kelsey R Allen, Alex K Lew, Leslie Pack Kaelbling, and Josh Tenenbaum. Few-shot bayesian imitation learning with logical program policies. In Association for the Advancement of Artificial Intelligence, 2020.
[50] Jiajun Wu, Joshua B Tenenbaum, and Pushmeet Kohli. Neural scene de-rendering. In IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[51] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harri Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03333 2021.
[52] Ferran Alet, Javier Lopez-Contreras James Koppel, Maxwell Nye, Armando Solar-Lezama, Tomas Lozano-Perez, Leslie Kaelbling, and Joshua Tenenbaum. A large-scale benchmark for few-shot program induction and synthesis. In International Conference on Machine Learning. 2021.
[53] Xinyun Chen, Dawn Song, and Yuandong Tian. Latent execution for neural program synthesis beyond domain-specific languages. arXiv preprint arXiv:2107.00101 2021.
[54] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski. David Dohan, Ellen Jiang, Carrie Cai, Michael Temry Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2 102.0708.7772 2021.
[55] Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, and Manzil Zaheer. Latent program- mer: Discrete latent codes for program synthesis. In International Conference on Machine Learning, 2021.
[56] Catherine Wong, Kevin Ellis, Joshua Tenenbaum, and Jacob Andreas. Leveraging language to learn program abstractions and search heuristics. In International Conference on Machine Learning, 2021.
[57] Xinyun Chen, Petros Maniatis, Rishabh Singh, Charles Sutton, Hanjun Dai, Max Lin, and Denny Zhou. Spreadsheetcoder: Formula prediction from semi-structured context. In Interna- tional Conference on Machine Learning. 2021.
[58] Maxwell Nye, Yewen Pu, Matthew Bowers, Jacob Andreas, Joshua B. Tenenbaum, and Armando Solar-Lezama. Representing partial programs with blended abstract semanties. In International Conference on Learning Representations, 2021.
[59] Dongkyu Choi and Pat Langley. Learning teleorcactive logic programs from problem solving. In International Conference on Inductive Logic Programming, 2005.
[60] Elly Winner and Manuela Veloso. Distill: Learning domain-specific planners by example. In International Conference on Machine Learning, 2003.
[61] Mikel Landajuela, Brenden K Petersen, Sookyung Kim, Claudio P Santiago, Ruben Glatt, Nathan Mundhenk, Jacob Pettit, and Daniel Faissol. Discovering symbolic policies with deep reinforcement learning. In International Conference Machine Learning, 2021.
[62] Diederik Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
[63] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with a constrained variational framework. In International Conference on Learning Representations, 2016.
[64] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist rein- forcement learning. Machine learning, 1992.
[65] Reuven Y Rubinstein. Optimization of computer simulation models with rare events. European Journal of Operational Research, 1997.
14

---

[66] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction no-regret online learning. In International Conference on Artificial Intelligence and Statistics, 2011.
[67] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arx.vv1707.0634444 2017.
[68] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, 2018.
[69] Zachary C Lipton. The mythos of model interpretability. In ICML Workshop on Human Interpretability in Machine Learning, 2016.
[70] Owen Shen. Interpretability in ml: broad overview, 2020. URL htt.htttp/:mmll red/ muse/ 0aeee/5990666331
[71] Jesse Zhang, Brian Cheung, Chelsea Finn, Sergey Levine, and Dinesh Jayaraman. Cautious adaptation for reinforcement learning in safety-criticn settings. In International Conference Machine Learning, 2020.
[72] Lukas Hewing, Juraj Kabzan, and Melanie N. Zeilinger. Cautious model predictive control using gaussian process regression. IEEE Transactions on Control Systems Technology, 2019.
[73] Jaime F Fisac, Anayo K Akametalu, Melanic N Zeilinger, Shahab Kaynama, Jeremy Gillula, and Claire Tomlin. A general safety framework for learning -baee control in uncertain robotic systems. IEEE Transactions on Automatic Control, 2018.
[74] A.
Hakobyan, G. C. Kim, and I. Yang. Risk-aware motion planning and control using evar- constrained optimization. IEEE Robotics and Automation Letters, 2019.
[75] Dorsa Sadigh and Ashish Kapoor. Safe control under uncertainty with probabilistic signal temporal logic. In Proceedings of Robotics: Science and Systems, 2016.
[76] Felix Berkenkamp. Matteo Turchetta, Angela Schoellig, and Andreas Krause. Safe model- based reinforcement learning with stability guarantees. In Advances in Neural Information Processing Systems, 2017.
[77] Brijen Thananjeyan, Ashwin Balakrishna, Ugo Rosolia, Felix Li, Rowan McAllister, Joseph Gonzalez, Sergey Levine, Francesco Borrelli, and Ken Goldberg. Safety augmented value estimation from demonstrations (saved): Safe deep model-based for sparse cost robotic tasks. IEEE Robotics and Automation Letters, 2020.
[78] Anil Aswani, Humberto Gonzalez, S Shankar Sastry, and Claire Tomlin. Provably safe and robust learning- baaringg-basdd model predictive control. Automatica, 2013.
[79] Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International Conference on Machine Learning, 2017.
[80] Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli. Zero-shot task generalization with multi-task deep reinforcement learning. In International Conference on Machine Learning, 2017.
[81] Shao-Hua Sun, Te-Lin Wu, and Joseph J. Lim. Program guided agent. Conference on Learning Representations, 2020.
International
[82] Yichen Yang, Jeevana Priya Inala, Osbert Bastani, Yewen Pu, Armando Solar-Lezama and Mar- tin Rinard. Program synthesis guided reinforcement learning, arXiv preprint orXiv:2102.11137, 2021.
[83] Youngwoon Lee, Shao-Hua Sun, Sriram Somasundaram, Edward Hu, and Joseph Lim. Composing complex skills by learning transition policies. In International Conference on Learning Representations, 2019.
15

---

[84] Zelin Zhao, Karan Samel, Binghong Chen, and Le Song. Proto: Program-guided guided transformer for program-guide guided tasks. arXiv preprint 100002210000804, 2021.
[85] Yee Whye Teh, Victor Bapst, Wojeiech Marian Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. arXiv preprint wwXivv1777.000 04170, 2017.
[86] Richard Socher Tianmin Shu, Caiming Xiong. Hicrarchical and interpretable skill acquisition in multi-task reinforcement learning. International Conference Learning Representations, 2018.
[87] Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hicrarchical reinforcement learning for zero- shot generalization with subtask dependencies. In Advances in Neural Information Processing Systems, 2018.
[88] Ayush Jain, Andrew Szot, and Joseph Lim. Generalization to new actions in reinforcement learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 4661-4677 PMLR, 18 Jul 2020. URL httttps:/pproceeddiii 1119/jain200 html.
ml press/
[89] Karl Pertsch, Youngwoon Lee, and Joseph J. Lim. Accelerating reinforcement learning with learned skill priors. In Conference on Robot Learning. 2020.
[90] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems. 2017.
[91] Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim. Multimodal model-agnostic meta-learning via task-aware modulation. In Neural Information Processing Systems, 2019.
[92] Oriol Vinyals, Charles Blundell, Tim Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In Advances in Neural Information Processing Systems, 2016.
[93] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks. In International Conference on Machine Leurning, 2017.
[94] Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim. Toward multimodal model- agnostic meta-learning, arXiv preprint arXiv: 2018.
[95] Wei-Yo Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. A closer look at few-shot classification. In International Conference on Learning Representations, 2019.
[96] Yoonho Lee and Seungjin Choi. Gradient-Based Merm-ng with Learned Layerwise Metric and Subspace. In International Conference on Machine Learning, 2018.
[97] Alex Nichol and John Schulman. Reptile: a scalable metalearning algorithm. arXiv preprint arXiv: 00099,0999..0 2018
[98] Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. In Neural Information Processing Systems, 2020.
[99] Yun-Chun Chen, Chao-Te Chou, and Yu-Chiang Frank Wang. Learning to learn in a semi- supervised fashion. In European Conference on Computer Vision, 2020.
[100] L.T. Jolliffe. Principal Component Analysis. Springer Verlag. 1986.
[101] Mihalj Bakator and Dragica Radosav. Deep learning and medical diagnosis: review of literature. Multimodal Technologies and Interaction, 2018.
[102] Dinggang Shen, Guorong Wu, and Heung-Il I1 Suk. Deep learning in medical image analysis. Annual review of biomedical engineering. 2017.
[103] Biraja Ghoshal and Allan Tucker. Estimating uncertainty and interpretability in deep learning for coronavirus (covid-19) detection. arXiv preprint arXiv:2003. 10769, 2020.
16

---

[104] Chia-Jung Chang, Wei Guo, Jie Zhang, Jon Newman, Shao-Hus Hua Sun, and Matt Wilson. Behavioral clusters revealed by end-to-end decoding from microendoscopic imaging. bioRxiv, 2021.
[105] Amitojdeep Singh, Sourya Sengupta, and Vasudevan Lakshminarayanan. Explainable deep learning models in medical image analysis. Journal of Imaging, 2020.
[106] Vladimir losifovich Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 1966.
[107] Michihiro Yasunaga and Percy Liang. Graph-based, self-supervised program repair from diagnostic feedback. In International Conference on Machine Learning, 2020.
[108] Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. Semfix: Program repair via semantic analysis. In Conference on Software Engineering, 2013.
[109] Jiajun Jiang, Yingfei Xiong, Hongyu Zhang, Qing Gao, and Xiangqun Chen. Shaping program repair space with existing patches and similar code. In ACM SIGSOFT International Symposium on Software Testing and Analysis, 2018.
[110] Qi Xin and Steven Reiss. Leveraging syntax- related code for automated program repair. In International Conference on Automated Software Engineering, 2017.
[111] Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. Automated program repair. Communications of the ACM, 2019.
[112] Eric Schulte, Stephanie Forrest, and Westley Weimer. Automated program repair through the evolution of assembly code. In International Conference on Automated Software Engineering, 2010.
[113] Anil Koyuneu, Kui Liu, Tegawendé F Bissyandé, Dongsun Kim, Jacques Klein, Martin Monperrus, and Yves Le Traon. Fixminer: Mining relevant fix patterns for automated program repair. Empirical Software Engineering, 2020.
[114] Thomas Durieux and Martin Monperrus. Dynamoth: dynamic code synthesis for automatic program repair. In International Workshop on Automation of Software Test, 2016.
[115] Yi Li, Shaohua Wang, and Tien N Nguyen. Dlfix: bantext-based code transformation learning for automated program repair. In International Conference on Software Engineering, 2020.
[116] Liushan Chen, Yu Pei, and Carlo A Furia. Contract-based program repair without the contracts. In International Conference Automated Software Engineering, 2017.
[117] Martin White, Michele Tufano, Matias Martinez, Martin Monperrus, and Denys Poshyvanyk. Sorting and transforming program repair ingredients via deep learning code similarities. In IEEE International Conference on Software Analysis, Evolution and Reengineering, 2019.
[118) Rahul Gupta, Soham Pal, Aditya Kanade, and Shirish Shevade. Deepfix: Fixing common language errors by deep learning. In Association for the Advancement of Artificial Intelligence, 2017.
[119] Ke Wang. Rishabh Singh, and Zhendong Su. Dynamic neural program embedding for program repair. arXiv preprint arXiv:1711.0716. 2017.
[120] Ali Mesbah, Andrew Rice, Emily Johnston, Nick Glorioso, and Edward Aftandilian. Deepdelta: learning to repair compilation errors. In ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2019.
[121] He Zhu, Zikang Xiong, Stephen Magill, and Suresh Jagannathan. An inductive synthesis frame- work for verifiable reinforcement learning. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2019.
[122] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In IEEE Conference on Computer Vision and Pattern Recognition, 2015.
17

---

[123] Karol Hausman, Jost Tobias Springenberg, Ziyu Wang. Nicolas Heess, and Martin Riedmiller. Learning an embedding space for transferable robot skills. In International Conference on Learning Representations, 2018.
[124] 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, 2015.
18


Reviews:
[{"review_id": "sQhjVkaEI9A", "reviewer": "Reviewer_dyBV", "summary": "The paper approaches reinforcement learning from a program synthesis perspective and proposes a new method - LEAPS - that is capable of learning programmatic policies just from weak reward signals. This is achieved in two steps:\ni) learning a smooth latent manifold where similar programs are encoded close to each other;\nii) searching the latent space efficiently via the Cross Entropy Method.\nLEAPS is applied to several tasks in the Karel domain where it successfully can learn programmatic policies that are even transferable to larger state spaces for zero-shot learning.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed reading the manuscript and found some of the presented ideas quite interesting. As noted by the authors, the problem of synthesizing programs directly from weak reward signals is quite challenging and so other works utilize entire traces for supervision or resort to program templates. In contrast, the proposed approach is capable of synthesizing programs from the ground up using a predefined DSL that contains loops, conditional statements and domain dependent actions and perceptions.\n\nAt the core of this novel capability is the set of behavioural losses used to train a varioational autoencoder resulting in a latent space where programs with similar behaviours are grouped closer to each other. While the proposed program behaviour loss is an obvious step towards building a program autoencoder, the latent behaviour loss is a non-trivial addition which according to the ablation studies makes a sizeable contribution to the performance of the model. How did you choose the architecture of the neural program executor module and were there any speasdcial considerations driven by the DSL and family of supported programs? Once trained how closely did the neural program executor can actually match the execution of the ground truth program?\n\nAnother question that I have regarding the behavioural losses is why did you decide to use just actions? Wouldn't action-state sequences provide a stronger supervision signal especially when only fragments of the execution of the reconstructed program semantically match the ground truth trace?\n\nThe analyses, experiments and reported results clearly demonstrate that LEAPS does provide RL agents with the capability to learn programatic policies that can even generalize to larger worlds. However, there are a few more results which may be reported that I think would increase the quality of the paper:\n\n1) Traversals of the program latent space and visualizing interpolations between different programs. This will really shed more light on what the learnt latent space looks like.\n\n2) More explicit information about the computational resources and time needed to run the various experiments.\n\n3) At least one plot showing how the best found program evolves over the course of searching - complexity and losses.\n\nLastly, in figure 15 in the appendix the CEM search is described as converging to the ground truth solution, but the population of candidate solutions in fact passes right by the ground truth and never actually returns to it. Can you explain this phenomena?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the biggest limitation of the proposed paper is the fact that only relatively short programs are considered. This of course is a result of the simple grid world the Karel domain defines. Therefore, it will be very interesting to see LEAPS applied to tasks that require more complex and compositional behaviours. Additionally, as mentioned by the authors, bringing LEAPS to the robotics domain will be a great step towards synthesizing robust robotics policies, however, I believe for that the LEAPS framework will need to be extended to handle learning perception modules and action controllers simultaneously with the policy search.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "aOmBPgXfdp", "reviewer": "Reviewer_gcpQ", "summary": "This paper suggests representing policies for MDPs as programs, and shows how to learn programmatic policies effectively from a mix of trial-and-error experience on specific tasks and a pre-training phase to create an embedding that maps programs producing similar behaviors into similar points in the embedding. The authors compare their method to a variety of baselines, including both ablations of their own model as well as more traditional approaches from hierarchical RL, deep RL, and a standard program synthesizer on the KAREL domain. The authors find that the programmatic policy representations perform better overall for many of the KAREL tasks, and generalize better to larger problems than they were trained on.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper’s pros (thoroughly done scientific experiments, a different perspective on how to build generalizable policies for MDPs, and considered framing and discussion pointing out its own limitations) slightly outweigh its cons (missing related work from classical planning, confusion about the possibility for loops in decision trees, and statistically borderline results in some experiments), and I believe this paper presents a reasonable scientific effort that will be interesting for a subset of the NeurIPS community.\n\nIn the next sections I go into pros and cons in more detail, and point to areas that I would like the authors to comment on/address in their revisions. ++ is pro, -- is con.\n\nRelated work:\n++ The authors do a reasonable job of situating the work with respect to other efforts to synthesize programmatic policies from deep RL agents, program synthesis approaches, and limitations of finite state machines\n\n-- The authors make statements about decision trees not handling loops several times in the paper, but that is a somewhat misleading statement. It is possible to include loops in decision trees, but these loops must be encapsulated differently within the DSL (see Silver et al, AAAI 2020 for an example where they use a “scanning” function that operates like a while loop within a decision tree context). In the author’s DSL, I think this would amount to having a separate “Loop l := while(b, s)” and to make the program “p:= DEF run() : s | l”. There are certainly limitations to this, and these loops cannot be generally as expressive as doing full program synthesis, but I think this statement should be watered down (or removed) within the paper. It might help to reference Silver 2020 to point out the limitations of such setups of while loops in decision trees.\n\n-- There is a missing body of work from classical planning on synthesizing policies as programs in these same structures, two references below\n1. For synthesizing for loop and while loop policies: LoopDistill (Elly Winner and Manuela Veloso, 2007)\n2. For learning policies as programs in a more expressive space: Learning Teleoreactive Logic Programs from Problem Solving (Choi and Langley)\n\nResults:\n++ I appreciated the thoroughness of ablations covering all main aspects of the program embedding learning, and the method was (mostly) explained clearly.\n++ There were many comparisons to baselines, and these baselines were mostly appropriately chosen for the domain to underscore the points of the paper (HRL to address extended actions vs. extended actions as programs, DRL-abs to address differences in input representation, VIPER to address at least one alternative program synthesis approach (although there are others that are “neural” and might have been more appropriate, such as REPL, Ellis et al 2019)). The baselines’ hyperparameters were also reasonably optimized, as outlined in the supplement.\n\n++ The authors included exceptionally extensive supplementary material (31 pages!) with some nice visualizations of the learned program embeddings, extra details needed to reproduce the main experiments, extra experiments on transfer to unseen configurations of KAREL tasks, and code.\n\n-- many of the results are statistically insignificant given the enormous standard deviations in the tables, especially in the program reconstruction. While it seems like the full LEAPS model performs statistically better than the naive model, it *does not* seem to perform better than the baselines in a statistically significant way.\n\n-- it would have been nice to get some insight for why DRL-abs does not always perform better than DRL, as well as how these models were trained/how their parameters were validated. Could the authors comment on this?\n\n-- why can VIPER not solve the generalization task? If it’s also operating on the abstract space, I would have thought it should be invariant to the grid size since it will only have information about objects in the environment? Similarly why did the authors only evaluate generalization on StairClimber and Maze? It should be trivial to expand all of the problems to larger grids and it seems a bit weird to pick only 2.\n\n-- a simple way to keep the observation size the same for DRL between different problem sizes, which would also be a more fair comparison to the LEAPS model, would be to use a fully connected network (Long*, Shelhamer*, Darrell, 2015) as the policy, as that will look at grid locations in a more local way and be invariant to problem size (see Silver, 2020 who similarly found that this type of network significantly out-performed a fully connected model for changing grid sizes). This might perform much better than the current method while also generalizing better, and be a good test of whether it’s the programmatic structure of the policy that is required, or if it’s more of a “locality” or “relational” requirement.\n\n-- I think details about the RL aspect of the test tasks needs to be made very clear. E.g. how many episodes does an agent get within each task? How many training tasks do the DRL agents receive before they are evaluated? How are the training tasks for these distinguished from the test tasks for generating the numbers in Table 3?\n\nDiscussion\n++ excellent pointers to limitations of the work - a crucial component of ML papers.\n-- I would have liked to see a little more discussion on why programs specifically vs. hierarchical policies vs. abstract action spaces, and how this kind of approach would be expected to work for problems that are not specifically designed for program synthesis techniques. However I recognize there isn’t too much space and the authors alluded to this in the results sections.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes they have addressed these adequately.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "P3T_CAC-mqw", "reviewer": "Reviewer_etfX", "summary": "- Authors use a two-stage method for program synthesis: (1) They\n  create an embedding space capturing the semantics of the program\n  space; (2) They search through the embedding space for a program\n  that solves the task in hand.\n- They use variational autoencoder to encode programs, where an\n  encoder maps a sequence of program tokens into a latent space, while\n  a decoder maps from the latent space into the original program. They\n  use a combination of loss functions to ensure that not only\n  syntactically similar programs are close to each other in the latent\n  space but also semantically close programs. Loss function consists\n  of a composition of 3 losses. (A) Classical beta VAE loss which\n  helps that syntactically close programs are close to each other. (B)\n  Program behavior reconstruction loss which helps that semantically\n  similar programs are close to each other in the embedding space. For\n  example, two syntactically different programs can make same actions\n  under same situations. This loss is defined by difference between\n  execution traces of original and reconstructed program. (C) Latent\n  behavior reconstruction loss. This loss is constructed by learning a\n  policy to predict correct action based on the latent program\n  embedding. This allows for backpropagating gradient through the\n  policy and the encoder to ensure better quality of the embeddings.\n- After training the variational autoencoder, authors use a cross\n  entropy method to find a program with maximal performance using the\n  latent space. They sample the latent space distribution of programs,\n  decode the latent program into an actual program, execute the\n  program to obtain corresponding rewards, and repeat the process.\n- Authors did a nice ablation study where they measured effectiveness\n  of their individual design decisions: evaluating each of the loss\n  function components, as well as the effectiveness of the latent\n  space search method for finding the best performing program. They\n  compared they method to other methods, deep reinforcement learning\n  (DRL) based as well as Viper which is a decision tree policy\n  obtained by mimicking a DRL agent.", "questions": "", "limitations": "", "rating": 7, "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": "- Originality: I find the approach to be novel, creatively designing\n  loss functions ensuring quality latent space representation of\n  programs.\n\n- Significance: Program synthesis is an important and challenging\n  research area, and thus I find the problem being solved\n  important. Technique is illustrated on a simple (Karel) tasks which\n  might seem insufficient, but the program synthesis field is still at\n  the stage where small problems are hard to solve, thus I find the\n  choice appropriate.\n  \n- Paper is well written and easy to follow. In addition, authors\n  provide extensive appendix and accompanying web page with useful\n  information.\n\n- Figure 2 is very informative. I would suggest extending the caption\n  of the figure so it is more self-contained. For example, explain\n  what policy Pi is, as well as a1, a2, etc. I understood different\n  parts of the figure only when I thoroughly read the paper.\n\n- In the future, it would be good to evaluate the approach on tasks\n  that are outside of the Karel domain.\n\n- I do not have a good track of other approaches that can be used for\n  synthesizing Karel programs, and thus am not certain if all relevant\n  approaches are included in the comparison.\n\n- Questions\n    - Have you considered different ways of generating programs than\n      pure random generation? Are there many programs that are 'not\n      interesting' when performing random generation?\n    - Program Embedding Space Smoothness. Is there a specific reason\n      why embedding space search is performed on the train/val set, vs\n      test set? Does the same trend apply to the test set?\n    - In Table 2, do results represent percent of times that execution\n      traces of two programs match (averaged across program pairs)? I\n      understand that Rmat is defined as number of times traces match,\n      not percent of times.\n    - equation 4 (latent behavior reconstruction loss): Loss is\n      referred to as a cross entropy loss. However, EXECt(ro) seems\n      incorrect as it's constant in the inner sum. I assume it should\n      be 1 in a case of the executed action, and 0 otherwise?\n\n- Minor\n    - Line 233: \"shown in Figure 6\". This figure is not in the main\n      text.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors did cover these areas. They could elaborate how does their approach scale to other domains.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NeTLmY8v8Pi", "reviewer": "Reviewer_FK1E", "summary": "This paper presents a two-stage method for reinforcement learning via program synthesis, and shows that is is effective compared to baselines for a number of simple gridworld tasks, deminstrating a degree of out-of-distribution generalisation. The first stage of the process learns a latent space for encoding programs, and the second stage searches that latent space for programs that maximise reward in  the task. Overall a very nice paper that deserves publication.", "questions": "", "limitations": "", "rating": 8, "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": "This is a very substantial and impressive piece of work. Program synthesis is a very promising avenue for building RL agents that achieve better generalisation, and whose representations are humanly interpretable. A major accomplishment of this paper is to learn embeddings of programs (in a variant of the Karel language) using a VAE with a recurrent encoder and decoder and three different losses. (I’m not sufficiently famiiar with recent ML literature on program synthesis to know whether this is wholly new - so I rely on other reviewers to confirm this - but it seems like a significant step to me.) The authors carry out an extensive evaluation, with careful ablations, and show the effectiveness of the approach on a number of (admittedly quite simple) RL tasks. The most important result, to my mind, comes towards the end of the main text, which is to show that learned programs generalise to out-of-distribution grid sizes, where other approaches fail. The paper is clearly written and logically organised, although the method is complex, which means that a lot of referring to the Appendix is needed to follow it. (This is not a criticism, of course; it’s just a corrolary of the page limit.) Extensive material is supplied in the Appendix to back up the main paper.\n\nThere are quite a few issues in the definition of the DSL in Figure 1.\n\n1) “while(b)” should be “while(b): s”\n\n2) the definition of “Perception” is, at present, unused. I suspect the authors meant to write “Percept h” rather than “Perception h”, and to write “percept h” in the definition of a “Condition”.\n\n3) Since negation is the only logical operator, the definition of  “Condition” should perhaps be simply “percept | not percept”. (Or rather “percept h | not percept h”; see (2).) At present it allows for, say, “not not not not percept”, which probably unintended, and surely unnecessary.\n\n4) Don’t you need some brackets in the grammar? Otherwise how do you distinguish “while(B): (S1 ; S2)” from “(while(B): S1) ; S2”? (Obviously this isn’t an issue in normal Karel, where white space is used to indicate structure.) Indeed, from the examples in the Appendix (Fig. 6), it’s clear there are more symbols used in the code than in the grammar of Fig. 1, such as “c(“ and “)c”, which fulfil this bracketing function, as described in the caption. It’s a minor thing, but I feel the DSL grammar in Fig. 1 should be made to match this; it’s really a syntactic variant of Karel.\n\nSection 4.1: I was very curious, at this point, to know what the architecture of q_phi and p_theta was. It took me a while to hunt them down in the Appendix (Section F6). A pointer to this material in the main text (Section 4.1) would be helpful.\n\nIn the Appendix (Section F6), you state “we utilize a syntax checker … at the output of the decoder to limit predictions to syntactically valid tokens”. How do you do this? Does the training loop just skip to the next sample if a syntactically incorrect program is generated? This can’t be right? How do you use the syntax check?\n\nHow do you sample from the set of possible programs in order to learn the program embedding? Do they all carry out meaningful behaviours? Do they all terminate?\n\n\nTYPOS\n\nLines 81-82: “This limit the set of synthesizable programs” -> “This limits the set of synthesizable programs”\n\nLines 108-109: “view this objective is a special case” -> “view this objective as a special case”\n\nFigure 3 caption: “tasks that demands certain behaviors” -> “tasks that demand certain behaviors”\n\nLine 166: “ through supervised instead of RL gradients” -> “ through supervised learning instead of RL gradients” (presumably)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors include some material in the Discussion", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an interesting idea of learning policies for solving RL problems through program synthesis.  The key is to learn a good program embedding space, through 3 different losses that take care of 3 different aspects of a program representation.

The reviewers all appreciate the clarity of the paper and liked the idea.  The extensive ablations and supplementary material are also great for supporting the proposed approach.

In the future showing that this approach works on other domains beyond Karel, e.g. Minecraft and CARLA as suggested by the authors in the discussion, would be great.
Decision: Accept (Poster)