TECHNICAL REPORT
R-76
First version: Jun 2021
Last version: Nov 2021

Sequential Causal Imitation Learning with
Unobserved Confounders
Daniel Kumor
Purdue University
dkumor@purdue.edu

Junzhe Zhang
Columbia University
junzhez@cs.columbia.edu

Elias Bareinboim
Columbia University
eb@cs.columbia.edu

Abstract“Monkey see monkey do" is an age-old adage, referring to naïve imitation without adeep 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 (S EE), attempting to reproduce the demonstrator’s behavior (D O) canlead to poor outcomes. Imitation learning in the presence of a mismatch between
demonstrator and imitator has been studied in the literature under the rubric ofcausal 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 andsufficient 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 andcorroborate 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 (Sutton et al., 1998; Mnih et al., 2013). 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 usedwith great success in many learning machines, including humans, is exploiting observations of otheragents in the environment (Rizzolatti & Craighero, 2004; Hussein et al., 2017).
Learning to act by observing other agents offers a data multiplier, allowing agents to take into accountothers’ experiences. Even when the precise loss function is unknown (what exactly goes into beinga good driver?), the agent can attempt to learn from “experts”, namely agents which are known togain an acceptable reward at the target task. This approach has been studied under the umbrella ofimitation learning (Argall et al., 2009; Billard et al., 2008; Hussein et al., 2017; Osa et al., 2018).
Several methods have been proposed, including inverse reinforcement learning (Ng et al., 2000;
Abbeel & Ng, 2004; Syed & Schapire, 2008; Ziebart et al., 2008) and behavior cloning (Widrow,
1964; Pomerleau, 1989; Muller et al., 2006; Mülling et al., 2013; Mahler & Goldberg, 2017). 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 humandemonstrators are able to exploit this data, especially in dangerous situations (car horns, screeching
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

F

B

S

F

H

B

S

Z

H

X

Y

(a)

X

U1

X1

Y

X2

Z

Y

X2

Y

U2

U

(b)

X1

(c)

(d)

Figure 1: (a, b) represents a simplified view of a driver X and surrounding cars F , B, S. (c) is
imitable with policies π1 (X1 ) = P (X1 ) and π2 (X2 |Z) = P (X2 |Z), but in (d) X1 , X2 is notimitable, despite there being a valid sequential backdoor.

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. 1a,
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 avariable Y (red), which is unobserved (dashed node). Since our dataset only contains visual data, carhorns H remain unobserved to the learning agent (i.e., the imitator). Despite not being able to hearcar horns, the learner from Fig. 1a had a full view of the car’s surroundings, including cars behind andto 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 ¬X ⊕ F ⊕ B ⊕ S; ⊕represents the exclusive-or operator. The human driver decides the action X ← H where values ofhorn H is given by F ⊕ B ⊕ S. Preliminary analysis reveals that the learner could perfectly mimic
the demonstrator’s decision-making process using an imitating policy X ← F ⊕ B ⊕ S. On theother hand, if the driving system does not have side cameras, the side view S becomes latent; see
Fig. 1b. The learner’s reward IE[Y |do(π)] is equal to 0.5 for any policy π(x|f , b), which is far fromthe optimal demonstrator’s performance, IE[Y ] = 1.
Based on these examples, there arises the question of determining precise conditions under which anagent can account for the lack of knowledge or observations available to the expert, and how thisknowledge should be combined to generate an optimal imitating policy, giving identical performanceas the expert on measure Y . These questions have been recently investigated in the context of
causal imitation learning (Zhang et al., 2020), where a complete graphical condition and algorithm
were developed for determining imitability in the single-stage decision-making setting with partiallyobservable models (i.e., in non-Markovian settings). Other structural assumptions, such as linearity(Etesami & Geiger, 2020), were also explored in the literature, but were still limited to a single
action. Finally, de Haan et al. (2019) explore the case when expert and imitator can observe thesame contexts, but the causal diagram is not available. Despite this progress, it is still unclear how tosystematically 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. 1c and 1d).
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 insequential 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 ademonstrator has access to latent variables through simulations. Due to space constraints, proofs areprovided in the complete technical report (Kumor et al., 2021).
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 (Z = {Z1 , ..., Zn }, z = {z1 ∼ Z1 , ..., zn ∼ Zn }). |Z|
represents a set’s cardinality. The joint distribution over variables Z is denoted by P (Z). To simplify
notation, we consistently use the shorthand P (zi ) to represent probabilities P (Zi = zi ).
2

Z

Y

(a)

X2

Y

U1

Z

X1

W

1

X1

U

U

U

X

X2

(c)

(b)

Y

Z

X1
U2

X2

W

Y

(d)

Figure 2: Despite there being no latent path between Y and any X, the query in (a) is not imitable,
but the query in (b) is imitable. While (c) is imitable if Z comes before X2 in temporal order, thequery in (d) is imitable only if Z comes before X1 .
The basic semantic framework of our analysis rests on structural causal models (SCMs) (Pearl,
2000, Ch. 7). An SCM M is a tuple hU , V , F , P (u)i with V the set of endogenous, and U
exogenous variables. F is a set of structural functions s.t. for fV ∈ F , V ← fV (pa V , uV ),with PAV ⊆ V , UV ⊆ U . Values of U are drawn from an exogenous distribution P (u), inducing
distribution P (V ) over the endogenous V . Since the learner can observe only a subset of endogenous
variables, we split V into O ⊆ V (observed) and L = V \ O (latent) sets of variables. The marginal
P (O) is thus referred to as the observational distribution.
Each SCM M is associated with a causal diagram G where (e.g., see Fig. 2d) solid nodes represent
observed variables O, dashed nodes represent latent variables L, and arrows represent the argumentspa(V ) of each functional relationship fV . Exogenous variables U are not explicitly shown; a bidirected arrow between nodes Vi and Vj indicates the presence of an unobserved confounder (UC)affecting both Vi and Vj . We will use standard conventions to represent graphical relationships suchas parents, children, descendants, and ancestors. For example, the set of parent nodes of X in G isdenoted by pa(X)G = ∪X∈X pa(X)G . ch, de and an are similarly defined. Capitalized versions
Pa, Ch, De, An include the argument as well, e.g. De(X)G = de(X)G ∪ X. An observed variable
Vi ∈ O is an effective parent of Vj ∈ V if there is a directed path from Vi to Vj in G such that every
internal node on the path is in L. We define pa + (S) as the set of effective parents of variables in S,
excluding S itself, and Pa + (S) as S ∪ pa + (S). Other relations, like ch+ (S) are defined similarly.
A path from a node X to a node Y in G is said to be “active" conditioned on a (possibly empty)
set W if there is a collider at A along the path (→ A ←) only if A ∈ An(W ), and the path does
not otherwise contain vertices from W (d-separation, Koller & Friedman (2009)). X and Y are
independent conditioned on W (X ⊥⊥ Y |W )G if there are no active paths between any X ∈ X
and Y ∈ Y . For a subset X ⊆ V , the subgraph obtained from G with edges outgoing from X /incoming into X removed is written GX /GX respectively. Finally, we utilize a grouping of observed
nodes, called confounded components (c-components, Tian & Pearl (2002); Tian (2002)).
Definition 1.1. For a causal diagram G, let N be a set of unobserved variables in L ∪ U . A set
C ⊆ Ch(N ) ∩ O is a c-component if for any pair Ui , Uj ∈ N , there exists a path between Ui and
Uj in G such that every observed node Vk ∈ O on the path is a collider (i.e., → Vk ←).
C-components correspond to observed variables whose values are affected by related sets of unobserved common causes, such that if A, B ∈ C, (A 6⊥⊥ B|O \ {A, B}). In particular, we focus on
maximal c-components C , where there doesn’t exist c-component C 0 s.t. C ⊂ C 0 . The collectionof maximal c-components forms a partition C1 , . . . , Cm over observed variables O. For any set
S ⊆ O, let C(S) be the union of c-components Ci that contain variables in S. For instance, forvariable Z in Fig. 1d, the c-component C({Z}) = {Z, X1 }.

2

Causal Sequential Imitation Learning

We are interested in learning a policy over a series of actions X ⊆ O so that an imitator gets averagereward Y ∈ V identical to that of an expert demonstrator. More specifically, let variables in X
be ordered by X1 , . . . , Xn , n = |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 Xi ∈ X. To encode
the ordering of observations and actions in time, we fix a topological ordering on the variables of G,
which we call the “temporal ordering”. We define functions before(Xi ) and after(Xi ) to represent
nodes that come before/after an action Xi ∈ X following the ordering, excluding Xi itself. A policy
π on actions X is a sequence of decision rules {π1 , . . . , πn } where each πi (Xi |Zi ) is a function
3

