Counterfactual Structural Causal Bandits
Authors: Min Woo Park
Sanghack Lee
Venue: ICLR 2026 Poster (2026)
Keywords: causal inference
counterfactual inference
structural causal bandits
causal decision making
Primary area: causal reasoning
TL;DR: We introduce a counterfactual structural causal bandit (ctf-SCB) framework which expands the agent's feasible action space beyond conventional observational and interventional arms to include a class of realizable counterfactual actions.

Abstract: Causal reasoning lies at the heart of robust and generalizable decision-making, and the *Pearl Causal Hierarchy* provides a formal language for distinguishing between observational ($\mathcal{L}_1$), interventional ($\mathcal{L}_2$), and counterfactual ($\mathcal{L}_3$) levels of reasoning. Existing bandit algorithms that leverage causal knowledge have primarily operated within the $\mathcal{L}_1$ and $\mathcal{L}_2$ regimes, treating each realizable and physical intervention as a distinct arm. That is, they have largely excluded counterfactual quantities due to their perceived inaccessibility. In this paper, we introduce a *counterfactual structural causal bandit* (ctf-SCB) framework which expands the agent's feasible action space beyond conventional observational and interventional arms to include a class of realizable counterfactual actions. Our framework offers a principled extension of structural causal bandits and paves the way for integrating counterfactual reasoning into sequential decision-making.

Published as a conference paper at ICLR 2026
COUNTERFACTUAL A CAUSAL BANDITS
Min Woo Park
Sanghack Lee"
Scoul National University Seoul, Republic of Korea
Scoul National University Seoul, Republic of Korea sanghack@smu.aco ac.
al sds0dd0000 10:0010@@smie www.dsnn.......... ac.k
ABSTRACT
Causal reasoning lies at the heart of robust and generalizable decision-making and the Pearl Causal Hierarchy provides a formal language for distinguishing between observational (L1), interventional (L2), and counterfactual (Ly) levels of reasoning. Existing bandit algorithms that leverage causal knowledge have primarily operated within the L and C, regimes, treating each realizable and physical intervention distinct arm. That is, they have largely excluded counterfactual quantities due to their perceived inaccessibility. In this paper, we introduce a counterfactual structural causal bandit (CTF-SCB) framework which expands the agent's 's feasible action space beyond conventional observational and interventional arms to include a class of realizable counterfactual actions. Our framework offers a principled ex- tension of structural causal bandits and paves the way for integrating counterfactual reasoning into sequential mecision-making.
INTRODUCTION
The Pearl Causal Hierarchy (PCH) (Pearl and Mackenzie, 2018; Bareinboim et al., 2022) is a crucial milestone in our understanding of causality. The three layers of the PCH correspond to distinct regimes of reasoning about an environment: seeing, doing, and imagining. The first layer Lı represents observational distributions, such as P(Y I)), the second layer La represents interventional distributions, e.g., P(Y do(x)), using the do-operator (Pearl, 1995). The last highest layer, L3 represents counterfactual distributions addressing confliciing realities, such as effect of the treatment on the treated (ETT), P(Y, x²) (Heckman and Robb Jr, 1985; 1986): the distribution of Y had X been fixed as x, given that X was observed to be x'. is understood that higher layers subsume lower ones, but are unanswerable by them (Ibeling and Icard, 2020; Yang and Bareinboim, 2025).
It has long been believed that only L and C2 distributions are feasible to sample (known as realiz- ability of the distributions (Raghavan and Bareinboim, 2025)) in practice; the former through passive observation of the system's 's natural behavior, and the latter via Fisherian randomization (Fisher, 1935). In contrast, La distributions (c.g.. ETT) are typically considered non-realizable, since once a unit naturally adopts the decision X = x', the hypothetical outcome Y, under the counterfactual intervention do(z) cannot be simultaneously observed for the unit. However, Bareinboim al. (2015), Fomne et al. (2017) and Forney and Bareinboim (2019) have shown that it is feasible to draw samples from P(Y,, xx) through specific procedure called counterfactual randomization, in which one randomizes a unit's actual decision while also recording the natural decision that the unit would have normally taken according to its intention. More generally, Raghavan and Bareinboim (2025) characterized realizable distributions and provided guidance on how to draw such samples.
A parallel line of research has explored how causal models can be used to structure and optimize docision-making (Kumor et al., 2021; Zhang and Bareinboim, 2022; Bareinboim et al., 2024). Specifically, Bareinboim al. (2015), Lattimore et al. (2016), and subsequent works (Lu al., 2020; Bilodeau et al., 2022; Feng and Chen, 2023; Varici et al., 2023) have viewed multi- arme bandit (MAB) (Robbins, 1952; Lai and Robbins, 1985; Lattimore and Szepesvári, 2020) through a causal lens, where each action corresponds to an intervention on a variable, thereby grounding the bandit problem in a structural causal model (SCM) (Pearl, 2000). Building on this view, Lee and Bareinboim (2018; 2019) formalized a structural causal bandit (SCB) framework. They showed that
"Corresponding author

---

Published as a conference paper at ICLR 2026
naively applying standard bandit algorithms to full set of interventions can unnecessarily incur large regret, and proposed refining the action space prior to applying standard learning methods without relying parametric assumptions. Extending this line of work, we aim to investigate SCB at higher layer of PCH, encompassing hypothetical yet realizable actions.
Example (AI-assisted clinical decision support system). Consider a hospital aiming to improve the quality of pa- tient care. Let Y denote the final frealment outcome (e.g.. whether patients are discharged without complications), X patient's health status, W an expert physician's 's assessment, and Z the score from an Al-assisted clinical tool. Fig. la illustrates the scenario, where bidirected edges represent un- observed confounders such as history bias (Peiffer-Smadj et al., 2020). In the natural regime, a patient describes their health condition æ in their own words, and the subsequent evaluation yields the expected outcome BY,, (Fig. 1b). Alternatively, a standardized symptom-reporting interface can be introduced to translate the patient's 's input into a structured form X With this interface, the patient's 's natural description a remains available for the expert assessment, while the AI tool instead perceives reformulated and potentially different report x', c.g., a version that removes exaggeration and supplements prospective information, such as the anticipated health benefits of beginning regular exercise (Fig. 1c). This setup enables the evaluation of the hypothetical intervention EYw,. Z. allowing one to ask counterfactual- level questions- "what the Al assistant had perceived the patient's prospective health status x' rather than the current one x?? "=" and to design decision strategies that improve patient outcomes.
(a)
(b)
Figure I: Counterfactual regime.
Contributions. We open the door extending the structural causal bandit (SCB) framework to accommodate a broader class of decision-making scenarios. Our main contributions are as follows.
We first formulate a counterfactual structural causal bandit (CTF-SCB) which enables an agent to have wider range of considerations beyond Le-level interventions.
We investigate equivalence (Sec. 3.1) and partial-order (Sec. 3.2) relations among distinct actions, along with their complete graphical characterizations.
Building on these, we present an efficient algorithm for computing a refined action space in which redundant or verifiably suboptimal interventions are removed (Sec. 3.2.2).
Simulations in Sec. 4 corroborate findings. All omitted proofs are provided in Appendix F.
2 PRELIMINARIES
Following conventions, we use a capital letter, such as X, to represent a variable, with its correspond- ing lowercase letter, xr denoting a realization of the variable. Boldface is employed to represent set of variables or values, denoted by X or x. The domain of X is indicated by Dx and Dx= X xex X Dx- We consistently use P(x) as an abbreviation for P(X x). We denote by I(X = x). the indicator function. Two values x and are consistent if they share common values for X Z. We denote Z the value of X Z consistent with and by x n Z the subset of x corresponding to variables in Z.
We use structural causal model (SCM) (Pearl, 2000) as the semantic framework to represent the underlying environment in which a decision-maker (agent) is deployed. An SCM M is a quadruple (U, V V,F, where U is a set of exogenous variables determined by factors outside the model following a joint distribution P(U), and V is set of endogenous variables whose values are determined following a collection of functions F = {fv Jvev such that e + fv (pay, uy) where Pay C V (V) and Uv C U. We focus recursive SCMs (corresponding to causal diagrams that are acyclic) over V. The observational probability P(v) is defined as >n, lIve If (pay, uy) = a P()). Intervention do(x) in an SCM M creates a submodel Mx, where functions generating X are replaced with constant values x. The functions in My are denoted as Fx. Given variable X E V, the solution for X in Mw defines a potential response for a unit u, denoted as Xw (u). Averaging over the space of U, a potential response X,, (u) induces counterfactual variable Xw- We use bracketed subscripts when the variables already have index subscripts (e.g. XL,w, to XI(w.)).
This counterfactual mediator X (Raghavan and Bareinboim, 2025) fully encodes information about the variable X, and mediates how 7. perceives the value of X.
2

---

Published as a conference paper at ICLR 2026
We denote by Xw [X,[w] h== the set of counterfactual variables that share the same subscript w. Moreover, X. = {X [[]] 2|/w]::" ...) represents an arbitrary counterfactual event (a set of counterfactual variables). We denote V(X.) = [X E V Xw E X. When it causes no confusion, we abbreviate V(X.) as X. Every SCM M is associated with a causal diagram (also called a semi- Mari-varoovinn graph) g (V, E) where a directed edge V; + V3 E E if V; E ,ay, and a bidirected edge between V; and V, if Uv; and Uv, are not independent. 9[X] denotes an induced graph over X. We use kinship notation for graphical relationships: parents (Pa), children (Ch), descendants (De), and ancestors (An). Note that Pa(V)g corresponds to Pay. We denote the set of variables and edges in G by V(G) and E(G), respectively.
An SCM induces all quantities within PCH; for any Y, Y,Z.
... Z. X, W C V. the three layers of distri- butions are given by: (Observational: Lj): P(y) E, L(Y()) P()); (Interventional; C2):
P(yx) = Lu (u) = P(u); and (Counterfactual; Ly):P(yx. .... Zw) = EE = ". Zw (u) ((u). We refer the reader to Appendix B for additional background details.
3 COUNTERFACTUAL, STRUCTURAL CAUSAL BANDITS
We now formalize the counterfaciual structural causal bandit (CTF-SCB) problem where an agent interacts with a target system modeled by structural causal model (SCM) M (V, F. P(U)) including a reward variable Y E V. While traditional SCB (Lee and Bareinboim, 2018) optimizes EY² = E[ do(X = x)), we generalize this notion to EYx = E[Y do(X X.)] where X.
Arbirary counterfactual regimes within Cs
Irttial action space (Del. 1)
CTF-MIS (Sec. 3.1)
CTF-POMIS (Sec. 3.2)
Representative CTF-POMIS AA'
[Seo.3.2.2) 3.2.2)
X2(wa)).) with X, V W (Y} and W. V (Y). This operation implies that each X; E X behaves as another counterfactual variable Xi[w.] E X. (Correa and Bareinboim, 2025). In other words, the value of Xiiw. is computed in a submodel MMw and used to replace the natural mechanism fx, E F.
We aim to reduce the total action space A to a subspace A*, while ensuring ERA' S ERA.
Figure 2:
For concreteness, consider the introductory example in Fig. 1. While EY, represents the expected reward from M₁ where fx is fixed to constant x, EYw w_, Zz. represents the case where the value of W is computed in Mr while the value of Z is computed in Ma and then Y is determined within M. Note that EY, EYw.,,, holds since fixing X is equivalent making all children of X receive as their argument instead of X; thus, counterfactual regimes are more fine-graine than existing LS² regimes.
We use the terms arm, action, and intervention interchangeably. depending on the context. Throughout this paper, we assume that the causal diagram G representing M is fully accessible to the agent, although its parameterization is unknown; that is, an agent plays arms with knowledge of G and Y, but not of F and P(U). At each time step t E {1,... T., the agent interacts with a bandit instance by pulling an arm X., and subsequently observes the reward Y (i.e., Yx.)²
Definition (Action space). A total action space of CTF-SCB A is a set of counterfactual variables X., for which the corresponding reward distribution P(Yx.) ) is realizable'. That is, given a causal diagram G, an agent can interact with any SCM compatible with & and obtain rewards Yx..
Definition 2 (Counterfactual structural causal bandits). The goal of a counterfactual structural causal bandit agent is to minimize cumulative regret defined as follows:
R² = Txx:
Σ " 1=1
Σ NT(.),
X.EA
where mean reward is denoted by pxx,- Moreover, X!!) refers to the chosen arm in each round t following some strategy of the agent, and X; is an optimal arm. Ax, denotes suboptimal gap μx; px. and (X.) denotes the number of times an action X, was chosen up to round T.
*One may raise concern regarding actions hased on nested counterfactuals (Correa et al., 2021). However, any realizable nested counterfactual regimes such as [Z,rrs}i== are dominated by some action X. E A''.
which is deferred to Appendix E.4 for interested readers.
"e say that a distribution is realizable if samples can be drawn from it through a sequence of physical operations. A formal definition and background are deferred Appendix B.3.
3

---

