Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces
Authors: Tales Henrique Carvalho
Kenneth Tjhia
Levi Lelis
Venue: ICLR 2024 poster (2024)
Keywords: programmatic policy
reinforcement learning
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Recent works have introduced LEAPS and HPRL, systems that learn latent spaces of domain-specific languages, which are used to define programmatic policies for partially observable Markov decision processes (POMDPs). These systems induce a latent space while optimizing losses such as the behavior loss, which aim to achieve locality in program behavior, meaning that vectors close in the latent space should correspond to similarly behaving programs. In this paper, we show that the programmatic space, induced by the domain-specific language and requiring no training, presents values for the behavior loss similar to those observed in latent spaces presented in previous work. Moreover, algorithms searching in the programmatic space significantly outperform those in LEAPS and HPRL. To explain our results, we measured the "friendliness" of the two spaces to local search algorithms. We discovered that algorithms are more likely to stop at local maxima when searching in the latent space than when searching in the programmatic space. This implies that the optimization topology of the programmatic space, induced by the reward function in conjunction with the neighborhood function, is more conducive to search than that of the latent space. This result provides an explanation for the superior performance in the programmatic space.

Published as a conference paper at ICLR 2024
RECLAIMING THE SOURCE OF PROGRAMMATIC POLI- CIES: PROGRAMMATIC VERSUS LATENT SPACES
Tales H. Carvalho, Kenneth Tjhia, Levi S. Lelis
Amii, Department of Computing Science, University of Alberta (tal Staleshen, tihia, levi. 1 @ua berta.ca
ABSTRACT
Recent works have introduced LEAPS and HPRL. systems that learn latent spaces of domain-specific languages, which are used to define programmatic policies for partially observable Markov decision processes (POMDPs). These systems in- duce a latent space while optimizing losses such as the behavior loss, which aim to achieve locality in program behavior, meaning that vectors close in the latent space should correspond to similarly behaving programs. In this paper, that the programmatic space, induced by the domain-specifet language and requir- ing training, presents values for the behavior loss similar to those observed in latent spaces presented in previous work. Moreover, algorithms searching in the programmatic space significantly outperform those in LEAPS and HPRL. To ex- plain our results, we measured the "friendliness" of the two spaces to local search algorithms. We discovered that algorithms are more likely to stop at local max- ima when searching in the latent space than when searching in the programmatic space. This implies that the optimization topology of the programmatic space, induced by the reward function in conjunction with the neighborhood function, is more conducive to search than that of the latent space. This result provides an explanation for the superior performance in the programmatic space.
show
INTRODUCTION
Programmatic representations of policies for solving reinforcement learning problems can offer im- portant advantages over alternatives, such as neural representations. Previous work showed that due to the inductive bias of the language in which such policies are written, they tend to generalize better
to unseen scenarios (Inala et al. 2020: Trivedi et al. 2021). The programmatic nature of policies also allows modularization and reuse of parts of programs (Ellis al., 2023) Aleixo & Lelis 2023), which can speed up learning. Previous work also showed that programmatic policies can be more amenable to verification (Bastani et al., 2018) and interpretability (Verma et al. 2018 2019).
The main challenge with programmatic representations is that, in the synthesis process, one needs to search in very large and often discontinuous policy spaces. While some domain-specific languages (DSLs) are differentiable and gradient descent methods can be used (Qiu & Zhu 2022] Orfanos &
Lelis 2023). more expressive languages that allow the synthesis of policies with internal states (Inala et al. 2020 Trivedi et al. [2021] Liu et al. 2023) are often full of discontinuities, and thus one must use combinatorial search algorithms find suitable programs. In attempt to ease the process of searching for policies, recent work introduced Learning Embeddings for Latent Program Synthesis (LEAPS) (Trivedi al. 202T), a system that learns latent space of a DSL with locality program behavior. That is, if two vectors are near each other in the latent space, then they should decode to programs with similar behavior. Once the latent space is learned, LEAPS uses a local search algorithm to find a latent vector that is decoded into program encoding policy for target task. Liu et al. (2023) extended LEAPS to propose a hicrarchical framework, HPRL, to allow the synthesis of programs outside the distribution of programs used to learn the latent space.
In this paper, we evaluate local search algorithms operating in the programmatic space induced by the DSL, and compare them with LEAPS and HPRL. Searching in the original programmatic space involves defining an initial candidate solution (i.c., a program) and a neighborhood function that returns the neighbor programs of a candidate solution. We generate neighbors by following

---

Published as a conference paper at ICLR 2024
process similar to the one used in genetic programming algorithms (ozaa 1992), which was previously used in the context of programmatic policies in multi-agent settings (Medeiros et al. 2022 Aleixo & Lelis 2023 Moraes et al. 2023). We generate a number of neighbors by modifying parts of the program that represents the candidate. We hypothesized that searching for good policies in the latent space is not easier than in the original programmatic space, seen in the problems and
latent spaces considered in previous work (Trivedi et al. [202]] Liu et al.) (203)) Our rationale is that the latent spaces used in previous work are also high-dimensional and non-differentiable, given that the evaluation of latent vectors depends on the execution of the decoded program.
We tested our hypothesis using the same set of problems used to evaluate LEAPS and HPRL. We discovered that a hill- ciil-elimming algorithm in the programmatic space, HC, outperformed both LEAPS and HPRL.. HC consistently matched or exceeded the performance of the two latent-based methods. To interpret our findings, we examined the value of the behavior loss, used to learn the latent space, within the latent and programmatic spaces, and found that they are similar in each. Although loss values do not account for performance differences between the spaces, they suggest that optimizing solely for the behavior loss does not necessarily produce spaces conducive to search.
We then evaluated the "friendliness" of the two spaces for local search, which is formalized as the probability of a hill-climbing search, which is randomly initialized in the space. converging to a solution with at least given target reward value. This probability is measure of the topology of the search space for a given distribution of initial candidates, since it measures the likelihood that the search will be stuck in local maxima. We observed that the programmatic space is never worse and is often much superior to the latent space for a wide range of target reward values. These results not only support our hypothesis that searching in the programmatic space is easier than searching in the latent space, but also suggest that the programmatic space can be more conducive to search.
We conjecture that the effectiveness of latent spaces in synthesizing programmatic policies depends on two properties: how much the latent space compresses the original space and how conducive to search the space is. Intuitively, by compressing the space, the search becomes easier as one has fewer programs to evaluate; by being more conducive to search, the search signal could directly guide the search toward high-return programs. Our empirical results suggest that current systems for learning latent spaces lack either or both of these properties, since the search in the original programmatic space is more effective than the search in latent spaces. The contribution of this paper is to highlight the importance of using baseline that searches directly in the programmatic space in this line of research. Our baseline allows us to better evaluate and understand the progress in systems that search in latent spaces. The codebase used in this work is available online!
1.1 RELATED WORKS
Most of the early work programmatic policies considered stateless programs, such decision trees. For example, Verma et al. (2018) and Verma et al.] (2019) learn tree-like programs with no internal states. |Bastani al. (2018) imitation learning to induce decision trees encoding poli- cies. Qiu & Zhuj (2022) learn programmatic policies by using a language of differentiable programs, which are identical oblique decision trees. Learning programmatic policies with internal states, such as programs with while-loops, can be more challenging. This is because the search spaces are often discontinuous and thus not amenable to gradient descent optimization. Inala et al. (2020) presented an algorithm for learning policies in the form of finite-state machines, which can repre- sent loops. Similarly, Trivedi et al. (202T) and Liu et al. (2023) also consider programmatic policies with internal states, which are given by the lines in which the program stops and resumes its exe- cution while interating with the environment. There is also work on programmatic policies in the multi-agent context, where the search spaces are also discontinous and the policies are learned with combinatorial search algorithms (Medeiros et al. 2022 Alcixo & Lelis 2023 Moraes et al. 2023).
Program synthesis problems also pose problems similar to the ones we discuss WWaldinger & Lee, Solar-Lezama et al. 2006), where one must search in the programmatic spaces for a program be solved with brute-force search (Udupa et al. Albarghouthi et al. 2013) or with algorithms guided by a function that is often learned (Odena
1969
that satisfies the user's 's intent. These problems
2013
al. 2021 Barke et al. 2020 Shi al. 2022 Ellis et al.! 2023 Wong et al.) [021] Ameen & Lelis)
2023
A common method to learning such guiding functions is to use self-supervised approach
https://github...
resea rch rch/prog_policiies
2

