Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search
Authors: Max Liu
Chan-Hung Yu
Wei-Hsu Lee
Cheng-Wei Hung
Yen-Chun Chen
Shao-Hua Sun
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Model
Programmatic Reinforcement Learning
Primary area: reinforcement learning

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.

Published as a conference paper at ICLR 2025
SYNTHESIZING PROGRAMMATIC REINFORCEMENT LEARNING POLICIES WITH LARGE LANGUAGE MODEL GUIDED SEARCH
Max Liu Chan-Hung Yu-x
Wei-Hsu Lee
Cheng-Wei Hung'
Yen-Chun Chen
Shao-Hua Sun
National Taiwan University Miicrssoft
ABSTRACT
Programmatic reinforcement learning (PRL) has been explored for representing policies through programs as a means achieve interpretability and generalization. Despite promising outcomes, current state-of-the-art PRL methods are hindered by sample inefficiency. necessitating tens of millions of nograa--nnvironment interactions. To tackle this challenge, we introduce a novel L.LM-guided search framework (LLM-GS). Our key insight is to leverage the programming expertise and common sense reasoning of LLMs enhance the efficiency of assumption- free, search methods. We address the challenge of LLMs' inability generate precise and grammatically correct programs in domain-specifee lan- guages (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 L.L 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 natural language to obtain performant programs.
INTRODUCTION
Deep reinforcement learning (DRL) has achieved great success from beating the world champion in Go (Silver et al. 2016) to powering the frontier natural language assistants (Ouyang al., 2022 Bai
ct al. (022). and demonstrated great potential in robotics (Jain et al., 2024). autonomous vehi- cles WWag al. 2023b), and recommendation systems (Chen al. (023). However, approximating a policy using a deep neural network makes the decision-making process a black box and, there- fore, less interpretable and trustable to human users (Heuillet et al. (00TT) Subsequently, carefully designed tools and costly human intervention are often required to deploy trustworthy DRL sys- tems (Doshi Velez and Kim 2017). Moreover, DRL frequently encounters substantial performance declines when applied to previously unseen scenarios (Kirk et al. 2023 Cobbe et al. 2018). 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 200T Verma et al. 2018 Bastani et al. 2018 Silver al. 2020). Instead of learning a state-to-action mapping as in DRI., PRI synthesizzs programs written in Domain- Specific Languages (DSLs) as -umaa--eeddable policies that can be parsed and executed, making human inspection possible as 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. (021). Despite the encouraging results, the state-of-the-ar artt PRL algorithms are notoriously inefficient and require tens of millions of program execution in
"Equal contribution. Correspondence to: Shao-Hua Sun <shachuas ent..e.uuuu.............

---

Published as a conference paper at ICLR 2025
environments (Trivedi et al. 2021 Liu et al. 2023 Carvalho et al. 2024). Under the hood, they search or RL algorithmss 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 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 possess internet- scale knowledge that can be retrieved by a natural language interface (Wang et al. 2024 Zheng al., 2024; Taylor et al., 2022). If we view the text on the internet as a "text projection' civilizatiin,, 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 PRI algorithms, pushing PRI. one step closer to practical adoption.
human
To this end, we aim to develop 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 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 PRI., 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. 2023).
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-pure purposs programming languages and DSLs, we design a Pyt strategy that allows LLMs to generate more precise and grammatically correct DSL programs by first producing Python programs. (3) To further optimize the LLM- LLM-geeerated programs, we propose 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 meth- ods (Trivedi et al. 2021 Liu et al. 2023) Carvalho et al. 2024). 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-DSLL strategy leads to a higher ratio of ex- ecutable (i.e. grammatically correct) programs and higher average return compared to directly generating DSL. programs, (2) our proposed search method, Scheduled HC, achieves the best effi- ciency 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
ct al. 2018). state machine (Inala et al. 2020; Koul et al., 2019 Lin et al. 2024). symbolic expres-
sion Verma et al. 2018: 2019 Bhupatiraju et al.) al.] 2018] Landajuela et al. 2021). Logic programming language (Jiang and Luo, 2019), and program written in
language (DSL) (Andre and
Russell 2001 Silver et al. 2020 Sun et al. [220 Zhu et al., 2019 Qiu and Zhu 2022, Moraes and
Lelis| 2024 Mariño et al. 2021 Trivedi et al. 2021 Liu et al. 2023 Carvalho et al. 2024). Trivedi et al. 2021) : Liu et al. (2023) devised PRL tasks in the Karel domain (Pattis) 1981) and proposed
learning embedding spaces of programs using variational autoencoders (Kingma and Welling 2014)
and then optimizing program embeddings using tross-entropy method or RL. Carvaloo et al. 2024)
achieve the state-of-the-an results in the Karel domain (Patris) 1981) by searching in a programmatic
2

---

Published as a conference paper at ICLR 2025
Program p
run mf s m)
Goal: key to open the door
Goal: marker at the goal location
Task completed
Repetition 0..19
45
Perception frontisClear lefilsClear rightlsClear
markersPreeent noMaatersPresent
Condition 5 = perception not perception
Action move| lumLett turnRight
patMarker pickMarker
Statement WHILE e( be) w( $182 |
An example Karel task DOORKEY. The agent first needs to find the key (marker) in left room, which will open the door (wall) to the right room. Navigating to the goal marker in the right room and placing the picked marker on it will grant the full reward for the task. This sparse-reward task has been found to pose significant challenges to previous PRL methods, as it necessitates a greater capability in long- horizon strategy formulation.
Figure 2:
REPEAT Ren r( sr) IF (())
IFELSE b ELSEc( e)
Figure I: The Karel DSL grammar. It deseribes the Karel domain-specifie language's 's actions, perceptions, and control flows. The domain-specifii language is obtained from Liu et al. (023).
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 PRI. framework, we leverage the knowledge and the reasoning ability of LLMs to generate a set of initial programs to bootstrap search algorithms.
Large language models for code generation. With remarkable ability to understand and gen- erate natural languages and codes, LLMs have been widely adopted for code generation (Brown) et al. 2020 Achiam et al. 2023 Nijkamp et al. 2022, Xu et al. 2022 Roziere al. 2023) These works target general-purposs programming languages for software development, egg. Python and C++, with abundant data the internet; in contrast, aim to solve PRI. tasks that require writing programs in given domain-specifie languages. Prior works exploring using I.IMs to synthesize DSL programs via providing LLMS with DSL grammars and few-shot examples, hindsight relabeling, and prioritized experience replay (Wang et al. 2023a Grand et al. 2024 Butt et al. 2024). While they focus on string/array transformations and abstract reasoning (Chollet 2019). 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) 2011; Feser et al. 2015 Polozov and Gulwani [013 Gulwani al. 2017 Parisotto al. 2017| [Bllo et al., 2017). whose goal to find programs that sat- isty given examples, e.g. input/output string pairs. Recent works have explored utilizing search algorithms in DSL to learn libraries (Ellis et al. 2021 Grand et al. 2024). In the regime of pro- grammatic RL, Carvalho et al. (2024) recently applied the Hill Climbing algorithm to the Karel benchmark, achieving state- thethe-rrt performance. Instead of randomly sampling programs via search algorithms. present a framework that integrates knowledge from an LLM with search algorithm to significantly improve the sample efficiency.
An extended discussion on related work can be found in Appendix A
3 PRELIMINARY
The Karel domain. We first review the Karel domain, the de facto test bed for programmatic reinforcement learning research (Bunel et al.) 2018 Chen et al.] 2019 Shhin al.] 2018 Gupta
et al. 2020 Chen et al., 2021). The Karel domain-specific language illustrated in Figure | a robot programming language to control the Karel agent 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., EAT, WHILE, IF, and IFSLS, enable describing complex decision-making logics. More details of the DSL can be found in Appendix B
We illustrate Karel task, DOORKEY, in Figure The agent needs to explore the left room using the DSL actions such as move and turnleft ft as well as the perceptions such as front and rke r.P resent find the key (marker). After picking up the key via ciMarkker, the wall
3

---

Published as a conference paper at ICLR 2025
Taak Award Promet
Gurant Candidata Program
Neighbouring Programs
Erwironment
Scheckule uudd Heration boration
Yook onn
into
Yook spni peoticn teo ralats
Python Program
pasi Pick mackar
c'ambe weiih opena obar connacing bot
bonation
Pythonic DSL Instruction Promot
Parser
Search Center
Exacution Rissuts
Couesu is spec out onturn
lonverd cul...
Search
Region
Raturn
Convent coda D0L
DBL Program
Prog Prgrammatic Space
Beration
out knlur zlore seseptrang....
Clibbng
Update Candidate Program
(a) Generating DSL Program with LLM
(b) Search with Scheduled Hill Climbing
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.
to the right room will unblock. The agent then needs place marker the goal marker located in the right room to receive full task reward. Appendix C presents all the Karel tasks in detail.
The state-of-the-an performance in Karel is achieved by iteratively searching for improved programs according to their episodic return using search algorithms (Carvalho et al. 2024). Next, we introduce the concept of search space, which defines how search algorithms find neighbor programs from set of current candidates for improved performance, and then dive into the search algorithm details.
Programmatic space. In the programmatic space, program can be represented as an abstract syntax tree (AST), where each leaf node in the AST represents a program token (Carvalho et al.) (202)). To obtain its neighborhood program, node is sampled from its AST, and then replaced by a subtree randomly generated using the DSL's production rules and sampling strategies.
Hill climbing (HC). This search algorithm climbs whenever there is a higher place, i.e., moves to program having higher episodic return. Given program, HC generates its k neighborhood programs from the search space. These programs are evaluated in the environment. If one of them has higher episodic return than the initial program, it is set the search center program, and then this process repeats. Otherwise, the algorithm halts and returns the best program evaluated. This search algorithm has major weakness it searches surrounding programs in narrow proximity; thus, the distance between initial programs and optimal programs could upper-boune bound its sample efficiency.
4 LARGE LANGUAGE MODEL GUIDED SEARCH
The hill climbing algorithm (HC) is the tfte-of-thh-an programmatic reinforcement learning (PRL) approach in Karel, at the cost of tens of millions of program interactions (Carvalho et al. 2024). This prevents its application to real-world decision-making problems, where program-enviromment interaction at this scale is inapplicable. Hence, we aim maintain the high episodic return while reducing programs executed in the environments, ie., improves the sample efficiency of PRI. 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 lesss random- random-guessing guessing HC. However, to implement this idea, many challenges rooted in the environment's s domain gap (Section 4.1). DSL's language barrier (Section (.2)), and the inability to optimize closed-source LLMs (Section 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 LLM: "Write a program solve the Karel task DOORKEY," since this is how typical users interact with LLM- software development assistants. Obviously, repeating this until the I.MM spits out correct program is unlikely be more efficient.
4

---

Published as a conference paper at ICLR 2025
Table I: Activate LLM's domain and task awareness. To bridge the domain gap between the target task and the LLM's knowledge, we curate 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 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 ís 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 a 8 8 grid surrounded by walls that is vertically split into two chambers. The left chamber 6 3 grid and the right chamber is x grid. There a marker placed randomly on the left chamber as a key, and another marker placed randomly on the right chamber as goal.
Initial Position
The agent starts on random cell on the left chamber facing east.
Task Goal
The goal of the agent is pick up a marker on the left chamber, which opens door connecting hoth chambers. Allow the agent reach and put a marker on the goal marker.
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 DOORKFY. Therefore, it is crucial to provide 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 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 Appendix D.I] Table providde an example of user prompt for the Karel task DOORKEY. Now that the I.LM 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 user without any programming skills can simply describe the task in natural language to obtain a performant program, as shown in Section (.4
4.2 GENERATING DSL PROGRAMS WITH PYTHONIC-DSE STRATEGY
Given LLMs' widespread success in assisting software development, one might assume an LLM 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 DSL.s 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- purppoe programming language, such as Python, (2) The DSL can be represented by a possibly restricted version of the general-purpost programming language, and (3) The L.MM 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 details are provided, including the action, perception, primitives and
DSL. As shown in Table 2, 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 to- DSL parsing failures. An empirical useful mitigation instructing the L.L generate the DSL program converted from its own output Python program
5

---

Published as a conference paper at ICLR 2025
Table 2: The Pythonic-DSL instruction. The Karel DSL is specified via constrained version of Python with pre-defined functions, including Pythonic-DSL perceptions that allow the agent to observe, and Pythonic-DS. 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 Appendix D.I
Knowledge
Prompt Text
Pythonic-DSL
frent IsClear O): Returns True if there is no wall in front the agent. ma markersPresent (): Returns True if there exist markers on the current cell.
Perceptions
(more perceptions omitted)
Pythonic-DSL
move (): Asks the agent to move forward one cell ... (truncated) turnLeft () Asks the agent rotate 90 degrees counter-clockwise.
Actions
PickMarker () Asks the agent to pick up one marker from the current cell.
(more actions omitted)
Language Constraints
not define other functions besides run ()
do not define variables
(more rules omitted)
as backup. At this point, we have developed the mechanism to instruct an LLM to generate DSL programs given the PRI. task and the DSL. grammar in natural language.
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 key improvement that is crucial when initializing search from LLM- -eneeateedtted programs program-envine eeverammeniviromment interaction scheduling for a more efficient allocation of the interaction budget. The intuition is that L.MMs can often provide good initialization and therefore makes sense to keep a small search budget, Lee with 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 scheduler based on this intuition:
log2 k(n) = (1 rmm)) logg K Kstart + r(m) logg Kend,
where n represents the number of evaluated programs, k(n) denotes function indicating the current number of neighborhood programs based on the number of evaluated programs n. This function's logarithm a linear combination of the logarithms of two hyperparameters, Kstort and Kend, 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 to 1 throughout the evaluation of total of N programs (see Appendix E. With this scheduler, the number of neighbors i is a function of the execution budget used, growing from Kstart to Kend on an exponential basis. We apply this scheduler to Hill Climbing and call this method Scheduled Hill Climbing (Scheduled HC).
Overall, 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 l neighbors at each step following the scheduler in Eq. (I). This process repeated until either the optimal program is found or we meet the maximum program- enviromment interaction budget allowed (N).

