Linear Causal Bandits: Unknown Graph and Soft Interventions

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.

Paper

References (39)

Scroll for more · 27 remaining

Similar papers

Peer review

Reviewer 2rLb6/10 · confidence 3/52024-07-11

Summary

The paper considered a specific setting in the causal bandits problem where 1) the graph is unknown, 2) the causal model is linear , and 3) the action set consists of $2^{N}$ soft interventions. To tackle the problem, the author proposed an algorithm that first learns the causal structure and then uses UCB-based approaches to find the best action and minimize the regret. The regret of the algorithm is analyzed for both cases: with and without the knowledge of the graph.

Strengths

1- The paper considers a novel setting where the causal graph in unknown and SEM is linear. 2- The flow of the paper is clear, and each part of the proposed algorithm is thoroughly discussed. 3- 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. 4-  GA-LCB-ID, in the main case when the causal graph is unknown, achieves a reasonable upper bound. 5- The related work is comprehensively discussed in the introduction.

Weaknesses

1- The algorithm assumes that the causal graph does not contain latent variables. 2- The algorithm requires access to identifiability parameters, which is an unrealistic assumption. 3- The set of interventions is limited, for each node, we only have one soft intervention.

Questions

Can you provide a discussion for the above points? 1- I expected in the regret bound, the identifiability parameter would take part similar to previous work in an unknown setting. What is the intuition behind excluding it in this setting? 2- I didn’t understand why you took an expectation in Theorem 2. The theorem should show that with high probability, the regret is less than a certain bound. Why is it necessary to take an expectation? Note that you defined regret with implicit expectation over the randomness of rewards in Equation 5.

Rating

6

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes.

Authorsrebuttal2024-08-09

We thank the reviewer for this comparison question. A chain graph is a **special** simple graph with a maximum in-degree of $d=1$ and a maximum causal depth of $L=N-1$. **Regret Comparison:** For UCB-based algorithms in the classic bandit setting **without knowing** the graph, the regret scales as $\tilde{\mathcal{O}}(\sqrt{|\mathcal{A}| T}) = \tilde{\mathcal{O}}(\sqrt{2^N T})$. In contrast when the the graph is known, the regret reduces **significantly** and it scales as $\tilde{\mathcal{O}}(\sqrt{T})$ (e.g. Corollary 1). The reason for the higher regret of the UCB-based algorithm without knowing the graph is that due to the lack of graph structure, the algorithm treats each set of interventions as an independent arm. This means that there are $2^N$ possible intervention sets, leading to the regret mentioned above. **Computational Cost:** Here we compare the computational cost of three algorithms: UCB-1 (a UCB-based algorithm for the classic bandit problem), LinSEM-UCB [14] (a UCB-based algorithm for causal bandits), and our proposed algorithm. The UCB-1 algorithm incurs a computational cost of $\mathcal{O}(2^N)$ because it needs to select the best intervention from $\mathcal{A}$ with $|\mathcal{A}|=2^N$. The LinSEM-UCB algorithm, designed for causal bandits, has a computational cost of $\mathcal{O}(N \cdot 2^{2N})$, as each UCB iteration requires maximization over the vertices of an $N$-dimensional hypercube, with each vertex having a computational cost of $\mathcal{O}(N)$. Additionally, it selects the best intervention from $\mathcal{A}$. In contrast, our algorithm has a computational cost of $\mathcal{O}(N |\mathcal{A}_s|)$, where $\mathcal{A}_s$ represents the set of possible optimal interventions at time $t$ after elimination, with $|\mathcal{A}_s| \leq 2^N$ and $|\mathcal{A}_s| \rightarrow 1$ as $t \rightarrow \infty$. This is because the computational cost of the confidence width calculation in equation (19) is $\mathcal{O}(1)$ (recall that $d=1$), and the UCB only requires the estimated mean value (of order $\mathcal{O}(N)$) and $N$ confidence widths. Consequently, our algorithm has a slightly higher computational cost at the beginning but becomes more efficient as $|\mathcal{A}_s|$ decreases to $\frac{2^N}{N}$, which can be achieved in a few elimination steps. Overall, our approach achieves a substantial reduction in regret while maintaining a comparable computational cost to UCB-1 in the context of this simple graph. Finally, we emphasize that as the graph topology becomes more complex, the UCB-based algorithms further degrade. For example, in hierarchical graphs, the intervention set size is $2^{dL+1}$, leading to a regret of $\tilde{\mathcal{O}}(\sqrt{2^{dL+1} T})$, compared to our algorithm’s $\tilde{\mathcal{O}}(\sqrt{d^{L-\frac{1}{2}} T})$.

