Bridging the Gap: Providing Post-Hoc Symbolic Explanations for Sequential Decision-Making Problems with Inscrutable Representations
Authors: Sarath Sreedharan
Utkarsh Soni
Mudit Verma
Siddharth Srivastava
Subbarao Kambhampati
Venue:  (2021)
Keywords: Explanations
Concept based explanations
Learning symbolic representations
Sequential Decision Making
Planning
Reinforcement learning.

Abstract: As increasingly complex AI systems are introduced into our daily lives, it becomes important for such systems to be capable of explaining the rationale for their decisions and allowing users to contest these decisions. A significant hurdle to allowing for such explanatory dialogue could be the vocabulary mismatch between the user and the AI system. This paper introduces methods for providing contrastive explanations in terms of user-specified concepts for sequential decision-making settings where the system's model of the task may be best represented as a blackbox simulator. We do this by building partial symbolic models of a local approximation of the task that can be leveraged to answer the user queries. We empirically test these methods on a popular Atari game (Montezuma's Revenge) and modified versions of Sokoban (a well-known planning benchmark) and report the results of user studies to evaluate whether people find explanations generated in this form useful.

Under review as a conference paper at ICLR 2021
BRIDGING THE GAP: PROVIDING POST-HOC SYMBOLIC EXPLANATIONS FOR SEQUENTIAL DECISION-MAKING PROBLEMS WITH INSCRUTABLE REPRESENTATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
As increasingly complex Al systems are introduced into daily lives, it becomes important for such systems to be capable of explaining the rationale for their decisions and allowing users contest these decisions. A significant hurdle to allowing for such explanatory dialogue could be the vocabulary mismatch between the user and the Al system. This paper introduces methods for providing contrastive explanations terms of user-specified concepts for sequential decision-making settings where the system's model of the task may be best represented as a blackbox simulator. We do this by building partial symbolic models of a local approximation of the task that can be leveraged answer the user queries. We empirically test these methods on popular Atari game (Montezuma's 's Revenge) and modified versions of Sokoban (a well known planning benchmark) and report the results of user studies to evaluate whether people find explanations generated in this form useful.
INTRODUCTION
For AI systems be truly effective in the real world, they need to not only be capable of coming up with near-optimal decisions but also be capable of working effectively with their end users. One of the key requirements for such collaboration would to allow users to raise explanatory queries wherein they can contest the system's decisions. An obstacle to providing explanations to such questions the fact that the systems may not have shared vocabulary with its end users or have an explicit interpretable model of the task. More often than not, the system may be reasoning about the task in hiih--iieeeee digh-dimensional space that is opaque to even the developers of the system, let alone a lay user.
While there is a growing consensus within the explainable Al community that end-user explanations need to be framed in terms of user understandable concepts, the focus generally has been intro- ducing such methods for explaining one-shot decisions such as in the case of classifiers (c.f. Kim al. (2018); Riibeiro al. (2016)). This unfortunate as explaining sequential decision-making problems presents many challenges that are absent from the one-shot decision-making scenarios. In such problems, we not only have deal with possible interrelationship between the actions in the sequence, but may also need to explain conditions for the executability of actions and the cost of user
executing certain action sequences. Effectively, this means that explaining plan or policy would require the system to explain the details of the domain (or at least the agent's 's belief of it).
In this paper, we propose methods that are able to field some of the most fundamental explanatory queries identified in the literature, namely contrastive queries, i.e., questions of the form 'why P (the decision proposed by the system) and not Q (the alternative proposed by the user or the foil)?' (Miller 2018). in user-understandable terms. Our methods achieve this by building partial and ab- stract symbolic models (Section 2 expressed in terms of the user's 's vocabulary that approximates task details relevant to the specific query raised by the user. To the best of our knowledge, we are the first work to propose learning of symbolic local approximations of the problem dynamics and cost function for explanations in sequential decision-making scenarios. Specifically, will focus

---

Under review as a conference paper at ICLR 2021
deterministic tasks where the system has access to task simulator and we will identify (a) missing preconditions to explain scenarios where the foil raised by the user results in an execution failure of action and (b) cost function approximations to explain cases where the foil is executable but subop- timal (Section 3). We learn such models by interacting with the simulator (on randomly sampled states) while using learned classifiers that detect the presence of user-specified concepts in the sim- ulator states. Figure presents the overall flow of this process with illustrative explanations in the context of a slightly updated version of Montezuma's 's Revenge (Wikipedia contributors (2019). Our methods also allow for the calculation of confidence over the explanations and explicitly take into account the fact that learned classifiers for user-specified concepts may be noisy. This ability to quantify its belief about the correctness of explanation is an important capability for any post-hoc explanation system that may influence the user's decisions. We evaluate the system on two popu- lar sequential decision-making domains, Montezuma's 's Revenge and modified versions of Sokoban (Botea et al., 2002) (a game involving players pushing boxes to specified targets). We present user study results that show the effectiveness of explanations studied in this paper (Section
2 BACKGROUND
Our focus here is to address cases where a user is trying to make sense of agent behavior that may in fact be optimal in the agent's model of the task but is confusing to the user ow- ing to a differing understanding of the task (or them overlooking some facts about the task). Thus our focus isn't on how the agent came up with the specific decisions, but only on why this action sequence was chosen instead of alternative that the user ex- pected. We assume agent has access to a deterministic simulator of the form Mssm (S, T, C), where S represents the set of possible world states, A the set of actions and T the transition function that specifies the task dynamics. The transition function is defined as T: S' + SU(1), where 1 corresponds to an invalid absorber-stade staate generated by the execution of an infeasible action. Invalid state could be used to capture failure states that could occur when the agent violates hard constraints like safety constraints. Finally, C S x A - IR captures action
Garne state vitcuibaatio
Concept Clasvlerrs
Fot Undee
Full: 1e mare lof 1i
User
Explendor
Jone Jors le presecttin
spporration
caree
User
Fullh: sntoc
Oiphesatee:
Alcol cott le presecee
Denaier speniing C1
The teallsc el lnt prite Uh und
the cost function of executing state (with the cost of an infeasible action taken to be infinite). We will overload the transition function and cost functions to also take in sequence of actions (which in the case of the transition function returns the final state resulting from executing the action sequence and for cost function the cost of executing the sequence actions). We will consider goal-directed agents that are trying to drive the state of the world to one of the goal states. Where the tuple 11imm (L, G. MMsm)) represents the agent's 's decision making problem (I is the initial state and G the set of goal states). The agent comes up with plan (a sequence of actions) π such that T(4, E G and the plan is said to be optimal if there exists no cheaper plan that achieves the goal.
particular
Figure 1: Explanatory dialogue starts when the user presenting a specific alternate plan (foil). We consider two foils, one that is in- valid and another that is costlier than the plan. System explains the invalid plan by pointing out an action precondition that was not met in the plan, while it explains the foil suboptimality by informing the user about cost function. These model information are expressed in terms of concepts specified by the user which we operationalize by learn- ing claxsifiers for each concept.
We will use symbolic action models with preconditions and cost functions (similar to STRIPS models (Geffner& & Bonet 2013)) as a way to approximate the problem for explanations. Such a model can be represented by the tuple Ms. = (Fs, As, Is. Gs. Cs), where Fs is a set of propositional fluents defining the state space, As the set of actions, Is is the initial state, Gs is the goal specification. Each valid problem state in the problem is uniquely identified by the subset of fluents that are true in that state (so for any state s E SMs. where SMs is the set of states for Ms. C Fs). Each action E As is further described in terms of the preconditions prec, (specification of states in which a is executable) and the effects of executing the action. We will denote the state formed by executing action a in a state s as a(s). We will focus models where the preconditions are represented as a conjunction of state factors. If the action is executed in a state with missing preconditions, then the execution results in the invalid state (1). Unlike standard
2

---

Under review as a conference paper at ICLR 2021
STRIPS models, where the cost of executing action is independent of states, will be using state dependent cost function of the form Cs : 2" x As + R to capture the cost of valid action exccutions. Internally, such state models may be represented using conditional cost models of the type discussed in (Geißer et al., 2016). In this paper, we won't try to reconstruct the exact cost function but will rather try estimate abstract version of the cost function.
CONTRASTIVE EXPLANATIONS
The specific explanatory setting, illustrated in Figure ! that we are interested in studying involves a Decision-making problem specified by the tuple gim (I. G...)) for which the system identi- fies plan и. When presented with the plan, the user of the system may either accept it or responds by raising an alternative plan Ty (the foil) that they believe should be followed instead. Now the system would need to provide an explanation as to why the plan π may be preferred over the foil y. by showing that the foil is invalid or it is costlier than the plan More formally,
Definition
The plan a is said to be preferred over a soil n for a problem Ieim = (I, G, Msim). if either of the following conditions are met, i.e., (1) f is invalid, if T(I,Ty) & G. i. the action sequence doesn't 't lead to a possible goal state, or (b) the execution of the plan leads to an invalid state, Le., T[),5t) 1. (2) Or y is costlier than n,, i.e., C(I, < C(T,
To concretize this interaction, consider the modified version of Montezuma's 'ss revenge (Figure D. The agent starts from the highest platform, and the goal is to get to the key. The specified plan m may require the agent to make its way to the lowest level. jump over the skull, and then go to the key with a total cost of 20. Now the user raises two possible foils that are quite similar to π, but, (a) in the first foil, instead of jumping the agent just moves left (as in it tries to move through the skull) and (b) in the second, instead of jumping over the skull, the agent performs the attack action (not part of the original game, but added here for illustrative purposes) and then moves on the key. Using the simulator, the system could tell that in the first case, moving left would lead to an invalid state, and in the second case, the foil is costlier. Though it may struggle to explain what particular aspects of the state or state sequence lead to the invalidity or suboptimality. Even if it could identify parts of its own internal state representation as an explanation, it would not necessarily be meaningful to the end-user. This scenario thus necessitates the use of methods that are able to express possible explanations in terms that the user may understand.
Concept maps: In this setting, the system would need mapping from its internal state represen- tation to a set of high-level concepts that are known to the user (for Montezuma this could involve concepts like agent being ladder, holding onto the key, being next to the skull, etc.). We will as- sume each concept corresponds to a propositional fact that the user associates with the task's states and believes that the dynamics of the task are determined by these concepts (the specifies of the representational assumptions made by this paper can be found in the appendix). This means that as per the user, for each given state, a subset of these concepts may be either present or absent. We will assume access to binary classifiers for each of these concepts. These classifiers provide us with a way to convert simulator states to a factored representation. Such techniques have not only been used in explanation (c.f. Kim et al.] (2018): [Hayes & Shah (2017)) but also in works that have looked at learning high-level representations for continuous state-space problems (c.f. Konidaris et al. (2018)) Let C be the set of classifiers corresponding to the high-level concepts. For state 8 S, we will overload the notation C and specify the concepts that are true as C(s), i.e.. C(s) = {clc overload the notation to also stand for the label of the 7th concept). The user could specify the set of concepts by identifying positive and negative example states for each concept. These examples could then be used to learn the required classifiers by using algorithms best suited for the internal simulator state representation. Thus the system should have some method of exposing simulator states to the user. A common way to satisfy this requirement would be by having access to visual representations for the states. The simulator state itself doesn't 't need to be an image as long as we have a way to visualize it (for example in Atari games where the states can be represented by the RAM state of the game controller but we can still visualize them).
C()(s)) = 1} (where c; is the classifier corresponding to the 7th concept and we
Explanation using concepts: To explain why given foil is not preferred over the specified plan, we will present information about the symbolic model expressed user's vocabulary, M =
'ff the foil is as good as the original plan, then the system could switch foil without loss of optimality.
3

---

Under review as a conference paper at ICLR 2021
Where = - C(sy) and AS contains a definition for each action a E A. The model is said be local symbolic approximation for the simulator for regions of interest å S S if M is a sound abstraction of the simulator Mssi - (S. A,T,C) for S. That is Vs E $ and Va E A, we have an equivalent action at E AG, such that a (C(((s) = C(T(s, a)) (assuming C(1) = 1) and C)(C(s), a) = C(s,a). Note that establishing the preference of plan does not require informing the users about the entire model, but rather only the relevant parts. For conciseness, we will use d; for both the simulator action and the corresponding abstract action in the symbolic model as long as the context allows it to be distinguished.
(C, C(G),
=
To establish invalidity of x we just need to focus on explaining the failure of the first failing action di i.e., the last action in the shortest prefix that would lead to invalid state (move-left action in the state presented in Figure D for the first foil). We can do so by informing the user that the action has an unmet precondition, per the symbolic model, in the failing state. Formally
Definition 2 For failing action ag for the foil of = (a1, Usy and G. E C is considered an explanation for failure if a E preca; \ C(ss), where 8; is the state where ag is meant to be executed (i.e s; = -(I, (a1..., (z.1))).
In the example invalid foil, the explanation would inform the user that move-left can only be exe- cuted in states for which the concept skull-notoon-let is true; and the concept is false in the given state. This formulation is enough to capture both conditions for foil invalidity by appending an ad- ditional goal action at the end of each sequence. The goal action causes the state to transition to an end state and it fails for all states except the ones in G. Our approach to identifying the minimal explanation for specific query follows from studies in social sciences that have shown that selectivity or minimality is an essential property of effective explanations Miller (2018).
For explaining suboptimality, we have to inform the user about Cg. To ensure minimality of expla- nations, rather than provide the entire cost function or even the individual conditional components of the function, we will instead try to learn and provide an abstraction of the cost function Cubs
Definition 3 For the symbolic model M = (C, 43, C()). CS), an abstract cost function Cg 2dd x AS + &RA is specified as follows Cishe (fcI,.., C& J a) = min (s, a)]s E &Mgg. A (c)....c)) C s).
Intuitively, Cgsa (fci,.,, Cx),,, = k can be understood as stating that executing the action in the presence of concepts (cI,.., G costs at least k. We can use Cg in an explanation of the form
Definition 4 For valid foil TT = -(a,,.,, a plan π and a problem Ismm the sequence of concept sets of the form Cay = =(Ci,..,Ck along with Cabe is considered a valid explanation for relative suboptimality of the foil (denoted as Cg "C=" mg)) > C(I,T)) if VC; E Czy, C2 is subset of concepts presents in the corresponding state (where state is I for i = 1 and T(I, (ai,..,, i >> 1) and (1=(1.x) C5C (C..a.) C(I, x)
In the earlier example, the explanation would include the fact that executing the action attack in the presence of the concept
will cost at least 500 (as opposed to original plan cost of 20).
IDENTIFYING EXPLANATIONS THROUGH HAMPLE-BASEL TRIALS
For identifying the model parts for explanatory query, we will rely on the agent's ability to interact with the simulator to build estimates. Given the fact that we can separate the two cases at the simulator level, we will keep the discussion of identifying each explanation type separate and only focus on identifying the model parts once we know the failure type.
Identifying failing precondition: To identify the missing preconditions, we will rely on the simple intuition that while successful execution of an action in the state sj with concept C; doesn't 't necessarily establish that C2 is precondition, we can guarantee that any concept false in that state can not be a precondition of that action. This is a common line of reasoning exploited by many of the model learning methods (c.f CCrbbonll & Gil (1990); Steen & Juba )) We start with the set of concepts that are absent in the the state (Stal) where the failing action (ama) was executed, i.e., poss. ceespppee..oo set C C(ssa) We then randomly sample for states where dgai is executable. Each new
sampled state s, where the action is executable can then be used update the possible precondition set as poss-prec_set = poss poss_pree pprecsett n C(s:). That is, if a state is identified where the action is executable but a concept is absent then it can't 't be part of the precondition. We will keep repeating this sampling step until the sampling budget is exhausted or if one of the following exit conditions is met. (a) In cases where are guaranteed that the concept list is exhaustive, we can quit as soon
4

---

Under review as a conference paper at ICLR 2021
as the set of possibilities reduce to one (since there has to be a missing precondition at the failure state). (b) The search results in an empty list. The list of concepts left the end of exhausting the sampling budget represents the most likely candidates for preconditions. An empty list here signifies the fact that whatever concept is required to differentiate the failure state from the executable one is not present in the initial concept list (C). This can be taken as evidence to query the user for more task-related concepts. All locality considerations for sampled states, say focusing on states close to the plan/foil, can be baked into the sampler. The exact algorithm provided in the appendix.
Identifying cost function: We will employ a similar sampling based method to identify the cost function abstraction. Unlike the precondition failure case, there is no single action we can choose but rather we need to choose a level of abstraction for each action in the foil (though it may be possible in many cases to explain the suboptimality of foil by only referring the foil). Our approach here would each step such that of the total cost of the foil becomes greater than that of the specified plan. Thus for foil f = (a1...., az) our objective become mine, E..,,.A/
subset of actions in to find the most abstract representation of the cost function at
C|C:
subject to Ca (Cx,, > x(I
(C,, For any given C, CCte(C,, a,) can be approximated by sampling states randomly and finding the minimum cost of executing the action a; in states containing the concepts C, We can again rely on sampling budget to decide how many samples to check and enforce required locality within sampler. Similar to the previous case, we can identify the insufficiency of the concept set by the fact that we aren't i able to identify a valid explanation. The algorithm can be found in the appendix. Confidence over explanations: Though the methods discussed above are guaranteed to iden- tify the exact model in the limit, the accuracy of the methods is still limited by practical sam- pling budgets we can employ. For example in the case of precondition failure, at the end of sampling we are not guaranteed that the concept we end up choosing is in fact the true precondition or if generating more samples would have eliminated it. So this means it is important that we are able to establish some level of confidence in the solutions identified. To assess confidence, we will follow the probabilistic relation- ship between the random variables as captured by Figure 2 (A) for precondition identification and Figure 2 (B) for cost calculation. Where the various random variables captures the following facts: O indicates that action can be executed in state 8, G E Pa concept C is a precondition of a, O
Moquna
oz
O5
the concept e; is present in state s, Cake (fc;), a) 2 k the abstract cost function is guaranteed to be higher than or equal to k and finally Oc(a,))2* stands for the fact that the action execution in the state resulted in cost higher than equal to k. We will allow for inference over these models, by relying on the following simplifying assumptions - (1) the distribution of concepts over the state space is independent of each other, (2) the distribution of all non-precondition concepts in states where the action is executable is the same as their overall dis- tribution across the problem states (which can be empirically estimated), (3) cost distribution of an action over states corre- sponding to a concept that does not affect the cost function is identical to the overall distribution of cost for the action (which can again be empirically estimated). The second assumption implies that the likelihood of seeing a non-pree non-preconnitionn concept sampled state is equal to the likelihood of it appearing in any sampled state (this distribution is denoted as Pe.). ). While the third one implies that for a concept that has no bearing on the cost function for an action, the likelihood that executing the action in a state where the concept is present will result in a cost greater than & will be the same as that of the action execution resulting in cost greater than k for randomly sampled state (a)(..))))) For single sample, the posterior probability of explanations for each case can be expressed fol- lows: For precondition estimation, updated posterior probability for a positive observation can be computed as P(c. E PelO0, A O.) (1 P(c. & Pa IOS, A OZ)), where
A2
05
(0)
A simplified probabilis- tic graphical models for explanation inference, Subfigure (A) and (B) as- sumes classifiers to be completely cor- rect. while (C) and (D) presents cases with noisy classifier.
Figure 2:
P(c: & Pa 1%, A A Pe, P(c. & p.))
P(O:; OO:)
and for the case of cost function approximation
((C.))((=)),,)) 2
((C,)(((<)) a) 2 kOO,, A Oc(sa)2a) P(Cyba((c)) 2 R)) + PC(..)24 * ((-Ce>((a)) 2 k))
Full derivation of above formulas can be found in the appendix. The distribution used in the cost explanation, can either be limited to distribution over states where action a; is executable or allow
5