---

Published as a conference paper at ICLR 2025
LEARS
HPRL
CEBS
HG
LLM GS (Ours)
0.0
Average Return
0.8
Average Return
Averoge Retturn
0.0
0.6
0.0
0.0
0.
0.
6.
0.0
0.0
0.
0.
10F
102
107
10a
107
101
19a
201
12t
1of
10"
12a
12"
101
12"
30
18"
10
10
of Evaluated Program
of Evaluated Pregram
# of Evaluated Program
of Evaluated Program
(a) STAIRCLIMBER
(b) MAZE
FOURCORNERS
(d) TOPOFF
1.0
Average Return
Average Return
Average Raturn
0
06
0.0
0.4
0
0.4
0.
0.2
0.2
4.
10
Program
Program
Program
Program
(c) HARVESTER
(f) CLEANHOUSE
(g) DOORKEY
(h) ONESTROKE
1.0
1.0
0.8
0.8
Figure 4: Efficiency in the Karel tasks. We compare our proposed LLM-guided search (LLM-GS) framework against existing meth- ods, LEAPS, HPRI,, CEBS, and HC in the Karel and Karel-Hard problem sets. The re- sults show that our LLM-GS is significantly more efficient than these methods.
Average
0.2
0.2
10P
107
12"
10' 30t
107
10' 10
10t 12t
of Evaluated Program
# of Evaluated Program
(i) SEEDER
SNAKE
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 al. (02T) (STAIRCLIMBER, MAZE, FOURCORNERS, TOPOFF, HARVESTER, and CLEANHOUSE) and Karel-Hard (Liu et al. 2023 (DYORKEY, ONESTROKE, SEEDER, and SNAKE). More task details can be found in Appendix
Baselines. We compare our proposed framework with the following methods: LEAPS (Trivedi ct al. 2021) HPRL (Liu et al. 2023). CEBS (Carvalho et al.) 2024), and Hill Climbing (Carvalho
al. 2024 (the current state-of -hrt---rr.. Note that LEAPS and CEBS search programs in learned
latent program space, as introduced in Appendix F
Metrics. For fair comparison in sample efficiency, use the number of programs evaluated to represent the program program-environe environment interaction budget, i.e. a method is more sample-efficient if achieves higher average episodic return fixed budget. Specifically, for each task, the number of task variances is C. Task variances arise from differences in the environment's initial states. Fach program evaluation means executing the program all C task variances obtain average return. We set the number of task variances C' = 32, the maximum number of program evaluation N = 105, i.e., the interaction budget. Programs achieving an average return of 1.0 are considered optimal.
Setup. We use GPT-4 (Achiam et al. 2023 (gpt 1 -4-44-1-0 turbo 2024 -4-009 -09 with temperature= top-p=1.0) as our LLM module to generate the initial search population. The scheduler of our proposed Scheduled HC starts from Kstart = 32 to Kend = 2048. We evaluate our LLM-GS and HC with 32 random seeds and 5 seeds for LEAPPS, HPRI., and CEBS.
Data Leakage. When using modern LLMs, key concern is whether the model has already memorized the content the test bed, leading to biased 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.
7

---

Published as a conference paper at ICLR 2025
Update Stage
327 cnteelenateees 93
sesss cottar ofteoooeee
colerterriireeent ci
M] piottackor
Update Stage
veecce of sodlar shechoeeee of
core
MITZ rollacharsieenets
puttacker
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 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.
5.2 LLM-GUIDED SEARCH SIGNIFICANTLY IMPROVES THE SAMPLE EFFICIENCY
Figure presents the experimental result, indicating that our proposed LLM-GS surpasses all the existing methods by large margin on almost all the tasks.
On the Karel set, our framework completely solves these tasks and exhibits the best sample efficiency. Also, L.M--S performs extraordinarily well on SEEDER, ONESTROKE, and DOOR KEY, which are among the hardest of the Karel-Hard set. We highlight our DOOR result, with an efficiency improvement from not converging even 1M (baselines) converging within around 500K (ours). Existing PRL algorithms struggle at DOOR 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 z 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 two-stage task and thus generates a corresponding two-stage structured program, which much easier for later search to find the optimal program. The full dialogue is presented in Appendix D
We include a plot aggregating the performance across all ten tasks in Appendix a wall-clock time (real-time elapsed) evaluation in Appendix [1 and a statistical significance test in Appendix 0
5.3 ABLATION STUDIES
Which language to generate, Python 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 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 K
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- E (32, 256, 2048) and our proposed Scheduled HC. The results presented in Figure 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 DOOR KBY. 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 -LM-genertted programs as search initialization for Scheduled HC, we compare it to using randomly sampled programs initialization in DOORKEY and CLEANHOUSE. The results shown in Figure 7 suggest
8

---

Published as a conference paper at ICLR 2025
Table Pythonic-DSL. strategy ablation. We compare the programs generated using our proposed Pythonic-DSD DShh 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.
Python
DSL
Pythonic-DSV (ours)
Task
Acceptance Rate
Best Return
Acceptance Rate
Best Return
Acceptance Rate
Best Return
STAIRCLIMBER
88,02=3,57%
1.00=0.00
1.311111.59
0.75+:0.65
88.54114.54% %
1.00=0.00
MAZE
72.40=7.444 49%
0.9420.08
57.8 1.88 12%
0.88=00.07
92.48:13.89 %
0.98:0005
FOURCORNERS
83.07=5.04%
1.00:0.00
93.4942.4334
1.00:0.00
94.0112.4399
1.00
TOPFFF
90.89=2.07%
0.97-:0.07
94,53-14.29%
1.00:0.000
96.35-H3.008%
1.00=0.00
HARVESTER
67.45=7.51%
0.98::0.03
79.69: 64%
0.98
80.21-+-.551 %
0.95
CLEANHOUSE
62.50=3.45%
0.271:028
76.30
0.36::0.14
84.64:14.299 %
0,29=0.27
DOORKEY
90.10=3.86%
0.63-+0.13
75.78+15. 5.09%
0.55=00.05
94,53-13.605 %
0.63=0.14
ONESTROKE
0.774-0.06
85.68 7.8847...00
7..4%% 54%
0.74+-0.09
95.31 3.08
0.83 + 0.08
SEEDER
73.70=4.77%
0.93:10.14
88,28:14.88%
0.66::0110
74.74 10%
0,90= 14
SNAKE
N.76%%
0.09:-0.00
30.47+99.02%
0.09:-0.0
98.96 1.04 %
0.09 : 0.00
1.0
Average Return
Average Return
0.0
Average Return
Average
0.4
CMM
16:20
0.0
0.4
LLM
0.2
02
187
101
10
10
10t
10
10
10
10
10"
10
10 10
10"
10
10
10
10
101
12
10
of Evalusted Program
Evalusted Program
Evaluated Program
of Evaluated Program
(a) DOORKEY
(b) CLEANHOUSE
(a) DOORKEY
(b) CLEANHOUSE
Figure 6: Comparing search algorithms. We compare the proposed Scheduled HC with la- tent space CEM, CEBS, HC-250, and Sched- uled HC, and programmatic space HC-k E (32, 256, 2048] using LLM-initialized programs. Our method achieves comparatively good ef- ficiency in DOORKEY and performs best in CLEANHOUSE, justifying the efficacy of our pro- posed search method.
Figure 7: Comparing initializations. We com- pare initializing the search population using LLM-generated programs or randomly sampled programs, combined with our proposed SHC. The results demonstrate that starting from LLM- generated programs significantly improves effi- ciency and performance, especially in DOORKEY, highlighting the effectiveness of our proposed framework.
that initializing the search with LLM--eneratee programs significantly improves the sample efficiency compared to randomly initializing population-like search methods.
Scheduled HC variants. We ablate the components in the scheduled HC, i.e. logarithmic interpola- tion, sinusoidal schedule, and logarithmic ratio, and present the results in Appendix E.3
5.4 PERFORMANCE ON NOVEL TASKS SHOWCASES THE EXTENSIBILITY OF LLM-GS
A key advantage of proposed LLM-GS framework is its ability adapt 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, PATHFOLLLOw and WALLAVOIDER, as detailed in Appendix 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 X show that by only changing task descriptions, LLM-GS still achieves improved sample efficiency and finds better program policies.
5.5 PERFORMANCE ON MINIGRID DOMAIN VERIFIES THE ADAPTABILITY OF LLM-GS
To verify if our proposed LLM-GS framework can be adapted to another domain, we adopt three tasks in the Minigrid domain, LAVAGAP, PUTNEAR, and REDBLUEDOOR. Unlike the case in Karel, the perception functions in our Minigrid DSL parameterized, i.e., require input parameter such By adapting all aspects of the prompt from the Karel domain
as an object, as detailed in Appendix [ to the Minigrid version, including the domain prompt, the task descriptions, and the Python-to-DSI.

---

Published as a conference paper at ICLR 2025
0.8
Average Retur
08
Average Return
0.8
LLM-GS (Ours)
0.8
HC
0.6
06
0.6
0.6
Average
0.4
0.4
0.2
LLM GS (Ours)
HC
0.2
0.
-22
500c
12"
12"
Evaluated Program
Evaluated Program
Program
Evaluated Program
(a) PATHFOLLOW
(b) WALLAVOIDER
(a) LAVAGAP
(b) PUTNEAR
Figure 8: Performance of PATHFOLLLOw
Figure 9: Performance of Minigrid LavaGap
& WALLAVOIDER. With only changing the
and PutNear. We compare LLM-GS and the berfooorng bascline Karel, i.e. HC, in the Minigrid domain. LLM-GS demonstrates better sample efficiency in both of the two tasks.
task descriptions, LLM-GS surpasses the best- performing baseline HC on two novel tasks, high- lighting the extensibility of LLM-GS.
prompt, we evaluate our method against the strongest baseline, HC. The results presented in Figure show that our proposed LLM-GS is more sample-efficient in the Minigrid domain.
5.6 BEYOND INITIALIZATION PRELIMINARY ATTEMPT ON LLM REVISION
Given the encouraging results from LLM-ine iiitiiiial programs, one might be curious whether LLM itself without the help of any search algorithms can progressively revise and improve its programs once given feedback from the environment, egg., reward. For completeness, we additionally conduct studies with the following LLM-based revision:
Regeneration. Inspired by Chen et al. (2024) and Olausson et al. (2024), 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 ct al. 2024; Wang et al. 2024) and code repair (Chen et al. 2024 Olausson et al. 2024), 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. (2024). additionally point out the line of the program currently being executed as extra hints to the LLM.
We conduct the LLM revision experiments on DOORKEY for five revision rounds, each round with 32 programs with
0.9
Average Return
0.8
5 seeds. The results are presented in Figure 10 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 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 K
0.7
3.6
0.5
Regeneration
Regeneration reward
Agent execution trece
0.4
Agent and execution trace
2
# of Revision Round
Figure 10: LLM revision. The perfor- mance gain of LLM revision saturates within few program revision rounds.
DISCUSSION
We propose the LLMM-uidedd search (LLM-GS) that leverages the programming skills and common sense of LLM to bootstrap the efficiency of assumption-fre random-guessinn search methods. We propose a Pythonic-DSL method to address LLMs' inability to generate precise and grammatically correct programs. To improve 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 show the improved sample efficiency of LLM-GS. Extensive ablation studies verify the effectiveness of our proposed Pythonic- DSL method and Scheduled Hill Climbing. The limitations and future directions of L.M--SS presented in Appendix M
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et Gpt-4 technical report. arXiv preprint arXiv:2303.08774 088774 2023.
David Andre and Stuart Russell. Programmable reinforcement learning agents. In Advances in Neural Information Processing Systems, 2001.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay, In Neural Information Processing Systems, 2017.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862. 2022.
Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference on Learning Representations, 2017.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Neural Information Processing Systems, 2018.
Surya Bhupatiraju, Kumar Krishna Agrawal, and Rishabh Singh. Towards mixed optimization for reinforcement learning with program synthesis. arXiv preprint arXiv:1807.00400: 2018
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. In Neural Information Processing Systems, 2020.
Rudy R 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.
Natasha Butt, Blazej Manczak, Auke Wiggers, Corrado Rainone, David Zhang, Michaël Defferrard, and Taco Cohen. Codeit: Self-improving language models with prioritized hindsight replay. In International Conference on Machine Learning. 2024.
Tales Henrique Carvalho, Kenneth Tjhia, and Levi Lelis. Reclaiming the source of programmatic poli- cies: Programmatic versus latent spaces. In International Conference on Learning Representations, 2024.
Xiaocong Chen, Lina Yao, Julian McAuley, Guanglin Zhou, and Xianzhi Wang. Deep reinforcement learning in recommender systems: A survey and new perspectives. Knowledge- systems, 264: 110335, 2023.
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In Interna- tional Conference on Learning Representations, 2019.
Xinyun Chen, Dawn Song, and Yuandong Tian. Latent execution for neural program synthesis beyond domain-specifii languages. In Neural Information Processing Systems, 2021.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. International Conference on Learning Representations, 2024.
Maxime Snevaller-Boisverr Bolun Dai, Mark Towers, Rodrigo Perez- Vicente, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. In Neural Information Processing Systems, 2023.
François Chollet. On the measure of intelligence. arXiv preprint 1rxiv 2019.
11

---

Published as a conference paper at ICLR 2025
Karl Cobbe, Oleg Klimov, Christopher Hesse, Taehoon Kim, and John Schulman. Quantifying generalization in reinforcement learning. In International Conference on Machine Learning. 2018.
Quentin Delfosse, Hikaru Shindo, Devendra Dhami, and Kristian Kersting. Interpretable and explainable logical policies via neurally guided symbolic abstraction. In Neural Information Processing Systems, 2024.
Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, Subhajit Roy, et al. Program synthesis using natural language. International Conference on Software Engineering. 2016.
Finale Doshi- and Been Kim. Towards rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.0666 086088 2017.
Manuel Eberhardinger, Johannes Maucher, and Setareh Maghsudi. Learning of generalizable and interpretable knowledge in grid-based reinforcement learning environments. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2023.
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé- Lucas Morales, Luke Hewitt, Luc
Cary, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: Bootstrapping inductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation, 2021.
John Feser, Swarat Chaudhuri, and Isil Dillig- Synthesizing data structure transformations from input-output examples. ACM SIGPLAN Notices, 50(6), 2015.
Daniel Furelos-Blanco Blanco, Mark Law, Anders Jonsson, Krysia Broda, and Alessandra Russo. Hierarchies of reward machines. In International Conference on Machine Learning, 2023.
Gabriel Grand, Lionel Wong, Matthew Bowers, Theo X. Olausson, Muxin Liu, Joshua B. Tenenbaum, and Jacob Andreas. LILO: Learning interpretable libraries by compressing and documenting code. In International Conference on Learning Representations, 2024.
Lin Guan, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging approximate symbolic models for reinforcement learning via skill diversity. In International Conference on Machine Learning, 2022.
Sumit Gulwani. Automating string processing in spreadshects using input-output examples. ACM Sigplan Notices, 46(1), 2011.
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trends@ in Programming Languages, 4(1-2):1-119, 2017.
Kavi Gupta, Peter Ebert Christensen, Xinyun Chen, and Dawn Song. Synthesize, execute and debug: Learning to repair for neural program synthesis. In Neural Information Processing Systems, 2020.
Alexandre Heuillet, Fabien Couthouis, and Natalia Díaz-Rodríguez, Explainability in deep reinforce- ment learning. Knowledge-base systems, 214, 2021.
Xueyu Hu, Kun Kuang, Jiankai Sun, Hongxia Yang, and Fei Wu. Leveraging print debugging to improve code generation in large language models. arXiv preprint arXiv:2401.05319 2024.
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Representations, 2020.
Vidhi Jain, Maria Attarian, Nikhil Joshi, Ayzaan Wahid, Danny Driess, Quan Vuong, Pannag Sanketi, Pierre Sermanet, Stefan Welker, Christine Chan, et al. Vid2robot: End-to-end video- conditioned policy learning with cross-attention transformers. arXiv preprint arXiv:2403. 12943, 2024.
Adam Jelley, Amos Storkey, Antreas Antoniou, and Sam Devlin. Contrastive meta-learnigg for partially observable few-shot learning. In International Conference on Learning Representations, 2023.
12

---

Published as a conference paper at ICLR 2025
Zhengyao Jiang and Shan Luo. Neural logic reinforcement learning. In International Conference Machine Learning, 2019.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, al. Model-based reinforcement learning for atari. arXiv preprini arXivv:903, 09009990374440 2019.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
Robert Kirk, Amy Zhang. Edward Grefenstette, and Tim Rocktäschel. A survey of zero-shot generalisation in deep reinforcement learning. Journal of Artificial Intelligence Research, 76: 201-264, 2023.
Hector Kohler, Quentin Delfosse, Riad Akrour, Kristian Kersting, and Philippe Preux. Inter- pretable and editable programmatic tree policies for reinforcement learning. arXiv preprint arXiv:2405. 14956, 2024.
Anurag Koul, Alan Fern, and Sam Greydanus. Learning finite state representations of recurrent policy networks. In International Conference on Learning Representutions, 2019.
Mikel Landajuela, Brenden K Petersen, Sookyung Kim, Claudio P Santiago, Ruben Glatt, Nathan Mundhenk, Jacob F Pettit, and Daniel Faissol. Discovering symbolic policies with deep reinforce- ment learning. In International Conference Machine Learning, 2021.
Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Chu Hong Hoi. Coderl: Mastering code generation through pretrained models and deep reinforcement learning. In Neural Information Processing Systems, 2022.
Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael Ernst. N12bash: corpus and semantic parser for natural language interface to the linux operating system. In International Conference on Language Resources and Evaluation, 2018
Yu-An Lin, Chen-Tao Lee, Chih-Han Yang. Guan-Ting Liu, and Shao-Hua Sun. Hierarchical programmatic option framework. In Neural Information Processing Systems, 2024.
Guan-Tine Ting Liu, En-Pei Hu, Pu-Jen Cheng, Hung-Yt Yi Lee, and Shao-Hua Sun. Hierarchical program- matic reinforcement learning via learning to compose programs. International Conference on Machine Learning, 2023.
Julian R. H. Mariño, Rubens O. Moraes, Tassiana C. Oliveira, Claudio Toledo, and Levi H. S. Lelis. Programmatic strategies for real-time strategy games. In Association for the Advancement of Artificial Intelligence, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human level control through deep reinforcement learning. Nature, 2015.
Rubens O Moraes and Levi HS Lelis. Searching for programmatic policies in semantic spaces. arXiv preprint 2rXiv:2405.05431 2024.
Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-turn program synthesis. In International Conference on Learning Representations, 2022.
Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar-Lezama. Is self-repair a silver bullet for code generation? International Conference on Learning Representations, 2024.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. In Neural Information Processing Systems, 2022.
13

---

Published as a conference paper at ICLR 2025
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. seuro-symbolic program synthesis. In International Conference on Learning Representa- tions, 2017.
Richard E Pattis. Karel the robot: gentle introduction the of programming. John Wiley & Sons, Inc., 1981.
Oleksandr Polozov and Sumit Gulwani. Flashmeta: A framework for inductive program synthe- sis. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2015.
Wenjie Qiu and He Zhu. Programmatic reinforcement learning without oracles. In International Conference on Learning Representations, 2022.
Mohammad Raza, Sumit Gulwani, and Natasa Araii-Frayling. Compositional program synthesis from natural language and examples. In International Joint Conference on Artificial Intelligence, 2015.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. Code Ilama: Open foundation models for code. arXiv preprint arXiv:2308. /2950, 2023.
Reuven Rubinstein and Dirk P Kroese. The cross-entropy method: a unified approach to com- binatorial optimization. Cante-Carlo simulation, and machine learning, volume 133. Springer, 2004.
Eui Chul Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Neural Information Processing Systems, 2018.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittiisser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 2016.
Tom Silver, Kelsey Allen, Alex K Lew, Leslie Pack Kaelbling, and Josh Tenenbaum. Few-shot bayesian imitation learning with logical program policies. In Association for the Advancement of Artificial Intelligence, 2020.
STUDENT. The probable error of a mean. Biometrika, 6(1):1-25, 03 1908. ISSN 0006-3444.
Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In International Conference on Machine Learning, 2018
Shao-Hua Sun, Te-Lin Wu, and Joseph Lim. Program guided agent. International Conference Learning Representations, 2020.
Richard S Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018.
Hao Tang, Darren Key, and Kevin Ellis. Worldeoder, model-based Ilm agent: Building world models by writing code and interacting with the environment. In Neural Information Processing Systems, 2024.
Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. Galactica: A large language model for science. arXiv preprint arXiv:2211.0900. 2022.
Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J Lim. Learning to synthesize programs as interpretable and generalizable policies. Neural Information Processing Systems, 2021.
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, 2018
Abhinav Verma, Hoang Le, Yisong Yue, and Swarat Chaudhuri. imitation-projecet programmatic reinforcement learning. In Neural Information Processing Systems, 2019.
14

---

Published as a conference paper at ICLR 2025
Bailin Wang, Zi Wang. Xuezhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. Grammar prompting for -omaain-peccific language generation with large language models. In Neural Information Processing Systems, 2023a.
Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. Transactions on Machine Learning Research, 2024.
Letian Wang, Jie Liu, Hao Shao, Wenshuo Wang, Ruobing Chen, Yu Liu, and Steven L Waslander. Efficient reinforcement learning for autonomous driving with parameterized skills and priors. arXiv preprint arXiv:2305. 04412, 2023b.
Sida Wang, Samuel Ginn, Percy Liang, and Christoper Manning. Naturalizing a programming language via interactive learning. In Association for Computational Linguistics, 2017.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. In Neural Information Processing Systems, 2022.
Marco A Wiering and Hado Van Hasselt. Ensemble algorithms reinforcement learning. IEEE Transactions Systems, Man, and Cybernetics, Part B (Cybernetics), 2008.
Antonia Wüst, Wolfgang Stammer, Quentin Delfosse, Devendra Singh Dhami, and Kristian Kersting. Pix2code: Learning to compose neural visual concepts as programs. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
Frank Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoomn systematic evaluation of large language models of code. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming, 2022.
Huaixiu Steven Zheng, Swaroop Mishra, Xinyun Chen, Heng-Tze Cheng, Ed Chi, Quoc Le, and Denny Zhou. Take step back: Evoking reasoning via abstraction in large language models. In International Conference on Learning Representations, 2024.
Linghan Zhong, Ryan Lindeborg, Jesse Zhang, Joseph Lim, and Shao-Hua Sun. Hierarchical neural program synthesis. arXiv preprint arXiv:2303.0600 2023.
He Zhu, Zikang Xiong, Stephen Magill, and Suresh Jagannathan. An inductive synthesis framework for verifiable reinforcement learning. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2019.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
Table of Contents
A Extended Related work
17
B Karel DSL. details
Karel tasks
Karel tasks
20
Karel-Hard tasks
22
C.3 New Karel tasks
23
D An example pipeline of our method
24
D.1 The system prompt
24
D.2 The user prompt of the task DOORKEY
26
D.3 The sample response of LLM in the task DOORKEY
26
D.4 Apply post-processing and retrieve the LLM-initialized programs
27
E Scheduled Hill Climbing detail
28
E.1 Design intuition
29
E.2 Variants of Scheduled Hill Climbing components
29
E.3
Ablation study results
29
F
Baselines and their hyperparameters
30
F.1
Latent space
30
F2
LEAPS
30
F3
Hierarchical programmatic reinforcement learning (IPPRL)
31
F4
Cross-entropi beam search (CEBS)
31
F.5
Hill climbing (HC)
32
G Data Leakage
32
H Aggregated performance across all tasks
33
Wall-clock time evaluation on task DOORKEY
35
Statistical test between LLM-GS and HC
35
LLM prompts for ablations and revision Pythonic-DSL.
36
36
Python
39
DSL
40
K.4
Regenerate
41
Regenerate reward
42
K.6
Agent execution trace
44
K.7 Agent and Program exccution trace.
46
L Minigrid Environment
50
L.1
MiniGrid DSL.
50
L.2
Minigrid tasks
................................
50
L.3
Minigrid domain
53
L.4 Minigrid prompts
53
M Limitation
56
16

---

Published as a conference paper at ICLR 2025
A EXTENDED RELATED WORK
Sample efficiency in programmatic reinforcement learning While deep reinforcement learning has achieved tremendous success in various domains (Silver et al. 2016 Ouyang et al. 2022 Bai
al. 2022 Wang et al. 2023b; Chen et al., 2023). still suffers from sample ineffciency prob- lems. Many methods make their effort to improve sample efficiency including modeling transition model (Kaiser et al.) 2019), replay buffer (Mnih et al. 2015), hindsight relabeling (Andrychowic7
et al. 2017). ensembling (Wiering and Van Hasselt 2008), and importance sampling SSutoon[2018, 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 '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 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- bxaexpe (PBE) (Gulwani 2011, Feser al. 2015 Polozov and
Gulwani 2015 Gulwani et al. 2017 Parisotto et al. 2017 Balog el al. 2017), ). whose goal is to lind
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.) [202]] Grand et al. [2024] Eber
hardinger et al., 2023; Wüst et al. 2024) for PBE, imitating policies (Bastani et al. 2018 Kohler
et al.
2024), and object representations (Wüsst et al.) 2024). Neural program synthesis methods (Lin
ict al.
2018 Sun et al. 2018 Desai et al. 20166] Raza et al. 2015: Wang et al. 2017 Zhong al.
2023 Le al. 2022 Parisotto et al. 2017; Balog et al. 2017) learn neural networks from data
to synthesize programs intended by users. Grand et al. (2024) ; Eberhardinger et al. (2023) show that
LLMs can bootstrap program synthesis in the wake stage of library learning; it 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. 2024), prompt
design (Wang et al. 2023a Wei et al., 2022 Wüst et al. 2024 Grand et al. 2024). 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 2011 Feser et al., 2015 Polozoy
and Gulwani 2015: Gulwani et al. 2017] Parisotto et al., |017]] Balog et al. 2017 or DSLs with
learned libraries (Ellis et al. 2001; Grand et al. [2024] Eberhardinger et al. 2023 Wüst et al.) 2024)
for PBE, imitating policies (Bastani et al. 20188) Kohler et al. | (024), and object representations (Wüist
et al. 2024). 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, 2001] Verma et al. 2018 Silver al. (2020), decision trees (Bastani et al.] 2018: Kohler et 2024), state machines (Lin et al. 2024), and symbolic programs (Jiang and Luo, 2019]] Qiu and Zhu 2022 Delfosse et al. 2024]] 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 result, our prompt in Appendix D.I 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 2022)
B KAREL DSL DETAILS
In our framework, we ask the LLM to write the program in Python and then translate it into DSL, all in one response. We include a sample output from the LLM in Appendix [D.3] To translate the responded program an abstract syntax tree (AST), convert a string in DSL into an AST. We implement a translator to convert a Python program into Karel DSL. We list common mistakes LLM made in Table @ and how solve these problems.
off-the-sher Karel parser which can
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 The statement counts are the total
17

