Structural Causal Bandits under Markov Equivalence
Authors: Min Woo Park
Andy Arditi
Elias Bareinboim
Sanghack Lee
Venue: NeurIPS 2025 poster ()
Keywords: causal inference
structural causal bandits
markov equivalence
partial ancestral graph
maximal ancestral graph
Primary area: probabilistic_methods
TL;DR: We study the graphical characterization of structural causal bandits framework under Markov equivalence class.

Abstract: In decision-making processes, an intelligent agent with causal knowledge can optimize action spaces to avoid unnecessary exploration. A *structural causal bandit* framework provides guidance on how to prune actions that are unable to maximize reward by leveraging prior knowledge of the underlying causal structure among actions. A key assumption of this framework is that the agent has access to a fully-specified causal diagram representing the target system. In this paper, we extend the structural causal bandits to scenarios where the agent leverages a Markov equivalence class. In such cases, the causal structure is provided to the agent in the form of a *partial ancestral graph* (PAG). We propose a generalized framework for identifying potentially optimal actions within this graph structure, thereby broadening the applicability of structural causal bandits.

Structural Causal Bandits under Markov Equivalence
Min Woo Park
Andy Arditi
Elias Bareinboim
Sanghack Lee
Seoul National University
Columbia University
a1sdn0110@sm ac kr ebccs columbia.
ava21238columbia edu sanghackdenu .c.kr
Abstract
In decision-making processes, an intelligent agent with causal knowledge can optimize action spaces to avoid unnecessary exploration. A structural causal bandit framework provides guidance on how to prune actions that are unable to maximize reward by leveraging prior knowledge of the underlying causal structure among actions. A key assumption of this framework is that the agent has access to a fpeefispe causal diagram representing the target system. In this paper, extend the structural causal bandits to scenarios where the agent leverages a Markov equivalence class. In such cases, the causal structure is provided to the agent in the form of partial ancestral graph (PAG). We propose generalized framework for identifying potentially optimal actions within this graph structure, thereby broadening the applicability of structural causal bandits.
Introduction
The multi-armed bandit (MAB) [Robbins, 1952, Lai and Robbins, 1985, Lattimore and Szepesvári, 2020] problem is central topic in decision-making studies, where an agent aims to maximize cumu- lative rewards by repeatedly choosing actions based on observed reward, balancing the exploration- exploitation trade-off. Traditionally. MAB problems assume independence among the rewards of different arms, meaning that the reward obtained from one arm provides no information about the others, e.g., KL-UCB [Cappé al., 2013] and Thompson sampling [Thompson, 1933]. Although this independence assumption simplifies the problem, it limits its applicability real-world scenarios where dependencies among actions common, e.g., in movie recommendation system, user's positive reaction to one genre may indicate a higher likelihood of a positive reaction to similar genres.
Recent research has increasingly recognized the importance of structured dependencies among arms and Lugosi, 2012], leading
and reward [Li et al., 2010, Abbasi- Yadkori al., 2011, to the development of structured bandits. Concurrently. the integration of causal inference into the MAB framework has opened new avenues for modeling and solving decision problems with richer dependency structures [Bareinboim al., 2024]. Causal diagrams [Pearl, 1995] have been employed to represent causal relationships among actions, rewards, and other relevant factors. This approach enables agents to make informed decisions by considering how each action causally influences the reward through causal pathways. Existing studies [Bareinboim et al., 2015, Lattimore al., 2016, Forney et al., 2017] have shown that causality strategies 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 the availability of both observational and experimental distributions, or linear mechanisms [Zhang and Bareinboim, 2017, Lu et al., 2020, Bilodeau et al., 2022, Feng and Chen, 2023, Varici et al., 2023].
*Corresponding authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Specifically, Lee and Bareinboim [2018] formalized the structural causal bandit (SCM-MAB) without any parametric assumptions, where causal dependencies between arms are modeled using a structural causal model (SCM) [Pearl, 2000]. They proposed 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 non-manipulable variables among all the variables in the graph. Lee and Bareinboim [2020] and Everitt et al. [2021] established SCM-MAB with stochastic policies and Carey et al. [2024] studied the completeness of its graphical characterization.
While SCM-MAB has been established as general framework, these studies assume that the decision- making agent has perfect access to the entire causal structure. From observational data, only a Markov equivalence class of the true causal diagram over observed variables can be inferred without making a substantial assumption about causal mechanisms such as causal sufficiency [Verma and Pearl, 1990, Spirtes et al., 2001b, Chickering, 2002, Tsamardinos et al., 2006] or functional assumption [Perry et al., 2022, Peters et al., 2016, Ghassami et al., 2017, Heinze-Deme et al., 2018, Huang et al., 2020, Ghassami et al., 2018, 8, Zeng et al., 2021]. A prominent representation of the equivalence class is known as partial ancestral graphs (PAGs), and any causal diagrams can be uniquely represented by a PAG [Richardson and Spirtes, 2002, Zhang, 2006, 2008a,b, Ali, 2005].
Motivation and Contributions. With observational data, we can only learn a PAG, which encodes super-exponentia number of maximal ancestral graphs (MAGs), each of which, in turn, represents an infinite number of causal diagrams over supersets of the observed variables. Therefore, considering all causal diagrams consistent with the PAG is computationally prohibitive. Identifying conditions for MIS and POMIS at the level of ancestral graphs directly would allow one to circumvent the issue. Our key contributions are follows:
We generalize MIS and develop its graphical criteria in ancestral graphs, enabling agent to identify and exclude variables that have no effect on the reward (Sec. 3).
We devise POMIS for ancestral graphs along with its graphical characterization, leading to an action space worth exploring (Secs. 4.1 and 4.2).
We present efficient algorithm to determine whether given intervention set can be a POMIS in the Markov equivalence class represented by PAG (Sec. 4.3).
Experiments in Sec. 5 and additional ones in Appendix D corroborate our findings. All omitted proofs provided in Appendix H along with auxiliary results in Appendix G.
2 Preliminaries
We introduce notation and review relevant prior work. Following conventions. we use a capital letter. such as XX to represent a variable, with its corresponding lowercase letter, æ, 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 Xx. We use calligraphic letters for graphs and models such as 9 and S.
Graphical notations. We consider graph G having vertices V and edges E composed of directed (+) and bidirected edges (++). If there is an edge between two vertices X and Y in G, we say that the two vertices are adjacent in G. denoted by Y E Adj or X E AY)(Y)s. An ordered sequence of distinct nodes in G is called a path between X and Y in & if (1) the start node is X and the end node is Y, and (2) there is edge between any two subsequent variables in the sequence. If a path consists of directed edges with the same orientation, we say the path is directed. A variable Z is called collider on the path if the path contains two edges having arrowheads toward Z. We define path as a collider path if all non-endpoint vertices along the path are colliders. A path is uncovered (unshielded) if, for every consecutive triple on the path, its endpoints
not adjacent.
path is possibly directed from X to Y there is no arrowhead on the path pointing towards X. If there is a (possibly) directed path from X to Y. then Y is called a (possible) descendant of X, and X is a (possible) ancestor of Y. A variable Y referred to as a possible child of X, and X is possible parent of Y if they are adjacent and the edge is not directed into X. We denote the
2

---

ancestors, descendants, parents, and children of given variable as An, De, Pa, and Ch, respectively. Ancestors and descendants include the variable itself. For set of variables, we define the ancestral set as An (x))s = x An(X ). and similarly for other relationships. We add the prefix Poss when referring to possible relationships, such as PossAn.
An inducing path relative to L is defined as a path where every vertex not in L is a collider on the path, and every collider an ancestor of an endpoint of the path. A directed edge X + Y is visible if there exists no causal diagram in the corresponding equivalence class where there is an inducing path between X and Y that is into X. We refer to any edge that is not visible as invisible. The --lower-manipulee replaces all those edges that are out of variables in X but are invisible in G with bidirected edges denoted as Gx. The
of G deletes all edges that are visible and are out of variables in X, and
manipulation of G deletes all those edges in & that are into variables in X denoted as 9x. We denote the set of variables in G by V(g). A subgraph g[V'), where V S VG)) is defined as a vertex-induced subgraph in which all edges among the vertices in V are preserved. We define giX x as (G) X] for X C V(g).
Structural Causal Model. We use structural causal model (SCM) [Pearl, 2000] as the semantical framework to represent the underlying environment a decision-maker is deployed. An SCM S is a quadruple (U, V, F, P(U)), where U is set of exogenous variables determined by factors outside the model following a joint distribution P(U), and V is a set of endogenous variables whose values determined following a collection of functions F VieV such that V; t ft(pa, Uz) where PA, S V \ {Vi} and U, S U. The observational probability P(v) is defined as 2., IIv.v P(e; I pa, ) P(u). Every SCM S is associated with a causal diagram G = (V, E) where a directed edge V. V, E E V, PA,, and a bidirected edge between Vú and Vj if U, and U, are correlated. The
probability of V = V when X is intervened upon to take the value x is denoted by P(v \ x do(x)).
Ancestral graphical structures. Ancestral graphs are designed to capture graph structures without explicitly modeling latent variables. While directed edges between vertices in a causal diagram imply a direct causal effect between them, in ancestral graphs, directed edges instead represent ancestral relationships. Similar to the absence of directed cycles in causal diagrams, ancestral graphs do not permit almost directed cycle, which occurs when X + Y is present while X is an ancestor of Y.
A mixed graph is called a maximal ancestral graph (MAG) if (i) does not contain any directed or almost directed cycles (i.e., ancestral); and (ii) there is no inducing path between any two non-adjacent vertices (i.e., maximal). In general, a MAG repre- sents a set of causal diagrams with the same set of observed variables that entail the same conditional independence and ancestral relations among the observed variables. For each causal diagram, there exists unique MAG over observed variables which represents its marginal independence relations, as well as its ancestral relations. However, a MAG is not fully testable with observational data since distinct MAGs encode the same marginal independence relations. To illustrate, consider the causal diagrams Gn and G2 in Fig. 1. While they yield the same conditional independence relations, they correspond to distinet MAGs, Mi and M2, respectively.
(a) G1
(b) G2
(c) M1
(d) M2
(c) P
Figure I: Causal diagrams (a, b) with corresponding (c. d) MAGs and (c) PAG. visible edge is marked with v.
graph is a partial mixed graph (PMG) if it contains three types of marks: tails (-), arrowheads (>), and circles (o). A circle mark implies an uncertain mark that can be either an arrowhead or tail. In addition, we use an asterisk (x) as a wildcard to denote any possible mark. In a PMG, if every edge mark on path consists of circles, the path is called a circle path, and each edge is called circle edge (o-). An edge is a partially directed edge (o->) ) if it has both circle and arrowhead. A circle component is subgraph of a PMG in which every edge is circle edge. We use the ? mark to emphasize a wildcard that represents either a tail (-) or a circle (o), but not an arrowhead (>). Furthermore, [Q] denotes the set of MAGs represented by the PMG Q, and similarly [M] denotes the set of causal diagrams conforming to the MAG M.
A partial ancestral graph (PAG) denoted by P. is a PMG such that it represents Markov equivalence
class of MAGs. Every MAG M represented by a PAG has the same skeleton as P. and the non-cirele marks in P are identical to those in M. Every circle in P corresponds to a variant mark among the
3

---

