📊 statistics

Adaptive Policy Learning Under Unknown Network Interference

This paper proposes a Thompson sampling algorithm that jointly learns unknown network interference dynamics and optimizes individual-level treatment allocations via a Gibbs sampler, achieving sublinear Bayesian regret and enabling accurate downstream causal effect estimation in adaptive experimentation settings.

Original authors: Aidan Gleich, Eric Laber, Alexander Volfovsky

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aidan Gleich, Eric Laber, Alexander Volfovsky

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a large social club. You have a limited budget to give out "treats" (like free coffee or discounts) to your members. Your goal is to make the club as happy and profitable as possible.

Here's the catch: You don't know exactly who talks to whom. In fact, you don't even know if giving a treat to one person affects their friends. Maybe if you give a treat to Alice, her friend Bob gets happy just by association. Or maybe if you give treats to both, they cancel each other out. This is called interference.

For a long time, scientists trying to solve this problem had to make a big guess: "Let's assume we already know the friendship map," or "Let's just treat whole groups of people at once so we don't have to worry about individuals." But in the real world, you often don't have the map, and treating whole groups is inefficient.

This paper introduces a new, smart way to handle this situation. Think of it as a detective who learns the map while playing the game.

The Problem: The "Blind" Manager

Usually, if you want to figure out the best way to give out treats, you need two things:

The Map: Who is friends with whom?
The Strategy: Who should get the treat to maximize happiness?

Existing methods were like a manager who either:

Pretended they already had the map (which is rarely true).
Gave up on individual strategy and just treated big, clumsy groups.
Got overwhelmed if the club was too big (more than a dozen people).

The Solution: The "Gibbs" Detective

The authors (Aidan Gleich, Eric Laber, and Alexander Volfovsky) built a new algorithm they call Gibbs-TS. Imagine a detective who does two things at the same time:

They play the game: They give out a few treats, see how the club reacts, and calculate the "happiness score."
They update the map: Based on the reactions, they guess who is friends with whom. If Alice gets a treat and Bob suddenly seems happier, the detective thinks, "Aha! Alice and Bob are probably friends."

They use a mathematical trick called a Gibbs sampler. Think of this as a "what-if" machine. The machine runs thousands of tiny simulations in its head:

Scenario A: What if Alice and Bob are friends? How would the treats have worked?
Scenario B: What if they aren't? How would that look?

By running these scenarios over and over, the machine slowly narrows down the truth. It builds a best-guess map of the friendships while simultaneously figuring out the best strategy for handing out treats.

Why This is a Big Deal

The paper claims this method is a massive upgrade in three ways:

1. It learns the map and wins the game.
Most other methods just try to win the game assuming the map is known, or they try to draw the map without caring about the game. This method does both at the same time. It's like a GPS that learns the road conditions while you are driving, rather than waiting until you get home to draw the map.

2. It works on big networks.
Previous methods could only handle tiny groups (about 12 people). This new method works on networks with hundreds or even thousands of people. The authors tested it on real data from a village in India and a school in the US, and it worked great.

3. It creates a "Bonus Report."
Because the algorithm learns the friendship map, it doesn't just tell you who to give treats to; it gives you a reconstructed map of the network. This is valuable for scientists who want to study how influence spreads (like how a rumor or a disease moves through a group).

The Results: Less Regret, More Happiness

In the world of experiments, "regret" is a fancy word for "missed opportunities." If you gave a treat to the wrong person, you have "regret" because you could have made more happiness by giving it to someone else.

Old methods: When they ignored the fact that people influence each other, they made huge mistakes (linear regret). They kept making the same wrong choices.
This new method: It made mistakes, but it learned quickly. The "regret" grew very slowly (sublinear). In head-to-head tests, this new method made 10 times fewer mistakes than the next best competitor.

The Bottom Line

The paper presents a tool that allows researchers to run experiments in messy, real-world social networks where they don't know the connections between people. It learns the connections on the fly while trying to get the best results.

