Linear Causal Bandits: Unknown Graph and Soft Interventions

Authors: zirui  yan
ali  tajer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:42:18

Abstract: Designing causal bandit algorithms depends on two central categories of assumptions: (i) the extent of information about the underlying causal graphs and (ii) the extent of information about interventional statistical models. There have been extensive recent advances in dispensing with assumptions on either category. These include assuming known graphs but unknown interventional distributions, and the converse setting of assuming unknown graphs but access to restrictive hard/$\operatorname{do}$ interventions, which removes the stochasticity and ancestral dependencies. Nevertheless, the problem in its general form, i.e., _unknown_ graph and _unknown_ stochastic intervention models, remains open. This paper addresses this problem and establishes that in a graph with $N$ nodes, maximum in-degree $d$ and maximum causal path length $L$, after $T$ interaction rounds the regret upper bound scales as $\tilde{\mathcal{O}}((cd)^{L-\frac{1}{2}}\sqrt{T} + d + RN)$ where $c>1$ is a constant and  $R$ is a measure of intervention power. A universal minimax lower bound is also established, which scales as $\Omega(d^{L-\frac{3}{2}}\sqrt{T})$. Importantly, the graph size $N$ has a diminishing effect on the regret as $T$ grows. These bounds have matching behavior in $T$, exponential dependence on $L$, and polynomial dependence on $d$ (with the gap $d\ $). On the algorithmic aspect, the paper presents a novel way of designing a computationally efficient CB algorithm, addressing a challenge that the existing CB algorithms using soft interventions face.

Main paper: 
 motivation & overview: 
 Causal bandits (CBs) provide a formal framework for the sequential design of experiments over a network of agents with causal interactions. The objective of CBs is to identify an experiment that maximizes a notion of utility over the causal network. CB settings are specified by three elements: (i) a causal graphical model that defines the topological ordering of the causal variables and their probabilistic relationships; (ii) a set of structural equation models (SEMs) that specify their causeeffect dependencies among the variables; and (iii) intervention models that specify the extent of exogenous variations imposed on the causal interactions by an external force. By interpreting the set of interventions as the set of arms and the decision quality (utility) as the rewards, CBs' objective is to maximize the cumulative reward by strategically selecting the sequence of interventions that optimize a notion of cumulative utility [1, 2] . CBs have a broad range of applications [3] [4] [5] .The recent advances in CBs can be grouped based on three assumption dimensions: (i) the assumptions on the extent of information available about the causal graph structure, (ii) the assumptions about preand post-intervention statistical models, and (iii) the nature of the SEMs. There have been significant advances in understanding CBs when the causal graphs are known. The most relevant studies include those that started with analyzing do interventions as the simplest form of interventions [1, 2, 6, 7] and have progressed toward the more complex stochastic interventions (hard and soft). These studies have investigated various linear and non-linear SEMs. Specifically, the studies in [8] [9] [10] [11] [12] [13] assume that the pre-and post-interventional statistical distributions are known. The study in [14] further advances the results by assuming that these distributions are known only partially, and finally, the studies in [15] [16] [17] [18] entirely dispense with all the assumptions about the interventions' statistical models.In sharp contrast, when the causal graph is unknown, the problem is far less investigated and open in its general form. The lack of topology knowledge makes the problem substantially more complex, since the graph's topology captures all the conditional independence information about the random variables in the system. Hence, when the graph is known, it is unnecessary to learn the conditional independencies; however, when it is unknown, all the conditional independencies should be learned.The notable results under unknown graphs include [19] , which assumes that all interventional distributions are fully known. Dispensing with the assumption of interventional distributions with a focus on do is investigated in [19] [20] [21] [22] [23] [24] [25] . do interventions are generally more amenable to tractable analysis because of the analytical simplifications they enable. A do intervention at a node sets the random value of that node to a pre-specified fixed value. This results in (i) removing all the causal dependence of that node on its ancestors and (ii) removing the randomness of the data generated by that node. In sharp contrast, stochastic soft interventions are the more general and realistic forms of interventions that retain all the ancestral dependencies and the probabilistic nature of the model. A soft intervention, specifically, changes the pre-intervention statistical models to other distinct models. √ T + d + RN soft ✓ - (Theorem 2) Known Graph C-UCB[6] Õ √ K d T do ✓ - LinSEM-UCB[15] Õ d 2L-3 2 √ N T soft ✘ Ω d L-3 2 √ T (Theorem 3) GCB-UCB[18] Õ d 2L-1 √ T soft ✘ GA-LCB (this paper) Õ d L-1 2 √ T soft ✓ (Corollary 1)1 under weaker assumptions.Contributions. We establish upper and lower regret bounds for the CB problem under unknown graphs, unknown pre-and post-intervention statistical models, and soft stochastic interventions. Furthermore, we also provide a novel approach to algorithm design and regret analysis. The main assumptions and contributions of the paper are as follows.• Topology: We assume to know only the number of the nodes on the graph and the in-degree of the causal graph. 1 • Statistical model: We assume that all pre-and post-intervention statistical models are unknown.• Regret bounds: We characterize almost matching upper and lower bounds on the regret as a function of the time horizon and graph topology parameters. Specifically, we show the achievable regret of Õ (κd) L-1 2 √ T + d + N where κ > 1 is a constant, N is the number of graph nodes, d is the maximum in-degree of the graph, L is the maximum causal depth, and T is the time horizon. We also establish the minimax regret lower bound of Ω(d L-3 2 √ T ). • Tightness of the bounds: The dependence of the achievable regret on N is diminishing as T grows. Therefore, the mismatch of the achievable and the minimax regrets is on the order of d and a constant κ L-1 2 . • Special cases: Our general regret bounds provide improvements for the known special cases.In particular, we show that when the graph becomes known, our achievable regret becomes Õ(d L-1 2 √ T ), which is tighter than the best known results Õ(d 2L-1 √ T ) [18] .• Scalabe algorithm: We introduce a novel CB algorithm under soft interventions. We note that the existing algorithms for soft algorithms are based on the upper confidence bound (UCB) principle, and they are generally not scalable due to the intractable optimization problem pertinent to maximizing the UCBs. In our algorithm, we circumvent his issue, resulting in a scalable algorithm as the graph size grows.Notations. For a positive integer N ∈ N, we define [N ] ≜ {1, • • • , N }. Random variables and their realizations are represented by upper-and lower-case letters, respectively. Matrices and vectors are represented by bold upper-and lower-case letters. The i-th element of vector x is denoted by x i . The i-th column vector of matrix A is denoted by [A] i and [A] i,j denotes the (i, j) element of A.A n denotes the n-th power of matrix A for n ∈ N. 1 denotes the indicator function. Sets and events are denoted by calligraphic letters. The cardinality of set A is denoted by |A|. For any set S ⊆ [N ], 1{S} ∈ {0, 1} N is specified such that its elements at the coordinates included in S are set to 1, and the rest are 0. For a vector x and positive semidefinite matrix A, we define ∥x∥ A = √ x ⊤ Ax as the weighted ℓ 2 norm. The ℓ 1 -norm and ℓ 2 -norm of vector x ∈ R d are denoted by ∥x∥ 1 and ∥x∥ 2 , respectively. The notation Õ is an order notation that ignores constant and poly-logarithmic factors. 
