# Causal Explanations for Sequential Decision Making
Under Uncertainty

Samer B. Nashed  University of Massachusetts Amherst<EMAIL_ADDRESS>,
Saaduddin Mahmud  University of Massachusetts Amherst<EMAIL_ADDRESS>,
Claudia V. Goldman  General Motors Research<EMAIL_ADDRESS>and  Shlomo
Zilberstein  University of Massachusetts Amherst<EMAIL_ADDRESS>
###### Abstract.

We introduce a novel framework for causal explanations of stochastic,
sequential decision-making systems built on the well-studied structural causal
model paradigm for causal reasoning. This single framework can identify
multiple, semantically distinct explanations for agent actions — something not
previously possible. In this paper, we establish exact methods and several
approximation techniques for causal inference on Markov decision processes
using this framework, followed by results on the applicability of the exact
methods and some run time bounds. We discuss several scenarios that illustrate
the framework’s flexibility and the results of experiments with human subjects
that confirm the benefits of this approach.

##  1\. Introduction

As autonomous decision making becomes ubiquitous, researchers agree that
developing trust is required for adoption and proficient use of AI systems
(Linegang et al., 2006; Stubbs et al., 2007; Zhang et al., 2020), and it is
widely accepted that autonomous agents that can explain their decisions help
promote trust (Chen et al., 2018; Hayes and Shah, 2017; Mercado et al., 2016).
However, there are many challenges in generating such explanations. Consider,
for example, an autonomous vehicle (AV) stopping behind a truck for a long
duration. The passenger may wonder whether the AV is waiting for the truck to
move, waiting for an opportunity to pass the truck, or dealing with some
technical problem. Generating suitable explanations of such a system is hard
due to the complexity of planning, which may involve large state spaces,
stochastic actions, imperfect observations, and complicated objectives.
Furthermore, useful explanations must somehow reduce the internal reasoning
process to a form understandable by a user who likely does not know all of the
algorithmic details.

Another challenging aspect is the heterogeneity of possible operational
contexts and interaction with different types of users with different
expectations. For example, in the above AV scenario, the explanation furnished
to a passenger may differ from that given a driver evaluating whether or not
to intervene and take control of the vehicle. Moreover, different planning,
learning, and decision-making algorithms may not afford universal mechanisms
for explanation due to fundamental differences in available information.

Debate on the definition, taxonomy, and purpose of explanations has been well-
represented in the cognitive science, psychology, and philosophy literature
for a long time. While still active, there are several insights for which
there is broad consensus (Miller, 2019; Mittelstadt et al., 2019), and we use
this knowledge to motivate our approach. Scholars studying explanations mostly
agree that requests for explanations are often motivated by a mismatch between
the mental model of the requester and a logical conclusion based on
observation (Heider, 1958; Hesslow, 1988; Hilton and Slugoski, 1986; Hilton,
1996; Lombrozo, 2006; Williams et al., 2013), which creates a form of
generalized model reconciliation problem (Chakraborti et al., 2017).
Researchers also agree that explanations often require counterfactual analysis
(Mackie, 1980; Lipton, 1990; Hilton, 1990; Lombrozo, 2012), which in turn
requires causal determination (Woodward, 2005; Salmon, 2006; Lombrozo, 2010).
There are several computational paradigms for causal analysis, including those
based on conditional logic (Lewis, 1974; Giordano and Schwind, 2004), and
statistics (Freedman, 2007). Among the most well-studied paradigms is the
_structural causal model_ (SCM) (Halpern and Pearl, 2005a).

The primary contribution of this paper is a framework, based on SCMs, for
applying causal analysis to sequential decision-making agents. We create an
SCM representing the computation needed to derive a policy for a Markov
decision process (MDP) and apply causal inference to identify variables that
cause certain agent behavior. These variables can then be used to generate
explanations, for example by completing natural language templates. This
framework provides two main benefits. First, it is theoretically sound, based
on concepts and formalisms from the causality literature, while most existing
approaches use heuristics. Second, it is more flexible, allowing us to
identify multiple types of explanans, whereas existing approaches often
explain events in terms of a single set of variables in the decision-making
model. For example, they may use _only_ state factors or _only_ reward
variables, whereas we may use any set, increasing our framework’s
applicability. Furthermore, we offer several approximate techniques for large
problems or problems where the topology of the causal graph prevents exact
inference.

Theoretically, we determine the domain of problems for which this method is
exact and provide some worst-case run time bounds for the algorithms
presented. Empirically, we discuss several qualitative scenarios that
illustrate how our approach not only produces sensible causes of agent
behavior, but also uses a single framework to identify causal variables from a
variety of MDP components. This case study is presented along with results
from a user study in which users compare the proposed method to existing,
heuristic methods and we find statistically significant preferences in favor
of explanations generated via causal reasoning.

##  2\. Related Work

Automatically generating explanations is a growing field of AI research. One
focus area aims to explain the decisions of black-box machine learning
algorithms (Mothilal et al., 2020; Lucic et al., 2020; Karimi et al., 2021).
These works often use the terms explainable or interpretable machine learning
(XML). Another focus area, more aligned with this work, aims to explain the
outputs of planning algorithms, or modify planning algorithms so that they
produce plans that are inherently more explainable. These works typically use
the term explainable planning (XAIP). A large portion of XAIP research has
been devoted to deterministic planners, or analyzing plans after they have
been executed (Fox et al., 2017; Chakraborti et al., 2019, 2020). However,
many applications operate in stochastic domains or require explanations in
real time.

Research on explanations of stochastic planners, such as MDPs, is relatively
sparse, but there are several notable existing efforts. Elizalde et al.
((2009)) identify important state factors by looking at how the value function
would change were they to perturb that state factor’s value, and Khan et al.
((2009)) present a technique to explain policies for factored MDPs by
analyzing the expected occupancy frequency of states with extreme reward
values. Similarly, Juozapaitis et al. ((2019)) analyze how extreme reward
values impact action selection in decomposed-reward RL agents, and Bertram and
Peng ((2018)) look at reward sources in deterministic MDPs. Wang et al.
((2016)) try to explain policies of partially observable MDPs by communicating
the relative likelihoods of different events or levels of belief. However,
research clearly indicates that humans are not good at using this kind of
numerical information (Miller, 2019).

While these approaches have limited scope in the explanations they provide,
they are also computationally cheap and easy to implement. More complex
methods have been developed that attempt explanation via summarization. Pouget
et al. ((2020)) identify key state-action pairs via spectrum-based fault
localization, and Russell et al. ((2019)) use decision trees to approximate a
given policy and analyze the decision nodes to determine which state factors
are most influential for immediate reward. Panigutti et al. ((2020)) used
similar methods to explain classifiers.

Recently, the use of structural causal models for explaining MDPs has been
proposed by Madumal et al. ((2020)), who used SCMs to encode the influence of
particular actions available to the agent. This approach was used in a model-
free, reinforcement learning setting to learn the structural equations as
multivariate regression models during training. However, it requires several
strong assumptions including the prior availability of a graph representing
causal direction between variables, discrete actions, and the existence of
sink states. In contrast, our proposed framework allows causal analysis of all
the components of MDPs using a single set of algorithms. Moreover, it is
theoretically well-justified as it rests on a concrete theory of causality and
can be easily extended for cases where approximate reasoning is required,
including model-free planners.

##  3\. Background

Here, we provide an overview of concepts and notation for structural causal
models and Markov decision processes.

###  3.1. Structural Causal Models

Structural causal models (SCMs) (Halpern and Pearl, 2005a, b) are defined as
tuple $\mathcal{S}=\langle\mathcal{U},\mathcal{V},\mathcal{M}\rangle$,
describing a causal reasoning problem. The set $\mathcal{U}$, called the
_context_ , is a set of exogenous variables that describe some condition of
the world. These variables, while possibly causally relevant, are assumed to
be fixed for a given analysis. The set $\mathcal{V}$ is a set of endogenous
variables considered possible causes of some event. In our case, these
variables are internal to the reasoning process of the agent. All variables in
the world are either elements of $\mathcal{U}$ or elements of $\mathcal{V}$,
and $\mathcal{U}\cap\mathcal{V}=\emptyset$. The final component,
$\mathcal{M}$, is a set of equations that specify the causal effects of
variables in $\mathcal{U}$ and $\mathcal{V}$ on other variables in
$\mathcal{V}$. The decision of which variables to put into each set is a
design choice that we revisit later.

A causal graph is a DAG where nodes are variables and edges denote cause-
effect relations. A _layered_ causal graph (Fig. 1) is defined given an event
$\phi$, for which we want to determine causes, and a set of variables
$X\subseteq\mathcal{V}$, which we would like to evaluate as causal or not. A
layered causal graph (LCG) is a DAG whose nodes are partitioned into non-
intersecting layers $(S^{k},\ldots,S^{0})$, where for every edge $A\rightarrow
B$ there exists some $i\in\\{1,\ldots,k\\}$ such that $A\in S^{i}$ and $B\in
S^{i-1}$. Further, $X\subseteq S^{k}$, and $\phi\in S^{0}$.