---

Published as a conference paper at ICLR 2024
where the learning system exploits the structure of the language generate training data. Similarly to these works, LEAPS can be seen as an attempt to learn a function to help with the search in the programmatic space in the context of reinforcement learning.
2 PROBLEM FORMULATION
We consider episodic partially observable Markov decision processes (POMDPs) with deterministic dynamics, deterministic observations, and undiscounted reward functions. This setting can be de- scribed by (S, A, O O is the set of observations. The function p : A + determines the state transition dynamic of the environment, 9 S + O the observation given state and r S x A + R the reward given state and action, Finally, So defines the distribution for the initial state of an episode.
Sq). In this formulation, S is the set of states, A is the set of actions and
We consider that agents can interact in the environment following policies with internal states. The functions p. q. and r are hidden from the agent, the sense that the agent can only observe their output. Policies with internal states are defined by the function H represents the internal state the policy, initialized as a constant hgg Given an initial state So So and following the deterministic state transition 81+1 p(s,, az) and the policy (a,, h++1) T (q(s). h2) to determine the next states, we can define the trajectory as a function of the policy and initial state ( sn) (Og, al.... ar) for episode with T time steps.
O H + A x H. where
The goal of an agent acting in a POMDP is to maximize the cumulative reward over an episode. As the rewards during the episode depend uniquely the initial state so and the policy æ, can define the return of an episode as g(su, T) Σi (St, at). Our objective is to find an optimal policy x² given a policy class II.
π." arg max Eso~ [g(s0, T]]
(I)
rEll
2.1 PROGRAMMATIC POLICIES
A programmatic policy class DDSL. defines the set of policies that can be represented by program p within DSL., Figure [ shows a context-free grammar that defines the DSL for KAREI. THE ROBOT, the problem domain we use in our experiments. A context-free grammar is represented by the tuple (E, V, R, 1). Here, Σ and V are sets terminal and non-terminal symbols the grammar. R defines the set of production rules that can be used to transform non-terminal symbol into sequence of terminal and non-tente con-terminal ones. Finally. is the initial symbol of G. In Figure [ the non-terminal symbols
p, b, h and a, where & is the initial symbol; terminal symbols include WHILE, REPEAT, IF, etc. An example of a production rule is a == move, where the non-terminal is replaced by the action move. This grammar accepts strings defining functions with loops, if- statements, and Boolean functions, such as front Is IlClear, over the observation space O. The DSL also includes instructions defining actions in the action space A,, such move and t turnLeft. The policy class Dss. is defined as the set of all programs that the grammar accepts. The problem to search in the space of programmatic policies D for policy that solves Equation
Programs are represented as abstract syntax trees (ASTs). In an AST, each internal node represents a non-terminal symbol and each leaf node a terminal symbol of the grammar. Moreover, each node and its children represent a production rule. For example, for the AST shown in Figure 2 the root and its children represent the production rule p = DEF run m 8 m). The non-terminal transformed with the production rule := IF с c) i i). The Boolean expression of the if statement is given by 6 ;= and h == markersPresent Finally, the body of the statement is given by 8; 8, which branches into = PickMarker and s move.
A programmatic policy E ILSLL is a policy with internal state, where h can be interpreted as the pointer in the program p after the action taken at time step t 1. The internal state h, and the current observation (s,,) are sufficient to uniquely determine the action a, the programmatic policy returns, thus the trajectory policy generates given initial state is also deterministic.
3

---

Published as a conference paper at ICLR 2024
Program = DRF run m 8 m)
Statement = WHILE ot b c) wt w)
IF ct b c) il i)
IFELSE ct b c) 11 i) ELSE et e) REPEAT R r
8:8
Condition b h not
Number = 0..19
Perception = frcntIsclear LeftIsClear rightIsClear
markersPresent
noMarkersPresen:
Action move turnleft
turrRight
putMarker
pickMarker
Figure 1: DSL for KAREL THE ROBOT context-free grammar.
DEF run m IF c markersPresent c) i( pickMarker move
m.
Figure 2: An example of program defined in KAREL DSL (left) and its AST representation (right). In the AST, MP stands for markersPresent PM for pi ckMarker, and M for move.
3 SEARCH SPACES FOR PROGRAMMATIC POLICIES
We formalize searching for programmatic policy local search problem. This involves speci- fying a feasible set R S IpsL and a corresponding neighborhood function Ng R + R which, given a feasible solution p R, defines its K K--neihboorhodd In this work, we evaluate two search spaces: PROGR AMATIC SPACE, which uses the DSL. directly, and LATENT SPACE, which uses a learned embedding of the DSL.
3.1 PROGRAMMATIC SPACE
In this formulation, Rro is subset of the programs the DSL accepts. We define the subset Poog by imposing constraints on the size the programs. In particular, we limit the number of times the production rule s s; s (statement chaining) be used, and we also limit the height of the abstract syntax tree (AST) of every program. These constraints are the ones used to determine the distribution of programs used to train the latent space of LEAPS, which we describe in Appendix AA]
The K neighborroood of program E R T N (p), consists of K samples of mutation applied p. A mutation is defined by uniformly sampling a node n in the AST of p and removing one n's children that represents non-terminal symbol; the child that is removed is also chosen uniformily random. In this newly created "hole". we generate new sub-tree by sequentially sampling suitable production rule following the probability distribution used to generate the programs to train the latent space of LEAPS (Appendix until the newly created sub-tree does not have any leaf node representing non-terminal symbol and the resulting neighbor program is in R We ignore programs that are not in Remg through a sample rejection scheme. That is, if the neighbor of p is not in grog we sample new neighbor until we obtain one that is in Rooog
B). We continue to sample production rules from the grammar
3.2
LATENT SPACE
LEAPS (Trivedi et al. 202T) and HPRL (Liu et al. 2023) introduce a method for defining a contin- search space for programmatic policies. This is defined by variational auto-encoder (VAE),
4

---

