# Sequential Causal Imitation Learning with Unobserved Confounders

Daniel Kumor
Purdue University
<EMAIL_ADDRESS>
&Junzhe Zhang
Columbia University
<EMAIL_ADDRESS>
&Elias Bareinboim
Columbia University
<EMAIL_ADDRESS>

###### Abstract

“Monkey see monkey do" is an age-old adage, referring to naïve imitation
without a deep understanding of a system’s underlying mechanics. Indeed, if a
demonstrator has access to information unavailable to the imitator (monkey),
such as a different set of sensors, then no matter how perfectly the imitator
models its perceived environment (See), attempting to reproduce the
demonstrator’s behavior (Do) can lead to poor outcomes. Imitation learning in
the presence of a mismatch between demonstrator and imitator has been studied
in the literature under the rubric of causal imitation learning (Zhang et al.,
2020), but existing solutions are limited to single-stage decision-making.
This paper investigates the problem of causal imitation learning in sequential
settings, where the imitator must make multiple decisions per episode. We
develop a graphical criterion that is necessary and sufficient for determining
the feasibility of causal imitation, providing conditions when an imitator can
match a demonstrator’s performance despite differing capabilities. Finally, we
provide an efficient algorithm for determining imitability and corroborate our
theory with simulations.

##  1 Introduction

Without access to observational data, an agent must learn how to operate at a
suitable level of performance through trial and error [21, 11]. This from-
scratch approach is often impractical in environments with the potential of
extreme negative - and final - outcomes (driving off a cliff). While both
Nature and machine learning researchers have approached the problem from a
wide variety of perspectives, a particularly potent method which has been used
with great success in many learning machines, including humans, is exploiting
observations of other agents in the environment [20, 6].

Learning to act by observing other agents offers a data multiplier, allowing
agents to take into account others’ experiences. Even when the precise loss
function is unknown (what exactly goes into being a good driver?), the agent
can attempt to learn from “experts”, namely agents which are known to gain an
acceptable reward at the target task. This approach has been studied under the
umbrella of imitation learning [2, 3, 6, 15]. Several methods have been
proposed, including inverse reinforcement learning [14, 1, 22, 30] and
behavior cloning [28, 19, 12, 13, 10]. The former attempts to reconstruct the
loss/reward function that the experts minimize and then use it for
optimization; the latter directly copies the expert’s actions (behavior
cloning).

Despite the power entailed by this approach, it relies on a somewhat stringent
condition: the expert and imitator’s sensory capabilities need to be perfectly
matched. As an example, self-driving cars rely solely on cameras or lidar,
completely ignoring the auditory dimension - and yet most human demonstrators
are able to exploit this data, especially in dangerous situations (car horns,
screeching tires). Perhaps without a microphone, the self-driving car would
incorrectly attribute certain behaviors to visual stimuli, leading to a poor
policy? For concreteness, consider the scenario shown in Fig. 1(a), where the
human driver ($X$, i.e., the demonstrator, in blue) is looking forward ($F$),
and can hear car horns ($H$) from cars behind ($B$), and to the side ($S$).
The driver’s performance is represented by a variable $Y$ (red), which is
unobserved (dashed node). Since our dataset only contains visual data, car
horns $H$ remain unobserved to the learning agent (i.e., the imitator).
Despite not being able to hear car horns, the learner from Fig. 1(a) had a
full view of the car’s surroundings, including cars behind and to the side,
which turns out to be sufficient to perform imitation in this example.
Consider an instance where $F,B,S$ are drawn uniformly over $\\{0,1\\}$. The
reward $Y$ is decided by $\neg X\oplus F\oplus B\oplus S$; $\oplus$ represents
the exclusive-or operator. The human driver decides the action $X\leftarrow H$
where values of horn $H$ is given by $F\oplus B\oplus S$. Preliminary analysis
reveals that the learner could perfectly mimic the demonstrator’s decision-
making process using an imitating policy $X\leftarrow F\oplus B\oplus S$. On
the other hand, if the driving system does not have side cameras, the side
view $S$ becomes latent; see Fig. 1(b). The learner’s reward ${\rm
I\kern-3.00003ptE}[Y|\text{do}(\pi)]$ is equal to $0.5$ for any policy
$\pi(x|f,b)$, which is far from the optimal demonstrator’s performance, ${\rm
I\kern-3.00003ptE}[Y]=1$.

Based on these examples, there arises the question of determining precise
conditions under which an agent can account for the lack of knowledge or
observations available to the expert, and how this knowledge should be
combined to generate an optimal imitating policy, giving identical performance
as the expert on measure $Y$. These questions have been recently investigated
in the context of causal imitation learning  [29], where a complete graphical
condition and algorithm were developed for determining imitability in the
single-stage decision-making setting with partially observable models (i.e.,
in non-Markovian settings). Other structural assumptions, such as linearity
[5], were also explored in the literature, but were still limited to a single
action. Finally, [4] explore the case when expert and imitator can observe the
same contexts, but the causal diagram is not available. Despite this progress,
it is still unclear how to systematically imitate, or even whether imitation
is possible when a learner must make several actions in sequence, where expert
and imitator observe differing sets of variables (e.g., Figs. 1(c) and 1(d)).

The goal of this paper is to fill this gap in understanding. More
specifically, our contributions are as follows. (1) We provide a graphical
criterion for determining whether imitability is feasible in sequential
settings based on a causal graph encoding the domain’s causal structure. (2)
We propose an efficient algorithm to determine imitability and to find the
policy for each action that leads to proper imitation. (3) We prove that the
proposed criterion is complete (i.e. both necessary and sufficient). Finally,
we verify that our approach compares favorably with existing methods in
contexts where a demonstrator has access to latent variables through
simulations. Due to space constraints, proofs are provided in the complete
technical report [9].

$X$$Y$$F$$B$$S$$H$ (a)

$X$$Y$$F$$B$$S$$H$ (b)

$X_{1}$$X_{2}$$Z$$U$$Y$ (c)

$X_{2}$$X_{1}$$Z$$U_{1}$$U_{2}$$Y$ (d)

Figure 1: (1(a), 1(b)) represents a simplified view of a driver $X$ and
surrounding cars $F,B,S$. (1(c)) is imitable with policies
$\pi_{1}(X_{1})=P(X_{1})$ and $\pi_{2}(X_{2}|Z)=P(X_{2}|Z)$, but in (1(d))
$X_{1},X_{2}$ is not imitable, despite there being a valid sequential
backdoor.

###  1.1 Preliminaries

We start by introducing the notation and definitions used throughout the
paper. In particular, we use capital letters for random variables ($Z$), and
small letters for their values ($z$). Bolded letters represent sets of random
variables and their samples ($\bm{Z}=\\{Z_{1},...,Z_{n}\\}$,
$\bm{z}=\\{z_{1}\sim Z_{1},...,z_{n}\sim Z_{n}\\}$). $|\bm{Z}|$ represents a
set’s cardinality. The joint distribution over variables $\bm{Z}$ is denoted
by $P(\bm{Z})$. To simplify notation, we consistently use the shorthand
$P(z_{i})$ to represent probabilities $P(Z_{i}=z_{i})$.