causal bandit problem setup: 
 Causal graph. Consider an unknown directed acyclic graph (DAG) G = {V, E} in which V = [N ] is the set of nodes and E is the set of directed edges. A directed edge from node i to node j is denoted by the ordered tuple (i, j). The set of parents of node i ∈ V is denoted by pa(i). Similarly, the sets of ancestors and descendants of node i are denoted by an(i) and de(i), respectively. We define the causal depth of node i, denoted by L i , as the length of the longest directed causal path that ends at node i ∈ [N ]. According, we denote the maximum causal depth of the graph by L ≜ max i∈[N ] L i and denote the maximum in-degree of the graph by d ≜ {max i∈[N ] |pa(i)|}.Data model. DAG G represents a Bayesian network, in which we denote the causal random variable associated with node i ∈ V by X i . Accordingly, we define the random vector X ≜ (X 1 , . . . , X N ) ⊤ . For any A ⊆ V, X A denotes the vector formed by {X i : i ∈ A}. The extents of the cause-effect relationships among the causal variables X are specified by the following linear SEMs:EQUATIONwhere B ∈ R N ×N is the edge weights matrix and ϵ ≜ (ϵ 1 , . . . , ϵ N ) ⊤ denotes the model noises. It is noteworthy that the element [B] j,i is non-zero if and only if j ∈ pa(i). We denote the conditional distribution of X i given its parents by P(X i | X pa(i) ).A soft intervention on node i retains the ancestral dependence of X i on X pa(i) and its probabilistic nature. Specifically, a soft intervention on node i changes the conditional probability P(X i | X pa(i) ) to a distinct one denoted by Q(X i | X pa(i) ). In a linear SEM, the impact of a soft intervention on node i can be abstracted by a change in the vector [B] i . We denote the post-intervention vector by [B * ] i . We refer to B and B * as the observational and interventional weights matrices, respectively. We allow multiple nodes to be intervened simultaneously and denote the space of possible interventions by A ≜ 2 [N ] . For a specific intervention a ∈ A, we define B a as the post-intervention weight matrix specified byEQUATIONCausal bandit -problem statement. In causal bandit, a learner performs a sequence of interventions to optimize a reward measure. Each unique set of interventions a ∈ A is represented by an arm. Following the CB's convention, we designate node N as the reward node and its associated value X N as the reward variable. We denote the post-intervention probability measure of X induced by intervention a by P a , and the associated expectation by E a . Subsequently, we denote the expected value of variable X i under intervention a ∈ A byEQUATIONAccordingly, we denote the optimal intervention by a * , which is specified byEQUATIONThe sequence of interventions over time is denoted by {a(t) ∈ A : t ∈ N}. Upon intervention a(t) in round t, the learner observes X(t) ≜ (X 1 (t), . . . , X N (t)) ⊤ and collects the reward X N (t). The learner's objective is to minimize the regret that it incurs with respect to an omniscient oracle that hasWe note the assumption that knowing d can be replaced by knowing an upper bound, and the requirement of expected noise value ν can be removed by the re-arrange method in [15] . To ensure the bounded stability of the system, the bounded noise and weights assumptions are widely used in the linear causal bandits literature [15, 26, 27] . These assumptions imply boundedness of the variables, i.e., there exists constant m such that ∥X∥ ≤ m. The recent study in [28] shows that in linear bandits, the regret will scale linearly with this constant. Without loss of generality, we assume m ϵ = m B = 1. Finally, we provide the following standard regularity condition on interventions to ensure sufficient distinction between the observational and interventional statistical models [20, 23] . Assumption 5 (Intervention regularity). A soft intervention on node i with causal depth L i ≥ 1 shifts the expected values of the descendants of i at least η, i.e., µ j,∅ -µ j,{i} > η for all i ∈ [N ] and j ∈ de(i).3 Graph-Agnostic Linear Causal Bandit (GA-LCB) AlgorithmIn this section, we introduce our proposed algorithm Graph-Agnostic Linear Causal Bandit (GA-LCB). We also provide detailed comparisons to the existing algorithms designed for soft interventions.We will provide the regret analysis in Section 4, and defer all the proofs to the appendices.Algorithm overview. Identifying the best intervention a * defined in (4) hinges on learning all the possible probability distributions P a , the number of which grows exponentially with graph size N .Learning such an excessive number of distributions can be circumvented by properly leveraging the SEM parameters. Specifically, all the distributions {P a : a ∈ A} are functions of the observational and interventional weight matrices B and B * . Furthermore, we note that each of these matrices consists of at most N d non-zero entries. Hence, learning the entire set of distributions is equivalent to estimating at most 2N d non-zero parameters of B and B * . This problem, however, faces the hard constraint that the estimated matrices B and B * must conform to a valid DAG structure. Not enforcing this constraint gives rise to issues such as the possibility of support structures that include cycles or inconsistent supports for the estimates of B and B * .For this DAG-constrained problem of estimating matrices B and B * , we take a two-step approach. The first step aims to resolve the skeleton uncertainty to the extent needed to identify the best intervention, and the second step leverages the skeleton estimates to identify the best intervention design. More specifically, the first step (GA-LCB-SL in Algorithm 1) focuses on estimating the skeleton, which is equivalent to estimating the parent sets {pa(i Pull the arm a(N t + 1) = ∅ and observe X(t) and set t = t + 1 5:) : i ∈ [N ]}.for i ∈ [N -1] do 6:Pull the arm a(N t + i + 1) = {i} and observe X(t)7:Identify the ancestors set an(i) according to (9) and construct G 8:t = t + 1 9: if N ∅ < T 2 thenPull the arm a(t) = ∅ and observe X(t) until N ∅ = T 2 10: Calculate the Lasso estimator [ B] Lasso i as in (10) 11: Identify the parents:pa(i) = supp [ B] Lasso i 12: Return: { pa(i) | i ∈ [N ]} and topological ordering π based on ancestors sets of X N , and its statistical model can be specified only by the value assigned to its parents under a do intervention. Under soft interventions, however, all the causal paths from the youngest nodes to the reward node remain intact. This means that all nodes along the causal paths that end at the reward node contribute to the reward. Therefore, inevitably, we need to estimate the parent sets {pa(i) : i ∈ [N ]}. Motivated by these, Algorithm 1 provides estimates { pa(i) : i ∈ [N ]} such that with a high probability: (1) pa(i) ⊆ pa(i); and (2) | pa(i)| ≤ c|pa(i)| for a small constant c > 1.We note that our approach is distinct from the conventional approaches to learning causal skeletons, which typically identify only the Markov equivalence class and assume the existence of an oracle rather than focusing on sample complexity and computational efficiency. For linear non-Gaussian data, a DAG can be learned using observational data with a sample complexity of O(d 4 log n) [29] . In comparison, our CB-based structure learning saves on sample complexity and computation.The second step is focused on narrowing the search space for the set of candidate interventions among which the optimal one is identified. This will provide significant computational savings as we will discuss. In this step, specifically, based on the estimates { pa(i) : i ∈ [N ]}, the GA-LCB-ID algorithm performs a successive refinement of the set A to identify the intervention set of interest. This process consists of S = logT refinement stages, where the refined set in stage s ∈ [S] is denoted by Âs ⊂ A s-1 with Â1 ≜ A. To identify the interventions to be eliminated at stage s, the GA-LCB-ID algorithm identifies the interventions whose UCB values fall below the maximum in Âs minus a bandwidth m2 1-s . Such successive refinement allows us to calculate UCBs only for promising interventions, leading to a higher computational efficiency. Furthermore, the refinement rules do not need to calculate the exact UCB values. Instead, they calculate an upper bound for the UCBs, referred to as the UCB widths. This circumvents the computational challenge of calculating the exact UCBs.: a * ∈ Âs . 
step 1: cb-based structure learning: 
 Our approach to using a sequence of interventions to learn the unknown graph G consists of two procedures. It starts by identifying the correct ancestors an(i) for i ∈ [N ]. After T 1 rounds of exploration, for all i, j ∈ [N ] we compute the mean estimates asμi,∅ (t) = 1 N ∅ (t) τ ∈[t],a(τ )=∅ X i (τ ) , and μi,{j} (t) = 1 N {j} (t) τ ∈[t],a(τ )={j} X i (τ ) , (6)where N a (t) denote the number of times the a ∈ A is selected up to time tEQUATIONSubsequently, the algorithm identifies descendants sets de(i) for i ∈ [N ] according to:EQUATIONAlgorithm 2 Graph-Agnostic Linear Causal Bandit: Intervention Design (GA-LCB-ID) for i ∈ [N ] do 7:Calculate the ridge regression estimators [B(t -1)] i and [B * (t -1)] i as in (13) and (14) 8:for a ∈ Âs do 9:for i ∈ π do 10:Calculate estimated mean μi,a (t) as in (17) 11:Calculate the width w i,a (t -1) according to (19) 12:Calculate UCB a (t -1) = μN,a (t -1) + w N,a (t -1)13: if w N,a (t -1) ≤ m 1 √T for all a ∈ Âs then while w N,a (t -1) ≤ m2 -s for all a ∈ Âs do 17:Update Âs+1 as in (22) and set s = s + 1 Choose a(t) ∈ Âs such that w s a(t) > m2 -s according to which clearly i ∈ de(i). Note that |de(i)| = 0 indicates that node i is a root node (intervention on a root node does not change the conditional distributions). Furthermore, we also estimate the ancestors sets { an(i) : i ∈ [N ]} according to:EQUATIONThe algorithm will check whether the ancestor sets will form a DAG. This is confirmed by verifying that there does not exist i, j ∈ [N ] such that j ∈ de(i) and i ∈ de(j). To further refine the estimate of the parent set, the algorithm initiates T 2 rounds of additional explorations. This ensures the algorithm has gathered sufficient observational data to accurately identify the parent set pa(i). Subsequently, it uses the Lasso estimator on the ancestors set with λ = m 2 log(4N | an(i)|/δ)EQUATIONBased on these steps, Algorithm 1 identifies the parent set of node i ∈ [N ] asEQUATIONSpecifically, Algorithm 1 returns the estimates { pa(i) : i ∈ [N ]} and a valid topological order π based on ancestor information. Given a causal graph G, an ordered permutation of [N ], denoted by π is said to be a valid topological order if for each edge (i → j) ∈ E, we have π i < π j . This can be achieved by iteratively adding nodes to π such that the parents of that node are already included in π. Finally, we note that we set the exploration constants T 1 and T 2 as follows.EQUATIONEQUATIONwhere c > 1 is a constant.Assume at the stage s ∈ S ≜ log √ T , the algorithm maintains a refined set Âs ⊂ A. It starts with the set of candidates Â1 = A and successively refines this set by performing elimination on the previous refined set using the UCB width. Based on the outputs of Algorithm 1, we first estimate the weight matrices by ridge regressions. Specifically, based on the choices of interventions and the observed data up to time t, we estimate the column vectors {EQUATIONandEQUATIONwhere we have defined the gram matrices asEQUATIONand I N is the diagonal matrix with elements 1. Accordingly, we denote our estimate of B a for intervention a ∈ A at time t by B a (t), which are constructed as follows.EQUATIONBased on the estimates, we construct the estimator of mean value µ i,a as μi,a (t)EQUATIONwheref i (B a ) ≜ Li ℓ=0 B ℓ a i .Given all the information up to time t, the next decision is to identify the intervention a(t + 1). For this purpose, a standard UCB-type approach entails forming a confidence interval for the mean estimates followed by identifying the intervention that achieves the largest UCB. In our algorithm, we avoid such an optimization-based approach and instead compute the UCBs according to UCB a (t) = μN,a(t) + w N,a (t) ,in which we refer to w N,a (t) as the UCB width and it is defined recursively as follows.w i,a (t) ≜ j∈ pa(i)EQUATIONin which α ∈ R + controls the size of width, and {m pa,ℓ | ℓ ∈ [L]} is defined as m pa,ℓ ≜ max i∈[N ],Li=ℓ X pa(i) . Subsequently, we define the post-intervention gram matrices V i,ai (t) as follows.EQUATIONwhere a i (s) = 1{i ∈ a(s)} ∈ {0, 1}. A standard UCB-type approach selects the intervention set that maximizes UCB a within A. However, this involves solving optimization problems over a set of cardinality 2 N , which becomes another computational bottleneck. Phased elimination occurs when the uncertainty of the mean estimator, as captured by the UCB width, is sufficiently small for all interventions in the candidate subset.EQUATIONwhere s ∈ N is the current stage. At this point, only the interventions with UCB values close to the optimistic one are retained.EQUATIONAlternatively, if (21) does not holds, there is some intervention a ∈ Âs such that w s a (t) > m2 -s which prevents the perform of elimination. This intervention will then be selected at time t + 1 to accelerate the elimination. This procedure continues until t = T or if the stopping criterion w i,a (t) ≤ m 1 √ T is met. The stopping criterion indicates that the interventions are approximately equally good given the time horizon T . The algorithm will then select the intervention that maximizes UCB a asEQUATIONFinally, we note that we set α = 1 2 log( N T δ ) + √ d.We compare the computational efficiency of our algorithm with those of the existing algorithms for linear SEMs with soft interventions in [15, 18] . The algorithms in these studies adopt similar procedures: they find estimators for observational and interventional weights, form the confidence ellipsoids for the weights, and solve a joint optimization problem to calculate UCBs asEQUATIONwhere [15, Lemma 1] or Appendix C). Subsequently, the interventions are chosen as those that maximize UCB a a(t + 1) = arg max a∈A UCB a .C a = i∈[N ] C i,a and C i,a = 1{i ∈ a}C * i + 1{i / ∈ a}C i are confidence regions, f N is compounding function (see(EQUATIONAll the algorithms estimate the observational and interventional weights by solving 2N ridge regressions, which is not the computation bottleneck. The two bottlenecks in this standard UCB-type approach lie in solving (24) and (25) .First, different from the case in linear bandits [30] , the optimization problem in (24) for CBs is neither convex nor concave. This is due to the highly non-linear reward function. The nonlinearity arises from the compounding effects of the causal influences along different paths leading to the reward node. The contribution of any given node X i to the reward value will be multiplied by all the coefficients along the path connecting X i to the reward node (see Appendix C for more details). When there are multiple such paths, the aggregate weight products of all paths carry the contribution of X i to the reward node. Therefore, the reward becomes a function of the product of causal weights (i.e., elements of B and B * ). This non-linearity in weights makes the optimization problem in (24) becomes computationally impossible for larger graphs. In contrast, GA-LCB addresses this issue by computing the upper confidence bounds iteratively through causal depth, which can be done in polynomial time.Secondly, solving (25) involves an optimization problem over a discrete set of size 2 N , the computational complexity of which grows exponentially with N . To circumvent this, GA-LCB randomly chooses the under-explored intervention (line 18). UCB optimization specified in (23) is performed only when the refinement process is completed, indicating that (23) will be solved over a small subset of sufficiently good interventions.: µ N,a * -µ N,a ≤ m2 3-s .Proof: We prove the properties when the properties in Theorem 1 hold. We prove the first property using the triangle inequality. Specifically,EQUATIONTherefore, using the definition in ( 19) and (117), we obtainEQUATIONThus, by using Lemma 4 and summing over t ∈ [T ], with probability at least 1 -δ we haveEQUATIONThe second property holds since when the first property holds, a * always satisfies the condition line 16-17 in GA-LCB , i.e.UCB a * (t) ≥ max Induction Hypothesis: Assume it holds for s ≤ s ′ .Induction: This indicates that for s = s ′ + 1 we have Âs ⊂ Âs-1 . Additionally the condition in line 16 implies that w s-1 a ≤ m2 -(s-1) for a ∈ Âs and w s-1 a * ≤ m2 -(s-1) . Furthermore, the description of A s in (22) impliesEQUATIONThus, for any a ∈ Âs-1 we haveEQUATION)where (219) holds due to a ∈ Âs-1 , (220) holds due to (218) and ( 221) holds due to the definition of UCB.The next lemma provides an upper bound on the number of trials for which an alternative is chosen at the time T s for s ∈ [S].Lemma 13. If we define T s as the time when Âs is ended and Âs+1 starts, for all s ∈ [S] we haveT s ≤ 2 s m × (α + √ d) L ℓ=1 d ℓ-1 2 5 m 2 pa,ℓlog(m 2 pa,ℓ /d + 1)EQUATION)Proof: Note that similar to (213), we apply triangle inequality to getEQUATIONStep 1: To proceed, we first bound the second term in (224): summation regarding the eigenvalues, in the following lemma. Lemma 14. We have the following upper bound for the eigenvaluesEQUATIONwhere τ ≜ ι 2 m 4 κ 2 min and ι ≜ 16 3 log(2dN T 2 (T + 1)).Proof: In order to proceed, we need upper and lower bounds on the maximum and minimum singular values of U i,a(t) (t). However, these bounds depend on the number of non-zero rows of U i,a(t) (t) matrices, which equals the values of the random variable N i,a(t) (t). Let us define the weighted constantEQUATIONThen for every t ∈ [T ], and n ∈ [t], we define the error events corresponding to the maximum and values of U i (t) and U i (t) asEQUATIONEQUATION)Lemma 15. [15, Lemma 8] The probability of the error events E i,n (t) and E * i,n (t) are upper bounded asEQUATION)Then we define the union error event E i,∪ asE i,∪ ≜ {∃ (t, n) : t ∈ [T ], n ∈ [t], E i,n (t) or E * i,n (t)} .(230) By taking a union bound and using Lemma 3, we haveEQUATIONNow we turn back to E T t=1 λ i (t) to analyze it under the complementary events E i,∪ and E c i,∪ .Bounding term E 1{E i,∪ } T t=1 λ(t) . Since λ min V i,ai(t) (t) ≥ 1, we have the following upper bound.EQUATIONBy setting ι = 16 3 log(2dN T 2 (T + 1)), we obtainEQUATION≤ P(E i,∪ )T≤ N T (T + 1)d exp(log(dN T 5/2 (T + 1)))EQUATION)Bounding E 1{E c i,∪ } T t=1 λ i (t). Considering the event E c i,∪ , we can use the following bounds on the singular valuesEQUATIONThus, the target sum can be upper-bounded asEQUATION)It is noteworthy that the term in the sum in (238) has a critical point, and we bound the two regions separately. To this end, we define the functionEQUATIONIn order to analyze the behavior of the function n, we introduce τ ≜ ι 2 m 4 κ 2 min as the critical point. Note that when x ≤ τ , we have xκ min < γ n . In this case,EQUATIONwhich is an increasing function over the region. Now, we are ready to bound the last termEQUATIONWe define the set of time indices at which the chosen interventions are under-explored asEQUATION)It can be readily verified that |H i | ≤ 8τ since for node i we have a i ∈ {0, 1}. Furthermore, whenx ∈ H i , we haveEQUATION)Then we can bound the sum in (241) when H i occurs as follows.EQUATIONNext, we only need to bound the remaining part when t ̸ ∈ H iEQUATIONNote that when t ∈ H c i , we have N i,a(t) (t) > τ and n is a decreasing function. Hence,EQUATIONWe bound the discrete sums through integrals and defineEQUATIONSince g(x) is a positive, non-increasing function, for any k ∈ N, k ≥ 4τ + 1 we haveEQUATIONThen, the sum in ( 246) is upper bounded byEQUATIONSince h(x) is positive and decreasing, and H(y) is defined as an integral of the n function with a positive first derivative and negative second derivative, it can be deduced that H is a concave function. Thus, by applying the concavity property we haveEQUATIONNext, we proceed to establish an upper bound on the function H as follows.EQUATIONEQUATIONwhere we have used1 √ ax-b dx = 2 √ ax-b a + constant .Combining the results in ( 235), ( 244) and (255), the final result for the bound isEQUATIONStep 2: Now we bound the first term in second term in (224). We proceed by proving the following inequalities by induction. For i ∈ π with causal depth L i , we prove EQUATIONBase step: when i ∈ [N ] and L i = 1, we haveEQUATIONHence, applying Lemma 9 and Lemma 14, we have + Ts t=1 (α + √ d)(∥X [Vi,a i (t)] -1 + 2 √ 2m pa,Li λ -1/2 min V i,a(τ ) (t) ) (260) ≤ d × (α + √ d) k-1 ℓ=1 d ℓ-1 10 m 2 pa,ℓ log(m 2 pa,ℓ /d + 1)T s log m 2 pa,ℓ d T s + 1 + d × (α + √ d)2 √ 2 k-1 ℓ=1 d ℓ-1 m pa,ℓ 2 κ min T s + 8τ + 1 + (α + √ d) 10 m 2 k log(m 2 k /d + 1)EQUATIONwhere in (260) we use the definition of width, (261) holds due to induction and Lemma 14. Hence, we have proved the following inequality for the reward node.EQUATIONBy the condition of line 18 of GA-LCB , we haveEQUATIONCombining ( 263) and ( 264) we obtainEQUATION 
