Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits
Authors: Muhammad Qasim Elahi
Mahsa Ghasemi
Murat Kocaoglu
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal Bandits
No-regret Learning
Causal Discovery
Primary area: bandits
TL;DR: We propose a two-phase algorithm for causal bandits with unknown causal graphs: Phase one learns the subgraph on reward's ancestors to identify all possibly optimal arms, followed by a standard bandit algorithm with analysis of the cumulative regret.

Abstract: Causal knowledge about the relationships among decision variables and a reward variable in a bandit setting can accelerate the learning of an optimal decision. Current works often assume the causal graph is known, which may not always be available a priori. Motivated by this challenge, we focus on the causal bandit problem in scenarios where the underlying causal graph is unknown and may include latent confounders. While intervention on the parents of the reward node is optimal in the absence of latent confounders, this is not necessarily the case in general. Instead, one must consider a set of possibly optimal arms/interventions, each being a special subset of the ancestors of the reward node, making causal discovery beyond the parents of the reward node essential. For regret minimization, we identify that discovering the full causal structure is unnecessary; however, no existing work provides the necessary and sufficient components of the causal graph. We formally characterize the set of necessary and sufficient latent confounders one needs to detect or learn to ensure that all possibly optimal arms are identified correctly. We also propose a randomized algorithm for learning the causal graph with a limited number of samples, providing a sample complexity guarantee for any desired confidence level. In the causal bandit setup, we propose a two-stage approach. In the first stage, we learn the induced subgraph on ancestors of the reward, along with a necessary and sufficient subset of latent confounders, to construct the set of possibly optimal arms. We show that for our proposed algorithm, the number of intervention samples required to learn the set of possibly optimal arms scales polynomially with respect to the number of nodes. The second phase involves the application of a standard bandit algorithm, such as the UCB algorithm. We also establish a regret bound for our two-phase approach, which is sublinear in the number of rounds.

Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits
Muhammad Qasim Elahi Electrical and Computer Engineering
Mahsa Ghasemi
Electrical and Computer Engineering Purdue University
Purdue University el elahi 06purdue edu
mahsa @ purdue.edu
Murat Kocaoglu
Electrical and Computer Engineering
Purdue University
Rkkocaoglu@purdiee
Abstract
Causal knowledge about the relationships among decision variables and reward variable in bandit setting accelerate the learning of optimal decision. Current works often assume the causal graph is known, which may not always be available a priori. Motivated by this challenge, we focus the causal bandit problem in scenarios where the underlying causal graph is unknown and may include latent confounders. While intervention on the parents of the reward node is optimal in the absence of latent confounders, this is not necessarily the case in general. Instead, one must consider a of possibly optimal arms/interventions, each being a special subset of the ancestors of the reward node, making causal discovery beyond the parents of the reward node essential. For regret minimization, we identify that discovering the full causal structure is unnecessary; however, no existing work provides the necessary and sufficient components of the causal graph. We formally characterize the set of necessary and sufficient latent confounders one needs to detect or learn to ensure that all possibly optimal arms are identified correctly. We also propose randomized algorithm for learning the causal graph with a limited number of samples, providing a sample complexity guarantee for any desired confidence level. In the causal bandit setup, we propose two-stage approach. In the first stage, we learn the induced subgraph on ancestors the reward, along with necessary and sufficient subset of latent confounders. construct the set of possibly optimal arms. We show that for our proposed algorithm, the number of intervention samples required learn the set of possibly optimal arms scales polynomially with respect to the number of nodes. The second phase involves the application of standard bandit algorithm, such as the UCB algorithm. We also establish regret bound for our two-phase approach, which is sublinear in the number of rounds.
Introduction
Causal bandits have been topic of interest since their inception and have been studied in various contexts [ The authors assumed precise knowledge of the causal graph and the impact of in- terventions actions the parents of the reward node. Subsequently, there has been flurry of research on causal bandits 2 3 4. The primary limitation of the majority existing works on causal bandits is their assumption of full knowledge of the causal graph, which is often impractical for many
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

real-world applications [1 [5] 6]. Recently, efforts have been made to overcome this limitation. In [7]. the authors propose a sample efficient algorithm for cases where the causal graph can be represented as a directed tree or causal forest and later extend the algorithm to encompass a broader class of general chordal graphs. However, the proposed algorithm is only applicable to scenarios where the Markov equivalence class (MEC) of the causal graph is known and does not have confounders. In [8] the authors propose a causal bandit algorithm that does not require any prior knowledge of the causal structure and leverages separating sets. However, their theoretical result holds only when true separating set is known. The paper by Konobeev et al. ( also deals with causal bandits with an unknown graph and proposes two-phase approach. The first phase uses randomized parent search algorithm to learn the parents of the reward node, and the second phase employs UCB to identify the optimal intervention over the parents of the reward node. However, similar to 77 they assume causal sufficiency, i.e., no latent confounders are present. In another related paper, [10], the authors initially emphasize the challenge of dealing with exponentially many arms when addressing causal bandits with an unknown graph. To tackle this issue, the authors assume that the reward is a noisy additive function of its parents. This assumption enables them to reframe the problem as an additive combinatorial linear bandit problem.
We also focus on the causal bandit setup where the causal graph is unknown, but we allow the presence of latent confounders and make no parametric assumptions. The optimal intervention in this case is not limited to parents of the reward node; instead, we have candidate set of optimal interventions, called possibly optimal minimum intervention sets (POMISs), each being a special subset of the ancestors of the reward node [5]. Thus, learning only the parents of the reward, similar to 19), is insufficient. This implies that causal discovery beyond parents of the reward is imperative. However, for regret minimization, discovering the full causal structure is not necessary. Instead, characterize the set of necessary and sufficient latent confounders one needs to detect/learn to ensure all the possibly optimal arms are learned correctly.
Causal discovery is well-studied problem and can be applied to our setup 1|| 13 However,
the majority of the existing causal discovery algorithms rely on the availability of an infinite amount of interventional data [14 15] [6]. Some prior work shows that discovery is possible with limited interventional data, with theoretical guarantees when the underlying causal graph is tree and contains no latent confounders [17]. Also, the paper [18] proposes a sample-efficient active learning algorithm for causal graphs without latent confounders, given that the MEC for the underlying causal graph is known. Bayesian causal discovery can also be a valuable tool when interventional data is limited. However, it faces challenges when tasked with computing posterior probabilities across the combinatorial space of directed acyclic graphs (DAGs) without specific parametric assumptions 19 20 21). All in all, the sample-efficient learning of causal graphs with latent confounders, without any parametric or graphical assumptions, with theoretical guarantees, remains an open problem.
We propose a randomized algorithm for sample-efficient learning of causal graphs with confounders. We analyze the algorithm and bound the maximum number of interventional samples required to learn the causal graph with all the confounders with a given confidence level. For the causal bandit setup, we propose two-stage approach where the first step learns a subgraph of the underlying causal graph to construct set of POMISs, and the second phase learns the optimal arm among the POMISs. We show that the requirement of learning only a subgraph leads to significant savings in terms of interventional samples and consequently, regret. The main contributions of our work are as follows:
We characterize the necessary and sufficient set of latent confounders in the induced subgraph on ancestors of the reward node that we need to learn/detect in order to identify all the POMISs for a causal bandit setup when the underlying causal graph is unknown.
We propose randomized algorithm for sample-efficient learning of causal graphs with confounders, providing theoretical guarantee on the number of interventional samples required to learn the graph with given confidence level.
We propose a two-phase algorithm for causal bandits with unknown causal graphs containing confounders. The first phase involves learning the induced subgraph on reward's ancestors along with subset of latent confounders to identify all the POMISS. The next phase involves a standard bandit algorithm, e.g., upper confidence bound (UCB) algorithm. Our theoretical analysis establishes upper bound the cumulative regret of the overall algorithm.

---