---

Published as a conference paper at ICLR 2025
statements connected the root node of the abstract syntax tree (AST), and the statement counts limited to in search 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. (021). The probabilities of the production rules listed in Table 5 The mutation process selects one random node in the AST. We use the production rules to sample 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.
Table 4: Python to DSL converting rules.
Python
DSL
def run():
DEF run m( s m)
while b:
WHILE b c) w( w)
b:
IF c( b c) i)
bf: else:
IFELSE c( c) i( s ELSE c()
for in range(n):
REPEAT R=n (s))(s))
not h
not c( h c)
frontIsClear(
frontIsClear
leftlsClear()
leftlsClear
rightIsClear()
rightlsClear
markersPresent()
markersPresent
noMarkersPresentt)
noMarkersPresent
move()
move
turnleff((
turnleft
turRight()
turRigght
putMarker()
putMarker
pickMarker()
pickMarker
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 categories, this design allows the user easily fill in all categories for
tasks. Here we list
all the information pieces for these tasks. Appendix K.1.2) shows how these 5 different components filled into the placeholders in the user prompt. Appendix D.2 show all filled results with the task DOORKEY There are three sets of tasks: Karel (Trivedi et 2021). Karel-Hard (Liu et al. 2023). and new Karel tasks. Appendix C. lists all Karel tasks, Appendix C.2 lists all Karel-Hard tasks, and Appendix CC3 lists the 2 new tasks. Example figures of Karel tasks are in Figure [T] Karel-Hard
tasks are Figure 12 and new Karel tasks are Figure
18

---

Published as a conference paper at ICLR 2025
Table 5: Probabilities of the production rules.
Category
Rule
Probability
Program P Statement S
Statement
1.0
While
0.15
Repeat
0.03
Concatenate
0.5
0.08
Ifelse
0.04
Action
0.2
Condition
Boolean
0.9
not
0.1
Action
move
0.5
turnLeft
0.15
turnRight
0.15
putMarker
0.1
pickMarker
0.1
Boolean b
frontIsClear
0.5
leftlsClear
0.15
rightIsClear
0.15
markersPresent
0.1
noMarkersPresent
0.1
Number n
i (0 iis 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 mmmove m)
DEF run m( move m)
Brackets addition
DEF run m( WHILE frontIs-
DEF run m( WHILE e( fron- tlsClear e) w( move w) )m
Clear w( move w) )m
Brackets repairment If to IFELSE
DEF run m( move )
DEF run m( move m)
DEF run m( IF o( frontIsClear с) i( move i) ELSE turnLeft
DEF run m IFELSE o( fron- tlsClear e) i( move ELSE e( turnleft e) )m
e) )m
Redundant symbols removal
DEF run m( move() m)
DEF run m( move m)
Illegal symbols transformation
DEF run m( WHILE o( True
DEF run m( REPEAT 1=19 r( move r) m)
c) w( move w)
19

---

Published as a conference paper at ICLR 2025
(a) STAIRCLIMBER
(b) FOURCORNER
(c) TOPOFF
(d) MAZE
HARVESTER
CLEANHOUSE
Figure 11: Illustrations of the initial and desired final state of each task in the KAREL Problem set introduced by Trivedi et (202T). Note that these illustrations are from Trivedi al. (202I) except for STAIRCLIMBER, TOPOFF, and FOURCORNERS. We align our setting with Carvalho al. (2024) to evaluate these tasks in a map of 12x12. The position of markers, walls, and agent's position are randomly set according to the configurations of each task.
C.1 KAREL TASKS
C.1.1 THE TASK PROMPT OF STAIRCLIMBER
Purpose
Prompt Text
Task Name
STAIRCLIMBERSPAREE
Map Description
The map is a 12x grid surrounded by walls with stairs formed by walls and a marker 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 the stairs.
Task Reward
If the agent reaches the marker, the agent receives as an episodic return and 0 otherwise. If the agent moves to invalid position, i.e. outside the contour of the stairs, the episode terminates with a a return.
20

---

Published as a conference paper at ICLR 2025
C.1.2
THE TASK PROMPT OF MAZE
Purpose
Prompt Text
Task Name
MAZESPARSE
Map Description
The map is complex 8x8 grid surrounded by walls and a random marker is placed on an empty cell goal.
Initial Position
The agent starts on a random empty cell of the map facing cast.
Task Goal
The goal the agent is to reach the goal marker.
Task Reward
If the agent reaches the marker, the agent receives I as an episodic return and 0 otherwise.
C.1.3
THE TASK PROMPT OF FOUR CORNERS
Purpose
Prompt Text
Task Name
FOURCORNERS
Map Description
The map is empty 12x12 grid surrounded by walls.
Initial Position
The agent starts on random cell the bottom row of the map facing east.
Task Goal
The goal the agent is to place one marker each corner of the map.
Task Reward
Return 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 12x12 grid surrounded by walls with markers randomly placed on the bottom row of the map.
Initial Position
The agent starts the bottom left cell of the map facing cast.
Task Goal
The goal of the agent place extra marker top of every marker 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 -1 return.
C.1.5 THE TASK PROMPT OF HARVESTER
Purpose
Prompt Text
Task Name
HARVESTER
Map Description
The map is 8x8 grid surrounded by walls that starts with a marker on each cell.
Initial Position
The agent starts on random cell on the bottom row the map facing east.
Task Goal
The goal 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.
21

---

Published as a conference paper at ICLR 2025
C.1.6
THE TASK PROMPT OF CLEANHOUSE
Purpose
Prompt Text
Task Name
CLEANHOUSE
Map Description
The map a complex 14x22 grid made many connected rooms and is surrounded by walls. There 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
H
(a) DOO
(b) ONESTROKE
(c) SEEDER
(d) SNAKE
Illustrations of the initial and final state of each task in the Karel-Hard problem set introduced in by Liu et al. (023). The position of markers, walls, and agent's position are randomly set according to the configurations of each task.
Figure 12:
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 vertically split into two chambers. The left chamber is 6x3 grid and the right chamber is 6x2 grid. There is marker placed randomly on the left chamber as a key, and another marker placed randomly the right chamber as 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 door connecting both chambers. Allow the agent reach and put 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.
22

---

Published as a conference paper at ICLR 2025
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 marker in every empty cell of the map.
Task Reward
Return 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 marker randomly placed on the map.
Initial Position
The agent starts a random cell of the map facing east.
Task Goal
The agent acts like the head of 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 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.
touch the
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, PATIFFLLOWW and WALLAVOIDER. Here we list the task prompts.
23

---

Published as a conference paper at ICLR 2025
(a) PATHFOLLOW
(b) WALLAVOIDER
Figure 13: Illustrations of the initial and final state of the two new proposed tasks.
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 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 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 leaving the rugged markers line two cells away will have 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 any wall will terminate the episode with -1 return.
D AN EXAMPLE PIPELINE OF OUR METHOD
This is our pipeline of getting programs from LLM with the task DOO.KEY. Appendix D.I details the system prompt, Appendix D.2 provides all the information the task DOORKEY. Appendix [.3 lists the LLM response, and Appendix D.4 gives an example of how we get the Karel DSL program
D.1 THE SYSTEM PROMPT
You 're currently navigating within Karel environment, which is essentially a grid world. In this context, a "world" is referred to as "map." Within this map, there's entity
24

---

Published as a conference paper at ICLR 2025
known the "agent," capable of movement, changing direction, as well as picking up and placing markers on the map.
Additionally, there are obstacles called "walls" that impede the agent 's progress; whenever the agent encounters a wall, it turns around. Furthermore, there scattered throughout the map at the beginning, though the agent has the ability both pickup and place these markers as needed.
pre-existing "markers"
Your objective is to generate the appropriate Python program based on given task name and description. This Python program will encompass actions anablngg the agent to engage with the environment, alongside perceptions facilitating the agent's recognition of the environment's dynamics.
Here the available actions for the agent: () Asks the agent to move forward one cell. The agent will instead turn left twice if a wall is blocking its way.
suurnLeft (): Asks the agent to rotate 90 degrees counterclockwise.
turnRight (): Asks the agent rotate 90 degrees clockwise.
pickMarker Asks the agent to pick up one marker from the current cell.
(utMarker Asks the agent to put down one marker on the current cell.
Here are the available perceptions of the agent: front (): Returns True if there is wall in front of the agent.
leftTsClear (): Returns True if there is wall on the agent rift.rigghtssleerr() Returns True if there is no wall on the agent's right.
markersPresent (): Returns True if there exist markers on the
current cell.
noMarkersPresent (): Returns True if there is no marker on the current cell.
There are some limitations for the Python program: do not define other functions besides run()
do not call other functions
do not define variables
do not use True, False, break, continue, return, ==, !=, elif, or, and
Python to Karel dsl conversion
1. "def run(): s" to "DEF run m S m)"
2. "while
s" "WHILE el c) w( S w)
3. "if b: s" to "IF el b c) i{ I)"
4. "if s else: s" to "IFELSE c( c) i 1) ELSE e e)"
5. "for i in range (n) s" to "REPEAT R=n r( r)"
6. "not h" to "not d h c)"
7. "frontIsclear((" to "frontIsClear"
8. "leftIsClear()" to "leftIsClear"
9. "rightIsClear() " to "rightIsClear"
10. "markersPresent () to "markersPresent
11. "noVarkersPresent"
"noMarkersPresent"
12. "move() to "move"
13. "turnLeft () "turnLeft"
14. "turnRight () to "turnRight"
15. "putMarker ()* to "putMarker"
25

---

Published as a conference paper at ICLR 2025
16.
"pickMarker () to "pickMarker"
D.2 THE USER PROMPT OF THE TASK DOORKEY
I'11 provide you with the task name and description.
Task name: DOORKEY
Task map: The map is 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 marker
placed randomly on the left chamber as a key, and another marker placed randomly
goal. Task agent position: The agent starts on a random cell on the left chamber facing east.
the right chamber
Task goal: The goal of the agent is to pick a marker on the left chamber, which opens a door connecting both chambers. Allow the agent to reach and put marker on the goal marker. Task return: Picking up the first marker yields a 0.5 reward, and putting marker on the goal marker yields an additional 0.5.
1. Generate simple and short Python program to tackle the task, avoid using comments.
2. Convert the Python program to the Karel dsl program.
D.3 THE SAMPLE RESPONSE OF LLM IN THE TASK DOORKEY
### Pythen Program for Task DOORKEY
"python
def run ()
while not markersPresent ():
if FrontIsClear ():
m)
else:
turnLeft ()
pickMarker ()
turnLeft
while not markersPresent ()
if ErontIsClear ():
move
else:
turnLeft ()
putMarker ()
### Karel DSL Conversion
DEF run m WHILE not c markersPresent c) ( IF ErontIsClear i move 1)
ELSE el turnLeft
26

