1 Introduction↩︎

[1] introduced a class of problems termed causal bandit problems, where actions are interventions on a causal model, and rewards are samples of a chosen reward variable \(Y\) belonging to the causal model. They focus on hard interventions, where the intervened variables are set to specific values, without considering the values of any other variables. We will refer to this as a hard-intervention causal bandit problem. They propose a best-arm identification algorithm that utilizes observations of the non-intervened variables in the causal model to accelerate learning of the best arm as compared to standard multi-armed bandit (MAB) algorithms. Causal bandits have applications across a broad range of domains, particularly in scenarios requiring the selection of an intervention on a causal system. These include computational advertising and context recommendation [2], [3], biochemical and gene interaction networks [4], [5], epidemiology [6], and drug discovery [7]. Most of the work in causal bandits (see 7) focuses on developing MAB algorithms which incorporate knowledge about the causal graph. [8], in contrast, use the fact that the causal graph is known not to develop yet another MAB algorithm, but to reduce the set of nodes (i.e. variables) of the causal graph on which hard interventions should be examined, thereby reducing the search space for hard-intervention causal bandit problems. This reduction of the search space significantly improves and scales the applicability of existing causal MAB algorithms.

It is recognized in the MAB literature that, for many if not most applications, actions are taken in a context, that is, with available information [9]–[13]. E.g., content recommendation based on the user’s demographic characteristics, such as age, gender, nationality and occupation. Similarly, in causality, conditional interventions — where a variable \(X\) is set to a value \(g(\mathbf{Z_{X}})\) through some function \(g\) after observing a set of variables (a context) \(\mathbf{Z}_{X}\) — are more realistic than hard or softinterventions in many real-world scenarios. Conditional interventions were first introduced in [14] based on the argument that “In general, interventions may involve complex policies in which a variable \(X\) is made to respond in a specified way to some set \(\mathbf{Z}_{X}\) of other variables.” [15] motivate their interest in conditional interventions by providing the concrete example of a doctor selecting treatments based on observed symptoms and medical test results \(\mathbf{Z}_{X}\) to improve the patient’s health condition. The doctor performs interventions of the form \(\mathit{do}(X_{i}=x_{i})\), but “the specific values of the treatment variables are not known in advance, but instead depend on symptoms and test results performed ‘on the fly’ via policy functions \(g_{i}\)” [15]. Formally, this is denoted \(\mathit{do}(X_{i} = g(Z_{X_{i}}))\). See the paragraph on conditional interventions in 2 for further motivation and details about \(\mathbf{Z}_{X}\)

Novelty and contributions: This work, like that of [8], leverages the causal graph to reduce the search space of the MAB problem, thereby accelerating MAB algorithms applied to it and effectively serving as a pre-processing step for (causal) MAB problems. While [8] study causal bandits with multi-node hard interventions in the presence of latent confounders, we focus on single-node conditional interventions under the assumption of no latent confounders.

As discussed in 2, restricting to single-node interventions in fact makes the problem more challenging (relative to the no-confounder multi-node case). Furthermore, we consider conditional rather than hard interventions.

Therefore, our work addresses a fundamentally different and non-comparable problem from that of [8]. Because the single-node intervention problem without latent confounders is already highly non-trivial, we leave latent confounders to future work, making our study a necessary step toward the general case. The setting we study remains widely applicable — for instance, to the examples discussed in 2. Explicitly, our work is novel because we consider the case where (i) the arms are conditional interventions (which generalize both hard and soft interventions); and (ii) the interventions are single-node interventions. This is the first time the minimal search space for a causal bandits problem with non-hard interventions is fully characterized. Such a characterization has also not been done for single-node interventions (of any kind). Our contributions are as follows: (a) we establish a graphical characterization of the minimal set of nodes guaranteed to contain the optimal node on which to perform a conditional intervention (called the minimal globally interventionally superior set (mGISS)); and (b) we propose an algorithm which finds this set, given only the causal graph, with a time complexity of \(O(\lvert \mathbf{V} \rvert + \lvert E \rvert)\), that is, linear in the number of nodes and edges of the causal graph. As a supplementary result, we also show that, perhaps surprisingly, the exact same minimal set would hold for the optimization problem of selecting an atomic (i.e. single-node and hard) intervention in a deterministic causal model. We provide proofs for the graphical characterization and correctness of the algorithm, as well as experiments that assess the fraction of the search space that can be expected to be pruned using our method, in both randomly generated and real-world graphs, and demonstrate, using well-known real-world models, that our intervention selection can significantly improve a classical MAB algorithm.

Note that, if the true causal graph is unknown and instead a family of candidate graphs is available, the C4 algorithm can simply be applied to each candidate graph, and the results combined by taking the union of the resulting minimal search spaces. All proofs of the results presented in the paper can be found in the appendix. The code repository with the experiments can be found at https://github.com/francisco-simoes/minimal-set-conditional-intervention-bandits.

2 Preliminaries↩︎