regret analysis: 
 We show that the GA-LCB is almost minimax optimal by characterizing the achievable regret of the GA-LCB algorithm in the graph-independent setting and establishing that it matches a minimax regret lower bound. We provide additional discussions to interpret the dependence of the regret terms on various graph parameters and the relationship of these results vis-á-vis the existing results in the literature. We also present an improved graph-dependent bound, when additional information about the graph is available.We first show the graph-independent bounds that hold for a class of bandits with a maximum in-degree d and maximum causal length L. The key steps in these analyses involve determining the exploration time that ensures the identification of the parent sets with high probability and bounding the time instances that the refinement process is conducted. To delineate a regret upper bound, we start by establishing the performance guarantee for the GA-LCB-SL algorithm. In the following theorem, we demonstrate that with high probability, this algorithm correctly identifies the topological ordering and the parent sets. For this purpose, we define κ max and κ min as the maximum and minimum eigenvalue of the following second moment with null intervention:EQUATION)Theorem 1 (Achievable Graph Skeleton Learning). Under Assumptions 1-4, the GA-LCB-SL algorithm ensures that 1. with probability 1 -δ we have a valid topological ordering π; and 2. with probability at least 1 -2δ, for all i ∈[N ] we have pa(i) ⊆ pa(i) and | pa(i)| ≤ κ|pa(i)|,where κ is defined asEQUATION)Leveraging the result of Theorem 1, we characterize the achievable regret of GA-LCB. Theorem 2 (Achievable Regret). Under Assumptions 1-5, the GA-LCB-ID algorithm ensures that with probability 1 -3δEQUATIONwhere we have defined R ≜ m 2 η 2 .We note that R represents the guaranteed maximum signal-to-intervention-power ratio. This ratio measures the difficulty in distinguishing between observational and interventional distributions (the higher R, the harder to distinguish).To emphasize the cost of learning the skeleton, in the next corollary, we provide the achievable regret of the GA-LCB algorithm when the graph skeleton is known.Corollary 1 (Achievable Regret -Known Skeleton). When the graph skeleton is known, under the same setting as in Theorem 2, with probability 1 -δ, GA-LCB-ID ensures thatEQUATIONComparing Corollary 1 with Theorem 1, we observe that the term Õ(d + RN ) represents the cost to do structure learning, while κ L-1 2 reflects the cost resulting from imperfect graph learning. Next, we establish a lower bound on the regret. Any lower bound on the regret of the setting in which the graph's skeleton is known will immediately serve as a lower bound for our setting with an unknown graph. We will present one such lower bound and show that even though it is expectedly looser than a lower bound for our setting, it still almost matches the achievable regret characterized in Theorem 2. We also emphasize that our result improves the known minimax lower bound when the graph skeleton is known (c.f. [15, 18] ). Theorem 3 (Regret Lower Bound). For any given skeleton with parameters d and L, there exists a causal bandit instance such that the expected regret of any algorithm is at leastEQUATIONWhen comparing the upper bound in Theorem 2 and the lower bound in Theorem 3, we observe that the regret upper bound and lower bound show similar behavior with respect to graph parameter d, L, and the time horizon T . Given these results, we provide some observations.• Dependence on N . We first note that the achievable regret has a diminishing dependence on the graph size N as T grows. This is especially important since the number of interventions grows exponentially with N . This result indicates that the achievable regret has a diminishing effect not only on the graph size but also on the cardinality of the intervention space. • Unknown Skeleton. Comparing Theorem 2 and Corollary 1 indicates that the impact of an unknown graph has two parts. First, sufficient exploration is required to determine the correct topological ordering and parent sets, which adds a Õ(d + RN ) term to the regret bound. Secondly, the imperfect identification of the parent set by the Lasso estimator leads to an estimated graph with a maximum in-degree of cd instead of d, which is propagated through the network layers. • Graph topology. The regret bounds depend on the graph through its connectivity parameters d and L. Unlike the observations in [15, 18] , we have almost-matching upper and lower bounds up to a d factor. This significantly improves from the previously-known gap of d L .• Dependence on T . Regret upper and lower bound both scale with T at the rate Õ( √ T ).• Linear bandits. Finally, we note that despite some similarities, our problem is significantly different from linear bandits since, as shown in Appendix C, in linear causal bandits, the reward is non-linear with respect to the parameters or the interventions. This is the case for even L = 1. We note that our regret's dependence on d differs from that in the linear bandit setting.In linear bandits, the regret scales linearly with d as shown in [31, 32] . When L = 1, the regret upper bound in our case scales as Õ( √ dT ), and the regret lower bound scales as Ω( √ T ). We conjecture that the regret upper bound is tighter because it more accurately captures the uncertainty of parameter estimation.• Regret bounds comparisons. GA-LCB provides significanty improved regret bounds compared to LinSEM-UCB [15] and GCB-UCB [18] . Specifically, under the known graph skeleton setting, GA-LCB achieves a d L √ N factor improvement in the regret bounds compared to LinSEM-UCB. While GCB-UCB removes the √ N factor, it underperforms compared to LinSEM-UCB. Furthermore, our regret upper bound has only a d factor more than the lower bound.The graph-independent bounds can be further refined to recover graph-dependent regret bounds that use the instance-level information. To account for the actual influence of the graph parameters on the reward node, we define the effective maximum in-degree as d e = max i∈an(N ) d i and the effective maximum causal depth as L e = max i∈an(N ) L i . We have the natural inequalities d e ≤ d and L e ≤ L.To characterize the graph-dependent bound, we need to slightly modify the GA-LCB-ID algorithm. Specifically, we only need to identify the optimal intervention within A ′ = 2 [ an(N )] and estimate the column vectors{[B] i , [B * ] i : i ∈ an(N )}.By incorporating instance-specific information about the graph structure, the regret upper bound can be further refined as follows.Corollary 2 (Achievable Regret -Graph-Dependent). When L e and d e are known, the modified GA-LCB-ID algorithm ensures that with probability 1 -3δEQUATIONBy comparing the upper bound in Theorem 2 and Corollary 2, we observe that the cost of learning the graph remains intact. The reason is that we must explore interventions on every node i ∈ [N ] to identify the ancestor relationships, even when graph-dependent information is known. Hence, all the regret improvements are due to the part of learning the best intervention, particularly in relation to the graph topology. The term (κd) L-1 2 in Theorem 2 is replaced with (κd e ) Le-1 2 . The change is due to the fact we do not need to learn optimal intervention in the whole graph G as the interventions on non-ancestor nodes will not affect the reward. Instead, it suffices to learn only the optimal intervention on the subgraph G formed by an(N ) and the parameters of G. 
