MoET: Interpretable and Verifiable Reinforcement Learning via Mixture of Expert Trees
Authors: Marko Vasic
Andrija Petrovic
Kaiyuan Wang
Mladen Nikolic
Rishabh Singh
Sarfraz Khurshid
Venue:  (2020)
Keywords: explainable machine learning
reinforcement learning

Abstract: Deep Reinforcement Learning (DRL) has led to many recent breakthroughs on complex control tasks, such as defeating the best human player in the game of Go. However, decisions made by the DRL agent are not explainable, hindering its applicability in safety-critical settings. Viper, a recently proposed technique, constructs a decision tree policy by mimicking the DRL agent. Decision trees are interpretable as each action made can be traced back to the decision rule path that lead to it. However, one global decision tree approximating the DRL policy has significant limitations with respect to the geometry of decision boundaries. We propose MoET, a more expressive, yet still interpretable model based on Mixture of Experts, consisting of a gating function that partitions the state space, and multiple decision tree experts that specialize on different partitions. We propose a training procedure to support non-differentiable decision tree experts and integrate it into imitation learning procedure of Viper. We evaluate our algorithm on four OpenAI gym environments, and show that the policy constructed in such a way is more performant and better mimics the DRL agent by lowering mispredictions and increasing the reward. We also show that MoET policies are amenable for verification using off-the-shelf automated theorem provers such as Z3.

Under review as a conference paper at ICLR 2020
МOËТ: INTERPRETABLE & VERIFIABLE REINFORCE- MENT LEARNING VIA MIXTURE OF EXPERT TREES
Anonymous authors
Paper under double-blind review
ABSTRACT
Deep Reinforcement Learning (DRL) has led many recent breakthroughs on complex control tasks, such as defeating the best human player in the game of Go. However, decisions made by the DRL agent are not explainable, hindering its applicability in safety-critical settings. Viper, recently proposed technique, constructs a decision tree policy by mimicking the DRL. agent. Decision trees are interpretable each action made can be traced back the decision rule path that lead to it. However, one global decision tree approximating the DRL policy has significant limitations with respect to the geometry of decision boundaries. We propose MOËT, a more expressive, yet still interpretable model based on Mix- ture of Experts, consisting of a gating function that partitions the state space, and multiple decision tree experts that specialize on different partitions. We propose a training procedure support non-differentiabee decision free experts and integrate it into imitation learning procedure of Viper. We evaluate our algorithm on four OpenAI gym environments, and show that the policy constructed in such a way is more performant and better mimics the DRL agent by lowering mispredictions and increasing the reward. We also show that MOËT policies are amenable for verification using off-the-shed automated theorem provers such as Z3.
INTRODUCTION
Deep Reinforcement Learning (DRL) has achieved many recent breakthroughs in challenging do- mains such as Go (Silver et al.) 2016). While using neural networks for encoding state representa- tions allow DRL agents to learn policies for tasks with large state spaces, the learned policies are not interpretable, which hinders their use in safety-critical applications.
Some recent works leverage programs and decision trees representations for interpreting the learned agent policies. PIRL(Verm) Verma et al. 2018) uses program synthesis to generate a program in Domain-Specifie Language (DSL) that close to the DRL agent policy. The design of the DSL with desired operators is a tedious manual effort and the enumerative search for synthesis is difficult to scale for larger programs. In contrast, Viper (Bastani et al.) 2018) learns a Decision Tree (DT) policy by mimicking the DRL agent, which not only allows for general representation for different policies, but also allows for verification of these policies using integer linear programming solvers.
Viper uses the DAGGER (Ross et al.) 2011) imitation learning approach to collect state action pairs for training the student DT policy given the teacher DRL policy. modifies the DAGGER algorithm to use the Q-function of teacher policy to prioritize states of critical importance during learning. However, learning a single DT for the complete policy leads to some key shortcomings such as less faithful representation of original agent policy measured by the number of mispredictions, ii) lower overall performance (reward), and iii) larger DT sizes that make them harder to interpret.
In this paper, we present MOËT (Mixture of Expert Trees), technique based on Mixture of Experts (MoE) (Jacobs et al. 1991 Jordan and Xu 1995 Yuksel et al. (012), and reformulate its learning procedure to support DT experts. MoE models can typically use any expert as long as it is differentiable function model parameters, which unfortunately does not hold for DTs. Similar to MOE training with Sopeetation-Maxiiiiaa trained by interchangeably optimizing the weighted log likelihood for experts (independently from one another) and optimizing the gating function with respect to the obtained experts. Then, propose a procedure for DT learning in the specific context MOE. To the best of our knowledge are first to combine standard oindiffferet DT experts, which are interpretable, with MoE
(EM) algorithm, we first observe that MOËT can be

---

Under review as a conference paper at ICLR 2020
Existing combinations which rely on differentiable tree treelike models, such as soft decision trees (Isoo et al. 2012) and hierarchical mixture of experts (Zhao et al. 2019) are not interpretable.
model.
We adapt the imitation learning technique of Viper to use MoËT policies instead of DTs. MOËT creates multiple local DT's that specialize different regions of the input space, allowing for sim- pler (shallower) DT's that more accurately mimic the DRL agent policy within their regions, and combines the local trees into a global policy using a gating function. We use simple and inter- pretable linear model with softmax function as the gating function, which returns a distribution over DT experts for each point in the input space. While standard MoE uses this distribution average predictions of DTs, we also consider selecting just one most likely expert tree to improve inter- pretability. While decision boundaries of Viper DT policies must be exiss-erpendiculee the softmax gating function supports boundaries with hyperplanes of arbitrary orientations, allowing MOËT to more faithfully represent the original policy.
We evaluate our technique on four different environments: CartPole, Pong, Acrobot, and Mountain- car. We show that MOËT achieves significantly better rewards and lower misprediction rates with shallower trees. We also visualize the Viper and МOËT policies for Mountaincar, demonstrating the differences in their learning capabilities. Finally, we demonstrate how a MoËT policy can be translated into an SMT formula for verifying properties for CartPole game using the Z3 theorem prover De Moura and Bjørner 2008) under similar assumptions made in Viper.
In summary, this paper makes the following key contributions: 1) We propose MOËT, technique based on MoE to learn mixture of expert decision trees and present a learning algorithm to train МOËT models. 2) We use MOËT models with softmax gating function for interpreting DRL policies and adapt the imitation learning approach used in Viper to learn МOËT models. 3) We evaluate MOËT on different environments and show that it leads to smaller, more faithful, and performant representations of DRL agent policies compared to Viper while preserving verifiability.
2 RELATED WORK
Interpretable Machine Learning: In numerous contexts, it is important to understand and interpret the decision making process of machine learning model. However, interpretability does have unique definition that is widely accepted. Accoding to Lipton (Lipton) 2016), there are several prop- erties which might be meant by this word and we adopt the one which Lipton names transparency which is further decomposed to simulability, decomposability, and algorithmic transparency. A model simulable if a person can reasonable time compute the outputs from given inputs and in that way simulate the model's 's inner workings. That holds for small linear models and small decision trees [Lipton| 2016). A model is decomposable if each part of a models admits an intuitive explana- tion, which again the case for simple linear models and decision trees (Lipton 2016). Algorithmic transparency is related to our understanding of the workings of the training algorithm. For instance, in case of linear models the shape of the eтror surface and properties of its unique minimum to- wards which the algorithm converges are well understood (Lipton 2016). MOËT models focus on transparency (as we discuss at the end of Section 5) Explainable Machine Learning: There has been a lot of recent interest in explaining decisions of black-box models (Guidotti al., 20188a) Doshi-Velez and Kiml (017). For image classification, activation maximization techniques can be used to sample representative input patterns (Erhan et al.) 2009 Olah et al. 2017). TCAV (Kim al. 2017) uses numan-friendly high-level concepts asso- ciate their importance to the decision. Some recent works also generate contrastive robust explana- tions to help users understand a classifier decision based on family of neighboring inputs (Zhang et al. 20188 Dhurandhar et al.) 2018). LORE (Guidotti et al. (20 8b) explains behavior of a black- box model around an input of interest by sampling the black-box model around the neighborhood of the input, and training local DT over the sampled points. Our model presents approach that combines local trees into a global policy.
Tree- Sree-Structured Models:
Irsoy et al. (Irsoy et al. 2012) propose novel decision tree architecture with soft decisions at the internal nodes where both children are chosen with probabilities given by sigmoid gating function. Similarly, binary tree-structured hierarchical routing mixture of experts (HRME) model, which has classifiers as non-leaf node experts and simple regression models as leaf node experts, were proposed in (Zhao et al. 2019). Both models unfortunately not interpretable.
2

---

Under review as a conference paper at ICLR 2020
(c) Gridworld MOËT Policy
(a) Gridworld
(b) Gridworld Viper Policy
Figure I: A simple 5 x Gridworld example to showcase the policies learned by Viper and MOËT.
Knowledge Distillation and Model Compression: We rely on ideas already explored in fields of model compression (Bucilu et al. 2006) and knowledge distillation (Hinton et al.] 2015). The idea is to use complex well performing model to facilitate training of simpler model which might have some other desirable properties (e.g., interpretability). Such practices have been applied to approximate decision tree ensemble by a single tree (Breiman and Shang 1996), but this is different from our casc, since we approximate a neural network. In a similar fashion a neural network can be used to train another neural network (Furlanello et al.) 20188), but neural networks are hard to interpret and even harder to formally verify, so this is also different from our case. Such practices have also been applied in the field of reinforcement learning in knowledge and policy distillation (Rusu et al. [2016] Koul et al. 20199] Zhang et al.] (201)). which are similar in spirit to our work, and imitation learning (Bastani al.) 2018 Ross al. 201 Abbeel and Ng 2004
Schaal 1999)
which provide foundation for our work.
3 MOTIVATING EXAMPLE: GRIDWORLD
We now present a simple motivating example to showcase some of the key differences between Viper and MoËT approaches. Consider the N x N Gridworld problem shown in Figure Ia (for N = 5)- The agent is placed at a random position in a grid (except the walls denoted by filled rectangles) and should find its way out. To move through the grid the agent can choose to go up, left, right or down at each time step. If it hits the wall stays in the same position (state). State is represented using two integer values (I, y coordinates) which range from (0, 0) bottto left to (N - N, 1)-top right. The grid can be escaped through either left doors (left of the first column), or right doors (right of the last column). A negative reward of -0.1 is received for each agent action (negative reward encourages the agent to find the exit as fast as possible). An episode finishes as soon as an exit is reached or if 100 steps made whichever comes first.
The optimal policy (T.)) for this problem consists of taking the left (right resp.) action for each state below (above resp.) the diagonal. We used л. teacher and used imitation learning approach of Viper to train an interpretable DT policy that mimics T. The resulting DT policy is shown in Figure Tb The DT partitions the state space (grid) using lines perpendicular
and y axes, until separates all states above diagonal from those below. This results in a DT of depth 3 with 9 nodes. On the other hand, the policy learned by MOËT shown in Figure Ic The MoËT model with experts learns partition the space using the line defined by linear function 1.06xz 1.11y 4 (roughly the diagonal of the grid). Points on the different sides of the line correspond to two different experts which are themselves DTs of depth 0 always choosing go left (below) or right (above).
We notice that DT policy needs much larger depth to represent n. while MOËT can represent as only one decision step. Furthermore, with increasing N (size of the grid), complexity of DT will grow, while MoËT complexity stays the same; we empirically confirm this for N = [5. 10). For N 5, 6, 7, 9, 10 DT depths are 3, 4, 4, 4, 4, and number of nodes are 9, 11, 13, 15, 17, 21 respectively. In contrast, MOËT models of same complexity and structure as the one shown in Figure Tc are learned for all values of N (models differ in the learned partitioning linear function).
3

