Ranking Policy Decisions
Year: 2021

Abstract:
Policies trained via Reinforcement Learning (RL) are often needlessly complex, making them difficult to analyse and interpret. In a run with n time steps, a policy will make n decisions on actions to take; we conjecture that only a small subset of these decisions delivers value over selecting a simple default action. Given a trained policy, we propose a novel black-box method based on statistical fault localisation that ranks the states of the environment according to the importance of decisions made in those states. We argue that among other things, the ranked list of states can help explain and understand the policy. As the ranking method is statistical, a direct evaluation of its quality is hard. As a proxy for quality, we use the ranking to create new, simpler policies from the original ones by pruning decisions identified as unimportant (that is, replacing them by default actions) and measuring the impact on performance. Our experiments on a diverse set of standard benchmarks demonstrate that pruned policies can perform on a level comparable to the original policies. Conversely, we show that naive approaches for ranking policy decisions, e.g., ranking based on the frequency of visiting a state, do not result in high-performing pruned policies.

heading: 1 Introduction
text: Reinforcement learning is a powerful method for training policies that complete tasks in complex environments. The policies produced are optimised to maximise the expected reward provided by the environment. While performance is clearly an important goal, the reward typically does not capture the entire range of our preferences. By focusing solely on performance, we risk overlooking the demand for models that are easier to analyse, predict and interpret [16]. Our hypothesis is that many trained policies are needlessly complex, i.e., that there exist alternative policies that perform just as well or nearly as well but that are significantly simpler. This tension between performance and simplicity is central to the field of explainable AI (XAI), and machine learning as a whole [11]; our method aims to help by highlighting the most important parts of a policy.
∗The work in this paper was done while at the University of Oxford. †The work in this paper was done prior to joining Amazon.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The starting point for our definition of “simplicity” is the assumption that there exists a way to make a “simple choice”, that is, there is a simple default action for the environment. We argue that this is the case for many environments in which RL is applied: for example, “repeat previous action” is a straightforward default action for navigation tasks.
The key contribution of this paper is a novel method for ranking policy decisions according to their importance relative to some goal. We argue that the ranked list of decisions is already helpful in explaining how the policy operates. We evaluate our ranking method by using the ranking to simplify policies without compromising performance, hence addressing one of the main hurdles for wide adoption of deep RL: the high complexity of trained policies.
We produce a ranking by scoring the states a policy visits. The rank reflects the impact that replacing the policy’s chosen action by the default action has on a user-selected binary outcome, such as “obtain more than X reward”. It is intractable to compute this ranking precisely, owing to the high complexity and the stochasticity of the environment and the policy, complex causal interactions between actions and their outcomes, and the sheer size of the problem. Our work uses spectrum-based fault localisation (SBFL) techniques [20, 31], borrowed from the software testing domain, to compute an approximation of the ranking of policy decisions. SBFL is an established technique in program testing for ranking the parts of a program source code text that are most likely to contain the root cause of a bug. This ranking is computed by recording the executions of a user-provided test suite. SBFL distinguishes passing and failing executions; failing executions are those that exhibit the bug. Intuitively, a program location is more likely to be the root cause of the bug if it is visited in failing executions but less (or not at all) in passing ones. SBFL is a lightweight technique and its rankings are highly correlated with the location of the root cause of the bug [31]. We argue that SBFL is also a good fit for analysing complex RL policies.
Our method applies to RL policies in a black-box manner, and requires no assumptions about the policy’s training or representation. We evaluate the quality of the ranking of the decisions by the proxy of creating new, simpler policies (we call them “pruned policies”) without retraining, and then calculate the reward achieved by these policies. Experiments with agents for MiniGrid (a more complex version of gridworlds) [7], CartPole [4] and a number of Atari games [4] demonstrate that pruned policies maintain high performance (similar or only slightly worse than that of the original policy) when taking the default action in the majority of the states (often 90% of the states). As pruned policies are much easier to understand than the original policies, we consider this an important step towards explainable RL. Pruning a given policy does not require re-training, and hence, our procedure is relatively lightweight. Furthermore, the ranking of states by itself provides important insight into the importance of particular decisions for the performance of the policy overall.
The code for reproducing our experiments is available on GitHub3, and further examples are provided on the project website4.

