Clustered Switchback Designs for
Experimentation Under Spatio-temporal Interference

Our main theorem states that a truncated HT estimator achieves an MSE of $1/NT$ times a \cyreplacesome combinatorial parameters that involve $\Pi$ and the interference graph $G$; see Theorem 1.graph clustering-dependent quantity which is $O(1)$ for low-degree graphs for good clusterings, e.g., growth restricted graphs (Ugander et al., 2013) or spatially derived graphs (Leung, 2022). This result bridges the literature on experimentation with spatial/network interference and temporal interference by extending the following results:

1. 1.

   Pure switchback experiments. Hu and Wager (2022) independently obtained a $\tilde{O}(t_{\rm mix}/T)$ MSE rate for $N=1$. Our Theorem 1 generalizes this result to the $N$-individual setting, using a different class of estimators. We discuss the comparison with their work in Section 3.

2. 2.

   Network interference. Assuming that the interference graph satisfies the $\kappa$-restricted growth condition (defined in Section 4), Ugander et al. (2013) showed that the HT estimator achieves an MSE of $\tilde{O}({\color[rgb]{0,0,0}2^{{\kappa^{6}}}}d/N)$ for $T=1$ with a suitable partition (graph clustering), where $d$ is the maximum degree. Moreover, by introducing randomness into the clustering, Ugander and Yin (2023) improved the exponential dependence on $\kappa$ to polynomial, achieving a $\tilde{O}(d^{2}\kappa^{4}/N)$ MSE. Our Corollary 4 generalizes this to $\tilde{O}(d^{2}\kappa^{4}t_{\rm mix}/NT)$ in the presence of Markovian temporal interference.

We state our results under the $\delta$-fractional neighborhood exposure ($\delta$-FNE) as introduced in Ugander et al. (2013); Eckles et al. (2017b), generalizing beyond the “exact” (i.e., $\delta=0$) neighborhood interference assumption. We summarize our results (with $\delta=0$ for simplicity) in Table 2.

We emphasize that our setting, even for $N=1$, can not be reduced to that of Leung 2022. Essentially, this is because their independence assumptions no longer holds here. We will provide more details in a dedicated discussion section Section 3.2.

Many existing works that tackle this problem assume that interference is summarized by a low-dimensional exposure mapping and that individuals are individually randomized into treatment or control by Bernoulli randomization (Manski, 2013; Toulis and Kao, 2013; Aronow et al., 2017; Basse et al., 2019; Forastiere et al., 2021). Some work departed from unit-level randomization and introduced cluster dependence in unit-level assignments in order to improve estimator precision, including Ugander et al. 2013; Jagadeesan et al. 2020; Leung 2022, 2023, just to name a few.

There is another line of work that considers the temporal interference (or carryover effect). Some works consider a fixed bound on the persistence of temporal interference (e.g., Bojinov et al. (2023)), while other works considered temporal interference arising from the Markovian evolution of states (Glynn et al., 2020; Farias et al., 2022; Johari et al., 2022; Shi et al., 2023; Hu and Wager, 2022; Li and Wager, 2022; Li et al., 2023). Apart from being limited to the single-individual setting, many of these works differ from ours either by (i) focusing on alternative objectives, such as stationary outcome Glynn et al. (2020), or (ii) imposing additional assumptions, like observability of the states Farias et al. (2022).

Consider a horizon with $T$ rounds and $N$ individuals, where each individual is randomly assigned to treatment (“1”) or control (“0”) at each time. We model the interference between individuals using an interference graph $G=(U,E)$ where $|U|=N$ and each node represents an individual. Formally, the treatment assignment is given by a binary matrix $W\in\{0,1\}^{N\times T}$. \cydeleteAlthough it may sometimes be reasonable to assign the treatments in each round adaptively, We focus on non-adaptive designs where $W$ is drawn at the beginning and hence is independent of all other variables, including the individuals’ states and outcomes.

To model temporal interference, we assign each individual $i\in U$ a state $S_{it}\in\mathcal{S}$ at time $t\in[T]:\{1,2,\dots,T\}$ that evolves independently in a Markovian fashion. The transition kernel is a function of the treatments of $u$ and its direct neighbors in $G$ at time $t$, which we refer to as the \cyeditinterference neighborhood of $u$, denoted ${\cal N}(i):=\{i\}\cup\{i\in U\mid(i,j)\in E\}$. The state at time $t+1$, $S_{i,t+1}$, is drawn from a distribution $P_{it}^{W_{{\cal N}(i),t}}(S_{i,t+1}\in\cdot\mid S_{it})$. We allow $P_{it}^{w}$ to vary arbitrarily across different combinations of $i,t$ and $w\in\{0,1\}^{{\cal N}(i)}$.

