Year: 2021

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.

heading: 1 INTRODUCTION
text: A growing body of research has explored programs in a domain-specific programming language as a new RL policy representation that intentionally encourages policy interpretability. Yet, learning a policy as a high-level program in structured representations is challenging. This is because algorithms must jointly identify a reasonable program architecture to allow for sufficient expressiveness while optimizing the parameters of a program’s modules. For example, depending on the shape of a maze, walking a robot to different goals on the maze by a program may require various if-then-else conditions to travel along different paths, the number of which might not be known to the agent before training. Existing programmatic policy synthesis algorithms either learn from a pretrained program embedding space that must support smooth interpolation (Trivedi et al., 2021), or 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 et al., 2020; Inala et al., 2020; Verma et al., 2018; 2019). The task of imitating an oracle is, intuitively, significantly simpler than the full RL problem. However, since the policy spaces of neural networks and that of programmatic policies are significantly 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 instead synthesize interpretable and differentiable programmatic policies solely from reward signals by policy gradient methods, without needing any oracles and pretraining. A conceivable way of synthesizing program architectures would be to enumerate all possible architectures induced by the grammar of a domain-specific policy language, 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 as each RL trial may explore millions 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 as learning the probability distribution over all possible architecture derivations (up to a certain bound on program abstract syntax tree depth) induced by a policy language grammar. This enables our RL algorithm to jointly optimize program architectures and the parameters of program modules via policy-gradient methods.
Our second contribution is improving programmatic policies to 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 to 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., 2019), 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-art 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.