Published as a conference paper at ICLR 2024
with encoder Q: HsLL R and decoder P: IR HDLL trained to reconstruct the text represen- tation of a program p E I.LSL. In addition to minimizing à reconstruction loss, LEAPS additionally minimizes two losses related to program behavior, ensuring that programs that yield similar trajec- tories over a set of initial states are embedded close together in the LATENT SPACE.
As the LATENT SPACE is constructed in supervised manner, it is trained sampled from a predetermined distribution. For the VAE reconstruction loss, LEAPS uses the same constraints as described for the PROGRAMMATIC SPACE and the same probabilistic DSL rules to generate a training set of programs. For training the VAE behavior losses, LEAPS generates trajec- tories by running each program from the training set on set of initial states from the environment.
of programs
Given a trained LATENT SPACE, its feasible set Rla C IpsL is the set of all programs that P can generate. Meanwhile, given a program p P(z) Rla, E Rd. each program in its K- neighborhood N (p) given by decoding z + e, where ~ (O Ila) and Ia represents the d x identity matrix. The standard deviation of the noise and the dimension d hyperparameters of the LATENT SPACE.
K
4 LOCAL SEARCH ALGORITHMS
Once the LATENT SPACE is learned, LEAPS relies on the Cross-Entropy Method (CEM) (Rubin- stein 1999) to search for a vector that will decode into a program that approximates a solution to Equation I In addition to CEM, we also consider Cross-Entropy Beam Search (CEBS), a method inspired by CEM that retains information about the best candidate solutions from a population. We also consider Hill Climbing (HC), as it is an algorithm that does not offer any mechanism for escap- ing local minima, and thus can be used to measure properties related to the space topology. In all search algorithms, we break ties arbitrarily.
Hill Climbing (HC) HC starts by sampling a candidate solution, using the probabilistic context- free grammar from Appendix [ when searching in the PROGRAMMATIC SPACE, or vector from distribution (N la) when searching in the LATENT SPACE. HC evaluates the K-neighborhood set of this initial candidate. If the neighborhood contains another candidate that yields greater episodic return on the evaluated task than the initial candidate, then this process is repeated from that neighbor. Otherwise, the algorithm returns the best-seen candidate and its episodic return.
Cross-Entropy Method (CEM) CEM generates the K neighbors of an initial candidate, whose latent is sampled from (0, Ta), and evaluates all of them in terms of episodic return. CEM then calculates the mean of the latent vectors of the candidate solutions that return the best E episodic returns, where E' is a hyperparameter defining the clite size. This process is then repeated from the resulting mean vector. CEM returns the best-found solution once a computational budget is reached.
Cross-Entropy Beam Search (CEBS) CEBS maintains a set of promising candidates, called a beam. Starting from initial candidate, CEBS generates the K neighbors and selects the best E candidates with respect to their episodic return as the beam the search. Then CEBS forms the next beam by selecting the top E candidates from the pool given by all K neighbors of the candidates in the beam. This process continues until the mean of the episodic returns seen in the beam does not increase from one iteration to the next. Appendix Crreientssessssss the pseudocode of HC and CEBS.
EXPERIMENTS
In this section, we describe our methodology for comparing the PROGRAMMATIC SPACE and the LATENT SPACE with respect to how conducive they are to local search algorithms. We have two sets of experiments. In the first set, we compare CEM searching in the LATENT SPACE, as presented in LEAPS' original paper, CEBS also searching in the LATENT SPACE, HPRL, which implements a hierarchical method over the LATENT SPACE, and HC searching in the PROGRAMMATIC SPACE. In the second set, we compare the spaces in a controlled experiment, where we fix the search algorithm to HC for both spaces. We also explain KAREL. THE ROBOT, the domain used in experiments.
5

---

Published as a conference paper at ICLR 2024
5.1 KAREL THE ROBOT DOMAIN
KAREL THE ROBOT was first introduced as a programming learning environment (Pattis] 1994) and, due to its simplified structure, it has recently been adopted as test-bed for program synthesis and reinforcement learning (Bunel et al.] 2018 Chen et al., 2018: [Shin et al. 2018) Trivedi et al. [021)) KAREL is a grid environment with local Boolean perceptions and discrete navigation actions.
To define the programmatic policy class for KAREL, we adopt the DSL of Bunel et al. (2018) (Figure D. This DSL represents subset of the original KAREI. language. Namely, it does not allow the creation of subroutines or variable assignments. The language allows the agent to ob- serve the presence of walls in the immediate neighborhood of the robot, with the perceptions [front|left right JICiearr and the presence of markers in the current robot location with markersP resent and noMarkerst preent... The agent can then move the robot with the ac- tions move and turn(Left Right), }. and interact with the markers with (put/p jpick Marker.
We consider the KAREL and KAREL-HARD problem sets to define tasks. The KAREL set contains the tasks STATRCIIMBER MAZE, FOURCORNERS, TOPÔFF, HARVESTER and CLEANHOUSE, all introduced by Trivedi et al. (202T). The KARFL-HAAR problem set includes the tasks DOORKEY, ONESTROKE, SEEDER and SNAKE, designed by Liu et al. (2023) more challenging problems. Trivedi et al. 2 showed that these domains are challenging for reinforcement learning algo- rithms using neural representations, LEAPS and HPRL represent the current state of the art in these problems. A detailed description of each task in both sets is available in Appendix D
5.2 FIRST SET: REWARD-BASED EVALUATION
Our first evaluation reproduces the experiments of Trivedi et al. (202I) and Liu et al. (2023), where we add the results of HC searching in the PROGRAMMATIC SPACE. We use K 250 as the neighborhood parameter for the HC. For CEBS, we set the dimension of the latent vector = 256, the neighborhood size K 64, the elite size E = 16, and the noise 0.25. The hyperparameters for CEM and HPRL are exactly as described in their papers.
For each method, estimate the expected return of policy by averaging the returns collected over trajectories starting from a set of initial states. In this experiment, we consider a set of 16 initial states for each problem. We limit the execution of each method to budget of 106 program evaluations. If an algorithm fails to converge but its execution is still within the budget, we re-sample an initial program and restart the search. We report results over 32 independent runs (seeds) of each method.
Table D summarizes our results in the KAREL and K KAREL-HARD problem sets, comparing them to the results reported in the papers of LEAPS and HPRL. To better outline the performance of each algorithm, we plot the reached episodic return as a function of the number of episodes in Figure and analyze the differences a harder version of the environments, which were not used in previous work, in Appendix G and study the impact of the different initialization methods in Appendix H
+
running time in Appendix E We further evaluate every method on
We see that HC, based on PROGRAMMATE SPACE, achieves the highest episodic return every task compared to all methods based on LATENT SPACE. Furthermore, the plots show that, although HC and CEBS achieve the same mean episodic return at the end of the search process for SEEDER, HC generally does so with a smaller number of samples.
We highlight the results observed on DOORKEY. This is two-stage task that requires the agent to pick up marker in a room, yielding a 0.5 reward, which opens a second room that contains a goal square, which yields extra 0.5 reward upon reaching it. LEAPS, HPRL and CEBS are only able to find programmatic policies that achieve 0.5 episodic return in this task, suggesting that their search procedures reach a local maximum that does not lead general solution. Meanwhile, HC achieves a mean episodic return that is higher than 0.5, suggesting that, in some cases, it is able to escape such local maxima and find policies that reach the final goal. We conjecture that this is a property of the search space itself, since HC does not employ mechanism to escape local maxima.
Thhe CEM curve in this plot is based our implementation of the algorithm, thus it diverges slightly from the results reported by the I.EAPS authors in few cases.

---

Published as a conference paper at ICLR 2024
LATENT
PROGRAMMATIC
Task
LEAPS
HPRL
CEBS
HC
STAIRCLIBBRR
1.00 + 0.00
1.00 + 0.00
1.00 0.00
1.00 + 0.00
MAZE
1.00 0.00
1.00 0.00
1.00 0.00
TOPOFF
0.00
1.00
1.00 0.00
FOURCORNERS
0.25
1.00
1.00
1.00 1.00
HARVESTER
0.00
1.00
1.00
1.00
CLEANHOUSE
0.00
1.00
1.00
DOORKEY
0.50
0.50 0.00
0.50
+ 0.02
ONESTROKE
0.65
0.80 0.80
0.90
0.95 = 0.00
SEEDER
0.51 0.03
0.58 0.06
1.00 0.000
1.00 = 0.00
SNAKE
0.23 + 0.06
0.33 0.07
0.26 + 0.01
0.65 + 0.03
Table I: Mean and standard error of final episodic returns of our proposed methods in KAREL and KAREL-HARD problem sets within budget of 10 program evaluations, compared to the reported results from baselines. LEAPS, HPRL, and CEBS search in LATENT SPACES, while HC searches PROGRAMMATIC SPACES. HC and CEBS results are estimated over seeds.
STAIRCLIBER
TOPOPF
HARVESTER
DOORKEY
SEEDER
1.0
0.5
Best. Episodic Return
MAZE
FOURCORNERS
CLEANHOUSE
ONESTROKE
SNAKE
1.0
0.5
0.0
10
10a
10
10
10
10
10
10a
10
10
10a
10
10
10
10
Number of Episodes
HC
CEBS
CEM
Figure 3:
Episodic return performance of all methods in KAREL and KAREL-HARD problem sets. Reported mean and 95% confidence interval over 32 seeds. The x-axis is represented in log scale.
5.3 SECOND SET: TOPOLOGY-BASER EVALUATION
To understand the discrepancy between HC the algorithms searching in the LATENT SPACES, analyze the PROGRAMMATIC and LATENT SPACE while controlling for the search algorithm.
5.3.1 LOCAL BEHAVIOR SIMILARITY ANALYSIS
We first analyze the behavior loss used to train the LATENT SPACE in the two search spaces. We define metric that measures the loss the neighborhood of randomly sampled programs search space. The similarity between two programmatic policies, and p', with trajectories from an initial state so given by T(p, so) (ap, ar) and r(p', "(p's0)) so) (al o, ... o'r.), as
psimilarity((p, s0)) max (0 < < l ao. = a' a'o..}
L
where min (T, T'} and = max(T, T'). and Øo. = (oo..... .,,...,,))))))).))).))...). normalized length of the longest common prefix of the action sequences and p' produced from 8p-
x.). The p-similarity returns the

