Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference

AI summary

Overview

• Research area: Multi-armed bandits with network interference (MABNI), bridging adversarial online learning and causal inference/design-based statistics.
• Technical level: Advanced. The paper is heavily theoretical, relying on bandit lower-bound arguments, information theory (Le Cam's two-point method, KL-divergence bounds), and asymptotic confidence sequences.
• Scope in one sentence: The paper establishes a Pareto frontier between cumulative regret and average-treatment-effect (ATE) estimation error in adversarial MABNI and proposes an algorithm, EXP3-N-CS, that targets regret minimization, continual inference, and ATE estimation simultaneously.

What This Paper Is About

In many experiments, treating one individual changes the outcomes of others, so a bandit learner must choose "super arms" (one arm per unit) across a network of interacting units. The authors study the conflict between two goals that existing work usually treats separately: pulling the best super arms as often as possible to keep regret low, versus sampling sub-optimal super arms often enough to estimate causal effects accurately. They derive the first theoretical Pareto frontier for this trade-off and design an algorithm that explicitly balances it while remaining valid for inference at any stopping time.

Key Contributions

1. A unified adversarial framework, adversarial MAB-N. The authors extend the stochastic MAB-N formulation of Zhang and Wang (2024) to the adversarial (design-based) setting, using exposure mapping and clustering to compress the exponentially large super-arm space of size K^N, and describe an exposure super arm space of cardinality at most |d_s|^C.
2. The first Pareto frontier for regret versus causal estimation in adversarial MABNI. Theorem 4.1 gives a lower bound of the form inf over estimators, max over instances, of sqrt(R_ν(T,π)) · e_ν(T,Δ̂) = Ω_{K,T}(sqrt(|U_E|)), quantifying the fundamental tension between learning efficiency and statistical power.
3. An anytime-valid asymptotic confidence sequence (CS) and the EXP3-N-CS algorithm. Proposition 5.2 defines the CS built on an inverse-propensity-weighting (IPW) estimator, Definition 5.4 introduces MAD (a modular exploration device), Theorem 5.5 proves the CS is asymptotically valid with width Õ(|U_E|^{1/2} t^{(α-1)/2}), and Algorithm 1 (EXP3-N-CS) combines these with an EXP3-style update.
4. Simulation studies. The paper states that simulation studies were conducted to examine the empirical performance of EXP3-N-CS (Section 6). The specific numerical results are not included in the provided excerpt, so no simulation figures or benchmark values are reported here.

Main Findings

• Trade-off lower bound (Theorem 4.1): For any policy π and any exposure mapping and clustering satisfying Condition 3.1, inf_Δ̂ max_{ν ∈ E_0} (sqrt(R_ν(T,π)) · e_ν(T,Δ̂)) = Ω_{K,T}(sqrt(|U_E|)). The bound preserves a sharp dependence on the size of the effective exposure super-arm space |U_E|.
• Interpretation of the frontier: The authors state that if the ATE estimation error achieves T^{-1/2}, the regret must be Ω(T). Conversely, if ATE estimation is dropped and the learner only identifies the best arm, regret converges. This is presented as a guideline for practitioners deciding how much inference accuracy to trade for regret performance.
• Proof technique: Two adversarial bandit instances are constructed that differ only in the expected reward of one exposure super arm S, creating a fixed difference in the ATE between S and another arm S' while remaining statistically hard to distinguish. Le Cam's two-point method and a KL-divergence bound show that accurate ATE estimation requires a minimum number of pulls of S, which directly conflicts with low regret.
• Impossibility of naive approaches: Extending the classical result cited from Zhang and Wang (2024) (their Proposition 1), the paper notes that in certain difficult situations any valid policy incurs regret linear in the time horizon, R(T,π) = Ω(T), motivating exposure mapping and clustering.
• Asymptotic CS for MAB-N (Proposition 5.2): The CS {τ̄̂_t(S_i,S_j) ± Ĉ_t(S_i,S_j)} is built on an IPW estimator that averages (𝟙{S_{t'}=S_i} R_{t'}(S_{t'}) / π_{t'}(S_i)) − (𝟙{S_{t'}=S_j} R_{t'}(S_{t'}) / π_{t'}(S_j)) over rounds. The width Ĉ_t(S_i,S_j) depends on a variance proxy V̂_t(S_i,S_j) = Σ_{t'=1}^{t} (1/π^MAD_{t'}(S_i) + 1/π^MAD_{t'}(S_j)) and a free positive parameter η.
• Assumption on variance growth (Assumption 5.3): The cumulative conditional variance V_t(S_i,S_j) must grow at least linearly in t, i.e., V_t(S_i,S_j) = Ω(t). The authors describe this as weaker than the Θ(1) expected-reward-gap assumption of Simchi-Levi and Wang (2024), but stronger than the requirement V_t → ∞ used by Waudby-Smith et al. (2021) and Ham et al. (2023); they argue linear growth is realistic because instances where all 𝒴_t(S) = 0 after some time are rare and may indicate experiment problems.
• MAD exploration module (Definition 5.4): The sampling probability becomes π^MAD_t(S) = (1/|U_E|) δ_t + (1 − δ_t) π^ALG_t(S) with δ_t ∈ [0,1] a time-varying parameter. At δ_t = 0 the policy is the base algorithm (pure regret focus); at δ_t = 1 it samples uniformly over U_E (pure exploration).
• CS validity and rate (Theorem 5.5): With δ_t = 1/t^α and α ∈ [0, 1/2), the CS of Proposition 5.2 is a valid asymptotic (1 − δ̃) confidence sequence with width Ĉ_t(S_i,S_j) = Õ(|U_E|^{1/2} t^{(α−1)/2}).
• Positioning relative to prior work (Table 1): The paper's own framework is marked as satisfying all of regret minimization, continual inference, ATE estimation error minimization, a trade-off result, network interference, and the adversarial setting. Zhang and Wang (2024) is marked as covering all except the adversarial setting; Liang and Bojinov (2023) as covering the three objectives and the adversarial setting but neither a trade-off result nor network interference; Simchi-Levi and Wang (2024) as covering regret, ATE error, and trade-off but not continual inference, network interference, or the adversarial setting; Jia et al. (2024) and Agarwal et al. (2024); Xu et al. (2024) as focusing on regret under network interference without inference or trade-off results.

Methodology in Plain English

• Reduce the action space first. Instead of one arm chosen per node across K^N combinations, the authors use two standard causal-inference tools. Exposure mapping collapses a unit's neighbor treatment configuration into a small set of exposure categories of size d_s. Clustering forces units in the same cluster to share the same exposure arm, capping the effective super-arm space at |d_s|^C. Condition 3.1 requires 2 ≤ |U_E| ≤ T so the problem stays non-trivial but tractable.
• Set up three objectives. Objective 1 is cumulative regret relative to the best fixed exposure super arm; Objective 2 is a confidence sequence that stays valid at every time t (anytime validity); Objective 3 is the maximum ATE estimation error over all pairs of exposure super arms, e_ν(T,Δ̂) = max_{S_i,S_j ∈ U_E} E[|Δ̂_T − τ̄_T|].
• Prove a lower bound by constructing hard instances. The authors build two nearly identical bandit worlds differing only in one arm's expected reward. Retelling the sketch: distinguishing them requires enough samples of that arm, so any estimator with small error forces many pulls of a possibly sub-optimal arm, which in turn forces large regret. Information-theoretic tools convert this into the Ω_{K,T}(sqrt(|U_E|)) bound.
• Build inference from the data the bandit already collects. The IPW estimator reweights observed rewards by the probability the algorithm assigned to each exposure super arm, correcting for the fact that the algorithm samples some arms far more often than others.
• Force the algorithm to keep exploring. Because pure regret minimizers sample low-reward arms rarely, the authors add MAD, which mixes the base algorithm's probability with a uniform probability over U_E using the decaying parameter δ_t = 1/t^α, α ∈ [0, 1/2).
• Combine into EXP3-N-CS. Algorithm 1 takes the arm set, unit set, exposure super arm set, and a sequence {L_m} as input. In each round it computes ε_m = sqrt(log(|U_E|) / (|U_E| 2^{m−1})) for the block containing t, uses a uniform probability at the block's first round, otherwise uses an exponential-weights update based on estimated rewards R̂_{L_m,t−1}(S), and then applies MAD.
• Test empirically. The authors report simulation studies of EXP3-N-CS (Section 6). Specific experimental setups, baselines, and numerical outcomes are not reported in the provided excerpt.

Why This Matters

• Research impact: The paper connects two literatures that rarely meet — adversarial bandit regret analysis under network interference, and design-based/anytime-valid causal inference — and claims the first Pareto frontier characterizing their trade-off. It also supplies a confidence-sequence tool (Proposition 5.2) that the authors describe as a plug-in module usable inside other adversarial algorithms such as EXP3.
• Methodological shift: Instead of treating inference as a post-hoc add-on to a bandit run, the framework treats estimation accuracy as a design constraint that shapes the sampling policy, via the MAD mixing parameter δ_t.
• Real-world applications (as discussed in the paper):
  • Clinical evaluation of drug treatments, where researchers want both high treatment efficacy during the trial and reliable estimates of how treatments differ.
  • Economics and social science field experiments where one person's treatment spills over to others (the paper cites applications in economics and the social sciences generally).
  • Pandemic response, where hospitals may prioritize accurately measuring the efficacy of treatments rather than purely maximizing outcomes over a fixed period.
  • Adaptive experiments that must decide when to stop based on data-driven thresholds, which is where anytime-valid inference is needed.
• Industry relevance: Any platform running networked experiments — marketplace interventions, social or referral features, public-health deployments — faces the same tension between optimizing outcomes now and reporting trustworthy effect estimates later. The paper gives a formal language and an explicit dial (α, δ_t) for choosing a point on that trade-off, and warns that demanding T^{-1/2}-accurate estimates may be paid for with Ω(T) regret.

Future Directions

• Tighten the trade-off. The paper establishes a lower bound; the provided content does not report a matching upper bound showing EXP3-N-CS attains the Ω_{K,T}(sqrt(|U_E|)) frontier, which is a natural next question.
• Relax the variance-growth assumption. Assumption 5.3 requires V_t = Ω(t), which is stronger than the V_t → ∞ condition used in related adversarial-bandit confidence-sequence work; whether the same asymptotic guarantees hold under the weaker condition is left open here.
• Extend the design choices. The framework already subsumes classic MAB, the settings of Jia et al. (2024) and Agarwal et al. (2024), and an offline-style threshold exposure mapping from Leung (2022a); the paper notes MAB-N enables novel frameworks not previously studied online, leaving room to explore other exposure mappings and clustering rules, including cases where the adjacency matrix H is unknown.
• Connect to covariate diversity and contextual variants. Related work (Duan et al. 2024) argues Pareto optimality can be improved with a covariate diversity assumption absent interference, and Xu et al. (2024) extended MABNI to linear contextual bandits; combining those directions with the adversarial MAB-N framework is an open path.
• Empirical grounding. The reported simulation studies are the paper's only empirical evidence in the provided content; broader benchmarking in realistic networked deployments (health, economics, social platforms) remains to be done.

Target Audience

• Bandit and online-learning theorists interested in regret guarantees under interference and in lower-bound/Pareto arguments.
• Causal inference and design-based statisticians working on exposure mappings, clustering, IPW estimators, and anytime-valid confidence sequences.
• Methodologists in biostatistics, economics, and the social sciences who run sequential or adaptive networked experiments and need valid inference at unplanned stopping times.
• Practitioners and applied researchers in clinical trials, public health, and platform experimentation who must decide how much regret to accept in exchange for more accurate treatment-effect estimates.

Authors’ abstract

In multi-armed bandits with network interference (MABNI), the action taken by one node can influence the rewards of others, creating complex interdependence. While existing research on MABNI largely concentrates on minimizing regret, it often overlooks the crucial concern that an excessive emphasis on the optimal arm can undermine the inference accuracy for sub-optimal arms. Although initial efforts have been made to address this trade-off in single-unit scenarios, these challenges have become more pronounced in the context of MABNI. In this paper, we establish, for the first time, a theoretical Pareto frontier characterizing the trade-off between regret minimization and inference accuracy in adversarial (design-based) MABNI. We further introduce an anytime-valid asymptotic confidence sequence along with a corresponding algorithm, $\texttt{EXP3-N-CS}$, specifically designed to balance the trade-off between regret minimization and inference accuracy in this setting.