Published as a conference paper at ICLR 2026
Corollary 1. xe = arg Dx Mx be optimal arm in Lg2. Then, Px S -X::
To provide the condition under which a counterfactual event constitutes a valid action, we introduce the notion of ancestral relation among counterfactuals (Correa et al., 2021). The set of ancestors of Xw. denoted by An (Xw), consists of each counterfactual variable T2 such that (i) T E An(X) \ W and (ii z = w 7 (n(") For a set of variables X., we define An XX. Ux EX, An(Xw) (w) For instance, given X. = [W., Zer) } in Fig. 3a, we have An( = (W. Ze ] ( ) = {W., Zz: Ze
Proposition 1. A counterfactual X, consists of CTF-SCB action space A if and only if Annn (Yx, X.) does not contain a pair of Xw: Xx of the same variable X under different regimes where w o
Proof. According to counterfactual unnesting theorem (CUT) (Correa et al., 2021):
P(YT..x, =y) =y== =E y, X2 z)),
(2)
where T. represents any combination of counterfactuals, we obtain P(yx.)= = Ex P(xx, X, =x). x). Hence, checking for conflicts (i.e., Xw, Xt An X.) with w + t) establishes the realizability of Yx, by Corollary 3.7 in Raghavan and Bareinboim (2025) (see Lem. 4 in Appendix B.3).
For concreteness, consider the causal diagram shown in Fig. 3a, Suppose an agent intends to perform X, {Wz, Zz } with * z'. In this setting, the value of 2,, is computed under a system in which W is evaluated within the submodel M2 while Z is evaluated within separate submodel Myr. However, for to listen to Wa. the mechanism fz must receive x as input, leading to Za (shown in blue). Conversely, for Y to simultaneously listen to Zz', the same mechanism fz must receive r' (shown in red). These conflicting requirements on fz render X. non- realizable, making it infeasible to sample rewards through interaction with the system; thus X, (Wa, Zu,) & A. Leveraging Prop. 1, we have An X.) = {Y==,, Wa, Ze, Z which contains conflict, i.e., the same variable Z instantiated under different subscripts x and a'. Similarly, the regime X. = =[Zw} } in Fig, 3b is also not a valid action either, since AY,Y,, X.) = (Y,, X, W,
Zzy
7
Wi
(a) X.
(W.: 7z/
(b) (. {
Figure 3: Invalid actions.
induces a conflict at X.
In contrast, consider X. (W,., Z in the introductory example (Fig. 1), which corresponds to Yw..z,, To evaluate this regime, we imput x and x' into fw and fz. respectively, thereby simulating the counterfactual behavior of both variables. Since intervention on X. { Z } does not induce any conflict, it constitutes a valid action, identified by AY, X.) = (Ywz. Wz. }-
Through the remaining parts, we first introduce equivalence relations among arms (Sec. 3.1). Next, we explore partial order over arms that characterizes "possibly optimal" arms (Sec. 3.2). Using these properties, we shrink A into subspace A allowing agents to efficiently optimize their policy without sacrificing unnecessary exploration. The schema in Fig. shows the overall flow.
3.1 COUNTERFACTUAL MINIMAL INTERVENTION SET
Although the semantics of counterfactuals permit considering any regime of the form X, [Xiw,,]i=1-invee exponential combinations of X; E V (Y} and W; C C (Y}-certal) counterfactual variables X, E X, may be irrelevant to the reward, depending on the topology of causal systems, indicating /xx, = \/x.). CTF-calculus (Correa and Bareinboim, 2025) (counterpart of do-calculus for L3) provides a set of rules for assessing such invariances within the action space. To systematically handle these equivalence relations, we first introduce key tool, interventional minimization (Correa et al., 2021).
Lemma (Interventional minimization). Let Xw be counterfactual variable, 9 causal diagram, and X2 such that z = w O An(X) sw Then, X = X2, holds for any SCM compatible with G.
This transformation is denoted as |x A XwmAn(X))ww For instance, ||aa.l = W, in Fig. by {a, } n An(W) (I, n {W, 2} = {2}. For a set of counterfactual variables X., we define |X.|| Uxmex, |Xwll.
4

---

Published as a conference paper at ICLR 2026
Definition 3 (Counterfactual minimal intervention set). A set of counterfactual variables X, sat- isfying X. = |XX || is a counterfactual minimal intervention set (CTF-MIS) there is no other counterfactuals Z, X, such that μx. = 4 for every SCM conforming to G.
In words, a CTF-MIS implies that every variable Xiww.] X. affects the reward, and it is sufficient to play only that arm among those in its equivalence class with respect to expected reward.
Theorem 1 (Graphical characterization of CTF-MIS). A counterfactual X, = (X (Xtw,he= A is CTF-MIS if and only (i) X S An and (ii) for any Xi(w.) E X., W; n An(An (n(Xi)sxxxx)) * 0.
Verbally speaking, the first condition states that for X, to be a CTF-MIS, each X; E X must have its own causal (directed) path Y; otherwise, another minimal equivalent set could be identified.
For example, consider Fig. 3a with X. = (We, Zz} A. which is nor CTF-MIS since subset { X, is equivalent to X. by the following derivation:
CUT Σ
(H Wer Zx)
R3 Σ
P Wxy 7n)
Σ y W
CUT
yous
3/10
Here, the first and last equalities follow from CUT, while the second follows from CTF-Rule 3 of CTF-calculus. Graphically, one observes that the only causal path from to Y passes through W,
implying X (W, )) E An(Y) (W,Y).
To explain the second condition, consider X, = {Xw., [..] in Fig. 3b which satisfies the first condition; namely, {_, 2} An(Y)) (X, 2}. Nevertheless, the only causal path from W to Z passes through X. This means that intervening on X,, induces Z, (i.e., w = w', otherwise violates Prop. 1), which implies that intervention X alone is sufficient, shown below:
PX,
CUT
Σ
yP(yuz Rw', Iw)
Prop.
Σ
(Puwwx Zw Iwc)
RI
Σ
yP Rrws Tw)
yes
P( 2x, Fww)
Σ
y (Max, 2z, Fwo)
Σ (( Fw)
CUT
where RI and denote CTF-Rule and CTF- 3, respectively. As a result, X. not a CTF-MIS. Remark that (W) n An (Z)s = 0 allows the application of CTF-Rule 3 in the second line and introduces the equivalence /xx. p.
Further equivalences. Surprisingly, we will show that there is additional room to extract equiv- alence relationships among counterfactuals. Specifically, although these relationships do not stem from subset inclusion, they nevertheless constitute genuine equivalence relationships.
As intuition pump, consider the causal diagram shown in Fig, 4a with two CTF-MISs X, (We, ] and Z. = (Tz, Ze' the only difference is that W listens to x in X, rather than T in Z.. We will derive pz, p.x Applying CUT and marginalization over W we have:
PT.
CUT
Σ
yP(yce te 2xr) = Σ
yP(yce twx Zw', Wz).
3.1.x
u.s.l,w
We proceed to derive as follows:
R3
y yP(yezw, bz, Zat, Wx)
[W} n An :,न.5
y yPyttswr tuz, 2x' Wx)
We tu tww
RL
g.s.L.w
R3
y (y two Re', Wz)
{X} n (T) kTw5
gus.b.a
(a) G
(b)
(P tows Ze', Wo)
(Z) An (T) 197w
g.
Figure 4: (a) Causal diagram (b) X. and Z. are equivalent, as they induce the same effect propaga- tion from x
(y taws Zar, W.).
tzw
+ Yiaw = Vaw
g.s.b,w
Summation over Tzw and then applying CUT again results in:
to Y.
yP( Lawy Zzz, Ws)
Σ
y yP( Zal, W.)
CUT
3,2,10
We refer to X. and Z. as equivalent if the equality holds. For example, X. and X || are always equivalent.
5

---

Published as a conference paper at ICLR 2026
Therefore, we find that the two CTF-MISs X. = (We, Z and Z. (T,, are equivalent. Graphically, one can observe that whether an agent performs X. or Z., the subscript x propagates to Y through W and T in the world M,, (blue in Fig. 4b), while x' propagates through Z and R. as in M2 (red). In other words, Y cannot distinguish whether the input to the functional mechanism Jy is governed by Tx or W,. Furthermore, consider CTF-MIS T. = (Tz, R which is also equivalent to X, and Z, The key point is that their propagation can be represented in the same graph (Fig. 4b). This property will serve useful role in the next section.
Remark 1. There are no equivalence relations among minimal intervention sets (MISs)* in SCB; thus, any MIS can be thought of representative set among all possible equivalence classes, but this does not hold in CTF-SCB.
3.2 COUNTERFACTUAL POSSIBLY- OPTIIMAL MINIMAL INTERVENTION SET
We now characterize partial orders among actions within CTF-MISs. Given causal diagram G, it is possible that counterfactual interventions on certain variables always perform at least as well as interventions other variables, regardless of the paramctrization of the underlying model.
To see this, consider the causal diagram G in Fig. 5a. Here, we can derive H4.- = E, E| do(2)), 2| do(=*)) = Σx MzP((x | do(=*)) I pzz and A4 = E E|y | P() S
E. Mo. P(w)= = Ykw where the superscript * denotes the best arm in the corresponding domain (i.e., " arg maX pw)) This means that both do(A) and do(2") cannot be better than the other.
Beyond partial ordering among such physical interventions over C we now consider comparisons involving counterfactual actions. Let us now select wi = arg m Dw Mw Z., this licenses Pu = Mee Zw-. S | 1 For concreteness, consider SCM with binary variables and the following mechanisms: Sw uw. Jx uz /wwSurr fx ux @ and fv 1 (uy @ @uzy @rx@ (1-w)) where all exogenous follow Bern (0.1). In this setting, we obtain A4 ~ 0.22 < 0.24 R jow with w 0, by fixing its mechanism f to constant function f/ w Meanwhile the expected reward under the counterfactual arm pw z ~ 0.88 with wi = dominates pw R 0.24.
To build more intuition, we rewrite ply WWW.. Z. and pw Z MW Z.. respectively. This highlights that the two arms differ only how the variable Z is handled; in the former, Z behaves as it would under the factual intervention w", whereas in the latter, Z behaves as if w had been applied, as shown in Fig. 5b. the hypothetical action Z. yields higher expected reward than Z the agent should prefer it; otherwise, if their outcomes coincide, w may simply be set to w². This discrepancy in how Z listens to ultimately propagates to Y, resulting in a significantly improved outcome pw- < Mkw z,t in this SCM instance.
W
(a) g
(b) fw" Zut
Figure 5: Possibly-optimal action.
Definition 4 (Counterfactual possibly-optimal intervention set). Let X, be a CTF-MIS relative to (G. Y). If there exists an SCM conforming to g such that μx: > pz: for any non-equivalent CTF-MIS Z., then X, is a counterfactual possibly-optimal minimal intervention set (CTF-POMIS).
We begin by observing a simple setting in which exogenous variables as- sociated with the reward are uncorrelated with exogenous variables of all other endogenous variables (in graphical terms, there is no bidirected edge connecting with Y). In this setting, a natural intuition is to directly intervene on the parents of Y, assigning them the values that Y most prefers to listen to. Fortunately, this leads to a desirable result. Concretely, we observe the values pay when x is intervened upon (best arm), and then mimic those values by directly intervening on Pa(Y)g. This approach guarantees ,xx. S Kpaa.
Pw(Y)g
Figure 6: Markovian
To witness, revisit the causal diagram shown in Fig. 3a, equipped with an SCM where mechanisms
are defined as fv = pay) A (A uv). and each binary exogenous U U \ Uy follows P(U 1) == E ~ 0, while U E Uy follows PU = 1) = 1- - e. In this setting, consider an arm X; = { [2,) with x = 1. We can observe that μzz, = c(1 - E). Moreover, we find P(W
Yz, 1) = 1,
indicating that directly fixing W = 1 (i.e., ) would result in a better strategy; thus, Jzz S Hpa:.
FFormal definitions of the minimal intervention set (MIS) and possibly-optimal minimal intervention set (POMIS) (Lee and Bareinhoim, 201 (0)) are provided in Appendix B.I.

---

Published as a conference paper at ICLR 2026
(a) g
(b) Z..
(c) Hr.
(d) Hn.
(c) HR.
Figure 7: (a) Causal diagram; (b-e) counterfactual regime graphs corresponding distinct CTF-MISS. The first three CTF-MISs are CTF-POMISS, whereas the last one not by IB [B(x.., Y) = {X} V.
Proposition 2. I is not confounded with An(Y)g \ (Y), then Pa(Y)g g is the only CTF-POMIS.
Corollary 2 (Markovian CTF-POMIS). ifG is Markovian, then Pa(Y)g is the only CTE-POMIS.
Therefore, in Markovian settings, agents do not need to consider counterfactual actions. Instead, However, this conclusion may no longer hold if Y
suffices to intervene on the parents confounded with variables that causally affect it. In the previous example (Fig. 5), we already observe that Paa.. 0.82 < 1w" zut indicating that interventions on the parents are suboptimal.
3.2.1 GRAPHICAL CHARACTERIZATION OF CTF-POMIS
In this section, we graphically characterize CTF-POMISs. We first introduce unobserved confounders' territory and interventional border, proposed by Lee and Bareinboim (2018). Let cc(X)s y be c-component (Tian and Pearl, 2003) containing X in G, and cc(X)g = Uxex cc(X)g.
Definition 5 fettobeerved-coffouddee set of variables T C V(H) containing Y is called a UC-territory on G with respect to Y if De(T) H T and cc(T) H = T. The UC-territory T is said to be minimal, denoted T MUCT Y), if no T & T is a UC-territory.
territory (Lee and Bareinboim, 2018)). Let = (A)()))
Definition 6 (Interventional border (Lee and Bareinboim, 2018)). Let T be a minimal UC-territory causal diagram with respect to Y. Then Pa(T)g T is called an interventional border (IB) for G with respect to Y, denoted as IB(G,Y) Y).
Minimal UC-territory represents the smallest closed set that transmits all hidden information from unobserved confounders the downstream reward, while interventional border comprises the nodes that directly influence this closed mechanism. Lee and Bareinboim (2018) demonstrated that IB Y)
X is sound and complete condition for X to be POMIS.
Counterfactual regime graph. We will show that interventional borders also fully characterize CTE-POMISS when considered with a graph specially designed to preserve causal relations among counterfactual variables of interest, called counterfactual regime graph. Given CTF-MIS X., define the counterfactual regime graph for X, as Hx. = (VT, Et) where V = V (An((Yx, X.) and E E(G[Vi)) For concreteness, consider the causal diagram G in Fig. 7a with CTF-MIS X, {W., Z J. The construction of Hx. adds nodes in V = V(An (Yx X.)) )))) = (W, Z, R, Y and connects edges among Vt inherited from the causal diagram (Fig. 7b).
The key distinction from previous graphical representations (e.g.. AMWNs (Correa and Bareinboim, 2024) or counterfactual graphs (Shpitser and Pearl, 2007)) that Hx. connects directed edges from each X; E X to 7 E Ch(Xi)g. thereby preserving the original causal relations among them, based on consistency X, = Yx Yx. RCle-Rule 1). For instance, W -> and + R appear in Hx., implying W₂ + Tw, (= Tw) and Ze' Rz Ry), while W - Tw or Ze + R. do not appear in those representations.
According to realizability (Prop. 1), whenever T2 E An(X,jwi) and T3 E An(X j(w it follows that z = S. Hence, the generating process Yx. can be written in the form a single SCM Mx. V, P(U)) where each mechanism in Fx. is modified such that, for every X/[w:] E X., the arguments W, of its downstream variables in V are fixed to w,. Therefore, this construction mirrors the way in which the value of Yx, is determined.
7

---

Published as a conference paper at ICLR 2026
Algorithm 1: Algorithm enumerating all representative CTR-POMISs (simple version)
Input: Causal diagram G; and a reward variable
Output: All representative CTF-POMISS with respect to (G, Y)
Set H (Y))
for each children choice
E (y ( 20b > do
Generate map pa[X] {W Xw [S Pa(X) n) for all E V(H).
if IB("',, Y = 0 where H (VHH),(HH) { + X VX V(H), MA E pa(X]})
then
Let X, == (X2 X E UWEW } where = UTEAn(X)
pa pT[
Compute X = CTE-MISIFY (G. X..
yield X if An X.) satisfies Prop.
function CTF-MISIFY(,, X.,
Set X v
10
return (Xilw,) E X, Xj E X and W, O An())) ( ,x11,,))
Corollary 3. Given a CTF-MIS X,, the counterfactual regime graph Hxx is a subgraph of the causal diagram compatible with Mx. over V1.
For example, consider a CTF-MIS X. (T₂} shown in Fig. 7c. Under an action for X., the original mechanism (X, Uw) F is replaced by fw (w, Uw) ) fy (W)) in Mx.- This implies that it no longer a function of X. Similarly, the CTF-MIS X. = [R [ in Fig. 7 operates analogously-thh original mechanism (x, Uz) F is replaced by fz Uz) (2z in
Mx.. We are now ready to characterize CTT-POMIS using the rich graphical structure.
Theorem 2 (Graphical characterization of CTF-POMIS). CTF-MIS X. with respect (G, Y) is CTE-POMIS if and only if IB(x, Y) = holds.
To witness, revisit the CTF-MIS X. (Wz, Zz'} } and its counterfactual regime graph in Fig. 7b. We begin by constructing a minimal UC-terriory T in Hx, By construction, Hx. = 7xx. (Ax)) always holds. Starting from = {YY, we observe cc(Y) = {Y, R, Z, W): thus, we update T to (Y, R, Z, W). Including all their descendants yields T (Y, R, Z, W, T). Since there are no further unobserved confounders between T and An(Y) T, we obtain MUCT(Hx., Y) (Y, R, Z, W, T3 along with ( Y) = 0. Therefore, X. qualifies as a CTE-POMIS. Likewise, the CTS-MISs Figs. 7c and 7d can also be verified as CTF-POMISs.
In contrast, consider the CTF-MIS X, = { } in Fig. 7e, which is not a CTF-POMIS. In this example, IB(Hx. Y)= {X} # @ entails that an intervention on X. U {W*} yields no worse and possibly better outcomes.
( R, W). and adding their descendants results in T {W, T, Y). Since there are no additional unobserved confounders between T and AY(Y) ( Hx. \ T, we obtain IB(Hx., Y) {X}. which violates the condition for being a CTF-POMIS.
Initializing with T (Y) gives HY) (Y,
Indeed, IB(Hx, y) {X) implies EYx = Σ. E(yx. xr] P(x) = Σ. EYx, P(x) S
EY EY(x.,
w. (X.....)
and thus X, is not CTF-POMIS with respect to (G, Y)
3.2.2 ALGORITHMIC APPROACH: ENUMERATING REPRESENTATIVE CTE-POMISS
Identifying all realizable actions through Prop. I over arbitrary counterfactual events, and subsequently verifying whether each constitutes CTF-MIS and a CTF-POMIS action computationally prohibitive, which grows super-exponentiall) with the number of nodes. To circumvent this, first identify counterfactuals of the form (x)))a(x))))ee Notably, each such counterfactual can represent dozens of equivalent CTP-(PO)MISs, and collectively they cover A", which is verified by the following proposition.
that satisfy the CTF-POMIS conditions (Thm. 2).
Proposition 3 (Existence of equivalent action). For any CTF-(PO)MIS Z, for (G,Y), there exists equivalent action X. [x]w/]i== C An(Z.) satisfying X C W U CUChC)) where W U, W,
8

