Identifying Dynamic Sequential Plans

Jin Tian Department of Computer Science Iowa State University Ames, IA 50011 jtian@cs.iastate.edu

Abstract
We address the problem of identifying dynamic sequential plans in the framework of causal Bayesian networks, and show that the problem is reduced to identifying causal effects, for which there are complete identification algorithms available in the literature.

1

Intro duction

This paper deals with the problem of evaluating the effects of sequential plans from a combination of nonexperimental data and qualitative causal assumptions. The causal assumptions will be represented in the form of an acyclic causal diagram [Spirtes et al., 1993, Heckerman and Shachter, 1995, Lauritzen, 2000, Pearl, 2000] in which arrows represent the potential existence of direct causal relationships between the corresponding variables. The causal diagram may contain unmeasured variables, and our task is to decide whether we can estimate the effects of a sequence of actions from the observed data. We motivate the study by considering a medical treatment problem discussed in [Pearl and Robins, 1995, Dawid and Didelez, 2005]. There are a sequence of medical treatments (X1 , . . . , Xk ) applied to a patient over time. We have observations Zi before and between the treatments. Doctors may prescribe a treatment based on previous treatments and observations. There is a outcome variable Y (say survival) of special interest and we want to estimate the effects of the sequential treatments on Y . In general there may be unobserved confounders that have influence on the observed variables. There are different possible strategies for choosing the treatment action (Xi ). The simplest action involves fixing the value of Xi to a particular value x , called atomic intervention and denoted i

by do(x ) in [Pearl, 2000], e.g. fixing the dosage i of a treatment irrespective of any observations on the patient. A unconditional plan consists of a sequence of pre-defined atomic actions. The problem of identifying unconditional plans is to compute the distribution of Y under atomic interventions on a set X of action variables, denoted by Px (y ) = P (y |do(x)), a quantity known as the causal effects of X on Y . Sufficient graphical criteria for the identifiability of unconditional plans are derived in [Pearl and Robins, 1995]. Recently the general problem of identifying causal effects Px (y ) in a causal diagram containing unobserved variables has been solved and complete algorithms for identification are given in [Tian and Pearl, 2003, Shpitser and Pearl, 2006b, Huang and Valtorta, 2006]. In general we may want to use dynamic treatment strategies in which the values of action variables (Xi ) are determined based on the previously observed variables and previously taken actions. Sufficient graphical criteria for the identifiability of dynamic plans are derived in [Dawid and Didelez, 2005]. However the identifiability problem is far from being solved. In this paper, we show that the problem of identifying dynamic sequential plans can be reduced to the well-studied problem of identifying causal effects and therefore essentially solved the sequential plan identification problem. Although Pearl (2000, Section 4.2) has suggested that dynamic conditional plans may be identified by identifying conditional causal effects of the form Px (y |c), for which complete identification algorithms have been developed [Tian, 2004, Shpitser and Pearl, 2006a], in this paper, we will show that this gives a sufficient condition for identifying dynamic sequential plans but it is not necessary. The rest of the paper is organized as follows. In Section 2, we review the work in [Dawid and Didelez, 2005] and define useful notation. In Section 3, we formulate the sequential plan problem in the framework of causal Bayesian networks. We


show how to reduce the problem of identifying dynamic sequential plans into a problem of identifying causal effects in Section 4, and discuss in Section 5 the problem versus that of identifying unconditional plans and conditional causal effects. Section 6 concludes the paper.

 · Atomic intervention Vi = do(vi ): The strat egy of setting Vi to a fixed value vi , denoted by   do(Vi = vi ) or simply do(vi ) in Pearl (2000), such that   P (vi |pai ; Vi = do(vi )) =  (vi , vi ),   where  (vi , vi ) is one if vi = vi and zero otherwise.

2

Previous Work and Notation

