Research map / Probabilistic and scientific modeling / Molecules and proteins
Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that simple hill climbing directly in the hand-defined programmatic space (Karel DSL) outperforms latent-space methods LEAPS, HPRL and CEBS, and explains this via a convergence-rate (search topology) analysis.
Problem
Latent spaces learned for domain-specific languages (LEAPS, HPRL) are assumed to ease program synthesis of programmatic policies for POMDPs, but no baseline searches directly in the programmatic space to test whether the latent space helps.
Approach
Use a training-free programmatic space induced by the DSL with AST-mutation neighborhoods and hill climbing; compare against latent-space search on behavior-loss similarity and on a convergence-rate measure of how often local search gets stuck at local maxima.
Key results
- On Karel-Hard DoorKey, hill climbing in the programmatic space reaches 0.84±0.02 return versus 0.50 for LEAPS, HPRL and CEBS in latent space.
- On Snake, hill climbing achieves 0.65±0.03 versus 0.23 (LEAPS), 0.33 (HPRL), 0.26 (CEBS).
- Generating one neighbor takes 0.0021 s in the programmatic space versus 0.0293 s in the latent space (more than 10x faster).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Search in programmatic space with HC instead of latent-space search | HC versus LEAPS, HPRL, and CEBS · StairClimber and Maze | episodic return: 1.00\pm0.00 | No clear effect |
| Search in programmatic space with HC instead of latent-space search | HC versus HPRL and CEBS · TopOff, FourCorners, Harvester, and CleanHouse | episodic return: 1.00\pm0.00 | No clear effect |
| Search in programmatic space with HC instead of latent-space search | HC versus LEAPS, HPRL, and CEBS · DoorKey | episodic return: 0.50\pm0.00 -> \mathbf{0.84}\pm0.02 | Helped |
| Search in programmatic space with HC instead of latent-space search | HC versus LEAPS, HPRL, and CEBS · OneStroke | episodic return: 0.90\pm0.00 -> \mathbf{0.95}\pm0.00 | Helped |
| Search in programmatic space with HC instead of latent-space search | HC versus LEAPS, HPRL, and CEBS · Seeder | episodic return: \mathbf{1.00}\pm0.00 | No clear effect |
| Search in programmatic space with HC instead of latent-space search | HC versus LEAPS, HPRL, and CEBS · Snake | episodic return: 0.33\pm0.07 -> \mathbf{0.65}\pm0.03 | Helped |
| Initialize search with programs sampled from the probabilistic grammar instead of latent samples (ablation) | CEM and CEBS in latent space · Karel and Karel-Hard tasks | episodic return | No clear effect |
| Initialize search by decoding a latent sample instead of sampling a program from the grammar (ablation) | HC in programmatic space · Karel and Karel-Hard tasks | episodic return | No clear effect |
| Use programmatic space instead of latent space for hill climbing | HC · Karel and Karel-Hard convergence-rate evaluation | convergence rate | Helped |
| Vary neighborhood size to K=10, K=250, or K=1,000 (ablation) | HC in programmatic and latent spaces · Karel and Karel-Hard convergence-rate evaluation | convergence rate | Mixed |
| Replace HC with CEBS in latent space (ablation) | Latent-space convergence-rate search · Harvester, DoorKey, OneStroke, and Seeder | convergence rate | Helped |
| Replace HC with CEM in latent space (ablation) | Latent-space convergence-rate search · Karel and Karel-Hard tasks | convergence rate | No clear effect |
Surprising findings
- A simple hill-climbing search without escape mechanisms outperforms state-of-the-art latent-space methods on most tasks.
- The programmatic space achieves behavior-loss values comparable to the trained latent spaces despite requiring no training.
Limitations
- Evaluation limited to the Karel the Robot domain and its task sets.
- Latent space results depend on hyperparameters (sigma, dimension) taken from prior work, not extensively tuned.
- Convergence analysis uses hill climbing only, which cannot escape local maxima, so conclusions about other search algorithms are indirect.
Experimental setup
Datasets: Karel the Robot tasks (Karel) Karel-Hard tasks programs sampled from LEAPS probabilistic CFG
Benchmarks: Karel Karel-Hard Crashable Karel
Metrics: episodic return behavior loss / behavior-similarity identity-rate convergence rate running time per neighbor
Baselines: LEAPS HPRL CEBS CEM
Builds on: LEAPS HPRL Cross-Entropy Method
Closest papers by meaning
- Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search (ICLR 2025 · similarity 0.87)
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.86)
- Online Markov Decision Processes Configuration with Continuous Decision Space (AAAI 2024 · similarity 0.86)
- Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction (ICML 2024 · similarity 0.85)
- Oracle-Efficient Reinforcement Learning for Max Value Ensembles (NeurIPS 2024 · similarity 0.85)
- Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.