heading: 2 PROBLEM MOTIVATION AND FORMULATION
text: We study how to express RL policies as differentiable programs, which use symbolic language constructs to compose a set of parameterized primitive modules. To control an agent, a 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 a pair (E, θ), where E is a discrete program architecture and θ is a vector of real-valued parameters of the program. A program architecture E is structured based on the context-free grammar (Hopcroft et al., 2007) of a policy DSL. In this paper, we consider the context-free grammar depicted in the standard Backus-Naur form (Winskel, 1993) in Fig. 1. A vertical bar “|” indicates choice. Such a grammar consists of a set of production rules X ::= σ1 σ2 · · · σj where X is a nonterminal and σ1, · · · , σj are either terminals or nonter-
minals. For example, we may expand the nonteriminal E1 in a partial program if B1 then C1 else E1 to if B1 then C1 else (if B2 then C2 else E2). The nonterminals E and B stand for program expressions that evaluate to action values in Rm and Booleans, respectively, where m is the action dimension size. We represent a state input to a programmatic policy as s = {x1 : ν1, x2 : ν2, . . . , xn} where n is the state dimension size and νi = s[xi] is the value of xi in s. As usual, the unbounded variables in X = [x1, x2, . . . , xn] are assumed to be input variables (state variables in our context). A terminal in this grammar is a symbol that can appear in a program’s code, e.g. the if symbol and xi.
The semantics of a program in E is mostly standard and given by a function JEK(s), defined for each DSL construct. For example, JxiK(s) = s[xi] reads the value of a variable xi in a 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 σ is the sigmoid function:
Jif B then C else EK(s) = σ(JBK(s)) · JCK(s) + (1− σ(JBK(s)) · JEK(s) (1) Thus, any policy programmed in this grammar becomes a differentiable program. C is a controller used by a programmatic policy. During execution, the policy can invoke a 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:
CAffine ::= θc + θ · X | θc
where θ ∈ Rm·|X |, θc ∈ Rm are control parameters. Particularly, CAffine can be as simple as some (learned) constants θc. An example affine policy is given in Appendix K.1.
if θ1c + θ T 1 · X > 0
then ( 95% · πUP(s) + 5% · πLEFT(s))←− Branch 1 else if θ2c + θ T 2 · X > 0
then ( 95% · πLEFT(s) + 5% · πRIGHT(s))←− Branch 2 else ( 13% · πDOWN(s) + 87% · πRIGHT(s))←− Branch 3
X = [ x, y, Gx, Gy, arctan yx , ‖x, y‖2 ] θ1 = [ − 2.052, 0.049, 0.440, 0.181, 0.241, 1.443 ], θ1c = −0.202 θ2 = [ 1.333, 2.204,−2.2171, 2.132, 1.878, 0.331 ], θ2c = −0.416
Figure 3: An Ant Cross Maze program Pcross with three branches. A program input X includes current Ant position x, y along with the target location Gx, Gy (sampled from one of the three goals in Fig. 2). arctan yx and ‖x, y‖2 are functions of x and y. Each branch composes primitive functions: πUP, πDOWN, πLEFT, and πRIGHT. Composition weights are shown in percentage.
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 π1, · · · , πN as callable library functions:
Cπ ::= θ1 · π1(s) + θ2 · π2(s) + · · ·+ θN · πN (s) Cπ explicitly compose primitive functions (e.g. running forward or jumping) hierarchically into a complex program (e.g. jumping over multiple hurdles to reach a target) where θ1, · · · , θN ∈ R1 parameterize a primitive combination. The input space of a primitive function can be different than that of the composite program (formally defined below). Its semantics is captured as follows:
JCπK(s) = N∑ i=0 qi · πi(s) where qi = exp(θi/T )∑N j=0 exp(θj/T )
Here the composition weights {qi}Ni=0 for primitive ensemble are computed using gumbel-softmax, where T is the temperature term (Jang et al., 2017).
PID Policies. Suppose we know a 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.
Program Interpretability. Our RL algorithm searches over a DSL to synthesize a programmatic policy. Thanks to the structured and symbolic representations, it learns highly interpretable policies. For example, consider an Ant Cross Maze environment depicted in Fig. 2. The cross-maze contains three possible goal positions and one would be randomly selected at each time. In this environment, the task for a 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 or crash. We consider the DSL for this task using ensemble policies Cπ. It includes four basic primitive functions for moving the Ant up πup, down πdown, left πleft, and right πright (pretrained as neural network policies using standard RL algorithms with details left in App. F.2).
Fig. 3 depicts a synthesized program Pcross 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 of the predicate in a Boolean condition determines the activation of the controller guarded by the Boolean condition. At each state, branch activation determines the strength of each of the controllers in the program. For example, the activation of branch 1 is σ(θ1c + θ T 1 · X ), and the activation of branch 2 is (1− σ(θ1c + θT1 · X )) · σ(θ2c + θT2 · X ).
Fig. 4a depicts the activation of branch 1 as a function of (x, y) when the goal to reach is sampled at Gx = 12,Gy = 0. The degree of activation (yellow) is close to 1 on all states under (12, 0) indicating that the ensemble policy at branch 1 is used to drive the Ant up to the goal. Indeed, according to the
distribution of each primitive function at branch 1, the effect of πUP dominates. Fig. 4b, Fig. 4c, and Fig. 4d depict the activation of all three branches when the goal is at Gx = 6,Gy = −6. The program can be interpreted as branch 1 (where πUP dominates) and branch 3 (where πRIGHT dominates) are activated in the yellow areas of Fig. 4b and Fig. 4d respectively. This allows the Ant to make a curved up and right move to the goal (branch 2 is not activated during execution for this goal).
Problem Formulation. We frame programmatic RL as a Markov Decision Process (MDP) defined by a tuple {S,A, T ,R} where S and A represent the environment state space and action space, T : S × A × S → [0, 1] captures the set of transition probabilities, and R : S × A → R denotes the reward function. We assume S ⊇ R|X∪V| where X is the set of input variables of a composite program (defined by a DSL) and V is the set of input variables of primitive functions. For a noncomposite affine policy, V = ∅. At time t ≥ 0, an RL agent receives an environment state st ∈ S and performs an action at ∈ A selected by its policy π(at|st) : S → A. Based on st and at, the agent transits to receive the next state according to the transition model T (st+1|st, at), and receives the reward R(st, at). We aim to learn a programmatic policy π in the DSL in Fig. 1 by jointly synthesizing the program’s architecture E and optimizing the program’s parameters θ to maximize the cumulative discounted reward Es0,a0,s1···∼π [∑∞ 0 γ t ·R(st, at) ] where γ ∈ (0, 1].

heading: 3 ARCHITECTURE SEARCH FOR PROGRAMMATIC POLICIES
text: 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. It takes as input any policy DSL with differentiable semantics and conducts policy architecture search on a program derivation tree of the DSL. Formally, a program derivation tree is T = {V, E} where a node u ∈ V contains partial architectures with missing expressions or a complete architecture permissible by the DSL. An edge (u, uE) ∈ E exists if one can obtain the architectures in uE 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, uE contains more than one architecture. Take the Pcross program in Fig. 3 as a concrete example: Fig. 5 depicts a program derivation tree for the DSL in Fig. 1 where a controller C is an ensemble policy. On the root node 0, 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 E2. Node 1 thus contains two partial architectures. Formally, we use F(uE) to represent the set of architectures on a node uE . To expand a nonterminal or a missing expression of a partial program architecture, we relax the categorical choice of DSL production rules into a softmax over all possible production rules for the missing expression with trainable weights. For example, on node 1, the choices to expandE1 between the ensemble policy C1 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 E1 to the conditional branching expression on node 1. Assume we further expand E2 on node 1 to a conditional branching expression as well on node 5. Then again we have two choices to expand the nonterminal E3 on node 5 weighted by w2. This time we choose to expand E3 to an ensemble policy C5. Formally, the weight matrix wuE of the incoming edge to a node uE is of the shape R|F(uE)|, and wuE [E′] weighs the likelihood of choosing a particular architecture E′ ∈ F(uE) for expanding E.
A program derivation tree T essentially expresses all possible program derivations up to a certain bound on the depth of program abstract syntax trees. To train architecture weights, we encode a program derivation tree itself as a differentiable program πTθ,w that takes a state s as input. Its action output is weighted by the outputs of all programs included in πTθ,w, where w represents program architecture weights and θ includes unknown program parameters of all the mixed programs in the tree. The semantics computation of an expression JEK(s) in a program derivation tree πTθ,w is delegated to its tree node uE where the nonterminal E is expanded and the categorical choice of expanding E on uE is relaxed to a softmax over all possible choices:
JEK(s) = JuEK(s) JuEK(s) = ∑
E′∈F(uE)
exp(wuE [E ′])∑
E′′∈F (uE) exp(wuE [E ′′]) · JE′K(s)
Complexity. Assume that the root of T hosts the initial DSL nonterminal ET , d is the depth of T , k is the number of DSL production rules, and m is the maximum number of nonterminals in the body of any rules. The semantics of πTθ,w is defined as JπTθ,wK(s) = JET K(s). The number of DSL operations (e.g. evaluations of ensemble policies and Boolean conditions) invoked by JET K(·) is bounded by O((km)d). In practice, we optimize the run-time cost of JET K(·) as discussed in Appendix. F.1. The parameters w and θ of a program derivation tree πTθ,w can be jointly optimized using any policy gradient methods. To obtain stochastic policy gradients, πTθ,w(·|s) is encoded as a Gaussian policy where the tree program outputs the action distribution mean. A separate set of parameters specify the (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 δ, where ρπTθold,wold is the discounted state visitation frequency of πTθold,wold , AπTθold,wold is an estimator of the advantage function over a finite batch of samples from πTθold,wold and θold, wold are policy architecture weights and parameters before the update:
maximizeθ,w Jθold,wold(θ, w) = Es∼ρ πT θold,wold ,a∼πTθold,wold [ πTθ,w(s, a) πTθold,wold(s, a) AπTθold,wold (s, a) ] subject to Es∼ρ
πT θold,wold
[ DKL(π T θold,wold (·|s) ∣∣∣∣∣∣ πTθ,w(·|s))] ≤ δ (2)
Policy Parameter Optimization. Our training algorithm is an iterative bilevel optimization procedure. At training iteration k, we perform two steps. At the first step, we optimize the lower-level program parameters θ with respect to (2), freezing the upper-level architecture weights w:
θk+1 = argmax θ Jθk,wk(θ, wk) s.t. Es∼ρπT θk,wk
[ DKL(π T θk,wk (·|s) ∣∣∣∣∣∣ πTθk+1,wk(·|s))] ≤ δ (3)
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 = argmax w Jθk+1,wk(θk+1, w) s.t. Es∼ρπT θk+1,wk
[ DKL(π T θk+1,wk (·|s) ∣∣∣∣∣∣ πTθk+1,wk+1(·|s))] ≤ δ
(4) 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 a linear
approximation to the objective and a quadratic approximation to the constraint (Schulman et al., 2015). Upon convergence, based on architecture weights, we obtain a discrete program architecture from πTθ,w replacing each tree node containing multiple architectures with the most likely architecture in a top-down manner. Finally, we train the parameters in the chosen architecture using RL (Schulman et al., 2015) until convergence from parameter values learned during the search process. The algorithmic pseudocode is depicted in Algorithm 1 in the appendix.

heading: 4 PROGRAMMATIC HIGH-LEVEL PLANNING
text: 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 a ⊃-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 an 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 HRL methods are either model-free e.g. (Nachum et al., 2018; 2019) or model-based e.g. (Roderick et al., 2018; Jothimurugan et al., 2021). In a model-free approach, the learning algorithm in Sec. 3 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 a 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, low-level primitives designed to grasp basic, task-agnostic skills (e.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 ⊃-maze are collected on an abstract 2-D gridworld m ∈ RN×N in Fig. 6b. An abstract grid (x, y) ∈ N ×N subsumes concrete positions with a known scale where m[x, y] = 1 indicates walls and m[x, y] = 0 indicates navigable spaces. The domain expert can then specify a pair of abstract Ant start (yellow) ϕInit and goal (green) ϕGoal state.
ϕInit(x0, y0) ≡ x0 = 3 ∧ y0 = 1 ϕGoal(xk, yk) ≡ xk = 1 ∧ yk = 1 Our design choice of state and action abstraction addresses an 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, it is straightforward to directly specify the statetransition behavior of the abstract actions ϕAct as opposed to learning it. For example, the Ant primitives move an Ant by updating its horizontal position xi or vertical position yi one step dxi or dyi on the abstract model. The Ant can also be moved diagonally via primitive composition:
ϕAct(xi−1, yi−1, xi, yi) ≡ ∃dxi, dyi.xi = xi−1 + dxi ∧ yi = yi−1 + dyi ∧ −1 ≤ dxi, dyi ≤ 1 An abstract action is specified together with a guard ϕGuard that encodes conditions under which the action can occur. For example, an Ant in ⊃-maze should not walk into walls and the path from an old position to a new position should not be blocked by walls.
ϕGuard(xi−1, yi−1, xi, yi) ≡ m[xi][yi] 6= 1 ∧ ( m[xi−1][yi] 6= 1 ∨m[xi][yi−1] 6= 1 ) We further leverage the primitive function specifications to synthesize a high-level control plan on the abstract model. Suppose for now that we are searching over a high-level plan of a fixed number k of
abstract action steps to reach the goal state ϕGoal from the initial state ϕInit:
ϕInit(x0, y0) ∧ k∧ i=1 ( ϕAct(xi−1, yi−1, xi, yi) ∧ ϕGuard(xi−1, yi−1, xi, yi) ) ∧ ϕGoal(xk, yk) (5)
Constraint (5) can be solved by off-the-shelf 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 k until the optimal solution is found. Such a plan is a sequence of sub tasks. For example, the solved high-level plan for Ant ⊃-Maze navigation is depicted in Fig. 6c. Since a sub task may depend on multiple primitives e.g. Ant turning around at a corner, we learn a low-level policy for each sub task 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 ϕAct 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.1); (2) more importantly, these easy-to-annotate specifications substantially improve the sample efficiency of HRL (Sec. 5).

heading: 5 EXPERIMENTS AND EVALUATIONS
text: 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 a randomly sampled goal location within a confined circular region. (3) Pusher: A robotic arm in Fig. 10b is trained to push a cylinder object to a given target location. (4) HalfCheetah Hurdle: A MuJoCo 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 ⊃-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 a 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 πJUMP and πFORWARD, Pusher πPUSH-LEFT and πPUSH-DOWN (with details in Appendix F.2).
Programmatic RL. To the benchmarks from the first group, we apply the RL algorithm in Sec. 3 to learn a program derivation tree πT -PRL from which we extract programmatic RL policies π-PRL. The tree depth bound of πT -PRL is set to 6. Our baselines include Composition-SAC (Qureshi et al., 2019) that learns Bidirectional LSTM-based ensemble policies using the SAC algorithm (Haarnoja et al., 2018) to combine the task-agnostic primitives for solving the task environments. On-policy RL algorithms TRPO (Schulman et al., 2015) and PPO (Schulman et al., 2017) are the other two baselines. Fig. 7a depicts the mean learning performance in terms of the agent’s final distance from targets over 10 random seeds. TRPO and PPO both fail to reach the goals. During policy architecture search, πT -PRL successfully solves all tasks and outperform or match the performance of the BiLSTM models of Composition-SAC. The πT -PRL models exhibit less data-efficiency than the Composition-SAC policies in part due to the use of TRPO for on-policy update that is less sample-efficient than off-policy SAC (our learning algorithm can also be applied to off-policy RL).
Upon convergence of training a πT -PRL program derivation tree, our algorithm extracts a program π-PRL from πT -PRL and trains it until convergence. Table 1 presents the mean and standard deviation of π-PRL’s final distance from given targets. Extracted programs recover the performance of πT -PRL models and continue to outperform or match the BiLSTM models in Composition-SAC. Importantly, π-PRL policies are significantly more interpretable than the BiLSTM policies e.g. Fig. 3 and Fig. 4. The high interpretability of π-PRL policies in turn leads to strong generalizability to novel environments because of the inductive bias implicitly encoded in the policy’s interpretable 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 π-PRL in Appendix I and J.
In Table 1, we also show the number environment steps needed until convergence for policy architect search πT -PRL, extraction π-PRL, and training a programmatic policy using the same architecture
with π-PRL from scratch. Except Ant Cross Maze, the sample efficiency of policy architecture search and extraction combined is even better than learning a single program from scratch. Intuitively, this is because πT -PRL is essentially an over-parameterized model of the optimal policy in the search space. The better data efficiency of our method compared to enumerating all possible policy architectures to perform RL for each highlights the merits of jointly optimizing policy architectures and parameters.
Programmatic High-level Planning. To the second group of the benchmarks, we apply the task planning algorithm in Sec. 4 to learn hierarchically programmatic RL policies, denoted as π-HPRL programs. Our baselines include a model-free Hierarchical RL method HIRO (Nachum et 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 in terms of the agent’s final distance from targets over 5 random seeds. The π-HPRL 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 a local optimum. Unlike π-HPRL, HIRO is model-free and does not know the structure of the abstract state space, so it is unable to discover the path from the initial region to the goal region. A-AVI performs worse than π-HPRL because it does not decouple model-based high-level planning and model construction. π-HPRL is more sample efficient as it decomposes a task into multiple simpler sub tasks with explicit sub goals to 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 to synthesize monolithic programs in the DSL in Fig. 1 that switch back and forth between a set of affine controllers under different conditions. Table 2 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 to 5, 6, 7 respectively. Table 2 shows that the final performance of the synthesized policies is not sensitive to the depth setting. Although a larger depth bound incurs a greater search space, our algorithm eventually 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 of our algorithm are depicted in Appendix B.
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 1. To ensure a 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 structure spaces, the program that best imitates an oracle is not necessarily a performant programmatic policy. Our oracle-free method overcomes the suboptimality induced by oracle-guided programmatic RL. Comparison results with other oraclebased programmatic RL baselines can be found in Appendix C.

heading: 6 RELATED WORK AND CONCLUSION
text: Existing programmatic RL methods mostly train a programmatic policy to imitate a pretrained RL oracle. Using a teacher-student learning paradigm, 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 a nontrivial distillation gap as the distillation process can yield suboptimal policies. Our approach optimizes programmatic polices in a continuous relaxation of the non-differentiable architecture space solely using reward signals by policy-gradient methods. Trivedi et al. (2021) first learns a program embedding space that supports smooth interpolation and then searches over the learned program embedding space to synthesize a program. Our approach differs as we do not need to prepare a dataset of programs to train the program embedding space, thus is more suitable when sampling such a dataset of unique programs is challenging (e.g. Ant continuous control). Yang et al. (2021) uses a MaxSAT solver to synthesize straight-line programs to guide a policy to reach a goal. Our method is more suitable when there are multiple goals in an environment for which architecture synthesis is necessary to learn conditional branches to reach diverse goals. Our method is also related to the growing body of research on neural program synthesis (Devlin et al., 2017; Balog et al., 2017; Bunel et al., 2018; Chen et al., 2019c; Sun et al., 2018; Tian et al., 2019; Hong et al., 2021). We discuss it with other related work in a broader context 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-gradient methods. Our RL framework leverages compositionality in programming languages to integrate primitive functions into a composite program to solve novel RL problems. Experiment results demonstrate that our algorithm excels in discovering compositional RL programs with optimal architectures and strong interpretability.
Reproducibility Statement. The source code of the tool that supports this paper is uploaded as a supplementary material.

heading: A TRAINING ALGORITHM PSEUDOCODE

heading: A.1 THE PROGRAMMATIC REINFORCEMENT LEARNING ALGORITHM
text: We depict the pseudocode of our oracle-free programmatic reinforcement learning algorithm in Algorithm 1. The algorithm builds a program derivation tree that involves programs whose abstract syntax tree depth is bounded by a hyperparameter d. We encode the program derivation graph as a differentiable program πTθ,w with architecture weight w and policy parameters θ. Recall the surrogate objective definition in Eq. (2):
Jθold,wold(θ, w) = Es∼ρ πT θold,wold ,a∼πTθold,wold [ πTθ,w(s, a) πTθold,wold(s, a) AπTθold,wold (s, a) ] where AπTθold,wold
is an estimator of the advantage function over a finite batch of samples from πTθold,wold and θold, wold are policy architecture weights and parameters before policy update.
In the pseudocode, training steps (3) for learning θ 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 a quadratic approximation to the constraint (Schulman et al., 2015). Upon convergence, based on architecture weights, we obtain a discrete program architecture from πTθ,w replacing each tree node containing multiple architectures with the most likely architecture in a top-down manner. Finally, we train the parameters in the chosen architecture using RL (Schulman et al., 2015) until convergence from parameter values learned during the search process.
Algorithm 1 Programmatic Reinforcement Learning without Oracles Require: Policy Context-free grammar E, depth bound d, KL-divergence limit δ Ensure: Synthesized programmatic policy π T ← get Program Derivation Tree (E, d)
. T expresses all programs whose abstract syntax tree depth is bounded by d πTθ,w ← encode (T ) . πTθ,w as differentiable program with parameters θ and architecture weights w that encodes T θ0, w0 ← randomly initialize (θ, w) for k = 0, 1, 2, . . . ,M do . Policy Architecture Search
θk+1 = argmaxθ Jθk,wk(θ, wk)
s.t. Es∼ρ πT θk,wk
[ DKL(π T θk,wk (·|s) ∣∣∣∣∣∣ πTθk+1,wk(·|s))] ≤ δ . Per Eq. (3)
wk+1 = argmaxw Jθk+1,wk(θk+1, w)
s.t. Es∼ρ πT θk+1,wk
[ DKL(π T θk+1,wk (·|s) ∣∣∣∣∣∣ πTθk+1,wk+1(·|s))] ≤ δ . Per Eq. (4)
end for πθ ← extract (πTθM ,wM ) . Extract a single program from based on architecture weights w M θ0 ← θM . The extracted policy inherits parameters from trained πTθM ,wM for k = 0, 1, 2, . . . , N do . Train the chosen architecture
θk+1 = argmaxθ Jθk(θ)
s.t. Es∼ρπθk
[ DKL(πθk(·|s) ∣∣∣∣∣∣ πθk+1(·|s))] ≤ δ end for return πθN

heading: A.2 THE PROGRAMMATIC HIGH-LEVEL PLANNING
text: The pseudocode of the synthesis algorithm for HRL policies is depicted in Algorithm 2. The goal is to synthesize a high-level control plan on the abstract model using abstract actions ϕAct as constraints. An abstract action is specified together with a guard ϕGuard that encodes conditions under which the action can occur. Suppose for now that we are searching over a high-level plan of a fixed number k
of abstract action steps to reach the goal state ϕGoal from the initial state ϕInit:
ϕInit(x0, y0) ∧ k∧ i=1 ( ϕAct(xi−1, yi−1, xi, yi,mi−1,mi) ∧ ϕGuard(xi−1, yi−1, xi, yi,mi−1) ) ∧
ϕGoal(xk, yk)
(6)
Constraint (6) can be solved by off-the-shelf constraint satisfiability 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 k until the optimal highlevel plan solution is found. A solved high-level plan is a sequence of sub-tasks:( β(x0, y0), π1, β(x1, y1) ) , ( β(x1, y1), π2, β(x2, y2) ) , . . . , ( β(xk−1, yk−1), πk, β(xk, yk) ) where we extract the intermediate high-level goals x1, y1, . . . , xk−1, yk−1 from the solution of the statisfiability solver, and the concretization function β converts abstract states back to concrete goals on the unabstracted environment for the agent to successively achieve. For example, the solved high-level plan for Ant ⊃-Maze navigation is depicted in Fig. 6c. For each sub-task i that starts from a set of initial states β(xi−1, yi−1), we learn a new low-level policy πi that drives the agent to reach states in β(xi, yi). The states of πi when reaching β(xi, yi) serve as the initial states for training πi+1. Notice that we do not directly use primitive functions as πi, because oftentimes low-level policies need to compose primitive functions using different weights under different environment conditions not fully captured by abstract models 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 πi as a programmatic ensemble policy composing primitive functions using the technique in Sec. 3 and distance-based rewards. This ensures that our HRL policies are interpretable at both levels.
Algorithm 2 Programmatic High-Level Planning Require: Primitive Specifications ϕAct, abstract Action Guard ϕGuard, abstract initial ϕinit and goal ϕgoal, time-step limit T for the execution of each low-level policy Ensure: A high-level plan model, and low-level policies π0, π1, . . . , πk−1 for k = 1, 2, . . . ,M do . High-level policy planning
φk ← ϕInit(x0, y0) ∧ ∧k i=1 ( ϕAct(xi−1, yi−1, xi, yi) ∧ ϕGuard(xi−1, yi−1, xi, yi) ) ∧ϕGoal(xk, yk) . Per Eq. (5) model← solve (φk) if model 6= None then ∀ i. xi, yi = model[xi], model[yi] . A high-level control plan is synthesized Break else if k ==M then Return “Failed”
end if end for for i = 0, 1, 2, . . . , k − 1 do . Low-level policy learning
Ri ← λs, a.− dist(s, β ( xi, yi) ) . Reward based on distance to sub goal (xi, yi)
πi = argmaxπi Es0∼ ( π0,...,πi−1 ) , ( a0,s1··· ) ∼πi [∑T 0 γ t ·Ri(st, at) ]
. Apply Algorithm 1 to learn a low-level programmatic policy πi
. The initial state s0 is sampled as the last state observed by πi−1 end for return π0, π1, . . . , πk−1

heading: B MORE ABLATION STUDY RESULTS
text: Our first ablation study investigates the impact of compositionality on our algorithm. Fig. 8 shows the ablation study results on comparing different strategies, i.e., learning a programmatic ensemble policy, learning a programmatic affine policy, and learning a deep neural network policy using TRPO (Schulman et al., 2015). A programmatic affine policy is a monolithic program in our DSL (Fig. 1)
that switches back and forth between a set of affine controllers under different environment 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 generation trees, comparing 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 the depth bounds. Although a larger depth bound incurs a greater search space, the algorithm eventually converges to architectures with similar performance. Table 2 additionally shows that the structures of the converged architectures are also similar. This suggests that if the user does not know how complex the programmatic policy should be a priori, the user can simply set a large tree-depth bound and our algorithm would assign the highest probability to the architecture within the program derivation tree that maximizes cumulative RL reward.

heading: C COMPARISON WITH ORACLE-GUIDED PROGRAMMATIC RL
text: One of the main contributions is direct programmatic policy search. Existing oracle-guided programmatic 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 a 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 on reward signals without using any oracles. This allows the synthesis algorithm to search for optimal programs in the differentiable programmatic policy space, without hindrance. We compare
our programmatic RL algorithm with oracle-based programmatic RL algorithms that learn policies in the form of programs (using the same DSL as ours) (Verma et al., 2018) and decision trees (Bastani et al., 2018). We first report results on Mujoco/OpenAI environments where programmatic policies invoke a set of affine controllers under different environmental conditions in Table 3. To ensure a fair comparison, we relax the semantics of oracle-guided RL programs to be continuous as well but decision trees remain discrete. Neural oracles and our programmatic policies were trained with TRPO (Schulman et al., 2015) 3 million steps and we report the averaged final reward performance of three repeated experiments.
The reward performance of our oracle-free programmatic RL policies is comparable to, sometimes better than neural network policies. Due to the distillation gap, the oracle-guided RL programs learned by the baselines perform worse than their oracles and our policies. We also tried the imitation-projected programmatic RL algorithm (Verma et al., 2019) that optimizes a programmatic policy by taking a mirror gradient descent in a policy space with a mix of neural and programmatic representations, which enables deep policy gradient approaches on programmatic policies. However, our own implementation of the algorithm does not achieve results better than (Verma et al., 2018) — optimization in the mixed policy space does not lead to significant policy improvement.
We further compare our algorithm with (Verma et al., 2018) on the environments reported in Sec. 5. According to our results in Fig. 7a, these environments are best solved using policies that invoke a 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-SAC (Qureshi et al., 2019). Table 2 demonstrates that the oracle-guided RL programs (π-Oracle) 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-SAC policy in general works well, the success rate of reaching the goal (6, -6) is 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).
The above two sets of experiments demonstrate that our oracle-free programmatic RL overcomes the suboptimality induced by oracle-guided programmatic RL.

heading: D DSLS WITHOUT LOOPS
text: Our loop-free programmatic policies can already produce repetitive behaviors when necessary. This is because policies are always executed in a 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 of a parking spot to an 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 are varied to evaluate whether policies can produce an arbitrary number of repetitions. For example,
on QuadPO, the obstacle course length is doubled during testing. Table 4 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 et al., 2020) as its implementation is not available.
Moreover, our tool indeed supports loops in a program that sequentially processes a history of environment states and actions. For example, our DSL allows a 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 a history. We could alternatively add fold(f, h) directly to the DSL to search policies that combine the results of recursively processing each past state in a history h to build up a return action (the body of the combining operation f can also be synthesized).

heading: E ADDITIONAL RELATED WORK
text: Compositional Reinforcement Learning. To improve RL efficiency, a line of research that transfers 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 to assign weights for action composition (Peng et al., 2019; Qureshi et al., 2019). Hierarchical reinforcement learning, such as option-critic (Bacon et al., 2017), is also a 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 approach to automate deep learning applications Zoph & Le (2017); Zoph et al. (2018); 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 a composition of softmaxes over all possible candidate operations between a 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 a super-network. It then selects the optimal architecture based on the weights. Various methods further improve architecture search efficiency, accuracy and applicability Chen et 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 reinforcement 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 a synthesizer e.g. DeepCoder (Balog et al., 2017), or generate a 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 a 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 et al., 2021) iteratively builds sketches using progressively more complicated primitives though a wake-sleep algorithm. Latent Programmer (Hong et al., 2021) considers two-level search for program synthesis, in which the synthesizer first generates a plan — a sequence of symbols, in other words discrete latent code from input/output examples by discrete autoencoders, that describes the desired program at a high level—before generating the program, and then generates the program in the target language. This method avoids enumerative search, which is prohibitively expensive for large program spaces.
There is also a line of work that deals with learning to process partial programs in addition to the specification. In execution-guided program synthesis, the model guides iterative extensions of the partial programs until a matching one is found. Zohar & Wolf (2018) process intermediate values of a program using a neural network for a small, straight-line DSL, but they do not use the model to evaluate intermediate programs. Ellis et al. (2019) allow values of whole programs encountered during bottom-up search to be used to prioritize the search in an actor-critic framework. Tian et al. (2019) exploit the differentiability of the rendering process to train a program generating policy and generalize it beyond the training distribution via gradient-based fine-tuning. Similarly, Chen et al. (2019c) exploit intermediate values while synthesizing a program via a top-down fashion using a neural encoder-decoder model.
F IMPLEMENTATION DETAILS
In this section, we present implementation details including the optimization of JEK(·), primitive policies, symbolic inputs and reward structures of each environment, and hyperparameters of reinforcement learning algorithms.

