Causal Imitability Under Context-Specific Independence Relations
Authors: Fateme Jamshidi
Sina Akbari
Negar Kiyavash
Venue: NeurIPS 2023 poster (2023)
Keywords: causal inference
conditional independence
context-specific independence relations
imitability
TL;DR: We address the feasibility imitation in a causal setting when certain context-specific independence relations are known.

Abstract: Drawbacks of ignoring the causal mechanisms when performing imitation learning have recently been acknowledged. Several approaches both to assess the feasibility of imitation and to circumvent causal confounding and causal misspecifications have been proposed in the literature.
However, the potential benefits of the incorporation of additional information about the underlying causal structure are left unexplored.
An example of such overlooked information is context-specific independence (CSI), i.e., independence that holds only in certain contexts.
We consider the problem of causal imitation learning when CSI relations are known.
We prove that the decision problem pertaining to the feasibility of imitation in this setting is NP-hard.
Further, we provide a necessary graphical criterion for imitation learning under CSI and show that under a structural assumption, this criterion is also sufficient.
Finally, we propose a sound algorithmic approach for causal imitation learning which takes both CSI relations and data into account.

Causal Imitability Under Context-Specific Independence Relations
Fateme Jamshidi EPFL, Switzerland
Sina Akbari EPFL, Switzerland sina. akbari@epfl.c.
Negar Kiyavash
EPFL, Switzerland negar www..kssaaasspll...m ch
fateme. jamshiiipfm.i
Abstract
Drawbacks of ignoring the causal mechanisms when performing imitation learning have recently been acknowledged. Several approaches both to assess the feasibility imitation and to circumvent causal confounding and causal misspecifications have been proposed in the literature. However, the potential benefits of the in- corporation of additional information about the underlying causal structure are left unexplored. An example of such overlooked information is context-specific independence (CSI), i.e., independence that holds only in certain contexts. We consider the problem of causal imitation learning when CSI relations are known. We prove that the decision problem pertaining to the feasibility of imitation in this setting NP-hard. Further, we provide necessary graphical criterion for imitation learning under CSI and show that under a structural assumption, this criterion is also sufficient. Finally, we propose a sound algorithmic approach for causal imitation learning which takes both CSI relations and data into account.
Introduction
Imitation learning has been shown to significantly improve performance in learning complex tasks in a variety of applications, such autonomous driving (27]) electronic games [77 41), and navigation 34]. Moreover, imitation lcarning allows for learning merely from observing expert demonstrations, therefore circumventing the need for designing reward functions or interactions with the environment. Instead, imitation learning works through identifying policy that mimics the demonstrator's 's behavior which is assumed to be generated by an expert with near-optimal performance terms of the reward.
Imitation learning techniques are of two main flavors; behavioral cloning (BC) 42 30 24 255, and inverse reinforcement learning (IRL) [26] succeed. IRL methods have proved more successful in practice, albeit at the cost of an extremely high computational load. The celebrated generative adversarial imitation learning (GAIL) framework and its variants bypass the IRL step by occupancy measure matching learn optimal policy (15).
BC approaches often require extensive data to
Despite recent achievements, still in practice applying imitation learning techniques can result in learning policies that are markedly different from that of the expert 99 7 22). This phenomenon is for the most part the result of a distributional shift between the demonstrator and imitator environments All aforementioned imitation learning approaches rely on the assumption that the imitator has access to observations that match those the expert. An assumption clearly violated when unobserved confounding effects are present, e.g., because the imitator has access only to partial observations of the system. For instance, consider the task of training an imitator to drive car, causal diagram of which is depicted in Figure Ta X and Y in this graph represent the action taken by the driver and the latent reward, respectively. The expert driver controls her speed (X) based on the speed limit on the highway (denoted by S), along with other covariates such as weather conditions,
II 31 12]
Also referred to as inverse optimal control in the literature.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) not imitable
(b) imitahle
(c) contextually imitable (d) wage rate example
Figure 1: Example of learning to drive car. (a) Imitation is impossible, as the imitator has no
access to the speed limit. (b) The car has automatic cruise control, which makes the expert actions
independent of the speed limit. (c) Driver actions are independent of speed limit only in the context of heavy traffic.
simple example of a CSI relation in economics.
brake indicator of the car in front, traffic load, etc. We use two such covariates in our example: Z and T. An optimal imitator should mimic the expert by taking actions according to the expert poliey P(X|S, Z, T), However, if the collected demonstration data does not include the speed limit (S), the imitator would tend to learn a policy that averages the expert speed, taking only the other covariates (Z and 7' into account. Such an imitator could end up crashing on serpentine roads or causing traffic jams on highways. As shown in Figure la the speed limit acts as a latent confounde D
One could argue that providing more complete context data to the imitator, c.g. including the speed limit in the driving example, would resolve such issues. While this solution is not applicable in most scenarios, the fundamental problem in imitation learning is not limited to causal confounding. As demonstrated by [12] and [43] having access more data not only does not always result in improvement but also can contribute to further deterioration in performance. In other words, important issues can stem not merely from lack of observations but from ignoring the underlying causal mechanisms. The drawback of utilizing imitation learning without considering the causal structure has been recently acknowledged, highlighting terms including causal confusion [12,, sensor-shift 13.. imitation learning with unobserved confounders 43 and temporally correlated noise [36].
Incorporating causal structure when designing imitation learning approaches has been studied in recent work. For instance, [[2] proposed performing targeted interventions to avoid causal misspecification. 43 characterized necessary and sufficient graphical criterion to decide the feasibility of an imitation task (aka imitability). It also proposed a practical causal imitation framework that allowed for imitation in specific instances even when the general graphical criterion (the existence of π bbbckdoorr admissible set) did not necessarily hold. [36] proposed a method based on instrumental variable regression circumvent the causal confounding when a valid instrument was available.
Despite recent progress, the potential benefits of further information pertaining to the causal mecha- nisms remain unexplored. An important type of such information is context-specifie independence (CSI) relations, which are generalizations of conditional independence. Take, for instance, the labor market example shown in Figure Id where W. E. and U' represent the wage rate, education level, and unemployment rate, respectively. The wage rate W is a function of E and U. However, when unemployment is greater than 10%, the education level does not have significant effect on the wage rate, as there is more demand for the job than the openings. This is to say, W is independent of E given U, only when U > 10%. This independence is shown by label U > 0.1 on the edge E - W. Analogously, in our driving example, the imitator would still match the expert's 's policy if there was heavy traffic on the route. This is because, in the context that there is heavy traffic, the policy of the expert would be independent of the speed limit. This context-specific independence between the speed limit S and the action X given T 1 (heavy traffic) is indicated by a label (T' 1) on the edge S + X in Figure Ic This label indicates that the edge S + X is absent when T = 1. The variables T' in Figure Ic and U in Figure Id are called context variables, i.e., variables which induce conditional independence relations in the system based on their realizations.
CSIs can be incorporated through a refined presentation of Bayesian networks increase the power of inference algorithms (8. The incorporation of CSI also has ramifications on causal inference. For instance, (39] showed that when accounting for CSIs, Pearl's do-calculus is longer complete for causal identification. They proposed a sound algorithm for identification under CSIs. It is noteworthy
"On the other hand, if the car had automatic cruise control, the expert policy would be independent of the speed limit, resolving imitation issues (refer to Figure lb)

---

that unlike conditional Independence (CI) relations that can be learned from data and are widely used infer the graphical representation of causal mechanisms [35 6
19 [8] not all CSI relations can be learned from mere observational data. However, several approaches exist for learning this paper, we investigate how CSIs allow for imitability
certain CSIs from data [2 16 82 23].
in previously non-imitable instances.
After presenting the notation (Section 2). we first prove hardness result, namely, that deciding the feasibility of imitation learning while accounting for CSIs is NP-hard. This is in contrast to the classic imitability problem [43,, where deciding imitability is equivalent to single d-separation test. We characterize a necessary and sufficient graphical criterion for imitability under CSIs under a structural assumption (Section B by leveraging a connection we establish between our problem and classic imitability. Next, we show that in certain instances, the dataset might allow for imitation, despite the fact that the graphical criterion is not satisfied (Section 4 Given the constructive nature of our achievability results, we propose algorithmic approaches for designing optimal imitation policies (Sections Jndd 4 and evaluate their performance in Section
[
The proofs of all our results appear in
Appendix
2 Preliminaries
Throughout this work, we denote random variables and their realizations by capital and small letters, respectively. Likewise, we use boldface capital and small letters represent sets of random variables and their realizations, respectively. For a variable X, Dxx denotes the domain of X and Px the space of probability distributions over Dx. Given two subsets of variables T and S such that T C S, and realization E Ds, we use (s)r to denote the restriction of s to the variables in T.
We use structural causal models (SCMs) as the semantic framework of our work (88 An SCM M a tuple (U, V, pa (U), where U and V are the sets of exogenous and endogenous variables, respectively. Values of variables in U are determined by an exogenous distribution pM (U), whereas the variables in V take values defined by the set of functions F = { Jvvv. That is, V + IV (Pa(V) U Uv) where Va(V) S V and Uy S U. We also partition V into the observable and latent variables, denoted by O and L, respectively, such that V O U L. The SCM induces a probability distribution over V whose marginal distribution over observable variables, denoted by pM (O), is called the observational distribution. Moreover,
do(X x) to denote an intervention on X S V where the values of X are set to a constant x in lieu of the functions {fx : VX E X]. We use PM (y) == .MPPP (Y y|do(X x)) as shorthand for the post- interventional distribution of Y after the intervention dx(x=x)
Let X, Y. W, and Z be pairwise disjoint subsets of variables. X and Y are called contextu- ally independent given W the context z E Dz P 2) P(X[W, 2)) whenever P(Y, W,z) > O. We denote this context-speciff independence (CSI) relation by X IL Y/W,z. z. Moreover, a CSI is called local if is of the form X IL Y|z where {YJUZC Pa(X).
A directed acyclic graph (DAG) is defined as a pair G = (V, E), where V is the set of vertices, and E S x V denotes the set of directed edges among the vertices. SCMs are associated with DAGs, where each variable is represented by a vertex of the DAG, and there is a directed edge from V, to V, V, E Pa(V,) (28]. Whenever a local CSI of the form Vú 1L Vyle holds, we say L is a label for the edge (V,, V3)) and denote it by & E V) Recalling the example of Figure 1c the realization T = 1 is a label for the edge (S, X). which indicates that this edge is absent when T equal to 1. Analogous to (2), we define labeled DAG (LDAG), denoted by go, as a
tuple gc = (V, E, L), where L denotes the labels representing local independence relations. More
precisely, (L(v.v)) L(v.,))) # 0 (V, V2) E E), where
G(v.))= D V S Pa(V)) (V). V. TL Vgle).
Note that, when L 0, g reduces to a DAG. That is, every DAG is a special LDAG with no labels. For ease of notation, we drop the superscript L. when L - 0. Given a label set L, we define the context variables of L, denoted by C(C), as the subset of variables that at least one realization of them appears in the edge labels. More precisely,
C(C)= Vv + V. V. e: e:
VE n(v.v)) (1)
3

---

where V' is an arbitrary subset of nodes containing V, The argument is that if there exists some arbitrary subset V of nodes containing Vi such that realization / of this subset results in indepen- dence (e.g., of some V and Vt,), then Vú is considered as context variable. We mainly focus on the settings where context variables are discrete or categorical. This assumption can be relaxed under certain considerations (See Remark (.1T). We let Migey denote the class of SCMs compatible with
the causal graph g For a DAG G, we use 9x and 9x represent the subgraphs of G obtained by removing edges incoming to and outgoing from vertices of X, respectively. We also use standard kin abbreviations to represent graphical relationships: the sets of parents, children, ancestors, and descendants of X in 9 are denoted by (a(X) Ch(X), An(X), and De(X), respectively. For disjoint subsets of variable X. Y and Z in G. X and Y are said to be d-separated by Z in G, denoted by X L ZIZ, if every path between vertices in X and Y is blocked by Z (See Definition 1.2.3. in 28). Finally, solid and dashed vertices in the figures represent the observable and latent variables, respectively.
3 Imitability
In this section, we address the decision problem, i.e., whether imitation learning is feasible, given causal mechanism. We first review the imitation learning problem from a causal perspective, analogous to the framework developed by [43]. We will use this framework to formalize the causal imitability problem in the presence of CSIs. Recall that O and L represented the observed and unobserved variables, respectively. We denote the action and reward variables by X E O and Y E L, respectively. The reward variable is commonly assumed to be unobserved in imitation learning. Given a set of observable variables Pa CO) De(X), a policy π is then defined as a stochastic mapping. denoted by π
mapping the values of Pa to probability distribution over the action X. Given a policy we use do(x)) to denote the intervention following the policy æ, i.e., replacing the original function fx in the SCM by the stochastic mapping m. The distribution of variables under policy do( can be expressed in terms of post-interventional distributions (P())d((z)) as follows:
P(v[do(T))
Σ
P(v]do(x), pa ) p (x) P(pa"),
xEDx EE" EP
where v a realization of an arbitrary subset V' C V. We refer to the collection of all possible policies as the policy space, denoted by II = {T : Dr + Px}. Imitation learning is concerned with learning an optimal policy x" E II such that the reward distribution under policy n" matches that of the expert policy, that is, P(y]do(T*)) (oxx(()))) II, if such a policy exists, the instance is said to be imiitalee w.r.t. (g IT). The causal imitability problem is formally defined below.
P(y) [3]. Given a DAG G and the policy space
Definition 3.1 (Classic imitability w.r.t (G, 11) 43). Given a latent DAG G and a policy space 11, let Y be an arbitrary variable in G. P(y) is said to be imitable w.r.t. {G, 11) for any M E Mig, there exists a policy π E II uniquely computable from P(O) such that PM (y)do(r))=pPb)
= PPM (y).
Note that Y & De. ). the third rule of Pearl's do calculus implies P(yldo(z), pa") P(ylpa") and from Equation (2). P(y do( = P(y) for any arbitrary policy x. Intuitively, in such case, action X has no effect on the reward Y, and regardless of the chosen policy, imitation is guaranteed. Therefore, throughout this work, we assume that X affects Y, i.e., Y E De(X) n L. Under this assumption, [43] proved that P(y) is imitable w.r.t. (G, 11) if and only if there exists a r-backdoor admissible set Z w.r.t. 11).
Definition 3.2 (s (a-backdoor, 45 Given DAG 9 and a policy space II, a set Z is called x-bbcckooor admissible set w.E.. (G. II) if and only if Z S Pa and Y 1 Z in Gx.
The following lemma further reduces the search space backkoo admissible sets to a single set. Lemma 3.3. Given a latent DAG 9 and a policy space II, if there exists ा -acckdoorr admissible set w.t. (G, II, then Z An([X, Y}) n (Pa") is a r-backdoor admissible set w.r.t. (g, II).
As result, deciding the imitability reduces to testing a d-separation, i.e., whether Z defined in Lemma 3.3 d-separates X and Y in Gx, for which efficient algorithms exist [4 38). If this d-separation holds, then π (xXIZ)
P(X (Z) is an optimal imitating policy. Otherwise, the instance is not imitable.

---

T-0
T-
(a) g
(b) W (2).
(c) W = [ 10,
Figure 2: Two examples of context-induced subgraphs (Definition 3.5
It is noteworthy that in practice, it is desirable to choose r-admissible sets with small cardinality for statistical efficiency. Polynomial-time algorithms for finding minimum(-cost) d-separators exist
2 38
3.1 Imitability with CSIs
Deciding the imitability when accounting for CSIs is not as straightforward as the classic case discussed earlier. In particular, as we shall see, the existence of r-backdoor admissible sets is not necessary to determine the imitability of P(y) anymore in the presence of CSIs. In this section, we establish connection between the classic imitability problem and imitability under CSIs. We begin with a formal definition of imitability in our setting.
Definition 3.4 (Imitability w.r.t. (ge IT)). Given an LDAG G and a policy space II, let Y be an arbitrary variable in GC, Ply) called imitable w.r.. (G II) for any M E Migey, there exists policy π E ll uniquely computable from POO) such that PM (y do(T)) = = (y).
For an LDAG ge, recall that we defined the set of context variables C(C) by Equation I.. The following definition is central in linking the imitability under CSIs to the classic case.
Definition 3.5 (Context-induced subgraph). Given an LDAG gf = (V, for subset W C C( and its realization w E 'ww, we define the context-induced subgraph of g² w.r.t. w, demoted by Shr as the LDAG obtained from G by keeping only the labels that are compatible with w w and deleting the edges that are absent given W = w, along with the edges incident to W.
Consider the example of Figure 2 visualization. In the context Z = 1, the label Z = 0 on the edge U X is discarded, as Z = 0 not compatible with the context (see Figure [ Note that edges incident to the context variable Z are also omitted. On the other hand, in the context Z = 1,7 0, the edge X + Y is absent and Edges incident to both T and Z are removed in this case. Equipped with this definition, the following result, the proof of which appears Appendix A| characterizes a necessary condition for imitability under CSIS
be deleted from the corresponding graph (refer to Figure 2c
Lemma 3.6. Given LDAG G and a policy space I1, let Y be arbitrary variable in G P(y) imitable w.rt. (ge,1) I1) only if P(y) is imitable w.n.. ( 11} for every realization w E Dw of every subset of variables W C C(C).
For instance, necessary condition for the imitability of P(y) in the graph of Figure 2a is that P(v) imitable both 2b and 2c Consider the following special case of Lemma 3.6 if C(C), then _f 9w is DAG, as Lw 0 for every E Dw. In essence, necessary condition of imitability under CSIs can be expressed in terms of several classic imitability instances:
Corollary 3.7. Given an LDAG G and a policy space II, let Y be an arbitrary variable in GC. P(y) is imitable w.r.. (Ge, II') only if P(y) is imitable w.nt. (Ge, I1), i.e., there exists r-backdoor admissible set w.E.t (Ge, I1,, for every e DD(()-
It is noteworthy that although the subgraphs Ge in Corollary 3.7 are defined in terms of realizations of CCC), the number of such subgraphs does not exceed pl_ This is due to the fact that Ges share the same of vertices, and their edges are subsets of the edges of gc.
Formally, we say that label / is compatible with realization w if they are consistent; in the sense that the variables the intersection of the label and the realization take the same values under both assignments.
5

---

Although deciding the classic imitability is straightforward. the number of instances in Corollary 3.7 can grow exponentially in the worst case. However, view of the following hardness result, more efficient criterion in terms of computational complexity cannot be expected.
Theorem 3.8. Given an LDAG gf and policy space II, deciding the imitability of P(y) w.r.t. (GC, MT is NP-hard.
This result places the problem of causal imitability under CSI relations among the class of NP- hard problems in the field of causality, alongside other challenges such as devising minimum-cost interventions for query identification [3] and discovering the most plausible graph for causal effect identifiability [5] Although Theorem 3.8 indicates that determining imitability under CSIs might be intractable in general, as we shall see in the next section taking into account only handful of CSI relations can render previously non-imitable instances imitable. Before concluding this section, we consider a special yet important case of the general problem. Specifically, for the remainder of this section, we assume that Pa Pa(C(()) C C(C). That is, the context variables have parents only among the context variables. Under this assumption, the necessary criterion of Corollary 3.7 turns out to be sufficient for imitability as well. More precisely, we have the following characterization.
Proposition 3.9. Given LDAG g where Pa(C(C)) S C(C) and policy space II, let Y be an arbitrary variable in g P(y) is imitable w.r.l. (Gf, II if and only if P(y) is imitable w.rl. (Ge, II), for every De(c).
Algorithm 1 Imitation w.r.t. (gC, II]
1: function IMITATE (GC, 11, X,
2: Compute C
C(C) using Equation
3:
for c E DDc do
4:
Construct DAG Ge using Definition 3.5
5: if FINDSEP (Ge, II, X, Y) Fails then return FAIL
6:
7:
else
8:
Ze f- FINDSEP (Ge, II, X,Y) To (e(Xpa"" t P(X (pa )²c)
9:
10: I rX |aa" ) Eoede! ((pa") (ppa c
return .
The proof of sufficiency, which is constructive, appears in Appendix A The key insight here is that an optimal imitation policy is constructed based on the imitation policies corresponding to the instances II). In view of proposition 3.9 we provide an algorithmic approach for finding imitation policy under CSIs, as described Algorithm [ This algorithm takes as input an LDAG ge, policy space II, an action variable X and a latent reward Y. It begins with identifying the context variables C(= C(C)), defined by Equation (T) (Line 2). Next, for each realization с E Dc. the subgraph (Def. 3.5 is built (which is a DAG). If P(y) is not imitable
optimal
corresponding context-indued in any of these DAGs, the algorithm fails, i.c., declares Pty) is not imitable in G The imitability in each DAG is checked through a d-separation based on Lemma 3K3 (for further details of the function FindSep, see Algorithm 3 in Appendix B Otherwise, for each realization c E Dc. an optimal policy is learned through the application of the b-backdoor admissible set criterion (line 9). If such a policy exists for every realization of C, P(y) is imitable w.r.t. (Ge, III due to Proposition 3.9 An optimal imitating policy x" is computed based on the previously identified policies me. Specifically, n², the output of the algorithm, is defined as
((Xppa)
Σ E1((pa)) (eTTe(Xpaa) CEDc
Theorem 3.10. Algorithm 7 is sound and complete for determining the imitability of P(y) w.r.t. (gC, IT) and finding the optimal imitating policy in the imitable case, under the assumption that C)) C C(C).
Remark 3.11. Algorithm 7 requires assessing the d-separation of line 5 in the context- context-inducel induced subgraphs Ge. Even when the context variables C are continuous, the domain of these variables can

---

coo
Sith non-id surrogate (b) g with no surrogates
(c) G 0)
(d) (C=)))))
Figure 3: Two examples of leveraging CSI relations achieve imitability.
be partitioned into most 2 equivalence classes in terms of their corresponding context-induced subgraph, where m denotes the number of labeled edges. This holds since the number of context- induced subgraphs cannot exceed 2Th It noteworthy, however, that solving the equation referred to in line 10 of Algorithm for continuous variables may bring additional computational challenges.
Remark 3.12. Under certain assumptions, polynomial-inn algorithms can be devised for deciding imitability. One such instance is when DC(c)= = O (ooo[[[V)
(V)((V)))))))))) ()). Another analogous case is when the number of context-specifec edges is O (og((V))). Both of these lead polynomially many context- induced subgraphs in terms of [V, which in turn implies that Alg. Truns in polynomial time.
4 Leveraging causal effect identifiability for causal imitation learning
Arguably, the main challenge in imitation learning stems from the latent reward. However, in certain cases, there exist observable variables S C O such that (())d)(=) P(S) implies P(y]do(=)) = P(y) for any policy π E I1. Such S is said be an imitation surrogate for [43). Consider, for instance, the graph of Figure 3a where X represents the pricing strategy of a company, Css binary variable indicating recession (C 0) or expansion (C = 1) period, U denotes factors such as demand and competition in the market, S represents the sales and Y is the overall profit of the company. Due Proposition 3.9 (vy) is not imitable this graph. On the other hand, the sales figure (S) is an imitation surrogate for the profit (Y), as it can be shown that whenever ((S))d(=)) = P(S) for given policy ग, P(y do(r))
P(v) holds for the same policy. Yet, according to do-calculus, P(S do(r)) itself is not identifiable due to the common confounding U. On the other hand, we note that the company's pricing strategy (X) becomes independent of demand (U) during a recession (C = 0), as the company may not have enough customers regardless of the price it sets. This CSI relation amounts to the following identification formula for the effect of an arbitrary policy ı sales figures:
P(s)do(T)) = Σ P(s|æ, C (()())))
where all of the terms on the right-hand side are known given the observations. Note that even though S is a surrogate in Figure Ba] without the CSI C = O, we could not have written Equation (3). Given the identification result of this equation, if the Tr" then π² becomes an imitation policy for P(y) as well [43. It is noteworthy that solving the affoemeetioned linear system of equations for straightforward, for it boils down matrix inversion In the example discussed, although the graphical criterion of Proposition 3.9 does not hold, the data-specific parameters could yield imitability in the case that these equations are solvable. We therefore say P(y) is imitable w.r.t. {ge, II, P(O)), as opposed to 'w.r.t. (g III . Precisely, we say Pςy) imitable w.r.t. (gf II, P(O)) if for every M E Migay such that PM (0) = P(O), there exists policy æ such that PM (y)do())) = (y).
of equations P(s]do(T)
P(s) has solution
The idea of surrogates could turn out to be useful to circumvent the imitability problem when the graphical criterion does not hold. Figure 3b) however, neither graphical criteria yields imitability nor any imitation surrogates exist. In what follows, we discuss how CSIs can help circumvent the problem of imitability in even in such instances. Given an LDAG df and a context C = c, we denote the context- speccfic DAG w.r.t. (G c) by (c(c) where (c(c) is the DAG obtained by deleting all the spurious edges, i.c., the edges that are absent given the context C = e, from g
In the discrete case, and kernel inversion in the continuous case.
7

---

Algorithm 2 Imitation w.r.t. (ge, 11, P(O))
1:
function IMITATE2 (GC, 11, X, XY, P()))
2:
if SUBIMITATE (g II, X.X,YY 0, P(O)) then
3: TT" < SUBIMITATE
4: return
5: else
6:
return Fail
function SUBIMITATE(S II, X,Y, C, P(O))
2: Construct the context-specifee DAG (c)
3:
if FINDSEP (c), X, K Y) then
4:
Ze <- FINDSEP (c),
5:
(X + PZ. C=c)
6: return Te
7:
else if F (CLL,, X,Y, C) then
8:
Se f- FIINDMIISSEP (I, if CSI-ID (d(z)) C c)) then Solve P(S.) dol Te), c)-P(((c))) for TeE II if such me exists then return Te.
9:
10:
11:
12:
13:
else
if C(C) Pa" then
15:
return FAIL
else
17:
Choose V E C( \
Carbitrrrily
for UE Dv do + CUCV,, c' cU(
19:
Sl II. X,Y, C² C','', P(O)) then #c.0
21:
X.Y. X.Y.C,CC,
else
23:
return Fail
24:
Te(X PP + EveDy [(Pa")
25:
return
Definition 4.1 (Context-speciffc surrogate). Given an LDAG g., a policy space 11, and a context set of variables C O called context-specifi surrogate w.r. (G)(c), 11) X 1 Y|{S, C} in (c) III where (c) UII is a supergraph of (c) by adding edges from Pa to X.
Consider the LDAG Figure 3b for visualization. The context-specific DAGS corresponding to contexts C = 0 and C = 1 are shown in Figures 3c and 3d respectively. S is a context-specific surrogate with respect to ( = 0), II), while no context-specific surrogates exist with respect to (C 1), II). The following result indicates that despite the absence of general imitation surrogate, the existence of context-specific surrogates could suffice for imitation.
Proposition 4.2. Given an LDAG G and a policy space II, be a subset of Pa n C(C). If for every realization e E DD at least one of the following holds, then P(y) is imitable w.r.f. (ge II, P(O)).
There exists a subset Se such that 1 LY(SS, C} in (c(c) and P(Seldo(r).C-
c) = P(S c) has solution ne E II.
There exists Z. C Pa such that X YKZEe C} in gC(()x
As a concrete example, defining Z; = 0, X (Z, C} holds in the graph of Figure 3d Moreover, (S), is a context-specific surrogate w.r.t. (g 0), II). As consequence of Proposition
Sa
P(y) is imitable w.r.t. (g II, P(O)), if solution To exists to the linear set of equations
P(S)do(T), C 0) P(S|C 0),
where P(s)do(m)) 0) E., P(s 0, 0) = P(t 0), analogous to Equation