The basic semantic framework of our analysis rests on structural causal models
(SCMs) [17, Ch. 7]. An SCM $M$ is a tuple
$\langle\bm{U},\bm{V},\bm{F},P(\bm{u})\rangle$ with $\bm{V}$ the set of
endogenous, and $\bm{U}$ exogenous variables. $\bm{F}$ is a set of structural
functions s.t. for $f_{V}\in\bm{F}$, $V\leftarrow
f_{V}(\mathit{pa}_{V},u_{V})$, with
$\mathit{PA}_{V}\subseteq\bm{V},U_{V}\subseteq\bm{U}$ . Values of $\bm{U}$ are
drawn from an exogenous distribution $P(\bm{u})$, inducing distribution
$P(\bm{V})$ over the endogenous $\bm{V}$. Since the learner can observe only a
subset of endogenous variables, we split $\bm{V}$ into $\bm{O}\subseteq\bm{V}$
(observed) and $\bm{L}=\bm{V}\setminus\bm{O}$ (latent) sets of variables. The
marginal $P(\bm{O})$ is thus referred to as the _observational distribution_.

Each SCM $M$ is associated with a causal diagram $\mathcal{G}$ where (e.g.,
see Fig. 2(d)) solid nodes represent observed variables $\bm{O}$, dashed nodes
represent latent variables $\bm{L}$, and arrows represent the arguments
$\mathit{pa}(V)$ of each functional relationship $f_{V}$. Exogenous variables
$\bm{U}$ are not explicitly shown; a bi-directed arrow between nodes $V_{i}$
and $V_{j}$ indicates the presence of an unobserved confounder (UC) affecting
both $V_{i}$ and $V_{j}$. We will use standard conventions to represent
graphical relationships such as parents, children, descendants, and ancestors.
For example, the set of parent nodes of $\bm{X}$ in $\mathcal{G}$ is denoted
by
$\mathit{pa}(\bm{X})_{\mathcal{G}}=\cup_{X\in\bm{X}}\mathit{pa}(X)_{\mathcal{G}}$.
$\mathit{ch}$, $\mathit{de}$ and $\mathit{an}$ are similarly defined.
Capitalized versions $\mathit{Pa},\mathit{Ch},\mathit{De},\mathit{An}$ include
the argument as well, e.g.
$\mathit{De}(\bm{X})_{\mathcal{G}}=\mathit{de}(\bm{X})_{\mathcal{G}}\cup\bm{X}$.
An observed variable $V_{i}\in\bm{O}$ is an _effective parent_ of
$V_{j}\in\bm{V}$ if there is a directed path from $V_{i}$ to $V_{j}$ in
$\mathcal{G}$ such that every internal node on the path is in $\bm{L}$. We
define $\mathit{pa}^{+}(\bm{S})$ as the set of effective parents of variables
in $\bm{S}$, excluding $\bm{S}$ itself, and $\mathit{Pa}^{+}(\bm{S})$ as
$\bm{S}\cup\mathit{pa}^{+}(\bm{S})$. Other relations, like $ch^{+}(\bm{S})$
are defined similarly.

A path from a node $X$ to a node $Y$ in $\mathcal{G}$ is said to be “active"
conditioned on a (possibly empty) set $\bm{W}$ if there is a collider at $A$
along the path ($\rightarrow A\leftarrow$) only if $A\in\mathit{An}(\bm{W})$,
and the path does not otherwise contain vertices from $\bm{W}$ (d-separation,
[7]). $\bm{X}$ and $\bm{Y}$ are independent conditioned on $\bm{W}$
$(\bm{X}\perp\\!\\!\\!\perp\bm{Y}|\bm{W})_{\mathcal{G}}$ if there are no
active paths between any $X\in\bm{X}$ and $Y\in\bm{Y}$. For a subset
$\bm{X}\subseteq\bm{V}$, the subgraph obtained from $\mathcal{G}$ with edges
outgoing from $\bm{X}$ / incoming into $\bm{X}$ removed is written
$\mathcal{G}_{\underline{\bm{X}}}$/$\mathcal{G}_{\overline{\bm{X}}}$
respectively. Finally, we utilize a grouping of observed nodes, called
_confounded components_ (c-components, [25, 23]).

######  Definition 1.1.

For a causal diagram $\mathcal{G}$, let $\bm{N}$ be a set of unobserved
variables in $\bm{L}\cup\bm{U}$. A set
$\bm{C}\subseteq\mathit{Ch}(\bm{N})\cap\bm{O}$ is a c-component if for any
pair $U_{i},U_{j}\in\bm{N}$, there exists a path between $U_{i}$ and $U_{j}$
in $\mathcal{G}$ such that every observed node $V_{k}\in\bm{O}$ on the path is
a collider (i.e., $\rightarrow V_{k}\leftarrow$).

C-components correspond to observed variables whose values are affected by
related sets of unobserved common causes, such that if $A,B\in\bm{C}$,
$(A\not\perp\\!\\!\\!\perp B|\bm{O}\setminus\\{A,B\\})$. In particular, we
focus on maximal c-components $\bm{C}$ , where there doesn’t exist c-component
$\bm{C}^{\prime}$ s.t. $\bm{C}\subset\bm{C}^{\prime}$. The collection of
maximal c-components forms a partition $\bm{C}_{1},\dots,\bm{C}_{m}$ over
observed variables $\bm{O}$. For any set $S\subseteq\bm{O}$, let $\bm{C}(S)$
be the union of c-components $\bm{C}_{i}$ that contain variables in $S$. For
instance, for variable $Z$ in Fig. 1(d), the c-component
$\bm{C}(\\{Z\\})=\\{Z,X_{1}\\}$.

$Z$$Y$$X$

$U$

(a)

$X_{2}$$Y$$X_{1}$

$U$

(b)

$X_{1}$$W$$X_{2}$$Y$$Z$

$U_{1}$

(c)

$Z$$W$$X_{2}$$Y$$X_{1}$

$U_{2}$

$U_{1}$

(d)

Figure 2: Despite there being no latent path between $Y$ and any $X$, the
query in (2(a)) is not imitable, but the query in (2(b)) is imitable. While
(2(c)) is imitable if $Z$ comes before $X_{2}$ in temporal order, the query in
(2(d)) is imitable only if $Z$ comes before $X_{1}$.

##  2 Causal Sequential Imitation Learning

We are interested in learning a policy over a series of actions
$\bm{X}\subseteq\bm{O}$ so that an imitator gets average reward $Y\in\bm{V}$
identical to that of an expert demonstrator. More specifically, let variables
in $\bm{X}$ be ordered by $X_{1},\dots,X_{n}$, $n=|\bm{X}|$. Actions are taken
sequentially by the imitator, where only information available at the time of
the action can be used to inform a policy for $X_{i}\in\bm{X}$. To encode the
ordering of observations and actions in time, we fix a topological ordering on
the variables of $\mathcal{G}$, which we call the “temporal ordering”. We
define functions $\operatorname{before}(X_{i})$ and
$\operatorname{after}(X_{i})$ to represent nodes that come before/after an
action $X_{i}\in\bm{X}$ following the ordering, excluding $X_{i}$ itself. A
policy $\pi$ on actions $\bm{X}$ is a sequence of decision rules
$\\{\pi_{1},\dots,\pi_{n}\\}$ where each $\pi_{i}(X_{i}|\bm{Z}_{i})$ is a
function mapping from domains of covariates
$\bm{Z}_{i}\subseteq\operatorname{before}(X_{i})$ to the domain of action
$X_{i}$. The imitator following a policy $\pi$ replacing the demonstrator in
an environment is encoded by replacing the expert’s original policy in the SCM
$M$ with $\pi$, which gives the results of the imitator’s actions as
$P(\bm{V}|\text{do}(\pi))$. Our goal is to learn an imitating policy $\pi$
such that the induced distribution $P(Y|\text{do}(\pi))$ perfectly matches the
original expert’s performance $P(Y)$. Formally

