Programmatic Reinforcement Learning without Oracles
Authors: Wenjie Qiu
He Zhu
Venue: ICLR 2022 Spotlight (2022)
Keywords: Reinforcement Learning
Programmatic Reinforcement Learning
Compositional Reinforcement Learning
Program Synthesis
Differentiable Architecture Search

Abstract: Deep reinforcement learning (RL) has led to encouraging successes in many challenging control tasks. However, a deep RL model lacks interpretability due to the difficulty of identifying how the model's control logic relates to its network structure. Programmatic policies structured in more interpretable representations emerge as a promising solution. Yet two shortcomings remain: First, synthesizing programmatic policies requires optimizing over the discrete and non-differentiable search space of program architectures. Previous works are suboptimal because they only enumerate program architectures greedily guided by a pretrained RL oracle. Second, these works do not exploit compositionality, an important programming concept, to reuse and compose primitive functions to form a complex function for new tasks. Our first contribution is a programmatically interpretable RL framework that conducts program architecture search on top of a continuous relaxation of the architecture space defined by programming language grammar rules. Our algorithm allows policy architectures to be learned with policy parameters via bilevel optimization using efficient policy-gradient methods, and thus does not require a pretrained oracle. Our second contribution is improving programmatic policies to support compositionality by integrating primitive functions learned to grasp task-agnostic skills as a composite program to solve novel RL problems. Experiment results demonstrate that our algorithm excels in discovering optimal programmatic policies that are highly interpretable. The code of this work is available at https://github.com/RU-Automated-Reasoning-Group/pi-PRL.

Published as a conference paper at ICLR 2022
PROGRAMMATIC REINFORCEMENT LEARNING WITHOUT ORACLES
Wenjie Qiu
He Zhu
Department of Computer Science Rutgers University wq378cs. rut gers. edu
Department of Computer Science Rutgers University
hz.755ec... rut.ers.
ABSTRACT
Deep reinforcement learning (RL) has led to encouraging successes in many challenging control tasks. However, a deep RL model lacks interpretability due to the difficulty of identifying how the model's control logie relates its network structure. Programmatic policies structured in more interpretable representations emerge as promising solution. Yet two shortcomings remain: First, synthesizing programmatic policies requires optimizing over the discrete and non-differentiable search space of program architectures. Previous works are suboptimal because they only enumerate program architectures greedily guided by pretrained RL oracle. Second, these works do not exploit compositionality. an important programming concept, to reuse and compose primitive functions form complex function for new tasks. Our first contribution is a programmatically interpretable RL framework that conducts program architecture search on top of continuous relaxation of the architecture space defined by programming language grammar rules. Our algorithm allows policy architectures to be learned with policy parameters via bilevel optimization using efficient policy-gradien methods, and thus does not require a pretrained oracle. Our second contribution is improving programmatic policies to support compositionality by integrating primitive functions learned to grasp task-agnostic skills as a composite program to solve novel RL problems. Experiment results demonstrate that our algorithm excels in discovering optimal programmatic policies that are highly interpretable.
INTRODUCTION
growing body of research has explored programs in domain domain-specific programming language as new RL policy representation that intentionally encourages policy interpretability. Yet, learning policy as a high-level program in a structured representation is challenging. This because algorithms must jointly identify reasonable program architecture to allow for sufficient expressiveness while optimizing the parameters of the program modules in the architecture. For example, depending on the shape of maze, walking robot different goals the maze by program may require various if-then-elss conditions to travel along different paths, the number of which might not be known to the agent before training. To curb the non-differentiable program architecture search space, existing programmatic policy learning algorithms either learn from a pretrained program embedding space that must support smooth interpolation (Trivedi et al., 2021), must be guided by the supervision of a pretrained oracle (e.g. a neural network policy trained by RL) via a teacher-student learning paradigm (Bastani et al., 2018; Silver al., 2020; Inala et al., 2020; Verma et al., 2018: 2019). The task of imitating an oracle is significantly simpler than the full RI problem. However, since the policy space of neural networks and that of programmatic policies are very different, a significant performance gap exists between an imitating program and its RL oracle (Verma et al., 2018).
The first contribution of our paper is a framework to synthesize interpretable and differentiable programmatic policies solely from reward signals by policy gradient methods, without needing any oracles or pretraining. A conceivable way of synthesizing program architectures would be to enumerate all possible architectures induced by the grammar of run standard RL for each to find the optimal values of its unknown parameters, and return the best program. However, doing so is computationally expensive each RL trial may explore millions
policy language,

---

Published as a conference paper at ICLR 2022
of environment steps. Inspired by recent advances in differentiable neural architecture search e.g. DARTs (Liu et al., 2019b), we relax the discrete program architecture search space to be continuous. Specifically, we encode program architecture synthesis learning the probability distribution over all possible architecture derivations (up to a certain bound on program abstract syntax tree depth) induced by policy language grammar. This enables RI. algorithm to jointly optimize program architectures and the parameters of program modules via policy-gradient methods.
Our second contribution is improving programmatic policies support compositionality the integration of primitive functions trained to grasp basic, task-agnostic skills (e.g. running forward or jumping) into a new complex function as a composite model solve novel RL problems (e.g. jumping over multiple hurdles to reach a target). As opposed to policy ensemble models based on neural networks (Qureshi et al., 2020), our programmatically composite models interpret how primitive functions are composed under different environment conditions based on an RL agent's perceptions, and naturally generalize to novel scenarios. We further apply programmatic policies to address challenging hierarchical RL problems. Our solution leverages the specifications of primitive functions to create an optimal high-level control plan via a satisfiability constraint solver and implements the high-level plans by learned composition of primitive functions.
Finally, we benchmark our method against the state-of-the the-arr RL methods. Our results demonstrate that the programmatic RL framework is able to solve extremely hard RL problems using highly interpretable policies with improved task performance.
PROBLEM MOTIVATION AND FORMULATION
We study how to express RI. policies as disferentiable programs, which use symbolic language constructs compose a set of parameterized primitive modules. To control agent, programmatic policy takes an environment state as input and computes an action as return for the agent to execute.
We view a programmatic policy as pair (E, 0), where E is a discrete program architecture and 0 is a vector of real-valued parameters of the program. A program archi- tecture E is structured based on the context-free free grammar (Hoperoft et al., 2007) of policy DSL. In this paper, we consider the context-free grammar depicted in the standard Backus-Naur form (Winskel, 1993) in Fig. A vertical bar "I" indicates choice. Such grammar consists of set of production rules X ::= 0 02 ... oj where X is a nonterminal and ..... ; TJ are either terminals nonter- minals. For example, we may expand the nonteriminal Eg in partial program if B₁ then C1 else E to if B, then C₁ else (if B₂ then C2 else E2). The nonterminals E and B stand for program expressions that evaluate to action values in R.' and Booleans, respectively, where mn is the action dimension size. We represent state input to programmatic policy as s { 12 U22---. zn)) where n is the state dimension size and v/2 s(x.]] is the value of æ, in s. As usual, the unbounded variables X' [21, I2, 12 ... ,, In.] are assumed be input variables (state variables in our context). A terminal in this grammar is a symbol that can appear in a program's 's code, e.g. the if symbol and x;
E : C if then else E
B = 0g + 0T X 2 0
Figure 1: A Context-free DSL Grammar for programmatic policies.
The semantics of program in E is mostly standard and given by function [E](s) defined for each DSL construct. For example, [s) s[2,] reads the value of a variable 2; in state input s. A policy may use an if-then-else branching construct. To avoid discontinuities for differentiability, we interpret its semantics in terms of a smooth approximation where a is the sigmoid function:
if B then C' clse (+) = (()] [C](s) (1 - (+)) [E]
(1)
Thus, any policy programmed in this grammar becomes differentiable program. C' is a controller used by a programmatic policy. During execution, the policy can invoke set of controllers under different environment conditions, according to the activation of B conditions in the program. We consider three DSLs depending on how C' is structured for affine, ensemble. and PID policies.
Affine Policies. The DSL for affine policies allows C to be expanded as an affine transformation:
Cafine
0- 0 X Oc.
2

---

