Counterfactual Realizability
Authors: Arvind Raghavan
Elias Bareinboim
Venue: ICLR 2025 Spotlight (2025)
Keywords: causal inference
experiment design
causal reinforcement learning
counterfactual reasoning
Primary area: causal reasoning
TL;DR: A complete algorithm for which counterfactual (Layer 3) distributions can be experimentally realized; and its implications for optimal decision-making

Abstract: It is commonly believed that, in a real-world environment, samples can only be drawn from observational and interventional distributions, corresponding to Layers 1 and 2 of the *Pearl Causal Hierarchy*. Layer 3, representing counterfactual distributions, is believed to be inaccessible by definition. However, Bareinboim, Forney, and Pearl (2015) introduced a procedure that allows an agent to sample directly from a counterfactual distribution, leaving open the question of what other counterfactual quantities can be estimated directly via physical experimentation. We resolve this by introducing a formal definition of realizability, the ability to draw samples from a distribution, and then developing a complete algorithm to determine whether an arbitrary counterfactual distribution is realizable given fundamental physical constraints, such as the inability to go back in time and subject the same unit to a different experimental condition. We illustrate the implications of this new framework for counterfactual data collection using motivating examples from causal fairness and causal reinforcement learning. While the baseline approach in these motivating settings typically follows an interventional or observational strategy, we show that a counterfactual strategy provably dominates both.

Published as a conference paper at ICLR 2025
COUNTERFACTUAL REALIZABILITY
Arvind Raghavan and Elias Bareinboim
Causal Artificial Intelligence Lab Columbia University far, ebjecs. co 1 lumbia edu
ABSTRACT
It is commonly believed that, in real-world environment, samples can only be drawn from observational and interventional distributions, corresponding to Layers and of the Pearl Causal Hiierarcy. Layer 3, representing counterfactual distributions, is believed to be inaccessible by definition. However, Bareinboim, Forney, and Pearl (2015) introduced procedure that allows an agent to sample directly from a counterfactual distribution, leaving open the question of what other counterfactual quantities can be estimated directly via physical experimentation. We resolve this by introducing formal definition of realizability, the ability to draw samples from distribution, and then developing a complete algorithm to determine whether an arbitrary counterfactual distribution is realizable given fundamental physical constraints, such as the inability to go back in time and subject the same unit to different experimental condition. We illustrate the implications of this new framework for counterfactual data collection using motivating examples from causal fairness and causal reinforcement learning. While the baseline approach in these motivating settings typically follows an interventional or observational strategy, we show that a counterfactual strategy provably dominates both.
INTRODUCTION
The Pearl Causal Hierarchy, or PCH, is an important recent milestone in our understanding of causality (Pearl & Mackenzie 2018 Bareinboim al.J 2022). The three layers of the PCH represent the distinct regimes of seeing, doing, and imagining, with regard to environment. Consider an environment involving a decision variable X and an outcome Y. Layer 1 (L1) represents observational distributions, such as P(Y | x). Layer 2 (L2) represents interventional distributions, such as P(Y; do(z)), using the do() operator. Layer 3 (Ca) represents counterfactual distributions dealing with conflicting realities, such as P(Y.: x' y'): the distribution of Y had X been fixed as given that X, Y were in fact naturally observed to be x' ,'yy". Higher layers subsume lower ones, but underdetermined by them (Ibeling & Icard 2020; Bareinboim et al. (022)).
Reasoning about C3-quantities plays a vital role in personalized decision-making (Mueller & Pearl 2023), analysing a causal effect into direct and indirect pathways (Pearl 2001 Rubin 20044, and constructing explanations for decisions, among other topics, in applications such as healthcare (Mueller & Pearl (2024), economics (Li & Pearl 2019), epidemiology (Robins & Greenland 1992)
etc. Suppose an economist were interested in estimating P 2²), an important Ca-quantity
called the effect of the treatment on the treated, or ETT (Heckman & Robb Jr. 1985 1986). One
approach to computing such quantities is through identification (Pearl |2000] $3.2.4): leveraging causal knowledge about the environment, typically a causal graph or parametric assumptions. to
infer the ligher-layer quantity using lower-layer data. This approach fails when the quantity is
nonidentifiable, e.g. ETT in the general setting (Shpitser & Pearl 2009) Correa et al. 2021).
However, another approach uses physical experimentation to attempt to directly draw samples from the relevant distribution, P(Y,,Xi in the case of ETT, and then uses statistical methods to estimate P(Y, = y, X x²). This approach is only possible if there is some sequence of physical actions by which an agent can measure these random variables simultaneously for a single unit. It is generally believed to be feasible to draw samples only from L1- and L2 Ey-distributions, the latter by interventions like randomized controlled trials (RCT), à la Fisher (Fisher) 1935). and the former by simply observing the natural behaviour of the system. Li-iitributtions like P(Y,, X) are deemed

---

