Graph Agnostic Causal Bayesian Optimisation

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-09-06 04:39:50

Abstract: We study the problem of globally optimising a target variable of an unknown causal graph on which a sequence of soft or hard interventions can be performed. 
     The problem of optimising the target variable associated with a causal graph is formalised as Causal Bayesian Optimisation (CBO).
     We study the CBO problem under the cumulative regret objective with unknown causal graphs for two settings, namely structural causal models with hard interventions and function networks with soft interventions.
     We propose Graph Agnostic Causal Bayesian Optimisation (GACBO), an algorithm that actively discovers the causal structure that contributes to achieving optimal rewards. GACBO seeks to balance exploiting the actions that give the best rewards against exploring the causal structures and functions. 
     To the best of our knowledge, our work is the first to study causal Bayesian optimization with cumulative regret objectives in scenarios where the graph is unknown or partially known. We show our proposed algorithm outperforms baselines in simulated experiments and real-world applications.

Main paper: 
 problem setup: 
 Structural Causal Models An SCM [Pearl, 2009] is defined as a tuple ⟨g, Y, V , f g , Ω⟩, where g is a Directed Acyclic Graph (DAG) describing the relations between observed random variablesV = {V i } m-1 i=0 , with each node i ∈ [m] belonging to a compact space V i ⊂ R.Here, Y = V m is the reward variable, and f g = {f g i } m i=0 represents the unknown functions associated with g, with independent noise terms Ω = {Ω i } m i=0 having zero mean and a known distribution. The parent nodes of any node i in g are denoted by pa g (i) ⊂ [m], andZ g i = {V j } j∈pag(i) represents the parents of node i in g. Each node V i ∈ V is generated by the function f g i : Z i,g → V i , with the observed value v i given by v i = f g i (z g i ) + ω i .These functions are evaluated topologically from root to leaf nodes according to g. In this setting, not all observable variables are intervenable [Lee and Bareinboim, 2019] . Let I ⊂ {0, . . . , m -1} denote the indices of intervenable variables. The set of observed variables V is decomposed into intervenable variables X = {V j } j∈I and non-intervenable variables C = {V j } j / ∈I , with the target variable Y = V m assumed to be non-intervenable.We use a soft intervention model for noisy function networks (NFNs) [Eberhardt and Scheines, 2007] , where controllable action variables a = {a j } n j=0 are added as nodes in g and act as parents to nodes V i , making them inputs to f g i . The subset a g i ⊂ a affects V i based on g, with the action space A g i ⊂ R |a g i | and total action space A. Since f g i : Z g i × A g i → V i is unknown, the agent cannot predict the effect of a g i on V i in advance. Observations are modelled as a special case i.e., {a j = 0∀a j ∈ a g i }Hard interventions are modelled as a subset of intervenable variables I ∈ P(I) being set to values a I = {a i } i∈I independent of their parents using the do operator s.t. {do(x i = a i ) ∀i ∈ I, a i ∈ A i ⊂R} and values are evaluated for all nodes i ∈ [m], based on the topological ordering of g The objective is to design a sequence of actions {a :,t } T t=0 or {I t , a It } T t=0 that maximizes the average expected reward for soft and hard interventions, respectively, which is equivalent to minimizing the expected cumulative regret [Sussex et al., 2022, Lattimore and Szepesvári, 2020] : Plausible Models At time step t, plausible models are defined as the set of surrogate models likely to contain the true SCM, with confidence intervals ensuring a probability of at least 1 -δ. We calculate the plausible functions for each node i using:v i = f g i (z g i ) + ω i if i / ∈ I a i if i ∈ I (1)R T = T t=1 [E[y|a * ] -E[y|a :,t ]] ; R T = T t=1 [E[y|a * ] -E[y|do(x It = a It )]] .EQUATIONE i,t [z i , a i ] = E g∼p(g|Dt) [µ g i,t-1 (z g i , a g i )], V i,t [z i , a i ] = V g∼p(g|Dt) [µ g i,t-1 (z g i , a g i )] + E g∼p(g|Dt) [(σ g i,t-1 (z g i , a g i )) 2 ].Here, z i includes all observable nodes except V i , and β i,t ensures confidence bounds, set as β i,t = β T .Further details about β i,t are provided in A.6 At time t, all f g i within the confidence intervals defined by the joint posterior p(g|D t ) and associated GP posteriors form the plausible functions M t :  and  (2) holds for all a ∈ A}.M g t = { fg = { f g i } |V | i=0 such that ∀ i : f g i ∈ H ki , ∥ f g i ∥ ki ≤ B i ,(3)The plausible graphs G t are defined as:EQUATION) with G 0 = {g ∈ G}, where G denotes the space of all possible DAGs. For a graph to be plausible at time t, there must be at least one associated function within the confidence interval for each node.Algorithm We present two variants of the GACBO algorithm for soft 1 and hard interventions 2.The causal subgraph discovery algorithm 3 is used in both variants of the algorithm to estimate the graph posteriors and sample relevant graphs.The maximum possible value varies across different graphs and function sets within the plausible models at time t, each having its own optimal action. Our acquisition function identifies the graph and function set that yield the highest target node value and returns the action that achieves it. (5) It is important to note that 5 is not suitable for standard optimization methods because it requires maximization over a set of functions with a bounded RKHS norm.Therefore for a graph g within the plausible models, the reparametrisation trick introduced in Curi et al.[2020] and utilised for CBO in Sussex et al. [2022] can be used to write any functionEQUATIONThe acquisition function can therefore be expressed in terms of η g : Z g × A g - → [-1, 1] |V (g)| ,EQUATIONMore details about the optimistic reparameterisation trick can be found in A.5. The data collected is used to update model posteriors and construct plausible models for next time step. 