conclusions: 
 In this paper, we have solved the causal bandit problem with unknown graph skeletons under general stochastic interventions. We have proposed an implementable algorithm and provided regret analysis for both unknown and known graph skeletons. The unknown skeleton affects the achievable regret bounds in two ways: a term that is linear in d + N but is independent of T and a cd factor due to the imperfect identification of the parents. When the graph skeleton is unknown, the achievable regret bounds and the minimax regret lower bound are shown to match up to a d factor. Compared to the existing algorithms, the proposed algorithm is more amenable to scalable implementation.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The experiments only needs single CPU.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theoretical paper.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 did not release new assets.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: We did not involve crowdsourcing nor 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 did not involve crowdsourcing nor 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. 
 
 Appendix: In this section, we assess the regret performance of GA-LCB. As the most relevant existing approaches, we compare the regret of our algorithm to those of LinSEM-UCB [15] and GCB-UCB [18] , which are designed for causal bandits with soft interventions.Causal graph. We consider the hierarchical graph illustrated in Figure 1 . This graph consists of (L + 1) layers, with the first L layers having d nodes. The nodes between two adjacent layers are fully connected. The last layer consists of one node (reward node) that is fully connected to nodes in layer L. The number of nodes in this graph is N = dL + 1.Parameter setting. The noise terms {ϵ i : i ∈ [N ]} are set to be drawn from the uniform distribution Unif(0, 1). We set the non-zero elements in the observational and interventional weights matrix to 1 and 0.5, respectively. We evaluate L ∈ {2, 4, 6}. The experiment was conducted using 2 CPUs from Mac Mini 2023. We set T 1 = T 2 = 500 for experiments with L = 2, T 1 = T 2 = 1000 for experiments with L = 4 and L = 6.Algorithm settings. The theoretical guarantees relied on specific technical conditions on parameters. We observe that the algorithms designed can provide better-than-foreseen empirical performance by tuning the parameters involved. Specifically, we adjusted the parameters λ, α, and the sufficient exploration times T 1 and T 2 . We observe that setting λ = α = 0.1 yields reasonable performance. The experiments are repeated 100 times, and the average cumulative regret is reported. Regret performance. In Figure 2 , we present the cumulative regret of GA-LCB algorithm and other algorithms with the hierarchical graph with d = 3 and L = 2. LinSEM-UCB and GCB-UCB exhibit lower regret within the shown time horizon, while our algorithm (GA-LCB with known graph) shows a slightly higher regret. This difference is due to balancing a more precise confidence radius with enhanced scalability. Besides, we observe that GA-LCB incurs higher regret due to the structure learning phase. Since both LinSEM-UCB and GCB-UCB face computational challenges for scaling up to larger graphs, we evaluate the cumulative regret of GA-LCB under known and unknown graph Scaling with L: Scaling of the regret with respect to the causal depth L is depicted in Figure 5 for the setting of a hierarchical graph with d = 2 and L varying in the range {1, • • • , 9}. The theoretical results (regret upper and lower bounds) predict that the regret grows at the rate (2κ) L (i.e., exponential in L). The empirical results in Figure 5 corroborate that the cumulative regret scales exponentially with length L, and the actual regret closely tracks the upper bound's trend.Scaling with d: Scaling of the regret with respect to the maximum in-degree d is depicted in Figure 6 for a hierarchical graph with L = 2. We increase the number of sufficient exploration parameters T 1 and T 2 to ensure we accommodate all settings with different degrees. The theoretical predictions suggest that our algorithm's regret scales as d 3/2 (i.e., polynomial d). Figure 6 demonstrates that our regret is super-linear and tracks the polynomial trend of the regret upper bound (i.e., the achievable regret).Computational time. In Figure 7 , we compare the running times of different algorithms under the two settings mentioned above. The figure indicates that our proposed algorithm significantly reduces computational time in the hierarchical graph with L = 2 when compared with LinSEM-UCB and GCB-UCB. In the hierarchical graph with L = 4, which is considered sufficiently large in the related studies, the GA-LCB still demonstrates a notable stronger running time.In this section, we present the notations that will be useful in our analyses. We denote the singular values of a matrix A ∈ R M ×N with M ≥ N in the descending order byEQUATIONIn the proofs, the analyses often involve with zero-padded vectors and their corresponding matrices (e.g., X pa(i) and V i,ai(t) ). Consequently, these matrices have non-trivial null spaces, resulting in zero singular values. In such instances, we are interested in the effective smallest singular values that are non-zero. We denote the effective largest and smallest eigenvalues, which correspond to the effective dimensions of a positive semidefinite matrix A with rank k, byEQUATION)For a square matrix U = AA ⊤ ∈ R N ×N , we denote the effective largest and smallest eigenvalues by 2λ max (U) ≜ σ 2 max (A) , and λ min (U) ≜ σ 2 min (A) .(34) Then we construct data matrices that are related to gram matrices. At time t ∈ N and for any node i ∈ [N ], the data matrices U i (t) ∈ R t×N and U * i (t) ∈ R t×N consist of the weighted observational and interventional data, respectively. Specifically, for any τ ∈ [t] and i ∈ [N ], we defineEQUATIONandEQUATION)We also define the observation matrix that is used for Lasso estimator U i, an(i) (t) ∈ R t×N that stores the observational data on the ancestor's set.EQUATIONWe also define the data vectorEQUATIONandEQUATION)Similarly to (2), we denote the relevant data matrices for node i ∈ [N ] under intervention a ∈ A byEQUATIONEQUATIONEQUATIONDefine N * i (t) as the number of times that node i ∈ [N ] is intervened, and N i (t) as its complementEQUATIONandEQUATIONAccordingly, for any i ∈ [N ] and t ∈ N, defineEQUATIONFor a ∈ A, we define the pseudo estimated variables X a (t) and pseudo underground variables X a (t) is the random variable at time t generated according to the following linear SEMsEQUATIONandEQUATIONwhich share the same ϵ(t) acorss the different interventions.Finally, let us denote the second moment of the parents of a node i under intervention a ∈ A with unknown weight matrices B and B * byEQUATIONAccordingly, we denote the lower and upper bounds on the minimum and maximum singular values of these moments by κi,a,min ≜ σ min Σ i,a , κmin ≜ minEQUATIONκi,a,maxEQUATIONWe note due to the Cauchy interlacing theorem, we haveEQUATIONFinally, we use ∆(x) to represent the diagonal matrix with elements in x.Similar to [15, Lemma 1], we present the following decomposition for the expected value of the variable X i for i ∈ [N ]. We note our design of the mean value estimator in (17) based on this lemma. Lemma 1. Given intervention a ∈ A, the value of node X i is related to the noise vector ϵ viaEQUATIONProof. To capture the contribution of ϵ j on node i, we use the fact that the entry at row j and column i of B ℓ a is the sum aggregate of the weight products along all paths from node j to node i that have the exact length ℓ. Since the longest length will be L i , the term Li ℓ=1 [B a ] j,i becomes the aggregated sum of weight products along all paths from node j to node i regardless of path length. We denote this sum byEQUATION)We note that the noise ϵ at any time t is independent of the process that decides B a . Therefore, the expected value of X i under intervention a isEQUATIONThe proof is divided into two parts. First, we show thatT 1 = 32m 2 η 2 log( 2N 2 δ) is sufficient to identify the ancestors sets and a valid topological ordering with probability at least 1 -δ. Subsequently, we show that with a probability of at least 1 -δ, Lasso regression yields the desired estimates for the parent sets.Part 1: topological ordering. In this part, we show that de(i) ⊆ de(i). Based on this, we will see an efficient topological ordering would be natural. Recall the definition of de(i) and an(i) in ( 8) and ( 9), respectively, it is equivalent to show that for i ∈ [N ] with L i ≥ 1 all j ∈ de(i), we have |μ j,∅ -μj,{i} | > η 2 and for all j ∈ an(i), we have |μ j,∅ -μj,{i} | ≤ η 2 . We note that the bounded noises that satisfy Assumption 4 are 1-sub-Gaussian. After sufficient exploration, the mean estimators μj,∅ and μj,∅ defined in (6) will be close enough to the true means µ j,∅ and µ j,∅ with high probability, respectively. When the mean estimates are accurate enough, based on Assumption 5, we show that η 2 can be used to separate descendants from non-descendants based on the value of |μ j,∅ -μj,i |. Based on the definition of μj,∅ and μj,∅ in (6), we haveEQUATIONwhere (55) holds because Hoeffding's inequality and (57) holds since the definition of T 1 in (12) .Similarly, we haveEQUATION)We define error events in which the mean estimates have a large error as follows.EQUATIONBy taking a union bound and leveraging (57)-(58), we obtainEQUATIONNext, we prove that under event E c TO , we can correctly identify de(i) for all node i ∈ [N ]. If j ∈ de(i), to evaluate the gap |μ j,∅ -μj,{i} |, we leverage the following relationship:EQUATIONwhere ( 62) is due to the triangle inequality. Thus, for all i ∈ [N -1] and j ∈ de(i) we haveEQUATION(59)EQUATION)On the other hand, when j ̸ ∈ de(i), we have µ j,∅ = µ j,{i} , based on which we obtainEQUATIONEQUATION)In conclusion, with probability 1-δ, the estimates of descendants sets de(i) = de(i)for node i ∈ [N ]with L i > 0 with probability at least 1 -δ. Hence, with probability at least 1 -δ the an(i) defined in (9) will be the best set we can find, that is an(i) ⊆ an(i) for i ∈ [N ] and for i ∈ an(i) \ an(i), we can infer that i is a root node. Besides, the topological ordering π is valid.Part 2: Lasso regression. In this part, we establish a sparsity property of the Lasso estimator in linear causal bandit, which is inspired by [33] and [34] . We consider the case when T 2 ≥ T 1 . The case for T 2 < T 1 can be analyzed similarly. We prove for fixed i ∈ [N ] as it is the same for all i ∈ [N ]. When the ancestors sets and topological ordering are correct with probability at least 1 -δ from Part 1. We define the time instance T 3 = N T 1 + T 2 -T 1 be the time that the Lasso estimators are calculated.We show that when T 2 ≳ d log(N ) and when ancestors sets and topological ordering are correct, with probability at least 1 -δ, the Lasso estimates satisfy the desired property. The proof consists of three steps. In the first step, we show that the Lasso estimates provide a bounded cardinality, that is for i ∈ [N ] we have | pa(i)| ≤ κ|pa(i)|. his step involves first bounding the support of the Lasso estimator by the empirical error, followed by bounding the empirical error itself. In the second step, we prove by contradiction that for i ∈ [N ] we prove |pa(i) ⊆ | pa(i)|. Finally, we take a union bounds on all nodes i ∈ [N ] to get the desired result.Step 1: Bounded cardinality. In this step we show | pa(i)| ≤ κ|pa(i)|. Recall that the Lasso estimator in the feature selection stage is defined asEQUATIONWe state some preliminary properties of the Lasso estimator and later show that our estimator satisfies the conditions for these properties.Property 1 (Restricted eigenvalues). Let S ≜ supp([B] i ), define the coneEQUATION)Then for all θ ∈ C(S), there exists some positive constant κ ′ such that the observation matrix U i, an(i) (t) ∈ R t×| an(i)| satisfies the conditionEQUATION)Property 2 (Column normalized). We say that U i, an(i) (t) is column-normalized ifEQUATIONLemma 2. Consider a d-sparse linear regression and assume that design matrix U i,0 (t) ∈ R t×| an(i)| satisfies Properties 1-2. Given the Lasso estimator with regularization parameter λ = 4m log(| an(i)|)/t, then the following properties hold with probability at least 1 -δ.• The estimation error under ℓ 1 -norm of any optimal solution [ B Lasso ] i satisfies [35, Theorem 7.13]:EQUATION• The mean square prediction error of any optimal solution [ B Lasso ] i satisfies [35, Theorem 7.20 ]:EQUATIONFor j ∈ an(i) define the random variablesEQUATION)Since X an(i) (t) ∞ ≤ m, the Hoeffding's inequality for sub-Gaussian random variables impliesEQUATION)We note that content we have N ∅ (t) = T 2 . For j ∈ [N ], define E gj as the event that g j is contained in the interval close to mean value, i.e.,EQUATION)Based on the probability bounds in (76), we haveEQUATIONAccordingly, defineEQUATIONBy taking a union bound and leveraging (78), we obtainEQUATION)From the Karush-Kuhn-Tucker (KKT) condition of Lasso regression, the solution [ B Lasso ] i satisfies1 T2 τ ∈[T 3 ],a(τ )=∅ Xj(t) Xi(t) -[ B Lasso ] ⊤ i X an(i) (t) = λ sign [ B Lasso ]i , if [ B Lasso ]i,j ̸ = 0 , (81) 1 T2 τ ∈[t],a(τ )=∅ Xj(t) Xi(t) -[ B Lasso ] ⊤ i X an(i) (t) ≤ λ, if [ B Lasso ]i,j = 0 . (82)Therefore, we haveEQUATION) Since λ = m 2 log 4N | an(i)| δ T2, under event E gi , we haveEQUATION)Based on (84), we can have the following lower boundEQUATIONwhere (85) holds since an(i) ⊆ supp([B Lasso ] i ) and (86) holds due to (84). On the other hand, define the uncentered empirical covariance matrix asEQUATION)Let κi,max = σ max Σ i . Then we haveEQUATION)Now we need a high probability bound for ϕ max . In order to proceed, we need upper and lower bounds for the maximum and minimum singular values of U i, an(i) (t). However, these bounds depend on the number of non-zero rows of U i, an(i) (t) matrices, which equals to value of the random variable N i,a(t) (t). Let us define the weighted constantEQUATION)We define the error events corresponding to the maximum and minimum singular values of U i, pa(i) (t)(T 3 ) as follows.E i ≜ σ min U i, an(i) (T 3 ) ≤ max 0, T 2 κi,∅,min -γ n .orEQUATIONLemma 3. [15, Lemma 8] The probability of the error events E i (t) are upper bounded asEQUATIONThus, by setting η = 16 3 log 2dN δ , we have with probability 1 -δ 2N we haveEQUATIONHence, with probability 1 -δ we haveEQUATIONEQUATIONEQUATIONwhere we use (92) in (95) and the last inequality is due to T 2 ≳ d log(N ). Since κ i,max has the natural upper bound m 2 , we defineEQUATIONCombined with (98) we know that κi,max ≤ κ 0 , (100) based on which we haveEQUATIONwhere (102) holds due to the matrix formulation of the equation and the definition of U i, an(i) (T 3 ) in (37) , and (103) holds due to (100).Combining all the results in ( 86) and (103), we find that with probability at least 1EQUATION)The speed of convergence of Lasso estimators depends on how rapidly the term ∥U i, an(i) [B Lasso ] i -U i, an(i) [B] i ∥ 2 2 decreases. We now ensure D satisfies Property 1 with κ = κ min,∅ /2 when T 2 ≳ d log(| an(i)|). The uncentered empirical covariance matrix defined in (87) satisfiesEQUATIONWe need the notion of restricted eigenvalue defined as follows.Definition 1. Given a symmetric matrix H ∈ R d×d , positive integer k, and L > 0, the restricted eigenvalue of H is defined asEQUATIONIt is easy to see U i, an(i) (T 3 )Σ -1/2 i,∅has independent sub-Gaussian rows with sub-Gaussian normΣ -1/2 i,∅ X an(i) ψ2 = κ-1/2 i,∅,min .If the population covariance matrix meets the restricted eigenvalue condition, then the empirical covariance matrix also satisfies this condition with high probability [36, Theorem 10] . Specifically, suppose the number of rounds in the exploration phase satisfiesEQUATIONfor some c * ≤ 2000 and c ′ = 10 4 dκ 2 i,∅,max /ϕ 2 (Σ, k, 9). Then the following condition holdsEQUATIONNoting ϕ(Σ, k, 9) ≥ κ1/2 i,∅,min , we subsequently getEQUATIONwherec 1 = 1 4c * κ-1/2 i,min. This guarantees Σ satisfies Property 1 in the appendix with κ 0 = κi,∅,min 2 .It can be readily verified that Property 2 holds. Applying the in-sample prediction error bound in Lemma 2, we have with probability at least 1 -δ N ,1 T 3 ∥U i, an(i) (t)[ B Lasso ] i -U i, an(i) (t)[B] i ∥ 2 2 ≤ 18 κmin • d log( N | an(i)| δ ) T 2 ≤ 18 κ min • d log( N | an(i)| δ ) T 2 .(110) Putting ( 104) and (110) together, with probability at least 1 -2δ N , we haveEQUATION)Step 2: Containing pa(i) set. This step is to verify the variable screening property of the Lasso estimator, that is supp([EQUATIONby using Lemma 2, it holds that with probability at least 1 -δ 2N ,EQUATIONwhere in the last inequality we use the fact that ∥• ∥ 2 ≥ ∥ • ∥ ∞ .Now we prove the variable screening property by contradiction. If there exists a j such that j ∈ supp([B] i ) but j / ∈ supp([ B Lasso ] i ), we haveEQUATIONOn the other hand,EQUATIONwhich leads to a contradiction. Hence, we conclude that supp([B Lasso ] i ) ⊇ supp([B] i ).Step 3: Union bounds. By taking a Union bounds on N nodes with probability at least 1 -2δ, for all i ∈ [N ], we haveEQUATIONThis proof leverages a technique initially introduced by [37] and further developed by [38] and [32] for contextual linear bandit setting. However, unlike their settings, we face stochastic environments and compound effects due to the causal structures. In the proof, we address the added uncertainty introduced by noise from the parent variables, which requires careful handling. In the proof of Theorem 2, we work with the estimate of the maximum in-degree, denoted by d ≜ max i∈[N ] | pa(i)| which, with probability at least 1 -2δ, satisfies d ≤ κd, as proved in Theorem 1. However, to cover the proof for Corollary 1 and Corollary 2 where the proof needs to deal with d and d e , respectively, we use the notation d to represent d, and pa(i) to represent pa(i) throughout. Besides, we work on the time instances from T 3 to T for GA-LCB , to accommodate the known graph setting, we extend the proof across the entire time horizon, and prove the theorem for the entire time horizon T . The proof consists of four main parts: first, we demonstrate that the UCB width holds in Section E.1, second, we bound the cumulative width in Section E.2, then bound the time required for elimination in Section E.3, and finally, we bound the regret in Section E.4.In this section, we begin by proving the following estimation error lemma, that is for node i ∈ π, if we can observe the contextual observation X pa(i),a , a tighter contextual UCB width can be achieved, as shown in the following lemma.Lemma 4. For i ∈ π and a ∈ A, define the true UCB width asEQUATION)where α = 1/2 log(2N T ) + √ d. With probability at least 1 -δ T for all a ∈ A and j ∈ an(i) we have X j,a (t) -X j,a (t) ≤ w j,a (t) .(118)Proof: We first provide a high probability bound on the exploration bonus ∥X pa(i),a (t)∥ 2[Vi,a i (t)] -1 via Azuma's inequality and then prove this lemma via induction on the causal depth L i .High probability bound. Due to the statistical independence of the observation samples U i,ai (t) and X pa(i),a (t) for all a ∈ A, we have E[ϵ i (t)] = 0, whereϵ i (t) ≜ (ϵ i (1), • • • , ϵ i (t)) ⊤ .Hence, for all a ∈ A we haveEQUATIONwhere (120) holds since Azuma's inequality implies, and ( 121) is due to the following factEQUATION)and we use β = 1 2 log N T δ in (122), which corresponding to the first term in α we used for the UCB width in Theorem 2.Next, we prove the Lemma 4 by induction.Base step: L i = 1. For node i ∈ [N ] with causal depth L i = 1, we show that for all a ∈ A with probability 1 -δ T N we haveEQUATION)We start by decomposing the left-hand side in (128) as follows.EQUATIONwhere ( 131) is due to whenEQUATION)The right-hand side above decomposes the prediction error into a variance term (first term) and a bias term (second term). Next, we bound the second term in (135) as followsEQUATIONwhere (138) holds since the matrix U i,ai (t) ⊤ U i,ai (t) is positive semidefinite.Combining the bounds in ( 135), ( 122) and (139) completes proof for L i = 1.Step: Assume that the property holds true for causal depths up to L i = k. We show that it will also hold forL i = k + 1.For this purpose, we start with the following expansion and apply the triangular inequality to find an upper bound for it. Similar to (135), we haveEQUATION)Using ∥[B a ] i ]∥ ≤ √ d and triangle inequality, we obtainEQUATIONwhere the last two terms can be bounded similarly as in the Base Step. It remains to bound the termEQUATION)From induction, we know that for all j ∈ pa(i), with probability 1 -δ we have X j,a (t) -X j,a (t) ≤ w j,a (t) .(144) Thus, we obtainEQUATION)Hence, we conclude the proof.To bound the sum of UCB width, we first need to bound the sum of the exploration bonuses, as presented in the following lemma. Lemma 5. For all i ∈ [N ] with L i = ℓ ,with probability at least 1 -δ we haveEQUATION)where m pa,ℓ ≜ max i∈[N ],Li=ℓ X pa(i) .Proof: This proof will use some intermediate steps from proof of Lemma 4. To proceed, we need the following lemma to bound the exploration bonus X pa(i) (t) [V i,a i (t) (t)] -1 in terms of eigenvalues.Lemma 6. Let {λ ai(t),j (t), j ∈ [N ]} denote the ordered eigenvalues of V i,ai(t) (t) such that λ ai(t),j (t) ≤ λ ai(t),j+1 (t) for j ∈ [N -1]. Then we haveX pa(i) (t) 2 [V i,a i (t) (t)] -1 ≤ 10 d j=1λ ai(t),j (t + 1) -λ ai(t),j (t) λ ai(t),j (t) .(148)Proof: The proof is similar to [37, Lemma 11] and [38, Lemma 2] with minor modifications to reflect bounded assumptions (the effect of m) and causal mechanisms (post-intervention distributions). We provide the proof for fixing i ∈ [N ] and a i = 0 as it can be readily generalized to all cases a ∈ A.To proceed, we need the following lemmas. Lemma 7. [37, Lemma 17] For any λ 1 ≥ λ 2 , a ∈ R, we haveEQUATION)for some 0 ≤ y ≤ a 2 λ1-λ2 and some orthogonal matrix U.Lemma 8. Let λ 1 ≥ • • • ≥ λ d ≥ 1. And let ν 1 , ≥ • • • ≥ ν d denote the effective eigenvalues of matrix ∆ (λ 1 , . . . , λ d , 1 • • • 1) + z • z ⊤ , where z ∈ R N , ∥z∥ ≤ m pa,Li ,There exists y h,j ≥ 0, 1 ≤ h < j ≤ d, and the following holds:EQUATIONEQUATIONEQUATIONEQUATIONEQUATION)EQUATIONProof: Clearly (151) implies ( 154) and ( 151); (152) imply (153). We prove the lemma by a recursive methods similar to induction on the dimension d.Base step: We apply Lemma 7 to obtain the following transformation:EQUATIONwhere λh = λ h + y h,d , and y h,d ≥ 0, for h = 1, . . {U d ′ , • • • U d }.Induction Step: We proceed by applying Lemma 7 with the upper left sub-matrixEQUATION)to tackle the d ′ row and column. Then (155) follows from Lemma 7 since all elements in the diagonal are increasing with the induct step but no element grows by more than m 2 pa,ℓ since ∥z∥ ≤ m 2 pa,ℓ . Now, we are ready to prove the Lemma 5. From the definition of V i,ai(t) (t + 1) we getEQUATIONwhere in (163) we apply Lemma 8 on V i,ai(t) (t) and we define X pa(i) (t) = U(t)X pa(i) (t). Thus, the effective eigenvalues of V i,ai(t) (t + 1) are the effective eigenvalues of the matrixEQUATIONUsing the notation of Lemma 8, let λ 1 ≥ • • • ≥ λ d ≥ 1 be the eigenvalues of V i,ai(t) (t), {ν 1 , . . . , ν d } be the eigenvalues of V i,ai(t) (t + 1), and z = X pa(i) (t). For these choices we have the following propertyEQUATIONTo bound z 2 j , we use (151) in Lemma 8 and obtainEQUATIONFor λ h > λ j + 3m 2 pa,Li from (155) we obtainEQUATIONandEQUATIONsince ∥z∥ ≤ m 2 pa,Li . Hence, by combining (166) and (168) we getEQUATIONand, subsequentlyEQUATIONIf λ j ≥ m 2 pa,Li and λ h ≤ λ j + 3m 2 pa,Li when λ j ≥ λ h /4 and we haveEQUATIONwhere (171) holds as we relax the sum to include more terms and (173) holds due to (153). Thus, by applying ( 170) and ( 173) to (165), we obtainEQUATIONEQUATIONSo far, we have characterized a bound for confidence width. Next in terms of eigenvalues, we proceed to bound the sum in term of time instances the following lemma. Lemma 9. For all i ∈ [N ] with L i = ℓ we haveEQUATIONProof: The proof is similar to the proof of [37, Lemma 13] , but modified to handle the difference between our algorithms and the difference of the weights. Lemma 6 impliesEQUATIONSince a i (t) ∈ {0, 1} we haveEQUATIONTo bound the width sum, we leverage the closed-form solution of the following optimization problem. We define the instances at which node i is intervened and not intervened as follows.EQUATIONLemma 10. [38, Lemma 8] The solution to the following optimization problem set of time instances Ψ ⊂ [T ] and C > dEQUATIONisEQUATIONWe have the following property for the constraints.EQUATIONλ 0,j (t + 1)EQUATIONwhere ( 186) is due to the definition of m pa,ℓ . Hence, by applying Lemma 10 in (180) we obtain t∈Ti(t)EQUATIONNext, we use the following lemma to bound (188). Lemma 11. If ψ ≥ 1, the following inequality holdsEQUATIONProof:EQUATIONEQUATIONand h(ψ) ≜ log(1 + ag(ψ)) .(192) Since h(ψ) > 0. Showing (189) is equivalent to showing that for all ψ ≥ 1 we haveEQUATIONWe show it in two steps. First, we show = 1, g(ψ) h(ψ) is less than 1. Second, we show the derivative of the function g (ψ) h(ψ) is negative for ψ ≥ 1. To proceed, we use the following properties of g(ψ) and h(ψ).EQUATIONwhere ( 195) is due to L'Hôpital's rule. Similarly, we haveEQUATIONBesides, the derivative of g(ψ) isg ′ (ψ) = m 2 pa,ℓ d ψ -log m 2 pa,ℓ d ψ + 1 ( m 2 pa,ℓ d ψ + 1)EQUATIONNow, letEQUATIONThe sign of g ′ (ψ) is the same as k(ψ) when ψ > 0. Furthermore, k(1) ≤ 0 andEQUATIONThus, we can conclude that k(ψ) < 0 for all ψ ≥ 1. Therefore, using (198) we findEQUATIONStep 1: When ψ = 1, we haveEQUATIONTo show g (1) h(1) ≤ 1, we equivalently showEQUATIONwhich is obvious since a =m 2 pa,ℓ / d log(m 2pa,ℓ / d+1) . Thus, we haveEQUATIONStep 2: The gradient of g(ψ) h(ψ) can be calculated asEQUATIONWe have g ′ (ψ) < 0, 1 + ag(ψ) > 0, and h(ψ) > 0. Thus, we only show that m(ψ) = 1 + ag(ψ) log(1 + ag(ψ)) -ag(ψ) > 0. We show this by noting thatEQUATIONandEQUATIONThus, we conclude that m(ψ) > 0 for ψ ≥ 1 andEQUATIONCombine the results in ( 201), ( 204) and ( 210) we show the inequality in (189). Now, by applying lemma 11 to (188), we obtainT t=1 X pa(i) (t) [V i,a i (t) (t)] -1 ≤ 10 m 2 pa,ℓ log(m 2 pa,ℓ /d + 1) |T i (t)| log m 2 pa,ℓ d |T i (t)| + 1 + 10 m 2 pa,ℓ log(m 2 pa,ℓ /d + 1)|T * i (t)| log m 2 pa,ℓ d |T * i (t)| + 1 . (211)Since the function g(t) = 10EQUATIONBased on Lemma 9, we are able to bound the following lemma, which provide three important properties. Lemma 12. With probability at least 1 -2δ, the following properties hold:EQUATION.Lastly, we define Ψ 0 as the time instance that GA-LCB performs UCB to select interventions. Now, we are ready to prove the final theorem. We start from the decomposition of the regret as followsEQUATIONEQUATIONwhere ( 267) is due to 2 -S ≤ 1 √ T and Lemma 13. Then we use fact that for d ≥ 2 we haveEQUATIONSince S = O(log T ) and m pa,ℓ ≤ m, we haveEQUATIONFinally, to get the regret bound in Theorem 2, we combine the results in Theorem 1 and (272), we conclude that with probability at least 1 -3δ, we haveEQUATIONF Notes on proof of Corollary 1 and Corollary 2In the setting of Corollary 1, the causal graph G is known. We do not need to use GA-LCB-SL algorithm to do structure learning. Instead, we can directly employ the GA-LCB-ID algorithm with the true parent sets {pa(i) | i ∈ [N ]}. Hence, we can follow the proof of Theorem 2 to prove Corollary 1. The difference is that we will use the exact maximum in-degree d instead of κd as we do not have that error due to the imperfect graph structure learning. Consequently, the regret bound simplifies, and we obtain the result stated in Corollary 1.For Let Π be the set of all policies on the set of stochastic bandit environments I. The minimax regret is defined asEQUATIONwhere E π,I0 [R(T )] denotes the expected regret of policy π on the bandit instance I 0 . We will consider a set Ĩ, instead of I, that contains two bandit instances. By definition of minimax regret, a lower bound for the regret of any policy on Ĩ also is a lower bound for the minimax regret sinceEQUATIONFollowing this property, the central idea of the proof is as follows. Consider two linear SEM causal bandit instances that differ by a small fraction and are hard to distinguish. At the same time, we can construct them to have different optimal interventions, indicating that a selection policy cannot incur small regret for both at the same time under the same data realization. Note that, the difference of the rewards, or equivalently the regrets, observed by these two bandit instances under the same intervention can be computed by tracing the effect of the differing edge parameter over all the paths that end at the reward node. We carefully build graphs to maximize the number of such paths for given d and L. In this section, we provide details of these steps.We consider the hierarchical graph as depicted in Figure 8 , which consists of L layers each with d nodes. Adjacent layers are fully connected. There exists a final layer with one node fully connected to layer L. We label the j-th node on layer ℓ by X (ℓ-1)d+j and the reward node by X N .We consider two linear SEM causal bandit instances I and Ī that share the same graph G. I is parameterized by I ≜ {B, B * , ϵ} and Ī is parameterized by I ≜ { B, B * , ϵ}. For each instance I ∈ Ĩ and for edges (i → j) ∈ E with causal depth L i = 0 or L i > 1, let the weights of all observational edges be m B , and all interventional edges be m B -δ where δ ∈ (0, m B ) will be determined later. In other words, for i, j ∈EQUATIONEQUATIONLet noise terms follow the standard Gaussian distribution for nodes except the first layer, i.e., ϵ i ∼ N (0, 1) for all i ∈ [N ], i > d. Furthermore, we let the noise in the first layer follow a Gaussian distribution N (1, 1) for all i ∈ [d].The only difference between instances in I and Ī is in the weights for the nodes with causal depth L i = 1. Note that nodes are labeled from d + 1 to 2d. We have for iEQUATIONEQUATIONNext, consider a fixed bandit policy π that generates the following filtration over timeEQUATIONThe decision of π at time t is F t-1 -measurable. Accordingly, define P t and Pt as the probability measures induced by F t by t rounds of interaction between π and the two bandit instances I and Ĩ.When it is clear from context, we use the shorthand terms P and P for P T and PT , respectively. We will show that π cannot suffer small regret in both instances at the same time and under the same filtration F T .By Lemma 1, since all the elements of observational and interventional weights are non-negative, the optimal intervention is the one that maximizes the value of each entry of B a and Ba . The optimal action between two bandit instances only differs in nodes with L j = 2. This means optimal intervention should include node j if elements of . Define E j lb as the event in which the decision on node d is sup-optimal at least T 2 times after T rounds on bandit instance I, i.e.,EQUATIONWe note that the event E j lb is defined on the σ-algebra defined by the filtration F t , that induces both P t and Pt . We compute the expected instantaneous regret when node i ∈ [d + 1, 2d] is chosen sub-optimal in the first bandit instance and the total regret is the summation over these nodes. Note that each path passes node that node i contributes to the expected regret. Furthermore, since every weight is positive, in I, we have when the intervention on node {d + 1, • • • , 2d} is chosen to be suboptimal, the impact on the average regret is δm L-1 B d L-1 since there are d L-2 paths of length L -1 from node j to N and the difference between weights as δ is multiplied with a m B factor for every edge along a path. Then, by the definition of E lb , we haveEQUATIONEQUATIONwhere (281) holds as we break down the regret and (282) holds due to the definition of E j lb in (279). Similarly, for Ī, each node {d + 1, • • • , 2d} that is not intervened, it will occur at least δm L-1 B d L-1 regret. Applying the same steps as in (280),-(282), we obtainEQUATIONBy combining (282) and (285) we haveEQUATIONNext, we characterize a lower bound on P(E lb ) + P(E c lb ), which involves the Kullback-Leibler (KL) divergence between P and P, denoted by D KL (P ∥ P). For this purpose, we leverage the following theorem.Theorem 4 (Bretagnolle-Huber inequality). Let P and P be probability measures on the same measurable space (Ω, F) and let A ∈ F be an arbitrary event. Then, P(A) + P(A c ) ≥ It remains to compute exp(-D KL (P ∥ P)) to conclude our proof, for which we leverage the following result.Lemma 16. The KL divergence between P and P, the probability measures induced by F t on I and Ĩ, is equal toEQUATION)Proof: Note that a Bayesian network factorizes asEQUATIONAdditionally, the two bandit instances differ only in the mechanism of the first layer. Then, D KL (P ∥ P) can be decomposed as Hence, we only need to analyze D KL (P(X d+j ) ∥ P(X d+j ) | X pa(d+j) ) under two cases: (i) when node (d + j) is observed, and (ii) node (d + j) is intervened. We have thatEQUATION)By noting that • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.EQUATIONEQUATIONEQUATIONJustification: The research only include the synthetic dataset and hence, do not have potential potential harmfulness.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).38th Conference on Neural Information Processing Systems (NeurIPS 2024).We note that assuming only an upper bound on the in-degree is sufficient to achieve the same regret bound.For matrix V = U + I, we denote the effective smallest eigenvalues by λmin (V) ≜ σ 2 min (A) + 1. 


