Partial Identification of Counterfactual Distributions
Authors: Junzhe Zhang
Elias Bareinboim
Jin Tian
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Causal inference
Graphical Models

Abstract: This paper investigates the problem of bounding counterfactual queries from a combination of observational data and qualitative assumptions about the underlying data-generating model. These assumptions are usually represented in the form of a causal diagram (Pearl, 1995). We show that all counterfactual distributions (over finite observed variables) in an arbitrary causal diagram could be generated by a special family of structural causal models (SCMs), compatible with the same causal diagram, where unobserved (exogenous) variables are discrete, taking values in a finite domain.  This entails a reduction in which the space where the original, arbitrary SCM lives can be mapped to a dual, more well-behaved space where the exogenous variables are discrete, and more easily parametrizable. Using this reduction, we translate the bounding problem in the original space into an equivalent optimization program in the new space. Solving such programs leads to optimal bounds over unknown counterfactuals. Finally, we develop effective Monte Carlo algorithms to approximate these optimal bounds from a finite number of observational data. Our algorithms are validated extensively on synthetic datasets.

Partial Identification of Counterfactual Distributions
Anonymous Author(s)
Affiliation
Address
email
Abstract
This paper investigates the problem of bounding counterfactual queries from a combination of observational data and qualitative assumptions about the underlying data-generating model. These assumptions are usually represented in the form causal diagram (Pearl, 1995). We show that all counterfactual distributions (over finite observed variables) in arbitrary causal diagram could be generated by a special family of structural causal models (SCMs), compatible with the same causal diagram, where unobserved (exogenous) variables values a finite domain. This entails reduction in which the space where the original, arbitrary SCM lives can be mapped to dual, more well-behaved space where the exogenous variables are discrete, and more easily parametrizable. Using this reduction, we translate the bounding problem in the original space into equivalent optimization program in the new space. Solving such programs leads to optimal bounds over unknown counterfactuals. Finally, we develop effective Monte Carlo algorithms to approximate these optimal bounds from finite number of observational data. Our algorithms are validated extensively synthetic datasets.
2
6
discrete, taking
10
12
13
14
15
Introduction
16
17
This paper studies the problem of inferring counterfactual queries from the combination non- experimental data (e.g., observational studies) and qualitative assumptions about the Kata-generating 19 process. These assumptions are represented in the form a causal diagram [32], which directed acyclic graph where arrows indicate the potential existence of functional relationships among corresponding variables; some variables are unobserved. This problem arises diverse fields such artificial intelligence, statistics, cognitive science, economics, and the health and social sciences.
21
23 For example, when investigating the gender discrimination college admission, one may ask "what would the admission outcome be for female applicant had she been male?" Such counterfactual
25 query contains conflicting information: in the real world the applicant is female, in the hypothetical world she was not. Therefore, is not immediately clear how to design effective experimental procedures for evaluating counterfactuals, let alone how to compute them from observations alone.
26
27
The problem of identifying counterfactual distributions from the combination of data and causal diagram has been studied in the causal inference literature. First, there exist a complete proof system for reasoning about counterfactual queries [19]. While such system, in principle, is sufficient in evaluating any identifiable counterfactual expression, it lacks a proof guideline which determines the feasibility of such evaluation efficiently. There algorithms to determine whether counterfactual distribution is inferrable from all possible controlled experiments 41 There exist also algorithms for identifying path-specific effects from experimental data [I] and observational data Ap
29
31
33
34
35 In practice however, the combination of quantitative knowledge and observed data does not always permit one to point-identify the target counterfactual queries. Partial identification methods concern 37 with deriving informative bounds over the target counterfactual probability, even when the target
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