######  Definition 2.1.

[29] Given a causal diagram $\mathcal{G}$, $\bm{Y}\subseteq\bm{V}$ is said to
be imitable with respect to actions $\bm{X}\subseteq\bm{O}$ in $\mathcal{G}$
if there exists $\pi\in\Pi$ uniquely discernible from the observational
distribution $P(\bm{O})$ such that for all possible SCMs $M$ compatible with
$\mathcal{G}$, $P(\bm{Y})_{M}=P(\bm{Y}|do(\pi))_{M}$.

In other words, the expert’s performance on reward $Y$ is imitable if any set
of SCMs must share the same imitating policy $\pi\in\Pi$ whenever they
generate the same causal diagram $\mathcal{G}$ and the observational
distribution $P(\bm{O})$. Henceforth, we will consistently refer to Def. 2.1
as the _fundamental problem of causal imitation learning_. For single stage
decision-making problems ($\bm{X}=\\{X\\}$), [29] demonstrated imitability for
reward $Y$ if and only if there exists a set
$\bm{Z}\subseteq\operatorname{before}(X)$ such that
$\left(Y\perp\\!\\!\\!\perp X|\bm{Z}\right)_{\mathcal{G}_{\underline{X}}}$,
called the backdoor admissible set, [17, Def. 3.3.1] ($\bm{Z}=\\{F,B,S\\}$ in
Fig. 1(a)). It is verifiable that an imitating policy is given by
$\pi(X|F,B,S)=P(X|F,B,S)$.

Since the backdoor criterion is complete for the single-stage problem, one may
be tempted to surmise that a version of the criterion generalized to multiple
interventions might likewise solve the imitability problem in the general case
($|\bm{X}|>1$). Next we show that this is not the case. Let $\bm{X}_{1:i}$
stand for a sequence of variables $\\{X_{1},\dots,X_{i}\\}$;
$\bm{X}_{1:i}=\emptyset$ if $i<1$. [18] generalized the backdoor criterion to
the sequential decision-making setting as follows:

######  Definition 2.2.

[18] Given a causal diagram $\mathcal{G}$, a set of action variables $\bm{X}$,
and target node $Y$, sets
$\bm{Z}_{1}\subseteq\operatorname{before}(X_{1}),\dots,\bm{Z}_{n}\subseteq\operatorname{before}(X_{n})$
satisfy the sequential backdoor for $(\mathcal{G},\bm{X},Y)$ if for each
$X_{i}\in\bm{X}$ such that $(Y\perp\\!\\!\\!\perp
X_{i}|\bm{X}_{1:i-1},\bm{Z}_{1:i})_{\mathcal{G}_{\underline{X}_{i}\overline{\bm{X}}_{i+1:n}}}$.

While the sequential backdoor is an extension of the backdoor to multi-stage
decisions, its existence does not always guarantee the imitability of latent
reward $Y$. As an example, consider the causal diagram $\mathcal{G}$ described
in Fig. 1(d). In this case, $\bm{Z}_{1}=\\{\\},\bm{Z}_{2}=\\{Z\\}$,
$\\{(X_{1},\bm{Z}_{1}),(X_{2},\bm{Z}_{2})\\}$ is a sequential backdoor set for
$(\mathcal{G},\\{X_{1},X_{2}\\},Y)$, but there are distributions for which no
agent can imitate the demonstrator’s performance ($Y$) without knowledge of
either the latent $U_{1}$ or $U_{2}$. To witness, suppose that the adversary
sets up an SCM with binary variables as follows: $U_{1},U_{2}\sim Bern(0.5)$,
with $X_{1}:=U_{1}$, $Z:=U_{1}\oplus U_{2}$, $X_{2}:=Z$ and
$Y=\lnot(X_{1}\oplus X_{2}\oplus U_{2})$, with $\oplus$ as a binary XOR. The
fact that $U\oplus U=0$ is exploited to generate a chain where each latent
variable appears exactly twice in $Y$, making $Y=\lnot(U_{1}\oplus(U_{1}\oplus
U_{2})\oplus U_{2})=1$. On the other hand, when imitating, $X_{1}$ can no
longer base its value on $U_{1}$, making the imitated
$\hat{Y}=\lnot(\hat{X}_{1}\oplus\hat{X}_{2}\oplus U_{2})$. The imitator can do
no better than ${\rm I\kern-3.00003ptE}[\hat{Y}]=0.5$! We refer readers to [9,
Proposition C.1] for a more detailed explanation.

###  2.1 Sequential Backdoor for Causal Imitation

We now introduce the main result of this paper: a generalized backdoor
criterion that allows one to learn imitating policies in the sequential
setting. For a sequence of covariate sets
$\bm{Z}_{1}\subseteq\operatorname{before}(X_{1}),\dots,\bm{Z}_{n}\subseteq\operatorname{before}(X_{n})$,
let $\mathcal{G}^{\prime}_{i}$, $i=1,\dots,n$, be the manipulated graph
obtained from a causal diagram $\mathcal{G}$ by first (1) removing all arrows
coming into nodes in $X_{i+1:n}$; and (2) adding arrows
$\bm{Z}_{i+1}\rightarrow X_{i+1},\dots,\bm{Z}_{n}\rightarrow X_{n}$. We can
then define a sequential backdoor criterion for causal imitation as follows:

######  Definition 2.3.

Given a causal diagram $\mathcal{G}$, a set of action variables $\bm{X}$, and
target node $Y$, sets
$\bm{Z}_{1}\subseteq\operatorname{before}(X_{1}),\dots,\bm{Z}_{n}\subseteq\operatorname{before}(X_{n})$
satisfy the “sequential $\pi$-backdoor"111The $\pi$ in “$\pi$-backdoor” is
part of the name, and does not refer to any specific policy. for
$(\mathcal{G},\bm{X},Y)$ if at each $X_{i}\in\bm{X}$, either (1)
$(X_{i}\perp\\!\\!\\!\perp Y|\bm{Z}_{i})$ in
$(\mathcal{G}^{\prime}_{i})_{\underline{X_{i}}}$, or (2) $X_{i}\notin An(Y)$
in $\mathcal{G}^{\prime}_{i}$.

The first condition of Def. 2.3 is similar to the backdoor criterion where
$\bm{Z}_{i}$ is a set of variables that effectively encodes all information
relevant to imitating $X_{i}$ with respect to $Y$. In other words, if the
joint $P(\bm{Z}_{i}\cup\\{X_{i}\\})$ matches when both expert and imitator are
acting, then an adversarial $Y$ cannot distinguish between the two. The
critical modification of the original $\pi$-backdoor for the sequential
setting comes from the causal graph in which this check happens.
$\mathcal{G}^{\prime}_{i}$ can be seen as $\mathcal{G}$ with all future
actions of the imitator already encoded in the graph. That is, when performing
a check for $X_{i}$, it is done with all actions after $i$ being performed by
the imitator rather than expert, with the associated parents of each future
$X_{j>i}$ replaced with their corresponding imitator’s conditioning set.
Several examples of $\mathcal{G}^{\prime}_{i}$ are shown in Fig. 3.

The second condition allows for the case where an action at $X_{i}$ has no
effect on the value of $Y$ once future actions are taken. Since
$\mathcal{G}^{\prime}_{i}$ has modified parents for future $\bm{X}_{j>i}$, the
value of $X_{i}$ might no longer be relevant at all to $Y$, i.e. $Y$ would get
the same input distribution no matter what policy is chosen for $X_{i}$. This
allows $X_{i}$ to fail condition (1), meaning that it is not imitable by
itself, but still be part of an imitable set $\bm{X}$, because future actions
can shield $Y$ from errors made at $X_{i}$.

