Interpreting Reinforcement Policies through Local Behaviors
Authors: Ronny Luss
Amit Dhurandhar
Miao Liu
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Explainability

Abstract: Many works in explainable AI have focused on explaining black-box classification models. Explaining deep reinforcement learning (RL) policies in a manner that could be understood by domain users has received much less attention. In this paper, we propose a novel perspective to understanding RL policies based on identifying important states from automatically learned meta-states. The key conceptual difference between our approach and many previous ones is that we form meta-states based on locality governed by the expert policy dynamics rather than based on similarity of actions, and that we do not assume any particular knowledge of the underlying topology of the state space. Theoretically, we show that our algorithm to find meta-states converges and the objective that selects important states from each meta-state is submodular leading to efficient high quality greedy selection. Experiments on three domains (four rooms, door-key and minipacman) and a carefully conducted user study illustrate that our perspective leads to better understanding of the policy. We conjecture that this is a result of our meta-states being more intuitive in that the corresponding important states are strong indicators of tractable intermediate goals that are easier for humans to interpret and follow.

Under review as a conference paper at ICLR 2022
INTERPRETING REINFORCEMENT POLICIES THROUGH LOCAL BEHAVIORS
Anonymous authors Paper under double-blind review
ABSTRACT
Many works in explainable AI have focused on explaining black-box classification models. Explaining deep reinforcement learning (RL) policies in manner that could be understood by domain users has received much less attention. In this paper, we propose a novel perspective to understanding RL policies based on identifying important states from automatically learned meta-states. The key conceptual difference between our approach and many previous ones is that we form meta- states based on locality governed by the expert policy dynamics rather than based similarity of actions, and that we do not assume any particular knowledge of the underlying topology of the state space. Theoretically, we show that our algorithm to find meta-states converges and the objective that selects important states from each meta-state is submodular leading to efficient high quality greedy selection. Experiments on three domains (four rooms, door-key and minipacman) and a carefully conducted user study illustrate that our perspective leads to better understanding of the policy. We conjecture that this is a result of our meta- states being more intuitive in that the corresponding important states are strong indicators of tractable intermediate goals that are easier for humans to interpret and follow.
INTRODUCTION
Deep reinforcement learning has seen stupendous success over the last decade with superhuman performance in games such as Go (Silver et al. (016). Chess (Silver et al. (018)) as well as Atari benchmarks (Mnih et al. 2015). With increasing superior capabilities of automated (learning) systems, there is strong push to understand the reasoning behind their decision making. One motivation is for (professional) humans to improve their performance in these games (Rensch) 202T). An even deeper reason is for humans to be able to trust these systems if they are deployed in real life scenarios (unnning 2017). Safety, for instance, is of paramount importance in applications such as self-driving cars or deployments Data Protection Regulation (Yannella & Kagan 2018) passed in Europe demands that explanations need to be provided for any automated decisions that affect humans. While various methods with different flavors have been provided to explain classification models (Ribeiro et al.) 2016 Lundberg
unmanned aerial vehicles (UAVs) (Garcia & Fernandez 2015). The General
& Leee 2017 Lapuschkin al.) 2016; Dhurandhar al., (018)) and evaluated in amplication-gronneen manner (Doshi- Velli & Kim] (017) Dhurandhar et al. (017), the exploration of different perspectives explain reinforcement learning (RL) policies has been limited and user study evaluations comparing
methods are rarely employed in this space.
In this paper, we provide a novel perspective to produce human understandable explanations with task-oriented user study that evaluates which explanations help users predict the behavior of a policy better. Our approach involves two steps: 1) learning meta-states, i.e., clusters of states, based on the dynamics of the policy being explained, and 2) within eat meta-state, identifying states that act intermediate goals, which we refer to as strategic states. Contrary to the global nature of recent explainability works in RL (Topin & Veloso 2019 (rredharan et al.) 2020 Amir & Amir 2018). our focus is on local explanations; given the current state, we explain the policy moving forward within a fixed distance from the current state. This key distinction allows us to consider richer state spaces (i.e., with more features) because the locality restricts the size of the state space we consider, as will be demonstrated. It is also important to recognize the difference from bottlenecks (Menachel jet al. 2002; Simsek & Barto 2004) which are policy- indeeededdeen and learned by approximating the state space with randomly sampled trajectories; rather than help explain policy, bottlenecks

---