---

Published as a conference paper at ICLR 2025
PickMarker turnLeft m WHILE not c( markersPresent c) w IF front {(
move 1)
ELSE e(
turnLeft e) w)
putMarker m)
D.4 APPLY POST-PROCESSING AND RETRIEVE THE LLM-INITIALIZED PROGRAMS
For the Python program part in LLM response, convert the Python program to DSL program through the rule-based method and apply post-processing to correct minor mistakes. For the DSL part, directly apply post-processing correct minor mistakes. Appendix D presents the original Python program, the converted DSL, and the post-processed DSI. Appendix D.4.2 shows the original DSL and the post-processed DSL., All of the post-processing rules are listed in Table
D.4.1 PYTHON PROGRAM PART
Listing 1: Original Python program
def run ()
while not markersPresent ():
if TrontTsClear ()
m)ve
else:
turnLeft ()
pickMarker
turnLeft
while not markersPresent ()
if ErontIsClear
m)ve
else:
turnLeft ()
putMarker ()
Listing 2: DSL program converted through the rule-based method
DEF run m
WHILE c not c markersPresent c) w IFELSE C FrontIsClear c) i(
move 1)
ELSE e
turnLeft e) w)
PickMarker
turnLeft
WHILE c( not c markersPresent c) c) w
IFELSE C frontIsClear c) i(
move 1)
ELSE el
turnLeft
PutMarker m)
Listing 3: DSL program after post-processing
27

---

