Contextual Causal Bayesian Optimisation
Authors: Vahan Arsenyan
Antoine Grosnit
Haitham Bou Ammar
Arnak S. Dalalyan
Venue: ICLR 2026 Poster (2026)
Keywords: Bayesian Optimization
Causality
Optimal Control
Primary area: optimization
TL;DR: We extend causal Bayesin optimization to contextual scenarios and provide the first upper bound on the regret of causal BO methods that covers both contextual and context free setups.

Abstract: We introduce a unified framework 
for contextual and causal Bayesian optimisation, 
which aims to design intervention policies 
maximising the expectation of a target variable. 
Our approach leverages both observed contextual 
information and known causal graph structures 
to guide the search. Within this framework, we 
propose a novel algorithm that jointly optimises 
over policies and the sets of variables on which 
these policies are defined. This thereby extends and 
unifies two previously distinct approaches: 
Causal Bayesian Optimisation and Contextual 
Bayesian Optimisation, while also addressing 
their limitations in scenarios that yield 
suboptimal results. We derive worst-case and 
instance-dependent high-probability regret bounds 
for our algorithm. We report experimental results 
across diverse environments, corroborating that 
our approach achieves sublinear regret and reduces 
sample complexity in high-dimensional settings.

Arnak Dalalyan CREST, ENSAE, IP Paris, FR Published as a conference paper at ICLR 2026
CONTEXTUAL CAUSAL BAYESIAN OPTIMISATION ATION
Vahan Arsenyan CREST, ENSAE, IP Paris, FR
Antoine Grosnit
Haitham Bou-Ammar
Huawei Noah's Ark Lab, UK
Huawei Noah's ' Ark Lab, UK
ABSTRACT
We introduce a unified framework for contextual and causal Bayesian optimisa- tion, which aims to design intervention policies maximising the expectation of a target variable. Our approach leverages both observed contextual information and known causal graph structures to guide the search. Within this framework, we propose novel algorithm that jointly optimises over policies and the sets of variables on which these policies are defined. This thereby extends and unifies two previously distinct approaches: Causal Bayesian Optimisation and Contex- tual Bayesian Optimisation, while also addressing their limitations in scenarios that yield suboptimal results. We derive worst-case and instance-dependent high- probability regret bounds for our algorithm. We report experimental results across diverse environments, corroborating that our approach achieves sublinear regret and reduces sample complexity in bigh-dimension settings.
INTRODUCTION
Bayesian optimisation (Garnett, 2023) a powerful approach for optimising expensive black-box functions, often formulated as conditional expectations of target variable given that intervenable variables are assigned some specific values. In settings where intervenable variables exhibit causal relationships, specialised Causal Bayesian Optimisation (CaBO) algorithms can achieve superior performance by strategically focusing on select subsets of variables (Lee & Bareinboim, 2018). The critical challenge is to identify these subsets efficiently, since exhaustive search is computationally intractable and sample inefficient.
On the one hand, existing CaBO research develops specific tools to reduce regret by leveraging the causal graph assumed to be known. Consistent with prior work (Aglietti et al., 2020b; Zhang & Bareinboim, 2022), we restrict attention to precise interventions (Pearl, 2009, Chapter 3) and assume the graph is given. Although extensive work on causal discovery provides methods for inferring such graphs (Spirtes et al., 2000; Hoyer et al., 2008; Hyttinen et al., 2013; Duong et al., 2025), this direction lies beyond the scope of our study. On the other hand, Contextual Bayesian Optimisation (CoBO) leverages observable context variables but is constrained by a fixed policy scope, that is, a fixed tuple of intervenable and contextual variables. As we demonstrate in the example in Section 2, this fixed scope constraint can lead to provably linear regret, which suboptimal.
Optimising over multiple policy scopes arises in several domains. In complex environments such as video games, fully specifying the state and action spaces is intractable, both computationally and from an optimisation standpoint, practitioners adopt alternative design choices (Berner et al. (2019), Vinyals et al. (2019),, each inducing a distinct policy scope. In portfolio optimisation, multiple strategies are proposed, each controlling particular sets of portfolio parameters conditioned market observables (Cakmak & Özekici (2006), Cakmak et al. (2020).. In neural architecture search (Elsken al. (2019)), multiple strategies exist: one may monitor gradient and activation magnitudes and adjust network width and weight initialisation accordingly; another may track test-time performance and the generalisation gap, adjusting learning rate, gradient clipping, and depth. While jointly controlling all architectural parameters and conditioning on all performance metrics might seem optimal, the resulting search space is infeasible, so researchers adopt heuristic, scope-specific strategies. These examples fit naturally within our framework of optimising over multiple scopes.

---

Published as a conference paper at ICLR 2026
The need for our proposed framework emerges from three critical observations discussed above: (1) overcoming linear regret in CoBO requires extending beyond fixed policy scopes, (2) the exponential growth of possible policy scopes with respect to the number of variables makes exhaustive search computationally intractable, and (3) while causal relationships can inform policy scope selection, existing CaBO approaches do not incorporate contextual variables. In response, we introduce unified framework for contextual and causal Bayesian Optimisation (BO).
Our framework, termed CoCa-BO for Contextual-Cants Bayesian Optimisation, is designed to reduce the search space of policy scopes and guarantee convergence to the optimal policy. It addresses the challenges of applying the causal acquisition function (Aglietti et al., 2020b) for policy selection in contextual settings. We present analytical cases where existing methods fail, and show both theoretically and experimentally that CoCa-BO converges to the optimum. Experimental results further demonstrate that CoCa-BO achieves lower sample complexity in large-scale systems and outperforms existing methods.
Below, we summarise our main contributions:
We propose novel method for context-aware causal Bayesian optimisation that addresses policy selection in context-aware settings with multiple possible policy scopes.
We provide general, scalable, and practical framework for implementing causality-awe aware optimisation algorithms, along with a suite of environments for evaluation and benchmarking.
Assuming Gaussian process priors, probability upper bounds on the regret of our method. These bounds are valid under mild assumptions on the kernels of the Gaussian process priors and highlight the impact of the number of steps on the cumulative regret.
establish both worst-case and instance-dependent, high-
Notation Random variables are denoted by capital letters like X and their values by corresponding lowercase letters like The domain of random variable X is denoted Ex. Sets of variables denoted by bold capital letters and the set of corresponding values by bold lowercase letters. Vectors always considered as 1 1-column matrices and for any vector x, denote by x its transpose. Identity matrices are denoted by I without indicating the dimension, which is clear from the context. We denote by N the set of strictly positive integers, and by [m]] the set of strictly positive integers smaller than, or equal to, m E N For x E RTM, |x|| >m i=1 [ and ||x| maxisism |ra))-
2 BACKGROUND
This section aims to provide a background on possibly optimal mixed policy scopes and on their importance for the contextual decision making setup where the causal graph is available.
Preliminaries We consider the following general problem: in the absence of any intervention, the environment generates a random vector V according to a probability distribution denoted by PV on Tv. We are allowed to perform certain interventions (a precise definition will be given later) on the components of V. which result in modifications of their joint distribution. Each set of admissible interventions π, referred to policy, induces new distribution Pt vv. II denotes the set of all admissible policies; it will be specified below and may be infinite and even uncountable in general.
We assume that objective is to identify a policy that leads to nearly maximal expected reward. More precisely, for given reward function r Xv + R, our goal is to find a policy क such that
(*+) = E [v()),
the expected reward under â, is close to the optimal expected reward supaem Epg (r()). We will focus on the case where r( r(V) (e, V), where is an element of the canonical basis. This is equivalent to assuming that Y : r (V) is component of V.
To define what a policy is and how the set of admissible policies is specified, we follow (Lee Bareinboim, 2020). Assume that pe pa is given by a structural causal model M (Pearl, 2009, Chapter 7). A structural causal model (SCM) 21 is a quadruple (V, U, Pu). where and U are, respectively, a set of observed and latent variables. JF is collection of functions such that for each V E V, there exists fv E F that determines the value V based on other variables in V VUT U. That is, for some PAv C V \ {V) and Uy U, V = fv (PAv, Uv). The latent variables U are jointly distributed according to Pu. Consequently, the SCM 21 induces a joint distribution p over the observed variables V.
2

---

Published as a conference paper at ICLR 2026
The SCM Di also defines directed acyclic graph (DAG) 9 with two types of nodes. First-type nodes represent variables from V, while second-type nodes represent variables from U. Only first-type nodes have incoming edges. An edge from node corresponding to variable Z to first-type node corresponding to V indicates that Z E PAy y Uu.. The policies we consider in this paper are defined on mixed policy scopes (MPS), which should be compatible with the graph & of the SCM Dt. The following definitions and terminology are based on (Lee & Bareinboim, 2020).
Definition (Mixed policy scope), Let X' SV {Y} and C' CV) {Y} be two sets, termed the set of intervenable variables and the set of contextual variables, respectively. A mixed policy scope S compatible with G is defined as a collection of pairs (X; Cx) such that X X", Cx C 1 {X). and the following compatibility condition is satisfied. The graph Gs obtained from 9 by removing edges into X and adding new ones from Cx to X, for every (X; Cx) E S, remains acyelic.
We denote the set of all MPSs compatible with & by Sig.. The notation X(S) designates the set of intervenable variables for an MPS S, and C(S) the contextual ones.
Definition 2. A mixed policy based on S is a collection = (xxI where C is a mapping from c to Æx-
For every MPS S E S[G), the set of all policies based on S is denoted by Tss. We define Mg Usestg Iss as the space of all policies.
If G is the causal graph of an SCM IN = (V, U.F.Pu). every mixed policy т based on S E S[g] defines new SCM 2 (V,U,F* Pt) with F' obtained as follows. For each intervenable variable X E X(S), replace the function fx from F by the new function xx|Cx &cx + Xx. This new SCM 21" induces a new distribution on V, denoted by PV.
The agent is given the graph G of an unknown SCM Wt. At each step / =
a) the agent chooses mixed policy scope S. E S(g) and a mixed policy E Iss, based on the past observations D (Sy, ne, ce. ge)
b) the environment generates v, according to the distribution PV:
c) the agent observes the components (c,, y1) v;, vt, corresponding to contextual variables of
S₁ and the reward.
The agent aims to minimise the regret RT = T suprem ((T) ΣT ((TT)) with ((T)) = Epg [Y]
Possibly-optimal mixed policy scopes Our work focuses on a special set of MPSs that are possibly optimal under an SCM compatible with G (Lee & Bareinboim, 2020). Let μ²s sup ((T) be the largest expected reward corresponding to the MPS S.
Definition 3 (Possibly-Optimal MPS (POMPS)). Given YYY C*), we say that S S(g] is possibly-optimal MPS if there exists an SCM Mi compatible with the graph & such that nó > uss for any S' S[G] different from S!.
We denote by S [g] the set of all POMPSs compatible with G. The policy considered in this work selects S, from (G].). While further restricting the candidate set could reduce computational cost, would risk linear regret: for any S E S* [g]. there exists an SCM DI compatible with G for which optimal. Thus, given only G, the agent cannot exclude any POMPS from the set of candidate scopes without potentially discarding the optimal policy and incurring linear regret.
Example of CoBO/CaBO's failure modes Let us illustrate through an example the role of incor- porating both causal and contextual information. Specifically, we demonstrate that neglecting either component can lead to regret that is not sublinear in the number of steps T. Consider the example in Figure I, where the context variable C' influences both the intervenable variable X₂ and the outcome Y. The causal graph G also includes the intervenable variable X1, which affects X2.
First, we observe that there exists a policy achieving an expected value of Y equal to 1/3. Specifically, (1)
consider the mixed policy (1) defined on the MPS S = {(X;; C)} by π "x lc (c) = -c. Under this policy, we have E,,v) [Y] = a, [U3] E, [x + a [C] = E!U?! 1/3.
SS must additionally be non-redundant under optimality. Please see Definition 4 of Lee & Bareinboim (2020).
3

---

