Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search

## Abstract

Abstract Programmatic reinforcement learning (PRL) has been explored for representing policies through programs as a means to achieve interpretability and generalization. Despite promising outcomes, current state-of-the-art PRL methods are hindered by sample inefficiency, necessitating tens of millions of program-environment interactions. To tackle this challenge, we introduce a novel LLM-guided search framework (LLM-GS). Our key insight is to leverage the programming expertise and common sense reasoning of LLMs to enhance the efficiency of assumption-free, random-guessing search methods. We address the challenge of LLMs’ inability to generate precise and grammatically correct programs in domain-specific languages (DSLs) by proposing a Pythonic-DSL strategy – an LLM is instructed to initially generate Python codes and then convert them into DSL programs. To further optimize the LLM-generated programs, we develop a search algorithm named Scheduled Hill Climbing, designed to efficiently explore the programmatic search space to improve the programs consistently. Experimental results in the Karel domain demonstrate our LLM-GS framework’s superior effectiveness and efficiency. Extensive ablation studies further verify the critical role of our Pythonic-DSL strategy and Scheduled Hill Climbing algorithm. Moreover, we conduct experiments with two novel tasks, showing that LLM-GS enables users without programming skills and knowledge of the domain or DSL to describe the tasks in natural language to obtain performant programs.

### 1 Introduction

Deep reinforcement learning (DRL) has achieved great success from beating the world champion in Go (Silver et al., ) to powering the frontier natural language assistants (Ouyang et al., ; Bai et al., ), and demonstrated great potential in robotics (Jain et al., ), autonomous vehicles (Wang et al., ), and recommendation systems (Chen et al., ).
However, approximating a policy using a deep neural network makes the decision-making process a black box and, therefore, less interpretable and trustable to human users (Heuillet et al., ).
Subsequently, carefully designed tools and costly human intervention are often required to deploy trustworthy DRL systems (Doshi-Velez and Kim, ).
Moreover, DRL frequently encounters substantial performance declines when applied to previously unseen scenarios (Kirk et al., ; Cobbe et al., ), revealing another aspect of its challenges in generalization.

Recent programmatic reinforcement learning (PRL) methods have explored representing an RL policy using a program (Andre and Russell, ; Verma et al., ; Bastani et al., ; Silver et al., ).
Instead of learning a state-to-action mapping as in DRL, PRL synthesizes programs written in Domain-Specific Languages (DSLs) as human-readable policies that can be parsed and executed, making human inspection possible as an extra safety guard.
Moreover, such structured program policies are shown to be able to capture high-level task-solving ideas, allowing for generalizing to a wide range of task variants (Trivedi et al., ).
Despite the encouraging results, the state-of-the-art PRL algorithms are notoriously inefficient and require tens of millions of program execution in environments (Trivedi et al., ; Liu et al., ; Carvalho et al., ).
Under the hood, they are search or RL algorithms without any assumption to the targeting problems.
On the one hand, this allows generalization to all kinds of problems; on the other hand, the search time grows exponentially with increasing DSL complexity, making it intolerable for any practical use case.

Our key insight is that there is likely only a limited set of problems corresponding to specific program policies that are of human interest – hence, we can utilize reasonable assumptions to prune the search space.
Recently, large language models (LLMs) have been demonstrated to possess internet-scale knowledge that can be retrieved by a natural language interface (Wang et al., ; Zheng et al., ; Taylor et al., ). If we view the text on the internet as a “text projection” of human civilization, an LLM as a knowledge base should be able to provide hints to “prune” the program search paths that are out of the “human interest scope”.
With this intuition, we conjecture LLMs can be utilized to bootstrap the sample efficiency of search-based PRL algorithms, pushing PRL one step closer to practical adoption.

To this end, we aim to develop a PRL framework that utilizes LLMs to produce task-solving program policies while minimizing the number of program executions in environments.
Directly instructing LLMs to synthesize DSL programs for solving PRL tasks faces three fundamental challenges:
(1) LLMs may lack the domain knowledge of the PRL tasks, *e.g*., environment dynamics, what an agent can obverse or how it can act,
(2) the training data of modern LLMs are mostly natural language texts and general-purpose programming languages, *e.g*., Python and C++, which can be quite different from the DSLs used in PRL,
and (3) there is no apparent mechanism for directly and iteratively optimizing LLMs to produce programs that maximize rewards since the best-performing LLMs are privately owned, *e.g*., GPT-4 (Achiam et al., ).

To combat these challenges, we present an LLM-guided search (LLM-GS) framework leveraging the programming skills and common sense of LLMs and the effectiveness of search algorithms.
(1) To familiarize LLMs with PRL tasks, we devise domain and task-aware prompts that convey PRL domain knowledge to LLMs while avoiding leaking task-solving information.
(2) To mitigate the gap between general-purpose programming languages and DSLs, we design a Pythonic-DSL strategy that allows LLMs to generate more precise and grammatically correct DSL programs by first producing Python programs.
(3) To further optimize the LLM-generated programs, we propose a search algorithm, Scheduled Hill Climbing (Scheduled HC), to efficiently improve programs.

We compare our proposed LLM-GS framework in the Karel domain to various existing PRL methods (Trivedi et al., ; Liu et al., ; Carvalho et al., ).
The experimental results demonstrate that LLM-GS is significantly more effective and efficient than the existing methods.
Extensive ablation studies show that
(1) our proposed Pythonic-DSL strategy leads to a higher ratio of executable
(*i.e*. grammatically correct)
programs and a higher average return compared to directly generating DSL programs,
(2) our proposed search method, Scheduled HC, achieves the best efficiency among existing search algorithms,
(3) initializing the search population of Scheduled HC using LLM-generated programs is significantly more efficient than randomly sampled programs.
To evaluate whether LLM-GS is useful to users without knowledge of the Karel domain and DSL, we additionally design two novel tasks and only provide LLM-GS with task descriptions while fixing the domain and DSL prompts.
The experiment results show that LLM-GS still achieves significantly improved sample efficiency, highlighting the extensibility of our proposed framework.

### 2 Related work

Programmatic reinforcement learning (PRL).
PRL represents RL policies using more structured and potentially more interpretable and generalizable representations, such as decision tree (Bastani et al., ), state machine (Inala et al., ; Koul et al., ; Lin et al., ), symbolic expression (Verma et al., ; ; Bhupatiraju et al., ; Landajuela et al., ), Logic programming language (Jiang and Luo, ), and program written in domain-specific language (DSL) (Andre and Russell, ; Silver et al., ; Sun et al., ; Zhu et al., ; Qiu and Zhu, ; Moraes and Lelis, ; Mariño et al., ; Trivedi et al., ; Liu et al., ; Carvalho et al., ).
Trivedi et al. (); Liu et al. () devised PRL tasks in the Karel domain (Pattis, ) and proposed learning embedding spaces of programs using variational autoencoders (Kingma and Welling, ) and then optimizing program embeddings using cross-entropy method or RL.
Carvalho et al. () achieve the state-of-the-art results in the Karel domain (Pattis, ) by searching in a programmatic space of AST structure.
Despite the encouraging results and the generality of these methods, they are notoriously inefficient, requiring tens of millions of program executions to obtain task-solving programs.
In this work, to devise an efficient PRL framework, we make the first attempt to leverage the knowledge and the reasoning ability of LLMs to generate a set of initial programs to bootstrap search algorithms; moreover, we propose Scheduled HC, a search algorithm that best utilizes the LLM-generated programs.

Large language models for code generation.
With a remarkable ability to understand and generate natural languages and codes, LLMs have been widely adopted for code generation (Brown et al., ; Achiam et al., ; Nijkamp et al., ; Xu et al., ; Roziere et al., ) via neural program synthesis methods (Lin et al., ; Sun et al., ; Desai et al., ; Raza et al., ; Wang et al., ; Le et al., ; Parisotto et al., ; Balog et al., ).
These works target general-purpose programming languages for software development, such as Python and C++, with abundant data on the internet; in contrast, we aim to solve PRL tasks that require writing programs restricted by given domain-specific languages.
Prior works exploring using LLMs to synthesize DSL programs via providing LLMs with DSL grammars and few-shot examples, hindsight relabeling, and prioritized experience replay (Wang et al., ; Grand et al., ; Butt et al., ).
While these works focus on string and array transformation as well as abstract reasoning (Chollet, ), we leverage LLMs to synthesize DSL program policies to be executed in an RL environment and maximize the return.

Search-based program synthesis.
Various search algorithms have been developed for program-by-example (PBE) (Gulwani, ; Feser et al., ; Polozov and Gulwani, ; Gulwani et al., ; Parisotto et al., ; Balog et al., ), whose goal is to find programs that satisfy given examples, *e.g*. input/output string pairs.
Recent works have explored utilizing search algorithms in DSL to learn libraries (Ellis et al., ; Grand et al., ).
In the regime of programmatic RL, Carvalho et al. () recently applied the Hill Climbing algorithm to the Karel benchmark, achieving state-of-the-art performance.
Instead of randomly sampling programs via search algorithms, we present a framework that integrates knowledge from an LLM with a search algorithm to significantly improve the sample efficiency.