mapping from domains of covariates Zi ⊆ before(Xi ) to the domain of action Xi . The imitator
following a policy π replacing the demonstrator in an environment is encoded by replacing theexpert’s original policy in the SCM M with π, which gives the results of the imitator’s actions as
P (V |do(π)). Our goal is to learn an imitating policy π such that the induced distribution P (Y |do(π))
perfectly matches the original expert’s performance P (Y ). Formally
Definition 2.1. (Zhang et al., 2020) Given a causal diagram G, Y ⊆ V is said to be imitable withrespect to actions X ⊆ O in G if there exists π ∈ Π uniquely discernible from the observational
distribution P (O) such that for all possible SCMs M compatible with G, P (Y )M = P (Y |do(π))M .
In other words, the expert’s performance on reward Y is imitable if any set of SCMs must share thesame imitating policy π ∈ Π whenever they generate the same causal diagram G and the observational
distribution P (O). Henceforth, we will consistently refer to Def. 2.1 as the fundamental problemof causal imitation learning. For single stage decision-making problems (X = {X}), Zhang et al.
(2020) demonstrated imitability for reward Y if and only if there exists a set Z ⊆ before(X) suchthat (Y ⊥⊥ X|Z)GX , called the backdoor admissible set, (Pearl, 2000, Def. 3.3.1) (Z = {F , B, S}
in Fig. 1a). It is verifiable that an imitating policy is given by π(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 surmisethat a version of the criterion generalized to multiple interventions might likewise solve the imitability
problem in the general case (|X| > 1). Next we show that this is not the case. Let X1:i stand fora sequence of variables {X1 , . . . , Xi }; X1:i = ∅ if i < 1. Pearl & Robins (1995) generalized the
backdoor criterion to the sequential decision-making setting as follows:
Definition 2.2. (Pearl & Robins, 1995) Given a causal diagram G, a set of action variables X, andtarget node Y , sets Z1 ⊆ before(X1 ), . . . , Zn ⊆ before(Xn ) satisfy the sequential backdoor for(G, X, Y ) if for each Xi ∈ X such that (Y ⊥⊥ Xi |X1:i−1 , Z1:i )GX X
.
i

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 G described in Fig. 1d. In this case, Z1 = {}, Z2 = {Z}, {(X1 , Z1 ), (X2 , Z2 )} is asequential backdoor set for (G, {X1 , X2 }, Y ), but there are distributions for which no agent can
imitate the demonstrator’s performance (Y ) without knowledge of either the latent U1 or U2 . To
witness, suppose that the adversary sets up an SCM with binary variables as follows: U1 , U2 ∼Bern(0.5), with X1 := U1 , Z := U1 ⊕ U2 , X2 := Z and Y = ¬(X1 ⊕ X2 ⊕ U2 ), with ⊕ as abinary XOR. The fact that U ⊕ U = 0 is exploited to generate a chain where each latent variableappears exactly twice in Y , making Y = ¬(U1 ⊕ (U1 ⊕ U2 ) ⊕ U2 ) = 1. On the other hand, whenimitating, X1 can no longer base its value on U1 , making the imitated Ŷ = ¬(X̂1 ⊕ X̂2 ⊕ U2 ). The
imitator can do no better than IE[Ŷ ] = 0.5! We refer readers to (Kumor et al., 2021, 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 Z1 ⊆before(X1 ), . . . , Zn ⊆ before(Xn ), let Gi0 , i = 1, . . . , n, be the manipulated graph obtained froma causal diagram G by first (1) removing all arrows coming into nodes in Xi+1:n ; and (2) addingarrows Zi+1 → Xi+1 , . . . , Zn → Xn . We can then define a sequential backdoor criterion for causal
imitation as follows:
Definition 2.3. Given a causal diagram G, a set of action variables X, and target node Y , sets
Z1 ⊆ before(X1 ), . . . , Zn ⊆ before(Xn ) satisfy the “sequential π-backdoor"1 for (G, X, Y ) if at
each Xi ∈ X, either (1) (Xi ⊥⊥ Y |Zi ) in (Gi0 )Xi , or (2) Xi ∈/ An(Y ) in Gi0 .
The first condition of Def. 2.3 is similar to the backdoor criterion where Zi is a set of variables that
effectively encodes all information relevant to imitating Xi with respect to Y . In other words, if thejoint P (Zi ∪ {Xi }) matches when both expert and imitator are acting, then an adversarial Y cannot
distinguish between the two. The critical modification of the original π-backdoor for the sequential
setting comes from the causal graph in which this check happens. Gi0 can be seen as G with all future1

The π in “π-backdoor” is part of the name, and does not refer to any specific policy.

4

Z

X2

U

U

U

X1

U1

Z

X1

X1

W

Y
U

(a)

U2

Y
X2

U

1

U

U

X1

X2

U

(b)

Y

Z

X2

W

Y

U

(c)

(d)

Figure 3: Examples of G10 . In Fig. 1c, we can have Z1 = ∅, Z2 = {Z}, so X2 has its parents cut,
and a new arrow added from Z to X2 (blue). The independence check (X1 ⊥⊥ Y |∅) is done ingraph (a) with edges outgoing from X1 removed (orange). In Fig. 2b, using Z1 = ∅, Z2 = {X1 },we first replace the parents of X2 with just X1 (b), and then remove both resulting outgoing edges
from X1 to check if (X1 ⊥⊥ Y ). On the other hand, in Fig. 2c, if Z2 = {Z}, we get (c), whichmeans Xi ∈/ An(Y ), passing condition 2 of Def. 2.3. Finally, in Fig. 2d, with Z2 = {W }, X1 must
condition on either Z or W to be independent of Y in (d) once the edge X1 → Y is removed.
actions of the imitator already encoded in the graph. That is, when performing a check for Xi , it isdone with all actions after i being performed by the imitator rather than expert, with the associatedparents of each future Xj>i replaced with their corresponding imitator’s conditioning set. Several
examples of Gi0 are shown in Fig. 3.
The second condition allows for the case where an action at Xi has no effect on the value of Y once
future actions are taken. Since Gi0 has modified parents for future Xj>i , the value of Xi might nolonger be relevant at all to Y , i.e. Y would get the same input distribution no matter what policy is
chosen for Xi . This allows Xi to fail condition (1), meaning that it is not imitable by itself, but stillbe part of an imitable set X, because future actions can shield Y from errors made at Xi .
The distinction between condition 1 and condition 2 is shown in Fig. 3c: in the original graph G
described in Fig. 2c, if Z comes after X1 , then there is no valid adjustment set that can d-separate X1
from Y . However, if the imitating policy for X2 uses Z instead of W or X1 (i.e. πX2 = P (X2 |Z)),
X1 will no longer be an ancestor of Y in G10 . In effect, the action made at X2 ignores the inevitable
mistakes made at X1 due to not having access to confounder U1 when taking the action.
Indeed, the sequential π-backdoor criterion can be seen as a recursively applying the single-action
π-backdoor. Starting from the last action Xk in temporal order, one can directly show that Y isimitable using a backdoor admissible set Zk (or Xk doesn’t affect Y by any causal path). Replacing
Xk in the SCM with this new imitating policy, the resulting SCM with graph G0k−1 has an identical
distribution over Y as G. The procedure can then be repeated for Xk−1 using G0k−1 as the starting
graph, and continued recursively, showing imitability for the full set:
Theorem 2.1. Given a causal diagram G, a set of action variables X, and target node Y , if there
exist sets Z1 , Z2 , ..., Zk that satisfy the sequential π-backdoor criterion with respect to (G, X, Y ),then Y is imitable with respect to X in G with policy π(Xi |Zi ) = P (Xi |Zi ) for each Xi ∈ X.
Thm. 2.1 establishes the sufficiency of the sequential π-backdoor for imitation learning. Consider
again the diagram in Fig. 2c. It is verifiable that covariate sets Z1 = {}, Z2 = {Z} are sequential
π-backdoor admissible. Thm. 2.1 implies that the imitating policy is given by π1 (X1 ) = P (X1 )and π2 (X2 |Z) = P (X2 |Z). Once π-backdoor admissible sets are obtained, the imitating policy canbe 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
π-backdoor is a method for choosing a set of covariates to use when performing imitation learning,which can be used instead of P a(Xi ) for each Xi ∈ X in the case when the imitator does not observe
certain elements of P a(X). With the covariates chosen using the sequential π-backdoor, one can use
domain-specific algorithms for computing an imitating policy based on the observational data.

3

Finding Sequential π-Backdoor Admissible Sets

At each Xi , the sequential π-backdoor criterion requires that Zi is a back-door adjustment set in
the manipulated graph Gi0 . There already exist efficient methods for finding adjustment sets in the5literature (Tian & Paz, 1998; van der Zander & Liśkiewicz, 2020), so if the adjustment were withreference to G, one could run these algorithms on each Xi independently to find each backdoor
admissible set Zi . However, each action Xi has its Zi in the manipulated graph Gi0 , which isdependent on the adjustment used for future actions Xi+1:n . This means that certain adjustment sets
Zj for Xj>i will make there not exist any Zi for Xi in Gi0 that satisfies the criterion! As an example,
in Fig. 2c, X2 can use any combination of Z, X1 , W as a valid adjustment set Z2 . However, if Z
comes after X1 in temporal order, only Z2 = {Z} leads to valid imitation over X = {X1 , X2 }.
The direct approach towards solving this problem would involve enumerating all possible backdoor
admissible sets Zi for each Xi , but there are both exponentially many backdoor admissible sets
Zi , and exponentially many combinations of sets over multiple Xi:n . Such a direct exponential
enumeration is not feasible in practical settings. To address these issues, this section will see thedevelopment of Alg. 1, which finds a sequential π-backdoor admissible set Z1:n with regard toactions X in a causal diagram 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 Van der Zander et al. (2015) that can generate a backdoor admissible set Zi for asingle independent action Xi in the presence of unobserved variables. While it does not solve theproblem of multiple actions due to the issues listed above, it is a building block for Alg. 1.
Consider the Markov Boundary (minimal Markov Blanket, Pearl (1988)) for a set of nodes O X ⊆ O,
which is defined as the minimal set Z ⊂ O \ O X such that (O X ⊥⊥ O \ O X |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 O X ⊆ O, the Markov Boundary of O X in G is Pa + (C(Ch + (O X ))) \ O X
If there is a set Z ⊆ before(Xi ) that satisfies the backdoor criterion for Xi with respect to Y , thenYtaking G Y as the ancestral graph of Y , the Markov Boundary Z 0 of Xi in GX
has Z 0 ⊆ before(Xi ),iand also satisfies the backdoor criterion in G (Lem. C.1). The Markov Boundary can therefore beused to generate a backdoor adjustment set wherever one exists.
A naïve algorithm that uses the Markov Boundary of Xi ∈ X in (Gi0 )YXi as the corresponding Zi ,and returns a failure whenever Zi ∈/ before(Xi ) for the sequential π-backdoor is equivalent to theexisting literature on finding backdoor-admissible sets. It cannot create a valid sequential π-backdoor
for Fig. 2c, since X2 would have Z2 = {W }, but no adjustment set exists for X1 that d-separates itfrom Y in the resulting G10 . We must take into account interactions between actions encoded in Gi0 .
We notice that an Xi does not require a valid adjustment set if it is not an ancestor of Y in Gi0 (i.e. Xi
does not need to satisfy (1) of Def. 2.3 if it can satisfy (2)). Furthermore, even if Xi is an ancestor of
Y in Gi0 , and therefore must satisfy condition (1) of Def. 2.3, any elements of its c-component that are
not ancestors of Y in Gi0 won’t be part of (Gi0 )Y , and therefore don’t need to be conditioned.
It is therefore beneficial for an action Xj to have a backdoor adjustment set that maximizes the0number of nodes that are not ancestors of Y in Gj−1
, so that actions Xi<j can satisfy (2) of Def. 2.3 if
possible, and have the smallest possible c-components in (Gi0 )Y (increasing likelihood that backdoor
set Zi ⊆ before(Xi ) exists if Xi must satisfy condition (1)).
To demonstrate this intuition, we once again look at Fig. 2c, focusing only on action X2 . If we wereto use {W } as Z2 , we still have the same set of ancestors of Y in G10 . If we switch to {X1 }, then W
would no longer be an ancestor of Y in G10 - meaning that X1 is better as a backdoor adjustment set
for X2 than {W } if we only know that X2 is an action (i.e. W would directly satisfy (2) of Def. 2.3
if it were the other action). Finally, using {Z} as Z2 makes both X1 and W no longer ancestors of Y
in G10 , meaning that it is the best option for the adjustment set Z2 .
F IND OX in Alg. 1 employs the above ideas to iteratively grow a set O X ⊆ O of ancestors of X (andincluding X) in G Y whose elements (possibly excluding X) will not be ancestors of Y once theactions in their descendants are taken. That is, an element Oi ∈ O X where ch + (Oi ) ⊂ O X is notpresent in (Gi0 )Y for all actions Xi that come before it in temporal order. Combined with the Markov
Boundary, F IND OX can be used to generate sequential π-backdoors.
We exemplify the use of Alg. 1 through Fig. 2c. O X represents a map of observed variables which0
are not ancestors of Y in Gi<jto the earliest action Xj in their descendants. The keys of O X will be
the set O X . Considering the temporal order {X1 , Z, W , X2 , Y }, the algorithm starts from the last6

Algorithm 1 Find largest valid O X in ancestral graph of Y given G, X and target Y
1: function H AS VALIDA DJUSTMENT(G,O X ,Oi ,Xi )2:
C ← the c-component of Oi in G Y
3:GC ← the subgraph of G Y containing only Pa + (C) and intermediate latent variables
4:
O C ← C \ (O X ∪ {Oi }) (elements of c-component
that might be ancestors of Y in Gi0 )
CC
5:return Oi ⊥⊥ O |(O ∩ before(Xi )) in GC
6: function F IND OX(G,X,Y )7:
O X ← empty map from elements of O to elements of X
8:do
9:for Oi ∈ O of G Y (ancestral graph of Y ) in reverse temporal order do
10:
if |ch + (Oi )| > 0 and ch + (Oi ) ⊆ keys(O X ) then11:
Xi ← earliest element of O X [ch + (Oi )] in temporal order12:
if H AS VALIDA DJUSTMENT(G,keys(O X ),Oi ,Xi ) then13:
O X [Oi ] ← Xi
14:else if Oi ∈ X and H AS VALIDA DJUSTMENT(G,keys(O X ),Oi ,Oi ) then15:
O X [Oi ] ← Oi
16:
while |O X | changed in most recent pass17:
return keys(O X )node, Y , which has no children and is not an element of X, so is not added to O X . It then carries on
to X2 , which is checked for the existence of a valid backdoor adjustment set. Here, the subgraph ofthe c-component of X2 and its parents (H AS VALIDA DJUSTMENT) is simply W → X2 , meaningthat we can condition on W to make X2 independent of all other observed variables, including Y ,in GX2 (W is a Markov Boundary for X2 in GX2 ). The algorithm therefore sets O X = {X2 : X2 },because X2 is an action with a valid adjustment set. Notice that if the algorithm returned at thispoint with O X = {X2 }, the Markov Boundary of O X in GX2 is W , and corresponds to a sequential
π-backdoor for the single action X2 (ignoring X1 ), with policy π(X2 |W ) = P (X2 |W ).
Next, W has X2 as its only child, which itself maps to X2 in O X . The subgraph of W ’s c-component
and its parents is X1 → W , giving (W ⊥⊥ O|X1 )GW , and {X1 } ⊆ before(X2 ), allowing us toconclude that there is a backdoor admissible set for X2 where W is no longer an ancestor of Y . We
set O X = {X2 : X2 , W : X2 }, and indeed with O X = {X2 , W }, the Markov Boundary of O X in
GX2 is X1 , and is once again a valid sequential π-backdoor for the single action X2 (ignoring X1 ),with policy π(X2 |X1 ) = P (X2 |X1 ). The W in O X was correctly labeled as not being an ancestorof Y after action X2 is taken.
Since Z doesn’t have its children in the keys of O X , and is not an element of X, it is skipped,leaving only X1 . X1 ’s children (W ) are in O X , we check conditioning using X2 instead of X1(i.e. we check if X1 can satisfy (2) of Def. 2.3, and not be an ancestor of Y in G10 ). This time,
we have X1 ↔ Z as the c-component subgraph, and Z comes before X2 , satisfying the check(X1 ⊥⊥ Z|Z) in H AS VALIDA DJUSTMENT, resulting in O X = {X2 : X2 , W : X2 , X1 : X2 }, andX
O = {X2 , W , X1 }. Indeed, the Markov Boundary of O X in GX2 is {Z}, and we can construct avalid sequential π-backdoor by using Z1 = {} and Z2 = {Z}, where X1 is no longer an ancestor of
Y in G10 ! In this case, we call X2 a “boundary action", because it is an ancestor of Y in G20 . On theother hand, X1 is not a boundary action, because it is not an ancestor of Y in G10 .
Definition 3.1. The set X B ⊆ X called the “boundary actions" for O X := F IND OX(G, X, Y ) areall elements Xi ∈ X ∩ O X where ch + (Xi ) 6⊆ O X .
Alg. 1 is general: the set O X returned by F IND OX can always be used in conjunction with its Markov
Boundary to construct a sequential π-backdoor if one exists:
Lemma 3.2. Let O X := F IND OX(G, X, Y ), and X 0 := O X ∩ X. Taking Z as the Markov
Y
B
Boundary of O X in GX
as the boundary actions of O X , the sets Zi = (Z ∪ X B ) ∩0 and X
before(Xi0 ) for each Xi0 ∈ X 0 are a valid sequential π-backdoor for (G, X 0 , Y ).

7

Lemma 3.3. Let O X := F IND OX(G, X, Y ). Suppose that there exists a sequential π-backdoor forX” ⊆ X. Then X” ⊆ O X .
Combined together, Lems. 3.2 and 3.3 show that F IND OX finds the maximal subset of X where asequential π-backdoor exists, and the adjustment sets Z1:n can be constructed using the subset of a
Markov Boundary over O X that comes before each corresponding action Xi (Lem. 3.2). F IND OX is
therefore both necessary and sufficient for generating a sequential π-backdoor:
Theorem 3.1. Let O X be the output of F IND OX(G, X, Y ). A sequential π-backdoor exists for(G, X, Y ) if and only if X ⊆ O X .

4Necessity of Sequential π-Backdoor for Imitation

In this section, we show that the sequential π-backdoor is necessary for imitability, meaning that thesequential π-backdoor is complete.
A given imitation problem can have multiple possible conditioning sets satisfying the sequential
π-backdoor, and a violation of the criterion for one set does not preclude the existence of anotherthat satisfies the criterion. To avoid this issue, we will use the output of Algorithm F IND OX, which
returns a unique set O X for each problem:
Lemma 4.1. Let O X := F IND OX(G, X, Y ). Suppose ∃Xi ∈ X s.t. Xi ∈ X \ O X . Then X is notimitable with respect to Y in G.
Our next proposition establishes the necessity of the sequential π-backdoor criterion for the imitabilityof the expert’s performance (Def. 2.1), which follows immediately from Lem. 4.1 and Thm. 3.1.
Theorem 4.1. If there do not exist adjustment sets satisfying the sequential π-backdoor criterion for(G, X, Y ), then X is not imitable with respect to Y in G.
The proof of Lem. 4.1 relies on the construction of an adversarial SCM for which Y can detect theimitator’s lack of access to the latent variables. For example, in Fig. 2a, 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 ∼ Bern(0.5), X := U , Z := U , Y := X ⊕ Z leaves the imitator with a performance of
IE[Ŷ ] = 0.5, while the expert can get perfect performance (IE[Y ] = 1).
Another example with similar mechanics can be seen in Fig. 2c. If the variables are determinedin the order (X1 , W , X2 , Z, Y ), then the sequence of actions is not imitable, since Z can transfer
information about the latent variable U to Y , while X2 has no way of gaining information about U ,because the action at X needed to be taken without context.
Finally, observe Fig. 2d. If Z is determined after X1 , the imitator must guess a value for X1 without
this side information, which is then combined with U2 at W . An adversary can exploit this toconstruct a distribution where guessing wrong can be detected at Y as follows: U1 ∼ Bern(0.5),
Z, X := U1 , U2 ∼ (Bern(0.5), Bern(0.5)) (that is, U2 is a tuple of two binary variables, or a single
variable with a uniform domain of 0, 1, 2, 3). Then setting W = U2 [Z] ([] represents array access,meaning first element of tuple if Z = 0 and second if Z = 1), and X2 := W , Y := (U2 [X1 ] == X2 )gives IE[Y ] = 1 only if π1 guesses the value of U1 , meaning that the imitator can never achieve
the expert’s performance. This construction also demonstrates non-imitability when X1 and Z areswitched (i.e., Fig. 2c with W ↔ Y added, and X1 coming before Z in temporal order).
Due to these results, after running Alg. 1 on the domain’s causal structure, the imitator gets twopieces of information:
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. 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 ofwhich is correct (known as “Simpson’s Paradox” in the statistics literature (Pearl, 2000)).
Furthermore, as demonstrated in Fig. 2c, when performing actions sequentially, someactions might not be imitable themselves (X1 if Z after X1 ), which leads to bias in observed
8#Structure

Order

Seq. π-Backdoor

π-Backdoor

Observed Parents

All Observed

Z, X1 ,
X2 , Y

0.04 ± 0.04%

0.04 ± 0.03%

0.05 ± 0.04%

0.13 ± 0.18%

Z, X1 ,
X2 , Y

0.05 ± 0.03%

0.05 ± 0.03%

0.20 ± 0.25%

0.05 ± 0.03%

X1 , Z,
X2 , Y

0.04 ± 0.03%

Not Imitable

0.27 ± 0.40%

0.26 ± 0.39%

X1 , Z,
X2 , Y

Not Imitable

Not Imitable

0.19 ± 0.29%

0.19 ± 0.29%

Z

1
X1

X2

U1

Z

X1

X2

U1

Z

X1

X2

2
3

Y

Y

Y

X1

4

U2

U1
Z

X2

Y

Table 1: Values of |IE[Y ] − IE[Ŷ ]| from behavioral cloning using different contexts in randomly
sampled models consistent with each causal graph. Cases with incorrect imitation are shown in red.

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 Zi for every action Xi 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 Kumor et al. (2021, Appendix B)), comparing
the performance of 4 separate approaches to determining which variables to include in an imitating
policy:1. All Observed (AO) - Take into account all variables available to the imitator at the time ofeach action. This is the approach most commonly used in the literature.
2. Observed Parents (OP) - The expert used a set of variables to take an action - use thesubset of these that are available to the imitator.
3. π-Backdoor - In certain cases, each individual action can be imitated independently, so theindividual single-action covariate sets are used.
4. Sequential π-Backdoor (ours) - The method developed in this paper, which takes into
account multiple actions in sequence.
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 X was replaced with imitating policies approximating
π(Xi ) = P (Xi |ctx(Xi )), with context ctx determined byeach of the 4 tested methods in turn. Our results are shownin Table 1, with causal graphs shown in the first column,
temporal ordering of variables in the second column, andabsolute distance between expert and imitator for the 4 Figure 4: Results of applying supervised
methods in the remaining columns.
learning techniques to continuous data
In the first row, including Z when developing a policy with different sets of variables as input
for X leads to a biased answer, which makes the average at each action. OPT is the ground truth
error of using all observed covariates (red) larger than just expert’s performance, SπBD represents
the sampling fluctuations present in the other columns. our method, AO is all observed, and OP
Similarly, Z needs to be taken into account in row 2, but represents observed parents.
9

it is not explicitly used by 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 X1 , making the π-backdoor incorrectly claim
non-imitability. Our method recognizes that X2 ’s policy can fix the error made at X1 , and is the only
method that leads to an unbiased result. Finally, in the 4th row, the non-causal approaches have noway 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 fromthe HighD dataset (Krajewski et al., 2018) altered to conform to the causal model, to demonstrate thatdifferent 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 theresults shown in Fig. 4. The causal structure was not imitable from the single-action setting, so theremaining 3 methods were compared to the optimal reward, showing that our method approaches theperformance of the expert, whereas non-causal methods lead to biased results. Full details of model
construction, including the full causal graph are given in (Kumor et al., 2021, Appendix B)

6Limitations & 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 (o). Datadependent methods can be computationally intensive, often requiring density estimation. If ourapproach 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 foola 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
Abbeel, P. and Ng, A. Y. Apprenticeship learning via inverse reinforcement learning. In Proceedingsof the twenty-first international conference on Machine learning, pp. 1, 2004.
Argall, B. D., Chernova, S., Veloso, M., and Browning, B. A survey of robot learning fromdemonstration. Robotics and autonomous systems, 57(5):469–483, 2009.
Billard, A., Calinon, S., Dillmann, R., and Schaal, S. Survey: Robot programming by demonstration.
Handbook of robotics, 59(BOOK_CHAP), 2008.
de Haan, P., Jayaraman, D., and Levine, S.
Causal confusion in imitation learning.
In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran
10

Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper/2019/file/947018640bf36a2bb609d3557a285329-Paper.pdf.
Etesami, J. and Geiger, P. Causal transfer for imitation learning and decision making under sensorshift. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, New York, NY, 2020.
AAAI Press.
Hussein, A., Gaber, M. M., Elyan, E., and Jayne, C. Imitation learning: A survey of learning methods.
ACM Computing Surveys (CSUR), 50(2):1–35, 2017.
Koller, D. and Friedman, N. Probabilistic Graphical Models: Principles and Techniques. MIT press,
2009.
Krajewski, R., Bock, J., Kloeker, L., and Eckstein, L. 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), pp.
2118–2125, 2018. doi: 10.1109/ITSC.2018.8569552.
Kumor, D., Zhang, J., and Bareinboim, E. Sequential causal imitation learning with unobserved
confounders. Technical Report R-76, Causal AI Lab, Columbia University., 2021.
Mahler, J. and Goldberg, K. Learning deep policies for robot bin picking by simulating robust
grasping sequences. In Conference on robot learning, pp. 515–524, 2017.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M.
Playing Atari with Deep Reinforcement Learning. arXiv:1312.5602 [cs], December 2013.
Muller, U., Ben, J., Cosatto, E., Flepp, B., and Cun, Y. L. Off-road obstacle avoidance throughend-to-end learning. In Advances in neural information processing systems, pp. 739–746, 2006.
Mülling, K., Kober, J., Kroemer, O., and Peters, J. Learning to select and generalize striking
movements in robot table tennis. The International Journal of Robotics Research, 32(3):263–279,
2013.
Ng, A. Y., Russell, S. J., et al. Algorithms for inverse reinforcement learning. In Icml, volume 1, pp.
663–670, 2000.
Osa, T., Pajarinen, J., Neumann, G., Bagnell, J. A., Abbeel, P., Peters, J., et al. An algorithmic
perspective on imitation learning. Foundations and Trends in Robotics, 7(1-2):1–179, 2018.
Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan
Kaufmann, 1988.
Pearl, J. Causality: Models, Reasoning and Inference. 2000.
Pearl, J. and Robins, J. M. Probabilistic Evaluation of Sequential Plans from Causal Models withHidden Variables. arXiv:1302.4977 [cs], 1995.
Pomerleau, D. A. Alvinn: An autonomous land vehicle in a neural network. In Advances in neural
information processing systems, pp. 305–313, 1989.
Rizzolatti, G. and Craighero, L. The mirror-neuron system. Annu. Rev. Neurosci., 27:169–192, 2004.
Sutton, R. S., Barto, A. G., et al. Reinforcement Learning: An Introduction. MIT press, 1998.
Syed, U. and Schapire, R. E. A game-theoretic approach to apprenticeship learning. In Advances inneural information processing systems, pp. 1449–1456, 2008.
Tian, J. Studies in Causal Reasoning and Learning. PhD thesis, Computer Science Department,
University of California, Los Angeles, CA, November 2002.
Tian, J. and Paz, A. Finding Minimal D-separators. pp. 15, 1998.
Tian, J. and Pearl, J. A General Identification Condition for Causal Effects. pp. 7, 2002.
11

van der Zander, B. and Liśkiewicz, M. Finding minimal d-separators in linear time and applications.
In Uncertainty in Artificial Intelligence, pp. 637–647. PMLR, 2020.
Van der Zander, B., Textor, J., and Liskiewicz, M. Efficiently finding conditional instruments forcausal inference. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
Widrow, B. Pattern-recognizing control systems. Compurter and Information Sciences, 1964.
Zhang, J., Kumor, D., and Bareinboim, E. Causal Imitation Learning with Unobserved Confounders.
pp. 27, 2020.
Ziebart, B. D., Maas, A. L., Bagnell, J. A., and Dey, A. K. Maximum entropy inverse reinforcement
learning. In Aaai, volume 8, pp. 1433–1438. Chicago, IL, USA, 2008.

12

The Sequential π-Backdoor

A

This section contains proofs of the core theorems mentioned in the text. All results shown here are inreference to the sequential π-backdoor:
Definition 2.3. Given a causal diagram G, a set of action variables X, and target node Y , sets
Z1 ⊆ before(X1 ), . . . , Zn ⊆ before(Xn ) satisfy the “sequential π-backdoor"2 for (G, X, Y ) if at
each Xi ∈ X, either (1) (Xi ⊥⊥ Y |Zi ) in (Gi0 )Xi , or (2) Xi ∈/ An(Y ) in Gi0 .
The first portion shows the proof of sufficiency of of Def. 2.3 for imitation, the second provesthat Alg. 1 finds valid sequential π-backdoors, and the third portion provides the construction ofa counterexample for imitation whenever the algorithm fails to find a valid sequential π-backdoor,
which then shows necessity.
A.1

Proof of Sufficiency

The proof of sufficiency will make heavy use of sufficiency of the π-backdoor as shown in Zhang
et al. (2020), reproduced here using our paper’s notation for convenience:
Theorem A.1. (Zhang et al., 2020) Y is imitable w.r.t. X in G if there is Z ⊆ before(X) such that(X ⊥⊥ Y |Z) in GX . Moreover, the imitating policy is given by π(Z) = P (X|Z).
We will show that the sequential version can be proved with a recursive application of Thm. A.1:
Theorem 2.1. Given a causal diagram G, a set of action variables X, and target node Y , if there
exist sets Z1 , Z2 , ..., Zk that satisfy the sequential π-backdoor criterion with respect to (G, X, Y ),then Y is imitable with respect to X in G with policy π(Xi |Zi ) = P (Xi |Zi ) for each Xi ∈ X.
Proof. We will proceed by induction on the X in reverse temporal order. In the base case we have
Gk0 with distribution over Y identical to the distribution over Y in G (Gk0 = G so the distribution of Y
when no action is taken by the imitator is identical to the original distribution).
In the inductive step, we have graph Gi0 , which explicitly encodes actions of Xi+1 , ..., Xk . We knowthat the distribution over Y is identical in both G and Gi .
If condition (2) is satisfied for Xi in Gi , then Xi is not an ancestor of Y , and therefore P (Y |do(Xi )) =P (Y ) for any action Xi . We can therefore take any action from Xi without affecting the distributionof Y , and therefore the distribution is identical for Y in G and Gi−1 (which is the graph explicitly
encoding whichever policy was chosen for Xi .
If condition (2) is not satisfied, condition (1) must be satisfied in Gi , and by Thm. A.1, the policy
πXi (Zi ) = P (Xi |Zi ) perfectly imitates Y in Gi , meaning that once the policy is explicitly encoded
to construct Gi−1 we have P (Y )Gi−1 = P (Y )Gi−1 = P (Y )G where P (Y )Gj is the probability ofY assuming the given policy is followed for Xj+1 , ..., Xk . We therefore have Gi−1 which encodes
the causal graph of the imitator acting on Xi , ..., Xk has an identical distribution over Y if the given
policies are taken, proving the inductive hypothesis.
Finally, once all actions are taken according to the described policies, the distribution over Y remains
identical to the distribution over Y in the original mode with all actions taken by expert, meaning that
Y is imitable with respect to X in G.
A.2

Algorithm Proofs

Lemma A.1. Suppose that there exists a sequential π-backdoor for X.
F IND OX(G, X, Y ).

Then X⊆

Proof. We first observe that keys can only be added to O X in Alg. 1. Furthermore, while thealgorithm runs a loop in reverse temporal order, the outer "do" runs until there is no change in O X
for a pass through all of the variables.
We can therefore do a proof by induction over X in reverse temporal order. In particular, on eachsuccessive pass of the outer loop, we focus on the element before it, Xi ∈ X and its ancestors - since2

The π in “π-backdoor” is part of the name, and does not refer to any specific policy.

13

adding elements to O X can only help in the conditioning checks, the focus on reverse temporal orderis, in a sense, a worst-case scenario of the algorithm being artificially limited.
We will show that after the ith successive outer-loop, all elements of Xk−i+1 , ..., Xk will be in the set0keys(O X ), as well as all elements that are not ancestors of Y in Gk−i+1
of the ancestral graph of Y .
In the first outer loop, we have Xk ∈ X that is last in temporal order. When performing the checkfor Xk , a conditioning check is performed ensuring that all values of the c-component of X
0
Suppose for contradiction that Vj is not an ancestor of Y in Gk−1
or is Xk , and yet Vi ∈/ keys(O X ).
Since the check is performed in the ancestral graph of Y , the only way for this to be true is if all of its
directed paths to Y pass through Xk , and as such are cut when the parents of Xk are replaced withthe conditioning set Zk . We therefore conclude that Vi and has at least one directed path (possiblyof size 0 if Vi = Xk ) to Xk in G, and no element along any path from Vi to Xk is in Zk (otherwise0
it would be an ancestor of Y in Gk−1). For Vi to not be in keys(O X ), the algorithm’s conditioning
check must have failed somewhere along one of the directed paths to Xk . Call the node of failure Vj .
The conditioning check ensures that all elements in the c-component of Vj reachable without using
colliders at elements in O X are in before(Xi ). Since the keys of O X represent non-ancestors of Y ,the check failing means that there is a path to an element of the c-component that is in before(Xk ).
Each collider that the path passes is either an ancestor of Y , and therefore either it, or one of its
descendants must be in Zk , or was not yet added to keys(O X ), but it itself is not an ancestor of Y ,in which case the same proof can be repeated using that element as Vj , since it would also fail theconditioning check. Since any conditioning set will have a path to an element before Xk , which itself
0
is an ancestor of Y in Gk−1
, it and its descendants can’t be part of a conditioning set Zk , meaningthat there was a contradiction (Zk was a d-separating set - since Xk was the last element in temporalorder, and we are in the ancestral graph of Y , it must satisfy condition (1).

Now suppose we are on the i’th loop. After the first i − 1 loops, all elements Xk−i+1 , ..., Xk will be0
in the set keys(O X ), and all elements that are not ancestors of Y in Gk−i
are also in keys(O X ). If
Xk−i satisfies condition (2) of the sequential π-backdoor, then it is already in keys(O X ), and any
policy chosen will not have any effect on the elements that are ancestors of Y .
However, if it satisfies condition (1), we proceed in the same way as before (we show a shortened0
repeat here). Suppose for contradiction that Vi is not an ancestor of Y in Gk−i−1, but is not inXkeys(O ) after the ith loop. Since all non-ancestors of Y that don’t have paths through Xi werealready in keys(O X ) after the i − 1st loop, Vi must have a directed path to Xi . For the algorithm to
not include the element, the conditioning check must have failed at some node on one of the paths
from Vi to Xi . Call this element Vj . Once again, the conditioning Zk that satisfies the sequential
π-backdoor must block all elements of the c-component of Vj that have directed paths to Y which
are reachable without conditioning on non-ancestors, which is violated if any such element comes
before Xi . This is a contradiction, since the conditioning set satisfies the sequential π-backdoor.
We have therefore shown that after repeating the proof inductively for all variables, using k passes of
the algorithm through the nodes, we have X ⊆ F IND OX(G, X, Y ).
The next theorem and proof will use the following definition of boundary nodes:
Definition 3.1. The set X B ⊆ X called the “boundary actions" for O X := F IND OX(G, X, Y ) areall elements Xi ∈ X ∩ O X where ch + (Xi ) 6⊆ O X .
Lemma 3.2. Let O X := F IND OX(G, X, Y ), and X 0 := O X ∩ X. Taking Z as the Markov
Y
B
Boundary of O X in GX
as the boundary actions of O X , the sets Zi = (Z ∪ X B ) ∩0 and X
0
0
0
before(Xi ) for each Xi ∈ X are a valid sequential π-backdoor for (G, X 0 , Y ).
Proof. We will perform a proof by induction over the algorithm’s O X map. Suppose that thealgorithm is given G, X, Y - we show that at each step of the algorithm, returning O X would satisfy
the theorem.
00

In the base case O X is empty, making O X = ∅, so X 0 = X ∩ O X = ∅. There is therefore a valid
sequential π-backdoor of size 0.
Next, suppose that O X can be used to construct a valid sequential π-backdoor. Suppose we are now
checking a node Vi ∈ V for inclusion in O X , following Alg. 1.
14

If the check fails, no node is added, and the theorem remains true. We therefore focus on the situations
where an element is added to O X .
Suppose ch(Vi ) ⊆ keys(O X ), and the algorithm chooses the earliest element of O X [ch(Vi )] in
temporal order, or the element is a boundary action of the current V X . For Vi to be added to the keysof O X , we will show that the resulting conditioning set corresponds to a valid sequential π-backdoor.
If the added element was in X, but is not a boundary action, then we know it satisfies condition(2), since by the given construction, all directed paths from Vi to Y pass through elements of X,
which in turn don’t have any descendants of Vi in their conditioning sets. Furthermore, all previously
added elements of keys(O X ) ∩ X that have all children in keys(O X ) satisfy condition (2), since noelements were removed from keys(O X ). We therefore only need to prove that the boundary actions
satisfy (1).
We will prove this by contradiction. Suppose that Vi is added to O X , but after adding Vi , there is aboundary action Xj which had (Xj ⊥⊥ Y |Zj ) before Vi was added, but has (Xj 6⊥⊥ Y |Zj ) after it
was added. Using Lem. 3.1, we know that the only difference in Zj before and after Vi is added tokeys(O X ) is that Vi is removed from the conditioning set, and elements of its c-component and its
parents that are not in keys(O X ) added. Because Xj and Y are no longer independent, there exists apath from Xj to Y in Gj0 with colliders at elements of Zj . Since the entire conditioning set remains
identical as before, and was a valid markov boundary, adding the elements of Vi ’s c-component
cannot open any paths to Y . However, the removal of Vi from the conditioning set can open paths.
We therefore know that the path from Xj to Y must pass through Vi . Suppose P is this path. There
are two possibilities for this path.
1. The path comes to Vi , and continues into the descendants to Vi (Vi → ...). All paths into
descendants pass to either elements of X that come after Xj , in which case they are notancestors of Y in Gj0 , and Zj does not condition on them, meaning that the path can’t get to
Y . On the other hand, if the path passes to elements of X ∩ before(Xj ), it has a collider atthat element (call it Xl ), and then continues back up. However, if the path continues backpassing Vi again, we know that it must be blocked, since in the original conditioning set, we
can modify the path to simply use Vi as a collider, showing a contradicton. On the other
hand, if the path does not pass back up to Vi ’s ancestors, either (Xl 6⊥⊥ Y |Zl ), in which case
we can repeat this proof using Xl instead of Xj as the starting node (since Zl ⊂ Zj ), or thepath uses an element Xo ∈ after(Xl ) but Xo ∈ before(Xj ) as a collider. In that case, thesame argument can be repeated: either (Xo 6⊥⊥ Y |Zo ), in which the proof can be restarted
with Xo , or the path continues to another such element. Since there are finite elements of
X, at some point we have (Xo 6⊥⊥ Y |Zo ), and can restart the proof from there.
2. The path comes to Vi from the descendants (← Vi ←) or Vi is the starting node. The pathmust therefore either start at a descendant to Vi (Xl ) or have a collider at Xl . In both cases,
since Vi passed the conditioning check that includes all such possible descendants, the set
Zl contains all the elements of the c-component and their parents that are not in keys(O X ).
We can therefore repeat the argument made in possibility 1 for the continuation of the path,showing that there must exist another element Xo where (Xo 6⊥⊥ Y |Zo ) along this path,from which the proof can be restarted.
Since both cases recusively shorten P on each restart of the proof, there will be an Xo at which oneof the requirements will be violated, showing a contradiction.
Theorem 3.1. Let O X be the output of F IND OX(G, X, Y ). A sequential π-backdoor exists for(G, X, Y ) if and only if X ⊆ O X .
Proof. Lem. A.1 shows that X ⊆ O X , if a π-backdoor exists, and ?? shows that we can construct avalid π-backdoor whenever X ⊆ O X , which shows that the algorithm returns an answer if and only
if a π-backdoor exists.
0

Lemma A.2. O X := F IND OX(G, X, Y ), and let O X := F IND OX(G, X 0 , Y ), with X 0 ⊆ X.
0
Then O X ⊆ O X .
15

Proof. We first observe that keys can only be added to O X in Alg. 1. Furthermore, we observe thatthe conditioning checks can only be helped by adding values of X to consider in the algorithm (i.e.
adding an element to O X cannot cause a conditioning check to fail that would otherwise succeed,
but it can cause a conditioning check to succeed where it would have failed). Therefore, all of
the conditioning checks that succeeded when using X 0 will also succeed when using X, and so0
keys(O X ) ⊆ keys(O X ).
Lemma 3.3. Let O X := F IND OX(G, X, Y ). Suppose that there exists a sequential π-backdoor forX” ⊆ X. Then X” ⊆ O X .
Proof. Suppose not, that is, suppose that a sequential π-backdoor exists for X”, but X” 6⊆ V X .
However, using Lem. A.2, it also means that V X” := F IND OX(G, X”, Y ) does not contain X”, andso using Thm. 3.1, no sequential π-backdoor exists for X”, a contradiction.
A.3

Proof of Necessity

Definition A.1. A O X -adversarial directed path is a directed path from a node V1 to Y in theancestral graph of Y , such that given O X from F IND OX(G, X, Y ), is constructed iteratively startingfrom Vi as follows:• If ch(Vi ) ⊆ keys(O X ), choose the one that maps to the earliest element of X in O X(Vi+1 ∈ {Vj |Vj ∈ ch(Vi ), O X [ch(Vi )] ⊆ after(O X [Vj ])})
• If Vc := ch(Vi ) \ keys(O X ) is non-empty, choose any Vi+1 ∈ Vc as next element in path.
• If the resulting path intersects with another, the path continues with the other to Y .
Definition A.2. A O X -adversarial directed path set is a set of paths starting at a set of nodes V P to
Y , where each path carries a tuple of values, and two paths merging concatenates the tuples of both
paths, such that Y obtains a tuple containing all of the values of nodes at V P .
Definition A.3. A O X -adversarial latent path is a path starting at Vi ∈ V Y and ending at Vj ∈ V Y ,of the form Vi ← ... → C1 ← ... → Vj , with colliders C1 , C2 , ..., Ck ∈ C ⊆ V Y and:1. ∀Ci ∈ C ∪ {Vi , Vj }, Ci ∈/ keys(O X )2. All elements along the path except C, Vi , Vj are latent
3. Vj comes after Vi and all elements of X where {Xi ∈ X|∃Ci ∈ C ∪ {Vi }, ch(Ci ) ⊆keys(O X ), Xi ∈ O X [Ci ], Xi ∈ Before(Xj )∀Xj ∈ O X [Ci ]}4. |ch(Vj ) \ keys(O X )| > 0
Lemma A.3. Given O X , and Vi ∈ X or ch(Vi ) ⊆ keys(O X ), but Vi ∈/ keys(O X ), then thereX
exists a O -adversarial latent path from Vi to a node Vj , crossing colliders A1 , ..., Ak .
Proof. Given the c-component C of Vi (including Vi ), every Ci ∈ C which is not in keys(O X ),but is either in X or has all its children in keys(O X ) had (Vi ⊥⊥ C \ (O X ∪ {Vi })|(C \ (O X ∪{Vi })) ∩ before(Xi )) in GC evaluated in F IND OX(G, X, Y ) on the last iteration, and failed thecheck, without any changes to O X in the iteration. This means that each Ci has an element of the
c-component, Cj ∈ after(Ci ) (otherwise it would be part of the conditioning in the check) such that
there is a path in the c-component’s subgraph to it crossing only colliders A1 , ..., Ak ∈ C not in O X .
Let P be the path corresponding to Vi . Conditions 1,2 hold by definition. However, this path does notnecessarily satisfy conditions 3,4. Let Ai be the first element along the path from Vi which violatescondition 3, meaning that Vj comes before Ai . Since Ai must is either in X or has all its children inkeys(O X ) by the requirements of condition 3’s constraint, it has a path to a different end element,
Va , which comes after Ai . We can therefore concatenate P with the new path, removing all loops
and intersections, such that we are left with a new path P 0 ending at Va . The elements of the pathbefore Ai satisfied condition 3, so they must satisfy the condition with an end element coming evenlater in temporal order. We can repeat this procedure until we have a path from Vi where none of thecolliders come after the last element Vj0 , meaning that condition 3 is also satisfied.
16

Finally, suppose Vj has all of its children in keys(O X ), violating condition 4. This is once again
sufficient for a path to exist from Vj to an element before Vj , which is concatenated in the samemanner to P . We repeat the procedure for violations of 3 and 4 until all conditions are satisfed (which
can be repeated up to |C| times, since each iteration uses a later end node in the c-component).
The above procedure is sufficient for the resulting path to be a O X -adversarial latent path startingfrom Vi , which completes the proof.
Lemma 4.1. Let O X := F IND OX(G, X, Y ). Suppose ∃Xi ∈ X s.t. Xi ∈ X \ O X . Then X is notimitable with respect to Y in G.
Proof. We prove this by induction, starting with a proof that X ∩ Before(Xi ) is not imitable.
Base Case: Define Xj to be the earliest element of O X [ch(Xi )] if all children of Xi are in O X ,otherwise let it be Xi .
Since Xi was not in O X , it means that there is a O X -adversarial latent path from Xi to element
Vj ∈ after(Xj ), crossing colliders A1 , ..., Ak (Lem. A.3). Between each two successive observed
nodes of the latent path, there is a latent variable that is a common ancestor. That is, the path isof the form Xi ← ... ← U1 → ... → A1 ← .... → Vj . The set of these latent variables can be{U1 , U2 , ..., Uk+1 } = U Xi . Set these variables to each be Ui ∼ Bern(0.5) (i.e. random coin flips),and have the directed paths from U Xi to the observed nodes of the path to simply pass throughthe values. Then, let each Ai = Ui ⊕ Ui+1 , Xi = U1 , and Vi = Uk+1 . Finally, construct a O X adversarial directed path set (Def. A.2) from (A..., Vi , Xi ) to Y that passes these values toL
Y . Y thenaccepts the set of values (A..., Vi , Xi ) which conform to the condition 0 = Xi ⊕ Vj ⊕ Ai ∈A Ai .
Note that we do not have Y as a mathematical function of its arguments, but rather as the set of tuples
that are considered "correct", with Y = 1 if the inputs to Y are in the “accepted” set, and Y = 0
otherwise.
When the expert is acting, the result is is 0, since M ⊕ M = 0 for any variable M , making Y = 1:!
M
Xi ⊕Ai ⊕ Vj = U1 ⊕ (U1 ⊕ U2 ) ⊕ (U2 ⊕ U3 ) ⊕ ... ⊕ (Uk ⊕ Uk+1 ) ⊕ Uk+1 = 0
Ai ∈A

We observe that when imitating Xi , the imitator does not have access to U1 , and all imitated elements
can only use A as context (since Xi is the last element of X ∩ Before(Xi ) in temporal order, andVi ∈ after(Xi ). Since many paths for the path set can have crossed Xi , we can create a generalized
imitator which has control over all of the inputs to Y except for Vj . This means that the requirement
is now:
0 = Vj ⊕ f (A1 , ..., Ak ) = Uk+1 ⊕ f (U1 ⊕ U2 , ..., Uk ⊕ Uk+1 )Uk+1 is only present in Ak , but then Uk must be isolated to extract the value of Uk+1 . This proceeds
recursively along the chain until U1 is reached, which is not present in any other observed variable,
allowing us to conclude that it is impossible to isolate Uk+1 , and therefore impossible to guesscorrectly all the time, and so it is impossible to match the expert’s performance (which is 100%). We
have therefore shown that X ∩ Before(Xi ) is not imitable.
Inductive Step: Define Xj ∈ X. Suppose that X ∩ before(Xj ) is not imitable, with a given
adversarial circuit for X ∩ before(Xj ) as constructed in this proof bearing witness to non-imitability.
We will prove that X ∩ Before(Xj ) (i.e. including Xj ) is not imitable, and construct a corresponding
circuit.
We are adding another imitator Xj to the previous path sets, which can possibly come after theprevious circuit’s adversarial path Vj (which came after Xj−1 ). This means that we must modify thecircuit to make sure that Xj cannot use its ability to observe previous values to “fix” any mistakes
made by Xj−1 .
If none of the paths from the previous circuit pass through Xj , then it cannot affect the value ofY , and thus X ∩ Before(Xj ) is not imitable with an identical circuit as the previous inductive step.
Similarly, any adversarial directed paths that enter O X in the second node of the path and moveacross Xj before exiting to V Y (first node of any adversarial directed path in the circuit is neverin O X ) means that there is an element in after(Xj ) in the O X -adversarial latent path that createdthe node starting this path set, and therefore Xj cannot know at least one of the values required to17

“correct” for the value passed down this path (each adversarial latent path corresponds to a sequenceof xors of bernoulli random variables - to set these values to be consistent with the full xor chain, Xj
would need to have access to the entire chain).
Finally, suppose there is a set P of O X -adversarial directed paths which enters O X and passes
through Xj before exiting to V Y , and the last node Vb of each such path before entering O X to Xj
is not the first node of the path. Note that the value of O X stays the same in each fragment of O X
before exiting to Y , since otherwise it would mean that either the path moved across a boundary node
directly back into O X (disallowed by definition of adversarial path), or that the conditioning checksucceeded using Vi , Vi , but failed when using Xi , Vi , where Xi comes after Vi - where there are lesselements not conditioned. For each path pi ∈ P we have two cases. In the first case, the path did notcross any other Xi after entering the O X of Xj , and in the second case it does.
We start by tackling the first case. We know that X ∩ before(Xj ) is not imitable, so with a certain
probability, the full set of paths gives a set of values that are not in the acceptable set for Y . In
particular, it is now possible that by modifying the values that pass through the paths across Xj , theimitator might set the values to their correct settings given the context of all previous values. The
adversary can prevent this by recognizing that Vb (the last node of pi before entering O X to Xj ) musthave an associated O X -adversarial latent path from Vb to element Vj ∈ after(Xj ). Suppose thatthe path pi passes n binary values to Y across Vb . We combine this with an adversarial latent path,
which is of the form Vb ← ... ← U1 → ... → A1 ← .... → Vj . The set of these latent variables canbe {U1 , U2 , ..., Uk+1 } = U Xi . Set these variables to each be Ui ∼ Bern(0.5)2n (i.e. 2n randomcoin flips), and have the directed paths from U Xi to the observed nodes of the path to simply passthrough the values. Once again, each Ai = Ui ⊕ Ui+1 where the xor is performed elementwise, and
Vi = Uk+1 . At Vb , however, we now perform a different operation. We take the 2n-dimensional
vector coming from U1 , reshape it to (n, 2), and have as output be U1 [pi ], in other words, the binary
values passing through pi are now indices that choosethe binary
 values from U1 for each element. In
a bother words, if p1 carries the tuple (0, 1), and U1 =, then U1 [p1 ] = (a, d). Then, the pathc d
pi replaces its value at Vb with this output, carrying it to Y . At Y , each element of the set of valid
values has its corresponding pi element replaced with the set of values compatible with:!
M
0 = Vb [pi ] ⊕Ai [pi ] ⊕ Vj [pi ]Ai ∈AThis is because once again:
U1 [pi ] ⊕ (U1 ⊕ U2 )[pi ] ⊕ (U2 ⊕ U3 )[pi ] ⊕ ... ⊕ (Uk ⊕ Uk+1 )[pi ] ⊕ Uk+1 [pi ] = 0
Once again, without being able to change the value of pi to the correct one before it gets to Vb , Xj only
has access to the imitated value of p1 , which only matches the correctly imitated elements. Without
knowledge of Vj , Xj cannot correctly account for the elements of pj which were not imitated/guessed
correctly (inductive hypothesis).
Finally, in the second case, the path crossed through another element Xi after entering the O X of
Xj . This means that O X at Vb for Xi was either Xj or an element after it, meaning that the circuit
constructed for Xi still has its Vi value unobserved by Xj , and once again cannot be imitated.
By repeating this step for each path crossing Xj , and performing the procedure for each Xj ∈ X, we
can construct a full circuit for the entire graph, which is not imitable at each step in temporal order
after the element Xi , completing the proof.
Theorem 4.1. If there do not exist adjustment sets satisfying the sequential π-backdoor criterion for(G, X, Y ), then X is not imitable with respect to Y in G.
Proof. By Thm. 3.1 and Lem. 4.1

18

H

A

C

R1

X1

R2

X2

R3

X3

R4

Y

Figure 5: Causal graph for the continuous data experiment given in Appendix B.2.

B

Simulations

This section describes implementation details of each experiment.
B.1

Synthetic Binary Simulations

This experiment first generates a randomly sampled model consistent with the causal graphs in
Table 1. All variables are binary. This means that each variable X contains 2 possible actions. Y is
also binary, such that IE[Y ] is sufficient for characterizing the imitation results.
For each variable in the causal graph, the model was generated by sampling each element of theconditional probability table (CPT) uniformly at random. For example, X2 in Table 1 #1 would have
its CPT generated as follows for every combination of values x1 , u2 of its parents:
P (X2 = 1|X1 = x1 , U2 = u2 ) = U nif orm(0, 1)
Y was also generated in the same way:
P (Y = 1|P a(Y )) = U nif orm(0, 1)
P (Y = 0|P a(Y )) = 1 − P (Y = 1|P a(Y ))This type of modeling ensures that the resulting bias is an average of randomly chosen models,
proving that distributions where the bias is non-negligible consistent with the given graphs arecommon.
With the models produced as above, for each action, we sampled 10,000 runs, creating a dataset over
the observed variables (including expert actions). We subsequently found the empirical CPT for eachaction Xi to reproduce P (Xi |Context) from the observational data. Context is chosen according to
the given policy (Seq π-Backdoor, π-Backdoor, Observed Parents, All Observed).
Finally, the trained policies were plugged back into the model, giving their performance in the actual
system for a total of 10000 runs. The absolute value of the difference between the expectation of Y
from expert and the imitator is recorded.
This procedure, including sampling of new models consistent with the graph, is performed 1000
times for each graph, and the resulting average performance is recorded in Table 1.
B.2

Adversarial Graph with Continuous Data

The causal graph in Fig. 5 was generated to demonstrate a larger problem that uses continuous
observed variables rather than the small binary graphs demonstrated in Appendix B.1.
The implemented structure intuitively represents a simplified radar-based cruise control system’sobservations of a driver’s behavior. At the time of each action Xi , the radar (Ri ) detects the distanceto the car in front, as well as the change in distance over time. The driver is increasing/decreasing(Xi ) the speed based on both the distance to the car in front, and their own mental state (H, for“in a hurry”), which is unobserved by the driving system. The driver’s action results in a new
distance/relative velocity between cars (Ri+1 ).
19

The driving system also has access to the full vehicle state, which includes whether the air conditioning(A) has been turned on. The AC state is determined by the driver’s internal thoughts (H), as wellas the driving conditions (C), including outside temperature, which are not directly sensed by thesystem.
Finally, whether the driver is considered a “safe driver" according to highway patrol is dependent on
the overall conditions (C), and the distance between cars throughout the measuring period (Ri ).
The goal of the system is to drive in such a way that the anti-robot highway patrol will not notice any
erratic behavior.
In this model, we once again compare the 4 approaches.
1. All Observed: We assume that A is observed before all actions. This gives us the following
policy:π(X1 |R1 , A) = P (X1 |R1 , A)π(X2 |R1 , X1 , R2 , A) = P (X2 |R1 , X1 , R2 , A)π(X3 |R1 , X1 , R2 , X2 , R3 , A) = P (X3 |R1 , X1 , R2 , X2 , R3 , A)
2. Observed Parents: In this approach, we only condition each policy on the subset of theaction’s parents that are observed. Namely:π(X1 |R1 , A) = P (X1 |R1 )π(X2 |R1 , X1 , R2 , A) = P (X2 |R2 )π(X3 |R1 , X1 , R2 , X2 , R3 , A) = P (X3 |R3 )3. π-Backdoor: The π-backdoor cannot be applied in this situation, since X1 would need to
be imitable by itself, whereas here there is a path to Y through H that cannot be taken into
account at X1 .
4. Sequential π-Backdoor: The sequential π-backdoor returns the following policy:
π(X1 |R1 , A) = P (X1 |R1 )π(X2 |R1 , X1 , R2 , A) = P (X2 |R1 , X1 , R2 )π(X3 |R1 , X1 , R2 , X2 , R3 , A) = P (X3 |R1 , X1 , R2 , X2 , R3 )The only difference between policies here is the data that is taken into account for imitation purposes.
In particular, the sequential π-backdoor explicitly ignores the state of the air conditioning, which isavailable to it, and would alter the outcome (see the “All Observed” policy).
B.2.1

Generating an Adversarial Environment

The cruise control system has no knowledge of “correct” behavior, and does not understand humans,
which includes both the driver and highway patrol. Whatever policy is generated by the algorithm
must therefore take into account any possible behaviors that are consistent with the causal graph.
To demonstrate the issues stemming from an incorrectly chosen covariate set, we are free to construct
an adversarial model. To do this, we followed a procedure similar to Zhang et al. (2020), maximizing
error from naïve behavioral cloning. We first construct a binary model consistent with the above
causal graph, then overlay continuous data over the Ri . The imitator will only have access to thecontinuous data, and will remain ignorant to the underlying data-generating mechanics, except forthe causal graph. In particular, we will focus on two sub-structures in the model.
1. The first sub-structure, shown in Fig. 6a, can have the following binary representation:
R1 ∼ Bern(0.5)
H ∼ Bern(0.5)
X1 = R1 ⊕ H
R2 = X1
X2 = R2 ⊕ H
R3 = X2
Y = R1 == R3
20

H

A

C

R1

X1

R2

X2

H

A

R3

X3

R4

C

R1

X1

R2

X2

R3

X3

R4

Y

Y

(a)

(b)

Figure 6: The two sub-structures that are adversarially optimized in the binary model to generate thefull causal graph.
Given this structure, using only R2 as X2 ’s parent when imitating will give P (X2 |R2 ) =P (X2 ), but the correct policy would be X2 = R1 - meaning that the imitator can only guesscorrectly half the time.
2. The second sub-structure, from Fig. 6b, has the following binary representation:
H ∼ Bern(0.62)
C ∼ Bern(0.62)
A=C ∧H
X3 = H
R4 = X3
Y = R4 ⊕ C
With this structure, not including A in X3 ’s policy gives an average performance E[Y ] =0.47, but including it gives a maximum of E[Y |do(π)] = 0.18.
Combining these two substructures gives us the following binary version of the full graph:C ∼ (Bern(0.5), Bern(0.62))
H ∼ (Bern(0.5), Bern(0.62))
A = C[1] ∧ H[1]R1 = C[0]X1 = R1 ⊕ H[0]R2 = X1
X2 = R2 ⊕ H[0]R3 = X2
X3 = H[1]R4 = X3
Y = (R1 == R3 ) ∧ (R4 ⊕ C[1])Since the resulting samples of the above model would be binary, we generate an overlay of continuous
data which has identical underlying mechanics.
B.2.2

Applying Continuous Data to a Binary Structure

While we could sample from arbitrary continuous distributions, we choose to use data from the
HighD dataset (Krajewski et al., 2018), which includes vehicle trajectories gathered from drones
flying over a section of highway. This dataset does not include a causal graph, and hypothesizing agraph from the data is beyond the scope of our contribution. Instead, since this data does not conformto the distribution implied by the adversarial binary structure generated in Appendix B.2.1, we alter
the data to match the adversarial structure before performing imitation. This gives us a non-trivial
continuous distribution conforming to the causal graph. We are effectively creating a new dataset
21

using the randomness/distribution present in the HighD dataset’s trajectories, for which we know theground-truth causal diagram and model.
The procedure used to generate a trajectory conforming to a sequence of actions determined by thecausal model from a trajectory in the HighD dataset is:
1. Sample each real trajectory at 4 points (one for each Ri ), giving a tuple for the distance/change of distance between cars ((D1 , ∆D1 )(D2 , ∆D2 ), (D3 , ∆D3 ), (D4 , ∆D4 )).
Pi
2. Set each new trajectory to be Di0 = D1 + j=2 |∆Dj | × (−1)1−Xj based on the actions,with ∆Di = |∆Di | × (−1)1−Xi−1 .
This gives continuous trajectories conforming to the adversarial causal model.
By using Y = ((∆D1 > 0) == (∆D3 > 0))((δD4 > 0)C [1]), we get a simulator for trajectories,
and can use the above conversion to evaluate imitator decisions.
B.2.3

Imitators

A 2 hidden layer neural network with (50,20) neurons with ReLU activation, and Adam optimizer(lr=5e − 5) was trained for each Xi and context pair. At each Xi , the network inputs were the context
variables specific to the method being tested, and output being a prediction of probability of Xi(sigmoid activation with BCE loss).
The outputs (X1 , X2 , X3 ) were binarized by sampling from a bernoulli distribution using the outputsof the network as probabilities.
B.2.4

Results

The testing dataset was converted using the same method as described above, using the outputs
X1 , X2 , X3 from the learned policies instead of the ground-truth causal graph as inputs to thesynthetic trajectory generation. This gave an expected performance average for each policy type,shown in Fig. 4.

22

C

Examples and Simplified Proofs

Lemma C.1. If there is a set Z ⊆ before(Xi ) that satisfies the backdoor criterion for Xi , thenYtaking G Y as the ancestral graph of Y , the Markov Boundary Z 0 of Xi in GX
also satisfies theibackdoor criterion in G
Y
Proof. We know that if Z 0 exists, (Y ⊥⊥ Xi |Z 0 ) in GX
by definition of Markov Boundary.
i

All we need to show is that if Z ⊆ before(Xi ) exists, then Z 0 ⊆ before(Xi ). With outgoing edges
Yfrom Xi removed in GX, the boundary simplifies to Pa + (C(Xi )) \ {Xi }, and in the ancestral graphiof Y , each element of C(Xi ) is an ancestor of Y , and so has an element of Z ⊆ before(Xi ) blocking
each such path - and therefore Pa + (C(Xi )) ⊆ before(Xi ) too.
Proposition C.1. The distribution of X1 , X2 is not imitable with respect to Y in Fig. 1d.
Proof. Define the following functional dependence between the nodes in the causal diagram Fig. 1d,
where ⊕ represents XOR:U1 := Bernoulli(0.5)
Z := U1 ⊕ U2
X2 := U2

U2 := Bernoulli(0.5)
X1 := Z
Y := ((X1 ⊕ X2 ) == U1 )The idea above is to encode information about U1 in X1 , X2 , which can then be verified by Y . In
particular,
Y = ((X1 ⊕ X2 ) == U1 ) = (((U1 ⊕ U2 ) ⊕ U2 ) == U1 ) = (U1 == U1 ) = 1
Notice that the value of Y compares the imitated values X1 , X2 to U1 . Without any way to observe
U1 , the imitator has no way of guessing correctly more than 50% of the time.
More rigorously, the imitator has a distribution determined by a function f (Z) → (X1 , X2 ), since
only Z is observed. The problem of imitation here can therefore be reduced to finding values
for an output distribution for f that result in a distribution over Y identical to the demonstrator’sobservational distribution:
The demonstrator’s (i.e. natural) distribution is as follows, which has P (Y = 1) = 1
U1
0
0
1
1

U2
0
1
0
1

Z
0
1
1
0

X1
0
1
1
0

X2
0
1
0
1

Y
1
1
1
1

P (...)
0.25
0.25
0.25
0.25

The target distribution over the imitating function can be written as a set of variables:
Z
0
0
0
0
1
1
1
1

X1
0
0
1
1
0
0
1
1

X2
0
1
0
1
0
1
0
1

P (f (Z) → (X1 , X2 )|Z)a0
a1a2
1 − a0 − a1 − a2b0b1b2
1 − b0 − b1 − b2

Using this, we can now compute P (Y = 1|U1 = 0, U2 = 0), where Z = U1 ⊕ U2 = 0, giving
P (X1 ⊕ X2 = 1) = a1 + a2 - this means that P (Y = 1|U1 = 0, U2 = 0) = 1 − a1 − a2 , meaningthat a1 = 0 and a2 = 0 to match the demonstrator’s distribution (demonstrator never has Y = 0).
23

U1

U1

Z1

X1

U1

Z1
U2

X2

X1

Z1
U2

X2

Z2

X1
U2

X2

Z2

X3

Z2

X3

U3

X3

U3

U3

Z3

Z3

Z3

Y

Y

Y

(a)

(b)

(c)

Figure 7: An example non-imitable query (Prop. C.2) that is used to demonstrate the ideas of Thm. C.1
is shown in (a). A “bidirected path” through the latents is shown in (b), and the XOR tree constructedfrom the path is in (c).
Next, we compute P (Y = 1|U1 = 1, U2 = 1), with Z = U1 ⊕ U2 = 0 once again. P (X1 ⊕ X2 =1) = a1 + a2 once again, giving P (Y = 1|U1 = 1, U2 = 1) = a1 + a2 , which must add up to 1 but we already required that both variables were 0 to satisfy the previous requirement.
This means that there exists no assignment to the imitator’s probabilities that has P (Y = 1).
Proposition C.2. The distribution of X1 , X2 , X3 is not imitable with respect to Y in Fig. 7c.
Proof. This example is used as a demonstration of the ideas behind the proof of Thm. C.1. We noticethat there is a latent chain Y ← U3 → Z3 ← U2 → Z2 ← U1 → X1 (Fig. 7b), which shows that Y
and X1 are in the same ancestral c-component.
We will construct an equation of XORs made up of the values of the latent variables in the above
chain, such that each latent variable except U3 is used twice, canceling itself, so that Y can check if
the chain correctly cancelled with a comparison to U3 .
To witness, we have:
U1 , U2 , U3 ∼ Bernoulli(0.5)
Z1 = 1X1 = U1
X2 = X1
Z2 = U1 ⊕ U2
X3 = X2 ⊕ Z2
Z3 = X3 ⊕ U2 ⊕ U3
Y = (Z3 == U3 )⇒U1 ⊕ U1 ⊕ U2 = U2⇒U2 ⊕ U2 ⊕ U3 = U3⇒(U3 == U3 ) = 1

Critically, we can now show that without a way to observe X1 or U1 , it is now impossible to correctly
set the values incoming to Y :Y = (Z3 == U3 ) = ((X3 ⊕ U2 ⊕ U3 ) == U3 ) = ((f (Z1 , Z2 ) ⊕ U2 ⊕ U3 ) == U3 )24

Since X3 is imitated, it must be a function of the observed variables (X1 , X2 are generated, theimitator does not observe what they would have been had the imitator not performed any action).
The only way to satisfy the above equation is f (Z1 , Z2 ) == U2 . However, we can substitute:f (Z1 , Z2 ) = f (1, U1 ⊕ U2 ). With no additional knowledge, there is no way to disentangle U1 ⊕ U2 ,meaning that there does not exist a function f that outputs U2 from the given inputs.
Theorem C.1. Let G Y be the ancestral graph of Y in G. If there is Xi ∈ X such that Xi ∈ C(Y ),then X is not imitable with respect to Y in G.
Proof. An example of the steps taken in this proof is given in Prop. C.2. Let the corresponding chainof latent variables be Y ← U1 → V1 ← U2 → ... ← Un → Xi . WLOG, we can assume that the
chain does not repeat nodes (if it did, then it has a cycle, and we can create another chain with thecycle removed), and that none of the Vj are imitated (we can shorten the chain to the first element of
X along it).
We construct a model for the given graph as follows:• Create a tree T rooted at Y which will hold the scaffolding for our constructed distribution.
Since this is an ancestral graph, each node has a directed path to Y . For each V1 , ...Vn−1 , Xi
in reverse topological order, find a single directed path from the node to either Y or a node
along a previously found path, whichever intersects first. Define the set of nodes along thesepaths (including V and Xi ) as P .
• Each of V1 , ...Vn−1 hasL2 inputs from the chain (as well as possibly other inputs). Let thevalue Vi = Ui ⊕ Ui+1 Pj ∈(P a(Vi )∩P ) Pj .
L
• Each element P \ V is defined as Pi = Pj ∈(P a(Pi )∩P ) Pj
L• Xi = Un Pj ∈(P a(Xi )∩P ) Pj
L
• Y = (U1 == Pj ∈(P a(Y )∩P ) Pj )• Let all Ui ∼ Bernoulli(0.5)• All other variables are set to 1
The model’s construction is consistent with the causal graph, and results in Y = 1 with probability 1.
We now show that the imitator has no way of reconstructing Y = 1. Define T 0 as the subtree of T
which, starting at Y , stops at the first element of X, or at the end of the path in P . Let these sub-paths
be P 0 . The equation resulting for the imitated Y is therefore:!
!!
MM
Y = U1 ==(Ui ⊕ Ui+1 )Xi
Vi ∈V ∩T 0

Xi ∈X∩T 0

We
L now imagine a stronger version of the imitator, which replaces the possibly multiple
Xi ∈X∩T 0 Xi with a single function f , which has as inputs all possible observed information,
including information computed after the action X is taken.
To achieve this, we observe that only the Vi have values not completely determined by their observed
parents. We define Vi0 = Ui ⊕ Ui+1 , which can be computed from the observed values by xoringwith its parents. This means the Vi0 contain all of the information from the observed values - and are
well-defined even for future nodes (nodes that depend on an imitation decision).
This means that the function f has more information than the actual imitator. We will show that eventhis weaker version of the problem is not imitable:
!
!
M
0
0
Y = U1 ==(Ui ⊕ Ui+1 ) ⊕ f (V1 , ..., Vn−1 )Vi ∈V ∩T 0

25

Since Vi0 = Ui ⊕ Ui+1 , we can redefine f 0 =0
Vi ∈V ∩T 0 (Vi ) ⊕ f to reduce the above equation to:L

Y = (U1 == f 0 (U1 ⊕ U2 , ..., Un−1 ⊕ Un ))U1 is only present in V10 , so it must be used in f , but then U2 must be isolated to extract the value of
U1 . This proceeds recursively along the chain until Un is reached, which is not present in any otherobserved variable, allowing us to conclude that it is not possible to isolate U1 in f 0 .
This shows that even a generalized imitator that has access to future information cannot perform
imitation here, and so the above distribution is not imitable.
Theorem C.2. Suppose that there exists an m-factor (V X , X, Z, Y ) in G, and let X 0 =0{X2 , ..., Xn } (X with the first element in temporal order removed). Then there exists sets V X , Z 00such that (V X , X 0 , Z 0 , Y ) is an m-factor for G.
Proof. Let X1 be the removed variable. Note that since X1 comes first in temporal order, none of its
ancestors are in X. There are two cases of interest.
The first is when X1 6∈ X B . In this case, the new m-factor is simply (V X , X 0 , Z, Y ). Since theconditioning sets and V Y remain identical, the m-factor conditions hold directly for the new set.
In the case where X1 ∈ X B , we cannot directly remove X1 , since there can be elements of V X
0that are ancestors of X1 . We instead show that we can create a new set V X and Z 0 which removes
ancestors of X1 from V X . In particular, we can instead set Z 0 = Z ∪ (V X ∩ An(X1 )GX B ), and0

V X = V X \ An(X1 )GX B . We show that the resulting set satisfies the requirements of an m-factor.
1. Since An(X1 )GX B were the only elements removed from V X and added to V Y , we know
0that X 0 ∈ V X , since X1 was the first element of X in temporal order (so none of its
0
ancestors are in X 0 ). Likewise, Z 0 ⊆ V Y , since V Y = V Y ∪ An(X1 )GX B , which inludes
Z ⊆ V Y and (V X ∩ An(X1 )GX B ) ⊆ An(X1 )GX B .
00

2. Since all ancestors of X1 in GX B are removed from V X , any element in X X has the samedescendants in GX B as the original m-factor.
00

3. Suppose not. That is, ∃Vx ∈ V X and Vy ∈ V Y such that (Vx 6⊥⊥ Vy |Z 0 ) in GX B . We
know that Vy ∈/ V X ∩ An(X1 )GX B , because those elements are part of Z 0 , and all elements
are independent of Vy conditioned on Vy . We therefore know that Vy ∈ V Y . Likewise,
00since V X ⊆ V X , Vx ∈ V X . Suppose that the path crosses colliders Z1 , Z2 , ..., Zk ∈ Z 0 .
Suppose that all colliders are from the set Z, and there are none from Z 0 \ Z. This path
also exists in the original m-factor, so we have created an unblocked path which violatescondition 2 of the original m-factor, (V X ⊥⊥ V Y |Z) - a contradiction. Next, suppose thatthe colliders can be elements of Z 0 \ Z (i.e. elements added for the new m-factor). Let Zj
be the last such element along the path. This means that Zj ∈ V X ∩ An(X1 )GX B . Taking
only the portion of the path from Zj to Vy , the remaining colliders are from Z, we havecreated an unblocked path from Zj ∈ V X to Vy ∈ V Y . However, this path cannot exist,
since (V X ⊥⊥ V Y |Z) by condition 2 of the original m-factor.
4. Suppose not. That is, suppose that there is an unblocked path in GX B from Xj ∈ X 0 to0V Y conditioned on (X 0 ∪ Z 0 ) ∩ before(Xj ). Let Z1 , ..., Zk be the colliders along thispath. For each such collider Zi in Z 0 \ Z, we know that it is an ancestor of X1 , and thatit has a directed path to it in V X . Since X1 ∈ X ∩ before(Xj ) (X1 is first element of X
in temporal order), we can replace each Zi collider in the original path with the directed
path from Zi to X1 , and the path repeated back to Zi , effectively replacing the collider at Zi
with a collider at X1 , creating a path from Xi to Vy conditioned on (X ∪ Z) ∩ before(Xj ),violating condition 4 of the original m-factor.
This completes the conditions, showing that the smaller m-factor always exists when removing thefirst element of X in temporal order from the set of actions.
26

X1

A

X1

B

A

X2

X1

B

A

X2

X1

B

A

X2

C

X2

C

X3

B

C

X3

C

X3

X3

Y

Y

Y

Y

(a)

(b)

(c)

(d)

Figure 8: An example graph used to demonstrate the procedure used to check a sequential π-backdoor
from Prop. C.3. The temporal observation order of the nodes is: X1 , A, B, X2 , C, X3 . This means,for example, that the imitator for X2 has no knowledge of C nor the decision that will be made at X3 .
Proposition C.3. The distribution shown in figure Fig. 8a with temporal order X1 , A, B, X2 , C, X3
is imitable using the functions: X1 = P (X1 ), X2 = P (X2 |A), X3 = P (X3 |X2 , C).
Proof. In the graph shown in Fig. 8a, we can follow the conditions of Def. 2.3 iteratively:
1. In Fig. 8a, which is equivalent to G3 , since there are no later actions (X3 ⊥⊥ Y |X2 , C)X3 ,satisfying condition (1).
2. Once X3 is replaced with the imitating function, we get G2 , shown in Fig. 8b. Here,(X2 ⊥⊥ Y |A)X2 , once again satisfying condition (1).
3. Finally, we get G1 , in Fig. 8c. While there is no way to condition on A because it comes
after X1 , X1 is no longer an ancestor of Y , so it satisfies condition (2).
This leads to a final imitating policy shown in Fig. 8d.
To verify this result, we can now decompose the probability of Y using the independence relations
from the given graph:X
X
P (Y , A, X2 , X3 , C) =P (Y |A, X2 , X3 , C)P (A, X2 , X3 , C)
P (Y ) =A,X2 ,X3 ,C

A,X2 ,X3 ,CX

P (Y |A, X2 , X3 , C)P (A)P (C)P (X2 |A)P (X3 |AX2 C)=

A,X2 ,X3 ,CWhen replacing the mechanisms of X with their imitated counterparts, we get the following probability for Y :X
X X
P̂ (Y ) =P (V ..., Y ) =P (V ..., Y , U ...)
V \{Y }=X

V \{Y } U

P (Y |AX2 X3 C)P (A|U1 )P (U1 )P (X1 )P (B|X1 )P (X2 |A)P (U2 )P (X3 |CX2 A)P (U3 )P (C|U3 )P (U3 )X=
P (Y |AX2 X3 C)P (A)P (B, X1 )P (X2 |A)P (X3 |CX2 A)P (C)V \{Y }=X

P (Y |AX2 X3 C)P (A)P (X2 |A)P (X3 |CX2 A)P (C)A,X2 ,x3 ,CThese equations match, showing that the given mechanisms are sufficient for imitation.

27