{'fraction_non_alphanumeric': 0.05574987033367468, 'fraction_numerical': 0.014642320428763315, 'mean_word_length': 3.8004341164453526, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge

Treatment effect estimation from observational data is a fundamental problem in causal inference. There are two very different schools of thought that have tackled this problem. On one hand, Pearlian framework commonly assumes structural knowledge (provided by an expert) in form of directed acyclic graphs and provides graphical criteria such as back-door criterion to identify valid adjustment sets. On other hand, potential outcomes (PO) framework commonly assumes that all observed features satisfy ignorability (i.e., no hidden confounding), which in general is untestable. In prior works that attempted to bridge these frameworks, there is an observational criteria to identify an anchor variable and if a subset of covariates (not involving the anchor variable) passes a suitable conditional independence criteria, then that subset is a valid back-door. Our main result strengthens these prior results by showing that under a different expert-driven structural knowledge -- that one variable is a direct causal parent of treatment variable -- remarkably, testing for subsets (not involving the known parent variable) that are valid back-doors is equivalent to an invariance test. Importantly, we also cover the non-trivial case where entire set of observed features is not ignorable (generalizing the PO framework) without requiring knowledge of all parents of treatment variable. Our key technical idea involves generation of a synthetic sub-sampling (or environment) variable that is a function of the known parent variable. In addition to designing an invariance test, this sub-sampling variable allows us to leverage Invariant Risk Minimization, and thus, connects finding valid adjustments (in non-ignorable observational setting) to representation learning. We demonstrate effectiveness and tradeoffs of our approaches on a variety of synthetic data as well as real causal effect estimation benchmarks.


Introduction
Estimating the impact of a treatment (or an action) is fundamental to many scientific disciplines (e.g., economics (Imbens and Rubin, 2015), medicine (Shalit et al., 2017;Alaa and van der Schaar, 2017), policy making (LaLonde, 1986;Smith and Todd, 2005)). In most of these fields, randomized clinical trials (RCT) is a common practice for estimating treatment effects. However, conducting a RCT could be unethical or costly, and we may only have access to observational data. Estimating treatment effects with only observational data is a challenging task and is of central interest to causal inference researchers.
A fundamental question in treatment effect estimation is: Which subset of observed features should be adjusted for while estimating treatment effect from observational data?
Simpson's paradox (Pearl, 2014), which is a phenonmenon that is observed in many real-life studies on treatment effect estimation, underscores the value of selecting appropriate features for treatment effect estimation. Over the years, two schools of thoughts have formed on how to tackle treatment effect estimation. The Pearlian framework (Pearl, 2009) commonly assumes that an expert provides us with the causal generative model in the form of a directed acyclic graph (DAG) that relates unobserved exogenous variables to observed features, treatment variable, and outcome variables. With the knowledge of the DAG available, the framework provides different graphical criteria (e.g., back-door criterion (Pearl, 1993), front-door criterion (Pearl, 1995)) that answers whether a subset is valid for adjustment. The DAG framework allows for the existence of confounders -unobserved variables that affect multiple observed variables. The potential outcomes (PO) framework (Rubin, 1974) makes an untestable assumption called ignorability -the assumption (in a rough sense) requires potential outcomes under different treatments be independent of the treatment conditioned on all (or a known subset of) observed features. In other words, ignorability implies that a subset of observed features is a valid adjustment and is known. The PO framework provides various techniques (e.g., inverse propensity weighing (Swaminathan et al., 2016), doubly robust estimation (Funk et al., 2011)) for treatment effect estimation under ignorability. One can view the Pearlian DAG framework as providing graphical criteria implying ignorability of certain subsets.
In summary, the Pearlian framework requires the knowledge of the DAG and the PO framework assumes ignorability with respect to the observed features. Motivated by the limitations of both of these frameworks we ask: can we significantly reduce the structural knowledge required about the DAG under non-ignorability of observed features and yet find valid adjustment sets?

Our Contributions
We assume the following minimal expert-driven local structural knowledge: a known observed feature is a direct causal parent of the treatment. Given this, we propose a simple invariance test, and show that it is equivalent to testing if a subset not involving the known parent satisfies the back-door criterion (without requiring ignorability) when the features are pre-treatment. To design our invariance test, we use the known parent to create 'fake environment variables'. We then test for invariance (across these environments) of the outcome conditioned on subsets of observed features (not containing the known parent) and the treatment. If a subset passes this invariance test, then it satisfies the back-door criterion (and therefore is a valid adjustment set) allowing for treatment effect estimation. Crucially, our result also goes in the other direction, i.e., if there exists a set (not containing the known parent) that satisfies the back-door criterion, then it will pass our invariance test.
We propose two algorithms based on this equivalence result to identify valid adjustments. In the first algorithm, we use a subset based search procedure that exploits conditional independence (CI) testing to check our invariance criterion. As is standard with any subset based search approach, the application of our first algorithm is limited to small dimensional datasets. To overcome this, in our second algorithm, we leverage Invariant Risk Minimization (IRM) (Arjovsky et al., 2019), originally proposed to learn causal representations for out-of-distribution generalization, to act as a continuous optimization based scalable approximation for CI testing. We demonstrate the effectiveness of our algorithms in treatment effect estimation on both synthetic and benchmark datasets. In particular, we also show that IRM based algorithm scales well with dimensions in contrast to the subset search based approach. The source code of our implementation is available at https://github.com/Abhin02/invariance-via-subsampling.

Outline
In Section 2, we look at some related literature. In Section 3, we formulate our problem and state our assumptions. We provide our main results in Section 4 and our algorithms in Section 5. In Section 6, we demonstrate our experimental findings. In Section 7, we conclude, discuss a few limitations and directions for future work. See the Appendix for its organization.

Related Work
Next, we provide an overview of related work that directly concerns finding valid adjustment in treatment effect estimation. See Appendix B for an overview of prior work related to potential outcomes and usage of representation learning to debias treatment effect.

Finding valid adjustment with global knowledge
Finding valid adjustment sets for general interventional queries has been extensively studied in the Pearlian framework (Tian and Pearl, 2002). Given the complete knowledge of the DAG, a sound and complete algorithm to find valid adjustments was proposed by Shpitser and Pearl (2008). When only the observational equivalence class is known, i.e., partial ancestral graph or PAG (Zhang, 2008), Perkovic et al. (2018) provided a sound and complete algorithm for finding valid adjustments. VanderWeele and Shpitser (2011) showed that if a valid adjustment set exists amongst the observed features, then the union of all observed parents of outcome and all observed parents of treatment is also a valid adjustment set. However, they required global knowledge i.e., information about every observed feature while our work requires knowledge about only one observed parent of treatment i.e., local knowledge.

Finding valid adjustment with local knowledge.
As opposed to the works described in the previous paragraph, another line of work (e.g., Entner et al. (2013); Cheng et al. (2020); Gultchin et al. (2020)) focused on finding valid adjustment sets by exploiting local knowledge of the DAG. In Entner et al. (2013), a two-step approach was proposed. First, an anchor variable is characterized by an observational criteria that is testable. Next, a conditional independence test is performed on the subsets not involving the anchor variable to find the valid adjustment set. In the reverse direction, if a valid adjustment set exists that does not contain the anchor variable, their test is shown to succeed only if the anchor variable has no observed or unobserved parents. As a result, even if it were possible to carry out consistent treatment effect estimation based on adjustment sets not involving the anchor, their procedure need not necessarily enable it. In contrast, in these settings, under the assumption that the anchor variable (direct causal parent of the treatment) is specified by the expert, our invariance test enables consistent treatment effect estimation. On the other hand, in Cheng et al. (2020), the anchor variable is characterized by topological properties of the PAG. We provide examples where our procedure can correctly declare that consistent treatment effect is not possible but they cannot.
Following Entner et al. (2013), Gultchin et al. (2020) proposed a fully-differentiable optimization framework to find a representation of the features that passes the conditional independence criteria analogous to Entner et al. (2013). While their approach avoids the brute-force subset search required by Entner et al. (2013), their approach is as limited in the reverse direction as Entner et al. (2013). Further, their continuous optimization framework assumes the outcome is binary or the whole system (including the treatment) is linear Gaussian. Additionally, they use partial correlation as a proxy for conditional independence. This proxy is correct when the underlying distribution is Gaussian and in the worst-case constrains only the second moment. In other words, their framework doesn't provide formal guarantees even if one of the variables (e.g. treatment) isn't Gaussian. In contrast, our approach doesn't make these assumptions and is more general.

Invariance principle.
The invariance principle (also known as modularity condition) is fundamental to causal bayesian networks (Bareinboim et al., 2012;Schölkopf, 2019). Arjovsky et al. (2019) proposed a continuous optimization framework called invariant risk minimization (IRM), to search for causal representations which satisfy invariance principle, that achieves out-of-distribution generalization. A recent line of work (e.g., Shi et al. (2020);Shah et al. (2021)) has focused on using IRM for treatment effect estimation. Shi et al. (2020) assumed (i) that there are no unmeasured confounders and (ii) access to interventional data is available (similar to IRM). We significantly differ from this as we allow unmeasured confounders and do not require interventional data -we create artificial environments by sub-sampling observational data -and leverage IRM to find valid adjustment sets that satisfy our criterion. On the other hand, while Shah et al. (2021) created environments artificially (similar to ours), their sub-sampling procedure lacks theoretical justification. Further, they focus primarily on the setting where there is little support overlap between the control and the treatment group, and lack formal guarantees on finding valid adjustment sets.

Semi-Markovian Model, Effect Estimation, Valid Adjustment
Consider a causal effect estimation task with x as the feature set, t as the observed treatment variable and y as the observed potential outcome. For the ease of exposition, we focus on binary t. However, our results apply to non-binary t as well. Further, while we consider discrete x and y , our framework applies equally to continuous or mixed x and y . Let G denote the underlying DAG over the set of vertices W := {x, t, y }. For any variable w ∈ W, let π(w ) denote the set of parents of w i.e., π(w ) = {w 1 : To estimate the causal effect of treatment t on outcome y , a Markovian causal model requires the specification of the following three elements : (a) W -the set of variables, (b) G -the DAG over the set of vertices W, and (c) P(w |π(w )) -the conditional probability of w given its parents π(w ) for every w ∈ W. Given the DAG G, the causal effect of t on y can be estimated from observational data since P(w |π(w )) is estimable from observational data whenever W is observed.
Our ability to estimate the causal effect of t on y from observational data is severely curtailed when some variables in a Markovian causal model are unobserved. Let x (o) ⊆ x be the subset of features that are observed and x (u) = x \ x (o) be the subset of features that are unobserved. For any variable w ∈ W, let π (o) (w ) ⊆ π(w ) denote the set of parents of w that are observed and let π (u) (w ) := π(w ) \ π (o) (w ) denote the set of parents of w that are unobserved. We focus on the semi-Markovian causal model (Tian and Pearl, 2002), defined below, since any causal model with unobserved variables can be mapped to a semi-Markovian causal model while preserving the dependencies between the variables (Verma and Pearl, 1990;Acharya et al., 2018).
U is the set of unobserved (or exogenous) features, i.e. U := W \ V = x (u) , 3. G is the DAG over the set of vertices W such that each member in U has no parents and at-most two children. 4. P(v |π (o) (v ), π (u) (v )) ∀v ∈ V is the set of unobserved conditional distributions of the observed variables, and 5. P(U) is the unobserved joint distribution over the unobserved features.
In a semi-Markovian model, unobserved variables with only one or no children are omitted entirely. See Figure 1 for a toy example of a semi-Markovian model with V = {x 1 , x 2 , x 3 , t, y }, U = {u 1 , u 2 , u 3 , u 4 }, and G = G toy .
u 4 y t Figure 1: The toy example G toy .
In observational data, we observe samples of V from P(V) which is related to the semi-Markovian model M by the following marginalization (Tian and Pearl, 2002): Next, we define the notion of causal effect using the do-operator.
Definition 2. (Causal Effect.) The causal effect of the treatment t on the outcome y is defined as The do-operator forces t to be t in the causal model M, i.e the conditional factor P(t = t |π (o) (t), π (u) (t)) is replaced by the indicator 1 t=t and the resulting distribution is marginalized over all possible realizations of all observed random variables except y . Next, we define average treatment effect and valid adjustment.
Definition 4. (Valid Adjustment.) A set of variables z ⊆ x is said to be a valid adjustment relative to the ordered pair of variables (t, y ) in the DAG G if P(y |do(t = t)) = E z [P(y |z = z, t = t))].
If z ⊆ x (o) is a valid adjustment relative to (t, y ), then the ATE can be estimated from observational data by regressing the factual outcomes for the treated and the untreated sub-populations on z i.e., For any variables w 1 , w 2 ∈ W, and a set w ⊆ W, (a) let w 1 ⊥ p w 2 |z denote that w 1 and w 2 are conditionally independent given z and (b) let w 1 ⊥ ⊥ d w 2 |w denote that w 1 and w 2 are d-separated by w in G. For completeness, we provide the definition of d-separation in Appendix D as well as review potential outcomes (PO) framework (Imbens and Rubin (2015)), discuss ignorability and connect it with valid adjustment in Appendix C.

Back-door Criterion
We now discuss the back-door criterion (Pearl et al., 2016) -a popular sufficient graphical criterion for finding valid adjustments i.e., any set satisfying the back-door criterion is a valid adjustment (Pearl (1993)).
Definition 5. (Back-door criteria.) A set of variables z ⊆ x satisfies the back-door criterion relative to the ordered pair of variables (t, y ) in G if no node in z is a descendant of t and z blocks every path between t and y in G that contains an arrow into t.
Often, G is represented without explicitly showing elements of U but, instead, using bi-directed edges (Tian and Pearl (2002)) to represent confounding effects of U. For example, Figure 1 uses bi-directed edges to represent unmeasured confounders (i.e., elements of U that influence two variables in V) in the DAG G toy .
In this work, we make the following structural assumption on the DAG G under the semi-Markovian model M. This assumption is analogous to the common assumption that all observed features are pre-treatment variables. As an example, consider the DAG G toy in Figure 2 that satisfies this assumption.
Assumption 1. Let the DAG G be such that the treatment t has the outcome y as its only child. Further, the outcome y has no child.
x 1 x 2 x 3 y t Figure 2: The toy example G toy with bi-directed edges.

Main Results
In this section, we state our main results relating sub-sampling and invariance testing to the back-door criteria. First, we define the notions of sub-sampling and invariance. Next, we provide : (a) a sufficient d-separation condition (that can be realized by our invariance test under sub-sampling) for a class of back-door criteria (Theorem 4.1) and (b) a necessary d-separation condition (that can be realized by our invariance test under sub-sampling) implied by a class of back-door criteria (Theorem 4.2). Combining these, we show equivalence between an invariance based d-separation condition and a class of back-door criteria (Corollary 1). Finally, we propose an algorithm to find all subsets of the observed features that satisfy the back-door criteria when all the parents of the treatment variable are known and observed (Appendix I).
Sub-sampling. We create a sub-sampling (or environment) variable e from the observed distribution P(V). Formally, we use a specific observed variable x t ∈ x (o) and a subset of the observed variables v ⊆ V \ {x t , y } to sub-sample e i.e., e = f (x t , v, η) where η is a noise variable independent of W, and f is a function of x t , v and η. The choices of x t and v, which differ for the sufficient condition (Theorem 4.1) and the necessary condition (Theorem 4.2), are made clear in the respective theorem statements. We let the sub-sampling variable e be discrete and think of the distinct values of e as identities of distinct artificial environments created via sub-sampling. While the case where e is continuous is similar in spirit, we postpone the nuances for a future work. Graphically, sub-sampling variable introduces a node e, an edge from x t to e and edges from every v ∈ v to e in the DAG G. For example, see Figure 3a where e is sub-sampled in toy example G toy with x t = x 1 and v = {t}.
Invariance testing. Our main results relate the back-door criterion to d-separation statements of the type e⊥ ⊥ d y |z for some z ⊆ V \ {y }. While our goal is to infer sets satisfying the back-door criterion from observational data, such d-separation statements cannot be tested for from observational data. To tackle this, we propose the notion of invariance testing. An invariance test is a conditional independence test of the form e ⊥ p y |z for some z ⊆ V \ {y } i.e., an invariance test tests if the sub-sampling variable is independent of the outcome conditioned on z for some z ⊆ V \ {y }.
For our results involving invariance testing, we require the following limited set of faithfulness assumptions to ensure invariance testing with e is equivalent to d-separation statements involving e.
Thus, in effect, we create synthetic environments and show that a class of back-door criterion either implies or is equivalent to a suitable invariance test. For our framework to work, we only require the knowledge of x t from an expert. This is in contrast to any detailed knowledge of the structure of the DAG G.

Sufficient condition.
Suppose an expert provides us with an observed feature that has a direct edge or a bi-directed edge to the treatment. Let e be sub-sampled using this feature as x t and any v ⊆ V \ {x t , y }. The following result shows that any subset of the remaining observed features satisfying a d-separation involving e (or an invariance test under Assumption 2) also satisfies the back-door criterion. See Appendix F for a proof.
Theorem 4.1. Let Assumption 1 be satisfied. Consider any x t ∈ x (o) that has a direct edge or a bi-directed edge to t i.e., either x t − → t, x t t or x t − → t. Let e be sub-sampled using x t and v for any If e is d-separated from y by z and t in G i.e., e⊥ ⊥ d y |z, t in G, then z satisfies the back-door criterion relative to (t, y ) in G.
Remark 1. A stronger result that subsumes Theorem 4.1 was proven in Entner et al. (2013); we provide our theorem for clarity of exposition and completeness.
Necessary condition. Suppose an expert provides us with an observed feature that has a direct edge to the treatment. Let e be sub-sampled using this variable as x t and any v ⊆ {t}. The following result shows that any subset of the remaining observed features satisfying the back-door criterion satisfies a specific d-separation involving e (as well as an invariance test). See Appendix G for a proof.
Theorem 4.2. Let Assumption 1 be satisfied. Consider any x t ∈ x (o) that has a direct edge to t i.e., x t − → t or x t − → t. Let e be sub-sampled using x t and v for any v ⊆ {t} i.e., e = f (x t , v, η). Let z ⊆ x (o) \ {x t }. If z satisfies the back-door criterion relative to (t, y ) in G, then e is d-separated from y by z and t in G i.e., e⊥ ⊥ d y |z, t in G.
Remark 2. Theorem 4.2 is useful to find out (some) sets that cannot be valid adjustments (see comparison with Entner et al. (2013) and Gultchin et al. (2020) as well as comparison with Cheng et al. (2020) below). Knowing whether a given set of features is valid for adjustment or not is crucial -especially in healthcare and social sciences -to avoid using decisions based on biased estimates from observational studies.
Remark 3. We note that Theorem 4.2 requires x t to be a parent of t (i.e., a direct edge to t) whereas Theorem 4.1 requires x t to be a parent of t or a spouse of t (i.e., a direct or a bi-directed edge to t).
Equivalence. Suppose an expert provides us with a feature that has a direct edge to the treatment. Let e be sub-sampled using this variable as x t and any v ⊆ {t}. Combining Theorem 4.1 and Theorem 4.2, we have the following Corollary showing equivalence of the back-door criterion and a specific d-separation involving e (as well as an invariance test under Assumption 2).
Then, z satisfies back-door criterion relative to the ordered pair of variables (t, y ) in G if and only if e is d-separated from y by z and t in G i.e., e⊥ ⊥ d y |z, t in G.
Remark 4. While our framework captures a broad class of back-door criteria, it does not cover all the back-door criteria. For example, our method cannot capture that the M-bias problem (Liu et al., 2012;Imbens, 2020) where no observed feature is a parent of the treatment. (see Appendix H for details).
An illustrative example. First, we illustrate Corollary 1 with our toy example G toy . We let x t = x 1 and sub-sample e using x 1 and t (see Figure 3a). For this example, It is easy to verify that z = {x 2 } satisfies the back-door criterion relative to (t, y ) in G toy but z = ∅, z = {x 3 }, and z = {x 2 , x 3 } do not. Similarly, it is easy to verify that e⊥ ⊥ d y |x 2 , t but e ⊥ ⊥ d y |t , e ⊥ ⊥ d y |x 2 , t, and e ⊥ ⊥ d y |x 2 , x 3 t in G toy . See Appendix F.2 for an illustration tailored to Theorem 4.1.
x 1 x 2 x 3 e y t (a) e has been sub-sampled using x 1 and t.
x 1 x 2 x 3 e y t (b) e has been sub-sampled using x 3 and t. Figure 3: The toy example G toy with different sub-sampling strategies.
Next, we illustrate the significance of the criteria that qualifies x t to our results. In Figure 3a, we let x t = x 1 (x 1 has a direct or bi-directed edge to t). Here, the d-separation e⊥ ⊥ d y |x 2 , t holds implying that x 2 satisfies back-door relative to (t, y ). In Figure 3b, we let x t = x 3 (x 3 does not have a direct or bi-directed edge to t). Here, the d-separation e⊥ ⊥ d y |x 3 , t holds but x 3 does not satisfy the back-door relative to (t, y ).
Comparison with Entner et al. (2013) and Gultchin et al. (2020). In Entner et al. (2013), x a is an anchor variable if it satisfies the observational criterion x a ⊥ ⊥ d y |z for some x a and some z not containing x a . Further, if the CI test implied by (the d-separation condition) x a ⊥ ⊥ d y |z, t is satisfied, then z is shown to be a valid adjustment. While our sufficient condition in Theorem 4.1 is implied by this result, we provide a proof tailored to our condition and notations in Appendix F for completeness.
However, the reverse direction in Entner et al. (2013) is as follows: if some z (not containing x a ) is a valid adjustment, then x a ⊥ ⊥ d y |z, t, only when x a does not have any (observed or unobserved) parent in addition to satisfying the criteria for the anchor variable. Under our criterion, if x t is a direct parent of t, the reverse direction can be shown in generality (our Theorem 4.2).
As a concrete example, in G toy , Entner et al. (2013) cannot conclude that ∅, {x 3 }, {x 2 , x 3 } are not admissible i.e., not valid back-doors (because x a = x 1 has an unobserved parent) while our Theorem 4.2 can be used to conclude that. See the empirical comparison in Appendix K.7. Likewise, Gultchin et al. (2020), which build on Entner et al. (2013), also cannot conclude that ∅, {x 3 }, {x 2 , x 3 } are not valid adjustment sets in G toy .
Comparison with Cheng et al. (2020). In Cheng et al. (2020), the anchor variable x a is a COSO variable i.e., either a parent or a spouse of the treatment but neither a parent or a spouse of the outcome in the true maximal ancestral graph (MAG). Our criteria for x t is different from this, and our result is neither implied by nor implies the result of Cheng et al. (2020).
Consider an example which is obtained by adding the edge x 1 → y to G toy in Figure  2. The results of Cheng et al. (2020) are not applicable since the anchor variable x t is a parent of the outcome in the true DAG (and thereby in the MAG). However, x t is a parent of the treatment (i.e., it satisfies our criteria), and our Theorem 4.2 is applicable. It can be used to conclude that ∅, {x 2 }, {x 3 } and {x 2 , x 3 } are not admissible sets. See the empirical comparison in Appendix K.8.
Connections to Instrument Variable (IV). While our anchor (i.e., x t ) may look similar to IV, this is not the case: (i) An IV needs to satisfy the exclusion restriction i.e., it needs to be d-separated from y in G −t (i.e., the graph obtained by removing the edge from t to y in G). However, we do not require x t to be d-separated from y in G −t . (ii) Unlike our work, IVs can only provide bounds on ATE in non-parametric models; they provide perfect identifiability of ATE only in linear models (Balke and Pearl, 1997).

Algorithms
Our invariance criterion in Corollary 1 requires us to find a z such that e ⊥ p y |z, t. In this section, given n observational samples, we propose two algorithms that enable finding valid adjustment sets that pass our invariance criterion as well as use it to estimate ATE.

Testing and Subset Search
First, we propose an algorithm (Algorithm 1) based on conditional independence (CI) testing and it works as follows. The algorithm takes the sub-sampling variable e that is a function of x t (e could also be a function of both x t and t). The algorithm considers the set X of all candidate adjustment sets that do not contain x t . For every candidate adjustment set z in X , our algorithm checks for CI between e and y conditioned on z and t. If this CI holds, then z satisfies the back-door criterion and is a valid adjustment set (see Corollary 1 and Assumption 2). The ATE estimated by our algorithm is the average of the ATE estimated by regressing on such valid adjustment sets. On actual datasets, we use the following criterion as acceptance for CI: a p-value threshold p value is used to check if the p-value returned by the CI tester is greater than this threshold. We use the RCoT CI tester (see Appendix K.1).
Similar to Entner et al. (2013), the computational complexity of Algorithm 1 grows exponentially in the dimensionality of x (o) . This makes it impractical for high dimensional settings.
Algorithm 1: ATE estimation using subset search.

IRM based Representation Learning
To alleviate these concerns, we propose a second algorithm based on invariant risk minimization (IRM). This leverages our use of the subsampling variable and creation of synthetic environments. IRM was proposed to address out-of-distribution generalization for supervised learning tasks and is aimed at learning a predictor that relies only on the causal parents of the label y and ignore any other spurious variables. IRM takes data from different environments indexed as e and learns a representation Φ that transforms the features x such that e ⊥ y |Φ(x). Given that our invariance criterion is of a similar form, and involves checking invariance of the outcome y conditioned on the feature set z and the treatment t across environments e, IRM is a perfect fit to test this criterion.
Our IRM based procedure leverages IRMv1 from Arjovsky et al. (2019) with linear representation Φ. We take the data in treatment group t = 1 (or the control group t = 0) and divide it into different environments based on e and pass it as input to IRMv1. From the theory of IRM it follows that if the absolute value of some coefficient of Φ is low, then the corresponding component is unlikely to be a part of the subset that satisfies the invariance criterion. Following this observation, we define a vector of absolute values of Φ and denote it as |Φ|. We divide the values in |Φ| into two clusters using k-means clustering with k = 2. We select the subset of the features that correspond to the cluster with a higher mean absolute value. We estimate the treatment effect by adjusting over this selected subset. Further details of the procedure can be found in Algorithm 2 (we describe the algorithm for treatment group and can run a similar procedure for control group). While the computational complexity of IRMv1 (and hence Algorithm 2) is unclear yet, in practice, Algorithm 2 is much faster and scales better (see Figure 4c) than Algorithm 1.

Experiments
ATE estimation and Performance metrics: To test how successful our method is with respect to finding valid adjustments, we consider estimating the ATE of t on y . When the ground truth ATE is known, we report the absolute error in ATE prediction (averaged over n r runs). When the ground truth ATE is unknown, we report the estimated ATE (averaged over n r runs).
Algorithm 2: ATE estimation using IRM Input: n, n r , t, y , e, x (o) \ x t Output: ATE Initialization: ATE = 0, k = 2 1 for r = 1, · · · , n r do // Use a different train-test split in each run As described in Section 3.1, ATE can be estimated from observational data by regressing y for the control and the treatment sub-populations on a valid adjustment set. We note that our work is complementary to works on ATE estimation as our focus is on finding valid adjustments. Once we select a valid adjustment, any of the available ATE estimation methods could be used. We use ridge regression with cross-validation as the regression model for baseline as well as our method.
Environment variable and parameters. For all of our experiments, we let n r = 100 and p value = {0.1, 0.2, 0.3, 0.4, 0.5}. For our experiments we create an environment variable as being a random function of x t and t (i.e., e = f (x t , t)). Exact details of their generation and alternate settings, such as the case of e = f (x t ) (i.e., v = ∅), are given in Appendix K.
Algorithms. We compare the following algorithms: 1. Baseline: This uses regression on all of the observed features i.e., x (o) to estimate ATE. In other words, it assumes x (o) is ignorable. See Appendix J for a pseudo-code of Baseline.
2. Exhaustive: Given x t , this applies Algorithm 1 with X being the set of all subsets of 3. Sparse: Given x t , this applies Algorithm 1 with X being the set of all subsets of x (o) \ x t of size at most k (which is determined in the context).
4. IRM-t: Given x t , this applies Algorithm 2 to the samples from the treatment group.
5. IRM-c: Given x t , this applies Algorithm 2 to the samples from the control group.

Synthetic Experiment
Description. Consider the toy example G toy from Figure 1 with unobserved features u 1 ∈ R, u 2 ∈ Rd, u 3 ∈ Rd, u 4 ∈ Rd and observed features x 1 ∈ R, x 2 ∈ Rd, x 3 ∈ Rd i.e.,    ATE error for adjusting on {x 2 } is low since e⊥ ⊥ d y |x 2 , t. Next, we validate our algorithms via Figure 4b. With x t = x 1 , our algorithms Exhaustive, IRM-t, and IRM-c significantly outperform Baseline for d = 3, 5, 7 even for multiple p value thresholds for Exhaustive. We note that IRM based algorithms significantly outperform the testing based algorithm even in moderately high dimensions (d = 7) and performs very well even for d = 65 as seen through in Figure 4c.

Semi-synthetic Dataset : Infant Health and Development Program (IHDP)
Description. IHDP (Hill, 2011) is generated based on a RCT targeting low-birth-weight, premature infants. The 25-dimensional feature set (comprising of 17 different features) is pre-treatment i.e., it satisfies Assumption 1. The features measure various aspects about the children and their mothers e.g., child's birth-weight, the number of weeks pre-term that the child was born. See Appendix K.4 for details. In the treated group, the infants were provided with both intensive high-quality childcare and specialist home visits. A biased subset of the treated group is typically removed to create imbalance leaving 139 samples with t = 1 and 608 samples with t = 0. The outcome, typically simulated using setting "A" of the NPCI package (Dorie, 2016), is infants' cognitive test score. Results. We compare Baseline, Exhaustive, Sparse with k = 5, IRM-c and IRM-t. All our algorithms except IRM-c significantly outperform Baseline (see Figure 5a). The intuition behind k = 5 is the belief that valid adjustments of size 5 exist (see Appendix K.4) 1 .  Analysis. Out of the features we have access to (see Appendix K.5), we pick mother's age to be x t .
Results. The ground truth ATE is unknown (because for every sample either y 0 or y 1 is observed). However, the authors in Almond et al. (2005) expect a strong negative effect of maternal smoking on the weights of babies -about 200 to 250 grams lighter for a baby with a mother smoking during pregnancy. We compare all the algorithms except Exhaustive with x t = mother's age. For the sparse algorithm, we set k = 5 to ensure a reasonable run-time. As seen in Figure 5b, the ATE estimated using all our algorithms fall in the desired interval (i.e., (-250,-200)) and suggest a larger negative effect compared to the Baseline.

Conclusion and Discussion
We showed that it is possible to find valid adjustment sets under non-ignorability with the knowledge of a single causal parent of the treatment. We achieved this by providing an invariance test that exactly identifies all the subsets of observed features (not involving this 1 We note that Sparse still has to perform 5 i=0 9 i = 382 tests to estimate ATE. Therefore, Sparse performs not very differently from Exhaustive. parent) that satisfy the back-door criterion.
Knowledge of a causal parent of the treatment. Our invariance test depends on the causal parent of the treatment i.e., x t via the environment variable i.e., e. Therefore, our approach works even when the expert knowledge of x t is not available or samples of x t are not observed so long as we have samples of e directly. Investigating the application of this insight is an interesting question for future research.
Assumption 1 and 2. Assumption 1 and faithfulness (a stronger version of Assumption 2) are commonly used in data-driven covariate selection works (Entner et al., 2013;Gultchin et al., 2020;Cheng et al., 2020). While settings beyond Assumption 1 are interesting for future research, finding valid adjustments under Assumption 1 is non-trivial and important in both PO and Pearlian framework (see the first paragraph in VanderWeele and Shpitser (2011)). Further, we note that Assumption 1 holds for some benchmark causal effect estimation datasets (e.g., IHDP, Twins). Lastly, while it is common to assume faithfulness with respect to conditional independencies involving the entire DAG, we assume faithfulness only with respect to conditional independencies involving the sub-sampling variable.
Alternate minimal DAG knowledge. As discussed in Remark 4, our method doesn't cover all back-door criteria (e.g., the M-bias problem). Therefore, exploring alternate minimal DAG knowledge sufficient to test for a broader/different family of valid adjustments could be fruitful.

Appendix
Organization. In Appendix A we briefly discuss any potential societal impacts of our work. In Appendix B, we discuss prior work related to potential outcomes and usage of representation learning to debias treatment effect. In Appendix C, we review potential outcomes (PO) framework, discuss ignorability and connect it with valid adjustment. In Appendix D, we provide the definition of d-separation as well as a few related definitions.
In Appendix E, we provide a few additional notations. In Appendix F, we provide a proof of Theorem 4.1 and also provide an illustrative example for Theorem 4.1. In Appendix G, we provide a proof of Theorem 4.2. In Appendix H, we provide a discussion on the M-bias problem. In Appendix I, we provide an Algorithm (Algorithm 3) that, when all the parents of the treatment are observed and known, finds all subsets of the observed features satisfying the back-door criterion relative to (t, y ) in G as promised in Section 4. We also provide an example illustrating Algorithm 3 and the associated result via Corollary 2. In Appendix J, we provide an implementation of the Baseline ATE estimation routine considered in this work. In Appendix K, we discuss the usage of real-world CI testers in Algorithm 1, provide more discussions on experiments from Section 6, specify all the training details, as well as provide more details regarding the comparison of our method with Entner et al. (2013), Gultchin et al. (2020), and Cheng et al. (2020).

A Societal Impact
In health-care scenarios, since it is sometimes difficult/unethical to do randomized control trials (RCTs), sometimes the consensus treatment protocol is decided based on observational studies. Our algorithm could pick out a correct valid adjustment set when some existing methods assume ignorability due to lack of expert knowledge about the causal model.
On the flip side, due to lower testing power at finite samples or mis-identification of a feature as a direct parent of the treatment (a local causal knowledge required in our work), our algorithm could pick an incorrect valid adjustment set. This, in turn, could potentially result in miscalculation of the treatment effect. The consensus treatment protocols based on such observational conclusions could prove detrimental. However, we emphasize that this is a risk associated with most (if not all) observational studies and effect estimation algorithms.

B Additional related work
Potential Outcomes framework. Potential outcomes (PO) framework formalizes the notion of ignorability as a condition on the observed features that is sufficient (amongst others) for valid adjustment in treatment effect estimation (Imbens and Rubin, 2010). Various methods like propensity scoring (Rosenbaum and Rubin (1983)), matching (Rosenbaum and Rubin (1985)) of the treatment group and the control group based on features that satisfy ignorability, and synthetic control methods (Abadie et al. (2010)) have been used to debias effect estimation. In another line of work (Wager and Athey (2018); Künzel et al. (2019); Alaa and van der Schaar (2017)), treatment effect was estimated by regressing the outcome on the treated and the untreated sub-populations. While this list of works on the PO framework is by no means exhaustive, in a nutshell, these methods can be seen as techniques to estimate the treatment effect when a valid adjustment set is given.
Representation learning based techniques. Following the main idea behind matching (Rubin (1973) (2020)). These methods aimed to correct the lack of overlap between the treated and the control groups while assuming that the representation learned is ignorable (i.e., a valid adjustment).

C Review of potential outcomes and ignorability
We briefly review the potential outcomes (PO) framework in the context of treatment effect estimation (Imbens and Rubin, 2015). In the PO framework, there are exogenous variables called units. With a slight abuse of notation, we denote them by x (u) as well. When x (u) is fixed to say x (u) , the observed variables (including y ) are deterministically fixed i.e., only the randomness in the units induces randomness in the observed variables. The PO framework typically studies the setup where the observed features x (o) are pre-treatment (similar to semi-Markovian model under Assumption 1). Every observational sample (x (o) , t, y) has an associated unit x (u) . For t ∈ {0, 1}, the potential outcome y t is the resulting outcome for the unit x (u) when the treatment t is set (by an intervention) to t .
In the above definition, the potential outcomes y 0 and y 1 , the observed treatment t, and the features z are all deterministic functions of the units x (u) . Therefore, the conditional independence criterion makes sense over the common probability measurable in the space of the units x (u) . As mentioned in Section 1, ignorability cannot be tested for from observational data since for every observational sample either y 0 or y 1 is observed (and not both).
In the PO framework, the ATE is defined as E x (u) [y 1 − y 0 ]. When z ⊆ x (o) is ignorable, it is also a valid adjustment relative to (t, y ) in G and therefore the ATE can be estimated by regressing on z.
The Pearlian framework provides a generative model for this setup i.e., a semi-Markovian model (specifying a DAG that encodes causal assumptions relating exogenous and observed variables) as well as specifies graphical criterions that imply existence of valid adjustments relative to (t, y ) in G.

D D-separation
In this section, we define d-separation with respect to a semi-Markovian DAG G. The d-separation or directed-separation is a commonly used graph separation criterion that characterizes conditional independencies in DAGs. First, we will define the notion of a path.
Definition 8. (Path) A path P(v 1 , v k ) is an ordered sequence of distinct nodes v 1 . . . v k and the edges between these nodes such that for any i ∈ [k], v i ∈ V and for any i ∈ For example, in Figure 2, P(x 1 , x 3 y } are two distinct paths. Next, we will define the notion of a collider. Definition 9. (Collider) In a path P(v 1 , v k ), for any i ∈ {2, · · · , k−1}, a collider at v i mean that the arrows (or edges) meet head-to-head (collide) at v i i.e.
For example, in P(x 1 , x 3 ) defined above, there is a collider at x 2 . Next, we define the notion of a descendant path.

Definition 10. (Descendant path) A path
For example, in Figure 2, P(x 1 , y ) = {x 1 − → x 2 − → y } is an descendant path from x 1 to y . Next, we define the notion of a descendant.
For example, in Figure 2, y is a descendant of x 1 .
Definition 12. (Blocking path) For any variables v 1 , v 2 ∈ W, a set v ⊆ W, and a path P(v 1 , v 2 ), v blocks the path P(v 1 , v 2 ) if there exists a variable v in the path P(v 1 , v 2 ) that satisfies either of the following two conditions: (1) v ∈ v and v is not a collider.
(2) neither variable v nor any of it's descendant is in v; and v is a collider.

E Additional notations
In this section, we will look at a few additional notations that will be used in the proofs of Theorem 4.1, Theorem 4.2, and Corollary 2.

E.1 G −t
Often it is favorable to think of the back-door criterion in terms of the graph obtained by removing the edge from t to y in G. Let G −t denote this graph. The following (well-known) remark connects the back-door criterion to G −t .
Remark 5. Under Assumption 1, a set of variables z ⊆ x satisfies the back-door criterion relative to the ordered pair of variables (t, y ) in G if and only if t and y are d-separated by z in G −t .
Proof. Under Assumption 1, y is the only descendant of t i.e., no node in x is a descendant of t. Therefore, from Definition 5, z satisfying the back-door criterion relative to (t, y ) in G is equivalent to z blocking every path between t and y in G that contains an arrow into t.
Further, under Assumption 1, there are no paths between t and y in G that contain an arrow out of t apart from the direct path t − → y . However, this direct path t − → y does not exist in G −t . Therefore, z blocking every path between t and y in G that contains an arrow into t is equivalent to z blocking every path between t and y in G −t . Thus, z satisfying the back-door criterion relative to (t, y ) in G is equivalent to z blocking every path between t and y in G −t i.e., t⊥ ⊥ d y |z in G −t .

E.2 Subset of a path
Now, we will define the notion of a subset of a path.
Definition 14. (Subset of a path) A path P (y 1 , y j ) is said to be a subset of the path such that x i = y 1 , x i+1 = y 2 , · · · , x i+j−1 = y j and the edge between x i+l−1 and x i+l is same as the edge between y l and y l+1 ∀l ∈ [j − 1].
For example, in Figure 2, . For a path P(x 1 , x k ), it is often convenient to represent the subset obtained by removing the nodes at each extreme and the corresponding edges by P(

F Proof of Theorem 4.1 and an illustrative example
In this section, we will prove Theorem 4.1 and also provide an illustrative example for Theorem 4.1. Recall the notions of path, collider, descendant path, blocking path and d-separation from Appendix D. Also, recall the notions of subset of a path and G −t as well as Remark 5 from Appendix E.

F.1 Proof of Theorem 4.1
We re-state the Theorem below and then provide the proof. 2 Theorem 4.1. Let Assumption 1 be satisfied. Consider any x t ∈ x (o) that has a direct edge or a bi-directed edge to t i.e., either x t − → t, x t t or x t − → t. Let e be sub-sampled using x t and v for any v ⊆ V \ {x t , y } i.e., e = f (x t , v, η). Let z ⊆ x (o) \ {x t }. If e is d-separated from y by z and t in G i.e., e⊥ ⊥ d y |z, t in G, then z satisfies the back-door criterion relative to (t, y ) in G.
Proof. We will prove this by contradiction. Suppose z does not satisfy the back-door criterion relative to (t, y ) in G. From Remark 5, under Assumption 1, this is equivalent to t and y not being d-separated by z in G −t . This is further equivalent to saying that there exists at least one unblocked path (not containing the edge t − → y ) from t to y in G when z is conditioned on. Let P(t, y ) denote the shortest of these unblocked paths. We have the following two scenarios depending on whether or not P(t, y ) contains x t . First, we will show that in both of these cases there exists an unblocked path 3 P (x t , y ) from x t to y in G when z, t are conditioned on.
Note : All bi-directed edges in G are unblocked because (a) none of the unobserved feature is conditioned on and (b) there is no collider at any of the unobserved feature.
(i) x t ∈ P(t, y ): This implies that there is an unblocked path P (x t , y ) ⊂ P(t, y ) from x t to y in G when z is conditioned on. Suppose we now condition on t in addition to z. The conditioning on t can affect the path P (x t , y ) only 4 if a) there is an unblocked descendant path from some x s ∈ P (x t , y ) \ {x t , y } to t and b) x s is a collider in the path P (x t , y ) \ {x t , y } . However, conditioning on such a t cannot block the path P (x t , y ). Thus, there exists an unblocked path P (x t , y ) = P (x t , y ) in G when z, t are conditioned on.
(ii) x t / ∈ P(t, y ): Under Assumption 1, G cannot contain the edge t ← − y (because a DAG cannot have a cycle). Furthermore, under Assumption 1, t has no child other than y . Therefore, in this case, the path P(t, y ) takes one of the following two forms : (a) t ← − x s · · · y or (b) t x s · · · y for some x s = x t . In either case, there is a collider at t (i.e., either Suppose we now condition on t in addition to z. The conditioning on t unblocks the path P (x t , x s ) because there is a collider at t. Also, similar to the previous case, the conditioning on t cannot block the path P(t, y ) from t to y (passing through x s ). Therefore, we see that there is an unblocked path P (x t , y ) from x t to y (passing through t and x s ) in G when z, t are conditioned on (i.e., either Now, in each of the above cases, there is an edge from x t to e because e is sub-sampled using x t . Therefore, there exists an unblocked path P (e, y ) ⊃ P (x t , y ) of the form e ← − x t · · · y in G when z, t are conditioned on because x t / ∈ z i.e., x t is not conditioned on. This is true regardless of whether x t is an ancestor of z or not since the edge e ← − x t cannot create a collider at x t . The existence of the path P (e, y ) contradicts the fact that e is d-separated from y by z and t in G. This completes the proof.

F.2 An illustrative example for Theorem 4.1
Now, we will look into an example illustrating Theorem 4.1. Consider the DAG G bi in Figure 6. We let x t = x 1 (because x 1 t) and sub-sample e using x 1 and t (see Figure  6). For this example, z ⊆ {x 2 , x 3 } i.e., z ∈ {∅, {x 2 }, {x 3 }, {x 2 , x 3 }}. It is easy to verify that e⊥ ⊥ d y |x 2 , t but e ⊥ ⊥ d y |t, e ⊥ ⊥ d y |x 3 , t, and e ⊥ ⊥ d y |x 2 , x 3 t in G bi . Given these, Theorem 4.1 implies that z = {x 2 } should satisfy the back-door criterion relative to (t, y ) in G bi . This is indeed the case and can be verified easily. Thus, we see that our framework has the potential to identify valid adjustment sets ({x 2 } for G bi ) in the scenario where no causal parent of the treatment variable is known but a bi-directed neighbor of the treatment is known.
Note : Theorem 4.1 does not comment on whether ∅, {x 3 } and {x 2 , x 3 } satisfy or do not satisfy the back-door criterion relative to (t, y ) in G bi .
x 1 x 2 x 3 e y t Figure 6: The DAG G bi where e has been sub-sampled using x 1 and t.

G Proof of Theorem 4.2
In this section, we will prove Theorem 4.2. Recall the notions of path, collider, descendant path, descendant, blocking path and d-separation from Appendix D. Also, recall the notions of subset of a path and G −t as well as Remark 5 from Appendix E.
We re-state the Theorem below and then provide the proof. 5 Theorem 4.2. Let Assumption 1 be satisfied. Consider any x t ∈ x (o) that has a direct edge to t i.e., x t − → t or x t − → t. Let e be sub-sampled using x t and v for any v ⊆ {t} i.e., If z satisfies the back-door criterion relative to (t, y ) in G, then e is d-separated from y by z and t in G i.e., e⊥ ⊥ d y |z, t in G.
Proof. We will prove this by contradiction. Suppose e ⊥ ⊥ d y |z, t in G i.e., e and y are not d-separated by z, t in G. In other words, there exists at least one unblocked path from e to y in G when z, t are conditioned on. Let P(e, y ) denote the shortest of these unblocked paths.
Depending on the choice of v, we have the following two cases. In each of this cases, we will show that the path P(e, y ) is of the form e ← − x t · · · y .
• v = {t} : e is sub-sampled using t and x t . Therefore, the path P(e, y ) can take one of the following two forms : (a) e ← − t · · · y or (b) e ← − x t · · · y . However, t is conditioned on and the path e ← − t · · · y cannot form a collider at t (because of the edge e ← − t). Therefore, the path P(e, y ) cannot be of the form e ← − t · · · y and has to be of the form e ← − x t · · · y .
• v = ∅ : e is sub-sampled using only x t . Therefore, the path P(e, y ) has to be of the form e ← − x t · · · y . Now, observe that there is no collider at x t in the path e ← − x t · · · y and x t is not conditioned on (because x t / ∈ z). Therefore, there exists at least one unblocked path from x t to y in G when z, t are conditioned on. Let P (x t , y ) ⊂ P(e, y ) denote the shortest of these unblocked paths from x t to y in G when z, t are conditioned on. The path P (x t , y ) cannot contain the edge t − → y since t is conditioned on and the path cannot form a collider at t (because of the edge t − → y ).
We have the following two scenarios depending on whether or not P (x t , y ) contains t. First, we will show that in both of these cases there exists an unblocked path P (t, y ) from t to y (that does not contain the edge t − → y ) in G when z is conditioned on.
Note : All bi-directed edges in G are unblocked because (a) none of the unobserved feature is conditioned on and (b) there is no collider at any of the unobserved feature.
(1) t / ∈ P (x t , y ): Suppose we now uncondition on t (but still condition on z). We have the following two scenarios depending on whether or not unconditioning on t blocks the path P (x t , y ) (while z is still conditioned on).
(i) Unconditioning on t does not block the path P (x t , y ): Consider the path P (t, y ) ⊃ P (x t , y ) from t to y of the form t ← − x t · · · y . This path is unblocked in G when z is conditioned on because (a) by assumption the path P (x t , y ) is unblocked in G when z is conditioned on and (b) there is no collider at x t in this path (in addition to x t not being conditioned on since x t / ∈ z). P (t, y ) does not contain the edge t − → y because P (x t , y ) does not contain the edge t − → y .
(ii) Unconditioning on t blocks the path P (x t , y ) (Refer Figure 7 for an illustration of this case): We will first create a set x S consisting of all the nodes at which the path P (x t , y ) is blocked when t is unconditioned on (while z is still conditioned on). Define the set x S ⊆ x (o) such that for any x s ∈ x S the following are true: (a) x s ∈ P (x t , y ) \ {x t , y }, (b) the path P (x t , y ) contains a collider at x s , (c) there is a descendant path P d (x s , t) from x s to t, (d) the descendant path P d (x s , t) is unblocked when z is conditioned on, (e) x s / ∈ z, and (f) there is no unblocked descendant path from x s to any x a ∈ z. Since the path P (x t , y ) is blocked when t is unconditioned on (while z is still conditioned on), we must have that x S = ∅. Let x c ∈ x S be that node which is closest to y in the path P (x t , y ). By the definition of x S and the choice of x c , unconditioning on t cannot block the path P (x c , y ) ⊂ P (x t , y ) when z is still conditioned on. Also, by the definition of x S , the descendant path P d (x c , t) from x c to t is unblocked when z is conditioned on. Now consider the path P (t, y ) of the form t ← − · · · ← − x c ← − · · · y i.e., P (t, y ) ⊃ P (x c , y ) and P (t, y ) ⊃ P d (x c , t). The path P (t, y ) is unblocked when z is conditioned on since (a) P d (x c , t) is unblocked when z is conditioned on, (b) P (x c , y ) is unblocked when z is conditioned on, and (c) there is no collider at x c and x c is not conditioned on since x c / ∈ z. Furthermore, P (t, y ) does not contain the edge t − → y because P (x c , y ) ⊂ P (x t , y ) does not contain the edge t − → y and P d (x c , t) does not contain the edge t − → y .
(2) t ∈ P (x t , y ): In this case, there is an unblocked path P (t, y ) ⊂ P (x t , y ) from t to y when z, t are conditioned on. There are two sub-cases depending on whether or not unconditioning on t can block the path P (t, y ) (while z is still conditioned on).
(A) Unconditioning on t does not block the path P (t, y ) : In this case, by assumption, the path P (t, y ) = P (t, y ) in G is unblocked when z is conditioned on. Furthermore, since P (t, y ) ⊂ P (x t , y ), P (t, y ) does not contain the edge t − → y .
(B) Unconditioning on t blocks the path P (t, y ): Let x t be the node adjacent to t in the path P (t, y ). Consider the path P (x t , y ) ⊂ P (t, y ). Clearly, t / ∈ P (x t , y ) since the path P (x t , y ) was assumed to be the shortest unblocked path from x t to y . Therefore, the only way unconditioning on t could block the path P (t, y ) is if it blocked the path P (x t , y ). Now, this sub-case is similar to the case (1)(ii) with x t = x t and P (x t , y ) = P (x t , y ) 6 . As in (1)(ii), it can be shown that there exists an unblocked path P (t, y ) in G (that does not contain the edge t − → y ) when z is conditioned on.
x t x c e y t Now, in each of the above cases, there exists an unblocked path P (t, y ) in G when z is conditioned on and this path does not contain the edge t − → y . Therefore, there exists an unblocked path P (t, y ) in G −t when z is conditioned on (since P (t, y ) does not contain the edge t − → y ) implying t ⊥ ⊥ d y |z in G −t . From Remark 5, under Assumption 1, this is equivalent to z not satisfying the back-door criterion relative to (t, y ) in G leading to a contradiction. This completes the proof.

H The M-bias model
In this section, we discuss the M-bias problem. It is a causal model under which although some observed features (that are pre-treatment) are provided, one must not adjust for any of it. This model has been widely discussed (Imbens, 2020;Liu et al., 2012) in the literature to underscore the need for algorithms that find valid adjustment sets.
We illustrate the M-bias problem using the semi-Markov model (with the corresponding DAG G M ) in Figure 8. The DAG G M consists of the following edges: t − → y , x 1 t, x 1 y . It is easy to verify that {x 1 } does not satisfy the back-door criterion with respect to (t, y ) in G M . Further, it is also easy to verify that the empty set i.e., ∅ satisfies the back-door criterion with respect to (t, y ) in G M . In what follows, we will see how our framework cannot be used to arrive at this conclusion.
There are no observed parents of t in G M . Therefore, Theorem 4.2 (i.e., the necessary condition) does not apply here. For Theorem 4.1 to be applicable, there is only one choice of x t i.e., one must use x t = x 1 . Now, for any v ⊆ {t} such that e is sub-sampled according to e = f (x 1 , v, η), e is not d-separated from y given only t. Therefore, one cannot conclude whether or not z = ∅ satisfies the back-door criterion with respect to (t, y ) in G M from Theorem 4.1 (i.e., the sufficiency condition). In summary, we see that our sufficient condition cannot identify the set satisfying the back-door criterion (i.e., the null set) and necessity condition does not apply in the case of the M-bias problem.
Therefore, there are models where sets satisfying the back-door criterion exist (for e.g., the empty set in the M-bias problem) and our results may not be able to identify them.

I Finding all back-doors
Building on Corollary 1, we provide an Algorithm (Algorithm 3) that, when all the parents of the treatment are observed and known, finds the set of all the subsets of the observed features satisfying the back-door criterion relative to (t, y ) in G which we denote by Z. We initialize Algorithm 3 with the set Z 1 obtained by adding π(t) to every element of the power set of x (o) \ π(t). The set Z 1 can be constructed easily with the knowledge of x (o) and π(t) provided to Algorithm 3. Then, we repeatedly apply Corollary 1 to each parent in turn to identify all back-doors. We state this result formally in Corollary 2 below.

Algorithm 3: Finding all back-doors
Input: π(t), e, t, y , if e ⊥ p y |z, t then 4 Z = Z ∪ z Remark: Algorithm 3 is based on two key ideas : (1) Any subset of the observed features that contains all the parents of the treatment satisfies the back-door criterion relative to (t, y ) in G. Formally, consider the set Z 1 obtained by adding π(t) to every element of the power set of x (o) \ π(t). Then, any z ∈ Z 1 satisfies the back-door criterion relative to (t, y ) in G. We use the set Z 1 in the initialization step of Algorithm 3 as it can be constructed easily with the knowledge of x (o) and π(t).
(2) For any z / ∈ Z 1 that satisfies the back-door criterion relative to (t, y ) in G, there exists x t ∈ π(t) such that z ⊆ x (o) \ x t . In this scenario, Algorithm 3 captures z because e ⊥ p y |z, t from Corollary 1 (under Assumption 2).
We now provide an example illustrating Algorithm 3, followed by Corollary 2 and its proof.

I.1 Example
We illustrate Algorithm 3 with an example. Consider the DAG G bd in Figure 9. It is easy to verify that, for x 4 } can be constructed by adding π(t) to every element of the power set of x (o) \ π(t) i.e., to the power set of {x 3 , x 4 }). Algorithm 3 is initialized with Z 1 and the only remaining sets to be identified are {x 3 }, {x 1 , x 3 }, and {x 2 , x 3 }. When x t = x 1 , Algorithm 3 will identify {x 3 } and {x 2 , x 3 } as sets that satisfy the back-door criterion relative to (t, y ) in G bd . Similarly, when x t = x 2 , Algorithm 3 will identify {x 3 } and {x 1 , x 3 } as sets that satisfy the back-door criterion relative to (t, y ) in G bd .
x 2 x 3 x 4 x 1 y t Figure 9: The DAG G bd for illustrating Algorithm 3