---

Under review as a conference paper at ICLR 2021
for the cost of executing an action in a state where it is not executable to be infinite.
Using noisy concept classifiers: Given how unlikely it is to have access to perfect classifier for any concept, a more practical assumption to adopt could be that we have access to a noisy classifier. However, we assume that we also have access to a probabilistic model for its prediction. That is, we have access to function Pc C + J0. 1] that gives the probability that the concept predicted by the classifier is present in the state. Such distributions could be learned from the test set used for learning the classifier. Allowing for noisy observation generally has a more significant impact on the precondition calculation since we can no longer use a single failure (execution of an action in state where the concept is absent) as evidence for discarding the concept. Though we can still use it as evidence to update the probability of the given concept being precondition. We can remove a particular possible precondition from consideration once the probability of it not being a precondition crosses a specified threshold. To see how we can incorporate these probabilistic observations into our confidence calculation, consider the updated relationships presented in Figure (C) and (D) for precondition and cost function approximation respectively. Note that in previous sections, made distinction between the concept being part of the state and actually observing the concept. Now we will differentiate between the classifier saying that a concept is present (0%) from the fact that the concept is part of the state (eg C(S)). Now can use this updated model for calculating the confidence. We can update the posterior of a concept not being precondition (O".,) using the formula
given a negative observation
P(c. & PalO"., A O P(O la E Pa A O2) + P(e; & pa PalO:)
P(O-c, Oa)
Similarly we can modify the update for a positive observation to include the observation model and also do the same for the cost explanation. This can either be empirically calculated from samples with true label or we can assume that this value is going to be approximately equal to the overall distribution of the cost for the action. The derivations for all of the above expressions and formulas for the other cases can be found in appendix. Note all the experiments reported in this paper were performed using this noisy classifier formulation. In fact, for Montezuma's revenge we saw that the original formulation couldn't in fact identify the correct concepts.
5 EVALUATION
We tested the approach on the open-Al gym's deterministic implementation of Montezuma'ss s Revenge (Brockman et al. (016)) for precondition identification and two modified versions of the gym implementation of Sokoban (Schrader) 2018) for both precondition and cost function identification. Appendix contains the images for all the foils, plans used for each domain.
Montezuma's 's Revenge: We used RAM-based state representation for Montezuma. To add richer preconditions the settings, we added wrapper over the original simulators for all the games to render any non-noop action that fails to change the current agent state as an action failure. We selected four invalid foils (generated by the authors by playing the game), three from screen 1 and one from screen 4 of the game. We specified ten concepts for each screen and collected positive and negative examples for each concept by sampling through the state space. We used AdaBoost Classifier (Freund et al.] 1999) for concept and had an average accuracy of 99.72%.
Sokoban Variants: We used an image-based representation for these domains and had two variations on the standard Sokoban game. One that requires switch the player could turn on before pushing the box (we will refer to this version as Sokoban-switch) and the second version (Sokoban-cells) included particular cells from which it is costlier to push the box. For Sokoban-switch, we had two variations one in which turning on the switch was a precondition for the action and another one in which it merely reduced the cost of pushing the box. The plan and foil were generated by the authors by playing the game. Additionally, we made sure the plan was part of the optimal policy. We used a survey to collect the set of concepts for these variants. The survey allowed participants to interact with the game through a web interface (the cost based version for Sokohan-switch and Sokohan-cell), and at the end, they were asked to specify game concepts that they thought were relevant for particular actions. We received 25 unique concepts from six participants for Sokoban-switch and 38 unique concepts from seven participants for Sokoban-cell. We converted the user descriptions of concepts to scripts for sampling positive and negative instances. Consequently, we focused on 18 concepts and 32 concepts for Sokoban-swine and Sokoban-cel respectively based on the frequency with which they appear in game states and used Convolutional Neural Networks (CNNs) for the classifier. The classifiers had an average accuracy of 99%4 for Sokoban-switch and 99.34% for Sokoban-cell. The exact filtering conditions

