11institutetext: Department of Applied Mathematics and Computer Science,
Technical University of Denmark, Kongens Lyngby, Denmark
11email<EMAIL_ADDRESS>
# Programmatic Policy Extraction by Iterative Local Search

Rasmus Larsen 11 0000-0001-9177-2695 Mikkel Nørgaard Schmidt 11
0000-0001-6927-8869

###### Abstract

Reinforcement learning policies are often represented by neural networks, but
programmatic policies are preferred in some cases because they are more
interpretable, amenable to formal verification, or generalize better. While
efficient algorithms for learning neural policies exist, learning programmatic
policies is challenging. Combining imitation-projection and dataset
aggregation with a local search heuristic, we present a simple and direct
approach to extracting a programmatic policy from a pretrained neural policy.
After examining our local search heuristic on a programming by example
problem, we demonstrate our programmatic policy extraction method on a
pendulum swing-up problem. Both when trained using a hand crafted expert
policy and a learned neural policy, our method discovers simple and
interpretable policies that perform almost as well as the original.

###### Keywords:

Program synthesis Reinforcement learning Hindley-Milner type system
Neighborhood search

##  1 Introduction

While neural policy representations are by far the most common in modern
Reinforcement Learning (RL), other representations are worth considering.
Programmatic policies provide a number of potential benefits: For example, a
program might be read and understood by a human, something that generally is
not possible with a neural network. Programs are also inherently
compositional, which allows for not only reuse of policies in new
combinations, but also compositional reasoning about their behavior.

However, learning programmatic policies is challenging. The structured,
discrete space of programs does not allow for the gradient based optimization
that neural policies benefit greatly from. Compared to a more standard
inductive synthesis setting, programmatic policies must be evaluated in an
environment that, whether simulated or real, is expensive to interact with.
Several approaches exist that attempt to handle this interaction issue, such
as learning a parametric environment model [6], imitating an existing policy
[1, 14], or evaluating fewer programs by learning to search more efficiently
[2]. Furthermore, [13] extend the imitation setting by providing a framework
for intertwining RL and programmatic policy imitation.

This imitation-projection framework brings us a step closer to programmatic
RL, where programs can be learned gradually through interaction with the
environment. Essentially, this allows similar sample efficiency when compared
to policy gradient methods, since the imitation-projection step is performed
offline by scoring programs according to an imitation learning objective. One
could even plausibly imagine that the inductive bias in a problem-specific
policy language could lead to improved learning. The framework leaves many
choices open in terms of how the policy update and programmatic policy
projection steps are performed, as well as in terms of defining the program
space. [13] perform experiments with a specific choice of update and
projection, using two tailored program spaces based on PID controllers with
either decision tree regression or Bayesian optimisation over some parameters
as the projection operator.

In this paper we experiment with a more general program space based on Domain
Specific Languages (DSLs) implemented in a typed lambda calculus. We
demonstrate a method for re-using projections by local search around a
previous projection, potentially reducing the required computational effort
while allowing much longer programmatic policies to be found. Since imitation-
projection greatly reduces environment interaction, the presented method takes
advantage of this and performs relatively large searches in program space.
Demonstrating the method on the pendulum swing-up task, we show that a simple
and effective programmatic policy can be found by imitating a learned neural
policy.

##  2 Methods

Our framework is based on previous work on imitation-projected and
programmatically interpretable reinforcement learning [14, 13]. We extend
these methods to DSLs defined in a general-purpose programming language,
namely the lambda calculus with Hindley-Milner type system. Using the building
block of depth-limited type-directed program search, we construct an algorithm
for finding a programmatic imitation of a given control policy. In order to
discover programs much larger than what the depth limit of a single search
allows, the algorithm performs multiple iterations of local search.

###  2.1 Program synthesis by type-directed search

