Deep Reinforcement Learning (DRL) has achieved incredible feats across various domains, but it continues to struggle with two major "Achilles' heels": interpretability and generalization. Neural network policies act as black boxes; when an agent fails, it is nearly impossible to inspect the weights and understand why. Furthermore, a policy trained on a $10\times10$ grid often fails completely when moved to a $20\times20$ grid because it learns specific spatial mappings rather than logical, scale-invariant rules.
Programmatic policies—representing agent behavior as readable code—solve these issues by being inherently structured and interpretable. However, writing code is a discrete, combinatorial nightmare for optimization. Previous attempts to search for programs usually required expert demonstrations or rigid templates.
To address this, researchers introduce LEAPS (Learning Embeddings for lAtent Program Synthesis), a framework that synthesizes complex, loopy programs using only sparse reinforcement learning rewards, without needing human demonstrations.
Methodology: The LEAPS Framework
The core innovation of LEAPS is transforming the discrete problem of writing code into a continuous optimization problem. The authors achieve this through a two-stage framework.
1. Learning a Program Embedding Space
Instead of searching through discrete code tokens (like if, while, move), LEAPS first trains a Variational Autoencoder (VAE) on a dataset of 50,000 randomly generated programs. Crucially, the VAE is not just trained to reconstruct the text of the code. It utilizes three distinct losses to ensure the latent space captures actual agent behavior:
- Program Reconstruction ($L^P$): A standard VAE loss to learn valid syntax.
- Program Behavior Reconstruction ($L^R$): Uses the REINFORCE algorithm to ensure the reconstructed program behaves identically to the original in the environment.
- Latent Behavior Reconstruction ($L^L$): A supervised loss where a neural "executor" attempts to predict the actions of a program directly from its latent embedding.
This creates a "smooth" latent space where nearby points represent programs that act similarly, making the space highly searchable.
2. Latent Program Search
When faced with a new task, the model does not write code token-by-token. Instead, it uses the Cross Entropy Method (CEM)—a gradient-free optimization technique—to search the continuous latent space. It samples embeddings, decodes them into readable programs, tests them in the environment, and iteratively narrows the search toward regions yielding the highest rewards.
Evaluation Environment
The researchers evaluated LEAPS in the Karel the Robot domain, a classic educational programming environment consisting of a gridworld where an agent can move, turn, and interact with markers.
The framework was tested on six challenging benchmarks: StairClimber, FourCorner, TopOff, Maze, CleanHouse, and Harvester. Because the Domain Specific Language (DSL) supports while and repeat blocks, the resulting policies can be highly expressive and compact.
Key Results and Insights
- Superior Performance: LEAPS outperformed standard DRL (PPO/SAC) and other program synthesis baselines on almost all tasks. For instance, in the TopOff task, LEAPS achieved a reward of 0.81, while the best DRL baseline only reached 0.63.
- Zero-Shot Generalization: Because the output is a logical program (e.g.,
while(frontIsClear): move()), it is invariant to the size of the environment. When tested on massive $100\times100$ grids, LEAPS maintained a 1.00 success rate on tasks like StairClimber and Maze, whereas DRL policies catastrophically dropped to a 0.00 success rate. - Human-in-the-Loop Debugging: Since the output is human-readable code, humans can easily intervene. In a user study, non-experts were able to take suboptimal programs synthesized by LEAPS and improve their performance by 125% with just a few manual edits—a feat impossible with opaque neural network weights.
Limitations and Future Work
While LEAPS represents a significant step forward, it relies on a predefined Domain Specific Language (DSL) and assumes the agent already has access to high-level perceptions (like frontIsClear). In real-world robotics, extracting these symbolic states from raw pixels remains a separate, difficult challenge. Additionally, if the initial dataset of random programs lacks behaviors remotely related to a new task, the embedding space may struggle to represent the required solution. Future work may explore goal-conditioned program generators to speed up the CEM search process and reduce reliance on the initial random dataset.
Summary updated