📊 statistics

Scalable Policy Maximization Under Network Interference

This paper introduces a scalable Thompson sampling algorithm for multi-armed bandits under network interference that overcomes the sample size limitations of existing methods by leveraging linear reward structures to achieve sublinear Bayesian regret on dynamic networks.

Original authors: Aidan Gleich, Eric Laber, Alexander Volfovsky

Published 2026-05-07

📖 4 min read☕ Coffee break read

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 massive online marketplace, or perhaps a public health official trying to distribute vaccines. Your goal is simple: figure out who to give a "treatment" (like a coupon or a vaccine) to, so that you get the best possible result (more sales or fewer sick people).

The tricky part is that you don't know the answer upfront. You have to learn by doing. This is a classic "Multi-Armed Bandit" problem—like a gambler trying to figure out which slot machine pays out the most by pulling different levers.

The Problem: The "Ripple Effect"
In most standard computer algorithms, they assume that what happens to Person A has nothing to do with Person B. But in the real world, people are connected. If you give a coupon to your best friend, you might be more likely to buy something too. If you vaccinate your neighbor, you are less likely to get sick.

This is called interference. The treatment of one person "ripples" out to affect their friends.

The paper points out a major flaw in existing computer methods: they are terrible at handling these ripples when the network is big. Current methods work fine if you have a tiny group of 15 people, but if you try to scale that up to 1,000 or 10,000 people, the math explodes. It's like trying to solve a puzzle where every piece changes the shape of every other piece; the computer gets overwhelmed and crashes.

The Solution: Finding the Pattern
The authors, researchers from Duke University, found a clever shortcut. They realized that while interference is complicated, it often follows simple, predictable rules. They borrowed ideas from a field called "causal inference" (which studies cause-and-effect) and applied them to these learning algorithms.

They made three main assumptions to simplify the math:

Local Influence: You only care about your own treatment and the treatment of your immediate friends (neighbors). You don't need to know what the whole world is doing.
Additivity: Your own treatment and your friends' treatments add up separately; they don't create weird, unpredictable magic when combined.
Symmetry: It doesn't matter which specific friend gets treated, only how many of your friends get treated. If three of your friends get a coupon, it's the same as if three other friends got one.

By assuming these rules, the authors turned a massive, impossible math problem into a neat, linear equation. Instead of needing millions of variables to describe a network of 1,000 people, they could describe it with just a handful of parameters.

The Algorithm: The "Smart Guessing" Machine
They built a new algorithm called Thompson Sampling. Think of this as a super-smart detective who is constantly making guesses.

At every step, the detective draws a random "hypothesis" about how the world works (e.g., "Maybe giving coupons to 2 friends doubles the sales").
Based on that guess, they decide who to treat next to get the best result.
They watch what actually happens, update their guess, and repeat.

Because they simplified the math using the rules above, this detective can now handle networks with thousands of people, whereas the old detectives could only handle tiny groups.

The Results: Fast and Accurate
The paper tested this new detective against the old methods using computer simulations.

Speed: The new method learned quickly and handled huge networks (up to 1,000+ people) without breaking a sweat.
Performance: It made better decisions (earned more "rewards") than the existing methods, even when the rules weren't perfectly followed.
Robustness: Even when the network data was a bit messy (like missing a few connections), the algorithm still worked well.

In a Nutshell
This paper bridges a gap between two worlds: the theory of how people influence each other (causal inference) and the practice of making real-time decisions (bandit algorithms). By realizing that social influence often follows simple, symmetrical patterns, they created a tool that can efficiently figure out the best strategy for treating people in massive, connected networks. It's the difference between trying to count every single grain of sand on a beach versus realizing that sand piles up in predictable dunes, allowing you to measure the whole beach with a single ruler.

Technical Summary: Scalable Policy Maximization Under Network Interference

Problem Statement
The paper addresses the challenge of sequential decision-making (policy maximization) in environments characterized by network interference, where the treatment status of one individual influences the outcomes of others. While Multi-Armed Bandit (MAB) algorithms are standard for sequential learning, they typically rely on independence assumptions that fail in networked settings (e.g., clinical trials, online marketplaces, social networks).

Existing approaches to MABs under interference face two critical limitations:

Scalability: Current methods struggle to scale beyond very small networks (approximately $n \approx 15$ nodes). They often attempt to capture arbitrary interference patterns, leading to a parameter space that grows exponentially with the node degree ( $d_{max}$ ) and linearly with the network size ( $n$ ). For a network with $n=1000$ and $d_{max}=10$ , this results in over a million unknown parameters, rendering estimation computationally infeasible.
Static Assumptions: Many existing algorithms require the network structure and the population of individuals to remain fixed over time, an assumption that creates inconsistencies in dynamic settings where outcomes depend on historical treatment statuses.