---

Published as a conference paper at ICLR 2026
CTAROSIS
CYPPOMIE
CITMBS
CITIRS
POSBS
POMES
1000
(a) Task 1
(b) Task 2
(c) Task 3
Figure& 8: Cumulative regrets for the corresponding KL-UCB (solid) and TS (dashed) under distinct strategies. We plot the average cumulative regrets along with their standard deviations.
To see this, consider again Fig. 4a. We observed that X, = { x. Za') equivalent Z., which satisfies X [W,Z} S [X, W, 2) W U C..)g. Recall that Hx. =\t Hz.. as they share the same effect propagation (Fig. 4b). Thus, it suffices to test whether X. a CTF-POMIS; other equivalent counterfactuals are no longer needed and can be safely discarded. We refer to such X, representative CTF-POMIS.
W.. Z
Theorem 3. The Algorithm I returns all and only representative CTE-POMISs given (G, Y)-
Building on this, Algo. enumerates all representative CTF-POMISs via an edge-selection approach. which runs in O(n² 21 For concreteness, consider the causal diagram in Fig. 3b where g = gg)) (line 1). With the children choices pal [ = {7] and pa[X] X] {W} among each power set over children, let H' be the subgraph obtained by removing the selected edges T - Z and W + X from G. In lines 4-5, since IB(H', Y) = 9, we construct X. = {zzw> X.r) from pa = {T} and pa[X] = (W} where the subscript w in Ztw induced by the realizability condition, i.e., W E An ( gro and H' Hx. holds (further theoretical explanation provided in Appendices E.2 and E.3).
In line 6, the algorithm calls subroutine CTF-MISIFY, which modifies the counterfactual so that it satisfies the two conditions of CTF-MIS (Thm. 1) as follows: given (g, Y) with a counterfactual X, ( fi (i) remove Xj[w; X, if X; & An(Y) and (ii) remove if W, AA((X))Xx1X)) O. Since X. = (Zr X satisfies the two conditions, it follows that X = X., Then, since there is no conflict in Ay X.) = {Yzu, Zew: X J. X', constitutes valid form by Prop. 1, and is therefore returned. More detail is presented as Algo. 2 in Appendix E.3.
4 EXPERIMENTS
We evaluate the cumulative regret (CR) of CTF-SCB under different strategies to assess the effect of employing representative CTF-POMIS. Hereafter, we omit the term representative for brevity. The number of trials is set to 10k for the first two tasks and 100k for the last one, which is sufficient to observe performance differences. Each simulation is repeated 1,000 times to ensure consistency of results. We compare three arm-selection strategies- CTC--CCT--PPPP CTT-MISSS (pink in Fig. 8), CTF-MISs (purple), and POMISs (green)eech combined with two prominent solvers: Thompson Sampling (TS) and KL-UCB Details of the bandit mechanisms and settings can be found in Appendix C.
Task 1. We compared CTF-MIS and CTE-POMIS for the causal diagram in Fig. 5a. The CTF-POMIS based TS and KL-UCB achieve CRs of 66.69 and 19, which correspond to CR for CTF POMIS Co MTF-MIS x 38.92% and 38.96% respec- tively. Since the number of arms for POMIS is smaller than A POMIS may suffer less from exploration and thus temporarily achieve a smaller CR than CTF- (PO)MIS; nevertheless, CTF-(POJMIS ultimately prevails, depicted in Fig. 8a.
Task 2. We consider the causal diagram in Fig. 3b. Using the three strategies,
Figure
the CTF-POMIS based TS and KI-UUCB achieve CRs of 387.01 and 831.24, 24, which correspond to 57.46% and 70.17%, respectively, of CR for CTF-MIS. As shown in Fig. 8b, CTF-(PO)MIS consistently outperformed POMIS.
We apply standard bandit solvers to A' which enjoy wetllestablished finite-time regret guarantecs order Oxx. (x..ett loxT) (Lattimore and Szepesvári, 2020).

---

Published as a conference paper at ICLR 2026
We evaluate CRs with the causal diagram in Fig. 9 in more involved scenarios where (i) the optimal action is not contained in POMIS, as in the previous tasks (Fig, 8c, left), and (ii) the optimal action lies in Ls² (right). In the first case, the CR for POMIS suffers linear regret due to the strictly positive gap Agga - μx; Ux O. When X lies in Ls2 (i.e., Acg. 0)-a special case that does not undermine our theoretical results, since the deployed agent can never be certain prior to interaction whether the optimal arm lies in L<z the smaller action space allows POMIS to converge faster than the others. All CRs and the numbers of sets and arms are provided in Tables I and 2 in Appendix C.
Task 3.
LIMITATIONS
Modeling bandit instances in the form of SCMs. SCMs are versatile and expressive framework that provides a principled way to represent and reason about causal relationships. Their generality makes them applicable across a wide range of domains. However, SCMs come with certain limitations, such as the assumption of well-defined set of variables and fixed causal structure, which may not adequately capture the complexity of dynamic, high-dimensional, or partially observed systems. Nonetheless, our work addresses a fundamental problem within the SCM framework. We believe provides a solid foundation for future research, such as extending causal bandits to more complex or less structured environments.
Ability to perform counterfactual actions. A key limitation of our work lies in the assumption that the deployed agent can execute any action corresponding to realizable counterfactual distributions P(Yx.). ). This assumption implicitly requires the identification of suitable counterfactual mediators. While our results provide a rigorous theoretical foundation, the practicality of this assumption limited, real- world environments may constrain both the realizability of such operations and the construction of appropriate counterfactual mediators due to ethical, safety, or technical considerations.
Known causal diagram. We make the standard assumption that the deployment learner has access to the underlying causal diagram. While knowledge of the causal structure can greatly enhance decision-making this requirement may limit the broader applicability of the proposed approach. In practice, though several techniques suruuessss-uhhheeeee such as causal discovery methods or the use of ancestral graphs help alleviate this issue, these techniques typically require substantial
as plausible explanations domain knowledge or precise conditional independence (CI) statements, and thus, the assumption remains key limitation of our framework. However, some degree of misspecification can be tolerated without invalidating the performance guarantess-particulaaty when the assumedd causal diagram forms super-model of the true environment. Suppose that the true environment compatible with the causal diagram g ([X, Y), {X -> Y}). If we are unsure about the presence of an unobserved confounder, we can conservatively posit a super-model g' ({X,
(XXYY, Y), (X Y, V.X X + Y7). Then, a collection of CTE-POMIS under G is {{X*)), while under G' it becomes {0, (Xa)). which covers the true CTE-POMIS. This leads to less informative but still correct inferences, outperforming methods that ignore structural information altogether. In contrast, misspecifying in the opposite direction can lead to incorrect inferences. This reflects a fundamental asymmetry: being conservative preserves soundness, but missing edges can violate correctness.
6 CONCLUSION
In this work, we have extended the structural causal bandit (SCB) framework by incorporating realizable counterfactual regimes into the agent's 's action space. We introduced the notions of coun- terfactual minimal intervention sets (CTF-MIS) with its conditions (Thm. 1), and possibly-optimal minimal intervention sets (CTF-POMIS) to systematically prune suboptimal actions. By leverag- ing counterfactual regime graphs-special graphical representations that preserve consistent causal relations-we developed a characterization of these sets (Thm. 2). Taken together, we developed an efficient algorithm (Algo. 1) which completely enumerates all non-redundant CTF-POMISs relative to the reward in an edge-selection manner (Thm. 3). We believe this work opens new research avenue at the intersection of causal inference, decision theory, and online learning, inviting further exploration of counterfactual causal bandit algorithms in both theoretical and practical domains.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank anonymous reviewers for constructive comments improve the manuscript. This work was partly supported by the IITP (RS-2022-112205553330) and NRF (RS-2023-0021119477066 grant grant funded by the Korean government.
REFERENCES
Virginia Aglietti, Xiaoyu Lu, Andrei Paleyes, and Javier González. Causal Bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 3155-3164. PMLR, 2020.
Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39, 1-39226.... JMLR Workshop and Conference Proceedings, 2012.
Chen Avin, llya Shpitser, and Judea Pearl. Identifiability of path effects. In Proceedings of the Nineteenth International Joint Conference Artificial Intelligence, pages 357-363, 2005. 2005.
Alexander Balke and Judea Pearl. Probabilistic evaluation of counterfactual queries. In Probabilistic and Causal Inference: The Works of Judea Pearl, pages 237-254. Association for Computing Machinery, 1994.
Elias Bareinboim and Judea Pearl. Transportability of causal effects: Completeness results. In Proceedings of the 26th AAAI Conference on Artificial Intelligence, pages 698-704, 2012.
Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27):7345-7335) 2016.
Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: A causal approach. In Proceedings of the 28th Annual Conference on Neural Information Processing Systems, pages 1342-1350, 2015.
Elias Bareinboim, Juan D Correa, Duligur lbeling, and Thomas Icard. On Pearl's hierarchy and the foundations of causal inference. Technical Report R-60. Causal Artificial Intelligence Laboratory, Columbia University, 2020.
Elias Bareinboim, Juan D Correa, Duligur lbeling, and Thomas Icard. On Pearl's hierarchy and the foundations of causal inference. Probabilistic and causal inference: the works of judea pearl, pages 507-556. 2022.
Elias Bareinboim, Sanghack Lee, and Junzhe Zhang. An introduction to causal reinforcement learning. Technical Report R-65, Causal Artificial Intelligence Lab, Columbia University, Dec 2024. URL https: causalaisaaaa.aaaa net /ree:/665. pdf.
Alexis Bellot, Alan Malek, and Silvia Chiappa. Transportability for bandits with data from different environments. Advances in Neural Information Processing Systems, 36:44356-44381 2023.
Marianne Bertrand and Sendhil Mullainathan. Are Emily and Greg more employable than Lakisha and Jamal? a field experiment on labor market discrimination. American economic review, 94(4): 991-1013, 2004.
Shriya Bhatija, Paul- David Zuercher, Jakob Thumm, and Thomas Bohné. Multi-objective causal Bayesian optimization. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 4172-4195, PMLR, 13-19 Jul 2025. URL https: https://proceeiian /pt.eeedooccee...coooooo mlr.
press Press/v266 v htt///hatii/ intaaijja2 ja25a html.
Blair Bilodeau, Linbo Wang, and Dan Roy. Adaptively exploiting d-separators with causal bandits. Advances in Neural Information Processing Systems, 15:20381-20392. 2022.
Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-leible upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pages 1516-1541, 2013.
11

---

Published as a conference paper at ICLR 2026
Ryan Carey, Sanghack Lee, and Robin J Evans. Toward complete criterion for value of information in insoluble decision problems. Transactions on Machine Learning Research, 2024.
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. Advances Neural Information Processing Systems, 24, 2011.
Silvia Chiappa. Path-specific counterfactual fairness. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7801-7808, 2019.
Juan Correa, Sanghack Lee, and Elias Bareinboim. Nested counterfactual identification from arbitrary surrogate experiments. Advances in Neural Information Processing Systems, 34, 2021.
Juan D Correa and Elias Bareinboim. Counterfactual graphical models: Constraints and inference. Technical report, Technical Report R-115, Causal Artificial Intelligence Lab, Columbia University, 2024.
Juan D Correa and Elias Bareinboim. Counterfactual graphical models: Constraints and inference. In Forty-second International Conference on Machine Learning, 2025.
Arnoud De Kroon, Joris Mooij, and Danielle Belgrave. Causal bandits without prior knowledge using separating sets. In Conference on Causal Learning and Reasoning, pages 407-427, PMLR, 2022.
Wen-Bo Du, Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Avoiding undesired future with minimal cost in non-stationary environments. Advances in Neural Information Processing Systems, 37: 135741-135769, 2024.
Wen-Bo Du, Hao-Yi Lei, Lue Tao, Tian-Zuo Wang, and Zhi-Hua Zhou. Enabling optimal decisions in rehearsal learning under CARE condition. In Forty-second International Conference on Machine Learning, 2025a. URL https: http::/ss///ppeeeee..... att.://www..tttooou/d/aaaa----- SLLC..
Wen-Bo Du, Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Variance-reduced long-term rehearsal learning with quadratic programming reformulation. The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025b. URL https: http:////opppeeveeeeeeeee net forum?
1d=3m02vOFYpB.
Muhammad Qasim Elahi, Mahsa Ghasemi, and Murat Kocaoglu. Partial structure discovery is sufficient for no-regret learning in causal bandits. Advances in Neural Information Processing Systems, 17:109066-109100, 2024.
Tom Everitt, Ryan Carey, Eric D Langlois, Pedro A Ortega, and Shane Legg. Agent incentives: A causal perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11487-11495, 2021.
Helmut Farbmacher, Martin Huber, Lukáš Lafférs, Henrika Langen, and Martin Spindler. Causal mediation analysis with double machine learning. The Econometrics Journal, 25(2):277-300, 2022.
Shi Feng and Wei Chen. Combinatorial causal bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7550-7558, 2023.
Shi Feng, Nuoya Xiong, and Wei Chen. Combinatorial causal bandits without graph skeleton. In Vu Nguyen and Hsuan-Tien Lin, editors, Proceedings of the 16th Asian Conference Machine Learning, volume 260 of Proceedings of Machine Learning Research, pages 27 1-266.. PMLR, 05-08 Dec 2025. URL httph::t//// http:://ppocceeeee
walr.press.e. /22 w0 25ng252nn.. html.
Ronald A. Fisher. The Design of Experiments, Oliver & Boyd, Edinburgh, edition, 1935.
Andrew Forney and Elias Bareinboim. Counterfactual randomization: rescuing experimental studies from obscured confounding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1454-2461 2019.
12

---

Published as a conference paper at ICLR 2026
Andrew Forney, Judea Pearl, and Elias Bareinboim. Counterfactual data-fusion for online reinforee- ment learners. In Doina Precup and Yee Whye Teh, editors. Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pages 166. PMLR, 06-11 Aug 2017. URL https: httptttt////orceed ngg. ml press/ 777/forney178 html.
Aurélien Garivier and Olivier Cappé. The ki-uch algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
James Heckman and Richard Robb Jr. Alternative methods for evaluating the impact of interventions: An overview. Journal of econometrics, 30(122) 267, 1985.
James J Heckman and Richard Robb Jr. Alternative methods for solving the problem of selection bias in evaluating the impact of treatments outcomes. Drawing Inferences from Self-Selected Samples, pages 63-107, 1986.
Inwoo Hwang. Yunhyeok Kwak, Suhyung Choi, Byoung- Tak Zhang, and Sanghack Lee. Fine-grained causal dynamics learning with quantization for improving robustness in reinforcement learning. In International Conference Machine Learning, pages 20842-20877 PMLR, 2024.
Byoung-Tak
Duligur lbeling and Thomas Ieard. Probabilistic reasoning across the causal hierarchy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10170-10177, 2020.
Kosuke Imai, Luke Keele, and Teppei Yamamoto. Identification, inference and sensitivity analysis for causal mediation effects. Statisticul Science, 25(1):51-71, 2010.
Kosuke Imai, Luke Keele, Dustin Tingley, and Teppei Yamamoto. Unpacking the black box of causal- ity: Learning about causal mechanisms from experimental and observational studies. American Political Science Review, 105(4):765-77) -899,,777777 2011.
Kasra Jalaldoust, Alexis Bellot, and Elias Bareinboim. Partial transportabilityy for domain gener- alization. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024.
Yonghan Jung, Min Woo Park, and Sanghack Lee. Complete graphical criterion for sequential covariate adjustment in causal inference. Advances in Neural Information Processing Systems, 37: 19813-19838, 2024.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
Mikhail Konobeev, Jalal Etesami, and Negar Kiyavash. Causal bandits without graph learning. In Bi- wei Huang and Mathias Drton, editors, Proceedings of the Fourth Conference on Causal Learning and Reasoning, volume 275 of Proceedings of Machine Learning Research, pages 31 21-63. PMLR, 07-09 May 2025. URL https: http:///poeeeeng.meeeee. mlr. press /
html.
Daniel Kumor, Junzhe Zhang, and Elias Bareinboim. Sequential causal imitation learning with unobserved confounders. Advances in Neural Information Processing Systems, 34:14669-14680, 2021.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematies, 6(1):4 22, 1985.
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: causal inference. Advances in neural information processing systems, 29, 2016.
Learning good interventions via
Tor Lattimore and Csaba Szepesvári. Bandit algorithmss. Cambridge University Press, 2020.
Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? Advances in
Neural Information Processing Systems, 31, 2018.
13

