Source-linked AI summary
Programmatically Interpretable Reinforcement Learning
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, Swarat Chaudhuri
TL;DR
PIRL addresses the difficulty of obtaining interpretable and verifiable reinforcement-learning policies by representing them as programs and searching within sketch-defined languages. NDPS uses a DRL neural oracle to guide local program search toward imitation, and the resulting policies meet meaningful performance goals while supporting transfer and verification. The framework is evaluated mainly in TORCS, with additional classic-control experiments.
Problem
Neural-network policies can be effective yet difficult to interpret or check for consistency with desired properties, especially in safety-critical applications.
Method
PIRL represents policies in a high-level language, while NDPS uses a DRL-learned neural oracle to guide local search over programmatic policies by behavioral distance.
Results
NDPS generates interpretable policies that clear reasonable performance goals, are amenable to symbolic verification, and, with a well-designed sketch, are robust and transferable to unseen environments.
Takeaways & Limitations
Programmatic policies can combine human readability and symbolic verification with useful reinforcement-learning performance and transferability.
Takeaways & Limitations
The experiments consider symbolic inputs and deterministic policies; perceptual inputs and stochastic policies remain future work.
Abstract
from arXiv · showhide
We present a reinforcement learning framework, called Programmatically Interpretable Reinforcement Learning (PIRL), that is designed to generate interpretable and verifiable agent policies. Unlike the popular Deep Reinforcement Learning (DRL) paradigm, which represents policies by neural networks, PIRL represents policies using a high-level, domain-specific programming language. Such programmatic policies have the benefits of being more easily interpreted than neural networks, and being amenable to verification by symbolic methods. We propose a new method, called Neurally Directed Program Search (NDPS), for solving the challenging nonsmooth optimization problem of finding a programmatic policy with maximal reward. NDPS works by first learning a neural policy network using DRL, and then performing a local search over programmatic policies that seeks to minimize a distance from this neural "oracle". We evaluate NDPS on the task of learning to drive a simulated car in the TORCS car-racing environment. We demonstrate that NDPS is able to discover human-readable policies that pass some significant performance bars. We also show that PIRL policies can have smoother trajectories, and can be more easily transferred to environments not encountered during training, than corresponding policies discovered by DRL.
1. Introduction
PIRL represents reinforcement-learning policies as human-readable programs, using sketches and NDPS to search a difficult policy space while retaining interpretability and verification benefits.
- Framework: PIRL represents policies in a high-level programming language and seeks the highest-reward program permitted by a policy sketch.The sketch syntactically defines the candidate program set.
- Framework: Syntactic restrictions can encode inductive bias, prune undesired policies, and support symbolic verification of correctness properties.PIRL policies can still depend on events far back in history.
- NDPS: NDPS first learns a high-performance neural policy with DRL, then directs local search over programmatic policies toward that neural oracle.The program space can be vast and nonsmooth, making direct optimization difficult.
- NDPS: NDPS seeks to minimize a distance from the neural oracle, treating this as an imitation-learning approach to searching the nonsmooth program space.The supplied passage introduces direct policy search in this setting.
- Evaluation: In TORCS and three classic control games, NDPS found interpretable policies that passed significant performance bars, including completing a TORCS lap.The TORCS policy used branches selecting among PID controllers with unknown parameters.
2. Programmatically Interpretable Reinforcement Learning
PIRL formalizes policy learning as finding a high-reward program within a sketch-defined language whose expressions map observation histories to actions.
- Formalization: A reinforcement-learning problem is modeled as a POMDP with states, actions, observations, transitions, rewards, initialization, and discounting.Policies map histories of observations and actions to actions.
- Formalization: The expected aggregate reward is discounted over time, and reinforcement learning seeks a policy that maximizes this quantity.The policy induces a distribution over possible rewards.
- Policy language: PIRL uses a high-level domain-specific functional language over atoms and sequences, including histories, observations, actions, and auxiliary values.The language is designed to express parameterized policies compactly and canonically.
- Policy language: A type system ensures consistent language use and identifies expressions whose inputs are histories and outputs are actions; these are programmatic policies.It can catch errors such as peeking beyond a history’s size.
- Sketches: Sketches restrict the grammar and operator choices to define a manageable set of candidate programs for policy search.The permitted programs are denoted by [[S]].
- Example: In the car example, the sketch encodes switching among PID controllers whose parameters and switching conditions are learned.The resulting acceleration policy uses sensor histories and conditional controller selection.
3. Neurally Directed Program Search
NDPS addresses nonsmooth program search by imitating a DRL-derived neural oracle, iteratively refining program structure and parameters on selected and augmented histories.
- Challenge: Programmatic-policy reward can vary irregularly over a vast search space, making ordinary local search perform poorly.This nonsmooth objective is the central technical challenge addressed by NDPS.
- Core method: NDPS computes a neural policy oracle with DRL and searches for a program that closely imitates its behavior.The oracle approximates the programmatic policy being sought.
- Core method: NDPS uses distance from the oracle as a simpler search objective than long-horizon reward aggregation.This reframes the search as imitation learning.
- Optimization: At each iteration, NDPS searches structurally similar program templates, optimizes their parameters, and retains the candidate minimizing oracle distance.Bayesian optimization is the primary parameter-optimization tool, with SMT explored additionally.
- Input augmentation: Input augmentation periodically simulates the current program, adds newly encountered histories, and updates oracle actions for those inputs.This addresses trajectories that the oracle or earlier programs never encountered.
- Algorithm details: NDPS initializes a pool of oracle-like programs, selects a high-reward starting point, and iterates until estimated reward stops improving.The algorithm begins by sampling oracle histories and repeatedly updates both the program and interesting-input set.
4. Environments for Experiments
The evaluation covers TORCS and three classic control games, using program sketches and simulated interaction to synthesize and assess controllers.
- Environments: NDPS is evaluated on TORCS and on Acrobot, CartPole, and MountainCar.The classic games have fewer sensors and discrete actions than TORCS.
- TORCS: TORCS controllers choose acceleration, brake, clutch, gear, and steering in an environment with up to 89 sensors and race-level decisions.The paper’s DRL agents use a DDPG approach for continuous action spaces.
- TORCS: TORCS sketches provide the structure of PID programs with holes for parameters and observations, while folds are limited to the five latest history observations.The fold restriction corresponds to automatic integral-error reset in discretized PID controllers.
- Evaluation procedure: Each TORCS track is treated as a distinct POMDP, and NDPS synthesizes a program for one selected track through racing simulations.Reward depends on the car’s speed, angle, and position at each time step.
- Evaluation procedure: The history-collection procedure records TORCS sensor observations from a synthesized lap and pairs them with actions generated by the DRL agent.These observation-action tuples are added to the history set.
5. Experimental Analysis
Experiments in TORCS and related control tasks evaluate NDPS against neural and alternative program-synthesis agents. NDPS produces interpretable policies with competitive race performance, smoother steering, robustness to blocked sensors, transfer to unseen tracks, and formally verified behavior.
- Experimental setup: NDPS synthesizes programmatic policies for TORCS tracks and classic control games, comparing them with DRL and ablation agents.The TORCS evaluation uses CG-Speedway-1 and Aalborg, while additional control-game results appear in the appendix.
- Performance evaluation: The NoAug and NoSketch variants cannot reliably produce programs completing a single lap on either TORCS track.NoSketch samples an excessively large unconstrained program space, while NoAug lacks oracle-based input guidance.
- Interpretability: NDPS policies are compact and human-readable by construction, unlike DRL policies encoded as black-box neural networks.The paper treats interpretability qualitatively and illustrates the programmatic policies with synthesized examples.
- Behavior of Policy: NDPS uses less aggressive actions and produces smoother steering than the DRL agent, measured by steering-action standard deviation over a complete race.Figure 3 visualizes a CG-Speedway-1 race slice, while Table 2 defines lower standard deviation as smoother steering.
- Generalization: The NDPS program far outperforms DRL on unseen tracks, while DRL cannot complete any evaluated transfer race.Transfer tests use CG tracks 2 and E-Road after CG-Speedway-1 training, and Alpine 2 and Ruudskogen after Aalborg training.
- Verifiability: Formal verification proves smooth-action implications and universal action bounds under stated sensor assumptions.For one policy, small recent RPM changes imply consecutive acceleration changes below 0.49; another guarantee bounds consecutive steering changes below 0.11 under small TrackPos changes.
6. Related Work
The paper distinguishes PIRL from approaches that either encode program semantics in neural networks or explain neural models after training. PIRL instead synthesizes human-readable source code and uses symbolic verification at the program level.
- Syntax-Guided Synthesis: Syntax-guided synthesis constrains program search with a sketch in addition to examples, addressing potentially intractable hypothesis spaces.
- Imitation Learning: NDPS uses a trained DeepRL agent as an oracle to guide iterative input-output augmentation and local search, rather than exactly imitating demonstrations.
- Neural Program Synthesis and Induction: Neural program induction learns program semantics inside network weights, often with differentiable computational substrates such as memory, modules, or stacks.
- Interpretable Machine Learning: Interpretability work commonly explains neural networks through abstraction, relevance propagation, or symbolic techniques, whereas PIRL replaces the neural policy with synthesized human-readable source code.
- Verification of Deep Neural Networks: Unlike DNN verification through specialized solvers such as Reluplex, PIRL outputs source code suitable for traditional symbolic program verification.
7. Conclusion
PIRL represents policies in a high-level language and uses NDPS to search for policies that satisfy a sketch while achieving long-term reward. The reported policies meet reasonable performance goals and support verification and transfer when the sketch is well designed, while the experiments remain scope-limited.
- PIRL represents reinforcement-learning policies in a high-level language, with NDPS searching for a policy that fits a syntactic sketch and optimizes long-term reward.
- The method generates interpretable policies that clear reasonable performance goals and are amenable to symbolic verification.
- Assuming a well-designed sketch, the reported policies are robust and easily transferred to unseen environments.
- The experiments considered only environments with symbolic inputs, leaving perceptual-input handling as a future algorithmic challenge.
A. Evaluation on Classic Control Games
The appendix evaluates NDPS on classic control games using OpenAI Gym implementations and compares rewards from optimal policies found by several methods. It describes the environments, evaluation setup, and optimization variants.
- The evaluation covers Acrobot, CartPole, and MountainCar using OpenAI Gym environment implementations.
- The experiments use DUEL-DDQN as the neural policy oracle for these games because its implementation appeared on the OpenAI Gym leaderboard.
- Acrobot: Acrobot uses six sensor readings, three discrete actions, −1 per-step reward, and a 200-step episode limit.
- CartPole: CartPole terminates after threshold violations or 200 steps, uses two discrete actions, and defines solving as average reward of at least 195.0 over 100 episodes.
- MountainCar: MountainCar uses position and velocity sensors, three discrete actions, −1 per-step reward, and a 200-step episode limit.
- The classic-control results table reports rewards from optimal policies found using various methods, with DRL listed in the first row.
- NDPS-SMT and NDPS-BOPT denote NDPS variants using SMT-based optimization and Bayesian optimization for template parameters.
B. Additional Details on Algorithm
The appendix details NDPS’s program-template enumeration, oracle-distance optimization, and alternative Bayesian and SMT parameter-search methods. It also reports that SMT is better suited to classic control’s small discrete action spaces but does not scale well to continuous actions.
- Distance computation: NDPS compares candidate programs with an oracle by minimizing the sum of output distances over histories.
- Discovered policies: The appendix illustrates synthesized steering and acceleration policies for Aalborg, CG-Speedway-1, and classic control environments.
- Program templates: NDPS enumerates templates by parameterizing numerical constants, eliding subexpressions, and regenerating them from sketch rules with shorter expressions prioritized.
- Bayesian optimization: Bayesian optimization searches real-valued template parameters using Euclidean output distances between synthesized programs and the neural oracle.
- SMT-based Optimization: SMT optimization constrains synthesized outputs to match oracle outputs within a constant error over the maintained histories.
- Max-Sat handling: Because the oracle is approximate, NDPS relaxes exact constraint satisfaction by assigning weighted constraints and solving a Max-Sat problem.
- Method limitations: SMT-based optimization does not scale well in continuous-action environments, so TORCS experiments exclusively use Bayesian optimization.
- Method comparison: SMT performs better on classic control because actions are limited to at most three discrete values, whereas Bayesian optimization uses more histories and can become trapped in local minima.
C. Policy Examples
This section presents examples of policies discovered by NDPS across driving tracks and classic control games. The examples include separate steering and acceleration policies for TORCS tracks and policies for Acrobot, CartPole, and MountainCar.
- TORCS policies: NDPS found a steering policy trained on the Aalborg track, paired with the paper’s acceleration policy.The steering policy appears in Figure 5, while the corresponding acceleration policy appears in Figure 2.
- TORCS policies: NDPS found separate acceleration and steering policies when trained on the CG-Speedway-1 track.Figures 6 and 7 show the acceleration and steering policies, respectively.
- Classic control games: Additional NDPS policies were found for Acrobot, CartPole, and MountainCar.Figures 8, 9, and 10 show the policies for these three classic control tasks, respectively.
D. TORCS Video
The video compares DRL and NDPS agents on a training track and the unseen E-Road transfer track. NDPS shows smoother steering on training and avoids the crash that prevents DRL from completing a transfer lap.
- Training track: On the training track, NDPS takes smoother steering actions than the DRL agent.The DRL steering actions are described as very irregular by comparison.
- Transfer track: On the unseen E-Road transfer track, the DRL agent crashes before completing a full lap, whereas the NDPS agent does not crash.The clips are short, but the text states that the behavior is representative of the entire race.