Sequential Causal Imitation Learning with Unobserved Confounders
Authors: Daniel Kumor
Junzhe Zhang
Elias Bareinboim
Venue: NeurIPS 2021 Oral (2021)
Keywords: causality
reinforcement learning
imitation

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

Sequential Causal Imitation Learning with Unobserved Confounders
Daniel Kumor Purdue University dkumor@purdue.com edu
Junzhe Zhang Columbia University j junzhez0cs. columbia.cs edu
Elias Bareinboim Columbia University eböcs columbia. edu
Abstract
"Monkey see monkey do" is age-old adage, referring naive imitation without a deep understanding of a system's underlying mechanics. Indeed, if demonstrator has access information unavailable to the imitator (monkey), such different set of sensors, then no matter how perfectly the imitator models its perceived environment (SFE), attempting to reproduce the demonstrator's behavior (Do) can lead to poor outcomes. Imitation learning in the presence of a mismatch between demonstrator and imitator has been studied in the literature under the rubric causal imitation learning (Zhang et al. 2020), but existing solutions are limited to single-stage decision- makinn.. This paper investigates the problem of causal imitation learning in sequential settings, where the imitator must make multiple decisions per episode. We develop a graphical criterion that is necessary and sufficient for determining the feasibility of causal imitation, providing conditions when an imitator can match demonstrator's 's performance despite differing capa- bilities. Finally, we provide efficient algorithm for determining imitability and corroborate our theory with simulations.
Introduction
Without access to observational data, agent must learn how operate at a suitable level of performance through trial and error (Sutton et al. 1998) Mnih et al.) 2013). This from-scratch approach often impractical in environments with the potential of extreme negative and final outcomes (driving off cliff). While both Nature and machine learning researchers have approached the problem from wide variety of perspectives, a particularly potent method which has been used with great success in many learning machines, including humans, is exploiting observations of other agents in the environment (Rizzolatti & Craighero 2004 Hussein et 2017).
Learning to act by observing other agents offers a data multiplier, allowing agents to take into account others' experiences. Even when the precise loss function is unknown (what exactly goes into being a good driver?), the agent can attempt to learn from "experts"" namely agents which are known to gain acceptable reward the target task. This approach has been studied under the umbrella of imitation 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. (2044] (Syed & Schapire 2008 Ziebart et al. 2008) and behavior cloning (Widrow
1964] Pomerleau 1989 Muller al.] (0066) 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 s sensory capabilities need be perfectly matched. As example, self-driving cars rely solely on cameras or lidar, completely ignoring the auditory dimension and yet most human demonstrators able exploit this data, especially in dangerous situations (car horns, screeching
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

8
s
F
X
X
X2
X
U2
(a)
(b)
(c)
(d)
Figure (a represents simplified view of driver X and surrounding cars F.B.S. ( is
imitable with policies Ti (X1) = P(X1) and my ( 2), but in (d) X2 is not
imitable, despite there being valid sequential backdoor.
tires). Perhaps without 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. Ia 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 s performance is represented by a variable Y (red), which is unobserved (dashed node). Since our dataset only contains visual data, horns H remain unobserved to the learning agent (i.e., the imitator). Despite not being able to hear horns, the learner from Fig. Ta had a full view of the car's surroundings, including cars behind and to the side, which turns out to be sufficient to perform imitation in this example. Consider an instance where F, B, S are drawn uniformly over {0, 1]. The reward Y is decided by -X @ F B @ S: @ represents the exclusive-or operator. The human driver decides the action X + HH where values of horn H is given by F @ B @ S. Preliminary analysis reveals that the learner could perfectly mimic the demonstrator's s decision- other hand, if the driving system does not have side cameras, the side view S becomes latent; see Fig. lb The learner's 's reward E[y [d((T) is equal to 0.5 for any policy π( 6), which is far from the optimal demonstrator's 's performance, F[Y] = 1.
process using an imitating policy X < F @ B @ S. On the
Based on these examples, there arises the question of determining precise conditions under which an agent can account for the lack of knowledge or observations available the expert, and how this knowledge should be combined to generate an optimal imitating policy, giving identical performance as the expert on measure Y. These questions have been recently investigated in the context of causal imitation learning (Zhang et al. 2020), where a complete graphical condition and algorithm were developed for determining imitability in the single-stage decision- decision-making setting with partially observable models (i.e., in non-Markovian settings). Other structural assumptions, such as linearity (Etesami & Geiger, 20200), were also explored in the literature, but were still limited to a single action. Finally. de Haan et al. (219)) explore the case when expert and imitator can observe the same contexts, but the causal diagram not available. Despite this progress, is still unclear how to systematically imitate, or even whether imitation is possible when learner must make several actions in sequence, where expert and imitator observe differing sets of variables (e.g., Figs. [cland
The goal of this paper is to fill this gap in understanding. More specifically, our contributions are as follows. (1) We provide graphical criterion for determining whether imitability is feasible in sequential settings based on a causal graph encoding the domain's 's causal structure. (2) We propose an efficient algorithm to determine imitability and to find the policy for each action that leads to proper imitation. (3) We prove that the proposed criterion is complete (i.e. both necessary and sufficient). Finally, we verify that our approach compares favorably with existing methods in contexts where a demonstrator has access to latent variables through simulations. Due to space constraints, proofs are provided in the complete technical report (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- = {Z,,-. ..., 2n), z {21 Zi; .... En Zn ). |Z| represents a set's cardinality. The joint distribution over variables Z is denoted by P(Z). To simplify notation, consistently use the shorthand P(z) to represent probabilities P(Z, 2))

---

X
X
X
U2
2
X2
X
w
X
Z
W
X2
(b)
(c)
(d)
Figure 2: Despite there heing 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 comes before X2 in temporal order, the query in ddb imitable only if Z comes before Xi.
The basic semantic framework of our analysis rests on structural causal models (SCMs) (Pearl 2000, Ch. 7). An SCM M is a uplle (U,V,F, P(u)) with V the set of endogenous, and U exogenous variables. F is set of structural functions s.t. for fv E F, V + (pay, uy) uv). with PAy S VVUV U. Values of U are drawn from an exogenous distribution P(u), inducing distribution P(V) over the endogenous V. Since the learner
observe only a subset of endogenous variables, we split V into O C V (observed) and L = V \ O (latent) sets of variables. The marginal P(O) is thus referred as the observational distribution.
Each SCM M is associated with a causal diagram G where (e.g., see Fig. 2 solid nodes represent observed variables O, dashed nodes represent latent variables L, and arrows represent the arguments pa(V) of each functional relationship fv. Exogenous variables U are not explicitly shown; bi- directed arrow between nodes V; and V, indicates the presence of an unobserved confounder (UC) affecting both Vi and V,. We will use standard conventions to represent graphical relationships such as parents, children, descendants, and ancestors. For example, the set of parent nodes of X in G is denoted by pa(X); = Uxe x (a(X)) (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 Vi E O is an effective parent of V, E V if there is a directed path from V, to Vj in 9 such that every internal node 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 U pa (S). Other relations, like ch + (S) are defined similarly.
de( X) & U X. An observed variable
path from node X node Y in G is said be "active" conditioned on (possibly empty) set W if there is a collider at A along the path (- A <-) only if A E An (WW, ). and the path does not otherwise contain vertices from W (d-separation, Koller & Friedman 2009)). X and Y are independent conditioned on W (X IL Y if there are no active paths between any X E X and E Y. For a subset X C V, the subgraph obtained from & with edges outgoing from X / incoming into X removed is written Gx/9x respectively. Finally, we utilize 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 L UUU.A. A ser C S Ch( n O is e-component for any pair Us, U, E N, there exists a path between U, and U, in G such that every observed node V₁ E on the path is a collider (i.e., V& +-).
C-components correspond to observed variables whose values are affected by related sets of unob- served common causes, such that if A, B E C, (A H. BJO (A, B)). In particular, we focus on maximal c-components C. where there doesn't exist c-component C" s.t. C C C". The collection of maximal c-components forms a partition Ct...., On over observed variables O. For any set S C O, let C(S) be the union of c-components C, that contain variables in S, For instance, for variable Z in Fig. Id. the c-component C((Z)) = ( {Z,X,} X
2 Causal Sequential Imitation Learning
We are interested in learning a policy over series of actions C O that an imitator gets average reward Y E V identical to that of an expert demonstrator. More specifically, let variables in X be ordered by Xj...., 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 X; E 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( X:) and after (Xter(X)) to represent nodes that come before/after an action X, X following the ordering, excluding X, itself. policy on actions X is sequence of decision rules { nn) where each n. Tx(X, (X,l Z.) is function
3

---

mapping from domains of covariates Z; S before(X,, to the domain of action X,, The imitator following a policy x replacing the demonstrator in an environment encoded by replacing the expert's original policy in the SCM M with л, which gives the results of the imitator's is actions as P(V]do(=)) Our goal to learn an imitating policy и such that the induced distribution P(Y]do(zz) perfectly matches the original expert's performance P(Y). Formally
Definition 2.1. [hhagg et al. 2020) Given causal diagram G. Y C V is said to be imitable with respect to actions X C O in 9 if there exists πT E uniquely discernible from the observational distribution P(O) such that for all possible SCMs M compatible with g. P(Y) P(Y P(Y|do((T))
In other words, the expert's performance on reward Y is imitable if any set of SCMs must share the same imitating policy E II whenever they generate the same causal diagram & and the observational distribution P(O). Henceforth, we will consistently refer to Def. 1 as the fundamental problem of 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 C beforee X such that (Y IL X xxx) called the backdoor admissible set, (Pearl 2000 Def. 3.3.1) (Z = B.
in Fig. la.. It is verifiable that an imitating policy is given by π [ B) = P(X
Since the backdoor criterion is complete for the single-stage problem, one may be tempted to surmise that a version of the criterion generalized to multiple interventions might likewise solve the imitability problem in the general case (IX) > 1). Next we show that this is not the case. Let X stand for
a sequence of variables {XI...... X; X = 0 i < 1. Pearl & Robins 1995) generalized the backdoor criterion to the sequential decision- makinng setting as follows:
Definition 2.2. (Pearl & Robins 1995) Given causal diagram G, a set of action variables X. and target node Y, sets Z1 C (xi). Zn C. before(X,)) satisfy the sequential backdoor for X, for each X; E X such that (Y TL X, 1 Zia) (11))x,7 6x,x.11'
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. ld In this case, Z1 = 0, Ze {Z). {(X1, (X,, [2)} } is sequential backdoor set for (g. {X X2). ). 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 ~ (ern((.5), with X1 == U1. Z == U1 + U2. X2 == Z and Y = -(X, + X₂ + U2), with @ as binary XOR. The fact that U U is exploited generate chain where each latent variable appears exactly twice in Y. making Y -UU @ (U, e U2) @ U2) = 1. On the other hand, when imitating, X₁ can no longer base its value on U1, making the imitated y = -(,, + X2 @ U2). The imitator can do no better than Ely] = 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 Z₁ C before(X1),.... Zn S before(Xn). let G/, i = I,..., n, be the manipulated graph obtained from causal diagram G by first (1) removing all arrows coming into nodes in X and (2) adding arrows Z++1 + X Zn + X,, We can then define a sequential backdoor criterion for causal imitation as follows:
Definition 2.3. Given causal diagram G. set of action variables X, and target node Y, sets Z1 C beefoe(X.)..... Zn C (efore(XX)) satisfy the "sequential x-backdoor [foor XY if at each X, E X, either (1) (X, 11 Y Z)Z,) in (G))x, or (2) X, & An(YY) in G/
The first condition of Def. 2.3 is similar to the backdoor criterion where Z, is set of variables that effectively encodes all information relevant to imitating X, with respect to Y. In other words, if the joint P(Z, U (X+)) matches when both expert and imitator acting, then adversarial Y cannot distinguish between the two. The critical modification of the original --cckoooor for the sequential setting comes from the causal graph in which this check happens. G can be seen as with all future
'The in backooroo"" is part of the name, and does not refer to any specific policy.

---

X2
X
w
X2
W
X
(a)
(b)
(c)
(d)
j. so X2 has its parents cut, Figure 3: Examples of 9j. In Fig. Ic we can have Zi 0, Z2 ]
and a new arrow added from Z to X2 (blue). The independence check (X; 11. Y is done in graph (ap with edges outgoing from X1 removed (orange). In Fig. 2b using Zi 0, Z2 (X1). we first replace the parents of X2 with just X1 (b). and then remove both resulting outgoing edges from X, to check if (X1 TL Y). On the other hand, in Fig. 2c if Ze {Z). we get (c). which
means X, & AY(Y), passing condition 2 of Def. 2.3 Finally, in Fig. 2d with Zo = {W}, X1 must
condition on either Z or W to be independent of d once the edge X1 + Y is removed.
actions of the imitator already encoded in the graph. That is, when performing check for X,, it is done with all actions after being performed by the imitator rather than expert, with the associated parents of each future xイ>s replaced with their corresponding imitator's 's conditioning set. Several examples of G are shown in Fig.
The second condition allows for the case where an action at X; has no effect on the value of Y once future actions are taken. Since 9 has modified parents for future Xj>i, the value of X; might no longer be relevant at all to Y. i.e. Y would get the same input distribution no matter what policy is chosen for X, This allows X, to fail condition (I), meaning that it not imitable by itself, but still be part of an imitable set X, because future actions can shield Y from errors made at X;
The distinction between condition and condition 2 is shown 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 X₃ (i.e. Rx, P(X₂ (Z), X1 will no longer be an ancestor of Y in gi- In effect, the action made at X2 ignores the inevitable mistakes made X, due to not having access to confounder Un when taking the action.
Indeed, the sequential π ---bckddoor criterion can be seen as a recursively applying the single-action r-backdoor. Starting from the last action X₃ in temporal order, one can directly show that Y is imitable using a backdoor admissible set Z& (or X₁ doesn't 't affect Y by any causal path). Replacing Xx in the SCM with this new imitating policy, the resulting SCM with graph G¹ has an identical distribution over Y G. The procedure then be repeated for Xk-1 using Gk the starting graph, and continued recursively, showing imitability for the full set:
Theorem 2.1. Given causal diagram G, a set of action variables X, and target node Y, if there exist sets Z1, Zz...., Zy that satisfy the sequential π T-backdoor criterion with respect to (G, X. Y), then Y is imitable with respect to X with policy π (X. P(X, Z.) for each X, E X.
Thm. 2.1 establishes the sufficiency of the sequential r-backdoor for imitation learning. Consider again the diagram in Fig. 2c It is verifiable that covariate sets Z 0, Ze = {Z) are sequential r-backdoor admissible. Thm. 2.1 iimlies that the imitating policy given by mh (X,)
P(X;)
and (x2) = P(x Z). Once ग --backdoor admissible sets are obtained, the imitating policy can be learned from the observational data through standard density estimation methods for stochastic policies, and supervised learning methods for deterministic policies. This means that the sequential b-bcckdoor a method for choosing a of covariates
when performing imitation learning, which can be used instead of Pa(X,) for each X, E X in the case when the imitator does not observe certain elements of Pa(X). With the covariates chosen using the sequential π T-backdoor, one can use domain-specific algorithms for computing an imitating policy based on the observational data.
3 Finding Sequential 7 7-Backdoor Admissible Sets
At each X,, the sequential n-backdoor criterion requires that Z, a back-door adjustment set in the manipulated graph G/. There already exist efficient methods for finding adjustment sets in the
5

---

literature (Tian & Paz 1998: van der Zander & Liskiewicz 2020), so if the adjustment were with reference to G. one could run these algorithms on each X; independently to find each backdoor admissible set Z, However, each action X; has its Z; in the manipulated graph 9% which is dependent on the adjustment used for future actions X4+1mn- This means that certain adjustment sets Zj for X jis will make there not exist any Z; for X; in Gj that satisfies the criterion! As an example. in Fig. [c] X2 can use any combination of Z, X1, W as a valid adjustment set Zz. However, if Z comes after X1 in temporal order, only Z2 {Z} leads to valid imitation over X X2).
The direct approach towards solving this problem would involve enumerating all possible backdoor admissible sets Zi for each X,, but there are both exponentially many backdoor admissible sets Z, and exponentially many combinations of sets over multiple X Such a direct exponential enumeration is not feasible in practical settings. To address these issues, this section will see the development of Alg. [ which finds a sequential r-backdoor admissible set Zi... with regard to actions X in causal diagram G in polynomial time, if such set exists.
Before delving into the details of Alg. [ we describe method intuitively motivated by the "Nearest Separator" from Van der Zander et al. (0155) that can generate a backdoor admissible set Z, for single independent action X; in the presence of unobserved variables. While it does not solve the problem of multiple actions due to the issues listed above, it is a building block for Alg. !
Consider the Markov Boundary (minimal Markov Blanket, Pearl 1988) for set of nodes which is defined as the minimal set Z C O \ O* such that (O can be applied to graphs with latent variables, where it can be constructed in terms of e-components:
Ox Z). This defimition
Lemma 3.1. Given O* C the Markov Boundary of Ox in G is Pat (C(Ck
\ Ox
If there is set Z S before X;) that satisfies the backdoor criterion for X, with respect to Y, then taking GY the ancestral graph of Y, the Markov Boundary Z' of X, in g% has Z' C befoor(X,)) and also satisfies the backdoor criterion in G (Lem. C.T). The Markov Boundary can therefore be used to generate a backdoor adjustment set wherever one exists.
A naive algorithm that uses the Markov Boundary of X, E X in (9)), as the corresponding Z, and returns failure whenever Z, & before(X,) for the sequential r-backddor is equivalent to the existing literature on finding sackdoor-admissible sets. cannot create valid sequential π r-backdoor for Fig. 2c since X2 would have Z₂ (W), but no adjustment set exists for X1 that d-separates it from Y in the resulting G/- We must take into account interactions between actions encoded in 9%-
We notice that an X, does not require a valid adjustment set if it is not an ancestor of Y in S (i.e. X; does not need to satisfy (1) of Def. 2.3 if it can satisfy (2)). Furthermore, even if X; is an ancestor of Y in Go and therefore must satisfy condition (1) of Def. 2.3 any elements of its c-component that are not ancestors of Y in G won't 't be part of (g))), Y. and therefore don't 't need to be conditioned.
It is therefore beneficial for an action X, to have a backdoor adjustment set that maximizes the number of nodes that are not ancestors of Y in 9/ so that actions Xi<, can satisfy (2) of Def. 2.3 if possible, and have the smallest possible c-components in (G)) (increasing likelihood that backdoor set Z, C before(X.) (X.) exists if X, must satisfy condition (1)).
To demonstrate this intuition, we once again look at Fig. 2c focusing only on action X2. If we were to use {W} as Zz, we still have the same set of ancestors of Y in G¹. If we switch to {X,} }. then W would no longer be an ancestor of Y in 9 meaning that X2 is better as a backdoor adjustment set for X₂ than {W} } if we only know that X₂ is an action (i.c. W would directly satisfy (2) of Def. 2.3
it were the other action). Finally, using { (Z) as Z₂ makes both X2 and W no longer ancestors of Y in Øi, meaning that it is the best option for the adjustment set Zz-
FINDOX in Alg. [ employs the above ideas to iteratively grow set OX C O of ancestors of X (and including X) in G whose elements (possibly excluding X) will not be ancestors of Y once the actions in their descendants are taken. That is, an element O E O* where ch (O,) c O is not present in (g)) Y for all actions X, that come before it in temporal order. Combined with the Markoy Boundary, FINDOX can be used to generate sequential r-backdoors.
We exemplify the use of Alg. through Fig. 2c x represents a map of observed variables which are not ancestors of Y in Gi to the earliest action X, in their descendants. The keys of O will be
the set O Considering the temporal order (X1, Z, W, X2, Y). the algorithm starts from the last

---

Algorithm 1 Find largest valid Ox in ancestral graph of given G. X and target Y
1:
function FASVALIDADIUSTTENTTG O .0,...)
2: C' f the c-component of of in GY
3: Gc f the subgraph of G¹ containing only (C) and intermediate latent variables
4: OC CC) (Ox U (O,)) (elements of e-component that might be ancestors of Y in 9))
5:
return (O, II 00 (Oc before(X:))) in 9c
6:
function FINDOX(G,XX))
7: Ox + empty map from elements of O to elements of X
8:
do
9:
for O, E Of G (ancestral graph of Y) in reverse temporal order do if ch Mrlch+(O0 (O,)) 0 and ch (O.) S keys then
11:
X; earliest element of 6* ch (ch (O,)) in temporal order
12:
if HHASAAAIIAADUSTTENTTT........ (.0..) then
0x10, - X;
14:
else if O, E X and HAS HASYAALDDDDDDSTTMETTTTCCAACCAAO, then 0x [xOO + O;
15:
while |0 changed in most recent pass
17:
return (xy)((x))
node, Y, which has no children and is not an element of X, so is not added to Øx It then carries on to X2, which is checked for the existence of valid backdoor adjustment set. Here, the subgraph of the c-component of X2 and its parents (HAS AAAAVVAALIAAIUSTMMENTT is simply W that we can condition on W to make X2 independent of all other observed variables. including Y, in Gx2 (W a Markov Boundary for X2 in Gx.). The algorithm therefore sets 6x {X2 : X2). because X2 is action with valid adjustment set. Notice that if the algorithm returned this point with O = {X2). the Markov Boundary of O in 9x2 is W, and corresponds to a sequential T-backdoor for the single action X2 (igmoring X1), with policy x(X2 = PW)
meaning
Next, W has X₂ its only child, which itself maps X₂ in Ox The subgraph of W's c-component and its parents is
W. giving (W TT O|Xi)ew and {{1] S before(X2). allowing us to conclude that there is backdoor admissible set for X2 where W is no longer an ancestor of Y. We set Ø {X2 X2, W : X2), and indeed with O* = (X2, W}, the Markov Boundary of O in 9x2 is X1, and is once again valid sequential π r-backdoor for the single action X₂ (ignoring X1).
with policy π (1) (1) The W in O* was correctly labeled as not being an ancestor of Y after action X2 is taken.
Since Z doesn't have its children in the keys of Ox and is not element of X, it is skipped, leaving only X2. X1 's children (W) are in Ox we check conditioning using X2 instead of X1 (i.e. we check if X, can satisfy (2) of Def. 2.3 and not be ancestor of Y in Gr., This time, we have X: X+ Z as the c-component subgraph, and comes before X2, satisfying the check
(X, Z Z) in HASVALIDADIUSTMENT resulting in O% = {X2 : X2, W X2, X, : X22), and 0x= (X2, W, X.). Indeed, the Markov Boundary of O in 9x2 is [2), and we can construct valid sequential babakkdoor by using Z {} and Zn {Z}, where X1 is no longer an ancestor of Y in Gi ! In this case, we call X₂ a "boundary action", because it is an ancestor of Y in G. On the other hand, X, is not boundary action, because it is not an ancestor of Y in Ø/-
Definition 3.1. The set X B C called the "boundary actions" for Ox = FINDOX X, X) are all elements X; E X O where ch+ (Xx) & Ox
Alg. | is general: the set O returned by FINDOX can always be used in conjunction with its Markov Boundary to construct a sequential T- n-backdoor if one exists:
Lemma 3.2. Let Ox = LI, and X' = O n X. Taking Z as the Markov Boundary of x in G and 8 as the boundary actions of OX the sets Z, = (Z x ))
before(X!) for each X E X' are a valid sequential क babakkoorr for (9, X',Y)
7

---

Lemma 3.3. Let O* = FINDOX X,Y, Y). Suppose that there exists sequential x x-backdoor for X" C.X Then X CO
Combined together, Lems. 3.2 and 3.3 show that FINDOX finds the maximal subset of X where sequential 7 r-backdoor exists, and the adjustment sets Z can he constructed using the subset of a Markov Boundary over Ox that comes before each corresponding action X; (Lem. 3.2p. FINDOX is therefore both necessary and sufficient for generating sequential π n--bckdoor:
Theorem 3.1. Let O* be the output of FINDOX (A, X,Y). A sequential r-backdoor exists for XY) if and only if X C Ox
4 Necessity of Sequential r-Backdoor for Imitation
In this section, we show that the sequential n-backdoor is necessary for imitability, meaning that the sequential π --backdoor is complete.
given imitation problem can have multiple possible conditioning sets satisfying the sequential π- m-backdoor, and violation of the criterion for one set does not preclude the existence of another that satisfies the criterion. To avoid this issue, we will use the output of Algorithm FINDOX, which returns a unique set O for each problem:
Lemma 4.1. Let Ox : FINDOX(G, X,Y). Suppose EX; E X s.t. X, E Ox Then X is not imitable with respect Y in
Our next proposition establishes the necessity of the sequential r-backdoorr criterion for the imitability of the expert's 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 r-backdoor criterion for (, Y), then X is not imitable with respect Y in G.
The proof of Lem. 4.1 relies the construction of an adversarial SCM for which Y can detect the imitator's '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 ~ (0r5( X == U, Z == U,Y
Y == X + leaves the imitator with a performance of E| = 0.5, while the expert can get perfect performance (ElY) 1).
Another example with similar mechanics can be seen in Fig. 2c If the variables are determined in 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 taken without context.
Finally, observe Fig. 2d If Z is determined after X1, the imitator must guess value for X1 without this side information, which then combined with U2 W. An adversary can exploit this to construct a distribution where guessing wrong can be detected at Y as follows: U₁ ~ Bern(0.5)) = U1. U2 (0.5.. (055)) (that is, U2 is a tuple two binary variables, or single variable with uniform domain of 0, 1, 3). Then setting W [2[2] (1 represents array access, meaning first element of tuple if = and second if Z = 1), and X₂ := W. Y = (U2[X,] =- X₂) gives E|y] 1 only if лΙ guesses the value of U1. meaning that the imitator
never achieve the expert's performance. This construction also demonstrates non con-imitability when X1 and are switched (i.c.. Fig. 2c with W ++ Y added, and X; coming before Z in temporal order).
Due to these results, after running Alg. 1 on the domain's causal structure, the imitator gets two pieces of information:
1. Is the problem imitable? 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 of which is correct (known as "Simpson's 's Paradox" in the statistics literature (Pearl 2000)). Furthermore, as demonstrated in Fig. 2c when performing actions sequentially. some actions might not be imitable themselves (Xx if Z after X1), which leads to bias in observed

---

#
Structure
Order
Seq. r-Backdoor
π Backdooor
Observed Parents
All Observed
2.X,
0.04 + 0.04%
0.04 0.03%
0.05 0.04%
0.13 0.18%
X
2
2.X,
0.05 + 0.03%
0.05 0.03%
0.20 + 0.25%
0.05 + 0.03%
Xa.Y
3
x,
0.04 + 0.03%
Not Imitable
0.27 + 0.40%
0.26 + 0.39%
X,,Y
4
X,
Not Imitable
Not Imitable
0.19 + 0.29%
0.19 + 0.29%
X,
Table 1: Values of [E[]] E| 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 Z; for every action X, could be be used as input to existing algorithms for behavioral cloning, giving an imitating policy with an unbiased result.
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 imitating policy:
1. All Observed (AO) Take into account variables available the imitator the time of each action. This is the approach most commonly used in the literature.
2. Observed Parents (OP) The expert used set of variables to take an action use the subset of these that are available the imitator.
3. π r-Backdoor certain cases, each individual action can be imitated independently, so the individual single-action covariate sets used.
4. Sequential r-Backdoor (ours) The method developed in this paper, which takes into account multiple actions sequence.
The first simulation consists of running behavioral cloning on randomly sampled distributions consistent with a se- ries 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 pol- icy X was replaced with imitating policies approximating or (X;) P(Xx|clar( (X,)), with context clar determined by each of the tested methods in turn. Our results are shown in Table with causal graphs shown in the first column, temporal ordering of variables the second column, and absolute distance between expert and imitator for the 4 methods the remaining columns.
Adversarial Method Comparison
0.2
0.1
0.0
OP
AO
SnBD
OPT
Figure 4: Results of applying supervised learning techniques to continuous data with different sets of variables as input each action. OPT is the ground truth expert's performance, Br represents our method, AO is all observed. and OP represents observed parents.
In the first row, including Z when developing a policy for leads to biased answer, which makes the average emoor of using all observed covariates (red) larger than just the sampling fluctuations present in the other columns. Similarly, Z needs to be taken into account in row 2, but

---

it is not explicitly used by X, so a method relying only on observed parents leads to bias here. In the next row, Z is observed at the time of action X,, making the x-backdoor incorrectly claim non-imitability. Our method recognizes that X2's policy can fix the enror made at X1, and is the only method that leads an unbiased result. Finally, in the 4th row, the non-causal approaches have no way to determine non-imitability, and return biased results in all such cases.
The second simulation used a synthetic, adversarial causal model, enriched with continuous data from the HighD dataset (Krajewski et al. 2018) altered to conform to the causal model, to demonstrate that different covariate sets can lead significantly different imitation performance. A neural network was trained for each action-polics pair using standard supervised learning approaches, leading to the results shown in Fig. 4 The causal structure was not imitable from the single-action setting, so the remaining 3 methods were compared to the optimal reward, showing that our method approaches the performance of the expert, whereas non-causal methods lead biased results. Full details of model construction, including the full causal graph are given in (Kumor et al. 2021, Appendix B)
6 Limitations & Societal Impact
There are two main limitations to our approach: (1) Our method focuses on the causal diagram, requiring the imitator to provide the causal structure of its environment. This is 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). Data- dependent methods approach returns "imitable", then the resulting policies are guaranteed to give perfect imitation, without needing to process large datasets to determine imitability.
be computationally intensive, often requiring density estimation. If our
Finally, advances in technology towards improving imitation can easily transferred to methods used for impersonation a target (Y) into believing they are interacting with a known party (expert). Our method shows when it is provably impossible to detect an impersonation attack. On the other hand, our results can be used to ensure that the causal structure of a domain cannot be imitated, helping mitigate such issues.
method provides conditions under which an imposter (imitator) can fool
Conclusion
Great care needs to be taken in choosing which covariates to include when determining policy for imitating an expert demonstrator when expert and imitator have different views of the world. The wrong set of variables can lead biased, 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 authors were partially supported by grants from NSF IIS- 1704352 and IIS- 1750807 (CAREER). Daniel Kumor also acknowledges additional revenue from an internship at Amazon.
References
Abbeel, P. and Ng, A. Y. Apprenticeship learning via inverse reinforcement learning. In Proceedings of 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 from
demonstration. 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 Gar- nett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran
10

---

Associates, Inc., 2019. URL https://proceedinngs wttp://gg....rri..ooooooooo http://cccaccaaooopooooopoopo//p 947088800E5222000155777666359999
Etesami, J. and Geiger, P. Causal transfer for imitation learning and decision making under sensor- shift. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, New York, NY, 2020.
AAAI Press.
Hussein, A., Gaber, M. M., Elyan, E., and Jayne, C. Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR), 30,2):1-35,20 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 german highways for validation of highly automated driving systems. In 2018 2 International Conference on Intelligent Transportation Systems (ITSC), pp. 2118-2125, 2018. doi: 10.1 10.1109/TSC.2218885555555
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. 13 [cs], December 2013.
Muller, U., Ben, J., Cosatto, E., Flepp, B., and Cun, Y. I.. Off-road obstacle avoidance through end-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, Causality: Models, Reasoning and Inference. 2000.
Pearl, J. and Robins, J. M. Probabilistic Evaluation of Sequential Plans from Causal Models with Hidden Variables. 1rX.v: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, 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 apprenticeship learning. In Advances in neural 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.

---

van der Zander, B. and Liskiewiez, 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, Efficiently finding conditional instruments for causal inference. In Twenty-Fourth International Joint Conference 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. 4433-1438 Chicago, IL, USA, 2008
12


Reviews:
[{"review_id": "wWH9fZTxhva", "reviewer": "Reviewer_aRng", "summary": "This paper extends the results of Zhang et al. (2020) to sequential contexts, where the goal is to reproduce the behavioural distribution using a sequence of interventional policies, rather than just a single one. The paper provides natural generalisations of the definitions and results of Zhang et al. (2020) for this scenario, as well as an algorithm for finding conditioning sets for this interventional policy, and some experimental results.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The extension to Zhang et al. (2020) considered, while conceptually straightforward, clearly does involve additional technicalities and difficulties that make it worthy of separate study. This paper introduces various results for doing so that seem to be a useful contribution to the literature. In particular, the necessary and sufficient characterisation of imitability (Theorem 2.1 and Theorem 4.2) seems to be of particular interest to the community.\n\nThe main shortcoming of the paper is its clarity: several sections are difficult to parse (e.g. Section 3) due to the highly dense notation used, especially when describing graphical concepts. This may be somewhat inevitable given the reliance on graph theoretic ideas throughout, but the paper would benefit from any efforts made by the authors to improve clarity. For example, Algorithm 1 is quite opaque to me. (For example, although the authors motivate this from the perspective of wanting to avoid an exponential blowup, the actual complexity of Algorithm 1 that they achieve is unclear to me.) In addition, please see below for several more low-level points that are illustrative of other improvements that could be made to the paper throughout:\n\n* Line 99 - \"if it contains a collider (-> A <-) only if $A \\in An(W)$\" - this is unclear\n* Line 106 - \"c-component\" is not defined previously (\"confounded component\" is, which I assume is what is meant)\n* Line 127 - The terminology \"uniquely computable\" is a bit misleading since the issue is not around computability but really around identifiability. In addition, it doesn't seem to matter if there is more than 1 $\\pi$ for which the observational distribution matches the interventional one (i.e. \"uniqueness\" is potentially misleading, unless I am misunderstanding)\n* Line 158 - It is unclear what the meaning of $\\pi$ is in the definition - the definition applies just with regards to the causal model, and does not need to refer to any policy\n\nFinally, the experimental section is somewhat underdeveloped. For example, it is not at all clear what is going on in the HighD experiment from the paragraph given in Section 5.  (Figure 4 does not even label its vertical axis, so that it isn't even clear what metric is being compared - I am guessing $E[Y]$.) The Supplement does help, but e.g. it is unclear how the policy is being evaluated, given that the dataset is static, and so would seem to require OPE techniques. Likewise, for the synthetic data, I was confused about why $|Y - \\hat{Y}|$ was used as the relevant metric to consider - according to Definition 2.1, what matters is just that the interventional distribution match the behavioural distribution, not the comparison between counterfactuals. I.e. $|E[Y] - E[\\hat{Y}]|$ seems more appropriate (unless I am misunderstanding what is meant by $|Y - \\hat{Y}|$).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors appear to have covered adequately the limitations and potential negative impacts of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "Rkp8uK4xG4", "reviewer": "Reviewer_N9bU", "summary": "This paper seeks to formalize when it is possible to imitate an expert when the learner and the expert have access to different observations. This is a novel problem that is important. The authors consider graphical models representing simplified imitation learning settings and develop necessary and sufficient conditions for knowing when a learner can exactly imitate the expert.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper seems like a solid theoretical study of imitation learning. I am concerned that the assumptions may make it only interesting theoretically; however, I think the theory provided is a good start towards a better understanding of causality and imitation learning. In particular, the analysis and experiments seem to rely on the assumption of binary decision variables and learning a unique policy for every individual state, which seems unlikely to have much impact on imitation learning in practice. \n\nI like the example given in Fig 1 of a car learning to drive but not  having access to auditory signals that the human expert may be using. However, despite the nice grounding of the high-level problem, I found the details hard to follow. It would be nice to ground the actual policy, observations, and reward in plain english and ground them to the driving example. Also the paper is very dense and difficult to follow with notation often being used before it is defined. For example lines 80-86 use pa() and U_V without defining either. I understand this is a theoretical paper, but as someone with no background in causality I would have appreciated a bit more hand holding and grounded examples. As written it is hard grasp the concepts or see how they could inform better algorithmic advances for actual imitation learning problems.\n\nIn terms of related work, I was surprised to see no mention of de Haan et al.  \"Causal confusion in imitation learning.\" NeurIPS 2019. This paper seems highly relevant as it also considers sequential imitation learning and causality. I would like to know how the current approach is related to this prior work.\n\nI appreciate the effort to run realistic experiments, but the details of the HighD experiments make it difficult to tell whether these experiments are realistic or even need real data. Since you are using actual recorded data is performance simply measuring the accuracy of the predicted actions? Also it appears that the actions are only binary which doesn't seem realistic. It seems that too much effort has been made to make the experiment seem more realistic than it is by putting all the details in the appendix. In particular, it appears that there is a separate BC model for each action which does not match how BC is usually applied. Is it possible to learn a BC model that works for every state?\n\n---\n\nPost Rebuttal:\nThe authors have sufficiently addressed my questions. The experiments are idealized and simple. I agree that the contribution is mainly theoretical and the paper seems to make important theoretical contributions; however, it would be nice to have a discussion section, even in the supplement, which highlights potential ways to make the proposed method work on realistic problems. After reading the author responses and other reviews I have moved my score to an Accept.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "6w-sSRllN8R", "reviewer": "Reviewer_mSFc", "summary": "This paper studies the task of imitation learning in the presence of confounding variables which are not available to the imitation learning system. For example, data from human drivers where the drivers use sound to make decisions may be interpreted incorrectly by the IL system if it has no access to audio data. The authors apply tools from causal inference to approach this problem. The authors develop a backdoor criterion for the sequential RL setting, extending previous work on causal imitation in bandit setting. The authors provide an algorithm to efficiently find covariates which the policy should depend upon in order to correctly imitate. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Causal imitation learning is an exciting topic. It seems that research in this area could be very useful, as we increasingly deal with diverse input data from multiple sources and multiple input modalities. I'm not an expert in causal inference, which comprise the majority of the technical contributions of this paper. Based on my understanding, it seems that this paper makes a solid contribution to the understanding and application of causal inference to imitation learning. \n\nOne contribution of this paper is the extension of previous work in the bandit setting to the sequential setting, developing the idea of a 'sequential $\\pi$-backdoor' to characterise which covariates a policy should depend on at each timestep, in order to properly recover the reward in a way that doesn't fail due to confounders. I think the key contribution is the algorithm FIND_OX, which recovers a set of covariates that the policy should depend on, in a way that is more practical than the naive method of trying exponentially many candidate covariate sets. Experiments show that this method leads to less causal misidentification than the naive behavioural cloning based on all observables. \n\nThe paper doesn't reference or discuss some previous work that seems relevant [Haan, 2019], discussing similar issues and introducing an algorithm to deal with causal misidentification. Could the authors discuss the relevance of this paper to the present work, and perhaps a comparison to the $\\pi$-sequential backdoor could be made?\n\n\nOther questions for the authors:\n+ It seems like the examples only have tabular settings at the moment where the policy depends on categorical covariates. Are there any obstacles to using continuous rvs $X, Z$ etc? Perhaps in higher dimensions some techniques from MBRL could be used to distil out the relevant causal variables [Ke, 2021].\n+ In the driving example, it seems that the causally imitable policy we must have a policy which depends on a large number/almost all of the previous variables (while the original policy is Markov). It seems like this could cause a problem for environments with large numbers of timesteps. Is the requirement of the policy relying on many/all previous timesteps a general feature of causal imitation learning for many environments? Is it possible to use FIND_OX to choose between the possible sequential $\\pi$-backdoor conditioning sets to find the one where the policies depend on the smallest number of covariates?\n\nTypos:\nIn the caption of figure 3, should 'which means $X_i \\in \\text{An}(Y)$' read 'which means $X_1 \\in \\text{An}(Y)'$?\n\nAs a minor point, it could be useful to clarify early in section 2.1 that the goal is to find  $Z_i$. When initially reading I thought that $Z_i$ was given as part of the problem definition, resulting in a bit of confusion. \n\nHaan et al, Causal Confusion in Imitation Learning, Neurips 2019\nKe et al, Systematic Evaluation of Causal Discovery in Visual Model Based Reinforcement Learning, arxiv 2021\n\n----------------------------------------------------\nUpdate after author rebuttal (16/08/2021):\nThanks to the authors for the replies, and particularly in addressing the question of relevance of Haan 2019. After reading the paper again and all the reviews and replies, I don't see any reason why this paper should not be accepted: I keep my score at 7.\n----------------------------------------------------", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "-mCP8mYs_rQ", "reviewer": "Reviewer_WPhA", "summary": "This paper presents a necessary and sufficient graphical criterion for the feasibility of causal imitation learning. It extends previous work (Zhang et al.) to handle the situation where the causal graph has several decision nodes, rather than just one. Additionally, it derives and algorithm for efficiently testing the proposed graphical criterion and, when possible, choosing an appropriate set of variables to condition on during IL. Experiments demonstrate the proposed algorithm working as expected on illustrative synthetic datasets, and shows similar results for a semi-synthetic dataset based on HighD.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provided a clear exposition of a complete solution to a problem of common interest in the decision-making community (that is, how you can robustly imitate demonstrators that do not share the same set of sensors as the imitator). I appreciated the crisp examples and explanatory asides throughout the paper. The main limitations of the proposed framework are fairly straightforward and already covered in Section 6. However, the fact that each experiment is mostly or entirely synthetic is IMO also a weakness of the paper—given that the data is constructed to meet the assumptions of the method, it feels like the experiments do not add much over the mathematical results. It would be great to see this framework fruitfully applied to an \"in the wild\" problem in a future paper.\n\nA few minor comments on clarity, etc.:\n\n- Definition 1.1: space permitting, it might save the reader some time if the paper explains why c-components are a useful concept.\n- Definition 2.2: the end of this definition seems to be missing. It says \"if for each $X_i \\in \\mathbf X$ such that &lt;condition&gt;\" and then stops.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, limitations and societal impact were appropriately addressed.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper seeks to formalize when it is possible to imitate an expert when the learner and the expert have access to different observations. This paper seems like a solid theoretical study of imitation learning.
The authors consider graphical models representing simplified imitation learning settings and develop necessary and sufficient conditions for knowing when a learner can exactly imitate the expert.
The rebuttal also provides sufficient answers to reviewer concerns. The main shortcoming of the paper is its clarity of presentation and exposition. 
The authors should improve the draft as per the reviewer suggestions, and despite remaining concenrs, this paper provides an interesting result for the community to justify acceptance. 
Decision: Accept (Oral)