# Searching for Programmatic Policies in Semantic Spaces

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

## Key facts

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

## Builds on (most cited first, 13 of 13)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [babble: Learning Better Abstractions with E-Graphs and Anti-Unification](https://mlsanity.com/paper/2212.04596/) (2022)
- [Hierarchical Programmatic Reinforcement Learning via Learning to Compose Programs](https://mlsanity.com/paper/2301.12950/) (2023)
- [What can we Learn Even From the Weakest? Learning Sketches for Programmatic Strategies](https://mlsanity.com/paper/2203.11912/) (2022)
- [Choosing Well Your Opponents: How to Guide the Synthesis of Programmatic Strategies](https://mlsanity.com/paper/2307.04893/) (2023)
- [Combinatorial Multi-armed Bandits for Real-Time Strategy Games](https://mlsanity.com/paper/1710.04805/) (2017)
- [Combining Strategic Learning and Tactical Search in Real-Time Strategy Games](https://mlsanity.com/paper/1709.03480/) (2017)

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

- [Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search](https://mlsanity.com/paper/2405.16450/) (2024)
- [From Code to Play: Benchmarking Program Search for Games Using Large Language Models](https://mlsanity.com/paper/2412.04057/) (2024)
- [InnateCoder: Learning Programmatic Options with Foundation Models](https://mlsanity.com/paper/2505.12508/) (2025)
- [Scheduling That Speaks: An Interpretable Programmatic Reinforcement Learning Framework](https://mlsanity.com/paper/2605.18454/) (2026)
- [DiPRL: Learning Discrete Programmatic Policies via Architecture Entropy Regularization](https://mlsanity.com/paper/2605.18508/) (2026)

## Abstract (arXiv)

Syntax-guided synthesis is commonly used to generate programs encoding policies. In this approach, the set of programs, that can be written in a domain-specific language defines the search space, and an algorithm searches within this space for programs that encode strong policies. In this paper, we propose an alternative method for synthesizing programmatic policies, where we search within an approximation of the language's semantic space. We hypothesized that searching in semantic spaces is more sample-efficient compared to syntax-based spaces. Our rationale is that the search is more efficient if the algorithm evaluates different agent behaviors as it searches through the space, a feature often missing in syntax-based spaces. This is because small changes in the syntax of a program often do not result in different agent behaviors. We define semantic spaces by learning a library of programs that present different agent behaviors. Then, we approximate the semantic space by defining a neighborhood function for local search algorithms, where we replace parts of the current candidate program with programs from the library. We evaluated our hypothesis in a real-time strategy game called MicroRTS. Empirical results support our hypothesis that searching in semantic spaces can be more sample-efficient than searching in syntax-based spaces.