---

Published as a conference paper at ICLR 2024
Behavior similarity
1.0
1.0
Identity rate
Programmatic Latent, g = 0.1
0.5
0.5
Latent, a 0.25
Latent, = 0.5
0.0
0.0
3
4
5
6
10
1
2
3
4
8
10
Number of mutations
Number of mutations
Figure 4: Behavior-similarity and idee metrics on PROGRAMMATES SPACE and LATENT
SPACE (o = {0.1, 0. 0.25, 0.5}). Reported mean and 95% confidence interval of the estimation of each metric over a set of 32 initial states of the environment and 1, 000 seeds for the initial programs.
The behavior-similarity of a search space defined by the neighborhood function Nx with initial program distribution Po and initial state distribution Sy is described as
behavior-similarityy NN, Pemutations) = PP
[p-similarity(Po. frstriiiii--
Pramutions 80)].
(3)
where Pragraicss is the outcome of the neighborhood function N1 (Nx with K = 1) iteratively applied mmmutations times po. thus producing path in the underlying search space.
We observe that measuring behavior-similarity alone can be misleading due to the possibility of ob- serving neighbor that provides no change the original program. We propose the metric identity- rate to complement the analysis, which measures the probability of observing program in its own candidate neighborhood. The identity-rate is defined as follows, where 1{-} the indicator function.
ratentt memutation) = Po. [P P }}.
(4)
To estimate the metries given by Equations and we sample distribution Sy and set of 1, 000 initial programs from Po. Sy is composed of random KAREL maps unrelated to any task in the problem sets, and we set P. differently for each search space. For PROGRAMO AMATIC SPACE, Po is given by the probabilistic DSL. rules from Appendix ( and for LATENT SPACE, Po is given by A (0, Ia). We run the metrics estimations as function of Temmtations
of 32 initial states from
[L, 10j and three specifications of LATENT SPACE, setting {0.1, 0.25, 0.5) hyperparameters commonly used by LEAPS and HPRL. The results are presented in Figure 4
Although the behavior-similarity metric is one of the objectives of the LATENT SPACE, the PRO- GRAMMATIC SPACE achieves comparable schavior-similane values. Although the setting o = 0.1 on LATENT SPACE achieves high behavior-similarig in practice it is not necessarily more ducive to search, possibly due to its higher identity rate. However, the observed result still does not explain the performance discrepancy that observe when searching for policies that solve tasks.
5.3.2 CONVERGENCE ANALYSIS
Next, we look at the topology of each search space with respect to the return function of the tasks we want to solve. Specifically, we want to measure how conducive a given space is to search. To do so, we use search algorithm that cannot escape local minima, HC, and measure how likely the search is to converge to a solution of a given quality in the search space of interest.
We define the convergence rate of search space given by the neighborhood function Nx. with ini- tial program distribution Po and initial state distribution So of given POMDP. The initial program distribution for the PROGRAMMATEN SPACE is given by the LEAPS probabilistic context-free gram- mar (Appendix B): for the LATENT SPACE, it is given by the programs decodes after sampling latent vector from (0, I2). The convergence rate is measured in terms Jusget E [0, 1] as follows.
convergence-rate Nx, Iarge)) Po
{greanc (po, Su) 2 Itarget }}
(5)
where Isearch (po. sp) is the return of the best- cert-performing program encountered in the search starting with candidate Po and with the return computed by rolling the policies out from 80-
8

---

Published as a conference paper at ICLR 2024
TOPOFF
HARVESTER
DOORKEY
SEEDER
1.0
0,001
Convergence rate
0.5
0.0
MAZE
FOURCORNERS
CLEANHOUSE
ONESTROKE
SNAKE
1.0
0.001
0.5
0.20.6
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Episodic return target
Programmatic
Latent
Figure 5: Convergence rate of the hill-climbing algorithm in the PROGRAMMATIC SPACE and in the LATENT SPACE with neighborhood size K 250. Reported mean and 95% confidence interval of estimation over set of 10, 000 initial candidates. The plots for DOORKEY and SNAKE show zoomed-in region highlighting runs of the search that achieve reward values larger than 0.5.
As the return of the program depends on the task we are solving, we report estimates of Equation for each task. The estimation involves sampling a of 32 states given by the task's initial state dis- tribution, and sampling 10, 000 programs to serve initial candidates for search. In this experiment, a follows the values used the original LEAPS experiments for each task: a = 0.5 for FOUR- 0.1 for MAZE, and 0.25 for all other tasks. The estimation
CORNERS and HARVESTER, of convergence-raice rate PROGRAMMATIC SPACE and LATENT SPACE, both set to a neighborhood size K 250, for every task in problem sets is shown in Figure 5 as a function of Itarget E [0, 1], using HC as the search algorithm. the figure, we show a zoomed-in plot for the tasks DOOR KEY and SNAKE better visualize cases with low convergence rate. Table and Figure show that the search in the programmatic space achieves reward values larger than 0.5 for DOORKEY and SNAKE; the zoomed-in regions Figure 5 show that these are rare events, but possible to be observed with a reasonable search budget. We show in Appendix K that policies with a return greater than 0.5 exist the LATENT SPACE for DOORKEY; it the search that failed find them. The plots show that, even in tasks where HC only matched or performed marginally better than latent methods, the PROGRAB A MMATIC SPACE is more likely to yield policies with greater episodic return. This suggests that this search space is more conducive to search algorithms than the LATRNT SPACE.
6 CONCLUSION
In this paper, showed that, despite recent efforts in learning latent spaces replace programmatic spaces, the latter can still be more conducive to search. Empirical results in KAREL THE ROBOT showed that simple hill-climbing algorithm searching the programmatic space can significantly outperform the current state-of-the-art algorithms that search in latent spaces. We measured both the learned latent space and the programmatic space in terms of the loss function used to train the former. We discovered that both have similar loss values, even though the programmatic space does not require training. We also compared the topology of the two spaces through the proba- bility of hill-climbing search being stuck at local maxima in the two spaces, and found that the programmatic space is more conducive to search. Our results suggest that the use of the original programmatic space is important baseline that suggest that learning latent spaces for casing the process of synthesizing programmatic policies for solving reinforcement learning problems is still an open and challenging research question.
missing in previous work. Our results also

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This research was supported by Canada's NSERC and the CIFAR AI Chairs program, and enabled in part by support provided by the Digital Research Alliance of Canada. We thank the reviewers for their helpful discussions and suggestions, and the Area Chair who handled our paper, for following the discussions closely and taking the time to understand the contributions our work. Finally, we also thank Matthew Guzdial and Adam White for their comments on an early version of this work.
REFERENCES
Aws Albarghouthi. Sumit Gulwani. and Zachary Kincaid. Recursive program synthesis. In Interna- tional Conference Computer Aided Verification, pp. 934-950, 2013.
David S. Aleixo and Levi H. S. Lelis. Show me the way! Bilevel search for synthesizing program- matic strategies. In Proceedings the AAAI Press, 2023.
the AAAI Conference on Artificial Intelligence, pp. 4991-4998.
Saqib Ameen and Levi H. S. Lelis. Program synthesis with best-first bottom-up search. Journal of Artificial Intelligence Research, 77:1275-1310, 08 2023.
Shraddha Barke, Hila Peleg, and Nadia Polikarpova. Just-in-time learning for bottom-up enumera- tive synthesis. Proceedings of the ACM on Programming Languages, 4:1-29, 2020.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezamp Verifiable reinforcement learning via policy extraction. In Proceedings of the International Conference on Neural Information Processing Systems, pp. 2499- 2509, 2018.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.
Xinyun Chen, Chang Liu, and Dawn Song. Execution- Execution-guided neural program synthesis. In Interna- tional Conference on Learning Representations, 2018.
Kevin Ellis, Lionel Wong, Maxwell Nye, Mathias Sabl-Meyer, Lue Cary, Lore Pozo, Luke Hewitt, Armando Solar-Lezama, and Joshua Tenenbaum. Dreamcoder: growing generalizable, inter- pretable knowledge with wake-sleep bayesian program learning. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 381, 2023.
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. International Conference on Learning Rep- resentations, 2020.
R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selec- tion. MIT Press, Cambridge, MA, 1992.
Guan-Ting Liu, En-Pei Hu, Pu-Jen Cheng, Hung-Yi Lee, and Shao-Hua Sun. Hierarchi- cal programmatic reinforcement learning via learning to compose programs. arXiv preprint arXiv:2301.12950, 2023.
Leandro C. Medeiros, David S. Aleixo, and Levi H. S. Lelis. What can learn even from the weakest? Learning sketches for programmatic strategies. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 7761-7769 AAAI Press, 2022.
Rubens O. Moraes, David Aleixo, Lucas N. Ferreira, and Levi H. S. Lelis. Choosing well your opponents: How to guide the synthesis of programmatic strategies. In Proceedings of the Inter- national Joint Conference on Artificial Intelligence, pp. 4847-4854, 2023.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. BUS- TLE: Bottom-up program synthesis through learning-guiie guided exploration. In International Con- ference Learning Representations, 2021.
10