By choosing the lambda calculus with Hindley-Milner type system, we obtain an
expressive program space, in which exhaustive search for programs of a
specified type is straightforwardly defined. An especially useful feature of
this program representation is that the type system can be used to reduce the
search space, by filtering candidate programs that do not type check. Further
filtering is possible, such as the filtering of semantically similar programs
as done in MagicHaskeller [9]. In this program representation, DSLs can be
defined as sets of typed functions and constants, which together represent the
space of possible programs to be searched.

Our starting point for program synthesis is a simple version of depth-limited
type-directed search. This choice is not a given; other, more advanced program
search algorithms can be used. Here, the space of all programs in a DSL is a
tree, with the empty program at the root. Internal nodes are partial programs,
with each branch being a candidate substitution for a hole in a partial
program. Enumerating through this search tree results in generating all valid
programs, according to the DSL, as the leaves of the tree.

We take advantage of the typed language to reduce the search space. Instead of
yielding all syntactically valid programs, as explained above, we want to
yield only well-typed programs. This type-directed search algorithm is the
same as used by e.g. [2] to sample programs from a prior distribution, but
instead of sampling, all programs are enumerated. To expand a node in the
search tree, a typed hole (an empty program with a type annotation) in the
corresponding partial program is selected for synthesis. Then, valid
candidates are selected from the set of all DSL candidates by unification; the
resulting context of the unification is propagated to the further expansion of
child nodes, ensuring that any constraints are satisfied. All candidates that
can produce the correct type are considered, even if they would need arguments
applied to them first.

###  2.2 Typed neighborhood

⬇

input: domain specific language $\mathcal{D}$

input: imitation dataset $\Gamma$

input: initial program $P$

output: best program in typed neighborhood $p^*$

function $N_n^d(\mathcal{D},\, P,\, l) \quad$ // generates the neighborhood
for location $l$ in $P$

return $\varnothing$ if d = 0

$T = \textsc{type}(P,\, l) \quad$ // type of expression at $l$ in $P$

$C = \\{e \,|\, e : t \in \mathcal{D} \land T \texttt{ can unify with }
\textsc{yield}(t)\\} \quad$ // everything valid from DSL

$P’ = \\{\texttt{edit}(P, l, c)) \,|\, c \in C \\}$

// return all complete programs, recursively generate partial programs

return $\\{p \in P’ \,|\, p \texttt{ is complete}\\} \cup
N_n^{d-1}(\mathcal{D}, p’, l’) \quad \forall p’ \in \\{p’ \in P’ \,|\, p’
\texttt{ is partial}\\}$

where $l’$ is the location of the first hole in $p’$

end

$p^* \leftarrow \varnothing,\, v^* \leftarrow \infty \quad$ // best program
and imitation loss

foreach $l \in $ set of all paths in $P$

$E_{l} = \textsc{expression}(P,\, l) \quad$ // expression at location

$\mathcal{D}’ = \mathcal{D} \cup \left(E_{l},\, \textsc{type}(E_{l})\right)
\quad$ // locally extend DSL with $E_l$

foreach $p \in N_n^d(\mathcal{D}’,\, P,\, l) \quad$

evaluate $p$ on $\Gamma$ and update $p^*$ and $v^*$

end

end

⬇

input: oracle policy $f$

optional input: initial program $p_{init} = \varnothing$

output: imitation program $p_K$

collect $N$ on-policy trajectories using $f$:

$\tau_0 = \left(\left(s^0_0, f(s^0_0), s^0_1, f(s^0_1), \dots\right), \dots,
\left(s^N_0, f(s^N_0), s^N_1, f(s^N_1), \dots\right)\right)$

create supervised dataset $\Gamma_0 = \left\\{\left(s, f(s)\right) | s \in \tau_0 \right\\}$

derive $p_0$ from $\Gamma_0$ by local search from $p_{init} \quad$ //
algorithm 1

for $k = 1, \dots, K$

collect $M$ on-policy trajectories using $p_{k-1}$:

$\tau_k = \left(\left(s^0_0, p_{k-1}(s^0_0), s^0_1, p_{k-1}(s^0_1),
\dots\right), \dots, \left(s^M_0, p_{k-1}(s^M_0), s^M_1, p_{k-1}(s^M_1),
\dots\right)\right)$

create supervised dataset $\Gamma’ = \left\\{\left(s, f(s)\right) | s \in \tau_k \right\\}$

aggregate datasets:

$\Gamma_k = \Gamma_{k-1} \cup \Gamma’ \quad$ // or $\Gamma_k = \Gamma_0 \cup
\Gamma’$, which is cheaper

derive $p_k$ from $\Gamma_k$ by local search from $p_{k-1} \quad$ // algorithm
1

end

In LABEL:alg:search, the type-directed depth-limited synthesis algorithm is
used to generate what we call the typed neighborhood of a given program. This
construction applies the basic synthesis algorithm in multiple places of an
existing program, resulting in a iterative local search method that can both
add and remove subprograms in each iteration. Because of this, the algorithm
can synthesize larger programs, while also benefiting from work performed in
previous iterations of the search.

In more detail, we use a tree edit operation to define the programs contained
within a typed neighborhood. Define the edit operation
$\footnotesize\texttt{edit}(P,\,l,\,P^{\prime})$ as the program obtained by
replacing the subprogram at location $l$ in program $P$ with the program
$P^{\prime}$. Given a typed DSL $\mathcal{D}$, containing functions,
constants, and their (polymorphic) types, the neighborhood of the program $P$
at location $l$ is the set of programs obtained by generating all well-typed
expressions $P^{\prime}$ contained in $\mathcal{D}$, written
$N_{n}^{d}(\mathcal{D},\,P,\,l)$. The definition of a location is the root-to-
expression path in the abstract syntax tree (AST) of the program. Here, we use
the concept of a location in a generalized manner that can encompass multiple
simultaneous locations, that is, a location $l$ can represent multiple paths
in the AST that are to be simultaneously replaced using independent edit
operations. The neighborhood of a program $P$ is thus the union of the
neighborhoods at all locations, $N_{n}^{d}(\mathcal{D},\,P)=\bigcup_{l\in
L(P)}N_{n}^{d}(\mathcal{D},\,P,\,l)$, where the neighborhood is parameterized
with a maximum depth $d$ of the expressions generated by edit operations, and
with a maximum number of simultaneous edits $n$.

Furthermore, the expression being edited is dynamically added as a candidate
to the DSL, and for the depth evaluation this candidate counts as having a
depth of 1. This allows an edit not just to replace an expression, but to also
extend an expression by using it as part of the new expression, despite the
result otherwise being too large (compared to the depth limit). The size of
the neighborhood $|N^{d}_{n}(\mathcal{D},P)|$ is quite sensitive to all
involved parameters $\mathcal{D}$, $P$, $n$, and $d$, but these can be
flexibly chosen based on the problem and available computational resources.

###  2.3 Policy extraction by local synthesis

We use the typed neighborhood to discover programs that imitate reinforcement
learning policies. In this setting, input/output examples are obtained by
executing an existing policy and storing the state observations together with
the corresponding actions chosen by the policy in each state. Thus, the policy
synthesis problem is framed as imitation learning. Like in previous policy
imitation methods, an interactive dataset aggregation method such as DAgger
[11] is used: Instead of imitating only on states that the expert experiences,
which is called behavioral cloning, some experience from the imitation policy
is periodically added to the set of states considered. This allows subsequent
imitation iterations to correct mistakes that otherwise wouldn’t be observed,
since the expert policy never experiences these mistakes. However, unless the
expert is a global optimum, it is possible that it also makes mistakes on
states which are not usually observed, and for this reason it is not always a
clear benefit. The iterative imitation approach using the typed neighborhood
is described in LABEL:alg:imitation.

