Linear Causal Bandits: Unknown Graph and Soft Interventions
Authors: Zirui Yan
Ali Tajer
Venue: NeurIPS 2024 poster (2024)
Keywords: causal bandit
unknown graph
soft interventions
Primary area: bandits

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.

Linear Causal Bandits: Unknown Graph and Soft Interventions
Zirui Yan
Ali Tajer
Rensselaer Polytechnic Institute yanz11@rpi.
Rensselaer Polytechnic Institute tajer edu
edu edu
Abstract
Designing causal bandit algorithms depends on two central categories assump- tions: (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 either category. These include assuming known graphs but unknown interventional distributions, and the converse setting of assuming unknown graphs but access restrictive hard/do interventions, which removes the stochasticity and ancestral dependencies. Nevertheless, the problem in its general form, i.c., unknown graph and unknown stochastic intervention models, remains open. This paper addresses this problem and establishes that in graph with N nodes, maximum in-degree d and maximum causal path length L, after T interaction rounds the regret upper bound scales as Ó ((dd)--+ /T + d + RN) where > 1 is a constant and R is measure of intervention power. universal minimax lower bound is also established, which scales as (dd- VT). 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 (with the gap d ). On the algorithmic aspect, the paper presents novel way of designing computationally efficient CB algorithm, addressing a challenge that the existing CB algorithms using soft interventions face.
1 Motivation & Overview
Causal bandits (CBs) provide a formal framework for the sequential design of experiments over network of agents with causal interactions. The objective of CBs is to identify 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 cause- effect 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 to maximize the cumulative reward by strategically selecting the sequence of interventions that optimize notion of cumulative utility [ 2]. CBs have broad range of applications B15)
The recent advances 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 pre- and 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 2 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-13] assume that the pre- and moss-interventionall 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-18 entirely dispense with all the assumptions about the interventions' statistical models.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 learn the conditional independencies; however, when it is unknown, all the conditional independencies should be learned.
The notable results under unknown graphs include [9] which assumes that all interventional distributions are fully known. Dispensing with the assumption of interventional distributions with a focus on do is investigated analysis because of the analytical simplifications they enable. A do intervention at a node sets the random value that node pre-specified fixed value. This results in (i) removing all the causal dependence of that node on its ancestors and (ii) removing the randommess of the data generated by that node. 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 other distinct models.
[19 25 do interventions are generally more amenable to tractable
Table 1: Cumulative instance-iiddependent regrets for linear CBs.
Algorithm
Regret bound
Intervention
Scalable
Lower bound
Unknown Graph
20
Ö Ø(VKT KT + Kd
do
Q(VNKT)
GA-LCB (This paper)
soft ò ((xd)) 1.- TT + + RN
(Theorem
Known Graph
C-UCB[6
VKTT
do
L5
δ LL VNT
soft
x
Ω (d
GCB-UCH 18
(PL-LVT
soft
(Theorem
GA-LCB (this paper)
δ (d' VVT
soft
(Corollary [
uunder 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 follows.
Topology: We assume to know only the number of the nodes on the graph and the in-degree of the causal graph!! !
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 function of the time horizon and graph topology parameters. Specifically, we show the achievable regret of ((Kd))-- + d N) where graph nodes, d is the maximum in-degree the graph, is the maximum causal depth, and T is the time horizon. We also establish the minimax regret lower bound of 2(d=-2 VV))..
is constant, N is the number of
Tightness the bounds: The dependence of the achievable regret on N diminishing as T grows. Therefore, the mismatch of the achievable and the minimax regrets is on the order of d and a constant n² 1.
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 (dd-- 1 (T), which is tighter than the best known results O(d2L-1 [8].
We introduce 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 scalable algorithm as the graph size grows.
Scalabe algorithm:
Wee note that assuming only upper bound on the in-degree is sufficient to achieve the regret bound.

---

Notations. For a positive integer N E N, we define [N] _ N1}. 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 zq- The i-th column vector of matrix A denoted by [A]; and [A],, denotes the (i.j) element of A. A denotes the n-th power of matrix A for E N. 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 C [N), [[$} E {0, 1 is specified such that its elements at the coordinates included in S are set to 1, and
the rest are O. For a vector x and positive semidefinite matrix A. we define ||X|| <xx Ax as the weighted & norm. The fnorr and f--norm of vector x Rd are denoted by ||x||| and ||x|||+ respectively. The notation O is an order notation that ignores constant and poly-logarithmic factors.
2 Causal Bandit Problem Setup
Causal graph. Consider an unknown directed acyclic graph (DAG) 9 (V, (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. The set of parents of node i of ancestors and descendants of node are denoted by an(i) and de(i), respectively. We define the causal depth of node i, denoted by I4, as the length of the longest directed causal path that ends at node E [N]. According, we denote the maximum causal depth of the graph by L - max,g[N] L; and denote the maximum in-degree of the graph by d {maxie[N] [i)].)
denoted by pa(i). Similarly, the sets
Data model. DAG G represents Bayesian network, in which we denote the causal random variable associated with node E V by X,. Accordingly, we define the random vector X & .X......xx) For any A S V, X denotes the vector formed by {X; : i E A}. The extents of the cause-effect relationships among the causal variables X are specified by the following linear SEMs:
x B
where B E NRN is the edge weights matrix and é A (EI,...,EN) denotes the model noises. It is noteworthy that the element [B]5 is non-zero if and only if j E pa(i). We denote the conditional distribution of X; given its parents by P(X: Xpa(t)).
Soft stochastic interventions. We use soft interventions as the most general form of intervention. A soft intervention on node retains the ancestral dependence of X; on X paa() and its probabilistic nature. Specifically, soft intervention on node changes the conditional probability P(X;; X (xp(s)) to a distinct one denoted by Q(;; X x. i can be abstracted by a change in the vector [B], 5. We denote the post-intervention vector by [B*].- 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 E A. we define Ba as the cost-intervention weight matrix specified by
). In a linear SEM, the impact of a soft intervention on node
Bal: A 1 E [B + 1 B)
Causal bandit - problem statement. In causal bandit, a learner performs a sequence of interven- tions to optimize reward measure. Each unique set of interventions a E A is represented by an arm. Following the CB's convention, we designate node N as the reward node and its associated value XN as the reward variable. We denote the post-intervention probability measure of X induced by intervention a by Pa. and the associated expectation by Eg. Subsequently, we denote the expected value of variable X; under intervention A by
aia
(3)
Accordingly, we denote the optimal intervention by a", which is specified by
arg max UN..
(4)
aEA
The sequence of interventions over time denoted by {a(t) E N). Upon intervention a(t) in round I, the learner observes X(1)= A (I) ( and collects the reward Xw The learner's objective is to minimize the regret that it incurs with respect to omniscient oracle that has
3

---

access to the best intervention a". Hence, the average regret incurred at time t is r(t) = Ma- Pa.
Accordingly, the average cumulative regret over horizon is given by
E B(R(T)) & Tpa-
(5)
We list the set of assumptions that we make about the SEMs.
Assumption 1 (Unknown graph). We assume that the skeleton and orientation of the edges in graph g are unknown. We assume the number of nodes N and degree are known.
This assumption is in contrast to all the existing studies on soft intervention
15
Assumption 2 (Unknown conditional distributions). We assume that all observational and inter- ventional conditional distributions {P(X; Xxa(t)) : [N]] and (Q(X; Xxs()) : [N]] are unknown.
Assumption 3 (Weight matrices). The interventional and observational matrices B and B* are unknown. We assume that the range of weight matrix elements is known, i.e., there exists a known mB E R. such that [B]r S mB and [B'] S mB for all i. E [N].
Assumption 4 (Noise model). We assume that the noise statistical model is unknown. The expected noise value v & E[e] is known. We assume the noise terms are independent and bounded, i.e., there exists m. R+ such that (t) S for all E [N] and E [T].
We note the assumption that knowing d can be replaced by knowing an upper bound, and the requirement of expected noise value v 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 || linear bandits, the regret will scale linearly with this constant, Without loss of generality, assume me mB 1. Finally, we provide the following standard regularity condition on interventions to ensure sufficient distinction between the observational and interventional statistical models 20 23
|| S m. The recent study in (28) shows that in
Assumption 5 (Intervention regularity). A soft intervention node with causal depth L 2 1 shifts the expected values of the descendants of at least 7, i.e., |1500 (5,00] > n,for all E [N] and j E de(i).
Graph-Agnostic Linear Causal Bandit (GA-LCB) Algorithm
In this section, introduce our proposed algorithm 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.
Linear Causal Bandit (GA-
Algorithm overview. Identifying the best intervention a* defined in (4) hinges on learning all the possible probability distributions Pa. 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 {IP E 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 Nd non-zero entries. Hence, learning the entire set of distributions is equivalent to estimating at most 2Nd non-zero parameters of B and B This problem, however, faces the hard constraint that the estimated matrices B and B' must conform to valid DAG structure. Not enforcing this constraint gives rise to issues such as the possibility of support structures that include cycles inconsistent supports for the estimates of B and B*
For this DAG-constrained problem of estimating matrices B and B*, we take 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 identify the best intervention design. More specifically, the first step (GA-LCB- SL in Algorithm I focuses on estimating the skeleton, which is equivalent to estimating the parent sets {pa(1) : E based on seft interventions is fundamentally different from doing so based on do intervention setting 20 (23 since under do interventions, identifying pa(N) (N) suffices to determine the best intervention when there are no confounders. This is because do interventions remove all ancestral dependence
[ Forming such estimates

---

Algorithm Graph-Agnostic Linear Causal Bandit: Structure Learning (GA-LCB-SL)
1: Inputs: identifiability parameter 7), sufficient exploration conditions Ii and T-
2: 0
3: while 9 is not DAG or t (N + 1)T, do
4: Pull the arm a(Nt + 1) = and observe (t) and set f t +
5: for i IN -1 do
6: Pull the arm a(N( + i + 1) = { and observe (()
7:
Identify the ancestors set an() according to ( and construct ; 1-t+1
8:
9: if Na < <2 then Pull the (() 0 and observe X(I) until Ng T2
10: Calculate the Lasso estimator [B] as in (10)
11: Identify the parents: pa(i) = supp Laaao
Return: {i) [A]] and topologiaal ordering मे based on ancestors sets
of XN. and its statistical model can be specified only by the value assigned to its parents under 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 the reward. Therefore, inevitably, we need to estimate the parent sets (pa(i) i [N]]. Motivated by these, Algorithm I provides estimates {pa(i) i [N]] such that with a high probability: (1) pa S pa(i): and (2) (pa(t) S c(pa(t)l for 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 sample complexity of Odd 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(t) i [N]], the GA-LCB-ID algorithm performs successive refinement of the set A to identify the intervention set of interest. [S] is denoted by A, C Ae-1 with Ai è A. To identify the interventions to be eliminated at stage s, the GA-LCB-ID ID algorithm identifies the interventions whose UCB values fall below the maximum in A. minus a bandwidth m22 Such successive refinement allows to calculate UCBs only for promising interventions, leading 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.
This process consists of S = log vT) refinement stages, where the refined set in stage
3.1 Step 1: CB-based Structure Learning
Our approach to using a sequence of interventions to learn the unknown graph G consists of two procedures. starts by identifying the correct ancestors an(i) for [N]. After Ti rounds of exploration, for all j [N] we compute the mean estimates as
(t)
Σ
Xi(T), and (t)
Σ Xi(T), (6)
No(t)
(or(1) re(()a(7)=((1)
r)())
where (t) denote the number of times the a E selected up to time t
(t)
Σ ((a(7)= a} =
rElt
Subsequently, the algorithm identifies descendants sets de(i) for E [N] according to:
de(i) { [M] |A,00 Px(0) "
(8)
2
5

---

Algorithm 2 Graph-Agnostic Linear Causal Bandit: Intervention Design (GA-LCB-ID)
1: Inputs: Time Horizon T, S = loog vT], exploration parameter a E R fidentifiability parameter 17, sufficient exploration conditions T, and T2) or (edge set E),
2: if E not given then
3:
(pa E [N), =Graphl.eamnng(y, Ti, T2)
4: set 8 - 1 and Ai =
do 6: for [N] do [N]]d
5: while
7:
Calculate the ridge regression estimators [B 1)]; and [B*(t 1)], as in and
8:
for E A. do
9:
for i E मे do
10:
Calculate estimated mean jui,a (1) as in 17
11:
Calculate the width Wi,a(1 1) according (19)
12:
Calculate (C - - AN 1) + WN aN
13:
if
WN, 1) m VT
1 for all A. then
14:
Choose a(t) according to (33 until
15:
Break
16:
while W.. - 1) I m2- for all a E As do
17:
Update As+ as in 22) and set 8 +
Choose a(t) As such that w((1) m2
according to which clearly de(i). Note that [de(t)] 0 indicates that node is a root node (intervention on a root node does not change the conditional distributions). Furthermore, we also estimate the ancestors sets (áñ(i) [N] according to:
an = [N] i and ([de(j) or de(s)))-
The algorithm will check whether the ancestor sets will form DAG. This is confirmed by verifying that there does exist i.j E [AV] such that j E de(i) and de(j). To further refine the estimate of the parent set, the algorithm initiates T, rounds of additional explorations. This ensures the algorithm has gathered sufficient observational data to accurately identify the parent set pa()). Subsequently,
(4gg(4))ant))) for i [N] as (g(1)
uses the Lasso estimator on the ancestors set with À = m
Lasso
argmin
Σ
(X((T) - Xan(s) (T)) + A111111
(10)
(t)
d mi))
rE(t),n(TT-@
Based on these steps, Algorithm| identifies the parent set of node i [N] as
pa( = supp ( (Blaa00)
(11)
Specifically, Algorithm returns the estimates {pa(t) : E [N]] and a valid topological order based on ancestor information. Given causal graph G. an ordered permutation of [M]. denoted by
said to be a valid topological order if for each edge j} j) E ε, we have क; < Ty. This can be
achieved by iteratively adding nodes such that the parents of that node already included in
Finally, we note that we set the exploration constants Ti and T2 as follows.
32m
2N22
Ti
log
and T2 = cd log( (N).
(12)
n
8
where e is a constant.
3.2 Step 2: Sequential Design of Interventions
Assume at the stage S A log vT), the algorithm maintains refined set Å. C A. It starts with the set of candidates Á₁ A and successively refines this set by performing elimination on the previous refined set using the UCB width. Based 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
( B+ [N]] follows
B(4) [V:(0]=
E
(T(((T)(X((T)) - -;),
(13)
and [B' & [VT(0)-
E
()) vz).
(14)
rE(()NEa(T)
where we have defined the gram matrices as
Vi(1) A Σ Xau(t)) IN VI(1) A Σ (x (T) + IN, (15)
rE(()
rE(()SEA(T)
and IN is the diagonal matrix with elements 1. Accordingly, denote estimate of Bg for intervention a A at time t by (t),, which are constructed as follows.
[B] - (i E & a) (4), + [ a)(B(())
(16)
Based on the estimates, we construct the estimator of mean value Pi,a
(t)a(t) (f.(Ba(t)), v)
(17)
where f.aa.) A Ez B ;- Given all the information up time t, the next decision is to identify the intervention a(t + 1). For this purpose, standard UCB-type approach entails forming confidence interval for the mean estimates followed by identifying the intervention that achieves the citimiization-basee approach and instead compute
largest UCB. In algorithm, avoid such
the UCBs according to
UCBa(t)
(N + (t).
(18)
in which refer to (t) the UCB width and it is defined recursively follows.
(t)
Σ
Wja + aa
(0)- + mp.. A (V i (t))
(19)
(EPa(()
in which E IR+ controls the size of width, and {ma,e | l [Z]] is defined as mpa,t A max,g(N)) [ Il- Subsequently, we define the post-intervention gram matrices Vi,a, (1)
as follows.
V Via, (t) & 1{a((s) = (t) + (a,(s) = =(v(s)=0\Vv(t))
(20)
where (s(s) = 1fi E a(s) E 1). A standard UCB-type approach selects the intervention set that maximizes UCB, within A. However, this involves solving optimization problems over set of cardinality 2-V, which becomes another computational bottleneck. Phased elimination occurs when
the uncertainty of the mean estimator, captured by the UCB width, is sufficiently small for all interventions in the candidate subset.
WN.a(t - 1) S m2- Y A.,
(21)
where 8 is the current stage. At this point, only the interventions with UCB values close to the optimistic one are retained.
Å.t fa f UCBa(t) 2 max UCBa(!) - -m2
(22)
=EA,
Alternatively, if (21) does not holds, there is some intervention Å, such that (1) > m2 which prevents the perform of elimination. This intervention will then be selected at time f + 1 to accelerate the elimination.
This procedure continues until /. T or if the stopping criterion (i.n(() S m V 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(t + 1) = arg max UCBa(t).
(23)
a
Finally, we note that we set a = v log( NT 8
+ Va.
7

---

3.3 Computational Efficiency
We compare the computational efficiency of our algorithm with those of the existing algorithms for linear SEMs with soft interventions in [15] [8]. The algorithmss in these studies adopt similar procedures: they find estimators for observational and interventional weights, form the confidence ellipsoids for the weights, and solve joint optimization problem to calculate UCBs as
UCBa
max (fN (Ba). 2)
(24)
B.CCa
where C. = KEE Cia and Ci = 1 E a);; + 1fi & a)C; are confidence regions, fN is compounding function (see [13] Lemma 1] or Appendix Cp. Subsequently, the interventions are chosen those that maximize UCB,
a(l + 1) = arg max UCB
(25)
aEA
All the algorithms estimate the observational and interventional weights by solving 2.V ridge re- gressions, 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 [3]. the optimization problem in 24 for CBs is neither convex concave. This is due 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, to the reward value will be multiplied by all the coefficients along the path connecting X; to the reward node (see Appendix [C more details). When there are multiple such paths, the aggregate weight products of all paths carry the contribution of X; 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 optimization problem over discrete of size 2 the compu- tational complexity of which grows exponentially with N. To circumvent this, GA-LCB randomly chooses the under-explored intervention (line [8]. UCB optimization specified in (23) is performed only when the refinement process is completed, indicating that (23) will be solved over small subset of sufficiently good interventions.
4 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 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.
4.1 Graph-independent bounds
We first show the ceeph-nddepndeen bounds that hold for 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 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 Kmax and Kmin as the maximum and minimum eigenvalue of the following second moment with null intervention:
Kmax
Amax (Eg [XX]]] Kmin Amin (Eg [XX
(26)
Theorem 1 (Achievable Graph Skeleton Learning). Under Assumptions the GA-I.CB-SL. algorithu ensures that
8

---

1. with probability 1 1 5 we have valid topological ordering म; and
2. with probability at least 1 - for all i E [N] we have pa(i) S pa(i) and [pa(t)] S klpa(t)),
where e. is defined as
9 min m² Kmax + m²²
16 log
(2dN)
372
(27)
Kmin
Leveraging the result of Theorem we characterize the achievable regret of GA-LCB. Theorem (Achievable Regret), Under Assumptions 5 the GA-LCB-ID algorithm ensures that with probability 1 35
[[((T) < ((xx))--vI++d + RN),
(28)
where we have defined R
We note that R represents the guaranteed maximum sigmal-to-inters titr---ooiiteeeeioooo-oooooe poweerrro-ooroorreeee ratio. This ratio measures the difficulty in distinguishing between observational and interventional distributions (the higher R, the harder distinguish).
To emphasize the cost learning the skeleton, in the next corollary, we provide the achievable regret of the GA-LCB algorithm when the graph skeleton is known.
Corollary (Achievable Regret Known Skeleton). When the graph skeleton is known, under the GA-LCB-ID ensures that
same setting as in Theorem with probability
E E[R(T)] - Õ(d-+tVT)
(29)
Comparing Corollary with Theorem observe that the term O R.N) represents the cost do structure learning, while x 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
lower bound for setting with
unknown graph. We will present one such lower bound and show that even though it expectedly looser than lower bound for 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
Theorem 3 (Regret Lower Bound). For any given skeleton with parameters d and L, there exists causal bandit instance such that the expected regret of any algorithm is at least
B(R(T)) 2 a(aa- VT).
(30)
When comparing the upper bound in Theorem 2 and the lower bound in Theorem 3 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 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 [ indicaaess 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 Ö + RNN) 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 ed 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 previouslyknnwwn gap of d'.

---

Dependence on T. Regret upper and lower bound both scale with T at the rate O(VT).
Linear bandits. Finally, we note that despite some similarities, our problem is significantly different from linear bandits since, as shown in Appendix C linear causal bandits, the reward is non-linear with respect to the parameters or the interventions. This is the case for even =. We note that our regret's 's dependence on d differs from that the linear bandit setting. In linear bandits, the regret scales linearly with d as shown in [1 32). When L = 1, the regret upper bound in our case scales as ((vdT). and the regret lower bound scales as (((TT). We conjecture that the regret upper bound is tighter because more accurately captures the uncertainty of parameter estimation.
Regret bounds comparisons. GA-LCB provides significanty improved regret bounds compared to LinSEM-UCB [I5] and GCB-UCB [8. Specifically, under the known graph skeleton setting, GA-LCB achieves a d' factor improvement in the regret bounds compared to LinSEM- UCB. While GCB-UCB removes the /N factor, underperforms compared to LinSEM-UCH Furthermore, our regret upper bound has only d factor more than the lower bound.
4.2 Graph-dependent Regret Bound
The graph-indepennn bounds can be further refined to recover graph-dependent regret bounds that use the instance-level information. To account for the actual influence the graph parameters on the reward node, define the effective maximum in-degree d, = maX4ean(N ()) d, and the effective maximum causal depth as L,, max)ean(N) I4- We have the natural inequalities de S d and L., I L. To characterize the graph-dependent bound, we need to slightly modify the GA-LCB-IID algorithm. Specifically, we only need to identify the optimal intervention within A' = 2 and estimate the column vectors [[B]: 1 E á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- .eanh-Dependent. When Le and de are known, the modified GA-LCB-ID ID algorithm ensures that with probability 1 1 36
[[R(T)) & Ō((nde) VT + d +NN
(31)
By comparing the upper bound in Theorem 2 and Corollary we observe that the cost of learning the graph remains intact. The reason is that we must explore intereenions on every node i E [N] to identify the ancestor relationships. even when regret improvements are due to the part of learning the best intervention, particularly in relation to the graph topology. The term ( in Theorem 2 is replaced with (sd_)).-5 The change is due to the fact we do not need to learn optimal intervention in the whole graph as the interventions on non-ancestor nodes will not affect the reward. Instead, it suffices to learn only the optimal intervention on the subgraph & formed by an(N) and the parameters of G.
information known. Hence, all the
5 Conclusions
In this paper, we have solved the causal bandit problem with unknown graph skeletons under general stochastic interventions. We have proposed implementable algorithm and provided regret analysis for both unknown and known graph skeletons. The unknown skeleton affects the achievable regret bounds in two ways: term that is linear in d + N but independent of I'' and ed factor due the imperfect identification of the parents. When the graph skeleton is unknown, the achievable regret bounds and the minimax regret lower bound are shown match up d factor. Compared the existing algorithms, the proposed algorithm is more amenable to scalable implementation.
Acknowledgments
This work was supported in part by the U.S. National Science Foundation under Grant 2M192319996. and in part by the Rensselacr-IBM. Future of Computing Research Collaboration (FCRC).
10

---

References
[1] Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good inter- ventions via causal inference. In Proc. Advances in Neural Information Processing Systems, Barcelona, Spain, December 2016.
[2] Elias Bareinboim, Andrew Fomeyy and Judea Pearl Bandits with unobserved confounders: causal approach. In Proc. Advances in Neural Information Processing Systems, Montréal, Canada, December 2015.
[3] Ossama Ahmed, Frederik Träuble, Anirudh Goyal, Alexander Neitz, Manuel Wuthrich, Yoshua Bengio, Bernhard Schölkopf, and Stefan Bauer. Causalworld: A robotic manipulation bench- mark for causal structure and transfer learning. In Proc. International Conference on Learning Representations, virtual, May 2021.
[4] Siqi Liu, Kay Choong See, Kee Yuan Ngiam, Leo Anthony Celi, Xingzhi Sun, and Mengling Feng. Reinforcement learning for clinical decision support in critical care: Comprehensive review, Journal of Medical Internet Research, 22(7), July 2020.
[5] Yan Zhao, Mitchell Goodman, Sameer Kanase, Shenghe Xu, Yannick Kimmel, Brent Payne, Saad Khan, and Patricia Grao. Mitigating targeting bias in content recommendation with causal bandits. In Proc. ACM Conference on Recommender Systems Workshop on Mulri-Objecteo Recommender Systems, Seattle, WA, September 2022.
[6] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge. In Proc. Conference Uncertainty in Artificial Intelligence, virtual, August 2020.
[7] Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits, In Proc. International Conference on Artificial Intelligence and Statisties, virtual, April 2021.
[8] Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, and Ken-ichi Kawarabayashi. Causal bandits with propagating inference. In Proc. International Conference on Machine Learning, Stockholm, Sweden, July 2018.
[9] Aurghya Maiti, Vineet Nair, and Gaurav Sinha. A causal bandit approach to learning good atomic interventions in presence of unobserved confounders. In Proc. Conference on Uncertainty in Artificial Intelligence, Eindhoven, Netherlands, August 2022.
[10] Nuoya Xiong and Wei Chen. Pure exploration of causal bandits. In Proc. International Conference on Learning Representations, Kigali, Rwanda, May 2023.
[11] Shi Feng and Wei Chen. Combinatorial causal bandits. In Proc. AAAI Conference Artificial Intelligence, Washington, D.C., February 2023.
[12] Ayush Sawamn,, Rahul Madhavan, Gaurav Sinha, and Siddharth Barman. Learning good interventions causal graphs via covering. In Proc. Conference on Uncertainty in Artificial Intelligence, Pittsburgh, PA, 2023.
[13] Lai Wei, Muhammad Qasim Elahi, Mahsa Ghasemi, and Murat Kocaoglu. Approximate alloca- tion matching for structural causal bandits with unobserved confounders. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[14] Rajat Sen, Karthikeyan Shanmugam, Alexandros G. Dimakis, and Sanjay Shakkottai. Identify- ing best interventions through online importance sampling. In Proc. International Conference on Machine Learning. Sydney, Australia, August 2017.
[15] Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Causal bandits for linear structural equation models. Journal of Machine Learning Research, 24(297):1559, 2023.
[16] Scott Sussex, Anastasiia Makarova, and Andreas Krause. Model-based causal bayesian opti- mization. Proc. International Conference on Learning Representations, Kigali, Rwanda, May 2023.
11

---

[17] Scott Sussex, Pier Giuseppe Sessa, Anastasia Makarova, and Andreas Krause. Adversarial causal bayesian optimization. In Proc. International Conference on Learning Representations. Kigali, Rwanda, May 2023.
[18] Zirui Yan, Dennis Wei, Dmitriy Katz-Rogozhnikov Prasanna Sattigeri, and Ali Tajer. Causal bandits with general causal models and interventions. In Proc. International Conference on Artificial Intelligence and Statisties, Valencia, Spain, May 2024.
[19] Blair Bilodeau, Linbo Wang, and Daniel M Roy. Adaptively exploiting d-separators with causal bandits. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2022.
[20] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Causal bandits with unknown graph structure. In Proc. Advances in Neural Information Processing Systems, virtual, December 2021.
[21] Amoud De Kroon, Joris Mooij, and Danielle Belgrave. Causal bandits without prior knowledge using separating sets. In Proc. Conference on Causal Learning and Reasoning, Eureka, CA, April 2022.
[22] Shi Feng, Nuoya Xiong, and Wei Chen. Combinatorial causal bandits without graph skeleton. In Asian Conference on Machine Learning, Hanoi, Vietnam, December 2023.
[23] Mikhail Konobeev, Jalal Etesami, and Negar Kiyavash. Causal bandits without graph learning. arXiv:2301.11411.
[24] Alan Malek, Virginia Aglietti, and Silvia Chiappa. Additive causal bandits with unknown graph.
In Proc. International Conference Machine Learning, Honolulu, Hawaii, July 2023.
[25] Muhammad Qasim Elahi, Mahsa Ghasemi, and Murat Kocaoglu. Partial structure discovery is
sufficient for no-regret learning in causal bandits. In Proc. International Conference on Machine Learning Workshop on Foundations of Reinforcement Learning and Control-Connection and Perspectives, Vienna, Austria, July 2024.
[26] Zirui Yan, Arpan Mukherjee, Burak Vaneı, and Ali Tajer. Robust causal bandits for linear models. IEEE Journal on Selected Areas in Information Theory, 3:78-93, March 2024.
[27] Zirui Yan, Arpan Mukherjee, Burak Vancı, and Ali Tajer. Improved bound for robust causal bandits with linear models. In Proc. IEEE International Symposium on Information Theory, Athens, Greece, July 2024.
[28] Hamish Flynn, David Reeb, Melih Kandemir, and Jan Peters. Improved algorithms for stochastic linear bandits using tail bounds for martingale mixtures. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[29] Asish Ghoshal and Jean Honorio. Learning linear structural equation models in polynomial time and sample complexity. In Proc. International Conference on Artificial Intelligence and Statistics, Playa Blanca, Spain, April 2018.
[30] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, Cam- bridge, UK, 2020.
[31] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Proc. Conference on Learning Theory, Helsinki, Finland, July 2008
[32] Yingkai Li, Yining Wang, and Yuan Zhou, Nearly minimax-optimal regret for linearly parame- terized bandits. IEEE Transactions on Information Theory, 70(1):372-388, 2023.
[33] Peter Bickel, Ya' acov Ritov, and Alexandre B Tsybakov. Simultaneous analysis of lasso and dantzig selector. Annals of Statistics, 1705-11777773 2009.
[34] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. In Proc. Advances in Neural Information Processing Systems, Virtual, December 2020.
12

---

[35] Martin J Wainwright. High-dimensional statistics: A non-asymitotic viewpoint, volume 48. Cambridge University Press, Cambridge, UK, 2019.
[36] Adel Javanmard and Andrea Montanari. Confidence intervals and hypothesis testing for high- dimensional regression. Journal of Machine Learning Research, 15(1):2869-2909, 2014.
[37] Peter Auer. Using confidence bounds for exploitation-exxlorrtion trade-offs, Journal of Machine Learning Research, 3(Nov):397 422, 2002.
[38] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear pay- off functions. In Proc. International Conference on Artificial Intelligence and Statistics, Ft. Lauderdale, FL, April 2011.
13

---

Linear Causal Bandits: Unknown Graph and Soft Interventions Supplementary Materials
Table of Contents
Empirical Evaluations
B Additional Notations
17
Decomposition of Node-level Rewards
18
Proof Theorem
(Structure Learning)
E
Proof of Theorem 2 (Intervention Design)
24
Bounding UCB width
24
E.2 Bound sum of width of UCB
26
Bounding the time periods elimination
E,4 Bounding the regret
38
Notes on proof Corollary and Corollary
38
Proof of Theorem (oower Bound)
39
A Empirical Evaluations
In this section, we assess the regret performance of GA-LCB. As the most relevant existing approaches, compare the regret of our algorithm those of LinSEM-UCB [15] and GCB-UCB [18), which are designed for causal bandits with soft interventions.
This graph consists of (L+ 1) layers, with the first 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 nodes in layer L. The number of nodes in this graph is N = dL +
Causal graph. We consider the hierarchical graph illustrated in Figure 1
Parameter setting. The noise terms {e, [N]} are set be drawn from the uniform distribution (O, 1). We set the non-zero elements in the observational and interventional weights matrix to 1 and 0.5, respectively. We evaluate L E (2, 4, 6). The experiment was conducted using 2 CPUs from Mac Mini 2023. We set Ti = T2 = 500 for experiments with L 2, Ti T2 1000 for experiments with
and L
Algorithm settings. The theoretical guarantees relied on specific technical conditions on parameters. empirical performance
We observe that the algorithms designed can provide setter-than-foree by tuning the parameters involved. Specifically, we adjusted the parameters X, a, and the sufficient exploration times and Tz. We observe that setting a = 0.1 yields reasonable performance. The experiments repeated 100 times, and the average cumulative regret is reported.
14

---

X1
X2
X3
X4
Xs
X
Xx-9
Xx-2
XN-
a.y
-
XN
N
Figure 1: Example bierarchical graph.
10000
25000
Cumulative Regret
Cumulative Regret
8000
20000
GA-LCB
6000
GA-LCB(known)
15000
GA-LCB GA-LLB(kknow)
4000
GCB-UCB
10000
LinSEM-UCB
2000
5000
0
10000
20000 30000 40000
10000 20000 30000 40000
Number of Iterations T
Number of Iterations 7
Figure 2: Cumulative regret with L 2.
Figure 3: Cumulative regret with L 4.
50000
Cumulative Regret
40000
30000
GA-LCB GA-LCB(known)
20000
10000
0
10000 20000 30000
40000
Number of Iterations T
Figure Cumulative regret with 6.
Regret performance. In Figure 2 we present the cumulative regret of GA-LCB algorithm and other algorithms with the hierarchical graph with d and L 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 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
15

---

1e6
Cumulative Regret
2.5
old -3)
GA-LCB
Cumulative Regret
800000
old--)
GA-LCB
2.0
-ld-1)
600000
o(dh-1)
1.5
400000
1.0
200000
0.5
0.0
0
2
8
Figure Cumulative regret with different
Figure 5: Cumulative regret with different length L under hierarchical graph with d 2.
degree d under hierarchical graph with J. = 2.
settings when the maximum causal depth is L. 4 in Figure and T. 6 in Figure scalability of the GA-LCB algorithm. Besides, comparing the regret of known and unknown settings, see the additional cost of structured learning is diminishing, which is desirable. The fluctuation of GA-LCB under the known graph setting is due to imperfect phased eliminations which remove the interventions with larger expected values first.
4 We show the
GA-LCB
40-
GA-LCB(knnww)
35-
GCB-UCB
LinSEM-UCB
Running Time
20
15
10
L=2
Figure 7: Computational time of different algorithms.
Scaling with L: Scaling of the regret with respect to the causal depth is depicted in Figure 3 for
the setting of 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 (2x)* (i.e., exponential in L). The empirical results in Figure Segure/Scorroo 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 is depicted in Figure for a hierarchical graph with L We increase the number of sufficient exploration parameters Ti and Ty to ensure we accommodate all settings with different degrees. The theoretical predictions suggest that our algorithm's 's regret scales as d3/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. the hierarchical graph with 4, which considered sufficiently large in the related studies, the GA-LCB still demonstrates notable stronger running time.
16

---

B Additional Notations
In this section, we present the notations that will be useful in our analyses. We denote the singular values of matrix A E MxN with M 2 N in the descending order by
(A 2 (2 2 ... 2 (A)
(32)
In the proofs, the analyses often involve with zero-padded vectors and their corresponding matrices (e.g., Xpa(() and (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 with rank k, by
max (A) - (A() and miin (A) 2 ox(A).
(33)
For square matrix U = AA NNN, we denote the effective largest and smallest eigenvalues by
max (U) (U)
-
o max (A)
and Amin (U) (U) o (A).
(34)
Then we construct data matrices that are related to gram matrices, At time t E N and for any node i [N]. the data matrices (t(t) E x and (t) e RCxN consist of the weighted observational and interventional data, respectively. Specifically, for any T E [t] and i [N]. we define
[UT A ((a((T) 0) X pa(s) pats) (T). and [U:
(35)
((a((T) 1I pa(s) (a)))(T)
(36)
We also define the observation matrix that used for Lasso estimator U, () E R that stores the observational data on the ancestor's set.
U (t)) (a((T) = x (r)
(37)
We also define the data vector Da(() E RC and D2(() E T&' as
[D;(), A ((a((T) = ()((((T) vi), and [P:()], & 1(a((T) 1)(x((T) 14)
(38)
(39)
Similarly denote the relevant data matrices for node [N] under intervention E A by
(1) A (aa(()) = (1) + (a.(1) O)U,()),
(40)
Vi,a, (t) A ((a = (t) + ((a(t)) (t).
(41)
Di.a, (t) 1{a((t) = (t) + ((a(() O)D,(t).
(42)
Define (t) as the number of times that node i E [N] is intervened, and Nt(t) as its complement
(T) 4 Σ (ai(T)=11 =))
(43)
and N:(() A 1- N;().
(44)
Accordingly, for any E [N] and E N, define
Ni (t) 1 (a=(() = ()) + (a, O))
(45)
For A, we define the pseudo estimated variables Xa(t) and pseudo underground variables Xa(t) is the random variable at time t generated according to the following linear SEMs
x.(() B (1) (1)8x(())))))))))) +(((),
(46)
and (1 = B (t()) (())
(47)
For matrix V U we denote the effective smallest eigenvalues by Amin (V) A o (A) + 1.
17

---

which share the same c(t) acorss the different interventions.
Finally, let denote the second moment of the parents of node i under intervention E A with unknown weight matrices B and B by
- Eg
X
Xan(())
(48)
Accordingly, we denote the lower and upper bounds on the minimum and maximum singular values of these moments by
(iia):
Jmin
Emin
min min, VE[N]
(49)
mi,,,ax
maxx
Frmax
A min max.
(50)
iE[N]
We note due the Cauchy interlacing theorem, we have
Kmin Rimin
I Rimax I Kmax
(51)
Finally, we (x) represent the diagonal matrix with elements in x.
C Decomposition of Node-level Rewards
Similar to 15 Lemma 1], we present the following decomposition for the expected value of the variable X; for [N]. We note our design of the mean value estimator in (17) based on this lemma.
Lemma 1. Given intervention
A, the value of node X; is related to the noise vector via Th
X, (Ba), e). where f.(Ba)
Ele
[B]] Consequently, the expected value of X4 under
intervention a
14a (B.(),), v)
(52)
Proof. To capture the contribution of ej on node i, we use the fact that the entry row j and column of B is the sum aggregate of the weight products along all paths from node j node that have the exact length f. Since the longest length will be L;, the term Σt= [Ba]j becomes the aggregated sum of weight products along all paths from node node regardless of path length. We denote this sum by
L
f BB.)
[
(53)
Ê=
We note that the noise at any time is independent of the process that decides B,, Therefore, the expected value of X, under intervention is
La
Uia = Ea [X
= E
Σ
B
5)
=
(Ba) v)
(54)
D Proof of Theorem (Structure Learning)
The proof is divided into two parts. First, we show that Ti = 32m² log( 2N2 is sufficient to identify the ancestors sets and a valid topological ordering with probability at least 1 5. Subsequently, we show that with a probability of least 6, Lasso regression yields the desired estimates for the parent sets.
Part 1: topological ordering. In this part, we show that de(i) C de(i). Based on this, we will see an efficient topological ordering would be natural. Recall the definition of de(i) and an(1) in (8) and (9), respectively, it is equivalent to show that for E [N] with L, 2 all j E de(i), we have jă /,,(,)]= > 3 and for all j an()), we have 1ū (55 < 3. We note that the bounded noises that satisfy Assumption are I-sub-Gaussian. After sufficient exploration, the mean estimators fg and Ag defined in (6) will be close enough to the true means
18

---

Mj,0 and Mj, with high probability, respectively. When the mean estimates are accurate enough, based on Assumption we show that 3 can be used to separate descendants from non-descendants
based on the value of 11,,0 Pzal- Based on the definition of 13,00 and $3,0 in (6 we have
P P(A50 1g00
")
PP P(RR0
4
(55)
2T y"
S 2 exp
(56)
4m
8
(57)
N2
where (55) holds because Hoeffidingss inequality and Similarly, we have
(7
holds since the definition Ti in 12
P P(1 -
2
(58)
2N
We define error events in which the mean estimates have a large error as follows.
7 Ero - {1i50 M4,0l S 4
and |p5(0) 15.00 $ " 4'
Aj (N
(59)
By taking union bound and leveraging 57
58
we obtain
P(ETo) S N
N2 5
(60)
Next, we prove that under event Eio. we can correctly identify de(i) for all node i E [M]. Jf de(i).
to evaluate the gap [²,00 (3,(1) we leverage the following relationship:
1p5.0 P5.00)
= [p5.. (3,00) + (15,0 - P3.00 + (1366) - A.,1))
(61)
S |0 - p3, + 1,3,0 - أمy + |4400 - 4,,00.
(62)
where 62 is due to the triangle inequality. Thus, for all i [N []d j E de(()) we have
103.0
P3.00)
2 |p300 |,,07 |A..0 p3,0 |ps.00) -.)
(63)
(64)
4 4
(65)
On the other hand, when j $ de(i), we have 13.0 Mj.(1). based which we obtain
103,0
11j,0 P).00 15,01
(66)
|ăz0 M5,00 |A Mg.00
(67)
n/2.
(68)
In conclusion, with probability 1-8, the estimates of descendants sets de(i) = de(i) for node i E [N] with L, > with probability least 1 8. Hence, with probability at least 8 the an(i) defined in (9) will be the best set we can find, that is an(i)= C an()) for E [N] and for i E an(i) an()), we can infer that is a root node. Besides, the topological ordering valid.
Lasso regression. In this part, we establish a sparsity property of the Lasso estimator in linear causal bandit, which inspired by [33] and [4 We consider the case when T2 > Ti. The case for T3 < Ti can be analyzed similarly. We prove for fixed i E [N] as it is the same for all i E [N]. When the ancestors sets and topological ordering are correct with probability at least 1 - from Part 1. We define the time instance T3 = NT, T2 Ti be the time that the Lasso estimators are calculated.
Part 2:
We show that when T2 Z dl log( N)) and when ancestors sets and topological ordering are correct, with probability at least - 8, the Lasso estimates satisfy the desired property. The proof consists of three steps. In the first step, show that the Lasso estimates provide a bounded cardinality,
19

---

that is for i E [M] we have |pa(t) - (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 E [N] we prove ppa(i) C [pa())] Finally, we take union bounds on all nodes E [N] to get the desired result.
Step 1: Bounded cardinality, In this step we show [pa(t) S k| pa)).. Recall that the Lasso estimator in the feature selection stage is defined
(1 1
B BLLasoo]
argmin PERIAE
E
(Xi(T) 0 (x)())(T)) +1110111)
(69)
(t)() TE(1),(T)==)
We state some preliminary properties of the Lasso estimator and later show that our estimator satisfies the conditions for these properties.
Property (Restricted eigenvalues). Let - supp([B])) define the cone
C(S) - { supp(0) = an))), |10s- 11 s [10
(70)
Then for all 0 E C(S), there exists some positive constant x' such that the observation matrix
U (t))((a) E RRt (2x)) satisfies the condition
in (1)01 K 1
(71)
t Property (Column normalized). We say that U, (t) (t) is column-normallzed if
| (t)al
S m,, Vj pa(1).
(72)
Vt
Lemma 2. Consider a d-sparse linear regression and assume that design matrix Uz,(() E Given the Lasso estimator with regularization parameter = -4 4m [lg([an())))/ then the following properties hold with probability at least 1 -
[(x(an(0) satisfies Properties 2
-The estimation ervor under fn-ormm of any optimal solution [ [Lass]] satisfies
335
Theorem
7.13]:
d
2 an (1)1
B
Blaso]
[B]
(73)
Rd
The mean square prediction error of any optimal solution
B
Lasioj satisfies [35 Theorem 7.20]:
(s)
(B [ [BI:)
9
d log( an (1)1//8)
(74)
k
For j E án(i) define the random variables
bij
Σ (e((t) -v)
(75)
No
TE)=))a(7)==
Since (m)))())()
m, the Hoeffding's inequality for sub-Gaussian random variables implies
Σ X,(t) - v.) 2 25) < 2exp (-2
P
(76)
2.No (t)m²)
We note that content have (t) Tz. For j E [N], define E,, the event that g, is contained the interval close to mean value, i.e.,
2m2 log
4N 5n())
Eb.,
|br S V
(77)
T2
20

---

Based on the probability bounds in (76). we have
6
P(E..,) S
(78)
2N an())
Accordingly, define
Eb. U Ebr
(79)
SEan(()
By taking union bound and leveraging
78). we obtain
P ((
S
Σ
bb.
< an(()) 2N (n)
(80)
2N
(i)
From the Karush- Karush-Kuhn-a Kuhn-Tuckee (KKT) condition of Lasso regression, the solution
[ Lasso] satisfies
T2 Σ X,(t) (Xi(t) [ Xan(s) (t) sign (B!ano)),
1 * 0 (81)
(T)
Σ
X,(t) (x((t) B Xsmc)(()) S
if B La
1. 0. (82)
T2
Therefore, we have
1
Σ
Xy(t) [B], (t) [BLaso / (ta(t)(t))
T2
a=(=)
1
Σ
(t) (x((t)
B Lasso X (ta(s((t))
Σ Xy(t)e(t).
(83)
T2
T2 rE(t),a(r==0
rE(t),a(T)=0)
20g
1N shis)
Since A mp
under event Eg., we have
72
Σ
X,(1) (B)7 X (1)
B X (paro(()
2 A/2, if [ asso
1/. # #0. (84)
T2
rE(Ts))a(7==0
Based on 84
we can have the following lower bound
Σ (jEa((s)
Σ
Xy(() (BB) X (t) - -i BLusno X (aaco(t)
T3
rE(T)))a(()==
2 (t)
Σ
Xy(t) B Xpa(1) (t) BLaso x
(85)
To
jEsupp mon
TE (())))
2
supp
B [BLassoj,
|.)|
(86)
4
where (85) holds since an) S B [lsso))) and (86) holds due to 844. On the other hand, define the uncentered empirical covariance matrix
ΣS
T2 (n))))) (Tz) (,) (Tx)
(87)
Let Ri, = Tmax ES
Then we have
Tmax
U (i) U, (Ts)/T2)
T2 max (UT U (Ts)
(88)
Now we need high probability bound for Φmax- In order to proceed, we need upper and lower bounds for the maximum and minimum singular values of (t). However, these bounds depend
21

---

on the number of non-zero rows of (z,an(e) matrices, which equals to value of the random variable Nia(t) (t). Let us define the weighted constant
In - max { (nm²² T2,, 7"m22
(89)
We define the error events corresponding to the maximum and minimum singular values of U (Ta) as follows.
E, 6 min (U (n1)) (Tb) V max (0, 0.min Tn.
Omax (Us,aa(()))) T2Rs,,0mas + In
(90)
Lemma 3. [I5
Lemma 8] The probability of the error events Et( are upper bounded as
3r2
((E,(t)) & dexp
(91)
16
Thus, by setting
16 3
log
2dN 8
), we have with probability
we have
2N
max (Us,n(())) (t)) T2Rs, mmxxx max
(92)
Hence, with probability 8 have
mi,max = max (U (U,,sn(s) U Ui,a(t//TT
(93)
= J Tmax U (U,in())) Uz,an(e)
1
(94)
T2
m.,00max
(95)
T2
max {am? TT, a²m²
Amax
(96)
T2
16
2dN
16
2ddN
Emax + m2 max
log
log
(97)
3T,
3T,
16
2d.
Kmax + m
log
(98)
3T2
where we use 92 in (55) and the last inequality is due T3 2 dllog(N). Since Ki, has the natural upper bound m we define
16
2dN
Ko a min m² Kmax + m²
log
(99)
372
Combined with (98) we know that
Ri, S Ko
(100)
based on which we have
Σ
Σ
X,(1) [B]7 X Xpa(t) - Lasso Xpacos())
(101)
T
jEPa(t)
<rE(Ts)a(77==0
(U (Uz,an(i)
(B), U (n)) (7') B Lasoo [:) T U Us,5((1) (Ta) (,)(()) (Tx)
(
T
(U (1))) (Ta) B]; U (3) (Ta) Blasso
(102)
< Ro T2
| (3) (Ts) B Lasso]
U U (Ta)
(103)
where T02) holds due to the matrix formulation of the equation and the definition of U U, (Ta) in and 103 holds due to (10).
37
22

---

Combining all the results in 86 and (03)), we find that with probability at least 1
No
46p 2
Jsupp
[ Lasso
[;)
(U,,an())
[B [Lasso]] - (,,h((s) [B]i
[
(104)
The speed of convergence of Lasso estimators depends on how rapidly the term ||U,,an()) [
U (i)) B decreases. We now ensure D satisfies Property I with = Kmin,0/2 when T2 2
log( (+)) The uncentered empirical covariance matrix defined in (87) satisfies
E (.)) Cov
2,,0
(105)
We need the notion of restricted eigenvalue defined follows.
Definition 1. Given symmetric matrix H E Rdddd positive integer k, and L > O, the restricted eigenvalue of H is defined
(0, HO) |00|||
2² (H, L)
min SC skld),
min
:0 IE 1|s==11h 1h L &110sl
(106)
It is easy to see U, s,n((s) (Ta) (Ta) 1/2 has independent sub-Gaussian rows with sub-Gaussian norm
1-1 1/2 If the population covariance matrix meets the restricted eigenvalue --11-X an))) d/ m,0,min" 1,, 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 satisfies
To 2 4c, K. min log(elan(i)//c)
(107)
for some c, 2000 and c' = 10 i, max / K, Then the following condition holds
1 P (1 k, 2 (EE,,K9) 2 1 -1-20 2exp
T2
(108)
4c 1,0,min
1/2
Noting ((E,k,9) 2
x: 1/2 i, miin subsequently get
P
33 k)
Kg.0.min
2 1 - 2exp (bc;Tb).
(109)
2
where 46 R
172 This guarantees E satisfies Property in the appendix with Ko
8x,8,anin
2
It can be readily verified that Property 2 holds. Applying the in-sample prediction enror bound in Lemma we have with probability at least
N
18 log Nisn(E)
d log( Nian(()
18
U (,)(()) BLLSO (1))n()) (O
T3
Kinin
T2
Kinin
T2
(110)
Putting
(104 and 1110 together, with probability at least
N: we have
28
9K 9k/pa(i)] x| xl|a(i)]
ppa(1) < |supp Lasso (assss)))]
(111)
Kmin
Step 2: Containing pa(i) set. This step is to verify the variable screening property of the Lasso
estimator, that is supp( B Lasso] (:) 2 supp BB),) Since we set
4d log(NN
T2 min
(112)
min (es B B
by using Lemma it holds that with probability at least 1
2N
min (B),)
g.sl
| [BLaso
Lasso - Blolooo
(113)
23

---

where in the last inequality we use the fact that || 1l 2 llae.
Now prove the variable screening property by contradiction. If there exists j such that j supp [B]:) but $ supp [ Lasso
k)) we have
B Lasso
B B = [
> || LBLsso
[Blilo
(114)
On the other hand,
[ Lass
B Lasso
(115)
which leads to contradiction. Hence, we conclude that supp ( 2 supp((B)).
Step 3: Union bounds. By taking Union bounds on N nodes with probability at least 1 - 26, for all
i [N], we have
pa(1) _ pa(x), and ppa(t) & xlpa(1))
(116)
E Proof of Theorem 2 (Intervention Design)
This proof leverages technique initially introduced by [37 and further developed by 38 and for contextual linear bandit setting. However, unlike their settings, we face stochastic environments and compound effects due to the causal structures. In the proof, address the added uncertainty
32
introduced by noise from the parent variables, which requires careful handling. In the proof of Theorem we work with the estimate of the maximum in-degree, denoted by d e max4e[N] [pa())
which, with probability at least 25, satisfies d < kd, as proved in Theorem I However, cover the proof for Corollary [ and Corollary 2 where the proof needs to deal with d and de, respectively, use the notation d to represent d, and (a(i) to represent pa(t) throughout. Besides, we work the time instances from T3 to 7 for GA-LCBB 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 Section | 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
E.1 Bounding UCB width
In this section, we begin by proving the following estimation error lemma, that is for node E f. if we can observe the contextual observation Xpa(i),as a tighter contextual UCB width can achieved, as shown in the following lemma.
Lemma 4, For E â and
A, define the true UCB width as
iiaa (t)
Σ
Wja max
[
(117)
aEd
jE
where a = 1122oo((2NT) have
+ Va With probability at least 1 - 5 $ for all a E A and j E an(i) we
8za(1) - [)x(()-X)aa(0) (1)a(1).
(118)
Proof: We first provide high probability bound on the exploration bonus || (t)ll (0)- via Azuma's 's inequality and then prove this lemma via induction on the causal depth L,.
High probability bound. Due to the statistical independence of the observation samples U (1) and (t) for all e A. we have (t)) = 0, where ex(t) A (e.(1), ,e((t) Hence, for

---

all E A we have
q Ui (t]lV (t)l X aa))))a((t)) 3 max || (I
(119)
aed
23² maxacd [ (1) (+)-
< exxp
(120)
Ui.,, La, (t) - X pa (t) (t)l²
< 2 exp (-2,32)
(121)
(122)
TN
where (200) holds since Azuma's inequality implies, and [12 is due to the following fact
max REAA
|X
pa(s), (t) (v., (0),
(0]-+
(123)
(xp((t).a (t)l [v....0)) (0]-
(124)
Xpa(1) a (1) VV, (t) (IN (t (1)) (V (t)]= (xa(t)..
(125)
x (t) i.a, UU) (t) U,a (t)[V L.a (t)] (()]]]XXp(tee (t)
(126)
|| (t)l k, (p((aaxp(i)aatt)))
(127)
and we use B 1 log NT in 122 which corresponding the first term in a used for the UCB width in Theorem
Next, we prove the Lemma 4 by induction.
Base step: L 1. For node [N] with causal depth L; 1, we show that for all a E A with probability 1 - TN have
[ia(t) Xia(t) S
| (Xpa(t))ll max aeA
(128)
We start by decomposing the left-hand side in (128) as follows.
(ia(() (() [Ba(1]] & (1)()).(() -Ba] X (()
(129)
[B]( & (tatt).a(t) (pa(t).(t))
D.T. (4) VV -t)))tX(pa(x_)eaee (p)(
[Bald (IN Ui,, (t) UúA (t)) [Vi,a - (xx(0,a(t)
(130)
Di,,, Ut) (t)[V s.a, - -t) (t)
[Ba] (IN + Ui,a, (t) Ura, (Vs,a. 1001="Xppp0,0a -V (xp((),att)
(131)
D.,,, (1)U,, (t)[V, i.a. (4) (xpp((t))a()))
- ([Ba]] + [Ba] U, (t) TU,a, (t)) [V [ Xxa(),,)
(132)
X (D (t) - Bull (t) U (t) sa. (t)] x pa(()),
[Ba] [V..a(() (
(133)
=e (t) (t) (t) (t))-1Xp(())x(t
-[a,]] [V.. (t) X (t))
(134)
where (131) due to when Lg we have X (aa(t), (t) X (pa(i).a(t)) (t) (pa(t)- Since
|Baa]]l Vd.
we obtain
8ia(()- xxra(0) S|eT (1) (1)] Xpa(t).al (()]-
+
(x)
(135)
25

---

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 (35) follows
||[ s, (t) XX (a))(t)aatt)
(136)
V Xxpt0), (t)lV,,
t,a, (t)
[V s.a, (t) XX (t)
(137)
S xa (t)[V i.a, (t)l
(IN + Ui (t) Uso (t)) Va (t)]= pa()),a
(138)
(t)llv.)))
(139)
where (388) holds since the matrix Ui,a, (1) Ui (1) is positive semidefinite.
Combining the bounds in 135
122 and 139 completes proof for L,
Induction Step: Assume that the property holds true for causal depths up to L, = We show that will also hold for L; + 1. For this purpose, we start with the following expansion and apply the triangular inequality to find an upper bound for it. Similar to (I35), we have
(t) -xi,att)
(140)
= [Ba(t)) (8pai),a(t) - (pa(i).(tt)
+ c (t)U (t) (t)) (t)]]](pp(()) (t)
- [Ba]] [V (V) (pari..a))
(141)
Using [Ba]]]l < V and triangle inequality, we obtain
Xin (t) - (t)
- [t]()] (8pa (t) Xpaco).(tt)
(D aa (t) T [Ba] I U U (t) U Una (t)a in (t)] (xa(())a(t))
+ Vd [ [.): (()]
(142)
where the last two terms can be bounded similarly as the Base Step. It remains to bound the term
Ba (t)) (Fpa().a(t) xpa())a(())
Σ
[Ba())asl (ga((t) Xz,a(0)
(143)
jEpa(s)
From induction, we know that for all E pa()). with probability 1 5 we have
X (x))))((,(tt) < (t).
(t)
(144)
Thus, we obtain
(ta(()) X1,(tt
Σ [B(t)] wysa + all patlxaatellliia..e
(145)
jEpa(t)
<
Σ Uy.a + al x|xxallaaa - jE
(146)
Hence, conclude the proof.
E.2 Bound sum of width of UCB
To bound the sum of UCB width, we first need bound the sum of the exploration bonuses, as presented in the following lemma.
Lemma 5. For all i E [N] with L, 1==6 E,ith probability at least 1 we have
m² pa.
mm pa.e
Σ (10 S/
16 log
+
11
(147)
log m²
//d
2d
where maa.e e Ma ||x [pa(t|l
26

---

Proof: This proof will use some intermediate steps from proof of Lemma following lemma bound the exploration bonus [Xpa(t)(t) [Vi.a(t)((0) (
4 To proceed, we need the in terms of eigenvalues.
Lemma 6. Ler (t))()),(().) E [NT] denote the ordered eigenvalues of (t) such that (t)())((t) I (1,( (or E [N 1]. Then we have
(t,()) (t +1) 1) )as(t)s(()
paattt (t)lliv. (0)
S 10
(148)
)a)(t)s(t)
==1
Proof:
The proof is similar to 337 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 E [N] and a; 0 as it can be readily generalized to all cases AA To proceed, we need the following lemmas.
Lemma 7.
37 Lemma 17] For any X1 2 >2, E R, we have
(
A1
a X/ )
=UT
A1 A
A2 12-99 y )
U
(149)
for some 0 S S A1- and some orthogonal matrix U.
a²
Lemma 8. Let \1 2 ... = Xd 1. And let v1, .... 2 Va denote the effective eigenvalues of matrix
A (A1....: Ad, 1 1...1)
where z E RRN, ||z| S Ip and supp(z) [d]. There exists
Uh.j 2 0, S < S d, and the following holds:
Vj 2 >j
(150)
B/y = Xy + 2j
yh. +
Σ
Yihh
(151)
h=1
h hmi+1
4-1
Σ
yhuj S 5=
(152)
h=1
Σ Vj.h $ 1/2 xgg
(153)
Amj+1
d Σ
d
Uj
Σ j=1
\j + ||z||
(154)
/=1
An > X3 + m mp then
2
yh. -
(155)
A
Xj
m pa.
Proof: Clearly 151 implies 154) and [5T] 152) imply 153 methods similar to induction on the dimension d.
We prove the lemma by recursive
Base step: We apply Lemma 7 to obtain the following transformation:
A (A1..... de, 1,
..,1)+ +1) 2.
(156)
\1 2
21
21 2d
:
21 2d
Ad-1 + 22
Zd-1 2d Aa 2
(157)
21
2d 12d
I
À1 + 2f
21 212d-1
:
:
U
21 21
Àa-1 + 2
0
U
(158)
0
Xd
I
27

---

where in = Au + Vh,d- and Wh,d 2 0, for h = ......dd 1, and مa = Aa + 2 En=i 3h.d- And we have the fact that Σ yn I 2/z Thus Xj X, for j 1, ......d. d.
Induction Hypothesis: Assume that we can apply the base step to dimension {d', .. df and get {Uw,,.. Ua).
Induction Step: We proceed by applying Lemma with the upper left sub-matrix
A ( ) + [. z2r
-22, 1-,,,-.. 2ar
(159)
\1 + 2
212
(160)
Xu + z
X1 + o7
21 -1
0
:
:
Ua
U
(161)
21
Xa 1 +
0
0
X1
to tackle the d' row and column. Then (15)) follows from Lemma 7 since all elements in the diagonal are increasing with the induct step but no element grows by more than m2 pa.é
since ||||| S m²
pa.
Now, we are ready prove the Lemma From the definition of V (t 1) we get
V (t) + 1 (Viatt)) + X pa(() (t)x (1)
(162)
(A))) ..... Ad(1), 1) U(!)
+ U()) X (1) (()(())))))))))
(163)
where (13) we apply Lemma 8 on Vi,a,()) (t) and we define Xpa(t) (t) = ((()))
(t). Thus,
the effective eigenvalues of V (,, + 1) are the effective eigenvalues of the matrix
A (t) ..... >a(t), 1........... +)+
X pa(t) (t) X (t)
(164)
Using the notation of Lemma let X ... 2 Aa 2 be the eigenvalues of V (e (t), (vi...., be the eigenvalues of V (t) 1). and Xpares( (t). For these choices we have the following property
XT pa(c) (t) ia (t))) (1)
(t())(t)) (X) Σ Xg
(165)
To bound =3, we use [15] in Lemma 8 and obtain
23 vg A +
yh.s
(166)
For Av A3 3m from 135) obtain
27
23 27
Uh.j 5 An >3 mp
(167)
2m 2mpa.L.
and
23
Σ
Uh 5 2m 2
(168)
h:An S> A, +3m2 p.
Le h:AA>>, +3mg p.
since
|z|| S m2 L. Hence, by combining (66) and (68) we get
2) S A, + k
Shoj S - +
Σ
yh
(169)
hejiAn S SAy+3ma
28

---

and, subsequentyy
= - X3 +
Σ
ybb
(170)
ne S.y 3m po.2e
If N 2 m,,.. and d I d + 3m pa, when M, /n/4 and we have
Σ Σ
yhu
4 Σ
yh.
(171)
Xj
An
he I
+3
ybu
(172)
h j=b+1 An
1/2
An
(173)
A
h: 21
where (7T) holds as we relax the sum to include more terms and (73) holds due to 153) Thus, by
applying (70) and (173) to (165), we obtain
||xpcco (0)))
Σ
(174)
2
2
1/ X
+
Σ
yh.,
(175)
Xj
1
he Sdy +m
2 Σ
1/j
>1g
+8) 2
An.
(176)
X
An
h
Σ Vj - X1
< 10
(177)
So far, we have characterized 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, we have
m 2
"ma.t 2d
Σ (xpa)) (V))) S2 log(m?
pa.8 pa.e/ po.e/d /dd+1 1)
T log
T + 1)
(178)
Proof: The proof is similar to the proof of [37 Lemma 13), but modified handle the difference between our algorithms and the difference of the weights. Lemma 6 @implies
T Σ
T
(t (iig)s(t+++))
(+))
(0)
10
(179)
(a.(0.st))
j=1
Since a,(1) E {0, 13 we have
T
|| [xpati (t)
T Σ [{a((t) 1{a(()=00}
00
d 10 Σ
At,s(t +1 -1)
-1)
)a,s(t)
j=1
A 11 -1) 1) (t)
+ 1=1
(a;(t)) 1a;(t)==)
VV 10 Σ
(180)
j=1
To bound the width sum, leverage the closed- form solution of the following optimization problem. We define the instances at which node is intervened and not intervened as follows.
Tt(t)= (T [t] a.(r) 0} (T) {T e [t] (:(7) 1)
(181)
29

---

Lemma 10. 188 Lemma 8] The solution to the following optimization problem with a set of time instances and C > d
Σ
max (R,E
Ctj
IvV
j=1
(182)
d
s.t.
Σ j=lrEv
II
(og
+1)
i
C
1/11/
Gjj =
1, AEE v E [d]
(183)
d
We have the following property for the constraints.
Ao, (1+
Σ
I
Σ
(T
(184)
(0,(1)
1=1 (ET(())
5=1
Σ [xa(a + d
(185)
tеτ(())
$ m (T;(t)) +d,
(186)
Ao,s +1)
and II
II
mps. e (1) + d,
(187)
(t,
J=1
where (186) is due to the definition of maatt. Hence, by applying Lemma 10 in (80
we obtain
(m
mriin
Σ
paa) (t)]
(000000000000 (0) S [T.(t)VVOdd
T.(t)
+1
(E).())
(
127
+ (TT(
(7
1. (188)
Next, we use the following lemma bound (88) Lemma 11. b 1, the following inequality holds
mpa.e m
1/4
m p..ee/ /d log " vb +1 (mat++))
2b +
-15
(189)
d
log (m2 //d + 1)
pa.e/
m ./d
Proof: Let
showing (199) is equivalent to showing
log(m3 nu. /d+1)
1
m pa.e
2 1 - log
pa.t v + +1))
loog /
2b + +1} < log
(190)
d
Define
m² mpp.t
g( A vb
log
1 +
(191)
d
and
M(()) log(1 + ag(v))
(192)
Since h(v)) > 0. Showing (89 is equivalent to showing that for all 4/ > 1 we have
((b))
< 1.
(193)
h( (+))
30

---

We show it in two steps. First, we show when v = 1, derivative of the function g(b)) and h(t).
g(v2 is less than 1. Second, we show the kToj
g(t) is negative for 1a 1. To proceed, the following properties of k()
1
m
lim ((vb)
lim 10-000 v
log
+
(194)
1 100
m
m
lim n0
(195)
mh co.f //
+
(196)
where 195) is due L'Hôpital's rule. Similarly, we have
lim ((v)) = 0 v1000
(197)
Besides, the derivative of g(1b) is
m
log
m ia. 1b + 1
(
m vb + 1)
g g'((b)
d
(198)
2
m Pa.e vb + 1)
Now, let
k(bb) A m²
m2
m
pa.l
v log
1/
/ +
(199)
d
d
The sign of g'(v) is the same as k(bb when 1p > O. Furthermore, k(1) S 0 and
m pa.k
log pa.
k' (+b))
+ <0.
(200)
Thus, can conclude that k(b) < 0 for all &b 1. Therefore, using (198) we find
g'(v) <0
(201)
Step 1: When di 1, we have
9(1) log(m2 / /d+++ 1) h(1)
(202)
log(1 + a log(m2 2 /d + 1))
To show s(1) h(1) $ 1, we equivalently show
pa.e/ m² e/a.e/d +1++1111 lm pa /dd + 1),
(203)
m2 m/a /d log(mn? p0.e/ (dd1)) 1)+
which is obvious since
Thus, we have
g(1) h(1)
< 1.
(204)
Step 2: The gradient of g(w) (())
can be calculated as
((1))
g' g(())((1)))) - M(+))(1))
h(w))
h²(w))
(205)
gbb)) log(1 + ag())) (w)(w)
( g(b))
(206)
h²(0)
((1 ag(b)) log(1 + ag(+)) ag(())
(207)
1²()) (1 ag(v))
31

---

We have g'(2) < 0, 1 + ag(l)) > 0, and h(15) > O. Thus, we only need to show that m(
(1 + ag(1)) log(1 + ag(i)) - ag(w) > O. We show this by noting that
lim m( 0, 4-2
(208)
and
m (v² = ag'(v) log(1 + ag(+)) + ag'(v) ag' (w) = ag'(v) (v) log(1 + ag(v)) < <0.
(209)
Thus, we conclude that m(1) for +p 2 1 and
g(
<0 <0.
(210)
h(+b)
Combine the results in (001) 204 and (110
we show the inequality in (89
Now, by applying lemma to [88
obtain
Σ (t)()) (.a((o(()) S
log m pa.e/ e/d + [i(t))
pa.
log
m +1
pa.é
d [T((t]
m2 pa,e
(m (T00++1)
10
[T (t)
(211)
log( (m. pa.e/ // dd +
d
Since the function g(()
m pa.e
log
"pal + +1 is concave function / and [T:(1] +
log( m m /d+1j
[27 (t) = T we have
m2 mpott
"ma.e
(taa) 2
/ 1og(m2 /ttt///////// //d++/+)
T Plog
T +
(212)
2d
E.3
Bounding the time periods for elimination
Based on Lemma 9 we are able to bound the following lemma, which provide three important properties.
Lemma 12. With probability least 1 25, the following properties hold:
1. Va E A,t [T]: (t) &N.al S (N.att).
2. Vs e [S]: a² A..
3. Va As: PN,." JNa & m23-5
Proof: We prove the properties when the properties in Theorem Thold. We prove the first property using the triangle inequality. Specifically,
||X (Xpatt) (1) (-)) I pl (1)
(... pi (1) (pa(t) (000 (213)
< ( (0) V2mpa -m1 (Vroc(())))
1/2
(214)
Therefore, using the definition 199 and 117 we obtain
WN (1) wN,.(1)
(215)
Thus, by using Lemma and summing over E [T], with probability least we have
(1) - PN.l = (8Na(1) - XN.((1) S (N.a(l)) S wN.all).
(216)
32

---

The second property holds since when the first property holds, a' always satisfies the condition in the GA-LCB i.e.
line 16 17
UCB (1) max UCB, m22-9
(217)
agA,
Next, we prove the third one by induction.
Base Step: When 8 = 1 it is obvious since we have |,N S m and |ANal S m. Induction Hypothesis: Assume it holds for S Ss'.
Induction; This indicates that for = 8 + 1 we have A C Ag-1-- Additionally the condition
in line 16 implies that wa- S m2 m2-(*-1) for A. and wa- I m2 m Furthermore, the description of Ag in (22) implies
UCB( 2 UCB (1) 12200mm22-111 (x-11)
(218)
Thus, for any E Ao-1 we have
ANa 2 (CCB(-1)) (t) - m2 (--11 a
(219)
LCB((=11 (x) (t) m4 2 (6-11)
(220)
PN m4 (s-1)
(221)
where (219 holds due A.-1, 220 holds due (118) and 221 holds due the definition of UCB.
The next lemma provides upper bound on the number of trials for which alternative is chosen at the time T3 for s E [S].
Lemma 13. we define T2 the time when Ag is ended and Ast1 starts, for all [S] have
L
m
mpa.
T₂ < m
x
(a (a vJ)
v
Σ
12
8
log(mp pa. p
T3 log
2d
T3 +
E=1
(v Kmin
+ (a + vd)2v2 Σ
d
"ppa
(222)
Proof: Note that similar (213) we apply triangle inequality to get
{ (+)l + ( (t) (ta (223)
paatt) (t) (v) + V2mps,L, -1/2 (Ven)(t)(t)..
1122
(224)
Step 1: To proceed, we first bound the second term in (244 summation regarding the eigenvalues, in the following lemma.
Lemma 14. We have the following upper bound for the eigenvalues
T
1/2
(V (t))
VT + 8T +1,
(225)
min
Kmin
where 7 A mm and l2g( 1)).
In order proceed, we need upper and lower bounds the maximum and minimum singular values of Ui,a(e) (t). However, these bounds depend on the number of non-zero rows of ( matrices, which equals the values of the random variable (t) Let us define the weighted constant
Proof:
In max { tm /n, em²]
(226)
33

---

Then for every t E [T), and n E [8]. we define the error events corresponding to the maximum and minimum singular values of (t) and (t) as
((,(() _ - (((1) = n and { {mmin (U,(1) & /max {0, 7.mia 7nn
or max (U,(t)) 2 v Vitimax + +7m }.
(227)
(1) 2 (T = n and min (U)(1) S /max {0, nimin 7n
or O Fmax (U)(t)) 2 /nnmmax + +mn
(228)
Lemma 15. 15 Lemma 8) The probability the error events (i, and (i) are upper bounded
as
362
max
S dexp
(229)
16
Then we define the union error event Ei,u as
E (3 (). : e [T], E [4] (i, (())
(230)
By taking union bound and using Lemma we have
362
IP(EE
edx
(231)
16
1=
312"
S T(T + exp
(232)
16
Now turn back to E
Σ 1 2c(t)
to analyze under the complementary events & and E
Bounding term E bound.
11 ET= x(O) Since Amin (V (o)) 2 1, we have the following upper
Ax(1)
(V (1) (t)) 1.
(233)
We have
E
((E,))
Σ (t)
[[ PT
(234)
By setting &
log (T + 1)). obtain
3
T
234 P(E
NT(T+1)d T<1. + 1)))
E
1(
Σ (t)
(235)
=T
Bounding E 11 d: x100) Considering the event & we can use the following bounds on
the singular values
mmin (e) (t)) 2
max (0, Ni, (t) - 7m
(236)
Thus, the target sum can be apper-bounded as
E 1
(8
Σ
X(1)
E
1
Σ
(237)
v J (Uzaces +
1=1
T
<
E
(238)
max (N,att (f)8min - 7n +
34

---

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 function
n(x)
O.
(239)
max {0, Zhmin 7m +
In order to analyze the behavior of the function n, we introduce that when S T, we have 2.min < 7n. In this case,
2m min
as the critical point. Note
nx)) 1,
(240)
which is an increasing function over the region. Now, we are ready to bound the last term
T
T
E
Σ (t)
S E
Σ (M(Naaco(t)
(241)
t=1
We define the set time indices at which the chosen interventions are under-explored as
H4 {t E (T) (1) - 4r}
(242)
It can be readily verified that [H,] $ 8T since for node we have a; {0, 1}. Furthermore, when I E H4, we have
h(x) 1, TT.
(243)
Then we can bound the sum in
241 when Hi occurs as follows.
E
IltE H.yM(Ne,aco S 87
(244)
Next, we only need to bound the remaining part when / & Hi
T
E
Σ ilt (N))
(245)
Note that when E HSS have (1) and decreasing function. Hence,
N.(T)+4r
(T)+
Σ Mfee e H()M(N
Σ
n(s)+ +
Σ n(s).
(246)
We bound the discrete sums through integrals and define
H-(y) f n(x)dx, y 2 4T.
(247)
F=AT
Since g(x) is a positive, non-increasing function, for any K E k 2 + 1 have
n(s) $ 1 s=
Σ
n(s)ds=H,(h
(248)
#=4++1
Then, the sum in 246 is upper bounded by
NO +7)
Σ
n(s)
+
Σ
n(s) S (N,(() + 47) (+ + 4r).
(249)
#=4+1
#=4++1
Since h(r) is positive and decreasing, and Hyy) is defined as an integral of the function with positive first derivative and negative second derivative, be deduced that concave function. Thus, by applying the concavity property we have
T 44T
H~(((() + + + (t) 4r) s 2H,
(250)
2
35

---

Next, we proceed to establish an upper bound on the function H as follows.
+++
T
H,
+
4T
h(x)dr
(251)
2
z=4r
2/2
+.7
.n + dx
(252)
A=
Vatimin
3 744
dx
(253)
A=
Velimni - '/2 +
2 Kmiin 2 + 4T) In + A8Kiin To
(T'
(254)
Emin
2
(255)
Aimin
where we have used f
255), the final result for the bound constant. Combining the results in
-ar-8 dæ
2
235
244 and
T Σ
(1)
S
2 Kmin
VT + 8T 11.
(256)
Step 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,, we prove
T w (r) S (a + Vdl
L: Σ d
m pa.
mpp,t 2d
12
To log
T3
+
log(mp pa..e/ pa.e/e/de//e /d++1)
1=1
(V2VTo+888 87
+ + vdj2v2
d mpatt
(257)
Kmiin
Base step: when i E [N] and L; 1, we have
w (a(T)) 5 X (p) (0] (01- 2v 2m A (V (t))
(258)
Hence, applying Lemma and Lemma 14 we have
T
m²
mm mps. To +
Σ
w (.((7)
< 2
L.
T, log
log m2 L. dd
1)
2d
+ 2 2/2mma.l
(V22
(V
2
VT, VT, +7+++)
(259)
Fenin
36

---

Induction Step: Assume 257 holds for nodes i E [M] with L, = k - 1. Then for i E [N] and L; k, we have
T
(s) ja((T)
w
(.)(T)
1=1
1=1 jEpa(i)
T.
+
aa + vd)(IIX pa(1) pa)) (V.., (0)- + 2v 2m pa Ami (V (t)r)) (260)
t=1
m
2
m p To +1
<dx
pa.
T, log
log(m² m pa,e/ e/ d 1)
+dx (a vdj2v Σ
d² E
2
Tr, + 87 87+11
Kmin
m
Mpse To +
+ + 1
10
To log
log(mg/ +
d
(V Kimin
+ + + Vd)2V2mA
VT, 87 +1
(261)
m²
m pa.f
(a vd) _ d
10
pa.
To log
To + +
log(m² pa.e! p.ppp/p////
d
8=1
VV2VTo+8T
+ + + vd)2v2
d
(262)
where in (600) we use the definition width, (66T) holds due to induction and Lemma we have proved the following inequality for the reward node.
Hence,
T
N.(r)) S (a+ VJ)
Σ d 1-
pa.e
Ta log
m= mpa.e
T. +
Tog(m pa,e/ pe//mm//++111 /d+11)
2d
1=1
Krmin (V V VTs 87 2
+ vdj2v2
Σ
d=
"paall
(263)
1=1
By the condition of line 18 of GA-LCB we have
T
Σ
w N. N.((T)
(T) m2 "T,
(264)
Combining (663 and 264
we obtain
L Tg < (a + vd) Σe m
2a
d--12
m pa.t
log
m2
pa..
T,
+1
log(ma pa.e/ /dde//+111 +1
2d
8=1
+ (a 22)222
1.
x mmpm (V (v22
2
VT + 87 188++111)
(265)
Kmin
1=1
37

---

E,4 Bounding the regret
Lastly, we define Vo as the time instance that GA-LCB performs UCB to select interventions. Now, are ready to prove the final theorem. We start from the decomposition of the regret follows
T
E(R = Tm
Ma(()
(266)
Σ (Ma- Ma(o)
+
Σ
Σ
(ux- (a(t))
(267)
1=1:-14
s +
2m
Vol
Σ
8m2
(268)
VT
1=1
2m
Vol
Σ
8
(a
Vd) Σ d 1
m 2
pa.
Ta log
m
pa.t
T, +
TT
log(m (m² pa,e/ / 1)
2d
+ (a vdj2v2
d
mmpill (V
VT, -VV 8T V STTTTT+1
2
(269)
Kimin
t=1
pa. T
8 mpo,e d 2 log(m pa.e/ ///mma.///4o / < 2m2mmm++ + 8(a + vdys Σ
T log
+ +1
2d
t=1
2 T 87 + +1))
2
+ 22V2
(V
(270)
Aimin
where (66 is due 2-8 < /
and Lemma
13
Then use the fact that for 2 2 we have
d= -1
Σ d
< 2d = O(di-1))
(271)
d
Since S = Ollog T) and mpa,t S m, we have
E(R(T)] < 0(d--i
(272)
Finally, to get the regret bound in Theorem 2, we combine the results in Theorem and 272). we
conclude that with probability at least 30, we have
B[R(T)) o( RN + +d)
(273)
F Notes on proof of Corollary 1 and Corollary 2
In the setting Corollary 1 the causal graph is known. We do not need use GA-LCB-SL algorithm to do structure learning. Instead, we can directly employ the GA-LCB algorithm with prove
can follow the proof of Theorem Corollary [ The difference is that we will use the exact maximum in in-degree d instead of kd 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
the true parent sets {pa(i) E [N]]. Hence,
For Corollary 2 we have additional knowledge of the effective maximum in-degree de and the causal depth L.. we define d. max E an(N) pa())) from Theorem we have d, S rd.. At the same time, we can obtain a valid topological ordering 7. that only contains an(N). Hence, we can follow the proof of Theorem with maximum in-degree de and causal depth Thg and induction on n. to prove Corollary 2
38

---

3
X
X5
X
05
Xx-
Xx-
XN-1
6N-1
GV--
4,-1
X
Figure 8: Sample hierarchical graph used in the proof of Theorem 3
G
Proof of Theorem 3 (Lower Bound)
Let II be the set of all policies the set of stochastic bandit environments I. The minimax regret is defined as
inf sup E. [R(T).
(274)
#ell TeE
where RT,I, 'R(T)] denotes the expected regret of policy a on the bandit instance Zg- We will consider a set I, instead of I, that contains two bandit instances. By definition minimax regret, a lower bound for the regret of any policy on I also a lower bound for the minimax regret since
inf sup E. Zo [(T) 2
inf sup E. (R())
(275)
wEll IgEI
Tell JoEł
Following this property. the central idea of the proof is as follows. Consider two linear SEM causal bandit instances that differ by 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 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. this section, we provide details of these steps.
We consider the hierarchical graph as depicted in Figure S which consists of L layers each with d nodes. Adjacent layers are fully connected. There exists final layer with one node fully connected to layer L. We label the j-th node on layer é by ((e-1)a+5 and the reward node by XN-
We consider two linear SEM causal bandit instances I and that share the same graph g. is parameterized by (B, B,, Bc,c ef and I is parameterized by 2 {B, B", ...
For each instance E Ī and for edges (i + j) E with causal depth I = 0 or Ia > 1, let the weights of all observational edges be mB. and all interventional edges be mB determined later. In other words, for i,j E [N], if L; or L, > 1 and (i j) E E, then
where d (0. mB) will be
B B mB,
and [ [B mB - 8.
(276)
Let noise terms follow the standard Gaussian distribution for nodes except the first layer, i.e., 6; ~ (0, 1) for all E [N], > Furthermore, we let the noise in the first layer follow a Gaussian distribution (1, for all [d].
The only difference between instances in and i is the weights for the nodes with causal depth L, = 1. Note that nodes are labeled from d' + 1 to 2d. We have for i E [d + 1, 2d and j [d]
[ kd4j
[3k.d++ MB, and
B B"k.44
B Bli,4 mp 8. (277)
39

---

Next, consider fixed bandit policy x that generates the following filtration over time
Fi -
(())
(278)
The decision of π at time is F -mesuuuureelle.. Accordingly, define P. and P. as the probability measures induced by Fe by rounds of interaction between и and the two bandit instances and I. When it is clear from context, we use the shorthand terms IP and IP for Pr and Pr, respectively. We will show that π cannot suffer small regret both instances the same time and under the same filtration FT.
By Lemma ! 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 Ba and Ba. The optimal action between two bandit instances only differs in nodes with L3 2. This means optimal intervention should include node j if elements of [B] are mB and not include j otherwise, for j E [d + 1, 2d]. As result, we have a7 0 and a [d + 1, 2d]. Define E/, the event in which the decision on node sup-optimal at least times after T' rounds on bandit instance 1, i.e.
T N4+, (T) 2
c Ib
for j E [d]
(279)
We note that the event Ed, is defined on the o-algebra defined by the filtration Fr, that induces both F, and P,. We compute the expected instantaneous regret when node [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 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 8m since there are d'-2 paths of length L-1 from node j to N and the difference between weights as is multiplied with a my factor for every edge along path. Then, by the definition of Eib, we have
Ep [(() Ep
Σ
r()
(280)
Ep
Σ
Σ
1 E (l)))mm(
(281)
jE[d.2d]
d
T L
Σ
p(C))
dm
1
(282)
1=1
where (28T) holds as we break down the regret and (22) holds due to the definition E/G
279)
Similarly, for each node {d + 1, 2d] that is not intervened, it will occur at least 8m
L.-11
L-1
dd--1
regret. Applying the same steps in (280
282
we obtain
Ep [p(R(()) RE
Σ r(t)
(283)
Σ Σ
l E (m()))mmmB
(284)
jEld2/
T
P(E
8mp bmb-lda--1 2
(285)
By combining (282
and 285
we have
T
Ex R + ((())
> dm L-1 411
+PE))))
(286)
Next, we characterize a lower bound on P(E + +P(E)) which involves the Kullback-Leible (KL) divergence between IP and denoted by DRt. (TP) || P). For this purpose, we leverage the following theorem.
40

---

Theorem 4 (Bretagnolle- Huber inequality). Let P and P be probability measures on the same measurable space (S2, F) and let A E be an arbitrary event. Then,
1 P(A) P(1)
2 exp(-DRL(() P))
(287)
By invoking Theorem from 286
we obtain
T
Es [t)) + E3 [R()))
dm B
h-1 d 11-1 ((P(E)) P(
(288)
j=1
T dm b d'- d dexp(- -op---d-11 P)) P))
(289)
It remains to compute exp(-DRL(P P)) to conclude proof, for which we leverage the following result.
Lemma 16. The KL divergence between P and P,, the probability measures induced by Fs I and I, is equal to
DEL P) (
(290)
Proof: Note that a Bayesian network factorizes as
N
P(X Xx) = II P(X, Xpa(s))
(291)
Additionally, the two bandit instances differ only in the mechanism of the first layer. Then, (PL IP) can be decomposed as
(K
||
P)
DRL (P(X, Xpa(i)) IP(;; (xp(t)))
(292)
i=1
DEL (P((a+s) || P(Xa+s) | X Xpa(d+s))
(293)
Hence, we only need to analyze DKL (P(X4+g) || P(Xat5) X Xpa(d+s)) under two cases: (i) when node (d ++)) j) is observed, and (ii) node (d + j) is intervened. We have that
N (mm Σd X 1)
under I when j + d
N( - 0) Σ X; 1).
under IP when j + d E
Xj4d=
(294)
M(MB Σd X1,1),
under IP when j + d
W(mB Σ X;, 1)
under PP when j + d E
By noting that
d DKL (M(mB Σ X 1) || - 6) Σ xx,1))
(295)
i=l
= -DR((N((m) (N((mB
=
8) x1, N (mB 1),
(296)
1=1
1=1
8' X,)²
d
(297)
2
41

---

from 294
we obtain that for j E [d]
(P((((()ta) (P(Xa+s) (x xpa(i+a))
Σ
(WL(W(mB Σ X1, 11, - o) Σ X1,1),
(298)
re(T))++dEa(!)
i=1
Σ
DKL(N((mB - 6) Σ
1). Σ
X 1))
(299)
i=1
(E
82
d
X;)²
82 ( Xz)3
= -T() E
+ Ni())
(300)
2
2
= T d8)52
(301)
By applying Lemma 16 2889
and setting 8
/d we obtain
[x 2
2 [pp [R((]] + [x(
(302)
T
2
8mB
1----11 - dexp(- (d + d2)82)
(303)
expl
2)
d'
m
1-11
VT.
(304)
8
vd+1
Hence, the policy æ incurs a regret O(d (T) in least one of the two bandit instances.
42

---

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

---

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

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
See the details in Appendix A and the codes.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. ec/
gublic/guidess hetiii/ggiidee//eeebbiiiiss
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips cc/ wttppppllllllppieeee http://oooeeuuaassssooooooool1
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See the details in Appendix A and the codes in https://githuu/ com/ -aakoomn-Graph
Zirui EiruiYan/Lineary Causal-
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The theoretical results based average regret. We do not include the variance of regret as metric in this paper; therefore, it not defined and applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
45

---

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 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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
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 compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://nneiipppe Seeeurpss.cppuuli//BBee hcc//ubliic/tthiccccieeelel..lll
Answer: [Yes]
Justification: The research only include the synthetic dataset and hence, do not have potential potential harmfulness.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
46

---

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

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then 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.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We did involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
48

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "NFFltjhcQK", "reviewer": "Reviewer_1kEj", "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}$.\n\nThe 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$. \n\nThe 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.\n\nIt is assumed throughout that interventions do not affect the causal structure: $\\mathrm{Supp}(B)=\\mathrm{Supp}(B^*)$.", "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}$)?\n\nI 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? \n\nIn 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": "Yes, the authors provide some key underlying assumptions. Whether causal sufficiency is assumed should be indicated either way.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The authors identify a novel problem setup in the understudied field of causal bandits with soft interventions and unknown causal structure. Their results are significant to the causal bandit literature and have clear applications for real-world modelling.", "weaknesses": "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.\n\nThe 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. \n\nPutting 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. \n\nThe 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. \n\nThe 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.\n\n[1] Sanghack Lee and Elias Bareinboim, *Structural Causal Bandits: Where to Intervene?*, NeurIPS 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the thoughtful questions, especially those pertinent to the instance-dependant regret and hidden confounders. We provide more discussions and we hope these clarify the reviewer’s technical concerns. \n\n**Dependence on $d$ and $L$:** The reviewer raises a good point about also characterizing instance-dependent regret bounds. This falls into the general dichotomy of class-level versus instance-level regret analysis. We have provided regret bounds for a class of bandits with a maximum in-degree $d$ and maximum causal length $L$. As the reviewer correctly points out, this can be further fine-tuned to recover instance-dependent regret bounds that use the instance-level information $L_N$ and $d^*$. Characterizing these bounds is verbatim similar to our analysis, and we will add a remark in the paper to state these instance-dependant regret bounds. \n\nThe changes in the instance-dependent bounds can be done as follows: \n\n- **The effect of $L$ and $L_N$.** We note that neither Algorithm 1 nor Algorithm 2 requires the information of $L$. Algorithm 1 implicitly learns $L$ by learning the parent sets, which is then fed to Algorithm 2. For the regret bound proof, we use recursion along the longest causal path. Each layer in the causal path contributes a term $cd$ to the regret, the compound effect of all layers along the causal path becomes $(cd)^L$ in the class-level regret. For the instance-dependent regret on the reward node, it is sufficient to perform this process along the causal path on the subgraph that only contains $an(N)$, in which case the regret will depend on $L_N$. This subgraph is learned by Algorithm 1.\n\n- **The effect of $d$ and $d^{\\star}$.** Similar to the previous point, when we evaluate the regret compounding along the causal paths formed by $an(N)$, the maximum in-degree will be $d^*$. Thus, the contribution of each layer to the regret will $cd^*$ instead of $cd$.\n\n- Algorithm 1 requires knowing $d$, and the iterative approach suggested by the reviewer can save some computational cost by applying Lasso estimators only on $an(i)$. But this approach does not tighten the regret since the same amount of observational data $T_2$ is needed to learn any parent sets.\n\n **Parameter $R=(m / \\eta)^2$:** We certainly agree with explicitly incorporating the effect of $R$ on the regret bounds. We agree with the reviewer’s point that introducing this notion of SNR allows for replacing/relaxing Assumptions 3-5 could be restated equivalently as an Assumption on the SNR term $R$.  We further elaborate on the dependence on $R$ in the answer to the next comment.\n\nWe also note our objective has been primarily focused on the fundamental question of how the regret depends on (i) the graph topology and (ii) interventional distribution. Causal bandit literature has been evolving towards removing as many assumptions as possible about graph topology and interventional distribution. This is the first paper that has dropped both under general structures and interventional models (with the remaining piece being extending linear SEMs to non-linear SEMs). However, we certainly agree that it is also important to understand the dependence of regret on other model parameters.\n\n\n**Upper regret bound:** Based on the previous point, the correct instance-dependant regret bound is $\\tilde{\\mathcal{O}}((c d^*)^{L_N - 1/2} \\sqrt{T} + d^{+} + RN)$. The term $RN$ term arises from the step of identifying the ancestor relationship. We note that a similar term appears in related literature [19,22], where the term $R$ is coupled with the degree as they only need to identify $pa(N)$.\n\n**Additional  experiment:** Please refer to the global response where we provide more experiments.\n\n**Hidden confounders:** Thank you for the comment. We note that all our statements are in the context of our specified setting (no hidden confounders). Under this setting (i.e., no hidden confounders and full intervention capability), only $pa(𝑁)$ are optimal. We will re-emphasize this as a remark in the paper to avoid confusion.\n\nWe highlight that having no hidden confounders is a standard assumption in the existing literature on causal bandits (even under more restrictive $do$ interventions).  The primary reason is that causal bandits are not fully understood even when there are no hidden confounders. Nevertheless, we certainly agree that understanding the effect of unobservable confounders is also important. Including hidden confounders will introduce non-trivial challenges. For instance, it brings in bi-direction edges, as a result of which one cannot express the reward as a linear function of observable variables. \n \n**Causal sufficiency:** We thank the reviewer for this question. Yes, our approach does assume causal sufficiency, and we will include this in Assumption 4.\n\n **first case in equation (9):** Thanks for the sharp observation. Yes, based on Assumption 5, indeed the condition part \"if $\\text { if } i<N \\text { and }|\\widehat{\\operatorname{de}}(i)|>0$ Is a typo and should be removed. \n\n**$K$ in table 1:** Yes, $K$ represents the number of possible $do$ interventions on one node. We will add a comment to specify it.\n\n**Final note about “soundness”:** We hope we have addressed the reviewer’s concerns about “soundness” (rate 2: fair) – especially about having hidden confounders and class-level versus instance-level regret (which can be readily recovered from our result). We remark that this paper significantly extends the scope of the causal bandit literature by entirely removing the assumption about knowing the graph topology (a common assumption by extensive recent publications in JMLR, NeurIPS, ICML, and AISTATS). This is a major leap in causal bandits, and kindly request that the reviewer consider re-evaluating their rating of the manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "blLMDkmbyp", "reviewer": "Reviewer_zJSz", "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.", "questions": "What does assuming that B_i and B_i^* have the same support buy you?\n\nIs the Lasso calibrated for the max number of parents?\n\nThe bound you have on kappa in (27) is very big, O(m^2). Doesn’t this make Theorem 1, part 2 trivial?\n\nIs 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?\n\nWhat is c, or at least what does it depend on?\n\nWhy use ridge regression for estimating B, B*? They are assumed sparse, after all. \n\nWhy 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?\n\nCan you provide some intuition for what the lower bound construction looks like?", "limitations": "No limitations discussed in the main body.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The problem formulation is natural and seems to be “the right size;” it’s added generality compared to the previous state of the art is enough to be interested but still allow for a solvable problem. The presentation is generally clear and polished.", "weaknesses": "There are some technical concerns; please see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Support of weights matrices:** We clarify that $B_i$ and $B_i^*$ always have the same support under soft interventions. as such interventions only change the conditional distribution of node $i$ without affecting the topology. The causal topology remains intact, leading to $B_i$ and $B_i^*$ having the same support. As a side note, we also remark that under more restrictive types of interventions ($do$ and hard), an intervention on node $i$ removes its causal dependence on its parents, i.e., $pa(i)$. In such cases, the support of $B_i^*$ becomes a subset of $B_i$. However, even in such cases when the topology is unknown, assuming that the support of $B_i^*$ is a subset of $B_i$ does not provide any gain. Overall, since we are assuming soft interventions, $B_i$ and $B_i^*$ have the same support.\n\n**Lasso calibrated for the max number of parents:** Yes, the algorithm is designed for the entire class of causal models with maximum in-degree bound $d$. If more node-level information is available, the Lasso regression can be accordingly modified. We remark that the interest of the community working on causal bandits has been towards removing as much as possible assumptions about the graph structure and interventions. Our setting is in line with extending the state of the art by removing topology information.\n\n**Loose bounds on kappa:** We thank the reviewer for the sharp observation. The reviewer is right that this is not a tight bound. Nevertheless, we note that for achieving a tight regret, such a loose bound is inevitable, and further improving it compromises the regret. Here’s the reason: the regret is only a function of the topology information, and the topology should be learned only to the extent that it facilitates identifying the best intervention. In other words, learning the topology up to some level improves regret and, after that, starts compromising it since learning the topology requires collecting more samples, which implies less sample efficiency. Therefore, any algorithm that learns the topology accurately is over-learning, and our conjecture is that it will compromise the regret. Please note that the purpose of Theorem 1 is to provide the guarantees needed only for characterizing the regret, and it is not intended to claim that the topology is learned accurately. \n\n**Necessity of Assumption 5:** As the reviewer points out, this assumption is needed for graph recovery, and it is standard when graph skeletons is unknown [19,22,R1]. When a node acts as a confounder, intervening on that node might not impact certain intermediary nodes but still influences reward. Without Assumption 5, the confounder relationships cannot be identified, leading to an incorrect graph topology recovery. The reviewer’s point is correct: the interventions on some nodes might have minimal effect on the reward. However, when the topology is unknown, these nodes need to be identified and treated properly. The reason is that even a minimal effect on the regret can still accumulate linear regret if it is chosen linearly in $T$. So the algorithm needs to also properly identify these nodes to ensure they are selected sublinearly.\n\n[R1]: Elahi et. al. Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits, ICML 2024 Workshop RLControl Theory.\n\n**Definition of $c$:** Thanks for the sharp observation. This constant is $c=\\kappa$ with $\\kappa$ is defined in (27). We recognize this notation is redundant and will change it to $\\kappa$. \n\n**The weights matrices are assumed sparse:** Thank you for this question. We are not assuming sparsity for $B$ and $B^*$. The maximum in-degree $d$ can be arbitrarily large, i.e., it can be as large as  $N−1$ . This means the columns of $B$ and $B^*$ are $d$-sparse, where $d$ can be $N−1$. Nevertheless, the reviewer is correct that if we limit the scope of the problem to assume that $B$ and $B^*$ are sparse, then sparse-recovery methods can be more effective than ridge regression. \n\n**Continuous relaxation for optimization** We recognize that the reviewer might have an interesting point about solving a bandit combinatorial problem via continuous relaxation. We are unaware of such relaxation in the bandit literature. One challenge in adopting such an approach is that the utility to be optimized (i.e., UCB) does not take values at non-discrete values. Specifically, $UCB_{a}$ is not defined for $a_i\\notin\\{0,1\\}$. As such, while we appreciate the reviewers' thoughts, we do not see an immediate way of using continuous relaxation in combinatorial bandit decisions.\n\n**Lower bound construction:** In this paper, we provide a minimax lower bound. This is done by constructing two bandit instances that are highly similar, and distinguishing them is difficult. Specifically, we construct two bandit instances that share the same hierarchical graph structure. These instances differ only in the parameters that switch the observational and interventional weights for the nodes with causal depth of 1, resulting in distinct optimal interventions. We identify the minimum samples that any algorithm will need to distinguish between the two bandit instances and the minimum regret it will incur on one of the instances. This serves as a lower bound on the minimax regret.\n\n**Final note about “soundness”:** We hope we have addressed the reviewer’s concerns about “soundness” (rate 2: fair) – especially why  $B_i$ and $B_i^{\\star}$ have the same support, why the second part of Theorem 1 is sufficient for our regret minimization purposes, lack of sparsity in $B$ and $B^{\\star}$, and continuous relaxation. We remark that this paper significantly extends the scope of the causal bandit literature by entirely removing the assumption about knowing the graph topology (a common assumption by extensive recent publications in JMLR, NeurIPS, ICML, and AISTATS). This is a major leap in causal bandits, and kindly request that the reviewer consider re-evaluating their rating of the manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A0brEv8bI8", "reviewer": "Reviewer_2rLb", "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.\nTo 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.", "questions": "Can you provide a discussion for the above points?\n\n1- 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?\n\n2- 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": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1- The paper considers a novel setting where the causal graph in unknown and SEM is linear.\n\n2- The flow of the paper is clear, and each part of the proposed algorithm is thoroughly discussed.\n\n3- The upper bound of GA-LCB-ID, when the graph is known, demonstrates an improvement compared to related work. Also, it is closed to the minimax lower bound.\n\n4-  GA-LCB-ID, in the main case when the causal graph is unknown, achieves a reasonable upper bound.\n\n5- The related work is comprehensively discussed in the introduction.", "weaknesses": "1- The algorithm assumes that the causal graph does not contain latent variables.\n\n2- The algorithm requires access to identifiability parameters, which is an unrealistic assumption.\n\n3- The set of interventions is limited, for each node, we only have one soft intervention.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** The algorithm assumes that the causal graph does not contain latent variables. The algorithm requires access to identifiability parameters, which is an unrealistic assumption.\n\n**Response:** We thank the reviewer for the thoughtful comment.  In principle, we agree with the reviewer about the importance of relaxing these assumptions. However, we note that these are standard assumptions in the current causal bandit literature (e.g.,  [14,17,19,22]). The primary reason is that causal bandits are not fully understood even under such assumptions. Causal bandit literature has been evolving towards removing as many assumptions as possible about graph topology and interventional distribution. This is the first paper that has dropped both under general structures and interventional models (with the remaining piece being extending linear SEMs to non-linear SEMs). However, we certainly agree that next, it is also important to dispense with assumptions on latent variables and identifiable parameters. \n\n**Comment:** The set of interventions is limited, for each node, we only have one soft intervention.\n\n**Response:** Thanks for the note. For presentation clarity, we have focused on the binary intervention model. However, the algorithms can be readily extended beyond binary interventions where we can show that the regret will scale as $\\sqrt{KT}$ when $K$ is the number of interventions per node. In the final version we can use the additional one page to provide a brief discussion on the extension to $K$ interventions per node. Importantly, we note that expanding the intervention space will not impose additional costs for identifying the causal structure, as one soft intervention is sufficient. We also note that under $do$ intervention, the regret scales with $\\sqrt{KT}$ where $K$ is the number of possible $do$ interventions. This means that under a significantly more relaxed intervention model, we can achieve the same regret that $do$ interventions achieve. \n\nQuestions:\n\n**Comment:** 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?\n\n**Response:** We thank the reviewer for this question. If we define $R=(m / \\eta)^2$ and incorporate it into the regret, the term $N$ in the regret order will appear as $RN$. We will include this in the updated version. The $RN$ term arises from the step of identifying the ancestor relationship. Notably, a similar term is observed in related literature [19,22], where the term $R$ is coupled with the degree as they only need to identify $pa(N)$. Besides, in previous work, $K$ represents the number of distinct interventions, and we will have similar behavior when generalized to multiple soft interventions.\n\n**Comment:** 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.\n\n**Response**: We thank the reviewer for the sharp observation. Having the expectation is a typo, and we will remove it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers about the comments about our assumptions and empirical evaluations. We would like to clarify the following:

**Theoretical contributions:**  We remark that 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 have provided more details on these. We are glad that the reviewers have not pointed to any technical flaws in the analysis. We believe this paper provides a  major contribution in the trajectory of development in causal bandits, which has been moving away from stylized assumptions. We certainly agree that there are still important issues to address (e.g., hidden confounders) that remain for future work. 

**Additional empirical evaluations:** With the additional results, overall we have provided evaluations to assess the key theoretical findings of the paper. These include: 
Scaling behavior with respect to the three key parameters in the results, i.e., $d, L$. 
Sublinear regret and fast convergence.
Computational advantage, which is a bottleneck for almost all the existing approaches to causal bandits with even stronger assumptions. 

We remark that due to computational challenges, causal bandit algorithms are generally focused on small graph sizes. Additionally, the hierarchical graph is the one that can mimic the worst-case regret for algorithms with given parameters. The hierarchical graphical models that we are evaluating have $L=9$ layers and $N=19$ nodes, which is the largest model considered in the literature (for instance the JMLR paper [14], the AISTATS paper [17], and the JSAIT paper [24] consider hierarchical with no more than 3 layers; JMLR [14] and JSAIT [24] also consider simpler graph with at most $N=10$ nodes; and [22], which focuses on $do$ intervention with unknown graph, provides experiments for a simple binary tree with $N = 20$ nodes.)

**Scaling with $L$:** Scaling of the regret with respect to the causal depth $L$ is depicted in Figure 1 in the attached document for setting of a hierarchical graph with $d=2$ and $L$ varies in the range $1$ to $9$. The theoretical results (regret upper and lower bounds) predict that the regret grows at the range $(2c)^L$ (i.e., exponential in $L$). The empirical results in Figure 1 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 2 in the attached document based on a hierarchical graph with $L=2$. We note that we increase the number of sufficient exploration parameters $T_1$ and $T_2$ to ensure the results for all the degrees. Theoretical predictions suggest that our algorithm’s regret scales as $d^{3/2}$ (i.e., polynomial growth in $d$). For the choice of $L$, the lower bound becomes linear in $L$. Figure 2 demonstrates that our regret is super-linear and tracks the polynomial trend of the regret upper bound (i.e., our achievable regret). 

**Sublinear regret:** Figure 3 of the attached document shows the cumulative regret for a larger graph with $L=6$ and $d=2$. In this scenario, both GA-LCB with and without graph information exhibit sublinear regret. However, the GA-LCB with unknown graph information incurs higher cumulative regret due to the need for additional exploration required for estimating the topology.

**Computational cost:** As discussed in Section 3.3, a key contribution of our algorithm is its significant computational advantage compared to the existing causal bandit algorithms (which also rely on stronger assumptions). First, our algorithm circumvents the computational complexity of computing the upper confidence bounds (which generally requires solving an optimization problem) by iteratively computing the value through the causal depth. To highlight the advantage, we note that the UCB-based causal bandit algorithms are computationally viable for only $L\leq 2$ or for special graphs such as chain graphs [24]. In contrast, the computational complexity of our algorithm scales linearly with $L$ (especially scales as with $\mathcal{O}(Ld^3)$). This has allowed us to easily implement algorithms for causal paths as long as $L=9$. Additionally, our algorithm includes a phase elimination step that removes sub-optimal arms from the potential best intervention set. Since we need to calculate UCBs for each possible intervention, the phase elimination step prevents unnecessary UCB computation. This results in significant computational savings as the time horizon increases.
We have also provided more empirical analysis of the computational complexity in Appendix A. Figure 4 (Appendix A) illustrates the computational differences between various algorithms. It is evident that our algorithm significantly reduces computation time, even for small graphs. In contrast, the other algorithm is not scalable with respect to both degree $d$ and length $L$.

Meta-review: 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.
Decision: Accept (poster)