###  3.2. Markov Decision Processes

A _Markov decision process_ (MDP) is a model for reasoning in fully
observable, stochastic environments (Bellman, 1952), defined as a tuple
$\langle S,A,T,R,d\rangle$. $S$ is a finite set of states, where $s\in S$ may
be expressed in terms of a set of _state factors_ , $\langle
f_{1},f_{2},\dots,f_{N}\rangle$, such that $s$ indexes a unique assignment of
values to the factors $f$; $A$ is a finite set of actions; $T:S\times A\times
S\rightarrow[0,1]$ represents the probability of reaching a state
$s^{\prime}\in S$ after performing an action $a\in A$ in a state $s\in S$;
$R:S\times A\times S\rightarrow\mathbb{R}$ represents the expected immediate
reward of reaching a state $s^{\prime}\in S$ after performing an action $a\in
A$ in a state $s\in S$; and $d:S\rightarrow[0,1]$ represents the probability
of starting in a state $s\in S$. A solution to an MDP is a policy
$\pi:S\rightarrow A$ indicating that an action $\pi(s)\in A$ should be
performed in a state $s\in S$. A policy $\pi$ induces a value function
$V^{\pi}:S\rightarrow\mathbb{R}$ representing the expected discounted
cumulative reward $V^{\pi}(s)\in\mathbb{R}$ for each state $s\in S$ given a
discount factor $0\leq\gamma<1$. An optimal policy $\pi^{*}$ maximizes the
expected discounted cumulative reward for every state $s\in S$ by satisfying
the Bellman optimality equation $V^{*}(s)=\max_{a\in A}\sum_{s^{\prime}\in
S}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\gamma V^{*}(s^{\prime})]$.

Figure 1. A layered causal graph.

##  4\. Structural Causal Models for MDPs

At a high level, we construct a causal model of the computation that solves
for the policy of an MDP and then use this model to determine causes for agent
actions, which can later be used for explanation. In the general case, this
process follows four steps. (1) A causal graph is generated from the relevant
MDP components. (2) The resulting graph is converted into a layered causal
graph. (3) The layered graph is pruned to remove any irrelevant nodes and
edges, given $X$ and $\phi$. (4) A recursive algorithm identifies sets of
causal variables in the pruned graph. This approach provides a principled,
general framework for causal inference on MDPs while simultaneously supporting
several types of explanations.

In our layered graphical representation of MDPs we call layer $S^{0}$ the
policy layer. This layer contains Boolean variables of the form
$\pi_{sa}=[\pi(s)=a]$ that collectively represent the policy of the MDP. Thus,
$S^{0}$ has $|S||A|$ variables, one for each state-action combination.
Depending on the definition of $\mathcal{V}$, layers $S^{1}$-$S^{k}$ represent
different parts of the MDP. In all definitions for $\mathcal{V}$ below we can
derive the agent’s action for some state $s$, given the layered causal graph
for its MDP and the values of all nodes without incoming edges, by passing
values along edges and computing variables in subsequent layers of the graph
until we reach layer $S^{0}$. We will first detail this process in layered
MDPs (§4) and then discuss general MDPs and approximate methods (§5).

###  4.1. Causal Models for Layered MDPs

We begin with the special case of layered MDPs, which contain both tree-
structured MDPs and finite-horizon MDPs, and for which our methods are exact
(up to discretization). Although it is possible to create a single, monolithic
causal graph that simultaneously represents all components of the MDP tuple,
this is not helpful since it does not afford any additional types of
inference, is much less computationally efficient, and requires substantial
bookkeeping to maintain the layered property. Thus, we analyze two causal
models that, together, can answer causal queries about all parts of MDPs
considered in previous literature.

###### Definition 0.

A _layered Markov decision process_ is an MDP where, for all states $s\in S$,
the successor graph of depth $h$ representing state $s$ is a layered graph
$\forall h\in\mathbb{N}$.

##### State Factors

The first model is for queries about the causality of state factors. Here, we
let $\mathcal{U}=\emptyset$, and

$\mathcal{V}=\pi_{sa}\cup s\cup f_{i}\hskip 14.22636pt\forall s\in S,\forall
a\in A,\forall i\in\\{1,\ldots,n\\}$

where $f_{i}$ denotes the $i$th state factor. Finally, $\mathcal{M}$ is
composed of the following three sets.

$\mathcal{M}_{F}:=f_{i}=f_{i}^{t},\hskip 14.22636pt\forall
i\in\\{1,\ldots,n\\}.$

Here $f_{i}^{t}$ is the value of state factor $i$ at time $t$. A given set of
state factors $\langle f_{1},\ldots,f_{n}\rangle\in f$ determines the state
$s\in S$.

$\mathcal{M}_{S}:=[s=s_{i}]=[f_{1}=f_{1}^{i}]\wedge\ldots\wedge[f_{n}=f_{n}^{i}],\hskip
14.22636pt\forall s\in S.$

Last, we have equations representing action selection.

$\mathcal{M}_{A}:=[\pi(s)=a]=\pi_{sa}\wedge s\hskip 14.22636pt\forall s\in
S,a\in A.$

Thus we define
$~{}\displaystyle{\mathcal{M}:=\mathcal{M}_{F}\cup\mathcal{M}_{S}\cup\mathcal{M}_{A}}$.

Figure 2. A layered causal graph generated from an MDP representing the
influence of state factors on the action.

Fig. 2 shows the causal graph represented by this SCM. In general, this
definition of SCMs for state factors creates layered graphs with exactly three
layers, and when the state space is discrete, permit exact inference
regardless of the underlying MDP topology. Importantly, this graph represents
a _fixed_ policy. While we _cannot_ change state factors to produce a
different policy, we _can_ understand how state factors affect action
selection for a given policy.

##### Rewards, Transitions, and Values

The second causal model we present is used to analyze how reward, transition,
and value functions causally influence action selection. Here, we let
$\mathcal{U}=\\{\gamma\\}$ since it is essential for computing the effect of
other variables in the system, but we are unlikely to consider this a direct
cause of any behavior we want to explain. Further, we let
$\mathcal{V}=T(s,a,s^{\prime})\cup R(s,a,s^{\prime})\cup
V(s)\cup\pi_{sa}~{}~{}~{}\forall s,a,s^{\prime}$. Finally, we let
$\mathcal{M}$ be the set of equations needed to solve for a policy, for
instance by value iteration. The first two sets do not depend on other
endogenous variables.

$\mathcal{M}_{R}:=R(s,a,s^{\prime})=R^{ss^{\prime}}_{a},\hskip
14.22636pt\forall s,s^{\prime}\in S,\forall a\in A;$
$\mathcal{M}_{T}:=T(s,a,s^{\prime})=T^{ss^{\prime}}_{a},\hskip
14.22636pt\forall s,s^{\prime}\in S,\forall a\in A.$

The set of equations for the value at each state $s\in S$ is

$\mathcal{M}_{V}:=V(s)=\max_{a}\sum_{s^{\prime}\in
S}T_{a}^{ss^{\prime}}[R_{a}^{ss^{\prime}}+\gamma V(s^{\prime})],\hskip
14.22636pt\forall s\in S.$

Last, we have the set of equations for action selection.

$\mathcal{M}_{A}:=(\pi(s)=a_{k})=\Big{[}\sum_{s^{\prime}\in
S}T_{a_{k}}^{ss^{\prime}}V(s^{\prime})=A_{max}^{s}\Big{]},\hskip
2.84526pt\forall s\in S.$

Here,

$A_{max}^{s}=\max_{a}\Big{(}\sum_{s^{\prime}\in
S}T_{a_{1}}^{ss^{\prime}}V(s^{\prime}),\ldots,\sum_{s^{\prime}\in
S}T_{a_{m}}^{ss^{\prime}}V(s^{\prime})\Big{)}.$

Thus we define
$~{}\displaystyle{\mathcal{M}:=\mathcal{M}_{R}\cup\mathcal{M}_{T}\cup\mathcal{M}_{V}\cup\mathcal{M}_{A}}$.

Figure 3. A layered causal graph representing the effect of rewards,
transitions, and values on action selection. $V^{a}(s)$ is the value of taking
action $a$ at state $s$.

