Bayesian Causal Bandits with Backdoor Adjustment Prior
Authors: Jireh Huang
Qing Zhou
Venue: Accepted by TMLR ()

Abstract: The causal bandit problem setting is a sequential decision-making framework where actions of interest correspond to interventions on variables in a system assumed to be governed by a causal model. The underlying causality may be exploited when investigating actions in the interest of optimizing the yield of the reward variable. Most existing approaches assume prior knowledge of the underlying causal graph, which is in practice restrictive and often unrealistic. In this paper, we develop a novel Bayesian framework for tackling causal bandit problems that does not rely on possession of the causal graph, but rather simultaneously learns the causal graph while exploiting causal inferences to optimize the reward. Our methods efficiently utilize joint inferences from interventional and observational data in a unified Bayesian model constructed with intervention calculus and causal graph learning. For the implementation of our proposed methodology in the discrete distributional setting, we derive an approximation of the sampling variance of the backdoor adjustment estimator. In the Gaussian setting, we characterize the interventional variance with intervention calculus and propose a simple graphical criterion to share information between arms. We validate our proposed methodology in an extensive empirical study, demonstrating compelling cumulative regret performance against state-of-the-art standard algorithms as well as optimistic implementations of their causal variants that assume strong prior knowledge of the causal structure.

Published in Transactions Machine Learning Research (01/2023)
Bayesian Causal Bandits with Backdoor Adjustment Prior
Jirch Huang
jirchuuan@Bucla.com edu
Department of Statistics University of Californio, Los Angeles
Qing Zhou
zhoudistat. ucla. edu
Department of Statistics
University of California, Los Angeles
Reviewed on OpenReview: https: // openreview. net/ forum? id- GMoGu5Kfml fm
Abstract
The causal bandit. problem setting is sequential decision-making framework where actions interest correspond to interventions on variables in a system assumed to be governed by a causal model. The underlying causality may be exploited when investigating actions in the interest of optimizing the yield of the reward variable. Most existing approaches assume prior knowledge of the underlying causal graph, which is practice restrictive and often unrealistic. In this paper, develop novel Baycsian framework for tackling causal bandit problems that does not rely on passession of the causal graph, but rather simultane Itaneonslyy learns the causal graph while exploiting causal inferences optimize the reward. Our meth- ods efficiently utilize joint inferences from interventional and observational data in unified Bayesian model constructed with intervention calculus and causal graph learning. For the implementation of our proposed methodology the discrete distributional setting, we derive an approxination of the sampling variance of the backloor adjustment estimator. In the Gaussian setting, we characterize the interventional variance with intervention calculus and propose simple graphical criterion to share information between arms. We validate proposed methodology in an extensive empirical study, demonstrating compelling cumula- live regret performance against stale-of-thh-art standard algorithms as well as optimistic implementations of their causal variants that assume strong prior knowledge of the causal structure.
1 Introduction
The multi-armed bandit (MAB) problem is well-known sequential allocation framework for experimental investigations [Berry & Fristedt 1985). Classically, the MAB problem formulation features an action set consisting of [A|
actions, also called arms, typically corresponding to interventions. Each arm E A defines real-valued distribution for the reward signal, with expected reward Pa. The objective of an allocation policy is to sequentially pick arms in a manner that maintains a balance between exploration and exploitation the interest of identifying and obtaining the greatest reward. Maximally and effectively utilizing all available information is imperative, especially when investigating interventions that are either or both demourddd and time-consuming.
Lattimore et al. (2016) proposed the causal bandit (CB) problem setting wherein non-trivial probabilistic causal model is assumed to govern the distribution of the reward variable and its covariates [Pearl] 2000).
The addition of cansal assumptions introduces avenues by which interventional distributions may be inferred from observational distributions and information may be shared between arms. Most works addressing the
CB problem exploit strong assumptions as to prior knowledge of the underlying causal model to achiove improvements over standard MAB algorithms. In this work, develop Bayesian CB framework that.

---

Published in Transactions on Machine Learning Research (01 (01/))
does not roquire prior knowledge of the underlying causal structure, but instead efficiently utilizes previously available observational data and acquired interventional data to inform exploitation and guide exploration.
For illustrative purposes, we borrow and adapt the farming example described in Lattimore et al. (0016) as an illuminating motivating example of the problem setting of interest and the surounding challenges. Suppose a farmer wishes to optimize the yield of a certain crop, which she knows is only dependent on temperature, a particular soil nutrient, and moisture level. While she understands that crop yield is somehow affected by these factors, the underlying causality governing this system of four variables (including crop yield) is unknown to her. The farmer's resource limitations restrict her to intervening on at most one factor in cach crop season by adjusting the temperature, controlling the soil nutrient content, or regulating moisture level. These experimental interventions are costly to perform, and each realization of the interventional data can only be observed once a season. Hence, is the farmer's best. interest. to leverage her historical logs containing observational data accrued from previous seasons where no interventions were performed, but rather the variables were passively observed as they naturally varied from season to season. In this paper, we propose a framework by which the farmer may aggregate and synthesize the available evidence to optimize resource allocation to attain the highest yield.
1.1 Related Work
In its original formulation by Lattimore et al. (2016), the CB problem prosupposes knowledge of the un- derlying causal graph. Accordingly, most proposed CB algorithms require knowledge of the causal graph
structure (Lattimore et. al. 20166; Lee & Bareinboim 2018 Maiti et al. 2021 Yabe al. 2018), and some
additionally assume certain model parameters are given (Lu et al.) 2020 Nair et al.) 2021 ). Furthermore,
many approaches are dependent on some restrictive form or class graphs. These assumptions are restrictive and often unrealistic in practice.
More recently, Lu et al. (2021) proposed a central node approach based on the work of Greenewald et al. (2019) that does not assume prior knowledge of the causal graph, but rather asymptotic knowledge of the observational distribution. Their approach is restrictive in terms of structural and distributional assump- Lions, and while it is generally reasonable assume that observational data is much more accessible than interventional data (Greenewald et al., 2019), the large-sample observational setting is not often realistic. de Kroon ct al. (2022) proposed an cstimator using separating sets to share information between arms with- out assuming prior knowledge of nor requiring discovery of the causal graph. Their methodology makes no attempt to learn the causal graph, and makes use of observational data only to strengthen conditional independence testing to identify separating sets.
Relevant to our work is intervention calculus, set of inference rules proposed by Pearl 2000) that defines avenues by which interventional probabilities may be estimated from observational data. In the CB setting, Lattimore et al. (2016) and Nair et al. (2211) consider graph structures with no confounding such that the interventional distributions are equivalent to conditional distributions, and Maiti et al. (2021) proposed a consistent estimator for the expected reward for discrete variables using both interventional and observational data in the presence of confounding. Our work extends the Bayesian model averaging approach proposed by Pensar et al. (2020) wherein the possible causal effect estimates are averaged across an observational posterior distribution of graphs.
Bayesian approaches to the MAB problem has received significant attention in the past decade. Russo & Van Roy| (004)) translated existing regret bounds algorithms based on optimism in the face of uncertainty to Baycsian regret bounds for posterior sampling by establishing deep connection between the two in their study of the Bayesian regret. In their informationn-teerreie analysis of Thhompoon sampling, [Lu & Van Roy (2019) demonstrated improved regret. performance by leveraging prior information regarding the bandit environment, which was further tightened in the form of prior-dependent bound by [Keton et all (2021). Numerous developments to learn the prior have been proposed in the bandit. meta-learning space [Basu al.] 2021 Kveton al.) 2021 Wan et al. 2021 Hong al. 2022), with many works studying the effects of prior misspecilication (Bastani et al., 2022 Peleg et al.) 2022; Simchowitz et al., 2021). J. While these contributions operate in the multi-task setting, seoking to learn the prior by solving many similar tasks typically corresponding to bandit. instances, our work more resembles the approach of Kauffann et al. 2012

---

Published in Transactions on Machine Learning Research (01 (213))
in applying Bayesian tochniques tackle single bandit instance. In such a way, rather than an estimate of the task prior, our proposed prior is best interpreted encoding the prior information on the underlying parameters of a given bandit instance based on available observational data generated within the task.
1.2 Our Contributions
We approach the CB problem from a Bayesian perspective, assuming simply that finite samples of observa- lional data are available. Importantly, we do not assumee the causal graph is known, nor are we restrictive as to the class of graph structures. We design novel Bayesian CB framework called Bayesian Backdoor Bandit (BBB) that efficiently utilizes the entirety of evidence from an ensemble of observational and inter- ventional data in a unified Bayesian model. Our proposed BBB methodology quantifies the uncertainty in the expected reward estimates as contributed to by the reward signal and the causal model to identify po- tentially profitable exploration, simultaneously learning the causal graph in addition to and for the purposes of improving estimates to exploit. Through extensive numerical experiments, we validate our methodology by demonstrating compelling empirical performance against both non-causal and causal algorithms. In par- ticular, we show that our BBB approach is able to leverage modest samples of observational dala, scamlessly integrating causal effect estimation and structure modeling, achieve substantially superior cumulative regret performance compared to standard algorithms that make no use of observational information. We similarly demonstrate competitive performance against a generously optimistic version of the causal central node approach propased by Lu et al. (202)) that assumes large-sample observational data. A preliminary analysis shows that, under some assumptions on the posterior distributions in our Bayesian model, the de- pendence of the cumulative regret of BBB algorithm on the size of the action space can be greatly relaxed given sufficient amount of obscrvational data.
Additionally, detailing the application of our mothods to the discrete and Gaussian distributional scttings, propose various developments that are of independent interest. In the discrete setting, we derive ap- proximation for the sampling variance of the backdoor adjustment probability estimate. In the Gaussian setting, we characterize the interventional variance of a target variable using intervention calculus and corre- spondingly propose an estimator, and we propose a simple graphical criterion for sharing causal information between arms to perform intervention calculus with jointly observational and interventional data.
The remainder of the paper is arranged as follows. We first review relevant background and notation in Section 2 Then, we develop the formulation of our proposed Bayesian backdoor adjustment prior and its posterior update in [Section 3 discussing the design of informative conditional priors given graph and Bayesian model averaging across graph structures. In [Section 4 we develop our proposed algorithms by applying established MAB algorithms under the BBB framework, and we discuss details regarding the implementation of BBB in the discrete and Gaussian settings in [Section 5) Finally, we provide extensive empirical results in Section 6 and conclude with discussion in [Section 7 Appendices A through D contain proofs, additional details and numerical results, and tochnical derivations.
Preliminaries
We consider the setting where the generative model governing a joint probability distribution P of a set of p variables X = (Xi....,
is a causal Bayesian network (CBN). A CBN model is defined by 5 = (g, 0c) consisting of its structure G, which takes the form of a directed acyclic graph (DAG), and its parameters Og. Its DAG 9 = (V,E), often referred to as the undorlying causal graph, is composed of a set of nodes V (I,1,...,77 in one-to-one correspondence with the variables, and set of directed edges E oriented such that there are no directed cycles. As is standard in causal literature, we may refer to a node i E V and its corresponding variable X; X interchangeably. In our work, we assume that X is causally sufficient. system with no unobserved confounders.
The causal implications imposed by the underlying CBN of X are expressed in the form of structural equation model (SEM), X, = S(Paffe.) ex) for all E V, where Paf = (X, j - E E} is the parents of X, in G and E; is an exogenous noise term. Otherwise stated, cach variable X, is a function of its direct causes in and an independent noise variable, which defines its conditional distribution P(X; Paf 05)

---

Published in Transactions on Machine Learning Research (01 /2033)
with local parameters of E dg. The joint distribution P imposed by the CBN factorizes according to structure G: P(X)= = P(X; Pa{.0f). Realizations from P(X) without any experimental intervention are referred to as obscrvational data, whereas interventional data are rcalizations of the SEM when the value of one or more variables are being coltrdlled by intervention. In our work, we consider deterministic atomic interventions denoted do(X, xz) (Paar 1995), where single variable is forcibly controlled to a fixed value 2 Dom(X;). This has the effect of mutilating the cansal graph by deleting the direct effects of Pay on correspondingly modifying the SEM to x;= zj and x, = f(Paf ,s) for all i E V The interventional distribution P(X X, do(X, = my)) is not in general equivalent to the observational conditional distribution P(X) \ X, X3 = 2z), motivating the calculation of the interventional distribution from the observational distribution, such as (1 below, which we refer to as interventional calculus.
The action set. A consists |A| = K arms that correspond to interventions on variables in X Y. where Y Xp is the reward variable (Lattimore et al. 2016). In particular, let arm E A correspond to the intervention do = za), fixing X to some value 2e E (a:)) where (a) E V is the node corresponding to the intervened variable. The expected reward of each arm a E A is given by Pa Ep(Y do(X = xa)] where Fp[[] is the expectation in P defined by CBN B, and there is some optimal arm a* argmna a Pa corresponding to the optimal reward μ == Mar. Given a horizon of time steps T, let a E AA be the arm pulled by an algorithm time steps with a balance between exploring different arms and exploiting the reward signal to minimize the expected cumulative regret BI - )l
time step E 7-) The objective of the algorithm is to pull arms over T
We now describe Bayosian approach to the general MAB problem, with some notation adapted from Kaufmann et al. (2012). The parameters O = (0a)aEA assumed to mutually independently define the corresponding marginal reward distríbutions po, (v) Ply = y do(X,a) (a) = saal, jointly follow modular prior distribution x+,) = II (0))). Typically, (5")aE are chosen to be all equal and uninformative. When arm a E A pulled at time step L and a realization ye +- Y do(X = Ne.) is observed, the posterior IT' is computed by updating according to nú (fa.) x ps_, (we) TTr (lm.). while n.. m for a & Oe. For each arm E A, the posterior va induces posterior distribution for the expected reward Na: which is simply a marginal or transformation of xy since, in general, Pa function of 0a. These posteriors are utilized by Bayesian MAB algorithms, which we discuss and apply under our proposed framework in Section 4
In our problem formulation, we assume possession of no samples observational data Do prior to inves- tigating arms. We denote by Dít) the interventional data acquired by pulling arm or at time t, and by D.14 = Uist,az= D(I) the accunulated interventional data from arm a through time l. The combined ab- servational and interventional data accrued through time t is Dit] = Do UnEA Dalt), which we refer as ensemble data.
3 Designing Informative Priors with Intervention Calculus
In this section, we detail the design of the cornerstone of BBB and what we refer to as the backdoor ad- justment prior, an informative prior II that distinguishes BBB from standard non-causal bandit algorithms by encoding inferences from observational data and seamlessly integrating interventional data to update to the posterior IT', We begin by introducing the construction of conditional priors given backdoor adjustment sets before continuing to obtain the backdoor adjustment prior by Bayesian model averaging over parent set probabilitics. We conclude by discussing the formulation and considerations of the posterior distribution over graph structures that gives rise to the parent set probabilities.
Conditional Priors. For each arm a E A, construct conditional priors (0a) using the backdoor adjustment given sets Z C X \( X(, as follows. If Z satisfies the backdoor criterion relative to X and Y Pearl 2000 Definition 3.3.1), then the interventional distribution Y do(X,,; = 2a) may be expressed terms of the joint observational distribution of (X Y) Z via the backdoor adjustment (Pearl 2000
Theorem 3.3.2):
PLY =y do(X,.) = ka)]=
Σ (ED(
P(Y = X = Ez, 2 2) = z).
(1)

---

Published in Transactions on Machine Learning Research (01 /2023)
Eq. provides an avenuc through which an estimator for Ma using obscrvational data may be derived, which we denote Ra,bda(Z) and with which we design informative prior Talz such that the induced prior distribution of the expected reward Aa satisfics
E 2 [Ma] = Da. (Z), Var, 2/2 [ua]= = SEE Aun.bda (Z)].
(2)
Here, E.g [I] and Var, H are respoctively the expectation and variance in ma and SE [An. (2))
the estimated sampling variability of the expected reward estimate bd, in P. The matching of the prior variance with the sampling variance of the backdoor adjustment estimator endeavors to assign the appropriate prior effective sample size. When arm at = is pulled at time step (I....,f} and realization of the reward Y/ + Y do(X = za) is observed in D(O, the posterior zaz is computed by updating according to (0.)) po. (ye) 1 (8.).
Parent Set Averaging. Thus far have taken for granted the possession of adjustment set Z, the validity of which is dependent on the underlying causal structure G which we assume to be unknown. If Y & Pa (ay> then Z = Pa satisfies the backdoor criterion relative to X,a and Y, and its uncertainty is quantified by the posterior probability P(Paça = Z D(t)) given the ensemble data at time t. Accordingly, the posterior of 0g is determined by averaging over all possible parent sets for iaa;
Fta (0a)
Σ (9) = Z D(t)), (CX(X(
which is the key posterior distribution to be updated at each time step in the Bayesian CB problem. Note that if Y E Pay then P[Y do(X,a) = za]] P(Y y) holds straightforwardly for DYm(Y). Accordingly, if Y E Z, we compute Pa,bda with the marginal distribution of Y for the design of Ta
Structure Posterior.
The parent set distribution in 3 is obtained according to a posterior distribution of DAG structures informed by jointly observational and interventional data D/c]:
P(Pa. = Z D(t)) = Σ
P(g' D(t)).
(4)
G'PaP'= =
The structure postcrior is given by P(g D(t)) x P(D ()P()), where P(G) is the structure prior, and the marginal likelihood P(D[t] 9) = P(D G 0,0)) 9)d0g is obtained by integrating the likelihood function over the support of conjugate prior of the parameters as follows. Let m I (I...., ..) index the M = no + samples of data in D(t), and let O, C I represent the data points for which X, is not fixed by intervention. We make standard assumptions for Bayesian network structure learning, namely that the priors for the parameters of the conditional probability distributions satisfy global parameter independence, with (9x)) = IITE "aig(Oa), as well as parameter modularity, with (Oa) = =" xgigr(0)) = =" zz (0.) for graphs & and g' where Pa.. = Pa = Z (see Heckerman et al. (1995) and Friedman & Koller (2003 for details). These allow us to express the marginal likelihood as P(D[(] G) I1 P(a,[O.] pa (O.)), where 2=]:1] and paf [:] represent indexed samples of X; and Paf in DI4). respectively. Assuming a conjugate prior, each conditional likelihood P(x; (O,] pa. [O.]) can be calculated in closed form by integrating over the parameters:
/ II P ((aafm paf (m], 09) pa0 LmEO,
P(a,OO1 pa.1).))
(5)
where 08- = xpa is the parameters specifying the conditional distribution of X, given its parents & Murphy 2007).
Eaton
Assuming the distribution P is faithful to G (that is, all and only the conditional independence relationships in P are entailed by 9), the posterior probability P(g D(t)) will concentrate around the Markov equivalence class with increasing samples of observational data no- The equivalence class consists of the identification

