Matching a Desired Causal State via Shift Interventions
Authors: Jiaqi Zhang
Chandler Squires
Caroline Uhler
Venue: NeurIPS 2021 Poster (2021)
Keywords: Causality
Active Learning
Graphical Models

Abstract: Transforming a causal system from a given initial state to a desired target state is an important task permeating multiple fields including control theory, biology, and materials science. In causal models, such transformations can be achieved by performing a set of interventions. In this paper, we consider the problem of identifying a shift intervention that matches the desired mean of a system through active learning. We define the Markov equivalence class that is identifiable from shift interventions and propose two active learning strategies that are guaranteed to exactly match a desired mean. We then derive a worst-case lower bound for the number of interventions required and show that these strategies are optimal for certain classes of graphs. In particular, we show that our strategies may require exponentially fewer interventions than the previously considered approaches, which optimize for structure learning in the underlying causal graph. In line with our theoretical results, we also demonstrate experimentally that our proposed active learning strategies require fewer interventions compared to several baselines.

Matching a Desired Causal State via Shift Interventions
Jiaqi Zhang LIDS, EECS, and IDSS, MIT vi vichang@@mt edu
Chandler Squires LIDS, EECS, and IDSS, MIT csquires@mit. edu
Caroline Uhler
LIDS, EECS, and IDSS, MIT cuhler@mit edu
Abstract
Transforming a causal system from a given initial state desired target state is important task permeating multiple fields including control theory, biology, and materials science. In causal models, such transformations can be achieved by performing set of interventions. In this paper, we consider the problem of identifying a shift intervention that matches the desired mean of system through active learning. We define the Markov equivalence class that is identifiable from shift interventions and propose two active learning strategies that are guaranteed to exactly match a desired mean. We then derive worst-case lower bound for the number of interventions required and show that these strategies are optimal for certain classes of graphs. In particular, exponentially fewer interventions than the previously considered approaches, which optimize for structure learning in the underlying causal graph. In line with our theoretical results, we also demonstrate experimentally that our proposed active learning strategies require fewer interventions compared several baselines.
show that strategies may require
1 Introduction
Consider an experimental biologist attempting to turn cells from one type into another, e.g., from fibroblasts neurons (Vierbuchen et al., 2010), by altering gene expression. This is known as cellular reprogramming and has shown great promise in recent years for regenerative medicine (Rackham al., 2016). A common approach is model gene expression of cell, which is governed by an underlying gene regulatory network, using structural causal model (Friedman al., 2000; Badsha al., 2019). Through set of interventions, such gene knockouts expression of transcription factors (Dominguez et al., 2016), a biologist can infer the structure of the underlying regulatory network. After inferring enough about this structure, biologist can identify the intervention needed to successfully reprogram cell. More generally, transforming causal system from an initial state to a desired state through interventions is an important task pervading multiple applications. Other examples include closed-loop control (Touchette and Lloyd, 2004) and pathway design of microstructures (Wodo al., 2015).
With little prior knowledge of the underlying causal model, this task is intrinsically difficult. Previous works have addressed the problem of intervention design to achieve full identifiability of the causal model (Hauser and Bühlmann, 2014; Greenewald et al., 2019; Squires et al., 2020a). However, since interventional experiments tend be expensive in practice, one wishes to minimize the number of trials and learn just enough information about the causal model to be able to identify the intervention that will transform it into the desired state. Furthermore, in many realistic cases, the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of interventions which can be performed is constrained. For instance, in CRISPR experiments, only limited number of genes can be knocked out to keep the cell alive; or in robotics, a robot can only manipulate certain number of arms at once.
Contributions. We take the first step towards the task of causal matching (formalized in Section 2), where an experimenter can perform a series of interventions in order to identify a matching inter- vention which transforms the system to a desired state. In particular, we consider the case where the goal is to match the mean of a distribution. We focus on a subclass of interventions called shift interventions, which can for example be used to model gene wvereexpesssion experiments (Triantafil- lou et al., 2017). These interventions directly increase or decrease the values of their perturbation targets, with their effect being propagated variables which are downstream (in the underlying causal graph) of these targets. We show that there always exists a unique shift intervention (which may have multiple perturbation targets) that exactly transforms the mean of the variables into the desired mean (Lemma 1). We call this shift intervention the matching intervention.
To find the matching intervention, in Section we characterize the Markov equivalence class of causal graph induced by shift interventions, i.e., the edges in the causal graph that are identifiable from shift interventions; in particular, we show that the resulting Markov equivalence classes can be more refined than previous notions of interventional Markov equivalence classes. We then propose two active learning strategies in Section 4 based on this characterization, which are guaranteed to identify the matching intervention. These active strategies proceed in an adaptive manner, where each intervention is chosen based on all the information gathered so far.
In Section 5, we derive a worst-case lower bound on the number of interventions required to identify the matching intervention and show that the proposed strategies are optimal up logarithmic factor. Notably, the proposed strategies may use exponentially fewer interventions than previous active strategies for structure learning. Finally, in Section 6, we demonstrate also empirically that our proposed strategies outperform previous methods as well as other baselines in various settings.
1.1 Related Works
Experimental Design. Previous work on experimental design in causality has considered two closely related goals: learning the most structural information about the underlying DAG given a fixed budget of interventions (Ghassami et al., 2018), and fully identifying the underlying DAG while minimizing the total number or cost (Shanmugam et al., 2015; Kocaoglu et al., 2017) of interventions. These works can also be classified according to whether they consider a passive setting, i.e., the interventions are picked at a single point time (Hyttinen et al., 2013; Shanmugam et al., 2015; Kocaoglu et al., 2017), or an active setting, i.e., interventions are decided based on the results of previous interventions (He and Geng, 2008; Agrawal et al., 2019; Greenewald et al., 2019; Squires et al., 2020a). The setting addressed in the current work is closest to the active, full-identification setting. The primary difference is that in order to match a desired mean, one does not require full identification; in fact, as we show in this work, we may require significantly less interventions.
Causal Bandits. Another related setting is the bandit problem in sequential decision making, where an agent aims to maximize the cumulative reward by selecting an arm at each time step. Previous works considered the setting where there are causal relations between regrets and arms (Lattimore et al., 2016; Lee and Bareinboim, 2018; Yabe et al., 2018). Using a known causal structure, these works were able to improve the dependence on the total number of arms compared to previous regret lower-bounds (Bubeck and Desa-Bianchi, 2012; Lattimore et al., 2016). These results were further extended to the case when the causal structure is unknown a priori (de Kroon et al., 2020). In all these works the variables are discrete, with arms given by do-interventions (i.c., setting variables to given value), so that there are only a finite number of arms. In our work, we are concerned with the continuous setting and shift interventions, which corresponds to an infinite (continuous) set of arms.
Correlation-basser Approaches. There are also various correlation- based approaches for this task that do not make use of any causal information. For example, previous works have proposed score- based (Cahan et al., 2014), entropy-based (D' Alessio et al., 2015) and distance- approaches (Rackham et al., 2016) for cellular reprogramming. However, as shown in bandit settings (Lattimore et al., 2016), when the system follows a causal structure, this structure can be exploited to learn the optimal intervention more efficiently. Therefore, we here focus on developing a causal approach.

---

a
(a)
Figure 1: Completely identifying DAG can require exponentially more interventions than identifying the matching intervention. Consider a graph constructed by joining r size-4 cliques, where the matching intervention has the source node the only perturbation target, pictured in (a) with r = 2 and the source node in purple: (b) shows the minimum size set intervention (in purple) that completely identifies the DAG, which grows as O(r) (Squires et al., 2020a). In Theorem 2, we show that the matching intervention can be identified in Ologr) single-node interventions.
Problem Setup
We now formally introduce the causal matching problem of identifying intervention to match the desired state a causal system under a given metric. Following Koller and Friedman (2009), a causal structural model is given by a directed acyclic graph (DAG) g with nodes [p] = (1,.... P). and a set of random variables X
Xpl whose joint distribution P factorizes according to G. Denote by (i) = tjj E [p] j i} the parents of node i in G. An intervention I C [p] with multiple perturbation targets i E 1 either removes all incoming edges to X; (hard intervention) or modifies the conditional probability P(XiIXXag(( (soft intervention) for all i T. This results in
an interventional distribution P'. Given a desired joint distribution Q over X, the goal of causal matching is to find an optimal matching intervention I such that P' best matches Q under some metric. In this paper, we address a special case of the causal matching problem, which we call causal mean matching, where the distance metric between pl and Q depends only their expectations.
We focus on causal mean matching for a class of soft interventions, called shift interventions (Rothenhäusler et al., 2015). Formally, a shift intervention with perturbation targets T C [p] and shift values Jeer modifies the conditional distribution as (X(; = x + a; X p=)(()) x x(Xpag(t)) Here, the shift values {at hie are assumed to be deterministic. We aim to find C [p] and father ! such that the mean of Pd is closest that of Q, i.e., minimizes d(Ep, (X), Eq for some metric In fact, as we show in the following lemma, there always exists a unique shift intervention, which we call the matching intervention, that achieves exact mean matching."
P(X, =
Lemma 1. For any causal structural model and desired mean Ex(X), there exists unique shift intervention I' such that Epr (X) = [X)
We assume throughout that the underlying causal DAG is unknown. But assume causal sufficiency (Spirtes et al., 2000), which excludes the existence of latent confounders, as well as access enough observational data to determine the joint distribution P and thus the Markov equivalence class of G (Andersson et al., 1997). It is well-known that with enough interventions, the causal DAG becomes fully identifiable (Yang et al., 2018). Thus one strategy for causal mean matching is to first use interventions to fully identify the structure of G, and then solve for the matching intervention given full knowledge of the graph. However, in general this strategy requires more interventions than needed. In fact, the number of interventions required by such a strategy can be exponentially larger than the number of interventions required by strategy that directly attempts identify the matching intervention, as illustrated in Figure I and proven in Theorem 2.
In this work, consider active intervention designs, where series of interventions chosen adaptively to learn the matching intervention. This means that the information obtained after performing each intervention is taken into account for future choices of interventions. We here focus on the noiseless setting, where for each intervention enough data is obtained to decide the effect of each intervention. Direct implications for the noisy setting are discussed in Appendix G. To incorporate realistic cases in which the system cannot withstand an intervention with too many target
To lighten notation, / denote both the perturbation targets and the shift values of this intervention.
3

---

variables, as is the case in CRISPR experiments, where knocking out too many genes at once often kills the cell, we consider the setting where there is sparsity constraint S on the maximum number of perturbation targets in each intervention, i.e., we only allow where [ s S.
3 Identifiability
In this section, we characterize and provide a graphical representation of the shift interventional Markov equivalence class (shift-I-MEC), i.e., the equivalence class of DAGs that is identifiable by shift interventions I. We also introduce mean interventional faithfulness, an assumption that guaran- tees identifiability of the underlying DAG up to its shift-I-MEC. Proofs given in Appendix C.
3.1 Shift-interventional Markov Equivalence Class
For any DAG with nodes [p]. a distribution f is Markov with respect to G it factorizes according to f(X) [Tee [XX, (t)) Two DAGs Markov equivalent in the same Markov equivalence class (MEC) if any positive distribution f which is Markov with respect to (w.r.t) one DAG is also Markov w.r.t. the other DAG. With observational data, DAG is only identifiable up its MEC (Andersson al., 1997). However, the identifiability improves smaller class of DAGs with interventions. For a set of interventions I (not necessarily shift interventions), the pair (f, (ff))ez) is I-Markov w.r.t. 9 if Markov w.r.t. 9 and f factorizes according to
(x) II f(X, pm, (1)) (Xil(X)XX)))) VI
SET
Similarly, the interventional Markov equivalence class (I-MEC) of DAG can be defined, and Yang et al. (2018) provided structural characterization of the I-MEC for general interventions I (not necessarily shift interventions).
Following, we show that if Z consists of shift interventions, then the I-MEC becomes smaller, i.e., identifiability of the causal DAG is improved. The proof utilizes Lemma the relationship between conditional probabilities. For this, denote by ang (i) the ancestors of node i, i.e., all nodes j for which there directed path from if aig(i) n = Ø. A subset I' C I is a source w.r.t. if every node in I' is a source w.r.t. 1.
in G. For subset of nodes we say that E is source w.r.t.
Lemma 2. For any distribution f that factorizes according to G, the interventional distribution f for shift intervention I with shift values {as}ies satisfies
(x,(X,, = By((.) + di.
for any source E 1. Furthermore, if E 1 is not a source w.r.t 1, then there exists positive distribution f such that E, (X:) + 1 (X:) + az
Hence, we can define the shift-I-Marke property and shift-interrenntioal Markov equivalence class (shift-I-MEC) as follows.
Definition 1. For a set of shift interventions the pair (f, (f,ff')Ez)) is shift-Z-Markov w.r.t. if (f, (f, is I-Markov w.r.t. G and
(X,) = Ey(X,)+
ViEle ang(1) n nI Ø.
Two DAGs are in the same shift-I-MEC if any positive distribution that shift-I --Mrkoo- w.r.t. one DAG is Shift-I-Marke also w.r.f. the other DAG.
The following graphical characterizations are known: Two DAGs are in the same MEC and only if they share the same skeleton (adjacencies) and v-structures (induced subgraphs i - <- k), see Verma and Pearl (1991). For general interventions I, two DAGS are the same I-MEC, they are in the same MEC and they have the same directed edges {i + již E I.j I, I, - where i i means that either + j or j + (Hauser and Bühlmann, 2012: Yang et al., 2018). In the following theorem, provide graphical criterion for two DAGs to be in the same Shift-T-MEC.
Theorem 1. Let I be set of shift interventions. Then two DAGs G1 and G2 belong to the same shift-IMEEC if and only if they have the same skeleton, v-structures, directed edges (i Jli E T.j g 1.1 E I, j}. well source nodes of for every 1 E I.

---

(c)
(d)
Figure 2:
Three types of essential graphs. (a). DAG G; (b). EG of g: (c), I-EG of g where
contains one intervention with perturbation targets X1, X2 (purple); (d), shift-Z-EG of g, which can identify an additional edge compared to Z-EG (red).
In other words, DAGs are in the same shift-I-MEC if and only if they in the same I-MEC and they have the same source perturbation targets. Figure shows an example; in particular, to represent the essential graph (EG), which has the same skeleton any DAG in this class and
an MEC, directed edges i - j i + j for every DAG in this class. The essential graphs corresponding to the MEC, I-MEC and shift-Z-MEC of DAG & are referred to as EG, I-BG and shift-Z-EG of G. respectively. They can be obtained from the aforementioned graphical criteria (along with a set of logical rules known as the Meek rules (Meek, 1995); details Appendix A). Figure 2 shows an example of EG, Z-EG and shift-I-EG of a four-node DAG.
3.2 Mean Interventional Faithfulness
For the causal mean matching problem, the underlying 9 can be identified from shift interventions I up to its shift-Z-MEC. However, we may not need to identify the entire DAG to find the matching intervention /" Lemma implies that if is neither in nor downstream of I* then the mean of X; already matches the desired state, i.e., Ep(X,) = Eo();;; this suggest that these variables may be negligible when learning I* Unfortunately, the reverse not true; one may design "degenerate" settings where variable is in (or downstream of) |" but its marginal mean is also unchanged:
and Ep = 1, that Ep(Xa) Suppose 1" is a shift intervention with perturbation targets (X1, Xa), with a = 1, 02 = -1, and 03 1. Then Ep, (Xx) ie.,, the marginal mean of X3 is unchanged under the intervention.
Example 1. Let X3 X1 + 2X2, with (x(X,)
Such degenerate cases arise when the shift node X, (deemed ( if not shifted) exactly cancels the contributions of shifts on its ancestors. Formally, the following assumption rules out these cases.
Assumption (Mean Interventional Faithfulness). If E [p] satisfies (p(X,) Ex(X.), then i is neither a nor downstream of any perturbation target, i.e., & I", raaan(() n Ø.
This is particularly weak form of faithfulness, which is implied by interventional faithfulness assumptions in prior work (Yang et al., 2018; Squires et al., 2020b; Jaber et al., 2020).
Let T be the collection of nodes i [p) for which Ep(X,, o (xx)) The following lemma shows that under the mean interventional faithfulness assumption we can focus on the subgraph Gr induced by T. since I* C. T' and interventions on Xr do not affect X(piYT.
Lemma 3. If Assumption I holds, then any edge - j with E T and $ T has orientation j + i. Conversely, if Assumption does not hold, then there exists some j. T, of T such that j i.
4 Algorithms
Having shown that shift interventions allow the identification of source perturbation targets and that the mean interventional faithfulness assumption allows reducing the problem to an induced subgraph, we now propose two algorithms to learn the matching intervention. The algorithms actively pick shift intervention I at time f based on the current nhift-interventional essential graph (shift-I,- EG). Without loss of generality and for ease of discussion, we assume that the mean interventional faithfulness assumption holds and we therefore only need to consider Gr. In Appendix D, we show that the faithfulness violations can identified and thus Assumption not necessary for identifying the matching intervention, but additional interventions may be required.
5

---

Figure 3: Learning 1x when the structure is known. Undimmed parts represent the current subgraph with source nodes (in purple). /* (1, 2,,4,35 5] } is solved in three steps. Shift values are omitted. (a). Gr and UT: (b). Gr, and Un, (c). GT, and UT.-
Warm-up: Upstream Search. Consider solving for the matching intervention /* when the structure of Gr is known, i.e., the current shift-Z,-EG is fully directed. Let UT {ili (1) = Ø be the non-empty set of source nodes in T. We make the following key observation.
Observation 1. Up C I", and the shift values are a; = (X,, - ( each i E Ur-
This follows since shifting other variables in T cannot change the mean of nodes in UT. Further, the shifted means of variables in Ur match the desired mean (Lemma 2). Given the resulting intervention Ur, we obtain a new distribution pCr Assuming mean interventional faithfulness on this distribution, we may now remove those variables whose means in p²r already match Q. We then repeat this process on the new set of unmatched source nodes, Ti, to compute the corresponding shift intervention Un, Repeating until we have matched the desired mean for all variables yields I*. We illustrate this procedure in Figure 3.
The idea of upstream search extends to shift-Z,-EG with partially directed or undirected Gr. this case, if node or nodes of GT are identified as source, Observation 1 still holds. Hence, we solve part of 1a with these source nodes and then intervene on them to reduce the unsolved graph size.
Decomposition of Shift Interventional Essential Graphs: decompose the current shift-I,-EGG into undirected components. Hauser and Bühlmann (2014) showed that every interventional essential graph is chain graph with chordal chain components, where the orientations in one chain component do not affect the orientations in other components." By similar argument, graphs, and show that there is at least one chain component with no incoming edges. Let us separate out all of the chain components of shift-I,-Fi with no incoming edges. The following lemma proves that all sources are contained within these components.
In order to find the source nodes, we
obtain analogous decomposition for shift interventional essential
Lemma 4, For any shift-I-EG of G, each chain component has exactly one source node w.r.t. this component. This node is source w.r.f. G if and only if there are no incoming edges to this component.
These results hold when replacing 9 with any induced subgraph of it. Thus, we can find the source nodes in T by finding the source nodes in each of its chain components with no incoming edges.
4.1 Two Approximate Strategies
Following the chain graph decomposition, we now focus on how to find the source node of an undirected connected chordal graph C. If there is sparsity constraint the number of perturbation targets in each shift intervention, then directly intervening on all of the variables node, since by Theorem 1, all DAGs in the shift-I-MEC share the same source node. However, when the maximum number of perturbation targets in an intervention is restricted to S < [C), multiple interventions may be necessary to find the source node.
gives the source
After intervening on nodes, the remaining unoriented part can be decomposed into connected components. In the worst case, the source node of C is in the largest of these connected components. Therefore we seek the set of nodes, within the sparsity constraint, that minimizes the largest connected component size after being removed. This is known as the MinMaxC problem (Lalou et al., 2018), which we show is NP-complete on chordal graphs (Appendix D). We propose two approximate
"The chain components of a chain graph are the undirected connected components after removing all its directed edges, and an undirected graph is chordal if all cycles of length greater than 3 contain chord.

---

Algorithm 1: Active Learning for Causal Mean Matching
Input: Joint distribution P, desired joint distribution Q sparsity constraint S. Initialize | = 2 and I {
2 while p (X) + (x do
let I" = { E lp.. (X,) + (X))) let be the subgraph of shift-I-EG induced by T'
let Ur be the identified source nodes in T;;
while U.- = do
let C be chain component of G with no incoming edges;
select shift intervention I by running CliqueTree(C, S) or Supermodular((..9) perform and append it to Z;
end 10
update 9 and Ur as the outer loop;
12
set 04 = (X;) Epr (X,) for i in Ur;
13
include perturbation targets U. and shift values fasheeu in and perform I";
end
Output: Matching Intervention 1
strategies to solve this problem, one based on the clique tree representation of chordal graphs and the other based on robust supermodular optimization. The overall algorithm with these subroutines is summarized in Algorithm 1. We outline the subroutines here, and give further details in Appendix D.
Clique Tree Strategy. Let C(C) be the of maximal cliques in the chordal graph C. There exists clique tree T(C) with nodes in C(C) and edges satisfying that VC1, C2 C(C). their intersection C1 n C2 is subset of any clique on the unique path between C1, C2 in T(C) (Blair and Peyton, 1993). Thus, deleting a clique which is not a leaf node in the clique tree will break C' into at least two connected components, each corresponding to a subtree in the clique tree. Inspired by the central node algorithm (Greenewald et al., 2019; Squires et al., 2020a), we find the S-constrained central clique of T (C) by iterating through C(C) and returning the clique with no more than S nodes that separates the graph most, i.e., solving MinMaxC when interventions are constrained to be maximal cliques. We denote this approach as CliqueTree.
Supermodular Strategy. Our second approach, denoted Supermodular, optimizes a lower bound of the objective of MinMaxC. Consider the following equivalent formulation of MinMaxC
min max fa(A), |A| S S,
Ve <EVe
where Ve represents the nodes of C and V i E Ve, fi(A) = Ejeve (A) with (i. if and j are the same or connected after removing nodes in A from and gb (A) otherwise.
MinMaxC (1) resembles the problem robust supermodular optimization (Krause et al., 2008).
Unfortunately, fi is not supermodular for chordal graphs (Appendix D). Therefore, we propose to optimize for surrogate of /a defined as fa(A) Ejec (i.(A), where
mi. (Ve. A) (Ve)
i-jj in
(A)
otherwise.
Here m4.(Vo:: is the number of paths without cycles between and in C' (deemed 0 if does not belong to C' and 1 if = j C') and i --j means i is either connected or equal to j. Comparing 9i,J with Pi.j. we see that (A4 is a lower bound of f(A) for MinMaxC, which is tight when C is tree. We show that f. is monotonic supermodular for all (Appendix D). Therefore, consider (2) with f; replaced by f.. which can be solved using the SATURATE algorithm (Krause et al., 2008). Notably, the results returned by Supernodular can be quite different to those returned by CliqueTree since Supermodules ar is not constrained pick maximal clique; see Figure 4.
5 Theoretical Results
In this section we derive a worst-case lower bound on the number of interventions for any algorithm to identify the source node in a chordal graph. Then use this lower bound to show that our
7

---

(3,4)
(,,7,8)
(1,2,3) 3)
(4.5)
(5.6)
(a)
(b)
Figure Picking 2 nodes in an undirected connected chordal graph C. CliqueTree picks (Xa; Xs}. while Supermodular picks the better (X3, Xa). (a). C: (b). Clique tree T(C).
strategies are optimal up to a logarithmic factor. This contrasts with the structure learning strategy. which may require exponentially more interventions than our strategy (Figure 1).
The worst case is with respect to all feasible orientations an essential graph (Hauser and Bühlmann, 2014; Shanmugam et al., 2015), i.e., orientations corresponding to DAGs in the equivalence class. Given a chordal chain component C' of G, let re be the number maximal cliques in C, and me be the size of the largest maximal clique in C. The following lemma provides lower bound depending only on me.
Lemma 5. In the worst case over feasible orientations of C, any algorithm requires at least mm--l shift interventions to identify the source node, under the sparsity constraint S.
9
To give some intuition for this result, consider the case where the largest maximal clique is upstream of all other maximal eliques. Given such an ordering, in the worst case, each intervention rules out only S nodes in this clique (namely, the most downstream ones). Now, we show that our two strategies need at most [log2(re + 1)] 1n shift interventions for the same task.
Lemma 6. In the worst case over feasible orientations of C, both CliqueTree and Supermodular require at most [logg(rc 1)7 ma shift interventions to identify the source node, under the
sparsity constraint S.
By combining Lemma and Lemma 6, which consider subproblems of the causal mean matching problem, obtain bound on the number of shift interventions needed for solving the full causal mean matching problem. Let r be the largest re for all chain components of G:
Theorem 2. Algorithm I requires at most [rog2(r + 1)] times more shift interventions, compared to that required by the optimal strategy, in the worst case over feasible orientations of G.
direct application of this theorem is that, in terms of the number interventions required to solve the causal mean matching problem, our algorithm is optimal in the worst case when 1, i.c., when every chain component is a clique. All proofs are provided in Appendix E.
Experiments
We now evaluate our algorithms in several synthetic settings. 3 Each setting considers particular graph type, number of nodes p in the graph and number of perturbation targets |/|| S in the matching intervention. We generate 100 problem instances each setting. Every problem instance contains DAG with p nodes generated according to the graph type and randomly sampled subset of [T") nodes denoting the perturbation targets in the matching intervention. We consider both, random graphs including Erdös Erdös-Rényi Rényi graphs (Erdōs and Rényi. 1960) and Barabási-Albert graphs (Albert and Barabási, 2002), as well as structured chordal graphs, particular, rooted tree graphs and moralized Erdös-Rényi graphs (Shanmugam et al., 2015). The graph size p in our simulations ranges from to 1000, while the number of perturbation targets ranges from to min(p. 100).
We compare our two subroutines for Algorithm 1, CliqueTree and Supermodular ar, against three carefully constructed baselines. The UpstreamRand baseline follows Algorithm where line is changed to selecting / randomly from without exceeding S, i.c. when there is no identified source
CCode is publicly available at: httppp/p//gggtttt..co..////aaaaa
cow wwww///wwwww///..oooo.o.. causal maw.aaacinmaanaaciinnn.....

---

10
0.00
040
5007 PRENATTIIN
Dlaselite
-115
-420
-020
-02
20
100
30
50
100
10
Perturationn oogees 0921
Parturtationn De gett (96)
Sposity cengtaee 5-0g
(a)
(b)
(c)
Figure 5: Barabási- graphs with 100 nodes. (a), Averaged (100 instances) numbers of extra interventions each algorithm (with sparsity constraint S = 1) requires compared to Oracle, plotted against number of perturbation targets I*: (b). Rates of extra interventions Cl CliqueTree and Supermodula ar (S = 1) required relative to UpstreamRand, plotted against number of perturbation targets in I"; (c). Relative extra rate (17*1 = 50), plotted against sparsity constraint S.
node it randomly samples from the chain component with no incoming edge. This strategy highlights how much benefit is obtained from Cliqui Cliueeree and Supermodular on top of upstream search. The Colorime oiiiing baseline is modified from the coloring- boasengg-baeed policy for structure learning (Shanmugam et al., 2015), previously shown to perform competitively on large graphs (Squires et al., 2020a). first performs structure learning with the Mhooing-bbsse policy, and then uses upstream search with known DAG. We also include an Oracle baseline, which does upstream search with known DAG.
In Figure 5
we present a subset of our results on Barabási-A Albert graphs with 100 nodes; similar behaviors are observed in all other settings and shown in Appendix F. In Figure 5a, we consider problem instances with varying size of [.' Each algorithm is run with sparsity constraint S = 1. We plot the number of extra interventions compared to Oracle, averaged across the 100 problem instances. As expected, Coloring requires the largest number of extra interventions. This finding is consistent among different numbers of perturbation targets, since the same amount of interventions used to learn the structure regardless of I*. As [r*] increases, CliqueTree and Supermodular outperform UpstreamRand. To further investigate this trend, we plot the rate of extra interventions' used by CliqueTree and Supermodular relative to UpstreamRand in Figure 5b. This figure shows that CliqueTree and Supermodulat ar improve upon upstream search by up to 25% as the number of perturbation targets increases. Finally, consider the effect of the sparsity constraint S in Figure 5c with |+| = 50. In line with the discussion Section 4.1, as S increases, the task becomes easier for plain upstream search. However, when the number of perturbation targets is restricted, CliqueTree and Supermodular ar are superior, with Supermodular performing best in most cases.
Discussion
In this work, we introduced the causal mean matching problem, which has important applications in medicine and engineering. We aimed to develop active learning approaches for identifying the matching intervention using shift interventions. Towards this end, we characterized the shift interventional Markov cquivalence class and showed that it is in general more refined than previously defined equivalence classes. We proposed two strategies for learning the matching intervention based on this characterization, and showed that they are optimal up to a logarithmic factor. We reported experimental results on a range of settings to support these theoretical findings.
Limitations and Future Work. This work has various limitations that may be interesting to address in future work. First, distribution. This is an inherent limitation of deterministic shift interventions: as noted by Hyttinen al. (2012), in the linear Gaussian setting. these interventions can only modify the mean of the initial distribution. Thus, matching the entire distribution, or other relevant statistics, will require broader classes of interventions. Assumptions the desired distribution also required rule out possibly non-realizable cases. Second, we have focused on causal DAG models, which assume acyclicity and the absence of latent confounders. In many realistic applications, this could be an overly optimistic assumption, requiring extensions of our results to the cyclic and/or causally insufficient setting.
focus the task of matching a desired mean, rather than entire
'The rate is calculated by (#Strategy wttppp/reeaaiandd////sstrreeeeee where # denotes the number of ex tra interventions compared to Oracle and Strategy be CliqueTree, Supermodulas ar Upstreapne beatrea

---

Finally, throughout the main text, we have focused on the noiseless setting; we briefly discuss the noisy setting in Appendix G, but there is much room for more extensive investigations.
Acknowledgements
C. Squires was partially supported by an NSF Graduate Fellowship. All authors were partially supported by NSF (DMS-1651955)) ONR (N00014-17- 1-2147 and N00014-18-1-2765), the MIT- IBM Watson AI Lab, and Simons Investigator Award to C. Uhler.
References
Agrawal, R., Squires, C.. Yang, K., Shammugam, K., and Uhler, C. (2019). Abed-strategy: Budgeted experimental design for targeted causal structure discovery. The 22nd International Conference on Artificial Intelligence and Statistics, pages 3400-3409, PMLR.
Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47.
Andersson, S. A., Madigan, D., Perlman, M. D., et al. (1997). A characterization of markov equivalence classes for acyclic digraphs. Annals of statistics, 25(2):505-55) -.1.
Badsha, M. Fu, A. Q., et al. (2019). Learning causal biological networks with the principle of mendelian randomization. Frontiers in genetics, 10:460.
Blair, R. and Peyton, B. (1993). An introduction to chordal graphs and clique trees. Graph theory and sparse malrix computation, pages 1-29. Springer.
Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. In Foundations and Trends Machine Learning, pages 1-122.
Cahan, P., Li, H., Morris, S. A., Da Rocha, E. L., Daley, G. Q., and Collins, J. J. (2014). Cellnet: network biology applied to stem cell engineering, Cell, 158(4):903-915.
de Kroon, A. A., Belgrave, D., and Mooij, J. M. (2020). Causal discovery for causal bandits utilizing separating sets. arXiv preprint arXivv2009.07916.
Dominguez, A. A., Lim, W. A., and Qi, L. S. (2016). Beyond editing: repurposing crispr-cas9 for precision genome regulation and interrogation. Nature reviews Molecular cell biology, 17(1):5.
D' Alessio, A. C., Fan, Z. P., Wert, K. J., Baranov, P., Cohen, M. A., Saini, J. S., Cohick, E., Charniga, C., Dadon, D., Hannett, N. M., et al. (2015). A systematic approach to identify candidate transcription factors that control cell identity. Stem cell reports, 5(5):763-775.
Erdós, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60.
Friedman, N., Linial, M., Nachman, I., and Pe'er, er, D. (2000). Using bayesian networks to analyze expression data. Journal of computational biology, 703-4):601-620.
Ghassami, A., Salehkaleybar, S., Kiyavash, N., and Bareinboim, E. (2018). Budgeted experiment design for causal structure learning. In International Conference on Machine Learning, pages PMLR.
Greenewald, K., Katz, D., Shanmugam, K., Magliacane, S., Kocaoglu, M., Boix Adsera, E., and Bresler, G. (2019). Sample efficient active learning of causal trees. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Hauser, and Bühlmann, (2012). Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13(1):2409-2464.
Hauser, A. and Bühlmann, (2014). Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 52(4)9926-93.
10

---

He, Y.-B. and Geng, Z. (2008), Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov):2523-2544 2547.
Hyttinen, A., Eberhardt, F., and Hoyer, O. (2012). Learning linear cyclic causal models with latent variables. The Journal of Machine Learning Research, (3(1):33773343)
Hyttinen, A., Eberhardt, F., and Hoyer, P. O. (2013). Experiment selection for causal discovery. Journal of Machine Learning Research, 14:3041-3071.
Jaber, A., Kocaoglu, M., Shanmugam, K., and Bareinboim, E. (2020). Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in Neural Information Processing Systems, 33.
Kocaoglu, M., Dimakis, A., and Vishwanath, S. (2017). Cost-optimal learning of causal graphs. In International Conference on Machine Learning, pages 1875-1884. PMLR.
Koller, D. and Friedman, N. (2009). Probabilistic graphical models: principles and techniques. MIT press.
Krause, A., McMahan, H. B., Guestrin, C., and Gupta, A. (2008). Robust submodular observation selection. Journal of Machine Learning Research, 9(12).
Lalou, M., Tahraoui, M. A., and Kheddouci, H. (2018). The critical node detection problem in networks: survey. Computer Science Review, 28:92-117.
Lattimore, F., Lattimore, T., and Reid, M. D. (2016). Causal bandits: Learning good interventions via causal inference. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc.
Lee, and Bareinboim, E. (2018). Structural causal bandits: where to intervene? Advances in Neural Information Processing Systems 31, 31.
Meek, C. (1995). Causal inference and causal explanation with background knowledge. In Proceed- ings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI'95, page 403-410, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
Rackham, O. J., Firas, J., Fang, H., Oates, M. E., Holmes, M. L.,, Knaupp. A. S., Suzuki, H., Nefzger, C. M., Daub, C. O., Shin, J. W., al. (2016). predictive computational framework for direct reprogramming between human cell types. Nature genetics, 48(3):331.
Rothenhäusler, D., Heinze, C., Peters, and Meinshausen, N. (2015). Backshift: Learning causal cyclic graphs from unknown shift interventions. In Advances Neural Information Processing Systems, volume 28. Curran Associates, Inc.
Shanmugam, K., Kocaoglu, M., Dimakis, A. G., and Vishwanath, S. (2015). Learning causal graphs with small interventions. In Advances in Neural Information Processing Systems, volume 28.
Curran Associates, Inc.
Spirtes, P., Glymour, C. N., Scheines, R., and Heckerman, D. (2000). Causation, prediction, and search. MIT press.
Squires, C., Magliacane, S., Greenewald, K., Katz, D., Kocaoglu, M., and Shanmugam, K. (2020a). Active structure learning of causal dags via directed clique trees. In Advances in Neural Information Processing Systems, volume 33, pages 21500-21511. Curran Associates, Inc.
Squires, C., Wang, Y., and Uhler, C. (2020b). Permutation- causal structure learning with unknown intervention targets. In Conference Uncertainty in Artificial Intelligence, pages 1039-1048, PMLR.
Touchette, H. and Lloyd, S. (2004). Information--thorree approach to the study of control systems. Physica A: Statistical Mechanics and its Applications, 33 331(112):140-172
Triantafillou, S., Lagani, V., Heinze-Deml, C., Schmidt, A., Tegner, J., and Tsamardinos, I. (2017). Predicting causal relationships from biological data: Applying automated causal discovery on mass cytometry data of human immune cells. Scientific reports, 7(1):1111.
11

---

Verma, T. and Pearl, J. (1991). Equivalence and synthesis of causal models. UCLA, Computer Science Department.
Vierbuchen, T., Ostermeier, A., Pang, Z. P., Kokubu, Y., Südhof, T. C., and Wernig, M. (2010). Direct conversion of fibroblasts to functional neurons by defined factors. Nature, 463(72844:1035--044
Wodo, O., Zola, J., Pokuri, B. S. S., Du, P., and Ganapathysubramanian, B. (2015). Automated, high throughput exploration of process- structure- -rrupture-roppety relationships using the mapreduce paradigm. Materials discovery, 1:21-28.
Yabe, A., Hatano, D., Sumita, H., Ito, S., Kakimura, N., Fukunaga, and Kawarabayashi, K.-i. (2018). Causal bandits with propagating inference. In International Conference on Machine Learning, pages 5512-5520. PMLR.
Yang, K., Katcoff, A., and Uhler, C. (2018). Characterizing and learning equivalence classes of causal dags under interventions. In International Conference on Machine Learning, pages PMLR.
12


Reviews:
[{"review_id": "yeD4ew9YBz", "reviewer": "Reviewer_6sir", "summary": "This paper studies shift interventions, where interventions are performed by biasing the respective nodes. It is shown that to move a system to the desired state, it is sufficient to know the topological ordering of the causal graph. Active learning strategies are proposed for transforming the current state of a system to a desired state in as few interventions as possible. Worst case bounds are provided and compared to lower bounds.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The use of shift interventions is well motivated by biological applications, and the results seem correct, with versions of MEC and faithfulness well defined. I have some remaining questions however. \n\nIt is stated that \"our strategies may require exponentially fewer interventions than the previously considered approaches, which optimize for structure learning in the underlying causal graph.\" However this seems to be shown only for baselines which are not adaptive. In fact, the structure learning approach of Squires et al, on which the central node approach is heavily based, seems to succeed in learning the structure of the entire graph in the same order of interventions (at least when S=1). It is therefore not yet clear to me the advantage of using the direct active approaches here as opposed to simply doing (active) structure learning followed by upstream search. I hope the authors can clarify this point, and perhaps include something like this as a baseline in the experiments.\n\nMinor: Lemma 1 seems to be limited given in general it will require all nodes to be intervened on. Since sparsity is emphasized in all the following results, Lemma 1 should be accompanied by a comment to this effect. Also, I am not sure why the desired mean is listed as E_Q(X), I would have expected something like \\mu_Q.\n\nREVISION: The authors addressed my concerns. \n \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "unknown"}, "extra_text": {}}, {"review_id": "pn2PsPk5fBt", "reviewer": "Reviewer_1Wz1", "summary": "This submission considers the problem of choosing a set of continuous shift interventions to match a desired mean when causal graph structure is unknown. The authors present theoretical results relating shift interventional Markov equivalence classes standard Markov equivalence classes, and use this theory to develop a new online algorithm for causal graph structure learning. They present synthetic experiments demonstrating that the proposed methods require few interventions relative to other structure learning baselines.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Overall the paper is well-written, significant, and appears to be technically sound. This submission does an excellent job of presenting the motivation, the intuition, and the technical detail in the condensed format of a conference paper.\n\nDespite its strengths, I am concerned that the paper proposes a method and evaluates that method in a way that is misaligned with the submission's primary motivation. Specifically, the submission motivates the method by claiming that full graph structure learning is unnecessary because we are only interested in achieving a particular state. If achieving a particular state is the objective, why then should we attempt to learn the graph structure at all? In the related works the submission cites Lattimore et al., 2016 as motivation for taking an explicitly causal approach, but Lattimore et al. rely on a priori knowledge of the causal structure. \n\nOne way of addressing this concern could be to expand the empirical evaluation to include; (i) evaluation metrics about the mean discrepancy various algorithms are able to achieve with a fixed computation budget, and (ii) additional strong baselines that avoid structure learning altogether. I would also strongly recommend adding some non-synthetic evaluations if possible, although I know this difficult for causal structure learning.\n\nWhile I am currently recommending against acceptance on the basis of these critiques, I would be willing to change that recommendation if they can be addressed.\n\nMinor comments:\nThe submission appears to describe causal structure learning and causal inference as synonyms, whereas there are many other tasks within the umbrella of causal inference and causality. For example, in the related works section I would recommend saying \"previous work in experimental design in causal graph structure learning\" rather than \"previous work in experimental design in causality\", as this submission does not consider the broad literature on experimental design in social sciences, economics, etc.\n\nUpdate: The authors have sufficiently addressed my concerns and I have updated my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have addressed the limitations and societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "40hjIAvW_qz", "reviewer": "Reviewer_Ga8v", "summary": "This paper considers the problem of identifying a shift intervention to match a given joint distribution of a causal model to a desired joint distribution at the expectation level. It defines the causal mean matching criteria, shows the existence of shift interventions for matching the desired means, and characterizes the shift-interventional Markov equivalence class (shift-I-MEC), which is a more refined subclass of interventional MEC (I-MEC). This refinement is due to the interventions being a certain type of soft interventions, that is the shift interventions.\n\nFollowing a chain graph decomposition of the interventional essential graph, clique tree and supermodular optimization approaches are proposed for active learning of the matching intervention for causal mean matching. A lower bound for the number of shift-interventions and upper bound for the proposed algorithms are provided. Importantly, the upper bound is a logarithmic factor of the lower bound. Proposed approach is compared to random search and structure learning based baselines in simulations with synthetic data.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This work considers an interesting problem, causal matching, and provides analysis for various aspects of it, such as its graphical characterization, active learning algorithms and bounds for the number of interventions.\n\nStrengths:\n-\tThe task of causal matching itself which is to transform joint distribution of a causal model to a desired joint distribution is interesting (though not well motivated, see weaknesses below). Using the related literature on active interventions would require full identification of the underlying DAG. It is emphasized that matching only the means can be done with significantly smaller number of interventions, and this is the difference from previous works. \n-\tIdentifiability in terms of Markov equivalence classes (MEC) is well discussed. Graphical characterization of the proposed shift-interventional (shift-I) MEC, and its refinement over the general interventional MEC is given clearly. Assumptions are reasonable within the given setting.\n-\tExtending the decomposition of intervention essential graphs to shift interventional essential graphs is sound.  Both of the proposed approaches for solving the problem, clique tree and supermodular strategies are reasonable. Use of a lower bound surrogate function to enable supermodularity is clever.\n-\tThe paper is organized clearly, and the theoretical claims are well supported.\n\n\nWeaknesses: I have several concerns on the importance of the proposed settings and usefulness of the results.\n-\tAlthough the causal matching problem seems interesting and new, it is not well motivated. To the reviewer’s knowledge, interventions on a causal model are tied to inferring the underlying structure (it does not need to be the whole structure of the model). In this regard, it is not clear how exactly matching the means of a causal system is preferable to performing more relaxed cases of soft interventions. The authors are encouraged to further explain how this setting can be beneficial. \n-\tDeterministic shift interventions are useful to test the applicability of the proposed ideas. However, restricting the problem setting to only shift interventions is quite limited and leads to some rather trivial results. For instance, existence and uniqueness results of matching shift-intervention in Lemma 1, and the properties of source nodes in Lemma 2 are immediate observations in a DAG. \n-\tClique tree approximation is just a minor modification of the cited central node algorithm (Greenewald et al., 2019). \n-\tComplexity of the submodularity approach subroutine uses SATURATE algorithm (Krause et al., 2008), and is said to scale with $N^5$ in appendix D.4. It is worth commenting on the feasibility of this approach. For instance, what are the runtimes of the simulations for large models in Section 6?\n-\tIt is a nice result that the number of proposed interventions is only a logarithmic factor of the lower bound. However, the baselines in the simulations are not very strong to demonstrate the usefulness. Though coloring approach of Shanmugam et al., 2015 is a related active intervention design, the goal of it is broader than finding a matching intervention. For instance, a simple random upstream search, the other baseline, performs much better than coloring due to the simpler objective. That being said, the reviewer understands that the proposed task is new and fair comparisons may not be easy. \n\nAlthough this paper has several nice properties, the overall contribution, constraints on the problem, and the importance of the results are not adequate for publication at NeurIPS.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Main limitations of the work, which are also stated in the above review, and potential impact of the work, which is not very imminent, are adequately addressed in the discussion section.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "-rj2E0G83PN", "reviewer": "Reviewer_qTtP", "summary": "This paper focuses on the problem of identifying shift interventions that match the desired mean of a system by active learning. It provides both theoretical guarantees that there always exists a unique shift intervention, as well as practical algorithms. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Overall, the paper is well-written, and to the best of my knowledge, the studied problem is novel. The paper gives interesting theoretical results that there exists a unique intervention to match the desired mean.\n\nHowever, the assumptions seem rather restrictive, which usually do not hold in practical scenarios.  For example, the authors assume the noiseless setting (Line 121) and only match the mean of the desired distribution.  \n\nUpdate:\n\nThanks for the response. I hope the restrictions can be relaxed in a further version.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of transforming a causal system from a given initial state to a desired target state using a set of continuous shift interventions to match a desired mean when causal graph structure is unknown. The authors provide active learning strategies to choose interventions that guarantee to exactly match a desired mean. .

Post rebuttal, the reviewers seem to be on the positive side and there is some consensus to accept the paper. The paper provides an interesting contribution and the fact that on some for certain problems, compared to state of art the proposed method requires exponentially fewer interventions is interesting. There is some concern about the restrictiveness of the assumption made by the authors. But none the less, I am inclined to accept the paper.
Decision: Accept (Poster)