Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits

Authors: muhammad qasim elahi
mahsa  ghasemi
murat  kocaoglu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:33:40

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.

Main paper: 
 introduction: 
 Causal bandits have been a topic of interest since their inception and have been studied in various contexts [1] . The authors assumed precise knowledge of the causal graph and the impact of interventions or actions on the parents of the reward node. Subsequently, there has been a flurry of research on causal bandits [2, 3, 4] . The primary limitation of the majority of existing works on causal bandits is their assumption of full knowledge of the causal graph, which is often impractical for many 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 a 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 a true separating set is known. The paper by Konobeev et al. [9] also deals with causal bandits with an unknown graph and proposes a two-phase approach. The first phase uses a 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 [7] , 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 a 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 [9] , 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, we 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 a well-studied problem and can be applied to our setup [11, 12, 13] . However, the majority of the existing causal discovery algorithms rely on the availability of an infinite amount of interventional data [14, 15, 16] . Some prior work shows that discovery is possible with limited interventional data, with theoretical guarantees when the underlying causal graph is a 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 a two-stage approach where the first step learns a subgraph of the underlying causal graph to construct a 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 a 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 a 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 a 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 an upper bound on the cumulative regret of the overall algorithm.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 we 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 in 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 as long as it is clear that these goals are not attained by the paper. 
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 M = ⟨V, U, F, P (U)⟩ where V = {V i } n i=1 ∪ {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 f i map the parents (Pa(V i )) and a subset of exogenous variables U i ⊆ U, to the value of variable V i , i.e., V i = f i (Pa(V i ), U i ). We consider the causal bandit setup where all the observed variables V i ∈ V are discrete with the domain Ω(V i ) = [K] := {1, 2, 3, . . . , K}, and the reward Y is binary, i.e., Ω(Y ) = {0, 1}. We can associate a DAG G = (V, E) with every SCM, where the vertices V correspond to the observed variables and edges E consist of directed edges V i → V j when V i ∈ Pa(V j ) and bi-directed edges between V i and V j (V i ← → V j ) 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 [10] . An intervention on a set of variables W ⊆ V, denoted by do(W), induces a post-interventional DAG (G W ) 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 a fixed realization we have W ∼ P(.), where P is a probability measure over the domain Ω(W). We denote the sub-model induced under hard intervention by M W=w and the one induced under stochastic intervention by M W . 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 R T .EQUATIONwhere do(W t = w t ) represents the intervention selected by the agent in round t. We use the notation ∆ do(w) to define the sub-optimality gap of the corresponding arm do(W = w). We denote the descendants, ancestors and children of a vertex V i by De(V i ), An(V i ) and Ch(V i ) respectively. We use the notation Bi(V i , G) to denote the set of vertices having bidirected edges to V i except the reward node Y . We refer to the induced graph between observed variables as the observable graph. The transitive closure of a graph, denoted by G tc , encodes the ancestral relationship in G. That is, the directed edge V i → V j is included in G tc only when V i ∈ An(V j ). The transitive reduction, denoted by T r(G) = (V, E r ), is a graph with the minimum number of edges such that the transitive closure is the same as G. The connected component (c-component) of the DAG G, containing vertex V i , is denoted by CC(V i ), which is the maximal set of all vertices in G that have a path to V i , consisting only of bi-directed edges [23] . For a subset of vertices W ⊆ V, we define CC(W) := Wi∈W CC(W i ).In a DAG, a subset of nodes W d-separates two nodes V i and V j when it effectively blocks all paths between them, denoted asV i ⊥ ⊥ d V j |W.Blocking is a graphical criterion associated with d-separation [22] . A probability distribution is said to be faithful to a 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 [14, 24] . We assume that the following form of the interventional faithfulness assumption holds in our setup. Assumption 2.1. Consider a set of nodes W ⊆ V and the stochastic intervention do(W, U) on W and any setU ⊆ V \ W. The conditional independence (CI) statement (X ⊥ ⊥ Y | Z) M W,U holds in the induced model if and only if there is a corresponding d-separation statement in post-interventional graph (X ⊥ ⊥ d Y | Z) G W,U, 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.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 4.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
possibly optimal arms in causal bandits with unknown causal graph: 
 The optimal intervention in a causal bandit setup is not restricted to the parent set of the reward node when the reward node Y is confounded with any node in its ancestors An(Y ) [5] . For instance, consider SCMX 1 = U 1 and X 2 = X 1 ⊕ U 2 and reward Y = X 2 ⊕ U 2 ,where U 1 ∼ Ber(0.5) and U 2 ∼ Ber(0.5). Note that X 2 and reward Y are confounded in this SCM. The optimal intervention in this case is do( 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 [5] ) Consider a causal graph G(V, E) with a reward node Y and letX 1 = 1) since E[Y |do(X 1 = 1)] = 1. The intervention on the parent of the reward (Pa(Y ) = X 2 ) is suboptimal because E[Y |do(X 2 = 0)] = E[Y |do(X 2 = 1)] = 0.5. The example Y V 1 V 2 V 3 (a) G Y V 1 V 2 V 3 (b) G1 Y V 1 V 2 V 3 (c) G2 Y V 1 V 2 V 3 (d) G3H be G[An(Y )]. A set of variables T ⊆ V (H) containing Y is called an UC-territory on G with respect to Y if De H (T) = T and CC H (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 a set of variables, starting from the reward {Y }, alternatively updating the set with the c-component and descendants of the set until there is no change. Definition 3.2. (Interventional Border) [5] Let T be a minimal UC-territory on G with respect to Y . Then,X = Pa(T ) \ T is called an interventional border for G w.r.t. Y denoted by IB(G, Y ). Lemma 3.1. [5] For causal graph G with reward Y , IB(G W , Y )is a POMIS, for any W ⊆ V \ {Y }.Although the graphical characterization in Lemma 3.1 provides a means to 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 1 . Using Lemma 3.1, the set of POMISs for the true graph G isI G = {ϕ, {V 1 }, {V 2 }, {V 3 }, {V 1 , V 2 }}.However, for G 1 which has the bidirected edge V 2 ↔ Y missing, the set of POMISs isI G1 = {ϕ, {V 2 }, {V 1 , V 2 }}. Also for G 2 which has the bidirected edge V 1 ↔ V 2 missing, the set of POMISs is I G2 = {ϕ, {V 1 }, {V 2 }, {V 1 , V 2 }}.In both cases, we miss at least one POMIS, and since it is possible to 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 G 3 has the bidirected edge V 1 ↔ V 3 missing, it still has the same set of POMISs as the true graph, i.e.,I G3 = {ϕ, {V 1 }, {V 2 }, {V 3 }, {V 1 , V 2 }}.This example shows that only a 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. (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 Z and Y , and there exists a bidirected edge in G between some X ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , 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 a 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 An(Y ). Then, we need to test for latent confounders between any pair Z ∈ An(Y ) such that Z and Y don't have a bi-directed edge between them, and X ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , Y ) until there are no new pairs to test. Theorem 3.1 can be useful because depending on 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 n different parent nodes, i.e., Pa(Y ) = {V 1 , V 2 , . . . , V n }, 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, as implied by Theorem 3.1. However, in the worst-case scenario, we would need to test |An(Y )|+1 2 latent variables when the true graph only has the confounders V 1 ← → Y and V i ← → V i+1 for all i = 1, .., n -1. The exact number of latents we need to test can range from |An(Y )| to |An(Y )|+1 2 depending on the true 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to 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. 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
finite sample causal discovery algorithm: 
 In this section, we propose a 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 ⊆ V. Furthermore, let X, T ∈ V \ W be any two variables. Under the faithfulness Assumption 2.1 (X ∈ An(T )) G W if and only if for any w ∈ [K] |W| , we have P (t|do(w)) ̸ = P (t|do(w), do(x)) for some x, t ∈ [K]. Lemma 4.2. Consider two variables X i and X j such that X j / ∈ An(X i ) and a set of variables (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i , X j / ∈ W. Under the faithfulness Assumption 2.1 there is latent confounder between X i and X j if and only if for any w ∈ [K] |W| , we have P (x j | do(x i ), do(W = w)) ̸ = P (x j | x i , do(W = w)) for some realization x i , x j ∈ [K].These Lemmas are modified versions of Lemma 1 in [14] and Interventional Do-see test in [14] , respectively. The difference between Lemma 4.1 and Lemma 1 in [14] is that we have an inequality test that can be used in 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 j / ∈ An(X i ), 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, 9, 17] . Assumption 4.1. Consider a causal graph G(V, E) and W ⊆ V. Furthermore, let X, T ∈ V \ W be any two variables. Then, we have (X ∈ An(T )) G W if and only if for any w ∈ [K] |W| , we have |P (t|do(w)) -P (t|do(w), do(x))| > ϵ for some x, t ∈ [K], where ϵ > 0 is some constant. Assumption 4.2. Consider two variables X i and X j such that X j / ∈ An(X i ) and a set of variables(Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i , X j / ∈ W.There is a latent confounder or a bidirected edge between X i and X j if and only if for any w ∈ [K] |W| , we have P (x j | do(x i ), do(W = w)) -P (x j | x i , do(W = w)) > γ for some realization x i , x j ∈ [K] and some constant γ > 0.We propose Algorithm 1 to learn the transitive closure under any arbitrary intervention do(W), denoted by G tc W . 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 G tc W . We recall that the transitive reduction T r(G) = (V, E r ) of a DAG G = (V, E) is unique, with E r ⊆ E, and it can be computed in polynomial time [25] . Also, note that T r(G) = T r(G tc ). We propose a randomized Algorithm 2 similar to the one proposed in E = ∅ & IData = ∅ for i = 1 : 8α dmax log(n) do W = ∅ for Vi ∈ V do 6 W ← -W ∪ Vi with probability 1 -1 2dmax G tc W , Data W = LearnTransitiveClosure(V, W, δ1, δ2) Compute the transitive reduction T r(G tc W ) & add any missing edges from T r(G tc W ) to E IData = IData ∪ Data W (Keep Saving Interventional Data)return The observable graph structure (V, E) and interventional data samples in IDataEnd Function [14] that repeatedly uses Algorithm 1 to learn the observable graph structure. The motivation behind the randomized Algorithm 2 is Lemma 5 from [14] , which states that for any edge (X i , X j ), consider a set of variables W such that {W i : π(W i ) > π(X i ) & W i ∈ Pa(X j )} ⊆ W where π is any total order that is consistent with the partial order implied by the DAG, i.e., π(X) < π(Y ) iff X ∈ An(Y ).In this case, the edge (X i , X j ) will be present in the graph T r(G 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 takes a parameter d max , which must be greater than or equal to the highest graph degree for our theoretical guarantees to hold.Lemma 4.3. Suppose that the Assumption 4.1 holds and we have access to max( 8ϵ 2 , 8 γ 2 ) log 2K 2 δ1 samples from do(X i = x i , W = w) ∀x i ∈ [K] and 8 ϵ 2 log 2K 2 δ2 samples from do(W = w) for a fixed w ∈ [K] |W| and W ⊆ V. Then, with probability at least 1 -δ 1 -δ 2 , we have (X i ∈ An(X j )) G W if and only if ∃ x i , x j ∈ [K] s.t. P (x j | do(w)) -P (x j | do(w), do(x i )) > ϵ 2 .Lemma 4.3 provides the sample complexity for running ancestrality tests. Algorithm 1 selects a realization w ∈ [K] |W| , takes B samples from the intervention do(W = w), and A samples from every do( X i = x i , W = w) for all X i ∈ V \ W and x i ∈ [K] interventions.Assumption 4.2 can be used to 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 to detect latent confounders in the next phase. For any variables X i and X j such that X j / ∈ An(X i ), we need access to interventional samples do(W = w) such that (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i & X j / ∈ W.In the supplementary material, we demonstrate that randomly selecting the target set W in Algorithm 2 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 (x j |x i , do(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 i = x i is zero or is lower-bounded by some constant η > 0. The role of this assumption is to bound the number of interventional samples required for accurate estimation of the conditional causal effects. Assumption 4.3. For any variable X i ∈ V and any intervention do(W = w) where W ⊆ V and w ∈ [K] |W| , we assume that eitherP (x i |do(W = w)) = 0 or P (x i |do(W = w)) ≥ η > 0.Function LearnCausalGraph(α, dmax, δ1, δ2, δ3, δ4): Lemma 4.5. Consider two nodes X i and X j s.t. X j / ∈ An(X i ) and suppose that Assumptions 2.1 4.2 hold and we have access to max( 8G, IData = LearnObservableGraph(α, dmax, δ1, δ2) C = 16 ηγ 2 log( 2n 2 K 2 δ 3 ) + 1 2η 2 log( 2n 2 K 2 δ 4 ), B = 8 ϵ 2 log 2nK 2ϵ 2 , 8 γ 2 ) log 2K 2 δ1 samples from do(X i = x i , W = w) ∀x i ∈ [K] and 16 ηγ 2 log( 2K 2 δ3 ) + 1 2η 2 log( 2K 2 δ4 ) samples from do(W = w) for a fixed w ∈ [K] |W| and W ⊆ V such that (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i & X j / ∈ W. Then, with probability at least 1 -δ 1 -δ 3 -δ 4 , we have a latent confounder between X i and X j iff ∃ x i , x j ∈ [K] s.t. P (x j |do(x i ), do(w)) -P (x j |x i , do(w)) > γ 2 .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 3 to learn the true causal graph, including all latent confounders, with a given confidence level. An important feature of the sampling complexity result in Theorem 4.2 is that the number of intervention samples needed to learn the causal graph scales polynomially with the number of nodes n.Theorem 4.2. Algorithm 3 learns the true causal graph with latents with probability at least 1 -2 n α 2dmax -2 -8αd max log(n)(nδ 1 + (δ 2 + δ 3 + δ 4 )) with a maximum of 8αd max log n(KAn + max(B, C)) interventional samples. If we set α = 2dmax log ( 4 δ +2) log n , δ 1 = δ 64αdmaxn log n and δ 2 = δ 3 = δ 4 = δ 64αdmax log n ,then Algorithm 3 learns the true causal graph with probability at least 1 -δ. (A and B are given by line 2 of Algorithm 1 and C is given by line 3 of Algorithm 3.) Suppose the constant gaps ϵ and γ in Assumptions 4.1 and 4.2 are close; then, we haveC > 1 η A ≥ 1 η 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 we need to 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 we do not need to test for confounders between all pairs of nodes among ancestors of the reward node to learn the POMIS set. 
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 4 first learns the transitive closure of the graph G tc to find ancestors of the reward node Y . This is because POMISs are only subsets of An(Y ). 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, as characterized by Theorem 3.1. This approach is more sample-efficient since it 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 4 is to run a simple bandit algorithm, e.g., UCB algorithm [26] , to identify the optimal arm from the POMISs. Given that Assumptions 4.1, 4.2, and 4.3 hold, and the reward is binary (Y ∈ {0, 1}), using the results from Lemma 4.4 and Theorem 4.2, 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 α, δ1, δ2, δ3, δ4 as in Theorem 5.1G tc = LearnTransitiveClosure(W = ϕ, δ 2n , δ n ) G, IData = LearnObservableGraph(An(Y ) G tc , α, dmax, δ1, δ2)# Learn the bi-directed edges between reward Y and all nodes Xi ∈ An(Y ) and update G.for every Xi ∈ An(Y ) G tc do G = DetectLatentConfounder(G, Xi, Xj, δ2, δ3, δ4, IData) (Algorithm 5)while There is a new pair that is tested do Theorem 5.1. Algorithm 4 learns the true set of POMISs with probability at least 1 -2δ. Under the event that it learns POMISs correctly, the cumulative regret is bounded as follows:R T ≤ Kn max 8 ϵ 2 , 8 γ 2 log 4n 2 K 2 δ + 8 ϵ 2 log 4nK 2 δ + 8αd max KA An(Y ) + max(B, C) log An(Y ) + s∈{Ω(I)|∀I∈I G } ∆ do(s) 1 + log T ∆ 2 do(s),where A and B are given by line 2 of Algorithm 1, and C is given by line 3 of Algorithm 3 by settingα = 2dmax log ( 4 δ +2) log An(Y ) , δ 1 = δ 64αdmax An(Y ) log An(Y ) and δ 2 = δ 3 = δ 4 = δ 64αdmax log An(Y ).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 G ). The last term corresponds to 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 |An(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 n nodes, there will ben i=1 n i K i = (K + 1) n different possible arms/interventions. 
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 An(Y ). However, Algorithm 4 selectively examines only a subset of latent confounders sufficient to infer the true POMIS set, as outlined in Theorem 3.1. Although the advantage is hard to quantify in general, we demonstrate it using simulations on randomly generated graphs. We sample a random ordering σ among the vertices. Then, for each nth node, we determine its in-degree as X n = max(1, Bin(n -1, ρ)), followed by selecting its parents through uniform sampling from the preceding nodes in the ordering. Finally, we chordalize the graph using the elimination algorithm [27] , employing an elimination ordering that is the reverse of σ. Additionally, we introduce a confounder between every pair of nodes with a probability of ρ L . For all the simulations, we randomly sample 50 causal graphs with different values of densities ρ and ρ L and assume that all variables are binary for simplicity, i.e., K = 2. We set the value of δ to 0.99, and the gaps γ = ϵ = 0.01 and η = 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. The simulation results in Figure 2 demonstrate that Algorithm 4 requires fewer samples than learning the induced graph on An(Y ), which includes all confounders. However, as ρ L increases for a fixed ρ, this advantage diminishes, as illustrated in Figure 2 . The trend remains consistent as the density parameters ρ and ρ L are varied from 0.2, 0.4, and 0.6. The plots in Figure 3 compare the exponentially 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. We also run the UCB algorithm on the learned POMIS set and plot the cumulative regret in Figure 4 .Since the number of time steps T is on the order of 108 , it is not feasible to 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 piecewise linear if we zoom in. Also, the UCB phase converges very fast compared to 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 https://github.com/CausalML-Lab/CausalBandits_ with_UnknownGraph. 
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 a 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. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a 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 see any risk of misuse of our code.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 we encourage authors to take this into account and make a 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 are purely synthetic in nature, and we don'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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 crowdsourcing or research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: We don'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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: A.1 Review of d-separation:Consider three disjoint sets of nodes X, Y, and Z in the causal graph G = (V, E). The sets of nodes X and Y are d-separated given Z, denoted by (X ⊥ ⊥ d Y|Z) G , if and only if 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 a path is a node with both arrows converging, e.g., B is a collider on the path ABC in A → B ← C).A.2 Pearl's Rules of do-Calculus ([22]):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 1: (Insertion/deletion of observations):EQUATIONRule 2: (Action/observation exchange):EQUATIONRule 3: (Insertion/deletion of actions):EQUATIONwhere Z(W) is the set of nodes in Z that are not ancestors of any of the nodes in W in the graph G X .Function DetectLatentConfounder(G, Xi, Xj, δ2, δ3, δ4, IData): Before proceeding to the proof, we recall an important result from [5] : For a causal graph G with reward variable Y , IB(G W , Y ) is a POMIS for any W ⊆ V \ Y .C = 16 ηγ 2 log( 2n 2 K 2 δ 3 ) + 1 2η 2 log( 2n 2 K 2 δ 4 ), B = 8 ϵ 2 log 2nK 2 δ 2 if Xj ∈ An(Xi) swap them.Proof: Consider a causal graph G(V, E) with a node X ∈ An(Y ) such that there exists a latent confounder between X and the reward Y . 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 Y . 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 a set of nodesW = Pa(X) ∪ Ch(Pa(X)) ∪ CC(X) \ {X, Y }. For the graph G ′ , note that X / ∈ MUCT(G ′ W , Y ), and also there ∄Z ∈ Ch(Pa(X)) \ {X} s.t. Z ∈ MUCT(G ′ W , Y ). This implies that ∄Z ∈ Pa(X) s.t. Z ∈ IB(G ′ W , Y). However, for the true graph G, we have a different IB(G W , Y ) for the same definition of W because it contains the bi-directed edge between X and Y , which implies that X ∈ MUCT(G W , Y ), and as a result, Pa(X) ⊆ IB(G W , Y ). Also, in the case Pa(X) = ∅, we have a different POMIS. On this side, note that X / ∈ MUCT(G ′ W , Y ), which implies that along the causal path from X to Y , there must be one node Z such that Z ∈ MUCT(G ′ W , Y ), which implies either X or one of its descendants on the path from X to Y is in IB(G ′ W , Y ), which is not the case for G since X ∈ MUCT(G W , Y ). Thus, we have different interventional boundary or POMIS for the two causal graphs G and G ′ given the above choice of W, even if X has no parents. The next step is to show that the particular POMIS IB(G W , Y ) cannot be learned from the DAG G ′ , i.e., IB(G W , Y ) ̸ = IB(G ′ W ′ , Y ) for any W ′ ⊆ 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) ⊆ IB(G W , Y ) and for all Z ∈ Ch(Pa(X))\{X}, there exists eitherZ ∈ IB(G W , Y ) or De(Z)\{Y } ∈ IB(G W , Y ).Also, if there are such nodes in CC(X) \ {X, Y } which do not have a path to X comprised of directed edges only, call such set of nodes T . If T ̸ = ϕ, then for all t ∈ T , we have eithert ∈ IB(G W , Y ) or De(t) \ {Y } ∈ IB(G W , Y ). Also, note that ∄Z ∈ De(X) ∪ {X} such that Z ∈ IB(G W , Y ). Now consider DAG G ′ with the bi-directed edge between X and Y missing. Assume by contradiction ∃W ′ ⊆ V such that IB(G W , Y ) = IB(G ′ W ′ , Y ). This, however, using the aforementioned characterization of IB(G W , Y ) implies that ∄Z ∈ Ch(Pa(X)) \ {X} such that Z ∈ MUCT(G ′ W ′ , Y) and also ∄t ∈ T such that t ∈ MUCT(G ′ W ′ , Y ) using the aforementioned definition of T . However, note that we need Pa(X) ⊆ IB(G ′ W ′ , Y ), which under the given choice of W is only possible when X ∈ MUCT(G ′ 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 a contradiction because we require the following to be true:∄Z ∈ De(X) ∪ {X} such that Z ∈ IB(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∄W ′ ⊆ V such that G ′ , i.e., IB(G W , Y ) ̸ = IB(G ′ 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 ∈ An(Y ), and may incur linear regret. This completes the proof of Lemma 3.2.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 a 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 a subset of the bidirected edges in G. The graphs will yield different collections of POMISs if there exists some Z ∈ An(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 Z and Y , and there exists a bidirected edge in G between someX ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , Y ) and Z but not in G ′ .Proof: The first half of Lemma A.1, i.e., "The graphs will yield different collections of POMISs if there exists some Z ∈ An(Y ) such that there is a bi-directed edge between Z and Y in G but not in G ′ ," is the same as Lemma 3.2, and the same proof applies here. The reason is that in graph G ′ , we miss a 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 A.1 i.e. graphs will yield different collections of POMISs if there exists some Z ∈ An(Y ) such that (b) is true. 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. 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 G have a bidirected edge between Z and Y , and there exists a bidirected edge in G between some X ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , Y ) 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 a set of nodesW = Pa(Z) ∪ Ch(Pa(Z) \ An(X)) ∪ Bi(Z, G ′ ) \ {X, Z, Y }. For the graph G ′ , note that Z / ∈ MUCT(G ′ W , Y ), and also there ∄N ∈ Ch(Pa(Z) \ An(X)) \ {Z} s.t. N ∈ MUCT(G ′ W , Y ). This implies that ∄N ∈ Pa(Z) \ An(X) s.t. N ∈ IB(G ′ W , Y ).However, for the true graph G, we have a different IB(G W , Y ) for the same definition of W because it contains the bi-directed edge between X and Z, which implies that Z ∈ MUCT(G W , Y ), and as a result, Pa(Z) \ An(X) ⊆ IB(G W , Y ). Also, in the case Pa(Z) \ An(X) = ∅, we have different a POMIS. On this side, note that Z / ∈ MUCT(G ′ W , Y ), which implies that along the causal path from Z to Y , there must be one node N such that N ∈ 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 ∈ MUCT(G W , Y ). Thus, we have different interventional boundary or POMIS for the two causal graphs G and G ′ given the above choice of W. ′ ⊆ V such that IB(G W , Y ) = IB(G ′ W ′ , Y ). This, however, using the aforementioned characterization of IB(G W , Y ) implies that ∄N ∈ Ch(Pa(Z) \ An(X)) \ {Z} such that N ∈ MUCT(G ′ W ′ , Y ) and also ∄t ∈ T such that t ∈ MUCT(G ′ W ′ , Y )for the aforementioned definition of T . However, note that we need Pa(Z) \ An(X) ⊆ IB(G ′ W ′ , Y ), which under the given choice of W is only possible when Z ∈ MUCT(G ′ W ′ , Y ), which would require a 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 to be true:∄N ∈ De(Z) ∪ {Z} such that N ∈ IB(G ′ 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∄W ′ ⊆ V such that G ′ , i.e., IB(G 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.We now proceed to the formal proof for Theorem 3.1: Theorem. 3.1: 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 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 ∈ An(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 Z and Y , and there exists a bidirected edge in G between some X ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , Y ) and Z but not in G ′ .Proof: 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 a bi-directed edge between some Z ∈ An(Y ) and some X ∈ 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 a bi-directed edge between X and Z in G ′ , the graphs will yield the same set of POMISs. This is because Z / ∈ M U CT (G W , Y ) for some set of nodes W only when Z ∈ W, and the same is the case for G because they share a 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 X 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-directed edges between a node Z ∈ An(Y ), such that there is no bi-directed edge between Z and Y in both graphs (G and G ′ ) and a node X that has the following characteristics:X ∈ MUCT(G ′ W , Y ) for some set W ⊆ V but X / ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , 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 ∈ MUCT(G ′ W , Y ) but X / ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , Y ) implies that either ∃N ∈ Pa(Z) such that N ∈ MUCT(G ′ W , Y ) or ∃N ∈ Bi(Z, G ′ ) such that N ∈ MUCT(G ′ W , Y ). Since bi-directed edges in G ′ are a subset of bi-directed edges in G, we have: Either ∃N ∈ Pa(Z) such that N ∈ MUCT(G W , Y ) or ∃N ∈ Bi(Z, G) such that N ∈ MUCT(G W , Y ).∈ MUCT(G ′ W , Y ) but X / ∈ MUCT(G ′ Pa(Z),Bi(Z,G ′ ) , Y ) already implies that either ∃N ∈ Pa(Z) such that N ∈ MUCT(G W , Y ) or ∃N ∈ Bi(Z, G) such that N ∈ MUCT(G W , 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 a 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.Consider a causal graph G(V, E) and W ⊆ V. Furthermore, let X, T ∈ V \ W be any two variables. Fix some realization w ∈ [K] |W| . Under post interventional faithfulness Assumption 2.1 we want to prove: (X ∈ An(T )) G W ⇐⇒ P (t|do(w)) ̸ = P (t|do(w), do(x)) for some x, t ∈ [K].Forward Direction ( =⇒ ): (X ∈ An(T )) G W =⇒ P (t|do(w)) ̸ = P (t|do(w), do(x)) for some x, t ∈ [K]. By contradiction, assume P (t|do(w)) = P (t|do(w), do(x)), ∀x, t ∈ [K]. This implies that P (t|do(w), do(x)) = P (t|do(w)) = some function of only t and w. This implies that for the sub-model M W,X the following CI statements holds: (T ⊥ ⊥ X) M W,X . However, note that if (X ∈ An(T )) G W , then we still have (X ∈ An(T )) G W,X . This implies there is a directed path from X to T in the post-interventional graph G W,X . Therefore, we have: (T ̸ ⊥ ⊥ d X) G W,X . Note that under the post interventional faithfulness Assumption 2.1, the CI statement (T ⊥ ⊥ X) M W,X can hold only if the d-separation statement holds (T ⊥ ⊥ d X) G W,X , which is clearly a contradiction. This completes the proof for the forward direction.Reverse Direction ( ⇐= ): (X ∈ An(T )) G W ⇐= P (t|do(w)) ̸ = P (t|do(w), do(x)) for some x, t ∈ [K]. We prove the contrapositive statement instead, i.e., (X / ∈ An(T ))G W =⇒ P (t|do(w)) = P (t|do(w), do(x)), ∀x, t ∈ [K]. Note that (X / ∈ An(T )) G W clearly implies that (X / ∈ An(T )) G W,X which implies that (T ⊥ ⊥ d X) G W,X. Thus, using Rule 3 of Pearl's do calculus, we have: P (t|do(w), do(x)) = P (t|do(w)), ∀x, t ∈ [K]. This completes the proof of the reverse direction.Consider two variables X i and X j such that X j / ∈ An(X i ) and a set of variables (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i & X j / ∈ W. Fix some realization w ∈ [K] |W| .Under the post-interventional faithfulness Assumption 2.1 we want to show that: There is latent confounder between X i and X j ⇐⇒ P (x j | do(x i ), do(W = w)) ̸ = P (x j | x i , do(W = w)) for some realization x i , x j ∈ [K].There is latent confounder between X i and X j such that X j / ∈ An(X i ) =⇒ P (x j | do(x i ), do(W = w)) ̸ = P (x j | x i , do(W = w)) for some realizationEQUATIONHowever, since we know that L ij is a confounder between X i and X j , we have an edge L ij → X i in the causal graph, which implies that under any intervention do(Z) such that X i / ∈ Z, we must have (L ij ̸ ⊥ ⊥ X i ) M Z by interventional faithfulness Assumption 2.1. This implies that there exists a realization x * i and l * ij such that:P (U ′ j = u ′ j , L ij = l * ij |x * i , do(pa(X i )), do(pa(X j ) \ {x i })) ̸ = P (U ′ j = u ′ j , L ij = l * ij ) (12)Now, using the combination do(W = w) and a special choice of realizations x * i and l * ij , we must have at least one special realization x * j such that:P (x * j | do(x * i ), do(Pa(X i )), do(Pa(X j ) \ {x i }), U ′ j = u ′ j , L ij = l * ij ) > 0.Combining this with Equations 12 and 10, we conclude for somex * i , x * j ∈ [K], we have P (x * j | do(x * i ), do(W = w)) ̸ = P (x * j | x * i , do(W = w)). Thus this leads to contradiction. Thus if there is a latent confounder between X i and X j =⇒ P (x j | do(x i ), do(W = w)) ̸ = P (x j | x i , do(W = w)) for some realization x i , x j ∈ [K]. This completes the proof of the forward direction.Reverse Direction ( ⇐= ): For a pair of variables X i and X j such that X j / ∈ An(X i ), if P (x j | do(x i ), do(W = w)) ̸ = P (x j | x i , do(W = w)) for some realizations x i , x j ∈ [K], then there is a latent confounder between X i and X j . We prove the contrapositive statement instead, i.e., if there is no latent confounder between X i and X j , then P (x j | do(x i ), do(W = w)) = P (x j | x i , do(W = w)), ∀x i , x j ∈ [K].Note that by construction, we have: (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W. For such choice of set W and the fact that X j / ∈ An(X i ) and there is no latent confounder between X i and X j , we have (X j ⊥ ⊥ X i ) G X i W . Thus, from Pearl's do-calculus Rule 2, we haveP (x j | do(x i ), do(W = w)) = P (x j | x i , do(W = w)), ∀x i , x j ∈ [K].This completes the proof of the reverse direction.Suppose that Assumption 4.1 holds and we have access to max( 8 ϵ 2 , 8 γ 2 ) log 2K 2 δ1 samples from do(X i = x i , W = w) ∀x i ∈ [K] and 8 ϵ 2 log 2K 2 δ2 samples from do(W = w) for a fixed w ∈ [K] |W| for some W ⊆ V. We want to show that with probability at least 1 -δ 1 -δ 2 , we have the following:EQUATION)Using Hoeffding's inequality with A samples from intervention do(x i , w),EQUATION) If we choose A = max( 8 ϵ 2 , 8 γ 2 ) log 2K 2 δ1, we have:EQUATION)Similarly, using Hoeffding's inequality with B samples from intervention do(w),EQUATION)If we choose B = 8 ϵ 2 log 2K 2 δ2 , we have:EQUATION)Lemma A.2. [14] Consider a graph G with observed variables V and an intervention set W ⊆ V.Consider post-interventional observable graph G W and a variable X j ∈ V \ W. Let X i ∈ Pa(X j ) be such that all the parents of X j above X i in partial order are included in the intervention set W. This implies that {Wi : π(W i ) > π(X i ) & W i ∈ Pa(X j )} ⊆ W . Then, the directed edge (X i , X j ) ∈ E(T r(G W )).The properties of transitive reduction yields T r(G W ) = T r(G tc W ). Consequently, the transitive reduction of G tc W , i.e., T r(G tc W ) = T r(G W ) may be used to learn the directed edge (X i , X j ). (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) < π(Y ) iff X is an ancestor of Y).Assume that the number of the direct parents of X j above X i is d ij where d ij ≤ d max . Let E i (X j ) be the following event:X i , X j / ∈ W & {W i : π(W i ) > π(X i ) & W i ∈ Pa(X j )} ⊆ W.The probability of this event for one run of the outer loop in Algorithm 2 with the assumption that 2d max >= 2 is given by:EQUATION)The last inequality holds for 2d max >= 2 because (1 -1 x ) x ≥ 0.25, ∀x ≥ 2. Based on Lemma A.2, the event E i (X j ) implies that the directed edge (X j , X j ) will be present in T r(G tc W ) and will be learned. The outer loop runs for 8αd max log(n) iterations and elements of the set W are independently sampled. The probability of failure, i.e., the event under consideration does not happen for all runs of the outer loop in Algorithm 2, is bounded as follows:EQUATION)For a graph with a total number of variables n, the total number of such bad events will be n 2 since a graph can have at most n 2 edges. Using the union bound, the probability of bad event for any pair of variables is given by:EQUATION)Under the event that Algorithm 1 learns the correct transitive closure G tc W for all the 8αd max log n randomly sampled intervention sets W ⊆ V, the above derivation shows that we will be able to learn all edges in the true observable graph with a probability of at least 1 -1 n α 2dmax-2 . Now recall the result from Lemma 4.3 that Algorithm 1 learns the true transitive closure under any intervention, i.e., G tc W , with KAn + B intervention samples with a probability of at least 1 -nδ 1 -δ 2 . Combining the two results above using the union bound, we have the following result: Algorithm 2 learns the true observable graph with a probability of at least 1 - 1 n α 2dmax -2 - 8αd max log(n)(nδ 1 + δ 2 ) with a maximum 8αd max log n(KAn + B) interventional samples. Also, if we set α = 2dmax log ( 2 δ +2) log n , δ 1 = δ 32αdmaxn log n ,EQUATIONηγ 2 log( 2K 2 δ3 ) + 1 2η 2 log( 2K 2 δ4 ) from do(W = w) for a fixed w ∈ [K] |W| and W ⊆ V such that (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i & X j / ∈ W.We want to show that, with probability at least 1 -δ 1 -δ 3 -δ 4 , we have the following:There exists a latent confounder between X i and X j ⇐⇒ ∃ x i , x j ∈ [K] s.t. P (x j |do(x i ), do(w)) -P (x j |x i , do(w)) > γ 2 .(31) Using Hoeffding's inequality with A samples from intervention do(x i , w).EQUATION) If we choose A = max( 8 ϵ 2 , 8 γ 2 ) log 2K 2 δ1, we have:EQUATION)Using Hoeffding's inequality with C samples from intervention do(x i ).EQUATION)Where C xi is the number of samples where X i = x i among the C samples for the intervention do(w).Note the we can't directly control C xi and it's value depends on the true interventions distribution P (x i , do(w)) along-with the number of samples C. Suppose if we can set C xi ≥ 8 γ 2 log 2K 2 δ3 , we have:EQUATION)We need to find the number of samples C such that C xi ≥ 8 γ 2 log 2K 2 δ3 . Using the Hoeffding's bound we have:EQUATION) Let δ4 K 2 = 2e -2η 2 /C , which implies η = C 2 log 2K 2δ4 . Thus we have:EQUATION)Using Assumption 4.3, we have P (x i |do(w)) = 0 or P (x i |do(w)) ≥ η. Note that if P (x i |do(w)) = 0, the event will never happen, and we don't care about the accuracy of the estimate P (x j |x i , do(w)) because it is already initialized to zero. Now the equation above can be rewritten as:EQUATION)Since we want C xi ≥ 8 γ 2 log 2K 2 δ3 with high probability, we have the following relationship:EQUATIONSolving the equation for number of samples C we get:EQUATIONIn order to make the expression simpler we choose the number of samples C as follows:EQUATIONEQUATIONEQUATIONEQUATIONSuppose we take C samples for intervention do(w) as given above. Now, from Equations 35, 39, and 40, using the union bound, we have the following:EQUATION) Since the realization w ∈ [K] |W| is fixed, but x i , x j ∈ [K],we have a total of K 2 possible bad events when estimates are not good. With the given choice of number of samples A and C, we have:EQUATIONEQUATIONUnder the good event, which has a probability of at least 1 -δ 1 -δ 3 -δ 4 , both estimates are accurate. We now consider the two possible scenarios. Suppose that there is no latent confounder between X i and X j . In this case by Lemma 4.2 we have P (x j |do(x i ), do(w))-P (xj |x i , do(w)) = 0 , ∀x i x j ∈ [K]. By triangular inequality we have the following:EQUATIONHowever, when there is a latent confounder between X i and X j , in this case, under Assumption 4.2, we must have some configuration, say x i , x j ∈ [K], for any w ∈ [K] |W| , such that P (x j |do(x i ), do(w)) -P (x j |x i , do(w)) > γ. By triangular inequality when there is a latent confounder between X i and X j , ∃ x i , x j ∈ [K] such that: P (x j |do(x i ), do(w)) -P (x j |x i , do(w)) ≥ P (x j |do(x i ), do(w)) -P (x j |x i , do(w))-P (x j |do(x i ), do(w)) -P (x j |do(x i ), do(w)) -P (x j |x i , do(w)) -P (xEQUATIONThus, using Assumption 4.2 with the given choice of number of samples with probability at least 1 -δ 1 -δ 3 -δ 4 , we have the following result:There exists a latent confounder between X i and X j ⇐⇒EQUATIONThis 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 2 learns the true observable graph with a probability of at least 1 -1 n α 2dmax -2 -8αd max log(n)(nδ 1 + δ 2 )with a maximum of 8αd max log n(KAn + B) interventional samples. The next phase in Algorithm 3 is to learn/detect latent confounders between any pair of variables. For all pairs of nodes X i and X j such that X j / ∈ An(X i ), we define a set of nodesW ij ⊆ V such that X i , X j / ∈ S i , where W ij = (Pa(X i ) ∪ Pa(X j ) \ {X i }). Also, note that |W ij | ≤ 2d max . Let us define the event E ij = [W ij ⊆ W & X j , X i / ∈ W].The probability of this event for one run of the outer loop in Algorithm 2 with the assumption that 2d max ≥ 2 is given by:EQUATIONThe last inequality holds for d max ≥ 2. Note that we reuse all the interventional data samples from Algorithm 2 in Algorithm 3. Under Assumption 4.2, if the event E ij happens with a large enough number of samples, we can detect the presence or absence of latent confounders between X i and X j . The outer loop runs for 8αd max log(n) iterations, and the elements of the set W are independently sampled. The probability of failure, i.e., the event under consideration does not happen for all runs of the outer loop in Algorithm 2, is bounded as follows:EQUATION)For a graph with a total number of variables n, the total number of such bad events will be n 2 . Using the union bound, the probability of bad event for any pair of variables is given by:P [F ailure] ≤ n 2 × 1 n α 2dmax ≤ 1 n α 2dmax -2 .(54) This implies with a probability of 1 -1 n α 2dmax-2 , we will be able to find an appropriate interventional dataset to test the presence of latent confounders between any pair of variables using Assumption 4.2 after running Algorithm 2. We still need to make sure we have enough interventional samples to be able to test the latents. This is because we need to accurately estimate conditional effects to carry out the test, as in Assumption 4.2. We first consider estimation of the causal effect P (x j |do(x i ), do(w)) for any randomly sampled set W. Now, consider a fixed X i , X j ∈ V \ W. We have access tomax 8 ϵ 2 , 8 γ 2 log 2nK 2 δ1samples for every x i ∈ [K]. We have already shown that under the good event, we have the following:EQUATION)EQUATIONNow, we consider estimation of the conditional causal effects, i.e., P (x j |x i , do(w)). Note the while running the Algorithm 2 we have access toB = 8 ϵ 2 log 2nK 2 δ2samples 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 leastC = 16 ηγ 2 log( 2n 2 K 2 δ3 ) + 1 2η 2 log( 2n 2 K 2 δ4 ) samples instead. Now, consider a fixed X i , X j ∈ V \ W.With access to C samples as given above, following from Equation 48 in the Proof of Lemma 4.5, we have the following result:EQUATION)Note that in the above equation, we have δ3 n 2 and δ4 n 2 instead of δ 3 and δ 4 as in Equation 48, because here in the number of samples C, we also have δ3 n 2 and δ4 n 2 instead of δ 3 and δ 4 when compared to the number of samples in Equation 45. Now, using the union bound we have the following:EQUATIONAgain using the union bound over all X i ∈ V \ W we have the following:P (x j |do(x i ), do(w)) -P (x j |do(x i ), do(w)) ≤ γ 4 ∀x i , x j ∈ [K] , ∀X i ∈ V \ W , ∀X j ∈ V \ (W ∪ {X i }) w.p. at least 1 -δ 3 -δ 4 (58)This implies that under the good event, for every randomly sampled intervention set W ⊆ V, the estimate of the conditional causal effect is accurate within the desired γ 4 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 8αd max log n 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 1- 1 n α 2dmax -2 - 1 n α 2dmax -2 -8αd max log(n)(nδ 1 +δ 2 )-8αd max log(n)(δ 3 +δ 4 ) = 1- 2 n α 2dmax -2 - 8αd max log(n)(nδ 1 + (δ 2 + δ 3 + δ 4 ))G tc = LearnTransitiveClosure(W = ϕ, δ 2n , δ n ) G, IData = LearnObservableGraph(An(Y ) G tc , α, d max , δ 1 , δ 2 ) C = 16 ηγ 2 log( 2n 2 K 2 δ3 ) + 1 2η 2 log( 2n 2 K 2 δ4 ) , B = 8 ϵ 2 log 2nK 2 δ2#Learn the bi-directed edges between reward Y and all nodes X i ∈ An(Y ) and update G.for every X i ∈ An(Y ) G tc do Set X j := Y Find interventional data sets do(W = w) and do(X i = x i , W = w) from IData s.t. (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i & X j / ∈ W Get max(0, B -C) new samples for do(W = w) if ∃ x i , x j ∈ [K] s.t. | P (x j |do(x i ), do(w)) -P (x j |x i , do(w))| > γ 2 then Add bi-dirceted edge X i ← → X j to graph Gwhile There is a new pair that is tested do # Test for the latent between the pair (Z, X) and update G.Set X i := Z, X j := X if X j ∈ An(X i ) swap them.Find interventional data sets do(W = w) and do(X i = x i , W = w) from IData s.t. (Pa(X i ) ∪ Pa(X j ) \ {X i }) ⊆ W and X i & X j / ∈ W Get max(0, B -C) new samples for do(W = w) if ∃ x i , x j ∈ [K] s.t. | P (x j |do(x i ), do(w)) -P (x j |x i , do(w))| > γ 2 then Add bi-directed edge X i ← → X j to graph GLearn the set of POMISs I G from the graph G Using Algorithm 1 in [5] .Run UCB algorithm over the arm set A = {Ω(I) | ∀I ∈ I G }.A. 13 δ . The next step is to learn the complete observable graph induced on the reward node and its ancestors and then learn/detect only a subset of latent confounders which are characterized to be necessary and sufficient to learn the true set of POMISs (Theorem 3.1). Although this step saves us interventional samples compared to the full discovery Algorithm 3, 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 can 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 a probability of at least 1 -δ using . 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 V j for every realization of its parents Pa(V j ). As a result, there are a total of K K |Pa(V j )| possible mappings from Pa(V j ) to V j . Also, note that within a c-component, the response variables for every observed variable are correlated. This implies that for every component C j , the corresponding response variable M j has the domain|Ω(M j )| = Vi∈C j K K |Pa(V i )|. Thus, every vector p j will have a total of Vi∈C j K K |Pa(V i )| components. Although the response variable decomposition is useful for smaller and sparse causal graphs, the scaling for the length of vectors p j 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 to exploit them effectively, especially for larger and denser causal graphs, which is still an open problem.We ran our experiments on a 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 a 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 2 hours. For the experimental plots in Figure 4 , the total runtime is around 2 hours for each subplot since we run the full algorithm for multiple randomly sampled graphs.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 decision-making 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-making or policy recommendations in real-world situations. Thus, extra care and consideration of ethical boundaries regarding actions/interventions are needed while applying our proposed methodology to practical problems.AcknowledgmentMurat Kocaoglu acknowledges the support of NSF CAREER 2239375, IIS 2348717, Amazon Research Award and Adobe Research. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: There are a few typos in the paper:
- For the definition of transitive reduction, does it force $\mathcal{G}$ to be connected? Otherwise, the empty edge set is minimum.

- For the d-separation defined in line 119, shouldn't it condition on $\mathbf{W}$?

- Assumption 2.1 is defined on a mixture of hard intervention and stochastic intervention (in line 126)?

- Line 4 in Algorithm 2, should it be $\mathcal{W}=\emptyset$?
questions: questions: - How is transitive reduction computed in Algorithm 2? Does it need to exhaust all possible sub-graphs?

- 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].

- 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: limitations: The paper assumes semi-Markovian causal models and stronger identification assumptions.
paper_summary: paper_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. 

While 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.
strength_weakness: strength_weakness: (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.
questions: 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)$?

Are 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: 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.
paper_summary: paper_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.
To 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.
strength_weakness: strength_weakness: 1- The proposed regret bound can become very large when either $\epsilon$ or $\gamma$ is small, which is a possible scenario.

2- It’s not clear whether the proposed algorithm and upper is optimal or not. No discussion has been provided.

3- There is not any discussion regarding the running time of algorithms.
questions: questions: Could you discuss the points mentioned above?

1- 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?

2- 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)

3- In algorithm 2, for each iteration, Should not set $W = \emptyset$?
limitations: limitations: Yes.

Comments: title: Re.
Re.
Re.
Re.
comment: We thank the reviewer for their insightful comments and suggestions. We will include the extended experiments in the main paper following the reviewer's suggestion. We are also grateful to the reviewer for recommending acceptance of our work.
We thank the reviewer for their insightful comments and suggestions. We are also grateful to the reviewer for appreciating our work and increasing the score.
Thanks the the response and I also read the other insightful discussions. I believe it is a solid paper that contributes to the field and I'd like to raise the score from 6 to 7.
Many thanks for the clarification and extended experiments. I maintain my score for a weak accept.
We thank the reviewer for their insightful comments and suggestions to improve the clarity of our manuscript. We are also grateful to the reviewer for increasing our score.
Thank you for your comprehensive discussion. After reviewing the rebuttals and considering the comments from other reviewers, I intend to raise my score to 7.
Thank you for your reply. The **main deciding factor** in the choice between vanilla UCB and our proposed algorithm is the number of nodes, $ n $, in the graph. The vanilla UCB may perform better for graphs with a small number of nodes. However, as the number of nodes increases, it becomes infeasible to run the naive algorithm that does not consider causal information due to the exponential growth of the action space. Our simulations demonstrate that once the number of nodes exceeds a certain threshold—around 17 or so—the number of arms for the vanilla UCB algorithm grows significantly larger than our regret bound, as shown in the plot in Fig. 3. Note that we set the gap parameters $ \gamma = \epsilon = 0.01 $ in our simulations. The number of arms for the vanilla UCB algorithm scales exponentially with the number of nodes $ n $, whereas our regret bound scales polynomially with respect to $ n $.

**Impact of  graph structure:**

Regarding the graph structure, it depends on whether we have prior knowledge of the underlying graph structure before running the bandit algorithm. For instance, if we know that there is a confounder between every pair of nodes in the graph, causal discovery will not reduce the size of the action space, and it might be preferable to skip causal discovery and apply only the classic UCB. The key factor here is that the reduction of the action space using causal discovery depends on the density of latent confounders. If there are confounders between a large number of pairs of nodes, the reduction in the size of the action space becomes smaller. However, without prior knowledge of the graph's structure, one cannot make this distinction. We will include a simulation with a range of values for the parameter $\rho_L$, from $0.10$ to $1.00$, to demonstrate how the reduction in the size of the action space achieved through causal discovery—compared to vanilla UCB—varies with the density of latent confounders in the underlying graph. Note that the parameter $\rho_L$ controls the density of latent confounders in the sampled graph. We are grateful to the reviewer for highlighting this point and we believe it would be a valuable addition to our manuscript.

**Impact of  parametric assumptions (i.e., $\epsilon$ and  $\gamma$):**

Regarding the parametric gap assumptions, $\epsilon$ and $\gamma$, they are constants that do not depend on the number of nodes in the graphs. As discussed earlier, running UCB with an exponential number of arms, specifically $(K+1)^n$, will result in very large regret for large $n$. However, we can still make a basic comparison between vanilla UCB and our algorithm by comparing the sum of the first four terms in our regret bound with the regret bound or the number of arms in the vanilla UCB algorithm, similar to Figure 3 in our paper. This comparison will help inform our choice. We will include this discussion in the revised manuscript.

We hope that we have addressed the reviewer’s question and would be happy to discuss further if there are any follow-up questions. If the reviewer has no further questions, we would kindly request them to reconsider our score, taking into account our rebuttal and the additions we have suggested.
Thank you for your response. Regarding the comparison with Classic UCB, I understand that your algorithm reduces the action space before applying UCB. However, this typically incurs a cost (as reflected in the first four terms of your regret bound). My question was: under which graph structures and parametric assumptions (i.e., $\epsilon$ and  $\gamma$) would it be preferable to skip causal discovery and apply only classic UCB? Could you discuss this?