---

Published in Transactions on Machine Learning Research (01 (202))
of all direct edge connections (that is, the skeleton of 9) and some edge orientations called compelled edges, but even with infinite observational data, in general, not all edge orientations are identifiable without inter- ventional data. The effect on P(g) |
D(t)) of pulling arm a E A and observing interventional data according to the intervention do( (a: va) is primarily though not limited to that of clarifying the orientation of the edges incident to [a; in g.
Considering that the DAG space grows super-exponentee
with the number of variables (Robinson, 1977
computation of the parent set probabilitics P(Pa; D[4) is admittedly challenging, even when the maximum number of parents is restricted. Due to the computational complexity, it is standard to assume a structure prior satisfying modularity that is P(g) = P(Paς), so that the posterior distribution is proportional to decomposable weights consisting of the product of local scores depending only on a node and its parents [Friedman & Koller 2003). This property score deconupssaiiitt is crucial for the efficient. implementation of Markov Chain Monte Carlo (MCMC) methods in which the probability distribution of features in G may be estimated by sampling DAGs from Markov chain with stationary distribution P(g D(t) (Madigan jot al. our purposes is algorithm developed by Pensar et al. (2020) to compute the exact parent set probabilities
1995 Friedman & Koller 2003; Kuipers & Moffa 2017 Kuipers et all, 2022). Particularly useful for
for a graph in time (3"p) that also takes advantage of score docomposability. In our empirical evaluation of BBB, we apply BBB using both exact computation of parent set posteriors as well as approximation with MCMC sampling.
4 Bayesian Backdoor Bandit Algorithms
In this section, we apply our proposed BBB framework to several state-of-the-art MAB algorithms, namely upper confidence bound (UCB). Thompson sampling (TS), and Bayesian UCB (Bayes-UCB). Each method is concerned with designing and computing some criterion (t) to maintain balance between exploration and exploitation when selecting arms according to a E argmax, (t).. In what follows, we briefly intro- duce these methods and discuss their application under the BBB framework. We then provide preliminary theoretical analysis of the cunmlative regret for BBB-UCB and BBB-TS.
4.1 Description of Algorithms
The general UCB family of algorithms operates under the principle of optimism in the face of uncertainty (Lai & Robbins 1985). Arms that have not been investigated as many times as others have more uncertain reward estimates and thus optimistically have potential for greater reward, motivating the design of padding function (t) for computing the selection criterion U.(1) (a(()) (t)... Intuitively, the combination of the expected reward estimate (t) and the uncertainty Ft(t) maintains a balance between high confidence exploitation and potentially profitable exploration. Perhaps the most well-known and typically the default
instantiation of UCB algorithms is UCB1 (Agrawal 1995 Auer et al. 2002) which computes the following
criterion:
Ua(1) = Pa(1 -) + eolool/ 1)/na(t -1), 1),
(6)
where (4) = Ei=, (a a} denotes the number of times arm a has been pulled in & time steps. The confidence tuning parameter > 0, discussed in [Sutonn & Barto (0118), controls the desired degree of exploration, where = v2 in Aucr et al. (2002). Hercafter, when discussing UCB, we refer to the policy expressed by the criterion in 66.
In what we refer to as BBB-UCB, we estimate the expected reward with the posterior mean E with respect to Bp and we replace 1/na(t- - 1) with the posterior variance Var,, [[aa] ~ 1/(no + nalt - 1)). In particular, lor each arm A, we compute
(t( = Eze- [pa] + o/ Var_.- [Mm] log(t),
(7)

---

Published in Transactions Machine Learning Research /2023)
where, for outer expoctation with respect the parent set distribution Pz-1(Z) P(Pa; Z Dit 1])
E [Mt]] = Eg, B
[Ma]]
Var.: [Ma] = Ep, Var,, 2/2
[Ma]
+ Varr,
E [ma]]
The Bayesian procedures of Bayes-UCB UCB and TS especially amenable to straightforward application under the BBB framework. These methods follow the Bayesian MAB formulation introduced in [Section 2] typically taking as imput uninformative priors in IT that are equivalent for each arm. cach time stop t, TS samples the expectations from the posterior (t) +- (Ma), effectively selecting arm A with probability oqual to the posterior probability that pa is the highest expectation (Thompson, 1933). Baycs-UCB instead computes for each time t an upper quantile of Na based on its posterior dist.ribttin induced by x/-
m Ua(t) Q (1 (1oogTTo
where Q(r, p) is the quantile function defining P,(X s Q(r p)) r for probability distribution p and random variable X ~ and is a constant for computing the quantile used in the theoretical analysis of Bayes- with c empirically preferred (Kaufmann ot al. 2012).. For the BBB variants of Baycs-UCh and TS, we need simply supply our designed backdoor adjustment prior 11 and make appropriate Bayesian updates to obtain the posterior II'
We present our proposed BBB methodology applied to Bayes UCB, TS, and UCB in Algorithm
Algorithm 1 BBB-Alg(T)
Require: Horizon T, action set A, observational data Do, confidence level
1: Compute the observational parent set posteriors
2: for all E A and C X \ ((a;
3: Compute T
according to (2)
4: end for
5: for all 1= I..., T do
6: for all A do
7:
Compute criterion (f) according to Alg:
Bayes-UCB: (a()) Q(1 1/(1[log ()9, as in S
TS: Sample (t(t) T/a (pa))
UCB: Ua(t) E ev Var (uo) log(t) as
8:
end for
Pull arm a argmax (t) and observe (())
10: for all Z C X Naa; where a = dg do
Update Taiz according to zz (0.) x Po. (uc) 2 (0a)
end for Compute update the parent set posteriors 14: end for
4.2 Preliminary Regret Analysis
In this section, we provide some preliminary analysis the Bayesian cumulative regret for BBB- UCB and BBB-TS. We begin by defining the Bayesian cumulative regret. Given reward parameters O,,, the (expected) cumulative regret of a policy is defined as
T (or)
Rr(OA)=
Σ (n*
O

---

Published in Transactions Machine Learning Research (01 /2023)
where the parameters A are fixed. Under our Baycsian setting, we specify prior P(9) over the DAG and conditional priors T9 for the parameters of the reward distribution under interventions a A, which defines a prior IT over A- The Bayesian regret averages the regret (r(@A) over the prior distribution IT::
R$ = Eno (RA(OA)) = EB1 -orl:
where the second expectation is with respect to the joint distribution the parameters and the data [G, A, D Note that (a(OA) )) is random variable under the Bayesian setting, If Rí = O(g(T), then (+A) Oplg(T)) with respect to the prior distribution of (g, O.).
Without loss of gencrality, assume Ma E [- for all E A. We first analyze the BBB-UCB algorithm [Algorihhm By Eq. (2) Russo & Van Roy (2014), for the UCB sequence {ae].
R$ v Σ 1=1
BlU (t) Maal +
Elpc (t).
1=1
The first term ElU (t) [a.] (U,, (t) Ma. 1 113.. Since (a(t) a deterministic function of Dit - 1], we have E. [Ua (f) Dit 1]} Un, (f) and consequently,
ElUa, (1) - pa.l ElU,. - E(pa. Dit - 1])
=cv/log! Var(Ua. DDtt 1))
Scu/logt / [Va Ditt - 1])],
(10)
where the last inequality follows from Jensen's inequality. Note that Var(μa D(t)) (ar,+ and
E(pa D(t)) = (Ha, as in
We make the following assumptions on the posterior distribution p(ua D(t). See Appendix for detailed discussion on how to verify these assumptions.
Assumption 1. Let d, be the ramber of candidate parent sets for X For all t 121 1 and E A.
à + cāda expl (t)(-))na()),,
[ar((u D(t)
Bo + (t)
where and 8n are positive constants.
The Markov equivalence class the true DAG, represented by CPDAG, can be accurately estimated with large amount of observational data (ng is large). In such cases, d, < 2m is usually quite small, where m. the number of undirected edges connected to Xay in the CPDAG.
The second assumption the concentration of n² pa- around its posterior mean E(pa D(()):
Assumption 2. For all 2
p. 1r E((s D(())
Var(r D(1) ev log D[d]
cz6
where 63 and b are constants.
Proposition Under Assumptions
and
2 the Bayes regret of the BBB- UCB algorithm satisfies
R < c4 (VKT K2(mo 1) (2 - 1)) + Σ dda Vlog co.
(11)
where K (A] and 04,05,00 are positive constants.

---

Published in Transactions Machine Learning Research /2023)
Remark 1. By Proposition 1 of Russo & Van Roy 2014), the same upper bound Bayes regret of the BBB-TS algorithm.
11 also applies the
For any no 2 1, by concavity of VI,
K 1) KT (m0 - 1) VKT.
Therefore, when T is large such that E. Vil = O(VT), the regret. R Ol KT log To which identical to the order of the regret of standard MAB, e.g. Proposition 2 of Russo & Van Roy 2014). The benefit of our backdoor adjustment prior is seen when no is large relative to T. If 7/ - 1) < M, where M is a constant, then
{1
T
1/2
V ( KT
KT (m - 1) = K2 -1
-1
K(no - 1)
T
VMT
S
2/70 m1 -1
2
where the first inequality is due to (1 + 2/2/22 < + x/2 for x 2 0. In this case, we obtain a regret bound R O(vTlog independent of K. This confirms the advantage of using observational data to simullancously estimate all rewards Pa. A through backdoor adjustment, which largely relaxes the dependence of the regret on the number of actions.
Implementation Details
5.1 Nonparametric Discrete Setting
We now detail the application of our proposed construction of T to the setting where the conditional probability distributions are multinomials, with each variable X, X probabilisticall attaining its states depending on the atlained state configuration of its parents Pay. The reward variable Y Xp is a bi- nary variable with DYm = {0, 13. If Y & Z, Hh may be estimated with observational data through straightforward empirical estimation of [
1 Σ
nal I, Ja, zimole
Dud (Z) = P PPpy=1 = do( =xa]] =
(12)
mo/ 2)
where no[1, Fa, 2] represents the number of the no samples of Do which 1, Fas Z z, with corresponding definitions for n(z,,, z) and nzz).
Analysis of the sampling distribution (12) admittedly challenging. To design an appropriately weighted characterization of the sampling variability of f. Ada (Z).
informative prior proposed in (2). we require
Hence, we derive approximation of the variance of (12), SE (Ro, We accomplish this by first re- expressing the joint counts nal:] as sums elements of multinomial random vector. The term within the sum may then be expressed as a product and ratio of intersecting random quantities, which approximate through a first-order Taylor series expansion. The details of the derivation are delegated to Appendixx D appropriate acknowledge that Maiti et al. (2021) proposed a provably unbiasod strategy for empirical estimation of ( through splitting the sample into independent partitions. However, this approach suffers from severe loss precision through what some may consider underutilization of the observed data. In experiments detailed in [Appendix C.T. we find the empirical performance of [12 in applications to be acceptable. We additionally provide extensive empirical validation of our derived approximation, demonstrating coverage probabilities comparable to empirical estimates the sampling variability modest sample sizes.
Since the reward variable under arm a is a Bernoulli random variable with probability parameter Ha P|Y 1 do( ka)], assume conjugate prior T Beta( 30) for O. na designed according

---

Published in Transactions Machine Learning Research (01 /2023)
to resulting prior hyperparameters
Pa..daa [Z)[1 Pa bda (2)
-1)
(1 (1- Ao, (2)
0xg = Ma, (Z)
3o 00
SE (da.bda(2) (2)
Aa, (Z)
5.2
Gaussian Unit Deviation Setting
In this section, we consider the setting where the causal model may be expressed as set of Gaussian structural equations:
P x,= 2 B. Ey N(,, j j=1,...,,
(13)
There no intercept term, which analogous having prior knowledge of the observational means, and we consider interventions E [-1,1], which may be interpreted as investigating unit deviations from the observational means. In this setting, the causal effect Xaa on Y is given by
Via: = Eply do(( =x' +I'+ ErlY do(X ='']
for any x' IR derived via special case of (I). Note that in our problem formulation, Y do(X 1) and -Y (a; -1) are identically distributed, so all data generated from interventions on (a;; may be combined to estimate Payy- Since μa, = Tabiaa we focus our efforts on estimating and modeling priors using intervention calculus, design priors saal for day
(aa.. Accordingly, in constructing corresponding to estimating pay and allow = to be the induced priors for 02 corresponding to pa Way dctailed as follows.
Y & Z, then a consistent estimator of bay denoted on, bda, may be obtained with observational data by the least squares regression
Y = + + + ee. e~ e~ N(O.
(14)
the coefficients of the parents Maathuis et al. 2009 Pensar et al, 2020 and some dependence on is omitted for simplicityy Correspondingly, express the desired interventional distribution as Y do(X = za) ~ N( w²). Claiming no prior knowledge of the interventional variance, we assume Normal-innerse-gamee gamma (N-r-1) conjugate prior =0 Taaziz for Ora: = (#)
where 7 R
Way | w² N (mo
w² ~ r-- 1 r (14,,N)) No).
(15)
Since in general, the residual variance n)² in 14h is not equivalent to w², we propose the following to estimate w2 from observational data.
Proposition 2. Suppose that X. follows the causal structural equation model (SEM) in (13 with CBN B. Let Y X, and denote by ao the causal effect of X on Y. Then for any E Dom(X),
Varp do(X r)] = Marr|Y-uxX)
Note that Vare(-] the variance in defined by CBN B, and the variance on the right side with respect to the observational distribution of X. Intuitively, subtracting by & negates the noise variances o² in [13 propogated through and from X to Y. We include a detailod proof for Proposition 2 in Appendix A
Thus, to estimate 22 from Do, propose the cstimator 3 Σ. 0)2/(no Z 2) where d realizations of y Y v (a,,, ())xaa (a; in Do, and ni [Z] 2 is the degrees of freedom resulting from estimating ア in addition to |Z| + coefficients in [4]. Accordingly, we design the prior w² ~ r (wo, vn) to have prior mean B[w"]= = u (uo - 1) = 2², resulting hyperparameters un = (no /2))/2 and to = Σ, //. After marginalizing out w², Vias ~ t2 (mo, vo(u)))) -1), so we set Eg [e)) = mo = (o,, (Z)
and solve to obtain v n0/ (0/(10 18, (2))).
10

---

Published in Transactions Machine Learning Research (01 /2023)
To maximally utilize the ensemble data, we further generalize the cstimation of Vi via regression in [14 to include eligible samples of intervention data. This is achieved through the following proposition, which we prove in Appendix A] This result does not rely on any parametric assumptions for the underlying cansal model, assuming simply that X follows a general linear SEM with DAG & (Pearl 2000).
Proposition 3. Suppose that X follows linear SEM with CBN B (G. θg) and X, X. Suppose that W E X (X,Y) does not block any directed path from X to Y in G. Then for any w E R,
à Eppy do(X = x)] = Oz 8x
Ep do( = x), do = w)]
Proposition 3 asserts a simple graphical criterion which, satisfied, defines an avenue by which information be shared between arms. In work, we check the graphical criterion for estimating the causal effect. of Xaa on Y with interventional data generated from intervening on X3 as follows. Using another algorithm proposed by Pensar el al. (2020) for computing exact ancestor posterior probabilities, we consider the criterion satisfied at time step if the event that X, blocks directed path from ((a; to Y has low posterior probability:
P(X X3 ~ Y D & (in(P ~ X, D(I), ~ Y D()) ST
(16)
where Xj ~ denoles that X, is an ancestor and the threshold is set to = 0.1 in our application. If [6 holds at time step t, we combine the observational data and the data from interventions on X, when conducting the regression [14]. While independent samples of observational and interventional data are not guarantced to have identically distributed errors the regression (14). we provide extensive empirical validation of our proposed regression with ensemble data in Appendix C.2 confirming indistinguishable performance for the purposes of estimating taa and its sampling variability compared to that of purely observational data.
Numerical Experiments
We conducted extensive numerical experiments to empirically validate our proposed methodology. For main experiments, we generated random CBN models in an effort to empirically demonstrate the merits of our proposed methodology by evaluating BBB across a broad range of scenarios. To address the com- then evaluated an implementation using MCMC to estimate parent set
putational challenges of BBB, probabilities and applied it to a larger realistic reference network. Comprehensive experimental details suf- ficient for reproducing our experiments, such as CBN preparation and algorithm parameters, are provided in Appendix B| Additional supplemental experiments independently evaluating (12) and Proposition may be found in Appendix C The complete code and instructions for reproducing our results have been made available the following link:
https:///ittubb.com http:/twww..co///eeeuaua/a//////
6.1 Random Networks
For our main experiments, generated CBN models with p= 10 variables in the interest of representing diverse range of scenarios in our empirical comparisons. The structures were randomly generated, with the reward variable designated to have Paf| = parents, according (2022). The conditional probability distributions of each CBN were likewise generated randomly. Atomic interventions as described in [Sectiin 5) were allowed on all variables excluding the reward variable, with the discrete variables assumed be binary, resulting in |A| 2(p 1) 18 actions.
process adapted from de Kroon et al,
We evaluated our BBB methodology against algorithms designed to optimize cumulative regret, including popular standard MAB algorithms Bayes-UCh TS, and UCB that do not utilize causal assumptions (see Scction 4p. Additionally, we compared against what can be interpreted as highly optimistic version of the central node approach by [u et al.] (2021), introduced in Section 1] by presupposing knowledge of the direct. causes of the reward variable. In particular, for UCyes-UCB*, TS* and UCB*, executed the

---

Published in Transactions on Machine Learning Research (01 (2033)
respoctive algorithms over the reduced action set A' = {a E A (a) E pa Accordingly, for the cases where (a") & pay, we redefined the optimal intervention to a* = a Pa when evaluating the regret of TS" and (Bayes-)UCB". To circumvent confounding arising from the differences in algorithm designs and any relevant parameter tuning, we focus our comparisons within algorithm types, e.g. amongst TS, TS", and BBB-TS.
Using the process described above, generated 100 CBN models for each distributtinal setting. For each CBN, we executed the competing methods 10 times but our BBB methods only 5 times due to their greater computational expense, with T 5000 time steps. The results presented are averaged across all simulations for each time step, with the cumulative regret normalized by the optimal reward μ² to ensure that each CBN model contributes comparably. In preference to the competing methods, we tuned for their best-performing parameters where relevant and applied them to our BBB implementatious. We computed exact parent set probabilities in BBB using an algorithm proposed by Pensar et. al.] (2020) in an effort to assess our BBB methodology the most precise implementation of its formulation. Additional experimental details may be found in Appendix B] and additional supporting results are provided in Appendix C
Note that while the simulations were exccuted across cluster of heterogencous nodes, it was not difficult to observe that the computational requirements of BBB vastly exceeded that of the considered competing methods. The average execution time of each iteration of our discrete and Ganssian implementations of BBB on the random networks was respectively around 4.3 and 8.2 seconds, compared to less than 0.15 seconds for the competing methods. This includes the exact. computation of parent set posteriors, computing or updaling corresponding backdoor adjustment estimates, and in the Gaussian case, ancestor posterior probabilities. While BBB requires signilicantly greater computational expense, the cost. must be weighed against other considcrations such as the time and resources roquired for additional exploration of interventions.
6.1.1 Cumulative Regret Comparisons
The empirical cumulative regret results in Figure 1 demonstrate that in both the discrete and Gaussian settings and for all algorithms, our BBB methodology is able to reliably outperform the non-causal variants with finite samples of observational data. The improvement increases monotonically with increasing sample sizes of observational data (Ro). While correspouding variants of Bayes-UCB and TS perform comparably, UCB achieves substantially lower regret, because the parameter e in (6) was tuned to maintain a balance between exploration and exploitation that most empirically preferred. In particular, UCB able to avoid excessive exploration by scaling its padding term with relatively small constant, whereas Bayes-UCIB maintains a relatively high minimum exploration rate according to its formulation in ( as does TS.
In comparison to the optimistic central node versions of the algorithms, BBB generally achieves lower cumulative regret with ng 2 800 in the discrote setting and np 2 40 in the Gaussian sotting. Recall that, in practical applications, the central node approach relies on the availability of large-sample observational data as well as sequence of interventions to recover the reward generating variables Pag. Based our simulation settings, this reduces the action set from |A| = 18 arms only |.4'| = 2|Pa = arms, and we additionally artificially restrict a* E A' to evaluate the regret. Furthermore, the regret results reported for these methods do not include the interventions required to identify Paς. thus representing a kind of best case scenario for the central node approach. In contrast, our methodology derives substantial benefit from modest amounts of observational data samples no-
Indeed, we find that our BBB methods are able to perform competitively against the competing methods even when the latter are given no time steps to explore arms before incurring regret. To compensate for the fact that BBB utilizes no samples of observational data prior to investigating arms, we present the results where the competing algorithms TS(*) and (Bayes-) UUC((*) are given a head start of no E (100-2* : 0,...... 5) time steps to explore arms before incurring regret. The results for the discrete set are shown in Figure 2 The Gaussian results are omitted because no S 320 is relatively small, so the head start does not offer substantial benefit to the competing methods. In all cases, BBB still siguificantly outperforms the standard algorithms TS and (Bayos-) given the head start. Given sufficient samples of observational data, BBB still performs comparably to if not better than the optimistic central node variants in terms of curulaatve
12

---

Published in Transactions Machine Learning Research (01 /2023)
Alg: Bayes-UCB
Alg: TS
Alg: UCB
Discrete Cumulative
300
200
01
Alg: Bayes-UCB
Alg: TS
Alg: UCB
Gaussian Cumulative
300
200
1000
2000 3000
4000
5000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Time Step
Alg
BBB-Alg(k-0)
BBB-Al((k-2)
BBB-Alg(K-4)
Alg"
Blg-A)
BBB Alg(k3)
Aig(k))
Figure Average cumulative regret against T 5000 time steps comparing Alg, Alg", and BBB-Alg for Alg E Claaes-UUIi, TS, UCB}. BBB methods were executed with no 100 2 in the discrete setting and no = 10 2 in the Gaussian setting.
regret, for which the head start only an additional unwarranted advantage given that they already require significantly observational data well additional interventions.
6.1.2 Structure Identification
In addition to the cumulative regret performance, it is of interest to consider the structure identification behavior of the BBB approach in our experiments. We measure the concentration of the posterior probability across DAGs G with respect to the underlying causal graph G* using the edge support sum of absolute errors (ESSAE), which is given at time t by
ΣΣ PU E Pa D(d) 1 {1 (.jePa.')) Pa
This quantity may be understood as a probabilistic version the structural hamming distance, a common metric in Bayesian network structure learning literature. Lower ESSAE corresponds greater concentration of the posterior probability around the causal graph G*_ The results are provided in Figure 3
In discrete results for BBBB-Bayes-UCH UCB and BBB-TS, the initial ESSAE is unsurprisingly lower for the larger sample sizes, but the trend quickly reverses the time steps progress. This effect is also observed occurring in the Gaussian results, but at an accelerated pace. This behavior is perhaps best understood in complement the cumulative regret results in Figure If is faithful to G, then if no large, the structure prior P(G Do) is expected to concentrate around the Markov equivalence class, which entails identification of the skcleton and in general, partial identification of the orientations. Additionally, the conditional priors Tazz will be precise models, allowing BBB quickly identify and select. arm(s) A with small regret.

---

Published in Transactions Machine Learning Research (01 /2023)
100
400
800
1600
3200
Bayes-UCh UCB
100
200
400
800
1600
3200
T5
100
200
400
800
1600
3200
UCB
Time Step
Aig
Alg"
BBB-Alg
Figure 2: Discrete average cumulative regret for Alg E (Bayes-UCB, TS, UCB} with a head start of no
(100 2 0.0,,. 0....... 5) time steps for competing mothods.
Alg: Bayes-UCB
Alg: TS
Alg: UCB
Discrete ESSAE
12
3-
0-
Alg: Bayes-UCB
Alg:
Alg: UCB
104
Gaussian ESSAE
8
1000 2000
4000
5000
1000
2000
3000
4000
5000
2000
3000
4000
5000
Time Step
BBB Alg(k))(
BBB-Alg(k-2) Blg-k))((-3)
Blg-A))(k-4) BBB-Alg(k-5)
BBB-ANG Alg(k))
Figure 3: Discrete (ng 100 2 and Gaussian (ng = 10 2*) results of the average ESSAE of the full graph structure for BBB--Alg Alg [Bayes- MCBy TS, UCB).

---

Published in Transactions on Machine Learning Research (01 (013))
-Ma which has the effect of clarifying the orientation of edges incident such (aa) The policies take no interest in determining the orientation of the remaining edges if the uncertainty does not indicate potential to identify more profitable actions. In contrast, when ng is small, the greater uncertainty in both the structure prior and the conditional priors encourage the exploration of many different arms, thus incurring greater cumulative regret. In addition to clarifying the orientation of the incident edges, selecting arm(s) a E A contributes to identifying the direct edge connections excluding those from Pay, to Xias, as can be seen in (5) Thus, the skelcton is recovered and more edge orientations identified than in the case where no is large, achieving lower ESSAE at the cost of greater cummllatiee regret. Notably, while this reversal appears to be absent in the discrote results for BBB-UCB, actuality it has simply not yet been realized even after T = 5000 time steps due to the small exploration constant c in
6.2 Scaling BBB With MCMC
Despite the efficiency of the algorithm proposed by Pensar el al. (2020) its scaling in p of (3Pp) means that exact computation of the parent set posteriors is not always feasible. Pensar et al. (0020) noted that their algorithm executed on 20 variables in about 25 minutes, which would translate to over 86 days for 5000 time steps. While potentially justifiable depending on the context of the application such as when interventions are particularly expensive or time-consuminng such intensive computational requirement for each time step is likely to be limiting of the practical application of BBB on larger systems. As discussed in Section 3) the parent set probabilities are derived from posterior distribution of graph structures which may be estimated by MCMC. In this section, we discuss the implementation of BBB using MCMC to estimate the structure posterior. We provide preliminary results in the discrete setting assessing this approximation against the exact computation of parent sets and evaluating its performance variables.
realistic reference network with p 20
The posterior distribution of graph structures P(G D(()) may be approximated by sampling DAGs Gf from P(g D(t) using MCMC and empirically estimating from the sampled graphs:
11 (Paf = =2]
P(Pa: = 2 2(()
SreG
Various MCMC sampling schemes for DAGs have been developed, most basic of which is the structure MCMC sampler which accepts proposed single edge addition, deletion, or reversal steps according Metropolis-
Hastings probability (Madigan et al. 1995; Giudici & Castelo, 2003). With order MCMC, Friedman & Koller (2003) reduced the search space to the topological orderings of the p nodes, significantly accelerating
convergence but retaining a degree of bias since a given DAG may belong to multiple orders. Kuipprs &
Moffa (2017) addressed this issue of bias by considering the space of ordered partitions in partition MCMC, Lhough al the price of greater computational requirement. (Suter el. al., 2021).
In our simulations, we chose to use order MCMC despite the potential bias due to its computational advantage over partition MCMC while achieving satisfactory performance. For further improvements in efficiency, we applied the hybrid approach proposed by Kuipers et al. (202)) in which DAGs are sampled from a loosely restricted initial search space, with built-in provisions to expand the search space. In particular, before performing any interventions, we obtained an initial search space with the PC algorithm (Spirtes & Glymour) 1991 and sampled DAGs from P(g Do). For subsequent iterations, we restricted the search space using the structure posterior estimated from the immediately preceding iteration. Whenever conducting the restricted sampling schome, the scarch space was allowed to be extended as designed by Kuipers et al. (022) to account for false negatives in the restriction.
We first compared the cumulative regret amongst exact computation of parent set posteriors (Exact), approx- imation by MCMC without restricting the search space at any step (MCMC), and MCMC with restricting the search space as described (Hybrid MCMC). Each of these were executed twice on each of the 100 ran- domly generated discrete CBNs, and the results at various time steps are shown in Figure 4 Hybrid MCMC performed cquivaleutly with unrestricted MCMC, enjoying significant computational reductions without ex- hibiting any inferiority in performance. However, while (hybrid) MCMC performed comparably with exact computation in most cases, there were significantly more extreme values in the MCMC methods. These
15

---

Published in Transactions Machine Learning Research /2023)
BGB-BByes-UCB
BBB-TS
BBB-UCB
>60
12 35 84
20
20
7
3.
17
17
20
22 23
60-
Cumulative Regret
200
00:
080
40
20
0
500
2000
3500
5000
500
2000
3500
5000
500
2000
3500
5000
Time Step
Exact
MCMC
Hybrid MCMC
Figure 4: Cumulative regret of BBB-Alg for Alg E (Bayes-UCi TS, UCB} with no 3200 the discrete random networks from Section 6.1 for time steps t E {500, 2000, 3500, 5000) comparing between computing exact parent set posteriors and approximating with MCMC. Each boxplot represents 200 data points, with the number of points above 60 labeled above.
may have resulted from the bias inherent to order MCMC, but given that general settings were applied and convergence was not assessed for each iteration, another potential explanation would insufficient itera- tions for certain CBNs. In general, approximation of the structure posterior with MCMC appears to be an acceptable scalable alternative to exact computation.
We then applied BBB with hybrid MCMC CHILD, moderately sized discrete reference network with 20 nodes for diagnosing congenital heart disease (Spiegelbalter 1992). CHILD was constructed with domain experts and made available a Bayesian network repository (Spiegelhalter 1992. Scutari 2010). The network preprocessed to have binary variables, and the target variable set to LowerBody leaf node with two parents. All other variables were intervenable, with |A| = 38 arms, though only [A4|| = for the optimistic central node approach.
The cumulative regret results for 20 executions of various algorithms are presented in F Figure 5) Even after = 5000 Lime steps, most methods fail to exhibit meaningful convergence in the form of the flattening of the cumulative regret curve. This is because all but two arms have expected reward Ma 0.5, making the optimal reward of approximately n = 0.622 difficult to distinguish without great deal of exploration. Unsurprisingly, the central node approach performs exceptionally well, having only four arms investigate. With по 3200, BBB was able to adequately distinguish the arms with higher expected reward, achieving cumulative regret competitive with the contral node approach. The average exccution time cach iteration of BBB with MCMC CHILD around 9.4 seconds, compared to less than 0.23 seconds for the competing methods.
7 Discussion
In this paper, we proposed the BBB framework for enhancing experimental investigations with observational data. BBB consists of an aggregation various strategies for estimating and modeling the parameters interest with jointly interventional and observational data in order efficiently utilize all available data to inform exploitation and exploration. Applied in our methodology but also independent interest, we derived well-performing approximation for the variance of the discrete backdoor adjustment estimator, and in the Gaussian setting, we characterizod the interventional variance using the observational distribution and proposed a simple graphical criterion for sharing information between arms. We supplied preliminary regret analysis justifying our methodology, and empirically validated our proposed algorithms through extensive
16

---

Published in Transactions Machine Learning Research (01 /2023)
Alg: Bayes-UCB
Alg: TS
Alg: UCB
Average Cumulative
800
400
200
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Alg
Alg
BBB-Alg(K=5)
Medlan Cumulative (95%)
Alg: Bayes-UCB
Alg: TS
Alg: UCB
750
500
250
500
2000
3500
5000
500
2000
3500
5000
500
2000
3500
5000
Time Step
Alg
BlB-Al
Figure Average cumulative regret and median cumulative regret with 95% percentile intervals against T = 5000 time steps comparing Alg, Alg", and BBBB-Ag for Alg E (Bayes-UCB, TS, UCB), executed on CHILD (p = 20). BBB methods were executed with no = 3200 using hybrid MCMC to estimate the structure posterior.
numerical experiments against standard MAB algorithms as well as a generously optimistic version of a recently proposed CB approach.
Although our work notably does not depend certain restrictive assumptions made by previous work, namely knowledge the causal graph or large-sample observational information, our proposed methodology nonetheless requires causally sufficient system which may not be available in practice. In the presence of unobserved confounders, an obvious challenge is that the variables in the parent sets that BBB uses for backdoor adjustmment may not. be observed. Since sets that satisfy the backdoor criterion are nol limited to the parent set, approach to this setting would be otherwise identify valid adjustment sets. Perhaps the most obvious extension of our methodology would be to model the underlying ancestral graph instead the DAG. From the ancestral graph, causal effects may be estimated from obsorvational data by identifying valid backdoor adjustment sets based its structure.
The challenge scaling BBB was addressed briefly by hybrid MCMC in Section 6 but the limits of the computational feasibility of BBB have yet to be carefully investigated precisely articulated. Preliminary investigations suggest that BBB can scale to well over 100 variables, but extended empirical evaluation necessary. A careful technical study of the posterior distributions left as future work complete the theoretical analysis of the cumulative regret. Finally, it would be interesting to consider how to share information between arms in the discrote setting as in Proposition 3 with a similarly simple graphical criterion.

---

Published in Transactions Machine Learning Research (01 /2023)
Acknowledgements
This work was supported by US NSF grant DMS-19959 1952929. This work used computational and storage services associated with the Hoffman2 Shared Cluster provided by UCLA Institute for Digital Research and Educatiion's Research Technology Group.
References
Rajeey Agrawal. Sample mean based index policies by Ollo n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27(4):1054- 10788, 1995.
0r000/r00//00333/27733333 2307/1427934
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem.
Machine learning, (7(2)2335-254 2002. http:///.d..arg//.....0022211111
Hamsa Bastani, David Simchi-Levi and Ruihao Zhu. Meta Dynamic Pricing: Transfer Learning Across
2022. Experiments. Management Science, 68(3):1865 2022. http::://dooooo//1// 1ttp//..111////// /t/m///mcc... 2021.002112221 .071
Sounya Basu, Branislav Kveton, Manzil Zaheer, and Csaba Szepesvári. No Regrets for Learning the Prior in Bandits. Advances in Nearal Information Processing Systems, 34:28029 28041, 2021. https:
//proceedings..eenee httpr//......pppo.o.oo/oo/oot/ta
Papeerr.pppppp.pfpff Paperr
Donald A Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments (Monographs on statistics and applied probabilitt)) London: Chapman and Hall, 5(71-87):7 7, 1985. Inttps:/link:
springer. cwtp://///oob/o//ooooooooooo 1007 977-994-15--311-----11---111---1
Arnoud de Kroon, Joris Mooij, and Danielle Belgrave. Causal bandits without prior knowledge using sepa- rating sets. In First Conference on Causal Learning and Reasoning, 2022. httpps://proceedings.. mlr.
press/v177/Krron222 html
Daniel Eaton and Kevin Murphy. Exact Bayesian structure learning from uncertain interventions, In Marina Meila and Xisotong Shen (eds.), Proceedinggs of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pp. 107-114, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR https:///proceedings.. mmr. wtw...ppreeeeeeeeeten///// htmll
Nir Friedman and Daphne Koller. Being Bayesian About Network Structure. A Bayesian Approach to Structure Discovery in Bayesian Networks. Machine learning, 50(1):95 125, 2003. htttaa//dol: org/10.
100244991295
Paolo Giudici and Robert Castelo. Improving Markov Chain Monte Carlo Model Search for Data Mining, Machine learning, 50(1):127-155 2003. https://doi. http::///oooor//11// 0023/0: 1020202028934
Kristjan Greenewald, Dmittry Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, En- ric Boix Adsera, and Guy Bresler. Sample Efficient Active Learning of Causal Trees. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'AchhéBBc,, E. Fox, and R. Garnett (eds.), Advances in Neural Infor- mation Processing Systems, volume 32. Curran Associates, Inc., 2019. https://proceeddng/ www.eeddiinnnn.nnssssseeee pdf
cc/paper/2019/
Dominique MA Haughton. On the Choice of a Model Fit Data from an Exponential Family. The Annals of Statistics, pp. 342 355, 1988. https://www. jstor org/ at///b/211/222244
David Heckerman, Dan Geiger, and David M Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20(3)1197-243, 1995. https://doi.org//1
BF00994016
Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical Bayesian Bandits.
In International Conference on Artificial Intelligence and Statistics, pp. 7724-7741 PMLR, 2022. https:
//proceedings.nbt mlr. wttpe/ednnn........rr//////////a ppress/v151/hong2220 html
Markus Kalisch and Peter Bühlmann. Estimating High- Dinechiimmsiin Directed Acyelic Graphs with the PC- Algorithm. Journal of Machine Learning Research, ((22):613-68) 016-636,36666631 2007. http://jmlr httl://rrrrorrr/lr//r/eee patg////prs//////////
kalisch07a. html
18

---

Published in Transactions on Machine Learning Research (01 /2023)
Emilic Kaufmann, Olivier Cappe, and Aurelien Garivier. On Bayesian Upper Confidence Bounds for Bandit Problems. In Neil D. Lawrence and Mark Girolami (eds.), Proceedings of the Fifteenth International Con- ference on Artificial Intellignce and Stafistics, volume 22 of Proceedings of Machine Learning Rescarch, pp. 592 600, La Palma, Canary Islands, 21 23 Apr 2012. PMIR. /22/kaufmann12 2tml
https://proceecdings mml.iinngmmm..m.mm.mmmmmm..m.mm. wtt.://aam.....r.aaaapea
Jack Kuipers and Giusi Moffa. Partition MCMC for Inference on Acyelic Digraphs. Journal of the American Stalisticul Association, 112(517):282-225))) 2017. https://doi. org/10. 101111111000001115...0 21116621159..11.....1111 2015. 2011..1334266666
Jack Kuipers, Polina Suter, and Giusi Moffa. Efficient Sampling and Structure Learning of Bayesian Net- works. Journal of Computational and Graphical Statisties, 0(0):1 12, 2022. https://doi.orge: www.ro.../.. 1080/
10618600 2021. 2020127
Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari. Meta-Thompae Sampling. In International Conference on Machine Learning, pp- 5884-5893. PMLR, 2021. https://proocesdings..a mlr. wrapa/eeeee//3///eeetoo2222...
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rulcs. Advances in Applied Mathematics, 6(1):4 22, 1985. ISSN 0196-8858. httppee//aaol.oorg//...000///// (000)/0000000888888808000088088
Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal Bandits: Learning Good Interventions via Cansal Inference. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advonces in Newral Information Processing Systems, volume 29. Curran Associates, Inc., 2016. https://proocediing. Paper. pdf
neurips.
Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? In S. Bengio, H. Wal- lach, H. Larochelle, K. Grauman, N. Oesa-Bianchi, and R. Garnett (eds.), Advances in Neural Informa- tion Processing Systems, volume 31. Curran Associates, Inc., 2018. htttps:/pproceeding neurips. cc/
.dff
Xiuyuan Lu and Benjamin Van Roy. Information-Thooree Confidence Bounds for Reinforcement Learn- ing. Advances in Neural Information Processing Systems, 32, 2019. https://proceeednng" www.iis...e.rrr....c.co pdf
Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret Analysis of Bandit Problems with Causal Background Knowledge. In Jonas Peters and David Sontag (eds.), Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAT), volume 124 of Proceedings of Machine Learning Research, pp. 141-150. PMLR, 03 06 Aug 2020. httpps://proceedings mlr wwwps//vve////////eeee hntm
Yangyi Lu, Amirhosscin Meisami, and Ambuj Tewari. Causal Bandits with Unknown Graph Structure. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Newral Information Processing Systems, volume 34, pp. 24817 24828. Curran Associates, Inc., 2021. https: .pdf
7/proceedings
Marloes H. Maathuis, Markus Kalisch, and Peter Bühlmann. Estimating dineedimensional intervention effects from observational data. The Annals of Statistics, 37(6A):3133 - 3164, 2009. httpss///dii.ow org/ 10. 1256/09-
David Madigan, Jeremy York, and Denis Allard. Bayesian Graphical Models for Discrete Data. International Statisticol Review / Revue Internationale de Statistique, (322):115-232, 1995. ISSN 03067734, 17515823.
http:://ww.jjstrr/ http:://ww..sttrrroor///aaaaa//p org.sstable/1403615.
Aurghya Maiti, Vincet Nair, and Gaurav Sinha. Causal Bandits on General Graphs. Xrxi preprint arXiv:210700277 2021. https: www.ooggg.....o...ooo httgg//b//110.... .07772.
Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and Non-Budgeted Causal Bandits. In Arindam Banerjec and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference Artificial Intel- ligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2017-2025. PMLR, 13-15 15 Apr 2021. https://procceednngs mlr. http:/iiinn...l..eess/ss///om///
html
19

---

Published in Transactions Machine Learning Research (012))
Judea Pearl. Causal diagrams for empirical rescarch. Biometrika, 82(4):669-66) 688, 12 1995. ISSN 0006-3444.
http://bt...rg111.10100/// we.met//....... 469
Judea Pearl. Causality. Cambridge University Press, 2000.
Amit Peleg, Naama Pearl, and Ron Meir.
Metalearning Linear Bandits by Prior Update. In International Conference on Artificial Intelligence and Statistics, pp. 2885 2926. PMLR, 2022. httpe://prooceedings
mlr. htt..ppres//vl//plegg2aa... html
Johan Ponsar, Topi Talvitie, Antti Hyttinen, and Mikko Koivisto. A Bayesian Approach for Estimating
Causal Effects from Observational Data. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04).5395-5442, Apr. 2020, attps://ojss aaai orgg
org/index. index. phtp://A/article///aaaaea
Robert W Robinson. Counting unlabeled acyelic digraphs. In Charles H. C. Little (ed.), Combinatorial Mathemalics V. pp. 28 43. Springer, Berlin, Heidelberg, 1977. ISBN 978-3-540-37020-8. https://doi.
org/10. 2T0/10.1007/1 100.10000//BB009777 BF/00691700
Daniel Russo and Benjamin Van Roy. Learning to Optimize via Posterior Sampling. Mathematics of Oper- ations Research, 122111223) 2014. https: org/ 10. 1287/ 2014.0014.
Gideon Schwarz. Estimating the Dimension of Model. The Annals of Statistics, 6(2):461 164, 1978. ISSN 00905364. ottpp:://doi.orr/100 121111/////////////4133366
Marco Scutari. Learning Bayesian Networks with the bulearn R Package. Journal of Statistical Soflware, 35 (3):1 2010. /ttp::///bb.orrg/101166////
Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy; Daniel J Hsu, Thodoris Lykouris, Miro Dudik, and Robert E Schapire. Bayesian decision-making under misspecified priors with applications to meta-learning. Advances in Neural Information Processing Systems, 34:26382 26394, 2021. https: pdf David J Spiegelhalter. Learning in probabilistic expert systems. Boyesian statistics, 4:447-465, 1992.
ipproceedings.neurrteeee httpp///p///01//////aaaaa////100
Peter Spirtes and Clark Glymour. An Algorithm for Fast Recovery of Sparse Causal Graphs. Social Science Computer Review, 9(1):62 72, 1991.
Polina Suter, Jack Kuipers, Giusi Moffa, and Niko Beerenwinkel. Bayesian structure learning and sampling of Bayesian networks with the R package BiDAG. arXiv preprint S15:::205500488 2021. https://
arxiv. wwtp////////...//0//00
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, second edition, 2018
William I Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-22)) 294, 12 1933. ISSN 0006-3444. https:///oi.ozg 10. 1093/biomet/25.3 2-8.2885)
Runzhe Wan, Lin Ge, and Rui Song. Metadata-basod Multi-Task Bandits with Bayesian Hicrarchical Mod- els. Advances in Newral Information Processing Systems, 34:29655 29668, 2021. https://proceeddngg. pdf
neurips
Hao Wang. Banstraint-Based Learning of Interventionnal Markoe Equivalence Classes on Hige-Dimensional
Data. Phl) thesis, UCL.A, 2022.
Akihiro Yabe, Daisuke Hatano, Hanna Sumila, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, and Ken- ichi Kawarabayashi. Causal Bandits with Propagating Inference. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5512-5520. PMLR, 10-15 Jul 2018. httpps://rooceedingss press/v80/yabe115 html.
20

---

Published in Transactions Machine Learning Research (01 /2023)
A Proofs and Discussions
Proof of Proposition Let T. = [1 : az = a} be the time steps in which a is selected. Then by
inequality (10 Assumption and the concavity of VT, we have
1)]
Σ ElU.(() Mal S oolog
Σ TET.
Ino + nall 111 + c2v du Σ
c1
exp
1ETa
Now the first summation on the right side
Re Pa)1-1
Σ TT
Ino + no 1)] 1)]-
Σ (no -
(o)
x -z = 2(V 1) + (T) vno 1).
mg-1
Similar derivation shows that the second summation
Sa 1)
Σ
exp
Ca.
TET.
where Ca is constant. Therefore,
Σ ElUa(t) Mal s 201 c 1) + (T(T) vno - 1) + c2ca Vo VlogT. RE
By Kauchy-Schwarte inequality,
Σ Vino +) (T) V K(no -1 -() Σ. E.nnTTT) 1/2 aEA
VKT K2 - 1).
Summing actions, we arrive at
Σ E(Ua(t) - Ma]= Σ EtU,(t) Pa]
TEALET.
< c1 (V KT K2 1) / K2 1)) + Σ Vola VlogT.
(17)
a
where ea 200, and Cs 002 max. Ca.
Next, we show that the second term in implics
9 is bounded. By the definition of U.(f) in Assumption 2
P( >
E [P Ua-(1) Dlt f)) s ca(t 1)-
for t 2, and thus,
8 Σ P(uo- > Ua. 5 11 03
Σ b-
Therefore, the second term bounded by constant cg. Accordingly, follows from
17
Discussion of Assumption 1 and Assumption 2 We now demonstrate how to verify Assumption and
Assumption 2 for Proposition 1 over possible parent set. Z, Pa. C X(a)-
Recall that the posterior distribution p(p, D(t)) defined via averaging

---

Published in Transactions Machine Learning Research (01 (203))
We start with decomposing Var(ua D(t)) by conditioning on Zo:
Var(uo D(f) E [Var(ua Za, D(t) Pit]] + Var [E(ua Za, D(f) Dit]]-
(18)
Using the Gaussian setting an example, under the conjugale prior (15). the conditional posterior plpa Za, D(1] is a t-distribution with (no + (t( - |Zal) degrees of freedom and variance
V.d (Za)
Var(Ho Za. D(1))
ni + ma())"
where (Z)) Op1 depends on D(d. Now the first term on the right side of is expressed as
(Zo)
E [Var((Me Z. D(t)) D[d]]
Σ
P(Zo D(4).
(19)
no + (a(
Za
Taking further expectation average over D[1], we gel.
I o
E [ar(uu Z., D(t)) D[t)]
}
E
v. Σ Z..
(Z.))
D(t))
(20)
no (t)
no na (1)
where of is an upper bound for the expectation the second step for all a A.
Let (Z.) = E (p4a Z., D(1) and 9 be the true causal DAG. Then,
Var (2,(
D[j]]
Σ
pi(Zaa 1 (Pa P(Za D(()
Z.zPa (6)
(Z,) (Pa 1² P(Zn. # Pa D(f))
max
I -0 P(Zz f Pag. D(1)):
where the last inequality is due to the assumption that Ma E [-C, CJ for all a. Based on asymptotic approxi- mation (Schwarz 1978 Haughton 1988), the posterior probability P(Z.. D(t)) = (x. (t)) for any Zn Paly when (t) is large, where 8(Z.) > 0 is a constant depending on Z. Let de be the number of candidate parent sets for Xaa and & min foinff((..))) Z, f Pa Taking expectation, arrive at
E (aa (Z.) D(t) } di exp( (t),,,(tt)),
(21)
for some positive constant C2. Combining
20 and 21 leads to Assumption I
Put Z. = Zu- and na- (1) = n. (t). To verify Assumption 2 we make use of concentration of the conditional posterior distribution p(u" Z. D(f)) and concentration E (n* Z., D(t)). Define two events,
11" Ely Z. D(D)
E,
Vlogt
/ E Varlr Z. ((4) D[4]
2
E(n" Z., D(() 13(1") (D()) Vlogt
E,p
Var [B(+* Z., D(t)) D[t]
By 18
Varl DD(1) 2 E [Var("" [[4) D[]] and Var(p" (DI4) 2 Var [E("" z., D(()) D[(]] Then,
we have
p 1rt E(p² D(t)
> ov ooog Did < P(E.1 (D!) P( D(4).
Var(u" (D[[]
22

---

Published in Transactions Machine Learning Research (01 /2033)
For the first probability, we further condition on Z.:
P( D(4)
Σ
P(E,, Z., P(A) (D())-
Z.
According to 19 for fixed D(t), Var(u" Then for some constant c(Z.) > 0,
Z., Dit)) = (Var(u" Z(iD(t) D((]) = (tt)
P Z., D(t)) S P Fr Bly Z., D(()) Var((u Z. D(t])
c(Z.) v logt Z., Z., D(t)
Upper bounds for right side can be established based on concentration of many commin posterior distributions. For the Gaussian setting, n² Z., D(t] follows a t distribution with (no + (t) - |Z.l) degrees of freedom. Existing concentration inequality for distribution with degrees of freedom, such as
P([4] 2 2) & cexp( 1aap(-22110 /2/4) + exp(-r/16)
in Lemma 18 of Wang 2002).. can be used to show that P(E,1 Z., D(t) = O(t-²) for some b and every candidate Z. and therefore P(E,, D(1)) 0 for any Dit).
Note that E(p" Z., D(4) = n (Z.) is function of Z, conditioning on D[4 and thus discrete and bounded
random variable. The second probability
P(E,2 D(t)) P (Z.) E( (Z.) VVa [M', (Z.) D[t]] 2 looot D(t)
D(())
may be shown to be O(t-b) by existing concentration incquality of a discrete bounded random variable and the concentration of [z. D(fj] on the true parent set.
Proof of Proposition Let. Z be the parent set of X. Then by special case of
ply do(x)) / ply 1 (z2)((z)dz
=f óly the + z, 0. )²) 0, 0,Ez)dz
øly paa, Σzy o²).
where Φ(: |1, E) is the probability density function of N(4, E) and Ez is the covariance matrix of Z. Thus,
Y do = x) ~ N(var, 7 V>y + o²).
Now representing [Y] X, Z] by a linear regression:
Y -= +
where E N((0,02) 1Z N(O, Ez). Then we have
Varp xx- Varply 7 Z+
= = Eny 0² Varp do(X =)).
Proof of Proposition 3 The result follows straightforwardly from a simple graphical argument. Let =0 denote the distinct directed paths from to Y in the causal graph G given the model [3] where & E
23

---

Published in Transactions Machine Learning Research (01 (203))
consists of all the directed edges - E on the given path from X to Y. Then the causal effect of X on Y can be expressed the sum of propagated direct effects along all directed paths from X to Y:
0 Erly do(X = 2)] = Σ IIA, Sg.
x = dr
&E itEE
We denote the variables under the intervention do(W w), E IR as X, with resulting causal model
Xy Bay X, EEj, j=1.....
where
0
w x
Bg
Beg
otherwise,
Ej otherwise.
The corresponding causal graph for X is the mutilated graph resulting from deleting all edges into W. The causal effect of X on Y is then
xxy dr
Eply do(8 =x]== dr EplY do(X x). do(W w)l
Σ EE
II A.g.
T-JEE
Since W does not block any directed path from X to Y, the mutilated graph & retains all the directed paths from X to Y in G, so Exr = x By the same reasoning, B.g Big for all i - j E & where E x Therefore, for any w IR,
0 E do(X z)]
a EplY do = 2), do(W w)]
Dx
Oz
B Experimental Details
In this section, we include details regarding the experiments discussed Section 6
For our random network simulations, we generated CBN models for p 10 variables with reward variable Y = Xp- In order to investigate interesting structures with diverse non-trivial confounding relationships, we randomly generated graph structures using the following process adapted from de Kroon al. (2022). Given fixed topological sort of the variables Xi < ... Xp where the reward variable is Y -xp we soquentially considered nodes in reverse topological order: i = 1,..., We uniformly sampled the maximum out-degree of X,, denoted d,, from to p- Then, for d, times, we randomly selected X, from (X, E X X; < Xj), adding X; + X, to the graph only if the edge was not already present and [Pa < 3. We imposed an additional requirement that PPa = 3, randomly adding parents if necessary. the generated structure consisted multiple disconnected components, we rejected the structure and reattempted the process.
The conditional probability distributions of each CEN were likewise generated randomly. For discrete net- works, the variables were all assumed to be binary, and the conditional probability tables were randomly generated uniformly and normalized, and were accepted only if for every edge X, + X; there is a suffi- ciently large causal effect, with [P[X, = x; do(X, = -,)]- P(X, = xx)l 2 0.05 for some x; E Dom (X,) required the marginal probability of any single discrete level to be at least 0.01, and that the reward signal of the optimal intervention a" be sufficiently large with respect to the observational mean: μ² E|Y] 2 0.05. For Gaussian networks, according to the model expressed [3 sampled coefficients uniformly from [-1, 0055 U (0.5, I] for X, E Pay and standard deviations from
and Hy E DX,, Additionally,
VO.55 I]. and we normalized the system to have unit variance. Note that in the Gaussian setting, there
24

---

Published in Transactions on Machine Learning Research (01 (203))
effectively [A] actions given that interventional data on the same variable may be combined as discussed in Section 5.2 which we implement for the competing methods as well. We found that (a") E Pay held for 98% of the discrote models that we randomly generated, though only for 65% of the random Gaussian models. As discussed in Section 6 we artificially enforced (a*) E pay when evaluating the regret of TS* and (Bayes))UCB*
The randomly generated networks were limited to size p = 10 in the interest of extending the scope of our empirical investigation in other aspects, namely in representing a large number of random causal models and exccuting cnough repetitions and time steps to rcasonably assess the expected performance. We emphasize that this limitation is primarily due the breadth of simulation study, whereas in practical applications there may not be the need for tens of thousands of executions.
The in-degree restriction of Paa S for all j E V was largely due to the difficulty reliably generating random conditional probabilily distributions that have meaningful causal effects and reward signals, as defined in the previous paragraph, for denser discrete networks. In general, it is not uncommon to assume the underlying DAG structure is sparse (Kalisch & Bühlmann, 2007). Similarly, the choice of [Pağ = 3 was motivated by our interest in investigating non- non-trivial structures that have substantive connectivity between the reward variable and the intervened variables. Note that without sufficiently meaningful connectivity and causal effects, our BBB methodology is actually advantaged in that the interventional distributions generally will not be substantively dilferent. than the observational distribution, thus nullifying the need for backdoor adjustmennt and correspondingly causal structure learning.
For
the best quantile constant in 8 was 0, in agreement with the empirical recommen-
dation by Kaufmann et al. (2012). The best exploration parameter for UCB in ( was c = 1/(2/2) for UCB(") in the discrete setting. In the Gaussian setting, UCB and UCB" preferred respectively, the latter of which we applied for BBB. We used standard uninformative priors for TS(*). with an Bu for the Beta prior and mo = 0, 1/- 1, and Ue = Vo = 1 for the N-r-1 prior. For BBB, we computed exact parent set probabilitics (4) using the program implementing the efficient algorithm developed by and applicd in Pensar ct al. (2020), restricting the maximum size of parent sets to three and using the Bayesian Dirichlet equivalent uniform and Bayesian Gaussian equivalent scores. For the Gaussian sctting, we checked the graphical critcrion in Proposition 3 according to (16) with T T 0.1.
1/2 and c= 1/v2,
While we focused in Section on designing the marginal posteriors according to (3), a notable difference between our proposed Bayesian CB framework and the Bayesian MAB approach described in Section 2 is that in our design, the posterior distribution is not modular, with the marginals (Ta) mutually dependent on the distribution of graph structures. However, because of software limitations and for simplicity, we sampled the criterion (t) for each arm independently in the implementation of BBB-TS in our random network experiments (line 7 in Algorithm Ip. Although preliminary results have shown the difference in empirical performance to be negligible, more precise implementation would first sample DAG g from the posterior distribution P(g] | D(I) and subsequently for each arm a E A, sample (a( from of "a/Paf,"" which we apply using MCMC in our scaling experiments.
For our investigation of scaling BBB with MCMC, we used the same generated random networks as previously described for Figure 4 For the CHILD network, we coerced all variables to binary variables, with the extrancous discrete states removed by sequentially merging states with least marginal probability. We averaged the conditional probability distributions imposed by merged states weighted according to their marginal probabilitics.
Order MCMC was implemented by extending the BIDAG package {Suter et al. 2021 to accommodate computing scores with ensemble data as described in [Section 3) For each iteration of BBB, the structure posterior was estimated by conducting 10 iterations with a thinning interval of 10 and discarding the first 20% burn-in steps. The resulting set of DAGs were used for Bayesian model averaging in BBB- (Bayes- JUBB and for BBB-TS one random DAG was selected. For hybrid MCMC, the search space was initially gently restricted by executing the PC algorithm (Spirtes & Glymour 1991 with a relatively large threshold 0.1 and only investigating conditioning sets of up to size one. For subsequent iterations, the scarch space
Pensar
2020 provided their code under the MTT License at
25

---

Published in Transactions Machine Learning Research (01 /2023)
Alg: Bayes-UCB
Alg: TS
Alg: UCB
800
Discrete Cumulative
400
200
Alg: Bayes-UCB
Alg: TS
Alg: UCB
Gaussian Cumulative
750
500
250
500
2000
3600
5000
500
2000
3500
5000
500
2000
3500
5000
Time Step
Alg
Alg
(BB-Alg(k-O) - BBB-Alg(K-3) -
BBB-Alg(k-S)
Figure 6: Median cumulative regret with 95% percentile error bars for time steps t {500, 2000,3500, 5000} comparing Alg, Alg", and BBB-Alg for Alg E [Bayes-UCB, TS, UCB3. BBB methods were executed with no 100 2 the discrete setting and no 10 2 the Gaussian setting.
was restricted to edges that appear with at least 0.05 probability in the structure posterior estimated in the preceding iteration. Note that the hybrid approach proposed by Kuipers et al. (2022) includes provisions for extending the search space for greater robustness in the presence of false negatives, so with each iteration the scarch space may be sequentially reduced or expanded as the structure posterior is increasingly informed by interventional data.
C Additional Results
Due the density of information communicated in figures such Figuree along with the substantial variability arising from the randomness in graph structures, conditional probability distributions, and data, we chose not to include error bounds of the empirical variability. To visualize the variability in the empirical results, provide median cunulative regret with 95% percentile crror bars in Figure 6
Furthermore, in what follows we present the results from additional experiments designed to evaluate firstly our proposed approximation of the sampling variance of the discrete backdoor adjustment estimator 12 and
26

---

Published in Transactions on Machine Learning Research (01/2023)
secondly the application of Proposition 3 by way of Gaussian backdoor adjustment with jointly interventional and observational data.
c.1 Discrete Backdoor Adjustment and Variance
In this section, we describe and present experiments evaluating the behavior of Pa,hda where Z = Pa (a) as in (12), as well our proposed approximation of its variance, derived in detail in Appendix D Four variance estimation methods were investigated. In the naive approach, Aa, (Z) is treated as a conditional proportion as is the case when |Z] = 0, and the variance estimated as Pd, -aa,-da [ n(zz is the number of samples of data where Xaa Za. The sampling approach estimates the variance from samples from the population ion distribution, and the bootstrap approach conducts resampling from each sample distribution, each with 10 repetitions.
where
The generation of discrete CBNs for the simulation scenarios was designed as follows. The graph structure was generated simply by initializing a structure where there is a direct odge from the intervened node aa to the reward variable Y and X tay has jZ] m parents. For each parent X, E Z, an edge X3 + Y was randomly added with 0.5 probability to create backdoor paths. Finally, conditional probability tables were generated uniformly as described in Section 6
For observational sample sizes no E {100- 2 : 0,,,., 5, and parent set sizes |Z| E 1,,,,,,3) 10a scenarios were created by randomly generating CBNs as described above and the methods were assessed under each scenario through the following process. First, 10 datasets were generated, each with no samples of obscrvational data, and for cach dataset, bd, was computed for some arbitrary Ta E (o:).. Then, for each of the four methods, the variance was estimated corresponding to the first 10 estimates of Pa,bda and from those the 2 standard deviation interval coverage probability of the true Ha was computed.
The estimator Pa, (Z) itself was found to be generally unbiased, with the average of the 10 estimates deviating from the true Ma by less than 2% in over 99% of the 24,000 scenarios. The coverage probability results are shown in Figure 7 where each boxplot visualizes the coverage probability of a mothod across 10a scenarios randomly generated under the given simulation setting. The outliers and invalid values, which typically corresponded to extreme scenarios, were removed. The naive approach is only correct when |Z| = 0 and performs poorly when otherwise. The general results may be summarized as Naive < Bootstrap Proposed < Sampling, though our proposed estimator appears to oulperform the bootstrap approach for larger [Z] and perform comparably with the population sampling approach for larger while requiring significantly less and nearly negligible computational expense compared to cither.
C.2 Gaussian Backdoor Adjustment with Ensemble Data
In this section, empirically validate our methodology of conducting the regression (14 with jointly interventional and observational data to estimate vias, as discussed in (Section 5.2) In particular, we compare the coverage probability of (da) where Z = Pal, estimated using purely observational data and ensemble data. The ensemble data was generated by allowing each data sample be generated by one of the possible interventions {do(X, = xz) Xj E Z, 2. E [-1,1]] or by passive observation, with equal probability given to each of the 2/7] + options.
For sample sizes E {10-2* l/ 0. 1, .,....5) 5) and parent set sizes |Z| E 21, 3), 10 scenarios were created by randomly generating CBNs. The network structures were generated as described in Appendix C.I. and the parameters in Seccion 6. Each data generation method was evaluated for each scenario by generating 10" datasets with n samples and estimating bda (Z) and SÉ 2 [8 (Z)) for each dataset by conducting the regression [4 From those estimates, 95% confidence interval coverage probabilities were computed for
each scenario.
The average of the 10S estimates of he (Z) deviated from the true Pia by at most 0.9% across all 24,000 simulation scenarios for both data generation methods. The coverage probability results are shown in Figure 8) Since the results did not vary across parent sot sizes, cach boxplot visualizes the coverage probability of a method across the 4, 000 simulation scenarios at each sample size. It is easy equivalent.
27

---

Published in Transactions Machine Learning Research (01 /2023)
100
100
100
100
1.00
0.95
0.90
0.85
200
200
200
200
0
1
2
3
1.00
0.95
0.90
0.85
400
400
400
400
0
1
2
3
1.00
Coverage per Scenario
0.95
0.90
0.85
800
800
800
800
1.00
0.95
0.90
0.85
1600
1600
1600
1600
2
1.00
0.95
0.90
0.86
3200
3200
3200
3200
0
1
2
3
1.00
0.95
0.90
0.85
Estimator
Naive
Bootstrap
Proposed
Sampling
Figure 7: Coverage probability per scenario using various estimators VarlAn, (Z) across no -100-2*;
h: 0. 1, ......5) 5) samples of observational data and |Z| E {0, 1. adjustanent set sizes.
28

---

Published in Transactions Machine Learning Research (01 /2023)
Coverage per Scenario
0.948
0.952
10
20
80
160
320
Sample Size
Observational
Ensemble
Figure Coverage probability per simulation sccnario across sample sizes for observational and ensemble data generating methods.
performance of the estimator computed with ensemble data compared to observational data, with consistent coverage across all sample sizes.
Derivation of the Discrete Backdoor Adjustment Variance Approximation
In this section, we derive the approximation of the sampling variance
12
nal 1, Fa. z)molz)
Pa. bdu (Z)
1i0 Σ
nT z]
For the entirety of this section, assume that the expectations and variances are with respect to the discrete probability distribution P defined by a fixed CBN B.
D.1 Introduction
For simplicity, we redefine some notation. The backdoor adjustment to estimate the interventional distribu- tion of Y do(X = z) with parent set Z = Pa with r parent configurations is given by:
P|Y do(x x)] Σ P(Y= x x, P) = 2).
Empirically, given samples of observational data, this quantity is estimated using counts:
n/y, 2, n/z)
nly, z/n(z]
p[y do z)]
(22)
n|x,
where n(y,2, x, z] represents the number of samples which Y y. x, and Z 2, with corresponding definitions for ve[r, z] and nzx]]. The joint probability distribution of X, Y. and Z may be lumped into a multinomial random vector N NN, ,,.,,,,,,,,, N,',N," E 3 where for = I....,r,
N₂ nly.2, 2,). N n1-0, N n.)

---

Published in Transactions Machine Learning Research (01 /2023)
Note that N; + N2' + +N rlz,], so Ei= (Nr N2' +N") n. so N may be thought of as repartitioning of the joint probability distribution of X, Y, and Z into 3r disjoint levels:
N (Ni, N1, N1" NY, ,,",,, Multinom(n, p);
p = (pi,Pi', ..... Pr.Pr's Pr.PP''po ,p'"p'')) ",",,
where
(23)
n M. x. Zi
E n| y. I. 2,
ps" = n u. zil
P E
for i I,....r.
72
The advantage of such a representation is so that for each ū,, the term within the summation may be expressed function of three disjoint elements of multinomial random vector:
nly, x. 2i/n/2d
nly, 2. 2,l (nly. 2, + nl. vo| WE, 2il)
n Zil
mly, + n,,
(24)
N.NN + NY + N
Note that each term is not straightforward to compute. An obvious challenge is that the denominator of each term in the summation in (24 can be zero, so there is no analytical solution for its mean, variance, and covariance.
D.2 Taylor Series Expansion for Ratio Distribution
To circumvent this challenge, approximate the ratio in 24 with the Taylor series approximation. We begin by defining
M. = NNN, + N + N.
n
W. = N
n
M.
Q. f(M,, W.)
W
This allows us to express the variance of 24 in terms of Qi:
r
Var [PlY 1 do(x 2)] Var
Σ
Qi
i=1
(25)
Σ Var (Qrl +
Σ
Σ
Cov QQ, Q,)
i=1 jzl
By Taylor series expansion around = (UM..-W.)) = [E]M],E[[[l)..
Q S(M, W³)
= f(w) + (M: (M.) Of
(m:) + (W; - pw.) 0f
ow; (m))
9M;
1 (M: )ma.) 8
f
(44)
(W: mw:)) aw? (ms)
(26)
2
0M7
82
+ (M. -MM, (MM) NW, - (ww)
aM.OW. (1,)
O (II,, W.) -m1l))
30

---

Published in Transactions Machine Learning Research (01 (203))
where
0f
8.
(M, W.)
(M,, W.) = 0,
0M;
W,"
OM?
0f
M,
8
2M, W
(M, W:)
(M, W:)
(27)
ow;
W
Ow?
0 f aM,ow; (M, W.)
f
(M,, W.)
OW,OM,
W?
Given 26
obtain approximate expected value:
1 S (14. [ar
ØJ Var
82 aM,OW, (ox)Cov[[M, Wi].
F[QU & f(1) + 2 aM?
(28)
aw?
For variance and covariance,
simpler approximation:
0f
Of
Q. = ((M,,W)) R f(w)) + (M; - mMM,)
(1.) + (W; lww,)
OW. (14),
(29)
0M,
resulting in
0M, (1:) (4z)) Var[M:] + af
0f
Var[Q.] ~
ow, (14) (ar)
(30)
+ 2 05 (14) 0f
Cor Wi).
0M, aw.
and
E(QQR) R= f(m)f(())
+ 0s 0s (1, Cov M,]+
0s (n,) 05 Cov)
(1x)
0M, OM,
aM, oW,
0f (m,) af
0f aw; (mx) 0f aw, Cor) W,).
Cor Myl
ow; aM,
80
Cov [Q: Q,1 (112@21-E(Q.JE 0f
(mi) 0f aM, OM, 0f (14) of Cov),,, My + of (1s) of ow,
(w, Cor Myl + 0f (m)) 0f aM, aw, (or Ws] (31)
Cov) W,].
aw; aM,
ow;
what follows, we first derive important quantities from the multinomial distribution in Appendix D.3 and apply them to compute the quantities in (5)
D.3 Multinomial Derivations
For this subsection, in an abuse of notation, let N (N,,..,, N.) Multinom (n. p) and u, u,u,w,a (I....,r) are inst values. It is well-known that E[N,] nPu, Var[Nu] rep -Pw), and Cov(Na, No) -pp.Po. Furthermore,
N,N,N.J = Cov(Ner N.J + E[N.] =n(n 1)puPes
(32)

---

Published in Transactions Machine Learning Research /2023)
and the first four moments from derivating the moment generating function are:
[[M.] repu,
E[M.] v(n 1)p + E.N.]
rpp-[1 (n 1)pul,
E|NM] n(n 1)((1 2)p². - 2
(33)
(n 1)p.. + ()))p,
E[MC] ntnn 1)(n 2) [(n 3)p 3p:] + 2n(n 1) [(n - 2)p2 + 200] + E[NN)]
rpp + 17 + (n - 2)p. + (n 3)pp))
Define indicator random variable U. such that U. if the outcome for trial is fl,...,r) r) and Us = 0 otherwise. Similarly define Vi for o Wi for w o o u, and X; for f & o u. Then Nu. No. Nu and N may expressed as
n
No Σ U
No
V4, N Σ Wi.
N₂ Σ
X
We are interested in N N[N N.),, N.N.N.N E[N and N,N,NN
Σ vi ]
EIN E.
Σ U1
by distributing
B
by linearity of expectation since U.V: 0 for all i= I....,
BLU.UVVA
by independence between trials
&ULCMEMM + ΣΣΣΣ E RTU.U,IIIA
E[C.USJE[VA]]
reexpressed
BUJ ΣΣΣΣ
reexpressed; independence; and
ΣΣΣ
since E(U.U,] E|U.EE[U,] i i
light
back
cotk 196
= n(n - 1)pup. n(n 1)(n - 2) 3)pppt
since E(U?) = E = Pa.
n(n 1)(n 2) n(n () 2)påp.
=n(n - 1)pup [1 + (n 2)(pu + pe + (n 3)puPe)]
simplified.
Hence,
E[N n2nn 1)PxPo [1 (n 2)(,, P + (n 3)puPr)].
(34)

---

Published in Transactions Machine Learning Research (01 /2023)
Following the same derivation strategy.
B[ n(n 1)PuPo (n 2)pa(3 + (n 3)pu)l.
(35)
E NNN n(n 1)(n P)p.p.Pw. [] + (n 3)pul,
(36)
NNNNN N. = n 1)(n 2) PoWssoPuPs.
(37)
N[ 11 1)pPP [1 + (n - 2)pul:
(38)
E|N,NN n(n 1)(n 2)p.poPw.
(39)
D.4 Numerator and Denominator of Ratio
We turn to the lask of deriving expressions for Var[M,], Var[Wi], and Cov[M, Wi] in order to compute
30 and additionally for Cov[M, Mj]. Cov[M, W,l. Cov Myl, and Cov[W; Wy] for 431. For this subsection, return the notation for expressed [23
The distribution of W; - + N,¹) is most simple. By the lumping property of multinomial random vectors,
E[W]] ps Pb', Var[W.] (p, p. P:')( -p; p:d)
(40)
(pt (ps + pz¹)
Cov(W, Wy]
n
The distribution of M, n N,, N2 Ny") is more challenging. From 33 is given by:
and
the expectation
E[M] = n "EN, + N2' + +(")
= n (E[N B[N.N]] E[N,N(])
(41)
(mpill + (n 1) n(n 1) D)pp'' n(n - 1)p.p,") ") -p (n - 1) + p.' p(")).
Nexl, the variance is given by:
[ar[M,] = n V.. N + +N,")]
= n =a= + N.N,' + N,N,")
= n =>=((Var[N3) + Var [N,NN, - Var[N,N/"]
+ +2Cov(N7, N.N:J 2Cov|N?, N,N,"" 2Cov N,N,1)).
The terms in the expression above are given below. From the moments of the multinomial distribution 13
Var[ E E[N np: (n 1)p,(7 (n 2)p, (n 3)p,)) (mp, 1)p.))² np; [ 1 (n 1)p:(7 + (n 2)p. 6 (n 3)p:)) mp, (1+ (n- 1)
From 34
and
32
Var[N,N.1] -
n(n 1)p.p. [1 + (n 2)(p: + p. (n -3pppp ') [n(n 1)ppp' n(n 1)p.P: [1 (n 2) + + (n 3)p.P(') / - n(n D)p..''s Var[N.N,"] n(n 1)p.P:" [1 2)(p: p." + (n 3)psp;") -r(n 1)p:P:"
33

---

Published in Transactions Machine Learning Research (01 (013))
From 35
33
and
32
N.N - B[N
nnn - 1)pppp''s [] + (n 23, + (n 3)p:3l
-np:[1 (n (n-)))// - 1)pip'
n 1)ppps' [] (n (3pp + (n 1-3p(t) rep + (n 1)p:)]
Nor[N,,NN, nn 1)p.p." [1+ (n 2)(pp + (n 3)p²) npp(1 +11++ (n -1)p;)]
From 36
and 32
Cov(N.N N,N."
nn 1) 2)p:p''p'"' (n - 3)pd - nnn 1)p:pt' Dpp""
= n(n 1)por ps 1(m - 2)(1 + (n - -3)p:] n(n 1)pil.
Hence, Var[M]]] is derived:
[ar[M]] = n 7r-1tppp
(np, [1 + (n ( (1- (n-3pp.) np: (n }
n(n 1)p.pt'[1 (I 2)(p, + p. (n 3)p;p:') n(n 1)p:p''1
+ n(n 1)p:p;"[1 "p 2)(p: + p:" - (n (n- 3)p(pt") - n(n 1)ppp"" "1
(42)
+ 2n(n - 1)p:pa' [1+ - 22)3pp; + (n - 3)p?) - np:(1 + (n 1)p:)]
+ 2n(n - 1)p.p," " [1+ (n -2)(3p) (n 3)p²) -p.(1 + (n-
- 1)p:)]
+ n(n 1)p:p' pp"" [[ [[n-]]] + (n 3)pd n(n 1)pt)) )-
Next, consider Cov(M. My].
Cov[Mr, Mj] *Cov
(N. + N.", NJ'+N,")]
*Cov N2 + N,N;' N,N, N3 + N,N,' + N5,N,"
-n "Coo(C"" NN31
[N,, NNJNy'1 + CovIN N, CoN(NVNN, N31 + Cov(NN,G,,,N' Cov[NN,V N,,N Cov NNN N,N,,1 Cov N,JN, Co N,N,")
The terms in the expression above are given below. From 34
and
33
Cov -
= =n(n= 1)p [1 + 2 + + (n 3)p:p;)]
l)p,] = -pppp/((n (1) ()))) + + (n --)pp))
- - (n (1 (m-
-n(1 + (n 1)p,) (n 1)p,)].
From 36
33
and
32
Cov[NV N,N,1 EIN2N,,111
r2(n - 1)(n - 200--2)ppspp/1111111 + (n 3)pil 1p:pppp11+ (1p[[++(0 1)p.)((n 1)psp,''
nan 1)p-,,//[(m222))
(n (1n-3)p 3)p,
m(1 (n 1)pt)l,
Cov[NV, NyNN ra(n 11)mp5p5"" 2)--2][1 (n 3)p: =n(1 + (n 1)p:]l.
No NN. n2nn 1)p,PEP [(n-2)] (0]) (n-3)p,) -n(1 (n 1)p;)],
N,, NN) = 1)),P<p ((n 2)[1 + (n 3)2, -n(1 + (n 1),;)]

---

Published in Transactions Machine Learning Research (01 (203))
From 37
and
122
LONNNN,,,N, E.N.N.,,NVJ
= rn(1 1)(n - 2) 3)p - n(n 1)ppP n(n 1)ppp'
rn(n D)pppip,,pp/' 2)(n 3) -n(n 1)]
Cov[N,N NYNg"" = mnn 1)ppi'p,,)"" [(m 2)(n -3) 3) n(n 1)]
Cov[N,Ni NyN, = m(n D)pp PyPj '(m 2)(n 3) n(n
Cov(NNNV" N = nnn 1)pp, PbP, " [[n 2)(n - -3) - n 1)
Hence, Cov(Ms M3] is derived:
Cov M, My]
(mpaps
(1-
-[1=<(0-1p)01+00-10000 n1 + (n 1)p:)l
+ n1 1)p,,,p; (0n-)2((++nm))))) (n-3)p.
+ n(n 1)pppp; [[]] +n=-3pp m11 [n 1)p;)]
2]]]
+ n1nn 1)pppaps ((m [[n-2]] + (n -m-33pp 3)p,] m(1 + (n 1)p;)]
+ n(n 1)p;p.p," " [mm-2][1 (n 3)p,] m(1 (n 1)ps)]
+ n1(1 ))pp''',p [(n 2)(n - 3) n 1)]
(43)
+ n(n 1)p:pi'p,p3 " [(n 2)(n 3) n(n - 1)]
+ nn 1)p.p:" p,p) [(n 2)(n 3) - -n(n 1)]
+ n(n 1)ppp:" pyp)" " [(m-2)( -3) - -m(n 1)])
= n
(n ppp,
1) + +1; 33):)p)
+
2][1 (n 3)p; - n(1 + (n 1)p:)] + pppp(p++'p''\('>
+ (n- - (m33)p, - n1 + (n - 1)p))]
+ (p. (p:'+""")) ((o""+""""""" 2)(n 3) - n(n - 1)])
- n11 + (n - (1 1]p,]
Finally, we turn attention to Cov(M, Wi], Cov Wj), and Cov (W., M,). Beginning with Cov[Me W.J:
CovlMr, Wi] n *Cov [N.(N. + N'' + N,"", N₁ + N:]
n ~Covv [N, + N,N,'' + N,N;", N; - N²'l n (Cov(N? Ni. + [ov N;T +Cov[N,N; Ni] + Cov Cov[NNN/ NY1 Cov[N,N,", Cov[NNN,",
The terms in the expression above are given below. From
CoviN?, E[N - E[N
= np; [1 + (n - 13 + (n 2)p.)] | npp(1 + (n 1)p/(pp.
npp; [1 + (n - ()p: 2)p.) -np,(1 + (n 1)p,)]
= np, [1+p((n - 1)(3 2p.] - n)]
From 38
and 33
Cov CoviN? N.1 = -
= =n(n - -n(n-1)).p (n - 2)pp] mp:(1 + (n - 1)p,)mp,
(44)
= (nn (n 2)ps) n11 + (n 1)p;)].

---

Published in Transactions Machine Learning Research (01 (203))
From
18
and
33
Cov(N, Mi. =
n2n 1)p.p,'[1 (n 2)pil -n(n 1)p:Ps 'rep:
= nnn - 1)p,ps'P [[1 2p:].
N NN1 n(n 1)ps'p/l 2p:'l.
[ov[N,N " Ni] n(n2 1)p.P. "[1 2prl-
From
39
32
and 13
Cov|N,N NO. E[N,N, N "IENN""
T(n - 1)(n 2)p "p." - n(n 1)p.p. np,
(45)
-2n(n 1)pppt"p"
Hence, Cov[Ms, Wi] derived:
Cov[M, W.] = =n n= (mp:: pr
2p,] mn]
+ +np.p: (on-p-l((nn(CCC))) 1)(1+ (n 22)p:) n11 + -1)p:]
+ +n( - 1)p.P:/ - 1 2p:]
+ nnnn 1)p''p.(1 2pr
+ +n(n 1)pp,""1 2pd
(46)
2n(n 1)p:p:"p." "p.".
p. + p((n 1)(3 2p:] - n))
+ P [(n 1)(1 + (n 2)p,) n2 + (n - 1)p;)])
+ n (m 1)(p,, 2p, - 2p, p.P. - 2p. - -2p,')-
Then, moving on to Cov(M, W,] and Cov[W,,
Cov(M, Wg] = n CCov [N + N/' + N,",, N2 + N3y
= n "Cov [N? + N.N' + N.N,", N2 + N
n (Cov|NN, N,] Cov|N?, Ny'l
+ Cov[N,N', N2)]
No No,(N,N",,,,))
The terms in the expression above are given below. From
44
Cov Cov[N?,N] N2) np:p (nn 1)(1 (n 2)p:) nl1 (n 1)p(),
Cov NN,, N5' np:P5' [[n 1) (n 2)p;) n01 (nz 1)p:)]
From 45
Cov[N,N; N2] = 2n(n 1ppp''s Pj:
Cov[NeN N₁² 2n((n 11pP''P p3'
Cov " .2)] = -2n(m 1)p Pj-
Cov(N,N.". N5' 2n 1ppPp""p""
Hence, Cov[M W3] and Cov(W,, My] are derived:
Cov[M, W,] =
1pp(11 [) - 1)(1 (n- 2)p:) - + (n - 1)pd)l
- 2n - (p + + ",""" +p','')
+
= =n 2 p3 ) 1)(1 (n (m- 2(p + (r + +
(47)
n11 (n- 11):))
Cov(W,, M,] = n 3 (p: ; p4') (m))((-1)(( 1)(1 (n 2)p; 2(p + p. "','))p + p())
-n(1 (n - 1)p;)/
36

---

Published in Transactions Machine Learning Research (01 (2033)
Thus, all quantities necessary to compute (25 are derived.
37


Reviews:
[{"review_id": "jhF2VP3xlX", "reviewer": "Reviewer_PzMw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This study demonstrates a naive but powerful and natural approach to the causal bandit problem. Bayesian algorithms or algorithms motivated by Bayesian ideas can naturally incorporate prior information into algorithms. Among practitioners, employing Bayesian methods for incorporating prior knowledge is a well-known idea. Therefore, I believe that the main contribution lies in the confirmation of the effectiveness of this approach in the causal bandit problem. The proposed framework is innovative and intriguing because such algorithms have not been officially proposed in spite of their usefulness. \n\nAlthough the proposed framework has some novelty, the lack of theoretical analysis makes this study’s evaluation difficult. To investigate the optimality of algorithms, it is preferable to show the lower and upper bounds for the proposed algorithms. For example, we can employ information-theoretic lower bounds of Lai and Robbins (1985) or lower bounds for an asymptotic Bayes evaluation to show the asymptotic optimality (Lai, 1987). If the authors consider a Bayesian evaluation instead of a frequentest evaluation, they might obtain Bays optimal algorithm by solving dynamic programming under appropriate settings on time horizon and discount rates, such as Gittins index (Gittins, 1989).\n\n\nMy main questions are listed as follows:\n- Definitions of some notations, such as $E$, $\\mathrm{Var}$, and $\\hat{\\mathrm{SE}}$ are desirable, although we can guess the meanings. \n- On p.3, is $E[R_T] = T\\mu^* 0 \\sum_{a\\in\\mathcal{A}}$ is an expectation under posterior parameters? Similarly, is $\\mu_a$ an expectation under a fixed parameter, and $E_{\\pi^0_{a|\\bm{Z}}}[\\mu_a]$ is an expectation marginalized over the posterior distribution? For example, Kaufmann et al. (2012) denotes the cumulative regret by $R_n(\\theta) = \\mathbb{E}_\\theta[\\sum^n_{t=1}\\mu^* - \\mu_{I_t}]$ on Eq. (1) in their paper. \n- What is $\\hat{P}$ on (9). Is it a posterior probability given observations?\n- Should $\\mathrm{Var}(Y|dp(X=x))$ be denoted by $\\mathrm{Var}(Y|dp(X=x), \\pi^t_a)$ because it is the variance under a fixed parameter?\n- Can the authors show the posterior convergence and consistency for some important parameters such as $\\mu_a$ given the data generating process, even if they cannot show the optimality of their algorithms?\n- In Appendix D.2, for $Q_i = f(M_i, W_i)$ the authors apply series expansion around $\\mu_i = (\\mu_{M_i}, \\mu_{W_i})$. In Eq. (18), the authors omit the higher-order term of the second-order series expansion, but briefly writing them may be helpful for readers. Furthermore, I think that the higher-order term can be ignored only when the sample is infinite. Can the authors justify the use of approximation when the sample size is small?\n\n1. Gittins, J. C. (1989): Multi-armed Bandit Allocation Indices. Wiley, Chichester, NY.\n2. Lai, T., and H. Robbins (1985): “Asymptotically efficient adaptive allocation rules,” Advances in Applied Mathematics.\n3. Lai, T. L. (1987): “Adaptive Treatment Allocation and the Multi-Armed Bandit Problem,” The Annals of Statistics, 15(3), 1091 – 1114.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study presents Bayes-flavored algorithms for the Causal bandit problem with frequent evaluation. As causal bandits require the knowledge of causal graphs, most existing studies develop their own algorithms given the information. In this context, the authors' methods incorporate the information as prior information of Bayes-flavored algorithms. Motivated by this, the authors develop several algorithms utilizing the properties of Bayesian algorithms. Furthermore, the author also simulation studies to demonstrate the superiority of the proposed method over existing methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I agree that the proposed framework of this study is practically useful and insightful in that it allows us to incorporate prior information into algorithms. However, (i) there are no theoretical results such as optimality and posterior convergence, and (ii) the notations are a bit hard to read, or the definitions (formulations) may have some issues. Because of these concerns, I believe that the formulation and theoretical analysis need to be further improved in order for this paper to be accepted.\n", "broader_impact_concerns": "The proposed algorithms are easy to apply and implement. They are also helpful for practitioners.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UlTdvUhG0p", "reviewer": "Reviewer_Veix", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- The assumptions of the proposed method is kind of weak, which makes it is closer to the application settings. Prior works mostly rely on known causal graphs, or the underlying causal graph is restrictive. This paper gets rid of them by taking a Bayesian perspective, however, it might worth to discussing that if we want to have some theoretical results for BBB, are the limited causal graph class is required?\n\n- Most part of the paper is pretty well-written and easy to read. The methods and their instantiations are well-illustrated.\n\n- The empirical section, though is based on synthetic data, shows some interesting observation, i.e., the larger sample size of observational data might even hurt the performance when the time step is longer. Is this also the case for other baseline algorithms?\n\nWeakness:\n\n- The main concern of the proposed method is the high computation cost in computing the parent set probabilities and the conditional parameter posteriors, which might limit its use and impact. Though the author discusses some approximation through MCMC might be possible for BBB-TS, it would be great to give a try and illustrate the robustness of the proposed method under the approximation setting. \n\n- I would suggest the paper to dig into more investigations into either the theoretical or empirical side of the proposed method. For the current version of the paper, the regret analysis of the BBB framework is missing, and it would be great to understand more how it compared with the baselines theoretically. For the empirical side, it would be great to have some real-world datasets to illustrate the proposed BBB framework. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the causal bandits from the Bayesian perspective. Compared with prior works, it does not assume the known causal graph or some requirements in the causal graph class. Instead, it takes a Bayesian perspective by constructing the prior using observational data and updated the posterior using the interventional data. To achieve this, this paper design a new framework: Bayesian Backdoor Bandit (BBB) that simultaneously learns the causal graph and utilizing the causal inference to optimize the reward. To instantiate this idea, the paper discusses the implementations on both the discrete and gaussian setting. Empirically, it also shows superior performance over baseline algorithms, such as TS, UCB in small scale experiments.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- It would be great to have the approximated version of BBB-TS, to showcase the more applicable version and how the approximation affects the overall performance.\n\n- As pointed out above, it would be great to either have a regret analysis for the BBB framework, under either discrete or continuous setting; or it might be helpful to test the methods in more real-world datasets, or large scale datasets (apparently, the computational complexity might affects the feasibility of doing this).\n\n- Section 3 is a little bit hard to follow, could we organize them utilizing paragraphs that suggest the main points? \n\n- In the empirical section, it would be great to give a more detailed description on the structure setup from de Kroon et al. (2022). ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "px8nb1f5zo", "reviewer": "Reviewer_rebg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe problem definition in terms of introducing observational and interventional data as a prior into the multi-armed bandit framework appears novel, to the best of my knowledge.\n\nThe paper is well-written and defines the problem clearly. \n\nWeaknesses:\n\nThe terminology if 'backdoor adjustment prior' is not commonplace, and relatively unexplained.\n\nWhat is the quantitative difference between observational and interventional data? This is not well-defined, and therefore the intuition behind eqn. (1) is absent.\n\nSimilarly, interventional calculus is a term that is thrown around, but its meaning is not widely understood. Therefore, it should be more rigorously defined in the context of the introduction of the Bayesian prior.\n\nTo evaluate the backdoor adjustment prior in eqn. (3), we need access to the probabilities P(Pa_a = Z | D[t] ) which are associated with the DAG defining the causal structure. How reasonable is this assumption? Some practical instances when it is known, or not known, should be detailed. \n\nA key weakness of this work is that there appears to be no regret bound analysis that establishes the performance of the proposed approach, and contrasts its theoretical rates with UCB or Thompson sampling without such knowledge of the casual DAG. Therefore, a rigorous understanding of when and why this approach outperforms some prior baselines is not very clear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work develops the multi-armed bandit setting for the case that both observational and interventional data are available, and a directed acyclic graph relating them is available in the form of a prior that relates the causal structure of the problem. With this information in hand, a maximum a posteriori update rule for these probabilities is developed, and its uses in a way that can be incorporated as a prior into upper-confidence bound and Thompson sampling, is developed. Experimental analysis illuminates the merits of the proposed approach. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In the discussion of limitations of assuming knowledge of the causal graph in prior work during Section 1.1, the authors should provide an illustrative example where this assumption breaks, so as to make clear that these conditions are in fact limiting. Moreover, the following paragraph discusses various efforts to relax this assumption and the limitations of those efforts as well; however, without specific technical reasons that their conditions are restrictive in the context of some problem in particular, the argument that these conditions are limiting comes across as hollow. Why is the estimation of interventional quantities from observational data more practical? is it because then the bandit algorithm does not depend on unverifiable assumptions? How are the conditions imposed by this approach weaker than the aforementioned ones? \n\nIn the summary of contributions, the authors should provide a more quantitative description of the main regret bound in the discrete, especially how it refines previous results' dependence on the prior, and how that prior exhibits specific dependence on the observational data which facilitates theoretical and potentially practical improvements. For the continuous space with Gaussian model, how does the proposed framework improve dependence on the prior, and what specific improvements are achieved through the use of interventional calculus? As written, these aspects are ambiguous.\n\nIn Section 3, it is mentioned that the class of priors is easier to evaluate when submodularity is present, due to the super-exponential growth with the dimension of the variables. However, is this referring to the dimension of the feature space or the action space? Moreover, which classes of priors actually satisfy this condition? How restrictive is it, and what are some practical examples? \n\nThe legend in Figures 1-2 seems incorrect. I think the red should refer to Bayes-UCB, and the green should refer to UCB, and the dotted to the backdoor adjustment prior variant. If it is correct, then it is ambiguous. Please correct the legend. What does Alg mean? I think the authors mean to contrast the performance of Thompson sampling/UCB with and without a backdoor adjustment prior. \n\nReferences missing regarding the link between bandit algorithms and experimental design:\n\nKrause, A., Singh, A., & Guestrin, C. (2008). Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2).\n\nBedi, A. S., Peddireddy, D., Aggarwal, V., & Koppel, A. (2020, July). Efficient large-scale gaussian process bandits by believing only informative actions. In Learning for Dynamics and Control (pp. 924-934). PMLR.\n\nThe authors should expend more effort to illuminate how the proposed backdoor adjustment prior improves dependencies on naive implementations of UCB or Thompson sampling for the proposed setting. \n\nThe analysis that gives rise to Proposition 1-2 does not appear novel in my reading. What is specifically different about these proofs as compared with the references from whence they came, and is there any attribute of the MAB setting or DAG structure associated with the causal inteventional setting that necessitates such a departure?\n\nThere are long run-on mathematical experiments in the appendices that no reader should be expected to parse. See equation (35) for an exmaple. These expressions should be broken up, and only each term that actually gets manipulated should be restated. One does not need to carry all the terms to explain what is going on. ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ad0nxLnWBq", "reviewer": "Reviewer_E6Uy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The presented work is solid, with the following strengths:\n\n- The main contribution of this work is being able to bypass the restrictive assumption of knowing the true causal graph. In contrast to previous work by Lu et al. (2021), this work focuses on the non-asymptotic observational data regime: i.e., it does not rely on the large-sample observational setting of (Greenewald et al., 2019).\n\n- The work is very clearly presented, with succinct arguments about this work's contributions (section 1.2) that contrast with related alternatives (section 1.1), before delving into necessary preliminaries (section 2) to design informative (causal-graph based) priors in Section 3 needed for their proposed Bayesian Backdoor Algorithms of Section 4.\n\n- Section 5 contains details on how to compute mean and variance estimates for BBB's implementation for two specific use-cases.\n\n- The authors empirically demonstrate how BBB compares to standard algorithms that assume knowledge of the causal structure. Importantly, they showcase that BBB outperforms all non-causal counterparts (with performance monotonically improving with more observational data) and that it achieves lower cumulative regret than the optimistic central node counterparts with enough observational data.\n\nSome weaknesses of the presented work are:\n\n- The increased computational cost of the proposed BBB algorithm (that requires computation of parent posteriors in Equation 4). Details on this computational overhead are not provided or discussed.\n\n- BBB is a combination of existing techniques, i.e., the proposed method's significance is on merging them together.\n\n- The work, which relies on informative priors and estimates learned from prior observational data, lacks a theoretical analysis on how such data impacts regret performance (this tradeoff is illustrated empirically). The authors leave the theoretical analysis as future work.\n\n- The work assumes all variables in the graph are observed. A discussion on whether confounding could be accommodated via techniques from the causal inference literature would be of interest. \n\n- BBB is instantiated for 2 specific models: a discrete bandit setting and a (linear) Gaussian Unit Deviation Setting. Details on the significance of the Gaussian unit-deviation setting, and a discussion on the challenges of other causal models would strengthen the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work addresses causal bandits ---a multi-armed bandit setting where observable variables are modeled with a causal graph defining their conditional dependencies--- where the agent leverages the underlying causal relationships to more efficiently optimize its attained rewards.\n\nThe authors study causal bandits where data is observed as generated by the causal model, prior to the bandit agent playing (intervening on) any arms. Due to the dependencies inherent in the causal model, interventional distributions (i.e., those of the bandit's actions) may be inferred from observational distributions. Hence, information may be shared between arms for efficient exploration-exploitation strategies.\n\nIn contrast to existing work that assumes knowledge of the underlying causal graph, this work relaxes such assumption and combines causal graph learning with causal bandit interventions to devise a Bayesian bandit policy.\n\nThe proposed bandit algorithm computes inferences based on both observational (i.e., available prior to the bandit actions) and interventional (i.e., resulting from the agent's actions) data to simultaneously ($i$) learn about the underlying causal graph, and ($ii$) optimize the bandit's cumulative rewards, by exploiting causal inferences.\n\nThe proposed framework, named Bayesian Backdoor Bandit (BBB), quantifies the uncertainty in the expected reward estimates of the bandit agent by accounting for the reward signal and the unknown causal model, merging the following techniques:\n\n1. Bayesian bandit policies, such as Bayes-UCB and Thompson sampling;\n2. intervention calculus and the back-door formula, for estimating interventional quantities from observational data; and\n3. Bayesian model averaging, to compute causal estimates that average over posterior distributions of plausible graphs, based on a technique proposed by Pensar et al. (2020).\n\nSpecifically, BBB implements a Bayesian bandit policy (Bayes-UCB or TS) with priors designed based on information from observational data (computed via the backdoor adjustment formula): the priors are initialized with expected value and variance estimates as presented in Equation (2). This prior is then sequentially updated to corresponding posteriors as the bandit plays (intervenes) on different arms.\n\nBecause the backdoor adjustment formula requires knowledge of the parents of a variable ---assumption not made by the authors here--- these estimates are computed by averaging over the posterior distribution of the plausible causal models, as indicated in Equations (3) and (4).\n\nBBB leverages this carefully designed prior to execute Bayesian policies, where the posterior mean and variance statistics are updated as interventions are made, via averages over the posterior of the parent set distribution of Equation (4); i.e., the proposed Bayesian posterior incorporates uncertainties about both the reward function and the plausible causal graphs.\n\nKey to the proposed BBB algorithm are the definition of the priors' mean and variance estimates, which the authors detail for two specific causal bandit applications: the discrete, multinomial bandit and the linear, Gaussian unit deviation setting. The derivation of the variance estimates for these two applications is the focus of Section 5 (with proofs provided in the Appendix), where approximations to these quantities of interest are provided. Given the proposed estimates' approximate nature, the authors focus on providing empirical evidence of the correctness and validity of these approximations, e.g., demonstrating coverage in Appendix Section C. \n\nThe work concludes with an evaluation section where the performance of BBB is compared to alternatives closest to this work (as per the discussion in Section 1.1) in a variety of simulated causal bandits. Results show that \n1. BBB outperforms all non-causal counterpart policies, with performance monotonically improving with more observational data.\n2. BBB achieves lower cumulative regret than the optimistic central node counterpart with enough (yet not excessive) observational data: $n_0 \\geq 800$ in the discrete setting, $n_0 \\geq 40$ in the Gaussian setting.\n\nIn addition, the authors showcase BBB's graph structure learning capabilities, describing the algorithm's performance tradeoff between the size of the observational data $n_0$ and the graph learning accuracy. With small observational data, initial uncertainty in both the structure prior and the reward encourages exploration of all arms, incurring in greater cumulative regret but allowing for identification of connections beyond the reward's parents; i.e., better graph recovery is possible than when BBB is initialized with bigger datasets ---where reduced initial uncertainty enables quick identification of the good arms, and thus small regret, yet the lack of exploration of other arms hinges learning the orientation of their edges.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. For completeness, and to help a reader not familiar with causal graph inference techniques, details on the following should be incorporated:\n    1. Describing the algorithm developed by Pensar et al. (2020), which is used here to compute the parent set probabilities in Equation (4). This would facilitate reproducibility of BBB.\n    2. Describing in detail the \"standard assumptions of global and local parameter independence and parameter modularity\" mentioned in Section 3.\n    3. $\\hat{SE}$ appears in Equation (2) without being previously defined. Given its importance ---the focus of Section 5 is on approximating it--- the authors should define it before its first appearance. \n\n2. Evaluation section:\n    1. Results are presented for bandits with $p=10$ variables and 3 parents for the reward variable. The authors should clarify the motivation behind these choices; e.g., are these numbers used due to computational constraints imposed by Pensar's posterior computation algorithm? In addition, the work would be strengthen with results showing how sensitive BBBs performance is to these choices. \n    2. Empirical analysis/evidence showcasing the extra computational complexity of BBB is missing: how expensive is to compute parent set posteriors and averages over them?\n    3. The provided figures, given that they are averages over realizations, should include error-bars illustrating performance variability. \n\n3. The authors acknowledge that in this work, $X$ is a causally sufficient system with no unobserved confounders. A discussion on the challenges unobserved confounders raise, and how to leverage tools from the causal inference literature to mitigate or accommodate them would complement and strengthen this work.\n", "broader_impact_concerns": "This work does not discuss broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a Bayesian variant of causal bandits. The advantage of the Bayesian framework is that the causal graph does not have to be specified in advance and is learned on the go by maintaining its posterior. The authors evaluate their approach empirically and also derive a preliminary regret bound.

The initial version of this paper was already solid. In the rebuttal period, the authors comprehensively addressed the comments of the reviewers. They also went beyond the original writeup in two major ways:

* A preliminary regret analysis. The initial writeup had none.

* An approximate MCMC implementation of the algorithm. This is one major strength of the Bayesian view, that many approximations (although not with regret guarantees) exist.

I suggest acceptance of this paper **AS IS**, with the understanding that the authors expand related work (Section 1.1) to discuss Bayesian bandits better. There are many recent works that show algorithmic and regret improvements due to a better prior. Here are some pointers to consider:

* Modern Bayesian analyses of TS and Bayes-UCB (precursor to showing improvements due to the prior) started in [Learning to Optimize via Posterior Sampling](https://pubsonline.informs.org/doi/abs/10.1287/moor.2014.0650).

* An actual improvement is shown in [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://proceedings.neurips.cc/paper/2019/hash/411ae1bf081d1674ca6091f8c59a266f-Abstract.html). A tighter MAB analysis, which is also easier to follow, is in Lemma 4 of [Meta-Thompson Sampling](https://proceedings.mlr.press/v139/kveton21a.html).

* Bandit meta-learning, essentially learning the prior for TS by repeatedly solving similar bandit tasks, received a lot of attention recently:

  * [Meta Dynamic Pricing: Transfer Learning Across Experiments](https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3334629)

  * [No Regrets for Learning the Prior in Bandits](https://proceedings.neurips.cc/paper/2021/hash/ec1f764517b7ffb52057af6df18142b7-Abstract.html)

  * [Bayesian Decision-Making Under Misspecified Priors with Applications to Meta-Learning](https://proceedings.neurips.cc/paper/2021/hash/ddcbe25988981920c872c1787382f04d-Abstract.html)

  * [Metadata-Based Multi-Task Bandits with Bayesian Hierarchical Models](https://proceedings.neurips.cc/paper/2021/hash/f7cfdde9db36af8e0d9a6d123d5c385e-Abstract.html)

  * [Metalearning Linear Bandits by Prior Update](https://proceedings.mlr.press/v151/peleg22a.html)

* Fully Bayesian methods, where the prior reflects the structure of the problem, have been especially successful:

  * Posterior sampling for choosing one model out of many ([Latent Bandits Revisited](https://proceedings.neurips.cc/paper/2020/hash/9b7c8d13e4b2f08895fb7bcead930b46-Abstract.html))

  * Posterior sampling with a mixture prior ([Thompson Sampling with a Mixture Prior](https://proceedings.mlr.press/v151/hong22b.html))

  * Posterior sampling for meta-, multi-task, and federated learning ([Hierarchical Bayesian Bandits](https://proceedings.mlr.press/v151/hong22c.html))

Congratulations to acceptance!
Decision: Accept (poster)