figurec [firstpage,color=gray!90,angle=0,scale=0.28,
xpos=0in,ypos=-5in]*correspondence<EMAIL_ADDRESS>
# BF++: a language for general-purpose program synthesis

Vadim Liventsev  Aki Härmä  Milan Petković

###### Abstract

Most state of the art decision systems based on Reinforcement Learning (RL)
are data-driven black-box neural models, where it is often difficult to
incorporate expert knowledge into the models or let experts review and
validate the learned decision mechanisms. Knowledge-insertion and model review
are important requirements in many applications involving human health and
safety. One way to bridge the gap between data and knowledge driven systems is
program synthesis: replacing a neural network that outputs decisions with a
symbolic program generated by a neural network or by means of genetic
programming. We propose a new programming language, BF++, designed
specifically for automatic programming of agents in a Partially Observable
Markov Decision Process (POMDP) setting and apply neural program synthesis to
solve standard OpenAI Gym benchmarks. Source code is available at
https://github.com/vadim0x60/cibi

_K_ eywords Reinforcement Learning $\cdot$ Program Synthesis $\cdot$
Programming Languages

##  1 Introduction

Reinforcement Learning (RL) has been applied successfully in fields like
Energy, Finance and Robotics [1]. However, traditional approaches to
Reinforcement Learning involve black box models that preclude any exchange of
knowledge between experts and ML algorithms. In safety-critical
fields111Safety requirements in healthcare are the main motivation for our
research. However, in this paper we use conventional OpenAI Gym benchmarks to
enable comparison between methods like Healthcare [2] the ability to
understand the decision algorithms induced by artificial intelligence, as well
as to initialize the system using expert knowledge for an acceptable baseline
performance, is required for acceptability.

In this work we focus on an alternative approach for RL based on program
induction, known as Programmatically Interpretable Reinforcement Learning [3].
We introduce BF++, a new programming language tailor-made for this approach
(section 4.1). We then demonstrate that neural program synthesis with BF++ can
solve arbitrary reinforcement learning challenges and gives us an avenue for
knowledge sharing between domain experts and data-driven models via the
mechanism of _expert inspiration_ (section 5.5).

##  2 Background

In this paper we define a Reinforcement Learning environment as Partially
Observable Markov Decision Process [4, 5]: when at step $i$ the agent takes
action $a_{i}\in A$ it has an impact on the state of the environment $s_{i}\in
S$ via distribution $p_{s}(s_{i+1}|s_{i},a_{i})$ of conditional probabilities
of possible subsequent states. State is a latent variable that the agent
cannot observe. Instead, the agent can see an observation $o_{i}\in O$ which
is a random variable that depends on the latent state via distribution
$p_{o}(o_{i}|s_{i},a_{i})$. $A$, $S$ and $O$ are sets of all possible actions,
states and observations respectively. Finally, at every step the agent
observes a reward $r_{i}=R(s_{i},a_{i})$

Given this limited toolset, without full (or any) prior knowledge of how the
agent’s actions influence the the environment (distributions
$p_{s}(s_{i+1}|s_{i},a_{i})$ and $p_{o}(o_{i}|s_{i},a_{i})$), the agent has to
come up with a strategy that will maximize $n$-step return
$R_{n}=\sum_{t=i}^{n}r_{t}$ where $n$ is the agent’s planning horizon. It is,
in the general sense, a hyperparameter, however if an environment has a limit
on how many steps an episode can last, it is reasonable to set $n$ equal to
the step limit.

Conventional solutions [6] introduce a parametrized _policy function_
$\pi_{\phi}(a|s)$ that defines agent’s behavior as a probability distribution
over actions and/or function $Q_{\phi}(a|s)$ that defines what $R_{n}$ the
agent is expecting to receive if they take action $a$. Parameters $\phi$ are
learned empirically, using gradient descent or evolutionary methods [7, 8].

This approach has been applied extensively and with great success [9] in
Partially Observable Markov Decision Process (POMDP) settings, however it does
have major limitations:

  1. 1.

The agent is defined as stateless. As such, when making a decision $a_{i}$ the
agent is unable to take into account any observations it made prior to step
$i$. Long-term dependencies like "this patient should not receive this drug
since she has shown signs of allergy when this drug was administered to her 17
iterations ago" cannot be captured by a memoryless model.

  2. 2.

The agent is represented as a set of model weights $\phi$, often with millions
of parameters. Such a program can be used as a black box decision system, but
domain experts are unable to understand and/or make their contributions to the
agent’s programming.

In this paper, we address these limitations by representing an RL agent with a
program in a specialized language, to be introduced in section 4.1, as opposed
to $\pi_{\phi}$ and $Q_{\phi}$

##  3 Related work

Despite Program Synthesis being one of the most challenging tasks in Computer
Science, many solutions exist, see [10]. They can be roughly classified by
specification modality: how are the requirements for a program to be
synthesized communicated to the generative model?

The most advanced program synthesis technology to date is deep neural network-
based language modeling [11]. This models are autocomplete engines that given
a fragment of a program, also known as a prompt, predict the fragment to
follow afterwards. Such models can be very powerful, however, the prompt is a
suboptimal form of specification, creating an open problem of prompt
engineering - generating the first fragment of the program in such a way that
it encourages the language model to write a particular prompt [12].

If the requirements are specified as a natural language description of what a
program should do, program synthesis becomes a machine translation task [13].
A neural model can be pre-trained as a language model and fine-tuned on a
translation dataset like CoNaLa [14] or, in the case of AlphaCode [15], a
dataset of competitive programming tasks and submitted solutions.