---

Published as a conference paper at ICLR 2026
Sanghack Lee and Elias Bareinboim. Structural causal bandits with mon-manipulable variables. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4164 4172, 2019.
Sanghack Lee and Elias Bareinboim. Characterizing optimal mixed policies: Where to intervene and what to observe. Advances in Neural Information Processing Systems, 53:8565-85777 2020.
Sanghack Lee, Juan D Correa, and Elias Bareinboim. General identifiability with arbitrary surrogate experiments. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2019.
Ang Li and Judea Pearl. Unit selection based counterfactual logic. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019.
Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit prob- lems with causal background knowledge. In Conference on Uncertainty Artificial Intelligence, pages 141-150 PMLR, 2020.
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. Advances in Neural Information Processing Systems, 34:24817-24828 2021.
Alan Malek, Virginia Aglietti, and Silvia Chiappa. Additive causal bandits with unknown graph. In PMLR, 2023.
International Conference Machine Learning, pages
Caleb H Miles, Ilya Shpitser, Phyllis Kanki, Seema Meloni, and Eric J Tchetgee Tchetgen. On semi- parametric estimation of a path-specific effect in the presence of mediator-outcome confounding. Biometrika, (07(1))159-177) 2020.
Scott Mueller and Judea Pearl. Personalized decision making-a conceptual introduction. Journal of Causal Inference, 11(1):0022050, 2023.
Scott Mueller and Judea Pearl. Perspective on 'harm'in personalized medicine-an alternative perspective. Technical report, 2024.
Min Woo Park and Sanghack Lee. On transportability for structural causal bandits. arXiv preprint arXiv:25/1.17953 2025.
Min Woo Park, Andy Arditi, Elias Bareinboim, and Sanghack Lee. Structural causal bandits under Markov equivalence. Advances in Neural Information Processing Systems, 38, 2025.
Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-710, 1995.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, 2000. 2nd edition, 2009.
Judea Pearl. Direct and indirect effects. Probabilistic and Causal Inference: The Works of Judea Pearl. page 373, 2001.
Judea Pearl and Elias Bareinboim. Transportability of causal and statistical relations: formal approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pages 247-254, 2011.
Judea Pearl and Dana Mackenzie. The book of why: the new science of cause and effect. Basic Books, 2018.
Judea Pearl and James Robins. Probabilistic evaluation of sequential plans from causal models with hidden variables. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence, pages 444-453, 1995.
Judea Pearl, Madelyn Glymour, and Nicholas P Jewell. Causal inference in statistics: primer. John Wiley & Sons, 2016.
Nathan Peiffer- Peiffer-Smadja, Timothy Miles Rawson, Raheelah Ahmad, Albert Buchard, P Georgiou, F-X Leseure, Gabriel Birgand, and Alison Helen Holmes. Machine learning for clinical decision support in infectious diseases: a narrative review current applications. Clinical Microbiology and Infection, 26(5):584-50) 595, 2020.
14

---

Published as a conference paper at ICLR 2026
Drago Plecko and Elias Bareinboim. Causal fairness analysis. arXiv preprint arXiv:2207.11383 2022.
Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Rehearsal learning for avoiding undesired future. Advances in Neural Information Processing Systems, 36:80517-805444 2023.
Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Gradient-based nonlinear rehearsal learning with mul- tivariate alterations. Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 26859-26867, 2025.
Arvind Raghavan and Elias Bareinboim. Counterfactual realizability. In The Thirteenth International Conference on Learning Representations, 2025.
Thomas Richardson and Peter Spirtes. Ancestral graph Markov models. The Annals of Statistics, 30 (4):962-1053) 1030, 2002.
Thomas S Richardson and James M Robins. Single world intervention graphs (swigs): A unification of the counterfactual and graphical approaches to causality. Center for the Statistics and the Social Sciences, University of Washington Series. Working Paper, 128(30):2013, 2013.
Jonathan Richens and Tom Everitt. Robust agents learn causal world models. In The Twelfth International Conference on Learning Representations, 2024. URL
net/ piet/fose wtru//ormmi//o 2
Jonathan Richens, Tom Everitt, and David Abel. General agents need world models. In Forty-second International Conference Machine Learning, 2025. URL https://openzeree/ forum? -idd-idddll TounNixt.
Herbert Robbins. Some aspects the sequential design of experiments. Bull. Amer. Math. Soc., 58 (5):527-535, 1952.
James M Robins, Thomas S Richardson, and Ilya Shpitser. An interventionist approach to mediation analysis. In Probabilistic and causal inference: the works of Judea Pearl, pages 713-764. 2022.
Kangrui Ruan, Junzhe Zhang, Xuan Di, and Elias Bareinboim. Causal imitation for markov decision processes: A partial identification approach. Advances in Neural Information Processing Systems, 37:87592-87620, 2024.
Donald B Rubin. Direct and indirect causal effects via potential outcomes. Scandinavian Journal of Statistics, 31(2):161-170, 2004.
Ilya Shpitser. Counterfactual graphical models for longitudinal mediation analysis with unobserved confounding. Cognitive science, 37(6):1011-1035, 2013.
Ilya Shpitser and Judea Pearl. What counterfactuals can be tested. In 23rd Conference on Uncertainty in Artificial Intelligence, UAI 2007, pages 352-359, 2007.
Ilya Shpitser and Eric Tchetgen Tchetgen. Causal inference with graphical hierarchy of interventions. Annals of statistics, 44(6):2433, 2016.
Ilya Shpitser, Thomas S Richardson, and James M Robins. Multivariate counterfactual systems and causal graphical models. In Probabilistic and causal inference: The works of Judea Pearl, pages 813-852. 2022.
Lue Tao, Tian-Zuo Wang. Yuan Jiang, and Zhi-Hua Zhou. Avoiding undesired future with sequen- tial decisions. In Proceedings of the Thirty- Fourthh International Joint Conference on Artificial Intelligence (IJCAI), pages 6245-6253, 09 2025. doi: 10.24963/ijcai.22255659
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-22 2944, 1933.
Jin Tian and Judea Pearl. On the identification causal effects. Technical Report R-290-L, 2003.
Tyler VanderWeele and Mirjam Knol. A tutorial on interaction. Epidemiologic methods, 3(1): 33-72, 2014.
15

---

Published as a conference paper at ICLR 2026
Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Causal bandits for linear structural equation models. Journal of Machine Learning Research, 24(297):1-59, 2023.
Lai Wei, Muhammad Qasim Elahi, Mahsa Ghasemi, and Murat Kocaoglu. Approximate alloca- tion matching for structural causal bandits with unobserved confounders. Advances in Neural Information Processing Systems, 36:68810 10-68832, 2023.
Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Bareinboim. The causal-neural connection: Expressiveness, learnability, and inference. Advances in Neural Information Processing Systems, 34, 2021.
Kevin Muyuan Xia, Yushu Pan, and Elias Bareinboim. Neural causal models for counterfactual iden- tification and estimation. In The Eleventh International Conference on Learning Representations, 2023.
Zirui Yan and Ali Tajer. Linear causal bandits: Unknown graph and soft interventions. Advances in Neural Information Processing Systems, 37:23939-233887 2024.
Hongshuo Yang and Elias Bareinboim. A hierarchy of graphical models for counterfactual inferences. Advances in Neural Information Processing Systems, 38, 2025.
Jiji Zhang. On the completeness orientation rules for causal discovery in the presence of latent
confounders and selection bias. Artificial Intelligence, 172(16):1873-188) 1896, 2008. ISSN 0004-3702. doi: https://doi.org org/ 200.1//ttttttt.ttt0...o.ooo 08 0000 URL https: / www. sc enced rect.. 008.
com/ http:///eeeee/eereeeee//////////
Junzhe Zhang and Elias Bareinboim. Transfer learning in multi-armed bandit: causal approach. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 1778-1780, 2017.
Junzhe Zhang and Elias Bareinboim. Fairness in decision-making-ttie the causal explanation formula. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Junzhe Zhang and Elias Bareinboim. Near-optimal reinforcement learning in dynamic treatment regimes. Advances in Neural Information Processing Systems, 32, 2019.
Junzhe Zhang and Elias Bareinboim. Designing optimal dynamic treatment regimes: A causal reinforcement learning approach. In International conference on machine learning, pages 11012- 11022. PMLR, 2020.
Junzhe Zhang and Elias Barcinboim. Online reinforcement learning for mixed policy scopes. Advances in Neural Information Processing Systems, 35:3191-3202, 2022.
Junzhe Zhang and Elias Bareinboim. Eligibility traces for confounding robust off-policy evaluation. OpenReview preprint, 2024.
Junzhe Zhang, Daniel Kumor, and Elias Bareinboim. Causal imitation learning with unobserved 2020.
confounders. Advances in Neural Information Processing Systems,
Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. International conference on machine learning, pages 26548-26558. PMLR, 2022.
Kevin Zhang, Yonghan Jung, Divyat Mahajan, Karthikeyan Shanmugam, and Shalmali Joshi. Path- specific effects for pulse-oximetry guided decisions in critical care. Advances in Neural Information Processing Systems, 38, 2025.
16

---

Published as a conference paper at ICLR 2026
CONTENTS
1
Introduction
Preliminaries
3
Counterfactual Structural Causal Bandits
3.1 Counterfactual Minimal Intervention Set
3.2
Counterfactual Possibly-Optimal Minimal Intervention Set
3.2.1
Graphical Characterization of CTF-POMIS
3.2.2
Algorithmic Approach: Enumerating Representative CTF-POMISS
4 Experiments
5 Limitations
10
6 Conclusion
10
Related Works
18
Backgrounds
19
B.1 Structural Causal Bandits
B.2 Counterfactual Calculus..
22
B.3 Realizability
23
C Experimental Details
24
D Discussions
26
E Technical Details
26
E.1 Counterfactual Action
26
E.2 Graphical Constraint Induced by Realizability
27
E.3
Algorithm Details
28
E,4 Nested Counterfactual Regimes
29
Omitted Proofs
30
F.1
Proof of Theorem
30
F.2 Proof of Proposition and Corollary
32
F3 Proof of Proposition 3
33
F.4
Proof of Corollary 3
34
F55 Proof of Theorem 2 and Corollary
34
F66
Proof of Proposition 3
37
17

---

Published as a conference paper at ICLR 2026
COUNTERFACTUAL STRUCTURAL CAUSAL BANDITS (APPENDIX)
A RELATED WORKS
Causal decision making. Integrating causal knowledge into a decision- makinn process enables an agent to model decision problems with abundant dependency structures (Zhang and Bareinboim, 2019; 2020; Zhang et al., 2020; Kumor et al., 2021; Zhang and Barcinboim, 2022; Ruan et al., 2024; Zhang and Bareinboim, 2024; Richens and Everitt, 2024; Richens et al., 2025), where structural causal models (SCMs) (Pearl, 2000) have been employed to represent causal relationships among actions, rewards, and other relevant factors such as context and states. This approach allows agents to make informed decisions by explicitly considering the causal pathways through which each action affects the reward (Mueller and Pearl, 2023; Bareinboim et al., 2024).
The integration of causal inference into multi-armed bandit (MAB) framework (Robbins, 1952; Lai and Robbins, 1985; Lattimore and Szepesvári, 2020) has opened new avenues for modeling and solving decision problems with richer dependency structures. Existing studies (Bareinboim et al., 2015; Lattimore et al., 2016; Forney et al., 2017) have shown that causality-awan strategies can significantly outperform MAB algorithms that do not account for such underlying causal relationships. Subsequent work has explored various specialized settings by introducing additional structural assumptions, such as the availability of both observational and experimental distributions, or linear mechanisms (Zhang and Bareinboim, 2017: Lu et al., 2020; Bilodeau et al., 2022; De Kroon et al.. 2022; Feng and Chen, 2023; Varici al., 2023).
Lu et al. (2021) were the first to study causal bandits without assuming access to the full causal diagram. Their approach targets an atomic setting in which reward variable has only single parent, reducing the problem identifying that parent for optimal intervention. They further assume that the agent observes instead the skeleton of the true causal diagram. Extending this line of work, Konobeev et al. (2025) eliminated the need for prior knowledge the graph skeleton. However, their setting remains restricted to the same atomic case. More recently, Feng al. (2025) considered causal bandits in which each action corresponds to an intervention on a set of variables. Yan and Tajer (2024) considered actions as soft interventions on variables, i.e., changing the conditional distribution P(v] pay) to Q( p.y)). Despite this generalization, all these approaches assumed causal sufficiency and thus do not account for the presence of latent variables. Malek et al. (2023) provided some results for settings with unknown graph structures, the authors initially highlight the challenge posed by the exponentially large number of arms in causal bandit problems under unknown graphs, and assumed that no confounding exists between the reward variable and its ancestors.
Structural causal bandits. Lee and Bareinboim (2018) formalized structural causal bundit (SCB) framework, in which a bandit instance is structured by an SCM, and each action corresponds to an intervention on a subset of variables. They proposed a sound and complete graphical characterization to identify minimal intervention sets (MISs) and possibly-optimal minimal intervention sets (POMISs), where the former includes only the variables that affect the reward, and the latter refers to actions that could be part of an optimal strategy among MISs, thereby guiding the agent to avoid unnecessary exploration, without any actual interaction. Lee and Bareinboim (2019) extended this approach to accommodate scenarios involving mon-manipulable variables among all the variables in the graph.
Lee and Bareinboim (2020) established the framework under stochastic policies and demonstrated the informativeness of such policies. Everitt al. (2021) and Carey al. (2024) further investigated the completeness of the graphical characterization of optimal policy spaces, although the general completeness remains an open problem. Wei et al. (2023) proposed parameterization-baase approach to incorporate shared information among possibly-optimal actions. Elahi et al. (2024) extended the SCB to settings where causal diagram is assumed to be accessible, requiring their algorithm to
18

---

