High-dimensional policies, such as those represented by neural networks, cannot be reasonably interpreted by humans. This lack of interpretability reduces the trust users have in policy behavior, limiting their use to low-impact tasks such as video games. Unfortunately, many methods rely on neural network representations for effective learning. In this work, we propose a method to build interpretable policy trees as surrogates for policies such as neural networks. The policy trees are easily human interpretable and provide quantitative predictions of future behavior. We demonstrate the performance of this approach on several simulated tasks.
Deep reinforcement learning has achieved state of the art
performance in several challenging task domains
Interpretability is important for high-consequence tasks. Domains in which neural networks have already been applied, such as image classification, often do not require interpretable decisions because the consequences of mislabeling images are typically low. In many potential applications of deep reinforcement learning, such as autonomous vehicle control, erroneous actions may be costly and dangerous. In these cases, greater trust in policy decisions is typically desired before systems are deployed.
Our work is motivated by tasks in which a human interacts directly with the policy, either by approving agent actions before they are taken or by enacting recommendations directly. This is often referred to having a human “in the loop”. An example is an automated cyber security incident response system that provides recommendations to a human analyst. In these cases, knowing the extended course of actions before committing to the recommendation can enhance the trust of the human operator.
It is difficult for humans to holistically interpret models
with even a small number of interacting terms
In this work, we propose a method to develop transparent surrogate models as local policy trees. The resulting trees encode an intuitive plan of future actions with performance comparable to the original policy. The proposed approach allows users to specify tree size constraints and fidelity targets. The method is model-agnostic, meaning that it does not require the original policy to take any specific form. Though this work was motivated by neural networks, the proposed approach may be used with any baseline policy form.
During execution of a tree policy, the actions taken by an agent are guaranteed to be along one of the unique paths from the root. Experiments on a simple grid world task highlight the impact of algorithm parameters on tree behavior. The experiments also show that using the trees as a recedinghorizon policy maintains good performance relative to the baseline model. Additional experiments on more complex infrastructure planning and cyber-physical security domains demonstrate the potential utility of this approach in realworld tasks.
Despite its importance in machine learning, there is no
precise qualitative or mathematical definition of
interpretability. In the literature, interpretability is commonly used to
describe a model with one of two characteristics. The first
is explainability, defined by
Techniques for model interpretability can vary greatly. We
characterize the methods presented in this work using the
taxonomy proposed by
The control tasks in this work are assumed to satisfy the
Markov assumption and may be modeled as either Markov
decision processes (MDPs) or partially observable Markov
decision processes (POMDPs). MDPs are defined by
tuples (S; A; T; r; ), where S and A are the state and
action spaces, respectively, T (s0 j s; a) is the transition model,
r(s; a; s0) is the reward function, and is a time discount
factor. POMDPs are modeled by the same tuple with the
addition of the observation space O and observation model
Z(o j s; a). A policy is a function that maps a state to an
action in MDPs or a history of observations to an action in
POMDPs. To solve a MDP is to learn the policy : S ! A
that maximizes the expected sum of discounted rewards
over all states. Learning an optimal policy is equivalent to
learning the optimal action value function
where is the optimal policy. When learning an action
value function estimator, the effective policy is
(s)
arg max Q^(s; a)
a2A
(3)
where Q^(s; a) is the learned approximator. These problems
can be solved using a variety of methods such as dynamic
programming, Monte Carlo planning, and reinforcement
learning
There has been a wealth of prior work in the field of
explainable and interpretable artificial intelligence. The book
by
A common technique for model-agnostic surrogate
modeling is to learn a surrogate model of an inherently
interpretable class. An useful example is locally interpretable
model-agnostic explanations (LIME)
Several methods have been proposed to distill neural
network policies to decision tree surrogates. Linear model
Utrees
Structural causal models (Madumal et al. 2020) also try to learn an inherently interpretable surrogate as a directed acyclic graph (DAG). The learned DAG represents relations between objects in the task environment that can be easily understood by humans. The DAG structure, however, must be provided for each task, and the fidelity is not assured.
Our work proposes tree representations that provide
intuitive maps over future courses of action. When used as a
policy, the realized course of action is guaranteed to be along
the branches of the tree. In this way, the method is similar to
methods of neural network verification that seek to provide
guarantees of network outputs over a given set of inputs.
The methods proposed in this work also resemble
Monte Carlo tree search (MCTS) algorithms
We present model-agnostic methods to represent policies for both MDPs and POMDPs as interpretable tree policies. Trees are inherently more interpretable than high dimensional models like neural networks. The proposed method uses the baseline policy to generate simulations of trajectories reachable from a given initial state. The trajectories are then clustered to develop a width-constrained tree that represents the original policy with low expected return loss. The methods assume that baseline policies return distributions over actions or estimates of action values for a given state. Building trees also requires a generative model of the task environment.
In addition to representing the future policy, the tree also provides useful statistics on expected performance such as likelihood of following each represented trajectory. The tree may be used as a policy during task execution with guarantees on expected behavior. We present methods to generalize to states not seen during tree construction by using the tree as a constraint on the baseline policy.
Before describing the tree construction algorithm, we first present the local tree policies that it produces. A policy tree is a rooted polytree where nodes represent actions taken during policy execution. An example tree policy for a stochastic, fully observable task is shown in fig. 1. Each node of the tree represents an action at taken at time t. The root action of each tree is the action recommended by the policy at the initial state. Each path from the tree root to a leaf node gives a trajectory of actions at; at+1; : : : ; at+h that the agent may take during policy execution up to some depth h. Trajectories leading to terminal conditions before h steps result in shallower tree branches.
Policy trees are interpretable representations of the future behavior of a policy that give explicit, quantitative predictions of future trajectories. Each node provides an estimate of the probability that the action sequence up to that node will be taken P (a0; : : : ; at j s0; ) and estimates of the policy value Q(s; a). Each node also contains a set of example states or observations that would result in that action.
Figure 2 provides more detailed views of the policy tree in fig. 1. The trajectory probabilities and value estimates shown in fig. 2a are calculated during tree construction and may be presented for any surrogate policy. The states in the example problem st 2 Rn are real vectors. Each node in fig. 2b shows the mean of that node’s state values. While the mean state value is useful for understanding this problem, it may not be useful in all problems. For example, the mean value may be meaningless for problems with discrete state spaces. Methods to compactly represent a node’s set of states or observations cannot be generally defined and instead should be specified for each problem.
Trees are an intuitive choice for the local surrogate model
of a control policy. Local surrogate methods seek to provide
simple approximate models that are faithful to the original
policy in a space around a target point. For control tasks,
often only predictions of future behavior are useful. Trees
provide compact surrogate models by only representing
behavior in states that are forward-reachable from the current
state. This is in contrast to methods that define local
neighborhoods by arbitrarily perturbing the initial point
Trees are built by simulating multiple executions of the baseline policy from the given initial state or belief and clustering them into action nodes. The process is illustrated in fig. 3. Each simulation is represented by a collection of particles pt for each time t along the simulation trajectory. Particles are tuples (st; rt) of the state at time t and reward received from t 1 to t. For POMDPs, particles also record the observation ot and belief bt.
Tree construction begins by first generating a set of particles for the initial state or belief. For the initial step, all particles are assigned to the root action node an0, which takes the action given by the baseline policy a0 = (s0) for MDPs or a0 = (b0) for POMDPs. The particles are then advanced through one simulation time step to produce the particles for t + 1, as shown in fig. 3a. The t + 1 particles that did not enter terminal states are clustered to new action nodes as shown in fig. 3b. This process continues until a terminal state is encountered or a fixed depth limit is met. Action nodes that do not have at least nmin particles are not expanded further to limit over-fitting, where nmin is specified by the user.
The point of entry for tree construction is the BUILD function, presented in algorithm 1 for MDPs. The initial particle set is created and clustered into the root action node. Each root particle for an MDP policy is initialized with the same state s0. Each action node is a tuple (P; a; Ch), where P is the node’s set of particles, a is the action taken from that node, and Ch is the set of child nodes. The BUILD function for POMDPs follows the same procedure as for MDPs, Action: City 4 Value: -0.44 Prob: 55.2 %
Action: City 5 Value: -0.43 Prob: 44.8 % Action: City 8 Value: -0.35 Prob: 34.4 %
Action: City 5 Value: -0.26 Prob: 20.8 %
Action: City 1 Value: -0.26 Prob: 20.7 %
Action: City 7 Value: -0.38 Prob: 24.1 %
Action: City 4 Average Infections:
City 1: 10.4% City 2: 8.5% City 3: 9.0% City 4: 11.6% City 5: 8.1% City 6: 33.3% City 7: 11.0% City 8: 4.1%
Action: City 5 Average Infections:
City 1: 7.2% City 2: 9.9% City 3: 9.2% City 4: 10.4% City 5: 10.9% City 6: 26.8% City 7: 14.8% City 8: 5.0% (a) (b) though states and observations for the initial particle set are sampled from the initial belief b0.
Algorithm 1: Build MDP 7: 8: 9: 10: 11: 1: procedure BUILDMDP(s0, , n, dmax) 2: P ; 3: Ch ; 4: d 0 5: for i 2 1 : n 6: P P [ f(s0; 0)g p0 (s0) a0 arg maxa2A (s0) root Node(P; a0; p0; Ch) root ROLLOUT(root; ; d) return root
Particles are advanced through recursive calls to the ROLLOUT function (algorithm 2). Each time ROLLOUT is called from an action node an, it proceeds if the size of the node particle set anP exceeds the minimum threshold and the depth limit dmax has not been exceeded. If these conditions are met, each particle is advanced by calling the simulator GEN(s; a) using that particle’s state and the node action. The set of new particles are then grouped into new action nodes by the CLUSTER function. ROLLOUT is recursively called on each new action node and the returned node is added to the child node set anCh.
The action nodes of the tree T encode a deterministic policy for the sampled particles, T : SR ! A, where SR is the set of states contained in the particle set. The particles are Algorithm 2: Rollout 1: procedure ROLLOUT(an, , d) 2: if janP j nmin and d < dmax 3: P ; 4: for p 2 anP 5: s ps 6: s0; o0; r0; done 7: if not done 8: p0 PARTICLE(s0; o0; r0) 9: P P [ fp0g
C CLUSTER(P; ) for c 2 C c0 ROLLOUT(c; ; d + 1) anch anch [ fc0g return node
GEN(s; ana) clustered into action nodes to minimize how much this policy deviates from the baseline policy while meeting constraints on tree size. To achieve this, we developed a clustering algorithm that approximately solves for the optimal clustering through recursive greedy optimization.
The recursive clustering approach is presented in algorithm 3. The algorithm progressively clusters particles into an increasing number of nodes k until a distance measure between the actions assigned by the tree and the baseline policy is less than a threshold or the maximum number of nodes cmax is exceeded.
Clusters are assigned according to a greedy heuristic process shown in algorithm 4. In this approach, the complete set t = 1 t = 2
GREEDYCLUSTER(P; k; ) k + 1
or jCj cmax of actions assigned to each particle under the baseline policy AU is ranked according to frequency by the UNIQUEACTIONS function. Action nodes for each of the top k actions and all particles assigned that action by the baseline policy are clustered. Any particles not clustered to a node at the end of this process are assigned to the previously formed node that minimizes the distance between that action and the action assigned by the baseline policy.
Algorithm 4: Greedy Cluster 1: procedure GREEDYCLUSTER(P , k, ) 2: C ; 3: 0 4: AU UNIQUEACTIONS(P; ) 5: for i 2 1 : k 6: a AU [i] 7: P A 8: C 9: P
fp 2 P j arg maxa2A fNODE(P A; a; ;)g [ C
P n P A To use the tree as a policy during task execution, it must be able to generalize to states not encountered in the particle set of the tree. To do this, we propose a simple method that uses the baseline policy, constrained by the tree at each time step. For a tree constructed for a state s0, the policy will always take the action at the root node an0. For all remaining steps, the policy will return a arg max a02AT (st) where AT is the set of actions in the child set of the preceding action node ant 1. Intuitively, the agent will take the best action predicted by the baseline policy that is included in the tree. Building a new tree each time a leaf state is encountered allows the tree policies to be run in-the-loop for long or infinite-horizon problems.
We ran experiments to test the performance of the proposed approach. One set of experiments are conducted on a simple grid world task. These experiments were designed to quantitatively measure the effect of various algorithm parameters and environment features on tree size and performance. Two additional experiments were run on more complex tasks that (4) (5) demonstrate the utility of the approach on real-world motivating examples. The first of these is multi-city vaccine deployment planning. In large-scale infrastructure planning tasks such as this, it is often necessary to have a reasonable prediction of all steps of the plan in order to gain stakeholder trust. The second task is a cyber security agent that provides recommendations to a human analyst to secure a network against attack. Interpretable policies are important for tasks with human oversight and cooperation.
We implemented the proposed algorithm with the distance
function defined in eq. (4) in Python. Neural network
training was done in PyTorch
In the grid world task, an agent must navigate a discrete, 2D
world to reach a goal state while avoiding trap states. The
agent may take one of n total actions to move between 1 and
n
b 4 c units in any of the four cardinal directions on the grid.
The agent moves in the intended direction with probability p
and takes a random action otherwise. To incentivize solving
the problem quickly, the agent receives a cost of 1 at each
time step. The agent gets a positive reward of +10 for
reaching a goal state and a penalty of 5 for reaching a trap state.
The episode terminates when the agent reaches a goal state
or when a maximum number of steps is reached. Because we
know exact transition probabilities, we used discrete value
iteration to learn a baseline policy
We constructed surrogate trees from the baseline policy using various environment and tree-build algorithm settings. For the environment, we swept over different values of the transition probability p and the number of actions n. For the tree build algorithm, we varied the total number of particles, the minimum particle count, the distance threshold , and the maximum leaf node depth. Only one parameter was varied for each test, with all others held fixed. The baseline settings for the environment were n = 4 actions and a successful transition probability of p = 0:9. The baseline tree build parameters are 1000 total particles, 250 minimum particles, distance threshold of 0.01, and maximum depth of 10.
To test each tree, we ran it as a policy from the initial state until it reached a leaf node. The baseline policy was then used to complete the episode. We tested 2,500 trees for each parameter configuration. Select results are shown table 1. The mean change in performance of the tree policy relative to the baseline is shown along with one standard error bounds. The average depth of leaf nodes is also shown, though standard error is omitted as each had SE < 0:05.
From the transition probability sweep, we see that relative performance generally improves as transition probability increases. At p = 0:5, both policies perform very poorly and the difference between the two is not significant as a result. In the deterministic case, the surrogate tree perfectly represents the baseline policy. These results suggest that surrogate trees are better suited for tasks with low stochasticity.
As we increase the number of actions, the difference in performance between the baseline and the tree policy decreases. The average leaf depth of the trees also decreases
with more actions. This likely explains the improved performance, as shallower trees will transition back to the baseline policy sooner in the tests. Another possible explanation is that as the number of actions grows, the cost of taking a suboptimal action decreases. For example, with 4 actions, if the optimal action is not taken, then the agent moves in a completely different direction than it should. With n > 4 actions, the agent may still move in the correct direction, though by more or less distance than optimal.
For the tree building algorithm parameters, we see that as increases, the depth of the leaf nodes also decreases. This is likely because higher values of leads to more aggressive node clustering and fewer branches. Similar to the trend observed by varying the number of actions, as the average leaf depth decreases, relative performance increases. Similarly, as the max depth increases, the tree is allowed to grow deeper and the relative performance drops.
In the vaccine deployment task, an agent decides the order
in which to start vaccine distributions in cities in the midst
of a pandemic outbreak. Each step, the agent picks a city
in which to start a vaccine program. The spread of the
disease is modeled as a stochastic SIRD model
I~t(i)St(i) t(i)St(i) + tS;(i) I~t(i)St(i) + tS;(i) It(i)
I(i) t dRt(i) = I(i) + t t(i)S(i)
t dDt(i) = I(i) t (6) (7) (8) (9) where , , and are the mean infection, recovery, and death rates, respectively. The vaccination rate t(i) of city i at time t and is equal to zero until an action is taken to deploy a vaccination program to that city. The noise is sampled from a zero mean Gaussian. The effective infection exposure at city i is defined as I~(i) = Pj wij Ij , where the sum is taken over all cities, and wii = 1. Cities with closer index values will have higher weights, for example w12 > w13.
Each episode is initialized with up to 10% of each city infected and the remainder susceptible. One city is initialized with 25% infected. The episode concludes after five cities have had vaccine programs started. The simulation is then run until all cities have zero susceptible or infected population. The reward at each time step is rt = a Pi dIt(i) + b P dDt(i), where a and b are parameters.
i
We trained a neural network policy using double
DQN
The surrogate tree in fig. 2 provides an intuitive understanding of the learned policy. In fig. 2b we can see that the policy does not deploy vaccines to the most heavily infected cities first. It instead prioritizes cities with larger susceptible populations to give the vaccine time to take effect on a larger amount of the population.
The cyber security task requires an agent to prevent unauthorized access to secure data server on a computer network. The computer network is comprised of four local area networks (LANs), each of which has a local application server and ten workstations, and a single secure data server. The compromise state of the network is not known may be observed through noisy alerts generated from malware scans. Workstations are networked to all others on their LAN and to the LAN application server. Servers are randomly connected in a complete graph. An attacker begins with a single workstation compromised and takes actions to compromise additional workstations and servers to reach the data server.
The defender can scan all nodes on a LAN to locate
compromised nodes with probability pdetect. Compromised
nodes will also generate alerts without being scanned with
low probability. The defender can also scan and clean
individual nodes to detect and remove compromise. The reward
is zero unless the data server is compromised, in which case
a large penalty is incurred. The defender was trained using
Rainbow DQN
Automated systems such as this are often implemented with a human in the loop. Policies that can be more easily Scan LAN 2 Value: -0.35 Prob: 100.0 % Mode Observation:
Alert: Host Detection LAN: 2 IP: 192.168.2.6
Clean Host (2,6) Value: -0.25 Prob: 62.5 %
Scan LAN 1 Value: -0.26 Prob: 37.5 % interpreted are more likely to be trusted by a human operator. A surrogate tree for the neural network is shown in fig. 4. Unlike the baseline neural network, the policy encoded by this tree can be easily interpreted. The agent will continually scan LAN 1 in most cases, and will only clean a workstation after malware has been detected.
In this work, we presented methods to construct local surrogate policy trees from arbitrary control policies. The trees are more interpretable than high-dimensional policies such as neural networks and provide quantitative estimates of future behavior. Our experiments show that, despite truncating the set of actions that may be taken at each future time step, the trees retain performance comparable to their baseline policies. Experiments demonstrate the effect of various environment and algorithm parameters on tree size and performance in a simple grid world. Demonstrations show how surrogate trees may be used in more complex, real-world scenarios.
The action node clustering presented in this work used
a heuristic search method that provided good results, but
without any optimality guarantees. Future work will look at
improved approaches to clustering, for example by using a
mixed integer program optimization. We will also explore
using the scenarios simulated to construct the tree to backup
more accurate value estimates, and refine the resulting
policy. Including empirical backups such as these may also
allow calculation of confidence intervals or bounds on policy
performance