WHILE c noMarkersPresent c) ( Published as a conference paper at ICLR 2025
DEF m ( WHILE c( noMarkersPreaent c) W
IFELSE C( FrontIsClear c) i
move 1)
ELSE el
turnLeft e) w)
PickMarker
turnLeft
WHILE of noMarkersPresent c) W IFELSE c( frontIsClear c) i
move i)
ELSE e( turnLeft e) w)
putMarker m)
D.4.2 DSL PROGRAM PART
Listing 4: Original DSL program
DEF run m WHILE not c markersPresent c) w
IF Isont i(
move 1)
ELSE e(
turnLeft e) W)
PickMarker
turnLeft
WHILE not c( markersPresent c) (
IF ErontIsClear i(
move 1)
ELSE e turnLeft putMarker m)
Listing 5: DSL program after post-processing
DEF run m
WHILE c noMazkersPresent c) W IFELSE C( frontIsClear c) i
move 1)
ELSE e turnLeft e) w)
PickMarker
turnLeft
IFELSE c( front c) i( move 1)
ELSE e( turnLeft e) w)
putMarker m)
E SCHEDULED HILL CLIMBING DETAIL
This Scheduler is designed for improving sample efficiency. is the number of programs evaluated, and Kstars and Kend are arper-parameters representing the initial and terminal number of neighbors to search, respectively. r(n) is sinusoidal function that smoothly increase from to 1 over the course of total programs evaluated in the environment. We provide detailed equation in Equation ( and Equation 3
28

---

Published as a conference paper at ICLR 2025
logzk(n) (1 -r(n)) log, Kstart + r(n) logg Kend,
(2)
2r(n) = sin (
2 log log N
1) x 7
2 +1.
(3)
E.1 DESIGN INTUITION
Scheduled HC comprises logarithmic interpolation, sinusoidal schedule, and logarithmic ratio. Our intuition to logarithmic interpolation and logarithmic ratio aims allocate the most appropriate neighborhood size, k, to tasks of varying difficulties. The logarithm of the number of executed programs provides an indication of task difficulty, with the intuition that the optimal lt should increase exponentially according to the structure of AST. For the sinusoidal schedule, we prioritize maintaining a stable neighborhood size during both the early and final stages of the training process.
E.2 VARIANTS OF SCHEDULED HILL CLIMBING COMPONENTS
We add their linear counterpart, resulting in 2 variants for each component and 8 variants (2x2x2-8) on the whole.
F.2. INTERPOLATION VARIANTS
Logarithmic interpolation
logzk(n) = -r(n)) (r(n))logg log2 Kstart r(n) logz Kend
(4)
Linear interpolation
k(n) = (1 r(n)) start + r(n) Kend
(5)
E.2.2 SCHEDULE VARIANTS
Sinusoidal schedule
2r(n) = sin (2 ratio 1) x
π 2.
(6)
Linear schedule
r(n) ratio
E.2.3 RATIO VARIANTS
Logarithmic ratio
log n
(8)
log N
Linear ratio
(9)
N
E.3 ABLATION STUDY RESULTS
We conduct experiments for all 8 variants on DOORKEY and CLEANHOUSE for 8 seeds. The results shown Figure 14 present no significant differences between variants.
29

---

Published as a conference paper at ICLR 2025
1.0
1.0
Average Return
0.0
Average Return
0.0
0.4
0.4
Log Sm-Log 1Ouns)
Ln-Shroog
0.0
Log Sm-Lin
Log-Un-
Ln-SinLin
Li-lin-oog
0.0
Un
Un
10"
10a
10.
of Evaluated Program
of Evaluated Program
(a) DOORKEY
(b) CLEANHOUSE
Figure 14: Comparing Scheduled HC variants. We compare our proposed Scheduled HC with its variants. The label stands for interpolation-scheulleeeea interpolation, sinusoidal schedule, and logarithmic ratios, our label Log-Sin-Log. The results indicate no significant differences between all Scheduled HC variants.
For example, when using logarithmic
F BASELINES AND THEIR HYPERPARAMETERS
We compare our framework to four baselines, LEAPS (Tivedi et al. 2021). HPRL (Liu et al. 2023 CEBS (Carvalho al., 2024), and HC (Carvalho et al. 2024). LEAPS, HPRI, and CEBS search programs in the latent spaces, while HC searches programs in the programmatic space. We first introduce the concept of latent space in Appendix F.I then dive into the details each baseline in the following sections. The pseudo-code of CEBS described in Algorithm | and the pseudo-code of HC is described Algorithm
F.1 LATENT SPACE
In addition the programmatic space, another choice is to search in a learned latent space (Trivedi al. 2021 Liu et al, 2023), constructed by training a variational autoencoder on randomly generated DSL programs. To sample neighbor program, 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.
F.2 LEAPS
LEAPS utilizes the Cross-entropy method (CEM) RRubinstein and Kroese 2004) as its search strategy. It first generates neighborhood programs from its latent space and evaluates their episodic return on the Karel environment (Trieddi et al. 2021). Next, if the average return over the top- E neighborhood programs is higher than the best-seen average return, it continues the process the mean latent embedding of the top-E neighborhood programs. When the average return no longer increases, the program with the highest episodic return returned.
The hyperparameters of the LEAPS baseline are from LEAPS (Trivedi et al. 2021 and HPRL (Liu ct al. 2023). 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. (2024), thus we do not have hyperparameters of exponential decay. Also, the re- ce-imlementation samples candidate from fixed normal distribution which is hyperparameter in LEAPS (Trivedi et al. 2021). In Table 7 k is the neighborhood size and the candidate, o the noise scale. In LEAPS and HPRL, they use an elite ratio represent the candidate programs. For better understanding, round F. to be integer.
30

---

Published as a conference paper at ICLR 2025
Table LEAPS hyperparameter settings on all KAREL tasks.
TASK NAME
k:
E
STAIRCLIMBER
32
0.25
2
FOURCORNERS
64
0.5
13
TOPОFF
64
0.25
3
MAZE
16
0.1
2
CLEANHOUSE
32
0.25
2
HARVESTER
32
3
DOORKEY
32
0.25
3
ONESTROKE
64
0.5
3
SEEDER
32
0.25
3
SNAKE
32
0.25
F.3 HIERARCHICAL PROGRAMMATIC REINFORCEMENT LEARNING (HPRL)
HPRL (Liu et al. 2023 aims to improve LEAPS by composing several programs to represent more complex behaviors. Given a learned latent space, meta-policy learns predict sequence of actions, i.e. programs, by optimizing the return obtained by executing the composed programs using reinforcement learning. HPRL considers the discount factor y the meta-MDP; as a result, the evaluation method is not the same as our problem formulation. To ensure fair comparison, we record one million programs explored by meta-policy in the training stage. 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 T we list hyperparameters modified in the HPRL training script. All other hyperparameters remain the same as described in HPRL.
Table HRPL hyperparameter settings on all KAREL tasks.
TASK NAME
training steps
height
weight
STAIRCLIMBER
50K
FOURCORNERS
500K
12
12
TOPÖFF
5M
12
12
MAZE
50K
CLEANHOUSE
500K
12
22
HARVESTER
SM
DOORKEY
SM
ONESTROKE
5M
SEEDER
5M
SNAKE
SM
F.4 CROSS-ENTROPY BEAM SEARCH (CEBS)
CEBS (Crvalho et al. 2024) extends CEM to maintain a set of E candidate programs to perform beam search. Unlike CEM which only maintains one candidate program. CEBS maintains set of E candidate programs, to perform beam search. In other words, CEBS searches all the neighborhoods of the top-F programs.
It also utilizes the pre-trained VAE weight from LEAPS (Trivedi et al. 2021) ) to search the program the latent space. All the hyperparameter follows the original CEBS with neighborhood K equal to 64, candidate E equal to 16, and noise ratio a equal to 0.25 for all ten Karel tasks. The pseudo-code described Algorithm [
31

---

Published as a conference paper at ICLR 2025
F.5 HILL CLIMBING (HC)
HC (Carvalho et al. 2024) is state-of-the-art algorithm solving Programmatic Reinforcement Learning tasks. All the hyperparameter follows the original HC with neighborhood K equal 250
for all ten Karel tasks. The pseudo-code is described in Algorithm
Algorithm 1 Cross-entropy beam search algorithm (Carvalho al. 2024)
Require k, number of nei neighborhood; E number of top candidate; T, the task; VAE, the program encoder and decoder.
Ensure: p² the highest averaged return over 32 task variants.
1: ~~ I)
2: P decode(z)
3: steps +0
4: Relurn f- evaluate(p,))
5: p² p
6: Mean -00
Pt get-neighbor(pe
8: while steps < 1000000 do Candidates +
10: for each Pnew in P do
11: T +=valuate(pneu T)
12: Candidates Pnew)
13: if r Return then
14: O Pnew
15: Return tr
16: end if
17: end for
18: Elites + Top (oppE(Candidate)
19: if Mean > get-mean Elites) then
20: break
21: end if
22: if Relurn= =1 then
23: break
24: end if
25: Mean + get-eetee mean(Elites)
26: P []
27: for each Prew in Elites do
28: P.extend(get- teighggotnnighhhor(e.... k/E))
29: end for
30: sleps +- sleps +
31: end while
G DATA LEAKAGE
While our proposed framework shows significant improvement over the baselines, some may ques- tion 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., [021 Liu et al. 2023 Carvalho et al. 2024), thus making data leakage potential concern. Still, we would like to rule out this possibility from three aspects: the timeline of previous works, the L.MMs' understand- ing 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. (2023) in July 2023, the optimal programs were not included in Liu et al. (2023) since their proposed method could only partially solve the tasks. Carvalho et al. (2024). made public in 2024, are the first provide optimal programs for the Karel-Hare tasks. Hence, our LLM (gpt-4-turbo-200 tuwbooo022-004--a2 with knowledge up to December 2023) could not access the optimal KareI-Hard tasks programs.
32

---

Published as a conference paper at ICLR 2025
Algorithm 2 Hill climbing algorithm (Carvalho et al. 2024)
Require: T, the task; k, number of neighborhood.
Ensure: p², the highest averaged return over 32 task variants.
Initialize p with random solution
2: Return evaluate(p,1)
p F
4: improved +- True
steps 0
6: while improved and steps < n do improved + False
8: Neighbors f- get-neighbor(AAs
for each Pnew in Neighbors do
10: Theu + =evaluatePrez:
11:
if Tnou > Return then
12:
O0 Pnew
13: Return &- Tnew
14: improved +- True
15: break
16: end if
17: sleps f- sleps +
18: end for
19:
P p /²
20:
end while
The Karel environment is used to test Programmatic Reinforcement Learning (PRL) algorithms and includes a variety of tasks. There are six tasks in the Karel test set and four more challenging tasks in the Karel-hard thesize Programs as Interpretable and Generalizable Policies" and "Hierarchical Programmatic Reinforcement Learning via Learning Compose Programs."
set. These tasks utilized the research papers "Learning Syn-
Can you list all ten tasks and their task descriptions based on what you have learned?
Figure 15: The prompt that asks GPT-4 about the Karel PRL tasks
Does the LLM know the Karel tasks?. To verify if the LLM knows the Karel tasks used in our work. prompt GPT-4 by providing the paper names of LEAPS TTrieedi al., 2021) and HPRI. (Liu et al. 2023) 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 our work. The full prompt and response listed in Figure 15 and Figure [6
Two novel tasks. We additionally design two novel tasks that have not been used in any existing work, PATHFOLLLOW, and AVLLAVO illustrated in Figure 13] The details of these two novel
tasks are Appendix C.3 The results Figure & show that our framework can extend to new tasks
that are impossible to leak to L.MMs.
H AGGREGATED PERFORMANCE ACROSS ALL TASKS
To clearly examine the performance across all the tasks, include a plot that aggregates the perfor- mance of all main results (Figure 4 in Figure 17 Our proposed LLM-GS framework significantly outperforms the existing methods.
33

---

Published as a conference paper at ICLR 2025
Sure! The Karel environment, based on the educational programming language designed to introduce students the basics of programming, provides programmatic challenges that both regular and hierarchical reinforcement learning algorithms can address. Here a summary of the tasks typically included in both the Karel test and the Karel-hard set based common challenges noted in similar environments and research contexts:
KAREL TEST SET TASKS
1. Move to Wall: The task is for the agent (Karel) to move forward until it encounters wall.
Turn Right: Teach Karel turn right using sequence of commands (since Karel inherently only has command to turn left).
Collect Marker: Karel needs to navigate towards and collect a marker from the grid.
Avoid Hurdles: Karel must move from one point 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 different location.
6. Maze Solving:
Karel needs to find path from one point another in maze-like structure.
KAREL-HARD TEST SET TASKS
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 appear
suddenly, requiring Karel to adapt its path dynamically.
Conditional Logic Usage: Tasks where Karel must use sensors to make decisions based the conditions of its environment (e.g., If front is clear, move forward; otherwise, turn left).
Complex Maze:
More intricate and challenging mazes that require advanced pathfind- ing algorithms and possibly backtracking strategies.
While these 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 implemen- tation the focuses of different research papers 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.
Figure 16: The GPT-4 response about Karel PRL tasks
1.0
Average Return
0.8
0.6
0.4
Ours
0.2
HC
CEBS
0.0
HPRL
-0.2
10a
10a
102
10
10a
10a
10f
# of Evaluated Program
Figure 17: Aggregated performance across all the tasks. The aggregate performance across all ten lasks. Our proposed LLM-GS framework surpasses all existing methods by a large margin.
34

---

Published as a conference paper at ICLR 2025
1.0
Average Return
0.6
0.4
0.2
0.0
HC
LEAPS
-0.2
100
10a
10a
10a
10*
10a 10
Of seconds
Figure 18: Wall-clock time evaluation on the DOORKEY task. We evaluate the wall-clock time performance on the DOORKE: KEY task, with the x-axis representing the number of seconds on logarithmic scale. The plot also includes the time LLM takes to generate the programs. The results demonstrate the superiority of our proposed LLM-GS framework.
I WALL-CLOCK TIME EVALUATION ON TASK DOORKEY
We provide a wall-clock time evaluation (real- time elapsed) for the DOORKEY task in Figure 18 with the x-axis showing the number of seconds on log scale, It also accounts for the time LLM takes to generate the programs. The result highlights the superiority of our proposed LLM-GS framework.
p-value- Left Axis
LLM-GS (Ours) - Right Axis
HC Right Axis
1.00
1.50
0.25
Average Retum
0.80
Aver age Raturn
0.80
Average Ratum
Average Retuing
3.40
pryalug
.0
pvplus
poyalue
0.40
82
0.20
0.20
0.20
0.20
3.98
8.88
0.0
8:88
0.0
8:8
10'
10
Tea
10
10'
Program
Program
Program
Program
(a) STAIRCL.MMBR
(b) MAZE
(c) FOURCORNERS
(d) TOPOFF
1.00
1.0
0.80
Average Reeum
Aver Average Return
Avarage Ricturn
Average Return
p-valug
p-valus
p-yalue
8.88
88
0.0
8.83 10'
10
10'
12
12'
107
10
10
10
10
10'
T6a
30'
10'
10
30t
10"
10"
of Evaluated Program
of Evaluated Program
# of Evaluated Program
#: of Evaluated Program
(e) HARVESTER
(f) CLEANHOUSE
DOORKEY
(h) ONESTROKE
1.00
1.0
1.00
3.0
0.80
0.80
Average Return
Figure 19: Statistical test the Karel and Karel-Hard tasks. We use the Student's t-test measure the mean of LLM-GS and HC. The p-value of the t-test (red line) follows the left axis, while LLM-GS and HC use the right axis. The brown dotted line presents the significant level of the null hypothesis. LLLM-GS outper- forms HC on 8 10 tasks when the search ends.
pavalug
3.40
Average
0.20
3,93
8.60
Evaluated Program
of Evaluated Pregram
(i) SEEDER
(j) SNAKE
J STATISTICAL TEST BETWEEN LLM-GS AND HC
Since the confidence interval of LLM-GS overlaps with that of HC in some tasks, conduct hypothesis testing between these two methods for better comparison. The null hypothesis Ho is that the mean of LLM-GS is greater than HC. We use Student's t-test (STUDENT 1908) to test the
35

---

Published as a conference paper at ICLR 2025
distribution of LLM-GS and HC at the same number of evaluated programs. Figure shows the p-value from the t-test across the evaluated program on the Karel and Karel-hard tasks. We adjust the primary y-axis (left) and the secondary y-axis (right) to have the same scale. The brown dotted line is 0.05. If the red lines (p-value) are under the brown dotted line, LLM-GS statistically outperforms HC. If the red lines are above the brown dotted line, LLM-GS fails surpass HC.
The result shows that our method significantly outperforms HC on STAIRCLIMBER, MAZE, FOUR- CORNERS, DOORKEY, and SEEDER. On task TOPÖFF, LLM initialization can not outperform HC in the first few attempts but has superior efficiency when the search ends. On the task HARVESTER, LLM-GS can surpass HC in less than a thousand programs, but cannot find a difference at the end of the search. On the task CLEANHOUSE, LLM-GS cannot outperform HC except for the LLM initialization. On the task ONESTROKF and SNAKE, LLM--S eventually surpasses HC when the search process ends. The LLM initialization (32 is at the middle point of 10 and 100) surpasses HC on all tasks. On the other hand, LLLM-GS outperforms HC on 8 10 tasks (except for HARVESTER and CLEANHOUSE) when the search ends.
K 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 re- turn. 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 con- tain 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 Ap- pendix C, all of the dase-dependent information can be filled in the placeholders. Appendix [D.2shows the full Pythonic-DSSL prompt with the task DOORKE, filled in the placeholders. The Pythonic-DSL. prompts are in Appendix K.] and the Python prompts are in Appendix K.2 and the DSL prompts are in Appendix K.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 Appendix K.I 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 Appendix K.4 We ask the L.MM to regenerate with the program relating reward, and the revision prompt of the Regenerate with reward is in Appendix K.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 Appendix K.6 We provided the action/perception call and executing line, and the revision prompt of the Agent and program execution trace is in Appendix K.7] The program Listing ] the revision target of our method revision method in Appendix K.6 and Appendix K.7 Figure 20 the trajectories of the program we used in method Appendix K.6 Appendix K.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.
K.1 PYTHONIC-DSI.
K.1.1 SYSTEM PROMPT
You' You're re currently navigating within a Karel environment, which is essentially a grid world. In this context, a "world" is referred to as a "map." Within this map, there's an entity known as the "agent, as well as picking up and placing markers on the map.
capable of movement, changing direction,
Additionally, there are obstacles called "walls" that impede the agent's progress; whenever the agent encounters wall, it turns around. Furthermore, there are pre-existing "markers" scattered throughout the map at the beginning, though the
36