The resultant LCG, shown in Fig. 3, is built conditioned on the agent’s
current state. If the agent moves to a new state, a new graph is built, since
reward and transition variables associated with successor states may change.
Here, we also see that some layers contain value variables conditioned on
particular actions ($V^{a}(s_{i})$), allowing us to analyze arbitrary
policies. If we want to answer queries about a fixed policy, these variables
can be collapsed into the existing value variables ($V(s_{i})$) since we no
longer perform a max operation. Fig. 3 shows only 4 successor states in
$S^{2}$, but there may be up to $|S|$. This graph thus reproduces either value
iteration or policy evaluation depending on whether $V^{a}(s_{i})$ variables
are aggregated. It is also possible to move variables from $\mathcal{V}$ to
the context $\mathcal{U}$, reducing complexity at the cost of eliminating
variables from causal analysis. For example, we could move all reward
variables to generate explanations using only transition variables.

##### Exactness Results

Layered MDPs are well-behaved since the SCMs formed by our construction
naturally form LCGs. Given $\mathcal{M}$ and a state $s_{0}$, we can construct
an LCG using the layered structure of the MDP. The following theorem and
lemmas give a class of MDPs for which LCGs may be constructed and analyzed
exactly.

###### Theorem 2.

Let $M$ be a finite-horizon MDP. If $G$ is a layered causal graph representing
$M$ at state $s$, then $G$ preserves cause-effect relationships in the
reasoning process for action selection in $M$ at $s$.

###### Lemma 3.0.

Given a finite-horizon MDP with horizon $h$ and start state $s_{0}$, there
exists an equivalent layered MDP.

Proof of Lemma 1: We prove this by providing an algorithm for constructing
layered MDPs from finite-horizon MDPs. For any start state $s_{0}$, we create
a successor graph $H$ such that a directed edge from node $i$ to $j$ exists if
and only if $\exists a\in A$ such that $T(s_{i},a,s_{j})>0$.

Next, we run Breadth First Search without an explored list until all paths of
length $\leq h$ have been explored and recorded. From these recorded paths, we
can create a tree with root node $s_{0}$. We then append “$k$” to state IDs at
the $k$th level of the tree. Last, we aggregate any duplicate nodes,
preserving their edges. Such nodes will only occur within the same layer of
the tree. Thus, after aggregation, the resulting successor graph may not be a
tree, but will be layered. ∎

###### Lemma 4.0.

If $G$ and $H$ are causal graphs of finite Bayesian networks, and there exists
a homomorphism $G\rightarrow H$, then $G$ and $H$ preserve cause-effect
relationships.

Proof of Lemma 2: This result follows from Jacobs et al. ((2019)) and Otsuka
and Saigo ((2022)).

Proof of Theorem 1: Since $M$ is finite-horizon, then by Lemma 1 we can create
an equivalent layered MDP and associated successor graph $H$ that represent
action selection for any given state $s$. We can construct a function $\psi$
that induces a homomorphism $\psi:G\rightarrow H$ in the following way: map
all nodes for variables $V(s_{i})$ or $T(s,a,s_{i})$ in $G$, to the node
representing $s_{i}$ in $H$.111Fig. 3 is an expanded version of the graph $G$,
where the odd layers (representing max($\cdot$) operations) have been
explicitly factored out to illustrate the possibility of modeling different
policies. Next, map all nodes for variables $R(s,a)$ to any node $n\in H$ such
that $\psi(T(s,a,s_{i}))=n$. Since the homomorphism $\psi:G\rightarrow H$
exists, and since MDPs may be represented as Bayesian networks, then by Lemma
2, $G$ captures all cause-effect relationships for action selection. ∎

###  4.2. Causal Inference for Layered MDPs

Given an LCG, we can perform causal inference to determine causal variables
with respect to an event $\phi$. In an MDP, a natural choice for $\phi$ is a
subset of the variables $\pi_{sa}$. For example, if action $a$ is taken in
state $s$ instead of $a^{\prime}$, we have

$\phi=\langle[\pi(s)=a],[\pi(s)=a^{\prime}]\rangle=\langle\textsc{True},\textsc{False}\rangle.$

However, it is less clear how to define potential explanans, denoted by $X$.
Intuitively, we often define $X$ as being, for example, the set of all state
factors, the set of all reward variables, or the set of all values for states
$h$ actions away. That is, we tend to define $X$ according to some semantic
type.

Given $X\subseteq\mathcal{V}$ and $\phi$, such that $\phi\cap X=\emptyset$, we
would like to check if variables in $X$ cause $\phi$. We now review
definitions of weak and actual cause from Halpern and Pearl ((2005a)) and
conditions for weak causality using LCGs.

###### Definition 0.

Let $X\subseteq V$ be a subset of the endogenous variables, and let $x$ be a
specific assignment of values for those variables. Given an event $\phi$,
defined as a logical expression, for instance $\phi=(\neg a\wedge b)$, a _weak
cause_ of $\phi$ satisfies the following conditions:

  1. (1)

Given the context $U=u$ and $X=x$, $\phi$ holds.

  2. (2)

Some $W\subseteq(V\setminus X)$ and some $\bar{x}$ and $w$ exist such that:

A) using these values produces $\neg\phi$.

B) for all $W^{\prime}\subseteq W$, $Z\subseteq V\setminus(X\cup W)$, where
$w^{\prime}=w|W^{\prime}$ and $z=Z$ given $U=u$, $\phi$ holds when $X=x$.

Essentially, item 2 b) is saying that, given context $U=u$, $X=x$ alone is
sufficient to cause $\phi$, independent of some other endogenous variables
$W$.

###### Definition 0.

An _actual cause_ is a weak cause $X$ where no such $X^{\prime}\subset X$
exists such that $X^{\prime}$ is also a weak cause.

We now introduce two additional constructs from Eiter and Lukasiewicz
((2006)), that they use to establish a theorem on identification of weak
causes. These constructs are general and do not have particular meaning with
respect to MDPs. First, however, some notation. $\mathcal{P}(\cdot)$ and
$\mathcal{D}(\cdot)$ denote power set and domain, respectively. $\phi_{xy}(u)$
is the value of $\phi$ given context $U=u$ and the assignments of variables
$X=x$ and $Y=y$. $w^{\prime}=w|W^{\prime}$ refers to the restriction of $w$ to
$W^{\prime}$. Last, $[x\langle y]=x|(X\setminus Y)\cup y$.