I.2 Corollary 2
Recall the notions of path, collider, descendant path, descendant, blocking path and d-separation from Appendix D. Also, recall the notions of subset of a path and G −t as well as Remark 5 from Appendix E.
Corollary 2. Let Assumptions 1 and 2 be satisfied. Let Z be the set of all sets z ⊆ x (o) that satisfy the back-door criterion relative to the ordered pair of variables (t, y ) in G. If all the parents of t are observed and known i.e., π(t) = π (o) (t) is known, then Algorithm 3 returns the set Z.
Proof. From Remark 5, under assumption 1, z satisfying the back-door criterion relative to the ordered pair of variables (t, y ) in G is equivalent to t and y being d-separated by z in G −t i.e., t⊥ ⊥ d y |z in G −t . From Pearl et al. (2016), π(t) always satisfies the back-door criterion relative to the ordered pair of variables (t, y ) in G i.e., t⊥ ⊥ d y |π(t) in G −t . Consider any z ⊆ x (o) such that π(t) ⊆ z. First, we will show that t⊥ ⊥ d y |z in G −t i.e., z satisfies the back-door criterion relative to the ordered pair of variables (t, y ) in G.
Suppose t ⊥ ⊥ d y |z in G −t i.e., t and y are not d-separated by z in G −t . This is equivalent to saying that there exists at least one unblocked path (not containing the edge t − → y ) from t to y in G −t when z is conditioned on. Without the loss of generality, let P(t, y ) denote any one of these unblocked paths. The path P(t, y ) has to be of the form t ← − x t · · · y where Suppose, for a CI tester and for an increasing sample size n, we find a sequence of Type-I error rate (α n ) and Type-II error rate (β n ) going to zero i.e., α n , β n − → 0. Then, if there is a valid adjustment set, it is easy to see that our algorithm will have zero bias in the estimated effect when the significance threshold α n is used as the p-value threshold in our algorithm.

