Adversarial Causal Bayesian Optimization
Authors: Scott Sussex
Pier Giuseppe Sessa
Anastasia Makarova
Andreas Krause
Venue: ICLR 2024 poster (2024)
Keywords: causality
bayesian optimization
Primary area: causal reasoning
TL;DR: A causal Bayesian optimization algorithm for when other agents can also intervene on the system

Abstract: In Causal Bayesian Optimization (CBO), an agent intervenes on a structural causal model with known graph but unknown mechanisms to maximize a downstream reward variable. In this paper, we consider the generalization where other agents or external events also intervene on the system, which is key for enabling adaptiveness to non-stationarities such as weather changes, market forces, or adversaries. We formalize this generalization of CBO as Adversarial Causal Bayesian Optimization (ACBO) and introduce the first algorithm for ACBO with bounded regret: Causal Bayesian Optimization with Multiplicative Weights (CBO-MW). Our approach combines a classical online learning strategy with causal modeling of the rewards. To achieve this, it computes optimistic counterfactual reward estimates by propagating uncertainty through the causal graph. We derive regret bounds for CBO-MW that naturally depend on graph-related quantities. We further propose a scalable implementation for the case of combinatorial interventions and submodular rewards. Empirically, CBO-MW outperforms non-causal and non-adversarial Bayesian optimization methods on synthetic environments and environments based on real-word data. Our experiments include a realistic demonstration of how CBO-MW can be used to learn users' demand patterns in a shared mobility system and reposition vehicles in strategic areas.

Published as a conference paper at ICLR 2024
ADVERSARIAL CAUSAL BAYESIAN OPTIMIZATION
Scott Sussex
Pier Giuseppe Sessa ETH Zürich
Anastasia Makarova ETH Zürich
Andreas Krause ETH Zürich
ETH Zürich s scott sesst..usseeeing seasseeiiff.ttz...... et.z.ch
ABSTRACT
In Causal Bayesian Optimization (CBO), agent intervenes structural causal model with known graph but unknown mechanisms to maximize a downstream reward variable. In this paper, consider the generalization where other agents external events also intervene on the system, which is key for enabling adaptiveness non-stationarities such as weather changes, market forces, or adversaries. We formalize this generalization of CBO as Adversarial Causal Bayesian Optimization (ACBO) and introduce the first algorithm for ACBO with bounded regret: Causal Bayesian Optimization with Multiplicative Weights (CBO-MW). Our approach combines a classical online learning strategy with causal modeling of the rewards. To achieve this, it computes optimistic counterfactual reward estimates by propagating uncertainty through the causal graph. We derive regret bounds for CBO-MW that naturally depend on graph-related quantities. We further propose a scalable implementation for the case of combinatorial interventions and submodular rewards. Empirically, CBO-MW outperforms non-causal and non-adversarial Bayesian optimization methods on synthetic environments and environments based on real-word data. Our experiments include realistic demonstration of how CBO-MW can be used to learn users' demand patterns in a shared mobility system and reposition vehicles in strategic areas.
INTRODUCTION
How can a scientist efficiently optimize an unknown function that is expensive to evaluate? This problem arises in automated machine learning, drug discovery and agriculture. Bayesian optimization (BO) encompasses an array of algorithms for sequentially optimizing unknown functions (Močkus) 1975). Classical BO algorithms treat the unknown function mostly as a black box and make minimal structural assumptions. By incorporating more domain knowledge about the unknown function into the algorithm, one can hope to optimize the function using fewer evaluations.
A recent line of work causal Bayesian optimization (CBO) (Aglietti et al. 2020) attempts to integrate use of structural causal model (SCM) into BO methods. It is assumed that actions are interventions on some set of observed variables, which are causally related each other and reward variable through known causal graph (Fig. Ip), but unknown mechanisms. Many important BO problems might take such shape. For example, managing supply Shared Mobility System (SMS) involves intervening on the distribution of bikes and scooters across the city. Importantly, Sussex et (202)) show that a BO approach leveraging the additional structure of CBO can achieve exponentially lower regret in terms of the action space size.
Most CBO methods date assume that the system is completely stationary across interactions and that only one agent interacts with the system. However, often it would be desirable to incorporate the influence of external events. For example, in SMS the day's 's demand is highly non-stationary, and only be fully observed at the day's 's end. We would like algorithm that adapts to the variability in these external events.
In this work, we incorporate external events into CBO by introducing novel adversarial CBO (ACBO) setup, illustrated in Fig. Ic. Crucially, in ACBO the downstream reward is explicitly influenced by potentially adversarial interventions
certain nodes in the causal graph (identified using dashed nodes in Fig. Ib) that can only be observed a-posteriori. For this general setting, we propose novel algorithm CBO with multiplicative weights (CBO-MW)- and prove regret

---