The distinction between condition 1 and condition 2 is shown in Fig. 3(c): in
the original graph $\mathcal{G}$ described in Fig. 2(c), if $Z$ comes after
$X_{1}$, then there is no valid adjustment set that can d-separate $X_{1}$
from $Y$. However, if the imitating policy for $X_{2}$ uses $Z$ instead of $W$
or $X_{1}$ (i.e. $\pi_{X_{2}}=P(X_{2}|Z)$), $X_{1}$ will no longer be an
ancestor of $Y$ in $\mathcal{G}^{\prime}_{1}$. In effect, the action made at
$X_{2}$ ignores the inevitable mistakes made at $X_{1}$ due to not having
access to confounder $U_{1}$ when taking the action.

Indeed, the sequential $\pi$-backdoor criterion can be seen as a recursively
applying the single-action $\pi$-backdoor. Starting from the last action
$X_{k}$ in temporal order, one can directly show that $Y$ is imitable using a
backdoor admissible set $\bm{Z}_{k}$ (or $X_{k}$ doesn’t affect $Y$ by any
causal path). Replacing $X_{k}$ in the SCM with this new imitating policy, the
resulting SCM with graph $G^{\prime}_{k-1}$ has an identical distribution over
$Y$ as $\mathcal{G}$. The procedure can then be repeated for $X_{k-1}$ using
$G^{\prime}_{k-1}$ as the starting graph, and continued recursively, showing
imitability for the full set:

######  Theorem 2.1.

Given a causal diagram $\mathcal{G}$, a set of action variables $\bm{X}$, and
target node $Y$, if there exist sets $\bm{Z}_{1},\bm{Z}_{2},...,\bm{Z}_{k}$
that satisfy the sequential $\pi$-backdoor criterion with respect to
$(\mathcal{G},\bm{X},Y)$, then $Y$ is imitable with respect to $\bm{X}$ in
$\mathcal{G}$ with policy $\pi(X_{i}|\bm{Z_{i}})=P(X_{i}|\bm{Z}_{i})$ for each
$X_{i}\in\bm{X}$.

Thm. 2.1 establishes the sufficiency of the sequential $\pi$-backdoor for
imitation learning. Consider again the diagram in Fig. 2(c). It is verifiable
that covariate sets $\bm{Z}_{1}=\\{\\},\bm{Z}_{2}=\\{Z\\}$ are sequential
$\pi$-backdoor admissible. Thm. 2.1 implies that the imitating policy is given
by $\pi_{1}(X_{1})=P(X_{1})$ and $\pi_{2}(X_{2}|Z)=P(X_{2}|Z)$. Once
$\pi$-backdoor admissible sets are obtained, the imitating policy can be
learned from the observational data through standard density estimation
methods for stochastic policies, and supervised learning methods for
deterministic policies. This means that the sequential $\pi$-backdoor is a
method for choosing a set of covariates to use when performing imitation
learning, which can be used instead of $Pa(X_{i})$ for each $X_{i}\in\bm{X}$
in the case when the imitator does not observe certain elements of
$Pa(\bm{X})$. With the covariates chosen using the sequential $\pi$-backdoor,
one can use domain-specific algorithms for computing an imitating policy based
on the observational data.

$X_{1}$$X_{2}$$Z$$U$$Y$ (a)

$X_{2}$$Y$U$U$$U$$X_{1}$ (b)

$X_{1}$$W$$X_{2}$$U$$U$$Y$$Z$

$U_{1}$

(c)

$Z$$W$$X_{2}$$U$$U$$Y$$X_{1}$

$U_{2}$

$U_{1}$

(d)

Figure 3: Examples of $\mathcal{G}^{\prime}_{1}$. In Fig. 1(c), we can have
$\bm{Z}_{1}=\emptyset,\bm{Z}_{2}=\\{Z\\}$, so $X_{2}$ has its parents cut, and
a new arrow added from $Z$ to $X_{2}$ (blue). The independence check
$(X_{1}\perp\\!\\!\\!\perp Y|\emptyset)$ is done in graph (3(a)) with edges
outgoing from $X_{1}$ removed (orange). In Fig. 2(b), using
$\bm{Z}_{1}=\emptyset,\bm{Z}_{2}=\\{X_{1}\\}$, we first replace the parents of
$X_{2}$ with just $X_{1}$ (3(b)), and then remove both resulting outgoing
edges from $X_{1}$ to check if $(X_{1}\perp\\!\\!\\!\perp Y)$. On the other
hand, in Fig. 2(c), if $\bm{Z}_{2}=\\{Z\\}$, we get (3(c)), which means
$X_{i}\notin An(Y)$, passing condition 2 of Def. 2.3. Finally, in Fig. 2(d),
with $\bm{Z}_{2}=\\{W\\}$, $X_{1}$ must condition on either $Z$ or $W$ to be
independent of $Y$ in (3(d)) once the edge $X_{1}\rightarrow Y$ is removed.

##  3 Finding Sequential $\pi$-Backdoor Admissible Sets

At each $X_{i}$, the sequential $\pi$-backdoor criterion requires that
$\bm{Z}_{i}$ is a back-door adjustment set in the manipulated graph
$\mathcal{G}^{\prime}_{i}$. There already exist efficient methods for finding
adjustment sets in the literature [24, 26], so if the adjustment were with
reference to $\mathcal{G}$, one could run these algorithms on each $X_{i}$
independently to find each backdoor admissible set $\bm{Z}_{i}$. However, each
action $X_{i}$ has its $\bm{Z}_{i}$ in the manipulated graph
$\mathcal{G}^{\prime}_{i}$, which is dependent on the adjustment used for
future actions $X_{i+1:n}$. This means that certain adjustment sets
$\bm{Z}_{j}$ for $X_{j>i}$ will make there not exist any $\bm{Z}_{i}$ for
$X_{i}$ in $\mathcal{G}^{\prime}_{i}$ that satisfies the criterion! As an
example, in Fig. 2(c), $X_{2}$ can use any combination of $Z,X_{1},W$ as a
valid adjustment set $\bm{Z}_{2}$. However, if $Z$ comes after $X_{1}$ in
temporal order, only $\bm{Z}_{2}=\\{Z\\}$ leads to valid imitation over
$\bm{X}=\\{X_{1},X_{2}\\}$.

The direct approach towards solving this problem would involve enumerating all
possible backdoor admissible sets $\bm{Z}_{i}$ for each $X_{i}$, but there are
both exponentially many backdoor admissible sets $\bm{Z}_{i}$, and
exponentially many combinations of sets over multiple $X_{i:n}$. Such a direct
exponential enumeration is not feasible in practical settings. To address
these issues, this section will see the development of Alg. 1, which finds a
sequential $\pi$-backdoor admissible set $\bm{Z}_{1:n}$ with regard to actions
$\bm{X}$ in a causal diagram $\mathcal{G}$ in polynomial time, if such a set
exists.

Before delving into the details of Alg. 1, we describe a method intuitively
motivated by the “Nearest Separator" from [27] that can generate a backdoor
admissible set $\bm{Z}_{i}$ for a single independent action $X_{i}$ in the
presence of unobserved variables. While it does not solve the problem of
multiple actions due to the issues listed above, it is a building block for
Alg. 1.