---

Table I: Results pertaining to the model of Figure 3a
Algorithm
Metric
Expert
Naive 1
Naive
Algorithm
E (d((=AL)))
1.367
1.194
1.193
1.358
0
0.0217
0.0219
0.0007
DEI(TALO(X[T = ALL 0))
NA
2.3 10-5
4.4 x 10-6
1.3 x 10
NA
2.3 10-5
4.8 x 10-4
1.3 x 10-3
To sum up, accounting for CSIs has a two-fold benefit: (a) context-specific surrogates can be leveraged to render previously non-imitable instances imitable, and (b) identification results can be derived for imitation surrogates that were previously non-identifiable.
In light of Proposition 4.2 an algorithmic approach for causal imitation learning proposed, summarized as Algorithm This algorithm calls recursive subroutine, SubImilate, also called SI within the pseudo-codee code. It is noteworthy that Proposition 4.2 guarantees imitability if the two conditions are met for any arbitrary subset of C(C) n Pa". As we shall see, Algorithm 2 utilizes a recursive approach for building such a subset so to circumvent the need to test all of the possibly exponentially many subsets.
The subroutine SI is initiated with an empty set (C = 0) as the considered context variables at the first iteration. At each iteration, the realizations of C are treated separately. For each such realization c, the second condition of Proposition 4.2 is met through a set Ze, then P(X Ze. C = c) is returned as
the context-specific imitating policy (lines 3-6). Otherwise, the search for context-specific surrogate begins. We utilize the FindMinSee algorithm of [40] to identify a minimal separating set S. U C for X and Y, among those that necessarily include C (lines 7-8). We then use the identification algorithm of [39] under CSI relations to identifyy the effect of an arbitrary policy on Se, conditioned on the context c. This algorithm is built upon CSI-calculus, which subsumes do-calculus Next, if the linear system of equations P(Se|do(TT)) c) P(Sel, c) has a solution, then this solution is returned as the optimal policy (lines 9-12). Otherwise, arbitrary variable V C(C) n Pa \ C is added to the considered context variables, and the search for context-specific policies proceeds while taking the realizations of V into account (lines 17-24). If variables are left to add to the set of context variables (i.e., C = C(C) n Pa and neither of the conditions of Proposition 4.2 are met for a realization of C, then the algorithm stops with a failure (lines 14-15). Otherwise, an imitating policy n¹ is returned. We finally note that if computational costs matter, the CSI-ID function of line 9 can be replaced by the ID algorithm of (33]. Further, the minimal separating sets of line 8 might not be unique, in which case all such sets
be used.
Theorem 4.3. Given an LDAG GC, a policy space II and observational distribution P(O), if Algorithmm 2 rreturns policy π²". then x² is an optimal imitating policy for P(y) w.r.t. (g II, P(O)). That is, Algorithm 2 is sound
5
Experiments
Our experimental evaluation is organized into two parts. In the first part, we address the decision problem pertaining to imitability. We evaluate the gain resulting from accounting for CSIs in rendering previously non-imitable instances imitable. In particular, we assess the classic imitability v.s. imitability under CSIs for randomly generated graphs. In the second part, we compare the performance of Alg. 2 against baseline algorithms on synthetic datasets (see Sec. for further details of our experimental setup). Python implementation are accessible at fettttts//// //gt:t////tttt com/ Sinakkbarii/causa imi ioniiationn -atraaainnnatttt---eaannnnnege
5.1 Evaluating imitability
We sampled random graphs with n vertices and maximum degree A = nL uniformly at random. Each variable was assumed to be latent with probability 1 6. We chose 3 random context variables
TO
$ Figure Balis is an example where do-calculus fails identify P(s do(x)). whereas CSI-caleulus provides an identification formula, Equation (3).
See Section C for an example where Algorithm 2 is not complete.

---

Fraction of Fimitblle instomces
1.4
0.6
0.4
Instable
Iniaable under
0.0
50
80
100
120
140
160
Number of vertices
Figure 4: The fraction of imitable instances (in the classical sense) vs those that are imitable considering CSIs.
such that the graphical constraint Pa(C(C)) C(C) is satisfied. Labels on the edges were sampled with probability 0.5. We then evaluated the graphical criterion of classic imitability (existence of r-backdoor) and imitability with CSIs (Corollary 3.7 The results are depicted in Figure 4 where each point in the plot is an average of 100 sampled graphs. As seen in this figure, taking into account only handful of CSI relations (in particular, 3 context variables among hundreds of variables) could significantly increase the fraction of imitable instances.
5.2 Performance evaluation
In this section, we considered the graph of Figure 3b as generalization of the economic model of Figure 3aj where the reward variable Y can be more complex function. As discussed earlier, this graph has neither a n-backdoor admissible set nor an imitation surrogate. However, given the 0), Algorithm 2 can achieve an optimal policy. We compared the
identifiability of P(S) P(S)do(T), performance of the policy returned by Algorithm 2 against two baseline algorithms: Naive algorithm which mimics only the observed distribution of the action variable (by choosing (X) = P(X)), and Naive algorithm 2, which takes the causal ancestors of X into account, designing the policy (X(T) = (TX Naive algorithm can be thought of as a feature selection followed by behavior cloning approach. The goal of this experiment was to demonstrate the infeasibility of imitation learning without taking CSIs into account. model with binary observable variables and ternary reward was generated. Let TLG represent the policy that the algorithm would have learned with infinite number of samples, and ALG the policy it learns with the given finite sample size. As can be seen in Table I Algorithm 2 was able to match the expert policy both in expected reward and KL divergence of the reward distribution. The naive algorithms, on the other hand, failed to get close to the reward distribution of the expert. Since the algorithms were fed with finite observational samples, the KL divergence of the estimated policies with the nominal policy is also reported. Notably, based on the reported measures, the undesirable performance of the Naive algorithms does stem from estimation errors.
Concluding remarks
We considered the causal imitation learning problem when accounting for context-specific inde- pendence relations. We proved that in contrast to the classic problem, which equivalent d-separation, the decision problem of imitability under CSIs is NP-hard. We established link between these two problems. In particular, we proved that imitability under CSIs equivalent to several instances of the classic imitability problem for a certain class of context variables. We showed that utilizing the overlooked notion of CSIs could be worthwhile tool in causal imitation learning as an example of a fundamental Al problem from causal perspective. We note that while taking few CSI relations into account could result in significant achievable results, the theory CSIs not yet deve-deee. In particular, there exists no complete algorithm for causal identification under CSIs. Further research on the theory of CSI relations could yield considerable benefits in various domains where such relations present.
10

---

Acknowledgements
This research was in part supported by the Swiss National Science Foundation under NCCR Automa- /1.
tion, grant agreement 51NF40_ 180555 and Swiss SNF project
References
[1] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty- tresty-first international conference on Machine learning, page 1, 2004.
[2] Silvia Acid and Luis M. De Campos. An algorithm for finding minimum d-separating sets in belief networks. In Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence, UAI'9,, page 3-10, San Francisco, CA, USA, 1996. Morgan Kaufmann Publishers Inc.
[3] Sina Akbari, Jalal Etesami, and Negar Kiyavash. Minimum cost intervention design for causal effect identification. In Proceedings of the 39th International Conference Machine Leurning, volume 162 of Proceedings of Machine Learning Research, pages 258-289. PMLR, 2022.
[4] Sina Akbari, Luca Ganassali, and Negar Kiyavash. Causal discovery via monotone triangular transport maps. In NeurlPS 2023 Workshop Optimal Transport and Machine Learning, 2023.
[5] Sina Akbari, Fateme Jamshidi, Ehsan Mokhtarian, Matthew James Vowels, Jalal Etesami, and Negar Kiyavash. Causal effect identification in uncertain causal networks. In 7'hirty-seventh Conference Neural Information Processing Systems, 2023.
[6] Sina Akbari, Ehsan Mokhtarian, AmirEmad Ghassami, and Negar Kiyavash. Recursive causal structure learning in the presence of latent variables and selection bias. Advances in Neural Information Processing Systems, 34: 101 10119-10130, 2021.
[7] Mayank Bansal, Alex Krizhevsky, and Abhijit Ogale.
Chauffeurnet: Learning to drive by imitating the best and synthesizing the worst. arXiv preprint arXiv:1812.030% 2018.
[8] Craig Boutilier, Nir Friedman, Moises Goldszmidt, and Daphne Koller. Context-speciffc independence in bayesian networks. In Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence, UAI'96, page 115-123, San Francisco, CA, USA, 1996. Morgan Kaufmann Publishers Inc.
[9] Felipe Codevilla, Eder Santana, Antonio M López, and Adrien Gaidon. Exploring the limitations of behavior cloning for autonomous driving. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9329-9338, 2019.
[10] Diego Colombo, Marloes H. Maathuis, Markus Kalisch, and Thomas S. Richardson. Learning high-dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages
2012.
[11] Hal Daumé, John Langford, and Daniel Marcu. Search-based structured prediction. Machine learning, 75(3):297-325, 2009.
[12] Pim De Haan, Dinesh Jayaraman, and Sergey Levine. Causal confusion in imitation learning. Advances in Neural Information Processing Systems, 32, 2019.
[13] Jalal Etesami and Philipp Geiger. Causal transfer for imitation learning and decision making under sensor-shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10118-11 10-101 2020.
[14] Dan Geiger, Thomas Verma, and Judea Pearl. d-separation: From theorems to algorithms. In Machine Intelligence and Pattern Recognition, volume 10, pages 139-148. Elsevier, 1990.
[15] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.

---

[16] Antti Hyttinen, Johan Pensar, Juha Kontinen, and Jukka Corander. Structure learning for bayesian networks over labeled dags. In International Conference on Probabilistic Graphical Models, pages 133-144. PMLR, 2018.
[17] Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari. Advances in neural information processing systems, 31, 2018.
[18] Fateme Jamshidi, Jalal Etesami, and Negar Kiyavash. Confounded budgeted causal bandits. 3rd Conference Causal Learning and Reasoning, 2024.
[19] Fateme Jamshidi, Luca Ganassali, and Negar Kiyavash. On sample complexity of conditional independence testing with von mises estimator with application to causal discovery. arXiv preprint arXiv:2310. 13553,, 2023.
[20] Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972.
[21] Mikko Koivisto and Kismat Sood. Computational aspects of bayesian partition models. In Proceedings of the 22nd international conference on Machine learning, pages 433-440, 2005.
[22] Alex Kuefler, Jeremy Morton, Tim Wheeler, and Mykel Kochenderfer. Imitating driver behavior with generative adversarial networks. In 2017 IEEE Intelligent Vehicles Symposium (IV), pages 204 211. IEEE, 2017.
[23] Ehsan Mokhtarian, Fateme Jamshidi, Jalal Etesami, and Negar Kiyavash. Causal effect identi- fication with context-specific independence relations of control variables. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 1237--12246, 2022.
[24] Urs Muller, Jan Ben, Eric Cosatto, Beat Flepp, and Yann Cun. Off-road obstacle avoidance through end-to-end learning. Advances in neural information processing systems, 18, 2005.
[25] Katharina Mülling, Jens Kober, Oliver Kroemer, and Jan Peters. Learning to select and generalize striking movements in robot table tennis. The International Jourmal of Robotics Research, 32(3):263-22) 2013.
[26] Andrew Y Ng, Stuart Russell, et al. Algorithms for inverse reinforcement learning. In Icml, volume I, page 2, 2000.
[27] Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntaek Lee, Xinyan Yan, Evangelos A Theodorou, and Byron Boots, Imitation learning for agile autonomous driving. The International Journal of Robotics Research, 39(2-3):286-333 00286 2020.
[28] Judea Pearl. Causality. Cambridge university press, 2009.
[29] Johan Pensar, Henrik Nyman, Timo Koski, and Jukka Corander. Labeled directed acyclic graphs: generalization of context-specifie independence in directed graphical models. Data mining and knowledge discovery, 2953)3033-533, 2015.
[30] Dean A Pomerleau. Alvinn: An autonomous land vehicle in neural network. Advances in neural information processing systems, 1, 1988.
[31] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
[32] Yujia Shen, Arthur Choi, and Adnan Darwiche. A new perspective on learning context-specific independence. In International Conference on Probabilistic Graphical Models, pages 436-436. PMLR, 2020.
[33] Ilya Shpitser and Judea Pearl. Identification of joint interventional distributions in recursive semi-Markovian causal models. eScholarship. University of California, 2006.
12

---

[34] David Silver, James Bagnell, and Anthony Stentz. High performance outdoor navigation from overhead data using imitation learning. Robotics: Science and Systems IV, Zurich, Switzerland. 1, 2008.
[35] Peter Spirtes, Clark N. Glymour, and D. Scheines, Richardand Heckerman. Causation, predic- tion, and search. MIT press, 2000.
[36] Gokul Swamy, Sanjiban Choudhury, Drew Bagnell, and Steven Wu. Causal imitation learning under temporally correlated noise. In International Conference Machine Learning, pages 20877-20890. PMLR, 2022.
[37] Umar Syed and Robert E Schapire. A game-theoretic approach to apprenticeship learning. Advances in neural information processing systems, 20, 2007.
[38] Jin Tian, Azaria Paz, and Judea Pearl. Finding minimal d-separators, 1998.
[39] Santtu Tikka, Antti Hyttinen, and Juha Karvanen. Identifying causal effects via context-specific independence relations. Advances in neural information processing systems, 32, 2019.
[40] Benito Van der Zander, Maciej Liskiewicz, and Johannes Textor. Constructing separators and adjustment sets in ancestral graphs. In CI@ UAA, pages 11-24, 2014.
[41] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michael Mathieu, Andrew Dudzik, Jun- young Chung. David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782):50--35,, 2019.
[42] Bernard Widrow. Patterm-recognizing control systems. Compurter and Information Sciences, 1964.
[43] Junzhe Zhang, Daniel Kumor, and Elias Bareinboim. Causal imitation learning with unobserved confounders. Advances in neural information processing systems, 13:12263-12274 2020.
[44] Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd National Conference on Artificial Intelligence Volume 3, AAAI'08, page 1433-1438. AAAI Press, 2008
13