---

Under review as a conference paper at ICLR 2020
4 BACKGROUND
In this section we provide description of two relevant methods we build upon: (1) Viper, an approach for interpretable imitation learning, and (2) MOE learning framework.
Viper. Viper algorithm (included in appendix) is an instance of DAGGER imitation learning ap- proach, adapted to prioritize critical states based Q-values. Inputs to the Viper training algo- rithm are (1) environment e which is an finite horizon (T-step) Markov Decision Process (MDP) (S, A, P, R) with states S, actions A, transition probabilities P S x A + [0. and rewards R S - RR; (2) teacher policy Te : S + A; (3) its Q-function Q== : S x A - R and (4) num- ber of training iterations N. Distribution of states after T steps in environment e using a policy π is (c) (assuming randomly chosen initial state). Viper uses the teacher as oracle to label the data (states with actions). initially uses teacher policy to sample trajectories (states) to train a student (DT) policy. It then uses the student policy to generate more trajectories. Viper samples training points from the collected dataset D giving priority to states s having higher importance (s),, where [s) A QT* a) m A QT (s, a). This sampling of states leads faster learning and shallower DTs. The process of sampling trajectories and training students is repeated for number of iterations N, and the best student policy is chosen using reward as the criterion.
Mixture of Experts. MoE is an ensemble model (Jacobs et al., 1991; Jordan and Xu 1995 Yuksel jt al., 2012) that consists of expert networks and gating function. Gating function divides the input (feature) space into regions for which different experts are specialized and responsible. MoE is flexible with respect to the choice of expert models as long as they are differentiable functions of model parameters (which is not the case for DTs).
In MOE framework, probability of outputting y E IR given an input x E IR" is given by:
E
0) = Σ P(ilx,0,) P(y) 0,) Σ (x, 0,) P(r
(1)
1=1
where E is the number of experts, (x, 02) is the probability of choosing the expert (given input x), P(y x, 0t) is the probability of expert producing output y (given input x). Learnable parameters are 0 (0g. Oz), where Og parameters of the gating function and 0z = (0,, 0g .... 0g) are parameters of the experts. Gating function can be modeled using a softmax function over a set of linear models. Let fg consist of parameter vectors 0g.....,0))) then the gating function can be defined as gx 0g) exp(e"xx//E exp()"))x)
In the case of classification, an expert i outputs a vector y; of length C, where C is the number of classes. Expert associates a probability to each output class e (given by yic) using the gating function. Final probability of a class c is a gate weighted sum of yıe for all experts i E 1,2,.... E. This creates probability vector y (3/, 12, MC)), and the output of MoE arg max, Yi.
MOE is commonly trained using EM algorithm, where instead of direct optimization of the likeli- hood one performs optimization of an auxiliary function L defined in a following way. Let z denote the expert chosen for instance x. Then joint likelihood of x and z can be considered. Since is not observed in the data, log likelihood of samples (x, 2, y) cannot be computed, but instead expected log likelihood can be considered, where expectation is taken over 2. Since the expectation has to rely on some distribution of in the iterative process, the distribution with respect to the current estimate of parameters 0 is used. More precisely function Ł is defined by (Jordan and Xu 1995):
[(0, o(*)) = E, log P(x, z, y) y, 0(5)]= = / P(z|x, (10)) log P(x, 2, y)
(2)
where g(k) is the estimate of parameters o in iteration k. Then, for a specific sample D yx) | ii=li Ny. the following formula can be derived (Jordan and Xu 1995):
E
E
1(0,0
(1) log 93 (x,, 0,) +
(k) log P(y.lx,,,) 0,) Mi
(3)
i=1
where it holds
gj (x;, 0940) P(y xi, 0(4)))
(4)
Σ 1 91 (x:, (k) P(ys) 0(10))
4