---

Published as a conference paper at ICLR 2024
Spyros Orfanos and Levi H. S. Lelis. Synthesizing programmatic policies with actor-critic algo- rithms and relu networks, 2023.
Richard E Pattis. Karel the robot: a gentle introduction to the art of programming. John Wiley & Sons, 1994.
Wenjie Qiu and He Zhu. Programmatic reinforcement learning without oracles. In International Conference on Learning Representations, 2022.
Reuven Y. Rubinstein. The Cross-Entropy Method: A Unified Approach to Combinatorial Opti- mization, Monte-Carlo Simulation, and Machine Learning. Springer Science & Business Media, 1999.
Kensen Shi, Hanjun Dai, Kevin Ellis, and Charles Sutton. Crossheam: Learning search in bottom- up program synthesis. In International Conference on Learning Representations, 2022.
Eui Chul Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. Advances in Neural Information Processing Systems, 31, 2018
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. Combi- natorial sketching for finite programs. In Proceedings of the International Conference Archi- tectural Support for Programming Languages and Operating Systems, pp. 415. Association for Computing Machinery. 2006.
Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph Lim. Learning synthesize programs as interpretable and generalizable policies. Advances in neural information processing systems, 34: 55146-251633 2021.
Abhishek Udupa, Arun Raghavan, Jyotirmoy V. Deshmukh, Sela Mador-Haim, Milo M.K. Martin, and Rajeev Alur. Transit: Specifying protocols with concolic snippets. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 287- 296. ACM, 2013.
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, pp. 5045-5054. PMLR, 2018.
Abhinav Verma, Hoang Le, Yisong Yue, and Swarat Chaudhuri. Imitation-proojent programmatic reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Richard J. Waldinger and Richard C. T. Lec. Prow: A step toward automatic program writing. In Proceedings of the 1st International Joint Conference on Artificial Intelligence, pp. 241-252, San Francisco, CA, USA, 1969. Morgan Kaufmann Publishers Inc.
Catherine Wong, Kevin M Ellis, Joshua Tenenbaum, and Jacob Andreas. Leveraging language to learn program abstractions and search heuristics. In International Conference on Machine Learning, pp. 11193-11208 PMLR, 2021.

---