Published as a conference paper at ICLR 2026
U
C
2
U1, Uniform([-1,1]
Xi U1, C= U1
22 = U2
X1
X2
Y= U22 +
(b) Structural causal model Figure 1: An SCM and its DAG G for which CoBO and CaBO fail to converge to the optimum.
(a) Graph G
we ignore the contextual information and rely solely on the causal relationships, at each step the choice reduces to one of three options: intervention, intervention on X1, intervention X2. Intervening simultaneously on both X2 and X₂ excluded because, according to the graph depicted above, intervening on X2 renders the value of X₁ irrelevant to Y. In the case of no intervention, we have E[Y] 1/a V/1 401] < 1/6. If we intervene on X2, becomes independent of U2 and the expected value of Y reduces to zero. Finally, intervening on X1 by setting it to fixed value x yields ==)) [Y] 1/ (e (x U1)²| < 1/3 e 1/s. Therefore, for every policy that does not incorporate the context, the expected reward is strictly less than 1/4, and consequently, least 7/12.
the cumulative regret of any such algorithm
Finally, suppose we ignore the causal structure and rely solely on the contextual information. Then, the decision reduces to selecting function x x(2) c + (#1, that specifies the values of (X1.Xx) given C c. Under such a policy, B, Y ( [U2X2 CJ |U| 22 (C) + C.. Note
that 2 E[[| = 0, and Th² (C) being deterministic function of C, is independent of U2. Therefore, E,,ca) YY] = O. This shows that, for any context-only policies used across the steps, the expected reward is zero. Thus, neglecting the causal structure leads to regret of least T/3.
PROPOSED ALGORITHM
In this section, we provide high-level description of the identification of intervenable scopes and the selection of optimal policies. We then formalise the contextual BO strategy used within each scope. Finally, discuss why CaBO's POMPSs selection strategy is inadequate in contextual settings and motivate our alternative approach.
A: ititttatinn
Obarrve context c. P(C..)
DP,, with x,
POMPS (1())) Os(ee)) p(1))//
(m))
X, arg max UCB ox)
Xi,
Sw(s.) Ou(nn)) + pu(mtw/ vin
Set X, gi
(a(a)) with UCB (x).
POMPS Selection
Action Selection
Update
Figure 2: At each iteration t, we select a POMPS using the running average of the UCB evaluated at the points x, and Ct, plus an exploration term p: p=(n))/ ( where n; is the number of times POMPS i has been chosen so far. We then implement the intervention X;, observe the target yi under this intervention, and update the parameters the algorithm. For more details please see Algorithm
High-level description Our method, outlined in Alg. 1, has 3 main components. The first compo- nent is the POMPS function, which computes the set ş S* [9] (Lee & Bareinboim, 2020) for given causal graph G. This computation involves brute-force search over MPSs, with computational complexity scaling exponentially in /V]. However, this step highly parallclisable, a feature we exploit in implementation. Our definition of the contextual variables as C' V \ (X" U (Y)) suffices to ensure that optimal POMPSs are not missed (Lee & Bareinboim, 2020, Prop. 2). A visual overview is provided in Figure 2.
The method proceeds as follows: at each step t, based on historical data D = ((S,, ni, Ct v=] first selects POMPS S, from St, then chooses policy m. E ss.
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 Contextual Causal BO (CoCa-BO)
Input:
causal graph 9 on the nodes V, the target Y E V, the set of intervenable variables X' C V, domain variables Iv, number of iterations T. We consider C' V (X* (X* (Y))).
Compute S = POMPS(G, X*) and create A MAB
for S E S" do Create Opts = BO(X(S), C
for t = 1 to T do
Select POMPS: S A.suggest()
Implement Ts provided by Opts.
Observe y, xs. Cs drawn from p Optg. polg-update((1) y, xs, cs); A.update (y, S Opts)
end for
This amounts to choosing an interventional value for Xs. after observing the context c asso- ciated with the variables Cs. Consequently, we may equivalently write the historical data as D = {(S, c2, X4, y: hete-1]- 'he second component is the selection of a POMPS from the finite set S* using MAB. Each POMPS serves as an arm, and the algorithm aims find the one with the largest mean reward p Formally, we may view MAB as mapping A St + R. At each step f, it selects a POMPS S; E argmax A(S). and after observing (Ct, xt: Me), it updates the value A at S; while keeping all others unchanged. Details of this update step are provided in Algorithm 2. The third component of our method is Bayesian Optimisation routine with Gaussian process surrogate, used to choose the intervention value of Xs, once the POMPS S, is selected and the context C, is observed. This component described in more detail later this section. Finally, the selected BO optimiser is updated at each iteration using the newly observed values. These updates involve Gaussian process posterior updates, which require inverting a T matrix, and thus have computational complexity ((T3).
Contextual Bayesian optimisation policy For a given scope S selected at step f, the contextual Bayesian optimisation assumes that y/ = g(x,, C₂) - onht, where g is random Gaussian process defined on Xx5 X ICs. C₁ is a random vector drawn from P2g- and & standard Gaussian random variable. All three quantities (g, Ct Ex) are assumed independent. To provide more details, we define the set [f]s = {i [t] S = S} and denote by D's {(xss, c's, y²) he(t) the subsample of D' corresponding to those steps where the scope S was selected. The Gaussian process has zero mean and covariance function i: (3xx )² - R. Given the dataset D's, the posterior distribution of the output for test point (x, c) is a Gaussian N (HHpusi (X, c), of o (x, c)), where
Mts + aTT) Y(dss Mpost (x, c) -k (x, c) (K
(I) with I the identity matrix of appropriate size, Yitls the vector of observed targets in D's, K [1]s the kernel matrix of all (x, c) pairs in D's, and kig (x, e) the vector of covariances between the test point and each training point. The noise level 0, is tunable parameter.
poat (x, c) = k((xx c), (x, c)) |ts (x, c) (K [t]s + +0,1)
-1
kigja (x,
In our method, we deploy HEBO (Cowen-River of-the-art BO algorithm (Turner et al., 2021) capable of optimising in contextual settings and handling both continuous and discrete variables. HEBO's Gaussian process model includes learnable transformations of both input and output, which makes it robust to heteroscedasticity and non- stationarity. All methods described in Section 6 use HEBO as the BO subroutine.
al., 2022) for each POMPS, as it is a state-
POMPS selection Our algorithm performs POMPS selection using historical values of the acquisi- tion function combined with margin (see Section B). In contrast, CaBO selects the next intervenable set based on the values of the acquisition functions associated with each GP. This strategy is motivated by the intuition that the optimal intervenable set, together with its optimal interventional values, should yield the highest reward. Accordingly, acquisition functions are expected to reflect this pattern, particularly in regions of low uncertainty. However, this approach becomes unsuitable in contextual settings, where the optimal values of acquisition functions inherently depend on the observed context. This dependence introduces a fundamental issue: the comparison performed between acquisition functions evaluated at different contexts, which undermines the validity of such comparisons. Such
5

---

Published as a conference paper at ICLR 2026
comparisons may lead the optimisation process to switch arbitrarily between scopes based on the observed context, potentially causing instability or divergence.
Our selection criterion U., defined in Algorithm 2, is the rumning average of the UCB values the evaluation points for each POMPS instance. As shown in Lemma 2, this quantity simultaneously upper and lower bounds the empirical mean of the target under the optimal policy, up to additive terms. These terms decay sufficiently fast to ensure that suboptimal POMPS are selected only rarely, formalized in Lemma 4.
REGRET BOUND FOR COCA-BO
In this section, prove that the CoCa-BO algorithm outlined in Algorithm 2 achieves sublinear regret. For this purpose, we place ourselves in a more general setting, which we refer to as multi- function BO. We assume that we are given integer sets (xx(()) Nee mi and (Etm) At each step & E N we first select an index i, E [m]] and then observe random variable C₁ drawn from RC(())- Based on C₁ and the past observations, we choose X, from (x(i,) and subsequently observe the reward Y,. In this formulation, the indices [m]. henceforth called arms, correspond to POMPSs; the variables C, correspond to contexts; and the variables X., henceforth called actions, correspond interventional values.
N", together with two sequences of
We assume that for some random processes fm and for some unknown context distributions Pi,..., P. the reward takes the form Y,, (X, C₁) fzz where conditionally to é fi...... Jm C, is drawn from P.,, and conditionally to iz. f1......f....................... fm and C2, E,,N( o²). A more detailed description of the setting can be found in Section B.1.
Assumption 1 (Comvex-compact domains). For every i E [m]. Xx(i) and EC() convex and compact. Furthermore, there exist constants ri, r >> di, d' N such that Xx(() r. and Ico) C [0, r for every i E [m]. We set F; = r and d; = d, V d. Assumption (Smooth and bounded kernels). Processes fi are independent, each f, be Gaussian with zero mean and covariance kernel k,. The covariance kernels k; are bounded, i.e., for some K1, Ki > O, we have maxx. ky ((x, c); (x, c)) S k, Furthermore, there are constants 1 4 > such that, for any E (0, 1) and for any [m], with probability at least 5
sup V c)ll I (oloog(d.//)) x.C
(2)
Note that these assumptions are not very restrictive compared to those usually imposed Bayesian optimisation. In particular, it follows from (Ghosal & Roy, 2006) that if the kernels k, admit fourth-order mixed partial derivatives, then the path smoothness condition (2) is satisfied.
For brevity, defer the precise definitions of the subroutines UCB-UCB and HEBO from Algo- rithm 1 to Section B. We only mention here that, in the Bayesian optimisation subroutine, an upper (8)
confidence bound is constructed from the posterior means 14,- and standard deviations 0; of the i-th GP at time f, together with a sequence of tuming parameters (8,(n)) nEN.. As for the arm-selection subroutine MAB-UCB, it chooses the arm with the largest average UCB over past observations, plus a penalty term involving the sequence of tuning parameters (ps(n))ie To ease that statement of the main theorem, set
(8)
Br = max max (2(n) [m[m RST
and PT = max max (n)..
DST
Let = (C.,) = maxx fx c) (dcc and I argmax; As. Clearly, AAs depends on /i and I' depends on f = (f1,-.., Sm). but for simplicity of notation we do not make this dependence explicit. We also write μ¹ maxie(mi pq. The cumulative regret is then
T R =
C.) If f
In words, the regret is the difference between the context-averaged reward of oracle strategy (which always selects an arm with maximal context-averaged reward and plays a context-optimal action) and the context-averaged reward of our algorithm. This notion of regret, specific multi-uunction

---

Published as a conference paper at ICLR 2026
BO, differs from those considered in the MAB literature (Lattimore & Szepesvári, 2020) and the BO literature (Srinivas et al., 2010). In MAB, the reward of a chosen arm is constant across rounds, whereas in our setting, the expected reward evolves as the estimated maxima of f., are progressively refined. On the other hand, unlike in BO, our regret compares the context-averaged maximum of fi, 14", which may correspond to the optimal value of another function fμ- These distinctions introduce additional challenges in establishing bound for regret Rr of the procedure defined in Algorithm 1.
A key quantity characterising the regret of the algorithms commonly used in BO with Gaussian process prior is the maximum information gain (Srinivas et al., 2010). Denoted by 7(n)), the maximum information gain of the 1th GP fi over horizon n. defined by
1 max log det(I - KK,A),
(nn))
A:|A|=n 2
where the maximum is over all sets A C (x)) EC(() of cardinality n and K is the matrix with the general term (2 z'), z, E Xx(e) &C(i). We refer the reader to (Vakili et al., 2021) for results on bounding the maximum information gain in terms of n and the kernel parameters. Based on y/ (n), we define the worst-case-an and arm-averaged information gains by
max 7/ (T), TT
and
'T-
max B.
Σ m(m.).
KE [m]
where the last maximum is over all vectors n (M1, mm) E N summing T.
Theorem 1. Let d E (0, 1/2), A = (AI...., ....) be the vector of sub- uub-optimality gaps defined by A; = 11" H4 and 1 (i: A; 0). Let Assumptions I and
fulfilled. There exist constants A1, Az, As depending only on a, v. (Kis T2. Te:r))) (mm). such that if the parameters 3g and p: satisfy
(n)n) A pn)) 2 Aid, log (Armd,n/5)
for every i E [m]] and every E N then regret (6) of UCB-BO Algorithm 2 applied up to horizon T, with probability at least 1 28, satisfies for all T N the following inequalities
Rr S A2t ml (V BITT pr) + ||
(3)
Rr S Aa VIT ( WBTiT + pT) + (BTTT + PT)
Σ 141"
Σ
1 A.
ml +
+||A|l
(4)
We now provide several comments on the upper bounds in Theorem 1. First, the term |اه in the regret bounds is unavoidable. It arises because the algorithm plays each of the arms independently during the initial m rounds. However, since this term is 0(m) and independent T,, its impact on the asymptotic regret is negligible. Aside from this (m)) term, the bound in (3) is independent of the functions (fi,..., fm.) fm) we therefore refer to it as a worst-case bound. For kernels with exponential eigendecay (c.g.. the squared exponential kernel), the parameter "T most polylogarithmic in T' (see Table in the supplementary material). Hence, with appropriate tuning, the worst-case regret is of order /mT max; d, up to polylogarithmic factors in m and T. Notably, this yields a vT polylog(T)) dependence on T, a significant improvement over a linear regret.
One might expect the regret dependence on m improve beyond vm when there a significant gap between the optimal and sub-optimal arms. This is indeed the case, as captured by the instance- dependent bound in (4). Under mild assumptions on the Gaussian processes (see Section C.2), the set of optimal arms I* is almost surely a singleton. In such cases, the leading term of (4) is of order VT max; d, (up to polylog factors), improving upon the worst-case bound by factor of vm. This improvement holds when the sub-optimality gaps A, for & I' are bounded away from zero; otherwise, the term Eigr 1/A; may dominate.
To the best of our knowledge. Theorem presents the first regret bound not only for our proposed contextual-causal BO framework, but also for the more established Causal BO (CaBO) setting.
5 RELATED WORK
The integration of causal knowledge to improve policy learning is an active area of research (Lee & Bareinboim, 2018; 2019; 2020), with recent progress both conditional and unconditional
7

