Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference
Authors: Zichen Wang
Haoyang Hong
Chuanhao Li
Haoxuan Li
Zhiheng Zhang
Huazheng Wang
Venue: NeurIPS 2025 poster ()
Keywords: Causal inference
Adversarial bandits
Network interference
Primary area: probabilistic_methods
TL;DR: Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference

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.

Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference
Zichen Wang!"
Haoyang Hong?*
Chuanhao Li
Haoxuan Li*
Zhiheng Zhang
Huazheng Wang*
Deppartment of ECE and CSL, UIUC
Schooo of EECS, Oregon State University
Department of Industrial Engineering, Tsinghua University
*Center for Data Science, Peking University
SSchool of Statistics and Data Science, Shanghai University of Finance and Economics, Shanghai 200433, P.R. China Institute of Data Science and Statistics, Shanghai University of Finance and Economics, Shanghai 200433, P.R. China
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-un unit scenarios, these challenges have become more pronounced in the context MABNI. this paper, we establish, for the first time, a theoretical Pareto frontier characterizing the trade-off between regret minimization and inference accuracy adversarial (design-based) MABNI. We further introduce anytime-valid asymptotic confidence sequence along with corresponding algorithm, EXP3-N-CS, specifically designed to balance the trade-off between regret minimization and inference accuracy in this setting.
Introduction
Network interference [Leung 2022a b. 2023 Imbens 2024), a well-known concept in causal in- ference, describes phenomenon where the treatment assigned one individual can influence the outcomes of others. It has been extensively studied across various disciplines, with significant appli- cations economies [Arpino and Mattei (016)] Munro et al. [02T]] and the social sciences [Bandiera ett al. 2009 Bond et 2012 Paluck et al. [2016] Imbens) 2024 Due to its broad real-world rele- vance, this concept in causal inference has recently been explored and recognized by researchers in online learning. Consequently, it has begun to be frequently applied in multi-armed bandits Agarwal
ct al. 2024 Jia et al. 2024 Zhang and Wang 2024].
To effectively identify causal effects under network interference, common approach involves con- ducting randomized experiments estimate causal effects from experimental data [Leung 2022a b 2023 Gao and Ding 2023]. Specifically, researchers design estimators that leverage feedback col- lected from each individual (commonly referred as potential outcomes in the causal inference
Equal contribution.
Corresponding author. Email: zhangahshenndmail.c www.eeeennmmaaa..........eeeeeee edu. en.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

literature). They primarily focus on ensuring unbiasedness and controlling the variance of these esti- mators. However. in practice, such experiments are often conducted over multiple rounds, introducing a dynamic aspect to individual feedback. In this setting, the aforementioned potential outcomes are also referred to as rewards the online learning literature, as they contribute to cumulative regret, which quantifies the overall welfare loss incurred throughout the experiment (Simchi-Leei and Wang, 2024). Once the experiment concludes, data collected in earlier rounds can be utilized to improve social welfare in future applications [Mok et al. 2021]. For instance, when evaluating the effectiveness of different drug treatments, researchers may not only seek to maximize treatment efficacy during the trial but also estimate the relative differences in treatment effects across drugs based on experimental data. This process necessitates a careful balance between optimizing the estimation accuracy of causal effects and minimizing the cumulative regrer incurred during the experiment (Simchi-l_evi and Wang, 2024 Zhang and Wang 2024]. Furthermone, researchers may wish continuously infer causal effects throughout the experiment, allowing them to make informed decisions about when to stop based on data-driven metrics or predefined thresholds [Ham et al., [003] Woong Ham al. [0033 [Ling and Bojinov 2023]. This type of continual inference often requires anytime-validity, ensuring that statistical inferences remain robust regardless of the time at which they are made (Lindon and Malek 2022 Waudby-Smith et al. 2024
Building on the above observations, three critical learning objectives emerge: (i) conducting continual inference on causal effects, (ii) minimizing cumula- tive regret, and (iii) designing estimators that leverage collected data to accurately estimate causal effects once the experiment concludes. However, most ex- isting studies fail to address these three objectives simultaneously. For instance, Jia al. 20224.. |Agar- wal et al. [2024) focus exclusively on regret min- imization MABNI, whereas [Ham al. 22033
Statoiical Info
Objective:
Continual Inference
Esimation Emrr Minimization
Regret Minimization
Asymptotic [1barrn 2.5)
IPW Estimator (Theoeer dn
EXP3 (heern (00
Technique:
Woong Ham et al. [2023] primarily explore continual inference in adversarial MAB using the technique
EXP3-N-CS
Asymptotic Confidence Sequences (CS) (Waudby- Smith et al. 202T]. Similarly. (Simchi-Levi and Wang 20024_ZZhag and Wang [2024). Duan et al. [2024] investigate the trade-off between regret minimization and causal effect estimation but place little empha- sis on continual inference. The most closely related work is Liang and Bojinov| [2023), which considers all three learning objectives within the framework of adversarial MAB. However, their approach suffers from two key limitations: (i) it does not account for network interference, and (ii) it lacks rigorous theoretical results characterizing the trade-off between causal effect estimation and regret minimization. Building the above observations, we aim to achieve three key learning objectives in adversarial MABNI and make the following contributions:
Figure 1: The main contribution of our paper is to study how to achieve these three objec- tives and to analyze their underlying interre- lationships.
We propose unified learning framework tailored for the adversarial setting, which we term adversarial MAB-N. Furthermore, we establish the first Pareto frontier that delineates the fundamental trade-off between regret and causality-estimatte error in adversarial MAB-N.
We develop an anytime-valid asymptotic CS to enable continuous inference in adver- sarial MAB-N. Building this, introduce Exp3-Network- Conookk-Cofiennnc Sequence (EXP3-N-CS), which integrates our asymptotic CS and is specifically designed to achieve all three learning objectives (ii-
We conduct simulation studies to investigate the empirical performance of our EXP3-N-CS.
The paper is organized as follows. Section 2 reeiews related work. In Section 3 we introduce the core setting of adversarial MABNI, along with the techniques of exposure mapping and clustering, which support the design of MAB-N. Section presents our results on Pareto optimality. In Section 5 we introduce the Asymptotic CS technique and our main algorithm, EXP3-N-CS. Finally, Section reports the experimental results.
2

---

Table 1: The overview of the exploration of these three objectives: Obj. represents regret minimiza-
tion, Obj. 2 represents continual inference, and Obj. 3 corresponds to minimizing the ATE estimation error.
Paper
Obj- 1
Obj. 2
Obj. 3
Trade-off
Network
Adversarial
Simchi-Lew and Wang 2024
x
Woong Ham et al. 2023
Ham
X
X
x
al. 2023
Liang and Bojinov
20023
S
J
V
X
X
Jia al. 2024
X
X
X
Agarwal et al.
2024
Xu et al.
X
X
X
V
X
[2024]
Zhang and Wang 2024
/
X
V
V
V
X
Ours
V
V
V
V
2
Related Work
Causality inference under network interference. In the current causality literature, interference is a well-established concept that signifies a violation of the Stable Unit Treatment Value Assumption (SUTVA) [Imbens] 2024). It arises in scenarios where an individual's ' treatment potentially influ- ences the outcomes of others, phenomenon frequently observed in practice. Existing research on offline causal inference under network interference has primarily employed two key methodological
approaches: clustering-basse and exposure mapping techniques [Leung] 2002a bj 2023 Zhao
methods (Zhang and Imai 2023
Viviano et al., 2023 Zhao 2024
2024 Recently. a growing interest has been in studying the MABNI. For instance, Agarwal al. [2024] applied Fourier analysis to
transform the MABNI problem into a sparse linear stochastic bandit formulation. However, to mitigate the exponential growth of the action space, they imposed a strong sparsity assumption on network structures, restricting the number of neighbors each node can have. In contrast, Jia et al. 2024] explored an MABNI setting without such sparsity assumption. Their learning framework enforces a switchback design, in which all nodes must adopt the same arm simultaneously. However, this approach does not account for scenarios in which the optimal arm may vary between nodes or subgroups. To address these limitations, Zhang and Wang (2024) proposed general learning frame- work, MAB-N, which simplifies the stochastic MABNI problem while allowing flexible adjustment of the action space through exposure mapping and clustering techniques. MAB-N generalizes the settings considered in Dia et al. (2024) and et al. [2024,, treating them as special cases (see discussion in Section 3.2 Furthermore, Xu al. [2024) extended MABNI to the linear contextual bandit setting, incorporating a structured linear relationship between potential outcomes and interference intensity.
Trade-off' between inference and regret. A substantial body of research has focused on developing statistical methods for inference in stochastic MAB, often deriving statistical tests or central limit theorems while keeping the bandit algorithm largely unchanged [Luedtke and Van Der Laan 2016
Dimakopoulou et al. 2017 2019 Zhang et al.) 2020aa Dimakopoulou et al.J [2021] Hadad et al. 2021 [021/Zhang et al.) 2021 Han et al.) [
al., 2023 Simehi-Levi and Wang 2024
These methods enable aggressive regret minimization but are subject to several key limitation:: (i) they rely on the SUTVA, (ii) they assume that bandit rewards are i.i.d. samples from specific distribution families, and (iii) they do not support anytime-valid continual inference. Regarding the
last limitation, to knowledge, the only works that attempt continual inference in the adversarial
bandit setting are Ham et al. [2023). Woong Ham et al. 2023) Liang and Bojinoy (2023) However, these studies also assume SUTVA and lack a rigorous theoretical analysis of the inference-regret trade-off. To explore this inference-regret trade-off, researchers have first shifted their attention simpler problem: balancing estimation accuracy and regret minimization. To our knowledge, the first rigorous trade-off results were provided by (Simchi-Levi and Wang (2024) in the stochastic MAB setting, though their approach remains constrained by the SUTVA assumption, Duan al.) (024) further argues that Pareto optimalit--simulaann simultaneously achieving optimal regret and estimation accuracy- can improved by introducing covariate diversity assumption, provided that there is no network interference. More recently. /Zhang and Wang (2024) extended the trade-off results from Simchi-Leevi and Wang 2024 to the stochastic MAB-N framework, accommodating network interference.
3

---

Additional discussions of the related work are provided in the Appendix. The relationship between our work and the most closely related studies summarized in Table
3 Preliminaries
In this section, we first introduce the basic adversarial MABNI framework. Then, we present the techniques of exposure mapping and clustering and outline the adversarial MAB-N framework.
3.1 Basic framework: adversarial MABNI
We extend the classic single-unit adversarial bandit framework [Auer et al. 2002a to incorporate network interference [Zhang and Wang] 2024]. Consider network with N units. represented by ( the l = [I,...,N. N and the adjacency matrix H == [ha.ik..jen E {0, 1] NxN (where hi,j = 1 indicates unit i and j are neighbors, while hi, O indicates otherwise). It is worth noting that full not strictly required; its necessity depends on the specific design introduced in the following section (see the discussion in Section 3.2). We assume that each unit has K K-armed set (action set) denoted as K = {0, 1..........4 K - IJ. At each round t, the learner must assign an arm to each unit, resulting in super arm (a collection of arms across all units) represented as A, = (a1,,, 02,t, .N.)) ) E K.4 Suppose the super arm A, is pulled in round i, the reward derived by unit E U/ is (A,) E [0, 1], where (-)) : 1C" + IR represents the reward function of unit i in round t. The terminal time T is pre- pre-specified and cannot be known the learner in advance. We define the set of all legitimate design- design-based bandit instances as Eg. where a legitimate instance v== (Y), AEK" JE(r) satisfies (A) E [0, 1] for all A KM, L (T) and E U.
knowledge of
We aim to design policy æ (II, TT). The Te is a rule that determines the super arm pulled round based on the history 14-1:= {A1, 1 (A1) jeu. At-1, (A) Specifically, Te (A) = P(A,- = A 11.11). The performance of the policy is commonly measured by the cumulative regret [Auer et al. 2002a
Lattimore and Szepesvári 2020). defined as
R(T, == max AER
ΣE
T Σ
(2, REUL
E
Σ
T
Yia(AA)) Σ
N
EEW
The above-mentioned problem is far more challenging than the simple MAB problem (which only involves arms), as it involves K N possible super-arms, increasing the action space exponentially. As shown by Zhang and Wang [024] (see their Proposition 1), in certain difficult situations, any valid policy ı will incur regret that grows linearly with the time horizon T, i.e., R(T, x) = Q(T)). To manage this complexity, techniques: exposure mapping and clustering [Leung 2022a| Zhang and Wang 2024) to reduce the effective dimensionality of the action space. These techniques enable the formulation of unified framework, MAB-N, which captures a broad spectrum of learning settings.
adopt the method of Zhang and Wang [024 employing two key
3.2 MAB-N
Exposure mapping is a common tool in causal inference for network interference that reduces the complexity of treatment assignments in networked settings. The core idea of exposure mapping is to compress these high-dimensional features of neighbors and network structure into a smaller set of exposure categories. Instead of labeling each individual as merely "treated" or "untreated," we assign them an exposure level that reflects the degree type of influence they experience, such as "having two treated neighbors" or "having least one treated neighbor." The definition of the exposure mapping follows [Leung] 2022a Zhang and Wang 2024
Exposure mapping [Leung 2022a
S(i, A, HI), where S U KM (0,1) +U,
(1)
where denotes the exposure arm, the exposure mapping, and its output space, referred to the exposure-arm set, with cardinality [24,] d.. Intuitively, the exposure mapping reduces the original super arm space of size KN an exposure arm space of size d,, We define S (S(i, A, HI) Jew (s1,..., sN) as the exposure super arm. This allows us to decompose the policy Tx(-) and define the expected exposure mapping-bawt based reward:
Te (A) = P(A, A (S) He-1), Yr.(S.)) = Σ (r, = A S.).
(2)
AEKU

---

Here St denotes the exposure super arm selected by the algorithm in round t based on the history He He-1- and the policy nz (A) is represented by two-stage sampling procedure: it first draws S, ~ PP H4-1) and then samples A, ~ (P( St). The second line of the above equation is a generalized notation of Leung [202aa]. Notably, TP = A 5) represents a fixed sampling rule that can be manually defined by the learner before the learning starts. Typically, the probability of selecting A, A given S is zero if does not match the set (S(i. A, HI) Jeu.. Conversely, if S is equal to this set, then the probability of choosing A is strictly positive, i.e., I(A, A S) > O. In this context, the expected reward of S (i.e., (S)) depends solely on the definition of the exposure mapping S and the network topology H..
Clustering. We define the clustering set as C := [Cy where C = C represents the total number of clusters. The clusters are assumed be disjoint, meaning that for any i * j. C, nc, = Ø, and collectively exhaustive, such that Ugeto: Cg [N]. For any [N], we denote C- (i) as the cluster containing& Such an operation is common and necessary, otherwise, the total arm space is exponentially large.
Framework of MAB-N. We define the legitimate exposure super arm set Ug == Uc no. where Uo := {[S(i, A, H) hreu : A E K3)) ensuring that S E Uo is compatible with the original arm set K", and Uc == Se : j E U, if (i) = C-), then St,; = $ denoting all kinds of cluster- wise switchback exposure super arms. For instance, if E {0, 1). .N- = 4, C, = {1,2), C2 = (3, 4), then Ue [(k,, ki, k2, ka) ki, k2 {0, 1}). Hence, the cardinality of the exposure super arm space satisfies [W/]] S [d,] C. The word "legitimate" means in each round, the policy can only select an exposure super arm S, in Ug and sample the A according (PA,,
S)). The exposure
mapping (which controls d.) and clustering (which controls C?) allow us to manage the action space; they only need satisfy the following condition:
Condition 3.1. The exposure mapping S and C should ensure that 2 < Mgl S T.
In addition, we define Di(S) = A Eieu (S) as the expected average reward of the exposure super arm S E Ug in round l. The reward in round t (S,) follows (s.)))) = t/2 Eieu (A,),,,, where A₁ ~ PAA,+ = A St).
MAB-N is unified framework. It is important to note that MAB-N is not parallel to the learning settings in Tia et al. [0044) Agarwal et al. 2024]; rather, it provides more general framework that encompasses these settings. In the following, we provide several illustrative examples: Example (i). Classic MAB [Auer et al.) 2002b (Simehi-Lev and Wang, 2024] corresponds to the case where
N = 1, that is, a single unit without network effects, and the exposure mapping is defined as S(1, A, HHI) := A, where E K. Example (ii). (ii)./Agarva |Agarall et al. [0024] adopt an exposure mapping of the form Sii IH] == Ae; and set C = N., meaning each unit is assigned to its own cluster. Example (iii). Jia et al. (024) also define ((i Hi) ;= Ae, but use C' = 1, assigning all units to single cluster. This models the global proportion of treatment at each round t. Example (iv). The exposure mapping and clustering framework can also be traced back to the offline causal inference literature. Suppose E, hij > 0 for all j U. The exposure mapping can be defined as Eye h
S(i A, HI = Seu his
E [0, 1)) which is adapted from the offline setting [Leung 2022a
Gao and Ding 2023
As shown in the above examples, MAB-N is a unified framework that captures a wide range of learning settings. Studying it effectively subsumes many existing scenarios. For example, to model a switchback design as in Ji et al. [2024], one can adopt the exposure mapping and clustering described in Example (iii. Moreover, MAB-N N also enables the exploration of novel frameworks that have not been considered in prior online settings, such as the one presented in Example (iv).
Is H necessarily known? We emphasize that whether the adjacency matrix HH must be known a priori depends entirely on how the exposure mapping S(-) is defined. For example, our setting reduces to the scenario in Leung [202a]] 2022elynmmey... when the exposure mapping depends on all first-order neighbours
the neighbourhood information H must indeed be known in advance. In contrast, if our exposure mapping simply uses each node's 's cluster index, then IH can remain unknown. Overall, we include Hi in our setup in order to focus on a unified framework, and this does not imply that all information in H always needs to be learned.
5

---

Finally, we introduce the definition of the ATE [Leung. 2022a Liang and Bojinov 2023) Definition 3.2 (ATE). The ATE between exposure super arm S, E Uig in round l is (S),
Er==1 (e, S2) = E (Dr()))) - (s,))
3.3 Learning objectives
Objective Regret minimization. of regret in Section 3.1
Based on the setting of the MAB-N, we can refine the definition
Σ Rn(S)) 1==1
(T)
max SEll
D((S) -E EETT
1=1
Objective 2: Continual inference. For all S,, Sj E Ugg our objective is to design (1 8) CS {I((S,, S,)le where each [S,, Sz) an interval and 8 is the probability parameter such that ( 2 1, (S,, Sy) E ((S),,))) 2 1 1
Objective 3: ATE estimation error minimization. We aim design estimators ÂT S for all St, E Us to minimize the maximum ATE estimation error (Simchi-Levi and Wang 2024
Zhang and Wang 2024 defined as (T, (T, Å) = S, B[IÂT(S,, Sj) Fr (r. Sy)[
Recalling Figure T simultaneously addressing Obj. 1-3 is shared concern among online learning and statistical researchers, with the former primarily focusing on Obj. and the latter on Obj. 2-3. However, achieving both Obj. and Obj. 2-3 simultaneously is often challenging; essentially, there a trade-off between the two. When we excessively prioritize the estimator's ' accuracy (e.g., through independent random sampling), we may fail to adequately explore the optimal strategy, resulting in regret that it does not remain sublinear in time T. Conversely, if we focus solely on identifying the optimal strategy, we naturally overlook the measurement of the reward gap, which can lead to uncontrolled variance in the estimator. In the following section, we provide a rigorous description of the relationship between Objective and Objective 3.
Pareto optimality results
In this paragraph, aim to construct the theoretical optimal trade-off between the ATE estimation accuracy and the regret.
Theorem 4.1. Given any online decision-making policy æ, and any S and C that satisfy Condition 3.1 the trade-off between regret and ATE estimation exhibits
inf max DEED (VR.(T, (T. = QK (VMMe))
where Ry and e, denote, respectively, the regret and the maximum ATE estimation error under instance v.
The sketch of proof. To prove the lower bound, we construct two adversarial bandit instances that differ only in the expected reward associated with exposure super arm S, while all other distributions remain identical. This creates a small but fixed difference the average treatment effect (ATE) between S and another arm S", yet renders the instances statistically hard to distinguish. The crux of the argument is that unless the learner samples S sufficiently often, it cannot accumulate enough information to detect this perturbation. Consequently, any estimator of the ATE between S and S" will exhibit large eттоr due to insufficient exploration. Formally, the argument applies tools from information theory, specifically Le Cam's 's two-point method and KL-divergence bound, to show that accurate estimation of the ATE requires distinguishing between the two constructed environments, which turn necessitates minimum number of pulls of arm S. This induces direct tension between the estimation error e(T, Å) and the cumulative regret R(T, T): minimizing one forces the other to grow. By optimizing this trade-off, we derive the lower bound as above, which highlights fundamental information-theores limit in adversarial bandits under network interference. The novelty lies in extending classical bandit lower- bound techniques the setting of

---

networked exposure mappings and adversarial reward generation, preserving the sharp dependeney on the effective arm space size [Mg]
Theorem 4.1 establishes the fundamental trade-off between the estimation, namely, the statistical power, and the cumulative regret, namely, the learning efficiency. For instance, when the estimation achieves T/2 estimation, we claim that, unfortunately, the regret will exhibit (((T). In contrast, when we omit the estimation of ATE and solely figure out the best arm, the regret will converge. This guideline essentially encourages practitioners carefully and reasonably design estimators and evaluate their convergence performance concerning T. When practitioners are more inclined to estimate the reward gap between different arms rather than pursuing the optimal policy such as in scenarios where hospitals, during a specific period of a pandemic, aim to assess the efficacy of treatments more accurately efforts should be directed toward actively designing estimators with higher convergence efficiency. Practitioners should also be prepared to accept the trade-off of potential losses in regret convergence resulting from this approach.
5 Asymptotic Confidence Sequence and Main Algorithm
In this section, we first introduce a technique called asymptotic CS, which facilitates continual inference of the ATE as defined in Definition 3.2 Next, we propose our algorithm EXP3-N-CS that integrates asymptotic CS to achieve three objectives.
5.1
Asymptotic CS and MAD
CS is a series of confidence intervals that remain uniformly valid over time (Darling and Robbins Waudby-Smith et al., 2021]. Unlike traditional confidence intervals, which are limited to inference a pre-specified terminal time T, CS enables continual inference throughout the process. This allows for adaptive decisions regarding experiment termination or continuation, as the learning algorithm does not need know or define the time horizon T' in advance. Instead, the algorithm can continuously utilize the CS for inference, concluding the experiment once satisfactory learning outcomes are achieved. We introduce the concept of asymptotic CS, first developed by Waudby-Smith et al. (20TT]
1967
Definition 5.1 (Asymptotic (1 - 5) CS). Suppose there exists an (unknown) non-asymptotic (1 - 8) CS {Āt = C7 1 for a sequence of target parameter {1p ] and a CS {Ae = C2 such that é 0.&
1, then {it + č2 ) is asymptotic (1 - 8) CS for {
Our Asymptotic CS for MAB-N is defined in the following proposition. Proposition 5.2 (Asymptotic CS for MAB-N). We define the asymptotic CS for Si E Ue as
(S, S3) + (S,, 8 The IPW estimator Sy) is defined as 1 Σt Ei= (S; (S;,S) Sz) ((,,=S,) which serves to estimate (S, Sÿ). The CS width my((;)
1 S.) (8))
C,(S,, S,) = 8,, log (h(5 where (z, = E/- (Smd)()) Aaj
(5,)
and 17 is an arbitrary positive parameter.
Asymptotic CS can appear a plug-in module that operates independently of any specific algorithm. Its performance is based on the following assumption
Assumption 5.3. We require that the cumulative conditional variances (,,, = Ei= ((fr Fe) grow at least linearly with / for all S., S, E Ug. that VS S,) = 2(1), where F, denotes the sigma algebra that contains (S))
and He.
The above assumption is weaker than the one made by Simchi-Levi and Wang 2024], which assumes that the expected reward gap of each pair of arms is ((1) (stochastic setting). We should mention that our assumption is relatively stronger than the assumption in Waudby- -mith et al. [202]] Ham et al. 2023), which only requires the cumulative conditional variance V.(S,, S,) - when / - xc, but does not assume a linear growth rate. However, this assumption should hold the most realistic experimental settings, provided that instances where there exists time t' such that 38, ()()) 0
7

---

Algorithm EXP3-N-CS
Input: arm A, unit set U exposure super arm set Mg sequence {Cm 100
2: for t= 1,,, .....
3: Compute m such that t E Lm, set Cm
Me 1mm
4: if = Am then
5: For all S E Ug set (S) = [agl
6: else
expl cm Re Rem. 11))
7:
For all S E Ug set o. (S) = Eug exp Em R 1-))))
8:
end if
9:
For all S Ugg set at (S)
1 6,
8.)
[eee
10: Sample S, based on mi TMAD,, implement Sampling's (S:) and observe the rewards Rg (S,)
11: For all S,, S3 E Ugg construct the confidence sequence it (S,, S;) + S5)
12: For all S E Mig set (S) Er-t.. 11 R..))))
13: end for
14: Return ( = (s, for all S, Sy E Us
for all > t' are rare in practice and may indicate practical problems with the experiment [Liang and Bojinov 2023]. The asymptotic CS presented in Proposition 5.2 can be incorporated into various classic adversarial bandit algorithms,, such as EXP3. However, algorithms like EXP3 primarily focus on minimizing regret, which often leads sampling the exposure super arm with low rewards at low probability. This behavior exposure super arms and significantly weaken the inference power of the asymptotic CS. Therefore, it is essential to ensure that the algorithm explores each exposure super arm with sufficiently high probability. To this end, we incorporate the MAD [Liang and Bojinov 2023]. a modular component that can be integrated into various algorithms to promote effective exploration.
reduce the accuracy of our IPW estimator in estimating low-reward
Definition 5.4 (MAD). Let the probability of Algorithm ALG pulling arm S in round [ be denoted by m/ ALG (S) = IP (S, = H4-1), where FALG denotes the probability taken with respect to ALG. After applying MAD, the probability of pulling the exposure super arm S in round is given by MAD (5) = (A = S H(-1)= = Ti 6t + (1 )T ALG (S). where &, E [0, 1] is a
time-varying parameter and MAD denotes the probability taken concerning MAD. It is easy to verify that z3 (S) E [0, 1] for all S E Ug and Eseus " MMAA(() (S) 1.
MAD can balance the trade-off between regret minimization and additional exploration. Consider two special cases: 8, and 8, = When ó, = 0, the policy becomes M.AD = ALG entirely focusing minimizing regret (as suppose ALG intends to minimize the regret). On the other hand, when & = 1, the policy becomes -MAD( (S) = [égel for all S E Ugg (uniformly samples S, from Ug), entirely prioritizing exploration. The following Theorem shows that with a specific setup, the CS proposed in Proposition 5.2 is a valid asymptotic (1 - ÔS
Theorem 5.5 (Performance of the Asymptotic CS). Suppose S and C satisfy Condition 3./ and As-
sumption 5.3 holds. For all Ss, Sj E Ug, consider the sequence of random variables (fx S
where the probability of observing St S at time is given by n MMAD (S) Weel 6, + (1 8.) mL
We set 6,- = 1 which satisfies a E [0, })) The CS in Proposition 5.2 forms a valid asymptotic CS for
(S,, R,)) with confidence level 5 and the CS width (S, S,) (((+)
5.2
Main algorithm
In the previous section, demonstrated that both the asymptotic CS and the MAD can be integrated into learning algorithms such as EXP3. In this section, we analyze the performance of the resulting algorithm, which we refer to EXP3-N-CS.
EXP3-N-CS designed to achieve three learning objectives. We ensure that the algorithm does not
rely on prior knowledge of T by employing the doubling trick [Besson and Kaufmann 2018a]. We
define the time interval L. = {tms.... ..., t. + 2 1}. where t and t.m. 1 Σm== 2m
8

---

Algorithm 2 Sampling
1: Input: St
2: Derive the set of real super arm { (Zr hrett) such that for all Zr, (S(i, T,, = St
3: Sample At from set {Zy hew based on P(A = Zr St), pull As, and observe reward
(e(S = N Eieu (1,(
for all m > 1. The algorithm begins by computing the policy st (S) (ALG equals to EXP3)
for all S E Ug using the standard EXP3 technique (line 4-8). Next, it adjusts the policy to derive
(ADD(S) (S) for all S Ug based on the MAD (line 9). The algorithm then samples S. based on
"MAD
Tt and subsequently samples Ar conditioned on St (line 10 and Algorithm 2). Algorithm 2 will
first derive real super arm candidate set {Zy }re(( such that (S Zv. H. HeEu = S, 4l' E [
Then, it will sample A, from (7r) )r based on P(A, A St) (note that for all A [ ]ve[])- P(A, A Se) 0). Using the asymptotic CS proposed in Proposition 5.2 the algorithm constructs the CS to estimate the ATE in each round (line 11). Note that the xT(S) in the asymptotic CS should be replaced with (S). Finally, after the algorithm terminates the iteration, the algorithm outputs (S S,) fr,S,,S)) the estimated ATE (line 14).
Theorem 5.6. Following the setting in Theorem 5.5
(i) (Estimation error upper bound) For all S Sj E Ug define å S,) == ir Sy). Then, we have (S,Ar(S;, Sj) (r. S,)1= ((el)tt())
(ïi) (Regret upper bound) The regret of the EXP3-N-CS can be upper bounded by R(T, MAD) + T.
Me OVTMelT
(iii) (Pareto-optimality) For all legitimate instances v E Eo, select a such that v M S 7 and a E [0, }), then EXP3-N-CS guarantees e, (T, ( n MAD) = (VViee))
we conclude that EXP3-N-CS achieves the Pareto-optimal trade-off estab- lished in Theorem 4.1 There is no need choose a larger than 1. as doing so does not reduce the regret but instead deteriorates the estimation accuracy. Furthermore, although our analysis centers on EXP3-N-CS, the underlying design principles naturally extend to broader class of bandit algorithms, owing to the strong modularity and composability of the Asymptotic CS and MAD components. In particular, for any base algorithm that achieves regret bound of the form (TV under the MAB-N framework, the performance guarantee in Theorem 5.6 can be easily extended. This is because the MAD adopts the form o7 TTAAD(S (S) क + (1 6, mz ALG (S), where the first term (with coefficient 6,) is introduced to improve ATE estimation, and the second term n (S) is the base algorithm aimed at regret minimization. To analyze the regret, we decompose the total regret into two components corresponding to the two terms in the strategy, and then separately upper bound each. As shown in Theorem 5.6 (ii), the first part of the regret scales as D(VIue (T), which comes from the (1 (1-6,) m ALG (S) term, and the second part scales as Ö(T2-a), arising from the T 6, term, which is independent of the specific base algorithm. Therefore, we can easily analyze the overall regret upper bound as Ö / [Me [T + a1) The Asymptotic CS and MAD components serve as general-purpose purpose mechanisms that facilitate balancing Objectives 1-3 across broad range of algorithms.
From Theorem
We now present guidance on selecting by combining theoretical insights with practical considera- tions. Specifically, setting a = 0 results in linear regret, but ensures a fast convergence rate for the CS width and the ATE, specifically (144 :1- In addition, setting a such that / TT = 710 we can minimize the regret to the level of Ō OVVIE (T) while achieving statistical inference with 0144 ( To demonstrate its practical selection, consider the following example. When treating group of critically ill patients, the primary goal is to minimize regret by assigning treatments that are currently believed to be most effective, thereby improving their immediate survival chances within the network. Conversely, for patients with milder symptoms and stable conditions, it can be advantageous to explore less-certain yet promising treatments, as doing so improves the evaluation of the relative effectiveness of different options. This enhanced inference leads to more precise ATE estimation and, in turn, supports better-informed treatment decisions for future populations. Accordingly, one may

---

265
ESPL pee (1
Fas
Standard
100 Loke
4300 6633
800
uoce
01
02
03
(a) Cumulative regret
(b) CS width
(c) Maximum ATE estimation error
Figure 2: Experimental results.
prefer selecting a closer to in the latter, emphasizing pure exploration.
2 in the former scenario, prioritizing regret minimization, and closer to 0
Experiments
In this section, demonstrate the empirical performance of EXP3-N-CS by some simulation studies. The code is available at: https:///itthtt com htmm//eerrylaaiic/iiigrr basesiign-aaae-Bandddd
Setup. We consider network consisting of 101 units. Specifically, there one center cluster C1 = {1} that contains a single unit, which is connected to every unit in the five outer clusters.
Each of the outer clusters contains 20 units. We set the action set IC {0. 1]. Additionally,
we define the exposure mapping inspired by [Leung] 2022a Gao and Ding, 2023 expressed as
E [0. 2) exploring the influence of the proportion of action taken among all the neighbors of each unit. The exposure mapping implies d, 2. For all S Ug. we define P(A, = A 5) as uniform sampling, and (S) = N Eieu (A) for all A such that (S(i, A, [II) = S. Besides, we let (S) be sampled from Bernoulli distribution. The mean of this Bernoulli distribution is uniformly resampled from [0, 1] every 1000 rounds. We set the trade-off parameter of EXP3-N-CS to a E {0.1, 0.2, 0.3, 0.4, 3.49 and compare its performance against two baselines: Standard (where 6, 0) and Uniform (where 6, 1). Each algorithm is executed 1000 times, and we report the averaged results. Results. The simulation results are shown in Fig. ((a) 2(b and ( From Fig. 2(a) the Uniform bascline consistently exhibits the highest cumulative regret throughout the entire horizon. In contrast, both the Standard baseline and EXP3-N-OG with larger a values (e-g.,
((1, H) = { Eg buy xay
his has
0.4 a 0.49) achieve the lowest cumulative regret. This is because Uniform does not focus on minimizing regret. Fig. iullustttee the trajectories of the CS width arg maxs, EM Eld Ör(S,, S,) (Čr(S,,S) takes the average value of
Cr,S,, Sy), where S, 1000 times). The Uniform baseline achieves the narrowest CS, indicating the most accurate inference. In contrast, the Standard bascline maintains the widest CS width throughout the horizon, implying the least accurate inference. The EXP3-N-CS variants lie between these two extremes, with smaller values producing wider CS widths that approach that of Uniform. Fig. presents the box plot of the maximum ATE estimation error (i.e., (T, Å)), where the orange line represents the median. As shown in Fig. [(c] both EXP3-N-CS variants with smaller a values and the Uniform baseline achieve relatively low maximum ATE estimation
with compact interquartile ranges and fewer extreme outliers. In contrast, the Standard baseline exhibits a noticeably wider spread of errors and substantial number of outliers. This inferior inference performance of Standard (Obj. 2-3) is attributed to its lower frequency of exploring sub-optimal arms compared to Uniform and the EXP3-N-CS variants. Due to page limitations, we present four extensive experimental instances in Section F of the Appendix.
Acknowledgements
Haoyang Hong and Huazheng Wang are supported by National Science Foundation under grant IIS-2403401. Zhiheng Zhang is supported by "the Fundamental Research Funds for the Central Universitics" (number: 20251 10602) of Shanghai University of Finance and Economics.
10

---

References
Michael Leung. Causal inference under approximate neighborhood interference. Econometrica, 90 (1):267-293, 2022a.
Michael P Leung. Rate-optimal cluster-randomized designs for spatial interference. The Annals of 2022b.
Statistics,
Michael P Leung. Network cluster-robust inference. Econometrica, 91( 2023.
Guido Imbens. Causal inference in the social sciences. Annual Review of Statistics and Iis Application, 11, 2024.
Bruno Arpino and Alessandra Mattei. Assessing the causal effects of financial aids firms in tuscany allowing for interference. The Annals of Applied Statistics, 2016.
Evan Munro, Stefan Wager, and Kuang Xu. Treatment effects in market equilibrium. arXiv preprint MrXiv:210911144 2021.
Oriana Bandiera, Iwan Barankay, and Imran Rasul. Social connections and incentives in the workplace: Evidence from personnel data. Econometrica, 77(4):1047-1094, 2009.
Robert M Bond, Christopher J Fariss, Jason Jones, Adam DI Kramer, Cameron Marlow, Jaime Settle, and James H Fowler. A 61-million-person experiment in social influence and political mobilization. Nature, 489(7415);295-299) 2012.
Elizabeth Levy Paluck, Hana Shepherd, and Peter M Aronow. Changing climates of conflict: A social network experiment in 56 schools. Proceedings of the National Academy of Sciences, 113 (3):666-571, 2016.
Abhineet Agarwal, Anish Agarwal, Lorenzo Masoero, and Justin Whitehouse. Multi-armed bandits with network interference. arXiv preprint arXiv:2405. /8621, 2024.
Su Jia, Peter Frazier, and Nathan Kallus. Multi-armed bandits with interference. arXiv preprint arXiv:2402.01885, 2024.
Zhiheng Zhang and Zichen Wang. Online experimental design with estimation-regret trade-off under network interference. arXiv preprint arXiv:2412.03727, 2024.
Mengsi Gao and Peng Ding. Causal inference in network experiments: pitression-based analysis and desiin-based properties. arXiv preprint arXiv:2309.07476, 2023.
David Simchi-Levi and Chonghuan Wang. Multi-armed bandit experimental design: Online decision- making and adaptive inference. Management Science, 2024. doi: 2087//mncc.0233.04444.
Ka Ho Mok, Yeun-Way Ku, and Tauchid Komara Yuda. Managing the covid-19 pandemic crisis and changing welfare regimes, 2021.
Dae Woong Ham, lavor Bojinov, Michael Lindon, and Martin Tingley. Design-based inference for multi-arm bandits. arXiv preprint arXiv:2302.14136 2023.
Dae Woong Ham, Michael Lindon, Martin Tingley, and Iavor Bojinov. Design-based confidence sequences: A general approach to risk mitigation in online experimentation. Harvard Business School Technology & Operations Mgt. Unit Working Paper, (23-070), 2023.
Biyonka Liang and Lavor Bojinov. An experimental design for anytime-valid causal inference on multi-armed bandits. arXiv preprint arXiv:2311.0579, 2023.
Michael Lindon and Alan Malek. Anytime-valid inference for multinomial count data. Advances in Neural Information Processing Systems, 35:2817-2831, 2022.
Ian Waudhy-Smith, Lili Wu, Aaditya Ramdas, Nikos Karampatziakis. and Paul Mineiro. Anytime- valid off off-policy inference for contextual bandits. ACM/JMS Journal of Data Science, 133:1-442 2024.

---

Ian Waudby-Smite -mith,, David Arbour, Ritwik Sinha, Edward H Kennedy, and Aaditya Ramdas. Time-ume camne-niform central limit theory and asymptotic confidence sequences. arXiv preprint arXiv:2103.06476, 2021.
Congyuan Duan, Wanteng Ma. Jiashuo Jiang, and Dong Xia. Regret minimization and statistical infer- ence in online decision making with high-dimensional covariates, arXiv preprint arXiv:2411.06.22 2024.
Yang Xu, Wenbin Lu, and Rui Song. Linear contextual bandits with interference. arXiv preprint arXiv:2409.15682, 2024.
Yi Zhang and Kosuke Imai. Individualized policy evaluation and learning under clustered network interference. arXiv preprint vrXiv:2311.02446 2023.
Davide Viviano, Lihua Lei, Guido Imbens, Brian Karrer, Okke Schrijvers, and Liang Shi. Causal clus- tering: design of cluster experiments under network interference. arXiv preprint arX1v:2310.14983, 2023.
Jinglong Zhao. A simple formulation for causal clustering. Available SSRN 5008213, 2024.
Alexander R Luedtke and Mark Van Der Laan. Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy. Annuls of statistics, 44(2):713, 2016.
Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Estimation considerations in contextual bandits. arXiv preprint arXiv: 2017.
Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Balanced linear contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3445-3453, 2019.
Kelly Zhang, Lucas Janson, and Susan Murphy, Inference for batched bandits. Advances in Neural Information Processing Systems, 33:9818-9822 2020a.
Maria Dimakopoulou, Zhimei Ren, and Zhengyuan Zhou. Online multi-arme bandits with adaptive inference. Advances in Neural Information Processing Systems, 34: 14:1999-1999 19511,99111111 2021.
Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the national academy of sciences, 118(15): 20014602188, 2021.
Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical inference with m-estimators on adaptively collected data, Advances in Neural Information Processing Systems, 34:7460-7471, 2021.
Qiyu Han, Will Wei Sun, and Yichen Zhang. Online statistical inference for matrix contextual bandit. arXiv preprint arXiv:2212.1133 2022.
Yash Deshpande, Adel Javanmard, and Mohammad Mehrabi. Online debiasing for adaptively collected dimhessinnsi data with applications to time series analysis. Journal of the American Statistical Association, 118(542):1 166-1139, 2023.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-71 2002a.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 37:235-256, 2002b.
Donald A Darling and Herbert Robbins. Confidence sequences for mean, variance, and median. Proceedings of the National Academy of Sciences, 58(1):66-68 -8,, 1967.
Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't do for multi-armed bandits. arXiv preprint 1XXx::1883006777 2018a.
12

---

Zhiheng Zhang and Xinyan Su. Partial identification with proxy of latent confoundings via sum- of-ratios fractional programming. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, pages 4140-4172, 2024.
Zhiheng Zhang. Tight partial identification of causal effects with marginal distribution of unmeasured confounders. In Forty-first International Conference on Machine Learning, 2024.
Zhiheng Zhang, Quanyu Dai, Xu Chen, Zhenhua Dong, and Ruiming Tang. Robust causal inference for recommender system to overcome noisy confounders. In Proceedings of the 46th International ACM SIGIR Conference Research and Development in Information Retrieval, pages 2349-2353, 2023.
Zhiheng Zhang, Wenbo Hu, Tian Tian, and Jun Zhu. Dynamic window-lews level granger causality of multi-chan time series. arXiv preprint arXiv:2006.07788, 2020b.
Xinyan Su. Zhiheng Zhang, and Jiyan Qiu. Unveiling environmental sensitivity of individual gains in influence maximization. arXiv e-prints, pages arXiv-2301, 2023.
Zhiheng Zhang. The maximum intersection number of regular simplicial partitions. arXiv preprint arXiv:2210.11450. 2022.
Zhiheng Zhang, Haoxiang Wang, Haoxuan Li, and Zhouchen Lin. Active treatment effect estimation via limited samples. In Forty-second International Conference Machine Learning. 2025.
Balázs Szörényi, Róbert Busa-Fekete, István Hegedüs, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Gossip-based distributed stochastic bandit algorithms. In International Conference Machine Learning, 2013.
Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in collaborative environment. Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, 2016.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. simple and provably efficient algorithm for asynchronous federated contextual linear bandits. arXiv preprint 2rXiv:2207.03) 106, 2022.
Yuanhao Wang. Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. arXiv preprint arxiv: 1904.06309, 2019.
Zichen Wang, Chuanhao Li, Chenyu Song, Lianghui Wang, Quanquan Gu, and Huazheng Wang.
Pure exploration in asynchronous federated bandits. arXiv preprint arXiv:2310. 11015, 2023a.
Jonathan Louëdec, Max Chevalier, Josiane Mothe, Aurélien Garivier, and Sébastien Gerchinovitz. A multiple-pla, bandit algorithm applied to recommender systems. In The Twenty-Eighth Interna- fional Flairs Conference, 2015.
Paul Lagrée, Claire Vernade, and Olivier Cappe. Multiple-play bandits in the position- basod model. Advances in Neural Information Processing Systems, 29, 2016.
Datong Zhou and Claire Tomlin. Budget-constrained multi-armed bandits with multiple plays. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Lilian Besson and Emilie Kaufmann. Multi-player bandits revisited. In Algoritmiii Learning Theory, pages 56-92. PMLR, 2018b.
Su Jia, Nishant Oli, Ian Anderson, Paul Duff, Andrew A Li, and Ramamoorthi Ravi. Short-lived high-volume bandits. In International Conference on Machine Learning, pages 14902-14929. PMLR, 2023.
Nicolo Desa-Bianchh and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1:55):444-1188 1422, 2012.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference machine learning, pages 151-159, PMLR, 2013.
13

---

Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. Advances Neural Information Processing Systems, 27. 2014.
Richard Combes, Mohammad Sadegh Talebi Mazrach Shahi, Alexandre Proutiere, al. Combinato- rial bandits revisited. Advances in Neural Information Processing Systems, 28, 2015.
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits.
Advances in Neural Information Processing Systems, 28, 2013.
Aadirupa Saha and Aditya Gopalan. Combinatorial bandits with relative feedback. Advances in
Neural Information Processing Systems, 32, 2019.
Zichen Wang, Rishab Balasubramanian, Hui Yuan, Chenyu Song, Mengdi Wang, and Huazheng Wang. Adversarial attacks on online learning to rank with stochastic click models. arXiv preprint arXiv:2305. /92/8, 2023b.
14

---

A Notations
Set of units
N
Number of units
Adjacency matrix
K
Real arm set (action set)
K
Number of real arms Arm assigned unit i
A,
Real super arm pulled in round & Exposure mapping
A,
sit
Exposure arm assigned to unit i Exposure super arm sampled in round
St
(C)..((S)
Reward estimator for exposure super arm S Set of exposure super-arms Number of exposure arm Legitimate exposure super arm set Set of exposure super arm that can be triggered by real super arm Set of cluster-wise switchback exposure super arm Probability of Algorithm ALG pulling exposure super arm S Probability of pulling exposure super arm after using MAD Set of legitimate instances
Us
de
UE
Uo
ue
T (S)
T (S)
Eo
(A)
Expected reward the unit under Expected reward unit under Average expected reward under S
(S)
(((S)
R.(S.)
Average reward under S, in round / Cumulative regret
R(T,T)
T(S,,S,)
Difference between potential outcome of S and Sj ATE between S; and S
((S,
((S,S))
IPW estimator for Te S,, Sj) IPW estimator for FF. width
(,(S.)))
Cumulative conditional variance between S and Sj
(,)
Estimator of the cumulative conditional variance between S; and Sj
(5)
+ S,),
Confidence sequence
(S,),
Estimated ATE between S, and S
(T A)
Maximum estimation error the ATE
15

---

B Comparing MABNI with Causality, Multiple-Play, Multi-Agent and Combinatorial Bandits
Multi-armed bandits with network interference (MABNI) focus on online decision-making under networked dependencies, where each action on one node affects others' rewards through interfer- ence. Our work formalizes this challenge by establishing theoretical trade-off between regret minimization and inference precision, and by constructing design-based anytime-vall confidence sequences that remain valid under adversarial network structures (Zhang and Wang 2024). In contrast, causal inference aims to characterize the identifiability of treatment effects under explicit structural assumptions. When point identification fails, partial identification methods quantify what range of causal effects remain compatible with observed data and plausible assumptions (Zhang and Su 2024| Zhang 2024). This distinction suggests that MABNI primarily concerns learnability under adaptive design, whereas causal inference addresses identifubility under fixed assumptions. Yet the two are deeply connected: sequential designs that minimize regret can also be optimized to tighten identification regions as data accumulate, thereby transforming the exploration process into controlled reduction of causal uncertainty. Moreover, robust and proxy-based identification methods (Zhang et al., 2023) complement design-based randomization by mitigating latent confounding in observational segments that interleave with experimental interventions. In settings with interference and dynamic dependencies, such social temporal networks, causal structures evolve over time; this connects MABNI to dynamic Granger-style causal discovery (Zhang et al., 2020b). Finally, the trade-off' between exploration, inference, and structure generalizes beyond networks broader combinatorial domains, where the geometry of feasible allocations-Suue as simplicial partitions
or influence desrappss-deerrinnes the attainable identification set (Su al. 2023 Zhang 2022
Zhang et al. 2025). Taken together, MABNI operationalizes the causal principle of controlled experimentation under interference, while partial and robust causal inference extend its theoretical foundation toward identifiability, providing unified lens on how to jointly optimize regret, inference validity, and causal learnability within complex, networked environments.
The MABNI problem is related to the multi-agent bandit problem, in which multiple agents simulta- neously pull arms in each round. These agents often collaborate by sharing their local observations to collectively accelerate learning [Szörényi et al. 2013 Wu et al. 2016 He et al.. 2022 Wang et al.) 2019 2023a]. J. A key distinction lies in the modeling assumptions: multi-agent bandit formulations typically assume a priori relationships among agents-Such as cooperation or competition and place significant emphasis on the design of communication protocols to enable coordination or negotiation. Besides, the multi-play bandit problem, where the algorithm selects multiple arms in each round and receives individual reward feedback for each, closely related to the MABNI setting,
This framework has been extensively studied in the literature [oouèdec et al. 2015 Lagrée et al., 2016 Zhou and Tomlin 2018 Besson and Kaufmann, 2018b Tia et al. 2023]. While both settings involve the simultaneous selection of multiple actions, MABNI further emphasizes the interference among actions selected at different units, where the reward of a unit may depend not only on its own action but also on the other actions selected in the same round. Furthermore, our work is also related to the combinatorial bandit problem, where the learner selects a subset of base subject to combinatorial constraints such as budgets or matroids-ann receives feedback and rewards that depend on the selected combination Combes et al. [2015] Kveton et al. 2015 Saha and Gopalan| [019 Waag al. 2023b). Some existing works consider interference effects among units, but such interference is typically either explicitly known to the learner assumed to follow a predefined structural pattern. In contrast, the MABNI makes no assumptions about the nature or structure of interference across units; instead, it needs to implicitly learn the interference effects through observed rewards.
and Lugosi 2012 Chen et al. 2013 2014
C Proof of Theorem 4.1
Proof of Theorem 4.1
Recall that the definition of ATE in round is defined as
(S, 8z) = Σ
Te,S,, =
1 Σ
t'
16

---

and the definition of regret is
T
R(T,T)
max SELlE
Vi(S) - Ex
Σ Re(St)
(4)
Here
(s,(s)== E (A)P(( A|S), Vi(S) - Σ (S).
(5)
AEK
SEM
Given a fixed policy T,, we provide the following hard instances. We define the first instance as VI Eo, in which (A) Bernoulli(f(AA)). We denote the best arm as S" and = arg migninsuee.ss 5"), (WT), where Ng EE 1(S, S} and (S, =
N Eieu YveKU (P(A)(P(A = Al 5) - P(A. A S*)). The difference treatment effect between S and S
T (8,
11 TN
Σ
Σ -V,
t=1 sEl
can be equivalently expressed as (for brevity, T2 to denote F/ (S, in the subsequent discussion)
11 ΣE E (P((A) A A) PPA,, = =11
(6)
TN
(=1 iell AEKU
Based on the fact that 1/ Eieu EnEKU (.,(A) 5) - P(A: A {1)) is 1-sub- Gaussian, and for all E [T]
N Σ E (e,(A) (P(A) A1 P = A (1))))
1 Σ E M(A)(P(A:= A| A15)).
E
N VEU AEKU
BEL AEKU
the Hoeffding inequality implies that, with probability at least
+
1og
2 F1.
(7)
On the other hand, we construct another instance as (3 E (0, 1) is chosen sufficiently small)
(A)= = (Bemoulli({{(A))
AA satisfying P(A, = A (S) = 0,
(8)
[Bemoulli[[(A)) B) AA satisfying P(A: A () > 0.
leads to
=2 + 22,>0, where
1 ΣΣ Σ
A -) - (1ia==AAs)))(PPL - A () -0,
$2,=0
N
(=1 iEll AEN!
1 T
F2.50 TN
ΣΣΣ
(PAA)) A| P(A. = = A A1S))
I[P(A, (A1)))((((A. A [S) 0}.
t=1 SEU AEKU
Follow the similar argument as Eq
we have with probability at least
2 log
22
(9)
where
i/ 72 72 + f2,00, where
= N
1
Σ Σ = = A1)) -
A|S)) =),
NEL AEKU
1
Σ Σ (f((A) (3)))- = A S) - P(A, = (118))1(P(A AAS)) > 0}.
72.00 N
FE AER
17

---

Define event &g = = +
2log(2T)
F1,; 2 $2 (2lug(er) }. Under this event:
2log(2T)
T2 -1 - 2-2
(-3))(P(A+) = A1 - P(A, - A| A1)) 1[P(A,
-Al
) = Al > 00}
T
N
BEll AERU
2lx((27)
- V
Σ
-15)>
T
N
iEU AEK
Plog(21)
- 2 T
B.
On this basis, given any pre-specified estimator and strategy, which is recorded as (ar following Zhang and Wang 2024). Simchi-Levi and Wang [2024], we establish hypothesis test as
((rT) = arg min A
+ i, E (1,2) is a sufficient condition of F implying that v (AT)
Å Tol 1 V
2 2log(2T) 2T
Therefore
inf max Pv Ar MEEo
1 Ful2 (
+
(27)
2 inf max Pu år (E(12]
Å Fel 20 +
2 (27)
2
T
T
2 inf max Pr, (5(á2) #1)
Ay se(12)
inf max (v & i).
(E(1.)
(10)
The above equation directly lead to
1 RHS of 10P 2 2 (1 - TV,,,, 2
1 - V KL un P.,))
(11)
2
Let (.),(() denotes the reward density distribution conditioning on arm S in v. Due to the fact that KL(P,,, Pv,) = Ex, (.)...)).))...s and
Pr.)),..s))))) = / Pel.s(X (X)
dX S 9332N N,
(12)
where q > 0 is a constant. It achieves that
KL(P,,, Pv,) = Ev, [W')
S 93 N [N']
Reloc (T,
s g N
(13)
Ue F
2 log((2))
Rsto (T,
$ q 8 + 2
N
T
U 1
where R-tor(-) denotes the regret defined in the stochastic bandit setting under instance V1. Here the last inequality is due to the definition S. Combining -- it implics
13).
2 log((21
inf max Py Ay MECa
( ST) - (S, S S,,,
max
+
T
(14)
2 log 2T")
log()(T)
2 Retoo (T,
59
( 2
N
Me [|=1|
Moreover, we aim relate the regret in adversarial and stochastic settings. For any feasible stochastic instance v, obtained for example by Bernoulli sampling of (A), we have
(T, TT)
Retor (T, m),
(15)
18

---

where the inequality follows from Jensen's inequality. Combining (14 11
we get under event &g
2 log((21))
inf max Pv År MEED
max S1.S,ELte
- - (F,,, 2 +
T
(16)
2 2log(22)) 2 N Run (T, )
V 29 B (2 +2
[e [
As consequence,
inf max Ey År MEED
max El1e
(S;, S1) v (T,
(T)
1 1
2log((2))
2log(2T)
Ru (T,x)
+
2 3 22
N
V RRn (T,
2 T
T
T
Me [i
(17)
When we choose B such that of
B 2/
log (T/2)
N
Ruy (T,z) 1e 1i
it follows
2
17
1
2
)
Uell
= (2K.TVV/ (
(18)
8
T
NqNN
D Proof of Theorem 5.5
The following lemma is important the proof of Theorem 5.5
Lemma D.1. Following the setting Theorem 5.5 for all S,, Sy E Ug the sequence (S S S satisfies the Lindeberg- type uniform integrabiliry condition (Condition L2 of Proposition 2.5) outlined by Waudby- Souubby-Smith et al. (2021). i.e., there exists 3 E (0,1) such that
E [ft,(S,,, (S., (() (S, (,)) (3))
(1)(
< 00 a.s.,
where Ss, = =i ((,, FFe is the cumulative conditional variance.
Proof of Lemma D.I We first upper bound ()) (5,,, S,)) Based on the definition of our IPW estimator, we have
(fr Sy) 7e (s:,
1(S, = (S.)) n (SD))S)
145, = Ra)))
5))
" (Sp)
8
+ +4
(SA)) A T. MAD (S)))
MAD (S.) A t MA)()
MAD (S)))
16
(AAA (S,) A m MAD (S,)) 2'
where the first inequality is due (S) E [0, 1). Note that, based the setup of Theorem 5.5
have (S)= = (a)aa) for all S E Ur. This implies that (S,, Sj) (S.,, (
Furthermore, based on Assumption 5.3 we have VS,S, S,) 2(t). Therefore, by setting $ (2a, 1), there always exists finite time t' such that for all t 2 t', (f. (S,, 5
19

---

(M)( and
E Sy) (11))
> (M)(
(V)(S),))))
S)) (S... ( - -T((
(Vi(S, S,))"
()))
=1
<00 a.s.
Here finish the proof of Lemma D.I
Based on Lemma D.1
we can prove Theorem 5.5
Proof of Theorem 5.3 Based on Assumption Lemma D.I and Proposition 2.5 Waudby-Smith
al. [2021] (S. S,) + C, s,) constitutes an asymptotic (1 8) CS. where
C,,),, = 2 (St, S,)m² + 1) log 12-12
(,) + +1)
8
Besides, based the definition of the variance, know that V. V4. where Vu E (S, Ei= (2,()))) (S.) (9,) Therefore, (fr(S,, S,) + C, S,) is
also asymptotic - 8) CS, where
2(V. S,)n² + 11 1212
V Vi((s,, SyDp +
S) S S,) V
log
8
Define SS) (M.))(s)) wp)n)(s))
the estimator of (S,, and let 1
Ex= (S,, Sz). Since D) 2 V.. the sequence (fr(S., Cr , forms an asymp- totic (1 5) confidence sequence, where
(,),, = (1,( + +1) t2n2
VV((S,
)
log
We finally show that S,) 01( for all S, E Me. We first upper bound (S, Sy), i.e.
S,) = Σ
1
(AAD
+
(S))
P=1
5 Σ (2)
1=1
Then
(,(S,,S))=O
(1Ke)ktttan 11
[eltt+anp +
= 0(1u 1 =
log
127p
and it will converge to 0 when t + This concludes the proof of Theorem 5.5
20

---

E Proof of Theorem 5.6
Proof of Theorem 5.6 Claim (i). Based on the result in Theorem 5.3 for all S * SJ. with probability
at least 1 - 8, we have
A (b,) AlAi v 200r(S,,
(Vr((S,,S))n + 11
(Vr(St.S))) +
-21
T212 log
= -((El(2a0))
where the first inequality owing to Theorem 5.5 and the last inequality owing to the definition of SS), Finally, set 8 1/T, we have
E (.,) - 1 s 2(1 (I.,)),, + 5T 0((ue)70-
Proof of Theorem 5.6 Claim (ii). Let EMAD|:] and EALG denote the expectations taken with respect to the MAD and ALG (EXP3), respectively. Recall the definition of regret:
T
I
R(T, R(T,~MAR MAD) = max Selle
V4(S) - EMAD
Σ
Re(Ss)
(19)
t=1
we also define
T
T
R(T, n MAD i) = Σ (.() - EMAD Σ (S.)
(20)
As the "regret" assuming fixed super arm S; is optimal for all T rounds, while R(T, π measures the actual regret relative the best super arm each round. If Ö(v [efe (T Ti-a) for all S; Ugg it follows directly that R(T, MAD) Ō /Me ( T1-a).
establish that R(T, MAD i)
Based on the definition the MAD, we can decompose Eq
20 as
T
T (S:))
R(T, n
MAD ;)
(.().)
EMAD
Σ
T Σ V((S))
T
Eseu Vi(S)
Σ
+ (1 - -1,,)AAALL RR (S:)]
(21)
t=1
t=1
T
EsEue Vi(()
RRT,, π ALGG ,1)
Σ
8z
ÆALG Re(()))
1=1
R(T, ALG
1-a
where the third incquality is owing to the definition that R(T, "'TT'AAl. ALG = ΣT V((S)) Ein EALG(RR(S.).. We further decompose R(T, ALG .).. Let M be such that T E LMs and detine R(Cm, ALG .i) as R(Lm, ALG i) Exec.,. D.(S.) EAAD [Ereo.. (S.).. It follows directly that R(T, ALG i) S EM, R(Lm, ALG,
21

---

We now focusing on upper bound R(Cm π TAIG i). Set Remimm-15) = 0 for all S E Ug. Based on the unbiasedness the IPW estimator, we have:
BALG R Lm (122-11(())) Σ Vi(S), 4S E Angaadd
KE
BALG (((5))
Σ (L((())
SElle
Σ
ALG ALG (S)EALG RCm. - Rem.x-1(5)) He-1) (()-)) Vt E fm.
SEul
(22)
According to Eq 22 Eq (0 can be rewritten
R(Lm; x 2)
2) EALG 12m- BALG
Σ Ra(Si)
-EE -
Re(Si) He- ]
-ALG (am -ALLG EALG
IEL
= -EALG 1an BALG
Σ
Σ
ALG (5))EAL
(REm.(S) R H6-1
LEEmm SEMe
T Σ
=EALG R2mm-tmttm--1166
Σ
ALG(() (Rem Remmtt1(S)
1=1
SElfe
EALG (2 -Rem..
where the first and third equalities follow from the tower rule, while the last equality holds due to our definition: Rcm. E.ec... Eseu, T. (SL
- (S)).
For E Lm. we define W, = Eseue exp (cm (cm.(())) Consider the ratio between successive W. Using the definition of: W, and W,- W.
AL) exp (fm (em
(23)
W
We rewrite the ratio as:
We
Σ
nt (S) exp (Rc,,, (....e-(()))
(24)
W
SeMl
We now introduce two incqualities: 1) exp(x) 1 + +1+ Vx $ 11:2)1+2 2 Ye Based on these two inequalities, rewrite Eq (24)
Σ ALG
T (S) (S)exp (mm (Rc... (em..-1(5)))
Selle
Σ nt ALLG(S) Rem.((S) Rcm, + cm 2 Σ T AL) (Rm..e()) (
1 + Cy
Setle
Selle
Sexp
fm
Σ Tt
(S)
RCm.)-(5S) (S) (Rcm.(())
tm
2 Σ m (S) (Cm. (S) f
Selle
Seld
Multiplying these ratios from fm to tm + 2m 1, we obtain:
W
T (LLG (Rcm)(()) - ( )²)
We 1-1 = [usl
S Us
exp em Rm + Em Σ
Σ
Wr-1
tE tEC.
EEC... SElde
22

---

Taking logarithms and rearranging the above equation, it yields:
log (14+=1)
12m-tt -1---------- - R.c. S
+ Cm Σ Σ
Tt (S) ((m) R(m))
tELm SEMee
Recalling the definition R(fm: ALGG xALG, ,)) = EALG fmmm - R. we obtain:
+2m-1
log (14411) EALG Em Σ E
Tt (S) (S) (RC.))()) Rc -- (()) 2
R(Cms AAG .1)
Em
tECm SEUle
We then try to bound BALG
Em Etecm EsEue mf (S) (S), R Remme- 15)) there is
(S), - R. (emdd-((S)) 2
BALG
Cm
Σ
Σ
#t ALLG(S)
LE tE SEllE
T1 (L))(S) (1- 1(S, = =5](1 - -Re(5)) 21
)
BBLL fm
T xPL(((5)
LELm SElls
x 1(S: (1(())
1(5 55 -
}
=EALG Cm
Σ tEL. SEMd
Σ
Tt (LC
(S)
(S)2
1(S, = 1[5,=5](
(1- Re R.(5))² H6-21
=EALG Cm
Σ
(2)((5)) + EALG
Cm Σ Σ T (S)
me (S)
t.C.
rECm Selle
=EALG
Cm
2Rc(St)-1) + Em Σ
Σ
(1 (1- (S))²²
EEC...
SEUf
< 2
Em-
Based on the definition of cm. we conclude that R(Cm, TALG ,i) Ö( ue 1 We can upper
bound R(T, ALGG i) by Em R(Lm, TAGG i) Ô ((EM V 16 22mh- Ō(vis 2M/2) Owing to M I log, (T) + 1, we have R(T, ALG, i) Ö(VIHE)T). We can finally bound
RT,, n MAD i) and RT,, n MAD) by (( + +TI-a).
F Additional Experimental Results
In this section, we present four additional experiment instances along with the corresponding results.
Instance 1: single unit. In this setup, the network consists of single unit (as illustrated in Fig. B(a)., making identical to the case considered Liang and Bojinov (2023). Additionally, the action set is defined to include five actions, i.c., A = algorithms are configured the same manner described in Section
The reward structure and baseline
Instance 2: 6 units. The network in this setup consists of 6 units, organized in loop topology, as illustrated in Fig. [4(a) Furthermore, the network divided into three clusters, with the cluster structure also depicted in Fig. 4(a) The configuration of the action set, reward structure, and baseline algorithms follows the same setup as described in Section
Instance 10 units case In this setup, the network consists of 10 units, with the topology structure depicted in Fig. 5(a) Additionally, we divide the network into three clusters, and the cluster structure is also illustrated Fig. [[a) The configuration of the action set, reward structure, and baseline algorithms remains the same as described in Section 6
23

---

800
Fom 1.00 poent)
Ragrer.
jendiig
600
400
200
2000
4020
5000
8000
10200
lime
(a) Network topology
(h) Cumulative regret
EXP3 c_ (9-0
0.3
(0-0.4)
DXPS (0=0031
0.7
Melhod
PXP3NN_0S(000021 ----
Wode
0.5
EXP3_N_CS (0-0.1) [|+
Standard
0.3
Uniform
2000
1000
8000 Time
8000
10000
0.0
0.2
0.4
0.6
0.8
1.0
Max ATE Difference
(c) CS width
(d) Maximum ATE estimation error
Figure 3: Experimental results of instance 1.
Instance 4: 10 units 2
The network consists of 10 units arranged in star-like topology, as shown in Figure 6(a) At the center of the network lies single unit forming the central cluster, which directly connected every unit in three outer clusters. Each of these outer clusters comprises units, resulting in total of 9 peripheral units connected to the central cluster. The configuration of the action set, reward structure, and baseline algorithms remains the same as described in Section
We ran the algorithms 100 times and reported the average results.
The experimental results are presented in Fig. approach and EXP3-N-CS with larger a values achieve the lowest regret, while the Uniform baseline incurs the highest regret. For continual inference, although Standard exhibits narrower CS widths than some EXP3-N-CS variants, its intervals are invalid due to the lack of theoretical guarantees. This issue is reflected in the maximum ATE estimation error, where Standard exhibits the largest errors with many outliers. In contrast, EXP3-N-CG N-CS with moderate or large a and the Uniform baseline achieve lower estimation errors.
and 6 For cumulative regret, both the Standard
24

---

C
800
Fom 1.00 poent)
Regrar.
600
2000
4020
5000
8000
10200
lime
(a) Network topology
(h) Cumulative regret
EXP3 c_ (0-0.49)
0.3
(0-0.4)
Wode [0.1
DXP3 (0=0.31
0.7
Melhodd
0.5
EXP3_N_CS (o-0.11
Standard
0.3
Uniform
2000
1000
8000 Time
8000
10000
0.0
0.2
0.4
0.6
0.8
1.0
1.2
Max
ATE Difference
(c) CS width
(d) Maximum ATE estimation error
Figure 4: Experimental results of instance 2.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
In Abstract and Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
In Section 6 and the Appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
25

---

Fom 1.00 poent)
Lumulativs Regre,,
500
100
C
200
2000
4020
6000
8000
10200
lime
(a) Network topology
(h) Cumulative regret
EXP3 c_ (a-0.49)
0.9
EXP3 (o-0.4)
Wide [0.1]
DXPS (a=0.31
Melbod
0.6
FXBS P=3_N_0S
EXP3_N_CS (o-0.11
+
0.4
Standard
Uniform
2000
1000
8000 Time
8000
10000
0.0
0.1
0.2
0.3
0.4
0.5
Max ATE Difference
(c) CS width
(d) Maximum ATE estimation error
Figure 5: Experimental results of instance 3.
The paper should point any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approxinations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In the main text and the Appendix.
Guidelines:
26

---

350
E0P 1,00
FOPL p003
250
Oanuattve
200
150
100
50
2000
4020
5000
8000
10200
lime
(a) Network topology
(h) Cumulative regret
Undore
EXP3_N_CS cS (2-0.49)
0.9
(a-0.4)
EXPO (a=0.3)
0.7
Method
Wett
0.6
EXP3 NP
EXP3_N_C5 (o-0.11)
Standard
0.3
Uniform
2000
1000
6000 Time
8000
10000
0.3
6.1
0.2
0.3
0.4
Max ATE Difference
(c) width
(d) Maximum ATE estimation error
Figure 6: Experimental results of instance 4.
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: In Section and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same datasct, provide access to the model. In general. releasing code and data is often
27

---

reproducible, they one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
In Section 6
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (tttps://nips.cc)
lobbitc//uddes//dddeebliiisssss ciciioooooiyyyl for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https httppppwwwwgppppp/ppppppppppeeep httpg//udde//oeeeuummmmm
/
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Section and the Appendix.
Guidelines:
28

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars reported because it would be computationally expensive.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section and the Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: In Section
29

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
30

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes].
Justification: In Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswith com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
31

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
32


Reviews:
[{"review_id": "kICmS2f7Rq", "reviewer": "Reviewer_Nu5B", "summary": "The paper establishes theoretical results unifying statistical estimation and regret minimization in the multi-armed bandits with network interference setting. The paper also tests the trade-off with different network topologies and experimental setups.", "questions": "1. The paper uses two common techniques to reduce the dimension of the potential outcomes, I wonder what is the role of the clustering assumption beyond just restricting the cardinality of $\\mathcal{U}_{\\epsilon}$. For example if I only have this exposure mapping but restrict the cardinality of $\\mathcal{U}_s$. I think all the results go through? \n2. I am a bit confused about the line 357, can you explain why you make that conjecture? Also, can you explain what makes line 339 and (3) so different? \n3. Is it possible to add covariates into this setup, for example your potential outcomes depend on the exposure mapping as well as personal characteristics.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n1. Significance: I think the topic is very interesting to me, unifying different pieces from two topics: statistical estimation and regret minimization. The former is very broadly studied by statistics community and the latter by the online learning community. As shown in table 1, there is no previous work that considers the three objectives in a network interference setup. \n2. Quality: The theoretical results are complete and I also like the experiments.\nWeaknesses: \n1. Clarity: \n* Can you make sure the reference works in the main text as well as the appendix? In particular, figure 1 referred to theorem 5.2, 5.3 and 5.4 which are not in the text. \n* Some of the notations can be more clear. For example, in the definition of objective 3, the left hand side uses $\\nu$ which is a legitimate  instance but the right hand side not.", "was_revised": true, "final_justification": "All my concerns are resolved and I vote for acceptance.", "rebuttal": "We appreciate the recognition of the importance of our learning problem, as well as the kind words regarding the clarity of our writing. We address the points below.\n\n> ***Q1: Can you make sure the reference works in the main text as well as the appendix? In particular, figure 1 referred to theorem 5.2, 5.3 and 5.4 which are not in the text. Some of the notations can be more clear. For example, in the definition of objective 3, the left hand side uses ν which is a legitimate instance but the right hand side does not.***\n\n---\n\n**A1:** Thank you for your helpful comments. We will carefully revise the paper to ensure all references are properly defined and linked in both the main text and appendix. We will also clarify notations and correct all typos and grammar issues in the final version.\n\n> ***Q2: The paper uses two common techniques to reduce the dimension of the potential outcomes, I wonder what is the role of the clustering assumption beyond just restricting the cardinality of $\\mathcal{U}_E$. For example if I only have this exposure mapping but restrict the cardinality of $\\mathcal{U}_s$. I think all the results go through?***\n\n---\n\n**A2:** Thank you for your question. In our setting, the role of clustering is to restrict the cardinality of the super exposure arm set $U_E$, i.e., $|\\mathcal{U}_E| \\le d_s^C$, where $C$ denotes the number of clusters. If there is no clustering, this corresponds to the special case $C = N$, where each unit belongs to its own cluster. In that case, we have $|\\mathcal{U}_E| \\leq d_s^N$, under which all of our theoretical results continue to hold. In fact, the case studied by Agarwal et al., (2024) can be viewed as a setting without clustering, which is a special case of our framework. Please refer to line 192 for a more detailed discussion.\n\n> ***Q3: I am a bit confused about line 357. Can you explain why you make that conjecture? Also, can you explain what makes line 339 and (3) so different?***\n\n---\n\n**A3:** Thank you for your question. The conjecture in Line 357 was meant to propose a potentially provable lower bound that could match the upper bound achieved by our algorithm. In light of your and Reviewer fNDP’s suggestion, we will remove this conjecture for clarity and instead revise the discussion to focus on explaining why the current upper bound (i.e., Line 339) does not match the existing lower bound (i.e., Eq. (3)).\n\nWe believe the gap between the upper and lower bounds can be attributed to inherent structural constraints required by asymptotic confidence sequences (CS). Proposition 2.5 together with Condition L3 of Waudby--Smith et al. (2021) gives a convenient way to construct a valid $(1-\\tilde{\\delta})$ asymptotic CS in our learning setup: Define\n$\\tilde V_t(S_i, S_j)\n= \\sum_{s=1}^t \\sigma_{s}^2(S_i, S_j)\n= \\sum_{s=1}^t \\left(\\frac{\\mathbb{E}[R_s(S_i)^2]}{\\pi^{\\text{MAD}}s(S_i)}+\\frac{ \\mathbb{E}[R_s(S_i)^2]}{\\pi^{\\text{MAD}}s(S_j) }\\right)$.\nIf there exists $\\hat{V}_t(S_i,S_j)$ such that $t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j) \\xrightarrow{a.s.}0$, then $\\hat{\\bar{\\tau}}_t(S_i, S_j) \\pm \\hat C_t(S_i, S_j)$ is a valid ($1-\\tilde{\\delta}$) asymptotic CS, where $\\hat C_t(S_i,S_j)=\\sqrt{\\frac{2(\\hat V_t(S_i,S_j)\\eta^2+1)}{t^2\\eta^2}\n\\log(\\frac{\\sqrt{\\hat V_t(S_i,S_j)\\eta^2+1}}{\\tilde{\\delta}})}$. \n\nTo ensure $t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j) \\xrightarrow{a.s.}0$, we construct $\\hat V_t(S_i,S_j)$ via the unbiased IPW estimator that is fully computable from the data: $\\hat V_t(S_i, S_j) = \\sum_{s=1}^t  \\frac{ \\mathbf{1}( S_{s} = S_i ) \\cdot R_{s}(S_i)^2 }{ ( \\pi^{\\text{MAD}}s(S_i) )^2 }  + \\frac{ \\mathbf{1}( S_{s} = S_j ) \\cdot R_{s}(S_j)^2 }{ ( \\pi^{\\text{MAD}}s(S_j) )^2 }$. Let $M_s(S_i,S_j):=(\\hat \\sigma_s^2- \\sigma_s^2)(S_i,S_j)$. Then $M_s(S_i,S_j)$ is a martingale difference sequence and $t^{-1}\\sum_{s=1}^t M_s(S_i,S_j)= t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j)$. By the SLLN for martingale difference sequence, if $\\sum_{t=1}^\\infty \\mathbb{E}[M_t^2(S_i,S_j)]/t^2<\\infty$, we obtain $t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j)\\xrightarrow{a.s.}0$. This requires $(\\hat \\sigma_t^2 - \\sigma_t^2)^2(S_i,S_j) = o(t)$ (by a $p$-series test).\nIn our design this summability is guaranteed by $1/\\pi_t^{\\mathrm{MAD}}(S)=o(t^{1/4})$ for all $S\\in \\mathcal{U}_E$. Hence, when $\\pi_t^{\\mathrm{MAD}}(S)\\propto t^{-\\alpha}$, we require $\\alpha\\in[0,1/4)$. Under this requirement the CS width behaves as $\\hat C_t=\\tilde{O}(t^{\\alpha-1/2})\\quad \\text{for }\\alpha\\in[0,1/4)$,\nand enforcing $1/\\pi_t^{\\mathrm{MAD}}(S)=o(t^{\\alpha})$ for all $S\\in\\mathcal{U}_E$ induces additional regret $\\tilde{O}(t^{1-\\alpha})$. This ultimately leads to the gap between the lower and upper bounds.\n\n> ***Q4: Is it possible to add covariates into this setup, for example your potential outcomes depend on the exposure mapping as well as personal characteristics.***\n\n---\n\n**A4:** Thank you for the insightful question. We believe that the covariate-assisted exposure modeling framework (offline setting) studied by Leung et al. (2022) can be naturally extended to our online learning setting. In their work, graph neural networks (GNNs) are employed to estimate the ATE under network interference. Meanwhile, several studies in the bandit literature, such as Kassraie et al. (2022), have explored the integration of GNNs with structured decision-making. These advances indicate that applying GNN-based algorithms and estimators to our generalized setting (i.e., our setting with covariates) is both natural and technically feasible. We leave this interesting direction for future investigation.\n\n**Reference:**\n\nLeung M P, Loupos P. Graph neural networks for causal inference under network confounding[J]. arXiv preprint arXiv:2211.07823, 2022.\n\nKassraie P, Krause A, Bogunovic I. Graph neural network bandits[J]. Advances in Neural Information Processing Systems, 2022, 35: 34519-34531.\n\nWaudby-Smith I, Arbour D, Sinha R, et al. Time-uniform central limit theory and asymptotic confidence sequences[J]. The Annals of Statistics, 2024, 52(6): 2613-2640.\n\nAgarwal A, Agarwal A, Masoero L, et al. Multi-Armed Bandits with Network Interference[J]. Advances in Neural Information Processing Systems, 2024, 37: 36414-36437."}, {"review_id": "2lV1KbEfIT", "reviewer": "Reviewer_fNDP", "summary": "The paper studies the multi-armed bandit problem with network interference problem. The goal is to design an algorithm that continually satisfies two-fold objectives: regret minimisation, and accurate ATE estimation. The paper proposes first a lower bound on the product of regret and ATE estimation error. Then under known adjacency matrix assumption, it develops an adversarial bandit algorithm EXP3-N-CS, and proves the regret and ATE estimation upper bounds for it. Numerical experiments are provided to demonstrate efficiency of EXP3-N-CS.", "questions": "1. Check the weaknesses and please address them.\n2. Why in theorem 5.5. $\\alpha$ has to be in the range of $[0,1/4)$? What is the technical bottleneck or is it some step in proof that leads to it? \n3. Can you provide a detailed ablation study on choice of $\\alpha$?\n4. Also, it would be interesting to see how the proposed algorithm performs against Simchi-Levi and Wang [2024] and Liang and Bojinov [2023] in network-less setup and Zhang and Wang [2024] in the networked setup. Specially, I am curious why to choose adversarial or stochastic algorithm in this setting.", "limitations": "Except the known H assumption, limitations are not discussed much. Check pointers regarding $\\alpha$ and tightness claims.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is cleanly and logically written. Works as a good introduction to the setup for the reader.\n2. The idea of deriving a \"Pareto optimality\" lower bound and upper bound in the setting as in [Simchi-Levi and Wang, 23] is interesting.\n3. The experimental evidence across networks validates the applicability of the algorithm.\n\nWeakness:\n1. Please add the algorithm pseudocode in the main paper. It is very hard to understand Sec 5.2. without going to and fro to the Appendix.\n2. It is not clear how to choose $\\alpha$ in practice. \n3. I understand why knowing H is helpful here and not knowing it would increase complexity. But I am not sure that it has to be known. The exposure mapping can be learned on-the-go too.\n4.  The paper does not show why the produce of two objectives is \"the\" way to look into Pareto optimality in this setting. It is not intuitive, in general. An explanation is needed.\n5. Line 362-365 were not necessary. You do not have to be slightly suboptimal or really optimal to write a science paper. Do remove this claim. Rather, Theorem 5.6. says that the gap between lower bound and upper bound grows with $T^{\\alpha/2}$. It is more useful to community if you explain from where this gap is arising. Is it a proof issue or natural to the algorithm? Also, experiments do not point to \"optimality\". There is no lower bound plot in experiments.", "was_revised": true, "final_justification": "The authors addressed all the questions thoroughly and promised to incorporate the changes. After reading other reviews and responses, I feel that together with the recommended addendum, it is an interesting work.", "rebuttal": "Thank you for your positive feedback. We're glad that you found the paper clearly written, the Pareto-optimality formulation interesting, and the experimental results convincing. We have carefully addressed your comments and suggestions in our responses below.\n\n> ***Q1: Please add the algorithm pseudocode in the main paper.***\n\n---\n\n**A1:** Thanks for the suggestion. We will include the pseudocode in Section 5 in the future version of the paper.\n\n> ***Q2: It is not clear how to choose α in practice.*** \n\n---\n\n**A2:** Thank you for the question. A concrete example arises in evaluating treatment strategies for infectious disease. When facing a group of critically ill patients, it is important to prioritize regret minimization by assigning treatments that are currently believed to be most effective, thereby maximizing the overall chance of survival within the network. In contrast, for a group of patients with milder symptoms and stable conditions, assigning less-certain but promising treatments can facilitate a better evaluation of the relative effectiveness of different options. This leads to more accurate ATE estimation and supports improved treatment decisions for future populations. Accordingly, one may prefer choosing $\\alpha$ closer to $1/4$ in the former case and closer to $0$ in the latter. We will include this example in a future version of the paper.\n\n>***Q3: I understand why knowing H is helpful here and not knowing it would increase complexity. But I am not sure that it has to be known.***\n---\n**A3:** We emphasize that whether the adjacency matrix **$H$** must be known a priori depends entirely on how the exposure mapping $S(\\cdot)$ is defined. For example, if our setting reduces to the scenario in Agarwal et al. (2024)—namely, when the exposure mapping depends on **all first-order neighbours**—then the neighbourhood information in $H$ must indeed be known in advance. In contrast, if our exposure mapping simply uses each node’s cluster index, then $H$ can remain unknown. Overall, we include $H$ in our setup in order to focus on a unified framework, and this does not imply that all information in $H$ always needs to be learned. Furthermore, thanks to our framework’s extensibility, the exposure mapping itself **can be learned and optimized**—we could show a combined approach with Shishir Adhikari et al. (2025) in the revised version.\n\n\n>**Q4: Why the product of two objectives is \"the\" way to look into Pareto optimality in this setting**\n\n**A4:** It is because the optimal solution (find the best partial order) of the mini-max problem $min_{\\pi, \\Delta} max_{\\nu ∈ \\mathcal E_0} \\\\{\\sqrt{R_\\nu(T, \\pi)}, e_\\nu(T, \\Delta) \\\\}$ induce the form of production. We have added this formulation to the revised version.\n\n\n\n\n\n\n\n> ***Q5:  Please remove the claim in Lines 362–365 and clarify the reason of the gap between the lower and upper bounds — is it due to a proof issue or inherent to the algorithm? Additionally, justify why Theorem 5.5 restricts $\\alpha \\in [0, 1/4)$. Finally, the experiments do not demonstrate \"optimality\"; a lower bound curve is missing.***\n\n---\n\n**A5:** Thank you for the insightful suggestion. We will remove the claim given in Lines 362–365.\n\nWe believe the gap between the upper and lower bounds can be attributed to inherent structural constraints required by asymptotic confidence sequences (CS). Proposition 2.5 together with Condition L3 of Waudby--Smith et al. (2021) gives a convenient way to construct a valid $(1-\\tilde{\\delta})$ asymptotic CS in our learning setup: Define\n$\\tilde V_t(S_i, S_j)\n= \\sum_{s=1}^t \\sigma_{s}^2(S_i, S_j)\n= \\sum_{s=1}^t \\left(\\frac{\\mathbb{E}[R_s(S_i)^2]}{\\pi^{\\text{MAD}}s(S_i)}+\\frac{ \\mathbb{E}[R_s(S_i)^2]}{\\pi^{\\text{MAD}}s(S_j) }\\right)$.\nIf there exists $\\hat{V}_t(S_i,S_j)$ such that $t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j) \\xrightarrow{a.s.}0$, then $\\hat{\\bar{\\tau}}_t(S_i, S_j) \\pm \\hat C_t(S_i, S_j)$ is a valid ($1-\\tilde{\\delta}$) asymptotic CS, where $\\hat C_t(S_i,S_j)=\\sqrt{\\frac{2(\\hat V_t(S_i,S_j)\\eta^2+1)}{t^2\\eta^2}\n\\log\\left(\\frac{\\sqrt{\\hat V_t(S_i,S_j)\\eta^2+1}}{\\tilde{\\delta}}\\right)}$. \n\nTo ensure $t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j) \\xrightarrow{a.s.}0$, we construct $\\hat V_t(S_i,S_j)$ via the unbiased IPW estimator that is fully computable from the data: $\\hat V_t(S_i, S_j) = \\sum_{s=1}^t  \\frac{ \\mathbf{1}( S_{s} = S_i ) \\cdot R_{s}(S_i)^2 }{ ( \\pi^{\\text{MAD}}s(S_i) )^2 }  + \\frac{ \\mathbf{1}( S_{s} = S_j ) \\cdot R_{s}(S_j)^2 }{ ( \\pi^{\\text{MAD}}s(S_j) )^2 }$. Let $M_s(S_i,S_j):=(\\hat \\sigma_s^2- \\sigma_s^2)(S_i,S_j)$. Then $M_s(S_i,S_j)$ is a martingale difference sequence and $t^{-1}\\sum_{s=1}^t M_s(S_i,S_j)= t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j)$. By the SLLN for martingale difference sequence, if $\\sum_{t=1}^\\infty \\mathbb{E}[M_t^2(S_i,S_j)]/t^2<\\infty$, we obtain $t^{-1}(\\hat V_t-\\tilde V_t)(S_i,S_j)\\xrightarrow{a.s.}0$. This requires $(\\hat \\sigma_t^2 - \\sigma_t^2)^2(S_i,S_j) = o(t)$ (by a $p$-series test).\nIn our design this summability is guaranteed by $1/\\pi_t^{\\mathrm{MAD}}(S)=o(t^{1/4})$ for all $S\\in \\mathcal{U}_E$. Hence, when $\\pi_t^{\\mathrm{MAD}}(S)\\propto t^{-\\alpha}$, we require $\\alpha\\in[0,1/4)$. Under this requirement the CS width behaves as $\\hat C_t=\\tilde{O}(t^{\\alpha-1/2})\\quad \\text{for }\\alpha\\in[0,1/4)$,\nand enforcing $1/\\pi_t^{\\mathrm{MAD}}(S)=o(t^{\\alpha})$ for all $S\\in\\mathcal{U}_E$ induces additional regret $\\tilde{O}(t^{1-\\alpha})$. This ultimately leads to the gap between the lower and upper bounds.\n\nFollowing your suggestion, we will incorporate the above discussion into the main text for clarity. We will also add the corresponding lower bound to the experimental plots.\n\n> ***Q6: Can you provide a detailed ablation study on choice of $\\alpha$?***\n\n---\n\n**A6:** Thank you for your suggestion. We have included an ablation study evaluating the performance of our method under various choices of $\\alpha$. Please see the tables and discussion provided in A8 of our rebuttal to Reviewer 8D4t, we apologize for this due to space constraints.\n\n> ***Q7: Also, it would be interesting to see how the proposed algorithm performs against Simchi-Levi and Wang [2024] and Liang and Bojinov [2023] in network-less setup and Zhang and Wang [2024] in the networked setup.***\n\n---\n\n**A7:** Thank you for your suggestion. We have included a comparison here. \n\nIn the stochastic setting without a network, the algorithm proposed by Simchi-Levi and Wang (2024) achieves a regret upper bound of $R(T, \\pi) = \\tilde{O}(K^5 + T^{1-\\alpha}) \\quad (\\alpha \\in [0,1])$, which relies on an additional assumption that the reward gap between the optimal and suboptimal arms is $\\Theta(1)$, and an ATE estimation error upper bound $e(T, \\hat{\\Delta}) = \\tilde{O}(K^2 T^{\\alpha/2 - 1/2})$, leading to $\\sqrt{R(T, \\pi)} \\cdot e(T, \\hat{\\Delta}) = \\tilde{O}(K^2)$. In comparison, our algorithm achieves $R(T, \\pi) = \\tilde{O}(\\sqrt{KT} + T^{1-\\alpha})$ $(\\alpha \\in [0,1/4])$, $e(T, \\hat{\\Delta}) = \\tilde{O}(KT^{\\alpha - 1/2})$, $\\sqrt{R(T, \\pi)} \\cdot e(T, \\hat{\\Delta}) = \\tilde{O}(KT^{\\alpha/2})$. Thus, our algorithm significantly improves the dependence on $K$, while the dependence on $T$ increases from constant to $T^{\\alpha/2}$. It is worth noting that our algorithm does not rely on the reward gap assumption required by Simchi-Levi and Wang~(2024). \n\nIn the adversarial setting without network interference, Liang and Bojinov~(2023) provide an ATE estimation error upper bound of $\\tilde{O}(KT^{\\alpha - 1/2})$ for $\\alpha \\in [0, 1/4]$, which matches the performance of our algorithm when specialized to the no-network case. Since their work primarily focuses on ATE inference and does not provide a regret upper bound, a direct comparison of regret upper bounds is not straightforward.\n\nIn the stochastic setting with network interference, Zhang and Wang~(2024) propose a two-phase algorithm: the first phase (of length $T_1$) uniformly explores all exposure super arms, while the second phase performs pure regret minimization. They achieve a regret bound of  $R(T, \\pi) = \\tilde{O}(\\sqrt{|\\mathcal{U}_E| T} + T_1)$, and an ATE estimation error of $e(T, \\hat{\\Delta}) = \\tilde{O}(\\sqrt{|\\mathcal{U}_E| / T_1})$, which together yield $\\sqrt{R(T, \\pi)} \\cdot e(T, \\hat{\\Delta}) = \\tilde{O}(\\sqrt{|\\mathcal{U}_E|})$. While their algorithm is theoretically optimal in this setting, we emphasize two key limitations: (i) its theoretical guarantees hinge on the assumption of a specific reward distribution (i.e., the stochastic bandit setting), and (ii) it lacks support for continual monitoring of ATE inference, which hinders the ability to dynamically balance ATE estimation and regret minimization throughout the learning process. In contrast, our design leverages confidence sequences, which enables continual monitoring of ATE inference and dynamic adjustment of the exploration strategy. Therefore, we claim that our design balances the trade-off between statistical inference and regret minimization, whereas theirs only addresses the trade-off between estimation and regret.\n\n**Reference:**\n\nWaudby-Smith I, Arbour D, Sinha R, et al. Time-uniform central limit theory and asymptotic confidence sequences[J]. The Annals of Statistics, 2024, 52(6): 2613-2640.\n\nSimchi-Levi, David and Wang, Chonghuan, Multi-armed Bandit Experimental Design: Online Decision-making and Adaptive Inference (September 20, 2022). Available at SSRN.\n\nLiang B, Bojinov I. An experimental design for anytime-valid causal inference on multi-armed bandits[J]. arXiv preprint arXiv:2311.05794, 2023.\n\nZhang Z, Wang Z. Online experimental design with estimation-regret trade-off under network interference[J]. arXiv preprint arXiv:2412.03727, 2024.\n\nAbhineet Agarwal, Anish Agarwal, Lorenzo Masoero, Justin Whitehouse. A Multi-Armed Bandits with Network Interference, \n\nShishir Adhikari, Sourav Medya, Elena Zheleva. Learning Exposure Mapping Functions for Inferring Heterogeneous Peer Effects"}, {"review_id": "UeUAOumDpL", "reviewer": "Reviewer_8D4t", "summary": "Briefly, the paper presents a modular framework for Multi-Armed Bandits with Network Interference (MABNI). It contributes the trade-off between regret minimization and inference accuracy through establishing a theoretical Pareto frontier for minimizing regret and ATE estimation error in adversarial networked bandit scenarios and also their EXP3 algorithm to address regret minimization, continual inference and ATE estimation error minimization. They manage the action space with exposure mapping and clustering.", "questions": "How is \"overly prioritizing the optimal arm can compromise the inference accuracy of the sub-optimal arm\" neglected? Isn't this a version of exploration-exploitation trade-off, which is pretty standard in bandit research?\n\nThe phrases \"anytime-valid\" and asymptotic do not seem complementary. Please elaborate.\n\nIn (1), how is the adjacency matrix H both a possible argument for the mapping S and part of the domain bold italic S?\n\nLine 159: isn't the size reduced to a power of the size of $d_s$?\n\nThere seems to be mix-up with the notation in the first part of (2). Please properly define $S_t$.\n\nDefinition 3.2: explain ATE here.\n\n(3): what is the usage of the subscript in R? Adversarial nature? It is undefined.\n\nAlso, why is the lower-bound in Theorem 3.1 of importance? Why is the multiplication of square-root regret and ATE error is specifically chosen for lower bounding?\n\nThe experiments section can be improved. The figures only support the theoretical findings in a basic manner. Maybe replace the figures with tables to properly report various experimental results.", "limitations": "no, you can include some comments in conclusion.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Quality: \nThe submission is somewhat technically sound.\nClaims are supported by theoretical analysis and experimental results.\nThe methods used are appropriate, each addressing different aspects in a modular fashion.\nThis is a complete piece of work, with some open problems as a future direction.\nThe authors are careful and honest about evaluating both the strengths and weaknesses of their work, but experiments section is a bit neglected.\n\n### Clarity: \nThe submission is mostly clearly written.\nIt is generally well organized.\nIt seems to adequately inform the reader by providing enough information to reproduce its results.\n\n### Significance: \nThe results are impactful for the community, with a well-establish trade-off between regret minimization and inference accuracy for consideration in critical practical applications.\nOthers (researchers or practitioners) are likely to use the ideas or build on them.\nThe submission addresses a difficult task in a better way than previous work, as demonstrated by the shortcomings of the past works.\nIt advances our understanding and knowledge on the topic in a demonstrable way. However, the importance of lower-bound is ambiguous and there exists an optimality gap.\nIt provides a unique theoretical modular framework.\n\n### Originality: \nThe work provides new insights and deepen understanding for MABNI trade-off with pareto frontier.\nIt is clear how this work differs from previous contributions, with relevant citations provided.\nThe work introduces novel methods that advance the field.\nThis work offers a novel combination of existing techniques to address different objectives, and the reasoning behind this combination is well-articulated.", "was_revised": true, "final_justification": "My questions (and also many other concerns raised by the reviewers) were mostly answered. The authors improved the clarity through resolving ambiguities, better conveyed the significance via adequate explanations, and elevated the experimental evaluation to highlight the impact of their work.", "rebuttal": "Thank you for your thoughtful and encouraging evaluation. We’re glad that you found our work to be clearly written and technically sound. We have carefully addressed your concerns in our responses below.\n\n> ***Q1: How is \"overly prioritizing the optimal arm can compromise the inference accuracy of the sub-optimal arm\" neglected? Isn't this a version of exploration-exploitation trade-off, which is pretty standard in bandit research?***\n\n---\n\n**A1:** Thank you for the insightful question. While this statement shares similarities with the standard exploration-exploitation trade-off in bandit problems, there are some important differences. In classical bandit problems focused solely on regret minimization, exploration is primarily used to (implicitly) identify the best arm. Once identified, the algorithm simply pulls it, and the learning objective is fulfilled. However, in our setting, even if the best arm is known, the task is not complete. We still need to allocate pulls to all suboptimal arms in order to accurately estimate their expected rewards and, consequently, the ATE. This introduces a more delicate trade-off, where overly prioritizing the best arm can compromise the accuracy of ATE estimation.\n\n> ***Q2: The phrases \"anytime-valid\" and asymptotic do not seem complementary. Please elaborate.***\n\n---\n\n**A2:** Thank you for your suggestion. A confidence sequence (CS) $(I_t)_{t \\ge 1}$ is called anytime-valid if: $\\mathbb{P} (\\forall t \\geq 1,\\ \\theta^*_t \\in I_t) \\geq 1 - \\delta$. This property ensures that the interval is valid at all time points (i.e., $t\\ge1$) simultaneously.\n\nThe notion of an asymptotic CS was first introduced by Waudby-Smith et al. (2021). Formally, define $\\hat \\mu_t \\pm C_t^*$ as a non-asymptotic $(1 - \\tilde \\delta)$ CS for a sequence of target parameters $\\mu_t$, \n\nand another CS $\\hat \\mu_t \\pm \\hat C_t$ such that $\\hat C_t/C_t^* \\xrightarrow{\\text{a.s.}} 1$, then $\\hat \\mu_t \\pm \\hat C_t$ is said to be an asymptotic $(1 - \\tilde{\\delta})$ CS for $\\mu_t$. A non-asymptotic confidence sequence with confidence level $1 - \\tilde{\\delta}$ is a sequence of intervals $\\hat \\mu_t \\pm C_t^*$ such that, with probability at least $1 - \\tilde{\\delta}$, all intervals simultaneously cover the target parameters with probability at least $1 - \\tilde{\\delta}$.\n\n>***Q3: In (1), how is the adjacency matrix H both a possible argument for the mapping S and part of the domain bold italic S?***\n---\n**A3:** Thank you for your careful reading. We acknowledge the confusion around the role of the adjacency matrix $H$ in the definition of the exposure mapping $S(\\cdot)$. To clarify: in our framework, $H$ is treated as an **external input** to the exposure mapping $S$, i.e., $S_i = S(H, A)$, where $A$ is the treatment assignment. The function $S$ maps the global treatment and network context into a lower-dimensional summary (e.g., degree-weighted exposure). The bold italic $\\mathcal{S}$ denotes the **codomain** or the **range** of possible exposure values, and does not itself contain $H$. To avoid ambiguity, we have revised the notation in the paper to make this distinction explicit: $S : \\{0,1\\}^N \\times \\mathbb{R}^{N \\times N} \\to \\mathcal{S}$, where $H \\in \\mathbb{R}^{N \\times N}$ is the adjacency matrix. We thank the reviewer for pointing this out.\n\n\n\n\n> ***Q4: Line 159: isn't the size reduced to a power of the size of $d_s$?*** \n\n---\n\n**A4:** Thank you for the suggestion. Yes, due to the exposure mapping and clustering procedures, the size of the exposure super arm set is reduced to $d_s^C$, where $d_s$ denotes the number of exposure arms and $C$ is the number of clusters. We have clarified this point in Line~178.\n\n> ***Q5: There seems to be mix-up with the notation in the first part of (2). Please properly define $S_t$.***\n\n---\n\n**A5:** Thank you for your suggestion. In our paper, $S_t$ denotes the exposure super arm selected by the learning algorithm in round $t$.\n\n\n\n>***Q6: Definition 3.2: explain ATE***\n---\n**A6:** The ATE (Average Treatment Effect) defined here intuitively captures: the average difference in group-level responses when assigning the entire population to two different exposure super arms $S_i$ and $S_j$ over multiple rounds. Formally,  it measures the mean outcome difference across $t$ rounds between these two exposure conditions.\n\n\n\n> ***Q7: What is the usage of the subscript in $R$? Adversarial nature? It is undefined.***\n\n---\n\n**A7:** Thank you for your question. In Lines 139--141, we define $\\mathcal E_0$ as the set of all legitimate instances of the adversarial bandit with network interference. The notation $\\nu$ in our paper refers to a specific instance in $\\mathcal E_0$. Therefore, in Eq.~(3), $R_{\\nu}(\\pi, T)$ denotes the regret incurred by algorithm $\\pi$ under the adversarial instance $\\nu \\in \\mathcal{E}_0$.\n\n> ***Q8: Why is the lower-bound in Theorem 3.1 of importance? Why is the multiplication of square-root regret and ATE error is specifically chosen for lower bounding?***\n---\n**A8:** This is the standard paradigm to express the trade-off (it has been proved to be optimal in the stochastics setting), referring to Zhang et al and Simchi et al. \n\n\n> ***Q9: The experiments section can be improved. The figures only support the theoretical findings in a basic manner. Maybe replace the figures with tables to properly report various experimental results.***\n\n---\n\n**A9:** Thank you for the helpful suggestion. In the revised manuscript, we have replaced the original figures with tables that more systematically summarize the experimental results. These tables report key metrics — including cumulative regret, confidence sequence width, and ATE estimation error — under different choices of the parameter $\\alpha$. Following the experimental setup described in the main text, an example of the revised result tables is shown below:\n\n**Final Cumulative Regret (T = 10,000)**\n\n\n| Method      | Parameters    | Mean     | SE     |\n|-------------|--------------|----------|--------|\n| Uniform     | -            | 189.30   | 2.84   |\n| EXP3_N_CS   | $\\alpha$=0.05| 167.25   | 2.36   |\n| EXP3_N_CS   | $\\alpha$=0.1 | 152.97   | 2.14   |\n| EXP3_N_CS   | $\\alpha$=0.15 | 143.78   | 2.05   |\n| EXP3_N_CS   | $\\alpha$=0.2 | 137.99   | 1.99   |\n| EXP3_N_CS   | $\\alpha$=0.24| 134.21   | 2.01   |\n| Standard    | -            | 127.09   | 2.01   |\n\n\n\n**Final Confidence Sequence Width (T = 10,000)**\n\n| Method      | Parameters    | Mean     | SE      |\n|-------------|--------------|----------|---------|\n| Uniform     | -            | 0.1924   | 0.0001  |\n| EXP3_N_CS   | $\\alpha$=0.05| 0.1972   | 0.0003  |\n| EXP3_N_CS   | $\\alpha$=0.1 | 0.2062   | 0.0006  |\n| EXP3_N_CS   | $\\alpha$=0.15 | 0.2157 | 0.0009  |\n| EXP3_N_CS   | $\\alpha$=0.2 | 0.2247   | 0.0012  |\n| EXP3_N_CS   | $\\alpha$=0.24| 0.2362   | 0.0015  |\n| Standard    | -            | 0.2801   | 0.0042  |\n\n\n\n**ATE Difference Statistics (T = 10,000)**\n\n\n| Method      | Parameters    | Mean     | Median  | Std     |\n|-------------|--------------|----------|---------|---------|\n| Uniform     | -            | 0.0287   | 0.0274  | 0.0122  |\n| EXP3_N_CS   | $\\alpha$=0.05| 0.0294   | 0.0285  | 0.0120  |\n| EXP3_N_CS   | $\\alpha$=0.1 | 0.0307   | 0.0294  | 0.0131  |\n| EXP3_N_CS   | $\\alpha$=0.15 | 0.0326   | 0.0303  | 0.0148  |\n| EXP3_N_CS   | $\\alpha$=0.2 | 0.0334   | 0.0315  | 0.0152  |\n| EXP3_N_CS   | $\\alpha$=0.24| 0.0364   | 0.0339  | 0.0172  |\n| Standard    | -            | 0.0658   | 0.0332  | 0.0882  |\n\n\nAs shown in the tables, increasing $\\alpha$ reduces cumulative regret but slightly increases the confidence sequence width and ATE estimation error. Notably, $\\alpha = 0.24$ achieves a balanced trade-off: its regret is close to that of the Standard baseline (EXP3 with network), while its confidence sequence width and ATE estimation error remain close to those of the Uniform baseline (uniform exploration).\n\n**Reference:** \n\nWaudby-Smith I, Arbour D, Sinha R, et al. Time-uniform central limit theory and asymptotic confidence sequences[J]. The Annals of Statistics, 2024, 52(6): 2613-2640.\n\nSimchi-Levi, David and Wang, Chonghuan, Multi-armed Bandit Experimental Design: Online Decision-making and Adaptive Inference (September 20, 2022). Available at SSRN.\n\nZhang Z, Wang Z. Online experimental design with estimation-regret trade-off under network interference[J]. arXiv preprint arXiv:2412.03727, 2024."}, {"review_id": "34yrgrbR4s", "reviewer": "Reviewer_LDZS", "summary": "This paper studies an adversarial bandit problem with network interference where in each round, the decision maker must assign one of K arms to each of the N nodes in a network with some underlying graph structure. The authors study three (generally) competing objectives of regret minimization, validity of post hoc inference and average-treatment-effect estimation and establish Pareto optimality results. They also propose an anytime-valid asymptotic confidence sequence and based on it an EXP3-style algorithm that balances the trade-off between regret minimization and inference accuracy.", "questions": "When N=1, does Theorem 4.1 reduce to Theorem 1 of Simchi-Levi and Wang [2024]? Or Condition 3.1 prohibits this reduction? Further to this point, it would be nice to know how much of the proof of Theorem 4.1 is adapted from the proof of Theorem 1 of Simchi-Levi and Wang [2024]. \n\nIn terms of the algorithm, Simchi-Levi and Wang [2024] also consider a variant of EXP3. Given this, it would be helpful for the readers to know what new technical/analytical contributions the authors make to overcome limitations of prior techniques.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is well-written generally and makes progress on an important problem in causal learning. Addressing causal inference with interference in an online learning setting is quite relevant in practical applications like social networks and large-scale experimentation on platforms. The anytime-valid confidence sequences provided in this paper are important in this context. The authors also generalize the theoretical lower bound of (Simchi-Levi and Wang, 2024) to capture the complexity of the networked setting via a new implicit primitive (effective arm space size).\n\nThe following are not weaknesses, just some resistance I encountered while parsing the content: \nSome constructs (e.g., exposure mappings and clustering) are not common in traditional bandit literature and might need a little more context and/or instantiation via examples for readers not entirely familiar with the causal inference/bandit learning interface. I understand the paper is constrained to be within 9 pages, but it would be useful if the model development in S3.1 and S3.2 is pre-padded with a little more context in this regard. While not a weakness per se of the paper, it is less than ideal that the main algorithm itself is pushed to supplementary pages together with a high-level discussion of what it does. This leaves S5.2 somewhat obscure on the first read.\n\nI want to emphasize that I liked reading the paper but my conservative score is a consequence of being unable to place the methodological and analytical contributions in this work vis-a-vis prior art. In particular, though the networked model under interference is a significant generalization of the simple setting of (Simchi-Levi and Wang, 2024), the hardness of analyzing this setting is not very clear. I would be open to revising my scores pending a satisfactory rebuttal to this end.", "was_revised": true, "final_justification": "The author response was comprehensive and helped me contextualize their results better. It also resolved my initial concern (favorably) about differentiation from prior work.", "rebuttal": "Thanks for your comments! We will address it point by point.\n\n>***Q1: The following are not weaknesses, just some resistance I encountered while parsing the content: Some constructs (e.g., exposure mappings and clustering) are not common in traditional bandit literature and might need a little more context and/or instantiation via examples...While not a weakness per se of the paper, it is less than ideal that the main algorithm itself is pushed to supplementary pages together with a high-level discussion of what it does. This leaves S5.2 somewhat obscure on the first read.***\n---\n**A1:** Exposure mapping (and clustering) is a well-established concept in causal inference and experimental design. Our goal is to extend this idea to the online learning and bandit setting. Intuitively, exposure mapping embeds the exponentially large action space $K^N$ into a lower-dimensional space or manifold of size $|\\mathcal{U}_{\\mathcal{E}}|$, via a mapping defined as:\n\n$$\ns \\equiv \\mathbf{S}(i, A, \\mathbb{H}), \\quad \\text{where } \\mathbf{S}: \\mathcal{U} \\times \\mathcal{K}^{\\mathcal{U}} \\times \\mathbb{H} \\rightarrow \\mathcal{U}_s.\n$$\n\nFor example, in real-world scenarios such as COVID-19 treatment or ride-sharing dispatch, the exposure mapping can encode the proportion of a unit’s neighbors who are treated (e.g., receiving medication or requesting a ride). Based on this, we further apply clustering to reduce the dimensionality of the exposure-based arm space, ensuring that the action space $|\\mathcal{U}_{E}|$ remains computationally feasible. In the revised version, we will provide a more intuitive exposition of the exposure mapping and move the main algorithm into the main text to enhance readability.\n\n\n\n\n>***Q2: When N=1, does Theorem 4.1 reduce to Theorem 1 of Simchi-Levi and Wang (2024)? Or Condition 3.1 prohibits this reduction? Further to this point, it would be nice to know how much of the proof of Theorem 4.1 is adapted from the proof of Theorem 1 of Simchi-Levi and Wang [2024]. In particular, though the networked model under interference is a significant generalization of the simple setting of (Simchi-Levi and Wang, 2024), the hardness of analyzing this setting is not very clear. I would be open to revising my scores pending a satisfactory rebuttal to this end.***\n---\n**A2:** \nWhen $N = 1$, our setting naturally reduces to a case similar to that of Simchi-Levi and Wang (2024). However, our results are **strictly stronger**: we not only retain tightness in the time horizon $T$, but also in the total action space dimension. This extension is both necessary and important—under network interference, the action space can grow exponentially large, rendering the conclusions in Simchi-Levi and Wang \\[2024] inapplicable.\n\nFor example, even if we take a simplified exposure mapping where each unit's exposure is defined by its cluster index (with $M$ clusters), the resulting action space already contains $2^{d_s}$ possibilities. In practice, our exposure arm space can be much richer—for instance, encoding the proportion of treated neighbors—which is essential for capturing a broad range of network interference scenarios.\n\nThis conceptual advancement naturally gives rise to new technical challenges, beyond those addressed in Simchi-Levi and Wang (2024). We summarize these challenges into three key dimensions:\n\n\n\n**``Global Counterexample Construction under Network Interference``**\nIn the Simchi-Levi et al., (2024), the lower bound is constructed via a simple reward gap between two arms—localized and independent across individuals. In contrast, our setting involves network interference, where the reward function depends on the joint action profile across the network. This requires designing globally distinguishable yet locally indistinguishable problem instances—i.e., constructing interference-aware reward functions that are information-theoretically hard to distinguish under a limited number of observations. This significantly increases the complexity of the lower bound argument.\n\n**``Robustness to Misspecification and Approximation Error``**\nIn our case, we could further explicitly account for misspecification between the inference mechanism (e.g., IPW/REG/DR estimators) and the actual exposure structure or clustering granularity. As a result, our analysis must control for functional approximation error in the estimation layer, which creates an additional regret–inference tradeoff not addressed in prior work. We give a brief illustration: Let $\\hat\\Delta_T(S_i,S_j)$  be our IPW estimator based on the *designed* exposure super-arms $S_i,S_j\\in\\mathcal U_{E}$. Denote by $\\bar{\\tau}^{\\star}_T(S_i, S_j)$ the *true* ATE computed under the (possibly finer) ground-truth exposure mapping $S^{\\star}$. Define the ``approximation (misspecification) bias`` $\\mathcal B(\\mathbf S,\\mathcal C)$ as follows:\n\n$\\max_{S_i,S_j\\in\\mathcal U_{\\mathcal{E}}} := |\\bar{\\tau}^{\\star}_T(S_i,S_j)-\\bar{\\tau}_T(S_i,S_j)|,$ we prove the *biased* minimax lower bound  \n\n$\\min_{\\pi, \\hat{\\Delta}} \\max_{v \\in \\mathcal{E}_0}\\sqrt{R(T, \\pi)} \\cdot (e(T, \\hat{\\Delta}) - \\mathcal B(\\mathbf S,\\mathcal C) )= {\\Omega}(\\sqrt{|\\mathcal{U}_E|}).$\n\n\nIntuitively, misspecification bias introduces larger errors. However, we can maintain robustness by controlling the term $(e(T, \\hat{\\Delta}) - \\mathcal B(\\mathbf S,\\mathcal C) $ to preserve our lower bound to show robustness: ``even after subtracting the systematic bias, the regret–inference product cannot beat the lower bound barrier``; it is strictly higher than in the perfectly-specified setting in the previous literature. We have added it in our revised version.\n\n\n**``Transformation between Adversarial & Stochastic Settings``**\nSimchi(2024) operates entirely in a stochastic regime. Our analysis, by contrast, develops the lower bound in an adversarial design-based framework, and further shows that this bound recovers the classical stochastic lower bound under special cases of the exposure mapping. This unification reveals that both regimes share a common fundamental tradeoff structure and establishes a stronger minimax lower bound valid under broader assumptions.\n\n\n\n\n\n>***Q3: In terms of the algorithm, Simchi-Levi and Wang (2024) also consider a variant of EXP3. Given this, it would be helpful for the readers to know what new technical/analytical contributions the authors make to overcome limitations of prior techniques.***\n---\n**A3:** Thank you for the suggestion. We have now clarified the technical/conceptual contributions of our algorithm.\n\n1. We develop a uniform analysis framework that enables our MAD design, combined with an asymptotic confidence sequence, to be seamlessly integrated into any general regret minimization algorithm in adversarial settings. Note that the MAD strategy takes the form $\\pi_t^{\\text{MAD}}(S) = \\frac{1}{|U_E|} \\delta_t + (1 - \\delta_t) \\pi_t^{\\text{ALG}}(S)$, where the first term (with coefficient $\\delta_t$) is introduced to improve ATE estimation, and the second term $\\pi_t^{\\text{ALG}}(S)$ is the base algorithm aimed at regret minimization. To analyze the regret, we decompose the total regret into two components corresponding to the two terms in the strategy, and then separately upper bound each. As shown in Theorem 5.6 (ii), the first part of the regret scales as $\\sqrt{|U_{E}| T}$, which comes from the $(1 - \\delta_t)\\pi_t^{\\text{ALG}}(S)$ term (in our case, a network variant of EXP3), and the second part scales as $T^{1 - \\alpha}$, arising from the $\\frac{1}{|U_{E}|} \\delta_t$ term, which is independent of the specific base algorithm. Therefore, we can easily analyze the overall regret upper bound as $\\tilde{O}(X + T^{1 - \\alpha})$, where $X$ denotes the regret of the base algorithm. In contrast, the method by Simchi-Levi and Wang (2024) improves ATE estimation by adding extra exploration that depends heavily on the structure of his elimination-based EXP3.  Their tight coupling makes it non-trivial to extend such sampling strategies to other adversarial bandit algorithms, such as EXP3-IX. \n\n2. Simchi-Levi and Wang (2024)'s algorithm is heavily depended on the arm number $K$, i.e., $R(T, \\pi) = \\tilde{O}(K^5 + T^{1 - \\alpha}) \\quad (\\alpha \\in [0, 1])$ and $e(T, \\hat{\\Delta}) = \\tilde{O}(K^2 T^{\\alpha/2 - 1/2})$. This result is largely due to the inefficiency of their additional exploration strategy. Moreover, their theoretical guarantees rely on the assumption that the reward gap between the optimal and suboptimal arms is $\\Theta(1)$, which limits generality. While this may be acceptable in Chonghuan’s networkless setting, where $K$ can be treated as a relatively insignificant constant, our exposure action set $U_E$ intertwines $K$ with other critical quantities—such as the number of nodes $N$ and the degree of interference—thereby making it a central parameter in our analysis. As a result, directly extending Simchi-Levi and Wang (2024)’s method to the networked setting is less effective. By leveraging the modularity of MAD, our framework can easily decouple additional exploration from regret minimization. As a result, we obtain regret and ATE bounds $R(T, \\pi) = \\tilde{O}(\\sqrt{|U_{E}|T} + T^{1 - \\alpha})$ for $\\alpha \\in [0, 1/4]$, and $e(T, \\hat{\\Delta}) = \\tilde{O}(|U_E| T^{\\alpha - 1/2})$, which are significantly less sensitive to the size of $U_E$.\n\n**Reference:**\n\nSimchi-Levi, David and Wang, Chonghuan, Multi-armed Bandit Experimental Design: Online Decision-making and Adaptive Inference (September 20, 2022). Available at SSRN.\n\nZhang Z, Wang Z. Online experimental design with estimation-regret trade-off under network interference[J]. arXiv preprint arXiv:2412.03727, 2024.\n\nMichael P. Leung, Causal Inference Under Approximate Neighborhood Interference."}]

Author rebuttal:

Meta-review: This paper studies the problem of bandits with network interference under objectives of jointly minimizing the regret and estimating the treatment effect in the adversarial environment. The paper establishes an essential tradeoff between them and constructs an algorithm, EXP3-N-CS that tries to optimize it. Though the derived lower and upper bounds have some gap, detailed experiments are conducted to examine the tradeoff.

The reviewers agreed in the opinions that the paper is well-motivated and has solid technical contributions. While several questions and concerns such as the ones on the presentation and practical aspects are raised, they are well-addressed in the rebuttal. Based on these observations I determined to recommend acceptance. I would expect that the authors polish the paper in the final version by incorporating the discussions with the reviewers.

While this paper makes good contribution in the area of causal inference, my concern is the interest to general NeurIPS community. Indeed, while the high-level message on the tradeoff between the regret minimization and the treatment effect estimation is very interesting, the explanation of the model heavily relies on the context of causal inference (in particular, seemingly [Leung 2022a]) and it is very hard to understand. For example, the meaning of "exposure" is explained nowhere despite its heavy use. Combined with the inappropriate or wrong notation (please see below), I gave up to understand the formal definition of the considered model, which seems to also apply to other readers outside the area of causal inference. I would expect that the authors authors also address this point so that the paper becomes of broader interest.

Examples of the problems I encountered when reading the model is as follows.
- Since no intuitive meaning of "exposure mapping" is introduced, the exposure mapping $\mathbf{S}$ has to be just regarded as an abstract function in the form of (1). Here, the second $\mathbb{H}$ in (1) seems to be a typo, since it must be a domain of the first $\mathbb{H}$. $\mathcal{U}_s$ is just explained as "the set with $d_s$ exposure arm", but since (1) is the equation to define the "exposure arm", this explanation is cyclic. Similarly, it is strange that the notation like $d_s$ appears in the definition of $s$.
- In addition, the example in the L176 says that $\mathcal{U}_c$ is not a set and is 0 or 1, which is incompatible with the description of (1). Is this a typo for $\mathcal{U}_s=\\{0,1\\}$? I don't see why in this case $\mathcal{U}_C$ is automatically determined without specifying the function $\mathbf{S}$.
- $S_t$ is undefined. I guess it is $\mathbf{S}(i, A_t, \mathbb{H})$ but, if so, what is $\mathbb{P}(S_t|\mathcal{H}_t)$ in (2)? Is this a random variable such that $\mathbb{P}(S_t=S|\mathcal{H}_t)$ where $S_t$ (a random variable) is substituted to $S$? Does this mean something like $\pi_t(A, S_t)$ rather than $\pi_t(A)$?
- I guess that $\mathbf{\mathrm{S}}$ in (1) is a typo for the italic. Similarly there also seems to be a confusion for $C_q$ and $\mathcal{C}_q$.

In general, since the notion of the exposure mapping seems to be a part of the model itself, I believe that the formal definition and its advantage should not be described in a mixed way like a current one.
Decision: Accept (poster)