Published as a conference paper at ICLR 2024
Bayesian Optimization (BO)
Causal
Adversarial Causal
Bayesian Optimization (CBO)
Bayesian Optimization (ACBO)
Qy
dg
Xo
Y
X
Y
a
X1
X1
(a)
(b)
(c)
Figure 1: Visualizations of Bayesian Optimization (BO), Causal BO (CBO), and the Adversarial
CBO (ACBO) introduced this work. Agents must select actions a that maximize rewards Y. (a) Standard BO assumes the simplest DAG from actions to reward, regardless of the problem structure. (b) CBO incorporates side observations, c.g., Xo, X1 and causal domain knowledge. Each observation could be modeled with separate model. (c) In ACBO (this work), we additionally model the impact of external events (weather, perturbations, other players' actions, etc.) that cannot be controlled, but can only be observed a-posteriori. These are depicted as dashed blue nodes and could directly affect the reward node, like dy, or indirectly affect by perturbing upstream variables, like a/. dj-
guarantee using a stronger (but natural) notion of regret than the one used in existing CBO works. For settings where the number of intervention targets is large, we propose a distributed version of CBO-MW which is computationally efficient and can achieve approximate regret guarantees under some additional submodularity assumptions the reward. Finally, we find empirical evidence that CBO-MW outperforms relevant prior work in adversarial versions of previously studied CBO benchmarks and in learning to re-balance units in SMS simulation based upon real data.
BACKGROUND AND PROBLEM STATEMENT
We consider the problem of agent interacting with an SCM for T rounds in order maximize the value of a reward variable. We start by introducing SCMs, the soft intervention model used in this work, and then define the adversarial sequential decision-making problem we study. In the following. we denote with [m] the set of integers {o....,m}
Structural Causal Models Our SCM is described by a tuple J,Y,,,,F,F of the following is set of observed scalar random variables; the set F {fi)m == defines the unknown functional relations between these variables; and Ω = [ is a set of independent noise variables with zero-mean and known distribution. We the notation Y and Xm interchangeably and assume the elements of X are topologically ordered, i.c., Xo is a root and X,, is a leaf. We denote with pa; C {O..... m] the indices of the parents of the ith node, and use the notation Z; (X,)jepa; for the parents this node. We sometimes use X; to refer to both the ith node and the ith random variable.
elements: G is a known DAG; is the reward variable; X = | 1m=1
Each X; is generated according to the function fi Z; + X. taking the parent nodes Z, of X; as input: x; = fz(z)) + wi, where lowercase denotes a realization of the corresponding random variable. The reward is scalar 3'm [0, 1] while observation X; is defined over compact set 2; E X; R, and its parents are defined over Z,- = IIEppe, N, for i E [m -
Interventions In our setup, an agent and an adversary both perform interventions on the SCM We consider a soft intervention model (Eberhardt and Scheines, (007) where interventions are parameterized by controllable action variables. A simple example of a soft intervention is a shift intervention, where actions affect their outputs additively (Zhang et al. 2021).
'err consider scalar observations for ease of presentation, but we that the methodology and analysis can casily extended to vector observations as in Sussex et a (2022)
?Our framework allows for there to be potentially multiple adversaries, hut since consider everything from single player's perspective, is sufficient combine all the other agents into single adversary.
2

---

Published as a conference paper at ICLR 2024
First, consider the agent and its action variables {a: Each action o; is real number chosen from some finite set. That is, the space A, of action ag is A, C Rio.1] where |A] = K, for some K2 E N. Let A be the space of all actions a {a, m i=0' We represent the actions as additional nodes in G (see Fig. 1): a; is parent of only X,, and hence an additional input to fi Since fi is unknown, the agent does not know apriori the functional effect of a; on X, Not intervening on a node X; can be considered equivalent to selecting a O. For nodes that cannot be intervened on by our agent, we set K, = 1 and do not include the action in diagrams, meaning that without loss of generality we consider the number of action variables to be equal to the number of nodes m.
For the adversary we consider the same intervention model but denote their actions by a' with each df defined over A/ R1o.1j where |A'] = K" and K? is not necessarily equal to Kg
According to the causal graph, actions a, a' induce a realization of the graph nodes:
23 fz az dd) + we, Vi E [m]]
(1)
If an index corresponds a root node, the parent vector z; denotes an empty vector, and the output of fa only depends on the actions.
Problem statement Over multiple rounds, the agent and adversary intervene simultaneously on the SCM, with known DAG G and fixed but unknown functions F = D with fi : Z, x A; x A + X, At round the agent selects actions a.. = {as.e) T and obtains observations I., = { J==0 where we add an additional subscript to denote the round of interaction. When obtaining observations, the agent also observes what actions the adversary chose a', = {d(,))==o- We assume the adversary does not have the power to know a. when selecting a',. but only has access to the history of interactions until round / and knowledge of the agent's 's algorithm. The agent obtains a reward given by
Y/ fm (Zm,t, am,t, m,,) + Wm.t.
which implicitly depends on the whole action vector a., and adversary actions a',--
The agent's goal is to select sequence of actions that maximizes their cumulative expected reward Ei=r ,t, [', where r(a.,,, a', E y/ a.,t e',, and expectations are taken over w unless otherwise stated. The challenge for the agent lies in not knowing a a-priori neither the causal model (i.e., the functions F {ft m 1), nor the sequence of adversarial actions {
Performance metric notion of regret:
After T timesteps, we can measure the performance of the agent via the
T
R(T) = max Σ r(a.a'.)) - Σ r(a d(y)) aEA
(3)
1=1
i... the difference between the best cumulative expected reward obtainable by playing a single fixed action if the adversary's ' action sequence and F were known in hindsight, and the agent's s cumulative expected reward. We seek to design algorithms for the agent that are no-regret, meaning that R(T)/T + 0 as T + oo, for any sequence a', We emphasize that while we use the term "adversary", our regret notion encompasses all strategies that the adversary could use to select actions. This might include cooperative agents or mechanism non-stationarities.
For simplicity, we consider only adversary actions observed after the agent chooses actions. Our meth- ods can be extended to also consider adversary actions observed before the agent chooses actions, i.c., a context. This results in learning a policy that returns actions depending on the context, rather than just learning fixed action. This extension is straightforward and we briefly discuss it in inpppediix A.2
Regularity assumptions We consider standard smoothness assumptions for the unknown functions fo : S + X; defined over a compact domain S (Srinivas et al.) 2010)). In particular, for each node i E [m]. we assume that f((-) belongs to reproducing kernel Hilbert space (RKHS) HA, a space of
smooth functions defined on S = Z, x A; x A'. This means that fi E He, is induced by kernel func- tion k; S x S + R. We also assume that (s, 8') S 1 for every s, s' s Moreover, the RKHS
'hher may be constraints on the actions our agent can take. We refer the reader to Sussex et al. 2022 for how our setup can he extended to handle constraints. *This is known as the bounded variance property, and it holds for many common kemnls..
3

---

Published as a conference paper at ICLR 2024
norm of fa()) is assumed to be bounded || [|fe S 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., uy E [-1,1]"
3 RELATED WORK
Causal Bayesian optimization Several recent works study how to perform Bayesian optimization on systems with an underlying causal graph. Aglietti al. (2020) proposes the first CBO setting with hard interventions and an algorithm that uses the do-calculus to generalise from observational interventional data, even in settings with unobserved confounding. [Astudillo and Frazier (2021) consider noiseless setting with soft interventions (known as a function network) where a full system model learnt, and an expected improvement objective used to select interventions. Sussex et al. (2022) propose MCBO, an algorithm with theoretical guarantees that can be used with both hard and soft interventions. MCBO propagates epistemic uncertainty about causal mechanisms through the graph, balancing exploration and exploitation using the optimism principle (Srinivas et al. 2010)) Causal bandits, which similarly incorporate causal graph knowledge into the bandit setting, usually consider discrete actions with categorical observations (Lattimore et al. 2016) linear mechanisms with continuous observations (Varici et al. 2022). All of these methods consider only stationary environments and do not account for possible adversaries.
Bayesian optimization in non-i.id. settings Multiple works study how to develop robust strategies against shifts in uncontrollable covariates. They study notions of worst-case adversarial robustness (Bogunovic et al., 2018)) distributional robustness (Kirschner et al., 2020; Nguyen et al., 2020), robust mixed strategies (Sessa et al. 2020a) and risk-aversion to uncontrollabe environmental parameters (Makarova et al. 2021 Iwazakk et al. (02T). Nonstationarity is studied in the canonical BO setup in Kirschner et al. (2020); Nguyen et al. (2020) and in the CBO setup in Aglietti et al. (20TT) However, these methods do not accommodate adversaries in the system, e.g., multiple agents that we cannot control. A foundation for our work is the GP-MW algorithm (Sessa et al. 2019) which studies learning in unknown multi- sallttsagens games and is a special case of our setting. We compare further with GP-MW in Section 5) Another special case of CBO-MW with specific graph STACKEL UCB (Sessa et al. 2021), designed for playing unknown Stackelberg games with multiple types of opponent (see Appendix A.1.I.
Tazzki
METHOD
In this section, we introduce the methodology for the proposed CBO-MW algorithm.
4.1 CALIBRATED MODELS
An important component of our approach is the use of calibrated uncertainty models learn functions F, as done in Sussex et al. (022). At the end of each round t, we use the dataset D. { 1.,1:t, a' I. of past interventions fit a separate model for every node in the system. CBO-MW can be applied with any set of models that have calibrated uncertainty. That is, for every node at time / the model has a mean function fs,t and variance function ai,t (learnt from D,) that accurately capture any epistemic uncertainty in the true model.
Assumption (Calibrated model). All statistical models are calibruted w.r.t. F, so that Vi, there exists a sequence B, R2 such that, with probability least (1 -)), for all 2,, ay df E A, A we have (z, a,, a²) Mi,t-1 ag, df)l < 1, ag a²), clement-wise.
If the models are calibrated, we can form confidence bounds that contain the true system model with high probability. This done by combining separate confidence bounds for the mechanism each node. At time I, the known set M, of statistically plausible functions F {f.)) defined as:
M. {F- f== -fim s.t. Vi: je E Ha,, llfele, S B,, and
(4)
(((,,,,,))) M,,- - S S af). Vz, E 2, E Ar, E A}
4

---

Published as a conference paper at ICLR 2024
GP models Gaussian Process (GP) models can be used to model epistemic uncertainty. These the model class we study in our analysis (Section 5). where we also give explicit forms for B that satisfy Assumption 1 For all i [m], let Mi.0 and oe denote the prior mean and variance functions for each Jt, respectively. Since w; is bounded, it is also subgaussian and we denote the variance by bg. The corresponding posterior GP mean and variance, denoted by μi, and of, respectively, are computed based on the previous evaluations D;:
(1,,1(1,111)) = k((88,1:)) (K, + (/1,) 10i,1 "
(5)
(8111)) k(81,1:6) 81.1a) k. (81,1:) (K, + 1.
(6)
where 81, = (a 0i, a(,,,)), kc(81,1)) = (k(8)..) 84,14)]==1+ and K. [k(B 88," Mai is the kernel matrix.
Algorithm Causal Bayesian Optimization Multiplica- tive Weights (CBO-MW)
4.2 THE CBO-MW ALGORITHM
Require: parameters т, (3) (1,,), 9, S. kernel func- tions k; and prior means 14,0 = 0 Vi E [m]]
We can now present the proposed CBO-
MW algorithm. Our approach is based
upon the classic multiplicative weights
1: Initialize w L (I,....1) E RI4]
[
method (Littlestone and Warmuth] [994]]
2: for -ar/=10 1. 1.2....... do
Freund and Schapire 1997), widely used
3: Sample a ~ w
adversarial online learning. Indeed, ACBO
4: Observe samples { Li,e, dí, 1==
can be seen as specific structured online
5: Update posteriors (1.,( ()), (-)
learning problem. At time t, CBO-MW maintains a weight w² for every possible intervention E A such that Σ. w² 11 and uses these to sample the chosen intervention, i.e., a, w/a Contrary to standard CBO (where algorithms can choose actions deterministicallyy.. in adversarial environments such as ACBO randomization is necessary to achieve no-regret, see, e.g., Dessa-Bianchi and Lugosi (2006).
6:
for a E A do
7:
Compute UCB/ (a, a/) using Algorithm 2
8:
; =1i UCB, (a. a!))
-++1 x w exp(r 1%a)
9:
W.a
10: end for
11: end for
Then, CBO-MW updates the weights at the end of each round based upon what action the adversary took aj and the observations xy. the mechanism between actions, adversary actions, and rewards were to be completely known (i.e., the function r(-) in our setup), standard MW strategy suggests updating the weight for every a according to
w1+1 x w/ exp (r.r(a,a)))
where 7 is a tunable learning rate. In particular, r(a, a!) is the counterfactual of what would have happened, in expectation over noise, had a' remained fixed but the algorithm selected a instead of a,,
However, in ACBO the system unknown and thus such counterfactual information not readily available. On the other hand, as outlined in the previous section, models around the unknown mechanisms and then estimate counterfactual quantitics from them. Specifically, CBO-MW utilizes the confidence set Mr to compute an optimistic estimate of r(a, af):
build and update calibrated
UCB (a, a') max E [y) F, FEM,
|F,,aaa a. a;)
Given action a, opponent action at and confidence set M,, UCB, (a, a') represents the highest expected return among all system models in this confidence set. CBO-MW uses such estimates to up- date the weights in place of the true but unknown counterfactuals r(a, a)). Computing UCB$ (a, a') challenging since our confidence set Mr consists of set of m different models and one must propagate epistemic uncertainty through all models in the system, from actions to rewards. Because mechanisms can be non-monotonic and nonlinear, one cannot simply independently maximize the output of every mechanism. We thus defer this task to algorithmic subroutine (denoted causal UCB oracle) which we describe in the next subsection. CBO-MW is summarized in in/oogrii I]
We note that CBO-MW strictly generalizes the GP-MW algorithm of Sessa et al. (2019), which was first to propose combining MW with optimistic counterfactual reward estimates. However, they consider trivial causal graph with only target node, thus single GP model. For this simpler
5