---

Under review as a conference paper at ICLR 2021
provided used along with the network details and hyperparameters are provided in the appendix. Explanation identification: We ran the search for identifying preconditions for Montezuma 's foils and Sokoban-switch and cost function identification concepts, we doubled the final concept list used by including negations of each concept (so 20 each for Montezuma and 36 and 64 for Sokoban variants). The probabilistic models for each classifier were calculated from the corresponding test sets. For precondition identification, the search was run with a sampling budget of 500 and a cutoff' probability of 0.01 for each concept. The search was able to identify the expected explanation for each foil. For Montezuma, the explanations had mean confidence of 0.5044 for foils in screen and a confidence value of 0.8604 for the foil in screen 4. The ones in screen 1 had lower probabilities since they were based on more common concepts and thus their presence in the executable states was not strong evidence for them being a precondition. For Sokoban-switch the confidence was 0.7279. For cost function identification, the search was run with a sampling budget of 750, and all the calculations, including both computing the concept distribution and updating the probability of explanation, were limited to states where the action was executable. Again the search was able to find the expected explanation. We had average confidence of 0.9996 for the Sokoban-switch and 0.998 for the Sokoban-cell.
both Sokoban. From the collected list of
User study: With the basic explanation generation methods in place, we were interested in evaluating if users would find such an explanation helpful. All studies were performed while following local IRB protocols. Screenshots of interface used for the study along with additional details can be found in the appendix. Specifically, the hypotheses we tested were Hypothesis 1: Missing precondition information is useful explanation for action failures. Hypothesis 2: Abstract cost functions are a useful explanation for foil suboptimality.
Hypothesis 3: Concept based precondition explanations help users understand the task better than saliency map based ones.
For HI and H2, we went with a within-subject study design where the participants were shown an explanation generated by our method along with a simple baseline. For precondition case (HI), the baseline involved pointing out just the failing action and the state it was executed. For the cost case (H2), it involved pointing out the exact cost of executing each action in the foil. The users were asked to choose the one they believed was more useful (the choice ordering was randomized to ensure the results were counterbalanced) and were also asked to report on a Likert scale the completeness of the chosen explanation. For each foil, we took the explanation generated by the search and converted it into text by hand. For HI, we collected 20 replies in total (five per foil) and 19 out of the 20 participants selected precondition based explanation as the choice. On the question of whether the explanation was complete, we had an average score of 3.47 out of 5 on the Likert scale (1 being not at all complete and being complete). For H2, we again collected 20 replies in total (ten per foil) and found 14 out of 20 participants selected the concept-based explanation over the simple one. The concept explanations had on average a completeness score of 3.21 out of 5. The results seems to suggest that in both cases people did prefer the concept-based explanation over the simple alternative. The completeness results suggest that people may like, at least in some cases, to receive more information about the model.
H3 is particularly interesting in the case of precondition failures because under specific settings a Saliency map based explanation could highlight areas corresponding to failed precondition concepts (especially when concepts corresponds to local regions within the image). Though even in such cases the user has to still figure out what concepts these highlighted regions may correspond to and from the highlighted concepts figuring out the one that might be the actual precondition. We measured the user's understanding of the task by their ability to solve the task themselves. Here we went with a hetween-subject study design. Each participant was allowed to play the precondition variant of the sokoban-switch game. They were asked to finish the game within 3 minutes and were told there would be bonuses for people who finish the game in the shortest time. During the game, if the participant performs an action whose preconditions are not met, then the current episode ends and they have to restart the game. Whenever such an invalid action is executed, then the users are shown an explanation for why the action might fail. One group of users were provided the precondition explanations generated through our method, while the rest were presented with saliency map generated by using a variant of state of the art saliency-map based explanation method (Greydanus al.) (2018) and were told that these would be the parts of the state an AI agent would focus on if it was acting in that state. In all the saliency map explanations one of the parts of the state that was highlighted was the switch. The details of the Saliency generation method along with the explanation images shown are provided in the appendix. In total we collected 30 responses, but had to discard six responses because five participants had reported in their submission of not
7

---

