Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces

Tales Henrique Carvalho, Kenneth Tjhia, Levi H. S. Lelis

Abstract

Recent works have introduced LEAPS and HPRL, systems that learn latent spaces of domain-specific languages, which are used to define programmatic policies for partially observable Markov decision processes (POMDPs). These systems induce a latent space while optimizing losses such as the behavior loss, which aim to achieve locality in program behavior, meaning that vectors close in the latent space should correspond to similarly behaving programs. In this paper, we show that the programmatic space, induced by the domain-specific language and requiring no training, presents values for the behavior loss similar to those observed in latent spaces presented in previous work. Moreover, algorithms searching in the programmatic space significantly outperform those in LEAPS and HPRL. To explain our results, we measured the "friendliness" of the two spaces to local search algorithms. We discovered that algorithms are more likely to stop at local maxima when searching in the latent space than when searching in the programmatic space. This implies that the optimization topology of the programmatic space, induced by the reward function in conjunction with the neighborhood function, is more conducive to search than that of the latent space. This result provides an explanation for the superior performance in the programmatic space.

Introduction

In reinforcement learning (RL), programmatic policies—policies expressed in a human-readable domain-specific language (DSL)—offer significant advantages over traditional neural network policies. They are interpretable, modular, and demonstrate robust generalization to novel scenarios. However, the discrete and non-differentiable nature of program space makes it notoriously difficult to navigate.

To address this, recent research has pivoted toward learning continuous "latent spaces" using Variational Autoencoders (VAEs). Systems like LEAPS and HPRL map discrete programs into smooth vector embeddings, theoretically allowing search algorithms to operate in a more manageable environment. This paper critically evaluates this trend, asking whether these learned latent spaces actually provide a superior optimization landscape compared to the original, raw programmatic space.

Methodology

Search Environments

We compared two distinct approaches to policy search:

  1. Programmatic Space: This approach involves searching directly on the Abstract Syntax Trees (ASTs) of the DSL. We utilized a simple Hill Climbing (HC) algorithm that generates neighbors through small, stochastic mutations of the program code.
  2. Latent Space: This approach utilizes the embedding space learned by a VAE. We evaluated existing methods like the Cross-Entropy Method (CEM) and introduced a more robust variant, Cross-Entropy Beam Search (CEBS), to ensure a fair comparison.

Measuring "Friendliness"

To quantify the quality of these search spaces, we introduced the concept of "friendliness." This metric measures the probability that a local search algorithm, starting from a random initialization, will converge to a solution of a specific quality. We also analyzed behavioral similarity to determine if proximity in the search space (either latent or programmatic) consistently results in similar agent behavior in the environment.

Experimental Setup

Our evaluation focused on the KAREL THE ROBOT domain, a standard benchmark for program synthesis. We tested across three variations:

  • Standard KAREL: Tasks such as Maze, Harvester, and StairClimber.
  • KAREL-HARD: Complex tasks requiring internal logic and state management, including DoorKey, Seeder, and Snake.
  • CRASHABLE KAREL: A novel variant where invalid actions (e.g., hitting a wall) result in immediate episode termination, testing the robustness of the policies.

Key Findings

The Topology Trap

Our most significant discovery is that latent spaces are often less "friendly" than the raw DSL. While VAEs are designed to create smooth embeddings, the encoding and decoding process introduces artificial local maxima. Search algorithms in latent space are significantly more likely to become trapped in these sub-optimal regions. In contrast, the programmatic space, defined by the reward function and simple mutation neighborhoods, possesses a topology more conducive to reaching global optima.

Locality and Generalization

While latent spaces aim to achieve "locality" (where nearby vectors represent similar behaviors), we found that the raw programmatic space naturally exhibits similar levels of behavioral locality without the need for expensive neural network training. Furthermore, latent spaces tend to overfit the specific environment dynamics they were trained on. In the "Crashable Karel" environment, the environment-agnostic nature of the raw DSL allowed it to generalize far more effectively than the latent embeddings.

Computational Efficiency

Searching in the programmatic space is substantially more efficient. Generating a neighbor in the DSL is approximately 10 to 14 times faster than in the latent space, as it avoids the heavy computational overhead of running a neural decoder for every search step.

Results

Simple Hill Climbing in the programmatic space outperformed state-of-the-art latent space methods (LEAPS and HPRL) across every task in both the KAREL and KAREL-HARD benchmarks. For example, in the DoorKey task, latent methods consistently stalled at a reward of 0.5, failing to reach the goal after opening the door. Programmatic HC achieved a mean reward of 0.84, successfully solving the task. Our friendliness analysis confirmed these results; in the OneStroke task, the programmatic space was nearly twice as likely to lead the search to a high-quality solution compared to the latent space.

Conclusion

Our results suggest that the current move toward latent space embeddings for programmatic policies may be premature. The raw programmatic space offers a more effective optimization topology, better generalization, and higher computational efficiency. Future research should focus on whether these findings hold for more complex, low-level languages and explore whether new training objectives can produce latent spaces that truly surpass the inherent advantages of the source code.

Summary updated

Abstract

Recent works have introduced LEAPS and HPRL, systems that learn latent spaces of domain-specific languages, which are used to define programmatic policies for partially observable Markov decision processes (POMDPs). These systems induce a latent space while optimizing losses such as the behavior loss, which aim to achieve locality in program behavior, meaning that vectors close in the latent space should correspond to similarly behaving programs. In this paper, we show that the programmatic space, induced by the domain-specific language and requiring no training, presents values for the behavior loss similar to those observed in latent spaces presented in previous work. Moreover, algorithms searching in the programmatic space significantly outperform those in LEAPS and HPRL. To explain our results, we measured the "friendliness" of the two spaces to local search algorithms. We discovered that algorithms are more likely to stop at local maxima when searching in the latent space than when searching in the programmatic space. This implies that the optimization topology of the programmatic space, induced by the reward function in conjunction with the neighborhood function, is more conducive to search than that of the latent space. This result provides an explanation for the superior performance in the programmatic space.
BibTeX
@inproceedings{carvalho2024reclaiming,
  author = {Tales Henrique Carvalho and Kenneth Tjhia and Levi H. S. Lelis},
  title = {{Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=NGVljI6HkR},
}
Figure