The authors proved mathematically that this approach is efficient and showed through computer simulations and real-world data that it works much better than previous methods. They also noted that the map it builds can be used later to answer other scientific questions about how people influence each other.

In short: It's a smart, self-learning system that figures out the hidden social web while figuring out the best way to help people, all without needing a pre-drawn map.

Technical Summary: Adaptive Policy Learning Under Unknown Network Interference

Problem Statement

In many experimental settings, the outcome of a unit depends not only on its own treatment but also on the treatments assigned to its neighbors within an underlying network. This phenomenon, known as interference or spillover, violates the Stable Unit Treatment Value Assumption (SUTVA). While causal inference literature has developed robust methods for static experiments under interference (e.g., Sussman and Airoldi, 2017; Aronow and Samii, 2017), these approaches typically assume the interference network is known or rely on coarse cluster-level randomizations.

Existing adaptive (sequential) experimentation methods face significant limitations:

Known Network Assumption: Scalable methods like Gleich et al. (2025) assume the network structure is fully observed, which is unrealistic in many applications where social or behavioral ties are latent.
Scalability Issues: Methods that attempt to learn the network structure, such as Agarwal et al. (2024), rely on Fourier analysis over all possible neighbor configurations, resulting in parameter counts exponential in neighborhood size. These methods fail to scale beyond roughly $n \approx 12$ units.
Loss of Granularity: Other adaptive designs (e.g., Viviano and Rudder, 2024) operate on predefined clusters, bypassing individual-level optimization and failing to recover the interference network itself.

The core challenge addressed by this paper is jointly learning the unknown interference network and optimizing individual-level treatment allocations in a sequential setting to maximize cumulative outcomes (e.g., revenue, health metrics).

Methodology

The authors propose a Thompson Sampling (TS) framework that jointly infers the interference network and reward parameters using a Gibbs sampler.

1. Model Setup

Setting: Sequential allocation of binary treatments $Z_t \in \{0, 1\}^n$ to $n$ units over $T$ rounds, subject to a budget constraint $\|Z_t\|_1 \le B$ .
Neighborhood Interference Assumption (NIA): The outcome of unit $i$ depends only on its own treatment and the treatments of its neighbors defined by an unknown adjacency matrix $A$ .
Reward Model: The expected outcome is linear in a parameter vector $\theta$ , i.e., $r(Z; A, \theta) = H(Z; A)\theta$ . The design matrix $H$ depends on the network $A$ .

2. Joint Posterior Sampling via Gibbs

Since the likelihood is non-linear in $A$ (due to neighbor counts), a closed-form posterior is unavailable. The authors employ an edge-wise Gibbs sampler to draw approximate joint samples from the posterior $\pi(\theta, A | \mathcal{D}_{t-1})$ :

Parameter Update ( $\theta | A$ ): With $A$ fixed, the model reduces to a standard conjugate Gaussian regression. The posterior for $\theta$ is Gaussian.
Edge Update ( $A | \theta$ ): With $\theta$ fixed, the sampler sweeps over all edges $(i, j)$ . The full conditional for edge $A_{ij}$ depends only on the reward streams of nodes $i$ and $j$ . The update rule is derived via a logit transformation of the likelihood ratio, allowing efficient sampling without enumerating all $2^{\binom{n}{2}}$ graph configurations.

3. Algorithm (Gibbs-TS)

At each round $t$ :

Perform $K$ Gibbs sweeps to obtain an approximate joint sample $(\theta^{(t)}, A^{(t)})$ .
Select the treatment vector $Z_t$ that maximizes the sampled expected total reward: $Z_t = \arg\max_{Z: \|Z\|_1 \le B} \mathbf{1}^\top H(Z; A^{(t)}) \theta^{(t)}$ .
Observe rewards and update the history $\mathcal{D}_t$ .
Warm-start the next round's Gibbs chain with the final sample from the current round.

