Synthesizing Programmatic Policies that Inductively Generalize

Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, Armando Solar-LezamaICLR 2020 · OpenReview

Introduction

Deep reinforcement learning (RL) has achieved remarkable success in solving complex control tasks. However, standard neural network policies are notoriously brittle when faced with environments that differ even slightly from their training data. For instance, a neural network trained to park a car in a spot with 5 feet of clearance might fail completely if the spot shrinks to 4 feet, even though the underlying logic (back up, turn, pull forward) remains identical.

Researchers from MIT and UPenn address this gap by developing a method to train robots using programmatic state machine policies. Unlike standard neural networks, these "flowchart-like" policies can learn a repetitive behavior once and apply it an infinite number of times—a property known as inductive generalization.

The Adaptive Teaching Framework

The core challenge is that programmatic policies (policies written in discrete code) are incredibly hard to train. Their discrete, "if-then" nature lacks the smooth gradients required by modern AI optimization techniques. To bridge the gap between flexible neural optimization and rigid programmatic logic, the authors introduce a framework called Adaptive Teaching.

Adaptive Teaching Framework
  1. The Policy Class: Instead of a neural network, the "student" is a State Machine Policy. It consists of discrete "modes" (e.g., "Drive Forward"), continuous action functions for each mode, and "switching conditions" (e.g., "If distance to wall < 0.5m, switch to Reverse").
  2. The Teacher: To train this student, the authors use an "Adaptive Teacher," which acts as an over-parameterized trajectory optimizer to find the best path for a specific starting point.
  3. The Feedback Loop: Unlike traditional imitation learning where the student passively copies the teacher, this framework features a co-evolving dynamic. The teacher adaptively updates itself to favor strategies that are easy for the student's specific state-machine structure to represent.
  4. Optimization: The researchers use Variational Inference to formalize this process: the teacher acts as the "variational distribution" that guides the student toward high-reward areas of the policy space that are also "program-friendly."

Experimental Results and Insights

The authors evaluated their approach on six control benchmarks modified to test generalization, including navigating a car out of tight parking spots, flying a drone through obstacle courses, and balancing a cart-pole over varying time horizons.

State Machine Policy and Car Benchmark
  • Superior Generalization: In the Car benchmark, standard RL (PPO) achieved near-perfect scores on training data but failed on test data with tighter gaps. The programmatic policy maintained near-perfect performance across both by inductively generalizing the learned "back-and-forth" maneuver to accommodate the tighter space.
  • Structure as a Prior: Forcing the policy into a state machine provides a strong structural prior, hinting that the solution involves discrete steps and repetitions. This makes the policy identifiable from very little data, often requiring only 2 to 4 modes to solve complex tasks.
  • Interpretability and Human-in-the-Loop: Because the final policy is a state machine with human-readable predicates, engineers can easily interpret the agent's decision-making. The authors demonstrated that a user could manually tweak a threshold (e.g., tightening a distance check) in the synthesized code to improve performance without any additional training.
  • Robustness to Partial Observability: In tasks where obstacles are hidden, the state machine outperformed recurrent neural networks (LSTMs), proving that explicit state transitions can be more effective than hidden neural states.

Limitations and Future Directions

While powerful, the method has limitations. It currently struggles to scale to problems requiring very large state machines, as the search space for transition structures grows exponentially with the number of modes. Additionally, the teacher relies on model-based numerical optimization, requiring prior knowledge of the environment's physics. Future work may explore model-free techniques to enhance flexibility and reduce the burden of manually defining the program's building blocks (the grammar constraints).

Summary updated

Abstract

Deep reinforcement learning has successfully solved a number of challenging control tasks. However, learned policies typically have difficulty generalizing to novel environments. We propose an algorithm for learning programmatic state machine policies that can capture repeating behaviors. By doing so, they have the ability to generalize to instances requiring an arbitrary number of repetitions, a property we call inductive generalization. However, state machine policies are hard to learn since they consist of a combination of continuous and discrete structures. We propose a learning framework called adaptive teaching, which learns a state machine policy by imitating a teacher; in contrast to traditional imitation learning, our teacher adaptively updates itself based on the structure of the student. We show that our algorithm can be used to learn policies that inductively generalize to novel environments, whereas traditional neural network policies fail to do so.
BibTeX
@inproceedings{inala2020synthesizing,
  author = {Jeevana Priya Inala and Osbert Bastani and Zenna Tavares and Armando Solar-Lezama},
  title = {{Synthesizing Programmatic Policies that Inductively Generalize}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=e55r0iaKcQk},
}
Figure