$\displaystyle R^{0}=$ $\displaystyle\\{(\mathbf{p},\mathbf{q},F)|F\subseteq
S^{0},\mathbf{p},\mathbf{q}\subseteq\mathcal{D}(F),\hskip 75.0pt$
$\displaystyle\exists w\in\mathcal{D}(S^{0}\setminus F)\forall
p,q\in\mathcal{D}(F):$ $\displaystyle p\in\mathbf{p}\text{ iff
}\neg\phi_{pw}(u),$ $\displaystyle q\in\mathbf{q}\text{ iff
}\phi_{[q\langle\hat{Z}(u)]w^{\prime}}(u)$ $\displaystyle\forall
W^{\prime}\subseteq S^{0}\setminus F,w^{\prime}=w|W^{\prime},\hat{Z}\subseteq
F\setminus S^{k},$

and

$\displaystyle R^{i}=$ $\displaystyle\\{(\mathbf{p},\mathbf{q},F)|F\subseteq
S^{i},\mathbf{p},\mathbf{q}\subseteq\mathcal{D}(F),$ $\displaystyle\exists
w\in\mathcal{D}(S^{0}\setminus
F)\exists(\mathbf{p^{\prime}},\mathbf{q^{\prime}},F^{\prime})\in
R^{i-1}\forall p,q\in\mathcal{D}(F):$ $\displaystyle p\in\mathbf{p}\text{ iff
}F_{pw}^{\prime}(u)\in\mathbf{p^{\prime}},$ $\displaystyle
q\in\mathbf{q}\text{ iff
}F_{[q\langle\hat{Z}(u)]w^{\prime}}^{\prime}(u)\in\mathbf{q^{\prime}}$
$\displaystyle\forall W^{\prime}\subseteq S^{0}\setminus
F,w^{\prime}=w|W^{\prime},\hat{Z}\subseteq F\setminus S^{k},\text{ for }i>0.$

1: Input: Layered causal graph $G$, variables $X$, event $\phi$

2: Output: Sets of weak causal variables $\mathcal{C}_{W}\subseteq X$ of
$\phi$.

3: $R^{0}\leftarrow\emptyset$, $S^{0},S^{k}\leftarrow$ layers of $G$
containing $\phi,X$

4: for all $F\in\mathcal{P}(S^{0})$ do

5: $\bf{p},\bf{q}\leftarrow\emptyset$

6: for all $w\in\mathcal{D}(S^{0}\setminus F)$ do

7: for all $p\in\mathcal{D}(F)$ do

8: if $\neg\phi$ given $p$ and $w$ then

9: ${\bf p}\leftarrow p\cup{\bf p}$

10: for all $q\in\mathcal{D}(F)$ do

11: $b\leftarrow$ True

12: for all $W^{\prime}\in\mathcal{P}(S^{0}\setminus F)$ do

13: $w^{\prime}\leftarrow w|W^{\prime}$

14: for all $\hat{Z}\in\mathcal{P}(F\setminus S^{k})$ do

15: $z^{\prime}\leftarrow\hat{Z}(u)$

16: if $\neg\phi$ given $q$, $\hat{z}$, and $w^{\prime}$ then

17: $b\leftarrow$ False

18: break

19: if $\neg b$ then

20: break

21: if $b$ then

22: ${\bf q}\leftarrow q\cup{\bf q}$

23: $R^{0}\leftarrow({\bf p},{\bf q},F)\cup R^{0}$

24: $R^{-}\leftarrow R^{0}$

25: $l\leftarrow 1$

26: while $l\leq k$ do

27: $R\leftarrow$ RecurrenceStep$(S^{l},S^{k},R^{-})$

28: $R^{-}\leftarrow R$, $l\leftarrow l+1$

29: $\mathcal{C}_{W}\leftarrow\emptyset$

30: for all $({\bf p},{\bf q},F)\in R^{-}$ do

31: if ${\bf p}\not=\emptyset$ and $x\in{\bf q}$ then

32: $\mathcal{C}_{W}\leftarrow x\cup\mathcal{C}_{W}$

33: return $\mathcal{C}_{W}$

Algorithm 1 Determine Weak Causes

###### Theorem 7.

(From Eiter and Lukasiewicz ((2006))) Let
$\mathcal{S}=(\mathcal{U},\mathcal{V},\mathcal{M})$ be a causal model. Let
$X\subseteq\mathcal{V}$, $x\in\mathcal{D}(X)$, $u\in\mathcal{D}(U)$, and let
$\phi$ be an event. Let $(S^{0},\ldots,S^{k})$ be a layering of
$G(\mathcal{S})$ relative to $X$ and $\phi$, and let $R^{k}$ be defined as
above. Then, $X=x$ is a weak cause of $\phi$ under $u$ in $\mathcal{S}$ iff
(1) $X(u)=x$ and $\phi(u)$ in $\mathcal{S}$, and (2) $\exists(p,q,X)\in R^{k}$
such that $\mathbf{p}\not=\emptyset$ and $x\in\mathbf{q}$.

We now develop a naive, exact algorithm, Algorithm 1, that computes
$R^{0},\ldots,R^{k}$ and then applies Theorem 2 to determine weak causality.
At a high level, Algorithm 1 proceeds up the causal chain in the LCG,
recursively identifying causes one layer at a time. That is, sets of variables
in $S^{1}$ are identified as causes of events in $S^{0}$. Those variables then
assume the role of the event(s) and their causes are identified in $S^{2}$.
This process repeats until the algorithm reaches layer $S^{k}$. Lines 7-9
check condition 2A from Def. 2, while lines 10-22 check condition 2B.
Condition 1 is always satisfied since $\phi$ represents some part of the
agent’s actual policy. The recurrence step (pseudocode in Appendix A) applies
the same reasoning to the output of the initial step. The final result is a
family of sets of causal variables $\mathcal{C}_{W}$, where
$\mathcal{C}_{W}^{i}\subseteq X$, that each satisfy Def. 2 w.r.t. the original
event $\phi$. We direct interested readers to Eiter and Lukasiewicz ((2006))
for a thorough treatment of Theorem 2 and definitions of $R^{0}$ and $R^{k}$.

One challenge is the continuous domain of variables representing the
transition and reward functions. Here, we assume a discretization scheme. For
example, reward variables could have discrete domains bounded by the min and
max of the original reward function. Furthermore, the variables in $X$ must be
located in the same layer in the causal graph.

Thus, Algorithm 1 supports analysis of LCGs as in Figs. 2 and 3, but is not
efficient and does not exploit any structure in MDPs. If we restrict $X$ to
the state factors in the MDP, we get LCGs as in Fig. 2. Here, we can use a
simpler algorithm, similar to that presented by Bertossi et al. ((2020)),
based on the concepts of responsibility and blame from Chockler and Halpern
((2004)). Algorithm 2 iterates directly through possible weak causal sets
(line 4), and then progressively checks larger sets $W$ for assignments $w$
that satisfy Def. 2. Lines 11-15 and 19-22 check conditions 2A and 2B,
respectively. Finally, lines 23-27 compute the responsibility score, $\rho$,
used to determine if $F$ is weakly causal. In addition to finding weak causal
sets consistent with Def. 2, $\rho$ provides a ranking over causal sets.
Algorithm 2, MeanRESP, has some properties that allow us to expand its
applicability later.

1: Input: State factors $F$, states $S$, policy $\pi$, start state $s_{0}$

2: Output: Set of weak causes $\mathcal{C}_{W}$, responsibility scores
$\mathcal{R}$.

3: $\mathcal{C}_{W},\mathcal{R}\leftarrow\emptyset$

4: for all $F^{\prime}\in\mathcal{P}(F)$ do

5: for all $\beta=0...|F\setminus F^{\prime}|$ do

6: $\sigma,t\leftarrow 0$

7: for all $W\in\mathcal{P}(F\setminus F^{\prime})$ such that $|W|=\beta$ do

8: for all $w\in\mathcal{D}(W)$ do

9: $b\leftarrow\textsc{True}$

10: $t\leftarrow t+1$

11: for all $W^{\prime}\in\mathcal{P}(W)$ do

12: $w^{\prime}\leftarrow w|W^{\prime}$

13: $s^{\prime}\leftarrow[s_{0}\langle w^{\prime}]$

14: if $\pi(s^{\prime})\neq\pi(s_{0})$ then

15: $b\leftarrow\textsc{False}$

16: break

17: if $\neg b$ then

18: continue

19: for all $f^{\prime}\in\mathcal{D}(F^{\prime})$ such that
$s_{0}|F^{\prime}\not=f^{\prime}$ do

20: $s^{\prime}\leftarrow[s_{0}\langle(f^{\prime}\cup w)]$

21: if $\pi(s^{\prime})\neq\pi(s_{0})$ then

22: $\sigma\leftarrow\sigma+\frac{1}{|\mathcal{D}(F^{\prime})|}$

23: $\rho\leftarrow\sigma/(t(1+\beta))$

24: if $\rho>0$ then

25: $\mathcal{C}_{W}\leftarrow\mathcal{C}_{W}\cup F^{\prime}$

26: $\mathcal{R}$.Append$(\rho)$

27: break

28: return $\mathcal{C}_{W}$

Algorithm 2 MeanRESP

We can determine actual causes by checking the minimality condition within the
weak causes $\mathcal{C}_{W}$ (psuedocode in Appendix A). Further, since
causal queries are made with respect to an event $\phi$ and variables $X$,
inference may be sped up by removing irrelevant variables. Graphs absent such
variables are called _strongly reduced_ (see the removal conditions and
algorithm in Appendix A).

##  5\. Generalization and Approximation

Although layered MDPs encompass a large class of MDPs, Algorithms 1 and 2 have
three key limitations. (1) They cannot represent infinite horizon problems.
(2) While the graph itself is straightforward to build for finite horizon
problems, very large problems or problems with large horizons may still be
prohibitively expensive to analyze. (3) These algorithms cannot handle
continuous state factors. In this section we propose several modifications to
MeanRESP and an additional pre-processing step that address these limitations,
either by constructing smaller, approximate causal models or by approximating
more expensive inference processes.

###  5.1. Approximate Causal Models for MDPs

Here, we address limitation (1). There are many methods for building
approximate causal graphs of arbitrary MDPs, depending on the available
information. We assume the original graph is built using a generic, uninformed
algorithm, such as the one we present in Appendix A based on Iwasaki et al.
((1986)). The resulting causal graph may not be unique if $\mathcal{M}$
contains circular dependencies (Iwasaki and Simon, 1986; Trave-Massuyes and
Pons, 1997). Since the Bellman update equation is a recurrence relation
between MDP state values, non-layered structures are highly likely.

Thus, we develop Algorithm 3 which, given state $s_{0}$ and causal graph $G$,
removes these structures to produce an LCG $G_{s_{0}}$ for causal analysis
whenever the agent is in state $s_{0}$. We consider a horizon $h$ and let
variables associated with states not reachable within $h$ actions form causal
‘leaves’ by removing their incoming causal edges. Remaining non-layered
structures are corrected by removing edges such that states farther from
$s_{0}$ causally influence states nearer to $s_{0}$, forming a simplified,
finite-horizon version of the original MDP. These operations are executed
simultaneously in Algorithm 3. In a sense, the causal influence flows from the
horizon at time $t+h$ back in time to the present time $t$.

1: Input: Causal graph $G$, successor graph $H$, current state $s_{0}$,
horizon $h$

2: Output: Layered causal graph $G_{s_{0}}$

3: $G_{s_{0}}(E^{\prime},\mathcal{V})\leftarrow G(E,\mathcal{V})$

4: for all $V_{s_{i}}\subset\mathcal{V}$ where $V_{s_{i}}$ represents
variables for state $s_{i}$ do

5: if $s_{i}$ is reachable on $H$ in $\kappa\leq h$ actions from $s_{0}$ then

6: label all $v\in V_{i}$ with $\kappa$

7: else

8: label all $v\in V_{i}$ with $\infty$

9: for all $v\in\mathcal{V}$ do

10: if label$(v)=\infty$ then

11: remove all incoming edges to $v$

12: continue

13: for all $v^{\prime}\in\mathcal{V}$ do

14: if label$(v)\geq$ label$(v^{\prime})$ then

15: $E^{\prime}\leftarrow E^{\prime}\setminus$ { directed edges from
$v^{\prime}$ to $v$ }

16: return $G_{s_{0}}$

Algorithm 3 Construct Layered Causal Graph

###  5.2. Approximate Causal Inference for MDPs

Often, models are too large for exact inference. Moreover, we may wish to
apply more restrictive versions of Def. 2, or extend analysis to real-valued
state factors. We address these problems via tweaks to MeanRESP. If state
factors are real-valued or their domains are simply too large, we can
approximate inference by replacing lines 7 and 8 with a single for loop over
vectors $w$ of size $\beta$ generated via sampling. Input-output pairs are
constructed and counted in the same way and the responsibility score still
indicates weak causality. The challenge becomes determining sampling domains
that cover important counterfactual scenarios efficiently.

There are several techniques applicable to both discrete and continuous
domains. One class involves limiting the sizes of $W$ and $Z$, the benefit of
which is reduction in problem complexity at the cost of omitting potential
weak causes. These restrictions of course diverge from Def. 2, but can be made
in a principled way that more or less preserves an order over the possible
results. In particular, one may set $Z=\emptyset$ and or $|W|\leq\eta$ for
some $\eta<<|\mathcal{V}|$. In the state factor case, the latter restriction
is equivalent to requiring $\rho\geq\epsilon>0$ rather than $\rho>0$, for weak
causality. Moreover, while we use one Def. 2, Halpern and Pearl, and later
Halpern (Halpern, 2015), have proposed several definitions.

Often, reward or transition variables in MDPs are not independent, but instead
depend on a high-level rule. For example, reward may be proportional to the
value of a state factor, or the transition function may encode identical
slipping probabilities regardless of location, as in classic grid-world
domains. These rules constrain the transition and reward function to
manifolds, and we can discretize these manifold to gain efficiency without
sacrificing important possible worlds. Given such structure we can replace
loops over, for example, all possible values of $T(s,a,s^{\prime})$, and
instead loop over the set of high-level rules, which is much smaller.

Finally, we may want to perform causal analysis on value function variables of
future states. If we want to look far into the future, or the branching factor
of the successor graph is large, the resulting LCG may be too large to
analyze, even when limiting domains or $|W|$ and $|Z|$. In these cases, we can
use a form of beam search to limit the intermediate events represented at each
layer of the LCG. The idea is to measure the influence of variables on $\phi$
and then keep only the $m$ most influential variables as the search
progresses.

##  6\. Results

We present three results: 1) a case study highlighting our framework’s
flexibility, 2) results of a user study showing strong user preference for
explanations generated via causal analysis, 3) asymptotic run time and memory
use bounds, and a discussion on the tightness of these bounds in practice and
potential pre-computation.