Decision: The paper studies causal bandit with unknown causal graph structure and soft interventions. The reviewers acknowledge that the paper addresses an important problem extension in causal bandits with significant results. The issues addressed by the reviewers are mostly addressed by the authors during the rebuttal stage. Overall, the paper provides solid contributions to the study of causal bandits, and I recommend accepting the paper.

Reviews: review: paper_summary: paper_summary: The authors consider a stationary causal bandit problem for an unknown linear model with weight matrix $B \in \mathbb{R}^{N \times N}$ and noise vector $\epsilon \in \mathbb{R}^N$. In their setup, intervention on the node $X_i$ replaces all of the weights into $X_i$ with those from another unknown matrix $B^* \in \mathbb{R}^{N \times N}$.

The authors propose a two-phase approach: learning the causal structure by (1a) learning a valid topological ordering (1b) learning the causal DAG, and then (2) applying a phase elimination algorithm to learn the best pulls over a time horizon $T$. 

The authors also include a minimax lower bound for their problem setup. For either bound, the authors argue that the maximum causal depth $L$ and a known upper bound (denoted here as $d^+$ for clarity) for the maximum in-degree $d$ are the relevant topological parameters.

It is assumed throughout that interventions do not affect the causal structure: $\mathrm{Supp}(B)=\mathrm{Supp}(B^*)$.
strength_weakness: strength_weakness: The authors make an informal claim near the beginning of the paper, which I suspect affects the tightness of their bounds. They argue that all conditional independencies must be learned for regret minimisation with an unknown graph. However, it should be clear that only the nodes in $\mathrm{An}(Y)$ are relevant. In stage (1b), beginning with the reward node $N$ and iteratively learning the parent sets $\mathrm{pa}(N)$ then $\mathrm{pa}(\mathrm{pa}(N))$ should be a more efficient approach. This suggests to me that the relevant causal path depth in their bounds is actually $L_N$, while the relevant in-degrees in stages (1) and (2) of their algorithm are $d^+$ and $d^* := \mathrm{max}_{i \in an(N) \cup N} (d_i)$ respectively.