Published as a conference paper at ICLR 2024
Pr(s: = WHILE) 0.15; := IF) = 0.08; Pr(s IFELSE) = 0.04;
Pr(s = REPEAT) 0.03; Pr(s 8; = 0.5; Pr(s == == 0.2;
Pr(b = h) 0.9; Pr(b == not h ) 0.1;
Pr(n == 0) Pr(n = _... Pr(n == 19) = 1/20;
Pr(h = front.scleart 0.5; Pr(h = wee.l 0.15;
Pr(h == rightIsclear) 0.15; Pr(h makk: :al.=mmarrrsseeeent.. = 0.1;
Pr(h noMazkersPresent) - 0.1;
Pr(a == move) 0.5; wwtrttunnnee. = 0.15 Pr(c turnnnnigh 0.15;
Pr(a = pi ckMarker) = 0.1; Pr(a = putMarker) 0.1
Figure 6: Adopted probabilities for the KAREL THE ROBOT DSL probabilistic context-free grammar.
A SETTINGS FOR GENERATING PROGRAMS
In this work, we use the same constraints for generating programs as the LEAPS project (Trivedi et al. 202T), as described below.
Maximum AST height: 4;
Maximum statement chaining s; rule):
Maximum program length (in number of symbols in the program text representation): 45.
B PROBABILITIES FOR DSL PRODUCTION RULES
We adopt fixed probability for each DSL production rule, described in Figure 6 as probabilistic context-free grammar. The adopted probabilities are based on the LEAPS project specifications (Trivedi al. 2021)
C ALGORITHM DETAILS OF SEARCH ALGORITHMS
We present pseudo-code implementations of HC and CEBS as described in Section 4 in Algorithms and respectively.
Algorithm Hill Climbing for Programmatic Policies
Require: N, the neighborhood function; K, the neighborhood size; Po. the initial program distri-
bution; g: the task return function; So, the of task initial states.
Ensure: P. best-seen program with respect to highest episodic return estimate; g, estimated episodic
return of best-seen program.
1: p Po
2: g + [Sal Exee, (Tp:: so)
3: repeat
4: in_local maximum f- true
5: for each p in Nx (p) do
6:
g
150 Exees, ((Tp, so)
7:
if > 9 then
8:
0 P
9:
g 2- g
10:
+ false
11:
until local maximum = true
12

---

Published as a conference paper at ICLR 2024
Algorithm 2 Cross-Entropy Beam Search for Programmatic Policies in LATENT SPACES
Require: Nlu, the neighborhood function; K, the neighborhood size; E, the size of the beam; a, the noise parameter for the LATENT SPACE; Po. the initial program distribution; g: the task return function; Sp. the set of task initial states.
Ensure: p. best-seen program with respect return of best-seen program.
episodic return estimate: g. estimated episodic
p~ Po
2: g + [So] En [TTp so)
3:
elite return -00
4: candidates +- Nha. (p)
5: repeat
6: in local maximum + true
7: g
<+|
8:
for each p in candidates do
9:
g g.append( [ EnDes I(T,: s0))
10:
if g
1
>
then
Index -1 represents the last element in the list.
0
0+4 P
12:
6 g
clite indices < argtop-E(g E(g)
14:
if
E Eieeliteindiooss g(i
then
15:
best_meat Dest_mean_ellin mneanellitereeurr +- F. > Ligelie_jndices g|i]
16:
mn.local_maximun + false
17:
candidates < Uieelite indices Na (p(i)
Aggregates K K--nighborhood of the elite.
until local maximum true
D KAREL PROBLEM SETS
In this Section, we specify the initial state and return function of every task in KAREL and KAREL- HARD problem sets. Further details of each task are present in LEAPS (Trivedi et al. (02T) and HPRL (Liu et al., (023), works that introduced KAREL and KAREL-HARD. respectively. All tasks time out episode after 10, 000 actions.
D.I KAREL
SLAIRCL This environment is given by a 12 x 12 grid with stairs formed by walls. The agent starts on random position on the stairs and its goal initialized on the stairs. If the agent reaches the marker, the agent receives as episodic return and 0 otherwise. If the agent moves to an invalid position, i.e. outside the contour of the stairs, episode terminates with - return.
reach marker that is also randomly
MAZE A random maze is initialized on an 8 8 grid, and a random marker placed on an empty square goal. The agent starts random empty square of the grid and its goal is reach the marker goal, which yields episodic return. Otherwise, the agent receives 0 as return.
TOPOFF Markers are placed randomly on the bottom row of an empty 12 12 grid. The goal of the agent, initialized on the bottom left of the map, is to place one extra marker on top of every marker on the map. The return of the episode is given by the number of markers that have been topped off divided by the total number of markers.
FOUR Starting on a random cell on the bottom row of an empty 12 12 grid, the goal of the agent is to place one marker in each corner of the map. Return is given by the number of corners with one marker divided by four.
The agent starts random cell on the bottom row of 8 x grid, that starts with a marker on each cell. The goal the agent is to pick up every marker on the map. Return given by the number of picked-up markers divided by the total number of markers.
HARVESTER
13

---

Published as a conference paper at ICLR 2024
PROGRAMMATIC SPACE
LATENT SPACE
Elapsed time (seconds)
0.0021 + 0.0002
0.0293 = 0.0004
Table 2: Time for generating neighbor from a given candidate, measured over 1, 000 initial random candidates. Reported mean and 95% confidence interval.
CLEANHOUSE In this task, the agent starts on a fixed cell of complex 14 x 22 grid environment made of many connected rooms, with ten markers randomly placed adjacent to the walls. The goal of the agent is to pick up every marker on the map and the return is given by the number of picked-up markers divided by the total number of markers.
D.2 KAREL-HARD
DOORKEY The agent starts a random position on the left side of an 8 x 8 grid that is vertically split into two chambers. The agent goal to pick up marker on the left chamber, which opens a door connecting both chambers and allows the agent to reach goal marker. Picking up the first marker yields 0.5 reward, and reaching the goal yields an additional 0.5.
ONESTROKE Starting on random position of empty 8 x 8 grid, the goal of the agent is to visit every grid cell without repeating. Visited cells become a wall that terminates the episode upon touching. The episodic return given by the number of visited cells divided by the total number of cells the initial state.
The environment starts empty 8 grid, with the agent placed randomly in any square. The agent's 's goal is to place one marker in every empty cell the map. The return is given by the number of cells with one marker divided by the total number of empty cells at the start of the episode.
SEEDER
SNAKE In this task, the agent and one marker are randomly placed on an empty agent acts like the head of snake, whose body grows each time marker is collected. The goal of the agent is touch the marker on the map without colliding with the snake's body, which terminates the episode. Each time the marker is collected, it is placed in new random location, until 20 markers are collected. The episodic return given by number of collected markers divided by 20.
grid. The
E RUNNING TIME COMPARISON OF PROGRAMMATIC AND LATENT SPACES
In this section, we compare the neighborhood generation process of each search space in terms of rumning time. We do this by measuring the time the PROGRAMMATIC SPACE and the LATENT SPACE take to generate one neighbor from given candidate program, sampled from the initial distribution, and present the results in Table 2 is more than 10 times faster than sampling from the latent space. This means that the gap between the search in PROGRAMMATE in the paper were in terms of running time instead of episodes.
We see that sampling from the programmatic space
SPACE and LATENT SPACE would larger the results reported
F EXAMPLES OF OBTAINED SOLUTIONS
In this section, we show representative examples of programmatic policies from HC and CEBS across some relevant tasks. We selected programs that yield the highest return for each algorithm. Results are presented in Tables B and for HC and CEBS, respectively.
G EVALUATION ON CRASHABLE KAREL
To further evaluate the search algorithms, we propose a modification the KAREL environment. In this version, which name CRASHABLE, invalid actions terminate episodes. This change implies
14

---

Published as a conference paper at ICLR 2024
Task
Solution
Return
HARVESTER
DEF run m WHILE C leftIsClear c) W WHILE a leftIsClear a) w( REPEAT R=14 r( move pickMarker r) turnRight w) WHILE c( rightIsClear с) w pickMarker turnRight move turnLeft w) WHILE c frontIsClear c) W move w) m)
1.0
CLEANHOUSE
DEF run m WHILE cf leftIsClear w( move turnRight move move w) WHILE c( frontIsClear a) w( turnRight w) WHILE o( noMarkersPresent c)
1.0
( move REPEAT R=7 z( turnLeft move pickMarker r) w) move turnLeft m)
DOORKEY
DEF run m WHILE c frontIsClear c) w move w)
1.0
turnLeft move WHILE of noMarkersPresent c) w( turnRight move move w) IF c( leftIsClear c) i( pickMarker move move WHILE c( noWarkersPresent C) w move turnRight move w) putMarker i) m)
ONESTROKE
DEF run m{ IF el frontIsClear с) i turnRight i) WHILE c noMarkersPresent c) w WHILE c( frontIsClear c) w( turnRight move w) turnleft IFELSE a FrontIsClear c) il move turnRight pickMarker move move move i) ELSE e turnRight move e) w) m)
0.953
SEEDER
DEF run mf turnLeft WHILE c noMarkersPresent c) #( putMarker REPEAT R-10 r( move r) REPEAT R=5 r WHILE c markersPresent c) w( turnleft move turnRight w) PickMarker r) w) WHILE c(
1.0
frontIsClear с) w( turnLeft w) m)
SNAKE
DEF m turnLeft WHILE o( frontIsClear c) w( move w) WHILE o rightIsClear с) w WHILE a rightIsClear a front.IsClear c) i move move i) turnleft w) putMarker WHILE c rightIsClear c) w putMarker w) turnRight w) m)
1.0
move turnLeft move IF
Table 3: Representative high-return solutions from HC searches in the PROGR AMMATIC SPACE.
15

---

Published as a conference paper at ICLR 2024
Task HARVESTER
Solution
Return
DEF m WHILE c leftIsClear w move PickMarker move turnLeft pickMarker move pickMarker move turnleft move pickMarker move turnLeft move pickMarker move w) m)
1.0
CLEANHOUSE
DEF run m WHILE c noMarkersPresent c) w move pickMarker turnLeft w) WHILE c leftIsClear о) w move move w) WHILE c( frontIsClear с) w( move move w) m)
1.0
DOORKEY
DEF run m WHILE c rightIsClear с) w turnLeft 0.6875
pickMarker w) WHILE ef noMarkersPresent c) ( turnRight move w) pickMarker WHILE c( noMarkersPresent putMarker m)
turnRight move w)
ONESTROKE
DEF run m WHILE c noMarkersPresent c) W turnLeft move turnLeft WHILE o frontIsClear c) w turnLeft move w) pickMarker move move move w) WHILE c noMarkersPresent c) w ( turnleft
0.9288
move w) pickMarker move move move move m.)
SEEDER
DEF m( WHILE c noMarkersPresent. c) w( putMarker move move WHILE c( markersPresent w( turnRight move w) w) m)
1.0
SNAKE
DEF run m( WHILE e( noMarkersPresent c) W REPEAT R=13 r( IFELSE o frontIsClear c) i( turnRight move pickMarker i) ELSE e move pickMarker REPEAT R=13 r( turnRight move r) REPEAT R=13 r( pickMarker r) move e) pickMarker m)
0.4375
Table 4: Representative high-return solutions from CEBS search in LATENT SPACE.
16

---