If the requirements are specified as a set of inputs to the program along with
expected outputs, the task is known as programming by example [16, 17] using
techniques like neural-guided program search [18]. One can also generate
input-output pairs artificially [19]. Models like Neural Turing Machines [20],
Memory Networks [21] and Neural Random Access Machines [22] are also trained
with input-output pairs and even though they don’t explicitly generate code,
they fit the definition of program.

In this work our goal is to synthesize programs with no explicit specification
- only an environment where the program can be tested. This task is typically
tackled with neural program synthesis [3, 23] or genetic programming [24] in a
domain-specific language, where the reward function of the POMDP is known as
the _fitness function_. However, to the best of our knowledge, there is no
programming language for POMDP settings specifically. Because of this,
applications of genetic programming for Reinforcement Learning challenges have
been limited and [23], for example, only supports non-interactive programs,
i.e. a program is a mapping from an input string to an output string.

##  4 BF++

###  4.1 BF syntax

Abolafia et al [23] picked BF222Brainfuck [25] as their language for program
synthesis for the following reasons:

  * •

In industry-grade programming languages like Python or Java program code can
contain a very large variety of characters since any of the 143859 Unicode
[26] characters can be used in string literals. In BF, however, only 8
characters can be used: they can be one-hot-encoded with vectors of size 8.

  * •

BF’s simple syntax means that an arbitrary string of valid characters is
likely to be a valid program. In more complex languages, most possible strings
result in a syntax error. A generative model being trained to write programs
in such a language risks being stuck in a long exploration phase when all the
programs it generates are invalid and it has no positive examples in the
dataset.

  * •

Despite all of the above, it is a Turing-complete language.

The simplicity of the language also means that it is relatively easy to
develop a compiler that translates programs from an industry-standard
programming languages like Java and Python to BF thus making use of the expert
knowledge existing in those languages.

In the current paper, we introduce an extended version of the original BF
language, BF++. As explained below, the extensions to the original BF syntax
are particularly useful in the RL use cases.

BF’s runtime model is inspired by the classic Turing Machine [27]: at any
point during the program’s execution, the state of the program consists of:

  * •

An infinite333If you happen to be executing a BF program on a computer with
finite memory, the tape will be finite due to your hardware limitations. tape
of cells $T$ where each cell holds an integer number.

  * •

A memory pointer $p_{T}$ that points to a certain cell in the tape (active
cell $T^{p_{T}}$).

  * •

A string of characters $C$ that represents program code.

  * •

A code pointer $p_{C}$ pointing to a character about to be executed.

The code pointer starts at the first character, then this character gets
executed and the pointer is incremented (moved to the next character). There
are 8 possible characters:

>

Move the memory pointer one cell right. $p_{T}:=p_{T}+1$

<

Move the memory pointer one cell left. $p_{T}:=p_{T}-1$

+

Increment the active cell. $T^{p_{T}}:=T^{p_{T}}+1$

-

Decrement the active cell. $T^{p_{T}}:=T^{p_{T}}-1$

.

Write $T^{p_{T}}$ from the active cell to the output stream444The definition
of input and output streams is purposefully underspecified, it may depend on
the particular implementation.

,

Read $x$ from the input stream to the active cell. $T^{p_{T}}:=x$

[

If the active cell $T^{p_{T}}=0$, jump (move $p_{C}$) to the matching $]$.

]

If the active cell $T^{p_{T}}\neq 0$, jump (move $p_{C}$) to the matching $[$

[ and ] commands constitute a loop that will be executed repeatedly until the
active cell becomes zero. They are also the only way to write a BF program
with a syntax error: a valid BF program is one that doesn’t contain non-
matching [ or ]

###  4.2 Negative values

In BF memory cells $T^{i}$ hold non-negative values only. In BF++
$T^{i}\in\mathbb{Z}$, a negation operator ~ is introduced and operators []are
redefined to loop while the active cell is non-positive, i.e.

~

If the active cell $T^{p_{T}}:=-T^{p_{T}}$.

[

If the active cell $T^{p_{T}}\geq 0$, jump (move $p_{C}$) to the matching $]$.

]

