Bayesian Active Learning for Bivariate Causal Discovery
Authors: Yuxuan Wang
Mingzhou Liu
Xinwei Sun
Wei Wang
Yizhou Wang
Venue: ICML 2025 poster (2025)
Keywords: active causal discovery
Bayes factor
sequential decision-making
intervention design
Primary area: general_machine_learning->causality
TL;DR: We propose a Bayes factor-based active causal discovery framework that efficiently determines causal relationships through sequential interventions, demonstrating its effectiveness in bivariate, tree-structured, and embodied environments.

Abstract: Determining the direction of relationships between variables is fundamental for understanding complex systems across scientific domains. While observational data can uncover relationships between variables, it cannot distinguish between cause and effect without experimental interventions. To effectively uncover causality, previous works have proposed intervention strategies that sequentially optimize the intervention values. However, most of these approaches primarily maximized information-theoretic gains that may not effectively measure the reliability of direction determination. In this paper, we formulate the causal direction identification as a hypothesis-testing problem, and propose a Bayes factor-based intervention strategy, which can quantify the evidence strength of one hypothesis (*e.g.*, causal) over the other (*e.g.*, non-causal). To balance the immediate and future gains of testing strength, we propose a sequential intervention objective over intervention values in multiple steps. By analyzing the objective function, we develop a dynamic programming algorithm that reduces the complexity from non-polynomial to polynomial. Experimental results on bivariate systems, tree-structured graphs, and an embodied AI environment demonstrate the effectiveness of our framework in direction determination and its extensibility to both multivariate settings and real-world applications.

Bayesian Active Learning for Bivariate Causal Discovery
Yuxuan Wang' Mingzhou Liu
Xinwei Sun 2
Wei Wang Yizhou Wang*
Abstract
1. Introduction
Determining the direction of causal relationships between pairs of variables is a fundamental challenge in understand- ing complex systems. In fields like genetic research (Pinna et al., 2010; Jia & Zhang, 2022), while we may observe strong associations between genetic variants and pheno- types, determining which variable causally influences the other remains difficult. This directional uncertainty com- plicates our understanding of underlying mechanisms and limits our ability to make reliable predictions about system behavior.
Determining the direction of relationships be- tween variables is fundamental for understand- ing complex systems across scientific domains. While observational data can uncover relation- ships between variables, it cannot distinguish be- tween cause and effect without experimental in- terventions. To effectively uncover causality, pre- vious works have proposed intervention strategies that sequentially optimize the intervention val- ues. However, most of these approaches primarily maximized thfoeriiion-theorrticc gains that may not effectively measure the reliability of direc- tion determination. In this paper, we formulate the causal direction identification as a hypothesis- testing problem, and propose Bayes factor-based intervention strategy, which can quantify the ev- idence strength of one hypothesis (e.g., causal) over the other (e.g., non-causal). To balance the immediate and future gains of testing strength, we propose a sequential intervention objective over intervention values in multiple steps. By analyzing the objective function, we develop a dynamic programming algorithm that reduces the complexity from non-polynomial to polynomial. Experimental results on bivariate systems, tree- structured graphs, and an embodied Al environ- ment demonstrate the effectiveness of our frame- work in direction determination and its extensi- bility to both multivariate settings and real-world applications.
Traditional methods for inferring causal direction rely pri- marily on observational data, representing relationships through directed edges between variable pairs. However, observational data alone often proves insufficient for deter- mining causal direction due the fundamental limitation of Markov equivalence (Pearl, 2009) different causal di- rections can generate identical observational distributions, making them indistinguishable without intervention data.
The limitations of observational studies necessitate experi- mental interventions as the gold standard for determining causal direction (Fisher, 1936). While interventional ex- periments like gene knockouts have become increasingly feasible (Pinna al., 2010), they remain costly and resource- intensive. This limitation has motivated the development of active learning methods for causal direction determina- tion. Traditional approaches typically employ information- theoretic objectives (Tong & Koller, 2001; Murphy, 2001; Agrawal et al., 2019), greedily maximizing the mutual in- formation between interventions and outcomes. However, recent studies (Gong al., 2023) have shown that successful causal direction inference depends not only the informa- tiveness of generated data but also on its evidential complex- ity. This highlights potential misalignment: maximizing information gain alone may not be optimal for bivariate causal discovery, as does not directly optimize for the probability of drawing correct directional conclusions. This is crucial distinction from Bayesian decision-theooette perspective (Trimmer al., 2011), where the objective is typically to select actions that maximize the expected util- ity of the outcome, in our case, the correct identification of causal direction. Simply acquiring information is often a surrogate for, but not identical to, achieving specific
School of Computer Science, Peking University, Beijing, China "Shoool of Data Science, Fudan University, Shanghai, China 'State Key Laboratory of General Artificial Intelligence, BIGAL Bei- jing. China School of Computer Science, Inst. for Artificial Intelligence, State Key Laboratory of General Artificial Intelli- gence, Peking University, Beijing, China. Correspondence to: Xinwei Sun <sunxinwei @ fudan.cdu.cn.>. Wei Wang <wwng- wei@bigai.ai>>.
Proceedings of the 12nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Bayesian Active Learning for Bivariate Causal Discovery
decision-making goal.
ments. These results validate the framework potential for both scaling complex multivariate systems and practical deployment in real-world scenarios.
In this paper, we study sequential intervention strategies to effectively determine causal direction while minimizing experimental costs. Working with a fixed intervention bud- get requires to consider intervention decisions jointly rather than independently (Huan & Marzouk, 2016; Lim et al., 2022), as myopic approaches focusing solely on immediate information gain may lead to suboptimal outcomes once the budget is exhausted. Our framework balances two key objec- tives: maximizing the probability of discovering the correct causal direction early in the sequence, while maintaining the capability to reach definitive conclusions by the end of the budget period. This requires carefully planning each intervention by considering both its immediate evidential value and its impact on future discovery potential. More- over, sequential optimization is computationally expensive, especially when the intervention budget or the action space is large, necessitating efficient algorithmic solutions.
The main contributions of this paper are:
1.
We propose an active intervention framework that lever- ages Bayes factors to quantify the strength of direc- tional evidence, providing an alternative to traditional information-thheorticc approaches.
2.
We formulate a sequential objective that balances short- term and long-term intervention outcomes, and develop a dynamic programming algorithm for efficient opti- mization of intervention selection.
3.
We evaluate our method on bivariate edge orienta- tion tasks, root source localization in tree-structured graphs (Greenewald et al., 2019), and a switch- light reasoning task in embodied Al settings.
To address these challenges, we propose a framework that employs Bayes factors (Kass & Raftery, 1995) to formulate an objective for edge orientation. This approach is inher- ently decision-focused: Bayes factors enable systematic hy- pothesis testing by quantifying the relative evidence support- ing competing directional hypotheses, directly informing the decision about causal direction. This formulation allows us to explicitly optimize for obtaining decisive and correct di- rectional evidence- alliging with established thresholds for when evidence is deemed conclusive- rather than pursuing broader informational criteria that may not be as efficiently targeted towards the specific decision at hand. We develop sequential objective that explicitly balances immediate and future rewards, and use dynamic programming to effi- ciently optimize the intervention selection process, ensuring that each intervention not only provides immediate insights but also maintains flexibility for future direction determi- nations. While the framework is introduced for bivariate cases, it extends to tree-structured graphs (Greenewald et al., 2019), enabling root cause localization through sequential interventions.
2. Related work
Active causal discovery. Traditional causal discovery meth- ods based on observational data face the inherent challenge of the Markov equivalence class (Pearl, 2009), where multi- ple causal structures can induce identical observations. To overcome this constraint, researchers have developed ac- tive intervention techniques. For example, (He & Geng, 2008) proposed to maximize edge recovery per interven- tion; (Shanmugam et al., 2015) selected the optimal inter- vention vertices based on graph coloring. Works that are most relevant to ours are (Murphy, 2001; Tong & Koller, 2001; Masegosa & Moral, 2013; Agrawal et al., 2019; Toth et al., 2022), which selected interventions that maximize the mutual information between the graph and hypothetical objectives samples. However, such information-theorre can be suboptimal from a Bayesian decision-ther theoretic stand- point (Trimmer et al., 2011) when the goal is a specific, correct determination, as they do not always maximize the probability of achieving confident causal conclusions (Gree- newald al., 2019). In contrast purely information- theoretic goals, we employ Bayes factors directly opti- mize for decisive and accurate evidence for specific causal hypothesis, aiming for more efficient discovery for this tar- geted decision.
To demonstrate the effectiveness and generality of our frame- work, we evaluate our methods on bivariate edge orien- tation tasks and further extend to more challenging sce- narios including root source localization in tree-structured graphs (Greenewald et al., 2019) and switch-light reason- ing task in embodied Al environments (Peng et al., 2024). Our experiments on tree-structured graphs demonstrate the potential for handling multivariate settings through sequen- tial interventions, particularly in applications such as biol- ogy (Jia& & Zhang, 2022) and system anomaly detection (Han al., 2023). Additionally, results from the embodied AI ex- periment show that our method can efficiently make correct decisions about causal relationships in physical environ-
Bivariate causal discovery. To identify the causal direction between two variables, previous works leverage asymme- try prior between the cause and the effect for identification through only observational data. Upon this prior, one line of works employed Kolmogorov complexity as a measure of causal direction (Tagasovska et al., 2020; Mitrovic et al., 2018). However, the Kolmogorov complexity is computa- tionally intractable. Another line of work imposed restric- tions on the functional class of causal relationships, such
2

---

Bayesian Active Learning for Bivariate Causal Discovery
as assuming additive noise models (Hoyer al., 2008; von Kügelgen et al., 2019; Blöbaum al., 2018). However, it may fail to generalize to broader family of models. In this paper, we achieve bivariate causal identification through active intervention, without imposing any asymmetry con- straints to the causal relationship.
denote k = (1, k) for any S k E N. For vector E TR we denote æ= as the sub-vector that excludes the k-th element.
Bayes factor. To measure the uncertainty during the inter- vention, we borrow the concept of fayesf (Jeffreys, 1961; Kass & Raftery, 1995) defined as the likelihood ratio BF 01 = P(D Ho) (I H1) over data D, which measures the strength of evidence in favor of the null hypothesis over the alternative. It has been widely used in selecting the true graph among Markov equivalence classes (Madigan et al., 1996; Castelo & Perlman, 2004; Castelletti & Consonni, 2024). In particular, (Castelletti & Consonni, 2024) em- ployed the Bayes factor in active causal discovery: however, it only used it to determine the minimum number of interven- tions, without truly interacting with the environment, In this paper, we provide a framework that incorporates the Bayes factor to actively interact with the environment, enabling more effective identification of the causal relationship.
Sequential experiment design (SED). SED proposes to generate the design points in a sequential manner until the convergence of optimization, in order to overcome the oversampling or undersampling issue met in design of ex- periments (DOE) (Rainforth et al., 2024). For example, (Chakraborty & Chowdhury, 2016) introduced a novel dis- tribution adaptive sequential experimental design for gener- alised analysis of variance; (Foster et al., 2021) reduced the computational cost of traditional Bayesian DOE by learning an amortized deep design network; and (Blau et al., 2022) induced the design policy by solving a Markov decision pro- cess. Particularly, in causal discovery, researchers such as (Tigas et al., 2022: Toth et al., 2022) proposed to apply SED using informatioontthorrel criteria, aiming to maximize information gain with each intervention. However, infor- mation gain maximization can be suboptimal for achiev- ing specific, correct decisions. For decision-focused SED, Bayesian decision theory (Reggiani & Weerts, 2008; Berger, 2013) offers an alternative by optimizing choices for desired outcomes or minimal loss. This aligns with broader needs in tasks like sequential decision- makinng under causal un- certainty (Gonzalez-Soe et al., 2018), where robust causal models guide subsequent actions. In this paper aligning with a decision-theoretic approach, we introduce SED that explicitly gathers information for obtaining decisive and correct evidence regarding causal direction, making the optimization more effective for achieving correct causal conclusions.
4. Methodology
In this section, we present our intervention strategy for learning causal direction. In section 4.1, we first introduce the Bayesian objective over a single-step intervention for interaction. To interact, section 4.2 introduces an iterative algorithm, including prior initialization, optimization, and posterior updating. Section 4.3 extends the framework to multi-step interventions. Finally, section 4.4 applies our approach to multivariate causal discovery.
4.1. Bayesian sample selection
Suppose we have conducted m interventions so far, and the corresponding intervention data are denoted as Dm == ((71,)),... (Ino Fm)) To determine the next interven- tion value x, we propose to maximize the probability of decisive and correct evidence (denoted as IPDc)):
3. Preliminaries
Problem setup & Notations. Consider a bivariate system with X E X and Y E ), our goal is to design an interven- tion strategy to effectively distinguish the causal relation HiI : X + Y from the anti-causal one Hl : X + Y. To achieve this, we assume the availability of n observational data Daies = {a11 ((r1,)))," .i..... (In: }n)} that are i.i.d drawn from the joint distribution Y.. When X Y, the underlying structural causal model (SCM) is:
IP De (T) F(Ho) + PD) P(HH))
(la)
pD Be (T) = PP (BFm) (Dm U [ 7)) > ko|lH,, D.
(1b)
(b) = PP (BFm (Dm U { T)) < H,, D., (1c)
The objective PP is the weighted sum of the probability of determination under the null and alternative hypothesis. The Bayes factor is defined as:
x; = (Nx.), y1 := fr Ny.), Vi,
BF (D... = P(D Hb)
P(Dm m H))
where fx and fy are structural equations, and ) [Ny are independent noise. Throughout, we assume Nx and Ny are d-separated in the graph, i.e., Nx La Ny, which implies the causal sufficiency condition (Spirtes et al., 2001) that is standard in causal discovery. For notational convenience, we denote N the set of natural numbers, and
Therefore, the objective (1a) takes expectation over p(v) under Ho, and p[]] under H1, Since we cannot identify causal directions through only Done we set the prior P(H)) = P(H,) = 1/2. Here, ko, ki are related to the decisive evidence under Ho and H2, respectively.
3