Published as a conference paper at ICLR 2026
perform causal discovvery-ice constructing the causal structure- during online interaction. Building on this line of work, causal Bayesian optimization (CBO; Aglietti et al. (2020)) leveraged the systematic characterization of MIS and POMIS for structural pruning in continuous action spaces, and Bhatija et al. (2025) extended it multi-outcomme variant incorporating Pareto optimality. Park et al. (2025) investigated SCB in settings where the available information does not constitute full partial ancestral graph (Richardson and Spirtes, 2002; Zhang, 2008) representing the Markov equivalence class of the true causal diagram, and Park and Lee (2025) focused on the transportability (Pearl and Bareinboim, 2011; I; Bareinboim and Pearl, 2012; 2016) of SCB.
Counterfactual bandits. Counterfactual reasoning plays vital role in decision-making construct- ing explanations for decisions in applications (Mueller and Pearl, 2024; Li and Pearl, 2019), analyzing a causal effect into direct and indirect pathways (Pearl, 2001; Rubin, 2004).
Beyond factual actions, Bareinboim al. (2015) and Forny et al. (2017) proposed MAB strategies aiming optimize [Y,,, x²], which go beyond interventional studies by incorporating the agent's natural intention-the agent's 's initially intended arm choice at each round prior to the final choice-as part of the decision-making evidence. Building on this idea, Raghavan and Bareinboim (2025) proposed bandit strategy that leverages additional evidence in the form of E[,,, x', = The established studies focused on extracting evidence about agents' intentions and using this information as context, which constitutes the most distinctive aspect of our work.
Path-specific effects. Path-specific effects (Pearl, 2001) constitute a broad class of causal effects that measure the influence of a treatment on an outcome through specific causal pathways. For example, Total Effect (TE) captures the influence transmitted through all causal paths connecting the treatment and the outcome (Pearl, 2000). In the presence of mediators, contemporary research on path-specific analysis (Zhang and Bareinboim, 2018; Chiappa, 2019; Miles et al., 2020; Plecko and Bareinboim, 2022; Farbmacher et al., 2022; Zhang et al., 2025) has broadened its scope to investigate effects transmitted along particular paths using counterfactuals, such as Natural Direct Effeet (NDE) and Natural Indirect Effect (NIE) (Pearl, 2001; Imai et al., 2010; 2011; VanderWeele and Knol, 2014).
While our work is related to the original idea of path-specific of certain nodes, also known as edge intervention (Shpitser and Tchetgen, 2016; Pearl al., 2016; 6; Robins et al., 2022)-ourr our focus is fundamentally different. Rather than disentangling which specific paths contribute to the rewards and to what extent, we aim to develop optimized strategies for maximizing or minimizing regret in its entirety.
on perception
Graphical representations for counterfactual inference. Balke and Pearl (1994) introduced a graphical construction that represents two "worlds" within single graph, known as twin network. Avin et al. (2005) later presented parallel networks, generalization of the twin networks to multi- world settings. However, d-separation criterion (Pearl, 1995) is sound but not complete for parallel networks, as they include more variables with deterministic relationships among them. Shpitser and Pearl (2007) proposed algorithm for merging nodes in parallel network under specific variable instantiations, resulting in what is referred to as the counterfactual graph, which is conjectured to be complete for determining d-separations between counterfactual events. For Single World Intervention Graphs (SWIGs) (Richardson and Robins, 2013; Shpitser al., 2022), conditional independence among variables can be read using d-separation. However, SCMs imply many cross- world constraints on the counterfactual joint distribution that cannot be captured by single-intervention representa- tion. Recently, Correa and Bareinboim (2024; 2025) introduced novel graphical representation, called Ancestral Multi- World Networks (AMWNs), which provide sound and complete d-separation statements, and allow for polynomial-time reasoning with respect to the number of different worlds involved in the counterfactual query.
B BACKGROUNDS
An SCM induces observational, interventional and counterfactual quantities over the endogenous variables, which form three layers known as Pearl Causal Hierarchy (PCH).
19

---

Published as a conference paper at ICLR 2026
Definition 7 (Pearl Causal Hierarchy (Bareinboim et al., 2022)). An SCMM (C, P(U))
induces three layers of probability distributions which form the Pearl Causal Hierarchy. For any Y, Z. X,W C V, the three layers of distributions are given by:
(Observational):
(M) Σ (
(3)
(Interventional):
pM(yx) = Σ
(4)
(Counterfuctual))
pM (yx,"" kw) = Σ T(Yx(u) = y, (w,(u) = P(u).
(5)
The collection of all L1 (observational) is denoted ph, the collection of all C2 (interventional) is denoted as p and the collection of all C3 (counterfactual) is denoted P4s,
Multiple interventions entail different copies of the mechanisms of the SCM, each for different world (syntactically represented by a different subscript), but all sharing the same P(U). A counterfactual distribution can be evaluated by passing the of exogenous variables U through the different versions of those mechanisms, depending which hypothetical world one aims to evaluate.
Given an SCM M, a graph can be constructed to capture topological information among endogenous and exogenous variables, called causal diagram (Pearl, 1995).
Definition 8 (Causal diagram; Definition 13 Bareinboim et (2020)). Consider an SCM M (U, V.J, P(U)). Then is said to be causal diagram of G if constructed as follows:
(i) Add vertex for every endogenous variable in the set V.
(ii) Add an edge (V - for every V, W V V appears as an argument of Jw E F.F.
(iii) Add bidirected edge (V + W for every V, W E V if the corresponding Uv, Uw C are correlated or the corresponding functions Jv Jw share some E as an argument.
The pairing causal diagram with the set of invariance constraints it encodes over a collection of distributions defines graphical model (Yang and Barcinboim, 2025).
Definition 9 (Counterfactual Bayesian Network (Correa and Barcinboim, 2024)). A graph & is Counterfactual Bayesian Network (CTFBN) for collection of counterfactual distributions f ift
(i) (Independence Restrictions) Let W. be a set of counterfuctuals of the form W Waww' and CI.... Ci the c-components of GVV (W.) .)), and CI..... Ct. the corresponding partition over W.. Then P(W.) factorizes
P(
A
W Paay
II P A j=1
W waww)
(6)
Wpayy CW.
Wpay EC;.
(ii) (Exclusion Restrictions) For every variable Y V with parents Pay, for every set Z C V \ (Pay U (Y)) and any counterfactual set W., we have
P(Ypay.z: 2z W.) P((paay W.)
(iii) (Local Consistency) For every variable Y E V with parents Pay, let X C Pay, then every Z V (X (Y}) and any counterfactual W. we have P(Y2 = y. X, = x, W.) = P(Yxa = = x, W.)
(8)
D-separation. In a causal diagram G. path p between vertices X and a d-connecting path relative to set Z if (i) every non-collider on p is not member of Z; and (ii) every collider on p is
20

---

Published as a conference paper at ICLR 2026
B
B
(a) g
(b) g = Go
(c) STe.o
(d) 9T..
(c) 9Tp
Figure 10: MUCT and IB are shown in red and blue, respectively; (b, c) non-POMISs; (d. e) POMISs.
an ancestor of some member of Z. Two variables X and Y are said to be d-separated by Z if there is no d-connecting path between X and Y relative to Z. Two disjoint sets X and Y are said to be d-separated by Z if every variable X is d-separated from every variable in Y by and denoted as (X 1L Y Z)g.
Do-calculus. Pearl (1995) devised do-calculus which acts as bridge between observational and interventional distributions from a causal diagram without relying on any parametric assumptions.
Theorem 4 (Do-calculus (Pearl, 1995)). Let G be a causal diagrum compatible with a structural causal model M, with endogenous variables V. For any disjoint X, Y. W, Z V, the the following rules are valid.
Rule 1. P(y [d((w),,,z) Ply do(w), 2)
if X. and Y are d-separated by W U in 9w
Rule P(y (d(w)), do(x), z) Ply do(w),
if X and Y d-seporated by W Z in 9w
Rule P(y do dd(lw,, do(x), 2) Ply do(w).
X and Y d-separated by W Z in 9w.xX X(Z]
where X & X v
B.1 STRUCTURAL CAUSAL BANDITS
In this section, we provide definitions of minimal intervention set (MIS) and possibly-optings minimal intervention set (POMIS) (Lee and Bareinboim, 2018), along with their complete graphical characterizations and illustrative examples.
Definition 10 (Minimal intervention set (MIS)). Given information (G. Y), a set of variables S V V {Y} is called a minimal intervention set (MIS) if there is X C X such that [x[x]] = flx for every SCM conforming to G.
MIS leverages Rule 3 of do-calculus (Pearl, 1995) to eliminate variables that are irrelevant to the reward. Intuitively, an MIS can be understood as a set in which there exists a directed path from any variable X E X to Y, ensuring that each X can influence Y.
Proposition 4 (Characterization for MIS; Proposition 1 in Lee and Bareinboim (2018)). Let G be causal diagram over the set of variables V. set X C V V (Y) is an MIS relative to (G, Y) if and only X S ((())x..
Definition 11 (Possibly-optimal minimal intervention set (POMIS)). Let X C (Y) be a MIS relative to (G, Y). If there exists an SCM conforming to G such that Mlx- then X a possibly-optimal minimal intervention set (POMIS).
When given a causal diagram G, minimal UC-territory (MUCT; Def. 5) and interventional border (IB; Def. 6) provide graphical characterization of POMIS. Intuitively. MUCT is the smallest set of variables that constitute a closed mechanism conveying all hidden information from unobserved confounders to the downstream reward, while the IB consists of the nodes that directly affect this closed mechanism. This implies that intervening on any variable within the territory may disrupt essential information, while intervening on all variables in IB with values that exert positive effect can be beneficial.
Theorem (Characterization for POMIS; Theorem Lee and Bareinboim (2018)). Given infor- mation (G, Y), a set X C V \ (Y) is a POMIS with respect to (G,Y) if and only if IBx Y) X.
21

---

Published as a conference paper at ICLR 2026
For example, consider the causal diagram in Fig. 10a. Here, G (Y)n holds. An L1 action do(0) is not POMIS. To see this, we construct MUCT, initializing T = {Y}, }. as follows: Since Y has an unobserved confounder with C, we update = cc(Y)g {C, Y). and thereafter add all unobserved confounders
the descendants of C, obtaining T = {C, D, ). Since there between T and Ay(Y); T, MUCT has been found and is given by MUCT(G, Y) = [C,D,Y along with IB(g, Y) = {A, }} (Fig. 10b). According to the graphical characterization, we can conclude that do(0) is not POMIS with respect (G, Y). Similarly, {B, C} is also not POMIS, as IB(9 (n.c). Y)
{B, D}. as depicted in Fig. 10c. In contrast, the regimes corresponding to Figs. 10d and 10e are POMISS, since they satisfy IB(gx) Y)= X.
B.2 COUNTERFACTUAL CALCULUS
Correa and Bareinboim (2024; 2025) introduced a novel calculus over probability quantities that may be defined at the counterfactual level (C3), called the CTF-calculus.
Theorem 6 (Counterfactual calculus (CTF-calculus); Theorem 3.1 in Correa and Bareinboim (2024)).
Let 9 be a causal diagram, then for Y, X, Z, W, T, R S VV the following rules hold for the probability distributions generated by any model compatible with G:
Rule I. (Consistency rule Obss/intervention exchange)
P(yt XT., W.) P(yT.;XT. W.)
Rule 2. (Independence rule- Adding/removing counterfactual observations)
P(yr Xx, W.) (Pyr.w.)
(Y 11 X W.)9a
Rule 3. (Exclusion Rule Adding/removing interventions)
P W.) P(yz, W.) if An (Y) = 0 in Oz
where GA is the AMWN (G Y, UX,UW.)
The independence rule requires the construction of another graphical object, known the Ancestral Multi-Worlde Network (AMWN), which serves to identify d-separation (Pearl, 1995) relations among counterfactual variables.
Nested counterfactuals. Any quantity of nested counterfactuals can be expressed in terms of unnested ones using CTF-Rule (consistency), enabling their analysis through standard counterfactual semantics.
Lemma 2 (Counterfactual Unnesting Theorem (CUT); Theorem in Correa al. (2021)). Let Y,X E V, Z Z S V, and let z be set of values for Z. Then, the nested counterfactual P(Yr....) can be written with one less level of nesting as:
-f)..x.-y)
Σ P(YT.. = y, x).
(9)
zEDx
where T. represent any combination of counterfactuals based on T.
To see this, consider the causal diagram G in Fig. 11 with three variables, where X represents level of exercise (x' for regular exercising, x for none), Z cholesterol levels, and Y cardiovascular disease. An interesting question is how much exercise prevents the disease through pathway other than cholesterol regulation, which can be expressed as E|Y2.2 22 Yz]. This quantity also known as Natural Direct Effect (NDE) (Pearl, 2001). Although the second term EY, can be trivially identified, the identifiability of the first term EY,,, Z cannot be tested directly. According to CUT, the corresponding probability term (()..,,) can written as P(ya .7.) = Σ, P(ya'z Zx), which implies that identifiability of P (yaazz, Ex) entails the identifiability of P(we...)
Figure 11: Non-identifiable Natural Direct Effect (NDE).
22

---

Published as a conference paper at ICLR 2026
Note that P(ye'z: 2z) is non-identifiable in this case; thus the NDE quantity cannot be estimated, even with arbitrary experimental data. For further details about CUT and the identification of counterfactual queries, we refer the reader to Correa al. (2021); Correa and Bareinboim (2024; 2025).
B.3 REALIZABILITY
Realizability a property of distributions, indicating that an agent can draw samples from them through physical experimentation (e.g., RCT). We begin by introducing the most granular exper- imental capabilities, which serve as the fundamental building blocks of experimental procedures, including counterfactual randomization (Raghavan and Bareinboim, 2025).
Definition 12 (Feasible operations). Given causal diagram G, the physical operations that agent can perform any unit are limited to:
(i) SELECT(); randomly choosing, without replacement, a unit from the target population, to observe in the system;
(ii) (V)) measuring the way in which causal mechanism fv F has physically affected unit i, by observing its realized feature V();
(iii) RAND(X)()) (6) erasing and replacing i's natural mechanism fx for decision variable X with an enforced value drawn from randomizing device having support over Dx;
(iv) CTF-RAND(X + C)O0; This counterfactual randomization can be performed if there is special counterfuctual mediator by which the mechanisms generating C perceive the value of X. This counterfactual mediator then allows the agent to intervene on the value of as perceived by C, thus mimicking an actual intervention on X.
For example, RAND(X)) (+) denotes the standard Fisherian randomization of decision variable X. By applying RAND X ()(O, the natural decision unit is erased (i.e., its natural mechanism is broken). Consequently, performing READ(Y)())) under this randomized regime allows researchers to estimate the causal effect of X on Y.
Definition 13 (Counterfactual mediator (informal definition); Definition 2.2 in Raghavan and Barein- boim (2025)). We call X counterfactual mediator of X w.r.t E Ch(X); if the value X can be retrieved from X by the mechanism generating
counterfactual mediator X can receive exogenous noise, but the inverse from X X needs to be deterministic. This means that the domain of X divides into equivalence classes of values that can each be mapped back to a unique X. This is quite intuitive and well aligns with real-life situations, for example, race could be associated with many stereotypical names, but for each stereotypical name, it maps back to unique race (Bertrand and Mullainathan, 2004). The formal definition and details can be found in Appendix D in Raghavan and Bareinboim (2025).
Definition 14 (Realizability; Definition 3.4 in Raghavan and Bareinboim (2025)). Given a causal diagram & and set of feasible operations A, Ls-distribution P(W.) is realizable if there exists sequence of operations from & by which an agent can draw an i.i.d. for any M consistent with G.
Definition 15 (Maximal feasible operation set (Raghavan and Bareinboim, 2025)). Given an SCM M (U, V, P(U)), the maximal feasible operation At is the of all feasible operations an agent can perform in M with the most granular interventional capabilities: (i) SELECT()) (ii) READ(V)()), VV E V; (iii) RAAD(X)(C)) and (iv) VX E V: CTE-RAND(X - C) VX E V,VC E (X
In short, we say P(W.) )) W. is realizable if it is realizable from maximal feasible operation set. We now investigate the realizability of distributions graphical language through a causal diagram.
Lemma 3 (Lemma D.6 in Raghavan and Bareinboim (2025)). Given causal diagram for any SCM M compatible with G, the jointly necessary and sufficient conditions measure Xw are (i) W is fixed as w (by intervention) as an input to all children C & Ch Ch(W), (W)g n An(X), );; (ūi each E An(X) oo with A & W U (X) is received "naturally" (without intervention) by its children C E Ch(A) (a(A)) O An X)g: and (iii) the mechanism fx is not erased and overwritten by intervention.
23

---