One purpose of this search algorithm is to fit into the full imitation-
projection framework from [13]. A simple, modified version of this framework
is shown in LABEL:alg:ip. The difference consists of the projection step,
which now also depends on the previous projection, as enabled by
LABEL:alg:search. Compared to LABEL:alg:imitation, the main difference is that
each iteration also contains an Update step, which optimizes the expert
policy.

⬇

input: initial policy $\pi_0$

optional input: initial program $p_0 = \varnothing$

output: trained policy $\pi_J$, program $p_J$

for $j = 1, \dots, J$

$\pi_j \leftarrow \textsc{Update}(\pi_{j-1}) \quad$ // reinforcement learning,
e.g. policy gradient

$p_j \leftarrow \textsc{Project}(\pi_j,\, p_{init}=p_{j-1}) \quad$ // program
synthesis by algorithm 2

end

##  3 Experiments

We present three different program synthesis experiments: The first is a
programming by example (PBE) task with sampled ground truth programs,
demonstrating the efficacy of the local search heuristic in LABEL:alg:search.
The second is a policy extraction task, testing LABEL:alg:imitation, where the
ground truth is a hand-coded policy. In these two first experiments, the DSL
used for the search contains the true program used to generate observational
data. Finally, in our third experiment we examine if we can learn a simple yet
effective policy by imitation from a more complicated neural network policy
which is trained using an existing reinforcement learning algorithm.

###  3.1 Programming by example with local program search

Figure 1: Programming by example: Learn a program from input-output examples.
Experiment on 100 sampled programs. Left: For each program, the absolute error
(normalized wrt. first iteration) by number of programs evaluated. Right:
Mean, median, and standard deviation by search iteration.

As a first evaluation of the method, we used a straightforward PBE task, whose
purpose is to show that the described iterative local search is capable of
synthesizing nontrivial programs from input-output specifications.

DSL: We defined a language containing the set of constants
$\\{-1,\,0,\,0.5,\,0.8,\,\allowbreak 1,\,\allowbreak 3,\,\allowbreak
5,\,6,\,\operatorname*{{\footnotesize\texttt{true}}}\\}$, which are all
$\operatorname*{{\footnotesize\texttt{Float}}}$ing point numbers except
$\operatorname*{{\footnotesize\texttt{true}}}$ which is
$\operatorname*{{\footnotesize\texttt{Bool}}}$ean, and the functions with
associated type signatures
$\\{\operatorname*{{\footnotesize\texttt{if}}}:\operatorname*{{\footnotesize\texttt{Bool}}}\Rightarrow\operatorname*{{\footnotesize\texttt{T0}}}0\Rightarrow\operatorname*{{\footnotesize\texttt{T0}}}0\Rightarrow\operatorname*{{\footnotesize\texttt{T0}}}0,\,>\,:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Bool}}},\,\land\,:\operatorname*{{\footnotesize\texttt{Bool}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Bool}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Bool}}},\,\oplus:\operatorname*{{\footnotesize\texttt{Bool}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Bool}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Bool}}},\,-:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}),\,\allowbreak*:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}},\,\allowbreak\cdot^{2}\,:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\\}$.

Data: The observation space (i.e. input) to these programs consists of three
$\operatorname*{{\footnotesize\texttt{Float}}}$s, which are distinct variables
that can be used just like constants. 10 sets of these numbers were randomly
sampled as inputs to be used during synthesis. Ground truth programs of some
length, as a simple proxy for complexity, were sampled from a weighted
distribution over the DSL. In order to obtain samples that have a reasonable
length, we designed a distribution on the abstract syntax of our DSL that puts
more probability on higher-arity functions. Further, the probability of
sampling $\operatorname*{{\footnotesize\texttt{true}}}$ was weighted
significantly down, while the probability of sampling an input variable was
weighted higher. Since program length is not the best measure of complexity,
samples were rejected on other criteria as well. Programs were discarded if:
the length of the program (number of tokens) was less than 8, program output
was constant, or an input-output equivalent program, on some randomly chosen
inputs, existed within a depth 4 search of the DSL.