---

Under review as a conference paper at ICLR 2020
5 MIXTURE OF EXPERT TREES
In this section we explain the adaptation of original MoE model to mixture of decision trees, and present both training and inference algorithms.
Considering that coefficients (k) (first double sum) and each expert part depend on disjoint subsets of parameters 6, training can be carried out by interchangeably optimizing the weighted log likelihood for experts (independently from one another) and optimizing the gating function with respect to the obtained experts. The training procedure for MOËT, described by Algorithm [1 is based on this observation. First, the parameters of the gating function are randomly initialized (line Then the experts are trained one by one. Each expert j is trained on a dataset D'r of instances weighted by coefficients h: (line 5). by applying specific DT learning algorithm (line 6) that we adapted for MoF context (described
Hig (Eq. are fixed with respect to 0 and that in Eq. 3 the gating part
below). After the experts are trained, an optimization step is performed (line 7 in order to increase the gating part of Eq. 3 At the end, the parameters are returned (line 8)
Our tree learning procedure is as follows. Our technique modifies original MOE algorithm in that uses DT's experts. The fundamental difference with respect to traditional model comes from the fact that DTss do not rely on explicit and differentiable loss function which can be trained by gradient descent or Newton's 's methods. Instead, due to their discrete structure, they rely on specific greedy training procedure. Therefore, the training of DTss has to be modified in order to take into account the
attribution of instances to the experts given by coefficients hij (k) sometimes called responsibility of expert j for instance i. If these responsibilities were hard, meaning that each instance is assigned to strictly one expert, they would result in partitioning the feature space into disjoint regions belonging to different experts. On the other hand, soft responsibilities are fractionally distributing each instance to different experts. The higher the responsibility of an expert for an instance i, the higher the influence of that instance on that expert's 's training. In order to formulate this principle, we consider which way the instance influences construction of tree. First, it affects the impurity measure computed when splitting the nodes and second, it influences probability estimates in the leaves of the tree. We address these two issues next.
A commonly used impurity measure to determine splits in the tree is the Gini index. Let U be a set of indices of instances assigned to the node for which the split being computed and Dy set of corresponding instances. Let categorical outcomes of be 1,..., C and for 1 = 1, C denote Pt fraction of assigned instances for which it holds y = L. More formally pt = Exer [/m= where I denotes indicator function of its argument expression and equals 1 if the expression is true. Then the Gini index G of the set Du is defined by: G(pi,..., PPC) = > př. Considering that the assignment of instances to experts are fractional as defined by responsibility coefficients (1) (which provided tree fitting function weights of instances computed in line the algorithm), this definition has to be modified in that the instances assigned to the node should not be counted, but instead, their weights should be summed. Hence, we propose the following definition:
[8]
P: EiEv Aly = =1 (K)
EiEU h(1)
and compute the Gini index for the set DU as Pc). Similar modification can be per- formed for other impurity measures relying on distribution of outcomes of categorical variable, like entropy. Note that while the instance assignments experts are soft, instance assignments to nodes within an expert are hard, meaning sets of instances assigned to different nodes are disjoint. Probability estimate for y in the leaf node is usually performed by computing fractions of instances belonging to each class. In our case, the modification is the same as the one presented by Eq. [] That
way, estimates of probabilities P(y |x, g(²)) needed by MoE are defined. In Algorithm function fit.tree performs decision tree training using the above modifications.
We consider two ways to perform inference with respect to the obtained model. First one which call MOËT, is performed by maximizing P(y|x, 9) with respect to y where this proba- bility is defined by Eq. [ The second way, which we call МоËт,, performs inference as arg maxy P(y (x, Oarg max, 9, (=,,,)), meaning that only rely on the most probable expert.
5

---

Under review as a conference paper at ICLR 2020
Algorithm MOËT training.
1: procedure MOËT (DATA {(x;) 1....,,.. NY. EPOCHS NE. NUMBER OF EXPERTS E))
2: 0g + initialize()
3: for 4 1 to NE do
4: for j + 1 to E do
5:
Dw
Ni. 9: 2x
1i -i= 1i=1,...,N
0
6:
0j + (Dtt
7:
90 (x 0g + 0g A Ei= 2===
9 0,(x,,,)
log Bj (x; 0²)
8: return 0g. (ft,...,,8))
Adaptation of MOËT to imitation learning. We integrate MOËT model into imitation learning approach of Viper by substituting training of DT with the MOËT training procedure.
Expressiveness. Standard decision trees make their decisions by partitioning the feature space into regions which have borders perpendicular to coordinate axes. To approximate borders that not perpendicular to coordinate axes very deep trees are usually necessary. МOËT, mitigates this short- coming by exploiting hard softmax partitioning of the feature space using borders which still hyperplanes, but need not be perpendicular to coordinate axes (see Section 3 This improves the expressiveness of the model.
Interpretability and Verifiability. A MOËT, model is a combination of a linear model and several decision tree models. For interpretability which is preserved Lipton's sense of transparency, is important that a single DT is used for each prediction (instead of weighted average). Simultability of MoËT, consisting of DT and linear models preserved because our models are small (2 S depth S 10) and we do not use high dimensional features (Lipton) [2016), so person can easily simulate the model. Similarly, decomposability is preserved because simple linear models without heavily engineered features and decision trees are decomposable (Lipton 2016) and MOËT, is a simple combination of the two. Finally, algorithmic transparency is achieved because MOËT training re- lies DT training for the experts and linear model training for the gate, both of which are well understood. However, the alternating refinement of initial feature space partitioning and experts makes the procedure more complicated, portantly, we define a well-founded translation of MOËT, models to SMT formulas, which opens a new range of possibilities for interpreting and validating the model using automated reasoning tools. SMT formulas provide rich means of logical reasoning, where a user can ask the solver questions such as: "On which inputs do the two models differ?", or "What is the closest input to the given input on which model makes different prediction?", or "Are the two models equivalent?", or "Are the two models equivalent in respect to the output class C?". Answers to these and similar questions can help better understand and compare models in rigorous way. Also note that our symbolic rea- soning of the gating function and decision trees allows us to construct SMT formulas that are readily handled by off-the-sheef tools, whereas direct SMT encodings of neural networks do not scale for any reasonably sized network because of the need for non-linear arithmetic reasoning.
algorithmic transparency partially achieved. Im-
EVALUATION
We now compare MOËT and Viper on four OpenAl Gym environments: CartPole, Pong, Acrobot and Mountaincar. For DRL agents, we use policy gradient model in CartPole, in other environments we use DQN (Mnih et al. 2015) (training parameters provided in appendix). The rewards obtained by the agents CartPole, Pong, Acrobot and Mountaincar are 200.00, 21.00. -68.60 and - 105.27, respectively (higher reward better). Rewards are averaged across 100 runs (250 in CartPole).
Comparison of MOËT, MOËT,, and Viper policies. For CartPole, Acrobot, and Mountaincar environments, we train Viper DT's with maximum depths of {1, 2, 3, 4, 5). while in the case of Pong we use maximum depths of {4, 6, 8, 10) as the problem is more complex and requires deeper trees. For experts in MOËT policies which we use depths to 9) and we train the policies for 2 to experts (in case of Pong we train for {2, 4, 8) experts). We train all policies using 40 iterations of Viper algorithm, and choose the
the same maximum depths as in Viper (except for Pong for

---

Under review as a conference paper at ICLR 2020
Table I: Comparison of Viper, MOËT, and МоËТ, on four environments. effective depth of Viper and MOËT models, R is of rewards (return), M mispredictions in comparison with the DRL agent, and C is a MoËT configuration (E number of experts, depth of each expert). and M values shown averaged across many trials (episodes), and furthermore averaged across multiple models trained with the same configuration.
Viper
MOËT M
MOËT₂ M
M
R
C
R
C
CartPole
181.76
30.43%
200.00
16.65%
200.00
0.84%
E2:D1
200.00
0.91%
E2:D1
200.00
11.04%
200.00
0.66%
E3:D1
200.00
0.61 %
E4:D1
200.00
6.87%
200.00
0.92%
E3:D2
200.00
0.80%
E4:D2
200.00
5.89%
200.00
0.93%
E3:D3
200.00
0.87%
E3:D3
Pong
-6.35
76.50%
6.05
76.48%
E8:D1
4.88
75.01 %
E4:D2
6
11.01
70.74%
15.20
70.44%
E2:D5
15.21
72.37%
E8:D3
15.96
68.12%
20.24
64.32%
E2:D7
19.13
66.12%
E8:D5
10
20.57
59.35%
20.70
56.78%
E2:D9
20.73
54.91%
E4:D8
Acrobot
-86.17
19.83%
-82,47
20.50%
E2:D1
-81.70
19.18%
E2:D1
-83.40
19.68%
-81.68
17.90%
E4:D1
-80.68
19.35%
E4:D1
-82.64
20.17%
-79.92
14.89%
E8:D1
-79.70
15.75%
E5:D1
-81.99
17.41%
-78.58
14.74%
E7:D2
-81.92
15.88%
E4:D3
Mountainear
-19.07
35.09%
-00.53
21.35%
E2:D1
-07.15
22.85%
E2:D1
109.82
24.12%
-01.27
14.86%
E3:D1
100.66
13.34%
E3:D1
-103553
9.19%
-99.67
8.04%
E4:D2
-00.36
7.08%
E2:D3
100.664
7.67%
-100.07
8.84%
E6:D2
-100.20
7.31%
E8:D2
best performing policy in terms rewards (and lower misprediction rate case equal rewards), We use two criteria to compare policies: rewards and mispredictions (number of times the student performs an action different from what teacher would do). High reward indicates that the student leareed more crucial parts of the teacher's policy, while low misprediction rate indicates that in most cases student performs the same action as the teacher. order to measure mispredictions, we run the student for number of runs, and compare actions it took to the actions teacher would perform.
To ensure comparable depths for evaluating Viper and MOËT models while accounting for the different number of experts in MOËT, we introduce the notion of effective depth of a MoËT model as [log, (E)1 D, where E denotes the number of experts and D denotes the depth of each expert. Table compares the performance of Viper, MOËT and MоËT,, The first column shows the depth of Viper decision trees and the corresponding effective depth for MOËT, rewards and mispredictions shown in R and M columns resp. We show results of the best performing MoËT configuration for a given effective depth chosen based on average results for rewards and mispredictions, where e.g. E3:D2 denotes 3 experts with DT's of depth 2. All results shown averaged across 10 run!]
For CartPole, Viper, MOËT and MoËT, all achieve perfect reward (200) with depths of and greater. More interestingly, for depth MOËT and MоËT, obtain significantly lower average mis- prediction rates of 0.84% and 0.91% respectively compared to 16.65% for Viper. Even for larger depths, the misprediction observe that MOËT and MoËT, consistently outperform Viper for all depths in terms of rewards and mispredictions, whereas MOËT and MOËT, have similar performance. For Acrobot, we simi- larly notice that both MOËT and MOËT, achieve consistently better rewards compared to Viper for all depths. Moreover, the misprediction rates are also significantly lower for MoËT and MoËT, in majority of the cases. Finally, for Mountaincar well, observe that MOËT and MоËT₁
for MOËT and MOšT, remain significantly lower. For Pong,
except for Pong which for 7 times hecause of high computational cost.

---

Under review as a conference paper at ICLR 2020
0.5
0.00
6G4
0.44
6/2
0.00
-.05
-000
(a) DRL agent policy.
(b) Viper policy,
(c) MOËT, policy.
142 -64
03
-33 -16 -00
09 92 64 -1B
04
(d) Viper mispredictions.
(e) МоËT, mispredictions.
(f) Difference in mispredictions.
Figure 2: Visualization of DRI, Viper, and MoËT, policies (up), and their differences (down) on Mountaincar environment. Upper images visualize policies, where left. neutral, and right actions are shown in green, yellow, and blue, respectively. Lower left 2 images visualize mispredictions compared to DRL agent shown in red, where more critical mispredictions are shown with higher intensity. Finally, image in the bottom right shows difference in mispredictions between Viper and МOËТ, (blue regions is where МOËT, is predicting correctly but Viper does not, and red the opposite, and color intensity denotes how critical the action is).
both consistently outperform Viper with significantly higher rewards and lower misprediction rates. Moreover, in both of these environments, we observe that both MoËT and MoËT, achieve compa- rable reward and misprediction rates. Additional results are presented in appendix.
Analyzing the learned Policies. We analyze the learned student policies (Viper and MOËT,) by visualizing their cate-nction space, the differences between them, and differences with the teacher policy. We use the Mountaincar environment for this analysis because the ease of visualizing its 2-dimensional state space comprising of car position (p) and car velocity (v) features, and 3 allowed actions left, right, and neutral. We visualize DRI,, Viper and MOËT, policies in Figure 2 showing the actions taken in different parts of the state space (additional visualizations are in appendix).
The state space is defined by feature bounds p E [-1.2, 0.6] and E [-0.07, 0.07]. which represent sets of allowed feature values in Mountaincar. We sample the space uniformly with resolution 200 x 200. The actions left, neutral, and right are colored in green, yellow, and blue, respectively. Recall that MOËT, cover regions whose borders are hyperplanes of arbitrary orientation, while Viper, i.e. DT can only cover regions whose borders are perpendicular to coordinate axes. This manifests in MoËT, policy containing slanted borders in yellow and green regions capture more precisely the geometry of DRL policy, while the Viper policy only contains straight borders.
Furthermore, we visualize mispredictions for Viper and MоËT, policies. While previous section we calculated mispredictions by using student policy for playing the game, in this analysis we vi- sualize mispredictions across the whole state space by sampling. Note that in some states (critical states) it is more important to get the action right, while in other states choosing non-optimal action does not affect the overall score much. Viper authors make use of this observation weight states by their importance, and they use difference between Q values of optimal and non-optimal actions as proxy for calculating how important (critical) state is. Importance score is calculated as follows: (s) max.eA Q(s, a) minae Q(s, a). where ((s, a) denotes the Q value of action in state s, and A is set of all possible actions. Using function we weight mispredictions by their importance.
We create a vector i consisting of importance scores for sampled points, and normalize it to range [0, 1]. We also create binary vector z which is in the case of misprediction (student policy decision is different from DRL decision) and 0 otherwise. We visualize multiplication). where higher value indicates misprediction of higher importance and is denoted by red color of higher intensity. Such normalized mispredictions (m) for Viper and MoËT, policies
@ (element- wisse
8

---

Under review as a conference paper at ICLR 2020
shown in Figure 2d and Figure 2e respectively. We observe that the MoËT, policy has fewer high intensity regions leading to fewer overall mispredictions.
To provide a quantitative difference between the mispredictions of two policies, compute M (Σ, mj/ E i,) 100, which is measure bounds [o, 100) such that its value is O in the case of no mispredictions, and 100 in the case of all mispredictions. For the policies shown in Figure 2 and Figure Ze] obtain M 15.51 for Viper and M 11.78 for MоËT, policies. We also show differences in mispredictions between Viper and MоËT, (Figure 2 by subtracting the m vector of MoËТ, from the vector of Viper. The positive values are shown in blue and the negative values are shown in red. The higher intensity blue regions denote states where MOËT, policy gets more important action right and Viper does not (similarly vice versa for high intensity red regions).
Translating MOËT to SMT. We now show the translation of MOËT policy to SMT con- straints for verifying policy properties. We present an example translation of MoËT policy on CartPole environment with the same property specification that was proposed for verify- ing Viper policies (Bastani et al.) 2018). The goal in CartPole is to keep the pole upright, which can be encoded where 8; represents state after i steps, & is the deviation of pole from the upright position. In order encode this formula it is necessary to encode the transition function fr fr a) which mod- els environment dynamics: given a state and action it returns the next state of the environment. Also, it is necessary to en- code the policy function т (s)) that for given state returns action to perform. There are two issues with verifying sh: (1) infinite time horizon; and (2) the nonlinear transition function fc. To solve this problem, Bastani et al. (2018) use finite time horizon Tmaz = 10 and linear approximation of the dynamics and we make the same assumptions.
formula: to = 8o E So A A ( (8)-1))) 1 yo-
320
250
110
100
Pexpprts
Figure 3: Verification times.
To encode T (s) we need to translate both the gating function and DT experts to logical formulas. Since the gating function in MoËT, uses exponential function, it is difficult to encode the function directly in 73 as SMT solvers do not have efficient decision procedures to solve non-linear arith- metic. The direct encoding of exponentiation therefore leads prohibitively complex 73 formulas. We exploit the following simplification of gating function that is sound when hard prediction is used:
exp(OT.x) xi ンー exp(O7)x)
arg mag(mxxxxp(((x))) = arg max x)
e = arg mAX
Σ E
First simplification is possible since the denominators for gatings of all experts are same, and second simplification is due to the monotonicity of the exponential function. For encoding DTs we use the same encoding as in Viper. To verify that holds we need to show that - unsatisfiable. We run the verification with our МоËТ, policies and show that - is indeed unsatisfiable.
To better understand the scalability of our verification procedure, we report on the verification times needed to verify policies for different number of experts and different expert depths in Figure 3 We observe that while MoËT, policies with 2 experts take from 2.68 to 8s for verification, verification times for 8 experts can go up to as much as 319s. This directly corresponds to the complexity of the logical formula obtained with an increase in the number of experts.
7 CONCLUSION
We introduced MOËT, technique based on MoE with expert decision trees and presented a learn- ing algorithm to train MOËT models. We then used MOËT models for interpreting DRL agent poli- cies, where different local DTs specialize on different regions of input space and are combined into a global policy using gating function. We showed that MoËT models lead smaller, more faithful and performant representation DRL agents compared to previous ontee-of-the-rr approaches like Viper while still maintaining interpretability and verifiability.
9

---

Under review as a conference paper at ICLR 2020
REFERENCES
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically Interpretable Reinforcement Learning. In International Conference on Ma- chine Learning, pages 5052 50611, 2018.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama Verifiable reinforcement learning via policy extraction. In Advances in Neural Information Processing Systems, pages 2499-2509, 2018.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc- tured prediction no-regret online learning. In Proceedings of the fourteenth international con- ference on artificial intelligence and statistics, pages 627-635, 2011.
Robert A Jacobs, Michael Jordan, Steven Nowlan, Geoffrey E Hinton, et al. Adaptive mixtures of local experts. Neural computation, 3(1):79 87, 1991.
Michael I Jordan and Lei Xu. Convergence results for the EM approach to mixtures of experts architectures. Neural networks, 119):1409-1431 1995.
Seniha Esen Yuksel, Joseph N Wilson, and Paul D) Gader. Twenty years of mixture of experts. IEEE transactions on neural networks and learning systems, 1779:1117 2012.
Ozan Irsoy, Olcay Taner Yıldız, and Ethem Alpaydın. Soft decision trees. In Proceedings of the 21st International Conference on Puttern Recognition (ICPR2012), pages 1819-1822. IEEE, 2012.
Wenbo Zhao, Yang Gao, Shahan Ali Memon, Bhiksha Raj, and Rita Singh. Hierarchical Routing Mixture of Experts. arXiv preprint 1903.09903.07766 2019.
Leonardo De Moura and Nikolaj Björner. 73: An efficient SMT solver. In International conference Tools and Algorithms for the Construction and Analysis of Systems, pages 337-340. Springer, 2008.
Zachary C Lipton. The mythos of model interpretability. arXiv preprint arXiv:1606.03490) 2016.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM computing surveys (CSUR), 51(5):93, 2018a.
Finale Doshi-Veles and Been Kim. Towards rigorous science of interpretable machine learning. arXiv preprint arXiv: htt:::/02..0000 2017.
Dumitru Erhan, Yoshua Bengio, Aaron Courville, and Pascal Vincent. Visualizing higher-layer features of a deep network. 2009.
Chris Olah, Alexander Mordvintsev, and Ludwig Schubert. Feature visualization. Distill, 2(11):e7, 2017.
Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, and Rory Sayres. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav). arXiv preprini 1711 12799 2017.
Xin Zhang, Armando
and Rishabh Singh. Interpreting neural network judgments via minimal, stable, and symbolic corrections. In Advances in Neural Information Processing Systems, pages 4874 2018.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. Advances in Neural Information Processing Systems, pages 592-603, 2018.
10