An observed outcome $Y_{it}\in\mathbb{R}$ is generated as a function of (i) the unit’s state and (ii) the treatments of itself and its neighbors, according to

where $\epsilon_{it}$ has mean zero. The \cyeditconditional mean outcome $\mathbb{E}[Y_{it}\mid W]$ is determined by $\mu_{it}:\mathcal{S}\times\{0,1\}^{{\cal N}(i)}\to[0,1]$, which we call the outcome function. The model dynamics are thus specified by the sequence

We emphasize that we do not assume observation of the state variables.

Given the observations (consisting solely of $W,Y$), our objective is to estimate the difference between the \cyeditcounterfactual outcomes under continuous deployment of treatment $1$ and treatment $0$, averaged over all individuals and rounds, referred to as the Global Average Treatment Effect.

If the Markov chains are rapid-mixing (defined soon), then $\cal D$ “matters” only by a lower-order term compared to the MSE (see Proposition 1), and we will thus suppress $\cal D$. We also want to point out that our results still hold if “${\bf 1}$” and “${\bf 0}$” are replaced with an arbitrary pair of fixed treatment sequences.

A key assumption as introduced in Hu and Wager (2022) that allows for estimation despite temporal interference is rapid mixing:

As a convenient consequence, the initial state distribution does not matter much.

The above implies that the error caused by misspecifying the initial distribution is $\tilde{O}(1/NT)$, and thus it contributes only a $\tilde{O}(1/(NT)^{2})$ term to the MSE. This is of lower order compared to our MSE bound, which scales as $1/NT$, as we will soon see.

We assume that the mean-zero noise $\epsilon_{it}$ \cyreplaceindependenthave zero cross-correlation and bounded \cyreplacecorrelationvariance:

We state our results under the $\delta$-Fractional Neighborhood Exposure ($\delta$-FNE) mapping as introduced in Ugander et al. (2013); Eckles et al. (2017a); the neighborhood interference assumption is the special case when $\delta=0$. For concreteness, the reader may assume $\delta=0$ without losing sight of the main ideas.

We focus on \cyeditclustered switchback designs, which specify a distribution for sampling the treatment vector $W$ given a fixed clustering over the network.

We independently assign treatments to the cluster-timeblock product sets uniformly.

We consider a class of Horvitz-Thompson (HT) Horvitz and Thompson (1952) style estimators under a misspecified radius-$r$ exposure mapping, similar to that of Aronow et al. (2017); Leung (2022); Sävje (2024).

Note that as in previous literature, $Y_{it}$ and $X_{ita}^{r}$ are not independent, as they both depend on the treatments in the $r$ rounds before $t$. The truncated HT estimator was proposed in the spatial interference setting (Leung, 2022), and utilizes the framework of misspecified exposure mappings introduced by Aronow et al. (2017); Sävje (2023).

The following will be useful when stating our results in the general form.

The reader should not confuse dependence graph with interference graph. The former is, in fact, always a supergraph of the latter. For example, if each cluster in $\Pi$ is a singleton, then the dependence graph is the second power of the interference graph.

The dependence graph has the following useful property: If $(i,i^{\prime})\notin E_{\Pi}$, then $i,i^{\prime}$ do not intersect any common cluster, and hence their outcomes and exposure mappings are independent.

This result is the consequence of the following facts: (1) $\widehat{\Delta}_{it}^{r}$ only depends on the treatments of the clusters that intersect $N(i)$, (2) $i\not\perp\!\!\!\perp i^{\prime}$ implies ${\cal C}_{i}\cap{\cal C}_{i^{\prime}}=\emptyset$ where ${\cal C}_{i}$ denotes the collection of clusters that $i$ intersects, and (3) the treatments are independently assigned to each cluster.

The is reminiscent of the decaying interference assumption in Leung 2022 (albeit on distributions rather than realizations), which inspires us to consider a truncated HT estimator as considered therein. However, their analysis is not readily applicable to our Markovian setting, since their potential outcomes are deterministic.

Recall that $i\not\perp\!\!\!\perp i^{\prime}$ if $(i,i^{\prime})\in E_{\Pi}$ where $E_{\Pi}$ is the set of edges of the independence graph induced by $\Pi$.