---

Published as a conference paper at ICLR 2025
(a) This is the initial state of one of (b) This is the last step of the trajec-(e) The program ends at step 47 and DOORKEY the task variants.
tories the prompts.
reward granted.
Figure 20: This is the demonstration of the task DOORKEY. The Karel agent can only reach the surrounding grids the left chamber in the trajectory.
Listing This is the program for LLM revision.
def run ()
while noMarkersPresent ():
if #rontIsClear() ():
move ()
else:
turnLeft ()
frontIsClear ()
move ()
turnRight ()
pickMarker
while noMarkersPresent ():
if frontIsClear
()
else:
turnLeft ()
putMarker
Listing 2 The revision results of Appendix K.6
while noMarkersPresent ():
if front ():
move
else:
turnLeft ()
pickMarker() ()
while IrontIsClear ():
move ()
turnRight ()
while noMarkersPresent: ():
if ErontIsClear
move
else:
turnLeft ()
if FrontIsCleat ():
move ()
turnRight ()
putMarker
37

---

Published as a conference paper at ICLR 2025
Listing 3 The revision results of Appendix K.7
while noMarkersPresens O)
if FrontIsClears ():
move ()
else:
turnLeft
pickMarker ()
while noMarkersPresent :):
if rightTsclear
turnRight() ()
m)ve
else:
if frontIsClear() ():
move ()
else:
turnLeft ()
putMarker
agent has the ability to both pickup and place these markers as needed.
Your objective is to generate the appropriate Python program based on given task name and description. This Python progran will encompass actions enabling the agent to engage with the environment, alongside perceptions facilitating the agent's recognition of the environment's dynamics.
Here are the available actions for the agent: () Asks the agent to move forward one cell. The agent will
instead turn left twice if a wall is blocking its way.
Curnneft (): Asks the agent to rotate 90 degrees counterelockwise. turrRiggt (): Asks the agent to rotate 90 degrees clockwise.
pickMarker (): Asks the agent to pick up marker from the
current cell.
(utMarker Asks the agent put down one marker on the current cell.>
Here are the available perceptions of the agent: front (): Returns True there is no wall in front of the agent.
leffiscleerr (): Returns True if there is no wall on the agent 's left.
Iighh (): Returns True if there is no wall on the agent's right.
markersPresent (): Returns True if there exist markers on the
current cell.
noMarkersPresent (): Returns True if there is no marker on the current cell.
There are some limitations for the Python program: do not define other functions besides run ()
do not call other functions
do not define variables
do not use True, False, break, continue, return, ==, !=, elif, or, and
Python to Karel dsl conversion
38

---

Published as a conference paper at ICLR 2025
1. "def run (): s" to "DEF m m)
2. "while b: s" to "WHILE of b c) w S w)
3. "if b: s" to "IF o( b i( i)"
4. "if b: 8 else: s" to "IFELSE c( b c) i 8 i) ELSE e s e)
5. "for i in range s" to "REPEAT Ren r)
6. "not h" to "not C h c)"
7. "firotIsCClear() to "frontIsclear"
8. "leftIsClear()" to "leftIsClear"
9. "rightIsclear() to "rightIsClear"
10. "markersPreseet ()" to "markersPresent
11. "noMarkerssreeeent
to "roMarkersPresent"
12. "move () to "move"
13. "turnLeft () to "turnLeft"
14. "turnRight () to "turnRight"
15. "putMarker ()* to "putMarker"
16. "pickMarker to "pickMarker"
K.1.2 USER PROMPT
I'1l provide you with the task name and description.
Task name: <<Task Name>>
Task map: <<Map Description>>
Task agent position: <<Initial Position>>
Task goal: <<Task Goal>>
Task return: <<Task Reward>>
1.
Generate simple and short Python program to tackle the task,
avoid using comments.
2. Convert the Python program to the Karel dsl program.
K.2 PYTHON
K.2.1 SYSTEM PROMPT
You' re currently navigating within a Karel environment, which is essentially a grid world. In this context, a "world" is referred to as a "map." Within this map, there's an entity known the "agent," capable of movement, changing direction, as well as picking up and placing markers on the map.
aaditionally there are obstacles called "walls" that impede the agent s progress; whenever the agent encounters a wall, it turns around. Furthermore, there are pre-existing "markers" scattered throughout the map at the beginning, though the agent has the ability to both pickup and place these markers as needed.
Your objective is to generate the appropriate Python program based on given task name and description. This Python program will encompass actions enabling the agent to engage with the environment, alongside perceptions inns pacilitating the agent 's recognition of the environment's 's dynamics.
Here are the available actions for the agent:
move Asks the agent to move forward one cell. The agent will instead turn left twice if wall is blocking its way. (urnLeft() () Asks the agent to rotate 90 degrees counterclockwise. turnRight (): Asks the agent to rotate 90 degrees clockwise.
39

---

Published as a conference paper at ICLR 2025
pickMarker (): Asks the agent to pick up marker from the current cell.
putMarker Asks the agent to put down marker the current cell.
Here are the available perceptions of the agent:
fronttsclear (): Returns True if there is no wall in front the agent.
leftIsClear (): Returns True there is no wall on the agent
left.
right (): Returns True there is no wall on the agent's right.
markerssresent (): Returns True if there exist markers on the
current cell.
noMarkersPresent (): Returns True if there is no marker on the current cell.
There are some limitations for the Python program: do not define other functions besides run ()
not call other functions
do not define variables
do not use True, False, break, continue, return, ==, !=, elif, or, and
K.2.2 USER PROMPT
T'll provide you with the task name and description.
Task name: <<Task Name>>
Task map: <<Map Description>>
Task agent position: <<Initial Position>>
Task goal: <<Task Goal>>
Task return: <<Task Reward>>
1.
Generate simple and short Python program to tackle the task, avoid using comments.
K.3 DSL
K.3.1 SYSTEM PROMPT
You re currently navigating within a Karel environment, which is essentially a grid world. In this context, "world" is referred to as a "map." Within this map, there's s an entity known the "agent," capable of movement, changing direction, and placing markers on the map.
as well as picking
Additionally, there are obstacles called "walls" that impede the agent 's progress; whenever the agent encounters a wall, it turns around. Furthermore, there are pre-existing "markers" scattered throughout the map at the beginning, though the agent has the ability to both pickup and place these markers as needed.
Your objective is to generate the appropriate Karel dsl program based on a given task name and description. This Karel dal program will encompass actions enabling the agent to engage with the environment, alongside perceptions facilitating the agent's recognition of the envirnttttt dynamics.
40

---

Published as a conference paper at ICLR 2025
Here are the available actions for the agent:
move: Asks the agent to move forward one cell. The agent will
instead turn left twice if a wall is blocking its way.
turrneft: Asks the agent rotate 90 degrees counterclockwise,
turnRight: Asks the agent to rotate 90 degrees clockwise. pickMarker: Asks the agent pick up one marker from the current cell.
putMarker: Asks the agent put down one marker on the current cell.
Here are the available perceptions of the agent: frontIsclear: Returns True if there is no wall in front of the agent.
leftisClear: Returns True if there is no wall on the agent's left.
righttsClear: Returns True if there is wall on the agent's right.
markersPresent: Returns True if there exist markers on the current cell.
noMarkersPresent: Returns True if there is no marker on the current cell.
This is the production role of the domain-specific language of the Karel environment.
Program p : DEF run m m)
statement 8 : WHILE o( b c) w( 8 w) I IF c b c) i( s 1) IFELSE
c( c) i( s i) ELSE e e) REPEAT R=n E( r)
Condition b := h not c h
Number := 0, 1, 2, 4, 5, 6, 7,
10, 11, 12, 13, 14, 15,
16, 17, 18, 19
Perception
frontIsClear leftIsClear rightIsClear markersPresens noMarkersPresent
Action a == move turnLeft turnRight putMarker PickMarker
K.3.2 USER PROMPT
I'll provide you with the task name and description.
Task name: <<Task Name>>
Task map: <<Map Description>>
Task agent position: <<Initial Position>>
Task goal: <<Task Goal>>
Task return: <<Task Reward>>
1.
Generate simple and short Karel dsl program to tackle the task, avoid using comments.
K.4 REGENERATE
I'1l provide you with the task name, task description, and the programs you generated last time.
Task name: DOORKEY
Task map: The map is 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 marker placed randomly on the left chamber as a key, and another goal.
marker placed randomly on the right chamber
41

---

Published as a conference paper at ICLR 2025
Task agent position: The agent starts random cell the left chamber facing east.
Task goal: The goal of the agent is to pick up marker the left chamber, which opens a door connecting both chambers.
Allow the agent to reach and put marker on the goal marker, Task return: Picking up the first marker yields a 0.5 reward, and putting marker on the goal marker yields an additional 0.5.
These are the programs you generated last time, all of these programs cannot yield perfect performance.
Program 1:
def run () while noMarkersPresent ():
if frontIsClear()
move
else:
turnLeft ()
pickMarker
while noMarkersPresent() ():
if frontIsClear() m)
else:
turnLeft ()
if markersPresent ()
putMarker()
#4423 programs are 41
Program 25:
def run (): while noMarkersPresent O):
if ErontIsClear ():
m)ve
else:
turnLeft ()
pickMarker
for i in range (19)
if ErontIsClear() ()
move
else:
turnRight ()
1. Generate Python program that is not identical to any of the previous programs tackle the task, and avoid using comments
2. Convert the Python program to the Karel dsl program
K.5 REGENERATE WITH REWARD
I'll provide you with the task name, task description, and the programs rewards pairs sorted by their evaluation rewards from 32 task variants.
Task name: DOORKEY
Task map: The map is a 8x8 grid surrounded by walls that is vertically split into two chambers. The left chamber is 6x3
42

