# Program Synthesis Guided Reinforcement Learning for Partially Observed Environments

arXiv: https://arxiv.org/abs/2102.11137 · HTML: https://mlsanity.com/paper/2102.11137/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 80 references that are in the map.
- First posted on arXiv 22 Feb 2021.

## Builds on (most cited first, 30 of 39)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [World Models](https://mlsanity.com/paper/1803.10122/) (2018)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [A Deep Hierarchical Approach to Lifelong Learning in Minecraft](https://mlsanity.com/paper/1604.07255/) (2016)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Learning to Infer Graphics Programs from Hand-Drawn Images](https://mlsanity.com/paper/1707.09627/) (2017)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Learning to Infer and Execute 3D Shape Programs](https://mlsanity.com/paper/1901.02875/) (2019)
- [Hierarchical Reinforcement Learning By Discovering Intrinsic Options](https://mlsanity.com/paper/2101.06521/) (2021)
- [Neurosymbolic Reinforcement Learning with Formally Verified Exploration](https://mlsanity.com/paper/2009.12612/) (2020)
- [Sub-policy Adaptation for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1906.05862/) (2019)
- [Hierarchical Reinforcement Learning for Zero-shot Generalization with Subtask Dependencies](https://mlsanity.com/paper/1807.07665/) (2018)
- [DAC: The Double Actor-Critic Architecture for Learning Options](https://mlsanity.com/paper/1904.12691/) (2019)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples](https://mlsanity.com/paper/1804.01186/) (2018)
- [HOUDINI: Lifelong Learning as Program Synthesis](https://mlsanity.com/paper/1804.00218/) (2018)
- [Learning Differentiable Programs with Admissible Neural Heuristics](https://mlsanity.com/paper/2007.12101/) (2020)
- [Data-efficient Hindsight Off-policy Option Learning](https://mlsanity.com/paper/2007.15588/) (2020)

## Built on by (most cited first, 8 of 8)

- [Learning Language-Conditioned Robot Behavior from Offline Data and Crowd-Sourced Annotation](https://mlsanity.com/paper/2109.01115/) (2021)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs](https://mlsanity.com/paper/2207.05006/) (2022)
- [Programmatic Reward Design by Example](https://mlsanity.com/paper/2112.08438/) (2021)
- [A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2204.09772/) (2022)
- [Exploring with Sticky Mittens: Reinforcement Learning with Expert Interventions via Option Templates](https://mlsanity.com/paper/2202.12967/) (2022)
- [Improving Reliable Navigation under Uncertainty via Predictions Informed by Non-Local Information](https://mlsanity.com/paper/2307.14501/) (2023)
- [Learning Explainable Representations of Complex Game-playing Strategies](https://mlsanity.com/paper/2610.07638/) (2026)

## Abstract (arXiv)

A key challenge for reinforcement learning is solving long-horizon planning problems. Recent work has leveraged programs to guide reinforcement learning in these settings. However, these approaches impose a high manual burden on the user since they must provide a guiding program for every new task. Partially observed environments further complicate the programming task because the program must implement a strategy that correctly, and ideally optimally, handles every possible configuration of the hidden regions of the environment. We propose a new approach, model predictive program synthesis (MPPS), that uses program synthesis to automatically generate the guiding programs. It trains a generative model to predict the unobserved portions of the world, and then synthesizes a program based on samples from this model in a way that is robust to its uncertainty. In our experiments, we show that our approach significantly outperforms non-program-guided approaches on a set of challenging benchmarks, including a 2D Minecraft-inspired environment where the agent must complete a complex sequence of subtasks to achieve its goal, and achieves a similar performance as using handcrafted programs to guide the agent. Our results demonstrate that our approach can obtain the benefits of program-guided reinforcement learning without requiring the user to provide a new guiding program for every new task.