results: 
 We evaluate GACBO on synthetic environments (Dropwave, Alpine3, Rosenbrock, ToyGraph) and a real-world Epidemiology Graph from [Astudillo and Frazier, 2021, Branchini et al., 2023] . The metric used is the average reward, inversely related to cumulative regret. We repeat each experiment 5 times with different seeds and report average rewards ±σ/ √ 5, where σ is the standard deviation.We compare GACBO with: 1) MCBO [Sussex et al., 2022] using the true causal graph, 2) MCBO with incorrect graphs (missing or extra edges), 3) GP-UCB [Srinivas et al., 2009] for soft interventions. Using standard notation, we use Capital letters to denote random variables and lowercase letters to denote the realization of said random variables. We use bold letters to denote sets of certain nodes.The support of a variable is given by curly letters. We use the subscript t to index data observed thus far, and the subscript i is used to index a particular node in a vector, the superscript g is used to refer to the input space Symbol DescriptionV j j th observed variable Y Target variable we seek to optimize corresponds to V m V Set of all observed variables X Set of intervenable variables C Set of non intervenable variables A i Action performed on node i g * True latent causal graph A Action vector composed of {A i } m i=0 Z g * i The parents of node i in graph g * f g * i (z g * i , a g * i )functions relating a node i with it's parents and actionsf g * (a)The overall function with input action composed of functions {f Surrogate Functions We model surrogate functions using Gaussian processes (GPs). Posterior means µ g i,t and variances σ g i,t for any function parameterising any possible graph g at a given point is calculated according to the GP posterior at time step t. The posterior is calculated using GP update equations [Williams and Rasmussen, 1995] .g i (•, •) σ g i,t (•) Variance function based on data D t and kernel k g i (•, •) GP (µ g i,t , σ g i,t ) Gaussian Process f g i (•) ∼ N (µ g i,t (•), σ g i,t (•)) H k g i Hilbert Spaces of functions implied by kernel k g i f g i A functionEQUATIONwhereEQUATIONwhere I is used to define the identity matrix, vec(v i,1:t ) = [v i,1 . . . v i,t ] ⊤ , k g i,t (z g i , a g i ) = [k g i ((z g i,1 , a g i,1 ), (z g i , a g i )), . . . , k g i ((z g i,t , a g i,t ), (z g i , a g i ))], [K g i ] t1,t2 = k g i ((z g i,t1 , a g i,t1 ), (z g i,t2 , a g i,t2)).The Markov Property of Bayesian networks allows for a compact factorisation of the joint distribution of all observed nodes V = {V 1 , . . . , V m } in the Bayesian Network,EQUATIONThe joint distribution factorises into conditional distributions given its parents in the graph g.In the case of soft interventions any observed node V i is affected by its parents Z g i as well as the actions which appear as extra nodes in the SCM, we use A g i to denote the set of action nodes affecting node i therefore it is calculated asEQUATIONThe distribution factorises into conditional distributions for each variable, given its parents in the DAG and the associated actions for the node.GPs admit a closed-form expression for the marginal likelihood of the t observations v i,1:t of the node V i . p(v i,1:t |g, θ i ) can be calculated as belowEQUATION)where Kg i,θ = K g i,θ + ω 2 i I. The covariance matrix K g i,θ is given by the kernel k g i,θ used and observations collected until time step t (z g i,1 , a g i,1 ) . . . (z g i,t , a g i,t ), (z g i,1 ) . . . (z g i,t ) for soft and hard interventions respectively. The input space of the functions and hence the kernel specified is dependent on the selected graph. The lengthscales θ i = {θ i,j } i∈pag(i) chosen for different input nodes in the selected graph, determine the smoothness of the functions in the RKHS implied by the kernel. The lengthscales chosen for the kernel relate directly to the smoothness of the functions sampled from the GP [Berkenkamp et al., 2019] . We define priors θ i ∼ π(θ i ) over hyperparameters consistent with our smoothness assumptions.The Score is defined as Friedman and Nachman [2013] as S and is calculated as follows. The score shows the probability of the observed values of node V i is v i,1:t given the graph g and dataset D t-1 , where graph g indicates the parents of node V i is Z g i and actions A g i .EQUATIONTherefore the probability of observing data D t given g is given as the product of observing the values of each node in i ∈ [m] given the values of its parents according to graph gEQUATION)The probability of the graph g given D t is directly proportional to the product of the probability of observing the data given graph P (D t |g) and prior probability of graph g p(g) using Bayes Rule,EQUATIONA.5 Optimistic ReparameterisationActions are evaluated based on the topological ordering of nodes in a graph g. Finding the optimal value of the target node requires selecting the correct actions for all its ancestor nodes. This task is challenging due to two key factors. First, there is function uncertainty, meaning that for a given set of node values and a fixed action, the exact value of the affected node is not known but lies within a confidence interval. Second, the values of ancestor nodes, given actions up to node i in g, can vary.The optimistic reparametrization approach involves choosing values for these ancestor nodes within their confidence intervals in a way that allows descendant nodes to take on values that optimize the target node.For a graph g within the set of plausible models, the reparametrization trick from Curi et al. [2020] and used for CBO in Sussex et al. [2022] allows us to express any functionf g i ∈ fg ∈ M g t using η i,g : Z g i × A g i → [-1, 1] as f g i,t ( zg i , ãg i ) = µ g i,t-1 ( zg i , ãg i ) + β t σ g i,t-1 ( zg i , ãg i )η i,g ( zg i , ãg i ).The acquisition function can then be expressed in terms of η g : By selecting a sequence η g corresponding to actions a :,t , we can choose optimistic but plausible functions that maximize the target node for a given action. The objective then becomes finding the right sequence η g and the optimal action a :,t to achieve the best possible outcome given the current function estimates.Z g × A g → [-1, 1] |V (g)| ,In noiseless settings, instead of parameterizing each η i as a neural network, it can be parameterized as a constant. Without noise, the inputs to η i,g (z g i and a g i ) are fixed given a, reducing the parameter space to optimize. This allows us to use the optimization procedure from EIFN by Astudillo and Frazier [2021] , which is also implemented as an optimizer in the BoTorch package Balandat et al.[2020].For noisy settings where each η i,g : Z g i × A g i → R is parameterized as a neural network, we use our own optimizer. For each initialization of η parameters, we perform stochastic gradient descent to optimize both the η i parameters and the action a, leveraging the differentiability of the acquisition function with respect to both a and the η i parameters. After running stochastic gradient descent on many random initializations, we select the candidate with the highest acquisition function value. Since the acquisition function may be highly non-convex, we use a large number of random initializations.Alternative approaches, such as those in Curi et al. [2020] for model-based reinforcement learning, could also be adapted to optimize our acquisition function. When parameterizing each η i with a neural network, we use a two-layer feed-forward network with a ReLU non-linearity, followed by an element-wise Sigmoid function to map the output into [-1, 1].We operate under standard smoothness assumptions for any function relating any node to its parents f g * i - → S × V i isEQUATION)This is slightly different as compared to soft interventions, because a hard intervention mutates the graph, making the node independent of all ancestor nodes and interventions performed on them, thus simplifying the problem. This induces the notion of Minimal Intervention Sets MIS [Lee and Bareinboim, 2018] . A MIS for an SCM ⟨g, Y, V , f g , Ω⟩ is defined as the set of variables X s ∈ P(X)such that there exists no such X ′ s ⊂ X s for which E[Y | do(X s )] = E[Y | do(X ′ s )].Input: S i = {S(V i , Z i , A i |D t ), ∀(Z i , A i ) ∈ Z i × A i }, where i ∈ [m], g t = {}, De(m) = {}. function FINDSUBGRAPH(g, i, S i , De(i)) if i ∈ g then return g end if S c i = {S ∈ S i | Z i ∩ De(i) = ∅}, Sc i = { S S∈S c i S ∀S ∈ S c i }, (Z c i , A c i ) ∼ Multinomial( Sc i ) if Z c i = ∅ then g = g ∪ {i : (Z c i , A c i )} else g = {g ∪ {i : (Z c i , A c i )}, P a g (i) ∼ Uniform(Permutations(Z c i )) for j ∈ P a g (i) do De(j) = De(j) ∪ {i}, g = FINDSUBGRAPH(g, j, S j , De(j)) end for end if return g end function Output: g t = FINDSUBGRAPH(g t , m, S m , De(m))Causal Subgraph Discovery Our causal Subgraph discovery algorithm is used in both versions of the GACBO algorithm to sample from the posterior over graphs. The Graph discovery algorithm only focuses on components that are possibly ancestors of the target variables. It recursively samples graph components based on scores of the graph components for any given node. The given nodes are those of already sampled components closer to the target variable. We ensure acyclicity by excluding components that form a cycle with one or more of the already sampled nodes. We randomly sample the ordering of the parents of a node to determine their respective graph components.We illustrate an example of how making use of causal structure in soft or hard intervention cases can improve the optimization in Figure 5 . This example shows observing intermediate nodes is essential.Consider a modeller trying to optimize Y using A2, while ignoring the values of X1, X2, they would observe a lot of different values of y for the same action A2 considering that X1 can take on several different values, consequently affecting X2 and Y.Consider an investigator trying to optimize her crop yield, the crop could be dependent on several variables such as hours of daylight, soil moisture content, soil nitrogen content, temperature, rainfall, pest control, fertilizer use, crop rotation, irrigation practices, planting density, soil pH, weed control, climate conditions, genetic factors and so on.While she is aware of all the factors that are related to crop yield, the causal relations between these factors and the target variable are either unknown or partially known to her. Some of these factors are not directly manipulable like rainfall, soil moisture content, soil pH, and soil nitrogen content. However, they can be manipulated using soft interventions such as changing irrigation frequency or adding pesticides. For example, soil moisture would be dependent on both rain and irrigation practices, so even though we cannot directly set soil moisture content to our desired level we can manipulate it by changing irrigation practices.A2 X2 Y A1 (a) X2 A2 Y X2 Y X1 A1 A2 Y X2 Y X2 A1 (c-w1) X1 A1 Y X2 Y X2 A2 X1 Y X2 Y X2 (c) (b) (c-w2)Adding pesticides could be treated as a soft intervention on both soil nitrogen content and soil pH level. Both these variables might have a nonlinear relation to the amount of pesticide used.If by some mechanism we could set the soil pH to our desired value that would be equivalent to a hard intervention.By experimentation, she can manipulate the values of these variables discover the causal relations between them, and consequently design a policy that maximizes crop yield.A.9 Simulation Details A.9.1 Dropwave Surjanovic and Bingham [2013], Astudillo and Frazier [2021] , Sussex et al. [2022] For our setting we consider A 0 ∈ [-5.12, 5.12] and A 1 ∈ [-5.12, 5.12], we set β = 0.5 and ϵ i = 0.1∀i ∈ [m]EQUATIONResults GACBO outperforms all cases other than MCBO when the graph is known as apriori. We see a dip in performance in the initial rounds as expected, which are spent on graph discovery, however after the 20th iteration on all seeds the posterior is concentrated around the true graph and the performance matches that of MCBO.Jamil and Yang [2013] , Astudillo and Frazier [2021] , Sussex et al. [2022] For our setting we useEQUATIONResults GACBO matches the performance of other baselines in this environment. This behaviour is expected as Rosenbrock has an additive structure and causal graph knowledge does not help accelerate BO's performance. However as demonstrated in our experiments, MCBO with missing edges performs drastically worse as compared to all other methods demonstrating that utilising MCBO with a misspecified graph can result in bad performance.[Jamil and Yang, 2013 , Sussex et al., 2022 , Astudillo and Frazier, 2021] For our experiments we consider a i ∈ [0, 10], for i ∈ m, we consider β = 0.5 and η = 0.1 Results GACBO significantly outperforms MCBO with the wrong graph in both cases (extra and missing edges). The ToyGraph environment is incredibly noisy when intervening on non-parent nodes and therefore knowledge of the graph structure boosts performance.EQUATIONA.9.5 Epidemiology Branchini et al. [2023] Havercroft and Didelez [2012] In our settings, we consider the following input ranges for interventions T ∈ [0, 4] and R ∈ [0, 4], we use β = 1 and noise levels are specified according to the SCM.EQUATIONA.10 Causal Discovery and Causal Bayesian OptimizationCausal discovery from observational data [Verma and Pearl, 2022 , Andersson et al., 1997 , Spirtes et al., 2000 , Chickering, 2002 , Friedman and Koller, 2003 , Shimizu et al., 2006] can recover causal Janzing et al. [2012] go beyond MEC from purely observational data based on information asymmetry. Tong and Koller [2001] , Murphy [2001] , Eaton and Murphy [2007] , Hauser and Bühlmann [2014] , Wang and Jegelka [2017] , Ness et al. [2017] , Yang et al. [2018 ], Ghassami et al. [2018] , Agrawal et al. [2019 ], Faria et al. [2022] study the problem of learning graphs from observational and interventional data.Active causal discovery aims to learn the SCM efficiently. For example, von Kügelgen et al. [2019] studied causal structure learning actively using Bayesian Optimal Experimental Design (BOED). The acquisition function used in their model seeks to select the intervention that is maximally informative about the underlying causal structure with respect to the current model.Bayesian optimisation aims to learn the optimal point of unknown functions. Knowing the causal structure helps us reduce the causal intrinsic dimension of the optimisation problem for hard interven-tion. In the case of soft interventions, causal knowledge is useful for utilising the information from intermediate nodes and converting a high-dimension problem into n smaller dimensional optimisation problems (where n is the number of intermediate nodes).However, learning the entire SCM such as in active causal discovery (i.e., all the causal edges and mechanisms of all nodes in their entire domain) is not necessary for causal Bayesian optimisation. This is understood in two separate cases:Hard Intervention A hard Intervention mutates the graph, making the intervened node independent of all its parents and ancestors. Lee and Bareinboim [2018] demonstrated that the optimal intervention lies within the parents when there are no unobserved confounders. In such a case learning the causal relation between the ancestors of the parents does not help the underlying goal of causal Bayesian optimisation. Consider the example of ToyGraph, in the true data-generating mechanism X 1 is the parent of Y , and on performing do(X 1 = x 1 ) the value of Y is not affected by the value of X 0 , hence for optimization knowing the causal direction or mechanism relating X 0 and X 1 is not required.Soft Intervention A soft intervention does not mutate the graph, hence learning the causal relations of the ancestral nodes is still relevant to the downstream optimisation problem, however learning the entire causal structure might still be wasteful. If we have determined (specified by expert knowledge or during a certain step of our active causal discovery process that a certain node is not an ancestor of the target node, then knowing the ancestors or descendants of the node does not contribute to causal Bayesian optimisation. Causal structure in the case of soft intervention utilises values of intermediate nodes to constrain the optimisation problem. Causal structure is only useful when the decomposed problem is simpler than the original problem. For example consider function f (x 1 , x 2 ) = g(h(x 1 ), x 2 ), knowing the intermediate value h(x 1 ) is only useful if the composed function f is more difficult to optimise (because of non-linearity) than the individual functions g and h. We observe in our experiments with the Rosenbrock graph in Section ?? that there is no significant advantage of causal structure when the intermediate functions are purely linear.The goals of active causal discovery and Bayesian optimisation are misaligned. While Bayesian optimisation tries to balance exploration and exploitation to minimise cumulative regret, the active causal discovery acquisition function might choose an intervention that has a low reward and does not help future steps of causal Bayesian optimisation but helps discover the true underlying Causal Graph. Therefore it is sub-optimal to firstly perform active causal discovery and then followed by causal Bayesian optimisation as separate steps. Since the active causal discovery step might spend additional samples with low reward learning useless parts of the Causal graph.Our algorithm naturally unifies these two steps by making causal discovery a sub-task of causal Bayesian optimisation. If multiple causal graphs exist within our hypothesis space that explain the data collected up to time step t, we only perform an intervention aimed at disambiguation between these graphs if it potentially leads to better rewards than the optimal value observed thus far. Our acquisition function (2) has three maximisations, for a given graph g ∈ G t there are several plausible functions for each node f g i,t and all possible combinations of node functions define the function space for the graph g. We use the optimistic reparameterisation trick to find the combination of functions and actions a g which maximises the target node. We do this for all plausible graphs and compare the best possible value for each graph g. We select the plausible graph g with the maximum possible value for the target node and the corresponding action a g which maximises it. Consider a hypothetical scenario with two different graphs g 1 , g 2 which disagree on the value of node i for intervention a but the action which maximises the value of target node y g1 , y g2 in g 1 and g 2 is same a * , and the target node values also agree i.e., y * g1 = y * g2 for action a * , even though performing a would help identify the true graph our acquisition function is designed to choose a * . Because y g1 ≤ y * g1 or y g2 ≤ y * g2 for any action a ̸ = a * .The problem setting we addressed in this paper is challenging due to the super-exponential growth of the number of DAGs with the increase in the number of nodes. We only focus on small graphs where all the graphs can be enumerated to study the problem of CBO with unknown graphs in isolation.Our approach can be further improved to be more scalable, by MCMC-based sampling in the space of graphs Giudice et al. [2023] , or Differential approaches like DiBS Lorch et al. [2021] in latent spaces or topological ordering of nodes. We leave it as a future work.Our method in its current state computes the GP score of all possible graph components (all combinations of parents and actions for all observed nodes) and samples graphs based on the GP score and individually optimises and compares all sampled graphs. For larger graphs, the problem becomes intractable as the number of components for which the GP score needs to be calculated increases exponentially. In the initial rounds, the number of graphs that need to be optimised and the number of comparisons that need to be made also increases superexponentially. Causal Bayesian optimisation using the MCBO approach also takes longer for larger graphs.A.12 Discussion on Theoretical AnalysisOur approach suggests attaining a similar regret bound to MCBO but with an added constant term.However, our method holds the potential for a superior regret bound by simultaneously exploring the causal structure and exploiting rewards from the outset. Empirical results indicate that our algorithm, GACBO, exhibits a significantly faster increase in average rewards after initial rounds, underscoring its potential for improved regret. The lack of guarantees for the convergence of the posterior to the true graph in finite samples is a major obstacle. A potential theoretical proofing can be achieved by decomposing our regret into two parts:• Constant term: For the first n samples before learning the true graph, we obtain the constant regret. This is due to the boundness assumption of function (See section 2. O((K + q)(logT ) K+q+1 ) scales exponentially with respect to K and q the length of each action vector. This results in an expression that scales exponentially in K, N . The theorem demonstrates a potentially exponential improvement in the scaling of cumulative regret for possible actions m ≥ K + N .For environments allowing hard interventions, the optimisation problem can be reduced to the Causal Intrinisic dimension [Aglietti et al., 2020] if interventions on parents are allowed, Lee and Bareinboim [2018] shows results that the optimal intervention is always found among parents. For to Markov Equivalence Classes are further distinguished under the assumptions underpinning the GPN models, considering the functions f i , are not generally invertible [Giudice et al., 2023] , the GPN usually suggest higher scores to models admitting the true SEM structure as confirmed in our numerical experiments. For cases where functions are invertible [Hoyer et al., 2008] guarantees identifiability by leveraging the asymmetry of residual noise distributions. 
reward: 
 Apply BO on all plausible graphs g1 g2 g3 g4 g5 …. ing [Močkus, 1975 , Garnett, 2023] . Traditional BO methods [Srinivas et al., 2009 , Garnett, 2023] often treat functions as black boxes, but real-world data usually exhibits structural patterns. Causal Bayesian Optimization (CBO) methods [Aglietti et al., 2020 , Sussex et al., 2022 ] leverage these structures to improve sample efficiency. However,in many cases, causal graphs are either unknown or incorrectly specified. We address this by proposing a Graph Agnostic Causal Bayesian Optimization (GACBO) method that works with unknown or partially known causal graphs. Unlike previous methods [Branchini et al., 2023 , Alabed and Yoneki, 2022b , Toth et al., 2022] , which focus on hard interventions and simple regret, have a limited prior on graphs or target causal reasoning but not BO, GACBO handles both soft and hard interventions and aims to maximize cumulative rewards while learning the causal structure as needed. OurSubmitted to Workshop on Bayesian Decision-making and Uncertainty, 38th Conference on Neural Information Processing Systems (BDU at NeurIPS 2024). Do not distribute.approach balances exploitation (selecting actions with the highest potential outcomes) and exploration (uncertainty in function space or causal structure learning). Figure 1 illustrates our proposed method.We begin with a uniform prior over all possible acyclic graph structures, modeling surrogate functions for each target node's ancestors using Gaussian processes, with inputs being the node's parents and influencing actions. The Bayesian Score [Friedman and Nachman, 2013] models the probability of these graphs. At each iteration, we retain functions and graphs within high-probability confidence intervals, selecting interventions with a UCB-based acquisition function using the reparametrization trick [Sussex et al., 2022] . Our contributions are as follows: 1) We are the first to study causal Bayesian optimization with a cumulative objective in scenarios where the graph is unknown or partially known. 2) We propose a novel algorithm, Graph Agnostic Causal Bayesian Optimization (GACBO), that handles both soft and hard interventions and includes all possible graphs in the prior, effectively sharing information across different experiments through a model-based approach. 3) We introduce an Upper Confidence Bound-based acquisition function that integrates causal discovery as a subtask, engaging in it only when distinguishing between graphs improves outcomes, thereby balancing exploitation and exploration. 4) We demonstrate on synthetic and real-world causal graphs that our algorithm performs competitively compared to existing baselines. 
 
 Appendix:  



