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 are 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 {=1 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 & 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 WV, 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. [hhag 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 ((Y())((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- makiing 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)sx,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-1 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 muckdoor-admissibee 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 Gt 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 HASYALLDADDDSSTMENTTK.KKCCCOOO.O 0x [xOO + O;
then
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 X2 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. T-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 cwtp://gg....rri..ooooooooooooo http://cccaccaaooopooooopoopo//p B7705650060000606333222222-22
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": "sdaBSohrWnN", "reviewer": "Reviewer_3m9X", "summary": "This paper investigates the problem of determining imitability in casual imitation learning in sequential settings. This is an extension from a previous work that studies the same problem in single-stage settings. The authors propose necessary and sufficient conditions for determining whether an imitator is able to unbiasedly imitate a demonstrator given a causal diagram. The authors further develop an efficient algorithm that outputs 1) whether such conditions are met and 2) a set of observable variables as inputs to the imitator policies to unbiasedly imitates the demonstrator. In addition, the authors demonstrate the performance of the algorithm and the usefulness of the conditions on both synthetic and real-world data. \n", "questions": "", "limitations": "", "rating": 7, "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 paper contributes to the foundations of imitation learning and attempts to answer an important question of whether an imitator is able to imitate a demonstrator if there exists sensor input mismatch. The results of the paper are applicable to all causal diagrams beyond Markov Decision Processes (MDPs). I think such fundamental research largely increases the practicality of imitation learning to fields that require formal guarantees, and provides a promising direction to understanding imitation learning. \n\nHowever, I have some concerns of the practicality of the results on high-dimensional and complex problems. For example, t\nhe conditions proposed can determine whether a demonstrator can be imitated unbiasedly, but they do not answer other practical questions such as (1) in the biased case what variables should be used, and (2) given a finite amount of data, whether the set of variables found by Algorithm 1 is always better than other set of variables that do not guarantee imitability. But I think this paper is a good start to address these questions. \n\nOther comments:\n\nThe efficiency of the Algorithm 1. The authors mention that this avoids the exponential complexity due to the need of checking all backdoor admissible sets. What’s the computational efficiency of Algorithm 1 then if not exponential? The experiments do not demonstrate the efficiency of the proposed algorithm as the structures considered in the synthetic experiments are rather small.\n\nI think the authors did a good job in making this paper accessible to readers who are not familiar with do-calculus. However, the exposition of the theorems and the algorithm is a bit abstract. Is it possible to have a running tangible example? In addition, it would be great if the motivating car example in Page 2 can be improved. It’s a bit confusing, especially before I read Section 1.1. In L44, “the learner from Fig.1a had a full view of the car’s surroundings”. Which node in Fig. 1a corresponds to the learner? Based on the text, X is the human driver. If X also represents the learner, X does not seem to have access to a full view of surroundings as it is only connected to F (“looking forward”) and H (“car horns”). Furthermore, the mean of E[Y|do(\\pi)] was not explained. And there is no concrete meaning of X being 0 or 1. \n\nThe results in the paper hold for non-stationary policies, i.e. having a distinct policy at every time step. Are the results applicable to stationary policies and infinite horizon settings as non-stationary policies are more expensive to learn and maintain? \n\nIn L 118, the authors mentioned that besides a causal diagram, a topological ordering is required. Is that a total ordering of all variables as in the Order column in Table 1?\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": "4 hours"}, "extra_text": {}}, {"review_id": "gw5OARU3J-k", "reviewer": "Reviewer_1SfX", "summary": "This paper studies the problem of imitation learning when the expert and learner differ in their available information and input. The authors extend the work of Zhang e al., 2020 from single stage to the sequential setting. A necessary and sufficient graphical criterion is proposed to determine if optimal imitation (P(y | do(pi)) = P(y)) is possible. An algorithm to determine the set of covariates enabling such imitation is also proposed. Experiments showcasing the value of the new approach are conducted on synthetic and semi-synthetic data.", "questions": "", "limitations": "", "rating": 7, "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 strengths of this paper are the nice theoretical extensions to  Zhang e al., 2020. Naively applying  Zhang et al., 2020 to the sequential case by considering each sequential action independently may incorrectly prescribe “not-imitable” to some graphs, The new graphical criterion in this work considers all sequential actions in conjunction (using similar flavoured techniques as sequential backdoor) to give the correct result. The algorithm to determine which covariates to use is also useful and surely will lend itself to new applications.\n\nThe first weakness of this paper is strong assumptions needed, thus limiting its practicality. The main concern of the paper is the very strong imitability criterion P(y | do(pi)) = P(y). In practice we may be more concerned with simply maximizing E[y] even if a graph is not truly imitable. However because this work is data independent, this is something that cannot be handled. \n\nAnother strong assumption is that the full causal graph has to be known and specified a priori. While this assumption is probably very difficult to remove completely, it could be taken into consideration by providing error bounds for mismatched causal graphs, etc. \n\nI also wish that the causal graphs studied were more realistic. For example, the HighD experiment’s example of air conditioning being the collider for mental state and road conditions feels a bit artificial. I understand that the experiment is largely meant to be illustrative, but it is nonetheless a weakness. Given that the method requires the full causal graph, it is more likely that practitioners will come up with more simple and structured graphs rather than intricate and detailed ones. For example, it may be more practical if the authors could have studied graphs of particular structure (e.g. block MDPs), which seems to be more likely to be used in the real world. Likewise, the current analysis requires different covariates for each step, with no clear solutions for infinite (or long horizon) settings with some repeated structure, which seem to be the predominant setting in the real world.\n\nDespite deferring the bulk of the proofs to the appendix, the paper is still quite dense due to its heavy use of inline notation. But given the nature of the work I’m not sure how avoidable it is. Perhaps using more of the high level examples (sound of horn, etc.) in place of the later examples of SCMs with xor functions, etc. could make the paper more approachable.\n\nOverall I feel the paper makes some solid contributions, and will update my score if some of the concerns can be addressed.\n\n---\n**EDIT**: I have updated my score, for more details see the reply to the author's response.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed them well.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "eTrON3K6TUU", "reviewer": "Reviewer_rfa1", "summary": "The paper proposes to study causal imitation learning in a sequential framework by taking advantage of the structure of the causal graph. The authors present a necessary and sufficient criterion, distinct from the sequential backdoor criterion, in order to allow the feasibility of a causal imitation learning algorithm. Finally, the authors propose an algorithm to make it possible to define whether such a criterion is respected.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n========\n\nThe paper is clear, rigorous, and well written. Several examples inserted in the text facilitate the understanding and development of ideas. The paper clearly explains its theoretical limitations while addressing an important problem with concrete applications in ML.\n\nWeaknesses\n==========\n\nThe notation may seem heavy at first glance and requires special attention from readers to deeply understand the article. On the other hand, this notation seems necessary and is directly related to the rigor of the article. There is no free lunch. \n\nClarity\n======\n\n* *line 51*: $\\mathbb{E} [y \\mid \\text{do}(\\pi)]$: this expression has not yet been presented in the text.\n* *line 106*: It would be clearer to use the expression *ch*.\n* *line 122*: We think that the reader could benefit from making the link between the policy and the SCM explicit.\n* *line 138*: It seems more natural to us to use the expression \"*we have*\" instead of \"*such that*\" from a logical perspective.\n* Figure 3: Figure 3: faded edges are not defined.\n* Table 1: If there is enough space, add some comments so as not to refer directly to the text. For example, what do the statistics in red mean?\n* *line 217*: The term *ancestral graph* is not defined.\n* Figure 4: The abbreviation $\\pi-\\text{BD}$ is not defined. Also, it would be preferable to use another abbreviation so as not to confuse the reader with Approach 3 presented in line 324.\n\nTypos\n=====\n\n* fig. 1a *(line 39)*: Fig. 1a", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly discuss the limitations and societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "YXChRYKsyqO", "reviewer": "Reviewer_nWYc", "summary": "Paper presents a novel method to tackle the problem of causal imitation learning in a sequential setting. A graph-based criterion is proposed to measure the feasibility of causal imitation and an algorithm is derived to determine the imitability, which seems to be critical to the success of causal imitation learning. All introduced approaches come with theory and simulation experiments (on a simple toy domain).", "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": "My background is imitation learning in general and I have to admit I know very little about the technical details of causal learning (casual identification, confounding, etc). So I may not be able to access the technical contribution made by this paper on causal learning. But I do read this paper in detail twice and find it very illustrative and seems to be sound.\n\nThe empirical results can be limited -- only experiments on some toy domains are conducted. As I'm not familiar with the common practice in this topic, this may not be a serious issue.\n\nFrom an imitation learning perspective, I do think the research problem here can be related to imitation learning from observation [1, 2, 3, 4] and over-imitation[5]. The authors are suggested to add citations to these papers.\n\n[1] Behavioral Cloning from Observation\n\n[2] Imitation Learning from Observations by Minimizing Inverse Dynamics Disagreement\n\n[3] Third-Person Imitation Learning\n\n[4] Imitation from Observation: Learning to Imitate Behaviors from Raw Video via Context Translation\n\n[5] Mirroring without Overimitation: Learning Functionally Equivalent Manipulation Actions", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0cnJyfcHRi-", "reviewer": "Reviewer_4Bw1", "summary": "The paper addresses the task of behavioral cloning for sequential decision making problems, in a setting where the expert and the imitation learner have different sets of observable variables, i.e. in the presence of observational mismatch. To do this, the paper assumes knowledge of the causal graph that models the process used to generate the data. Using the graph, the authors characterize conditions under which imitation is possible and if it is, propose a process for coming up with the right subset of variables to use.  ", "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": "The paper is original and high quality. It is hard to parse for readers more familiar with imitation learning than causality, but that is inevitable to an extent. The main contribution is significant.\n\nAs a practitioner, I have the following questions.\n1. In many practical deployments, people don't use behavioral cloning but instead deploy adversarial imitation learning, which has better properties than behavioral cloning when expert data isn't abundant. Can you share your thoughts whether it makes sense to match distributions over the subset of state features selected by your algorithm?  \n2. More broadly, a crucial condition for the applicability of the proposed method in practice is the amount of expert data it requires. Would you expect the method to work for a small dataset (e.g. just one expert trajectory)?\n3. How would you approach the scenario where observations are images? It seems hard to impose causal structure on parts of an image and yet you use images as motivation in the description of your Figure 1a. \n\nMinor point: Figure 4 has no confidence bars.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The adequately discuss the limitations and societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: It is my pleasure to recommend acceptance of this paper.

As noted by reviewers:

*The paper is clear, rigorous, and well written. Several examples inserted in the text facilitate the understanding and development of ideas. The paper clearly explains its theoretical limitations while addressing an important problem with concrete applications in ML.*

Also:

*The paper contributes to the foundations of imitation learning and attempts to answer an important question of whether an imitator is able to imitate a demonstrator if there exists sensor input mismatch.*
Decision: Accept (Oral)