2
X
X
(a) IV
(b) Double bow
(c)
(d) Bow
Figure DAGs variables U: Z in 1s also referred to as an instrumental variable.
containing a treatment X, an outcome Y. an ancestor Z, and exogenous
38 itself is non-identifiable. Several algorithms have been developed to bound counterfactuals from the 25
39
combination of observational and experimental data 60 36
35 23
24
16
49
In this work, we build on the approach introduced by Balke & Pearl in which involves direct discretization of the exogenous domains, also referred to as the principal stratification [17 84 Con- sider the causal diagram of Fig. where X, Y, Z are binary variables in {0, 1): U is unobserved variable taking values in an arbitrary continuous domain. 3 showed that domains of U could be discretized into 16 equivalent classes without changing the original counterfactual distributions and the graphical structure in Fig. Ta For instance, despite it being induced by an arbitrary distribution Pa (u) over continuous domain of the exogenous variable U, the observational distribution P(x. y|2)
41
43
44
45
46
47
must be reproduced by a generative model of the form P(z, y/z) = >. P(r 22ru,,)2P. Pyyl,, u) P(u), where (uu) is discrete distribution over finite exogenous domain , 16).
48
49
Using the finite-state representation of unobserved variables, effects under the condition of noncompliance in Fig. [ representation in a Bayesian framework, to obtain credible intervals for the posterior distribution of causal effects in noncompliance settings. Despite their optimal guarantees, these bounds are only applicable to the specific noncompliance setting in Fig. Ta For the most general cases, a systematic procedure for bounding counterfactual queries in arbitrary causal diagrams is still missing.
4 derived tight bounds on treatment
21 applied the parsimony of finite-state
51
52
58
54
55
Our goal in this paper is to overcome these challenges. We investigate the expressive power of discrete structural causal models (SCMs) [3 where cach unobserved variable is drawn from discrete distribution, takes values in finite set of states. We show that when inferring about counterfactual distributions (over finite observed variables) in an arbitrary causal diagram, could restrict domains of unobserved variables to a finite space without loss of generality. This observation allows us to develop novel partial identification algorithms to bound unknown counterfactual probabilities from the observational data. More specifically, our contributions are as follows. special family of discrete SCMs, with finite unobserved domains, and show that it could represent all categorical counterfactual distributions in an arbitrary causal diagram. (2) Using this result, we translate the original partial identification task into equivalent polynomial programs. Solving such programs leads to informative bounds over unknown counterfactual probabilities, which are provably optimal. (3) We develop an effective Monte Carlo algorithm to approximate optimal counterfactual bounds from a finite number of observational data. Finally, our algorithms are validated extensively on synthetic datasets. Given space constraints, all proofs are provided in Appendices and B
57
59
61
(1) We introduce a
82
63
64
85
86
87
68
1.1 Preliminaries
We introduce in this section some basic notations and definitions that will be used throughout the
71 paper. We use capital letters to denote variables (X), small letters for their values (x) and Ωx for their domains. For an arbitrary set X, let X be its cardinality. For convenience, we denote by P(ar)
73 probabilities P(X- = x); for an arbitrary subdomain X C Ωxx P(X) P(X E X). Finally, the
74 indicator function 1x= xx= returns 1 if an event X holds true; otherwise 1x== = 0.
75 The basic semantical framework of our analysis rests on structural causal models (SCMs) [3
76 Ch. 7]. An SCM M is tuple (V. U, F, P) where V is a set of endogenous variables and U is is a set of functions where each fv E F decides values of an 78 endogenous variable V E V taking as argument a combination of other variables in the system. That
77 a set of exogenous variables.
79 is, v + (pay,, w Pav C VV C U. Exogenous variables E U are mutually independent, values of which are drawn from the exogenous distribution P(u). Naturally, M induces joint 81 distribution P(v) over endogenous variables V. called the observational distribution. Each SCM is associated with a causal diagram G (c.g.. Fig. D.. which is directed acyclic graph (DAG) where

---

83
solid nodes represent endogenous variables V, empty nodes represent exogenous variables U and 84 arrows represent the arguments Pay, Uv of each function fv.
85 An intervention on an arbitrary subset X C V. denoted by do(æ)), is an operation where values of
86 X are set to constants æ; regardless of how they are ordinarily determined. For SCM M, let Ma denote a submodel of M induced by intervention do(æ). For any subset Y S V, the potential 88 response Y₂ ( (u) is defined as the solution of Y in the submodel Ma given U- u. Drawing values of exogenous variables U following the probability measure P induces a counterfactual variable Ya-
87
89
90 Specifically, the event Y² = y (for short, Ya)) can be read as "Y would y had X been x". For any W S V. the distribution over counterfactuals Y....., Zw is defined as: subsets Y. Z, X.
91
P (yym:... Zuo) = S2y
(x A... (.
(I)
82 Distributions of the form P(ym) is called the interventional distribution; when the treatment set 98 X 0, P(y) coincides with the observational distribution. Throughout this paper, we assume that endogenous variables V are discrete and finite; while exogenous variables U could take any (continuous) value. The counterfactual distribution P (ye,... ..... zw defined above is thus categorical distribution. For a more detailed survey on SCMs, we refer readers to 33 Ch. 7].
94
95
96
Discretization of Structural Causal Models 2
97
For DAG G with endogenous V and exogenous variables U, let P denote the collection of all counterfactual distributions over variables V. Formally,
99
p (P (P
AY vY....,,,xX NKK...,WWV.. WVV..
(2)
100
Let M be the family of all the SCMs compatible with the causal diagram G. i.e,, Al
{VM GM - Counterfactual distributions in G are defined as the collection ( (PMr : VV E .ff that contains all counterfactual probabilities induced by SCMs M in the candidate family M. In this
101
102
103
section, we will show that counterfactual distributions in any causal diagram G could be generated by an alternative family of "generic" SCMs compatible with G, which we will define later. Definition
104
105
Fauurraaettal-Fuaiaaeeeeeeee For a DAG G. Ae, .N be two sets of SCMs compatible with G. M and N are said to be counterfactually equivalent (for short, ctf-equivalent) if for any M E M, there exists an alternative N E EV such that P = Pj, and vice versa.
106
107
108
Our analysis rests on a special family of SCMs where values of each exogenous variable are drawn from a discrete distribution over finite set of states.
109
110
Definition 2. An SCM M = (V.U, F, P) is said to be discrete SCM if
1. Values of every U U are drawn from discrete distribution P(u) over a domain Py: let On denote the probability PUU = u), for any u E Py- f
112
2. Values of every V E V are decided by function + fv (paa,, uv)= EV uv) where for
113
Vpav, uv, 5 (p)) is constant in the finite domain Gyy
114
Given a causal diagram G, our goal is to construct family of discrete SCMs V that is counter- factually equivalent to the original family of SCMs M. Our construction utilizes a special type of clustering of nodes in the diagram, called the confounded component (45).
116
118
Definition 3. For an DAG G. a subset C' C V is a c-component if any pair X,Y E C' is connected
in & by a bi-directed path of the form V1 + 1/2 + ++ Vn, n 1, 2, .... where (1) V1 X, V, = (2) (Vi..., V. S V: and (3) each V; + Vj is a sequence V; < Us- - V, and Ug E U.
120
121 A c-component C' in G is maximal if there exists no other c-component that contains C. We denote by C(G) the collection of all maximal c-components G. Naturally, e-components in C(G) form partition over endogenous variables V. which, in turn, defines partition (Uvecliv VC' E C(G))
122
123
124
over exogenous variables U. Therefore, for every U E U, there must exist a unique e-component
125
in C()), denoted by Cv. such that U E Uvec, Uv. For example, exogenous variables U1, U2 in
126
Fig. la corresponds c-components Cu, = {2} and Co, = (X, Y3 respectively; while the causal diagram of Fig. lb only has single c-component Y,
127
'We will use the subscript M to represent the restriction to a specific SCM M. Therefore, GM represents the causal diagram associated with SCM M; so does the collection of counterfactuals Pi.
3

---

128
Theorem 1. For a DAG g, consider the following condition (1) M is the set of all SCMs compatible with G: (2) .Y is the set of all discrete SCMs compatible with G where for every U E U. its cardinality [Ry] = Ivec, |Spay + ( i.e, the number of functions mapping from Pay to V for every variable V in the c-component Cv. Then, M and N are counterfactually equivalent.
129
130
131
132
Thm. establishes the expressive power of discrete SCMs in representing counterfactual distributions in a causal diagram G. It implies that the counterfactual distribution P (ya....,, ;Zw) in any SCM M could be generated using a generic model as follows, for du = -IvvEo [Prar Styl
133
134
P (Yzz
Σ
Σ
I [yz(u)=y/ A A A (w)==
II 0.-
(3)
UEU u=I,..,d
UEU
135
Among above quantities, 8, are parameters of the exogenous distribution P(u) over a finite domain {1. ..... d Counterfactual variables (u) are recursively defined as follows:
136
xt
if E X
Yu(u) = (Ya(u) VY E Y). where (zu)) =
c (Vo (aa
(4)
otherwise
137
where Zy is the value assigned to variable Y in constants æ. As an example, consider the causal diagram G described in Fig. Lb where X,Y, Z are binary variables in {0, 1}. Since & has single c-
138
139
component {X, Y, Z} exogenous variables U,, U2 must share the same cardinality d in the proposed family of discrete SCMs N. It follows from Thm. I the counterfactual distribution Pf yar) in any SCM compatible with G could be written as follows:
140
141
P(z, Iz,
Σ 212211=1
( A 1 19
1 Es (0)= Our Ouzi
(5)
142
where ((a)) (02) (())
-xx Sy are parameters taking values in {0, 1}; ou,. i 2, are probabilities
143
of the discrete distribution P(u.) over the finite domain {1...., d}. The cardinality d = [52z] x
144
[2z + 2xx [2x + fyy 32. The total cardinalities of domains for U1, U2 are thus 2d 64.
145
Comparison with related work One could naively apply the discretization procedure in f and obtain a family of discrete SCMs that are sufficient in representing distributions in an causal diagram. However, such parametrization is not necessarily complete. To witness, consider again the causal diagram in Fig. Tb with binary X, Ył Z. Applying the discretization in 3 leads to a family of discrete SCMs compatible with a different diagram in Fig. [c where the cardinality of exogenous variable U is equal to d 32 (see Appendix D for details). However, this parametrization fails to capture some critical constraints over counterfactual distributions since does not maintain the original structure of the causal diagram. For instance, counterfactual variables Z and Y, in the original diagram of Fig. [b] are independent due to independence restrictions 3 Ch. 7.3.2]; while 2 and
147
149
151
152
153
154
Yz in Fig. Ic are generally correlated due the presence of unobserved confounder U. Compared with R. the discretization method in Thm. captures all constraints over counterfactual distributions while requiring only a factor of [U] increase in the cardinality of exogenous domains.
155
156
157 More recently. [S] proved a special case of Thm. T for interventional distributions in a specific class of causal diagrams that satisfy the running intersection property. When there is no direct arrow between endogenous variables, [38] showed that the observational distribution in a diagram could be represented using finite-state exogenous variables. Thm. I generalizze these results by showing that, for the first time, all counterfactual distributions in an arbitrary causal diagram could be generated using discrete exogenous variables taking values from finite domain, without any loss of generality.
159
160
161
162
163
2.1
Partial identification of Counterfactual Distributions
164 To demonstrate the expressive power of discrete SCMs, we investigate the problem of partial iden- tification of counterfactual distributions. For an SCM M = (V. U, F, P), we are interested in evaluating an arbitrary counterfactual probability P(ya: ... 2.) The detailed parametrization of
165
186
M' is unknown. Instead, the learner only has access to the causal diagram G and the observa- tional distribution P(v) induced by M Our goal is to derive an informative bound [1,]] from the combination of G and P(v) that contains the actual counterfactual probability P(ye.... Zw).
168
For every V E V. Prey + Gy is the set of all functions mapping from domains Prey Qy.

---

170 Let L denote the family of discrete SCMs defined in Thm. 1 which are compatible with the causal
171 diagram G. We derive bound [1. over Ply....... :u) from the observational data P(v) by solving the following optimization problem:
172
|. r min / max (y ww) E (NN(N) P
(6)
For instance, consider again the double-bor bow diagram 9 in Fig. P(x, 2) in any discrete SCM in N could be written as:
1b. The observational distribution
174
d
((),
Σ
1 ( A A dew s)) Pn, Oug
5x
175 One could derive a bound over the counterfactual distribution Plz, Mr') from the observational
176 data P(ar, y: 2) by solving polynomial programs which optimize the objective Eq.
5 over parameters
c(a1) ((2.01.22) c(z.w2), subject to the observational constraints Eq.
Ous Owz, Sz .5x
As corollary, follows immediately from Thm. that the solution [1, of the optimization problem
Eq. 66 is guaranteed to be a valid bound over the unknown counterfactual P(y .Zw)
179
Corollary (Soundness). Given a DAG G and an observational distribution P(v), let .ll be the set of all SCMs compatible with 9 and let Mr +(VM .l (M) P(v)}. For the solution [1,
180
of Eq. 60. (y tw) E [1,r] r) for any SCM M E Mo.
182
Since the underlying SCM M E Mo. Corol. 1 Iimples that the derived bound [1, rl must contain the actual counterfactual probability P(yz:..... ) Our next result shows that such a bound [7, is provably tight, i.e., cannot be improved without additional assumptions.
183
184
185
186
Corollary (Tightness). Given DAG G and an observational distribution P(v), let M be the set of all SCMs compatible with & and let M. (VM E Al (M)(2) = =P(w)} For the solution [1 of Eq. 66. there exist SCMs M1, M2 E M, such that Pas, (Ya...., : zw) =1 PM, (ye...... zwo r.
187
188
Corol. 2 confirms the tightness of the bound [1 obtained from Eq. 60. Suppose there exists valid
190
bound I' r'r strictly contained in r.. One could construct from Corol. 2 an SCM M compatible
with the causal diagram G and the observational distribution P(v), but its counterfactual probability
192 P yy...... zw) lies outside [l', r"]. which is a contradiction.
193
The optimization problem of Eq. (6 is reducible to equivalent polynomial programs (see Appendix E. Despite the soundness and tightness of derived bounds, solving such programs may take exponentially long in the most general case [2]] Our focus here is upon the causal inference aspect of the problem and like earlier discussions we do not specify which solvers are used 3 In some cases of interest, effective approximate planning methods for polynomial programs do exist. Investigating these methods an ongoing subject of research 26
194
196
196
3 Bayesian Approach for Partial Identification
199
200
This section describes an effective algorithm to approximate the optimal counterfactual bound in Eq. 6 provided with finite samples = (x(")) Jn= drawn from the observational distribution
P( (v)) and prior distributions over parameters 8,, and </ c(pay.uv) (possibly uninformative).
203
We first introduce Markov Chain Monte Carlo (MCMC) algorithms that sample the posterior distribu- tion P (O 6) over a counterfactual probability 0ur P (ym..... ...). More specifically, for every
V E V. Vpay, uv, parameters < (wv) are drawn uniformly over the finite domain ly. For every U E U. exogenous probabilities 0g, are drawn from generalized Dirichlet distribution [12.. We will take the view a stick- breaking construction 40 which successively breaks pieces off a unit-length stick with size proportional to random draws from Beta distribution. Parameters 6, are proportions of each of the pieces relative to its original size. Formally,
205
207
209
Yu = mu=1,2.. 1.2..... du.
0_ = pbu II
(1
n.),
Pa ~ Beta (ale) ,
(8)
5

---

6U1
U2!1
U P9
U2 P9
U
U P
X11
Y1
X
YR2)
X
yhv
EZ
Ex
Ex
Figure 2: The data-generating process for the observational data {x(m), y 2 N associated with the causal diagram in Fig. For every exogenous variable E U. 8u = (0, Vu). For every endogenous variable V V. εv {
J n=1 in an SCM
(l av) Vpaa, uV
where du EC. Prav + 14g and Oig B are hyperparameters. Finally, truncate this construction by setting Mdl 1. Note from Eq.
(w)
S that all parameters 0, for >> dy are equal to zero. As an example, Fig. shows a graphical representation the data-generating process over
212
parameters 0n and gy uuv) associated with SCMs in Fig. 1 spanning over N observations.
Gibbs sampling well-known MCMC algorithm that allows one to sample posterior distributions. For convenience, we introduce the following notations. Let parameters 0 {Ow, YU e U, Vu}
215
and E { ((paysu)) VV E V, Vpaa, uv The set U = {U(m) N 216
n= are exogenous variables
affecting N observations V = [v(")) n= we use ú to represent their realizations. Our blocked Gibbs sampler works by iteratively drawing values from the conditional distributions of variables as follows 22 Detailed derivations of complete conditional distributions are shown in Appendix
217
219
Sampling ( 6, () Exogenous variables U(x),,
I,...,,,, N,, are mutually independent corresponding to the nth observation
given parameters 0, We could draw each (U(n) 10, &, V)
independently. The complete conditional for (m) is given by
222
P ((
0.5)
II VEV
II 0..
(m EV
zolm) UEU
Sampling P (E, ú. u) Parameters 0 are independent given V, U. Therefore, will derive
complete conditional &, separately. Note that in discrete SCMs, the nth observation variable
224
V E V is decided by v(n) e(pay. given pay (m) pay, uy uv. Thus, draw values of each ap)) E from the complete conditional defined as: SV
226
1 1 3f s.t. pa pav, uv uv,
P (((mavaur)
0, ū
Ev 1//00l
(10)
otherwise.
Let nu EN I,(n)= records the number of values in (r) that are equal to u. By the conjugacy of the generalized Dirichlet distribution, the complete conditional of O,, is given by, for every U E U,
227
228
Yu 1.2....d22 du. 0n pa [I (1))),,
pi). Mhu Beta
(1) av + Tuu
U
(u)
n
(11)
==1
kma-111
Doing so eventually produces values drawn from the posterior distribution over (0,E, V). Given parameters E. we compute the counterfactual probability Oet P(y following the
229
230
three-step algorithm in [3 which consists of abduction, action, and prediction. Thus computing far from each draw 0, U eventually gives the draw from the posterior distribution P (Beu B).
232
3.1
Collapsed Gibbs Sampling
234
also describe an alternative sampler that applies to stick-breaking priors with known Pólya characterization. Formally, consider stick-breaking priors in Eq. ( with hyperparameters

---

(0) auy and ( = (dv / for some real ay > 0. Let U-n denote the set OU difference U U(m); so does V-n V V(n), Our collapsed Gibbs sampler first iteratively draws values from the conditional distribution of (Ur()) U-n, V), n I,....,N,, N, as follows.
Sampling P (z)a))
B, u.n.
At etchh iteration, draw U(m) from the conditional given by uy ① -- u-n
P
U, u u.nun)
x II P ((((m) pay (n)
II
(u(m) (8-n:un)) (12)
VEV
VEU
240
Among quantities in the above equation, for every V VEV.
[1(m)=ot if pay (i)
pay (n) (0) (n)
(x)) P (uln) pay" uV 8 B_n, umn)
(n)
"V -uv (13)
1//1rl
otherwise.
For every U E U, let ü.n be set of exogenous samples (u())... ....., un u((+1)) uN) Let {ui "ui.,.,, " denote K unique values that samples in ū-n take on.
n + au/dy
if uf = =i for l = 1....... K
P (u(()) Ü-n. ū.)
au + +N- - oz (1 K/dr)
(14)
if (() & (ui uk]
au + where niz = Eifen 1u(0=u records the number of values in (1) E ü-n that are equal ug.
243
Doing so eventually produces exogenous variables drawn from the posterior distribution of (Ú
244
We then sample parameters from the posterior distribution of (0, & Ü, V); the complete conditional P (E. 0 o. ū are given in Eqs. (TP) and IT]. Finally, computing 6er from each sample 9, & gives us draw from the posterior distribution P P(err] 8).
245
246
248
When the cardinality dy of exogenous domains is high, the collapsed Gibbs sampler described here more computational efficient than the blocked sampler, since it does not iteratively draw parameters 0, & in the gigh-dimensional space. Instead, the collapsed sampler only draws 0, & once after samples drawn from the distribution of (Ú V) converge. On the other hand, when the cardinality du is reasonably low, the blocked Gibbs sampler is preferable since it exhibits better convergence [22]
250
252
3.2
Credible Intervals over Counterfactual Probabilities
254
Given a MCMC sampler, one could bound the counterfactual probability Oar by computing credible intervals from the posterior distribution P (far v)).
255
296
Definition 4. Fix a E [0, 1). A 100(1 - a)% credible interval [la, ra] for Oer is given by
La = sup [
P (fat S 8) a/2}. Ta = inf {o P (far S ú) 1 a/2).
(15)
257
For 100 - 3% credible interval [l,, ral, any counterfactual probability Par that is compatible with observational data e lies between the interval la and ra with probability 1 a. Credible intervals have been widely applied for computing bounds over counterfactuals provided with finite observations 20 47 37 46]. As the number of observational data N grows (to infinite), the 100%
259
261
credible interval (4o, ro] eventually converges to the optimal asymptotic bound [4, r] in Eq. 6 T 1
Let (0(0)
be T' samples drawn from P (Oat ū). One could compute the 100(1 a)% credible interval for using the following consistent estimators
263
(T) = g(((a/2)11)
fa (T) g(((1-a/2)1)
(16)
where (((()/2)7), (((() (()(1)) are the th smallest and the [(1 a a/2)T smallest of
284
265
{ 1B
Our next results establish nom-asymptotic deviation bounds for the empirical estimates of
266
credible intervals defined in Eq. (G for finite samples.
267
Lemma 1. Fix T and (0, Let function f(T,8) V2T--11n4- In(66),, With probability at
288
least 1 8, estimators (T)) for any a E [0, 1) is bounded by
(a)) E (a
(T) E Tr
(17)
For any real IR, [a] denotes the smallest integer n ' larger than ie., [a] min(n E 2 a).
7

---

289
We summarize our algorithm, CREDIBLEIN-
Algorithm 1: CREDIBLEINTERVAL
270
TERVAL, Alg. I It takes a credible level
and tolerance levels 8, as inputs. In par-
1: Input: Credible level a, tolerance level ó,
272
ticular, CREDIBLEINTERVAL repeatedly draw
2: Output: An credible interval [l. hal for ter-
T 2 [2 (n(4/8] samples from P (fett Ø).
3: Let T = [2 I2 [n(4/
273
274 It then computes estimates i. (T). (T. from
4: Draw samples {0(1) ..... ( from the
275
drawn samples following Eq. (T) and return them as the output. It follows immediately from Lem. that such a procedure efficiently approx- imates 100(1 a)% credible interval.
posterior distribution P (0at ().
276
5: Return interval (T)) (T) (Eq. (1
277
278
Corollary 3. Fix 5 E (0,1) and 0. With probability at least 1 8, the interval [i, CREDIBLEINTERVAL ó, for any a E [0, 1) is bounded by byle (la-e:lo+e) and e [Tates Ta-e]-
280
Corol. implies that any counterfactual parameter Oar compatible with observational data i falls between [1 = CREDIBLEINTERVAA
8, e) with probability P (Bur E [2,6] 8) ~ 1 - - c. As
282
the tolerance rate c -> 0, [1, f) converges to a 100(1 a3% credible interval with high probability.
283
4
Simulations and Experiments
284
285
We demonstrate our algorithms on various simulated SCM instances and real world patient dataset collected from the International Stroke Trial (IST) [0. Overall, we found that simulation results sup- port our findings and the proposed bounding strategy consistently dominates state-of-art algorithms.
286
287
288
When target distributions are identifiable (Experiment 1), our bounds collapse to the actual, unknown counterfactual probabílities. For non-identifiable settings, our algorithm obtains sharp asymptotic bounds when closed-fore solutions already exist (Experiments 2 & 3); and improves over state-of-art bounds in other more general cases where the optimal strategy unknown (Experiment 4).
289
280
291
292
In all experiments, we evaluate our proposed bounding strategy based on credible intervals (ct). In particular, draw x 10x samples from the posterior distribution over the target counterfactual
293
294
(Ber V). This allows us to compute 100% credible interval over Par within error 6 = 0.05, with probability at least 1 - 5 = 0.95. As the baseline, we also include the actual counterfactual probability
295
296
g For details on simulation setups and additional experiments, we refer readers to Appendix C
297
Experiment 1: Frontdoor Graph This experiment evaluates our sam- pling algorithm on interventional probabilities that are identifialle from the observational data. Consider the "Frontdoor" graph described in
U
U2
298
299
300
Fig. 3 where X, Y. W are binary variables in (0. ;; U1. U2 E R. In this case, the interventional distribution P(y.) is identifiable from P(x, w.y) through the frontdoor adjustment 33 Thm. 3.3.4]. We collect N 10
Figure 3: Frontdoor
302
observational samples V = [x('), ((),, W( J from a randomly
303
304
generated SCM. Fig. 4a shows samples drawn from the posterior distribution of the target probability
(P = 1) | V). The analysis reveals that these samples collapse to the actual interventional
305
308
probability P(Y==0 =0 = 1) = 0.5085, which confirms the identifiability of P(yz) in Fig. 3
307
Experiment 2: Instrumental Variables (IV) This experiment evaluates our bounding strategy in non-identifiable settings, while closed-form solutions for the optimal bounds over target probabilities already exist. Consider first the "IV" diagram in Fig. la where X, Y, Z E {0, 1} and U1, U2 E IR. The non-identifiability of P(y=) from the observational data P(x, y, 2) with the instrument 2 and the unobserved confounding between X and Y has been acknowledged in [ For binary X. Y. 2 derived closed-form, sharp bounds over P(y=) (labelled as opr). We collect N 10s observational samples V (*), (x)) (*), _ j from randomly generated SCM instance. Fig. 4b shows samples drawn from the posterior distribution of (P(Y,=0 = 1) V). As a baseline, we also include the optimal bound opt, and posterior samples obtained from the Gibbs sampler of [M. which utilizes
309
311
314
315
316
the canonical partitions of exogenous domains in [2] (bp). The analysis reveals that our algorithm
317
derives the valid bound over the actual probability P(Y-- = 1) 0.3954; the 100% credible
interval converges to the optimal IV bound ( 0.1468, r 0.6617.
8

---

ci
bp
bp
bp
0
0*
0
opt
opt
nb
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
(a) Frontdoor
(b) IV
(c) PNS
(d) IST
Figure Histogram plots for samples drawn from the posterior distribution over target counterfactual probabilities. For all plots @ using the representation of canonical partitions [2]; 0* is the actual counterfactual probability.
a cí represents our proposed algorithms; bp stands for Gibbs samplers
opl represents the optimal asymptotic bound, if exists. < nb stands for the natural bounds 30
Experiment 3: Probability of Necessity and Sufficiency (PNS) We now study the problem of evaluating the probability of necessity and sufficiency P(Y,=1 1.Y 0) from the observational
320
data P(x, 1) in the "Bow" diagram of Fig. ld where X.Y E (0 and U E R. The sharp bound for P(Y--1 1, Y = 0) from P(r, y) was introduced in 44 (labelled as opt). We collect N = 10a
322
observational samples V = {x(*), y ] from an SCM instance. Fig. shows samples drawn from the posterior distribution of (P(Y==1 Y2= 0) V). As baseline, we also include the optimal bound opt, and posterior samples obtained from the Gibbs sampler which discretizes the exogenous domains using canonical partitions [ (bp). The analysis reveals that our 100% credible
323
324
325
326
327
interval (cf) matches the optimal PNS bound = 0, r = 0.6775, ie.. the proposed strategy achieves
328
the sharp bound over the counterfactual probability P(Y.-1 x= 1, Y = = 0) = 0.1867.
large, randomized, open trial of up 330 to 14 days of antithrombotic therapy after stroke onset [10]. In particular, the treatment X is a pair (i where 0 stands for no aspirin allocation, 1 otherwise: j = 0 stands for no heparin allocation,
Experiment 4: International Stroke Trials (IST) IST
332 1 for median-dosage, and 2 for high-dosage. The primary outcome Y E {O...., 3} is the health
333
of the patient months after the treatment, where 0 stands for death, for being dependent on the family, 2 for the partial recovery, and 3 for the full recovery.
334
To emulate the presence of unobserved confounding, rules ( Z E (o. 9). following a procedure in 49]. Doing so allows us to obtain N x 10 synthetic observational samples V (.x(m), ("), _ that are compatible with the "Double bow" diagram of Fig. Tb We are interested in evaluating the treatment effect ={))=(11.)) for only assigning aspirin X (1, 0). Fig. 4d shows samples drawn from the posterior distribution of (E(Y==(1.0)) V). As baseline, we also include naïve generalization of the discretization
filter the experimental data with selection
336
337
340
procedure (bp) 2 (see Appendix D) and the natural bounds [36 30 estimated at the 95% confidence
341
342
level (nb) 49 Posterior samples of ci and bp are drawn using our proposed collapsed sampler
343
due to the high-dimensional latent space. The analysis reveals that all algorithms achieve bounds 1.3418. Our bounding strategy obtains 100% credible interval L 1.2604, Fei 1.4687, which consistently improves over all the other al agorithms (lip- = 1.1121, Tip = 1.8073, Lub = 1.1195, Vib = 1.6221).
344
that contain the actual, target causal effect E (1)o2=
346
5
Conclusion
348
This paper investigated the problem of partial identification of counterfactual distributions, which concerns with bounding unknown counterfactual probabilities from the combination of the obser- vational data and qualitative assumptions of the tata-generating process, represented in the form of directed acyelic causal diagram. We studied a special family of SCMs with discrete exogenous variables, taking values from a finite set of unobserved states, and showed that it could represent all
3/9
350
351
352
353
counterfactual distributions (over finite observed variables) an arbitrary causal diagram. That is,
this new family of discrete SCMs is counterfactual equivalent to the original family of candidate SCMs compatible with the causal diagram. Using this result, we developed novel algorithm to derive bounds over counterfactual probabilities from finite observations, which are provably tight.
355

---

References
357
358
[1] C. Avin, L. Shpitser, and J. Pearl. Identifiability of Nineteenth International Joint Conference Artificial Intelligence IJCAI-O5, pages 357-363, Edinburgh, UK, 2005. Morgan-Kaufmann Kaufmann Publishers.
effects. In Proceedings of the
360
361
[2] A. Balke and J. Pearl. Counterfactual probabilities: Computational methods, bounds, and applications. In R. L. de Mantaras and D. Poole, editors, Uncertainty in Artificial Intelligence 10, pages 46-54. Morgan Kaufmann, San Mateo, CA, 1994.
363
364
[3] A. Balke and J. Pearl. Counterfactuals and policy analysis in structural models. In P. Besnard and S. Hanks, editors, Uncertainty in Artificial Intelligence 11, pages 11-18. San Francisco, 1995.
365
388
367
[4] A. Balke and J. Pearl. Bounds on treatment effects from studies with imperfect compliance. Journal of the American Statistical Association, 92(439): ([(439):1122111 172- 1176, September 1997.
368
369
[5] E. Bareinboim and J. Pearl. Causal inference by surrogate experiments: z-identifiability. In N. de Freitas and K. Murphy, editors, Proceedings of the Twenty-Eight Conference on Uncertainty in Artificial Intelligence, pages 1 13-- Corvallis, OR, 2012. AUAI Press.
370
371
372
[6] H. Bauer. Probability theory and elements of measure theory. Holt, 1972.
373
[7] H. Bauer. Measure and integration theory, volume 26. Walter de Gruyter, 2011.
374
[8] F. A. Bugni. Bootstrap inference in partially identified models defined by moment inequalities: Coverage of the identified set. Econometrica, 78(2):735-7533 2010.
99] C. Carathéodory. Über den variabilitätshericch der fourier's schen konstanten von positiven har- monischen funktionen. Rendiconti Del Circolo Matematico di Palermo (1884-1940), 32(1):193- 217, 1911.
377
379
[10] A. Carolei et al. The international stroke trial (ist): a randomized trial of aspirin, subcutaneous heparin, both, or neither among 19435 patients with acute ischaemic stroke. The Lancet, 349:1569-1581, 1997.
380
381
382
[11] D. Chickering and J. Pearl. A clinicinn's 's tool for analyzing con-compliance. Computing Science and Statistics, 29(2):424-433 1997.
383
384
[12] R. J. Connor and J. E. Mosimann. Concepts of independence for proportions with generaliza- tion of the dirichlet distribution. Journal of the American Statistical Association, 64(325):994 206, 1969.
385
[13] J. Eckhoff. Helly, radon, and carathéodory type theorems. In Handbook of convex geometry, pages 389-448. Elsevier, 1993.
388
389
[14] R. J. Evans. Graphical methods for inequality constraints in marginalized dags. In 2012 IEEE International Workshop Machine Learning for Signal Processing, pages 1-6. IEEE, 2012.
[15] R. J. Evans et al. Margins of discrete bayesian networks. The Annals of Statistics, 46(6A):2623-
392
2656, 2018.
393
[16] N. Finkelstein and I. Shpitser. Deriving bounds and inequality constraints using logical relations among counterfactuals. In Conference on Uncertainty in Artificial Intelligence, pages 1348- 1357. PMLR, 2020.
394
395
396
[17] C. Frangakis and D. Rubin. Principal stratification in causal inference. Biometrics, 1(58):21-29, 2002.
397
398
[18] D. Galles and Pearl. An axiomatic characterization of causal counterfactuals. Foundation of Science, 3(1):151-182, 1998.
399
[19] J. Halpern. Axiomatizing causal reasoning. In G. Cooper and S. Moral, editors, Uncerlainty Artificial Intelligence, pages 202-210. Morgan Kaufmann, San Francisco, CA, 1998. Also, Journal of Artificial Intelligence Research 12:3, 17-37, 2000.
401
10

---

403
[20] G. W. Imbens and C. F. Manski. Confidence intervals for partially identified parameters. Econometrica, 72(6):1845-1855) 2004.
404
405
[21] G. W. Imbens and D. B. Rubin. Bayesian inference for causal effects randomized experiments with noncompliance. The annals of statistics, pages 305-327, 1997.
406
407
[22] H. Ishwaran and F. James. Gibbs sampling methods for stick breaking priors. Journal of the American Statistical Association, 96(45))1161-173 2001.
[23] N. Kallus and A. Zhou. Confounding-robust policy improvement. In Advances in neural information processing systems, pages 9269-9279, 2018.
410
[24] N. Kallus and A. Zhou. Confounding-rohus, policy evaluation in infinite-horizon reinforcement learning, Advances in Neural Information Processing Systems, 2020.
412
413
[25] N. Kilbertus, M. J. Kusner, and R. Silva. A class of algorithms for general instrumental variable models. In Advances Neural Information Processing Systems, 2020.
414
415
[26] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal optimization, 11(3):796-817, 2001.
417
[27] Lasserre, Moments, positive polynomials and their applications, volume 1. World Scientific, 2009.
[28] M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry. pages 157-270. Springer, 2009.
420
[29] H. R. Lewis. Computers and intractability.. guide to the theory of np-completeness, 1983.
[30] C. Manski. Nonparametric bounds treatment effects. American Economic Review, Papers and Proceedings, 80:319-323, 1990.
423
[31] P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96(2):293-320, 2003.
425
426
[32] J. Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-710, 1995.
427
[33] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York,
428
2000. 2nd edition, 2009.
429
[34] J. Pearl. Principal stratification a goal or a tool? The International Journal of Biostatistics, 7(1, 2011. Article 20, DOI: 10.2202/1557-467..153 Available at:
430
431
[35] A. Richardson, M. G. Hudgens, P. B. Gilbert, and J. P. Fine. Nonparametric bounds and sensitivity analysis of treatment effects. Statistical science; a review journal of the Institute of Mathematical Statisties, 29(4):596, 2014.
433
435
[36] Robins. The analysis of randomized and non-randomized aids treatment trials using new approach to causal inference in longitudinal studies. In L. Sechrest, H. Freeman, and A. Mulley, editors, Health Service Research Methodology: A Focus on AIDS, pages 113-159. NCHSR. U.S. Public Health Service, Washington, D.C., 1989.
436
437
438
[37] J. P. Romano and A. M. Shaikh. Inference for identifiable parameters in partially identified econometric models. Journal of Statistical Planning and Inference, (38(9)2776-222 2008
440
[38] D. Rosset, N. Gisin, and E. Wolfe. Universal bound on the cardinality of local hidden variables networks. Quantum Information & Computation, 18(11-12):910-99 926, 2018
442
443
[39] K. Sen and J. M. Singer. Large sample methods in statistics: an introduction with applications, volume 25. CRC press, 1994.
445
[40] Sethuraman. A constructive definition of dirichlet priors. Statistica sinica, pages 639-650,
1994.

---

447
[41] I. Shpitser and J. Pearl. What counterfactuals can be tested. In Proceedings of the Twenty-Thire Conference on Uncertainty in Artificial Intelligence, pages 352-359. AUAI Press, Vancouver, BC, Canada, 2007. Also, Journal of Machine Learning Research, 9:1941-1979, 2008
448
450
[42] I. Shpitser and E. Sherman. Identification of personalized effects associated with causal pathways. In UAI, 2018.
451
[43] J. Tian. Studies in Causal Reasoning and Learning. PhD thesis, Computer Science Department, University of California, Los Angeles, CA, November 2002.
455
454
[44] J. Tian and J. Pearl, Probabilities of causation: Bounds and identification. Annals of Mathematics and Artificial Intelligence, 28:287-313, 2000.
455
496
[45] J. Tian and J. Pearl. A general identification condition for causal effects. In Proceedings of the Eighteenth National Conference Artificial Intelligence, pages 567-573. AAAI Press/The MIT Press, Menlo Park, CA, 2002.
458
459
[46] D. Todem. J. Fine, and L.. Peng. A global sensitivity test for evaluating statistical hypotheses with nonidentifiable models. Biometrics, 66(2):558-566 5566, 2010.
460
461
[47] S. Vansteelandt, E. Goetghebeur, M. G. Kenward, and G. Molenberghs. Ignorance and uncer- tainty regions as inferential tools in a sensitivity analysis. Statistica Sinica, pages 953-979, 2006.
462
463
[48] H. Waki, S. Kim, M. Kojima, and M. Muramatsu. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM Journal on Optimization, 17(1):2182422, 2006.
465
467
[49] J. Zhang and E. Bareinboim. Bounding causal effects on continuous outcomes, In Proceedings of the 35nd AAAI Conference on Artificial Intelligence, 2021.
468
Checklist
489
470
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
472
473
(b) Did you describe the limitations of your work? [Yes] "Throughout this paper, we assume that endogenous variables V are discrete and finite; while exogenous variables
474
475
U could take any (continuous) value."
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work does not present any foreseeable societal consequence.
477
478
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
479
480
2. If you are including theoretical results...
481
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sec.
482
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices and B
484
3. If you ran experiments...
485
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Appendix C
486
487
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
480
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix "Experiments
432
were performed on computer with 32GB memory."
12

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
485
(a) If your work uses existing assets, did you cite the creators? [Yes] "IST was a large, randomized, open trial of up 14 days of antithrombotic therapy after stroke onset
487
T0C
See also Appendix [
(b) Did you mention the license of the assets? [Yes] See Appendix C The IST dataset is shared under "Open Data Commons Attribution License (ODC-By) v1.0".
499
500
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
502
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
503
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
505
508
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
508
509
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
510
511
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "wmBM-_f_WX", "reviewer": "Reviewer_bRA7", "summary": "The paper presents a methodology to obtain bounds on counterfactual probabilities from unknown SCMs using observational data. The authors consider a setting where the causal structure (DAG) of the data-generating model is known and all the endogenous variables are discrete and finite.\n \n\nIn this setting, the authors show that the set of all SCMs compatible with the known DAG, G, and observational data can be mapped to a special class of SCMs, which they call discrete SCMs. These discrete SCMs have the nice property that they are compatible with DAG G and the observational distribution and all exogenous variables are discrete and finite (with known maximum value). The authors show that there must exist a discrete SCM within this family which agrees with the original (unknown) SCM on all counterfactual probabilities. Using this as the main idea, the authors attempt to bound the counterfactual probabilities by maximising/minimising the counterfactual probabilities over all discrete SCMs in this family.\n \n\nThe paper makes no assumptions about the missing exogenous variables in the SCM model under question. This makes for a very powerful idea which can be used to bound counterfactual queries.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe paper tackles the question of gaining insights into the counterfactual world using the factual observed data with missing confounders. This is a fundamentally challenging question to answer without making additional assumptions. The authors propose a methodology which does not make any assumptions about the missing (exogenous) variables, which makes this methodology quite appealing.\n \n\nSetting:\nHowever, the setting under consideration is very specific: the authors are only considering SCMs with discrete and finite endogenous variables. This rarely occurs in most real world problems. Additionally, the authors work on the assumption that the DAG of the data-generating model is known (including causal links between unobserved variables and observed variables). This may be a reasonable assumption in some settings, but depending on the problem at hand, we may not know the number of missing (exogenous) variables and how they causally affect endogenous variables in great granular detail. In such cases, we may have to resort to a very general DAG, which could potentially come at the cost of the tightness of the bounds on counterfactual probabilities.\n \n\nNotation:\nThe work is generally high quality, however, in my opinion the notation gets very dense at times and could be further simplified. While the authors generally did a good job of defining the notation, it was sometimes difficult to get an intuitive feel of what a concept meant for a model under consideration. For example, it would have been nice to have a visual representation of c-components within a DAG, as it would allow readers to immediately see why they form partitions over both endogenous and exogenous variables. Moreover, the notation U_V is unclear as this is the first time the authors use endogenous variables as subscripts for exogenous variables. I believe either the definition of this notation is missing, or this is a typo.\n \n\nMethod:\nWith regards to the methodology itself, I think the general idea is very nice, and the authors have provided a reasonable theoretical backing to show that it works. However, one of the questions that has not been addressed theoretically in sufficient detail is: how good is the Bayesian approach in finding the family of discrete SCMs that agree with the observational distribution? While the authors show that the problem of finding the bounds can be reduced to a polynomial program in Appendix E, they do not use this approach to find the counterfactual bounds. I think it is very important to include a comparison of credible intervals obtained using Bayesian approach with the bounds obtained by solving these polynomial programs. This would be useful to gauge the reliability of credible intervals against the ground truth.\n \n\nExperiments:\nThe experimental results generally show that the credible intervals obtained contain the ground truth, which is promising, and in the case where the counterfactual probability is identifiable, the credible interval is very tight. However, one thing which is concerning is that the observational data size used in first three experiments is very high (N=10^5) even though the endogenous variables are binary and models are very small (with at most 3 endogenous variables). I would like to see the effect of having smaller datasets on credible intervals. Additionally, the credible intervals in experiment 2 and 3 are very wide (and largely uninformative). In experiment 4, the authors have used age as a confounder, however, having looked at the IST details on https://pubmed.ncbi.nlm.nih.gov/9174558/, it seems that the trial is randomized (\"Half the patients were allocated unfractionated heparin (5000 or 12,500 IU bd [twice daily]), and half were allocated \"avoid heparin\"…\"). This suggests that age is not a confounder. Please clarify this if I am wrong and have overlooked something.\n \n\nOverall, the idea is original and nice, but I believe more needs to be done to justify the use of this methodology in partial identification of counterfactual outcomes.\n \n\nI have given it a rating of 6 because of some of the above questions. I will be happy to reconsider my rating if these questions are addressed. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have stated the assumptions clearly, however I believe more can be done to justify the Bayesian approach for obtaining Credible Intervals (see main review for more details).\n \n\nI do not see any potential negative impacts of their work on the society.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "hEsJe7GOcHy", "reviewer": "Reviewer_BaLP", "summary": "The main result of this paper is to establish that any SCM with discrete endogenous variables can be transformed into a counterfactually equivalent SCM where also the exogenous variables are discrete (finite domains). This result is used to find exact bounds on counterfactual probabilities based on the observational distribution, or, using an MCMC procedure, approximate bounds based on observational data.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main theorem is an impressive result that was apparently very challenging to prove. Knowing that infinite domains need not be considered for exogenous variables is of great theoretical interest, and could open the way to computational approaches for problems that were previously not accessible in such a way.  Two such new approaches are given in the paper, and the empirical results confirm their usefulness. But to me, Theorem 1 is the main contribution of this paper. I did not check the proof, though.\n\nMinor comments:\n\nLine 112: runaway \"f\"\nLine 113-114: If I'm not mistaken, this condition follows from the general definitions of SCMs + the preceding condition + the assumption that endogenous variables have finite domains (which was stated earlier). It does apparently serve the role of introducing the $\\xi$-notation, and maybe to put the finiteness assumption in a clearer place. But as it is, it looks like a fairly complicated condition when the actual message is much simpler.\nLine 144: Why mention $2d=64$ here? Wouldn't $d^2$ be more relevant computationally?\n\nUPDATE: I thank the authors for engaging in the discussion. Based on the other reviews and the discussion, I have revised my score to a 6: while there is a novel contribution in this paper, the result is in fact closer to existing results than I thought at first.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The exact method is computationally prohibitive, possibly to the point of not being practical, but this is not quantified (at least not in the main paper)", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "b_JXccG7kuZ", "reviewer": "Reviewer_R5pL", "summary": "Bounding unknown counterfactual probabilities using observational data and assumptions in a causal graph is the core problem addressed here. The main result is formally presented in theorem 1 which states that all counterfactual distributions in an arbitrary causal diagram could be generated using discrete exogenous variables taking values from a finite domain.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Too many results crammed in together makes the paper extremely hard to understand and follow. Too few examples and complicated notations make it harder. Broadly speaking, there are solutions to two problems that are jointly presented here, the first is identification and the second is estimation.  Also, in this work, proofs are the main contribution. Proofs are in the appendix and the appendix is filled with errors and typos. \n\nAn example for equation 2 where V is a small set V will be helpful. I found one in the appendix but there are issues with it that I detail below. \n\nThere is an ‘f’ at the end of line 112 on page 3.\n\n(3) in definition 3: Please clarify what you mean. Is it the case that an U variable can only occur once in the path?\n\n“SCM lives can be mapped… well-behaved space”: Try to avoid using such vague and ill-defined terms. \n\n“Since G has a single c-component...family of discrete SCMs N”(page 4). It is not immediately clear why U1 and U2 must share the same cardinality. \n\nAppendix A\n\nWhy is there a difference in the definitions of SCM in section 1.1 and definition 5?  h_{u_v} in definition 5 appears to be essentially the same as f_v in section 1.1.  Also in the first line of definition 5, you have M=<V,U,F,P>. ‘F’ is not mentioned anywhere in the rest of the definition. In line 557, the authors revert to the use of ‘f_v’. \n\n“Since Y is not a descendant of X” (line 531): Are you still referring to Fig. 1d? If so, Y is a child of X and hence a descendant.\n\nIn 533, the notation pertaining to ‘h’ changed. I am assuming the ‘h’ referred here is the same as in line 3 of definition 5. What does the superscript denote? Also shouldn’t the subscript denote the exogenous variable that is a parent of X? The notation of h in line 540 makes better sense. This example described from lines 535-545 is crucial. It ought to be corrected and moved to the main paper. \n\n\nThere are similar issues throughout the paper. For the results to be useful to the community this paper needs to be split into two, carefully revised (rewritten with more examples and by including more content from the appendix) and reviewed again. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "2N4kYgaHIGA", "reviewer": "Reviewer_bpXs", "summary": "EDIT:  I thank the authors for their clarifications and corrections to my previous line of thought, and I am prepared to revise my score up to 5 as a result.  I take the point about polynomial vs linear programming, and I can see that Lemma 4 is a non-trivial result.  The authors, however, make no effort to point to Lemma 4 as being the primary source of the novelty in Theorem 1!\n\nOverall, the content of the paper seems too rich for a conference with a page limit like this one, it might be better off submitted to a journal with much more explanation and more examples.\n\n----\n\nThis paper gives a Monte Carlo method for obtaining bounds from any DAG model with hidden variables.   The authors illustrate the algorithm on the front door model, as well as the instrumental variables model; they give several more examples in the supplementary material.  \n\nI think the paper could be improved by explaining more explicitly how the Bayesian algorithm for obtaining samples helps, when presumably one could solve the linear program (6).", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Main Points\n\n1. I do not think that Theorem 1 is quite as much of a contribution as the authors claim.  First, note that Rosset et al. do not explicitly exclude edges within the graph, and I don't think their result is restricted in the way that the authors here imply.  Secondly there is an unpublished manuscript of Sainz and Wolfe that shows it is sufficient to consider graphs where the random vertices (i.e. those inside a given C-component) do not have children (it is referenced in Navascués and Wolfe, 2020).  \n\n    The addition of counterfactually equivalent distributions seems like only a small technical tweak.  I also note that the proof is now essentially identical to that of Rosset.\n\n2.  The MCMC algorithm seems quite good, though it is never tested on a really high dimensional example.  In fact the only example given seems to be the instrumental variables model.  In addition, does the tighter credible interval you obtain simply reflect a more concentrated prior distribution?\n\n3.  I note that there is no comparison with Richardson et al (2011), who do something very similar. \n\n4.  I am curious about the authors' statement that the Balke-Pearl bounds do not apply to Figure 1(b).  Can you elaborate? \n\n### Minor Points\n\n - l14: 'finite number of observational data' $\\rightarrow$ 'finite quantity of observational data'?  Or 'observational data points'?\n\n - l41: 'as the principal stratification'- should this just be 'as principal stratification'?  (I am genuinely not sure.)\n\n - l345: '100% credible interval' - should this be '95%'?\n\n - l354: 'counterfactual equivalent' $\\rightarrow$ 'counterfactually equivalent'\n\n### References\n\nNavascués and Wolfe. The inflation technique completely solves the causal compatibility problem. _Journal of Causal Inference_ 8(1)70-91, 2020.\n\nRichardson, Evans and Robins.  Transparent parameterizations of models for potential outcomes. _Bayesian Statistics 9_, 2011.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I'm not sure what to write here!  The paper seems fine other than the remarks I have made above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A summary from one of the reviews:

"This paper gives a Monte Carlo method for obtaining bounds from any DAG model with hidden variables. The authors illustrate the algorithm on the front door model, as well as the instrumental variables model; they give several more examples in the supplementary material."

The paper received extensive discussion, both with the authors, and among the reviewers.  This discussed alleviated some of the concerns reviewers had, which resulted in overall improved scores.  Nevertheless, concerns about an appropriate way of explicating the novelty of the contribution given constraints of conference proceedings, remained.

Theorem 1, prior work and overall length.  The author's manuscript, as currently written, made it very challenging to see the distinction in the proof strategy between their contribution (via Lemma 4 in the supplement), and related prior work.  While discussions with the authors clarified this to some extent, making this connection clearer would entail nontrivial changes.

In general, while many NeurIPS submissions have extensive appendices, at the conclusion of the discussion reviewers felt this paper in particular relied on results and narrative in the supplement in a way that made reading challenging without expanding the main body of the paper.  Thus, it was felt that the paper in its current was better suited for a journal.

Decision: Reject