represented MAGs. The PAG P in Fig. le, for instance, encodes every MAG obtained by orienting circle marks incident to A and B as either > or -. including both M₁ and M2. In our work, we assume the absence of selection bias; therefore, there is no undirected edge in PAGs and MAGs. Moreover, we assume access to the true PAG that represents the target underlying system. We refer readers unfamiliar with ancestral graphs to Zhang [2006] and Jaber [2022].
Structural causal bandits. We follow the structural causal bandit (SCM-MAB) problem [Lee and Bareinboim, 2018], where an SCM models the target system with which an agent interacts, including a reward variable Y V where Xy S IR. In the SCM-MAB setting, pulling each arm corresponds to intervening on set of variables (x E Xx X S VV (Y)). The mean reward of an arm is denoted by Fix = E|| do(x)] and the best expected reward by intervening on X is fxx* = maXxeXx Px. We denote μ² as the optimal expected reward. The goal of the agent is to minimize the cumulative regret after .V rounds, which is given by Reg,- = ExExx -xxXx,XCVM11) Ax [xX[[x[N)] where Tx(N) denotes
the number of times the arm was played after N rounds, 4x μ¹ Mx and Ex Xxex Ex.
MIS and POMIS. A minimal intervention set (MIS) ensures that there is no proper subset that equivalent to the set with respect to the reward. Lee and Bareinboim [2018] demonstrated that X is an MIS if and only if X S An(Y) For instance, consider G in Fig. 2 where {A, B} is an MIS since {A, B} C. An Taxey holds. In contrast, (A, B, C} is not an MIS since A is not an ancestor of Y in TAABBCT. as depicted in Fig. 2c.
B
B
B
(a) g = 93 (b) 9TABT
(c) TA.B.Cy
Figure 2: MUCT (red) and IB (blue).
A possibly-optimal minimal intervention set (POMIS) is an MIS such that intervening on any non- POMISS cannot yield a better outcome than the optimal one associated with the POMIS. Therefore, an agent who is aware of POMISs should only explore and exploit actions consistent with those sets. When given a causal diagram G, minimal unobserved confounders' territory (MUCT) and interventional border (IB) [Lee and Bareinboim, 2018] provide graphical characterization of POMIS. MUCT the minimal set of variables that (i) contains the reward variable Y; and (ii) is closed under descendants and bidirected edge connections; and IB consists of the parents of MUCT, excluding MUCT itself. We defer the formal definitions to Appendix B. Intuitively, MUCT is the minimal closed mechanism that conveys all hidden information from unobserved confounders to the downstream reward, while IB consists of the nodes that directly affect this closed mechanism. Let us denote MUCT and IB with respect to [G, Y] as MUCT(G, Y) and IB Y), respectively. Leveraging these, the authors showed that ( 9g. Y) = X provides a complete characterization of POMISs. For example, Figs. 2a and 2b show MUCT and IB for the subgraphs Go and (TABB-- The do-nothing action (do( is not a POMIS since MUCT T. Y) = (C, }} implies IB Y)- = {AA,B). not 0. while the set {4, B} is a POMIS since MUCT(G (a.B). Y) = D.Y). implying (B(9 Y) = B).
3 Generalizing Minimal Intervention Sets
We first generalize minimal intervention set (MIS) cover not only causal diagrams but also ancestral graphs, aiming to identify all sets that do not include variables irrelevant to the reward by ruling them out, referring to MAGS or PAGs. In the following parts, we first provide complete graphical conditions for MIS in terms of MAGS and PAGs. Surprisingly, we then show in Sec. 3.1 that an MIS may include variables irrelevant to reward when dealing with PAGs. To address this issue, in Sec. 3.2, we propose the concept of definitely minimal intervention set (DMIS), which ensures that no further variables can be pruned, thereby aligning with the intuitive notion of minimality.
We use D to refer to either a causal diagram or an ancestral graph (MAG or PAG) over V. We denote by x[W) the values of x restricted to the subset of variables in W n X.
Definition I (Minimal intervention set (MIS)). Given information [D. YY, a set of variables X C V \ {Y} is called a minimal intervention set (MIS) relative to [D, Y] if there is no X' Ç X such that Mx[x]] Xx for every SCM conforming to D.
Proposition Let M be MAG over V. A set X C V (Y) is an MIS relative to [M, YJ if and only if there exists causal diagram & conforming M such that X is an MIS relative [G.Y]. Yl.

---

The proposition guarantees the existence of a causal diagram G where X is an MIS relative to [G, Y], provided that X is an MIS relative to [M, Y] for the given MAG M. We now proceed to the graphical characterization of MIS for MAGs, in manner similar to causal diagrams, utilizing the explicit ancestral relations among variables in MAGs and Rule of do-calculus for MAGS, i.e., Mxz Px if Z and Y are m-separated in My [Zhang, 2008b].
Theorem 1 (Characterization of MIS for MAGs). Let M be MAG over V. Given information [M, YI, a set X C V. } is an MIS relative to [M,Y] and only if X S An MM holds.
For example, consider g' and M in Figs, 3a and 3b where g' E [M]. A set (A,B,C } is an MIS relative to [M, Y] since (A, C) An(Y) MTTM,) holds.
Remark 1. Even though set X is MIS with respect to Y, there is guarantee that X is an MIS with respect to [[] Y1 for every causal diagram G conforming to M.
The set (A, B, C} also an MIS relative to [g', Y] in Fig. 3a since (A, M, C An T..
holds. However, while 9 in Fig. 2a is also represented by M, it is not an MIS with respect to [G. YI.
3.1 MIS for PAGs and Its Possible Vacuousness
We proceed to the characterization of MIS for PAGs. Unfortunately, we cannot similarly rely on Rule 3 for PAGs (Jaber et al. [2022]; see Thm. in Appendix B) because the rule is applied when ancestral relations are apparent for all represented models, whereas a PAG might involve uncertainty reflected by circle marks one may easily surmise that {X, Z) is not MIS in PAG X o-o Z o-o Y, but Rule 3 remains silent on this case.
B
B
(a) g'
(b) M
(c) M \ {A, B}
Figure 3: (a) Causal diagram; and (b) MAG repre-
senting both causal diagrams g' and G in Fig. 2a.
Hence. we utilize specific type of path: A proper possibly-directed path from X E X to Y with
(c) Induced graph of M over V \ {A, B3.
respect to X, where only the first node X is in X. This path is not disturbed by other intervening variables, thus aligning with the characterizations of MISs for causal diagrams and MAGs.
Proposition (Graphical characterization of MIS for PAGs). Let P be a PAG over the set of variables V. A set X C V (Y} is MIS relative to [P, Y1 if and only if. for every variable X X. there exists a proper possibly-dine directed path from X to with respect to X in P.
Possible vacuousness. One might expect that if X is an MIS relative to [[P Y], then it would also be an MIS relative to [M, Y] for some MAG M conforming to the PAG P. However, this is not always the case and no SCM may regard X as an MIS with respect to [.MY]]
For concreteness, consider the PAG P in Fig. where {A, B} is an MIS with respect to [[, Y] since each A and B has proper possibly-directed paths to Y (i.e., A o-o Y and B o- Y- respectively). However, we will demonstrate that at least one of A or B is irrele- vant to reward Y in every conforming MAG. To see this, we construct SCMs where the domains of vari- ables are binary and VUve(U,, UUy P(Uv 1)
B
(a) P
(b) M1
(c) M2
(d) Ms
Figure 4: M, and M2 are represented by P. In contrast, M3 is not represented by P.
e = 0. For proper subset X (A), we can construct an SCM S₁ following that the mechanism for Y in Sj is defined as fy = b e uy, and the mechanism for B is fB ug where ① denotes the exclusive-or operator. Then, j = 14g 2c(1 c) while ja,b- = 146-
with 8" 1. Thus, we find that Ma.b- > Ma holds in S,. This construction can be done for each proper subset of [A, B}. validating (A, B) is an MIS relative to [P, YI. However, the remarkable point here is that there is no representative SCM S" that satisfies Mx[x'] + μx for arbitrary proper subset X' Ç X, as doing so would require the mechanism fy to depend on the values of both A and B. This setup would introduce an uncovered collider at Y (i.e., A Y + B and A & Adj AB)( in the underlying graph
"The inducing path A + C ++ Y in G appears A Y in M since C' is ancestor of Y in G.
5

---

of P, leading to inconsistency with the structure of P. Therefore, we observe that {4, B} is an MIS with respect to [P, Y]. but least one of or B is irrelevant to reward Y in all conforming MAGs.
3.2 Definitely MIS and Its Characterization
To address this vacuousness, we propose the concept of definitely MIS, which ensures that an MIS in PAG remains an MIS in some consistent MAG. With the definition of MIS, we first choose X' Ç X, and then check whether Mx[X"] o Jxx holds across all SCMs conforming to D; here, we first choose an SCM S conforming to D, then examine whether the inequality holds across all subsets X'.
Definition 2 (Definitely minimal intervention set). Given information [D, YP,Y,, set X V (Y) is called a definitely minimal intervention set (DMIS) relative to [D. Y]. denoted by DD, if there exists an SCM compatible with D such that, for every proper subset X' Ç X, [x[x"] # 2y holds.
Proposition X is a DMIS with respect to [D,Y] then is an MIS with respect to [D,
Proof. Let S be an SCM associated with DD such that Mx(x) # Px holds for every X' ç X. For all proper subsets, such an S certifies that X satisfies the definition of MIS.
O
Proposition 4. Let D be either a causal diagram or MAG (i.e,, not PAG). X an MIS with respect to [DD Y1, then X is a DMIS with respect to [D, YI.
Proof sketch. We can construct an SCM S where all mechanisms consist of the sum of the values of their parents, which ensures that X is DMIS.
n
This equivalence between MIS and DMIS for a causal diagram or MAG (Props. and 4) is derived from determined ancestral relations, X C An We now move on to discuss DMIS for PAGs,
where ancestral relations are undetermined, suggesting a notable gap between MIS and DMIS. Recall the PAG P in Fig. 4a, where {A, B} is an MIS but not a DMIS with respect to [P,Y].
Proposition& 5. Let P be a PAG over V. A set X CVV \ only if there exists a MAG M conforming P such that X is an MIS relative [M, Y]
(Y} is a DMIS relative to [P,Y] if and
Hence, DMIS provides a truly feasible space for actions associated with intervention sets that no longer contain variables to rule out. According to Props. 3 and 4, we focus on establishing the graphical criterion for DMIS only for PAGs. In Fig. 4a, we have observed that A oo and B Bo-oY Y cannot both be an ancestor of Y at the same time due the uncovered path Ao-oY Y o-o B. To this end, we devise the notion of relevance among edges in a PAG.
Definition 3 (Relevant edges). Let P be PAG. For any edges ( +-* +2) and (2(Vn-1 + Vnn). we say that E, is relevant to 62 in P if there exists an uncovered path Vi a V/2 o........0 Vn- 0 V, with n 2 in P.
Theorem 2 (Graphical characterization of DMIS for PAGs). Let P be PAG over the set of variables
V. A set X C (Y) is DMIS relative to [P, Y if and only if. for any pair of vertices X, Z E X. there exist uncovered proper possibly-directed paths from X and Z Y with respect to X such that their starting edges are not relevant.
Consider the PAG P shown in Fig. 5, where A Ao-oC C and Do-o Y are relevant in P because of the path Ac-o lo-oo-oo o-o D. The key point here is that all triplets along the path are definite non-colliders so that the end nodes cannot be simultameously ancestors of non-end nodes. Fur- thermore, consider any MAGs represented by P where A a-o C appears as a directed edge out of A (e.g., Mi and M2). Clearly, this results in C' -+1 y + D, as the path is of definite status. In contrast, if any MAG contains D > Y, this leads to Y C A, as in M3- The important observation is that A - C ensures D & An(Y)) and + Y ensures A & AY()) for all MAGs M represented by P. This indicates that A and D cannot simultancously be ancestors of Y in M, thus {A, D} is not a DMIS relative to [P, Y].
(a) P
(b) Mi
(c) M2
(d) Ma
Figure 5: The nodes in the light blue region are the ancestors of Y. The three MAGs are represented by the PAG P.

---

4 Possibly Optimal Minimal Intervention Sets
We now refine the possibly-optimal minimal intervention set over DMISs rather than MISs. This refinement guarantees the existence of an underlying SCM compatible with a PAG and implies the following proposition. Note that the refined POMIS exactly matches established studies and serves as a natural extension, supported by Props. 3 and 4, which state that MIS and DMIS coincide in causal diagrams and MAGs.
Definition 4 (Possibly-optimal minimal intervention set (POMIS)). Let X C V \ (Y) be DMIS relative to [D, YJ If there exists an SCM conforming to D such that /xx- >> VWEDD, ((X)/w" then X is possibly-optimal minimal intervention set (POMIS) relative to [D,Y].
Proposition 6. Let P be PAG over V. A set X S V (Y) is a POMIS relative to [P, Y1 if and only if there exists a MAG M conforming to such that X is POMIS relative to M.
We investigate into the graphical characterization of POMISs for MAGs and PAGs. The main challenge in characterizing POMIS for ancestral graphs lies in the fact that induced paths by latent variables (or UCs) do not explicitly appear, which makes it impossible to directly identify the unobserved confounders' territory as for causal diagrams. Instead, we leverage edge's ' visibility which indicates that the edge is not confounded in any underlying causal diagram (Lem. 2 in Appendix B for details). To generalize the UC-territory, we introduce a possible c-component, which provides a necessary condition for nodes to belong to the same e-component in underlying causal diagram.
Definition 5 [pe-component [Jaber et al., 2018]). Two nodes are in the same possible c-component (pe-component) if there is a path between them such that (i) all non-endpoint nodes along the path are colliders, and (ii) none of the edges are visible.
We denote the pe-component of a partial mixed graph (PMG) Q containing X as PC(X) and P - Uxex p) For example, A and B are in the same pe-component in P of Fig. le because they are connected through an invisible colliding path A a-> C to B, i... PC(AA) = {A, B, C). Furthermore, due to A & PC(Y)p e-component in any causal diagrams conforming to P. We now generalize MUCT and IB for PMGs.
{B, }J. A and Y cannot belong to the same
territory for PMGs). Given information [2,Y] and inter- vention set X S V (Y), let H = Q(PossAn(Y)) \ X]. A set of variables T C PossAn (Ys) X containing Y is called UC-territory on Q with respect to Y if PossDe (T) R = T and PC T. A UC-territory T is called a minimal UC-territory (MUCT) if no T T is UC-territoyy
Definition 6 (Unobsereed-coffouddee)
Definition 7 (Interventional border for PMGs). Let T be a minimal UC-territory with respect to [2, Y, x]. Then Pa(T) e T is called an interventional border (IB) with respect to [Q,Y X].
For concreteness, consider M and X = {A, B} in Fig. 3. Here, we omit Poss, as we discuss in the context of MAG. Let H be the induced graph M[Ann(Y), \ X]. In H. the nodes C and Y are the same pe-component, and D is a descendant of C. This implies that T = {C, D, Y} is the minimal closed set for DeH and PCH, leading to IB(M, Y, X)= = (A, BJ3 derived from Pa Pa (T) \ T.
4.1 Characterization of POMIS for MAGs
With the MUCT and IB for PMGs established, we are now ready to characterize POMISS for MAGs. Theorem 3 (Graphical characterization of POMIS for MAGs). Let M be a MAG over the set of variable V. A set X C V \ (Y) is a POMIS relative to [[, Y1 if and only if X IB(M, Y X).
For example, consider the MAG M in Fig. 3c where IB(M, Y, [A, = {A, B} holds. Therefore, we get that (A, B} is a POMIS with respect to [M, Y]. Indeed, as previously shown, G in Fig. represented by M and {A, B} is POMIS with respect to [[, Yl.
4.2 Characterization of POMIS for PAGs.
The remainder of the main body focuses on characterizing POMIS for PAGs. We first present necessary conditions for a PMG to represent MAGs M in which X is a POMIS relative to [M, Y].
We denote MUCT and IB with respect to [Q, Y, xX as MUCT(Q, Y, X) and IB Q Y, X), respectively.
7

---

Algorithm 1: Identify whether a given set is a POMIS for PAG.
function IsPOMIS(P, Y, X)
Input: P: PAG, Y: reward, X: Intervention set 2 given does not satisfy Thm. 2 then return False
Let Qx be PMG oriented from P with X according to Prop. 7.
return SublsPOMIS( X {Y), Y,
5 function subisPOMIS A, YYX X)
if A is empty then return (B(2, Y, X) =
7
f Pick a node from A.
8
for each set C {V E ( Ac-* } do
if CR satisfies Thm. 7 (i.e., check validity of local transformation) and
9
Y FosaDe(A) then
Let Q' be the PMG obtained by orienting the circle marks around A following C and completing the orientation rules from Q. if sublsPOMIS Q', A {A}. Y, then return True
10
11
12
return False
Proposition 7. Let Qx be a PMG representing MAGs where X is POMIS with respect to Y. Then, the following properties hold in 2x. every X X:
1. Every uncovered proper possibly-directed path from X to Y relative to X ends with arrowhead (>).
2. If X is adjacent to Y, then the edge between X and Y is directed edge (X + YY).
Put simply, violating these conditions introduces an almost directed cycle directed cycle. To characterize POMIS for PAGs, we partition [2x] based on the orientation of circle marks incident on XU {Y). We refer to local transformation [Wang et al., 2023b] C C {V E AA) Aoss V} as the vertices whose edges with a circle A (i.e., Ao- V in Q) will be oriented with arrowheads at A (i.c., A ++ V); all remaining edges A a-* V will be oriented as A + V'.
Proposition 8. For every MAG M E [2x]. if is POMIS relative to [M,Y] then there exists PMG Qx representing M such that the following conditions satisfied:
1. Every circle mark around X (Y) in Qx is oriented as either a tail (-) or an arrowhead (>) in Øxx according to valid local transformations.
2. Every X E X is an ancestor of Y in Oxx-
3. Q closed under orientation rules."
In words, Ø'x is
oriented PMG instance derived from Qx by applying the valid local transformations for circle marks around X (Y). along with the orientation rules, while confirming that X an ancestor of Y in all MAGs M [ For clarity, recall the PAG P in Fig, 5a with a DMIS X {C). Here, every MAG M [P] satisfying that {C) is a POMIS conforms Qiey in Fig. 6a. Each 2/cy (Fig. 6b; corresponding
(a) Q(c)
(b) Cicy
(c) Hiyy
Figure 6: The light blue region indicates possible ancestors of Y.
C (2 [B) and CO 1 (BB) and Licy (Fig. 6c;
corresponding to CR(0) =0 and C 2())) (c) =(A}) illustrates PMG where local transformations for C and Y are oriented, and both graphs closed under the orientation rules.
For example, C = 0 with c = B} is invalid local transformation, as it implies Y + B a- C - Y which introduces either directed almost directed cycle. The complete graphical criterion of the [2023b] presented in Thm. Appendix B. 'The orientation rules refer to R, Ra. R2, RR-Ro R and Ras. R₃ are not considered since we assume selection bias. Further details regarding the orientation rules provided in Appendix B.
validity of proposed by Wang

---

Theorem 4 (Characterization of POMIS for PAGs). A set X SVV (Y) is POMIS relative to [P.Y] if and only if there exists O' satisfying Props. and such that IB( Y. Y. X.
The key observation is that local transformations restricted to X are sufficient for this determi- nation, thereby circumventing the need to enumerate all MAGs represented by the given PAG. To witness, consider Scc with X {C} in Fig. 6b where IB( c/ Y, X) X holds, and it follows that {C] is POMIS with respect to [P, Y1. Indeed, we can find MAG instance M by orienting the circle marks around B in Lccy as tails, in which IB(M, Y, X) X (Thm. 3) also holds.
4.3 Algorithmic Approach: Enumerating POMISS
We now present algorithm IsPOMIS (Alg, 1), through which we can determine whether given set X is a POMIS relative to [P. Y1 based on our theoretical results (Thms. and 4).
Theorem (Soundness and completeness). The algorithm IsPOMIS (Alg. 1) returns True if and only if there exists MAG .M conforming to P such that X is POMIS relative to [M,Y].
The algorithm begins by checking whether the given set X is a DMIS (Line 2). X is identified as a DMIS, it then infuses the necessary condition in Prop. 7 (Line 3). Subsequently, the local transformations for X U } are oriented recursively within sublsPOMIS. During each recursion, evaluates the validity of a local transformation around vertex and the ancestral relations between the vertex and the reward Y (Line 9). The PMG is updated based on local transformations and orientation rules (Lines 10-11). Finally, in the base case (Line 6). the algorithm checks whether the fully-oriented PMG O' satisfies IB( Oxx Y,X) = X based on Thm. 4.
Runtime analysis. In the algorithm, Line runs in ((VV)3) time, using standard reachability algorithm. Each local transformation (Line 8) requires ((2P) space, where p V denotes the number of circle marks around the current vertex. Both the validation of local transformations and the check for ancestral relations (Line 9) take ((VV))) [Wang et al., 2023b].
Identifying all POMIS sets requires checking all subsets of V \ (Y) using IsPOMIS (Alg. 1), and thus the size of the search space grows exponentially. However, since all non-DMIB sets are filtered out in Line the enumeration process effectively depends only on the number of DMISs
A naive approach is to enumerate all possible MAGs M that conform to given PAG, and verify whether IB(M, Y.X) X) X holds for each M. However, this method presents analytical challenges in terms of complexity- the enumeration process may generate many duplicate MAGs, and it is difficult determine when the transformation should terminate. Even under optimistic assumptions namely, that no duplicate MAGs are produced and that an oracle informs us when all MAGs consistent with the PAG have been generated- the number of such MAGs remains super--xponentially large [Zhang, 2012, Wang et al., 2023a]. Even when adopting MAGLIST [Wang et al., 2024a]. which systematically enumerates MAGs via local transformations, its worst-case complexity remains higher than ours, as it performs transformations over the entire set V, whereas IsPOMIS constructs only distinct PMGs Ø oriented through local transformations around X U (Y} C V for a DMIS X.
Experiments
We evaluate the cumulative regrets (CR) of SCM-MAB under different strategies to assess the effect of employing POMIS for PAGs (Fig. 7). The number of trials is set to 10,000 for Tasks 1 and 2, and 5,000 for Task which is sufficient to observe performance differences. Each simulation is repeated 1,000 times to obtain consistent results. We compare three arm-selection strategies: POMISS (pink), DMISs (purple), and Brute-force (BF; green), each combined with two prominent solvers: Thompson Sampling (TS) and KL-UCB. In the Brute-force strategy (i.e., without causal knowledge), all possible combinations of arms are evaluated: that is, the number of possible intervention sets of BF 2 V|-1 and the total number of corresponding arms is E (IVI-I) K = (K + 1) where K denotes the cardinality. We assume that all variables are binary for simplicity (K" = 2).
AAthhough Lee and Bareinboim [2018] provided an efficient algorithm for enumerating all POMISs in a causal diagram by leveraging topological order, such an approach is not applicable to PAGs, where the topological order is not determined.

---

POWS
2530
PC4B
006-
DV15
DM4
100-
750
1530
1230
252-
130
106
T1a
Traas
(a) Task
(b) Task 2
(c) Task 3
Figure 7: 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.
The underlying model mechanisms randomly generated by combining binary logical operations, and the exogenous variables are set to follow Bernoulli distributions whose parameters are randomly selected over (0, 1). Additional details and experiments are provided in Appendix D.
Task 1. The deployed agent can only access the PAG P in Fig. 5a to obtain DMISs and POMISS. The environment in which agent interacts consistent with P. Using three strategies (BF: 81 arms, DMIS: 25 arms, POMIS: 19 arms), the POMIS-based TS and KL-UCB achieve CRs of 123.4 and 243.4, which correspond to 39.3% and 48.9%, respectively, of CR for BF.
visible
Figure 8: Six variables.
Task 2. We consider the PAG in Fig. 8 to validate our result. Using three strategies (BF: 243 arms, DMIS: 195 arms, POMIS: 85 arms), the POMIS-basee TS and KL-UCB achieve CRs of 320.9 and 629.9, which correspond to 44.3% and 50.4%, respectively, of CR for BF.
Task 3.
We consider more involved scenario (Fig. 9) to validate our result. Using three strategies (BF: 19683 arms, DMIS: 2025 arms, POMIS: 54 arms), the POMIS-basee TS and KL-UCB achieve CRs of 60.3 and 52.0, which correspond to only 2.5% and 2.1% %, respectively, of CR for BF. Notably, the size the POMIS arms accounts for only 19683 of that of the BF. We observe that the superiority of POMIS remains consistent regardless of the solvers used. All CRs and the numbers of sets and arms are provided in Tables and 2 in Appendix D. These results demonstrate that refining arms by taking into account the Markov equivalence class represented by PAG enhances the efficiency of agents.
54 0..7%%
Figure 9: Ten variables.
6 Conclusion
We proposed novel structured causal bandit strategy (SCM-MAB) in the context of ancestral graphs. We first provided graphical characterization MIS for MAGs and PAGs. We then demonstrated the vacuousness of MIS, i.e., that some MISs for PAG are not MISs of any MAG consistent with that PAG. To address this, we introduced the notion a definitely minimal intervention set (DMIS), which guarantees the existence of an underlying SCM, thereby aligning with the general intuition behind the concept of MIS. Finally, we refined the concept of POMIS over DMIS from MIS and provided a complete characterization of POMIS for MAGs and PAGs, along with algorithm for enumerating all POMISS given a PAG. We believe these results have practical implications for the design of intelligent agents, providing foundation for optimizing the action space when the environment is not fully accessible but is abstracted as a Markov equivalence class.
Acknowledgments and Disclosure of Funding
This work was supported in part by NSF, ONR, AFOR, DOE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation. Min Woo Park and Sanghack Lee were partly supported by the ITTP (RS-2022--12220555/55. RSS-2025-0226355425262 00222663/25%) grant funded by the Korean govermment.
and NRF (RS-2023-0021 1904/25%, RS-2023-
10

---

References
Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Virginia Aglietti, Xiaoyu Lu, Andrei Paleyes, and Javier González. Causal bayesian optimization. In International Conference 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-39.26. JMLR Workshop and Conference Proceedings, 2012.
R Ayesha Ali. Towards characterizing Markov equivalence classes for directed acyelic graph models with latent variables. Proc. Conf. on Uncertainty Artificial Intelligence (UAI-05), pages 10-17, 2005.
Bryan Andrews, Peter Spirtes, and Gregory F Cooper. On the completeness of causal discovery the presence of latent confounding with tiered background knowledge, In International Conference on Artificial Intelligence and Statistics, pages 4002-4011. PMLR, 2020.
Alexander Balke and Judea Pearl. Counterfactuals and policy analysis in structural models. In Proceedings of the Eleventh conference on Uncertainty artificial intelligence, pages 11-18, 1995.
Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: causal approach. In Proceedings of the 28th Annual Conference on Neural Information Processing Systems, pages 1342-1350, 2015.
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 pettps:/ccausalee www.eee.......e. pdf.
Alexis Bellot. Towards bounding causal effects under markov equivalence. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
Alexis Bellot and Silvia Chiappa. Towards estimating bounds the effect of policies under unobserved confounding. Advances Neural Information Processing Systems, 37:104556-104594 2024.
Shriya Bhatija, Paul-David Zuercher, Jakob Thumm, and Thomas Bohné. Multi-objective causal bayesian optimization. arXiv preprint trXiv:2502.14755. 2025.
Blair Bilodeau, Linbo Wang, and Dan Roy. Adaptively exploiting d-separators with causal bandits. Advances in Neural Information Processing Systems, 35:20381-20392. 2022.
Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pages 1516-1541, 2013.
Ryan Carey, Sanghack Lee, and Robin J Evans. Toward a complete criterion for value of information in insoluble decision problems. Transactions on Machine Learning Research, 2024.
Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 444--4422 2012.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(N5v):507-554, 2002.
Davin Choo and Kirankumar Shiragur. Adaptivity complexity for causal graph discovery. In Uncertainty in Artificial Intelligence, pages 391-402. PMLR, 2023.

---

Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high- dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages 2 2012.
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-421 PMLR, 2022.
Gabriel Andrew Dirac. On rigid circuit graphs. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 25, pages 7 71-76. Springer, 1961.
Wen-Bo Du, Tian Qin, Tian-Zuo Wang, and Zui-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-Y Lei, Lue Tao, Tian-Zuo Wang, and Hui-Hua Zhou. Enabling optimal decisions in rehearsal learning under care condition. In Forty-second International Conference Machine Learning, 2025.
Muhammad Qasim Elahi, Mahsa Ghasemi, and Murat Kocaoglu. Partial structure discovery is sufficient for no-regret learning in causal bandits. arXiv preprint 1.Xiv:241..0005:: 2024a.
Muhammad Qasim Elahi, Lai Wei, Murat Kocaoglu, and Mahsa Ghasemi. Adaptive online experi- mental design for causal discovery. arXiv preprint 1rXiv:2405.11540 2024b.
Tom Everitt, Ryan Carey, Eric D Langlois, Pedro A Ortega, and Shane Legg. Agent incentives: A causal perspective. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11487-11495, 2021.
Shi Feng and Wei Chen. Combinatorial causal bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 7550-7558, 2023.
Shi Feng, Nuoya Xiong, and Wei Chen. Combinatorial causal bandits without graph skeleton. arXiv preprint arXiv:2301.13392 2023.
Andrew Forney, Judea Pearl, and Elias Bareinboim. Counterfactual data-fusion for online reinforce- ment learners. In Doina Precup and Yee Whye Tch, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1156-1164. PMLR, 06-11 Aug 2017. URL https: forney17a.html
https:tt//occeeeeeeeie pttp///eeecce...eeeeee//e/c/..ep mll wttpiiisssmm....ess/eeeee www.ppresssvo
Aurélien Garivier and Olivier Cappé. The kl-ueb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Kun Zhang. Learning causal structures using regression invariance. Advances in Neural Information Processing Systems, 30,
2017.
AmirEmad Ghassami, Negar Kiyavash, Biwei Huang, and Kun Zhang. Multi-domani causal structure learning in linear systems. Advances in neural information processing systems, 31, 2018.
Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. Elsevier, 2004.
Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. Advances in Neural Information Processing Systems, 32, 2019.
Michel Habib, Ross Mac Connell, Christophe Paul, and Laurent Viennot. Lex-bfs partition refining technique, application to transitive orientation and consecutive I's testing. Theoretical Computer Science, 234, 2000.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes directed acyelic graphs. The Journal of Machine Learning Research, 13(1): 2409-2464, 2012.
12

---

Christina Heinze- Deezle Jonas Peters, and Nicolai Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018.
Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romerg Clark Glymour, and Bernhard Schölkopf. Causal discovery from hederogeneous/nonsattionyyy data, Journal of Machine Learning Rexearch, ((88))1-533 2020.
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 on Machine Learning, pages 20842-20870, PMLR, 2024.
Amin Jaber. Causal Reasoning in Equivalence Classes. PhD thesis, Purduc University Graduate School, 2022.
Amin Jaber, Jiji Zhang, and Elias Bareinboim. Causal identification under Markov equivalence. In Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, 2018.
Amin Jaber, Adele Ribeiro, Jiji Zhang, and Elias Bareinboim. Causal identification under Markoy equivalence: calculus, algorithm, and completeness. Advances in Neural Information Processing Systems, 35:3679-3690, 2022.
Yonghan Jung and Alexis Bellot. Efficient policy evaluation across multiple different experimental datasets, Advances in Neural Information Processing Systems, 37:136361-136392 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.
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. Advances in Neurul Information Processing Systems, 30, 2017.
Mikhail Konobeev, Jalal Etesami, and Negar Kiyavash. Causal bandits without graph learning. arXiv preprint arXiv:2301.11401, 2023.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interventions via causal inference. Advances in neural information processing systems, 29, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? Advances in neural information processing systems, 31, 2018.
Sanghack Lee and Elias Bareinboim. Structural causal bandits with non-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, 33:8565
8575666--777,, 8576, 2020.
Lihong Li. Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670 2010.
Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit prob- lems with causal background knowledge. In Conference on Uncertainty in 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.
13

---

Marloes H Maathuis and Diego Colombo. A generalized back-door criterion. The Annals of Statistics, 4363):1000-1088, 2015.
Marloes Maathuis, Markus Kalisch, and Peter Bühlmann. Estimating nigh-dimensional intervention effects from observational data. The Annals of Statistics, pages 3133-3164, 2009.
Alan Malek, Virginia Aglietti, and Silvia Chiappa. Additive causal bandits with unknown graph. In International Conference Machine Learning, pages 23574-23589, PMLR, 2023.
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 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, 1995a.
Judea Pearl and James Robins. Probabilistic evaluation of sequential plans from causal models with hidden variables. In Proceedings of the 1 Ith Conference Uncertainty in Artificial Intelligence, pages 444-453. Morgan Kaufmann Publishers Inc., 1995b.
Emilija Perkovic, Johannes Textor, Markus Kalisch, Marloes H Maathuis, et al. Complete graphical characterization and construction of adjustment sets in Markov equivalence classes of ancestral graphs. Journal of Machine Learning Research, 18(220):1-6) 2018.
Ronan Perry, Julius Von Kügelgen, and Bernhard Schölkopf. Causal discovery in heterogeneous environments under the sparse mechanism shift hypothesis. Advances in Neural Information Processing Systems, 35:10004-10917, 2022.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 78(5):947-1012, 2016
Tian Qin, Tian Wang, and Zhi-Hua Zhou. Rehearsal learning for avoiding undesired future. Advances in Neural Information Processing Systems, 36:80517-80545 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, 2025.
pages
Amy Richardson, Michael G Hudgens, Peter B Gilbert, and Jason P Fine. Nonparametric bounds and sensitivity analysis of treatment effects. Statistical Science, pages 596-618, 2014.
Thomas Richardson and Peter Spirtes. Ancestral graph Markov models. The Annals of Statistics, 30 109992210300 2002.
Herbert Robbins. Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc., 58 (5):527-535, 1952.
Raanan Rohekar, Shami Nisimov, Yaniv Gurwicz, and Gal Novik. Iterative causal discovery in the possible presence of latent confounders and selection bias. Advances in Neural Information Processing Systems, 34:2454-2465, 2021.
Raanan Yehezkel Rohekar, Shami Nisimov, Yaniv Gurwicz, and Gal Novik. From temporal to contemporaneous iterative causal discovery in the presence of latent confounders. In International Conference on Machine Learning, pages 99939-39950.. PMLR, 2023.
Donald Rose, R Endre Tarjan, and George Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal computing. 5(2):266-283, 1976.
14

---

Peter Spirtes and Thomas S. Richardson. A polynomial time algorithm for determining dag equiva- lence in the presence of latent variables and selection bias. In David Madigan and Padhraic Smyth. editors, Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics, volume R1 of Proceedings of Machine Learning Research, pages 489-500. PMLR, 04-07 Jan 1997. URL https:://///. http///poceeednn/e///ee/ mlr wwt..peeesss/seeeeeee http://rsspptttt9/9/// htmml. Reissued by PMLR on 30 March 2021.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. MIT press. 2001a.
Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT Press, 2nd edition, 2001b. ISBN 9780262194402
Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems, 1-225500221511 2020.
Lue Tao, Tian-Zuo Wang, Yuan Jiang, and Zhi-Hua Zhou. Avoiding undesired future with sequential decisions. pages 6245-6253, 09 2025. doi: 2...4996/jjcai..225565555
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of samples. Biometrika, 25(3-4):285-944, 1933.
Jin Tian and Judea Pearl. A general identification condition for causal effects. In Proceedings of the 18th National Conference on Artificial Intelligence, pages 567-573, 2002.
Ioannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine learning, 65:31-78, 2006.
Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Causal bandits for linear structural equation models. Journal of Machine Learning Research, 24((97):1 2023.
Aparajithan Venkateswaran and Emilija Perković. Towards complete causal explanation with expert knowledge, arXiv preprint arXiv:2407.07338, 2024.
Thomas Verma and Judea Pearl. Equivalence and synthesis of causal models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, pages 255-270, 1990.
Tian-Zuo Wang, Tian Qin, and Zhi-Hua Zhou. Sound and complete causal identification with latent variables given local background knowledge. Advances in Neural Information Processing Systems, 35:10325-10333 2022.
Tian-Zuo Wang. Tian Qin, and Zui Zhou. Estimating possible causal effects with latent variables via adjustment. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 36308-36335. PMLR, 23-29 Jul 2023a. URL petttss:/pproeeeee .mw.iiinng..m......mmm.m...m.... mmr. wewt.press/vve hvtp://22//eeeee 20000//aa23aagg html.
Tian-Zuo Wang, Tian Qin, and Zhi-Hua Zhou. Sound and complete causal identification with latent variables given local background knowledge. Artificial Intelligence, 322: 103964, 2023b.
Tian Wang. Wen-Bo Du, and Zhi-Hua Zhou. efficient maximal ancestral graph listing algorithm. In Forty-first International Conference on Machine Learning, 2024a.
Tian-Zuo Wang, Lue Tao, and Zhi-Hua Zhou. New rules for causal identification with background knowledge, 2024b. URL httpht/t////// //axxiv. wttpaaawww.aaaaaaaaaaaaaaa org/ ha/aab//2200 2200 15259.
Tian-Zuo Wang, Wen-Bo Du, and Hui Zhou. Polynomial-delay mag listing with novel locally complete orientation rules. In Forty-second International Conference on Machine Learning, 2025a.
Tian-Zuo Wang, Lue Tao, Tian Qin, and Zhi-Hua Zhou. Estimating possible causal effects with latent variables via adjustment and novel rule orientation. Artificial Intelligence, page 104387, 2025b.
15

---

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:688 0--8882, 2023.
Marcel Wienöbst, Max Bannach, and Maciej Liškiewicz. A new constructive criterion for Markov equivalence of MAGs. Proceedings of the Eightt Conference on Uncertainty in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pages 2107-2116. PMLR, 2022. URL https: http////ooeeeeenneeeeeeeeeeeesee mlr wpwps/vee0000 hwtp://iiinnnntneeeeeeeeeee html.
Zirui Yan and Ali Tajer. Linear causal bandits: Unknown graph and soft interventions. Advances in Neural Information Processing Systems, 37:23939-23987, 2024.
Yan Zeng, Shohei Shimizu, Ruichu Cai, Feng Xie, Michio Yamamoto, and Zhifeng Hao. Causal discovery with multi-domain lingam for latent factors. In Causal Analysis Workshop Series, pages 1.4. PMLR, 2021.
Jiji Zhang. Causal inference and reasoning in causally insufficient systems. PhD thesis, Citeseer, 2006.
Jiji Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence. 172(16):1833-189, 2008a. ISSN 0004- 3702. doi: com/ htt.a//ceeaarttrae///////////020
08.001. URL hwtph:tt////wet scwencedirect..
Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9:
1437-1474, 2008b.
Jiji Zhang. characterization of markov equivalence classes for directed acyclic graphs with latent variables. arXiv preprint arXiv: 1206.5220 2012.
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. 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 Bareinboim. Bounding causal effects on continuous outcome. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12207-12215, 2021.
Junzhe Zhang and Elias Bareinboim. Online reinforcement learning for mixed policy scopes. Advances in Neural Information Processing Systems, 35:3191-3202, 2022.
Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. In International conference machine learning, pages 26548 225588.. PMLR, 2022.
Hui Zhao, Zhongguo Zheng, and Baijun Liu. On the Markov equivalence of maximal ancestral graphs. Science in China Series A: Mathematics, 48:548-562, 2005.
Zihan Zhou, Muhammad Qasim Elahi, and Murat Kocaoglu. Characterization and learning of causal graphs from hard interventions. arXiv preprint arXiv:2505.01037,2225 2025.
16

---

Contents
1
Introduction
2 Preliminaries
3 Generalizing Minimal Intervention Sets
3.1
MIS for PAGs and Its Possible Vacuousness Definitely MIS and Its Characterization
3.2
4
Possibly Optimal Minimal Intervention Sets
4.1
Characterization of POMIS for MAGs
4.2
Characterization of POMIS for PAGs.
4.3
Algorithmic Approach: Enumerating POMISs
5
Experiments
6
Conclusion
10
Related Works
18
B
Additional Preliminaries and Background Results
19
B.1
Additional Preliminaries
19
B.2
Background Results
23
B.2.1
Background Results in Zhang [2006, 2008a]
23
B.2.2
Background Results in Maathuis and Colombo [2015] ...........
24
B.2.3
Background Results in Perkovic al. [2018]
24
B.2.4
Background Results in Jaber et al. [2018. _0..............................
24
B.2.5
Background Results in Wang al. [2023b, 2024a]
25
Assumptions
26
Experimental Details and Additional Results
26
E
Discussions
29
E.1
Partial Mixed Graphs Obtained from Local Transformation
29
E.2 Adaptive Learning: Simultaneous Discovery and Regret Minimization
30
E.3 Comparison with Elahi al. [2024a]
30
Limitations and Future Works
31
G Auxiliary Results
32
H Proofs
34
17

---

Appendix for "Structural Causal Bandits under Markov Equivalence"
A Related Works
The integration of causal inference into the MAB framework has opened new avenues for modeling and solving decision problems with richer dependency structures [Bareinboim et al., 2024]. Causal diagrams [Pearl, 1995] have been employed to represent causal relationships among actions, rewards, and other relevant factors. This approach enables agents to make informed decisions by considering how each action causally influences the reward through causal pathways. Existing studies [Bareinboim al., 2015, Lattimore et al., 2016, Forney et al., 2017] have shown that causality-awars 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 et al., 2023].
Lu al. [2021] were the first to study causal bandits without assuming access to the full causal diagram. Their approach targets the atomic setting in which the reward variable has only a single parent, reducing the problem to identifying that parent for optimal intervention. They further assume that the agent instead observes the skeleton the true causal diagram. Extending this line of work, Konobeev et al. [2023] eliminated the need for prior knowledge of the graph skeleton. However, their setting remains restricted to the same atomic case. More recently, Feng et al. [2023] 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: pa,) to Q(e: pa.). 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.
Lee and Bareinboim [2018] formalized the structural causal bandit (SCM-MAB) framework, in which a bandit instance is structured by 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 non-manipulable variables among all the variables in the graph. Lee and Bareinboim [2020] established the framework under stochastic policies and demonstrated the informativeness such policies. Everitt et al. [2021] 1] and Carey et al. [2024] further investigated the completeness of the graphical characterization of optimal policy spaces, although the general completeness remains an open problem. Wei al. [2023] proposed parameterization based approach to incorporate shared information among oostimly-optimal actions. Elahi et al. [2024a] extended the SCM-MAB framework to settings where no causal graph is assumed to be accessible, requiring their algorithm to perform causal discovery-i.e.. constructing the causal structure-durinn online interaction. In contrast, our work investigates a graphical approach that eliminates unnecessary actions a priori, given a partial ancestral graph, before the interaction begins. detailed comparison between our work and Elahi et al. [2024a] is presented in Appendix E.3.
Building on this line of work, causal Bayesian optimization (CBO; Aglietti et al. [2020]) leverages the systematic characterization MIS and POMIS for structural pruning in continuous action spaces, and Bhatija et al. [2025] extend it to multi-ouccome variant incorporating Pareto optimality.
18

---

B Additional Preliminaries and Background Results
In this section, provide additional preliminaries from previous works (B.1) and background results relevant to our study (B.2).
B.1 Additional Preliminaries
Definite status. Let p be any path in a PMG, and (X, Y) be any consecutive triple along p. We say that Z is definite collider on if both edges are directed into Z. If one of the edges is out of Z. or both edges have a circle mark at Z (i.e., x Z o-x Y) and there is no edge between X and
2, then we say that a definite non-collider on p. path is said to have definite status if every non-endpoint node along is either definite collider definite non-collider.
Markov equivalence class. Multiple MAGs can entail the same m-separationn relationships. Such MAGs constitute Markov equivalence class (MEC). The Markov equivalence class of MAGs be uniquely represented by a PMG which we refer to as PAG.
Definition 8 (Markov equivalence [Zhang, 2012]). Two MAGS MM, M2 with V(Mi) = V(M2) are Markov equivalent if for any three disjoint sets of vertices X, Y, Z, X and Y are m-separated by in M₁ if and only if X and Y are m-separated by Z in M2.
path between X and Y. = (X,.... W, Z, Y), is a discriminating path for if (i) p includes at least three edges; (ii) Z is non-endpoint vertex on p. and is adjacent to Y on p; and (iii) X is not adjacent to Y, and every vertex between X and Z is collider on p and is parent of Y.
For two MAGs to be in the same Markov equivalence class, discriminating paths must either be present in both graphs none of the graphs, as well as the same skeleton and unobserved colliders.
Lemma (Graphical characterization of MEC [Spirtes and Richardson, 1997, Zhang, 2012]). Two MAGs Mi and M2 with ((Mi) (MM2) are Markov equivalemt if and only
(i) they have the same adjacencies:
(ii) they have the same uncovered colliders; and
(iii) if some path is discriminating path for vertex V in both graphs M1 and M2, then V is collider on the path in MM if and only if it is collider on the path in M2.
A collider path .V..... Vie) is called a minimal collider puth if V1 is not adjacent to Vz, and no subsequence of the path is also a collider path.
The two conditions (ii) and (iii) can be expressed condition for MAGs to share the same minimal colliding paths [Zhao et al., 2005]. Identifying Markov equivalence of a pair of MAGs is tractable with worst-case runtime ([V((s [Wienöbst al., 2022].
Visible edges. A directed edge X + Y is visible if there exists no causal diagram in the corre- sponding equivalence class where there an inducing path between X and Y that is into X. We refer any edge that not visible as invisible.
Lemma (Graphical characterization of visibility [Zhang, 2006, Maathuis and Colombo, 2015]). directed edge X + Y is visible if
(i) there is vertex Z not adjacent Y, such that there an edge between and that into X (Z + X); or
(ii) there is a collider path between Z. and X that is into (7 x-> + X) and every vertex the path except 7 is parent of Y.
'M M-separation [Richardson and Spirtes, 2002] refers to an extension of d-separation [Pearl and Robins, 1995b] for ancestral graphs.
19

---

(a) P
(b) P(o)
(c) P {C}
Figure 10: (a) PAG P, (b) (C)-upper-manipulate graph, and (c) induced graph over V(P) \ (C). In MAGs and PAGs, the visibility is preserved from P (see Lem. 15). For example, although there is no edge oriented into D in P {C}, the directed edge + Y remains visible.
important to note that (i) an invisible edge Y does not necessarily imply that X and Y confounded in every underlying causal graph; and (ii) invisible edges should not be considered independently. To witness, consider a scenario where we have +- + in a MAG M, and X and Z are not adjacent. Since both edges, X < Y and Y - Z, are invisible, causal diagrams include most of the following structures added .N: X + L1 t
L, Y or Y + L1 + ... + L, + Z (X + Y, or Y ++ Z). Adding any one of these does not introduce new collider between and Z, thereby maintaining conformity with M.. However, if both are added simultaneously, by M..
collider introduced at Y, resulting in causal diagram that is not represented
Manipulations. Given a causal diagram 9 and a set of variables therein, the X-lower- manipulation of G deletes all edges in G that are out the variables in X. The resulting graph is denoted by 9x. The E-upper-manipulation of deletes all edges in G that are into variables in X. The resulting graph is denoted by 9x-
Given PMG Q and a of variables X therein, the X-lower-manipulation of deletes all those edges that are visible in Q and are out of variables in X and replaces all those edges that are out of variables in X but are invisible in Q with bidirected edges. The resulting graph is denoted as Qx The ceppe--manipulation of Q deletes edges Q that are into variables X, and otherwise keeps Q as it is.
The manipulated graphs play a crucial role the derivation of do-calculus.
Do-calculus. Pearl [1995] devised do-calculus which
bridge between observational and interventional distributions from causal diagram without relying on any parametric assumptions. Zhang [2008b] proposed the do-calculus for MAGs and PAGs (also known as Zhang's calculus). Jaber al. [2022] noted that there are cases where Pearl's do-calculus rules are applicable every causal diagram within given PAG, but Zhang's calculus cannot be applied to the same PAG. To address this, Jaber et al. [2022] proposed refined version of do-calculus for PAGs and demonstrated that whenever the proposed rule is not applicable given a PAG, then the corresponding rule Pearl's calculus is not applicable for some causal diagram in the Markov equivalence class represented by the PAG.
Here, we present do-calculus for PAGs, which encompasses that for MAGs.
Definition 9 (Definite m-connecting path [Jaber al., 2022]). In PAG, a path p between and Y is definite m-connecting path relative to set of nodes Z if is definite status, every definite non-collider on p is not a member Z, and every collider on is a ancestor of some member of Z. X and Y are m- m-separated by there no definite m-connecting path between them relative to Z.
Theorem 6 (Do-calculus for PAGs [Jaber et al., 2022]. Let be the PAG over and X, Y. W, be disjoint subsets of V. The following rules are valid, in the sense that if the antecedent of the rule holds, then the consequent holds in every MAG and consequently every causal diagrams represented by P.
Rule 1. P(y do(w), x, P(y d)(w).z)
if X. and Y m-separated by W U in Pw
20

---

Rule 2. P(y do(w), do(x). 2) = P(y do(w), x,2)
if X and Y are m-sepurated by W U in Pwx
Rule 3. P(y| do(w), do(x)) z) P(y do(w), if and Y are m-separated by W U U in P P.
where (Z)
X PossAn (a)rnAn(Z))/va (Z)P[V
Induced graph. A subgraph [[A] is defined as a vertex-induced subgraph in which all the edges among the vertices in A C V(2) are preserved while maintaining the visibility from @ (see Fig. 10).
Chordal graph. We also introduce some useful graph theory and terminology, excerpted from Maathuis et al. [2009] and Wang al. [2023a]. A graph is chordal if any cycle of length four or more has a chord, which refers to an edge joining two vertices that are not adjacent in the cycle. If graph = (V, E) is chordal, then its subgraphs are also chordal. A vertex Z in V is called simplicial (Z)))(Z)gg induces complete graph. As shown by Dirac [1961] and Golumbic [2004], there least two non-adjacent simplicial vertices in any non-complete chordal graph with more than one vertex. A perfect elimination order of a graph G is an ordering o = (V1, ... Viv)) of its vertices, so that each vertex V; is simplicial vertex in the subgraph 9 (Vi,.... V,-1): J. It is always possible transform any circle component in PAG into directed acyclic graph (DAG) without introducing new unshielded colliders, as the circle component is chordal and every chordal graph has a perfect climination order [Rose et al., 1976, Habib al., 2000].
Orientation rules. Fast Causal Inference (FCI) [Spirtes et al., 2001a] is causal discovery algo- rithm for identifying PAGs from conditional independence relationships derived from an observable distribution that follows underlying model. We present the complete orientation rules proposed by Zhang [2008a], omitting rules R5-R, due the absence of selection bias.
Ro For each uncovered triple (X, 2,,Y,, in P, orient it as a collider X +- 7 t* if and only if Z is not in Sepset(X: Y)".
R1 If
Zo-xY, and X and are not adjacent, then orient Zo Y as + Y. R2 X + - Y or X + > Y, and X X4-oY, then orient X X as X x Y. +, x W o- X and Y are not adjacent, and W x-o Z, then orient W + 2 as W x+ Z.
R3 If X-+ +
R4 If (X..... ...., WWW Y. a discriminating path between X and Y for Z. and Z Y; then if Z E Sepset(X, X, Y). orient Z o-* Y as Z Y; Otherwise orient the triple (W. ZZ,Y as
W + Z ++ Y.
Rs X + 7 - Y, and X a- Y, orient X o- as X
Rg If X o- Y, and p (X, Z, W.... ,Y) is uncovered possibly directed path from X to Y such that Z and Y are not adjacent, then orient X a-> Y as X +YY.
Rio Suppose Xo Y, Z + Y + W, Pi is an uncovered possibly directed path from X to Z, and p2 is an uncovered possibly directed path from X to W. Let U be the vertex adjacent to X on p1 (U could be Z), and V be the vertex adjacent X on p2 (V could be W). If U and V are distinct, and not adjacent, then orient X o-> Y as X +Y
Incorporating background knowledge. Andrews et al. [2020] demonstrated that the ten rules R1 - 110 are complete for incorporating tiered background knowledge, which refers to background knowledge where the variables in a PAG can be partitioned into distinct groups with an explicit causal order defined among them.
Wang et al. [2022, 2023b] proposed that the rules R₂ Ra, R4,, Rs R orienting PAG when local background knowledge (i.e., all marks around vertex) is available. The second additional rule R3g naturally follows from the absence of selection bias.'
Rio and Rse are complete for
$A set E Sepset(X, Y)
are independent given Z.
*Wang et al. [2024a] proved that rules R, - Rio with one additional rule are sound and complete to incorporate local background knowledge scenarios where selection bias is present.
21

---

R4 (X, ... , W.Z. is discriminating path between X and Y for Z, and Z c-+ Y; then orient Zo- Y as Z Y. Ras X -oY, then orient -oY as X -.
Furthermore, they built the necessary and sufficient conditions for validating local background knowledge (referred to here as local transformation the context of our paper), which can be determined in ((
Theorem 7 (Theorem 3 in Wang et al. [2023b]). Denote Q the obtained PMG after some valid local transformations from PAG P with orientation rules R1 R3RR3. R4, Rs -100 and Rgs. Given set Cº S o X o-s V), there exists MAG M consistent to Q with X ++ V for all VE C and X V for all E (V E Adj(X) X x V) C if and only if C satisfies the following conditions:
1. PossDe(X) (a(C))) 0;
2. 2[C is complete graph;
3. Orient the subgraph QiPossDe (X) cg as follows until no feasible updates: For any vertices Vi and Vj such that Vi 1- V. orient as Vi V, if
(i) Fv, # 9, or;
(ii) Fv. = Fv; well there is vertex Vn PosaDe X 2.0g not adjacent to V, such that Vm + Vio-VV
where Fv, IV e C U(X) V Vi Q}. Then, uncovered colliders introduced.
The PMG incorporating local transformations satisfies desirable properties as follows.
Theorem (Theorem in Wang et al. [2023b]). Let Q be a PMG obtained from some valid local transformations from PAG and orientation rules R1 11--e R3, R4, Rs RR00 and Rgz. Then Q satisfies the following properties.
(Closed). Q is closed under the orientation rules.
(Invariant). The arrowheads (>) and tails (-) in Q are invariant in all the MAGs consistent with Q
(Chordal). The circle component in Q is chordal.
(Balanced). For any three nodes A, B,C in if B c C, then there is edge between A and C with an arrowhead at C, namely, A + C. Furthermore, if the edge between and B is A > B, then the edge between A and C is either A + or Ao C (i.e., it is not A ++ C).
(Complete). For each circle vertex A on any edge Ao-* in Q there exist MAGs Mj and M2 consistent with Q such that A ++ B in M1 and A + B in M2.
Recently, Venkateswaran and Perković [2024], Wang et al. [2024b, 2025a] devised additional rules for more general type of background knowledge. However, the completeness of the orientations in the resulting PMG after applying these rules remains open problem.
Wang et al. [2023a] leveraged the PMG incorporating local background knowledge to determine whether given set of variables can be adjustment set in MAG consistent with the PMG, and Wang et al. [2024b, 2025b] demonstrated that the additional rules can improve this process.
Soundness and completeness of orientations. To eliminate ambiguity, we provide a formal description of soundness and completeness the context of orientation within PMG. Let Q be PMG. We say that orientations in Q are sound if there is at least one MAG M conforming to Q such
22

---

that invariant edge marks in Q are subset of edge marks in M. We say that the orientations in Q
are complete if for every Ao B edge in H. there are two MAGs M1 and M2 represented by Q
containing the edges A + B and A t+ B, respectively, such that Mj and M2 conforming Q.
Structural causal bandit. We review the notion of minimal intervention set (MIS) and possibly optimal minimal intervention set (POMIS) as well as their graphical characterizations for causal diagram by Lee and Bareinboim [2018]. Let be a causal diagram and CC(X) g be the c-component [Tian and Pearl, 2002] of G that contains X where a e-component is maximal set of vertices connected with bidirected edges. We denote CC(X); = Uxex CC(X)s. Let MUCT(G, Y) and IB(G, Y) be the MUCT and IB given YT. respectively.
Definition 10 (MIS [Lee and Bareinboim, 2018]). Given information [g. Y], a set of variables X V {Y) is said to be minimal intervention set (MIS) with respect to [G, Y']. denoted by Mcg, Y there is no X' Ç X such that Px[x'] = Vx for every SCM conforming to the causal diagram g.
Proposition (Proposition in Lee and Bareinhoim [2018]). Let 9 be a causal diagram over the set of variables V. A set X C V (Y) is an MIS relative to [g, Y] if and only if C An(Y))x
MIS leverages Rule 3 of do-caleulus [Pearl, 1995] to eliminate variables that are irrelevant to the reward. Intuitively, an MIS can be understood as a set X in which there exists a directed path from any variable E X to Y, ensuring that each X can influence Y.
Definition 11 (POMIS [Lee and Bareinboim, 2018]) Let X S V {Y) be an MIS with respect to [G. Y.. If there exists an SCM conforming to G such that jxx >> -WeEMa (XX)/w> then X is possibly-optimal minimal intervention ser (POMIS) with respect to [G, Y..
Definition 12 (Unobservad-coffoundey territory). Given information [G, Y1. let H = 9 (Y)))) set of variables T S VH) containing Y is called a UC-territory on with respect to Y De x = T and CC(T) T. A UC-territory T is said to be minimal if no T' S T is UC-territory (MUCT).
Definition 13 (Interventional border). Let T be a minimal UC-territory on causal diagram 9 with respect to Y. Then W = P \ T is called an interventional border (IB) for G with respect Y.
When given causal diagram G, MUCT and IB provide graphical characterization of POMIS. In words, MUCT is the minimal set of variables that is closed under descendants and connected by bidirected edge; and IB consists of the parents of MUCT, excluding MUCT itself. Intuitively, MUCT the minimal closed mechanism that conveys all hidden information from unobserved confounders to the downstream reward, while IB consists of the nodes that directly affect this closed mechanism.
Theorem 9 (Theorem 6 in Lee and Bareinboim 20018). Let G be causal diagram over the set of variables V. A set X C V \ { is a POMIS if and only if holds (B Y) = X.
B.2 Background Results
We present useful results established in existing works.
B.2.1 Background Results in Zhang [2006, 2008a]
Lemma 3 (Lemma O, used in the proof of Lemma 5.1.7 in Zhang (2006]). Let X and Y be distinct
nodes in a MAG M. If = (X.... Z, V, Y is discriminating path from X to Y for V in a MAG M, and the corresponding subpath between and V in P is (also) a collider path, then the path corresponding to p in Q is also discriminating path for V.
Lemma 4 (Lemma A.I in Zhang [2008a] & Lemma 5 in Jaber al. [2018]) Let P be PAG over V, and let P[A] be the subgraph P P induced by A C V. For any three nodes A, B, C, if A A B Bo*+C C, then there is an edge between A and C with an arrowhead at C, namely, A C. Furthermore, if the edge between A and B is A -> B, then the edge between A and C is either A C or Ac- C (i.e., it is not A C).
Lemma 5 (Lemma 3.3.2 in Zhang [2006]). In a PAG P. any two nodes A and B, if there is circle path, then following holds:
23

---

1. If there is an edge between A and B, the edge is not into or or B:
2. For any other node C, C+ if and only ++ B. Furthermore, C+ A if and only if
C ++ B.
Lemma 6 (Theorem 2 in Zhang [2008a]). Let be PAG. Let M be the graph resulting from the following procedure applied to P.
Step 1. Replace all partially directed edges (o-+) in with directed edges (-).
Step 2. Orient the circle component of P into a DAG with no unshielded colliders.
Then, the result graph M conforms P.
Lemma 7 (Lemma B.1 in Zhang [2008a]). Let and be two distinct nodes in a PAG P. If is B in PAG P, then some subsequence of forms an uncovered
a possibly directed path from possibly directed path from A to B in P.
Lemma 8 (Lemma B.2 in Zhang [2008a]). Let A and B be two distinct nodes in a PAG P. If
p = -Vo(== A), (= B)) 2, is an uncovered possibly directed path from to B in P, and V for some i (1, ,.), then V,-1 Vj for all j 11,...,,,
Lemma 9 (Lemma B.4 in Zhang [2008a]). In PAG P, if there is possibly directed path from A to B, then the edge between A and B, any, is not into A.
Lemma 10 (Lemma B.5 in Zhang [2008a]). a PAG P, let A and be two distinct nodes PAG P. there is possibly directed path from A to B that into B, then every uncovered possibly directed path from A to B is into B.
Lemma 11 (Lemma B.7 in Zhang [2008a]). In a PAG P, if there circle path between two adjacent vertices in P. then the edge between the two vertices is circle edge (o-o).
B.2.2 Background Results in Maathuis and Colombo [2015]
Lemma 12 (Lemma 7.6 in Maathuis and Colombo [2015]). Let P be PAG with edges into X, 2 O. Then there exists at least one MAG M in the Markov equivalence class represented by P that has k edges into X.
B.2.3 Background Results Perkovic et al. [2018]
Lemma 13 (Lemma 48 in Perkovic et al. [2018]). Let X be a node in PAG P. Let M be MAG conforming P that satisfies Lem. 6. Then any edge that is either X o-o Y, X o- Y, or invisible X + in invisible + M.
B.2.4 Background Results in Jaber al. [2018, 2022]
Jaber et al. [2018]). Let P be a PAG over V, and G be any causal diagram in the equivalence class represented by P. Let X + Y be two nodes in A C V. If X is an ancestor Y in AA), then X is possible ancestor Y in P[A].
Lemma 14 (Proposition
Lemma 15 (Lemma 4 in Jaber et al. [2018]). Let P be a PAG over V. For every directed edge X + in induced subgraph P[A] with S V, if is visible in P, then it also visible in P[A).
Lemma 16 (Proposition Jaber et al. [2018]). Let P be a PAG over V, and G be any causal diagram in the equivalence class represented by P. Let X 4 Y be two nodes in A C V. If X and Y are in the same c-component A.A.. then X and Y are in the same pc-component in [[A].
24

---

Algorithm 2: Partial Topological Order PTO [Jaber et al., 2018]
Input: P. A S ((P)
Output: Partial Topological Order over P[A]
while there exists bucket B in P[A] with only arrowheads incident on it do
2
Extract B from P[A]
A
end
The partial order is B' <- ... B in reverse order of the bucket extraction, i.e., B is the last bucket extracted and B the first.
Lemma 17 (Proposition in Jaber et al. [2018]). Let P be PAG over V, and let P(A) be the subgraph of P induced by A C V. Then, Alg. is sound over P[A], the sense that the partial order is valid with respect to G forr every causal diagram G in the equivalence class represented by P.
Lemma 18 (Lemma 6 in Jaber et al. [2018]). In M[A), where M is MAG over V and A C.V. the following property holds:
For any three vertices A, B. B, A+ B C and both edges are invisible, then we have A+ C and the edge is invisible.
Lemma 19 (Lemma 18 in Jaber et al. [2022]). Let P be PAG over V, and let P[A] be the subgraph of induced by S V. In [[ the following property holds:
For any three vertices A, B, C, A B . C and both edges are invisible, then we have A+ C and the edge is invisible.
B.2.5 Background Results Wang et al. [2023b, 2024a]
Lemma 20 (Lemma 2 in Wang et [2023b]). Let Q be PMG obtuined from some valid local transformations from PAG P and the orientation rules. If is possibly directed path from A to B in Q, then some subsequence of p is an uncovered possibly directed path from A to B in Q.
Lemma 21 (Lemma 3 in Wang et al. [2023b]). Let Q be a PMG obtained from some valid local transformations from PAG P and the orientation rules. In a PMG Q. any two nodes A and B, there is a circle path, then following holds:
1. If there is an edge between A and B, the edge is not into or B;
2. For any other node C, C+ A if and only if FCC* ++++ B. Furthermore, C 4> A if and only if C B.
Lemma 22 (Lemma 4 in Wang et al. [2023b]). Let Q be PMG obtained from some valid local transformations from PAG P and the orientation rules. Suppose a MAG M consistent to Q and the local transformation Cº. Then Y PossDe(X)) (X) 2xcs if and only if Y E De(X)
Lemma 23 (Lemma 16.1 in Wang al. [2023b]). Let be PMG obtained from valid local transformations from a PAG P and the orientation rules. The MAG oriented according to Lem. 6 conforms to Q.
Lemma 24 (Lemma 2 in Wang et al. [2024a]). Let Q be a PMG obtained from some valid local transformations from PAG P and the orientation rules. If there an uncovered circle path p (V1, V2,... Va), n 2 in Q. then any two non-consecutive vertices are not adjacent (minimal circle path).
A bucket refers to the closure of nodes connected with circle paths.
25

---

Tisk
T
Task
Tisk
Task
Taak
Total tridds
10K
106
5k
2k
7k
POMIS
128.4 (233663)3))
$20.9 43.7(44.35))
60.8 3.9)
86.9 43.31 (8.1(8.7%)
51.9 2.3/14.99)
203.8 3.8/23.89))
144.9 61.9
661.1 00.6
1713.6 + 23.1
385.9 48.3
108.2
805.6
314.0
724.8
2421.3
889.1
854.5
POMIS
55.5(48
65.1(50.45)
0.1(2.15))
(6..9)))))
0.2/12.79))
0.3117.995 1043.3 + 13.7
KL-UCB DMIS
270.9 64.9
1175.3 + 52.3
1901..6 9.9
7UC.0 66.6
128.4 1.7
BF
497.9 56.7
1250.9 9 + 80.5
2483.6 + 33.7
1518.4 + 71.0
431.1 16.0
1130.7 + 13.9
Table I: Mean and standard deviation of cumulative regret (CR). The asterisk (+) indicates additional experiments. The percentages (red) represent the ratio CR for POMIS
100(%))
CR for
C Assumptions
In this paper, we assume that there is no selection bias in the SCM-MAB system; that is, the PAG representing our causal diagrams of interest contains undirected edges. Since our work focuses on a graphical perspective of the structured bandit system in terms PAGs, we assume access to the true PAG representing the causal diagram corresponding the target bandit instance.
D Experimental Details and Additional Results
This section provides details on the specific SCMs used in all bandit instances presented in the experiments (See. 5) and additional experiments. Simulations are repeated 1,000 times to obtain consistent results. The simulations were conducted on 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: POMISs, DMISs, and Brute-force (BF). combined with two prominent MAB solvers: Thompson Sampling (TS) [Thompson, 1933, Chapelle and Li, 2011, Agrawal and Goyal, 2012, Kaufmann al., 2012] and KL-UCB [Garivier and Cappé, 201 Cappé et al., 2013]. In the Brute-force strategy, all possible combinations of arms Uxcvvry Xx evaluated. The number of trials is set to 10,000 for Tasks 2, and 4; 5,000 for Task 3; and 2,000 for Tasks 5 and 6, which is sufficient to observe performance differences among action spaces. The number of trials is selected such that the cumulative regret with respect POMIS stabilizes across 1000 repeated runs. Our experimental setup closely follows those of Lee and Bareinboim [2018] and Wei et al. [2023]. Tables and summarize our simulation results.
These results demonstrate that refining arms by considering the Markov equivalence class into account enhances the efficiency of agents when interacting with the underlying environment.
Details of the Causal Models for Bandit Instances
We denote the exclusive-or operation by @, and use Bern to represent a Bernoulli distribution. We randomly generate structural functions F using binary logical operations (A, V, v,0,-) and the parameters of the exogenous variable distributions are also randomly selected.
Task 1. The bandit instance associated with an SCM S where
U
{UA, UB. Uc, Up, Uv, UBY,UAc} [A, (AB,C,,D,Y)
V
SA = 4A M.C, MBC = ((1-ug) A AuBy),
F
fc ((1 uc) Auc)), = uD,
S
(1)
"ByY)] A by UA ~ Bern(0.44). (Bn Uc Bern(0.4), (ern(0.66), UBY ~ (0rn().28), UAC Bern(0.77).
fy = - ((1
P(U)
Un ~ (0.r9)0.59).;
26

---

16:00
DVG
POWBS
400
DV55
300
2000
100
130
de
(a) Task
(b) Task 5
(c) Task 6
Figure 11: Cumulative regrets for the corresponding KL-UCB (solid) and TS (dashed) for additional experiments (Task 4-6) under distinct strategies. We plot the average cumulative regrets along with their standard deviations.
Task 2.
The bandit instance is associated with SCM Sn where
U
(UA.UB. Uc, UD. Ug, , UAY, UBr} = (,,
V
fA 4. @ uAY fB up uBY fc uc 0b, SD - un $ =c ug) (1 Ac, fy my v (((1-)) (MAY "By)) A Ad]
F
S2
(2)
UA (ern(0.47), ~Brn 00599, , Uc ~ (0.37). UD Bern (orn((061)).7 Bern (0.55, Uy (ern()
P(U)
UAY Bern(0.54), UBY ~ (0.36).
Task 3.
The bandit instance is associated with an SCM S3 where
U
UUA.Un,U,, Ur, Ug. Un. U, Uv. U UnE UnG, Unr -.A.BBCC.D...........
V
= u== U @AB.A (uBE @ UAB) A (a ub),
Sc = uc @ = 0c
f ((1 - ([1=ug) @g- A ABEE
fF ((L up) (1-e)) UFG.
SG = (uFG (eV
Sy
АH ((1 un) (1 (1-e)) UHF,
fI = (WLY @ unι) A (f
fy uy V (((- ((A))))) A
UA ~ U0 Bern (0.59), Uc Bern (0.37),
UD Bern
(ern((055) UF Bern (0.21),
P(U)
UG Bern(0.54), Un (erm(0.36), U, (0rm(0.45),
Uy (orn().37), UAB (ern())) UBE ~ (0r53).53).
UFG Bern(0.62), UHI (erm(0.46), UnY Bern (0.67).
As an additional experiment, we evaluate the cumulative regrets (CR) of SCM-MAB using the PAGs illustrated Fig. 12. The corresponding plots are shown Fig. 11.
Task 4. We consider the PAG in Fig. 12a validate our result. Using three strategies, the POMIS- based TS and KL-UCB achieve CRs of 85.9 and 195.1, which correspond to 9.7% and 12.9%.
27

---

Task
Task
Task 3
Task 4"
Task 5
Task 6*
POMIS
(43.75%)
(56.3%)
(1.56%)
6 (37.5%)
16 (12.5%)
40 (31.3%)
DMIS
9
30
152
14
32
120
32
512
128
POMIS
(23.3%) (36. (36.696)
54 (0.27%)
15 (6.17%)
81 (3.70%)
231
(10.79))
Arms
DMIS
25
195
2025
189
1755
BF
81
243
19683
243
2187
2187
Table 2: For each task, the number of intervention sets (IS; shown above) and the corresponding number of arms (shown below) are reported. The percentages (red) indicate the ratio POMIS and the corresponding ratio for the number of arms.
# x100(%).
B
E
(a) Task 4
(b) Task 5
(c) Task 6
Figure 12: Each PAG represents a target bandit mechanism that the deployment agent interacts with.
respectively, of CR for BF. The bandit instance is associated with an SCM S where
U
(UA,UB, Uc, UD. Uy, LY,,UUU,UAAA UAA,
V
= D,,
[AA = uA [[(1 d) (uAY uAC)] Ab],
.n = un @ uAY;
F
fc (uAC @ E) (BV uc), up Ob,
S
f = {(1 - ug) (1 b)} Ad,
fr uy V ([(1 @ (uAY Auny) A
UA- ~ Bern(0.47). (Ug ~ Bern(..59), Uc ~ (0r37).37), Bern(0.55), Uy Bern(0.21), Bar (0.36), UAY Bern(0.54), UBY Bern(0.45)
P(U) = UD (er.n..66),, UAC Bern
Task 5. We consider the PAG Fig. 12b to validate our result. Using three strategies, the POMIS- based TS and KL-UCB achieve CRs of 51.9 and 54.1, which correspond 14.5% and 12.7%, respectively, of CR for BF. The bandit instance is associated with an SCM Sş where
U
(UA, Uc, Up, Un, Ur. UG, Uy UAB UBY UUD,
V
D,, [A = (1 (1- uA] {(1 UAB) 0 #e),
fB [1 (uBy V - =gg}) @ (MAB @ f),
(1-ug)}) Sc won @ uc, = (1 un) (c-- @c),
fE = d O ug, NE (1 v @e),
S₁
(5)
fc
fY = ((()((()))))
UD Bern (0 Uc ~ (0r36)
UA ~
Ur Bern (0.58).
P(U)
Ua ~ Bern(0.55), Bern UPG Bern(0.36)
UAB (ern(..37), UpY Bern(0.35), UCD (0.n)
28

---

Task 6. We consider the PAG in Fig. 12c to validate our result. Using three strategies, the POMIS- based TS and KL-UCB achieve CRs 203.3 and 202.9, which correspond to 23.8% and 17.9%. respectively, of CR for BF. The bandit instance is associated with an SCM Sg where
U
UUA,U U.. Up, UG. Uy UAY,UEP,UPG D, E, F, G,
V
SA = 4A O u fB = uB:
fc ((1 uc) A ) a,
f UD:
JE = ((1 10) b)
((1 - ugF) ) (1 - d))) A ug:
F
fF ((1 uFF) A uFG) V UEF,
S
(6)
fa = ((1 uG) A wrg) Vg.
fy = e A ((1 d) V (((1 - uy) A g) V uAY)) (0.42) Uc Bern(0.777,
UA Bern (0.59), L/B (
UD ~ Bern (0.28), Bern(
U/ ~ Bern(0.72). UF ~ Bern(0.48),
P(U) =
Ua Bern(0.68), Uy (0rn( Bern(0.61),
UEF ~ Bern(0.63), UrG ~ (0.55).
E
Discussions
In this section, we discuss circle mark transformations from the perspective of orientation complete- ness and complexity of enumerating all POMISs for PAGs.
E.1 Partial Mixed Graphs Obtained from Local Transformation
Let Qx be PMG that satisfies (1) the conditions in Prop. and (2) closed under orientation rules R₁ - Rs. R4, Rg R10- and Rea with additional Rules provided by Wang et al. [2024b], Venkateswaran and Perković [2024], Wang al. [2025a]. is important to note that the completeness of @x remains an open problem. Therefore, Qx is inadequate to completely characterize POMIS for PAGs.
Remark 2. Every Q'x is complete for orientations; for any Ao- B in Øx there are two MAGs B and A t-* respectively.
Mi and Ma represented by Ø'x containing
Morcover, even though we have access to Qx a PMG that satisfies (1) the two conditions in Prop. 7 and (2) the orientation completeness 2x still insufficient ensure X Ann To witness, consider PAG P in Fig. with X {A).
(a) ((4)
a
(c) M
(d) Avi Z
(e) Q
Figure 13: The light blue region indicates possible ancestors of Y. (a) PMG incorporating necessary conditions (Prop. 7) and (b) the PMG with orientation completeness. (c) MAG represented by Q(4)
while A & An(Y) M- (d) PMG representing sound and complete orientations over MAGs satisfying that {A} an MIS. (e) PMG with ( and L (Y)
(B).
(A)
Then C o-o Y in P corresponds o Y in Øx according to the first condition in Prop. supported by the uncovered proper possibly directed path A o-o c-o Moreover, Y - D is oriented by R2, and all remaining circle marks can vary across the underlying MAGs represented by Øx Here, we can find MAG M where & An(Y). by orienting Co- Y as Y, suggesting that additional information (orientation) is necessary.
29

---

Furthermore, neither 2x nor Qx guarantees the balanced property (Lems 4 and 31). To witness, refer to Picy (identical to 2(cy). ). We can observe that there is + Y c-o while Co-o B, which violates the balanced property.
One might surmise that X IB(P, Y, .X) is appropriate characterization of POMIS for PAGs.
However, this approach does not hold. For illustration, consider the PAG P in Fig. 5a and a set X = {A), which is a DMIS with respect to [P. Y]. Moreover, we can simply derive (B(P, Y, X) = {A), and thus X IB(P, Y, X) holds. For X to be an MIS for MAG M represented by P. the edge A o-o C' should correspond to A + C' in M, implying the visible edges C - B and C' + Y. as these are non-definite colliders (see M₁ and M2 in Figs. 5b and Sc with Fig. 13d). Regardless of the edge orientation of B c-o Y, we find (B(M, Y, X) {C}, in Fig. 13e. Thus, X (A) is not a POMIS with respect to [M,Y Y] for all M E [P]. Therefore, (B(P, Y, X) fails to characterize POMIS.
E.2 Adaptive Learning: Simultaneous Discovery and Regret Minimization
natural question is why we do not pursue adaptive discovery from online information. We address this point, beginning with relevant literature on causal discovery with interventions.
Offiine discovery from interventions. offline or non-adaptive setting, interventions are prede- termined before algorithm execution. Hauser and Bühlmann [2012] studied the problem of learning graph structures from interventions under the assumption of no unobserved confounders, while Kocaoglu al. [2017] explored experimental design for learning causal diagrams from interventions. Recently, Zhou et al. [2025] investigated learning PAGS from interventions.
Online discovery from interventions. While those offline causal discovery researches require access to infinite interventions, there has been intensive works that adaptively selects interventions from an online learning. Squires et al. [2020] and Choo and Shiragur [2023] applied interventions sequentially, with adaptively chosen targets at each step, still necessitating access to interventional distributions. Although Greenewald et al. [2019] and Elahi et al. [2024b] worked with finite inter- ventions, it applicable only when the underlying causal structure has no unobserved confounders. Notably, designing adaptive discovery algorithms that work with finite interventions and allow for unobserved confounders remains an open problem.
It may possible to incorporate online causal discovery into the decision-making process. For example, at each step, an agent can choose interventions aimed at improving structural knowledge, while also expecting that those arms could be valuable for minimizing regret. However, designing algorithms that effectively balance exploration for structure learning and for regret minimization poses substantial -trucctu
additional challenges, as these two objectives structure discovery and regret minimization are not naturally aligned.
Furthermore, Wang et al. [2022, 2023b] adaptively refine PAG by resolving circle marks through targeted interventions. In this sense, interventions on nodes involved in circle marks can be useful for structural refinement. However, as noted in Wang et al. [2024a], obtaining closed-form characterization of the number of MAGs compatible with PAG given particular orientation of circle mark remains an open problem, implying that determining which circle marks to prioritize for learning is itself a challenging problem. As such, designing reliable algorithms that exploit structural uncertainty during learning involves solving nontrivial structure learning problems and remains an active area of research.
E.3 Comparison with Elahi et al. [2024a]
Elahi et al. [2024a] demonstrated that it is not necessary to learn the full causal diagram to identify all POMISs, and specified the extent of graphical structure that must be discovered to do so. Building on this insight, their work flow proceeds as follows: In the first phase, the method leams the induced subgraph the ancestors of the reward node an online manner, through interventions; Using the learned graph, they identify POMISs following the method of Lee and Bareinboim [2018]; Finally, they run standard independent MAB solvers with the identified POMISs.
30

---

In contrast, our work does not focus on causal discovery, but instead assumes access to a PAG (e.g.. obtained via FCI [Spirtes et al., 2001b, Zhang, 2008a]) and aims to identify POMISs directly from this PAG. That is, given a PAG derived from purely observations, our algorithm prunes suboptimal arms priori, without requiring any interventions for causal discovery. From practical perspective, interventional data is often more costly and risk-prone than observational data. This suggests that our approach first discovering a PAG from observational data and then identifying POMISs may offer substantial advantages in resource-constraing on extensive intervention for graph discovery.
high-risk domains, compared to methods that rely
Since both our method and Elahi al. [2024a] ultimately reduce the problem standard bandits over set of POMISs, their regret bounds in both approaches depend critically on the size of the resulting POMIS set (each denoted by Ip and Iş). In Elahi et al. [2024a], the regret bound consists of a discovery term and a minimization: (f k) + O(ExEI (x + log ))" whereas our A
A )). Since our approach avoids online causal discovery, our regret does not include the additional discovery term. However, because PAGs contain structural uncertainty (e.g., circle marks), the number of POMISs derived from a PAG typically larger than that from a fully specified causal diagram. As result, the bandit term of Elahi et al. [2024a] is usually smaller than ours. Therefore, although direct comparison is difficult due to the different settings, the trade-off can be summarized as eliminating the online discovery cost at the expense of starting with a larger initial action space.
regret bound contains only the minimization term: O 4x + Tog
F Limitations and Future Works
In this section, we present limitations of our work and outline promising directions.
Modeling bandit instances in the form of SCMs. Structural Causal Models (SCMs) are a versatile and expressive framework that provides a principled way to represent and reason about causal relationships. Their generality makes them applicable across wide range of domains. However, SCMs come with certain limitations, such as the assumption of a well-defined set of variables and a fixed causal structure, which may not adequately capture the complexity of dynamic, high- dimensional, or partially observed systems. Nonetheless, our work addresses fundamental problem within the SCM framework. We believe it provides a solid foundation for future research, such as extending causal bandits to more complex or less structured environments.
Known partial ancestral graphs. We make the standard assumption that the deployment-phase learner has access to the true PAG representing the underlying causal diagram. In practice, while several causal discovery methods in the presence of latent confounders have been proposed [Spirtes et al., 2001a, Zhang, 2008a, Colombo et al., 2012, Rohekar et al., 2021, 2023], these techniques typically rely on accurate estimation of conditional independence (CI) relations. This would be especially true for constrained-based algorithms like FCI, where the exact PAG recovery would require many empirical conditional-independdnee tests to work perfectly. Therefore, our work implicitly assumes that the decision-man maker possesses sufficient domain knowledge and statistical capability for reliable CI testing.
PAG misspecification. It is of great practical interest study how MIS. DMIS and POMIS are affected given PAG misspecification. Notably, the edges in a PAG are governed by structural constraints and logical dependencies such as the balanced property and chordality. Due to the structured entanglements, it is indeed difficult expect that computing POMISs would yield robust results. Although our work is primarily theoretical and assumes access to the true PAG, we acknowledge that developing robust methodologies that account for such issues is a promising direction for future research.
incorrect PAG
11 "where danx denotes a constant greater than the maximal in-degree in the true causal diagram, and d, represent some parameters. See Appendix A.13 of Elahi al. [2024a] for further details.
31

---

Future work. In future research, given the availability of an observational distribution, it becomes possible to identify specific causal effects and climinate suboptimal arms [Jaber et al., 2022]. More- over, integrating this approach with partial identification [Balke and Pearl, 1995, Richardson et al., 2014, Zhang and Bareinboim, 2020, 2021, 1, Zhang et al., 2022, Bellot, 2024], enables the exclusion of arms where the upper bound is less than the lower bound of another arm, as proposed by Zhang and Bareinboim [2017]. One can account for uncertainty in identification or bounds caused by finite sample, which will lead to more robust analyzes [Bellot and Chiappa, 2024, Jung and Bellot, 2024]. Beyond causal bandits, we believe that ancestral graphical modeling offers practical value by integrating with causal reinforcement learning [Zhang and Bareinboim, 2022, Hwang et al., 2024, Bareinboim al., 2024], rehearsal learning [Qin et al., 2023, 2025, Du al., 2024, 2025, Tao et al., 2025] and sequential planning [Pearl and Robins, 1995a, Jung et al., 2024].
G Auxiliary Results
In this section, we provide auxiliary results utilized throughout the paper.
Lemma 25. Let be a PAG over V. and let P[A] be the subgraph of P induced by A S PossAn(Y)p V. If X and Z belong to different buckets over P[A], then the starting edges of any uncovered proper possibly directed paths from X and Z to Y with respect to X are not relevant.
Proof. Since and are not the same bucket, there no circle path connecting the two nodes. Consequently, X and Z are not relevant.
Lemma 26. Let P be PAG over the set of variables V. If a set X XVV (Y) is DMIS relative to [P,Y], then there exists a MAG M such that every E X has a proper directed path to with respect X in M.
Proof. According to Prop. and thm. there exists MAG M such that X AnnYY) For the sake of contradiction, suppose that X C An(Y) holds while there is no proper directed path from X E X to Y with respect to X in M. This implies that every directed path from X to Y must contain some node Z X \ {X}. Consequently, such paths would be cut by the X-lower manipulation. resulting in X & An(Y) M. This contradicts the assumption that X AY())
Lemma 27. Let Q be a PMG obtained from some valid local transformations from PAG P and the orientation rules. In Q, the following property holds:
A + B visible, then every A + C' is also visible for every C connected as circle path with B.
Proof. For the sake of contradiction, assume that there exists node C such that A - C is invisible while connected as circle path with B.
First, let D - A be arbitrary edge that makes A + B visible. Since A - is invisible, D and C' must be adjacent and the edge is into C' by the orientation rule R2 (i.e., D+ C). According to Lem. 31, this implies the existence of 2 B, which contradicts the assumption that A - B is visible.
Next, consider the path D V1 + + V2 + A with n 2 1 where V; is a parent of B. By
Lem. 31, we get that there exist edges * for all V. Furthermore, these edges must take the form Vi + C, because if any edges V C existed, R22 would be triggered, resulting in V/2 C.
Therefore. A + C' is also visible, leading to contradiction for the assumption that A + C is
invisible. This concludes the proof.
32

---

from Lemma 28. Let Q be a PMG obtained from some valid local transformations from from PAG P and Yf in [[A]
the orientation rules, and be any causal diagram in the equivalence class represented by Q. Let X + Y be two nodes A V(2). X is an ancestor of in [ then X is a possible ancestor
Proof. The lemma follows the proof of Lem. 14 (Prop. 1 in Jaber et al. [2018]). If X is an ancestor in g[A]. This path is also present in G.
Y in g[A]. then there exists a directed path X .... + and consequently in the corresponding MAG M. Hence, the path corresponds path in Q. Since all nodes along the path are in A, they are also present in Q[A], implying X is possible ancestor of Y [[A].
possibly directed
Lemma 29. Let Q be a PMG obtained from some valid local transformations from PAG and the orientation rules, and G be any causal diagram in the equivalence class represented by Q. Let X * Y be two nodes in A C V(Q). For every X + Y in Q[A), if it is visible in Q, then it remains visible in [[A]
Proof. The proof follows the argument of Lem. 15 (Lem in Jaber al. [2018]). Let & defined over V(Q) U.. Let X + Y be visible edge in Q where X and Y are in A. Then, there is no inducing path between and Y relative to L that is into X in G. It follows that no such inducing path (relative to the latent nodes in g[A] exists in the subgraph G[A].
Lemma 30. Let Q be a PMG obtained from some valid local transformations from PAG P and the orientation rules, and G be any causal diagram in the equivalence class represented by Q. Ler X + Y be two nodes in A C (Q)). ) If X and Y are in the same c-component in G[A), then X and are in the same pe-component [[A].
Proof. The proof follows the argument of Lem. 16 (Prop. 2 in Jaber et al. [2018]). If X and Y are in the same c-component in G[A], then there is a bidirected path in G[A].
Lemma I (Lemma in Jaber et al. [2018]). Let M be MAG over V and G be a causal diagram represented by M. For any X and Y in V. if there is bidirected path p between X and Y in G, then there is path p' between X and Y in M over a subsequence of p such that (1) all the non-endpoint nodes are colliders, and (2) all directed edges on pl are invisible.
Lemma II (Lemma in Jaber et al. [2018]. Let M be a MAG over V and P be a PAG representing M. For any X and in V, if there a path p between X and Y in M such that (1) all non-endpoint nodes are colliders and (2) all directed edges, if any, there is a path p' between X and Y in P over a subsequence of p such that (1) all non-endpoint nodes along the path are definite colliders, and (2) none of the edges are visible.
not visible, then
we choose path p', which is the shortest subsequence of p between and Y in M, corresponding to p" in P. such that (1) all non-endpoint nodes along the path are colliders, and (2) none of the directed edges are visible. By Lemma II, the path p" is a definite colliding path between X and Y, and none of the directed edges along the path are visible P. For contradiction, assume that pt in Q, which is corresponding to in P. includes visible edge out of X. Then, the visible edge would have to appear in all MAGs represented by Q. However, the edge along p' invisible in M, leading to a contradiction. Therefore, p is also of definite status, containing no visible edges, which implies that X and Y are in the same pe-component in Q. Since all nodes along pt are in A, pt is also present in A.A., ensuring that X and Y are in the same pc-component in [A.]
According to Lemma
33

---

Lemma 31. Let Q be a PMG obtained from some valid local transformations from PAG P and the orientation rules, and [ be the induced graph over A C V) For any three nodes A, B, C in Q, if A+++ o- C, then there is an edge between A and C with an arrowhead C, namely, A+ C. Furthermore, if the edge between A and B is A + B, then the edge between A and C is either A + or Ac-> C' (i.e., it is not A t+ C).
Proof. The balanced property holds in the PMG with local transformations as shown in Thm. (Theorem in Wang al. [2023b]). By the definition of induced graph, this property is preserved in [[A].
Lemma 32. Let Q be a PMG obtained from some valid local transformations from a PAG P and the orientation rules. In PMG for any two nodes A and B, if there is circle path, then following holds:
1. If there is an edge between A and B, the edge is not into A or B:
2. For any other node C, C+ A if and only if + B. Furthermore, C &> A if and only if
C ++ B.
Proof. The proof follows the argument Lem. (Lem 3.3.2 Zhang (2006]). The properties depend on the balanced property in Lem. 4, which holds in demonstrated in Thm. 8 and lem. 31.
Lemma 33. Let Q be a PMG obtained from some valid local transformations from PAG P and the orientation rules. PTO (Alg. 2) is also sound over [[A), in the sense that the partial order is valid with respect to G[A]. for every causal diagram in the equivalence class represented by Q.
Proof. The proof follows the argument of Lem. 17 (Prop. in Jaber et al. [2018]). By Lem. 28, the possible-ancestee relations in [[ subsume those in [[A] Hence, a partial topological order that is valid with respect to Q [ is also valid with respect to G[A]. The correctness of Alg. relies solely on the balanced property, which is satisfied the PMG with local transformations per Thm. and lem. 31. Thus, the algorithm is also sound with respect to Q[A].
H Proofs
In this section, we provide detailed proof' of the propositions and theorems presented in the main body of the paper. For readability, we restate of them.
Theorem (Characterization of MIS for MAGs). Let M be a MAG over V. Given information [M, YJ, a set X C V {Y} is MIS relative to [M, Y] if and only if X C M holds.
Proof. (If) Suppose that X is not MIS relative to [M This implies that there exists some X' C X such that Mx = μx for every SCM conforming to the MAG M. For the sake of contradiction, assume that X C An(Y) To derive contradiction, suffices to construct a SCM such that /x[x'] # Px- Consider the causal diagram g generated by the following procedure:
Step 1. A A B in M, then add directed edge A + B G. Step 2. A A B in M, then add a bidirected edge 4+ B to
From this construction, is clear that the causal diagram & corresponds to M. Furthermore, we have X C An(Y)gx since G and M have the exact same edges.
Now consider the following SCM associated with Each variable V, V(G) is associated with unique latent variable U; and the function of each endogenous variable in V(G) is the sum of the
34

---

value of its parents. Since X C An (Y) holds, there exist directed paths from X \ X' to Y without passing through X'. Let W X X Then, setting W to E|W do(x')] + 1 results in a larger outcome value for Y. i.c., Px = Hw.x' MxXx], which leads to a contradiction.
(Only if) Suppose that X g Am(Y) M, holds. This indicates that there exists nonempty subset Z - X An(Y) Let X' X Z. Our goal is to show that Y and Z are m-separated by X' in M X Once established, we can apply Rule 3 of do-calculus for MAGs [Zhang, 2008b] to derive
14xx = |xx'=x
For contradiction, assume that there exists some variable Z E Z such that Z and Y are m-connected conditioning on X' in Mx. This means the existence of a m-connected path between Z and Y. Since has its incoming edges removed, p must start with an edge outgoing from Z. If there were any collider along the path, it would be m-separated, a conditioned node X'. However, if the path begins with an outgoing edge from Z and has no colliders, then must be a directed path from Z to Y. This implies that Z E Ann(Y) holds, thus Z and Y are not m-separated by X' in Mxx leading to a contradiction. Consequently, we have that X is not an MIS relative to [|
the collider cannot be ancestor of
Proposition Let M be MAG over V. A set X S V only if there exists causal diagram 9 conforming M such that X is an MIS relative [G,Y] Y].
(Y) is an MIS relative to [M, Y] if and
Proof. (II) Let X be an MIS relative to [G. Y] for some causal diagram G conforming to M. By the definition of MIS for causal diagrams in Def. 10, there is no X' ç X such that for all SCM conforming to G, Fx[X'] = Pxx- In other words, for every X' Ç X, there exists an SCM S conforming to G such that [x(X'] * Pxx Since any SCM conforming to G also conforms to M, we know that S also conforms to M. Thus, for any proper subset X' ç X, there exists an SCM associated with M
in which |x[X1 Px holds.
(Only if) Let X be an MIS relative to [M, Y]. The causal diagram 9 constructed in the same manner as in the proof of thm. conforms to A and satisfies X C An An())) Therefore, we can conclude that X is an MIS relative [] supported by Prop. 9.
Proposition (Graphical characterization of MIS for PAGs). Let P be a PAG over the set of variables V. A set X C V (Y) is an MIS relative to [P, Y] if and only for every variable X X, there exists a proper possibly-directed path from X to Y with respect to X in P.
Proof. (If) Suppose that X is not an MIS relative to [P, Y1. which implies that there exists some proper subset X' I X such that [x[x]] = Px for every SCM conforming to P. For contradiction, suppose that for all X E X, there exist proper possibly-directed paths from X to Y with respect to in P. Let W = X \ X' and W be a vertex in W. Suppose that p is an uncovered proper possibly path from W to Y with respect to X P. Let M E [P] be a MAG constructed by the following procedure:
Step 1. Orient all edges along p as directed edges. Step 2. Orient the remaining edges according to Lem. 6.
Then, p corresponds to a proper directed path from W to Y with respect to X in M. Thus, W AYn)) holds. We can then use the same construction the proof of Thm. In the constructed causal diagram G. W E An An(Y) holds. Furthermore, we know there exists an SCM S in which W has a positive causal effect on Y which is not mediated by any variable in X. Thus, setting W to E[W do(x')) + will result in larger outcome for Y, i.e., Px = p' > [x[[')] meaning x # |x[x'], which contradicts the statement: [x[x]] Px for every SCM conforming to P.
(Only if) Suppose that for some Z E X, there no proper possibly directed path from Z to with respect to X in P. Let X' X {Z). We aim to show that Pyy do(x')) Ply do(x', 2)).
35

---

which would imply fx px... Unfortunately, we cannot apply Rule 3 of do-calculus for PAGs, since it is not guaranteed that X and Y are definitely m-separated by X' in Px. However, we can reason over the MAGs in the Markov equivalence class represented by P.
All paths from 2 to Y in P which do not pass through X must not be a directed path due to our assumption, i.e. they all contain an arrowhead pointing towards Z. Let M be a MAG conforming to P. Then, all paths from Z to Y in M which do not pass through X must also be non-directed. Thus, using similar reasoning as in the proof of Thm. 1, Z and Y are m-separated by X' in Mx. This is because any path out of Z to Y must contain a collider node, which must be blocked, since it cannot be an ancestor of any conditioned node. Therefore, we conclude that Ply do(x')) = P(y do(x', Since this argument holds for every MAG conforming to P. it holds for all SCMs conforming to P.
Proposition& 4. Let 'D be either a causal diagram or MAG (i.e., not PAG). X is an MIS with respect to [D, then X is a DMIS with respect to [D, Y].
Proof. Without loss of generality, assume that all nodes in D are ancestors of Y. For contradiction, assume that X is an MIS but not DMIS relative to [D. By Thm. 1 and prop. 9, we have X C An(Y) Then, we can consider an SCM S compatible with D, where all mechanisms consist of the sum of the values of their parents, i.e., fv = -ippy pay tuy. Let X' be an arbitrary proper subset of X. and W denote X X'. Such model S* always ensures that setting W as E[W] do(x') + 1 results in fx = pw.x' > Mx|X]] for any proper subset X' since there exist directed paths from each W E W Y without passing through X'. The existence of S leads to contradiction.
Proposition 5. Let P be a PAG over V. A set X CVV \ (Y) is DMIS relative to [P; Y] and only if there exists MAG M conforming to P such that X is an MIS relative to [M, YJ.
Proof. (II) Suppose X C V {r} be an MIS relative to [P,Y] Y1. and there exists a MAG M conforming to P where X is an MIS relative [M, Y]. By Prop. X is DMIS relative to [M, Y]. Hence, there exists SCM S such that for any proper subset X', Mx|x'1 * Mx holds. Since S conforms to M, it also conforms to P, thus concluding proof for this direction.
(Only if) Suppose X C CVV (Y) be DMIS relative to [P, Y]. By the definition of DMIS (2), there exists an SCM S associated with P such that, for every X' Ç X, |x[X]] # 2xx holds. Therefore, X is an MIS, since for any proper subset X', Px[x]] # fx holds under the SCMS.
Theorem 2 (Graphical characterization of DMIS for PAGS). Let P be a PAG over the set of variables V. A set X S V (Y} is a DMIS relative to [P, Yl if and only if. for any pair of vertices X, Z E X. there exist uncovered proper possibly- directed paths from X and Z to Y with respect to X such that their starting edges are not relevant.
Proof. (If) Let px denote an uncovered proper possibly-directed path from X to Y with respect to X in P. Suppose that X is not a DMIS, implying that, for all MAGs M E [P]. holds that 7 E An An(Y) and X An(Y)) without loss of generality. In other words, if orienting px Y is valid, it follows that orienting any possibly directed path from Z to Y as
as X - Z + ... ........ Y is invalid in all MAGs conforming to P. We will show that the starting edge of px is relevant to the starting edge of any uncovered possibly-directed path from Z to Y in P.
Let pz be an arbitrary uncovered proper possibly-directed path from Z to Y with respect to X in P. Note that such path always exists, as established by Lem. 7. We know that the path pz must begin with one of the following edges: o-o, o or +, We will show that pz can only start with circle edge (a-o).
(pz only starts with circle edge (o-o)). Suppose pz starts with 7-+, Then, the path must take the form Z ? + Y in P by Lem. 8. In this case, can construct valid M by orienting any
36

---

circle marks (o) along the path as tails (-) following Lem. 6. This contradicts the assumption that there is no MAG conforming P in which pz is a directed path from to Y. Therefore, we conclude that pz only can be Z
xX X') is not relevant to ez(Z' c- Z) where each For the sake of contradiction, assume ex ex x- denotes the starting edges of px and pz respectively; Then, we consider the following two cases separately: ① X and Z are not in the same bucket, or @ they are in the same bucket, and every circle path including ex and ez is not uncovered. i... they are not relevant.
@ X and Z do not belong to the same bucket). Consider the orientation according Lem. 6. the second step of the construction, we always have MAG M containing Z - Z' by the completeness of orientation in PAGs, which indicates p2 corresponds to a directed path from Z to Y in M. as it is uncovered. Therefore, we can construct a valid M according to Lem. 6, contradieting the assumption that Z An M) for all MAGS M [P].
@ X and Z are in the same bucket). Suppose that X and Z are in the same bucket. Let 1- Z²) o- (= Z) be arbitrary non-uncovered circle path between X and Z in P. By the definition of an uncovered circle path, such path must include at least one non-uncovered triple (V,, Vi+1, Vi+2) on the circle path. The existence of an edge between V; o-o V2+2 would induce an uncovered circle path V1 o-o... o-o V; o-a Vi+2 0-0.... o-o Vn, To avoid this, X and Z must be adjacent, and furthermore, the edge connecting X and Z must appear as a circle edge X a-o Z by Lem. 11.
(1(== x) (=(== X')o-....o
o-o
The existence of the edge x-o Z implies that there must be edges X Vú for all 3 S S or Z o-o V, for all 2 < i S n 2 by chordality. In the former case, we orient the subgraph of P over {Vi...., Vn) following a similar approach to the proof of Lemma 7.6 in Maathuis and Colombo [2015]. We begin by selecting vertex V22 and orient all edges incident to 1/2 as directed into V2- Since the subgraph is chordal and V/2 is simplicial, this orientation does not create any uncovered colliders in the subgraph. We then remove V/2 and the oriented edges from the subgraph. The resulting graph remains chordal and therefore again choose a vertex V3. and orient any edges incident to V/ into V33 We continue this procedure until all edges create any directed cycle, almost directed cycle, or uncovered collider, thus it is valid orientations. Since X + X' + ..... Y is valid, we have a directed path Z + + + X' + Y which leads contradiction.
oriented. The constructed subgraph does not
In the latter case, we can similarly orient the edges, starting from - and proceeding to V/2 Furthermore, this procedure can also be extended to cases where the graph takes on a superimposed form.
(Only if) Suppose that ex is relevant to ez in P. follows that (= X) (= X') (= Vo-oo((= Z) is an uncovered circle path. For the sake of contradiction, assume that X is a DMIS relative to [P, Y, I. Then, there exists MAG M conforming to P such that both px and pz are proper directed paths with respect to X in M. Therefore, we can orient V o-oooo V/2 as Vi - V2, and VA, o-o Vn- as V, - Vn-1 to construct M from P. Furthermore, since the circle path uncovered, Vi Vi+1 must be oriented V; V4a for i 2..... n 2. However, this orientation introduces a new uncovered collider Vn-2 + Vn-1 + V., which leads to a contradiction.
Vn-i(e (= Zz)o-ol o-o
Theorem 3 (Graphical characterization of POMIS for MAGs). Let M be a MAG over the set of variable V. A sei X C (Y) is a POMIS relative to [[, Y1 if and only if X IB(M, X).
Proof. (Only if) We will show contrapositive, i.e., X IB(M, Y. X) does not hold, then X not POMIS relative to [M, Y]. We denote W IB(M, Y, X) and T MUCT(M, Y, Y,)), assuming X # W. Let W A W X. Before proceeding with the main proof, we first establish that the following conditional independence statement holds:
Claim 1. (Y TL W' X) holds in Mxw
Note that laniu--aninllationn has higher priority than maniullannoooation so that 2xy or 2 denotes the graph resulting from applying the k-upper-manipulaee the Y -lower- manipulated graph of Q.
37

---

Proof. Suppose that the negation of this statement holds: (Y T W X) in M Xxw This would imply that there exists m-connected path from some W E W to Y given X in Mxw-- For the m-connected path exist, there must be no colliders, as node along the path can be an ancestor of X due to all incoming edges to X being cut in My. Moreover, as all outgoing edges from W are cut in Mw. the path cannot begin with an edge going out of W. Therefore, we get that the m-connected path must be of the following form: W + W1
Wn, + Ri + Rm + Y with n., 2 O where no node along the path can be in W; otherwise, it would either be part of X, since we are conditioning on X, or in W in which case all of its outgoing arrows would have been removed. Since Y is contained in T. the parent of Y. Rms along the path must be either in T or W. However, previously argued, node along the path can be in W; therefore, it must be in T. This reasoning can be applied iteratively up to Rt, implying that closed under PC, the inclusion of Rí TT implies that W,, must also
Rí is also in T. Since be in T. Additionally, because T is closed under descendants, W 1, Wi must also be in T. Consequently, W must be in T as well. However, this leads to a contradiction, since W is in W. and W and T are disjoint by definition. Therefore, the conditional independence statement (Y IL W' X) must hold in Xxw".
Claim 2. (Y TT X' W) holds in Mw xi where X' 2 X W.
W) holds in Mw x Then, there exists an m-connected path from some X E X' to Y given W in Mw.x Since all edges into X' are removed, the path must begin with an edge going out of X. The path cannot contain any colliders, as no node can be an ancestor of a node in the conditioned set W, given that all incoming edges to W are cut. Thus, all edges along the path must be directed, pointing to Y:
Proof. Suppose this statement is false, i.c. (Y 1 X'
X + W + > W,, + (n 2 0) where no node along the path can be in W. since we are conditioning on W. The parent of Y. Wn. along the path must be either in T or W, as Y in However, as previously argued, no node along the path can be included in W, which means it must be in T. This reasoning can be applied iteratively up W1, implying that W1 is also in T. Therefore, X must be parent of node in T, implying that X is in W. This leads to contradiction for X E X W.
We are now ready to proceed to the main proof. We will show that X is not a POMIS by proving that ux vw- in every SCM conforming to M. We derive that the following holds:
Px = E|Y do(x")]
E|Y do(x"), w' P'' do(x"))
E|Y do(x')
do(x*))
V. Claim 1
E[Y do(x [ do( do(x*))
Claim 2
w
< E[Y do do(ww)] do(x'))
= E|y do(w")]
Mw
Therefore, X not a POMIS with respect to [.M Y]. which completes the proof.
(If) To prove this direction, we will show that if X = IB(M, Y, X), then X is a POMIS relative to [[MY]] Suppose that X = IB(M, Y, X) holds. It suffices to show that there exists causal diagram 9 such that X is a POMIS relative [g, Y]. Consider the causal diagram 9 constructed by the following lemma:
Lemma 34. Let M be a MAG. Let G be the graph resulting from the following procedure applied to M.
Step 1. For each visible edge A + B in M, add A + B in G.
38

---

Step 2. For each bidirected edge A ++ B in M, add A + B G.
Step 3. For each invisible directed edge A - B in M, if it is the unique invisible edge among directed edges outgoing from A in M, then add both a directed edge A + and bidirected edge A 4> B g.
Step 4. Let TG - MUCT(G,) Y). Consider all nodes for which there are invisible edges outgoing from A in M.
1. If there exists B Ch(A)M that is contained in Tg. add both a directed edge + B and bidirected edge A + B, and add directed edges A - C for all
E Ch(A)M \ (B).
2. Otherwise, if there is no intersection with Tg, add directed edges A + C for all
C' C.
This step is repeated with the updated Tg < MUCT(G, Y) as long as 9 remains unchanged.
Then, the result graph a causal diagram conforming to M.
Proof. We need show that G and M have the same ancestral relations, and the same conditional independence relations.
@0 and M have the same ancestral relations). This is evident, each directed edge is added to 9 if and only if it also exists in M.
(& 9 and M encode the same independence relations). The graphs G and M differ only in the bidirected edges added to G corresponding to invisible edges in M. Thus, it suffices show that these additional bidirected edges added to G do not encode any additional independence between variables. Therefore, we need to show that these edges do not create any new uncovered colliders.
Consider bidirected edge A ++ B added to G in Step 3. For this added edge to create collider, there must be either a directed edge incoming to A (i.e., C + A + B), or bidirected edge incoming A (i.e., C + ++ B) G. both cases, B and C are adjacent in M, since A > invisible in .M by Lem. 19. Therefore, this collider A does not introduce any independence.
Now consider a bidirected edge ++ B added to G in Step The previous argument can be reused here to argue that this edge does not encode any new independence, since we add only one bidirected among outgoing directed edges from A. For clarity, suppose that we have MAG M = (A + A B, A + D) where B,C, and D are mutually not adjacent in M. Adding at most one + C, ++ B, or +> D does not introduce a new collider A, thereby preserving conditional independence.
Let G be the causal diagram constructed following Lem. 34. We will prove that X is POMIS with respect to [G, Yl. Let X be any variable in X. Then X is a parent of some T E MUCT(M, Y, X,X) in M. suffices to show that T MUCT(Gx. YY since this means that X is parent member of MUCT(Gx, Y). and is therefore in IB(Gx. Y).
Let Tg & MUCT(G, Y) and TM & MUCT(M,,,,)) 0).. We will show that TM C Tg. Let T be node in TM- We know such a node always exists because is in both Tg and TMM- Let H & G[(n(Y))s) and N & M(An(Y).M) Since M and share the same skeleton and the same ancestral relations among vertices, it follows that An(Y)M An(Y),, y, implying V(H)= VWN).
(a W E PC(T),, then W E Tg). Suppose that another node W is in the same pe-component of T in i... W PC(T))v. This implies that there exists a path between T and W in N such that (i) all non-endpoint nodes along the path colliders, and (ii) none of the edges visible.
For all directed edges + V along this path, if there does not exist an edge + Z(+ V) in N, bidirected edge U < V is added in Step Consequently, and W are the same c-component in H.
39

---

Otherwise, if there is some directed edge U + V along the path for which there exists U + Z( V), then from Step 4, we know that one of these outgoing edges from U will have a corresponding bidirected edge in H which adds U to Tg. Since MUCT is closed under descendants, all descendants of U are also included in MUCT well.
This logic applies along the entire path, ensuring that T E Tg = ET..
( If W E De(T) then W E Tş). Now, suppose that W is descendant of T in W, i.e., W E De(T)x Then W is a descendant of T in H as well, and so we have T E Tg = W E Tg.
@ implies TM S Tg). Thus, we have shown that any node which can be shown be TM can also be shown to be in Tg, and therefore TM S Tg.
can be applied to show that MUCT(M, Y, X) E MUC Y). as we can operate over .M X and G \ X instead of M and G, respectively. Thus, have that T MUCT(M, Y, X) implies T E MUCT(Gx. Y). Therefore, we can conclude that IB(9x. Y) X holds.
Proposition Let be PAG over V. A set x V (Y) is a POMIS relative to [P,Y] if and only if there exists MAG M conforming to P such that X is POMIS relative to [.M.]].
Proof. (If) Suppose X is a POMIS relative to [M,Y] Y] for some M conforming to P. Then there exists an SCM conforming to M such that jlx- > VWEDM. (X)//"XXWWww.... Since any SCM conforming .M also conforms P. the SCM also conforms to P, the SCM S also conforms to P, and thus X is a POMIS relative to [P, Yl.
(Only if) Let X be a POMIS relative to [P, Yl. Then there exists an SCM S conforming to such that ux* > WweD (XX))))))(()))..)). Mww Let be the causal diagram associated with the SCM S. Then, there exists a MAG M representing G that corresponds to P with X as a POMIS relative to [M, YJ, since Ppy Dy,y. This concludes the proof for this direction.
Proposition 7. Let Qx be a PMG representing MAGs where X is a POMIS with respect to Y. Then, the following properties hold in Qx.for every X E X:
1. Every uncovered proper possibly-directed path from X to Y relative to ends with an arrowhead (>).
If X is adjacent to Y, then the edge between X and Y a directed edge (X + +Y).
Proof. We will show that the conditions are necessary for X to be MIS in the MAGs, which implies that they are also necessary for X to be POMIS.
(First condition). For the sake of contradiction, suppose that there exists an uncovered path ending with tail mark at Y in MAG M [Qx]. This implies the path must take the form X t.... f- Y in M. Since X is an MIS relative to [M, Y], there exists a directed path from X to Y in M, which would introduce a directed cycle, leading to a contradiction.
(Second condition). We will first show X x*** Y forms Y in Qx, and then demonstrate that must be X + by proving that X ++ Y leads to a contradiction. For the sake contradiction, assume that there exists X Y a MAG M [Qx]. In M, any directed path from X to Y would violate the ancestral property, resulting in a MAG M E [2x] This configuration would also violate the ancestral property by introducing an almost directed cycle, which leads contradiction.
contradiction. Similarly. assume that there exists X < Y
Proposition 8. For every MAG M E [Qx], X is POMIS relative to [M,Y], then there exists PMG Q'x representing M such that the following conditions are satisfied:
1. Every circle mark around X (Y) in Qx is oriented as either a tail (-) ) or an arrowhead (>) in Q'x according valid local transformations.
40

---

2. Every E X is an ancestor Y
Y in Q'x 3. Oxx closed under orientation rules.
Proof. The first and third conditions are satisfied by the soundness and completeness of valid local transformations (Thm. 8). Furthermore, since X is a POMIS with respect to [P, Y] (thus, X is DMIS), the second condition also satisfied (see Lem. 22), which completes the proof.
Theorem 4 (Characterizatiion of POMIS for PAGs). [P, Y if and only if there exists Q'x satisfying Props. and 8 such that xx. Y.X) X.
X CVV (Y) is POMIS relative to
Proof. This follows from the result of Thm. 5.
Theorem (Soundness and completeness). The algorithm IsPOMIS (Alg. 1) returns True and only if there exists MAG M conforming to P such that X is POMIS relative to [M,Y],
Proof. (IsPOMIS returns True = 3g such that IB Y, Y) = X). Suppose that IsPOMIS
returns True. Then, there PMG Øx satisfying IB Φ Y,X) X. We will demonstrate that there exists MAG M E [2x] such that IB(M,Y, Y, X) X by constructing such MAG. To do so, consider the following lemma:
Lemma 35. Let 2x be PMG in Alg. 1. Let M be the graph resulting from the following procedure applied to Øx
Step 1. Orient partial directed edges (o-+ ) as directed edges (-+).
M Step 2. Consider A B in Ox. Let T & MUCT(M,Y, X). If B is contained in TX orient the circle component including as a DAG where each cirele edge involving A in Qx corresponds to directed edge outgoing from A in M (i.e., Ao-oV corresponds to A V).
This step is repeated with the updated TX + (M, X) as long as M remains unchanged.
Step 3. Orient remaining circle component into DAG with unshielded colliders.
Then, the resulting graph M is a MAG conforming to Qx
Proof. The construction follows Lems 6 and 12, and the fact that every circle component can be oriented independently by Lem. 31.
Now, we will show that the MAG M constructed according to Lem. 35 satisfies IB(M, X,X) = X. Let X be any node O Y, 7). Then, X is parent of some Tx E MUCT Qx Y, X) in Φx By Lem. 24, there exists uncovered possibly-directed path Tx o- Thx Due to the balanced property in Lem. 31 path X + Tx + + which corresponds to X + T + + Y in M by construction (see Step 1). Therefore, we have that for any nodes X X, X and T included in An(Y),, Our goal is to show that T E MUCT(M, Y, X) since this means X E IB(M, Y, X).
Y exists in Øx
For convenience, we denote TM = MUCT(M,,, X) and Tej MUCT(Q',, Y,X). Let N & M M(An(Y) and A Øx (YY) Suppose that is node such that E Tey (An(Y) and T E TMM We know such a node exists, as Y is in both T, M and Tox O An(Y))
@ If W& E component of in H. An()) This implies that there exists path between and W such that (i) all con-entdoint nodes along the path are colliders, and (ii) none of the edges are visible, i.c. T+ + + < W in M{)n(
M))) then W E TM). Suppose that another node W is in the same pc-
41

---

For all edges U 7- V along this path, the edges correspond to directed edges U + V in N. If there are no circle edges with in H. the edges remain invisible in N since orienting a tail mark alone does not introduce any visible edges.
Otherwise, if there are any circle edges U o-o Z in H that correspond to U + Z in N, no additional visible edges are introduced. When the edges correspond to U <- Z in .N, U would already have been included in TM,, which in turn ensures that V be included in T.M.
@& If W E PossDe (TssDe(T) (A) then W E TM). This means that there exists an uncovered possibly-directee path from T to W in H[An(Y) by Lem. 28. According to our construction, there is node S E TM (it could be T) in the same bucket as T and W such that all nodes in the bucket are descendants of S in M. Since W E De(S) and S E TM, we have W E TM-
( )). Thus, we have shown that any node in Tox AY can also be shown to be in T.M. and therefore we can get Tx E TM..
IB( X) is empty. For the sake of contradiction, consider any vertex W E W. Then, there exists node Tw E TM where W E Pa(aTT)aa M. Note that Tw E Tex n An())M holds (see the proof of the reverse direction). If W + Tw is invisible, then W is included in TM, leading to contradiction for W E: IB(M, X). If W + +Tw is visible in both M and Øx then we can find a visible edge W + Tw satisfying Y in M by Lems 24 and 27. This implies W E (B((xx Y, X), resulting in a contradiction. If W + Tw appeared as an invisible edge, either c-o or o-> W - Tw should also appear as an invisible edge by our construction (see Step 2). Therefore, we conclude the proof of the soundness of IsPOMIS.
The remaining task is to prove that W A IB(MYY,X
W .w ?_....._ Y in Ox corresponding to W Tw -
(IsPOMIS returns False = Z.M such that (B(M, Y, ()) = X). Suppose that X is POMIS relative to [M,Y], Then, we have = IB(M, Y, X). Let 2x be a PMG representing M. Moreover, we have that An(Y)m _ PossAn(()) (Y)) 2% holds by Lem. 28.
Let X be any variable in IB(M, X). Then, X is a parent of some Tx MUCT(M,,, X) in M. Furthermore, this appears in Øx by the construction of IsPOMIS in Alg. (outgoing edges from X are determined in ②x)) By Lem. 24, there exists an uncovered possibly-directed path 7x o-o 3 ...."
Y exists in 2x Now we will show that 7'x MMUCT(Xx.. Y, X) since this implies X E EBI(Ox Y, X).
Tx
......>>> in Φx Due to Lems 20 and 31, the path X + TTx +
Let TM A MUCT(M,Y,X X) and Tex A MUCT( Y,X). W A MlAn(Y) mm] and Q (PosSAAA) oz) Suppose that T is a node satisfying T E T n An and T E TMM- We know such node exists since Y is in both TM and Tøx AnnYY
H A
(If W& E TM, then W E T Tex O An(Y)m). Since any invisible edges in .M correspond to invisible ones in Øx we have W E PC)(TT) implies W E TT O An())) according to Lem. 30. Furthermore, we know that W E De(T") implies W E PossDe(T) H((m)(Y)) by Lem. 28. Therefore, we get that W Tox O An(Y),.. Thus, we have shown that any node in TM can also be shown to be in T oxx O AY(),,, and therefore Tx E ET
The remaining task is prove that W A IB(2xx Y,X) \ IB(M, Y, X) is empty. For the sake of contradiction, consider any vertex W E W. Then, there exists a node Tw E Tey where W Pa(Tww)x ox If W + Tw is invisible in Φ'x then W is included in Tox, leading contradiction for W E II( Q'xx Y). IF + Tw is visible in Ox it is also visible in M, and we can find a visible edge W - TN satisfying W + TW + ..... Y by Lems 24 and 27. This implies W E IB(M, Y. X), resulting in a contradiction. Therefore, we conclude the proof of the completeness of ISPOMIS.
42

---

Broader Impact Statement
This work addresses a structured causal bandit framework that leverages causal knowledge from Markov equivalence class represented by PAG. This approach has potential applications in practical settings such as personalized healthcare, adaptive education, and resource-constraineed recommendation systems, where decision-maker aims to make optimal decisions without assuming causal sufficiency (i.e., the absence of unobserved variables), assumption that is often unrealistic in practice. Therefore, this study takes step toward the practical application of the framework. However, improper specification of causal structures may lead to misleading conclusions and biased decisions; thus, careful validation and domain-specifie causal modeling essential prior deployment in high-stakes environments.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
The main claims are clearly stated in the abstract. The contributions are explicitly stated the introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations are clearly stated in the "Limitations and Future works" section in the supplemental material (Appendix F).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
43

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Detailed proofs are provided in the "Proofs" section in the supplemental material (Appendix H).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
We clearly state the experimental settings and provide additional details in the "Experimental Details and Additional Results" section in the supplemental material (Appendix D).
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible dataset, provide access the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
others to replicate the model with the same
44

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The provided code includes sufficient instructions reproduce all of
results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
wwm.iisssssiccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nipps.ccccc wttp:ccccppppuuuccccecccc hwabbllc/guidss... weoeeddueeeoeeeememioeeee ss ssiinnolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We clearly state the experimental settings and provide additional details in the "Experimental Details and Additional Results" section in the supplemental material (Appendix D).
45

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: deviations.
Our experimental plot (Fig. and Fig. 11) and table (Table 1) include standard
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We clearly state the computer resources in the "Experimental Details and Additional Results" section in the supplemental material (Appendix D).
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
46

---

Question:
Does the research conducted in the paper conform, in every respect, with the
NeurIPS Code of Ethics https: /ttpe////eeeips... http:///........ttttccccccc..ol.
Answer: [Yes]
Justification:
We have reviewed the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We clearly state the broader impacts of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper mainly deals with theoretical results that are unlikely misused.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
47

---

Datasets that have been scraped from the Internet could pose safety risks. The authors
should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All related and used results are cited properly.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode. thcode. com datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The code is provided with annotated descriptions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve human subjects.
Guidelines:
48

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Our work does not involve using LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to LLM policy (https: /tte::///eeeua /tt.//eurp...// cc/Connfreencces/22225 for what should or should not be described.
49


Reviews:
[{"review_id": "UgA75830fc", "reviewer": "Reviewer_QaCD", "summary": "The paper considers structural causal bandits.  It relaxes the assumption that a structural causal model must be provided to the agent apriori. Instead, it assumes that a partial ancestor graph is known.  The main contribution is an analysis with a corresponding algorithm to identify possibly optimal minimal intervention sets (POMISs).  This reduces the number of arms that need to be explored to find the the optimal arm.", "questions": "* Is there a way to explain the approach so that the average ML researcher without much causality background could apply the proposed approach?\n* What are the MIS and POMIS in each task and how is the count derived for the number of arms to be explored in each approach in the experiments?", "limitations": "The paper describes limitations in the appendix.", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Let me start by acknowledging that I am not an expert in structural causal bandits.  I lack background in causality to fully understand the details of this paper.  Hence, this evaluation is really a guess.\n\nStrengths:\n* Strong theoretical contribution\n* The first approach (to my knowledge) to identify POMISs\n* A practical approach to reduce the amount of exploration in structural causal bandits\n\nWeaknesses:\n* Since most ML practitioners may not be familiar with partial ancestral graphs (PAGs), it is not clear that practitioners will be able to provide a PAG as input.  This may or may not be a weakness of the approach if practitioners need to be educated.  Nevertheless, specifying a PAG should require less knowledge than specifying a structural causal model.\n* I found the paper difficult to read because of the high number of definitions, propositions and theorems before we get to the main contribution.  Again, I acknowledge that I don't have sufficient background in causality.  However, suppose that a practitioner wanted to use your approach.  Is there a way to explain the approach so that the average ML researcher without much causality background could apply the proposed approach?", "was_revised": true, "final_justification": "My evaluation is really a guess since I lack familiarity with the topic.  While I recommend acceptance, I will not object to rejection based on review by UG9x.", "rebuttal": "> Since most ML practitioners may not be familiar with partial ancestral graphs (PAGs), it is not clear that practitioners will be able to provide a PAG as input. This may or may not be a weakness of the approach if practitioners need to be educated. Nevertheless, specifying a PAG should require less knowledge than specifying a structural causal model\n> \n\n> suppose that a practitioner wanted to use your approach. Is there a way to explain the approach so that the average ML researcher without much causality background could apply the proposed approach?\n> \n\nA. Thank you for prompting us to provide a brief description of our framework’s workflow. We believe that our approach can be made accessible to practitioners with limited background in causality. \n\nThe Fast Causal Inference (FCI) algorithm [Spirtes et al., 2001b, Zhang 2008a] is a well-established causal structure learning method that infers a PAG from purely observational data using conditional independence tests among variables (Practitioners can use the python package *causal-learn* [Zheng et al., 2024] to run FCI and learn a PAG). Therefore, if a practitioner wishes to perform causal decision-making, they can first (1) apply FCI to obtain a PAG, and then (2) use our proposed method to prune the action space accordingly. This abstracted procedure facilitates causal decision-making without requiring full knowledge of the underlying causal diagram. \n\n- Zheng, Yujia, et al., Causal-learn: Causal discovery in python., JMLR (2024)\n\n> What are the MIS and POMIS in each task and how is the count derived for the number of arms to be explored in each approach in the experiments?\n> \n\nA. We appreciate your comment for helping us highlight this important point. Let us consider the PAG shown in Fig. 9. Given the PAG with 10 nodes, an agent can consider interventions on arbitrary combinations of nodes $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$.  The number of possible intervention sets is $2^9 = 512$ (i.e., the number of subsets of $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$), and the total number of corresponding arms is $\\sum_{i=1}^9\n\\binom{9}{i}K^i = (K+1)^9 = 19683$ with binary domains $K=2$.  \n\nIn this example, there are 152 MISs in total (identical to DMIS in this example). We present only the POMIS sets. The collection of POMISs (8 sets) is $\\lbrace \\lbrace E \\rbrace, \\lbrace E, F \\rbrace, \\lbrace E, H \\rbrace, \\lbrace E, I \\rbrace, \\lbrace E, F, I \\rbrace, \\lbrace E, F, H \\rbrace, \\lbrace E, H, I\\rbrace, \\lbrace E, F, H, I\\rbrace \\rbrace$ with a total of $(54 = 2 + 4\\ast 3 + 8\\ast 3+ 16)$ corresponding arms. Therefore, it suffices to consider only $\\frac{54}{19 683} \\approx 0.27$% of the total arms. The complete counts of intervention sets and their corresponding arms, for both the main and additional experiments, are provided in Table 2 in Appendix D. \n\n|  | Task1 (Fig. 5a) | Taks2 (Fig. 8) | Taks3 (Fig. 9) | Task4 (Fig. 11a) | Task5 (Fig. 11b) | Task6 (Fig. 11c) |\n| --- | --- | --- | --- | --- | --- | --- |\n| POMIS arms | **19 (23.5%)** | **89 (36.6%)** | **54 (0.27%)** | **15 (6.17%)** | **81 (3.7%)** | **231 (10.7%)** |\n| DMIS arms | 25 | 195 | 2025 | 57 | 189 | 1755 |\n| Total arms | 81 | 243 | 19683 | 243 | 2187 | 2187 |\n\nwhere the percentages indicate the ratio $\\frac{\\text{The number of POMIS arms}}{\\text{The number of Total arms}} \\times 100$, and tasks 4—6 are in Fig. 11 in Appendix D.  All POMISs of our experiments can be found in pages 25-26."}, {"review_id": "w0A7yUPMyb", "reviewer": "Reviewer_UG9x", "summary": "The paper addresses a multi-armed bandit setting in which actions and rewards form a causal graph. The authors consider a scenario where the causal graph is known only up to its Markov equivalence class, in contrast to prior work that assumes the graph is fully known. The goal of the paper is to preprocess and identify the actions (i.e., interventions) that could be optimal given information. This approach can significantly reduce the action space.", "questions": "1- Could you elaborate on the point noted in the section above?\n\n2- As you mentioned in the related work, Elahi et al. [2024] consider the causal bandit problem with an unknown graph. How does your approach (i.e., finding the POMIS set in the MAG and running KL-UCB) compare to theirs, both theoretically and practically?\n\n3- Can you provide an analysis of how much the action space is reduced? For example, could you quantify this for a specific graph structure if a general result is not possible?", "limitations": "Yes.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 1, "originality": 3, "strengths_and_weaknesses": "The paper presents solid theoretical results and provides a graphical characterization of potentially optimal actions within Markov equivalence classes. However, I have some concerns about the effectiveness of the proposed method in reducing cumulative regret. While I agree that the action space can be significantly reduced, this does not necessarily lead to optimal regret performance. For example, since arbitrary interventions are allowed, why not attempt to dynamically learn the graph structure while optimizing regret? In that case, the actions removed during the preprocessing phase might actually be beneficial. Alternatively, is it possible to formally show that the removed actions are uninformative?", "was_revised": true, "final_justification": "The paper aims to characterize the best possible optimal arms in PAGs. By identifying this set of possible arms, the arm set size can be significantly reduced. However, the main issues with the paper are:\ni) they do not provide any non-trivial algorithm for the online phase,\nii) they do not present any regret bound comparable to previous work, and\niii) more generally, there is no clear justification for why this pruning in the offline phase is necessary. There might be alternative approaches that could lead to better regret. For example, ideas similar to those proposed by Elahi et al. [2024].\n\nI discussed these concerns with the authors, but their responses did not convince me.", "rebuttal": "> While I agree that the action space can be significantly reduced, this does not necessarily lead to optimal regret performance. For example, since arbitrary interventions are allowed, why not attempt to dynamically learn the graph structure while optimizing regret? In that case, the actions removed during the preprocessing phase might actually be beneficial. \n> \n\nA. We are grateful for sharing your insightful feedback. Discovering graphical structures is a core line of research in the causal inference literature, referred to *causal discovery.* To clarify our focus, we need to provide representative studies that aim to causal discovery from interventions. \n\n**Offline causal discovery from interventions.** In the offline or non-adaptive setting, interventions are predetermined before algorithm execution. [Hauser and Bühlmann, 2012] studied the problem of learning graph structures from interventions under the assumption of no unobserved confounders, while [Kocaoglu et al., 2017] explored experimental design for learning causal diagrams from interventions. Recently, [Zhou et al., 2025] investigated learning PAGs from interventions. \n\n**Online causal discovery from interventions.** While those offline causal discovery researches require access to infinite interventional samples, there has been intensive works that *adaptively* selects interventions from an online learning. [Squireset al., 2020; Choo and Shiragur, 2023] applied interventions sequentially, with adaptively chosen targets at each step, still necessitating access to interventional distributions (i.e., an infinite number of interventional samples). Although [Greenewald et al. 2019;  Elahi et al., 2024b] worked with finite interventions, it is applicable only when the underlying causal structure has no unobserved confounders. Notably, designing adaptive discovery algorithms that work with finite interventions *and* allow for unobserved confounders remains an open problem. \n\n|  | cover unobserved confounder | online discovery | Interventional sample efficiency |\n| --- | --- | --- | --- |\n| [1] Hauser and Bühlmann, 2012 | x | x | x |\n| [2] Kocaoglu et al., 2017 | o | x | x |\n| [3] Greenewald et al. 2019 | x | o | o |\n| [4] Squires et al., 2020 | x | o | x |\n| [5] Choo and Shiragur, 2023 | x | o | x |\n| [6] Elahi et al., 2024b | x | o | o |\n| [7] Zhou et al., 2025 | o | x | x |\n\nIt may possible to incorporate online causal discovery into the decision-making process.  For example, at each step, an agent may choose interventions aimed at improving structural knowledge, while also expecting that those arms could be valuable for minimizing regret. However, designing algorithms that effectively balance exploration for structure learning and for regret minimization poses substantial additional challenges, as these two objectives—-structure discovery and regret minimization—are not naturally aligned. \n\nWhile we acknowledge this as an interesting direction, our main contribution lies in providing a sound and complete characterization of optimal action selection given a PAG, which is obtained in the offline phase without interventions. We believe this foundation can complement future work on integrating online structure refinement where beneficial.   \n\n- [1] Hauser, Alain, and Peter Bühlmann., Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs., JMLR (2012)\n- [2] Kocaoglu, Murat, Karthikeyan Shanmugam, and Elias Bareinboim., Experimental design for learning causal graphs with latent variables., NeurIPS (2017).\n- [3] Greenewald, K., et al., Sample efficient active learning of causal trees., NeurIPS (2019).\n- [4] Squires, C., et al., Active structure learning of causal dags via directed clique trees., NeurIPS (2020).\n- [5] Choo, D. and Shiragur, K. Adaptivity complexity for causal graph discovery. arXiv preprint (2023).\n- [6] Muhammad Qasim Elahi, et al., Adaptive Online Experimental Design for Causal Discovery., ICML(2024b).\n- [7] Zhou, Zihan, Muhammad Qasim Elahi, and Murat Kocaoglu., Characterization and Learning of Causal Graphs from Hard Interventions., arXiv preprint (2025).\n\n> Alternatively, is it possible to formally show that the removed actions are uninformative?\n> \n\nA. From the perspective of regret minimization, arms that are not POMIS are clearly uninformative by the definition of POMIS (Definition 4). Accordingly, our algorithm (Alg. 1) ensures that only suboptimal or redundant arms are pruned. \n\n\n> As you mentioned in the related work, Elahi et al. [2024] consider the causal bandit problem with an unknown graph. How does your approach (i.e., finding the POMIS set in the MAG and drunning KL-UCB) compare to theirs, both theoretically and practically?\n> \n\nA. We deeply appreciate your pointed comment, which helps us highlight an important distinction between our work and [Elahi et al., 2024].  \n\n**Theoretical comparison.** As you noted, suboptimal arms (i.e., non-POMIS arms) can be useful for learning the underlying causal graph structure—-a direction explored by [Elahi et al., 2024]. To briefly summarize their approach:\n\n(1) The first phase learns the induced subgraph of the ancestors of the reward node $Y$ in an online manner, by interventions over $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$; (2) Using the learned graph, they identify POMISs following the method of [Lee and Bareinboim, 2018]; (3) Finally, they run standard UCB with the identified POMISs. \n\nTheir key contribution lies in (1) learning the graph until it is sufficient to identify POMISs; particularly uncovering ancestral relations and latent confounders using interventions. However, they acknowledge that sample-efficient learning of causal diagrams with latent confounders without any assumptions is challenging. To address this, their method assumes certain testable conditions, such as probability gaps among variables. \n\nIn contrast, our work does not focus on causal discovery, but instead assumes access to a PAG (e.g., obtained via FCI algorithm [Spirtes et al., 2001b; Zhang, 2008a]) and aims to identify POMISs directly from a PAG input. That is, given a PAG from purely observational data, our algorithm prunes suboptimal arms *a priori*, without requiring any interventional data for causal discovery. \n\nIn summary, while [Elahi et al., 2024] focus on discovering a subgraph sufficient to identify POMISs, our work addresses the problem of identifying POMISs given a PAG. \n\n**Practical comparison.** From a practical perspective, interventional (experimental) data is often more costly and risk-prone than observational data. This suggests that our approach first discovering a PAG from observational data and then identifying POMISs may offer substantial advantages in resource-constrained or high-risk domains, compared to methods that rely on extensive intervention for graph discovery. \n\n> Can you provide an analysis of how much the action space is reduced? For example, could you quantify this for a specific graph structure if a general result is not possible?\n> \n\nA. Thank you for the opportunity to emphasize how significantly the action space can be reduced. We first note that, in general, there is no known method to precisely quantify the number of arms based solely on the graph structure. However, in specific cases---such as when (1) the system is assumed to be Markovian or when there are no unobserved confounders between $Y$ and its ancestors; and (2) given the corresponding causal diagram---it is known that the set of parents of $Y$ is the only POMIS (Proposition 2 and Corollary 3 in [Lee and Bareinboim, 2018]. In such cases, the number of arms reduces to the cardinality of $Pa(Y)$. \n\nSince the number of POMIS arms depends on the graphical instance, we provide the example our paper addressed. Let us consider the PAG shown in Fig. 9. Given the PAG with 10 nodes, an agent can consider interventions on arbitrary combinations of nodes $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$.  The number of possible intervention sets is $2^9 = 512$ (i.e., the number of subsets of $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$), and the total number of corresponding arms is $\\sum_{i=1}^9\n\\binom{9}{i}K^i = (K+1)^9 = 19683$ with binary domains $K=2$.  The number of POMISs is 8, with a total of 54 corresponding arms. Therefore, it suffices to consider only $\\frac{54}{19 683} \\approx 0.27 $\\% of the total arms. The complete counts of intervention sets and their corresponding arms, for both the main and additional experiments, are provided in Table 2 in Appendix D. \n\n|  | Task1 (Fig. 5a) | Taks2 (Fig. 8) | Taks3 (Fig. 9) | Task4 (Fig. 11a) | Task5 (Fig. 11b) | Task6 (Fig. 11c) |\n| --- | --- | --- | --- | --- | --- | --- |\n| POMIS arms | **19 (23.5%)** | **89 (36.6%)** | **54 (0.27%)** | **15 (6.17%)** | **81 (3.7%)** | **231 (10.7%)** |\n| DMIS arms | 25 | 195 | 2025 | 57 | 189 | 1755 |\n| Total arms | 81 | 243 | 19683 | 243 | 2187 | 2187 |\n\nwhere the percentages indicate the ratio $\\frac{\\text{The number of POMIS arms}}{\\text{The number of Total arms}} \\times 100$, and tasks 4—6 are in Fig. 11 in Appendix D. All POMISs of our experiments can be found in pages 25-26."}, {"review_id": "xEFoSNWlR7", "reviewer": "Reviewer_FQk8", "summary": "This paper studies the causal bandit problem under do interventions and unrestricted structural causal models. In this setting, many multi-node interventions (i.e., arms of the causal bandit) are equivalent since do interventions break the causal paths that start upstream and pass through the intervened node to affect the reward. This notion is previously formalized under (possibly-optimal) minimal intervention sets (PO)MISs, for causally sufficient models. The whole focus of this paper is on generalizing this concept to ancestral graphs. Specifically, characterizing and determining the conditions of a set being POMIS given a partial ancestral graph.", "questions": "**Questions about the setting and positioning of the paper**:\n1. MIS-POMIS notions are strictly for causal bandits with *do-hard* interventions. Many papers on causal bandits, including some of the first ones, indeed use do interventions. However, many of the more recent papers, including some of the papers that are covered in the related work discussion, focus on ``soft intervention’’. To clarify, in the soft intervention case, the downstream effect of an intervention is not cancelled out by the other interventions on the causal path to the reward node. In the next version of the paper, I strongly suggest that soft interventions to also be discussed (at least briefly), and the distinction/positioning of the paper should be clearer. \n2. Causal bandits with unknown graphs: Discussion on this subject is incomplete. To my knowledge, Bilodeau et al. (2022) (which is already cited), de Kroon et al. (2022), and Malek et al. (2023) have some results for unknown graph structures as well. More recently, Yan et al. (2024b) studied unknown causal graphs with soft interventions (under a linear model).\n\nThis is not really a weakness, but more of a comment/question. The theoretical nature of the paper is quite involved. I’m mostly familiar with this line of work, and still, I found it difficult to follow since it requires calling many tools and notions from the literature---which are inevitably mostly relegated to the appendix. In this regard, I wonder whether a journal would have been a more appropriate venue for this paper to be hosted, reviewed more carefully, etc.\n\n**Experiments**:\nAs discussed in Appendix F, one limitation of the current work is that it still requires the partial ancestral graph as input. It would have been interesting to see how robust the proposed algorithm (and the gains w.r.t. the baselines) is under slight perturbations of the input PAG, e.g., a couple of misspecified edges, which is a realistic setting for practical usage. For instance, Yan et al. (2024a), Peng et al. (2025), and Varici et al. (2023) demonstrate some empirical results for robustness and/or misspecifications.\n\n**Minor points:**\n* For example, Rule 3 of do-calculus for MAGs is given in the Appendix, but its understanding is crucial for the main body. In particular, the possible vacuousness of MIS for PAGs is explained through this rule. Hence, it’d be better to make the rule clear in the main paper. This is related to my broader point that, in my opinion, it’s difficult to fit the content of this paper into a 9-page conference format.\n* Footnote 4: PAGs have “partially ordered” topological orders, right?\n\n**References**\n- Malek, A., Aglietti, V., & Chiappa, S. (2023). Additive causal bandits with unknown graph. ICML 2023\n- De Kroon, A., Mooij, J., & Belgrave, D. (2022). Causal bandits without prior knowledge using separating sets. CLeaR 2022\n- Yan, Z., Mukherjee, A., Varıcı, B., & Tajer, A. (2024a). Robust causal bandits for linear models. IEEE Journal on Selected Areas in Information Theory.\n- Yan, Z., & Tajer, A. (2024b). Linear Causal Bandits: Unknown Graph and Soft Interventions.  NeurIPS 2024\n- Peng, C., Zhang, D., & Mitra, U. (2025). Asymmetric graph error control with low complexity in causal bandits. IEEE Transactions on Signal Processing.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:** The paper has a clear problem---generalizing (possibly-optimal) minimal intervention sets (PO)MISs, which were previously proposed and studied under causal sufficiency, to ancestral graphs. This is a niche yet interesting problem that is unexplored to my knowledge. While the paper does not introduce new tools for solving this problem (if I'm not missing), still, the solution steps and progression of the results are rigorous.\n\n**Weaknesses:** While related work discussion is mostly good, I think the positioning of the paper is missing some important clarifications on the intervention model (and relatedly, some recent references are missing). See my detailed comments below the questions.", "was_revised": true, "final_justification": "As I stated in my initial review, the paper has a clear (albeit niche) problem and solves it rigorously. I find this problem/solution possibly interesting to the causal bandits community, which is a clear positive factor in my evaluation. On the other hand, technical novelty is limited (not at the level of 'very clear accept' threshold for me). Also, the revision should carefully address the valid concerns of reviewer UG9x regarding the utility of the proposed approach compared to Elahi et al. (2024). To be clear, I understand, settings are different (offline vs. online causal discovery stages), though the utility of the current setting (offline discovery, taking PAG as input) is not very clearly conveyed, beyond the appreciation of the technical problem.\n\nOverall, I remain slightly positive about this paper, and maintain my score (4).", "rebuttal": "> MIS-POMIS notions are strictly for causal bandits with *do-hard* interventions. Many papers on causal bandits, including some of the first ones, indeed use do interventions. However, many of the more recent papers, including some of the papers that are covered in the related work discussion, focus on ``soft intervention’’. To clarify, in the soft intervention case, the downstream effect of an intervention is not cancelled out by the other interventions on the causal path to the reward node. In the next version of the paper, I strongly suggest that soft interventions to also be discussed (at least briefly), and the distinction/positioning of the paper should be clearer.\n> \n\n> Yan et al. (2024b) studied unknown causal graphs with soft interventions (under a linear model).\n> \n\nA. We sincerely appreciate for pointing this out. We would like to refer to the sentence in Lines 44–45: “[Lee and Bareinboim, 2020] and [Everitt et al., 2021] established SCM-MAB with stochastic policies, and [Carey et al., 2024] studied the completeness of its graphical characterization.” To elaborate further, [Lee and Bareinboim, 2020] introduced the concept of *Possibly Optimal Mixed Policy Scope* (POMPS), a soft-intervention counterpart to POMIS, along with its graphical characterization. Similarly, [Everitt et al., 2021] proposed a related framework in the context of the *influence diagrams* literature. Subsequently, [Carey et al., 2024] studied the completeness of POMPS characterization, although this still remains an open problem. \n\nWe will revise this part to improve clarity in related works (Appendix A) of the final version with additional reference [Yan et al., 2024b]. Thank you again for your insightful comment. \n\n- Yan, Z., and Tajer, A., Linear Causal Bandits: Unknown Graph and Soft Interventions., NeurIPS (2024b).\n\n> Causal bandits with unknown graphs: Discussion on this subject is incomplete. To my knowledge, Bilodeau et al. (2022) (which is already cited), de Kroon et al. (2022), and Malek et al. (2023) have some results for unknown graph structures as well. More recently,\n> \n\nA. [Bilodeau et al., 2022] and [de Kroon et al., 2022] assumed *causal sufficiency*---that is, the absence of unobserved confounders and thus no bidirected edges in the graph. While [Malek et al., 2023] also 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 they assumed no confounding exists between the reward variable $Y$ and its ancestors. We will also append the works into related works (Appendix A), discussing on comparison with this line of work. \n\n- De Kroon, et al., Causal bandits without prior knowledge using separating sets., CLeaR (2022).\n- Malek, A., et al., Additive causal bandits with unknown graph., ICML (2023).\n\n> This is not really a weakness, but more of a comment/question. The theoretical nature of the paper is quite involved. I’m mostly familiar with this line of work, and still, I found it difficult to follow since it requires calling many tools and notions from the literature---which are inevitably mostly relegated to the appendix. In this regard, I wonder whether a journal would have been a more appropriate venue for this paper to be hosted, reviewed more carefully, etc.\n> \n\nA. We appreciate your thoughtful comment. We fully agree that the theoretical nature of the paper demands a substantial background and inevitably involves many technical tools, some of which are deferred to the Appendix due to space constraints. \n\nWe chose to submit this work to NeurIPS because we believe the conference offers a valuable venue for early dissemination and active discussion with a community of experts in related areas, including causal inference [Jaber et al., 2022], causal bandits [Lee and Bareinboim 2018, 2020; Wei et al., 2023; Elahi et al., 2024], and graphical models [Wang et al., 2022]. In particular, there might be audiences who are actively seeking the solutions addressed in our work, and we hope to contribute meaningfully to these ongoing conversations. \n\n> It would have been interesting to see how robust the proposed algorithm (and the gains w.r.t. the baselines) is under slight perturbations of the input PAG, e.g., a couple of misspecified edges, which is a realistic setting for practical usage.\n> \n\nA. This is an insightful suggestion. We agree that it is an important direction. One possible approach could involve checking the compatibility of observed data with the given PAG while pulling POMIS arms, thereby identifying inconsistencies that may hint at structural misspecification. This idea resonates with hybrid strategies that combine exploration for model validation (e.g., $\\epsilon$-greedy mechanisms) with regret minimization via UCB or Thompson Sampling. Alternatively, one could consider scenarios where multiple PAG candidates are available. In such cases, pulling POMISs from each candidate—possibly with appropriate weighting on overlapping arms—might allow the agent to gradually place higher confidence on the true PAG. However, this strategy leans more toward *causal discovery* than regret minimization and falls outside the primary scope of our contribution. \n\nWe would like to note that our algorithm relies entirely on the partial information encoded in a PAG when determining POMISs. Importantly, the edges in a PAG are not independent; rather, they are governed by structural constraints and logical dependencies. For example, in the structure $A *\\to B \\circ - *C$ , one can deduce $A \\ast\\to C$ (*balanced property*; shown in Lemma 4). Due to the structured entanglements, it is indeed difficult to expect that computing POMISs on an incorrect PAG would lead to robust results. We will include this limitation into the Limitation section in the final version.  \n\n> For example, Rule 3 of do-calculus for MAGs is given in the Appendix, but its understanding is crucial for the main body. In particular, the possible vacuousness of MIS for PAGs is explained through this rule. Hence, it’d be better to make the rule clear in the main paper.\n> \n\nA. This is an excellent suggestion. We will add do-calculus for MAGs and PAGs (Theorem 6 in Appendix B.1) into main body, utilizing an extra page in the final version. \n\n> Footnote 4: PAGs have “partially ordered” topological orders, right?\n> \n\nA. Yes, that is correct. PAGs have partial topological order among circle components (Lemma 17 in Appendix B.2.3)."}, {"review_id": "OE69UDUdYY", "reviewer": "Reviewer_nSMs", "summary": "This paper proposes a general framework for bandit learning when the causal structure of the data generating process is only known up the Markov equivalence class of partial ancestral graphs (PAG) and associated maximum ancestral graphs (MAG). The aim of the work are to extend prior research on the structured causal bandit (SCB) problem to practical applications involving learning from observational data, where causal relations can only be known up to PAG and MAG. The paper contributes by developing the theory for learning the sets of interventions worth exploring in this problem setting, and then devising an algorithm to discern whether such a discovered set is possibly optimal.", "questions": "Experimental evaluations:\n1. Do you have any evidence or references that 5'000 and 10'000 trials are enough? \n2. Are the number of nodes considered relevant for empirical problems? I would expect that practical problems can involve much large graphs (and intervention sets) than those considered here. How would the two proposed methods scale computationally with the size of a graphs and intervention sets? A comment on this would help readers understand the applicability of the work to real data. \n\nI ask for this because, as far as I know, causal discovery is still a research area primarily of theoretical interest. For applied sciences where causal inference methodology is critical and appreciated, like epidemiology, political science, and economics, causal discovery algorithms have yet to really demonstrate a practical usefulness. \n\nThis is not to say that the authors work is intrinsically less valuable, but because the problem being studied is explicitly motivated by a lack  of knowledge of the true graph in \"practical contexts\", it would, at the minimum, be useful to understand when also the authors approach of working with Markov Equivalence classes would provide any tangible progress in real-world settings. Some comments and discussions would be appreciated,", "limitations": "Appendix F provides some discussion of limitations and opportunities for future work. The paper could benefit from further discussing the problem that, in practice, the SCM is essentially never known outside of deterministic DGPs or trivial settings. The authors kind of touch on this by noting that assumed SCMs may not fully capture real world systems (first paragraph) and that their work assumes knowledge of the PAG (second paragraph).\n\nHowever, the main issue underlying the uptake of SCMs for research in applied sciences is that we do not know the true SCM to begin with, and learning it via causal discovery algorithms, even if only up to a PAG or MAG, is to my knowledge not very reliable because causal discovery algorithms tend not to be robust against sampling variability, measurement errors, and other practical problems related to statistical uncertainty in empirical data. Currently, the paper appears to \"abstract away\" this problem, which is fine for theoretical research. If the work is to be positioned as useful for practice, however, then it should be acknowledged and carefully discussed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The problem is well-defined and the authors clearly address the problem being studied. \n2. The results appear to be complete and novel.\n\nWeaknesses:\n3. The paper is positioned as addressing a problem for practical applications, yet does not fully engage with what (I understand) is the main hindrance to the uptake of the class of methods being studied. This is a limitation to its significance.\n4. The experimental evaluation does not seem comprehensive. This affects the quality a bit.\n5. The writing is technically sound but at times very dense, negatively affecting clarity. I am referring to Sec. 3-4 in particular. The paper could be improved by simplifying the exposition, if possible. \n6. The work is incremental, in the sense that it takes a known results and extends them by relaxing an assumption. Please correct me if this is the incorrect interpretation of what the paper does. If my understanding is right, then originality is limited.\n\nPlease see Questions for details on weaknesses.", "was_revised": true, "final_justification": "I updated my score from Bordeline Accept to Accept in light of the authors response to my review.", "rebuttal": "> 3. The paper is positioned as addressing a problem for practical applications, yet does not fully engage with what (I understand) is the main hindrance to the uptake of the class of methods being studied. This is a limitation to its significance.\n> \n\nA. We deeply appreciate for your valuable feedback. We will revise this point to better underscore the position of our paper. To clarify, our work aims to provide a theoretical guarantee for the *a priori* elimination of suboptimal arms by leveraging structural knowledge encoded in a PAG, rather than a fully specified causal diagram. This is motivated by the fact that, in the absence of the *causal sufficiency* assumption (i.e., in the presence of unobserved confounders), only a PAG can be obtained from observational data. Accordingly, our framework offers a practically meaningful guideline for action space pruning under more commonly encountered assumptions. This directly addresses a key barrier to the practical uptake of causal bandit methods—-namely, the reliance on a fully specified causal diagram, which is rarely available. By operating under the weaker assumption of partial causal knowledge, our approach significantly broadens the applicability and accessibility of these methods. \n\n\n\n> 5. The writing is technically sound but at times very dense, negatively affecting clarity. I am referring to Sec. 3-4 in particular. The paper could be improved by simplifying the exposition, if possible.\n> \n\nA. We have made efforts to follow the notation used in prior work as closely as possible, particularly those by [Wang et al., 2022, 2023ab, 2024ab], [Zhang 2008ab], and [Jaber et al., 2018, 2022]. That said, we acknowledge that the exposition in Sections 3–4 can be dense, and we will make further efforts to improve clarity, making use of the extra page available in the final version. \n\n\n\n> 6. The work is incremental, in the sense that it takes a known results and extends them by relaxing an assumption. Please correct me if this is the incorrect interpretation of what the paper does. If my understanding is right, then originality is limited.\n> \n\nA. We are happy to emphasize this point. At first glance, one might view our work as a natural extension of existing methods from causal diagrams to PAGs—-for example, by replacing ancestral relations with “possibly ancestral” ones, or substituting the standard do-calculus for causal diagrams [Pearl, 1995] with the do-calculus for PAGs [Jaber at el., 2022]. However, as the saying goes, “*the devil is in the details.”,* extending structural causal bandits from causal diagrams to PAGs presents several nontrivial challenges:\n\n1. As discussed in Section 3.1 (MIS for PAGs and Its Possible Vacuousness), the standard notion of MIS does not behave as expected in PAGs, necessitating the introduction of *Definitely MIS* (DMIS).\n2. The naive intuition of simply replacing deterministic relations with “possible” ones fails to capture the correct characterization of POMISs in PAGs. We refer to corresponding challenge in the section “Discussion on Partial Mixed Graphs Obtained from Local Transformation” in Appendix E.2.\n3. The edges in a PAG are governed by structural constraints and logical dependencies. For example, in the structure $A *\\to B \\circ  - *C$ , one can deduce $A \\ast\\to C$ (*balanced property*; shown in Lemma 4). Furthermore, any circle components (composed only with circle edges $\\circ - \\circ$ ) in a PAG are chordal graph.  These structural entanglements pose significant challenges when proving the soundness and completeness of graphical characterizations in PAGs. \n4. To obtain solid theoretical result, we need to extend the known result to Partial Mixed Graphs (PMGs) incorporating local transformation (e.g., visibility, partial ancestral relation, balanced properties for the PMGs). We built this point in the “Auxiliary Results” section in Appendix G. \n\nWe hope the reviewer appreciates that these challenges partly explain the length and complexity of the proofs provided in our Appendix G and H.\n\n\n\n> Do you have any evidence or references that 5'000 and 10'000 trials are enough?\n> \n\nA. The number of trials is selected such that the cumulative regret with respect to POMIS stabilizes across 1000 repeated runs. Our experimental setup closely follows those of [Lee and Bareinboim, 2018] and [Wei et al., 2023].\n\n\n\n> 4. The experimental evaluation does not seem comprehensive. This affects the quality a bit.\n> \n\n> Are the number of nodes considered relevant for empirical problems? I would expect that practical problems can involve much large graphs (and intervention sets) than those considered here. I ask for this because, as far as I know, causal discovery is still a research area primarily of theoretical interest. For applied sciences where causal inference methodology is critical and appreciated, like epidemiology, political science, and economics, causal discovery algorithms have yet to really demonstrate a practical usefulness.\n> \n\nA. We appreciate your concern regarding the scope of the experimental evaluation. However, we would like to clarify that our work does not focus on causal discovery; rather, it assumes a given PAG as input and centers on the theoretical developments in graphical characterizations. Specifically, our contributions lie in proving the soundness and completeness of the proposed algorithm for identifying POMISs from a PAG. Given this theoretical orientation, the number of nodes does not affect the validity of our results. \n\nFor the experiments, we deliberately chose representative PAGs that facilitate reader understanding. The underlying SCMs were constructed using a randomized yet principled procedure to ensure diversity and fairness. We believe these instances serve as meaningful test cases that reflect the theoretical nature of our work, rather than aiming for exhaustive empirical benchmarking. \n\n\n\n> How would the two proposed methods scale computationally with the size of a graphs and intervention sets? A comment on this would help readers understand the applicability of the work to real data.\n> \n\nA. Thank you for your comment about complexity. Identifying all POMIS sets requires checking all subsets of $\\mathbf{V} \\setminus \\lbrace Y \\rbrace$ using IsPOMIS (Alg. 1), and thus the size of the search space grows exponentially. However, since all non-DMIS sets are filtered out, the enumeration process effectively depends only on the number of DMISs, i.e. $\\mathcal{O}(2^d)$ where $d$ denotes the number of DMISs.  \n\nMoreover, although [Lee and Bareinboim, 2018] provided an efficient algorithm for enumerating all POMISs in a causal diagram by leveraging a topological order between $Y$ and other variables, such an approach is *not* applicable to PAGs, where the topological order is not determined; this fundamental challenge with respect to *undetermined* topological order in PAGs lead to exponential complexity. We would like to note that discussion on complexity is shown in footnote 4 in page 8, and further detailed discussions are addressed in the “Discussion on Complexity of Enumerating POMISs for PAG.” section in Appendix E.2.\n\n\n\n\n> However, the main issue underlying the uptake of SCMs for research in applied sciences is that we do not know the true SCM to begin with, and learning it via causal discovery algorithms, even if only up to a PAG or MAG, is to my knowledge not very reliable because causal discovery algorithms tend not to be robust against sampling variability, measurement errors, and other practical problems related to statistical uncertainty in empirical data. Currently, the paper appears to \"abstract away\" this problem, which is fine for theoretical research. If the work is to be positioned as useful for practice, however, then it should be acknowledged and carefully discussed.\n> \n\nA. We appreciate your thoughtful comment. Our work does not focus on causal discovery itself, and thus assumes access to a correct PAG as a starting point—-an assumption commonly made in this line of research (e.g., adjustment in PAGs [Wang et al., 2023a], causal effect identification, and do-calculus for PAGs [Jaber et al., 2022]). However, we fully agree that in practical applications, the reliability of causal discovery algorithms is limited due to statistical uncertainty, measurement noise, and sampling variability. Since our method builds upon a given PAG, we acknowledge that this limitation deserves more explicit discussion. \n\nWhile we referred this point in Lines 1593—1595 of the section Broader Impact Statement—-“Improper specification of causal structures may lead to misleading conclusions and biased decisions; thus, careful validation and domain-specific causal modeling are essential prior to deployment in high-stakes environments”—-we agree that a more direct discussion of this point would strengthen the paper. In the camera ready version, we will add a dedicated note in the limitations section to clarify that the reliability of the input PAG is critical for safe and effective application, and that care must be taken. Thank you again for your constructive suggestions. Your feedback will strengthen our work."}]

Author rebuttal:

Meta-review: The paper presents a study on stochastic causal bandit with latent variables, and it starts with a Markov equivalent class. Addressing causal bandits with latent variables and unknown causal graph structure is an important topic, and the reviewers acknowledge the importance and appreciate that the authors provide a solid algorithmic contribution with theoretical analysis. After the rebuttal and discussion period, one major remaining concern is that the work requires a preprocessing period to obtain the Markov equivalent class, while some other studies do not need this preprocessing period and is purely online processing, e.g. [Elahi et al., 2024] . 

After reading the review comments and discussion, I feel that the technical contribution of the paper overall is solid, and outweigh this concern of preprocessing. In some scenarios, preprocessing data to obtain Markov equivalent class may be necessary anyway and may already have been done, and thus some method utilizing the Markov equivalent class could be reasonable and worth exploring.

Therefore, I would like to recommend the paper for acceptance, but indeed the paper is more or less at the boundary of NeurIPS acceptance bar. I hope that the authors could provide a thorough revision addressing all concerns from the reviewers to improve the quality of the paper, and provide a detailed discussion on the reliance of Markov equivalent class.
Decision: Accept (poster)