Consider the Markov Boundary (minimal Markov Blanket, [16]) for a set of nodes
$\bm{O}^{X}\subseteq\bm{O}$, which is defined as the minimal set
$\bm{Z}\subset\bm{O}\setminus\bm{O}^{X}$ such that
$(\bm{O}^{X}\perp\\!\\!\\!\perp\bm{O}\setminus\bm{O}^{X}|\bm{Z})$. This
definition can be applied to graphs with latent variables, where it can be
constructed in terms of c-components:

######  Lemma 3.1.

Given $\bm{O}^{X}\subseteq\bm{O}$, the Markov Boundary of $\bm{O}^{X}$ in
$\bm{G}$ is
$\mathit{Pa}^{+}(\bm{C}(\mathit{Ch}^{+}(\bm{O}^{X})))\setminus\bm{O}^{X}$

If there is a set $\bm{Z}\subseteq\operatorname{before}(X_{i})$ that satisfies
the backdoor criterion for $X_{i}$ with respect to $Y$, then taking
$\mathcal{G}^{Y}$ as the ancestral graph of $Y$, the Markov Boundary
$\bm{Z}^{\prime}$ of $X_{i}$ in $\mathcal{G}^{Y}_{\underline{X_{i}}}$ has
$\bm{Z}^{\prime}\subseteq\operatorname{before}(X_{i})$, and also satisfies the
backdoor criterion in $\mathcal{G}$. The Markov Boundary can therefore be used
to generate a backdoor adjustment set wherever one exists.

A naïve algorithm that uses the Markov Boundary of $X_{i}\in\bm{X}$ in
$(\mathcal{G}^{\prime}_{i})^{Y}_{\underline{X_{i}}}$ as the corresponding
$\bm{Z}_{i}$, and returns a failure whenever
$\bm{Z}_{i}\notin\operatorname{before}(X_{i})$ for the sequential
$\pi$-backdoor is equivalent to the existing literature on finding backdoor-
admissible sets. It cannot create a valid sequential $\pi$-backdoor for Fig.
2(c), since $X_{2}$ would have $\bm{Z}_{2}=\\{W\\}$, but no adjustment set
exists for $X_{1}$ that d-separates it from $Y$ in the resulting
$\mathcal{G}^{\prime}_{1}$. We must take into account interactions between
actions encoded in $\mathcal{G}^{\prime}_{i}$.

We notice that an $X_{i}$ does not require a valid adjustment set if it is not
an ancestor of $Y$ in $\mathcal{G}^{\prime}_{i}$ (i.e. $X_{i}$ does not need
to satisfy (1) of Def. 2.3 if it can satisfy (2)). Furthermore, even if
$X_{i}$ is an ancestor of $Y$ in $\mathcal{G}^{\prime}_{i}$, and therefore
must satisfy condition (1) of Def. 2.3, any elements of its c-component that
are not ancestors of $Y$ in $\mathcal{G}^{\prime}_{i}$ won’t be part of
$(\mathcal{G}^{\prime}_{i})^{Y}$, and therefore don’t need to be conditioned.

It is therefore beneficial for an action $X_{j}$ to have a backdoor adjustment
set that maximizes the number of nodes that are not ancestors of $Y$ in
$\mathcal{G}^{\prime}_{j-1}$, so that actions $X_{i<j}$ can satisfy (2) of
Def. 2.3 if possible, and have the smallest possible c-components in
$(\mathcal{G}^{\prime}_{i})^{Y}$ (increasing likelihood that backdoor set
$\bm{Z}_{i}\subseteq\operatorname{before}(X_{i})$ exists if $X_{i}$ must
satisfy condition (1)).

Algorithm 1 Find largest valid $\bm{O}^{X}$ in ancestral graph of $Y$ given
$\mathcal{G}$, $\bm{X}$ and target $Y$

1:function HasValidAdjustment($\mathcal{G}$,$\bm{O}^{X}$,$O_{i}$,$X_{i}$)

2: $\bm{C}\leftarrow$ the c-component of $O_{i}$ in $\mathcal{G}^{Y}$

3: $\mathcal{G}_{\bm{C}}\leftarrow$ the subgraph of $\mathcal{G}^{Y}$
containing only $\mathit{Pa}^{+}(\bm{C})$ and intermediate latent variables

4: $\bm{O}^{C}\leftarrow\bm{C}\setminus(\bm{O}^{X}\cup\\{O_{i}\\})$ (elements
of c-component that might be ancestors of $Y$ in $\mathcal{G}^{\prime}_{i}$)

5: return
$\left(O_{i}\perp\\!\\!\\!\perp\bm{O}^{C}|(\bm{O}^{C}\cap\operatorname{before}(X_{i}))\right)$
in $\mathcal{G}_{\bm{C}}$

6:function FindOx($\mathcal{G}$,$\bm{X}$,$Y$)

7: $\mathscr{O}^{X}\leftarrow\text{empty map from elements of $\bm{O}$ to
elements of $\bm{X}$}$

8: do

9: for $O_{i}\in\bm{O}$ of $\mathcal{G}^{Y}$ (ancestral graph of $Y$) in
reverse temporal order do

10: if $|\mathit{ch}^{+}(O_{i})|>0$ and $\mathit{ch}^{+}(O_{i})\subseteq
keys(\mathscr{O}^{X})$ then

11: $X_{i}\leftarrow$ earliest element of
$\mathscr{O}^{X}[\mathit{ch}^{+}(O_{i})]$ in temporal order

12: if
HasValidAdjustment($\mathcal{G}$,$keys(\mathscr{O}^{X})$,$O_{i}$,$X_{i}$) then

13: $\mathscr{O}^{X}[O_{i}]\leftarrow X_{i}$

14: else if $O_{i}\in\bm{X}$ and
HasValidAdjustment($\mathcal{G}$,$keys(\mathscr{O}^{X})$,$O_{i}$,$O_{i}$) then

15: $\mathscr{O}^{X}[O_{i}]\leftarrow O_{i}$

16: while $|\mathscr{O}^{X}|$ changed in most recent pass

17: return $keys(\mathscr{O}^{X})$

To demonstrate this intuition, we once again look at Fig. 2(c), focusing only
on action $X_{2}$. If we were to use $\\{W\\}$ as $\bm{Z}_{2}$, we still have
the same set of ancestors of $Y$ in $\mathcal{G}^{\prime}_{1}$. If we switch
to $\\{X_{1}\\}$, then $W$ would no longer be an ancestor of $Y$ in
$\mathcal{G}^{\prime}_{1}$ \- meaning that $X_{1}$ is better as a backdoor
adjustment set for $X_{2}$ than $\\{W\\}$ if we only know that $X_{2}$ is an
action (i.e. $W$ would directly satisfy (2) of Def. 2.3 if it were the other
action). Finally, using $\\{Z\\}$ as $\bm{Z}_{2}$ makes both $X_{1}$ and $W$
no longer ancestors of $Y$ in $\mathcal{G}^{\prime}_{1}$, meaning that it is
the best option for the adjustment set $\bm{Z}_{2}$.

FindOx in Alg. 1 employs the above ideas to iteratively grow a set
$\bm{O}^{X}\subseteq\bm{O}$ of ancestors of $\bm{X}$ (and including $\bm{X}$)
in $\mathcal{G}^{Y}$ whose elements (possibly excluding $\bm{X}$) will not be
ancestors of $Y$ once the actions in their descendants are taken. That is, an
element $O_{i}\in\bm{O}^{X}$ where $\mathit{ch}^{+}(O_{i})\subset\bm{O}^{X}$
is not present in $(\mathcal{G}^{\prime}_{i})^{Y}$ for all actions $X_{i}$
that come before it in temporal order. Combined with the Markov Boundary,
FindOx can be used to generate sequential $\pi$-backdoors.