Published as a conference paper at ICLR 2022
if V. + of ' >
then 95% TiP(s) s) + 5% (s) < Branch 1
else 02. + 02 >
then 95% (=) + 5% (RIIHTT(S)) - Branch 2 Branch 3
else 13% TDOWN (a) 87% TRIGHT
[ 2, y, G2, gy orctan 2, ||., yll
= [ 2.052, 0.049, 0.440, 0.181, 0.241, 1.43 J, A1c = -0.202
02 = [ [1.333, 2.204, 222111, 2.132, 1.878, 0.331 J, 02c = -0.416
Figure 3: An Ant Cross Maze program P Perass with three branches. A program input X' includes current Ant position x, y along with the target location 9as 9, (sampled from one of the three goals in Fig. 2). aretan & and ||r, yll2 functions of and y. Each branch composes primitive functions: TUP, TDOWN. TLEFT, and TRIGHT Composition weights are shown in percentage.
where 0 E m (learned) constants 0.- An example affine policy given Appendix K.1.
0g E Rm are policy parameters. Particularly, Caffine be simple some
Ensemble Policies. The most important feature of our programmatic model is compositionality composing and reusing task-agnostic primitives in new programs to solve novel problems. The DSL for ensemble policies includes pre-acquired primitives " TN callable library functions:
C 01 TI (s) + T2(5) + ON (N(ss)
Cx explicitly compose primitive functions (e.g. running forward or jumping) hierarchically into complex program (e.g. jumping over multiple hurdles to reach target) where 01. ... parameterize primitive combination. The input space of primitive function can be different from that of program (formally defined below). The semantics of C² is defined as follows:
.....00p ON e R'
exp(0:/T)
[s)
Σ Ts (s(s) where qi
=o= (xp(0,/T)
Here the composition weights (4: JN for primitive ensemble are computed using gumbel-softmax, where 7 is the temperature term (Jang al., 2017).
Suppose we know priori that PID control is suitable for stabilising of an RL system. We can express this knowledge using the DSL for PID functions that allows C' to be expanded as discretized, multivariable PID controllers (Zheng et al., 2002). We leave the details in Appendix K.2.
PID Policies.
Program Interpretabiliiyy Our RL algorithm searches over DSL to synthesize programmatic policies. Thanks to their structured and symbolic representation, the algorithm learns highly interpretable policies. For example, consider Ant Cross Maze environment depicted in Fig. 2. The maze contains three possible goal positions and one would be randomly selected each time. In this environment, the task for quadruped MuJoCo Ant is to reach the selected location by navigating through the maze staring from an initial position on the bottom and without collision crash. We consider the DSL for this task using ensemble policies Cz. includes four basic primitive functions for moving the Ant up TUP, down DDwN, left ALEFT, and right RRIGhT (pretrained as neural network policies using standard RI. algorithms with details left in App. F.2).
Figure 2: Ant Cross Maze
Fig. depicts a synthesized program Porose with three branches for solving the Ant Cross Maze environment. As specified in Equation 1, our semantics of a branching construct is approximated by the sigmoid function σ.. The value the predicate a Boolean condition determines the activation of the controller guarded by the Boolean condition. At each state, branch activation determines the strength each of the controllers in the program. For example, the activation of branch is (0, e + of X)), and the activation of branch 2 is (1 a a of -2)) a0 2 0f X)).

---

Published as a conference paper at ICLR 2022
Dranch One Act eitics
Branch One Achricc
Brack Teo Actisionn
Branct Time AchoDic
(a) Branch I activation,
(b) Branch 1 activation,
(c) Branch 2 activation, (G.. Gy) = (6, -6)
(d) Branch 3 activation. (Gz, 9y) (6, -6)
(gr, 9y) (12, 0)
(Gx, fy) (6, -6)
Figure 4: Branch activation as functions of Ant position (2. y) for program Peross.
function of (I, y) when the goal to reach is sampled 92 = 12, g, = O. The degree of activation (yellow) is close to I on all states under (12, 0) indicating that the ensemble policy branch I is used drive the Ant up to the goal. Indeed, according the distribution of each primitive function at branch I, the effect of TUP dominates. Fig. 4b, Fig. 4c, and Fig. 4d depict the activation of all three branches when the goal at G- 6, Gg = 6. The program can be interpreted as branch 1 (where TUP dominates) and branch 3 (where TRGGHT dominates) are activated in the yellow areas of Fig. 4b and Fig. 4d respectively. This allows the Ant to make curved up and right move to the goal (branch 2 is not activated during execution for this goal).
Fig. 4a depicts the activation of branch
Problem Formulation. We frame programmatic RL as Markov Decision Process (MDP) defined by tuple (S.A, T, R} where S and A represent the environment state space and action space, T S x A x S + [0, 1] captures the set of transition probabilities, and R S x A + R denotes the reward function. We assume S 2 IR. XUVI where X' is the set of input variables of composite program (defined by DSL) and V is the set of input variables of primitive functions. For an affine policy, V- = 0. At time 2 0, an RL agent receives an environment state St E S and performs an action a₂ AA selected by its policy (a, [st) S + A. Based on 8 and de, the agent transits to receive the next state according to the transition model T( 1 (s, 0z). and receives the reward R(s,,a). We aim to learn a programmatic policy π in the DSL in Fig. 1 by jointly synthesizing the program's s architecture E and optimizing the program's parameters 0 to maximize the cumulative discounted reward E E0.. Ee 7 R(st, where 7 (0,
ARCHITECTURE SEARCH FOR PROGRAMMATIC POLICIES
Inspired by differentiable neural architecture search e.g. DARTs (Liu et al., 2019b), we relax the policy architecture search space to be continuous. This amounts to collectively optimizing the probability distribution of all program architectures in the search space and assigning the the highest probability to the architecture that maximizes cumulative MDP reward.
Our algorithm is not specific to a DSL. takes as input any policy DSL with differentiable semantics and conducts policy architecture search program derivation tree of the DSL. Formally, program derivation tree is T = {V,E} where a node u E V contains partial architectures with missing expressions or a complete architecture permissible by the DSL. An edge (u, ug) E & exists if one can obtain the architectures in ug by expanding a nonterminal E within a partial architecture in u following some DSL production rules. If more than one rule can be applied to expand the nonterminal E. ug contains more than one architecture. Take the Peross program in Fig. 3 as a concrete example: Fig. 5 depicts program derivation tree for the DSL in Fig. where a controller C' is an ensemble policy. On the root node O, we have two choices to expand the initial nonterminal E1 to either an ensemble policy C1 or a partial architecture if B1 then C2 else Ez. Node thus contains two partial architectures. Formally, we use F(ur) to represent the set of architectures on a node ug-
To expand a nonterminal or a missing expression of partial program architecture, we relax the categorical choice of DSL production rules into softmax over all possible production rules for the missing expression with trainable weights. For example, on node 1, the choices to expand E, between the ensemble policy Cj and the conditional branching expression are weighted by the weight matrix W1 (obtained after softmax) drawn in Fig. 5. Based on W1, we choose to expand E₁ to the conditional branching expression node 1. Assume
further expand Eg node to conditional branching expression as well on node 5. Then again we have two choices to expand the nonterminal E, on node 5 weighted by w2. This time we choose expand Fgg an ensemble policy Cs. Formally, the
4

---

Published as a conference paper at ICLR 2022
19s
B, then C, else B 90%
lif B, then C, eise
6 1200
Puttig X
lot (7000)
Gflff & then C. alse &
88%
then C,
12%
Cilif & C. alse &
10 Larool
T + x22
Figure 5: Ant Cross Maze Program Derivation Tree with program input X. IT refers to the primitives of Ant moving up TUP, down TDDWN, left TLEFT and right TRIGHT that take the Ant's own observations.
weight matrix Wag of the incoming edge to node is of the shape R[(F(s)),, and Wag [F'] weighs the likelihood choosing a particular architecture E' E F(ug) for expanding E.
A program derivation tree T essentially expresses all possible program derivations up to certain bound on the depth program abstract syntax trees. To train architecture weights, we encode a program derivation tree itself as differentiable program zT,. that takes state as input. Its action output is weighted by the outputs of all programs included in nē... where w represents program architecture weights and 0 includes unknown program parameters of all the mixed programs in the tree. The semantics computation of an expression (s) in a program derivation tree T6 is delegated to its tree node where the nonterminal E is expanded and the categorical choice of expanding E on ug is relaxed a softmax over all possible choices:
exp(wus [ET)
[s](s) [s
[uE]($)=
Σ
ERKEF(WE) exp(wug [ET) [E'((s)
E'EF(ug)
Complexity. Assume that the root of hosts the initial DSL nonterminal E,,, d is the depth of T, A the number DSL production rules, and m is the maximum number of nonterminals in the body of any rules. The semantics of Tे... is defined as [T (s) = [E)] The number of DSL operations (e.g. evaluations of ensemble policies and Boolean conditions) invoked by [ET](.) is bounded by ((km)))) In practice, we optimize the run-time cost of [Er](-) as discussed in Appendix. F.I.
The parameters w and of program derivation nh... can be jointly optimized using any policy gradient methods. To obtain stochastic policy gradients, TT... (-|s) is encoded as a Gaussian policy where the tree program outputs the action distribution mean. A separate set of parameters specify (diagonal) distribution covariance. In this paper, we consider trust region methods e.g. (Schulman et al., 2015) and aim to maximize the "surrogate" objective function, subject to a constraint on the size of the policy update by 6, where P=T Maa
is the discounted state visitation frequency of oI. Waw"
AnT AnTaraa was an estimator the advantage function over a finite batch of samples from 7I Th and Oold, Wold are policy parameters and architecture weights before the update:
Th (s,a) L Tom (8,
maximizeo, Jo (0, w) = Eamp. awit aas waw
ATT (s.
subject to E Egcp-
DKKe ward (1s)
Te. (-1s)) 5
old
Policy Parameter Optimization. Our training algorithm is an iterative bilevel optimization proce- dure. At training iteration k, we perform two steps. At the first step, we optimize the lower-level program parameters f with respect to (2), freezing the upper-level architecture weights
8k+1 arg max Je (8, wx) s.t. Egcp, Bem-pTT..u b..
DKu( (-1s) TT. (-1s)) < (3)
9
Policy Architecture Optimization. At the second step, we optimize the upper-level architecture weights w with respect to (2), freezing the lower-level program parameters
Wk+1 = arg max Jo b (f&+1, w. s.t. Eeop,
D 1 (-1s) - 1
(-1s)) s
(4)
5

---

Published as a conference paper at ICLR 2022
1
1
0
0
0
1
75
0
1
1
0
1
1
1
0
0
1
1
Ant D-Maze
(b) D-Maze State Abstraction
(c) D-Maze High-Level Plan
Figure 6: Model-based high-level planning for Ant D-Maze.
Training steps (3) and (4) are alternated across training iterations until reward convergence. They can be approximately solved using the efficient conjugate gradient algorithm, after making linear approximation to the objective and a quadratic approximation to the constraint (Schulman et al., 2015). Upon convergence, based on architecture weights, we obtain discrete program architecture from T replacing each tree node containing multiple architectures with the most likely architecture top-down manner. Finally, we train the parameters in the chosen architecture using RI. (Schulman et al., 2015) until convergence from the parameter values learned by the architecture search process. The algorithmic pseudocode is depicted in Algorithm in the appendix.
PROGRAMMATIC HIGH-LEVEL PLANNING
We further explore learning programmatic policies for high-level planning tasks with long-horizon and weak reward signals. For example, consider the Ant navigation task in 3-maze from (Nachum et al., 2018) in Fig. 6a. Due to the complex maze shape, distance-based rewards do not lead to solving the problem. Hierarchical RL (HRL) is efficient approach to solve long-horizon high-level planning. HRL uses a high-level policy to generate a sequence of high-level goals and low-level policies to generate sequences of actions to achieve each successive goal. Existing HRI. methods are either model-free e.g. (Nachum et al., 2018; 2019) or model-based e.g. (Roderick et al., 2018 8; Jothimurugan et al., 2021). In model-free approach, the learning algorithm in Sec. can be applied to train HRL policies as programs. In this section, we focus on model-based planning that takes advantage of the structure in the model of high-level planning task to improve learning efficiency.
For model-based planning, we abstract over both states and actions to ensure a finite high-level model. Recall that functions in the DSL of ensemble policies are assumed to be simple, lowelevel primitives designed to grasp basic. task-agnostic skills (c.g. Ant moving up and down). We use these primitives as abstract actions because they abstract low-level agent actions to an abstract space of skills. Regarding state abstractions, similar to previous works (Abel et al., 2020; Winder et al., 2020; Jothimurugan et al., 2021), we assume that state abstractions can be effectively provided by domain experts. For instance, the abstract states of the D-maze are collected on an abstract 2-D gridworld m E X in Fig. 6b. An abstract grid (z, y) E N x N subsumes concrete positions with known scale where m [x. y] indicates walls and m jr. = O indicates navigable spaces. The domain expert can then specify pair of abstract initial state P (yellow) and goal state PGaaal (green).
Pinm (Zo: yo) 20 = 3 yo =
Paaaaa yk) = .r yk =1
Our design choice of state and action abstraction addresses important challenge of model-based HRL it has to simultaneously perform model-based high-level planning and estimate the state transition probabilities of the abstract model based on the current high-level policy (Jothimurugan et al., 2021). In our approach, we decouple this dependency. Since abstract actions as primitive functions implement simple, task-agnostic skills, straightforward directly specify the state- transition behavior of the abstract actions AAct as opposed to learning it. For example, the Ant primitives move an Ant by updating its horizontal position 2; or vertical position yi one step dr, or dy: on the abstract model. The Ant can also be moved diagonally via primitive composition:
(Pcc
(I₁-1: (
W4-1, T,, y1) Edx;, dy. 2, = 2;-1 + dx; A y: y:-1 dy: --1 < dr,, dy, S
An abstract action is specified together with a guard (oouadd that encodes the condition under which the action can occur. For example, an Ant in 3-maze should not walk into walls and the path from an old position to new position should not be blocked by walls.
PGanrd (T) 1, Di- 11 Fz; y:) m[xe][ys]] # (m(xx-1](sa) m m[xs]lun-i #

---

Published as a conference paper at ICLR 2022
We further leverage the primitive function specifications to synthesize high-level control plan the abstract model. Suppose for now that we are searching over a high-level plan of a fixed number & of abstract action steps to reach the goal state GGea from the initial state I
(Pni yo) A A (1 V1 2i 26) A PGunrd (14-1 Vi Ii. Mi)) (Gona (Tyss yk)
(5)
Constraint (5) can be solved by off-the- constraint solvers e.g. Z3 (de Moura & Bjørner, 2008). We incrementally search for longer and longer high-level plans, starting from k = 1 and increasing until the optimal solution is found. Such plan is a sequence of sub tasks. For example, the solved high-level plan for Ant D-Maze navigation is depicted in Fig. 6c. Since a sub task may depend on learn a low-level policy for each sub task
multiple primitives e.g. Ant turning around corner, as a programmatic ensemble policy composing primitive functions using the technique in Sec. 3 guided by distance-based rewards. This ensures that our HRL policies are interpretable at both high level and low level. More details including the algorithmic pseudocode are given in Appendix. A.2.
Compared to existing model-based HRL approaches e.g. (Jothimurugan et al., 2021), our algorithm additionally needs abstract actions to be specified (as fPatt and (Guard) rather than learned. We show that (1) providing specifications of task-agnostic abstract actions (primitive functions) is trivial even for complex high-level planning tasks (Appendix G. (2) more importantly, these easy-to-annotate specifications substantially improve the sample efficiency of HRL (Sec. 5).
5 EXPERIMENTS AND EVALUATIONS
We evaluated our approach on two groups of challenging continuous control benchmarks involving motion control and task planning Group one contains four MuJoCo environments that require agents to reach or move an object to target locations: (1) Ant Cross Maze: the example depicted in Fig. 2. (2) Ant Random Goal: The quadruped MuJoCo Ant in Fig. 10a is trained to reach randomly sampled goal location within a confined circular region. (3) Pusher: A robotic arm in Fig. 10b is trained to push cylinder object to given target location. (4) HalfCheetah Hurdle: A MuloCo halfcheetah in Fig. 10c is required to run and jump over three hurdles to reach a given goal area. Group two consists of three hierarchical RL benchmarks: (1) Ant D-Maze: the example depicted in Fig. 6a. (2) Ant Push: This task requires the Ant in Fig. 10d to push away a movable block to reach the goal region behind it. (3) Ant Fall: The Ant in Fig. 10e is required to push movable block into a rift to fill the gap and then walk across it to reach the target on the other side of the rift. Multiple neural network primitives were trained and included in our ensemble policy DSL e.g. HalfCheetah THMP and TFORWARD. Pusher - and TPUSH- DOWN (with details in Appendix F.2).
Programmatic RI. To the benchmarks from the first group, we apply the RI. algorithm in Sec. to learn program derivation tree nr? -RRI. from which we extract programmatic RL policies PPRR. The tree depth bound of ... -PRL is set to 6. Our baselines include Composition- 2020) that learns Bidirectional LSTM- ensemble policies using the SAC algorithm (Haarnoja et al., 2018) to combine the aank-agi primitives for solving the task environments. On-policy RL algorithms TRPO (Schulman et al., 2015) and PPO (Schulman al., 2017) are the other two baselines. Fig. 7a depicts the mean learning performance in terms of the agent's 's final distance from targets over 10 random seeds. TRPO and PPO both fail to reach the goals. During policy architecture search, -T -PRI. successfully solves all tasks and outperform or match the performance of the BiLSTM models of Composition-SAre SAC. The -7 -PRL models exhibit less data-efficiency than the Composition-SAl policies in part due to the use of TRPO for on- on-policy update that is less sample-effice efficient than off- oof-colicy SAC (our learning algorithm can also be applied to off- off-policy RL).
(Qureshi et al.,
Upon convergence of training π -PRL program derivation tree, our algorithm extracts a program T-PRL from x .PRL and trains it until convergence. Table 1 presents the mean and standard deviation of rPLL's final distance from given targets. Extracted programs recover the performance of TT models and continue to outperform or match the BiI.STM models in Composition-SAC. Importantly, PRI policies are significantly more interpretable than the BiL.TMM policies e.g. Fig. 3 and Fig. 4. The high interpretability of 7-PRL policies in turn leads to strong generalizability to novel environments because of the inductive bias implicitly encoded in the policy's interpretable
"oode available https: //gt thub. com /RU- Aut ooated--teeeeeooooo Rea son nn-grgup/////o pppppp
7

---

Published as a conference paper at ICLR 2022
Art Cross Maze
And Random Goal
IChostan Hurdle
Possher
1.0
0.4
6.0
<2P
Chu0re THATT Caape
Ehdiooment Chape
TRPO
PPO
(a) Comparison with baselines for group one environments. Results are averaged over 10 random seeds.
32
38
62-
117
HIO
AJM1
(b) Comparison with baselines for group two environments. Results are averaged over 5 random seeds.
Figure 7: Comparison results against baselines. The y-axis records the agent's distance towards its goal normalized by the agent initial distance from the goal so values close to 1 or higher show failures.
Performance
Convergence
Depth
Environment
T-PRI.
Comp-SAC
-PRL
--PRI
Scratch
(max 6)
Ant Cross Maze
0.10:10.06
0.11=0005
5.0
3.0
4.0
4.75
Ant Random Goal
0.14+:0.04
0.12+00.02
4.0
5.30
HalfCheetah Hurdle
0.03
0.43++0.22
0.5
0.0
1.0
3.10
Pusher
0.09++0.05
0.16++0.06
0.2
0.1
0.35
3.50
Table 1: Performance and convergence comparison for group one environments averaged over 10 random seeds. The performance section compares the mean normalized final distances to goals of extracted programs T-PRL with standard deviations; the convergence section compares averaged numbers of environment steps (in millions) until convergence for policy architecture search π² -PRL, policy extraction T-PRL, and training program on the same architecture as π- T-PRL from scratch. The depth section shows mean abstract syntax tree depth of extracted 7-PRL programs.
representation, e.g. if-then-else conditions used to drive the Ant to different regions on a maze. We show more examples about the interpretability and generalizability of r-RRL in Appendix and
In Table 1, we also show the number environment steps needed until convergence for policy ar- chitecture search x -RRL, extraction -PRL and training a programmatic policy using the same architecture -PLL from scratch. Except Ant Cross Maze, the sample efficiency of policy architec- ture search and extraction combined is better than learning a single program from scratch. Intuitively, this is because n -PRI. is essentially space. The better data efficiency of our method compared to enumerating all possible programs to perform RL for each highlights the merits of jointly optimizing policy architectures and parameters.
peramaaraeteri model of the optimal policy in the search
Programmatic High-level Planning. To the second group of the benchmarks, we apply the high- level planning algorithm in Sec. 4 to learn hierarchically programmatic RL policies, denoted as --HPRL programs. Our baselines include model-free Hierarchical RL method HIRO (Nachum al., 2018) and a model-based high-level planning method A-AVI (Jothimurugan et al., 2021). All algorithms run under the same setting to reach a given target, which is fixed for each environment. Fig. 7b depicts the mean learning performance terms of the agent's final distance from targets over 5 random seeds. The π HPRRL programs are more stable, outperform the baselines, and uniquely solve the Ant Push and Ant Fall environments. We show the success rates of each algorithm in Appendix G.2. Fig. 7b shows that HIRO gets stuck in local optimums. Unlike -HHPRL HIRO is model-free and does not know the structure of the abstract state space, so is unable to discover the path from the initial region to the goal region. A-AVI performs worse than 7-HPRL because does not decouple model- based high-level planning and model construction. 7-HPRL more sample efficient it decomposes task into multiple simpler sub tasks with explicit sub goals to
8

---

Published as a conference paper at ICLR 2022
T-Affine
n -Ensem
n --Esem
'²' -Ensem
T-Oracle
Environment
Distance
Distance
d
Distance
d
Distance
Distance
Ant Cross Maze
0.87=0.03
0.10=0.06
4.2
0.10=0.06
4.8
0.07=0.05
5.6
0.3
Ant Random Goal
0.95+00.06
0.16+00.03
4.4
0.14+0.00
5.3
0.15
5.2
0.42++0.22
HalfCheetah Hurdle
0.57+00113
0.03++0.01
3.1
0.03+
3.1
0.04=0.02
2.6
0.67++0.24
Pusher
0.36++0.05
0.08
3.0
0.09+00.05
3.5
0.10
0.04
4.0
0.26+0.17
Table 2: Ablation study on different configurations of our algorithm. T-Affine denotes a non- compositional programmatic policy with affine controllers (the depth bound of its program derivation tree is set to 6). π -deppt--Ensmm represents compositional program with primitive ensembles learned by setting the corresponding program derivation tree depth bound. π-oracle denotes a policy learned by imitating its oracle (Verma et al., 2018). d shows mcan abstract syntax tree depth of learned policies. The mean normalized final distances goals are averaged over random seeds.
reach in an optimal high-level plan. First, since the high-level plan is in accordance with the primitive specifications, a sub goal is easy to achieve by utilizing the corresponding primitives. Second, the training procedure can be guided by dense distance-based rewards to the sub goal. Therefore, training for each sub task converges extremely fast well in advance of the expiration of the training budget allocated to the sub task, causing the ladder-shape convergence curves in Fig. 7b.
Ablation Study. We investigate the impact of compositionality in our algorithm. For the first group of our benchmarks, we apply our algorithm synthesize programs in the DSL in Fig. 1 that switch back and forth between a set of affine controllers under different conditions. Table shows that these programs perform much worse than the composite programs, which highlights the merits of composition. We additionally study the effect of the depth bound on a program derivation tree for policy architecture search. We set the depth bound performance of the synthesized policies is not sensitive to these settings, Our algorithm converges to similar architectures as it strives to assign the highest probability to the architecture that maximizes cumulative RL reward. Convergence curves of all the ablated versions are depicted in Appendix B.
6, respectively. Table 2 shows that the final
Table 2 also reports the performance comparison between our oracle-free programmatic RL algorithm with an oracle-guided baseline (Verma et al., 2018). The baseline learns programmatic policies that imitate the neural Compositional-SAC policies in Table To ensure fair comparison, we relax the semantics of these programs to be continuous as well. The results show that the performance of the distilled programs is worse than that of their oracles and our policies. Since the neural oracles and programs reside in very different policy architecture spaces, the program that best imitates an oracle is not necessarily a performant programmatic policy. Comparison results with other oracle- based programmatic RL baselines can be found in Appendix C.
RELATED WORK AND CONCLUSION
Existing programmatic RL methods mostly train a programmatic policy to imitate a pretrained RL oracle. They synthesize policies by enumerating a set of templates in the form of decision trees (Bastani et al., 2018; Silver et al., 2020), finite state machines (Inala et al., 2020), or program sketches (Verma et al., 2018; 2019). However, imitation-based approaches suffer from nontrivial distillation gap as the distillation process can yield suboptimal policies. Our approach optimizes programmatic polices in continuous relaxation of the con-differentiable architecture space solely using reward signals by policy-gradient methods. Trivedi et al. (2021) first learns a smooth program embedding space and then searches over the embedding space synthesize a program. Our approach differs as we do not need to prepare a dataset of programs to train the program embedding space, thus more suitable when sampling such a dataset challenging. Yang et al. (2021) uses MaxSAT solver to synthesize straight-line programs to guide a policy to reach goal. Our method is more suitable when there are multiple goals for which architecture synthesis is necessary to learn conditional branches to reach different goals. We discuss other related work in broader contexts in Appendix. E.
Conclusion. We present a novel programmatically interpretable and compositional RL framework. Our method jointly learns policy parameters and policy architectures in a continuous relaxation of the non-differentiable program architecture space via policy- selly-ggraientttt methods. Our RL framework leverages compositionality in programming languages to integrate primitive functions into composite program to solve novel RL problems. Experiment results demonstrate that it excels in discovering compositional RL. programs with optimal architectures and strong interpretability.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We have included instructions to reproduce our results in the supplementary material. The code of this work is available at https: /ttp:://ggttt////// com/RU Ressonnntt pi-PRL.
Reasoning- Group/
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their comments and suggestions. This work supported by NSF Award #CCF-2124155 and NSF Award #CCF-2007799.
REFERENCES
David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup. and Michael Littman. Value preserving state-action abstractions. In Silvia Chiappa and Roberto Calandra (eds.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy), volume 108 of Proceedings of Machine Learning Research, pp. 1639-1650. PMLR, 2020. URL http::/troceeediinneee htt.::ssww..ppr.ss.emmmmmmmeee abel20a html.
mlr. wwwpppressvvveee
Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
Karl Johan Áström and Tore Hägglund. Automatic tuning of simple regulators with specifications on phase and amplitude margins. Autom., 2065)645-651, 1984, doi: (016/0005-1008884499000000
URL https: //w.ooooo//ooooooo..oo worgor/// 10. 1016 00066/00000-110 1098 (84) 90014-1.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Satinder P. Singh and Shaul Markovitch (eds.), Proceedings of the Thirty-First AAAI Conference on Artificial Intelli- gence, February 4-9, 2017, San Francisco, California, USA, pp. 1726-1734. AAAI Press, 2017.
URL http: org/ ocs/ winiinixxx.. Bonddx..pp/AAaee AAAIITAAITIII http////papp///////e////a
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deep- coder: Learning to write programs. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: opwnrevieweeeeeeeeeoeeeee.eoee.m net wwweeeeeouueeeeeeeeeeeeeeeeeeeee ottpe//ww..eeeoouuoooo.opa/oaoaa
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL https: /ttp://///cccceeceeeeeeoo neurips cc/paper//01eee 2018/file/ e6d8545das
Paper pdf.
Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htttps://pennevieww.r /
forum? d= Xw62RZZ.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), October 2019a.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul. Korea (South). October 27 November 2. 2019, pp. 1294- 1303. IEEE, 2019b. doi: 10.1 109//CCV.20190000 ICCV 2019 9..19.00 00138.
URL ht ///oi.//////////ooo/ /ttp::////ooo/o/////////// 1109/
Xinyun Chen, Chang Liu, and Dawn Song. Execution- guided neural program synthesis. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA. May 6-9, 2019. OpenReview.net, 2019c. URL https://openreviii net net/forum?id H1 1lgffiAqym..
10

---

Published as a conference paper at ICLR 2022
Guofeng Cui and He Zhu. Differentiable synthesis of program architectures. In -hitty-Fifth Confer- ence on Neural Information Processing Systems, 2021. URL https::/ net/
Forum?id=ivxdl XXXXXM..
Leonardo Mendonça de Moura and Nikolaj Bjørner. Z3: an efficient SMT solver. In C. R. Ra- makrishnan and Jakob Rehof (eds.), Tools and Algorithms for the Construction and Analysis of Systems, 14th International Conference, TACAS 2008, Held as Part of the Joint European Conferences on Theory and Pructice of Software, ETAPS 2008, Budapest, Hungary, March 29- April 6, 2008. Proceedings, volume 4963 of Lecture Notes in Computer Science, pp. 337-340. Springer, 2008. doi: 10. 100779977-3 0080-000-77--333 24. URL https: /ttp owt.i.orgg/00 1007/
978-3- 978-3-540-788 500-550077800-00 24.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-1 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 990-998.10 PMLR, 2017. URL http:/ http://pcoceccessceeeeees.c mlr .prsss/ v70/devlin17 html.
Kevin Ellis, Maxwell I. Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with REPL. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bus Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 9165-9174, 2019. URL https: /ttp://e///ccceeeigggee nwwrips......e cc/ htc/paper/2013 9/hash/ -aa.:07ttttaaaaaatattt.......... html.
Kevin Bllis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke B. Hewitt, Luc Cary, Armando LezamaL and Joshua B. Tenenbaum. Dreamcoder: bootstrapping inductive program synthesis with wake-sleep library learning. In Stephen N. Freund and Eran Yahav (eds.), PLDI '21: 42nd ACM SIGPLAN International Conference
Programming Language
Design and Implementation, Virtual Event, Canada, June 20-25, 202 1, pp. 835-850 ACM, 2021. 3454080.
doi: 10.1145/34534883.4544000 URL https: //:://dooo //oi/oiiioo/// org/ 10.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without reward function. In 7th International Conference on Learning Representationss ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL net / forum? 1d- J3 JRqEm.
https://cpenreviil
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.). Computer Vision ECCV 2020 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Purt XVI, volume 12361 of Lecture 01178883-30--851717
Notes in Computer Science, pp. 544 560. Springer, 2020. doi: 10.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference machine learning, pp. 1861-1870. PMLR, 2018
Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, and Manzil Zaheer. Latent programmer: Discrete latent codes for program synthesis. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 4308 4318. PMLR, 2021. URL http:////// / http///roeeeen..ceeee mmlr. press/sssseeeee v199/ / htt.hhon2la... html.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automata theory, lan- guages, and computation, 3rd Edition. Pearson international edition, Aidison-Wesled 2007. ISBN
978-0-321-47617-33
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:tt/////......t //tp:ss////pprevrtt net forum? d=s1 d= BONNDD.

---

Published as a conference paper at ICLR 2022
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL httpp:://ppeneeeeeeettt net/forund id= ddrrkeyy855e
Yufan Jiang, Chi Hu, Tong Xiao, Chunliang Zhang, and Jingbo Zhu. Improved differentiable architecture search for language modeling and named entity recognition. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 3576-3581, 2019.
Kishor Jothimurugan, Osbert Bastani, and Rajeev Alur. Abstract value iteration for hicrarchical reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 1162-1170. PMLR, 2021.
Youngwoon Lee, Shao-Hua Sun, Sriram Somasundaram, Edward S. Hu, and Joseph J. Lim. Compos- ing complex skills by learning transition policies. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. Open 2019. URL https: http:///peeeeeeeeeeeeeee/eeeeeee net / forum? id de rygrBBC5t...
Youngwoon Lee, Jingyun Yang, and Joseph J. Lim. Learning to coordinate manipulation skills via skill behavior diversification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: // //openrevis ew net wttf//oordddrreree Bt.... Btvv.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European conference computer vision (ECCV), pp. 19-34, 2018.
Chenxi Liu, Liang-Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L.. Yuille, and Li Fei-Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019b. URL S1eXHoC5FX.
net wwtp::/weweeeet.ni..ee.o. fformmiddmd
Vijayaraghavan Murali, Letao Qi. Swarat Chaudhuri, and Chris Jermaine. Neural sketch learning for conditional program generation. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver; BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: openeeview...ee net/ wwwimmmidxdiii Abb.
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchi- cal reinforcement learning. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 31: Anmual Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 3307-3317, 2018. URL
www.eediiinnnnnnnsssoeeeeeeeeeee neurips ec/ paper/2018 hash/ Abbttraat. html.
e (5347714417722222cfffeeeeee
Ofrr Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal representation learning for hierarchical reinforcement learning. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:
//openreview.
Maxwell I. Nye, Luke B. Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4861 4871- PMLR, 2019. URL http: htttt:://proceedii ngs ml wwwpprrsssvvv... v97 nyel 9a html.
12

---

Published as a conference paper at ICLR 2022
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. BUSTLE: upttom-up program synthesis through comming-guided exploration. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https: /owenrevevvveeeeee ew. net/ forum? dd
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: / wwwp/eeeeeeeeeeee////pp.....e.we net.
cex.
Xue Bin Peng, Michael Chang, Grace Zhang, Pieter Abbeel, and Sergey Levine. MCP: learning composable hierarchical control with multiplicative compositional policies. In Hanna M. Wal- lach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Bor Buc, Emily B. Fox, and Roman Garnett (eds.). Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canuda, pp.
2019. URL htwps: /twp//e/oooeeeeeeeeeooocoocceeec ngs. nerrips. www.iisscccpppeoo -bstraactcbbatttttcccaaa html.
Ahmed Hussain Qureshi, Jacob J. Johnson, Yuzhe Qin, Taylor Henderson, Byron Boots, and Michael C. Yip. Composing task-agnostic policies with deep reinforcement learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: https///ppppeeveeeeeee net forum?id- H1 ez FF.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized evolution for image classifier architecture search. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu. Hawaii, USA, January 27- February 1. 2019, pp. 4780 AAAI Press, 2019. doi: 10.1609/aaai. 33111..31.00033333787733
Melrose Roderick, Christopher Grimm, and Stefanie Tellex Deep abstract q-networks. In Elisabeth André, Sven Koenig, Mehdi Dastani, and Gita Sukthankar (eds.), Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pp. 131-138, International Foundation for Au- tonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018 URL http: SiEmmiddd337400
//dl. acm. orgg eet/ciiaaiion
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
Tom Silver, Kelsey R. Allen, Alex K. Lew, Leslie Pack Kaelbling, and Josh Tenenbaum. Few- shot bayesian imitation learning with logical program policies. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirly-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 10251-10258. AAAI Press, 2020. URL https: //aaa///aaaaa.// wtwgg//jaaaj....... index. www.inwwwwpppepiieeeeeeeeeeppe phpppppppaaa.a/ AAAI/ article/viee 6587.
Shao-Hur Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph J. Lim. Neural program synthesis from diverse demonstration videos. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmüssann Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 4797- 4806. PMLR, 2018. URL http:/ http:://pocceeeieeee mlr. pwwppressseeee v880/ w00/sunneei sun Ba. html.
Yonglong Tian, Andrew Luo, Xingyuan Sun, Kevin Ellis, William T. Freeman, Joshua B. Tenenbaum, and Jiajun Wu. Learning infer and execute 3d shape programs. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: http:///pppeeiiieeeeeee net/ /t///foree forum?irmeeee wecummiddrrp d=ry NH20qFQ.
13

---

Published as a conference paper at ICLR 2022
Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J Lim. Learning synthesize programs as interpretable and generalizable policies. In A. Beygekimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:// openreview n forum? d= 9twkexC3..
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmääsaan Stockholm. Sweden, July 10-15, 2018, volume 80 of Proceedings of Ma- chine Learning Research, pp. 5052-5061, PMLR, 2018. URL http:::/ppocceeingss.... mlr. press/v8t /v/0///0///// 2e10/veealBBB/0 html.
Abhinav Verma, Hoang Minh Le, Yisong Yue, and Swarat Chaudhuri. Imitation-projected pro- grammatic reinforcement learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 15726-15737, 2019. URL https: htteepp:/ppoceeddie http///proeeeeeeeeeeeeee neuripe httppssccpppppppe wttppppee//11....ppppppoo 9/hash/ 5a44a53b7d2 www.eee44b222222. Bcc.e/edbcbbbbbbceccee-- html.
Alexander Vezhnevets, Volodymyr Mnih, Simon Osindero, Alex Graves, Oriol Vinyals, John P. Agapiou, and Koray Kavukeuoglu. Strategic attentive writer for learning macro-actions In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Gar- nett (eds.), Advances Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3486-3494, 2016. URL c4492cbe 90 0rt.:ecc000....laaaae6e666eeeeee Abb.aaaaaaaeeee---aaaaaaatt..... html.
wtwp:r/rwweeeiio......e..ee.e.ee nwwrips....... wttpcc//paae (papex/2016/haar/
Ruochen Wang, Minhao Cheng. Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsieh. Rethink- ing architecture selection in differentiable NAS. In 9th International Conference on Learning Representations, ICIR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
John Winder, Stephanie Milani, Matthew Landen, Erebus Oh, Shane Parr, Shawn Squire, Marie desJardins, and Cynthia Matuszek. Planning with abstract learned models while learning transferable subtasks. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAA/ 2020, New York, NY, USA, February 7-12, 2020, pp. 9992-10000. AAAI Press, 2020. URL https: aaaii. org/ ojs/ / www.i.nnp//iiiiiiieiimmppp http://AA//aaticeeeeeeeee
6555.
Glynn Winskel. The formal semantics of programming languages - an introduction. Foundation of computing series. MIT Press, 1993. ISBN 978-0-26--233169955
Yichen Yang, Jeevana Priya Inala, Osbert Bastani, Yewen Pu, Armando Solar-Lezama. and Martin Rinard. Program synthesis guided reinforcement learning for partially observed environments. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:/ /oppnreveeeeeeeeee/ee / QwNLVId9Df.
net / forum? 1id=
Yiyang Zhao, Linnan Wang, Yuandong Tian, Rodrigo Fonseca, and Tian Guo. Few-shot neural architecture search. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12707-12718. 18. PMLR, 2021.
Feng Zheng, Qing-Guo Wang, and Tong Heng Lee. On the design of multivariable PID controllers via LMI approach. Autom., 38(3):517-526 2002. doi: 10.1016/50005- 1098(00)00 URL
https: //ts://doo: /oi. .rgg 10. 0000111//000110000 (01) 00237-0.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with learned garbage collector. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicold Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 31: Anmual Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. wtw.ooeeeeddinn....nne.eee...eee neurips..r....... .ccossccc/pee wttpc//pppppee wwtpppppp///111///// 2e001//hahh// / f- f-Abstract. html.
2018 URL
14

---

Published as a conference paper at ICLR 2022
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. In 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net,201
15

---

Published as a conference paper at ICLR 2022
A TRAINING ALGORITHM PSEUDOCODE
A.1 THE PROGRAMMATIC REINFORCEMENT LEARNING ALGORITIIM
We depict the pseudocode of our oracle-free programmatic reinforcement learning algorithm in Algorithm I. The algorithm builds program derivation tree that involves programs whose abstract syntax tree depth is bounded by a hyperparameter d. We encode a program derivation tree differentiable program Th... with architecture weight w and policy parameters 0. Recall the surrogate objective definition in Eq. (2):
T (8, TT
Joss wisd (6, w) = Erpppp aa "i aidd
AnT Oas, (s, a) Pas
(s, a))
is an estimator of the advantage function over finite batch of samples from B Wals where A-T mau and Oold. Wold are policy architecture weights and parameters before policy update.
In the pseudocode, training steps (3) for learning 0 and (4) for learning w are alternated across training iterations until reward convergence. They can be approximately solved using the efficient conjugate gradient algorithm, after making a linear approximation to the objective and quadratic approximation to the constraint (Schulman et al., 2015). Upon convergence, based on architecture weights, we obtain discrete program architecture from T replacing each tree node containing multiple architectures with the most likely architecture parameters in the chosen architecture using RL (Schulman et al., 2015) until convergence from the parameter values learned by the search process.
top-down manner. Finally, we train the
Algorithm Programmatic Reinforcement Learning without Oracles
Require: Policy Context-free grammar E,, depth bound d, KL-divergence limit Ensure: Synthesized programmatic policy
T + Program Derivation. Tree (E.d)
> T expresses all programs whose abstract syntax tree depth is bounded by d
Th. + encode (T)
b To. as differentiable program with parameters 0 and architecture weights w that encodes T iinitialize (0, w)
On, wo randomly.initialize
for = 0, 0,1,2..... M do
Policy architecture search
0x+1 arg max, Jor. (0, wk) DKL (n (-1s)
s.t. BE-P-T kiin
T To (-1))) 0
Per Eq. (3)
Wk+1 = arg max Jentime (0K+1, W)
s.t. Exmp.T P.
D 0 (-18)
x 1 (11)) s
D Per Eq. (4)
end for
+ extract (IT mate)
b Extract single program based on architecture weights w The extracted policy inherits parameters from trained THT wnM Train the chosen architecture
6g + 8₁
for 0, 0,1,2,.... N do
Dx+1 arg maxg (0)
s.t. ExNPEns DKe
Te (1s)) 5
end for return na
A.2 THE PROGRAMMATIC HIGH-LEVEL PLANNING
The pseudocode the synthesis algorithm for HRL policies is depicted Algorithm 2. The goal is to synthesize high-level control plan the abstract model using abstract actions PPcc constraints. An abstract action is specified together with a guard (Pauadd that encodes the condition under which high-level plan of a fixed number
the action can occur. Suppose for now that are searching
16

---

Published as a conference paper at ICLR 2022
k of absttacc action steps reach the goal state Poua from the initial state Piint
Pini (o yn)
m A PGuard (24-1, Vi Zis Me. m;-1)) A
(6)
1=1 (Tk, ya)
Constraint (6) can be solved by off-the-shelf constraint satisfiability solvers e-g. 73 (de Moura & Bjørner, 2008). We incrementally search for longer and longer and increasing until the optimal high-
high-level plans, starting from level plan solution is found. A solved high-level plan is sequence of sub-tasks: (3(2o. Mo). Tı, (11,, B1)), (3(21. v1), T2, 3(22, /2) (8)))....,((E (f(#k-1.36 9k-1), Th, B( yk)) where extract the intermediate high-level goals 21, f/...........................f F1..1.......11111. #k-1- from the solution of the statisfiability solver, and the concretization function 3 converts abstract states back to concrete goals on the unabstracted environment for the agent successively achieve. For example, the solved high-level plan for Ant D-Maze navigation is depicted in Fig. 6c. For each sub-task i that starts we learn a new low-level policy क, that drives the agent to reach states in ((z,, 31). The states of when reaching (2,, yi) serve as the initial states for training .- Notice that we do not directly use primitive functions Ti, because oftentimes low-level policies need to compose primitive functions using different weights under different environment conditions to achieve a sub-task, e.g. Ant turning around a corner with different poses and velocities while contacting walls in the process. We therefore learn each low-level policy π, as programmatic ensemble policy composing primitive functions using the technique in Sec. and distance-based rewards. This ensures that our HRL policies are interpretable at both high level and low level.
=
from set of initial states (1,
Algorithm 2 Programmatic High-Level Planning
Require: Primitive Specifications Pact, abstract Action Guard (Guards abstract initial Pinit and goal Pgaal time-step limit I' for the execution of cach low-level policy
Ensure: A high-level plan model, and its low-level policies To, T1. for l ..2,..., M do Φ PPni (Fo: yo) Ni (PAa(E)--1 M1-1 Fs. vi) A (Cmmmi Yc Iú. vi))
Tk-1
D High-level policy planning
Per Eq. (5)
model + solve (Φx)
model f None then
V Iz,
Ni, Vi mase model[y:]
> A high-level control plan is synthesized
Break
else if k == M then Return "Failed"
end if end for
for i
k 1o
Low-level policy learning b Reward based on distance to sub goal (z,, yi)
R; < Xs, a.
dist(s, (I,, ys))
n; arg maxx, E
Dd 7" (.(s).a))
Ng (To.... -T- 1). (ap.))))) N..
Apply Algorithm to learn low-level programmatic policy m
> The initial state so is sampled as the last state observed by ni-1
end for
return model, (No, Th, Tk
B MORE ABLATION STUDY RESULTS
Our first ablation study investigates the impact of compositionality on our algorithm. Fig. shows the ablation study results comparing different strategies, i.e., learning programmatic ensemble policy, learning programmatic affine policy, and learning a deep neural network policy using TRPO (Schulman al., 2015). A programmatic affine policy monolithic program in our DSL (Fig. 1)
17

---

Published as a conference paper at ICLR 2022
Maze
Art Random Coal
HalfCheetah Hurdle
Pusher
2.
3.0
10-
www.w/
08-
0.5
0.6
0.4
0.4
94-
0.3
00
STrES
Enviforment strps
ensifonment strpe
Ensermate
Amii
TRPO
Figure 8: Ablation study on the importance of compositionality, Results are averaged over random seeds. The y-axis records the agent's 's distance towards its goal. We normalize the distances to final goal by the agent initial distance from the goal so values close to or higher show failures.
Hurdle
3.0
1.0
1.6
3.0
9'-
1.0
Deach
Depth
Digthh
Figure 9: Ablation study on the impact of the depth bound of a program derivation tree. Results are averaged over 10 random seeds. The y-axis records the agent's s distance towards its goal. We normalize the distances to final goal by the agent initial distance from the goal so values close to 1 or higher show failures.
that switches back and forth between a set of affine controllers under different enviromment conditions. The result shows that our programmatic ensemble policies significantly outperform the other two representations in all group one environments, which highlights the merits of composition. Notice that in the HalfCheetah Hurdle and Pusher environments, the programmatic affine policies significantly outperform the neural network policies.
Our second ablation study investigates the impact of the depth bound of a program derivation tree on the performance of our algorithm. Fig. 9 shows the ablation study result about using different depth bounds on program derivation trees and compares the mean normalized final distances to goals of learned policies with standard deviations (averaged over 10 random seeds). Specifically, we compare program derivation trees with depths of 5, 6 and 7. The result demonstrates that the training performance is not sensitive to these depth bounds. The algorithm converges to architectures with similar performance. Table additionally shows that the structures of the converged architectures are also similar. This suggests that if the user does not know how complex programmatic policy should be a priori, the user can simply set a large tree-depth bound and let the learning algorithm assign the highest probability to the architecture that leads to program maximizing cumulative RL reward.
C COMPARISON WITH ORACLE-GUIDE PROGRAMMATIC RL
One of our main contributions is direct programmatic policy search. Existing oracle-guided pro- grammatic RL algorithms suffer from a nontrivial distillation gap as the distillation process can yield suboptimal programmatic policies whose reward performance is significantly worse than that of their oracles. This is because oracles (e.g. neural policies) and programs may reside in very different policy structure spaces. Due to the structural constraints, the program that best imitates an oracle is not necessarily performant programmatic policy, or could even be much worse than the optimal program in the search space. To address this limitation, we propose programmatic RL solely based reward signals without using any oracles. This allows the synthesis algorithm to search for optimal programs in the programmatic policy space. We compare our programmatic RL algorithm with oracle-based programmatic RL algorithms that learn policies in the form of programs
18

---

Published as a conference paper at ICLR 2022
Oracle-guided Programs
Oracle-free
Environment
Neural Oracles
Decision Trees
RI. Programs
Reacher
-5.01
-5.79
-4.79
-5.05
Walker2d
4752
3672
1714
5178
Hopper
3634
1646
2995
3535
HalfCheetah
14627
3569
2810
10773
Ant
5786
4875
3504
5680
Swimmer
335
335
334
340
Bipeda/Walker
287
273
252
274
Pendulum
-146
-146
-149
-144
Table 3: Comparison between our programmatic RL algorithm with oracle-based programmatic RL algorithms that learn policies the form of programs (using the same DSL as ours) (Verma et al., 2018) and decision trees (Bastani et al., 2018) Mujoco/Open environments. Neural oracles and our programmatic policies were trained using million environment steps and we report the averaged final reward performance of three repeated experiments.
(using the same DSL ours) (Verma et al., 2018) and decision trees (Bastani et al., 2018). In Table 3, we report results on Mujoco/OpenAl envirouments where programmatic policies invoke a set of affine controllers under different environmental conditions. To ensure a fair comparison, semantics of oracle-guided RI. programs to be continuous as well but decision trees remain discrete. Neural oracles for Walker2d, Hopper, HalfCheetah, and Ant were trained with SAC (Haarnoja et al., 2018) using 3 million environment steps. Neural oracles for Reacher, Swimmer, BipedalWalker, and Pendulum were trained with TRPO (Schulman al., 2015) using million environment steps and we report the averaged final reward performance of three repeated experiments.
relax the
The reward performance of our oracle-free programmatic RL policies is comparable neural network policies. Due to the distillation gap, the oracle- gulieeguudd RL programs Icarned by the baselines perform worse than their oracles and our policies. We also tried the -projeece-- programmatic RI. algorithm (Verma et al., 2019) that optimizes a programmatic policy by taking mirror gradient descent policy space with a mix of neural and programmatic representations, which enables deep policy gradient approaches programmatic policies. However, own implementation of the algorithm in the mixed policy space does not lead to significant policy improvement compared with (Verma et al., 2018).
We further compare our algorithm with Verma et al. (2018) on the environments reported in Sec. According to results in Fig. 7a, these environments are best solved using policies that invoke set of ensemble controllers. We report the mean normalized final distances to goals of learned policies with standard deviations. The neural oracles were trained by Compositional-SS. 2020). Table 2 demonstrates that the oracle-guided RL programs (T--Oaale) are again suboptimal due to the distillation gap. Especially, they do not work well in environments with multiple goals. For example, we found that although on Ant Cross Maze the neural compositional-SAal works well, the success rate reaching the goal (6, -6) higher than reaching the other goals. The bias is amplified in the oracle-guided programmatic RL policy. When the goal is at (12, 0), the agent sometimes mistakenly goes somewhere near (6, -6).
(Qureshi et al.,
policy in general
The above two sets of experiments demonstrate that our oracle-free programmatic RL overcomes the suboptimality induced by oracle-guided programmatic RL.
D DSLS WITHOUT LOOPS
Our loop-free programmatic policies can already produce repetitive behaviors when necessary. This because policies are always executed in feedback loop with RL. environments. At each iteration, environment states encountered by repetitive behaviors would repeatedly activate or be matched to the same if-then-else conditions and therefore trigger alike actions. To support this argument, we evaluated our tool on two environments from Inala et al. (2020): Car and QuadPO. Both environments need policies that capture repeating behaviors. For Car, the goal is to drive a car out a parking spot to adjacent lane while avoiding collisions. For QuadPO, the goal is to maneuver a 2D quadcopter through an obstacle course by controlling its vertical acceleration. The training and test distributions varied to evaluate whether policies can produce arbitrary number of repetitions. For example,
19

---

Published as a conference paper at ICLR 2022
Environments
TRPO NN
TRPO Programmatic Affine Policy
Car
82.6%
100%
QuadPO
69.6%
85.6%
Table 4: Comparison between our programmatic affine policies with neural network policies both learned based on TRPO agent (Schulman et al., 2015). The training and test distributions are varied to evaluate whether policies can produce an arbitrary number of repetitions. We report the results on test distributions by measuring the fraction of rollouts (out of 500) that safely reach the goal.
on QuadPO, the obstacle course length is doubled during testing. Table summarizes the results on test distributions by measuring the fraction of rollouts (out of 500) that safely reach the goal.
Our loop-free programmatic policies generalize better than neural policies on the test distributions. We did not compare our policies with the state-machine policies (Inala al., 2020) as its implementation is not available.
Moreover, our tool indeed supports loops in a program that sequentially processes history of environment states and actions. For example, our DSL allows controller C' to be expanded as a discretized, multivariable PID controller in Fig. 1. In Appendix K.2, such a PID controller is formalized based on the higher-order combinator fold that acts over a fixed-sized window on history observations. We could alternatively add fold(f, directly to the DSL to search policies that combine the results of recursively processing each past observation in a history h to build up return action (the body of the combining operation ff can also be synthesized).
E ADDITIONAL RELATED WORK
Compositional Reinforcement Learning. To improve RL efficiency, a line of research that trans- fers past skills into new skills for solving new complex problems has emerged. Lee et al. (2019; 2020) learn high-level polices to select the previously trained primitive policies. The macro-action models (Vezhnevets et al., 2016) similarly learn a high-level planner to combine actions sequences from primitives. These methods activate only one policy at each timestep. Other works have explored simultaneously composing multiple task-agnostic primitive skills by learning assign weights for action composition (Peng et al., 2019; Qureshi et al., 2020). Hierarchical reinforcement learning, such as option-critie (Bacon et al., 2017). is also promising approach to solve complex tasks, However, option-critic is prone to inefficient task decomposition. Nachum et al. (2018) address this issue by automatically decomposing a complex task into subtasks and solving them by optimizing the subtask objectives. As opposed to these efforts, our method learns high-level and low-level policies that are both interpretable. Our technique can integrate any primitive skills diverse enough to complete a task and is orthogonal to automatic skill discovery methods e.g. (Eysenbach et al., 2019).
Differentiable Architecture Search. Neural architecture search has emerged as a promising ap- proach to automate deep learning applications (Zoph & Le, 2017: Liu et al., 2018; Real et al., 2019). Particularly, our program architecture synthesis algorithm is inspired by DARTS (Liu et al., 2019b). This method uses composition of softmaxes over all possible candidate operations between fixed set of neural network nodes to relax the neural architecture search space in a super-network, and uses approximate gradient descent to iteratively train the weights and parameters of the super-network. It then selects the optimal architecture based on the weights. Various methods further improve architecture search efficiency, accuracy and applicability (Chen al., 2019a; Guo et al., 2020; Zhao et al., 2021; Wang et al., 2021; Cui & Zhu, 2021; Jiang et al., 2019; Liu et al., 2019a). However, none of these methods has performed differentiable architecture search in a reinforeement learning context or considered leveraging symbolic logical abstractions for hierarchical architecture synthesis.
Neural Program Synthesis. Neural program synthesis involves learning neural networks to predict function distributions to guide synthesizer e.g. DeepCoder (Balog et al., 2017), or generate program autoregressively in an end-to-end fashion e.g. (Sun et al., 2018; Parisotto et al., 2017; Bunel et al., 2018) and RobustFill (Devlin et al., 2017). BUSTLE (Odena et al., 2021) uses bottom-up search that allows the model to prioritize and combine small programs that solve different subtasks. SKETCHADAPT (Nye et al., 2019) first generates program sketch with holes, and then fills the holes using a conventional synthesizer. BAYOU (Murali et al., 2018) infers a different form of program sketches that abstract names and operations by their type. DreamCoder (Ellis al., 2021)
20

---

Published as a conference paper at ICLR 2022
Models Program derivation tree Programmatic policy (depth 6)
Ant Cross Maze
Ant Random Goal
Pusher
Cheetah Hurdle
0,0023s
0.0023s
0.0014s
0.0014s
0,0019s
0.0019s
0.0009s
0.0009s
Bidirectional LSTM
0.0034s
0.0033s
0.0022s
0.0021s
Table 5: The average running time of over 10000 random executions of program derivation trees, single programmatic policies, and Bidirectional LSTM models (Qureshi al., 2020).
iteratively builds sketches using progressively more complicated primitives though a wake-sleep algorithm. Latent Programmer (Hong al., 2021) considers two-level search for program synthesis, in which the synthesizer first generates plan sequence of symbols, in other words discrete latent code from input/output examples by discrete autoencoders, that describes the desired program at high level, and then generates the program in the target language. These methods avoid enumerating every possible program, which is prohibitively expensive for large program spaces.
There is also line of work that deals with learning to process partial programs in addition to the specification. In execution- execution-guided program synthesis, the model guides iterative expansions of partial program until matching one is found. Zohar & Wolf (2018) process intermediate values of a program using a neural network for search direction prioritization for a small, straight-line DSL. Ellis et al. (2019) allow values of whole and ground programs encountered during bottom-up search to be used to prioritize the search in an actor-critic framework. Similarly, Chen et al. (2019c) exploit intermediate values while synthesizing a program via top-down fashion using neural encoder-decoder model. Tian et al. (2019) exploit the differentiability of a rendering process to train a program generating policy and generalize it beyond the training distribution via gradient- fine-tuning.
F IMPLEMENTATION DETAILS
In this section, we present implementation details including the optimization of [F](), primitive policies, symbolic inputs and reward structures of each environment, and hyperparameters of rein- forcement learning algorithms.
F.1 COMPUTATIONAL COMPLEXITY OF PROGRAM DERIVATION TREE EXECUTION
We compare the computational complexity of [E] (where d 6) with that of the deepest single program in [E](.) and that of the Bidirectional LSTM-based model used by the Compositional SAC baseline (Qureshi al., 2020) as follows. We report the average running time of over 10000 random executions of the three models in Table 5.
In implementation, the run-time execution of program derivation tree is optimized follows. As depicted in Fig. 5, primitive policies are invoked multiple times by various programs embedded a program derivation tree. Since the input any primitive always the current environment state, it suffices to call each primitive just once and use its result anywhere it is invoked in the tree policy. Table shows that this simple optimization could enable us to run our algorithm as fast as the Compositional SAC baseline that does not perform any architecture search.
More importantly, we do not need explicitly enumerate and execute programs up to some depth for each state evaluated during an episode. Fig. shows that we allow the exponential number of programs program derivation tree to share computation (similar to weight sharing in DARTS) intermediate results computed by shallower program be reused by deeper program.
For more complex DSLs with a large number of production rules, we could optimize the architecture search procedure by applying a strategy similar to Progressive DARTS (Chen et al., 2019b). This strategy gradually increases tree depth d during search while dropping the search directions leading to lowest- weighttd programs at the previous stage from the program derivation tree. Such progressive procedure would allow our algorithm to deeply explore the architecture space even when & is large, which is left for future work.
21

---

Published as a conference paper at ICLR 2022
F.2 PRIMITIVE POLICIES DETAILS
In all reinforcement learning tasks, require multiple primitive skills policies to compose higher- level programs. Since primitive policies are obtained for completing dedicated tasks, e.g., navigating the ant agent move up, pushing down the object in the Pusher environment, it is unnecessary to include targets information in high-level tasks into their observation space during training. All primitive skills policies are obtained using SAC algorithm (Haarnoja al., 2018) implemented in OpenAl Spinning Up RL framework (Achiam, 2018).
Ant. For standard-torque and low-torque ant, we train two sets of four basic primitive policies, i.e., UP, DOWN, LEFT and RIGHT for 1 million steps for each. The reward function to acquire above four primitives defined as:
Fant Co Udirection + T(IsHealthy) ||a||2 12 eg - |II
where Udirection is the velocity of given direction, (IIHeallthy) is Boolean function that determines the health condition the agent, action a is a 8-dimension vector, and feontact a vector that encodes the contact force of the agent. In order train UP and DOWN primitives, Udirection t should track velocities on tr-axis; similarly, to train LEFT and RIGHT policies, we should set Udirection Byy keep track of velocities along dyy-axis. Coefficients Cos Cha Ca and oy are to be 1, 0.5, 5 x 10-4, respectively.
The Pusher environment requires two skills: PUSH-DOWN and PUSH-LEFT used to manipulate the object to move down and left, and both of them are trained for 0.5 million steps. The reward function to acquire these two primitives is defined as:
Pusher.
Tpusher Gp Udirection Ca ||al|2
where Udbrection denotes the object's velocity projected on DOWN (negative y-axis) or LEFT (positive ar-axis), and is the action. Coefficients co and ca are set to be and 0.1, respectively.
HalfCheetah. In HalfCheetah Hurdle environment, two simple policies JUMP and FORWARD are trained for 0.5 million steps, and they sufficient to compose the program and solve the task. The reward function can be defined as:
The Cu. Ufooward + Coy V/uump Ca ||al|2
(9)
where oooraard and Ujump velocities projected forward (æ-axis) and jump (y-axis) directions, and a is the action. In order to train FORWARD policy, coefficients Crys Cay are set to be and O; for policy JUMP, cost coefficient which set to be 0.1.
coefficients Cry 0.05 and Cv 1, respectively. Coefficient e, is the control
Note that for Ant and HalfCheetah Hurdle environment, primitive policies are trained in blank environment without any obstacle so that they can move freely.
F.3 PROGRAM INPUTS
For low-torque ant, we consider its current position z, y, distance from current position to the starting point [|z, 21 and the angle between current direction to the x-axis arctan " as symbolic inputs. For standard-torque ant, besides the above inputs, we also take the goal position G.. Gy for navigation, since goals in environments which utilize the standard ant are randomly sampled. In the HalfCheetah Hurdle environment, the position of the next hurdle Hnext and the distance from HalfCheetah" 's back foot to next hurdle [Bbakk- Hnentl are considered. For the simple pusher task, we use distance from origin to the object ||oobj Yobj 2 and to the robotic Farm, Darm l symbolic inputs.
22

---

Published as a conference paper at ICLR 2022
Figure 10: Navigation and manip- ulation benchmarks that require agents reach or move the object to the given targets (represented by a red circle for pusher and by green spheres for the rest). Addi- tionally, Ant Cross Maze and Ant O-Maze are depicted in Fig. 2 and Fig. 6a respectively. In all ant environments, the definitions of up, down, left, right, and for- ward moving towards posi- tive/negative x/y axes directions, respectively.
(a) Ant Random Goal
(b) Pusher
HalfCheetah Hurdle
(d) Ant Push
(e) Ant Fall
F.4 ENVIRONMENT DETAILS
F.4.1 ANT ENVIRONMENTS
The standard-torque Ant environments include Ant Cross Maze and Ant Random Goal environ- ments. In these environments, a MuloCo quadruped ant with 150 units torque limit is required to start from origin and reach the random given targets. The radius of the goals are and 0.25, respectively, Specifically, the goal of Ant Cross Maze is randomly sampled from one of three positions: (6, 6), (12, 0) and (6, -6) each time; and the goals in Ant Random Goal is a random position within circle with radius of 5. In ant environments, the reward function is defined as:
Fant rl Cdistance (ca llPant - Proat II2) + ch [(IHeealthy)
(10)
Ca ||a||2 cs 1 |cootttctl
where Pont (Fent: Yont) and Proot = (T Bgoot) are positions of ant and the given targets, ([sHeell)hy) is Boolean function that determines the health condition of the agent, action is vector, and Scontact is a vector denotes the contact force. Coefficients Cdistances Cd. Cha Ca and cy are set to be 1, 5, 0.05, 0.01 and 0.001, respectively.
Additionally, we consider three challenging low-torque MuloCo Ant environments with weak distance-based reward signals. Compared standard-torque, the low-torque ant has the force range [-30, 30). Since smaller force exerted on joints, the ant moves slower and suitable for intricate HRL tasks. Specifically,, distance from the goal so values close to I or higher show failure. Greedily following this kind of reward signals does lead to solving the problems as these environments are in complex shapes.
normalize the distances a fixed final goal by the agent initial
In the Ant D-Maze environment, we place the Ant in a D-shaped maze for a navigation task. The agent is trained reach the farthest end of the maze located (0, 19). In the Ant Push environment, the moveable block is at (0, 8), and the goal is at (0, 19). In the Ant Fall environment, the movable block at (8, 8) at the same elevation as Ant. Their a rift in the region [-4, 12] [12, 20]. To reach the target the other side of the rift, the Ant must push the block down into the rift, and then step on to get to the goal position. For all three environments, the low-torque Ant starts from the origin, and the radius of goals are set to be 1.
F.4.2 PUSHER ENVIRONMENT
In the Pusher environment, the initial position of the object is randomly sampled from the region [0.3, 1] x [-1, -0.4]. In order to successfully move the object to the given target centered at (-1, 0) with radius of 0.17 using the robotic arm, the distance from arm object, well object goal should be tracked. The reward function for Pusher environment is defined as:
Tpusher2d -Creach |Parm Poby 112 Cmove
|lPobj
Pgoatll2 C. -|all2
(11)
23

---

Published as a conference paper at ICLR 2022
where Parm (aarm Marm), Pobj (Tobj Vobj). and Pooal (Iigoals Vyoat) positions of the robotic arm, object, and the goal. respectively. Coefficient Creach+ Cmooes Ca are set to 0.5, 1, and 0.1, respectively.
F.4.3 HALFCHEETAH HURDLE ENVIRONMENT
In the HalfCheetah Hurdle environment, a MuJoCo halfcheetah required to start from origin and jump three hurdles to reach the target with radius of 1. The reward function is defined as:
Thurdle
Cdistance"
[gool
x + Chardle" (ownt(x)
(12)
+ Gooal'
[[IReechhdd) + Cran Up + Cjump Vy - Ccollision (IICoollided)
where x is cheetah's 's current position, "'gool is target location, cownl(x) function returns the number of hurdles has been passed, [[sReached) is Boolean function that determines the cheetah reach the target, V/ and fy are the projected velocities on z-axis and y-axis, and [(IsCollided) is Boolean function that determines if the cheetah is collision. Coefficient Cdistonces Churdles Cgoats Crun. Cjump and Coollision are set to be 0.1, 1, 1000, 1, 0.3 and 2, respectively.
F.5 HYPERPARAMETERS
Following hyperparameters are used to train primitive policies with SAC (Haarnoja et al., 2018) algorithm.
Discount factor y 0.99.
SGD optimizer; actor learning rate 0.001; critic learning rate 0.001.
Mini-batch size n 100.
Replay buffer of size 100000.
Soft update targets 0.005.
Target update interval and gradient step are set to be 1.
Following hyperparameters are used to train T- 7-PRI, programs for solving tasks in group one environ- ments with TRPO (Schulman al., 2015) algorithm.
Discount factor = 0.99.
Number of trajectories per epoch N 50.
Maximum search depth of program derivation graph D, 6.
KL--Divergence limit 0.01.
GAE = 0.97.
Gumbeel-Softma Temperature =
Following hyperparameters are used to train --HPRL programs for solving tasks in group two environments with TRPO algorithm.
Discount factor 0.995.
Number of trajectories per epoch N 100.
KL--Divergence limit = 0.01.
GAE = 0.97.
Gumbel-Softmax Temperature = 0.25.
Table 6 summarizes the neural network architectures used in reinforcement learning algorithms.
24

---

Published as a conference paper at ICLR 2022
Method
Network Structure
Hidden Units
High-level Policy: Three layer feed forward network
300
HIRO
Low-level Policy: Three layer feed forward network
300
Encoder: Bidirectional RNN with LSTMs
128
Composition-SAl SAC
Decoder: Single layer feed forward network
128
Attention:W Wo, Wa E TRdxd W E IRd
128
TRPO/PPO policy
Two layer feed forward network
256
SAC primitive policy
Two layer feed forward network
256
Table 6: Network Structures.
G IMPLEMENTATION DETAILS OF PROGRAMMATIC HIGH-LEVEL PLANNING
G.1 SPECIFICATIONS FOR HIGH-LEVEL PLANNING
In our experiment, we have applied programmatic high-level planning in Sec. 4 to 3 challenging environments, namely Ant D-Maze (Fig. 6a), Ant Push (Fig. 10d), and Ant Fall (Fig. 10e), that are commonly used to evaluate the effectiveness of hierarchical reinforcement learning. Sec. 4 shows how to perform high-level planning based on the ensemble policy DSL and uses Ant D-Maze as an example. In this section, we apply programmatic high-level planning to solve Ant Push and Ant Fall.
Recall that our method builds an abstract high-level model based on state abstractions provided by domain expert, similar to previous works (Abel et al., 2020; Winder et al., 2020; Jothimurugan et al., 2021). For example, consider the Ant navigation task in a D-shaped maze from Nachum et al. (2018) in Fig. 6a. The abstract states of the task are collected
abstract 2-D gridworld E R N in Fig. 6b. An abstract grid (x. y) E N x N subsumes concrete positions with a known scale where indicates walls and mar y] 0 indicates nagivable spaces. The domain expert can then specify a pair of abstract initial state şPmi (yellow) and goal state &Gao (green). By abstracting away details of the low-level dynamics such as Ant orientation and velocity, a high-level policy over abstract states and actions can efficiently plan over much longer time horizons.
m[a, y]
For Ant Push and Ant Fall, we reuse the same state abstraction as above. We additionally use mma y| = Move to specify that there is a movable block at (x, y). The Ant needs to push away the movable block reach the goal behind in Ant Push or push into a rift and then utilize the block as bridge to get close to the goal on the other side of the rift.
Other than state abstraction, for model-based planning, also abstract over actions to ensure finite high-level model. We directly use action abstractions as provided primitive functions therein the ensemble policy DSL because they abstract low-level agent actions to an abstract space of skills. Our algorithm then leverages abstract action (primitive function) specifications to synthesize a high-level control plan on the abstract high-level model.
Compared to existing model-based HRI. approaches e.g. (Jothimurugan et al., 2021), our algorithm uses abstract actions as specified rather than learned. In the following, we show that with task- agnostic abstract actions (primitive functions), providing these specifications is trivial even for complex high-level planning tasks.
For the Ant Push and Ant Fall environments, the Ant primitives move Ant up Tup down doown left Tgn. and right Trihh- Therefore, the abstract actions move an Ant horizontally, vertically, or diagonally (via composition) one step the abstract model:
Antt.AAt.Psshl Push (Ii-14 1, Wi-1, V/. m+) =
3dx;, dy: 24 x--1 + dx, A Yi = V + dy: A -1 - dz,, dy. <
0
m [ [yi] = Move A p = v; ^ =
Vp. q. m.[lmg
MOVE
m = Move A p = + dz; ^ q = y: dy
m [p
otherwise
Compared to the Ppu definition in Sec. 4, add two parameters m;-1 and m, to the new definition above. This is because an agent action may change its environment. Here m;-1 refers to the old environment before agent action, and m. refers to the environment after the agent
25

---

Published as a conference paper at ICLR 2022
Environment
T T-HRPL.
HIRO
A-AVI
Ant D-Maze
0.06=0.02
64%
0.27+00.04
42%:t.%%
0.18:00.22
77%=88%
Ant Push
0.07=0002
94 94%%8% %
0.19:10.08 0.42:10.08
46%+8%
0.40=#0.08
42%=12%
Ant Fall
0.04
65 % %
35%
0.31
52%:1.%
Table 7: Performance comparison for group two environments averaged over 5 random seeds. The mean normalized final distances to goals and success rates with their standard deviations are reported.
action. For example, for Ant Push, if a movable block is pushed by the Ant, the state abstraction should be updated accordingly reflecting the fact that the space after the movable block in m,-1 holds the block after the push the new environment m,,
We require that an abstract action be specified together with guard @uaadd that encodes the condition under which the action can occur. For Ant Push, the Ant should not walk into walls and the path from an old position to new position should be available. Importantly, if in the high-level plan the Ant pushes the movable block, there should exist space behind the block that allows for the push in the old environment m before the action. Besides, movable block can only be moved vertically or horizontally in the environment.
Puaad Ant Push (Z:- M/- Zz. Ms. mi-1
m [m]]
[3 # A (m;-1 [xt-1] ( [Ms] = 0 m [ = 0) A
m: [x Move m [2 + (I) x1-1)llly + (yr 91-1)] )]
m: [r:][y/ Move
- = V/-1
The abstract action specification for Ant Fall can be defined similarly as follows:
Pct Ant Fall (Tj- 1 V/- Fz. Vi, m1 m,) =
I2 = -;-1 + dr, A Vi V--1 + dy: A -1 S dx;, dy: I 1A
mi- 1 [ui]lv Move p 24 A A yi
m, 1 [x Move m44111111
Rift
34 + dx; A y/: + dy: m Rift
vp, m//pla =
Move
[x:]][]][[]]] Move
p == 34 + dx; A q y/ dy:
m4
[p]|
otherwise
Notice that AacLAam is almost the same as Pact except that we specify that if the Ant pushes movable block into rift, the rift becomes bridge for the Ant to bypass.
PGuard Ant.Fall T y/ Fz De, m
m,
[m]] [y:]
# (m--1 [2, [[v:]] 02 0)
m;-
771
[<:][b]]]]
Move = mi-1 [2 (x; 22-1) (y: y/- 0V
m, m,-1 [2; + (x; [x-1)][u + (3) 1 Rift
M [
Move = x, = ---1 V 1/4 V/-1
Similarly, PGGaardAAm_Fal is almost the same as (Gnaand except that we additionally specify that the Ant can push a movable block either if there is an empty space or a rift behind the block in the old environment before the action.
G.2 DETAILED RESULTS ON HIERARCHICAL RL BENCHMARKS
We show the success rates of applying learning algorithm (Sec. 4), HIRO (Nachum et al., 2018),
and A-AVI (Jothimurugan et al., 2021) in Table
It can be seen that π -HRPLL programs signifiantly outperform both HIRO and A-AVL For example, on the challenging Ant Push environment, our --HPL policy achieves 94% success rate goal reaching far beyond that of HIRO and A-AVI.
26

---

Published as a conference paper at ICLR 2022
H PROGRAM INTERPRETABILITY: ANT CROSS MAZE
In this section, we take one step ahead and show how an Ant Cross Maze program Peross can be interpreted by using both branch activation and also policy strength graphs.
H.1 BRANCH ACTIVATION
In Sec.2, we demonstrate multiple branch activation graphs given different two targets: (6, -6) and (12, 0), and we analyze how they can be explained. Furthermore, When the goal is set to (6, 6). in most areas of the maze, branch one of the Peross is activated (shown in Fig. Iaa and the agent would majorly follow the instruction provided by the branch one. From Fig.3, we can conclude that the semantics of this branch is to navigate the agent to go UP, since the parameter associated with UP primitive policies dominates this branch. Similarly, Fig. b shows that int most upper-half of the given area, branch two activated and it would enforce the agent to go RIGHT.
Branch One Activation
Branch Two Activation
0.5
02
2
(a) Branch activation, (Gz, Gy) = (6, -6)
(b) Branch 2 activation, (Gz, Gy) (6, -6)
Figure 11: Branch activation as functions of Ant position (z, y) for program P Peroee.
H.2 POLICY STRENGTH
Unlike a branch activation graph which informs us how a branch activated, a policy strength graph demonstrates how a specific primitive skill policy is invoked without considering the semantic of any branch, so is suitable for final analysis and interpretation.
Fig.12t and 12b demonstrate the UP policy strength of program Peross given target locations (12, 0) and (6, -6). Presumably, if the agent start from origin (0, 0) and the target is (12, 0), it should move straight up and invoke UP policy. From the Fig. 2a know that the behavior of the program is consistent with our expectation: invoking UP policy throughout its trajectory. Furthermore, if we change the target position to (6, -6), behavior of how the program invokes UP policy (see Fig. 12b) changes accordingly: the strength of UP policy is at a high level in the beginning of the trajectory, then decreases rapidly to prepare for right turn. Therefore. the effect of Peross shows in Fig. 12 can be summarized as: the strength of UP policy could be adjusted according to different target locations, yet it stays at a high level at the beginning of the trajectory.
The goals shown in Fig. 13a and 13b are symmetric. After reaching the central area of the maze using UP policy, the program should navigate the ant make a left right turn by calling LEFT or RIGHT primitive policies, respectively. If the goal is located at (6, 6) (see Fig. 13a), the LEFT policy strength is high after the agent reaches the center of the maze, so it can be pushed and move towards left. When the goal is assigned to (6, -6) on the right side of the maze (see 13b), the RIGHT policy is invoked at a high level after the ant reach the center of the maze, so that the agent will be pushed the LEFT or
to move right. Therefore, the effect of Peross shows in Fig. 13 can be summarized
RIGHT polices strength is at a high level when the ant reaches the center area of maze so it can be navigated to make left right lurn reach the targets.
27

---

Published as a conference paper at ICLR 2022
Up Policy Strength
Up Policy Strength
(a) UP policy strength, (G., Gy) (12, 0)
(b) UP policy strength, (G., G2) = -6)
Figure 12: UP policy strength of Ant Cross Maze program P Peross
10 Policy Strangth
Right Policy Strength
12
67
02
(a) LEFT policy strength, (G., Gy) = (6, 6)
(b) RIGHT policy strength, (Gr, Gry = (6, -6)
Figure 13: LEFT and RIGHT policy strength of Ant Cross Maze program P Peross.
I PROGRAM INTERPRETABILITY. MORE EXAMPLES
In this section, we demonstrate more examples of programs and their branch activation and policy strength graphs for interpretation.
I.1 ANT RANDOM GOAL PROGRAM
Fig. 14 demonstrates the expression of the program Prandom for solving Ant Random Goal environ- ment. The pre-defined function input X' takes symbolic states include current position along with the randomly sampled target location Gz, Gy. Also, vector of distribution of weights of primitive policies can be found on each terminal branch.
Fig. 15 shows the branch activation of the first three branches. The figures clearly demonstrate that when the goal is set to be (G.. Gyy = (-3, -3), roughly only branch one is activated in the needed areas, so the behavior of the agent is dominantly determined by the semantic of branch one. Since the second and fourth values in the policy distribution vector in branch one nearly equally dominate the branch, the expected behavior of this branch can be summarized as: go RIGHT and go DOWN the same time.
Fig. 1a and 16b demonstrate the DOWN and RIGHT policy strength program Prandom given origin (0, 0) and target location (-3, -3), respectively. In the figures, the x-axis and y-axis reflect the current position of the agent. The output of Prandom
vector that contains strength of each primitive skill policy and we are interested in the strength DOWN and RIGIIT primitive policies in this case. Presumably, if the goal position is (-3, -3) and the ant starts from (0, 0), the simplest path for ant is to move diagonally along with southeast direction, and surely this requires DOWN and RIGHT primitive policies, and each them is likely to contribute equally. From Fig. 16 we know that with this program P Prandoms when the agent moves southeast, the contribution of DOWN and
28

---

Published as a conference paper at ICLR 2022
if (0), + . > 0)
then (0% Tup(s) + 51% TTowN(s) + 0% M.FFT (s) 49% [R]GhT(s)
else (02_ + xx 0)
then (3% Tur(s) + 0% TT)wN(ss + 97% (T) + 0% TRIGHT(s)
else if (Os. 0g X 0)
then (82% (s)(s) 15% mnoww(>) + 0% (5) + +3 TRIGHT( (s)
else (78% (sp(s) + 0% TDoWN + 0% TLET(()) )) + 22% TRIGHT (s)
X [ x, V, Ga, Gy, arwtar ", ||,,,111, 5/12
0.00199,00800) 0.080 J, 81. =-2.05 [ 0.899, 0.397, 00899, 00.394 -0.019,
02 = [ [0.222. 1.679, 0.111, 1.468. -0.107, 0.297 1. 02. =-3.798
0g = [ 0.895,0.1990 1.290, 2.43, -2.667 2.378 1, Os. = -22226
Figure 14: An Ant Random Goal program P Prandom powered by four primitive skill policies: Tup(s); TDOWN(s) (s) and TR) Program input X' includes current Ant position 2, V. target goal Gr. Py. arctan 2 and | yll2-
Branch Activation
Branch Two Activation
Branch Three Activation
(a) Branch activation
(b) Branch 2 activation
(c) Branch 3 activation
Figure 15: Branch activation of an Ant Random Goal program Prondoms (gz, 9yy = (-3,-3).
RIGHT are roughly the same, and this is consistent with expectation. Therefore, the effect of this program can be summarized as: if the agent is required to move southeast (0, 0) to (-3, -3), assign DOWN and RIGHT equally at roughly 50 percent of strength.
1.2 PUSHER PROGRAM
17 demonstrates program P Ppusher with three branches for solving Pusher environment. The program input X' takes symbolic states Tobjy Yohjs Farm: Form as inputs, then computes [[abt Mobiily ||aam, yarm ll to decide which branch of weight cell take.
From Fig. 18a we can conclude that, only the first branch is activated the whole possible situations. Such activation values for branch demonstrate that the possibility cutting other branches in the program without hurting the performance of the graph too much. Also, it suggests that a smaller value of maximum depth of program derivation graph is sufficient for searching a program solve this task. Also, the distribution of primitive policies in this branch shows that: the agent needs more PUSH DOWN policy than PUSH-LEFT policy move the object to the target location.
Furthermore, F8g.18 demonstrates TUSH-DOWN and PUSH-LEFT policy strength of the program Prusher- Unlike Ant Cross Maze or Ant Random Goal environment, the goal of pusher environment is at a fixed location. From Fig. 18b we can conclude that: when the object is faraway from the origin, i.e. close to the goal, PUSH-DOWN policy strength is at a relatively lower level, compared to at higher level when the object is far from the goal position. Also, we can summarize the effect of how the program invoke PUSH-LEFT primitive policy from Fig. when the object is too close to the origin, the PUSH-LEFT policy strength is at lower level, and if the object is close the goal, the PUSH-LEFT policy strength is at a higher level. In general, the above behavior of PUSH-LEFT can be explained if we consider velocities in both and y axes: if we want to acquire policy which
29

---

Published as a conference paper at ICLR 2022
(a) DOWN policy strength
(b) RIGHT policy strength
Figure 16: DOWN and RIGHT policy strength of program P Prandom, (Gz, Gy) (-3, -3).
if (01, + of X > 0)
then ( 74% DOWN (8) 26% TUUSHLEFT(S)
else if (02. + 03 X > 0)
then 99% NowN (s) + 1% TrUsH
else 99% TrUSH (8) + 1% (FUSHLEF((S)
[obj. Mony l1.. || Harmll 2|
0 1.370, 0.621 J. 01. = 5.041
02
1.252, 8.100 1.101], O2. = 3.426
Figure 17: A Pusher program P Puucher powered by two primitive skill policies: TRUSH-DOWN (s) and LEUS Program input X' includes norms over Tobj. Yobj and Tarms yarm
push the object at a constant tangential velocity all the way to the goal, we may need to adjust the distribution of PUSH-LEFT and PUSH-DOWN in order to get reasonable combination of velocity in both X and y axes.
1.3 HALFCHEETAH HURDLE PROGRAM
According to our experiments when applying x- PRL algorithm to HalfCheetah Hurdle environment, the program derivation graph is inclined to select a program with few branches. fact, a simple HalfCheetah Hurdle program Phe with only one branch (shown in 19g. is able to solve the task with high performance and success rate.
An example of such program can be written 95% #FORWARD 5% TJUMP(S). In this simple program, the input is not even used, this means the agent invokes each primitive policy at fixed rate. The success of such simple combination of two primitive skill policies tells us, if program is powered by appropriate low-level primitive policies, we may solve a RL task in a much simpler way.
J POLICY GENERALIZABILITY
In our experience, the high interpretability of learned programmatic policies leads strong generaliz- ability of the policies to novel environments.
J.1 ANT No MAZE
We consider applying the programmatic policy Peross for Ant Cross Maze to an environment with randomly sampled target positions far beyond the three possible goals in the original environment. Our goal is to test if the programmatic policy has learned how to perform goal navigation. Since a new target position can quite different than the three goals in Ant Cross Maze, we remove all the walls from the environment the Ant can navigate freely. Fig.20s and 20b depicts the UP and
30

---

Published as a conference paper at ICLR 2022
Branch Activation
Push Down Palicy Stooagh
Left Policy Streggth
ORTANDS
C14
C50
PALL TANCE
(a) Branch 1 Activation
(b) PUSHI-DOWN policy strength
(c) PUSH-LLFFT policy strength
Figure 18: Branch activation and policy strength graph of a pusher program P Ppuseer-
95% #FORWARD(S) 5% STUMP(S)
X = [ Hnexxt: bback
Hnext
Figure 19: A HalfCheetah Hurdle program Pho powered by two primitive skill policies: #FORWARD(s) and Ts)MP()). Program input X' includes the position of the next hurdle Hneat and the distance from HalfCheetah's 's back foot to next hurdle Tback - Hneztl. The program Phe shown is special program which does not contain any if if-then-else structure, i.c., there exists fixed strength of invoking each primitive policy.
RIGHT policy strength if we set the goal to (14, -8), i.c., the upper-right corner Fig. 20c and 20d shows the UP and LEFT policy strength if we set the goal to (14, 8), i.e the upper-left corner. Peross can successfully drive the Ant to these positions. From these policy strength figures we can conclude that P Peross successfully detects the change of goals and weighs UP and associated RIGHT or LEFT policies in appropriate areas to navigate the ant to reach the goals.
Up Policy Strength
Right Palicy Strength
30
12
35
35
03
81
(a) UP policy strength, goal (14, -8)
(b) RIGHT policy strength, goal (14, -8)
Up Policy Strength
Laft Policy Strangth
12
10
30
81
(c) UP policy strength, goal (14, 8)
(d) LEFT policy strength, goal (14, 8)
Figure 20: UP, RIGHT and LEFT policy strength of a transferred program Perose
31

---

Published as a conference paper at ICLR 2022
Goal Radius
Peross
Comp-SAC
1.0
0.16:10.04
0.28=0008
1.5
0.13:10.03
0.26==0.06
2.0
0.10
0.23
Table 8: Comparison results of policy generalizability in Ant Reshaped Maze environment (Fig. 21). We set multiple goal radius 1.0 (the original radius in Ant Cross Maze), 1.5, and 2.0. Normalized final distances to goals reported as the average over 50 random executions.
J.2 ANT RESHAPED MAZE
Furthermore, we consider a reshaped cross maze with three different goals: (8, 8), (14, 0), (8, -8) (represented by blue spheres in 21..21). The shapes and positions of walls have also been changed and adapted to new possible goals accordingly. This novel environment Ant Reshaped Maze similar to Ant Cross Maze environment in many ways, e.g. they both have three possible goals, their goals are symmetric, etc.
We directly apply Peross to Ant Reshaped Maze and com- pare the generalizability of Peross with the BiLSTM policy learned in the Ant Cross Maze environment well using
Figure 21: Ant Reshaped Maze
Composition-SAC (Qureshi et al., 2020). We compare with Composition-SAl because the two policies both learn to compose primtivie skills to adapt to new complex behavior. However, Peross is more interpretable than BiLSTM model. Table 8 shows that Peross successfully realizes the change of the three goals and drive the Ant the novel environment with 0.16 normalized distance the new goals. In constrast, the Composition-SAl -AAC policy does not solve the novel environment well. We further increase the original radius goals to 1.5 and 2 in the novel environment, both Peross and the Composition-SAC policy get close to goals with P Perose continuing to perform much better.
K
AFFINE POLICIES AND PID POLICIES
K.1
AFFINE POLICIES
The DSL for affine policies implements a controller C as affine transformations in Fig. 1:
Cafine
0- 0 X 1
where 0 E (g | 0g E 12t0 are control parameters. Particularly, Cafine can be as simple as some (learned) constants 0..
For example, consider the continuous OpenAl Gym MountainCar environment in Fig. 22a. A car on one-dimensional track, positioned between "mountains". The goal is drive up the mountain on the right. Because the car's 's engine is not strong enough, a policy has to drive the car back and forth to build up momentum in multiple passes. The reward greater if the policy spends less energy to reach the goal.
learned programmatic policy to control the continuous MountainCar environment is given Fig. 23. Fig. 22b depicts the activation of branch 1 in the program as a function of (position, velocity). The degree of activation (yellow) is close to on almost all states under with speed velocity greater than O. The logic of the program is then obvious policy accelerates the forth to drive the car forward: when ever the car speed is less than O, the policy accelerates the forth to drive the backward. Indeed, this helps drive the car back and forth to build up momentum. The policy succeeds reaching the goal and receives cumulative reward greater than the threshold 90 all experienced episodes.
when ever the speed is greater than 0, the
32

---

Published as a conference paper at ICLR 2022
0.08
0.06
velochty
-..02
(a) MountainCar Gym Environment
(h) MountainCar Branch Activation
Figure 22: Continuous MountainCar Example. In the branch activation graph, yellow region indicates the area of states on which the control signal in branch is activated.
if 01. + of X then 0.92 Branch 1 else 0.95 +- Branch
X [ position, velocity ] [0.1, 128.1 01. 0.88
Figure 23: A MountainCar program with two branches. Program input X' includes current car position and velocity.
K.2
PID POLICIES
The DSL for PID policies implements a controller C discretized, multivariable PID function in Fig. 1:
Crn == PIDop.0,,0p (c, h, 8) 0
where 8p, 01, 0D R parameters representing the proportional gain, integral gain, and derivative gain matrices of PID control. Notice that a PID controller additionally takes a known constant that represents fixed target for the controller stabilize the system under control around, and histroy a sequence states before the current control step. The semantics the controller follows:
PID p. 0, 0p [r, h, 8) -0p P 0, 7 0+0 D where fold(+, h) D peek -1)
(13)
P P= (c-ss
In the semantics definition, P is the proportional term, / is the discrete approximation of the integral term (calculated via a fold), and D the finite-difference approximation of the derivative term. In line with the standard integral error reset strategy (Aström & Hägglund, 1984), the fold function acts over fixed-sized window on the history (e.g. the five latest states of the history). peek(h, 1) returns the most resent state in a history h.
For example, consider the OpenAI Gym Pendulum environment in Fig. 24a. The pendulum swingup problem is classic problem in the control literature. The pendulum starts in random position, and the goal to swing it up so it stays upright. The state space include w that is the angle the pendulum makes with the vertical and the angular velocity W. However, the observation exposed to policy for this task is (cos(w), sin(w), w). Since the goal is to stablise the pendulum upright, the fixed goal e for PID controller for this task is [1,
(i.e. [cos(w) = 1, sin(w:
à -]).
learned programmatic policy to control the pendulum environment is given in Fig. 25. Fig. 24b function of (w, w). The degree of activation (yellow) is close to on all states where the PID controller in branch would be applied to. Accordingly, the large constant control signal in branch 2 would be applied states within the blue
depicts the activation of branch in the program
33

---

Published as a conference paper at ICLR 2022
(a) Pendulum Gym Environment
(b) Pendulum Branch Activation
Pendulum Example. In the branch activation graph, yellow region indicates the area of states on which the control signal branch activated.
Figure 24:
if 11 Of X
then PIDor.d 000.00 0n (1.00 (1.0000,4,s)
44,) < Branch
else 2.39 k- Branch
co)(ww), sin(w), W
0: = 2.57, 2.18, 0.71 01. = 0.94
0P 9.28, 1.04, 1.71 I 0, 1- 0.26, 157,0.14 On [ 2.03, -0.48 J²
Figure 25: A pendulum program with two branches. In the system, the angle the pendulum makes with the vertical. Program input X' includes cos(w), sin(w),
region. The logic of the program is then obvious - when ever the pendulum is hanging or downwards close + -T, the policy applies the large (constant) control action in branch 2 to push the pendulum to an area in which it is easy for the PID controller in branch to eventually stabilise 2m. The policy succeeds all experienced episodes. In
the pendulum upright at 0, 2m,, experience, we found that it is impossible to train single PID controller to solve the task. The programmatic policy in turn uses large control action push the pendulum where the PID controller is able to function.
Experiment Results of Learning Affine and PID Policies. We have applied the learning algorithm in Sec. 3 to the popular benchmark suite MuJoCo. This benchmark suite consists of multiple locomotion tasks with 2D and 3D agents. Table demonstrates that our results on Humanoid-v3 and LunarLander-v2 are competitive with state-of- thetherrt RL algorithms (trained using 3 million environment steps). More results were given in Table 3.
π R-RP
SAC
PPO
Environment
stoc
mean
stoc
mean
stoc
Humanoid-v3
5207
5737
5488
5521
1340
1912
279
279
279
102
Table 9: We compare the final episode reward of our programmatic policies --RPL with that of SAC (Haarnoja et al., 2018) and PPO (Schulman et al., 2017) agents on Humanoid-v3 and LunarLander-ve We report the averaged results of three repeated experiments where "stoe" refers to Gaussian policy with actions sampled from it, while "mean" refers to using mean of the policy, LumnraLander(conntiuuus)) controlled by a discretized, multivariable PID program.
34


Reviews:
[{"review_id": "wEUz_WcoI2O", "reviewer": "Reviewer_xiEe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## **Paper Strengths**\n\n- **Clarity:** The paper is pretty clear wrt the high-level topic and what the high-level intuitions are. This is good, because I think some low-level parts of the paper could be clearer (see weaknesses section). Figure 3 is also a great and clear figure, and therefore should be referenced in the \"Ensemble Policies\" subsection of section 2.\n- **Experiments:** Comparing against the HRL style of environments such as the Ant mazes and HalfCheetah hurdle is nice, and serves as a nice comparison (although not direct because the abstractions provided are very different) to existing deep RL HRL algorithms. Furthermore, the authors evaluate over 10 random seeds, and include learning curves (not always given for these types of program RL papers), which is very thorough.\n- **Method**: This continuous relaxation of the discrete program search tree is neat and intuitive, and serves as a contribution in the program synthesis for RL space.\n- **Motivation**: The motivation is nice, to generate interpretable/stable policies for RL by synthesizing programs which can act as the agent in environments. Part of the novelty here is the continuous relaxation, which makes the program search more feasible.\n- **Comprehensive Appendix:** The appendix has some solid extra analysis along with example programs for each of the tasks. \n\n## **Paper Weaknesses**\n\n- **Clarity:** I think section 2 can be made a little clearer to people not familiar with the program synthesis domain by introducing examples earlier (e.g. giving a clear example immediately after \"production rules X → \\sigma_1, \\sigma_2,....or nonterminals\"). $\\phi_{Act}$ could be better defined by first defining $dx_i$, $dy_i$, and using underbraces with text or having an extra sentence explaining it. It took me more time than it should've to parse. Furthermore, I think there should be an algorithm pseudocode box where all stages of training the method for the different versions of the method are detailed, this would make it clearer how exactly the method works (it can be hard to keep track of high-level details when reading a long method section that goes over all individual parts). Finally, your graphs don't have axis labels (Figure 8).\n- **Method:** Seems to me that the tree structure is essentially decided beforehand. Essentially one would have to decide how complex the program is a priori, and then learn via policy optimization what the weights of that program tree are. This seems somewhat limiting to me, but in one sense perhaps acts as a hyperparameter that regularizes the policy structure. Could the authors do an ablation study on this with extra analysis?\n- **Abstractions:** Having abstractions for Program Synthesis is perfectly reasonable, and even more reasonable in the case of this HRL-style of RL program synthesis. But is $\\phi_{\\text{Guard}}$ necessary? It seems like a pretty restrictive assumption to me, and would be interesting to see how well the model-based HRL version of the algorithm can work without this guard.\n- **Misc:** \"The high interpretability of π-PRL policies in turn leads to strong generalizability to novel environments.\" → The connection between interpretability and generalizability in novel environments is not well explained. Do the authors mean the inductive biases of the program structure enforced by the fact that these have to be simple, interpretable policies?\n- **Missing related work:** This is not that big of a deal as both of these papers are recent on arXiv (2021). But authors should cite [1] and [2], and compare/contrast with them in the related works and intro section. But I believe that both of these don't require RL oracles, so perhaps a bit more nuance is needed in the intro/abstract/related work describing the contribution of this paper.\n- **Experiments:** In light of the above complaint, I think that generally the experiments lack solid analysis in the main paper. Especially in the high level planning experiments, the authors should explain why they believe HIRO gets stuck where \\pi-HPRL does not, why \\pi-HPRL is more sample efficient, etc. Furthermore, I think an ablation study on tree depth would be illuminating (mentioned in method weaknesses).\n- **Baselines**: Can the authors compare to a program RL baseline? Some of the cited works in the related works should work fine, for example the cited Verma works, the cited Bastani/Silver decision tree papers, or [2]? Even if the specific DSL here won't work with them, or they require teacher policies, this type of comparison would elucidate where some of \\pi-PRL/HPRL's advantages come from (the DSL? the program structure? the search procedure? the continuous relaxation? the lack of needing a teacher oracle??).\n\n## **Questions**\n\n- Being not familiar with Composition-SAC, why Composition-SAC instead of just regular SAC?\n- \"The $\\pi^\\Tau-$PRL models exhibit less data-efficiency than the Composition-SAC policies in part due to the use of TRPO.\" Why not use off-policy RL for the method then?\n\n## Minor Issues\n\n- Page 2: \"defined for each DSL constructs\" → each DSL construct\n- Page 4: \"u_e contain more than one architecture\" → u_e contains\n- Page 7: \"primitives e.g. Ant turning around at a corner. We\" → \"primitives, e.g. Ant turning around a corner, we learn a ...\"\n- Page 7: \"Expect pusher\" → \"Except pusher\"\n- Although our DSLs are simple, the expressiveness is equivalent\nto previous interpretable RL works (Bastani et al., 2018; Verma et al., 2018; 2019) → in light of [1] this sentence may need to be reworded\n\n[1] Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J. Lim. Learning to Synthesize Programs as Interpretable and Generalizable Policies. 2021.\n\n[2] Yichen Yang, Jeevana Priya Inala, Osbert Bastani, Yewen Pu, Armando Solar-Lezama, Martin Rinard. Program Synthesis Guided Reinforcement Learning. 2021.\n\n", "summary_of_the_paper": "This paper presents a method for synthesizing programs to solve MDPs without the need for teacher oracle policies by proposing a continuous program search relaxation that allows synthesizing performant programs as policies.\n", "summary_of_the_review": "In summary, I like the high level idea and motivations of this paper. The method is also seemingly novel and performs well. But there are some issues with detail clarity, experiments and analysis, and a comparison to similar baselines. I am currently voting for rejection, but will happily change my score and/or be responsive to authors during the review process as these concerns are addressed.\n\n\nUPDATE: Score has been revised after discussion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eGHx3eJpZQS", "reviewer": "Reviewer_iSsz", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 idea of using a differentiable version of a DSL to allow for gradient-based optimization is clever and elegant. I understand that the authors were inspired by methods used to learn neural network architectures such as DARTs. The application to the synthesis of programmatic policies is non-trivial and interesting, thus worthy of publication. \n\nHowever, I have a two concerns with the paper.\n\nThe first concern is minor. Why is the title of the paper \"Programmatic Reinforcement Learning Without Oracles\"? In my opinion, the main contribution of the work and that makes it interesting is the differentiable approximation of the DSL that allows one to perform gradient methods to search over the originally discrete space of programs. Learning without an oracle can also be achieved without the differentiable approximation. For example, if the problem domains were discrete, one could use an enumeration procedure similar to what NDS does without the Bayesian optimization step [1]. \n\nMoreover, the need of having an oracle isn't necessarily a major hurdle. If an oracle was available how would the proposed method compare with other methods such as NDS [1] and Propel [2]? I am wondering if the main advantage of the proposed method is that it doesn't require an oracle for training or if it is able to more quickly find an effective programmatic policy in the large space induced by the DSL. \n\nThe second concern I have is regarding the computational complexity of equation defining $\\[E\\](s)$. The equation is recursive and resolving the value of the equation is equivalent to traversing the tree of programs. This computation can be prohibitive depending on the DSL and on the size of the program that needs to be synthesized. That is, we need to enumerate all programs up to some depth for each state evaluated during an episode! \n\nI understand that the complexity of $\\[E\\](s)$ doesn't involve gathering samples from the environment, but it has a non-negligible computational complexity that isn't even mentioned in the paper (I apologize if I missed a discussion about the complexity of $\\[E\\](s)$). What happens if the x-axis of the plots is given in running time? Will the method proposed in the paper be much slower than other competing methods? \n\nThe following could be better explained in the paper:\n\n1) Why encode the tree program as a Gaussian distribution? \n2) rho isn't defined in Equation 2. \n3) Explain that the action the tree program returns is given by the evaluation of the root of the tree with the [E](s) equation. \n\nReferences\n\n[1] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. Proceedings of the 35th International Conference on Machine Learning, ICML 2018.\n\n[2] Abhinav Verma, Hoang Minh Le, Yisong Yue, and Swarat Chaudhuri. Imitation-projected programmatic reinforcement learning. Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019\n", "summary_of_the_paper": "This paper presents a novel method for synthesizing programmatic policies. The code idea of the method is to define a relaxed and differentiable version of the domain-specific language (DSL) used to encode the programmatic policies. \n\nThe program space the DSL induces can be described as a program of the DSL itself. Since the program defines a differentiable space, one can use policy gradient methods to search in the space of programs by assigning higher probabilities to production rules that maximize the expected rewards. \n\nThe search for programmatic policies happens in two steps. The first step applies a policy gradient method to optimize the probabilities defining the program space. Then, one can extract the most likely program structure from the search space by greedily choosing the production rules with higher probabilities. The resulting program is further optimized with reinforcement learning. \n\nEmpirical results on continuous control problems show the advantages of the method. ", "summary_of_the_review": "The paper presents a novel and interesting approach to synthesizing programmatic policies that uses a differentiable approximation of a domain-specific language for policies. This differentiable DSL allows for the use of policy gradient methods to search over the space of programs. The main weakness of the method is the computational complexity required to compute the action of the policy during training. The method iterates through all programs one can synthesize in the DSL up to a given depth. The computational complexity of the policy isn't even mentioned in the paper and it can be a show-stopper depending on the DSL and on the size of the program that needs to be synthesized. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FxrfgZDskzE", "reviewer": "Reviewer_R2Gf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Paper strengths and contributions\n\n**Motivation**\n- Exploring using programmatic policies structured in more interpretable representations to yield better interpretability compared to deep RL policies is promising.\n- The idea of conducting a program search on a differentiable architecture space with policy gradient is novel and convincing. This paper presents an effective way to implement this idea.\n\n**Technical contribution**\n- Relaxing the discrete program architecture search space to be continuous allows for optimizing the program architecture and the parameters of program modules using policy gradient methods.\n- To the best of my knowledge, leveraging pre-defined/pre-learned primitive program functions (i.e. ensemble policies) to tackle hierarchical RL problems in the field of programmatic RL is novel.\n- Using specified state transition behavior of the abstract actions in HRL training seems effective, especially when simple, task-agnostic skills is available\n\n**Clarity**\n\nThe overall writing is clear. The authors utilize figures well to illustrate the presented ideas. Figure 5 clearly shows the idea of the Program Derivation Tree and how it creates differentiable architecture spaces.\n\n**Experimental results**\n- The presentation of the experimental results is clear and the discussion is sufficient and mostly convincing.\n- The experimental results show that the proposed method outperforms or achieves competitive performance compared to RL baselines such as HIRO, TRPO, PPO.\n\n**Reproducibility**\n\nThe code is provided, which helps understand the details of the proposed framework.\n\n## Paper weaknesses and questions\n\n**DSLs without Loops**\n\nThe paper simply states that the loops are omitted in this work. Yet, describing many desired behaviors involves loops/repetitive behaviors. I would like to hear the authors' opinions on how the proposed framework can deal with such behavior.\n\n**PRL baselines**\n\nThe paper only compares with non-programmatic RL methods. \nIt would be more informative to compare the proposed method against the PRL works (such as \"[Verifiable reinforcement learning via policy extraction](https://arxiv.org/abs/1805.08328)\", \"[Synthesizing Programmatic Policies that Inductively Generalize](https://openreview.net/forum?id=S1l8oANFDH)\", etc.), even they require training RL oracles first, which should not be a critical assumption given the tasks considered in this work. With these comparisons, it would be easier to justify how well the proposed method can perform. Or, it would be even greater to show what suboptimality is induced by learning from RL oracles so that it would make this work more convincing.\n\n**Figure 8b: the ladder-shape convergence curves**\n\nDo authors have a good intuition on why the convergence curves of the proposed method presented in Figure 8b look like that?\n\n**Related work: PRL work that does not use RL oracles**\n\nWhile I am well aware of the fact that arXiv papers do not count as publications, it would be great if the authors can distinguish this paper from a recent work (\"[Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://arxiv.org/abs/2108.13643)\") that also tackles learning a programmatic policy purely from rewards. (This suggestion does not affect my evaluation of this paper.)\n\n**Related work: program synthesis**\n\nDiscussing prior works in program synthesis, whose aim is to synthesize programs to fulfill some specifications, would make the related work section more comprehensive. Some relevant works include:\n- RobustFill: Neural Program Learning under Noisy I/O\n- DeepCoder: Learning to Write Programs\n- Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis\n- Execution-Guided Neural Program Synthesis\n- Neural Program Synthesis from Diverse Demonstration Videos \n- Learning to Infer and Execute 3D Shape Programs\n- Latent Programmer: Discrete Latent Codes for Program Synthesis\t\n\n**The proposed method without compositionality**\n\nThe effectiveness of compositionality is not fully justified since no experiment with the proposed method without ensemble policies is presented.\n\n**Decreased interpretability with the transformation**\n\nWhile the differentiable architecture space is mentioned as a strength of the paper, it requires affine transformation for conditions in if-else statements, which decreases the interpretability of the program in complex environments and makes it difficult to be interpreted by non-expert users.\n\n**Code**\n\nPlease include a requirement.txt specifying the versions of all the dependencies. I have encountered many issues when trying to reproduce the results.\n\n## Other metrics\n\n### Relevance and significance\nSolid contributions to a relevant problem\n\n### Novelty\nSeveral novel and surprising contributions\n\n### Technical quality\nTechnically adequate for its area, solid results\n\n### Experimental evaluation\nInsufficient or lacking evaluation in 1-2 criteria, but sufficient w.r.t. the other criteria\n\n### Clarity\nVery clear, only minor flaws.", "summary_of_the_paper": "This paper addresses the problem of the low efficiency of program search guided by a pre-trained oracle or on discrete and non-differentiable architecture space. To this end, the paper proposes a framework that performs program architecture search on top of a differentiable relaxation of the architecture space. This allows the program architectures and parameters to be learned via policy-gradient methods without RL oracle. The proposed method also exploits compositionality by allowing an ensemble of primitive functions that perform task-agnostic skills. The experimental results on navigation and manipulation domains show that the proposed method can reliably obtain task-solving programs and outperforms or performs competitively compared to RL baselines including SAC, PPO, TRPO. I believe this work studies an interesting and promising research direction and proposes a convincing framework to tackle this problem with solid technical contributions. Yet, I am mainly concerned with some missing baselines, relevant works, and ablations.", "summary_of_the_review": "I believe this work studies an interesting and promising research direction and proposes a convincing framework to tackle this problem with solid technical contributions. Yet, I am mainly concerned with some missing baselines, relevant works, and ablations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an approach to synthesize programmatic policies, utilizing a continuous relaxation of program semantics and a parameterization of the full program derivation tree, to make it possible to learn both the program parameters and program structures jointly using policy gradient without the need to imitate an oracle.  The parameterization of the full program derivation tree that can represent all programs up to a certain depth is interesting and novel.  In its current form this won’t scale to large programs that require large tree depth, but is a promising first step in this direction.  The learned programmatic policies are more structured and interpretable, and also demonstrated competitive performance against other commonly used RL algorithms.  During the reviewing process the authors have actively engaged in the interaction with the reviewers and addressed all the concerns, and all reviewers unanimously recommend acceptance.
Decision: Accept (Spotlight)