Reviews: review: title: title: Review for "Graph Agnostic Causal Bayesian Optimisation"
main_review: main_review: The paper proposes a methodology for selecting interventions in order to maximize an expected cumulative reward over $T  < \infty $ iterations, where relationships between variables (intervanable and non-intervenable) can be described by a causal graph so that causal effects can be properly defined. The causal graph and the SCM functions are unknown and priors are placed on these. 

The paper takes a potentially interesting direction that differs in (again potentially) interesting ways w.r.t. previous work, which is appropriately cited, but several things need to be clarified before it becomes a full, ready paper. In particular some things about how the graph posterior support is defined and the sampling over graphs is done is unclear/potentially wrong, and many formal assumptions are missing. 
I will put "Marginally above acceptance threshold" because this is a workshop, but I would not accept the methodology as is for a conference. 

Major comments 

- In Eq. 2 the posterior over graphs is not defined. There is not a unique way to define posterior over graphs. See for instance Kuipers, J et al 2022 regarding assumptions about parameter modularity etc. Assumptions should be made explicit (faithfulness, causal sufficiency, etc.) as well as their consequences. Also mentioning whether the posterior satisfies any type of Bernstein-von Mises property, or in what sense the posterior converges to the true (unknown) graph. This has consequences for of Eq. 2. that should be elaborated upon. Sample sizes required to learn the posterior over graphs in a suitable sense should be discussed, see e.g. Castelletti, F. et al 2024. 
- The definition of the plausible graphs should be justified much more in depth. Also most of this notation in Eq 3: $ \forall_i: \tilde{f}_i^{g} \in \mathcal{H}_k ,  | \tilde{f}_i^{g} |_k \leq \mathcal{B}_i  $ is undefined (am writing k instead of k_i because of rendering issues). Also very unclear why the plausible graphs change over time. How do you know you won't exclude the true graph over time ? Under what assumptions ? Also this means that you have a posterior over graphs with a support that changes over time ? This affects convergence of the posterior to the true graph (in any meaningful sense) for sure. 
- You should elaborate on how you propose to calculate (or approximate) the expectations / variances in Eq. 2. 
- Why are you * maximizing* over $g \in G_t $ and $\tilde{\boldsymbol{f}}_g \in \mathcal{M}_t^g $  ? You have posterior distributions over these, no ? It is very weird to maximize over the variable if you have a posterior over it ? Why are you not marginalising ? Again also changing the plausble graphs here affects the optimization problem a lot. And how would you maximize over the plausible set ? Nontrivial discrete optimization. 
- Is is unclear whether you are proposing a method for selecting both intervention *variables* AND *values* for those variables  as in Aglietti et al 2020 (or only values, which is a substantially easier problem)  

Minor comments
- $G_0$ in line 90 still undefined since definition of plausible graphs come later. 
- Line 63 should say in a topological order not "topologically" 
- Unclear why you consider *both* soft interventions and hard. Do they not require different treatment in your framework ? I may have missed a detail here. 
- The sampling algo for graphs, what is the computational complexity (space/time)? Why is it valid ? Why can you avoid graph MCMC as in, e.g., Kuipers and Moffa 2017 for example. 

Refs.
- Castelletti, F. and Consonni, G., 2024. Bayesian sample size determination for causal discovery. Statistical Science, 39(2), pp.305-321.
- Kuipers, J. and Moffa, G., 2017. Partition MCMC for inference on acyclic digraphs. Journal of the American Statistical Association, 112(517), pp.282-299.
- Kuipers, J., Suter, P. and Moffa, G., 2022. Efficient sampling and structure learning of Bayesian networks. Journal of Computational and Graphical Statistics, 31(3), pp.639-650.
title: title: Good contribution to the CBO literature
main_review: main_review: In this work the authors present an algorithm called Graph Agnostic Causal Bayesian Optimization (GACBO), which performs Causal Bayesian Optimization (CBO) with unknown graphs for the cumulative regret objective.

Section 3, where the authors detail their approach, is mostly written in a very concise and readable manner. A model over the SCM is maintained using what the authors call plausible models and plausible graphs, whose definitions make sense. This model is then used in the acquisition function which searches over the intervention space to maximize the reward variable.
The acquisition function being used makes intuitive sense, but it would be good to know why the authors choose to take the max over the plausible models and graphs instead of averaging over them.
In Equation 2, $\tilde{f}^g_{i,t}$ is introduced but described in Equation 6 - it would be good to relate them.