Published as a conference paper at ICLR 2024
STAIRCLIMBER
TOPÔFF
HARVESTER
DOORKEY
SEEDER
1.0
0.5
Best Episodic Return
0.0
MAZE
FOURCORNERS
CLEANHOUSE
ONESTROKE
SNAKE
1.0
0.0
10"
10
10
10
10
10
10
10
10
10
10
10
10
10
10
Number of Episodes
HC
CEBS
CEM
Figure 7: Episodic return performance of all methods in KAREL and KAREL-HARD problem sets, using the CRASHABLE version the environment, that does not allow invalid actions. Reported mean and 95% confidence interval over 16 executions. The x-axis is represented in log scale for better visualization.
that the same tasks from KARFL and KAREL-HARD become more difficult to solve, the valid trajectories are stricter. Figure 7 outlines the episodic return performance of CEM, CEBS, and HC on the CRASHABLE version of every task of the problem sets.
The results show a greater discrepancy between the programmatic and latent methods. We conjec- ture that this is because the LATENT SPACE was trained with trajectories obtained from the original environment setting and it is unable to generalize to the CRASHABLE environment. Since the PRO- GRAMMATIC SPACE does not require any training, generalizes better to the CRASHABLE setting.
H EVALUATING THE IMPACT OF INITIALIZATION METHODS
To measure the impact of the initialization methods of the search algorithms,, we evaluate an alter- native version of all search algorithms using the initialization rule of the opposed search space. For CEM and CEBS, this version of the algorithms initializes the search with policies sampled from the defined probabilistic context-free grammar. And for HC PROGRAMMATIC SPACE, search is initialized by decoding latent sampled from (0, La) in the LATENT SPACE. Figure 8 compares the performance HC in PROGRAMMATIC SPACE with the alternative initialization scheme, while Figures 9 and 10 compare the performance of CEM and CEBS, respectively, with the alternative initialization scheme.
Results show that the performance of the alternative version of the algorithms very similar to the original algorithm in most cases, and marginally inferior others. This suggests that both initialization methods are similar and one does provide significant advantage over the other.
I CONVERGENCE RATE FOR DIFFERENT NEIGHBORHOOD SIZES
We expand the convergence rate analysis by adopting neighborhood functions NR with different neighborhood sizes K Equation (5). The convergence-rate analysis on a space given by lower K is related to how robust the search space is to conduct search process, given that it relies small number of samples. On the other hand, the result convergence-rate on higher gives us information about how capable the search space is, as it can expand search state further to find the better candidate. Figure [eguppare the convergence-rate estimation both PROGRAMMATIC and LATENT SPACE adopting K (10, 250, 1000), and suggests that the PROGRAMMATE SPACE is
17

---

Published as a conference paper at ICLR 2024
STAIRCLIBER
ТOPÖFF
HARVESTER
DOORKEY
SEEDER
1.0
0.5
Best Episodic Return
0.0
MAZE
CLEANHOUSE FORNCSRNERS
ONESTROKE
SNAKE
1.0
0.5
0.0
10
10
10
10
10
10
10
10
10
10
10a
10
10
10
10
Number of Episodes
HC
Lateatent
Figure 8: Episodic return performance of HC in PROGRAMMATIC SPACE with original and latent initialization in KAREL and KAREL-HARD problem sets. Reported mean and 95% confidence in- terval over 32 seeds. The x-axis is represented in a log scale for better visualization.
STAIRCLIMBER
TOPOFF
HARVESTER
DOORKEY
SEEDER
1.0
0.5
Best Episodic Return
0.0
MAZE
CLEANHOUSE FOURCSRNERS
ONESTRORE
SNAKE
1.0
0.5
0.0
10
103
10
10
103
10
10
10a
10
10
10a
10
10a
10a
10
Number of Episodes
CEM
CEM+
Figure 9: Episodic return performance CEM in LATENT SPACE with original and programmatic initialization in KAREL and KAREL-HARD problem sets. Reported mean and 95% confidence in- terval over 32 seeds. The x-axis is represented in a log scale for better visualization.
18

---

Published as a conference paper at ICLR 2024
STAIRCLIMDER
TOPÔFF
HARVESTER
DOORKEY
SEEDER
1.0
0.5
Best Episodic Return
0.0
MAZE
FOURCORNERS
CLEANHOUSE
ONESTROKE
SNAKE
1.0
0.0
10"
10a
10
10
10
10
10
10
10
10
10a
10
10"
10
10
Number of Episodes
CEBS
CEBS + ProgInit
Figure 10: Episodic return performance of CEBS in LATENT SPACE with original and programmatic initialization in KAREL and KAREL-HARD problem sets. Reported mean and 95% confidence in- terval over 32 seeds. The x-axis is represented in log scale for better visualization.
both more robust, evidenced by the higher convergence-rate with 10, and more capable, shown by the superior convergence-rait with K 1, 000.
J CONVERGENCE RATE OF CEM AND CEBS
We further analyze the convergence rate of the LATENT SPACE by using CEM and CEBS as the search algorithm in Equation Figure [2 compares comparess the convergence rate obtained with HC (original setting), CEM, and CEBS, with K 64 (neighborhood size). Although CEM and HC have similar convergence rate across all tasks, we see that CEBS outperforms both in H HARVESTER, DOORKEY, ONESTROKE and SEEDER. These results highlight the ability of CEBS to escape local optima. Despite the superior performance of CEBS, HC searching in the PROGRAMMATIC SPACE performs better than CEBS searching in the LATENT SPACE (see Figure 3
K VALIDATING THE EXISTENCE OF HIGH- PGGH-PERFORMING POLICIES IN LATENT SPACE
To complement the performance and topology analysis of the LATENT SPACE, we designed an additional experiment validate the existence high-performn perfforrffmin policies in the space. Specifically, we are interested in confirming if policies with an episodic return larger than 0.5 in the DOORKEY task exist the LATENT SPACE.
We start by selecting a high-pent nigh-performing policy found by searching in the PROGR AMMATIC SPACE. This policy is then encoded as a latent vector be represented the LATENT SPACE. Note that the encoded policy does not necessarily decode to the same original policy. To account for that, we use the encoded policy as the initial candidate for an HC search on LATENT SPACE with neighborhood size K 1, 000. Table shows particular choice of initial candidate that led to the discovery of a policy in the LATENT SPACE that yields an episodic return of 0. 0.71875 in KEY.
This experiment confirms that high-perfore performing policies exist in the LATENT SPACE. However, the convergence rate analysis shows that searching with HC in the space did not result in such policies, after considering 10, 0000 different search initializations.
19

---

Published as a conference paper at ICLR 2024
STAIRCLIMBER
TOPOFF
HARVESTER
DOORKEY
SEEDER
Convergence rate
0
MAZE
CLEANHOUSE
ONESTROKE
SNAKE
Episodic return target
Programmatic
Latent
(a) K = 10
STAIRCLIMBER
TOPÔFF
HARVESTER
DOORKEY
SEEDER
Convergence rate
0
MAZE
FOUNCSRNERS
CLEANHOUSE
ONESTROKE
SNAKE
1
0
0
0
0
Episodic return target
Programmatic
Latent
(b) K 250
STAIRCLIMBRR
TOPÔFF
HARVESTER
DOORKEY
SEEDER
Convergence rate
0
MAZE
FOURCORNERS
CLEANHOUSE
ONESTROKE
SNAKE
1
0
0
0
0
0
Episodic return target
Programmatic
Latent
(c) K = 1,000
Figure 11: Convergence rate of PROGRAMMATIC SPACE and LATENT SPACE with neighborhood sizes K = 10 (a), K 250 (b) and K = 1, 000 (c), guided by hill-climbing. Reported mean and 95% confidence interval of estimation over a set 250 search initializations.
20

---

Published as a conference paper at ICLR 2024
STARCLIMBER
TOPÓFF
HARVESTER
DOORKEY
SEEDER
1.0
Convergence rate
0.5
0.0
MAZE
FOURCORNERS
CLEANHOUSE
ONESTROKE
SNAKE
1.0
0.5
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Episodic return target
HC
CEM
CEBS
Figure 12: Convergence rate of LATENT SPACE with neighborhood size = 64, guided by HC, CEM, and CEBS. Reported mean and 95% confidence interval over 1, 000 seeds.
Policy
DOORKEY return
Original initial candidate
DEF run m WHILE a noMarkersPresent c) w( turnLeft pickMarker move move w) pickMarker move WHILE a noMarkersPresent c) w REPEAT R=17 r move r) move turnLeft move w)
0.9375
putMarker
Decoded initial candidate
run m WHILE o roMarkersPresent с) w turnLeft pickMarker move w) move move REPEAT R=3 r move r)
-0.5
putMarker turnLeft. m)
Search result
DEF m WHILE c( toMarkersPresent с) w turnLeft move move w) pickMarker move WHILE c( noMarkersPresent c) w turnLeft move w) WHILE c( rightIsClear c) putMarker w) m)
0.71875
Table S: Initial candidate and resulting program from searching for high-performing policy in LATENT SPACE for the DOORKET KEY task. The original initial candidate is defined in the PROGRAM- MATIC SPACE, while the decoded initial candidate and the search result are defined LATENT SPACE.
21