If the active cell $T^{p_{T}}<0$, jump (move $p_{C}$) to the matching $[$

This decision was taken because negative observations are common in control
problems (see section 5) as is branching on whether the observed value is
positive or negative.

###  4.3 Non-blocking action operators

The main issue of BF as a language for Reinforcement Learning is its input-
output system. It assumes that the program can freely decide on the relative
frequency of inputs to outputs. For example, the following program

+[.....,]

inputs 5 integers, outputs the 5th character it read, then goes back to the
beginning and proceeds indefinitely outputting every 5th character it inputs.
Thus it assumes a 5:1 frequency of inputs to outputs. If we simply assume that
inputs are observations and outputs are actions, such program will not be able
to operate in a POMDP environment where I/O frequency is fixed at 1:1 and the
agent that has made an observation has to act before it can make the next
observation. In other words, operators . and , are blocking: . stops program
execution and waits until new input is received to resume execution, , stops
program execution and waits until there is an opportunity to act in the
environment.

To address this, in BF++ . operator is non-blocking. It outputs the current
value of the active cell by placing it at the bottom of the action queue $S$
\- a sequence of integer numbers that represent actions the program is
planning to take in the environment. We also introduce a non-blocking operator
! that places $T^{p_{T}}$ on top of the action queue.

$\begin{array}[]{cc}.&S:=S^{\frown}(T^{p_{T}})\\\
!&S:=(T^{p_{T}})^{\frown}S\end{array}$ (1)

where $\frown$ denotes concatenation of tuples

The program can thus decide by using . or ! whether the newly added action
takes precedence over ones already in the queue. As soon as an opportunity to
act arises, the top of the action queue (item $S^{1}$ or several items
$S^{1},S^{2},\dots$, see section 5.2) defines which action the program takes
and is then removed from the queue. If $S^{k}$ does not exist (the queue is
empty or shorter than $k$) default value of $S^{k}=0$ is assumed.

, operator, on the other hand, is blocking. Thus its function is more
important than just reading an observation into memory. Executing , is when
the program moves to the next step of POMDP.

###  4.4 Virtual comma

The system where the only way to proceed to the following iteration is the ,
operator, naively implemented, means that to be successful in any POMDP
environment, a program has to contain an infinite loop with a , operator. Any
program that has a finite number of , steps will terminate prematurely in an
environment that supports arbitrarily long number of iterations. Since we
originally set out to develop a language where most random programs would be
valid, this had to be addressed.

We decided to turn any BF++ program into an infinite loop with a , operator by
default:

  1. 1.

Every BF++ program starts with a virtual , operator at address $p_{C}=-1$: it
is executed before all operators in the code of the program, they are indexed
starting from $p_{C}=0$

  2. 2.

When the code pointer $p_{C}$ reaches the end of the program it loops back to
the virtual comma $p_{C}:=-1$

Due to the virtual comma, every program starts executing with the initial
observation already stored in memory and available for branching/decision-
making.

###  4.5 Observation discretization

Another issue complicating applications of BF to Reinforcement Learning is
that since its memory tape holds only integer numbers its inputs and outputs
have to be integer as well. And this issue cannot be fixed simply by replacing
an integer tape with a tape of floating point numbers as BF’s only operations
for manipulating numbers are + and - \- increment and decrement. Non-integer
action and observation spaces are fairly common in reinforcement learning
tasks hence BF++ implements coercion mechanisms for reading and writing
continuous vectors into discrete memory.

We assume that the vector observation space $O$ is a hypercube defined as an
intersection of $n$ separate scalar observation spaces $O^{k}$ such that

$o_{1}\in O_{1}^{k},o_{2}\in O_{2}^{k},\dots,o_{n}\in
O_{n}^{k}\Leftrightarrow(o_{1},o_{2},\dots,o_{n})\in O$ (2)

This assumption theoretically excludes some possible observation spaces, but
almost all POMDP tasks discussed in the research literature and all OpenAI Gym
tasks conform to this assumption.

To write an observation onto the memory tape we the observation vector of size
$n$ is aligned with memory cells $T^{p_{T}},T^{p_{T}+1},\dots,T^{p_{T}+n-1}$
and turned into an integer with the use of $d$ discretization bins.

$T^{p_{T}+k-1}:=\min_{\omega\in 1,\dots d|o^{k}<\tau^{k}_{\omega}}\omega$ (3)

If $O^{k}$ is an interval $O^{k}=[o_{low},o_{high}]$, it is split into
discretization bins evenly, as in eq. 4:

$\tau_{\omega}=\begin{cases}o_{low}+\frac{o_{high}-o_{low}}{d}\omega,\omega=1,2,\dots,d-1\\\
+\infty,\omega=d\end{cases}$ (4)

Figure 1: Fluid discretization example in Mountain Car

Some environments, however, have unbounded observation spaces
$O^{k}=(-\infty;+\infty)$, $O^{k}=(-\infty;o_{high}]$,
$O^{k}=[o_{low};+\infty)$. This spaces are challenging because the formal
description $O^{k}$ does not in any way reflect the actual underlying
distributions of observations. It can be the case, for example, that
$O^{k}=(-\infty;+\infty)$ but most observations found in the environment fall
in the interval $O^{k}=[42;43]$. For such observation spaces, BF++ uses a
fluid discretization system that learns the true distribution of observations
online. The idea was inspired by a work of Touati et al [28], although, they
assumed that $O^{k}$ has a finite diameter and didn’t support unbounded
observation spaces. Initial thresholds $\tau_{\omega}$ can be arbitrary. With
each new observation, thresholds $\tau_{\omega}$ are readjusted so that among
$h$ prior observations, roughly $\omega$ out of $d$ observations are lower
values that $\tau_{\omega}$:

$\underset{\tau}{\text{minimize}}\sum_{\omega\in 0,1,\dots
d}|\frac{\omega}{d}-\frac{\sum_{i^{\prime}\in
i-h,i-h+1,\dots,i-1}\mathbb{I}(o_{i^{\prime}}^{k}<\tau_{\omega})}{h}|$ (5)

To solve this optimization problem, one has to sort previous $d$ observations
in ascending order so that

$\text{sort}:\\{o_{i}|i\in i-h,i-h+1,\dots,i-1\\}\longrightarrow\\{s_{i}|i\in
1,2,\dots,h\\}$ (6)

is such a bijection that $s_{1}<s_{2}<\dots<s_{h}$ holds and set

$\tau_{\omega}=s_{\lceil\frac{\omega}{d}h\rceil}$ (7)

See figure 1 for a visual example.

This system has 2 hyperparameters: $d$ and $h$. With a low $d$ a lot of the
information observed form the environment is lost, while when $d$ is in the
hunderds the generated programs can become very complex. $h$ switches between
relative and absolute observations. With a very high $h$, $\omega=0$ means
that this observation is one of the lowest that can be observed in this
environment, with $h=1$ it means that the observation is lower than the
previous one.

High values of $h$ present an additional challenge: how to correctly
discretize observation in the first $h$ iterations? We implemented burn-in:
before training or evaluation we run $h$ iterations of a random agent (see
section 4.8) to collect a history of $h$ observations and pick correct
thresholds.

###  4.6 Action coercion

A symmetrical problem arises with actions taken by the agent. Memory tape
holds integer numbers $T^{k}\in\mathbb{Z}$ and any value can be pushed onto
the action stack. However, the action that’s output to the environment has to
belong to a $N$-dimensional action space $A$, an intersection of
unidimensional action spaces $A^{k}$. The "act" operation thus includes a
coercion system and is defined as:

$\begin{array}[]{l}a^{k}:=\begin{cases}\frac{S^{k}}{d-1},A^{k}=(-\infty;+\infty)\\\
a_{\text{min}}+|\frac{S^{k}}{d-1}-a_{\text{min}}|,A^{k}=[a_{\text{min}};+\infty)\\\
a_{\text{max}}-|a_{\text{max}}-\frac{S^{k}}{d-1}|,A^{k}=(-\infty;a_{\text{max}}]\\\
a_{\text{min}}+\frac{(S^{k}\bmod
d)}{d-1}*(a_{\text{max}}-a_{\text{min}}),A^{k}=[a_{\text{min}};a_{\text{max}}]\\\
S^{k},A^{k}\subset\mathbb{Z}\end{cases}\\\
S:=(S^{N+1},S^{N+2},\dots)\end{array}$ (8)

###  4.7 Goto

It is notoriously hard to introduce any kind of branching behavior in BF [29].
To facilitate if-then style programs we introduce a goto operator `^` defined
as

$p_{T}:=T^{p_{T}}$ (9)

Note that it is not a goto; in the traditional C sense, since the memory
pointer is being moved, not the code pointer. Still, it lets the agent
preemptively store potential actions in memory cells and than branch between
this actions based on the observation.

###  4.8 Random number generator

Operator @ writes a random number into the active cell. A random agent is
often used as a starting point for exploration and in BF++ a random agent can
be implemented as `@!`

###  4.9 Shorthands

With all the commands we introduced in sections 4.1 \- 4.7 it is still
surprisingly hard to encode relatively simple decisions like "add action 5 to
the top of the action queue":

[>]+++++!

This program moves the memory pointer right until it hits a cell that contains
zero, increments it five times, and then pushes $T^{p_{T}}$ to the top of the
action queue. It also loses the current value of the memory pointer which
might be meaningful. Our experiments have shown that it takes a very long time
for the neural model to learn to write this kind of combinations.

To mitigate this issue we introduce shorthands: commands 01234 mean "write the
respective number (0,1,2,3 or 4)" into the cell and commands abcde mean "move
the memory pointer to cell a,b,c,d or e" where cells a,b,c,d and e are the
first 5 cells in the memory tape. We intentionally made the number of
shorthands equal to discretization constant $d=5$. Due to our method of
discretization of continious action spaces (see sections 4.5, 4.6) the program
will often encounter situations when it can choose between $d$ different
actions and thanks to shorthands taking them can be encoded as 1!, 2!, …

###  4.10 Summary

In total (assuming 5 shorthands) BF++ has 22 commands:

><^@+~-[].,!01234abcde

Commands `@^~01234abcde` are considered optional and can be disabled if the
task at hand calls for it. The number of shorthand commands can be increased
or decreased.

Observation discretization and action coercion techniques built into the
language mean that BF++ is compatible with any POMDP environment. However, in
practice, there is one important limitation: the complexity of the program
required to operate in an environment is directly proportional to
dimensionality of it’s action and observation spaces $A$ and $O$. If, for
example the observation space is 10000-dimensional, once an observation is
read onto tape $T$ it takes 9999 `>` operators to reach second to last
observation. Thus, in practice, BF++ should be used with low-dimensional
POMDPs.

An extension of our methodology to high-dimensional POMDPs (such as Atari
games [30], where the observation is a matrix of pixels on simulated game
screen) can be achieved by adding a scene encoder neural network that maps the
observed image to a low-dimensional vector as proposed in [31].

##  5 Experimental setup

###  5.1 Hypotheses and goals

Our experiments were designed to test the following hypotheses:

$H_{1}$

BF++ can be used in conjunction with a program synthesis algorithm to solve
arbitrary reinforcement learning challenges (POMDPs)

$H_{2}$

BF++ can be used to take a program written by an expert and use program
synthesis to automatically improve it

$H_{3}$

BF++ can be used to generate an interpretable solutions to Reinforcement
Learning Challenges that experts can learn from

$H_{4}$

Optional commands `@^~01234abcde` introduced for convenience make it easier
for experts to write programs in BF++

$H_{5}$

Optional commands `@^~01234abcde` improve the quality of programs synthesised
by neural models

Hence we

  1. 1.

Pick several commonly studied reinforcement learning environments

  2. 2.

Employ an expert555first author of this paper to write BF++ programs to solve
them

  3. 3.

Develop a program synthesis model following from [23]

  4. 4.

Compare the best programs generated by the model with expert programs in terms
of program quality

  5. 5.

Perform ablation studies: remove some of the optional commands from the
language (resulting language is called BF+), remove the expert program from
the model’s program pool, compare program quality

  6. 6.

Perform case studies: analyze programs generated by the model to gain insight
into how the model approached the problem

###  5.2 Environments

(a) CartPole-v1

(b) MountainCarContinuous-v0

(c) Taxi-v3

(d) BipedalWalker-v2

Figure 2: Selected environments, visualized

We evaluate our framework on 4 low-dimensional (see section 4.10) POMDPs
sampled from OpenAI Gym [32]
leaderboard666https://github.com/openai/gym/wiki/Leaderboard:

  1. 1.

CartPole-v1 [33]. A pole is attached to a cart. which moves along a
frictionless track. The agent observes cart position, cart velocity, pole
angle and pole velocity at tip. The goal is to keep the pole upright by
applying force between -1 and 1 to the cart. At every step the agent receives
a +1 reward for survival. The episode terminates when the pole inclines too
far.

  2. 2.

MountainCarContinuous-v0 [34]. A car is on a one-dimensional track, positioned
between two "mountains". The goal is to drive up the mountain consuming a
minimal amount of fuel by controlling the engine, setting it’s torque in the
range $[-1;1]$; however, the engine is not strong enough to scale the mountain
in a single pass. Therefore, the only way to succeed is to drive back and
forth to build up momentum. We picked MountainCarContinuous-v0 as opposed to
MountainCar-v0 to demonstrate the performance of our discretization system.

  3. 3.

Taxi-v3 [35]. There are 4 locations (labeled by different letters) and the
goal is to pick up the passenger at one location and drop him off in another
in as few timesteps as possible spending as little fuel as possible.

  4. 4.

BipedalWalker-v2. A simulated 2D robot with legs has to learn how to walk.
Moving rightwards is rewarded, falling is penalized. Observation vector
consists of speeds, angular speeds and joint positions collected by the
robot’s sensors. These observations do not, however, include any global
coordinates - they can only be inferred from sensor inputs. With action vector
of size 4 the agent controls speeds of the robots hip and knee motors.

###  5.3 Hyperparameters

For observation discretization (section 4.5) we picked $d=5$ (so that it’s
equal to the number of shorthands) and $h=500$ for our experiments, hence when
the observation is among the highest 20% of the last 500 observations it is
written into memory as 4 while if it falls between 40-th and 60-th percentiles
it is 2.

###  5.4 Expert programs

For CartPole we wrote 2 programs. One completely ignores all observations and
just alternates between "move right" and "move left":

0!,1!

Another calculates the difference between velocity of the cart and angular
velocity of the pole. If it’s positive, the cart is pushed to the right (the
cart has to catch up with the pole), if it’s negative the cart is pushed to
the left, if zero it is pushed randomly:

[a0>0>0>0>0>@>1>1>1>1>1>,>[->>-<<]>>+++++^!1]

The first part of this program sets up an action map on the tape where every
possible value of the velocity differential has a respective cell with 0, 1 or
(in the center) random number. Then `[->>-<<]` block does subtraction, `+++++`
adds 5 to the result, so that it belongs to in $0..10$ and not $-5..5$, `^`
moves the memory pointer to the correct cell in the action map and `!` puts
the action onto the action stack.

For Mountain Car we wrote an elegant algorithm that reads the observation
vector into the tape, goes to the second observation (car velocity) and
outputs it as action:

>!a

In other words, we apply motor torque in the same direction where we’re
currently headed, thus always accelerating our car. If we’re headed right,
that helps us get to the destination and if we’re headed left that helps us
get as high as possible onto the hill so that when direction reverses, the car
has more energy to push through the right hill.

For Taxi we introduce 2 programs. The first program:

  1. 1.

Finds the coordinates of the current destination (passenger to pick up or
current passenger’s destination)

  2. 2.

Subtracts the current destination

  3. 3.

Moves in the resulting direction

The problem with this approach is that it always gets stuck when it hits a
wall. To compensate for that, the second program alternates between the
strategy above (for 5 iterations) and random movements (for 5 iterations) so
that it eventually gets unstuck. See source code repository for the programs.

Optional commands `@^~01234abcde` have all been invaluable in developing these
programs - a fact in support of $H_{4}$. A more rigorous way to confirm it
would be employing several human experts to develop programs with and without
optional operators, but finding volunteer BF++ developers has proven
difficult.

Developing programs for Bipedal Walker is, unfortunately, above our expert’s
paygrade.

###  5.5 Program synthesis model

In order to train a generative model $g$ to write BF++ programs we treat the
writing process as a reinforcement learning episode in its own right [23] .
Every character of a program is an action taken by the _writer agent_ , the
programs are terminated by a NULL character. When the NULL character is
written, a _BF++ agent_ is created in the target POMDP environment (e.g.
CartPole) and sum total of rewards $Q$ collected in that episode is assigned
as a reward to the _writer agent_ for the NULL character. All other characters
are rewarded with zero.

The _writer agent’s_ policy is modeled with an LSTM [36] neural network and is
trained with a modified version of REINFORCE [37] algorithm. While standard
REINFORCE optimizes Policy Gradient:

$O_{\text{PG}}(\phi)=\mathbb{E_{\pi(C;\phi)}}(Q)$ (10)

where $\phi$ are LSTM parameters, $C$ \- program, $Q$ \- reward obtained by
the program in target environment,

we optimize

$O(\phi)=O_{PG}(\phi)+O_{PQT}(\phi)$ (11)

where

$O_{\text{PQT}}=\frac{1}{K}\sum_{k=0}^{K}\log\pi(C_{k};\phi)$ (12)

where $C_{1}$ is the best (highest $Q$) known program, $C_{2}$ \- second best,
…

Intuitively, both $O_{\text{PG}}(\phi)$ and $O_{\text{PQT}}(\phi)$ when
optimized update the weights of the LSTM so that programs that we have found
to be successful are more likely. But Policy Gradient weighs programs
proportionately to their respective rewards while PQT creates a priority queue
of the best known programs and assigns a high importance to them and zero to
the rest.

Figure 3: Neural-symbolic learning cycle [38]

$O_{\text{PQT}}$ component has been shown to have "a stabilizing affect and
helps reduce catastrophic forgetting in the policy" [23]. In addition to this,
we use $O_{\text{PQT}}$ to implement expert inspiration. By default, the
priority queue of the best known programs is initialized as an empty set. But
if expert-written programs are available, it can be prepopulated with these
programs that act as useful positive examples for teaching the _writer agent_.
This approach is used to incorporate programs from section 5.4 and transfer
knowledge from experts to the neural developer.

This approach to expert inspiration follows what’s known as neural-symbolic
learning cycle, displayed in figure 3 \- expert knowledge is represented
symbolically, in terms of a BF++ program, then a neural network is trained to
generate this program, effectively translating the expert knowledge from
symbolic into connectionist format (_representation_), the neural network
learns from reinforcement how to solve the task better than the expert
(_training_). Unlike in most neural-symbolic systems [39] that extract
knowledge from connectionist systems with algortihms like TREPAN [40] or JRip
extraction [41], the _extraction_ step is trivial since the neural network
outputs a symbolic program directly.

In all experiments below, the _writer agent_ ’s LSTM has hidden size of 50,
batch size of 4 and is trained with RMSProp [42] optimizer.

###  5.6 Stopping and Scoring

All experiments were run with an upper limit of 100000 training episodes.
Environments other than Taxi also used Exponential Variance Elimination [43]
early stopping technique - training was stopped when the postive trend in the
quality of the best found program stopped, i.e. when the exponential moving
average of program quality is lower that it was 1000 episodes ago. Agents for
Taxi are trained for a fixed number of episodes, because we noticed that in
this environment the longest part of the training process is learning to pick
up your first passenger and until that happens $Q=-200$ holds.

Once the training process is finished, we take the best known programs and
since each of them was only tested once (leading to high variance) we test
them again, averaging total rewards over 100 episodes. We use this averaged
reward to pick the best program.

###  5.7 Implementation

BF++ interpreter and the training system were written in Python with
TensorFlow for neural models. GPU resources weren’t used, because the
performance bottleneck of the system is not backpropagation but rather testing
a BF++ program in the environment, single experiment runtime was between 1
hour (CartPole) and 10 (Taxi).

##  6 Results

Table 1: Total episode reward $Q$ achieved by best programs found, averaged over 100 episodes Environment | CartPole-v1 | MountainCarContinuous-v0 | Taxi-v3 | BipedalWalker-v2
---|---|---|---|---
Random agent | 9.3 | 0 | -200 | -91.92
BF++ expert program 1 | 20.48 | -6.55 | -179.49 | -
BF++ expert program 2 | 18.23 | - | -150.44 | -
BF+ (without shorthands) LSTM | 44.55 | 91.57 | -57.93 | -91.9
BF+ (without `@^~`) LSTM | 48.14 | 81.16 | -42.21 | -31.79
BF++ LSTM | 71.38 | 88.41 | -199.82 | -26.97
BF++ LSTM with expert inspiration | 96.64 | 91.39 | -60.65 | -
Leaderboard threshold | 195 | 90 | 0 | 300

###  6.1 Quantitative results

Table 1 presents the quality metric (average 100-episode reward) of the best
program in every category, compared to that of a fully random agent and the
result required to join the OpenAI gym leaderboard for context. Note that the
expert programs used a lot of optional operators (shorthands and `@^!`), so it
wasn’t possible to implement expert inspiration with limited command sets.

These results support (see section 5.1) hypothesis $H_{1}$ \- we have obtained
functional programs for all environments, $H_{2}$ \- when expert inspiration
was used the resulting programs were better than expert programs and better
than programs generated without expert inspiration and $H_{4}$ \- ablation
studies for optional operators do indeed show that those operators are useful.

###  6.2 Case studies

We have established that the program synthesis model is able to learn from
human experts. But can experts learn from the model? ($H_{3}$) To confirm
this, we offer a detailed explanation of the most successful program of all
experiments listed in section 5.

This program scored _91.39_ on Mountain Car:

-..~+

The trailing `~` and `+` do not affect the behavior of the agent: they modify
the value of the active cell only for it to be immediately rewritten by the
virtual comma (section 4.4) before it has any chance to influence actions. One
can think about these commands as inactive genes in the DNA - we have found
many resulting programs to contain such commands. If necessary this effect can
be accounted for by incorporating program length into the loss function. So
this program is equivalent to:

-..

Figure 4: Visual summary of the strategy enacted by -.. on Mountain Car

When the virtual comma is executed, car position and car velocity are read
into memory, discretized into integers $0\dots 4$. The position is read into
the active memory cell $p_{T}$, while the velocity is in cell $p_{T}+1$. Then
the active cell is decremented and the resulting number is put onto the action
stack twice. There is 1 read operation and 2 write operations to the end of
the action stack, which introduces a delay before the actions get executed.
When it’s time to act, the number on the action stack is coerced to one of the
actions possible in this environment (0 for going left, 1 for doing nothing, 2
for right).

A strategy emerges, illustrated on figure 4, in which the car puts "going
right" onto the agenda if it’s on the far left or the center right of the
landscape, puts "going left" onto the agenda when it’s on the far right or
center left and schedules doing nothing if it’s in the center. This strategy
helps the car successfully reach the right fringe every time it is applied.

##  7 Conclusions

In this paper, we have introduced a new programming language tailored to the
task of programmatically interpretable reinforcement learning. We have shown
experimentally that this language can facilitate program synthesis as well as
knowledge transfer between expert-based systems and data-driven systems.

The results in the OpenAI gym test examples show that the proposed system is
able to find a functional solution to the problem. In some cases the
performance is similar to the best deep learning solution but the obtained
program remains still explainable. This is a very encouraging result and
suggest that the use of program induction methods may indeed be a viable way
towards explainable solutions in RL applications.

We propose the following directions for future work:

  1. 1.

Develop translation mechanisms between BF++ and other languages. Potentially,
BF++ can be used as _bytecode_ [44] for reinforcement learning. The expert
would write a program in a higher-level language and transpile it into BF++ so
that the program then can be improved with reinforcement learning.

  2. 2.

Use other neural network architectures as well as non-neural evolution methods
like genetic programming [45] in conjunction with BF++

  3. 3.

Apply the framework to problems in Healthcare where expert inspiration is
important for crossing the AI chasm [46].

  4. 4.

Use Natural Language Generation techniques to translate the BF++ code
automatically to a friendly human-readable text description as in [47, 48].

## Acknowledgements

This work was funded by the European Union’s Horizon 2020 research and
innovation programme under grant agreement n° 812882. This work is part of
"Personal Health Interfaces Leveraging HUman-MAchine Natural interactionS"
(PhilHumans) project: https://www.philhumans.eu

## References

  * Li [2019] Yuxi Li.  Reinforcement learning applications.  _CoRR_ , abs/1908.06973, 2019.  URL http://arxiv.org/abs/1908.06973.
  * Yu et al. [2019] Chao Yu, Jiming Liu, and Shamim Nemati.  Reinforcement learning in healthcare: a survey.  _arXiv preprint arXiv:1908.08796_ , 2019.
  * Verma et al. [2018] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri.  Programmatically interpretable reinforcement learning.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 5045–5054, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.  URL http://proceedings.mlr.press/v80/verma18a.html.
  * Åström [1965] K J Åström.  Optimal control of Markov processes with incomplete state information.  _Journal of Mathematical Analysis and Applications_ , 10(1):174–205, 1965.  ISSN 0022-247X.  doi: https://doi.org/10.1016/0022-247X(65)90154-X.  URL http://www.sciencedirect.com/science/article/pii/0022247X6590154X.
  * Kramer [1964] Jr Kramer, J David R.  Partially Observable Markov Processes., 1964.
  * Sutton and Barto [2017] Richard S Sutton and Andrew G Barto.  _Reinforcement Learning: An Introduction, Second edition in progress_ , volume 3.  2017\.  doi: 10.1016/S1364-6613(99)01331-5.
  * Mousavi et al. [2018] Seyed Sajad Mousavi, Michael Schukat, and Enda Howley.  Deep Reinforcement Learning: An Overview.  In _Lecture Notes in Networks and Systems_ , volume 16, pages 426–440. 2018.  doi: 10.1007/978-3-319-56991-8_32.  URL https://arxiv.org/abs/.
  * Arulkumaran et al. [2017] K. Arulkumaran, M. P. Deisenroth, M. Brundage, and A. A. Bharath.  Deep reinforcement learning: A brief survey.  _IEEE Signal Processing Magazine_ , 34(6):26–38, 2017.  doi: 10.1109/MSP.2017.2743240.
  * Kaelbling et al. [1996] Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore.  Reinforcement learning: A survey.  _Journal of artificial intelligence research_ , 4:237–285, 1996.
  * Gulwani et al. [2017] Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh.  Program synthesis.  _Foundations and Trends in Programming Languages_ , 4(1-2):1–119, 2017.  ISSN 23251131.  doi: 10.1561/2500000010.  URL www.nowpublishers.com;.
  * Chen et al. [2021] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba.  Evaluating large language models trained on code.  _CoRR_ , abs/2107.03374, 2021.  URL https://arxiv.org/abs/2107.03374.
  * [12] The unreasonable effectiveness of language models for source code · vadim liventsev.  https://vadim.me/posts/unreasonable/.  (Accessed on 07/08/2022).
  * Xu et al. [2017] Xiaojun Xu, Chang Liu, and Dawn Song.  Sqlnet: Generating structured queries from natural language without reinforcement learning.  _CoRR_ , abs/1711.04436, 2017.  URL http://arxiv.org/abs/1711.04436.
  * Yin et al. [2018] Pengcheng Yin, Bowen Deng, Edgar Chen, Bogdan Vasilescu, and Graham Neubig.  Learning to mine aligned code and natural language pairs from stack overflow.  In _International Conference on Mining Software Repositories_ , MSR, pages 476–486. ACM, 2018.  doi: https://doi.org/10.1145/3196398.3196408.
  * Li et al. [2022] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals.  Competition-level code generation with alphacode, 2022.  URL https://arxiv.org/abs/2203.07814.
  * Kant [2018] Neel Kant.  Recent Advances in Neural Program Synthesis.  2018\.  URL http://arxiv.org/abs/1802.02353.
  * Polozov and Gulwani [2015] Oleksandr Polozov and Sumit Gulwani.  Flashmeta: A framework for inductive program synthesis.  In _Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications_ , OOPSLA 2015, page 107–126, New York, NY, USA, 2015. Association for Computing Machinery.  ISBN 9781450336895.  doi: 10.1145/2814270.2814310.  URL https://doi.org/10.1145/2814270.2814310.
  * Vijayakumar et al. [2018] Ashwin K Vijayakumar, Dhruv Batra, Abhishek Mohta, Prateek Jain, Oleksandr Polozov, and Sumit Gulwani.  Neural-guided deductive search for real-time program synthesis from examples.  In _6th International Conference on Learning Representations, ICLR 2018 - Conference Track Proceedings_ , 2018.  URL https://microsoft.github.io/prose/impact/.
  * Shin et al. [2019] Richard Shin, Neel Kant, Kavi Gupta, Christopher Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song.  Synthetic datasets for neural program synthesis.  Technical report, 2019.
  * Zaremba and Sutskever [2015] Wojciech Zaremba and Ilya Sutskever.  Reinforcement learning neural turing machines.  _CoRR_ , abs/1505.00521, 2015.  URL http://arxiv.org/abs/1505.00521.
  * Weston et al. [2015] Jason Weston, Sumit Chopra, and Antoine Bordes.  Memory networks.  In _3rd International Conference on Learning Representations, ICLR 2015 - Conference Track Proceedings_ , oct 2015.  URL http://arxiv.org/abs/1410.3916.
  * Kurach et al. [2016] Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever.  Neural random-access machines.  In _4th International Conference on Learning Representations, ICLR 2016 - Conference Track Proceedings_ , 2016.
  * Abolafia et al. [2018] Daniel A. Abolafia, Mohammad Norouzi, Jonathan Shen, Rui Zhao, and Quoc V. Le.  Neural Program Synthesis with Priority Queue Training.  2018\.  URL http://arxiv.org/abs/1801.03526.
  * Ahvanooey et al. [2019] Milad Taleby Ahvanooey, Qianmu Li, Ming Wu, and Shuo Wang.  A survey of genetic programming and its applications.  _KSII Transactions on Internet and Information Systems (TIIS)_ , 13(4):1765–1794, 2019.
  * Muller [1993] U. Muller.  Brainfuck – an eight-instruction turing-complete programming language.  Available at the internet address http://en.wikipedia.org/wiki/Brainfuck, 1993.  URL http://en.wikipedia.org/wiki/Brainfuck.
  * Allen et al. [2012] Julie D Allen, Deborah Anderson, Joe Becker, Richard Cook, Mark Davis, Peter Edberg, Michael Everson, Asmus Freytag, Laurentiu Iancu, Richard Ishida, et al.  The unicode standard.  _Mountain view, CA_ , 2012.
  * Turing [1938] A M Turing.  On computable numbers, with an application to the entscheidungsproblem. a correction.  _Proceedings of the London Mathematical Society_ , s2-43(1):544–546, 1938.  ISSN 1460244X.  doi: 10.1112/plms/s2-43.6.544.
  * Touati et al. [2020] Ahmed Touati, Adrien Ali Taiga, and Marc G Bellemare.  Zooming for efficient model-free reinforcement learning in metric spaces.  _arXiv preprint arXiv:2003.04069_ , 2020.
  * Linander [2016] Mats Linander.  control flow in brainfuck | matslina, 2016.  URL http://calmerthanyouare.org/2016/01/14/control-flow-in-brainfuck.html.
  * Bellemare et al. [2013] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling.  The arcade learning environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, jun 2013.
  * Kimura [2018] Daiki Kimura.  Daqn: Deep auto-encoder and q-network.  _arXiv preprint arXiv:1806.00630_ , 2018.
  * Brockman et al. [2016] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  _CoRR_ , abs/1606.01540, 2016.  URL http://arxiv.org/abs/1606.01540.
  * Barto et al. [1983] A. G. Barto, R. S. Sutton, and C. W. Anderson.  Neuronlike adaptive elements that can solve difficult learning control problems.  _IEEE Transactions on Systems, Man, and Cybernetics_ , SMC-13(5):834–846, Sep. 1983.  ISSN 2168-2909.  doi: 10.1109/TSMC.1983.6313077.
  * Moore [1990] Andrew William Moore.  Efficient memory-based learning for robot control.  Technical report, 1990.
  * Dietterich [2000] Thomas G. Dietterich.  Hierarchical reinforcement learning with the maxq value function decomposition.  _Journal of Artificial Intelligence Research_ , 13:227–303, 2000.
  * Gers et al. [1999] Felix A Gers, Jürgen Schmidhuber, and Fred Cummins.  Learning to forget: Continual prediction with lstm.  1999\.
  * Williams [1992] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3-4):229–256, 1992.
  * Bader and Hitzler [2005] Sebastian Bader and Pascal Hitzler.  Dimensions of neural-symbolic integration-a structured survey.  _arXiv preprint cs/0511042_ , 2005.
  * Besold et al. [2017] Tarek R Besold, Artur d’Avila Garcez, Sebastian Bader, Howard Bowman, Pedro Domingos, Pascal Hitzler, Kai-Uwe Kühnberger, Luis C Lamb, Daniel Lowd, Priscila Machado Vieira Lima, et al.  Neural-symbolic learning and reasoning: A survey and interpretation.  _arXiv preprint arXiv:1711.03902_ , 2017.
  * França et al. [2015] Manoel Vitor Macedo França, Artur S d’Avila Garcez, and Gerson Zaverucha.  Relational knowledge extraction from neural networks.  In _CoCo@ NIPS_ , 2015.
  * Svatoš et al. [2019] Martin Svatoš, Gustav Šourek, and Filip Železný.  Revisiting neural-symbolic learning cycle.  In _14TH INTERNATIONAL WORKSHOP ON NEURAL-SYMBOLIC LEARNING AND REASONING_ , 2019.  URL https://sites.google.com/view/nesy2019/home.
  * Tieleman and Hinton [2012] T. Tieleman and G. Hinton.  Lecture 6.5—RmsProp: Divide the gradient by a running average of its recent magnitude.  COURSERA: Neural Networks for Machine Learning, 2012.
  * Liventsev [2021] Vadim Liventsev.  vadim0x60/evestop: Early stopping with exponential variance elmination.  https://github.com/vadim0x60/evestop, 2021.  (Accessed on 01/20/2021).
  * Wikipedia contributors [2020] Wikipedia contributors.  Bytecode — Wikipedia, the free encyclopedia, 2020.  URL https://en.wikipedia.org/w/index.php?title=Bytecode&oldid=995026385.  [Online; accessed 21-January-2021].
  * Poli et al. [2008] Riccardo Poli, William B Langdon, Nicholas F McPhee, and John R Koza.  _A field guide to genetic programming_.  Lulu. com, 2008.
  * Keane and Topol [2018] P. A. Keane and E. J. Topol.  With an eye to AI and autonomous diagnosis.  _NPJ Digit Med_ , 1:40, 2018.  [PubMed Central:PMC6550235] [DOI:10.1038/s41746-018-0048-y] [PubMed:29618526].
  * Richardson et al. [2017] Kyle Richardson, Sina Zarrieß, and Jonas Kuhn.  The code2text challenge: Text generation in source code libraries.  _CoRR_ , abs/1708.00098, 2017.  URL http://arxiv.org/abs/1708.00098.
  * LeClair et al. [2019] A. LeClair, S. Jiang, and C. McMillan.  A neural model for generating natural language summaries of program subroutines.  In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_ , pages 795–806, 2019.  doi: 10.1109/ICSE.2019.00087.