Results show that GACBO is a promising approach given that it assumes the DAG is unknown. This is especially clear when comparing GACBO to Model-Based Causal Bayesian Optimization (MCBO, which assumes the DAG is known) with the wrong causal graph. Given that the true causal graph is almost always not known, this an important result.

Figures 6,7,8,9 in the Appendix show the wrong graphs which were used for MCBO in the experiments, however the results may be more robust if the causal graphs were learnt using an off-the-shelf search based causal discovery algorithm (which would probably not give the true DAG) before being passed to MCBO.

Section A.11, line 548 suggests the authors are enumerating over the DAG space - in this situation it would be nice to know how $G_t$ changes over time.

Section A.13, line 612 - The choice of seeds raises questions, why were these seeds chosen? Do these seeds result in some assumptions being satsified? That being said, the transparency is good.

Small issues:
- How is $\delta$ chosen?
- Lines 314-319, and 523-528 are a copy-paste except for one paragraph saying Causal Bayesian Optimization and the other saying CBO.
- The paper uses the term mutated graph for the graph after a hard intervention is performed. I believe the exact terminology is mutilated graph, at least in Pearl's 2009 Causality book.
- Line 20: No space before citation.
- Line 27: No space after "However,".
- Line 58: Would be better to move part "... with each node $i \in [m]$ belong to a compact space $\mathcal{ V }_i \subset \mathbb{ R }$" after introducing $Y=V_m$. Also, as far as I am aware, $[m]$ refers to $\{1,\dots,m\}$, not $\{0, \dots, m\}$.
- Line 73: No whitespace between $0$ and $\forall$ - similar issue in Input of Algorithm 1.
- (Below) Line 84: The same term $R_T$ is used for both soft and hard interventions, also missing an equation number.
- Algorithm 1: $a$ is not bold in 3rd line inside for loop.
- Line 105: Missing . after A.6.
- (Below) Line 107, Equation 4: $\forall_i$ instead of $\forall \: i$.
- Line 434: X and Y are not in LaTeX math, also Figure 5 caption.
- Line 481: no space after [...2023]
- Line 513: Bracket not closed.
- Line 521: Reference error.
- Line 579: log