In Section 4 we will further simplify the above by considering natural classes of graphs.

Taken together, we deduce that for any fixed $\Pi$, we have:

We will soon see that for “sparse” graphs or geometric graphs, the summation becomes $O(N)$, and thus the MSE becomes $\tilde{O}(1/NT)$.

We address some questions that the readers may have at this point.

Proposition 3 provides insights on how to select the best $r$ specific to this $\ell$. For example, consider $N=1$ and $\ell=1$. Then, Propositions 2 and 3 combined lead to an MSE of $T^{-t_{\rm mix}/(t_{\rm mix}+O(1))}$ if

So far, we have stated our Theorem 1 in terms of the minimal exposure probabilities $p_{i}^{\rm min}$. Intuitively, smaller values of these probabilities lead to higher variance and worse MSE bounds. We next present lower bounds on these probabilities in $\delta$ (as in the $\delta$-FNE, see 3).

To see the intuition, consider $T=1,d_{\Pi}(i)=5$ and $\delta=0.2$. For simplicity, assume that all clusters intersecting ${\cal N}(i)$ have the same cardinality. Then, the exposure mapping $X_{ita}^{r}$ equals $1$ if at least $(1-0.2)\times 5=4$ of these clusters are assigned $a$. Thus, the exposure probability is

Therefore, there is a $18.25\%\times 2=37.5\%$ probability (multiplying by two to account for both $a=0$ and $1$) that we will keep each data point. More generally, by Stirling’s formula, for any $\delta\geq 0$ s.t. $\delta d$ is an integer,

It follows that

Our Theorem 1 states that the optimal MSE rate is achieved when the block length and HT radius are both $O(t_{\rm mix}\log T)$. We next show the efficacy of this design-estimator combination through experiments.

Next, we show that in the presence of both spatial and temporal interference, clustered switchback outperforms both “pure” switchback (i.e., only partition time) and “pure” A/B test (i.e., only partition space).

MDP. Suppose that $N$ units lie on an unweighted line graph. Each unit’s state follows the random walk capped at $\pm m=\pm 30$, similar to the single-user setting. To generate spatial interference, we assume that the move-up probability $p_{\rm up}(i,t)$ of $u$ at time $t$ is

In particular, if all $h$-hop neighbors are assigned treatment $0$ (resp. 1), then $p_{\rm up}=0.1$ (resp. $0.9$). In this setting, the exposure mapping for treatment $a$ is equal to $1$ if and only if all $h$-hop neighbors are assigned $a$ in the previous $r$ rounds. As suggested by Corollary 5, we choose $r=30\log(NT)$.

Benchmarks. We partition the space-time $[N]\times[T]$ into “boxes” of (spatial) width $w$ and (temporal) length $\ell$. We will compare the performance of the HT estimator under the following designs.
(1) Pure Switchback Test: $w=N,\ell=30\log T$ (rate optimal block length for switchback).
(2) Pure A/B Test: $w=h$ (rate optimal width for pure A/B test, see Corollary 5), $\ell=T$.
(3) Clustered Switchback Test: $\ell=30\log T,w=h$ (rate optimal width and length).

Discussion. For each $T$, we randomly generated $100$ instances and $200$ treatment vectors. When $N=T$, the MSE of clustered switchback decreases most rapidly. The slope of its curve in the log-log is $-1.89$, close to the theoretical value $-2$. It also outperforms the other two designs in the other two scenarios.

Finally, let us compare pure A/B with pure switchback. Theoretically, they have MSE rates of $1/N$ and $1/T$. Consistent with this, our empirical study shows that the MSE of pure A/B test decreases slower than pure switchback when $N=\sqrt{T}$, and faster when $N=T^{2}$.

We repeat the five-curve comparison for different choices of $m$. Recall that in the main body we choose $m=30$. We now choose $m=30$ and $m=100$, respectively. As a key observation, we found that the performance of HT-small is heavily based on $m$: It works well for small $m$ and not for large ones. This is because the mixing time is almost linear in $m$, so for large $m$, we need more time for the chain to mix sufficiently. But this is difficult for a small block length. In fact, the exposure probability is $O(2^{-{t_{\rm mix}/\ell}})$. So, when $m=300$ and $\ell=8$, we have $t_{\rm mix}/\ell>m/\ell=37.5$. This means that the exposure mapping discards most of the data points, leading to a high variance.