Model-based Causal Bayesian Optimization
Authors: Scott Sussex
Anastasia Makarova
Andreas Krause
Venue: ICLR 2023 notable top 25% (2023)
Keywords: causal inference
bayesian optimization

Abstract: How should we intervene on an unknown structural equation model to maximize a downstream variable of interest? This setting, also known as causal Bayesian optimization (CBO), has important applications in medicine, ecology, and manufacturing. Standard Bayesian optimization algorithms fail to effectively leverage the underlying causal structure. Existing CBO approaches assume noiseless measurements and do not come with guarantees. We propose the {\em model-based causal Bayesian optimization algorithm (MCBO)} that learns a full system model instead of only modeling intervention-reward pairs. MCBO propagates epistemic uncertainty about the causal mechanisms through the graph and trades off exploration and exploitation via the optimism principle. We bound its cumulative regret, and obtain the first non-asymptotic bounds for CBO. Unlike in standard Bayesian optimization, our acquisition function cannot be evaluated in closed form, so we show how the reparameterization trick can be used to apply gradient-based optimizers. The resulting practical implementation of MCBO compares favorably with state-of-the-art approaches empirically.

Published as a conference paper at ICLR 2023
MODEL-BASED CAUSAL BAYESIAN OPTIMIZATION
Scott Sussex
Anastasiia Makarova ETH Zürich
Andreas Krause
ETH Zürich
ETH Zürich
sws.tt.suseeeiin..cco etw.ee..ceeeeee.cchhh.hc
ABSTRACT
How should we intervene on an unknown structural causal model to maximize downstream variable of interest? This optimization of the output of a system of interconnected variables, also known as causal Bayesian optimization (CBO), has important applications in medicine, ecology, and manufacturing. Standard Bayesian optimization algorithms fail to effectively leverage the underlying causal structure. Existing CBO approaches assume noiseless measurements and do not come with guarantees. We propose model-based causal Bayesian optimization (MCBO), an algorithm that learns full system model instead of only modeling intervention-rewart pairs. MCBO propagates epistemic uncertainty about the causal mechanisms through the graph and trades off exploration and exploitation via the optimism principle. We bound its cumulative regret, and obtain the first non-asymptotic bounds for CBO. Unlike standard Bayesian optimization, our acquisition function cannot be evaluated in closed form, show how the repa- rameterization trick can be used to apply gradient- based optimizers. Empirically we find that MCBO compares favorably with existing state-of-the-ard approaches.
INTRODUCTION
Many applications, such drug and material discovery, robotics, agriculture, and automated ma- chine learning, require optimizing an unknown function that is expensive to evaluate. Bayesian optimization (BO) an efficient framework for sequential optimization of such objectives (Močkus) 1975). The key idea in BO is to quantify uncertainty in the unknown function via probabilistic model, and then use this to navigate trade-off between selecting inputs where the function output favourable (exploitation) and selecting inputs to learn more about the function in areas of uncertainty (exploration). While most standard BO methods focus on a black-box setup (Figure I a), in practice, we often have more structure the unknown function that can be used to improve sample efficiency.
In this paper, we exploit structural knowledge in the form of a causal graph specified by directed acyelic graph (DAG). In particular, assume that actions be modeled interventions structural causal model (SCM) (Pearl (209)) that contains the reward (function output) as a variable (FigureT While we assume the graph structure be known, consider the functional relations in the SCM as unknown. All variables the SCM are observed along with the reward after each action. This Causal BO setting has important potential applications, such optimizing medical and ecological interventions (Aglietti et al., 2020b). For illustrative purposes, consider the example of agronomist trying to find the optimal Nitrogen fertilizer schedule for maximizing crop yield, described in Figure [ There, the concentration of Nitrogen in the soil causes its concentration in the soil at the later timesteps.
To exploit the causal graph structure for optimization, we propose model-based causal Bayesian optimization (MCBO). MCBO explicitly models the full SCM and the accompanying uncertainty of all SCM components. This allows our algorithm to select interventions based on an optimistic strategy similar to that used by the upper confidence bound algorithm (Srinivas et al. 2010). We show that this strategy leads to the first CBO algorithm with a cumulative regret guarantee. For a practical algorithm, maximizing the upper confidence bound in our setting is computationally more difficult, because uncertainty in all system components must be propagated through the entire estimated SCM to the reward variable. We show that an application of the reparameterization trick allows MCBO be practically implemented with common gradient-based based optimizers. Empirically,

---

Published as a conference paper at ICLR 2023
Bayesian Optimization
Causal Bayesian Optimization
a1
X1
Xo
Y
a2
X2
Y
C11
a22
a3
X3
(a)
(b)
Figure 1: visual comparison between the modelling assumptions of BO vs CBO. Circular nodes represent observed variables, squares represent action inputs and Y is the reward. Algorithms select before observing and Y. (a) In standard BO, the DAG has the structure shown regardless of the problem structure. (b) The DAG corresponding to our stylised agronomy example, where we aim maximize crop yield Y. CBO takes this DAG as input for designing actions. Xo is an unmodifiable starting property of the soil, and XI...X X3 are the measured amounts of Nitrogen the soil different timesteps. Each observation modelled with its own Gaussian process. a1 ....... ag are possible interventions involving adding Nitrogen fertilizer to the soil.
MCBO achieves competitive performance on existing CBO benchmarks and related setting called function network BO (Astudillo & Frazier 2021b
Contributions
We introduce MCBO, model-based algorithm for causal Bayesian optimization than can be applied with very generic classes of interventions.
Using MCBO we prove the first sublinear cumulative regret bound for CBO. We show how the bound scales depending on the graph structure. We demonstrate that CBO can lead to potentially exponential improvement in cumulative regret, with respect to the number of actions, compared to standard BO.
By an application of the reparameterization technique, we show how our algorithm can be efficiently implemented with popular gradient-based optimizers.
We evaluate MCBO existing CBO benchmarks and the related setting of function network BO. Our results show that MCBO performs favorably compared to methods designed specifically for these tasks.
BACKGROUND AND PROBLEM STATEMENT
We consider the problem an agent interacting with an SCM for T rounds in order to maximize the value of particular target variable. We start with introducing SCMs and the kinds of interventions an agent can perform on an SCM. In the following, we denote with [m] the set of integers {O.....m)
Structural Causal Models An SCM is described by a tuple Y, F. Ω2 of the following ele- ments: g is known DAG; Y is the reward variable of interest; X {X, J is set of observed random variables; the set
( defines the functional relations between these variables; and Ω {S,). is set of independent noise variables with zero-mean and known distribution.
We use the notation Y and X,, interchangeably and assume the elements of X are topologically ordered, i.e., X, is root and X,, is leaf. We the notation pa, C {O...., mm) for the indices of the parents of the äth node, and Z, = (X,}eepau for the parents of the ith node. We sometimes X; refer both the ith node and the ith random variable.
2

---

Published as a conference paper at ICLR 2023
Each X, is generated according the function f: Z, X, taking the parent nodes Z: of X; as input: x; = fz,) + w/s where lowercase denotes a realization of the corresponding random variable. The reward is a scalar Im E R. An observation X; is defined over compact set 2; E &, C IRd, and its parents are defined over 2; = IIEppa 23 for E [m 1].
Interventions At each interaction round, the agent performs an intervention on the SCM. this work, we consider two types of intervention models.
We consider a soft intervention model (Eberhardt & Scheines 2007 where interventions are parameterized by controllable action variables. Let A, C. Re denote the compact space of an action a, and be the space of all actions a = {a,) We represent the actions as additional nodes in (see Fig. I]: a, is parent of only X;, and hence an additional input to fi. Since f. is unknown, in our soft intervention model, the agent does not know apriori the functional effect of a, on X,. A simple example of soft intervention is shift intervention æ; (z a.) +w; w; g=(z))++ + a; aa; for some function gi. A shift intervention might occur in our example of adding Nitrogen fertilizer to soil and then measuring the total soil Nitrogen concentration.
While our theoretical results will focus on data obtained via soft interventions, our experiments also consider two other data sources. First, we consider hard intervention model: hard interventions (often referred to as do-interventions) modify the targeted variable to specific distribution inde- pendently of the variable's 's parents. For example, a doctor sets the dosage of a patient's s medication, which fixes the dosage to specific value (Aglietti et al., (2200). Second, special case under both intervention models is the collection of observational data, which when no intervention is performed on the system. In the soft intervention model, not intervening on node is equivalent to setting a = 0. An example would be not applying any Nitrogen fertilizer to the soil. In practice, the agent may have access to some previous observational data before its first interaction with the system. In the following, we introduce the problem setup under the soft intervention model and then adapt it to the hard intervention model.
Constraints on interventions In many applications, we may not be able to intervene on all nodes simultaneously. For example, farmer may only have the capacity to apply fertilizer at two out of three possible time windows in Fig. 1 This results in an action space with cardinality constraints, written
m
{a:) 3
Σ
1 10 S Sc
Problem statement We consider the problem of an agent sequentially interacting with an SCM, with known DAG and fixed but unknown set of functions F (ft with f: 2, x A, - X4- At round we select actions a., = {ar,)) h and obtain observations æ = { i=o where we add additional subscript denote the round of interaction. The action a,,, and the observation Ti are related by
Zt,t (z at,e) + Wi,t Vie [m]]
i corresponds to a root node, the parent vector z denotes an empty vector, and the output of fo only depends on the action aięt- Since we cannot intervene on the target variable Xms we fix am = 0. The reward is given by
Vt = fm am,1) + Wm.t.
(3)
which implicitly depends on the whole intervention vector a.,- We define the action that maximizes the expected reward by
a' = arg max [y]a],
(4)
a
where, unless otherwise stated, expectations are taken over noise w.
Performance metric Our agent's goal is to design a sequence of interventions {a. that achieves high average expected reward. We hence study the cumulative regret (Lattimore & Szepesvári] 2020) over time horizon T
T
RT
Elyla"| Elyla..]
(5)
3

---

Published as a conference paper at ICLR 2023
A sublinear growth rate of Ri with T implies vanishing average regret: RT/T - 0 as T As an alternative to cumulative regret, one can also study the simple regret Elyla*] - The most appropriate metric depends on the application. In the Nitrogen fertilizer example. cumulative regret might be preferable because we care about obtaining high crop yields across all years, not just in one final year.
Index notation Let iitt [.........,, ........,,,,..d denote a vector where æ1,,, indicates indexing the component 1 E [d] of the ith timepoint of the observations at the node i E [m]] For functions with vector output, e.g., f: : 2; + X, we sometimes consider notation with additional input to fa that indicates the output dimension: fi(2. a) = [fi(z, a, a)1)................. .,,. a, d))²
Regularity assumptions We consider standard smoothness assumptions for the unknown functions ft : + Xr defined over a compact domain S (Srinivas et al. 2010). In particular, for each node i E [m], we assume that f:(.) belongs of smooth functions defined on = 2, x A; This means that fa E He, is induced by a kernel function k; : $ x $ + I where $ = S x [d] We also assume that ks(),'') S 1 for every s. E Moreover, the RKHS norm of f-) is assumed to be bounded [|lall I B, for some fixed constant B, > 0. Finally, to ensure the compactness of the domains 2,, we assume that the noise w is bounded, i.e., wi E [-
reproducing kernel Hilbert space (RKHS) HA. space
Problem statement under hard interventions Under a hard intervention model, instead of select- ing an action in Eq. (4) the agent must select both a set of intervention targets / E I C P([m 1I) and their values a1 E A E A. For hard intervention we can rewrite Eq. (2) as
a. (z; + ww otherwise,
ifeel
x;
Vi E [m],
where fi is unknown and employs the same regularity assumptions. Further constraints similar to Eq. (1) can be placed on either the intervention nodes I or action values aj. Finally, observational data corresponds to the empty intervention set = 0.
2.1 RELATED WORK
Optimal decision decision-making in SCMs has been the subject of several recent works, for example, in the bandit setting (Lattimore et al. 2016 Bareinboim et al. 2015). Aglietti et al. (2020b) introduce causal BO (CBO) focusing on hard interventions. CBO considers unobserved confounding and uses the do-calculus to estimate Y given I, a using both observational data and interventional data with the same intervention targets 1. Aglictti al. (2020a) extend CBO to make use of data obtained from hard interventions with different intervention targets. While both methods use do-calculus to estimate causal effects, they do not learn the full system model. Branchini et al. 2022) and AAlaedd] & Yoneki (202)) extend these works to explore the CBO setting in the case of unknown DAG.
Function network BO (FNBO) (Astudillo & Frazier 2021b) is similar to the CBO setup with soft interventions and the proposed algorithm uses an expected improvement acquisition function to select actions. MCBO generalizes the FNBO setup richer class of problems since the causal model formalism allows for modelling hard interventions. Moreover, in contrast to MCBO, FNBO assumes the system is noiseless which might be restrictive assumption in practice. Kusakawa et al. (202T) study stochastic function networks in the special case of a chain graph. Similar to MCBO, they develop a UCB-based acquisition function and provide an accompanying cumulative regret guarantee. However, they do not employ a reparameterization trick to show how to optimize the acquisition function. Kusakawa et al. (2021) do not perform any empirical study of the proposed UCB-based method, but evaluate expected improvement and credible interval methods
I For vector-valued functions coming from an RKHS we consider a scalar-valued function where the output index is part of the function input, as deseribed in Curi ct al. (2020) Appendix F.
This is known as the bounded variance property, and it holds for many common kernels.
'This assumption can be relaxed to being nab-Gausiian using similar techniques to Curi et al. Appendix I. Though sub-Gaussing noise includes distributions with unbounded support, Curi al. 2020
2020
provide high probability bounds on the domain of 2,.
4

---

Published as a conference paper at ICLR 2023
also developed for the chain graph setting. Both FNBO and CBO are part of wider research direction on using intermediate observations from the computation of the unknown function to improve the sample efficiency of BO algorithms (Astudillo & Frazier 2021a).
In concurrent work, Varici et al. 2022) consider a similar setup and prove cumulative regret guarantee for UCB-based algorithm with soft interventions. However, they focus only linear SCMs and a binary action space for each intervention target, while MCBO applies to non-linear SCMs and continuous action space.
The function class studied in this paper is similar to that of deep Gaussian processes (GPs) (Damianou & Lawrence 2013) in that MCBO models Y composition of GPs given Deep GPs, however, do not make use of intermediate system variables and do not compose GPs according causal graph structure.
Our use of the reparameterization trick to practically implement an upper confidence bound acqui- sition function (Srinivas et al. 2010) MCBO is inspired by Curi al.) (2020), who apply ideas from BO to design an algorithm for sample efficient reinforcement learning.
3 ALGORITHM
In this section, we propose the MCBO algorithm, describing the probabilistic model and acquisition function used. We first introduce MCBÓ under the soft intervention setup and then describe how to adapt it to hard interventions.
Statistical model
We use Gaussian processes (GPs) for learning the RKHS functions fo..... fm from observations. Our regularity assumptions permit the construction of confidence bounds using these GP models with priors associated with the RKHS kernels. more background on the relation between GPs and RKHS functions. For all [m]] let 1i:0 and of denote the prior mean and variance functions for each f. respectively. Since is bounded, it is also subgaussian and we denote the variance by p.. The corresponding posterior GP mean and variance, denoted by fs,t and of, respectively, are computed based on the previous evaluations D: 12 C,,1:t; ). In particular, for each function f defined by the given kernel h; and output component
refer to Rasmussen (2003) for
pi,((z,, ai, = ku,(zz, a; [K, (vec(aa)))
o2, as, 1) k; ((zz, az (Zi, (4;1)) (i, ai . [,,(KKK
ai,
(8)
&reddl and for where denotes the identity matrix, vec( = [04.1,1, 24.1,, Rrsdd (t1,l), (tz, E [11, (1,2). (t]d)]:
KK) (K)) = (, ai,t, I); (Ziga, ait,,, 11)), (2,,(z;,,,11
[k; ((2,1111 1,11, 1); (z,, a. I)),..., ky ((z,,,d as,,,d, d); (z,, a, T))
We write μige Juce(( 1),.... ., (- d))" and similarly for di,t. We give more background on the posterior updates of vector-valued GPs Appendix A.1
At time the known Mr of statistically plausible functions F = (f (functions that lie inside the confidence interval given by the posterior of each GP) is defined as:
M₁ F (f s.t. Vi: f. Hk.s |ffele, S B,,
(9)
and f((z), pite- ai) Bi an), Vz, 2,, a E Ai).
Here, 3r. is a parameter that ensures the validity of the confidence bounds. Some examples of concentration inequalities under similar regularity assumptions well explicit forms for 3 can be found in Chowdhury & Gopalan (2019) and Srinivas et al. (2010). In the following, we set Bit = B, for all such that the confidence bounds in lqq. (9)are still valid.
5

---

Published as a conference paper at ICLR 2023
Algorithm Model-based Causal BO (MCBO)
Require: Parameters {31 {51 9, Zt kernel functions k; and prior means M4,0 Vi E [m]
1: for = ....... do
2: Construct confidence bounds in Eq. (9)
3: Select de E arg aa ma) Egy (f) a) as in Eq. (12)
4: Observe samples {2i,1, 2i, Fe=D
5: Use D, to update posterior {MLL (.), o (.) as in Eqs. (7) and (8)
6: end for
Algorithm 2 Model-based Causal BO with Hard Interventions (MCBO)
Require: Parameters {B,)22 G, S2 kernel functions k; and prior means 14,0 0 Vi E [m] 1: for t- = 1, .... do
2: Construct confidence bounds in Eq. (9)
3: Select I, a, arg 1igma,,,,, max, E (f do a;]]
4: Observe samples { Li,t Ji=0
5: Use D, to update posterior (M o
in Eqs. (7) and (8)
6: end for
Acquisition function At each round f, interventions are selected based on maximizing an acquisi- tion function. Our acquisition function is based on the upper confidence bound acquisition function (Siinvas et al. 2010). That is, we optimistically pick interventions that yield the highest expected return among all system models that are still plausible given past observations:
a. arg max max Ew F
(10)
aeA FEM.
Note that Eq. (10) is not amenable commonly used optimization techniques, due the maximization over set of functions with bounded RKHS norm. Therefore, following Curi et al. (2020), we use the reparameterization trick to write any f: E FF MM using a function 77, 11, as:
(11) where 0; fi(E,, ā.) + W denotes observations from simulating actions in of the plau- sible models, and not necessarily the true model. denotes the elementwise multiplication of vectors. This reparametrization allows for rewriting our acquisition function in of A [1, 1]
fr, ā.) = (2, a.) + B.o 12; a:) ni (2,,
0g arg max max Ens [y] aa. s.t. F- (fe Eq.
(12)
aEA
7(.)
Intuitively, the variables v allow for choosing optimistic but plausible models given the confidence bounds. In practice, the function 7) can be parameterized by, for example, a neural network, and then standard optimization techniques are applied. For the theory, we assume access to an oracle providing the global optimum for Eq. (12) In practice, such an oracle may be computationally infeasible due to non-convexity hqq (12) We discuss heuristics that we use for approximating this oracle in Appendix A.3
Algorithm summarizes our Model-based Causal BO approach. We note that for the special case of the SCM following the DAG of Fig. Ta), our algorithm and the associated guarantees reduce to standard BO (Srinivas et al. 2010).
Hard interventions MCBO also naturally generalizes to hard interventions (Algorihhm 2). In experiments, we perform the combinatorial optimization over the set of nodes Z by enumeration because [Z] is not large for the instances we consider. We apply the notion of a minimal intervention set from Lee & Bareinboim 2019) to prune sets of intervention targets that contain redundant interventions, resulting in smaller optimize over.

---

Published as a conference paper at ICLR 2023
4 THEORETICAL ANALYSIS
This section describes the convergence guarantees for MCBO under a soft intervention model, showing the first sublinear cumulative regret bounds for causal BO. We start by introducing additional technical assumptions required for the analysis.
Assumption (Functional relations). All fi E F are Ly-Lipschitz continuous.
Assumption (Continuity). Vi,t, the functions Mi,e, oi,t are Lus La Lipschitz continuous.
Assumption (Calibrated model). All statistical models are calibrated w.r.t. F, so that Vi, there exists sequence 3r E Ryo such that, with probability at least (1 8), for all 2i, a, E Z, x A, we have (z; a.) 1 a.) S 3 a,). element-wise.
Assumption T follows directly from the regularity assumptions Section 2 Assumption Seniipttionnnoolle holds if the RKHS of each fi has Lipschitz continuous kernel (see Curi et al. (2020), Appendix G). As- sumption 2
restricts the convergence guarantees soft interventions that affect their target variable in smooth way, meaning that our analysis does not directly apply to the hard intervention model. We nevertheless experimentally demonstrate the effectiveness of MCBO in non-smooth settings, such as CBO with hard interventions. Assumption B holds when we assume that the ith GP prior uses the same kernel as the RKHS of f; and that B. sufficiently large ensure the confidence bounds in Eq. hold.
In the DAG over nodes {X;}== let N denote the maximum distance from a root node to Xm: N max; dist(X; Xm) where dist(.,)) -) is measured as the number of edges in the longest path from node X; to the reward node Xm. Let denote the maximum number of parents any variable in G: K max; |pa(i)). The following theorem bounds the performance of MCBO in terms of cumulative regret.
Theorem 1. Consider the optimization problem in Fgg. (4) where G is known but F is unknown. Then for all T 2 1, with probability at least d, the cumulative regret of Algoriihhmm iis bounded by
with SCM satisfying Assumptions 1
RT S LL B my TT))
Here, YT = max; 7iT where the node-specific Ki denotes the maximum information gain a time 7 commonly used in the standard regret guarantees for Bayesian optimization (Srinivas et al.) 2010). This maximum information gain is known to be sublinear in T' for many common kernels, such linear and squared exponential kernels, resulting in overall sublinear regret for MCBO. We refer to Appendix A.2.3 for the proof.
Theorem demonstrates that the of the graph structure in MCBO results in potentially exponential improvement in how the cumulative regret scales with the number of actions m. of the graph structure, results in cumulative regret exponential in m (Srinivas et al. 2010), when using a squared exponential modeled with squared exponential kernels that model output
Standard Bayesian optimization in Fig. (a), that makes
kernel. When all X; in MCBO components independently, we have pr (dd K Kd + (log T" kd+o+1), resulting in a cumulative regret that exponential in K and exponential in N. However, note that 2 K + N. For several common graphs, the exponential scaling in N and K could be significantly more favorable than the exponential scaling in m. Consider the case of having the binary- tree-likk structure in appendix Fig. 3) (binary tree), where N log(m)) and K = 2. In such settings, the cumulative regret of MCBO will have only polynomial dependence on m. We further discuss the bound in Theorem for specific kernels in Appendix A.2.3 and discuss the dependence of Br T in Appendix A.2.4
5 EXPERIMENTS
In this section, we empirically evaluate MCBO on six problems taken from previous CBO func- tion network papers (Aglictti et al. 2020b; Astudillo & Frazier 2021b). The DAGs corresponding to each task given in Fig. of the appendix. We provide open-source implementation of MCBC
https://gi thtp:///tttttttt./ wwt.:thh......tttt.ett wwt.s////tes//c//oooooo
7

---

Published as a conference paper at ICLR 2023
TroGrophs Avenge Reward
PSAGraph: Averago Roward
Ackley: Averge Rewand
16-
Average Reward
1.4
Averrage Rowward
-55
Averaage Rewward
1:0
-5.0-
1.0
MCDO
MCBO
MCBD
0.6
EICBO
-5
EIFN
ETFN
GT UCB
0
30
60
100
20
60
100
20
60
90
100
Round
Round
Round
Dropwwse naisy: Averag Rewvard
Reeembrock, noiey: Average Reward
Alpine2, noisy: Averago Reward
0.5
200-
Average Revward
6.4
Averrae Roseard
-500
Average Rewward
150+
-750
100
6,3-
MCBO
MCBD
024
EIFN
-1500
EIPN
BIFN
GP-UCB
-1750
GP UCB
0
20
60
100
70
Round
100
20
201
80
100
Round
Round
Figure 2: (a, b) EICBO does not achieve monotonically improving average reward on CBO tasks, while MCBO achieves high average reward on both tasks. (c) On the noiseless Ackley function networks task, EIFN also does not achieve monotonically improving average reward. (d, e, f) On a range of noisy function networks tasks, MCBO is good and often higher performing than EIFN and GP-UCB baselines.
Baselines We compare our approach with three baselines (i) Expected Improvement for Function Networks (EIFN) (Astudillo Frazier (021b); (ii) Causal Bayesian Optimization (EICBO) (Agli etti et al. 2020b): and (iii) standard upper confidence bound (GP-UCB) (Srinivas et al. (010)) which models the objective given interventions with single GP (see a)). To enable a fair comparison, we only apply EICBO to the hard intervention setting, since it was designed specifically for a hard intervention model.
Experimental setup We report the average reward function of the number of system inter- ventions performed. The average reward at time T is defined by Σr [Y a.]] and is directly inversely related to cumulative regret in that high average expected reward is equivalent to low cu- mulative regret. This matches the performance metric studied in our analysis. Average expected reward and cumulative regret are natural metrics for many real applications, like crop management, in which we want consistently high yield, and the healthcare-inspires setting we study in these ex- periments, where we seek good treatment outcomes for more than a single patient. In the appendix, we show experiments measuring the best expected reward of any action previously chosen, which is more similar to an inverse of the simple regret. We report mean performance over 20 random seeds, with error bars showing + 0/v 2/v20 /20 where a is the standard deviation across the repeats. All figures that are referenced but not in the main paper can be found in the appendix.
For the guarantees in Theorem 1 to hold, {B must be chosen so that the model is calibrated all time-stpss as in Eq. (9), In practice, we select a single such that 8 3. Vt. Choosing too pessimistically will result in high regret, as demonstrated by the dependence of the guarantee on 3.V For GP-UCB and MCBO, 33 chosen by gross-validation across tasks, as described in the appendix.
Toy Experiment First, we evaluate on the synthetic ToyGraph setting from Aglietti et al. (2020b). ToyGraph is hard intervention CBO task where I {0, (0), {1)]. All methods start with 10 observational samples and samples from 2 random interventions on each E I. When EICBO obtains interventional data, it obtains noiseless samples because it is not designed for the noisy setting. By noiseless samples, we mean that for action a EICBO observes E., [Y a). Other methods obtain single samples from the distribution Y, X a.
8

---

Published as a conference paper at ICLR 2023
In ToyGraph, / {1} is the optimal target, but to efficiently learn the optimal [()) the agent must generalize from both observational data and interventional data on other targets / = {0). EICBO models Y given az with a separate GP for every / and consequently only able to make use of observational data and interventional data with the same target. Since MCBO learns full system model, it incorporates all observations into the learned model, even when interventions do not match.
Figure (a) shows that the average reward of MCBO (Algorithm 2) is favorable compared to the baselines. Both baselines are built on expected improvement, which will continue to explore even after high-reward solutions are found. This explains the oon-onnoooiic average reward of EICBO.
Healthcare Experiment PSAGraph is inspired by the DAG from a real healthcare setting (Ferro et al., 2015) and also benchmarked by /Aglietti et al. (2020b). The agent intervenes by prescribing statins and/or aspirin while specifying the dosage to control prostate-specific antigen (PSA) levels. Here I {0, [2). [3], (2.3) 3}} and all interventions are hard interventions. Initial sample sizes are the same as for ToyGraph. Figure 2
(b) again shows EICBO having a nonmonotonic average reward and strong comparable performance of MCBO.
Noiseless Function Networks In addition to the hard intervention setting, we evaluate MCBO and the baselines on four tasks from Astudillo & Frazier (2021b). All systems have up six nodes and varying graph structures. In function networks, actions can affect multiple system variables, and system variables can be children of multiple actions. Function networks are deterministic, so O. MCBO (Algorithm 1) can be applied directly in this setting, and the guarantees are also easily transferable. Like in Astudillo & Frazier (202 lb), there are no constraints (besides bounded domain) on actions, and the agent is initialized with 2AA + samples from random actions, where A is the number of action nodes.
Figure 2 (c) and Figure (abb.c) show that MCBO achieves competitive average reward on all tasks. EIFN is better on Dropwave. Mcanwhile, MCBO is substantially better than EIFN on the Ackley and Rosenbrock tasks. Overall, there are not sufficiently many tasks established in the literature to conclusively say which properties might make a task favor EIFN over MCBO. However, this would be interesting to understand in future work and likely relates to the wider conversation in BO comparing expected improvement and UCB algorithms (Merrill et al., 2021). We find that the naive GP-UCB approach, which does not use the graph structure, generally performs poorly, especially on problems with larger graphs like Alpine2. On Ackley, EIFN does not achieve monotonically im- proving average reward, which is not unexpected given that is based upon expected improvement.
Noisy Function Networks We modify three of the function networks settings to include an additive zero-mean Gaussian noise every system variable, making w non-zero. EIFN is designed for deterministic function networks and has no convergence guarantees in this setting. Results in terms of average (Figure 2 f.e.f) and best reward (Figure glg g, h, i) are comparable to the noiseless case, with MCBO and EIFN both performing well compared to GP-UCB.
6 CONCLUSION
This paper introduces MCBO, principled model-based approach to solving Bayesian optimization problems over structural causal models. Our approach explicitly models all variables the system and propagates epistemic uncertainty through the model to select interventions based on the optimism principle. This allows MCBO to solve global optimization tasks in systems that have known causal structure with improved sample efficiency compared to prior works. We prove the first non-asymptotic convergence guarantees for an algorithm solving the causal Bayesian opti- mization problem and demonstrate that its theoretical advantages are reflected in strong empirical performance. Future work might consider how to apply the method to large graphs, where the sets of all possible discrete intervention targets cannot be efficiently enumerated.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
We thank Lars Lorch, Parnian Kassraie and Ilnura Usmanova for their feedback and anonymous reviewers for their helpful comments. This research was supported by the Swiss National Science Foundation under NCCR Automation, grant agreement 51NF40 180545, and by the European Re- search Council (ERC) under the European Union's 's Horizon grant 815943.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Virginia Aglietti, Theodoros Damoulas, Mauricio Alvarez, and Javier González. Multi-task Causal Learning with Gaussian Processes. In Advances Neural Information Processing Systems (NeurIPS), 2020a.
Virginia Aglietti, Xiaoyu Lu, Andrei Paleyes, and Javier González. Causal Bayesian Optimization. In International Conference on Artificial Intelligence and Statistics (AISTATSS, 2020b.
Sami Alabed and Eiko Yoneki. BoGraph: Structured Bayesian Optimization From Logs for Expen- sive Systems with Many Parameters. In Proceedings of the 2nd European Workshop on Machine Learning and Systems, 2022.
Raul Astudillo and Peter I Frazier. Thinking inside the box: A tutorial on grey-box bayesian opti- mization. In 2021 Winter Simulation Conference (WSC). IEEE, 202
Raul Astudillo and Peter I. Frazier. Bayesian Optimization of Function Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021b.
Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson, and Eytan Bakshy. BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Elias Bareinboim, Andrew Forney, and Judea Pearl. Bandits with unobserved confounders: causal approach. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Nicola Branchini, Virginia Aglietti, Neil Dhir, and Theodoros Damoulas. Causal entropy optimiza- tion. arXiv:2208. 10981, 2022.
Sayak Ray Chowdhury and Aditya Gopalan. Online learning in kernelized markov decision pro- cesses. In International Conference on Artificial Intelligence and Staristics (AISTA7S). 2019.
Sebastian Curi, Felix Berkenkamp, and Andreas Krause. Efficient Model-Based Reinforcement Learning through Optimistie Policy Search and Planning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Andreas Damianou and Neil D. Lawrence. Deep Gaussian processes. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2013.
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of sci- ence, 74(5):981-995 2007.
Ana Ferro, Francisco Pina, Milton Severo, Pedro Dias, Francisco Botelho, and Nuno Lunet. Use of statins and serum levels of prostate specific antigen. Acta Urológica Portuguesa, 32(2):71-77, 2015.
Shunya Kusakawa, Shion Takeno, Yu Inatsu, Kentaro Kutsukake, Shogo Iwazaki, Takashi Nakano, Toru Ujihara, Masayuki Karasuyama, and Ichiro Takeuchi. Bayesian Optimization for Cascade- type Multi-stage Processes. arXiv preprint, 2021.
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interventions via causal inference. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Sanghack Lee and Elias Bareinboim. Structural causal bandits with manipullllll variables. In AAAI Conference on Artificial Intelligence, 2019.
Erich Merrill, Alan Femn, Xiaoli Fern, and Nima Dolatnia. An empirical study of bayesian optimiza- tion: Acquisition versus partition. Journal of Machine Learning Research, 2021.
Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization Techniques, 1975.
Judea Pearl. Causality. Cambridge University Press, 2009.

---

Published as a conference paper at ICLR 2023
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pp. 63-71. Springer, 2003.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimiza- tion in the bandit setting: No regret and experimental design. In Proceedings of International Conference on Machine Learning (ICML)), 2010.
Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Causal bandits for linear structural equation models. arXiv preprint arXiv:2208. /2764, 2022.
12

---

Published as a conference paper at ICLR 2023
A APPENDIX MODEL-BASED CAUSAL BAYESIAN OPTIMIZATION
A. BACKGROUND ON GPs
Here we give more background on the vector-valued GP models we use. We will drop the i-node index and consider the modelling of single function with scalar output f : A x Z + IR in RKHS + R where S (2 x A). We assume measurement noise with variance p². Assuming prior mean and variance Ao, Th and dataset D, = fzı:1 a1:t. F1a where I, E R, we get a posterior GP mean and variance given by updates
Hy with kernel k:
Me(z. a) kz(z, a) (Ki + p²1)
(13)
(z,za)) - -k((z,)); (z, k) (K, (21+
kı(z,a),
(14)
where
(Ki)tt,t2 k(Ez, at, )i (Ztz: aiz)); kx(z,a) = [k((21, an) a).......
...., k((z,, az); (2,
and I is the identity matrix. This follows the standard GP update given in Rasmussen (2003).
In this work, we model functions with vector-valued outputs Ax + X Rd (we will continue to drop the i index). For this we follow Chowdhury & Gopalan (2019) and use a scalar-output GP that takes the component of the output vector under consideration as an input. That is, model ((:))) (the Ith output component of the function under study) where f = [f(. d)]. We again assume that f is from RKHS Hy but with kernel k : S x S + I where S = (Z x A x [d).. Assuming prior mean and variance No: Tu and dataset De {a1., x1.1} where I2 E R we
get a posterior GP mean and variance given by updates
Mr(2, = (2, a,1) 1)_ (K, + - vve((an.))
(15)
o2 a,) k<(z,, a, 1): 1)) 1, a, [K, + "
(16)
where vec( (1 ................................ a and for (1,,0, 12) E [(1, 1), (1,2)......
..... (1,
[K. (1) = k(( ard 1); (Zi,,' "r, "r,)), 1'), (z,z,,1)) = [k: (Z.11 a1,1, 1); (z, a, I)), .... (((z,, a d); (2,
This follows the posterior update of Chowdbury & Gopalan 2019). The key idea is to single scalar-output GP with kernel i for modeling all output components, but introduce the component index as part of the input space. This requires introducing the notation vec(m1:)) and ordering all observations, of all time points and all components, in a single index, since the GP update for component ( considers observations of all other components. Under this GP model the components of f need not be independent if kernel k is designed to model dependency between the components. In our work, we use one of these vector valued GP models for each individual random variable in our causal model, leading to the reintroduction of the additional i index in Eqs. (7) and
A.2 PROOFS FOR THE THEORETICAL ANALYSIS
Our analysis closely follows Curi et al. (222)), particularly the proofs in their Appendix D, where they prove similar guarantees for a model based reinforcement learning problem. In contrast to Curi jet al. (200)), which models RL transition dynamics with a single GP for all timesteps, MCBO uses independent GPs for modeling the functional relation {fi...., Jm.....,). and uses the causal graph G to determine the input and output variables of these functions.
This section is organized as follows. In Appendix 1.2.1 we discuss notion of model complexity I'r similar to the one introduced in the RL setting by Curi et al. (2020). We then bound the cumu- lative regret in terms of T in Appendix A.2.2 Finally. in Appendix A.2.3, we prove Theorem 1 by connecting our notion of model complexity with the maximum information gain of a GP model.
The norm notation I|||| refers fo-m if no additional notation is given. We let far. E A Zi,1 Z, Jusn denote the set of actions chosen by MCBO and the realizations of the parents of node i, respectively.
13

---

Published as a conference paper at ICLR 2023
A.2.1 MODEL COMPLEXITY
The number of samples needed learn low-regret action is related the number of samples needed to learn all GP models in our SCM. This is analogous to the classic BO setting (Srinivas) al. 2010). We quantify the model complexity of our entire model class Mr
TT
max
ΣΣ 1
(17)
(5xx)
This measure of model complexity closely relates to the maximum information gain "Yr used for proving regret guarantees in BO (Srinivas et al. 2010). For single GP model, YT the maximum information gain about the unknown f that can be obtained from noisy evaluations of the f at fixed inputs (see Eq. (39). Later we show that T can be bounded by a sum of the information gains for all m GPs. is worth noting that Equation 17 may be loose notion of model complexity because it assumes we can independently choose every 2i. but for many graphs, there could be overlap in the 24, 2j for i (two nodes could have shared parent).
A.2.2 ANALYSIS IN TERMS OF GENERAL MODEL COMPLEXITY TT
In this section, we will prove theorem similar to Theorem but in terms of the model complexity we define in Eq. (17) Note that this version of the theorem does not require that μ and or come from GP model with independent outputs, but any model such that Assumptions 1 are satisfied. In later sections, when using a GP model we bound Fr in terms of the maximum information gain of the m GPs used to get TThorem
We will use the function E-,(() to represent a matrix all zeros except the values the diagonal, given by (-). A result, (.)((.) diag (E),(-))
Theorem 2. Consider the optimization problem in Eq. (4) with SCM satisfying Assumptions 1 where G is known but unknown. Then, for all
with probability least 6, the regret
of Algoritth Dis bounded by
R S OO K N VTmTT
We first sketch the proof steps. In Lemma I show that with, high probability, there exists some set of functions 7 that allows the reparameterized plausible SCM model in Eq. (1T) to match the true SCM. Recall the mechanism of the ground-truth SCM in Eq. (2)
Fi f(z,,, a.,)) + Witt Vi E {O....,m),
and the mechanism of the optimistic SCM model using the reparameterization of Fg. (11)
Bi, fi (i.)) Wi.t
(18)
= -1 ās,e) + 1,, ān.)) (.,,) ) W Vi (o....,m).
(19)
In Lemma 2 Lemma 3 and Corollary we bound the instantaneous regret (regret at some specific timepoint t) by bounding the difference in SCM output, for the same action input, assuming the true SCM vs the optimistic reparameterized SCM. Then in Lemma 5) the intermediate result of
Lemma 4 to show that our bound on instantancous regret implics bound on cumulative regret.
In Lemma for convenience,
will drop the explicit dependence of all quantities t.
Lemma 1. Assume some fixed set of actions a is chosen at any timepoint t. Under Assumption 3 8 there exists set of functions n {mp) where n:: 2, A: [1, such that x = & if Vi Wü
for any æ generated by the true SCM Eq. (2) with probability at least
Proof. Since w e we only need to prove that there exists some such that Vi f( a,) = (4(2, ā.) BE, a:).i
14

---

Published as a conference paper at ICLR 2023
By Assumption 3 with probability 8, for all 0, ................................ m, we have elementwise bound [f( a.) - (2 a:)l I (,0,( as,e). Thus for each 2i,e, at,, there exists a vector 7) with values in |-1,1] 1] such that fz a.) = (2 a,) + _E, a, Mr. Note that this not quite what need because the RHS contains and not ž.. We will now use inductive argument on i that constructs each 7) sequentially from i = 0 to m.
Base case: must prove that for 0 we have (z au) mu a.) + B, Eu (uu a.) no. We know Za = &o (both are the empty vector) and a = a by the assumption there exists some vector dJo such that (z an) n zo, ao) + (g ao vo)voo 10 Eo. ao) + (2g, ao) 77- Let (.) be the function that outputs the vector no given input 20: Og and the base case is proven.
fixed action. Then
Now assume the inductive hypothesis: Vj < i we have We want show that this implies (i,, a.) (2 a;) + (2, a. We know a, a; and we plaa]] [mm[]l))......[[mmm]]]]
(1, aj) (Zj, āg) Mn
by the assumption of a fixed action. 2; 2, because 2; = [_pp,[1]......
selected each such that éj = Zj- Then there exists some vector vi such that fi a,) = (z,, a,) + (2, a.))m: = (,, ā.) + (E, ā.)) Let mi(-) output the vector n, given input 2,, a; and the inductive step is proven.
Lemma 2. Under Assumption 3
with probability at least (1 5) Vt z the instantaneous regret
Tt. is bounded by
Tt Ely F, a") B BlylF,a..1
FL, a..)
TEyl F, a..e]-
(20)
Proof. The result follows directly from,
Ely|F, a") < E Elyler, a..]
(21)
This is true by the definition of Fe, a, as the argmax Eq. (12) and that with probability at least (1 have F E Mr-
We now show how the observations under the true and optimistic dynamics differ for fixed noise sequence u w and the fixed action Ojjt at any time
Lemma 3. Under Assumptissn / let I. = 1 L + 2,, Then, for all iterations > 0, any functions ny RP: X R
1,1 and any sequence of w; with w, = w; (for all i), we have
m
|mm, Sm,ell 28,K
1 ax,))l
(22)
Proof. We prove by induction on i.
Base case. Consider the base case i O. Because the nodes are topologically ordered we will have pao 0. Its realization, therefore, depends only the chosen action. Formally, assume zo 0.
2o fo an) + wo and To fo āo) + Wo. Since wo
Wo.
| T || (Z0,1, ) Wo,t 1 ax,e) Br E,, au, a0.) ao.1) Wull < [l (zo,t, ao.z) 1o,t-1 ( 0l || + 1 (
ao.:)l
2,, Eo,-1120..1 ao.:)l
In the following, we omit the dependence on the action a, e.g., using fz(,)) instead of fi ax,)) since we assume the actions be the same for the process generating Ti,t and ø.,t-
Induction step. Now assuming that || - prove a similar result for the ith node.
N.- - 2.-1, < 23, N.-1 L E (Z we
[[fa(zi,)) witt (3..) ( W.ell
15

---

Published as a conference paper at ICLR 2023
(lf((z))) (82.::)))))8.........000........ f( f((2,))
(f(()))) p4,11 (Z),) - -
- 14 + 1 2a (1 - f(
6 Bel 0 | x.,l
28, 20, + |, 2,,e|
28. 01,-0 - 0 1 + L E,,el
1 23, (100,,-1(z..))
Lo | - 2r,e1l + L L &s,ell
23, 23.101.1-(21::))
Ly 2., || Ei,ell
28 (1 L + 2z)
Σ
|| - T.,e
jEpa:
28.(oo,1-1(Eu)))
+ (1 L, + 28,Lo)
+
E
23, N, (1 L + 23 )
Σ
(
jEpas
=:
h=0
23. N
(23)
where ① follows the dynamics Eqs. (2) and In 2 we assume the noise to be equal and add and subtract the same term. In and we reorder terms and apply the triangle inequality. In s and O)) we rely on the calibrated uncertainty and Lipschitz dynamics, then collect terms and use diagonality of the matrix i (-). In and +) we add and subtract the same term and use the Lipschitz continuity ,, Finally, in we add to ensure that we can later upper bound this follows the inductive
term by taking the exponential of it. applies the triangle inequality.
hypothesis, and is due to the depth of least one parent j being N, = -N-1.
Li
Now we will relate this bound on the observations to bound on yr when selecting actions according MCBO in both the optimistic and true dynamics.
Corollary 1. Under the assumptions Le 3 for any sequence of n) [[1, 1]44 0 E DD and t 2 we have that
T72
Fr. a.
Ely a. 28,K L.
(24)
Proof. This follows from Lemma
Y just the final observation so
yc F., a..
E F. a..]
B[]|@m, Zm. alll [..e]
m
23,K M.N.E E
16