K.2 Synthetic experiment
In this sub-section, we provide more details on the synthetic experiment in Section 6.1.
Let Uniform(a, b) denote the uniform distribution over the interval [a, b] for a, b ∈ R such that a < b. Let N (µ, σ 2 ) denote the Gaussian distribution with mean µ and variance σ 2 . Let Bernoulli(p) denote the Bernoulli distribution which takes the value 1 with probability p. Let Sigmoid(·) denote the sigmoid function i.e., for any a ∈ R, Sigmoid(a) = 1/1 + e −a . Let Softmax(·) denote the softmax function.
For all our experiments, we use 3 environments i.e., e ∈ {0, 1, 2} and generate the sub-sampling variable as below withÊ denoting the empirical expectation. While other choices of sub-sampling function f could be explored, the natural choice (for discrete e) of softmax with random weights suffices.
62 ∈ Uniform(−2, −1) In other words, we keep separation between the weight vectors associated with different environments to make sure that the environments look different from each other as expected by IRM.
Success Probability. For a given p value threshold, we let the success probability of the set {x 2 } be the fraction of times (in n r runs) the p-value of CI(e ⊥ p y |x 2 , t) is more than p value . In Figure 10a below, we show how the success probability of the set {x 2 } varies with different p value thresholds i.e., {0.1, 0.2, 0.3, 0.4, 0.5} for the dataset used in Section 6.1. As we can see in Figure 10a, the success probability of the set {x 2 }, for the same p value threshold, is much lower in high dimensions compared to low dimensions. We believe this happens (a) because of the non-ideal CI tester and (b) because the number of samples are finite. In contrast, our algorithms IRM-t and IRM-c always pick the set {x 2 } to adjust on i.e., z irm = {x 2 } for both IRM-t and IRM-c for d = 3, 5, 7.  Sparse subset search. In Section 6.1, we validated our algorithm by letting X be the set of all subsets of x (o) \ {x t }. However, for this synthetic experiment, we do know that only x 2 ∈ X satisfies the back-door criterion relative to (t, y ). Further, we know that x 2 is d-dimensional. Therefore, with this additional knowledge, we could instead let X be the set of alld-dimensional subsets of In other words, we consider the Sparse algorithm from Section 6 with k =d 7 . We show the performance of this algorithm for this choice of X , in comparison to the Baseline (i.e. using all observed features) as well as IRM-t and IRM-c, in Figure 10b for d = 3, 5, 7. With this restriction on the candidate adjustment sets, our algorithm performs better than it does in Figure 4b where there are no restrictions on the candidate adjustment sets.
Performance with dimensions. The gains of our testing and subset search based algorithm over the Baseline are much more in the low dimensions compared to the high dimensions as seen in Figures 4b and 10b. We believe there are two primary reasons behind this : (a) The CI tester leaks more false positive in high dimensions compared to low dimensions (see Appendix K.1) and (b) The CI tester fails to consistently output a high p-value for the set {x 2 } in high dimensions (see Figure 10a). The gains of our IRM based algorithm remain consistent even in high dimensions as expected.