Under review as a conference paper at ICLR 2021
seeing an explanation and one response discarded as they refreshed the game in the middle. Out of the remaining 24 responses, 11 corresponded to concept explanations and 13 to saliency based explanations. Participants who got concept based explanation were able to solve the game on average 34.56 steps and 53.56 secs, as opposed to the group who received saliency explanations who took average 52.92 steps and 71.85 secs. This is in accordance with H3, though we can't establish a statistically significant difference based on confidence intervals (reported in A.6).
6 RELATED WORK
There is an increasing number of works investigating the use of high-level concepts to provide meaningful post-hoc explanations to the end-users. The representative works in this direction include works like |Bau et al.] (2017), TCAV (Kim et al.] 2018) and its various offshoots like (Luss et al. 2019) that have focused on one-shot decisions. Most works in explaining sequential decision-making problems have used model specified in shared vocabulary as starting point for explanation or focus on saliency-based explanations (c.f. (Chakraborti et al.) 20200, with very few exceptions. Authors of (Hayes & Shah 2017) have looked at the use of high-level concepts for policy summaries. They use logical formulas to concisely characterize various policy choices, including states where specific action may be selected (or not). Unlike our work, they are not trying to answer why the policy ends up choosing a specific action (or not). (Waa et al., (018) looks addressing the suboptimality of foils while supporting interpretable features, but it requires the domain developer to specifically encode positive and negative outcomes to each action. In addition to not addressing possible vocabulary differences between a system developer and the end-user, it is also unclear when it is possible to attach negative and positive outcomes to individual actions. Another related work is the approach studied in (Madumal et al., 2020). Here, they are also trying to characterize dynamics in terms of high-level concepts, but assume that the full structural relationship between the various variables provided upfront. The explanations discussed this paper can also be seen as special case of Model Reconciliation explanation (c.f (Chakraborti ct al. (017)), where the human model is considered to be empty. The usefulness of preconditions explanations has also been studied by works like (Winikoff) 2017 Broekens al. 2010)). Our effort to associate action cost to concepts could also be contrasted to efforts in (Juozapaitis et al.) 2019) and (Anderson et al. (201)) which leverage interpretable reward components. Their methods rely on having access to reward functions represented using interpretable components.
CONCLUSION
We view the approaches introduced in the paper as the first step towards designing more general symbolic explanatory methods for sequential decision- making problems that operate on inscrutable representations. The current methods facilitate generation of explanations in user-specified terms for sequential decisions by allowing users to query the system about alternative plans. We implemented these method in multiple domains and evaluated the effectiveness of the explanation using user studics. While contrastive explanations are answers to questions of the form "Why P and not Q?", we have mostly focused on refuting the foil (the "not Q?" part). This is because, in the presence of a simulator, it is easier to show why the plan is valid by simulating the plan. We can further augment such traces with the various concepts that are valid at each step of the trace. Also, note that the methods discussed in this paper can still be used if the user's questions are specified in term of temporal abstraction over the agent's ss action space. As long as the system can simulate the foils raised by the user, we can directly use the methods discussed in the paper. While most of the discussions in the paper has been focused on deterministic domains, these ideas also carry over to stochastic domains. The way we are identifying preconditions and estimating cost functions remain the same in stochastic domains. The only difference would be the estimation of the value or the failure point of the foil. One way to easily adapt them to our method would be to compare against the worst case execution cost of the foil or the failure point under one of the execution traces corresponding to the foil. Also while we mostly focused on propositional concepts, our framework is also completely compatible with scenarios where the user may be more comfortable providing relational concepts, since those could be compiled down into propositonal ones. Another avenue of future work could be to see how one could automatically acquire the required concepts, similar for example to the work done by (Ghorbani et al. 2019) in the context of single-shot decisions.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Andrew Anderson, Jonathan Dodge, Amrita Sadarangani, Zoe Juozapaitis, Evan Newman, Jed Irvine, Souti Chattopadhyay, Alan Fern, and Margaret Burnett. Explaining Reinforcement Learn- ing to Mere Mortals: An Empirical Study. In IJCAI, 2019.
David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. Network dissection: Quantifying interpretability of deep visual representations. In Proceedings the IEEE conference computer vision and pattern recognition, pp. 6541-6549, 2017.
J. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, and Siddharth Srivastava (eds.). Pro- ceedings of the Twenty-Ninth International Conference on Automated Planning and Schedul- ing, ICAPS 2018, Berkeley, CA, USA, July 11-15, 2019, 2019. AAAI Press. URL https: php/
Adi Botea, Martin Müller, and Jonathan Schaeffer. Using abstraction for planning in sokoban. In International Conference on Computers and Games, pp. 360-375. Springer, 2002.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. CoRR, abs/1606.015500 2016. URL http::/arxiv..r org/
01540
Joost Broekens, Maaike Harbers, Koen Hindriks, Karel Van Den Bosch, Catholijn Jonker, and John- Jules Meyer. Do you get it? user-evaluated explainable bdi agents. In German Conference on Multiagent System Technologies, pp. 28-39. Springer, 2010.
Jaime G Carbonell and Yolanda Gil. Learning by experimentation: The operator refinement method. In Machine learning, pp. 191-213. Elsevier, 1990.
Tathagata Chakraborti, Sarath Sreedharan, Yu Zhang, and Subbarao Kambhampati, Plan explana- tions model reconciliation: Moving beyond explanation as soliloguy. In IJCAI, pp. 156-163, 2017.
Tathagata Chakraborti, Sarath Sreedharan, and Subbarao Kambhampati. The emerging landscape of explainable planning and decision making. arXiv preprint arXiv:2002.11697 2020.
Yoav Freund, Robert Schapire, and Naoki Abe. short introduction boosting. Journal- Jaarnel-Japansee Society For Artificial Intelligence, 14(771-780):1612 1999.
Hector Geffner and Blai Bonet. A concise introduction models and methods for automated plan- ning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 8(1):1-141, 2013.
Florian Geißer, Thomas Keller, and Robert Mattmüller. Abstractions for planning with state-
dependent action costs. ICAPS, 2016.
Amirata Ghorbani. James Wexler, James Y Zou, and Been Kim. Towards automatic concept- based explanations. In Advances in Neural Information Processing Systems 32, pp- 9277-9286 Curran Associates, Inc., 2019. URL based explanations..oommmommaa.......e .dff
cowards
Samuel Greydanus, Anurag Koul, Jonathan Dodge, and Alan Fern. Visualizing and Understanding Atari Agents. In ICML, 2018.
Bradley Hayes and Julie Shah. Improving robot controller transparency through autonomous pol- icy explanation. 2017 12th ACM/IEEE International Conference on Human-Roban Interaction (HRI), pp. 303-312. IEEE, 2017.
Zoe Juozapaitis, Anurag Koul, Alan Fern, Martin Erwig, and Finale Doshi-Veler. Explainable Reinforcement Learning via Reward Decomposition. IJCAI Workshop on explainable Al (XAI), 2019.
B. Kim, Wattenberg M., J. Gilmer, Cai C., Wexler J., F. Viegas, and R. Sayres. Interpretability Be- yond Feature Attribution: Quantitative Testing with Concept Activation Vectors (TCAV). . ICML, 2018.

---

Under review as a conference paper at ICLR 2021
George Konidaris, Leslie Pack Kaelbling, and Tomas Lozano-Peree From skills to symbols: Learn- ing symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, 61:215-289 2018.
Ronny Luss, Pin-Yu Chen, Amit Dhurandhar, Prasanna Sattigeri, Yunfeng Zhang, Karthikeyan Shanmugam, and Chun-Chen Tu. Generating contrastive explanations with monotonic attribute functions. arXiv preprint arXiv:1905. 2019.
Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable reinforcement learn- ing through a causal lens. In AAAI, 2020.
Tim Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intel-
ligence, 2018.
F. Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Couraaeeau M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Jourmal of Machine Learning Research, 12:2825-2834 2011.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144. ACM, 2016.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint Xrv: 011.:/511..0555 2015.
Max- Max-Philipp B. Schrader.
gym-sokoban.
gym-sokoban, 2018
Roni Stern and Brendan Juba. Efficient, safe, and probably approximately complete learning of action models. arXiv preprint arXiv: feo:::005000.1 08961, 2017.
J Waa, J van Diggelen, Bosch, and M Neerinex. Contrastive Explanations for Reinforcement Learning in Terms of Expected Consequences. In IJCAI Workshop on explainable AI (XAI), 2018.
Wikipedia contributors. Montezuma's revenge (video game) - Wikipedia, the free encyclope- dia, 2019. URL wttp:psseeeee...l...llaa.o.o httgg//wwindeeee/ index. wtw.eeeeppptiiieeeettttt..omoooe 2 7s Les___evene____e (aridde__gameeeeeee 2020].
[Online; accessed 14-Janurry-
Michael Winikoff. Debugging agent programs with why? questions. In Proceedings of the 16th Conference Autonomous Agents and MultiAgent Systems, pp. 251-259, 2017.
10

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
A.1 APPENDIX OVERVIEW
This appendix contains the following information; (1) the representational assumptions used by the method, (2) pseudo-code for the algorithms used, (3) the derivation of the formulas for confidence calculation (4) the derivation the formulas for using noisy classifier and finally (5) the details on the experiment that are not included in the main paper (6) screenshot of the various interfaces.
A.2 REPRESENTATIONAL ASSUMPTIONS
The central representational assumption applicability of actions and cost functions in terms of high-level concepts. Apart from the intuitive appeal of such models (many of these models have their origin models from folk psychology), these representation schemes have been widely used to model real-world sequential decision- cotisiionmmaiing problems from variety of domains and have clear real-world utility (Benton et al., 2019). We agree that there may be problems where it may not be directly applicable, but we believe that this sound initial step and is applicable to many domains where currently Reinforcement Learning (RL) based decision-making systems are being successfully used, including robotics and games.
making is that it is possible approximate the
Apart from this basic assumption, we make one additional representational assumption, namely, that the precondition can be expressed as a conjunction of positive concepts. Note that the assumption doesn't restricts the applicability of the methods discussed here. Our framework can still cover cases where the action may require non-conjunctive preconditions. To see why, consider a case where the precondition of action a is expressed as an arbitrary propositional formula, ((C). In this case, express it in its conjunctive normal form o' (C). Now each clause in (C(C) be treated as a new compound positive concept. Thus we can cover such arbitrary propositional formulas by expanding our concept list with compound concepts (including negations and disjuncts) whose value is determined from the classifiers for the corresponding atomic concepts.
A.3 ALGORITHM
This algorithm for identifying the precondition is specified as Algorithm
The algorithm takes
Algorithm Algorithm for Finding Missing Precondition
procedure PRECONDITION SEARCH
Inpur:
Stil, Odill Sampler, Msim, C,
Output: Missing precondition Cpeee Procedure:
5: poss_prcconddtionnstt
(C(saa)
sample_comu count =
while sample_com count < do
~ Sampler
if T(s, (sm) 1. then
10:
poss poss_prec coss_pee_sstte set =
C(s) then return C, Eposs prec
end condition sample_count return Any concept C, Eposs prec set
as input the failed action (ama), the simulator, the state at which it was supposed to be executed as per the foil (sga), random sampler that returns valid states of the problem (Sampler), the set of all concepts (C) and an upper bound on the number of samples to be explored (2). Any locality assumptions we want to enforce (like sampling around the plan/foil) can be baked into the sampler, and a simple way to generate such samplers could be by leveraging random walk either from the initial state or states from the foil or the proposed plan. The algorithm starts by initializing the set of possible missing preconditions all concepts missing from the failure state (aa).. Then we start sampling other possible problem states, and we use each new state where the action executable to reduce possible precondition list further (since any concept not part of this state can't be
11

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Algorithm for Finding Cost Function
procedure COST-FUNCTIIN-SSEARCHI
Impur:
Ca, Sampler, Mum, C,
Output: Cx
4: Procedure:
for cone Jimit in 1 to |C] do current_foil_cost cone_list=
8:
for in to (the length of the foil) do find min cone set(C(T(s,, (a1.....i-1))), os, cone limit,
C., min current foil cost += min cost conc.list.push((..
10:
11:
min.ccott)
12:
current_fov ceennttfoo__oosstt foil_cost/ > C then return cone_list
return Signal that the concept list is incomplete
possible precondition). If we know that all concepts required to characterize the preconditions are given upfront, then whenever the set of remaining concepts drops to one, we can exit the loop and return the remaining concept. This is because, as per our setting, there must be at least one missing precondition in the fasl- Unfortunately, if there multiple preconditions that are missing in the original failure state or we are not sure whether the given concept set is complete, then we will have to wait until exhaust the sampling budget.
An algorithm for cost function search provided in Algorithm 2 The algorithm takes as its in- put, the foil, the cost of the original plan C,,, the problem simulator, the sampler, the concept set C and the sampling budget f. The procedure hnd_min_com cim__con__eel -ett takes the current concept represen- tation of state i in the foil and searches for the subset C, of the state with the maximum value for Cgs (É,, az), where the value is approximated through sampling (with budget f), and the subset size upperbounded by conc limit. Note that this only satisficing algorithm and not an optimal one; but we found it to be effective enough for the scenarios we tested.
A.4 CONFIDENCE CALCULATION
For confidence calculation, we will be relying on the relationship between the random variables as captured by Figure 2 (A) for precondition identification and Figure 2 (B) for cost calculation. Where the various random variables captures the following facts: O indicates that action a can be executed in state s, C: Pa concept is precondition of a, O the concept is present in state Cahs (fcs), a) 2 k- the abstract cost function is guaranteed to be higher than equal k and finally Octs,a)> stands for the fact that the action execution in the state resulted in cost higher than equal to k.
We will allow for inference over these models by relying on the following simplifying assumptions- (1) the distribution of concepts over the state space independent of each other, (2) the distribution of all preconnconiiio concepts in states where the action is executable is the same as their overall distribution across the problem states (which can be empirically estimated) and (3) cost distribution for an action over states corresponding to a concept that does not affect the cost function is identical the overall distribution of cost for that action (which can again be empirically estimated). The second assumption implies that you are as likely to see a prnpprecoonitioon concept in sampled state where the action is executable as the concept was likely to appear at any sampled state (denoted as P..). While the third one implies that for concept that has bearing the cost function for an action, the likelihood that executing the action in a state where the concept is present will result in a cost greater than & will be the same that of the action execution resulting in cost greater than or equal to for any randomly sampled state (Pc(..)2kk..
For single sample, the posterior probability of explanations for each case be expressed as follows: For precondition estimation, updated posterior probability for a positive observation can be computed as P(e Or A Og) =(1 P(ea & pa ^ O?)), where
12

---

Under review as a conference paper at ICLR 2021
02
gh ((c))aa
0 Cisajak
02
C E Pa
0
(A)
(B)
0
((c a
0 C(saeeR
2 k
0
S
C Pa
CESs
02
(C)
(D)
Figure 3: A simplified probabilistic graphical models for explanation inference, Subtigure (A) and (B) assumes classifiers to be completely correct, while (C) and (D) presents cases where the classifier may be noisy.
P(c, & p.10%, A O.) lo $ Pa A O1) * P(c, $ pa (H
P(Os, O::
Given & $ Pa is independent of 0 and expanding the denominator we get
P(O la & Pa O%) P(c, $ pa) P(O lc, & pa Pa A.) P(e p.)+ P(O p. A O2) * P(a E p.)
From our assumption, we know P(Og lo; & PaA0 is same as the distribution a over the problem states (Pc,) and P(O lc; E Pa A 02) must be one.
Pe, * P(c $ Pa)
Pe, P(a E p.) P(c. P.)
For cost calculation, we have
P(C ((c).a) 2 k/O2, Octe,a22) P(Octua)2k O2, ACC 2)) ((ci), 2 HO0.) P(Ocmme(2x
Where P(Octe.)2x 10 Cabs Caw.eaahheeeee (fc)),a) 2 k) should be 1 and Ca (fc)) a) 2 k independent of O
Which gives
P(Octea)221
P(C.ha ((at)((()))))))))) 2
P(Oc Cahn P(Octt.)2 A onhe (fc)) 2 H)) P(-Cr ((a:) 2 k))
a) 2 k)) ((c +
From our assumptions, we have P(Oc A (())((())))))) 2 k)) pC(.a)2k
((C))s((a))a)
P(Cahe (1c:),( k)) + PC(.a)2k P(-Coèe (o..Ceolcc).ccooo a) 2 k))
13