Graphs and causal models We will make use of Directed Acyclic Graphs (DAGs). The main concepts of DAGs and notation used in this paper are reviewed in 9. Furthermore, we operate within the Pearlian graphical framework of causality, where causal systems are modeled using Structural Causal Models (SCMs) [16], [17]. An SCM \(\mathop{\mathrm{\mathfrak{C}}}\) is a tuple \((\mathbf{V},\mathbf{N},\mathcal{F},p_{\mathbf{N}})\), where \(\mathbf{V}=(V_{1}, \ldots, V_{n})\) and \(\mathbf{N} = (N_{V_{1}}, \ldots, N_{V_{n}})\) are vectors of random variables. The exogenous variables are jointly independent, and are distributed according to the noise distribution \(p_{\mathbf{N}}\), while each endogenous variable \(V_{i}\) is a deterministic function \(f_{V_{i}}\) of its noise variable \(N_{V_{i}}\) and a (possibly empty) set of other endogenous variables \(\mathrm{Pa}(V_{i})\), called the parents of \(V_{i}\). The \(V_{i}\) and \(N_{V_{i}}\) are called endogenous and exogenous (or noise) variables, respectively. \(R_{V}\) denotes the range of the random variable \(V\). \(\mathcal{F}\) is a set of functions \(f_{V_{i}}\colon R_{\mathrm{Pa}(V_{i})}\times R_{N_{V_{i}}} \to R_{V_{i}}\), termed structural assignments. The endogenous variables together with \(\mathcal{F}\) characterize a DAG called the causal graph \(G^{\mathop{\mathrm{\mathfrak{C}}}}\vcentcolon=(\mathbf{V}, E)\) of \(\mathop{\mathrm{\mathfrak{C}}}\), whose edge set is \(E = \{(P, X) : X \in \mathbf{V},\; P\in \mathrm{Pa}(X)\setminus \{X\}\}\). We denote by \(\mathop{\mathrm{\mathfrak{C}}}(G)\) the set of SCMs whose causal graph is \(G\). Having an SCM allows us to model interventions: intervening on a variable changes its structural assignment \(f_{X}\) to a new one, say \(\tilde{f}_{X}\). This intervention is then denoted \(\mathit{do}(f_{X} = \tilde{f}_{X})\). In the simplest type of interventions, called atomic interventions, a variable \(X\) is set to a chosen value \(x\), thus replacing the structural assignment \(f_{X}\) of \(X\) with a constant function setting it to \(x\). Such an intervention is denoted \(\mathit{do}(X=x)\), and the SCM resulting from performing this intervention is denoted \(\mathop{\mathrm{\mathfrak{C}}}^{\mathit{do}(X=x)}\). The joint distribution over the endogenous variables resulting from the atomic intervention \(\mathit{do}(X=x)\) is denoted \(p^{\mathit{do}(X=x)}\) and called the post-intervention distribution for this intervention. Each realization \(\mathbf{n}\in R_{\mathbf{N}}\) of the noise variables will be called a unit. A deterministic SCM is an SCM for which the noise distribution is a point mass distribution with all its mass on some (known) unit \(\mathbf{n} \in R_{\mathbf{N}}\). Finally, nodes are denoted by upper case letters, sets of nodes by boldface letters, and variable values by lower case letters. We will make use of the fact that the structural assignments of the ancestors of an endogenous variable \(X\) (including its own structural assignment) can be composed to express \(X\) as a function \(\bar{f}_{X}(\mathbf{n})\) of the vector \(\mathbf{n}\) of exogenous variables values. We call thisthe unrolled assignment of \(X\).

Conditional interventions Given an SCM \(\mathop{\mathrm{\mathfrak{C}}}= (\mathbf{V},\mathbf{N},\mathcal{F},p_{\mathbf{N}})\) with causal graph \(G\), \(X\in \mathbf{V}\), \(\mathbf{Z}_{X} \subseteq \mathbf{V}\setminus \{X\}\), and a (any) function \(g\colon R_{\mathbf{Z}_{X}} \to R_{X}\) (which we call a policy for \(X\)), the conditional intervention on \(X\) given \(\mathbf{Z}_{X}\) for the policy \(g\), denoted \(\mathit{do}(X = g(\mathbf{Z}_{X}))\), is the intervention where the value of \(X\) is determined by that of \(\mathbf{Z}_{X}\) through \(g\) [17]. The precise conditioning set \(\mathbf{Z}_{X}\) for each \(X\) is pre-determined by the specific problem or application, or by the practitioner. In order to systematically study conditional interventions, we will need to make some assumptions of what nodes can reasonably be in \(\mathbf{Z}_{X}\), i.e. what variables can we expect to have knowledge of at the time of applying the policy \(g\) to intervene on \(X\). As noted in [14], [17], the nodes in \(\mathbf{Z}_{X}\) cannot be descendants of \(X\) in \(G\). Hence, \(\mathbf{Z}_{X} \subseteq \mathbf{V}\setminus \mathrm{De}(X)\). On the other hand, all (proper) ancestors of \(X\) are realized before \(X\). Since we will be dealing with the case with no latent variables, we can assume that all ancestors of \(X\) are observed, and can be used by a policy \(g\) to set \(X\) to a value \(g(\mathbf{Z}_{X})\). Thus, we assumethat \(\mathrm{An}(X) \setminus \{X\} \subseteq \mathbf{Z}_{X}\). We will then focus on the case where for each \(X\), the conditioning set \(\mathbf{Z}_X\), chosen by the practitioner, obeys the inclusion relations \(\mathrm{An}(X)\setminus \{X\} \subseteq \boldsymbol{Z}_{X} \subseteq \mathbf{V} \setminus \mathrm{De}(X)\). Furthermore, we focus on cases where the context that is available for an intervention is also available for later interventions. As an example, consider the case where a traffic controller needs to intervene on the delay \(D_{i,s}\) of a train \(i\) at a train station \(s\) (for example by forcing it to wait for 5 extra minutes before departing). Clearly, all delays \(D_{i',s'}\) of all train/station pairs affecting \(D_{i,s}\) have already been observed, and can therefore be used when selecting \(D_{i,s}\). As another example, similar to the one used in [14] when first introducing conditional interventions, consider the situation where a doctor must decide, over a period of three weeks, whether and when to intervene on the weight, blood pressure or renal blood flow of a patient, in order to improve the patient’s kidney function. The goal is to maximize kidney function (variable Kidney3) at the end of the third week. Due to side-effects, the patient can only be prescribed medication for one week. The causal graph for this situation can be found in 5, 10. Notice that at the time of intervening on a node \(X_{i}\), the doctor can use information about all measurements made until then. For instance, all the data available when performing an intervention on the renal flow on week 1 (node RenalFlow1) will also be available when intervening on the renal flow on week 2 (node RenalFlow2). Mathematically, this last assumption can be written \(W \in \mathrm{An}(X) \Rightarrow \mathbf{Z}_{W} \subseteq \mathbf{Z}_{X}\). We then say that \(\mathbf{Z}_{X}\) is an observable conditioning set for \(X\).