---

Published as a conference paper at ICLR 2026
policies (Aglietti et al., 2020b; Zhang& & Bareinboim, 2017; 2022). Our work builds and extends this literature. Below, we summarize the most related lines of work and contrast them with our contributions.
Causal Bayesian Optimisation (Aglictti et al., 2020b) uses the causal graph and a causal acquisition function (cAF) to search over policy scopes, treating non-intervenable variables unobserved. In contrast, our method explicitly leverages contextual variables and searches the joint space of intervenable and contextual variables. This not only leads better solutions but also overcomes the instabilities of cAF in contextual scenarios, Contextual Bayesian Optimisation conditions interven- tional choices on observed contexts but typically treats all controllable variables as intervenable. This can prevent recovery of the optimal policy. By searching over the set of POMPSs, our method avoids this suboptimality.
Functional Causal BO (Gultchin et al., 2023) places GP prior on (u(T)) via finite RKHS expansion, .V T(.) > (c')( Although this permits distance-based kernels, the critical choices of N, ag and c' are unspecified, hindering reproducibility. Furthermore, the optimisation of acquisition functions within this framework is also not addressed. In contrast, our method requires no such finite expansion, avoids the associated optimisation overhead, provides theoretical guarantees, and is accompanied by a public implementation tested on diverse environments.
Model-Based Causal BO (Sussex al., 2023) assumes specific structural causal models (V (v( + Uv) with restrictions on the noise terms and requires no unobserved confounders. Without any reduction of the search space, it considers only a limited family of interventions representable as parameter perturbations of the structural functions fv. Sussex et al. (2023) prove that RT S ( (K (Tr)), where K is the maximum in-degree, N is the length of the longest path to Y, fr and "r are similar to those defined in Section 4. Note that both the factor (K 3T) ) and [V| can be very large (see Section A.3). In contrast, conditions and the bounds scale more favorably; in the setting with no unobserved confounders, the set of POMPS is singleton (Lee& & Bareinboim, 2020), leading to significantly improved scaling.
theory applies under more general
The method of (Zhang & Bareinboim, 2022) also optimises over POMPS. However, it restrictively assumes that the domain ky is discrete and finite, an assumption not required by our approach. The regret bound established for causal-UCB" is sublinear in T. but it scales at least as the sum of the square roots of the cardinalities of the domains of the variables in V.
Another MAB-based method that utilises causal knowledge is proposed by Lattimore et al. (2016). It is the first to show that causal bandit framework subsumes the classical setting. Their method enjoys favourable regret bounds and is computationally efficient. As with Zhang & Bareinboim (2022), it assumes all variables have finite support. However, does not consider contextual interventions and assumes the absence of unobserved confounding.
Multitask GPs (Bonilla al. (2007)) learn similarities across the outputs of multiple functions and are useful for optimisation over multiple tasks that share inputs. Aglietti et al. (2020a) formalise when information sharing is possible under a known causal graph: tasks differ their sets of interventional variables but share the same target variable. They show that sharing is possible only if every variable confounded with the target does not simultancously have unconfounded incoming and outgoing edges. However, they study optimisation without contextual variables, and their information sharing mechanism requires computing high-dimensional integrals. Identifying assumptions that enable information sharing between POMPS without strong restrictions, and computationally efficient mechanism to realise it, remains an open problem.
6 EXPERIMENTS
We evaluate the proposed method against CaBO and CoBO across a series of experiments. For each experiment and optimiser, we report the time-normalised cumulative regret Rt + Σi f where A = F [Y] - y/1 the immediate pseudo-regret at iteration We also track the cumulative MPS selection frequency. i.e., the fraction of times each MPS has been selected up to iteration t. We consider two configurations.
Configuration I: Both the proposed method and the benchmark method can achieve the optimum. We aim to assess the additional cost introduced by the proposed method in terms of sample com-
8

---

Published as a conference paper at ICLR 2026
CaBO Asp.
EARO POARS
MPS selectio fespennyy
MPS eibetinn Eneuumnc
MPS selector frspaney
0.4
MPS selectioo Brequncc
Axp,
Sua.
Aop.
S Sia.
26
OvCa-B0 POMES
DaCeilo POMPS 0 <x/0> -Q- Xxj0>>
-0- < -X10
0.3
9-00-0000 0000000000000
Boee cunn regeed
Co -0- CaBO
Neemelien menelleedd cuzalltive Peturt
Normalees comedation arospve.
162
Nomualreed eumulativ repret
CoCa 30 CaBO
CalOO
20"2
26
106
301
000
Nambor of stage
Number stops
Namber stops
Number of steps
(a) CaBO vs (L.
(b) CadO CO
(C) CoBO CoCa:BO
(d) CoBO CoCo-BO
Figure 3: Top: frequency of selecting the corresponding POMPS POMIS (omitted when there is only one candidate). Bottom: time-normalised cumulative regret Rr.
plexity. In environments with many observed variables, CoBO results an expansive optimisation domain, requiring a substantial sample size. Our method leverages the independencies encoded within the causal graph to reduce the optimisation domain. For instance, in another example reported in Appendix A.3, the dimensionality of the domain is reduced by factor of 22.
Configuration II:
The benchmark method cannot achieve the optimum. We empirically confirm that there cases where neither CoBO CaBO converges to the optimum, leading to linear cumulative regret. In the same cases, we demonstrate that CoCa-BO converges to the optimum policy and has sub-linear cumulative regret.
All experiments were conducted with 110 random seeds over 700 iterations, corresponding 700 distinct interventions. We used single-node system with 120 CPUs, though the experiments can also be reproduced on a single-core machine with 16 GB RAM. Results are reported as averages, with error bars denoting 1.96 standard errors.
CaBO vs CoCa-BO To compare CaBO and CoCa-BO under the two aforementioned configurations, we consider two SCMs based on the graph of Fig. 4 below (Ferro et al., 2015; Thompson, 2019).
In this example, the variables PSA, age, BMI, cancer, aspirin and statin observable, but only the last two are intervenable. Prostate-specine antigen (PSA) (Wang et al., 2011), 1), used to detect prostate cancer, is our target. Here, the set of POMISS is {Ø, {Aspirin], {Statin), {Aspirin, Statin)) and there is only one POMPS, namely {Aspirin; Age, BMI); (Statin; Age, BMI)..
First Configuration: When SCM is such that the optimal value of the target is the same across all values of the contextual variables, CaBO can attain the optimum. This requires specific alignment of the SCM parameters, which may be unstable and sensitive small fluctuations (Pearl, 2009, Ch. 2). Such an SCM is defined in Section A. 1.1. The optimal values at which Statin and Aspirin are controlled to minimise PSA are the same for all values of Age and BMI, that is V( age, bmi) E X Age FBMi
argmin E do (dopiii, statin), age, bmi] argmin F| do(aspirin, statin)). (aspirin,statin)
(aspirin,statin)
We show that the minimum above is attained for aspirin= 0 and statin= Empirical results for this SCM appear in the first column of Fig. 3a. Since CaBO selects POMISS via the causal acquisition function, the top plot shows that its choices are highly variable, which harms optimiser convergence (bottom plot). contrast, CoCa-BO achieves much smaller regret, illustrated in the bottom plot.
The SCM for the second configuration, defined in Appendix 1.1. is consis- tent with the causal graph in Fig. 4. It implies that controlling Aspirin and Statin based on Age and BMI yields lower expected PSA than fixing them to constant values. Fig. 3b depicts the results for this setup. Since CaBO marginalises the contextual variables, it cannot control medications based on Age and BMI, and therefore fails to converge (bottom plot). The top plot shows again the high variability in POMIS selection under CaBO, As expected, CoCa-BO attains much smaller regret.
Second Configuration:

---

Published as a conference paper at ICLR 2026
Aspirin
Cancer
Statin
BMI
Figure Causal graph of PSA level. White nodes:
Figure 5: Robustness the noise: Normalised
intervenable variables; gray nodes: ob- regret under varying noise levels. servable variables; shaded node: target variable.
CoBO vs CoCa-BO We consider two SCMs based on the graph of Fig. 1.
First Configuration: Appendix describes an SCM consistent with the causal graph in Fig. 1, where intervening on both Xı and X2 does not hinder the agent's ability to reach the optimal outcome. Fig. 3c (bottom plot) shows both methods converge to the optimum, as evidenced by o
the decreasing normalised cumulative regret, with CoBO converging faster than CoCa-BO. In this configuration, CoCa-BO's advantage over CoBO emerges environments with many variables, as shown in Section A.3.
The second configuration examined in this study is the SCM of Fig. 1. We have shown analytically that the CoBO method is unable to attain the optimal solution. Our method, CoCa-BO, has been demonstrated to effectively achieve the desired optimum, resulting in sub-linear regret. The top sub-figure of Fig. 3d illustrates the cumulative frequency of selecting the corresponding POMPS. We observe that CoCa-BO converges to the policy scope (X1; C)) yielding the optimal value. The lower sub-figure of Fig. 3d illustrates that the normalised cumulative regret remains constant for CoBO, indicating its linear cumulative regret. On the other hand, CoCa-BO attains sub-linear cumulative regret, as evidenced by the decreasing trend of the blue curve.
Second Configuration:
Robustness Noise The target variable Y is pivotal, as observed values guide both policy scope and selection. Consequently, higher noise in Y slows the convergence of optimisation algorithms (Lattimore & Szepesvári, 2020; Krause Ong, 2011; I; Srinivas et al., 2010). To assess the robustness of CoCa-BO to noise in Y, vary the standard deviation of Ey in the example of Appendix A.2, adjusting (cy) from 0.01 to 6.25. As shown in Fig. 5, CoCa-BO converges for a up to 1.25, while convergence becomes unclear under extreme noise, e.g., ((y) 6.25.
7 CONCLUSION
We provided evidence that existing Bayesian optimisation methods that incorporate causal knowledge are not capable of integrating contextual information without incurring substantial computational and statistical costs. To overcome these challenges, introduced CoCa-BO, novel method that efficiently optimises over mixed policy scopes. We derived worst-case and instance-dependent regret bounds, which also address theoretical gaps previous methods. We conducted experiments across various environments and demonstrated that CoCa-BO consistently reached the optimum even where existing methods could not. Moreover, our experiments showed that CoCa-BO is robust to noise and reduces sample complexity by identifying smaller optimisation domains in environments with large number of variables. support reproducibility, we provide our Pyro- brsed implementation (Bingham et al., 2018; Phan et al., 2019), offering a unified framework for future research.
REFERENCES
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C.,, Corrado, G. S., Davis, A., Dean,
J., Devin, M., Ghemawat, S., Goodfellow, L., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowiez, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D.,, Monga, R., Moore. S., Murray, D., Olah, C. Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V.,
Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng,
X. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015.
10

---

Published as a conference paper at ICLR 2026
Aglietti, V., Damoulas, T., Álvarez, M., and González, J. Multi-task causal learning with Gaussian processes. Warwick Research Archive Portal (University of Warwick), 33:6293-6300 9 2020a.
Aglietti, V., Lu, X., Paleyes, A., and González, J. Causal bayesian optimization. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020b.
Azuma, K. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, (3), 1967.
Balandat, M., Karrer, B., Jiang. D. R., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. BoTorch: A Framework for Efficient Corte Bayesian Optimization. In Advances Neural Information Processing Systems 33, 2020.
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, Dennison, C., Farhi, D., Fischer, Q Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 1912.06611. 2019.
Bingham, E., Chen, J. P., Jankowiak, M., Obermeyer, F,, Pradhan, N., Karaletsos, T., Singh, R., Szerlip, P., Horsfall, P., and Goodman, N. D. Pyro: Deep Universal Probabilistic Programming. Journal of Machine Learning Research, 2018.
Bonilla, E. V., Chai, K., and Williams, C. Multi-tass gaussian process prediction. Advances in neural information processing systems, 20, 2007.
Cakmak, S., Astudillo Marban, R., Frazier, P., and Zhou, E. Bayesian optimization of risk measures. Advances in Neural Information Processing Systems, 33:201 30-20141, 2020.
Cakmak, U. and Özekici, S. Portfolio optimization in stochastic markets. Mathematical Methods of Operations Research, 63(1):151-166, 2006.
Jowen-Rivers, A., Lyu, W., Tutunov, R., Wang. Z., Grosnit, A., Griffiths, R.-R., Maravel, A., Hao, J., Wang, J., Peters, J., and Bou Ammar, H. Hebo: Pushing the limits of sample-efficient hyperparameter optimisation. Journal of Artificial Intelligence Research, 2022.
Duong, B., Gupta. S., and Nguyen, T. Causal discovery via bayesian optimization. In International Conference on Representation Learning, 2025.
Elsken, T., Metzen, H., and Hutter, F. Neural architecture search: survey. Journal of Machine Learning Research, 20(55): 1-21, 2019.
Ferro, A., Pina, F., Severo, M., Dias, P., Botelho, F., and Lunet, N. Use of statins and serum levels of Prostate Specific Antigen. Acta Urlóóiica Portuguesa, 2015.
Gardner, J., Pleiss, G., Weinberger, K. Q., Bindel, D., and Wilson, A. G. Gpytorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration. Advances in neural information processing systems, 31, 2018.
Gamett, R. Bayesian optimization. Cambridge University Press, 2023.
Ghosal, S. and Roy, A. Posterior consistency of Gaussian process prior for nonparametric binary regression. The Annals of Statistics, (5), 2006.
Gultchin, L., Aglietti, V., Bellot, A., and Chiappa, S. Functional causal bayesian optimization. In Uncertainty in Artificial Intelligence, pp. 756-765. PMLR, 2023.
Hoeffding, W. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, (301), 1963.
Hoyer, P. O., Janzing, D., Mooij, J. M., Peters, J., and Schölkopf, B. Noulinear causal discovery with additive noise models. In Advances Neural Information Processing Systems 21, 2008
Hyttinen, A., Eberhardt, F., and Hoyer, P. O. Experiment selection for causal discovery. Journal of Machine Learning Research, (1), 2013.
11

---

Published as a conference paper at ICLR 2026
Koller, D. and Friedman, N. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Krause, A. and Ong, C. S. Contextual gaussian process bandit optimization. In Advances in Neural Information Processing Systems 24, 2011.
Lattimore, F., Lattimore, T., and Reid, M. D. Causal bandits: learning good interventions via causal
inference. ANU Open Research (Australian National University), 29:1 29:1189 1898-19977711 12 2016.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.
Lee, S. and Bareinboim, Structural causal bandits: Where to intervene? In Advances in Neural Information Processing Systems 31, 2018.
Lee, S. and Bareinboim, E. Structural causal bandits with non-manipulable variables. In The Thirty-Thin AAAI Conference on Artificial Intelligence, 2019.
Lee, S. and Bareinboim, E. Characterizing optimal mixed policies: Where intervene and what to observe. In Advances in Neural Information Processing Systems 33, 2020.
Lifshits, M. A. Absolute continuity of functionals of "supremum" type for gaussian processes. Journal of Soviet Mathematics, (5), 1984.
Matthews, A. G. d. G., van der Wilk, M., Nickson, T., Fujii, K., Boukouvalas, A., León- Villagr,,, P., Ghahramani, Z., and Hensman, J. GPflow: A Gaussian process library using TensorFlow. Journal of Machine Learning Research, 18(40):1-6, apr 2017.
Pearl, Causality, Cambridge University Press, 2009.
Phan, D., Pradhan, N., and Jankowiak, M. Composable effects for flexible and accelerated probabilis- tic programming in numpyro. ArXiv preprint, 2019.
Spirtes, P., Glymour, C. N., and Scheines, R. Causation, Prediction, and Search. MIT press, 2nd edition, 2000.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. W. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, 2010.
Sussex, S., Makarova, A., and Krause, A. Model-based causal bayesian optimization. In International Conference on Learning Representations, 2023.
Thompson, C. Causal graph analysis with the causalgraph procedure. In Proceedings of SAS Global Forum, 2019.
Turner, R., Eriksson, D., McCourt, M., Kiili, J., Laaksonen, E., Xu, Z., and Guyon, I. Bayesiaa optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020. In Proceedings of the NeurIPS 2020 Competition and Demonstration Track, 2021.
Vakili, S., Khezeli, K., and Picheny, V. On information gain and regret bounds gaussian process bandits. In The 24th International Conference Artificial Intelligence and Statisties, 2021.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H.,
Powell, R., Ewalds, T., Georgiev, P., al. Grandmaster level in stareraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-335 -3444000334444 2019.
Wang, X., Zhao, M., Nolte, D., and Ratliff, T. L. Prostate specific antigen detection in patient sera by fluorescence-free BioCD protein array. Biosensors and Bioelectronics, (5), 2011.
Zhang, J. and Bareinboim, E. Transfer Learning in Multi-Armed Bandit: A Causal Approach. Adaptive Agents and Multi-Agents Systems, 2017.
Zhang, J. and Bareinboim, F. Online reinforcement learning for mixed policy scopes. In Advances in Neural Information Processing Systems 35, 2022.
Zhang, and Hua, C. Spectral mixture kernels for bayesian optimization, 2025.
12

---

Published as a conference paper at ICLR 2026
Appendix
Table of Contents
A
Additional details on the experimental results
14
A.1
CaBO vs CoCa-BO
A.2
CoBO vs CoCa-BO
A.3
Environment with large number of variables
16
A.4
Robustness Noise
18
A.5
Robustness to GP backend and Importance of Context
18
B Main theoretical results
18
B.1 Description of the setting and the algorithm
18
B.2 Proof of the main result
20
B.3 Proof of Theorem
28
C Additional theoretical results
29
C.1 Bounds on the information gains
29
C.2 On uniqueness of the optimal arm
30
13

---

Published as a conference paper at ICLR 2026
Acronym
Full text
BO
Bayesian Optimisation
CaBO
Causal Bayesian Optimisation
CoBO
Contextual Bayesian Optimisation
CoCa-BO
Contextual Causal Bayesian Optimisation
POMIS
Possibly Optimal Minimal Intervention Set
SCM
Structural Causal Model
GP
Gaussian Process
UCB
Upper Confidence Bound
DAG
Directed Acyclic Graph
MPS
Mixed Policy Scope
POMPS
Dessibly-Ottima Mixed Policy Scope
MAB
Multi-Armed Bandit
Table 1: This table presents the main acronyms used throughout the paper.
A ADDITIONAL DETAILS ON THE EXPERIMENTAL RESULTS
In this section, present the details necessary to understand and reproduce the experiments reported
in Section
A.1
CABO Vs COCA-Bo BO
We describe and analyse SCMs used for comparing CaBO with CoCa-BO in this section.
A.1.1 FIRST CONFIGURATION
The SCM that is used for the comparison of CaBO vs CoCa-BO in a scenario where CaBO can achieve the optimum is given below: Age ~ U(55, 75), e ~ N 0.4) and?
BMI (27.00 0.01 x Age 007)
Aspirin = e(-8.0 + 0.10 Age + 0.03 x BMI)
Statin e(-13.0 + 0.10 x Age + 0.20 BMI)
0.05 x Age + 0.01 BMI 0.04 x Statin + 0.02 x Aspirin Cancer = e(2.2 0.05
PSA c 6.8 0.04 Age - 0.15 x BMI 0.60 Statin 0.55 Aspirin + Cancer
We first note that for any values Age and BMI
E[PSA| do(asp, sta), age, age, bmi]
Ele + 6.8 + 0.04 Age 0. 1.BIBMI 0.60 Sta + 0.55 Asp + Can do sta), age, bmi]
6.8 + 0.04age 0.15bmi 0.6sta + 0.55asp + [E[ Can do(asp, sta), age, bmi]
6.8 + 0.04age - 0.15bmi 0.6sta + 0.55asp
+ e(2.2 - 0.05age + 0.01bmi 0.04sta 0.02asp)
is easy to see that
argmin E(PSA
do(aspirin, statin), age, bmi]
asp,sta
argmin 0.6 + 0.55 asp e(2.2 0.05age + 0.01bmi 0.04sta + 0.02asp). atp,sta
In summary, to minimise PSA, Statin should be controlled at its highest value and Aspirin at its lowest value. Since the domains of both variables are [0, 1], the solution of the optimisation problem is Aspirin 0 and Statin = 1, which is independent of Age and BMI. This implies that the optimal control values for Aspirin and Statin are the same for all values of Age and BMI. This is why the optimum is achievable by CaBO.
Here, denotes the sigmoid function.
14

---

Published as a conference paper at ICLR 2026
Notation
Mcaning
U.V
Vectors/sets composed of random variables
U, V,
Values taken by vectors/sets of random variables random variables
U,V,Y
Rv,
The domains of the random variables U, U,V;X; i.e., the sets in which U, V, take their values.
Xv. Xx
The domains of the random vectors U, V.X.
PV
A probability distribution of the random vector V; 0 can be replaced by different symbols, for instance, by 0 or by æ.
Epyl2]
The expectation of the random variable g () assuming that V is drawn from PV-
F
Set of functions with elements usually denoted by ʃ- A structural causal model given by the quadruple (V, U,F,F.
SCM
g
A directed acyclic graph.
PAv
When V is node in a DAG, PAy is the set of its parent nodes.
Cx
When X is an intervenable variable, Cx is its scope, i.., a set of observable variables that can be used for planning intervention X.
S
A mixed policy scope, i.e., a collection of pairs (X, Cx).
X(8)
The of intervenable variables of S.
C(S)
The set of contextual variables of S.
Gs
The graph obtained from G by removing edges into X and adding new ones from each element of Cx to X for every (X, Cx) E S.
xx Cx
mapping from &cx to Xx-
S[G]
All mixed policy scopes S compatible with the DAG G. A mixed policy, i.e., collection of mappings x Cx The set of all mixed policies и based on the mixed policy scope S. The of all mixed policies based on a mixed policy scope S e S[g). The SCM obtained from 21 by applying the policy
m
IIs
Ilg
((T)
The expected reward under the mixed policy и. For well specified Y E V, it is defined as μu(T) = E.g [Y].
The highest expected reward among all mixed policies i based on the scope S.
[
For a random variable Z gVV) and mixed policy æ, this a short- hand for Epg [Z].
(*
The subset of S(g) consisting of only those S that are possibly optimal, Historical data up to time e N, consisting of quadruplets (S,, C,2 X;, Us) for i = ,t...,t. t.
D
14
(0) a000
Posterior mean and standard deviation of the 7th Gaussian process after time
Pr, Ri, Ri
Instantaneous regret at time cumulative regret at time I, and time- normalised cumulative regret at time t.
Table 2: This table summarises the main notations used throughout the paper.
A. SECOND CONFIGURATION
The SCM that used for this setup is such that an agent should control Aspirin and Statin based on Age and BMI to achieve the minimum expected value for PSA. It is defined by Age ~ (55, 75),
15

---

Published as a conference paper at ICLR 2026
(O, 0.01) and
BMI ~ (27.0 - 0.01 x 001)
Aspirin e(-8.0 + 0.10 Age 0.03 BMI)
Statin e(-1030 + x Age + 0.20 x BMI)
Cancer Statin AgeBMI + 0.5 x Aspirin
PSA Cancer + 0.5 Asp² AgeBMI - x AgeBMI x (Asp Sta).
where we used the notation
AgeBMI = Age
BMI
21
4
Plugging in the structural equation of Cancer into PSA, we get
PSA E Asp* + Sta 2AgeBMI
AspAgeBMI - Sta AgeBMI
= (Asp AgeBMI)² + (Sta AgeBMI) +
An agent controlling both Aspirin and Statin expected value PSA, namely 0. CaBO fails does not consider Age and BMI while controlling Aspirin and Statin.
(Age-55 55
BMI-27
level achieves the minimal
21
A.2 CoBO vs COCA-BO
We introduce an SCM such that CoBO which by default controls both X, and X2 based on is still capable of getting to the optimum value. The SCM is based on the causal graph depicted in Fig. and the following equations
U1, U2 ~ Uniform(-1,1)
EC; EXi (0(00.1), ey ~ (00.0.01))
= U1 +EC
X1 U1 +
X2 = IC' (C-x11 0.2U2
Y = cos(C' X2) 0.10p + ey.
This SCM has two POMPSs, namely (X1;)) and (X2
We first note that intervening on both X, and X₂ is redundant in the sense that intervening X₂ destroys the directed causal path from X; to Y and renders the intervention on X, irrelevant to Y. Let the intervention X₂ be given by arbitrary function Kc + Xx,. Then the expectation of Y under such control can be expressed as:
[x] E, [cos(C X2) + 0.10 cn] = E, [cos(C X2)1 = [c - -((n())(()))))
It is trivial see that maximise the above expectation, should X₂ the value of C, i.e., the identity. This yields max, Ee (Cos(C - T (C))) 1.
Therefore intervening X₂ based C yields the optimal value, which is the highest value that the expectation of may achieve under any policy E3 [V] = Ey [cos(C X2) + 0. + 0.1c,) = E, Gcosss X2)] < 1. We conclude that CoBO achieve the optimal value for this SCM.
A.3 ENVIRONMENT WITH A LARGE NUMBER VARIABLES
This example highlights key advantage of CoCa-BO: it can yield significant gains in sample efficiency over standard CoBO, even when both methods converge to the same optimum. The advantage stems from using the causal graph to identify and remove superfluous variables from the policy scope. The resulting reduction in dimensionality often accelerates learning. We demonstrate this in challenging, nigh-dimensional setting with 57 contextual and 29 intervenable variables, where the improvement from simplified scope outweighs the cost of searching over the policy space. The underlying Structural Causal Model is defined follows.
16

---

Published as a conference paper at ICLR 2026
MPS solection frequency
0.8
x2
< x1
Co
0.0
0.4
C2
0.2
Normaiised cunnlative regret
10/
COCa-BO
CoBO
C
Co
50
CA
10-3
X
27
Number steps
210
0001
(a)
(b) Performance of CoBO and CoCa-BO
Figure 6: (a) A causal graph with a large number variables. The rectangular nodes represent plates of variables. The number below the rectangles represents the number of variables within each plate. Variables C₁ and X,, over-specify the environment and are redundant for optimising the expected value of Y. (b) Both methods converge, but CoCa-BO has lower cumulative cost due smaller policy scopes (((Xi: C1, Cs), (X2; C.)).
U1. ~ Uniform(-1,
C. N(0.0.2)
X1 ~ 0.1),
C N(Ca 01,
C2 O.1,,,
Cg ~ N(C,,C,,
C₁ ~ C,NN(Cs, 0.1)
50
1
G. -.(00.22)
Vi (1,....,50)
Ooo
C
50
1=1
27
1
X1, Uniform [- 1,,,,, 0.16
Vj (1....,,277
X27
Σ
X1,
27
j=1
C +.C1+ 0.1)
C. ~ CC 0.1)
X2 ~ V(0..(CC) +C) + X1 + 0.3 0.3 0.1)
Y ~ (Ccos(( - x2) + 0.112, 0.01)
We also provide the causal graph corresponding to the above SCM in 6a, where we use rectan- gular nodes to represent the plate notation (Koller & Friedman, 2009). This example has purely contextual variables C₁, and X,, that only influence the rest of the system only through Cs. It not necessary to control observe these variables to achieve highest expectation of the target variable Y. This is reflected in the POMPSs {(X1; C1 C&), (X2; Ci)) corresponding the causal graph. Both POMPSs contain noticeably fewer variables than the policy scope considered by CoBO (X1, X2, X Co.6. Crasa) where Xm.. (X, < < n).
One may note that this SCM is similar to the SCM from A.2. Indeed, the structural equations for Y are the same. The same derivations apply to this SCM, proving that CoBO can achieve the optimum, which is reflected in Fig. 6b, which shows that both methods converge to the optimum, yielding decreasing trend in the normalised cumulative regret. Moreover, CoCa-BO converges faster as utilises the causal graph and derives policies with a smaller scope. As we see, this significantly improves the convergence speed over CoBO even if it achieves the optimum.
17

---

Published as a conference paper at ICLR 2026
Normalisol cunnlative regret
O-
HEBO
Normalised cumnlative regret
with context w/o context
BoTorch GPflow
10%
109
10-1
10-1
200
400
600
200
400
600
Number of steps
Number of steps
(a) BO backend comparison
(b) Importance of context
Figure Left: CoCa-BO performance under different BO implementations. Right: CoCa-BO
performance with contextual information preserved versus discarded.
A.4 ROBUSTNESS TO NOISE
We note that the total variance of under the optimal policy is actually higher than the variance of cy due to an unobserved confounder U2, which has a variance of 1 1/3. Thus, var=(Y) 10-2 + var(ey) under the optimal policy æ. We emphasise that var, (Y') under any other policy is greater than or equal to var, (Y).
3
A.5 ROBUSTNESS TO GP BACKEND AND IMPORTANCE OF CONTEXT
This subsection examines the effect of the underlying BO optimisation on our method. We ablate the backend across HEBO (Cowen-Rivee et al. (2022)), BoTorch (Balandat et al. (2020)), and GPllow (Matthews et al. (2017)). HEBO and BoTorch utilise GPyTorch (Gardner et al. (2018)) for GP inference, whereas GPflow provides its own CensorFlow-basee implementation (Abadi et al. (2015)).
We conduct the study on the SCM described Appendix A.2 and summarise the results in Figure 7a. We observe that our method converges regardless of the underlying BO routine, though HEBO appears slightly better.
In the same environment, ablate context by removing the contextual variables from all POMPS while preserving the interventional variables and the hierarchical design CoCa-BO. The results in Figure 7b show that, without contextual information, the algorithm quickly converges a suboptimal solution and cannot escape it, due to the missing context.
B MAIN THEORETICAL RESULTS
B.1 DESCRIPTION OF THE SETTING AND THE ALGORITHM
Our algorithm, described in Algorithm does not distinguish between two POMPSs that share the same sets of intervenable and contextual variables. Hence, we say that two MPSs S and S' are equivalent if X(S) X(S') and C(S) C(S'). Let m denote the number of distinct equivalence classes of POMPSs. We index these equivalence classes by i {L...., m). For the i-th equivalence class, we denote its intervenable variables by X(i) and contextual variables by C(i). We denote by P: the distribution of the random vector C(i).
We assume that the reward obtained under a POMPS S belonging to the i-th class given by
Y f. (x(i., C(i) + Ex,
where /; Xx(1) x Σcτa) - and E; is independent Gaussian noise, 6; ~ ~N o²). Furthermore, for every equivalence class, we assume f. GP(O, k;) independently across i, where k; are known covariance functions such that n; supx,exx. e &e (x((x, c), (x', c'))
18

---

Published as a conference paper at ICLR 2026
This means that we assume that the following arrays of independent random objects generated by the nature
1:
Jis (Ci,1, C1,2, ...,,..., C1,
(P(O,k)) P GP(O, k2) @ P
i = 2: fzi (C2.1, 22 C2. .,
= mi
Smi (Cm,1, Cm,2: Cm....... Cm.f....)
GP((P kim) PEN
,t,...,,,,...... St....)
~ ~N(00,2)00.
Here, for probability distribution Q, denoted by QaN the probability distribution of the sequence (Zz) of independent random variables drawn from the same distribution Q. We denote the contextual best reward for arm i by
(c)
sup c((,c), xcXx(1)
and the corresponding contextual best action by
x arg max ft(x,c), xxXx())
which we refer to as the optimal policy of arm i.
Throughout this section, we will use the notation PPZ f) and [E[Z f] to denote, respectively, the conditional probability and the conditional expectation of a random vector Z given f = (Ji,.--, fm)) The conditioning is understood with respect to the Gaussian process f = (f1,..., Sm). which means that the integration carried out over all realisations of the noise variables Et.
An agent, without prior knowledge of the functions ft, interacts with this bandit in a sequential manner. At each time step t:
1. the agent chooses is E [m]]
2. the agent observes C₁ Ps..
3. the agent selects x; E 3x(i:))
4. the agent observes y/ (x,, + Ec, where Es sid N(0,03).
We use x,,s and Ci,s to refer to the interventional and contextual values of the 2th equivalence class of POMPSs when has been selected for the 5th time, Additionally, we refer to an equivalence class as an arm, reflecting the similarity of our problem to the m-armed bandit setting. Each arm i has f; as its expected payout function, where Xx()) assumed be convex and compact.
In our causal optimisation framework, contexts for each arm are sampled i.i.d. from fixed distribution. key aspect of our setting that the agent actively selects which contextual variables to observe, decision determined by the chosen POMPS. The agent's 's objective is to maximize (in expectation) the cumulative reward D'n Vt over unknown time horizon T.
Our proposed algorithm relies on the upper confidence bound (UCB) as the selection criterion for the evaluation point. Recall that the posterior mean and variance of the GP are denoted by (x,,(x, c) and 0i, (x, c), respectively, after the 7th arm has been played times. The UCB at the point (x, c) after plays is defined as
UCB,,e c) = 14,0-((x,)) c) + VBB((+/((,.ee (((()a,,-ixx,))) c),
(5)
for some tuning parameters (f). We summarise our method in Algorithm 2, where Bi, and n, are free parameters be specified later.
fe(x, c) (dcc and 1 = argmaxig(m) Pi. Clearly, μ4 depends on ft. whereas Rr and I' depend on f. but for the sake of simplicity of writing, this dependence will not be highlighted in the notation. We also write μ² max4e[m] /4. The regret then is defined as:
Regret Definition Let μ4; = EIS
R1 Σ (1r 1=1
Elf. (X. C.) f.
(6)
19

---

Published as a conference paper at ICLR 2026
Algorithm 2 Intervention selection algorithm UCB-BQ
Input: m := number of equivalence classes of MPSs from S*
Parameters: (B.(n)))((l)eee) (p:(n) (p:(n))ee)m))enn) for / to do
i < m then
Select equivalence class: is := t.
Observe context c₁ = Ci,,--
Select action: X, X1,1 arg maxxeXx(a))
(x, (See Eq. (5) for UCB.)
Set: (1) == UCB.,,1 (x,, 1; n4, 1.
Observe: 1/1
Update the posterior for the & Gaussian process based on X;,, Cie, and yr-
else
Select an equivalence class: & = arg maxie[m) (Us( + P.(n.)
Update: ni; 14i + 1.
Observe context: C₁ = Ci
Select an action: X, Xis,ni, arg maxxexx; UCB (x, Ct)
Observe: yt
Update the posterior for the Gaussian process based on X Ct2 and ye.
Set: Us (nx,))
(Me (1)+-1) Ü2 (ns, 1) + - UC (Xe, Ct)
Ric
end if end for
The regret Ry can be decomposed into two components:
Rr Σ
p.. - EIJ,, (
Selection Regret
Context-avernged Action Selection Regret
The context-averaged action selection regret measures how much the mean reward fú, of the action X₁ chosen by the agent deviates from the mean reward of the best possible action x; (c.,). averaged over all values of the context. We note that is localised to the chosen arm. The arm selection regret compares the rewards of each arm if the agent plays according to the optimal policy that arm.
B.2 PROOF OF THE MAIN RESULT
Our next lemmas motivate the choice of the index for arms in Algorithm 2. Recall that X, is an element of xx()) that maximises x -> UCB,,e(x, C.,)).
Lemma 1. Let 8 (0.1) 1) and (Tn)ENN- be nondecreasing sequence of positive numbers such that EnEr. A. 1. Let Ni, be an E-net of Xx(s) in norrr, with 1/ 1/( If for all E N",
B(()) 2 2
log(2/ (m5)) + 4d, log,, (mr:deun))
there is an event Ac(ō) of probability least such that on A;()), the following properties hold
f((,,,, C..)) Z UCB,, (X C..e) 2/ Ci,e); for all E NN, (og(2dd for all x E Ex(O): CEN
(7)
(C,e) & UXB,,,(X,,4 Ci,e) + mmee
(8)
Proof. We define the events
Ωg () f((x', c)1 S py lov/lo/222///// ||x -XII,, for all x, E Tx(0) e Ica),
2g,1 = (si(x, C..) s UCB.,(x, C.e); for all x E Nie),
24,2 (C(()))) (X,, - a (X,,, C(d)
20

---

Published as a conference paper at ICLR 2026
Assumption implies that P(Q)) 2 11-187 8/22. Furthermore, recall that for any (xx xx(i) x Xo()) the conditional distribution of fi(x,,) c) given Di,--1 is Gaussian with mean 1 (x, c) and variance (x,,
c). This implies that
P (()((x,)) & (x, 22lg((166)) ore o e) Di,t-1) /1
6
for every de E (0, 1). Note that the above inequality holds not only for any deterministic (x, c), but also for every random pair (x, c) provided that is independent of fi given D; Therefore, applying this inequality to all pairs {(x, Cz.e) x E Na,e) and taking the union bound, we get
P( Cit) S (x, Ci,)) + (B:(0); 01,--1 C,,)); VX Ni,e Di.c-1) 2 We
2
(((e) 2 ( / Taking into account the definition of UCB;, arrive at Since this inequality holds for any set of values taken by the
P( (i,,-1) 2 1 be/2
data 1 1, we get
1( 2 1 - (6/4T)), provided that B.(e) > loog(2T) (1,,
Since X. is the maximiser in Xx(() of x + & Ci,e). it is clearly independent of fa conditionally D Therefore, the argument used above can be repeated infer that the following inequalities hold with probability 2 6/(4m)):
f C2 2 (X C..)) 22log(2T, ( (X Ci,e)
2 UCB((X,,. C.,e) - 2/BB())) (x,))) Ciee),
provided that 3:(E) 2 2 10g We conclude that as soon as 3:(E) 2 2 (N,e//0) we have (():(8)) 5 for
A. Qo n (N (Se, nlez)
E=1
The fact that (7) holds on A(8) is obvious. To show that (8) holds well, suffices notice that for all x E [x() and for all E N
fa(x. C.,)) I max fi(x, C..e) yd,r, pd..://ll (m xEN.,
< (CB,, Ci + @V ht log(2d, (mm))) (m=z)-1
< SUCB,, C.,)) + l/lo (m
The first inequality above follows from the fact that Ro realised, the second inequality follows from S4,1 and the third inequality is due to the fact that X, is the maximiser of x eCB,,(x, C.e). Since we assumed that xx()) C [0, rd]d, we have [NG.e S (rad//5)4 v = (mr, m2) d V 1. This implies that it suffices to choose (E) satisfying
(((() 2 log(2/ (mo)) + 4d, log, (mrr,dTT)).
This completes the proof of the lemma.
Lemma 2. Let (TT))EN be nondecreasing sequence of positive numbers such that EnEN. n.,"" Define
Ú.(n) 1 E UCB,,(Xi,1 C.r), p.(m) (CC.))
n
(7) and (8) are satisfied for some E (0, 1), then for every n E N
p=(n) /P/log(2, < (.(n) S [n(n)) 2 log((1 + -xx))
2618((1))i())
21

---

Published as a conference paper at ICLR 2026
Proof. From (8), we infer that
(C,,) & (XL. C..e) + 8 (log(2d,55/))
miz
Averaging over & = l,..., and using the inequality Ei 1/TE S 1, we obtain
(.(n)= - (.(n) + sdher Vlog(2d;)/0)
me
To get lower bound on [n(n), we average over l = 1..... inequalities (7), then apply the Cauchy-Schware inequality, obtain
(n) 2 U.(n)
Bi(l) 01,8-1(Xi1 Ci,))
t=1
2 2.(n) 2 (n)
01.-1((i,e Ciee
2 (n) - (X,,,, Cie)
1/2
2 U.(n)
(9)
vn
The definition of o c) as the posterior variance of fi(x, c) given Di.-- and formula (1) imply that of,,(x,,) S Ki for every c). Therefore, the increasingness of the function x >> x/ log(1 + yields
- o (x, Ci.) log (1 + o 20 1 (x, Ci,))
2k,
S
log(1 - o -kks)
This can be rewritten
Nú log (1 0-2 2,6-1 (Xier Cit))
(X,,, C.,0
N*.
log(1 + -22x)
Therefore, we have
Ki Σ o 1 (Xi,,, Ci,) log(1 (1 + 2k²
log (1 - Ci,))
E=1
2x, (n)
(10)
log(1 + 2x:)
The last inequality above follows from the definition of Yn and (Srinivas et al., 2010, Lemma 5.3). Combining (9) and (10), we arrive at
(
(()) + 2/ nlog(1 -2kz)
This completes the proof of the lemma.
Lemma Let E (0,1) and let Re(i) be convex and compact, included in [0, ri for some d' E N and some r 2 Let us denote
X( derlep log(2(d/ 2TT)
(11)
There exists an event A,(0) of probability at least 8 such that on Ai(5), it holds
X((5)
(C,,) us
Vn E N
/2n
22

---

Published as a conference paper at ICLR 2026
Proof. If we set Af? maxe (c) mine f (c). the Höffding inequality implies that
1og(2/61)
P (C,)) 14 - A 1=1
5 21 211-1..
51, Vi E [m].
2n
Choosing 81 m2(T) and using the Bonferroni inequality, get
p( Σ (C.,) Mi S SAT
log (T44mT//) for all E N²' 5 2 1 11--/2. (12)
p
2n
On the other hand, since &C() is convex and compact, included in [0, rr114 Assumption 2 implies that there exist kernel dependent positive constants sp, v such that, with probability at least - 5/22,
(f((xc) - cx(x /v ||c c'Il:: for all Xx(): c, e' E Xx())
Hence, with probability at least 6/2, we have
Af; S dr. /
Combining with (12), this implies that on an event of probability at least 1 - 6, denoted by A((5), have, for any N
log (og(4Tn//)
(CC.)) pi
s Voci:v/oog2//////////
2n
log(2(d'
2mn)//)
s <dripp
22n
/2n
This completes the proof of the lemma.
Our next step to upper bound the number times a suboptimal arm i $ 1" played.
Lemma 4. Let
(0,1/2) and (In) be a positive nondecreasing sequence satisfying 1. Let C, 8k,/ /os(1og(111))) + =n)). Assume that the parameters (:(n) and pc(n) are selected so that, for every i E [m] and every n E N
Enery 1/T,- =
(.(n) 2 2log44/)) + 4d, log(mr,d(Ta),
pa(n) loVlog(4md.)) /5) d'r log (4m(d'v 2TT)//)..
n A (m)) be the intersection of the events defined in Lemma 2m) (6m2mmm Let A(d) = - (6
and Lemma 3. Then ((A 2 1- 8 and on A(8), the number of times n, nT(T) a suboptimal arm with gap A; > 0 has been played over the horizon T satisfies
Vnr(T) S (() + 2pc(ns)
V1,
VT 2 1, 1..
A
Proof. The fact that ((A(8)) 2 1 1-6 follows from Lemma Lemma 3 and the union bound, Let us use the notations
b2(n) = (n)x(())))())))
and X as defined by (11). For all pairs (T, such that n (T) = 1, the desired inequality is obviously satisfied. Consider now the pairs (T, i) such that (T)) > 2. Let be the last time the arm i has been played among the first T' rounds. To ease notation, let us set nı, = n2(t.) = n (T") Let j = j(f) be p4. Since round t, arm has been
optimal arm, that is, integer from [m] maximising preferred to the optimal arm j, we have
Ul(m:) + (1(
Vnu 2 (n,), + py(ng)
(13)
23

---

Published as a conference paper at ICLR 2026
Under choice of (x(n)) and Ty, Lemma 1 and Lemma 2 applied with 8/(2m) instead of 6, imply that on A(6), for all T 2 and for all & I", holds that
by(n,) vTu
U.(n:) S [n,))))
(14)
Új(ng) 2 m3((5)) Pis/log 1ogg
(15)
mnj
Combining (13), (14) and (15), we check that with probability at least -6/2. for all 2 and for all i I", it holds that
(m)))) + be(n)) pi(na) VT4
(n))n)) Ps(mg)
gyvlog (4mg4
(16)
Vnj
mny
Since work under A()) that is included in U (5(662m) have
(m6m2m) for all i [m]] (n) - 14 S
V2n
In conjunction with (16), this implies that for all T 1 and for all gr.jer, be(m)) + pi(n.)
11(6/2m)
Pz(ng)
/ Poy/log(4md,dby (mdd
(5/2mm)
#4 +
My
VTR
V2ng
Vnj
n
22n
In the rest of this proof, we work under this event.
When (n(n) is chosen so that for all j E [m]]
Pz(1)
L2
log( 1/5 /8)
(5(5/2m)
m
v2
we infer that
be(ne) + pi(n;) + 11(6/2m)
2 Dn
for all & l*
Vni
This implies that
(.().) + (1():) + M((02m))
b((n:) + (n.)
Th
A,
This completes the proof of the lemma.
From now we use the notation
C max Ci, K max Ki, d max di, d' d'=max di,
max
B(T) max max B((n), P(T) max max (n). ns
R
and
>(T) max (T), 7(T) max
a(m))
(n.) E, =
the last maximum being over all the sequences positive integers summing to T. We omit the dependence of (T)) the horizon T' and write for brevity. We denote 31 maxiet 3.T and upper bound Ry under Lemma 4.
Proposition 1. Les 8 E 10,1 and (m,) be positive nondecreasing sequence satisfying
Ener. 1/T, = 1. Let C = 8k/ log(1 + o =xx). Let A (AI,..., Am) be the vector of sub- optimality gaps defined by A; = μ³" μs and I" = {i A = 0}. Let Assumption and Assumption 2 be fulfiiled,, and assume that the parameters Br and p: of the algorithm satisfy
(())) 2 2log(4/6) + 4d, loggmo,,,,,,..m
p((n) 2 povlog(Amd;y) v/0) + dr log (4m( + 2mx)/8)
24

---

Published as a conference paper at ICLR 2026
for every i E [m]] and every Nº. If the UCB-BO Algorithum 2 is applied up to horizon T then, with probability at least 1 26, the regret defined by (6) satisfies the following two inequalities
+ (()) + I1, Rr S 55 (VC
Rr 1 22 (1 ( + (TT
Σ
1 A
+ + 2m +
for all TEN.
Proof. Throughout the proof, assume that the event A(8), of probability at least 1 8, defined Lemma 4, is realised. We will also repeatedly use the following inequalities, that are direct consequences of the
inequality:
Vvm((T) & VIJIT
Σ KEJ
n4 (T)())))))))))) S VmTp(T), for all J C [m].
IEV
We will also use the notation
(n) - (C3(m)(n)+++++) + p(n),
a(n) = (C3(n)((n) + p(n),
for any E N'. Let us define the functions (x c) fc(c) fi(x, With this notation, the regret RT can be written as:
Rr Σ
1r ELJ, (X,, C+) 11),
T
Σ
[1" p4, + Elf X,,, Ct) 11
1
1 C,) + Σ
- - C.)
fi((X,
1=1
t=1
This leads to decomposition of the regret into three components
RT RI, + Rr + R
with
T
T Σ
RT,1 Σ [u- piat
R
fi Ci) 1=1
RT33 Σ
C.)
(X,, C.)}
One can check that for any function h defined on the appropriate set, we have
T
m
h(l,. X,, C.) = m (T)
Σ M(i, X., C.) = Σ
Mi, Xis, C.e)
This yields
RT,1 Σ (T) A
IgI*
m mi(T)
m mc(T)
RT. Σ
(X Cae)= =
C())
(T(T)
RT,
Σ
(X,,, C.,) f f.Dittl (Xi, C.t)
We will upper bound the three components of the regret, RT,1 Ro and Rr. separately.
25

---

Published as a conference paper at ICLR 2026
Bounds the arm selection regret Ry,1: We have
RT.1 <
Σ igr mi(T)>1
Σ
A
m
Σ
( + 2p((n))))
+ Σ
A
ig1
1=1
1/2
1/2
<
T Σ (Bisnniaaa
4T
+ E
ag
The first inequality above is obtained by simple algebra using the fact that A, 2 for every i, the second inequality follows from Lemma 4, while the third inequality is consequence of the Cauchy-Schwe inequality and the fact that the terms (T) sum to T. Since all the functions 3:(-) and p+(+) are nondecreasing, we get
RT, S (CC((TCCC)) 2p(T)) + E S 20(T) + I|
(17)
An alternative bound can be obtained by using Lemma 4 to infer that
RI S
Σ
V (m,,(m))) + 20:(ns) 2
} + +1]
A.
ier-
4o (n:)
+ A1} S (T)
Σ
1
+ +| 1.
(18)
igl A;
Bounds on the action selection regret RT Let us the shorthand notation À PV eeVlog(4mm) (4mdu//8). In view of Lemma on the event A(d) c n A.6/22m), for any arm [m]] and for any n E No, we have
n
n
(ft (C.,)) - f(X,,,, C.,)) $2 > V C.,)) +
< 2 Bi(n)
Oie-- 1i Ci,e) +
m
n
1/2
X
S 2 nBi(m)
Σ
Co.1-1(Xi.. Cite)
m
S (nC x
(19)
m
Here, for the first inequality, we used (7) and (8), for the second inequality, we used the fact that (-(-) a nondecreasing function, the third line follows from the Cauchy-Schwal inequality, whereas the forth line is a consequence of inequality (10). This leads to a first bound on the second component of the regret:
R (.(().))))))) +
VC3(T)
V (n(x(m))+P(TT
+ P(T)
+ pTT) (TT
/mI e(T).
(20)
An alternative bound can be obtained by replacing in (19) n by n4 (T())) and, for i & I", using Lemma 4:
ni
(C((C)) Cao) < 22 k3()) + (T)
A
26

---

Published as a conference paper at ICLR 2026
The first term in the right hand side above comes from the fact that if n, = 1, then instead of using Lemma 4, we can simply use the fact that (1%((1) I 4kg. Summing over all E [m], we get
R S VTIM + 2m kB(1) 5c (T)
Σ 1E1 A,
(21)
Bounds the stochastic-error-term R1,3 Let denote by Fi,m the o-algebra generated by (D f) and define M4,0 0 and
Min Σ ( C. f2 C,, Em1
for n E N
clear that Min is a Fu.n - bound Mi,,. will apply the azuma-Hoeffüee inequality (Azuma, 1967; Hoeffding, 1963). To this end, note that fi (x, c) 2 for every x and c. Furthermore, as seen in the proof of Lemma 3, the set of functions satisfying the inequalities
the sense that B[M,,, Fi,n-1] [ M To upper
(X,e: C.,e) = max (x C..) - f1x C.,)
SaSe S d'r''v//og'' (4mdw) == X
is of probability at least 1 6/2m. This implies that conditionally to f. [Min Min- & X. Therefore, we can apply the Azuma- Hoota--g inequality to infer that
PP (M S X' 22 log(1/))) f) 2 1- 81
with probability at least 1 - 8/2 over the randomness in f. Choosing 61 = 82(2mm,)) and using the union bound, we arrive at
6
PMMi,n S V 2n log(2mm,,/0), for all N", ie [m]] ff 2 1
2
with probability at least 8/2 over the randomness in f. From this, we readily get
PM, S X' 22 log(2mn,. for all n E N", i [ml) 2 Hence, on an event B()) of probability at least 1 8, we have
R
Min,,TT X 2 log 15)
(T(
(22)
i=1
X' 2m'l' log(2m*T/5))
(23)
The alternative upper bound on the term RT is obtained by combining (22) with Lemma 4. This yields
RT, S P(T) [ + 2c(T)) Σ A.
(24)
Combining upper bounds (17), (20) and (23), we get
Rr $ 3v mT 3/ a(T) + A la + X' /2mm lo
I mT a(T) + | /
with probability at least 1 - 26. Similarly, combining bounds (18), (21) and (24), we get
R (T)
Σ
|
cT(T-((TT) 2m 2m (Mm))3(1)+ 56 2
Σ
A
İg7. A
TET
T m + 2c(T) Σ ).
+ (T)
ig1
Regrouping the terms, we arrive at
Rr (12
Σ
Σ 1 A.
|A + 2/TT[=(((T) + (2 kB(1) + p(T)).
This completes the proof of the proposition.
27

---

Published as a conference paper at ICLR 2026
B.3 PROOF OF THEOREM 1
We denote & = 9 V and vi th V 1, and take Tn = n2n2//6 Proposition assumes that
(,(m) 2 2 log(4/6) + 4d, log(mr,
where the right-hand side can be upper bounded by
llog(4/6) + 4d, log(mr,d,mm)) s 4d, log (on(22n
Tv
md,nn
8d, log
8
since d; 2 1.
Now we analyse the assumption on (i(n):
pi(n) 2 & sy /0) + derpplog
(4m(d' + 2mn)/6).
where the right-hand side can be upper bounded by
sf v Vlooo44mm.)///// + derlup log (Am(d''s 2mm)
S v (log( ( w/)) + d'r', log (4m(d + 288)
4m deb
n²n²²
s 2rd((r' V log
3
s 2r' v 1) log (Smd,un ((3rn(((33))) as + b S 2ab, Va, 6 2 1
2 2T
mnd,
s 4rd((r) v log
V3
5
Hence, (n(n) and pz(n)) satisfy the conditions of Proposition 1 if
Be(n) A Pa(n) 2 (F: V 1) log (5. (5.14% VI mnd//8)
By taking A (F, 1), then (n) and (n) satisfy the conditions of Theorem I whenever they satisfy the conditions of Proposition 1.
Under Section the regret is upper bounded
Rr < 5v (VCB(T)(T)++((T) + +|A
|||||
which implies A = 5VC
For the instance dependent upper bound, Section 3 implies that
Ri < (VC3(M)C)++ + +2((3(0)))++++(
Σ
'/1- A
+| + 2m ( P(T)
Σ
igr- A
+ +2(VRV1)m(V/)) 3(1) + p(T)) + +||
Consequently, we take A₁ = 2(11CV VEV1II
In summary, if we take A 8Pb(F: V 1), Ao = 5VCVI, and A3 = 2(11C V VR V 11) then
Section implies Theorem
28

---

Published as a conference paper at ICLR 2026
Kernel
YT
m n 2is1 i= Yn.
Matém-
O 2v log 2+ (T))
2x
O 2047 T 2w44
2v
log 20 (T) m)
20
Squared exponential
O d+1 (T))
O log d+ (T))
124+1
22'12
Cauchy spectral mixture
OT 24 202-2042 log(T))
O 20 +2644
22842443 log(T)) + m)
D-dimensional feature-map B- --polynomial eigendecay 3 8-exponential eigendecay
O(Dlog(1)
O(mDlog(?
o OT 1- 1-11 (T))
O(m O(ml-1/8T1/010 1og
1- (T) m)
Ollo 1118 (T))
O0mlog++1/8(1)
Table 3: Bounds on maximum information gains and their sums on domain of dimension d.
C ADDITIONAL THEORETICAL RESULTS
In this section, provide additional mathematical results that support the discussion conducted after Theorem 1.
C.I BOUNDS ON THE INFORMATION GAINS
This subsection aims to upper bound sums of the following form
max ENT =.=T
Σ ((n).
(25)
where 7/ are the maximum information gains for possibly different Gaussian processes (i.e. with different kernels) but satisfying assumptions (0 mean, covariance function is bounded by etc.). We set (t) = 0, vt < 0 for convenience.
To upper bound (25), use results of Vakili al. (2021) that imply that
for kernels with exponential eigendecay s <Ooog" 1+ d. where Be is a positive constant,
for kernels with polynomial eigendecay - O(T d log do T), where Sp > 1.
2u As an example, for widely used kernels, such Matern-v Yr S O( log न T) and YT S Olog**+1 7)) for the squared exponential kernel.
Hence, we write that (T) < A,T log" + For simplicity, we take A, B,b b and a be the maximums of the corresponding constants, e.g. maX:e[m] di. So we have that
+ B; for some A;, b,
> 0 and 0 < < 1.
7:( < AT log T B, Vi e
(26)
We note that B> (1),, Vi [m] which under the assumption that kernels are bounded by k is at most log(1 +o - xx). So B log(1 + -xx).
Proposition 2. If the array (rx(n)) satisfies (26), then
Σ
m(()) S Am--eT" log" T + mB.
max
R, RENNT E R.=T
*Please Vakili et al. (2021)
'Please see Zhang & Hua (2025)
'Please Srinivas al. (2010)
29

---

Published as a conference paper at ICLR 2026
Proof. Using that log" x is increasing and that + x is concave, upper bound (25) by
max N.EN =
Mi, S A
max n. m1 Σ n==
log
T
my +
mB
m
I Am Amlog
T
max
14
+
ny ER. R2 21
m i=1
=
Am Am-taag u70 log T mB
and the claim of the proposition follows.
We illustrate the implications of Proposition 2 for several widely used kernels in Table 3. Our results also extend to composite kernels, i.e. sums and products of kernels. particular, Theorem 3 of (Krause & Ong. 2011) gives upper bound on the maximum information gain of a sum kernel in terms of the information gains of its components. Similarly, Theorem 2 of (Krause & Ong, 201 I) shows that when the component kernels finite-rank, the information gain of their product can be bounded likewise by those of the components.
C.2 ON THE UNIQUENESS OF THE OPTIMAL ARM
This section motivates the uniqueness the optimal arm in the scenario where (fi), are sampled from Gaussian processes. We recall that the reward of arm i is
μ. E sup fi(x, C) 1 xxXx
(27)
We next show when (s # HLy for distinct and j. Lemma 5. Let + j. If least one of μs and μ. is absolutely continuous, then P(u = Pyy)
Proof. Note that μı is offi) measurable and μúj is off)) measurable. By Assumption 2, the random variables fi and f, are independent, which implies that any random variables defined on their respective algeebrss
also independent, in particular μ4 and Hj independent.
We assume without loss of generality that μi is absolutely continuous. Under the established independence write that
P( p1) (Pus Pay)(a =1))= / Puilus =)) Prs (dx)
- f Pay (dx) = 0,
which concludes the proof.
It follows from Lemma that if all μ4, except possibly one, absolutely continuous, then almost surely no two distinct ones are equal.
The next lemma provides sufficient conditions for μ4 be absolutely continuous.
Lemma 6. Ler | < oc and k, be strictly positive definite, then μ4 is absolutely continuous.
Proof. Our Assumption 2 implies that fi is almost surely continuous and hence, thanks to the compactness assumption made in Assumption 1, attain their maxima Xx(1)- We may rewrite the expectation in (27) as sum, assuming that &c(() cyy):
14 = Σ
P(C ())(
cEλC()
= max
1=1
30

---

Published as a conference paper at ICLR 2026
It is clear that the process
F((X1,,--. xx) Σ (x
centered and Gaussian. For x
xx) and X = (x1,...,xkk)
xx). we have
(28)
where VT= (11,..., and
hy (x), (x),,,,
xxxxx*)=
Note that (X, X') is strictly positive definite since kę is strictly positive definite. So (28) is strictly greater than zero for all and x' from their respective domains.
We have that F; is zero-mean Gaussian process whose index set is compact and separable, it is compact subset of Euclidean space, and its variance is zero nowhere. This implies that sup, F(xt is absolutely continuous (Lifshits, 1984, Corollary, page 2), and so is j4g
Consequently, if we have that for all i, except possibly one, [o(a < co and k; are strictly positive definite, we can invoke Lemma 6 and Lemma to conclude that all μ4 are almost surely distinct. So I set contains only one element almost surely.
31


Reviews:
[{"review_id": "6Jmr4xulL9", "reviewer": "Reviewer_fPRW", "summary": "The paper introduces CoCa-BO, a unified framework that optimises intervention policies while jointly selecting the policy scope (which variables to intervene on and which contexts to condition on) using causal structure and observed context. It generalises and connects Causal BO (CaBO), which uses a known DAG but ignores context, Contextual BO (CoBO) which uses context but fixes scope showing that either alone can suffer linear regret in plausible settings. CoCa-BO treats each possibly-optimal mixed policy scope (POMPS) as an arm in a bandit over scopes, and within a chosen scope runs contextual GP-BO (HEBO) to select the intervention values. The authors provide worst-case and instance-dependent high-probability regret bounds and experiments demonstrating sublinear regret and lower sample complexity in high-dimensional problems.", "questions": "1. In large-dimensional settings, how does the model avoid the curse of dimensionality when embedding context directly into the GP input? Were any dimensionality-reduction or feature-selection methods considered?\n\n2. For graphs with many nodes, enumerating POMPS can be exponential. Could you discuss heuristic or approximate methods for pruning scopes without losing theoretical guarantees?\n\n3. Can you show a task where the same interventions yield different optima under distinct contexts, demonstrating that context truly modulates causal effects?\n\n4. Have you compared against meta-learning or multi-task BO baselines that can share context information across tasks, to isolate the benefit of causal reasoning?\n\n5. What happens if you remove context from the GP input but keep the same scope structure? Does performance drop substantially, confirming that context contributes non-trivially?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper presents a clean framework that truly unifies causal scope selection with contextual action choice and identifies precise failure modes of CaBO/CoBO. \n- The authors also provide sound theory with practical knobs. That is, there are clear regret guarantees with interpretable dependence on info gain; the approach also uses well-known GP-UCB machinery. \n- Scope-as-arms with HEBO inside each arm is sensible and parallelisable; \n- The paper is careful about the acquisition mismatch in contextual settings. \n- There are also compelling empirical examples which show when each baseline fails and how CoCa-BO succeeds;  The work also includes a large dimensional environment in A.3 to stress sample efficiency.", "weaknesses": "- The approach requires known causal structure; while standard in CaBO, many real tasks need robustness to graph misspecification or partial knowledge. (They defer discovery to future work.)\n- Computing the POMPS set can be exponential in |V| (albeit parallelisable). For very large graphs, this may become the bottleneck.\n-The MAB over scopes uses historical acquisition values; bandit feedback is influenced by the within-scope BO’s learning speed and noise, which may cause slow scope identification when arms differ mainly via context distributions.\n- While reasonable, results depend on a single contextual BO backend; it would strengthen claims to show backend-agnostic performance (e.g., GPflow/BoTorch comparisons)\n- Robustness is explored but limited; at very high noise or with heavy-tailed outcomes, the GP assumptions might need adaptation.\n- Most importantly, the approach  treats context as an observable input variable but does not explicitly model how context affects the causal mechanisms or intervention effects (e.g., through structural equations). This limits causal interpretability since the GP simply learns correlations between c_t and outcomes rather than a causal modulation of intervention efficiency.\n- Each POMPS scope maintains its own contextual GP, trained on samples observed when that scope was active. This means data from different scopes, which might share the same contexts, is not shared across arms. In practice, this can lead to data inefficiency: if two scopes operate under overlapping context distributions, each must relearn context-outcome relationships independently.", "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": "IYVqxkMq1o", "reviewer": "Reviewer_Y6Wq", "summary": "The authors introduce a unified framework for contextual and causal Bayesian optimization (CoCa-BO) that aims to design intervention policies maximizing the expected value of a target variable. The proposed approach integrates both observed contextual information and known causal graph structures to effectively guide the search process. Theoretical contributions include worst-case and instance-dependent high-probability regret bounds for the algorithm. Empirical evaluations across diverse environments further demonstrate that the proposed approach achieves sublinear regret and significantly reduces sample complexity in high-dimensional settings.", "questions": "(a) The advantages  of CoCa-BO over CaBO with contextual modeling remains unclear. The authors should provide additional experimental evidence to explicitly demonstrate the advantages of CoCa-BO over CaBO when context variables are considered.\n\n(b) The experimental evaluation would benefit from including more baselines and diverse datasets to better substantiate the generalizability of the proposed method.\n\n(c) Minor issue: the spelling should be standardized to “Bayesian optimization” (instead of optimisation).", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper presents an extensive theoretical analysis of the proposed method. In addition, the authors use real-world examples to illustrate and support the proposed method.", "weaknesses": "Although the paper provides thorough theoretical results on the regret bounds, several important aspects require further clarification and experimental validation:\n\n(1) Missing Baselines.\n The experimental evaluation lacks comparisons with several relevant baselines, such as existing causal Bayesian optimization (CaBO) methods — e.g., CBO (Aglietti et al., 2020) and MCBO (Sussex et al., 2023). Even though the proposed framework targets a specific problem setting, existing CBO methods could potentially be applied and should therefore be included for a fair comparison. Moreover, standard Bayesian optimization (BO) baselines such as UCB-based methods should be evaluated as well, since in some scenarios UCB can outperform CBO approaches.\n\n(2) Limited Discussion of Related Work. \nThe paper should provide a more comprehensive discussion of prior work on Contextual Bayesian Optimization (CoBO) and include corresponding experimental comparisons. While the authors compare CoCa-BO against CoBO, they do not discuss other existing CoBO methods in depth, leaving the relationship between these approaches unclear.\n\n(3) Unclear Distinction from Existing CBO Frameworks. \n\nThe conceptual and methodological differences between existing CaBO and the proposed CoCa-BO remain insufficiently discussed. If existing CaBO methods are capable of incorporating contextual variables, the motivation for introducing CoBO and CoCa-BO becomes less convincing. For instance, in the illustrative example shown in Figure 1, the context variable C could also be integrated within most CaBO frameworks. \nTo strengthen the paper’s contribution, the authors should include additional experiments comparing CoCa-BO with CaBO models that explicitly incorporate contextual variables.", "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": "ucH0ZbnR6a", "reviewer": "Reviewer_xqZh", "summary": "The paper proposes CoCa-BO, a framework that unifies causal and contextual Bayesian optimisation by integrating the concept of Mixed Policy Scopes (MPSs) from causal inference with Bayesian optimisation (BO) methods. The algorithm operates in two layers: (i) a multi-armed bandit (MAB) mechanism that adaptively selects among possibly-optimal mixed policy scopes (POMPSs), and (ii) a Gaussian-process-based BO routine that optimises interventions within each chosen scope. Theoretical analysis establishes high-probability sublinear regret bounds for this hierarchical process. Empirical studies on synthetic causal models demonstrate that CoCa-BO avoids linear regret suffered by standard CaBO and CoBO baselines in regimes where either causality or context alone is insufficient.\nStrengths", "questions": "see above", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Summary\nThe paper proposes CoCa-BO, a framework that unifies causal and contextual Bayesian optimisation by integrating the concept of Mixed Policy Scopes (MPSs) from causal inference with Bayesian optimisation (BO) methods. The algorithm operates in two layers: (i) a multi-armed bandit (MAB) mechanism that adaptively selects among possibly-optimal mixed policy scopes (POMPSs), and (ii) a Gaussian-process-based BO routine that optimises interventions within each chosen scope. Theoretical analysis establishes high-probability sublinear regret bounds for this hierarchical process. Empirical studies on synthetic causal models demonstrate that CoCa-BO avoids linear regret suffered by standard CaBO and CoBO baselines in regimes where either causality or context alone is insufficient.", "weaknesses": "Weaknesses\nLimited empirical validation\n\nExperiments are mostly synthetic or semi-realistic; no real-world dataset or ablation studies.\n\nThe runtime overhead of managing multiple scopes is not quantified.\n\nIndependence across scopes\n\nEach POMPS maintains a separate GP, which may underutilise shared structure among overlapping interventions.\n\nDiscussion on potential information sharing (e.g., multitask GPs or shared hyperpriors) would be valuable.\n\nAlgorithmic detail gaps\n\nAlgorithm 1 is schematic; explicit update formulas for Opts.update() and A.update() are missing.\n\nSchedules for \\beta_t,\\rho_t and constants in the bounds are not provided, hindering reproducibility.\n\nClarity\nGenerally clear and well-written, though dense. A figure illustrating the two-level UCB mechanism (scope-level vs. within-scope) would enhance intuition. Captions could be more self-contained. Also the authors could reintroduce POMPS and MPS for better readability. \nRelation to Prior Work\nMissing citations include:\n\nAglietti et al. (2020) Multi-task Causal Learning with Gaussian Processes (very relevant in my opinion)\nLattimore et al. (2016) Causal Bandits: Learning good interventions via Causal Inference\n\nChowdhury & Gopalan (2017)  On Kernelised multi armed bandits \n\nAdding these would help situate the work fully.", "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": "hOmKPLU1QV", "reviewer": "Reviewer_AJMc", "summary": "The authors argue that existing Causal Bayesian Optimization and Contextual Bayesian Optimization are not suitable for problems where both causal and contextual information is present. They propose a method which combines those two methods in order to construct a method which can handle such problems.", "questions": "1. Can the authors provide an example of a situation modeled by the mathematical problem described in the box at lines 120-128?\n2. Why would the practitioner/agent not use all of the context it has access to? Why should it choose any scope other than the maximal (and still informative) one at every step? Is it because mixed policies would be harder to learn or is there something else to it?\n3. The past observations (line 122) do not include the elements of $\\mathbf{v}_{l}$ not in $\\mathbf{c}_{l}$. Is this sensible? I understand that the mixed policy only makes use of the $\\mathbf{c}_{l}$, but why not make use of the observed $\\mathbf{v}_{l} \\setminus \\mathbf{c}_{l}$ in future steps?\n4. Your definition of POMP drops the requirement of them being NROs from (Lee & Barenboim 2020). What is the justification for this? This should be justified in the paper.\n5. In line 133, why $\\mu^{*}_{S} > \\mu^{*}_{S'}$ instead of $\\mu^{*}_{S} \\ge \\mu^{*}_{S'}$? As it stands, won't we eliminate MPS $S$ that are indeed optimal for some SCM, but it just so happens that there is another MPS $S'$ which leads to the same average reward? It seems to me that both $S$ and $S'$ should be taken as POMPS in that case, not both eliminated.\n6. In line 138 you state that the regret would increase linearly. Why?\n7. Isn't the MAB too \"complex\" to actually converge to something useful? I'll explain: the MAB has POMPS as arms, but for each POMP $\\mathcal{S}$ that it may choose, there are multiple (possibly uncountable) policies $\\pi_{\\mathcal{S}}$ that can be chosen; hence the $\\mu_{S}$ that the MAB is trying to maximize is an expected value over a complicated distribution combining the different $\\pi_{\\mathcal{S}}$ and the probabilities of each of them being chosen, which heavily depends on the details of the chosen BO method. Another way of viewing this, is that each arm of the MAB does not simply have one reward distribution, but multiple, and the choice of which to sample from is done by the BO. Could you explain why this is not an issue?\n8. Related to the previous question: from what I gather, what we want to choose is not the best $\\mathcal{S}$, but the best pair $(\\mathcal{S}^{*}, \\pi_{\\mathbf{S}}^{*})$. It seems to me that it could easily happen that the best such pair would not be found by the proposed method. It may happen that $A$ suggests $\\mathcal{S}^{*}$ a few times but a very bad $\\pi_{\\mathcal{S}}$ is suggested by the BO, and the MAB \"concludes\" that $\\mu_{\\mathcal{S}^{*}}$ is low and starts picking other MPSs. Thus, I do not see the algorithm being trustworthy for reasonable (i.e. non-astronomical) numbers of $T$. Could you explain why this is not an issue?\n9. In the paragraph starting at line 237, the authors justified why CaBO's selection method is unsuitable for the case with context. But why is CoCa-BO's method suitable? This is not explained in the main text/in a high-level way. Could you also include a discussion of your method and why it is suitable in the main text?\n\n### Other comments\n\n- It should be clearer that the definition of mixed policy scope comes from (Lee & Bareinboim 2020), for example by citing in the definition's title. Same comment holds for other concepts taken from that or other sources.\n- Re-defining $G_S$ in the first footnote can cause confusion. I would stick would the formally correct definition only.\n- \"the nature generates...\" (line 123/124) is strangely phrased.\n- typo line 132: ...*is* a possibly-optimal...\n- In line 136, you retroactively changed the protocol in the box. This can make it confusing to understand the exact problem this paper is trying to solve.\n- typo line 919: equivalence\n- Defining the MAB as a mapping seems to hide the actual complexity of that step. I would suggest explaining in detail what is the MAB problem here (see also question above).\n- line 209: I do not see how the details of the MAB update step are provided by Algorithm 2. Is this a typo?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper illustrates well (albeit with a toy example) that using only context or only causal information can lead to unnecessarily large regrets.\n- Despite \"simply\" combining Causal BO and Contextual BO, this blend is non-trivial enough for the contributions of this paper to be relevant.\n- Both experimental and theoretical evidence is presented in defense of the proposed method.", "weaknesses": "- The introduction does not motivate the problem (where does it emerge? Any specific cases?), and the first paragraph seems disconnected from the rest, mentioning POMISs, which are not used anywhere in the text.\n- Not enough is said about CaBO and CoBO for context, and for comparison with the method proposed in this paper. It should be very clear where exactly this method differs from those two.\n- It is not explained why the problem/task of the agent (lines 120-127) is relevant to study in the first place, even in principle. This is my most serious problem with this paper. See questions 1-3 below about this.", "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)