Dawid and Didelez (2005) formulated the problem of identifying dynamic sequential plans in the framework of regime indicators and influence diagrams. An influence diagram (ID) is a DAG over a set V = {V1 , . . . , Vn } of variables that also includes regime indicators as special nodes of their own called decision nodes [Dawid, 2002]. We assume that all variables are discrete. The DAG is assumed to represent conditional independence assertions that each variable is independent of all its non-descendants given its direct parents in the graph.1 These assertions imply that the joint probability function P (v ) = P (v1 , . . . , vn ) factorizes according to the product [Pearl, 1988] i P (vi |pai ) (1) P (v ) = where pai are (values of ) the parents of variable Vi in the graph.2 The question of causal inference is considered as a problem of inference across different regimes, in which we may intervene in certain variables in certain ways and observe the behavior of other variables. Regime indicators are used to represent different types of interventions. Here we will roughly follow the notation used in [Didelez et al., 2006]. The regime indicator for an intervention in a variable Vi is denoted by Vi and can take values in a set of strategies. Under strategy Vi , the conditional probability P (vi |pai ) is changed to P (vi |pai ; Vi ). We will consider the following types of interventions. · Id le regime Vi = : No intervention takes place, therefore P (vi |pai ; Vi = ) = P (vi |pai ). The idle regime is also called the observational regime under which we will assume that observational data has been collected. Therefore P (vi |pai ) can be estimated from data if Vi and P ai are observed.
We use family relationships such as "parents," "children," and "ancestors" to describe the obvious graphical relationships. 2 We use uppercase letters to represent variables or sets of variables, and use corresponding lowercase letters to represent their values (instantiations).
1

· Conditional intervention Vi = do(g (c)): In general, Vi may be made to respond in a specified way to some set C of previously observed variables, denoted by do(Vi = g (c)) in Pearl (2000), such that P (vi |pai ; Vi = do(g (c))) =  (vi , g (c)), where g (.) is a pre-specified deterministic function and the variables in C can not be descendants of Vi . · Random intervention Vi = dC : More generally, we may let Vi take on a random value according to some distribution possibly depending on some set C of previously observed variables such that P (vi |pai ; Vi = dC ) = P  (vi |c), where P  (vi |c) is a pre-specified probability distribution and the variables in C can not be descendants of Vi . In a sequential decision problem, we may intervene, at least in principle, in a set of variables X = {Xi }  V , called control variables or action variables, and are interested in the response of a variable Y , called response variable or outcome variable. Let Z be the rest of observed variables which are often called covariates. The variables are assumed to be ordered in a sequence (L1 , X1 , . . . , LK , XK , Y ) where Li  Z are the set of observed covariates after Xi-1 and before Xi . We de¯ ¯ note Li = (L1 , . . . , Li ) and Xi = (X1 , . . . , Xi ). Given an intervention strategy X = {Xi }, under a condition called simple stability which says that the observed covariates Li and the outcome Y are independent of how action variables are generated once all ¯ ¯ earlier observables (Li-1 , Xi-1 for Li ; X, Z for Y ) are given, Dawid and Didelez (2005) show that the postintervention distribution of Y is identified as x i P (y ; X ) = P (y |x, z ) P (li |¯i-1 , xi-1 ) l ¯
,z

i

P (xi |xi-1 , ¯i ; Xi ), ¯ l

(2)

where P (xi |xi-1 , ¯i ; Xi ) are determined by the chosen ¯ l regime and the other quantities can be estimated from


observational data. Eq. (2) is known as the G-formula, and has been obtained in [Robins, 1986, Robins, 1987] in the framework of potential response models. When there are unobserved confounders, the simple stability may not hold. Dawid and Didelez (2005) makes extended stability assumption which essentially is (simple) stability with respect to the extended domain that includes unobserved U variables ignoring the distinction between Z and U . The G-formula (2) no longer holds unless we include unobserved U variables, but then the conditional probabilities involving U variables can no longer be estimated from the data. Sufficient graphical criteria for identifying P (y ; X ) are derived. The criteria were obtained by identifying graphical conditions under which the simple stability can be regained such that the G-formula can be used, and by extending the work in [Pearl and Robins, 1995] to dynamic plans.

interested in the response of a set of outcome variables Y . Assume that all the variables V are observed and let the rest of covariate variables be Z = {Zi } = V \ (X  Y ). Given an intervention strategy X = {Xi }, by modularity assumption, we can predict the effects of X as P (v ; X ) i i i P (xi |paxi ; Xi ), P (zi |pazi ) P (yi |payi ) = (3) where, by modularity assumption, those conditional probabilities corresponding to unmanipulated variables remain unaltered. We note that Dawid and Didelez's (2005) simple stability assumption leads to Eq. (3) in the framework of CBNs. We see that, given a CBN, whenever all variables in V are observed, the consequence of an intervention strategy on the outcome variables Y is computed as i xi P (zi |pazi ) P (yi |payi ) P (y ;  X ) =
,z

3

