Synthesizing Programmatic Policies that Inductively Generalize
Authors: Jeevana Priya Inala
Osbert Bastani
Zenna Tavares
Armando Solar-Lezama
Venue:  (2020)
Keywords: Program synthesis
reinforcement learning
inductive generalization

Abstract: Deep reinforcement learning has successfully solved a number of challenging control tasks. However, learned policies typically have difficulty generalizing to novel environments. We propose an algorithm for learning programmatic state machine policies that can capture repeating behaviors. By doing so, they have the ability to generalize to instances requiring an arbitrary number of repetitions, a property we call inductive generalization. However, state machine policies are hard to learn since they consist of a combination of continuous and discrete structures. We propose a learning framework called adaptive teaching, which learns a state machine policy by imitating a teacher; in contrast to traditional imitation learning, our teacher adaptively updates itself based on the structure of the student. We show that our algorithm can be used to learn policies that inductively generalize to novel environments, whereas traditional neural network policies fail to do so. 

Published as a conference paper at ICLR 2020
SYNTHESIZING PROGRAMMATIC POLICIES THAT INDUCTIVELY GENERALIZE
Jeevana Priya Inala
Osbert Bastani University Pennsylvania obastant @seas upenn.eds
Zenna Tavares MIT CSAIL
MIT CSAIL
jinala@csal mim.tde
zenna@mi @mit edd
Armando Solar-Lezama MIT CSAIL asolar@csail. mit. edu
ABSTRACT
Deep reinforcement learning has successfully solved number of challenging control tasks. However, learned policies typically have difficulty generalizing to novel environments. We propose algorithm for learning programmatic state machine policies that can capture repeating behaviors. By doing so, they have the ability to generalize to instances requiring arbitrary number of repetitions, a property we call inductive generalization. However, state machine policies are hard learn since they consist of combination of continuous and discrete structures. We propose a learning framework called adaptive teaching, which learns a state machine policy by imitating teacher; in contrast traditional imitation learning, our teacher adaptively updates itself based on the structure of the student. We show that our algorithm can be used learn policies that inductively generalize to novel environments, whereas traditional neural network policies fail to do so.
INTRODUCTION
Existing deep reinforcement learning (RL) approaches have difficulty generalizing to novel envi- ronments (Packer et al.] 2018 Rajeswaran et al., 2017). More specifically, consider task that requires performing a repeating behavior we would like be able learn policy that generalizes to instances requiring an arbitrary number of repetitions. We refer to this property as inductive generalization. In supervised learning, specialized neural network architectures have been proposed that exhibit inductive generalization not obvious how those techniques would generalize to the control problems discussed this paper. Alternatively, algorithms have been proposed for learning programmatic policies for control problems that generalize better than traditional neural network policies (Verma et al. 2019 2018), but existing approaches have focused on simple stateless policies that make learning generalizable repetitive behaviors hard, e.g., stateless program cannot internally keep track of the number of repetitions made far and decide the next action based on that progress.
tasks such as list manipulation (Cai et al.) (017). but it is
We propose an algorithm for learning programmatic state machine policies. Such a policy consists of of internal states, called modes, each of which is associated with controller that applied while in that mode. The policy also includes transition predicates that describe how the mode is updated. These policies are sufficiently expressive capture tasks of interest-e.g, they can perform repeating tasks by cycling through some subset of modes during execution. Additionally, state machine policies are strongly biased towards policies that inductively generalize, that deep RL. policies lack. other words, this policy class is both realizable (i.c., it contains "right" policy that solves the problem for all environments) and identifiable (i.c., we can learn the right policy from limited data).
However, state machine policies are challenging to learn because their discrete state transitions make it difficult to use gradient- based optimization. One standard solution is to "soften" the state transitions by making them probabilistic. However, these techniques alone insufficient; they still run into local optima due to the the constraints on the structure of the policy function, as well as the relatively few parameters they possess.

---