---

Published as a conference paper at ICLR 2024
model one compute UCB in closed- but must ignore any causal structure in the reward model. In |Section 5] and in our experiments we show CBO-MW can significantly outperform GP-MW both theoretically and experimentally.
4.3
CAUSAL UCB ORACLE
The problem in Eq. (7) is not amenable to commonly used optimization techniques, due to the maximization over set of functions with bounded RKHS norm. Therefore, similar to (usSsx et al.
(022) we make use of the reparameterization trick to write any Sa E F E Mr using a function M 2, x A A [-1, 1] as
f. ai σ() = Mh, 1 d; a!) + 3,0,,-1(2,, a. d.)m:( a; a!).
(8)
where à; fā a, a() W; denotes observations from simulating actions in one of the plausible models, and not necessarily the true model. The validity of this reparameterization comes directly from the definition of Mr in Eq. (4) and the range of TJ:
The reparametrizzaionn allows for rewriting UCB in terms of n7 A x A' + 1-1,11
UCB (a. a') max Ew y F.a.a, s.t. F (fa.) in Eq. (8)
n(-)
In practice, we can parameterize 17, for ex- ample with neural networks, and maximize this objective using stochastic gradient ascent, as described in Algorithm 2 The use of the reparameterization trick simpli- fies the optimization problem because we go from optimizing over functions with tricky constraint (F E M2) to much simpler constraint (1) just needing output in [0, 1)). Since the optimization problem is still non-convex, we deploy multiple ran- dom re-initializations of the r parameters.
Algorithm 2 Causal UCB Oracle
Require: neural networks n. actions a', model
posteriors μ4, a. parameter 3e, repeats Nye-
I: Initialize SOLUTIONS = (1
2: for j= 1,... NNep do
3: Randomly initialize weights of each 1/c "
4: UCB, max Ely F, a, a') computed
via stochastic gradient ascent on r
5:
SOLUTIONS SOLUTIONS {UCB])).
6: end for
7: return max(SOLUTIONS)
ANALYSIS
Here we analyse the theoretical performance of CBO-MW and provide a bound on its regret as a function of the underlying causal graph. For our analysis, we make some additional technical assumptions. First, we assume all fi E F are Ly-Lipschitz continuous. This follows directly from the regularity assumptions Section 2] Second, we assume that Vi, 4, the functions 14, Ts, are Ly Lg Lipschitz continuous. This holds if the RKHS of each fo has a Lipschitz continuous kernel (see Curi et al.) (2020), Appendix G). Finally, we assume the causal UCB oracle can always compute UCB, (a,a') (Eq. (9) exactly.
In addition, to show how the regret guarantee depends on the specific GP hyperparameters used, we notion of model complexity for each node i:
I(Z,11;,ff Nr A.C (2.XA(XA))
max
(10)
where I is the mutual information and the observations I;,1T implicitly depend on the GP inputs A, This is analogous to the maximum information gain used in the analysis of standard BO algorithms
Srinivas et al. (010)). We also define
TT max K.T
(11)
as the worst-case maximum information gain across all nodes in the system.
Finally, we define two properties of the causal graph structure that the regret guarantee will depend on. In the DAG g over nodes { let A denote the maximum number of parents of any variable in G: A max; [pa()). Then let N denote the maximum distance from root node to X,.: N = max, di, X,)) where dist(...) ) is the number of edges in the longest path from a node X; to X... We can then prove the following theorem the regret of CBO-MW.

---