---

Appendix
Proofs of the main results are given in Section A The details of FindSep subroutine presented in Section B In Section Crrovides an example where Alg. 2 is not complete, and Section includes the details of our experiment setup.
A Technical proofs
Lemma 3.3. Given a latent DAG 9 and a policy space II, if there exists r--bacddorr admissible set w.t.t (g, II,, then Z An((X,Y)) (Pa") is r-backdoor admissible set w.r.t. (9,11).
Proof. We first claim that for any set W C (X,Y), the set of ancestors of W in G and Gx coincide, i.e. (nW) = An (()))) Oxx First, note that since 9x a subgraph of G, An W Gx An (W) For the other direction, let E AnAnn<W Otherwise, there exists a directed path from T to Y that does not pass through X. The same directed path exists in 9x, and as result, T An An(W)ax- Therefore, An(W)g C An(AAn())a
be an arbitrary vertex. If E An(X), then T An(W) 0g
The rest of the proof follows from an application of Lemma 3.4 of 40 in 9x, with I = 0 and R Pa
Lemma 3.6. Given an LDAG G and a policy space 11, let Y be an arbitrary variable in G Ply) imitable w.r.. (g HI only if P(y) imitable w.r.t. (g"" II; for every realization E Dw of every subset of variables W S C(C).
Proof. Assume the contrary, that there exists subset of variables W V V Y such that for an assignment Wo E Dw. Pyy) is not imitable w.r.t. (G II). suffices to show that P(y) is not imitable w.r.t. (GC, IT). Since Ply) is not imitable w.r.t. (gwo ; IT), there exists SCM such that pad (y))d((T)) # pM' (y) for every II. Define
M' E M (
min PM (y) pM (z]do(<))) elll
Also, define
8 = min 1 4' }
(5)
Note that > 0, and 0 < 8 < 1. Next, construct an SCM M over V compatible with Gfor as 8, and the is uniformly distributed over
follows. For variables W, PM (W wo) other realizations (summing up to 8), such that PM (W a wo) = ó. For variables V; E V W, pM (V.[Pa(VV)) = PM' (a(P)(V))) i.e., they follow the same law as the model M'. Note that by construction, W are isolated vertices gf and therefore independent of every other variable in both M' and M. Therefore,
PM (1) Σ PM (wl
Σ pM (M) WEDW
Σ pAl (y) (w) WEDW
wEDW
(6)
=PM (v)-
Moreover, for any policy ग E dependant on the values of Z' C "l define policy 22 E II dependant on Z Z' W m2(X (1 -1-60 () W wo) 8m (X W # wo). Note
14

---

that Z n W = 0. That is, T2 is independent of the values of W. We can write
pdl (y)do((T)))
E pal (y)do(mT), w)) (w (w/d(()) (w
wEDw
pMl (v)do(TT)) W = w 0) o) PM (yllo((T) W & wold
Σ( P) (y)do(z)), 2, W wol W = wo) (z) W = wo)
2,2
Σ 8pM (yldo(z), 2, W + wo) W o wo) (2/ * wo)
(1 6) (g)do(z). 2) W = wo)
2,2
8pM (1) w & wo) (z)
pM 2) (z)
pMp (y)do(Fz))
That is, for any policy я under model M, there is a policy To that results in the same reward distribution under model M'. Therefore, combining Equations and
min well
PM (w) PM (v]dd(=)) min PP' (v) PM (yldo(+)) xell
although this minimum might occur under different policies. Recalling Equation we get that under Model M and for any policy π E II,
e ES|p (v) - pM (y]do(T)).
(8)
Now we construct yet another SCM M over as follows. Variables W are distributed as in model M, i.e., PM (W) = PM (W). Moreover, for each variable E V W set V = V Pa(V) (wo)pa(V)>> where VM denotes the same variable V under SCM M. Otherwise, distribution of V is uniform in Dy. Note that by definition of M the values of W are assigned independently, and the values all other variables (V) W) only depend on their parents, maintaining all the CSI relations. As a result, M is compatible with G Also, by construction.
PM6 (0)
W/W = wo) = (M) W): pM* (0 Wldo(z), W wo) = PM (0 Wldo())).
(9)
=
Next, we write
pas (w) = Σ pass (wlw)pare (w)
WEDw
PPM* (y W DM (W- wo)
+ PM (y/W W + wo) w.) PM (W + wo)
= -1 (y/W= = wo) + p (v) W + wo)
The second term of the right-hand side above a positive number not larger than 8. Moreover, by construction of M we have pM' (yl W = wo) = PM (y). Therefore, we get
(1 - 8M (v) < PM (v) s (1 P) (v) +
(10)
15

---

Ix-1
1x
Figure 5: Reduction from 3-SAT imitability.
On the other hand, for arbitrary policy II, depending on the values of Z C Pa pM (yldo(T)) PM (yldo(TT), W wo) (W- woldo(11)
+ pMr (uldo(T)) W + wo) (W & woldo(TT)
= PM (vldo(T); W = P (W- = wo)
+ PM' (yld(())) W + wo) (W= & wo)
Σ pM (y) x). z, W wo)
B=W=w))Pd (W =wo)
+ 8PM (g)do(TT) W + wo)
Σ (y]do((()) z, W = (o) wo)PP (WW wo)
5PM* (v)do(=)) W # wo)
PM (uldO(T)) W -al (W wo) + 8PM (v|do(TT), W + wo)
(y)dO(T)), W wo)) (W- wo) + PM W wo) (W wo)
(uldo()) W #wo) PM (W- * wo) + 55P (uldo(T)) W * Wo)
= PM (yldo(()) - 5(pD (y))o(TT), W 3f wo) - pas (y)do(=)) W wo)),
and as a result,
PM (y)do(T)) - pM (g)do(T)) S PM (y((o((T) +
(11)
Combining Equations
10 and [1], we get
(PM()) (M)ldo((T)) - 8PM (y) 8
s MM (y) p (y)do(a)) s
(p' (y) PM (v]do(>))) - ( -8P + 8,
and consequently,
(p) (y)lo((T)
25 < MM (v) - pM (vldo(T)) < (PM()) - (yldo((T)) + 28,
which combined with Equation g results in the following inequality:
IpM* (y) pM* (y)do(()) 2 - 25 2 0.
To sum up, we showed that there exists model M E Migcyy. such that for every क par (y)))(T)) o pmt (y) which is in contradiction with the imitability assumption. Hence, P(y) is
II,
imitable w.r.t. (Ghr,, II) for every w E Dw of any arbitrary subset of variables W V.Y.. O
Theorem 3.8. Given an LDAG 9 and policy space II, deciding the imitability of P(y) w.r.t. (g II) is NP-hard.
16

---

Proof. Our proof exploits ideas similar to the proof of hardness of causal identification under CSIs by [3 We show a polynomial -ottttmmm reduction from the 3-SAT problem, which is a well-known NP-hard problem (20,, to the imitability problem. Let an instance of 3-SAT be defined as follows. formula F in the conjunctive normal form with clauses .I..... Sm is given, where each clause St has 3 literals from the set of binary variables W,...., W and their negations, -W.,.... - The decision problem of 3-SAT is to determine whether there is a realization of the binary variables W..... We that satisfies the given formula F, i... makes F' true. We reduce this problem to an instance of imitability problem with CSIs as follows. Define an LDAG with one vertex corresponding to each clause S, for S i S m. one vertex W which corresponds to the set of binary variables (W1.... W. and three auxiliary vertices So X, and Y. Vertex W is a parent of every S; for 1 i m. There is an edge from S,-1 to S, for 1 S i S m. Also, So is parent of X, and X and Sm are parents of Y. As for the labels, the label on each edge S - S; is that this edge is absent if the assignment of W does not satisfy the clause S. Constructing this LDAG is clearly polynomial-time, as it only requires time in the order of the number of variables (W....., W&) } and the number of clauses [S,...., Sm... We claim that P(y) is imitable in this LDAG if and only if the 3-SAT instance is unsatisfiable.
Only if part. Suppose that the 3-SAT instance is satisfiable. There exists realization w* of the binary variables (W,.... ,W}} that satisfies the formula F. Define a model M over the variables of the LDAG follows. W has the value w' with probability 0.6 (PM (W- w") = 0.6), and the rest of the probability mass is uniformly distributed over other realizations of W (i.c., each with probability 3. Sn is Bernoulli random variable with parameter 1. S, for 1 I i S m is equal to S if the edge S + S; is present (the clause S; is satisfied by the realization of W), and S; = 0 otherwise. X is equal to Sy. and Y is defined as Y = -X @ Sm. Note that model M is compatible with the LDAG defined above. We claim that under this model, for every policy II, PM (uldo(T)) + PM (v). That is, P(y) is not imitable.
Let Di and Di be the partitioning of the domain of W into two disjoint parts which satisfy and do not satisfy the formula F, respectively. Note that w E D For any realization w E Dw: observed values of Y in M is always equal to (because Y = -Sp @ Sq), i.e., PM (Y = 1/ = 1. On the other hand, for any realization w E D there exists a clause S; which is not satisfied, and therefore
Sm = 0, and Y = -X. Therefore, P* 1/w) = PM (x = 0) = 2. From the total probability law,
PM (Y = 1) = Σ
P(Y = 1[w)
Σ P(Y = P(w)
WEDW
WEDW
Σ
P(w)
1
Σ P(w)
2
WEDW
WEDW
(12)
Σ P(w) + Σ P(w)) +
Σ P(w)
WED
WEDW
WED
1
1 P(w") 0.8, 2
Σ P(w)
2
2
WED
where we dropped the superscript M for better readability. Now consider an arbitrary policy n E TI. For any realization w E Diw Y = -X @ So. where So is a Bernoulli variable with parameter 2 independent of X. As result, PM (Y 1|do(T), w) pM (S X) }.-- On the other hand, for any realization w E Dw. there exists a clause S, which is not satisfied, and therefore Sn = O, and Y -X. Therefore, PM = L|do(TT), w) = pM (x = 0]do(=)) = 7(X- = 0). Using the total probability law again, and noting that pMl (w dd(()))) PM (w).
pM (Y = 1|do(T)) = Σ
P(Y = 1 [do( w) P(W((d(((T)
WED
+
Σ
P(Y 1)d((T), (P(((T).))PP(((( (lW((())))))
WEDW
Σ
= Σ P(w), WED
= 2
WED
17

---

where we dropped the superscript M for better readability. Now define q = =E PM
1 EwEDY P(w), where we know q 2 0.6 since w E Div- From the equation above we have
pd (Y = 1===1/d00 [l(o(T)) = 2 + K = 0) -))
(13)
where 0.6 S q S and 0 < x =(X = 0) S 1. We claim that P(Y 1]do(=)) < 0.7. Consider two
cases: 7(X = 0) S 2'
then from Equation (3).
1
1
P(Y 1 [T) - 29
2
91 0.5 0.7.
Otherwise, assume x(X = 0) > 1 2. Rewriting Equation
13
P(Y = 1[do(=)) = 1 < = 0)) + x = 0) < 0.6(
2 - T(X = 0)) + + (X=X0 =0) 0)
= = + 0.4T(X = 0) s 0.7.
We showed that for any arbitrary policy π E IT,
pd (Y = 1]do(=)) 0.7.
(14)
Comparing this Equaiton 12 completes the proof.
If part. Let Ix be the intervention vertex corresponding to X, i.c. _x = and Ix = indicate that X is passively observed (determined by its parents) and actively intervened upon (independent of its parents), respectively (refer to Figure 5). Assume that the 3-SAT instance unsatisfiable. We claim that x(x) P(x) is an imitating policy for P(y). Since the 3-SAT is unsatisfiable, for any context w E Dw there exists S S m such that the edge S + S, is absent. Then, we have Ix_ 1 X, W d-separation Ix Lg W holds, by contraction, we have Ix Y, W| X in G. As a result, Ix 1 Y|X in G. Therefore,
in G for every
Dw, then Ix 1 Y X. W in G. Moreover, since the
Ply]do(z)) = Σ P(yldo(=))<<()) = Σ x001, = Σ
P(ylæ, = -)))((a)))
zEDx
xEDx
xEDx
= Σ P()) = Σ P(s))) = P(y).
zEDx
TEDx
Proposition 3.9. Given an LDAG g where Pa(C C CC() and a policy space II, let Y be an arbitrary variable in G Ply) is imitable w.r.t. (G III if and only if P(y) is imitable w.e.. II), for every c E DC(E).
Proof. It suffices to show that for an arbitrary M E M (Gsy there exists a policy E Il uniquely computable from P(O) such that pM (y)do(T)) = pM (y). For ease of notation, let C = C(C). For every с E Dc. construct an SCM Me over V by setting C = c, and replacing every occurrence of variables C by the constant value c in the equations of M. Therefore, Me is compatible with Ge and
Me (0) PM (O)))c)).
By assumption, we know that for every e E Dc, there exists a policy Te E Il uniquely computable from P(O) such that
(MM(yylo(TT)) = (M
(15)
Suppose ne relies on the values of Z. S Pa We can write
(y)d(((ee) = PM (yldo(=e), do(c))
Σ
(zldo(TT), pM (oldd(x),,d(c)) ze) (o ze (zoldo((()
m.Dx
(
Σ
p. (wldd(x)) c, 2d) (x|do( e, 2c) (zc(c)
BoEDDe
pM (yldo(((e)))
(16)
18

---

where the first and third parts of @ hold since Y 1 C|X, Ze in GTC and Pa(C) S C. For the second part, let M be the model obtained from substituting the model of X given its parents by in the equations of M. Then, we get
pM (z))do(Tee. do(c), zz) pil (2) ze) pM ar)c, PM (x)dd( ze).
Note that, since Pa(C) _ C, PM (x) do(c), ze) pM ( Ze).
Furthermore,
pile (y) = pMd (v]do(c)) = p (ylc).
(17)
Combining Equations 16
17 and (5) we get the following for every E De
pdl (yldo((e)) c) (ylc))..
(18)
Next, define a policy x² (2: Pa ) = EceDe ((PA) = Te. where ((Pa))=e) is an indicator function such that 1. = when C = c, and is equal to zero otherwise. Now, we can write
PM (yldo(x*))
Σ pM (yldo(=*), (c
cEDe
Σ
PM (yldO(TT)) c))
cEDc
Σ
PM (vlc) (c) = pM (g),
cEDe
where the last line holds due to Equation (18) and the fact that Pa(C) S C. We proved that there exists a policy '' II uniquely computable from P(O) such that PM (yldo(TT)) pM (y). Hence, P(y) is imitable w.r.t (G,II.)).
Proposition 4.2. Given an LDAG g and a policy space II, let C be subset of Pa n C(C). for every realization c E De at least one of the following holds, then P imitable w.r.t. (g 11, P(O)).
There exists subset Se such that X I LYKSe, C} in (c(c) and P(Seldo(T), C=
c) = P(S = c) has a solution Te E II.
There exists Z. C Pa such that X 1 YKZee C} in GC
Proof. Let M Mige; and PM (0) P(O), i... M induces the observational distribution P(O), be an arbitrary model. It suffices to show that there is a policy æ E Il uniquely computable from P(O) such that PM (y]do(π))
pM (v). To do so, first, partition De into two subsets Dj and D such that Dc = Di L D& and for every c E D the first condition of the lemma holds, whereas for every E D the second condition does.
For each e E Dj. construct model Mz. by substituting the model of X given its parents by me in M. Now, we get the following for each E D
pM (yldo(TTe).) = PM (ylc) =
Σ MM se PaMe
ReEDs.
pase (yldo(z), Moc
SoEDse
Σ
pM (y]dd((x), sc) p MM (selc)
=
(19)
ScEDso
(b)
Σ
PM (c) Pore (sclc)
ReDDs
(c)
pM (s = PM (y/c).
D
19

---

Algorithm 3 Find Possible 7: 7-backdoor admissible set
1: function FINDSEP (G, X,, Y,C)
2:
if C is not specified then
C 5-6 0 4: Set Z = ( Y) UC) n (Pa")
3:
5: if TESTSED (Gx. X,Y, then
6: return
7: else
8:
return FAIL
where and (b) hold since Y 1 S|e Cín (CI and in (c)),, respectively Y TT X/S c
M Th and M). Moreover, (c) holds because pM (o Te), c) PM (S. c).
Next, for each DJ let (x: PM Ze: c), then get
PM (w)do(Te))))
Σ DEDx.2eED4
pdl (yylo((r), 2e c) c) (z/ P. (zelc)
Σ
PM x, Ze, PM (rlze, c) (zelc) = PMl (ylc),
where the second equation holds since X Y Zo; Cn GC
Now, define policy x² (x|Pa") == EeeDe 1 ((Pa))=)) Te
We get the following where the second line follows from Equation 119
and the fact that CnDe(X)
0.
pM (yldo(= = Σ PM (yldo(TT) c) (cldo(xx)
cEDe
Σ pM (sldo(Te).
cEDe
Σ
PM (v/c) (c) (y).
cEDe
The above equation implies that there a policy n" 11 such that PMd (y)ld((T)) PM (1) where M is an arbitrary model compatible with g.. Therefore, P(y) is imitable w.r.t. (9-, II) and n² is an imitating policy for that.
B FindSep Algorithm
FindSep was used as a subroutine in Alg. This function is summarized here Algorithm 3, which takes a DAG G, variables X and Y, and subset of variables as inputs. It finds a separating set containing C, if exists, in Gx between X and Y. To do so, it constructs Z in line 4. According to lemma 3.4 of 40 where I C and Pa if such separating set exists, separating set.
C Example for Algorithm 2
We present a simple counterexample to illustrate that Algorithm is not complete, in the sense that may happen that instance is imitable w.r.t. (G II, P(O); ) but Algorithm 2 fails to find an imitating policy. To that end, take the instrumental variable graph depicted Figure 6 It is evident that the set of equations
P do(m)
P = 0, C - P) 0)x
P = 0) - + -X
for both values of y = and y is set of linear equations with two equations two parameters, namely TxX 0) and =(X 1). which always has solution. This indeed indicates that this
20

---

G-
Figure 6: An example where Algorithm 2 fails identify an imitating policy, despite the fact that there exists one such policy.
instance is imitable, i.e., there always exists at least one imitation policy. However, Algorithm would not be able find any such policy.
D Experimental setup
For the experiments of Section 5 we worked with an SCM in which
C~ Be(0.05).
P(Y 0/C 1) 0.2,
P(Y = 1 = 1) 0.5,
P(Y 2 = 1) 0.3,
T Be(0.)),
U1 Be(0.8),
X = O, U1 =0 Be((.7),
X 0, U1 1 Be((.7),
X = 1,U = 0 Be(O), and,
X 1,U 1 Be(1).
Moreover, we had
S/C X 0,U1 Be(1),
S/C = 0, X = 0,U, ~ Be(0),
S/C X 1,U Be(0),
S/C = 0, 1,4 Be(1).
And finally,
P(Y 0|C = 0,5 0) 0.8,
P(Y = 1|C = 0,5 0) = 0.1,
P(Y 2/C = 00 0) 0.1,
P(Y = 0|C' = 0, 1) = 0.05,
P(Y 1|C 0, 1) 0.2, and,
P(Y = 2|C = 0,5 1) = 0.75.
21


Reviews:
[{"review_id": "T7Dyr1dIVD", "reviewer": "Reviewer_Fd5v", "summary": "This paper extends studies on causal imitation learning to settings in which additional information can be provided in the form of context-specific independences (CSIs). Causal imitation learning seeks to maximize some unobserved reward $Y$ by finding a policy $\\pi^*$ from the space of policies $\\Pi$ such that the reward distribution under that policy, $P(Y \\mid do(\\pi))$ matches that of the expert policy, $P(Y)$, thereby mimicking the expert. However, mimicking $P(Y)$ is not always possible in settings with unobserved confounding, so additional knowledge in the form of causal constraints is necessary to decide whether $P(Y)$ is imitable. In prior works where such constraints are assumed in the form of a causal diagram $\\mathcal{G}$, it has been proven that $P(Y)$ is imitable if and only if there exists a $\\pi$-backdoor admissible set $\\mathbf{Z}$ w.r.t. $\\langle \\mathcal{G}, \\Pi \\rangle$. However, completeness no longer holds when CSIs are provided, in which further independence information about the distributions may be provided, conditioned on specific settings of the variables. The paper first proves that deciding imitability in this more general setting is NP-hard (Thm. 3.8). Given this limitation, they provide a sound algorithm that checks imitability within each context-induced subgraph, which they prove is also complete under a further assumption (Alg. 1). In settings where this assumption does not hold, they show that imitability can still be achieved if a policy on a set of surrogate variables is identifiable under a specific setting of CSIs. This provides a more general algorithm (Alg. 2), evaluated experimentally.", "questions": "No questions, but would be interested in hearing author responses in case I missed something.", "limitations": "Limitations are clearly stated.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "To be fully transparent, I have reviewed this paper in the past, so the following list of strengths and weaknesses reflect my existing impressions of this paper, which I have updated following another read of the latest manuscript. However, my points are largely the same, since I do not see many notable changes in the latest version. Please correct me if I am wrong.\n\n**Strengths:**\n1. Problem is well-motivated. LDAGs arise in practice and provide more information than standard causal diagrams, which should be leveraged to allow more imitable cases. This would add more positive results to the causal imitation learning literature.\n\n\n2. Assumptions are clearly stated. LDAGs are well defined, and the paper does a good job of explaining specifically how the additional constraints are incorporated. The authors are very transparent with the limitations of their approach.\n\n\n3. The solution is nontrivial and interesting. The paper clearly shows non-imitable cases that are rendered imitable when accounting for CSIs. The obvious solution of checking for backdoor sets in each context-induced subgraph is only complete under a strict assumption.", "weaknesses": "I reiterate that these points are similar to the points I made in my previous read of the paper. I have an overall positive opinion of the paper, and my goal is to help improve the paper, so I hope the authors will take this feedback into consideration.\n\n**Weaknesses:**\n1. There is nothing done to address the NP-hardness claimed by Thm. 3.8. Alg. 1 and 2 still take exponential time in the worst case. It may be insightful to provide some alternative settings in which assumptions are strict enough that polynomial time solutions can be developed. Alternatively, algorithms that sacrifice completeness for speed could be provided. While I understand that this may be out of the scope of the paper, it is otherwise not clear to me why Thm. 3.8 is relevant to the paper in the first place.\n\n\n2. Unfortunately, even Alg. 2 is not complete in the general case. Completeness is not a requirement for it to serve as a real contribution, but it would help to have some insights in this paper on why Alg. 2 is incomplete (e.g. some counterexamples) and some ideas on what could be done to move towards completeness.\n\n\n3. The motivation for Alg. 2 could be improved in terms of clarity. Notably, it could be emphasized why Alg. 1 fails in a more general setting. Eq. 3 could be explained better as well to motivate the idea of context-specific surrogates (I did not really understand Eq. 3 until I derived it myself by hand).\n\n\n4. The experiments illustrate the point as intended, but the tested scenarios are very limited in scope. The first experiment only studies a specific family of graphs, and the second experiment is performed on one specific SCM. Neither of these choices are justified. While a more extensive empirical study would boost the strength of this work, it would help immensely just to be transparent about the data generating process to ensure that there was no cherry picking. For example, for Sec. 5.1, why were those choices of delta and probability of latent variables chosen? And for Sec. 5.2, why were the parameters for that specific SCM chosen (as described in Appendix C)? \n\n\n5. Many of the ideas in this paper (including the interesting point about surrogates) incrementally improve existing ideas from Zhang et al. (2020). This reduces some of the novelty.\n\n\n6. This is a minor point and did not affect my judgment of the score, but on line 261, the authors describe the imitability problem under CSIs using the inputs of $\\langle \\mathcal{G}^{\\mathcal{L}}, \\Pi, P(\\mathbf{O}) \\rangle$ as opposed to $\\langle \\mathcal{G}^{\\mathcal{L}}, \\Pi \\rangle$. I understand that this is due to the CSI setting requiring additional information in the form of constraints over $P(\\mathbf{O})$, but I think this could be better framed. Both the original imitability problem and the new version with CSIs uses $P(\\mathbf{O})$, since it must be clear that only observational data is available, as opposed to additional interventional data such as $P(\\mathbf{O} \\mid do(\\mathbf{x}))$, collected from experimentation. In addition to this however, the CSI setting should include a set of independences.\n\n\nOverall, my impression is that this paper is worth publishing, since everything is well-defined, the proofs make sense, the assumptions are clear, and the claims are sufficiently backed. I believe that a score of 6 is appropriate given the level of contribution of the paper, which is solid but somewhat limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable input.\n\n**Regarding NP-hardness and polynomial-time solutions**\n\nWe agree that providing settings where a polynomial-time solution exists is insightful, and we thank the reviewer for this suggestion. We have come up with certain restrictions that allow for polynomial-time solutions. One such case is bounded-degree graphs. We will discuss these settings along with their corresponding polynomial-time solutions to provide further insights to the reader.\n\n---\n**Regarding Algorithm 2**\n\nWe appreciate the reviewer's understanding that completeness is a challenging requirement for the proposed Algorithm 2. While achieving completeness for imitation in this setting poses significant difficulties, we acknowledge the importance of providing insights and counterexamples to aid the readers in understanding the limitations and potential improvements of our work.\nIn the revised version of the paper, we will include a discussion of counterexamples and scenarios where Algorithm 2 may not produce the optimal solution.\n\nAs a concrete example, take for instance the instrumental variable graph ($C\\gets X\\gets U\\to Y$, $X\\to Y$), where $U$ is an unobserved confounder, $Y$ is a binary unobservable reward, and $C$ and $X$ are observed binary random variables. Also suppose that the edge $U\\to X$ has the label $C=0$. This is similar to our Figure 3 (a) in the text, without the surrogate $S$.\nIt is evident that if the set of equations \n\n$$\\left(P(y\\vert do(\\pi))=\\right)P(y\\vert X=0, C=0)\\pi(X=0)+P(y\\vert X=1, C=0)\\pi(X=1) = P(y\\vert X=0)P(X=0)+P(y\\vert X=1)P(X=1) \\left(=P(y)\\right)$$\nfor both values of $y=0$ and $y=1$ is a set of linear equations with two equations in two parameters, namely $\\pi(X=0)$ and $\\pi(X=1)$, which always has a solution.\nThis indeed indicates that this instance is imitable, i.e., there always exists at least one imitation policy. However, Algorithm 2 would not be able to find any such policy.\n\n---\n**Regarding the experiments**\n\nIndeed our experiments were primarily aimed at illustrating the potential benefits of taking context-specific information (CSIs) into account in the imitation learning process, particularly in terms of 'achievability' of imitation learning. We acknowledge that the current experiments are limited to synthetic datasets, and we agree that testing the proposed algorithms on more extensive datasets is essential to validate their practical applicability. As we move forward, we plan to address this limitation. Developing more efficient algorithms for handling CSIs as well as conducting extensive experiments on real-world datasets to evaluate the performance and efficiency of our approach in practical scenarios will be a part of our future work to enhance the overall usability and scalability of the proposed methods.\n\nWe also thank the reviewer for other minor points and comments."}, {"review_id": "b5s5qbr87u", "reviewer": "Reviewer_2EML", "summary": "This paper explores the potential benefits of incorporating context-specific independence (CSI) information into causal imitation learning, where CSI relations are known. The authors prove that the decision problem for the feasibility of imitation in this setting is NP-hard, provide a necessary graphical criterion for imitation learning under CSI, and propose an algorithmic approach for causal imitation learning that takes both CSI relations and data into account.", "questions": "- Q1. How strong is the assumption that \"the context variables have parents only among the context variables\"? It is difficult to discern the insights from which this assumption was generated without reasoning on it.\n- Q2. Equation (1) is difficult to parse. What is V’ here? Could you simplify it or provide a verbal explanation?\n- Q3. \"The labels compatible with w\" should be formally defined.\n- Q4. Is \"G_{w}\" defined? Does it refer to the context-induced subgraph of G^{L} with respect to w?\n- Q5. What is the computational cost for evaluating pi^{*} in Theorem 3.10? Isn't it still exponential in evaluating the equation?\n- Q6. Is the result valid for continuous variables? It seems that the paper assumes discreteness throughout.", "limitations": "1. There is a lack of justification for the assumption, making it difficult to assess the clarity and significance of the statement.\n2. I believe the significance of the paper lies in its practical benefits of considering the Channel State Information (CSI), which is prevalent in the real world. Therefore, it would be beneficial to have a simulation scenario that incorporates a real-world dataset.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "**Clarity**\n\n1. This paper is well-written and self-contained. It covers previous literature thoroughly.\n2. The introduction section does an excellent job of motivating the research problem, and the problem statement is clear.\n\n**Significance**\n\n1. The research problem is interesting and significant in practice.\n\n**Literature**\n\n1. This paper covers related literature extensively.\n\n**Soundness**\n\n1. All results appear to be sound.", "weaknesses": "**Clarity in Assumptions**  \n\n1. I believe that the assumption used in Proposition 3.9 requires justification. Without an explanation, it is difficult to assess the generality of the assumption. It would be interesting if the simulation described in Section 5.1 provided the fraction of instances in which the assumption was satisfied.\n\n**Lack of real-world dataset analysis.**\n\n1. I believe the significance of the paper lies in its practical benefits of considering the Channel State Information (CSI), which is prevalent in the real world. Therefore, it would be beneficial to have a simulation scenario that incorporates a real-world dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable input and appreciate the positive feedback regarding the significance of our work. We address the main points and questions raised by the reviewer below.\n\n---\n**Regarding the assumption of Proposition 3.9**\n>I believe that the assumption used in Proposition 3.9 requires justification.\n\n>Q1. How strong is the assumption that \"the context variables have parents only among the context variables\"? \n\n\nThe assumption used in Proposition 3.9 is based on the premise that the context variables are only influenced by other context variables and not by non-context variables. This assumption implies that non-context variables do not have a causal impact on the context variables.\nTo illustrate this, consider the example discussed in Section 4, where a company aims to maximize revenue. It is reasonable to assume that factors such as pricing policy or demand rate, which are non-context variables, do not influence the context variable $C$ representing the macroeconomic variable of recession.\n\nHowever, it is important to note that if in some instances, certain context variables are influenced by factors other than $C$, the corresponding CSI relations can be disregarded without compromising the overall approach. In such cases, our approach remains applicable, although with a potential loss of imitability.\n\nIn summary, while the assumption of having parents only among the context variables is ideal, our approach can still be adapted and remains valid in cases where this assumption does not strictly hold.\n\n---\n> Q2. Equation (1) is difficult to parse. What is $V’$ here? Could you simplify it or provide a verbal explanation?\n\n$C(\\mathcal{L})$ in equation (1) is the set of variables, at least one realization of which results in a context-specific independence (or removal of an edge, graphically speaking).\nIn particular, $\\mathbf{V}'$ is an arbitrary subset of nodes containing $V_i$ in Equation (1). The argument is that if there exists some arbitrary subset $\\mathbf{V}'$ of nodes containing $V_i$ such that a realization $\\ell$ of this subset ($\\mathbf{V}'$) results in an independence (e.g., of some $V_j$ and $V_k$), then $V_i$ is considered as a context variable.\nWe thank the reviewer for this feedback and we will simplify this equation and include further explanation in the revision.\n\n---\n>Q3. \"The labels compatible with w\" should be formally defined.\n\nIn our context, labels refer to realizations of a subset of variables. Formally, we say that a label $\\ell$ is compatible with a realization $w$ if they are consistent, meaning they have the same value on the intersection of the variables to which they assign a value.\nWe will add this explanation in the revision.\n\n---\n> Q4. Is \"G_{w}\" defined? Does it refer to the context-induced subgraph of G^{L} with respect to w?\n\nYes, indeed. We thank the reviewer for pointing this out, and we will clarify that this symbol refers to the context-induced subgraph of $\\mathcal{G}^\\mathcal{L}$ w.r.t. $\\mathbf{w}$, as defined in definition 3.5.\n\n---\n>Q5. What is the computational cost for evaluating pi^{*} in Theorem 3.10? Isn't it still exponential in evaluating the equation?\n\nAlgorithm 1 runs linearly many loops in terms of the number of contexts. The loop itself requires testing a d-separation which is quadratic-time in the worst case, in the number of variables. The number of possible contexts, however, can still be exponential in the number of variables. This is inevitable considering the hardness result of Theorem 3.8. \n\n---\n>Q6. Is the result valid for continuous variables? It seems that the paper assumes discreteness throughout.\n\nThe discreteness assumption can indeed be relaxed under certain considerations.\nIn particular, Algorithm 1 requires assessing the d-separation of line 5 in the context-induced subgraphs $\\mathcal{G}_c$.\nEven when the context variables $C$ are continuous, the domain of these variables can be partitioned into at most $2^m$ equivalence classes in terms of their corresponding context-induced subgraph, where $m$ denotes the number of labeled edges.\nThis holds since the number of context-induced subgraphs cannot exceed $2^m$.\nIt is noteworthy, however, that solving the equation referred to in line 10 of Algorithm 2 for continuous variables may bring additional computational challenges. We will elaborate on this point in the revision.\n"}, {"review_id": "Um1yzITBQL", "reviewer": "Reviewer_g52k", "summary": "This paper studies the problem of causal imitation learning, where the goal is to construct a policy that replicates the outcomes of an expert.  The challenge is that the expert may e.g., make decisions based on unobserved variables.  Prior work (e.g., [36] as cited in this paper) has established graphical conditions under which imitation can still be achieved.  This paper shows that context-specific independence relations (or \"CSIs\"), if known, can expand the space of scenarios where imitation can be achieved, and give algorithms for performing imitation learning in this setting.  In addition, this paper gives an algorithm for potential identification when the graphical criterion fails (see Proposition 4.2, Alg 2, Theorem 4.3), although this algorithm is not necessarily complete, a limitation acknowledged in the conclusion\n", "questions": "The main weakness of this paper, in my view, is the plausibility of finding context-specific independences in real-world problems.\n\nAre there other motivating examples, beyond those discussed already in the paper, that the authors would consider particularly compelling?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The contribution of this paper is quite clear, technically interesting, and novel.  Context-specific independence relations have been studied before in the causal inference literature (see e.g., citation [32]) in the context of causal identification, and so has the problem of causal imitation learning (see e.g., [36]). However, from my reading, this paper does more than simply put these concepts together (CSIs and causal imitation learning) in an obvious way. As it happens, this paper shows that incorporating CSIs renders the problem of imitation learning NP-hard \n\nWhile there is a substantial amount of technical detail to parse, which perhaps makes the paper a bit difficult to skim, I found the paper to be reasonable clear in the technical presentation given a close read. Likewise, the authors clearly outline some of the limitations of their proposed approach, e.g., the fact that they provide a sound (but not necessarily complete) algorithm in Section 4.\n\nThe synthetic experiments are somewhat minimal, but I would not expect extensive experiments in a more theoretically-oriented paper like this one, and I found the setup of the synthetic experiments to be well-motivated, exploring the benefits of their approach over random graphs.\n", "weaknesses": "First, in order to be practically applicable, this method requires some knowledge of context-specific independence relations, where there is a hard independence between certain variables in certain contexts.\n\nHowever, the motivating examples given in this paper for context-specific independence seem somewhat unrealistic.  The examples given in the paper are\n* Lines 60-65: No impact of education on wages when unemployment is high\n* Lines 66-70: In heavy traffic, no impact of speed limit on driving\n* Lines 250-252: Company pricing is independent of demand during a recession\n\nOf these, the second example seems most realistic.  In the others, complete independence between variables in those contexts seems unrealistic.\n\nSecond, I would not overstate the \"straightforward\" nature of solving for $\\pi^*$ in Section 4 (see e.g., lines 257-259, \"solving the aforementioned linear system of equations for $\\pi^*$ is straightforward, for it boils down to a matrix inversion\").  As mentioned in the footnote, this is only generally true in discrete settings, and even then may not be very practical with large numbers of variables, or variables with large cardinality.  Moreover, moving from the discrete to continuous setting introduces some substantial technical difficulties with e.g., ill-posed inverse problems.  This aspect is not the main focus of the paper, so I consider it a somewhat minor piece of feedback.\n\nAs an additional minor point, there is some lack of clarity in the experiments;  E.g., clarifying what is $\\pi_{ALG}$ versus $\\hat{\\pi}_{ALG}$ in Table 1.  There are also some minor typos \n* Line 25 \"bypass IRL step\" -> \"bypass the IRL step\"\n* Line 28 \"is for the most part result of\" -> \"is for the most part the result of\"\n* Line 75, missing space \"For instance,[32]\"\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough feedback. We acknowledge their positive feedback regarding the novelty and clarity of our work. We will now turn our attention to the points raised by the reviewer.\n\n\n---\n>The main weakness of this paper, in my view, is the plausibility of finding context-specific independences in real-world problems. Are there other motivating examples, beyond those discussed already in the paper, that the authors would consider particularly compelling?\n\nIn addition to the examples discussed in the paper, CISs have been utilized to analyze, for example, gene expression data [1], proteins [2], dynamics of pneumonia [3], parliament elections, prognosis of heart disease and occurrence of plants [4]. For a simple instance, consider an antibiotic that normally has a dose–response effect on the number of bacteria. However, due to a genetic mutation, the bacteria become resistant to the antibiotic, resulting in an independent relationship between the dose and the number of bacteria in the context of this mutation. As another example, In general, smoking has a causal effect on blood pressure. Nevertheless, if a person's ratio of beta and alpha lipoproteins exceeds a specific threshold, smoking is unlikely to have any significant impact on their blood pressure [5].\n\nMoreover, we envision that CSI relations can be particularly compelling in fields such as epidemiology, environmental sciences, public policy, and social sciences. For instance, in epidemiology, understanding the context-specific effects of certain risk factors on disease outcomes can be critical for designing targeted interventions and public health policies. In environmental sciences, the interactions between environmental variables and their effects on ecosystems may exhibit context-specific behavior, and CSIs can help unravel these complex relationships.\n\nFurthermore, in social sciences, studying the impact of social interventions or policies on different subgroups of a population may reveal context-specific causal patterns. For example, the effectiveness of a job training program may vary based on the participants' prior work experience, educational background, or age group.\n\nWhile the plausibility of finding CSIs in real-world scenarios may present challenges, we believe that their existence and relevance in multiple domains make them a compelling concept to explore and incorporate into causal modeling and inference approaches.\n\n\n[1] Y. Barash and N. Friedman. Context-specific Bayesian clustering for gene expression data.\nJournal of Computational Biology, 9(2):169–191, 2002.\n\n[2] B. Georgi, J. Schultz, and A. Schliep. Context-specific independence mixture modelling\nfor protein families. In European Conference on Principles of Data Mining and Knowledge\nDiscovery, pages 79–90. Springer, 2007.\n\n[3] S. Visscher, P. Lucas, I. Flesch, and K. Schurink. Using temporal context-specific independence\ninformation in the exploratory analysis of disease processes. In Conference on Artificial\nIntelligence in Medicine in Europe, pages 87–96. Springer, 2007.\n\n[4] H. Nyman, J. Pensar, T. Koski, and J. Corander. Stratified graphical models-context-specific\nindependence in graphical models. Bayesian Analysis, 9(4):883–908, 2014.\n\n[5] Edwards, D. and Toma, H. (1985). A fast procedure for model search in multidimensional contingency tables. Biometrika.\n\n---\n> As an additional minor point, there is some lack of clarity in the experiments; E.g., clarifying what is $\\pi_{ALG}$\n versus $\\hat{\\pi}_{ALG}$ in Table 1.\n\nWe thank the reviewer for bringing this to our attention. We will provide the following clarification in the experiments section: $\\pi$ refers to the policy that the algorithm would have learned with an infinite number of samples, while $\\hat{\\pi}$ is the policy it actually learns with the given finite sample size.\nBy including this distinction in Table 1, we aimed to show that the sub-optimality of the naive algorithms is not due to the limited sample size but is inherent to the approach itself.\n\nWe also thank the reviewer for other minor comments."}, {"review_id": "dLv4013DJV", "reviewer": "Reviewer_puDh", "summary": "The paper studies causal imitation learning. In particular, it extends traditional causal graphs with context specific independence. Although the original causal imitation learning problem can be reduced to d-seperation test, causal imitation learning with context specific independence is NP hard. But under other conditions, causal imitation learning with CSI can be solved more efficiently. ", "questions": "\n1. Context-specific independence seems like a specific form of structural equations? For instance, in the wage example, CSI can be incorporated into how the function w = f(e, u) is defined. I guess it does not work with Pearl’s do-calculus because of a violation of faithfulness? My point is that it does not seem like causal graphs need refinement to incorporate CSI?\n2. In line 134, replacing fx with stochastic mapping \\pi in mentioned as soft interventions. But as far as I know, soft interventions do not allow adding edges between intervened variable and its non-parent? \n3. In definition 3.5, what’s intuition that the edges incident to W are deleted?", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem is well motivated and theoretical contributions seem solid.  ", "weaknesses": "1. Theoretical results rely heavily on (Zhang [et.al](http://et.al), 2020) and might appear derivative. It would be better if the authors can explain a bit more on the contributions in contrast to existing works, especially in terms of identifiability, because NP-hardness is not surprising. \n2. Experiments are relatively weak as they are only tested on synthetic datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and we are delighted to learn that they found our contribution to be solid. Below, the main points and questions raised by the reviewer are addressed.\n\n---\n>Experiments are relatively weak as they are only tested on synthetic datasets.\n\nIndeed, our experiments were primarily aimed at illustrating the potential benefits of taking context-specific information (CSIs) into account in the imitation learning process, particularly in terms of 'achievability' of imitation learning. We agree that the current experiments are limited to synthetic datasets, and we acknowledge that testing the proposed algorithms on real-world datasets is essential to validate their practical applicability.\nAs we move forward, we plan to address this limitation. Developing more efficient algorithms for handling CSIs as well as conducting extensive experiments on real-world datasets to evaluate the performance and efficiency of our approach in practical scenarios will be a part of our future work to enhance the overall usability and scalability of the proposed methods. \n\n---\n> Theoretical results rely heavily on (Zhang et.al, 2020) and might appear derivative. It would be better if the authors can explain a bit more on the contributions in contrast to existing works, especially in terms of identifiability, because NP-hardness is not surprising.\n\nWhile we acknowledge that we drew inspiration from previous work, the introduction of CSIs and their influence on imitability are the key contributions that distinguish our approach and open up new possibilities for imitation learning in complex scenarios. In our experiments, particularly illustrated in Figure 4, we demonstrate how accounting for CSIs can significantly increase the number of instances that become imitable, showcasing the practical benefits of our proposed framework. We will emphasize these aspects in the revised version.\n\n---\n>1. Context-specific independence seems like a specific form of structural equations? For instance, in the wage example, CSI can be incorporated into how the function w = f(e, u) is defined. I guess it does not work with Pearl’s do-calculus because of a violation of faithfulness? My point is that it does not seem like causal graphs need refinement to incorporate CSI?\n\nIt is absolutely correct that context-specific independence (CSI) is inherent in the functional form of the structural causal model (SCM). However, when it comes to the graphical representation of causal relationships, traditional causal graphs, such as directed acyclic graphs (DAGs), are not equipped to directly incorporate CSIs without additional refinement.\nCSI relations imply conditional independence relationships between certain subsets of variables given specific contexts. While this information can be encoded in the functional form of the SCM, it is not explicitly captured in the standard graphical representation. Traditional DAGs represent the causal relationships between variables in a global sense, but they do not distinguish between different contexts in which these relationships might vary.\nWe took advantage of the concept of labeled DAGs to represent context-specific causal relationships explicitly, making it possible to distinguish between different contexts and their corresponding conditional independencies.\n\n---\n>2.  In line 134, replacing fx with stochastic mapping $\\pi$ in mentioned as soft interventions. But as far as I know, soft interventions do not allow adding edges between intervened variable and its non-parent?\n\nIndeed in the literature, a soft intervention is often used to refer specifically to interventions that do not change the parents of a variable. In our work, we used the term \"soft intervention\" in a broader sense to encompass any form of intervention that may or may not change the set of parents. We will clarify this terminology in the revision to ensure consistency with the existing literature. We thank the reviewer for bringing this to our attention.\n\n>3. In definition 3.5, what’s intuition that the edges incident to W are deleted?\n\nWe aimed at constructing a subgraph such that imitability in the original graph would imply imitability in the subgraph (which, in our work is the context-induced subgraph of definition 3.5).\nEquivalently, any non-imitable model over the subgraph must imply non-imitability in the original graph.\nTo have the flexibility in defining a non-imitable model, intuitively speaking, we would like the context variables $W$ to be completely detached from the rest of the model. This allows us to define a structural causal model (SCM) on the subgraph, where the model over $W$ is independent of the model over $V\\setminus W$. For further details, please see the proof of Lemma 3.6.\n"}]

Author rebuttal:

Meta-review: Unanimous reviewer opinion after discussions with upward score revisions. 

Authors deal with imitation learning with context dependent independencies based side information. Authors show NP-hardness result regarding decision problem of feasibility of imitation learning which is interesting. Authors show necessary and sufficient graphical criterion given the side information for feasibility of imitation learning.

Authors have promised a few revisions in the new camera ready. I strongly suggest authors to pay attention to these.
Decision: Accept (poster)