Published as a conference paper at ICLR 2020
goal
15
15-
goal
15.
goal
15
goal
10
10
10-
10
M
start
start
5
star
star
0
0
-2.5 0.0
-2.5 0.0
-2.5 0.0
-2.5 0.0
(a)
Train 1
(b) Train
(c) Train 3
(d) Test
G
G
G5
m,
True
m
x S -1.13
Mg
s 1.58
me
Hm;
[2.4.335]
Hmg = [1.6, -335
G2
G
dg s 0.33
dy S 0.31
m22
H
[-2.0,-44 -09]
(e) State machine based policy. False edges are dropped.
Figure 1: Running example: retrieving autonomous car from tight parking spots. The goal is to learn a state-machine policy (e) that is trained on scenarios (a), (b), and (c), that generalizes to scenario (d).
To address this issue, we propose approach called adaptive teacher that alternatingly learns teacher and a student. The teacher is an wverpparameterized version of the student, which is state-machine policy trained to mimic the teacher. Because the teacher is over-parameterized, it can be easily learned using model-based numerical optimization (but does not generalize as well as the student). Furthermore, our approach is different from traditional imitation learning (Schaal 1999 Ross et al., (01T)) since the teacher is regularized to favor strategies similar to the ones taken by the student, ensure the student can successfully mimic the teacher. As the student improves, the teacher improves as well. This alternating optimization can naturally be derived within the framework of variational inference, where the teacher encodes the variational distribution (Wainwright et 2008).
We implement our algorithm and evaluate it on a set of reinforcement learning problems focused on tasks that require inductive generalization. We show that traditional deep RL approaches perform well on the original task, but fail to generalize inductively, whereas our state machine policies successfully generalize beyond the training distribution.
We emphasize that we do not focus on problems that require large state-machines, which is qualitatively different problem from and would require different algorithms to solve. We believe that state- mattemmachinss are most useful when only a few modes are required. In particular, we are interested in problems where relatively simple behavior must be repeated certain number of times to solve the given task. The key premise behind our approach, shown by our evaluation, is that, in these cases, compact state-machie machines can represent policies that both have good performance and are generalizable. In fact, algorithm solves all of our benchmarks using mlahie policies with at most modes. When many modes are needed, then the number of possible transition structures grows exponentially, making difficult learn the "right" structure without having an exponential amount of training data.
Example. Consider the autonomous car in Figure I which consists of blue (the agent) parked between two stationary black cars. The system state is (a, y, 8, d), where (æ, y) is the center of the car, 0 is the orientation, and d is the distance between the two black cars. The actions are (v, v),
2

---

Published as a conference paper at ICLR 2020
where is velocity and s is steering angle (we consider velocity control since the speed is low). The dynamics are standard bicycle dynamics. The goal is to drive out of the parked spot to an adjacent lane while avoiding collisions. This task is easy when d is large (Figure Ta). It is somewhat more involved when d is small, since it requires multiple maneuvers (Figures 1b and [c). However, it becomes challenging when d is very small (Figure Tdp. A standard RI. algorithm will train a policy that performs well on the distances seen during training but does not generalize to smaller distances. In contrast, our goal is to train an agent on scenarios (a), (b), and (c), that generalizes to scenario (d).
In Figure Tel we show a state machine policy synthesized by our algorithm for this task. We use dj and d, to denote the distances between the agent and the front and back black cars, respectively. This policy has three different modes (besides a start mode m, and an end mode m.). Roughly speaking, this policy says (i) immediately shift from mode m, to m., and drive the car forward and to the left, (ii) continue until close to the car in front; then, transition to mode m2, and drive the car backwards and to the right, (iii) continue until close to the car behind; then, transition back to mode m., (iv) iterate between m and m2 until the car can safely exit the parking spot; then, transition to mode my, and drive forward and to the right to make the car parallel to the lane. This policy inductively generalizes since it captures the iterative behavior of driving forward and then backward until exiting the parking spot. Thus, it successfully solves the scenario in Figure ld
Related work. There has been growing interest in using program synthesis to aid machine Iearn- ing (Lake et al. 2015] Ellis et al. 2015 2018 Valkov et al. 2018 Young et al., 2019). Our work is most closely related recent work using imitation learning learn programmatic policies (Vermal et al. 2018 Bastani et al. 2018 Zhu et al., 2019, Verma et al. 2019). These approaches use a neural network policy as the teacher. However, they are focused on learning stateless policies and hence, they use a supervised dataset of state-action pairs from the teacher and a domain-specifit program synthesizer to learn programmatic policies. Building such a synthesizer for state machine policies is challenging since they contain both discrete and continuous parameters and internal state. The student in our algorithm needs to learn the state-machine policy from entire "trajectory traces" to learn the internal state. In particular, each trajectory trace consists of the sequence of states and actions from the initial state to the goal state visited by the teacher, but also encodes which states correspond to mode changes for the teacher. In the teacher's iteration, the teacher's 's mode changes are regularized to align more closely with the possible student mode changes. As a consequence, in the student's iteration, it is easier for the student mimic the teacher's mode changes. Leveraging this connection between the teacher structure and student structure is critical for us to be able to learn state- machine policies Additionally, with the exception of (Verma al. 2019), for the other approaches, there is no feedback from the student to the teacher.
State machines have been previously used represent policies that have internal state (typically called memory). To learn these policies, gradient ascent methods assume fixed structure and optimize over real-valued parameters (Meuleau et al. 1999] Peshkin al. 2001 Aberdeen & Baxter 2002), whereas policy iteration methods uses dynamic programming to extend the structure (Hansen 1998). Our method combines both, but similarly to toupart & Boutilier (004).. the structure space is bounded. In addition, programmatic state machines use programs to represent state transitions and actions rules, and as a result can perform well while remaining small in size. Hierarchies of Abstract Machines (HAM)s also use programmatic state machines for hierarchical reinforcement learning, but assumed a fixed, hand-designed structure (Parr& & Russell 1998 Andre & Russell 2002).
Our inductive generalization goal is related to that of meta-learning (Finn et al. 2017;; however, whereas meta-learning trains on a few examples from the novel environment, our goal is to generalize without additional training. Our work is also related to guided policy search, which uses teacher in the form of a trajectory optimizer to train a neural network student (Levine & Koltun| 2013). However, training programmatic policies is more challenging since the teacher must mirror the structure of the student. Finally, it has recently been shown that over-parameete weerparameteriization is essential in helping neural networks avoid local minima (Allen-Zhh) et al., 2019). Relaxing optimization problems by adding more parameters is a well established technique; in many cases, re-parameterization can make difficult non-convex problems solve efficiently (Carlone & Calatiore 2018).
3

---

Published as a conference paper at ICLR 2020
2 PROBLEM FORMULATION
Dynamics. We are interested in synthesizing control policies for deterministic, continuous- dynamical systems with continuous state and action spaces. In particular, consider partially observable Markov decision processes (POMDP) (X, O, F, Z, Xo, Øs, Φg) with states C R actions A C Rd observations O S Rdo deterministic dynamies F X A + X (i.e., F(x, a)). deterministic observation function : X + O, and initial state distribution Xy ~ Xo.
We consider safety specification ós X IR and goal specification dg X + R. Then, the agent aims to reach a goal state (x) I 0 while staying in safe states Φs(x) S 0. A positive value for (x) (resp., (x)) quantifies the degree to which is unsafe (resp., away from the goal).
Policies. We consider policies with internal memory π : O x - A x S where S C R is the of internal states; we assume the memory initialized to a constant So. Given such policy T, we sample a rollout (or trajectory) 7 (Xo, xI, x,) with horizon N E N by sampling Xo Xy and then performing discrete-time simulation Xn+1
Xn + Fxx,; an) A, where (a,. Sn+1) = x (xx,),, sn) and A E Ryo is the time increment. Since F. Z. and π are deterministic, 7 is fully determined by X, and и,; T can also be represented as a list of actions combined with the initial state i.e r = (xo, (an, "","",,,))
The degree to which Øs and dg are satisfied along a trajectory is quantified by a reward function R(T, X²) = (xx( - En= policy class II is one which maximizes the expected reward Ex,-xx, [R( xo)].
(x,)),) where x = max (0, x). The optimal policy x' in some
Inductive generalization. Beyond optimizing reward, we want a policy that inductively generalizes to unseen environments. Formally, we consider initial state distributions: training distribution X and a test distribution X8al that includes the extreme states never encountered during training. Then, the goal is to train policy according to X -ie..
n² = arg max Xox [R(T, X
(1)
=En
but measure its performance according to X700 rie. Exo-xx [R(T, xo)]-
PROGRAMMATIC STATE MACHINE POLICIES
To achieve inductive generalization, we aim synthesize programmatic policies in the form of state machines. At a high level, state machines can be thought of as compositions of much simpler policies, where the internal state of the state machines (called its mode) indicates which simple policy is currently being used. Thus, state machines are capable of encoding complex nonlinear control tasks such as iteratively repeating a complex sequence of actions (e.g.. the car example in Figure [T]. At the same time, state machines are substantially more structured than more typical policy classes such as neural networks and decision trees.
More precisely, a state machine æ is a tuple (M, H. G, m,, me). The modes m. E M of are the internal memory of the state machine. Each mode m, E .M corresponds an action function Hm, E H. which is function Hm, O - A mapping observations to actions. When in mode mi, the agent takes action a = Hm, (o). Furthermore, each pair of modes (m,,,)) corresponds to a switching condition Gma E G, which is a function Gm, O - TR. When an agent in mode m; observes such that G (o) > 0, then the agent transitions from mode m, mode mj. If there multiple modes m, with non-negative switching weight G (o) > O, then the agent transitions to the one that is greatest in magnitude; if there are several modes of equal weight, we take the first one according fixed ordering. Finally, m,, me M are the start and end modes, respectively; the state machine mode is initialized to m., and the state machine terminates when it transitions to me.
Formally, T(O,, sn) (an, Sn4)), where a Hs. (Ox), So my and
m= darg max,, Gm (o.,) if G (o,) 2 otherwise
Sn1
S,
where darg max is deterministic arg max that breaks ties described above.
Action functions and switching conditions are specified by grammars that encode the space of possible functions space of programs. Different grammars be used for different problems.
4

---

Published as a conference paper at ICLR 2020
Typical grammars for action functions include constants {Ca 0 a} and proportional controls [Pag.o] : [o(o - a1)). A typical grammar for switching conditions is the grammar
B : {oli S a) [ol]] 2 a) B1 A B2 B V B2
of Boolean predicates over the current observation o, where ofi] is the ith component o. In all these grammars, Og E R are parameters to be learned. The grammar for switching conditions also has discrete parameters encoding the choice of expression. For example, in Figure [ the action functions are constants, and the switching conditions are inequalities over components of
4 FRAMEWORK FOR SYNTHESIZING PROGRAMMATIC POLICIES
We now describe the adaptive teaching framework for synthesizing state machine policies. In this section, the teacher is abstractly represented as a collection of trajectories Txa (i.e., an open-loop controller consisting of fixed sequence of actions) for each initial state A key insight is that we can parameterize Txa in a way that mirrors the structure of the state machine student. As we discuss in Section 4.2 parameterize Txo "loop-free" state machine. Intuitively, our algorithm efficiently computes Tx. (from multiple initial states Xa) using gradient- based optimization, and then "glues" them together using maximum likelihood to construct state machine policy.
4.1 ADAPTIVE TEACHING VIA VARIATIONAL INFERENCE
We derive the adaptive teaching formulation by reformulating the learning problem in the framework of probabilistic reinforcement learning, and also consider policies that are probabilistic state machines (see Section 4.3). Then, we use a variational approach to break the problem into the teacher and the student steps. this approach, the log- likellilo of policy defined as follows:
{()) = log (e
(3)
where p(r TT) is the probability of sampling rollout r when using policy æ from a random initial state Xo. Å E R20 is hyperparameter, and R(T) is the reward assigned to We have
AM(T) p(r x) (T)
(()) log Bg(r)
Bxc=)(AR(T) + log p(T|m) log 4(7)
(4)
where q(T) is the variational distribution and the inequality follows from Jensen's 's inequality. Thus, we can optimize by maximizing the lower bound Eq (4) on E(Tr). Since the first and third term of Eq (4) are constant with respect to we have
π = arg max ( (lgg((((T))))
(5)
Next, the optimal choice for q (i.e., to minimize the gap in the incquality in Eg 4)) is
q" arg min (xTT( || AR(T)
p(r m)/2)
where normalizing constant. We choose q to have form g(T) = p(xu) 5(T Txo), where is the Dirac delta function, p(Xp) is the initial state distribution, and Tx, are the parameters to be optimized, where txp encodes trajectory from Xo. Then, up to constants, the objective of Eq (6) equals
px(()) [ogg(Xx) + Es(r-rzo) 8(T 3xo)] - (AR(Txx) + log क, xo))
The first term is constant; the second term degenerate, but is also constant. Thus, we have arg max Ep(xo) [AR(Txx)) + log I,, x.xx)]
(Txg)
Thus, we can optimize Eq by alternatingyy optimizing Eq 5 and Eq (
We interpret these equations adaptive teaching. At high level, the teacher (i.e., the variational distribution q" in Eq 7 is used to guide the optimization the student (i.e., the state machine policy =² in Eq (5).. Rather than compute the teacher in closed form, we approximate it by sampling
5

---

Published as a conference paper at ICLR 2020
Student
M-step
Teacher
Student
E-step Learn mode mapping P(4)
Learn best action functions Mm, (Fix r.((t)
Generate loop- free policies (Fix m)
Learn the best structural program policy
Model-baced Irajeclory optimization
(Fix m)
(Fix r)
Leam best switch conditions " (Fix p(0))
Figure 2: Flowchart connecting the different components of the algorithm.
finitely many initial states x Xu and then computing the optimal rollout from x Formally, the ith iteration, the teacher and student are updated as follows:
K
Teacher
O Σ
5(T))
(8)
where
Thé
arg max AR(T) + logp(T | (xf Xo)
K
Student
arg max
logp(T ा., x,)
A=1
The teacher objective Eq 8 is to both maximize the reward R(T)) from a random initial state Xy and to maximize the probability p(r π, Xp) of obtaining the rollout from initial state X according to the current student æ. The latter encourages the teacher to match the structure of the student. Furthermore, teacher is itself updated each step to account for the changing structure of student. The student objective Eq is to imitate the distribution of rollouts according to the teacher. Figure shows the different components of our algorithm.
4.2 TEACHER: COMPUTING LOOP-FREE POLICIES
We begin by describing how the teacher solves the trajectory optimization problem Eq 8 i.e., computing The for a given initial state x
Parameterization. One approach is to parameterize
arbitrary action sequence (ag. a
and use gradient-based optimization to compute However, this approach can perform poorly-even though we regularize 7 towards the student, it could exhibit behaviors that hard for the student to capture. Instead, we parameterize in a way that mirrors the student. In particular, we parameterize like state machine, but rather than having modes and switching conditions that adaptively determine the sequence of action functions to be executed and the duration of execution, the sequence of action functions fixed and each action function is executed for a fixed duration.
More precisely, we represent an loop-free policy = (H, T)). To execute each action function H, E is applied for the corresponding duration T, T, after which H is applied. The action functions are from the same grammar of action functions for the student.
The obvious way to represent a duration T; is as number time steps T, E N. However, with this choice, we cannot use continuous optimization to optimize T, Instead, we fix the number of discretization steps P for which H; is executed, and vary the time increment A; = TP/P-ie.. Xa+1 R X,, F(x,, (o)) A, We enforce A < Amax for small A max ensure that the discrete-time approximation of the dynamics is sufficiently accurate.
Figure aa) and (d) show examples of loop-free policies for different initial states and two different teacher iterations. The loop-free policies (d) are regularized to match the student's state-machine policy learned in the previous iteration (shown in Figure
Optimization. We use model-based trajectory optimization to compute loop-free policies. The main challenge is handling the term p(T म. xo) in the objective. Symbolically computing the

---

Published as a conference paper at ICLR 2020
Iteration 1
X
X
(a) Teacher
R
R R
(b) Mode mapping
(c) Student
R = -0.30
R -0.36
Iteration 2
X
(d) Teacher
R = 0
R =
(e) Mode mapping
(I) Student
R 0.15
R 0004
Figure 3: Visualization showing the student-teacher interaction for two iterations. (a) The loop-free policies (with their corresponding rewards) learned by the teacher for two different initial states. Here, the boxes signify the different segments in the loop-free policies, the colors signify different actions, and the lengths of the boxes signify the durations of the segments. (b) The mapping between the segments and the modes in the sate-machine-iiee p(u my). Each box shows the composition of modes vertically distributed according their probabilities. For example, the third segment in the loop-free policy for x has p(u Green) 0.65 and p(u Brown) 0.35. (c) The most probable
rollouts from the mtahinm policy learned by the student. Finally, (d), (c) and (f) are similar to (a), (b) and (c), but for the second iteration.
this probability is hard because of the to precompute the probabilities of all the trajectories that can be derived from However, this also infeasible because the number of trajectories is unbounded. Thus, we perform trajectory optimization in two phases. First, we use sampling-based optimization algorithm obtain set of good trajectories r!,...,? T.. Then, we apply gradient-based optimization, replacing pl- æ,, xo) with a term that regularizes 7 be close {T') Jt=1
structure of т. Another alternative is
The first phase proceeds follows: (i) sample T!....,7" using from Xn, and let p' be the probability of of according to æ, (ii) sort these samples in decreasing order of objective p² (RR()( and (iii) discard all but the top P samples. This phase essentially performs one iteration of CEM (Mannor cet al. 2003). Then, the second phase, we replace the probability expression with p(r π. Xo) R Ei pf.e-d(rirt which
gradient-based optimization to optimize. Here, d(r, 75 is distance
metric between two loop-free policies, defined as the T.2 distance between the parameters of 7 and - We chose the number of samples, = 10. For our benchmarks, we did not notice any improvement in the number of student-teacher iterations by increasing p above 10. So, believe not losing any information from this approximation.
4.3 STUDENT: LEARNING STRUCTURED STATE MACHINE POLICIES VIA IMITATION
Next, we describe how the student solves the maximum likelihood problem Eq 9 to compute π².
Probabilistic state machines. Although the output of algorithm student policy that is deterministic state machine, our algorithm internally relies on distributions over rollouts induced by the student policy to guide the teacher. Thus, we represent the student policy as probabilistic state machine during learning. To do so, we simply make the action functions Hm, and switching conditions Gmy; probabilistic-instedd of constant parameters in the grammar for action functions and switching conditions,
have Gaussian distributions N o). Then, when executing obtain i.i.d. samples of the parameters H'm Hmy and ((Gml Gmh }m]; every time switch
to mode my, and act according H',, and (G until the mode switches again. By re-sampling these parameters every mode switch, we avoid dependencies across different parts of a rollout or different rollouts. On the other hand, by not re-sampling these parameters within mode switch, we ensure that the structure of remains intact within a mode.
Optimization. Each тę can be decomposed into segments (k, where action function HA is executed for duration Tr. For example, each block in Vigure is segment. Furthermore, for the student n, let Hm, be the action function distribution for mode m, and Gmy be the switching
7

---

Published as a conference paper at ICLR 2020
Oun
Dircchgg:
R-LSTH
Drrchoppe
1.0
Trannerromans
34-
O0a2 OzidPo Scuum Ciigdc Swimer
CA7
Oued
QUASPO Pand.tu Carbol Snfrine
Train distribtioon Irange of
Figure 4: Comparison of performances on train (left) and test (middle) distributions. Our approach outperforms the baselines on benchmarks in terms of test performance. An empty bar indicates that the policy learned for that experiment failed on all runs. We also plot test performance for different choices of training distribution for the Car benchmark (right).
condition distribution for mode mi to mode m2jz. Note that Hm; and Gmjj are distributions whereas Hx, and TRe are constants. We have
p(Tk n. xx)
II p(H,, (Txx)) p(Tk, nT, x.)
For each (k: i), let jk, be the latent random variable indicating the ith mode used by starting from x5: in particular, Pk.i is a categorical random variable that takes values in the modes {m,} And Pa. = m, means that H sampled from the distribution Hm, and Ta determined by the
mi sampled switching conditions from distributions {Gmz Assuming the latent variable jk,, allows the student to compute π² by computing Hū,, and Gmjy separately. In Figure (b) and (e) show the learned mode mappings p(u= = m2) for the segments in the loop-free policies shown in (a) and (d) respectively.
Since directly optimizing the maximum likelihood is hard in the presence of the latent variables (RR, we use standard expectation maximization (EM) approach to optimizing म, where the E-step computes the distributions P(PR, my) assuming is fixed, and the M-step optimizes assuming the probabilities p(ux., = my are fixed. See Appendix for details. In Figure 3 (c) and (f) show the most probable rollouts from the math-me policies learned at the end of the EM approach for two different student iterations.
5 EXPERIMENTS
Benchmarks. We use control problems, each with different training and test distributions (summa- rized in Figure 8 in Appendix C): (i) Car, the benchmark in Figure [ (ii) Quad, where the goal is to maneuver 2D quadcopter through an obstacle course by controlling its vertical acceleration, where vary the obstacle course length, Figure Figure/@lftmmost, (iii) QuadPO, variant where the obstacles are unobserved but periodic (so the agent can perform well using a repeating motion), see Figure 6 vary the pendulum mass, (v) Cart-Pole, where vary
(second from left), (iv) Pendulum, where the time horizon and pole length, and (vi) Swimmer, where the goal is to move the swimmer forward through a viscous liquid, where we vary the length of the segments comprising the robot swimmer.
Baselines. We compare against: (i) RL: PPO with feed-forward neural network policy, (ii) RL- LSTM: PPO with LSTM, (iii) Direct-Opt: learning state machine policy directly via numerical optimization. Hyper-parameter are chosen to maximize performance on the training distribution. More details about the baselines and the parammterss can be found in Appendices B.2, B.3, & B.4. Each algorithm is trained 5 times; we choose the one that performs best on the training distribution.
Note that for the comparison to RL approaches, we use model-free algorithms, whereas. in our algorithm, the teacher uses model-based optimization. We do not compare against model-based RL approaches because (a) even model-free RL approaches achieve almost perfect performance on the training distribution (see Figure 4 left) and (b) our main goal is to compare the performance of the test distribution and not the training distribution.
policies and the neural network policies Moreover, in case the model of the system is unknown, we can use known algorithms to infer the model from data (Ahmadi et al. 2018) and then use this learned model in our algorithm.
8

---

Published as a conference paper at ICLR 2020
Traaeciory Calltiion
Trajectrry Calls on
15
15
goal
goal
15. goal
goal
goal
10
10.
10
W
start
5
start
start
start
start
0
-2.5 0.0
-2.5 0.0
-2.5 0.0
-2.5 0.0
-2.5 0.0
(a) RL Train
(b) RL Test
(c) Original
(d) User change
(c) User change 2
Figure 5: (a-c) The RL policy generates unstructured trajectories, and therefore does not generalize from (a) the training distribution to (b) the test distribution. In contrast, our state machine policy in (c) generates highly structured trajectory that generalizes well. (c-e) A user can modify our state machine policy to improve performance. In (d), the user sets the steering angle to the maximum value 0.5, and in (e), the user the thresholds in the switching conditions Gm). G to 0.1.
M
CuD
PM
time
Figure 6: Left: Trajectories for the Quad (leftmost) and QuadPO (second from the left) benchmarks using state machine policy. Right: Graph of vertical acceleration over time for both policy (red) and the neural network policy (blue), for Quad (second from the right) and QuadPO (rightmost).
5.1 RESULTS
Figure 4 results on both training and distributions. We measure performance as the fraction of rollouts (out of 1000) that both satisfy the safety specification and reach the goal.
Inductive generalization. For all benchmarks, our policy generalizes well the distribution. In four cases, we generalize perfectly (all runs satisfy the metric). For Quad and QuadPO, the policies result collisions on some runs, but only towards the end of the obstacle course.
Comparison to RL. The RL policies mostly achieve good training performance, but generalize poorly since they over-specialize Swimmer. Even in these cases, the RL policies take longer to reach the goals than our state machine policies (see Figure and Figure i Appendix [c. For QuadPO, the RL policy does not achieve good training performance since the states are partially observed. We may expect the LSTM policies to alleviate this issue. However, the L.TTM policies often perform poorly even on the training distribution, and also generalize worse than the feed-forward neural network policies.
states seen during training. The exceptions are Pendulum and
Comparison direct-opt. The state machine policies learned using direct-opt perform poorly even in training because of the numerous local optima arising due to the structural constraints. This illustrats the need to use adaptive teaching to learn state machine policies.
5.2 QUALITATIVE ANALYSIS
Behavior of policy. We empirical analyze the policies. (ggure]Sshows the trajectory taken by the RL policy (a), compared to our policy (c), from a training initial state for the Car benchmark. The RL policy does not exhibit repeating behavior, which causes it to fail on the trajectory from test state shown in (b). Similarly, Figure 6 (right) compares the actions taking by our policy to those taken by the RL policy
Quad and QuadPO. Our policy produces smooth repeating actions, whereas the RL policy does not. Action vs time graphs for other benchmarks can be found in the appendix (Figures
12 13 & 14] and they all show similar behaviors.

---

Published as a conference paper at ICLR 2020
Varying the training distribution. We study how the test performance changes vary the training distribution on the Car benchmark. We vary X0 as [dmin 13], where dmin = {13, 12.5, 12, 11.5, 11.2, 11}. but fix X to d ~ [11, 12]. Figure 4 (right) shows how test per- formance varies with danin for both our policy and the RL policy. Our policy inductively generalizes for wide range of training distributions. In contrast, the test performance of the RL policy initially increases as the train distribution gets bigger, but it eventually starts declining. The reason is that its training performance actually starts decline. Thus, in some settings, our approach (even when trained on smaller distributions) can produce policies that outperform the neural network policies produced by RL (even when trained on the full distribution).
Interpretability.. An added benefit of our state machine policies is interpretability. In particular, we demonstrate the interpretability of our policies by showing how a user can modify a learned state machine policy. Consider the policy from Tigurelielfo for the autonomous car. We manually make the following changes: (i) increase the steering angle my, to maximum value 0.5, and (ii) decrease the gap maintained between the agent and the black cars by changing the switching condition G to d S 0.1 and G to dg < 0.1. F demonstrates these changes-it shows trajectories obtained using the original policy (c), the first modified policy (d), and the second modified policy (e). There is no straightforward way to make these kinds of changes to a neural network policy.
CONCLUSION
We have proposed an algorithm for learning state machine policies that inductively generalize novel environments. Our approach is based on framework called adaptive teaching that alternatively learns a student that imitates a teacher, who in-turn adapts to the structure of the student. We demonstrate that our policies inductively generalize better than RL policies.
In the future, we will explore more complex grammars for the action functions and the switching conditions, for example, with some parts being small neural networks, while still retaining the ability to learn generalizable behaviors. Moreover, we will extend our approach to use model-free techniques in the teacher's algorithm to make our approach more aligned with the reinforcement learning premise. Finally, we believe that the idea of learning programmatic representations and using the adaptive teaching algorithm deal with the mixed discrete-conninuond problems can be applied to other learning settings such as supervised learning and unsupervised learning.
ACKNOWLEDGMENTS
This work was supported by ONR N00014-17-1-2699 and NSF Award CCF-1910769.
REFERENCES
Douglas Aberdeen and Jonathan Baxter. Scaling internal-state policy-gradient methods for pomdps. In ICML, pp. 3-10, 2002.
Mohamadreza Ahmadi, Ufuk Topcu, and Clarence Rowley. Control-oriented learning of lagrangian and hamiltonian systems. In 2018 Annual American Control Conference (ACC), pp. 520-525. IEEE, 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242 252, Long Beach, California, USA. 09-15 Jun 2019. PMLR. URL http::/proceet ngs m prwss//ssse/ee....
zhu 9a html]
David Andre and Stuart J Russell. State abstraction for programmable reinforcement learning agents. In AAAI/AAII, pp. 129, 2002.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Advances in Neural Information Processing Systems, pp. 2494-2504, 2018.
Pavol Bielik, Veselin Raychev, and Martin Vechev. Program synthesis for character level language modeling. In ICLR, 2017.
10

---

Published as a conference paper at ICLR 2020
Jonathon Cai, Richard Shin, and Dawn Song. Making neural programming architectures generalize via recursion. In 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. URL URL/attpa:///eeeeeeeeer
http:/mmmmmaaaaadmmemmmmm d=skby4psqq
Luca Carlone and Giuseppe C. Calafiore. Convex relaxations for pose graph optimization with outliers.
IEEE Robotics and Automattion Letters, 3(2): 1 1167. 2018. doi: 10.11091RRA2201.2793332
URL aattps://ooi http://oiiog///////////o/// 1109/ LRA. 2018 27933572222
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford,
John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https
//githab. com cattm/opeaa///ean
ines 2017.
Kevin Ellis, Armando Solar- and Josh Tenenbaum. Unsupervised learning by program synthesis. In Advances in neural information processing systems, pp. 973-981, 2015.
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Advances Neural Information Processing Systems, pp. 6060-6069, 2018.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning-Vor Volume 70, pp. 1 1126-1133 1135. JMLR. org, 2017.
Eric A Hansen. Solving pomdps by searching in policy space. In Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence, pp. 21 2119219. Morgan Kaufmann Publishers Inc., 1998.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 150062666:13322113333) 2015.
Sergey Levine and Vladlen Koltun. Guided policy search. In International Conference on Machine Learning, pp. 1-9, 2013.
Shie Mannor, Reuven Y Rubinstein, and Yohai Gat. The cross entropy method for fast policy search. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pp. 512-519, 2003.
Nicolas Meuleau, Leonid Peshkin, Kee-Eung Kim, and Leslie Pack Kaelbling, Learning finite-state controllers for partially observable environments. In Proceedings of the Fifteenth conference Uncertainty in artificial intelligence, pp. 427-436. Morgan Kaufmann Publishers Inc., 1999.
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing generalization in deep reinforcement learning. arXiv preprint 18X0v: 12282, 2018.
Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems, pp. 1043-1049, 1998.
Leonid Peshkin, Nicolas Meuleau, and Leslie Kaelbling. Learning policies with external memory. arXiv preprint cs/0/03003, 2001.
Pascal Poupart and Craig Boutilier. Bounded finite state controllers. In Advances in neural information processing systems, pp. 823-830, 2004.
Aravind Rajeswaran, Kendall Lowrey Emanuel V Todorov, and Sham M Kakade. Towards gen- cralization and simplicity in continuous control. In Advances in Neural Information Processing Systems, pp- 6550-6561, 2017.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635, 2011.
Stefan Schaal. Is imitation learning the route to humanoid robots? Trends in cognitive sciences, 3(6):
233-242, 1999.
11

---

Published as a conference paper at ICLR 2020
Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong learning as program synthesis. In Advances in Neural Information Processing Systems, pp. 8701-8712, 2018.
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. arXiv preprint arXiv: 02477, 2018.
Abhinav Verma, Hoang Minh Le, Yisong Yue, and Swarat Chaudhuri. Imitation-projecter policy gradient for programmatic reinforcement learning. CoRR, abs/1907.05431, 2019. URL http
//arxtv.orr/abb//1117...333
Martin Wainwright, Michael I Jordan, al. Graphical models, exponential families, and variational inference. Foundations and Trends()) in Machine Learning, 1(1-2):1-305, 2008.
Halley Young, Osbert Bastani, and Mayur Naik. Learning neurosymbolic generative models via program synthesis. International Conference Machine Learning, pp. 7144-7153, 2019.
He Zhu, Zikang Xiong, Stephen Magill, and Suresh Jagannathan. An inductive synthesis framework for verifiable reinforcement learning. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Laguagge Design and Implementation, pp. 686-701. ACM, 2019.
12

---

Published as a conference paper at ICLR 2020
A
EXPECTATION MAXIMIZATION FOR STUDENT OPTIMIZATION
A.1
COMPUTING p(r xo)
First, note that we have
p(T n., xb) II [p(lk x.) -((T, / x7,
where
p ( n, (x,00))
Ep(Hes p(HEs Hmg) p( = my).
Similarly, the duration Tk is determined both by the current mode ji,k mij. and by the switching conditions mm {Gmjy Jm from the current mode mi into some other mode ''j.. More precisely, let YR, denote the trajectory (sequence of states) of the (k, i) segment of Tæe and let S(yk,, Gmy) denote the earliest time at which switching condition G E Gm, becomes true along The Since Gm, are distributions, C(TH, Gm,) ) is distribution transition times. Then, have
P(Ta, T. x,x
p(uc;i mz)) p( =m1z)= p(Tk. Gm,y Gma ΣΣ 1111 1232
mia
Gmy
Gmj = p(T = C(Tk,i Gmy
II
p(T,, < C(Tk.
Gma
#miz
In other words, Th the duration until Gm triggers, conditioned on none of the conditions Gma triggering (where mja F mjz).
A.2 OPTIMIZING THE STUDENT POLICY
Numerically optimizing the maximum likelihood objective to compute x² is hard because it requires integrating over all possible choices for the latent variables Pk,s. For example, if the teacher generates 10 loop-free policies every iteration and there are 10 modes in each loop-free policy, and 4 modes in the state-machine. the number of choices for the latent variables 4000 which makes the enumeration infeasible. The popectationmmaximiizae maximum likelihood, by alternatingly optimizing for the latent variables and the state-machine parameters. The E-step computes the probability distributions p(ue,i mj) for fixed n, and the M-step optimizes Hm, and Gm given p(pa, my).
method provides efficient way for computing the
E-step.
Assuming æ is fixed, have
P(1K, = my n, (T+)) = p(HRi Hms)) p(Tr.i C(Th,i Gmy))
(10)
Em, p(H Hm)) p(Tr.i ((yk.es Gms))
M-step.
Assuming p(uE, = m2) is fixed, we solve
arg max (Hmyl
p(un.i = m2) log p(H Hm;)
(1I)
k,s
p(un.s m()) p( = = logp(TT, C(Th,) Gmal))
arg max [Gmjay k.
+ + = m plu = m) log (TT., < C(V G
(12)
For Gmy,, the first term handles the case Px.i+1 = mjn, where we maximize the probability that Gmyy makes the transition at duration Tk, and the second term handles the case pk.+1 + mjz where maximize the probability that Gmii does not make the transition until after duration Tk.
13

---

Published as a conference paper at ICLR 2020
We briefly discuss how to solve these equations. For action functions, suppose that H encodes the distribution ((a oH) over action function parameters. Then, we have
Ln plue, =m)) H...
Hm
Ek,eDlun = m,)
Ho ) En. m2) (art. - O'mm HHH))aaHa (atHe. aHmm )a
PLPRR = m2)
Solving for the parameters of Gm is more challenging, since there can be multiple kinds of expressions the grammar that are switching conditions, which correspond to discrete parameters, and we need to optimize over these discrete choices. To do so, we perform greedy search over these discrete choices (see Section A.3 for details on the greedy strategy). For each choice considered during the greedy search, we encode Eq 122 numerical optimization and solve it to compute the and standard deviations o² "/ Then, we choose the discrete choice that corresponding means ex* Gmmy
achieves the best objective value according to Eq
Computing the optimal parameters for switching conditions is more expensive than doing so for action functions; thus, on each student iteration, we iteratively solve Eq (TO) and Eq multiple times, but only solve Eq once.
The EM method does not guarantee global optima but usually works well in practice. In addition, since computing the switching conditions is expensive, we had to restrict the number of EM iterations. However, note that even if the EM algorithm didn't converge, our overall algorithm can still recover by using additional teacher-student interactions.
The alternate method would be to run the EM algorithm multiple times/tonger to get better results per student iteration, and "maybe" reduce the total number of teacher-student iterations. We say "maybe" because the EM algorithm might have already converged to the global optima, making the extra EM iterations useless. The trade-off between our approach and this alternative depends whether the teacher's algorithm or the student's algorithm is expensive for particular benchmark.
that some of benchmarks already use very few (< 5) teacher-student iterations (Car, QuadPO, Pendulum, Mountain car, and Swimmer). Of the other three benchmarks that needed many iterations, for of them (Cartpole and Acrobot), the student's algorithm is as expensive as the teacher's algorithm. This justifies our decision to not run the EM algorithm multiple times/longer.
However, from Figure 15]
A.3 SYNTHESIZING SWITCHING CONDITIONS
Next, we describe how we search over the large number of discrete choices in the grammar for switching conditions. is not hard show that in Eq (12). the objectives for the switching condition parameters Gm corresponding to different transitions (m,,, m2z) decompose into separate problems. Therefore,
perform the search for each transition (m,, m,,,) separately. For each transition, the na've approach would be to search over the possible derivations in the context-free grammar for switching conditions to some bounded depth. However, this search space is exponential in the depth due to the productions B :: A B and : B v B. Thus, we employ greedy search strategy to avoid the exponential blowup.
Intuitively, our search strategy is to represent switching conditions as a kind of decision tree, and then perform a greedy algorithm to search over decision I Our search strategy is similar (but simpler than) the one in Bielik et al. (2117). In particular, we can equivalently represent a switching condition as decision tree, where the internal nodes have the form ofi] I a or oli] 2 a (where i {1.... do} and a E IR are parameters), and the leaf nodes are labeled with "Switch" or "Don't 't switch"- e.g.. Figure two examples of switching conditions expressed as decision trees. Then, our algorithm initializes the switching condition to single leaf node-i.e., Geur + "Switch". At each step, we consider switching conditions E next(G that expand a single leaf node of Geuri among these, we choose Gour to be the one that minimizes a loss cost(G)).
However, our algorithm is very similar to greedy decision tree learning algorithms.
14

---

Published as a conference paper at ICLR 2020
Internal node
olt a,
ol4,s d,
True
True
Leaf nodes
Switch
switch
olt dz
Don't
True
Switch
Don't switch
Figure Switching conditions represented as decision trees.
Algorithm Greedy algorithm for learning switching conditions.
procedure LEARNSWTCCHINGCODDTII Geur t- "Switch"
while |Gaurl < do
Geur f- aarg milll cost(
return Geur
More precisely, to construct next(Geur). we iterate over all leaf nodes E leaves (Gerr) and all expressions E &, where
= if
3 E
a then "Switch" else "Don't Switch" e (1...., do]. aER, ~E NE (2
Here, ~E {2.5} inequality relation, i E {1,..., do) component o, and E is threshold. For each pair L and E, we consider the decision tree G obtained by replacing L with E in Geur- The set next(G contains all G constructed in this way.
Next, the loss function cost(G)) (G) is given by Eq (2). In each iteration, our algorithm optimizes cost G)) over E next(Geur), and updates Geur + G. solve this optimization problem, we enumerate the possible choices and and use numerical optimization to compute (since a is continuous parameter). An example of a single iteration our algorithm is shown Figure 7 In particular, letting G' be the tree the left and G' be the tree the right, the left-most leaf node of G is expanded to get G
Our algorithm is summarized in Algorithm ! different discrete structures, where is the number of nodes in the decision tree and do is the length of the observation vector
Overall, algorithm searches over N (N 1) do
B IMPLEMENTATION DETAILS
B. BENCHMARKS AND STATE-MACHINE STATISTICS
Figure shows the statistics regarding the benchmarks such as the number of action variables and observation variables, and the set of initial states used for training and testing. Figure also shows the different aspects of the grammar used to describe the space of possible state-machine policies. We are able learn policies for these benchmarks using 2 to 4 distinet modes in the mach-e with either a constant grammar of depth or 2 all the switching conditions.
proportional grammar for the action functions. We use the Boolean tree
For the Quad benchmark, the action variable is the acceleration of the quadcopter in the vertical direction. The observations include the position x, y, the velocities Va, Uy. and the four sensors O,, oz ow,, oYn to describe the obstacle course in the near neighborhood. The QuadPO benchmark has the same action space as the Quad benchmark, but can only observe x, V, Uz. and vy, The synthesized stte-machine policies for these benchmarks shown in Figure 16 and Figure 17 The action functions used for these benchmarks choose the acceleration to be proportional to Vy.
The goal for the Pendulum benchmark is to control the force (continuous) at the actuated link in order to invert the link. The observation space includes the full state, i.e.. the angle 0 and the angular velocity W. Figure T shows the synthesized mate-machine policy for the pendulum benchmark.
15

---

Published as a conference paper at ICLR 2020
Bench
#A
#0
X
modes
A.
C_G G
Car
2
5
d ~v
[m
d~ [m
3
Constant
Boolcan tree (depth 1]
Quad
1
8
dist 40m
x dist 80m
2
Proportional
Boolcan tree (depth 1)
QuadPO
dist 60m
x 120m
Proportional
Boolean tree (depth 1)
Pendulum
mass ~> [1.1.5kkg
[1.5.5]kg
Constant
Boolcan (depth
Cartpole
4
time 5s, len = 0.5
time 300s, len = 1.0
2
Constant
Boolcan tree (depth 2)
Acrobot
4
masses [0.2.0.5]
masses = [0.5.2]
2
Constant
Boolean tree (depth 2)
Mountain car
power = [5.15]e-4
power = [3.5]e-4
Constant
Boolcan tree (depth 1)
Swimmer
10
len unit
Ien 0.75 unit
4
Proportional
Boolean (depth 2)
Figure 8: Summary of our benchmarks. #A is the action dimension, #O is the observation dimension, Xhain the set of initial states used for training, X is the of initial states used test inductive generalization, # modes is the number of modes in the state machine policy, and A_G and C_G are the grammars for action functions and switching conditions, respectively. Depth of C indicates the number of levels in the Boolean tree.
The Cartpole benchmark consists of pole attached to cart. The goal is to keep the pole upright by applying continuous force to move the cart to the right or to the left. The observations include the position æ. the velocity of the cart, the angle 0, and the angular velocity of the pole. The synthesized solution shown in Figure 19
The Acrobot benchmark is similar to the Pendulum benchmark but with two links; only the top link can be actuated, and the goal is to drive the bottom link above a certain height. The observations are the angles 81, fg and the angular velocities w1,w2 of the two links. For this benchmark, vary the mass of the links between the training and the test distributions. The synthesized solution is shown in Figure 20
For the Mountain car benchmark, the goal is to drive a low powered car to the top of a hill. An agent has drive back and forth to gain enough momentum be able cross the hill. The agent controls the force (continuous) to move the car to the right or left and observes the position æ and the velocity at every timestep. We vary the power of the car between the training and the test distributions. The synthesized solution is shown in Figure 21
The Swimmer benchmark is based the Mujoco's swimmer. To make this benchmark more challenging, we use 4 segments instead of 3. There are three actions that control the torques at the joints and the goal observe the swimmer's 's global angle 6, the joint angles (01, 02 0z), the swimmer's global angular velocity w. the angular velocities of the joints (wi, W2, Wa), and the velocity of the center of mass (Ua, vy). We vary the length of the segments between the training and the test distributions. The actions are chosen to be proportional to their corresponding angles. The synthesized state machine policy is shown in Figure 22
make the swimmer move forward through viscous liquid. The agent can
B.2 HYPER-PARAMERS
There are three main hyper-parameteen in our algorithm:
The maximum number of segments/modes in loop-free policy. A large number of segments makes the teacher's numerical optimization slow, while a small number of segments might not be sufficient get high reward.
The maximum time that a segment can be executed for in a loop-free policy. This maximum time constraint helps the numerical optimization to avoid local optima that arise from executing a particular (non-convex) action function for too long.
The parameter in Section 4.1
This parameter strikes balance between preferring high- reward loop-free policies versus preferring policies that similar to the ttate-machine learned so far.
The first two parameters solely affect the teacher's 's algorithm; thus, choose them by randomly sampling from set and select the one that produces high-reward loop-free policies. We use 100 for all our experiments.
16

---

Published as a conference paper at ICLR 2020
B.3 THE DIRECT-OPT BASELINE
For this baseline, we convert the problem of synthesizing state machine policy into a numerical optimization problem. To do this, we first encode the discreteness in the grammar for switching conditions into a continuous one-hot representation. For example, the set of expressions ofi] S og or of] 2 ag are encoded as ass [0 + 220 + a., S do with constraints -1 S os S 1, vi E {1....,,) n.. 0 I S 1 and Di=1 (g = 1. The choices between the leaf expressions, conjunc- tions, and disjunctions are also encoded in a one-hot fashion. We also tried an encoding without the extra constraints would expect the linear encoding to be less generalizable than the one-hot encoding. However, we found that it is hard to even synthesize policy that works well on the training set with either of the encodings.
a-i.e., the switching conditions are linear functions of the observations. We
Another difficulty with direct optimization is that we need to optimize the combined reward from all the initial states at once. In contrast, the numerical optimization performed by the teacher in our approach can optimize the reward for each initial state separately. To deal with issue, optimization technique that uses 10 initial states for every batch and seeds the starting point of the numerical optimization for each batch with the parameters found so far. It also restarts the process with random starting point if the numerical optimization stalls. We carryout this process in parallel using 10 threads until either a solution found or the time exceeds hours.
a batch
B.4 RL BASELINES
We use the PPO2 implementation from OpenAI Baselines (Dhariwal et al.) 2017) with the standard MLP and LSTM networks for our RL baselines using 10? timesteps for training.
Environment featurization. We used the same action spaces, observation spaces, and the set of initial states that we used for our approach. One exception is the Car benchmark, for which we appended the observation vector with observations from the previous timestep. This modification was essential for the RL baseline to achieve a good performance on the training dataset.
Designing reward functions. While our approach takes in safe specification (s(x) 0 and a goal specification (x(x) < O, the RL baselines need a reward function. For the classic control problems such as cartpole, pendulum, acrobot, mountain car and swimmer, we used the standard reward functions as specified by their OpenAl environments. For Quad and QuadPO benchmarks, since the goal is to avoid collisions for as long as possible, we use a reward of for every timestep that the agent is alive and the agent is terminated as soon as it collides with any of the obstacles. Designing the reward function for the Car benchmark was tricky, because this benchmark has both a goal and a safety specification, and finding a right balance between them is crucial for learning. We tried various forms of rewards functions and finally, found that the following version achieves better performance the training distribution (on the metric that measures the fraction of roll-outs that satisfy both the goal and the safety property):
f-
if (x(s > 0
r(x, a) -xx
10
otherwisc
which adds the numerical error for not satisfying the goal with a constant negative error (-L) if the safety specification is violated at any time-step. We tried different values for L {0.1, 1, 10, 203 and found that L, = 10 achieves the best performance on the training distribution.
Hyper-parameters search. We performed a search over the various hyper-parameters in the PPO2 algorithm. We ran 10 instances of the PPO2 algorithm with parameters uniformly sampled from the space given below, and chose the one that performs well on the training distribution. This sampling is not exhaustive, but our results in Figure 4 (left most) show that did find parameters that achieve good training performances for most of our benchmarks.
The number of training minibatches {1, 2, 8, 16, 32, 64, 128, 256, 512, 1024, 20483. For the Istm network, we set this hyper-parameter to
per update, nminibatches
17

---

Published as a conference paper at ICLR 2020
Performance on Train dist.
Performance on Test dist.
Bench
Algorithm
G
T_ G
G
T_G
Ours
0.08
7.9s
0.02
31.8s
RL
0.16
6.5s
0.0
45.2s
Acrobot
Direct-opt
T
1
1
1
Ours
0,001
168.5s
0.008
290.1s
RL
0.0
98.7s
0.0
214.7s
Mountain car
Direct-opt
0.006
105.3s
2.18
216.0s
Figure 9: Experiment results for additional benchmarks. the average goal error (closer to better). T_G is the average number of timesteps to reach the goal (lower the better). 1 indicates timeout. We can see that both our approach and RL generalizes for these benchmarks.
angular velocity
enguler velecity
angle (radiens)
angle
Figure 10: Trajectories taken by our state machine policy (left) and the RL policy (middle) on Pendulum for test environment (i.e., heavier pendulum). Green (resp., red) indicates positive (resp., negative) torque. Our policy performs optimally by using positive torque when angular velocity 2 and negative torque otherwise. In contrast, the RL policy performs sub-optimally (especially in the beginning of the trajectory).
The policy entropy coefficient in the optimization objective, coef {0.0, 0.01, 0.05, 0.1}.
The number of training epochs per update, noptepochs (3...., 36).
The clipping range, cliprange = (0.1, 0.2,
The learning rate, Ir [5 x 10-6 0.003].
C ADDITIONAL RESULTS
C.I ADDITIONAL PERFORMANCE RESULTS
Figure 9 shows the training and test performance for the acrobot and mountain car benchmarks. We can see that both our approach and RL generalizes for these benchmarks.
Figure 10 qualitatively analyzes the policies learned by approach versus RL for the Pendulum benchmark. We can see that the RL policy performs slightly sub-optimally compared to our policy.
Figure II shows the trajectories from the learned state machine policy and RL policy Swimmer for train environment and test environment. While both policies generalize, the swimmer with the state machine policy is slightly faster (it takes about 35s to cover distance of 10 units while the RL policy takes about 45s).
time plots for the various benchmarks using the learned State-machine policies and neural network policies. We can see that state-matt machime polices produce smooth actions, whereas the RI policies do not.
Figures 12
show the action
18

---

Published as a conference paper at ICLR 2020
(a)
(b)
(c)
(d)
Figure 11: Trajectories taken by our state machine policy on Swimmer for (a) train environment with segments of length 1, and (b) test environment with segments of length 0.75, The colors indicate different modes. The axes are the x and coordinates of the center of mass the swimmer. Trajectories taken by the RL policy While both policies generalize, the swimmer with the state machine policy is slightly faster (it takes about 35s to cover distance of 10 units while the RL policy takes about 45s).
Swimmer for (c) train environment, and (d) test environment.
atcering angle
0.5
velocity
AL
RL
0.0
-0.5
time
time
Figure 12: Action vs time graphs for the car benchmark for both our policy (red) and the neural network policy (blue). Left shows the velocity of the agent and Right shows the steering angle.
C.2 ANALYSIS RUNNING TIME
Figure I5 shows the synthesis times for various benchmarks. It also shows the number of student- teacher iterations, and the time spent by the teacher and the student separately. The teacher optimizes the loop-free policies for different initial states in parallel. The student optimizes the switching conditions between different pairs of modes parallel. We used parallelized implementation with 10 threads, and report the wall clock time.
19

---

Published as a conference paper at ICLR 2020
10
tarque
2
-10
0
50
100
time
time
Figure 13: Action time graphs for the pendulum benchmark (left) and the cartpole benchmark (right) for both our policy (red) and the neural network policy (blue).
FUIFA
torquct
M
Rerouz
10
15
10
13
20
time
time
time
Figure 14: Action vs time graphs for the swimmer benchmark for the three torques at the three different joints of the swimmer. Blue line is for the neural network policy and red line for the state machine policy.
Ionatonn:
Teather
3000
1030
Mac
7000
6000
Time (S)
900
5000
4000
6:0
harstons
2000
1000
Poodiase
Pendalim Caradd
Salmmer
Benchmarks
Figure 15: Synthesis times (in seconds, wall clock time) for learning state machines policies for the different benchmarks. The plot breaks down the total synthesis time into time taken by the teacher, the student and other miscellaneous parts of the algorithm. Misc. mostly includes the time spent for checking convergence at every iteration. The plot also shows the number of teacher-studens iterations taken for each benchmark.
GP
63
ox,,
True
H =
Hm,
m,
[-1.97 (s, - 1.5)]
[1888 1.35)
0x) <.9.
Figure 16: Synthesized state-machine policy for the Quad benchmark.
G3
6]
y 2
True
Hm, [-1.12 (v, 1.55)]
Hay
m,
[-1.48 1.76)
y 3.63
Figure Synthesized state-machine policy for the QuadPO benchmark.
20

---

Published as a conference paper at ICLR 2020
Gf
2: 0.15
True
71
m
Hm.
[-1622]
Hag, [1.76]
G3
0.12
65
Gf
0
0.05 6.23
< 0.05
Figure 18: Synthesized state-machine policy for Pendulum.
G
m/g
G3
0.02
0.02
G7
Z 0.46
8 2 0.06
m1
Hmg
[- 3.3)
Hm, [3.98]
G3
< -0.99
Figure 19: Synthesized state-machine policy for Cartpole.
G?
G3
0.36
m2
[0.85]
Mm, 0.67
G
Gf
00
8, 0.05
< 0.05
A B > 3.10
A > 3.10
Figure 20: Synthesized machim policy for Acrobot.
G7
True
m,
Hm,
[0.92]
11,, [-0.33]
G
17 S 0.001
Gf
0.45
2 0.45
m
Figure 21: Synthesized state- mate--mcchine policy for Mountain car.
G True
-0.7 A 2 0.3
(0, 1.1).
(8, 0.0).
Hm,,
H
(8g 0.3)
(9, + 0.6)
GP
G3
0.3
(9 0.1
V 2.6
8,
A -0.14
m4
mg
-(8, 0.2),
10, - 0.7)
G1 0, 2 0.6
Bm,
(0; 1.3).
0.8)
10,
Aby
Figure 22: Synthesized state-machine policy Swimmer.
21


Reviews:
[{"review_id": "HyeFWUlkqr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a framework for structuring policies using finite state machines, training a teacher-student setup using variational inference. The method is tested on a suite of standard control problems against PPO with / without memory and against simple numerical optimisation, analysing both performance and some degree of generalisation.\n\n\nOverall, I like both the problem setting (constraining / structuring policies using SMs), and the proposed modeling and optimisation. In particular, the teacher-student setup makes sense to me in the way it has been casted under VI, and I would like to see it explored further.\n\nI have however a few major issues that prevent me from recommending acceptance of the work:\n\n1. The experiment section is generally lacking in terms of implementation details. The authors don't specify anything about models structure or details about the employed state machines, and do not seem to have included details about their direct optimisation baseline, environment featurisation, hyperparameters used across their experiments, and so on. I very much doubt I would be able to reproduce the results based only on the manuscript.\n\n2. The quality of the policies depend heavily on how close the proposed state machine matches the underlying dynamics of each task. Since - very often - complex tasks are hard to optimally describe without producing very large state machines, I would have liked to see the method tested against poor and/or adversarial specifications, to see whether empirically how well the student-teacher optimisation system can recover under such constraints.\n\n3. Casting the problem as a POMDP, while technically fine (and in most cases reasonable), doesn't seem to provide any significant advantage to the method, and seems to only be adding noise in the formalisms described across the paper. Since the method introduces notation that a lot of RL researchers are not necessarily familiar with, I would suggest the author to try to simplify it where possible. [Also please note that I haven't re-derived section 4.1 under this assumption, so correct me if I'm wrong on this.]\n\n\nAt this point, I am recommending a weak rejection, however I will be happy to significantly reconsider my overall assessment provided that at least point (1) is decently addressed (and ideally I get some response wrt. points 2 and 3).\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xaHcTk9S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper can be viewed as being related to two bodies of work:\n\n(A) The first is training programmatic policies (e.g., https://arxiv.org/abs/1907.05431).  The most popular idea is to use program synthesis & imitation learning to distill from a programmatic policy from some oracle policy.  \n\n(B) The second is training compact policies using a complex model-based controller (e.g., Guided Policy Search).   The idea is to use a step-wise model-based controller to design a good trajectory that maximizes reward, while not deviating too far from the current policy.  Then the new policy is learned from this trajectory.\n\nThe authors contrast with (A) via \"our student does not learn based on examples provided by the teacher, but is trained to mimic the internal structure of the teacher\". The authors contrast with (B) in part by claiming that \"the teacher must mirror the structure of the student\", which is supposedly harder.\n\nThus, it seems much of the intellectual merit & novelty lies how the proposed method tackles this \"structure\" problem, from both the teacher and the student side.  However, I'm having a hard time appreciating this aspect of the proposed approach.  I'm also confused by how the \"student does not learn based on examples provided by the teacher\" if it's doing imitation learning on trajectory-level demonstrations. Can the authors elaborate on this point further?\n\nThe experiments seem ok.  The idea of training programmatic polices that \"inductively generalize\" has been done before on arguably more difficult tasks (see Table 2 in https://arxiv.org/abs/1907.05431).   To contrast with this prior result, it seems the main point is that prior work relied on domain-specific program synthesizers.  Can the authors elaborate on this point further?\n\nMinor comments:\n\n-- Adaptive teaching is a pretty ambiguous term, and I think misleading within ML community (cf. https://arxiv.org/abs/1802.05190). I recommend a different algorithm name.\n\n-- Deriving the variational objective is a lot of work to reduce it to just trajectory design.  Seems overkill.\n\n\n\n------------------------------------------------------------\nUpdates after Author Response\n------------------------------------------------------------\n\nI increased my score to accept.  I think this is a worthy contribution, and the authors did an excellent job addressing my concerns.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xDWh2Pcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThis paper proposes a technique for synthesis of state machine policies for a simple continuous agent, with a goal of\nthem being generalizable to out-of-distribution test conditions. The agent is modeled as a state machine with constant\nor proportional actions applied in each node (regime), and switching triggers between the regimes represented as\nlength-2 boolean conditions on the observations. The technique is evaluated on 7 classic control environments, and found\nto outperform pure-RL baselines under \"test\" conditions in most of them.\n\n# Review\n\nI am not an expert in RL-based control, although I'm familiar with the recent literature that applies formal methods to\nthese domains. I find the studied settings valuable albeit fairly limited, but the paper's method undeniably shows\nnoticeable improvement on these settings. Inductive generalization is an important problem, and the authors' approach of\nlimiting the agent structure to a particular class of state-machine policies is a reasonable solution strategy.\n\nThat said, the complexity of synthesizing a state machine policy clearly caused the authors to limit their supported\naction and condition spaces considerably (Figure 6). That, I'm assuming, limits the set of applicable control\nenvironments where optimization is still feasible. The authors don't provide any analysis of complexity or empirical\nruntime of the optimization process. Breaking it down for each benchmark would allow me to appreciate the optimization\nframework in Section 4 much more. As it stands, Section 4 describes a complex optimization process with many moving\nparts, some of which are approximated (q* and p(τ|π,x₀)) or computed via EM iteration until convergence (π*). It is hard\nto appreciate all this complexity without knowing where the challenges manifest on specific examples.\n\nSection 4.2 needs an example, to link it to the introductory example in Figure 1. The \"loop-free\" policies of the\nteacher are, in programmatic terms, _traces_ of the desired state machine execution (if I understand correctly), but\nthis is not obvious from just the formal definition.\n\nThe EM optimization for the student policy makes significant assumptions on the action/condition grammars. Namely, the\nalgorithm iterates over every possible discrete \"sketch\" of every program, and then numerically optimizes its continuous\nparameters (Appendix A). When the action/condition grammars grow, the number of possible programs there increases\ncombinatorially. Is there a way to adapt the optimization process to handle more complex grammars, possibly with\ndecomposition of the problem following the program structure?\n\nSection 5 needs a bit more details on the Direct-Opt baseline. It's unclear how the whole state machine policy (which\nincludes both discrete and continuous parts) is learned end-to-end via numerical optimization. Granted, the baseline\nperforms terribly, but would be great to understand how it models the learning problem in order to appreciate why it's\nterrible.\n\nWhy were the \"Acrobot\" and \"Mountain car\" benchmarks removed from the main presentation of results?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider control tasks that require "inductive generalization", ie                                                     
the ability to repeat certain primitive behaviors.                                                                                 
They propose state-machine machine policies, which switch between low-level                                                      
policies based on learned transition criteria.                                                                                     
The approach is tested on multiple continuous control environments and compared to                                                   
RL baselines as well as an ablation.                                                                                                          
                                                                                                                                   
The reviewers appreciated the general idea of the paper.                                                                           
During the rebuttal, the authors addressed most of the issues raised in the                                                        
reviews and hence reviewers increased their score.                                                                                 
                                                                                                                                   
The paper is marginally above acceptance.                                                                                          
On the positive side: Learning structured policies is clearly desirable but                                                        
difficult and the paper proposes an interesting set of ideas to tackle this                                                       
challenge.                                                                                                                         
My main concern about this work is:                                                                                                
The approach uses the true environment simulator, as the                                                                           
training relies on gradients of the reward function.                                                                               
This makes the tasks into planning and not an RL problems; this needs to be                                                       
highlighted, as it severly limits its applicability of the proposed approach.                                                                              
Furthermore, this also means that the comparison to the model-free PPO baselines                                                   
is less meaningful.                                                                                                                
The authors should clear mention this.                                                                                             
Overall however, I think there are enough good ideas presented here to warrant                                                     
acceptance. 
Decision: Accept (Poster)