---

Under review as a conference paper at ICLR 2021
A.5 USING NOISY CONCEPT CLASSIFIERS
Note that in previous sections, we made no distinction between the concept being part of the state and actually observing the concept. Now we will differentiate between the classifier saying that concept is present (O is state from the fact that the concept is part of the state (c; C(S)) )) The relationship between the random variables can be found in 3 and (D). We will assume that the probability of the classifier returning the concept being present given by the probabilistic con- fidence provided by the classifier. Of course, this still assumes the classifier's model of its prediction accurate. However, since it the only measure we have access to, we will treat as being correct. Now we can use this updated model for calculating the confidence. For the precondition estimation, we can update the posterior of a concept being a precondition given negative observation (O=c.) using the formula
P(c: & Pal0"r, AO)) P(O la Pa A O.) * P(c. & ppa(Ot)
P(O%,, O8)
Where P(q: & pal02) P(q & Pa) and
expand P(O2c $ Po A Og) as follows
P(O l/ $ Pa A O.) =
P(0-a, E C(s)) P(C, e c(s)ee: & A O2) P(O-a & C(s)) P(e. & C(s)la P. A O²))
Where defined earlier P(c: & C(s)le & Pa A 0 and P(q e C(s]C; & Pa A 0.) would correspond to (1 Pc,) and Pe,- The denominator also needs to be marginalized over C(s).
Similarly for posterior caleulation for positive observations, we have
P(O A AC)
le C(s)) P(a C(s)le, $ pa A P(O,le & C())) P(c, & C(s)la $ pa A.O)
Now for the cost, we can similarly incorporate the observation model as follows.
P(Oc)s.)2k Og CC (fc+), 2 k)) P(C (fc).. k)
2 KIO%, Oc(ma))=+)==
P(Oc(s.a)26; Of,)
(P(Oc(ma)2 O2 E C(s), (fcs)a ((c3),)) 2 k) P(Ocinajss: O2, la & C(s), C2 ((c:),)) k) P(a & C(s))) + P (H4),)))
P(c: E C(s))+
P(Ocio.)244.2 02,)
Given their parents, Oc(s,))2k and O are conditionally independent, and given its parent O is independent of (cch(((c)).))) a) 2 k)), there by giving
(P(Octs.a)zale E (((s),cah ((c;), ).))).)))))) a) 2 k) P(Oa ces E C(s)) P(a: E C(s))+
P(Oc(naj2ala C(s), Cabs (fc)), a) 2 k) P(O la & C(s)) * P(a & C(s))) P(C. ((cs), 2 k)
P(Oc:o.a)2k: O%,)
Now P(Oc(s.))all E C(s),Cg ((c) 2 k) and P(Octs.))alle & C(s), ((a)) k) either be empirically estimated from true labels we make the assumption that equal to Po(..))kk (which we made use of in our experiments), which would take us to
(P(02,1a E (())) E C(s))+
PCC.u)24 * P(0 & C(s)) P(a & C(s))) P(C. (fo.), a. 2 k)
P(Octs.a22 02,)
14

---

Under review as a conference paper at ICLR 2021
A (Lay Rif Nov 3gg
Pbe Acdon
My-Opp
Figure 4: Montezuma Foils: Left Image shows foils for level 1, (A) Move right instead of Jump Right (B) Go left over edge instead using ladder (C) left instead of jumping over skull. Right Image shows foil for level 4, (D) Move Down instead of waiting.
Move bction
Move action Push oction
Puch ocrion
Figure 5: Sokohan Foils: Left Image shows foils for Sokohan-switch, note that the green cell will turn pink once agent passes it. Right Image shows foil Sokohan-cell.
A.6 EXPERIMENT DETAILS
For validating the soundness of the methods discussed before, we tested the approach on the open- Al gym implementation of Montezuma's Revenge Brockman et al. (2016) and variants of Sokoban Schrader (2018). Most of the search experiments were run on an Ubuntu 14.0.4 machine with 64 GB RAM.
For Montezuma, we used the deterministic version of the game with the RAM-based state repre- sentation (the game state is represented by the RAM value of the game controller, represented by 256-byte array). We considered executing an action in the simulator that leads to the agent's is death (falling down ledge, running into enemy) or non-NOOP (NOOP action is specific agent action that is designed to leave agent's state unchanged) action that doesn't 't alter the agent position (trying move left on ladder) as action failures. We selected four possible foils for the game (illustrated in Figure 4, three from level 1 and one from level 4. The base plan in level I involves the agent reaching the key, while level required the agent to cross the level.
For Sokoban, considered two variants with a single box and a single target. Both variants allow for 8 actions and a NOOP action. Four those actions are related to the agent's movements in the four directions and four to pushing in specific directions. We restricted the move actions only to able to move the agent if the cell is empty, i.e., won't move if there is box or a wall in that direction. The push action also moves the agent in the direction of push if there is box in that direction, and the agent will occupy the cell previously occupied by the box (provided there no walls prevent the box from moving). Similar Montezuma, consider any action that
15

---

Under review as a conference paper at ICLR 2021
doesn't change the agent position to be a failure. The first version of Sokoban included switch the player could turn on to push the box (we will refer to this version as Sokoban-sve -okoban-switch), and the second version (Sokoban-cells) included particular cells from which it is costlier to push the box. We considered two versions of Sokohan-switch, one in which turning on the switch only affected the cost of pushing the box and another one in which it was a precondition. For the cost case of Sokoban-switch, while the switch is on (i.e. the cell is pink), all actions have unit cost, while when the switch is off, the cost of pushing actions is 10. The cell can be switched on by visiting it, and any future visit will cause it to turn off. For the precondition-version, pushing of the box while the switch is off causes the episode to end with high cost (100). Since we also trained an RL agent for this version for generating the saliency map. We also added a small penalty for not pushing the switch and a penalty proportional to the distance between the box and the target. In Sokoban-cellk the cost of all actions except pushing boxes in the pink region is one, while that of pushing boxes in the pink region is 10. We selected one foil per variation, and the original plan and the foil are shown in Figure
Concept Learning For Montezuma, we came up with ten base concepts for each level that ap- proximates the problem dynamics at the level, including the foil failure. We additionally created ten more concepts by considering the negations of them. All state samples (used to generate the samples for the classifier and the algorithm) were created by randomly selecting one of the states from the original plan and then performing random walks from the selected state. For the classifiers, we used game-specific logic and RAM byte values to identify each positive instance and then ran- domly selected a set of negative examples. We used around 600 positive examples (except for the concepts .oirigh and _kullonn in level I, which had 563 and 546 examples, respec- tively) and twice as many negative examples for each concept. These RAM state examples were fed to a binary AdaBoost Classifier Freund et al.] (1999) (Scikit-learn implementation [Pedregosa] et al. (2011) version 0.22.1, with default parameters), with 70% of samples used as train set and the rest as the test set, for each concept. Finally, we obtained a test accuracy range of 98.57% to 100%, with an average of 99.72% overall concepts of both the levels. All the samples used for the classifier were collected from 5000 sampling episodes for level I and 4000 sampling episodes for level 4. During the search, We used a threshold of 0.55 classifiers for concepts of level I, such that a given state has a given concept when the classifier probability is greater than 0.55, to reduce false positives. The code for sampling and training the classifiers can be found in the directory PRECOND.BLACKBOOT BwA.BBOOO////alleee.......
coneeedccccparaaae inside the code directory.
For the Sokoban variants, we wanted collect at least the list of concepts from people. We used sur- veys to collect the set of concepts. The survey allowed participants to interact with the game through a web interface, and at the end, they were asked to specify game concepts that they thought were relevant for particular actions. Each user was asked to specify a set of concepts that they thought were relevant for four actions in the game. They were introduced to the idea of concepts and their effect on the action by using PACMAN as an example and presenting three example concepts. The exact instructions and screenshots of the interface used for Sokoban-cell can be found in the file Sokoban Lealaneee___aaeeee eell_survey.pdf in the directory Study_ Beclly_ebbbieeeeeee -dffs, which is part of the supplementary file zip. For Sokoban-switch, we collected data from six participants, four of whom were asked to specify concepts for push actions and two people for move actions. For Sokoban-cell, we collected data from seven participants, six of whom were asked to specify concepts for push actions, and one was asked specify concepts for move action. We went through the submitted concepts and clustered them into unique concepts using their description. We skipped ones where they just listed strategies rather than concepts describing the state. We removed two concepts from the Sokoban-cell list and two from Sokoban-switch because we couldn't make sense of the concept being described there. For Sokoban-switch, we received 25 unique concepts, and for Sokoban-cell, we collected 38 unique concepts. We wrote scripts for each of the concepts and used it to sample example states. We ran the sampler for 1000 episodes to collect the examples for the concepts. We trained classi- fiers for each of the concepts that generated more than 10 positive examples for the concepts. For sokoban-switch, we removed two additional concepts because their training set didn't 't contain any positive examples. We had, on average, 178.46 positive examples for Sokoban-cell per concept and 215.55 for Sokoban-switth 70% of samples for training and the remaining for testing. We used Convolutional Neural Networks (CNNs) based classifiers for the Sokoban variants. The CNN architecture involved four convolu- tional layers, followed by three fully connected layers that give binary classification output. The
We used all the other samples as negative examples. We again used
16