4. Explore-Then-Commit (ETC) Variant

For general NIA rewards where modular collapse does not hold, the authors analyze an ETC strategy:

Phase 1: Treat each node in isolation for $m$ rounds to estimate edge probabilities based on observed spillovers.
Phase 2: Run a standard Thompson Sampling algorithm (assuming the network is known) using the estimated graph $\hat{A}$ .

Key Contributions

Joint Learning Framework: The paper formulates the joint problem of network recovery and adaptive treatment allocation under NIA. It introduces a Thompson Sampling algorithm that uses edge-wise Gibbs sweeps to sample from the joint posterior of the network and reward parameters.
Downstream Causal Inference: The estimated network $\hat{A}$ is not merely a byproduct but a scientific deliverable. It supports post-experiment estimation of direct, indirect, and total treatment effects, as well as the design of follow-up experiments.
Theoretical Regret Bounds:
- Additive Spillover Models: For models where total reward is linear in the treatment vector with latent score coefficients (e.g., linear-in-means), the authors prove a Bayesian regret bound of order $O(\sqrt{nT \cdot B \log(en/B)})$ for exact posterior sampling. This bound depends on the latent score dimension $n$ , not the ambient dimension of $\theta$ .
- General NIA: For general rewards, the ETC variant achieves a regret bound with a graph-discovery cost of $O(n^2 \log T)$ .
- Lower Bound: An information-theoretic lower bound of $\Omega(n \log T)$ is established, demonstrating that any consistent algorithm must pay a cost linear in $n$ for network discovery.
Scalability: The method scales to networks with hundreds of nodes (up to $n=1000$ under linear-in-means), significantly outperforming existing methods that are limited to $n \approx 12$ .

Empirical Results

Regret Performance: On two real-world networks (a borrowing-money household network with $n=63$ and a school friendship network with $n=121$ ), the Gibbs-TS algorithm achieves sublinear regret. While there is a gap compared to an oracle that knows the true network, the regret is significantly lower than baselines that ignore interference (which suffer linear regret).
Comparison with State-of-the-Art: In head-to-head comparisons on small networks ( $n=8$ ) where Agarwal et al. (2024) is feasible, Gibbs-TS achieves more than an order-of-magnitude reduction in regret (e.g., median regret of 141 vs. 1571 for Agarwal et al. under specific conditions).
Network Recovery: The algorithm successfully recovers the interference network with high accuracy (F1 scores > 0.98 in synthetic settings and 0.74 in real-world settings).
Downstream Estimation: Using the recovered network $\hat{A}$ , the paper demonstrates that estimates of direct, indirect, and total treatment effects closely track those obtained using the true network, with small Root Mean Squared Errors (RMSE).

Significance and Claims

The paper claims to provide the first adaptive experimental design that jointly learns the interference network and optimizes individual-level treatment allocations in a sequential setting without requiring predefined cluster structures.

Scientific Value: The recovered network serves as a direct scientific output, enabling causal analyses (direct/indirect effects) that were previously inaccessible in adaptive settings.
Practical Impact: The method bridges the gap between theoretical causal inference under interference and practical, large-scale adaptive experimentation. It enables platforms and agencies to optimize interventions (e.g., vaccine rollout, marketing) in real-time while simultaneously mapping the underlying social or behavioral dynamics.
Theoretical Insight: The work establishes that under additive spillover models, the complexity of the problem reduces to the dimension of the latent score vector, allowing for regret bounds that are independent of the graph topology's complexity.

The authors acknowledge limitations, including the reliance on correct reward function specification, the computational bottleneck of integer linear programming for treatment selection in general NIA settings, and the gap between the $O(n^2)$ upper bound and $\Omega(n)$ lower bound for graph discovery costs. However, they assert that their approach represents a significant step forward in scalable, adaptive experimentation under unknown network interference.