Methodology
The authors propose a scalable Thompson Sampling algorithm that leverages structural assumptions common in the causal inference literature to achieve a parsimonious linear parameterization of the reward function.

Structural Assumptions (SANIA): The method relies on the Symmetric and Additive Neighborhood Interference Assumption (SANIA).
- Neighborhood Interference (NIA): A node's reward depends only on its own treatment and the treatment status of its immediate neighbors.
- Additivity: Direct effects do not interact with indirect (spillover) effects.
- Symmetry: A node's reward depends on the number of treated neighbors, not their specific identities.
  Under these assumptions, the vector of node-level rewards can be reparameterized as a linear system: $r_t = H(Z_t; A_t)\theta + \epsilon_t$ , where $\theta$ is a low-dimensional parameter vector containing treatment and interference effect parameters.
Algorithm Design:
- The algorithm maintains a posterior distribution over the parameter vector $\theta$ .
- At each time step $t$ , it samples a parameter vector $\theta^{(t)}$ from the posterior and selects a treatment allocation vector $Z_t$ that maximizes the total expected reward conditional on $\theta^{(t)}$ .
- The framework supports flexible parameterizations, including shared parameters (all nodes share $\theta$ ), grouped parameters (nodes in latent or observed groups share $\theta_g$ ), and latent feature models (where node positions in a Euclidean space influence rewards).
- The algorithm accommodates dynamic networks (where adjacency matrices $A_t$ change) and budget constraints (limiting the number of treated nodes).
Regret Analysis:
- The authors prove an upper bound on Bayesian regret of $O(D\sqrt{nT} \log(nT))$ , where $D$ is the dimension of $\theta$ , $n$ is the network size, and $T$ is the time horizon.
- They derive a matching lower bound of $\Omega(D\sqrt{nT})$ , demonstrating that the algorithm is near-optimal.
- The regret bounds reflect the trade-off between the increased information gained from observing $n$ interdependent nodes and the increased complexity of the action space.

Key Contributions

Scalable Parameterization: The paper demonstrates that common causal inference assumptions allow the reward function to be expressed as a linear function of a low-dimensional parameter vector, reducing the complexity from exponential to polynomial (specifically, linear in $n$ for shared/grouped models).
Scalable Thompson Sampling: The authors develop an algorithm capable of handling networks orders of magnitude larger than previous methods (demonstrated up to $n=1000$ in simulations), resolving the "curse of dimensionality" inherent in interference problems.
Dynamic Network Handling: Unlike prior works requiring fixed networks, this framework allows for both nodes and edges to be sampled or change at each time period, resolving inconsistencies between temporal independence and fixed population assumptions.
Theoretical Guarantees: The paper provides rigorous upper and lower bounds on Bayesian regret, establishing the near-optimality of the proposed approach.

Results
Simulation experiments validate the method across three parameterization schemes:

Shared Parameters: The algorithm learns quickly and scales effectively for networks of size $n \in \{100, 500, 1000, 2500\}$ .
Grouped Parameters: The method performs well even when group labels are partially latent and must be estimated using an "anchor" node per group.
Latent Features: The algorithm successfully handles heterogeneous effects dependent on latent node characteristics in latent space models.

Comparisons:

vs. Agarwal et al. (2024): The proposed method significantly outperforms the existing state-of-the-art (which uses Fourier analysis and sparse network interference) on small static networks. Crucially, the proposed method remains robust and outperforms Agarwal et al. even when the SANIA assumptions are misspecified (e.g., when additivity or symmetry is violated). This is attributed to the proposed method's ability to learn an effective approximation with far fewer parameters, whereas competing methods suffer from high variance due to the need to estimate exponentially larger parameter vectors.
vs. Standard MAB: Standard MAB approaches fail to scale due to the exponential growth of the action space ( $2^n$ arms).

Significance
The paper claims to close a key scalability gap between causal inference methods for interference and practical bandit algorithms. By enabling policy optimization in large-scale networked systems, the work bridges the divide between theoretical causal identification and dynamic decision-making. The authors suggest that this framework facilitates the application of bandit algorithms to real-world problems involving large, dynamic networks, such as vaccine distribution or online marketplace interventions, where interference is prevalent but previously too complex to model dynamically.

Technical Summary: Scalable Policy Maximization Under Network Interference

More like this