Published as a conference paper at ICLR 2026
Task 1 (Fig. Sa)
Task 2. (Fig.3b) 3b) 10k
Tisk (Fig. 9)
Total trials
10k
100K
CTF- POM-S
66.69
4-00.31
387.01 #71.21
1642.1 #:237.4
2477.4 +:36.3
TS
CTP-MIS
171.37 1:49.0
673.5 1:82.0
5160 63 1:307.9
4825.6 1:201.8
POMIS
664.27 +:3.5
1171.07
+10231
3295.4
+216.1
1439.8
+:300.7
CTI-POMIS
148.19
40.12
831.24
#88.9
4226.0
2:77.77
4511.8 1.25.77
KL-UCB
CTF-MIS
380
4:4.993
1184.68
+72.99
95633.71 77 +-248.0
5358.5 +100.23
POMIS
683.57 40.04
1397.
170.2
5179.9 1:236.7
3135.43 1:244.1
Table Mean and standard deviation of cumulative regret over 1,000 repeated simulations.
Furthermore, X. can be evaluated (realizable) if and only if the three conditions (i-iii) in Lem. 3 are met for each Xw E X. simultaneously.
Lemma 4 (Corollary 3.7 in Raghavan and Bareinboim (2025)). Given causal diagram G, an L3 Ca-distribution Q = P(W.) is a realizable distribution induced by any SCM compatible with given graph G if and only if the ancestor set An(W.) does not contain a pair of potential responses Wa, We of the same variable W under different regimes where + t.
Note the distinction between identifiability (Pearl, 1995; Tian and Pearl, 2003; Lee et al., 2019) and realizability. Identifiability refers to whether distribution (e.g. P(vx)) can be uniquely computed from collection of available distributions, given causal diagram G; that is, whether the target quantity can be derivable for any SCM compatible with constraints encoded in 9 in a symbolic way. For counterfactual queries, identifiability refers whether can be computed from any combination of Ce2 distributions (Correa et al., 2021). In contrast, realizability concerns whether it is physically possible for an agent to gather data sampled from the target distribution.
For instance, recall the causal diagram in Fig. where we have observed that EY, is non- identifiable; i.e., P(urrzz) Σ. 25 2x) cannot be identifiable from any combination of observational and experimental data. However, An(Y.'z, Zz) = {Yz'z, 3, (to test Lem. 4) does not contain any conflicting subscripts for the same variable. Thus, 2(Y='z,) is realizable. Therefore, one can directly sample from P(Y via feasible operations as defined in Def. 12. For more details on the realizability of counterfactual distributions, see Raghavan and Bareinboim (2025).
C EXPERIMENTAL DETAILS
This section provides details on the specific SCMs used in all bandit instances presented in the experiments. Simulations are repeated 1,000 times to obtain consistent results. The simulations were conducted Linux server equipped with an Intel Xeon Gold 5317 processor running at 3.0 GHz and 64 GB of RAM. No GPUs were used during the simulations.
We consider three strategies for selecting arms: CTF-POMISs, CTF-MISs, and POMISs, combined with prominent MAB solvers: Thompson Sampling (Thompson, 1933; Chapelle and Li, 201 Agrawal and Goyal, 2012; Kaufmann et al., 2012) and KL-UCB (Garivier and Cappé, 2011; Cappé et al., 2013). The number of trials is set to 10k for Tasks 1 and 2, and 100k for Task 3, which sufficient to observe performance differences among action spaces". Table summarizes our simulation results, and Table 2 provides the number of representative CTF-POMISs, CTF-MIS, and POMIS, along with the corresponding number of actions for the three tasks and examples in the main body.
We denote the exclusive-or operation by @ and use Bern to represent Bernoulli distribution. We first construct M1, corresponding to Fig. 5a, as an illustrative example. In contrast, we randomly generate structural functions F using binary logical operations (A, V, @ -), and the parameters of the exogenous variable distributions are also randomly selected for the subsequent SCMs.
'The number of trials is selected such that the cumulative regret with respect to CTF-POMIS stabilizes across 1000 repeated runs. Our experimental setup closely follows those of Lee and Bareinboim (2018) 8) and Wei et al. (2023).
24

---

Published as a conference paper at ICLR 2026
Task (Fig.
Task (Fig. 3b)
Task 3 (Fig. 9)
Fig.
Fig. 7a
CTE-POMIS
IS
CTE-MIS MIS
10
18
40
50
25
POMIS
CTF-POMIS
12
36
68
131
39
CTE-MIS
239
POMIS
16
36
43
31
Table 2: The number of intervention sets (IS; above) and the corresponding number of arms under binary domains (below). The number of CTF-POMIS refers to representative CTT-POMIS.
Task 1. The bandit instance associated with an SCM M1 associated with the causal diagram in Fig. 5a defined as follows:
U
(Uw,Ux+ U2, UU,,UX,UZ.UU U2r)
V
= =W,
Sw -w, = V ux,
M1
(10)
fz = uz V w @ uzy,ff = (uy 3x x (1 w) @ uzy) (0rl1..1), (0.1),Ux Uy Bern((.1)) Uzy Bern(0.1)
Uw Bern
Bern(0.1). Uz Bern(0.1),
P(U)
In this setting, the expected reward the optimal action μx; Pa 0,7 a 0.8848, and Px 0.0648 > O.
A Aga
-x:
Task 2. The bandit instance associated with an SCM M2 associated with the causal diagram in Fig. 3b defined as follows:
U
UUr, Ux, Uv U2, UxY,
V
= =TT,W,X,ZYY)
fr wr fw fx -1--ux) + (ux Vw).
F
fz = ((1 - (t (1=) Vz) uzy, fy ((1 (1l(uuz V u1- 1 uy) (z
M2
(11)
UT ~ Bern(0.65), Uw Bern (0.65), Ux ~ (0.71).
P(U)
Uy ~ Bern(0.73), Uz Bern(0.43), Uxy Bern(0.76). UZy ~ (0.33..43).
In this setting, the expected reward of the optimal action is μx; MX 22. 2 0.5912, which is optimal for both and / = 1. The gap is A μX: Fx R 0.0042 > 0.
Task 3.
The first bandit instance is associated with an SCM M3 (Fig. 8c, left) associated with the causal diagram in Fig. 9 defined as follows:
U
Un, Ur, UnU DA, E, F,Y)
V
fA = wA.fs ((11-((1-)) a) (g) @ (unc @ (uBY + f)),
fc (1-((1uc) (1-a))) (dd))
F
fo = (e Aup ug.
M3 =
(12)
fr = (1 (1- ((I A Aur) (upy @ (uDc c))
UA ~ Bern().)), ~ Bern Uc (0.4((0.4))
UD ~ Bern Ug (er5().)5), Up (022().)
P(U)
Uy ~ Bern((.6)) UBY (er7().74), UDY (0r35).35).
UBC ~ (0r37)
25

---

Published as a conference paper at ICLR 2026
In this setting, the expected reward of the optimal action is μx; Co R 0.618. The gap is Azga = μх; = 0.0248 > 0.
The second SCM M'3 (Fig. 8c, right) is defined as follows:
U
-UA, Uc. UD. Ug, UF, UBY, UByy UBC}
V
= D, F,Y
fA UA = (1- -1-uBy) BBY) V (((1 (uBC (B)) A Aa).
Sc = (1-upc) V ((1 a) A ((1 uc) Ad))
F
La (up (1- ( A
JE = ug, fr = uF,
(13)
fy (1 "BY) V (((1 - (uDY V uy Ac) Ab)
UA ~ (ern().34), UB ~ Bern(0.52). Uc (0.75)
UD (0rn().47)) Ug Bern(0.46), UF (ern(0.76).
P(U)
Uy Bern(0.67), UnY (er6().63), UnY Bern(0.68),
UBC (0rn6..26).
The expected reward of the optimal action μx; C = 1b=0,cml = 1, which implies
A Agga = Pxx; 1x O.
D DISCUSSIONS
Online optimal strategy. One might be concerned that while the algorithm (Algo. 1) effectively uses causal knowledge to eliminate suboptimal actions before learning begins, it then switches to traditional solvers that ignore additional observations available during each round. Indeed, there exists rich body of research that updates parameters under graphical constraints (Zhang and Bareinboim, 2022: Bellot et al., 2023; Wei et al., 2023; Jalaldoust et al., 2024) in online learning. However, such approaches often rely on optimization based approaches such as canonical SCM (Zhang et al., 2022) or neural causal models (NCMs) (Xia et al., 2021; 2023) that assume full parameterization. In contrast, our approach focuses on leveraging structural knowledge, before any online interaction, and without requiring parameterization or any strong assumptions beyond given graphical structure.
Future work. Beyond structural causal bandits, we believe that counterfactual decision making will offer substantial practical value when integrated with causal reinforcement learning (Zhang and Bareinboim, 2022: Hwang et al., 2024; Bareinboim et al., 2024), rehearsal learning (Qin et al., 2023; 2025; Du et al., 2024; 2025a;b; Tao et al., 2025), and sequential planning (Pearl and Robins, 1995; Jung et al., 2024).
E TECHNICAL DETAILS
In this section, we provide several technical details to support our main results.
E. COUNTERFACTUAL ACTION
Lemma 5 (Observational action: Lemma D.8 in Raghavan and Bareinboim (2025)), An agent can draw sample from PYY) associated with an SCM M by the following operations.
(i) (
(ii) (B) = = P(Y).
Lemma (Interventional action; Lemma D.10 Raghavan and Bareinboim (2025)). An agent can draw sample from P(Yx) associated with SCM M by the following operations.
(i) ())
26

---

Published as a conference paper at ICLR 2026
(ii) RAND(X)())
(ii)) If RAND(X) - x, then READ(Y)()= =y P(Yx), else repeat i-iil.
With the counterfactual randomization operation CTE-RAND, an agent can draw reward samples from counterfactual action do(X X X.) for X. satisfying Prop. 1.
Lemma 7 (Counterfactual action). satisfying Prop. 3. An agent can draw sample from P(Yx.) associated with SCM M by the following operations. Repeat (i-ii) for xjw,]] E X.:
X, be an CTF-SCB action equivalent to a target CTF-MIS
(i) SELECT().
(ii) CTF-RAND(W, ()) for forW; E W, " )g: fixing the value of counterfactual mediator Wj using a randomizing device for unit i. If (i is inconsistent with w,, return to (i).
(iii) READ(Y) = P.Yx.).
This procedure is written as if it were based on access to A., Further, CTF-RAND must always be applied with respect to a graphical children; it is not possible to bypass a child and directly alter the perception of a descendant.
Proof. This follows from the correctness of CTE-REALIZABLE (Theorem 3.5 in Raghavan and Bareinboim (2025)).
Remark 2. To enact an intervention such as do(x), we draw random value and reject the draw is not equal to This procedure is adopted for clarity of presentation and to provide general intuition linking a counterfactual action to its practical implementation; in environments where do(x) or dx(x) is feasible, this procedure can thus readily replaced with WRITE(X x) and CTF-WRITE(W: (w; + Xj). where CTF-WRITE is simply the deterministic counterpart of CTE-RAND.
E.2 GRAPHICAL CONSTRAINT INDUCED BY REALIZABILITY
We investigate which graphical constraint is induced by the realizability condition Prop. 1. Proposition 5. Les X, = {Xi(w.)ii= be CTF-MIS with respect to (G,Y), Y). For any Xiswel Xs(,,) if X, E An(X)) then w; S w, holds.
Proof. Since X; E An(X))ow, we know that (ijw,(Ma(Xx)err) E An(X)iw;)) S An(X.). In order for X, to be realizable, the subscript assignments must be consistent, implying w; w An(X, An(X:)ew; C w,. This completes the proof.
Consider the causal diagrams in Fig. 12a. The counterfactual regime X, {X1[[a wzl X wew in G1 is not realizable. To see this, observe that X X1(wi, [[w] E An (011[1s C An(X.) Hence, for X. to be realizable (i.e., An(Yx- X.) ) is realizable). there must not exist any variable of the form X1 with * [Wi, W2) in An Ax(X,), ). Since X, E An An((2))1wy An An(X2))z)) contains X X1|warAn(X,)) (an(X)) by the definition of counterfactual ancestors. However, we have W2 O (n(X)) = fwz) + fwi, w2). which results in a conflict between [[])),wa)] E An(X (w]]) and X [1)s)] E An(X2//a]). Therefore. X. is non-raalizable, and X., is not valid action in CTF-SCB with respect to (G1, Y).
Next, we consider the causal diagrams in Fig. 12b. Similarly, X, = fX [ wo2]: X X2 ans) is also not realizable. as X1 KIlag.aaa An(X ([w))) S conflicts with X (i(m) E An An(X2(wa))
In contrast, X, [Xi[wz)> w is realizable, and constitutes CTF-MIS with respect to (Gs, Y) (Fig. 12c), since w2 n An(X) (X)))w conflict with X X1[wz) E An(X1(w.) (it can be also checked by W4).
fwz {w>} implies that X X1/eal E An(22(wa) does not
27

---

Published as a conference paper at ICLR 2026
W3
(a) 91
(b) G2
(c) Ga
Figure 12: (a-c) Causal diagrams 91 92 and 93: red region represents w, and the blue represents W2. Notably, ancestral relations are independent of confounders; (c) G3 with a realizable regime (valid action) when the value of W2 is consistent; (d) Realizable regardless the value of W2.
Moreover, X. = (X [X1(w))wg) X2 wa)) in Fig. 12d is also realizable because An X2(wa)) does include any counterfactual variable of the form [(t))- These examples illustrated in Fig. 12 indicate that if X1 E AAn(X2)sgg then W2 An(X))e must be identical with W1.
E.3 ALGORITHM DETAILS
We provide more detailed version of Algo. demonstrated in Algo. 2.
Algorithm 2: Algorithm coumerating all representative CTF-POMISs (full version)
Input: Causal diagram G; and reward variable Y Output: All representative CTF-POMISs with respect to (G,Y)
Set H (Y)))))))-
for each children choice (eV) XWeer 20x(W)x do
Initialize a map pa[X] = 9 for all X E V(H).
for each W W and each child X E Xw do
Update pa X] pa[X] U (W) if W * else pa = -aaaaaaXuup if X & pa(X X] then break
else
if (B(' Y) = 0 where H'' = H (W + X V VW E pa[X]] then Let π [X1 X2
X,,) be topological order of V(H) (Y).
Initialize X. = (
10
for each X π with pa[X] + 0 do
11
Add {X₂ X E Uwew Xw } into X. where z = -UTEN((X) pa[T"]
12
13
Compute X = CTE-MISIRY X., Y).
14
yield X An(Yx. X() satisfies Prop. 1.
Lines 4-5, When constructing the map pa, if X = Y, we replace X with W since Yy. = Yw (Sec. 7.3 in Pearl (2000)) for all E V(H) and W E pa(X]] This substitution ensures that the algorithm does not violate the conditions X, V (Y) and W, (Y) for any potential result Xi(w:] E X..
Line 6. X S. pa[X], this will induce counterfactuals of the form X,,.., which are equivalent to either X₂ or C.. where C Ch(X)g. Therefore, this case will be addressed, or has already been addressed, in another loop corresponding to line 2.
Line 8. It is evident by Thm. and Cor. 3.
Lines 9-12. Note that realizability has not been verified. To maintain the same structure of the subgraph H' while modifying (Xpaix1} } into a CTF-POMIS, we first append the subscripts induced by the ancestors of each counterfactual variable of X Xps[X] (Prop. 5). Through this procedure, X, satisfies Lem. 4 in symbolic form; yet conffict may still arise between An (xx)) and An(X.).
may not be a CTF-MIS or CTE-POMIS since its
28

---

Published as a conference paper at ICLR 2026
Lines 13-14. Finally, CTF-MISIFY removes unnecessary counterfactuals from X, according to Thm. 1. In this process, the counterfactual regime graph Hx. does not change, since its construction accounts for ancestrality from the perspective of CTF-Rule and realizability. Therefore, by checking for conflicts through Prop. 1, confirm that this counterfactual symbol constitutes valid representative CTF-POMIS.
E.4 NESTED COUNTERFACTUAL REGIMES
One may raise concern regarding actions based on nested counterfactuals (Shpitser, 2013; Correa al., 2021). For example, consider nested realizable regime (Tw,, Zz } (i.e., An Two W Zz:)
does not contain any conflict) in the causal diagram shown in Fig. 7a. Then, we can derive as follows:
NT 2
Σ
y yP(Nzz las Way Rot))
CUT
(14)
9,2,1,10
Σ
yp(wut twz Way 2x))
CTF-Rule 3
(15)
g.add
Σ
y buzs Way kxr)
CTF-Rule I
(16)
Σ
y P(hezz Wz Ze))
summation
(17)
U.2,10
2...
CUT
(18)
Hence, observe that X. (Wz, Z can account for the nested counterfactual regime (Tw., Ze/) }. The following proposition shows that (possibly infinite) iterated nested counterfactual regimes can be disregarded general.
Proposition 6. For any realizable nested counterfactual regime, there exists an action that is equivalent to it; that is, A covers all nested realizable counterfactual regimes.
be realizable nested regime. We sup- pose Z S An(X:)sz and Tj S. An An( otherwise, one can find an equivalent regime by interventional minimization (Lem. 1). We now derive follows:
Proof. Let X., (Xiizz) /iz where Z /
px.
Σ ((xxx A 1
CUT
(19)
y.N.2
Σ y P(
A
Claim 1
(20)
Σ
y P(
A
^
Claim 2
(21)
U.x.2
Σ
P
A 1)11)) i
marginalization
(22)
M.2
PU. z
(23)
Note that for any pair of counterfactual variables G(g Z and [[t;]] Z if z², then
tj tf holds by the realizability condition (Prop. 1). Hence, the realizable nested regime X.. is equivalent to U, Z' E A under Claim 1 and Claim 2. Consequently, establishing the validity of these two claims implies that CTE-POMIS actions are sufficient to cover all realizable nested counterfactual regimes. We now provide a line-by-line explanation of the main part of the proof.
Claim 1. Let Z Z 0 An(Y) and z" Z Z', implying Z" 0 An(Y) = 0. Then, according
to the realizability condition, for any Zj Z' we have Zj(x] Z 2)xxnta(2))cg) An(Yx) which coincides with 3/1 Z, Therefore, Ar,
2f "tt
Mr, 2)xx = 2 holds. This property allows us
29

---

Published as a conference paper at ICLR 2026
to write follows:
z"
Eq. (19)
Σ
(
A Fsjm-]:
J1ey1
2
Steyy)
def
(24)
v.X.2
Re
Σ
y P(yx,
xxx
A (1t5)
realizability
(25)
N.X.x
Σ
y yP(uxa'
A (allar)) x
sieyy
CTF-Rule 1
(26)
Σ
A s Z
A
CTF-Rule 3
(27)
V:X.2
hj
Σ
y (( A (ister) 2/x0 ^
5107))
def
(28)
N.X.X
kij
y P(
A Arspee
(29)
which concludes the proof of the first claim. We now proceed to demonstrate the next claim.
Claim 2. Without loss of generality, we suppose X1 X2 x ... Xn where n = [V(X..). )-
Consider an arbitrary pair X,, X3 with X, x Xj.
First, if X, E An(X))sz holds, then z' = z' n An (x())) S z by Prop. 5. Therefore, we obtain that (Tape)) Fy(w)]] be written (Aijerz/) Fymr2)))
Otherwise, if X; $ An(X))ozz then Z' An(X)) @ holds, implying {Z(j)) Toleizi by CTF-Rule 3. Furthermore, suppose Z 0 An( An(X,)s, # 0. Then, this means X Xajel| E An An(X)(m/)) implying = z n An(Xi)) S x by Prop. 5. Therefore, {arw) Tyfwx)]) [Tapete)) Fx(e holds. Otherwise, if ZZ O An(X:) 0, applying CTF-Rule 3 results in (1npe))
Hence, we can say that ( [ Tattni) for any arbitrary pair X;, Xj with X, Xj. Therefore, can express as follows:
Eq. (20)
Σ yP
Fijel
realizability
(30)
9xx.2
Σ
y PP(uee: X
def
(31)
9xx8
Σ
yP(uz: Xxx
A
x
CTF-Rule
(32)
Σ
yP( A
(33)
9.x.2
which concludes the proof of the second claim, and thus completes the main proof.
F OMITTED PROOFS
In this section, we provide detailed proofs of the statements presented in the main body of the paper. For readability, we restate all of them.
F.1 PROOF OF THEOREM
Theorem 1 (Graphical characterization of CTF-MIS), A counterfactual X, -Xii..Jim A is CTF-MIS if and only (i) X C An(Y))g and (ii) for any Xiw..) X., W,n An(Xi) # 0.
30

---

Published as a conference paper at ICLR 2026
Proof. We first note that actions in the L52 regime such do(w) correspond to intervention set of counterfactual variables of the form do( W = Ww) within X, For instance, in the counterfactual expression Y x_ the corresponding regime X, {Z xw) and V(X.) = [Z, X
(Only if) If some X, does not satisfy the first condition, it means there exists Xi(w.] E X, such that X; does not have any proper causal path to Y with respect to V V(X.)* implying μx. px. (Xim,) To see this, derive as follows:
Px. = Σ
(P X. x
CUT
(34)
y.
Σ
XIX) A x)tw;))
def
(35)
E
yP( Bi(wal A 2s(ws])
CTF-Rule
(36)
Σ yP(MAXX.)) A Fy/w,))
summation
(37)
[xX(X,
MX.. ((Xi(a))
(38)
Therefore, we have shown that if X. violates the first condition, then is not CTF-MIS. We now proceed next step.
For the sake of contradiction, let X, first condition but not the second; we assume W, "r An minimal X' {X}}}= V(X.) (X} such that W = This implies X' blocks all directed paths from W, X,. The notable point is that Xj(wol =Xjjw, (xx))))(X)))) =X][w.] and
A be CTF-SCB action satisfying the = 0. implying that there exists
W, W; for any Xj X' (see Prop. 5) otherwise, Xstwil would conftict with Xj)wsnan(X))ap violating the realizablity condition (Prop. Hence, we can derive {X5(ws) X, E X'}
[X5jw,))s=1 X
For convenience, we denote by x", the value of X; E X that constitutes neither X' nor X;. Then, we can derive as follows:
px. = Σ
yP X. x)
CUT
(39)
UX
Σ
A
xk(Wee)
def
(40)
y
X,EX
XxEX'U(X+
Σ
Ik/ww))
realizability
(41)
Vot.i x
X EXXUXX
Σ
yPlya AWWX)
CTF-Rule 1
(42)
V.
X XgxX
Σ
CTF-Rule 3
(43)
x. x
X
Σ
yP Ti(x']; X
A
CTF-Rule
(44)
X X
X XXXX
yP(yx' Xw
A
IN(wa))
summation
(45)
B.X X
XeEXUUXX))
yPu'x' A (xs)
A XigX/uXi))
Ik(W=))
minimization
(46)
B.X' X
XyEx
(X,, (X
(47)
'It means that corresponding reward is Yw Yw., we force variable to have the value w, then W will indeed take on the value w. Further details can he found in Sec. 7.3 in Pearl (2000). It refers directed path from X; to Y which does pass any nodes in V(X.) (X.).
31

---

Published as a conference paper at ICLR 2026
where CTF-Rule 3 in Eq. (43) holds from W, O An(X)) 0. induces the equivalence μxx Hx..) (Xxpi)) which contradicts the assumption that X, is CTF-MIS. This concludes the proof.
We find that W, n An(X =
(If) Assume that X.
[[w K[.w]//= /==1 is not CTF-MIS; that there exists X, = (X, [x,]w,)) (X]],,])= b= f X, such that μXx, = μx; for all SCMs. Consider an SCM .M with all variables real-valued where each variable Vi E V associates with its own binary exogenous variable U, following a fair (0rn) Let the function of an endogenous variable be the sum of values of its parents, i.c. fv
coin,
fv= --- pay +uy.
For the sake of contradiction, assume that the two conditions hold: (i) X S An(Y) Yog and (ii) for any X((w.) X., we have W, n An(Xi)xxx # 0. Thus, there exists Xxwwo] E X. X, Let
X A X. \ X Then, there exist directed paths from Xx E X' to Y in 9, and from W W A to Xg, which not constrained by the realizability subscripts (Prop. 5). Hence, setting the values of each W, which contradicts the assumption that X. is not a CTF-MIS with respect to (G, Y). This concludes the proof of this direction.
k as B kxx; + k[x;]
yields a larger outcome, breaking the equality,
F.2 PROOF OF PROPOSITION 2 AND COROLLARY 2
Proposition 2. Yf is not confounded with An(Y)g \ (Y). then Pa(Y)g is the only CTF-POMIS.
Proof. Let X. be an arbitrary CTF-MIS relative to (G,Y). Let Z Pa(Y)g) \ V(X.) and X'
V([Xw E X, x & Pa(Y)g}). Then, we derive as follows:
Px. Σ P(xx X. xx)
CUT
(48)
Σ yP 2x X. =x)
marginalization
(49)
2,y,x
Σ P( 2x:
CTF-Rule 1
(50)
2,y.x
Σ xP X, =x) x)
def
(51)
2
Σ yP X, =x)
CTF-Rule 3
(52)
2,yxx
Σ yP(BenPaya)) P((x X. = =x)
Unconfounded
(53)
2,y.X
PaYxnPay 2 Pl X. xx)
def
(54)
7,N
Σ 1paa P(zx; X, =x)
algebra
(55)
Σ Mpac P(zx.)
CUT
(56)
Ppaç.
(57)
The derivation begins by applying CUT over X., and marginalization over Ze in Eqs. (48) and (49). Note that Eqs. (51) and (52) represent the rewriting of counterfactual terms, and removing x' according to CTF-Rule by the fact that YxnPay (u) fy (x n Pay, 2, u n Uy); once all of its parents are fixed by intervention x n Pay, z, the only source of variation for the variable of
YxnPay 2 (u) depends only on u n Uy which justifies Eq. (53) (sce independence restriction of CTFBN in Def. 9). The remaining steps Eqs. (55) (57) are straightforward.
Corollary (Markovian CTF-POMIS). i is Markovian, then Pa(Y)g is the only CTF-POMIS.
Proof. In Markovian settings, there are no unobserved confounders in the causal diagram. Therefore, conclude the proof by Prop. 2.
32

