Causal Bandits with Unknown Graph Structure
Authors: Yangyi Lu
Amirhossein Meisami
Ambuj Tewari
Venue: NeurIPS 2021 Poster (2021)
Keywords: bandit
causal bandit
causality

Abstract: In causal bandit problems the action set consists of interventions on variables of a causal graph. Several researchers have recently studied such bandit problems and pointed out their practical applications. However, all existing works rely on a restrictive and impractical assumption that the learner is given full knowledge of the causal graph structure upfront. In this paper, we develop novel causal bandit algorithms without knowing the causal graph. Our algorithms work well for causal trees, causal forests and a general class of causal graphs. The regret guarantees of our algorithms greatly improve upon those of  standard multi-armed bandit (MAB) algorithms under mild conditions. Lastly, we prove our mild conditions are necessary: without them one cannot do better than standard MAB algorithms.

Causal Bandits with Unknown Graph Structure
Yangyi Lu Department of Statistics University of Michigan yyluêuma ch, edu
Amirhossein Meisami Adobe Inc. me sami Badobe. com
Ambuj Tewari
Department of Statistics University of Michigan tewari a@um ch. edu
Abstract
In causal bandit problems, the action set consists of interventions on variables of causal graph. Several researchers have recently studied such bandit problems and pointed out their practical applications. However, all existing works rely on a restrictive and impractical assumption that the learner is given full knowledge the causal graph structure upfront. In this paper, we develop novel causal bandit algorithms without knowing the causal graph. Our algorithms work well for causal trees, causal forests and general class of causal graphs. The regret guarantees our algorithms greatly improve upon those of standard multi-armed bandit (MAB) algorithms under mild conditions. Lastly, we prove mild conditions are necessary: without them one cannot do better than standard MAB algorithms.
Introduction
multi-armed bandit (MAB) problem is one of the classic models of sequential decision mak- ing (Auer et al. 2002; Agrawal and Goyal 2012 2013a). Statistical measures such as regret and sample complexity measure how fast learning algorithms achieve near optimal performance bandit problems. However, both regret and sample complexity for MAB problems necessarily scale with the number of actions without further assumptions. To address problems with a large action set, researchers have studied various types of structured bandit problems where additional assumptions are made on the structure of the reward distributions of the various actions. Algorithms for structured ban- dit problems exploit the dependency among arms to reduce the regret or sample complexity. Examples of structured bandit problems include linear bandits (Abbasi Yadkori et al.) [00T Agrawal and Goyal 2013b). sparse linear bandits (Abbasi- Yadkori et al. 2012), and combinatorial bandits (Cesa-Bianch and Lugosi 2012] Combes et al.) 2015).
In this paper, we study a different kind of structured bandit problems: causal bandits. In this setting, actions composed of interventions on variables of a causal graph. Many real world problems can be modeled via causal bandits. In healthcare applications, the physician adaptively adjusts the dosage of multiple drugs to achieve some desirable clinical outcome (Liu et al.) 2020). In email campaign problems, marketers adjust for features of commercial emails to attract more customers and convert them into loyal buyers (Lu et al.) 2019 Nair et (021). Genetic engineering also involves direct manipulation of one or more genes using biotechnology. such as changing the genetic makeup of cells to produce improved organisms (Wikipedia contributors (002). Recently there has been a flurry
of works (Lattimore et al. 2016 Sen et 2017) and Bareinboim, 2019) Nair et al. 2021) on causal bandits that show how to achieve simple e regret or cumulative regret not scaling with the action set size.
[017;Lee Lee and Bareinboim, 2018 Lu et al. 2019 Lee
However, major drawback of existing work is that they require significant prior knowledge. All existing works require that the underlying causal graph is given upfront. Some regret analysis works even assume knowing certain probabilities for the causal model. In practice, they are strong assumptions.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper, our goal is to develop causal bandit algorithms that 1) do not require prior knowledge of the causal graph and 2) achieve stronger worst-case regret guarantees than non-causal algorithms such as Upper Confidence Bound (UCB) and Thompson Sampling (TS) whose regret often scales at least polynomially with the number of nodes n in the causal graph. Unfortunately, this goal cannot be achieved for general causal graphs. Consider the causal graph consists of isolated variables and the reward directly depends on one of them. Then in the worst case there is no chance to do better than standard algorithms since no meaningful causal relations among variables can be exploited. In this paper, we study what classes of causal graphs on which we can achieve the goal.
Our Contributions. We summarize our contributions below.
1. We first study causal bandit problems where the unknown causal graph is directed tree, or causal forest. This setting has wide applications biology and epidemiology (Greenewald et al. 2019; Burgos et al. 2008 Kontou et al. 2016 Pavlopoulos et al. 2018). We design novel algorithm Central Node UCB (CN-UCB) that simultaneously exploits the reward signal and the tree structure to efficiently find the direct cause of the reward and then applies the UCB algorithm on a reduced intervention set corresponding to the direct cause.
Theoretically, we show under certain identifiability assumptions, the regret of our algorithm only scales !ogarithmically with the number of nodes n in the causal graph. To our knowledge, this the first regret guarantee for unknown causal graph that provably outperforms standard MAB algorithms. We complement our positive result with lower bounds showing the indentifiability assumptions are necessary.
3. Furthermore, we generalize CN-UCB to more general class of graphs that includes causal trees, causal forests, proper interval graphs, etc. Our algorithm first constructs undirected clique (junction) trees and again simultancously exploits the reward signal and the junction-tree structure to efficiently find the direct cause of the reward. We also extend our regret guarantees to this class of graphs.
In many scenarios, our algorithms do not recover the full underlying causal graph structure. Therefore, our results deliver the important conceptual message that exact causal graph recovery not necessary in causal bandits since the main target is to maximize the reward.
2 Related work
The causal bandit framework was proposed by Lattimore et al. (2016) and has been studied in various settings since then. In the absence of confounders, Lattimore et al. (2016) and [Sen et al. (2017) studied the best arm identification problem assuming that the exact causal graph and the way interventions influence the direct causes of the reward variable are given. Lu et al. (20T9) and Nair et al. (2021) proposed efficient algorithms that minimize the cumulative regret under the same assumptions. When confounders exist, Lee and Bareinboim (2018) 2019) developed effective ways to reduce the intervention set using the causal graph before applying any standard bandit algorithm, such as UCB. Even though the performance of above works improved upon that of standard bandit MAB algorithms, they all make the strong assumption of knowing the causal graph structure in advance.
In our setting, the underlying causal graph is not known. Then a natural approach is first learn the causal graph through interventions. There are many intervention design methods developed for causal graph learning under different assumptions (He and Geng. 2008: Hyttinen et al., 2013)] (Shanmugan et al. [015] Kocaoglu et al. 2017: [Lidgren et 2018 Greenewald et al. 2019 Squires et al. 2020). However, this approach is not sample efficient because it is not necessary to recover the full causal graph in order to maximize rewards. de Kroon et al. (020) tackled this problem with unknown graph structure based on separating set ideas. However. this implicitly requires the existence a set of non-intervenable variables that d-separate the interventions and the reward. Moreover, their regret bound does not improve upon non-causal algorithms such as UCB. In this paper, we take a different approach which uses the reward signal to efficiently learn the direct causes of the reward.
Our approach is inspired by Greenewald et al. (2019) which proposed a set of central node algorithms that can recover the causal tree structure within O(log n) single-node interventions. [Squires et al. (2020) also extended the central node idea to learn general class of causal graphs that involves constructing junction trees and clique graphs. Following these works, our causal bandit algorithms
2

---

also adaptively perform interventions on central nodes to learn the direct causes of the reward variable. However, our algorithms differ from theirs because we also take the reward signal into account.
3
Preliminaries
In this section, we follow the notation and terminology of Lattimore et al. (2016); Greenewald et al. (2019) for describing causal models and causal bandit problems.
3.1 Causal Models
A causal model consists of a directed acyclic graph (DAG) D over a set of random variables X' = _.,..... ,.,) and a joint distribution P that factorizes over D. The parents (children) of a variable X; on graph D. denoted by (ap(X,) (or (x)( are the set of variables X, such that there is directed edge from X, to X; (or from X; to Xj) on graph D. The set of ancestors (descendants) of a variable X,, denoted by (X) (or (x,();)) are the set of variables X, such that there is path from X, X; (or from X; Xj) on D. Without loss of generality, we assume the domain set for every X; is Dom = [K] == (1....: .......K. For every X,, we write the set of neighbors of X; in graph D as ND(X;) including variables X5 such that there is an edge between X, and X, regardless of the direction. The maximum degree of an undirected graph G is denoted
by dmax (G). Throughout, we denote the true causal graph by D. use (+) as the set of vertices of graph and detine skeleton(-) -) as the undirected graph obtained by replacing the arrows in the directed graph with undirected edges.
Definition 1 (Directed Tree and Causal Tree). A directed tree is a DAG whose underlying undirected graph is a tree and all its edges point away from the root. A causal tree is a causal model whose underlying causal graph is directed tree.
For a node X; on a directed or undirected tree D and its neighbor Y E (X,),), we write B as the set of nodes that be reached from Y through any path the graph (regardless of the directions edges on the path), when the edge between X, and Y is cut out from D. Note that the neighbor Y itself is always included in branch B,
Definition 2 (Central Node (Greenewald et al. 2019)). A central node Ue of an undirected tree T with respect to a distribution q over the nodes one for which max, No (v.) (B"".... 1/2 At least one such v. is guaranteed to exist for any distribution q (Jordan 1869 Greenewald et al. 2019).
Informally, central node Ue guarantees that the weight of every branch around Ue cannot be larger than 1/2 according to the distribution q(-).
Definition 3 (Essential Graph). The class of causal DAGs that encode the same set of conditional independences is called the Markov equivalence class. Denote the Markov equivalence class of
a DAG D by (D). The essential graph of D, denoted by E(D), has the same skeleton as D, with directed edges X; - X, if such edge direction between X, and X, holds for all DAGs in [D), and undirected edges otherwise.
The chain components of E(D), denoted by CC()(D)), are the connected components of E(D) after removing all directed edges. Every chain component of &(D) is a chordal graph (Anders- son et al., 1997). A DAG whose essential graph has a single chain component is called a moral DAG (Greenewald al. 2019).
Definition 4 (Causal Forest (Greenewald et al. 2019)). A causal graph is said to be causal forest if each of the undirected components of the essential graph are trees.
Many widely used causal DAGs including causal trees and bipartite causal graphs are examples of causal forest (Greenewald al., 2019). Bipartite graph applications can range from biological networks, biomedical networks, biomolecular networks to epidemiological networks (Burgos et al. 2008
Kontou et al. 2016 Pavlopoulos et al. 2018).
3.2
Causal Bandit Problems
In causal bandit problems, the action set consists of interventions (Lattimore et al. 2016). An intervention on node X removes all edges from (x)(X) to X and results in post-intervention
3