heading: F.1 COMPUTATIONAL COMPLEXITY OF PROGRAM DERIVATION TREE EXECUTION
text: We compare the computational complexity of JEK(·) (where d = 6) with that of the deepest single program in JEK(·) and that of the Bidirectional LSTM-based model used by the Compositional SAC baseline (Qureshi et al., 2019) as follows. We report the average running time of over 10000 random executions of the three models in Table 5.
In our implementation, the run-time execution of a program derivation tree is optimized as follows. As depicted in Fig. 5, primitive policies are invoked multiple times by various programs embedded in a program derivation tree. Since the input to any primitive is 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 5 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 to explicitly enumerate and execute all programs up to some depth for each state evaluated during an episode. Fig. 5 shows that we allow the exponential number of programs in a program derivation tree to share computation (similar to weight sharing in DARTS) — intermediate results computed by a shallower program can be reused by a deeper program.
For more complex DSLs with a large number k 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-weighted programs at the previous stage from the program derivation tree. Such a progressive procedure would allow our algorithm to deeply explore the architecture space even when k is large, which is left for future work.

heading: F.2 PRIMITIVE POLICIES DETAILS
text: In all reinforcement learning tasks, we require multiple primitive skills policies to compose higherlevel programs. Since primitive policies are obtained for completing dedicated tasks, e.g., navigating the ant agent to move up, or 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 et al., 2018) implemented in OpenAI 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 is defined as:
rant = cv · vdirection + ch · I(IsHealthy)− ca · ‖a‖2 − cf · ‖fcontact‖2 (7)
where vdirection is the velocity of given direction, I(IsHealthy) is a Boolean function that determines the health condition of the agent, action a is a 8-dimension vector, and fcontact is a vector that encodes the contact force of the agent. In order to train UP and DOWN primitives, vdirection = ±vx should track velocities on ±x-axis; similarly, to train LEFT and RIGHT policies, we should set vdirection = ±vy to keep track of velocities along ±y-axis. Coefficients cv, ch, ca and cf are set to be 1, 1, 0.5, 5× 10−4, respectively.
Pusher. 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:
rpusher = cv · vdirection − ca · ‖a‖2 (8)
where vdirection denotes the object’s velocity projected on DOWN (negative y-axis) or LEFT (positive x-axis), and a is the action. Coefficients cv and ca are set to be 1 and 0.1, respectively.
HalfCheetah. In HalfCheetah Hurdle environment, two simple policies JUMP and FORWARD are trained for 0.5 million steps, and they are sufficient to compose the program and solve the task. The reward function can be defined as:
rhc = cvf · vforward + cvj · vjump − ca · ‖a‖2 (9)
where vforward and vjump are velocities projected on forward (x-axis) and jump (y-axis) directions, and a is the action. In order to train FORWARD policy, coefficients cvf , cvj are set to be 1 and 0; for policy JUMP, we set coefficients cvf = 0.05 and cvj = 1, respectively. Coefficient ca is the control cost coefficient which set to be 0.1.
Note that for Ant and HalfCheetah Hurdle environment, primitive policies are trained in a blank environment without any obstacle so that they can move freely.

