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