---

Published as a conference paper at ICLR 2025
grid and the right chamber is 6x2 grid. There is marker placed randomly on the left chamber as a key, and another marker placed randomly the right chamber
goal. Task agent position: The agent starts on random cell on the left chamber facing east.
Task goal: The goal of the agent is to pick a marker on the left chamber, which opens a door connecting both chambers. Allow the agent to reach and put marker on the goal marker. Task return: Picking up the first marker yields a 0.5 reward, and putting marker the goal marker yields an additional 0.5.
Program reward pairs sorted by their evaluation rewards:
Program 1:
def run (): while noMarkersPresent ():
if FrontIsClear
()ve
else:
turnLeft ()
if front :):
move
turnRight ()
pickMarker()
while noMarkersPresent ():
if frontIsClear
m)ve
else:
turnLeft ()
putMarker
reward:
0.5
###23 programs are t#
Program 25:
def run (): for i in range (19):
if markersPresent,
pickMarker
while not frontIsClear
turnleft
move
if frontIsClear ()
m)ve
if markersPresent ():
putMarker
reward: -0.5
1. Depending on this information, examine the program pattern that the highest score programs process, but the lowest score programs do not.
2. Generate 1 simple and short Python program according to the pattern tackle the task, avoid using comment.
3. Convert the Python program to the Karel dsl program.
43

---

Published as a conference paper at ICLR 2025
K.6 AGENT EXECUTION TRACE
I'1l provide you with the code you developed previously, with the goal of refining it. To guide your revision, you'll receive the specific task name and a description. Since there are 32 different versions of the task that share the same objective but differ by random seeds, I will identify the specific variant where the performance of the program is most lacking. Additionally, you'll get the initial state of the task, the code, and a detailed trajectory demonstrating how the code operates within this particular scenario. This trajectory will detail each action step-by and show a localized snapshot of the environment (a 3x3 area centered on the agent) during execution. Rewards received by the agent will also be shown during these steps.
Task name: DOORKEY
Task map: The map is 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 marker
placed randomly on the left chamber as a key, and another marker placed randomly on the right chamber as goal. Task agent position: The agent starts on random cell on the left chamber facing east.
Task goal: The goal of the agent is to pick a marker on the left chamber, which opens a door connecting both chambers. Allow the agent to reach and put marker on the goal marker. Task return: Picking up the first marker yields a 0.5 reward, and putting marker the goal marker yields an additional 0.5.
Initial state:
(a,1 0)
Wall (C, 1)
Wall (0, 2)
Wall 3)
Wall (0, 4) ; Wall (0, 5) i
Wall (0, 6)
Wall (0, 7)
(1, 0)
Empty (1, 1) Empty 2) ; Empty (1, 3) ;
Wall (1, 4) ; Empty (1, 5) Marker (1, 6, quantity=l)
Wall (1, 7)
Wall (2,
Empty (2, 1)
Empty (2, 2) ; Empty (2, 3)
Wall (2, 4) ;
Empty (2, 5)
Empt (2, 6)
Wall (2, 7)
Wall (3, 0)
Empty (3, 1)
Empty (3, 2) ; Empty (3, 3)
Wall (3, 4)
Empty (3, 5)
Empty (3, 6)
Wall 7)
Wall 0)
Empty (4, 1)
Agent (4, 2, direction= (0, 1))
Empty (4, 3) ; Wall (4, 4)
Empty (4, 5)
Empty (4, 6)
Wall (4, 7)
Wall (5, 0)
Empty (5, 1) Marker (5, 2, quantity-1)
Empty (5, 3)
Wall(S (5, 4) i
Empty 5) Empty (5, 6)
Wall (5,
7)
Wall (6, 0)
Empty (6, 1)
Empty (6, 2)
Empty (6, 3)
Wall (6, 4)
Empty (6, 5) Empty (6, 6) Wall (6,
Wall (7, 0)
W7ll 1) W7ll 2) Wall 3)
Wall (7, 4)
Wall (7, 5) Wall (7, 6) Mall (7,
Program:
def run ()
while noMarkersPresent ()
if frontIsClear ():
move()
else:
turnLeft ()
if front
44

---

Published as a conference paper at ICLR 2025
move ()
turnRight ()
pickMarker()
while noMarkersPresent O)
if frontIsclear ():
m)ve
else:
turnLeft ()
putMarker
The average reward on 32 task variants is: 0.5
Trajector::
Step 1:
Agent performs perception: noMarkersPresent, The result is True.
Partial state:
Empty (3, 1) Empty (3, 2) Empty (3, 3)
Empty (4, 1]
Agent (4, 2, direction (0, 1)) Empty (4, 3) Empty (5, 3) ;
Empty (5, 1)
Marker (5, 2, quantity=1)
Step 2:
Agent performs a perception: frontIsClear. The result is True.
Partial state:
Empty (3, 1)
Empty (3, 2) Empty(3, 3)
Empty (4, 1]
Agent (4, 2, rict (0, 1)) ; Empty (4, 3) ; Empty (5, 3) ;
Empty (5, 1) Marker 2, quantity=1)
Step 3:
Agent performs an action: move.
Partial state:
Empty (3, 2)
Empty (3, 3) Wall (3, 4)
Empty (4, 2) Agent (4, 3, rect (0, 1)) ; Wall (4, 4) ;
Marker (5, 2, quantity=1)
Empty (5, 3) Wall (5, 4) ;
###45 steps truncated.
Step 49:
Agent performs perception: frontIsClear. The result is False.
Partial state:
(1, 0) Empty (1, 1) Empty (1, 2)
(2,1 0)
Agent (2, 1, direction= (0, -11) } ;
Empty (2,
2)
Wall 0) Empty (3, 1) ; Empty (3, 2) ;
The total step number is 105, the latter ones are truncated.
The total reward is 0.0
1. Depending this information, please analyze the reason why the program failed to achieve 1.0 on this task variant and generate a new strategy to solve this task.
2. Generate simple and short Python program according to the new strategy to tackle the task, avoid using comment.
45

---

Published as a conference paper at ICLR 2025
3. Convert the Python program to the Karel dsl program.
K.7 AGENT AND PROGRAM EXECUTION TRACE.
I'11 provide you with the code you developed previously, with the goal of refining it. To guide your revision, you'll receive the specific task name and a description. Since there are 32 different versions of the task that share the but differ by random seeds, I will identify the specific variant where the performance of the program is most lacking, Additionally, you'll get the initial state of the task, the code, and a detailed trajectory demonstrating how the code operates within this particular scenario. This trajectory will detail each action step-by-step, indicate which section of your code is active, and show localized snapshot of the envmeot (a 3x3 area centered on the agent) during execution. Rewards received by the agent will also be shown during these steps.
objective
Task name: DOORKEY
Task map: 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 marker
placed randomly on the left chamber as a key, and another marker placed randomly on the right chamber as goal. Task agent position: The agent starts on random cell on the left chamber facing east.
Task goal: The goal of the agent is to pick up marker the left chamber, which opens a door connecting both chambers. Allow the agent to reach and put marker the goal marker. Task return: Picking up the first marker yields a 0.5 reward, and putting marker the goal marker yields additional 0.5.
Initial state:
Wall 0)
Wall(C, 1)
Wall (0, 2)
Wall 3) Wall (0,
Wall (0, 4) ;
Wall( (0, 5) ;
Wall (0, 6)
Wall (1, 0)
Empty (1, 1) Empty (1, 2) Empty (1, 3)
Wall (1, 4) ; Empty (1, 5) Marker (1, 6, quantity=1)
Wall (1, 7)
Wall (2, 0)
Empty (2, 1)
Empty (2, 2) ; Empty (2, 3)
Wall (2, 4) ; Empty (2, 5)
Empty (2, 6)
Wall (2, 7)
Wall (3, 0)
Empty (3, 1)
Empty (3, 2)
Empty (3, 3)
Wall (3, 4) ; Empty (3, 5)
Empty (3, 6)
Wall (3, 7)
(4, 0)
Empty (4, 1)
Agent (4, 2, direction= (0, 1))
Empty (4, 3) ; Wall (4, 4)
Empty (4, 5)
Empty (4, 6)
Wall (4, 7)
Wall (5,
Empty (5, 1) ;
Marker (5, 2, quantity=1) 15p 5) Empty (5, 6)
Empty (5, 3)
Wall (5, 4)
Wall (5, 7)
Wall (6, 0)
Empty (6, 1)
Empty (6, 2)
Empty (6, 3) ;
Wall (6, 4)
Empty (6, 5)
Empty (6, 6) Wall (6, 7)
Wall (7, 0)
(7, 1) Wall (7, 2) Wall(7, 3)
Wall (7, 4)
Wall (7, 5)
Wall (7, 6) Wall 7)
Program:
def run ():
while noMarkersPresent ():
if frontTsClear()
46

---

Published as a conference paper at ICLR 2025
move ()
else:
turnLeît ()
if frontIscCeer :):
move ()
turnRight ()
PickMarker
while noMarkersPresent ():
if ErontIsClear()
m)ve
else:
turnLeft ()
putMarker()
The average reward 32 task variants is:
0.5
Trajectory:
Step 1:
Program:
def r)n():
while noMarkersPresent ():
Currently executing this line
if ErontIsClear()
m
else:
turnLeft ()
if front
move ()
turnRight ()
PickMarker ()
while noMarkersPresent ():
if frontIsClear()
()
else: turnLeft ()
putMarker()
Agent performs perception:
noMarkersPresent. The result is True.
Partial state:
Empty (3, Empty (3, 2) Empty (3, 3) ;
Empty (4, 1) Agent (4, 2, direction= (0, 1)) ; Empty (4, 3) ; Marker (5, 2, quantity=l)
Empty (5,
Empty (5, 3) ;
Step 2:
Program:
def run(): while noMarkersPresent ():
if ErontIsClear Currently executing this line
()
e else:
turnLeft ()
if front
move ()
turnRight ()
pickMarker ()
while noMarkersPresent ():
47

---

Published as a conference paper at ICLR 2025
if FrontIsclear( ():
move ()
else:
turnLeft ()
putMarker()
Agent performs
perception: FrontIsClear. The result is True.
Partial state:
Empty 1) Empty (3, 2) Empty (3, 3) ;
Empty (4, 11
Agent (4, 2, direction= (0, 1)) Empty (4, 3) Marker (5, 2, quantity=1)
Empty (5, 1)
Empty (5, 3) 7
Step 3:
Program:
def run(): while noMarkersPresent ():
if frontIsClear()
m)ve # Currently executing this line
else:
turnLeft ()
if Isont ()
move
turnRight ()
pickMarker ()
while noMarkersPresent ():
if FrontIsClear
m)ve()
else: turnLeft ()
(utMarker
Agent performs an action: move.
Partial state:
Empty (3, 2) Empty (3, 3) Wall (3, 4) ;
Empty (4, 2) Agent (4, 3, direction= (0, 1)) Wall (4, 4) Wall (5, 4) ;
Marker 2, quantity=1)
Empty (5, 3) ;
##44 steps are truncated. ###
Step 49:
Program:
def run ():
while noMarkersPresent ():
if FrontIsClear Currently executing this line
m)
e else:
turnLeft ()
if IrontasClear ()
move ()
turnRight ()
pickMarker ()
while noMarkersPresent
if fronttsClear()
move
else: turnLeft ()
putMarker
48

---

Published as a conference paper at ICLR 2025
Agent performs perception: FrontIsclear. The result is False.
Partial state:
Wall 0) Empty (1, 1) Empty (1, 2) ;
W2,l 0)
Agent (2, 1, directions (0, -1)) ;
Empty (2,
2)
Wall (3, 0)
Empty (3, 1). Empty (3, 2)
total step number is 105, the latter ones are truncated.
The total reward is 0.0
1. Depending on this information, please analyze the reason why the program failed to achieve 1.0 this task variant and generate a new strategy to solve this task.
2. Generate simple and short Python program according to the new strategy to tackle the task, avoid using comment.
3. Convert the Python program the Karel dsl program.
49

---

Published as a conference paper at ICLR 2025
L MINIGRID ENVIRONMENT
Minigrid Snevalier-Boisveed et al., 2023) a grid-world environment designed for conducting research on reinforcement learning (Guan et al. 2022 Jelley al. 2023 Furelos- Blanco et al.) 2023). Unlike the Karel environment (Pattis) 1981) ) Minigrid has a richer set of objects, and each object comes with color. Besides Karel's actions, the Minigrid agent also "toggle" objects, like unlocking a door or opening a box. The environment has built-in tasks that range from simple navigation to complex multi-step reasoning.
To evaluate our proposed LLM-GS framework on the Minigrid environment, we designed and implemented domain-specifie language (DSL.), which contains more actions and object types than the Karel one. We will introduce the DSL in Appendix L.] the tasks in Appendix L.2 the result
in Appendix L.3 and the prompts in Appendix L.4
L.1 MINIGRID DSL
Here, we present the DSL we designed for the Minigrid environment. The actions are similar to the ones from Karel. The perceptions, on the other hand, are distinct from Karel. Specifically, the perception functions in our Minigrid DSL are parameterized, i.e., require input parameter such as an object, since there are multiple object types in the domain, unlike the case Karel. Thus, we implemented two novel perceptions: mront_object type( type ) and wott-oeeeccoooorrrr color ), which are completely different from the ones in Karel DSL. They check if the cell right front of the agent has certain type certain color object. We list the Python DSL converting rules in Table ( and the probabilities of the production rules in Table 10, The setting for the program mutation the same the one in Karel DSL.
Table 9: Python to DSL converting rules in Minigrid.
Python
DSL
def run():
DEF run m( s m)
while b:
WHILE b w(sw)
bf s
IFc(bc) i(
b: s else: s
IFELSE o( b c) i( s ELSE e(s)
for in range(n):
REPEAT R=n s())
not h
not c( c)
front is clear()
front is clear
front.bbject.typp(tpe)))
fyont h( type h)
front_chjectcoolorccloo)
front_object_color h( color h) is carrying object
carrying object()
forward()
forward left
left(
right(
right
pickup(
pickup
drop(
drop
toggle(
toggle
L.2 MINIGRID TASKS
We evaluate three tasks from the Minigrid environment: Lava Gap (Appendix L.2.1 Put Near (Ap- pendix L.2.2), and Red Blue Door (Appendix L.2.3). We include an example illustration of the three tasks in Figure 21 and introduce the details of each task in the following sections.
50

---

Published as a conference paper at ICLR 2025
Table 10: Probabilities of the production rules in Minigrid.
Category
Rule
Probability
Program P Statement S
Statement
While
0.15
Repeat
0.03
Concatenate
0.5
0.08
Ifelse
0.04
Action
0.2
Condition
Boolean
0.5
not
0.5
Action forward
0.5
left
0.15
right
0.15
pickup
0.08
drop toggle
0.08
0.04
Boolean front_is_clest
0.125
oront_object_type
0.5
front object color
0.25
is carrying object
0.125
Type t
lava door
0.25
0.25
ball
0,25
box
0.25
Color
blue
0.5
red
0.5
Number
i (0 sis 19)
0.05
(a) LAVAGAP
(b) PUTNEAR
(c) REDBLUEDOOR
Figure 21: Illustrations of the initial and final state of the task we chose for the Minigrid (Chevalier] Boisvert et al., 2023) evaluation. The position obstacles, objects, and the agent's 's position are randomly set according to the configurations of each task.
L.2.1 LAVAGAP
In the task LavaGap, the agent must pass through gap in vertical strip of lava and reach the goal. Stepping on the lava will terminate the episode. We set the reward function of LavaGap to give reward of when stepping lava and reward of 1.0 when reaching the goal.
51

---

Published as a conference paper at ICLR 2025
Purpose
Prompt Text
Task Name
LAVAGAP
Map Description
The map is a 6x6 grid surrounded by walls. There is a vertical strip of lava with a randomly selected gap in the middle of the map and goal square at the bottom right corner.
Initial Position
The agent starts at the top left corner of the map facing east.
Task Goal
The agent has reach the goal square the bottom right corner of the map without step on lava. Touching the lava terminates the episode.
Task Reward
If the agent reaches the goal, it will receive reward of 1. If the agent steps on lava, it will receive a reward of-1. -1.
L.2.2 PUTNEAR
In the task PutNear, the agent needs to pick up the move object and drop it next to the target object. We modified the task to fix the move object as a ball and the targer object as a box. Picking up the move object will get a reward of 0.5 and dropping it next to the larger object will receive the remaining 0.5. Picking up the wrong object will get a reward of -1.0.
Purpose
Prompt Text
Task Name
PUTNEAR
Map Description
The map is a 6x6 grid surrounded by walls. There are two objects, one is a ball and the other is box. The two objects are randomly placed on the map.
Initial Position
The agent starts at the top left corner of the map facing east.
Task Goal
The agent has to first locate and pick up the ball. Next, it needs to find the box and drop the ball either to the right left of it. Picking up the wrong object will terminate the episode.
Task Reward
If the agent picks up the ball, it will receive a reward of 0.5. If the agent drops the ball the right or the left of the box, it will receive reward of I. If the agent picks up the wrong object, it will receive reward of -1.
L.2.3 REDBLURDDOR
In the task RedBlueDoor, the agent must first open the red door and then the blue one. Opening the red door first will get reward of O.5, followed by additional 0.5 for opening the blue door afterward. Opening the blue door before the red one will get a reward of -100.
Purpose
Prompt Text
Task Name
REDBLUEDOOR
Map Description
The map is a 6x12 grid surrounded by walls that are vertically split into three chambers. The left chamber is 4x2 grid, the middle chamber is 4x4 grid and the right chamber is a 4x2 grid. On the wall between the left and middle chamber, there is randomly placed red door. On the wall between the middle and right chamber, there is a randomly placed blue door.
Initial Position
The agent starts at a random position with a random direction in the middle chamber.
Task Goal
The agent has to first find and open the red door, then find and open the blue door. Opening the blue door first will terminate the episode.
Task Reward
If the agent opens the red door first, it will receive reward of 0.5. If the agent opens the blue door after opening the red door, it will receive a reward of 0.5. If the agent opens the blue door first, will receive reward of -1.
52

---

Published as a conference paper at ICLR 2025
L.3 MINIGRID DOMAIN
L.3.1 EVALUATION SETUP
We evaluate our proposed LLM-GS framework using the Minigrid tasks LAVAGAP, PUTNEAR, and REDBLUEDOOR. More task details can be found Appendix [.2] LLM-GS is compared with the best-performing baseline HC. The evaluation metric is the same the one mentioned in Section 5.1 except for C with temperature= 1.0, top-p=1.00 1.0) our LLM module to generate the initial search population. The scheduler of our proposed Scheduled HC starts from Kstart 32 to Kend = 2048. We evaluate our LLM-GS and HC with 8 random seeds.
and N = 10 For the setup, we use GPT-4o (gpt-40-2024-08-
L.3.2 EXPERIMENTAL RESULTS
Figure 22
presents the experimental result, indicating that our proposed LLM-GS is more sample- efficient compared HC all the tasks.
LLM-GS (Ours)
Average Return
0.8
Average Return
0.8
Average Return
0.8
HC
0.6
0.6
0.6
0.0
0.0
0.0
-0.7
-0.
-0.7
10a
10'
of Evaluated Program
# of Evaluated Program
# of Evaluated Program
(a) LAVAGAP
(b) PUTNEAR
(c) REDBLUEDOOR
Figure 22: Efficiency in Minigrid tasks. We compare our proposed LLM-GS framework against best-performing baseline HC in three Minigrid tasks LAVAGAP, PUTNEAR, and REDBLUEDOOR. The results show that LLM-GS is more sample-efficient than HC.
L.4 MINIGRID PROMPTS
L.4.1 THE SYSTEM PROMPT
In the Minigrid environment, you navigate grid-based world referred to as a "map." Within this map, an entity called the "agent" can move, change direction, and interact with objects. The map also includes obstacles like "walls, which block the agent s movement; stationary. Another obstacle is "lava," which ends the episode if the agent steps on it. Additionally, there are "doors" that block the agent until opened using the "toggle" action.
the agent encounters a wall, it remains
At the start of each episode, various objects are scattered across the map, and the agent can interact with them as needed. These objects fall into four categories: "lava, "door, "ball and "box." Except for lava, objects can appear in two colors: "red" and "blue."
Lava: Ends the episode when stepped on.
Door: Blocks the agent's path until opened using the "toggle" action.
Ball: Can be picked up and dropped.
Box: Can be picked up and dropped.
Your objective is to generate the appropriate Python program based given task and description. This Python program
53

---

Published as a conference paper at ICLR 2025
will encompass actions enabling the agent to engage with the environment, alongside perceptions facilitating the agent's recognition of the environment's 's dynamics.
Here are the available actions for the agent: forward Asks the agent to move forward one cell. The agent will stay still if a wall or an unopened door is blocking its way. The episode will be terminated if the agent steps on lava. (): Asks the agent to rotate 90 degrees counterclockwise. right ():: Asks the agent to rotate 90 degrees clockwise.
pickup (): Asks the agent to pick up an object right in front of the current cell. The agent can only carry one object at time.
drop(): (): Asks the agent to drop the object it is carrying right in front of the current cell. The agent can only drop the object if it is carrying
and there is object in the cell.
toggle Asks the agent to change the state of a door directly in front of its current position, The agent can this action to open or close the door inmediately ahead.
Here are the available perceptions of the agent: front contt_ssclearr (): Returns True if there is no wall and an unopened
door right in front of the agent. It can only check wall and unopened door, so if there is lava right in front of the agent it will return True.
pooott_objctttyppe (type: Literal ("lava", "door", "ball", "box"]): Returns True if there is an object of the specified type right in front of the agent. The type can be and only can be "lava " "door", "ball", Front_object_color (color: Literal
"box".
"blue"l) Returns True if the specified color right frent of
there is an object the agent. The color can be and only can be "red" or "blue". carryinggoojectt (): Returns True if the agent is carrying an object.
There are some limitations to the Python program:
do not define other functions besides run()
do not call other functions
do not define variables True, False, break, continue, return, ==, !=, elif,
do not or, and
Python to Minigrid dsl conversion
1. "def ()n(): s" to "DEF run ml s m)"
2. "while b: s" to "WHILE of b c) wi s w)"
3. "if
"IF e( C) if i)
4. "if b: else: s" to "IFELSE c b c) i i) ELSE e e)
5. "for
range s" to "REPEAT R=n r( S r)" 6. "not h" to "not c( h ")
7. "front_is_cleaz(0
to (Eront_is_cleat
8. "firot_objeect_tyee" (type) " to "front "front_object_tuue object_typep type h type h)"
9. "Eraat_abjeet_ccoorrcdlloo (color) to "front_object_col h( color h)
10. "is_carryynngoojecct() to "is_carrying_objett
11. "forward to "forward"
12. "left()" to "left"
13. "right()* to "right"
"pickup" 15. "drop()" to "drop"
14. "pickup()
16. "toggle() to "toggle"
54

---

Published as a conference paper at ICLR 2025
L.4.2 THE USER PROMPT OF THE TASK LAVAGAP
I'll provide you with the task name and description.
Task name: LAVAGAP
Task map: The map is a 6x6 grid surrounded by walls. There is a vertical strip of lava with a randomly selected gap in the middle of the map and goal square at the bottom right corner
Task agent position: The agent starts at the top left corner of the map facing east.
Task goal: The agent has reach the goal square the bottom right corner of the map without step on lava. Touching the lava terminates the episode.
Task return: If the agent reaches the goal, it will receive a reward 1. If the agent steps on lava, it will receive a reward of -1.
1. Generate simple and short Python program to tackle the task, avoid using comments. Convert the Python program to the Minigrid dsl program.
2.
L.4.3 THE SAMPLE RESPONSE OF LLM IN THE TASK LAVAGAP
python
def ():
while not front_object_tyee (elype("lae ("lava")
forward
left
forward
right
while front_is_cil _lear ():
forward
right
forward
()ft()
while front_is_clear() ():
forward
Minigrid DSL program:
DEF run ml
WHILE c not el front_object_type h "lava" h) forward
w(
w)
left
forward
right
WHILE c front_is_cee cler c) w
forward
w)
right
forward
left
WHILE o front_is clec c) w
forward
w)
m)
55

---

Published as a conference paper at ICLR 2025
M LIMITATION
Adapting to more complex environments beyond Karel. We believe developing more realistic and complex programmatic RL environments is promising future direction. However, to make new environment suitable for programmatic reinforcement learning (PRL). must carefully craft a domain-specific language (DSL) that defines action and perception primitives tailored to the environment's constraints. For example, in the Space Invaders Atari environment, actions might be defined as Left, Right, and F Fire, while perceptions could include A.l Allienine InFroon.. Only once such DSL is in place can our framework
Bul let InF ront, and 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- outting-edge hardware like GPUs or TPUs.
Necessity of domain experts. We need 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 L.M when introducing it to new environment. That said, adopting our framework to 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.
56


Reviews:
[{"review_id": "5V58qJFKAp", "reviewer": "Reviewer_st6i", "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.", "questions": "Please see above for specific questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Update: Authors addressed my concerns with many additional experiments. I increased my score accordingly.\n\n1. The paper proposes LLM-based initialization for heuristic search methods. This is applicable to broader range of domains.\n\n2. Experimental results indicate sample efficiency.", "weaknesses": "My main concerns are lack of realistic domains, novelty of the proposed idea, and significance of the experimental comparison.\n\n1. 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?\n\n2. 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?\n\n3. Related to (2), HC learning curve is steeper than yours. Can you explain why?\n\n4. 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?\n\n5. What is task variance? Is it random initialization in environment state or policy pool?\n\n6. What happens if you initialize other heuristics with LLM-based programs? Do they compare favorably compared to your Scheduling-HC?\n\n7. In line 425, it should be 500k.", "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": "oVL64WjO9g", "reviewer": "Reviewer_C8r6", "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.\nThe 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.", "questions": "I have two main points relating to the weaknesses mentioned above, which I would like to see addressed before possibly raising my score:\n- 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.\n- 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? \n\nMore but less pressing questions:\n- 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?\n- 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.\n- 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.\n- Which initialisation do the authors use for the ablation study in figure 6? To they use LLM-generated programs or randomly generated ones?\n - 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?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 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.", "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.", "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": "h3gdivdvbU", "reviewer": "Reviewer_CapU", "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.", "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?\n* Are the program embeddings used for latent space search generated by the LLM?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "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.\n* They demonstrate the superior performance of LLM-GS compared to several search baselines, instilling confidence in its effectiveness, particularly in the Karel domain.\n* The ablation studies are well-structured and thorough, effectively investigating each component to clarify the sources of performance improvements.\n* The authors address potential concerns regarding LLM memorization and data leakage, which adds to the credibility of their results.\n* 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.", "weaknesses": "I have two main concerns with the paper that prevent me from giving it a higher score:\n* 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.**\n* 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.", "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)