# Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search

arXiv: https://arxiv.org/abs/2405.16450 · HTML: https://mlsanity.com/paper/2405.16450/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 96 references that are in the map.
- First posted on arXiv 26 May 2024.

## Builds on (most cited first, 30 of 49)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [Galactica: A Large Language Model for Science](https://mlsanity.com/paper/2211.09085/) (2022)
- [Model-Based Reinforcement Learning for Atari](https://mlsanity.com/paper/1903.00374/) (2019)
- [A Systematic Evaluation of Large Language Models of Code](https://mlsanity.com/paper/2202.13169/) (2022)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [Quantifying Generalization in Reinforcement Learning](https://mlsanity.com/paper/1812.02341/) (2018)
- [Is Self-Repair a Silver Bullet for Code Generation?](https://mlsanity.com/paper/2306.09896/) (2023)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [Take a Step Back: Evoking Reasoning via Abstraction in Large Language Models](https://mlsanity.com/paper/2310.06117/) (2023)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [NL2Bash: A Corpus and Semantic Parser for Natural Language Interface to the Linux Operating System](https://mlsanity.com/paper/1802.08979/) (2018)
- [Explainability in Deep Reinforcement Learning](https://mlsanity.com/paper/2008.06693/) (2020)
- [Neuro-Symbolic Program Synthesis](https://mlsanity.com/paper/1611.01855/) (2016)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)
- [Neural Logic Reinforcement Learning](https://mlsanity.com/paper/1904.10729/) (2019)

## Built on by (most cited first, 13 of 13)

- [Reward Is Enough: LLMs Are In-Context Reinforcement Learners](https://mlsanity.com/paper/2506.06303/) (2025)
- [A Technical Survey of Reinforcement Learning Techniques for Large Language Models](https://mlsanity.com/paper/2507.04136/) (2025)
- [Mitigating Forgetting in LLM Fine-Tuning via Low-Perplexity Token Learning](https://mlsanity.com/paper/2501.14315/) (2025)
- [BILLY: Steering Large Language Models via Merging Persona Vectors for Creative Generation](https://mlsanity.com/paper/2510.10157/) (2025)
- [Multimodal LLM-assisted Evolutionary Search for Programmatic Control Policies](https://mlsanity.com/paper/2508.05433/) (2025)
- [From Code to Play: Benchmarking Program Search for Games Using Large Language Models](https://mlsanity.com/paper/2412.04057/) (2024)
- [Janus: An Algorithm-Evaluator Co-Evolution Framework for LLM-Driven Discovery under Expensive Evaluation Budgets](https://mlsanity.com/paper/2608.08189/) (2026)
- [REFLEX: Reflective Evolution from LLM Experience](https://mlsanity.com/paper/2606.16496/) (2026)
- [PolicyEvolve: Evolving Programmatic Policies by LLMs for multi-player games via Population-Based Training](https://mlsanity.com/paper/2509.06053/) (2025)
- [Policy-Conditioned Policies for Multi-Agent Task Solving](https://mlsanity.com/paper/2512.21024/) (2025)
- [DiPRL: Learning Discrete Programmatic Policies via Architecture Entropy Regularization](https://mlsanity.com/paper/2605.18508/) (2026)
- [Language-Critique Imitation Learning from Suboptimal Demonstrations](https://mlsanity.com/paper/2607.01225/) (2026)
- [Synthesizing Reactive Character Behaviors for Continuous Games via Programmatic Policy Search](https://mlsanity.com/paper/2609.24025/) (2026)

## Abstract (arXiv)

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.