---

Under review as a conference paper at ICLR 2020
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Dino Pedreschi, Franco Turini, and Fosca Giannotti. Local rule-based explanations of black box decision systems. arXiv preprint 10X1::1805.10820. 2018b.
Cristian Bucilu, Rich Caruana, and Alexandru Niculescu-Mizii. Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 535-541. ACM, 2006.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge neural network. arXiv preprint MoXiv:1503.02553 2015,
Leo Breiman and Nong Shang. Born again trees. University of California, Berkeley, Berkeley, CA, Technical Report, 1:2, 1996.
Tommaso Furlanello, Zachary C Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. Born again neural networks. arXiv preprint arXiv: 044700 2018.
Andrei A. Rusu, Sergio Gomez Colmenarejo, Çaglar Gülçehre, Guillaume Desjardins, James Kirk- patrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy dis- tillation. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Anurag Koul, Alan Fern, and Sam Greydanus. Learning finite state representations of recurrent policy networks. In ICLR, 2019.
Amy Zhang, Zachary C. Lipton, Luis Pineda, Kamyar Azizzadenesheli, Anima Anandkumar, Lau- rent Itti, Joelle Pineau, and Tommaso Furlanello. Learning causal state representations of partially observable environments. CoRR, 2019.
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In ICML, 2004.
Stefan Schaal. Is imitation learning the route to humanoid robots? Trends in cognitive sciences, 1999.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 528(7540):52,,, 2015.
OpenAl Baselines. OpenAl Baselines.
/baaeeeea///aeeeeeeee base ines
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Marc Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. arXiv preprint 2015.
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5):834-846 1983.
Richard S Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. Advances in neural information processing systems, pages 1038-1044, 1996.
Andrew William Moore. Efficient memory-based based learning for robot control. 1990.
11