Under review as a conference paper at ICLR 2022
used to learn efficient policies such as through hierarchical RL (Botvinick et al. 2008 options frameworks (Ramesh et al. 2019). Strategic states, however, are learned with respect to policy and identified without assuming access to the underlying topology.
An example of this is seen in Figure Ta. Each position is a state and a meta-state is a cluster of possible positions (states sharing color/marker). Within each meta-state, we identify certain states as strategic states (shown with larger markers), which are the intermediate states that moving towards will allow the agent to move to another meta-state and get closer the goal state, which is the final state that the agent wants to get to. In Figure Th. each room is (roughly) identified as a meta-state by our method with the corresponding doors being the respective strategic states. Topology refers the graph connecting states to one another; our method only has access to the knowledge of which states are connected (through the policy), whereas reinforcement learning algorithms might have access to properties of the topology. e.g., the ability to access similar states using successor representations (Machado et al., 2018). In Figure [] the topology is a graph connecting the different positions each room the doors connecting one room to another.
A key conceptual difference between our approach and others that other methods aggregate insight (i.e. reduce dimension) as function of actions (Bastani et al., (2018) or formulas derived over factors of the state space (Sreedharan et al. 2020) to output policy summary. whereas we aggregate based on locality of the states determined by the expert policy dynamics and further identify strategic states based on these dynamics. Still other summarization methods simply output simulated trajectories deemed important (Amir & Amir 2018, Huber et al., 2021) as judged by whether not the action taken at some state matters. We use the term policy dynamics to refer to state transitions and high probability paths. We use the term dynamics because this notion contrasts other methods that use actions to explain what to do in state or to identify important states; strategic states are selected according to the trajectories that lead to them, and these trajectories are implicitly determined by the policy.
The example in Figure I aalso exposes the global view of our explanations when the state space is small because local approximations of the state space are not needed. We show that this perspective leads to more understandable explanations; aggregating based on actions, while precise, are too granular a view where the popular idiom can't 't see the forest for the trees comes to mind. We conjecture that the improved understanding is due to our grouping of states being more intuitive with strategic states indicating tractable intermediate goals that easier to follow. An example of this is again seen in Figures and Te. where grouping based on actions for interpretability or for efficiency leads to less intuitive results (note that Figure D replicates Figure 4b from (Abel al. 2019)). A more detailed discussion of this scenario can be found in section 5] where yet other domains have large state spaces and require strategic states to explain local scenarios.
As such, our main contributions are two-fold:
1. We offer novel framework for understanding RL policies, which to the best of our knowledge, differs greatly from other methods in this space which create explanations based on similarity of actions rather than policy dynamics. We demonstrate on three domains of increasing difficulty.
2. We conduct a task- oriented user study to evaluate effectiveness of our method. Task-orient oriented evaluations are one of the most thorough ways of evaluating explanation methods (Doshi- Velez &
Kim, 2017 [ipton] 2016 Dhurandhar et al., (017) as they assess simulatability of a complex Al model by a human, yet to our knowledge, have rarely been used in the RL space.
2 NOTATION
We use the following notations. Let S define the full state space and s E S be a state in the full state space. Denote the expert policy by ()) (A, S) - R where A is the action space. The notation TE R[A[x[S] is matrix where each column is distribution of actions take given state (i.e., the policy is stochastic). Note that we assume a transition function fr((,)) (S, S) -> TR that defines the likelihood of going from one state to another state in one jump by following the expert policy.
Let S = [ 4 denote a meta-state space of cardinality I and Φ(-) S + S, denote a meta-state mapping such that d(s) E Sgp is the meta-state assigned to s E S. Denote m strategic states of meta-state & by G (of. :.... }md where of 8 Vi E m)....)..
2

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
Figure 1: Illustrations of our SSX (a), VIPER-D (b), and abstract states used for compression (c) methods based on an expert policy for the Four Rooms game with neither having information about the underlying topology of the state space. Colors/Shapes denote different meta-states/clusterr. The black X in the upper right is the goal state. SSX clusters the four rooms exactly with strategic states denoted by larger markers, where the biggest marker implies the priority strategic state. SSX explains that the expert policy will head towards the open doors in each room preferring the door that leads to room with the goal state. VIPER-D clusters states by action (black/plus-up, green/circle=down, blue/diamond-leff, red/square=right) based on the full (discrete) state space, rather than samples, since tractable here. The compressed state space in (c) is also function of the experts (conditional) action distribution. Clusters in (b) and (c) are scattered making it challenging for human to understand any policy over clusters.
3 METHOD
We now describe our algorithm, the Strategic State eXplanation (SSX) method, which involves computing shortest paths between states, identifying meta-states, and selecting their corresponding strategic states. However, we first define certain terms. Recall that all paths discussed below are based transitions dictated by expert policy because concept called bottlenecks are identified from paths generated as random walks through the state space and are meant help learn policies rather than explain them.
want explain the policy; the well-known
Maximum likelihood (expert) paths: One criterion used below is that two states in the same meta- state should not be far away from each other. The distance we consider is the most likely path from state to state s' under тg. Consider a fully connected, directed (in both directions) graph where the states are vertices and an edge from s s' has weight log fE,s, s'). By this definition, the shortest path is also the maximum likelihood path from to s'. Denote by (s, s') the value of this maximum likelihood path and I E [S| a matrix containing the values of these paths for all pairs of states in the state space. r, along with predecessor matrix P that can be used to derive the shortest paths, can be computed using Dijkstra's 's shortest path algorithm in S log [S]) because all edge weights are non-negative. Section 3.4 below discusses how our algorithm applied with large state space. Note that computation of means that SSX requires access
policy simulator for Tg. and in practice, might require simulation for estimation when I' cannot be computed exactly. This is a common requirement among related explanation methods, e.g., in order to simulate important trajectories Amir & Amir (2018) or samples to train a decision tree Bastani et al.) (2018). ) that are discussed below in Section
Counts of Out-paths: Another criterion used below for assigning states to meta-states that if state lies many of the paths between one meta-state 4; and all other meta-states then should be assigned the meta-state 4,, i.c., (ss) = 4;, We define, for fixed state and its assigned meta-state ((s), the number of shortest paths leaving d(s) that lies on. Denote 1 T'ss, s') as the set of states that lie on the maximum likelihood path between and s', i.e., the set of states that define ((s, s'). Then 1[s T(s', s")] is the indicator of whether state lies on the maximum likelihood path between s' and s", and we compute the count of the number of such paths for state s and meta-state Φ(s) via
C(s, (()))
Σ
Σ
I[s E T(s', s")].
((s)==(()
ois (00()
C(s, ((s)) can be computed for all s S in O(S ?2) by iteratively checking if predecessors of shortest paths from each node to every other node lie in the same meta-state the first node on the
3

---

Under review as a conference paper at ICLR 2022
path. Note this predecessor matrix was already computed for matrix I above. One may also consider the likelihood (rather than count) of out- out-paths by replacing the indicator in eq. ! with 7(s', s").
3.1 LEARNING META- STAAESSATES
We seek to learn meta-states that balance the criteria of having high likelihood paths within the meta-state and having many out-paths from states within the meta-state. This is accomplished by minimizing the following objective for suitable representation of s, which in case is the eigen-decomposstion of the Laplacian of r:
argmin [(s-)
n)((s, +)]
S +ES EE
where cp denotes the centroid of the meta-state Φ and 1| 0 balances the trade-off between the criteria. Note that we are optimizing Sş over all possible sets of meta-states. Other representations for and functions for the first term could be used, but our choice is motivated from the fact that such formulations are nostalgic of spectral clustering (Shi & Malik, 2000) which is known to partition by identifying well-connected components, something we strongly desire. Our method for solving eq. (2) is given by algorithm and can be viewed as regularized version of spectral clustering. In addition to clustering a state with others that it connected to, the regularization term pushes a state to cluster, even if there are only few connections to the cluster, if the policy dictates that many paths starting in the cluster go through that state.
Algorithm 1: Meta-state function MS(S, A. Tg, kk,
1) Get eigen representation of each state from eigen decomposition of the Laplacian of I 2) Randomly assign states S to meta-state in Sp { .... @x } and compute centroids
C1. ..., C for meta-states
3) eour current value of objective in eq.
do
4) Epeev Ecur
5) Reassign states s to the meta-states based on smallest value (s - -2 ryC 2)
.... Cj. for meta-states based on current assignment 7) gour current value of objective in eq.
6) Compute centroids cI....,
while [ecur - g Ca: Output: Meta-states ( 4x}
Algorithm 2: Strategic State function SS r, (g). Finds Strategic States with Greedy Selection (w.l.o.g. assume meta-state & contains the goal state).
for i = to k do 1) Let gour and Go. 0
do
2) gpee geur
3) Ga. G+. Ug where argmaxx of eq. 3 given the current strategic states Go. .Eo,
gour evaluate eq. with Go.
while |gaur - eprey Egi
end
5) G.. g, where g denotes the goal state of the expert policy
Output: Strategic states corresponding to each meta-state (Go, ..., Go,
3.2 IDENTIFYING STRATEGIC STATES
Next, strategic states must be selected for each meta-state. Assume that " 9h S are m strategic states for meta-state & that does not contain the target state. Our method finds strategic states by solving the following optimization problem for some 0:
112
G
(m) argiaax
Clgi 2)
Σ
Σ
max (7 99 T0; .9.
(3)
g
4

---

Under review as a conference paper at ICLR 2022
The first term favors states that lie on many out-paths from the meta-state, while the second term favors states that are far from each other. Thus, the overall objective tries to pick states that go to different highly rewarding parts of the state space from particular meta-state, while also balancing
the selection of states to be diverse (i.e., far from each other). The objective in eq. (3) is submodular
as stated next (proof in appendix) and hence we employ greedy selection in algorithm [
Note that
for the meta-state that contains the target state, the target state itself is its only strategic state.
Proposition 1. The objective to find strategic states in equation
is submodular.
3.3 STRATEGIC STATE EXPLANATION (SSX) METHOD
Our full method is detailed as follows. First, the maximum likelihood path matrix I' is computed. Then, algorithm T tries to find meta-states that are coherent w.r.t. the expert policy, in the sense that we group states into a meta-state if there is a high likelihood path between them. Additionally, many paths from states in a meta-state go through another state, then the state is biased to belong to this meta-state. Finally, algorithm seleetss strategic states by optimizing a trade-off between being on many out-paths with having a diverse set of strategic states. Code is provided in the Supplement.
3.4 SCALABILITY
Given our general method, we now discuss certain details that were important for making our algorithm practical when applied to different domains. SSX is applied in Section games with state spaces ranging from small to exponential in size. SSX is straightforward for small state spaces as one can pass the full state space as input, however, neither finding meta-states nor strategic states would be tractable with an exponential state space. One approach could be to compress the state space using VAEs as in (Abel et al. 2019), but as shown in Figure [p. interpretability of the state space can be lost as there is little control as how states are grouped. Our approach is to use local approximations to the state space; given a starting position, SSX approximates the state space by the set of states within some N > number of moves from the starting position. In this approach, Algorithms
D and 2 are a function of N, i..., increasing N increases the size of the approximate state space which is passed to both algorithms. One can contrast our approach of locally upproximating the state space with that of VIPER (Bastani et al.) 2018) which uses full sample paths to train decision trees. While the number of states in such an approximation is M where M is the number of possible agent actions, the actual number of states in game such a pacman is much smaller in practice. Indeed, while pacman has 5 possible actions, the growth of the state space in our approximation as N increases acts similar to game with between 2-3 actions per move because most states in the local approximation are duplicates due to both minipacman and the ghost going back and forth. See Figure S in the Appendix, where other practical considerations are also discussed.
4 RELATED WORK
While a plethora of methods are proposed in XAI (Ribeiro et al. 2016; Lundberg & Lee 2017 Lapuschkin et al. 2016 Dhurandhar et al. 2018), we focus on works related to RI. explainability and state abstraction, as they are most relevant to our current endeavor.
Most global RL methods summarize policy using some variation of state abstraction where the explanation uses aggregated state variables that group actions (Bastani et al., 2018) using decision trees or state features (Topin & Veloso 2019) using importance measures, or such that an ordering of formulas based on features is adhered to (Sreedharan et al. 2020). These approaches all intend to provide a global summary of the policy. Other summaries output trajectories deemed important according to importance measures (Amir & Amir 2018 Huber et al., 202T) or through imitation learning (Lage et al. 2019), or train finite state representations to summarize a policy with an explainable model (Danesh et al. 2019 2021). Visualization techniques combined with saliency have been used to either aggregate states and view the policy from a different perspective (Zahavy et al.. 2016) or create a trajectory of saliency maps (Greydanus et al. 2018). Further, other works try to find state abstractions or simplify the policy (Abel et 2019 Paul et al., 2019: Liang et al. 2016). and one should not confuse these works with those seeking explainability. State abstraction in these works is used to compress the state space so that simpler policies can be used; the compressed state space is not intepretable seen in Figure Tt.
5

---

Under review as a conference paper at ICLR 2022
Turning towards local explanation methods, some works focus on self-explaining models (Mott et al. 2019) where the policy has soft attention and so can indicate which (local) factors it is basing its decision at different points in the state space. Yau et al. (2220) learns a belief map concurrently during training which is used to explain locally by predicting the future trajectory. Interestingly, there works which suggest that attention mechanisms should not be considered explanations (Jain & Wallace 2019). These directions focus on learning an inherently explainable model rather than explaining given model which is our goal. Other works use local explanation methods to explain reasons for a certain action in particular state (Olson et al.) 2021] Madumal et al. 2020). These are primarily contrastive where side information such as access to the causal graph may be assumed. Our approach besides being methodologically different, also differs conceptually from these, where we form meta-states based on policy dynamics and then identify (strategic) states through which many policy-driven paths cross.
There are also program yynthesisttype methods (Verma et al. 2018 Inala et al., (020) that learn syntactical programs representing policies, which although more structured in their form, are typically not amenable to lay users. There are also methods in safe RL that try to uncover failure points of a policy (Rupprecht et al., 2020) by generating critical states. Another use of critical states, defined differently by how actions affect the value of a state, is to establish trust in a system (Huang et al. 2018). There is also explainability work in the markov decision processes literature which focus on filling templates according to different criteria such as frequency of state occurrences or domain knowledge (Khan et al.) 2009; Elizalde et al. 2009). A more elaborate discussion of these and other methods can be found in (Alharin et al. 2020). all of which unequivocally are different from ours.
5 EXPERIMENTS
This section illustrates the Strategic State eXplanation (SSX) method three domains: four rooms, door-key, and minipacman. These domains represent different reinforcement learning (RI.) regimes, namely, 1) non-adversarial RL with small state space and tabular representation for the policy, 2) non-adversarial RL, and 3) adversarial RL, the latter two both with a large state space and a deep neural network for the policy. These examples illustrate how strategic states can aid in understanding RL policies. Experiments were performed with I GPU and up to 16 GB RAM. The number of strategic states was chosen such that additional strategic states increased the objective value by at least 10%. The number of meta-states was selected as would be done in practice, through cross- validation to satisfy human understanding. Details about environments are in the Appendix, along with additional experiments illustrating faithfulness and consistency of SSX.
The objective of Four Rooms is move through a grid and get to the goal state (upper right corner). The lack of a marker in a position represents a wall. Our grid size is 11 x 11. The state space consists of the current position of player and the policy is learned as a tabular representation, since the state space is not too large, using Value Iteration (Martino & Mostofsky 2016).
Four Rooms:
SSX is displayed in Figure I with settings that learn four meta-states. Clustering the states using algorithm [ according to the policy dynamics (i.e. maximum likelihood path matrix T') results in an (almost) perfect clustering of states according to the rooms. X's denote strategic states learned in each meta-state, with a larger X corresponding blue, green or red rooms could lead to the goal state in the upper right corner (large yellow diamond), but it is important note that higher valued strategic states in the red and blue rooms are those that lead directly to the yellow room where the goal state is located.
the first strategic state found. Clearly either door in
Figure Tp illustrates the results of VIPER-D which is our implementation of VIPER (Bastani et al. 2018). The explanation is illustrated using different colors per action which effectively offers the rules of the decision tree. While an explanation based on rules can be informative in continuous state spaces (as demonstrated in (Bastani et al.) 2018)), such rules applied to a discrete state space as done here may lead to confusion, e.g., groups of green states are split by yellow states in the left two rooms and allow for optimal policy but it is not clear how to describe the cluster of states in which to take each action. Figure T: illustrates the difference between explainability and compression. The purpose of (Abel et al. 2019) is to learn abstract states upon which proxy policy can be learned more efficiently that replicates the original expert policy on the full state space. The lack of interpretability of the abstract states is not of concern in that context.

---

Under review as a conference paper at ICLR 2022
Locked Door
Unlocked Door
Figure 2: Illustration of our SSX method on Door-Key. Policies were trained different environments: Locked Door and Unlocked Door. Each row corresponds to a meta-state and strategic state (outlined in pink) from running SSX starting at different number of moves into the same path (one path for completing the task in each of the two environments).
Door-Key: Door-Key is another non-adversarial game, but differs from Four Rooms because the state space exponential in the size the board. The policy is learned as a convolutional neural network (CNN) with three convolutional and two linear layers. In this game, one room through a door to the next room and find the goal location to get reward. Policies are trained under two scenarios. In the first scenario, there is key in the first room that must be picked up and used to unlock the door before passing through. In the second scenario, the door closed but unlocked, so one does not need first pick up the key open the door.
must navigate from
SSX is run with local approximations to the state space with the maximum number of steps set to discussed in Section 3.4 Results are shown in Figure The state space is 7 grid reflecting the forward facing perspective of the agent. Walls are light gray and empty space visible to the agent dark gray. Grid positions blocked from view by walls are black. The scenes in Figure 2 are exactly what a user sees. To better understand why the scenes do not appear easily connected, consider the first two states in the first row the only difference from the first state that the agent has changed directions. When facing the wall, the agent's view only includes the three positions to the right and one position to the left. All positions on the other side of the wall are not visible to the agent, which is depicted black. When the agent changed directions (row column 2), many more positions in the room become visible to the agent.
In Figure 2, sample path generated using each policy. SSX along these paths, and one meta-state and corresponding strategic state (outlined in pink) from each SSX explanation is displayed. The three strategic states for the locked door environment correspond to the agent looking for the key (row 1), getting the key (row 2), and using it to open the door (row 3). The three strategic states for the unlocked door environment correspond to the agent immediately looking for the door (row 1), made it through the door (row 2), and moving toward the target (row 3).
three different states
For intuition how human would use these explanations, consider the cluster in 1 for the Locked Door. Comparing the first three states in the cluster to the strategic state, human sees that in this cluster, the policy suggesting to face the key and move closer it. As this local explanation, it is limited by the initial state being explained as to how close one get to the key. The cluster in row 1 for the Unlocked Door shows that the policy at these states to face the door. Perhaps facing the door within a certain distance is how the policy breaks down the ultimate strategy. While one might wonder why the strategy is not to get closer to the door (e.g., move up from the second column), recall that the strategic state is explaining the policy and not human intuition.
Lastly, note that for the Unlocked Door, the third state the same in rows and The rows correspond to explanations for two different initial states, but it is very possible that the same state is encountered in trajectories from each initial state and thus appears in multiple explanations as seen here. Such occurrences further illustrate that SSX explanations are local to initial state.
Minipacman: Minipacman is a small version of the classic Pacman game. This game differs from Door- Key with the addition of an adversary the ghost. The state space is again exponential in the size the board and the policy learned as a convolutional neural network with two convolutional and two linear layers. Two policies are trained with different objectives. The first objective, denoted

---

Under review as a conference paper at ICLR 2022
EAT Scenario
HUNT Scenario I
Illustration of our SSX method on minipacman. Two policies, EAT and HUNT, are displayed. Two clusters, one per row, are shown as part of the SSX result. The last board with pink background is a strategic state for each cluster. The color scheme is as follows: green = pacman, red ghost, yellow = edible ghost, cyan = pill, blue food, black food eaten, white/pink=wall!
Figure 3:
Humen Accuracy based Explanations
Qualitative Likee Evaluation
Coown
Comyletenne
60-
Likert 5-point Scale
undericaddaiitty
Percentage
SSX
Viper-D
SSX
Viper-D
Figure 4: Above (left) we see the percentage (human) accuracy in predicting if the expert policy is Eat or Hunt based SSX and Viper-D. As can be seen users perform much better with SSX with difference in performance being statistically significant (paired t-test p-value=0.01). Above (right) we see a 5-point Likert scale (higher better) for four qualitative metries used in previous studies (Madumal et al. 2020). Here too the difference is statistically significant for all four metrics (p-values are all less than 2
Error bars are std error.
EAT, is for minipacman to eat all the food with reward for cating the ghost. The second objective, denoted HUNT, is for minipacman to hunt the ghost with no reward for cating food.
SSX is again run with local approximations to the state space with the maximum number of steps set to 8. The state space a 10 x grid reflecting where food, pacman, a ghost, and the pill are located. sample scenario under both the EAT and HUNT policies, with two meta-states
Figure BatreBBdsppp displays and corresponding strategic states highlighted in pink. The two strategic states of EAT Scenario show pacman eating the food (row 1) but then avoiding the ghost and ignoring the pill (row 2). In HUNT Scenario 1, pacman is either directly moving towards the ghost after having eaten the pill (row or heading away from the pill while the ghost is near (row 2). Two additional scenarios for EAT and HUNT can be found in the Appendix. An additional experiment with a bascline motivated by Amir Amir (018) appears in the Appendix.
USER STUDY
We designed a user study to evaluate the utility of our approach relative the more standard approach of explaining based on grouping actions. While SSX has thus far been used to give users local explanations about particular scenarios, we use here to gain insight as the general goal a policy because the relevant explanations to compare with are global; as previously discussed, other local literature is about learning inherently explainable models rather than explaining fixed model or learning contrastive explanations which should be used complementary our methods. The global applicability SSX can also be seen as another advantage. As with Four Rooms, we again compare with our implementation of VIPER policies - with a visual output tailored for the discrete state space. We do not compare with methods that output trajectories (Amir& & Amir 2018) they require estimating Q-values to determine state
state-of-the
explanation method for reinforcement learning
8

---

Under review as a conference paper at ICLR 2022
importance which relies on sensitive hyperparameter tuning. Among explanation methods, Viper makes for the best comparison as it requires a similar amount of human analysis of the explanation (by observing states), and while meant for global explainability, also gives local intuitions, as opposed to other global methods. The utility of each approach is measured through a task posed to study participants: users must guess the intent of the expert policy based on provided explanations which are either output by SSX or Viper-D. Such a task oriented setup for evaluation is heavily encouraged in seminal works on XAI [Doshi-Velez & Kim 2017: Lipton 2016
Dhurandhar et al. 2017).
We use the minipacman framework with the EAT and HUNT policies trained for Section 5 and each question shows either an SSX explanation or Viper-D explanation and asks the user "Which method is the explanation of type A (or B) explaining?" to which they must select from the choices Hunt, Eat, or Unclear. Methods are anonymized (as A or B) and questions for each explanation type are randomized. Ten questions (five from both the EAT and HUNT policies) are asked for each explanation type giving a total of twenty questions to each participant. In addition, at the end of the study, we ask users to rate each explanation type based metrics- completeness, sufficiency, satisfaction and understandability as has been done in previous studies on explainable RL (Madumal et al. 2020). For users to familiarize themselves with the two types of explanations we also provided them with two training examples, one for each type at the start of the survey.
Setup:
5-point Likert scale for four qualitative
To be fair to VIPER-D explanations, rather than just displaying rules in text which may not be aesthetically pleasing, we also created visualization which not only displayed the (five) rules the user, but also three boards, one each for pacman, the ghost, and the pill, highlighting their possible locations as output by the rule. This is beyond the typical decision tree offered by VIPER, which is meant for continuous state spaces, and better renders what the explanation looks like in our discrete setting. Screenshots of sample visualizations along with the instruction page and optional feedback left by users can be found in the appendix.
The study was implemented using Google Forms and we received 37 responses from people with quantitativeteccnical backgrounds, but not necessarily AI experts. We removed 5 responses as they were likely due to users pressing the submit button multiple times as we twice received multiple answers within 30 seconds that were identical.
Figure 4 (left) displays user accuracy on the task for method SSX and Viper-D. Users clearly were able to better distinguish between the EAT and HUNT policies given explanations from SSX rather than Viper-D and the difference in percentage correct is statistically significant (paired t-test p-value is 0.01). Another interesting note is that less than 5% of SSX explanations were found to be Unclear whereas more than 25% of Viper-D explanations were labeled Unclear, meaning that, right or wrong, users felt more comfortable that they could extract information from SSX explanations.
Observations:
Figure (right) displays the results of the qualitative questions ("Was it com- pleteesufficienttsstiitacoooo
to understand?") for both SSX and Viper-D which users rate on a 5-point scale ranging from "Not at all" to "Yes absolutely". All metrics score high for SSX and differences with Viper-D are statistically significant. These results are consistent with the very different percentage of Unclear selections for SSX and Viper-D. i.c., users found very few SSX explanations to be unclear and therefore also scored SSX higher in the qualitative metries.
7 DISCUSSION
We have seen in this work that our novel approach of identifying strategic states leads to more complete, satisfying and understandable explanations, while also conveying enough information needed to perform well on a task. Moreover, it applies single agent as well as ageti- adversarial games with large state spaces. Further insight could be distilled from our strategic states by taking the difference between the variables in some particular state and the corresponding strategic state and conveying cumulative actions an agent should take to reach those strategic states (viz. go 2 steps up and 3 steps right to reach a door in Four Rooms). This would cover some information conveyed by the typical action-based explanations we have seen while possibly enjoying benefits of both perspectives. Other future directions include experimenting to see if strategic states could be used as intermediate goals for efficient training of new policies and extension of our idea to continuous state spaces. While one could discretize the state space which could be suboptimal, would be interesting to see if it can be symbiotically done.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
As Deep Reinforcement Learning (DRL) has seen huge success in solving challenging problems with superhuman performances across multiple domains (Silver al., 2016 2018 Mnih al.) 2015) understanding these policies has implications in human learning as well as safety (Garcia & Fernandez 2015). We in this work have provided mechanism for uncovering the core insights from such policies. Saying that, though, it is possible that some insights might be missed by our method as it distills relevant information. This limitation not specific to our method and applies to other posthoe explanation methods well. From privacy standpoint our method could be used to decipher sensitive information about an agent. Mitigation may possible by restricting access of our method to only desirable parts of the state space that are deemed safe to divulge.
REPRODUCIBILITY DISCUSSION
All datasets used are public. Experimental details are in Section of the main paper and Section C in the appendix. Code provided in the supplement.
REFERENCES
David Abel, Dilip Arumugam, Kavosh Asadi, Yuu Jinnai, Michael L. Littman, and Lawson L.S. Wong. State abstraction as compression in apprenticeship learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Alnour Alharin, Thanh-Nam Doan, and Mina Sartipi. Reinforcement learning interpretation methods: A survey, IEEE Access, 8:171058-171077, 2020. doi: 10.100/ACCEESSS.0000332535
Dan Amir and Ofra Amir. Highlights: Summarizing agent behavior to people. In AAMAS, 2018.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Advances in Neural Information Processing Systems, 2018.
MIchael M. Botvinick, Yacl Niv, and Andrew C. Barto. Hierarchically organized behavior and its neural foundations: reinforcement learning perspective. Cognitive, 3(1 13):2622222222 22062222200022 2008
Mohamad H. Danesh, Anurag Koul, Alan Femn, and Saeed Khorram. Learning finite state representa- tions of recurrent policy networks. In Intl. Conference on Learning Representaitons, 2019.
Mohamad H. Danesh, Anurag Koul, Alan Fern, and Saeed Khorram. Re-understanding finite state representations of recurrent policy networks. In Intl. Conference on Machine Learning, 2021.
Amit Dhurandhar, Vijay Iyengar, Ronny Luss, and Karthikeyan Shanmugam. TIP: Typifying the interpretability of procedures. arXiv: 1eXiv:1006.02) 02952,,, 2017.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems, pp. 012-592-00 603, 2018.
Finale Doshi Velez and Been Kim. Towards rigorous science of interpretable machine learning. 1 2017.
Francisco Elizalde, Enrique Sucar, Julieta Noguez, and Alberto Reyes. Generating explanations based markov decision processes. In Mexican Inil. Conference Artificial Intelligence, 2009.
Javier Garcia and Fernando Fernandez. A comprehensive survey on safe reinforcement learning. JMLR, 16:1487-4480 2015.
Samuel Greydamus, Anurag Koul, Jonathan Dodge, and Alan Femn. Visualizing and understanding atari agents. In International Conference Machine Learning, 2018.
David Gunning. Explainable artificial intelligence (xai). In Defense Advanced Re-
search Projects Agency 2017.
URL https: wwww///ww///.m//////////////./ darpa mi 1/progrrrm
explainables wwt.aaiiiiiaaaaaaaaaiaaaiiilaaaa
genne
10

---

Under review as a conference paper at ICLR 2022
Sandy H. Huang, Kush Bhatia, Pieter Abbeel, and Anca D. Dragan. Establishing appropriate trust via critical states. In Intl. Conference on Intelligent Robots and Systems, 2018.
Tobias Huber, Katharina Weitz, Elisabeth André, and Ofra Amir. Local and global explanations of agent behavior: Integrating strategy summaries with saliency maps. In arXiv:2101.124 2021.
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing
programmatic policies that inductively generalize. In International Conference Learning Representations, 2020.
Sarthak Jain and Byron C. Wallace. Attention is not explanation. NAACI, 2019.
Omar Zia Khan, Pascal Poupart, and James P. Black. Minimal sufficient explanations for factored markov decision processes. In Proceedings of the Nineteenth Intl. Conference on Automated Planning and Scheduling, 2009.
Isaac Lage, Daphna Lifschitz, Finale Doshi-Velez, and Ofra Amir. Exploring computational user models for agent policy summarization. In Intl. Joint Conference on Artificial Intelligence, 2019.
Sebastian Lapuschkin, Alexander Binder, Grégoire Montavon, Klaus-Robert Robert Müller, and Wojciech Samek. The Irp toolbox for artificial neural networks. Journal Machine Learning Research, 17 URL StLhttt::/ jmlr. org papers / //v1/v11 v17/15- 6 8 html
(114):1-5, 2016.
Yitao Liang. Marlos C. Machado, Erik Talvitie, and Michael Bowling. State of the art control of atari games using shallow reinforcement learning. In AAMAS, 2016.
Zachary C Lipton. The mythos of model interpretability. ICML Workshop on Human Interpretability in Machine Learning. 2016.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pp. 4765-4774, 2017.
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Conference Learning Representations (ICLR), 2018
Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable reinforcement learning through a causal lens. In AAAI, 2020.
Adriana Di Martino and Stewart Mostofsky. Ihtml.
Abide.
2016.
http://fconn 1000. wwwppp/ctt.inicc..ooiiniiaaaaaaa
Ishai Menache, Shie Mannor, and Nahum Shimkin. Q-cut dynamic discovery of sub-goals in reinforcement learning. In Proceedings of the European Conference Machine Learning, 2002.
V. Mnih, Silver Kavukcuoglu, K., and D. et al. Human-level control through deep reinforcement learning. Nature, 5 518:529-533, 2015.
Alexander Mott, Daniel Zoran, Mike Chrzanowski, Daan Wierstra, and Danilo Jimenez Rezende. Towards interpretable reinforcement learning using attention augmented agents. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL htttps://proceeeiinnn www.iieerrpppp.. http:/iissccppppp///////////// pdf
Matthew I.. Olson, Roli Khanna, Lawrence Neal, Fuxin Li, and Weng-Keen Wong. Counter- factual state explanations for reinforcement learning agents via generative deep learning. In arXiv:2101.12446, 2021.
Sujoy Paul, Jeroen Vanbaar, and Amit Roy-Chowdhury. Learning from trajectories via subgoal discovery. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Rahul Ramesh, Manan Tomar, and Balaraman Ravindran. Successor options: An option discovery framework for reinforcement learning. In Intl. Joint Conference Artificial Intelligence, 2019.
11

---

Under review as a conference paper at ICLR 2022
Daniel Rensch. Learn from the best: Alphazero, 2021.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should I trust you?"; Explaining the predictions any classifier. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135- 144, 2016.
Christian Rupprecht, Cyril Ibrahim, and Christopher J. Pal. Finding and visualizing weaknesses of deep reinforcement learning agents. International Conference on Learning Representations. 2020. URL wtt.https: htttt:::://ppnrevviii http://wwweeeeeruumeeddeeeerreee
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions PAMI, 2000.
D. Silver, Maddison Huang, A., and C. et al. Mastering the game of go with deep neural networks and tree search. Nature, 529:484 489, 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 16264419):1144441144 2018 ISSN 0036-8075, URL https: / sesssciieceee www.ssccwggn.iooooo.oo.. htt.:oogg///oooe..
coclee/cemm..oogg//noeeett/t///e /32/
O. Simsek and A. G. Barto. Hierarchical interpretations for neural network predictions. In Intl. Conference on Machine Learning, 2004.
S. Sreedharan, S. Srivastava, and S. Kambhampati. Tidr:
Policy summarization for factored ssp problems using temporal abstractions. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Nicholay Topin and Manuela Veloso. Generation of policy-level explanations for reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, 2018
Philip N. Yannella and Odia Kagan. Analysis: Article 29 working party guidelines on automated com/201 /al/aaasssi-artillle
decision making under gdpr. 2018. https//www..ybeeradvieee. 29- working boorking-partt-eee partp-aariiiee party-guidelines-oon www.oooooaaeddeeeeieiiiiiiieeeii -eeiiiiommaiiiiiigg.....-. under-gdpr!
Herman Yau, Chris Russell, and Simon Hadfield. What did you think would happen? explaining agent
behaviour through intended outcomes. In Advances in Neural Information Processing Systems, 2020.
Tom Zahavy, Nir Ben Zrihem, and Shie Mannor. Graying the black gox: Understanding dqns. Intl. Conference on Machine Learning, 2016.
APPENDIX
A ALGORITHMIC DETAILS
We first prove Proposition 1.
Proof. Consider two sets U and V consisting of strategic states of meta-state Q where U C V. Let w be strategic state & V and (.) represent the objective in equation 3 then we have
(U (U) = C(w, 4)
Σ NEU
max (r(w, r(u, w))
(4)
Similarly,
(V w) Gv) C(w, b)) Σ max (1(,,)), r(w,
(5)
12

---

Under review as a conference paper at ICLR 2022
Subtracting equation
from
we get,
Σ
max (7 r(,,
Σ
max (),
(6)
WEV
NEG
Σ
max (7(2, w), rww, u)) 2
Thus, the function G has diminishing returns property.
We next comment on the convergence for Algorithm which follows directly since our objective in equation (2) is bounded and monotonically decreases at each iteration. Proposition 2. Meta-state finding Algorithm| converges.
16
actions
actions
actions
actions
Log. States)
X
Maximum moves from initial state
Figure 5: Illustrations of SSX state space size in minipacman. Worst case state space size for local approximations is N where N is the maximum number of moves made and M is the number of possible actions per move. Pacman's 's state space is averaged over 100 random samples for each N I,..., 10. The state space of minipacman, while also growing exponentially, grows much slower (like game with 2-3 actions per move) which makes SSX practical method for such games.
B ADDITIONAL PRACTICAL CONSIDERATIONS
Additional information on scalability: SSX is applied in Section 5 to games with state spaces ranging from small to exponential in size. The SSX algorithm is straightforward for small state spaces pass the full state space as input, however, neither finding meta-states would be tractable with an exponential state space. One approach could be to compress the state space using VAFs in (Abel al. 2019), but shown in Figure Tp. interpretability of the state space can be lost as there is little control as to how states are grouped. The same phenomenon can be observed when considering compression versus explainability in other contexts such classification models. Our approach is to use local approximations to the state space; given a starting position, SSX approximates the state space by the of states within some N > 0 number of moves from the starting position. Considering different starting positions will offer the user global explanation for fixed policy. In this approach, Algorithms and 2 are function of i.e. increasing N increases the size of the approximate state space which is passed to both algorithms. One can contrast our approach of locally approximating the state space with that of VIPER (Bastani et al.) 2018) which
strategic states
uses full sample paths to train decision trees.
Figure displays how the state space size in minipacman, discussed in Section 5 the number of possible moves N allowed for the local approximation grows. Worst case state space size for local approximations M where
grows in practice as
is the number of possible actions per move. At any position the board, minipacman has at most 4 possible actions (3 possible directions to move or stay) and the ghost has an additional 3 potential actions for a total of 7 possible state movements at most. The state space of minipacman is averaged over 100 random samples for each N 1,...,
13

---

Under review as a conference paper at ICLR 2022
EAT
HUNT
Figure 6: Illustaaiion of selecting important states on minipacman. Two policies, EAT and HUNT, displayed across two scenarios for each. For each scenario, single cluster is shown. For given cluster, the last board with pink background an important state for that cluster as defined by equation (D). The color scheme is as follows: green = paeman, red ghost, yellow edible ghost, cyan = pill, blue = food, black = food eaten, white/pink=wall.
and, while growing exponentially, acts similar to game with between 2-3 actions per move because most states in the local approximation are duplicates due to both minipacman and the ghost going back and forth. When enumerating the local state space, duplicates can be removed before increasing the length of possible trajectories so that the local state space stored does not grow at the maximum rate in practice. Also note that the size of the local approximation the state space will not be affected if the board size increases because only local states are considered.
Storing Paths:
The predecessor matrix P defined such that Pej is the predecessor of state on a shortest path from i to (and infinity if no such path exists). This matrix is used to retrieve the shortest path between any two states and j. Then strategic state is defined as state s' such that Pst = s' where (ss) = ((s') & é(t), i.e. s' is the last node on the shortest path between states and t that are in two different meta-states that lies in the same meta-state as s. Then, by this definition, we can penalize the number of strategic states.
Number of Meta-states k: The number of meta-states can be chosen using standard techniques as trying different A and finding the knee of the objective (i.e. where the objective has little improvement) or based on domain knowledge. State representations may affect the (appropriate) number.
C REPRODUCING THE EXPERIMENTS
Code for SSX experiments is included. Separate directories and corresponding README files are available for experiments pertaining the three domains: Four Rooms, Door-Key, and Minipacman. Training all models uses default parameters from the respective github repositories used for each environment (links in Section Parameters used for the experiments given in Table T
Table 1: Parameters used for Four Rooms, Door- Door-Key, and Minipaeman experiments
Domain Door-Key
Parameter
Four Doors
Minipacman
strategic states
2
5
from eq. (3)
50.0
1.0
0.1
Eg from algorithm
0.1
0.1
0.1
N steps used for
NA
6
local approximation S
D COMMENTS ON STATE IMPORTANCE
potential baseline for explanations is motivated by the policy summarization method Amir & Amir (2018). Explanations in that work are offered simulated trajectories that deemed important. Importance of states along the trajectory is defined by
(ss) = max T min (s.a))
14

---

Under review as a conference paper at ICLR 2022
Minipacman
Ghost
Food
N
3
4
5
6
N
4
6
N
3
5
6
3
0
0.70
0.92
1.14
3
0
0.88
1.05
2.59
3
0
0.52
0.73
0.84
4
0.85
0.78
0
1.36
2.23
4
0.57
0.93
5
0
1.29
5
0
1.73
5
0
0.88
Table 2: Faithfulness measures for size of local neighhorhood. For Minipacman, measures are distances of minipacman positions strategic states when using different local approximations with varying approximation size N, where N is the maximum number of steps allowed for state to be included. Distances are symmetric (hence use -f.
where (s.n) is the Q-value for policy Te for taking action state By definition, this gives measure of variation (by action) for given state, i.e., the large the potential impact of which action is taken, the higher the importance value. While this measure can successfully be used to select important trajectories that give users an idea of what policy is doing, as done in (Amir & Amir 2018), such important states are not necessarily good representatives of states that one should aim for, as is the goal of strategic states in SSX. on minipacman. Note that there is a negative reward for eating pill in the EAT scenario because the policy is to eat all the regular food while avoiding the ghost. Q-values were estimated using the equation, Q(s,a) r(s,a) (U), where r(s, a) is the reward for taking action in state and is determined by the scenario (EAT or HUNT), t is the state that pacman transitions to by taking taking action a in state 8, and (1) is the value of being in state f. The expectation is taken with respect to the new state (because the ghost moves stochastically after pacman takes action a).
a few examples to demonstrate this property
In both EAT scenarios, important states are found with pacman located directly next the food; indeed, these are important according to the measure in equation (D) because the difference of whether pacman moves away from the pill or eats it is large. However, these are not positions where one would expect to guide pacman in the EAT scenario. Similarly, for the HUNT scenarios, the important states are found where pacman is relatively close to the ghost. For example, in the first row, if pacman moves left, there is chance the ghost will move right and cat pacman, whereas if pacman moves up or down, pacman will continue.
E FAITHFULNESS AND CONSISTENCY OF LOCAL APPROXIMATIONS
We here investigate how sensitive strategic states in SSX are to the size of the local approximation. Let N be the maximum number of steps that can be taken (as referred to above in the discussion on Scalability in Section 3,4). We allow N to vary from 3 to 6 steps and run SSX for the minipacman setup from various starting boards along a trajectory of the HUNT scenario. For each trial, we take the priority strategic state of the cluster containing the initial board and compare it against trials from the same initial board but with different N. We consider three distance metrics for each comparison: the distance between minipacman positions, the distance between ghost positions, and the distance between remaining food indicators of the boards.
Table displays the results. Distance is measured using la norm on the difference of (x.y) coordinates for minipacman and the ghost and the difference of indicators of whether or not food is present for the food. For reference, value of for minipaeman means that minipacman was usually position away (horizontally or vertically) in the two strategic states being compared. Values close to 0 mean that minipacman was often in the same spot in respective strategic states. We first note that distance generally increases the larger the difference of N between trials, as expected. The second note is that the distance of the ghost is larger than that of minipacman, which is also expected as the ghost moves randomly whereas minipacman is driven by the policy.
We next consider the consistency of local approximations by comparing strategic state results from an initial state to that when slightly perturbing the initial state. Consistency is illustrated on minipacman, where perturbations are done by randomly removing 3 pieces of food from the initial state being considered by SSX. For each initial state, 10 additional random perturbations are used, and various initial states along a trajectory are used. Distances are measured as ahThanks described above for minipacman, the ghost, and the food. Results are given in Table 3 Again, minipacman on average
15

---

Under review as a conference paper at ICLR 2022
Avg Distance
Minipacman 0.63
Ghost 1.61
Food
1.32
Table Consistency measures for perturbations of the initial state. For Minipacman, measures are distances of minipacman positions in strategic states when using different initial states (comparing strategic state from initial state to that of a perturbed initial state).
less than one position away when comparing SSX results between two initial states that differ by minor perturbation. As expected, the ghost moves more since the ghost is not controlled by the policy. The distance of 1.32 for food corresponds distance is an l2 norm between the indicator matrices of food). This makes sense as the perturbations make the boards differ by 3 units of food.
difference of close to 3 pieces of food (since
F ADDITIONAL MINIPACMAN EXAMPLES
EAT Scenario 2
HUNT Scenario 2
EAT Scenario 3
HUNT Scenario 3
additional scenarios of minipacman. Two policies, EAT and HUNT, are displayed across the two scenarios. For each scenario, two clusters, one row, are shown part of the SSX result. The last board with pink background is strategic state for each cluster. The color scheme is as follows: green pacman, red = ghost, yellow = edible ghost, cyan pill, blue food, black food eaten, white/pink=wall. In EAT scenarios, pacman generally ignores the pill and stays away from the ghost (even if the pill has been eaten). In HUNT, pacman generally looks for the pill (but stays away if the ghost near it) and moves toward the ghost (if the pill has been eaten).
Figure 7: Illustration of our SSX method
Figure 7 shows results of SSX applied to additional scenarios for the minipacman example. EAT Scenario 2 shows pacman willing to take a chance of being eaten order to get more food and EAT Scenario shows that, even though pacman already ate the pill (the ghost is yellow when the pill is caten), pacman prefers to eat more food rather than head for the ghost. These strategic states contrast directly with those in the HUNT scenarios. Strategic states in Hunt Scenarios and also show pacman eating the pill in order to hunt the ghost rather than eating more food.
G ADDITIONAL USER STUDY INFORMATION
Participants in the user study first read set of instructions where the two environments, hunt and eat, are explained. Further, participants are detailed the color scheme and what they are expected to do with each question of the survey. The full set of instructions are given in Figure g Participants
16

---

Under review as a conference paper at ICLR 2022
then first trained on example each with SSX and Viper-D explanations and were given the reasoning one might use in making their choices. The respective training examples are given in Figures ( and [0] Following the training examples, participants went through series of 20 questions, 10 from each of SSX and Viper-D explanations. The distribution of correct answers for eat versus hunt is 50/50. An example of each type of question with the choices, Eat, Hunt, and Unclear,
shown in Figures [1 and 12
17

---

Under review as a conference paper at ICLR 2022
Al Explanations for Pacman
PLEASE READ CAREFULLY
Thank you so much volunteering to take this survey. No information other what you choose to provide will be recorded in this survey. There are 22 questions and it should take around 10-15 minutes to complete the survey. At the end you can also leave additional feedback. Below are the details of the survey.
Two methods trained simplified version of the popular game Pacman, where just Ghost, one Pill and smaller maze having alightly different objectives.
HUNT: The first method we call HUNT declares Pacman as a winner if he is able to eat the Ghost (after eating the Pill which looks like a big light blue square) without getting eaten himself. There reward for eating food in regular Pacman.
EAT: The second method call EAT declares Pacman winner he able eat all the food (excluding pill). Eating the ghost this case does not buy him any extra browny points.
Each question the survey asks you to guess which one of these two objectives are being explained by the provided visualizations. There are two different types of visualizations, or what call explanations, which we refer to Type A and Type B. Your task is use the provided explanation (either type type surmise the objective (HUNT EAT) underlying method. the end, will ask which these explanation types you prefer based point sufficiency, satisfaction and understanding.
covering qualitative aspects such as completeness.
In all cases, the question is: WHICH METHOD (HUNT or EAT) IS THE EXPLANATION OF TYPE (A EXPLAINING? You also have the option mark UNCLEAR you about the objective given the visualization.
Note the following color scheme the different entities the game.
Color scheme applicable to both explanation types:
Pacman: Green
Pill: Light blue
Ghost before pill is eaten: Red (Ghost hunting Pacman)
Ghost after pill eaten: Yellow (Ghost eaten by Pacman)
Location where wall present: White (background)
There are also explanation specific colors (which will become clear in the next two examples) as follows:
Applicable type A explanation:
Location where food is present: Dark blue (maze paths) Location food
Black (maze paths).
Target state for each row: Pink (background).
Applicable to type B explanation:
Same color scheme indicated in the common part. However, since these rule based explanations regions in the maze are highlighted corresponding to the rule, rather than just specific locations of the different entities (viz. Pacman, Ghost, etc.) in particular state.
now provide one example of each explanation type before starting the survey. Thanks again for taking the survey.
Required
Figure 8: Screenshot of user study instructions. SSX explanations anonymized as Type A explanations and Viper-D explanations are anonymized as Type B explanations.
18

---

Under review as a conference paper at ICLR 2022
Example of type A explanation (no answer required below)
CL
4
The rows above represent three clusters of possible positions all with the same intent (l.e. hunt or eat). The last position each row (with pink background) represents the target position that pacman trying to reach to from all states in that row/cluster (to his left) given the position of everything else (i.e. ghost, food, pill).
For the above example, might guess that the explanation of type explaining the objective HUNT. One possible reasoning is that if the ghost is away from the pill (first row/cluster), Pacman moves to get the pill, while if the ghost is near the pill (rows and 3), Pacman moves stay far from ghost to move away and not worrying about eating more food that is close the pill likely waiting to him (target pink states are where food is already eaten).
Your answer
Figure 9; Screenshot of SSX explanation example used to train the participant taken from user study. SSX explanations are anonymized as Type A explanations.
19

---

Under review as a conference paper at ICLR 2022
Example of type explanation (no answer required below)
Rate used predict movv dowel Food Remainig 5.5 No food to the left, and bocations given below
predict right:: right.
and lecations
Pacman
Chost
PM
predict move
food
food is below, locations given bellow.
Pacman
Chest
Rute used predict 'move right: No food is the left, No food above, and locations given betsee.
Paciman
The above represent five individual rules that each predict the same intent (i.e. hunt eat). The title above each rule says what direction the says Pacman should move, along with additional details about how much food should be remaining and where food is around Pacman. The three boards each row shows where rule says Pacman, the Ghost, and the pill should located (locations being denoted by the green, red, and light blue squares, correspondinglyy. For example, if Pacman, the ghost, and the pill are the potential locations dictated by the board, and food to the right and below Pacman, the rules says that Pacman should move down.
For the above example, one might guess that the explanation type is explaining the objective EAT. One possible reasoning is that the rules suggest Pacman move away from the ghost but, not necessarily, towards, the pill. For example, last rule suggest Pacman move to the right because there is no food to the left, but Pacman were hunting, he'd probably want to go left and get to the possible pill locations faster.
Your answer
Screenshot of Viper-D explanation example used to train the participant taken from user study. Viper-D explanations are anonymized as Type B explanations.
Figure 10:
20

---

Under review as a conference paper at ICLR 2022
1) Which method is the explanation of type A explaining?
CI.2
C
Hunt
Eat
Unclear
Figure 11: Screenshot of SSX explanation survey question taken from user study. SSX explanations anonymized as Type explanations.
21

---

Under review as a conference paper at ICLR 2022
2) Which method the explanation of type explaining?
Pacman
Chost
Rude used to predict move up? Food Remainig
2.5, Roo food the left. Nhe food belon, and locations given belnw.
used prodict
Bemainig 3.5, Remainig Pecman
right.
locations given
Chost
Rulee used predict move food the left. Ne food above, Food below, and locations below
predict 'move down':
food above, locations given
Pecmen
Chost
Hunt
Eat
Unclear
Figure 12: Screenshot of Viper-D explanation survey question taken from user study. Viper-D explanations are anonymized as Type B explanations.
22


Reviews:
[{"review_id": "rOlwhPozcq8", "reviewer": "Reviewer_3j9K", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strength: (1) The paper proposes a new explanation method against deep reinforcement learning\nWeakness: (1) The utility of the explanation is vague and needs more details. (2) the evaluation is insufficient. ", "summary_of_the_paper": "The paper presents an explanation method for deep reinforcement learning. ", "summary_of_the_review": "It seems the method cannot handle exponentially large state spaces. While the authors discuss the scalability issue, it is still difficult for readers like me to understand how to a bounded but exponentially large space. I would like to the authors provide more details. \n\nI would like to see the proposed method applied in more sophisticated games (e.g., Pong and Mujoco games) in which the states cannot be numerated. \n\nThe utility of the explanation is unclear. It would be very helpful if the authors could share their survey questions. That could better help us understand the utility of the explanation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "evArMs3q1fh", "reviewer": "Reviewer_53LC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper explains DRL policies from an interesting perspective, i.e., explaining via prediction. It draws insights into a DRL agent's policy by predicting certain steps of future moves. Although studying an important problem, this paper has the following limitations that prevent me from supporting it. \n\n1. The readability and clarity of this work can be further improved. Due to some unclear terminologies, the proposed technique is not clearly described. Specifically, I would first suggest giving a concrete example to demonstrate the difference among states, meta states, and strategy states, especially strategy states. Neither Fig. 1 nor notions clearly express that. In addition, the papers suddenly throw out many termonologies without explanations, such as state-space topology, bottleneck, strategic policy. To be best of my knowledge, these terminologies are not specific to RL and may cause confusion. I would suggest giving a clear explanation or definition before using them. \n\n2. The proposed technique is actually mainly algorithms 1 and 2, where Algorithm 1 is like a clustering algorithm, and Algorithm 2 is a simple searching algorithm. I thus am a little bit concerned about the technical contribution of this work. It may not be reaching the bar of a top-tier ML conference. Regarding Algorithm 1, I am also wondering if one can directly apply an existing clustering method to replace it, like using K-NN or K-means based on $\\Gamma$. \n\n3. The paper misses a potential baseline that also explains DRL policies through action prediction, i.e., [1]. I would suggest the authors discuss the difference between [1] and the proposed technique and even empirically compare them.  Regarding the user study, existing works utilize user study to compare the utility difference among different explanation methods in identifying good/bad policies, e.g., [2,3]. I would suggest the authors comment on their choice of user study design and why not follow the existing work to compare policy identification ability.  \n\n4. It's not clear the problem space of the proposed technique or, in other words, what types of RL tasks are suitable for the proposed technique. More specifically, I am wondering whether the proposed technique can be applied to widely used Atari and MuJoCo environments or even real-world environments, like Go and Texas hold 'em. \n\n[1] Explain via prediction: What Did You Think Would Happen? Explaining Agent Behaviour through Intended Outcomes, NeurIPS 20.\n\n[2] Visualizing and understanding atari agents, ICML 2018.\n\n[3] Highlights: Summarizing agent behavior to people. AAMAS 2018", "summary_of_the_paper": "This paper proposes a novel explanation method for DRL policies that clusters environment states into meta states and identifies strategic states from meta states as explanations. The paper empirically compares its proposed explanation method with some existing methods on three games and designs a user study to demonstrate its utility. ", "summary_of_the_review": "This paper studies an important problem from an interesting perspective. It explains a policy by predicting certain steps of future moves. In summary, I identify the following limitations from this work:\n\n1. The readability and clarity of this work can be further improved. Due to some unclear terminologies, the proposed technique is not clearly described.\n\n2. The technical contribution may be a little bit thin, and some design choices are not clearly justified. \n\n3. The paper misses a potential baseline that also explains DRL policies through action prediction. \n\n4. It's not clear the problem space of the proposed technique or, in other words, what types of RL tasks are suitable for the proposed technique.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1iZlavZzbrw", "reviewer": "Reviewer_u9SV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "As motivated by the first paragraph of the paper, interpreting RL policies such that a human user understands the reasoning behind these policies is a critical step toward using these policies in a trustworthy manner in real-world domains. Unfortunately, the paper does not show the usefulness of the proposed method on any real-world application. Studied applications are grid games that may not reflect real-world applications such as those that arise in queuing, dynamic pricing, revenue management, among many others. As explained above, the notion of meta-states and strategic states for applications beyond gird games is unclear. Particularly, how should a human user interpret strategic states in real-world applications? The interpretation of strategic states for these applications may not be as simple as doors in a grid game. Therefore, at the very least, I recommend authors provide detailed explanations on how their approach can be employed in real-world settings, i.e., in robotics and business applications. Moreover, conducting a numerical study that applies the proposed method to a real-world application can significantly add to the paper's contributions.\n\nThe authors assume that the dynamics of the expert policy π_E, denoted f_E, are known apriori, and thus Γ can be computed exactly and provided to Algorithm 1 as an input. However, such dynamics are often unknown in practice and should be estimated through policy simulation, that is, one can only estimate f_E by simulation of π_E. Authors need to pose their method and the computation of matrix Γ through policy simulation. \n\nTo build on my previous concern, computing the entire matrix Γ, as done in the current version, is expensive and seems unnecessary. In many domains, a good policy (i.e., the expert policy) only visits a small subset of states with a non-negligible probability. In this case, is not it enough to restrict the computation of Γ to such states? If so, authors can more efficiently compute Γ by only focusing on the states observed by π_E during simulation. Please also comment on the computational cost of getting the eigen decomposition of the Laplacian of Γ needed in Algorithm 1. Can this be efficiently computed for large-scale problems? Given the current manuscript, I am not convinced that the computation of Γ and its Laplacian eigen decomposition are tractable for large-scale problems. \n\nThe authors mentioned the convergence of their method multiple times in the paper without carefully explaining what their algorithm converges to.  Proposition 1 proves the convergence of Algorithm 1 without identifying what does Algorithm 1 converges to. Can authors show that if a given expert policy induces a collection of k meta-states \\{Φ_1^E,…,Φ_k^E \\}, then Algorithm 1 converges to this set of meta-states? If not, how the output of Algorithm 1 is connected to the expert policy? The current version of Proposition 1 is not insightful. Moreover, the convergence results in Algorithm 1 should be presented when Γ is estimated through policy simulation and not when Γ  is known exactly (please see my comments above). \n\nI wonder how the choice of parameter η affects the interpretability of the expert policy. Some theoretical or empirical studies are useful here. For example, the authors can explain in the extreme cases of η being zero and being a large number, how does Figure 1-a change? Is there a need for fine-tuning η to get human-understandable meta-states? Moreover, how does Figure 1-a change for different values of λ?\n\nIt is not clear if the program (3) has a unique solution or not. I think there are examples at which multiple strategic states exist, given a fixed m and meta-state. In the case of degeneracy, how should a human user choose a solution? I encourage authors to comment on this.\n\n\nMinor comments.\n\t\nConsider rewriting the sentence “… which act as intermediate goals for states belonging to a particular meta-state”. I had read this sentence multiple times to understand what a strategic state means. \n\nTerm “policy dynamics” is unclear in Section 1. Authors may need to explain what they mean by policy dynamics in that section.\n\nColoring in Figure 1 is hard-to-follow. Please consider using different colors and using different markers.\n\nThe sentence “While one could discretize the state space, it would be interesting to see if it can be symbiotically done” is misleading. In many real-world continuous-state MDPs, discretizing the state-space leads to poor approximations and is thus not a solution.\n\nFigure 2 is very confusing. I had to read the text and check the figure multiple times. Is there a way to enhance it?", "summary_of_the_paper": "The paper proposes an approach to interpret a black-box control policy of a reinforcement learning (RL) problem such that its interpretations can be understood by a human user. For a given expert policy (i.e., a fitted deep neural network), the proposed approach uses transition probabilities induced by the expert policy to define regions of the state space that are “similar.” These policy-dependent regions are referred to as meta-states and are computed using an algorithm similar to spectral clustering. The proposed method then computes so-called strategic states for each meta-state, where strategic states of a meta-state are those states that belong to the meta-state and bridge the meta-state to other ones. In other words, the expert policy should pass through the strategic states frequently when it goes from one meta-state to another. The paper performs numerical experiments using standard RL applications, i.e., four rooms, door-key, and mini-Pacman, to show the effectiveness of the proposed approach.", "summary_of_the_review": "My overall impression of the paper is positive, but I have several concerns. My most critical concern is that given the theory and numerical experiments in the current manuscript, I am not sure if the proposed approach delivers human-understandable interpretations of RL policies in applications beyond grid games arising in robotics, flight control, multi-armed bandit, etc. In other words, the proposed method seems to work only for the grid games, and it is unclear how a human user should interpret meta-states and/or strategic states in applications beyond grid games. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-Bs2docOHBX", "reviewer": "Reviewer_GrkK", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "#### Local vs Global Confusion: \n\n-The authors state \"our focus is on local explanations,\" and use this to discount existing \"local\" works while not comparing to \"global\" works. However, in other places in the text, SSX is treated as producing global explanations. SSX is \"local\" only in the sense that, for larger domains, approximations are made to address scalability issues. Especially when discussing experiments, the authors use explanations to comment on overall (global) policy behavior (e.g., study subjects are asked about overall behavior not per-state behavior).\n\n-As a specific example, TLdR automatically finds landmark states based on transitions between states. This approach does differ from SSX but not to the degree mentioned in this work (which labels it a \"global summary\" method, unlike SSX). At the very least, TLdR is a good candidate for comparison.\n\n#### Complexity Concerns:\n\n-The authors note that directly applying SSX is not feasible, so a local neighborhood is used. The faithfulness of such a local approximation is not evaluated (e.g., run approximation for different N and non-approximate approach, then compare resulting explanations). \n\n-However, each neighborhood requires a number of samples exponential in the \"radius\" of the neighborhood. Experiments use a \"radius\" of at most 6. This is low for the use-cases used to motivate this work. To produce explanations for larger domains, even a single local neighborhood may not be feasible to explain.\n\n-The authors do not present a way to combine local neighborhoods. As neighborhood \"radius\" is decreased (to address exponential complexity) the number of neighborhoods to combine increases. It is unclear how to explain behaviors that consist of more actions than the neighborhood diameter. The consistency of explanations for adjacent explanations is not evaluated (e.g., produce Figure 1 for different neighborhoods, then look at whether states labeled by multiple neighborhoods create a consistent explanation).\n\n-The sharding process implicitly relies on access to a simulator to efficiently gather samples centered around different states. This is not acknowledged as a requirement/shortcoming of SSX.\n\n#### Positioning wrt Related Work:\n\n-Most relevant past work has been mentioned! Unfortunately, mentioning this work is insufficient to position SSX with respect to past work. SSX's methodology is indeed different from past work, but its final product (set of clusters with representative example(s) for each) is not novel. The authors note that some past work has \"the intent of efficient learning rather than interpretability\" but a different intent does not make a method sufficiently novel. Please position SSX with respect to past global methods, making the differences clear.\n\n-SSX is only compared with VIPER-D. Other works should be included in this comparison, especially works that produce similar cluster / meaningful state explanations. Relatedly, \"they require estimating Q-values ... which relies on sensitive hyperparameter tuning\" does not seem like a valid reason to exclude a work from this comparison.\n\n-The authors note that other state clustering methods may not map adjacent states to the same meta-state. However, SSX does not do always do this either, as seen in Figure 2.\n\n#### Problems with Example Explanations:\n\n-Explanations for Fig 2-3 are based on starting states within a single trajectory. I am concerned that the clusters exhibit \"common\" behavior within themselves specifically because the starting states are spaced apart. (e.g., if neighborhoods have radius 6 and clusters are m>6 steps apart, then of course each cluster will have similar states) To test this, multiple trials should be run and similarity should be measured across trials. Is SSX effectively just segmenting a trajectory for these figures? Please explicitly test this by comparing to baseline methods (such as creating a single \"cluster\" from each neighborhood around each starting state).\n\n-There appears to be manual tuning that is insufficiently explained. How were the starting states chosen for the different neighborhoods? How were clusters chosen for showcasing? (i.e., Fig 3 has odd cluster numbers, as though some were manually chosen to show)\n\n-The explanations given for Fig 2 (arguing that the clusters exhibit meaningful, distinct behaviors) do not match what is shown in the figure. There are images in later clusters despite occurring earlier in the episode. Specifically, \"Unlocked Door, second row, third column\" is several steps through the door despite being part of the \"going through the door\" cluster, despite \"third row, second column\" being an earlier state and in the \"moving toward the target\" cluster.\n\n#### Problems with Human Study:\n\n-It is great that a human study was done. The right feedback is being gathered from human subjects.\n\n-VIPER-D and SSX differ among several axes, so SSX's success cannot be attributed to the specific qualities pointed out by the authors. For example, VIPER-D uses a different output representation (distinct from both SSX and original VIPER).\n\n-In addition to not including past works in this comparison, a number of baselines are missing to determine which aspects of SSX are helpful. Please add these comparisons to show that SSX is meaningfully better due to its clustering approach. Perhaps showing states leads to subject satisfaction (should compare to randomly grouped past experiences)? Perhaps the trajectory is being segmented by clusters (should compare to \"local neighborhood around equally spaced starting states\")? \n\n-VIPER-D is unnecessarily modified and likely performing worse than original VIPER. VIPER can already handle discrete states. VIPER is designed to work with an iterative state gathering method, not simply the full state space as done here. ", "summary_of_the_paper": "This work proposes to explain an RL policy by clustering states into meta-states and presenting strategic state(s) for each meta-state. This clustering is performed based on policy rollouts, balancing likelihood of paths within a meta-state and number of paths from states within the meta-state. The authors present example explanations for three domains. A user study is performed to compare VIPER-D to the proposed method (SSX).", "summary_of_the_review": "The authors present a new way (SSX) to create a certain style of explanation, but the style itself is not novel. SSX is not shown to be better than existing methods. Furthermore, its computational complexity is concerning, and the authors do not fully address how to apply their method to larger domains. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new perspective for understanding reinforcement learning policies based on meta-states, as an effort to improve the explainability of RL control policies. After reviewing the revised paper and reading the comments from the reviewers, here are my comments:
 
- The paper is well-written and very concise.
- The strategy is novel and deserves merit.
- The utility of the explanation is not well described.
- The main concerns of the proposal are the utility of the explanation (that is not well described) and its usage in large discrete state spaces or continuous state spaces domains. 
 
From the above, it is difficult to see the contribution and applicability of the paper in a clear manner.
Decision: Reject