Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Learning to target with network interference

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Causal and structured bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies online targeting (bandits) under network interference with a sparse linear spillover model, proving regret lower bounds and near-optimal algorithms under three levels of known network structure (full support, column support sizes, none).

Problem

Adaptive treatment assignment under network interference where each individual's reward depends linearly on actions of a few others; the goal is to minimize cumulative regret while learning the sparse interference structure, which is high-dimensional in population size d.

Approach

Exploits row-sparsity of the interference matrix by learning per-individual reward rows rather than aggregating rewards into a single linear bandit; uses successive elimination on column sums of the effect matrix (with full or column-size knowledge) and an explore-then-commit LASSO method when no support is known, with matching instance-dependent lower bounds.

Key results

• Aggregated-reward baseline lower bound is Omega(d^{3/2} sqrt(T) ∧ dT) in the worst case, while full-support NSE-FS achieves Õ(sqrt(T) Σ sqrt(rho_j)), matching the Omega(sqrt(T) Σ sqrt(rho_j)) lower bound up to logs.
• NSE with column support sizes achieves Õ(sqrt(T) Σ rho_j), and NETC with no support information achieves Õ(d (sT)^{2/3}), linear in d.
• In simulations (d=100, T=20000) the baseline incurs the largest regret and structure-aware NSE/NSE-FS achieve the lowest cumulative regret; NETC's per-individual regret stays roughly flat in d.

Surprising findings

• Ignoring network structure and reducing to a standard linear bandit yields super-linear dependence on d (d^{3/2}sqrt(T)) in the worst case, showing the reduction is inherently inefficient.

Limitations

• Assumes linear additive interference model with row-sparse effects and no carryover effects across time periods.
• Gap between upper and lower bounds in the unknown-network regime; (sT)^{2/3} rate may not be optimal.
• NETC requires knowing the sparsity level s to set exploration length.

Experimental setup

Datasets: Indian village social network dataset (74 villages, Karnataka)

Benchmarks: simulated networks (d=100, T=20000) Indian village networks (74 villages)

Metrics: cumulative regret per-individual cumulative regret

Baselines: UCB on aggregated reward (network-agnostic linear bandit)

Builds on: linear bandit successive elimination high-dimensional sparse linear bandit explore-then-commit linear treatment effect model under interference

Closest papers by meaning

• Mutli-Armed Bandits with Network Interference (NeurIPS 2024 · similarity 0.92)
• Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits (ICML 2025 · similarity 0.90)
• Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference (NeurIPS 2025 · similarity 0.89)
• Linear Contextual Bandits With Interference (ICML 2025 · similarity 0.89)
• Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.88)
• Doubly Robust Causal Effect Estimation under Networked Interference via Targeted Learning (ICML 2024 · similarity 0.87)