Results and discussion: Results from $d=4$ local search on 100 sampled ground
truth programs can be seen in fig. 1, which shows that for many of the
programs an exact fit is found on the given inputs. Even for programs where an
exact solution is not found, most of the searches show significant progress
through the iterations, although a few make no progress at all. Since the
search is deterministic, if no improvement is made in an iteration, further
iterations will not lead to better results. It should also be noted that a
single iteration of search with $d=5$ in this setting corresponds to
evaluating about as many programs as 20 iterations with $d=4$.

###  3.2 Imitation of a programmatic pendulum swing-up policy

| Imitation from programmatic policy |  | Imitation from neural policy
---|---|---|---
a) |  |  |
b) |  |  |
c) |  |  |
d) |  |  |
Figure 2: Pendulum swing-up imitation learning of a programmatic policy from a
ground truth programmatic (left) or neural (right) policy. Policies are
visualized as a heat map; the state space is pendulum angle, $\theta$, and
angular velocity, $\dot{\theta}$, and the action is pendulum torque. The goal
state is $\theta=0\pmod{2\pi}$, $\dot{\theta}=0$. a) Cumulative reward of test
trajectories. b) Ground truth programmatic/neural policy. Points indicate all
states seen during training. c) Programmatic policy found after four
iterations of imitation learning, with five test trajectories shown. d)
Programmatic policy found after several more iterations, with five test
trajectories shown.

Next we examined if we were able to discover a ground truth programmatic
policy.

Task: We based the experiment on a simple, classical control problem, the
pendulum swing-up task. The state space consists of the angle and angular
velocity of the pendulum, and the action space is the torque applied to the
base of the pendulum, normalized to the interval [-1, 1]. This two-dimensional
state space allows us to easily display and visually compare policies. The
simulator is discretized with a time step of $0.05$s, and an episode is 200
steps long. The reward function is
$r(\theta,\dot{\theta},a)=((\theta+\pi\pmod{2\pi})-\pi)^{2}+0.1\dot{\theta}+0.001a^{2}$,
which results in a reward of $0$ if the pendulum is perfectly balanced with no
torque applied, and a reward of $-\pi^{2}$ when the pendulum is pointing
straight down while not moving. While the state space of the pendulum task is
$(\theta,\dot{\theta})$, the observation space supplied to the policies is
$(\scalebox{0.85}{$\mathtt{x1,x2,x3}$})=(\sin\theta,\cos\theta,\dot{\theta})$.

DSL: We used a simple, pure DSL with primitives suitable for solving the RL
task, containing the constants $\\{-6,-1,1,0.5,0.6,8,10\\}$, and the functions
$\\{\operatorname*{{\footnotesize\texttt{if}}}:\operatorname*{{\footnotesize\texttt{Bool}}}\Rightarrow\operatorname*{{\footnotesize\texttt{T0}}}0\Rightarrow\operatorname*{{\footnotesize\texttt{T0}}}0\Rightarrow\operatorname*{{\footnotesize\texttt{T0}}}0,\,\footnotesize\texttt{gt}\,:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Bool}}},\,\footnotesize\texttt{sub}:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}},\,\footnotesize\texttt{add}:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}},\,\footnotesize\texttt{mul}:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}},\,\operatorname*{{\footnotesize\texttt{sign}}}:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}},\,\footnotesize\texttt{sqr}:\operatorname*{{\footnotesize\texttt{Float}}}\Rightarrow\operatorname*{{\footnotesize\texttt{Float}}}\\}$.

Ground truth: We hand crafted a ground truth policy in the DSL, capable of
swinging up the pendulum from any starting state. The policy achieves an
average reward of approximately -211 and a maximum of -113. This handcrafted
policy is given by the program ((if ((gt x1) 0.6)) ((sub ((mul x2) -6)) x3))
(sign ((mul ((sub ((add ((mul 0.5) (sqr x3))) ((mul ten) ((sub x1) 1)))) 8))
((mul -1) x3))).

