Counterfactual Randomization Sampling — Poster

Paper context

Paper title: Counterfactual Realizability: Sampling from Counterfactual Distributions via Randomization Abstract: This poster introduces counterfactual randomization, a method to sample from counterfactual distributions in Layer 3 of Pearl's Causal Hierarchy. It defines realizability, presents the CTF-REALIZE algorithm, and demonstrates applications in causal fairness and reinforcement learning. Paper body (method & results): Published as a conference paper at ICLR 2025 (Spotlight) COUNTERFACTUAL REALIZABILITY Arvind Raghavan and Elias Bareinboim Causal Artificial Intelligence Lab Columbia University {ar, eb}@cs.columbia.edu 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. 1 INTRODUCTION The Pearl Causal Hierarchy, or PCH, is an important recent milestone in our understanding of causality (Pearl & Mackenzie, 2018; Bareinboim et al., 2022). The three layers of the PCH represent the distinct regimes of seeing, doing, and imagining, with regard to an 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(x)), using the do() operator. Layer 3 (L3) represents counterfactual distributions dealing with conflicting realities, such as P(Yx | x′, y′): the distribution of Y had X been fixed as x, given that X, Y were in fact naturally observed to be x′, y′. Higher layers subsume lower ones, but are underdetermined by them (Ibeling & Icard, 2020; Bareinboim et al., 2022). Reasoning about L3-quantities plays a vital role in personalized decision-making (Mueller & Pearl, 2023), analysing a causal effect into direct and indirect pathways (Pearl, 2001; Rubin, 2004), 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(yx | x′), an important L3-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 higher-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(Yx, X) in the case of ETT, and then uses statistical methods to estimate P(Yx = 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. 1 arXiv:2503.11870v1 [cs.AI] 14 Mar 2025 Published as a conference paper at ICLR 2025 (Spotlight) PCH L1 P (Y ) P (Y |x) L2 P (Y ; do(x)) realizable L3 P (Yx|x′) P (Yx|x′, y′) ? M⋆ SCM (unknown) Figure 1: It is commonly as- sumed an agent can sample only from L1 and L2 distribu- tions in the real world. It is generally believed to be feasible to draw samples only from L1- and L2-distributions, the latter by interventions like random- ized controlled trials (RCT), `a la Fisher (Fisher, 1935), and the former by simply observing the natural behaviour of the system. L3- distributions like P(Yx, X) are deemed non-realizable in general, as the potential response Yx and natural decision X belong to different ”worlds”. Once a unit naturally adopts decision X = x′, Yx can- not be evaluated in the do(x) regime for the same unit.1 However, Bareinboim, Forney & Pearl have shown it is feasible to draw sam- ples from the ETT distribution P(Yx, X) through a counterfactual randomization procedure (Bareinboim et al., 2015; Forney et al., 2017). This leaves open the possibility that other L3-distributions, say perhaps P(Yx, X, Y ), are also realizable through clever experi- mental setups, allowing one to estimate important quantities like the probability of sufficiency, P(yx | y′, x′) (Pearl, 1999). This brings us to the central question motivating this work: from which L3-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 L3-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. 3 we develop the CTF-REALIZE algorithm (Algo. 1) to determine whether an L3- distribution is physically realizable. We prove the algorithm is complete (Thm. 3.5), 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. 4 we discuss important practical implications of counterfactual realizability. The traditional route of computing L3-quantities through identification or bounding often fails. Our work suggests opportunities for novel experiment-design ideas to directly estimate these quantities, as illustrated through Examples 1,2 and 3. More concretely, – In Sec. 4.1, we describe an application in causal fairness, where the naive approach of constraining a classifier using an interventional (L2) fairness metric fails to prevent disparities in outcomes across groups, but where a counterfactual (L3) approach works. – In Sec. 4.2, we show how counterfactual randomization can be used to improve RL algo- rithms. The baseline approach in a multi-arm bandit setting is to use allocation procedures (e.g., UCB, EXP3, Thompson Sampling) to discover which arm x optimizes the expected outcome E[Y ; do(x)], which is an interventional (L2) strategy (Sutton & Barto, 1998; Latti- more & Szepesv´ari, 2020). It turns out there are provably superior strategies (w.r.t expected outcome) based on directly optimizing counterfactual (L3) objectives, as we demonstrate in Example 3. We prove optimality of our proposed strategy in a bandit setting with a generic causal template (Thm. 4.2, Cor. 4.3). Proofs and details of simulations are included in Appendices. 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)(Pearl, 2000). An SCM M is a tuple ⟨V, U, F, P(u)⟩. V is the set 1E.g., ”The problem with counterfactuals like [P(Yx | 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 (Spotlight) of observable variables. U is the set of unobservable variables exogenous to the system, distributed according to P M(U). F = {fV } is a set of functions s.t. each fV causally generates the value of V ∈V as V ←fV (UV , PaV ), where UV ⊆U and PaV ∈V \ V . Each M induces a causal diagram G (Bareinboim et al., 2022, Def. 13), which is a graph containing a vertex for each V ∈V, a directed edge from each node in PaV to V , and a bidirected edge between V, V ′ if UV , UV ′ are not independent. Given a graph G, GXW 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. B). 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. In other words, this is an intervention in the model M which overrides the natural mechanisms that generates X and assign fixed values x to these variables. A variable Y ̸∈X evaluated in this regime is called a potential response, denoted Yx. (W⋆= w) denotes an arbitrary counterfactual event, e.g. (Yx = y ∧Yx′ = y′ ∧X = x′′). The probability of such an event is given by the L3-valuation (Bareinboim et al., 2022, Def. 7): P M(W⋆= w) = P u  Q Wt∈W⋆1[Wt(u) = w]  P M(u), 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 behaviour a unit. Examples of units are patients in a clinical trial, neighbourhoods in a social science experiment, rounds played on a slot machine etc. We index units w.l.o.g. by i = 1, 2, 3..., which constitute a target population in the system. Definition 2.1 (Physical actions). (1) SELECT(i): randomly choosing, without replacement, a unit i from the target population, to observe in the system. (2) READ(V )(i): measuring the realized feature V (i) of unit i, produced by a causal mechanism fV ∈F operating on i. (3) RAND(X)(i): erasing and replacing i’s natural mechanism fX for a decision variable X with an enforced value drawn from a randomizing devi