The authors also seem to ignore the parameter $R := (m/\eta)^2$ in their regret bounds. While it is not a topological property of the population DAG, it is certainly an important parameter in the problem setting and could be thought of as a kind of guaranteed minimal signal-to-noise ratio (SNR). From the definition of $T_1$ there should be a linear scaling of the regret bounds with $R$, up to a poly-log factor. This SNR is important for real-world modelling and could also offer insights into relaxing assumptions 3, 4 and/or 5. 

Putting the above together, my estimation of the same upper regret bound is $\tilde{O}((cd^*)^{L_N - 1/2} \sqrt{T} + R + d^+ + N)$. Please correct me otherwise and/or update the manuscript. I will revise my score and evaluation of the paper's soundness following the authors' rebuttal. 

The authors provide a very minimal experiment, relegated to the appendix. It would have been informative to see parameter sweeps and experiments with random DAGs to compare their bounds with empirical scalings. 

The authors should make no mention of the possibility of hidden confounders and whether their models can incorporate this. In particular, the claim that only $\mathrm{pa}(N)$ are possibly optimal with hard interventions is false - see [1] for details.

[1] Sanghack Lee and Elias Bareinboim, *Structural Causal Bandits: Where to Intervene?*, NeurIPS 2018.
questions: questions: Does your approach assume causal sufficiency? In particular, are noise terms assumed to be mutually independent (i.e., $\mathrm{Corr}(\epsilon_i, \epsilon_j) = \delta_{ij}$)?