Problem Formulation

In this paper, we will formulate the sequential plan problem in the framework of causal Bayesian networks. A causal Bayesian network (CBN) consists of a DAG G over a set V = {V1 , . . . , Vn } of variables, called a causal diagram. The interpretation of such a graph has two components, probabilistic and causal. The probabilistic interpretation views G as representing conditional independence assertions such that the joint probability function P (v ) = P (v1 , . . . , vn ) factorizes according to Eq. (1). The causal interpretation views the directed edges in G as representing causal influences between the corresponding variables. In this interpretation, the factorization of (1) still holds, but the factors are further assumed to represent autonomous data-generation processes, that is, each conditional probability P (vi |pai ) represents a stochastic process by which the values of Vi are chosen in response to the values pai (previously chosen for Vi 's parents), and the stochastic variation of this assignment is assumed independent of the variations in all other assignments. Moreover, each assignment process remains invariant to possible changes in the assignment processes that govern other variables in the system. This modularity assumption enables us to predict the effects of interventions, whenever interventions are described as specific modifications of some factors in the product of (1). We typically assume that every variable Vi can potentially be manipulated by external intervention. So we might think of a CBN as an ID such that each node is (implicitly) pointed to by a corresponding regime/intervention indicator. In a sequential decision problem, we may intervene in a set of action variables X = {Xi }  V , and are

i

P (xi |paxi ; Xi ),

(4)

where P (xi |paxi ; Xi ) are determined by the chosen regime and the other quantities can be estimated from observational data. We note that the G-formula (2) can be reduced to Eq. (4) by using the conditional independence relationships implied by the CBN that each variable is independent of all its non-descendants given its parents. In general we may be concerned with confounding effects due to unobserved influential variables. In the presence of unobserved confounders, the distribution over observed variables can no longer factorize according to (1). Letting V = Y  Z  X and U = {U1 , . . . , Un } stand for the sets of observed and unobserved variables, respectively, the observed probability distribution, P (v ), becomes a mixture of products: u{ { P (v ) = P (vi |pavi ) P (ui |paui ).
i|Vi V } i|Ui U }

(5) We still make modularity assumption in the CBN with unobserved variables, and the effects of an intervention strategy X on the outcome variables Y can be expressed as x i i P (y ;  X ) = P (yi |payi ) P (zi |pazi )
,z ,u

i

P (xi |paxi ; Xi )

i

P (ui |paui ). (6)


We note that Dawid and Didelez's (2005) extended stability assumption leads to Eq. (6) in the framework of CBNs. In (6), the quantities P (yi |payi ) and P (zi |pazi ) (and P (ui |paui )) may involve elements of U and may not be estimable from data. Then the question of identifiability arises, i.e., whether it is possible to express P (y ; X ) as a function of the observed distribution P (v ). Definition 1 [Plan Identifiability] A sequential plan is said to be identifiable if P (y ; X ) is uniquely computable from the observed distribution P (v ).

from which we obtain that Px (y , z ) is identified as Px (y , z ) = = { p(x, y , z ) i P (xi |paxi ) P (vi |vi ), ¯ (10) (11)

i|Vi Y Z }

where we have used the chain rule assuming an order of V variables that is consistent with the DAG and vi ¯ denotes the V variables ordered ahead of Vi . Hence the sequential plan is identified as { xi P (vi |vi ), ¯ P (xi |paxi ; Xi ) P (y ; X ) =
,z i|Vi Y Z }

4

Identification of Sequential Plans
which is essentially the G-formula (2). I

(12)

First we make the following assumption about the type of interventions we will consider. Assumption 1 P (xi |paxi ; Xi ) does not depend on the unobserved variable. That is, for conditional intervention Xi = do(g (c)) or random intervention Xi = dC , we require C  X  Z . This assumption corresponds to Condition 6.6 or 7.2 in [Dawid and Didelez, 2005]. Under Assumption 1, Eq. (6) becomes P (y ; X ) = x
,z

n general Px (y , z ) being identifiable is not a necessary condition for P (y ; X ) being identifiable. Eq. (7) may be simplified in tz at a factor P (zi |pazi ) may be h summed out (using P (zi |pazi ) = 1) if Zi does not i appear in any other factors (graphically, if Zi does not have any children). We can derive stronger identification criterion by summing out as many factors as possible from Eq. (7). Before presenting our result, we first introduce some notation. Following [Tian and Pearl, 2003], for any observed set S  V of variables, we define the quantity Q[S ] to denote the post-intervention distribution of S under atomic interventions to all other variables: Q[S ](v ) = Pv\s (s) u{ =
i|Vi S }

i i i
,z

P (xi |paxi ; Xi ) P (zi |pazi ) i

u

i

P (yi |payi ) (7) (8)

P (ui |paui )

=

x

P (xi |paxi ; Xi )Px (y , z )

P (vi |pavi )

{
i|Ui U }

P (ui |paui ). (13)

Obviously a sufficient condition for P (y ; X ) being identifiable is that the causal effect Px (y , z ) is identifiable. In particular, a simple sufficient condition for Px (y , z ) being identifiable is if all the parents of action (X ) variables are observables, which is Condition 6.3 in [Dawid and Didelez, 2005]. Prop osition 1 If al l the parents of action (X ) variables are observables, then P (y ; X ) is identifiable [Dawid and Didelez, 2005]. Proof: If all the parents of action (X ) variables are observables, then P (xi |paxi ) contains no unobserved (U ) variables, and Eq. (5) can be written as P (v ) = i P (xi |paxi )Px (y , z ), (9)

For convenience, we will often write Q[S ](v ) as Q[S ]. Eq. (7) can be written as P (y ;  X ) = x
,z

i

P (xi |paxi ; Xi )Q[Y  Z ].

(14)

Let GX denote the manipulated graph under the intervention strategy X , which can be constructed from the original causal graph G as follows: · For an atomic intervention Xi = do(xi ), cut off all the arrows entering Xi ; · For a conditional intervention Xi = do(gi (ci )) or a random intervention Xi = dCi , cut off all the arrows entering Xi and then add an arrow entering Xi from each variable in Ci .


Based on Eq. (14), we obtain the following sufficient criterion for identifying P (y ; X ). Theorem 1 Let ZD be the set of variables in Z that are ancestors of Y in GX . P (y ; X ) is identifiable if the causal effects Q[Y  ZD ] = Px,z\zD (y , zD ) is identifiable. Proof: Let XD be the set of variables in X that are ancestors of Y in GX . Then all the non-ancestors of Y can be summed out from Eq. (14) leading to x { P (xi |paxi ; Xi )Q[Y  ZD ] P (y ; X ) =
D ,zD

F
igure 1: An example causal graph

i|Xi XD }

=

x
D ,zD

{
i|Xi XD }

(15) P (xi |paxi ; Xi )Px,z\zD (y , zD ). (16)

We therefore have reduced the problem of identifying dynamic sequential plans P (y ; X ) into that of identifying causal effects Q[Y  ZD ] while the latter problem has been solved and complete algorithms are given in [Tian and Pearl, 2003, Shpitser and Pearl, 2006b, Huang and Valtorta, 2006]. We demonstrate the application of Theorem 1 and the identification process with an example. Consider the problem of identifying P (y ; X1 , X2 ) in Figure 1, which was studied in [Dawid and Didelez, 2005] and is troubling to the methods presented therein. Theorem 1 calls for identifying Q[{Y , Z }] which can be shown to be identifiable. We are given the observational distribution P (v ) = P (y |x1 , x2 , z )P (x2 )Q[{Z, X1 }], where Q[{Z, X1 }] = u P (z |x2 , u)P (x1 |u)P (u). (20) (19)

W e conjecture that the condition in Theorem 1 is also necessary. It might appear that Eq. (15) can be further simplified as follows. Let ZXD be{ the set of Z variables that appear in the term i|Xi XD } P (xi |paxi ; Xi ) (the set of conditioning va{iables in the strategy XD ). r Then the term P (xi |paxi ; Xi ) is a function of XD and i|Xi XD } ZXD . Eq. (15) becomes P (y ; X ) x { =
D ,zX D

P (xi |paxi ; Xi ) z
D \zX D

z
D \zX D

Q[Y  ZD ] (17)

i|Xi XD }

We want to compute P (y ; X1 , X2 ) x = P (x1 ; X1 )P (x2 ; X2 )P (y |x1 , x2 , z )Q[{Z }],
1 ,x2 ,z



x
D ,zX D

g (xD , zXD )

Q[Y  ZD ]

(18)

(21) which calls for computing Q[{Z }]. From Eq. (20), it is clear that x Q[{Z }] = (22) Q[{Z, X1 }].
1

From z

Eq. (18), P (y ; X ) is identifiable if Q[Y  ZD ] is identifiable, and intuD \z
XD

itively, the condition appears to be necessary too, since the term g (xD , zXD ) is specified externally and no more factors can be summed out (as far as the function g (.) is not independent of any variables in zXD ). A strict proof of this necessity is still under study. On the other hand, due to the fact that none of the factors corresponding to the variables in ZD \ ZXD u can be sz mmed out from Q[Y  ZD ], it has been shown that Q[Y  ZD ] can be identified only via D \z
XD

From Eq. (19), we obtain Q[{Z, X1 }] = P (z , x1 |x2 ) (23)

Therefore Q[{Z }] is identified and we finally obtain P (y ;  X 1 ,  X 2 ) x = P (x1 ; X1 )P (x2 ; X2 )P (y |x1 , x2 , z )P (z |x2 ).
1 ,x2 ,z

identifying Q[Y  ZD ] and it is a if and only if condition (Lemma 11 in [Huang and Valtorta, 2006]). So from the point of view of identifying P (y ; X ) the reduction from Eq. (15) to Eq. (17) is not necessary.

(24)


(

we want to identify P (y ; X1 , X2 ) x P (x1 ; X1 )P (x2 |x1 , z ; X2 )Q[{Y , Z }] (28) =
1 ,x2 ,z

a) G

(b) GX

From Eq. (28), we see that if P (x2 |x1 , z ; X2 ) depends on Z , then the identifiability of P (y ; X1 , X2 ) depends on the identifiability of Q[{Y , Z }]. We therefore conclude that P (y ; X1 , X2 ) is not identifiable. On the other hand, if P (x2 |x1 , z ; X2 ) is independent of Z , say P (x2 |x1 , z ; X2 ) = P  (x2 |x1 ) (or X2 = do(x2 )), then the set ZD of variables in Z that are ancestors of Y in GX becomes empty (see Figure 2(b)), and, by Theorem 1, the identifiability of P (y ; X1 , X2 ) depends on the identifiability of Q[{Y }]. In fact, in this case, Eq. (28) becomes P (y ; X1 , X2 = dX1 ) z x Q[{Y , Z }] P (x1 ; X1 )P  (x2 |x1 ) = = x
1 ,x2

Figure 2: An example causal graph

5
5.1

Discussion
Unconditional plans are easier

In general identifying dynamic plans is more difficult than identifying unconditional plans that involve only atomic interventions. Let an intervention strategy X consist of all atomic interventions. Then the manipulated graph GX is a subgraph of GX . Let ZD be the set of variables in Z that are ancestors of Y in GX . Then ZD is a subset of ZD . We have P (y ;  ) = Px (y ) =
X

P (x1 ; X1 )P  (x2 |x1 )Q[{Y }]
1 ,x2

(29)

z
D

From Eq. (27) we obtain Q[Y  Z ].
D

(25)

Q[{X1 , Z, Y }] = P (v )/P (x2 |x1 , z ) = P (y |x1 , x2 , z )P (x1 , z ). It can be shown (or confirmed) that z Q[{X1 , Z, Y }] y Q[{Y }] = ,z Q[{X1 , Z, Y }] z = P (y |x1 , x2 , z )P (z |x1 ). We obtain

(30)

Therefore identifying Px (y ) calls for identifying Q[Y  ZD ] while P (y ; X ) calls for identifying Q[Y  ZD ]. Now we have Q[Y  ZD ] = z
D

Q[Y  ZD ]
\zD

(26)

(31)

The factors of the variables in ZD \ ZD are summed out from Q[Y  ZD ] since the variables in ZD \ ZD can be ancestors of Y only through Xi 's. In general, whenever Q[Y ZD ] (and therefore P (y ; X )) is identifiable, then Px (y ) is identifiable. However, it is possible that Px (y ) is identifiable but Q[Y  ZD ] (and therefore P (y ; X )) is not. We demonstrate this point with an example. Consider the problem of identifying P (y ; X1 , X2 ) in Figure 2(a), which was studied in [Pearl and Robins, 1995]. If P (x2 |x1 , z ; X2 ) depends on Z , say X2 = do(g (x1 , z )), then ZD = {Z }, and by Theorem 1, to identify P (y ; X1 , X2 ) we need to identify Q[{Y , Z }], which can be shown to be not identifiable (by theorems in [Huang and Valtorta, 2006]). More specifically, given the observational distribution P (v ) = P (x2 |x1 , z )Q[{X1 , Z, Y }], (27)

P (y ;  X 1 ,  X 2 = d X 1 ) x z = P (x1 ; X1 )P  (x2 |x1 ) P (y |x1 , x2 , z )P (z |x1 ).
1 ,x2

(32) And in particular, the unconditional plan is identified as z Px1 ,x2 (y ) = Q[{Y }] = P (y |x1 , x2 , z )P (z |x1 ). (33) 5.2 Identification via conditional causal effects?

Pearl (2000) has suggested that dynamic sequential plans involving conditional and random interventions


may be identified by identifying conditional causal effects of the form Px (y |z ). For interventions on a single variable X , we can show [Pearl, 2000, Section 4.2] that z P (y ; X = do(g (z ))) = Px (y |z )|x=g(z) P (z ), and P (y ; X = dZ ) =

(
a) G

x
,z

Px (y |z )P  (x|z )P (z ).

(
b) GX Figure 3: An example causal graph

Therefore it appears that P (y ; X ) is identifiable if and only if Px (y |z ) is identifiable. This idea was generalized to dynamic sequential plans. Consider a plan involving a sequence of conditional interventions Xi = do(gi (Ci )). Let ZX = Z  (i Ci ) be the set of conditioning variables in the strategy X . Pearl (2006) shows that z P (y ; X ) = (34) Pxz (y |zX )Pxz (zX ),
X

where xz are the values attained by X when the conditioning set ZX takes the values zX . Pearl then suggests that sequential conditional plans can be identified by identifying conditional causal effects Px (y |z ) and Px (z ). This motivated the study of the identifiability of conditional causal effects and complete algorithms have been developed in [Tian, 2004, Shpitser and Pearl, 2006a]. Next we show that although the identification of Pxz (y |zX ) and Pxz (zX ) is sufficient for identifying P (y ; X ), it is nonetheless not necessary. Rewrite Eq. (34) in the following x  (xi , gi (Ci ))Px (y , zX ) P (y ; X ) = (35) = x
,z  X

X = {X1 = do(g1 (Z1 )), X2 = do(g2 (Z2 )), X3 = do(g3 (Z3 ))} in Figure 3(a). The graph GX is shown in Figure 3(b). We have ZD = {Z1 , Z3 }, and Theorem 1 calls for identifying Q[{Y , Z1 , Z3 }] which can be shown to be identifiable. On the other hand, Px1 x2 x3 (y , z1 , z2 , z3 ) = Q[{Y , Z1 , Z2 , Z3 }] is not identifiable. More specifically, given the observational distribution P (v ) =P (y |x1 , x3 , z3 )P (x3 |x2 , z3 )P (z1 )Q[{X2 , Z3 }] Q[{X1 , Z2 }], we want to identify P (y ;  X ) x i  (xi , gi (zi ))P (y |x1 , x3 , z3 )P (z1 ) =
i ,zi

(37)

=

 (xi , gi (Ci ))
,z  X

z
\zX

x

Q[{Z3 }]Q[{Z2 }]
1 ,x3 ,z1 ,z3

(38)

 (x1 , g1 (z1 )) (x3 , g3 (z3 ))P (y |x1 , x3 , z3 ) P (z1 )Q[{Z3 }], (39)

Q[Y , Z ]

(36)

Comparing the reduction from Eq. (14) into (17) with the reduction from (14) to (36), we obtain that if XD = X then (36) is equivalent to (17), otherwise Eq. (36) may be further reduced in that more factors could be summed out from Q[Y , Z ]. We obtain the following conclusion · If all the variables in X are ancestors of Y in GX , then the sequential plan P (y ; X ) can be identified by identifying the causal effects Px (y , zX ), otherwise it is possible that P (y ; X ) is identifiable even if Px (y , zX ) is not. We demonstrate this point with an example. Consider the problem of identifying P (y ; X ) where

where Q[{Z3 }] can be identified as u P (z3 |u2 )P (u2 ) = P (z3 ). Q[{Z3 }] =
2

(40)

We obtain P (y ;  X ) = z
1 ,z 3

P (y |g1 (z1 ), g3 (z3 ), z3 )P (z1 )P (z3 ). (41)

On the other hand, P x 1 x 2 x 3 (y , z 1 , z 2 , z 3 ) = P (y |x1 , x3 , z3 )P (z1 )Q[{Z3 }]Q[{Z2 }] = P (y |x1 , x3 , z3 )P (z1 )P (z3 )Q[{Z2 }]

(42)


is not identifiable since Q[{Z2 }] is not identifiable. In fact the conditional causal effect Px1 x2 x3 (y |z1 , z2 , z3 ) = P (y |x1 , x3 , z3 ) is identifiable but the causal effect Px1 x2 x3 (z1 , z2 , z3 ) = P (z1 )P (z3 )Q[{Z2 }] is not identifiable. (44) (43)

[Pearl and Robins, 1995] J. Pearl and J.M. Robins. Probabilistic evaluation of sequential plans from causal models with hidden variables. In P. Besnard and S. Hanks, editors, Uncertainty in Artificial Intel ligence 11, pages 444­453. Morgan Kaufmann, San Francisco, 1995. [Pearl, 1988] J. Pearl. Probabilistic Reasoning in Intel ligent Systems. Morgan Kaufmann, San Mateo, CA, 1988. [Pearl, 2000] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, NY, 2000. Pearl. Comment on [Pearl, 2006] J. conditional plans. 2006. identifying http://www.mii.ucla.edu/causality/?p=36#comments. [Robins, 1986] J.M. Robins. A new approach to causal inference in mortality studies with a sustained exposure period ­ applications to control of the healthy workers survivor effect. Mathematical Modeling, 7:1393­1512, 1986. [Robins, 1987] J.M. Robins. A graphical approach to the identification and estimation of causal parameters in mortality studies with sustained exposure periods. Journal of Chronic Diseases, 40(Suppl 2):139S­161S, 1987. [Shpitser and Pearl, 2006a] I. Shpitser and J. Pearl. Identification of conditional interventional distributions. In R. Dechter and T.S. Richardson, editors, Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intel ligence, pages 437­ 444. AUAI Press, July 2006. [Shpitser and Pearl, 2006b] I. Shpitser and J. Pearl. Identification of joint interventional distributions in recursive semi-markovian causal models. In Proceedings of the Twenty-First National Conference on Artificial Intel ligence, pages 1219­1226, Menlo Park, CA, July 2006. AAAI Press. [Spirtes et al., 1993] P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. Springer-Verlag, New York, 1993. [Tian and Pearl, 2003] J. Tian and J. Pearl. On the identification of causal effects. Technical Report R-290-L, Department of Computer Science, University of California, Los Angeles, 2003. http://www.cs.iastate.edu/ jtian/r290-L.pdf. [Tian, 2004] J. Tian. Identifying conditional causal effects. In Proceedings of the Conference on Uncertainty in Artificial Intel ligence (UAI), 2004.

6

Conclusion

We present a method for identifying dynamic sequential plans. A closed-form expression for the probability of the outcome variables under a dynamic plan can be obtained in terms of the observed distribution, by using the algorithms for identifying causal effects available in the literature. Acknowledgments This research was partly supported by NSF grant IIS0347846.

References
[Dawid and Didelez, 2005] A.P. Dawid and V. Didelez. Identifying the consequences of dynamic treatment strategies. Technical report, Department of Statistical Science, University College London, UK, 2005. [Dawid, 2002] A.P. Dawid. Influence diagrams for causal modelling and inference. International Statistical Review, 70(2), 2002. [Didelez et al., 2006] V. Didelez, A.P. Dawid, and S. Geneletti. Direct and indirect effects of sequential treatments. In Proceedings of the 22nd Annual Conference on Uncertainty in Artifical Intel ligence, pages 138­146, 2006. [Heckerman and Shachter, 1995] D. Heckerman and R. Shachter. Decision-theoretic foundations for causal reasoning. Journal of Artificial Intel ligence Research, 3:405­430, 1995. [Huang and Valtorta, 2006] Y. Huang and M. Valtorta. Identifiability in causal bayesian networks: A sound and complete algorithm. In Proceedings of the Twenty-First National Conference on Artificial Intel ligence, pages 1149­1154, Menlo Park, CA, July 2006. AAAI Press. [Lauritzen, 2000] S. Lauritzen. Graphical models for causal inference. In O.E. Barndorff-Nielsen, D. Cox, and C. Kluppelberg, editors, Complex Stochastic Systems, chapter 2, pages 67­112. Chapman and Hall/CRC Press, London/Boca Raton, 2000.