Verifiable Reinforcement Learning via Policy Extraction

By Osbert Bastani, Yewen Pu, Armando Solar-Lezama. 2018

407 citations recorded by the source corpus.

While deep reinforcement learning has successfully solved many challenging control tasks, its real-world applicability has been limited by the inability to ensure the safety of learned policies. We propose an approach to verifiable reinforcement learning by training decision tree policies, which can represent complex policies (since they are nonparametric), yet can be efficiently verified using existing techniques (since they are highly structured). The challenge is that decision tree policies are difficult to train. We propose VIPER, an algorithm that combines ideas from model compression and imitation learning to learn decision tree policies guided by a DNN policy (called the oracle) and its Q-function, and show that it substantially outperforms two baselines. We use VIPER to (i) learn a provably robust decision tree policy for a variant of Atari Pong with a symbolic state space, (ii) learn a decision tree policy for a toy game based on Pong that provably never loses, and (iii) learn a provably stable decision tree policy for cart-pole. In each case, the decision tree policy achieves performance equal to that of the original DNN policy.

Subfields: Artificial Intelligence, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

Citations in the corpus

Scalable agent alignment via reward modeling: a research direction (2018, background): “If formal veriﬁcation can be scaled, we could attempt to verify properties of policies (Bastani et al., 2018) and reward functions with respect to a high-level speciﬁcation, including off-switches, side-effects, and others mentioned in Section 3.1.”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Progress has been made instead on explainable deep reinforcement learning (posthoc approximations), including tree-based explanations [66, 189, 81, 22, 73], reward decomposition [138], and attention-based methods”
Designing Interpretable Approximations to Deep Reinforcement Learning with Soft Decision Trees (2020, background): “Deep neural network (DNN)-driven algorithms now stand as the state of the art in a variety of domains, from perceptual tasks such as computer vision, speech and language processing to, more recently, control tasks such as robotics (Mirzadeh et al. 2019), (Bastani, Pu, and Solar-Lezama 2018).”
Toward Interpretable-AI Policies Using Evolutionary Nonlinear Decision Trees for Discrete-Action Systems (2020, methodology): “[24] extends this to utilize Q-values and eventually render DT policies involving < 1, 000 nodes on some toy games and CartPole environment with an ultimate aim to have the induced policies verifiable.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “The parameter values are ﬁxed to match those produced by the decision tree com-39 puted using CART.”
Neurosymbolic Program Synthesis (positive): “The P IRL [11] and V IPER [12] methods for “programmatic” reinforcement learning (RL) were the first distillation approaches to N SP .”
A Review of Safe Reinforcement Learning: Methods, Theory and Applications (2022, methodology): “To achieve safety policy, a growing number of approaches have been developed over the last few decades, such as primal-dual methods [51, 152, 160, 207, 235, 239, 271, 301], trust region with safety constraints methods [4, 32, 33, 106, 283, 307], formal methods [15, 23, 25, 86, 87, 120, 189, 208, 229”
Towards Mixed Optimization for Reinforcement Learning with Program Synthesis (2018, methodology): “Similarly, VIPER (Bastani et al., 2018) uses imitiation learning (a modified form of the DAGGER algorithm (Ross et al., 2011)) to extract a decision tree corresponding to the learned policy.”
Fairness with Dynamics (2019, background): “The key challenge is that learning with a fairness constraint is much more challenging in the MDP setting due to the inherent non-convexity—indeed, constrained reinforcement learning is an active research area (Altman, 1999; Achiam et al., 2017; Wen & Topcu, 2018; Bastani et al., 2018).”
Learning by Cheating (2019, neutral): “[3].”
Learning to Synthesize Programs as Interpretable and Generalizable Policies (2021, background): “[12] learns a decision tree as a programmatic policy for pong and cartpole environments by imitating an oracle neural policy.”
Learning Interpretable Models with Causal Guarantees (2019, methodology): “Performance (in terms of √ PEHE) of CART (left) and honest trees (right) using our approach (black, solid) and the baseline approach (red, dashed) on the IHDP dataset, as a function of the depth of the decision tree. forests (Breiman, 2001).”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “Mixed-integer programming formulations with better performance were given by Bertsimas and Dunn (2017) and Verwer and Zhang (2017).”
Provable repair of deep neural networks (2021, positive): “[7] present policy extraction for synthesizing provably robust decision tree policy for deep reinforcement learning.”