###  6.1. Case Study: Explanation Diversity

The purpose of this study is to show how (1) our approach can handle
_semantically different_ types of causal queries, corresponding to different
conceptions of MDP explanation in the literature, and (2) formal definitions
of causality identify sensible explanans. There are many templates for
inserting variables identified as explanans into natural language, which is
the predominant method. Here, we first qualitatively examine the correctness
of causal attribution.

Method | $F$ | $R$ | $T$ | $V$ | Causal?
---|---|---|---|---|---
Elizalde et al. ((2009)) | Yes | - | - | - | No
Russell and Santos ((2019)) | Yes | - | - | - | No
Khan et al. ((2009)) | - | Yes | - | - | No
Juozapaitis et al. ((2019)) | - | Yes | - | - | No
Betram et al. ((2018)) | - | Yes | - | - | No
Wang et al. ((2016)) | - | - | Yes | - | No
Madumal et al. ((2020)) | Yes | Yes | - | - | Yes
Proposed | Yes | Yes | Yes | Yes | Yes
Table 1. Comparison of method applicability

We have identified 4 general types of explanation in the literature, each
focusing on one component of the MDP tuple: _state factors_ ($F$) (Elizalde et
al. (2009); Russell et al. (2019)), _rewards_ ($R$) (Khan et al. (2009);
Juozapaitis et al. (2019); Bertram and Wei (2018)), _transitions_ ($T$) (Wang
et al. (2016)), and _future states and values_ ($V$) (Pouget et al., 2020).
These papers define metrics, algorithms, and definitions particular to their
type, and lead us to define the following.

###### Definition 0.

$Y$-type explanations use explanans $x\subset Y$. For example, $F$-type
explanations use the set of state factors.

We now detail an example MDP domain. Consider a robot navigating the
environment depicted in Figure 4. The agent knows: its $(x,y)$ location, time
to failure, $c$, and if its location is normal, ideal for repairs, or
hazardous, $t$. Thus, the state factors are $x\in\\{1,\ldots,9\\}$,
$y\in\\{1,\ldots,6\\}$, $c\in\\{0,\ldots,5\\}$,
$t\in\\{\textsc{Normal(N)},\textsc{Repair(R)},\textsc{Danger(D)}\\}$. The
actions are
$A=\\{\textsc{Up},\textsc{Left},\textsc{Right},\textsc{Repair}\\}$. If the
agent breaks down and cannot be repaired or visits a hazardous state, it gets
a reward of $-10$. Repairing has a reward of $R_{C}$, and reaching the $i$th
goal state yields reward $R_{i}$. All other state-actions have a reward of
$-1$. Last, transitions are deterministic except for actions Left and Right
when taken at $(5,3)$, which result in agent locations of $(4,3)$ (with
probability $T_{L}=0.6$) or $(4,4)$, and $(6,3)$ (with probability
$T_{R}=0.01$) or $(6,4)$, respectively. For all examples we considered event
$\phi=\pi_{s_{0}}$, and for explanation type $Y$ we set $X=Y$ and apply
MeanRESP. Table 2 shows the value of all state factors $s_{0}$, rewards, and
actions for each scenario. Below, we briefly contextualize MeanRESP’s output.

Figure 4. Example domain. The agent begins at $(5,1)$.

Scenario 1: The cause for action Repair is $t=$ R ($\rho=0.64$). Since
$R_{C}>0$, it is optimal to repair as it prevents failure later and is better
than the default reward of $-1$.

Scenarios 2 and 3: There are two causes of action Up in scenario 2: $t=$N
($\rho=0.50$) and $(x,y)=$(5,2) ($\rho=0.26$). Scenario 3 has the same causes,
but $\pi(s_{0})=$Left and $(x,y)$ has $\rho=0.60$. This is due to the topology
at (5,3) compared to (5,2). In both cases, $t$ is a cause since if $t=$R,
$\pi(s_{0})=$Repair.

Scenario 4: The causes for action Left are $c=2$ ($\rho=0.85$), $(x,y)=$(4,3)
($\rho=0.68$), and $t=$N ($\rho=0.60$). Note that unlike in previous
scenarios, time to failure is both a cause and has the highest responsibility
score. If the agent were to go directly to goal 2, it will break down at
(4,5).

Scenario 5: There are two causes of action Left: $R_{1}$ ($\rho=0.30$) and
$R_{3}$ ($\rho=0.55$). Since we bound $\mathcal{R}=[-100,100]$, no values for
$R_{2}$ or $R_{4}$ can change the outcome. $R_{4}$ is already the maximum, and
$R_{2}$ alone is not a cause due to its relatively weak effect on the expected
value of that subtree and transition variables were in $\mathcal{U}$ and not
$\mathcal{V}$.

Scenario 6: Here, only $R_{3}$ ($\rho=0.55$) is causal. Since $R_{C}>0$, the
agent exploits this by repeatedly taking service at (3,3). Thus, $R_{1}$ alone
cannot affect the agent’s policy since goals 1 and 4 will never be visited.
This is a good example of the proposed approach identifying a possible poorly
specified objective.

Scenarios 7 and 8: Since $R_{1}=R_{2}$ in scenario 7, the only cause of the
action Left is $T_{R}$ ($\rho=0.66$). However, in scenario 8, both $T_{R}$
($\rho=0.66$) and $T_{L}$ ($\rho=0.56$) are causes.