Synthesis: At each iteration of the local search we used a search depth of
$d=4$ which was found to be enough to discover the
$\operatorname*{{\footnotesize\texttt{if}}}$ expression that switches between
swing-up and balancing. As training data we used $N=5$ state trajectories from
the ground truth policy and $M=2$ trajectories from the latest programmatic
imitation policy. All training states were expert labelled with actions from
the ground truth policy. For evaluation we simulated 100 rollouts from
uniformly random states in the range
$\tfrac{\pi}{2}\leq\theta\leq\tfrac{3\pi}{2}$, $-1\leq\dot{\theta}\leq 1$,
which is the pendulum below horizontal with relatively low velocity.

Results and discussion: The results of the experiment is shown in fig. 2 (left
column). After four iterations of imitation learning a simple policy was
found, capable of balancing the pendulum and swinging up from some states.
After approximately ten iterations the policy could effectively swing up and
balance the pendulum from any state. The imitation learning did not find the
ground truth programmatic policy by iteration 10, likely due to the small
number of observations in certain areas of the state space. Nonetheless, it
managed to synthesize an effective policy which is quite similar to the ground
truth.

###  3.3 Imitation of a neural pendulum swing-up policy

Finally, we examined if we were able to discover a simple, interpretable
policy in a more realistic setting, with synthesis by imitating a trained
neural policy. The task, DSL, and synthesis procedure were as described in the
previous experiment, with the ground truth policy as the only difference.

Ground truth: The neural ground truth policy was found by TD3 [3], using feed-
forward neural networks with 2 hidden layers of 24 neurons for both the actor
and critic. Training was run for 5 million steps with a learning rate of
$10^{-4}$ to ensure relatively good convergence.

Results and discussion: The results of the experiment is shown in fig. 2
(right column). After four iterations of imitation learning, a simple
imitating policy capable of swinging up and balancing the pendulum is found.
This imitation policy is (mul x1) (cos (exp (sign ((add x3) ((add -1) (sqr
(exp x2))))))). After several more iterations, at iteration 56, a
significantly more complicated programmatic policy was found which resembles
the neural policy more closely but yields only a minor performance
improvement, while being significantly less interpretable. This imitation
policy has a length of 121 tokens, i.e. function calls plus arguments.

##  4 Discussion

We have presented and evaluated our method with simple experiments, and much
remains to be done. As mentioned, one goal is to integrate the local search
with reinforcement learning as described by LABEL:alg:ip. While simple, we
believe that the presented results show potential, especially through the
programs that were discovered in only a few iterations. In particular, it
would be interesting to evaluate this approach on more structured tasks, where
neural networks might struggle with generalization while a program could be
found that immediately generalizes. In such a setting, we could also take
better advantage of type-directed search, with more complicated DSLs
containing e.g. logic, matrix or computer vision functions potentially still
remaining computationally tractable.

It should also be mentioned that local, iterated synthesis as a concept
remains orthogonal to several other improvements in program synthesis; for
example, enumerating or sampling programs according to a learned probability
distribution as in e.g. [2] is possible, as is better filtering as in [9].
Instead of depth-limited search, it would be possible to limit the search to
programs above a certain likelihood. However, it seems unclear how this
distribution would be effectively learned for policies.

###  4.1 Related work