---

Under review as a conference paper at ICLR 2021
average accuracy of the Sokoban-swine was 99.46%, and Sokoban-cell was 99.34%. The code used for sampling and training for each domain can be found under the folder COST.TRAINEL (inside the directory BLACKBOX CODE). The classifier network is specified in the file CNNnetwork.py. The details on how to run them are provided in the README file in the root code directory.
Explanation Identification: For Montezuma, the concept distribution was generated using 4000 episodes, and the probability distribution of concepts ranged from 0.0005 to 0.206. For some of the less accurate models, we did observe false negatives resulting in the elimination of the accurate preconditions and empty possible precondition set. So we made use of the probabilistic version of the search with observation probabilities calculated from the test set. We applied a concept cutoff' probability of 0.01, and in all cases, the precondition set reduced to one element (which was the expected precondition) in under the 500 step sampling budget (with the mean probability of 0.5044 for foils A, B & C. Foil D, in level 4, gave a confidence value of 0.8604). The ones in level 1 had lower probabilities since they were based on more common concepts, and thus, their presence in the executable states was not strong evidence for them being a precondition.
For each Sokoban variant, we ran another 1000 episode sampler, which used random restarts from the foil states to collect samples that we used for the explanation generation. During the generation of the samples, we used the previously learned classifiers to precompute the mapping from concepts to states.
We used a variant of Algorithm 2 where we sped up the search by allowing for memoization. Specifically, when sampling is done for an action and specific conc_limit for the first time, then we precompute the min-cost for all possible concept subset of that size. Then for every step that uses that action, we look up the min value for the subset that appears in the state. The search was run with a sampling budget of 750. For calculating the confidence, all required distributions were calculated only on the states where the action was executable. Again the search was able to find the expected explanation. We had average confidence of 0.9996 for the Sokoban-switch and 0.998 for the Sokoban-cell The exact observation models values used can be found in constant.py under the directory COST WET.BBLACBBO/Stt and the file cost cost.explainer.py in the same directory contains the code for the exact search we used.
User study: With the basic explanation generation method in place, we were interested in evalu- ating if users would find such an explanation helpful. Specifically, the hypotheses we tested were Hypothesis 1: Missing precondition information is useful explanation for action failures.
Hypothesis 2: Abstract cost functions are useful explanation for foil suboptimality.
Hypothesis 3:
(at least precondition ones) help users understand the task better than Saliency map based ones.
Concept
To evaluate this, we performed user study with all the foils used along with the generated explana- tion and simple baseline. In the study, each participant was presented with a random subset of the concept we used for the study (around five) and then was shown the plan and possible foil. Then the participant was shown two possible explanations for the foil (the generated one and the baseline) and asked to choose between them. There were additional questions at the end asking them spec- ifyy what they believed was the completeness of the selected explanation, on a Likert scale from I to 5 (I being least complete and being the most). They were also provided a free text field provide any additional information they felt would be useful.
For H1, the options showed to the user includes one that showed the state at which the foil failed along with the information that the action cannot be executed in that state and the other one re- ported that the action failed because a specific concept was missing (the order of the options was randomized). In total, we collected data from 20 participants, where 7 were women, the average age was 25, and 10 people had taken an AI class. We found that 19 out of the 20 participants selected precondition based explanation as choice. On the question of whether the explanation was com- plete, we had an average score of 3.476 out of 5 on the Likert scale (1 being not at all complete and 5 being fully complete). The results seem to suggest that information about missing precondition are useful explanations though these may not be complete. While not a lot of participants provided information on what other information would have been useful, the few examples we had generally
17

---