Reviewer 2rLb2024-08-09

Sorry, it seems you misunderstood my example. My example was a chain graph where all variables also are parents of Xn (reward node). So, the graph has $2(n-1)$ edges (if I'm not wrong, $d = N -1$ and $L = N-1$)

Authorsrebuttal2024-08-10

Thank you for the clarification. To lay some context for discussion, we would like to address this in the dichotomy of instance-dependent versus class-level regret analysis. The former analyzes the performance of a policy on a specific bandit instance while the latter captures the performance over a class of instances. In this context, for any causal bandit algorithm (including ours), one can discuss - Instance-dependent regret analysis, which involves analyzing a policy for a specific causal bandit instance (e.g., with a specific graph topology). - Class-level analysis, which involves analyzing a policy designed for a class of causal bandits (e.g., causal bandits with maximum degree $d$ and causal depth $L$, which is standard in causal bandit literature). Given this context, we address the regret of the example proposed by the reviewer in both settings: **Class-level regret for the class of graphs with maximum in-degree $d$ and causal depth $L$:** The UCB-1 algorithm can have a class-level regret that scales as $\tilde{\mathcal{O}} \big(2^{\frac{d^L}{2}} \sqrt{T}\big)$ (e.g., in the reverse tree graph). On the other hand, our class-regret scales as $\tilde{\mathcal{O}}\Big( d^{L - \frac{1}{2}} \sqrt{T}\Big)$. **Instance-dependent regret for the chain graph:** As the UCB-1 algorithm does not take the causal structure into account, its regret remains as $\tilde{\mathcal{O}}(2^{N/2} \sqrt{T})$. On the other hand, we can readily analyze the instance-dependent regret of our algorithm, which scales as $(N-1)\sqrt{T}$. To get the instance-level regret of our algorithm, let's examine the source of the $d^{L-1/2}$ term in our regret:. if we define the maximum in-degree at each causal depth as $d_{(\ell)} = \max_{i\in [N], L_i=\ell} d_i$ for $\ell \in [L]$, then the $d^{L-1/2}$ term can be refined to the instance-dependent term $\sqrt{d} \prod_{\ell=1}^{N-1} d_{(\ell)}$ (in the proofs we need to replace $d$ with $d_{(\ell)}$). In the term $\sqrt{d} \prod_{\ell=1}^{N-1} d_{(\ell)}$, $\sqrt{d}$ reflects the complexity of the linear function, and the product accounts for the compounding effect where each causal depth contributes to $d_{(\ell)}$.

Reviewer 2rLb2024-08-11

Thanks for your response. based on the current result, the upper bound is $\mathcal{O} \left ( (N -1) ^{(N-3/2)}\sqrt{T} \right)$? If so, it seems that, compared to the classic UCB for this instance, the regret bound is not particularly advantageous. It may be beneficial to discuss the improved instance-dependent regret, as you mentioned, in the revised version. I intend to maintain my current score; however, I have concerns regarding soft interventions. In the title, abstract, and introduction, the authors claim to propose an algorithm for soft intervention cases. However, in the problem formulation, they define only a single soft intervention per node, which was unexpected.

Authorsrebuttal2024-08-11

As the reviewer points to, we have consistently mentioned that we focus on soft interventions. This is the most general form of intervention and subsumes hard and $do$ interventions. If the reviewer is asking about one versus multiple interventions per node, we re-emphasize that using one is standard in the causal bandit literature for notational simplicity. Extensions from one to multiple interventions is trivial. A constant 2 will be replaced by $K$ (number of interventions) in cardinality of the intervention space. We kindly ask the review to base their judgment on the theoretical contribution of this paper: this paper significantly extends the scope of the causal bandit literature by entirely removing the assumption about knowing the graph topology and general soft interventions. All our other assumptions are either in line with or more relaxed compared to those in the existing literature. We are glad that the reviewers have not pointed to any technical flaws in the analysis.

Reviewer 2rLb2024-08-11

Just for clarification regarding soft interventions. I expected that you define it in the following way. By soft intervention on node $i$, we can change any entries of $B_i$ to any values (with some restriction). But in your setting, by soft intervention, we can only change $B_i$ to $B^*_i$. Could you discuss the complexity of the former setting? Is it not learnable? I understand the theoretical contribution of the paper, and my judgment is based on that.

Authorsrebuttal2024-08-11

Thanks for giving us a chance to clarify this. Please note $B_i$ is *not* the interventional value of the random variable $X_i$ generated by node $i$. Rather, it specifies the mechanism for generating it. **Post-interventional random variables:** Specifically, upon intervening on node $i$, the random variable $X_i$ can take any arbitrary real value. Its value is not limited to only one or finite number of choices. Specifically, by applying a soft intervention on node $i$, we are changing its conditional distribution $\mathbb{P}(X_i \ | \ X_{{\sf pa}(i)})$ to a distinct conditional distribution. The post-intervention random variable $X_i$ will be generated according to the post-intervention conditional distribution. This is in contrast to $do$ interventions that specify a choice for $X_i$ (which essentially means placing the entire post-interventional conditional probability on a singular value). **Post-interventional SEMs:** Since we are working with linear SEMs, both pre- and post-interventional conditional distributions are fully specified by matrices $B$ and $B^*$ as well as the exogenous noise model. We are assuming that all these (i.e., $B$, $B^*$, and noise distribution) are fully *unknown*. This means that the pre- and post-interventional distributions are fully *unknown*. Our algorithm is learning all these, which includes learning $B$ and $B^*$ (their support and their real-valued entries). The complexity of learning all $2N$ such vectors $\{B_i,B^*_i:i\in[N]\} $is already included in the regret. We have considered one post-intervention SEM $B^*$. This can be readily extended to any finite number of post-intervention SEMs. Extensions to an infinite number of post-intervention models can be a potential extension. That necessitates learning an *infinite* number of interventional distributions, which to the best of our knowledge even for simpler settings (e.g., knowing the topology or even interventional distributions) is an open question. So, if we are understanding the reviewer’s concern correctly, having one single post-intervention $B_i^*$ does *not* mean that we are forcing $X_i$ to take only one value. Rather, we are changing the conditional distribution that generates $X_i$ and it still can take a real value generated by the interventional distribution (and this is a generalization of $do$ interventions that specify the $X_i$ to take a specific deterministic value – which in the context of causal bandits has a finite number of possibilities).

Reviewer 2rLb2024-08-11

Thanks for your reply. I understood the answer to my question in the following sentence: "Extensions to an infinite number of post-intervention models can be a potential extension. That necessitates learning an infinite number of interventional distributions, which to the best of our knowledge even for simpler settings (e.g., knowing the topology or even interventional distributions) is an open question.", Thanks for your clarification.

Reviewer zJSz4/10 · confidence 4/52024-07-12

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.

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.

Questions

What does assuming that B_i and B_i^* have the same support buy you? Is the Lasso calibrated for the max number of parents? The bound you have on kappa in (27) is very big, O(m^2). Doesn’t this make Theorem 1, part 2 trivial? Is assumption 5 necessary? Why can’t you argue that soft interventions that would break assumption 5 would have a minimal effect on the expected loss and therefore only contribute a small amount to the regret? One might even be able to have a bound that is adaptive to eta. Or do you need it for graph discovery? What is c, or at least what does it depend on? Why use ridge regression for estimating B, B*? They are assumed sparse, after all. Why do you need to solve an optimization problem over 2^|A|? Won’t the solution be on a corner of the |A|-dimensional hypercube, so a continuous relaxation would suffice? Can you provide some intuition for what the lower bound construction looks like?

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

No limitations discussed in the main body.

Reviewer 1kEj7/10 · confidence 4/52024-07-14

Summary

The authors consider a stationary causal bandit problem for an unknown linear model with weight matrix $B \in \mathbb{R}^{N \times N}$ and noise vector $\epsilon \in \mathbb{R}^N$. In their setup, intervention on the node $X_i$ replaces all of the weights into $X_i$ with those from another unknown matrix $B^* \in \mathbb{R}^{N \times N}$. The authors propose a two-phase approach: learning the causal structure by (1a) learning a valid topological ordering (1b) learning the causal DAG, and then (2) applying a phase elimination algorithm to learn the best pulls over a time horizon $T$. The authors also include a minimax lower bound for their problem setup. For either bound, the authors argue that the maximum causal depth $L$ and a known upper bound (denoted here as $d^+$ for clarity) for the maximum in-degree $d$ are the relevant topological parameters. It is assumed throughout that interventions do not affect the causal structure: $\mathrm{Supp}(B)=\mathrm{Supp}(B^*)$.

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. The authors also seem to ignore the parameter $R := (m/\eta)^2$ in their regret bounds. While it is not a topological property of the population DAG, it is certainly an important parameter in the problem setting and could be thought of as a kind of guaranteed minimal signal-to-noise ratio (SNR). From the definition of $T_1$ there should be a linear scaling of the regret bounds with $R$, up to a poly-log factor. This SNR is important for real-world modelling and could also offer insights into relaxing assumptions 3, 4 and/or 5. Putting the above together, my estimation of the same upper regret bound is $\tilde{O}((cd^*)^{L_N - 1/2} \sqrt{T} + R + d^+ + N)$. Please correct me otherwise and/or update the manuscript. I will revise my score and evaluation of the paper's soundness following the authors' rebuttal. The authors provide a very minimal experiment, relegated to the appendix. It would have been informative to see parameter sweeps and experiments with random DAGs to compare their bounds with empirical scalings. The authors should make no mention of the possibility of hidden confounders and whether their models can incorporate this. In particular, the claim that only $\mathrm{pa}(N)$ are possibly optimal with hard interventions is false - see [1] for details. [1] Sanghack Lee and Elias Bareinboim, *Structural Causal Bandits: Where to Intervene?*, NeurIPS 2018.

Questions

Does your approach assume causal sufficiency? In particular, are noise terms assumed to be mutually independent (i.e., $\mathrm{Corr}(\epsilon_i, \epsilon_j) = \delta_{ij}$)? I do not understand the first case in for the estimator for the ancestors of $i$ in equation (9): it appears to read "if $i$ is not the reward node but has decedents then it can't have any ancestors". Is this a typo? In table 1, the meaning of $K$ in the benchmark approaches should be indicated. Is this the number of possible hard interventions on a node for categorical data or something else?

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

4

Limitations

Yes, the authors provide some key underlying assumptions. Whether causal sufficiency is assumed should be indicated either way.

Reviewer 2rLb2024-08-09

Thanks for your response. I also have another question. How do you compare your algorithm and Corollary 1 with the Naive approaches (e.g., the ucb-based algorithm in classic bandit) on a specific graph like the following graph. X1 -> X2 -> .... -> Xn. Also for all $i$, Xi is the parent of Xn. It's a chain graph where all variables are parent of Xn.

Reviewer zJSz2024-08-09

Thanks for the detailed response, and I think many of my concerns are answered, concerning theorem 1. On a related note, how does the regret bound scale with m?

Authorsrebuttal2024-08-10

**Scale with $m$:** We appreciate the reviewer for raising this important question. The regret bounds scale linearly in $m$. An intuitive reason is that if we multiply all the random variables of the system by a constant $M$ then the final reward will be scaled up with $M$ and the regret of any algorithm scales up with a constant $M$. As discussed at the end of Section 2, the dependence of the regret on $m$ is linear even in simpler linear bandit problems (e.g., [25]). An exact same linear dependence has been also reported in other causal bandit settings [14,17]. We note that in some literature such dependence might not appear explicitly since they normalize the range of the random variables or rewards to fall in the range [0,1], i.e., by setting $m=1$ (e.g., causal bandit with $do$ intervention [1,6] and linear bandits [R2]). [R2]: Abbasi-Yadkori et. al. ​​Improved algorithms for linear stochastic bandits, NeurIPS 2011 **Other concerns:** We are glad that the reviewer’s concerns about Theorem 1 are addressed. We will be happy to also elaborate more on other concerns if there are still remaining ones.

Reviewer zJSz2024-08-12

Thanks for the response

Thanks, I agree that a linear scaling with m is not avoidable. I had a suspicion that it could have super-linear scaling, as the probability of error bounds degrade in m so I would expect some sample complexity terms to at least pick up a log(m) to compensate.

Authorsrebuttal2024-08-12

Again, we thank the reviewer for the thoughtful point. We'll add a comment to the revised manuscript to emphasize linearity in $m$. We'll be also happy to address any remaining concerns. Based on the discussions, we'd be grateful if the reviewer considers re-evaluating their rating of the paper.

Reviewer 1kEj2024-08-12

Many thanks to the authors for their thoughtful and detailed responses, which have addressed my major concerns and questions. In light of this, I will upgrade my overall rating to a 7: Accept, and my soundness rating to a 3: Good. My high overall score is based off the significance and novelty of the authors' contribution. I suspect correlated noise variables (i.e., latent confounders) could be incorporated into the authors' analysis, which presents one exciting avenue for future work.

Authorsrebuttal2024-08-12

We are grateful to the reviewer for the great suggestion. Indeed -- we agree that modeling the latent confounders via modifying the noise model is an effective of integrating them into the causal bandit model. We certainly agree that is an important next line of research in the causal bandit literature.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC