Structural Causal Bandits under Markov Equivalence

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.

A. 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.

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.

A. 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.

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.

A. 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:

1. 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).
2. 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.
3. 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.
4. 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.

We hope the reviewer appreciates that these challenges partly explain the length and complexity of the proofs provided in our Appendix G and H.

Do you have any evidence or references that 5'000 and 10'000 trials are enough?

A. 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].

4. The experimental evaluation does not seem comprehensive. This affects the quality a bit.

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.

A. 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.

For 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.

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.

A. 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.

Moreover, 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.

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.

A. 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.

While 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.

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.

Yan et al. (2024b) studied unknown causal graphs with soft interventions (under a linear model).

A. 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.

We 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.

• Yan, Z., and Tajer, A., Linear Causal Bandits: Unknown Graph and Soft Interventions., NeurIPS (2024b).

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,

A. [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.

• De Kroon, et al., Causal bandits without prior knowledge using separating sets., CLeaR (2022).
• Malek, A., et al., Additive causal bandits with unknown graph., ICML (2023).

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.

A. 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.

We 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.

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.

A. 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.

We 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.

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.

A. 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.

Footnote 4: PAGs have “partially ordered” topological orders, right?

A. Yes, that is correct. PAGs have partial topological order among circle components (Lemma 17 in Appendix B.2.3).

Thank you for the rebuttal. I have also read the other reviews and authors' rebuttals. I maintain my moderately positive judgement and score.

Two minor clarifications for my earlier comments:

1. PAG misspecification: I understand that the focus of paper entirely disregards causal discovery component. My suggestion for considering misspecified PAGs is more on the empirical side. As also mentioned by Reviewer nSMs, one repeated talking point of the paper is “practical motivation”. In this sense, it’s fair to assume that algorithm will almost never have access to the true PAG. Because, to my knowledge, existing causal discovery algorithms all are far from perfect in non-trivial real-data benchmarks. This would be especially true for constrained-based algorithms like FCI, where the exact PAG recovery would require many empirical conditional-independence test to work perfectly. Due to this reason, it’s of great practical interest to study (at least experimentally) how minimal intervention sets (and in turn, empirical regret) are affected given PAG misspecification.
2. Soft interventions: Thank you for the references and discussion. I just want to note that I was referring to a slightly different formulation, as covered in Yan et al. and others. To be clear, in the fully unconstrained soft intervention setting, none of the intervention sets would be redundant, which makes a graphical characterization impossible. Thus, I appreciate the references and the valuable discussion, but I just note that POMPS characterization is not what I was referring to.

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.

A. 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.

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.

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.

It 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.

While 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.

• [1] Hauser, Alain, and Peter Bühlmann., Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs., JMLR (2012)
• [2] Kocaoglu, Murat, Karthikeyan Shanmugam, and Elias Bareinboim., Experimental design for learning causal graphs with latent variables., NeurIPS (2017).
• [3] Greenewald, K., et al., Sample efficient active learning of causal trees., NeurIPS (2019).
• [4] Squires, C., et al., Active structure learning of causal dags via directed clique trees., NeurIPS (2020).
• [5] Choo, D. and Shiragur, K. Adaptivity complexity for causal graph discovery. arXiv preprint (2023).
• [6] Muhammad Qasim Elahi, et al., Adaptive Online Experimental Design for Causal Discovery., ICML(2024b).
• [7] Zhou, Zihan, Muhammad Qasim Elahi, and Murat Kocaoglu., Characterization and Learning of Causal Graphs from Hard Interventions., arXiv preprint (2025).

Alternatively, is it possible to formally show that the removed actions are uninformative?

A. 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.

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?

A. We deeply appreciate your pointed comment, which helps us highlight an important distinction between our work and [Elahi et al., 2024].

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:

(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.

Their 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.

In 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.

In 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.

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.

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?

A. 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)$.

Since 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 \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.

where 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.

Dear Reviewer UG9x

We would like to kindly ask whether our response has addressed your concerns. In particular, we have carefully addressed your comments regarding adaptive causal discovery and have highlighted that our work focuses on pruning the action space in an offline manner, using only a PAG. In addition, we have further clarified the distinction from [Elahi et al., 2024]’s fully online approach through a comparison of the regret bounds.

We sincerely hope that our clarifications were helpful in resolving your concerns and look forward to your response.

Best,

Authors 26106

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

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?

A. 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.

The 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.

• Zheng, Yujia, et al., Causal-learn: Causal discovery in python., JMLR (2024)

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?

A. 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 \binom{9}{i}K^i = (K+1)^9 = 19683$ with binary domains $K=2$.  

In 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.

where 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.