---

Published as a conference paper at ICLR 2026
F.3 PROOF OF PROPOSITION 3
Proposition (Existence of equivalent action), For any CTE-(POJMIS Z, for (9,Y), there exists an equivalent action X. - [Xi C An.Z) satisfying X C W Ch( (h)) where W U, W,
Proof. Let Z. [2 j= be CTF-MIS with respect to (G, Y), Without loss of generality, only consider T, * {2,}; so, we choose {Xa} = Tx {Z+}. We denote by X C X. = (Xi..Jimi. a of counterfactual variables such that (i) T3 An(2)) 0, and (ii) for all Xisws] X!, W; is consistent with ty. i.e., W; by (X:)) Note that X can always be found Xx An(Zg)g O cb( for each tj. Let us derive as follows:
as X A {Xile na((ilo0
nzz
Σ
P((ee: 2.)
CUT
(58)
1
Σ yP A Ksjt,] = =Zj; A Xiwwil = 22))
marginalization
(59)
v.2.x
(P A Ksits) Ejz A x xx)
def'
(60)
M.2.x
where any pair of (x"1, x for ji + jz is consistent; that is, Xw E X n X implies w
Wi O An (X)s = Wa An( aa(X)ew, Dow, We now provide a line-by-line explanation of the main
part of the proof.
Eq. (60) = Σ yP(uzi A
2 2j. / X2 xx)
Claim 1
(61)
v.2.x
j
Σ
y P(yxx 7x:
Ax! x²)
Claim 2
(62)
Σ yP( 2x::
A xx=x²
CTF-Rule
(63)
V.2.X
Σ
y P((x)) A X =xx)
summation
(64)
Ux
yP(Ux; A Xi(wal = xzi)
def
(65)
U.
px.
CUT
(66)
Claim 1. We can derive Eq. (61) from the fact that X! X2,, since all of Xi(wi] X are already consistent with ty. Therefore, the following holds:
Eq. (60)
Σ yP
Ziwwai
2z. x =x')
consistency
(67)
N.2.X
Σ
(y
[/wxxo Zzj, A AX1, =x)
CTF-Rule 1
(68)
Σ
yP
[l = Zz., A x =x)
consistency
(69)
222
Σ
yP
A Zip0o = 23, A x x²)
CTF-Rule 3
(70)
2.2.x
;
where the last equation holds due to Tl n An Zz) vix25
0 (see the construction of X!).
Claim 2. By the construction of X and consistency, we have Zy|z1 Zyjz), which leads to Eq. (71).
Furthermore, according V(X.) An An(Y)
(by the construction of X!), we can apply
CTF-Rule 3, as shown Eq. (72). Therefore, we can write:
Eq. (61) Σ yP(ya, / 2ynn 2z, / =
consistent (x"1, (x²)
(71)
33

---

Published as a conference paper at ICLR 2026
Σ y 1x A X =x))
def
(72)
(N lxx
\x x²).
CTF-Rule 3
(73)
8
This concludes the proof.
Algorithm 3: Construct counterfactual world SCM Mx.
Input: SCM M; a CTF-MIS X.; and reward variable Y; Output: counterfactual world SCM Mx..
Initialize Mx. (V, U, F, P(U)).
for each counterfactual variable X Xi(w,] X. do for each ancestral counterfactual T₂ An( An(]] do if fr FF has arguments Z' S Z then
Set the arguments Z' in fr E Fx, as fixed values z'.
return Mx.
F.4 PROOF OF COROLLARY
Corollary Given a CTF-MIS X., the counterfactual regime graph Hx, is subgraph of the causal
diagram compatible with Mx, over Vt.
Proof. Let X, = (X. be a CTF-MIS with respect to (G. Y). An SCM can be constructed as follows the procedure shown in Algo. 3, which mirrors the definition of do(X X.). According to realizability (Prop. 1), when Tz E An(Xi(w.) and T, E An(Xj(w,)) for i * j. we have z Therefore, Algo. 3 mirrors the way in which the values of V is determined under X.. We denote by 9x., the causal diagram (Def. 8) of Mx. Then, all edges Z T are removed from G for any Z E Z -= W, n sT C W.) in Gx.- Hence, we obtain the counterfactual regime graph Nx. = 9x. [An(Y))x.))))))))))) 9x. [Vt] where Vt V(An(Xx, X.)). Therefore, Hx, is subgraph of the causal diagram Gx. over Vi, This concludes the proof.
F,5 PROOF OF THEOREM AND COROLLARY
Theorem (Graphical characterization of CTF-POMIS). CTF-MIS X, with respect (g, Y) is CTF-POMIS if and only if [B( Y) holds.
Proof. (If) Suppose IB(Hx,, Y) holds. By the definition of interventional border, this means Vi = MUCT(Hx.. Y) holds. The intuition of the proof of this direction to construct an SCM, conforming G, for which the single best strategy involves intervening X.. In this proof, every exogenous variable is binary variable with its domain being (0, 1}. Let + denote the exclusive-or function and V the logical OR operator. The proof follows a similar argument to that of the proof of Proposition 4 Lee and Bareinboim (2018).
An easy case is when MUCT(Hx. Y) (Y) holds; thus, we obtain W A U, W. Pa(Y)) g and X. = Pa(Y)g lg { = Ww. In this case, we can express EYx, = EY = E|y do(w)) We construct an SCM such that (i) Each endogenous variable V V associates with an unobserved variable Uv; (ii) fy
with P(Uy 0) 1; and (ii) fv (+ uy) @ b pay) for V E V (Y) and U E U Uy following a fair coin Bern(0.5). By taking
(V uy (V pay.))
conditional expectations, it holds:
E|y do(W = 0)] = E|y do(Pa(Y); 0)]
(74)
= E do((a(Y)g = 0), U. O) #0)
(75)
+ EY do(Pa(Y) = Uy 0P
(76)
= P(Uy = ~ 1.
(77)
34

---

Published as a conference paper at ICLR 2026
8
R
(a) g
(b) Hu
(c) H2
Figure 13: (a) Causal diagram; (b, c) colored subgraphs for each unobserved confounders U1 and U2-
M1
M2
M
U1
U2
B
CO)
y())
D
(X2)
y()
Y'
Y
0
2
1
1
2
00
01
00
10 10
0
00
1001
1
0
0
1
1
1
2
01 00
00
00.11
01 10
0
0
00 00
00.00
01
Table Assignments with Ba= Ca'=1.e=1 where values for M. The target variables are shown as bit sequences, c.g., Y' represents (4y(1) y())))
Meanwhile, all other interventions yield expectations less than or equal to 0.5. Therefore. X. W w a CTF-POMIS with respect to (G, Y).
Now, we consider a general case where (Y) & Vt. That is, there exists at least one unobserved confounder between Y and its ancestors. As a first step, it will be shown that there exists an SCM M conforming to G where do(A, Xor x,) (mod 2))) is the single best strategy. Let U' 1 be the set of unobserved confounders H glv U W].
Given U, U', let B() and RU) denote its two children. We define SCM M, where the graph structure is given by:
H, H(De((BU) R()))x U (W n Pa(ee((B()) (())))
(78)
with all bidirected edges removed except Uy. In order to set the mechanisms for variables in Hj. the vertices will be labeled as described below.
We label (i) vertices in De( B() \ De De(R()) as blue; (ii) De(R()) \ De( as red; and (iii) De (B)) n De(Re (R()) as purple. Each of Búi and R() perceives U, as parent colored blue with value 2 and red with value Uyj respectively.
Each variable X-blue, red, and purple colored-ar are assigned to 3 if any value of their parents in W is not ord(X) (mod 2) Otherwise, their values are determined as follows. For every blue and red vertex, the associated structural equation returns the common value its parents of the same color and returns 3 if the values of the colored parents
homogeneous, For every purple vertex, its corresponding equation returns 2 if every blue, red and purple parent is 0,1,2, respectively, and returns if 1,0,1, respectively. For other cases, the function returns 3.
We now merge the SCMs {M₂ into one single SCM that is compatible with H. In Mj, two bits are sufficient to represent every variable. We build a unified SCM where each variable in Vt is represented with 2k bits where an SCM for U, will take 2 and 2 bits. We then binarize Y by setting if 2j-1m. and 2ja bits are 01 or 10 for every j and 0 otherwise. Let P(u, = 1) = 0.5 for U, E U'. This unified SCM M provides a core mechanism to output Y do(A, X.w, =rd((X)) (mod 2))) and Y otherwise. any of variable Vt is intervened, then at least sub-SCM will be disrupted yielding an expectation smaller than or equal to 0.5.
10That is, the parity of the ASCII code of X. Note that all possible CTF-POMIS configurations can be obtained by applying permutations the variable labels.
35

---

Published as a conference paper at ICLR 2026
The previously defined SCM for H givi Wi. will be extended to an SCM for G. However, we can ignore joint probability distributions for any exogenous variables only affecting endogenous variables outside H. Setting structural equations endogenous variables outside of H. is redundant
well. For V E An(Y)g VT, define the structural equations fv ( uy @ (4 pay). For U E U U we set P(U = 0) 0.5 if U's child(ren) is disjoint to Vt, and P(Uv ord(V) (mod 2)) =
intersects with V E Vi. Note that do(A, X mord( X;). (mod 2))) is still the single optimal counterfactual intervention. Therefore, X. a CTF-POMIS with respect (G.Y).
We provide example in Fig. 13 illustrating how & SCMs are constructed. Further, values of variables for Mi.Mp and unified M are shown in Table 3.
(Only if) We will prove the contrapositive statement; that is, IB Y) * 0, then CTF-MIS X. = [Xisw:) Jizı not a CTF-POMIS with respect to (g. Y). Let T (Tj}-r IB(Hx.) Y) + Н. We denote by X {X [(w!] iim., the assigned value of W; consisting of the best action of X..
Furthermore, we consider Z. = { [Zutta]k== such that Z E MUCT Y) with U T = T. To maintain consistency (i.e., avoid any conflicts that lead to non-realizability). for any [1tt.] E Z.. if Zi E V(X.), ) then Zite.] = Zil..nT..A.WW We denote X' - (X \ Z) n An(T)g and X"  (X Z) X'. Consistently, we denote X = [Xi[w.Jex, X E X'). We are now ready to derive
follows:
xx: = Σ P(Uxs A AF(ww!
CUT (79)
V.
Σ UP 21/21221// A Fi(w!!)
marginalization (80)
&
Σ UP(UxXZ,21
A FM(x)2), - Fe(m!??
CTF-Rule (81)
b
Σ yP(Nx Z.
A (M(x)Z)) A 3 Fi(w!) txx)z)
marginalization (82)
y.U.Z,t
Σ
<x(x))))), ^ Fe(w!] txxiz)
CTF-Rule (83)
yXUUZ,t
Σ
yP(Nx\Z.2
FAIUAA A Fa[w!] (x)2)
CTF-Rule (84)
XXUutt
Σ
(P Z.
A
TNW W
A
Zkftal:
A
Fe/w!1 tx)z2)
algebra (85)
MXUUtt
Z/X
zix
x
Σ
A
2x[w]
A
2n(ta))
A
"((w!)) txxx"))
def (86)
Σ
yP (P
A
A
A
Fo[w!] tx.)
CTF-Rule 3 (87)
TAATA WW)
y.N.z,t
ZnX
Z,X
X
Σ
RK/W LOTW COTTAAAW.. W..
A
I Fa(w]]> tx:)
CUT (88)
9xx",,, 2,
Z
Z
X
Σ
A
Zk(tv|)
Talw!l P((xx;
MUCT&IB (89)
9xx"
Z-X
2:X
X"
P[XPUZ.)'
(90)
where Eq. (89) holds, since T IB(Hx. Y) is not confounded with any variables in X Z and its descendants. Therefore, X, is not CTF-POMIS with respect to (g. Y), leading to contradiction. This concludes the proof this direction.
Corollary 1. Let x = arg max Pxx be an optimal arm in Lez. Then, Pxr S JXx:-
Proof. First, since x = = L22 optimal actions necessarily contained in the CTF-SCB action space A. Therefore, Mx- 5 μx:; holds. Furthermore, unless the POMIS and CTE-POMIS spaces are exactly the same (e.g., Markovian settings as shown in Cor. 2), we can construct an SCM such that Hbx pxx, following the construction in the proof of Thm. (see Fig. 13 and Table 3). I
36

---

Published as a conference paper at ICLR 2026
F.6 PROOF OF PROPOSITION 3
Theorem 3. The Algorithm! 1 returns all and only representative CTF-POMISS given (G, Y).
Proof. When constructing the map pa, if X = Y, we replace X with W for all X E V(H) and W E pa[X] since Yv,, Yw,, (Sec. 7.3 Pearl (2000)). This substitution allows the algorithm to reformulate any regime be defined over X; V (Y) and W, S V (Y) for any X (jw. E X,, Excluding the case where X = Y, any L2-level intervention can be written in the form of subscript Cw, where Cw denotes Ch(W)g.
Therefore, the brute-force manner over all edge selections (based on Prop. considers all possible equivalent classes of regimes. Since verification of CTF-MISIPY is straightforward from the com- pleteness of Thm. 1, and its validity as an action is ensured by Prop. and Prop. 5, we conclude that this counterfactual symbol constitutes valid representative CTF-POMIS, and that the algorithm yields all such representations.
IMPACT STATEMENT
This work addresses a counterfactual structural causal bandit framework that leverages counterfactual- level causal reasoning from a causal diagram. The approach has potential applications in practical settings such as personalized healthcare, adaptive education, and resource-constrained recommenda- tion systems, where a decision-maker seeks to make optimal decisions by considering counterfactual actions (future desirable regimes) with counterfactual mediators. However, improper specification of causal structures inappropriate counterfactual mediator selection may lead to misleading conclu- sions and biased decisions. Therefore, careful validation and domain domain- causal modeling are essential prior to deployment in high-stakes environments.
37


Reviews:
[{"review_id": "SMUGzG97Nr", "reviewer": "Reviewer_qZvW", "summary": "Summary\n- SCB but also taking into account counterfactuals from L3\n- Logical and crucial extension of theoretical base\n- well executed\n\nMy review is short since I am familiar with the previous SCB work and can see this is an obvious and clear next step of extensions. It is written and present very clear, thorough, yet accessible, with the right amount of empirical experimental evidence.", "questions": "- In Fig 8, Task 3, left: is POMIS about to cross over CTFMIS TS at 100k trials?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Very thorough, clear and precise presentation of\n    - CTF MIS, CTF POMIS \n    - Their algorithms  \n    - Their theorems", "weaknesses": "The paper is very well written and makes a clear and strong contribution, hence I only have one point on writing style:\n\n- This reads a bit clunky with a rather long subclause” When X⋆∗ lies in L≤2 (i.e., ∆L≤2 = 0)—a special case and does not undermine our theoretical results, since the deployed agent can never be certain prior to interaction whether 471 the optimal arm lies in in L≤2—the smaller action space allows POMIS to converge faster than the 472 others.”\n    - Maybe rephrase as: “a special scale that does not undermine”", "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": "fUNfhc9OVO", "reviewer": "Reviewer_cvdK", "summary": "The paper extends the structural causal bandit framework by introducing **Counterfactual Structural Causal Bandits (CTF-SCB)**, wherein actions corresponds to realizable counterfactual regimes. It defines minimal counterfactual action sets (CTF-MIS), and further refines them by identifying those that are *possibly-optimal* (CTF-POMIS). Building on this, the authors present an enumeration algorithm with complexity $\\mathcal{O}(n^2\\cdot 2^{|E|})$ that systematically constructs a representative CTF-POMIS set suitable for standard bandit solvers . They prove that restricting exploration to this set preserves optimality and can reduce regret. Across synthetic tasks using Thompson Sampling and KL-UCB, the method consistently achieves lower cumulative regret than baselines that explore either larger counterfactual spaces (CTF-MIS) or purely lower-level action spaces (POMIS). In Markovian graphs, the procedure collapses to intervening on the parents of the outcome node, yielding no additional benefit from counterfactuals.", "questions": "1. Could you please clarify the difference between $\\boldsymbol{Pa}_V$ and $\\boldsymbol{pa}_V$? If you are using the convention: capital letter -> variable and lowercase -> realization, where does the randomness come from in the $Pa$ operator, given a variable $V$?\n\n2. What does $X_{\\boldsymbol{w}}$ (line 102-103) refer to? You haven't defined before a rv $X$ with subscript $\\boldsymbol{w}$\n\n3. Could you please clarify how $\\mathbb{E} N_T(\\boldsymbol{X}_*)$ arises in eq. 1? Is an expectation missing?\n\n4. Does $An(Y_x, X_*)$ mean $An(\\\\{Y_x, X_*\\\\})=An(Y_x) \\cup An(X_*)$? Could you please clarify it in the paper?\n\n5. It would be interesting if the authors can formally discuss (or better derive) finite-time regret guarantees that quantify the benefit of pruning to the representative CTF-POMIS set.\n\n\nSuggestions:\n- move the sentence \"We use kinship notation for variable relationships...\" (line 105) above mentioning Pa (line 94-95). Also the font used is different.\n- end of line 100-101: $\\boldsymbol{X}_{1[\\boldsymbol{w}_1]}$ should not be bold.\n- typo line 282: \"... are cannot..\".", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Addresses an interesting problem and introduces a novel framework for realizable counterfactual interventions within causal bandits.\n- Provides a clear and coherent motivation, positioning the extension of counterfactual reasoning to bandit settings as a natural and meaningful conceptual advance.\n- Offers a potentially valuable theoretical foundation for subsequent research that may benefit from richer intervention classes in sequential decision-making.", "weaknesses": "- The exposition presupposes substantial familiarity with the CTF-calculus (Correa & Bareinboim, 2025) and related work (e.g., Correa et al., 2021). Consequently, several statements would benefit from further elaboration.\n- The paper is quite dense, and the notation is not intuitive, which makes it hard to read.\n- Although the substantial improvement over the super-exponential naive verification, the proposed algorithm remains exponential in the number of edges, raising questions about applicability.\n- At present, the manuscript does not address finite-time regret guarantees; a short discussion would be beneficial.", "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": "ywoxAeLrQW", "reviewer": "Reviewer_Yncn", "summary": "This paper introduces a variant of the causal bandit setting in which the agent has more power: they can also perform certain \"counterfactual\" interventions in which a variable $X$ is set to value $x$ as seen by one child, but to $x'$ as seen by another.", "questions": "- To what extent can counterfactual actions be modelled by defining a new graph which explicitly adds counterfactual mediators, and performing ordinary interventions on it?\n- line 78-79 (3rd contribution): what does it mean that suboptimal interventions are \"clearly\" removed?\n- line 100/101: I initially didn't understand what you meant by \"when the variables are indexed\". Now I think you mean: when the main variable already has a subscript, the counterfactual subscript is put between brackets for visual distinction. Could you confirm?\n- In Proposition 1, what does it mean for a counterfactual to \"consist of\" an action space?\n\n##### Comments\n- The limitations section is in the supplement and is not referenced from the main paper.\n- line 105: \"correlated\" should be \"dependent\" (only the same for Gaussians)\n\n##### Textual\n- line 31: \"were\" -> \"was\" (\"were\" is subjunctive mood, but this is factual)\n- line 125: \"behave**s**\"\n- Definition 3: \"no ~~an~~other\"\n- line 282: \"are cannot be\"\n- several places: \"interventional bo~~a~~rder\"", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The topic is theoretically interesting. I have the impression that the theory is sound.", "weaknesses": "- I am not convinced of the significance of this contribution. My impression is that counterfactual actions as used here are only possible in practice under special circumstances. See also my first question below.\n- The paper is very dense in technical material. Additionally, it builds closely on very recent work; familiarity with that work is necessary to build intuition about the present work. This makes the paper hard to review in a reasonable amount of time.", "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": "FrZuTX3ELo", "reviewer": "Reviewer_nMUN", "summary": "This paper extends the structural causal bandit framework to a counterfactual scenario, where interventions are mixed counterfactuals. In this setup, the action space is defined to satisfy ancestral consistency. Leveraging the existing result on the possibly-optimal minimal intervention set (POMIS), the paper developed a method to search for the POMISs in this counterfactual setup.", "questions": "- Could you explain the challenge in algorithm design? By checking Figure 7, Algorithm 1 seems to be an application of Lee and Bareinboim (2018) (algorithm to find POMISs).\n\n- The counterfactual framework in the paper is somewhat confusing. Standard counterfactual inference typically requires observed data to constrain the exogenous variables, and then uses these constraints to reason about what would happen under a hypothetical intervention. Simply replacing the hard interventions in Lee and Bareinboim (2018) with counterfactual distributions does not appear to constitute a substantial contribution. Moreover, the mixed counterfactuals considered here could, in principle, be handled by embedding \n$W$ into a multi-world SCM.\n\n- In Page 2 \"(e.g. $X_{1,[w_1]}$)\", the  X should not be boldface.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem formulation is novel and relevant to the field.\n- I skimmed through the theoretical results and found them sound.\n- The experimental section effectively demonstrates the merits of the algorithm. In particular, it is helpful to see comparisons when the optimal action lies in $\\mathcal{L}_{\\leq 2}$.", "weaknesses": "- The challenge of the problem is unclear to me, as the method for finding POMISs is already available.", "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 (Poster)