K.3 Generating the environment/sub-sampling variable
In all our experiments in Section 6, we let the sub-sampling variable depend on both x t and t. Now, we will look into the case where the sub-sampling variable is generated as a function of only x t = x 1 i.e., e = f (x 1 ). More specifically, we generate the sub-sampling variable as below: 61 , θ  Figure 11. As we can see in Figure 11a, Figure 11b, Figure 11c, and Figure 11d, the performance of our algorithm with e = f (x t ) is similar to (at a high level) its performance with e = f (x t , t). This should not be surprising since Corollary 1 holds for any v ⊆ {t} i.e., for both v = ∅ and v = {t}. In other words, while theoretical tradeoff between the choice of v i.e., ∅ or {t} is unclear, there is no major empirical difference.
Note: We do not show the performance of IRM based algorithms for e = f (x 1 ) since it is exactly the same as the performance for e = f (x 1 , t). (d) Performance of Algorithm 1 on G toy when the candidate adjustment sets ared-dimensional. Figure 11: Validating our theoretical results and our Algorithm 1 on G toy when e = f (x t ).

K.4 IHDP
In this section, we provide more details on experiments in Section 6.2 on the IHDP 8 dataset.
Dataset Description. First, we describe various aspects measured by the features available in this dataset. The feature set comprises of the following attributes (a) 1-dimensional: child's birth-weight, child's head circumference at birth, number of weeks pre-term that the child was born, birth order, neo-natal health index, mother's age when she gave birth to the child, child's gender, indicator for whether the child was a twin, indicator for whether the mother was married when the child born, indicator for whether the child was first born, indicator for whether the mother smoked cigarettes when she was pregnant, indicator for whether the mother consumed alcohol when she was pregnant, indicator for whether the mother used drugs when she was pregnant, indicator for whether the mother worked during her pregnancy, indicator for whether the mom received any prenatal care, (b) 3-dimensional: education level of the mother at the time the child was born, and (c) 7 -dimensional: site indicator.
The set of all observed features satisfies the back-door criterion for IHDP. As described in Section 6.2, the outcome simulated by the setting "A" of the NPCI package depends on all the observed features. In other words, there is a direct edge from each of the observed feature to the outcome y in this scenario. Also, recall from Section 6.2 that the feature set is pre-treatment (i.e., it satisfies Assumption 1). Therefore, from Remark 5, z ⊆ x satisfies the back-door criterion relative to (t, y ) in G if and only if t and y are d-separated by z in G −t . Here, when z is the set of all observed features, it is easy to see that t and y are d-separated by z in G −t . Therefore, the set of all observed features satisfies the back-door criterion.
Choices of features in x (o) . As mentioned in Section 6.2, we keep the feature child's birth-weight in x (o) . In addition to these, we also keep the number of weeks pre-term that the child, child's head circumference at birth, birth order, neo-natal health index, mother's age when she gave birth to the child , child's gender, indicator for whether the mother used drugs when she was pregnant, indicator for whether the mom received any prenatal care, and site indicator in x (o) .
Existence of valid adjustment sets of size 5. Since x (o) comprises of only 10 different features, the set of all subsets of x (o) \ {x t } comprises of 512 elements for any x t . Therefore, in principle, one could find the set with lowest ATE error amongst these 512 candidate adjustment sets instead of the averaging performed by our algorithm (Algorithm 1). In an attempt to do this for comparison with our algorithm, we accidentally came across the following subset of features : x (m) = {child's head circumference at birth, birth order, indicator for whether the mother used drugs when she was pregnant, indicator for whether the mom received any prenatal care, site indicator}. The ATE estimated using x (m) to adjust (termed as 'the oracle') significantly outperforms the ATE estimated using x (o) to adjust (termed as 'the baseline' i.e., Baseline) as shown in Figure 12a.  Therefore, we believe that there exist valid adjustment sets of size 5 (or adjustment sets better than x (o) ) for this dataset. Therefore, to curtail the run-time of Exhaustive, we consider Sparse with X = subsets of x (o) \ {x t } with size at-most 5 in Section 6.2. However, as mentioned in Section 6.2, the performance of Sparse is similar to that of Exhaustive since (a) Sparse has to perform 382 tests and (b) there is no guarantee that x (m) will be picked as a valid adjustment set (as explained below). Finally, we point out that the performance of IRM-t is closest to 'the oracle' as evident from Figure 5a.
Success Probability. Similar to Section K.2, we consider the success probability of the set x (m) . For a given p value threshold, we let the success probability of the set x (m) be the fraction of times (in n r runs) the p-value of CI(e ⊥ p y |x (m) , t) is more than p value . In Figure 12b, we show how the success probability of the set x (m) varies with different p value thresholds i.e., {0.1, 0.2, 0.3, 0.4, 0.5} for IHDP.

K.5 Cattaneo
In this section, we provide more details on experiments in Section 6.3 on the Cattaneo 9 dataset.
Dataset Description. We describe various aspects measured by the features available in this dataset. The feature set comprises of the following attributes : mother's marital status, indicator for whether the mother consumed alcohol when she was pregnant, indicator for whether the mother had any previous infant where the newborn died, mother's age, mother's education, mother's race, father's age, father's education, father's race, months since last birth by the mother, birth month, indicator for whether the baby is first-born, total number of prenatal care visits, number of prenatal care visits in the first trimester, and the number of trimesters the mother received any prenatal care. Apart from these, there are also a few other features available in this dataset for which we did not have access to their description.
For IRM, we use 15000 iterations. We train the IRM framework using 2 environments and perform validation on the remaining environment. For validation, we vary the learning rate (of the Adam optimizer that IRM uses) between 0.01 and 0.001 and vary the IRM regularizer between 0.1 and 0.001. During training, we use a step learning rate scheduler which decays the initial learning rate by half after every 5000 iterations. Entner et al. (2013) and Gultchin et al. (2020) As described in Section 4, Entner et al. (2013) and Gultchin et al. (2020) cannot be used to conclude that ∅, {x 3 }, and {x 2 , x 3 } are not admissible i.e., not valid backdoors in G toy (because the variable x t = x 1 has an unobserved parent) while our Theorem 4.2 can be used to conclude that. Here, we provide the p-values (averaged over 100 runs) corresponding to these in Table 1. As we can see, our invariance test results in a very small p-value for ∅, {x 3 }, and {x 2 , x 3 } leading to the conclusion that they are not valid backdoors in G toy . {x 2 , x 3 } 1.8 × 10 −4 ± 1.8 × 10 −4 5.1 × 10 −3 ± 3.6 × 10 −3 1.9 × 10 −4 ± 1.3 × 10 −4 K.8 Comparison with Cheng et al. (2020) As described in Section 4, Cheng et al. (2020) cannot be used to conclude that ∅, {x 2 }, {x 3 }, and {x 2 , x 3 } are not admissible i.e., not valid backdoors in the DAG obtained by adding the edge x 1 → y to G toy (because there is no COSO variable) while our Theorem 4.2 can be used to conclude that. Here, we provide the p-values (averaged over 100 runs) corresponding to these in Table 2. As we can see, our invariance test results in a very small p-value for ∅, {x 2 }, {x 3 }, and {x 2 , x 3 } leading to the conclusion that they are not valid backdoors. {x 2 , x 3 } 3.5 × 10 −7 ± 3.4 × 10 −7 1.1 × 10 −3 ± 7.8 × 10 −4 1.4 × 10 −3 ± 1.3 × 10 −3