Balancing Interference and Correlation in Spatial Experimental Designs: A Causal Graph Cut Approach
Authors: Jin Zhu
Jingyi Li
Hongyi Zhou
Yinan Lin
Zhenhua Lin
Chengchun Shi
Venue: ICML 2025 poster (2025)
Keywords: policy evaluation
AB testing
Graph cut
Spatial interference
Spatial correlation
Primary area: general_machine_learning->causality
TL;DR: Causal graph cut is all you need for cluster-randomized experimental designs

Abstract: This paper focuses on the design of spatial experiments to optimize the amount of information derived from the experimental data and enhance the accuracy of the resulting causal effect estimator. We propose a surrogate function for the mean squared error (MSE) of the estimator, which facilitates the use of classical graph cut algorithms to learn the optimal design. Our proposal offers three key advances: (1) it accommodates moderate to large spatial interference effects; (2) it adapts to different spatial covariance functions; (3) it is computationally efficient.  Theoretical results and numerical experiments based on synthetic environments and a dispatch simulator that models a city-scale ridesharing market, further validate the effectiveness of our design. A python implementation of our method is available at https://github.com/Mamba413/CausalGraphCut.

Balancing Interference and Correlation in Spatial Experimental Designs: A Causal Graph Cut Approach
Jin Zhu" "1
Jingyi Li Hongyi Zhou?
Yinan Lin
Zhenhua Lin
Chengehun Shi
Abstract
interventions applied to experimental unit may influ- ence others, leading to the violation of the fundamental stable unit treatment value assumption (SUTVA) for causal inference (Imbens & Rubin, 2015); (ii) the strong outcome correlations among units, which increase the variance of the causal effect estimator. We present the following ex- amples to illustrate.
This paper focuses on the design spatial ex- periments to optimize the amount of informa- tion derived from the experimental data and en- hance the accuracy of the resulting causal ef- feet estimator. We propose a surrogate func- tion for the mean squared error (MSE) of the estimator, which facilitates the use of classical graph cut algorithms to learn the optimal de- sign. Our proposal offers three key advances: (I) it accommodates moderate to large spatial in- terference effects; (2) it adapts to different spa- tial covariance functions; (3) it is computation- ally efficient. Theoretical results and numeri- cal experiments based on synthetic environments and a dispatch simulator that models a city-scale ridesharing market, further validate the effective- ness of our design. A python implementation of our method available at https: //gittgttb/u////// Baam/Mama-ee 4 1 Cww.aaaaaaaaaaaaaaaa
Example 1: A/B testing in marketplaces. A/B testing is frequently used in two-sided markets such as Uber. Lyft, Airbnb and eBay to assess the impact of a newly devel- oped product relative to a standard control. It has become the gold standard for companies in conducting data-driven decision making (Johari et al., 2022). Spatial interference is ubiquitous in marketplaces. For instance, ridesharing companies constantly offer subsidizing policies to drivers or passengers across different regions in a city. Applying a subsidizing policy in one location can attract drivers from neighboring regions to this area, potentially decreasing the driver supply other regions. Thus, subsidizing policy in one location can affect outcomes other locations, induc- ing interference over space (Shi al., 2023a). Meanwhile, market features like online driver numbers and call order numbers form interconnected spatial networks, leading to considerable spatial correlation (Luo et al., 2024).
1. Introduction
Background. Before deploying any policy in practice, it is essential to evaluate its impact. This renders randomized control trials or online experiments extensively used for ac- curate policy evaluation. In numerous applications, the ex- periments involve multiple units that are either distributed across different spatial regions or connected through net- work. The spatial or network dependencies inherent in these experiments pose two unique challenges for policy evaluation: (i) the existence of interference effects where
Example 2: Environmental and epidemiological appli- cations. Environmental and epidemiological studies fre- quently utilize spatial data examine causal effects of certain interventions on health outcomes in different geo- graphical regions (Reich et al., 2021). Spatial correlation and interference are likely to arise in these applications. For instance, in evaluating the impact of vaccination cam- paigns on disease incidence, infection rates exhibit strong correlations within regions. Furthermore, the vaccination coverage in given region not only influences its own in- fection rate but also those in the neighboring regions ( (Van- derWeele et al., 2012; Peyez-Heydrich et al., 2014).
"gqual contribution 'Deaarmennt of Statistics, London School of Economics and Political Science, London, United Kingdom 'Department Statistics and Data Science, National University of Singapore, Singapore 'Department of Mathematics, Tsinghua University. Beijing, China 'National Center for Applied Mathe- matics in Chongqing, Chongqing Normal University, Chongging, China. Correspondence to: Zhenhua Lin <linz edu.sg>, Chengchun Shi <cc.shi7 @ ac.k..c.uk>.
Example 3: Experimentation in social networks. So- cial network sites such as Facebook and LinkedIn exten- sively conduct online experiments to evaluate user engage- ment or satisfaction from a new service or feature. In these experiments, the treatment applied to given user may spill over to other users via underlying social connections
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(ss.

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
(like friends), leading network interference. Addition- ally, since connected users often exhibit similar behaviors, their outcomes are likely correlated (Gui et al., 2015).
1.1. Related works
This section reviews related works on spatial causal infer- ence, experimental design and off-policy evaluation.
Contributions. This paper primarily focuses on the first application, aiming to identify the optimal design that min- imizes the mean squared error (MSE) of the resulting av- erage treatment effect (ATE) estimator. Nonetheless, the theories and methods developed herein can be adapted to the other two examples.
Spatial causal inference. Our proposal is closely related to growing line of research on causal inference in the pres- ence of spatial interference. Depending on the underlying assumptions, the methodologies developed within this area can be broadly grouped into three categories:
Methodologically, our contribution lies in the develop- ment of a causal graph cut algorithm for designing exper- iments with spatial interference and correlation. The ad- vances of our algorithm are summarized as follows:
1.
The first category assumes partial interference where units are partitioned into clusters and interference is re- stricted to within these clusters, not between them (Hal- loran & Struchiner, 1995; Sobel, 2006; Hudgens & Hal- loran, 2008; Tehetgen & VanderWeele, 2012; Crépon et al., 2013; Liu et al., 2016; Zigler & Papadogeorgou, 2021).
Flexibility: Our proposal is more flexible than exist- ing works that assume weak interference (Viviano et al., 2023). It accomnodates moderate to large interference effects.
2. The second category assumes neighborhood interfer- ence where interference is limited to a unit's neigh- bors or predefined local region (Verbitsky-Save Savitz & Raudenbush, 2012; Bhattacharya al., 2020; Fatemi & Zheleva, 2020; Ma & Tresp, 2021; Gao & Ding, 2023; Dai et al., 2024; Jiang et al., 2024; Yang et al., 2024).
Adaptivity: Instead of employing existing minimax approaches (Leung, 2022; Viviano et al., 2023; Zhao, 2024b) that minimize the same worst-case MSE across applications with different covariance structures and can be overly conservative, our algorithm adapts to differ- ent correlation structures, providing a tailored solution to each individual application.
3. The last category considers more general interference structures (Aronow & Samii, 2017; Forastiere et al., 2021; Puelz et al., 2022; Song & Papadogeorgou, 2024; Zhang et al., 2024; Zhan et al., 2024).
The design problem requires allocating treatment for each region and is inherently NP- hard, as the number of treatment allocation rules grows exponentially fast with respect to the number of regions. Unlike existing solutions that rely on computationally in- tensive integer programming (Zhao, 2024b), we propose a new surrogate function for the MSE, which enables the use of spectral clustering- bused graph cut algorithms for minimization, thus substantially enhancing computa- tional efficiency.
Computational efficiency:
In the machine learning literature, spatial causal inference is also related to recent advances on bandits with interfer- ence (Jia et al., 2024; Agarwal et al., 2024; Xu et al., 2024). However, despite the development of various methods to handle interference, experimental designs have been less considered in these papers.
Theoretically, our analysis reveals that the two pivotal fac- tors - inttrfeerene and correlation -antttion-dee drive the optimal de- sign in opposite directions. Specifically, experiments with large interference effects are best designed by assigning same policies to neighboring regions whereas those with strong spatial correlations benefit from allocating different policies. By incorporating the effects of the two factors into our surrogate function, the proposed algorithm effectively address both challenges, achieving desirable properties.
Experimental design under interference. The design of experiments is a classical problem in statistics, motivated by applications ranging from biology and agricultrre to psychology and engineering (Fisher et al., 1966). Recently, it has gained considerable attention in the field of machine learning (see e.g., Foster et al., 2021; Blau et al., 2022; Weltz et al., 2023; Fiez et al., 2024; Kato et al., 2024).
Our paper contributes to a growing line of research focus- ing on identifying optimal treatment assignment strategies in the presence of interference. Several designs have been proposed to guide treatment allocation in settings with in- terference over time (Hanna et al., 2017; Hu & Wager, 2022; Zhong et al., 2022; Bojinov et al., 2023; Li et al., 2023; Xiong et al., 2024; Sun et al., 2024: Wen et al., 2025) or among entities in marketplaces (Wager & Xu, 2019; Jo- hari et al., 2020; Bajari et al., 2021; Munro et al., 2021: Li et al., 2022; Zhu et al., 2024).
Empirically, based on synthetic environments and city- level simulator constructed using physical models and real dataset from a ridesharing company to realistically simulate driver and passenger behaviors, we demonstrate the superior performance of our design compared to exist- ing state-of-the-as methods. Notably, in the simulator, the proposed ATE estimator achieves an MSE that is 3.5 times smaller than those of the benchmark approaches.
2

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
This work studies designs under spatial or network inter- ference. Methodologies developed within this field can be
2021; Chen & Qi, 2022; Shi al., 2022; Bian et al., 2024).
broadly categorized into three types:
2. Importance sampling (IS) method reweights the ob- served reward using IS ratios to address the distribu- tional shift between target and behavior policies (Heck- man et al., 1998; Zhao et al., 2012: Swaminathan & Joachims, 2015; Thomas et al., 2015; Liu et al., 2018;
1. The first type of methods adopts the principle of bal- ance in the design of experiments. These methods fo- cus on balancing covariates (Kallus, 2018; Liu et al., 2024; Harshaw et al., 2024) and cluster sizes in cluster- randomized designs (Gui et al., 2015; Saveski et al., 2017; Rolnick et al., 2019).
Dai et al., 2020; Luckett et al., 2020; Kuzborskij al., 2021; Wang et al., 2023; Hu & Wager, 2023; Zhou et al., 2025).
2. The second type of methods analytically calculates the MSE of the ATE estimator and uses either to heuris- tically guide the design of cluster-randomized experi- ments (Ugander et al., 2013) or determine the opti- mal number of clusters by minimizing the MSE's order of magnitude (Leung, 2022; Jia et al., 2023).
3. Doubly robust (DR) method and its variant combine the direct and IS estimators to achieve more accurate and robust estimation (Tan, 2010; Dudík et al., 2011; Zhang et al., 2012; 2013; Jiang & Li, 2016; Thomas & Brun- skill, 2016; Chernozhukov et al., 2018; Liu et al., 2019; Chernozhukov et al., 2022; Shi et al., 2021; Kallus & Uchara, 2022; Liao et al., 2022; Xu et al., 2023; Shi et al., 2024).
3. The last type of methods identifies the optimal de- sign through an optimization perspective (Zhao, 2024a). They apply optimization tools to directly minimize the MSE of the treatment effect estimator or its proxy (Baird et al., 2018; Ni et al., 2023; Jiang & Wang, 2023; Vi- viano et al., 2023; Chen et al., 2024). In particular, Viviano et al. (2023) markedly advanced the design of cluster-randomizee experiments under network interfer- ence by proposing a causal clustering algorithm, which offers a rigorous framework to numerically solve the optimal design via graph clustering algorithms. Subse- quent developments are explored in several recent stud- ies (see e.g., Eichhorn et al., 2024; Zhao, 2024b).
Moreover, there is a growing line of research that proposes to adapt OPE methodologies to A/B testing (see e.g., Farias et al., 2022; Shi et al., 2023b). However, none of these aforementioned studies address interference or focus on ex- perimental design. While works such as Wan et al. (2022), Hanna al. (2017) and Liu & Zhang (2024) consider the design problem to optimize the efficiency of the OPE esti- mator, they do not address spatial/network interference ei- ther.
2. Preliminaries
Our paper falls into the third category: it utilizes classical graph cut algorithms for optimization. Unlike Viviano et al. (2023) that employs a minimax formulation along with a weak interference assumption simplify the MSE- po- tentially at the cost of being conservative and restrictive our proposed algorithm does not rely on minimax formula- tions or limit itself to weak interference. Despite the more complicated form of the MSE, we identify a suitable surro- gate to optimize, backed by theoretical guarantees. Empir- ically, our proposal substantially outperforms both causal clustering and other state-of-the-art in our application.
In this section, we first formulate the A/B testing problem in spatial experiments, presenting our model and assump- tions. We next detail the ATE estimator. Finally, we in- troduce cluster-randomized designs, which are extensively used in the field (see e.g., Ugander et al., 2013; Karrer et al., 2021; Leung, 2022).
Spatial A/B testing. We consider a spatial setting with non-overlapping regions across a city. The goal of spatial A/B testing is to compare the impact of implementing newly developed policy in the whole city against an exist- ing practice. Its procedure can be summarized as follows:
Off-policy evaluation (OPE). Finally, our work is also closely related to OPE in contextual bandits and reinforce- ment learning. OPE aims to learn the expected return under a target policy using an offline dataset collected from a pos- sibly different behavior policy. There are three commonly- used OPE methods:
At the beginning of the experiment, we observe a covari- ate matrix O = (O1. OR) E R Rxd where each vector O E Rd measures certain market features from the ith region. For instance, in ridesharing, O, could rep- resent the number of initial drivers within that region.
1. Direct method derives the policy value estimator by learning a value function that measures the (cumulative) reward under the target policy (Hahn, 1998; Le et al., 2019; Feng et al., 2020; Luckett et al., 2020; Hao et al.,
During the experiment, the decision maker assigns poli- cies by specifying a vector A = A AR) where each A, is a binary variable indicating whether the i-th region receives the newly developed policy (A, = 1)
3

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
a standard control policy (A, = 0). In the context of ridesharing, A, could correspond to whether to assign certain driver-side or passenger-side subsidizing policy at the ith region (Shi et al., 2023a; Li et al., 2024).
For any S L S n and sis S R. let (As,, Y.,) denote the poliey-outcome pair associated with the i-th region col- lected from the t-th experiment. Assumption I motivates us to consider the following importance sampling (IS) esti- mator popularly employed in the literature to estimate the ATE (see e.g.. Ugander et al., 2013; Zhao, 2024b),
After the experiment, we collect an outcome vector Y = VV,,..,,YY with each Y; measuring the i-th region's 's outcome of interest (such as the total driver income). Throughout this paper, we assume Y; = gi (A, 0) + e for some unknown function 9r and mean- zero error e, in- dependent of O and A.
IS ATE
N
R
(1,
To,(O) Yi,
(TT,
[[T,,((O))
t=1
where Ti,(a) = II T(Agr az) so that (1) (or JEN,
Finally, the experiment is repeated N times, resulting in N independent (O, A, Y) triplets. Based on the data, we aim to estimate the ATE, deñned as
(O) indicates whether all neighbors of the i-th region (including itself) are treated with the new policy (or the standard control).
R
ATE = EE(ATT((O) = Σ
A well-known limitation of IS estimators is its large vari- ance (Dudík et al., 1). To mitigate this issue, we employ the following doubly robust (DR) estimator developed by Yang et al. (2024) for ATE estimation. DR attains theoreti- cally no larger and empirically often smaller MSE than IS, and is defined as
which measures the difference in outcome between ap- plying the new policy globally to all regions and imple- menting the control policy. Here, CATE denotes the con- ditional ATE as a function of the observation matrix.
We make two remarks. First, unlike existing works on the design of spatial/network experiments (see Section 1.1) which analyze data from a single experiment without re- peated measures, consider settings with repeated mea- surements (Zhang & Wang, 2024). This is motivated by our ridesharing example where the experiment is conducted over two weeks, and each day's data can be treated as an in- dependent realization since the number of call orders typi- cally wanes between and am (Luo et al., 2024).
DR ATE
1 N
N
R
(1,,(1) - uc,,
(1)
[[a.((a) Yr,, - gi O,)] and O2 denotes the observation matrix from the t-th exper- iment. Notice that Vi,, depends on Is, which is unknown and must be estimated. In practice, estimation of de can be achieved either parametrically, using a specified func- tional form based on lower-dimensions statistics of ac- tions and observations (Hu et al., 2022), or nonparamet- rically through neural networks (Leung & Loupos, 2022; Dai et al., 2024; Wang et al., 2024). Thanks to its dou- ble robustness property and the fact that the randomization probability (a)) is known by design, the resulting es- timator remains unbiased even when the estimated gi is in- consistent. Notably, when the estimated ga is set to zero, the resulting estimator simplifies to IS.
where V2,x(a) = (a, + (a
Second, our outcome regression model Y; = gi(A, (A, 0) + manifests the two challenges in spatial A/B testing:
1. Interference: 9i depends not only on the ith region's own treatment A,, but also on the treatments assigned to other regions as well.
2. Correlation: The covariance matrix of the residual = (c.,... ,en) denoted by Σ E RRR is typi- cally non-diagonal, indicating that residuals are corre- lated across regions.
Design. In our context, each design specifies treatment allocation rule that determines the joint probability distri- bution function of A. Following the existing practice, we focus on the class of cluster-randomized designs in this paper. These designs partition the R regions into m dis- joint clusters C,...., Cm where regions within the same cluster receive the same treatment. Meanwhile, treatments across different clusters are independent, each following a Bernouli distribution with a probability p of receiving the new policy. We further fix p 0.5 throughout the paper to ensure a balanced design, since the optimal design is indeed balanced (Yang et al., 2024).
Estimation. To simplify the estimation under spatial inter- ference, we impose the neighborhood interference assump- tion introduced in Section 1.1, which restricts the interfer- ence to neighboring regions. It a specific yet widely used exposure mapping assumption (Aronow & Samii, 2017).
Assumption (Neighborhood interference). For each re- gion i, denote N₁ as the set of spatial neighboring re- gions for the i-th region, including the i-th region itself.
Let aN, be the [Nr] Ail-diimesioaal subvector of a that is
formed by the treatments assigned to the regions in No. For any i E {1,2,... .R). a. a' E 1] R and o E Rd. gi o) = ga o) whenever aN, = a'y.:
Two special cases are worthwhile to mention: (i) When m 1, there is only one cluster. The resulting design
4

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
designs for the three experiments, with different colors rep- resenting different clusters. It clearly shows that:
(i)
With weakly correlated errors, interference plays the leading role in determining the MSE. Since all regions are connected, according to Claim 1, the optimal alloca- tion rule assigns the same policy to all regions, resulting in a global design.
(8)
Figure I. Illustrations of the optimal casster-randomized designs in three experiments, where different colors represent different clusters. (a) With weakly correlated residuals, the optimal design simplifies the global design. (h) Without interference, the op- timal design reduces to the individual design. (c) With moderate large levels of interference and correlation, the optimal design falls between the two extremes, resulting in a 3-cluster design.
(ii) Without interference effects, correlation becomes the sole factor in determining the MSE. According to Claim 2, the optimal allocation rule assigns different treatments across regions, creating individual design.
(iii) When both interference and correlation present, the optimal design typically falls between the two extremes, resulting in a cluster-randomized design. Specifically. in the right experiment, the proposed algorithm identifies a three-cluster design as the optimal design.
reduced to a global design where all regions receive the same policy during each experiment. (ii) When m R. each region forms single cluster, resulting in an individ- ual design where policies are i.idd across regions.
Our objective lies in determining the optimal cluster- randomized design, for which we propose a causal graph cut algorithm to minimize the MSE of the ATE estimator in (1). Details are provided in the next section.
For any two regions i and i', let Ege denote the covariance between two residuals 6; and egr. Let 8 > 0 represent the size of the spatial correlation so that |امم|] < 5 for any two non-neighboring regions i, 1'. The following two proposi- tions formally summarize the aforementioned findings.
3. Causal Graph Cut
Proposition 1. When 8 is sufficiently small (i.e., spatial correlation is weak among non-neighboring regions), and the covariance Eis between any two neighboring regions i, V' is positive, the global design minimizes the MSE of the DR estimator (1).
This section is organized as follows. Section 3.1 analyzes the roles of spatial interference and correlation in design- ing cluster-randomized experiments. Section 3.2 derives our surrogate function for the MSE of the ATE estimator. Finally, Section 3.3 details our causal graph cut algorithm.
Proposition 2. When SUTVA (i.e., the no-interference as- sumption) holds and all entries of Σ are non-ne non-negative, the individual design minimizes the MSE of the DR estimator.
3.1. Cluster-randomizzd design: the roles of interference and correlation
To verify the two claims and propositions, we offer a de- composition of the DR estimator's s MSE in the following theorem. Recall that N denotes the number of repeated ex- periments. For given cluster let aC denote its boundary. Theorem 1. Under Assumption 1, the DR estimator's MSE under a cluster-randomized design with m clusters {c, is given by
We will show that interference and correlation are the two driving factors determining the MSE of ATE estimators under different designs. Interestingly, they influence the design of experiments in completely different directions:
Claim 1. Experiments with large interference best de- signed by applying same policies to neighboring regions.
Claim 2. Experiments with strong correlation are best de- signed by allocating different policies to different regions.
MSE(ATE DR N
Var (CATE(O.)
Σ
T
Σ
N
3=1 L.'EC
design-agnostic
To illustrate these two claims, we consider three experi- ments visualized in Figure 1, with the same spatial grid. They differ in the sizes of interference effects and correla- tion: (i) In the left experiment, there is moderate to large in- terference, while the residuals .i...., e are weakly corre- lated across regions. (ii) In the middle experiment, SUTVA holds, meaning there is interference, but there is moder- ate to large correlation. (iii) In the right experiment, both levels of interference and correlation range from moderate to large.
spatial correlation (SCC) term
8
ΣΣ Σ j7h SECEE PEDC2
DWI(Win # 00
N
lirst-oreer interference term
m
0
Σ E
N
k,k= d'EDCE
second onder interfenence term
where the event Nop nC, + indicates that the i' -th region is adjacent to the j-th cluster.
Figure further visualizes the optimal cluster-randomized
5

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
3.2. Balancing interference and correlation: new surrogate function for the MSE
In this section, we design surrogate function aimed at achieving the following properties:
(8)
(D)
Property 1 (Flexibility)) The surrogate function shall ac- commodate moderate to large interference effects.
Figure 2. An illustration of each term in the MSE decomposition from Theorem I with m clusters distinguished by different colors. (a) SC captures the residual covariance between any i, r' within the same cluster. (h) I captures the residual covariance between any i, i' that belong to different clusters, with one region lying on the boundary between the two clusters. (c) lz captures residual covariance between any i, E' from different clusters, with both regions located on the boundary.
Property 2 (Adaptivity). The surrogate function shall adapt to different correlation structures.
Property 3 (Computational efficiency). The surrogate function can be optimized efficiently.
Flexibility is crucial, since limiting the methodology to weak interference would be overly restrictive. Addition- ally, computational efficiency essential for the practical implementation of the design. Below, we provide a numer- ical example to highlight the importance of adaptivity.
Theorem decomposes the MSE into four terms. We elab- orate each of them below.
1. The design-agnostic term (DA) accounts for the varia- tion in covariates across N experiments. It is indepen- dent of the design and hence design-agnostic.
A numerical example. Consider a square spatial grid with R = 144 regions visualized in Figure 3(a) and an expo- nential spatial correlation structure: Σgj = -piii for some < p S that characterizes the strength of spatial corre- lation. We numerically compute MSEs of DR estimators under different cluster-randomized designs, each dividing the spatial grid into m equally sized square rectangles (see Figure 3(a) for an example with m = 4). Notice that vary- ing p induces different covariance functions whereas vary- ing m yields different designs. We report the MSE for each combination of p and m in Figure 3(b), where the MSE values on the y-axis are presented using a logarithmic scale for clearer visualization and comparison. These results em- phasize two key motivations, which discuss below.
2. The spatial correlation term (SC) captures the residual covariances between regions within the same cluster, illustrated in Figure 2(a). When the covariance function is non-negative, it becomes evident that minimizing this term is equivalent to assigning different policies to dif- ferent regions, thus demonstrating Claim 2. Notably, it attains the minimum value under the individual design, which in turn proves Proposition
3. The interference terms / and 12 equal zero in the ab- sence of spatial interference. Unlike the SC which cap- tures only within-cluster correlation, both I and I2 ac- count for between-cluster correlation, as illustrated in Figure 2(b) and (c). Under neighborhood interference, the first-order term I requires at least one region to lie on the boundaries between the two clusters, represent- ing a first-order boundary effect. The second-orde term In further requires that both regions be located on the boundary, thus characterizing a second-order boundary effect. For any two neighboring regions, assigning them different policies causes them to belong connected yet different clusters, which creates boundaries. Thus, minimizing these terms is equivalent to assigning the same policy to neighboring regions, which demonstrates Claim 1. Apparently, there is no boundary effect under the global design. This proves Proposition 1.
1. We first note that the MSE varies considerably with cluster size. Notably, when = 0.9, the MSE reaches its minimum value of 20 with 4 clusters, but increases to over 40 under the global design. This highlights the motivation for addressing the design problem itself.
2. We also observe that the optimal cluster size varies with P. This highlights the motivation for developing an adaptive method capable of identifying the optimal de- sign tailored to each individual covariance function.
A new surrogate function. It remains challenging to de- sign a surrogate function for the MSE that satisfies the aforementioned three properties. Under neighborhood in- terference, the primary challenge arises from the presence of the two interference terms 11 and 12 (see Theorem 1), the calculation of which requires specifying cluster bound- aries. Since clusters under different designs have differ- ent boundaries, optimizing these terms becomes an NP- hard combinatorial optimization problem, conflicting with Property 3. One solution is to impose the weak interfer- ence assumption as Viviano et al. (2023), under which
In summary, interference and correlation drive the optimal design in opposite directions. Interference induces estima- tion errors at cluster boundaries. Thus, assigning the same policy to neighboring regions eliminates the boundary ef- feet and minimizes these errors. On the contrary, allocating different policies to different regions effectively negates the positive correlation between their residuals, thus reducing the estimation emror caused by spatial correlation.
6

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
647
3
2
1
(al [b]
[o]
(d)
Figure 4. (a) Spatial layout of 4 regions to be partitioned. (b) Each region is represented
(8)
(b)
vertex, with edges determined by the weight w. (c) The cut highlighted in red minimizes the total loss weight. (d) The spatial layout obtained after applying the 2-cut, illustrating how the regions are partitioned based on the graph cut.
Figure 3. (a) An 12 x 12 grid divided into four square clusters. (b) A scatter plot visualizing the DR estimator's MSE as a function of cluster size. p is selected from 0.3,, 0.5, 0.7, 0.9).
the boundary effect becomes negligible (see their proof of Lemma 3.2). However, this approach violates Property 1.
Proposition 3. Under Assumption 2, the first term in (2) upper bounds 41-
For illustration purposes, we will now focus on designs with two clusters to discuss how we address these chal- lenges and detail our surrogate function. Its more gen- eral form, applicable to general numbers of clusters, is pre- sented in Appendix A. Let C₁ and C2 denote a partition of all R regions, our surrogate function is defined as follows:
Meanwhile, when the covariance function is bounded away from zero, i.e., ming Ear O, the following Proposition shows that this upper bound remains tight in the sense that it is of the same order of magnitude as 11.
Proposition 4. When > O, the first term in (2) is up- per bounded by d I1 where dmax denotes the maximum number of neighbors across regions and a denotes the ratio maxi4e Exe/ /min,,y Ewy
SR N
W
8 N
Σ REC1 S'EC2
Ear,
(2)
REC1 S'EC2
It is also worthwhile to mention that our surrogate function explicitly relies on the covariance function E, allowing the resulting design to be dependent upon E. Alternatively, one could employ a minimax approach similar to Viviano et al. (2023) and Zhao (2024b) that derives a worst-case surrogate among all possible covariance functions. How- ever, the resulting design is no longer adaptive to Σ.
where (War ar f.,=-,..... denotes the binary adjacency ma- trix indicating whether two regions adjacent, and E max(Eur 0). This objective function is built upon Theo- rem 1 and is motivated by the following observations:
1. The DA term does not need to be incorporated in the surrogate, since it is design-agnostic.
In summary, the two terms in (2) measure the effects of in- terference and correlation, respectively. Optimizing these terms drives the resulting designs as described in Claims I and 2. By incorporating both, our surrogate function bal- ances interference and correlation, successfully achieving the first two desired properties. We will discuss how to ef- ficiently optimize this function in the next section.
2. Minimizing the SC term, i.e., the within-cluster covari- ance, is equivalent to maximizing the between-cluster covariance, represented by the second term in (2).
3. Instead of directly minimizing /1. we use a surrogate upper bound given by the first term in (2) that does not involve cluster boundaries and can be more efficiently optimized.
3.3. Causal graph cut: the detailed algorithm
4. Applying a similar upper bound to 12 will result in a quartic objective function, rather than quadratic, render- ing spectral clustering- -ased cut algorithms inapplica- ble. However, as indicated by Figure 2(c), only small fraction of the regions lie the boundary, making I2 high-order and negligible term when compared with I1. This justifies omitting 12 from the objective function.
We focus the case with two clusters to illustrate our al- gorithm. Notice that the surrogate function in (2) is propor- tional to Σiec, Evec, war where wi = RW W. - -Ew can be viewed as the weight between any two regions. As- signing two regions to different clusters results in loss of their weight, and minimizing the surrogate function is equivalent determining the optimal clustering that min- imizes the total lost weight. This formulation allows us to employ classical graph cut algorithms (see e.g., Gold- schmidt & Hochbaum, 1994; Stoer & Wagner, 1997) to optimize our surrogate function, as illustrated in Figure 4.
Proposition 3 below formally establishes that the first term in (2) serves as a valid upper bound for Ii, under the fol- lowing assumption which is automatically satisfied when the covariance function decays with distance - condition commonly imposed in spatial statistics (Cressie, 2015).
Following Hagen & Kahng (1992), let L. represent the Laplacian matrix of = (war Ju, and define the partition vector x such that x, = 1/v/Rifi E C₁ and x; = -1/VR if E C2. A key observation is that the cut loss func-
Assumption 2 (Decaying covariance). For any three dis- joint regions in iz. is such that only i and in are neigh- bors, it holds that E, 2 Eng

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
tion can be represented using the following quadratic form x La/4. Instead of employing integer programming to optimize this quadratic form, we relax the search space to the entire umit ball to facilitate computation. This simplifies the optimization to identifying the eigenvectors of I.. Given that the Laplacian matrix has a trivial eigenvector (a vector of all ones) with an associated eigenvalue of zero, classical graph cut algorithms typically compute the cigenvector as- sociated with the second smallest eigenvalue, known as the Fiedler vector (Fiedler, 1973; 1989).
Algorithm 1 Causal graph cut (CGC)
Input: A batch sample size B and an initial clustering C. 1: for 1 = 1,..... N/B do
2: Implement the design based on C and collect the dataset D(1) = {(Y,, A,, 0z)
3: Use datasets D(1,,.. D()) to estimate 9i (denoted by 9:) and compute Cie = Y₁ - -i (AN.,, ONt,t).
4: Compute the estimated covariance matrix Σ whose
(i, i' ) entry is given by En = EE1 Caert/B.
5: for m = 1,... Maxx do
However, our problem sightly differs from the classical graph cut problem in that the weight matrix is not guar- anteed to be positive definite. Consequently, if the smallest eigenvalue equals zero, we search for the Fiedler vector. Otherwise, we employ the first eigenvector. Once we have obtained the appropriate eigenvector, we apply the k-means algorithm to finalize the partition. In more general set- tings with m > 2 clusters, instead of searching for the first or second eigenvector, we search for a few (i.e., (mg)(m) many), and apply the k-means algorithm to determine the m clusters. By varying m from to a predefined maximum value maxx - set to R2//3 in our implementation based on Leung (2022)'s recommendation we obtain mmma many designs. We next evaluate their performance by plugging each design into the MSE formula derived from Theorem (instead of the surrogate function) and choose the number of clusters that minimizes the MSE. Finally, the aforemen- tioned discussion implicitly assumes that Σ is known; how- ever, in practical applications, direct access to Σ is often not feasible. Since the experiment is repeated N times, we can estimate Σ to construct the MSE estimator and update the design in an iterative manner. We summarize the pro- cedure in Algorithm 1.
6: Use Σ to estimate the MSE and apply graph cut
to learn the optimal design with m clusters.
7: end for
8: Select the number of clusters whose clustering min- imizes the estimated MSE and update C.
9: Calculate the DR estimator ATE, according to (1)
using the data D().
10: end for
Output: ATE = (B/N) EN
N/B ATE
10*
70
60
Number of repested mesourements
(8)
(b)
Figure 5. (a) Four types of spatial grids in synthetic environments: square (top-left), rectangle (top-right), circle (bottom-left fans (bottom-right). (b) MSES with different numbers of repetitions N in the real-data-based simulator. The shaded area visualizes the confidence interval.
4. Experiments
In this section, we conduct numerical experiments com- pare the ATE estimator computed via the proposed causal graph cut (CGC) algorithm against those constructed based on the following benchmark methods: (i) spectral cluster- ing (SC, Leung, 2022); (ii) the three-net algorithm (TNET, Ugander et al., 2013); (iii) causal clustering (CC, Viviano et al., 2023). we also compare against the DR estimators constructed based on (iv) the global design (GD) and (v) the individual design (ID). We also compare against (vi) an oracle version of the proposed CGC algorithm (denoted by OCGC) which works as well as if the covariance matrix Σ is known in advance.
gree of spatial dependence, evaluated under three different covariance structures (constant, truncated constant, expo- nential), see Appendix C.1 for further details. We study the MSE of estimators P increases from 0.1 to 0.9. The numerical results are shown in Figure 6, with values on the y-axis presented on a logarithmic scale for clearer vi- sualization. It can be seen that our algorithms CGC and OCGC achieve MSES that are substantially smaller than CC. TNET and SC. Besides, regardless of the spatial set- ting and covariance structure, our design consistently sur- passes both the naive global design and individual de- sign, with 54% and 72% improvements, which reflects the advantage of our proposed algorithms. Finally, it is worth mentioning that the CGC closely matches the per- formance of OCGC, indicating the effectiveness of our it- erative framework.
Synthetic environments. We design four spatial settings visualized in Figure 5(a), covering four classical urban morphology (Kropf, 2017). We set function 9i to be a si- nusoidal function that incorporates both spatial covariates and treatments, with correlation parameter o indicating de-
8

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
Hithod
OCGC
CGC
TNET
OCGC
OCGC(0.0)
OCGC1O.)
THET
SC Rectangle
CC
Square
Circle
Fan
Rectangle
Square
Clrcle
10
10"
10.
10
20
10'
10'
Comsoor
10
10
10
10
10
10
10
10"
10"
10'
10'
10"
10"
0.3 0.5 0.7 0.9
0.3
0.5 0.7
09
0.3
0..
0.7
0.9
0.3
0.5
0.7
0.9
0.5
0.5
0.7
0.9
0.3
0.5
0.7
0.5
0.3 0.5
0.7
0.5
0.3
0.5
0.7
0.9
10
10a
10
10a
20'
20'
204
30'
10
10"
10
1044
MEE
10
10
10
10
10"
20"
10P
10p
30
1044
10
10
10
10
10a
10'
20
20
10
10
10
10
10" 20
10
10
10
10
10
10
0.3 0.5
6.7
0.3 0.5
077
0.3
0.5
0.7
0.3
0.5
077
03
0.5
037
0.9
03
0.5
0.3
0.9
033
0.5
077
0.9
033
0.5
0.7
0.9
rho
rho
Figure 6. The plot of / versus MSE, with each panel representing different spatial arrangement setting.
Figure 7. The plot of P versus MSE single-xxperiment set- tings, with each panel representing a different spatial arrange- ment. OCGC (0.01) and OCGC (0.1) represent our method using noised covariance matrix, where the noise follows normal vari- able with mean 0 and variance 0.01 and 0.1, respectively. We did not implement GD in single-experiment settings, since assigns the same treatment to all regions, making the ATE unidentifiable from the experimental data.
Real-data-based simulator. We develop a simulator using a five-day historical dataset from ridesharing company to evaluate the proposed approach. This simulator repli- cates key dynamics of a city-scale ridesharing market with R 85 hexagonal regions. Every seconds, the simula- updates, among others: (I) drivers' decisions to accept assigned orders, taking into account historical driver and order characteristics; (2) driver movements to pick-up loca- tions or idle movement patterns based on historical trajec- tories; (3) the driver pool, accounting for new active drivers and those going offline; and (4) new orders based on his- torical data, incorporating factors like passenger subsidies and processing unassigned and new requests. Particularly, drivers' decisions and reposition leverage the prediction of machine learning models trained with datasets that includes about million observations. Furthermore, to match with the real world setting, when each simulation starts, drivers are distributed across the city based on their empirical dis- tribution from the offline dataset that has more than 70,000 observations. See Appendix C.2 for more details.
lower. Second, due to the strong spatial correlation in real-world environments, the global design is significantly less effective than the individual design, further supporting Proposition 1. The individual design, in turn, is substan- tially less effective than the proposed method, highlighting the advantages of our approach in balancing spatial corre- lation and interference.
Single-experiment settings. Finally, we remark that our core methodology does not rely on the assumption of repeated experiments. It remains applicable to single- experiment settings when we have certain prior knowledge regarding the underlying covariance matrix, either from a pilot study or based on historical data. To support this claim, we used proxy covariance matrix constructed by adding noise to the true covariance matrix, and present the corresponding numerical results in Figure 7.
In the experiments, the covariate is the number of initial drivers available at the start of each time period. The out- come, measured by gross merchandise value (GMV), will be used to evaluate the effectiveness of the policy. We ex- clude OCGC since we cannot assess the spatial correlation of the real-world environment. The results are presented in Figure 5(b).
The results demonstrate that our estimator: (i) maintains optimality against existing methods; (ii) achieves near- oracle performance (comparable to the oracle method with the true covariance matrix); (iii) remains robust to the ap- proximation errors in the covariance matrix.
First, observe that our proposed method achieves the lowest MSE in most cases, with its MSE consistently decreasing as the number of repeated experiments in- creases, demonstrating the learning capability of our iter- ative framework. The improvement over the benchmarks is substantial, with the MSE heing approximately 3.5 times
We also remark that while cross-fitting helps simplify the theory (by avoiding the need for imposing VC-class condi- tions on to establish the asymptotics of the ATE estimator), our method remains effective without it numerical results above were obtained without cross- fitting.

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
Acknowledgements
Blau, T., Bonilla, E. V., Chades, I., and Dezfouli, A. Op- timizing sequential experimental design with deep rein- forcement learning. In International Conference Ma- chine Learning, pp. 2107-2128, PMLR, 2022.
Zhu's and Shi's research was supported by the EPSRC grant EP/W014971/1. Zhou's research was partially sup- ported by the China Scholarship Council. Lin's research was partially supported by MOE AcRF Tier 1 grant. The authors express their gratitude for the constructive com- ments provided by the referees, which substantially en- hanced the initial version of the paper.
Bojinov, I., Simchi-Levi, D., and Zhao, J. Design and anal- ysis of switchback experiments. Management Science, 69(7):375--377,, 2023.
Chen, Q. Li, B., Deng, L., and Wang, Y. Optimized co- variance design for a/b test on social network under in- terference. Advances in Neural Information Processing Systems, 36, 2024.
Impact statement
The broader impact of this work lies in its potential to enhance policy evaluation and docision-making across di- verse domains, including urban planning, transportation, healthcare, and social sciences. Its scalability and adapt- ability provide opportunities to address complex societal challenges where spatial data plays a pivotal role. However, the application of our adaptive experimental design algo- rithm requires careful consideration of data privacy, trans- parency, and informed consent-espp esseccallyy in sensitive contexts involving personal or sensitive information-to ensure its responsible and ethical deployment.
Chen, X. and Qi. Z. On well-posedness and minimax opti- mal rates of nonparametric q-function estimation off- policy evaluation. In International Conference on Ma- chine Learning, pp. 3558-3388300 -588- PMLR, 2022.
Chernozuuoov V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W. and Robins, J. Double/debiased machine learning for treatment and structural param- eters. The Econometrics Journal, 21(1):C1-668, 01 2018. ISSN 1368-4221. doi: (0.1111/ect.110997 URL attps://doi.. http:///to.oogg//////// wrt../..gg....oo 1t..0..111eecct... 120977
References
Cheroozhukov, V., Newey, W. K., and Singh. R. Debiased machine learning of global and local parameters using regularized riesz representers. The Econometrics Jour- nal, 25(3):576-601, 2022.
Agarwal, A., Agarwal, A., Masoero, L., and Whitehouse, J. Multi-armed bandits with network interference. arXiv preprint arXiv:2405. 11..:24455.881,,, 18621, 2024.
Crépon, B., Duflo, E., Gurgand, M., Rathelot, R., and Zamora, P. Do labor market policies have displacement effects? evidence from clustered randomized experi- ment. The quarterly journal of economics, 128(2):531- 580, 2013.
Aronow, P. M. and Samii, C. Estimating average causal effects under general interference, with application to a social network experiment. The Annals of Applied Statis- fics, 11(4), December 2017. ISSN 1932-6157. doi: 10.1214/16-aooa 1005. URL http: doi. 10. 1 1012111111-01000055511110- AOAS1005.
Cressie, N. Statistics for spatial data. John Wiley & Sons, 2015.
Baird, S., Bohren, J. A., McIntosh, C., and Özler, B. Op- timal design of experiments in the presence of interfer- ence. The Review of Economics and Statistics, 100(5):
Dai, B., Nachum, O., Chow, Y., Li, L., Szepesvári, C., and Schuurmans, D. Coindice: Off-policy confidence inter- val estimation. Advances in Neural Information Process- ing Systems, 33:9398 9411, 2020.
844-860, 12 2018 ISSN 0034-6535. doi: 10.1162/
rest_a_00716. URL https: / /toi///ooiioo/// www.o....rrg111. 1162/ rest_a_0011
Dai, R., Wang, J., Zhou, F., Luo, S., Qin, Z., Shi, C., and Zhu, H. Causal deepsets for off-policy evaluation under spatial or spatio-temporal interferences. arXiv preprint 2tt::2477.19100 2024.
Bajari, P., Burdick, B., Imbens, G. W., Masoero, L., Mc- Queen, J., Richardson, T., and Rosen, I. M. Multiple ran- domization designs. arXiv preprint 1:Xiv:2112.13495, 2021.
Dudik, M., Langford, J., and Li, L. Doubly robust policy evaluation and learning. In Proceedings of the 28th In- ternational Conference on International Conference on Machine Learning, pp. 1097-1104, 2011.
Bhattacharya, R., Malinsky, D., and Shpitser, I. Causal inference under interference and network uncertainty. In Uncertainty in Artificial Intelligence, pp. 1028-1038. PMLR, 2020.
Eichhorn, M., Khan, S., Ugander, J., and Yu, C. Low- order outcomes and clustered designs: combining design and analysis for causal inference under network interfer- ence. arXiv preprint arXiv:2405.077 077999, 2024.
Bian, Z., Shi, C., Qi, Z., and Wang. L. Off-policy evalua- tion in doubly inhomogencous environments. Journal of the American Statistical Association, pp. 1-27, 2024.
10

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
Farias, V., Li, A., Peng, T., and Zheng, A. Markovian inter- ference in experiments. Advances in Neural Information Processing Systems, 35:535-549, 2022.
Hahn, J. On the role of the propensity score in efficient semiparametric estimation of average treatment effects. Econometrica, pp. 315-331, 1998.
Halloran, M. E. and Struchiner, C. J. Causal inference in infectious diseases. Epidemiology, 6: 6:142-151, 1995.
Fatemi, Z. and Zheleva, E. Minimizing interference and se- lection bias in network experiment design. In Proceed- ings of the International AAAI Conference on Web and Social Media, volume 14, pp. 176-186, 2020.
Hanna, J. P., Thomas, P. S., Stone, P., and Niekum, S. Data-efficient policy evaluation through behavior policy search. In International Conference on Muchine Learn- ing. pp. 1394-1403, PMLR, 2017.
Feng, Y., Ren, T., Tang, Z., and Liu, Q- Accountable off- policy evaluation with kernel bellman statistics. In In- ternational Conference on Machine Learning, pp. 3102- 3111. PMLR, 2020.
Hao, B., Ji, X., Duan, Y., Lu, H., Szepesvári, C., and Wang, M. Bootstrapping fitted q-evaluation for off-policy infer- ence. In International Conference on Machine Learning, pp. 4074-4084, PMLR, 2021.
Fiedler, M. Algebraic connectivity of graphs. Czechoslo- vak mathematical journal, 23(2):298-300 1973.
Harshaw, C., Sävje, F., Spielman, D. A., and Zhang, P. Bal- ancing covariates in randomized experiments with the gram-schmidt walk design. Journal of the American Sta- tistical Association, 119(548):2934-2946 2024.
Fiedler, M. Laplacian of graphs and algebraic connectivity. Banach Center Publications, 125)):77770, 1989.
Fiez, T., Nassif, H., Chen, Y.C.,, Gamez, S., and Jain, L. Best of three worlds: Adaptive experimentation for digi- tal marketing in practice. In Proceedings of the ACM on Web Conference 2024, pp. 1586-3597, 2024.
Heckman, J. J., Ichimura, H., and Todd, P. Matching as an econometric evaluation estimator. The review of eco- nomic studies, 65(2):261-294, 1998.
Hu, Y. and Wager, S. Switchback experiments under geo- metric mixing. arXiv preprint arXiv:2209.00197 2022.
Fisher, R. A., Fisher, R. A., Genetiker, S., Fisher, R. A., Ge- netician, S., Britain, G., Fisher, R. A., and Généticien, S. The design of experiments, volume 21. Springer, 1966.
Hu, Y. and Wager, S. Off-policy evaluation in partially ob- served markov decision processes under sequential ig- norability. The Annals of Statistics, 51(4):1561-1585 2023.
Forastiere, L., Airoldi, E. M., and Mealli, F. Identification and estimation of treatment and interference effects in observational studies on networks. Journal of the Amer- ican Statistical Association, 166654)):01-918, 2021.
Hu, Y., Li, S., and Wager, S. Average direct and indirect causal effects under interference. Biometrika, 109(4):
Foster, A., Ivanova, R., Malik, I., and Rainforth. T. Deep adaptive design: Amortizing sequential bayesian experi- mental design. In International Conference Machine Learning, pp. 3384-3395. PMLR, 2021.
1 1165-1172 2022.
Hudgens, M. G. and Halloran, M. E. Toward causal infer- ence with interference. Journal of the American Statisti- cal Association, 103(482):832--8) 842, 2008
Gao, M. and Ding, P. Causal inference in network experi- ments: regression-basee analysis and design-based prop- erties. arXiv preprint arXiv:23009 07476, 2023.
Imbens, G. W. and Rubin, D. B. Causal inference in statis- tics, social, and biomedical sciences. Cambridge univer- sity press, 2015.
Goldschmidt, O. and Hochbaum, D. S. A polynomial algo- rithm for the k-cut problem for fixed k. Mathematics of operations research, 19(1):24-37 37, 1994.
Jia, S., Kallus, N., and Yu, C. Clustered switchback ex- periments: Near-optimal rates under spatiotemporal in- terference. arXiv preprint 2rXiv:2312.15577. 2023.
Jia, S., Frazier, P., and Kallus, N. Multi-armed bandits with interference. arXiv preprint arXiv:2402.0118. 2024.
Gui, H., Xu, Y., Bhasin, A., and Han, J. Network a/b test- ing: From sampling to estimation. In Proceedings of the 24th International Conference on World Wide Web, pp. 399 409,40999200 2015.
Jiang, N. and Li, L. Doubly robust off-policy value evalua- tion for reinforcement learning. In International confer- ence on machine learning, pp. 652-661. PMLR, 2016.
Hagen, L. and Kahng, A. B. New spectral methods for ratio cut partitioning and clustering. IEEE transactions on codduter-aided design of integrated circuits and sys- tems, 1049):177411085 1992.
Jiang, Y. and Wang, H. Causal inference under network interference using a mixture of randomized experiments. arXiv preprint arXiv:2309.0m 00100,,001,, 2023.

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
Jiang, Y., Deng, L., Wang, Y., and Wang, H. Causal infer- ence in social platforms under approximate interference networks. arXiv preprint arXiv:2408. 444404444, 2024.
Li, T., Shi, C., Wang, J., Zhou, F,, et al. Optimal treat- ment allocation for efficient policy evaluation in sequen- tial decision making. Advances in Neural Information Processing Systems, 36, 2023.
Johari, R., Li, H., and Weintraub, G. Experimental de- sign in two-sided platforms: An analysis of bias. arXiv preprint arXiv:2002.056700 2020. "To appear in ACM Economics and Computation 2020".
Li, T., Shi, C., Lu, Z., Li, Y., and Zhu, H. Evaluating dy- namic conditional quantile treatment effects with appli- cations in ridesharing. Journal of the American Statisti- cal Association, pp. 1-15, 2024.
Johari, R., Koomen, P., Pekelis. L., and Walsh, D. Always valid inference: Continuous monitoring of a/b tests. Op- erations Research, 7063):100618211 2022.
Liao, P., Qi. Z., Wan, R., Klasnja, P., and Murphy, S. A. Batch policy learning in average reward markov decision processes. Annals of statistics, 50(6):3364, 2022.
Kallus, N. Optimal a priori balance in the design of con- trolled experiments. Journal of the Royal Statistical So- ciety Series B: Statistical Methodology, 80(1):85-112, 2018.
Liu, L., Hudgens, M. G., and Becker-Dreps, Dreps, S. On inverse probability estimators in the presence of inter- ference. Biometrika, 103(4):829-842, 2016.
Kallus, N. and Uchara, M. Efficiently breaking the curse of horizon in off-policy evaluation with double reinforce- ment learning. Operations Research, 3066:332223330. 2022.
Liu, L., Hudgens, M. G., Saul, B., Clemens, J. D., Ali, M., and Emch, M. E. Doubly robust estimation in observa- tional studies with partial interference. Stat, 8(1):e214, 2019.
Karrer, B., Shi, L., Bhole, M., Goldman, M., Palmer, T., Gelman, C., Konutgan, M., and Sun, F. Network ex- perimentation at scale. In Proceedings of the 27th acm sigkdd conference on knowledge discovery & data min- 2021.
Liu, Q.. Li, L., Tang, Z., and Zhou, D. Breaking the curse of horizon: Infiitt-horizzon off-policy estimation. Ad- vances in Neural Information Processing Systems, 31, 2018.
ing. pp.
Kato, M., Oga, A., Komatsubara, W., and Inokuchi, Active adaptive experimental design for treatment ef- feet estimation with covariate choices. arXiv preprint arXiv:2403.03589 2024.
Liu, S. and Zhang, S. Efficient policy evaluation with of- fline data informed behavior policy design. In Inter- national Conference on Machine Learning, pp. 32345- 32368. PMLR, 2024.
Kropf, K. The handbook of urban morphology. John Wiley & Sons, 2017.
Liu, Y., Zhou, Y., Li, P., and Hu, F. Cluster-adaptive network a/b testing: From randomization to estimation. Journal of Muchine Learning Research, 25(170):1 2024.
Kuzborskij. I., Vernade, C., Gyorgy, A., and Szepesvári, C. Confident off- aff-policy evaluation and selection through self-normalized importance weighting. In International Conference on Artificial Intelligence and Statistics, pp. 640-648. PMLR, 2021.
Luckett, D. J., Laber, E. B., Kahkoska, A. R., Maahs, D. M., Mayer-Davis, E., and Kosorok, M. R. Estimat- ing dynamic treatment regimes in mobile health using v-learning. Journal of the American Statistical Associa- tion, 115(530):692-7000 2020.
Le, H., Voloshin, C., and Yue, Y. Batch policy learning un- der constraints. In International Conference on Machine Learning, pp. 3703-3712. PMLR, 2019.
Luo, S., Yang, Y., Shi, C., Yao, F., J., and Zhu, H. Pol- icy evaluation for temporal and/or spatial dependent ex- periments. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp. qkad136, 2024.
Leung, M. P. Rate-optimal duster-randomizee designs for spatial interference. The Annals of Statistics, 50(5): 3064-3087, 2022.
Leung, M. P. and Loupos, P. Graph neural networks for causal inference under network confounding. arXiv preprint arXiv:2211.0788 2022.
Ma, Y. and Tresp, V. Causal inference under networked interference and intervention policy enhancement. In International Conference Artificial Intelligence and Statistics, pp. 3700-3708. PMLR, 2021.
Li, H., Zhao, G., Johari, R., and Weintraub, G. Y. Interfer- ence, bias, and variance in two-sided marketplace exper- imentation: Guidance for platforms. In Proceedings of the ACM Web Conference 2022, pp. 182-192, 2022.
Munro, E., Wager, S., and Xu, K. Treatment effects in market equilibrium. arXiv preprint arXiv:2109.1 11647, 2021.
12

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
Ni, T., Bojinov, I., and Zhao, J. Design of panel experi- ments with spatial and temporal interference. Available at SSRN 4466598, 2023.
Shi, C., Zhu, J., Shen, Y., Luo, S., Zhu, H., and Song, R. Off-policy confidence interval estimation with con- founded markov decision process. Journal of the Amer- ican Statistical Association, 1 (9(545))273-2844 2024.
Perez-Heydrich, C., Hudgens, M. G., Halloran, M. E., Clemens, J. D., Ali, M., and Emch, M. E. Assessing effects of cholera vaccination in the presence of interfer- ence. Biometrics, 70(3):731-741, 2014.
Sobel, M. E. What do randomized studies of housing mo- bility demonstrate? causal inference in the face of inter- ference. Journal the American Statistical Association, (0164)):: 2006.
Puelz, D., Basse, G., Feller, A., and Toulis, P. A graph- theoretic approach to randomization tests of causal ef- fects under general interference. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84 (1):174-204, 2022.
Song, Z. and Papadogeorgou, G. Bipartite causal infer- ence with interference, time series data, and a random network. arXiv preprint arXiv:2404.04775, 2024.
Stoer, M. and Wagner, F. A simple min-cut algorithm. Journal of the ACM (JACM), 44(4):585-55) -51, 1997.
Reich, J., Yang, S., Guan, Y., Giffin, B., Miller, M. J., and Rappold, A. A review of spatial causal inference methods for environmental and epidemiological applica- tions. International Statistical Review, 89(3):605-66 634, 2021.
Sun, K., Kong, L., Zhu, H., and Shi, C. Arma-design: Opti- mal treatment allocation strategies for a/b testing in par- tially observable time series experiments. arXiv preprint arXiv:2408.04 0554224,...0342,, 2024.
Rolnick, D., Aydin, K., Pouget-Abadie, J., Kamali, S., Mir- rokni, V., and Najmi, A. Randomized experimental de- sign via geographic clustering. In Proceedings of the 25th ACM SIGKDD International Conference on Knowl- edge Discovery& & Data Mining, pp. 2745-2753, 2019.
Swaminathan, A. and Joachims, T. The self-normalized estimator for counterfactual learning. advances in neural information processing systems, 28, 2015.
Tan, Z. Bounded, efficient and doubly robust estima- tion with inverse weighting. Biometrika, 9763)6661-682, 2010.
Saveski, M., Pouget-Abadie, J., Saint-Jacques, G., Duan, W., Ghosh, S., Xu, Y., and Airoldi, E. M. Detecting network effects: Randomizing over randomized exper- iments. In Proceedings of the 23rd ACM SIGKDD in- ternational conference on knowledge discovery and data mining, pp. 1027-1035, 2017.
Tang, X., Qin, Z., Zhang, F., Wang. Z., Xu, Z., Ma, Y., Zhu, H., and Ye, J. A deep value-network based approach for multi-driver order dispatching. In Proceedings of the 25th ACM SIGKDD international conference on knowl- edge discovery data mining, pp. 1780-1790 1790, 2019.
Shi, C., Wan, R., Chernozhukov, V., and Song, R. Deeply- debiased off- off-policy interval estimation. In International conference on machine learning, pp. 9580-9591. PMIR,, 2021.
Tchetgen, E. J. T. and VanderWeele, T. J. On causal infer- ence in the presence of interference. Statistical methods in medical research, 21 21(1):5-77, 2012.
Thomas, P. and Brunskill, E. Data-efficient off-policy pol- icy evaluation for reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 2139-2148. PMLR, 2016.
Shi, C., Zhang, S., Lu, W., and Song, R. Statistical in- ference of the value function for reinforcement learning in infinite-horizon settings. Journal of the Royal Sta- tistical Society Series B: Statistical Methodology, 84(3): 765-793, 2022.
Thomas, P.. Theocharous, G., and Ghavamzadeh, M. High- confidence off-policy evaluation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, 2015.
Shi, C., Wan, R., Song, G., Luo, S., Zhu, H., and Song, R. A multiagent reinforcement learning framework for policy evaluation in two-sided markets. The Annals of Applied Statistics, 1774222701- 2023a.
Ugander, J., Karrer, B., Backstrom, L., and Kleinberg, J. Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM SIGKDD international conference Knowledge dis- covery and data mining, pp. 329-337, 2013.
Shi, C., Wang, X., Luo, S., Zhu, H., Ye, J., and Song, R. Dynamic causal effects evaluation in a/b testing with a reinforcement learning framework. Journal of the American Statistical Association, 1180 118(543).059-2077) 2023b.
VanderWeele, T. J., Vandenbroucke, J. P.. Tehetgen, E. J. T., and Robins, J. M. A mapping between interactions
13

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
and interference: implications for vaccine trials. Epi- demiology, 23(2):285-22,, 2012.
Zhang, B., Tsiatis, A. A., Laber, E. B., and Davidian, M. A robust method for estimating optimal treatment regimes. Biometrics, 68(4):1010-1018, 2012.
Verbitsky-Saviin N. and Raudenbush, S. W. Causal infer- ence under interference in spatial settings: a case study evaluating community policing program in chicago. Epi- demiologic Methods, 1(1):107-130. 2012.
Zhang, B., Tsiatis, A. A., Laber, E. B., and Davidian, M.
Robust estimation of optimal dynamic treatment regimes for sequential treatment decisions. Biometrika, 100(3): 10-1093, 2013.
Viviano, D., Lei, L., Imbens, G., Karrer, B., Schrijvers, O., and Shi, L. Causal clustering; design of cluster ex- periments under network interference. arXiv preprint arXiv:2310. 14983, 2023.
Zhang, W., Yang, Y., and Yao, Spatial interference detection in treatment effect model. arXiv preprint arXiv:2409.0443 2024.
Wager, and Xu, K. Experimenting in equilibrium. arXiv preprint arXiv: 1et..0903.2.222 2019.
Zhang, Z. and Wang, Z. Online experimental design with estimation-regre trade-off under network interference. arXiv preprint arXiv:2412.03777, 2024.
Wan, R., Kveton, B., and Song, R. Safe exploration for efficient policy evaluation and comparison. In Inter- national Conference on Machine Learning. pp. 22491- 22511. PMLR, 2022.
Zhao, J. Experimental design for causal inference through an optimization lens. Tutorials in Operations Re- search: Smarter Decisions for a Better World, pp. 146- 188. INFORMS, 2024a.
Wang, J., Qi. Z., and Wong, R. K. Projected state-action balancing weights for offline reinforcement learning. The Annals Statistics, 51(4):1639-165, 2023.
Zhao, J. A simple formulation for causal clustering. Avail- able at SSRN 50082 13, 2024b.
Wang, Y., Gu, C., and Otsu, T. Graph neural networks: Theory for estimation with application on network het- erogeneity. arXiv preprint arXiv:2401.16277 2024.
Zhao, Y., Zeng. D., Rush, A. J., and Kosorok, M. R. Es- timating individualized treatment rules using outcome weighted learning. Journal of the American Statistical Association, 107(499): 106-11181 2012.
Weltz, J., Fiez, T., Volfovsky, A., Laber, E., Mason, B., Jain, L., et al. Experimental designs for heteroskedastic variance. Advances in Neural Information Processing Systems, 36, 2023.
Zhong, R., Zhang. D., Schäfer, L., Albrecht, S., and Hanna, J. Robust on-policy sampling for data-efficient policy evaluation in reinforcement learning. Advances in Neu- ral Information Processing Systems, 35:37376-37388, 2022.
Wen, Q. Shi, C., Yang, Y., Tang, N., and Zhu, H. Unrav- eling the interplay between carryover effects and reward autocorrelations switchback experiments. In Interna- tional Conference on Machine Learning. PMLR, 2025.
Zhou, H., Hanna, J. P., Zhu, J., Yang, Y., and Shi, C. De- mystifying the paradox of is with an estimated history- dependent behavior policy in ope. In International con- ference on machine learning. PMLR, 2025.
Xiong, R., Chin, A., and Taylor, J. Data-driven switch- back experiments: Theoretical tradeoffs and empirical bayes designs. arXiv preprint arXiv:2406. 06766, 2024.
Zhu, Z., Cai, Z., Zheng, L., and Si, N. Seller-side exper- iments under interference induced by feedback loops in two-sided platforms. arXiv preprint 1rX1v:2401.15811, 2024.
Xu, Y., Zhu, J., Shi, C., Luo, S., and Song, R. An instru- mental variable approach to confounded off-policy eval- uation. In International Conference on Machine Learn- ing, pp. 31848-8888888 PMLR, 2023.
Zigler, C. M. and Papadogeorgou, G. Bipartite causal in- ference with interference. Statistical science: review journal of the Institute of Mathematical Statistics, 36(1); 109, 2021.
Xu, Y., Lu, W., and Song, R. Linear contextual bandits with interference. arXiv preprint arXiv:2409. 15682, 2024.
Yang, Y., Shi, C., Yao, F., Wang, S., and Zhu, H. Spa- tially randomized designs can enhance policy evaluation. arXiv preprint arXiv:2403. 00044003.00000.. 1400, 2024.
Zhan, R., Han, S., Hu, Y., and Jiang, Z. Estimating treatment effects under recommender interference: A structured neural networks approach. arXiv preprint arXiv:2406. 14380, 2024.
14

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
A. Surrogate function for general m
For the general case where m 2, similarly, to minimize MSE that affected by the clustering configuration, sufficient minimize the upper bound of SC + by solving the following objective function:
ΣEΣ jekiEC, M'Ca
2R WW
ΣEΣ E
(3)
m
jskiec, F'E,
where the first term is upper bound of and the later one equal the term SC after adding constant Σ objective function (3) forms a graph-cut problem.
Egg. The 1,7'
B. Proofs
B.1. Proof of Theorem
Proof. According to Theorem 2 in Yang et al. (2024) and assuming functions 9: are known, we have
MSE(AT) (ATE DR
= oî DA,
where
of = N Σ
pp +
(1 - mm Ess > 0),
1
2
E (9.(11 O.) - 0.(0.
DA
Var
N
where ma = Σ IWWnc * (N ne, # Ø) represents the number of clusters that both Mr and A2. belong to.
We now elaborate that of SC 11 + 12. Note that set p 0.5 throughout this paper for balanced design. Let C3 denote the interior region of cluster Cj. We first rewrite of in the following form:
of
m
2A:
Σ VEBC,
I(AM =1) I(AN 01 ee
N
P
mm:
j=1
IECO
which can be decomposed into the of a within-cluster term o and between-cluster term of. Specifically,
En 22
EN iECy r'E pa
EN p +
2
N
j=1
EC
Eas p= pltmer
E,Y'C,
i
Ear (1 - p m
= SC + N Σ
pltma
#=1 LEE
15

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
and
o
2
Σ
Da pd
I(V nc, #0]
+ N
Σ Σ
Σ
Ene l(mi > 0)]
N
jzk iECy e'ecc
jæk iE d'EaC
2
En
I(N ne, =0]
Σ Σ
Die pm
2
[T([ nc, #0]
N
p
N
p²
jæk iEC,
K'EOCx
jØ tEaC, E'E
ENe pm (I(mar > - II nc, + $1)]
E
+
N
1 iE00, N'EBCk
= =1
Σ Σ
EN
2E
p² MING nc, # *0]
N
pma
1/ iEBC, PEDCy
EEe' pmunt (Immw > 0) -0 nC + +
ΣE j& iEaC, d'E8Cx
Σ
Jg
We denote 1/2 = J1 + J2 + J3- Then we have of = SC + 11 + T2-
B.2. Proof of Proposition 1
Proof. Because the correlation between non-neighboring regions is sufficiently small and the correlation between neigh- boring regions is positive, we can simplify our proof by setting Σnr = 0 for any two non-neighboring regions. Under such a condition, we have
N
SC
ΣSN
ENP
ΣΣ
Eie
4
j7h SEC s'ECk
Σ Es Σ
Σ
Eg Way,
jith NENN, E'ECk
4 = Σ 4
Σ
Egg Ww..
37k tEdC PEaC,
Thus minimizing SC is equivalent minimizing
ΣΣ Σ EarWi.
(4)
jutk iEBC, F'ENCE
Under the global design, there has only one cluster, making the expression in (4) equal to zero. Given that all elements Ene are non-negative, we conclude that the global design achieves the minimum value for (4).
For the second-order interference 12, we analyze its three components separately to demonstrate that the global design optimal:
For J1, when the i, -th regions are within the same cluster C,. we have mav 2 1, and thus (1p(--p"-e -1 Therefore, Jn is minimized under the global design where there are no boundaries.
2 0.
p plmme
For Jz, have
2ΣnV p2
NJ2 = Σ j#k iEaC, d'EaC,
I(N NC + (C O)I i' are two neighboring regions).
Since mar 2 2 when i, i are adjacent, together with the fact that p = 0.5, " p² The results ensures global design minimizes Jz.
Ene 2E
must be a non-negative value.
16

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
For J3. because Ny. n C3 * 0 implies ma 2 then have I(m 0) I(N₂ ne + 0), which ensures Dn p"rtt (I(mar > 0) - I nC₃ + 0)) is always non-negative. This fact implies J3 is minimized under the global design.
Since SC+ 1 and 1/ are each minimized under the global design, their sum is also minimized under the global design.
B.3. Proof of Proposition 2
Proof. When SUTVA holds, the interference terms I and 12 equal zero. For SC, we have
SC
Ew Σ 12
ΣΣΣ
Exe
(5)
N
jtkiEC, N'Ex
Thus minimizing MSE is equivalent to maximizing Σ jsh Eiec, Evec, Eie, which equals the summation over correla- tions between different clusters. Due to the non-negativeness of Eie, it is maximized when m R, where each region belongs unique cluster, i.c., as in the individual design.
B.4. Proof Proposition 3
Proof. As proved in Section B.I, we have
8
Σ
EaN
nCI # +0)+
Σ EEΣ
Σ
Int *
N
3'E
IEC, F'dc
Σ
Σ ECC
WE Σ
Σ+ Σ
Weo
F'E2
IEC, P'EC
LEC2
8
$
E We Σ
E Wes
IEC1 M'Ecs FEC1
IECa EEC; FEC2
|Gl
Σx We
|C2l Σ
E Wes
(6)
REC, LEC1
PEC EEC2
where the second inequality holds under Assumption 2. The last term (6) equals
N [c1++ 1ca))
Σ Σ
We We =
SR N
Σ ΣΣ SttWe
PEC, tEC
REC, LECs
which, together with Equation (5), gives the objective function:
8
Σ
Σ
RE War
Ens
N
IEC,
E'C,
17

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
B.5. Proof of Proposition 4
Proof. As stated in Section B.3, we have
8R N
Σ Σ
Wer
We
Wer + +ΣE> E
E Wee
N
E'E REC2
iEC E'ECa EEC,
lEC2 D'EC, LEC2
2e We + Σ
E
Σ
WeY
iEC 1' E'EdCs rEC1
IEC2 PEDCI EECa
max Eie N '9fl'
ΣE
Σ
We + 3
Σ
Wer
iEC1 F'E8C2 REC1
IEC2 F'ECC1 FEC2
dmax max Eis
Σ
Σ
I(N nc1 # 0) +
Σ
I(N nC2 + #M]
N
IEC PEDC2
IEC2 d'E0c1
N d
Σ Σ
ENI(NN nc # + Σ
Σ
ENI((N nC2 #0]
sECi d'eds
iEC2 d'EaC,
1maxol1:
where the second equation holds because Wx when i' falls in the interior region of its cluster, and the second inequality holds because each i' aC2 (for l 2) can have at most dmax adjacent neighbors that fall in Cy.
C. Experiments: details and additional results
C.1. Synthetic environments
Settings. The model for the outcome is represented as follows:
Yu = =00 sin (4z + by +8x x (Ase + 0.5A.s)) + eit,
where Oz. E IR represents the covariates, A. N EI=TESpI.EEN Ajr represents the average of neighboring treatments, and s denotes the signal strength, which is set to 2.5% for our experiments. For each i, (eit:..., eR)) are independently drawn from zero-mean multivariate Gaussian distribution with time-invariant covariance Σ. Under the spatial setting, is set as one of the following correlation structures: (i) constant correlation, Σg p (+/3)); (ii) truncated constant correlation, Eij = T(i = j) + (p- R- R- - ji) - jl S pf); (iii) exponential correlation, Eig = p --11, After structuring the regions, the corresponding synthetic environment is created to simulate the conditions that allow us to generate datasets.
We evaluate each method using the relative MSE as criterion. Specifically, we use the relative MSE which is computed as R- >x=
=1=1 (ATE, ATE)² (ATE),, where ATE, is the estimated ATE returned by one estimator at the r-th independent replication. We set the total number of replications to R = 50.
C.2. Real-data simulator
Orders and drivers are simulated as follows:
1. New orders are generated according to historical data. These orders, along with existing unassigned orders, are pro- cessed and assigned according to the dispatch algorithm described in Tang et al. (2019).
2. Drivers who are assigned to orders will decide whether to accept them based probabilities generated by a pre-trained LightGBM model. This step considers various characteristics of both the drivers and the orders.
Drivers who are idle and not currently assigned any orders are directed to specific areas based on historical data of idle driver movements.
4. Drivers who are subject to repositioning must follow the directives provided by a pre-trained repositioning algorithm implemented by the ridesharing platform.
5. Once drivers accept orders, they proceed to the pickup locations, collect the passengers, and then travel to the specified destinations.
The pool of available drivers is continuously updated to reflect new drivers entering the service area and existing drivers who go offline.
18

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
Different from the synthetic environment, cannot obtain the oracle ATE value by mathematical calculation. There- fore, we use Monte Carlo (MC) procedure approximate the true ATE value. Specifically, for N independent days under actions I and O, respectively, leading to the reward observations (1() JIsisRISSSN and (r hSSSRISISN- With the two datasets, the MC estimator for ATE is given by:
the simulator
N
ATE
MC
1
(1) it
10) rit
N
MC
When N + oo, the ATE converges to ATE, our experiment, we set N to a large value and the obtained ATE is set as the surrogate of the true ATE. Specifically, N is set as 1000.
C.3. Implementation details
Algorithm in the main text skips the estimation procedure of {g: so as to simplify the illustration of the algorithm. Here, we elaborate the details. Besides, to circumvent the need for imposing stringent metric entropy conditions on the outcome regression function (Dai et al., 2020), we adopt the data-splitting and cross-fitting method (Chernozhukov al., 2018).
The idea of cross-fitting is presented below. Given the repeated observations {(Y,,, A..,, h SigRISINN we split the data into K non-overlapped subsets of equal size. Then we estimate the regression function gi based on the training data {(Yi,; A, O,) t & I,, < i &. R}. where I denote the indices of the kth subset. We denote the estimated function gi as 9. under such step. Under the cross-fitting framework, we denote the DR estimator as ATE complete algorithm for this in Algorithm 2.
DR-CF
We summarized the
Algorithm Estimating ATE the (-th iteration using cross-fitting fitts--.ittig.
Input: Datasets DD) = (Y, A,, O.) for j = 1,..., I, as collected in Algorithm 1.
1: Split dataset ((1) .... ((() into K non-overlapped subsets of equal size. Let Ig denote the set of the indices for the ktth subset.
2: for k == ,....,,KK....... K do
3: Compute the estimated outcome regression functions (=(k) 1 based on the data tuples {(Y,,, Ai., Oit)3 | 1 i==1
I,, {1..... ......,RR R}} using random forest.
4: Compute 2(k)] (a) 9: (Ar.,, Or,)) + Ti,(a)
(k)
(k) [a] [Ys 9. (Ar, Owt) for all i E {l...., R} and t Ig.
5: end for
6: Compute the ATE estimator:
R
ATE
DR
1 (1) (1))) (0)
IB
1 TET, 1m1
CR
Output: ATE,
We give more details on the Step and Step 5 in Algorithm 2.
In Step instead of using the observed data each region fit regression model, we concatenate the observed data in all region, and augment the data by including the longitude and latitude two additional features. The advantage of this procedure is that it shares the information across spatial regions, making the estimated outcome regression model can still fit data well when the number of repeated observations N is small. The advantage of this procedure is demonstrated by Figure& 8. We can see that, when sample size is small, such procedures (denoted as OCGC, CGC) are much better than fitting gi individually with dataset {(Y,,, Aa, Oz) H (denoted as OCGC-Local, CGC-Local).
Step 6, we need to calculate the term (a)) for estimation. Because the treatment are randomly assigned and
19

---

Causal Graph Cut: Balancing Interference and Correlation in Spatial Experimental Designs
independent to covariates, (E (a)) has close form expression that is written as:
([Tx (p)
II SEN
1(i (o)
II iEN
[ $ Cx).
kyj
Using this expression can simplify the computing on ATE.
In the algorithm, in single step (i.e., D generated in the I-th step). This approach sufficiently leverages the collected data reported in Figure 9. We use the logarithmic scale on values of y-axis for clearer presentation. From Figure 9, leveraging all data (denoted as CGC) generally decreases the MSE when compared to using only one dataset D()) (denoted as CGC-ST).
use D ..... D D together to refit machine learning model, rather than using the dataset obtained
Method
OCGC
OCGC -Local
CGC
CGC CoCal
Constant
Truncated
Exponential
10
10-1_
10
MSE
Squars
10
10
10
20
30
40
20
30
40
50
60
70
80
50
60
70
80
Number of repeated experiments
Figure 8. The plot number of repeated experiments MSE square spatial setting. Each panel corresponds spatial corre- lation setting. For clearer representation, we adopt logarithmic scale for the values on the y-axis.
Method
OCGC
CGC
CGC-ST
Constant
Truncated
Exponential
1011
MSE
Square
10
20
40
60
80
100
120
140
20
40
80
100
120
140
20
40
60
80
100
120
140
Number of repeated experiments
Figure 9. The plot of number of repeated experiments versus MSE on square spatial setting.
D. Discussion and Future Works
Our method omits I in the objective function to facilitate the optimization. We acknowledge that such second- effects may be negliggigi However, its inclusion would significantly increase the computational complexity. Developing a computationally tractable solution that properly accounts for this term remains a practical challenge for future work. In terms of applications, our methodology primarily targets settings where independent experiments can be repeatedly conducted over time. While this framework aligns well with our ridesharing application for spatial A/B testing (the focus of this paper), it may require adaptation for other settings. From the empirically effective performance our approach on the single experiment, it would be promising direction extend our approach to general experimental settings.
20


Reviews:
[{"review_id": "PiRRuSkrSl", "reviewer": "Reviewer_VLbx", "summary": "This work addresses the problem of experimental design under interference. The authors assume that the interference structure can be accounted for by a covariance matrix which is proposed to be estimated from data via repeated experimentation. The key insight of this work is a decomposition of the global average treatment effect in terms which decomposes intrinsic variance and direct and indirect network components. This decomposition motivates the development of a graph cut based algorithm, with bernoulli randomization performed over clusters. Empirical evidence provided via synthetic data an simulations show strong performance in comparison with other commonly used methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "> Methods And Evaluation Criteria\n\nWe appreciate your thoughtful comments, which are mainly about our settings with repeated and independent experiments. We believe your concerns may arise from certain misunderstandings of our paper, and we appreciate the opportunity to clarify them. We address them in three ways: (1) clarifying our focus on spatial A/B testing; (2) demonstrating that our approach is readily applicable to single-experiment settings, supported by promising numerical results; (iii) showing that our approach can be extended to handle carryover effects (the delayed treatment effect you mentioned). \n\n(1) **Focus of this paper**. We clarify that this paper focuses on the **spatial** setting -- specifically, Example 1 (A/B testing in marketplaces) -- and **not network** A/B testing. While many designs from network experimentation can be adapted to our setting (and we compared them numerically), our primary focus, as stated on Page 1 (the last sentence), remains Example 1. \n\nIn applications like **ridesharing**, experiments can be conducted daily, with data across days treated as independent. This is due to the drop in demand early in the morning (1 -- 5 AM), ensuring each day’s data represents an independent realization. Such settings are well-adopted in prior work (Li et al., 2023, NeurIPS; Li et al., 2024, ICML; Luo et al., 2024, JRSSB). Another application occurs in **marketing auctions**, where daily budget resets eliminate carryover effects, making the independence assumption plausible (Basse, 2016, AISTATS; Liu, 2020, arXiv:2012.08724).\n\n(2) **Extensions to single-experiment settings**. Our core methodology does not rely on this assumption of repeated experiments. It remains applicable to single-experiment settings when we have certain prior knowledge regarding the underlying covariance matrix, either from a pilot study or based on historical data.\n\nTo satisfy the practical requirement, we utilized a proxy covariance matrix, obtained by inserting noises into the true covariance matrix, and conducted additional experiments during the rebuttal. The [results](https://www.dropbox.com/scl/fi/cnbq91x32ygqfj7k6kb1t/VLbx_NoRepeat.pdf?rlkey=8rn9ual6o8nv2qbbhzrtx2ds9&st=cg00de5r&dl=0) demonstrate that our estimator: (i) maintains optimality against existing methods, (ii) achieves near-oracle performance (comparable to the oracle method with the true covariance matrix), (iii) remains robust to the approximation errors. \n\nWe also remark that while cross-fitting helps simplify the theory (by avoiding the need for imposing VC-class conditions on $g$ to establish the asymptotics of the ATE estimator), our method remains effective without it - numerical results above were obtained without cross-fitting. \n\n(3) **Extensions with carryover effects**. The target here becomes the cumulative ATE aggregated over time. To handle carryover effects, we can use existing doubly robust estimators from the RL literature (Kallus & Uehara, 2022, OR); see also first equation on Page 18 of Yang et al. (2024). The resulting estimator maintains a similar form to ours, with two modifications: (i) the function g is replaced by a Q-function, and (ii) the IS ratio is replaced by its marginalized counterpart (Liu et al., 2018, NeurIPS). Treatments over time can be assigned using switchback designs, which are widely adopted (Bojinov, 2023, MS; Xiong et al., 2024, arXiv:2406.06768). As shown in Theorem 5 of Yang et al. (2024), the MSE of this ATE estimator has a similar closed-form expression, enabling us to apply the same decomposition and design a similar surrogate loss for optimization.\n\n> Experimental Designs or Analyses\n\nIn the rebuttal, we considered other topologies and conducted additional experiments. Results reported [here](https://www.dropbox.com/scl/fi/hrhn52rrbavnrt9heokaz/Vlbx_Topologies.pdf?rlkey=3zcr40ukuyysaj3z8x3flycdo&st=2h15akph&dl=0) demonstrate the advantages of our proposal over baselines.\n\n> Essential References\n\nWe are happy to include these additional references and discuss their findings as you required. However, as we discussed, we primarily focus on the **spatial** setting, and references on network experimentation might not be essential. \n\n> Bernoulli randomization\n\nThe Bernoulli randomization is the same as our individual design. While Kallus (2018) established its minimax optimality without additional assumptions, we also proved its optimality in Proposition 2 without spatial interference. However, in settings with spatial interference, such a design is no longer guaranteed to be optimal. Specifically, Theorem 3.4 in Viviano et al. 2023 shows that cluster randomization outperforms Bernoulli randomization when the interference is not too weak. We also provide theoretical (Proposition 1) and numerical (extensive experiments) evidence that Bernoulli randomization becomes suboptimal in such cases.", "claims_and_evidence": "Yes, overall I think the claims are well laid out, the evidence is also good, though I would have liked to have seen a slightly larger set of empirical results.", "methods_and_evaluation_criteria": "The authors rely on sample splitting/cross fitting in order to estimate the outcome model. However, I don't see how we can assume we are able to effectively perform cross fitting without a lot more additional considerations. The authors assume that we are able to conduct the same experiment multiple times. This is a very strong assumption on multiple levels. For many settings in both industry and the social sciences it is infeasible to run the same experiment multiple times. Even when we are able to run the experiment multiple times we are assuming that we can assume independence across time, i.e., that having received treatment $i$ at round $t$ has no impact on future outcomes (which often fails to hold). If instead of assuming that we are running an experiment multiple times on the same population we are assuming that we are subsampling a population and running an experiment, we are in the regime of sampling independent but representative samples from a network, a highly nontrivial problem which will induce many of the problems the paper is seeking to avoid. Given this, it's not clear how this method works outside of bespoke settings without being able to have oracle access to the network structure. I'm curious if I've missed something or if the authors have a set of scenarios where we'd expect to have this structure.", "theoretical_claims": "Yes. I found the claims to be well founded.", "experimental_designs_or_analyses": "Yes, I did. As I mention above, I would have liked to see a larger range (in particular varying topologies, etc. ) but what was performed is sound.", "relation_to_broader_scientific_literature": "This paper builds on a growing literature on network experimentation. The key insight sits between work in the experimental design literature (e.g., \"Optimal A Priori Balance in the Design of Controlled Experiments\" by Kallus, the Gram-Schidt Walk paper by Harshaw et al.) which seek to find designs where treatment status is negatively correlated with feature distance, and network experiementation (e.g., Ugander et al), where clustering is required to make plausible inference on global treatment effects.", "essential_references_not_discussed": "Should probably cite the work on experimental design (see above), as well as Fatemi, Zahra, and Elena Zheleva. \"Minimizing interference and selection bias in network experiment design.\" Proceedings of the International AAAI Conference on Web and Social Media. Vol. 14. 2020.", "other_strengths_and_weaknesses": "I think the decomposition is nice. The insight has existed implicitly in the literature but it is useful to see it explicitly spelled out.", "other_comments_or_suggestions": "Please see above regarding the repeated experiments.", "questions_for_authors": "See above, also in design it is known (see Kallus) that without further assumptions on the potential outcomes Bernoulli randomization is minimax optimal. It would be good to have this mentioned in the paper. My question is how we should think about how that assumption interplays with the necessary assumptions for estimating the GATE.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "Z0xhtlLrjb", "reviewer": "Reviewer_NcNs", "summary": "The paper proposes a new method for experimental design in settings with repeated experiments, spatial interference and error correlation. The authors characterize the MSE of the doubly-robust average treatment effect estimator, and propose an upper bound objective function that depends on estimable quantities and can be minimized using standard graph cutting algorithms. Their proposed method uses information from the estimated error correlation structure to balance the contributions of cross-cluster and within-cluster correlation in the MSE, and can be computed efficiently. Through a synthetic simulation exercise and a real data simulation study the paper shows that the proposed method performs well relative to other commonly used methods in the literature.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We greatly appreciate your constructive comments and your positive assessment of our paper. We focus on your major comments below.\n\n>Comparison with Viviano et al. (2023)\n\n**Difference in objective**: One of the key difference lies in the choice of the estimator. Specifically, our estimator explicitly accounts for interference and remains unbiased regardless of the interference pattern (we will make this clearer in the paper), whereas Viviano et al.'s IS estimator is biased under interference. As such, although both minimize MSE, our optimization focuses exclusively on variance reduction whereas they must jointly consider both bias and variance. \n\n**Gain from repeated experiments**: Having repeated experiments allows us to accurately estimate the covariance function, which is crucial for our approach to achieve adaptivity. In comparison, such estimation is not feasible in Viviano et al.'s setting. As such, they adopted a minimax formulation that considers the worse case across all covariance functions.\n\nFollowing your suggestion, we conducted an ablation study during the rebuttal to distinguish the improvements from having repeated experiments. We consider single-experiment settings with certain prior knowledge regarding the covariance function, e.g., having access to a noisy covariance matrix. We kindly refer you to our response to Reviewer VLbx for the experimental results (see **Extensions to Single-Experiment Settings**).\n\n>Theoretical claim 1\n\nThe inequality holds due to the presence of $R$ in (2) and the indicator function $\\mathbb{I}(\\mathcal{N}\\_{i'} \\cap \\mathcal{C} \\neq \\emptyset)$ in $I_1$. The key step in establishing this inequality lies in upper bounding the indicator by $\\sum_{\\ell \\in \\mathcal{C}} W_{\\ell i'}$. This inequality holds because when $i'$ is adjacent to $C$, there exists at least one $i\\in \\mathcal{C}$ such that $W_{ii'}=1$; see this [Figure](https://www.dropbox.com/scl/fi/r4zqqzmruzge7bu5zyklz/Ncns_Theory.pdf?rlkey=3talrjlyq4v2zdxnozv9dzsim&st=7j7r4x4y&dl=0) for a graphical illustration. When restricting to two clusters, this leads to bounding $I_1$ by two triple sums $\\sum_{i\\in \\mathcal{C}\\_1}\\sum_{i'\\in \\mathcal{C}\\_2}\\Sigma_{ii'}^+\\sum_{\\ell'\\in \\mathcal{C_1}}W_{\\ell i'}$ and $\\sum_{i\\in \\mathcal{C}\\_2}\\sum_{i'\\in \\mathcal{C}\\_1}\\Sigma_{ii'}^+\\sum_{\\ell'\\in \\mathcal{C_2}}W_{\\ell i'}$. The outermost summation in each triple (over $i$) produces terms proportional to the cluster sizes $|\\mathcal{C}\\_1|$ and $|\\mathcal{C}\\_2|$, whose sum adds up to $R$ (the number of regions). As such, the sum of all units in the other clusters is accounted by the factor $R$ rather than terms that depend only on the boundary regions. \n\n>Theoretical claim 2 & Question 2\n\nThree conditions are needed to consistently estimate covariance:\n\n* Each $g_i$ can be consistently estimated;\n* Each error $e_i$ is additive, i.e., independent of the covariates and treatment;\n* The error-covariates pairs are independent across experiments. \n\n*Note*: The independence condition (3) can be relaxed to certain mixing condition that allows for temporal dependence, provided the dependence decays sufficiently quickly over time (Bradley, 2005, Probability Surveys).\n\n>Theoretical Claims 3\n\nThere are some differences between the two approaches, which we clarify below. In our proposal, we remove only the high-order interference term, and keep the first-order interference term in the objective function. To the contrary, Viviano et al imposes a weak interference assumption that removes all relevant interference terms when calculating the worst-case variance (see their proof of Lemma 3.2).\n\n>New experiments\n\nThe baselines' inferior performance partially stems from their reliance on IS, while our method, ID and GD employ DR. To mitigate this effect, we conducted a new experiment by increasing variance of the random error, so as to reduce the impact of variance reduction by DR. [Results](https://www.dropbox.com/scl/fi/8rtxjnuj58an93z5pbc94/Ncns_Experiment2.pdf?rlkey=mueh74ksm8lxlao76w6ywwffu&st=lxfsa0yy&dl=0) show that the modification reduces (but does not close) the performance gap between our method and the baselines compared to Figs 5 & 6. \n\nMeanwhile, we conducted another experiment under a combination of (i) various covariance structures, (ii) the magnitude of correlation $\\rho$, and (iii) the number of grids $R$ to report the contributions of SC, $I_1$, $I_2$. [Results](https://www.dropbox.com/scl/fi/x1wk3ck2x9goq2rphcrwu/Ncns_Experiment3.pdf?rlkey=rvgdg0n86i3r4ox5u1essfiii&st=53swq9tn&dl=0) suggest that $I_2$ can be proportional to $I_1$. This is because the plots visualize the MSE of our estimated optimal design rather than the oracle optimal design. Since our objective function involves only $I_1$ and not $I_2$, it reduces $I_1$ by increasing $I_2$, making $I_2$ comparable to $I_1$.\n\n>Question 1\n\nWill revise the definition as an average over $R$ regions to maintain consistency with the literature.", "claims_and_evidence": "The paper makes three claims relating their method to the literature. I find the claims that their method is more adaptable to correlation structures and computationally efficient reasonable and an interesting contribution. I find the claim that the paper offers a method that is more flexible and better suited for moderate/large interference effects than the literature (Viviano et al. 2023) more nuanced. \n\n1. The paper would benefit by being more clear in how their assumptions relate to Viviano et al. 2023 and in particular how their objective differs from Viviano et al. 2023. In their paper both bias and variance are considered and some of their results and assumptions are aimed at minimizing bias, which may differ from the MSE goal of this paper.\n\n2.  The paper considers a setting in which repeated experiments are available. The paper should be more clear about what is gained by having repeated experiments and distinguish the improvements from having repeated experiments versus not having them and their method versus the literature.", "methods_and_evaluation_criteria": "The proposed method is sensible and the evaluation criteria (MSE) and simulations exercises are well suited to study this topic. However, usually in the literature there is a focus on the bias-variance trade off, and it is well known that  \n\n\"The choice of clustering must balance two competing objectives: the larger the clusters (and the smaller\nthe number of clusters), the smaller the bias of the estimated global effect, but the larger its\nvariance.\"  (Viviano et al. 2023)\n\nWhile focusing on the MSE is intuitive, usually the worry with interference is that it will bias our estimator of interest and so commenting on the bias of different designs would be helpful. If the estimator is unbiased regardless of the interference pattern or if the bias is the same regardless of the assignment mechanism it would be useful to clarify this.", "theoretical_claims": "The theoretical results are well stated and the proofs appear mostly correct. However, I have a couple questions/comments for which I need further clarification.\n\n1. The $I_1$ term of Theorem 1 depends on the correlation between units at the boundary of one cluster with all other units in the other cluster. I was surprised to see that this can be upper bounded by a term that depends only on the boundary regions of each cluster (as $W_{ii}$ ensures in formula (2)). \n\n2. It would be helpful to state if there are any restrictions between O, g, and the error term e. Under which conditions should we expect algorithm 1 to consistently estimate all the elements in the covariance matrix? Are we ruling out that the nature of the interference is similar to the error correlation structure?\n\n3. The paper claims that the results dont require the fraction of boundary points to go to zero, but then ignores $I_2$ wouldnt this be a similar assumption to Viviano et al?", "experimental_designs_or_analyses": "The simulation design is sound. However, I have the following comments:\n\n1. Figure 5 and Figure 6 suggest that the main improvement is to use repeated measurements. More discussion on whether the other methods used for comparison benefit from repeated measurements or not and why the differences are so stark would be helpful in understanding the benefits of the proposed method, specially given that ID and GD perform so much better than the other methods too.\n\n2. It might be helpful to have a simulation design for which we expect the other methods proposed in the literature to work to compare with the proposed method.\n\n3. Might be helpful to split MSE into the SC, $I_1$ and $I_2$ to see the contribution of each term.", "relation_to_broader_scientific_literature": "Relative to the broader literature, and in particular Viviano et al. 2023, the paper provides a computationally efficient method that uses the error correlation structure to improve the MSE performance of ATE estimators by utilizing repeated experiments. This is new and interesting contribution to the literature when repeated experiments are available, but its specific merits should be further clarified.", "essential_references_not_discussed": "The paper considers the key references in the literature.", "other_strengths_and_weaknesses": "I enjoyed reading the paper, it is well written, clear and provides a new interesting method.", "other_comments_or_suggestions": "The paper has a few typos: \n\n1. Bracket in 172.\n2. Independently in 212\n3. Clarifying that the boundary of the set $\\mathcal{C}$ is with other clusters.\n4. In Assumption 2 \"such that only\"\n5. Capital W in 373\n6. Plots in Figure 5 and 6 show same estimators in different colors which is confusing", "questions_for_authors": "Beyond the comments above:\n\n1. The definition of ATE is a bit odd in that it is not the average over $R$ but the sum. Might be good to comment on this as other papers, like Viviano et al. 2023, consider the average and do the asymptotics with respect to R.\n2. What are the assumptions on $O_i$. Should we expect that it is independent across experiments? Same question with $e_i$.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tQ9iqKofxm", "reviewer": "Reviewer_96AW", "summary": "This paper proposes a graph cut approach for design of spatial experiments to estimate Average Treatment Effect (ATE) in settings with both interference where SUTVA assumption does not hold as well as when there exists correlation between units. The authors present a method which builds flexible surrogate function for the Mean Squared Error (MSE) of the ATE estimator. Both theoretical empirical results corresponding to the proposed approach is presented.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We sincerely appreciate your thoughtful review and valuable feedback on our work. Your positive assessment is particularly encouraging to us. Below, we provide detailed responses to each of your comments.\n\n> **Real data analyses**\n\nWhile we do have a real-world dataset, it cannot be directly used for evaluation. To properly assess a given design, one would need to: (1) implement the design to generate corresponding data, and (2) compute the MSE from this generated data. This is precisely why we developed our real-data-based simulator, which enables adaptive data generation tailored to different experimental designs for  comparison.\n\nDuring the rebuttal, we identified another publicly available real-world dataset that examines the causal effect wind speed on PM10 levels [1]. However, as with our ridesharing dataset, this raw observational data cannot be directly used for evaluation. We therefore employed the simulation model from [1] to generate synthetic data under different designs. Our simulation results, visualized in [Figure](https://www.dropbox.com/scl/fi/usk0pcpv7h615634c8b4k/Lhaw_pm10.pdf?rlkey=qkabneg3idllwi4xc4zje89e9&st=wt8kuzxu&dl=0), demonstrate that our method achieves significantly lower MSEs compared to existing designs.\n\n> **Rationality of the synthetic outcome model (line 906)**\n\nOur outcome regression function follows the nonparametric model from [2] (Page 24), which studied the spatial A/B testing problem as well. We selected this model for two reasons: First, the outcome is a complex nonlinear function of observations, treatments, and spillover effects. Second, it naturally incorporates spatial heterogeneity through latitude/longitude coordinates, allowing for geographic variation. We consider these  features to approximate the complex dynamics present in real-world settings.\n\n> **Limitations**\n\nThere are a couple of limitations of our proposal:\n\n* Theoretically, our characterization of the interference-correlation trade-off relies on the assumption of non-negative covariance functions. While in practice we expect the presence of some negative covariances would not alter our conclusions, it remains unclear how to elegantly relax this mathematical constraint while preserving our theoretical findings.\n\n* Methodologically, we omit the second-order interference term in the objective function to facilitate the optimization. We acknowledge that such higher-order effects may be non-negligible. However, its inclusion would significantly increase the optimization complexity. Developing a computationally tractable solution that properly accounts for this term remains a practical challenge for future work. \n\n* In terms of applications, our methodology primarily targets experimental settings where independent experiments can be repeatedly conducted over time. While this framework aligns well with our ridesharing application for spatial A/B testing (the focus of this paper), it may require adaptation for other settings. We have discussed modifications for scenarios with either a single experiment or multiple experiments with carryover effects in our response to Reviewer VLbx. Extending our approach to more general experimental settings would be a valuable direction for future research. \n\n> **Typos**\n\nThanks for pointing them out. They will be corrected. \n\n[1] Zhang, W., et al. Spatial Interference Detection in Treatment Effect Model. \n\n[2] Yang, Y., et al. Spatially Randomized Designs Can Enhance Policy Evaluation.", "claims_and_evidence": "To my understanding, the claims made in the paper are well supported with both theory and methodology. Experiments on real data simulators are welcome.", "methods_and_evaluation_criteria": "The proposed method is interesting and certainly relevant for the problem at hand. Evaluation criteria seems fair with multiple different baselines included.", "theoretical_claims": "I did not check in detail the correctness of proofs.", "experimental_designs_or_analyses": "The experimental design and analyses on both synthetic data and simulator seem quite interesting and sound. The paper would have probably benefited if there was real data that could have been tested on.\nOne of the clarifications I would appreciate is for synthetic data how the outcome equation was chosen (line 906). Is it standard in prior works or is it based on some heuristic?", "relation_to_broader_scientific_literature": "Although I am not too familiar with broader scientific literature in this field, this paper proposes a method which can account for both interference and correlation between units in policy evaluation setting which I believe is not widely addressed in literature before. Although the proposed approach is simple, it addresses a problem which is practically relevant. Some of the prior works require SUTVA assumption.", "essential_references_not_discussed": "I think the paper does a good job in discussing the related literature.", "other_strengths_and_weaknesses": "I think the paper does a good job of exposition of the idea and also the setting. However, I think it would be great if some of the limitations of the present approach was discussed in the paper. For example, the algorithmic complexity when the interference/ correlation is high, possible limitations of design procedure itself in practical settings and so on.", "other_comments_or_suggestions": "In figure 5 (b) it should be number of \"repetitions\".", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4ODV0KKNdr", "reviewer": "Reviewer_Lhaw", "summary": "This paper studies optimal cluster-randomized designs for spatial A/B testing problems. The authors investigate the decomposition of the mean squared error (MSE) and show that interference and correlation are two key driving factors, contributing in opposite directions: when interference is strong, it is optimal to assign the same policies to neighboring regions, whereas strong correlation favors assigning different policies. They also propose a computationally efficient surrogate function for the MSE, which adapts to varying levels of interference and correlation structures. Combined with a graph cut algorithm, the surrogate function effectively learns the optimal design, as demonstrated by both theoretical analysis and experimental results.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": ">Applications to other data examples\n\nWe sincerely appreciate your valuable feedback. In response, we conducted extensive investigations during the rebuttal, including: (1) empirical validation on additional data, (2) methodological extensions, (3) theoretical investigations. The methodological  investigation is elaborated in our response to Reviewer VLbx.\n\n**Empirical validation on environmental data**. During rebuttal, we found a paper that studies the causal effect of wind speed on PM10 levels (Zhang et al., 2024, arXiv:2409.04836, Section 6). As the raw dataset cannot be directly used for evaluation (refer to our first response to Reviewer 96AW), we utilized the simulator described in their paper for comparison. The results, shown in [Figure](https://www.dropbox.com/scl/fi/usk0pcpv7h615634c8b4k/Lhaw_pm10.pdf?rlkey=qkabneg3idllwi4xc4zje89e9&st=aei7qaq2&dl=0), demonstrate our proposal achieves smaller MSEs compared with the benchmarks, confirming its applicability to environmental applications. \n\n**Methodological extensions**. Our primary focus is Example 1, but we have extended our design to handle two additional settings: (i) a single-experiment setting without repeated measurements and (ii) a multi-experiment setting allowing the carryover effects over time. For the single-experiment setting, our approach remains effective given prior knowledge of the covariance structure, as confirmed by our newly conducted numerical study. For multi-experiment settings with carryover effects, we have outlined the methodology while reserving its implementation for future work, as detailed in our response to Reviewer VLbx. Collectively, these extensions enable our framework to accommodate the applications described in Examples 2 and 3. \n\n**Theoretical investigation**. We have identified crucial assumptions that guarantee the validity of our proposed extension in the multi-experiment setting (ii). Specifically, we would require a Markov assumption (Puterman, 2014, John Wiley & Sons) and a temporal mixing condition (Bradley, 2005, Probab. Surv.) to maintain the covariance estimator's consistency in the presence of temporal dependencies. Similar conditions are widely employed in the RL literature for consistent estimation (Kallus and Uehara, arXiv:1909.05850).\n\n>Covariance assumption\n\nWe have comprehensively addressed your concern in the following three ways: First, we conducted extensive empirical validation under violations of the covariance assumption. Second, we clarified the role of the non-negativity assumption. Third, we developed methodological extensions for scenarios where Assumption 2 fails to hold.\n\n**Numerical experiments**: We conducted **another new experiment** during rebuttal to illustrate the robustness of our proposal. We design a periodic covariance function $\\Sigma_{ij} = 1 - \\rho \\times ((i - j)\\mod 3)$. Under this choice, the decaying covariance assumption no longer holds and the non-negativity assumption is violated when $\\rho>0.5$. The results, shown [here](https://www.dropbox.com/scl/fi/n08067ujhj9if8fru1gq1/Lhaw_PeriodCov.pdf?rlkey=z6mo09pntxihowq295b64cuax&st=o8jrb7g2&dl=0), demonstrate that our methods still outperform baselines.\n\nWe also remark that in both our **ridesharing simulator** and the **PM10 dataset** (see our first response), we find violations of the two assumptions. Nonetheless, our designs remain highly competitive. These results consistently demonstrate our proposal's robustness. \n\n**Non-negativity**: The non-negative assumption is primarily employed in Prop. 1 & 2 to demonstrate the trade-off between interference and correlation. It is not required to ensure the proposed surrogate function forms a valid upper bound (Prop. 3).\n\n**Methodological extension**: While the decaying covariance assumption (Assumption 2) is common in spatial statistics (Cressie, 2015), our method remains flexible when this condition is violated. In such cases, we propose a simple fix: scaling the first term in loss function (2) by a constant $C > 1$ to ensure it remains an upper bound. The hyperparameter can be optimally determined through simulation studies based on experimental data evaluating the performance of the resulting estimator across different $C$ values.\n\n>MSE of ID in Figure 5(b)\n\nYour are right that the **asymptotic** MSE of ID shall remain constant regardless of the number of repetitions $N$. However, in **finite sample**, the MSE actually improves with $N$, due to the estimation of the $g$ function. \n\nSpecifically, in theory, Neyman orthogonality guarantees that the asymptotic MSE will match that with an oracle g given sufficiently large $N$. In practice, we estimate $g$ by incorporating all prior data at each experiment. This leads to an initial period where the MSE decreases as $N$ increases, reflecting the improvements in the estimation of $g$. As the estimated $g$ approaches its oracle value, the MSE then stabilizes. The trend shown in Figure 5(b) clearly demonstrates this pattern.", "claims_and_evidence": "The claims regarding the contributions in spatial A/B testing problems make sense to me, however, I believe the authors should provide detailed discussions if they would like to claim their method also *is readily adaptable to Example 2: Environmental and epidemiological applications* and *Example 3: Experimentation in social networks.*", "methods_and_evaluation_criteria": "They make sense to me, but I would appreciate it if the authors could conduct more experiments on real-world datasets.", "theoretical_claims": "I reviewed the proof of Theorem 1, and it appears sound to me.", "experimental_designs_or_analyses": "Some of the simulation results make me worry about their credibility. Below, I list the concerns that I hope the authors can address in their response:\n- In Figure 5(b), the MSE of the ID method also improves as the number of repetitions increases. Intuitively, however, it should remain the same, since it is always an individual design. Could the authors clarify this behavior?\n- The theoretical results rely heavily on assumptions about the covariance matrix $\\Sigma$. For example, the surrogate function is valid only when all entries are non-negative, and Assumption 2 requires a decaying covariance structure. I would like to know how the authors handle cases where the estimated covariance $\\hat{\\Sigma}$ does not satisfy these conditions. How does the algorithm deal with such situations, and what is the expected performance of the proposed method in these cases?", "relation_to_broader_scientific_literature": "This paper is related to causal inference and experimental design with spatial interference.", "essential_references_not_discussed": "I don't see any obvious missing references.", "other_strengths_and_weaknesses": "- Strengths: The paper is generally well written and easy to follow. The trade-off between interference and correlation is clearly articulated within the studied setting. Additionally, the intuition behind the design of the surrogate function is reasonable and well motivated.\n\n- Weaknesses: My main concern lies in the assumptions made by the paper. Specifically, Assumption 2 and the conditions in Propositions 1 and 2 regarding the covariance matrix $\\Sigma$ may limit the applicability of the proposed method. In theory, when these assumptions are violated, the trade-off between interference and correlation, as well as the surrogacy result in Proposition 3, no longer hold. In practice, it is unclear how the proposed method performs when the estimated covariance matrix $\\hat{\\Sigma}$ does not satisfy these conditions. Clarification or empirical evaluation in such scenarios would strengthen the paper.", "other_comments_or_suggestions": "In line 172, the right square bracket is misplaced.", "questions_for_authors": "Please see my comments above in *Experimental Designs Or Analyses* and *Other Strengths And Weaknesses*.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors consider the spatial interference problem for causal inference. The key observation is a graph-cut based experimental design that uses MSE decompositon in terms of intrinsic variance and spatial effects. They propose an experimental design algorithm based on these observations and evaluate their method via simulations and a real world simulator.  

One expert reviewer is concerned about the assumption that the authors are performing the same experiment multiple times, calling it a very strong assumption on multiple levels. Unfortunately, the reviewer did not explicitly comment on the author's rebuttal nor participated in the AC discussions. Based on my own reading of the authors' rebuttal to the reviewers' comments, I can say that they did a good job. The authors emphasize the difference between spatial and network interference settings. They also suggest that their method can handle the single-experiment setting, so long as some additional assumptions are satisfied. Finally, they provide additional experimental results to supplement these claims.  

The other critical reviewer was concerned about the assumptions that led to the theory. The authors, in their rebuttal, conducted additional experiments testing the robustness of their method to relaxations of this assumption. The reviewer did not respond to the authors nor participated in the AC discussions but I find the authors' reply satisfying for the questions raised by this reviewer. 

The positive reviewers appreciated the contribution, such as computational efficiency relative to related work, and clarity of writing. Even the reviewers with weak reject scores acknowledged the contribution of the paper.
Decision: Accept (poster)