# Program Machine Policy: Addressing Long-Horizon Tasks by Integrating Program Synthesis and State Machines

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 73 references that are in the map.
- First posted on arXiv 27 Nov 2023.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [Quantifying Generalization in Reinforcement Learning](https://mlsanity.com/paper/1812.02341/) (2018)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks](https://mlsanity.com/paper/2306.13831/) (2023)
- [How to Train Your Robot with Deep Reinforcement Learning; Lessons We've Learned](https://mlsanity.com/paper/2102.02915/) (2021)
- [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)
- [ViZDoom: A Doom-based AI Research Platform for Visual Reinforcement Learning](https://mlsanity.com/paper/1605.02097/) (2016)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [A Study on Overfitting in Deep Reinforcement Learning](https://mlsanity.com/paper/1804.06893/) (2018)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [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)
- [Meta Learning Shared Hierarchies](https://mlsanity.com/paper/1710.09767/) (2017)
- [Bootstrap Your Own Skills: Learning to Solve New Tasks with Large Language Model Guidance](https://mlsanity.com/paper/2310.10021/) (2023)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [PEORL: Integrating Symbolic Planning and Hierarchical Reinforcement Learning for Robust Decision-Making](https://mlsanity.com/paper/1804.07779/) (2018)
- [Demo2Code: From Summarizing Demonstrations to Synthesizing Code via Extended Chain-of-Thought](https://mlsanity.com/paper/2305.16744/) (2023)
- [Diffusion Model-Augmented Behavioral Cloning](https://mlsanity.com/paper/2302.13335/) (2023)
- [Learning Finite State Representations of Recurrent Policy Networks](https://mlsanity.com/paper/1811.12530/) (2018)
- [Skill-based Meta-Reinforcement Learning](https://mlsanity.com/paper/2204.11828/) (2022)
- [LEAGUE: Guided Skill Learning and Abstraction for Long-Horizon Manipulation](https://mlsanity.com/paper/2210.12631/) (2022)

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

- [AI Agents as Universal Task Solvers](https://mlsanity.com/paper/2510.12066/) (2025)

## Abstract (arXiv)

Deep reinforcement learning (deep RL) excels in various domains but lacks generalizability and interpretability. On the other hand, programmatic RL methods (Trivedi et al., 2021; Liu et al., 2023) reformulate RL tasks as synthesizing interpretable programs that can be executed in the environments. Despite encouraging results, these methods are limited to short-horizon tasks. On the other hand, representing RL policies using state machines (Inala et al., 2020) can inductively generalize to long-horizon tasks; however, it struggles to scale up to acquire diverse and complex behaviors. This work proposes the Program Machine Policy (POMP), which bridges the advantages of programmatic RL and state machine policies, allowing for the representation of complex behaviors and the address of long-term tasks. Specifically, we introduce a method that can retrieve a set of effective, diverse, and compatible programs. Then, we use these programs as modes of a state machine and learn a transition function to transition among mode programs, allowing for capturing repetitive behaviors. Our proposed framework outperforms programmatic RL and deep RL baselines on various tasks and demonstrates the ability to inductively generalize to even longer horizons without any fine-tuning. Ablation studies justify the effectiveness of our proposed search algorithm for retrieving a set of programs as modes.