heading: 2 Background

heading: 2.1 Reinforcement learning (RL)
text: We use a standard reinforcement learning (RL) setup and assume that the reader is familiar with the basic concepts. An environment in RL is defined as a Markov decision process (MDP) and is denoted by 〈S,A, P,R, γ, T 〉, where S is the set of states, A is the set of actions, P is the transition function, R is the reward function, γ is the discount factor, and T is the set of terminal states. An agent seeks to learn a policy π : S → A that maximizes the total discounted reward. Starting from the initial state s0 and given the policy π, the state-value function is the expected future discounted reward as follows:
Vπ(s0) = E ( ∞∑ t=0 γtR(st, π(st), st+1) ) (1)
A policy π : S → A maps states to the actions taken in these states and may be stochastic. We treat the policy as a black box, and hence make no further assumptions about π.
3https://github.com/hadrien-pouget/Ranking-Policy-Decisions. Experiments done at commit c972414 4https://www.cprover.org/deepcover/neurips2021/

heading: 2.2 Spectrum-based fault localization (SBFL)
text: The reader is likely less familiar with spectrum-based fault localization (SBFL), as to the best of our knowledge, it has not yet been used in RL. We therefore give a detailed description. SBFL techniques [31] have been widely used as an efficient approach to aid in locating the causes of failures in sequential programs. SBFL techniques rank program elements (say program statements) based on their suspiciousness scores, which are computed using correlation-based measures. Intuitively, a program element is more suspicious if it appears in failed executions more frequently than in correct executions, and the exact formulas differ between the measures. Diagnosis of the faulty program can then be conducted by manually examining the ranked list of elements in descending order of their suspiciousness until the cause of the fault is found. It has been shown that SBFL techniques perform well in complex programs [2].
SBFL techniques first execute the program under test using a test suite. A test suite comprises of a set of inputs and an expected output for each input. A test passes when the output produced by the program under test matches the expected output given by the test suite, and has failed otherwise. In addition to the outcome of the test, SBFL techniques record the values of a set of Boolean flags that indicate whether a particular program element was executed by that test.
The task of a fault localization tool is to compute a ranking of the program elements based on the values of the Boolean flags recorded while executing the test suite. Following the notation from [20], the suspiciousness score of each program statement s is calculated from a set of parameters 〈asep , asef , asnp , asnf 〉 that give the number of times the statement s is executed (e) or not executed (n) on passing (p) and on failing (f ) tests. For instance, asep is the number of tests that passed and executed s.
Many measures have been proposed to calculate the suspicious scores of program elements. In Equations (2a)∼(2d) we list a selection of popular and high-performing measures [1, 9, 15, 30]; these are also the measures that we use in our ranking procedure.
Ochiai: asef√
(asef + a s nf )(a s ef + a s ep)
(2a) Tarantula:
asef asef +a s nf
asef asef +a s nf + asep asep+a s np
(2b)
Zoltar: asef
asef + a s nf + a s ep +
10000asnf a s ep
asef
(2c) Wong-II: asef − asep (2d)
SBFL-based tools present the list of program elements in descending order of their suspiciousness scores to the user. There is no single best measure for fault localization; different measures perform better on different types of programs, and it is best practice to use multiple measures [18]. In our experiments, we combine the four measures listed above for this very reason.
While more sophisticated versions of SBFL exist [3, 5], in this work we prefer to stick to the simpler approach, which was sufficient for producing notable results.

heading: 3 Method: ranking policy decisions using SBFL
text: Inspired by the use of SBFL for localising the cause of a program’s outcome, we propose a new SBFL-based method to identify the states in which decisions made by an RL policy are most important for achieving its objective. Our method is modular and is composed of two phases: (1) generating mutant policies and (2) ranking states based on the importance.

