Abstract
Recently, deep reinforcement learning (DRL) methods have achieved impressive performance on tasks in a variety of domains. However, neural network policies produced with DRL methods are not human-interpretable and often have difficulty generalizing to novel scenarios. To address these issues, prior works explore learning programmatic policies that are more interpretable and structured for generalization. Yet, these works either employ limited policy representations (e.g. decision trees, state machines, or predefined program templates) or require stronger supervision (e.g. input/output state pairs or expert demonstrations). We present a framework that instead learns to synthesize a program, which details the procedure to solve a task in a flexible and expressive manner, solely from reward signals. To alleviate the difficulty of learning to compose programs to induce the desired agent behavior from scratch, we propose to first learn a program embedding space that continuously parameterizes diverse behaviors in an unsupervised manner and then search over the learned program embedding space to yield a program that maximizes the return for a given task. Experimental results demonstrate that the proposed framework not only learns to reliably synthesize task-solving programs but also outperforms DRL and program synthesis baselines while producing interpretable and more generalizable policies. We also justify the necessity of the proposed two-stage learning scheme as well as analyze various methods for learning the program embedding.
Introduction
Deep Reinforcement Learning (DRL) has achieved remarkable success, but it suffers from two major "black box" problems: interpretability and generalization. Neural network policies are nearly impossible for humans to read or debug, and they often overfit to specific environment configurations. For instance, a neural network trained to navigate an 8x8 grid often fails completely when moved to a 100x100 grid because its spatial understanding is tied to the training dimensions.
Programmatic policies—representing a policy as code—address these issues because code is inherently structured and size-invariant. A while loop works regardless of grid size. However, searching for the right program in a discrete, symbolic space is extremely challenging. Prior methods either required expert demonstrations or used limited templates. We propose LEAPS (Learning Embeddings for lAtent Program Synthesis), which turns the discrete program search problem into a continuous optimization problem.
Methodology
The LEAPS framework simplifies program synthesis by splitting it into two stages: learning a behaviorally-smooth embedding space and then searching that space for a specific task.
Stage 1: Learning the Program Embedding Space
Instead of searching through raw code, LEAPS learns a continuous latent embedding space where similar programs are located near each other. A Variational Autoencoder (VAE) is trained on 50,000 randomly generated programs. A major insight is that syntactically similar programs can behave very differently. To ensure the space is behaviorally smooth (organizing programs by semantics rather than just syntax), three distinct losses are used:
- Program Reconstruction ($L^P$): Standard VAE loss to ensure the model can decode a latent vector back into valid code.
- Program Behavior Reconstruction ($L^R$): Uses REINFORCE to ensure the reconstructed program behaves like the original.
- Latent Behavior Reconstruction ($L^L$): A supervised loss where a neural "executor" predicts the actions of a program directly from its latent vector.
Stage 2: Latent Program Search
When given a new task, LEAPS uses the Cross Entropy Method (CEM)—a gradient-free search algorithm—to navigate the learned embedding space. It samples candidate programs, tests them in the environment, and iteratively narrows the search toward the region of the "map" that yields the highest reward.
Experimental Evaluation
We evaluated LEAPS in the Karel the Robot domain across several tasks like StairClimber, Maze, and CleanHouse.
Key Results
- Zero-Shot Generalization: On the
StairClimberandMazetasks, LEAPS achieved a 1.0 reward on 100x100 grids after being searched on much smaller grids. In contrast, standard DRL baselines dropped to 0.0 reward on the larger grids. - Search Efficiency: LEAPS outperformed naive program synthesis and other programmatic baselines like VIPER, especially on tasks requiring repetitive behaviors (loops).
- Interpretability: In a user study, participants improved suboptimal LEAPS-generated programs by an average of 125% with just five statement edits, demonstrating a level of contestability that neural policies cannot provide.
Conclusion
LEAPS demonstrates that learning a behaviorally-aware embedding space is a powerful strategy for program synthesis. By organizing programs based on their execution traces rather than just syntax, the framework enables efficient search for interpretable, generalizable policies using only reward signals. Future work includes expanding to more complex DSLs and integrating high-level perception modules for real-world robotics.
Summary updated