Scenario 9: Using MeanRESP with beam search, we find that the most influential
set of trajectories lead to goal 1. That is, its value contributes most to the
expected value, even though the most likely ($p{=}0.6$) outcome of taking
action Left at (5,3) reaches goal 2.

ID | $Y$ |  $s_{0}$ $(x,y,t,c)$ | $R_{1}$ | $R_{2}$ | $R_{3}$ | $R_{4}$ | $R_{C}$ | $Action$
---|---|---|---|---|---|---|---|---
1 | $F$ | (5,1), R, 5 | 80 | -50 | -40 | 100 | 2 | Repair
2 | $F$ | (5,2), N, 4 | 80 | -50 | -40 | 100 | 2 | Up
3 | $F$ | (5,3), N, 3 | 80 | -50 | -40 | 100 | 2 | Left
4 | $F$ | (4,3), N, 2 | 80 | 90 | -40 | 100 | -1 | Left
5 | $R$ | (5,3), N, 3 | 80 | -50 | -40 | 100 | -1 | Left
6 | $R$ | (5,3), N, 3 | 80 | -50 | -40 | 100 | 2 | Left
7 | $T$ | (5,3), N, 3 | 80 | 80 | 70 | 100 | -1 | Left
8 | $T$ | (5,3), N, 3 | 80 | -50 | -40 | 100 | -1 | Left
9 | $V$ | (5,3), N, 3 | 80 | -50 | -40 | 100 | -1 | Left
Table 2. List of scenarios

Summary: These scenarios show how different sets of explanans provide
_semantically distinct_ insights into variables’ effects on actions. This
underscores the utility of flexibility in generating explanations since the
‘best’ explanans may be unknown pre-deployment. Because existing methods only
analyze one component of the MDP, they cannot produce most of these
explanations (Table 1).

###  6.2. User Study

There is no definitive, automated metric for the quality of an explanation.
Therefore, the gold standard for assessing the effectiveness of an explanation
is a user study. Here, we describe the results of such a study, investigating
the following three hypotheses.

  * •

H1: Users tend to prefer explanations generated using causal reasoning over
explanations generated using heuristics.

  * •

H2: Users tend to prefer explanations supported by explanans representing
specific types of information.

  * •

H3: User preferences for explanation methods or explanan types correlate with
demographic or lifestyle indicators.

####  6.2.1. Study Description and Administration

In total, $189$ participants from the United States and Canada were recruited
via the crowd-sourcing platform Prolific (www.prolific.co). Participants were
fluent in English, were aged between 18 and 65, and 49% identified as male,
46% as female, and 5% as non-binary.

Participants were shown three short clips of simulated driving scenarios in a
randomized order, where a car drives on a highway (Leurent, 2018) and changes
speeds and lanes based on a policy from an MDP. After each particular action,
such as the left lane change shown in Fig. 5, participants were shown 7
different explanations in a randomized order, each generated by a different
method for automatic explanation, and asked to rank them relative to each
other to produce a strict preference ordering. The explanations shown included
three baselines: (Elizalde et al., 2009) ($F$-type), (Khan et al., 2009)
($R$-type), and (Wang et al., 2016) $T$-type as well as all four types of
explanation generated by our proposed method.

To present as little bias towards different explanations as possible, every
explanation was presented using the same basic template: ”The car ¡took
action¿ because ¡explanan 1¿, …, ¡explanan N¿.” Each explanan in the MDP had a
custom phrase, signifying both what the explanan represented and its value.

Figure 5. An example scene from the simulator where the ego car (green) makes
a left lane change.

####  6.2.2. Study Results

We find remarkably strong evidence in support of H1 and H2, and surprisingly,
strong evidence in favor of the null hypothesis w.r.t. H3. Below we review the
results in detail.

##### Preferences for Causal Explanations

Figure 6 summarizes our findings on user preferences for explanation methods.
The most important observation is that, for every explanation type, users
prefer the explanations generated via causal reasoning over those generated
via heuristic methods. We applied the Mann-Whitney U-test (Mann and Whitney,
1947) to each pair of generation methods (21 in total), using an initial
$\alpha$-value of $0.5$, and a Bonferonni corrected (Bonferroni, 1936)
$\alpha$-value of $0.0024$. We detected the following preference ordering with
p-values below 0.0001.

1) Prop-$F$ $\sim$ Prop-$V$ $\succ$ Elizalde $\succ$ Prop-$R$ $\sim$ Prop-$T$
$\succ$ Khan $\succ$ Wang

Here, $A\succ B$ denotes a strict preference for $A$ over $B$, and $\sim$
denotes preference equality.

Figure 6. Preference likelihoods for MDP explanation methods. The color of
cell $(row,col)$ indicates the probability that explanations generated using
method $row$ are preferred to explanations generated from method $col$.

We believe the overall preference for causal explanations is due to their
consistent relevance across all scenarios. For example, although both
heuristic and causal $F$-type methods have access to the same potential
explanans, and occasionally produce the same explanations, there are some
cases where the heuristic methods do not produce sensible explanations, such
as the following:

Heuristic Example: The car changed lanes to the right because the car was in
the left lane.

Casual Reasoning Example: The car changed lanes to the right because the car
was in the left lane, the estimated time to collision in the left lane was 2
seconds, and the right lane was empty.

Clearly, the heuristic method fails to provide both relevant and complete
information to explain the event in this case.

##### Preferences for Explanan Types

Figure 7 shows a similar analysis for the different types of explanation
($F$,$R$,$T$,$V$), where we can see that $F$-type explanations are, on
average, preferred over $R$-type and $T$-type. For this analysis if there were
multiple explanations based on the same explanans we used the most preferred
rank. For example, if a user preferred $A\succ B\succ C$, where $A$ and $C$
were $F$-type and $B$ was $R$-type, then we would record $F$-type as being
ranked highest, followed by $R$-type. We apply the same pair-wise Mann-Whitney
analysis as in H1, now with a total of 6 pairs and a Bonferonni corrected
$\alpha$-value of 0.0083. Following this analysis, we obtain the following
preference ordering: $F$-type $\succ$ $V$-type $\succ$ $R$-type $\sim$
$T$-type with p-value 0.00001.

Figure 7. Preference likelihoods for MDP explanations based on explanan type.

##### Demographic and Lifestyle Non-Impact

We found these results to be consistent across genders, age groups, and rates
of technology use. We also, somewhat surprisingly, found these results to be
consistent regardless of the frequency with which participants operated motor
vehicles. We also tried several unsupervised clustering methods to check for
more complex correlations between user demographics and preferences for
different types of explanations, but did not find anything significant. This
should give practitioners confidence that these results will hold in many
settings.

###  6.3. Resource Use and Practical Application

Table 3 shows some preliminary bounds on resource use. Here, $|S|$ is the size
of the state space, $|F|$ is the number of state factors, and $|\mathcal{V}|$
is the number of endogenous variables.

In practice, worst-case bounds are loose. In Algorithm 1, we check all
assignments of $X$, and $X\subseteq\mathcal{V}$. However, usually
$|X|<<|\mathcal{V}|$, especially after reducing the LCG. Bounds for Algorithm
2 are also poor estimates of in-practice cost, since it uses short-circuiting.
Some bounds’ tightness depends on the connectivity of the MDP. For Algorithm
3, the bounds assume fully-connected MDPs, but most MDPs are sparse and thus
the number of edges $E<<|S|^{2}$. Moreover, if $h$ is small compared to the
width of the MDP, run time will decrease since nodes labeled $\infty$ are
handled in linear time.

There are other possible improvements since theoretically every explanation
can be pre-computed, but this is impractical due to the number of possible
explanations. Notably, constructing LCGs for each state, regardless of how
$\phi$ and $X$ are specified, and computing connectivity and reachability
allows reductions and causal model approximations to be applied quickly
online, given $X$ and $\phi$.

Alg. | Res. | Complexity | Bottleneck
---|---|---|---
1 | time | $2^{|\mathcal{V}|}|\mathcal{D}(\mathcal{V})|^{2}k$ | Enumerating causal sets
| space | $4|\mathcal{V}|2^{|\mathcal{V}|}$ |  Storing $R$, $R^{-}$
2 | time | $2^{2|F|}|\mathcal{D}(F)|$ | Enumerating causal sets
| space | $2^{|F|}|F|$ | Storing weak causes
3 | time | $|S|^{2}(h+1)$ | Connectivity checks + Label comparisons
| space | $|S|^{2}$ | Reachability matrix
Table 3. Worst-case resource bounds for algorithms 1-3.

##  7\. Conclusion

We present a novel framework for causal analysis of MDPs using SCMs, motivated
by generating explanations of MDP agent behavior. Principally, this framework
provides (1) a theoretical foundation for explainable sequential decision
making, and (2) simultaneous support for causal queries using different
decision problem components, which has previously not been possible. Future
work will empirically investigate user preferences for explanations generated
using causal models compared to heuristics and how different contexts affect
user preferences for types of explanation.