Reviews:
[{"review_id": "FiJjebfXIR", "reviewer": "Reviewer_xg79", "summary": "The paper compares search for programmatic policies in the policy space and the latent space. The comparison results show that the same programmatic policy space search for the same domains converges faster in the policy space than in the latent space.", "questions": "I would appreciate a detailed comparison of running times, as well as rejection rates, and everything that would provide insights on relative performance of the algorithms with the domain and policy sizes going up.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "It is very welcome, in my opinion, to have a paper that questions  advantages of a more complicated approach over a simple and straightforward one, and this is one such paper. The authors did an excellent job in planning, conducting, and visualizing the empirical evaluations. The paper also provides a well organized review of background and related work, making it easy to understand the problem for an outsider.", "weaknesses": "I think the authors miss the main point of using latent spaces instead of observable spaces for search. This is not to make the search more accurate, but rather make impossible search possible. Take, for example,  atomic physics and classical Newton's mechanics. Every problem of Newton's mechanics can, in principle, be solved within the framework of atomic physics, and the solution using atomic mechanics is likely to be more accurate, in particular when the number of atoms is relatively small. However, 1g of carbon contains ~6 * 10^23 atoms. Solving directly a problem with 10^23 variables is beyond the capacity of any modern computer; therefore, the latent space of Newton's mechanic is used instead.  There are similar examples in other areas of physics and computer science. \n\nSame goes about learning programmatic policies. As long as one can efficiently sample the K-neighborhood of a policy in the policy space, searching in the policy space is going to be more accurate and converge better than search in latent space. However, sampling even relatively longer programs becomes increasingly difficult, and intractable for real-world problems. So, showing that latent space search is worse than observable space search if you CAN search in the observable space efficiently is a trivial result. \n\nPractically talking, reports of the running time, of the search in total and of individual search steps, are not given in the paper, and I believe that, properly measured, that would provide proper insights. How does the running time depends on the program length? The program's branching factor? I would expect these dependencies to be quite steep. On the other hand, selecting a candidate latent vector in the latent space is fixed time.", "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": "", "extra_scores": {}}, {"review_id": "JQZjVmAWGH", "reviewer": "Reviewer_acX2", "summary": "The authors introduce a simple method (direct search in programmatic space ) without any deep neural netowrks for decision problems. The mehtod outperforms the neural network baselines on Karel.", "questions": "1. Please justify why the proposed method \"is able to escape such local maxima\" and \"this is a property of the search space itself”. To this reviewer, it is not straightforward. Either theoretial or numerical evidences should be provided.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors introduce a simple method without any deep neural netowrks for decision problems. The mehtod outperforms the baselines on Karel.", "weaknesses": "1. The experiment enviornment is a rather simple one and use of knowledge of the simple grid world environment reduces strength of the proposed method. \n2. Performance mismatch:  Table 1 and Figure 5 please check. \n3. Potential dependance of the performance of the algorithm on initial condidtions. Please test.", "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": "", "extra_scores": {}}, {"review_id": "g3MvjVmbJ5", "reviewer": "Reviewer_BAZd", "summary": "This paper addresses the problem of searching programmatic policies for partially observable MDP. To this end, the paper proposes to conduct the search in the programmatic space. The experiments show the search in programmatic space will bring better numerical results with higher convergence rates. I believe this work provides an interesting point of view for program search from the program space instead of the learned latent space.", "questions": "As stated above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**Motivation**\nThe motivation for synthesizing programs as a more interpretable and generalizable representation of RL policies is convincing. This paper presents an effective method to address this problem.\n\n**Experimental Analysis**\n- Studies about the experimental result are comprehensive. This paper performs different kinds of topology-based evaluation to analyze the programmatic and latent space. \n- Multiple metrics (e.g., $\\rho$-similarity, behavior-similarity, identity-rate, convergence-rate) are used to evaluate the search results from the programmatic and latent space.", "weaknesses": "**Clarity**\n\n- Details about the search in the programmatic space are not sufficient. \n- What’s the maximum length of the sampled programs?\n- What is the exact number of times the production rule s := s; s (statement chaining) can be used?\n- What is the exact height of the abstract syntax tree (AST) of every program?\n- The above settings should be “similar” to LEAPS based on the description of Section 3.1, but are they identical to all the settings used in LEAPS in all experiments? What are the actual numbers used for the search in the programmatic space?\n\n\n**Novelty & contribution**\n\n- Overall, I do not find enough novelty in this work but the overall effort of this paper is appreciated. \n\n\n**Oversell**\n\n- Because the local search in the programmatic space is not continuous, the initial candidate and the randomness of the programs sampled from the distribution will dominate the quality of the search results. However, there is no further detail about how the initial candidate is sampled and how many random seeds are used to evaluate the search result. Such ambiguity makes it hard to assess the robustness and efficacy of this work.\n- The paper makes vague promises that are either not concrete or not trivially feasible to me. For example, the authors state in Section 5.2 that if the search algorithm fails to converge but its execution is still within the budget, an initial program is re-sampled and restart the search. I am not sure how often this kind of failure would happen. Since the budget is high (10^6) in this work, the search will be like a brute-force searching paradigm if the failure rate is high.\n\n**Method**\n\n- Why use fixed random seeds for the experiments as described in Section 3.1? Will the program search in the programmatic space work properly under different initial seeds? Will HC converge in all tasks in Table 1 under different random seeds?\n- In the Hill Climbing search, how do the authors choose the best-seen candidate if all candidates have the same episodic return (e.g., 0.0)?\n- As described in the second paragraph of Section 5.2, If an algorithm fails to converge but its execution is still within the budget, an initial program is re-sampled, and restart the search. What is the failure rate of HC and CEBS in each task in Table 1?\n\n\n**Experiment details**\n\n- How many seeds are used for each algorithm in Table 1 and Figure 3,4,5?\n- The details of the initial candidate programs are missing. How is the initial candidate determined to construct the search graph for each task? How long is the initial candidate program? From what probability distribution is it sampled?\n\n**Reproducibility**\n\n- The implementation details are lacking from the main paper, which makes reproducing the results difficult. \n- No figure or pseudocode of the Hill Climbing and the Cross Entropy Beam Search is provided for the Karel environment, which makes it hard to testify and evaluate the effectiveness of the proposed method.\n- No program from the search in programmatic space is shown in the paper, making it hard to assess the efficacy of program search in the programmatic space.\n\n\n**Experimental conclusions**\n\n- The experiment about convergence analysis is not convincing and could be misleading. In Table 1, the HC can achieve a score of 0.84 on task \"DoorKey\" while the corresponding convergence rate is 0.0 beyond the episodic return of 0.5 in Figure 5 (A similar observation can also be found on task \"Snake\"). Is it a contradiction, or the result of HC in Table 1 is based on rare cases?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)