---

Published as a conference paper at ICLR 2023
Lemma 4. Under Assumption 3 for all t. 2 0 that
let Ly,
2.
Then, with probability at least (1 - 6) it holds
r $ K mE Σ 1l (2,,,,
(25)
Proof.
r2 S E8 W/ Fr, 0r
- Elys F; asl
(26)
< 28,k L E
1 (2 anlill
(27)
1=0
s Ly,KK NE
1 axDi
(28)
1==0
2
m
r S L3 ,22K2N 2N
E
o (2,,) ar,1)l
(29)
27
m
5 k2ccK2N
o (Zi,z, ai,r)
(30)
m
$ K2 mE
1 (z,, 1 01.1
(31)
The last two lines are Jensen's inequality.
Now we bound cumulative regret Rr.
Lemma 5, Under the assumption of Assumptions
with probability at least (1 8) it holds for
all 2 0 that
T
R2 <
TL
TL
E
|| o
(2i,,, ai..) 2
(32)
1=0
Proof.
R2
Σ [ml
T
<
TL
Y
m
E
(33)
where ① is due to Jensen's inequality and ④ follows Lemma 4 Similar to the equivalent lemma in Curi et al. 2020), this bound is dependent on the data observed by the iteration t, making hard to interpret in general case. To this end, further provide the worst-case bound dependent on the model complexity Ty. Lemma 6. Under Assumptions 1
with probability at least (1 - 8) it holds for all t 2 0 that
R2 < &TLY, KNN ml'
(34)
Proof. Substituting Eq. (17)
we have
T
(z,,, )112 < STr
E
(35)
t=1
and the result follows.
Taking square roots and substituting in for Ly.r in terms of Br, Lg and Lg in Eq. (34) concludes the proof for Theorem
17

---

Published as a conference paper at ICLR 2023
A.2.3 PROOF OF THEOREM 1
We can bound I' Theorem to get a bound that depends on the specific GP model used for each fi We can show that for many commonly used kernels MCBO achieves sublinear (in 7)) regret.
Theorem 1. Consider the optimization problem in Eg. (4) with SCM satisfying Assumptions 3
where G is known but F is unknown. Then for all T Z 1, with probability at least d, the cumulative regret of Algorithm iis bounded by
Rr S B my TT)).
Proof. Step 1. Some preliminaries relating mutual information IT (TIIIT StAe)) and maximum information gain "T
In the following, we consider the information gain for the node i, i.e. for I1,1TT E R2xT and fI,IT [fi a..i)...., (ZZ,TT d.,T)! evaluated e points A, {ZL1:T, ai,1:T), A; 2, x A:. In this step, for simplicity, when clear from context we will omit the i-notation in the derivation for the information gain. Mutual information Ir (XI.T, fir)) then defined as:
1 fir)) H (2I.T) H1 (#irIfi: (fir))
where H()) denotes entropy. For fitting the GPs, the following models are used: atlft ~ (f. (z, az), p² and Iy 21--11 21:1, aidt (i at). I at)), where I Baxd and
Nt- (Z,, at) = [M- (Ze, at, 1), Ur (z,, d)]T, O 12 a,) =
ar,
(z). a.)) = 100-1(21 a₁ (t..1),.....1 ar dt,))
Our setup assumes that the components 1 are independent of each other given ž,, dg. There- fore from Srinivas et al. (2010) we know that the mutual information for the ith GP model is:
d
of oi oi-1(z,, ac.
Manr, fu.) = H(n..))) H(
In 1
(36)
because per component:
T
of o- ac.l) a..))
I( f(rr.) 2
In 1+
(37)
p²
1=1
Then, by the definition of maximum information gain N.r, per node in the graph:
1 T
Σ In 1 of oi, ar,
max f.N.T)))
max A:C (2 2
A:C x2
p²
1=1
(38)
Accordingly, we can write the maximum information gain between 2;,1:T and fú,1TT as follows:
Σ In (1 1+
T d
o2 (Z,, az,
N.T =
A:C
max (
I(ELII frAT))
max A.C (2ixA1)
T 2
p²
tml 1=1
(39)
1 T
In (1 1
2
12, a1,l)
[=1 A.C
max (Z
2
p²
B.T.
(40)
t=1
Note: Bounds for T and N.T Upper bounds on N.T. are provided in Srinivas et al. (2010)
for widely used kemels and scale sublinearly in T. We use p: (() to represent the size
18

---

Published as a conference paper at ICLR 2023
of the z-input to GP. Recall that q is the length of each action vector i.c. A, C R7. For the linear kernel N = (p:: + q) log T), and for the squared exponential kernel NtTu = O + (log T))++ We can use Eq. (39) to give bounds on Ri too e.g. if all GPs use independent linear kernels for each output component 7, (p: log and if all GPs use independent squared exponential kernels for each output component R.T = O(d(p; + (log T)++++)).
Step 2. A bound for model complexity TT.
Here we bound the model complexity Eq. (17)
1
TT
In(1 Pi 2 N..
(41)
For readability, in the following, we denote max(.)
max
(-).
A: A= AC(2(x.))))
Tr- max
0
21 a:)
(2x
i=0
T
max
0
a;) 21
max
(0;,-1(2;; a:)1
k=0
t=1
T
m
T
d
max
(2
a.)
max
10,(tt-)(22= a, a, 1)13
A
A
[=1
O
1=1
1=1
m
o2 (Zi, ai,l)
max- A;
In
In(1 + Pi
p
1=1
maximum information gain
Eg. (39)
(mrr),
R.T
In(1 +
where c bounds A and 2 with a box. ④ is from the max over sum. a is due to the assumption of Li being independent of Aj..j # i, conditioned on As. is is due to Jensen's inequality. is due to
the fact that for any 82 E [0, 2] we can bound 82 < In(1-p-2] In(1+ Srinivas et al. (0010). This also holds for function (-) = P; 20? ()) since P;
2 ().-1) P, k(.,) S P. because
(.) < 1 Vi (bounded kernel assumption). ( is due to Eqg. (36)and and (39) Finally, in 2 we define
Pr max; Yir being the maximum value the maximum information gains over graph nodes.
Plugging this upper bound on Pr into Theorem 2 completes the proof.
Note: Sublinearity w.r.t of maximum information gain "Y.
Upper bounds on will often scale sublinearly in T. This follows from Yir scaling sublinearly in T for many popularly used kernels (see previous note). In particular, lin- ear kernel leads to Yr O (d(Kd + q) log T)) and squared exponential kernel leads to Tr O (d(Kd + (log T) kddg+1) (assuming output components are independent) since max; P;- kd.
A.2.4 DEPENDENCE OF 3T ON FOR PARTICULAR KERNELS
Note that for Assumption 3 to hold under our RKHS assumptions, By might depend on T. For a single observed variable corresponding node i time i, for Assumption to hold must have BT Ô (B. (1,)) (Chowdhury & Gopalan 2019) equation 9). For Assumption 3 to hold
19

---

Published as a conference paper at ICLR 2023
time t for all i apply union bound and see that it is sufficient for BI Ô (B V() where max; B; and p max; Ps.
In the regret bound of Theorem 3T appears raised the power N. For "r corresponding to the linear kernel and squared exponential kernel, this will still lead to sublinear regret regardless of N because "Yr will be only logarithmic in T. However, for Matérn kernl,, where the best known bound Yr = O (p(pT))log(pT)) with 0 < c < 1, the cumulative regret bound will not be sublinear if N and e are sufficiently large. A similar phenomena with the Matérn kernel appears in the guarantees of Cf et al. (2020) which use GP models in model-based reinforcement learning.
A.3 MAXIMIZING THE ACQUISITION FUNCTION
Our theoretical results assume access to an oracle that can maximize Eq. (10) Here we discuss how we approximate this oracle in practice.
In noiseless settings, instead of parameterizing each v); as a neural network, we can parameterize constant. This is because with noise, the inputs to my (z; and a,) given are fixed. This keeps the space parameters to optimize over small, meaning we can use an identical optimization procedure to that used in EIFN by |Astudillo & Frazier (2021b) which is also an out-of-the-box optimizer in the BoTorch package Balandat et al. (2020).
For noisy settings where each 77: A, Z, - IR is neural network, use our optimizer. For each initialization of y7 parameters, we perform stochastic gradient descent to optimize both the n,; parameters and We can do this because Eq. (12) is differentiable with respect to both a and the parameters of each Vy. After running stochastic gradient descent on many random initializations we will have many solution candidates. We select the candidate with the highest acquisition functioon value. We use a large number of different random initializations because the acquisition function may be very non-convex. Other approaches, such as those considered in Curi et al. (2020) for model-based reinforcement learning, could also be adapted to optimize our acquisition function.
When parameterizing each n7 with neural network, we always use a two layer feed-forward net- work with ReLu non-linearity, To map the output into [-1,1] we put the output of the network through an element-wise Sigmoid.
In all noisy environments we estimate the expectation in the acquisition function Eq.. (12) using a Monte Carlo estimate with 32 repeats for each gradient step. For noisy Dropwave we use 128 repeats because the environment is particularly noisy compared to other noisy environments.
A.4 EXPERIMENTAL SETUP
Here we give additional notes to explain the details of our experimental setup.
The cross cooss-validttion for selecting 3 is performed across 3 f0.05, 0.5, 5). For given performance metric and task, we'll use the example of average reward on Dropwave, we select the B that on average performs best across all other tasks for the same performance metrie, called 3*. We then report the results in terms of average reward for running the algorithm (GP-UCB or MCBO) on Dropwave with B 3
For MCBO and EIFN, we use identical values for all shared hyperparameters (e.g. GP kernels) and use the original hyperparameters from Astudillo & Frazier (2021b). CBO methods do not have hyperparameters comparable with these methods because CBO methods do not model individual system observations (see Section 2.1 We run the original BICBO source code effectively unmod- ified Aglietti et al. (2020b).
For CBO tasks, if the agent selects no intervention (ohservational data) at given timestep, we give the agent, for any algorithm, single observational sample. This is different to in Aglictti et al. (0200b where 20 observational samples are given.
There is no noisy version of Ackley because adding noise can make the environment unstable by producing very large or very small rewards. For all environments and all X,, the noisy environment adds miitGaaussian noise, except Dropwave where scale this noise by 0.1 to make the environ- ment more stable.
20

---

Published as a conference paper at ICLR 2023
PSAGraph
Dropwave
X1
40
ToyGraph
X4
Y
Xo
y
Xo
X3
Q1
X
Y
Alpine2
Rosenbrock
Qg
1
Q
Q3
Q4
45
Q4
Xo
X1
X2
X3
X1
X
XI
X2
binary free
Ackley
a1
4g
X
Xo
X
X1
00
01
02
0.3
01
05
Y
Y
X
Xs
XI
43
X3
415
Figure 3: The DAGS corresponding to each task in the experiments, except binary tree which is used for illustrative purposes. Circles are observation reward variables. Squares are actions in the function network setting. hard intervention CBO, nodes with a dashed border can intervened upon. All nodes represent scalar random variable.
Dropmave: Average Reward
Rosembouuicc Averuge Rewpard
Alpine2: Average Reward
300
Average Roeeart
-006
Avtrgger Reveard
-750
150
6.4
100k
633
024
EIEN
-1500
BIFN
BIPN
GP-UCBB
-1254
20
40
100
30
Roumd
Round
Round
Figure 4: All average reward plots not used in the main paper. All settings are noiseless.
When applying MCBO to function networks we allow to be nonzero, to match the function networks setting.
21

---

Published as a conference paper at ICLR 2023
TroGroph: Avenge Reward
PSAGraph: Average Roward
Arkley: Averge Rewanl
1.-
1.4-
Average Reward
Avernage Rowward
Average Reeward
1.2
-3-
L--
-5.0-
68-
MCRD,
MCRD, , 0.05
MCRO, 0.36
MCBO, 8 0.3 MCBO, EIPN
-67-
MCBO, , 0.5
MCDO, 8 0.5
MCBO,
-5-
MCBO,
DIFN
DIFN
-0-
0
30
60
100
0
20
C0
100
20
60
90
100
Round
Round
Round
Dropwave: Averape Reward
Roseaboock: Average Reward
Alpine2: Average Reward
064
200
Average Reeward
Averaaee Roweard
Average Rewward
644
-50
100-
0.3
MCDDO ,5 ILGG MCRO,
MCBO,
MCBD, 8 0,5
MUBO,
2000
MCDO, 3
50-
MCDO, 2 0.5
MCBO,
KIPN
-3500
BIEN
EIFN
6.3
0
20
60
100
70
Round
100
20
80
100
Round
Round
Dropwnsee noisy: Average Reward
Roeenbrock, noiey: Average Reward
Alpine2, noisy: Average Reward
Average Reeoard
Aveeuge Rewoard
Average Romwurd
150
2000
2004
MCBO, 0.00
1200
MCBO,
MCDO,
MCBO. / 0,5
MCBO, , 0.5
MCBO. - 0,5
MCBO,
-3000-
MCRO, .-
MCBO.
RIPN
EIFN
0
20
Roumd
60
100
20
Round
100
20
4n
Round
80
101
Figure 5: An ablation across 33 where we plot average reward for all tasks.
A.5 FURTHER EXPERIMENTAL. ANALYSIS
Average expected reward
In Figure 4 we show the deterministic function networks plots not included in the main paper. In Figure we show the average reward for all / considered the cross-validation.
Best expected reward Here we also report the best expected reward as function of the number of rounds T. The best expected reward at time is defined by
max [Y a). (a.)
This is similar to but not directly inversely related to simple regret. Simple regret algorithms require an inference procedure to select final action after T' rounds of exploration. This procedure could be computationally expensive for the CBO setting. For example, a reasonable choice would be to report a final action based upon maximizing a lower confidence bound of the objective in Eq.. (4) however a closed form expression for this does not exist for CBO. Best expected reward instead assumes access an oracle that computes the highest expected reward of any action the algorithm has previously chosen, Our plotting the best expected reward is consistent with previous work on CBO (Aglietti et al. 2020b).
When performing the same cross-validation procedure as for the average expected reward case, we find that the performance of MCBO varies drastically across tasks. This is shown in Figure 6 Selecting 3 is known to be a difficulty with UCB-based method (Merrill et al., 2021). Figure 7 shows the performance in terms of best reward for all 3 possibilities for B. When selecting just
22

---

Published as a conference paper at ICLR 2023
TreGraph: Best Reward
PS.Graph: Best Reward
Ackley: Bes Reward
04
3.0
-6.2-
Bes Reward
1.-
Dest Rewwndd
Best: Permurt
-533
18-
1.1
MCDD E
0.67
MCBO
MCBO
ETFN
GT GF-UCB
0
30
10
60
100
0
20
C0
100
20
60
90
100
Round
Round
Round
Dmppvave: Best. Reward
Resmbbokk Best Reward
Alpine2: Best Reward
300-
Bext Reward
Reward
1000
Best [eeward
6.4
200
MCBO
31CBO
100
MCBO
6.4
EIFN
-500
EIE
BIFN
GP-UC1
GP-UCB
GP GP-UCB UCB
0
20
Found
60
100
6
30
60
Round
69
100
20
in
Round
80
100
Dropwwwee, noley: Best Reward
Roseubrock, polsy: Best Reward
Alpine2, noisy: Best Reward
300-
Beo Rewart
6.7
Resoard
100-
Best Resward
664
900
0,54
-000
MCBO
SCCBO
MCBO
0.4
EIFN
EIEN
EIFN
6.3
GP-TCR
-500
GP-UOB
GP-UCB
0
20
40
60
100
20
4n
80
100
Roumd
Round
Round
Figure 6: All best reward plots.
the best | among the tried, we find that MCBO is very strong on all tasks (with the exception of best reward ToyGraph, where it underperforms the baselines). The optimal B can vary by an order magnitude or more across tasks in our case. This likely because all of our settings have very different functional relationships and graph structures. As discussed in Section 4 this can be understood from our cumulative regret guarantee in Theorem
The plots of average and best scores for other values of B Figs. and 7 suggest that 3 can be made larger for MCBO to trade-off exploration vs. exploitation depending on whether simple or cumulative regret more of a priority. Meanwhile, expected improvement methods are focused almost almost entirely on exploration.
Runtimes In Figure g we show the total runtime of each method for all 100 rounds. EIFN and MCBO run on equivalent hardware, which has 4 times more ram than the hardware used for GP- UCB and EICBO. MCBO generally has much longer runtime than EIFN in noisy settings where the are parameterized by neural networks. Generally in BO, because the unknown function is often assumed expensive evaluate, we are less concerned about the time required optimize the acquisition function and more concerned with notions of statistical efficiency such as regret. Our implementation for noisy settings could likely sped-up with more parallelism to make more comparable to EIFN runtimes. In noiseless settings, where the optimization methods used are roughly equivalent between EIFN and MCBO, the two methods have comparable runtimes.
Non-monotonic regret of EICBO In Fig. 2 (a.b) we found that EICBO had non-monotonic av- erage reward, which could likely be explained by the use of an expected improvement acquisition function. We decided to clarify that the non-monotonic average reward was because of the algorithm and not because of differences in our setup compared to Aglietti et al. (2020b). Besides us evaluat-
23

---

Published as a conference paper at ICLR 2023
TraGraph: Best Reward
PSrGraphh: Best Reward
Ackley: Best Reward
2.0
-5.2
Bes Reward
Dest Rewwand
Best: Rerurrd
1.8
0.16
MCRD, -00.5
MCRO,
MCBD, 8 0,5 MCBO,
MCBO, 9- 0.5
MCDO, 8
0.5
MCBO,
MCBO,
14-
EIPN
DIFN
DIFN
-5.5
0
30
60
100
0
20
C0
100
20
60
80
100
Round
Round
Round
Dmpovave: Best Reward
Revebook Best Reward
Alpine2: Best Reward
200-
Bext Reward
Dest Reward
1000
Best [eeward
0.6
200
MCBBO, A 0.06 MCBO,
MCBO,
6.4
MCDO, 8 0-0. 0,3
MUBO,
-000
MCDO, 8
100
MCDO, 2-
MCBO,
EIPN
EIFN
EIFN
0
20
Round
60
100
6
30
60
Round
69
100
20
in
Round
80
100
Dropwwwee, noley: Best Reward
Roseubrock, boley: Best Reward
Alpine2, noisy: Best Reward
300-
Best Rewart
62-
Resoard
100-
Best Resward
68-
900
0.5-
MCBO, 8 0,5
MCBO, 0.00
-000
MCBBO, J 3.5
MCBO. - 0,5
MCDO,
0.4
MCBO,
MCDO,
MCHO,
RIPN
-50
BIFN
EIFN
6.5
0
20
40
6o
100
20
4n
80
100
Roumd
Round
Round
Figure 7: An ablation across 3 where we plot best reward for all tasks.
PSAGrope: Total Roatine
Alpine2: Total Rustime
Alpine2, noley: Total Runling
400K0
15000
Total Ramtie (acsstck)
Thtall Runline (accmul))
Total Runtime (provtdds)
12300
15000
10000
30000
2309
10000
2309
10000
3CCB
EIPN Algoritim
GP-DCB
Alpotithan
Alwotttim
Figure& 8: Runtimes of experiments for a a) CBO setting, b) noiseless function network setting, and c) noisy function network setting.
ing in terms average reward instead of best reward, compared to Aglietti et al. (020b) we also used smaller initial sample sizes (random samples the agent obtains before t 0) of observational data. This was to make the setting more challenging, since we found that with extra observational data ToyGraph and PSAGraph could be solved with very few samples. When reproducing the periments of Fig. 2 (a, b) with additional starting observational data, we found the same qualitative results (non- montonontni))iy) for the average reward case. Note that this result is not inconsistent at all with the experimental results of Aglietti et al. 2020b), since they only evaluate in terms of best reward.
24


Reviews:
[{"review_id": "n0PV7Ggvhbp", "reviewer": "Reviewer_B1mp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new algorithm for causal Bayesian optimization for both hard and soft interventions with theoretical guarantees. The authors use a reparameterization technique to optimize the acquisition function which is a maximum over functions. They empirically show that the algorithm mostly outperforms relevant baselines.", "summary_of_the_review": "I believe this paper has potential. Theoretical guarantees are important and the experiments show that their algorithm performs well in comparison to baselines. However, unless I am mistaken, the paper suffers from non-trivial technical issues. Assumption 3 as presented is already very strong but actually needs to be even stronger to properly achieve a sublinear regret bound. The definition of the GP posterior mean and variance is not well-defined and hinders understanding of their method. Until these issues are addressed, I am hesitant to recommend acceptance.\n\nPOST-REBUTTAL UPDATE: The authors have satisfactorily answered the main technical concerns and have improved the paper. I have improved my score to recommend acceptance.", "strength_and_weaknesses": "Strengths:\n1. The problem of causal BO is motivated well and explained clearly with diagrams.\n2. The algorithm's performance is empirically well-supported.\n\nWeaknesses:\n1. One concern comes from Assumption 3 not providing an explicit formula for the sequence $\\beta_t$. The authors claim that there is an \"overall sublinear regret for MCBO\". However, $\\beta_T^N$ appears in the regret bound, where $N$ is the maximum distance from a root node to the reward node. Without an explicit formula for $\\beta_t$ (as is usual in this line of work), there is no reason to believe that  $\\beta_T^N < \\mathcal O(\\sqrt{T})$. Even if we assume that the usual formula for $\\beta_t$ (Chowdhury and Gopalan, 2017) is applicable, we still have that $\\beta_t = \\mathcal O(\\sqrt{\\gamma_{t-1}})$. For the Matern kernel, $\\gamma_T = \\mathcal O(T^{d(d+1)/(2\\nu + d(d+1))} \\log T)$ (Srinivas et. al., 2010). Thus, if the Matern kernel was used, there would be some value of $N$ beyond which the regret bound is not sublinear. Assumption 3 needs to be even stronger than it currently is for the sublinearity claim to be true. Ideally, the authors could provide an explicit formula for $\\beta_t$ instead of assuming such a sequence exists, or at least discuss why constructing such a sequence would be hard.\n\n2. Each $f_i$ is a vector-valued function modelled by a vector-valued GP. However, the vector-valued GP as presented in this paper does not match with the usual understanding of a vector-valued GP. From Sec. 3 in Alvarez et. al. (2012) (https://arxiv.org/pdf/1106.6251.pdf), vector-valued GPs have matrix-valued kernel functions $\\mathbf K: \\mathcal S \\times \\mathcal S \\rightarrow \\mathbb R^{d \\times d}$. However, this paper's regularity assumptions use a vector-valued kernel function $k_i: \\mathcal S \\times \\mathcal S \\rightarrow \\mathbb R^{d_i}$. The definition of GP posterior mean and variance Equs. 7 and 8 are not well-defined as they rely on $\\mathbf K_t$ where $(\\mathbf K_t)_{ij} \\coloneqq k_i(\\mathbf z_i, \\mathbf a_i; \\mathbf z_j, \\mathbf a_j)$, but $k_i$ is vector-valued according to their definition, so $\\mathbf K_t$ is not a matrix. Can the authors clear up this confusion?\n\n3. Why is UCB not tested on ToyGraph and PSAGraph?\n\n4. Other issues:\n- For the definitions of $\\mathcal X$ and $\\mathcal Z_i$, did you mean to use Cartesian product $\\times$ instead of union $\\cup$?\n- The legends of the plots say MBCO instead of MCBO.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_pgTXkfHgS", "reviewer": "Reviewer_geFQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers Bayesian optimization over objective functions defined via a causal graph, where the nodes correspond to functions defining the relationships between nodes in the graph (including the action variables). Within this framework, a UCB-based acquisition function is proposed. This acquisition function is shown to enjoy sublinear regret. Moreover, it is shown to perform competitively with respect to several state-of-the-art methods across several test problems.", "summary_of_the_review": "This paper proposes a novel and technically sound acquisition function for causal BO. This acquisition function performs competitively in numerical experiments. My main concerns are that (1) this work's discussion regarding novelty over prior work is somewhat misleading, and (2) realistic experiments were not considered. Were these two aspects of the paper improved, I would support accepting this work.", "strength_and_weaknesses": "Strengths:\n1. This work considers a relevant problem setting and proposes a technically sound method with good empirical performance and theoretical guarantees. \n2. This paper is very well written overall.\n3. An implementation of the code used in the empirical evaluation is publicly available.\n\nWeaknesses:\n1. Novelty: My main concern is related to this work's novelty claims. I believe the problem setting considered by this work is the same as that of Astudillo and Frazier (2021) in the sense that a function network could be written as a causal graph and vice versa. Both papers consider a directed acyclic graph where nodes in the graph take as input an action variable and the outputs of their parent nodes. I would like the authors to clarify what they mean in the following statement: \"Moreover, function networks are not causal models and do not model actions as interventions.\" Is it only the use of the causal model formalism that makes these two problem settings different? Assuming this is the case, the primary source of the novelty of this work becomes the proposed acquisition function. I believe this is enough for this work to warrant publication, but the authors should clarify this. The authors should also explain that Kusakawa et al. (2021) also developed a UCB-based acquisition function that comes with similar sublinear regret guarantees in the cascade setting. How does the acquisition function proposed in this work compare with that proposed by Kusakawa et a. (2021) for causal graphs with a cascade structure?\n2. Lack of realistic experiments: As discussed by the authors, the problem setting considered in this work arises in many critical real-world applications. However, they only considered one realistic test problem in their empirical evaluation. Moreover, this problem does not seem to be built upon a high-fidelity simulator or real-world data.\n\nOther minor comments: \n1. The authors should discuss how $\\eta$ is modeled in more detail. I wonder how the choice of the neural network architecture affects performance.\n2. This work falls within an existing line of research on grey-box Bayesian optimization (see, e.g., Astudillo and Frazier 2022). I recommend the authors discuss this literature.\n\nAstudillo, R., & Frazier, P. I. (2022). Thinking inside the box: A tutorial on grey-box Bayesian optimization.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Exv4P2dYDp5", "reviewer": "Reviewer_wHmj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present a version of the CBO paper from 2020. They introduce some new minor ideas of how to fuse BO with causal inference ideas.", "summary_of_the_review": "This is a twist on an earlier idea. I do not think there is enough novelty to warrant inclusion as it stands.", "strength_and_weaknesses": "This review proceeds section by section per your paper.\n\n# Abstract\n\n- It is confusing when you say \"downstream\" variable of interest. Certainly BO is a sequential method but you are targeting static causal diagrams wherein which \"downstream\" makes it sound as if you mean something in the future. Looking at your graphs you are targeting the root node of each CD (as per causal inference literature, not decision tree root-nodes who flip the terminology -- though I notice you are calling the outcome variable the 'sink').\n- CBO, as introduced by Aglietti et al., target a full SCM not just a set of SEMs as you infer. Unless you are introducing a new method with the same name, then you are not discussing the same model framework.\n- The original CBO paper does not assume noisless measurements. Where does it say that? The implementation of the model CBO (see here for the complete graph from the paper: https://github.com/VirgiAgl/CausalBayesianOptimization/blob/master/graphs/CompleteGraph.py) clearly has an epsilon parameter (the noise parameter for the observational samples). Your statement is either wrong or you are referring to something different.\n- BO does not come with guarantees either so I am not sure how yours is a valid point? BO is not guaranteed to converge and so by extension neither is CBO.\n\n# Introduction\n\n- You should mention that this idea was first proposed by Aglietti et al. and yours is not a new idea w.r.t. the second paragraph. Similar ideas were introduced by the Lattimore brothers in their 2016 paper on causal bandits and Bareinboim in their 2015 before them. Optimal decision making + causal knowledge is not a new idea.\n- I am curious as to why you depart from standard ideas of representing observationa and interventions in graphical form w.r.t. figure 1. It is standard to make interventional nodes V as upper-case labels and then repsent interventions as removing any incoming arcs to that node which is relabelled with small-caps label v, Hence, why have you departed from this formalism? What is the reasoning?\n\n# BACKGROUND AND PROBLEM STATEMENT\n\n- You are assuming causal sufficiency (no UCs) but the original CBO papers does not. Is that not a bit of a limiting assumption? It certainly limits the type of problems that you can deal with.\n- It would be clearer if you used more set-notation e.g. to refer to all variables bar the outcome variables write $\\mathbf{X} \\setminus \\{Y\\}$. It is clearer.\n- The same thing for graph terminology: use standard family relationships to refer to e.g. the parents of X_i i.e. pa(X_i) if you are not including also the argument and Pa(X_i) if you are. Please stick to this and don't introduce new notation.\n- Can you please provide the pagenumber for \"soft intervention with unknown effect\" in Pearl's book, I cannot seem to find it.\n- I do not follow why graph mutilation (i.e. hard interventions) is an issue w.r.t. your method? Please explain. I do not follow the logic or rather reasoning for going with soft or shift interventions.\n- Not intervening with a hard-intervention would simply be to observe the system which results in no grap mutilation which means the DAG is not modified at all. This seems to be a odds with your previous point.\n- When we cannot intervene on a node we usually call it a \"non-manipulative variable\" - this is well studied. \n- As to _what_ we should intervene on, the intervention set as it is called, is also very well studied. See Lee and Bareinboim's 2018 paper on 'where to intervene' - they prove specifically that when there are no UCs present (like you are assuming) it is always best to intervene on _all_ the parents of the target variable.\n- You ought to reference the metric that you are using as it is not novel and has been used for decades to evaluate bandits.\n- Now in equation 6 you are using hard interventions but which in your setting will not mutilate graph is what you are saying? \n- I find it strange that you have not discussed _what_ you plan to intervene on given that you'll be exploring the whole powerset space of interventions $\\mathcal{P}(\\mathbf{x} \\setminus \\{Y\\})$ and this seems like a detail worth exploring, if not this will be terribly inefficient.\n\n# ALGORITHM\n\n- Where does equation 9 come from?\n- Please explain the last sentence of this paragraph where you say: \"In the following, we set βi,t = βt for all i such that the confidence bounds are still valid.\"\n- After equation 10 then it sounds as if you are indeed exploring the whole powerset over intervention variables. That is a _very_ large set to explore particularly as you do not have UCs so the best intervention is always the parents of Y. \n- What is $\\mathcal{I}$?\n- In the hard intervention paragraph you are saying that use the MIS/POMIS ideas of Lee and Bareinboim but you're not really; you are using one of their definitions (number 1) to find the minimal intervention sets because, again, you do not have UCs, their work is barely applicable to your setting. Their ideas come into their own when there are UCs but otherwise, with chain-structured graphs you just remove intervention sets which topologically yield the same outcome expression.\n\n# THEORETICAL ANALYSIS\n\n- This is a very nice section, nicely done.\n- It would have been nice to have a few examples of the bound in theorem 1 (give it an equation number so it can be referenced) applied to a few of the examples in figure 2.\n- Why are the a's in the figures no longer bold as in figure 1(b)?\n- I think you are taking too many liberties with how you are drawing your graphs. Typically, in causal inference, we reserve dashed edges for items that regard unobserved confounders (mind you, Aglietti et al. also takes liberty with their graph drawing so mine is a general comment). \n- You should look into dynamic treatment regimes; a lot of your examples graphs have the same topological structure (and ordering). Could be interesting to see if your ideas are applicable there.\n\n# EXPERIMENTS\n\n- It would seem odd for you to call the original paper 'EICBO' and not 'CBO' - call it the latter, as they were first to publish this idea.\n- It is very strange that you do not deploy all methods on all test cases in figure 3. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-SCVrFkvN-i", "reviewer": "Reviewer_UVNu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper is about Bayesian Optimization (BO), and, in particular, Causal Bayesian Optimization (CBO) based on a novel model-based approach. Authors propose to extend the existing CBO using a model-based approach, along with proofs for bounding the cumulative regret and more realistic assumptions compared to current CBO approaches. The reference model is the Structural Causal Model (SCM) with known casual graph but unknown functional relations, which enables the representation of both observational and interventional distributions. Authors explore both soft and hard interventions, with and without constraints over actions. The objective is to select a sequence of actions to maximize the expected reward by minimizing the cumulative regret function with a finite horizon. Since the acquisition function cannot be evaluated in closed form, authors apply the \"kernel trick\" and leverage gradient-based optimizers. Finally, both theoretical proofs and empirical evaluations are provided.", "summary_of_the_review": "The paper is well structure, organized and written and I enjoyed reading it.\nTheoretical statements are presented and supported by the associated proofs .\nFurthermore, empirical achievements are well supported a rich set of numerical experiments and obviously the associated results which are presented and discussed in an effective manner. \nThe presented approach is novel for the considered research area and its results are promising also when taking into consideration the assumptions made by the author/s. \nIt is also worth to mentin that the topic of the paper is relevant and discussed in details, thus representing an added value for the venue.\nIn conclusion I think the paper deserves consideration for being presented to a restigious venue as ICLR.", "strength_and_weaknesses": "Strength points:\n    - Model-based approach over structural causal models that inherits the theoretical framework for causal inference.\n    - Guarantees in terms of bounded cumulative regret.\n    - Assumptions make sense, allowing to generalize to a wide range of settings.\n\nWeak points:\n    - No unobserved confounding could be a naive assumption. \n    - Knowing the true causal graph combined with causal sufficiency means to know the causal mechanism, even if the functions are unknown.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%