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: ICLR 2022 Poster (2022)
Keywords: Explanations
XAI
Post-hoc explanations

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 {\em 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 an inscrutable model. 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 test these methods on a popular Atari game (Montezuma's Revenge) and variants 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.

Published as a conference paper at ICLR 2022
BRIDGING THE GAP: PROVIDING POST-HOC SYMBOLIC EXPLANATIONS FOR SEQUENTIAL DECISION-MAKING PROBLEMS WITH INSCRUTABLE
REPRESENTATIONS
Sarath Sreedharan, Utkarsh Soni, Mudit Verma, Siddharth Srivastava, Subbarao Kambhampati School Computing & AI, Arizona State University {ssreedh3, usonil, mvermal3, siddharths, rao Pasu.edi
ABSTRACT
As increasingly complex AI systems are introduced into our daily lives, it becomes important for such systems be capable of explaining the rationale for their deci- sions and allowing users to contest these decisions. A significant hurdle to allow- ing for such explanatory dialogue could be the vocabulary mismatch between the user and the AI system. This paper introduces methods for providing contrastive explanations terms of user-specified concepts for sequential decision-making making settings where the system's 's model of the task may be best represented as an in- scrutable model. We do this by building partial symbolic models of local ap- proximation of the task that can be leveraged to answer the user queries. We test these methods on popular Atari game (Montezuma's Revenge) and variants of Sokoban (a well-known planning benchmark) and report the results of user studies to evaluate whether people find explanations generated this form useful.
INTRODUCTION
As AI systems are increasingly being deployed in scenarios involving high-stakes decisions, the issue of interpretability of their decisions to the humans in the loop has acquired re- newed urgency. Most work on interpretabil- ity has hither-to focused on one-shot classifica- tion tasks, and has revolved around ideas such as marking regions of the input instance (e.g. image) that were most salient in the classifi- cation of that instance (Selvaraju et al. 2016) Sundararajan et al. 2017). Such methods used for one-shot classification tasks don't general- ize well to sequential decision tasks-that are the focus of this paper. In particular, in se- quential decision tasks, humans in the loop might ask more complex "contrastive" explana- tory queries-such as why the system took one particular course of action instead of another. The AI system's 's answers to such questions will often tied to its internal representations and reasoning, traces of which are not likely to be comprehensible as explanations to humans in the loop. Some have viewed this ment to make AI systems use reasoning over symbolic models. We don't 't take a position on the methods AI systems to arrive at their decisions. We do however think that the onus of making their decisions interpretable to humans in the loop in their own vocabulary should fall squarely on the AI systems. Indeed, we believe that orthogonal to the issue of whether AI systems internal
Came abala visualization
Concepts: Not lusber
Concept Classiliers
Foll::
User
precossition
Symtoak::
shul not not
apprssmation moddal
current state
User
Fell2: Saj oittack,
Explanation:
resence
Interction
This is in step
openttngg on
The total cost of foll greater than cout plan (arh 30
Figure 1: Explanatory dialogue starts when the
user presents specific alternate plan. The system explains the preference over this alternate plan in terms of model information expressed terms of propositional concepts specified by the user, oper- ationalized as classifiers.
argu-

---

Published as a conference paper at ICLR 2022
symbolic representations to guide their own decisions, they need to develop local symbolic models that are interpretable to humans in the loop, and use them to provide explanations for their decisions.
Accordingly, in this work, we develop framework that takes set of previously agreed-upon user vocabulary terms and generates contrastive explanations in these terms Miller (2018); [Hsss- low (1988). Specifically, we will do this by learning components of local symbolic dynamical model (such as PDDL (McDermott et al. 1998)) that captures the agent model in terms of actions with preconditions and effects from the user-specified vocabulary. There is evidence that such mod- els conform to folk psychology Malle] (2006). This learned local model is then used to explain the potential infeasibility or suboptimality of the alternative raised by the user. Figure Presents the flow of the proposed explanation generation process in the context of Montezuma's 's Revenge (Wikipedial contributors. 2019). In this paper, we will focus on deterministic settings (Section 3) though we can easily extend the ideas to stochastic settings, and will ground user-specified vocabulary terms in the Al system's ' internal representations via learned classifiers (Section ( The model components required for explanations are learned by using experiences (i.e. state-action-state sets) sampled from the agent model (Section & 5 Additionally, we formalize the notion of local symbolic approx- imation for sequential decision- decision-making making models, and introduce the idea of explanatory confidence (Section[6). The exaplanatory confidence captures the fidelity of explanations and help ensure the system only provides explanation whose confidence is above given threshold. We will evaluate the effectiveness of the method through both systematic (IRB approved) user studies and computational experiments (Section 7). As we will discuss in Section 2 our approach has some connections to (Kim et al. 2018), which while focused on one-shot classification tasks, also advocates explana- tions in terms of concepts that have meaning to humans in the loop. Our approach of constructing local model approximations is akin to LIME (Ribeiro et al., 2016). with the difference being that we construct symbolic dynamical models terms of human vocabulary, while LIME constructs approximate linear models over abstract features that are machine generated.
2 RELATED WORK
The representative works in the direction of using concept level explanation 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. These works take a line quite similar to us in that they try to create explanations for current decisions in terms of set of user-specified concepts. While these works don't 't explicitly reason about explanatory confidence they do discuss the possibility of ex identifying inaccurate explanation, and tries address them through statistical tests. Another thread
of work, exemplified by works like (Koh et al. 20200 Lin et al. 2020), tries to force decisions to be made terms of user-specified concepts, which can then be used for explanations. There have also been recent works on automatically identifying
concepts like Ghhorann ctt al. 2019) and Hamidi-Hainee et al. (2018). We can also leverage these methods when our system identilies scenarios with insufficient vocabulary.
Most works in explaining sequential decision-making problems either use a model specified a starting point for explanation or focus on saliency-based explanations (cf. (Chakraborti et al. 22220), with very few exceptions. Authors of (Hayes & Shahl 2017) have looked at the of high-level concepts for policy summaries. They logical formulas to concisely characterize various policy choices, including states where a specific action may be selected (or not). Unlike our work. they are not trying to answer why the agent chooses a specific action (or not). (Waa et al. 2018) looks at addressing the suboptimality of foils while supporting interpretable features, but it requires the domain developer to assign positive and negative outcomes to each action. In addition to not addressing possible vocabulary differences between a system developer and the end-user, is also unclear if it is always possible to attach negative and positive outcomes to individual actions.
shared vocabulary
Another related work 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 is provided upfront. The explanations discussed in this paper can also be seen as a special case of Model Reconciliation explanation (c.f (Chakraborti et al. 2017)), where the human model is considered to be empty. The usefulness of preconditions as explanations has also been studied by works like (Winikoff 2017: Broekens et 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. 2019) which leverage interpretable reward components. Another group of works popular in
2

---

Published as a conference paper at ICLR 2022
RL explanations is the ones built around saliency maps (Greydanus et al. 2018 Iyer et al. 2018 Puri et al. 2019), which tend to highlight parts of the state that are important for the current decision. In particular, we used (Greydanus et al.] (018)) as baseline because many follow-up works have shown their effectiveness (cf. (Zhang et al. )020)) Readers can refer to Alharin et al. (2020) for a
recent survey of explanations in RI..
Another related thread of work, is that of learning models (some representative works include (Car- bonell & Gil 1990; (Stern & Jubal 2017 Wu et al., 2007)). To the best of our knowledge none of the works in this direction allow for noisy observations of state and none focused on identifying specific model components. While we are unaware of any works that provide confidence over learned model components, (Stern & Juba (017) provides loose PAC guarantees over the entire learned model.
PROBLEM SETTING
Our setting consists of an agent, be it programmed or RL-based, that has a model of the dynamics of the task that is inscrutable to the user (in so far that the user can't directly use the model repre- sentation used by the agent) in the loop and uses decision-making process that is sound for this given model. Note that here the term model is being used in a very general sense. These could refer to tabular models defined over large atomic state spaces, neural network- based dynamics models possibly learned over latent representation of the states and even simulators. The only restriction place on the model is that we can sample possible experiences from it. Regardless of the true representation, we will denote the model by the tuple M = (S, A, A,T,C, C). Where S and A are the state and action sets and T 5Sx A - SU (1. the absorber failure state) and C : S A - TR capture the transition and cost function. We will use 1 to capture failures that could occur when the agent violates hard constraints like safety constraints or perform any invalid actions. We will consider goal-directed agents that are trying to drive the state of the world to one of the goal states (G being the set) from an initial state I. The solution takes the form of sequence of actions or a plan π.
We will use symbolic action models with preconditions and cost functions (similar to PDDL models (Geffner Bonet, 2013)) as a way to approximate the problem for explanations. Such model can be represented by the tuple Ms = (Fs, As, Is, Gs,Cs), where Fs is a set of propositional state variables defining the state space, As is the set of actions, Is is the initial state, Gs is the goal specification. Each valid problem state is uniquely identified by the subset of state variables that are true in that state (so for any state s E SMs. where SMs is the set of states for MMs 8 S Fs). Each action E As is further described in terms of the preconditions preca (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 state 8 as a(s). We will focus on models where the preconditions are represented as a conjunction of propositions. If the action is executed in a state with missing pre- conditions, then the execution results in the invalid state 1. Unlike standard STRIPS models, where the cost of executing action is independent of states, we will use a state-dependent cost function of the form Cs: 2" As -> IR to capture forms of cost functions popular in RL. benchmarks.
4 CONTRASTIVE EXPLANATIONS
The specific explanatory setting, illustrated in Figure is one where the agent comes up with a plan (to achieve one of the goals specified in G from Z) and the user responds by raising an alternate plan T (the foil) that they believe should be followed instead. Now the system needs to explain why may be preferred over T by showing that y is invalid (i.e., , doesn't 't lead to a goal state one of the action in T results in the invalid state 1) or T is costlier than π (C(1, x) < C(I, x
To concretize this interaction, consider the modified version of Montezuma's Revenge (Figure D. The agent starts from the highest platform, and the goal is to get to the key. The specified plan t may require the agent to make its way to the lowest level, jump over the skull, and then go to the key with total cost of 20. Now the user raises two possible foils that are similar to i but use different strategies in place of jumping over the skull. Foill: instead of jumping, the agent just moves left (i.e., it tries to move through the skull) and, Foil2: 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 to the key. Using the internal model, the system can recognize that in the first case, moving left would lead to an invalid state, and in the second case, the foil is costlier, though effectively communicating this to the user is a different question. If there exists a shared
If the foil is as good as the original plan or better, then the system could switch to the foil.
3

---

Published as a conference paper at ICLR 2022
visual communication channel, the agent could try to demonstrate the outcome of following these alternate strategies. Unfortunately, this would not only necessitate additional cognitive load on the user's end to view the demonstration, but it may also be confusing to the user in far that they may not be able to recognize why in a particular state the move left action was invalid and attack action costly. As established in our user study and pointed out by Atrey et al. (2019). even highlighting of visual features may not effectively resolve this confusion. This scenario thus necessitates the use of methods that are able to express possible explanations in terms that the user may understand.
Learning Concept Maps: The input to our system is the set of propositional concepts the user associates with the task. For Montezuma, this could involve concepts like agent being on a ladder, holding onto the key, being next to the skull. Each concept corresponds to propositional fact that the user associates with the task's states and believes their presence or absence in a state could influence the dynamics and the cost function. We can collect such concepts from subject matter experts as by Cai et al. (2019), or one could just let the user interact with or observe the agent and then provide possible set of concepts. We used the latter approach to collect the propositions for our evaluation of the Sokoban domains (Section 7 and A.7). Each concept corresponds to a binary classifier, which detects whether the proposition is present or absent in given internal state (thus allowing us to convert the atomic states into a factored representation). Let C be the set of classifiers corresponding to the high-level concepts. For state & S, we will overload the notation C and specify the concepts that are true as C(s), i.e., C(s) = fes|cz E C (4))) = 1} (where Q: is the the jth concept and we overload the notation also stand for the label of the jth concept). The training set for such concept classifiers could come from the user (where they provide set of positive and negative examples per concept). Classifiers can be then learned over the model states or the internal representations used by the agent decision secision-making (for example activations of intermediate neural network layers).
classifier corresponding
Explanation using concepts: To explain the preference of plan ι over foil TT. we will present model information to the user taken from a symbolic representation of the agent model. But rather than requiring this model to be an exact representation of the complete agent model, we will instead focus on accurately capturing a subset of the model by instead trying to learn a local approximation
Definition 1 A symbolic model M = (C, AS, C(T),C(G) CB). is said to be a local symbolic approximation of the model M = (S. A, for regions of interest á C S if Vs $ and Va E A, we have equivalent action a E AG. such that (a) a (C(s)) = C(T(s, (assuming ecnss C(sg)-
C(1) = 1) and (b) C)(C(()), = C(),a) and (c) C(G) =
Following Section 3 this is a PDDL-style model with preconditions and conditional costs defined over the conjunction of positive propositional literals. A.2 establishes the sufficiency of this rep- resentation to capture arbitrarily complex preconditions (including disjunctions) and cost functions expressed in terms of the proposition set C. Also to establish the preference of plan does not require informing the users about the entire model MS. but rather only the relevant parts. To establish the invalidity of xy. we only need to explain the failure of the first failing action a,, i.e., the one that resulted in the invalid state (for Foil/ this corresponds to move-left action at the state visualized in Figure Dp. We explain the failure of action in state by pointing out proposition that is an action precondition which is absent in the given state. Thus a concept c, E C is considered an explanation for failure of action 0; state 8i, if e E prece; \ C(s.). For Foill, the explanation would be the action move-left failed in the state as the precondition skull-not-on-left was false in the state.
This formulation can also capture failure achieve goal by appending additional goal action the end of the plan, which causes the state to transition to an end state, and fails for all states except the ones in G. Note that instead of identifying all the missing preconditions, we focus on identifying a single precondition, as this closely follows prescriptions from works in social sciences that have shown that selectivity or minimality is an essential property of effective explanations (Miller 2018).
For explaining suboptimality, we inform the user about the symbolic cost function CS. To ensure minimality, rather than provide the entire cost function, we will instead try to learn and provide an abstraction of the cost function Cuba
Definition 2 For the symbolic model MZ= = CC)) C(G), CS), an abstract cost function Cghe
2d A + R is specified as: Cih* ((ot),; = min(Cy a)ls E Sug/ A (ct....() C s).
4

---

Published as a conference paper at ICLR 2022
a
Algorithm for Finding Missing Precondition
b Algorithm for Finding Cost Function
1:
procedure PRECONDITIN-SEARGE
1:
procedure COST-PUNCTION-STANE
2: Japur: daa; Sampler, A1", ; C,
2:
Input: ny. Cz. Sampler, Mr ; C,
3: Outpur: Missing precondition Cyee
3:
Output: Cxz
4: Procedure:
4:
Procedirr::
5:
Pis <- Missing concepts fail
5:
for cone limit in [[|C]] do
6:
sample count =0
conc Jist [I. for in to k (the length of the foil) do + T(e,, a.)
pument_foil coil_
7:
while sample.count <. do
7:
8:
Sampler
9:
if (s,, ana) * then
10:
Me C(s) n Hz
10:
find. unddmmin.conn.see (oonn..st(C(()) lomi,
min cost=
11:
[Mtl] then return Signal concept
11:
current
min.cost
complete
12:
cone list. www.l.pssssh...... min.cost)
12:
sample count return any C. precs.pree.set
13:
current cost > C. return conc.list Jist return Signal that concept incomplete
Figure Algorithms for identifying (a) missing precondition and (b) cost function
Intuitively, Cape ((c), J a) k can be understood stating that executing the action a, in the presence of concepts (cI,-., (&) costs at least k. We can Cgbe in an explanation by identifying sequence of concept set Ca, = (ÉI,... C2), corresponding to each step of the foil π {a1, ax), such that (a) Cj is subset of concepts in the corresponding state reached by the foil and (b) the total cost of abstract cost function defined over the concept subsets are larger than the plan cost Ei= Cg (C,, a,) > C(I,x). For Foil2, the explanation would include the information executing the action attack in the presence of the concept skull-on-left, will cost at least 500.
5 IDENTIFYING EXPLANATIONS THROUGH SAMPLE-BASED TRIALS
For identifying the model parts, we will rely on the internal model to build symbolic estimates. Since we can separate the two explanation cases using the agent's internal model, we will only focus on the problem of identifying the model parts given the required explanation type.
Identifying failligg precondition: The first case we will consider is the one related explaining plan failures. In particular, given the failing state and failing foil action Opai we want to find a concept that absent in Stai but a precondition for the action Ogai We will try to approximate
whether concept is precondition or not by checking whether they appear in all the states sampled
from the model, where aam is executable (S set of all sampled states). Figure 2[a) presents the pseudo-code for finding such preconditions. We rely the sampler (denoted Sampler) create the set S. where the number of samples used is upper-bounded by a sampling budget f. poss-prec_set captures the set of hypotheses regarding the missing precondition maintained over the course of the search.
We ensure that models learned are local approximations by considering only samples within some distance from the states in the plan and foils. For reachability- baased distances, we can use random walks generate the samples. Specifically, observed in the plan/foil and end the sampling episode whenever the number of steps taken crosses given threshold. The search starts with set of hypotheses for preconditions Hi and rejects individual hypotheses whenever the search sees state where the action a fast is executable and the concept absent. The worst-case time complexity of this search linear on the sampling budget.
can start random walk from one of the states
If the hypotheses set turns empty, it points to the fact that the current vocabulary set is insufficient to explain the given plan failure. Focusing on single model- component not only simplifies the learning problem but we will see in Section [ allows us to quantify uncertainty related to the learned model components and also allow for noisy observation. These capabilities are missing from previous works.
Identifying cost function: We will employ a similar sampling-basee method to identify the cost function abstraction. Unlike the precondition failure case, there is single action but rather we need to choose a level of abstraction for each action the foil (though it may be possible in many cases to explain the suboptimality of foil by only referring subset of actions in the foil). For the concept subset sequence (Cny (CI,.., Ck)) that constitutes the explanation,
choose,
5

---

Published as a conference paper at ICLR 2022
will also try to minimize the total number of concepts used in the explanation (E==1. []. Figure 2(b) presents a greedy algorithm to find such cost abstractions. The procedure find_min.conc.set takes the current concept representation of state 8; in the foil and searches for the subset C2 of ((;))
with the maximum value for Cg (C;, 0:), where the value is approximated through sampling (with budget é), and the subset size is upper bounded by conc limit. As mentioned Definition 2 the value of Cg (C,, a.) is given as the minimal cost observed when executing the action a; in a state where C are true. The algorithm incrementally increases the conc limit value till solution is found or if crosses the vocabulary set size. Note that this algorithm is not an optimal one, but we found to be effective enough for the scenarios we tested. We can again enforce the required locality within the sampler and similar to the previous case, we can identify the insufficiency of the concept set by the fact that we aren't 't able to identify valid explanation when conc Jimit is at vocabulary size. The worst case time complexity of the search is O(CC) | x (E(). We are unaware of any existing works for learning such abstract cost-functions,
6 QUANTIFYING EXPLANATORY CONFIDENCE
One of the critical challenges faced by any post hoc explana- tions is the question of fidelity and how accurately the gener- ated explanations reflect the decision-making process. In case, we are particularly concerned about whether the model component learned using the algorithms mentioned in Section 5 is part of the exact symbolic representation. Mÿ (for a given set of states S and actions A). Given that model components based on concepts provided by the user, it would be easy to generate explanations that feed into the user's confirmation biases about the task.
Action Execuned
6
Concept precenditon
identifying
the
a
Concept glnerved
Our confidence value associates probability of correctness with each learned model component by leveraging learned re- lationships between the concepts. Additionally, our confidence measure also captures the fact that the learned concept classi- fiers will be noisy best. So we will the output of the classi- fiers as noisy observations of the underlying concepts, with the observation model P(O?, |c; E S) (where O% captures the fact that the concept was observed and o; E S represents whether the concept was present in the state) defined by a probabilistic model of the classifier prediction.
(A)
function
Concept present
C
concept observed
Ocuack
05
Observed cost bek
(B)
Figure 3 presents graphical model (with notations defined inline) for measuring the posterior of model component be- ing true given an observation generated from the classifier on sampled state. For given observation of executions of ac- tion a in state s (O; = True or just O2), the positive or negative observation of concept G; (Ot.
Figure 3: Simplified probabilistic graphical models for confidence of learned (A) Preconditions and (B) Cost).
xr where æ (True, False)) ) and an observation that action's 's cost is greater than ls (Oc(s.)22k), the updated explanatory confidence for each explanation type is provided as (1) P(e. E p.,..., = A O", A Octeree), where E Pa captures the fact that the concept is part of the precondition of a and Oz(s)eciss the observed status of the rest of the concepts, and (2) ([c)))((())))) 2 k(O = I Oc(s.a)==x A Octoree), where C (="(((()),a) 2 k asserts that the ab- stract cost function defined over concept is greater than k
The final probability for the explanation would be the posterior calculated over all the state samples. Additionally, we can also extend these probability calculations to multi-concept cost functions. We can now incorporate these confidence measures directly into the search algorithms described in Section 5 to find the explanation that maximizes these probabilities. In the case of precondition identification, given noisy classifier, we can no longer use the classifier output to directly remove a concept from the hypothesis set Hp. At the start of the search, we associate a prior to each hypothesis and use the observed concept value at each executable state to update the posterior. We only remove precondition from consideration if the probability associated with it dips below threshold n.

---

Published as a conference paper at ICLR 2022
Hight
jovobbn--wlttcn
Jutizban-cat
Figure 4: The plan and foils used in the evaluation, plans are highlighted in blue and foils in red: (i) shows the two montezuma's revenge screens used (ii) the two variations of the sokoban game used. For Montezuma the concepts corresponding not.on_rope, nol_dne. not and is.clear wwwwn.of.crrfe for failure points A, B, C and D respectively (note all concepts were originally defined as positives and we formed the not concepts by negating the output of the classifier). Concepts switch on and on pink cell for Sokoban cost variants that results in push action costing 10 (instead of 1)
missing precondition are
For cost function identification, if we have multiple cost functions with the same upper bound, we select the one with the highest probability. We also allow for noisy observations in the case of cost identification. The updated pseudo codes are provided in A.3
We can simplify the probability caleulations by making the following assumptions: (1) the distri- bution of all con-precondition concepts in states where the action is executable is the same as their overall distribution (which can be empirically estimated), (2) The cost distribution of action over states corresponding 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 first assumption implies that the likelihood of seeing a non monnprecondition executable is equal the likelihood of it appearing in any sampled state. In the most general case, this equals P(c: E s| s(Oc(s)te,) ), i.e., the likelihood of seeing this concept given the other concepts in the state. The second assumption 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 a cost greater than i for a randomly sampled state (pC(..)24). This assumption can be further relaxed by considering the distribution of the action cost given the rest of the observed set of concepts (though this would require more samples to learn). The full derivation of the probability calculations with the assumptions is provided in AA.4 and an empirical evaluation of the assumptions in A. 10 All re- sults reported in the next section were calculated using the probabilistic version of the search while allowing for noisy concept maps.
concept in sampled state where the action
EVALUATION
We tested the approach on the open-Al gym's deterministic implementation of Montezuma's Re- venge (Brockman et al. (016) for precondition identification and two modified versions of the gym implementation of Sokoban (Schrader (018)) for both precondition and cost function identification. To simplify calculations for the experiments, we made an additional assumption that the concepts are independens. All hyperparameters used by learning algorithms are provided in A.6
Montezuma's 's Revenge: We used RAM-based state representation here. To introduce richer pre- conditions to the settings, we marked any non-noop action that fails change the current agent state and action that leads to midair states where the agent is guaranteed to fall to death (regardless of actions taken) as failures. We selected four invalid foils (generated by the authors by playing the game), three from 1 and one from screen-4 of the game (Shown in Figure (i)). The plan for screen-1 involved the player reaching a key and for screen-2 the player has to reach the bottom of the screen. We specified ten concepts, which we believed would be relevant to the game, for each screen and collected positive and negative examples using automated scripts. We used AdaBoost Classifiers (Freund et al. 1999) for the concepts and had an average accuracy of 99.72%.
The original sokoban game involves the player pushing a box from one position to target position. We considered two variations of this basic game. One that requires switch (green cell) the player could turn on before pushing the box (referred to as Sokoban-switch), and second version (Sokoban-cells) included particular cells (highlighted in pink) from which it is
Sokoban Variants:
7

---

Published as a conference paper at ICLR 2022
costlier to push the box. For Sokoban-switch, had two variations, one in which turning on the switch was a precondition for push actions and another one in which it merely reduced the cost of pushing the box. The plan and foil (Shown in Figure (ii) were generated by the authors by playing the game. We used a survey of graduate students unfamiliar with our research to collect the set of concepts for these variants. 'he survey allowed participants to interact with the game through web interface (the cost-based version for Sokoban-switch and Sokoban-cell), and at the end, they were asked to describe 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 negatíve instances. We focused on 18 concepts and 32 concepts for Sokoban-switch and Sokoban-cell, respectively, based on the frequency with which they appear in game states, and used Convolutional Neural Networks (CNNs) for the classifier (which mapped state images to concepts). The classifiers had an average accuracy of 99.96995 .9% (Sokoban-switce) and 99.34% (Sokoban-cell).
Computational Experiments: We ran the search to identify preconditions for Montezuma's foils and Sokoban-switch and cost function for both Sokoban variants. From the original list of concepts, we doubled the final concept list used by including negations of each concept (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 cutoff probability of 0.01 for each concept. In each case, our search- based methods were able to identify the correct model component for explanations. Figure StA), presents the probability our system assigns to the correct missing precondition plotted against the sampling budget. It presents the average calculated across ten random episodes (which were seeded by default using urandom (Linux, 2013)). We see that in general, the probability increases with the sampling budget with few
3.0-
Explanation Confidence
MontezumaFoilz
Montegamiiol13
0.7
Nontinuma level3 Foi4
Socoban Foll).
0.8
10
100
250
500
150
2000
(A)
Sampling Budget
1.4
Explamation Confidence
9.8
small dips due to misclassificatios. We had the smallest explanation likelihood for foill in screen I in Montezuma (with 0.511 = 0,001), since it used a common concept, and its presence in the executable states was not strong evidence for them being a precondition. Though even in this case, the system correctly identified this concept as the best possible hypothesis for precondition as all the other hypotheses were eliminated after around 100 samples. Similarly, Figure B) plots the probability assigned to the abstract cost functions.
3.6
Sokoban Call Cost
Sokoban
(8)
10 100
250
Sampling Budget
500
750
1000
Figure 5: The average probability as- signed to the correct model compo- nent by the search algorithms, calcu- lated over ten random search episodes with std-deviation.
User study: With the basic explanation generation meth- ods in place, we were interested in evaluating if users would find such an explanation helpful. All study designs followed our local IRB protocols. We were interested in measuring the effecttivness of the symbolic explanations over two different di- mensions: (a) whether people prefer explanations that refer the symbolic model components over a potentially more concise and direct explanation and (b) whether such explanations help people get a better understanding of the task (this mirrors the recommendation established by works like Hoff- man et al. (2188). All study participants were graduate students (different from those who specified the concepts), the demographics of participants can be found in A.9
For measuring the preference, we tested the hypothesis
HI: People would prefer explanations that establish the corresponding model component over ones that directly presents the foil information (i.e. the failing action and per-step cost)
This is an interesting hypothesis, as in our case, the explanatory text for the baseline is a lot more concise (in terms of text-size). As per the selectivity principle (Miller 2018)), people prefer ex- planations that doesn't contain any extraneous information and thus we are effectively testing here whether people find the model information extraneous. The exact screenshots of the conditions
8

---

Published as a conference paper at ICLR 2022
Table 1: Results from the user study
Prefers symbols
Average Likert-
P-value
Method
of Participant
Average Time Taken (sec)
Average of Steps
score
Precondition
19/20
3.47
1.0 x 10
Coneept-Based
23
43.78 = 12.59
35.87 = 9.69
Cost
3.21
0.03
Saliency Map
25
134.24
52.64 I1.11
(a) HI
(b) H2
are provided in A.12 We used a within-subject study design where the participants were shown an explanation generated by our method along with simple baseline. Precondition case involved pointing out the failing action and the state it was executed and for the cost case the exact cost of ex- ecuting each action in the foil was presented. 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 five-point Likert scale the completeness of the chosen explana- tion (1 being not at all complete and 5 being complete). For precondition, we collected 5 responses per each Montezuma foil, and for cost we did 10 per each sokoban variant (40 in total). Table Ta presents the summary of results from the user study and supports H1. In fact, binomial test shows that the selections are statistically significant with respect to a = 0.05.
For testing the effectiveness of explanation in helping people understand the task, we studied H2: Concept-based precondition explanations help users understand the task better than saliency map based ones.
We focused saliency maps and preconditions, as saliency map based explanation could highlight areas corresponding failed precondition concepts (especially when concepts correspond to local regions within the image). Currently we are unaware of any other existing explanation generation method which can generate explanation for this scenario without introducing additional knowledge about the lask. We measured the user's understanding of the task by their ability to solve the task by themselves. We used between-subject study design, where each participant was limited to single explanation type. 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 that there would be bonuses for people who finish the game in the shortest time. They were not provided any exact instructions about the dynamics of the game. During the game, if the participant performs an action whose preconditions are not met, they are shown their respective explanation. Additionally, the current episode ends and they will have to restart the game from the beginning. One group of users were provided the precondition explanations generated through our method, while the rest were presented with saliency map. For the latter, we used a state of the art saliency-mo map based explanation method Greydanus al. (2018). The participants were told that highlighted regions are parts of the state an Al agent would focus on if it was acting in that state. In all the saliency map explanations, the highlighted region included the precondition region of switch (shown in 12). In total, we collected 60 responses but had to discard 12 due to the fact they reported not seeing the explanations. Table presents the average time taken and steps taken to complete the task (along with 95% confidence intervals). As seen, the average value is much smaller for concept explanation. Additionally, a two-tailed t-test shows the results are statistically significant (p- ialves of 0.021 and 0.038 against significance level = 0.05 for time and steps respectively).
CONCLUSION
We view the approaches introduced in the paper the first step towards designing more general post hoc symbolic explanation methods for sequential decision-making problems. We facilitate the generation of explanations user-speeified terms for contrastive user queries. We implemented these methods in multiple domains and evaluated the effectiveness of the explanation using user studies and computational experiments. As discussed in (Kambhampati et al. (202T), one of the big advantages of creating such symbolic representation is that it provides symbolic middle layer that can be used by the users to not only understand agent behavior, but also to shape it. Thus the user could use the model as starting point to provide additional instructions or to clarify their prefer- ences. Section I. contains more detailed discussion on various future works and related topics, including its applicability to settings with stochasticity, partial observability, temporally extended actions, the process of collecting more concepts, identifying confidence threshold and possible eth- ical implications of using our host-hoc explanation generation methods.

---

Published as a conference paper at ICLR 2022
9 ACKNOWLEDGEMENTS
This research supported in part by ONR grants N00014-16-1-289.. N00014-18-1-244, N00014- 18-1 1-240, N00014-9-1-2119, 19, AFOSR grant FA9550-18-1 NSF 1909370, DARPA SAIL-ON grant W91 INF19-2-0006 and a JP Morgan AI Faculty Research grant. We thank Been Kim, the reviewers and the members of the Yochan research group for helpful discussions and feedback.
REFERENCES
Alnour Alharin, Thanh-Nam Doan, and Mina Sartipi. Reinforcement learning interpretation meth- ods: A survey. IEEE Access, 8:171058-171077, 2020.
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 LJCAI, 2019.
Akanksha Atrey, Kaleigh Clary, and David Jensen. Exploratory not explanatory: Counterfactual analysis of saliency maps for deep reinforcement learning. arXiv preprint arXiv/19/2005743, 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 on computer vision and pattern recognition, pp. 6541 -649, 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: 7/aaai org ojs/ /ww///inxxx../mm//// php/ S.CAss//ssue/view////
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. CoRR, abs/1606.01540, 2016. URL http::ttpp:rrtttt org/
/bbs/606.. 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. German Conference on Multiagent System Technologies, pp. 28-39. Springer, 2010.
Carrie J Cai, Emily Reif, Narayan Hegde, Jason Hipp. Been Kim, Daniel Smilkov, Martin Wat- tenberg, Fernanda Viegas, Greg S Corrado, Martin Stumpe, et al. Human- tools for coping with imperfect algorithms during medical decision-male making. In Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, pp. 1-14, 2019.
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 as model reconciliation: Moving beyond explanation as soliloquy. In IJCAI, pp. 156-163, 2017.
Tathagata Chakraborti, Sarath Sreedharan, and Subbarao Kambhampati. The emerging landscape of explainable ai planning and decision making. In IJCAI, 2020.
Yoav Freund, Robert Schapire, and Naoki Abe. A short introduction to boosting. Journal-Japanest Society For Artificial Intelligence, 14(771-780):1613 1999.
Hector Geffner and Blai Bonet. concise introduction to models and methods for automated plan- ning. Synthesis Lectures Artificial Intelligence and Machine Learning, 8(1):1-141, 2013.
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, 2019.
Samuel Greydanus, Anurag Koul, Jonathan Dodge, and Alan Fern. Visualizing and Understanding Atari Agents. In ICMI, 2018
10

---

Published as a conference paper at ICLR 2022
Mandana Hamidi- Haines, Zhongang Qi, Alan Fern, Fuxin Li, and Prasad Tadepalli. Interactive naming for explaining deep neural networks: a formative study. arXiv preprint arXiv:18/2.07150, 2018.
Bradley Hayes and Julie Shah. Improving robot controller transparency through autonomous pol- icy explanation. In 20/7 12th ACM/IEEE International Conference Human-Robot Interaction (HRI), pp. 303-312. IEEE, 2017.
Germund Hesslow. The problem of causal selection. Contemporary science and natural explana- tion: Commonsense conceptions of causality, pp. 11-32, 1988.
Robert R Hoffman, Shane 'I' Mueller, Gary Klein, and Jordan Litman. Metries for explainable ai: Challenges and prospects. arXiv preprint arXiv: 2018.
Rahul Iyer, Yuezhang Li, Huao Li, Michael Lewis, Ramitha Sundar, and Katia Sycara. Transparency and explanation in deep reinforcement learning neural networks. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Sociery, pp. 144-150, 2018.
7oe Juozapaitis, Anurag Koul, Alan Fern, Martin Erwig, and Finale Doshi-Velez. Explainable Reinforcement Learning via Reward Decomposition. IJCAI Workshop on explainable Al (XAI), 2019.
Subbarao Kambhampati, Sarath Sreedharan, Mudit Verma, Yantian Zha, and Lin Guan. Symbols as lingua franca for bridging human-ai chasm for explainable and advisable AI systems. In AAAI, 2021.
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.
Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International Conference Machine Learning, pp- 5338-5348. PMLR, 2020.
Pat Langley. Varieties of Explainable Agency, In XAIP, ICAPS, 2019.
Zhengxian Lin, Kim-Ho Lam, and Alan Fern. Contrastive explanations for reinforcement learning via embedded self predictions. arXiv preprint arXiv:2010.05/80, 2020.
Linux. urandom(4) Linux man page, March 2013.
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. 22698, 2019.
Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable reinforcement learn- ing through a causal lens. In AAAI, 2020.
Bertram F Malle. How the mind explains behavior: Folk explanations, meaning, and social interac- fion. Mit Press, 2006.
Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, and David Wilkins, Pddl-the planning domain definition language. Technical report, Yale Center for Computational Vision and Control, 1998.
Tim Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intel- ligence, 2018.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Coumapeaau, M. Brucher, M. Perrot. and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2833 2011.
11

---

Published as a conference paper at ICLR 2022
Nikaash Puri, Sukriti Verma, Piyush Gupta, Dhruv Kayastha, Shripad Deshmukh, Balaji Krishna- murthy, and Sameer Singh. Explain your move: Understanding agent actions using specific and relevant feature attribution. arXiv preprint arX1v:1912.12191. 2019.
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
2015.
Max-Philipp B. Schrader.
gym-sokoban.
httpps///gtthub..ccmmmshhhabaaae
gym-sokoban, 2018.
Ramprasaath R Selvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra. Grad-cam: Why did you say that? arXiv preprint 1rX.v.161..07450, 2016.
Roni Stern and Brendan Juba. Efficient, safe, and probably approximately complete learning of action models. arXiv preprint arXiv: /70500861.0011 2017.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328, PMLR, 2017.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
J Waa, J van Diggelen, K 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.
index.nexi....i. php?title=Monttttttccome ezuma game) 6oldl))222lllll1l0230033330 27s Revenge_ (rgegeeeeiiioo__ggeeeeeoooaaalee 2020].
[Online; accessed 14-January-
Michael Winikoff. Debugging agent programs with why? questions. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pp. 251-259, 2017.
Kangheng Wu, Qiang Yang, and Yunfei Jiang. Arms: An automatic knowledge engineering tool for learning action models for ai planning. The Knowledge Engineering Review, 2202):135-152, 2007.
Zahra Zahedi, Mudit Verma, Sarath Sreedharan, and Subbarao Kambhampati. Trust-aware planning: Modeling trust evolution in longitudinal human-robot interaction. arXiv preprint arXiv:2105.01220. 2021.
Ruohan Zhang, Sihang Guo, Bo Liu, Yifeng Zhu. Mary Hayhoe, Dana Ballard, and Peter Stone. Machine versus human attention deep reinforcement learning tasks. arXiv preprint arXiv:2010. 15942, 2020.
12

---

Published as a conference paper at ICLR 2022
A
APPENDIX
A.1 OVERVIEW
This appendix contains the following information; (1) the assumptions and theoretical results related to the representational choices made by the method, (2) the pseudo-code for the probabilistic version of the algorithms which were used in the evaluation, (3) the derivation of the formulas for confidence calculation (4) the derivation of the formulas for using noisy classifier and finally (5) the details on the experiment that are not included in the main paper (6) analysis assumptions made and (7) extended discussion of various future works and possible limitations of the current method and (8) screenshots the various interfaces.
A.2 SUFFICIENCY OF THE REPRESENTATIONAL CHOICE
The central representational assumption we are making that it is possible approximate the 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-making problems from a variety domains and have clear real-world utility Benton et al. (2199).
Revisiting the definition of local approximations for given internal model M (8, A,T, and of states $ S, define local approximation
Definition 3 A symbolic model M (C, approximation for the problem II interest $ S if Vs å and Ya A. we have an equivalent action at As. such that (a) a (C(s)) C(T(s,a)) (assuming C(1) 1) and (b) C)(C(s), C(s,a) and (c)
is said to be a local symbolic (M (where M AS, for regions of
CCC) = Nageons C(s)).
We can show that
Proposition 1 If Š and are finite, there exists a symbolic model M = (C, C(), CG)) such that it's local symbolic approximation.
We can show this trivially by construction. We introduce set of concepts whose size is equal to the number of state in S (for s; S, we introduce a concept Cs and we define a conditional effect and conditional cost function for every viable transition in for an action in M and the precondition of becomes a disjunction over the negation of concepts corresponding to the states where a fails. In Proposition 3 we will further discuss how these disjunctive precondition turns into new conjunctive preconditions.
Proposition 2 If T., T2 are two plans such that कं 1 T2 for II then precedence is conserved in a symbolic model M that is local approximation that covers all states appear in π2-
This trivially follows from the fact that per definition of local approximation both the invalidity of plans and cost of plans are conserved. Which means any preference over plans that can be established in the complete model can be established in the approximate model.
Apart from this basic assumption, we make one additional representational assumption, namely, that the precondition can be expressed as conjunction positive concepts. Which brings us the next proposition
Proposition 3 A precondition of action preca,, which is represented as arbitrary logical formula over a set of propositions P can be mapped to a conjunction over positive literals from different set P' (which can be generated from P).
To why this holds, consider case where the precondition of action is expressed arbitrary propositional formula, ((C). In this case, we can express its conjunctive normal form øf (C). Now each clause in (C(C) can be treated
compound positive concept. Thus cover
13

---

Published as a conference paper at ICLR 2022
b Algorithm for Finding Cost Function
Algorithm Finding Missing Precondition
procedure COST-PUNCTION-SEAKCC
1:
procedure PRECONDITON-SEANE
2:
Iopat: Stal Abü; Sampler, M C, f
Input: Car, Sampler, M ,
3:
Outpur: Missing, precondition Cyes
Output:
Caz
4:
Procedure:
4: Procedure:
5:
P Missing concepts ffai
limit [C]
6:
Ps +- Initialize priors
6:
current foil. =
7:
sample.count =0
Prob_list =
8:
while sample,count <. i do
8:
conc_list =
9:
Sampier
for in (the length the foil) do
10:
if (s,,, ata) then
10:
Cs. min cost,
P(e, 22)mn cost
11:
Update Pr
12:
Fliminate any P. such that Pa((z))
11:
find min canc set(C)(((s (01,-.a; 1)1) ag cone limit,
current foil
min_cost
13:
[PI then Signal concept list incom-
12:
Prob list list.pushiPP (t..dii.pusd(((e...)))) (2g.a:))mmm...om
plete
14:
Ca count +=
13:
conc mim..lisppushhC... min_cost)
return C, Eposs_prec_see with highest probubility
14:
if current foil cost >> C- then return cone list, Proh list
return Signal that the concept list is incomplete
Figure 6: The extension of the two algorithms to use the confidence values, Subfigure (a) presents the algorithm for missing precondition and (b) the one for cost. function
such arbitrary propositional formulas by expanding concept list with compound concepts (in- cluding negations and disjuncts) whose value is determined from the classifiers for the corresponding atomic concepts. Note that the set of all possible compound concepts could be precomputed and add no additional overhead on the human's 's end. Also note, this is completely compatible with relational concepts as relational concepts defined over a finite set of objects can be compiled into set of finite propositional concepts. Proposition 3 also extends to cost functions, which we assume to be defined over conjunction of concepts.
A.3 EXPLANATION IDENTIFICATION WITH PROBABILISTIC CONFIDENCE
Now the objective of the methods become not only identify an explanation but that has the likelihood of being true. This means for precondition the objective becomes. Given the failing state Stail and action Gfail and set of states S where @tail is exccutable, explanation identification for failing precondition involves finding concept E C C(saa) such that arg max P(c E Pawa(S). In terms of the algorithm for finding precondition, the main difference is the fact that instead of eliminating the hypothesis directly from their presence or absence in the given state, we will instead use the observation to update the posterior over the hypothesis being true. We can also further improve the efficiency of search by removing possible hypothesis for final precondition, when its probability dips below a low threshold
0 and the observation model is perfect (P(Os, (cs E s) = 1 and P(O |c, & s) = 0), then the reasoning reflects the climination based model learning method used by many of the previous approaches Carbonell & Gil (990); Stern & Juba 2017).
Note that when
Now for the cost function, the objective becomes
Definition 4 Given foil π² (a1,..., a.) with ff unique actions (where A(a;) returns the unique action label), a set sets of states (s,.-.,,mm) where each $ Sta.) corresponds to a set of states where an action A(a,) is executable, the explanation for suboptimality correpond to finding an abstract cost function, that tries to minimize for the cost and maximize the probabilities.
mine
Σ 1| P(C(Ci,))) (A(a))( 11x P(CC)( 2 ky (Ba(ae)) E=1.f
subject Caba (Cr, > C(1
Rather than solve this full multi-objective optimization problem, will the cost the primary optimization criteria and use probabilities as a secondary one. Figure b(b), present a modified ver- sion of the greedy algorithm find such cost abstractions. The procedure find min cone set, takes
14

---

Published as a conference paper at ICLR 2022
the dira
(A)
(B)
Concapt
(C)
(D)
Figure 7:
A simplified probabilistic graphical models for explanation inference, Subfigure (A) and (B) assumes classifiers to be completely correct, while (C) and (D) presents cases where the classifier may be noisy.
the current concept representation of state i in the foil and searches for the subset C2 (and its prob- abilistic confidence) of the state with the maximum value for (C,, a,), where the value is again approximated through sampling (with budget f), and the subset size is upperbounded by conc limit. If there multiple abstract cost function with the same probability. Similar to the algorithm described in the main paper, here we incrementally increase the max concept size till we find an abstract cost function that meets the requirement.
cost it selects the one with the highest
A.4 CONFIDENCE CALCULATION
For confidence calculation, we will be relying on the relationship between the random variables captured by Figure 7 (A) for precondition identification and Figure 7 (B) for cost calculation. Where the various random variables captures the following facts: O indicates that action can be executed in state s, C, E Pa- -concept e; is a precondition of a, O the concept c; is present in state 8, Cabe ((c)),a) 2 k - the abstract cost function guaranteed to be higher than or equal to k and finally a)(a.)>>: stands for the fact that the action execution in the state resulted in cost higher than or equal to k. Since we don't 't know the exact relationship between the current concept in question is, for notational convenience we will use the symbol Oc(s)),, to stand for the other concepts observed in the given state.
We will allow for inference over these models, by relying the following simplifying assumptions - (1) the distribution of all non-pree non-precondition concepts in states where the action is executable the same their overall distribution across the problem states (which can be empirically estimated), (2) cost distribution of an action over states corresponding 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 first assumption implies that the likelihood of seeing a non-preconnition concept in sampled state is equal the likelihood of it appearing in any sampled state. In the most general case this distribution can be given as P(c, P(cy|Oc(eNNe))) i.e. the likelihood of seeing this concept given the other concepts in the state. This distribution can be empirically estimated per user (or shared vocabulary) independent of the specific explanatory query. While the second one implies that for a concept that has no bearing on the cost function for an action, the likelihood that executing the action in state where the concept is present will result in a cost greater than & will be the same as that of the action exccution resulting in cost greater than for a randomly sampled state (Po(.a)2ks). This assumption can be further relaxed by considering the distribution of the action cost under the observed set of concepts (though this would clearly require more samples to learn).
For single sample, the posterior probability of explanations for each case can be expressed as follows: For precondition estimation, updated posterior probability for a positive observation can be computed as P(c, E Pa A 0% A Occoree)) = (1 P(c: & pa O Ozonee))) )), where
15

---

Published as a conference paper at ICLR 2022
P(e. @ Pa Pa A A Octone))
P( l $ Pa A O A Octone)) * P(c. $ pa A Octare)
P(O Og A Occote.
Given G $ Pe is independent of O2 and Oc(s)a also expanding the denominator we get
la & Pa O Ocon)) + P(e. $ pa) P(O lcs Pa A Or A Oc(ore)) P(c, pa)+ P(O los E pa A Or A Octoree)) P(c: E pc)
From our assumption, we know P(O Pa A O A C(()))))) ) is same as the distribution G over the problem states (p(ca(Oc(e)ee)) ) and P(Og, (cs Pa A Og) must be one.
P(cs/Oc(nne)) P(c & Pa) p(c: # P(c: $ pa) + P(c: E pa)
For cost calculation, ignore (c(s) since according the graphical model once the concept is observed, Oc(s.a)2k is independent of the other concepts.
((c)), 2 k/0,, A Oc(Ha)24) P(Octe.a)2a O2 A AC, (fc)).a) k) P(C ((cx), 2 k(O.,)
P(Oc(s.)2x (22)
Where PiOc(s.a)2 Cabe ((+)),a) 2 k)) should be 1 and Ce ((ci),a) a) 2 k independent of Oz,- Which gives
((c)))()))))) 2x)
P(Oc))m)24104)
P(C ([()) k)
P(Octs.a)za Oe Ca (1a)), a) 2 k)) PlC (fai).) a) 2 ki)+ P(Oc(a,)zzaOO3 O A Cateaaaaaaaaaa ((4). 2 k)) x P( P( ((-C,"(()))))) 2 k)) From our assumptions, we have P(Oc(s.))2(/E,, A Caabr ((a)) 2 k)) = Po(..a)2k
((Csha((a)aa) > k)
P(Cabu (1c;) 2 k)) + PC(..))2 * P(-Caés (fci) a) 2 k))
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 will differentiate between the classifier saying that concept present (O%,) is state from the fact that the concept is part of the state (c: E C(S)). Here we note that the learned relationship is over the actual concepts in the state rather than the observation (and thus we would need to learn it from states with true concept labels). The relationship paationship between the random variables can found in Figure (C) and (D). We will assume that the probability of the classifier returning the concept being present is given by the probabilistic confidence provided by the classifier. Of course, this still assumes the classifier's 's model of its prediction is accurate. However, since it is the only measure we have access to, will treat it as being correct. Now updated model for calculating the confidence. For the precondition estimation, we can update the posterior of a concept being a precondition given a negative observation (O",,) using the formula
use this
P(c, p0 oy A OG A Octore)) P(O2,, lc $ Pa O% Octore;) P(c: & Pal0a Ocaone) P(O Og Octo)ee)
Where P(c, & Pal pal0 as follows
P(c: & pa) and we can expand P(O-o, Ia & PaA0
P(0-u,la & pa 0% Ocoo))=
P(O -, E C(s)) P(C, E C(s)la & po A 02 A Ocaire)
P(O - la $ C(s)) P(c. & C(s)lc & Pa A O% Oco(re))
16

---

Published as a conference paper at ICLR 2022
Where defined earlier P(c, & C(s)le; & Pa O A Oc(a)te)) and P(c C(s][C;
Po A O A (c()) would get expanded to the learned relationship between the concepts and their corresponding observation model. The denominator also needs to be marginalized over & C(s).
Similarly for posterior calculation for positive observations, we have
P(O le Po A A Octore) ae C(s)) * P(e e C(s)lc: pa A O2 A Octo)e+
l( & C(s)) * P(a & C(s)le, $ pa A O2 A Octir))
Now for the cost, we can similarly incorporate the observation model as follows.
P(Oc().))2k Oz ( (fa),a) ((C. 21)
([C,"(((())) 2 k A Oc(an))=k)) =
P(Oc(..224...)
(P(Oc(s.a)2a 0g E C(s), (fci), a) 2 k)* P(a: E C(s))+
P(Octna)se: O2 la @ C(s), Ca
(a ((a)).) k) P(a @ C(s))) * P(C (fa)a) k)
P(Octe.a)2x: O2,)
Given their parents, (c(r,))kk and Oz, conditionally independent, and given its parent O2, is ((c)), Cabe((())
independent of Cabe
k), there by giving
(P(Octs.a)zala E C(s), (fcs), ((cx)), 2 k) P( E C(s) P(a E C(s))+ P(Octe.)zaala & C(s), C. (fctha) 2 k) le & C(s)) * P(a. & C(s))) P(C (1ct P(Octs.)22a O%,)
((c a) 2 k)
Now P(Oc(s.)zzll: E C( (1c)), a) 2 k) 1 and P(Oc(e.a)2ale & C(s), ({c)))a))))) >
k) can either be empirically estimated from true labels or we can make the assumption that equal to PC(.a)2k (which we made use of in our experiments), which would take us to
(P(O2,le E C(s) E C(s))+ Po(..)22 le & C(s)) P(a. & C(s))) + P(C." a) P(Oc(s.a)2x.05
A.6 EXPERIMENT DOMAINS
Mooo Duerr Up
Par ksk
Mows Donry
Souel Rgg.
10
Figure 8: Montezuma Foils: Left Image shows foils for level 1, (A) Move right instead of Jump Right (B) Go left over the edge instead of using ladder (C) Go left instead of jumping over the skull, Right Image shows foil for level 4, (D) Move Down instead of waiting.
For validating the soundness of the methods discussed before, we tested the approach on the open- AI gym implementation of Montezuma's Revenge Brockman et al. (2016) and variants of Sokoban Schrader (0018). 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
17

---

Published as a conference paper at ICLR 2022
Move action Push aciión
Move action Push adtion
Figure 9: Sokoban Foils: Left Image shows foils for Sokoban- note that the green cell will turn pink once the agent passes it. Right Image shows foil for Sokoban-cell.
256-byte array). We considered executing action in the simulator that leads to the agent's 's death (falling down a ledge, running into an enemy) or a non-NOOP (NOOP action is a specific agent action that is designed to leave agent's state unchanged) action that doesn't 't alter the agent position (trying to move left on a ladder) as action failures. We selected four possible foils for the game (illustrated in Figure (). three from level I and one from level 4. The base plan in level I involves the agent reaching the key. while level 4 required the agent to cross the level.
For Sokoban, we considered two variants with a single box and a single target. Both variants allow for 8 actions and a NOOP action. Four of 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 be able to move the agent if the cell is empty, i.e., it won't move if there is box or wall in that direction. The push action also moves the agent in the direction of push if there is a box in that direction, and the agent will occupy the cell previously occupied by the box (provided there are no walls to prevent the box from moving). Similar to Montezuma, we consider any action that doesn't change the agent position to be failure. The first version of Sokoban included a switch the player could turn on to push the box (we will refer to this version as vokoban-switchh and the second version (Sokoban-cells) included particular cells from which it is costlier push the box. We considered two versions Sokohan-switch, one in which turning on the switch only affected the cost of pushing the box and another one in which it 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-vvrssin,, 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-cells, the cost of all actions except pushing boxes in the pink region is one, while that of pushing boxes in the pink region 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 set of negative examples. We used around 600 positive examples (except for the concepts skull on right and skull on left in level 1, which had 563 and 546 examples, respec- tively) and twice as many negative examples for each concept. These RAM state examples were
18

---

Published as a conference paper at ICLR 2022
fed to a binary AdaBoost Classifier Freund et al. (1999) (Scikit-learn implementation Pedregosa jet al. (201I) version 0.22.1, with default parameters), with 70% of samples used as train set and the rest the test set, for each concept. Finally, we obtained 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 1 and 4000 sampling episodes for level 4. During the search, We used a threshold of 0.55 on 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 BECCOND.BLACKBOX/amngee and concepttrnnnri inside the code directory.
A.7 CONCEPT COLLECTION
For the Sokoban variants, we wanted to 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_celll sullssurey. in the directory Study_ Sitrty_ebbite__eiiee Pdf's, which is part of the supplementary collected data from six participants, four of whom were asked to
file zip. For bakkoban-switchh specify concepts for push actions and two people for move actions. For Sokoban-cella we collected data from seven participants, six of whom were asked to specify concepts for push actions, and one was asked to 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 there. For Sokoban-switch, we received 25 unique concepts, and for Sokoban-celly 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,
couldn't 'tt make sense of the concept being described
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-swiiee 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 average accuracy of the Sokoban-switch 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 TRANNER (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.
We used all the other samples negative examples. We again used
A.8 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 confidence value of 0.8604). The ones in level I 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.
19

---

Published as a conference paper at ICLR 2022
We used variant of ( where sped up the search by allowing for memoization. Specif- ically, when sampling is done for an action and a 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 cal- culated 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-ced cell. The exact observation models values used can be found in constant.py under the directory COST_BLACKBOL
and the file cost.explainer.py in the same directory contains the code for the exact search we used.
In terms of time taken to generate the sample, creating 100 samples from montezuma for the first screen (averaged across the foils) took 59.754 seconds, montezuma second screen it took 97.673 seconds (the additional time is due to the overhead of the agent being moved the new level before the start of the episode) and the Sokoban variants took 40.660 secs.
A.9
USER STUDY
With the basic explanation generation method in place, we were interested in evaluating if users would find such an explanation helpful. Specifically, the hypotheses we tested were
HI: People would prefer explanations that establish the corresponding model component over ones that directly presents the foil information (i.e. the failing action and per-step cost)
H2: cencept-basedd precondition explanations help users understand the task better than saliency map based ones.
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 a 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- ify what they believed was the completeness of the selected explanation, on a I. Likert scale from 1 to (1 being least complete and heing the most). They were also provided a free text field to provide any additional information they felt would be useful.
For precondition explanation, 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 reported 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 complete, we had an average score of 3.476 out of 5 on the Likert scale (1 being not at all complete and 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 pointed to providing more information about the model (for example, information like what actions would have been possible in the failed state).
choice. On the question of whether the explanation was
For the cost function explanation, 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 the cost condition, 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, average, completeness score of 3.214 out of 5. The average age of the participants was 24.15, 10 had Al 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.
20

---

Published as a conference paper at ICLR 2022
original State
State with Highlights
Figure 10: Saliency map based explanation shown users part of H2
For H2, as mentioned the baseline was saliency map based explanation. For generating the saliency map, we trained the RL agent using DQN with prioritized experience replay Schaul et al. 2015 P
trained for 420k epochs. The Saliency map itself generated for four states, with the agent placed on the four sides of the box. The saliency map itself was generated using Greydanus al. (2018). where we used only the procedure for generating the map for the critic network Figure 10 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 take a quiz matching new states to those concepts, before moving on to play the game. Out of the 60 responses we considered, 16 identified as female and 41 identified as men. 23 of the participants reported they had some previous knowledge of AI, but only three participant reported having any planning knowledge. The participants who got concept based explanations took 43.78 + 12.59 secs (95% percentile confidence) and 35.87 + 9.69 steps on average to complete the game. On the otherhand participants of the other group took 134.24 + 61.72 secs and 52.64 + 11.11 steps on average.
The agent
PDF files showing the screenshots of the user study website for scenario for the precondition planation test and one from cost explanation can be found in www.ssudd-yppcdittiiooo study-cost.pdF in the directory Study Website Pdfs. The actual data collected from the user studies and the concept survey can be found in the directory USER_STUDY FEEDBACK. But below, we have included some screenshots of the interface
and User-
A. ANALYSIS OF ASSUMPTIONS MADE FOR CONFIDENCE CALCULATIONS
In this section we present results from additional tests we ran to 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 non-precondition 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 (2) cost distribution of an action over states corresponding to concept that does not affect the cost function is identical to the overall distribution of cost for the action (which can again be empirically esti- mated). We didn't run a separate test on the independence of concepts as we saw that many of the 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 a Bernoulli distribution, whose MLE estimates were calculated by running the sampler for ten thousand episode, where we used states from the original successful/optinal plan as the initial state for the random walk (ensuring the
FFor exact agent, we followed the approach deseribed in https//chhhnttaaooa//o////////// R
thub.
ipybb
We made use of the code available at http:: thub. wtt..h..o/wweeyaaas/////// sualllll i which had GPI. licence
21

---

Published as a conference paper at ICLR 2022
Action
Concept with Max difference empty above empty_ beloow 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_ bbelow
0.0172
0,0046
empty_left
0.002
0.0009
move down
wall_left
0.0017
0.0007
move left
empty right ampty_right
0.0032
0.0009
move right
0.0045
0.0008
Figure 11: Results from seloban-switchh on the distribution of non non-precondition concepts for each
action. For each action the table reports the concept with the maximum difference between the distribution concept for that specific version, versus the overall distribution and the average dif- ference in estimates across concepts.
Domain
Action
Concept with Max difference
Max Absolute
Average Difference in Estimates
Difference in Estimates
push up
wall left helow of box
0.1132
0.0461
push down
vall_left_helow_of
0.1107
0.0473
Sokoban-Switch
push left
above_switch
0.1135
0.0461
push right
wall.efft.bloww
0.111
0.0479
push up
vox_on_right
0.0956
0,0411
push down push left
_xx_on_riht
0.1098
0.0476
Sokoban-Cell
box_on_right
0.1012
0.0486
push right
wall_on.left
0.0889
0.0433
Figure 12: Results from Sokoban-switch and Sokoban-C&s on the distribution action cost across different concepts. Here report only the cost for push actions, since only those actions result in higher cost.
distributions generated from state space local the plan of interest). For first assumption, 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 is present versus the distribution of high cost for the action.
Table 11 summarizes the results from testing the first assumption for Sokoban-switch For each ac- tion the table reports the non-p 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 we can see for the domain, the differences are pretty small and we expect the differences to further reduce once start accounting the correlation between concepts.
Table 12 presents the results for the second assumption. In the cases of Sokoban-switch. we again skipped the switch_on concept and for Sokoban-Cod skipped the concepts related to the pink cells since they are all highly correlated to central concept controlling the cost function (on
A.11 EXTENDED DISCUSSION
Collecting Concepts In most of the current text, we expect the of concepts and classifiers to be given. As such before the system is actually used in practice we would have stage where the initial set concepts are collected. Collecting all the concepts from the same user may be taxing, even if we made use of more straightforward methods to learn the classifiers. Instead, more scalable method may be to set up domain- Noomain-specifee specific databases for each task that includes the set commonly used concepts for the task. This also the strategy used by Cai al. (2019), who created medical concept database to be used along with TCAV explanations. One could also use off off-the-shelf object recognition and scene graph generation methods to identify concepts for everyday settings.
22

---

Published as a conference paper at ICLR 2022
Describing Plans: 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). For the "Why P" part the agent could start by demonstrating its plan to show why it is valid and report the total cost it may accumulate. We can further augment such traces with the various concepts that are valid at each step of the trace. We can also report cost abstraction for the cost function corresponding to each step taken as part of the plan. Here the process for finding the cost abstraction stays the same as what is described in Section 4 of the main paper.
Stochastic Domains: While most of the discussions in the paper have been focused on deter- ministic 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 differ- ence would be the estimation of the value the failure point of the foil. One way to easily adapt them to our method would be to compare against the worst case, or best case execution cost of the foil the failure point under one of the execution traces corresponding change we would need to make to the entire method is before the actual search starts. Namely, when the agent is trying to simulate the foil in its own model, rather than doing it once, it would need to simulate it multiple times and look for the worst-case or best-case trace. Another possibility is rather than looking for the worst-case execution trace, would be consider the most likely traces and perform the same process but now over a set of possible foils.
the foil. So the only
Partial Observability and Non-Markovian Concepts: The paper focuses cases where the mapping is from each state to concept. Though there may be cases where the concept the user is interested in corresponds to specific trajectory. Or there may be cases where there may be some disparity between the internal state of the agent and what the human can observe, or the problem itself is partially observable. In such cases, rather than learning concept that is completely identified by the current state, the system may need to learn mappings from state action trajectories (or observation histories) to concepts. Then the rest of the process stays the same (except the search process now needs to keep track of history). We can still use the same class of symbolic models as before because while these concepts are non-markovian with regards to the underlying model, the fact that the concept symbols are part of the symbolic model state means any action transition or cost function that depends on these concepts can be defined purely with respect to the current state,
Temporally Extended Actions: Another assumption we have made through the paper is that the action space stays the same across the symbolic and internal models. However, this may not always be true. For domains like robotics, the human may be reasoning about the actions at a higher level of abstractions than what the agent may be considering. Such actions may be modeled as temporal abstractions (for example, options Sutton et al.] (1999) defined over the agent's atomic actions. If such abstract actions are not pre-specified to the agent, it could try to learn by a process similar to how it learned concepts. Once learned, the agent can either directly simulate these temporally abstract actions to identify its preconditions (for options, a characterization of its initiation set) and cost function (the expected cost over the holding time) or from the sampled traces which correspond to the execution of these abstract actions (if the system could only learn a mapping from trajectories to action labels).
Acquiring New Concepts: In the main text, discussed how the original vocabulary set may be incomplete and how our search algorithms could identify scenarios when the concept list is in- complete and insufficient to generate the required explanation. In such cases, the system would need to gather more concepts from the user. While the system could ask the user for any previously unspecified concepts, this would just result in the user wasting time specifying potentially irrelevant concepts. One would preferably want to perform a more directed concept acquisition. One possi- bility might be to use the system's 's internal model to provide hints to the user as to what concepts may be useful. For example, the system could generate low-level explanations like saliency maps to highlight the parts of the state that may be important and ask for concepts that are relevant to those states. Once the new concepts are collected, we can again make use of our current approach to see if any of the concepts could be used to build a satisfactory explanation. One could also wrap the entire interaction into meta- sequentall decision-making framework, where the framework cap- tures the repeated interaction between the user and the system. The actions that are available to the meta maker would include the ability query the user for more concepts and the objec-
23

---

Published as a conference paper at ICLR 2022
Seere and Potas
Puch
Srlas
Keys execure action::
ACOR
Pain Pen -2
Figure 13: Screenshot from the survey done to collect sokoban concepts.
tive would be to reduce the overall burden placed on the user. While one could follow the basic interaction pattern laid out in this paper, namely, querying the user only when the current set of concepts proves to be insufficient, the use of such a reasoning framework would allow the system to pre-emptively collect concepts from the user that may be useful for future interactions.
Confidence Threshold Our system currently expects to be provided a confidence threshold that decides the minimum confidence that must be satisfied by any explanation provided to the user. Such threshold may be provided by the stakeholders of the domain/system or the user. One could also determine when to provide explanations based on decision-theoretic principles. Since the con- fidence values are just probabilities, if the system has access to penalty values attached to getting an explanation wrong, then it can associate an expected value to an explanation (since after all the confidence is just the probability of the fact being true) and use it drive its decisions. This penalty value could be associated with both the user potentially making a mistake because of incorrect infor- mation but also could be related to loss of trust from the system providing an incorrect explanation. One could also use our explanatory methods along with the explanatory confidence in the context of trust-aware decision pocision-making systems like Zahedi al. (2021).
Ethical Implications The use of confidence values makes sure that the system is not giving ex- planations to humans that it doesn't It have high confidence in, thereby sidestepping many of the core issues related to post hoc explanations. One of the assumptions we have made in the main paper that allows us to do this is that the agent can correctly reason over its internal model. So we can learn an equivalent representation for this internal model, then one could guarantee that the explanations are sound, in so far that the agent would only generate behaviors that align with the stated model components. However, this assumption may not always hold and the agent could generate behavior that may not conform to its internal models. Unfortunately. in such cases, we would need additional mechanisms test whether the agent conforms the identified model component. Otherwise, the explanation could lead to the human assigning undeserved trust to the agent. One scenario where the soundness of the agent's reasoning process doesn't matter are cases where the mechanism described in the paper is being used purely as a way to generate preference accounts Langley (2019), i.e., the system purely trying to explain why one decision may better than other terms of its model of the task, regardless of how the agent generated the original decision. Such explanations could be helpful in cases where the agent and the user are collaborating to generate better solutions.
A.12 STUDY INTERFACE SCREENSHOTS
24

---

Published as a conference paper at ICLR 2022
Plan and the alternate plan
Click ongyhhree view
Altemete plan eugpested by the user: Folow the plans you
red as shown image moveritt Onaledd jumplirti than folow
Lopar
(A)
Explanation for why the alternate would fail
shown image then move loft (intead of jump and thon fallow nost of the plan.
Pleaso select explanation that find most usefut
the revolet
"haal Than Heroe, actinn micee
(B)
Figure 14: Screenshot from the study interface for H1 for precondition.
25

---

Published as a conference paper at ICLR 2022
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 IION corry?
(A)
Explanation for why the alternate plan more costly
Albematt Plan Steps-
eugpected
puching pink
skerd
and then proceed to the target
you
Ohu vow
Sep jusn of actonn cook
Ste--
Dep-h
(aep Vive csan
LG
dayp sua adion cana
altorat
adion
hepporing
Eancutng acien whan
The cosl at load
heppoiig
IG
Youv oalon happens
frow actis cosa best This happens
(B)
Figure 15: Screenshot from the study interface for for function explanations.
26

---

Published as a conference paper at ICLR 2022
Information
garme
Ressat Gurre
Time Remaining:
Possible Explanations:
2m 44s
possibie
You can only push 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
Oeghlighted
sould
original
State
Highlights
Keys execute actions:
Move []]
dwn
ops [g]
8
(B)
Figure 16: Screenshot from the study interface for H2.
27


Reviews:
[{"review_id": "fgMUVE592R8", "reviewer": "Reviewer_mLyQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Explainability is a highly relevant field within machine learning as more and more models find applications in critical areas. While there’s been substantial amount of investigation into explainability for classification models, generalization to other frameworks remains lacking. This paper does a good job of formalizing what kind of explanations might make sense for sequential decision-making problems, and it is easy to read and follow. The development is systematic, and the kind of explanations proposed appear sensible to me as an end-user. There is also extensive background and supplementary material provided in the appendix to support and reinforce the ideas. I think this is a promising albeit quite preliminary work in an ill-explored area.\n\nMy main concern is the limited nature of the evaluation section. It appears that the assertions are largely substantiated via a handful of examples and it’s unclear to me how these ideas might generalize. Needing to handcraft classifiers, learning preconditions for feasibility of actions via sampling, assuming certain variables to be independent (e.g. non-precondition concepts), imposing a loose generative model on the process, all appear somewhat fragile. While the appendix touches upon some of these weaknesses, it’s not entirely convincing without more exhaustive evaluation. Relatedly, the results of the human study with the subjects preferring concept-level explanations over saliency-based ones are appreciated but unsurprising. I wonder how the proposed method will compare against another parsimonious account of relevant concepts (e.g. skulls kill, falling off the edge kills, can’t go through crabs).", "summary_of_the_paper": "In this paper, the authors present a method for justifying an agent’s policy in a sequential decision-making task when the human proposes specific counterfactuals. The authors first represent the state of the system with a set of intuitive classifiers, and then explain why a counterfactual (termed foil), would fail or cost more than the agent’s policy based on this classifier representation. For example, identifying that “move left” leads to a failure state in a game when the current state has the classifier “platform_edge_on_left” = True, as one its descriptors. Similar ideas extend to identifying an overly costly foil policy. The authors develop how such state characterization can be constructed, how feasibility of actions can be learned from sampling, and how a simple Bayesian formalism can be used to quantify uncertainty arising from sampling and other assumptions. They go on to show how the proposed idea works for two game settings, as well as how these explanations are preferred by human subjects over saliency based ones.", "summary_of_the_review": "Overall, I think this is a good paper with the potential to spark more work in the area. However, the evaluation section can be made stronger to really convince the reader of the merit of the method. In its current draft, I am somewhat inclined for the paper to be accepted. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TMcb-zm7TrT", "reviewer": "Reviewer_wvCE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Explanation is contrastive [1] -- because in order to answer the question to why agent does X, there can be many different reasons, and only by contrast, we can truly perform causal selection (selecting the causes that explain the difference). \n\nStrengths:\n1. The paper is very well-written, but Section 3 and the algorithm can be a bit unclear to people unfamiliar with symbolic logic.\n2. I really like Section 5, where the confidence of explanation is quantified through a concept classifier, and it can additionally be incorporated into the search algorithm.\n\nWeakness:\n1. The need for a foil agent seems like a very big impediment of allowing the methodology proposed in this paper to have real-life application/impact. Collecting concepts from user seems very doable, but soliciting foil actions/agent from users is non-trivial. This is not a strong criticism on the paper, because the authors can suggest that the real explanation people need from an agent is: \"Why do you do X instead of Y?\"  -- this format of question is exactly what this paper captures.\n2. I really don't think game is the best domain -- because rarely would people want a game agent to justify its action when playing a game. RL policy is used in many other domains such as recommendation systems, healthcare, education -- in there, action space is more limited, and the need for policy to justify itself does exist. I wonder if the authors can comment on that and work through a concrete example, say in healthcare (ICU) + RL setting, what kind of concepts might be used in there, what could be the performance of the concept classifier, what does a foil action/agent look like, and whether the paper's method can provide satisfying explanations in a setting like [2] (no need to run actual experiment, a response with some worked out examples would be great!)\n3. In Section 2, the authors said \"We will focus on models where the preconditions are represented as a conjunction of propositions.\" -- this is never justified or explained. I can only assume there is some justification on why conjunction of propositions can perfectly represent pre-conditions. And why are pre-conditions ideal explanation candidates? This might seem very obvious to the authors -- but stating the justification can be important for future work to either expand on authors' idea.\n\nOverall, I think this paper contributes nice ideas to the field of XAI in RL. I wish the domain is not game -- but clearly, game is the easiest domain to focus on, and concepts can be easily acquired. I have some concerns on the real-world applicability of the methodology. However, the paper is well-written, and the information presented is a nice contribution to the discussion of XAI. I'm happy to raise my score if the authors address my concern.\n\n[1] Hesslow, Germund. \"The problem of causal selection.\" Contemporary science and natural explanation: Commonsense conceptions of causality (1988): 11-32.\n[2] Komorowski, Matthieu, et al. \"The artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care.\" Nature medicine 24.11 (2018): 1716-1720.", "summary_of_the_paper": "The paper presents a search procedure with concept classifiers to generate symbolic explanations (in terms of preconditions and costs) to justify an agent's action w.r.t. a foil agent. The authors conducted user study to show the usefulness of their method.", "summary_of_the_review": "The paper is well-written and the methodology is novel. However, XAI is most needed in critical domains like recommendation systems, healthcare, and education. Would be good to see some discussion in these areas.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "THWwbFqcRl5", "reviewer": "Reviewer_ike6", "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": "Strength:\n- AI interpretability is important; \n- detailed appendix \n\nWeakness: \nsignificant presentation issues; \nrelated work discussion; \nmodel evaluation; \nuser study is not appropriate;  \n\nDetailed comments:\n\n1. \nI agree that AI interpretability is an important subject -- but unfortunately the poor presentation clarity in this paper makes it hard to assess the soundness of the claims.\nOverall -- the text needs editing, there are no paragraph breaks, microscopic figure labels, and the discussion of related work is either scattered through the text or crammed in the end, instead of given in the introduction.\n\n- Consider this 5-line-long sentence:\n\"As part of developing this system, we will also formalize the notion of local symbolic approximation for\nsequential decision-making models, and introduce the notion of explanatory confidence (Section 5)\nthat captures the fidelity of explanations and help ensure the system only provides explanation whose\nconfidence is above a given threshold.\"\n\n- Labels in Figure 5 require 300% zoom to see, and can not be read in print at all.\n\n- The sentence \"We had the smallest explanation likelihood for foil1 in screen 1 in Montezuma (with 0.511   0.001), since it used a very common concept, and their presence in the executable states was not strong evidence for them being a precondition.\"\nTheir presence sounds like several concepts, the sentence refers to one concept, and it is unclear which one?\nThe authors do a good job motivating the paper in the opening paragraph, and Figure 1, but unfortunately do not sustain this momentum through the remainder of the paper. \n\n2. A comprehensive discussion of related work is missing, or scattered through the text, which makes it difficult to evaluate the novelty, contributions, and technical motivation of the current work.\n\n3. The number of concept classifiers is reasonable, and the method of soliciting concepts through surveys is good, however computational model evaluation is not sufficient. \nEvaluation of Montezuma's revenge used only 4 foils, evaluation of Sokoban uses only one foil. \nOne reasonable way to obtain such foils would be to obtain them from humans trying to play the game. The authors do use a study of users playing Sokoban to evaluate the effectiveness of explanations, so why not use the foils generated by users through play to evaluate the model as well.\n\n4. The user study measures \n -- Experiment 1-- whether people prefer explanations that refer to the symbolic model components over more concise explanation\n -- Experiment 2-- whether the proposed explanations help people get a better understanding of the task, compared to a non-verbal highlighting of problem areas by a saliency map.\n\nStudy result reporting is unusual, it was very hard to understand what was actually done in the studies.\nThe authors report that 100 users participated in the study.\nFurther, Experiment 1 collected collected 5 responses per each of the 4 Montezuma foils, and 10 responses for each of the 2 sokoban foils, this means 50 responses, ...but the study is said to be within-subjects. Does this mean that each subject gave 50 responses, and responded multiple times to the same files?  However, Table 1 reports X out of 20 subjects in each condition - indicating that each subject responded to just one foil, and that there were 50 subjects in total.\nAfter some reflection, I realized that 100 users participated in both Experiment 1 and Experiment 2.\n\nRegarding Experiment 1, I am not convinced that this study appropriately evaluates the system.\nThe authors misunderstand the preference for concise explanations. The point of this preference is that people look for (1) simplest explanation to make sense of their observations (Occams razor), and (2) explanations that are pragmatic -- communicate more content with fewer words (e.g. Grieces maxims). Neither of those principles assumes that the communicator should sacrifice grammar, important causal information, or linguistic intelligibility, in order to say less.\nThe authors reduce this to an incorrect assumption that people should prefer to see less text. \nFor example, consider human players discussing two alternative plans. Player A proposes a plan that results in loss. Player B can decline by saying \"death\" or by saying \"if we do this, we will loose because..\" -- both explanations are technically correct, but one of them omits casual information. Player A could also say \"death fall\" - which presumably includes causal information, but is given in a less intelligible form.\nThe value of concise explanations is to reduce the listener's cost (processing the answer) while maximizing reward (relevant information). Each experiment needs to clearly state what the subjects did.\n\nRegarding Experiment 2, the method of having human players play the task and measuring the number of steps they take is a good one, but the presented analysis has several issues.\n\n - \"we collected 60 responses but had to discard 12 due to them missing to self-report that they looked at the explanation.\"\nThis implies that 12 subjects did not find the explanation useful, not that they should be discarded. Human players may prefer to \"figure out\" a game by active learning -- posing and testing their own hypotheses about how the game works, instead of reading about it -- this is a common human behavior, and should not be considered invalid.\n\n- Is the saliency map explanation system known to actually known to be effective in the given Sokoban task variant? The illustration in Figure 10 implies that it is not really helpful, with a large area of the map being highlighted at the same time.\nIt would be good to see how many steps do people take in a \"no explanation\" condition. Further, this information needs to be presented with 95% confidence intervals, and would be more readable if presented as a bar plot rather than a table. \n\n- Were the Sokoban study subjects given task instructions? \n\n\n", "summary_of_the_paper": "This paper proposes a symbolic model implemented alongside a planning AI, which can respond to human  queries about why one plan is taken by the AI, and not another.  The system takes as input a user concept vocabulary, where each concept is implemented by binary classifier indicating whether the proposition is present. This concept vocabulary needs to be initially solicited from the user -- either through user surveys or designed by researchers. \nThe output of the classifiers is noisy, which is interpreted as confidence over the proposed explanation. The system then uses a symbolic PPDL model with the concept vocabulary to answer queries. The system can issue two types of answers about why a proposed plan is inadmissible: (1) a pre-condition for a given action is missing or (2) the proposed plan is more costly than the chosen plan.\n\nTo identify if a concept is a precondition for action A, the system samples a number of states from the model where A is executable. If concept is always present, then it is a pre-condition. Samples are generated by a random walk from one of the states in the model's given plan. In the evaluated problems games the sampling algorithm needs ~500 samples to accurately identify the missing pre-condition.\nTo identify the cost associated with executing a proposed action, a heuristic is used, such that tries to sample the minimal cost when executing the action given the preconditions. (This is not clearly explained ) \n\nA small user study was used to evaluate whether the subjects find the proposed explanations helpful.\n", "summary_of_the_review": "I am not convinced that this paper is ready for publication in ICRL. There are many good things to this paper -- such as a beautiful motivating example on the first page, and a detailed technical appendix -- but it still needs more work to be of interest to the broader ICRL community. The paper has significant presentation issues, which make it hard to evaluate the soundness of the claims, theoretical significance and novelty. \nThe described model evaluation, and user study, are insufficient to support the claims. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "2Jhl4eSu3c", "reviewer": "Reviewer_C3CZ", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "# Thank you\n\nThank you for your comments and changes. I have a suggestion:\nPlease add a short paragraph discussing what would happen if the users only mention part of the crucial concepts.\nThis is related to a transversal challenge on the method applicability being sensitive to the concepts that the users provide.\n\nI also find it interesting to consider the other extreme: what if the user were providing the perfect set of concepts.\nWhat would be happening in that cases? It seems the algorithm would be dealing with some form of model-based seq decision making.\n\n# Older main review\nThe paper emphasizes that the method is not trying to learn a full symbolic representation for the problem. Besides, given the intrinsic difficulty of explanations of sequences, the method should aim to high precision. I keep in mind that there are no solid alternatives for this setting.\n\nA potential weakness is the requirement of the concepts. I wonder what the alternatives are. All explainability setting convey their meaning in some way. In this case, the concepts are on the side of the users of the method. In this case, user experiences designers have tools that they can exploit in multiple ways. It should be possible to use abstract concepts that correspond to user interface elements, as far as they can be visualized later. The proposed method is orthogonal to that. Providing concepts is a relatively cheap label for sequential decision-making. Compare that with the complexity of labelling videos. Besides, vocabulary seems a minimal form of communication.\n\nThe general idea is both interesting and simple for those familiar with STRIPS planning. The appendix considers more detailed technical scenarios. However, a main important issue is explained in the body of the paper: the observations of concepts it bound to be noisy. The graphical model –explained in detail in the appendix– allows to provide probability estimates to guide the selection of explanations. The estimation using the graphics model is similar to some inferences on hidden Markov models. That's not casual since we are talking about sequences of actions and hidden variables.\n\nI am pretty satisfied with this revision of the paper, so I don't have many questions or comments. See some below.\n\n\npage 2: *We will denote the state formed by executing action a in a state s as a(s). We will focus on models where the preconditions are represented as a conjunction of propositions.*\nWhat about the action effects? What do they do?\n \npage 4: *Figure 2: Algorithms for identifying (a) missing precondition and (b) cost function*\nI understand what the algorithms do. However, the figure could be more clear. For instance, what's poss_prec_set?\n\npage 5: *The worst-case time complexity of this search is linear on the sampling budget*.\nWould you please comment more clearly about the cost/resources of producing explanations? Both in preparation and for a particular instance.\n\n", "summary_of_the_paper": "(NB: I reviewed a previous version of this paper. I was in favour of its acceptance. In my opinion, this version is far more clear and addresses the most salient concerns of the reviewers, including me. I'll keep this review self-contained and refer to this submission).\n\nThe paper proposes a methodology for providing post-hoc explanations in sequential decision settings without assuming a model of the environment. Usual methods for explainability do not translate well into sequential decision settings, as the explanation is related to the executed actions. In particular, what's the natural form for such explanations? A simple but useful query is to ask about modifications to the plan retuned by the AI agent. These are called constrastive explanations. Those modifications could be a) better, b) lead use some illegal action execution, c) be more expensive.\n\nThe method creates a symbolic approximation around the current situation. The approximation allows to show the user a single concept that is missing and makes an action fail, or to increase the cost. The validation with users reports that they are finding them usefull. A more indirect test, less sensitive to the bias of self-report, is whether they can solve a task faster. Those results are also positive.  ", "summary_of_the_review": "In summary, I recommend the acceptance of the paper. The idea is very simple and can be combined with efforts both on explainability and neurosymbolic methods that offer trust to the users.\n\nThe paper presents a strong combination of minimal information used to ground the explanations with learning and reasoning methods to provide adaptation and coherence. The use of planning allows to produce small explanations in the most critical parts.\n\nIf anything, the weakest point is that the notion of locality might be hard to control. In some cases, the reason for an action not being possible might be further away. Another round of interaction with the users might allow to discover for what concepts it might be useful to look further. For instance, a video game might feature a switch that should be open to achieve some effect. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives a method for generating contrastive explanations, in terms of user-specified concepts, for an agent in a sequential decision making setting. 

The reviewers found the paper to be a strong contribution to explainable AI and RL. There were some concerns about the writing, but the revisions have addressed most of these. 

Overall, I am delighted to recommend acceptance. I urge the authors to incorporate the feedback in the reviews in the final version.
Decision: Accept (Poster)