Published as a conference paper at ICLR 2025
non-realizable in general, the potential response Y, and natural decision X belong to different "worlds". Once unit naturally adopts decision X = x', Yg cannot be evaluated in the do(z) regime for the same unit However, Bareinboim, Forney & Pearl have shown it is feasible to draw samples from the ETT distribution P(Y... X) through a counterfactual randomization procedure (Bareinboim) et al. 2015, Forney al.] 2017). This leaves open the possibility that other La-distributions, say perhaps P(Y x: X, ). are also realizable through clever experimental setups, allowing one to estimate important quantities like the probability of sufficiency, P(ye y ,,2) (Pearl 1999).
This brings us to the central question motivating this work: from which Cx-distributions is it possible to draw samples given fundamental physical constraints like the inability to travel back in time and subject the original unit to a different experimental condition? We resolve this open question with a rigorous formal treatment of the realizability of an Lz-distribution (Def. 3.4).
Our main contributions in this work are as follows:
In Sec. 2 we introduce a physical procedure called counterfactual randomization (Def. 2.3 by which an agent can gather counterfactual data, subsuming previous similar notions.
In Sec. we develop the CTF-REALIZE algorithm (Algo. D to determine whether an L3- distribution is physically realizable. We prove the algorithm is complete (Thm. (35), and derive
important corollaries characterizing realizable distributions (Cors. 3.7 3.8 For instance, we show that our main result generalizes an influential notion in the causal inference literature, known as the fundamental problem of causal inference (Holland) 1986).
In Sec. 4we we discuss important practical implications of counterfactual realizability. The tradi- tional route of computing La-quantities through identification often fails. Our work suggests opportunities for novel experiment-design ideas to directly estimate these quantities, as illustrated More concretely,
through Examples 1 3
In Sec. we describe an application in causal fairness, where the naive approach of constraining classifier using an interventional (C2) fairness metric fails to prevent disparities in outcomes across groups, but where a counterfactual (C3) approach works.
In Sec. 4.2 we show how counterfactual randomization can be used to improve RL algo- rithms. The baseline approach in multi-arm bandit setting is to use allocation procedures (e.g.. UCB, EXP3, Thompson Sampling) to discover which arm x optimizes the expected outcome Y do(x)). which is interventional (L2) strategy (Sutton & Barto 1998 Latti- more & Szepesvári 2020). It turns out there are provably superior strategies (w.r. expected outcome) based on directly optimizing counterfactual (C3) objectives, as we demonstrate in We prove optimality of our proposed strategy in a bandit setting with a generic causal template (Thm. 4.2, Cor. 4.3 in Raghavan & Bareinboim 2025
Example 3
Proofs and experiment details are in the full technical report (Raghavan & Bareinboim 2025)
Preliminaries. We denote variables by capital letters, X, and values by small letters, x. Bold letters. X, are sets of variables and x sets of values. P(x) is shorthand for P(X = x). 1[] is the indicator function. We use Structural Causal Models (SCM) to describe the generative process for a system of interest (Bareinboim et al. 2022, Def. 1)(Perl 20000. An SCM M is a tuple (V, U,F, P(u)). V is the set of observable variables. U is the set of unobservable variables exogenous to the system, distributed according to PM((), F {fv] is set of functions s.t. each fv causally generates the value of V E V as V +- Uy, Pay). where Uv C U and Pay E V \ V. Each M induces a causal diagram G (Bareinboim et al. 2022 Def. 13), which is graph containing a vertex for each V E V, a directed edge from each node in Pay to V. and a bidirected edge between V, V.V' if Uv, Uy are not independent. Given a graph G, 9xw is the result of removing edges coming into variables in X, and edges coming out of W. We use standard terminology like parents, descendants of a node (see App. A). Our treatment is limited to recursive SCMs, which implies acyclic diagrams, with finite discrete domains over V. The do(x) operator indexes a sub-model Mx where the functions generating variables X are replaced with constant values x. A variable Y & X evaluated in this regime is called a potential response, denoted
E.g.. "The problem with counterfactuals like [P(Y. | x') is [that] ... we simply cannot perform an experiment where the same person is both given and not given treatment." (Shpitser & Pearl 2007) Also, "By definition, one can never observe [counterfactuals), nor assess empirically the validity of any modeling assumptions made about them..." (Dawid 2000
2

---

Published as a conference paper at ICLR 2025
Xx (W. w) denotes an arbitrary counterfactual event, e.g. = A = x"). The probability of such an event is given by the La-valuation (Bareinboim et al. 2022 Def. 7):
pM (W. w) En (Iwiew. L[Wa(u) w| pu()), with w taken from w.
2 DATA-COLLECTION PROCEDURES
In this section, we define a procedure, counterfactual randomization, that extends the scope of traditional Fisherian experimentation (discussed below). Consider a system of interest modeled by unknown SCM M. Interventions and counterfactual events are typically defined in terms of symbolic operations on M. To conceptually separate this from the physical constraints experienced by an agent (natural or artificial), we define the following physical actions that an agent can perform in the system. These are simply the physical counterparts to symbolic procedures.
We call each discrete episode of the system's 's behaviour a wnit. Examples of units are patients in clinical trial, neighbourhoods in a social science experiment, rounds played on a slot machine etc. We index units w.l.o.g. by = 2, 3... which constitute a target population in the system.
Definition 2.1 (Physical actions). (1) SELECT(); randomly choosing, without replacement, a unit i from the target population, observe in the system; (2) READ(V)()) measuring the realized feature ( of unit produced by a causal mechanism fv F operating on (3) RAND(X)()) erasing and replacing i's natural mechanism fx for a decision variable X with an enforced value drawn from a randomizing device having support over (X).
READ(V) = v and (A))(X)()) = x are also overloaded to refer to the values read and enforced, respectively. RAND(X)() is the standard Fisherian randomization of a decision variable X, corre- sponding to the symbolic procedure of stochastic intervention on X (Correa & Bareinboim 2020 As RAND(X) (+) erases the unit i's natural decision, (EAD(X)() will yield the value randomly assigned to unit i. The discovery of this procedure marked an important achievement in the history of
science and experiment-desige (Fisher 1925 1935). Since the use of randomizing device eliminates
by design any confounding between the assigned decision and the unit's latent attributes U(9, it
allows researchers to estimate causal effects.
It is evident that the actions in Def. 2. are sufficient for agent to physically draw samples from any L or C2-distribution, as discussed in App. C.I Until recently, it was generally presumed these were the only physical actions possible on units in a system. However, we discuss some important extensions of experimental capabilities next.
X
Y
Y
Figure (Top) Causal dia- gram with decision variable X; (Bottom) Procedure of randomizing the actual de- cision without erasing the unit's natural decision.
Counterfactual data-collection procedures. In an early work from the causal reinforcement learning literature, Bareinboim, Forney & Pearl describe an experimental setting in which it is possible to both randomize unit's actual decision, and also record the natural decision the unit would have normally taken (Bareinboim et al.) 2015 Forney eet al. 2017). Subsequently, this procedure has been used to establish benchmarks in counterfactual decision making (Zhang & Bareinboim, 2022). These settings involve
an agent introspecting to gauge their natural choice, or otherwise revealing their natural choice by some indication, c.g. physical gestures prior to decision-tinn time.. Importantly, this form of randomization does not erase the unit's natural choice of decision variable X, as schematically illustrated in Fig. I
Building on the idea, we formalize this into a more general extension of the agent's capabilities: the ability to intervene on variable X's value as perceived by its causal children. To illustrate this, consider the C3-quantity known as natural direct effect, or NDE, which is used in mediation analysis to measure the effect of X on Y via a "direct" path, as opposed to an "indirect" path via mediator Z (Pearl 2001) highly relevant in several fields, as discussed in Sec. The NDE is generally considered as identifiable from experimental data only under certain conditions (Pearl. 2001 Correal ct al.) 202 The following example details an experiment design where it is possible to compute the NDE even when these identification conditions are not met, by randomizing the perception of X.
IIf the device used for enforcing the value is constant function, this action simply becomes WRITE(X:
(4) corresponding to the atomic intervention do(x:). See Preliminaries in See.
3

---

Published as a conference paper at ICLR 2025
Example 1 (Mediation analysis). A computer vision company's tool is being evaluated for an automated speeding ticket system that uses footage from traffic cameras. But the government's s audit team has concern: it is possible the model is trained footage with strong correlation between the color of the car and speeding (perhaps due to color preference of different socioeconomic neighbourhoodss, and unfairly penalizes certain car colors.
This amounts to a hypothesis that X (car's color) affects Y (AI decision to issue a ticket) via a direct path as opposed the indirect path via Z (speeding). The indirect path describes the causal effects of, say, how pedestrians and other drivers react to a red car and affect its speeding. This hypothesis is true iff NDE is measured to be non-O, where NDE is defined as the following expression: (D) = P( 2.) - P(yz) (Pearl 2001). The second term, P(yx), can be estimated from a Fisherian randomization of X (say, an experiment recruiting drivers and assigning them random cars). Inconveniently, the first term, P(Uz z. ), is nonidentifialle for Fig. 2aa), even using RCT data. So is unclear how to make progress with this hypothesis test.
However, the audit team recognizes there exists special mediator, viz. the features W in the video which reveal the car's color to the model (say, RGB values of pixels in the video frames). They use standard video-editing tools to randomly swap the color of the car in the footage. By randomly assigning a particular car W +- red, they are able to affect the mechanism fy 's perception of X:
Y
Z
X
Y
PeW X blue)
est. from L2 data
(1)
-P(Yw=roch X = blue)
Z natural value
(2)
Z
-P(Yw=red, 2x X blue)
consistency property (3)
Figure 2: (a) "Expanded" dia- gram for Example 1, where W is counterfactual mediator for X; (b) Randomizing the value of X as perceived by Y.
=P(Yx- 2x
X blue)
Def. 2.2 X = W
(4)
P(Yx ((YY=mm x Zx-
d-separation
(5)
Eq. 4 ii justifiedd because W controls Y's perception of X given a
fixed (formalized in Lemma E.4 in the full technical report here).
Thus, they are able to directly sample from the La-distribution P(Y n, X) via physical procedure, and use identification rules to obtaín P.).z,,) Using the formula for NDE, they can evaluate whether car's color has direct effect on the odds of getting speeding ticket.
Here, one is able to randomize X as perceived by one of its children, by leveraging the variable W (RGB values) that fully encodes information about X (color) and mediates its effect on Y. We capture this intuition with the following (informal) definition.
Definition 2.2 (Counterfactual mediator (informal)). We call W counterfactual mediator of X w.r.t Y E (h(X) if the value of X can be retrieved from W by the mechanism generating Y.
Other examples of interventions on perceived attributes via counterfactual mediators include changing details on a job application (name, pronouns, keywords) simulate a perceived alternate demographic identity (Bertrand & Mullainathan 2003). or editing specific portions of text input to a language model (Feder et al. 2022). Randomizing perception has been discussed in |Parr et al, (2016) $4.4.4). For detailed discussion of the causal semantics of intervening
perceptions, and the related literature, see (Plecko& & Bareinboim 2024 App. D. We also provide a rigorous treatment in App. E of the full technical report, including a formal Def. E.2 of a counterfactual mediator.
This important extension to experimental capabilities is captured in the following definition of a new physical action that an agent might be able to perform in environment.
Definition 2.3 (Counterfactual (ctf-) randomization), CTF-RAND' - C)O;; fixing the value of X as an input to the mechanisms generating C C Ch(X)g using a randomizing device having support over (X), for unit i, given causal diagram g.
The key differences between the Fisherian RAND (X)() and CTE-RAND(X + C)( are (1) CTT-RAND does not erase the unit i's natural decision (+); and (2) while RAND affects all chil- dren of X, CTF-RAND does not affect Ch(X) C. CTF-RAND can only be enacted under certain structural conditions, viz., either in environments which permit the measurement of a unit's natural decision while simultancously randomizing the actual decision (Bareinboim et al. 2015), where counterfactual mediators can be used to alter X as perceived by a subset of children. Whether the agent is indeed able to perform this action thus depends the specific experimental setting.
4

---

Published as a conference paper at ICLR 2025
implies that it is possible physically perform multiple randomizations involving the same variable X on a single unit i, with each intervention affecting a different subset of children. Further, CTE-RAND may only be performed w.r.t graphical child variable; it is not possible to bypass a child and directly affect a descendant's perception of X.
Note: Def. 2.3
3 COUNTERFACTUAL REALIZABILITY
Given the possibility of performing ctf-randomiiztion (Def. 2.3 we are interested in knowing which La-distributions can be accessed directly by experimentation. In this section, discuss the constraints imposed by nature on an agent. We then formally define realizability and develop a complete algorithm to determine whether an L3 Ca-distribution is realizable.
The most basic constraints experienced by the agent (natural or artificial) are physical. Each mecha- nism Jv E F represents some physical process that transforms a unit according to the laws of nature. For instance, taking a drug, X, produces a side effect in the patient, Y. by a biochemical reaction fy(XXUy) which depends on the drug and the patient's 's latent health condition, Uy. Once patient i has been subjected to mechanism fy under X = I, there appears to be no way to go back in time and subject the same patient to mechanism fy under the process (e.g., by taking an antidote to the drug), the latent factors U u might have changed after the experiment (e.g., the patient could have developed tolerance to the drug). Repeating the experiment on this patient is tantamount testing This observation is made more formal through the following assumption.
x'. Even if technologically feasible to reverse
unit with unknown latent features U u
Assumption 3.1 (Fundamental constraint of experimentation (FCE)). A unit i in the target population can physically undergo a causal mechanism fv E F at most once.
Remark 3.2. The FCE assumption entails that a unit can only be submitted to a particular mechanism fv (Pay, Uv) under single set of experimental conditions, received as input to fv. By implication. the physical actions in Defs. 2.1 2.3 can only be performed at most once per unit i.
Once unit i has been subjected to fv, it is not possible to re-run fv with differently fixed inputs. READ(V) thus only yields one value for i. Although otf-randomization permits multiple interven- tions involving the same variable X, each such intervention can only be performed once, since it impacts different child mechanisms that can each only occur once for unit i. We also assume that the agent only perform the physical actions in Defs. 2.1 2.3 up to isomorphism.
Definition 3.3 (Li.d sample). Given an Li-distribution Q = P(W.) and a sequence of physical actions (+) performed on unit i in an environment modeled by SCM M, producing a vector of realized values (( w for the variables in W. the vector is said to be an i.i.d sample from Q if pC PC(W!" = w (1))) = PM (W. = w), Vw, where pC is the probability measure over the beliefs of the acting agent C, and the l.hs is the probability of physical actions ( producing the vector w when performed on some unit i.
Definition 3,4 (Realizability). Given a causal diagram & and the set of physical actions A, an L---iisribbtiinn P(W.) realizable given A and 9 iff there exists a sequence of actions A from A by which an agent can draw an i.i sample (Def. 3.3 from P.M (MWW)), for any M E M()), the class of SCMs compatible with g.
We emphasize the distinction between realizability and identifiability. Identifiability (Pearl 2000 Def. 3.2.3) from g states that a distribution (say. P(v; do(x))) can be uniquely computed from the available data (say, P(v)) for any SCM compatible with the assumptions in G. Realizability of distribution states that it is physically possible for an agent to actually gather data samples according to this distribution.
We next develop an algorithm to decide whether a distribution is realizable. As an intuition pump, suppose that an agent able perform RAND(V + C), VV, E Ch(V), w.r. an input causal diagram, and wants to obtain samples from P(Z., Wt). Consider the diagram Go in Fig. 3 By performing TAF-RRAN(TT >> W) and CAN-RAND(X + Z), the distribution realizable. However, suppose the input diagram is G1. A necessary condition to measure Z, for a unit is for mechanism fA
Inn the philosophy of science literature, similar ideas have been discussed under the topic of the temporal asymmetry of causation |Reichenhach 1956 ŞTIIIV).
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 CTF-REALIZE
1: Input: -y-distribution Q P(W.; causal diagram 9; action set A.
16:
for each {action tag) E INTv do Perform the randomization on unit i If the random-ged seadoom-geeerteed value + tag.
17:
2: Output: Li.d sample w from Q; FAIL if
18:
Q is not realizable given G
discard the unit and return to Line 4 end for
3: Fix topological ordering Top(G)
19:
4: SELECT( for new unit i
20:
for each W. E OUTPUTy do
21:
if (RAND(V) : INTy then
5: for V in order Top(G) do
22:
Return FAIL
6: INT
(Interventions for V} 7: OUTPUTV t 0 {Index in output vector) for each term W, in expression W. do E An(W)) g and V o W then Call COMPATIBLE(Y, W2) Alg. end if
23:
else
24:
Perform READ(V) = v' Assign e' to each index W(( out-
8:
25:
9:
put vector w(()
10:
26:
end if
11:
27: end for
12:
if V
W then Add (We} to OUTPUTy
13:
28: end for
end if
15: end for
29: Return i..d sample w! w
to receive the natural value of T, illustrated in green. While a necessary condition to simultaneously measure W, is for fw receive A,, which in requires ʃa receive fixed I, shown in red. This
conflict in necessary conditions renders the query non-realizable R
This "edge-coloring" intuition is formalized in Algo. ! The algorithm CTF-REALIZE takes as input an L3- distribution P(W,). a graph G, and a set of physical ac- tions A the agent is able to perform in the environment (viz., the RAND and ble in the environment). It returns an iid sample if the distribution is realizable, and FAIL otherwise.
X
T
X
nat.
t
nat.
actions which are possi-
Z
Z
The algorithm works as follows (a more detailed walk- through is presented in App. C.2 of the full technical reporti: going over each node V in topological order, the inner loops gather the necessary and sufficient conditions needed w.r.t V for realizing each W, in the input query W.. If there is a conflict in the necessary conditions for evaluating two terms (as we saw for P(Z,, W;) in Fig. 3 Gi), the query is non- realizable. The algorithm is fully general and does not make assumptions about the ability to perform any particular interventions. If the agent cannot perform any counterfactual randomization, the algorithm returns FAIL for non-L, queries. If the agent cannot perform any interventions at all, the algorithm returns FAIL for non-Ci queries (we assume the ability to READ all variables). Details about the time and space complexity of Algo. I are provided in App. C.3 of the technical report
Figure 3: Testing realizability of P(Z., WT) for 91 (left) and G2 (right). G1 yields conflicting requirements.
Theorem 3.5 (Correctness and Completeness). An La-distribution Q = P(W.) is realizable given action set A and causal diagram isf the algorithm CTF-REALIZE/ 9, A) returns sample.
A further question we may ask is which L--distributions are realizable we assume maximum experimental capabilities, notably, the ability perform separate ctf-randomization for each child of each variable. Given causal diagram G, we define the maximal feasible action set A (G) as the set containing all of the following actions: (E) (E) VV, and CTF-RAND( + C)
VX and C Ch(X). A (G) thus gives the agent the most granular interventional capabilities.
Definition 3.6 (Ancestors of counterfactual (Correa al. 2021 ) Given causal diagram G and potential response Yx, the set of (counterfactual) ancestors of Yx, denoted An(Yx), consists of each
'To be clear. the input to the algorithm is graph and an accurate set of actions the agent can perform in the environment. If the graph is per G1 in Fig. 3 then STF-RANDAL - 7) is not possible in this environment. Marginalizing A and providing graph G2 as input does help.

---

Published as a conference paper at ICLR 2025
Con 3.7 An(W.) has
P(V): Lem. C.1
do()))())) Lem. C.3
same variable twice
P(U)
P(X,Y; doo(=))
P(V) P(X,Y)
P(Y;do(1))
P Paa x)
Layer (realizable)
Layer (realizable)
Layer 3 (partially realizable)
SCM (unknown)
Figure 4: Pearl Causal Hierarchy (PCH) induced by an unknown SCM M. An La-distribution is realizable given a graph and the maximal feasible action set A. (g) iff the ancestor set An(W., does not contain the same variable under different regimes.
Wz s.t. W E (nnAnn)))) gx and z = x An(W)ox For a set W., An An(w)) of the ancestors of each potential response in the set.
defined to be the union
Corollary 3.7. An Ly-distribution Q P(W.) is realizable given causal diagram G and action
set AT (g) iff the ancestor set An(W., .) does not contain a pair of potential responses We, W. of the same variable W under different regimes.
For instance, if W. (Zz, W.} w.r. graph G1 in Fig. then An(W.) (Zz, A, W. Ar), which contains both A, Ag. Thus, P(W.) is not realizable even with maximal experimentation capabilities. In App. C.4 of the technical report, we provide further examples of using the CTF- REALIZE algorithm, and the graphical criterion, to demonstrate the realizability of the ETT distribution P(Y,, X), the non-realizability the probability of sufficiency distribution P(Y,, X, Y).
We believe this is an important contribution to causal inference. Cor. 3.7 provides graphical criterion delineate how far up the PCH an agent can go via experimental methods, in principle. Often, counterfactuals have been criticized being hypothetical, untestable, or unscientific assumptions. Our analysis counters this claim, as summarized Fig.
Corollary 3.8 (Fundamental problem of causal inference (FPCI) (Holland 1986)). The distribution P(Y Y is not realizable given maximal feasible action set A (TG), 9. and any variables X, & Desc(X).
ffr for any causal diagram
The FPCT an influential notion in the literature, and is often taken as a primitive, or in an axiomatic fashion. We show that it is rather specific consequence of the more general FCE assumption 3.1 and follows from Thm. 3.5 and Cor. 3.7 By itself, the FPCI does not translate to an operational criterion for determining which di-distriuutions are realizable (Def. 3.4). For instance, it does clarify that distribution with potential responses under conflicting regimes like P(Y,. Zz') may indeed be realizable via counterfactual randomization, as we show in Example It also does tell us that P(Z., W:) may be realizable given causal diagram G2 in Fig. 3 but not realizable given G1-
APPLICATIONS: COUNTERFACTUAL DECISION-MAKING AND FAIRNESS
Next, we highlight the practical relevance of our results with some concrete use-cases. We already discussed in Example [how realizability can be used design experiments for performing mediation analysis of direct and indirect effects, an important task in several fields. We now discuss applications in causal fairness analysis and causal reinforcement learning (RL... Our goal to underscore that the standard/baseline approaches in these areas, even among approaches that incorporate coun- terfactual reasoning. typically use observational (C₂) or interventional (L2) data only, whereas a counterfactual (Cz) data-collection approach can lead to demonstrably better results. We include in App. of the full technical report the specification of SCMs used and algorithms implemented.
4.1 CAUSAL FAIRNESS USING COUNTERFACTUAL DATA FAIRER DECISIONS
Causal faimess analysis is a burgeoning field and full survey is beyond the scope of this paper (see, c.g.. Pleckoo & Bareinboim (2024) for a review of related works). We limit our discussion to an example where counterfactual realizability is directly relevant.
7

---

Published as a conference paper at ICLR 2025
A common concern is that models trained to make automated decisions often reveal problematic biases (Angwin et al. 2016 Kodiyan 2019 e.g.). The causal approach to address this is typically to constrai a classifier to obey some causally- -eensii-eesstiive fairness measure, μ (Plecko & Bareinboim 2024 Def. 3.3). Some measures in the literature involve La La-quantities, and thus face the familiar issue of nonidentifiability (Kusner et al.) 2017 Imai & Jiang 2023). Other approaches acknowledge this limitation and try to construct interventional fairness measures that solely use L2-quantities (Salimi et al. 2019). We present next an example where relying only on C2-data can misleadingly approve a classifier as fair, but where a realizable L3 fairess measure actually ensures faimess. This scenario is inspired by a classic experiment in labor economies (Bertrand & Mullainathan 2003).
Example 2 (Causal fairness). A college is developing an automated system to screen candidates in the first round of college applications, receiving as input a standardized CV per candidate. The system contains two models: model I outputs Y and model 2 outputs Z, which are binary decisions of whether the applicant cleared the first review stage for admission and for financial scholarship, respectively. The two models respectively trained using data from previous years where an admissions team and separate scholarship team reviewed applications manually. The college wants to ensure fairness w.r.t X, a candidate's race (a binary variable, for simplicity). In particular, they want to ensure equitable financial access to education for all qualified candidates: a candidate of race X= who cleared the admissions screening (Y 1) but was rejected for financial aid (Z = 0) should still receive Z O had they been of race X = O. The causal diagram is in Fig. []. where the models' decisions Y, Z might reflect the unconscious race bias of the two committees in previous years (including possibly shared biases, represented by the latent confounder).
The L3 fairness measure they ought to minimize is thus
X
Mets PP(,, 1, L,, = 0) P(Y, 1, Zz. = 0)] (6)
But the second term P(yz, ) is nonidentifiable from the causal diagram in a). So the college instead uses the following La measures, as approximation for the fairness condition:
(a)
(b)
Pint1 P(Y 1: (o(o))))) = 0; do(x1))
L trained
175
- -P = 1; do = 0; do(())))
Frequency
131
L trained
Mint2 =P(Y 1, 2 = 0; do(x1)
(8)
300
Myy 0.05
- PP = 1, 0: do(
They train the models, adding Mintl + Pint2 as penalty in the objective. /intt1 /4in2 are estimated using holdout set of fake CVs, with the intervention do(x) being enacted by randomly choosing applicant name from equivalence class which stereotypically indicates one unique race group X = x, e.g. names like Lakisha and Jamal for Blacks, or last names like Nguyen or Xi for Asians (cf. Bertrand & Mullainathanj (2003)) Since the holdout set's CV body is independent of X, any effect of X on Y and Z is solely via the perception of race from the candidate name. We show in (cc simulations of such an optimization. In blue is the distribution of the true score Hetf, when the models are trained using Mimt1, Mint2- Out of 1000 simulations of classifiers, we see Metf > 5% for nearly half the C2 simulations, indicating statistically significant discrimination roughly 50% the time.
Mad
(c)
Figure 5: (a) Causal diagram
for Example 2; (b) P(Y,, )
is realizable using the interven- tions CTE-RAND(X + Y) and CTF-RAND(X - Z); (c) His- togram of 1000 classifiers trained on L2 (blue) and C3 (orange) fair- ness measures. L2 classifiers show statisically significant discrimina- tion (Haff > 0.05).
However, the distribution P(Ya, R; ? is indeed realizable (Def. 3.4p via the interventions CTF-RAND(X - CTE-RADDDS XX -> 2)). The data science team notices that they can sepa- rately and simultaneously randomize the candidate name as input to the respective models, and enact these interventions, as shown in btb). Thus, they are able to directly use the counterfactual measure fetf as a fairness constraint training. Results from 1000 simulations show that the classifiers trained directly using fet (shown in orange) nearly always meet the faimess requirement.
Details of the implementation are in App. F.2 here Note: in the original experiment, this example requires the structural assumption of race being revealed at the screening stage only by candidate name, which may be more defensible in highly standardized and controlled application processes.
8

---

Published as a conference paper at ICLR 2025
4.2 CAUSAL RL COUNTERFACTURE POLICIES FOR OPTIMAL DECISION-MAKING
Consider a multi-arm bandit problem in which X represents the choice of bandit arm and Y the outcome. The default online learning approach
Table 1: Performance of differ- ent strategies in Example 3.
for the agent to adopt an algorithm like EXP3, UCB or Thompson Sampling to converge to some arm x² : arg max, E[Y; do(x:) (Lattimore & Szepesvári (0200/Sutton) & Barto 1998). Even in methods that explicitly incorporate causal knowledge, the common approach is to use a combination of offline (C1) and online (C2) data converge more efficiently to the Lo opti- mization target arg max; E|Y; do Zhang& & Bareinboim, 2017 e.g.). It was already shown in (Bareinboim et al. 2015 | al.
Strategy
E Y
Behavioral pol- 0.65 icy (C1)
Naive randomiza- 0.7 tion (C2)
2017) that it is possible to perform better by deploying a counterfac- tual strategy based sampling each unit's natural choice X = x²'
baseline 0.75 strategy (Lg)
ETT
and randomizing actual choice in the same round, thus seeking to
Optimal L3 strat- 0.80 egy (this work)
converge to arg max; E[y2 z²], Vx', we discussed in Sec. _ We call this the ETT baseline strategy, as it relies on drawing samples from the C3 ETT distribution, P(Y., X), mentioned in Sec.
We improve on this baseline by showing how an agent can leverage the realizability (Def. (3.4p of more nuanced counterfactuals like P(Yz, X, D,."' to construct superior counterfactual strategies. The following scenario involves an agent faced with adversarial latent confounding.
X
OMP
Example 3 (Counterfactual bandit policies). Consider user of a social media platform which uses surveillance and predictions to increase user engagement through ad- dictive notifications and recommendations (Zuboff] (018).
Tgee
Iterations
Borations
(c)
(d)
The user chooses every evening whether to use the plat- form via desktop (X 0) mobile (X 1). Y is a binary indicator of whether she stays within her self- determined social media usage limit per day. She also notices that she receives ads when she logs in each evening as D (0: streaming service, 1: food delivery ads). The usage type X affects D, Y, as shown in Fig. ((a).
Figure 6: (a) Causal diagram for
Example 3; (b)
is realizable using the interven- tions CTE-RAND(X 7 Y) and CTF-RAND(X - D); (c) Cumulative Regret (CR) for Li strategy (blue) and Thompson Sampling algorithms implementing naive La (yellow, green), ETT baseline (red), and optimal Es strategy (purple); (d) Optimal Arm Probability (OAP) for all algorithms.
On average, the user experiences E = 0.65 from the observational (C1) policy of following her natural incli- nation each day. She suspects that the company could be tracking and exploiting her latent preferences, she decides to randomize her daily choice and pick the best "arm".. Sure enough, this naive La strategy breaks the adversarial confounding, and incurs bet- ter avg. performance of E[Y; do(x)] = 0.7, Ya. She then decides to test the ETT-based strategy (Ca) described earlier, by recording what she naturally feels like doing each day (X z²), and subsequently randomizing her actual choice on the same day to optimize IY,,, x'), getting an avg. performance of 0.75. However, at this point, she notices that she can do even better. The La-distribution P(Yz. X. D=") is realizable (Def. 3.4. since she can perform another counterfactual randomization, by sampling her natural choice (X x'). randomly logging in to just see what ads she gets (D... = d), and again randomizing how she actually uses the platform that day to get Y,. This strategy seeks an optimal x arg max, [V, x', d. which performs best as shown in Table I Details of the SCM, latent confounders, and the optimal C3-strategy are in App. F.3 here.
Simulations in the online setting corroborate this finding. Fig. o(c.d) shows the cumulative regret (CR) and optimal arm probability (OAP) over 2000 iterations averaged over 200 epochs (CI=95%). We adapt Thompson Sampling to implement the strategies in Table Details of implementation are in App. F.3.1 here The optimal E3 strategy (purple) performs best, improving on the performance of the baseline baTed strategy (red). Naive randomizations, the standard C2 bandit strategy, are shown in yellow and green. All other algorithms fail to improve in OAP after 2000 iterations.

---

Published as a conference paper at ICLR 2025
We make two remarks. First, the optimal counterfactual strategy is not simply contextual Thompson Sampling, where X, Dæ" are used "merely" as extra context variables per round; indeed, treating this merely contextual bandit problem is one of the naive - that we test (green plot in Fig. clcd)), which ignores the counterfactual relationship between these variables and incurs dramatically higher regret, as we discuss in App. F.3.1 here
Second, an interesting follow-up is whether we can guarantee that our strategy based on maximizing E|Y, x', dgen is optimal in this problem. Perhaps there are more refined Ca-distributions like P(Y,, X, Da, Day)) etc. that could yield better algorithms? It turns that this is indeed optimal, since most other Cs-distributions are not realizable (Def. (34). We prove this claim for all bandit problems that fit generic template, in Thm. 4.2 of the technical report, Thereby, we avoid having to conduct an intractable search over the space of all possible L3-strategies, trying to assess their realizability.
DISCUSSION
Finally, we discuss some important implications, future directions, and limitations of our work.
Identification and bounding. Much work has been done in the area of L3 identification and estima- A natural extension to our work
tion (Shpitser 2008 Correa et al. | [Geneletti & Dawid to investigate the relationship between realizability and identification: which additional La-quantities now become identifiable if the environment permits even some counterfactual randomization? This warrants an update to existing identification algorithms to allow (some) Ly- as input. Another fascinating research question involves "partial identification". where an input query is tightly bounded within range that can be computed from available data (Zhang al. 2022): how would the new da-data further tighten the bounds for nonidentifiable La-quantities?
Experiment design. One of the goals of this paper is to instigate new experiment design ideas that
leverage ctf-randomization (Def. (2.3 and go beyond the standard RCT methodology. as in Examples For instance, the increasingly automated HR pipeline in companies suggests opportunities for Targeted interventions to randomize demographic details in virtual interviews, in standardized aptitude tests, or ceaftormannn-evlluutttii systems for remote workers, track fairness metries.
12
Causal reinforcement learning (CRL), While counterfactual strategies have been studied in CRL. the literature currently focuses on ETT-related strategies based on optimizing [Y,, x²) (Bareinboim
et al. 2015; Forney et al., 2017 Zhang & Bareinboim| 2022 (Richardonn & Robins 2013 $5.1).
We presented an important extension by formalizing etf randomization (Def. (.33 via counterfactual mediators (Def. [2.2). subsuming the previous approach. An ETT-based approach only allows one randomization of a variable X, affecting all downstream mechanisms. Our approach recognizes the possibility of isolating specific causal pathways and randomizing X multiple times per unit, demonstrably surpassing the ETT baseline in Example 3 We proved in Thm. 4.2 of the technical report an optimality guarantee for our proposed strategy in bandit problems. Generalizing this to sequential dacision settings with arbitrary graphs is an important, non-trivial extension.
Limitations. The first obvious limitation of our framework is that it requires causal knowledge in the form of a graph (or equivalent). This is a standard assumption, needed to make progress in several areas of causal machine learning. Subsequent work could accommodate partial knowledge or model misspecification. Second, it may not always be feasible to perform counterfactual randomization (Def. 2.3) in a given setting. This is why Algo. [ and Thm. 3.5 are general and do not assume this capability a priori. But where it is possible, even in principle, our work pinpoints opportunities for novel experiment design, as discussed above.
CONCLUSION
In this paper, we tackle the open question of which counterfactual distributions are directly accessible by experimental methods what we define as the realizability of a distribution. Countering prevalent belief, we provide a complete algorithm and a graphical criterion for when a counterfactual can indeed be physically sampled from (Fig. 4). We demonstrate the practical relevance of this new framework with examples from causal fairness and causal RL, highlighting that ignoring this possibility could lead to poor outcomes. We believe that switching from an interventional to counterfactual mindset could help researchers spot opportunities for counterfactual randomization that permit exciting new types of experiments, and improved, more personalized decisions.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This research is supported in part by the NSF, ONR, AFOSR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation. We thank Juan D. Correa and the anonymous reviewers for their thoughtful comments.
REFERENCES
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine Bias: There's software used across the country to predict future criminals. And it's bi- ased against blacks. 2016. URL
Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: causal approach. In Advances in Neural Information Processing Systems, pp. 1342-1350, 2015.
Elias Bareinboim, Juan D. Correa, Duligur lbeling, and Thomas Icard. On Pearl's Hierarchy and the foundations of causal inference. In Probabilistic and Causal Inference: The Works of Judea Pearl, pp. 507-556. Association for Computing Machinery, New York, NY, USA, 1st edition, 2022.
Marianne Bertrand and Sendhil Mullainathan. Are Emily and Greg more employable than Lakisha and Jamal? A field experiment on labor market discrimination. Working Paper 9873, National Bureau of Economic Research, July 2003. URLhttpp: / /www. nber wwt.oo/pppppp////g...
J. Correa and E. Bareinboim. A calculus for stochastic interventions: Causal effect identification and surrogate experiments. In Proceedings the 34th AAAI Conference on Artificial Intelligence, New York, NY, 2020. AAAI Press.
Juan Correa, Sanghack Lee, and Elias Bareinboim. Nested counterfactual identification from arbitrary surrogate experiments. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 6856-6867. Curran Associates, Inc., 2021.
Philip Dawid. Causal Inference Without Counterfactuals (with Comments and Rejoinder). Journal of the American Statistical Association, 95(450):407-448, 2000.
Amir Feder, Katherine A. Keith, Emaad Manzoor, Reid Pryzant, Dhanya Sridhar, Zach Wood- Doughty, Jacob Eisenstein, Justin Grimmer, Roi Reichart, Margaret E. Roberts, Brandon M. Stewart, Victor Veitch, and Diyi Yang. Causal inference natural language processing: Estima- tion, prediction, interpretation and beyond. Transactions of the Association for Computational Lingwistics, 10:1 1311118-111 1158, 2022. doi: 10.1 162/tacl a a.00511, URL/https: htattps://aclanthooooo org/ tacl2-atccl-1
Ronald A. Fisher. Statistical Methods for Research Workers. Oliver and Boyd, Edinburgh, 1925.
Ronald A. Fisher. The Design of Experiments. Oliver and Boyd, Edinburgh, 1935.
Andrew Forney, Judea Pearl, and Elias Bareinboim. Counterfactual Data-Fusion for Online Rein- forcement Learners. In Proceedings of the 34th International Conference on Machine Learning. 2017. ISBN 9781510855144 doi: hhtp:/dx.ddii.or. woo..oogg11..1011111 1037//002227500
Sara Geneletti and A. Philip Dawid. Defining and identifying the effect of treatment on the treated. In Causality in the Sciences. Oxford University Press, 03 2011.
James Heckman and Richard Robb Jr. Alternative Methods for Evaluating the Impact Inter- ventions. In J J Heckman and B Singer (eds.), Longitudinal Analysis of Labor Market Data. Cambridge University Press, New York, NY, 1985.
James J. Heckman and Richard Robb Jr. Alternative Methods for Solving the Problem of Selection Bias in Evaluating the Impact of Treatments on Outcomes. In H. Wainer (ed.), Drawing Inference From Self Selected Samples, pp. 63-107. Sprnnnerrrggeeeeellaaa New York, NY, 1986.
11

---

Published as a conference paper at ICLR 2025
P W Holland. Statistics and Causal Inference. Journal of the American Statistical Association, 81 (396):455-964 12 1986.
Duligur lbeling and Thomas Ieard. Probabilistic reasoning across the causal hierarchy, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10170-10177, 2020.
Kosuke Imai and Zhichao Jiang. Principal Fairness for Human and Algorithmic Decision-Making. Statistical Science, 38(2):317 - 328, 2023.
Akhil Alfons Kodiyan. An overview of ethical issues in using ai systems in hiring with a case study of amazon's 's ai based hiring tool. ResearchGate preprint, pp. 1-19, 11 2019.
Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Ang Li and Judea Pearl. Unit selection based on counterfactual logic. In Proceedings of the Sivent-Fiighth International Joint Conference Artificial Intelligence, IJCAI-19, pp. 1793-1799. International Joint Conferences on Artificial Intelligence Organization, 2019.
Scott Mueller and Judea Pearl. Personalized decision making a conceptual introduction. Journal of Causal Inference, 11(1):20220500 2023.
Scott Mueller and Judea Pearl. Perspective on 'harm' in personalized medicine an alternative per- spective. Technical Report R-530, 2024. httttss::://ftp cs uuclalll.... wwt.aaa..duubbbttttteeeeee
ser/ ser/r530.. htt00530..ppp.
Judea Pearl. Probabilities of causation: Three counterfactual interpretations and their identification. Synthese, 121(1-2):93-144 149, 11 1999.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2000. ISBN 978-0-521-89560-66
Judea Pearl. Direct and indirect effects. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, pp. 41 411-420. Morgan Kaufmann, San Francisco, CA, 2001.
Judea Pearl and Dana Mackenzie. The Book of Why. Basic Books, New York, 2018. ISBN 978-0-465-09960-9,
Judea Pearl, Madelyn Glymour, and Nicholas P Jewell. Causal inference in statistics: A Primer. John Wiley & Sons, 2016. ISBN 9781 1831119166 199186777
Drago Plecko and Elias Bareinboim. Causal faimess analysis: A causal toolkit for fair machine learning. Foundations and Trends in Machine Learning, 17(3):304-555 589, Jan 2024.
Arvind Raghavan and Elias Bareinboim. Counterfactual realizability. Technical Report R-113, Causal Artificial Intelligence Lab, Columbia University, Mar 2025. URL U htttthtttt//uusaaa ai net/
r113. 111..pff
Hans Reichenbach. The Direction of Time. University of California Press, Berkeley, 1956.
Thomas S. Richardson and James M. Robins. Single world intervention graphs (SWIGs): A unification of the counterfactual and graphical approaches to causality. Working Paper 128, Center for the Statistics and the Social Sciences, 2013.
James Robins and Sander Greenland. Identifiability and Exchangeability for Direct and Indirect Effects. Epidemiology, 3(2):143-115, 1992.
Donald B Rubin. Direct and indirect causal effects via potential outcomes. Scandinavian Journal of Statistics, 31:161-170, 2004.
12

---

Published as a conference paper at ICLR 2025
Babak Salimi, Luke Rodriguez, Bill Howe, and Dan Suciu. Interventional faimess: Causal database repair for algorithmic fairness. SIGMOD '19, pp. 193-810, New York, NY, USA, 2019. Association for Computing Machinery.
Ilya Shpitser. Complete Identification Methods for Causal Inference. PhD thesis, Computer Science Department, University of California, Los Angeles, CA, 2008.
lyya Shpitser and Judea Pearl. What Counterfactuals Can Be Tested. In Proceedings of the Twenty- Third Conference on Uncertainty Artificial Intelligence, pp. 352-332-3 259. AUAI Press, Vancouver, BC, Canada, 2007.
lya Shpitser and Judea Pearl. Effects of Treatment the Treated: Identification and Generalization. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, Montreal, Quebec, 2009. AUAI Press.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 1998.
Junzhe Zhang and Elias Bareinboim. Transfer learning multi-armed bandits: Causal approach. In IJCAI International Joint Conference on Artificial Intelligence, 2017. ISBN 9780999241 103.
Junzhe Zhang and Elias Bareinboim. Can humans be out of the loop? In Bernhard Schölkopf, Caroline Uhler, and Kun Zhang (eds.), Proceedings of the First Conference on Causal Learning and Reasoning, volume 177 of Proceedings of Machine Learning Research, pp. 1010-1025. PMLR, 11-13 Apr 2022.
Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 16548-265556 PMLR,, 17-23 Jul 2022.
Shoshana Zuboff. The Age of Surveillance Capitalism: The Fight for Human Future at the New Frontier of Power. 1st edition, 2018. ISBN 1610395697.
13

---

Published as a conference paper at ICLR 2025
A GRAPHICAL TERMINOLOGY
Structural Causal Models (SCM) and causal diagrams are described in the preliminaries in Sec. | See Bareinboim et al. 2022) for full treatment. use the following graphical kinship nomenclature w.r. causal diagram g:
Parent(s) of V, denoted Pay: the set of variables (V') s.t. there is direct edge V V in G. Pay does not include V.
Children of V, denoted (V)):: the set of variables (V)) s.t. there a direct edge + V in G. Ch(V) does not include V.
Ancestors V. denoted An(V): the set of variables {V'} s.t. there is a path (possibly length 0) from V' to V consisting only of edges pointing toward V, V > V. An(V) is defined include
Descendants of V, denoted Desc( V): the set of variables {V') s.t. there a path (possibly length 0) from V to V' consisting only of edges pointing toward V V ... V Desc(V V) is defined to include V.
Non-descendants of V, denoted NDesc(V): the set V Desc(V). NDess(V) does not include V.
Given graph 9, &xw the result of removing edges coming into variables in X, and edges coming out of W.
B SUB-ROUTINE OF CTE-REALIZE ALGORITHM (ALGO. ①
Algorithm 2 COMPATIBLE (sub-routine)
1: Input: V V of G; W, W, of Q
20:
end if end if
2: for each C' CChVV) do
21:
3: if E An(W) then
22:
if V & T then
4:
V E T then
23:
for
each C
3
s.t.
5: Let == value of V in subscript
CTE-RAND(V + C) do
6:
Find smallest C 3
C s.t.
24:
(CTF-R - C) : E INTy and its label is not "Natural" then
CTE-RAND(V + C) E
7:
if (CTF-RAND(V - C)
}
E
INT and its label is not "o" then
25:
Return FAIL else
8:
Return FAIL
26:
9:
else
27:
Add (CTF-RAND(V C) Natural) to INTv, with the la- bel "Natural"
10:
Add (CTE-RAND(V + +C): to INTv, with the label "v" end if
11:
28:
end if end for if (RAND(V) : E INTv and its label is not "Natural" then
12:
no such CTE-RAND(V - C) E A then if (RAND(V): : INTy and its
C s.t.
29:
30:
13:
label is not "o" then
31:
Return FAIL
14:
Return FAIL else if RAND(V) & à then
32:
else if RAND(V) E A then Natural)
15:
33:
Add {RAND(V).
INT with the label "Natural"
16:
Return FAIL else
34:
end if
18:
Add [RAND(V) w) to INTv, with the label " end if
35:
end if
36:
end if
19:
37:
end for
For a detailed walkthrough of the algorithm and sub-routine, refer to Appendix C.2 of the full technical report here
14

---

Published as a conference paper at ICLR 2025
The full technical report also contains detailed examples of applying the algorithm to different graphs and queries, in its Appendix C.4 (Raghavan & Bareinboim 2025).
C ASSUMPTIONS AND REALIZABILITY PROOFS
For a summary of all the structural assumptions we make in this paper, and proofs of the results, refer Appendix D of the full technical report here
C.I REALIZABILITY OF L1- AND L2 L2-DISTRIBUTIONS
It widely known and acknowledged that it is possible to draw samples from C1- and Cz-distributions: the former by simply observing a system's 's natural behaviour, and the latter by intervening in the system through interventions like Fisherian randomization.
Still, we find educational to derive these proofs from first principles. This sub-section is not strictly needed follow the main contributions in Secs. 2 and 3
We define the probability measure (.) from the perspective an exogenous agent (i.e., an agent external to the system) C's beliefs about the environment, distinguished by superscript from PM()) the true unknown distribution.
Since unit selection is randomized, SELECT() yields unbiased sample of unit with latent features distributed according the target population frequency P(u). Le., pC(U(O) u SELECT pM (u). We also assume that target population size large enough that SELECT( does not significantly change the distribution of the remaining population.
Further, we assume that the actions READ(V) (6) and (AND(V)()) do not disrupt any other mechanism fv. for unit i.
Lemma C.1 (Observational sample). An agent C can draw an i.i.d sample distributed according to the Li query P(V) associated with an SCM M, by the following actions:
i. (
ii READ(V)(==V =V~ P(V)
Given N i.i.d samples, the consistent unbiased estimate of P(v) is
1 P(v) : N
EI $ NEV
(READ(V) =
Proof. This follows directly from the definitions of the actions. SELECT chooses unit random from the population. By Remark D.3 pC(U() =u uul SELECT()) PM()). For randomly selected unit i,
p (REEA(VV)(0 SELECT())
(10)
PC((U()) (1))CT(
(11)
P (READ((V))) U u, SELECT(
Chain rule
C SELECT( (V)(
Def. 2.1 iii
(12)
(MM(M)) =v
Rem. D.3
(13)
=PM(vV
Definition
(14)
15

---

Published as a conference paper at ICLR 2025
Le., this record is an i..d. sample from PM (VV.. Now consider the estimator below.
P(v)
1
EI
READ(V) =
(15)
N
VEV
1
M [U = u...I =
(16)
N
NEV
Un- un-biaseddness is established by taking expectation on either side, w.r.t the agent C's actions (choice of units to observe):
Ec Ec[P(v)] = Ec
1
ΣEI
1M
M = ul.1 (V(() wi]
(17)
PEV
Fe
M
M
II [V(u)) = w1]
Linearity expectation (18)
N
n
NEV
Ec
M M = II M (V(u)) u
Vuu) constant wrt C
(19)
N
NEV
N.PM
w
M (M) =
Def. 2.1
Rem. D.3
(20)
N
DEV
pv)
Definition (21)
Consistency is established by the fact that A (target population size) + oo, and N (sample size)
+ 00,
Σ T M = u] - pM((u)
(22)
Lemma C.2. The L2 distribution of an atomic intervention is equivalent the L2 distribution of the corresponding conditional stochastic intervention.
p. (v; do(x)) P. (v xx
(23)
Σ 1[V (u) v Xax = x P(u)
(24)
Proof. The step from the r.h.s Eq. 23 to Eq. 24 derived follows: in the submodel Max if
given that X has been randomly assigned then the remaining variables are deterministically generated as a function u and x via their respective equations. The probability mass is collected over all the which produce the output over all these equations.
(M(xxx; = -- T[V (n) v Xax = PM)))
(25)
Notice: if v is incompatible with x, the indicator in the r.h.s evaluates to O. Next, prove. Eq.
23
In Msx, as defined, X is assigned according to an independent random vector, Notate this vector as Xox and let the distribution of this vector be Pax (X), defined by the assignment frequency over the target population.
M,x is defined such that the target population is split into groups, each assigned (Xox x) for some x. Note, the assignment vector X is independent the latent features U across the target population iff each finite group assigned (X.x x) has the same distribution of latent features P(U) as in the overall target population.
The above discussion handles the finite size of the target population. Starting with the r.h.s of Eq.
23
pv(xxx;ox) = P(v,x;ox)
{
if v compatible with x otherwise
(26)
pxx;ox)
10
16

---

Published as a conference paper at ICLR 2025
Evaluating for when is compatible with
p(v;ox)
ox)
(27)
oxx;
Pox (x)
Σn P(u) Inevix P(u. pa, u:) (x)
Truncated factorization product
(x)
(28)
Σ P(u) II
P(u pa,, u:)
(29)
u
VEViX
PM (v;
Truncated factorization product
(30)
Eq. 28 uses the fact that each sub-group assigned (Xox x), by independence, has the same frequency of latent features P(u).
Lemma C.3 (Interventional sample). An agent C can draw an i...d sample distributed according to the L2 query P(V; do(x)) associated with an SCM M, by the following actions:
i. SELECT()
i.. RAND(X)())
iii. If RANDD(X)()
x. then READ(V))) = P(V; else repeat i-iii.
Given Nx iidd samples, the consistent unbiased estimate of Eq. 24 is given by
P(v; do(x)) =
(R)AD(V) v, RAND X (9) x).
(31)
Proof. The proof steps similar to the ones used for the Observational i.i.d sample case. Note that Remark D.3 still hold since even though the agent is conditioning on the value randomly assigned to a particular unit this value independent of the unit's latent features U())
17


Reviews:
[{"review_id": "NuyKA2dmlA", "reviewer": "Reviewer_jnLW", "summary": "This paper considers a simple procedure that makes it possible to sample certain counterfactual distributions (counterfactual realizability). The key observation is that the perception of a variable to its children can be intervened upon in some cases. This procedure is called counterfactual randomization. It also proposes an algorithm that takes in a candidate counterfactual distirbution and a graph, and outputs a sample from the counterfactual query if and only if it is possible to sample from the input candidate. Finally, a graphical characterization for counterfactual realizability is given.", "questions": "1) One interpretation of the counterfactual randomization procedure is that the counterfactual distribution is just an interventional distribution where the intervention is performed on the perception. Given that a few counterfactual distributions are realizable as defined, how does this affect the notion of 'causal hierarchy'?  Some discussion on this would certainly strengthen the paper. \n2) The main body and the proofs often use the notion of a probability measure of belief of an exogenous agent. I thought that this was ill-defined. Perhaps the authors could make Remark C.7 an axiom that defines this measure?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As the paper points out, the counterfactual randomziation procedure in itself has been alluded to in previous work. But, the main contribution of this paper is a characterization of when a counterfactual distribution can be 'realized'. I liked that the paper operates under this structure for sampling distributions at different levels of the causal hierarchy by the notion of actions. Since counterfactuals are commonplace in many applications and a major hurdle is their non-identifiabilty, this work is certainly significant. The paper is well written and padded with many examples to illustrate the applicability and importance of the procedure.", "weaknesses": "As the paper also mentions, I believe the idea for intervening on perceptions was known before and makes multiple informal appearances. A few other references are (S. Geneletti, A.P. David, Defining and identifying the effect of treatment on the treated, 2010). Also, the notion of SWIGs (Richardson and Robins, 2013) is quite similar. I believe a more thorough comparison with previous work is needed to make the paper more complete.", "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": "", "extra_scores": {}}, {"review_id": "U6QA8jjKnP", "reviewer": "Reviewer_4NTd", "summary": "The authors tackle the complex space of sampling from counterfactuals. \n\nSpecifically, they propose a \"formal definition of realizability, the ability to draw samples from a distribution, and then developing a complete algorithm to determine whether an arbitrary counterfactual distribution is realizable given fundamental physical constraints, such as the inability to go back in time and subject the same unit to a different experimental condition\"\n\nBoth causal fairness and CRL are used as illustrative examples, suggesting that a counterfactual strategy dominates strategies based only on interventional and observational data.", "questions": "- [ ] Bounding in mentioned but not referenced? The word \"bounding\" appears twice in the text, but at first mention is not referenced. Bounding is not a well known method, and without further definition will not be useful to the reader unless at least minimal referenced (and not just in the discussions section)\n- [ ] 535 Countering prevalent belief\n    - [ ] References pls, readers need to be able to verify claims independently\n- [ ] 168 fig 2a does not exist, do you mean top?\n- [ ] Assumption 3.1: I worry that this statement is too vague for a reader to agree with. Can you provide more justification for why this is reasonable to hold in practice? If not, provide justification for why a practitioner should entertain this method to provide additional analysis instead. \n- Can you define \"causal machine learning\"? I am aware that this is an emerging term, but in the context of this paper it is unclear to me what part of it the authors are trying to address exactly. \n\nTypos: \n- [ ] 507 typo \"cotribution\"\n- [ ] 175 mechanism OF\n\n\n\n\n\n- [ ] 258 what is an intuition pump?\n- [ ] 431 appreciate limitations\n    - [ ] What about limitations in general though?\n- [ ] 507 typo\n- [ ] 507: what bounding do you mean here? References?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper tackles a relevant problem, and covers all key bases to provide its key contribution. \n\nSampling from counterfactual distributions is naturally hard, and developing methods and tools to do so is important, as suggested in the paper.", "weaknesses": "I am not an expert in this field, so take it with a grain of salt:\n\nAs written by the authors \"representing counterfactual distri- butions, is believed to be inaccessible almost by definition.\"\n\nReferences are provided for e.g. the 'counterfactual randomisation procedure', i.e. attempts at sampling from CFs, but there is not much discussion about why it is 'believed' why CFs are inaccessible by definition.\n\n\"inaccessible almost by definition\" is not precise enough to be useful for a reader, \"almost\" needs to be refined and explicated, ideally both via intuition and formally, even just briefly.\n\nIn the conclusion, this rigour is missing, too, when the authors state: \"Countering prevalent belief\". A reader needs references to be able to follow the thoughts and verify by themselves, that indeed, the venture of CFs sampling is hard (or impossible?)\n\nIf CFs are not in fact \"\"inaccessible almost by definition\"\", then this paper of course would constitute a huge contribution to the field of causal inference in which case this should be highlighted more.", "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": "", "extra_scores": {}}, {"review_id": "hl3lXR91V2", "reviewer": "Reviewer_doTz", "summary": "The authors provide necessary and sufficient conditions for a ground truth counterfactual quantity of an SCM to be sampled directly (''realized'') through a ''counterfactual experiment''. Such an experiment involves manipulating the original SCM through adding mediators through some direct causal effects---a process the authors motivate with intuitive real-world examples.", "questions": "I would argue there do exist physically viable experiments that break the authors’ proposed fundamental constraint on experimentation. For instance, in the authors’ example of an artificial agent’s decision to issue a speeding ticket from video footage based off the color of a car, both the doctored footage of a yellow car and the original footage of a red car could be fed to multiple copies of the same artificial agent. Perhaps the assumption is more properly termed a ''constraint on experimentation without cloning’’?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The authors' contributions are original and significant. Their insights are laid out clearly and limitations and discussion of future work are provided. \n\nThe authors show the advantages of counterfactual experiments with intuitive examples. The authors show that counterfactual fairness measures that are not identified through interventions can be realized (and thus identified) through counterfactual experiments. Furthermore, the authors show that bandit policies which allow for counterfactual mediators dominate policies from the classical causal bandits setting.", "weaknesses": "I do have few substantial weaknesses to discuss. In the Questions section I voice a slight disagreement about the interpretation of ''physically possible'' experiments. Below are some minor comments.\n\n(Lines 105--107) Presumably W_* is a tuple of potential outcomes and w is a vector over the support of W_*. These should be defined formally to avoid confusion. I suspect there is a typo on line 107 when defining P^M---perhaps taking the product over t = 1 to |W_*| would clear this up. \n\n(Lines 120--121) Read (V)^(i) does not ''measure'' the effect of f_V on V, these mechanisms are in general not identified. This should be reworded---perhaps the physical actions should be defined formally.\n\n(Figure 2) Given the discussion in Example 1, it may be more natural to include latent confounding between X and Z in the DAGs.", "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": "", "extra_scores": {}}, {"review_id": "lmlLOrY7Pq", "reviewer": "Reviewer_4AQU", "summary": "Inspired by (Bareinboim et al., 2015), the authors introduced a new action of \"counterfactual randomization (ctf-randomization)\" in structural causal models. One of the examples of how such action can be applied is given in Definition 2 (Counterfactual mediator). In particular, for some variable $X$ and its children $Y$, $W$ is the counterfactual mediator of $X$ if the mechanism generating $Y$ can retrieve the value of $X$ from $W$. The authors studied under what conditions on the causal structure and set of available actions (which might include counterfactual randomization), it is feasible to generate i.i.d samples from a counterfactual distribution. This study assumes that each unit undergoes each causal mechanism only once (Assumption 3.1). The authors provide graphical conditions along with an algorithm (CTF-REALIZE) to check the feasibility of sampling (which they call this problem \"realizability\"). Moreover, they characterized graphical conditions for the case that it is possible to perform ctf-randomization for each child of\neach variable, and as a corollary, they obtained the case of \"fundamental problem of causal inference\". They explored the applications of counterfactual realizability in causal fair analysis and causal bandits. In particular, they showed in an example that the interventional fairness metric fails to preserve disparities\nin outcomes across groups while a counterfactual one approach works in it. Moreover, in a specific causal bandit setup, for a specific \"MAB template\", they showed that the proposed $\\mathcal{L}_3$-based strategy is optimal.", "questions": "1. For what real applications, is it possible to implement ctf-randomization? To my understanding, this might be only possible for some output $Y$, where it is generated by a computer program. Therefore, it is possible to generate the output several times with different inputs with the same randomization.\n\n2. In the definition of counterfactual mediator, it is assumed that the value of $X$ can be retrieved from $W$ in the causal mechanism that generates $Y$. Does it mean that there is no exogenous noise in $W$ and it is generated deterministicly from $X$?\n\n3. It is good to provide some intuitions on the advantage of using $\\mathcal{L}_3$-based methods that are discussed in Section 4. \n\n4. Please provide a clear description of  Algorithm 1 and COMPATIBLE subroutine either in the main body or the appendix. This should start with a general idea of the algorithm or subroutine and then describe the algorithm in detail. In the current version, it is hard to verify the main results for Algorithm 1.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality/Quality:\nThe definition of ctf-randomization and the algorithm for checking the counterfactual realizability are new in the field of causality. Moreover, the authors discussed the applications of $\\mathcal{L}_3$-based methods in fairness analysis and bandit problems which might be interesting for people in other fields.\n\nClarity: The writing should be improved as some of the parts need more explanations.\n\nSignificance: Although the concept of counterfactual realizability is new in the field, it is not completely clear to what extent such ctf-randomization can be implemented in reality.", "weaknesses": "The content of the paper is fairly dense and the authors did not have enough space to give a sketch of the proofs or even CTF-REALIZE algorithm is not described very well in the paper (For instance, it is not clear why there is a rejection sampling in line 18 of Algorithm 1). This also applies to the results in Section 4. Although the authors showed in some specific scenarios, $\\mathcal{L}_3$-based methods perform better than $\\mathcal{L}_2$-based methods, there is no intuition given in the paper why this is the case. One might wonder if the causal graphs or the causal mechanism are meticulously engineered to show the advantage of counterfactual reasoning.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)