Under review as a conference paper at ICLR 2021
original State
State with Highlights
Figure 6: Saliency map based explanation shown users part of H3
pointed to providing more information about the model (for example, information like what actions would have been possible in the failed state).
For H2, the baseline involved pointed out the exact cost of executing each action in the foil, and concept-explanation showed how certain concepts affected the action costs. In the second case, all action costs were expressed using the abstract cost function semantics in that they were expressed as the 'action costing at least X' even though in our case, the cost was the same as the abstract cost. For H2, again, we collected 20 replies in total (ten per foil) and found 14 out of 20 participants selected the concept-based explanation over the simple one. The concept explanations had, on average, a completeness score of 3.214 out of 5, The average age of the participants was 24.15, 10 had AI knowledge out of 20 people, 11 were masters students (rest were undergrad), and we had 14 males, 5 females, and one participant did not specify.
For H3, as mentioned the baseline was a saliency map based explanation. For generating the saliency map, trained the RL agent using DQN with prioritized experience replay (Schaul et al. 2015 P The agent was trained for 420k epochs. The Saliency map itself was generated for four states, with the agent placed the four sides of the box. The saliency map itself was generated using Greydanus et al. (2018), where we used only the procedure for generating the map for the critic network Figure shows the saliency map generated for one of the images. This was shown when the user tried push up action and fails. At the beginning of the study, both groups of the users were made to familiarize themselves with five concepts that were randomly ordered (the concepts themselves remained the same) and had to take a quiz matching new states to those concepts, before moving on to play the game. Out of the 24 responses we considered, six identified as female and 16 identified as men. Nine of the participants reported they had some previous knowledge of AI, but only one participant reported having any planning knowledge. For H1, the Participants who got concept bused explanation were able to solve the game averuge 34.56 steps and 53.56 secs (with a 95% confidence interval of #12.56 and +23.21 respectively), as opposed to the group who received saliency explanations took on average 52.92 (=16.01) steps and 71.85 (+28.65) secs. Note that given the overlap between the confidence intervals we can't II establish a statistically significant difference between the conditions using the intervals.
PDF files showing the screenshots of the user study website for a scenario for the precondition ex- planation test and one from cost explanation can be found in dber-study-preconditie pdf and User- study-cost.po pd in the directory Study_ Srebsite_Pdfss The actual data collected from the user studies and the concept survey can be found in the directory USER_STUDY FFEDDBCC. But below, we have included some screenshots of the interface
RI, Adventure/ http///bbbasss//eee/eeeeeebbasaa /4, hew.://eehh/tttre/g/g/t..o/.//oe We made use of the code available http://bw..cteeeggggg..oo/o///ge wuwle//aaaaazizaaararaa
2 For exact agent, we followed the approach described in ipynb
18

---

Under review as a conference paper at ICLR 2021
Action
Concept with Max difference empty above empty_belle below empty _below
Max Absolute
Average Difference in Estimates
Difference in Estimates
push up push down push left push right move up
0.018
0.004
0.0154
0.0033
0.0163
0.0037
empty_beloy bbelow
0.0172
0,0046
empty_left
0.002
0.0009
move down move left
wall
0.0017
0.0007
empty right empty_rip right
0.0032
0.0009
move right
0.0045
0.0008
Figure 7: Results from lokoban-switee on the distribution of non- con-precondition concepts for each
action. For each action the table reports the concept with the maximum difference between the distri- bution of concept for that specific version, versus the overall distribution and the average difference in estimates across concepts.
A.7 ANALYSIS OF ASSUMPTIONS MADE FOR CONFIDENCE CALCULATIONS
In this section we present results from additional tests we ran verify some of the assumptions made in the confidence calculations on the Sokoban variants. We mainly focused on Sokoban vari- ants since the concepts were collected directly from users and we tested the assumptions (1) the distribution of all preconcccnniioon concepts in states where the action is executable is the same as their overall distribution across the problem states (which can empirically estimated) and (2) cost distribution of an action over states corresponding to concept that does not affect the cost function identical to the overall distribution of cost for the action (which can again empirically esti- mated). We didn't 't run separate test the independence of concepts concepts listed by the users were in fact correlated and were denoting similar or even the same phe- nomena. All concepts were assumed be distributed according to Bernoulli distribution, whose MLE estimates were calculated by running the sampler for ten thousand episode, where we used states from the original successful/optimal plan as the initial state for the random walk (ensuring the distributions are generated from state space local to the plan of interest). For first assumption, we compared the distribution of concept for states where the action was executed against the distribution of the concept over all the sampled states. For the second assumption, we compared the distribution of the states with the high cost (>=10) where the concept present versus the distribution of high cost for the action.
saw that many of the
Table 7 summarizes the results from testing the first assumption for Sokoban-switeh For each ac- tion the table reports the non-precondition concept which had the maximum difference in estimates (the reported difference in the table). In this domain, the only precondition concept is switch_on for the push actions. As differences to further reduce once we start accounting the correlation between concepts.
see for the domain, the differences are pretty small and expect the
Table 8 presents the results for the second assumption. In the cases of Sokoban-switch, skipped the switch on concept and for Sokoban- Cell we skipped the concepts related to the pink cells since they are all highly correlated to central concept controlling the cost function (on -ink cell).
again
19

---

Under review as a conference paper at ICLR 2021
Domain
Action
Concept with
Max Absolute Difference in Estimates
Average Difference in Estimates
Max difference
push up
wall hwtpeeeellwoo_ooeeeeeeee
0.1132
0.0461
push down push left
0.1107
0,0473
Sokoban-Switch
_bboeeswitch
0.1135
0.0461
push right
wwll -of.ooowoofbboxoooooo
0.111
0.0479
push up
box_on_right
0.0956
0.0411
push down
box_on_right
0.1098
0.0476
Sokoban-Col Cell
push left
box on right
0.1012
0,0486
push right
wall left
0.0889
0.0433
Figure 8: Results from Sokoban-switch and Sokoban-Cell the distribution of action cost across different concepts. Here we report only the cost for push actions, since only those actions result in higher cost.
20

---

Under review as a conference paper at ICLR 2021
A.8 STUDY INTERFACE SCREENSHOTS
Gane inlornazion
Doncepts addted action
legal
Pritk ridal
Keys exécure accion::
ACOA
6 Pein rpht 15
Figure 9: Screenshot from the survey done collect sokoban concepts.
Plan and the alternate plan
onywhere
Allerntte plac eugpested by the usen Folow the you
as image movelat Onateed
jumpleett than
(A)
Explanation for why the alternate plan would fall
shown image then move left (mateed of jump left and then fallow the naxt of the plan.
Please select the explanation that you find the most useful
nevelt
Hence movelett
io te atamat park not perlers be
shonn
(B)
Figure 10: Screenshot from the study interface for H1.
21

---

Under review as a conference paper at ICLR 2021
Proposed plan and the alternate plan
Click anywheree the video below to view the proposed
plan:
Plan goal:
target
PL
Tosal cost
Alternate plan suggested the user: Instead of pushing the around pink calls, directy push box through them and proceed the target.
Eaplain why the atteruat plan IIGN corry?
(A)
Explanation for why the alternate plan more costly
Albematt Plan Steps-
eugpected
puching pink
sterd
and then proceed to the target
you
Ohu vow
Sep jusn of actonn cook
Ste--
Dep-h
(aep Vive csan
LG
daep sua adion uana
altorate
adii
hepporing
Eancutng acien whan
The cosa at load
heppoiig
IG
Youv oalon happens
frow actis cosa best This happens
(B)
Figure 11: Screenshot from the study interface for H2.
22

---

Under review as a conference paper at ICLR 2021
Information
garme
Ressat Gurre
Time Remaining:
Possible Explanations:
2m 44s
possibie
You can only push the box up if the butterity box activated thes rat brw the current saie.
Keys execute actions:
Move
Move rght
Push up x
Push down
Push bei
Push
(A)
Game Information
Astion
NOT REFRESH THE RAGE
Perder Game
Time Remaining:
Possible Explanations:
2m 48s
the
Oegtlighted
sould
original
State
Highlights
Keys execute actions:
Move []] dwn
ops [g]
8
(B)
Figure 12: Screenshot from the study interface for H2.
23


Reviews:
[{"review_id": "ruj1hhH81Zh", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the problem of answering queries about \"foils,\"\ni.e., why an alternative plan was not chosen by an agent acting\noptimally in a deterministic MDP. The authors describe three broad\nclasses of responses to this query: (1) one of the actions in the foil\ndoes not satisfy the preconditions, (2) the foil does not achieve the\ngoal, or (3) the foil has suboptimal cost. Importantly, all responses\nare conducted with respect to a pre-specified set of concepts\n(predicates; or binary classifiers): the symbolic preconditions and\ncosts are learned by interaction with the simulator but expressed in\nthe language of these concepts. The authors discuss extensions to\ntheir basic framework that (1) provide confidence measures along with\nthe responses and (2) handle noisy/probabilistic concepts.\n\nA strength of this paper, in my opinion, is that it addresses a very\nimportant problem and seems to make a lot of positive strides toward a\nsolution. I found the motivating paragraphs in the introduction to be\nhighly compelling, and the related work section to be sufficient for\nplacing this paper with respect to related literature on\nexplainability (which I am not very familiar with). Another plus point\nis that the authors show that their system is robust to uncertainty\n(via the confidence measures) and noise (via the probabilistic\nconcepts).\n\nHowever, my main issue with this paper surrounds the assumption of the\npre-specified concepts. The most compelling motivational sentence to\nme was, \"More often than not...lay user\"; however, if we are assuming\nthat lay users are the target users of the proposed system, where\nwould these concepts come from? I understand that they could be\nspecified ahead of time, but then there would be issues if the user\nhas a concept in mind while specifying a foil that is not covered by\nthe pre-specified set. The authors do partially address this concern\nin the sentences \"An empty list...task-related concepts.\", but I did\nnot find this sentence compelling on its own, and it seemed to me that\nthe empirical studies do not consider this possibility of needing to\nadd more concepts to be able to answer a query (please do correct me\nif I have missed this). To me, one of the most interesting aspects of\nthis problem is to consider how to automatically learn or improve the\ninitial set of concepts, perhaps given data of many users' foils\nacross different problem instances in a particular domain. For\ninstance, if we notice that users often provide a foil that involves\nwalking into the skull (we can figure this out with our simulator), we\nmay be able to learn that a concept NextToSkull is important when\nbuilding our symbolic preconditions. Unfortunately, the current paper\ndoes not focus enough on this important aspect of the problem, instead\nsimply assuming a good set of concepts to be pre-specified, which I\nfind to be highly unrealistic.\n\nA second major issue is the relatively low quality of the empirical\nresults. I appreciate that in this line of work, it can be hard to\nprovide rigorous numbers, since much of the evaluations come from\nhumans. Nevertheless, I believe that one can obtain much more\nilluminating results in this problem setting by improving the\nexperimental design and reporting. A simple starting point would be to\ninclude confidence measures on the reported numbers, in the paragraphs\ndiscussing the results of H1/H2 and H3. Beyond that, it would be good\nto probe deeper, e.g. for H3, cluster (and show us visualizations of)\nthe different situations where the precondition-based explanations\nwere useful while the saliency-based explanations were not, and vice\nversa, so that we can better understand when each one tends to be\nbetter. Personally, I could imagine many situations (e.g., in\nunderstanding the behavior of an autonomous vehicle) where I would\nrather just have the saliency map that highlights a region of my\nsurroundings, instead of being given a written explanation as to why\nthe vehicle performed a certain maneuver. So, I think the paper could\nbe greatly improved if the authors probe more deeply into explaining\nthe empirical results. By the way, much of the work by Anca Dragan (I\nam unaffiliated), see e.g. [1], can be a useful reference in how to set up highly\nrigorous user studies.\n\nLooking forward, I have one question for the authors. It is clear that\nin real-world applications of AI, our agents will never be able to act\noptimally, and we shouldn't expect them to. Given this, would there be\na way to modify the current work to create feedback from the user that\nallows the agent to improve its solution? For instance, perhaps the\nagent is in the middle of executing the best solution it found after\nthinking for 30 minutes, but then the user says \"why not do X\ninstead?\", and the agent has to decide between: (a) *the user* missed\nsomething, and I should generate an explanation; or (b) *I* missed\nsomething, and I should think more and revise my current policy.\n\n[1] Bobu, Andreea, et al. \"Learning under Misspecified Objective Spaces.\" Conference on Robot Learning. 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "M6KiWGkx8xc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary\nThis paper introduces a new method for contrastive explanation of symbolic models on sequential decision-making problems, i.e. explaining why a foil plan is not as good as the system proposed plan. The suboptimality of foil plans is categorized into two types: invalid actions and larger cost.\n\nTo make the explanation more understandable to human, the author introduces \"concepts\" to explanation, which are assumed propositional properties of states. Concept classifiers can be trained on samples to predict the presence of each concept in a state. To explain an invalid action, the method reports a missing precondition concept of the failing action; to explain a larger cost, it reports a set of representative concepts such that the foil actions under these concepts are guaranteed to give a larger cost than the proposed plan. The paper also provides detailed algorithms to find preconditions or representative concepts (using \"abstract cost functions\") for actions. The authors also introduce simple PGMs to evaluate the confidence of each explanation.\n\nThe authors conducted user studies on the proposed explanation method and demonstrated its usefulness.\n\n#### Strength\n- Model explanation is indeed a very important field today for any ML models. Sequential decision-making models are popular and widely used, but explanation methods for them are still somewhat underexplored. As reported in the paper, previous work either includes \"concepts\" directly in model learning (not post-hoc) or use saliency maps (not human concepts); this work introduces human concepts to post-hoc explanation.\n- The whole explanation method is novel and makes sense to me. The ideas are intuitive, but the algorithms for finding the explanations and evaluating the confidence are non-trivial.\n\n#### Weakness\n- In my opinion, the user study still has room for improvement.\n\t- For H1 and H2, directly asking the user \"which one is more useful\" does not look like a good way of comparison. At least to me, it's hard to tell which one is more useful if I have already read both and understood. Maybe it's better to only show one explanation to a participant, and ask how well they understood, or let them perform a task as in H3.\n\t- For H1, as I see in Figure 8B, the explanation with concepts (CE) has exactly more information than the baseline explanation (BE). In other words, CE is concept + image while BE is only image; BE is a strict subset of CE. Such a comparison does not seem very useful. Would it be better if you, for example, compare concept-only with image-only, such as removing \"in the state shown in the image\" in CE?\n\t- For H3, the task setting is interesting, but in the shown example, the concept that the user has to learn is merely to use the switch, which looks somewhat too simple and not very interesting. It would be more attractive if the concept is more complex (e.g. you can't fall off a plane or touch an enemy as in Montezuma).\n\t- I think the participants' background information (age, gender, how recruited, etc.) is important for a user study and I suggest having it in the main paper or at least making it easier to notice.\n- It seems that empirical studies are not provided for confidence score calculation, i.e. how well do the scores correspond with actual explanation accuracy.\n\n#### Questions\n- In Section 4 line 16, you mentioned \"In cases where we are guaranteed that the concept list is exhaustive...\" Could you provide some examples of these cases?\n\n- In Section 5 \"Explanation identification\", you mentioned \"The search was able to identify the expected explanation for each foil.\" Does that mean all the output explanations are accurate? If so, it will be interesting to see how the search performs on more complex tasks.\n- For explanations on larger cost, as in Figure 9B, to me the most ideal explanation would be just *Executing action \"push up\" when \"Box on pink cell\" costs at least 10*; other lines are not useful. In other words, it might be better to focus on steps where the foil has larger cost than proposed plan. Do you have any thoughts on this line?\n\n#### Typos\n- Section 2: symbol $G$ (set of goal states) font inconsistent\n- Appendix A.3 Algorithm 2 line 12: symbol broken\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8gbL-gVatQ8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe authors propose a method of explainable AI for inscrutable blackbox models. The explanations build on a set of user-defined primitives, independently trained on the blackbox representation (e.g., visual frames of an Atari game), and use an increasingly popular method of providing contrastive explanations. Two forms of foil-based responses are provided: (1) indication of action failure from the planning perspective (preconditions unsatisfied); and (2) an explanation of relative sub-optimality that highlights key aspects of action costs that the user may be unaware of.\n\nHigh-level concepts, particularly those tied to a symbolic description of the world dynamics, is an extremely compelling basis for explanation. It helps build a well-grounded intuition with human users/observers of autonomous systems and arguably is the best way to convey explanations that describe behaviour of an inherently sequential nature.\n\nIn addition to the form of explanation primitives, the algorithms are intuitive, and the probabilistic inference seems to be sound.\n\nMy concerns with the paper fall into two main categories: the lack of substantial contributions (particularly as related to representation learning) and the strong assumptions placed on the setting.\n\nOne of the most significant missed opportunities in this work is to focus on introducing new concepts. Especially given that human studies were conducted, and the setting was identified when algorithms fail, and new or revised concepts are required. Assuming highly accurate binary classifiers for each concept is relatively extreme, and it's only one such overly strong assumption.\n\nOther very strong assumptions include:\n\n(a) The state is memoryless/Markovian: every concept can be determined by looking exclusively at the current frame. This isn't the case in many settings where some memory of the previous actions is required.\n\n(b) The distribution of a fluent across the state space is independent to the distribution of other fluents: this is rarely the case in planning-like domains, and the types of explanations introduced in this work build on planning-like domains a great deal.\n\n(c) There is only one failed precondition: this might be an alright assumption to make given (b), but similarly, I find it unlikely that many domains would have this property.\n\nAs pointed out by the authors, assumptions (b) and (c) cause Algorithm 2 to exhaust the entire sampling budget before failing, and I don't believe they are safe assumptions to make.\n\nOn the topic of evaluation, there are two further issues. One is the scope of the evaluation (only two domains and a seemingly small number of subjects to test with), and this reduces the significance of the paper's contribution. Another issue is the choice of comparison for H3. The Saliency map is built using different information than that surfaced using the proposed approaches. This makes it challenging to adopt the experiment's conclusion as written since it is also testing the quality of the saliency map in addition to the comparative nature of the explanations.\n\nI am leaning towards rejecting the paper due to the number of assumptions placed on the approach. Combined with the limited evaluation setting and scope of work, the contributions to the field of learning representations seem limited.\n\nUltimately, my hesitation in recommending acceptance comes from the contribution being on the low-side for the ICLR community. The authors identify key elements that would change this impression -- e.g., refining the concepts when the algorithms fail to find an explanation (italics on pg 5) -- but these do not play a central role in the proposed work.\n\nThe H1/H2 results are, in some sense, evident that the proposed explanations are preferred (19/20 for H1). While an important element (it would be very surprising if this weren't the case), they don't serve as a sufficient contribution in their own right. The H3 comparison seems to be somewhat contrived since they come from different sources -- a more accurate comparison would be to engineer the saliency overlay based on the domain-knowledge known. I.e., reflecting the precondition-based information directly. Without that, you conflate both the choice of focus and ability to highlight that choice.\n\n\nQuestions for the authors:\n\n1. How do you remove the (seemingly strong) assumption that the distribution of fluents across the state space is independent among the fluents? Alternatively, why can we expect this to be a reasonable assumption to make?\n\n2. How would you remove the dependence on the fully observable / Markovian assumption on the blackbox output that is used for concept classification? I.e., when the full state cannot be discerned by looking at the screen alone.\n\n\nOther minor points of improvement for the paper:\n\no Mind the notation used for your Goal set (near the end of page 2, you are using a different syntax than the one introduced.\n\no Defn 3 seems to have a random bracket at the end.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5k9SECQGya", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Edit: \n\nI have read the other reviews as well as all author responses. The other reviewers noted meaningful concerns, but I believe the authors have clearly addressed most of these points. I still believe this work is an \"accept\".\n\n\nSummary: \n\nThe authors present a system for producing explanations in terms of user-specified prerequisite relationships. The authors train a classifier to detect the presence of user-specified concepts. Relationships between these concepts are found by learning a partial symbolic model. With this model, an agent's action can be compared to a user-provided alternative and the first prerequisite-violating action can be identified (or the cost difference can be conveyed). The authors evaluate their approach on two domains with a user study. \n\nPros:\n\n-This work addresses a relevant problem in explaining RL (and other SDM) agents and provides an initial solution that provides a solution for a meaningful set of domains. \n\n-I agree with the authors: to my knowledge, this is the first work to provide explanations in terms of a learned symbolic model separate from the one used by the agent.\n\n-The method for identifying failed preconditions is clearly introduced and motivated. The extension to handle noisy classifiers substantially increases the usefulness of this work. \n\nCons:\n\n-This work requires a deterministic domain, as well as access to a simulator from which states can be sampled. This substantially limits the applicability of this approach. (This limitation is not mentioned in the abstract.)\n\n-The authors make a number of assumptions (Section 4, \"Confidence over explanations\"), but these are not quantitatively evaluated. Adding experiments that measure how well these assumptions hold in practice would improve this work.\n\n-The user study could be improved in a number of ways. It used manual translation of explanations to text. A comparison was made to saliency maps, but not to other explanations (such as causal explanations). \n\nQuestions During Rebuttal Period:\n\n-Please address and clarify the \"Cons\" above. \n\n-How important was the change to Montezuma's Revenge (rendering failed actions)? Is this a general requirement for creating explanations in an environment?\n\n-Do you have additional information about the participants? Were they AI practitioners? Were any of the \"main study\" participants among those who selected the 25/38 concepts? \n\nOther Comments:\n\n-The authors may be interested in \"Distal Explanations for Explainable Reinforcement Learning Agents\" (a follow-up to the Madumal et al, 2020 work cited in Section 6). \n\n-Section 5 appears to be broken into fewer subsections / has fewer line breaks in order to meet page requirements. This leads to a cramped, less organized Section 5. \nSome Typos/etc:\n\n-In general, another editing pass for articles and agreement of subject/verb plurality would help this paper. \n\n-Line 2 of Introduction: \"they ... with its\" (change to \"with their\"). \n\n-Paragraph 3 of Introduction: The \"'\" after \"questions of this form\" is not matched. \n\n-Background: \"We will consider goal-directed agents that any given point is trying to drive\" (fix verb agreement and remove extra words). \n\n-The sentence leading into Definition 4 does not smoothly lead to Definition 4. \n\n-Section 4: \"So we start with\" (remove \"so\").\n\n-Section 4: \"we aren't be able\" (remove \"be\"). \n\n-Section 5: AdaBoost citation is using wrong command. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "3impv1XAJyw", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a novel approach to generate contrastive explanations in a dialogue setting between a human and a planning agent. The setting assumes that the agent generates and offers an optimal plan to the user, and the user in turn challenges the presented plan offering an alternative (i.e. a contrast/foil). The goal of the agent is the denounce the alternative plan by explaining the infeasibility or suboptimality of the plan to the user in concepts they understand.\n\nThe explored direction is interesting and relevant as it seems to be a natural addition to the related problem of *generating* contrastive (a.k.a. counterfactual) explanations. I would suggest, however, that the paper more clearly distinguishes between the contrastive explanation generation literature (see, e.g., a survey [1]) with the type of explanation which is offered here, which is to identify the minimal set of preconditions (in an alternative concept space) that describes/explains the difference between two given instances (i.e., a model-proposed fact and a human-generated foil). This motivation is related to such (missing) related work as [2].\n\n\nStrengths:\n- the writing throughout well-polished and the motivation in the abstract and introduction is very well done\n- the formulations are sensible and seem to be encapsulating the settings described and generalizations\n- the inclusion of a user-study is helpful\n\n\nSuggestions:\n- the overloading of notation is at times difficult to follow\n- as a reader not familiar with Montezuma's foils or Sokoban, I had a difficult time understanding the experimental section. \n- a comparison with optimal explanations is lacking (relatedly, statements such as \"the searchable to identify *the* expected explanation\" is misleading, as, without an infinite budget and exhaustive search, the algorithm can identify an approximate to the optimal explanation)\n- re: user study, I am not entirely convinced that the baselines are fair. by default, I would expect that offering more (non-fooling) information would render a higher subjective explainability score. perhaps the experiments would be stronger if tested against other types of information that is provided in addition to the presented baseline (something along the lines of H3; although even here it is not a completely fair comparison because unlike saliency maps, the offered explanations depend on human-annotated concepts which would naturally render the presented explanations are more human-understandable)\n- nit; a completeness score of 3.36 / 5 is not possible (this would mean one of the 20 participants voted a non-integer value)\n- in the related work, there seems to be an absence of literature on planning; perhaps a differentiation of the scope of the presented paper with this literature would boost the motivation\n\n\nSummary:\nI think this paper explores a fresh direction, which is necessary for enabling humans to contest, challenge, and ultimately trust the decisions of an automated system. I also believe that the presented material still requires a lot of further work and attention, and would be happy to see it accepted so the community can further explore these directions (fair user studies, the relation between approximate and optimal plans, investigations into the properties of foils relative to optimal actions, etc.). If accepted, I would strongly suggest a better integration of the main body and appendix, especially for Sec 3-5).\n\n\n[1] Karimi et al., https://arxiv.org/abs/2010.04050\n[2] Goyal et al., https://arxiv.org/abs/1904.07451\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is an intriguing study of agents that can give explanations (contrastive) of their actions via symbolic representation such as dialog.  Agents can also allow users to argue against the agents' decisions. I am extremely impressed by the quality of the reviewer comments and discussions.  It is also interesting that the reviewers have formed two camps of thought on the paper: One camp consists of R3 and R5 who are in agreement in vociferously criticizing the weak points in the paper.  The other camp consists of R1, R2, and R4, who champion the merits of what they see as strong points.  Notably, all reviewers have fairly high confidence values -- only one confidence score of 3 and all others are 4.

It was a borderline case and not an easy decision. In the end the program committee decided that the paper in its current form does not quite meet the bar, and would benefit from another revision (see e.g., R4 comments).  We think that the work is interesting, and encourage the authors to address the reviewers' comments and resubmit the work to another venue.

Decision: Reject