heading: F.3 PROGRAM INPUTS
text: For low-torque ant, we consider its current position x, y, distance from current position to the starting point ‖x, y‖2, and the angle between current direction to the x-axis arctan y x as symbolic inputs. For standard-torque ant, besides the above inputs, we also take the goal position Gx,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 hurdleHnext and the distance from HalfCheetah’s back foot to next hurdle |xback −Hnext| are considered. For the simple pusher task, we use distance from origin to the object ‖xobj , yobj‖2 and to the robotic arm ‖xarm, yarm‖2 as symbolic inputs.
(a) Ant Random Goal (b) Pusher (c) HalfCheetah Hurdle
(d) Ant Push (e) Ant Fall
Figure 10: Navigation and manipulation benchmarks that require agents to reach or move the object to the given targets (represented by a red circle for pusher and by green spheres for the rest). Additionally, Ant Cross Maze and Ant ⊃-Maze are depicted in Fig. 2 and Fig. 6a respectively. In all ant environments, the definitions of up, down, left, right, and forward are moving towards positive/negative x/y axes directions, respectively.

heading: F.4 ENVIRONMENT DETAILS

heading: F.4.1 ANT ENVIRONMENTS
text: The standard-torque Ant environments include Ant Cross Maze and Ant Random Goal environments. In these environments, a MuJoCo 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 1 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) at each time; and the goals in Ant Random Goal is a random position within a circle with radius of 5. In ant environments, the reward function is defined as:
rant rl = cdistance · (cd − ‖pant − pgoal‖2) + ch · I(IsHealthy) − ca · ‖a‖2 − cf · ‖fcontact‖2
(10)
where pant = (xant, yant) and pgoal = (xgoal, ygoal) are positions of ant and the given targets, I(IsHealthy) is a Boolean function that determines the health condition of the agent, action a is a vector, and fcontact is a vector denotes the contact force. Coefficients cdistance, cd, ch, ca and cf are set to be 1, 5, 0.05, 0.01 and 0.001, respectively.
Additionally, we consider three challenging low-torque MuJoCo Ant environments with weak distance-based reward signals. Compared to standard-torque, the low-torque ant has the force range [-30, 30]. Since smaller force is exerted on joints, the ant moves slower and suitable for intricate HRL tasks. Specifically, we normalize the distances to a fixed final goal by the agent initial distance from the goal so values close to 1 or higher show failure. Greedily following this kind of reward signals does not lead to solving the problems as these environments are in complex shapes.
In the Ant ⊃-Maze environment, we place the Ant in a ⊃-shaped maze for a navigation task. The agent is trained to reach the farthest end of the maze located at (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 is at (8, 8) at the same elevation as Ant. Their is a rift in the region [-4, 12] × [12, 20]. To reach the target on the other side of the rift, the Ant must push the block down into the rift, and then step on it 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.

heading: F.4.2 PUSHER ENVIRONMENT
text: In the Pusher environment, the initial position of the object is randomly sampled from the region [0.3, 1] × [-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 to object, as well as object to goal should be tracked. The reward function for Pusher environment is defined as:
rpusher2d = −creach · ‖parm − pobj‖2 − cmove · ‖pobj − pgoal‖2 − ca · ‖a‖2 (11)
where parm = (xarm, yarm), pobj = (xobj , yobj), and pgoal = (xgoal, ygoal) are positions of the robotic arm, object, and the goal, respectively. Coefficient creach, cmove, ca are set to be 0.5, 1, and 0.1, respectively.

heading: F.4.3 HALFCHEETAH HURDLE ENVIRONMENT
text: In the HalfCheetah Hurdle environment, a MuJoCo halfcheetah is required to start from origin and jump over three hurdles to reach the target with radius of 1. The reward function is defined as:
rhurdle =− cdistance · |xgoal − x|+ churdle · count(x) + cgoal · I(IsReached) + crun · vx + cjump · vy − ccollision · I(IsCollided)
(12)
where x is cheetah’s current position, xgoal is target location, count(x) function returns the number of hurdles has been passed, I(IsReached) is a Boolean function that determines if the cheetah reach the target, vx and vy are the projected velocities on x-axis and y-axis, and I(IsCollided) is a Boolean function that determines if the cheetah is in collision. Coefficient cdistance, churdle, cgoal, crun, cjump and ccollision are set to be 0.1, 1, 1000, 1, 0.3 and 2, respectively.

heading: F.5 HYPERPARAMETERS
text: Following hyperparameters are used to train primitive policies with SAC (Haarnoja et al., 2018) algorithm.
• Discount factor γ = 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 π-PRL programs for solving tasks in group one environments with TRPO (Schulman et al., 2015) algorithm.
• Discount factor γ = 0.99.
• Number of trajectories per epoch N = 50.
• Maximum search depth of program derivation graph Dg = 6.
• KL-Divergence limit δ = 0.01.
• GAE λ = 0.97.
• Gumbel-Softmax Temperature T = 0.25.
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 T = 0.25.
Table 6 summarizes the neural network architectures used in reinforcement learning algorithms.
G IMPLEMENTATION DETAILS OF PROGRAMMATIC HIGH-LEVEL PLANNING

heading: G.1 SPECIFICATIONS FOR HIGH-LEVEL PLANNING
text: In our experiment, we have applied programmatic high-Level planning in Sec. 4 to 3 challenging environments, namely Ant ⊃-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 ⊃-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 a 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 an U-shaped maze from (Nachum et al., 2018) in Fig. 6a. The abstract states of the task are collected on an abstract 2-D gridworld m ∈ RN×N in Fig. 6b. An abstract grid (x, y) ∈ N ×N subsumes concrete positions with a known scale where m[x, y] = 1 indicates walls and m[x, y] = 0 indicates nagivable spaces. The domain expert can then specify a pair of abstract Ant start (yellow) ϕInit and goal (green) ϕGoal state. 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.
For Ant Push and Ant Fall, we reuse the same state abstraction as above. We additionally use m[x, y] = Move to specify that there is a movable block at (x, y). The Ant needs to push away the movable block to reach the goal behind it in Ant Push or push it into a gap and then utilize the block as a bridge to get close to the goal on the other side of the gap.
Other than state abstraction, for model-based planning, we also abstract over actions to ensure a 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 HRL approaches e.g. (Jothimurugan et al., 2021), our algorithm uses abstract actions as specified rather than learned. In the following, We show that with taskagnostic 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 an Ant up πup, down πdown, left πleft, and right πright. Therefore, the abstract actions move an Ant horizontally, vertically, or diagonally (via composition) one step on the abstract model:
ϕAct Ant Push(xi−1, yi−1, xi, yi,mi−1,mi) ≡ xi = xi−1 + dxi ∧ yi = yi−1 + dyi ∧ −1 ≤ dxi, dyi ≤ 1 ∧
∀p, q. mi[p][q] =  0 mi−1[xi][yi] = Move ∧ p = xi ∧ q = yi MOVE mi−1[xi][yi] = Move ∧ p = xi + dxi ∧ q = yi + dyi mi−1[p][q] otherwise
Compared to the ϕAct definition in Sec. 4, we add two new parameters mi−1 and mi to the new definition above. This is because an agent action may change its environment. Here mi−1 refers to the old environment before an agent action, and mi refers to the new environment after the agent
action. For example, for Ant Push, if a movable block is pushed by an Ant, the state abstraction should be updated accordingly reflecting the fact in the new environment mi that the space after the movable block holds the block after the push.
We require that an abstract action be specified together with a guard ϕGuard that encodes conditions under which the action can occur. For Ant Push, an Ant should not walk into walls and the path from an old position to a 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 mi−1 before the action. Besides, a movable block can only be moved vertically or horizontally in the Ant environment.
ϕGuard Ant Push(xi−1, yi−1, xi, yi,mi−1) ≡ mi−1[xi][yi] 6= 1 ∧ ( mi−1[xi−1][yi] = 0 ∨mi−1[xi][yi−1] = 0 ) ∧
mi−1[xi][yi] = Move⇒ mi−1[xi + (xi − xi−1)][yi + (yi − yi−1)] = 0 mi−1[xi][yi] = Move⇒ xi = xi−1 ∨ yi = yi−1
The abstract action specification for Ant Fall can be defined similarly as follows:
ϕAct Ant Fall(xi−1, yi−1, xi, yi,mi−1,mi) ≡ xi = xi−1 + dxi ∧ yi = yi−1 + dyi ∧ −1 ≤ dxi, dyi ≤ 1 ∧
∀p, q. mi[p][q] =  0 mi−1[xi][yi] = Move ∧ p = xi ∧ q = yi 0 mi−1[xi][yi] = Move ∧mi−1[p][q] = Gap ∧ p = xi + dxi ∧ q = yi + dyi Move mi−1[xi][yi] = Move ∧mi−1[p][q] 6= Gap ∧
p = xi + dxi ∧ q = yi + dyi mi−1[p][q] otherwise
Notice that ϕAct Ant Fall is almost the same to ϕAct Ant Push except that we specify that if the Ant pushes a movable block into a gap, the gap becomes a bridge for the Ant to bypass.
ϕGuard Ant Fall(xi−1, yi−1, xi, yi,mi−1) ≡ mi−1[xi][yi] 6= 1 ∧ ( mi−1[xi−1][yi] = 0 ∨mi−1[xi][yi−1] = 0 ) ∧
mi−1[xi][yi] = Move⇒ mi−1[xi + (xi − xi−1)][yi + (yi − yi−1)] = 0 ∨ mi−1[xi + (xi − xi−1)][yi + (yi − yi−1)] = Gap
mi−1[xi][yi] = Move⇒ xi = xi−1 ∨ yi = yi−1 Similarly, ϕGuard Ant Fall is almost the same to ϕGuard Ant Push except that we specify that the Ant can push a movable block either if there is either an empty space or a gap behind the block in the old environment before the action.

heading: G.2 DETAILED RESULTS ON HIERARCHICAL RL BENCHMARKS
text: We show the success rates of applying our learning algorithm in Sec. 4, HIRO (Nachum et al., 2018), and A-AVI (Jothimurugan et al., 2021) in Table 7.
It can be seen that π-HRPL programs signifiantly outperform both HIRO and A-AVI. For example, on the challenging Ant Push environment, our π-HRPL policy achieves 94% success rate of goal reaching far beyond that of HIRO and A-AVI.

heading: H PROGRAM INTERPRETABILITY: ANT CROSS MAZE
text: In this section, we take one step ahead and show how an Ant Cross Maze program Pcross can be interpreted by using both branch activation and also policy strength graphs.

heading: H.1 BRANCH ACTIVATION
text: 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 Pcross is activated (shown in Fig. 11a) 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.11b shows that int most upper-half of the given area, branch two is activated and it would enforce the agent to go RIGHT.

heading: H.2 POLICY STRENGTH
text: Unlike a branch activation graph which informs us how a branch is activated, a policy strength graph demonstrates how a specific primitive skill policy is invoked without considering the semantic of any branch, so it is suitable for final analysis and interpretation.
Fig.12a and 12b demonstrate the UP policy strength of program Pcross 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.12a we 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 a right turn. Therefore, the effect of Pcross 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 to make a left or 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 Fig.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 to move right. Therefore, the effect of Pcross shows in Fig.13 can be summarized as: the LEFT or RIGHT polices strength is at a high level when the ant reaches the center area of maze so it can be navigated to make a left or right turn to reach the targets.

heading: I PROGRAM INTERPRETABILITY: MORE EXAMPLES
text: In this section, we demonstrate more examples of programs and their branch activation and policy strength graphs for interpretation.

heading: I.1 ANT RANDOM GOAL PROGRAM
text: Fig.14 demonstrates the expression of the program Prandom for solving Ant Random Goal environment. The pre-defined function input X takes symbolic states include current position x, y along with the randomly sampled target location Gx,Gy. Also, a 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 (Gx, Gy) = (-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 at the same time.
Fig.16a and 16b demonstrate the DOWN and RIGHT policy strength of a 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 is a vector that contains strength of each primitive skill policy and we are interested in the strength DOWN and RIGHT primitive policies in this case. Presumably, if the goal position is (-3, -3) and the ant starts from (0, 0), the simplest path for an ant is to move diagonally along with southeast direction, and surely this requires DOWN and RIGHT primitive policies, and each of them is likely to contribute equally. From Fig.16 we know that with this program Prandom, when the agent moves southeast, the contribution of DOWN and
if (θ1c + θ T 1 · X > 0)
then (0% · πUP(s) + 51% · πDOWN(s) + 0% · πLEFT(s) + 49% · πRIGHT(s)) else if (θ2c + θ T 2 · X > 0)
then (3% · πUP(s) + 0% · πDOWN(s) + 97% · πLEFT(s) + 0% · πRIGHT(s)) else if (θ3c + θ T 3 · X > 0)
then (82% · πUP(s) + 15% · πDOWN(s) + 0% · πLEFT(s) + 3% · πRIGHT(s)) else (78% · πUP(s) + 0% · πDOWN(s) + 0% · πLEFT(s) + 22% · πRIGHT(s))
X = [ x, y, Gx, Gy, arctan yx , ‖x, y‖2 ] θ1 = [ 0.899, 0.397,−0.893,−0.394,−0.019, 0.080 ], θ1c = −2.050 θ2 = [ 0.222,−1.679,−0.117, 1.468,−0.107, 0.297 ], θ2c = −3.798 θ3 = [ − 0.895, 0.196,−1.290, 2.423,−2.667, 2.378 ], θ3c = −2.226
Figure 14: An Ant Random Goal program Prandom powered by four primitive skill policies: πUP(s), πDOWN(s), πLEFT(s) and πRIGHT(s). Program input X includes current Ant position x, y, target goal Gx, Gy , arctan yx , and ‖x, y‖2.
RIGHT are roughly the same, and this is consistent with our expectation. Therefore, the effect of this program can be summarized as: if the agent is required to move southeast from (0, 0) to (-3, -3), assign DOWN and RIGHT equally at roughly 50 percent of strength.

heading: I.2 PUSHER PROGRAM
text: Fig.17 demonstrates a program Ppusher with three branches for solving Pusher environment. The program input X takes symbolic states xobj , yobj , xarm, yarm as inputs, then computes ‖xobj , yobj‖2 , ‖xarm, yarm‖2 to decide which branch of weight cell to take. From Fig.18a we can conclude that, only the first branch is activated in the whole possible situations. Such activation values for branch 1 demonstrate that the possibility of 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 to 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 to move the object to the target location.
Furthermore, Fig.18 demonstrates PUSH-DOWN and PUSH-LEFT policy strength of the program Ppusher. 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 a 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.18c: when the object is too close to the origin, the PUSH-LEFT policy strength is at a lower level, and if the object is close to 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 x and y axes: if we want to acquire a policy which
if (θ1c + θ T 1 · X > 0)
then ( 74% · πPUSH-DOWN(s) + 26% · πPUSH-LEFT(s) ) else if (θ2c + θ T 2 · X > 0)
then ( 99% · πPUSH-DOWN(s) + 1% · πPUSH-LEFT(s) ) else ( 99% · πPUSH-DOWN(s) + 1% · πPUSH-LEFT(s) )
X = [ ‖xobj , yobj‖2 , ‖xarm, yarm‖2 ] θ1 = [ − 1.370, 0.621 ], θ1c = 5.041 θ2 = [ − 1.252,−8.101 ], θ2c = −3.426
Figure 17: A Pusher program Ppusher powered by two primitive skill policies: πPUSH-DOWN(s) and πPUSH-LEFT(s). Program input X includes norms over xobj , yobj and xarm, 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 a reasonable combination of velocity in both x and y axes.

heading: I.3 HALFCHEETAH HURDLE PROGRAM
text: According to our experiments when applying π-PRL algorithm to HalfCheetah Hurdle environment, the program derivation graph is inclined to select a program with few branches. In fact, a simple HalfCheetah Hurdle program Phc with only one branch (shown in Fig.19) is able to solve the task with high performance and success rate.
An example of such program can be written as 95% · πFORWARD(s) + 5% · πJUMP(s). In this simple program, the input X is not even used, this means the agent invokes each primitive policy at a fixed rate. The success of such a simple combination of two primitive skill policies tells us, if a program is powered by appropriate low-level primitive policies, we may solve a RL task in a much simpler way.

heading: J POLICY GENERALIZABILITY
text: In our experience, the high interpretability of learned programmatic policies leads to strong generalizability of the policies to novel environments.

heading: J.1 ANT NO MAZE
text: We consider applying the programmatic policy Pcross 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 be quite different than the three goals in Ant Cross Maze, we remove all the walls from the environment so the Ant can navigate freely. Fig.20a and 20b depicts the UP and

heading: 95% · πFORWARD(s) + 5% · πJUMP(s)
text: X = [Hnext, |xback −Hnext| ]
Figure 19: A HalfCheetah Hurdle program Phc powered by two primitive skill policies: πFORWARD(s) and πJUMP(s). Program input X includes the position of the next hurdle Hnext and the distance from HalfCheetah’s back foot to next hurdle |xback −Hnext|. The program Phc shown is a special program which does not contain any if -then-else structure, i.e., there exists a fixed strength of invoking each primitive policy.
RIGHT policy strength if we set the goal to (14, -8), i.e., 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. Pcross can successfully drive the Ant to these positions. From these policy strength figures we can conclude that Pcross 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.
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 Fig.21). The shapes and positions of walls have also been changed and adapted to new possible goals accordingly. This novel environment Ant Reshaped Maze is 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 Pcross to Ant Reshaped Maze and compare the generalizability ofPcross with the BiLSTM policy learned in the Ant Cross Maze environment as well using
Composition-SAC (Qureshi et al., 2019). We compare with Composition-SAC because the two policies both learn to compose primtivie skills to adapt to new complex behavior. However, Pcross is more interpretable than a BiLSTM model. Table 8 shows that Pcross successfully realizes the change of the three goals and drive the Ant in the novel environment with 0.16 normalized distance to the new goals. In constrast, the Composition-SAC policy does not solve the novel environment well. We further increase the original radius of goals to 1.5 and 2 in the novel environment, both Pcross and the Composition-SAC policy get close to goals with Pcross continuing to perform much better.

heading: K AFFINE POLICIES AND PID POLICIES

heading: K.1 AFFINE POLICIES
text: The DSL for affine policies implements a controller C as affine transformations in Fig. 1:
CAffine ::= θc + θ · X | θc
where θ ∈ Rm·|X |, θc ∈ Rm are control parameters. Particularly, CAffine can be as simple as some (learned) constants θc.
For example, consider the continuous OpenAI Gym MountainCar environment in Fig. 22a. A car is on a one-dimensional track, positioned between two ”mountains”. The goal is to drive up the mountain on the right. Because the car’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 is greater if the policy spends less energy to reach the goal.
A learned programmatic policy to control the continuous MountainCar environment is given in 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 1 on almost all states under with speed velocity greater than 0. The logic of the program is then obvious — when ever the car speed is greater than 0, the policy accelerates the forth to drive the car forward; when ever the car speed is less than 0, the policy accelerates the forth to drive the car 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 on all experienced episodes.
if θ1c + θ T 1 · X > 0
then 0.92←− Branch 1 else − 0.95←− Branch 2
X = [ position, velocity ] θ1 = [ 0.1, 128.1 ], θ1c = 0.88
Figure 23: A MountainCar program with two branches. Program input X includes current car position and velocity.

heading: K.2 PID POLICIES
text: The DSL for PID policies implements a controller C as a discretized, multivariable PID function in Fig. 1: CPID ::= PIDθP ,θI ,θD ( , h, s) | θc where θP , θI , θD ∈ Rm·n are 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 a fixed target for the controller to stabilize the system under control around, and a histroy h of a sequence of states before the current control step. The semantics of the controller is as follows:
JPIDθP ,θI ,θDK( , h, s) =θP · P + θI · I + θD ·D where P = ( − s) I = fold(+, − h) D = peek(h,−1)− s (13)
In the semantics definition, P is the proportional term, I is the discrete approximation of the integral term (calculated via a fold), and D is the finite-difference approximation of the derivative term. In line with the standard integral error reset strategy (Åström & Hägglund, 1984), the fold function acts over a 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 a classic problem in the control literature. The pendulum starts in a random position, and the goal is to swing it up so it stays upright. The state space include θ that is the angle the pendulum makes with the vertical and the angular velocity θ̇. However, the observation exposed to a policy for this task is [cos(θ), sin(θ), θ̇]. Since the goal is to stablise the pendulum upright, the fixed goal for a PID controller for this task is [1, 0, 0] (i.e. [cos(θ) = 1, sin(θ) = 0, θ̇ = 0]).
A learned programmatic policy to control the pendulum environment is given in Fig. 25. Fig. 24b depicts the activation of branch 1 in the program as a function of (θ, θ̇). The degree of activation (yellow) is close to 1 on all states where the PID controller in branch 1 would be applied to.
if θ1c + θ T 1 · X > 0 then PIDθP ,θI ,θD ([ 1, 0, 0 ] , h, s ) ←− Branch 1
else 2.39←− Branch 2
X = [ cos(θ), sin(θ), θ̇ ] θ1 = [ 2.57, − 2.18, − 0.71 ], θ1c = 0.94 θP = [ − 9.28, 1.04, 1.71 ]T θI = [− 0.26, 1.57, 0.14 ]T θD = [− 4.70, 2.03,−0.48 ]T
Figure 25: A pendulum program with two branches. In the system, θ is the angle the pendulum makes with the vertical. Program input X includes cos(θ), sin(θ), θ̇.
Accordingly, the large constant control signal in branch 2 would be applied states within the blue region. The logic of the program is then obvious — when ever the pendulum is hanging or downwards close to +π or −π, 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 1 to eventually stabilise the pendulum upright at 0, 2π, or − 2π. The policy succeeds on all experienced episodes. In our experience, we found that it is impossible to train a single PID controller to solve the task. The programmatic policy in turn uses a large control action to push the pendulum to 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 9 demonstrates that our results on these benchmarks are competitive with state-of-the-art RL algorithms.

Review summaries:
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.

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.   The 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.   The 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.   Empirical results on continuous control problems show the advantages of the method.