I do not understand the first case in for the estimator for the ancestors of $i$ in equation (9): it appears to read "if $i$ is not the reward node but has decedents then it can't have any ancestors". Is this a typo? 

In table 1, the meaning of $K$ in the benchmark approaches should be indicated. Is this the number of possible hard interventions on a node for categorical data or something else?
limitations: limitations: Yes, the authors provide some key underlying assumptions. Whether causal sufficiency is assumed should be indicated either way.
paper_summary: paper_summary: This paper studies the linear scm setting for causal bandits. In particular, there are two vectors associated with the linear response of every node, and the learner may independently choose which of the two vectors to use. The value as well as the graph are unknown. Hence, the action space is 2**number_nodes. The authors provide an algorithm with a regret upper bound that nearly matches a lower bound, also presented.
strength_weakness: strength_weakness: There are some technical concerns; please see the questions below.
questions: questions: What does assuming that B_i and B_i^* have the same support buy you?

Is the Lasso calibrated for the max number of parents?

The bound you have on kappa in (27) is very big, O(m^2). Doesn’t this make Theorem 1, part 2 trivial?

Is assumption 5 necessary? Why can’t you argue that soft interventions that would break assumption 5 would have a minimal effect on the expected loss and therefore only contribute a small amount to the regret? One might even be able to have a bound that is adaptive to eta. Or do you need it for graph discovery?

What is c, or at least what does it depend on?

Why use ridge regression for estimating B, B*? They are assumed sparse, after all. 

Why do you need to solve an optimization problem over 2^|A|? Won’t the solution be on a corner of the |A|-dimensional hypercube, so a continuous relaxation would suffice?

Can you provide some intuition for what the lower bound construction looks like?
limitations: limitations: No limitations discussed in the main body.
paper_summary: paper_summary: The paper considered a specific setting in the causal bandits problem where 1) the graph is unknown, 2) the causal model is linear , and 3) the action set consists of $2^{N}$ soft interventions.
To tackle the problem, the author proposed an algorithm that first learns the causal structure and then uses UCB-based approaches to find the best action and minimize the regret. The regret of the algorithm is analyzed for both cases: with and without the knowledge of the graph.
strength_weakness: strength_weakness: 1- The algorithm assumes that the causal graph does not contain latent variables.

2- The algorithm requires access to identifiability parameters, which is an unrealistic assumption.

3- The set of interventions is limited, for each node, we only have one soft intervention.
questions: questions: Can you provide a discussion for the above points?

1- I expected in the regret bound, the identifiability parameter would take part similar to previous work in an unknown setting. What is the intuition behind excluding it in this setting?

2- I didn’t understand why you took an expectation in Theorem 2. The theorem should show that with high probability, the regret is less than a certain bound. Why is it necessary to take an expectation? Note that you defined regret with implicit expectation over the randomness of rewards in Equation 5.
limitations: limitations: Yes.

Comments: title: Thanks for the response
comment: We are grateful to the reviewer for the great suggestion. Indeed -- we agree that modeling the latent confounders via modifying the noise model is an effective of integrating them into the causal bandit model. We certainly agree that is an important next line of research in the causal bandit literature.
Again, we thank the reviewer for the thoughtful point. We'll add a comment to the revised manuscript to emphasize linearity in $m$. We'll be also happy to address any remaining concerns. 

Based on the discussions, we'd be grateful if the reviewer considers re-evaluating their rating of the paper.
Many thanks to the authors for their thoughtful and detailed responses, which have addressed my major concerns and questions. 

In light of this, I will upgrade my overall rating to a 7: Accept, and my soundness rating to a 3: Good. My high overall score is based off the significance and novelty of the authors' contribution. 