---

table tennis with two players. Minimum possible score is -21 and Under review as a conference paper at ICLR 2020
Algorithm 2 Viper training (Bastani et al. 2018)
1: procedure VIPER (MDP e, TEACHER Tt, Q-FUNCTION Q",, ITERATIONS N)
2:
Initialize dataset and student: D +- 0, Too + TT. 1 to N do
3: i
4:
Sample trajectories and aggregate: + ((s ~ d Sample dataset using Q values: D& {(s,a) =I=
5:
6: Train decision tree: Ts. + fit.treee tree(
7:
return Best policy E {Tss ... Tax)
A VIPER ALGORITHM
Viper algorithm is shown in Algorithm
B DRL AGENT TRAINING PARAMETERS
Here present parameters we used to train DRL agents for different environments. For CartPole, we use policy gradient model as used in Viper. While we use the same model, we had to retrain it from scratch as the trained Viper agent was available. For Pong, we use deep Q-network (DQN) network (Mnih et al. al. 2015). and we use the same model as in Viper, which originates from OpenAI baselines (OpenAl Baselines). For Acrobot and Mountaincar, we implement our own version of dueling DQN network following (Wang et al., 2015). We use 3 hidden layers with 15 neurons in each layer. We set the learning rate to 0,001, batch size to 30, step size to 10000 and number of epochs to 80000, We checkpoint model every 5000 steps and pick the best performing one in terms of achieved reward.
C ENVIRONMENTS
this section we provide a brief description of enviromments we used in our experiments. used four environments from OpenAl Gym: CartPole, Pong, Acrobot and Mountaincar.
C.1 CARTPOLE
This environment consists of a cart and a rigid pole hinged to the cart, based on the system presented by Barto al. (Barto al. 1983). At the beginning pole upright, and the goal is prevent from falling over. Cart is allowed to move horizontally within predefined bounds, and controller chooses apply either left or right force to the cart. State is defined with four variables: æ (cart position), (cart velocity), 9 (pole angle), and á (pole angular velocity). Game terminated when the absolute value of pole angle exceeds 12", cart position is more than 2.4 units away from the center, or after 200 successful steps; whichever comes first. each step reward of +1 given, and the game is considered solved when the average reward is over 195 in over 100 consecutive trials.
C.2 PONG
This is classical Atari game of maximum is 21.
C.3 ACROBOT
This environment is analogous gymnast swinging on horizontal bar, and consists of a two links and two joins, where the joint between the links is actuated. The environment is based on the system presented by Sutton (Sutton 1996). Initially both links are pointing downwards, and the goal is to swing the end-point (feet) above the bar for at least the length of one link. The state consists six variables. four variables consisting of sin and cos values of the joint angles, and two variables for angular velocities of the joints. The action is either applying negative, neutral, or positive torque on the joint. At each time step reward of is received, and episode is terminated upon successful
12

---

Under review as a conference paper at ICLR 2020
guking for
CA4
600
-0.8
-33
-16
-00
03
92
gkiight excert
C.99
2.22
-6.0
4.00
6.05
1.00
32
046 04
02
Figure 4: Visualization of gating function for different experts.
reaching the height, after 200 steps, whichever comes first. Acrobot is unsolved environment in that there no reward limit under which considered solved, but the goal is to achieve high reward.
C.4 MOUNTAINCAR
This environment consists of positioned between two hills, with goal of reaching the hill in front of the car. The environment is based on the system presented by Moore (Moore) 1990). Car can move in one-dimensional track, but does not have enough power to reach the hill one go, thus it needs to build momentum going back and forth to finally reach the hill. Controller can choose left, right or neutral action apply left, right or no force to the car. State defined by two variables, describing car position and car velocity. In each step reward of -1 is received, and episode is terminated upon reaching the hill, or after 200 steps, whichever comes first. The game considered solved if average reward over 100 consecutive trials is no less than -110.
D ADDITIONAL VISUALIZATIONS
In this section provide visualization of gating function. Figure shows how gating function partitions the state space for which different experts specialize. Gatings of MoËT, policy with experts and depth are shown.
13

---

Under review as a conference paper at ICLR 2020
Comparison of Viper, MOËT, and МоËТ, on four environments. effective depth of Viper and MOËT models, R is of rewards (return), M mispredictions in comparison with the DRL agent. Results shown are averaged across multiple trained models for Viper and MoËT. In addition, MoËT results averaged across multiple configurations that have the same effective depth.
Table 2:
Viper
MOËT
MoËT₂ R
D
R
M
M
CartPole
1
181.76
30.43%
%
2 200.00
16.65%
200.00
0.84%
200.00
0.91%
3
200.00
11.04%
200.00
0.87%
200.00
0.84%
4
200.00
6.87%
200.00
1.01%
200.00
0.96%
200.00 5
5.89%
200.00
1.16%
200.00
1.17%
Pong
4
-6.35
76.50%
3.03
74.48%
3.08
75.18%
6
11.01
70.74%
14.92
71.49%
12.66
72.59%
8
15.96
62%
18.50
64.74%
17.99
65.94%
20.57
59.35%
20.66
55.67%
20.29
52.81%
Acrobot
2
-86.17
19.83%
-82.47
20.50%
-81.70
19.18%
3
-83.40
19.68%
-82.45
19.34%
-81.79
19.52%
4 -82.64
20.17%
-82.36
17.61%
-81.52
17.37%
-81.99 5
17.41%
-82.44
16.16%
-83.57
17.44%
Mountaincar
2
-119.07
35.09%
-105.53
21.35%
-10.115
22.85%
3 -109.82
24.12%
-10.557
12.62%
-01.68
12.42%
4
-103.53
9.19%
-100.83
10.12%
10.03% 100.96
5
-102.64
7.67%
-101.06
8.03%
1100.69
7.73%
Table 3: Comparison of the best performing models for DRL, MoËT and MoËT,-
DRL
MOËT
МоËT,
CartPole
200
200
200
Pong
21
21
21
Acrobot
-68.60
-73.64
-73.31
Mountaincar
-105.27
-97.57
-97.59
E ADDITIONAL TABLES
Table shows results similar to Table 1 but here in addition to averaging results across multiple trained models, it averages results across multiple MoËT configurations that have the same effective depth.
Table 3 shows the results of best performing DRI,, MOËT and MoËT, models the evaluation subjects.
14

---

Under review as a conference paper at ICLR 2020
Table cartpole ViperPlus Evaluation
D
R
M
181.76
30.43%
2
200.00
16.65%
3
200.00
11.04%
4
200.00
6.87%
5
200.00
5.89%
Table 5: cartpole MOE Evaluation
M
2 200.00
0.84%
200.00
1.16%
2 200.00
1.04%
2
4
200.00
1.58%
2
5
200.00
2.44%
200.00
0.66%
3
200.00 3
0.92%
3
200.00
0.93%
3
4
200.00
1.37%
200.00
2.37%
200.00
0.80%
4 200.00
0.97%
4
3
200.00
0.96%
4
4
200.00
1.53%
4
199 96
2.71%
5
200.00
0.92%
5
200.00 3
1.02%
5
200.00
1.26%
5
4
200.00
1.97%
200.00
3.01%
6 200.00
0.99%
6
2
200.00
1.27%
6
3
200.00
1.17%
6 200.00
1.97%
6 200.00
2.68%
7
200.00
0.93%
7
2
200.00
1.07%
7
200.00
1.64%
200.00
2.67%
200.00
2.91%
8
1
200.00
1.29%
8
2
200.00
1.26%
8
200.00
1.57%
200.00
2.23%
8
200.00 5
3.27%
ABLATION RESULTS
In this section we show results for all DT depths and numbers of experts used for training Viper and
MOËT policies. Average mispredictions and rewards are shown for all configurations. Tables
show results for CartPole. Tables g show results for Pong. Tables 10 show results for Acrobot. Tables 13 15 show results for Mountaincar.
15

---

Under review as a conference paper at ICLR 2020
Table 6: cartpole MOEHard Evaluation
E
M
200.00
0.91%
2
200.00
0.98%
2
3
200.00
1.14%
2
200.00 4
1.34%
200.00
2.31%
3
200.00
0,93%
3
2
200.00
0.95%
3
3
200.00
0.87%
4
200.00
1.42%
200.00
2.48%
4
200.00
0.61%
4
2
200.00
0.80%
4
200.00 3
200.00
1.15%
4
1.86%
200.00
2.58%
5
200.00
0.92%
5
2
200.00
0.98%
5
200.00
1.31%
200.00
1.95%
200.00 00
3.17%
6 200 00
0.87%
6
2
200.00
1.02%
6
200.00
1.40%
200.00
2.10%
6 200.00
2.95%
7
I
200.00
0.90%
7 200.00
1.59%
7
200.00
1.36%
200.00
2.33%
7
5
200.00
3.30%
8
200.00
1.12%
8
2
200.00
1.26%
200.00
1.70%
8 200.00
2.57%
200.00 8
5
2.84%
Table 7: pong ViperPlus Evaluation
M
-6.35
76.50%
11.01
70.
8
15.96
68.12% 12%
10
20.57
59.35%
16

---

Under review as a conference paper at ICLR 2020
Table 8: pong MOE Evaluation
R
2
0.09
74.09%
15.20
70.44%
20.24
64.32%
2
9
20.70
56.78%
4
2
2.95
72.88%
4
14.70
70.27%
18.01
65.56%
4
8
20.65
56.72%
8
1
6.05
76.48%
8
14.84
73.77%
17.27
64.35%
20.62
53.52%
Table 9: pong MOEHard Evaluation
E
R
4.60
77.23%
2
7.64
74.29%
2
7
16.80
68.04%
2
9
19.51
56.33%
4
4.88
75.01% %
15.13
71.10%
4
6
18.04
63.66%
4
8
20.73
54.91
8
-0.23
73.31%
8
15.21
72.37%
19.13
66.12%
8
20.63 7
47.19%
Table 10: acrobot ViperPlus Evaluation
D
R
M
-6..77
19.83%
3
-83.40
19.68%
4
-82664
20.17%
-81.99
17.41%
17

---

Under review as a conference paper at ICLR 2020
Table 11: acrobot MOE Evaluation
D
R
M
-82.47
20.50%
2
-83.51
20.63% %
2
3
-85.61
19.45%
-84.22 4
16.97%
-82.22
15.49%
3
-82.17
19.48%
3
2
-82.34
19.79%
3
3
-83.69
17.47%
-86.89
17.93%
-82.88
15.13%
-81.68
17.90%
4
2
-82.22
17.92%
4
3
-4.28
16.91 %
84.36
16.34%
5
82.86
14.28%
5
-83.70
17.87%
5
2
-83.40
17.75%
-83.12
16.84%
85,50
15.53%
5
84.53
14.67%
81.22
17.49%
2
-82.74
15.07%
-84.07
16.23%
-22.64
13.52%
5
-84.55
13.75%
7
88.100
15.88%
-78.58
14.74%
84.00
16.07%
81.84
13.89%
7
5
84.96
13.19%
-7.922
14.89%
-80.19
14.23%
-83.27
15.39%
-81.61 5
12.77%
8
-82.58
13.28%
18

---

Under review as a conference paper at ICLR 2020
Table 12: acrobot MOEHard Evaluation
D
R
M
-81.70
19.18%
2
-83.61
19.68%
2
3
-82.01
19,42%
-83.86 4
19.37%
-85.60
18.11%
-81.08
19.52%
3
2
-82.71
19.77%
3
3
-86.51
20.72%
-83.92
17.50%
82.01
14.70%
80.68
19.35%
4
2
81.19
18.72%
4
-81.22 3
15.88%
-8.866
14.68%
84.64 5
15.66%
5
-9..70
15.75%
5
2
-84.37
18.84%
-85.08
17.87%
-2.42
14.58%
5
84.11
14.83%
81.51
16.88%
2
-83.27
16.37%
-85.06
15.77%
-83.52
13.84%
5
82.11
13.81%
7
-83.57
16.61%
-82477
15.50%
-85.09
17.11%
-81.71
12.82%
7
5
-2.86
13.24%
8
-79.96
14.47%
-82.56
15.41%
-82.39
15.31%
-22997 5
13.99%
8
84.50
13.17%
Table 13: mountaincar ViperPlus Evaluation
R
-11,007
35.09%
-109.82
24.12%
-103.53
9.19%
-102.64
7.67%
19

---

Under review as a conference paper at ICLR 2020
Table 14: mountaincar MOE Evaluation
R
-105.53
21.35%
-101.58
9.97%
-100.35
7.41%
-00.881
10.06%
104.60
6.92%
101.27
14.86%
100.51
7.95%
101.27
8.23%
103.95
8.91%
104.00
6.31%
-01.87
13.03%
4
.9.67
8.04%
100.65
7.39%
105.02
7.52%
103.49
6.39%
101.58
11.70%
5 100.50
6.63%
100.78
7.24%
103.93
8.36%
105.33
6.96%
101.01
10.73%
6 100.07
8.84%
101.45
7.50%
104.99
7.83%
104.60
6.92%
7
100.57
11.72%
100.79
7.69%
102.05
8.83%
104.44
7.21%
103.39
4.82%
102.15
13.32%
-00.36
7.40%
102.06
7.00%
105.07
6.48%
104.91 8
6.34%
20

---

Under review as a conference paper at ICLR 2020
Table 15: mountaincar MOEHard Evaluation
R
-107.15
22.85%
-102.37
12.27%
-100.36
7.08%
-10.33
7.97%
-00.40
7.10%
100.61
13.34%
100.79
8.10%
100.57
6.96%
100.77
7.61%
103.97
5,90%
102.06
11.65%
4
100.36
9.77%
101.17
7.89%
104.29
6.84%
104.21
5.65%
100.866
11.05%
5
-00.44
7.57%
101.27
7.59%
104.00
5,94%
104.16
4.70%
100.68
9.62%
6
100.60
8.56%
100.68
7.14%
104.92
6.97%
104.40
6.05%
100.59
11.8%%
100.522
7.84%
101.67
7.06%
102,81
5.27%
105.14
8.18%
103.09
12.71% %
-100.20
7.31%
101.41
6.69%
104.67
5.73%
105.80
4.69%
21


Reviews:
[{"review_id": "rJgr4h0jYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an extension to the Viper[1] method for interpreting and verifying deep RL policies by learning a mixture of decision trees to mimic the originally learned policy. The proposed approach can imitate the deep policy better compared with Viper while preserving verifiability. Empirically the proposed method demonstrates improvement in terms of cumulative reward and misprediction rate over Viper in four benchmark tasks.\n\nI tend to reject the paper in its current form because (1) the idea of using mixture of trees to do policy extraction is somewhat incremental; and (2) experiments do not consistently show significant performance gain over the existing approach.\n\n=============================================================================================\n\nNovelty and significance\n\nThe paper addresses an important problem in RL, trying to extract an interpretable and verifiable policy from a deep RL model. The novel aspect of the paper is employing a mixture of expert trees model instead of a single decision tree in Viper. The proposed method is somewhat incremental in the sense that it is equivalent to replacing the first layer of the hard decision tree with a soft decision layer, which enables learning a non-axis-align decision boundaries in the first layer. This is more like a small modification of the original method than a significant contribution.\n\nMoreover, in the experiments, the proposed method does not consistently show significant improvements over Viper. Of course one can expect some improvements over Viper because the proposed method is using more flexible model by employing a soft and non-axis-align decision layer. Besides, for Viper the comparison is not fair because it is comparing with the best performing mixture of expert trees model among many candidate structures. I would like to see how Viper compares with the average performance of different structures. \n\n=============================================================================================\n\nOther comments\n\nThe organization of this paper is good and the paper is easy to read. However the authors can improve the tables and figures by providing more descriptions to be more self-contained. For example, I don't know what the column labels in table 1 (D/R/M/C) are referring to by solely looking at the table. And their actual meanings are really hard to find in the text. And for figure 2, the authors should point out the meaning of colors inside the illustrations.\n\n\n\n\n\n\n[1] Bastani, Osbert, Yewen Pu, and Armando Solar-Lezama. \"Verifiable reinforcement learning via policy extraction.\" Advances in Neural Information Processing Systems. 2018.\n\nUpdate after rebuttal: score unchanged\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Skl_trsoFr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper suggests learning decision trees to learn policies that can be verified efficiently. The decision trees are learnt by imitation learning (DAGGER) and are guided by a DNN policy (called the oracle) and its Q-function. The paper is an extension of VIPER to mixture of Experts.\n\nThe paper does two contributions:\n- the modification of Viper to learn a mixture of decision tree policies that better mimics the DRL agent, and\n- the fact that the model based on Mixture of Experts is still interpretable.\n\nForm my understanding, it is known that mixture of experts can be more accurate than a single decision tree. I'm unsure about the importance of verifying experimentally that it is also the case in the context of DAGGER. Could you please expand on why using a mixture of experts in the context of DAGGER is challenging? I think that would be an important addition to the paper. That being said, the experimental results are of interest as they bring interpretability and verifiable RL to more challenging environments.\n\nMinor comments:\n- The notation \"EM\" that appears in the fourth paragraph of the introduction is not defined previously.\n- There a few typos: e.g., \"there do not exist\"\n- How many seeds are used for the \"average results (e.g. Appendix E)?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BygPnwlTtH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method (MOET) to distillate a reinforcement learning policy  represented by a deep neural network into an ensemble of decision trees. The main objective of this procedure is to obtain an \"interpretable\" and verifiable policy while maintaining the performance of the policy. The authors build over the previously published algorithm Viper (Bastani et al, 2018), which distillates deep policies into a single decision tree using the DAGGER procedures, i.e. alternation of imitation learning of an expert policy and of additional data-sampling from the newly learned policy. In the VIPER algorithm decision trees are chosen because their structured nature allows to formally prove properties of the policy they represent when the environments dynamics are known and expressible in closed form. \n\nThe main contribution of the paper is the adaptation of VIPER to ensembles of trees, specifically to mixtures of experts, and an adaption of the mixture of experts algorithm to non-differentiable experts. The mixture of experts is extended to decision trees with an em-like two step procedures that alternatively trains the experts and their input dependent weighting function. The main reason for extending VIPER to multiple trees is to increase the representation power of the procedure and obtain more faithful approximations of the original policy. The choice of using a input-dependent linear mixture of trees model instead of a more classical aggregation procedure like random-forests or xg-boosts is instead due to the assumed interpretability of input-dependent linear combinations.\n\nThe results in the paper seems to demonstrate comparable or improved performance of MOET over viper, but also show the systematic inability of both methods in imitating the actual neural network policy in all the environments but CARTPOLE. The authors conclude showing that the formal methods proposed to verify the policy in (Bastani et al, 2018) can be extended to MOET as they only rely on the choice of using decision trees as a target model.\n\nOn overall the paper creates a consistent narrative grounded on the notions that decision trees and linear models are interpretable, neural networks are not, individual decision trees can only create limited decision boundaries. The authors frame their technical contribution (em-like training of decision trees mixtures of experts) as necessary for creating more sophisticate decision boundaries through ensembling, while keeping the interpretability of the model (the ensembling method is linear and the components are decision trees).\n\nWhile the narrative is consistent and consequent technical work seems valid the paper has some flaws that put it in my opinion slightly below the acceptance threshold:\n\n1) The notions that linear models and decision trees have the \"interpretable\" propertiy is simply assumed as a known fact in the scientific field, while it is actually a largely discussed point of contention. See as an example \"Lipton 2017, The Mythos of Model Interpretability\". The authors should explain specifically what they mean by interpretability and how the properties of decision trees and linear mixtures of experts are consistent with their definition. \n\n2) On the overall paper (similarly to the narrative used for Viper) the authors speak of interpretability as if it was referred to the original deep neural network model while they only interpret the surrogate model. The lack of a formal definition of interpretable masks the problem of interpreting a model through the interpretation of a surrogate model, which would rely on some proof that links whatever is demonstrated on the surrogate to hold for the original model. \n\n3) The presentation of the results focus on the improvement of MOET with respect to VIPER. As a results it is difficult to compare the performance of both procedures to the original neural network model. For Pong and Acrobot the surrogate models do not achieve comparable performance, nor seems to be good imitations of the original policy, the reasons and the implication of this fact are not discussed.\n\n4) There should be a better connection with the knowledge distillation/model compression literature and in general the important idea that the same computation can be represented by different algorithms. (Born Again Trees, Model Compression, Distilling the Knowledge in a Neural Network, Policy Distillation, Born Again Neural Networks).  There is also some related novel literature mapping neural network policies and word models to minimal hidden-markov models that could be of interest to the authors (Learning Finite State Representations of Recurrent Policy Networks, Learning Causal State Representations of Partially Observable Environments). \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims at making a deep RL policy interpretable and verifiable by distilling the policy represented by a deep neural network into an ensemble of decision trees. This should be done without hurting the performance of the policy. The authors achieve this by extending the existing Viper algorithm. The resulting approach can imitate the deep policy better compared with Viper while preserving verifiability. Experiments show that the proposed method improves in terms of cumulative reward and error rate over Viper in four benchmark tasks.

The amount of improvement over the original Viper is not convincing given the presented results. Moreover, reviewers uniformly agree that the contribution of this work is incremental. I therefore recommend to reject this paper.
Decision: Reject