An extended discussion on related work can be found in Appendix A.

Figure: Figure 1: The Karel DSL grammar. It describes the Karel domain-specific language’s actions, perceptions, and control flows. The domain-specific language is obtained from Liu et al. ().
Refer to caption: x1.png

### 3 Preliminary

The Karel domain.
We first review the Karel domain, the de facto test bed for programmatic reinforcement learning research (Bunel et al., ; Chen et al., ; Shin et al., ; Gupta et al., ; Chen et al., ).
The Karel domain-specific language illustrated in Figure 2 is a robot programming language to control the Karel agent in a 2D grid world.
The agent’s actions include moving as well as interacting with the environment by picking up and putting down objects (markers).
The perceptions check for obstacles and markers, which allows observing the environment.
Lastly, control flows, *e.g*., REPEAT, WHILE, IF, and IFELSE, enable describing complex decision-making logics.
More details of the DSL can be found in Appendix B.

We illustrate a Karel task, DoorKey, in Figure 2.
The agent needs to explore the left room using the DSL actions such as move and turnLeft as well as the perceptions such as frontIsClear and markersPresent to find the key (marker). After picking up the key via pickMarker, the wall to the right room will unblock. The agent then needs to place a marker on the goal marker located in the right room to receive a full task reward.
Appendix C presents all the Karel tasks in detail.

The state-of-the-art performance in Karel is achieved by iteratively searching for improved programs according to their episodic return using search algorithms (Carvalho et al., ).
Next, we introduce the concept of search space, which defines how search algorithms find neighbor programs from a set of current candidates for improved performance, and then dive into the search algorithm details.

Programmatic space vs. latent space.
In the programmatic space, a program $P$ can be represented as an abstract syntax tree (AST), where each leaf node in the AST represents a program token (Carvalho et al., ).
To obtain its neighborhood program, a node is sampled from its AST, and then replaced by a subtree randomly generated using the DSL’s production rules and sampling strategies.
Another choice is to search in a learned *latent space* (Trivedi et al., ; Liu et al., ), constructed by training a variational autoencoder on randomly generated DSL programs.
To sample a neighbor program, a small noise is added to the latent embedding of the current program candidate, and the decoder can generate a program from the noise-corrupted embedding.

Hill climbing (HC).
This search algorithm climbs whenever there is a higher place, *i.e*., moves to a program having a higher episodic return.
Given a program, HC generates its $k$ neighborhood programs from the search space. These programs are evaluated in the environment. If one of them has a higher episodic return than the initial program, it is set as the search center program, and then this process repeats. Otherwise, the algorithm halts and returns the best program evaluated.

Cross-entropy method (CEM).
CEM (Rubinstein and Kroese, ) first generates $k$ neighborhood programs from its latent space and evaluates their episodic return on the Karel environment (Trivedi et al., ). Next, if the average return over the top-$E$ neighborhood programs is higher than the best-seen average return, it continues the process on the mean latent embedding of the top-$E$ neighborhood programs. When the average return no longer increases, the program with the highest episodic return is returned.

Cross-entropy beam search (CEBS).
CEBS extends CEM to maintain a set of $E$ candidate programs to perform beam search.
In other words, CEBS searches all the neighborhoods of the top-$E$ programs.

Note that HC can search in both programmatic and latent spaces, while CEM and CEBS are designed for continuous search spaces, *i.e*., latent program space only.
All of these search algorithms share the same weakness – they search surrounding programs in a narrow proximity thus the distance between the initial program and the optimal program directly upper-bounds the algorithm’s sample efficiency.

Figure: Figure 3: Large language model-guided search (LLM-GS). (a) With task description and the Pythonic-DSL instruction, LLM generates Python programs that are subsequently converted to DSL programs. (b) These initial programs serve as the initial population of our proposed Scheduled Hill Climbing, which evaluates the episodic return of the neighboring programs to update the current candidate program with increasing neighborhood size over search steps.
Refer to caption: x2.png

### 4 Large language model-guided search
for efficient programmatic reinforcement learning

**Table 1: Activate LLM’s domain and task awareness. To bridge the domain gap between the target task and the LLM’s knowledge, we curate a scaffolding prompt to alleviate the knowledge gap and activate the task-solving ability without explicitly dictating the specific programming approach or implementation. Take the task DoorKey as an example, the user writes down the task name, goal, and some detailed information like map and initial position. Users can easily follow the categories in the prompt to write the task description. The LLM is encouraged to solve the specified task with its programming skills and common sense. More details of the prompts can be found in Appendix D.**
| Knowledge | Prompt Text |
| --- | --- |
| Task Name | DoorKey |
| Map Description | The map is a $8\times 8$ grid surrounded by walls that is vertically split into two chambers. The left chamber is $6\times 3$ grid and the right chamber is $6\times 2$ grid. There is a marker placed randomly on the left chamber as a key, and another marker placed randomly on the right chamber as a goal. |
| Initial Position | The agent starts on a random cell on the left chamber facing east. |
| Task Goal | The goal of the agent is to pick up a marker on the left chamber, which opens a door connecting both chambers. Allow the agent to reach and put a marker on the goal marker. |

The hill climbing algorithm (HC) is the state-of-the-art programmatic reinforcement learning (PRL) approach in Karel, at the cost of *tens of millions* of program interactions (Carvalho et al., ).
This prevents its application to real-world decision-making problems, where program-environment interaction at this scale is inapplicable.
Hence, we aim to maintain the high episodic return while reducing programs executed in the environments, *i.e*., *improves the sample efficiency* of PRL.
To this end, our key insight is to utilize a large language model (LLM), hypothesizing that its abundant world knowledge, including programming skills and common sense, may bootstrap the inherently assumption-less, random-guessing HC.
However, to implement this idea, many challenges rooted in the environment’s domain gap (Section 4.1), DSL’s language barrier (Section 4.2), and the inability to optimize closed-source LLMs (Section 4.3) must be addressed.
Figure 3 presents an overview of our proposed framework, large language model-guided search (LLM-GS).

#### 4.1 Domain and task-aware prompting

An inexperienced LLM user might directly ask an LLM: “Write a program to solve the Karel task DoorKey,” since this is how typical users interact with LLM-based software development assistants.
Obviously, repeating this until the LLM spits out a correct program is unlikely to be more efficient than existing search algorithms.
There are two major challenges that exist: (1) the LLM lacks the dynamic environmental concepts inherent to the Karel domain, and (2) the LLM does not have background knowledge of the specific PRL task DoorKey.
Therefore, it is crucial to provide a detailed description of the task and environment in natural language so the LLM can make informed assumptions based on its learned common sense.

To address this, we devise a prompting strategy that converts the task description and the task-agnostic environment knowledge into natural language sentences that LLMs can process and reason.
The task-agnostic environment knowledge prompt introduces the basic mechanics of interacting with this environment to the model, setting the stage for more specific programming tasks within the Karel framework, detailed in Section D.1.
Table 1 provides an example of a user prompt for the Karel task DoorKey.
Now that the LLM has acquired basic knowledge of the Karel domain and the task, we can further instruct it to leverage its programming skills, algorithmic knowledge, and long-term planning abilities to generate programs that solve tasks.
Note that given this domain-aware prompt, given any novel task within the same domain, even a user without any programming skills can simply describe the task in natural language to obtain a performant program, as shown in Section 5.4.

#### 4.2 Generating DSL programs with Pythonic-DSL strategy

Given LLMs’ widespread success in assisting software development, one might assume an LLM can naively generate DSL programs.
Yet, precisely generating DSL programs turns out to be quite challenging for LLMs – their training data typically consists of natural language corpus and general-purpose programming language codes, thus specific DSLs used in PRL tasks are actually quite exotic for them.
Note that this language barrier is beyond lexical syntax differences.
For example, the DSL may specify rules that limit the usage of temporary variables constrained by the actual robotic hardware, which is rarely a concern for common Python / JavaScript code found on the internet.

Despite the issue, we still hope to leverage the best of LLM’s programming skills,
algorithmic knowledge, and long-term planning abilities
to synthesize DSL programs.
To this end, we derive a solution from the following assumptions: (1) The LLM is proficient in a general-purpose programming language, such as Python, (2) The DSL can be represented by a possibly restricted version of the general-purpose programming language, and (3) The LLM understands the restriction in natural language, if any.
Our Pythonic-DSL strategy instructs the LLM to generate Python programs instead, given the Karel rules and constraints we wrote in English, and then later convert it into the Karel DSL.
As shown in Table 2, DSL details are provided, including the action, perception,
primitives
and language constraints.
Thus, the LLM can generate programs based on its innate general programming skills and its understanding of the DSL description.
One caveat is that the LLM still occasionally generates Python programs that cause Python-to-DSL parsing failures.
An empirical useful mitigation is instructing the LLM to generate the DSL program converted from its own output Python program as a backup.
At this point, we have developed the mechanism to instruct an LLM to generate DSL programs given the PRL task and the DSL grammar in natural language.