I suspect correlated noise variables (i.e., latent confounders) could be incorporated into the authors' analysis, which presents one exciting avenue for future work.
Thanks, I agree that a linear scaling with m is not avoidable. I had a suspicion that it could have super-linear scaling, as the probability of error bounds degrade in m so I would expect some sample complexity terms to at least pick up a log(m) to compensate.
Thanks for your reply. I understood the answer to my question in the following sentence: "Extensions to an infinite number of post-intervention models can be a potential extension. That necessitates learning an infinite number of interventional distributions, which to the best of our knowledge even for simpler settings (e.g., knowing the topology or even interventional distributions) is an open question.", Thanks for your clarification.
Thanks for giving us a chance to clarify this. Please note $B_i$ is *not* the interventional value of the random variable $X_i$ generated by node $i$. Rather, it specifies the mechanism for generating it.

**Post-interventional random variables:** Specifically, upon intervening on node $i$, the random variable $X_i$ can take any arbitrary real value. Its value is not limited to only one or finite number of choices. Specifically, by applying a soft intervention on node $i$, we are changing its conditional distribution $\mathbb{P}(X_i \ | \  X_{{\sf pa}(i)})$ to a distinct conditional distribution. The post-intervention random variable $X_i$ will be generated according to the post-intervention conditional distribution. This is in contrast to $do$ interventions that specify a choice for $X_i$ (which essentially means placing the entire post-interventional conditional probability on a singular value).

**Post-interventional SEMs:** Since we are working with linear SEMs, both pre- and post-interventional conditional distributions are fully specified by matrices $B$ and $B^*$ as well as the exogenous noise model. We are assuming that all these (i.e., $B$, $B^*$, and noise distribution) are fully *unknown*. This means that the pre- and post-interventional distributions are fully *unknown*. Our algorithm is learning all these, which includes learning  $B$ and $B^*$ (their support and their real-valued entries).  The complexity of learning all $2N$ such vectors $\{B_i,B^*_i:i\in[N]\} $is already included in the regret. We have considered one post-intervention SEM $B^*$. This can be readily extended to any finite number of post-intervention SEMs. Extensions to an infinite number of post-intervention models can be a potential extension. That necessitates learning an *infinite* number of interventional distributions, which to the best of our knowledge even for simpler settings (e.g., knowing the topology or even interventional distributions) is an open question.

So, if we are understanding the reviewer’s concern correctly, having one single post-intervention $B_i^*$ does *not* mean that we are forcing $X_i$ to take only one value. Rather, we are changing the conditional distribution that generates $X_i$ and it still can take a real value generated by the interventional distribution (and this is a generalization of $do$ interventions that specify the $X_i$ to take a specific deterministic value – which in the context of causal bandits has a finite number of possibilities).
Just for clarification regarding soft interventions. I expected that you define it in the following way. By soft intervention on node $i$, we can change any entries of $B_i$ to any values (with some restriction). But in your setting, by soft intervention, we can only change $B_i$ to $B^*_i$. Could you discuss the complexity of the former setting? Is it not learnable? I understand the theoretical contribution of the paper, and my judgment is based on that.
As the reviewer points to, we have consistently mentioned that we focus on soft interventions. This is the most general form of intervention and subsumes hard and $do$ interventions.

If the reviewer is asking about one versus multiple interventions per node, we re-emphasize that using one is standard in the causal bandit literature for notational simplicity. Extensions from one to multiple interventions is trivial. A constant 2 will be replaced by $K$ (number of interventions) in cardinality of the intervention space.

We kindly ask the review to base their judgment on the theoretical contribution of this paper: this paper significantly extends the scope of the causal bandit literature by entirely removing the assumption about knowing the graph topology and general soft interventions. All our other assumptions are either in line with or more relaxed compared to those in the existing literature. We are glad that the reviewers have not pointed to any technical flaws in the analysis.
Thanks for your response. based on the current result, the upper bound is $\mathcal{O} \left ( (N -1) ^{(N-3/2)}\sqrt{T} \right)$? If so, it seems that, compared to the classic UCB for this instance, the regret bound is not particularly advantageous. It may be beneficial to discuss the improved instance-dependent regret, as you mentioned, in the revised version.

I intend to maintain my current score; however, I have concerns regarding soft interventions. In the title, abstract, and introduction, the authors claim to propose an algorithm for soft intervention cases. However, in the problem formulation, they define only a single soft intervention per node, which was unexpected.
Thank you for the clarification. To lay some context for discussion, we would like to address this in the dichotomy of instance-dependent versus class-level regret analysis. The former analyzes the performance of a policy on a specific bandit instance while the latter captures the performance over a class of instances. In this context, for any causal bandit algorithm (including ours), one can discuss 
- Instance-dependent regret analysis, which involves analyzing a policy for a specific causal bandit instance (e.g., with a specific graph topology).
- Class-level analysis, which involves analyzing a policy designed for a class of causal bandits (e.g., causal bandits with maximum degree $d$ and causal depth $L$, which is standard in causal bandit literature).

Given this context, we address the regret of the example proposed by the reviewer in both settings: 

**Class-level regret for the class of graphs with maximum in-degree $d$ and causal depth $L$:** The UCB-1 algorithm can have a class-level regret that scales as $\tilde{\mathcal{O}} \big(2^{\frac{d^L}{2}} \sqrt{T}\big)$ (e.g., in the reverse tree graph). On the other hand, our class-regret scales as $\tilde{\mathcal{O}}\Big( d^{L - \frac{1}{2}} \sqrt{T}\Big)$. 

**Instance-dependent regret for the chain graph:** As the UCB-1 algorithm does not take the causal structure into account, its regret remains as $\tilde{\mathcal{O}}(2^{N/2}  \sqrt{T})$. On the other hand, we can readily analyze the instance-dependent regret of our algorithm, which scales as $(N-1)\sqrt{T}$. To get the instance-level regret of our algorithm, let's examine the source of the $d^{L-1/2}$ term in our regret:. if we define the maximum in-degree at each causal depth as $d_{(\ell)} = \max_{i\in [N], L_i=\ell} d_i$ for $\ell \in [L]$, then the $d^{L-1/2}$ term can be refined to the instance-dependent term $\sqrt{d} \prod_{\ell=1}^{N-1} d_{(\ell)}$ (in the proofs we need to replace $d$ with $d_{(\ell)}$). In the term $\sqrt{d} \prod_{\ell=1}^{N-1} d_{(\ell)}$, $\sqrt{d}$ reflects the complexity of the linear function, and the product accounts for the compounding effect where each causal depth contributes to $d_{(\ell)}$.
**Scale with $m$:** We appreciate the reviewer for raising this important question. The regret bounds scale linearly in $m$. An intuitive reason is that if we multiply all the random variables of the system by a constant $M$ then the final reward will be scaled up with $M$ and the regret of any algorithm scales up with a constant $M$. As discussed at the end of Section 2, the dependence of the regret on $m$ is linear even in simpler linear bandit problems (e.g., [25]). An exact same linear dependence has been also reported in other causal bandit settings [14,17]. We note that in some literature such dependence might not appear explicitly since they normalize the range of the random variables or rewards to fall in the range [0,1], i.e., by setting $m=1$ (e.g., causal bandit with $do$ intervention [1,6] and linear bandits [R2]). 

[R2]: Abbasi-Yadkori et. al. ​​Improved algorithms for linear stochastic bandits, NeurIPS 2011

**Other concerns:** We are glad that the reviewer’s concerns about Theorem 1 are addressed. We will be happy to also elaborate more on other concerns if there are still remaining ones.
Thanks for the detailed response, and I think many of my concerns are answered, concerning theorem 1. On a related note, how does the regret bound scale with m?
Sorry, it seems you misunderstood my example. My example was a chain graph where all variables also are parents of Xn (reward node). So, the graph has $2(n-1)$ edges (if I'm not wrong, $d = N -1$ and $L = N-1$)
We thank the reviewer for this comparison question. A chain graph is a **special** simple graph with a maximum in-degree of $d=1$ and a maximum causal depth of $L=N-1$.

**Regret Comparison:** For UCB-based algorithms in the classic bandit setting **without knowing** the graph,  the regret scales as $\tilde{\mathcal{O}}(\sqrt{|\mathcal{A}| T}) = \tilde{\mathcal{O}}(\sqrt{2^N T})$. In contrast when the the graph is known, the regret reduces **significantly** and it scales as  $\tilde{\mathcal{O}}(\sqrt{T})$ (e.g. Corollary 1). The reason for the higher regret of the UCB-based algorithm without knowing the graph is that due to the lack of graph structure, the algorithm treats each set of interventions as an independent arm. This means that there are $2^N$ possible intervention sets, leading to the regret mentioned above.

**Computational Cost:** Here we compare the computational cost of three algorithms: UCB-1 (a UCB-based algorithm for the classic bandit problem), LinSEM-UCB [14] (a UCB-based algorithm for causal bandits), and our proposed algorithm. The UCB-1 algorithm incurs a computational cost of $\mathcal{O}(2^N)$ because it needs to select the best intervention from $\mathcal{A}$ with $|\mathcal{A}|=2^N$. The LinSEM-UCB algorithm, designed for causal bandits, has a computational cost of $\mathcal{O}(N \cdot 2^{2N})$, as each UCB iteration requires maximization over the vertices of an $N$-dimensional hypercube, with each vertex having a computational cost of $\mathcal{O}(N)$. Additionally, it selects the best intervention from $\mathcal{A}$. In contrast, our algorithm has a computational cost of $\mathcal{O}(N |\mathcal{A}_s|)$, where $\mathcal{A}_s$ represents the set of possible optimal interventions at time $t$ after elimination, with $|\mathcal{A}_s| \leq 2^N$ and $|\mathcal{A}_s| \rightarrow 1$ as $t \rightarrow \infty$. This is because the computational cost of the confidence width calculation in equation (19) is $\mathcal{O}(1)$ (recall that $d=1$), and the UCB only requires the estimated mean value (of order $\mathcal{O}(N)$) and $N$ confidence widths. Consequently, our algorithm has a slightly higher computational cost at the beginning but becomes more efficient as $|\mathcal{A}_s|$ decreases to $\frac{2^N}{N}$, which can be achieved in a few elimination steps.

Overall, our approach achieves a substantial reduction in regret while maintaining a comparable computational cost to UCB-1 in the context of this simple graph.

Finally, we emphasize that as the graph topology becomes more complex, the UCB-based algorithms further degrade. For example, in hierarchical graphs, the intervention set size is $2^{dL+1}$, leading to a regret of $\tilde{\mathcal{O}}(\sqrt{2^{dL+1} T})$, compared to our algorithm’s $\tilde{\mathcal{O}}(\sqrt{d^{L-\frac{1}{2}} T})$.
Thanks for your response. I also have another question. How do you compare your algorithm and Corollary 1 with the Naive approaches (e.g., the ucb-based algorithm in classic bandit) on a specific graph like the following graph. X1 -> X2 -> .... -> Xn. Also for all $i$, Xi is the parent of Xn. It's a chain graph where all variables are parent of Xn.