---

distribution denoted by P([X))do(X =x)) over {X] X [X}. An empty intervention is represented by do(). The reward variable is real-valued and for simplicity, we assume the reward is only directly influenced by one of the variables in X, which we call the reward generating variable denoted by Nn | The learner does not know the identity of Xn. Since there only one n in our setting, the optimal intervention must be contained in the set of single-node interventions as follows: A {Xo(X= = x) X E X, - [K]}. Thus, we focus on above intervention set with | = nK throughout the paper.
We denote the expected reward for intervention a do(X x)) by Ha = E [R]a] Then a" argmax A is the optimal action and we assume that Ha E [0, for all a. A random reward for a do z) is generated by R/a Ma + E, where is I-subGaussian. At every round t. the learner pulls a = do(X, Iz) based on the knowledge from previous rounds and observes a random reward R2 and the values of all X X. The objective of the learner is to minimize the cumulative regret Ry = Th Ei= Pa, without knowing the causal graph D.
We make the following assumptions below.
Assumption 1. The following three causal assumptions hold:
Causal sufficiency: for every pair of observed variables, all their common causes are also observed.
Causal Markov condition: every node in causal gruph G conditionally independent of its nondescendents, given its parents.
Causal faithfulness condition: the set of independence relations derived from Causal Markov condition is the exact set of independence relations.
Assumption T is commonly made in causal discovery literature (Peters et al. 2012 Hyttinen et al. 2013 [Eberhardt] 2017 Greenewald al. (019).. Equivalently speaking, there is latent common causes and the correpondence between d-separations and conditional independences is one-to-one.
Assumption (Causal Effect Identifiability) There exists an > 0, such that for any two variables X; + Xj in graph D, we have [P(X, x//o(X; z²)) P(X, x)) holds for some x E Dom ( E Dom(X.).
Assumption is necessary. It states that if there is direct causal relation between two variables the graph, the causal effect strength cannot go arbitrarily small. A similar version of this assumption was also made by Greenewald et al. (2019) in their causal graph learning algorithms. We show the necessity of this assumption in Section 6 Intuitively, without this assumption, any causal relation among variables cannot be determined through finite intervention samples and 2 (VnKT worst-case regret is the best one can hope for.
Assumption 3 (Reward Identifiability). We assume that for all X E An(XR), there exists [K] such that IE [[]o(() - [[] = x)]l Z for some universal constant A >
Lastly, show that Assumption is also necessary. It guarantees difference on the expected reward between the observations and after an intervention on an ancestor of X In Section 6 we prove that the worst-case regret is again lower bounded by ((vnKT) without this assumption.
In the following sections, we describe our causal bandit algorithms that focus on intervention design to minimize regret. Like most intervention design works, our algorithm take the essential graph E(D and observational probabilities over X' (denoted by P(2)) as the input, which can be estimated from enough observational data") (He and Geng 2008 Greenewald et al. 2019 Squires et al. 2020).
4 CN-UCB for trees and forests
We start with introducing our algorithm CN-UCB (Algorithm when the causal graph D is a directed tree. Before diving into details, summarize our results follows:
Theorem
(Regret
Guarantee for Algorithm
Define
B
max
32 A
log
8n
2 log [n2 }} and Ti = KB + d) log n, where
< 8 < 1.
For multiple reward generating variables cases, one can repeatedly run our proposed algorithms and recover each them one by one. We discuss this setting Section Observvatioal data is usually much more cheaper than interventional data GGrennealld et al. 2019).

---

Suppose we run CN-UCB with T > Ti interventions in total and T2 == T Tı. Then with probability least 6. we have
R Ō max
1 A2 d(logn) n)² VKT)
where d == dmaxx (sceleeot))))) and Ô ignores poly-log terms non-regarding
From above results, we see that especially for large n. and small maximum degree d, Algorithm outperforms the standard MAB bandit approaches that incur O(vnkT regret.
4.1 Description for CN-UCB
Our method contains three main stages. There no v-structure directed tree, so the essential graph obtained from observational data is just the tree skeleton To and we take it as our input in Algorithm ||
In stage 1, Algorithm interventions on central node (may change over time) on the tree skeleton. stage 2, Algorithm| |
I calls Algorithm to find directed sub-tree To that contains X by performing
calls Algorithm 4 to find the reward generating node X by central node interventions on To. We UCB prove that X n can be identified correctly with high probability from the first two stages, algorithm can then be applied on the reduced intervention set Ar = {do(X = k) k , for the remaining rounds in stage 3. In the remainder of this section, explain our algorithm design for each stage in detail and use an example in Figure T to show how CN-UCB proceeds step by step.
X₁
Stage 0): intervention central node X2.
(a) True causal tree.
(b) Input tree skeleton.
X
(d) Stage 1 (f 0) intervention
(c) Stage (t 1): intervention central node X3-
(f) Stage 1 (t 1) intervention result.
result.
X
X
XR
X
X
X
(g) Stage output: di- (h) Stage 0): rected subtree.
(i) Stage 2 (l 0): in-
Stage output: only X7 remains.
(j)
intervention on central terventions on the chil- node X3.
dren of X3.
Figure 1: Causal Tree Example for CN-UCB procedure.
In the beginning of CN-UCB, we collect reward data under empty intervention to obtain the observa- tional reward mean estimate R, which will be used in later steps to check whether a variable is an ancestor of the true reward generating variable X or not.
In our example, the true causal graph and its essential graph are displayed in Figure and Tb. where the true reward generating variable is X7.
5

---

Algorithm 1 Central Node Upper Confidence Bound (CN-UCB)
1: Input: Tree skeleton To. K, A, B, T2, observational probabilities P(X).
2: Perform do() for B times, collect Ri..... RB
3: Obtain reward estimate for the empty intervention do(): : R 4 B > Rs.
E, 4: Stage 1: Find directed subtree that contains XR: To f Find Sub-tree(To- K, B, E, A, R).
//call Algorithm 3 in Section
B
5: Stage 2: Find the key node that generates the reward: X +- Find Key Node To. K, B, A,
//call Algorithm 4 in Section
6: Stage 3: Apply UCB algorithm on Ag {do(XR= k) lo 1, K} for 22 rounds.
Stage 1. The goal of this stage is to find a directed subtree that contains XR within ( n) single-node interventions. We achieve this goal by adaptively intervening the central node that may change over time. To illustrate our main idea, we make the following claim for songle-node interventions.
Claim 1 (Two outcomes from single-node interventions on variable X). 1) Whether X is an ancestor of X R or not can be determined. 2) The directed subtree induced by X as its root can be found.
To see the first outcome, we obtain reward estimates under interventions over X. the difference between any of the reward estimates and R is larger than a threshold, Assumption 3 guarantees us that X is an ancestor of XR-
To see the second outcome, we estimate interventional probabilities P(Y y)do(X = x)) for all Y E Nx.()) and y. x E [K]. Comparing these quantities with the corresponding observational probabilities P(Y y). the directions of edges between X and its neighbors can be determined due to Assumption X while others are all causally influenced by X. Once the edges between X and its neighbors oriented, all other edges in the subtree induced by X (as the root) can be oriented using the property that each variable has at most one parent in a tree structure. Thus, if we learn that X is indeed an ancestor of X XR. directed subtree can be obtained immediately. Otherwise, we conclude that all the variables in the directed subtree induced by X cannot be X
2 Note that in a tree structure, at most one of the neighbors has causal effect on
Then a key question is: how do we adaptively select which variables to intervene? Arbitrarily selecting variables may easily require (n) single-node interventions. For example, let us consider graph X1 + X2 -....- + Xn and the reward generating variable is X,, If we start from intervening on Xx, and everytime move one-node backward towards intervening X1, we need O(n) single-node interventions in total to figure out the directed subtree containing X₃- To overcome this issue, we adopt the idea of central node algorithm proposed by Greenewald et al. (2019). Interventions central node (t) guarantees us to eliminate at least half of the nodes from future searching, because the directed subtree induced by v.)()) contains more than half of the nodes regarding to the current weighting function qe (.). And as long as (i(()) is not found as an ancestor of Xn, the weights 1 (-) for variables in the directed subtree induced by (f) the root will be set zeros. Thus, stage 1 can finish within (log n)) single-node interventions on To-
For the example in Figure I CN-UCB takes the tree skeleton in Figure lb as its input and identifies X₂ as the central node. As Figure Id shows, the directed subtree induced by root X₂ are crossed out from the candidate set for X since intervening on X2 shows that X₂ is not ancestor of the true Xg. CN-UCB then identifies X3 as the central node over the remaining variables(Figure [e). We will see Xg is indeed an ancestor of X7 from interventions because X, is on the upstream direction of X3 and cannot be the true Xn (Figure Tf Finally, stage 1 outputs the directed subtree in Figure Tg whose root is X3-
Xg. Thus, X, can be crossed out
The goal of this stage is to identify Xa in the directed sub-tree To within Olog n) single-node interventions. Similar to stage 1, we determine whether node X is an ancestor of Xa by performing interventions on it. If we find a variable X that not an ancestor of X according to its reward estimates, all nodes in the sub-tree induced by X can be eliminated from future searching. Otherwise, we continue to intervene on the children of X. Since X is unique, at most one child Y Ch(X) is ancestor of Xg. If such Y exists, repeat above procedure on the directed
Stage 2.

---

sub-tree induced by Y as the root and update weights for all other variables as zeros in the algorithm. Lastly, if none of the children E Ch(X) appears to be an ancestor of X X itself must be Xx.
We again perform intervention on the central node at the beginning of each round in Algorithm and intervene on its children if necessary. By the definition of central node, every round we can either eliminate at least half of the nodes or finish searching for XR. Thus, stage 2 can be finished within ( log, n) single node interventions on To, since the central node at each round has at most children.
For our example, stage 2 identifies X3 as the central node showing in Figure 1h conclude X3 indeed ancestor of X; XR. stage 2 continues to intervene its children X6 and X7 (Figure [i]. From the intervention results we will see that Xy is also an ancestor of the true X R so that X3 and X6 can be removed. Finally, stage 2 outputs X7 with high probability (Figure Lij
With high probability
Stage 3. Once the first two stages output a variable, we simply apply the UCB algorithm over the reduced intervention set defined Algorithm I
4.2 Extension of CN-UCB to causal forest
Generalizing CN-UCB to causal fores doriiede defined in Definition 4 is straightforward. The causal forest version for CN-UCB is presented in Algorithm (Section B We simply run stage and stage 2 of Algorithm D for every chain component (tree structure) of the causal forest essential graph until stage 2 finds the reward generating variable XR with high probability. Then, a standard UCB algorithm can be applied on the reduced intervention set corresponding XR. The regret guarantee for Algorithm is presented in Theorem 2
Theorem 2 (Regret Guarantee for Algorithm 5) Define CDD as the number of chain components in ED). Suppose we run Algorithmm (Section 5) with T >> 2K C(D) log, n := Ti total
interventions and T2 T - Tú, where 0 < and B max x= log (8nk] 2 log Bn² k²
Then under Assumptions 7 2 and 3 with probability at least 1 6, we have
R = Ō K max {
1 11 (d ((D)))(o)) VKT)
(2)
A2 22
where Ô ignores poly-log terms non-regarding and d= maXT)ECC(((D)) dmax (T))
5 Extension of CN-UCB to a general class of causal graphs
In this section, we extend CN-UCB to more general causal graphs. Our approach involves searching for the reward generating node Xa within each undirected chain component of E(D). In order to use the central node idea, we try to construct tree structures on each component.
5.1 Preliminaries for the general graph class
Before describing our algorithm, we first review definitions of clique (junction) tree and clique graph for undirected graph G following Squires al. (020))
Definition 5 (Clique). A clique C C (G) is subset of nodes in which every pair of nodes are connected with an edge. We say a clique C is maximal if for any v E V(G) C. C U {u) is not clique. The maximal cliques set of G is denoted by C(G) with its clique number defined as (G)) = maxcec(a) (C), where |C] denotes the number of nodes in clique C. We use [C(G) to denote the number of cliques in set C()).
Definition 6 (Clique Tree (Junction Tree)). A clique tree To for G is a tree with maximal cliques C(G) vertices that satisfies the junction tree property, i.e. for all & E V (G), the induced subgraph on the set of cliques containing e is a tree. We denote the set of clique trees for graph G by T(G).
Note that in our setting, causal forest refers to type of causal graph. This should not be confused with the causal forest machine learning method which is similar random forest.
7

---

Algorithm 2 CN-UCB for General Causal Graph
1: Input: essential graph {D), A,,,, B, T2, observational probabilities P(t).
2: Initialize: found t- False
3: Perform do() for B times, collect reward data Ri...... Rg: R
2 Rs-
4: for G E (D) do
5: Stage 1: Create a junction tree To and find directed sub-junction-tres tree that contains X 7 in Section
To Find Sub-junetion-treee(C; To, K, B, It). //call Algorithm
6: if Ta not empty then
7: Stage 2: Find a clique in To that contains XR: Co <-Find Key Clique (Ta. K, B, A, Mt
/ccall Algorithm
8 in Section B
8: Stage 3: Apply UCB algorithm on Ac. = {do(X- = k) T2 rounds.
X E V(Co), k 1...., K for
9: return Finished.
10: end if
11: end for
12: return No clique that contains Xn is found. Apply UCB algorithm on the entire action space
A = {do(X = xx) X E Xx x E [K]].
Definition 7 (Clique Graph). A clique graph a is the graph union TGG), i.e. = and (T) = UTET(G;U(T)) where U-) denotes the set of undirected edges.
Definition (Directed Clique Tree). directed junction tree TD of a moral DAG D has the same vertices and adjacencies
clique tree To of G skeleton(D)) (D). We use asterisks as wildcards for edge points, e.g. X₁* + Xj denotes either X, + Xj or X, ++ Xj. For each ordered pair of C2 we orient the edge mark of C2 as: 1) C1* C2 f012 C1 C2
adjacent cliques C1
Vu12
and Yuz E C2 \ C1 we have U12 - U2 in the DAG D or 2) C1 C2 otherwise.
Definition (Directed Clique Graph). The directed clique graph D of a moral DAG D is the graph union of all directed clique trees of D. The procedure of graph union is the same Definition B
Definition 10 (Intersection Comparable (Squires et al. 2020)). A pair of edges C C1 and C2 C3 on a clique graph are intersection comparable if
C2n or C1 nC, 2 C2 ng.
chordal graphs were introduced as "uniquely representable chordal graphs" in Kumar and Madhavan (2002). This class includes many familiar graph classes such as causal trees, causal forests and proper interval graphs (Squires et al., (2220.. A clique graph is said to be intersection inersection-innomaaabbbl if above intersection-comparate of edges. In this section, we design our algorithm for general causal graphs for every chain component G CC(E(D)), the corresponding clique graph Ie is intersection-inconn -inooppainn prove that our algorithm can achieve improved regret guarantee.
intereectonnincomppann
relation does not hold for any pair
5.2 CN-UCB for general causal graphs
Our approach for causal bandit problems with general causal graphs is similar as previous settings. We try to find subset of variables Xgub that contain the true reward generating node Xn with high probability and then apply UCB algorithm on interventions over Xaubb
Our method is presented in Algorithm We search for X in every chain component G E CC))(D)) separately. In stage 1, we create a junction tree To and search for a directed sub-junction-tre To that contains R via Algorithm 7 If such a TG exists, we keep searching for a clique Co in To that contains X R in stage 2 via Algorithm and apply UCB algorithm on single-node interventions over variables in Cp. Otherwise, we repeat above procedure for the next chain component.
Stage and stage 2 in Algorithm 2 also use the idea of central node interventions. But different from previous settings, Algorithm and Algorithm proceed by performing interventions on variables in the central clique that changes over time and every central clique intervention can eliminate at least half of the cliques on To To from future searching. A central clique for junction tree is defined the same way as central node for a tree that we just treat the cliques on junction tree as the "node" in Definition 2

---

Remark on the intersection-ineompaaae property. We now explain why we need the cntrssectionincomaaat property like other central node based algorithm that also involves con- structing clique graphs (Squires et al. 2020). In general, it is possible for directed junction tree T to have v-structures over cliques, which can make us unable finish searching for a directed sub-junction-tre that contains X R by intervening denotes the number cliques on T. The reason is, clique node may have more than one clique parents in T, so that cannot eliminate more than half of the cliques by interventions over the central clique. In total, we may need to perform (n)) single-node interventions to find XR R and incur (n) regret. However, for every chain component G of the essential graph, if its clique graph then there is no v-structure over cliques in any junction tree To of G' (Squires al. 2020), i.c. every node has at most one parent node.
variables in Oloog (T] cliques, where 'T]
Ig is pntersecttoo-incompareee
property holds or not. If the property does not hold, Algorithm may output nothing at line 5 or line 7 for all component G CC()(D)) (will not output an incorrect sub-junction tree or clique by its design). Thus, if the learner finds that Algorithm 2 does not output anything after line 5 or 7 for all components, standard UCB algorithm can be used on the entire action set (see line
Algorithm can take any graph input no matter whether intereectionincoopper
12 in Algorithm 2
Theorem 3 (Regret guarantee for Algorithm 2 ( is intersection-incompariii for all G CC(E(D)) Define O < 5 < 1 and B = max
32
log
8nK
2 log
8m2 } Suppose
we run Algorithm for T > B + K log2 (G(n)) + dG) + EGECcte(D) w(G) ;= Ti
total number of interventions and T2 == T Tí. Then under Assumptions at least 5, we have
and with probability
Ri
δ d(Ton))(GRR)+
Σ GECC(E(D))
w(G)
K max
1 A2 E²
1
log n log Cmax Vw(GR)KT
where d(TGR) denotes the maximum degree of junction tree TG GR denotes the chain component that contains the true Xn and Cmux A mmxxGECCE((D)) (C(C))EEE))))()))))))))))))))))) Ō(-) ignores poly-log terms non- regarding to n or number of cliques.
Above regret bound shows that our algorithm outperforms standard MAB algorithms especially when n is large and the degree d(Tag) and the clique numbers (G)) are small Also, above result reduces Theorem 2 when D is a causal forest, because (GG) is always 2 for tree-structure chain components.
Lower bounds
In this section we show without Assumption 2 or 3 any algorithm will incur an Q (VnkT) regret in the worst-case, which is exponentially worse than results in terms of n.
Definition (nK arm Gaussian Causal Bandit Class). For a bandit instance in nKKarmm -arm Gaussian causal bandit class, actions
composed by single-node interventions over n variables X (X1,-..X,, Xx): : A = {do(X; X;; = [x E [K] n. with |A| = =nK. The reward for every action is Gaussian distributed and is directly influenced by one of X.
Theorem (Minimax Lower Bound Without Assumption Let be the set of nK -armed Gaussian bandits (Definition 77 where the instances in & does not satisfy Assumption 2 We show that the minimax regret inf ren suppes E. (n, v)] (VVKTT) where II denotes the of all policies.
Theorem 5 (Minimax Lower Bound (Assumptionn 2 hholds but Assumption Booes not hold)). Let & be the set of nK-armed Gaussian bandits (Definition) 17 where the instances infrem En supree [E [[[ v))
satisfy Assumption
but does not satisfy Assumption 3, We show that the minimax regret is inf
Ω / nKT), where II denotes the set of all policies.

---

7 Discussion
In this paper. we studied causal bandit problems with unknown causal graph structures. We pro- posed an efficient algorithm CN-UCB for the causal tree setting. The regret of CN-UCB scales logarithmically with the number of variables n when the intervention size is nK. CN-UCB was then extended to broader settings where the underlying causal graph is causal forest or belongs to general class of graphs. For the later two settings, our regret again only scales logarithmically with Lastly, we provide lower bound results to justify the necessity of our assumptions on the causal effect identifiability and the reward identifiability. Our approaches are the first set of causal bandit algorithms that do not rely knowing the causal graph in advance and can still outperform standard MAB algorithms.
There are several directions for future work. First, one can generalize CN-UCB to the multiple reward generating node setting, i.e., more than one variable directly influences the reward. We expect this can be done by repeatedly applying stage and 2 in CN-UCB to find all the reward generating nodes one by one and apply a standard MAB algorithm on the reduced intervention set. this setting, is natural to consider interventions that can be performed on more than one variables. Second, it will interesting to develop instance dependent regret bounds, example, through estimating the probabilities over the causal graph in CN-UCB. Lastly, one can also develop efficient algorithms that do need know the causal graph when confounders exist.
Acknowledgement
We thank NeurIPS reviewers and meta-reviewer for helpful suggestions improve the paper.
Funding transparency statement
Funding (financial activities supporting the submitted work): Funding in direct support of this work: NSF CAREER grant IIS- 1452099, Adobe Data Science Research Award.
Competing Interests (financial activities outside the submitted work): None
10

---

References
Abbasi- Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320.
Abbasi-Yadkorts Y., Pal, D., and Szepesvari, C. (2012). Online-to-confideneesstt conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9. PMLR.
Agrawal, S. and Goyal, N. (2012). Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 39-1.
Agrawal, S, and Goyal, N. (2013a). Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pages 99-107. PMLR.
Agrawal, S. and Goyal, N. (2013b). Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135.
Andersson, S. A., Madigan, D., Perlman, M. D., et al. (1997). A characterization of markov equivalence classes for acyclic digraphs. Annals of statistics, 25(2):505-541
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-22 256..
Burgos, E., Ceva, H., Hernandez, L.., Perazzo, R. P., Devoto, M., and Medan, D. (2008). Two classes of bipartite networks: nested biological and social systems. Physical Review E, 78(4):046113.
Cesa-Bianchi, N. and Lugosi, G. (2012). Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1422.
Combes, R., Talebi, M. S., Proutiere, A., and Lelarge, M. (2015). Combinatorial bandits revisited. arXiv preprini arXiv: 550.003455
de Kroon, A. A., Belgrave, D., and Mooij, M. (2020). Causal discovery for causal bandits utilizing separating sets. arXiv preprint arXiv:2009.077 07916.
Eberhardt, F. (2017). Introduction to the foundations of causal discovery. International Journal of Data Science and Analyties, 3(2):81-91.
Greenewald, K.,, Katz, D., Shanmugam, K., Magliacane, S., Kocaoglu, M., Adsera, F. B., and Bresler,
G. (2019). Sample efficient active learning of causal trees. In Advances in Neural Information Processing Systems, pages 14302-14312.
He, Y.-B. and Geng, Z. (2008), Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov):2523-2547,
Hyttinen, A., Eberhardt, F., and Hoyer, P. O. (2013). Experiment selection for causal discovery. The Journal of Machine Learning Research, 14(1):3041330)
Jordan, C. (1869). Sur les assemblages de lignes. J. Reine Angew. Math 70(185):81.
Kocaoglu, M., Dimakis, A., and Vishwanath, S. (2017). Cost-optimal learning of causal graphs. In International Conference on Machine Learning, pages 1875-1884, PMLR.
Kontou, P. I., Pavlopoulou, A., Dimou, N. L., Pavlopoulos, G. A., and Bagos, P. G. (2016). Network analysis genes and their association with diseases. Gene, 590(():68-77 78.
Kumar, P. S. and Madhavan, C. V. (2002). Clique tree generalization and new subclasses of chordal graphs. Discrete Applied Mathematics, 117(1-3):109-15 1111
Lattimore, F. Lattimore, T., and Reid, M. D. (2016). Causal bandits: Learning good interventions via
causal inference. In Advances Neural Information Processing Systems, pages 1181-1189.
Lattimore, T. and Szepesvári, C. (2018). Bandit algorithms. preprint.
Lee, S. and Bareinboim, (2018). Structural causal bandits: where to intervene? In Advances in Neural Information Processing Systems, pages 2568-2578.
Lee, S. and Bareinboim, E. (2019). Structural causal bandits with non-manipulable variables. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4164
I Lindgren, F. M., Kocaoglu, M., Dimakis, A. G., and Vishwanath, (2018). Experimental design for cost-aware learning of causal graphs. arXiv preprint 1xvv:1810.1188
11

---

Liu, S., See. K. C., Ngiam, K. Y., Celi, L. A., Sun, X., and Feng, M. (2020). Reinforcement learning for clinical decision support critical care: comprehensive review. Journal of medical Internet research, 22(7):e 18477.
Lu, Y., Meisami, A., Tewari, A., and Yan, Z. (2019). Regret analysis of causal bandit problems. arXiv preprint arXiv: 100:::90000000 00.4498.
Nair, V., Patil, V., and Sinha, G. (2021). Budgeted and non-budgeted causal bandits. In International Conference on Artificial Intelligence and Statistics, pages 2017-2025. PMLR.
Pavlopoulos, G. A., Kontou, I., Pavlopoulou, A., Bouyioukos, C., Markou, E., and Bagos, P. G. (2018). Bipartite graphs in systems biology and medicine: a survey of methods and applications. GiguScience, 7(4):giy014.
Peters, J., Mooij, J., Janzing, D., and Schölkopf, B. (2012). Identifiability of causal graphs using functional models. arXiv preprint arXiv:1202.38
Sen, R., Shanmugam, K., Dimakis, A. G., and Shakkottai, (2017). Identifying best interventions through online importance sampling. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 3057-3066. JMLR. org.
Shanmugam, K., Kocaoglu, M., Dimakis, A. G., and Vishwanath, S. (2015). Learning causal graphs with small interventions. arXiv preprint arXiv: 151110001..
Squires, C., Magliacane, S., Greenewald, K., Katz, D., Kocaoglu, M., and Shanmugam, K. (2020). Ac- tive structure learning of causal dags via directed clique tree. arXiv preprint arXiv:2011.0066 1.0441..
Wikipedia contributors (2021).
Wikipedia, the free encyclo- https://ent www.wiiiiiiee. httpp/edaa...g//////oa..m wttp///g/////..////////e/// http:://ww.ddde...pttttteeeeeeee pwtptpttleeeeeeeetiiii..
Genetic engineering
pedia.
[nggmeeeriiggoll.111111119922229 09922011
[Online; accessed 26-April-2021).
12


Reviews:
[{"review_id": "mL7bGwTKUO0", "reviewer": "Reviewer_sHAH", "summary": "The authors present a novel approach to tackle so-called causal bandit problems where the structure of the underlying graph is unknown. The algorithm is based on a ‘central node’ approach to find the direct parent of the reward as soon as possible. Under certain restrictions various regret bounds are derived for this algorithm that show the asymptotic behaviour outperforms standard multi-arm bandits by a significant margin, though no experimental verification is provided.\n", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem considered in the paper is indeed challenging and relevant, and has so far not received the attention it deserves. \n\nUnfortunately, despite some nice results on regret bounds, the execution in the paper falls far short of what is promised at the outset. The end result is very disappointing and I consider it a missed opportunity.\n\nOn the plus side, the paper technically does provide a causal bandit approach for unknown causal structure that outperforms standard MABs, and it does offer some nice results on regret bounds. However it does so by invoking such strong restrictions and assumptions that it effectively kills the problem it set out to solve.\n\n- Essentially it is a standard ‘balanced split’ search method that is then presented as a ‘causal bandit approach’ by restricting the class of allowable causal models so far that the proposed search method works. These restrictions/assumptions reduce the problem to a trivial case (tree like where all ancestors have measurable impact on the reward) with little hope for any real-world situation to fit the problem. And there is little hope of adapting the method to more realistic causal structures, as the core of the method has little to do with causality or causal structures in the first place.\n\n- The ‘with unknown graph structure’ from the title turns out to involve full knowledge of the equivalence class representation of the model after all. And then it is supposed to be of a very specific type as well. \n\n- The ‘causal sufficiency’ part of assumption 1 is disappointing as in practice the larger the graph the more likely we are missing some relevant confounders. For a principled causal bandit approach this should not erven be necessary, but ok. Causal faithfulness is not needed for the current task (provided assumption 2 holds).\n\n- The assumed ‘causal tree / forest’ structures are extremely limiting cases of the general class of all  possible causal structures (with or without sufficiency). Worse, the then introduced ‘general class of causal graphs’  (section 5) turns out to be almost as restrictive. In other words: only if the causal bandit system under investigation happens to satisfy an extreme configuration can we apply the method presented here. And for large graphs the chance that any random causal structure will satisfy this condition is virtually negligible.\n\n- Assumption 3 however is the most extreme and completely unrealistic in practice, especially if the (assumed) tree graph is large. It states that all ancestors of the reward function have a measurable impact on it. However, in practice long directed chains tend to result in extremely weak dependencies that will remain undetectable even with huge amounts of data. \n\n- Even worse: under the extremely strong assumptions in the paper the problem can be solved much more quickly than with the algorithm presented, because as soon as there is an intervention on ANY of the ancestors of the reward function in stage 2 of the algorithm, its single direct parent can be found immediately by virtue of assumption 3: it will simply be the variable that shows the strongest dependence with the actual reward. No other tests are needed … which also indicates how niche and limiting the current setup is.\n\n\noriginality: novel approach but still fairly derivative\nquality: main results (Theorems 1-3 and CN-UCB algorithm) are technically correct. However the method is seriously miss-sold as a ‘general approach under mild conditions’, and despite the ‘unknown graph structure’ claim in the title, the first line of the algorithm starts with having the graphical equivalence class representation of the true causal structure: that is just not good enough. Also no experimental evaluation is provided. \nclarity: writing is ok, with some minor flaws. Some good examples, but far too much emphasis on the straightforward ‘tree/forest’ case (7 pages) leaving nowhee near enough space for the general case (5.2) and lower bounds (section 6). \nsignificance: the approach is too niche and weirdly restrictive, making it unlikely to generate much interest from the (causal) bandit community. In fact it hardly deserves the moniker ‘causal’ at all, and is in many respects a missed opportunity.\n\n\nminor comments:\np3.125: ‘Every directed edge in E(D) is within a v-structure’ => this is wrong. It is true that every v-structure corresponds to a directed edge in E(D), but other invariant directed edges are also possible.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No direct societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hrs"}, "extra_text": {}}, {"review_id": "Wx9c3Gk_OEb", "reviewer": "Reviewer_xwY7", "summary": "This paper investigates the problem of 'causal bandits,’ a sequential decision problem where the agent can intervene on a causal DAG (setting the value of a variable) and receives a reward associated with an unknown variable’s value.  Unlike prior works, in this paper, only partial prior knowledge of the structure is known (essential graph).  In addition to the reward, the agent also observes the realization of all the variables; that information with the essential graph helps inform the agent of where in the graph the reward-generating variable is.   Although the agent need not learn the full causal structure for the task, prior work on causal structure learning provides an algorithmic foundation for approaching the causal bandits problem.  Regret bounds for the algorithms are provided for trees, forests, and then general graphs (which satisfy certain topological constraints).  Lower bounds are also provided.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major Comments\n•\tOverall I found the paper quite interesting.  As the authors are upfront about, the algorithm design largely builds on central-node procedures for learning the causal structure.  Especially for trees and forests, that approach is at a high-level intuitive and the authors demonstrate effective.  As the authors point out, for the causal bandit problem, you only need to learn enough about the structure to identify with high confidence what region of the graph contains that variable; eg it is suboptimal to have one stage where you fully learn the graph and then search for reward-generating variable.  \n•\tIn terms of contribution, if the focus were just on trees, that might not have been enough, but the authors extend the algorithms to a class of general graphs, though point out limitations of central-node procedures in that case. \n•\tThere are no empirical results, which I think is ok given the analyses, though even simple experiments could further improve.\n•\tThe paper adopts terminology and notation from Greenewald et al., but it should nonetheless be self-contained; for instance, q() shows up in Definition 2 without any description beyond being ‘a distribution over nodes’; `a weight of a branch’ not explained, what a ‘central node’ is and why it changes is confusing at first (the nodes themselves are not; eg topology is static). While the high-level search strategy is communicated (Fig 1 is helpful), I don’t think some of the important details of how that is done are.\n\nMinor comments\n•\tline 6-7 ‘In this paper, we develop novel causal bandit algorithms without knowing the causal graph. Our algorithms work well for causal trees, causal forests and a general class of causal graphs.’  Slightly misleading, should qualify in abstract that the algorithm knows the essential graph.  \n•\tFor causal bandits, while it looks common to assume there is a single reward-generating variable, it sounds quite limiting.  The authors discuss this in part in Footnote 2 – the statement does not seem obvious to me though if they mean there is a single reward that depends on multiple variables.  If they mean that there are multiple observable rewards, each of which depends on a distinct single variable, then it is trivial.   If the former is meant, wouldn’t the reward function need to have quite special properties?\n•\tMinor issue, but line 140 discusses optimal intervention before the objective function introduced, line 143 uses Y which is not introduced, $X_t$ not defined\n•\t(very minor) Assumptions 2 and 3 – it is clear that both properties are needed, though I was a bit surprised that Assumption 2 does not imply Assumption 3 (though the dependence of \\Delta on \\epsilon, the graph topology, and P may be complicated).  I did not look at the appendix for the lower bound proof that contains an example, but if there is a simple high level explanation of why not, it might be worth mentioning.   \n•\t(minor) Claim 1 is imprecise – what does it mean to be ‘determined’ or for the subtree to be ‘found’?  that there is a number of interventions that is sufficient for exact structure recovery  with high probability ?\n•\t(very minor) $B$ used for branch in graph and algorithm parameter (Theorem 1)\n•\tLastly, I think some discussion, even high level, of per-round computational complexity would be beneficial.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes (while there are potential applications of this idea to the sciences, this work itself is theoretical)", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "U0FyZyxMiV", "reviewer": "Reviewer_Em8x", "summary": "Authors propose using the existing adaptive causal discovery algorithms to identify the reward variable in a causal graph efficiently and then run the existing bandit algorithms on this very small space of actions (interventions). They use the ideas from central node algorithm of Kristjan et al.: Identify a central node, either eliminate ~half the graph or find the subtree including the target node. They then have to check each child separately since either one of them can be the target node - which also serves as a method to check if central node itself is the target node. This takes ~dlogn interventions which can easily be converted to sample-complexity with the resorted assumptions. \n", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The two assumptions that are somewhat restrictive are the tree and in the next section intersection comparability assumption which was made by Squires et al. and that there is only a single node that affects the reward function. Despite these, I think this is a very nicely done first effort in this space of combining causal discovery with bandit algorithms. \n\nAuthors also show necessity of the assumptions by constructing counterexamples based on Lattimore's results. I think these are very important and insightful results and I am glad the authors included those. \n\nMinor comments:\n- Footnote seems to be hinting at that single X_R assumption is wlog. Is this true? Please elaborate on what fails or if it is. Discussion at the end seems to suggest this is only a tentative idea. Please clarify in the text as well.\n- Causal faithfulness definition is not precise, please check. It should say \"... has ONLY the independence relations\". missing only completely changes meaning here. \n- Directed tree assumption is indeed motivated by essential graph here but this is not explicitly stated in page 3 which makes the assumption look more restrictive than it actually is. \n- Essential graph definition in page 3 has an issue: It doesn't only involve edges that are part of v-structures but also those implied by Meek rules. E.g. X->Y->T + Z->T is the DAG and the essential graph since Z->T can be identified by the first Meek rule. \n- abstract: MAB bandit->MAB.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "55UDzKDoBoV", "reviewer": "Reviewer_d51G", "summary": "The paper presents a causal bandit algorithm for graphs with unkown causal structure (but no unobserved confounders). It is based on a couple of recent results in learning causal graphs using interventions, and previous causal graph work. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Authors provide an algorithm for causal bandits with logarithmic regret with a graph of unknown structure. Unlike causal graph setting, where the goal is to learn the whole graph, in causal bandit setting it is unnecessary, which is one major difference between this and previous work on causal graph structure. I am not aware of the previous causal bandit work that can achieve this on unknown graphs. Thus combining the two approaches is the novelty of the paper.\n\n Their assumptions are:\n\n-Standard graphical causality assumptions\n\n-No hidden confounders (also standard -- while most applications will have hidden confounders, proving anything in their presence gets much harder).\n\n-Underlying graph's clique tree has intersection-incomparible property. This last assumption is the least common of the three, and something that would be great to relax if possible or further justify. It is also present in previous work on causal graphs which this work is based on.\n\nI did not check the proofs in the Appendix carefully, and assumed for this review that proofs hold. They seem to hold \"intuitively\", so I would be surprised if they do not, but can not vouch for that.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact: similar to other papers in the field, so I don't think much new has to be said.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "3UAkQe2tYHe", "reviewer": "Reviewer_25sC", "summary": "This paper gives low-regret algorithms for the causal bandits problem when the graph structure is unknown. The main contribution is in combining use of some recent results on efficient causal structure discovery with traditional UCB approaches. Some minimax results are given to demonstrate the necessity of the assumptions made. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality\n+ The use of the causal discovery results by Greenewald et al. (19) and Squires et al. (20) within the context of a targeted structure discovery problem is a very nice idea. An assumption on there being some kind of tree structure (either a graph that is a forest or junction tree), allows the proposed algorithm to be more efficient than a naive application of these structure learning approaches, because they disregard parts of the tree as soon as they are found not relevant to the reward. \n+ To my knowledge this is the only work on causal bandits where the causal graph structure is unknown. \n\n### Quality\n+ The assumptions are intuitive and the results of section 6 reinforce their importance. \n- No consideration is given regarding the computational complexity of selecting each intervention. This seems like something that could at least be commented on for the various stages of Algorithm 1. \n- Would be nice to see a comment on how well these ideas might extend to continuous random variables, in particular linear bandits. \n- Other works I've seen on this area have included some experimental results on simulated data. I think there would certainly be some value in those here: demonstrating practical implementation of the proposed algorithms; considering the effect of graph structure on performance; performance when the identifiability assumptions break; performance when the intersection-incomparable assumption doesn't hold on the clique graph. Relevant baselines would be UCB and existing algorithms that get given the graph structure. \n\n### Clarity\n+ Description of the results, especially for tree graphs, is very clear and easy to follow. Figure 1 is great for following the algorithm explanation. \n- It could be made more clear exactly what assumptions are allowing us to improve over UCB in terms of sample efficiency. It seems that it is because of both the assumptions on having some non-degenerate graph structure and that we get side feedback on the values of nodes, which is not present in the typical bandit problem. These assumptions are just as important to understanding the results as the well emphasised assumptions on identifiability. \n- I think it is worth acknowledging that whilst previous works are limited in assuming knowledge of the causal graph, they do also address various settings which would be considered natural extensions to this paper. For example Lu et al. (19) consider interventions on multiple variables simultaneously, and the linear bandit setting. \n- line 350: does -> do. \n\n### Significance\n+ Causal bandits is a problem area that has received a fair bit of attention in the last few years, and good guarantees for the setting of an unknown graph structure is a significant contribution to the field. \n+ The minimax results also offer progress on understanding what assumptions are necessary to achieve interesting regret bounds for causal bandits when the graph structure is not known. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No broader impact statement is given here but it isn't really necessary in this case.  The scope of the work was generally clear and some nice directions for future work were given. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviews are extremely favorable except one dissenting review.

This paper produced a very long discussion and engagement between dissenting reviewer, other reviewers and authors. I would like to thank all reviewers (especially the dissenting reviewer) for participating in the discussion.

I would like to state the main points of the dissenting review  and I feel that the discussion and authors final responses does address most of the serious concerns raised. Therefore, I am recommending acceptance. 

Particularly, this is the first paper (I am aware of) that solves regret minimization problem for causal bandits when only the equivalence class is known. The authors leverage existing structure learning results to obtain an algorithm that ensures non trivial regret (non trivial regret guarantee holds under some technical conditions).

Main points from the dissenting review - followed by paraphrased answers from either the authors/other reviewers.

a) First step requires having the full equivalence class graph available

A) many other works in active structure learning literature makes these assumptions. This paper considers a harder problem of regret minimization without full structure knowledge, this would be not be a major penalizing factor. Besides, interventionally it does not cost anything to assume one has enough observational samples. Therefore, it is a resonable assumption.

b) "unknown graph then needs to satisfy some extremely restrictive properties"

A)  Authors assume intersection incomparable property on the clique tree decomposition of the observational markov equivalence class. The property assumed can be tested with only the equivalence class which is an input to the bandit.

 Nevertheless, this is a popular assumption - both in structure learning and some prior literature. Another reviewer even hinted that in a random graph, this may be satisfied even with high probability (or at least depends on random graph model assumptions). This is satisfied with popular chordal graph sub families.

Other aspect is that the bandit algorithm would run irrespective of the assumption. It would halt at a specific line and then the bandit part of the algorithm would commence with potentially large number of arms.

*Note to authors*: I would urge the authors to note this point explicitly in camera ready and provide a complete algorithm with the halting conditions etc...

Not withstanding the above, it is an assumption to avoid a 'pathology' (in my opinion) in the clique tree.

c) The claimed regret bounds in Thm2+3 are misleading in that an order N dependence is hidden in a constant that actually scales with N

A) All regret bounds in MAB problems scale with problem parameters - ambient dimension in linear bandits, number of arms in multi armed bandits, some graph parameter when DAG is known in causal bandits. Here, this is number of chain components in the chordal graph which is a parameter that depends on the EC. If all nodes are isolated this would reduce to standard MAB and therefore such a regret scaling would be unavoidable.



Decision: Accept (Poster)