Conditional causal bandits Recall that a MAB problem consists of an agent pulling an arm \(a\in \mathcal{A}\) at each round \(t\), resulting in a reward sample \(Y_{t}\) from an unknown distribution associated to the pulled arm [9]. We denote the mean reward for arm \(a\) by \(\mu_{a}\) and the mean reward for the best arm by \(\mu^{*} = \max_{a\in \mathcal{A}} \mu_{a}\). The objective is to maximize the total reward obtained over all \(T\) rounds. Equivalently, this can be framed as minimizing the cumulative regret \(\mathrm{Reg_{T}} = T \mu^{*} - \sum_{t=1}^{T} \mathbb{E}[Y_{t}]\). We now introduce a novel type of (causal) MAB problem. Consider the setting where the bandit’s reward is a (endogenous) variable \(Y\) in an SCM \(\mathop{\mathrm{\mathfrak{C}}}= (\mathbf{V}, \mathbf{N}, \mathcal{F}, p_{\mathbf{N}})\), and the arms are the conditional interventions \(\mathit{do}(X=g(\boldsymbol{Z}_{X}))\), where \(X \in \mathbf{V} \setminus \{Y\}\). Furthermore, the agent has knowledge of the causal graph \(G\) of \(\mathop{\mathrm{\mathfrak{C}}}\), but not of the structural assignments \(\mathcal{F}\) or the noise distribution \(p_{\mathbf{N}}\). We call this a single-node conditional-intervention causal bandit, or simply conditional causal bandit. The reward distribution for arm \(\mathit{do}(X=g(\boldsymbol{Z}_{X}))\) is the post-intervention distribution \(p_{Y}^{\mathit{do}(X=g(\boldsymbol{Z}_{X}))}\), and is unknown to the agent, since it has no knowledge of \(\mathcal{F}\). Notice that selecting an armcan be subdivided in (i) choosing a node \(X\) to intervene on; and (ii) choosing a policy \(g\), i.e. choosing a value to set \(X\) to given the observed variables \(\boldsymbol{Z}_X\). We do not impose any restrictions on the function \(g\). The conditioning sets \(\mathbf{Z}_{X}\) are specified in advance, as described in the paragraph on conditional interventions above. In this paper, we find the minimal set of nodes that need to be considered by the agent in step (i). The value of \(X\) chosen in step (ii) can be selected by an MAB algorithm.

It is worth noting that conditional causal bandits are distinct from contextual causal bandits. Choosing an arm in a conditional causal bandit can also be seen as (i) selecting a variable; (ii) observe the variable’s context; (iii) selecting a value to set the variable to. In contrast, in a contextual causal bandit, arm selection can be described as (i) observing context; (ii) selecting a variable and the value to set it to. See also 7.

As stressed in 1, the novelty of our problem lies in the fact that we deal with conditional interventions that are single-node. Both of these characteristics of our problem demand a different analysis from that of [8] (see 7). Perhaps unexpectedly, single-node interventions make a search for a minimal search space more involved than in the multi-node case (without latent confounders). Indeed, if one allows for interventions on arbitrary sets, one simply needs to intervene on all the parents \(\mathrm{Pa}(Y)\) of \(Y\) [8]. For example, in [subfig:not95lca95heur] one would simply need to intervene on \(\{A_1, A_2\}\). Since in our case the agent cannot do this whenever \(\lvert \mathrm{Pa}(Y) \rvert>1\), the minimal search space will, as we will see, be complex even without unobserved confounding. That said, the assumption that there is no unobserved confounding is a limitation of this paper, and a natural next step for future work (see 8).

3 Conditional-Intervention Superiority↩︎

In this section, we will define a preorder \({\succeq}^{c}_{Y}\) of “conditional-intervention superiority” on nodes of an SCM. If \(X {\succeq}^{c}_{Y} W\), then \(W\) can never be a better node than \(X\) to intervene on with a conditional intervention. We will then show that, perhaps surprisingly, this relation is equivalent to another superiority relation, defined in terms of atomic interventions in a deterministic SCM.

A similar relation can be defined for atomic interventions in deterministic SCMs, where the vector \(\mathbf{N}\) of exogenous variables is fixed to a known value \(\mathbf{n}\) (see 2).

We extend [def:cond-int-sup,def:det-sup] for sets of nodes in the obvious way: \(\mathbf{X}\) is superior to \(\mathbf{W}\) if every node in \(\mathbf{W}\) is inferior to some node in X.

The two relations \({\succeq}^{c}_{Y}\), \(\succeq^{\mathrm{det},a}_{Y}\) actually coincide (both for nodes and sets of nodes).