2 Preliminaries and Problem Setup
We start with an overview of the causal bandit problem and other relevant background needed on causal models. Structural causal model (SCM) is a tuple . = (V, U, P(U)) where V = (Vi)== U {Y} is the set of observed variables, U is the set of independent exogenous variables, F is the set of deterministic structural equations and P(U) is the distribution for exogenous variables [22]. The equations ft map the parents (Pa(Vi)) and a subset of exogenous variables U, S U, to the value of variable Vi, i.e. Vi- = (VV,,, U.). We consider the causal bandit setup where all the observed variables V; E V are discrete with the domain (VV),) = [K] == (1,2,3, ..... ...,.. and the reward Y is binary, i.e., (YY) = 10. We can associate DAG G (V, E) with every SCM, where the vertices V correspond to the observed variables and edges E consist of directed edges V; + V, when V, Pa(V)) and bi-directed edges between V2 and V2 (V₁ < V₂z) when they share some common unobserved variable, also called latent confounder. We restrict ourselves to semi-Markovian causal models in which every unobserved variable has no parents and has exactly two children, both of which are observed [00]. An intervention on a set of variables W C V. denoted by do(W), induces iestinteeveetional DAG (Gw) with incoming edges to vertices W removed. We can broadly classify interventions into deterministic interventions, where variables are set to a fixed realization denoted by do( W w), and stochastic interventions, where instead of fixed realization we have W ~ IP()), where P is a probability measure over the domain ?(W). We denote the sub-model induced under hard intervention by -w=w and the one induced under stochastic intervention by Mw. In the context of causal bandits, an arm or action corresponds to hard intervention on a subset of variables other than the reward. The goal of the agent is to identify the intervention that maximizes the expected reward. The performance of an agent is measured in terms of cumulative regret li.
RT := T max max B[Y|do = =w]]- Σ B[Y|do(W, = =w.).. WCV WCV WE(K]]W)
where do( (W,- = =w) represents the intervention selected by the agent in round f. We use the notation Aoo(w) to define the sub-optimality gap of the corresponding arm do -w). We denote the descendants, ancestors and children of vertex V; by De(V,), An(V,) and Ch(Vi) respectively. We use the notation Bi(V, 9) to denote the set of vertices having bidirected edges to Vi except the reward node Y. We refer to the induced graph between observed variables the observable graph. The transitive closure of a graph, denoted by g encodes the ancestral relationship in G. That is, the directed edge Vi V, is included in G only when V; AV;)). The transitive reduction, denoted by Tr(g) = (V, E ), is a graph with the minimum number of edges such that the transitive closure the same as G. The connected component (c-component) of the DAG G. containing vertex Vú, is denoted by CC(V),, which is the maximal set of all vertices in G that have a path to Vi, consisting only of bi-directed edges (23. For a subset of vertices W C V, we define CC(W)= == Uw.ew CC,,... In a DAG, a subset of nodes W d d-separates two nodes V/2 and V3 when it effectively blocks all paths between them, denoted as V; MLd V Blocking a graphical criterion associated with d-separation (22]. A probability distribution is said to be faithful to graph if and only if every conditional independence (CI) statement can be inferred from d-separation statements in the graph. Faithfulness is a commonly used assumption in the existing work on causal discovery assume that the following form of the interventional faithfulness assumption holds in our setup.
[14] [4]. We
Assumption 2.1. Consider a set of nodes W V and the stochastic intervention (W, U) on W and any set U C V W. The conditional independence (CI) statement (X 11. Y Z) u holds in the induced model if and only if there a corresponding d-separation statement post-intervvettioal graph (X ITt Y Z)e w where X. Y, and Z are disjoint subsets of V \ W. The CI statements in the induced model are with respect to the post-interventional joint probability distribution.
3 Possibly Optimal Arms in Causal Bandits with Unknown Causal Graph
The optimal intervention in a causal bandit setup is not restricted the parent set of the reward node when the reward node Y is confounded with any node in its ancestors AY(Y') [5]. For instance, consider SCM X, = U, and X₂ = X, e U2 and reward Y = X2 4 U2, where U, ~ Ber(0.5) and U2 ~ (0.5). Note that X₂ and reward Y are confounded in this SCM. The optimal intervention in this case is do X1 = 1) since Eo]]do( X; = 1)] = 1. The intervention on the parent of the reward (Pa(Y)) X2) is suboptimal because E| [d 0)] E dd = 1)] = 0.5. The example
3

---

V3
V/
V3
V3
Vi
VI
V2
(a) g
(b) 91
(c) 92
(d) G3
Figure I: True Causal Graph 9 with four other graphs each with one missing bi-directed edge.
shows that it is possible to construct SCMs where optimal intervention is on ancestors of the reward node instead of parents when reward node is confounded with one of its ancestors. The authors in [5] propose a graphical criterion to enumerate the set of all possibly optimal arms, which they refer to as POMISS. We revisit some definitions and results from their work.
Definition 3.1. (Unobserved Confounder (UC))Territory(55) Consider a causal graph G(V, E) with reward node Y and let H. be G Ann(Y)) ).. A set of variables T VVH) containing Y is called an UC-territory on 9 with respect to Y if Deu (T) T and (T) =T.
A UC-territory is minimal if none of its subsets are UC-territories. A minimal UC-territory denoted by MUCT(G, Y), can be constructed by extending set of variables, starting from the reward {Y) }. alternatively updating the set with the e-component and descendants of the set until there no change.
Definition 3.2. (Interventional Border) Let T be a minimal UC-territory on G with respect to Y. Then, X (T) \T T is called an interventional border for 9 w.r.t Y denoted by IB(G, Y).
Lemma 3.1. ( For causal graph G with reward Y, [B(9 w:
is a POMIS, for any W S V (Y).
Although the graphical characterization in Lemma provides means enumerate the complete set of POMISs, it comes with exponential time complexity. The authors also propose an efficient algorithm for enumerating all POMISs in (5). However, this requires knowing the true causal graph, and without it, one has to consider interventions on all possible subsets of nodes, which are exponentially many. One naive approach to tackle the problem is to learn the full causal graph with all confounders to list all POMISs. However, a question arises: Do we need to learn/detect all possible confounders since the goal is to find POMISs and not the full graph?
Before answering the above question. we start with an example considering the causal graphs in Figure I Using Lemma 3.1 the set of POMISs for the true graph G is Ia {Ø), (Vi), [V2), (V3), (Vi 12)). However, for 91 which has the bidirected edge 1/2 <> Y missing, the set of POMISS is Ig, = (ø. (12) (V1, V2 }}. Also for G2 which has the bidirected edge V12 ++ V/2 missing, the set of POMISs is Io, = {0. [V1, [12), (V1, V23}. In both cases, we miss at least one POMIS, and since it is possible construct an SCM compatible with the true causal graph G where any arm in POMIS is optimal, if this arm is not learned, we can suffer linear regret [5. Although the graph G3 has the bidirected edge V1 <> V/ missing, it still has the same set of POMISs as the true graph, i.e.. Ig, = (Ø, [V1}. [12). [Vs]. (Vi, V2 This example shows that only subset of latent confounders affect the POMISs learned from the graph. We formally prove that it is necessary and sufficient to learn/detect all latent variables between the reward and its ancestors because missing any one of them will cause us to miss at least one of POMISs leading to linear regret for some bandit instances.
Lemma 3.2. It is necessary to learn/detect the latent confounders between reward node Y and any node X E AY(Y)) in causal graph G to learn all the POMISs correctly and hence avoid linear regret. Theorem 3.1. Consider a causal graph G E) and another causal graph g' such that they have the same vertex set and directed edges but differ in bidirected edges, with the bidirected edges in g' being a subset of the bidirected edges in G. The graphs will yield different collections of POMISs if and only if there exists some Z E AY(Y)) such that either (a) or (b) is true:
(a) There is a bi-directed edge between Z and Y in G but not in g'.
(b) Neither of the graphs g' and G have a bidirected edge between 7 and Y, and there exists bidirected edge in G between some X E &MUTT( P112, Y) and Z but not in G'.
We extend Lemma 3.2 to provide necessary and sufficient conditions in Theorem 3.1
characterizing all the latent variables that need to be learned, ensuring that the POMISs learned from sparser causal

---

graph match all those in the true causal graph. Suppose we have access to the induced observable subgraph g' on ancestors of the reward node. We can start by testing for latent confounders between Y and any node in (Y)). Then, we need to test for latent confounders between any pair Z E An ( such that Z and don't have bi-directed edge between them, and X E MUCT(OL
Pa(2).Bi(.99) Y)
new pairs to test. Theorem 3.1 can be useful because depending the underlying causal graph, it saves us the number of latent confounders we need to test. For instance, consider a causal graph that has the reward Y with different parent nodes, i.e., Pa(Y) (Vi, V2.....,VVl with no edges between the parents. In cases where every parent of Y is confounded with Y, or when none of them is confounded with Y, we only need to test for [An(Y)] latent variables, implied by Theorem 3.1 However, in the worst-case scenario, we would need to test (lAm() latent variables when the true graph only has the confounders V1 < Y and V; <> Vi+1 for all = 1,,,,, n - 1. The exact number of latents we need to test can range from [An(Y)) to (IAn(Y))=1) depending graph. One issue still remains: we need a sample-efficient algorithm to learn the induced observable graph over An(Y) and to test the presence of confounders, which is addressed in upcoming sections.
until there
the true
Finite Sample Causal Discovery Algorithm
In this section, we propose sample-efficient algorithm to learn causal graphs with latent confounders. We propose a two-phase approach. In the first phase, the algorithm learns the observable graph structure, i.e., the induced graph between observed variables. In the second phase, it detects the latent confounders. In the next section, we use the proposed discovery algorithm to construct the algorithm for causal bandits with an unknown graph. We begin by proposing two Lemmas to learn the ancestrality relations and latent confounders using interventions.
Lemma 4.1. Consider a causal graph G(V, E) and W C V. Furthermore, let X, V\ W be any two variables. Under the faithfulness Assumption 2.7 (X An(T)) if and only if for any w E [K]IM, we have P(t)do(w)) + P())do(w), do(z)) for some x, t E [K].
Lemma 4.2. Consider two variables X, and X2 such that X, & An(X,) and a set of variables (Pa(X.) U PP()), (X.)) S W and Xi, X; & W. Under the faithfulness Assumption 2.1 there
latent confounder between X; and Xj if and only if for any w E [K] | we have P(r; | do(z;), do W = w)) * P(æ; Iz, do( W = w)) for some realization Iı, Tj E [K].
These Lemmas are modified versions of Lemma in [14 and Interventional Do-see test in [4]. respectively. The difference between Lemma 4.1 and Lemma 1 in [14] is that we have an inequality test that can be used the sample-efficient discovery instead of a statistical independence test. The Interventional Do-see test in [14] is valid for adjacent nodes only; however, our Lemma 4.2 can be used to test presence of latent confounder between any pair of nodes. This is because the condition in Lemma 4.2 X, & An(X.), can always be satisfied for any pair by flipping the order when one node is an ancestor of the other. In order to provide theoretical guarantees on sampling complexity, the inequality conditions are not enough; we need to assume certain gaps similar to 7 7 17).
Assumption 4.1. Consider causal graph G(V.E) and W C V. Furthermore, let be any two variables. Then, we have (X E (n)))) if and only if for any w E [K] we have [P({)doww) P(t]do(w), do(x))) > e for some x, E [K], where >> 0 is some constant.
V W
Assumption 4.2. Consider two variables X; and X, such that X5 & An(X,) and a set of variables (Pa(X.) (a(XX) (X+)) S W and X,,X, & W. There is a latent confounder or bidirected edge between X; and X; if and only for any w E [K] [W, we have P(x; do(x;), do(W W = =w)) - P(1;) l I;, do(W = w))l > for some realization I., D. E [K] and some constant y > O.
4.1 Learning the Observable Graph
We propose Algorithm to learn the transitive closure under any arbitrary intervention do (W). denoted by G We use the Assumption 4.1 to bound the number of samples for ancestrality tests. We start with an empty graph and add edges by running ancestrality tests for all pairs of nodes in V\ W. resulting in the transitive closure gde We recall that the transitive reduction Tr(g)
E") of DAG g (V, E) unique, with E" S E, and it can be computed in polynomial time 25 Also, note that Tr(g) = Tr(gto). We propose a randomized Algorithm 2 similar to the one proposed in
w
5

---

Algorithm 1: Learn the Transitive Closure of the Causal Graph under any intervention, i.e., S
Function Learn (V, W, d2):
0, Fix some w E [X]]W] and A mar & ,fd) log 2nk2 w)
2x log 2nx2
B1
Get samples from dW W
Get A samples from every do( XX; = TG, W - w) AX E / / and Vx, E [K] for every pair Xs, X, E V W do
Use the Interventional Data to Test (X; A
if Me, E [K] s.l. ((ay) (do(w)) P(wy (dl(()))))))))) (w), do(=;))) > then E U (X,,,))
return The graph's transitive closure (V, E) and All Interventional data
10 End Function
Algorithm 2: Learn the Observable Graph
Function cearrrbbservablerrraahhhh (V, a, dmazz 81, 82): = 0 IData =
for = 1 Sa dmax (n)(n) do
W = 0
for V Vo
WUV, with probability
Zdmax
WW. Dataw =
Learn Transsttvveeeeluuree W, 62
Compute the transitive reduction Tr(gW) & add any missing edges from Tr(g
IData = IData U Dataw (Keep Saving Interventional Data)
10
return The observable graph structure (V, E) and interventional data samples IData
End Function
14 that repeatedly uses Algorithm [ to learn the observable graph structure. The motivation behind the randomized Algorithm is Lemma 5 from [4). which states that for any edge (X,, X,,). consider a of variables W such that {W; :::::<WWW (W;) > (X,) & W; E Pa(X,)) C W where is any total order that is consistent with the partial order implied by the DAG, i.e., x (X) < (YY iff X E Ann)).. In this case, the edge (X,,x) X,) will be present in the graph Tr(w)). Algorithm 2 randomly selects W, computes the transitive reduction of the post-interventional graphs, and finally accumulates all edges found in the transitive reduction across iterations. Algorithm 2 must be greater than or equal to the highest graph degree for our theoretical guarantees to hold.
takes a parameter dmax, which
Lemma 4.3. Suppose that the Assumption 4.1 holds and we have access to max (.
7,2 log 2K2 81
8 samples do(X; = Iig W = -w) E K and 2² log 2K
62 samples from do( W = -w)for a fixed E [K] and W V. Then, with probability least 1 1- 81 82, we have (X₃ E An(X,)) if P(a, do(w), do(x:))) -
and only if T. E [K] s.4. |P(zr do(w))
Lemma 4.3 provides the sample complexity for rumning ancestrality tests. Algorithm selects a realization w [K] |W| takes samples from the intervention do (o(W- = w). and samples from every do = Tii W = w) for all X; E V W and a; [K] interventions. Thus, in the worst case, Algorithm [ requires K'An- + samples learn the true transitive elosure with high probability.
We formally prove this result in the Lemma 4.4
Lemma 4.4. Algorithm learns the true transitive closure under any intervention, i.e., Gte. with probability at least 1 nd= 82 with maximum K.An + B interventional samples. we we set 51 2n and 82 5 then Algorithm learns true transitive closure with probability least 6.
Algorithm Seportthm@repeaan reppatedlyy invokes Algorithm to learn Tr(Gw) for randomly sampled W. Through this iterative process, accumulates edges across iterations, ultimately constructing the observable graph structure. To establish the sampling complexity guarantee for Algorithm 2 we leverage the result from Lemma 4.4 The Theorem 4. gives the sampling complexity for learning the true observable graph with high probability.

---

Theorem 4.1. Algorithm
2 learns the true observable graph with probability at least Saxdmax (ng + 02) with 8odmaz log n K An + B) interventional samples. If we set or 2dmaz log +2) 61 32rddmue n. log and 82 32cddmux logn' then Algorithm
learns the true 2nk2 & observable graph with probability least of 1 8. (We have A max 2 log 61
log
B 2 log 2nk²
as in line 2 of Algorithm 82
4.2 Learning the Latent Confounders
Assumption can be used test for latents between any pair of observed variables. Note that while using Algorithm@) 2 we save and return all the interventional data samples. These samples can be reused detect latent confounders in the next phase. For any variables X, and X; such that X, & An(X,). we need access to interventional samples do(W ww such that (Pa(X:) Xx) U
(x:)) S W and X; & X; E W. the supplementary material, we demonstrate that randomly selecting the target set W in Algorithm ensures that we have access to all such datasets for all pairs of observed variables with high probability. In addition to simple causal effects we need to estimate the conditional causal effect of the form P(zz) [2;, do(w W w)). To bound the number of samples required to ensure accurate estimation of the conditional causal effects, we rely on Assumption 4.3 Note that Assumption 4.3 does not restrict the applicability of our algorithm; it simply assumes that under an intervention do W = w). either the probability of observing a realization X; = z; is zero or is nower-bounder by
2
constant 1) >> O. The role of this assumption is bound the number of interventional samples required for accurate estimation the conditional causal effects.
Assumption 4.3. For any variable X; E V and any infervention do W = w) where W C V and
w E [K] [I, we assume that either P(æ:Ido( W = w) = or ((x; do W = w)) 2 7 >
Algorithm 3: Learn the Causal Graph along-with with the Latent Confounders
Function LearnCausal Graph (a, dmazz 51, 62, 63. 64):
G.IData LearmbbservableGrrphho dinax; 51, 62)
C= 18 log( 2n² + 2n7 log( 2n?x² = & log 2nk? n.?
6g
04
o2
for every pair X,, X, do
If X, E An(X;), swap them. Find interventional data sets do(W- W w) and do(X; Hı, W w) from Daata s.t. (Pa(X.) PP(X)) \ (X.)) S W and X; & X, & W
Get max C B) new samples for do(W w)
ir xis xy E [K] s.f. P(xy dd((x)) do(w)) ((ss(=;
then
Add bi-directed edge X; + X, to graph g
10
return The Causal Graph with Latent Confounders g
End Function
Lemma 4.5. Consider two nodes X; and X3 s.t. X, An(X;) and suppose that Assumptions
or samples from do(X, = Ii, W = =) Va; E [K] and 16 my log( 2K + 2n log( 2K samples from do(W = for fixed w E [K] [ W and X; & X, & W. Then, with probability at least 1- 81 8g 84. we have a latent confounder between X, and X, iff 24, Zy e
2.1 4.2 hold and we have access to max( f., -2) log 2K
and W V such that (Pa(X,) U Pa(X,) (X,))
[K] s.t. P(xx]do((;)) do(w)) (xx do(w)) | 3.
Lemma 4.5 establishes the sample complexity for detecting the presence of latent confounders for any pair of nodes in the causal graph. Using results from Theorem 4.1 and Lemma 4.5] we bound the number of interventions required by the proposed Algorithm 3 to learn the causal graph along with the latent confounders. Theorem 4.2 provides the sample complexity guarantee for Algorithm to learn the true causal graph, including all latent confounders, with given confidence level. An important feature of the sampling complexity result Theorem 4.2 is that the number of intervention samples needed to learn the causal graph scales polynomially with the number of nodes
7

---

Theorem 4.2. Algorithm 3 learns the true causal graph with latents with probability at least
1
Sadmar (n)(n(nn) + (Ó2 + 83 d4]) with a maximum of 8addmas log An
n Aimma
max (B, interventional samples. If we set a = 2dmax log +++
64ndmazn log and 82
log
d3 64 bladmas logn' then Algorithm 3 learns the true causal graph with probability at least
1-6. 8. (A and B are given by line 2 of Algorithm and C given by line of Algorithm 3
Suppose the constant gaps and 7 in Assumptions 4. and 4.2 are close; then, we have C C>> A1A2
B. The value of the constant 0 < 1) < is usually small in practical scenarios, so the quantity C' is much greater than both B or A. This implies that the number of samples required to test the presence of latent variables is greater than that required to learn ancestral relations. This is because accurately estimate conditional causal effects to detect latent variables, which requires a large number of samples compared to simple causal effects. Theorem 3.1 is useful here because it shows that do not need to test for confounders between all pairs of nodes among ancestors of the reward node to learn the POMIS set.
need to
Algorithm for Causal Bandits with Unknown Graph Structure
Algorithm 4 is the sketch of our algorithm for causal bandits with unknown graph structure. The detailed algorithm with all steps explained is given in the supplementary material (Algorithm (6). Algorithm first learns the transitive closure of the graph G to find ancestors of the reward node Y. This is because POMISs are only subsets of AY) The next step is to learn the observed graph structure among the reward Y and nodes in An(Y). Instead of detecting the presence of confounders between all pairs of nodes in An(Y) as in Algorithm 3 we focus on identifying the necessary and sufficient ones, characterized by Theorem 3.1] This approach is more sample-efficient since tests for fewer latent confounders. The exact saving in terms of samples depends on the underlying causal graph and is hard to characterize in general. The last step of Algorithm i to run a simple bandit algorithm, e.g., UCB algorithm [26). to identify the optimal arm from the POMISs. Given that Assumptions
4.2 and 4.3 hold, and the reward binary (Y E {0, 13), using the results from Lemma 4.4 and Theorem we provide a worst-case regret bound for Algorithm 4 in Theorem 5.1
Algorithm 4: Sketch of Algorithm for causal bandits with unknown graph structure
Calculate a, 61, 62, 63, 54 as in Theorem 5.1
g = L
W
G, DaIDa = LearnOOservableGraahh (An(Y)))))))) ggre, at dmars 81, 62) # Learn the bi-directed edges between reward Y and all nodes X; An(YY) and update G.
for every X E An(Y)) gtte do
L G DettectLatentCoffounderr( X,, X,, 62, 83, 64, IData) (Algorithm 5
while There is new pair that is tested do
Find a new pair (Z, X)) s.t. Z E An(Y) such that Z and Y don't have bi-directed edge between them in & and X E MUCT(GG:: zi.gy Y) and test for the latent and update G.
G DeteectLteentoooffuuderrr
Z, X, X,82, 8g, 54, IDtaa)
10 Learn the set of POMISs Ia from the graph & (Using Algorithm 1 from (5).
Run UCB algorithm over the arm set A = (N(I) VI E Iz}.
Theorem 5.1. Algorithm 4 learns the true set of POMISs with probability least 1 25. Under the event that it learns POMISs correctly, the cumulative regret is bounded as follows:
8 log 4n²K²
8
4nK2
Rr S Knnma
(2)
log
( 72)
5
log 1
8admar KA|An(Y)] + max( c) log (IAn(Y)) +
Σ
Adots)
A2 do(s)
SE (R(MMMEEI)
where A and B are given by line 2 of Algorithm ! 2dmar log (2) 81
and C is given by line 3 of Algorithm 3 by setting and 82 83 = 62
log An(Y))
Gácxdimaa An(Y)) log An(Y))
G4ardmas log An(Y)
8

---

The first three terms in the regret bound correspond to the interventional samples required to learn the ancestors of the reward node, and then the set of POMISs (Iş). The last term corresponds the regret incurred by running the UCB algorithm over the POMIS set. The number of interventional samples used to learn the true set of POMISs, with high probability, has polynomial scaling with respect to the number of nodes n in the graph. However, the total number of arms in the POMIS set, in the worst case, can exhibit exponential scaling with respect to the number of ancestors of the reward node AAn(Y)), ) The advantage of sample-efficient discovery is that it helps us reduce the action space before applying the UCB algorithm. If the graph is not densely confounded, the total number of arms in the POMIS set would be small, and running causal discovery before the bandit algorithm is advantageous. Without discovery, one would always have to run the UCB or a standard MAB solver with exponentially many arms. For instance, if the causal graph has nodes, there will be > 1 (m) K" = (K + 1)" different possible arms/interventions.
6 Experiments
Theorem 5.1 establishes the worst-case upper bound for cumulative regret when we need to test latent confounders between all pairs of nodes within AY().. However, Algorithm Jeleetiivey examines only a subset of latent confounders sufficient to infer the true POMIS set, as outlined in Theorem Although the advantage is hard to quantify in general, we demonstrate it using simulations on randomly generated graphs. We sample random ordering σ among the vertices. Then, for each nihh node, we determine its in-degree as X,, max(1, 1, Bin(n- 1. p)). followed by selecting its parents through uniform sampling from the preceding nodes in the ordering. Finally, we chordalize the graph using the elimination algorithm 227, employing an elimination ordering that is the reverse of a. Additionally, we introduce a confounder between every pair of nodes with probability of pr.- For all the simulations,
3.1
randomly sample 50 causal graphs with different values of densities p and P1 and assume that all variables are binary for simplicity, i.c., K = 2. We set the value of to 0.99, and the gaps 7 e 0.01 and 1) = 0.05. We plot interventional samples used to learn the induced observable graph on An(Y) with and without latent confounders, as well as the samples required to learn the POMIS set by Algorithm 4
The width of confidence interval is set to 2 standard deviations.
Interention Semples
to
to =10f
Interverttoaal tread Somppee
10 10"
p= 1.2, pt. D66
Intersatiinal Sumuuao
Lean deg PCSBS Alg
Loening bohtett Aac't with locaa Ulversale bubiod prpioo A6/T1
Team bevil porl seel) with grod Sealy
Leas Chesrall Tnlland grick os Acll!
10
16
30
10
15
20
Number of Nodle G.A, de 0.2
Number Nodes
Namber of Nocee
Eseevesiioal Sumples
IntervalDonal Sumples
D4, Du4
Inzernational Samplex
11
-.1. Ps =
-.0
Losnaing FOOES (kly 41
PCMS
--- Lowaiing Deseoaale bob and gigll Aa
thaoeell and
03
15 Numbee Nodes
10
15
15
20
Nurber of Nodes
Numbber of Nodos
Jnne Imeeyntton Sumples
<10
0if,, 0.2
Istervontioaal Sumphe
108
066 de
0.6
Loarting (klg il
bohood sat town
Disooalle bood pights Marl)
Lockk Coumaa batoed pook 201)
G- Loviing (ivemaaee bukt pratt
Nodes
10
Number of Nedes
8
10
Sumber Nodes
Figure 2: Simulations to demonstrate the advantage of Algorithm over full graph discovery
(Learning all possible latents)
The simulation results in Figure 2 demonstrate that Algorithm 4 requires fewer samples than learning the induced graph on AY(). which includes all confounders. However, as pr. increases for fixed p. this advantage diminishes, as illustrated in Figure 2 The trend remains consistent as the density parameters p and PL are varied from 0.2, 0.4, and 0.6. The plots in Figure compare the exponentially
9

---

growing arms in causal bandits with intervention samples used by our algorithm to learn the reduced action set in the form of POMISs. This demonstrates the major advantage of our algorithm, which, instead of exploring an exponentially large action set as in naive UCB algorithms, uses interventions to reduce the action space to the POMIS set before applying the UCB algorithm. Additionally, the number of intervention samples required in the first phase of identifying the true POMIS set grows polynomially with respect to the number of nodes in the graph. However, the number of arms in the POMIS set can still exhibit exponential scaling with respect to the number of ancestors of the reward node in the worst case.
10%
ALSY with idteca
(h-d)
10
10
10
4
1011
12
10a
15
20
19
90
15
25
30
Nansher
(a) p = 0.4, PL = 0.2
p 0.4, PL = 0.4
(c) p = 0.4, PL 0.6
Figure 3: Simulations to demonstrate advantage of discovery for causal bandits.
Leeranag SeSani areaa on ADCS wirk DE awven 00B
ArTS with Linnda + 1831
prgt ao Laweete POSTle
Uncedaatie Seore (8c)
Couaedatre Bagrn
11me (1)
Tamm (1)
Dtec (1)
(a) Nodes n. 10
(b) Nodes = 15
(c) Nodes 20
Figure 4: Cumulative regret for Algorithm 4 versus learning all possible latents (p = PL = 0.3).
We also run the UCB algorithm on the learned POMIS set and plot the cumulative regret in Figure Since the number of time steps T is on the order of 10a, it is not feasible store and plot cumulative regret for every time step over multiple randomly sampled graphs; therefore, we downsample the cumulative regret to show the overall trend. The downsampling, along with the large scale of the y-axis, makes the regret in the discovery phase appear linear with a fixed slope, although it is piece- wise linear if we zoom in. Also, the UCB phase converges very fast compared the discovery phase because the number of POMISs for randomly sampled graphs is small. We plot the results for graphs with 10, 15, and 20 nodes, and in all cases, we can see the advantage of partial discovery compared to full discovery, since Algorithm 4 finds the POMIS set with fewer samples. The code to reproduce our experimental results is available at with_ UnknownGraph
com Lttp///aaaaaLLLaaaaaaSaaL
7 Conclusion
We show that partial discovery is sufficient to achieve sublinear regret for causal bandits with an unknown causal graph containing latent confounders. Without relying on causal discovery, one must consider interventions on all possible subsets of nodes, which is infeasible. Therefore, we propose a two-phase approach: the first phase learns the induced subgraph of the ancestors of the reward node, along with subset of confounders, to construct a set of possibly optimal arms. We demonstrate that the number of interventional samples in the first phase required to identify the POMIS set scales polynomially with respect to the number of nodes in the causal graph. In the next phase, we apply the Upper Confidence Bound (UCB) algorithm to the reduced action space to find the optimal arm.
8 Acknowledgment
Murat Kocaoglu acknowledges the support of NSF CAREER 2239375, IIS 2348717, Amazon Research Award and Adobe Research.
10

---

References
[1] Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interven- tions via causal inference. Advances in Neural Information Processing Systems, 29, 2016.
[2] Rajat Sen, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Identifying best interventions through online importance sampling. In International Conference on Machine Learning, pages 3057-3066. PMLR, 2017.
[3] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge. In Conference on Uncertainty in Artificial Intelligence, pages 141-150. PMLR, 2020.
[4] Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits, In International Conference on Artificial Intelligence and Statistics, pages 2017-2025. PMLR, 2021.
[5] Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? Advances neural information processing systems, 31, 2018
[6] Lai Wei, Muhammad Qasim Elahi, Mahsa Ghasemi, and Murat Kocaoglu. Approximate allocation matching for structural causal bandits with unobserved confounders. Advances in Neural Information Processing Systems, 36, 2024.
[7] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. Advances in Neural Information Processing Systems, 34:24817 17-24828, 2021.
[8] Arnoud De Kroon, Joris Mooij, and Danielle Belgrave. Causal bandits without prior knowledge using separating sets. Conference on Causal Learning and Reasoning, pages 407-427. PMLR, 2022.
[9] Mikhail Konobeev, Jalal Etesami, and Negar Kiyavash. Causal bandits without graph learning. arXiv preprint arXiv:2301. 11000.111000 11401, 2023.
[10] Alan Malek, Virginia Aglietti, and Silvia Chiappa. Additive causal bandits with unknown graph. arXiv preprint arXiv:2306.007855 2023.
[11] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: founda- tions and learning algorithms. The MIT Press, 2017.
[12] Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, and Gyorgy Simon. Challenges and opportunities with causal discovery algorithms: application to alzheimer's pathophysiology. Scientific reports, 10(1): 2020.
[13] Alessio Zanga, Elif Ozkirimli, and Fabio Stella. A survey on causal discovery: Theory and practice. International Journal of Approximate Reasoning, 151:101-129, 2022.
[14] Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. Advances in Neural Information Processing Systems, 30, 2017.
[15] Kun Zhang, Biwei Huang, Jiji Zhang, Clark Glymour, and Bernhard Schölkopf. Causal discov- ery from nonstationaryyheeerggneeee data: Skeleton estimation and orientation determination. In IJCAI: Proceedings of the Conference, volume 2017, page 1347. NIH Public Access, 2017.
[16] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.
[17] Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Ko- caoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. Advances in Neural Information Processing Systems, 32, 2019.
[18] Muhammad Qasim Flahi, Lai Wei, Murat Kocaoglu, and Mahsa Ghasemi. Adaptive online experimental design for causal discovery, 2024.

---

[19] David Heckerman, Christopher Meek, and Gregory Cooper. A bayesian approach to causal discovery. Technical report, Technical report mss-tr-97-05, Microsoft Research, 1997.
[20] Yashas Annadani, Nick Pawlowski, Joel Jennings, Stefan Bauer, Cheng Zhang, and Wenbo Gong, Bayesdag: Gradient-based posterior sampling for causal discovery. arXiv preprint arXiv:2307.139111 2023.
[21] Christian Toth, Lars Lorch, Christian Knoll, Andreas Krause, Franz Pernkopf, Robert Peharz, and Julius Von Kügelgen. Active bayesian causal inference. Advances in Neural Information Processing Systems, 35:1 15:166661-1275. 2022.
[22] Judea Pearl. Causality, Cambridge university press, 2009,
[23] Jin Tian and Judea Pearl. A general identification condition for causal effects. In Aaai/iaai, pages 567-573, 2002.
[24] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926-939, 2014.
[25] Alfred V. Aho, Michael Garey, and Jeffrey D. Ullman. The transitive reduction of directed graph. SIAM Journal on Computing, 1(2):131-377, 1972.
[26] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[27] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
12

---

A Supplemental Material
A.1 Review of d-separation:
Consider three disjoint sets of nodes X. Y, and Z in the causal graph G (V, E). EV, The sets of nodes X and Y are d-separated given Z. denoted by (X PTt Y if and only there exists no path, directed or undirected, between any node in set X and any node in set Y such that for every collider on the path, either the collider itself or one of its descendants is included in the set Z, and no other non-collider nodes on the path are included in the set Z. (A collider on path is a node with both arrows converging, e.g., a collider on the path ABC in + B + C).
A.2 Pearl's Rules of do-Calculus (2
Let G represent the causal DAG, and let P denote the probability distribution induced by the corresponding causal model. For any disjoint subsets of variables X, Y, Z, and W, the following rules apply:
Rule I:
(Insertion/deletionn of observations):
P(y]do(x), w) = P(yldo(x), if (Y Il Z/X, W)
(2)
Rule 2:
(Action/obserrattion extrbo//bbbrrraiionxecchhng
(o(()))) w) P(y)do(x),,, if (Y IL Z|X, Wo
(3)
Rule 3: (Insertion/delctionn of actions):
(ty) w) Ply]do(x), w) if (Y IL Z,X, &) k(w
where Z(W) is the set of nodes in Z that not ancestors of any of the nodes in W in the graph 9x-
A.3 Function to Detect Presence of Latent Confounder:
Algorithm 5: Function Detect Presence of Latent Confounder
Function Deteectaatenttooooooooe
(G, X;, Xj, 62, 03, ō4, IData): 2nk²
16 yyy
log( 2n 2n
+ Σny log( 2n² B log 22
bg
04
X, E An( (,) swap them.
Find interventional data sets do( w) and do(X; Hi, W = w) from Datta s.t. (Pa(X,) U Pa(X,) \ (X.)) C W and X; & X2 W
Get max (0, B C') new samples
do(W w)
if wi, æy E [K] s.f. [a(, (do(x;)) do(w)) ((syl=;;doww))
then
L Add bi-dirceted edge X; ++ X, to graph g
return Updated Causal Graph g
End Function
A.4 Proof of Lemma 3.2
Lemma. 3.2: It is necessary to learn/detect the latent confounders between reward node Y and any node X AY) in causal graph G to learn all the POMISs correctly and hence avoid linear regret.
Before proceeding to the proof, recall an important result from reward variable Y, [B Y) is a POMIS for any W S V.Y..
5 For causal graph G with
Proof: Consider a causal graph g(V. E) with node X E An(Y') such that there exists latent confounder between X and the reward Suppose we do not detect the presence of the confounder and have access to another causal graph G' with everything the same as G except that there is no confounder between X and We show that there exists one such POMIS that we cannot learn from G', which actually exists in the true causal graph G. To prove this, consider set of nodes
13

---

W = Pa( U ())) U (C(X) (X,Y), For the graph G', note that X & MUCT(G" W. Y). and also there BZ E (h() \ { s.t. ZE MUCT(G w. Y). This implies that AZ E (X( s.t. 7 E IB( w. Y). However, for the true graph G. we have a different IB(g Y) for the same definition of W because contains the bi-directed edge between X and Y. which implies that [ X E MUCT ( Y), and as result, Pa(X) C IB W. Y). Also, in the case Pa(X)= 0. we have
a different POMIS. On this side, note that X & MUCT w. Y), which implies that along the causal path from X to Y. there must be one node Z such that Z E MUCT(G' w. Y), which implies either X or one of its descendants on the path from X to Y is in IB' w. Y), which is not the case for g : Y). Thus, have different interventional boundary POMIS for the two causal graphs G and 9" given the above choice of W, even if X has no parents.
since X E MUCT(GW
The next step is to show that the particular POMIS IB (B Y) cannot be learned from the DAG g', i.e., IB Y) * (B'9' WT; Y) for any W C V. We need to show this because of the graphical
characterization of POMISS in Lemma 3.1, Using the definition of W. note that Pa(X) S I w: Y)
and for all Z E Ch(Pa(X) (X) ()({)) (X), there exists either Z E 1:: Y) or (e (Y) E (B Y).
Also, if there are such nodes in CC(X) \ (x, Y) which do not have path to X comprised of directed edges only, call such set of nodes T. If T * o. then for all t E T, we have either t E IB(g w. Y) or De(() (Y} E IB(Gw: Y). Also, note that AZ E De(X) U {X} such that Z E ( )). Now consider DAG g with the bi-directed edge between X and Y missing, Assume by contradiction ME S V such that IB Y) =IC WT. Y). This, however, using the aforementioned characterization of ( Y) implies that AZ E Ch(Pa(X)) \ {X} such that Z E MUCT(G' WT. Y) and also At T such that t E MUCT(G' wT, Y) using the aforementioned definition of T. However, note that we need Pa(X) S IB(( w. Y) which under the given choice of W is only possible when X E MUCT(O' W Y), which would require is a bi-directed edge between X and Y in the DAG g', which is a contradiction. Also, for the case when Pa(X) = Φ. we have contradiction because we require the following to be true: AZ E De(X) U {X} such that Z E (g' w Y). For the given choice of W, it implies that there is a bi-directed edge between X and Y in the DAG G', which is again a contradiction. Thus, by contradiction, we show that JW V such that G', i.e., W Y)= * IB' w: Y). This implies that we will miss at least one POMIS if we do not learn or detect latent confounders between the reward node Y and any node X E AY(Y). and may incur linear regret. This completes the proof of Lemma 3.2
A.5 Proof of Theorem 3.1
Before proving Theorem 3.1 we state and prove another Lemma. We then extend this Lemma to prove Theorem 3.1
Lemma A.1. Consider causal graph G(V. E) and another graph g' such that they have the same vertex set and directed edges but differ in bidirected edges, with the bidirected edges in G' being subset of the bidirected edges in G. The gruphs will yield different collections of POMISs if there exists some Z E An(Y) such that either (a) or (b) is true:
(a) There is a bi-directed edge between 2 and Y in G but not in G'
(b) Neither of the graphs G' and G have a bidirected edge between Z and Y, and there exists a bidirected edge in G between some X &MUCT(C PP Y) and Z but not in G'.
The first half of Lemma A.1 i.c., "The graphs will yield different collections of POMISs if there exists some Z E An(Y) such that there is a bi-directed edge between Z and Y in g but not in g'." is the same as L.2ma and the same proof applies here. The reason is that in graph g', we miss latent variable between reward and one of its ancestors, which was actually present in the true graph G. We only need to proof the second half of Lemma i.. graphs will yield different collections of POMISs if there exists some Z E An(Y') such that (b) is true. Consider a causal graph GVV, E) and another DAG G' such that they have the same vertex set and directed edges, but differ in bi-directed edges. Consider a causal graph G(V, E) and another DAG G' such that they have the same vertex set and directed edges, but differ in bi-directed edges. We show that if neither of the graphs G' and & have bidirected edge between Z and Y. and there exists bidirected edge in G between some X E MUCT (Aa))(() Pa(2),Bi(Z,57) YY) and Z, then there exists one such POMIS that we cannot learn from G', which actually exists in the true causal graph G. To prove this, consider set of nodes W = Pa(Z) u Ch(Pa(Z) \ An(X)) U Bi(Z,9") \ (X, Z, Y). For
Proof:
14

---

the graph G note that Z & MUCT(G' W. Y), and also there AN& E Ch(Pa(Z) \ An(X)) (2) s.t. N MUCT W. Y). This implies that AN E Pa(Z) \ An(X) s.t. N E IB w: Y). However, for the true graph G, we have different IB (B( Y) for the same definition of W because it contains the bi-directed edge between X and Z, which implies that Z E MUCT(SW: Y), and as a result, Pa()){ \ An(X) S IB(9w. Y). Also, in the case Pa(Z) \ An(X)= = 0. we have different POMIS. On this side, note that Z & MUCT((' W Y), which implies that along the causal path from Z to Y. there must be one node N such that N E MUCT(G" w. Y), which implies either Z or one of its descendants on the path from Z to Y is in IB(g' w, Y), which is not the case for G since Z E (UW Y). Thus, have different interventional boundary or POMIS for the two causal graphs 9 and G" given the above choice of W.
The next step is to show that the particular POMIS IB IB( Y) cannot be learned from the DAG g', i.e, IB Y) * IB(9' wi; Y) for any W C V. We need to show this because of the graphical
characterization of POMISS in Lemma 3.1, Using the definition of W, note that Pa Z)) \ An(X)= S
lB Y) and for all N E Ch(Pa 2) y An(X) (n())) {2). there exists either N E IB G Y) or ( (B, Y), Also, if there are such nodes in Bi (") [XX, Z, Y, which do not have
a path to comprising of directed edges only, call such set of nodes T. If + Φ. then for all t E T, we have either/ E IB(Gw: Y) or De(())s {Y)
such that N E ( Y). Now consider the DAG g' with the bi-directed edge between Z and Y missing. Assume by contradiction M: < V such that Gw. Y) = IB( W.. Y). This, however, using the aforementioned characterization of IB Y) implics that AN E Ch(Pa(Z) \ Ann()) \ {2) such that N E MUCT(G' wT. Y) and also St E T such that t MUCT(S WT, Y) for the aforementioned definition of T. However, note that we need Pa(Z) \ An(X) S [B( wT. Y), which under the given choice of W is only possible when Z E MUCT(S' W. Y), which would require bi-directed edge between Z and X in the DAG g', which is a contradiction. Also, for the case when Pa(Z) = Φ we have a contradiction because we require the following be true: AN E De(Z) U {2} such that N E IB' w Y). For the given choice of W. it implies that there is a bi-directed edge between Z and X in the DAG g", which is again a contradiction. Thus, by contradiction, we show that JW V such that g', i.e., IB (9 (w: Y)= * IB(g' W.. Y). This implies that we miss atleast one POMIS when either of statements (a) and (b) hold. This completes the proof of Lemma A.1
( Y). Also, note that INN E De(
We now proceed to the formal proof for Theorem 3.1
Theorem. 3.1: Consider causal graph G(V, E) and another DAG G' such that they have the same vertex set and directed edges but differ in bidirected edges, with the bidirected edges in G' being a subset of the bidirected edges in G. The graphs will yield different collections of POMISS if and only if there exists some 7. E AY) such that either (a) or (b) is true:
(a) There is bi-directed edge between 2 and Y in G but not in G'
(b) Neither of the graphs g' and & have a bidirected edge between Z and Y, and there exists bidirected edge in G between some X E MMUCT(G PP11,, Y) and Z but not in g'.
One direction for Theorem 3.1 is proved already in Lemma A.1 We only to need to prove the other direction which is that two causal graphs G and G' such that they have the same vertex set and directed edges, but differ in bi-directed edges will yield same collections POMISS when neither of statements (a) and (b) is true. Note when neither of (a) or (b) is true the graphs G and G' might still have a different set of bi-directed edges. We will have two possible scenarios here. Suppose G has bi-directed edge between some 7 E An(Y') and some X E An(Y), such that there is a bi-directed edge between pair of vertices (Z, Y) and (X, Y) in both the graphs and the bi-directed edge between X and Z is absent in G'. Further, assume neither of statements (a) and (b) hold. In this case, despite the absence of bi-directed edge between X and Z in G', the graphs will yield the same set of POMISS. This is because Z & MUCT(GT, Y) for some set of nodes W only when Z E W, and the same is the case for & because they share bi-directed edge between Z and Y. By symmetry, we have the argument hold for X as well. So, the presence or absence of bi-directed edges between X and Z does not change the set of POMISS learned from the graph when both and Z are confounded with reward Y already. Thus, we can delete all such bi-directed edges one by one from G while the set of POMISs learned from each of the intermediate causal graphs stays the same. Consider the second scenario, where G has bi birdirect edges between node Z E An(Y), ) such that there is no bi-directed
Proof:
15

---

edge between Z and Y in both graphs (g and G') and node X that has the following characteristies: Y). However, the bi-directed edge between X and Z is absent in g'. Further. assume neither of statements (a) and (b) hold. The condition X E MUCT(9' w. Y) but X & MUCT(S B.12) Y) implies that either
X E MUCT(S" W. for some set W S V but X & MUCT(S', Ba)
EN E Z)( such that N E MUCT(G w. Y) or 3N E Bi(Z, g') such that N E MUCT(S' W. Y). Since bi-directed edges in 9" are a subset of bi-directed edges in G, we have: Rither EN PZ( such that N E ( Y) or NN E Bi( such that N E MUCT(SW Y). Note that any MUCT closed under the De(.) and CC(.) operations, i.e, for any MUCT, say T, we have De(T) T and CC(T) = T. if EN E Pa(z) such that N E MUCT(C w. Y) or NN E Bi(z,9) such that N MUCT(S Y). we already have Z MUCT(S w. Y) using the definition of MUCT. The bi-directed edge between X and Z will play a role only when EN E Pa(Z) such that N E MUCT(SW: Y) and AN- E Bi(Z, g) such that N E MUCT(SW: Y) for any choice of W. Recall that the given condition X E MUCT(G W: Y) but X & MUCT(C
Pa Bi(2), Y) already implies that either IN E (Z( such that N E MUCT(S P) or IN E Bi(2, 9) such that N E (U Y). Thus absence or presence of bi-directed edge between X and Z will have no effect on POMISs learned from graph G in this scenario as well. Combining both of the scenarios when neither of the conditions of (a) and (b) hold, all other bi-directed edges from G. which are absent in G", can be removed one by one from G while keeping the POMISs learned from both the intermediate graphs the same. Since G and g' only differ in bi-directed edges, with bi-directed edges in g' being subset of those in G, eventually both graphs will become identical, which proves the statement: Two graphs G and g' will have the same POMISs if neither of the statements (a) or (b) hold true. This completes the proof of the Theorem 3.1
A.6 Proof of Lemma 4.1
Consider causal graph G(V E) and W S V. Furthermore, let X, E \ W be any two variables. Fix some realization w E [K]lWi, Under post interventional faithfulness Assumption 2.1 we want to prove: (X E An(T)) = (()) + P(t]do(w), do(x)) for some x,, t E [K]
for some x, E [K]. By contradiction, assume ((t)do(w)) = P(t|do(w) (w), do(x)). Vx, t E [K]. This implies that P(t]do(w) (W), do(x)) P())do(w)) = some function of only t and w. This implies that for the sub-model Mw.x the following CI statements holds: (T IL M)Mw.x However, note that if (X E An())) then we still have (X E An(T)) This implies there is a directed path from X to T in the post-interventional graph 9w Therefore, we have: (T AL X) Note that under the post interventional faithfulness Assumption 2.1 the CI statement (T TL X)Mw.x x can hold only if the d-separation statement holds (T' lLd X) Sw,x which is clearly contradiction. This completes the proof for the forward direction.
Forward Direction (=) ): (X E (T)))) = P()]do()) o P(()oow))dol)
Reverse Direction ( < ): (X E An(T))) = P()) * P(t dw)), do(z)) for some x,t [K]. We prove the contrapositive statement instead, i.c., (X & An(T)),, = (W)) P(t]do(w), do(x)), Va,t E [K]. Note that (X & An(T)) clearly implies that (X & An(T)) which implies that (T la X) Thus, using Rule 3 of Pearl's do calculus, we have: P(t)do(w), do((z) = P(t P(t)do(w)), Vn,t [K]. This completes the proof of the reverse direction.
A.7 Proof of Lemma 4.2
Consider two variables X, and X, such that X, & An(,)) and a set of variables (Pa(X))UPa(X,) \
(X.)) S W and X; & X; & W. Fix some realization w E [K] Under the post-interventional
faithfulness Assumption 2.1 we want to show that: There is latent confounder between X; and X,
+ P(zy do(x;), do w w)) + P(æ; I,, do( = w)) for some realization F,, Zy E [K].
Forward Direction (=) ): There is latent confounder between X; and X, such that X, & An(X.)
= Play do(x;), do (W- = w)) * P( Hi, do(W = w)) for some realization di zy E [K] By contradiction assume P(z, do(x;)), do( =w) P P(æ,) I., do(W- =)) Vz,, 23 E [K). Recall
16

---

that: X, = (P)(())) Uj). Since there is latent confounder between X; and X, call it Lig. Also note that Lij E Uj. Define Uj= := Uj {L,
P(a;| do(=:), do( W)) P(xy do(x;;) (dop))))ddd((())))
(2;))))
(5)
where the interventions do (a(()))) and do(Pa(X))) ))) are consistent with do(x;) and do( W = w). The equation[5]hol hollds by the application Pearl's do-caleulus Rule 3 because, by definition of the set W, we have (Pa(X,) U Pa(X)) {X,}) S W and X,, X, & W. All the extra intervention targets can simply be deleted, and we are left with intervention on X, Pa(X;), and Pa(X)).
P(ay (o(xx)),
Σ ug. 16g
P(ay d((a))))(ppax)))), do(ax(X) \ (zi)), U', n'J, Lوا = 4g))
x P(U", = u'j. Lij = 1.y)
(6)
We have another application of Pearl's do-calculus Rule 3 because interventions on observed variables don't ton't affect unobserved variables, there are causal/directed paths from observed to unobserved variables. Also we have:
P(a, o. do = P(x, |,, (o.. (x)))))
The equation holds by the application of Pearl's do-caleulus Rule 3 because, by definition of the set W, we have (Pa(X,) U Pa(X,) {X,}) S W and X,, X,, X,, $ W. All the extra intervention targets simply be deleted, and we are left with conditioning on X; 2; and interventions Pa(X,) and Pa(X)).
P(æy | x4, (o)) =
Σ uij bo
P(x, 24 do(pa( do(pa(XX,) \ (2;1), U' = =u'j. Lij = =41)
P(U"; =ujj. Taj = Layla,, (o(pa( (X))) (p (X()) \ {I:
Using Pearl's do-calculus Rule 2, can replace the conditioning X; = with the intervention do(x;) in P(z, x, do(p((X))) do( (Xx,)) {x;3), =',=u', Laj = byy) because X, $ An(),) and Pa(X,) are already intervened on. Also, the latent confounder Lıj is conditioned on, there is no open backdoor path from X, to Xy. Thus, we have:
P(xy Es, do()) = Σ P(zy | do(x;)) do(pa(X) f2i1), U'; = u'y, Lıj = 4ig)
un. 1as
x P(U', =' j'jj,T. T.j = liglas, do do(pa (p(()))))))p))))))))))))))))(( \ (xx1))
From the Equations 6 and 9 and assumption P(a; do(a;)) do( -w) P(rrg) Mi, do W =w))
Vz; E [K] we have:
Σ
P(a, dolpa (aii), U', = u'y, Lis 44)
ul. L..
x (P(U'= =u,, Lij = Lig |z,, do(pa do(pa(XX)) - -u', Lij = (45) =0
(10)
Since probabilities are non-negative, whenever P(a; do(x:), do (o((p(()))) do(pa(Xx))
(z,)), U', u'j, Lig = (4) > O. we must have:
17

---

P(U', = L. 4y|=, do(pa do(pa(XX) = P(U', u'
4T) (11)
However, since we know that Lyj is confounder between X; and X,. we have an edge Lij + X; in the causal graph, which implies that under any intervention do(Z) such that X; & Z. we must have (Iey A Mz by interventional faithfulness Assumption 2.1 This implies that there exists realization 2 and r.g such that:
P(U'; n' Loj = -1ylo (pa()))))) (o())(X;)) \ (xa))) + - Lij = (21)) (12)
Now, using the combination do W = w) and special choice of realizations x; and 12 we must have at least one special realization 23 such that: P(xž | do(x;). do(Pa(X,)), do))a())))
{=;]), U', = u'5 Tng- = 14 > O. Combining this with Equations] 12 and 10, we conclude for some 2f 2z E [K), we have P(a do(=;), do(W= = w)) * P(r5 | x do W w)). Thus this leads to contradiction.
Thus there is a latent confounder between X; and X5 = P(æj do(x;), do w)) o P(ay
Tz, do w)) for some realization 2;, [K]. This completes the proof of the forward direction.
Reverse Direction ( (=) ): For a pair variables X; and X, such that X; & An(X.), P(ay I do(x;), do(W- W = w)) P(x, 24, do(W w)) for some realizations 2,, 23 [K], then there is latent confounder between X, and X,. We prove the contrapositive statement instead, i.c., if there no latent confounder between X; and Xj. then P(zy do(x,), do( W = ww] = P(x, zi, do(W = w)), 2z E [K] Note that by construction, we have: (Pa(X,) U Pa(X,) (x+)) f W. For such choice of set W and the fact that X; & An(X,) and there is no latent confounder between X, and X,. we have (X, 1L Xi)9x, Thus, from Pearl's 's do-calculus Rule 2, we have P(z, do(z;), do( =
w)) P(r,) Vi, do W = w)). Va,, Ity E [K]. This completes the proof of the reverse direction.
A.8 Proof of Lemma 4.3
Suppose that Assumption 4.1 holds and we have access to mar -.t & log 2K o, samples from
73
do(X; = Ti, W = ww Vx: E [K] and 8
z log 2k² samples from do W w) for fixed w E [K] [W]
for some W S V. We want to show that with probability at least - 51 82. we have the following:
(X; An(X)))s,
3 24, By
[K] s.t. P(xr)dd(w)) ((zyldo(w))
2 (13)
Using Hoeffding's inequality with samples from intervention do(x;; w).
1 2K2
51
P(æ,)do(a;)) do(w)) do)))))dow))) do(w)) 2
1
log
w.p. at most K²
(14)
2A
If we choose A = max( 3,, 8
log 2x² 7z) or
we have:
P(z))lo(2)),dd(f - (dox)) 2 c
81
w.p. at most
(15)
K2
Similarly, using Hoeffding's 's inequality with B samples from intervention do(w).
P(z)]do(w)) P(æyldo(w)) 2
V 2A on
1
log
2K2 w.p. at most
K2
82
(16)
If we choose B $ log 2k² 02
we have:
P(æzldo(w)) - P(xy (do[)do()))
2 w.p. at most
(17)
K2
18

---

Since the realization w E [K] | is fixed, while æ; and æ; are in [K], we have total of K possible bad events when the estimates are not accurate. Given the choice of samples, and B, we have:
(elldl((;,, - ((1yldo(ss),do(w) 6 Vr,, 2. E [K] w.p. at least - 81, (18)
P(az)do(w)) - P(xy|do(w)) - S Vay [K] w.p. at least. 82.
(19)
Under the good event, which occurs with probability of least ō1 82, the estimates accurate. We now consider the two possible scenarios. Suppose that X; & An(X,) in Pw- In this case
by Pearl's do-calculus Rule 3 we have ((ay)do(z;) - P(æz)do(w)) = 0, Vene 2y E [K].
By triangular inequality we have the following:
P(ryldo(xx)) do( -
- [(or]ldo(x)) do(w)) - P(ozldo(z;)) do())))ddoo))))))))))))))))))d do(w))
P(æzldo(w)) P(rzldo(w)) (((p)d(())))(r))d(M))))) S
Vr,, Ty E [K]. (20)
However, when X; An(X;) in Iw under Assumption 4.1 we must have some configuration say 2y E [K] for any w E [K] such that P(x,) (do(x, do(w)) - P(x, (do(w))
e. By triangular
inequality when X; E An()) in Pw: 3 3.,, 33 E [K] such that
P(zyldo(zz), do(w)) - P(xy)do(w)) 2 P(az)ld(2z) - P(æyldo(w)))
((r)) do(w)) - P(æ, (d((;),();) do(w)) - P(zz)do(w)) P(zzldo(w)) > e
2' (21)
Thus, using Assumption 4.1 with the given choice of number samples with probability at least 1 - 6i 82, we have the following result:
(X, An(X)))
3 x., F, E [K] s.t. P(x,ldd(w)) P(z,)do(w) > 2 (22)
This completes the proof for Lemma 4.3
A.9 Proof of Lemma 4.4
In order to prove that Algorithm learns the true transitive closure under any intervention, i.e., Gtc we recall from the proof of Lemma 4.3 that the test for ancestrality works with high probability under the event that the causal effects of the form (d(s)) (oooa,dodowww))) do(w)) and ((ry)do(w)) are estimated accurately with error of at most for all 24, By [K] and any fixed E [K]W Now, since
Algorithm takes B -/4 log 2nk² samples from every do Ii, W w) for all X; V W and for all x; [K], the total number of intervention samples collected is clearly at most K An + B. order to show that Algorithm[] learns the true transitive closure under any intervention, i.e., Gte. with high probability, we must demonstrate that Algorithm can estimate all causal effects with maximum error of & with high probability, so that all the ancestrality tests work with high probability, as implied by the proof of Lemma 4.3
&2 samples from do( W w) and A max - K log 2nk² &
19

---

Using Hoeffding's inequality with B 2 log for any X, V W:
2n 82
samples from the intervention do(w), we have
P(zyldo(w)) P(zzldd(w)) S Vrz E [K] w.p. least
82 (23)
n
Using the union bound we have the following:
P(X, = 2z)do(w)) P(X, = xz =o)())
$ e Va, E [K], VX, V W w.p. at least 1 1-82-
(24)
Now, consider fixed pair x,, X, E W, and using A max 8
log 2nK samples from the intervention do(r;; w) for every Hı [K], we have the following using Hoeffding 's inequality:
d(x)) P(zz]do((z)) dolz:)))oo()))))) do(w))
< min(
S. 2) 4' 4
Vxs, F. E [K]
w.p. at least 1 1 81
(25)
Using the union bound we have the following:
do()))) P(rr)do(zz;), min( 4' 3/
Vx,, E [K], vX, E (W (X+)) w.p. at least 81
(26)
Again using the union bound over all intervention targets X; V we have the following:
d(o)))) - P(ry)do(as)) S <inn( E 7 4' 4
Vx,, E [K] VX, E V w, VX, E \ (WU w.p. at least ndj
(27)
From Equations 24 and 27 using the union bound with probability at least nō, 82, all the
causal effects are estimated within error of & from the true values, ensuring that all ancestrality tests work perfectly under this good event. Thus, Algorithm [ learns the true transitive closure under any intervention, i.e., Gte. with K An B intervention samples with probability of least
W
1 1- 1-n61 82. Also, if we set 81 5 under any intervention, i.e., Gte with a probability of - 6, with K An + B intervention samples.
2n and 8, = 3. then Algorithm learns the true transitive closure
where A max ( 72
log k² and B a log 4nk² This completes the proof of Lemma 4.4
A.10 Proof of Theorem 4.1
We start by revising the statement of Lemma 4.3 Algorithm I learns the true transitive closure under any intervention, i.e., See with KAn + intervention samples with a probability of least 1 nój 52. Algorithm randomly samples target set W and calls Algorithm learn the active true transitive closure of the post-interventional graph, i.e., 9 For every iteration, Algorithm
computes transitive reduction Tr(gk) and updates all the edges to construct the observable graph. To prove the results Theorem 4.1
W
we rely on Lemma from [4] which is stated below:
20

---

Lemma A.2. [4] Consider graph G with observed variables V and an intervention set W C V. Consider post- instiinterventional observable graph 9w and a variable X; E V W. Let X; E (a(X)) be such that all the parents of X; above X; in partial order are included in the intervention set W. This implies that (W; : ((W)) > (x;)) & W; E Pa(X))) 3 W Then, the directed edge (X,,X) X2) E B(Tr(Gw)). The properties of transitive reduction yields Tr(Sw) W Consequently, the transitive reduction of W i.e., Tr( Tr( may be used learn the directed edge Xx,X)).
(Note: E(g) denotes the edges of the graph G and π is any total order that is consistent with the partial order implied by the DAG, i.e. (X) < x (Y) iff is an ancestor of Y).
Assume that the number of the direct parents of X5 above X; is diy where d,j dman- Let (X,, be the following event: X,, X, & W & {W; : (W;) > (X;) & W. E Pa(X))) _ W. The probability of this event for one run of the outer loop in Algorithm 2 with the assumption that 2dmmaz
2 is given by:
1
(XE,
(1 2dmax
jou
(1
2dmar
(28)
4d 4ddnax
4dl max
2d
dmeox 16'
The last inequality holds for 2dmar >= 2 because (1 - 1 2 0.25, Vx 2 2. Based on Lemma
2
A.2 the event (Xx)) implies that the directed edge (5) will be present in Tr(g and will be learned. The outer loop runs for 8addmax log(n) iterations and elements of the set W are
W
independently sampled. The probability of failure, i.e., the event under consideration does not happen is bounded as follows:
for all runs of the outer loop in Algorithm 2
P((E((V)) <
1
Seadmaz log(n))
Idmar log(n)
(29)
16 d2 d2
n 3.
For graph with a total number of variables n, the total number of such bad events will be (2) since a graph can have at most (2) edges. Using the union bound, the probability of bad event for any pair of variables is given by:
P[Faiture] <
(30)
Idmas
71. 1.lhmouz
Under the event that Algorithm| learns the correct transitive closure Gle for all the 80dmax log n randomly sampled intervention sets W S V, the above derivation shows that we will be able to learn Now recall the result from Lemma 4.3 that Algorithm learns the true transitive closure under any intervention, i.e., Gw with K An + B intervention samples with a probability of least 1 nô1 82. Combining the two results above using the union bound, we have the following result:
all edges in the true observable graph with probability of least
Algorithm learns the true observable graph with a probability of at least
8oddmax log n1
(nuō + 52) with maximum 8od log no An + B) interventional samples. Also,
2dam log ( +2) 81 32ad logn' and 82 32adua log then Algorithm 2 learns the (2
we set a
log n
true observable graph with probability of at least 1 - 8. Where A = max
8
log 61
2nk² and
B log 2nk² This completes the proof of Theorem 4.1
82
A.11 Proof of Lemma 4.5}
Consider two nodes X; and X, s.t. X, & An(X,) and suppose that Assumptions 4.2 4.3 holds
and we have access to max( 8 8 7 log 2K samples from do(X; 2i, W w) Va, E [K] and
16 log( 2K² 2
6y + 1 log(" 2K? from do W = w) for fixed [K] wi and W C V such that
2n2
(Pa(X (a,))) U Pa(X)) (X,)) W and X, & X, & W. We want to show that, with probability at
least 1 81 6g Sq. we have the following:
21

---

There exists a latent confounder between X; and X, = D4 By E [K] s.t.
P(zy)do(z)), P(x, las, do(w)) |>
?
2
(31)
Using Hoeffddiggs inequality with A samples from intervention do(I;, w).
2K
51
P(æzldo(1:)) do(w)) (lzy)do(zi), do( do(w))) 2 V
log
w.p. at most
(32)
2A 81
K2*
If we choose A max( 22:
72) 61
8 2
log
we have:
P(ay [d((;;); dol(o)))do(w) P(zy)do(2z))
2 2 w.p. at most
81
(33)
K
Using Hoeffding's inequality with C' samples from intervention do(x;).
P(zz do(w)) - P(xylax do(w)) 2 V 2C2z 63
2k²
83
log
w.p. at most
(34)
K
Where Cn, is the number of samples where X; I, among the C' samples for the intervention do (w). Note the we can't It directly control Cz2, and it's value depends on the true interventions distribution
P(r;, do(w) along-with the number of samples C. Suppose if we can set Ca, 2 7 have:
& log 5s
2K
we
((,,l,;;dow))) P(x2 do do(w))
2 w.p. at most
83 K
(35)
4
We need to find the number of samples C such that Cs, 2 log we have:
8
2K 8g
Using the Hoeffding's s bound
72
P(C,, 2 CP(x;
do(w)) CP(x:)l((w) -1) 2 2e 202/0
(36)
Let 4 R²
= 221 10, which implies 11 /8 C log
2 8,
Thus we have:
2K²
54
P Cz, 2 CP(a))lo(w))
-
log
2
(37)
2
K2
2K² w.p. at least 1
84
2 222 CP(r:)lo(W))
log
(38)
K2
we have P(zyldo(w)) or P(z.ldo(w)) 2 n, Note that if P( ((x:)d(())) the event will never happen, and we don't 't care about the accuracy of the estimate P(x, ( do(w)) because it is already initialized to zero. Now the equation above can be rewritten as:
Using Assumption 4.3
C
2K
84
Co, 2 Cn
Cn-
log da
u.p. at least
(39)
2
K2
Since want Cz, 2
8 2k² 72 dg
log
with high probability, we have the following relationship:
22

---

C
2K
8
2K
Cn
V
2
log
d4
72
log
83
(40)
Solving the equation for number of samples C' we get:
477
log
In
2K 44
+
81)
8 log
26 bg
In
2
In
2
A4
C
(41)
41j2
In order to make the expression simpler we choose the number of samples C' as follows:
477
log
2x2
bg
+
2x²
+
STj
log
2x2
2K2 64
+
In2
2K2 44
+ (41)
log
2x
84
C
4np²
(42)
41
log
21c
In
2
+ V
4nj
8
log
2x2
b3
In
2K'
2
7-
de
7"
C
(43)
4172
log 2x3
+ In
2k
72a
84
C
(44)
2112
16
2K
2K
log(
+
log(
(45)
17?
83
277²
84
Suppose we take C' samples for intervention do(w) as given above. Now, from Equations 35 40 using the union bound, we have the following:
and
5g + 64
do(w)) P(zyl=,, do 2 w.p. at most
(46)
K
Since the realization w E [K] Wi is fixed, but Tj E [K]. we have total of K² possible bad events when estimates are not good. With the given choice of number of samples A and C, we have:
P(zy (oey)do(z;), do(w)) - P(z]]do(z;;
<
2 4
Vxy E [K] w.p. at least 1 - 81.
(47)
P(zyle;, do(w)) P(zylas,dol do(w)) S 7 Vx,, By E [K] w.p. at least 8z 84-
(48)
Under the good event, which has a probability of at least 81 - 53 - 5g, both estimates are accurate. We now consider the two possible scenarios. Suppose that there is no latent confounder
between X; and Xy. In this case by Lemma 4.2 we have P(æz)do(zz)) do(w)))((P))))
do(w)) =
0. Va,zy E [K]. By triangular inequality we have the following:
P(r,)do(zzs) (olldo)())ddo))))) do(w)) - P(ay ( do do(w))) S
P(x, (los))o(a;) do(w)) - P(æzldo(a=)) do(w))
P(z))2,,d((w) - P(x, do do(w))
S
Vx,, 2y [K]. (49)
23

---

However, when there is latent confounder between X; and Xy, in this case, under Assump- tion 4.2 we must have some configuration, say 24 E [K], for any E [K] such that P(æy)do(2z), do(w)) - P(zyla,, do(w))
By triangular inequality when there is a latent
confounder between X; and X,, 3 24, E [K] such that:
P(zyldo(xz), do(w)) - P(ay prs, do do(w)) 2 P(ay)lo((z)) - P(aj ( do(w))
-aadddd(www(j(/p/iaa ((ay)do((;)) dol - P(æg/do(z;)) do(w))
((t))l;,dd(w)) - (o,
7
(50)
Thus, using Assumption 4.2 with the given choice of number of samples with probability at least 1 81 83 54, we have the following result:
There exists a latent confounder between X; and Xj 4
Tg Fy E [K] s.t.
P(ayldo(z;)) - P(xx P(ayl2s, do(w)) |>
?
2
(51)
This completes the proof for Lemma 4.5
A.12 Proof of Theorem 4.2:
The Algorithm 3 first calls Algorithm 2 to learn the observable graph structure. We have already proved in Theorem 4.1 that Algorithm learns the true observable graph with a probability at least
Molasx 80dmax (og(n)(ná) + 02) with maximum of Sad log n K An B) interventional
samples. The next phase Algorithm 3 is to learn/detect latent confounders between any pair of variables. For all pairs of nodes X; and X, such that X2 & An(X;). we define
of nodes WH sy C V such that X,, & S,, where W sj = (Pa(X,) U Pa(X,) {X,}). Also, note that [Wij] S 2dmmxx Let us define the event Eij = (W C w & X, & W]. The probability of this event for one run of the outer loop in Algorithm with the assumption that 2d 2 2 is given by:
1 Wayl
P|Ey]
(1
(1
2d
(52)
4d max
2dman
4d2 maz
2d
mmax 16
The last inequality holds for dmax 2 2. Note that we reuse all the interventional data samples from Algorithm in Algorithm 3 Under Assumption 4.2 if the event Eij happens with large enough number of samples, we can detect the presence or absence latent confounders between X, and X,. The outer loop runs for Saddmax log(n) iterations, and the elements of the set W are independently sampled. The probability failure, i.e., the event under consideration does not happen for all runs of the outer loop in Algorithm is bounded as follows:
P 3 < (1 16 danax
Sadmax log(n) <
Bilmes log(n)
(53)
72 24man
For graph with a total number of variables n, the total number of such bad events will be (*) the union bound, the probability of bad event for any pair of variables is given by:
Using
P[Faiture] S
(54)
2dmmax
This implies with a probability of dataset to test the presence of latent confounders between any pair of variables using Assumption 4.2
we will be able to find an appropriate interventional

---

after running Algorithm2 2. We still need to make sure we have enough interventional samples to be able to test the latents. This is because we need accurately estimate conditional effects to carry out the test, as in Assumption 4.2 We first consider estimation of the causal effect ((zf)d(((;) (w)) for any randomly sampled set W. Now, consider fixed X,, X, E V W. We have access to & log 2nK² samples for every x; [K].
max ())
We have already shown that under the good
event, we have the following:
(oo))d)(z)) - P(ayldo(as), do(w)) S <min(
4' 3
Vo,, E [K], AX, E V W, VX, E V (W w.p. at least 1 - ndj
(55)
Now, we consider estimation of the conditional causal effects, i.e. ((z)))),dd(()). Note the while running the Algorithm we have access to B = 2² log 2nK² samples form intervention do(w) and in the step 7 of Algorithm 3 we add more samples to the data set and have access to at least
do(w)).
C= 16
2n*k² samples instead. Now, consider fixed X,, X; V W. ny² log( 2n K² ) + 2xy² log( 84
With access C samples as given above, following from Equation 48 in the Proof of Lemma 4.5 have the following result:
P(æylo,, do(w)) - P(xy lzs do(w))
? Vy E [K] w.p. at least 4
83 n²
54 n²
(56)
Note that in the above equation, we have f and f1 instead of 63 and ò₃ as in Equation 48 because here in the number of samples C, we also have 6g and by instead of d3 and ó4 when compared to the n²
n² number of samples in Equation 45] Now, using the union bound have the following:
P(aylz;, P(, do(w))
< 2
4
63
84
Vz,, Ty E [ XX, E V (WU w.p. at least 1
(57)
Again using the union bound over all X, V W we have the following:
P(zyldo do(xx), do(w)) ((z))dd((2)), do(w)) I Y
Y2,,2, [K], VX, E V W, VX, E EVE (WU w.p. at least - 83 - 84 (58)
This implies that under the good event, for every randomly sampled intervention set W C V, the estimate of the conditional causal effect is accurate within the desired threshold. This would imply that the test for detection of latent variables is perfect under this good event. We have already shown that to ensure we have access to sufficient datasets to detect latent variables between any pair of nodes, the Saddux log randomly sampled target sets in Algorithm 2 are sufficient. Combining these results with the results from Theorem 4.1 we have the following:
The Algorithm 3 learns the true causal graph along with all latents with a probability of at least
Sadman log(n)((ó) + log(n) + = 2ulmax
11 20max
Sumar
Sad log(n n (nd1 + (62 dz + 64)) with maximum Sadmas log n(K An max( B3, C') inter- ventional samples. Also If set 2dmax log ($ +2)
81 64admaz n log and 82 5g3 84
8
log
5 Biadmma logn' then Algorithm learns the true causal graph with latents with probability at least 1 1-8.
Note that: A max 22: log
2nk² B 3u log 82
2n
-
16 log( 62 }
2K
1 log( 2K"
8a ). This
51
2n
completes the proof for Theorem 4.2
25

---

Algorithm 6: Full version of Algorithm for causal bandits with unknown graph structure
Set the Parameter 6, dmax Calculate a, 11, 62, 63. d as in Theorem 5.1
g Learn TranstivvvoeveessuueeWWWWW
(2 2n n
G, = LeannOsseaaaaalGraahi
=
gmr, a, d 81, 01)
5 C' =
'/> log(
16
+ Zn log( 2n 2n²x²) B z²
8
log 52
2nk
51 # Learn the bi-directed edges between reward Y and all nodes X; E An(Y) and update G.
7 for every X; E An(Y) do
Set X; := Y
Find interventional data sets dW = w) and do(X; = Zú. W w) from IData s.t. (Pa(X,) Pa(X;) \ {X,)) W and X₃ & Xy W
10
Get max(0, B C)) new samples for do( W w)
if WiyTy Ty [K] s.l. [P(r,Ido(aaa) [d((;;) do(w)) P P(ryl do(w)) then
12
L
Add bi-dirceted edge X; + Xy to graph g
13
while There is new pair that is tested do
14
Find a new pair (Z, X) s.t. Z AY)) such that and Y don't have bi-directed edge between them in G and X E (2))) Y)
15
# Test for the latent between the pair (Z, X) and update
16
Set X; = Z. Z, X
17
if X, E An(X.) swap them.
18
Find interventional data sets do = w) and do(X; Fz, W w) from IDala s.t. (P,) Pa(X,) \ (x.)) C and X; & X; $ W Get max(0, B C)) new samples for do(W- = [do(z;), do(w)) P(zylæ,, do(w)) Add bi-directed edge X, + X3 to graph g
20
if 24 T E [K] s.t. ((,,,ld((;,)
7 then
L
Learn the of POMISS Zς from the graph Using Algorithm I in Run UCB algorithm over the arm set A {N(I) VI E Iz).
23
A.13 Full Version of Algorithm 4 and Proof of Theorem 5.1
Algorithm orr its full version (Algorithm 6 starts by learning the transitive closure of the graph. denoted as n This is because g can give us An(Y), and every possible POMIS is a subset of An(Y). Thus, we can restrict ourselves to ancestors of the read node. From Lemma 4.4 we can learn the transitive closure G with probability of at least 1 - 8 with a maximum of K An + B interventional samples by setting 61 = á and 82 = &. Then, Algorithm learns the true transitive
2n
closure with a probability of at least 1 - 8. (We have A = max
2nK2 log 51 and B
log 2n 5g to be Knmax 2
as in line 2 of Algorithm Thus, the total interventional samples for this step turn out
log
K2 + log 1nk? 6
The next step is learn the complete observable graph induced on the reward node and its ancestors and then learn/detect only subset of latent confounders which are characterized to be necessary and sufficient learn the true set of POMISs (Theorem 3.1. Although this step saves us interventional samples compared to the full discovery Algorithm which learns/detects latents between all pairs of variables, the exact saving will depend on the structure of the underlying causal graph. For the regret upper bound, we use the results from Theorem 4.2 to bound the number of interventional samples for learning the true POMIS set from the ancestors of the reward node. This implies that given the true set of ancestors of the reward An(Y), we can learn the true POMIS set with probability of
at least
K (Y))n(Y) + B) log (|An(Y)) interventions, where A and B are å using Seddax
given by line 2 of Algorithm
and C is given by line 3 of Algorithm by setting 2d log ( +2) log An(Y')
61 6Andam An(Y) log An(Y)
and d2 83 84
Gdccdoess log An(Y))
26

---

The last phase is just running the UCB algorithm over the set of all possibly optimal arms, i.e., log T 1+
A (Q(I) TA }o}. This phase has a regret bound of (x Ado(s)
do(a)
26 Now combining all the results we have the following:
Algorithm @goorthmm]leamm learns the true set of POMISS Ig with probability at least 6- 26, and under the good event E that it learns POMISs correctly, the cumulative regret is bounded as follows:
8
4n K2
4nK²
P₂ Kn max
log
log
2 72
8
(59)
8admaz KA|An(Y)) max(B, C1) log (AAn(Y))
E
do(s)
1+
log T
A dx(s))
SE(D(]]VIEZs>
where A and B are given by line 2 of Algorithm ! and C' is given by line 3 of Algorithm 3 by setting
2dmux log ( 81 64admar An(Y)
and d2 = 03 = 54
This
log Yy(Y) completes the proof of the Theorem 5.1
log An(Y)
64admaz log An(X)
A.14 Comparison with SCM-based Approximate Allocation Matching Algorithm from [6]:
Our proposed algorithm, Algorithm| 4 consists two phases. The first phase uses interventional samples to learn the set of POMISs, and the second phase uses the UCB algorithm to find the optimal arm among the POMISs. Note that in the second phase, we use the UCB algorithm, which assumes that arms are independent of one another. However, in the case of causal bandits, the arms are correlated, and every intervention provides some information about other interventions. The UCB algorithm cannot exploit this information. However, [6] proposes algorithm exploit the correlations between arms in a causal bandit setting, which accelerates the learning compared to the simple UCB algorithm. The main limitation is that the algorithm requires access the true causal graph. Therefore, it is possible that we can use an alternative approach where instead of POMISs, we learn the entire causal graph and then use the SCM-based Approximate Allocation Matching Algorithm from [6] for our problem setup. This approach can also allow us to reuse the intervention samples from the discovery phase to accelerate the next phase. However, the main drawback of this approach is that the algorithm proposed in [6] faces issues when it comes to larger, densely connected causal graphs. We explain the reasoning of our claim by reviewing some concepts from the paper 6
In order to exploit the correlations between different arms in a causal bandit setting, the authors in (6) rely response variable formulation for causal effects, which we discuss very briefly here. For any causal graph G, the observed variables V can be uniquely partitioned into c- components C², ...,... C"v(9), Consider a set of response variables M, which we also partition into M ( where each MD contains response variables corresponding to every observed variable in the corresponding c-component C³, Within c-component, the response variables of all the observed variables are correlated since they are connected by bidirected edges. However, across two c-components, the response variables are independent. As a result, P(m) = IT,=()) P(m)). By concatenating P(m') for each m E S(ML), one can construct a vector py E ((2(()) where {[ denotes the probability simplex over the discrete domain R(M)). Let the parent set of c-component Ci be Pac: == (Ueyecs Pa:) C), When taking intervention do(S = s), the values of C' n S are set to s(C*). which denotes the values of C S that are consistent with s. M' picks the mapping functions from Pa, to V, for all V/2 E C². By marking configurations in Bg., ( (C pac;) S ((M)) with I and 0, one constructs vector
bg,s(c:) (C), pacc)) E (0. (R(M)) such that:
n_(G)
mc(()
Pl(v)
II P(M' E (C = II j=1
( (C', pPp.p j=1
(60)
The equation 60 is very useful since it enables us to exploit the correlations between different interventions in the causal bandit setting. This is because every interventional distribution can be
27

---

written as a deterministic linear function of the response variable distribution. Thus, it is possible that using the response variable decomposition. we can reuse the samples from discovery into the next phase and accelerate learning of the optimal arm. However, we need to discuss the scalability of this approach. Note that every variable in the SCM can take values from the set [K], and in total, there could be K different realizations for Vj for every realization of its parents Pa(V)).
As a result, there are a total of k=K possible mappings from Pa(V;) to Vj- Also, note that within c-component, the response variables for every observed variable are correlated. This implies that for every component CV, the corresponding response variable M has the domain (Q(P)) IIv, K Thus, every vector Py will have a total of Iv, K*K PA(V) components. Although the response variable decomposition is useful for smaller and sparse causal graphs, the scaling for the length of vectors Pj is clearly exponential, making the use of response variable decomposition infeasible for larger or denser causal graphs. All in all, there are correlations between different arms in causal bandits, but it is not clear how exploit them effectively, especially for larger and denser causal graphs, which is still an open problem.
A.15 Experimental Compute Resources and Runtime
We ran our experiments
server equipped with the AMD Ryzen Threadripper PRO 5995WX CPU, which has 64 cores and 128 threads, with a base clock speed of 2.7 GHz and maximum boost clock speed of 4.5 GHz, along with 128 GB of RAM. The total runtime for the experimental plots in Figures 2 and 3 is around hours. For the experimental plots in Figure 4 the total runtime is around the full algorithm for multiple randomly sampled graphs.
2 hours for each subplot since
A.16 Broader Impacts of our Work
This paper presents work with the goal of advancing the field of Machine Learning. Since the causal bandit framework can be used to model real-life eeciiiionmmainn scenarios, there are some potential societal consequences of our work. The possibility of biased or incomplete understanding of causal relationships could lead to misguided decision-makinn makinn policy recommendations in real-worle situations. Thus, extra care and consideration ethical boundaries regarding actions/interventions needed while applying our proposed methodology to practical problems.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction clearly reflect the paper's contributions, and provide a list of main contributions at the end of the introduction as well.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Our paper clearly discusses all the limitations and assumptions in sections 2
and
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: All the theorems and lemmas in our paper are properly numbered, and formal proofs are provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide detailed explanation of our experiments in section and also provide the code with instructions to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have uploaded the code along with the instructions to reproduce the results in our experiments section.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccppbllcgggudeeeeeeeeeeee Coaee//dddeSebmmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all the details about our experimental setting in section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We plot the error bars as part of the experimental results section 6 and also mention the method used calculate them.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
31

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide all the information on computer resources and runtime for our experiments in section A.15 A.15
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps:://eurips.cc///bb//// htwp:/ubllcc/tthehuuuueeeeeeleed
Answer: [Yes]
Justification: We have looked at the NeurlPS code of ethics, and we believe there are no potential harms caused by the research or potential future harmful consequences for our work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss possible broader impacts of our work in section A.16
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
32

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: We mainly conduct synthetic experiments in our work, and we don't 't see any risk of misuse of our code.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our experiments purely synthetic in nature, and we don't 't use any datasets or models that require licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We don't ' create new assets in our work, and the main contributions of our work lie predominantly on the theoretical side.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We don't 't require any approval since our work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
34

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "AKgdO14DV7", "reviewer": "Reviewer_MSdE", "summary": "This paper ooks into the problem of causal bandits without graph information and with unobserved variables. The paper presents both graph learning algorithms and causal bandit algorithms.", "questions": "- How is transitive reduction computed in Algorithm 2? Does it need to exhaust all possible sub-graphs?\n\n- Correct me if I am wrong: In Assumption 4.1 and Assumption 4.2, the assumption is made for **any** $\\mathbf{w}\\in [K]^{\\mathbf{W}}$, which is stronger than the other causal bandit papers, e.g. [7], [9].\n\n- For Algorithm 3, line 4, how is the set $\\mathbf{W}$ determined as it is neither an input nor the output of LearnObservableGraph? Te $\\mathbf{W}$ matrices in $\\mathcal{I}Data$ does not share the same $\\mathbf{W}$, and and line 6 seems to attempt to find $\\mathbf{W}$.", "limitations": "The paper assumes semi-Markovian causal models and stronger identification assumptions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper tackles the novel problem of causal bandits (CB) with unknown graphs and unobserved variables. Theorem 3.1 is particularly interesting, and the use of a randomized algorithm to sample-efficiently learn the causal graphs is notable.", "weaknesses": "There are a few typos in the paper:\n- For the definition of transitive reduction, does it force $\\mathcal{G}$ to be connected? Otherwise, the empty edge set is minimum.\n\n- For the d-separation defined in line 119, shouldn't it condition on $\\mathbf{W}$?\n\n- Assumption 2.1 is defined on a mixture of hard intervention and stochastic intervention (in line 126)?\n\n- Line 4 in Algorithm 2, should it be $\\mathcal{W}=\\emptyset$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed review and comments. Below we address the reviewer’s concerns:\n\n**Transitive reduction forces $\\mathcal{G}$  to be connected?**\n\nTransitive reduction of a DAG $\\mathcal{G}$ is another DAG with the same transitive closure as  $\\mathcal{G}$ but with the least number of edges. The transitive closure of $\\mathcal{G}$ is another DAG $\\mathcal{G}^{tc}$, where a directed edge $ V_i \\rightarrow V_j $ is included in $\\mathcal{G}^{tc}$ iff $ V_i \\in \\mathsf{An}(V_j) $ (as defined in line 112). The definition does not restrict $\\mathcal{G}$ to be connected. The transitive reduction will be an empty edge set iff $\\mathcal{G}$ itself has no edges, because the transitive reduction must have the same transitive closure as $\\mathcal{G}$.\n\n**d-separation in line 119, shouldn't it condition on $\\mathbf{W}$ ?**\n**Line 4 in Alg. 2, should be $\\mathbf{W} = \\phi$.**\n\nApologies for the typos in line 119 and Algorithm 2; we will fix them\n\n\n**How is transitive reduction computed?**\n\n\nWe use a polynomial time $ O(poly(n)) $ algorithm from  [1] . In Line 227 we cite this paper and recall the results from Theorem 1 and Theorem 3: The transitive reduction of a DAG is unique and can be computed in polynomial time. Specifically, Theorem 3  provides a polynomial-time algorithm to compute transitive reduction using polynomial-time algorithms to find the transitive closure, such as the Floyd-Warshall algorithm having  complexity of $ O(poly(n)) $. We will clarify this in Algorithm 2 as well.\n\n\n**[1]** *Alfred V. Aho, Michael R Garey, and Jeffrey D. Ullman. The transitive reduction of a directed\ngraph. SIAM Journal on Computing, 1972.*\n\n\n\n**Algorithm 3, line 4, how is the set $\\mathbf{W}$  determined, and line 6  attempts to find $\\mathbf{W}$ in $\\mathcal{I}Data$:**\n\n\nWe apologize, there is a typo in line 4 of Algorithm 3. It should only be: (For all pairs $V_i, V_j \\in \\mathbf{V}$) without any mention of $\\mathbf{W}$. Later on, we attempt to find interventional samples for some suitable $\\mathbf{W}$ in $\\mathcal{I}\\text{Data}$ where $\\mathbf{W}$ is the union of parent sets of $V_i$ and $V_j$ excluding $V_i$ itself. Note that in the proof of Theorem 2, we show that such target $\\mathbf{W}$ for any pair of nodes will be selected in Algorithm 2 that is generating $\\mathcal{I}\\text{Data}$ with high probability (for details refer to Section A.12). We will fix the typo in revised manuscript and clarify it further in revised manuscript.\n\n**Assumption 2.1 is defined on a mixture of hard intervention and stochastic intervention?**\n**In Assumption 4.1 and Assumption 4.2, the assumption is made for any \n$\\mathbf{w} \\in [K]^{|\\mathbf{W}|}$, which is stronger than [7], [9]?**\n\n\nWe will address the reviewer’s concerns regarding Assumptions 2.1, 4.1, and 4.2 together. Assumption 2.1 is the main assumption in the paper. Using Assumption 2.1, we state and prove two lemmas, 4.1 and 4.2, which can be used to detect ancestral relationships and the existence of confounders, respectively. To provide theoretical guarantees on sampling complexity, the inequality conditions in the lemmas alone are not sufficient. Therefore, we introduce gaps $\\epsilon$ and $\\gamma$ in Assumptions 4.1 and 4.2, using the results from Lemmas 4.1 and 4.2.\n\n\nWe thank the reviewer for highlighting the point that Assumption 2.1 uses a mixture of hard and stochastic interventions. This can, in fact, be simplified by using only stochastic interventions instead. Consider a set of nodes $\\mathbf{W} \\subset \\mathbf{V}$ and the stochastic intervention $do(\\mathbf{W}, \\mathbf{U})$ on $\\mathbf{W}$ and any set $\\mathbf{U} \\subseteq \\mathbf{V} \\setminus \\mathbf{W}$. The conditional independence (CI) statement $(\\mathbf{X} \\perp \\mathbf{Y} \\mid \\mathbf{Z}){\\small{\\mathcal{M}}\\tiny{{\\mathbf{W}, \\mathbf{U}}}}$ holds in the induced model if and only if there is a corresponding $d$-separation statement in post-interventional graph $(\\mathbf{X} \\perp_{d} \\mathbf{Y} \\mid \\mathbf{Z}){\\small{\\mathcal{G}}\\tiny{{\\overline{\\mathbf{W}, \\mathbf{U}}}}}$ , where $\\mathbf{X}$, $\\mathbf{Y}$, and $\\mathbf{Z}$ are disjoint subsets of $\\mathbf{V} \\setminus \\mathbf{W}$. The CI statements are with respect to the post-interventional joint probability distribution. Assumption 2.1 is similar to the post-interventional faithfulness assumption used in the causality literature [1-3]. The difference pointed out by the reviewer between our Lemmas and Assumptions 4.1 and 4.2 compared to those in [7] and [9] stems from the post-interventional faithfulness Assumption 2.1.\n\nIn [7], the reward node has only one parent, and the action space consists of single-node interventions. On the other hand, the regret bound in [9] includes a term with a factor of $ K^{|\\text{Pa}(Y)|} $, which implies that the number of samples needed during the learning phase of the algorithm might grow exponentially with the number of nodes if the reward node has a large number of parents. In contrast, our regret bound has polynomial scaling with respect to the number of nodes in the graph.\n\n\n**[1]** *Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal networks\nfrom interventional data. In Proceedings of Sixth European Workshop on Probabilistic Graphical\nModels, 2012*\n\n**[2]**  *Wang, T.Z., Wu, X.Z., Huang, S.J. and Zhou, Z.H., 2020, November. Cost-effectively identifying causal effects when only response variable is observable. In International Conference on Machine Learning (pp. 10060-10069). PMLR*.\n\n**[3]**  *Kocaoglu, M., Shanmugam, K. and Bareinboim, E., 2017. Experimental design for learning causal graphs with latent variables. Advances in Neural Information Processing Systems*\n\n\nWe hope our response has clarified the reviewer's concerns and respectfully request that they reconsider their evaluation in light of our response. We would be more than pleased to engage in further discussion if the reviewer has any additional concerns or questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RwyJd6kYyi", "reviewer": "Reviewer_VRJg", "summary": "The authors extend the methodology in Lee and Bareinboim [2018] (L&B) for regret minimisation in a causal bandit setting with initially unknown causal structure and possible latent confounding. They identify the necessary and sufficient structural knowledge of latent confounding to identify possibly optimal minimal intervention sets (POMISs), given full knowledge of the observed causal graph, under similar modelling assumptions to L&B. \n\nWhile the conditions do not improve the number of test interventions needed in worst-case scenario, they can offer super-exponential speedup in other scenarios. The authors provide a finite sample POMIS-discovery algorithm with coverage guarantees of the true set of POMISs and derive regret upper bounds. Experiments, particularly figure 2, show a clear (regret) advantage over learning all latent confounders in a setting with random, triangulated DAGs.", "questions": "(Latent structure assumption) What is the role of the assumed structure on latent confounding in your results and how restrictive actually are these assumptions? Can these assumptions be relaxed to some degree, say if latent confounders are allowed to confound up to n (e.g., 3) observed variables, or have bounded pairwise correlation? Is it permitted for three vertices $(V_1, V_2, V_3)$ to be confounded pairwise, i.e., for confounding between $(V_1, V_2)$, $(V_2,V_3)$ and $(V_1, V_3)$?\n\nAre the graphs generated for the simulation experiments - i.e., after triangulation - typically dense or sparse? Is this an important factor to understand the advantage of your method over learning all latent confounders? Perhaps a parameter sweep over $\\rho$ and $\\rho_L$, i.e., a property of the observed versus unobserved graphs, could be informative to this end. Was the triangulated structure of the observed graph important for your results?", "limitations": "Yes - the authors state all underlying assumptions of their model. I would like to understand whether the latent structure assumption is limiting for real-world applications.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The authors present their contributions clearly, logically covering their motivation, theoretical results, algorithmic design, coverage guarantees, regret upper bounds, experimental design and experimental results. It is clear how their approach works in conjunction with other stages such as learning the observable graph and regret minimisation with the full set of POMISs. \n\nExperiments convincingly show the advantage of partial structure discovery over testing for all latent confounding in a class of random DAGs.", "weaknesses": "(Latent structure assumption) A key modelling assumption, retained from L&B, is that latent variables are mutually independent and confound only a pair of measured variables each. This modelling assumption (why is it necessary? how restrictive is it mathematically? in what real-world setting could it be relevant?) was not sufficiently explored in L&B or by the authors. The assumption is especially relevant to the impact of the authors' contributions so should be discussed more thoroughly in the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed review and comments. Below we address the reviewer’s concerns:\n\n**(Latent structure assumption)  Role and how restrictive it is? Can these assumptions be relaxed , say if latent confounders are allowed to confound up to n (e.g., 3) observed variables, or have bounded pairwise correlation? Can three vertices   to be confounded pairwise?**\n\nThe latent structure assumption we are using, also known as the semi-Markovian assumption, is widely used in the causality literature, including in L\\&B (additional references are provided at the end). We will briefly explain how general this assumption is.\n\nAn SCM (Structural Causal Model) consists of a set of equations of the form $ X_i = f_i(\\text{Pa}(X_i), U_i) $, where $ U_i $ are the exogenous noise variables. If the noise variables are independent, the model is Markovian. However, when exogenous noise variables are dependent, we have a broader class of models which are not Markovian. These are called semi-Markovian causal models. For instance, if exogenous variables $ U_i $ and $ U_j $ are dependent, we say $ X_i $ and $ X_j $ are confounded. We assume the underlying SCM for the causal bandit problem is semi-Markovian, which entails a specific latent structure: the latent variables are root nodes with no parents and can have at most two observed variables as children. A latent variable with two observed children implies that the observed variables have a latent confounder between them.\n\n\nComing to the second part of the question: The semi-Markovian assumption allows for pairwise confounding between any pair of observed variables. The main restriction is that one exogenous variable, for instance, one latent variable $ L $, cannot be the parent of three or more observed variables $ v_1, v_2, v_3, \\ldots $. However, one can map this non-Markovian example to a Markovian model by assuming pairwise confounding between the nodes. Also, if one decides to run the algorithm, they would detect that these variables have pairwise confounders. The characterization of possibly optimal arms (POMISs) in the paper by L\\&B is based on the assumption that the underlying causal model is semi-Markovian because they use existing identifiability results for semi-Markovian causal models. Our algorithm builds upon their results. A general extension of this work to non-Markovian models and the implications of violating the semi-Markovian assumption remain future work for us. Overall, we agree with the reviewer that it is essential to highlight this assumption and its implications in the revised manuscript.\n\n\n**[1]** *Pearl, J., 2009. Causality. Cambridge university press.*\n\n**[2]** *Tian, J. and Pearl, J., 2002, August. A general identification condition for causal effects. In Aaai/iaai (pp. 567-573).*\n\n**[3]** *Bareinboim, E., Correa, J.D., Ibeling, D. and Icard, T., 2022. On Pearl’s hierarchy and the foundations of causal inference. In Probabilistic and causal inference: the works of judea pearl (pp. 507-556).*\n\n**[4]** *Meganck, S., Maes, S., Leray, P., Manderick, B., Rouen, I.N.S.A. and St Etienne du Rouvray, F., 2006. Learning Semi-Markovian Causal Models using Experiments. In Probabilistic Graphical Models (pp. 195-206).*\n\n\n**Are the graphs generated after triangulation - typically dense or sparse? Is this an important factor to understand the advantage of over learning all latent confounders? Perhaps a parameter sweep over $\\rho$ and $\\rho_L$\n could be informative to this end.**\n\nIn the process of chordalization or triangulation, additional edges are added to make the observed graph structure chordal, which generally makes observable graphs a little denser. There are two density parameters: $\\rho$, which controls the density of the observable graph, and $\\rho_L$, which controls the density of latent confounders. Specifically, after sampling the observable graph, we add latents between pairs of observed variables with a probability of $\\rho_L$. While the triangulation makes the observable graph somewhat denser, it does not play a major role in our simulation studies and is optional.\n\nThe main idea we are trying to show through simulations is the advantage of partial discovery over full discovery for the causal bandit problem with an unknown graph.  We agree with the reviewer that a parameter sweep for different values of the density parameters $\\rho$ and $\\rho_L$ can be useful in our simulation section. In fact, we have shown the effect of a parameter sweep in our results in Section A.14 of the supplementary material. We set the variables $\\rho$ and $\\rho_L$ to values $0.2, 0.4, 0.6$ and plotted a grid with results for all 9 possible combinations. The main conclusion was that the advantage we get with partial discovery over full discovery mainly depends on the latent density parameter $\\rho_L$, and it reduces as we increase $\\rho_L$ from $0.2$ to $0.6$. The trend remains consistent across different values of the observable graph density parameter $\\rho$. We did not include these plots in the main paper due to space constraints, but we will move them to the camera-ready version using the extra content page.\n\nWe hope our response has clarified the reviewer's concerns and respectfully request that they reconsider their evaluation in light of our response. We would be more than pleased to engage in further discussion if the reviewer has any additional concerns or questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DBnX1TM6hh", "reviewer": "Reviewer_FQKc", "summary": "The paper addresses causal bandits problem without prior knowledge of causal graph and in the presence of latent variables. Previous work shows that the best possible interventions form a set known as POMISs. The paper theoretically demonstrates that a partial discovery of the causal graph is sufficient to find POMISs.\nTo tackle the main problem, the authors propose a randomized algorithm to identify POMISs without complete discovery and then use the UCB algorithm on the candidate set.", "questions": "Could you discuss the points mentioned above?\n\n1- The algorithms (e.g., Algorithm 4.1) are using the values in assumptions 4.1 and 4.2. How is it possible to access this information?\n\n2- How do you compare your algorithm (the regret bound) with a naive algorithm that blindly iterates over all possible interventions? Is it possible the latter performs better than your algorithm? If yes, which types of graphs do have this property? (I read Section A.15)\n\n3- In algorithm 2, for each iteration, Should not set $W = \\emptyset$?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1- The paper considers an important problem in the causal bandits area, in which the graph is unknown and latent variables exist. \n\n2- To find optimal candidate interventions (POMISs) the paper demonstrated that a partial discovery of the main causal graph is sufficient. (Theorem 3.1)\n\n3- A two-phased algorithm has been proposed for solving the causal bandit by providing a precise theoretical analysis.", "weaknesses": "1- The proposed regret bound can become very large when either $\\epsilon$ or $\\gamma$ is small, which is a possible scenario.\n\n2- It’s not clear whether the proposed algorithm and upper is optimal or not. No discussion has been provided.\n\n3- There is not any discussion regarding the running time of algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed review and comments. Below we address the reviewer’s concerns:\n\n**Proposed regret bound can become very large when  $\\epsilon$  , $\\gamma$  is small. How is it possible to know  $\\epsilon$\n , $\\gamma$ in-advance?**\n\nWe agree with the reviewer that the regret bound depends on $\\epsilon$ and $\\gamma$. However, in the context of causal bandits, the main emphasis is ensuring that regret is sublinear in rounds and does not grow exponentially with the size of the problem instance, which is the number of nodes $n$ in the graph. Also, $\\epsilon$ and $\\gamma$ are constants which do not have any dependence on the number of rounds or nodes in the graph. Such gaps parameters are fundamental, as there is no way around them. When these gaps are small, any statistical independent test would require a large number of samples for reliable conclusions.\n\nIn the introduction section, we discuss that the majority of existing work on causal bandits assumes the causal graph is known, which can be unrealistic in many practical applications. This is due to the challenges associated with sample-efficient causal discovery with theoretical guarantees. The previous two papers we discuss, which deal with causal bandits with an unknown graph, are Lu et al. (2021) (cited as [7]) and Konobeev et al. (2023) (cited as [9]). Both papers also have gap assumptions, such as assumption 2 and assumption 3 in Lu et al. (2021), and assumption 4.1 and 4.2 in Konobeev et al. The novelty of our work is that both papers assume causal sufficiency and do not allow for the presence of confounders. Additionally, the regret bounds in both papers have similar scaling with respect to gap parameters.\n\nOur algorithm indeed requires access to the gap parameters $\\epsilon$ and $\\gamma$, similar to the approaches in [7] and [9]. If these parameters are unknown in practice, one possible solution is to start with some suitable initial values for the gap parameters. Then, you can alternate between the learning phase and the UCB phase, gradually adjusting the values of the gap parameters until a required performance criterion is met.\n\n**On optimality of proposed algorithm and regret bound:**\n\nThere is prior work on lower bounds and optimality analysis for causal bandits with known graphs. However, **with unknown graphs**—especially when **latent confounders** are present—**lower bounds or optimality analysis** remains an **open problem**. This is because causal discovery is required as part of the solution; without graph learning, one must consider interventions on all possible subsets of nodes. Additionally, finite sample discovery for causal graphs with confounders, along with theoretical guarantees, is still an open problem. Our randomized algorithm makes progress toward addressing this under mild assumptions. Overall, optimal analysis for the learning phase of our proposed algorithm and its upper bound remains a topic for future work.\n \n**On Run time of algorithms:**\n\nWe provide details about computational resources and runtime for our simulations in supplementary material, section A.17. Asymptotically, our full bandit algorithm has polynomial runtime complexity, i.e., $O(\\text{poly}(n))$, where $n$ represents the number of nodes in the causal bandits problem. However, please note that the runtime reported in A.17 is larger because it accounts for the total time across multiple randomly sampled graphs with varying numbers of nodes. We will include discussion on the runtime complexity of our algorithm in revised manuscript.\n\n\n**Algorithm 2, for each iteration, Should not set $\\mathbf{W} = \\phi$?**\n\nThere is a typo on line 4; it should be $\\mathbf{W} = \\phi$. We set $\\mathbf{W} = \\phi$ for every iteration of the outer loop, and then the target set $\\mathbf{W}$ is randomly sampled for each iteration of the outer loop. At every iteration, Algorithm 2 calls Algorithm 1 to compute the transitive closure of the post-intervention graph $\\mathcal{G}^{tc}_{\\overline{\\mathbf{W}}}$ and finally accumulates all edges found in the transitive reduction of post-interventional graphs across all iterations of the outer loop.\n\n**On comparison with  naive algorithm that blindly iterates over all possible interventions? Can it outperform our Algorithm?**\n\nThe key feature of our regret bound is that it is sublinear in the number of rounds and has polynomial scaling with respect to the number of nodes $n$ in the graph. In comparison to a naive algorithm that intervenes on all possible subsets of nodes using any bandit algorithm, we at least have to play each arm once. For instance, if the causal graph has $n$ nodes, there will be\n$ \\sum_{i=1}^{n} \\binom{n}{i} K^i = (K+1)^n\n$ different possible arms/interventions, where $K$ is the number of different possible values each node can take. The advantage of sample-efficient discovery is that it helps us reduce the action space before applying the UCB algorithm. We have already included this discussion in the paper on lines 311 to 313.\n\nIn our simulations, we show that once the number of nodes exceeds a certain number, around 17 or so, the number of arms for the naive algorithm grows much larger than our regret bound, as shown in the plot in Fig. 3. This is because the number of arms for a naive algorithm scales exponentially with the number of nodes $n$, whereas our regret bound has polynomial scaling with respect to $n$. The naive algorithm may perform better than our solution for graphs with a small number of nodes; however, as the number of nodes grows, it will not even be feasible to run the naive algorithm that does not consider causal information because of the exponential size of the action space. \n\n\nWe hope our response has clarified the reviewer's concerns and respectfully request that they reconsider their evaluation in light of our response. We would be more than pleased to engage in further discussion if the reviewer has any additional concerns or questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper reports a study on causal bandits with unknown causal graphs and latent confounders. It is an extension of the prior work by Lee and Bareinboim [5], who only considered the case of known causal graphs. The reviewers show positive support to the paper, acknowledging the contribution and importance of studying the causal bandits when the causal graphs are unknown and when there are latent confounders. Overall, I agree with the reviewers on the positive contribution of the paper elevating the research to the unknown causal graph case, and in particular, the results in Section 3 and 4 are interesting. However, during the final stage when I gave a check on the paper, I did find an issue concerning a claim of the paper that the regret bound is polynomial in the graph size $n$. This leads to some further discussions among the reviewers. After the discussion, we decided that the paper is worth an acceptance as the poster, but the authors have to remove this incorrect claim and thoroughly revise the paper.

The following is the detailed description of the issue:

The last sentence of the abstract make the following claim:

"We also establish regret bound for our two-phase approach, which is sublinear in the number of rounds and has polynomial scaling with respect to the number of nodes in the graph."

The authors also repeated this claim about polynomial dependency of the regret bound on the graph size several times in the rebuttal, to argue that they are better than the naive use of UCB directly without the causal discovery part, since the naive use of UCB will have the number of arms in the scale of $O(K^n)$ where $K$ is the number of possible values each variable can take, and $n$ is the number of observable variables in the causal graph.

But what they did is to find all possibly optimal minimum intervention sets (POMISs), following the work of [5]. It reduces significantly the number of possible intervention to explore, but it is unclear that it would reduce this number to a polynomial in $n$. Let the size of largest POMIS set is $P$ and the number of POMIS set is $Q$, the total number of arms for the MAB problem is $O(Q K^P)$. This can also be seen from the regret bound in Theorem 5.1: the last term needs to enumerate through all POMIS set $I$ in $\mathcal{I}_{\mathcal{G}}$, and for each $I$, it needs to enumerate through all value combinations of $I$, namely $\Omega(I)$. So it is exponential in $P$, and $Q$ could also be exponential. Unless the authors can claim that $P$ is a constant or $\log n$ term, and $Q$ is a polynomial in $n$, I don't think the authors can claim that their regret bound is polynomial in $n$. In fact it certainly exists some cases in which the possible enumeration above is exponential. I do not see any discussion in the paper or in the rebuttal about this fact, and there is no technical discussions on when the above number could be polynomial. 

Another hint is from Figure 3 and 6 of the paper. The figure shows that the enumeration of all possible interventions is clear bad. However, looking at the enumeration of all possible interventions within the POMIS set, it is still like a linear curve with a small slope. But given that the x-axis is in linear scale while the y-axis is in log scale, I think it still indicates that the total number of enumerations for POMISs is exponential in $n$. 

After some discussion with the reviewers, we believe that the claim that the regret bound has polynomial scaling to the graph size is incorrect and the authors should remove this claim from the paper. But the other contributions of the paper is strong enough to warrant the acceptance of the paper as a poster in NeurIPS.
Decision: Accept (poster)