Experimentation Under Non-stationary Interference
Su Jia, Peter Frazier, Nathan Kallus, Christina Lee Yu · 2025
Read Experimentation Under Non-stationary Interference by Su Jia, Peter Frazier, Nathan Kallus, Christina Lee Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06685.txt.
Introduction
Su Jia, Peter Frazier, Nathan Kallus, and Christina Lee Yu estimate treatment effects when experimental units interfere with each other through a network that itself keeps changing. Ride-sharing drivers move, social ties form and dissolve, and yesterday's interference map is stale today. Randomized trials in such settings need estimators that respect the moving structure.
Their main result shows a truncated Horvitz-Thompson estimator whose error shrinks linearly with the number of space and time blocks, scaled by the average complexity of the interference graphs. A fine-grained covariance bound decays exponentially with time since two points last interacted, a key contrast with static analyses. Simpler corollaries follow for points moving in space and for dynamic random graph models.
Catalog record
| CREATOR | Su Jia, Peter Frazier, Nathan Kallus, Christina Lee Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06685
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Experimentation Under Non-stationary Interference Su Jia, Peter Frazier, Nathan Kallus, Christina Lee Yu Abstract We study the estimation of the average treatment effect (ATE) in randomized controlled trials under a dynamically evolving interference structure. This setting arises in applications such as ride-sharing, where drivers move over time, and social networks, where connections continuously form and dissolve. In particular, we focus on scenarios where outcomes exhibit spatio-temporal interference driven by a sequence of random interference graphs that evolve independently of the treatment assignment. Loosely, our main result states that a truncated Horvitz-Thompson estimator achieves an MSE that vanishes linearly in the number of spatial and time blocks, times a factor that measures the average complexity of the interference graphs. As a key technical contribution (that contrasts the static setting 10 ), we present a fine-grained covariance bound for each pair of space-time points that decays exponentially with the time elapsed since their last “interaction”. Our results can be applied to many concrete settings and lead to simplified bounds, including where the interference graphs (i) are induced by moving points in a metric space, or (ii) follow a dynamic Erdos-Renyi model, where each edge is created or removed independently in each time period. 1 Introduction Experimentation under interference — that is, when the Stable Unit Treatment Value Assumption (SUTVA) ( 21 ) is violated — poses a fundamental challenge in modern experimentation: In many large-scale online environments such as marketplaces, the treatment assigned to one unit may affect the outcomes of others through shared resources, social connections, or platform algorithms. Ignoring such spillover effects can lead to biased estimates, invalid inference, and misguided product decisions. As a result, modeling and mitigating interference has become a central challenge in the design of trustworthy experimentation pipelines. Most existing work in this area focuses on either (1) a single-period setting where non-stationarity is irrelevant, or (2) a multi-period model with a static interference pattern, usually characterized by a graph. However, such assumptions can be restrictive for modern applications, where user behavior and network structure evolve over time. In real-world systems, interference can evolve as users enter or exit the platform, content recommendations adapt, or interactions become more or less frequent. These dynamic patterns make it essential to develop experimental methods that account for both temporal evolution and the fluid nature of the interference graph. We initiate a study of experimentation under a non-stationary interference. Non-stationarity is two-fold : We allow not only the outcome distributions to vary (across both space and time), but also the interference graph to evolve over time, independently of the treatments. More precisely, conditional on the interference graphs, the outcomes of each fixed individual follow a Markov reward process, whose state transitions may depend on the treatment of other individuals in the same time period. 1.1 Our Contributions We progressively show the following results on the Horvitz-Thompson (HT) estimator. 1. Covariance Bound for the HT Estimators. We establish a general covariance bound in terms of a novel quantity called the last interaction time (LIT). Specifically, we show that the covariance between the HT estimators of individual treatment effects decays exponentially with the time elapsed since their LIT ( Proposition 4.2 ). This is a key technical component for our main result and is of independent interest, as it holds for any experimental design (i.e. distribution over the treatment assignment matrix). 2. Bounding MSE Using the Average Cluster Degree. We present a general MSE bound for a broad class of designs, which we call vertical designs : Partition the time horizon uniformly into time blocks, then within each time block, partition the population into spatial blocks and assign treatment/control at the block level. We show that the MSE of the HT estimator is 1/NT times the average cluster degree , where the average is taken over all individuals and time blocks ( Theorem 4.8 ). Here, two individuals are called cluster-neighbors in a time block if their neighborhoods intersect the same spatial block, and the cluster degree of an individual is the number of cluster-neighbors. 1.2 Related Work Violation of SUTVA. Experimentation is broadly deployed in e-commerce that is simple to execute ( 13 ; 24 ; 14 ) . As a key challenge, the violation of the Stable Unit Treatment Value Assumption (SUTVA) has been viewed as problematic in online platforms ( 3 ) . 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 ( 19 ; 25 ; 1 ; 2 ; 6 ) . Some work departed from unit-level randomization and introduced cluster dependence in unit-level assignments in order to improve estimator precision, including 26 ; 9 ; 15 ; 16 , 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., 4 ), while other works considered temporal interference arising from the Markovian evolution of states ( 7 ; 5 ; 12 ; 22 ; 8 ; 18 ; 17 ) . 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 7 , or (ii) imposing additional assumptions, like observability of the states 5 . Spatio-temporal Interference. Although extensively studied separately and recognized for its practical significance, experimentation under spatio-temporal interference has received relatively limited attention previously. Recently, 20 attempted to address this problem, but their carryover effect is confined to one period. Another closely related work is 18 . Similar to our work, they specified the spatial interference using an interference graph and modeled temporal interference by assigning an MDP to each individual. In our model, the transition probability depends on the states of all neighbors (in the interference graph). In contrast, their evolution depends on the sum of the outcome of direct neighbors. Moreover, our work focuses on ATE estimation for a fixed, unknown environment, whereas they focus on the large sample asymptotics and mean-field properties. 27 studied direct treatment effects for panel data under spatiotemporal interference, but focused on asymptotic properties instead of finite-sample bounds. Off-Policy Evaluation (OPE) Since we model temporal interference using an MDP, our work is naturally related to reinforcement learning (RL). In fact, our result on ATE estimation can be rephrased as OPE ( 11 ; 23 ) in a multi-agent MDP: Given a behavioral policy from which the data is generated, we aim to evaluate the mean reward of a target policy. The ATE in our work is essentially the difference in the mean reward between two target policies (all-1 and all-0 policies), and the behavioral policy is given by clustered randomization. However, these works usually require certain states to be observable, which is not needed in our work. Moreover, these works usually impose certain assumptions on the non-stationarity, which we allow to be completely arbitrary. Finally, we focus on rather general data-generating policies (beyond fixed-treatment policies) and estimands (beyond ATE), compromising the strengths of the results. 2 Formulation We consider a multi-period model that captures both spatial interference and