The difficult direction of this equivalence is \(X \succeq^{\mathrm{det},a}_{Y} W \Rightarrow X {\succeq}^{c}_{Y} W\). One way to see this is to note that, arguably unsurprisingly, \(X \succeq^{\mathrm{det},a}_{Y} W\) forces\(X\) to lie on every directed path \(W \dashrightarrow Y\), so \(X\) fully mediates whatever influence \(W\) has on \(Y\) (see 4). Once this mediation holds, anything a policy \(h\) on \(W\) achieves can be reproduced by a policy \(g\) on \(X\): simply set \(X\) to the value that \(h\) would have induced at \(X\). Hence \(X\) can always do at least as well as \(W\). The converse \(X {\succeq}^{c}_{Y} W \Rightarrow X \succeq^{\mathrm{det},a}_{Y} W\) is easier to check. \(X {\succeq}^{c}_{Y} W\) implies that there is a policy \(g^*\) such that \(\mathit{do}(X=g^*(\boldsymbol{Z}_X))\) is at least as good as \(\mathit{do}(W=h(\boldsymbol{Z}_W))\) for all \(h\), thus in particular for constant policies \(h(\boldsymbol{Z}_W) = w\). For a (deterministic) SCM with fixed setting \(m\), one can just set \(x^*\) to be \(g^*(\bar{f}_{\boldsymbol{Z}_X}(m))\), thus guaranteeing that \(\mathit{do}(X=x^*)\) is not inferior to \(\mathit{do}(W=w)\). The full, formal proof of [prop:cond-vs-atomic] can be found in 14.

We emphasize that [prop:cond-vs-atomic] equates conditional-intervention superiority with deterministic atomic-intervention superiority only — notgeneral atomic superiority.

Since these two relations are equivalent, we henceforth refer simply to interventional superiority without further specification, and use the symbol \(\succeq_{Y}\) when distinguishing them is not necessary. We will use [prop:cond-vs-atomic] to simplify our problem. Since deterministic atomic interventions are easier to reason about, we use them in formulating proposals for the minimal search space and in our proofs.

4 Graphical Characterization of the mGISS↩︎

Goal Our aim is to develop a method to identify, based on a causal graph \(G\), the smallest set of nodes that are “worth testing” when attempting to maximize \(Y\) by performing one single-node intervention. Specifically, regardless of the structural causal model \(\mathop{\mathrm{\mathfrak{C}}}\) associated with \(G\), we want to ensure that the optimal intervention can be discovered within this selected set of nodes. We define this set as follows:

This set is unique, so that we can talk of the minimal globally interventionally superior set.

As a sketch of the argument: if \(A\) and \(B\) were distinct minimal GISS, pick \(X \in B \setminus A\). Since \(A\) is globally superior, some \(Z \in A\) dominates \(X\). Now, either \(Z \in B\) already, or \(B\) dominates \(Z\) via some \(X' \in B\), and transitivity gives \(X' \succeq_Y X\). This produces two distinct comparable nodes inside \(B\). But a minimal GISS contains no two comparable nodes (dropping the dominated one would still leave a GISS), so no two distinct minimal sets can exist.

We now develop the intuition behind the machinery we introduce to arrive at a graphical characterization of the mGISS. Recall that, by [prop:cond-vs-atomic], we can rely on intuition about deterministic causal systems and atomic interventions throughout.

Intuition Since the value of \(Y\) is completely determined by the values of its parents \(A_{1}, \ldots, A_{m}\), along with the fixed value \(n_{Y}\) of a noise variable that cannot be intervened upon (see 2), we aim to induce the parents to acquire the combination of values \((a^{*}_{1}, \ldots, a^{*}_{m})\) that maximizes \(Y\) when \(N_{Y} = n_{Y}\). If this is not possible to achieve using a single intervention, we aim to obtain the best combination possible. Clearly, the parents of \(Y\) themselves need to be tested by bandit algorithms: there may be one parent on which \(Y\) is highly dependent, in such a way that there is a value of that parent which will maximize \(Y\). In the particular case where \(Y\) has a single parent \(A\), that node is the only node worth intervening on, since all other nodes can only influence \(Y\) through \(A\). Indeed, if \(a^{*} \in R_{A}\) is the value of \(A\) which maximizes \(Y\), it is not necessary to try to find an intervention on ancestors of \(A\) which results in \(A=a^{*}\): just set \(A=a^{*}\) directly ([subfig:one-parent-heur]). If \(Y\) has two or more parents, it is possible that a single intervention on one of the \(A_{i}\) does not yield the best possible outcome. Instead, a better configuration (potentially even the ideal case \((a^{*}_{1}, \ldots, a^{*}_{m})\)) may be achieved by intervening on a common ancestor of some or all of the \(A_{i}\) (1). Notice that \(X_{0}\) is also a common ancestor of \(A_{1}, A_{2}\), but one is never better off intervening on \(X_{0}\) than on \(X_{1}\). This is because all paths from \(X_0\) to \(A_1\) or \(A_2\) must pass through \(X_1\), so any influence that \(X_0\) can exert on \(Y\) is fully mediated by \(X_1\). This seems to indicate that testing interventions on, for instance, all lowest common ancestors (LCAs, see 9) of the parents of \(Y\), and only them, is necessary. While this works in 1, it fails for a graph such as [subfig:vanilla-lca-issue], where \(X\) needs to be tested and yet it is not in \(\mathrm{LCA}(A_{1}, A_{2}) = \{A_{1}\}\). This suggests that we need to define a stricter notion of common ancestor to make progress in characterizing \(\mathrm{mGISS}_{Y}(G)\).

Our heuristic argument so far suggests that we need to test the parents of \(Y\) and their LSCAs. However, there are additional nodes that must be considered: the reasoning for testing the lowest strict common ancestors of the parents can be repeated. For instance, in [subfig:not95lca95heur], the best possible configuration of the \(A_{i}\) may be achieved by intervening on \(Z\). Such an intervention could result in a combination of values of \(X_{1}\) and \(A_{2}\) that leads to the best possible combinations of \(A_{1}\) and \(A_{2}\). This suggests that the \(\mathrm{mGISS}_{Y}(G)\) should be determined by recursively finding all the LSCAs of the parents of \(Y\), then the LSCAs of that set, and so on, ultimately resulting in what we call the “LSCA closure of the parents of \(Y\)”, denoted \(\mathcal{L}^{\infty}(\mathrm{Pa}(Y))\). In the remainder of this section, we formally define \(\mathcal{L}^{\infty}(\mathrm{Pa}(Y))\), find a simple graphical characterization for it, and prove that it indeed equals \(\mathrm{mGISS}_{Y}(G)\).