**Table 2: The Pythonic-DSL instruction. The Karel DSL is specified via a *constrained* version of Python with pre-defined functions including *Pythonic-DSL perceptions* that allow the agent to observe, and *Pythonic-DSL actions* that enable the agent to interact. This Pythonic-DSL description is fed into the LLM via the system prompt so that it can generate Python code that can later be converted into Karel DSL. We will show that this approach outperforms the direct generation of DSL or Python programs in Table 3. The full prompt is presented in Section D.1.**
| Knowledge | Prompt Text |
| --- | --- |
| Pythonic-DSL | frontIsClear(): Returns True if there is no wall in front of the agent. |
| Perceptions | markersPresent(): Returns True if there exist markers on the current cell. |
|  | … (more perceptions omitted) |
| Pythonic-DSL | move(): Asks the agent to move forward one cell … (truncated) |
| Actions | turnLeft(): Asks the agent to rotate 90 degrees counter-clockwise. |
|  | pickMarker(): Asks the agent to pick up one marker from the current cell. |
|  | … (more actions omitted) |
| Language Constraints | - do not define other functions besides run() |
|  | - do not define variables |
|  | … (more rules omitted) |

#### 4.3 Optimizing the program policy with Scheduled Hill Climbing

Although the aforementioned techniques can already instruct the LLM to produce DSL programs that solve the target task to a certain degree, the episodic return can still be far from optimal.
Since best-in-class LLMs are typically proprietary APIs, directly and iteratively fine-tuning them via gradient-based policy optimization methods is not possible.
To further optimize the program generated by the LLM, we explore initializing search populations of search algorithms using LLM-generated programs.
Via extensive experiments with the HC, CEM, and CEBS search algorithms on both program space and latent space whenever applicable, we discover a key improvement that is crucial when initializing search from LLM-generated programs – program-environment interaction scheduling for a more efficient allocation of the interaction budget.
The intuition is that LLMs can often provide good initialization and therefore it makes sense to keep a small search budget, *i.e*. with a smaller population.
After a while, if an optimal program is not yet found, we can gradually increase the budget and facilitate broader exploration.
We design a scheduler based on this intuition:

$$ $\displaystyle\log_{2}{k(n)}$ $\displaystyle=(1-r(n))\log_{2}{K_{start}}+r(n)\log_{2}{K_{end}}\text{,}$ (1) $$

where $n$ represents the number of evaluated programs, $k(n)$ denotes a function indicating the current number of neighborhood programs based on the number of evaluated programs $n$. This function’s logarithm is a linear combination of the logarithms of two hyperparameters, $K_{start}$ and $K_{end}$, which signify the initial and terminal numbers of neighbors to search, respectively. The variable $r(n)$ governs the linear ratio, which itself is a sinusoidal function that gradually increases from 0 0 to $1$ throughout the evaluation of a total of $N$ programs (see Appendix E).
With this scheduler, the number of neighbors $k$ is a function of the execution budget used, growing from $K_{start}$ to $K_{end}$.
We apply this scheduler to Hill Climbing and call this method Scheduled Hill Climbing (Scheduled HC).

Overall, our best recipe consists of the following steps. First, we sample DSL programs for the LLM using the aforementioned techniques. Next, these programs are evaluated in the environment for the episodic return.
In some easy tasks, some generated programs might have achieved perfect returns and thus are optimal programs.
If no optimal program is found, we sort the programs based on the total reward decreasingly. Next, programs are selected from the sorted list, each serves as an initial program for the HC search, which is the best-performing search algorithm from our extensive experiments.
HC searches $k$ neighbors at each step following the scheduler in Eq. 1. This process is repeated until either the optimal program is found or we meet the maximum program-environment interaction budget allowed ($N$).

Figure: (a) StairClimber
[Uncaptioned image]: x3.png

### 5 Experiments

#### 5.1 Evaluation setup

PRL tasks. We evaluate our proposed framework LLM-guided search (LLM-GS) using the Karel tasks from the two problem sets: Karel (Trivedi et al., ) (StairClimber, Maze, FourCorners, TopOff, Harvester, and CleanHouse) and Karel-Hard (Liu et al., ) (DoorKey, OneStroke, Seeder, and Snake).
More task details can be found in Appendix C.

Baselines.
We compare our proposed framework with the following methods: LEAPS (Trivedi et al., ),
HPRL (Liu et al., ), CEBS (Carvalho et al., ), and Hill Climbing (Carvalho et al., ) (the current state-of-the-art).
More details of these methods are presented in Appendix F.

Metrics.
For a fair comparison of the sample efficiency, we use the number of programs evaluated to represent the program-environment interaction budget. A method is a more sample-efficient PRL algorithm if it achieves a higher average episodic return on a fixed budget. Specifically, for each task, the number of task variances is $C$. One program evaluated means a program is executed on all $C$ task variances to obtain the average return.
We set the number of task variances $C=32$, the maximum number of program evaluation $N=10^{6}$, *i.e*., the interaction budget.
Programs achieving an average return of 1.0 will be considered optimal.

Setup.
We use GPT-4 (Achiam et al., ) (gpt-4-turbo-2024-04-09 with temperature=1.0, top_p=1.0) as our LLM module to generate the initial search population.
The scheduler of our proposed Scheduled HC starts from $K_{start}=32$ to $K_{end}=2048$.
We evaluate our LLM-GS and HC with $32$ random seeds and $5$ seeds for LEAPS, HPRL, and CEBS.

Data Leakage.
When using modern LLMs, a key concern is whether the model has already memorized the content in the test bed, leading to biased or inflated results.
We carefully rule out this possibility in Appendix G by examining the LLM release dates and the availability of optimal Karel programs, and by probing the LLM we use.

#### 5.2 LLM-guided search significantly improves the sample efficiency

Figure 4 presents the experimental result, indicating that our proposed LLM-GS surpasses all the existing methods by a large margin on almost all the tasks.
We also include a plot aggregating the performance across all ten tasks to clearly demonstrate the improvement in Appendix H (Figure 15).

On the Karel set, our framework completely solves these tasks and exhibits the best sample efficiency.
Also, LLM-GS performs extraordinarily well on Seeder, OneStroke, and DoorKey, which are among the hardest of the Karel-Hard set.
We highlight our DoorKey result, with an efficiency improvement from not converging at even 1M (baselines) to converging within around 50K (ours).
Existing PRL algorithms struggle at DoorKey due to the fact that it is a two-stage task with a sparse reward function. Therefore, most of the baselines cannot escape the local maxima and converge around $0.5$.
Curiously, our method starts at an episodic return of $\approx 0.5$ from the beginning and converges quickly without being trapped by the local maxima. To analyze, we examine one output program from LLM shown in Figure 5.
The LLM clearly understands that DoorKey is a two-stage task and thus generates a corresponding two-stage structured program, which is much easier for later search to find the optimal program. The full dialogue is presented in Appendix D.

Figure: Figure 5: Example on DoorKey. This example shows how our search method improves an LLM-initialized program to an optimal one. The original program (left) has a two-stage structure but lacks navigation ability. The improved program (right) solves this by enhancing its navigating ability on both stages, allowing for solving the task.
Refer to caption: x4.png

#### 5.3 Ablation studies

###### Which language to generate, Python or DSL? Do both!

To justify the effectiveness of our proposed Pythonic-DSL strategy, we conduct experiments on generating either Python or DSL programs with the same 8 seeds and present the results in Table 3.
The acceptance rate calculates the ratio of executable DSL programs, while
the best return refers to the highest episodic return among the legal programs.
Our method achieves the highest acceptance rate on 9 / 10 tasks and the highest best return on 7 / 10 tasks. The complete prompts are presented in Appendix I.

**Table 3: Pythonic-DSL strategy ablation. We compare the programs generated using our proposed Pythonic-DSL strategy to directly generated Python or DSL programs. Our method achieves the highest acceptance rate and best return, justifying the effectiveness of our Pythonic-DSL strategy.**
| Task | Python | DSL | Pythonic-DSL (ours) |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Acceptance Rate | Best Return | Acceptance Rate | Best Return | Acceptance Rate | Best Return |  |
| StairClimber | 88.02$\pm$3.57% | 1.00$\pm$0.00 | 45.31$\pm$11.59% | 0.75$\pm$0.65 | 88.54$\pm$4.54% | 1.00$\pm$0.00 |
| Maze | 72.40$\pm$7.49% | 0.94$\pm$0.08 | 57.81$\pm$8.12% | 0.88$\pm$0.07 | 92.45$\pm$3.89% | 0.98$\pm$0.05 |
| FourCorners | 83.07$\pm$5.04% | 1.00$\pm$0.00 | 93.49$\pm$2.43% | 1.00$\pm$0.00 | 94.01$\pm$2.43% | 1.00$\pm$0.00 |
| TopOff | 90.89$\pm$2.07% | 0.97$\pm$0.07 | 94.53$\pm$4.29% | 1.00$\pm$0.00 | 96.35$\pm$3.08% | 1.00$\pm$0.00 |
| Harvester | 67.45$\pm$7.51% | 0.98$\pm$0.03 | 79.69$\pm$7.64% | 0.98$\pm$0.03 | 80.21$\pm$5.51% | 0.95$\pm$0.09 |
| CleanHouse | 62.50$\pm$3.45% | 0.27$\pm$0.28 | 76.30$\pm$6.16% | 0.36$\pm$0.14 | 84.64$\pm$4.29% | 0.29$\pm$0.27 |
| DoorKey | 90.10$\pm$3.86% | 0.63$\pm$0.13 | 75.78$\pm$15.09% | 0.55$\pm$0.05 | 94.53$\pm$3.60% | 0.63$\pm$0.14 |
| OneStroke | 85.42$\pm$4.77% | 0.77$\pm$0.06 | 85.68$\pm$7.54% | 0.74$\pm$0.09 | 95.31$\pm$3.08% | 0.83$\pm$0.08 |
| Seeder | 73.70$\pm$4.77% | 0.93$\pm$0.14 | 88.28$\pm$4.88% | 0.66$\pm$0.10 | 74.74$\pm$7.10% | 0.90$\pm$0.14 |
| Snake | 87.50$\pm$2.76% | 0.09$\pm$0.00 | 30.47$\pm$9.02% | 0.09$\pm$0.00 | 98.96$\pm$1.04% | 0.09$\pm$0.00 |

Figure: (a) DoorKey
Refer to caption: extracted/5923063/figure/search_ablation/doorkey.png

Our proposed Scheduled HC is the most efficient search method.
We compare various search methods in both programmatic and latent spaces in DoorKey and CleanHouse using LLM-initialized programs.
In the learned latent space, we run CEM, CEBS, HC-$250$ (HC with a fixed population size of $250$), and our proposed Scheduled HC;
in the programmatic space, we run HC-$k\in\{32,256,2048\}$ and our proposed Scheduled HC.
The results presented in Figure 7 show that HC in the programmatic space achieves the best performance compared to latent space search.
However, HC-$k$ with a fixed population size only specializes in specific tasks.
To be specific, HC-$32$ for CleanHouse and HC-$2048$ for DoorKey. In contrast, our proposed Scheduled HC achieves comparatively the best performance in both tasks.

LLM provides a better initial search population.
To verify the efficacy of using LLM-generated programs as search initialization for Scheduled HC, we compare it to using randomly sampled programs as initialization in DoorKey and CleanHouse.
The results shown in Figure 7 suggest that initializing the search with LLM-generated programs significantly improves the sample efficiency compared to randomly initializing population-like search methods.

#### 5.4 Performance on novel tasks showcases the extensibility of LLM-GS

Figure: (a) PathFollow
Refer to caption: extracted/5923063/figure/rebuttal/pathfollow.png

A key advantage of our proposed LLM-GS framework is its ability to adapt to new tasks using only text descriptions without requiring users to have any domain knowledge or familiarity with the DSL.
To showcase this feature, we designed two novel Karel tasks, PathFollow and WallAvoider, as detailed in Section C.3.
By simply replacing the task descriptions while keeping the Karel domain prompt, Python-to-DSL prompt, and hyperparameters the same, we compare our method with the best-performing baseline, HC.
The results presented in Figure 8 show that by only changing the task descriptions, our LLM-GS framework still achieves improved sample efficiency and finds better policies.

#### 5.5 Beyond initialization – a preliminary attempt on LLM revision

Given the encouraging results from LLM-initialized programs, one might be curious whether LLM can progressively revise and improve its programs once given feedback from the environment, *e.g*., reward.
For completeness, we additionally conduct studies with the following LLM-based revision:

- •
Regeneration. Inspired by Chen et al. () and Olausson et al. (), we instruct the LLM to re-generate non-duplicate programs given its previously generated programs.
- •
Regeneration with reward. In addition to the historical program list, the episodic return of each program is appended to the LLM’s inputs.
- •
Agent execution trace. Inspired by prior arts that leverage environment knowledge (Tang et al., ; Wang et al., ) and code repair (Chen et al., ; Olausson et al., ), we feed the program with the best episodic return and its execution traces into the LLM.
- •
Agent and program execution trace. Inspired by Hu et al. (), we additionally point out the line of the program currently being executed as extra hints to the LLM.

Figure: Figure 9: LLM revision. The performance gain of LLM revision saturates within a few rounds.
Refer to caption: extracted/5923063/figure/revised.png

We conduct the LLM revision experiments on DoorKey for five revision rounds, each round with $32$ programs with $5$ seeds.
The results are presented in Figure 9.
We can see that the improvement quickly saturates within the first two rounds, and no significant gain is observed with more revision rounds.
This indicates that only using LLM to revise the program may not be sufficient to solve the task.
On the other hand, our proposed Scheduled HC can converge to an optimal program – and is “free,” *i.e*. no expensive API calls or “API usage has reached your notification threshold” emails.
The details can be found in Appendix I.

### 6 Discussion

We propose an LLM-guided framework (LLM-GS), that
leverages the programming skills and common sense of LLM
to bootstrap the efficiency of assumption-free, random-guessing search methods.
We propose a Pythonic-DSL framework to address the inability of LLMs to generate precise and grammatically correct programs. To further maximize the programs generated by LLMs, we design a search algorithm, Scheduled Hill Climbing, which can explore the programmatic search space to consistently improve the programs.
The experimental results on the Karel tasks show the improved sample efficiency of our proposed LLM-guided framework. Extensive ablation studies verify the effectiveness of our proposed Pythonic-DSL and Scheduled Hill Climbing.
We discuss the limitations and future directions of LLM-GS in Appendix J in detail, which includes the necessity of domain experts and LLMs, etc.

### Appendix

## 

### Appendix A Extended Related work

Sample efficiency in programmatic reinforcement learning .
While deep reinforcement learning has achieved tremendous success in various domains [Silver et al., , Ouyang et al., , Bai et al., , Wang et al., , Chen et al., ], it still suffers from sample inefficiency problems.
Many methods make their effort to improve sample efficiency including modeling transition model [Kaiser et al., ], replay buffer [Mnih et al., ], hindsight relabeling [Andrychowicz et al., ], ensembling [Wiering and Van Hasselt, ], and importance sampling [Sutton, ].
Likewise, this is also the case for programmatic reinforcement learning (PRL) algorithms. The SOTA algorithm, Hill Climbing (HC), still needs to generate thousands to millions of programs to achieve optimal policies. In this work, we utilize the information on Karel’s tasks and LLM programming skills to initiate the search population of our proposed Scheduled HC to improve the sample efficiency.
Incorporating other sample efficiency-improving methods into PRL algorithms is a promising research direction, but is orthogonal to our contribution.

Large language models and search-based program synthesis.
Various search algorithms have been developed for program-by-example (PBE) [Gulwani, , Feser et al., , Polozov and Gulwani, , Gulwani et al., , Parisotto et al., , Balog et al., ], whose goal is to find programs that satisfy given examples, *e.g*., input/output string pairs.
Recent works have explored utilizing search algorithms in DSL to learn libraries [Ellis et al., , Grand et al., , Eberhardinger et al., , Wüst et al., ] for PBE, imitating policies [Bastani et al., , Kohler et al., ], and object representations [Wüst et al., ]. The LLM can bootstrap program synthesis in the wake stage of library learning [Grand et al., , Eberhardinger et al., ]. It is an open question whether the LLM can bootstrap the sleep stages. We utilize the description of the Karel tasks to bootstrap our scheduled HC. Additional information may be crucial for LLM assist bootstrapping and fine-tuning. This additional information may come from the execution [Chen et al., ], prompt design [Wang et al., , Wei et al., , Wüst et al., , Grand et al., ], and the task description in our work.

