Linear Causal Bandits: Unknown Graph and Soft Interventions

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.

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.

Comment: The set of interventions is limited, for each node, we only have one soft intervention.

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.

Questions:

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?

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.

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.

Response: We thank the reviewer for the sharp observation. Having the expectation is a typo, and we will remove it.

We thank the reviewer for this comparison question. A chain graph is a special simple graph with a maximum in-degree of $d=1$ and a maximum causal depth of $L=N-1$.

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

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

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

Finally, we emphasize that as the graph topology becomes more complex, the UCB-based algorithms further degrade. For example, in hierarchical graphs, the intervention set size is $2^{dL+1}$, leading to a regret of $\tilde{\mathcal{O}}(\sqrt{2^{dL+1} T})$, compared to our algorithm’s $\tilde{\mathcal{O}}(\sqrt{d^{L-\frac{1}{2}} T})$.

Thanks for your response. 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.

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.

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.

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.

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.

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.

[R1]: Elahi et. al. Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits, ICML 2024 Workshop RLControl Theory.

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

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.

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.

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.

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.

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.

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.

The changes in the instance-dependent bounds can be done as follows:

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

• 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$.

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

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.

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

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)$.

Additional experiment: Please refer to the global response where we provide more experiments.

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.

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

Causal sufficiency: We thank the reviewer for this question. Yes, our approach does assume causal sufficiency, and we will include this in Assumption 4.

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.

$K$ in table 1: Yes, $K$ represents the number of possible $do$ interventions on one node. We will add a comment to specify it.

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.