## Appendix A

###  7.1. Producing Causal Graphs

Algorithm 4 generates a causal graph given a structural causal model by first
constructing a bipartite graph, where variables ($\mathcal{V}$) and equations
($\mathcal{M}$) are nodes, and edges exist between variable nodes and equation
nodes if that equation contains that variable. Given the bipartite graph,
Hopcroft-Karp is run to produce a perfect matching. This perfect matching is
used to build a _directed_ (causal) graph containing only variables.

1: Input: Set of variables $\mathcal{V}$, set of equations $\mathcal{M}$

2: Output: Causal graph $G$

3: $\mathcal{B}\leftarrow$ ConstructBipartite$(\mathcal{V},\mathcal{M})$

4: $E_{PM}\leftarrow$ Hopcroft-Karp$(\mathcal{B})$

5: $V\leftarrow\mathcal{V}$, $E\leftarrow\emptyset$

6: for all $v\in\mathcal{V}$ do

7: // $Q$ is a node in $\mathcal{B}$ representing an equation.

8: for all $e(v,Q)\in\textsc{Edges}(v)$ do

9: if $e\in E_{PM}$ then

10: // $V_{Q}$ is the set of variables in equation $Q$.

11: for all $v^{\prime}\in V_{Q},v^{\prime}\not=v$ do

12: $E\leftarrow E\cup\textsc{Edge}(v^{\prime},v)$

13: else

14: for all $v^{\prime}\in V_{Q},v^{\prime}\not=v$ do

15: $E\leftarrow E\cup\textsc{Edge}(v,v^{\prime})$

16: $G\leftarrow\\{E,V\\}$

17: return $G$

Algorithm 4 Construct Causal Graph

###  7.2. Reducing Causal Graphs

Eiter and Lukasiewicz ((2006)) provide the following conditions for removing a
variable $v$ from a causal graph.

  1. (1)

$v\in X$ is not connected via variables in $V\setminus X$ to $\phi$.

  2. (2)

$v$ is neither a direct parent of a variable in $\phi$ nor part of a chain
connecting $X$ to $\phi$.

Given an LCG $G_{s_{0}}$ Algorithm 5 produces a strongly reduced LCG
$G_{s_{0}}^{\phi X}$.

1: Input: Layered causal graph $G_{s_{0}}$, explanans $X$, event $\phi$

2: Output: Strongly reduced layered causal graph $G_{s_{0}}^{\phi X}$

3: $G_{s_{0}}^{\phi X}\leftarrow G_{s_{0}}$

4: for all $x\in X$ do

5: if $\not\exists$ path from $x$ to some $y\in\phi$ then

6: remove $x$ and its edges from $G_{s_{0}}^{\phi X}$

7: if $\forall$ paths from $x$ to $\phi$, $\exists x^{\prime}\in X$ along the
path then

8: remove $x$ and its edges from $G_{s_{0}}^{\phi X}$

9: for all $v\in V\setminus(X\cup\phi)$ do

10: if $\not\exists y\in\phi$ such that $v$ is a direct parent and
$\not\exists x\in X,y\in\phi$ such that $v\in x\rightarrow y$ then

11: remove $v$ and its edges from $G_{s_{0}}^{\phi X}$

12: return $G_{s_{0}}^{\phi X}$

Algorithm 5 Reduce Causal Graph

###  7.3. Recurrence Step for Determine Weak Causes

The outer loop (line 4) looks at all possible subsets of variables, $F$, in
the $i$th layer. Variables not in $F$ are assigned values $w$ one at a time,
eventually looping over all possible sets of values (line 6). Then, for every
tuple $R^{-}$ from layer $i-1$ (line 7), we check the conditions for
$p\in\bf{p}$ (lines 8-10) and $q\in\bf{q}$ (lines 11-23). Finally, for a given
set $F$, we add all the qualifying $p,q$ to the tuple $R$ (line 24).

1: Input: Layers $S^{i}$, $S^{k}$, tuples $R^{-}$

2: Output: Set of tuples $R$.

3: $R\leftarrow\emptyset$

4: for all $F\in\mathcal{P}(S^{i})$ do

5: $\bf{p}\leftarrow\emptyset$; $\bf{q}\leftarrow\emptyset$

6: for all $w\in\mathcal{D}(S^{i}\setminus F)$ do

7: for all $({\bf p^{\prime}},{\bf q^{\prime}},F^{\prime})\in R^{-}$ do

8: for all $p\in\mathcal{D}(F)$ do

9: if $F^{\prime}$, given $p$ and $w$, is in ${\bf p^{\prime}}$ then

10: ${\bf p}\leftarrow p\cup{\bf p}$

11: for all $q\in\mathcal{D}(F)$ do

12: $b\leftarrow$ True

13: for all $W^{\prime}\in\mathcal{P}(S^{i}\setminus F)$ do

14: $w^{\prime}\leftarrow w|W^{\prime}$

15: for all $\hat{Z}\in\mathcal{P}(F\setminus S^{k})$ do

16: $z^{\prime}\leftarrow\hat{Z}(u)$

17: if $F^{\prime}$, given $q$, $z^{\prime}$, and $w^{\prime}$, is not in
$q^{\prime}$ then

18: $b\leftarrow$ False

19: break

20: if $\neg b$ then

21: break

22: if $b$ then

23: ${\bf q}\leftarrow q\cup{\bf q}$

24: $R\leftarrow({\bf p},{\bf q},F)\cup R$

25: return $R$

Algorithm 6 Recurrence Step

## References

  * (1)
  * Bellman (1952) Richard Bellman. 1952\.  On the theory of dynamic programming.  _National Academy of Sciences of the United States of America_ 38, 8 (1952), 716.
  * Bertossi et al. (2020) Leopoldo Bertossi, Jordan Li, Maximilian Schleich, Dan Suciu, and Zografoula Vagena. 2020.  Causality-based Explanation of Classification Outcomes.  _arXiv preprint arXiv:2003.06868_ (2020).
  * Bertram and Wei (2018) Josh Bertram and Peng Wei. 2018.  Explainable deterministic MDPs.  _arXiv preprint arXiv:1806.03492_ (2018).
  * Bonferroni (1936) Carlo Bonferroni. 1936\.  Teoria statistica delle classi e calcolo delle probabilita.  _Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericiali di Firenze_ 8 (1936), 3–62.
  * Chakraborti et al. (2019) Tathagata Chakraborti, Anagha Kulkarni, Sarath Sreedharan, David E Smith, and Subbarao Kambhampati. 2019.  Explicability? legibility? predictability? transparency? privacy? security? the emerging landscape of interpretable agent behavior. In _International Conference on Automated Planning and Scheduling (ICAPS)_. 86–96.
  * Chakraborti et al. (2020) Tathagata Chakraborti, Sarath Sreedharan, and Subbarao Kambhampati. 2020.  The emerging landscape of explainable automated planning & decision making. In _International Joint Conference on Artificial Intelligence (IJCAI)_. 4803–4811.
  * Chakraborti et al. (2017) Tathagata Chakraborti, Sarath Sreedharan, Yu Zhang, and Subbarao Kambhampati. 2017.  Plan explanations as model reconciliation: Moving beyond explanation as soliloquy.  _arXiv preprint arXiv:1701.08317_ (2017).
  * Chen et al. (2018) Jessie YC Chen, Shan G Lakhmani, Kimberly Stowers, Anthony R Selkowitz, Julia L Wright, and Michael Barnes. 2018.  Situation awareness-based agent transparency and human-autonomy teaming effectiveness.  _Theoretical Issues in Ergonomics Science_ 19, 3 (2018), 259–282.
  * Chockler and Halpern (2004) Hana Chockler and Joseph Y Halpern. 2004.  Responsibility and blame: A structural-model approach.  _Journal of Artificial Intelligence Research_ 22 (2004), 93–115.
  * Eiter and Lukasiewicz (2006) Thomas Eiter and Thomas Lukasiewicz. 2006.  Causes and explanations in the structural-model approach: Tractable cases.  _Artificial Intelligence_ 170, 6-7 (2006), 542–580.
  * Elizalde et al. (2009) Francisco Elizalde, Enrique Sucar, Julieta Noguez, and Alberto Reyes. 2009.  Generating explanations based on Markov decision processes. In _Mexican International Conference on Artificial Intelligence_. Springer, 51–62.
  * Fox et al. (2017) Maria Fox, Derek Long, and Daniele Magazzeni. 2017.  Explainable planning.  _arXiv preprint arXiv:1709.10256_ (2017).
  * Freedman (2007) David A Freedman. 2007\.  Statistical models for causation.  _The SAGE Handbook of Social Science Methodology_ (2007), 127–146.
  * Giordano and Schwind (2004) Laura Giordano and Camilla Schwind. 2004.  Conditional logic of actions and causation.  _Artificial intelligence_ 157, 1-2 (2004), 239–279.
  * Halpern (2015) Joseph Halpern. 2015\.  A modification of the Halpern-Pearl definition of causality. In _Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI)_. 3022–3033.
  * Halpern and Pearl (2005a) Joseph Y Halpern and Judea Pearl. 2005a.  Causes and explanations: A structural-model approach. Part I: Causes.  _The British Journal for the Philosophy of Science_ 52, 3 (2005), 613–622.
  * Halpern and Pearl (2005b) Joseph Y Halpern and Judea Pearl. 2005b.  Causes and explanations: A structural-model approach. Part II: Explanations.  _The British Journal for the Philosophy of Science_ 56, 4 (2005), 889–911.
  * Hayes and Shah (2017) Bradley Hayes and Julie A Shah. 2017.  Improving robot controller transparency through autonomous policy explanation. In _ACM/IEEE International Conference on Human-Robot Interaction (HRI)_. 303–312.
  * Heider (1958) Fritz Heider. 1958\.  _The psychology of interpersonal relations_.  Wiley, New York.
  * Hesslow (1988) Germund Hesslow. 1988\.  The problem of causal selection.  _Contemporary Science and Natural Explanation: Commonsense Conceptions of Causality_ (1988), 11–32.
  * Hilton (1990) Denis J Hilton. 1990\.  Conversational processes and causal explanation.  _Psychological Bulletin_ 107, 1 (1990), 65\.
  * Hilton (1996) Denis J Hilton. 1996\.  Mental models and causal explanation: Judgements of probable cause and explanatory relevance.  _Thinking & Reasoning_ 2, 4 (1996), 273–308.
  * Hilton and Slugoski (1986) Denis J Hilton and Ben R Slugoski. 1986.  Knowledge-based causal attribution: The abnormal conditions focus model.  _Psychological Review_ 93, 1 (1986), 75.
  * Iwasaki and Simon (1986) Yumi Iwasaki and Herbert A Simon. 1986.  Causality in device behavior.  _Artificial intelligence_ 29, 1 (1986), 3–32.
  * Jacobs et al. (2019) Bart Jacobs, Aleks Kissinger, and Fabio Zanasi. 2019\.  Causal inference by string diagram surgery. In _International Conference on Foundations of Software Science and Computation Structures_. Springer, 313–329.
  * Juozapaitis et al. (2019) Zoe Juozapaitis, Anurag Koul, Alan Fern, Martin Erwig, and Finale Doshi-Velez. 2019.  Explainable reinforcement learning via reward decomposition. In _IJCAI/ECAI Workshop on Explainable Artificial Intelligence_.
  * Karimi et al. (2021) Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. 2021.  Algorithmic recourse: From counterfactual explanations to interventions. In _Proceedings of the ACM Conference on Fairness, Accountability, and Transparency_. 353–362.
  * Khan et al. (2009) Omar Khan, Pascal Poupart, and James Black. 2009\.  Minimal sufficient explanations for factored Markov decision processes. In _International Conference on Automated Planning and Scheduling (ICAPS)_ , Vol. 19.
  * Leurent (2018) Edouard Leurent. 2018\.  An Environment for Autonomous Driving Decision-Making.  https://github.com/eleurent/highway-env.
  * Lewis (1974) David Lewis. 1974\.  Causation.  _The Journal of Philosophy_ 70, 17 (1974), 556–567.
  * Linegang et al. (2006) Michael P Linegang, Heather A Stoner, Michael J Patterson, Bobbie D Seppelt, Joshua D Hoffman, Zachariah B Crittendon, and John D Lee. 2006.  Human-automation collaboration in dynamic mission planning: A challenge requiring an ecological approach.  _Proceedings of the Human Factors and Ergonomics Society Annual Meeting_ 50, 23 (2006), 2482–2486.
  * Lipton (1990) Peter Lipton. 1990\.  Contrastive explanation.  _Royal Institute of Philosophy Supplements_ 27 (1990), 247–266.
  * Lombrozo (2006) Tania Lombrozo. 2006\.  The structure and function of explanations.  _Trends in Cognitive Sciences_ 10, 10 (2006), 464–470.
  * Lombrozo (2010) Tania Lombrozo. 2010\.  Causal-explanatory pluralism: How intentions, functions, and mechanisms influence causal ascriptions.  _Cognitive Psychology_ 61, 4 (2010), 303–332.
  * Lombrozo (2012) Tania Lombrozo. 2012\.  Explanation and abductive inference.  In _The Oxford Handbook of Thinking and Reasoning_ , K J Holyoak and R G Morrison (Eds.). Oxford University Press, 260–276.
  * Lucic et al. (2020) Ana Lucic, Hinda Haned, and Maarten de Rijke. 2020.  Why does my model fail? Contrastive local explanations for retail forecasting. In _Proceedings of the ACM Conference on Fairness, Accountability, and Transparency_. 90–98.
  * Mackie (1980) John Leslie Mackie. 1980\.  _The cement of the universe: A study of causation_.  Clarendon Press.
  * Madumal et al. (2020) Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. 2020.  Explainable reinforcement learning through a causal lens. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 2493–2500.
  * Mann and Whitney (1947) Henry B Mann and Donald R Whitney. 1947.  On a test of whether one of two random variables is stochastically larger than the other.  _The annals of mathematical statistics_ (1947), 50–60.
  * Mercado et al. (2016) Joseph E Mercado, Michael A Rupp, Jessie YC Chen, Michael J Barnes, Daniel Barber, and Katelyn Procci. 2016.  Intelligent agent transparency in human-agent teaming for Multi-UxV management.  _Human Factors_ 58, 3 (2016), 401–415.
  * Miller (2019) Tim Miller. 2019\.  Explanation in artificial intelligence: Insights from the social sciences.  _Artificial intelligence_ 267 (2019), 1–38.
  * Mittelstadt et al. (2019) Brent Mittelstadt, Chris Russell, and Sandra Wachter. 2019\.  Explaining explanations in AI. In _Proceedings of the ACM Conference on Fairness, Accountability, and Transparency_. 279–288.
  * Mothilal et al. (2020) Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. 2020\.  Explaining machine learning classifiers through diverse counterfactual explanations. In _Proceedings of the ACM Conference on Fairness, Accountability, and Transparency_. 607–617.
  * Otsuka and Saigo (2022) Jun Otsuka and Hayato Saigo. 2022.  On the Equivalence of Causal Models: A Category-Theoretic Approach.  _arXiv preprint arXiv:2201.06981_ (2022).
  * Panigutti et al. (2020) Cecilia Panigutti, Alan Perotti, and Dino Pedreschi. 2020\.  Doctor XAI: An ontology-based approach to black-box sequential data classification explanations. In _Proceedings of the ACM Conference on Fairness, Accountability, and Transparency_. 629–639.
  * Pouget et al. (2020) Hadrien Pouget, Hana Chockler, Youcheng Sun, and Daniel Kroening. 2020.  Ranking Policy Decisions.  _arXiv preprint arXiv:2008.13607_ (2020).
  * Russell and Santos (2019) Jacob Russell and Eugene Santos. 2019.  Explaining reward functions in Markov decision processes. In _Thirty-Second International FLAIRS Conference_.
  * Salmon (2006) Wesley C Salmon. 2006\.  _Four decades of scientific explanation_.  University of Pittsburgh press.
  * Stubbs et al. (2007) Kristen Stubbs, Pamela J Hinds, and David Wettergreen. 2007\.  Autonomy and common ground in human-robot interaction: A field study.  _IEEE Intelligent Systems_ 22, 2 (2007), 42–50.
  * Trave-Massuyes and Pons (1997) Louise Trave-Massuyes and Renaud Pons. 1997.  Causal ordering for multiple mode systems. In _Proceedings of the Eleventh International Workshop on Qualitative Reasoning_. 203–214.
  * Wang et al. (2016) Ning Wang, David V Pynadath, and Susan G Hill. 2016\.  The Impact of POMDP-Generated Explanations on Trust and Performance in Human-Robot Teams. In _International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_. 997–1005.
  * Williams et al. (2013) Joseph Jay Williams, Tania Lombrozo, and Bob Rehder. 2013\.  The hazards of explanation: Overgeneralization in the face of exceptions.  _Journal of Experimental Psychology: General_ 142, 4 (2013), 1006\.
  * Woodward (2005) James Woodward. 2005\.  _Making things happen: A theory of causal explanation_.  Oxford university press.
  * Zhang et al. (2020) Yunfeng Zhang, Q Vera Liao, and Rachel KE Bellamy. 2020\.  Effect of confidence and explanation on accuracy and trust calibration in AI-assisted decision making. In _Proceedings of the ACM Conference on Fairness, Accountability, and Transparency_. 295–305.