We exemplify the use of Alg. 1 through Fig. 2(c). $\mathscr{O}^{X}$ represents
a map of observed variables which are not ancestors of $Y$ in
$\mathcal{G}^{\prime}_{i<j}$ to the earliest action $X_{j}$ in their
descendants. The keys of $\mathscr{O}^{X}$ will be the set $\bm{O}^{X}$.
Considering the temporal order $\\{X_{1},Z,W,X_{2},Y\\}$, the algorithm starts
from the last node, $Y$, which has no children and is not an element of
$\bm{X}$, so is not added to $\mathscr{O}^{X}$. It then carries on to $X_{2}$,
which is checked for the existence of a valid backdoor adjustment set. Here,
the subgraph of the c-component of $X_{2}$ and its parents
(HasValidAdjustment) is simply $W$$\rightarrow$ $X_{2}$, meaning that we can
condition on $W$ to make $X_{2}$ independent of all other observed variables,
including $Y$, in $\mathcal{G}_{\underline{X_{2}}}$ ($W$ is a Markov Boundary
for $X_{2}$ in $\mathcal{G}_{\underline{X_{2}}}$). The algorithm therefore
sets $\mathscr{O}^{X}=\\{X_{2}:X_{2}\\}$, because $X_{2}$ is an action with a
valid adjustment set. Notice that if the algorithm returned at this point with
$\bm{O}^{X}=\\{X_{2}\\}$, the Markov Boundary of $\bm{O}^{X}$ in
$\mathcal{G}_{\underline{X_{2}}}$ is $W$, and corresponds to a sequential
$\pi$-backdoor for the single action $X_{2}$ (ignoring $X_{1}$), with policy
$\pi(X_{2}|W)=P(X_{2}|W)$.

Next, $W$ has $X_{2}$ as its only child, which itself maps to $X_{2}$ in
$\mathscr{O}^{X}$. The subgraph of $W$’s c-component and its parents is
$X_{1}$$\rightarrow$ $W$, giving
$(W\perp\\!\\!\\!\perp\bm{O}|X_{1})_{\mathcal{G}_{\underline{W}}}$, and
$\\{X_{1}\\}\subseteq\operatorname{before}(X_{2})$, allowing us to conclude
that there is a backdoor admissible set for $X_{2}$ where $W$ is no longer an
ancestor of $Y$. We set $\mathscr{O}^{X}=\\{X_{2}:X_{2},W:X_{2}\\}$, and
indeed with $\bm{O}^{X}=\\{X_{2},W\\}$, the Markov Boundary of $\bm{O}^{X}$ in
$\mathcal{G}_{\underline{X_{2}}}$ is $X_{1}$, and is once again a valid
sequential $\pi$-backdoor for the single action $X_{2}$ (ignoring $X_{1}$),
with policy $\pi(X_{2}|X_{1})=P(X_{2}|X_{1})$. The $W$ in $\bm{O}^{X}$ was
correctly labeled as not being an ancestor of $Y$ after action $X_{2}$ is
taken.

Since $Z$ doesn’t have its children in the keys of $\mathscr{O}^{X}$, and is
not an element of $\bm{X}$, it is skipped, leaving only $X_{1}$. $X_{1}$’s
children ($W$) are in $\mathscr{O}^{X}$, we check conditioning using $X_{2}$
instead of $X_{1}$ (i.e. we check if $X_{1}$ can satisfy (2) of Def. 2.3, and
not be an ancestor of $Y$ in $\mathcal{G}^{\prime}_{1}$). This time, we have
$X_{1}$$\leftrightarrow$ $Z$ as the c-component subgraph, and $Z$ comes before
$X_{2}$, satisfying the check ($X_{1}\perp\\!\\!\\!\perp Z|Z$) in
HasValidAdjustment, resulting in
$\mathscr{O}^{X}=\\{X_{2}:X_{2},W:X_{2},X_{1}:X_{2}\\}$, and
$\bm{O}^{X}=\\{X_{2},W,X_{1}\\}$. Indeed, the Markov Boundary of $\bm{O}^{X}$
in $\mathcal{G}_{\underline{X_{2}}}$ is $\\{Z\\}$, and we can construct a
valid sequential $\pi$-backdoor by using $\bm{Z}_{1}=\\{\\}$ and
$\bm{Z}_{2}=\\{Z\\}$, where $X_{1}$ is no longer an ancestor of $Y$ in
$\mathcal{G}^{\prime}_{1}$! In this case, we call $X_{2}$ a “boundary action",
because it is an ancestor of $Y$ in $\mathcal{G}^{\prime}_{2}$. On the other
hand, $X_{1}$ is not a boundary action, because it is not an ancestor of $Y$
in $\mathcal{G}^{\prime}_{1}$.

######  Definition 3.1.

The set $\bm{X}^{B}\subseteq\bm{X}$ called the “boundary actions" for
$\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$ are all elements
$X_{i}\in\bm{X}\cap\bm{O}^{X}$ where
$\mathit{ch}^{+}(X_{i})\not\subseteq\bm{O}^{X}$.

Alg. 1 is general: the set $\bm{O}^{X}$ returned by FindOx can always be used
in conjunction with its Markov Boundary to construct a sequential
$\pi$-backdoor if one exists:

######  Lemma 3.2.

Let $\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$, and
$\bm{X}^{\prime}:=\bm{O}^{X}\cap\bm{X}$. Taking $\bm{Z}$ as the Markov
Boundary of $\bm{O}^{X}$ in $\mathcal{G}^{Y}_{\underline{X^{\prime}}}$ and
$\bm{X}^{B}$ as the boundary actions of $\bm{O}^{X}$, the sets
$\bm{Z}_{i}=(\bm{Z}\cup\bm{X}^{B})\cap\operatorname{before}(X^{\prime}_{i})$
for each $X^{\prime}_{i}\in\bm{X}^{\prime}$ are a valid sequential
$\pi$-backdoor for $(\mathcal{G},\bm{X}^{\prime},Y)$.

######  Lemma 3.3.

Let $\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$. Suppose that there
exists a sequential $\pi$-backdoor for $\bm{X}"\subseteq\bm{X}$. Then
$\bm{X}"\subseteq\bm{O}^{X}$.

Combined together, Lems. 3.3 and 3.2 show that FindOx finds the maximal subset
of $\bm{X}$ where a sequential $\pi$-backdoor exists, and the adjustment sets
$\bm{Z}_{1:n}$ can be constructed using the subset of a Markov Boundary over
$\bm{O}^{X}$ that comes before each corresponding action $X_{i}$ (Lem. 3.2).
FindOx is therefore both necessary and sufficient for generating a sequential
$\pi$-backdoor:

######  Theorem 3.1.

Let $\bm{O}^{X}$ be the output of $\textsc{FindOx}(\mathcal{G},\bm{X},Y)$. A
sequential $\pi$-backdoor exists for $(\mathcal{G},\bm{X},Y)$ if and only if
$\bm{X}\subseteq\bm{O}^{X}$.

##  4 Necessity of Sequential $\pi$-Backdoor for Imitation

In this section, we show that the sequential $\pi$-backdoor is necessary for
imitability, meaning that the sequential $\pi$-backdoor is complete.

A given imitation problem can have multiple possible conditioning sets
satisfying the sequential $\pi$-backdoor, and a violation of the criterion for
one set does not preclude the existence of another that satisfies the
criterion. To avoid this issue, we will use the output of Algorithm FindOx,
which returns a unique set $\bm{O}^{X}$ for each problem:

######  Lemma 4.1.

Let $\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$. Suppose $\exists
X_{i}\in\bm{X}$ s.t. $X_{i}\in\bm{X}\setminus\bm{O}^{X}$. Then $\bm{X}$ is not
imitable with respect to $Y$ in $\mathcal{G}$.

Our next proposition establishes the necessity of the sequential
$\pi$-backdoor criterion for the imitability of the expert’s performance (Def.
2.1), which follows immediately from Lems. 4.1 and 3.1.

######  Theorem 4.1.

If there do not exist adjustment sets satisfying the sequential $\pi$-backdoor
criterion for $(\mathcal{G},\bm{X},Y)$, then $\bm{X}$ is not imitable with
respect to $Y$ in $\mathcal{G}$.

The proof of Lem. 4.1 relies on the construction of an adversarial SCM for
which $Y$ can detect the imitator’s lack of access to the latent variables.
For example, in Fig. 2(a), $Z$ can carry information about the latent variable
$U$ to $Y$, and is only determined after the decision for the value of $X$ is
made. Setting $U\sim Bern(0.5),X:=U,Z:=U,Y:=X\oplus Z$ leaves the imitator
with a performance of ${\rm I\kern-3.00003ptE}[\hat{Y}]=0.5$, while the expert
can get perfect performance (${\rm I\kern-3.00003ptE}[Y]=1$).

Another example with similar mechanics can be seen in Fig. 2(c). If the
variables are determined in the order $(X_{1},W,X_{2},Z,Y)$, then the sequence
of actions is not imitable, since $Z$ can transfer information about the
latent variable $U$ to $Y$, while $X_{2}$ has no way of gaining information
about $U$, because the action at $X$ needed to be taken without context.

Finally, observe Fig. 2(d). If $Z$ is determined after $X_{1}$, the imitator
must guess a value for $X_{1}$ without this side information, which is then
combined with $U_{2}$ at $W$. An adversary can exploit this to construct a
distribution where guessing wrong can be detected at $Y$ as follows:
$U_{1}\sim Bern(0.5)$, $Z,X:=U_{1}$, $U_{2}\sim(Bern(0.5),Bern(0.5))$ (that
is, $U_{2}$ is a tuple of two binary variables, or a single variable with a
uniform domain of $0,1,2,3$). Then setting $W=U_{2}[Z]$ ($[]$ represents array
access, meaning first element of tuple if $Z=0$ and second if $Z=1$), and
$X_{2}:=W$, $Y:=(U_{2}[X_{1}]==X_{2})$ gives ${\rm I\kern-3.00003ptE}[Y]=1$
only if $\pi_{1}$ guesses the value of $U_{1}$, meaning that the imitator can
never achieve the expert’s performance. This construction also demonstrates
non-imitability when $X_{1}$ and $Z$ are switched (i.e., Fig. 2(c) with
$W\leftrightarrow Y$ added, and $X_{1}$ coming before $Z$ in temporal order).

Due to these results, after running Alg. 1 on the domain’s causal structure,
the imitator gets two pieces of information:

  1. 1.

Is the problem imitable? In other words, is it possible to use only observable
context variables, and still get provably optimal imitation, despite the
expert and imitator having different information?

  2. 2.

If so, what context should be included in each action? Including/removing
certain observed covariates in an estimation procedure can lead to different
conclusions/actions, only one of which is correct (known as “Simpson’s
Paradox” in the statistics literature [17]). Furthermore, as demonstrated in
Fig. 2(c), when performing actions sequentially, some actions might not be
imitable themselves ($X_{1}$ if $Z$ after $X_{1}$), which leads to bias in
observed descendants ($W$) - the correct context takes this into account,
using only covariates known not to be affected by incorrectly guessed actions.

Finally, the obtained context $\bm{Z}_{i}$ for every action $X_{i}$ could be
be used as input to existing algorithms for behavioral cloning, giving an
imitating policy with an unbiased result.

##  5 Simulations

We performed 2 experiments (for full details, refer to [9, Appendix B]),
comparing the performance of 4 separate approaches to determining which
variables to include in an imitating policy:

  1. 1.

All Observed (AO) \- Take into account all variables available to the imitator
at the time of each action. This is the approach most commonly used in the
literature.

  2. 2.

Observed Parents (OP) \- The expert used a set of variables to take an action
- use the subset of these that are available to the imitator.

  3. 3.

$\pi$-Backdoor \- In certain cases, each individual action can be imitated
independently, so the individual single-action covariate sets are used.

  4. 4.

Sequential $\pi$-Backdoor (ours) \- The method developed in this paper, which
takes into account multiple actions in sequence.

Figure 4: Results of applying supervised learning techniques to continuous data with different sets of variables as input at each action. OPT is the ground truth expert’s performance, S$\pi$BD represents our method, AO is all observed, and OP represents observed parents. # | Structure | Order | Seq. $\pi$-Backdoor |  $\pi$-Backdoor | Observed Parents | All Observed
---|---|---|---|---|---|---
1 |  $X_{1}$$X_{2}$$Y$$Z$ |  $\begin{gathered}Z,X_{1},\\\ X_{2},Y\\\ \end{gathered}$ | $0.04\pm 0.04\%$ | $0.04\pm 0.03\%$ | $0.05\pm 0.04\%$ | $\bm{0.13\pm 0.18\%}$
2 |  $X_{1}$$X_{2}$$Y$$Z$ $U_{1}$ |  $\begin{gathered}\bm{Z,X_{1},}\\\ \bm{X_{2},Y}\end{gathered}$ | $0.05\pm 0.03\%$ | $0.05\pm 0.03\%$ | $\bm{0.20\pm 0.25\%}$ | $0.05\pm 0.03\%$
3 |  $X_{1}$$X_{2}$$Y$$Z$ $U_{1}$ |  $\begin{gathered}\bm{X_{1},Z,}\\\ \bm{X_{2},Y}\end{gathered}$ | $0.04\pm 0.03\%$ | Not Imitable | $\bm{0.27\pm 0.40\%}$ | $\bm{0.26\pm 0.39\%}$
4 |  $X_{2}$$X_{1}$$Z$$Y$$U_{1}$ $U_{2}$ |  $\begin{gathered}X_{1},Z,\\\ X_{2},Y\end{gathered}$ | Not Imitable | Not Imitable | $\bm{0.19\pm 0.29\%}$ | $\bm{0.19\pm 0.29\%}$
Table 1: Values of $|{\rm I\kern-2.70003ptE}[Y]-{\rm
I\kern-2.70003ptE}[\hat{Y}]|$ from behavioral cloning using different contexts
in randomly sampled models consistent with each causal graph. Cases with
incorrect imitation are shown in red.

The first simulation consists of running behavioral cloning on randomly
sampled distributions consistent with a series of causal graphs designed to
showcase aspects of our method. For each causal graph, 10,000 random discrete
causal models were sampled, representing the environment as well as expert
performance, and then the expert’s policy $\bm{X}$ was replaced with imitating
policies approximating $\pi(X_{i})=P(X_{i}|ctx(X_{i}))$, with context $ctx$
determined by each of the 4 tested methods in turn. Our results are shown in
Table 1, with causal graphs shown in the first column, temporal ordering of
variables in the second column, and absolute distance between expert and
imitator for the 4 methods in the remaining columns.

In the first row, including $Z$ when developing a policy for $\bm{X}$ leads to
a biased answer, which makes the average error of using all observed
covariates (red) larger than just the sampling fluctuations present in the
other columns. Similarly, $Z$ needs to be taken into account in row 2, but it
is not explicitly used by $\bm{X}$, so a method relying only on observed
parents leads to bias here. In the next row, $Z$ is not observed at the time
of action $X_{1}$, making the $\pi$-backdoor incorrectly claim non-
imitability. Our method recognizes that $X_{2}$’s policy can fix the error
made at $X_{1}$, and is the only method that leads to an unbiased result.
Finally, in the 4th row, the non-causal approaches have no way to determine
non-imitability, and return biased results in all such cases.

The second simulation used a synthetic, adversarial causal model, enriched
with continuous data from the HighD dataset [8] altered to conform to the
causal model, to demonstrate that different covariate sets can lead to
significantly different imitation performance. A neural network was trained
for each action-policy pair using standard supervised learning approaches,
leading to the results shown in Fig. 4. The causal structure was not imitable
from the single-action setting, so the remaining 3 methods were compared to
the optimal reward, showing that our method approaches the performance of the
expert, whereas non-causal methods lead to biased results. Full details of
model construction, including the full causal graph are given in [9, Appendix
B]

##  6 Limitations & Societal Impact

There are two main limitations to our approach: (1) Our method focuses on the
causal diagram, requiring the imitator to provide the causal structure of its
environment. This is a fundamental requirement: any agent wishing to operate
in environments with latent variables must somehow encode the additional
knowledge required to make such inferences from observations. (2) Our
criterion only takes into consideration the causal structure, and not the
associated data $P(\bm{o})$. Data-dependent methods can be computationally
intensive, often requiring density estimation. If our approach returns
“imitable", then the resulting policies are guaranteed to give perfect
imitation, without needing to process large datasets to determine imitability.

Finally, advances in technology towards improving imitation can easily be
transferred to methods used for impersonation - our method provides conditions
under which an imposter (imitator) can fool a target ($Y$) into believing they
are interacting with a known party (expert). Our method shows when it is
provably impossible to detect an impersonation attack. On the other hand, our
results can be used to ensure that the causal structure of a domain cannot be
imitated, helping mitigate such issues.

##  7 Conclusion

Great care needs to be taken in choosing which covariates to include when
determining a policy for imitating an expert demonstrator when expert and
imitator have different views of the world. The wrong set of variables can
lead to biased, or even outright incorrect predictions. Our work provides
general and complete results for the graphical conditions under which
behavioral cloning is possible, and provides an agent with the tools needed to
determine the variables relevant to its policy.

## Funding Transparency

The team is supported in part by funding from the NSF, Amazon, JP Morgan, and
The Alfred P. Sloan Foundation, as well as grants from NSF IIS-1704352 and
IIS-1750807 (CAREER).

## References

  * [1] P. Abbeel and A. Y. Ng.  Apprenticeship learning via inverse reinforcement learning.  In Proceedings of the twenty-first international conference on Machine learning, page 1, 2004.
  * [2] B. D. Argall, S. Chernova, M. Veloso, and B. Browning.  A survey of robot learning from demonstration.  Robotics and autonomous systems, 57(5):469–483, 2009.
  * [3] A. Billard, S. Calinon, R. Dillmann, and S. Schaal.  Survey: Robot programming by demonstration.  Handbook of robotics, 59(BOOK_CHAP), 2008.
  * [4] P. de Haan, D. Jayaraman, and S. Levine.  Causal confusion in imitation learning.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [5] J. Etesami and P. Geiger.  Causal transfer for imitation learning and decision making under sensor-shift.  In Proceedings of the 34th AAAI Conference on Artificial Intelligence, New York, NY, 2020. AAAI Press.
  * [6] A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne.  Imitation learning: A survey of learning methods.  ACM Computing Surveys (CSUR), 50(2):1–35, 2017.
  * [7] D. Koller and N. Friedman.  Probabilistic Graphical Models: Principles and Techniques.  MIT press, 2009.
  * [8] R. Krajewski, J. Bock, L. Kloeker, and L. Eckstein.  The highd dataset: A drone dataset of naturalistic vehicle trajectories on german highways for validation of highly automated driving systems.  In 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pages 2118–2125, 2018.
  * [9] D. Kumor, J. Zhang, and E. Bareinboim.  Sequential causal imitation learning with unobserved confounders.  Technical Report R-76, Causal AI Lab, Columbia University., 2021.
  * [10] J. Mahler and K. Goldberg.  Learning deep policies for robot bin picking by simulating robust grasping sequences.  In Conference on robot learning, pages 515–524, 2017.
  * [11] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller.  Playing Atari with Deep Reinforcement Learning.  arXiv:1312.5602 [cs], Dec. 2013.
  * [12] U. Muller, J. Ben, E. Cosatto, B. Flepp, and Y. L. Cun.  Off-road obstacle avoidance through end-to-end learning.  In Advances in neural information processing systems, pages 739–746, 2006.
  * [13] K. Mülling, J. Kober, O. Kroemer, and J. Peters.  Learning to select and generalize striking movements in robot table tennis.  The International Journal of Robotics Research, 32(3):263–279, 2013\.
  * [14] A. Y. Ng, S. J. Russell, et al.  Algorithms for inverse reinforcement learning.  In Icml, volume 1, pages 663–670, 2000.
  * [15] T. Osa, J. Pajarinen, G. Neumann, J. A. Bagnell, P. Abbeel, J. Peters, et al.  An algorithmic perspective on imitation learning.  Foundations and Trends in Robotics, 7(1-2):1–179, 2018.
  * [16] J. Pearl.  Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.  Morgan Kaufmann, 1988.
  * [17] J. Pearl.  Causality: Models, Reasoning and Inference.  2000\.
  * [18] J. Pearl and J. M. Robins.  Probabilistic Evaluation of Sequential Plans from Causal Models with Hidden Variables.  arXiv:1302.4977 [cs], 1995.
  * [19] D. A. Pomerleau.  Alvinn: An autonomous land vehicle in a neural network.  In Advances in neural information processing systems, pages 305–313, 1989.
  * [20] G. Rizzolatti and L. Craighero.  The mirror-neuron system.  Annu. Rev. Neurosci., 27:169–192, 2004.
  * [21] R. S. Sutton, A. G. Barto, et al.  Reinforcement Learning: An Introduction.  MIT press, 1998.
  * [22] U. Syed and R. E. Schapire.  A game-theoretic approach to apprenticeship learning.  In Advances in neural information processing systems, pages 1449–1456, 2008.
  * [23] J. Tian.  Studies in Causal Reasoning and Learning.  PhD thesis, Computer Science Department, University of California, Los Angeles, CA, November 2002.
  * [24] J. Tian and A. Paz.  Finding Minimal D-separators.  page 15, 1998.
  * [25] J. Tian and J. Pearl.  A General Identification Condition for Causal Effects.  page 7, 2002.
  * [26] B. van der Zander and M. Liśkiewicz.  Finding minimal d-separators in linear time and applications.  In Uncertainty in Artificial Intelligence, pages 637–647. PMLR, 2020.
  * [27] B. Van der Zander, J. Textor, and M. Liskiewicz.  Efficiently finding conditional instruments for causal inference.  In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
  * [28] B. Widrow.  Pattern-recognizing control systems.  Compurter and Information Sciences, 1964.
  * [29] J. Zhang, D. Kumor, and E. Bareinboim.  Causal Imitation Learning with Unobserved Confounders.  page 27, 2020.
  * [30] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey.  Maximum entropy inverse reinforcement learning.  In Aaai, volume 8, pages 1433–1438. Chicago, IL, USA, 2008.