Research map / Large language models / Agents, code and math
Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LLM-GS, which prompts GPT-4 to write Python programs that are converted to Karel DSL, then refines them with Scheduled Hill Climbing to cut the program-environment interactions needed for programmatic RL.
Problem
Programmatic reinforcement learning (PRL) policies in DSLs such as Karel need tens of millions of program-environment interactions with search methods, which is too sample-inefficient for practical use.
Approach
Use an LLM (GPT-4) with domain- and task-aware prompts to generate Python programs that are converted into DSL programs (Pythonic-DSL strategy), then seed a hill-climbing search whose neighborhood size is scheduled from small to large (Scheduled HC).
Key results
- On the Karel set LLM-GS completely solves the tasks with better sample efficiency than HC, LEAPS, HPRL, and CEBS.
- On DoorKey, LLM-GS converges within about 500K program evaluations while baselines do not converge at 1M.
- Pythonic-DSL achieves the highest acceptance rate on 9 of 10 tasks compared with direct Python or DSL generation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Generate Python programs and convert them to DSL instead of directly generating Python or DSL (ablation) | LLM-GS program generation · Karel tasks | acceptance rate | Helped |
| Generate Python programs and convert them to DSL instead of directly generating Python or DSL (ablation) | LLM-GS program generation · Karel tasks | best return | Mixed |
| Use Scheduled Hill Climbing instead of fixed-neighborhood search (ablation) | LLM-initialized program search · DoorKey and CleanHouse | sample efficiency | Helped |
| Initialize Scheduled Hill Climbing with LLM-generated programs instead of randomly sampled programs (ablation) | Scheduled Hill Climbing · DoorKey and CleanHouse | sample efficiency | Helped |
| Continue LLM program revision beyond the first two rounds (ablation) | LLM program revision · DoorKey | episodic return | No clear effect |
| Use LLM-GS instead of Hill Climbing | Programmatic RL · Karel tasks | sample efficiency | Helped |
| Use LLM-GS instead of Hill Climbing | Programmatic RL · Novel Karel tasks | sample efficiency | Helped |
| Adapt LLM-GS prompts and DSL for Minigrid | LLM-GS · Minigrid tasks | sample efficiency | Helped |
Surprising findings
- Directly regenerating DSL programs with LLM feedback (revision with reward or traces) saturates within about two rounds, so LLM revision alone is insufficient.
- Seeder shows lower acceptance for Pythonic-DSL (74.74%) than direct DSL generation (88.28%).
Limitations
- Approach is suited only to tasks whose solutions can be described in language; hard to extend to low-level control such as motor torque control.
- Pythonic-DSL restricts Python functionality, so the framework is tied to the DSL design.
- Relies on closed-source GPT-4 API, and the DSL prompt leaks some structure.
Experimental setup
Datasets: Karel tasks Karel-Hard tasks Minigrid LavaGap Minigrid PutNear Minigrid RedBlueDoor
Benchmarks: Karel Karel-Hard PathFollow WallAvoider Minigrid LavaGap Minigrid PutNear
Metrics: average episodic return vs. number of programs evaluated acceptance rate best return
Baselines: LEAPS HPRL CEBS Hill Climbing CEM
Builds on: hill climbing LEAPS CEBS
Closest papers by meaning
- Prompted Policy Search: Reinforcement Learning through Linguistic and Numerical Reasoning in LLMs (NeurIPS 2025 · similarity 0.90)
- $\mathcal{B}$-Coder: Value-Based Deep Reinforcement Learning for Program Synthesis (ICLR 2024 · similarity 0.89)
- LLM-Explorer: A Plug-in Reinforcement Learning Policy Exploration Enhancement Driven by Large Language Models (NeurIPS 2025 · similarity 0.89)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.88)
- RLEF: Grounding Code LLMs in Execution Feedback with Reinforcement Learning (ICML 2025 · similarity 0.88)
- Efficient Reinforcement Learning with Large Language Model Priors (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.