Learning to Synthesize Programs as Interpretable and Generalizable Policies

Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, Joseph J Lim

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.

The two-stage LEAPS framework: (a) Learning a continuous program embedding space, and (b) searching this space using the Cross Entropy Method.

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.

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 Karel the Robot environment, illustrating a gridworld task (e.g., StairClimber) where the agent must navigate and interact with its surroundings.

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

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. Website at https://clvrai.com/leaps.
BibTeX
@inproceedings{trivedi2021learning,
  author = {Dweep Trivedi and Jesse Zhang and Shao-Hua Sun and Joseph J Lim},
  title = {{Learning to Synthesize Programs as Interpretable and Generalizable Policies}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=wP9twkexC3V},
}
Figure