---

Bayesian Active Learning for Bivariate Causal Discovery
Specifically, we say the data provide decisive evidence in favor of Hig at level To if 01 (D) > kn = =(1 =((- with
from observational data.
In this paper, we do not update these priors using interven- tional data. This is because, even when Hi holds, the data may be better fit by |[()|HL)) making it difficult for the Bayes factor to provide sufficient evidence to support HHo. While we can put constraints on 0 to avoid this issue, it is not necessary in the scenario considered in this paper.
P(Ea) since we have (D) > 70-
w = P(H.)
The objective has been similarly used to determine the sam- ple size for interventions (Castelletti & Consonni, 2024), without actually interacting with the environment. In con- trast, we consider the scenario where the environment. During the interaction, our goal is sequen- tially choosing the values of X for intervention to most effectively reduce the uncertainty about the causal direction.
interact with
Optimization. Having identified the interventional distribu- tions, we now focus optimizing FDC over T. To this end, we expand PB and Dc in (1) with the following form:
Connection to information gain. One may consider op- timizing the intervention sample by maximizing the infor- mation gain (Lindley, 1956; Bernardo, 1979) that has been employed in causal discovery (Mian et al., 2023; Toth et al., 2022). We have demonstrated in Appx. A that the infor- mation gain is monotonic transformation of the Bayes factor, meaning it may favor interventions that maximize the Bayes factor given each hypothesis. However, the Bayes factor is more related the causal hypothesis testing con- sidered in our scenario, it is therefore employed guide the intervention process.
DC (z) / (BF U ( F) > ko)
x x Ho)) d Pm)); (4)
Pb (z) / [ (Dm U [ 7) }) < k1
x x Ho) dy P(H, (D..). (5)
This objective integrates over all possible outcomes y af- ter intervention. When X, Y are continuous, we employ Monte-Carke approximation to estimate the objective and apply a smooth approximation of the indication function, which enables gradient-based optimization. When X, Y are discrete, we can directly evaluate the objective by enumer- ating all possible intervention values to find the optimum. Please refer Appendix B.3 for details.
4.2. Optimization and posterior update
We introduce how to optimize and update the causal belief at each iteration. Our procedure involves estimating the initial intervention distribution for calculating the Bayes factor, optimization of zz and posterior update.
Posterior update. Having obtained the optimal x, we get y through interaction. We can append the interventional data D m++1+ = Dm U (3, V) With these data, we update our causal belief, a.k.a, posterior of each hypothesis as follows:
Estimating the intervention distribution. To compute the Bayes factor in (Ia), we need to compute plyl do (z), H under each hypothesis, which equals to:
plyldo(z), Ho)) / ply (0) [HH)ddo
P (mm+1) p( 7) (H,) PH (D.)
Eje(o.)) (( HH, (( (Dm)
p(yldo(z),HH) / p(ul,; ( [HH,, )d0
((,) (H (Dm) E P p(T) Tr Hi, P )m))
(3)
since the edge Y + X is broken when we intervene a, we have p = p(y) under Hg. Under Hi, we have p(y))o(x)} = p(y]2)) For each hypothesis, we take the expectation over p(0, [TH,). Following (Kass & Raftery, 1995), we specify p(O, (HI,) as the data-dependent prior cen- tered around the MLE estimate. when X, Y are continuous, we set it Gaussian distribution N0, S.). where 0 is the MLE estimate, and E is the inverse Hessian of the negative liceeioodooodd When X, Y are categorical, we use Beta dis- tribution to specify each level's parameter, where the param- eters in Beta distribution is obtained as the MLE estimate. Suppose X, Y respectively have xx and by levels, the param- eters we specify include 0o,: := IP = i) for i < Lx under Hl. and 01.j. == P(Y = =| = i) for < ly and i S 1x under H2. For each parameter do,s == Beta(ap. Bo.s) (the prior of 01,j, is similar), where 0g fo, are MLE estimates
where p(ū)7, H2) are given by (2-3) for j = 0, 1.
We summarize the whole procedure in Alg. with k = in lines 6-7.
4.3. Multi-step optimization
While the single-step intervention design presented in sec- tion 4.2 provides foundation, its greedy and myopic nature may lead to suboptimal solutions (Rainforth et al., 2024). In this section, propose multi-step version that opti- mizes a sequence of interventions by considering cumula- tive evidence across multiple steps, along with an efficient algorithm for solving the resulting optimization problem.
Multi-step objective. Following (González et al., 2016; Jiang et al., 2020), we optimize the next step by also looking
4

---

Complexity Analysis. For a given remaining intervention budget K, our algorithm determines the optimal interven- that maximizes the cumulative Bayesian Active Learning for Bivariate Causal Discovery
Algorithm 1 Bayesian active intervention
This property implies that (T. depends only on the count of each value from X' that appears in the sequence Tik- Therefore, we can rewrite J ( Tx) as J J(nx) and PDc((1:*) as (Dc)) where T4 E [ for any k S K represents the count vector. The i-th element of ny records how many times the value ã, appears in the sequence TiRk- Upon this property, the following proposition ensures us to optimize J (TI:K) via dynamic programming.
1: Input: Observational data Pobs. total budget B
2: Output: Pine. posterior P(H,) for j = 0, 1.
3: Initialize iitt. 0, P(H)) = ((H 2-
4: Specify 1)) from Dobs for j {0, 13.
5: while [Dint] < B do
6: Set remaining budget K = B Du
7: Obtain {2r, k by maximizing Σ - T
8: Perform do =I) and observe y.
Proposition 4.2. Denote FiKK as the optimal value of J(L Given -i for each k S K, the optimal value of b only depends on n
9: Update Dmm f Dint U {<11 v)}.
10: Update posterior P(H Dint).
11: end while
The proof is left to Appx. B.2. This property ensures us to solve x² in a recursive manner:
ahead its next K- steps (for simplicity, we omit Dm)):
J& == max (PDc(nL) + + - -ez))}
PDC (T1:K) = P (BF (1 (TI, V1 U Dia)) > ko (H P(Ho)
z == arg max (PDD + + (n Exr }
+ (BF 01 (( (1, U Daa) < 1 [ I((HH) )
(8)
(6)
where Diur = {32, ...y ] represents data of the next K- steps, with 2, y;). To determine the optimal x for intervention, we need to optimize over T.K. Here, K is a trade-off between the short-term and long-term benefits. Although a large value of K would maximize certainty in the long run, it may affect the effectivvness in the immediate steps. To balance the short-term and long-term benefits, we propose to optimize the following objective:
for each k S K, where er, E {0, 1)x represents the one-hot encoded vector, where the element corresponding to T& is 1, and all other elements are O. In this recursive formulation, the optimal solution to the original problem is composed of the optimal solution to each subproblem.
tion sequence (2² , ..., 2*k)
reward J( Since both x² and J are determined by count vectors n, we first enumerate all possible count vec- tors and compute their corresponding PD values (Phase 1), then recursively compute the optimal cumulative rewards Jz(n)) for each 1 (Phase 2). Finally, we obtain xx through backward optimization (Phase 3). The complexity analysis for each phase proceeds as follows.
J (Z Tx) PD((()))
where 0 < < 1 denotes the discount factor. Such a de- sign is common in sequential experimental design (Foster et al., 2021) and reinforcement learning (Huan & Marzouk, 2016) that balances immediate and future rewards. How- ever, our work differs in its optimization target: instead of maximizing information gain expected utility, we directly optimize the probability of reaching decisive causal conclu- sions. This arises from the practical goal that determines causal relationships within limited experimental budgets.
Phase 1: State Precomputation (lines 4-6). This phase enumerates all feasible count vectors n = -(n1, m)z) where fh. E N denotes the number of applications for in- tervention x E X, constrained by Evex The S K. This represents all possible ways to distribute K interventions across |X| different intervention types, with the total num- ber of combinations being ( (K+ = (( Each state's 's PD value is precomputed and stored for subsequent optimization.
Optimization via dynamic programming. We consider both categorical and continuous cases for optimizing (7).
When X is continuous, we can follow Sec. 4.2 to employ Monte Carlo approximation for the smooth approximation of the objective. When X is discrete, evaluating (7) requires considering |x possible sequences, which is computa- tionally infeasible when k is large. To accelerate, we use dynamic programming, which builds upon two key proper- ties that allow for efficient optimization, as presented below.
Phase 2: Recursive State Optimization (lines 8-12). For each step k = 1,..., K, the algorithm computes opti- mal cumulative rewards J4 (n) through backward induc- tion: i) State Generation: Enumerate all count vectors with Σx n2 = k, requiring -(1)=(11) states. ii) State Update: Evaluate all possible interventions x E X using the recursive relation (Equation (8)) with O(22') opera- tions per state. Aggregating across all budget levels yields: IK 0(12) - = 0(xx) -
Proposition 4.1. Suppose X has Ix categories, T1.... Tix- For any k, FDC(( is symmetric with respect to its argu- ments (I1, "* (kk)
5

---

Bayesian Active Learning for Bivariate Causal Discovery
Phase 3: Optimal Path Reconstruction (lines 14-18). Starting from the terminal state nj. the optimal intervention sequence is reconstructed by iteratively subtracting unit vec-
selected intervention target V V, our goal is to determine which neighboring node is its parent, thereby identifying edge directions in the causal tree. Let (VV)) denote the neighbors of node V in the tree skeleton. We design optimal intervention values Ty by maximizing (1) that is associated with multiple hypothesis:
tors: n²" + n² ext: k = ....., 1 This backtracking process requires O operations, independent of |
Total Complexity. Combining all phases yields: O(K O K x + O(K) O(1x* K) which is a poly- nomial complexity for K. This represents an exponential improvement over the naive O(Ix) k) brute-force approach.
Σ
FDc(XV:U),
(EN(V)
where PDc(Ty; U) denotes the objective whose goal is to discriminate IH, V U. from its null Ho V + U.
Algorithm 2 Dynamic Programming for Optimal Interven-
tion Design
1: Input: Remaining budget K, intervention space A'
5. Experiments
2: Output: Optimal intervention sequence (#I .... xxx)
3: Phase 1: Precompute PC values
In this section, we evaluate our method on bivariate causal discovery and tree-structure causal graph learning (Gree- newald et al., 2019). We also consider switch-light reason- ing task demonstrate the usage of our method in embodied artificial intelligence (Embodied AI).
4: for all count vectors n with Σvex n2 S K do
5: Store (nc(n) { {Compute via causal model]
6: end for
7: Phase 2: Forward value iteration
8: for each budget & = 1 to K do
Compared baselines. We compare our method with the following baselines: i) Rand that randomly selects the inter- vention value; ii) InfoGain (Tigas et al., 2022; Toth et al., 2022) that optimizes the information gain to choose the best intervention value. To accommodate this method to our hypothesis testing setting, we compute the Bayes factor after optimization to inform the decision; and iii) Multi- step InfoGain that enhances (Tigas et al., 2022; Toth et al., 2022) by incorporating the multi-step optimization scheme described in Sec. 4.3.
9: for all feasible n2 with En f2y = k do
10: Compute J& ( via Equation (8)
11: end for
12: end for
13: Phase 3: Backward path retrieval
14: Initialize n²" +- arg max,," Jx (n)
15: for k- k= K down to do
16: Find zt that maximized Equation (8) for n²
17: Update n + n²" - -ez
18: end for
Evaluation metrics. For bivariate causal discovery, we report the rate of type I error and recall, which are the probabilities of incorrectly rejecting the null hypothesis when it is true, and correctly rejecting it when it is false, respectively. We also report the probability of decisive and correct evidence PDc defined in (1). For tree-structure causal discovery and the switch-light reasoning task, we report the total number of interventions required to recover the causal graph.
4.4. Application to multivariate causal discovery
Our approach can be naturally applied causal discovery over multiple variables, when combined with off- the-s approaches in identifying the target variable for intervention (He& & Geng, 2008; Hauser & Bühlmann, 2014). For such target variable, it may be associated with multiple causal directions to determine. We can therefore optimize the value by combining the objective of all directions of interest. Besides, since we do not update p(y [f) once it is fixed, we require it to be identifiable. To illustrate, we provide examples over three variables in Appx. C.
Implementation details. We set the evidence levels in (1b) and (Ic) to ko 10 and 4 1/10, respectively. Results for alternative parameter settings, including kn = 300 k 1 /30 and Ko = 100, k1 = 1/100, are presented in D.3. The selection of these parameter values is based on the classifi- cation of Bayes factor detailed in Appendix D. following (Kass & Raftery, 1995; Schönbrodt & Wagenmakers, 2018). For Alg. 1, we set the total budge to number of observational samples to |Dobel 1000. For the optimization over discrete variables, we consider Alg. 2. For the optimization over continuous variables, we employ the Adam optimizer with a learning rate of 0.1 and a total iterations of 4000 steps. We decay the learning rate to 0.001 after the first 200 steps. The switch-light reasoning task
Causal trees. The type of causal graph that naturally sat- isfies this identifiable condition is causal trees, which can be widely applied in various domains, such as microservice systems diagnostics (Xin et al., 2023; Pham al., 2024; Fariha et al., 2020), general system anomaly detection (Han et al., 2023; Palanki, 2024).
100 and the
Specifically, given a tree skeleton with vertex set V and edge set ε, existing methods like (Greenewald et al., 2019) provide strategies for selecting intervention targets. For each
6

---

Bayesian Active Learning for Bivariate Causal Discovery
Setting Weak Causation
0.84
Fand
Inioiain
3.6
04
Maltiotep infoGae
Ours
3.5
96
H
0.82
03
01
0.83
20
000
30
Inservntiooal sampllex
Intevantional
Inanvetienal eimples
Intrvantional
Setting Strong Causation
0.00
0.01
04
0.4
4)
100
21
20
100
29
300
samples
Intervent samples
(3)
(b)
(d)
Figure 1. Results on bivariate causal discovery. The two rows presents results two different settings. Columns (a)-(d) report the type I rate, recall, PDc under Ho, and Po under H1, respectively, in relation the number of intervention samples.
Setting Weak Causation
Setting 2: Strong Causation
3.0
The wijn Matkery
0US
E/0
0.22
L1.4
6/0
0.0L
0.2
0/
0.00
0.
5.00
Intervendinal samples
Interventional samplca
Interverticnal surpples
Figure 2. Ablation study on the multi-step optimization algorithm. The red and blue lines denote our method with and without multi-step optimization, respectively. The first columns results from Setting-1, 1, and the last two columns results from Setting
implemented on the TongSim (Peng et al., 2024) engine running on a server with NVIDIA 2080-Ti GPUs.
we repeat the generation process 20 times. For each time, generate 100 replications under Hy and Hi, respectively, to record the type I error rate and recall.
5.1. Bivariate causal discovery
Comparsion with baselines. We report the performance of our method and the baseline approaches in Fig. 1. As shown, in Setting-1: Weak Causation, our method outperforms the baselines in recall, and achieving competitve type error rate, indicating effective causal discovery with controlled false positives; wheras in Setting-2: Strong Causation, the performance of our method and the baselines is similar. To interpret these results, the advantage of our method in Setting-1 1 largely stems from the use of the PD as the optimization objective, which facilitates a more efficient collection decisive and correct evidence (see columns (c) and (d)). leading to a better intervention strategy. On the other hand, for Setting-2, the causal relationship is strong and therefore can be identified without the need for refined interventions. Consequently, information gain-based meth-
Data generation. We consider binary variables!, where the data is generated from P(Y) Bern(0.5) (resp. P(X)) and P(X|Y 0) Bern(po). P(X = 1) Bern(p1) (resp. X)) under the null hypothesis HHo (resp. the alternative hypothesis H. Here, the quantity iPo P1l= (V = 0), PPX|Y = 1)) measures the strength of the causal influence. A small value of Ipo P1l indicates weak causal interaction, whereas a large one means the causal influence is strong. Accordingly, we consider different data settings: Setting-l: Weak Causation with Po PI| E 10 0.2) and Setting-2: Strong Causation with PP PIl E [0.8, 0.9). To remove the effect of randomness,
Please refer to Appx. D.4 for results continuous variables.

---

Bayesian Active Learning for Bivariate Causal Discovery
Average Number of Interventions
180
Table Results under different observational sample sizes |obs
160
Rand
InfoGain
[Paual
Setting
Setting 2
140
Multi-step InfoGain
800
Type
0.025 015
Emor
0.6071.0dt
Recall
Type Error
0.0001.00
1.0001.00
Recall
120
Ours
1000
0.03851.02
0.627
0.001
1.0001.00
100
1200
0.0395
0.6231.059
0.0001.00
1.0001.00
80
60
ods (Tigas et al., 2022; Toth et al., 2022) can also achieve results similar to ours.
0.05
0.1
0.15
0.2
0.24
Ablative study. We conduct an ablation study on the multi-step optimization algorithm introduced in Sec. 4.3 and present the results in Fig. 2. As we can sec, the se- quential optimization algorithm significantly enhances the performance of our method, particularly in Setting-1 where the causal relationship is more challenging to identify. This result demonstrates that our sequential optimization scheme can effectively balance the short-term and long-tem term bene- fits, leading the optimization of our PDC objective towards the optimal solution.
Figure 3. Results on tree causal discovery. The Y-axis is the aver- age number of interventions conducted when using (Greenewald et al., 2019) and our method to recover the whole tree. The X-axis represents different choices of the parameter 8. Please refer to Appx. D.5 for variance analysis.
5.3. Causal reasoning in embodied AI
In this section, we consider switch-light reasoning task to illustrate the usage of our method in causal Embodied AI.
Influence of the observational sample sizes |Dobs In Tab. 1, report the type I error rate and recall under differ- ent observation sample sizes [Doba| = {800, 1000, 1200). As shown, our method works consistently well under dif- ferent observational data settings. This result demonstrates that our method is robust to changes in hyperparameters, consistently achieving reliable causal identification.
Experimental setup. We develop a simulation environ- ment based on TongSim (Peng et al., 2024), which includes an embodied agent, two switches (S₁ and S2), and two lights (L1 and L2). The agent tasked to identify which switch controls which light through active intervention. The data of switch activation and lighting status is generated using Bernouli distributions P[L[[S] 0) ~ (ern(po) and P(L: = 1) Bern(pi) for i, = 1, We select the pa- rameter IPo - P1 = TV(P(L,|S) = (L,),, = 1)) from the set {(0.2, 0.3), (0.4, 0.5). (0.6, 0.7), (0.8, 0.9) for various strength of causal influence. To further increase the complexity, we introduce latent confounder between the switch activations, making the results unidentifiable based solely on observational data. To remove the effect of randomness, we repeat the generation process 100 times. The environment and its underlying causal structures are illustrated in Fig. 4.
5.2. Tree-structured causal graph learning
Data generation. We consider tree graphs with 30 ver- tices. To generate the data, we first randomly sample 200 trees from the space of all possible trees. Next, we se- lect root vertex and generate its value by sampling from (orn(..5). For the remaining vertices, we sample accord- ing to the following distributions: P(X,/PA, Bern(c), (,, = 1) ~ Bern(1 - <), where PA, rep- resents the parent of X; in the tree. For each vertex, we randomly select e from the interval [6, 0.5 8). We explore five different choices of (0.05, 0.1, 0. 0.15,,15551 0.2, 0.25).
0) ~
Result analysis. Tab. 2 shows the average number of inter- ventions needed recover the underlying causal structures. As we can see, our method demonstrates competitive per- formance across various settings of IPu - Pzl. Notably, the advantage is particularly pronounced when IPo -P1l is small and the causal influence is weak, which aligns with observa- tions from the bivariate causal discovery experiment. These results underscore the applicability of our method causal reasoning tasks in Embodied AI.
Results analysis. In Fig. 3, we show the averaged number of interventions required when applying (Greenewald et al., 2019) and our method to recover the tree graph. As we can see, our method demonstrates consistent advantage over baselines under all settings of 8. Particularly, the most challenging scenario with 0.05, our method recover the graph with averagely 140 interventions, which is about 10% fewer than the information- -theorettt methods proposed by (Tigas et al., 2022; Toth et al., 2022). These results highlight the effectiveness of our Bayes factor objective in optimizing reliable causal discovery, as well as the efficacy of our sequential optimization algorithm in identifying the optimal intervention values.
6. Conclusions and limitations
In this paper, we propose a novel Bayesian framework for active causal discovery. We formulated an objective based on Bayes factors and the probability of obtaining decisive
8

---

Bayesian Active Learning for Bivariate Causal Discovery
Ho :
S1
S2
References
L2
L1
Agrawal, R., Squires, C., Yang, K., Shanmugam, K., and Uhler, C. Abed-strategy: Budgeted experimental de- sign for targeted causal structure discovery. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3400-3409. PMLR, 2019.
H1 :
S1
S2
L1
L2
Figure 4. The simulation environment for the switch-light reason- ing task. The agent is required to identify which swich (S; and 52) controls which light (L, and L2) though active exploration. The causal graphs under He and Hi shown the right.
Berger, J. O. Statistical decision theory and Bayesian anal- ysis. Springer Science & Business Media, 2013.
Bernardo, M. Expected information expected utility. the Annals of Statistics, pp. 686-690, 1979.
Blau, T., Bonilla, E. V., Chades, I., and Dezfouli, Op- timizing sequential experimental design with deep re- inforcement learning. In International conference machine learning, pp. 2107-2128. PMLR, 2022.
Table Average number of interventions required the switch- light reasoning task. Best results are boldfaced.
Methods
Range of Ino
Pi
(0.2,033
0..4.0.5)
(0.6,0.7)
(0.8, 0.9)
Rand
46.151145
14.77a27
7.44
4.00gg.7
Blöbaum, P., Janzing, D., Washio, T., Shimizu, S., and
InfoGain
33.511139
9.97
5.05
2.60
Multi-sep InfoCiin
32.52
9.66
4.99
2.63
Schölkopf, B. Cause-effect inference by comparing re- gression errors. In International Conference Artificial Intelligence and Statistics, pp. 900-909. PMLR, 2018.
Ours
32.11,132
9.88
4.89
2.61.0.7
Castelletti, F. and Consonni, G. Bayesian sample size deter- mination for causal discovery. Statistical Science, 39(2):
and correct evidence for causal relationships under interven- tions. To optimize this objective, present efficient sequential optimization algorithm grounded in dynamic pro- gramming. The effectiveness of our method is demonstrated through superior performance in bivariate causal discovery and tree-structured causal graph learning tasks.
305-321, 2024.
Castelo, R. and Perlman, M. D. Learning essential graph markov models from data. In Advances in Bayesian networks, pp. 255-269, Springer, 2004.
Chakraborty, and Chowdhury, R. Sequential experimen- tal design based generalised anova. Journal of Computa- tional Physics, 317:15-32 32, 2016.
Limitation and Future works. While our method can ef- fectively identify causal relationships in the bivariate case, extending it to multivariate graphs be non-trivial, since we currently rely on the identifiability of p(vl do(x)} for optimization. To resolve this problem, we will develop algorithms that simultaneously estimate the interventional distribution and compute the Bayes factors from the inter- ventional samples for dedicated solution. Moreover, we also interested in applying method to various causal reasoning and intuitive physics tasks in Embodied AI.
Fariha, A., Nath, S., and Meliou, A. Causality- guided adap- tive interventional debugging. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 431-446, 2020.
Fisher, A. Design of experiments. British Medical Journal, 1(3923):554, 1936.
Acknowledgements
Foster, A., Ivanova, D. R., Malik, I., and Rainforth, T. Deep adaptive design: Amortizing sequential bayesian experi- mental design. In International conference on machine learning, pp. 3384-3395. PMLR, 2021.
This work was supported by the National Science and Technology Major Project (0222D0114904) and NSFC- 6247070125.
Gong, T., Gerstenberg, T., Mayrhofer, R., and Bramley, Active causal structure learning in continuous time. Cognitive Psychology, 140:101542, 2023.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must specifically highlighted here.
González, J., Osborne, M., and Lawrence, N. Glasses: Re- lieving the myopia of bayesian optimisation. In Artificial Intelligence and Statistics, pp. 790-799. PMLR, 2016.

---

Bayesian Active Learning for Bivariate Causal Discovery
Gonzalez-Soto, M., Sucar, L. E., and Escalante, H. Play- ing against nature: causal discovery for decision mak- ing under uncertainty. arXiv preprint arXiv:1807.01260 2018.
Lindley, D. V. On a measure of the information provided by experiment. The Annals of Mathematical Statistics, 27 (4):986-1005, 1956.
Loshchilov, I. and Hutter, Sgdr: Stochastic gra- dient descent with warm restarts. arXiv preprint arXiv:1608.0340 2016.
Greenewald, K., Katz, D., Shanmugam, K., Magliacane, S., Kocaoglu, M., Boix Adsera, E., and Bresler, G. Sample efficient active learning of causal trees. Advances in Neural Information Processing Systems, 32, 2019.
Madigan, D., Andersson, S. A., Perlman, M. D., and Volin- sky, C. T. Bayesian model averaging and model selection for markov equivalence classes acyclic digraphs. Com- munications Statistics-Theory and Methods, 25(11): 2493-2519, 1996.
Han, X., Zhang, L.., Wu, Y., and Yuan, S. On root cause localization and anomaly mitigation through causal in- ference. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 699-708, 2023.
Masegosa, A. R. and Moral, S. An interactive approach for bayesian network learning using domain/expert knowl- edge. International Journal of Approximate Reasoning, 54(8):116--111 2013.
Hauser, A. and Bühlmann, P. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4): 926-99 919.9999.92 2014.
Mian, O., Kamp, M., and Vreeken, J. Information-theored causal discovery and intervention detection over multiple environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 9171-9179, 2023.
He, Y.-B. and Geng, Z. Active learning of causal networks with intervention experiments and optimal designs. Jour- nal of Machine Learning Research, (500)22553-2 2008.
Mitrovic, J., Sejdinovic, D., and Teh, Y. W. Causal infer- ence via kernel deviance measures. Advances in neural information processing systems, 31, 2018.
Hoyer, P., Janzing, D., Mooij, M., Peters, J., and Schölkopf, B. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21, 2008.
Murphy, K. Active learning of causal bayes net structure.
Technical report, technical report, UC Berkeley, 2001.
Palanki, V. Leveraging causal inference techniques for
Huan, X. and Marzouk, Y. M. Sequential bayesian optimal experimental design via approximate dynamic program- ming. arXiv preprint arXiv: 160. (06.6004..3200 2016.
robust root cause identification in complex systems. J Artif Intell Mach Learn & Data Sci 2024, 2(3): 1200-1233,, 2024.
Jeffrees, H. Theory of Probability (3rd Edition). Oxford, University Press, 1961.
Pearl, J. Causality, Cambridge university press, 2009.
Peng, Y., Han, J., Zhang, Z., Fan, L.,, Liu, T., Qi, S., Feng, X., Ma, Y., Wang, Y., and Zhu, S.-C. The tong test: Evaluating artificial general intelligence through dynamic embodied physical and social interactions. Engineering, 34:12-22, 2024.
Jia, Z. and Zhang, X. Accurate determination of causalities in gene regulatory networks by dissecting downstream target genes. Frontiers in Genetics, 13:923339, 2022.
Jiang, S., Chai, H., Gonzalez, J., and Garnett, R. Binoculars for efficient, nonmyopic sequential experimental design. In International Conference on Machine Learning, pp. 4794 4803. PMLR, 2020.
Pham, L., Ha, H., and Zhang, H. Root cause analysis for microservice system based on causal inference: How far are we? In Proceedings of the 39th IEEE/ACM Interna- tional Conference on Automated Software Engineering, pp. 706-715, 2024.
Kass, E. and Raftery, A. E. Bayes factors. Journal of the american statistical association, 90(430):773-795, 1995.
Pinna, A., Soranzo, N., and De La Fuente, A. From knock- outs to networks: establishing direct cause-effect relation- ships through graph analysis. PloS one, 1219): 2010.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Lim, V., Novoseller, E., Ichnowski, J., Huang, H., and Goldberg, K. Policy-based bayesian experimental design for non non-differenntable implicit models. arXiv preprint arXiv:2203. 04272, 2022.
Rainforth, T., Foster, A., Ivanova, D. R., and Bickford Smith, F. Modern bayesian experimental design. Statistical Science, 39(1):100-114 2024.
10

---

Bayesian Active Learning for Bivariate Causal Discovery
Reggiani, P. and Weerts, A. A bayesian approach to decision- making under uncertainty: An application to real-time forecasting in the river rhine. Journal of Hydrology, 356 (1-2):56-68) 69, 2008.
Schönbrodt, D. and Wagenmakers, E. Bayes factor de- sign analysis: Planning for compelling evidence. Psy- chon. B. Rev., 25(1):128-142) 2017. doi: doi:10.3758.
s13423-017-1230-3
Schönbrodt, and Wagenmakers, E.-J. Bayes factor design analysis: Planning for compelling evidence. Psy- chonomic bulletin & review, 25(L):128-14) 2018.
Shanmugam, K., Kocaoglu, M., Dimakis, A. G., and Vish- wanath, S. Learning causal graphs with small interven- tions. Advances in Neural Information Processing Sys- tems, 28, 2015.
Spirtes, P., Glymour, C., and Scheines, Causation, pre- diction, and search. MIT press, 2001.
Tagasovska, N.. Chavez- Demoolin, V., and Vatter, T. Dis- tinguishing cause from effect using quantiles: Bivariate quantile causal discovery. International Conference on Machine Learning, pp. 9311 1311-9323. PMLR, 2020.
Tigas, P., Annadani, Y., Jesson, A., Schölkopf, B., Gal, Y., and Bauer, S. Interventions, where and how? experimen- tal design for causal models at scale. Advances in Neural Information Processing Systems, 35:24130-2411 23143443,, 2022.
Tong, S. and Koller, D. Active learning for structure in bayesian networks. In International joint conference on artificial intelligence, volume 17, pp. 863-869. Citeseer, 2001.
Toth, C., Lorch, L.., Knoll, C., Krause, A., Pernkopf, F., Peharz, R., and Von Kügelgen, J. Active bayesian causal inference. Advances in Neural Information Processing Systems, 35:16261-16274 2022.
Trimmer, C., Houston, A. I., Marshall, A., Mendl, M. T., Paul, E. S., and McNamara, J. M. Decision-making under uncertainty: biases and bayesians. Animal cognition, 14: 465-476, 2011.
von Kügelgen, J., Rubenstein, P. K., Schölkopf, B., and Weller, A. Optimal experimental design via bayesian optimization: active causal structure learning for gaus- sian process networks. arXiv preprint arXiv:1910.0396.. 2019.
Xin, R., Chen, P., and Zhao, Z. Causalrea: Causal inference based precise fine-grained root cause localization for mi- croservice applications. Journal of Systems and Software, 203:111724, 2023.

---

Bayesian Active Learning for Bivariate Causal Discovery
Appendix
The connection between Pc and information gain
13
Multi-step optimization
13
B.1 Proof of symmetry property
13
B.2 Proof of count-dependent only property
14
B.3 Estimation and optimization for continuous interventions
15
B.4
Estimation of Interventional Distributions
15
B.5 Parameter Prior and Likelihood Computation
15
B.6 Smooth Approximation for Gradient-based Optimization
15
Application to multivariate causal discovery
16
D Experiments
17
D.1 Bayes Factor classification
17
D.2 Additional results on the discrete setting with ko = 10.
17
D.3 Performance evaluation with different evidence thresholds
19
D.4 Experiments on Continuous Settings
19
D.5 Variance Analysis for Tree Structure Experiments
20
12

---

Bayesian Active Learning for Bivariate Causal Discovery
A. The connection between PDC and information gain
Here we provide a detailed analysis of the relationship between our objective functiin and the information gain criterion. The mutual information between the hypothesis H and new observation given intervention X z can be expressed as:
T( H x= x) Σ / p do = x)) log
P H h do(X = =x)) dy
ply do x). h}
(9)
Σ /
f plu do = x), H h) log
pVu. H h do = x²) dy ply do(X =. H h}
For the term plu, HI = h do(X = x)t/pfy/ do(X = 2), H = h} when h = Hu, we can derive:
ply. Ho, do(X x²}} plu | do(X = x), Hot
ply do(X x²), Ho.
En ply do(X = x), ht' ho(h'
plu do X = x). Ho}
(10)
plu do(X = x), HHo + ply do(X = x²), HI (H{
BF (f(2) Vnew))
BF (((x, Vnew ))) (Ho) + H
Similarly, when h = lHl1, we can obtain:
ply, HI do(( x)} ply do(X = x.), HI BF (((x, Vnow Ho) + ((HH)
(11)
Therefore:
I(Y: X = x) = / pl (HHll log
BFoi oz (f (x, Fnew))
P(Y = do(X = x), Jy
BF (1x, Unew ( Hog + p H
(12)
pl p(Hi) log BF (((x, Mhew)) Mnew))))(WHo)) + p(HH) p(y P
y do z) H1 Hiydy
Comparing the summands in equations 5 and above, we can observe that both are monotonic functions of BF (f Inew }) When oF (1(2, )new)]) increases, both the indicator function in P' and the logarithm term in information gain increase, indicating these objectives are aligned preferring interventions that yield high Bayes factors when Hi true, and low Bayes factors when HI, is true.
B. Multi-step optimization
B.1. Proof of symmetry property
Here provide detailed proof that PDC(#11) is symmetric in its arguments (æ1,-.. zxk for any fixed k. This symmetry property is crucial for reducing the computational complexity of our optimization problem.
Proposition B.1. For any fixed k, PDD((11)) is symmetric in its arguments (#1,"-", (Zk).
Proof. By definition of PDC (Equation (6)), we have:
PDc(#1:1) = P(FF ((z), vi U D > Ko Ho)P(HL) + P(BF (( v1 D(m) < kn HH(H)))
= Σ
Ply do(x).)) Ho (H, (BF, o1 ( V. Dia) > knp
(13)
Σ
P(yn do(#1.)) H. PHH, I (BF on ((11,)) vi Dim) < kg)
13

---

Bayesian Active Learning for Bivariate Causal Discovery
For each hypothesis Hly, the likelihood term can be expressed as:
A
/ 11 P(u 0, |d
P(yix (o(()1s)) HI,}
(14)
The Bayes factor is the ratio of these likelihoods:
S I P(us do(x;), 0, Ho)P(O Ho
oF U. Dim)
(15)
f S P(us do(x;), 0, H1 PP )d0
Both the likelihood terms and the Bayes factor are invariant under any permutation of the indices of (y1, yk) due to the product form inside the integrals. By Fubini's theorem, we can interchange the order of summation over yısk in the original expression. Since both the likelihoods and the decision criteria (through the Bayes factor) are invariant under permutations of corresponding (ar,. ys) pairs, ( must be symmetric (#1,** ,Tk).
This symmetry property leads to significant computational savings in the main optimization problem. Rather than evaluating all possible ordered sequences of interventions, we only need to consider unique combinations of intervention values, reducing the complexity from (()x to O(k
B.2. Proof of count-dependent only property
To develop an efficient optimization algorithm, we first prove that our k-step optimization decisions depend only on the aggregate statistics of previous interventions. This property enables to solve the problem recursively using dynamic programming.
Proposition B.2. For the sequential optimization problem in Equation 7, the optimal policy कं x - X at step depends only on the aggregate statistics of previous interventions:
T (f1st-1) = St
Σ
where Cz2 is the unit vector corresponding to intervention Tú and Se. M + X is some function.
Proof. Let n, E N denote the vector of counts for each intervention value in X' up step t, where the i-th element represents how many times the i-th intervention value has been used in the first steps. Our objective function is to maximize Σt PDC (#1:)). By the symmetry property (Proposition 4.1), PD (I1:;) PDC (n,), meaning the value at each step depends only on the count vector rather than the specific sequence of interventions.
We can then transform the optimization problem as follows:
K
A PDC (I1=)
max
K
*PDC (ng)
max
valid Di Dx
k=1
K-1
max valid ng
max valid "I TTK
> PDC (nx)
KDDC (ną)
(16)
Here, a count vector is valid if there exists an intervention sequence 2i:k that generates it, i.e., if there exists some Ze such that n ezc- This decomposition reveals that at each step we need to: (i) track the current count vector nę (ii) choose the next intervention 23 that generates a valid next count vector, and (iii) solve the subproblem for the previous
- 1 steps. This structure suggests maintaining value functions J4 (mx) and policies T. (nx) for each possible count vector each step, which can be computed recursively through dynamic programming.
14

---

Bayesian Active Learning for Bivariate Causal Discovery
B.3. Estimation and optimization for continuous interventions
In the continuous intervention setting, estimating interventional distributions and computing likelihoods requires careful consideration of the continuous parameter space. Here detail our approach for implementation.
B.4. Estimation of Interventional Distributions
For continuous interventions, we first estimate the parameters of the interventional distributions under each hypothesis using maximum likelihood estimation:
Under Ho where X has no causal effect on Y, the interventional distribution reduces to the marginal distribution:
P(y do X = x), 0, Ho) ) = P(y 0)
(17)
Under HH where X causes Y, the interventional distribution equals the conditional distribution:
Ply do(X 0, }1 (y x,
(18)
The maximum likelihood estimates for each hypothesis are obtained by:
Nas
0u = arg max
log P(u: xs, 0, H]
(19)
8
B.5. Parameter Prior and Likelihood Computation
Following (Kass & Raftery, 1995), we employ data-dependent parameter prior centered around the MLE estimate, For each hypothesis H., approximate the parameter posterior Gaussian distribution:
P(0) Dm. H} (6,
(20)
where E is the inverse Hessian of the negative log-like log-likelihood at Å.
The marginal likelihood is then approximated using Laplace's method:
Pl do(X HH (2 22x) do(X = 1113)) H)
(21)
In practice, computing the Hessian for all data points in each likelihood evaluation can be computationally intensive. An alternative is to use an empirical Bayes approach with point mass prior (É - 0), which reduces the computation to likelihood ratio test while maintaining computational efficiency.
B.6. Smooth Approximation for Gradient-based Optimization
To enable gradient-based optimization in continuous intervention space, we need to address the non-differentiabiliy of the indicator functions in PDD. We introduce a smooth approximation using the exponential function:
Hz(x)= exp(-</13)
if <
(22)
if 2 0
This can be expressed compactly using the ReLU function:
Ha(x) = (xp(-ReLU(-z)/B)
(23)
Using this approximation, we can first rewrite the single-step PDC differentiable form:
PDc(Dm, x) R Eyning (exp(- - BFa (Pm U (((,)))))))) P(Hllo Dm)
(24)
+ E Eysm, fexp( Reeo-RRRLUBBaap (D.. U v)) k))/8) P(H, Dm))
15

---

Bayesian Active Learning for Bivariate Causal Discovery
The expectations are approximated using Monte Carlo sampling:
N P( Dm)
PDC
exp {-ReLU(ko - BFoi
1=1
(25)
exp { (PL U [(x, (()) k.)/8) P(H1 Dm)
Similarly, for the step case, write:
FDC (TI.K)
E Eyrmm
of (Dm (( (1) P(Hu Dm) (D,.. U ( F1) U Diu)) ki)/8)) P( (Dm)
(26)
By
where Diu ((22, B.). (T
F represents data of the next K 1 steps.
This differentiable approximation enables the use gradient- optimization methods find the optimal intervention values. The smoothing parameter controls the trade-off between approximation accuracy and optimization stability.
C. Application to multivariate causal discovery
To illustrate both the applicability and limitations of our method in general graphs, consider a three-node complete graph (as shown in Figure 5). Figure shows all possible configurations under Ho + Y, and Figure shows configurations under H, X Y.
Z
X
Y
?
Figure 5. A complete three-node graph with uncertain edge directions
Z
X
X
Y
X
Y
(a) Case (i)
(b) Case (ii)
(c) Case (iii)
Figure 6. Possible configurations under Hp X + Y
Z
Z
Z
X
X
(a) Case (i)
(b) Case (ii)
(c) Case (iii)
Figure 7. Possible configurations under H. X + Y
When testing the causal direction between and in this setting, under H, X + Y, the possible configurations are shown in Figure 6. For all these cases, [P do (X),, [Ho)) P.Y) since has no causal effect on Y.
16

---

Bayesian Active Learning for Bivariate Causal Discovery
Under [H] : X + Y, we have the configurations shown in Figure 7. The interventional distributions differ across these
cases: for cases (a) and (b), (YY do(X), H-) P X), while for case (c), IP(Y do(X), Hi) [ X,Z = z)d
However, when certain structural information is known (e.g., if we know X + Z + Y exists), the interventional distributions become uniquely identifiable, corresponding to case (c) Figure 7. In such cases, our method directly applies.
D. Experiments
D.1. Bayes Factor classification
The Bayes factor be classified into different categories of evidence strength (Jeffreys, 1961; Schönbrodt & Wagenmakers, 2017), which helps interpret its value in supporting Hilp or HHl, Table 3 presents these classifications:
Table 3. Classification for the evidence levels of the Bayes factor BF (from (Schönbrodt & Wagenmakers, 2017) adapted from (Jeffreys, 1961)).
Bayes factor
Evidence Level
> 100
Extreme evidence for lHl
30 - 100
Very strong evidence for IHl Strong evidence for Ho Moderate evidence for Ho Anecdotal evidence for Hig
10 - 30
- 10
1 1
1
No evidence
1/3-1
Anecdotal evidence for HI] Moderate evidence for HHI, Strong evidence for H₃ Very strong evidence for [H] Extreme evidence for HF]
1/10 1/3
1/30-1/11
1/100 1/30
< 1/100
This classification provides a systematic framework for interpreting Bayes factors, with values further from indicating stronger evidence for the respective hypothesis. The reciprocal nature of the classification (e.g., BF > 100 and BF < 1/100 representing extreme evidence for opposing hypotheses) reflects the symmetry in evidence interpretation.
D.2. Additional results on the discrete setting with ko 10
This appendix presents comprehensive performance results across the full range of total variation (TV) distances from 0 to 1.0, examining how the choice of Ipr Pol described in Section affects both the recall rate and Type error control. For each TV distance range (spanning intervals of 1), we show recall rates under IHI and Type I error rates under Ho. presented in consecutive columns.
17

---

Bayesian Active Learning for Bivariate Causal Discovery
850
Tand
8:35
0.33
0.21
8.55
10
1.0
800
100
100
81
230
23
130
comples
comples
Recall (0.0-0.1)
Type I (0.0-0.1)
Recall (0.1-0.2)
Type I (0.1-0.2)
9.55
0.04
06
9.53
62
3:1
100
21
4B
53
109
100
25
83
130
23
100
Samples
Intonvevional samplis
Intercetinall Samplis
Recall (0.2-0.3)
Type I (0.2-0.3)
Recall (0.3-0.4)
Type (0.3-0.44
1.0
3.54
0.94
3.53
3.52
1.0
110
20
4B
ODI
12
101
109
20
83
91
2.0
53
130
Incevattinall samplia
Intonvanionall samplo
Intersntiraa sampli
bamppl
Recall (0.4-0.5)
Type I (0.4-0.5)
Recall (0.5-0.6)
Type (0.5-0.6)
1.0
0/3
4B
109
103
83
130
Intervanionaal samples
Intananntio sampple
Interentional sumpless
Inservindioal somppl
Recall (0.6-0.7)
Type (0.6-0.7)
Recall (0.7-0.8)
Type (0.7-0.8)
1.0
3.54
0.53
0180
0.02
82
1:0
0.00
60
43
60
169
83
130
Interaational complex
Intecceotio complee
Interestioall corplex
Insevaaatinal complee
Recall (0.8-0.9)
Type (0.8-0.9)
Recall (0.9-1.0)
Type (0.9-1.0)
Figure 8. Performance evaluation showing recall rates and Type error rates for different causal strengthness (evalueted by the total variation (TV) distance ranges between P(Y do(X 0}} and [P do(X- 1)}
These results provide a complete picture of method performance across different distributional distances, complementing the focused analysis of representative TV ranges presented in the main text. The figures maintain a consistent layout: each row shows two pairs of metrics recall and Type I eтroг rates for consecutive TV distance ranges, allowing direct comparison of performance as the distributional similarity varies from highly similar (TV range 0-0.1) to highly distinct (TV range 0.9-1.0).
18

---

Bayesian Active Learning for Bivariate Causal Discovery
Setting I: Weak Causation
14/05
Manturer Priiles
048
Ouus
08
64
84
0005
50
Intorvantonal samplics
80
201
41
Dona sumplic
100
31
Insovcational sampla
01
10
101
Setting 2: Strong Causation
1.0
14
3.0
0.003
DUB
Typt
044
0000
Internedional sumples
20
60 Intevestionall Comple
40
231
Intervar Gonal samples
131
Interseriznal lang
10
(b)
Figure 9. Results on bivariate causal discovery with ko = 30 (very strong evidence). The two rows presents results in two different settings. Columns (a)-(d) report the type error rate, recall, PDc under o, and PDc under H,, respectively. in relation the number of intervention samples.
The paired layout facilitates examination of how performance evolves across adjacent TVV ranges, with each row capturing the transition between consecutive intervals.
D.3. Performance evaluation with different evidence thresholds
Following established Bayesian evidence interpretation frameworks (Jeffreys, 1961; Schönbrodt & Wagenmakers, 2018), we conducted additional experiments with more stringent evidence thresholds to verify the robustness of our proposed method. This subsection presents results for ko = 30 (very strong evidence) and ko 100 (extreme evidence), complementing the kg = 10 results shown above. These experiments were conducted response to reviewer feedback and demonstrate the utility of our methods across different evidence strength requirements.
Results with stringent evidence thresholds. We report the performance under more stringent evidence requirements in Fig. 9 and Fig. 10. Our method consistently outperforms baselines in recall while maintaining competitive type error rates across both kn = 30 and ko- 100 settings. The advantage stems from our Ppc-based optimization that efficiently collects decisive evidence. Importantly, the superior performance of our approach remains consistent across different evidence threshold requirements, demonstrating the robustness of the proposed intervention strategy.
D.4. Experiments on Continuous Settings
Experimental Setup For continuous intervention variables, we employ the Adam optimizer (Kingma & Ba, 2014) with cosine learning rate scheduling (Loshchilov Hutter, 2016) (initial rate 0.1, cosine decaying to 0.001 over 200 steps, total 4000 optimization steps). Following the same rejection criterion as in the discrete case, we maintain kg = n2 = 1, 000 observational samples with 100 sequential interventions.
1 = and use
k
Data Generation
We evaluate our method using additive noise models (ANMs):
Under H, X Y:
= f(X) +
(27)
Under H, X Y:
X = f(Y) +
(28)
Here f(x) = tanh(x) the nonlinear link function. To test robustness across different noise distributions, we create pool
19

---

Bayesian Active Learning for Bivariate Causal Discovery
Setting I: Weak Causation
84
Rtdd
1.005
Mul- sap BrSGan
90
0.006
0.004
1ype
0.002
8000
9.0
6.
Inrneettoral tamples
Inoweentioal
10
Sctting 2: Strong Causation
1.0
1.0
1.000
8.004
8002
Age
04
0.4
8000
02
002
samples
20 40
semples
50
110
Inteventional sample
02
30
100
20
Interentional samplts
50
200
(8)
(b)
(6)
(d)
Figure 10. Results on bivariate causal discovery with ko 100 (extreme evidence). The two rows presents results in two different settings. Columns (a)-(d) report the type error rate, recall, PDc under o, and PDc under 1,,, respectively. in relation the number of intervention samples.
of noise models including uniform, normal, Student's t, and two different 4-component Gaussian mixtures:
3 Softmax(z)
(29)
where z ~ A(0 [4). For each experimental setting, we randomly select one distribution from this pool. This approach allows us to evaluate our method's performance under diverse and complex noise patterns.
Parameter Estimation For each hypothesis H, we model the functional relationship as:
fo(x) tanh(bar)
(30)
where 0 - (a,b) are learnable parameters. The output distribution is modeled using mixture of Gaussian components to upproximate arbitrary distributions flexibly. We jointly learn these structural parameters along with the mixture model parameters (means, variances, and mixing weights) using maximum likelihood estimation on observational data. The optimization is performed using Adam optimizer (Kingma & Ba, 2014) for 10,000 steps with an initial learning rate of 0.1, which is decreased by a factor of at steps 3000, 5000, and 7500.
After learning the model parameters from observational data, we compute the likelihood interventional samples using the method described in Appendix B.5.
Results The experimental results in Figure 11 demonstrate that all methods achieve comparable performance in the continuous setting. Both recall and Type error rates show similar performance levels across different approaches, with well-controlled Type I error rates. This convergence can he attributed to the identifiability properties of ANMs, where causal direction can often be determined from observational data alone. The intervention selection strategy thus becomes less critical compared to the discrete case, highlighting how model structure influences the complexity of causal discovery.
D.5. Variance Analysis for Tree Structure Experiments
To better understand the performance characteristics of different methods, we analyze the distribution of required interven- tions across 200 random trials, visualized through violin plots partitioned into five groups. While the average performance of random intervention appears competitive certain settings, the violin plots reveal high variance its performance distribution. Specifically, the random strategy exhibits bimodal distribution with concentrated mass of trials requiring
20

---

Bayesian Active Learning for Bivariate Causal Discovery
1.0
0.8
0.8
Type Emror
0.6
Rocall
0.4
0.4
Rand
0.2
InfoGain
0.2
Multi-step InfoGain
Ours
Active Sampling Size
Active Sampling Size
(a) Recall
(b) Type Error
Figure 11. Performance comparison in continuous settings showing recall and Type I eтro rates. All methods achieve comparable performance with relatively few interventions, suggesting that the continuous additive noise setting, causal direction can effectively determined regardless of the intervention strategy.
few interventions and longer tail of trials requiring significantly more interventions. In contrast, both information gain and multi-step information gain methods demonstrate more uniform distributions, indicating more consistent and predictable performance across trials. This suggests that the seemingly competitive average performance of random intervention is largely driven by a small subset of fortunate trials, rather than reliable systematic efficiency.
Average Number of Interventions
Rand
200
InfoGain
Multi-step InfoGain
150
Ours
100
50
0.05
0.1
0.15 8
0.2
0.24
Figure 12. Distribution of required interventions across different effect sizes e, visualized using violin plots. Each violin plot represents the distribution of 200 trials partitioned into five groups.
21


Reviews:
[{"review_id": "n4cOiUHhnk", "reviewer": "Reviewer_aqQB", "summary": "This paper focuses on causal discovery through Bayes factor. Instead of using information-theoretic gains to determine the direction of causal relationships, this paper adopts Bayes factor and formulating the task as a hypothesis testing. Furthermore, it uses sequential experiment design to selectively gather information for effective optimization.\n\n## update after rebuttal: overall this work presents an interesting idea. The authors' responses help clarify my questions. I would like keep my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and valuable feedback in reviewing our paper. Here are our responses.\n\n**About benefits of using Bayes Factor.** We choose the Bayes factor because it naturally aligns well with our goal and hence is more efficient for optimization. Bayes factors are commonly used in experimental design to assess the strength of competing hypotheses. When expressed in terms of $\\mathbb{P}\\_{\\mathrm{DC}}$, it directly supports our objective of maximizing certainty and correctness in causal discovery. While maximizing $\\mathbb{P}\\_{\\mathrm{DC}}$ can also increase the information gain, it is a transformation of $\\mathbb{P}\\_{\\mathrm{DC}}$, and optimizing this transformation is less efficient. As shown in Figures 1 and 3, $\\mathbb{P}\\_{\\mathrm{DC}}$ offers higher intervention efficiency compared to information gain.\n\n**Threshold of Bayes Factor.** We choose following [1,2] that provided evidence categories for different thresholds. Following [1,2], we chose $k\\_0=10$ as the threshold for \"strong evidence\". We also conducted experiments with $k\\_0=30, 100$ (\"very strong\" and \"extreme evidence\") available at https://sites.google.com/view/additional-figures-icml4692/ and the results verified the utility of our methods. We will include these experimental results in the final version.\n\n**Performance with small sample sizes.** We tested our method with $n=100$ and found it remains robust compared to the result with $n=1,000$. Below are the results for the Type I error rate (the proportion of cases where $\\mathrm{BF}\\_{10} > k\\_1$ under $\\mathbb{H}\\_0$, which differs from the more conservative definition used in the paper: $\\mathrm{BF}\\_{10} > \\frac{1}{k\\_0}$ under $\\mathbb{H}\\_0$) and recall (the proportion of cases where $\\mathrm{BF}\\_{10} > k\\_1$ under $\\mathbb{H}\\_1$):\n\n|$\\|\\mathcal{D}\\_{\\mathrm{obs}}\\|$|Type I Error (Setting 1)| Recall (Setting 1) | Type I Error (Setting 2)|Recall (Setting 2)|\n|----------------------| ------------------------|------------------|------------------------|------------------|\n|$100$| $0.0205\\pm0.0128$|$0.7595\\pm 0.0483$|$0.0005\\pm 0.0022$|$1.0000\\pm 0.0000$|\n|$1000$| $0.0305\\pm0.0186$|$0.8840\\pm 0.0325$|$0.0000\\pm 0.0000$|$1.0000\\pm 0.0000$|\n\nThese results show our method maintains high performance even with significantly reduced observational data.\n\n**Applicability to more complex graphs.** As discussed in lines 283-284, our current method requires $p\\\\{y|\\mathrm{do}(x)\\\\}$ to be identifiable from observational data, in order to calculate $\\mathbb{P}\\_{\\mathrm{DC}}$. As claimed in the \"Discussion\" section, this might not be achievable in multivariate causal discovery, as $p\\\\{y|\\mathrm{do}(x)\\\\}$ cannot be uniquely determined among the Markov equivalent class.\n\nTo resolve this problem, a promising solution is to extend $\\mathbb{P}\\_{\\mathrm{DC}}$ as the ratio of maximum likelhood over the equivalence class:\n\n$$\\mathrm{BF}\\_{01} = \\frac{\\max\\_{G \\in \\mathcal{G}^{(x,y)}\\_0} \\mathbb{P}\\\\{\\mathcal{D}| G,\\mathrm{do}(x),\\mathbb{H}\\_0\\\\}}{\\max\\_{G \\in \\mathcal{G}^{(x,y)}\\_0} \\mathbb{P}\\\\{\\mathcal{D}| G,\\mathrm{do}(x),\\mathbb{H}\\_1\\\\}}$$\n\nwhere $\\mathcal{G}^{(x,y)}\\_0$ (*resp.* $\\mathcal{G}^{(x,y)}\\_1$) denotes the Markov equivalence class regarding $p\\\\{y|\\mathrm{do}(x)\\\\}$ under $\\mathbb{H}\\_0$ (*resp.* $\\mathbb{H}\\_1$). Since $\\mathcal{G}^{(x,y)}\\_0$ (*resp.* $\\mathcal{G}^{(x,y)}\\_1$) encompasses the true graph under $\\mathbb{H}\\_0$ (*resp.* $\\mathbb{H}\\_1$), the maximum value recovers the true likelihood. We will pursue this direction in the future.\n\n**Computational Complexity.** Existing methods [3] adopted the greedy strategy. To avoid the local minima issue[4], they need to optimize the multi-step objective. The complexity is exponential. By using dynamic programming, we can reduce it to polynomial complexity.\n\n**Comparison with Castelletti & Consonni (2024).** The comparison may not be appropriate as we consider different settings. Castelletti & Consonni (2024) focuses on pre-experiment sample size determination without interaction with the environment. In contrast, we focus on determining the intervention value and can receive feedback from the environment at each iteration.\n**References**\n\n[1] Jeffreys, H. Theory of Probability (3rd Edition). Oxford, University Press, 1961.\n\n[2] Schönbrodt, F. D. and Wagenmakers, E.-J. Bayes factor design analysis: Planning for compelling evidence. Psychonomic bulletin & review, 25(1):128-142, 2018.\n\n[3] Toth C, Lorch L, Knoll C, et al. Active bayesian causal inference[J]. Advances in Neural Information Processing Systems, 2022, 35: 16261-16275.\n\n[4] Greenewald, K., Katz, D., Shanmugam, K., Magliacane, S., Kocaoglu, M., Boix Adsera, E., and Bresler, G. Sample efficient active learning of causal trees. Advances in Neural Information Processing Systems, 32, 2019.", "claims_and_evidence": "One claim is that: “we employ Bayes factors to establish an objective that directly optimizes the probability of obtaining decisive and accurate evidence, leading to more efficient causal discovery.”. This claim is supported by discussions on connection to information gain. However, it is not clear to me the real benefit by replacing traditional methods with Bayes factors.", "methods_and_evaluation_criteria": "The proposed methods make sense to me. I think it is an interesting idea that formulating the task as a hypothesis testing problem.", "theoretical_claims": "I have checked the derivations showing connection to information gain.", "experimental_designs_or_analyses": "How does the proposed approach compare to (Castelletti & Consonni, 2024)?", "relation_to_broader_scientific_literature": "Improving efficiency of causal discovery is important in many real-world applications, especially involving reasoning. This work could lay a strong foundation for empowering AI systems with causal reasoning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1.\tIt is interesting to formulate the task as an independent test. Is there any justification in using Bayes Factor instead of other techniques for performing independence tests?\n\n2.\tHow is the threshold of Bayes factor determined? Does the performance sensitive to the threshold?\n\n3.\tIn Table 1, three different sizes of sample set are considered. Considering the bivariable case, these sizes should be sufficient. How about further reducing the size of samples? Will the model remain robust under insufficient data?\n\n4.\tFor multivariate cases, the authors discussed 3-node graph in Appendix and studied tree-graph in the main paper. Are there any justifications like under which conditions the proposed approach work? In other words, how does the proposed approach generalize complex graphs with multiple variables and with loops.\n\n5.\tWhat is the complexity of the proposed approach compared to existing methods.\n\n6.    How does the proposed approach compare to (Castelletti & Consonni, 2024) in practice?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x043zEBv52", "reviewer": "Reviewer_g8jk", "summary": "This paper investigate the problem of determining the direction of relationships between variables by active intervention. The previous literature tries to maximize the information-theoretic gains for deciding the intervention value which may not effectively measure the reliability of direction determination. In contrast, this paper leverage the Bayes factor to formulate the objective function. To consider the multi-step intervention, this paper also propose a sequential intervention objective and develop a dynamic programming algorithm to solve it. The extensive experimental results show the effectiveness of the method in requiring less intervention and more correct direction.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and positive feedbacks regarding our paper. We address your concerns below.\n\n**Definition of $\\mathbf{x\\_{-k}}$ in Proposition 4.2.** Thank you for your clarification. We will correct this in the updated version.\n\n**Conditional Probability in equations (1b), (1c), and (6).** As mentioned in lines 201-202 (right column), we omit $\\mathcal{D}\\_m$ for simplicity. We apologize for any confusion and will highlight this in the updated version.\n\n**Threshold derivation.** Thank you for pointing this out. The threshold should be $\\frac{\\gamma\\_0}{(1-\\gamma\\_0)\\omega}$. According to Bayes formula, we have:\n\n$$\\mathrm{BF}\\_{01} = \\frac{\\mathbb{P}(\\mathcal{D}|\\mathbb{H}\\_0)}{\\mathbb{P}(\\mathcal{D}|\\mathbb{H}\\_1)} = \\frac{\\mathbb{P}(\\mathbb{H}\\_0|\\mathcal{D})\\mathbb{P}(\\mathbb{H}\\_1)}{\\mathbb{P}(\\mathbb{H}\\_1|\\mathcal{D})\\mathbb{P}(\\mathbb{H}\\_0)}$$\n\nSince we require $\\mathbb{P}(\\mathbb{H}\\_0|\\mathcal{D}) > \\gamma\\_0$, and by $\\omega:=\\frac{\\mathbb{P}(\\mathbb{H}\\_0)}{\\mathbb{P}(\\mathbb{H}\\_1)}$, we should have $k\\_0 = \\frac{\\gamma\\_0}{(1-\\gamma\\_0)\\omega}$.\n\n**Missing Discount Factor $\\gamma$.** Thank you for pointing this out. We will correct it later.\n\n**Complexity Analysis.** The complexity is related to the number of intervention steps $K$, rather than $|\\mathcal{X}|$. Since $X$ is discrete, the cardinality of the input space $|\\mathcal{X}|$ is finite and remains constant once the setting is determined.", "claims_and_evidence": "I think the empirical comparison experiments and the method design support the claims. The method performs better in direction determination and can be applied in wide scenarios.", "methods_and_evaluation_criteria": "I have some concerns about the design of methods. The details can be found in the Questions. The evaluation process makes sense.", "theoretical_claims": "I check the proof. However, I think the statement in Proposition 4.2 have some flaws. \"Given $\\bar{x}_{-k}^*$\"  should be modified as \n\n\"Given $\\bar{x}_{1:k-1}^*$\".", "experimental_designs_or_analyses": "I think the experimental design and analysis make sense and clearly shows the effectiveness of the method.", "relation_to_broader_scientific_literature": "This paper investigate a classical problem of determining the causal direction. The main contribution is concentrated on the novel objective functions developed with Bayes Factors and an improvement to multi-step version.", "essential_references_not_discussed": "I think the main references have been discussed.", "other_strengths_and_weaknesses": "This paper investigate a solid and challenging problem. The proposed method is advanced, but left some concerns of the soundness. The details of the concern can be found in the questions.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "I have the following concerns about the method.\n\n1. In equation (1b) and (1c), the probability is conditional on $D_m$. However, the definition of BF is not related to this condition. In contrast, in equation (6), this condition is missed.\n\n2. In the next paragraph, how is the threshold of $\\omega \\frac{\\gamma_0}{1-\\gamma_0}$ derived?\n\n3. In the objective function (8), the discount $\\gamma$ is missed.\n\n4. According to the Complexity Analysis subsection, the time complexity is exponential rather than polynomial.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YNljxJWOoK", "reviewer": "Reviewer_yCr9", "summary": "This paper presents a Bayesian active learning framework for identifying causal directions between variables through interventional strategies. Different from traditional information-theoretic approaches, it introduces an objective based on Bayes factors, which directly quantify the strength of evidence supporting one causal hypothesis over another. The authors formulate a sequential intervention objective that balances immediate and future evidential gains to optimize intervention selection. \n\nTo manage the computational complexity, they propose a dynamic programming algorithm that makes multi-step intervention planning tractable. The framework is tested across bivariate systems, tree-structured graphs, and embodied AI reasoning tasks, showing superior performance over baselines like InfoGain and random strategies. This approach effectively improves causal direction discovery, especially under limited budgets and weak causal influences.\n\n[Attention: Kindly note that the paper slightly exceeds the 8-page main-paper limit by one line.]", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your efforts and feedback in reviewing our paper. We address your questions below.\n\n**Why estimating priors using observation data?** We do not update priors using interventional data since if $k\\_0 > 1$, it is difficult for $\\mathrm{BF}\\_{01}$ to be greater than $k\\_0$ to identify $\\mathbb{H}\\_0$. To explain, even if $\\mathbb{H}\\_0$ is true, the data may exhibit a weak correlation between $X$ and $Y$. In such cases, it could happen that $\\mathbb{P}(\\mathcal{D}|\\mathbb{H}\\_1) \\geq \\mathbb{P}(\\mathcal{D}|\\mathbb{H}\\_0)$, making it fail to identify $\\mathbb{H}\\_0$ with $k\\_0 > 1$. A possible solution is to choose a lower $k\\_0$, such as setting $k\\_0 \\leq 1$. We will explore this in the future.\n\n**Scalability to general graphs.** We can extend our method to the general graph by redefining $\\mathbb{P}\\_{\\mathrm{DC}}$ as the ratio of maximum likelhood over the equivalence class:\n\n$$\\mathrm{BF}\\_{01} = \\frac{\\max\\_{G \\in \\mathcal{G}^{(x,y)}\\_0} \\mathbb{P}\\\\{\\mathcal{D}| G,\\mathrm{do}(x),\\mathbb{H}\\_0\\\\}}{\\max\\_{G \\in \\mathcal{G}^{(x,y)}\\_0} \\mathbb{P}\\\\{\\mathcal{D}| G,\\mathrm{do}(x),\\mathbb{H}\\_1\\\\}}$$\n\nwhere $\\mathcal{G}^{(x,y)}\\_0$ (*resp.* $\\mathcal{G}^{(x,y)}\\_1$) denotes the Markov equivalence class regarding $p\\\\{y|\\mathrm{do}(x)\\\\}$ under $\\mathbb{H}\\_0$ (*resp.* $\\mathbb{H}\\_1$). Since $\\mathcal{G}^{(x,y)}\\_0$ (*resp.* $\\mathcal{G}^{(x,y)}\\_1$) encompasses the true graph under $\\mathbb{H}\\_0$ (*resp.* $\\mathbb{H}\\_1$), it recovers the true likelihood ratio. We will pursue this direction in the future.\n\n**Evaluation metrics.** In our causal hypothesis testing setting, where $\\mathbb{H}\\_1$ (causal relationship exists) is the primary concern in causal discovery, we focus on Type I error rate (probability of detecting $\\mathbb{H}\\_1$ when $\\mathbb{H}\\_0$ is true) and recall (probability of detecting $\\mathbb{H}\\_1$ when $\\mathbb{H}\\_1$ is true, which is 1 - Type II error rate). We have provided all metrics (Type I error rate, Type II error rate, precision, recall, F1) at https://sites.google.com/view/additional-figures-icml4692/. Our method achieves competitive precision while outperforming baselines on other metrics. We will include these comprehensive results in the final version.\n\n**Robustness to causal sufficiency violations.** We assume causal sufficiency since our method requires the identifiability of $p\\\\{y|\\mathrm{do}(x)\\\\}$, as claimed in lines 283-284, 432-434 (right column).\n\nTo relax this condition, we can estimate $p\\\\{y|\\mathrm{do}(x)\\\\}$ using interventional data. In this regard, we should adjust the threshold for $\\mathrm{BF}\\_{01}$, as discussed in our response to the first question.\n\n**Threshold of Bayes Factor.** We choose following [1,2] that provided evidence categories for different thresholds. Following [1,2], we chose $k\\_0=10$ as the threshold for \"strong evidence\". We also conducted experiments with $k\\_0=30, 100$ (\"very strong\" and \"extreme evidence\") available at https://sites.google.com/view/additional-figures-icml4692/ and the results verified the utility of our methods. We will include these experimental results in the final version.\n\n**Additional references.** Thanks for your suggestions, we will add these references and discuss them accordingly.\n\n**References**\n\n[1] Jeffreys, H. Theory of Probability (3rd Edition). Oxford, University Press, 1961.\n\n[2] Schönbrodt, F. D. and Wagenmakers, E.-J. Bayes factor design analysis: Planning for compelling evidence. Psychonomic bulletin & review, 25(1):128-142, 2018.", "claims_and_evidence": "Yes. The core part of this paper is the Bayesian active learning framework. Some preliminary information is clearly introduced in Section 3, and the core methodology is mentioned in Section 4 in details.", "methods_and_evaluation_criteria": "Yes, this paper is focusing on bivariate causal discovery task. The proposed method formulates this causal direction identification as a hypothesis-testing problem, and proposes a Bayes factor-based intervention strategy, which is interesting and totally making sense. As for the evaluation, it remains unclear why only Type I error and Recall (no considering Type II error, Precision, F1) are used in the evaluation.", "theoretical_claims": "Yes, the only theoretical claims in this paper are Proposition 4.1 and Proposition 4.2. I have checked the correctness of these two Propositions.", "experimental_designs_or_analyses": "Yes, the experiments mainly cover bivariate causal discovery and tree-structure causal graph learning as synthetic experiments, and also causal reasoning in embodied AI as real-world experiments.", "relation_to_broader_scientific_literature": "Traditional approaches in active causal discovery have predominantly used information-theoretic objectives, while this paper shifts from information gain to Bayes factor-based objectives, which is somewhat a new aspect.", "essential_references_not_discussed": "Yes. (1) The paper emphasizes decision-focused active learning via Bayes factors, but does not discuss classic Bayesian decision-theoretic foundations, for example, [Chick'2006]. (2) Quite some papers, about decision-making under causal uncertainty, are not mentioned in the paper, such as [Gonzalez'2018]. \n\n[Chick'2006] Chick, S.E. “Bayesian Approaches to Optimal Decision Making Under Uncertainty”, 2006.\n\n[Gonzalez'2018] M. Gonzalez-Soto, et al. \"Playing against Nature: causal discovery for decision making under uncertainty\", 2018.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- With Bayes factor-based objective, this paper offers a direct and interpretable way to assess causal direction, addressing a major limitation of indirect mutual information-based methods.\n- When sequential optimization meets with dynamic programming, it provides a theoretically grounded and computationally efficient way to plan multi-step interventions, outperforming greedy or myopic baselines.\n- The proposed method is robust across settings. It demonstrates consistent performance in both weak and strong causation scenarios, making it suitable for diverse real-world applications.\n- It is scalable to Multivariate Causal Discovery, extending naturally to tree-structured graphs and multivariate problems, and showing flexibility and generalization potential.\n\n**Weaknesses and Comments:**\n- Heavily relying on accurate prior estimation, this paper requires prior specification from observational data, and does not update priors using intervention data, which could limit adaptation to complex systems.\n- Scalability to general graphs is still limited and challenging. While the method works well on tree structures, extension to general cyclic graphs or complex network structures remains a challenge.", "other_comments_or_suggestions": "Typos:\n\n- Line 399: At Table 2, \"Table 2. Average number of interventions required in the switch-ligh reasoning task\" -> \"switch-light reasoning task\";\n\n- Line 424: \"We develope a simulation environment based on TongSim\" -> \"We develop a simulation ...\";", "questions_for_authors": "- Why only Type I error and Recall are used, while no considering Type II error, Precision, F1, in the experimental evaluations?\n\n- How robust is the Bayes factor-based intervention strategy if the true data-generating process violates causal sufficiency?\n\n- How sensitive is your method’s performance to these hyperparameters? e.g., $k_0$ = 10, $k_1$=0.1, how do you find those values?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Gt1Ca9vPHr", "reviewer": "Reviewer_uXGK", "summary": "This paper investigates the problem of identifying the causal direction between two variables, i.e., identify whether x->y or y-> x, through Bayesian active intervention. The paper addresses this problem as a hypothesis testing problem, with a testing statistic called \"probability of decisive and correct evidence\" ($P_{DC}$) that depends on the Bayes factor (likelihood ratio of the hypothesis over data D). It then proposes an iterative active learning strategy that selects intervention values of X in order to gain most evidence according to the $P_{DC}$ criterion. It also provides a dynamic programming optimization strategy for planning interventions over multiple steps that reduces the combinatorial search space. \nThe paper then discusses 3 main experiments: (1) binary X, Y with two different causal directions in the form of Bernoulli distributions; (2) tree structured distribution and (3) a simulation environment with switch and light. In all 3 experiment environments, it compares their method with 3 baselines: random, infogain, and multi-step inforgain where it shows sample efficiency of their method over the baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and feedback regarding our paper. We address your concerns below.\n\n**Validity of PDC for sample selection.** Our framework is valid since the factorization of BF still holds if $x\\_i$ depends on the historical data. Intuitively, this is because the dependency only happens to the selection of $\\overline{x}$, while BF compares the ratio of two hypotheses that differ only in $p\\\\{y|\\mathrm{do}(x)\\\\}$.\n\nSpecifically, the joint probability $\\mathbb{P}\\\\{\\mathcal{D}\\_m|\\mathbb{H}\\_0\\\\}$ is:\n\n$$\\mathbb{P}\\\\{\\mathcal{D}\\_m|\\mathbb{H}\\_0\\\\} = \\mathbb{P}\\\\{\\overline{x}\\_1\\\\}\\mathbb{P}\\\\{\\overline{y}\\_1|\\mathrm{do}(\\overline{x}\\_1)\\\\} \\Pi\\_{i=2} \\mathbb{P}\\\\{\\overline{x}\\_i|\\overline{x}\\_{1:i-1},\\overline{y}\\_{1:i-1},\\\\}\\mathbb{P}\\\\{\\overline{y}\\_i|\\mathrm{do}(\\overline{x}\\_i)\\\\}$$\n\nsince $\\overline{y}\\_i$ only depends on the value of intervened $\\overline{x}\\_i$ during generation. We can derive a similar factorization for $\\mathbb{P}\\\\{\\mathcal{D}\\_m|\\mathbb{H}\\_1\\\\}$. When computing the Bayes factor, the term $\\mathbb{P}\\\\{\\overline{x}\\_i|\\cdot\\\\}$ was canceled out by the numerator and denominator, leading to:\n\n$$\\mathrm{BF}(\\mathcal{D}\\_m) = \\prod\\_{i=1}^m \\frac{p\\\\{\\overline{y}\\_i|\\mathrm{do}(\\overline{x}\\_i),\\mathbb{H}\\_0\\\\}}{p\\\\{\\overline{y}\\_i|\\mathrm{do}(\\overline{x}\\_i),\\mathbb{H}\\_1\\\\}}$$\n\nThe next intervention value $\\overline{x}\\_{m+1}$ is then optimized based on $\\mathcal{D}\\_m:=\\\\{(\\overline{x}\\_i,\\overline{y}\\_i\\\\}$.\n\nIn summary, while the selection of the intervention value depends on the historical information, the factorization still holds as we can cancel out these terms.\n\n**Distribution classes and generalizability.** As detailed in Appendix D.3, we do not restrict the model to be Gaussian. We have conducted experiments for uniform, normal, Student's t, and Gaussian mixtures and the results are shown in Figure 9.\n\n**Adapting to general DAGs.** As discussed in lines 283-284, our current version cannot work on general graph since it requires $p\\\\{y|\\mathrm{do}(x)\\\\}$ to be identifiable from observational data.\n\nA promising solution is to extend $\\mathbb{P}\\_{\\mathrm{DC}}$ as the ratio of maximum likelhood over the equivalence class:\n\n$$\\mathrm{BF}\\_{01} = \\frac{\\max\\_{G \\in \\mathcal{G}^{(x,y)}\\_0} \\mathbb{P}\\\\{\\mathcal{D}| G,\\mathrm{do}(x),\\mathbb{H}\\_0\\\\}}{\\max\\_{G \\in \\mathcal{G}^{(x,y)}\\_0} \\mathbb{P}\\\\{\\mathcal{D}| G,\\mathrm{do}(x),\\mathbb{H}\\_1\\\\}}$$\n\nwhere $\\mathcal{G}^{(x,y)}\\_0$ (*resp.* $\\mathcal{G}^{(x,y)}\\_1$) denotes the Markov equivalence class regarding $p\\\\{y|\\mathrm{do}(x)\\\\}$ under $\\mathbb{H}\\_0$ (*resp.* $\\mathbb{H}\\_1$). Since $\\mathcal{G}^{(x,y)}\\_0$ (*resp.* $\\mathcal{G}^{(x,y)}\\_1$) encompasses the true graph under $\\mathbb{H}\\_0$ (*resp.* $\\mathbb{H}\\_1$), it recovers the true likelihood ratio. We will pursue this direction in the future.\n\n**Effect of distribution misspecification.** If $p\\\\{y|\\mathrm{do}(x)\\\\}$ is misspecified, the $\\mathbb{P}\\_{\\mathrm{DC}}$ would not be accurate. As claimed in lines 283-284, 432-434 (right column), our method requires $p\\\\{y|\\mathrm{do}(x)\\\\}$ to be identified correctly. A possible solution is to update with interventional data, such as setting $k\\_0 \\leq 1$. We will explore this in the future.\n\n**Difference between switch-light task and simulation.** The switch-light task different from the one in simlation, as it involves confounding bias caused by $S\\_1 \\rightarrow L\\_1$, $S\\_2 \\rightarrow L\\_2$ or $S\\_1 \\rightarrow L\\_2$, $S\\_2 \\rightarrow L\\_1$. We present this to illustrate the applicability of our mehtod to this setting.\n\n**About table 2.** As claimed in line 411, we only say our method is competitive to others. Overall, we achieve comparable and better perfomance than other baselines across all tasks.", "claims_and_evidence": "I am not sure whether I agree with the authors that the proposed test statistic $P_{DC}$ is valid for sample selection. From my understanding, the goal of the paper is to give a criteria for actively selecting new data to collect evidence for either direction, that is, each new selection of x_i is dependent on the historical trajectory. However, the statistic $P_{DC}$ depends on the Bayes factor which assumes complete factorization for each x_i, i.e., independence.", "methods_and_evaluation_criteria": "The paper only discusses two very specific distribution classes for X and Y, for the continuous case, the paper uses Gaussian; and for categorical, it uses Beta-Bernoulli. It is unclear to me if the results generalize to other distributions, e.g. computational issues might arise that requires more sophisticated approximation and optimization techniques.", "theoretical_claims": "See above.", "experimental_designs_or_analyses": "The experiment setting seem a bit weak to me, in that all the experiments provided essentially only focus on the case of binary variables and Bernoulli distribution. \nSpecifically, the paper discusses 3 main experiments: (1) binary X, Y with two different causal directions in the form of Bernoulli distributions; (2) tree structured distribution and (3) a simulation environment with switch and light. In all 3 experiment environments, it compares their method with 3 baselines: random, infogain, and multi-step inforgain. The \"strength\" of the causation is tuned by the magnitude of the difference in conditional probabilities. \n\nI'm not sure how the embodied AI switch-light reasoning task is more complicated than the binary example in 5.1 and 5.2, given the switches S_1, S_2, and lights L_1, L_2 are just indicator variables. The paper mentions the addition of latent confounder, but how does the confounder affect the dynamic and why does it make the problem harder?\n\nMoreover, in table 2, it is not clear that the paper's method performs better than the other methods, given the performances of the paper's method are inside the confidence set of the baseline performances for every single instance.", "relation_to_broader_scientific_literature": "The paper designs a Bayesian active learning technique to address the question of distinguishing causal direction of bivariate systems. \nThe proposed selection criteria uses the idea of hypothesis testing to measure the strength of evidence in favor of the null hypothesis over the alternative.", "essential_references_not_discussed": "n.a.", "other_strengths_and_weaknesses": "n.a.", "other_comments_or_suggestions": "n.a.", "questions_for_authors": "- The paper shows how to deal with tree-structured graphs. How would you adapt your method if the graph is not a tree but a more general DAG?\n- If the distribution $p(y\\mid x)$ is misspecified, how does that affect the reliability of $P_{DC}$?\n- For experiment section 5.3, I'm not sure how the embodied AI switch-light reasoning task is more complicated than the binary example in 5.1 and 5.2, given the switches S_1, S_2, and lights L_1, L_2 are just indicator variables. The paper mentions the addition of latent confounder, but how does the confounder affect the dynamic and why does it make the problem harder?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers agree on this paper, in details they found strong points in the manuscript; i) the paper investigates a solid and challenging problem, and the proposed method is advanced, ii) the idea to use the Bayes factor-based objective, offers a direct and interpretable way to assess causal direction, addressing a major limitation of indirect mutual information-based methods, iii) the combination of sequential optimization and dynamic programming, provides a theoretically grounded and computationally efficient way to plan multi-step interventions, outperforming greedy or myopic baselines, iv) the performance under several settings is robust as it emerges from the numerical experiments, v) the proposed method is scalable to multivariate causal discovery, thus widening the settings where the method can be fruitfully applied. However, some weacknesses were pointed out, the main being; i) some criticism exists on the the soundness, ii) the paper strongly  relies on accurate prior estimation, while the proposed method requires prior specification from observational data, and does not update priors using intervention data, and this has been pointed out to limit adaptation to complex systems, iii) Some limitations was also raised with respect to scalability to general graphs. Indeed, while the method works well on tree structures, extension to general cyclic graphs or complex network structures remains a challenge. iv) anothe limitation was that the experimental setting seems a bit weak, in that all the experiments provided essentially only focus on the case of binary variables and Bernoulli distribution. However, the rebuttals from the author, as recognized by almost all the reviewers, solved all the concerns that were in the reviews. I personally liked the authors rebuttals which addressed point by point all the critical aspects as spotted by the reviewers.
Decision: Accept (poster)