Adaptive Policy Learning Under Unknown Network Interference
Authors: Aidan Gleich, Eric Laber, Alexander Volfovsky
Summary
The authors tackle adaptive experimentation when units influence each other through an unknown social network: you want to simultaneously learn who affects whom and allocate treatments to maximize cumulative reward. They propose a Thompson sampling algorithm with a Gibbs sampler that jointly infers the interference graph and picks individual-level treatment assignments, returning both an optimized policy and an estimate of the network for downstream causal analysis. Theoretical regret bounds are sublinear in time and linear in network size for additive spillover models, and empirically the method beats baselines by more than an order of magnitude.
Main takeaways:
- Existing methods either assume the interference network is fully known or randomize at the cluster level; this learns the network structure on the fly
- For additive spillover, proves Bayesian regret √(nT · B log(en/B)) for exact posterior sampling; Gibbs approximation achieves comparable sublinear regret
- Also analyzes a general neighborhood-interference variant with explore-then-commit, incurring O(n² log T) graph-discovery cost
- Returns both an optimized treatment policy and a network estimate usable for estimating direct, indirect, and total treatment effects
- On two real-world networks, achieves sublinear regret and small root-mean-square errors for downstream effect estimates
Relevance
Not directly related to my persona-installation or marker-implantation work. Included because it's a useful methodological reference if I ever need to run adaptive experiments under unknown interference (e.g., testing persona leakage across related system prompts).
Abstract
arXiv:2605.11191v1 Announce Type: new Abstract: Adaptive experimentation under unknown network interference requires solving two coupled problems: (i) learning the underlying dynamics of interference among units and (ii) using these dynamics to inform treatment allocation in order to maximize a cumulative outcome of interest (e.g. revenue). Existing adaptive experimentation methods either assume the interference network is fully known or bypass the network by operating on coarse cluster-level randomizations. We develop a Thompson sampling algorithm that jointly learns the interference network and adaptively optimizes individual-level treatment allocations via a Gibbs sampler. The algorithm returns both an optimized treatment policy and an estimate of the interference network; the latter supports downstream causal analyses such as estimation of direct, indirect, and total treatment effects. For additive spillover models, we show that total reward is linear in the treatment vector with coefficients given by an $n$-dimensional latent score. We prove a Bayesian regret bound of order $\sqrt{nT \cdot B \log(en/B)}$ for exact posterior sampling; empirically, our Gibbs-based approximate sampler achieves regret consistent with this rate and remains sublinear when the additive spillovers assumption is violated. For general Neighborhood Interference, where this reduction is unavailable, we analyze an explore-then-commit variant with $O(n^2 \log T)$ graph-discovery cost. An information-theoretic $\Omega(n \log T)$ lower bound complements both results. Empirically, our method achieves more than an order-of-magnitude reduction in regret in head-to-head comparisons. On two real-world networks, the algorithm achieves sublinear regret and yields downstream effect estimates with small RMSE relative to the truth.