Published as a conference paper at ICLR 2024
Theorem 1. Fix 8 E 10. if actions are played according to CBO-MW with B O (B+ Vn-1+ log(m/0) and r = 18loog |A)/T, then with probability at least 1 - -,
R(T)- = ( (VVTlo [A| + + (Tog((2/)) + (B V + log(m/6))
N+1 L Ly
where B = max; Bi, YT = max N, That is, "TT is the worst-case maximium information gain of any of the GP models.
Theorem 1 whose proof is deferred to the appendix, shows that CBO-MW is no-regret for variety of common kernel functions, for example linear and squared exponential kernels. This is because even when accounting for the dependence of "rr in T, the bound is still sublinear in T. We discuss the dependence of y/r on T for specific kernels in Appendix A.1.2
Comparison with GP-MW We can use Theorem 1 to demonstrate that the use of graph structure in CBO-MW results in a potentially exponential improvement in the rate of regret compared to GP-MW (essaa et al. 2019) with respect to the number of action variables m. Consider the graph Fig. 4p (see Appendix) for illustration. When all X; in CBO-MW are modeled with squared exponential kernels, we have " O((A + (log A+3)) This results in a cumulative regret that exponential in and N. Instead, GP-MW uses a single dige-nimmnsional GP (Fig. 4h), implying 'T = (llg T) for a squared exponential kemnel. Note that 2 A + N and thus, for several common graphs, the exponential scaling in N and A could be significantly more favorable than the exponential scaling in m. Specifically for the binary tree of Fig. 4p, where N log(m) and A 2, the cumulative regret of CBO-MW will have only polynomial dependence on m..
Furthermore, in addition favorable scaling of the regret in m, the model class considered by CBO- MW is considerably larger than that of GP-MW, because CBO-MW can model systems where reward depends on actions according to a composition of GPs based on G. rather than a single GP.
6 COMPUTATIONAL CONSIDERATIONS IN LARGER ACTION SPACES
The computational complexity of CBO-MW is dominated by the computation of the counterfactual expected reward estimate for each possible intervention E AA (Line 7 in [Algriithm I). In many situations, even with a large number of action variables m. |A| may still be small and thus CBO-MW feasible to implement.
notable example is when there exist constraints on the possible interventions, such as only being able to intervene on at most a few nodes simultaneously. In the worst case, though, [A] grows exponentially with m and thus CBO-MW may not be computationally feasible. In this section we will show how prior knowledge of the problem structure can be used to modify CBO-MW to be computationally efficient even in settings with huge action spaces. We note that the computational efficiency of CBO-MW is not affected by the number of possible adversary interventions [A'| because these are only observed a-posteriori (in fact, A' need not be finite).
The general idea consists of decomposing CBO-MW into decentralized algorithm, which we call D-CBO-MW that orchestrates multiple sub-agents. First recall that AA can be decomposed into m smaller action spaces so that A Ai x... agent performs CBO-MW but only over the action space A, Importantly, the observations of the ac- tions of the other agents are considered part of A' for that agent. Moreover, all agents utilize the same calibrated model M, at each round. We provide full pseudo-code and theory in the appendix. Our approach is inspired by (Sessa et al. (202T) who propose a distributed analog of the GP-MW algorithm.
... x Am. We then consider m independent agents where each
In Appendix B we show that under specific assumptions on the reward function, D-CBO-MW prov- ably enjoys an approximate version of the guarantees in Theorem 1] Namely, we study a setting where r is submodular and monotone increasing function of a for any given set of adversary actions. Sub- modularity is diminishing returns property (see formal definition in the appendix) widely exploited in variety of domains to derive efficient methods with approximation guarantees, see e.g., Marden and Wierman (2013); Sessa et al. (202T): Paccagnan and Marden (022). Similarly, we exploit submodu- the possible interventions in our causal graph. In our experiments, we study rebalancing an SMS where CBO-MW is not applica- ble due combinatorial action space but D-CBO-MW is efficient and achieves good performance.
larity in the overall reward's structure to parallelize the computation
7

---

Published as a conference paper at ICLR 2024
Alpion Peiny
Peetne-
Dropwave- Prapaave-eenyy
CID CBO-MWW MW (0um)
CBO. CBO-MW MW (Quss
CBO MW (Ous)
Cannlation Pogges
10.0
Commlstio Regres
MCBO
Commistiv Regres
MCBO
GP-UCB
GP-UCB
GP-UCB
7.3-
GP-MW
GP-MW
GP-MW
0.0-
0.9
0
30
100
25
50
100
0
50
15
150
Bound
Round
Round
Figure 2: CBO-MW achieves sublinear regret and high sample efficiency on function networks in the presence of adversaries. Non-adversarial methods (GP-UCB and MCBO) achieve linear regret and non-causal methods (GP-MW) are less sample efficient.
EXPERIMENTS
We evaluate CBO-MW and D-CBO-MW on various synthetic problems and a simulator of rebalancing an SMS based on real data. The goal of the experiments is to understand how the use of causal modelling and adaptability to external factors CBO-MW affects performance compared to other BO methods that are missing one or both of these components. All methods are evaluated over 10 repeats, with mean and standard error reported for different time horizons.
7.1 FUNCTION NETWORKS
Networks We evaluate CBO-MW 8 diverse environments. As base, we take 4 examples of function networks from Astudillo and Frazier (202T). Function networks is a noiseless CBO setup with no adversaries. To study an adversarial setup, we modify each environment by adding adversaries' inputs in 2 ways: Penny and Perturb. In Penny, an adversary can affect a key node with dynamic similar to the classic matching pennies game. In Perturb, the adversary can perturb some of the agent's 's interventions. The exact way in which the adversary's actions affect the environment is unknown and the actions themselves can only be observed a a-posteriori. has a 20% chance to play randomly, and an 80% chance to try and minimize the agent's 's reward, using full knowledge of the agent's strategy and the environment. The causal graph and structural equation model for each environment in given in Appendix C
each round, the adversary
Baselines We compare the performance of CBO-MW Algorithm I) with GP-MW Sessa et al. (2019) which does not exploit the causal structure. We additionally compare against non-adversaris baselines GP-UCB (Srinivas et al., 2010). and MCBO (Sussex et al. 2022) which uses a causal model but cannot account for adversaries.
We give results from 3 of the 8 environments in Fig. 2 In general across the environments, MCBO and GP-UCB obtain linear regret, while the regret of GP-MW and CBO-MW grows sublinearly, consistent with Theorem I CBO-MW has the strongest or joint-strongest performance on out of the 8 environments. The setting where CBO-MW is not strongest involves a dense graph where worst-case GP sparsity is the same in GP-MW. which is consistent with our theory. In settings such as Alpine where the graph is highly sparse, we observe the greatest improvements from using CBO-MW.
Results
Others can be found in Appendix C
7.2 LEARNING TO REBALANCE SHARED MOBILITY SYSTEMS (SMSs)
We evaluate D-CBO-MW on the task of rebalancing an SMS, a setting introduced in Sessa et al. (202T). The goal allocate bikes to city locations (using relocation trucks, overnight) to maximize the number of bike trips in the subsequent day. The action space is combinatorial because each of the 5 trucks can independently reallocate units to a new depot. This makes the approaches studied in Section 7.1 computaiiiolllll infeasible, so we deploy D-CBO-MW. We expect the reward Y, (total trips given unit allocation) to be monotone submodular because adding an extra unit to a depot should increase total trips but with decreasing marginal benefit, discussed in (Sesa et al. (2021). The goal is to compare D-CBO- MW to a distributed version of GP-MW and understand whether the use of a causal graph improve sample efficiency.
8

---

Published as a conference paper at ICLR 2024
0,300
Daly This (
0.175
0:160
0.196
0.300
0.076
D-CBO-MW (Ouss)
0.000
RANDOM
D-GP-MW
0
80 100 150
200
Doy
(a)
(b)
Figure 3: Learning rebalance SMS. (a) Green dots represent demand for trips, black crosses are depot locations, and blue circles are scaled size to the frequency that D-CBO-MW assigns bikes that depot (averaged across all repeats and days). D-CBO-MW W assigns bikes in strategic locations near high demand. (b) D-CBO-MW fulfills more total trips across over 200 days compared D-GP-MWV GW which does not use causal reward model.
Setup and trips simulator A simulator is constructed using historical data from an SMS in Louisville, KY (Lou 2021). Before each day t, all 40 bikes in the system are redistributed across 1 116 depots. This is done by 5 trucks, each which can redistribute 8 bikes at one depot, meaning truck i's action is a, [116]. The demand for trips corresponds to real trip data from Lou| (2021) After each day, we observe weather and demand data from the previous day which are highly non-stationary and thus correspond adversarial interventions a' according our model. Our simulator is identical to the one of Sessa et al. (02T). except we exclude weekends for simplicity. We give more details in Appendix C
We compare three methods on the SMS simulator. First, in RANDOM each truck places its bikes at depot chosen uniformly at random. Second, D-GP-MW modifies GP-MW using the same ideas as those presented in SSection 6 It is a special case of D-CBO-MW but using the graph in Fig. Ta). That is, a single GP used to predict Y, given a,, a/. Finally, we evaluate D-CBO- M W which utilizes more structured causal graph exploiting the reward structure. Based historical data, we cluster the depots into regions such that trips don't frequently occur across two different regions (e.g.. when such regions
too far away). Then, our graph models the trips starting in each region only using bike allocations to depots in that region. Y, is computed by summing the trips across all regions (seefl Fig. 8 (b) in the appendix for illustration). This system model uses many low-dimensional GPs instead of a single high-dimensional GP as used D-GP-MW.
Results Fig. 3 (a) displays the allocation strategy of D-CBO-MW. We observe that D-CBO-MW learns the underlying demand patterns and allocates bikes strategic areas where the demand (green dots) is higher. This plot is zoomed-in for readability. The allocation strategy over all depots is shown in Appendix Fig. 9 Morcover, in Fig. 3 (b) we see that D-CBO-MW is significantly more sample efficient than D-GP-MW. This improvement is largely attributed early rounds, where D-CBO-MW leamss the demand patterns much faster than D-GP-MW due to learning mallee--imensiooall GPs.
CONCLUSION
We introduce CBO-MW, the first principled approach to causal Bayesian optimization in non-stationary and potentially multi-agent environments. We prove sublinear regret guarantee for CBO-MW and demonstrate a potentially exponential improvement in regret, in terms of the number of possible intervention targets, compared to state-of-the-art methods. We further propose distributed version of our approach, D-CBO-MW, that can scale to large action spaces and achieves approximate regret guarantees when rewards monotone submodular. Empirically, our algorithms outperform existing non-causal and non-ad versariaa methods on synthetic function network tasks and SMS rebalancing simulator based real data.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
Attached to this submission we include code (https://githui) htttps///gttuubb.ccm//setttt/ implements CBO-MW, D-CBO-MW and all baselines seen in the experiments. It includes code for all function network environments and the SMS setting, which are also detailed in the appendix. All datasets used in the SMS setting are also included this url. The appendix includes information on our experimental protocol, for example how we selected the hyperparameters for the experiments shown in the paper.
that
All technical assumptions are given in the main paper, and complete proofs of all theoretical results are given in the appendix. Pseudocode for CBO-MW is given in the main paper and pseudocode for D-CBO-MW is given in the appendix.
ACKNOWLEDGEMENTS
We thank Lars Lorch for his feedback on the draft of this paper.
This research was supported by the Swiss National Science Foundation under NCCR Automation, grant agreement 5 51NF40 180545, by the European Research Council (ERC) under the European Union's Horizon grant 815943, and by ELSA (Furopean Lighthouse on Secure and Safe Al) funded by the European Union under grant agreement No. 101070617.
REFERENCES
Jonas Močkus. On Bayesian methods for seeking the extremum. In Optimization Techniques, 1975.
Virginia Aglietti, Xiaoyu Lu, Andrei Paleyes, and Javier González. Causal Bayesian Optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Scott Sussex, Anastasia Makarova, and Andreas Krause. Model-based causal bayesian optimization. In International Conference on Learning Representations (ICLR), 2022.
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of science, 74(5):981-95 999599, 2007.
Jiaqi Zhang, Chandler Squires, and Caroline Uhler. Matching desired causal state via shift interventions. Advances in Neural Information Processing Systems, 14:19923-19934, 2021.
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.
Raul Astudillo and Peter I. Frazier. Bayesian Optimization of Function Networks. In Advances in Neural Information Processing Systems (NeurIPS), 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.
Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Causal bandits for linear structural equation models. arXiv preprint arXiv:2208. 12764, 2022.
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with gaussian processes. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Thanh Nguyen, Sunil Gupta, Huong Ha, Santu Rana, and Svetha Venkatesh. Distributionally robust Bayesian quadrature optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
10

---

Published as a conference paper at ICLR 2024
Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. Mixed strategies for robust optimization of unknown objectives. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020a.
Anastasia Makarova, Ilnura Usmanova, Ilija Bogunovic, and Andreas Krause. Risk-averse het- eroscedastic bayesian optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Shogo Iwazaki, Yu Inatsu, and Ichiro Takeuchi. Mean-variance analysis in Bayesian optimization under uncertainty. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Virginia Aglietti, Neil Dhir, Javier González, and Theodoros Damoulas. Dynamic causal bayesian optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Pier Giuseppe Sessa, Iliaa Bogunovic, Maryam Kamgarpour, and Andreas Krause. No-regret learning in unknown games with correlated payoffs. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Pier Giuseppe Sessa, Ilija Bogunovic, Andreas Krause, and Maryam Kamgarpour. Online submodular resource allocation with applications to rebalancing shared mobility systems. In Proceedings of International Conference on Machine Learning (ICML), 2021.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-26)) 1994.
Yoav Freund and Robert E Schapire. A application to boosting. Journal of computer and system sciences, 55(1):119-13)) 1997.
generalization on-line learning and an
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Sebastian Curi, Felix Berkenkamp, and Andreas Krause. Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Jason R Marden and Adam Wierman. Distributed welfare games. Operations Research, 61(1): 155-168, 2013.
Paccagnan and JR Marden. Utility design for distributed resource allocation-par i:: Applications to submodular, covering, and supermodular problems. IEEE Transactions on Automatic Control, 67: 618-632, 2022.
Louisville Kentucky Open Data, 2021. dataset/dock weaiccklesseeeiiee les]
URL https::/daat..oosssrlllkkyy
Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause, Learning to play sequential games versus unknown opponents. Advances in Neural Information Processing Systems (NeurIPS), 2020b.
Pier Giuseppe Sessa, Ilija Bogunovic, Andreas Krause, and Maryam Kamgarpour. Contextual games: Multi-agent learning with side information. Advances in Neural Information Processing Systems (NeurIPS), 33:21912-21922 2020c.
An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann. Continuous dr-submodular maximiza- tion: Structure and algorithms. Advances Neural Information Processing Systems (NeurIPS), 30, 2017.
Francis Bach. Submodular functions: from discrete to continuous domains. Mathematical Program- ming, 175:419-459, 2019.
Local Weather Forecast. News and Conditions wunderground. com/
Weather Underground. URL ht https::///...... :///////w www
11