heading: 3.1 Definitions
text: Executions of RL policies We apply the SBFL technique to a set of executions (sometimes called trajectories in the literature) of a given RL policy π with mutations. An execution τ of π describes a traversal of the agent through the environment MDP using the RL policy π and is defined as a sequence of states s0, s1, . . . and actions a0, a1, . . ., where s0 is an initial state and each subsequent state si+1 obtained from the previous state si by performing action ai, as chosen using π(si). The last state must be a terminal state. As π or the environment can be stochastic, each execution of π may result in a different sequence of actions and states, and hence in a different τ . The set of all possible executions is denoted by T . A decision of a policy π in a state s is a pair 〈s, π(s)〉. Note that π(s) is the learned probability distribution from which an action in this state is obtained; in a deterministic policy, π(s) is a single action for each s.
Passing and failing executions An execution is either successful or failed. We define the success of an execution as a (binary) value of a given assertion on this execution. For example, the assertion can be that the agent reaches its destination eventually, or that the reward of this execution is not lower than 0.75 of the maximal reward for π. The assertion induces a Boolean function C : T → {0, 1}. We say that an execution τ is a pass if C(τ) = 1, and is a fail otherwise. We use a binary condition for simplicity, as SBFL is designed to work with passing and failing executions. This condition can be relaxed [5], and we plan to investigate generalising this in future work.
Mutant executions We use SBFL to understand the impact of replacing actions by a default action. The choice of the default action d is context dependent and can be configured by the user. For example, an obvious default action for navigation is “proceed in the same direction”. The default action can in principle be as basic as a single action, or as complex as a fully-fledged policy. In our experiments, we evaluate two default actions. The first is “repeat the previous action”, defined as:
d(s0, . . . , si, a0, . . . , ai−1) = ai−1, (3)
and the second is “take a random action”. For A being the action space,
d(s0, . . . , si, a0, . . . , ai−1) = asi ∼ Unif (A). (4)
Once asi has been sampled, it is not re-sampled if the state si is revisited; the same action is used. Using “take a random action” as the default action can be useful in cases where there is no other obvious default action. However, we generally expect this to be a worse option than a default action tailored to the environment. As the choice of d depends on the context and the user’s goals, it is ultimately a user choice.
Using the default action, we create mutant executions, in which the agent takes the default action d whenever it is in one of the mutant states. More formally, given a set of mutant states SM , we act according to the policy πSM defined as:
πSM (s0, . . . , si, a0, . . . , ai−1) = { π(si) si /∈ SM , d(s0, . . . , si, a0, . . . , ai−1) si ∈ SM .
(5)
Decisions made in states in which the default action is a very good option are deemed less important. In these states, not following the policy would be less consequential.

heading: 3.2 Generating the test suite and mutant executions on-the-fly
text: The naïve approach to generating a comprehensive suite of mutant executions for applying SBFL would be to consider all possible sets of mutant states SM—that is, we would need to consider all possible subsets of the state space S. However, the state space of most RL environments is too large to enumerate, and enumerating all possible subsets of S is intractable even for simplistic environments.
We use two algorithmic techniques to address this problem: (a) we generate mutant executions on-the-fly, and (b) we use an abstraction function α : S → Ŝ to map the full set of states S to a smaller, less complex set of abstract states Ŝ. Examples of these are in the supplementary material, and may for example include down-scaling or grey-scaling images that are input to the agent, or quantising a continuous state space. The set of possible mutations is then the set of subsets of Ŝ, instead of the set of subsets of S. We then score the abstract states, rather than the full state space. The test suite of mutant executions produced this way for π is denoted T (π) ⊆ T .
On-the-fly mutation We maintain a set SM ⊆ Ŝ per execution. We begin each execution τ by initialising the set SM with the empty set of states. At each step of the execution, upon visiting a state s, we check the current SM . If α(s) 6∈ SM , we add α(s) to SM according to the predefined mutation rate µ (and take the default action); otherwise, we use π to determine the action in this state. In case we re-visit an (abstract) state, we maintain the previous decision of whether to mutate state s or not. This way, the states that are never visited in any of the executions are never mutated; hence, we never consider “useless mutations” that mutate a state that is never visited. We finish by marking τ as pass or fail according to C(τ). Note that a mutant execution may visit states not typically encountered by π, meaning that we are even able to rank states that are out of distribution. This is especially important when trying to understand how the policy behaves in parts of the environment it is unfamiliar with.
Overall, our algorithm has five (tunable) parameters: the size of the test suite |T (π)|, the passing condition C, the default action d, the mutation rate µ and the abstraction function α.
SBFL benefits from a balanced test suite of passing and failing executions [31], a ratio largely determined by the choices of µ and C. The choice of C depends on the context. In our experiments in Section 4.3, our goal was to find the states with highest impact on the expected reward. We set the condition to be “receive more than X reward" for some X ∈ R, and chose X to yield a balanced suite (i.e. if there were too many failed runs, we lowered X). In most cases actions important for achieving at least X reward are important for maximising reward in general, so we found that this worked well. In the cases where some actions are not important for achieving X , but later important for getting even higher rewards (e.g., states that only appear after achieving X reward), we would not have considered them important. The choice of µ is also significant. If it is too large, executions fail too often, and the behaviour in mutant executions is uninteresting. If µ is too small, we do not mutate states enough to learn anything, and in larger environments fail to mutate many of the states we encounter. In our experiments, we selected µ manually, but this could easily be automated by a parameter tuning algorithm.

heading: 3.3 Computing the ranking of the policy decisions
text: We now explain how to rank states according to the importance of policy decisions made in these states, with respect to satisfying the condition. The ranking method is based on SBFL as described in Section 2.2. We first create the test suite of mutant executions T (π) as described above. We denote the set of all abstract states encountered when generating the test suite ST ⊆ Ŝ; these are the states to which we assign scores. Any unvisited state is given the lowest possible score by default.
Similarly to SBFL for bug localisation, for each state s ∈ ST we calculate a vector 〈asep , asef , asnp , asnf 〉. We use this vector to track the number of times that s was unmutated (e) or mutated (n) on passing (p) and on failing (f ) executions, and we update these scores based on those executions in which the state was visited. In other words, the vector keeps track of success and failure of mutant executions based on whether an execution took the default action in s or not. For example, asep is the number of passing executions that took the action π(s) in the state s, and a s nf is the number of failing executions that took the default action in the state s.
Definition 1 (Ranking). Given an SBFL measure m and a vector 〈asep , asef , asnp , asnf 〉 for each (abstract) state s in the set Ŝ of (abstract) states of the policy, we define the ranking function rank : Ŝ → {1, . . . , |Ŝ|} as the ordering of the states in Ŝ in the descending order according to the values m(s); that is, the state with the maximal value will be the first in the ranking.

heading: 4 Experimental evaluation

heading: 4.1 Research Questions
text: Our goal is to demonstrate the applicability of our ranking method to a variety of standard environments and to provide evidence of the utility of the generated ranking. We aim to answer the following research questions:
RQ1: How can we measure the relative importance of decisions for achieving the reward? What is a good proxy for measuring this?
RQ2: Does the approach we present in this paper scale to large policies and complex environments?
We answer these questions in Section 4.3 by performing extensive experiments with various environments and policies. In Section 4.4, we discuss possible applications of our ranking (including interpretability), and the effect of choosing a different default action.

heading: 4.2 Experimental setup
text: We experimented in several environments. The first is Minigrid [7], a gridworld in which the agent operates with a cone of vision and can navigate many different grids, making it more complex than a standard gridworld. In each step the agent can turn or move forward. We also used CartPole [4], the classic control problem with a continuous state-space. Finally, to test our ability to scale, we ran experiments with Atari games [4].
We use policies that are trained using third-party code. No state abstraction is applied to the gridworld environments (i.e., α is the identity). The state abstraction function for the CartPole environment consists of rounding the components of the state vector between 0 and 2 decimal places, and then taking the absolute value. For the Atari games, as is typically done, we crop the game’s border, grey-scale, down-sample to 18×14, and lower the precision of pixel intensities to make the enormous state space manageable. Note that these abstractions are not a contribution of ours, and were primarily chosen for their simplicity. For our main experiments, we use “repeat previous action” as the default action.
Examples of some environments, and important states found in them, are given in Figs. 1a and 1b. Details about the state abstraction functions, policy training, hyperparameters, etc., are provided in the full version of this paper [22].
We define two further measures in addition to the SBFL ones in Eq. (2), for comparison. Eq. (6a) measures how frequently the state was encountered in the test suite. Eq. (6b) is a random ranking of the states visited by the test suite. We use the FreqVis measure as a baseline because we are not aware of any previous work with the same goals as ours for ranking policy decisions, and a naïve approach to determining importance may be simply looking at how frequently a state is visited.
FreqVis: asep + a s ef + a s np + a s nf (6a) Rand: ∼ Unif(0, 1) (6b)

heading: 4.3 Experimental results
text: Performance of pruned policies The precise ranking of decisions according to their importance for the reward is intractable for all but very simple policies. To answer RQ1, in our experiments, we use the performance of pruned policies as a proxy for the quality of the ranking computed by our algorithm. In pruned policies, the default action is used in all but the top ranked states. For a given r (a fraction or a percentage), we denote by rank [r] the subset of r top-ranked states. We denote by πr the pruned policy obtained by pruning all but the top-r ranked states. That is, an execution of πr retains actions in the r fraction of the most important states from the original policy π and replaces
the rest by default actions. The states that are in rank [r] are called the original states. We measure the performance of the pruned policies for increasing values of r relative to the performance of the original policy π.
These results are given in first four columns of Tab. 1, and some are represented graphically in Figs. 2a,c. In these, SBFL stands for the SBFL portfolio, i.e., the combination of the four measures in Eq. (2), where the best result is taken at each point. The results show that the pruned policies obtained using the SBFL ranking can achieve performance that is comparable to π with less than 40% of the original decisions (and in some cases the number is as low as 20%). The performance of SBFL-based pruning is compared with random pruning in Eq. (6b) and FreqVis pruning in Eq. (6a). At first glance, it seems that the FreqVis pruned policies perform well in Figs. 2a,c. To better understand this, we show in the last two columns of Tab. 1 and in Figs. 2b,d how performance evolves with the proportion of steps in which the original policy is used over the default policy (i.e. not replaced by the default action). As shown in Figs. 2b and 2d, FreqVis does much worse by this metric, because it yields a pruned policy that prefers to use the original policy as often as possible.
We observe that using our ranking method enables a significant pruning of the policies, while maintaining performance. To answer RQ2, we experimented with larger and more complex Atari environments. The results demonstrate that our framework is reasonably scalable, but also that the quality of the ranking is significantly improved by using a state abstraction. The results in the larger and more complex Atari environments show the effect of using a test suite that is too small: many states are not encountered during the computation of the ranking. This means that rank [1], in which the original policy is used in all of the states discovered while making the ranking, does not recover the performance of the original policy. Increasing the size of the test suite would help, but this is not a scalable solution. Instead, we use better state abstractions, which reduce the state space. In CartPole, this allows us to tackle a continuous domain. In the Atari games, even the generic abstraction we use in all the games is sometimes not enough (“x” in Tab. 1).
To show the potential utility of specialised abstractions, we create one for Breakout in which we extract the coordinates of the ball and paddle. The results obtained with this abstraction are given in Tab. 1 in the row labelled “Breakout (abs)”. While the new abstraction does worse in terms of states
pruned within the policy, it allows us to reach 90% of the policy’s original performance with 13% fewer steps in which we use π over the default action.

heading: 4.4 Discussion
text: SBFL ranking for better understanding the RL policy Any strong claim about the ranking’s application to interpretability requires a user study, which is out of scope of this paper. However, we can look to existing research looking at the usefulness of SBFL. While some studies suggest that the users typically do not go over the list of possible causes generated by SBFL linearly (and hence question the usefulness of the ranking) [21], a recent large-scale study demonstrates statistically significant and substantial improvements for the users who use an SBFL tool, and the results hold even for “mediocre” SBFL tools [32]. Based on this evidence, we suggest that the ranking can be used to explain policy decisions, as the ranked list itself would be helpful to identify the most important decisions. In addition, the pruned policies that we construct are simpler than the original policies while achieving a comparable performance, which can make identifying problems more straightforward. Examples are presented in the CartPole and Minigrid sections of the website. Finally, in Fig. 3, we show a heatmap of the scores of each state of a minigrid environment. In each grid square, the agent can be facing four directions. We show the score based on the tarantula measure for these directions from blue (lowest) to red (highest). We show this only for the states visited along a path to the goal. Our heatmap gives information about the general behaviour of the policy. In this case, points at which the agent needs to turn are more red (more important) than points where the agent is walking in a straight line. To understand why the downward-facing states in the right-most column are considered important, refer to our website for a full heatmap and explanation.
A Different Default Action Not all environments have an obvious default action. In this case, a straightforward choice is to set the default action to “take a random action”. We measured the effect of this choice by running the same experiments with the changed default action, and detailed results are available in the full version of this paper [22]. The results are similar or slightly worse to the ones obtained with the default action “repeat the previous action”. In most games, the difference was small (≤ 10%); a few games show a marginal improvement.These results indicate that the choice of a default action has no effect on our conclusions.
Good vs. bad policies Finally, we performed some initial work towards using the ranking to understand the difference between high and low-performing policies. To this end, we produced a ranking according to the high-performing policy, and then compared how the two policies behaved in the highest ranked states. Interestingly, our experiments demonstrate that the high performing and low performing policies agree on 80% of the actions in the top 10% of states. This suggests that the policy training (in CartPole) first picks the ‘low-hanging fruit’ by performing well in the most important states. The difference between a high-performing and a low-performing policy is mostly in the lower-ranked states. Full results for this experiment are available in the full version of this paper [22].

heading: 5 Related work
text: There is a significant body of work on identifying the important parts of trained algorithms, but to the best of our knowledge none suggested to rank the states as we do. Prioritised experience replay [24] looks for the most important transitions for training. Saliency maps [10, 29, 33] identify the parts of the state that most influence influence the agent’s decision. Sun et al. [26] have previously applied SBFL to visual feature importance for input images given to image classifiers. Other attempts include identifying the important parts of the representation of the policy by looking at the parameters of a trained model and pruning it to reduce its size [17]. None of these methods attempt to understand what the important decisions of the policy as a whole are.
Much of the recent work focuses on making deep learning models more interpretable [23, 19, 26]. Many approaches [10, 29, 33] to explaining deep reinforcement learning methods explain the decision made in a single state, without the context of the past or the future behaviour. Iyer et al. [14] explain a single decision via an object-level saliency map by leveraging the pixel-level explanation and object detection. As these methods focus on single decisions, the explanation is typically not sufficient to understand the overall decision-making of the trained agent.
Other work has also attempted to explain entire policies, rather than individual decisions. Ehsan et al. [8] produce natural language explanations for state-action pairs, based on a human-provided corpus of explanations. Topin and Veloso [27] create a Markov chain which acts as an abstraction of the policy, making it easier to reason about the policy. They create the Markov chain by grouping states into abstract states based on how similarly the policy acts in those states; our method is substantially different in that it ranks states based on importance, rather than grouping similar states. While our method allows for the use of abstract states, it is not always necessary, and we are not contributing any specific abstraction function. Similarly, Sreedharan et al. [25] propose a method for creating
a temporal abstraction of a policy by using bottleneck ‘landmarks’ in the policy’s executions. A robot’s behaviour can be explained using operator-specified “important program state variables” and “important functions” [12]. We find that the policy-wide decision ranking in this paper is an easier and more general method for understanding the policy. For more work in this vein, we encourage the reader to consult the overview from Chakraborti et al. [6] of the rapidly growing field of Explainable AI Planning (XAIP).
There have been attempts to make more interpretable models, either from scratch [13], or by approximating a trained neural network [28]. In the latter case, our method may be useful for determining in which states the approximation must be most accurate.

heading: 6 Conclusions
text: We have applied SBFL-based ranking of states to reinforcement learning and demonstrated that this ranking correlates with the relative importance of states for the policy’s performance. The ranking can be used to explain RL policies, similarly to the way ranked program locations are used to understand the causes of a bug. We evaluate the quality of our ranking by constructing simpler pruned policies, where only the most important decisions are made according to the policy, and the rest are default. Our experiments show that the performance of the pruned policies is comparable to the performance of the original policies, thus supporting our claim that the SBFL-based ranking is accurate. Moreover, the pruned policies may be preferable in many use-cases, as they are simpler. Our approach can be scaled with the use of abstractions, as demonstrated by the larger Atari environments.
In the future, we hope to explore different applications of the ranking, new measures, more nuanced hyperparameter selection, and relaxing the binary constraint over the assertion C. We do not expect our work to have any negative societal impacts, as it only serves to improve our understanding of the policies we train; the main concern is incorrectly increasing confidence in a policy.
Funding transparency statement The authors acknowledge funding from the UKRI Trust-worthy Autonomous Systems Hub (EP/V00784X/1) and the UKRI Strategic Priorities Fund to the UKRI Research Node on Trustworthy Autonomous Systems Governance and Regulation (EP/V026607/1).

Review summaries:
The goal of this work is to leverage fault localization techniques from software development and debugging as a way to simply learned RL policies. The main premise is that learned policies are unnecessarily complex. In order to simplify their complexity, it is critical to rank the states where the learned policy decisions are critical. Motivated by spectrum-based fault localization, authors leverage it in RL by using similar cost functions to compare complex policy functions to so called mutant executions which are policies that recommend default or previous actions as a way to simplify the complexity of the policy class. Based on such mutant policies (identified on the fly by parametrizing specific aspects), the authors demonstrate they are able to rank important states (based on the policy's impact on outcome). The proposed method is evaluated on standard RL environments (atari, minigrid, cartpole) to quantify efficacy and visually demonstrate interpretability via saliency maps. 

This paper studies the problem of "ranking policy decisions," which uses spectrum-based fault localization to compute an offline score for each action, conditioning on a state. The main idea is that the action with a higher success frequency should be ranked higher than other actions. Studying the action rank of policies presents an interesting angle to investigate RL policy from simplifying the DRL policy, interpretability, offline evaluation, while the experiments conducted might not be sufficient to support either one aspect solidly.  

The paper uses an existing ranking mechanism borrowed from software testing to rank the states of trajectories in reinforcement learning. After ranking the states, the authors propose to replace the top performing states with a default decision/action showing that that proposed ranking correlates with the `importance` of the trajectory states. The results show that the performance of the pruned policies (after replacing the states with a pre-defined action) is comparable with the original (non-pruned) policies.

This paper introduces a novel method based on spectrum-based fault localization (SBFL) from the software testing domain to identify the states in which decisions made by an RL policy are most influential in determining whether or not the agent achieves its objective. More specifically, the authors create "mutant trajectories" where, with probability $\mu$, a state is mutated and the action that the agent must take in that state is the "default action" (e.g. "repeat the previous action") or unmutated, where the agent acts according to policy $\pi$ when in that state.  From these mutant trajectories, the authors use SBFL to determine a ranking of states.  SBFL takes as input the vector $\<a_{ep}^{s}, a_{ef}^{s}, a_{np}^{s}, a_{nf}^{s}\>$, where $a_{ep}^{s}$ is the number of successes achieved when state $s$ is a non-mutant state, $a_{ef}^{s}$ is the number of failures achieved when state $s$ is a non-mutant state, and $a_{np}^{s}$, $a_{nf}^{s}$ log the number of successful and failed trajectories when state $s$ is a mutant state.  In order to assess the quality of the ranking returned by SBFL, the authors create "pruned policies" where an agent can only use the policy $\pi$ for the top $r$ states, and must use the default action for all other states.  Overall, in a wide variety of settings ranging from MiniGrid and Cartpole to Atari games, the authors find that, by ranking states using SBFL, they are able to encourage agents to vastly reduce the length of their trajectories while still attaining high reward.  This is a significant contribution from the perspective of creating interpretable AI.