Previous work on synthesizing programmatic policies at the intersection of RL
and genetic programming (GP) include GPRL [6] which is based on offline GP,
performed in a previously learned parametric model of the system of interest.
They include a comparison with behavioral cloning, i.e., direct imitation of
the actions of a trained policy. Their method performs better on the actual
(simulated, but not learned) system. It is well known that behavioral cloning
can lead to poor performance, e.g. [11], which could explain the observed
performance gap. It seems likely that interaction with the model can overcome
some of the distributional issues arising from behavioral cloning. In RL, it
might be preferable to not learn a parametric model if it is used for credit
assignment (i.e. policy learning) [5]. [4] proposed a method for using program
repair in neural program synthesis. After neural synthesis, the resulting
program might not be correct or even satisfy the input-output relation. The
authors propose to learn a neural debugger that outputs so-called edits which
correct potential errors in the program. The relation to this work is apparent
in how we use an edit operator to define the neighborhood of a program. [8]
describe a way to integrate GP, RL and simulated systems. By first
synthesizing a policy using GP in the simulated system, it can later be
adapted and fine-tuned through RL, allowing the policy to function on a real
robot. [7] describe an imitation learning method that improves the inductive
generalization by adapting the teacher distribution according to the imitating
policy. The presented neighborhood search method can be considered an instance
of the (Very) Large-Scale Neighborhood Search framework [10]. Deterministic
versions of genetic algorithms have been considered before, such as in [12].

## References

  * [1] Bastani, O., Pu, Y., Solar-Lezama, A.: Verifiable reinforcement learning via policy extraction (May 2018), http://arxiv.org/abs/1805.08328
  * [2] Ellis, K., Morales, L., Meyer, M.S., Solar-Lezama, A., Tenenbaum, J.B.: Dreamcoder: Bootstrapping domain-specific languages for neurally-guided bayesian program learning. In: Neural Abstract Machines & Program Induction Workshop at NIPS (2018)
  * [3] Fujimoto, S., van Hoof, H., Meger, D.: Addressing function approximation error in actor-critic methods (Feb 2018), http://arxiv.org/abs/1802.09477
  * [4] Gupta, K., Christensen, P.E., Chen, X., Song, D.: Synthesize, execute and debug: Learning to repair for neural program synthesis. In: Advances in Neural Information Processing Systems (Jul 2020), http://arxiv.org/abs/2007.08095
  * [5] van Hasselt, H.P., Hessel, M., Aslanides, J.: When to use parametric models in reinforcement learning? In: Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 32. Curran Associates, Inc. (2019)
  * [6] Hein, D., Udluft, S., Runkler, T.A.: Interpretable policies for reinforcement learning by genetic programming (Dec 2017), http://arxiv.org/abs/1712.04170
  * [7] Inala, J.P., Bastani, O., Tavares, Z., Solar-Lezama, A.: Synthesizing programmatic policies that inductively generalize. In: International Conference on Learning Representations, (ICLR) (2020)
  * [8] Kamio, S., Mitsuhashi, H., Iba, H.: Integration of genetic programming and reinforcement learning for real robots. In: Genetic and Evolutionary Computation — GECCO 2003. p. 470–482. Springer Berlin Heidelberg (2003)
  * [9] Katayama, S.: Efficient exhaustive generation of functional programs using Monte-Carlo search with iterative deepening, p. 199–210. Lecture notes in computer science, Springer Berlin Heidelberg (2008)
  * [10] Pisinger, D., Ropke, S.: Large Neighborhood Search, p. 399–419. Springer US (2010)
  * [11] Ross, S., Gordon, G.J., Andrew Bagnell, J.: A reduction of imitation learning and structured prediction to No-Regret online learning (Nov 2010)
  * [12] Salomon, R.: The deterministic genetic algorithm: implementation details and some results. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406). IEEE (2003). https://doi.org/10.1109/cec.1999.782001
  * [13] Verma, A., Le, H., Yue, Y., Chaudhuri, S.: Imitation-Projected programmatic reinforcement learning. In: Wallach, H., Larochelle, H., Beygelzimer, A., dÁlché-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems 32, pp. 15752–15763. Curran Associates, Inc. (2019)
  * [14] Verma, A., Murali, V., Singh, R., Kohli, P., Chaudhuri, S.: Programmatically interpretable reinforcement learning (Apr 2018), http://arxiv.org/abs/1804.02477