---

Published as a conference paper at ICLR 2024
ADVERSARIAL CAUSAL BAYESIAN OPTIMIZATION
A APPENDIX
A.1 PROOF OF THEOREM
We start by proving that there exists a sequence of St that allow Assumption to hold.
Lemma 1 (Node Confidence Lemma) ). Lel Ha, be a RKHS with underlying kernel function kij- Consider an unknown finction Ji 2, x Ai Ai, X, in Ha; such that [[[[], I Bi, and the sampling model Ti,t = f(z,,,, ai o3,1) twe where we is A-sub-Gaussian (with independence between times). By setting
3, = B, + by (ri-1 log(m/6)).
the following holds with probability at least 6:
1 ae ai') fi(zz, ai, a')1 - B.or,t- ai, a')
Vzz ai de 2 A, Ai VI 1, Ei [m]; where pt (.) and 1-)1(-) are given in Eg. (5) Eq.. (6) and 4t is the maximum information gain defined in 11..
Proof. Lemma I follows directly from Sessa al. (2019 Lemma 1) after applying union bound so that the statement holds for all m GP models in our system.
Now we give an upper and lower confidence bound for at each l. Note that since in our setup all wi are assumed bounded in [0, 1], we can use b 1
Lemma 2 (Reward Contidence Lemma). Choose E [0, 1] and then choose the sequence { 1T according Lemma
Va, a, E Ax A', YL we have with probability 1 -
UCB/ (a. a') Cτ( S <r(a, al) UCB (a, of)
where we define Cτ(ō)
m ar
Cg(6) A
mEw
0 aR
We define Ly.: = (1 (1 + L, 23, M.
Proof. The RHS follows firstly from Assumption I meaning that with probability at least T {f.) The RHS then follows directly from the definition of UCB in Eq. (7)
The LHS follows directly from Sussex al. 2022 Lemma 4). The addition of the adversary actions
does not change the analysis in this lemma because for a given t, af, is fixed for both the true model f and the model in { that leads to the upper confidence bound.
Now we can prove the main theorem. Choose 8 E [0, 1] and then choose the sequence { according to Lemma 1 so that Assumption holds with probability 1 - 2. defined as
& First recall that regret is
R(T) = a() -E r(an, a.)
t=1
where â arg EL r(a, a.). Now say that with probability at least
12

---

Published as a conference paper at ICLR 2024
R(T) S
min(1,UCB]) a,)}
UUBB Co (6/2)
(12)
m1, UCB/ (a, a())
UCB aa, a,) + Σ C2 (6/2)
(13)
t=1
where the first line follows from Lemma 2 Evaluating the last term we see
Σ C6/2))
VT
Σ C. (8/2)²
(14)
m
VT
22 A
aess dl1
(15)
LY (Tmrr)
(16)
① comes from AM-QM inequality and 2 comes from plugging in for C₂()). Finally, 3 comes from LT, being weakly increasing in and from using the same analysis as (Sussex et al. 2022 Theorem 1) upper bound the sum of as with Tr-
Moreover, can upper bound the first two terms of Eq. (13) (13)using standard regret bound for the MW update rule (Line 9 in CBO-MW), e.g. from (Cesa-Bianchi and Lugosi 2006 Corollary 4.2). Indeed, with probability 1 it holds:
min UCB a()
Σ (CB a() =
(Al + (log(2/0)) (17)
Using the union bound on the two different probabilistic events discussed so far (Assumption and Eq. (17) we can say that with probability at least
R(T) = O ( (oT |A|
log + LY.T VTmYT).
Substituting in for Ly. and Br gives the result of Theorem
A.1.1 STACKELUCB AS A SPECIAL CASE
In Fig. 4[and[Section 5) we give comparison between GP-MW and CBO-MW, and see that GP-MW can be seen special case of CBO-MW with one-node causal graph. STACKEL Sessa et al.) (2020b) is another online learning algorithm that can be seen as a special case of CBO-MW. We show the graph Fig. In STACKEL UCB an agent plays an unknown Stackelberg game against changing opponent which at time f has representation 4',-- After the agent selects an action dp, the opponent sees this action and responds based upon a fixed but unknown response mechanism is Xo,: Jo Jo(o,,t: do,z). Then, the response, game outcome Y,, and opponent identity revealed the agent. The sequence of opponent identities, i.e. {a),) can be selected potentially adversarially based on knowledge of the agent's strategy.
for that opponent: their response
)T
A.1.2 DEPENDENCE OF 3r ON T FOR PARTICULAR KERNELS
In Theorem there is a dependence of the bound on Yr. Yr scales with at worst (vT) then the overall bound will not be in T, resulting in CBO-MW being no-regret. "yr will depend the
13

---

Published as a conference paper at ICLR 2024
GP-MW
CBO-MW
Y
01
X4
X5
022
Xo
X1
X2
X3
03
@1
a22
102
03
ag
(a)
(b)
Figure 4: An example of a binary tree graph to compare GP-MW and CBO-MW. (a) we see GP-MW ignores all observations and models Y given all agent and adversary actions, resulting a single high-dimensional GP. Meanwhile in (b), for the same task, CBO-MW fits a model for every observation resulting in multiple low-dimensional GP models.
Xo
Y
Figure 5: The causal graph corresponding STACKELUCB, special case of setup. The opponent action Xo is played based on the opponent type d and as a response to the agent's ' action ag- The reward Y depends on the agent and opponent's action.
kernel of the GP used to model each system component, For simplicity, in this section we'll assume that the same kernel is used for modelling all nodes, though if different kernels are used one just needs to consider the most complex (worst scaling of yr with T')
For "r corresponding to the linear kernel and squared exponential kernel, have sublinear regret regardless of N because "rr will be only logarithmic in T. In particular, a linear kernel leads to PT O ((A 1) log 7) and squared exponential kernel leads to 7T ((A + 1) +2).
However, for Matérn kernel, where the best known bound is "r O (Tg with hyperpa- and e are sufficiently large.
rameter 0 < c < 1, the cumulative regret bound will not be sublinear A similar phenomena with the Matérn kernel appears in the guarantees of Curi et al. (2020) which use GP models in model-based reinforcement learning and in Sussex et al. (022)
A.2 INCORPORATING CONTEXTS INTO CBO-MW
Our approach can be easily extended to a setting where a', the adversary actions at time f, are observed before the agent chooses aç. In this setting the adversary actions could be thought of as contexts. Our method for computing UCB can be plugged into the algorithm Sessa al. (202cc). Their algorithm maintains a separate set of weights for every context unless two contexts are "close" correspond to similar expected reward for all possible a.
14

---

Published as a conference paper at ICLR 2024
Algorithm 3 Multiplicative Weights Update (MWU)
Require: set AA where [A,] K,, learning rate 7)
1: Initialize w K. (1,....,]) 1) R.K,
2: function PLAY ACTION
3: p= 1/ プ w(i]
4: a~p
5: return a
|/ sample action
6: end function
7:
8: function UPDATE(f(.)
9: f min(1, ([( RRK
I/ rewards vector MW update
10: w w exp
return
12: end function
Algorithm 4 Distributed Causal Bayesian Optimization Multiplicative Weights (D-CBO-MW)
Require: parameters t, (.e 9, S2, kernel functions ky and prior means 14,0 0, Vi E [m]
1: Algo' t- MWU((A'), i ,,...,,, m, Algorithm 3
// initialize agents
2: for = 1, 1, do
3: Algo,.PLAY PPLALACTION()) i- -,,.... m
I/ sample actions and perform interventions
4: Observe samples {zi,,, Fi,t. 0
5: Update posteriors (-r,e(), {-))))
6:
for E I,...., do for a, E A; do
7:
Compute ((,)),(a,) = UCB (a,, a-i,, a.) for a, E A, using Algorithm 2 9: end for
8:
10:
UBD..T.DDDT,, ())), il,.,
end for end for
12:
B AN EFFICIENT VARIANT OF CBO-MW FOR LARGE ACTION SPACES
B.1 THE DISTRIBUTED CBO-MW (D-CBO-MW) AL.GORITHM
For case readability the pseudocode we pull-out some key functionality of the MW algorithm. which put into class called MWU described in Algorithm 3] Each agent is instance of this class, iee, each agent maintains its own set of weights over its actions, and updates to these instances coordinated by D-CBO-MW as described in [llgrithhm thought of as m instances of CBO-MW, where the action spaces of other agents are absorbed into A'. While for presenting the algorithm we always decompose A A₁ ... Am and have each agent control the intervention on one node, one could in practice choose to decompose the action space in different way. simple example would be having agent one control Ai A2 and thus designing the intervention for both X2
Conceptually it can be
When computing the U for a single agent E [m]] we will find the following notation convenient. Let aie A, the action chosen by agent at time t. a-i,t A_: A are the actions chosen at time t by all agents except agent i. Note that since the subspaces of the action space each agent controls are non-overlapping. A A U ;. When agent chooses actions in A,, for convenience we will from now on represent it as vector in A with ( at all indexes the agent cannot intervene. We do similarly for a-i,t- Then we use the notation UCB, (ai,s, a-i, a.) = UCB (a,, + j.jj.t a²).
B.2 APPROXIMATION GUARANTEES FOR MONOTONE SUBMODULAR REWARDS
In this section we show that D-CBO-ME MW enjoys provable approximation guarantees in case of monotone and DRsuumoodular rewards. Both such notions are defined below.
15

---

Published as a conference paper at ICLR 2024
Definition (Monotone Function). A function f A S Rm + R is monotone if for y.
f(z) - f(y).
Definition 2 ERRSSumoouularty,
Bian et al. 2017)). A function f A S R + R is DR- submodular if, for all æ S y E A. Vi E ml vk 2 such that (æ + ke;) and (y + ke,) E A,
f(a + ke,) (()) 2 f + ke,) f(y).
DR-submodularity is generalization of the more common notion of a submodular set function to continuous domains Bach (2019). For analysis, in particular, we assume that for every a', A', the reward function r r ., a is monotone DR-submodular in a.,.
consider ACBO as a game played among the distributed agents and the adversary. Our guarantees are then based on the results of [Sessa et al. (202T) and depend on the following notions of average and worst-case game curvature.
Definition 3 (Game Curvature). Consider sequence of adversary actions e4.....a.y We define the average and worst-case game curvature as
1=1 V Vr(2a d'dle
Cavg( (aug((a',)) (a', = inf
E [0,,1],
Li=IVrr(0, d'
Vr(2amazz d' E [0,
Cwel(a' 17
inf 2,5
|Vr(O, a
where amaz = amax= and amar is the largest intervention value single agent can assign at any index. If 20maz outside the domain of r, then the definition be applied to monotone extension r over Imm. A definition of game curvature for non-differentibble r is given in the appendix of Sessa al. (2021).
Curvature measures how close r(., a.) is to being linear in the agents' actions, with Caey = Cue 0 coinciding with completely linear function. The closer r(., a²,,) is to linear, generally the easier the function is to optimize in a distributed way, because linear function separable its inputs. Cwv
the worst-case curvature of r(,, af,,) across all rounds f, while Cang is the average curvature across rounds. The curvature of r(: ..,,) will change with t because a', will change across rounds.
We will without loss of generality assume that r(0, a') = 0 for all a'. If this did not hold then r(0, a') could simply be subtracted from all observations to make it true. Then, we can show the following.
Theorem 2. Consider the setting Theorem 7 1but with the additional monotone submodularity and curvature assumptions made in this section. Assume |Ai] = K for all i. Then, if actions are played according to D-CBO-MW with 3r = O B + V log (m/5)) and 1j = / (/8log(K)) then with probability at least 1 1-66 5,
r r(a a)) a OPT m ((B V yr + log(m/0)
N+1 A AN L. TTr)
(18)
m O (o.OOVVTioo (TTlog K + Tlog(2m/8))
with
a= max {1 Cavg Caog(ta',)) (1+ owe Cwella' (oc(
and OPT maxasA Et r(a,,,, is the expected reward achieved by playing the best fixed interventions in hindsight. B and pr are defined the same as in Theorem
Proof. We will find useful the notation of the regret of an individual agent E [m]. We will consider the regret of each agent to be not in terms of the reward but in terms of the feedback that agent receives: the UCB. We therefore define
T
T
R' (T)) = max
UCB$ (a, ami,, ab) - Σ
UCB (aias a-i,, a())
t=1
16

---

Published as a conference paper at ICLR 2024
It can be thought of as the regret of agent compared the best fixed action in hindsight, given that the actions all other agents are fixed, and the agent is trying to maximize the sum of UCBs.
Using the above definitions, and provided that UCB (.) are a valid upper confidence bound functions on the reward (according to Lemma 2), we can directly apply (Sessa et al. 2021 Theorem 1). This shows that with probability 2' the overall reward obtained by D-CBO-M is lower bounded by
m
Σ r(as, 22.00... OPT m Σ
Σ R (T).
where or is defined in Theorem and (,/22) is as defined in Lemma 2
We note that Sessa et al. (202T) stated their theorem for the where the UCB computed using single GP model (our setting with only reward node and parent actions), however the proof is identical when any method compute the UCB is used with an accompanying confidence bound in the form Lf 2
Then, we can obtain the bound in the theorem statement by further bounding the agents' regrets It (T). Indeed, because each agent updates its strategy (Line 10 in Algorrthh 4) using the MW rule (Algo rithm 30, we can bound each R' (T') with probability
2m. using Eq. (17) We can also substitute for (6/22) using Lemma 2] Via a union bound we get our final result with probability
C EXPERIMENTS
C.I FUNCTION NETWORKS
We evaluate CBO-MW on environments that have been modified from existing function networks Astudillo and Frazier (021). These have been previously used to study CBO algorithms Sussex et al. (2022). We modity each environment in two ways (Perturb and Penny) in order to incorporate an adversary, resulting in environments total. For all environments we tried to make the fewest modifications possible when incorporating the advensary in a way that made the game nontrivial while maintaining the spirit of the original function network.
Perturb environments allow the adversary to modify some of the input actions the agents. Penny environments incorporate some element of the classic matching pennies game into the environment. If node X; has an adversary action parent, part of the mechanism for generating X; will involve multiplying another parent by the adversary action. Because the adversary can select negative actions (see below), this results in dynamic similar to matching pennies.
Throughout the setup and theory we assume that there one action per node for simplicity. For many of the function networks experiments there may be 0 or more than one action per node. Similar theoretical results for this case can also be shown using our analysis.
In all environments we map the discrete action space [0, K - 1] to the continuous domain of the original function network. Using a as the continuous action at a single node and ä as the discrete action input that node, always
K-1 0.5 C1 + C2, where C1, C2 defines some environment specific linear map that usually maps to the input space of the original function network in Astudillo and Frazier (20TT) We use the same mapping for adversary actions in Perturb environments
mapping
For the adversary's actions in Penny environments, we use more complicated mapping from a' to a' to ensure that the adversary normally cannot select 0, which would result in trivial game that the adversary can solve by always playing a' = 0. If K even we use
a'
d'= =
C + C2, (1-2ee 0.5
K -
where E = 0.05. If K is odd we use
ā' + 0.5
d'
K (1
(1-2c)e-
-05 0.5 C + C2.
where 0.05.
17

---

Published as a conference paper at ICLR 2024
Dronwave-Penny
Dropwave-Perturb
Alpine-Penny
Ag
60
dg
83
X
Y
Xo
Y
X
X1
X2
Q1
Alpine- Alpine-Perturb
Sheenbookk-Penyy
Busenbrock-Pertuii
40
43
GO
Q1
Q2
X
X1
X2
Y
Xo
X1
Y
Xo
X1
Y
[
Ackley-Penny
Ackley-Perturb
X
X
60
01
(1
03
Y
ao
10
41
42
43
Y
X1
X1
Figure 6: The DAGS corresponding each task in the function networks experiments.
DAGs illustrating the casual structure of each environment are shown in Fig. For some environ- ments, we made the number of nodes smaller than the environment's 's counterpart in Astudillo and Frazier (202T) for computational reasons. We give the full SCM for each environment the end of this subsection.
To select hyperparamaters for each method we perform small hyperparameter sweep to select the best hyperparameters, before fixing the best hyperparameters and running 10 repeats fresh seeds. On all repeats the agent is initialized with 2m samples of uniformly randomly sampled a and a', where is the number of action nodes.
Fig. 7 shows the regret plots for environments not already shown in the main paper. As discussed, we find that standard non-adversarial BO algorithms often fail to achieve sublinear regret and that CBO- GP-MW is not at all sparse. That is, z5 m. Our (Therrm I suggests that most improvement will come in high dimensional settings with sparse graphs. This made clear by the superior performance of CBO-MW the Alpine2 environments.
MW is often the most sample efficient compared to GP-MW. Only on Ackley-
obtaining lower regret. This be understood by theory. Ackley-Penn
Here systematically list the SCM for each environment.
Dropwave-Penny a E [0, 20,2),.0 a' e [-1, We have
X, = =|a]|
18

---

Published as a conference paper at ICLR 2024
Drupesaee
Periiue Periurl
Rreebbmek Penny
Rosenbrock-
60+
CHO-MW [0un))
Cunniaativn Raggr
CBO MW (Oun)
MOBO
Ouzalative Roare
-0.0
CDO XIW (Omaa
MCBO
GP-UCBB
GP GP-UCB UCB
Conulalion
60
GP-MW
GP-MW
5.0
20
0.1
30
75
150
0
26
30
73
100
0
25
160
Rocand
Round
Roond
(a)
(b)
(c)
Ackley-Penn
Ankley Perturl
6-
(Oux)
CBO-MW (Ouns
Cummlativ Rlggett
MCCO
Conndaliio millen Begged
20
MCBO
GP-UCH
GP-UCB
GP-MW
0-
25
100
25
150
(d)
(c)
Figure 7: Regret plots for the function networks not already shown in Fig. 2
(3xo))
Y
+ 0.5.3 d
This is the original Dropwave from Astudillo and Frazier 2021 but with a modified input space and matching pennies dynamic the final node.
Dropwave-Perturb a E [010.4 10.24|2, E [-10.24/5, 10.24/5]*. Like many Perturb sys- tems, the adversary has smaller domain than the agent to prevent it from being too strong. We have
[[( ab)
01 x6)
1]
Xo =
y c3x()
2 + 0.5X7
This is the original Dropwave from Astudillo and Frazier (021) but with one of the actions being perturbed by the adversary.
Alpine-Penny
10, 1a0ss.c a' [1, We have
Xo -vao sin(ag)
For nodes X, with an adversary parent we have
X; - sin((a))) (a,)
and for nodes influenced by the agent have
= sin X
This is the original Alpine2 from Astudillo and Frazier (2021) but with an adversary controlling one of the nodes instead of the agent. We shift that adversary' action space that they cannot the output with fixed action.
Alpinc-Perturb
10, a' 20, Let a; a; + af for when X; has adversarial action input, and ā = a; otherwise. We have
Xo = v aa sin(
X si.)))(a.)
19

---

Published as a conference paper at ICLR 2024
Rosenbrock-Penny a [0, 1] a' E [0, 1]. We have
Xo -10((a) ag)² - -1- -1- 10,
X; (-100 -2²²² (1 11-ap a;)² + +10+ X--1
dy
where oe = 1 if there is no adversary over node i and otherwise a¹² = a
a E [-2, 2]*, a' E 1P3. Let ā; = a; + df for i when X, has an adversarial action input, and a; a; otherwise. We have
Rosenbrock-
Xo - 1000(a1 - ab)² - (1 - 00)² + 10,
X, = - 100 - -²²)² - (1 - (1=ā:)² + 10 + X
Ackley-Penny [-2,2] a' E [-1, Let d; at a² for when X; has adversarial action input, and a; = 0g otherwise. We have
Xo Σ aj
X1 4 Σ cOs (2Tā;),
Y = 20 exexp( -0.2 Xo) e.I.
Ackley-Perturb a [-2,22)) a' E [111, 1|². We have
Xo = 4 aj
Σ
Σ cos( (2Ta:),
X1 4
== 20a exp( 0.2 Xp) + x
This is the original Ackley from Astudillo and Frazier (221) but with matching pennies dynamic on the final node.
C.2 SHARED MOBILITY SYSTEM
We use the same SMS simulator as Sessa et al. (2021) and thus we largely refer to this regarding simulator details, unless otherwise specified. The simulator uses real demand data amalgamated from several SMS sources in Louisville Kentucky Lou (222I) We treat the system all transport units are identical. A single trip taken in the Louisville data at a specific time is treated single unit of demand in the simulator. The demand is fulfilled if the location of the demand (where the trip started in the dataset) is within a certain distance (0.8km Euclidean distance) of depot containing at least one bike. the demand for trip is satisfied, a single trip starting from the depot is counted and the bike is transported to the depot nearest to the end location of the trip in the dataset, after removing the bike from the system for 30 minutes to simulate the trip having non-zero duration. The simulator's 's use of real trip data means that the geographical and temporal distribution of demand, and its relation to the weather, realistic.
single SMS where
The depots are not in the original trip data but constructed from the trip data using a similar procedure to Sessa et al. (202T). The start location for every trip taken over the year clustered via k-means, and then clusters that are very close together are removed. This left 116 depots where bikes can be left. We consider a system with 40 bikes, which are distributed initially by 5 trucks that place all bikes in that truck the same depot.
We further allocate depots to regions. These are constructed by using trip data across the whole year, and using heuristic that clusters depots into regions so that there is low chance that any given trip starts in one region and ends in another. As shown in Fig. 8 this leads to nearby depots often being in the same region, which is reasonable. We get 15 regions Rí Ris.
20

---

Figure 8: (a) The allocation of depots to regions. Depots of the same colour belong the same region. (b) For our empirical evaluation of D-CBO-MW we use graph that computes trips for each region and then sums these up to get total trips. Here we show a simplified version for 2 regions R1 and R2. The total trips in the first region Xa, only depends on the number of bikes allocated to each depot in R₁ given by X X R1 [.]' This reduces the dimensionality of GPs used in the model. For simplicity we have removed the agent's action nodes from the graph since the relationship between Published as a conference paper at ICLR 2024
Ri
x1
XR1
R [R91
R2
x nz
R
B2 X R2
(a)
(b)
actions and bike allocations is fixed known mapping.
Agent action a, one-hot 116-length vector for which depot truck i's bikes are placed at.
We obtain 3 measurements for a' at the end of each day t. This is the day's average temperature, rainfall, and total demand (including unmet demand). These are part a' because they are out of our agent's control and not sampled i.i.d. across days. The agent must adaptively respond to these observations over time. Weather data is the real weather from that day obtained from Loc
Observations æ. give the number of bikes at day start in depot number i within region æ, is the total fulfilled trips that started region r. Reward is then the total trips in a day. All observations normalized to ensure they are fixed in [0, 1].
In Sessa al. (02I), 2 separate GPs are used to model weekday and weekend demand. For simplicity simulator that skips weekends, and therefore don't 't need separate model for the two types of day. No matter the algorithm used, the first 10 days of the year use the RANDOM strategy to gather exploratory data initialize the GP models for the .,,
The graph used by D-CBO-MW is given in Fig. 8). The relationship between the bike allocations Rao and bike distribution at day start {Xr Tr=R, is a fixed known function. The mechanism from the starting bike distribution in a region r (X!), adversary actions a' (weather and demand) and total trips in region between total trips Y and its parents is known (sum over parents). For this kind of graph the output of the Causal UCB Oracle (Algorithm 2} will always 7 1, because more trips in any region results in more total trips. For computational efficiency we therefore implement the Causal UCB Oracle to set 77 instead of optimising over 7).
the day (X,) is unknown function that must be learnt for each The relatio relationship
21

---

Published as a conference paper at ICLR 2024
Lymdon
jeffrrsoteee
Figure 9: Green dots represent demand for trips, black crosses are depot locations, and blue circles are scaled in size to the frequency that D-CBO-MW assigns bikes to that depot (averaged across all repeats).
22


Reviews:
[{"review_id": "AreeGeL3Jc", "reviewer": "Reviewer_xNam", "summary": "The authors propose an extension of the framework of CBO, named ACBO, where other agents (or external events) can also intervene on the system. This is to be able to model changes in the environment. The ACBO framework proposes a concrete algorithm to solve this problem, CBO-MW, which computes optimistic counterfactual reward estimates and enjoys cumulative regret bounds.", "questions": "If the authors clarify significantly the relationship with CBO, and modify the claims and narrative in the paper accordingly, I am open to increasing my score.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Interesting setting of doing BO with causal relationships among variables and external interventions\n- Interesting applied problem in the experiments", "weaknesses": "- The main weakness is the naming of the method, which refers to CBO (Aglietti et al 2020) and hereby its relationship with the CBO setting. The paper claims to show a generalization of CBO, which it seems to be an * algorithm * proposed in Aglietti et al 2020 as a solution to the \"Causal Global Optimization\" (CGO) problem. Here, in the abstract but also in the main paper, (1) no mention to the CGO problem is made (2) CBO seems to refer to the \"setting\" (somehow as a replacement to CGO), while the algorithm proposed here is CBO-MW. But CBO is not a setting, as said, it's an algorithm to solve the CGO under certain assumptions. In CBO, there are intervention *sets* and intervention *values/levels* (continuous-valued). I cannot see any of these here throughout, so it's unclear whether interventions on multiple variables here are excluded or what. In general, are you trying to also solve the CGO problem (a suitably modified version under external interventions, of course) or not ? Again on this point, the authors claim to compare using \"previous CBO benchmarks\", but there are no benchmarks actually from the CBO paper of Aglietti et al 2020, and the CBO-CW is actually *not* compared (nor experimentally, nor methodologically with a discussion) to CBO itself. There is also no \"causal prior\" associated to the GP as in CBO. \n- My understanding then from the above is that this work is actually not an extension of CBO at all (although I would like to hear from the authors), rather an extension of GP-MW which is mentioned a lot and compared to experimentally. \n- Strengthening my belief wrt to the \"distance\" of this work with CBO, the authors here evaluate performance with the **cumulative** regret. This does not seem to be used at all in CBO, where instead a simple regret seems to be used (Aglietti et al 2020).", "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": "", "extra_scores": {}}, {"review_id": "xXo4AHFPIW", "reviewer": "Reviewer_h5FK", "summary": "The paper studies causal bayesian optimization under certain kinds of adversaries who can pick additive variables in the causal graph post seeing the variables of the agent up to time t-1. \n\n- They derive regret upperbounds for a variant of the multiplicative weights algorithm and show scaling with sqrt(T). \n- The analysis is reasonably strong, but motivation could be made more clear -- the motivating examples are not necessarily adversarial.", "questions": "- Page 2: If X_m is a leaf, and it is the reward variable, then it has no parents? Did you mean X_0 is the reward variable?\n- You speak of Adversarial CBO, but assume a SCM. Do Causal Bayesian Networks involve the functional relations between the variables?\n- Why does cumulative regret go down with increasing rounds for Dropwave Penny in Figure 2?\n- What is the lower bound for regret?\n- You speak to a sqrt(t) dependence on regret, but the regret curve flattens for your experiment (and even decreases) in the graphs. Why do you believe this is happening?\n- Notation question: fi: Zi × Ai × A′i → Xi. Should this not be fi: Zi × Ai × A′i × Ω → Xi\n- You say \"Because mechanisms can be non-monotonic and nonlinear, one cannot simply independently maximize the output of every mechanism. We thus defer this task to an algorithmic subroutine (denoted causal UCB oracle)\". In this algorithm, you use a neural network explicitly. Does the error in functional approximation due to nn use not flow into the regret term?\n- Can line 7 in Alg 1 be amended to optimize over a' in [0,1] as well?\n- Why is it necessary to learn the causal function at each node, and not just at node Y, or at parents of Y? To bound reward estimates at Y, do we need equally good estimates at all nodes in the graph? (If not the search space for a,a' goes lower and therefore the number of calls to Alg2).\n\n\n## Typos:\n- Page 2 - \"for the parents this node\"\n\n## Suggestions\n- Please expand on the literature review.\n\n---\nNote: May be willing to improve the score based on author responses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Experiments show that the algorithm is strong for the use cases considered.\n- Well written problem statement.\n- For the model chosen, the analysis is sound.", "weaknesses": "- The related work ignores causal bandit literature?\n- The problem is not well motivated. Why is SMS adversarial and not stochastic?\n- The graph notations are confusing. The typical graph has 1 root node. But in causal graphs, we may have multiple nodes without parents.\n- The adversary cannot see the action taken by agent before taking its action. Is this adversary weak? You have considered that the agent can see adversary's action before choosing their own action set, but what about vice-versa?\n- The additive term Beta^{N+1} does seem high.\n- Note that \"Causal Bandits for Linear Structural Equation Models\" Varici et al 2023 show that the regret scales as length of the longest causal path in the graph for linear SCMs, whereas you consider N - length of path to root node. The former (not cited in your work), seems tighter.\n- Is the assumption of usage of only finite action spaces chosen from continuous Reals_[0,1] feasible? If we draw an epsilon net over [0,1], then the computation complexity of Alg 1 may rise.\n- There are exponential combination of adversarial choices, for each of which a counterfactual computation may be taken up. This is computationally demanding.", "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": "", "extra_scores": {}}, {"review_id": "Dazz0FLB8m", "reviewer": "Reviewer_aRF4", "summary": "The paper studies a model where an agent interacts with an unknown causal model that is partly controlled by an adversary. The problem is formulated as a Bayesian optimization problem. The paper proposes an algorithm based on multiplicative weights to solve the problem, which also uses the idea of the upper confidence bound algorith, that adopts an optimistic view in the face of uncertainty. Regret bounds were derived in the paper, and the proposed algorithm was evaluated empirically.", "questions": "- It is mentioned in the problem statement that the adversary does not know the action to be performed by the agent. Could you explain what the choice of the adversary's action is based on? If the worst-case analysis is applied here, does it matter whether the adversary know the agent's action or not since the adversary will always act in the worst way anyhow? Or does the adversary choose the worst action based only on history actions? But then do they know the agent's algorithm or not? The assumption that they don't know the agent's action seems a bit odd. \n\n- Could you explain the difference between your model and a model that combines stochanstic and adversary bandit?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The idea of studying an online causal model looks interesting.", "weaknesses": "I don't see any fundamental difference between the studied model and a standard bandit or Bayesian optimization problem, where part of the model is stochastic and part of it is controlled by an adversary. Therefore, apart from having a causal model in the story, the novelty of the contribution seems limited.", "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": "", "extra_scores": {}}, {"review_id": "18EHAAKHy4", "reviewer": "Reviewer_VBSi", "summary": "The authors present a method for causal Bayesian optimization in non-stationary where the authors also allow for multi-agent environments. They present result on eight synthetic environment and one (very interesting) real environment where they demonstrate competitive results.", "questions": "See strengths.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main review, with comments and questions, are all in this section owing to the flow in which this review was conducted.\n\n### Abstract\n\n- I think there is some ambiguity w.r.t. the first sentence: the DAG can be known but the relationships (the mechanisms) of the DAG unknown, or vice versa. Which one do you mean? In the original paper (Aglietti et al) the DAG was always assumed known but there are other settings where the DAG is assumed unknown.\n- Good abstract. Perhaps a bit more information on the experiments you performed (just the one sentence ought to do it).\n\n### Introduction\n\n- The supply example is great, but the way you introduce it in the second paragraph, reads a bit forced. Consider rephrasing. It doesn't sound very good at the moment.\n- If you are modelling a phenomena in an environment that is changing, why is it not possible to model that with a temporal DAG? Or dynamical DAG? There is plenty of that type of work being done. \n- Fig 1c - I am confused. Your blue nodes sound very much like standard non-manipulative variables and the idea of non-manipulative variables in causal setting, was introduced a long time ago. How are your blue nodes different?\n\n### Background and problem statement\n\n- There is some confusion here. In the abstract you said that $\\mathcal{G}$ was unknown and now at the start of paragraph one you say that $\\mathcal{G}$ is in fact know. Which is it?\n- Is there a reason you deviate from the standard SCM definition from Pearl with $\\langle U,V,P,F \\rangle$? It seems unnecessary to introduce new notation for a setting which is well defined and well studied. You are just saying, in different words and notation, the interaction between the endogenous and exogenous variables in the SEM. More confusingly though you say that the $\\mathcal{G}$ is part of your SCM definition whereas in the standard setting (well, Pearl's setting) the causal diagram is induced by the SCM, not part of it. See chapter 3 (Pearl, 2009).\n- What is the reasoning behind using soft rather than hard interventions? What would happen if you used hard instead?\n- There are as many actions as there are nodes $m$ in the graph? But then you are also intervening on the reward variable which is non-manipulative?\n- To check my understanding: actions are continuous, but there are a finite amount of continuous actions, the cardinality of the domain of each action is then $K$? Why isn't each action just continuous?\n- I think you should rephrase the uncertain parts of your problem statement: it is not the case that the causal model is unknown (this typically means the graph) but rather that the mechanisms of the SCM are unknown. You are not being precise enough at the moment to ward off ambiguity. Please change.\n\n### Method\n\n- I think this very important part deserves a deeper treatment, you say \"Contrary to standard CBO (where algorithms can choose actions deterministically), in adversarial environments such as ACBO randomization is necessary to achieve no-regret\" - why is that the case? Are you then saying that if you are using deterministic action selection it would be impossible to attain no-regret?\n- Consider using left-pointing arrows in algorithm 2 to make it more procedural, in place of using equality signs on line 4 and 5. That goes in general for all your algorithms.\n- How many times do you have to initialise the neural networks in algorithm 2 for this to work?\n\n### Analysis\n\n- It would be helpful if you gave an example of a Lipschitz continuous kernel, for uninitiated reader. I would also like to know what the consequence would be if you did not make this continuity assumption and how realistic it is?\n\n### Computational considerations in larger action spaces\n\n- Can you please comment on this line: \"even with a large number of action variables $m$, $|\\mathcal{A}|$ may still be small and thus CBO-MW feasible to implement\" - what is 'large' here? When does it become unfeasible? Some numerical ballpark figures would be helpful. \n\n### Experiments\n\n- To confirm: you are considering the causally sufficient setting i.e. you assume there are no unobserved confounders? If so, please state that early on in the paper (apologies if I missed it).\n- Would it also make sense to also compare against CBO? Don't worry this review is not conditional upon you doing that, I am merely wondering why it is not part of your analysis, seeing as you talk about it early on.\n- The SMS example is _great_. Really enjoyed reading that.", "weaknesses": "See strengths.\n\nNote: I have given this is a five to start with. I would be happy to increase my score following author engagement.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)