Note that, in cases where \(\mathrm{Pa}(Y)\) has no strict common ancestor, the closure stabilizes immediately and \(\mathrm{mGISS}= \mathrm{Pa}(Y)\). That is, only the parents of \(Y\) themselves are worth testing. Note that \(\mathrm{Pa}(Y) \subseteq L^\infty(\mathrm{Pa}(Y))\) always, so the mGISS is never empty as long as \(Y\) has some parents.

We will introduce the notion of “\(\Lambda\)-structures” (2), which provides an alternative, elegant, simple graphical characterization of \(\mathcal{L}^{\infty}(\mathrm{Pa}(Y))\). It will also be instrumental in the proofs of the main results of this paper.

Notice that, if \(V\in \mathbf{U} \cap \mathbf{W}\), then trivially \(V\in \Lambda(\mathbf{U},\mathbf{W})\): just take the trivial paths \(\pi=\pi'=(V)\).

We are now ready for the main result of this paper.

We emphasize that, due to [prop:cond-vs-atomic], this graphical characterization of the \(\mathrm{mGISS}_{Y}(G)\) is valid both for conditional interventions in a probabilistic causal model as for atomic interventions in a deterministic causal model (i.e. a causal model with known \(\mathbf{n}\)).

5 Algorithm to Find the Minimal Globally Interventionally Superior Set↩︎

The Closure Computation via Children with Multiple Connectors (C4) Algorithm (3) computes the closure \(\mathcal{L}^{\infty}(\mathbf{U})\) in \(O(|\mathbf{V}|+|E|)\) time, using connectors (illustrated in [fig:c4example]):

The connectors are constructed such that each \(\mathfrak{c}[V]\) “connects” \(V\) to \(\mathcal{L}^{\infty}(\mathbf{U})\) in the sense that \(\mathfrak{c}[V]\) is the first node in \(\mathcal{L}^{\infty}(\mathbf{U})\) on any path from \(V\) to \(\mathcal{L}^{\infty}(\mathbf{U})\). Thus, \(\mathfrak{c}[V]\) mediates all influence that \(V\) exerts over \(\mathcal{L}^{\infty}(\mathbf{U})\). This is formalized in 17 in 15. Consider for example the graph from [fig:c4example]. \(J\) and \(K\) are the elements of \(\mathbf{U}\), and thus \(\mathfrak{c}[J] = J\), \(\mathfrak{c}[K]=K\). Trivially, the first nodes on all paths from \(J\) and \(K\) to \(\mathcal{L}^{\infty}(\mathbf{U}) \supseteq \mathbf{U}\) are \(J\) and \(K\), respectively. The connector of \(H\) is \(\mathfrak{c}[H]=K\), and indeed \(K\) is the first element of the closure \(\mathcal{L}^{\infty}(\mathbf{U})\) on the only path (\(H \rightarrow K\)) from \(H\) to \(\mathcal{L}^{\infty}(\mathbf{U})\). Similarly for \(G\), whose connector is \(\mathfrak{c}[G]=J\). In contrast, \(E\) is its own connector (and thus is, as discussed below, an element of \(\mathcal{L}^{\infty}(\mathbf{U})\)). Again, all paths from \(E\) to \(\mathcal{L}^{\infty}(\mathbf{U})\) must (trivially) go through \(E\).

Crucially, 17 implies that \(V \in \mathcal{L}^{\infty}(\mathbf{U}) \Leftrightarrow \mathfrak{c}[V]=V\). Equivalently, \(V\) is its own connector if and only if it forms a \(\Lambda\)-structure over \((\mathbf{U}, \mathbf{U})\). Intuitively, if all children of \(V\) have the same connector \(X\) (i.e. \(\mathbf{C}=\{X\}\)), then \(V\) can only influence \(\mathbf{U}\) via \(X\), making \(X\) interventionally superior to \(V\), and thus \(V \notin \mathcal{L}^{\infty}(\mathbf{U})\). On the other hand, if \(V\)’s children have multiple connectors (i.e. \(\lvert \mathbf{C} \rvert>1\)), then interventions on \(V\) can influence all those connectors, so \(V\) is a potentially worthwhile candidate for intervention, and thus \(V \in \mathcal{L}^{\infty}(\mathbf{U})\). This establishes correctness of C4, which finds all nodes satisfying \(\mathfrak{c}[V] = V\) in linear time.

6 Experimental Results↩︎

We evaluate C4 on both random and real graphs. Additionally, we examine the impact of our method on the cumulative regret of a bandit algorithm.

Search space reduction in random graphs We applied the C4 algorithm to randomly generated DAGs using the Erdős-Rényi model for \(N\) graphs and probability \(p\) [18] adapted to DAG-generation. We generated \(1000\) graphs using \(20, 100, 300\), and \(500\) nodes, and varying the expected (total) degree of nodes from \(2\) to \(11\) in steps of \(3\). For each graph \(G\), we set the target \(Y\) to be the node with the most ancestors, used C4 to compute \(\mathcal{L}^{\infty}(\mathrm{Pa}(Y)) = \mathrm{mGISS}_{Y}(G)\), and calculated the fraction of nodes in \(\mathrm{An}(Y) \setminus \{Y\}\) that remain in \(\mathrm{mGISS}_{Y}(G)\). The results revealed that, for a given number of nodes, graphs with lower expected degrees benefit more from our method (i.e. their \(\mathrm{mGISS}_{Y}(G)\) correspond to smaller fractions of \(\mathrm{An}(Y) \setminus \{Y\}\)). Furthermore, for a fixed expected degree, our method is more effective for higher numbers of nodes. For example, for graphs with \(500\) nodes, the mGISS retained, on average, \(17\%\), \(29\%\), \(62\%\) and \(77\%\) of the nodes, for expected degrees of \(2, 5, 8\) and \(11\), respectively. Moreover, graphs with an expected degree of \(5\) saw these numbers decrease from \(70\%\) at \(20\) nodes to \(47\%, 35\%\) and \(29\%\) for \(100, 300\) and \(500\) nodes, respectively. The complete results are presented in 20 (16). These results are not surprising: if the average degree is small compared to the number of nodes, the edge density is small, in which case we expect fewer \(\Lambda\)-structures to form over Pa(Y). Graphs modeling real-world systems tend to have low average degrees, as can be seen in the graphs from the popular Bayesian network repository bnlearn. Therefore, we expect our method to be especially effective in those graphs. We test this below.

Search space reduction in real-world graphs We tested our method in most graphs from the bnlearn repository , as well as on a graph representing the causal relationships between train delays in a segment of the railway system of the Netherlands (see 16). For each graph, we set \(Y\) to be the node with most ancestors. The results are presented in the bar plot of 21 (16). This confirmed that realistic models with larger graphs tended to benefit more from our method, with a reduction of over \(90\%\) of the search space for some of the largest models. Notice also that these models indeed have relatively small average degrees, all below \(4.0\). From this, we conclude that we can expect our method to be useful when reducing the search space of conditional causal bandit tasks in real-world causal models, especially when they are large.

Impact on conditional intervention bandits We present empirical evidence that restricting the node search space to the mGISS allows a straightforward UCB-basedalgorithm (which we call CondIntUCB) for conditional causal bandits to converge more rapidly to better nodes. As explained in 2, on each round the algorithm must (i) choose which node \(X\) to intervene on; and (ii) choose the value for \(X\), given its conditioning set \(Z_{X}\). Choice (i) employs UCB over nodes, while choice (ii) utilizes a UCB instance specific to the conditioning set value. In other words, for each realization of \(\boldsymbol{Z}_{X}\) (each context) there is a UCB. This is identical to what is described in [9] for contextual bandits with one bandit per context. The cumulative regretis computed with respect to node choice, since we want to see how our node selection method affects the quality of node choice by CondIntUCB. We use 4 real-world datasets from the bnlearn repository, and again choose the node of each dataset with the most ancestors as the target. These datasets were selected because their graphical structures are non-trivialand both \(\mathrm{An}(Y)\) and \(\mathrm{mGISS}_{Y}(G)\) are sufficiently small to allow experimentation with our setup. For each dataset, we run CondIntUCB up to 500 times and plot the two average cumulative regret curves along with their standard deviations, corresponding to using all nodes (brute-force) and the mGISS nodes (4). The total number of rounds is chosen as to observe (near) convergence. These results show that cumulative regret curves can be significantly improved—meaning that better nodes are selected earlier for applying conditional interventions—if the search space over nodes is pruned using our C4 algorithm.

7 Related Work↩︎

Recent works in “contextual causal bandits” address interventions that account for context, bearing resemblance to our problem. However, our problem remains distinct. In a \(K\)-arm contextual bandit problem, each round is associated with a context that determines the reward distributions of the \(K\) arms. The agent uses the context to select one of the \(K\) arms. A general approach to solving such problems is to maintain a separate standard bandit algorithm for each context. More efficient solutions typically rely on assumptions about relationships between contexts [9]. In contrast, a conditional causal bandit problem involves, in each round, an intervened node \(X\) and an observed context that is a sample of \(\mathbf{Z}_{X}\). This context determines the reward distributions of the \(K = \lvert R_X \rvert\) possible atomic interventions on \(X\), and the agent chooses among these according to a policy. Thus, a conditional causal bandit problem can be interpreted as a collection of contextual bandits, one for each node \(X\) in a causal graph. In particular, conditional causal bandits are not simply particular cases of contextual bandits. In this paper, we leverage the structure of the causal graph to eliminate certain nodes, i.e., to exclude some of these contextual bandits from consideration. In [19], the term “contexts” is used in a very different way to the one used in our paper, actually referring to different graphs as opposed to different variable values. [20], [21] tackle the scenario in which an intervention is performed, with knowledge of a given set of context variables, on a pre-chosen variable \(X\) that has an edge into \(Y\) (and no other outgoing edges). This approach can be understood as selecting a conditional intervention for a predefined node from a very simple graph. In contrast, in our setting we need to choose what variable to intervene on to begin with, and there are no restrictions on the causal graph.

As mentioned in 1, [1] introduced the original causal bandit problems, which involve hard interventions in causal models. Subsequent works [22]–[28] proposed algorithms for variants of causal bandits with both hard and soft interventions, budget constraints, and unobserved confounders.

All of the works described above proposed algorithms which aim at accelerating learning by utilizing knowledge of the causal model. As explained in 1, this contrasts with our work, which, like the work of [8], [29], uses knowledge of the causal graph to find a minimal search space (over the nodes) for causal bandits. And, while the latter focus on multi-node, hard interventions, we focus on single-node, conditional interventions.

It is instructive to compare the mGISS with the minimal intervention sets (MIS) and possibly-optimal minimal intervention sets (POMIS) of [8]. There, an arm is a multi-node intervention on a set of variables, and one restricts attention to MISs (sets with no redundant subset) and, among these, to POMISs — the MISs that are non-dominated, i.e. optimal for some SCM consistent with \(G\). In our work, arms are single-node, so there is no redundancy among simultaneously-intervened sets to exploit, and thus no construction analogous to the MIS. The correct analogy is between the set of all POMISs and the mGISS. Each POMIS is a non-dominated set of nodes, while each element of the mGISS is a non-dominated node.

The work of [30] presents an interesting connection to our work. Given a causal graph, they study the sets of pairs \((\mathrm{node}, \mathrm{context(node)})\) (referred to as “scopes”) that may correspond to an optimal (multi-node) intervention policy where each node \(X\) in a scope is intervened on according to a policy \(\pi_{X}(X \mid \mathrm{context(X)})\). This is a challenging problem, and they do not provide a full characterization of these optimal scopes, instead deriving a set of rules that can be used to compare certain pairs of scopes. In this paper, we instead address the single-node intervention case, so that the rules derived by [30] for scope comparison do not apply to our case. Additionally, we are not concerned with finding the smallest conditioning sets we can. These are fixed by the experiment or the intervener (see 2). We focus instead on choosing the nodes that can yield the best results when intervened upon.

8 Discussion and Conclusion↩︎

In this paper we introduced the conditional causal bandit problem, where the agent only has knowledge of the causal graph \(G\), the arms are conditional interventions, and the reward variable belongs to \(G\). The theoretical contributions include a rigorous graphical characterization of the minimal set of nodes which is guaranteed to contain the node with the optimal conditional intervention, and the C4 algorithm, which computes this set in linear time. Empirical results validate that our approach substantially prunes the search space in both real-world and sparse randomly-generated graphs. Furthermore, integrating mGISS with a UCB-based conditional bandits algorithm showcased improved cumulative regret curves.

Importantly, our method is not itself a causal bandit algorithm, but a search space reduction that can be used as a pre-processing step for any intervention-selection strategy. Once a graph is available, C4 can substantially restrict the candidate intervention space. Note that we focused on single-node conditional interventions, a setting that, somewhat surprisingly, is actually more challenging than the multi-node case. To our knowledge, there is currently no existing work which addresses search-space pruning in this setting. As a result, direct comparisons with existing approaches are not possible.

Several extensions remain open, including settings with partially known graphs or a finite number \(K>1\) of interventions.

Addressing latent confounding would require substantially more research and is left to future work: it can render nodes outside the LSCA closure essential — e.g. in the case\(Z \to A \to Y\) with a latent confounder between \(A\) and \(Y\), \(Z\) must enter the mGISS despite being a strict common ancestor of no pair of parents of \(Y\).

We view this work as a first step toward addressing these more general cases. Furthermore, while [30] consider multi-node interventions, it would be interesting in future work to adapt their ideas to the single-node case and identify the smallest \(\boldsymbol{Z}_{X}\) sets for which the best policy can still be found.

Our method assumes the causal graph is known. When it is not, two cases are worth distinguishing. If a family of candidate graphs is available (e.g., a Markov equivalence class or the output of a causal discovery procedure), C4 can be applied to each candidate and the results combined by union. For a misspecified single graph, the consequences depend on the type of error: extra edges enlarge the LSCA closure (so the mGISS is conservatively larger but still contains the optimal node), while missing edges can cause genuinely necessary nodes to be excluded and thus break the guarantees. In short, C4 is robust to over-specification and brittle to under-specification of the causal graph.

9 Directed Acyclic Graphs↩︎

All graphs in this paper are directed acyclic graphs (DAGs). Every path is assumed to be directed. A path \(\pi\) in a graph \(G = (\mathbf{V}, E)\) is a tuple of nodes such that each node \(X\) in the path has an outgoing arrow from \(X\) to the next node in the tuple. For \(X \in \mathbf{V}\), we denote by \(\mathrm{Pa}(X)\), \(\mathrm{Ch}(X)\), \(\mathrm{De}(X)\) and \(\mathrm{An}(X)\) the sets of parents, children, descendants and ancestors of \(X\), respectively. We denote by \(\pi\colon X \dashrightarrow Y\) a path starting at node \(X\) and ending at node \(Y\), and \(\mathring{\pi}\) denotes the path formed by the inner nodes of \(\pi\). By abuse of notation, we often perform set operations such as \(\pi_{1} \cap \pi_{2}\) between paths, which implicitly means that these operations are performed on the sets of nodes belonging to the paths. Tuples with a single node are also considered to be paths, and are said to be trivial. Also, if \(B\in \pi\colon X\dashrightarrow Y\), then the paths \(\pi\vert^{Z}\colon Z\dashrightarrow Y\) and \(\pi\vert_{Z}\colon X\dashrightarrow Z\) are the paths resulting from removing from \(\pi\) all nodes before and after \(Z\), respectively. Every node is an ancestor of itself, so that the relation \(\preccurlyeq\) defined by \(X \preccurlyeq Y \iff Y \in \mathrm{An}(X)\) is a partial order. Given a set \(\mathbf{U}\) of nodes, we denote by \(\max_{\preccurlyeq}[\mathbf{U}]\) the set of maximal elements of \(\mathbf{U}\) with respect to \(\preccurlyeq\). We call this the ancestor partial order. If there is a non-trivial path from \(X\) to \(Y\), then \(Y\) is said to be reachable from \(X\). The set of common ancestors of nodes \(X\) and \(Y\) is denoted \(\mathrm{CA}(X,Y) = \mathrm{An}(X) \cap \mathrm{An}(Y) = \{Z \in \mathbf{V}\;\colon Z \preccurlyeq X \wedge Z \preccurlyeq Y\}\). Finally, the degree of a node in a DAG is the sum of the incoming and outgoing arrows of that node.

We also make use of a lesser-known graph theory concept, relevant for this paper: the “lowest common ancestors” of nodes \((X,Y)\). These are common ancestors that don’t reach any other common ancestors, intuitively making them the “closest” to \((X,Y)\).

For example, in 1, \(\mathrm{LCA}(A_{1}, A_{2}) = \{X_{1}\}\), whereas in [subfig:not95lca95heur], \(\mathrm{LCA}(A_{1}, A_{2}) = \{A_{1}\}\).

10 The Kidney Function Example↩︎

Recall the kidney function example discussed in 2. The variables Weight\(N\), BP\(N\) and RenalFlow\(N\) are the weight, blood pressure, and renal blood flow of the patient at the end of week \(N\) (equivalently, at the start of week \(N+1\)). All are measured at the end of each week. The doctor can intervene on one of these variables using the measured values as context for the intervention, in order to optimize the kidney function of the patient at the end of week 3 (Kidney3). We model this situation with the causal graph depicted in 5. Making use of [thm:superiority95of95lsca], we see that the minimal set of nodes which needs to be tested in this case is {RenalFlow2, Weight2, Weight1, Weight0}.

11 Unrolled Assignments↩︎

The structural assignments of an SCM can be utilized to express any endogenous variable as a function of the exogenous variables only. This is achieved by composing the assignments until reaching the exogenous variables. Our proofs will rely on these functions, which we will refer to as “unrolled assignments”, since we “unroll” the expressions for the endogenous variables until only exogenous variables are left. We define them formally by induction as follows:

Additionally, we can consider \(X\) as a function of both exogenous variables and a chosen endogenous variable \(B\). To achieve this, we substitute the assignments until we reach either \(B\) or the exogenous variables, thereby “unrolling” the dependencies until we reach the exogenous variables or we are blocked by \(B\).

The following lemma relates blocked unrolled assigments with atomic interventions, and will be used to prove [thm:superiority95of95lsca].

The following lemma shows how one can chain (blocked) unrolled assignments when there is a node \(Z\) present in all paths from the blocking node \(B\) to \(Y\). This result is consistent with the intuition that, if all paths from \(B\) to \(Y\) must go through \(Z\), then knowing the value of \(Z\) is enough to compute \(Y\).

12 Conditional Superiority vs Deterministic Atomic Superiority↩︎

We will show that conditional intervention superiority is equivalent to deterministic atomic intervention superiority. This result will help prove results about the former by making use of the former, which is mathematically simpler and easier to reason about.

We will also need a lemma similar to 7 but for conditional-intervention superiority. Its proof is similar to that of 7.

As mentioned in the main text (3), the superiority relation for atomic interventions in non-deterministic (general) SCMs defined in the natural way is not equivalent to \({\succeq}^{c}_{Y}\). Indeed, consider the following example:

13 Intervention Superiority Relations are Preorders↩︎

It is straightfoward to show that both interventional superiority relations are in fact preorders, and are partial orders if restricted to \(\mathrm{An}(Y)\).

13.1 …and are Partial Orders in \(\mathrm{An}(Y)\)↩︎

Notice that 4 is actually slightly stronger than antisymmetry within \(\mathrm{An}(Y)\), since \(X_1 \succeq^{\mathrm{det},a}_Y X_2\) and \(X_2 \succeq^{\mathrm{det},a}_Y X_1\) can only occur for distinct \(X_1,X_2\) if both are outside \(\mathrm{An}(Y)\).

14 Proofs for the Minimal Globally Interventionally Superior Set↩︎

14.1 Uniqueness of the mGISS↩︎

14.2 The LSCA Closure and \(\Lambda\)-Structures↩︎

It will be useful to know that, in order to show that a node belongs to \(\mathcal{L}^{\infty}(\mathbf{U})\), it suffices to prove that it belongs to the LSCA closure of a subset of \(\mathbf{U}\). We show by induction that this is indeed the case.

14.3 The LSCA Closure is the mGISS↩︎

To facilitate the exposition of the proof in [thm:superiority95of95lsca], we introduce the concept of superiority in a given SCM. It is simply a version of 2 with no universal quantifier over \(\mathop{\mathrm{\mathfrak{C}}}\). This definition can be extended for sets of nodes in the obvious way (in an identical manner to how 3 extended 1 and 2).

15 C4 Proofs↩︎

16 Supplementary Material for Experimental Results↩︎

The results of the experiments testing our search space reduction method are presented in 20 and 21, for randomly generated graphs and real-world datasets, respectively.

All real-world datasets come from the bnlearn repository, except for the railway dataset, which was provided by ProRail, the institution responsible for traffic control in the Dutch railway system. The bnlearn repository can be found in https://www.bnlearn.com/bnrepository/. It was created by Marco Scutari as part of the bnlearn R package, and it is licensed under the Creative Commons Attribution-ShareAlike 3.0 License (CC BY-SA 3.0).

The railway dataset consists of a graph whose nodes represent train delays in a segment of the Dutch railway system, measured at specific “points of interest” (such as train stations). Each node is labeled with a code identifying the train, an acronym for the point of interest, a letter indicating the train’s activity at that location—arriving (A), departing (V), or passing through (D)—and the planned time for that activity. Arrows are drawn between delay nodes that are known to influence each other. For example, arrows connect nodes of the same train at consecutive times, as the delay of a train at time \(t\) will influence its delay at \(t + \Delta t\). Additionally, arrows may connect nodes corresponding to train activities sharing the same platform, since a train must wait for the preceding train to vacate the platform before using it. This dataset can be found in the code repository.

The two search space reduction experiments – on both random and real-world graphs – were completed in a few minutes on a CPU-based laptop with 16 GB RAM and 512 GB SSD storage. The experiments evaluating the impact of our method on conditional intervention bandits using the bnlearn models asia, sachs and child were also run on the same laptop. However, the most complex model, pathfinder, exceeded the laptop’s memory capacity due to the large number of possible contexts generated from combinations of values assigned to ancestor nodes. Thus, the pathfinder experiment was run on an internal server with 1 TB RAM (350 GB allocated for the job) and 23 TB SSD storage (our codebase used 1.5 GB). All experiments used CPU-only compute workers. The asia, sachs, and child models completed in approximately 12 hours on the laptop using 2 CPU cores in parallel, while the pathfinder experiment took about 16 hours using 27 CPU cores in parallel on the server.

References↩︎