More on search methods and structured policy representations.
There are several different search methods developed for programming by example (PBE) [Gulwani, , Feser et al., , Polozov and Gulwani, , Gulwani et al., , Parisotto et al., , Balog et al., ] or DSLs with learned libraries [Ellis et al., , Grand et al., , Eberhardinger et al., , Wüst et al., ] for PBE, imitating policies [Bastani et al., , Kohler et al., ], and object representations [Wüst et al., ]. Recent studies explore different representations for Reinforcement Learning policies toward interpretable and/or explainable. Together with various structured policy representations such as DSL programs [Andre and Russell, , Verma et al., , Silver et al., ], decision trees [Bastani et al., , Kohler et al., ], state machines [Lin et al., ], and symbolic programs [Jiang and Luo, , Qiu and Zhu, , Delfosse et al., ].
Our method has the greatest bootstrapping ability for DSL programs but is difficult to extend to all kinds of representations. We designed our prompt by contrasting the policy representation (Karel DSL) with Python. As a result, our prompt in Section D.1 limits some of the functionalities of Python. We believe our framework is only suitable for tasks with task-solving procedures that could be described using languages. That said, it could be difficult to apply this framework to low-level control tasks, such as motor torque control [Qiu and Zhu, ].

### Appendix B Karel DSL details

There are 5 symbols in the Karel DSL: statement, condition, action, boolean, and number. The production rules and Python converting rules are listed in Table 4. The statement counts the mean total usage of converting one statement into two statements at the root of the abstract syntax tree (AST), and the statement counts are limited to 6 in search of optimal programs. The program length is the total number of tokens used in string representation and is set to 44. The depth in DSL is the recursive call of control flows, which is limited to 4. These limitations are the same as the original settings in LEAPS [Trivedi et al., ]. The probabilities of the production rules are listed in Table 5. The mutation process selects one random node in the AST. We use the production rules to sample a sub-tree to replace the original node. The Karel syntax has many symbol-related parentheses, *e.g*., “i(” and “i)” which are related to the “IF” and “IFELSE”, thus LLM sometimes makes mistakes translating Python to DSL. We list common mistakes LLM made in Table 6 and how we solve these problems.

**Table 4: Python to DSL converting rules.**
| Python | DSL |
| --- | --- |
| def run(): s | DEF run m( s m) |
| while b: s | WHILE c( b c) w( s w) |
| if b: s | IF c( b c) i( s i) |
| if b: s else: s | IFELSE c( b c) i( s i) ELSE e( s e) |
| for i in range(n): s | REPEAT R=n r( s r) |
| not h | not c( h c) |
| frontIsClear() | frontIsClear |
| leftIsClear() | leftIsClear |
| rightIsClear() | rightIsClear |
| markersPresent() | markersPresent |
| noMarkersPresent() | noMarkersPresent |
| move() | move |
| turnLeft() | turnLeft |
| turnRight() | turnRight |
| putMarker() | putMarker |
| pickMarker() | pickMarker |

**Table 5: Probabilities of the production rules.**
| Category | Rule | Probability |
| --- | --- | --- |
| Program P | Statement | 1.0 |
| Statement S | While | 0.15 |
|  | Repeat | 0.03 |
|  | Concatenate | 0.5 |
|  | If | 0.08 |
|  | Ifelse | 0.04 |
|  | Action | 0.2 |
| Condition c | Boolean | 0.9 |
|  | not | 0.1 |
| Action a | move | 0.5 |
|  | turnLeft | 0.15 |
|  | turnRight | 0.15 |
|  | putMarker | 0.1 |
|  | pickMarker | 0.1 |
| Boolean b | frontIsClear | 0.5 |
|  | leftIsClear | 0.15 |
|  | rightIsClear | 0.15 |
|  | markersPresent | 0.1 |
|  | noMarkersPresent | 0.1 |
| Number n | i (0 $\leq$ i $\leq$ 19) | 0.05 |

**Table 6: These are the common mistakes LLM makes. We implement a simple program to correct these mistakes.**
| Type | Before | After |
| --- | --- | --- |
| Brackets removal | DEF run m( move() m) | DEF run m( move m) |
| Brackets separation | DEF run m(move m) | DEF run m( move m) |
| Brackets addition | DEF run m( WHILE frontIsClear w( move w) )m | DEF run m( WHILE c( frontIsClear c) w( move w) )m |
| Brackets repairment | DEF run m( move ) | DEF run m( move m) |
| If to IFELSE | DEF run m( IF c( frontIsClear c) i( move i) ELSE e( turnLeft e) )m | DEF run m( IFELSE c( frontIsClear c) i( move i) ELSE e( turnLeft e) )m |
| Redundant symbols removal | DEF run m( move() m m) | DEF run m( move m) |
| Illegal symbols transformation | DEF run m( WHILE c( True c) w( move w) ) | DEF run m( REPEAT r=19 r( move r) m) |

### Appendix C Karel tasks

We give the large language model 5 pieces of information related to the tasks: task name, map description, initial Position, task goal, and task return. By converting the original task description into these 5 categories, this design allows the user to easily fill in all categories for new tasks. Here we list all the information pieces for these tasks. Section I.1.2 shows how these 5 different components are filled into the placeholders in the user prompt. Section D.2 show all filled results with the task DoorKey. There are three sets of tasks: Karel [Trivedi et al., ], Karel-Hard [Liu et al., ], and new Karel tasks. Section C.1 lists all 6 Karel tasks, Section C.2 lists all 4 Karel-Hard tasks, and Section C.3 lists the 2 new tasks. Example figures of Karel tasks are in Figure 10, Karel-Hard tasks are in Figure 11 and new Karel tasks are in Figure 12.

#### C.1 Karel tasks

Figure: (a) StairClimber
Refer to caption: x5.png

##### C.1.1 The task prompt of StairClimber

| Purpose | Prompt Text |
| --- | --- |
| Task Name | STAIRCLIMBERSPARSE |
| Map Description | The map is a 12x12 grid surrounded by walls with stairs formed by walls and a marker is randomly initialized on the stairs as a goal. |
| Initial Position | The agent starts on a random position on the stairs facing east. |
| Task Goal | The goal of the agent is to reach a marker that is also randomly initialized on the stairs. |
| Task Reward | If the agent reaches the marker, the agent receives 1 as an episodic return and 0 otherwise. If the agent moves to an invalid position, i.e. outside the contour of the stairs, the episode terminates with a -1 return. |

##### C.1.2 The task prompt of Maze

| Purpose | Prompt Text |
| --- | --- |
| Task Name | MAZESPARSE |
| Map Description | The map is a complex 8x8 grid surrounded by walls and a random marker is placed on an empty cell as a goal. |
| Initial Position | The agent starts on a random empty cell of the map facing east. |
| Task Goal | The goal of the agent is to reach the goal marker. |
| Task Reward | If the agent reaches the marker, the agent receives 1 as an episodic return and 0 otherwise. |

##### C.1.3 The task prompt of FourCorners

| Purpose | Prompt Text |
| --- | --- |
| Task Name | FOURCORNERS |
| Map Description | The map is an empty 12x12 grid surrounded by walls. |
| Initial Position | The agent starts on a random cell on the bottom row of the map facing east. |
| Task Goal | The goal of the agent is to place one marker in each corner of the map. |
| Task Reward | Return is given by the number of corners with one marker divided by 4. |

##### C.1.4 The task prompt of TopOff

| Purpose | Prompt Text |
| --- | --- |
| Task Name | TOPOFF |
| Map Description | The map is a 12x12 grid surrounded by walls with markers randomly placed on the bottom row of the map. |
| Initial Position | The agent starts on the bottom left cell of the map facing east. |
| Task Goal | The goal of the agent is to place one extra marker on top of every marker on the map. |
| Task Reward | Return is given by the number of markers that have been topped off divided by the total number of markers. Picking up the marker will terminate the episode with a -1 return. |

##### C.1.5 The task prompt of Harvester

| Purpose | Prompt Text |
| --- | --- |
| Task Name | HARVESTER |
| Map Description | The map is a 8x8 grid surrounded by walls that starts with a marker on each cell. |
| Initial Position | The agent starts on a random cell on the bottom row of the map facing east. |
| Task Goal | The goal of the agent is to pick up every marker on the map. |
| Task Reward | Return is given by the number of picked-up markers divided by the total number of markers. |

##### C.1.6 The task prompt of CleanHouse

| Purpose | Prompt Text |
| --- | --- |
| Task Name | CLEANHOUSE |
| Map Description | The map is a complex 14x22 grid made of many connected rooms and is surrounded by walls. There are ten markers randomly placed adjacent to the walls. |
| Initial Position | The agent starts on a fixed cell facing south. |
| Task Goal | The goal of the agent is to pick up every marker on the map. |
| Task Reward | Return is given by the number of picked-up markers divided by the total number of markers. |

#### C.2 Karel-Hard tasks

Figure: (a) DoorKey
Refer to caption: x11.png

##### C.2.1 The task prompt of DoorKey

| Purpose | Prompt Text |
| --- | --- |
| Task Name | DOORKEY |
| Map Description | The map is a 8x8 grid surrounded by walls that is vertically split into two chambers. The left chamber is 6x3 grid and the right chamber is 6x2 grid. There is a marker placed randomly on the left chamber as a key, and another marker placed randomly on the right chamber as a goal. |
| Initial Position | The agent starts on a random cell on the left chamber facing east. |
| Task Goal | The goal of the agent is to pick up a marker on the left chamber, which opens a door connecting both chambers. Allow the agent to reach and put a marker on the goal marker. |
| Task Reward | Picking up the first marker yields a 0.5 reward, and putting a marker on the goal marker yields an additional 0.5. |

##### C.2.2 The task prompt of OneStroke

| Purpose | Prompt Text |
| --- | --- |
| Task Name | ONESTROKE |
| Map Description | The map is given by an empty 8x8 grid surrounded by walls. |
| Initial Position | The agent starts on a random cell of the map facing east. |
| Task Goal | The goal of the agent is to visit every grid cell without repeating. Visited cells become a wall that terminates the episode upon touching. |
| Task Reward | Return is given by the number of visited cells divided by the total number of empty cells in the initial state. |

##### C.2.3 The task prompt of Seeder

| Purpose | Prompt Text |
| --- | --- |
| Task Name | SEEDER |
| Map Description | The map is given by an empty 8x8 grid surrounded by walls.. |
| Initial Position | The agent starts on a random cell of the map facing east. |
| Task Goal | The goal of the agent is to place one marker in every empty cell of the map. |
| Task Reward | Return is given by the number of cells with one marker divided by the total number of empty cells in the initial state. |

##### C.2.4 The task prompt of Snake

| Purpose | Prompt Text |
| --- | --- |
| Task Name | SNAKE |
| Map Description | The map is given by an empty 8x8 grid surrounded by walls with a marker randomly placed on the map. |
| Initial Position | The agent starts on a random cell of the map facing east. |
| Task Goal | The agent acts like the head of a snake, whose body grows each time a marker is reached. (No need to pick it up.) Every time a marker is reached, the body of the agent grows one marker. The goal of the agent is to touch the marker on the map without colliding with the snake’s body, which terminates the episode. Each time the marker is reached, it is placed on a random cell, until 20 markers are reached. |
| Task Reward | Return is given by the number of reached markers divided by 20. |

#### C.3 New Karel tasks

To showcase the extensibility of our proposed LLM-GS framework, we additionally propose two novel new tasks, PathFollow and WallAvoider.
Here we list the task prompts.

Figure: (a) PathFollow
Refer to caption: x15.png

##### C.3.1 The task prompt of PathFollow

| Purpose | Prompt Text |
| --- | --- |
| Task Name | PATHFOLLOW |
| Map Description | The map is given by a 8x8 grid surrounded by walls. There is a rugged ascending markers line that starts from the bottom left cell and randomly grows either north or to the east until it reaches the top right cell. Resulting in a rugged markers line connecting the bottom left cell and the top right cell. |
| Initial Position | The agent starts on the bottom left cell of the map facing north. |
| Task Goal | The goal of the agent is to collect every marker on that rugged markers line without leaving the rugged markers line two cells away. |
| Task Reward | Return is given by the number of picked-up markers divided by the total number of markers. Placing any marker or leaving the rugged markers line two cells away will have a negative return as -1.0 and terminate the episode. |

##### C.3.2 The task prompt of WallAvoider

| Purpose | Prompt Text |
| --- | --- |
| Task Name | WALLAVOIDER |
| Map Description | The map is given by an empty 8x5 grid surrounded by walls. |
| Initial Position | The agent starts on a random cell of the map facing random directions. |
| Task Goal | The goal of the agent is to place exactly one marker in every interior cell of the map, which refers to the cells that are not adjacent to any wall. |
| Task Reward | Return is given by the number of interior cells with exactly one marker divided by the total number of interior cells. Picking up the marker, putting more than one marker on one cell, or putting any marker on the cell adjacent to any wall will terminate the episode with a -1 return. |

### Appendix D An example pipeline of our method

This is our pipeline of getting programs from LLM with the task DoorKey. Section D.1 details the system prompt, Section D.2 provides all the information in the task DoorKey. Section D.3 lists the LLM response, and Section D.4 gives an example of how we get the Karel DSL program.

#### D.1 The system prompt

#### D.2 The user prompt of the task DoorKey

#### D.3 The sample response of LLM in the task DoorKey

#### D.4 Apply post-processing and retrieve the LLM-initialized programs

For the Python program part in LLM response, we convert the Python program to a DSL program through the rule-based method and apply post-processing to correct minor mistakes. For the DSL part, we directly apply post-processing to correct minor mistakes. Section D.4.1 presents the original Python program, the converted DSL, and the post-processed DSL. Section D.4.2 shows the original DSL and the post-processed DSL. All of the post-processing rules are listed in Table 6.

##### D.4.1 Python program part

Figure: Listing 1: Original Python program

Figure: Listing 2: DSL program converted through the rule-based method

Figure: Listing 3: DSL program after post-processing

##### D.4.2 DSL program part

Figure: Listing 4: Original DSL program

Figure: Listing 5: DSL program after post-processing

### Appendix E Scheduled Hill Climbing detail

This Scheduler is designed for
improving sample efficiency.
$n$ is the number of programs evaluated, and $K_{start}$ and $K_{end}$ are hyper-parameters representing the initial and terminal number of neighbors to search, respectively. $r(n)$ is a sinusoidal function that smoothly increase from 0 0 to $1$ over the course of $N$ total programs evaluated in the environment. We provide detailed equation in Equation 2 and Equation 3

$$ $\displaystyle log_{2}{k(n)}$ $\displaystyle=(1-r(n))\log_{2}{K_{start}}+r(n)\log_{2}{K_{end}}\text{,}$ (2) $$

$$ $\displaystyle 2r(n)=\sin{\left[(\frac{2\log{n}}{\log{N}}-1)\times\frac{\pi}{2} \right]}+1\text{.}$ (3) $$

### Appendix F Baselines and their hyperparameters

We compare our framework to four baselines, LEAPS [Trivedi et al., ], HPRL [Liu et al., ], CEBS [Carvalho et al., ], and HC [Carvalho et al., ]. LEAPS, HPRL, and CEBS search programs in the latent spaces. HC search program in the programmatic space. The pseudo-code of CEBS is described in Algorithm 1, and the pseudo-code of HC is described in Algorithm 2.

#### F.1 LEAPS

The hyperparameters of the LEAPS baseline are from LEAPS [Trivedi et al., ] and HPRL [Liu et al., ]. We downloaded the pre-trained weights of LEAPS and used the parameters for searching programs. We use the re-implementation of LEAPS from Carvalho et al. [], thus we do not have hyperparameters of exponential decay. Also, the re-implementation samples candidate from a fixed normal distribution which is hyperparameter in LEAPS [Trivedi et al., ]. In Table LABEL:table:leaps_karel_setting, $K$ is the neighborhood size and $E$ is the candidate, $\sigma$ is the noise scale. In LEAPS and HPRL, they use an elite ratio to represent the candidate programs. For better understanding, we round $E$ to be an integer.

**Table 7: LEAPS hyperparameter settings on all Karel tasks.**
| Task Name | $K$ | $\sigma$ | $E$ |
| --- | --- | --- | --- |
| StairClimber | 32 | 0.25 | 2 |
| FourCorners | 64 | 0.5 | 13 |
| TopOff | 64 | 0.25 | 3 |
| Maze | 16 | 0.1 | 2 |
| CleanHouse | 32 | 0.25 | 2 |
| Harvester | 32 | 0.5 | 3 |
| DoorKey | 32 | 0.25 | 3 |
| OneStroke | 64 | 0.5 | 3 |
| Seeder | 32 | 0.25 | 3 |
| Snake | 32 | 0.25 | 6 |

#### F.2 Hierarchical programmatic reinforcement learning (HPRL)

HPRL [Liu et al., ] aims to improve LEAPS by composing several programs to represent more complex behaviors. Given a learned latent space, meta-policy learns to predict a sequence of actions, *i.e*. programs, by optimizing the return obtained by executing the composed programs using reinforcement learning. HPRL considers the discount factor $\gamma$ in the meta-MDP; as a result, the evaluation method is not the same as our problem formulation. To ensure a fair comparison, we record one million programs explored by meta-policy in the training stage. In HRPL, the authors use the training step as a hyperparameter. One training step is one step of meta-policy, and the maximum episode length is set to 5 as the original setting in the HPRL paper. In Table LABEL:table:hprl_karel_setting, we list the hyperparameters we modified in the HPRL training script. All other hyperparameters remain the same as described in HPRL.

**Table 8: HRPL hyperparameter settings on all Karel tasks.**
| Task Name | training steps | height | weight |
| --- | --- | --- | --- |
| StairClimber | 50K | 12 | 12 |
| FourCorners | 500K | 12 | 12 |
| TopOff | 5M | 12 | 12 |
| Maze | 50K | 8 | 8 |
| CleanHouse | 500K | 12 | 22 |
| Harvester | 5M | 8 | 8 |
| DoorKey | 5M | 8 | 8 |
| OneStroke | 5M | 8 | 8 |
| Seeder | 5M | 8 | 8 |
| Snake | 5M | 8 | 8 |

#### F.3 Cross-entropy beam search (CEBS)

CEBS [Carvalho et al., ] also utilizes the pre-trained VAE weight from LEAPS [Trivedi et al., ] to search program in the latent space. All the hyperparameter follows the original CEBS with neighborhood $K$ equal to 64, candidate $E$ equal to 16, and noise ratio $\sigma$ equal to 0.25 for all ten Karel tasks. The pseudo-code is described in Algorithm 1.

#### F.4 Hill climbing (HC)

HC [Carvalho et al., ] is a state-of-the-art algorithm solving Programmatic Reinforcement Learning tasks. All the hyperparameter follows the original HC with neighborhood $K$ equal to 250 for all ten Karel tasks. The pseudo-code is described in Algorithm 2.

Figure: Algorithm 1 Cross-entropy beam search algorithm [Carvalho et al., ]

Figure: Algorithm 2 Hill climbing algorithm [Carvalho et al., ]

### Appendix G Data Leakage

While our proposed framework shows significant improvement over the baselines, some may question if this improvement only comes from the LLM “memorizing” all the answers. Indeed, some ground truth solutions have been documented in the previous literature [Trivedi et al., , Liu et al., , Carvalho et al., ], thus making data leakage a potential concern.
Still, we would like to rule out this possibility from three aspects: the timeline of previous works, the LLMs’ understanding of the Karel tasks, and the innovation of two novel tasks. Thus proving our framework utilizes the LLMs’ understanding and reasoning ability not just its internal knowledge.

Timeline. For the Karel-Hard problem set introduced by Liu et al. [] in July 2023, the optimal programs were not included in Liu et al. [] since their proposed method could only partially solve the tasks. Carvalho et al. [], made public in 2024, are the first to provide optimal programs for the Karel-Hard tasks. Hence, our LLM (gpt-4-turbo-2024-04-09 with knowledge up to December 2023) could not access the optimal Karel-Hard tasks programs.

Does the LLM know the Karel tasks?. To verify if the LLM knows the Karel tasks used in our work, we prompt GPT-4 by providing the paper names of LEAPS [Trivedi et al., ] and HPRL [Liu et al., ] and ask GPT-4 to list all the names and descriptions of the Karel tasks used in these works. Among all the responses generated by GPT-4, the only task closely resembling the Karel tasks used in our work is ”Maze Solving.” However, all other tasks described in the GPT-4’s response are drastically distinct from the ones we used in our work. The full prompt and response are listed in Figure 13 and Figure 14.

Two novel tasks. We additionally design two novel tasks that have not been used in any existing work, PathFollow, and WallAvoider, as illustrated in Figure 12. The details of these two novel tasks are in Section C.3. The results in Figure 8 show that our framework can extend to new tasks that are impossible to leak to LLMs.

Figure: Figure 13: The prompt that asks GPT-4 about the Karel PRL tasks

Figure: Figure 14: The GPT-4 response about Karel PRL tasks

### Karel Test Set Tasks

- 1.
Move to Wall: The task is for the agent (Karel) to move forward until it encounters a wall.
- 2.
Turn Right: Teach Karel to turn right using a sequence of commands (since Karel inherently only has a command to turn left).
- 3.
Collect Marker: Karel needs to navigate towards and collect a marker from the grid.
- 4.
Avoid Hurdles: Karel must move from one point to another while avoiding hurdles placed in its path.
- 5.
Put Marker and Move: This task combines placing a marker in a specified location and then moving to a different location.
- 6.
Maze Solving: Karel needs to find a path from one point to another in a maze-like structure.

### Karel-Hard Test Set Tasks

- 1.
Multiple Markers: Karel might need to collect or place multiple markers in various locations, requiring more complex navigation and memory usage.
- 2.
Dynamic Obstacles: The environments where obstacles may change location or appear suddenly, requiring Karel to adapt its path dynamically.
- 3.
Conditional Logic Usage: Tasks where Karel must use sensors to make decisions based on the conditions of its environment (e.g., If front is clear, move forward; otherwise, turn left).
- 4.
Complex Maze: More intricate and challenging mazes that require advanced pathfinding algorithms and possibly backtracking strategies.

While these are typical tasks deduced from the context of using Karel for testing PRL algorithms, please note that specific details or task names might vary based on the particular implementation or the focuses of different research papers or setups within the ”Karel” environment. Always refer back to the specific research documents or source materials for the most accurate descriptions and objectives of these tasks.

### Appendix H Aggregated performance across all tasks

To clearly examine the performance across all the tasks,
we include a plot that aggregates the performance of all main results (Figure 4) in Figure 15.
Our proposed LLM-GS framework significantly outperforms the existing methods.

Figure: Figure 15: Aggregated performance across all the tasks. The aggregate performance across all ten tasks. Our proposed LLM-GS framework surpasses all existing methods by a large margin.
Refer to caption: extracted/5923063/figure/rebuttal/all.png

### Appendix I LLM prompts for ablations and revision

Ablation prompts for program generation methods.
We conduct an ablation study in Section 5.3 to justify that our LLM-generating program method performs best in acceptance rate and best return. Here we list the complete prompts. There are three approaches to generating DSL programs: Pythonic-DSL, Python, and DSL. There are two types of prompt, system prompt and user prompt, in all approaches. In the system prompt, both the Python and the Pythonic-DSL approaches contain limitations of Python usage. The DSL approach contains the grammar of the Karel, and the Pythonic-DSL contains the paired Python-like and Karel production rules. All of the system prompts contain the environment physics, action, and perception. On the other hand, the user prompt contains five placeholders for task name, map description, initial position, task goal, and task reward. In Appendix C, all of the task-dependent information can be filled in the placeholders. Section D.2 shows the full Pythonic-DSL prompt with the task DoorKey filled in the placeholders. The Pythonic-DSL prompts are in Section I.1, and the Python prompts are in Section I.2, and the DSL prompts are in Section I.3.

Prompts for LLM revision.
We list all of the user prompts in the experiment of LLM revision, the system prompt is the same as the one in Section I.1. We implement four approaches to revising the program: Regenerate, Regenerate with reward, Agent execution trace, and Agent and program execution trace. We ask the LLM to regenerate with all generated programs in the last round without repetition, and the Regenerate prompt is in Section I.4. We ask the LLM to regenerate with the program relating to reward, and the revision prompt of the Regenerate with reward is in Section I.5. We utilize the execution trace of the Karel agent in the grid world, and the revision prompt of the Agent execution trace is in Section I.6. We provided the action/perception call and executing line, and the revision prompt of the Agent and program execution trace is in Section I.7. The program Figure 16 is the revision target of our method revision method in Section I.6 and Section I.7. Figure 16 is the trajectories of the program we used in method Section I.6 and Section I.7. In the example, the origin program has an average return of 0.5. LLM revision with agent trace can reach 0.640625, while LLM revision with both agent and program traces can reach a result of 0.8125.

Figure: (a) This is the initial state of one of DoorKey the task variants.
Refer to caption: extracted/5923063/figure/revising/doorkey_revising_initial.png

[!ht]
{minted}Python
def run():
while noMarkersPresent():
if frontIsClear():
move()
else:
turnLeft()
if frontIsClear():
move()
turnRight()
pickMarker()
while noMarkersPresent():
if frontIsClear():
move()
else:
turnLeft()
putMarker()
This is the program for LLM revision.

[!ht]
{minted}python
def run():
while noMarkersPresent():
if frontIsClear():
move()
else:
turnLeft()
pickMarker()
while frontIsClear():
move()
turnRight()
while noMarkersPresent():
if frontIsClear():
move()
else:
turnLeft()
if frontIsClear():
move()
turnRight()
putMarker()
The revision results of Section I.6.

[!ht]
{minted}python
def run():
while noMarkersPresent():
if frontIsClear():
move()
else:
turnLeft()
pickMarker()
while noMarkersPresent():
if rightIsClear():
turnRight()
move()
else:
if frontIsClear():
move()
else:
turnLeft()
putMarker()
The revision results of Section I.7.

#### I.1 Pythonic-DSL

##### I.1.1 System prompt

##### I.1.2 User prompt

#### I.2 Python

##### I.2.1 System prompt

##### I.2.2 User prompt

#### I.3 DSL

##### I.3.1 System prompt

##### I.3.2 User prompt

#### I.4 Regenerate

#### I.5 Regenerate with reward

#### I.6 Agent execution trace

#### I.7 Agent and Program execution trace.

### Appendix J Limitation

Adapting to more complex environments beyond Karel.
We believe developing more realistic and complex programmatic RL environments is a promising future direction. However, to make a new environment suitable for programmatic reinforcement learning (PRL), we must carefully craft a domain-specific language (DSL) that defines action and perception primitives tailored to the environment’s constraints. For example, in the SpaceInvaders Atari environment, actions might be defined as Left, Right, and Fire, while perceptions could include AlienInFront, BulletInFront, and ObstacleInFront. Only once such a DSL is in place can our framework be effectively implemented.

Availability of Capable LLMs.
Our work assumes the availability of capable LLMs with common sense and programming skills. Training large language models (LLMs) from scratch is resource-intensive, posing significant financial and computational costs. The process requires vast amounts of high-quality data and cutting-edge hardware like GPUs or TPUs.

Necessity of domain experts.
We need a domain expert who understands both the basic grammar of the domain-specific language (DSL) and the domain of interest, including its low-level action and perception primitives and simple control flows. This expert will provide a system prompt that explains the environmental and domain concepts to the LLM when introducing it to a new environment.
That said, adopting our framework to a new domain requires such an expert to provide domain prompts.
Note that the task prompt, describing the goal of tasks, is easy to write and accessible to general users, as it simply converts task documentation into a natural language description.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Please see above for specific questions.
soundness: 2
strengths: Update: Authors addressed my concerns with many additional experiments. I increased my score accordingly.

1. The paper proposes LLM-based initialization for heuristic search methods. This is applicable to broader range of domains.

2. Experimental results indicate sample efficiency.
summary: This paper studies learning programmatic-actions for RL, through heuristic search methods such as hill climbing. The paper focuses on the initialization problem. Rather than randomly initializing programs, the authors propose using LLM guided programs where the environment is described in natural language and a GPT-based model is prompted to bootstrap a set of programs. These programs are further improved using heuristic methods based on environment feedback. The authors also propose a scheduler for the hill climbing that allocates budget based on a sinusoidal scheduling. Finally, they find that generating DSLs directly is challenging due to domain gap; instead, they propose python-dsl where a python program is generated by the LLM and converted into DSL using rules. The resulting initialization and heuristic lead to improvement in sample complexity of the heuristics in a toy RL navigation benchmark.
weaknesses: My main concerns are lack of realistic domains, novelty of the proposed idea, and significance of the experimental comparison.

1. The proposed idea is only tested on a toy RL benchmark which only add marginal practical value. Are there no other environments where programs can be actions and your idea can be applied?

2. In Figure-4, HC and your method compare very similarly. In fact, confidence intervals overlap in many of the tasks. It is not clear if the your method is significantly better. Can you conduct a statistical test to better compare these two methods?

3. Related to (2), HC learning curve is steeper than yours. Can you explain why?

4. While the complexity focus is mainly on number of programs, the cost of running a LLM is ignored. Can you add the cost of initialization to your plots to understand if spending more “flops” is in general better?

5. What is task variance? Is it random initialization in environment state or policy pool?

6. What happens if you initialize other heuristics with LLM-based programs? Do they compare favorably compared to your Scheduling-HC?

7. In line 425, it should be 500k.

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 3
questions: I have two main points relating to the weaknesses mentioned above, which I would like to see addressed before possibly raising my score:
- The authors should run two more ablation studies of their LLM-GS method; one in in which they remove the LLM generated initialisation for SHC, and one in in which they run SHC which the initialisation strategy used by the SOTA HC. This would help address the weakness mentioned above.
- What is exactly the role of the parser? Does the LLM generate both Python and DSL code natively, or does it only generate Python code to be processed by the parser? Did the authors implemenent the parser themselves, of did they use an off-the-shelf parser? 

More but less pressing questions:
- The advantage of SHC in terms of # of program evaluations is manifest. However, how large is its advantage in terms of simple walltime/wait time?
- HC (and therefore SHC as well) is basically a greedy search algorithm. Isn't there a strong possibility of it getting stuck in local maxima? To me this seems to be a bigger problem of HC compared to its sample inefficiency.
- Most of the discussion in section 3 (aside from the outline of the Karel domain) feels more like a Related Work section. I suggest that the authors move it to Related Work or to the Appendix.
- Which initialisation do the authors use for the ablation study in figure 6? To they use LLM-generated programs or randomly generated ones?
 - How is the experiment in section 5.5 conducted? Is the LLM asked to revise programs, and these are then used as initialisation for SHC? Or is SHC completely absent from the experiment?
soundness: 3
strengths: The paper's idea is quite simple but effective, and one can see that it significantly improves over SOTA methods when it comes to sample efficiency/number of program evaluations during search, and for some tasks, also in terms of final average return. The paper is written clearly and features comprehensive ablation studies.
summary: In this paper, the authors propose a framework for PRL (Programmatic Reinforcement Learning) based on a new search algorithm in program space (SHC), whose initial population of programs  is generated from a capable LLM rather than obtained via random generation.
The authors' main contributions are a prompting strategy which correctly outlines each PRL task to the LLM, coupled with the idea of having the LLM generate both Python code and the DSL in which the solution to a given PRL task is supposed to be expressed; this allows the authors to get the LLM to generate programs with the correct DSL syntax, despite the DSL not having presumably been experienced by the LLM  during training.
weaknesses: It is not quite clear which one of the two contributions (SHC and its initialisation with LLM-generated programs) is the one which contributes the most to the final result. From figure 4, it does not appear that the SHC algorithm is really that much more efficient than HC. Plus, the role of the Python -> DSL parser is not quite clear.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: * Do the equations for the scheduled hill climbing algorithm derive from prior work, or is there additional intuition apart from the decision to increase the search budget as the algorithm progresses? There are several key choices here—such as the logarithmic interpolation and sinusoidal schedule—that don’t seem entirely intuitive and are introduced without sufficient justification. Could you provide more details on these decisions?
* Are the program embeddings used for latent space search generated by the LLM?
soundness: 2
strengths: * The authors have identified a significant limitation in existing search algorithms for programmatic reinforcement learning: their localized nature and the crucial role of initialization. They effectively combine this insight with the proven capabilities of LLMs in coding tasks to develop a straightforward yet powerful algorithm, LLM-GS. Furthermore, they propose a search strategy that aligns with their initialization approach, recognizing that they are likely starting from a strong position and can save their search budget for later stages.
* They demonstrate the superior performance of LLM-GS compared to several search baselines, instilling confidence in its effectiveness, particularly in the Karel domain.
* The ablation studies are well-structured and thorough, effectively investigating each component to clarify the sources of performance improvements.
* The authors address potential concerns regarding LLM memorization and data leakage, which adds to the credibility of their results.
* I found the LLM Revision experiment in Section 5.5 particularly fascinating, as it explores whether LLMs can be leveraged more effectively in the search process to refine the initially proposed program. This experiment highlights that existing simple techniques may not perform as well as anticipated.
summary: Programmatic policies for reinforcement learning have gained popularity in recent years, with state-of-the-art methods often employing search techniques that utilize various heuristics and initialization strategies. Given that these search methods are typically localized and proximity-based, the choice of initialization point becomes crucial. The authors present a novel LLM-based search algorithm, LLM-GS, which uses large language models (LLMs) for initializing the search, capitalizing on their coding capabilities. They acknowledge that LLMs often struggle to generate effective initializations within the domain-specific language (DSL) of the problem and introduce a Pythonic-DSL approach to address this challenge. Additionally, they propose a new search algorithm called scheduled hill climbing, which optimizes the search budget by starting with a smaller allocation and gradually increasing it as the search progresses. Through experiments in the Karel the Robot domain, they demonstrate the superiority of their algorithm compared to several search baselines and conduct thorough ablation studies to assess the impact of each contribution on performance.
weaknesses: I have two main concerns with the paper that prevent me from giving it a higher score:
* The authors have conducted experiments solely in the Karel the Robot domain. Testing the LLM-GS algorithm in another domain, such as MicroRTS, would enhance confidence in its effectiveness across different problem domains and DSLs. **Addressing this issue could lead me to reconsider my score.**
* The ablation study comparing search algorithms is quite limited, especially given the close results shown in Figure 6. It appears that the LLM provides such a strong starting point that the specific search algorithm has minimal impact. All search algorithms perform reasonably well on CleanHouse, and the results are very similar among the top 2-3 algorithms on DoorKey. Including results from additional domains would help establish the significance of the search algorithm. Furthermore, the scheduled hill climbing algorithm involves several design choices, such as the sinusoidal schedule and logarithmic interpolation; conducting separate ablation studies on the importance of each of these choices could be beneficial.

Meta-review: The paper presents a mechanism to use LLMs to find policies in a Domain Specific Language (DSL) for the Programmatic Reinforcement Learning paradigm. The technique builds on the Hill Climbing (HC) algorithm that effectively searches for programmatic policies directly in the program space. The proposed technique provides a mechanism to initialize the HC algorithm with promising candidates instead of with random programs. The experiments show the efficacy of the proposed technique in a toy RL navigation benchmark.

Decision: Accept (Poster)