Online Experimental Design With Estimation-Regret Trade-off Under Network Interference
Authors: Zhiheng Zhang
Zichen Wang
Venue: NeurIPS 2025 poster ()
Keywords: Online experimental design
Causal inference
Network interference
Multi-armed bandits
Primary area: probabilistic_methods
TL;DR: Online Experimental Design With Estimation-Regret Trade-off Under Network Interference

Abstract: Network interference has attracted significant attention in the field of causal inference, encapsulating various sociological behaviors in which the treatment assigned to one individual within a network
may affect the outcomes of others, such as their neighbors. A key challenge in this setting is that
standard causal inference methods often assume independent treatment effects among individuals,
which may not hold in networked environments. To estimate interference-aware causal effects, a
traditional approach is to inherit the independent settings, where practitioners randomly assign experimental participants to different groups and compare their outcomes. Although effective in offline
settings, this strategy becomes problematic in sequential experiments, where suboptimal decisions persist, leading to substantial regret. To address this issue, we introduce a unified interference-aware framework for online experimental design. Compared to existing studies, we extend the
definition of arm space using the statistical concept of exposure mapping, which allows for
a more flexible and context-aware representation of treatment effects in network settings. Crucially, we establish a Pareto-optimal trade-off between estimation accuracy and regret under the
network concerning both time period and arm space, which remains superior to baseline models
even without network interference. Furthermore, we propose an algorithmic implementation and
discuss its generalization in different learning settings and network topology.

Online Experimental Design With Estimation-Regret Trade-off Under Network Interference
Zhiheng Zhang*
School 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
Zichen Wang"
Department of ECE and CSL UICC
Abstract
Network interference has attracted significant attention the field of causal infer- ence, encapsulating various sociological behaviors in which the treatment assigned one individual within network may affect the outcomes of others, such as their neighbors. A key challenge in this setting is that standard causal inference methods often assume independent treatment effects among individuals, which may not hold in networked environments. To estimate interference-aver tional approach is to inherit the independent settings, where practitioners randomly assign experimental participants to different groups and compare their outcomes. Although effective offline settings, this strategy becomes problematic in sequen- tial experiments, where suboptimal decisions persist, leading substantial regret. To address this issue, we introduce a unified interference-awant framework for online experimental design. Compared to existing studies, extend the definition arm space using the statistical concept exposure mapping, which allows for more flexible and context-aware representation of treatment effects in network settings. Crucially, we establish Pareto-optimal trade-off between estimation accuracy and regret under the network concerning both time period and arm space, which remains superior to baseline models even without network interference. Fur- thermore, we propose an algorithmic implementation and discuss its generalization in different learning settings and network topology.
causal effects, tradi-
Introduction
Network interference has attracted significant attention in the fields of causal inference [Leung 2022a b
2023 Ma and Tresp) (02TT and online statistical learning theory [Agarwal et al. 2024
Jia et al. 2024 due to its capability to capture more complex real-world interactions. Unlike the
Stable Unit Treatment Value Assumption (SUTVA) assumption [Imbens] 2024), which posits that the treatment assignment and outcomes are isolated to individuals, network interference acknowledges
the influences that treatments received by one individual may have on the outcomes others within
network. This model has found extensive application in economics [Apino and Mattei] 2016 Munro
et al. 2 and social sciences [Bandiera et al. 2009 Bond et al., [2012] Paluck et al.
2016 Imbens
2024
where understanding such interconnected dynamics is erucial.
Equul contribution.
Corresponding author, Email: zhangahtheng@ma1l. shufe.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To successfully identify causal effect under network interference, one straightforward way is to conduct randomized experiments and use the difference in means type estimators to estimate causal
effect based on the experimental data [eugg 2022a b 2023 Gao and Ding 2023] Such design is
related to many applications [Ciotti et al. | Cai et al. 2015]. For instance, Ciotti et al. [2020] suggested the randomized experiment on a group of volunteering patients to investigate the therapeutic average treatment effects of various drugs for influenza, e.g., COVID-19, 19, where each individual's status of cure is influenced by the treatment assignment of their neighboring individuals. In practice, an experiment may consist of multiple rounds, and researchers may wish to use the experimental data from the previous rounds to enhance the social welfare of the experimental participants by minimizing the regret of the future rounds [Mok et al. 2021]. This requires us to consider the trade- off between the estimation accuracy of the causal effect and the cumulative regrer of the experiment. Apparently, such an online experiment represents a more complex design than offline. For example, if experimental designers directly borrow the Bernoulli sampling in offine design [Leung 2022a], they would empirically result in a regret linear to round time due to the lack of optimal strategy exploration. This motivates us to design sequential policy that theoretically guarantees the optimal trade-off between the two objectives under interference. Besides, such sequential policy is also relevant to multi-armed bandits with network interference literature (Jia et al. 2024 Agarwal et al. 2024]. which focuses primarily on minimizing regret rather than improving estimation accuracy.
To reiterate, it is crucial to recognize that estimation efficiency and regret might not be optimized simultaneously, necessitating a careful consideration of the trade-off between these two objectives. Optimal estimation efficiency, such as the Bernoulli design above, generally requires that the sampling probability of each arm remains strictly greater than zero, where the sub-optimal decision persists, leading to substantial regret. Conversely, optimal algorithms, such the Upper Confidence Bound (UCB) [Auer et al. 2002) and its variants, employ probability-vanishhe
exploration strategies for sub-optimal arms, potentially violating the overlap assumption in causal inference (D'Amour et al.) 2021]. This violation limits the estimator's precision, as the overlap assumption is critical for ensuring valid causal inferences by maintaining sufficient data across all arms |Sekhon| 2009
Existing works that explore the estimation-regret trade-off often overlook the presence of network interference, effectively assuming a scenario where only single individual is considered throughout the experiment. Perspectives include empirical algorithm design [Liang and Bojinov] 2023]. theoreti- cal bi-objective optimization (Simchi-Levi and Wang 2024]. and analyses of the interaction between trade-offs and exogenous model assumptions [Duan et al. 2024]. In comparison, our work extends such a trade-off in the context of network interference. Integrating the aforementioned perspectives requires an elevated viewpoint to construct challenging yet more universally applicable framework. Specifically, we introduce a unified online network enterference-based experimental design setting, referred to as MAB-N. This setting extends the definition of arm space in the multi-armed bandit (MAB) literature by employing the statistical concept of exposure mapping [Leung] 2022a Aronow and Samii 2017). We derive the theoretical optimal estimation reggeet tradc-off within it and provide an algorithmic implementation capable of achieving this optimal balance. Our contributions are summarized as follows: 1) We establish a unified setting for online experimental design with network interference, referred to as MAB-N, which leverages the statistical concept of exposure mapping. 2) We bridge the multi-objective minimax trade-off, achieving Pareto-optimality between treatment effect estimation and regret efficiency under network interference. Additionally, we propose criteria for a MAB algorithm to achieve Pareto-optimality. 3) We propose the UCB-TSN algorithm to achieve the aforementioned Pareto trade-off by constructing an upper bound for both the Average treatment effect (ATE) estimation error and regret, which is also validated by experiments. Our UCB-TSN algorithm outperforms the elegant preliminary work in (i) the degenerated single-unit case without interference and (ii) the extended adversarial bandit setting. The simulation results are provided in the Appendix to validate its effectiveness.
Our paper is organized as follows: Section 2 provides a brief literature review. Section 3 introduces our general MAB-N setting and discusses Pareto-optimality to illustrate the estimation-regret off. Section 4 provides provides general lower bound for the joint performance of regret and estimation, followed by the criteria for any algorithm to achieve Pareto optimality. Section 5 proposes the Pareto-optimal algorithmic implementation and includes comparison with the baseline. Section 6 extends MAB-N to adversarial cases. Finally, Section 7 concludes the paper with further discussion.
2

---

2 Related Work
Our results primarily bridge two lines of research: (i) extending bandit modeling scenarios by integrating interference settings from the statistical community [Agarwal et al., 2024] Tia al.) 2024], and (ii) exploring the trade-off between estimation and regret in online learning without network interference [Simchi-LLevi and Wang 2024, Duan et al. 2024], as detailed in Table 2 in Appendix C
In the first line of research, the insightful work of Agarwal et al. [2024) creatively utilizes Fourier analysis to reformulate interference-awe innovative approach, however, focuses on interference among first-order neighbors and incorporates a sparsity assumption to limit the number of neighbors each node can have. Complementing this, the meticulous study by Jia et al. [024]] advances the understanding of bandits under interference by forgoing such assumptions, though their methodology requires switchback design. This design insists that all nodes adopt the same
bandits as sparse linear stochastic bandits. This
synchronously, potentially overlooking scenarios where the optimal arm varies across nodes or subgroups. Turning to the second line of research, we commend Simehi-Levi and Wang [2024] for pioneering rigorous trade-off between regret and estimation error. Additionally, Duan et al. (024) contribute significantly by proposing enhancements to this Pareto-optimality, suggesting that both regret and estimation error might simultaneously reach their
optimal levels under the thoughtful assumption of covariate diversity. We invite readers to explore further details on these related works in Appendix C
3 Framework
Classic MAB under network interference. We introduce our setting following Agarwal al. [2024), which generalizes Auer et al. (2002). SimchiiLevi and Wang (2024) to the network inter- ference. We focus on the stochastic bandit problem involving a K-armed set K. = { K-1 an N-unit set 4 = (i) and the time horizon / E [T]. The relationship between units is encoded in the adjacency matrix H == (huglisje E {0, 1] x where h4 = signifies that units i and j are neighbors, whereas he, = 0 otherwise. K, N, are predefined. At each round, unit interactions induce interference effects. The original super arm is represented by an N-dimension vector 4 == (d1.ty..., aN,+) KM To bridge this formulation to causal inference,
start by notating the so-called potential outcome in statistics [Rubin| 2005) (expected reward in the bandit community [Auer et al. 2002) ) as (Y:(A)))
[Ya(a1,, 02 ....a,,)) for unit i in time O Without loss of generality, we set Vi E U1 A E KM (,))) [0, 1]. In this sense, the single-unir reward of unit i upon time is given by (At) = -Y,(A,) Th,t where (-,+(-) represents the reward function of unit E U4, and 1/i,t is zero-mean i..d. 1-sub Gaussian noise for each unit. Finally, define instance v as any legitimate choice of (A))
where (A): denotes the
reward distribution of unit if super arm A is pulled; and then denote Eo the set of all feasible v. Our primary interest is designing a learning policy π == (TI,..,, TT). In round 6, the agent observes the history H4-1 = {AA,, (Ar))e ..... A,
(A,-1) }. where each term is an N N-dimensional vector. The policy n, is probabilistic map from He-1 to the next action A,, We denote Te (A) = P= = A 1) indicating the probability that a super arm A is selected in round t.
Additional notation. We define e; as the standard basis vector whose i-th element is 1 and all other elements are O. For any Q N+, we use the shorthand notation [Q] 2,, Q}. We define the operations: a V {an Ine and {b,, Inggt, we adopt the following asymptotic notations: an = ((b..) if there exists a constant C > 0 such that for all sufficiently large n, an < Cbn.: an = ((bb,) ) if there exists a constant C. > 0 such that for all sufficiently large n, an Cb,.; On = Obb,)) if both On O(b.) and an 2bbb,.. hold. Finally, an Ó(b,) if there exist constants C 0 and A E N+ U (0) such that a. < Cb Cb,ggog b..)*.
max(a, (a,x(a,b), b), a aAb:= == min 6}. For sequences of positive numbers
'It does not mean we must get all information about H: instead, it depends on our detailed design. *Unit i's potential outcome only related to the treatments of the total population via fixed function, as standard in interferrnce- based causality [Leung] 2022alb [2023). J. This setting relaxes the traditional "Stable Unit Treatment Value Assumption" (SUTVA) RRbiin 1980), which assumes that one unit's outcome is unaffected by others' treatments.
3

---

3.1 Motivation: the hardness of classic MAB under interference
In this framework, referring to the concept of cumulative regret in traditional MAB problems more and Szepesvári 2020b), the performance metric of policy could be identified as
Latti
T Σ
I Σ (Y((A).
Rmoive (T, N Y((AA) Ex Σ Σ TE,c(A)) :E(T) KEW
A' arg max MEKS N
(1)
Foreseeably, fundamental challenge in this setting that the original super arm suffers from an exponentially large action space ([K2) = =)*), making direct optimization infeasible. Given this computational burden, we first establish negative result illustrate that directly pursuing the policy using the original super arm is computational impractical.
Proposition 1 Given a priori N, K. H. For any policy л. there exists a hard instance v E Eu such that Ryeive (T, ②T) = C VN (T (TAVKN))
Proposition 1 reveals that the regret convergence rate is influenced by the relative size of the time period compared to the arm space, resulting in a two-piece function. Specifically, when T I KN under interference, the regret Rgoine σ) increases linearly with T. Conversely, otherwise, although the rate degenerates to a square root relative to T, it is adversely affected by an exponentially large parameter KVN/JR /N). This negative result, from a counter perspective, substantiates why Agarwal al. [0024] and Jía et (2024) respectively relaxed the model from the network topology and action space: Agarwal et al. [2024 prudently considers interference only from first-order neighbors and incorporates sparsity assumptions, while Jia al. (2024] restrict the action space the all one and all zero N N-dimensional vector. Without such considerations, obtaining meaningful regret bounds would be unfeasible.
Further, it manifests more insights upon the triple of concepts (i) time, (ii) regret, and (iii) arm space, than lower bound analysis in classic MAB [Ltttmore and Szepesvári 2020b It is because researchers tend to preemptively judge that "time period >> arm numbers", e.g., force N = 1 in the single-unit setting and then T >> K holds by default. However, this oversimplification consideration of arm space can be detrimental under the interference scenario. For instance, even if we just choose K 2, N 30, any algorithm under interference-based MAB setting would potentially be cursed by an impractical regret. In sum, these insights motivate us to develop general statistical framework allow for a more reasonable reduction in the action space dimension without imposing excessive assumptions on the network topology, which is the so-called MAB-N, illustrated as follows.
3.2 Setting: MAB-N
We introduce the concept of exposure mapping developed by Leung [002aa] Aronow and Samil [017]. We define the pre-specified function mapping from the original super arm space (K*)) to a d,-cardinality discrete values (dl < KN) taking advantage of the network structure. For clarity, consider the discrete function case:
8 S(i, A, where S ::u KM x {0, + +U, 114 dg.
(2)
Here U, is called as exposure arm set. We set = (S(i, A, H)) = (81,..., .N) as the exposure super arm, and then we can decompose the policy Tr(-) and define the exposure-based reward:
(A) = P(A. = A H,-1) 1)= = F(A. = S.) H.-1),
(s.) Σ (V(A),, (.))),..((4)) (T()) P(A A | St),
AERU
The second line of Eq generalizes the framework of Leung 2022a by incorporating a broader class of exposure mappings. Specifically, while the original formulation assumes a fixed exposure structure, our approach allows for a more flexible characterization of treatment assignments under network interference. Detailed derivations are deferred to Appendix F To formalize in practice, we could define P(A, A S) predefined, time- inne--nvvriatt sampling rule, which the learner specifies before the learning process begins. For example, in the case of uniform sampling (by default), we have: P. (A, A S) AeEK |(A)/AA), where d(-) is an indicator function, and

---

A= {A (S(i. A, heu = Y denotes the set of all assignments that result in the observed exposure state S,. This formulation ensures that if S does not match the set {S(i, A, H) Jee,. the probability of selecting A, = A given S is zero. Conversely, if S corresponds to this set, then A chosen with strictly positive probability, i.e., P(A, = A | 5) > O. Under this framework, the observed outcome (i().) in Eq (3) depends solely on the network topology and the exposure state S2, independent of the specific arm assignment A,. This highlights key property of exposure mapping: it abstracts away individual-leve treatment assignments while preserving the structural dependencies induced by network interference. To further quantify decision-maiee makinng performance under network interference, we introduce the exposure reward (St), which serves as a proxy for the expected reward in the exposure space] Building on this exposure- brose representation, we now define the regret function, which quantifies the performance gap between the optimal and chosen policies under exposure mapping.
Regret based on exposure mapping. According to the action space reduction in Eq 33. we provide a more general and realistic regret compared to Jia et al.] [2024]. : Simchi-LLevi and Wang (202)) Agarwal et al. 20244) (refer to Example 1-4). We define the clustering set C. := {C₂ ge [C], C C
where Vi + j. E [C],C, Ø, UfC [[Cy)et(c] = U. For brevity, we denote C- c-1(i) as the cluster
of node i. We define the exposure- based regret:
(T( =
T N
P(S))
E
ΣΣ LIET2 iEU
(si)
S" = arg max SEll iEM
Σ Y((S),
(4)
N
EU
where exposure arm space Ug == Ue n Uo with Ue == {s : Vi,j E U1C-1(1) =
C- "() implies Se, = } and Uo := {(S(i, H)))e : A E 1²)) Here, Ue denotes all kinds of ideally cluster- wise switchback exposure super arm. For instance, us E 10,1),00 N 4, Ci {1, C2 {3, 4]. then Uc {k1,, k1, A2, k2) k1, hi E {0, 1}}. Moreover, Uo includes all exposure arm sets compatible with the original arm set. induces that [M4e S [d,l" Essentially, during the exposure mapping process, we efficiently reduce the action space by condensing the original arm information a structured manner, thereby achieving controlled enhancement of regret efficiency. According to Proposition]] I this balance between sacrifice and gain emerges naturally and inevitably. Such cluster-wist wise exposure mapping structures have appeared in multiple prior works. We illustrate how our framework can surroatte previous settings as special cases. By assigning specific parameter values, we can (i) flexibly transition between these cases (the following examples), (ii) allow for adaptive balance in different scenarios (Table in Appendix C and (iii) even characterize new and more general real-world scenarios (experiments in Appendix where existing methods would fundamentally fail.
Comparison with previous literature. For the comparison of regret. Example (i) Classic MAB [Auer al.) [002] Simchi- and Wang, 2024 without network, and HH) == A, A E X. Example (ii) Agarwal et al. [2024] chooses separate cluster). Example (fii On the
considered the case N 1, i.c., single unit
S(i, A, HD) == Ae; and C = N (each unit is assigned other hand, Jia et al. [2024) chooses S(i, A, H) = Ae; and C = 1 (all units are in one cluster), which denotes the global proportion of treatment in each time t. Additionally, the exposure mapping and clustering technique could also be traced back to the offline setting. Example (iv) Suppose
Vj E U. E3 hej O. We can choose Sii, A, Hi) == 1( hija;/ / Ejeu hij E [0, 4)} inherited from the literature of offline causality [Leung, 2022a Gao and Ding 2023 They require approximate neighborhood interference and their objective is to explore the influence of the treatment assignment proportion among all neighborhoods of each unit, which is still under-explored in the online learning scenario (we refer readers to experiments in Appendix [.. Example (v) For a supplement, we point out that the clustering strategy could also be traced back to the offline setting, which is also our special case: Viviano et al. [003)] Zhang and Imail 22033 considered the glustering-based setting S(i, A, H+)
Ae, in which only considers the set of the exposure arm {0, 1)c Specifically, Viviano
et al. 2023 focuses on the Bernoulli design in clusters, while Zhang and Imai 2023 further assumes
that interference occurs only within clusters rather than across clusters.
Notably, the difference between ((())) and the empirically observed reward (A.) arises from two distinct noise components: (i) sampling noise, where practitioners approximate (S.) using samples of (A:)). and (ii) endogenous noise. inherited from the original variability ns, in the observed reward. A detailed discussion noise rescaling is provided in Appendix F
5

---

In these examples, they all satisfy Us = Uc nuo & 0. We provide more justification for it in the next section and Appendix N
3.3 Goal: estimation-regret trade-off
We introduce the trade-off between regret efficiency and statistical power of reward gap estimation.
ATE between exposure super arm S; and Sj is defined as the reward gap (Simchi-Levi and Wang
2024]: A (k.d) == N Eveu (S., - Yy (S;)), where S. S, E MMg. It is a generalized deñnitton compared with the most relevant literature [Jia et al. 2024 Agarwal et al.) 2024 Simchii-Levi
and Wang 2024] when considering ATE (specifying the exposure mapping function as in Table
of Appendix Ct. We use Á (i-j) ;= (A. ((.55) J121, A := {á (t-))) Js..s, J, U,s.S,,es,, Elge to identify a sequence of
adaptive admissible estimates of A (1-5), The total design of an MAB experiment could be represented by the vector (T,, Á}. Our final goal is to portray the mini-max trade-off:
min max (T, A)), where e, (T, (x.A} MEED
B[ 1 (5)
max St,S, EMd
Given any feasible v, (T, TT) is associated with т, while (T, A) is associated with Å. Due to the complicated relation between and Á w.r.t. the history Hr, t E [T]. especially in the network interference setting, this multi-objective optimization quite challenging, For preparation, we define what is the "best" pair of {T, }} via the following definition of front:
Definition (Front and Pareto-dominate) For given pair of {π, Å}, we call a set of pairs (R, e) as front of { Á}. denoted by F(T, Å), if and only if (i) [Feasible instances exists] Vo == {No E E ( (RRo Rev T), eno (T, A) = (R. e)} + 0, and (iilfinstances in Vo are the best] to E E/Vo, S. E {K,T), (R,e) 20 (T, Co, Å)). We claim { Å} Pareto-domines another solution (म', Á'} (R, E F(m, Å). 3(RL e') E F(T', A'), such that V@ E &(KTT) either (i) R S R', e Kg d' (ii) R X R', te
We formalize the definition of front in the symbol of order 5 -ag e.g., (a, 2 (c, (),d), e -gg fig I Se9 h denotes (a S b S d),e < f.g < h when only consider the parameter with respect to @ E [K, T} sufficiently large and omit any other parameter. Finally, Pareto-optimality is identified according to the
in Definition D as follows.
Definition 2 (Pareto-optimal and Pareto Frontier) A feasible pair (x" (²) is cluimed to be Pureto-optimal when il is not Pureto-dominate by any other feasible solution. Pareto Frontier P is denoted as the envelope fronts of all Pareto-optimal solutions.
For example, according to Definition {Ti Aieeeg is not dominated by each other in Figure For more intuitive comprehension for practitioners, we provide the closed-form mathematical formulation in the following section.
4 Pareto-optimality
In the above section, we introduce the motivation and establishment of our MAB-N and then construct the mini-max trade-off problem along with the Pareto-optimality property. In this section, we explore in detail the lower bound of such trade-off and the geometric structure of Pareto optimality. According to the Definition I 2 the individual arm space and the time horizon T. Here is included in the exposure arm space Ue. Other parameters, such as N, are seen pre-fixed constant. We first introduce the following condition to restrict the fairly broad relationship between parameters.
in the following text, our analysis upon optimality mainly focuses on
Condition 1 Exposure mapping S and clusters C should satisfy 5 Me S.
'Intuitively speaking, if we denote the region formed by F(a, F(, Á'), X-axis and Y-axis first quadrant as Region(R, A), Region(#', Á'), respectively. Then { A} Pareto-dominate {<', A') means Region(r: m, Á) Region(m'ss A').

---

Rp(T.
(.(7.
Pareto-optimal
Presto-oplime
Pareto Fronterr
Our
Raseline
Rill Flct Alt T
(4,77)
(KT))
[si ( Log. Ag)
(6//7)
rut7)
(K/T)
K
[K/T)l
X e.(T.A)
(a) Our general result under interference.
(b) The comparison with the baseline without inter- ference.
Figure I: Pareto-optimality. (a) We use three blue fronts (first quadrant) to show three different MAB algorithms { Arhess) e.g., the blue regions represent the regrets and estimation errors that can be realistically achieved in all kinds of instances given 1 Å MAB algorithm is Pareto-optimal if and only its blue front is tangent to the Pareto Frontier (red) (otherwise, it is intersecting with the grey region). (b) The green line represents the baseline in SSmmchi-Levi and Wang 2024). which loses the Pareo-optimality concerning arm space.
Condition D reetrricss to the case where T relatively large with pre-specified non-empty Ugg which is inherently verifiable, adjustable and relevant. Regardless of any pre-fixed IH, we could manually design legitimate (2) and clusters to fit Condition [ It is the weakest condition to date, without additional restriction upon network topology, compared to the previous literature mentioned in the above section. Additional justification on exposure mapping and feasibility of model conditions are in Appendix D and Appendix Under such conditions, establish general lower bound when simultaneously considering the regret and estimation eтror.
Theorem Given any S and C that satisfies Condition [ Given any online decision-making policy the trade-off between the regret and the estimation exhibits
inf max Ar MEE (VR,(T,T)e 22 (Vite))
(6)
We use the subscript {K, T to emphasize that the order just corresponds to these two parameters and omit the subscript in the following text.
The challenge of the proof. The core idea involves constructing two carefully designed multi- armed bandit instances, and such that any estimator ÅT faces challenges in simultancously achieving low regret and high estimation accuracy across both instances. This difficulty is divided into three parts: (i) Regarding the goal, unlike the regret lower bound analysis in classic multi-armed bandit problems [Lattimore and Szepesvári, 2020aa, we employ statistical hypothesis testing to bridge these two goals, rather than analyzing worst-case regret in isolation. (ii) Concerning instance construction, compared to Simchi-Levv and Wang [2024). constructing two distinct instances is challenging due to the interference affecting the entire system, making it difficult for algorithm's 's regret or estimation behavior to differ significantly. (iii) From an information-theoree the correlated structure complicates the issue. The networked nature of exposure rewards necessitates a refined divergence measure that accounts for shifts in probability mass across dependent actions, such when applying the Kullback-Leibler inequality.
perspective,
The sketch of the proof. We defer the detailed proof in Appendix H To tackle these challenges, we carefully construct a pair of instances via slighting perturbing the reward of Y(A,) compatible with specific exposure arms: we let (A) == f((A) (Eo. Ea), Eo E (0,1), E (-1,1).
It means (A) Rad( Rad(1-//d (A): 1+f((A), Moreover, We establish
(A) Rad( 1-f((A)-a 1+
AA satisfying P(4, = 5) 0.
(A) ==
(7)
A satisfying P(4, A S) 0.
2
7

---

with a > 0 sufficiently small, and S is specifically selected. Conducting the information ctormatton-thhoretic
argument, we prove
inf max IPu År MEBo
max LijeUs
A
((
2 1- V
Ru (T, x 2
Mel
Here q' is a constant. Such inequality bridges the relationship between the statistical power and regret efficiency under these two instances and thus induces the final lower bound in Theorem
Theorem [ states that for any given policy म, there always exists least one hard MAB in- stance v, in which no matter what legitimate S, C, and estimator ÅT we choose, the lower bound DC / (iME) always holds. In other words, there are always challenging instance such that eg (T, Á) = Px,r( ( (T,
We take examples considering the worst case of v: O(T), Theorem [ states that the worst estimation error is least ((((4))/TT and could not be further decreased; stepping forwards, as we will show in Section that our proposed MAB-N algorithm's regret is upper bounded by O(v ME|T), then Theorem ad- ditionally states that the worst estimation eπтоr of our algorithm will be ideally at least ([4gl/TT /T) without need further implementation. In sum, Theorem serves as a free lunch, enabling practi- tioners to perform interactive inference and prediction regarding the trade-off between the algorithm's s regret efficiency and statistical power. A natural question what is the relationship between the lower bound and the Pareto-optimality? We provide the following closed-form for Pareto Frontier following the lower bound Theorem !
according to the fact (T,
Theorem Following the condition Theorem | a feasible pair {π, Δ} is coreto-optimal if the pair satisfies maXveto (T, ()) = 0 (VVils [Mg]). The Pareto Frontier is represented as Ö ((Vuel)))
P = (()
(T,
Theorem Saareem@essabliin establishes the sufficiency condition for the Pareto-optimal property. We also analyze the necessity conditions in Appendix[] For visual representation, readers are referred to Figure I which illustrates the Parcto-optimal pairs Å (blue region) and the Pareto Frontier (red line). Theorems | are applicable to any complex network topology H under mild conditions on exposure mapping (Condition T). These results not only generalize non-trivial trade-off's under network interference but also enhance the degenerated results without interference. Specifically, when compared to the setting of SimchiiLevii and Wang 2024] (i) we advance the Pareto-optimality trade-off concerning arm space, and (ii) we eliminate their additional assumption ATE, specifically that Á @(1)
Furthermore, our reward F2 is not constrained to the interval [-1, 1], allowing for unbounded values.
Algorithm
In Section 5 introduce the Upper Confidence Bound algorithm with Two Stages under Network interference (UCB- (SN). Our UCB-TSN operates in two phases: (i) uniformly explore the exposure super space using round-robin approach to estimate the ATE within Ti rounds. and (ii) applying the UCB exploration strategy to minimize regret. The pseudo code is provided the appendix due to the space limitation. Initially, we demonstrate that phase (i) effectively reduces the estimation error, as detailed below.
Theorem 3 (ATE estimation upper bound) Following the condition in Theorem 1 If > Usl
for any S; + S, E Ug, the ATE estimation error of UCB- UCB-TSN can be upper bounded as E E (i.))
A 1 (VTMel/T))
Theorem asserts that uniform exploration in phase (i) aids in estimating the ATE. This intuitive, as UCB-TSN explores the exposure action space using a round-robin approach. Provided that the practitioner selects T, Q(T*)) for a E (0, 1), the ATE estimation consistent. Following the uniform exploration in phase (i), phase (ii) focuses on identifying the optimal arm, leading to the convergence of the overall regret.
Theorem 4 (Regret upper bound) Following the condition in Theorem
1 With 8 =1/T2 and
T > [g the regret of UCB- can be upper bounded as R(T, T) Ō Me T -Ti).
8

---

Theorem claims the regret could converge o(T), accommodating with well-selected Ti. such as 7i v [T. Theorem 4is consistent with Proposition I when we omit phase (i), i.e., 7i 0
and reserve phase (i). By the combination of Theorem we claim the Pareto-optimality as stated in Section 4 in our UCB-TSh as follows.
Corollary (Trade-off result) Following the condition in Theorem E Ev. UCB-TSB can guarantee (T, (T) = Öly (ell).
1 Set T1 2 v MTl. for all
Corollary
D states that under stricter but still mild condition upon the uniform exploration process
T1 (since [ 2 Mg| under Condition lb. UCB-TSN could achieve the Pareto-optimal property
according to Theorem []
Comparison with the baseline algorithm. To facilitate the fair comparison, consider the degenerated case as in Simchi-Levi and Wang (2024), where we choose N = 1. [2g]] = K 2 2 in our UCB-TSN. Here I. corresponds to Ug. We compare the regret in (i) and estimation in (ii). (i) For the regret, they proposed their EXP3EG which guarantees the regret upper bound as (T, = Ö(K + TI-9), where a E [o, 17 Such result is build upon their assumption N Evey (S*) - (S,)) = ((1) for all S; * S In this single-agent setting with such assumption, it should be pointed out that our regret upper bound in Theorem coull be naturally strengthened to Ö(K + Ti) (refer to our instance dependent regret upper bound in Lemma in the Appendix). Thus our regret upper bound is strictly stronger than theirs if we force Ti O(T (ii) For the estimation error, they state that ATE could be upper bounded by (T, = OK
Therefore our estimation error in Theorem 3 i.e., Ö( /4 1TT = Ō(VK/TT) is strictly stronger than theirs since it is legitimate to force Ti = T V [us] Such strict improvement (i)- is illustrated in Figure []] validates the statements under Theorem P that we achieve the Pareto optimality with respect to time period I' and additionally, the exposure super arm space (Mg].
Extension to adversarial setting
The adversarial setting. We cover Simchi-Levi and Wang [2024]ss 's adversarial setting when considering trade-offs. We consider (ra) Y((A) + ft + nr.t. where n/. is i.i.d. zero means noise. In addition to the standard setting in the preliminaries, there is an ft. a pre-specified function w.r.t. period f, which an adversarial noise. We suppose (i,((A) E [0. 1] for all i E U,
KM and t E (T). It is also easy to verify that (S) E [0, 1] for all t E [T]. S. E Ue i E U and (S) ((() fe. Motivated by the fact that the UCB algorithm discussed in the previous section cannot be applied directly in this context, we provide the advanced EXP3-TS -SN algorithm for substitution. The pseudo-code and details of the EXP3-TSN provided in the Appendix.
Theorem (Pareto-optimality trade-off in the adversarial setting) Following the condition in Theorem 7 let T(t) = (2) + 1)² (t 2)//(( Me). then (i) [ATE estimation Sup- pose T 2 (T) and T, 2 T(Ti). For any S. & S.. the ATE estimation error of the EXP3 can be upper bounded as in Theorem 3 (ū) [Regret] Stepping back, if we only suppose T T(T), then the regret of EXP3-TS3 could be upper bounded as in Theorem (ii) [Pareto- pareeto-opimmlleee optimality) Stepping forward, additionally set Ti 2 T(Ti) V ME]T. then EXP3-TS- TSN can also guarantee the Pareto -ariialoptimality trade-off. i.e., e, (T, ②) (((,,) =(V UEl).
Theorem 5 states that under additional mild conditions, i.e., T > T(T) and Ti > T(T) the regret, ATE estimation error and the pareto-Optimality trade-off could still keep their original form in Thcorem 4 In such adversarial setting, our result can also outperforms Simchh-Levi and Wang [2024] with the same argument as in Section 5] and the discussion concerning the order of the node number N aligns analogously.
In their paper, R. (T, m) = O( Kllog(T) + (o==)) Ō(KS + +T-=). Here A denotes the hest arm.
Since T(t) O(12 (og(((ee(t)), such conditions are natural to satisfy given that I' is sufficiently large.

---

7 Conclusion and future work
We establish a unified online learning framework under network interference via statistical exposure mapping, balancing learning efficiency and statistical power through Pareto-optimal trade-off between regret and estimation error. We also introduce UCB-TSN, an algorithm achieving this balance with provable guarantees. In the future, we aim to investigate the estimation-regre trade-off in fully adversarial networked bandit, and extend it to more general and complex topics such as multi-agent reinforcement learning, online learning in causal inference and bandit in large language models.
Acknowledgements
Zhiheng Zhang is supported by "the Fundamental Research Funds for the Central Universities" (number: 20251 10602) of Shanghai University of Finance and Economics.
References
Abhinect Agarwal, Anish Agarwal, Lorenzo Masoero, and Justin Whitehouse. Multi-armed bandits with network interference. arXiv preprint arXiv:2405.18621 2024.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, 2012.
Venkatachalam Anantharam, Pravin Varaiya, and Jean Walrand. Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part lid rewards. IEEE Transactions on Automatic Control, 32(1 1):688-7,, 1987.
Peter M Aronow and Cyrus Samii. Estimating average causal effects under general interference, with application to a social network experiment. The Annals of Applied Statistics, 2017.
Bruno Arpino and Alessandra Mattei. Assessing the causal effects of financial aids firms in tuscany allowing for interference. The Aunals of Applied Statistics, 2016.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256, 2002.
Oriana Bandiera, Iwan Barankay, and Imran Rasul. Social connections and incentives the workplace: Evidence from personnel data. Econometrica, 77(4):1047-1094 2009.
Pietro Belotti, Christian Kirches, Sven Leyffer, Jeff Linderoth. James Luedtke, and Ashutosh Mahajan. Mixed-integer nonlinear optimization. Acta Numerica, 22:1-131, 2013.
Lilian Besson and Emilie Kaufmann. Multi-player bandits revisited. In Algorithmic Learning Theory, pages 56-92 92. PMLR, 2018
Robert M Bond, Christopher Fariss, Jason J Jones, Adam DI Kramer, Cameron Marlow, Jaime E Settle, and James H Fowler. A 61-million-perron experiment in social influence and political mobilization. Nature, 489(7415):295-298 2012.
Giuseppe Burtini, Jason Loeppky, and Ramon Lawrence. survey of online experiment design with the stochastic multi-armed bandit. arXiv preprint arXiv:1510.00757, 2015.
Jing Cai, Alain De Janvry, and Elisabeth Sadoulet. Social networks and the decision to insure. American Economic Journal: Applied Economies, 7:81-108. 2015.
Nicolo Resa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404-144) 1422, 2012.
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.
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.
10

---

Brian Cho, Dominik Meier, Kyra Gan, and Nathan Kallus, Reward maximization for pure exploration: Minimax optimal good arm identification for nonparametric multi-armes bandits. arXiv preprint arXiv:2410. 15564, 2024.
Marco Ciotti, Massimo Ciccozzi, Alessandro Terrinoni, Wen-Can Jiang, Cheng-Bin Wang, and Sergio Bernardini. The covid-19 pandemic. Critical reviews in clinical laboratory sciences, (7()): 365-388, 2020.
Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al. Combinato- rial bandits revisited. Advances in Neural Information Processing Systems, 28, 2015.
Yash Deshpande, Adel Javanmard, and Mohammad Mehrabi. Online debiasing for adaptively collected nigh-dimensional data with applications to time series analysis. Journal of the American Statistical Association, 118(542): 123-1139, 2023.
Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Estimation considerations in contextual bandits. arXiv preprint urXiv:
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,22
Maria Dimakopoulou, Zhimei Ren, and Zhengyuan Zhou. Online multi-armed bandits with adaptive inference. Advances in Neural Information Processing Systems, 34:1939-1995 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 preprinl arXiv:2411.006 2024.
Alexander D' Amour, Peng Ding, Avi Feller, Lihua Lei, and Jasjeet Sekhon. studies with nigh-dimensional covariates. Journal of Econometrics, 221(2):444-653) 2021.
Overlap in observational
Mengsi Gao and Peng Ding. Causal inference network experiments: regression-based analysis and design-based properties. arXiv preprini vrXXv:2309.074766 2023.
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): e2014602118, 2021.
Qiyu Han, Will Wei Sun, and Yichen Zhang. Online statistical inference for matrix contextual bandit. arXiv preprint arXiv22212.11385 2022.
Jiafan He, Tianhao Wang, Yifei Min, and Quanquan Gu. simple and provably efficient algorithm for asynchronous federated contextual linear bandits. arXiv preprint vrXiv:2207.03/06 2022.
Eshcar Hillel, Zohar S. Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh, Distributed exploration in multi-armed bandits. In Advances in Neural Information Processing Systems, 2013.
Michael G Hudgens and M Elizabeth Halloran. Toward causal inference with interference. Journal of the American Statistical Association, 103(482):832 842, 2008
Guido W Imbens. Causal inference in the social sciences. Annual Review of Statistics and Its Application, 11, 2024.
Kevin G. Jamieson, Matthew Malloy, Robert D. Nowak, and Séhastien Bubeck. lil' ucb An optimal exploration algorithm for multi-armed bandits. arXiv preprint arXiv: 1312,738, 2013.
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.
Su Jia, Peter Frazier, and Nathan Kallus. Multi-armed bandits with interference. arXiv preprint arXiv:2402.01845. 2024.

---

Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Optimal regret analysis of thompson sampling in stochastic aamli bandit problem with multiple plays. In International Conference on Machine Learning, pages 1.52-1161 PMLR, 2015.
Junpei Komiyama, Junya Honda, and Akiko Takeda. Position-based multiple-play bandit problem with unknown position bias. Advances in Neural Information Processing Systems, 30, 2017.
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. Advances in Neural Information Processing Systems, 28, 2015.
Paul Lagrée, Claire Vernade, and Olivier Cappe. Multiple-play bandits in the position-based model.
Advances in Neural Information Processing Systems, 29, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. 2020a.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020b.
Michael P 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 Statistics, 50(5):3064-3000 -087, 2022b.
Michael P Leung. Network cluster-robust inference. Econometrica, 91(2):641-667, 2023.
Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized linear bandits. arXiv preprint arXiv:2202.01087, 2022.
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference machine learning, pages 1245-1253. PMLR, 2016.
Biyonka Liang and lavor Bojinov. An experimental design for anytime-vall valid causal inference on multi-armed bandits. arXiv preprint 1rXXi:2331.05750 2023.
Jonathan Louëdec, Max Chevalier, Josiane Mothe, Aurélien Garivier, and Sébastien Gerchinovitz. A multiple-play bandit algorithm applied to recommender systems. In The Twenty-Eighth Interna- fional Flairs Conference, 2015.
Alexander Luedtke and Mark Van Der Laan. Statistical inference for mean outcome under a possibly non-unique optimal treatment strategy. Annuls of statistics, 44(2):713, 2016.
Yunpu Ma and Volker Tresp. Causal inference under networked interference and intervention policy enhancement. In International Conference on Artificial Intelligence and Statistics, pages 3700-3708. PMLR, 2021.
Ka Ho Mok, Yeun-Wen Ku, and Tauchid Komara Yuda. Managing the covid-19 pandemic crisis and changing welfare regimes, 2021.
Evan Munro, Stefan Wager, and Kuang Xu. Treatment effects market equilibrium. arXiv preprint 1rXiv:2109.11647 2021.
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):566-571, 2016.
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pages 461-469. SIAM, 2014.
Donald B. Rubin. Randomization analysis of experimental data: The fisher randomization test comment. Journal of the American Statistical Association, 75:591-593, 1980.
Donald B Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American Statistical Association, 100(469):322-333 2005.
12

---

Aadirupa Saha and Aditya Gopalan. Combinatorial bandits with relative feedback. Advances in Neural Information Processing Systems, 32, 2019.
Fredrik Sävje. Causal inference with misspecified exposure mappings: separating definitions and assumptions. Biometrika, 111(1):1-15, 2024.
Jasjeet Sekhon. Opiates for the matches: Matching methods for causal inference. Anmual Review of Political Science, 12(1):487-508, 2009.
David Simchi-Levi and Chonghuan Wang. Multi-armed bandit experimental design: Online decision- making and adaptive inference. Management Science, 2024. doi: 20.1288/mmcc.223..oo
Xinyan Su, Zhiheng Zhang, and Jiyan Qiu. Unveiling environmental sensitivity of individual gains in influence maximization. arXiv e-prints, pages arXiv-2301 2301, 2023.
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 on Machine Learning, 2013.
Taishi Uchiya, Atsuyoshi Nakamura, and Mineichi Kudo. Algorithms for adversarial bandit problems with multiple plays. In International Conference on Algorithmic Learning Theory, pages 375-389. Springer, 2010.
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 #xXiv23300144883 2023.
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, 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.19211 19218, 2023a.
Zichen Wang, Chuanhao Li, Chenyu Song, Lianghui Wang, Quanquan Gu, and Huazheng Wang. Pure exploration in asynchronous federated bandits. arXiv preprint 1rXiv:2310. 1015, 2023b.
Zichen Wang, Haoyang Hong, Chuanhao Li, Haoxuan Li, Zhiheng Zhang, and Huazheng Wang. Design-based bandits under network interference: Trade-off between regret and statistical inference. arXiv preprint arXiv:2510.0766 2025.
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.
Yang Xu, Wenbin Lu, and Rui Song. Linear contextual bandits with interference. arXiv preprint arXiv:2409. 15682, 2024.
Fanny Yang, Aaditya Ramdas, Kevin G Jamieson, and Martin Wainwright. framework for multi-a (rmed)/b (andit) testing with online fdr control. Advances in Neural Information Processing Systems, 30, 2017.
Jiayu Yao, Emma Brunskill, Weiwei Pan, Susan Murphy, and Finale Velez. Power constrained bandits. In Machine Learning for Healthcare Conference, pages 209 -59. PMLR, 2021.
Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances in Neural Information Processing Systems, 33:9818-9829, 2020a.
Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical inference with m-cstimators on adaptively collected data. Advances in Neural Information Processing Systems, 34:7460-7471, 2021.
Yi Zhang and Kosuke Imai. Individualized policy evaluation and learning under clustered network interference. arXiv preprint arXiv:2311.024. 2023.
13

---

Zhiheng Zhang. The maximum intersection number of regular simplicial partitions. arXiv preprint arXiv:2210.11450, 2022.
Zhiheng Zhang. Tight partial identification causal effects with marginal distribution of unmeasured confounders. In Forty-first International Conference Machine Learning, 2024.
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, Wenbo Hu, Tian Tian, and Jun Zhu. Dynamic window-level granger causality of multi-channel time series. arXiv preprint arXiv:2006. 07788, 2020b.
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 on Research and Development in Information Retrieval, pages 2349-2353, 2023.
Zhiheng Zhang, Haoxiang Wang, Haoxuan Li, and Zhouchen Lin. Active treatment effect estimation via limited samples. In sectod International Conference Machine Learning, 2025.
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.
14

---

A Technical Appendices and Supplementary Material
Appendix
B
summarizes key symbols in the main text for reference.
Appendix provides detailed literature review for better comprehension of the background.
Appendix
and N
provide the justification for exposure mapping and model conditions.
Appendix illustrates the experiments.
Appendix further analyzes the structure of the exposure mapping and the re-scaled noise.
Appendix provides the proof the Proposition[] I
Appendix contain the proof of Theorem and Theorem respectively.
Appendix presents the proofs Theorem
Section
Appendix provides an algorithm for Non-stochastic Settings.
Appendix delivers the proof of Theorem Finally, Appendix O includes the auxiliary lemmas.
B Notations
K
Real arm set
K
Number of arms Unit set Number of units Cluster set Number of clusters Instance
N
C
Ep
Set of the legitimate instance Learning policy Cumulative regret of policy Time horizon Length of the first exploration phase Potential outcome of unit i
R(', m)
T
T
Exposure potential outcome unit Exposure mapping
SO)
Adjacency matrix Action of Exposure action unit Supper arm played Exposure super arm played Optimal exposure super arm Number of the exposure arm Exposure arm
S
A.
U.
Uc
Cluster-wise wise switchback exposure super arm set
Uo
Set exposure supper arm that can be triggered by real supper arm Legitimate exposure super
Me
(S)(S)
Reward feedback of unit round exposure super arm pulled
(())
ATE between S; and Sj ATE between S* and 5:
A
(
Estimated ATE between S; and Sy
(.(S)
Reward estimator of exposure super arm S
e, (T.))
Largest ATE. estimation error Observation number of exposure super arm S until round
N
C Literature Review
In this section, we present a literature review on network interference within the causality and bandit communities. Additionally, we discuss relevant variants of bandit problems. Finally, we provide brief summary of recent advancements in the estimation-regret trade-off within the context of MAB.
Offline causality estimation under network interference. In the current causality literature, interference is well-known concept. It is violation of the conventional "SUTVA" setting, repre-
15

---

Interferece-baed MAB
Exposure mapping (S E))
Action space (ee))
Clusters (C)
Estimation goal (A4.))
Simeh-LLevi and Wang 2024
K
Y(A.) Y(A))
di al A121
Ae
+
Veli 1s] -o6 1x))
Agarwal et
Ae;
N
$ Leau (8.18) Es().))
KAB-Ni (Ours)
General Sti. A.)
00499
Table I: MAB-N N surrogates the previous bandit under interference as special cases. Here A;, Aj E KM, and S; S3 E Ue. We omit the subscript in Simchi-Levi and Wang [2024] since it only considers sole individual.
senting that one individual's 's treatment would potentially affect another individual's outcome, which relevant in practice. Current literature resort clustering ZZhng and Imai [2023. Viviano et al. [2033] or exposure mapping (eappiggLeungg 2022a b 2023
Bandit under network interference. Previous attempts are being made to consider the multi-armed bandit problem upon network interference. AAgawal et al. [2244] conduct the Fourier analysis to transform the traditional stochastic multi-armed bandit into sparse linear bandit. However, in order to reduce the exponential action space, they made a strong assumption of sparsity for network structures, i.e., the number of neighbors of each node is manually upper limited. On the other hand, Jia jet al. (2024) analyzes the action space at the other extreme that considers an adversarial bandit setting and thus forces each node to a simultaneous equal arm. It does not consider that the optimal arm could differ for each node or subgroup. Moreover, Xu et al. (2024] further considers the contextual setting under the specific linear structure between the potential outcome and the interference intensity.
Trade-off between inference (estimation) and regret. A significant body of research has been dedicated to developing statistical methods for inference in MABs. Numerous studies focus on deriving statistical tests central limit theorems for MABs while ensuring that the bandit algorithm
remains largely unaltered [Hadad et al. [001 Luedtke and Van Der Laan 2016 Deshpande et al.,
2023 Zhang et al. 2020a 2021 Han al. 2022 Dimakopoulou et al. 2017| 2019 [2021]. thereby
facilitating aggressive regret minimization. However, these works all rely on the SUTV assumption
and fail to account for potential interference between units.
Previous literature upon adaptive inference in multi-armed bandits include Dimakopoulou et al. [2021]. [iang and Bojinov] [2023) whereas without strict trade-off analysis. To our best knowledge. the only state-of-the-arr trade-off result primarily constructed by /Sijccii--Le and Wang 2024] whereas also be cursed by the SUTVA assumption without a network connection. Moreover, Duan cct al. [2024] argue that such Parcto-optimality could be further improved, i.c., the regret and estimation error could simultancously achieve their optimality, if additionally assuming the "covariate diversity" of each node without network interference. Stepping forward, when we shift our attention to the network setting, Jia et al. (2024) is also intuitively aware of the potential "incompatibility"" of decision- making and statistical inference: specifically, Jia et al. (2024) emphasizes that the truncated HT estimator directly into the policy learning system is no longer robust because policy learning gives different propensity probabilities to different arms, making the propensity score more extreme.
Relevant bandit variants: multiple-play bandits, multi-agent bandits, combinatorial bandits, and
bandits. In bandit literature, the problem where a bandit algorithm plays multiple arms in each time period has been a subject of study for a long time. Our work is related to the multi-play bandil problem, where the algorithm selects multiple arms in each round and observes their corresponding reward feedback [Anantharam et al.) 1987 UChhya et al. 20100 Komiyama et al.
2015 2017 Louëdec et al. [2015] Lagrée et al. [2016] | Zhou and Tomlin 2018 Besson and Kaufmann 2018 Jia et al. [023 Wang et al., 2023b]. Additionally, this is related to the multi-agen bandit problem (including distributed and federated bandits), where multiple agents each pull an arm in every time period. By exchanging observation histories through communication, these agents can collaboratively accelerate the learning process. (Hillel et al.) [013]] | Szörényi et al., [2013] Wu et al.) 2016 Wang et al. 2019 Li and Wang 2022 He et al., 2022, Wang et al., 2023b]. Furthermore, our work is also connected to the combinatorial bandit problem. where the action set consists of a subset of the vertices of a binary hypercube (Cesa-Biancd) and Lugosi| 2012 Chen et al.) 2013 2014
Combes et al.] 2015 Qin et al. 20044] K Kveton et al., 2015) 5 Li et al. 2016 Saha and Gopalan 2019
Wang et al. 2023a Some of these works account for interference between units, but they typically
16

---

Estimation (ofline)
Regret (online)
Trade-off between Regie
Auer et al. 2002
Simchi-Lvi and Wang 2024
Without interference
SUTVA causality
Burtini et al
2013
Duan et al. 2024
Leung 2022a
2023
Agarwal el al.
2024
With interference
[udgens and Halloran 2008
ela al. A024
Our paper
Sayge
et
Table 2: Most related and representative works in causality estimation and regret analysis with
(without) network interference.
assume that the interference is either explicitly known to the learning algorithm, or the interference follows a specific pattem. In contrast, our setting makes no such assumptions about the nature or structure of interference between units. Our paper also closely related to the field of multitasking bandits, where the learning algorithm is designed to achieve multiple objectives simultaneously during the learning process. YYang et al. [2017] explore the regulation of the false discovery rate while identifying the best arm. Yao et al. [202T] focus on ensuring the ability to detect whether an intervention has an effect, while also leveraging contextual bandits to tailor consumer actions. Jamieson et al. [013)] Cho et al. [2024) aim to minimize cumulative regret while identifying the best arm with minimal sample complexity.
D Justification, discussion and future work
Justification exposure mapping. It is well-known concept in causality. From statistical perspective, it serves as a functional tool for mapping a high-dimensional action space to a low- dimensional manifold; from machine learning standpoint, it can be interpreted as specialized input representation layer. However, its utility has not been fully explored in interference- based bandit referred to as exposure mapping
online learning settings like Bandits. Interference-best has recently been explored in Jia et al. [2024] to our knowledge. This additionally assumes the intensity of interference decays with distance. Still, the -ww-dimesiooall vectors from their exposure mapping are not involved in the computation of the target regret. In contrast, their regret, directly uses the adversarial setting that "the original super arm must be vector of the form a * 1 E K", which is limited in realistic compared to our settings, e.g. when the optimal arm takes place when the individuals in the network are assigned to different treatments; to tackle this problem, although Agarwal et al. (2024) can identify the best arm beyond a 1 ,a E K., their approach relies on a stronger assumption: the rewards of each node are influenced solely by its limited first-order neighbors, and the number of these neighbors is significantly smaller than N. In sum, our paper first presents an integration of exposure mapping with bandit regret frameworks and demonstrates its generality and applicability.
Justification on Condition [ Condition D states that Ug > 2 is not empty. It is already weaker than the previous interference- based bandit setting [Jia et al.) 2024 Agarwal al., [024] whereas it could be further relaxed. We consider the generalized metric to describe the distance between Mo and S, E Ue: D(Mo St) == ming'e4o || S11l1 via Manhattan distance. When the number of clusters grows, the action space [Mel exponentially expands and their compatibility D(Ue, Mo) also decreases. These previous literature and Condition I all satisfy D(Me, Mo)
and the former literature together with additional network structure [Agrwall and Goyal, 2012) or interference intensity [Jia et al., 2024 assumption as above. In Appendix N we claim that under the weakened assumption D(Me, Mo) < where < > 0 is a prior constant, our model remains capable of reasonable modeling by appropriately adjusting the definition of exposure- prpssure-based rewards accordingly. The interplay between this assumption and other well-known assumptions, such the neighbor sparsity assumption Agarwal et al. [2024], , the decaying interference assumption Jia et al. (2024). and the approximate interference assumption CouuptionnLLungg 2022aa] is left as avenue for future work.
Moreover, natural next step is to deepen the theoretical and methodological connections between networked bandit design (Wang et al., 2025) and causal inference. In particular, our analysis of Pareto-optimal trade-offss provides foundation for extending the notion of learnability adaptive designs toward formal identifiability in causal models. Future research may incorporate the theory of partial identification [Zhang and Su 2024 /Zhang 2024) to characterize the minimal information required for interference-awee aware effect estimation, thereby turning online exploration into a process of
17

---

progressively tightening causal bounds. Another promising direction is to embed robust and proxy- based causal adjustments [Zhang et al. 2023] into the online decision loop, allowing adaptive designs to remain valid in the presence of latent or noisy confounders. Extending our results to dynamic and time-varying network structures would further connect to recent advances in dynamic Granger-type causal analysis [Zhang et al. 2020b]. while bridging to active treatment-effect estimation with limited sampling budgets [Zhang et al. 2025]. Finally, structural and geometric constraints arising from network topology combinatorial design feasibility (Su et al. 2023 Zhang 2022] suggest that future online experiments could jointly optimize over both exploration reggett trade-offs and the attainable identification sets of causal effects, forming unified theory of inference aware sequential design under complex interference.
18

---

C.
(2.....11
101
(22
Co
C4
(62....811
(42....61)
Figure Network structure.
Cumulaative Regre
660
Uniform
#Outllers
Max ATF Diforence
Standard
0.3
400
UCB_TS0
10 outtlers
0.2
40 outliers
0.1
0.0
2000
4000
6000 8000 10000
Uniform
Standard Method
UCB_TSN
Time
(a) Cumulative regret
(b) ATE estimation error
Figure 3: Experimental results.
E Experiments
Setup. We consider network consisting of 101 units. Specifically, there is central cluster
C = {1} that contains single unit, which is connected to every unit in the five peripheral
clusters C2,,. .2...., C.
(namely, C2 {2, .2,...,2 21}, C3 = {22.- ... ,1), C4 {42, ... 61], Cs (62, (62....,811) and C. = [82...., 101). with each outer cluster containing 20 units, as shown in Fig.
2). We set the action set K. (0, 1). Inspired by [Leung] 2022a Gao and Ding. 2023 we define
the exposure mapping S(i, A. H) 1{ 2, hisay E [o which explores the influence of the
Σ, has
proportion of neighbors taking action on each unit; this exposure mapping implies that d, 2. For every S Ug, we define P(Ar arm corresponding to an exposure S, the reward is sampled from Bernoulli distribution.
S) as uniform sampling. Moreover, for each selected super
We evaluate the performance of UCB-TSW (T₃ = V 7) against two baseline methods: Standard (i.e., UCB-TSN with Ti 0) and Uniform (i.e., UCB-TSN with Ti = T). Each algorithm is executed 1000 times, and we report the averaged results.
Results. The simulation results are shown in Fig. ((a) and Fig. 3(b) As seen in Fig. ((a) both the Standard method and UCB-TSN achieve the lowest cumulative regret, while Uniform exhibits the highest cumulative regret. Fig. 3(b) presents a box plot of the maximum ATE estimation error, (,, Å), where the green line represents the median. The results indicate that UCB-TSM and Uniform yield lower ATE estimation errors with compact interquartile ranges and few outliers, whereas the Standard method shows wider spread of errors and multiple outliers. This relatively poorer performance of the Standard method in statistical estimation is due to its lower frequency of exploring sub-optimal arms compared Uniform and UCB-TSN. Our code is available at: hhtpps //github. com/ SrrchangO1/NeurIPS000 -ateeas--niiii----eeeeeee
The Discussion of Exposure Mapping and Noise Rescaling
We denote the policy and exposure reward inheriting from Leung 2022a as Preung and V Vit (-), respectively. Considering Eq (3), we take the exposure mapping function's output d, cardinality without loss of generality. We choose P(A, A S.)) : Po (A, A SSe,) then VS,e,
19

---

Yi,Leun((s) (s) EASK" Loongg (A, A (AY; LAEKU P(A. = A (A) = Y.(S)).
Hence our exposure- based reward notation is generalized from Leung 2022a]
Moreover, we discuss the re-scaling of noise. When AS E Ue 1(4 (S(i, A, Hi) hieu = -51= =01=1 1, it naturally leads to the variance proxy o² Hence, we mainly consider other cases, Notice that Eq (3 defines
of the Sub-Gaussiaa variables Eieu (i,
(S(S)), (S.)
Σ (a A| St).
AEKI
namely, for each St, practitioners select random legitimate (A,) to approximate (St), each with probability IPAA; = A S.). The randomness includes the sub-Gaussian noise and sampling noise. It follows that for all m E R.
m
Fra(S,) {((51)) A. A
E
exp
N
iEUl
(ra((A) - Y((A) + Y((A) (((A))-((S)))
E
cxp
N
iENl
(8)
(Y((A)- -)((s))()) | exp
(T,e(A) - x2(44))
cxx
N
SEM
m
(Y((A)- - exp
m²
Sexp
N
2N
VEW
Taking expectation upon both sides of Eq
8 it leads to
m
(S.) - v((si))
A A 11
m
m
(((A)-V((s))
exp
- exp
exp
N
2N
N EEW
iEW
(9)
According to the boundary 1/ EiEu((((A) Vi(Si) [-,,, 1]. it natural derive
m
((((A))((S())) < cosh(m/2) S cxp(m2/88
E
exp
N
Then Eq 99) achieves that
exp
m
exp(m2/88) exp
mm²
1 + )
(10)
2N
Therefore the Sub-Gaussian variables Σisu fr, (S)/N could achieve the variance proxy at most 1/N 1/4. In the following part, we set the variance proxy as o² without loss of generality.
Comment on the order of node number N. For a supplement, in Theorem/Corollary 3 we
additionally consider the order of node number N. (i) In Theorem we emphasize that Y Uz IA:::. {S(i, A, He = S'H = 1, namely, there is only one legitimate A which is compatible with each exposure arm S', then Theorem 3 could be strengthened as E[
O(VMee//TNN) Take the cluster-wise switchback experiment (S(i, A, IHI) = ai,)) for instance, which is the generalized case of Jia et al. [2024). In this case, since [M/ KCC & N via manually selecting d, C, then we can claim the estimation is consistent when + + Moreover, in the setting of Agarwal et al.] [2024). it is equivalent to the case C' = N and thus the result in Theorem is transformed 0 KN /TNN/TTN.... It serves as a supplement of Proposition claiming that not only
"Essentially, it is due to the re-scaling of noise. Under the one-to-one mapping in this paragraph, the result is intuitive since Σteu (S)(()) exhibits a re-scaled Sub-Gaussian noise with variance proxy 1/N. It degenerates to the offline setting when N + +00. Otherwise, we could only ensure Σ Eeu (S))NN is
Sub- Gabssia noise with variance proxy (1/N 1/4). We defer the details Appendix
20

---

the regret but also the estimation error is hard to control without exposure mapping. (ii) Analogously, in Theorem 4 the result is transformed to (T, m) = ( Ti) under the above one-to- one mapping. (iii) Finally, in Corollary the trade-off transferred be ((v/4e when slightly modify the condition of T1 as T1 2 /M4g T/N v [Me.. This result is also aligned with the proof of Theorem [
(T//
G Proof of Proposition 1
Proof (Proof of Proposition[] 1) We here define K3 := {AA]k= as the set of the super arm. Define
a MAB instance V1 Eg that (2(A) (1 = A J for all U and A E K",, where E [0. 1/2] will be defined later. We suppose that the noise of all unit follows NN, 1) Gaussian distribution. and therefore the normalized noise of the super arm (1/N) Eieu as. follows a 10,1 Gaussian distribution. Hence, we have 1/N Eieu Y:(A1) = A and 1/N Eieu Y:(As) = for all k [/1). This implies in v1, A1 = A is the best arm with potential outcome and A + A is the sub-optimal arm with potential outcome O. Due
KN
Ru (T, ( 2=2
(11)
where == 1(A, denotes the reward gap between super arm A and Ak (i.e., DR (L/N) Y((A)) Y, (A))))
} denotes the number that supper arm A is trigger till T and Ak
Suppose the super arm Aj. j = arg minje(KMM/() Be WW,,), then
E. WN, S KN-1
(12)
Besides, define another (0,11) Gaussian MAB instance V2 Eg, where Y!(A) = Y;(A) A = Aj} for all E U and A E KM, In v2, Aj is the best arm with potential outcome 2A.
Based on the decomposition of the regret Eq (II, we have
AT
AT
Rv (T, Pu, Pu (NZ, <
2 and Ruy (T,x) P 12 (VT, 2 T/2)
(13)
2
Let P and TP Pr denote the probability measures on the canonical bandit model induced by the T-round interaction between and vA, and N and v2, respectively. Finally, we have
Rv, (T, T. + Rys (T,
P P (NI, 2 T/2) + P.z. (NT, < <T/2)) AT
AT
2exp
KL(P P Pon,
- B WT KL (N (/N), (NO., 1/A1) AT 4
(14)
2exp
AT
2exp
E W,,, 12N
4
2T AT
Zexp
KN-1 4
where KL denotes the KL divergence, the second inequality is owing to the Bretagnolle-Huber inequality, the third inequality is due to the Lemma 15.1 in Lattimore and Szepesvári (2020b), the fourth inequality is due the definition of the noise distribution (i.e., (0, \) of the super arm.
Finally, select A
KN
based on the above result, we have (i = 1 or 2)
TTN
27
c
T
when T S KN
S/N:
Rv, (T
(15)
(KN 1)T when T 2 KN
21

---

H Proof of Theorem
Proof 2 (Proof of Theorem 1 In this section, simplify the notations in Section G we abbreviate Fvs as Fy and v as Ey. We consider two kinds of instances for a fixed policy т and a fixed strategy
constructing ATE estimator år. For the first one (i.e., 11), denote it as ii (A) fa (A)+ Here we let (((A) := f:(A) E [0, (0.1).ra,4A) E (-1.1). It means Ti, = Rad( ((()) (A) For each feasible cluster-wise exposure super arm S E Ugg recall that
2
2
Y((5) Σ (AAP(AA A
(16)
AEKU
The difference of expected reward of S' could be represented by A1(S,5) = (E(()) (()))), which is
AI(S
1 N
E E iEM AEKS
(((A)(((A, = -1S) - = A15)).
(17)
Without loss of generality, we select the feasible super arm to set (S, 0. For brevity, we omit the expression of the parentheses in the following text. Namely, we choose S' as the best arm, and as a sub-optimal arm in Ug. We choose = arg mins, S.1. A (S,,, S' W In (123,))121
this process, we use Á instance U2 and hope get different ATE value. We define it (A). We establish:
J121, Å == ( EMee We then construct a new MAB
(ra((A) |Rad( (-f((A4
AA satisfying P(A, A S) 0.
rA,(A):=
(18)
1+R(A)-0 2
AA satisfying P(A. = A| > O.
2
Here a > 0 should be chosen sufficiently small. Remind that following Eq 17 the ATE between super arm S' is
A 2
222, where
1 Σ
2 =
Σ (f((A) aP) = A S) - A (P)A = A | > 0),
N
BEL ACK
2 N E
1
Σ
- A ())) -A A|S)=00 0).
N
BELL AEK
Hence, it implies that the ATES in these two MAB instances, respectively, contain a difference
A A
Σ Σ
(P(A = S - P(A, = -
N
IEV AEAS
Σ
aP(A, = ()) = =|S)> >)>0)
(19)
iEll AEXS
Σ
Σ
-aP(A, = A) - <0
N
EEW AEXU
Naturally, our setting leads to 0 > A 2 The second equality is because (PA, A ()) A S') = 0 when + S'. In this sense, we consider given estimate strategy, which is summarized by (Av) Jeete- We define a minimum test v/( Ae) = arg min; (1.23 I - Arl. Naturally, it implies that &5 ((,) # fisE (1,2) is a sufficient condition of Å. Ail 9. As a consequence,
inf max P. (I A inf max P.M.
A -A 2
A. MEE
2
A. tE(1.2)
inf max P.r
((A)) +1)
(20)
A. (E(1,2)
inf max Pr, (v i).
w (E(1,2)
22

---

Here, the probability space is constructed on the exposure arm (S(i, A, H)h in each time period t. and the observed exposure reward. We use the technique in min-max bound. Notice that the original feasible region of MAB instances as En: we gel
RHS of 20
(P ms (v 2) Puz 1))
TV(P,,
(21)
1
- Pur)
22
We aim to provide an upper bound of KL divergence KL(P vs Pu.), inspired by the divergence decomposition:
dlFu, m1 cIP V
KL Pv.
Ev
log
(22)
For any instance {V1, V23. the density function of the series denoted as (we denote X₃ as the observed exposure reward (S)
Po (Si, 15,,,,,,,,.... Xt) = II
me (Se
(X+).
(23)
f'=1
Here Fv,s(-) denotes the reward density distribution conditioning on arm S in v. Hence Eq 22 can be transformed as
Pu (Xer)
KL(P v1 Piz)
Σ
Egg
log
Pusise (Xxz)
C'E(
P Pu.. (Xer) Pur,Su (X²)) |Sv)
Σ
Euy
Eeg log
(24)
r'E(t]
Σ Enn [KL (.), Pe..s (-))
d'
=Ev, (P), s())s
The last equation is derived from the construction in Eq 18 ())
We aim compute
P (X) (X))(X)
KL(P,,,()),P,,.s)
(X
dX S gNa2.
(25)
Here is constant via second-order Taylor expansion. As consequence, it implies that
Ry, (t,
KL(P Puz) S SyNa (W3] S Na
(26)
1 A
The last inequality is due to S = arg migss Elde EMfe (S S' S'y [N3.]- Combined with
Eq
20
26
inf max v å. WEED
max
(
(1:5
2 2
V
Ru (t, g2aa2
(27)
2
UU5 A1
On this basis, we derive the final trade-off as follows:
inf max E, A, MEED
max (JEE
(A(
((6))-199 A(--01
inf max P.
max LJEM
A (it)
A |6-0
0
(28)
2 A, vECO
a
Ry, (t, T
1 - 1-ay/
a/
2 2
4
Me
A
23

---

As a consequence, when t = T,
(64 - - (Rr(I
inf max By
max i.jEld
Ar MEEU
(29)
Run T))
1
ga2N
Ry, (T,
4
2
Me ||
Due to the sqrt-term spans [0, too] with [0, 1), hence we could set qo? N Ruy (7,z)
[uelAA 2' then,
when T 2 [Mg]. it leads to
HEll
Uel
29
DI,N.K N
(30)
2Nqa²
Theorem Dlloo follows. Q.E.D.
I Proof of Theorem 2
Proof (Proof of Theorem 2 We prove such sufficiency via contradiction. On the one hand, suppose that the MAB pair (πt, Å} satisfies maxveto (e) is not Pareto-optimal, it is equivalent to claim that there is another pair { to dom- inate Å}. In this sense, according to Theorem | there exists an instance v' such that R (T) - Moreover, according the definition of Pareto-dominance, there further exists another instance v", such that V0 E {K,T), Mel ts V (I, T) (T, A). It is contradiction.
Ö(VV/El))
Remark On the other hand, we additionally consider the proof of necessity part, also by contradic- tion. It is rigorous refinement of Theorem.5 in Simchi-Levi and Wang) (2024) with the extension the network interference case. We additionally condition that R. (T, π and (T, Å) could both be lower bounded by polynomial form T, T, i.e., the Pareto-dominanc is only considered in the region of Viower == {v R2 (T, тH = (211",, ev (T, Â) 22( ([VMMe]T' [ where > 0, 3 < 0 are constants. Recalling our goal is prove any Pareto-optinat pair {T,, Å} satisfies
(VR
= -
max DE VEViower
Suppose that for Pareto-optimal pair, there exist hard instances v² E Vhard Viront O Viower C Eo such that (here Vfrant = {u= (R. x), (T, (T,A)) E F(T, Å)}::
VV Viands Ru. (T, (T-- (T, C CyTuel, when T is sufficiently large.
Here, C is a constant. According to our condition, it induces that Ry >T 2,220, (T, Á) >r C2 where C1, C2 2 D,, = C, a1 + 02 > 0,02 S 0, E [0, 1/2] since the regret is bounded as O(T). It indicates that 0: 11/2. On this basis, we could construct feasible pair (Talgs Å via selecting suitable T T in Algorithm to satisfy (T, A) 2T (T, A 10 According to Theorem it follows that the pair {Talg: D would
Pareto-dominate the original Å). Contradiction.
J Algorithm UCB-Two Stage-Network
The UCB-TSN algorithm operates in two phases: an initial round-robin exploration phase over all exposure super arms to obtain empirical estimates of their rewards, followed by UCB-based selection phase where, at each time step, the super arm with the highest upper confidence bound chosen for sampling.
Heer ~ is the combination of and x.
24

---

Algorithm UCB-Two Stage-Network (UCB-TSN)
Input: arm set A, time {T unit number N, exposure super arm Ug, estimator (R)(S) = SeMe (No SEMe. {UCBo,s 0) sEMe counter
for 1. : do
Select exposure super arm S, = Ss and implement Sampling(S5) Set k + 1 < Mg). else set = end for
For all S, 5- Ugg St + 5j. output A (G.)) Rr, (S.) - Ry; (S,) do Select St arg maxseue UCB and implement Sampling(S),
for t Ti
end for
Parameter 1: WV3 Eir=1 (S =
= Parameter 2: R₂(S) = (S)- - Eieu Lieu (s)(s))
Parameter 3: UCBr,5 RR( + /18log(1/0)//N3
Algorithm 2 Sampling
Input: S;
Derive the set [2r hreg such that (S(i, Zr, Hel = Sr, VI' E [l]; sample A, from set (Zv heM based on P(A,, A S.), pull A,, and observe reward {fr, (S.) Tr,((,))ee
K Proof of Theorems in Section 5
K.1 Proof of Theorem
Proof 4 (Proof of Theorem Based on the design of the Algorithm 7 in the first phase, we have T for all S Ug. Define the good event Er, Rr. (S) N/2 Exeu Y((S) s
N
4 log Aloo (TVVENN/// AS E Ug and its complement Eq.- Based the previous discussion. the sub- Gaussian proxy of any exposure super arm's 's reward distribution is at most 2, then based on the Hoffeding inequality (Lemma 4), we have for exposure super arm S E Ue:
P
R&(S)
Σ Yi(S)
Se
(31)
N
BEll
substituting t Ti and a
1log(T: (Mel) NO
into Eg
31 and we can derive
1
4 log (T, (EEl)
1
RT, (S)
Σ {1(())
S
(32)
N
No.
Ti uEl
Utilize the union bound, there
(((B)(()) RT)(S)
4log (Ti (2sl)
Σ P
Σ {1(8>>
N
SElle
Σ Ti
(33)
SEll
1
T1
25

---

1. and ((ET)) 2 1- - T.. Therefore, for all St, Sn E Ug we have:
E E (1.) - -
<TP(ET,) jR
| - -//0111 118,: + P((E) )R | - - En
<T((T,) )R
(s((S)
1
Σ
(5.) + RR((S)
N Σ (o((s))
ET,
+ Ti
1
N
NEN
KEW
(34)
4 log (Th (Mel)
1
22
T1
=0
UE Ti
where the second inequality is owing to the triangle inequality and A (6-)) and Å (..))
E [0, 1], and the
last inequality is owing N
T
Here we finish the proof of Theorem
Mell
K.2 Proof of Theorem
In this section, we will first provide an instance-dependent regret upper bound (in the following Lemma DT and then, we will provide an instance-independen regret upper bound based on the instance- dependen one.
Lemma (Instance-dependent regret) Given any instance that satisfies Condition 1. The regret of the UCB- TSN can be upper bounded as follows
log (T)
R(T, π) =0
A +
(35)
Proof 5 (Proof of Lemma I Define N Ev= 1(S = S). Besides, define the good event for St as:
&
( Σ (s() UCB,,S WE [ 1, n Ry..s. +V N
}
18 18log (1)
S
1
Σ (o()
T₁
N
vell
Pell
where T, = (1 and we utilize Riy.s, to represent R((Ss) when No. = =Ty Based on Lemma (4
2 have P(EE) 2 1 Ti + 1)6 and its complement has IPE)) I (T - Ti + 1)ō.
We can decompose and bound the regret as
T
R(T,T)
Σ
Y.(S*)
E,
Σ
Σ
Fea(S.)
N
IEW
KE|T
SELL
Σ
AE s.
+1T)
Ti ΣA
Ue
S,4S' 500
S:SS-
regret in second phuse
regret in forst phose
Σ
A E
E.] + A'E NN
(TT+)
| [35
+
+
A'
UE
S 5000
S
Σ
A
N (1++)
[&]]
+ 728 +
Ti
Σ A
us SiSS
SIPS',A'5
(36)
26

---

Besides, want to show that under the event E, we have N ((T++122)
S To 15 T, then
this inequality trivially holds. If Ti < T, suppose N N > Th then, there exists time E [Ti + 1, T, such that St. = S. (Sc is pulled in round 1i), and (I =T:
-T+11 1-+1. 1. Based on the | we have UC,,,-1,S 2 UC,,, However, based on the
S.
exploration strategy in Algorithm definition of the event & we have
UCB
2
1
Σ Yr((S)
N
KEM
181g((100)
> AT.S +
Ti
18 (1/())))
= ( +
.N..
= UCB
which contradicts the previous assumption. Therefore, under the event & we have NI. I Th- Substituting this result and = 1/T² into Eq
36.. we have
R) I
Σ
E
N
(1++) S.
E,
+
+8+
Ti Σ A Us
S.tS* A
S,YS*
Ti
Σ
A'T, + +1+
Σ 8,48*
A
UE
S A
144 (T)
T
(37)
+1+
Σ
A
A
U
8 A150
S:zS
log (T)
T
=0
+
A'
Us
S A450
S.45*
Here we finsh the proof of Lemma !
The proof of Lemma]
1 relies on the following Lemma
2
Lemma We have PP(E)) 2 1 - - + 135 for all S; satisfies S F S" and A > O.
Proof 6 (Proof of Lemma 2 Define the complement of & as
3 - Σ (r(')> UCB, 31 E (1 +7+ U Rer.ss +1
18log (1)
Σ (o()
N
Te
N
veu
N'E
Based on the union bound, we huve
EYe(s)) Yx(S*) > UCB.,s", 3t [Ti 1, T7 |)
P(E)) <P
(N
N
Yeul
+ sP. (f Rer.ss +
18log (+t
Σ (3((5m)
2 N
Te
Nell
(38)
(SM) 2 UCB })
< Σ
Σ
(=T++1
Neu
+P (f (Rnist
18log (+)
Σ Ers(sr)) })
+V
2 N
T
well
27

---

Based on Hoeffding' 's inequality, we can bound the first term in Eq 38 by:
T
S(T )
Σ
P
(.())
(CBIs))UBBBSS))
UCB
(39)
T=
PEM
Besides, we can bound the second term in Eq
38) by:
18 18log (3)
1 Σ
{
P
RT..S.
+
z
N
e'ul
18 log (1)
=P
ST
(S,) 2 A
N
T
Y'Ell
(40)
2 )0/1
RT.
1
Σ
(s.)
N
expp
16
<8,
where the first and last inequality is owing to the definition Ts. and the second inequality is owing
Hoeffding's inequality. Based Eq (39) and Eq (40), we have P( 2 - (T - T1 1)8 for all
St satisfies S; + 5* and A > 0. Here we finish the proof of Lemma 2
Now we can prove Theorem
Proof 7 (Proof of Theorem In the Proof of Lemma we shows that for all S + S", A > 0,
we have
E [ <
144
+1.
(41)
(A')
Define A -6
Ue log(T)
we can decompose the regret as
R(T,T) S
A'E,
(.T)
Σ
A'E
Ws.
Ti
Σ A
9:
Us
AicA
B*#S*,Ai24
S.PS-
144)
Ti
TA+ +
+
A'
Σ
A
A'
Us
S
14 log(T)
Ti
<AA +
(1
Σ
A
A
UE
S:z5
s 30v u ITg(T)
(1
Ti
A
Us
=ō -V(VIOTTT
Ti
A
UE
S.
(42)
Here we finish the proof of Theorem
L Algorithm for Adversarial Setting in Simchi-Levi and Wang [0224)
This section introduces our algorithm, EXP3-TSH, TSN, which operates in two distinct phases. In the first phase, the algorithm uniformly samples exposure super arms from the set leg. Upon receiving reward feedback, it leverages this data to build unbiased inverse probability weighting (IPW) estimators to estimate the potential outcomes for the super arms. In the second phase, the algorithm applies the EXP3 strategy to minimize regret effectively.
28

---

Algorithm 3 EXP3-TWo Stage Network (EXP3-TSN)
Input: arm set A, unit number N, exposure super arm set Me estimator set {Ro(S) - seMe
active super exposure arm set Ao = Ug. T1, (e 2)((1 + 2|Me|)e log(2/6), 10/))//))))))))) v
[[
Me
for 1: Ti do
YS E Ug (S) - Mel and sample S based on π
Sample S, based on Tr, implement Sampling(())
end for
Output Á +,, RT, (S:) +, RT, (5₂) for any Sr E Ug St + Sj
VS Ue set Ry, =5)=0
for 1 = T + 1: do
exp(eRe-1(9))
VS E Ug: (S) Eses,
Sample S, based on Te. implement Sampling(S))
S Mg: set Rs(S)) = Pi-1 (S) + ={8,=) & Eieu Fr.(8))
(S())
end for
Unbiased estimators for exposure mapping We construct unbiased inverse probability weighting (IPW) estimators to estimate the potential outcome of each exposure super arm, i.c.,
R.(S) ( +1 1(S S} N/4 Eveu Fr.(S))
(43)
(S(
It is easy to verify that for all S E Ug for all i [1,T]:
E
1(S, = 51 N Eieu Pr,((S)
H4-1
1 N
Σ Yi(S) ft. NEW
(44)
Te (S)
Using our unbiased estimator (S). we can accurately estimate the ATE (which is demonstrated in Theorem 6). We define the martingale sequence (LM((-2) )s, where M( RG (s.))
(s,) A (R.5), and it is easy to verify that EE' [M,
(f.)) H4-1]] O.
M Proof of Theorem 5
Theorem could be equivalently separated as the following Theorem 6 and Theorem
M.1 Proof of Theorem 6
Theorem (Bounding the ATE estimation) Given any instance that satisfy 2 T(T) and [Mg]] 2
2. Set T > Ti 2 T(Ti). For any S, + S,, the ATE estimation error of the EXP3-T5 TS can be upper
bounded as follows: E B( a | = =0
[e
T1
Proof (Proof of Theorem The proof of this lemma is based on the Bernstein Inequality. To
utilize it, we first need to upper bound [M(5) (55) -M(()) M(6.3) Vt E [Ti). It can be expressed as:
M M M(110)
1[S, S1)
EreN 8r (S.)
11S, S,1(1 $/4 Ereu ((,( me (T()))
A A(-)
(S()))
1
+
+
Te. (S.)
(S,)
-2/Mee +1,
29

---

where the first inequality is owing to the P(a(-) E [0, and A E [-,,,], and the second equality due to the definition of (S) in the first phase. We also need upper bound the variance of the martingale in the first phase, denoted as ((i)), i.e, v(l-5)
11S: -.)(1 NV Ereu Fr. (()) 11S, Sj\(1 N/4 (Si)
) 2
Σ rE[TL]
E
a 1(b5))
He-1
Te (S₂)
$ Σ
1
1
(e()))
T((S))
(E[T:]
<2T [Mae-
(2) +1) 12g [R4x (*)
Based on this fact that Tj
we have
2(e-2) MEl
log(22 [ug 12)
1
S
2(e [T
2 +1'
which implies we can utilize the Bernstein Inequality (Lemma 5). have: Vt [Ti,, with probability least Ti/4e] there is
By the Bernstein inequality, we
S 2 |
2) TT log ME
Dividing both sides by Tı, based on the definition of the martingale M((d)) and the ATE estimator A (63)), we have:
4(c - (2)-2) ( log (2T, (Mee))
A -((5)) S 22
(45)
Ti
Define the good event Er, |A 11101 2 applying the union bound, it is easy to know that
4(e 2)- Ue (2g [tde))
AS, # S3
}. By
Ti
P( 2 Ti
(46)
Based the above result, for any S₁ F Sj. we have
2/1 - A <P(En, E | ال-+01
1 ET.
+ +PG JE
(6,0) A6-1 oq
4(c 2) Us log (2T, (eel
1
+
Ti
T:
-0(1
[EE
Ti
(47)
Here we finish the proof of Theorem 6
Theorem (Regret upper bound) Given any instance that satisfy T T(T) and (egl 2. The regret of EXP3-TS can be upper bounded by R(T,T) = ( (T ( +T)).
M.2 Proof of Theorem 7
Proof 9 (Proof of Theorem 7 Define R(t,j) = N/ Eveu (Tr)))) as the potential outcome
of exposure super arm Sy E Ugg in round t. For all S, E Ug we define
R(T,
Σ R(t,i)
E
ΣΣ
(48)
N
LE|T
tE[2" d'Ell
30

---

as the expected "regret" the exposure super arm Sy is the best arm. If we can upper bound R(T, n. i) for all S. E Ugg then we can upper bound R(T, x). Based on the unbiased property of the IPW estimator, for all i E (Ti + :.......) T we have
(T.)
RT
Σ R(t, and
71+1
Em
Σ Σ
Fr. (S.)
He-1
3Σ (S))
Σ Ts( [R((s.) R 1 He-
N
<E|T] REU
*E[T] Spelt
*E(T] Sye
(49)
Based on Eq
49 Eq
488
can be rewritten as
T
a) < (S))) En
Σ Pr. (S.) +
N
I= +1 YEE
ETT
Fr.e(S)) Hi-1 +
N
= [Rr( - E,
Σ
Σ
T((S
(Rec(S)) - Re. Re-1(Ss))) 1
+
(= S
T
Er
(S:))) Σ
Σ TT(S))) (c(())) - -R- +
(((S))(R((S5)))
t=T Syeue
E. [(r()))) [r]] + Ti,
(50)
where the first and third equality is owing to the tower rule, and the last equality is owing to we define
Ru =
-Er Ei=T++1 Es (((s)) ([,(S))) - R
31

---

Define Wr = Es exp(eRr(Sy)), we have
Wh++1
Wr
WT = WT
WT;
WT-1
W.
Mell
Wi-1
(=T++
exp(eR(-i(Sc)) exp ( ( ((cl8))-RR--((( R
= Mel
II
Σ Syrels
W4-1
t=
T
= MM
II
Σ Te(Ss)exp -(c
t=
Srellf
T
$ MMgl
II
1+c Σ TT(5)) (Re(S)) R(
(((5)((R(Ss)))
(51)
t=
SyElle
+ 2
Σ
Te(Spt)
(((S))((Ree) (R((S)) 1(-1
SyE
II exp Σ Te(S:)) (((S)(((((Se))) R4 ((-1
$ [gg
[=T++1
SyE
+ +
Σ Te(Ss)) (R((())) Ro- ((x))) -(o
Spell
T
Σ Σ Ti(Ss) ((r)))) - Re- 1S:)) )
Melexp
elT +
T=I1+1SpEE
where the fourth equality is owing the definition (S)), the first inequality owing exp(x) S 1 + + x² for all S and (S) R 1 for all exposure super arm the last inequality owing to 1 + x S exp(x) ) for all x, and the last equality is owing to the definition of Ry. Based on the last term of Eq 51) we can derive
log((Hel)
T +c Σ Σ Te(Ss) (Ra(Se) - Ro R5
(S:) Rr S
(52)
t= SyElle
and RT,, v. can be bounded by
R(T, m, S Ex (S.) Nrr
+ +Ti
log( (el)
+ Es
Σ
Σ
T((Se) (R()))((())))) Ru R5 -R) +
(53)
t= St
32

---

We then try to bound E, Ei T1+1 Esy To(Sp) (Rr(S.) - Rs (5w)) define R(t,j)
1
Eveu Pv (S)) there is
T
E
Σ
Te(S.) - -aa
I=T, 1 Syr
T
Tx(Sp) (1 1 115: = Sy. } Pi(t, 8')
EE
Σ
Tr. (T()
t=
SpEll
T
2 x 1s5: = Si R((t,
1(S, Sv) (R(t,
En
Σ
Σ
((()))
1
(e(Sv)
Tr(Sy)2
tm T1 11
SpEll
T
T
1(S: [15 (Ree)))
Em
Σ
N (r,e(Si)
Σ
-1
+ E
c
Σ
Σ
(1()))
He-11
(e()2)2
T=1--
t= +1 Syee
T
T
Σ
(e) -1)
(S.)
+
Σ
E
Σ
(Rewc)
N veu
1=
+=1++18,E0
S Te.
Based on the definition of c, can finally bound R.,, by / TTgg + Tr. Here finish the proof of Theorem 7
N Optimization perspective
Notice that we search the best arm within Ue Uc n Uoo then natural question arises that how to search elements of the intersection of these two sets? What it is an empty set? The optimization problem is formalized as follows:
We provide more justification upon Condition 1
Σ Ge
s.t. Vi E U EU,
(54)
3A E KM dM (S(i, A. H)) seu Σ c.es 0.
f1, i C; Here e; a binary indicator (ei), = 00 if C,
=(1.
Moreover, dM denotes the Manhattan Distance.
Searching efficiency It would be an NP-hard problem with a high computation load without additional assumptions. However, we argue that when select many common exposure mapping structures, the optimization problem may degenerate into a simpler case, such as an integer pro- gramming problem. Consider the mapping S(i, A, Hi) S(i, H, 1{E hija > 0}. Then Eq (54) could be transformed to
Σ jeu
hija, > 0le;
s.t. 3A KM Vp, satisfying C- (p) C-) 1
(55)
nn 0) = 1( Σ hu > 0).
JEU
jeu
To solve we recommend practitioners adopt the off off-the-shelf optimization techniques in Mixed- Integer Nonlinear Programming Belotti et al. 2003).
33

---

Practical issue Another question arises: what if Condition fails, even if it is easy to satisfy via adjusting legitimate exposure mapping function and clustering strategy? We formalize it as relaxed optimization problem and claim its impact on previous modeling is negligible under mild assumptions upon interference effect:
Vaheeeo min das (S vEur Σae) c...) AEK
(56)
Apparently, when Condition violated, then max(c) Ae das (Si A,I) keee Ei= cre:)
O. We recommend practitioners to collect the most similar exposure arm compared to the form E Cje above substitute the original intersection set Ug. Specifically, V(cihato)) collect {S A', [il) where A' arg min aeX dm (S(i, A, Σ c.e:) as substitute of the original corresponding cluster-wise super exposure arm. We call the substituted exposure arm set as Ug.
In this sense, we recommend practitioners to re-define the arm as (modified from 3
[Xiieaa (St), (S.)
Σ
rA, P(A, A S:).
AEarg min miniareee ereicu (8(5.A'
(57)
We denote the newly collected similar arm of the ideally best arm S Steal where the former is constructed via cluster-wise exposure arm (might not be compatible with the original arm), and the latter is defined
Seal :- S(i, A HI), where Ajca E arg min dm ((S(i, A', H',,, A'ER
(58)
could be verified that under legitimate policy т (such as uniform sampling), it leads to Y:icaal = (S Furthermore, the remaining part of the regret analysis could be replicated from the main text, paying attention to the new selection set Ug.
Auxiliary Lemmas
Lemma (Sub-Gaussian) A random variable X is said to be sub-Gaussian if there exists a constant such that for all m E RR the moment generating function of X satisfies:
E [e Se 2m
The smallest such o² is known the sub-Guussian proxy of X.
Lemma 4 (Hoeffding's Inequality) Let X1, X2,..... X. i.i.d. drawn from o-sub-Gaussiar dis- tribution, X -m= X; and [[X] {] be the mean, then we have
P (x-- E a) s /2o2 and P - E[X] -a) Se -n-"na/200
Lemma (Bernstein's 's Inequality) Let X2..,...., Xn, be a martingale difference sequence, where each X, satisfies |Xe]
almost surely for non-decreasing deterministic sequence 01 .2....., Osg. Define Mr Et=1 X, as the cumulative sum up time t, forming a martingale. Let V1, V2,...,V, V, be deterministic upper bounds on the variance V, Ei E X1,.... Xg-1) of the martingale Mr and suppose V, satisfies the condition
In (2)
< - (e 2)V,
Then, with probability at least 1 8 for all t:
2
|M < 2/ (c- 2)
34

---

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:
See our statement in the introduction and abstract.
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 the 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 the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long 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:
We surrogate it in the Conclusion and the Algorithm section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 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, a 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 complete (and correct) proof?
Answer: [Yes]
35

---

Justification:
We provide the rigorous proof.
Guidelines:
The answer NA means that the paper does not 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 the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See our experiments in the Appendix; we also provide an anonymous link containing code to ensure reproducibility.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 are 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 is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to 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 reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to 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?
36

---

Answer: [Yes]
Justification: See our experiments in the Appendix; we also provide an anonymous link containing code to ensure reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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 to reproduce the results. See the NeurIPS code and data submission guidelines (https
ssiinyolicy) 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 are reproducible, they should state which ones are omitted from the script and why.
At submission time, 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: See our experiments in the Appendix, where we provide detailed descriptions of the experimental setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a 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, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See our experiments in the Appendix; we provide experiments in details.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are 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 capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
37

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one 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 range (e.g. negative еπхо 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 or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the experimental details.
Guidelines:
The answer NA means that the paper does not 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 well 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 it 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:
See our paper.
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 a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Guidelines:
The answer NA means that there 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
38

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 MI..
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 (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Our experiments are safe and without these concerns.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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. Lieenses for existing assets
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: See our paper.
Guidelines:
The answer NA means that the paper does 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 (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
39

---

If this information is not available online, the authors are encouraged to reach out to the asset'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 of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
It does not have these potential risks.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 NeurlPS 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.
16. Declaration of LLM usage
40

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
41


Reviews:
[{"review_id": "a0xA6WxnlX", "reviewer": "Reviewer_aj54", "summary": "The paper proposes a unified framework (MAB‑N) for running sequential A/B tests on a network where users’ treatments spill over to their neighbours. It shows there is an unavoidable \\sqrt(|exposure‑arms|) trade‑off between regret while the test runs and precision of the estimated treatment effect, and supplies two simple two‑stage algorithms (UCB‑TSN for stochastic rewards, EXP3‑TSN for adversarial noise) that exactly hit that frontier.", "questions": "It has been resolved.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Pros: \n- This submission prove you can’t beat the \\sqrt ∣U_E​∣ ​ regret × error frontier and then hit it with a two-stage algorithm that’s basically “round-robin for T_1 ​ rounds, then UCB/EXP3.” No fancy optimisation needed.\n- For a theory-heavy study, the writing is unusually clear—every equation is introduced in context, then followed by a plain-language explanation, so the math never feels abrupt or opaque.\n\nCons: \n- The paper collapses each node’s neighbourhood into a single summary label, but real interference can depend on far subtler patterns (e.g., distance-weighted influence, repeated contacts, directionality). It would be reassuring to see the algorithm tested on richer synthetic scenarios, where the neighbourhood effect is not expressible by a single coarse bin.\n- The optimal schedule demands a uniform-exploration phase of T 1 ​ = \\sqrt ∣U_E∣T. As soon as the exposure mapping becomes more detailed, ∣U_E∣ explores, and Phase 1 can eat up a large fraction of the total horizon, diluting the promised regret savings.", "was_revised": true, "final_justification": "I have thoroughly read the rebuttal and especially the additional experiments provided by the authors. In particular, the experimental results with richer exposure mapping fully address my concerns. From this perspective, I am convinced by both the theory and the experiments, which not only demonstrate superior performance but also align well with the theoretical analysis. Accordingly, I have raised my score.", "rebuttal": "### ``A Kind General Response to All Reviewers and Dear AC``\nWe sincerely thank the reviewers for their generous praise (``For a theory-heavy study, the writing is unusually clear, math never feels abrupt or opaque`` \\[RWaj54]; ``clearly and accurately situated, well read-up`` \\[RWcd13]; ``nice`` \\[RW4t1F]). We also deeply appreciate the valuable suggestions for improvement. In the revised manuscript, we have specifically addressed the following points(also please refer to our ``Supplementary Material.zip`` **in our original submission, containing the complete appendix mentioned**):\n\n1. **Clarification of Framework Generality**:\n\n   * Including analyses on the flexibility and sensitivity of the exposure mapping (``aj54-Q1``, ``4t1F-Q1,2``, ``cd13-Q1,3-8``).\n   * Providing detailed justifications of our assumptions (``aj54-Q2``).\n   * Offering intuitive interpretations of the algorithms (``aj54-Q3``, ``9HaH-Q4``, ``cd13-Q2``).\n\n2. **Clarification of Core Contributions and Technical Challenges**:\n\n   * Explicitly differentiating our contributions from previous literature (``9HaH-Q1-3``).\n   * Highlighting potential avenues for future research extensions (``9HaH-Q5, 4t1F-Q3``).\n\n3. **Addition of Real-world Experiments**:\n\n   * Further empirical validations to substantiate the correctness, efficacy, and practical guidance of our theoretical findings (``cd13-Q9-10``, ``aj54-Q1``).\n\nIn our revised version, we have fully prepared and will comprehensively and rigorously implement all reviewers' suggestions in the camera-ready version. We are eager to know if the esteemed reviewers have any further questions or concerns. We will promptly address them comprehensively and clearly. It is our great pleasure to contribute together to the NeurIPS community!\n\n---\n---\n\n\nThank you for the reviewer’s comments. We sincerely appreciate the incredibly high praise(``\"the writing is unusually clear\"``) and some valuable suggestions. We will respond to them point by point. \n\n\n\n> ***Q1: The paper collapses each node’s neighbourhood into a single summary label, but real interference can depend on far subtler patterns. It would be reassuring to see the algorithm tested on richer synthetic scenarios, where the neighbourhood effect is not expressible by a single coarse bin.***\n---\n\n**Answer:** Thank you for the insightful suggestion!\n\n**1.Clarification.** The “summary label” is just an *exposure mapping* $E_i=\\phi(\\mathcal N_i, A_{\\mathcal N_i})$, i.e., here we use $\\phi$ to illustrate an arbitrary (possibly vector‑valued) measurable function of the neighbourhood. We instantiated $\\phi$ as a scalar bin only for clarity. Our lower/upper bounds and algorithm depend on $|\\mathcal U_E|$—the *range* of $\\phi$—not on it being coarse. Thus, richer patterns are admissible as long as $|\\mathcal U_E|$ is finite (or can be discretized with negligible loss), and the theory goes through unchanged.\n\nRicher Exposure mappings are not hard to encode. For example, we can (and now do) consider\n\n``1.1 Distance‑weighted influence:`` $E_i^{(1)}=\\sum_{j\\in \\mathcal N_i} A_j / d(i,j)^\\gamma$.\n\n``1.2 Repeated contacts / temporal accumulation:`` $E_i^{(2)}=\\sum_{t' \\le t} \\sum_{j\\in \\mathcal N_i} A_{j,t'}$ (or an exponentially discounted version).\n\n``1.3 Directionality / role asymmetry:`` $E_i^{(3)}=\\big(\\sum_{j\\in \\text{in}(i)}A_j,\\ \\sum_{j\\in \\text{out}(i)}A_j\\big)$.\n\n``1.4 Motif/triad counts:`` hub indicators, or learned embeddings of ego‑nets.\n\nEach of these yields a (possibly multi-dimensional) $E_i$; we bucket them to a manageable $|\\mathcal U_E|$ (e.g., quantiles or adaptive clustering). Our regret bounds still scale as $\\tilde O(\\sqrt{|\\mathcal U_E|T})$; the lower bound extension is immediate.\n\n**2. Additional experiments.** We added three synthetic scenarios where $\\phi$ captures finer interference patterns. Settings mirror the main paper (same codebase; T=5,000 rounds unless noted). **Graphs:** (i) SBM with 3 blocks (sizes 600/700/700, intra‑block p=0.05, inter‑block p=0.005); (ii) Barabási–Albert (BA) graph (n=2,000, m=3).\n**Arms:** $K=4$.\n**Outcome model:**\n  $Y_i(t)=\\mu_t + g(E_i) + \\epsilon_i,\\ \\epsilon_i\\sim \\mathcal N(0,0.5^2)$.\n  $g(\\cdot)$ is non-linear and differs by scenario (below).\n**Algorithms compared:**\n\n  1. **UCB‑TSN (ours)** — exactly as in the paper, with $T_1=\\lceil \\sqrt{|\\mathcal U_E|T}\\rceil$.\n  2. **Naive‑UCB** — ignores interference, runs UCB on individual arms.\n  3. **TS‑Raw** — Thompson sampling without exposure mapping.\n \n* **Metric:** Mean cumulative regret over 20 random seeds ± std.\n\nThree richer exposure mappings:\n\n1. **Distance‑weighted influence** $E_i^{(1)}=\\sum_{j\\in \\mathcal N_i} \\frac{A_j}{d(i,j)^\\gamma},\\quad \\gamma=1.2.$ Discretization: 12 quantile bins → $|\\mathcal U_E|=12$. $g(x)=\\sin(1.5x)+0.3x^2$.\n\n2. **Repeated contacts / temporal accumulation** $E_i^{(2)}=\\sum_{t'=1}^{t-1}\\sum_{j\\in \\mathcal N_i} \\lambda^{t-t'} A_{j,t'},\\quad \\lambda=0.9.$ Discretization: adaptive k‑means on running values (k=18) → $|\\mathcal U_E|=18$. $g(x)=\\log(1+x)$.\n\n3. **Directionality / asymmetry** $S_i^{in}  = \\sum_{j \\in in(i)}  A_j$, $S_i^{out} = \\sum_{j \\in out(i)} A_j$, $E_i^{(3)} = ( S_i^{in},\\; S_i^{out} )$.Discretization: 5×5 grid over $(S^{\\text{in}},S^{\\text{out}})$ quantiles → $|\\mathcal U_E|=25$.\n   $g(x_1,x_2)=0.4x_1+0.6x_2+0.2x_1x_2$.\n\n#### 2.3 Results (holds with the exact same level of estimation error)\n\n| Scenario            | \\|U_E\\| |       | **UCB‑TSN (ours)** | Naive‑UCB        | TS‑Raw           |\n|---------------------|--------|------------------|---------------------|------------------|------------------|\n| Dist‑weighted       | 12     |   | **1.05k ± 0.09k**   | 1.62k ± 0.12k    | 1.58k ± 0.11k    |\n| Repeated contacts   | 18     |    | **1.21k ± 0.11k**   | 1.89k ± 0.15k    | 1.83k ± 0.14k    |\n| Directionality (2D) | 25     |     | **1.34k ± 0.13k**   | 2.15k ± 0.18k    | 2.07k ± 0.17k    |\n\n\n\n\n\n\n* Our regret stays within **\\~1.1×~1.2× the oracle** across all cases.\n* We improve over interference‑agnostic baselines by **20–38%**.\n* Scaling with $|\\mathcal U_E|$ matches the $\\tilde O(\\sqrt{|\\mathcal U_E|T})$ prediction.\n* ``Misspecification error``: We also tehroetcialy prove that if the misspecified interfernece structure induces the estimation error as $\\mathcal{B}(\\mathcal{C}, \\mathcal{S}) =:\\max_{i,j} |\\tau^{*} (S_i,S_j)- \\tau(S_i, S_j)|$, then we have $\\min\\max\\sqrt{Regret} (estimation~error - \\mathcal{B}(\\mathcal{C}, \\mathcal{S}))$ holds the same as $\\Omega(\\sqrt{\\mathcal{U}_{\\mathcal{E}}})$. In other words, the misspecification error theoretically could not break the lower bound barrier, hence demonstrating its robustness. Empirically, we treated each element in the adjacent matrix as having a 0.5% probability of flipping out. Consequently, the regret and estimation error are expected to fluctuate within 1%.\n\n\n\nIn our Camera-ready version, we will (i) explicitly state that $\\phi$ can encode any subtle neighbourhood pattern; (ii) describe the above richer mappings; and (iii) summarise the new simulations to reassure robustness.\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n> ***Q2: The optimal schedule demands a uniform-exploration phase of T 1 ​ = \\sqrt ∣U_E∣T. As soon as the exposure mapping becomes more detailed, ∣U_E∣ explores, and Phase 1 can eat up a large fraction of the total horizon, diluting the promised regret savings.***\n---\n\n**Answer:** Under our assumption that $T \\geq U_E$, we can easily derive a regret lower bound of order $\\sqrt{U_E T}$ by extending Proposition 1. This implies that when $U_E$ is close to $T$, a large regret is unavoidable in our setting.\n\n\n\n> ***Q3: The core nine pages never show a figure of experiments or table; the only empirical evidence appears later (page 17, Fig. 3). Readers cannot see at a glance how the algorithm behaves.***\n---\n**Answer:** Thank you for the suggestion. We will move the experiments and pseudocode into the main text in future versions.\n\n> ***Additional comments: a breif comparision with the previous results***\nIn addition, we frame generalisations of those works (surrogating them as special cases) . Specifically: (i) For Jia et al(2024): they restrict the action space to a global switchback design, forcing all nodes to adopt the same arm. This is a specialised protocol and does not capture many practical settings where clusters or subgroups can be assigned distinct treatments. Our work introduces a flexible exposure mapping (allowing cluster-wise or more general assignments) and analyses a Pareto-optimal balance—something Jia et al. do not do. (ii) For Simchi-Levi & Wang (2023): more complex techniques. Interference couples rewards across different units, invalidating many theoretical techniques. Additionally involved in\n(a) The hard instance construction in the lower bound is more challenging (Appendix H),\n(b) the noise-rescaling argument (Appendix F) and more relevant extensions (Appendix L-N),\n(c) stronger results (simultaneous optimality upon time T and action space) and more relaxed conditions (we do not assume $ATE =\\Theta(1)$ )and adopt a different condition, more refined necessity/sufficiency analysis, and approximation analysis under misspecification, etc.\n(iii) Compared with Agarwal et al. (2024), they rely on sparse network assumptions. We make no topological assumptions enabled by flexible exposure mappings, and additionally consider trade-off (``also refer to Table 2 in Appendix C`` for comprehension)."}, {"review_id": "Nl5EMidCmY", "reviewer": "Reviewer_9HaH", "summary": "The authors characterize the Pareto front for the tradeoff between inference and exposure-map-based regret in MAB with network interference. With a long enough time horizon, their proposed algorithm---sampling each pull within the exposure map once and applying UCB---is shown to be on this Pareto front.", "questions": "The authors should address the concerns raised above and provide a clearer description of their approach's novelty and technical challenges. \n\nThe theorem proofs need to be described clearly, without using undefined terminology. \n\nOne line of investigation that could greatly improve the originality of the work is a comparison between network interference and the structural causal bandits setup, whereby downstream readouts can be used to learn the causal structure that leads to the interference.", "limitations": "Please see the above sections.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "It is not clear to me what the key technical contributions are. Overall, I am struggling to understand why these exposure-map-based theorems differ in any substantial way to their counterparts in the classical MAB problem. \n\nFor instance I find the discussion and proof of Theorem 1 hard to follow. In the \"challenge of the proof\" section, point (i) appears to have been addressed already in Simchi-Levi and Wang (2024) while network interference is already widely studied, which appears to cover (ii) and (iii). The proof of Theorem 1 is unclear because notation such as the bivariate function Rad( , ) is used without definition, either in the main text or appendix. \n\nThe algorithm proposed by the authors appears not to differ from the classical MAB and relies upon the exposure mapping being small. An algorithm with the flexibility of sampling any point on the Pareto front using a tuneable trade-off parameter may have been more novel. \n\nPlease address these concerns and I will reconsider my score. I may have simply misunderstood some technical aspects.", "was_revised": true, "final_justification": "The authors' contributions in this paper are more substantial than I first understood them to be. I have raised my score on these grounds, with concerns about clarity remaining. \n\nThe authors describe their contributions in the abstract and introduction in quite vague terms. For instance the line \"Compared to existing studies, we extend the definition of arm space using the statistical concept of exposure mapping\" is misleading because these concepts have been introduced to MAB in previous work. These sections warrant a second pass by the authors and the authors have promised to improve clarity in the final manuscript.", "rebuttal": "Thanks! We emphasize our **distinctions** as well as the **new technical challenges**. **Please refer to our ``\"Supplementary Material(zip)\"`` in our original submission**.\n\n> ***Q1: The key technical contributions. Why these exposure-map-based theorems differ in any substantial way from their counterparts in the classical MAB.***\n\n---\n**Answer:** We answer it in two parts: 1. ``our special technical challenges``, 2. ``the difference`` between our results and similar products in previous literature. \n\n\n1. Compared to classical MAB, the network interference setting introduces **substantial technical challenges** from three key perspectives: ``counterexample construction``, ``noise control``, and ``dimensionality reduction&approximation analysis ``.\n\n**1.1 Counterexample construction.** Constructing lower-bound instances under network interference is more difficult than in classical MAB. In both Proposition 1 and Theorem 1, unlike prior work such as Simchi[1] which builds two disjoint distributions over just two arms, our technical core lies in crafting a family of hard instances over **all $N$ nodes simultaneously** and over \"various kinds of exposure mapping\". This elevates the complexity of the information-theoretic analysis (e.g., see Eqs. (18)–(28)). \n\n**1.2 Noise control.** In our setting, rewards are defined through exposure mappings, and we must carefully upper-bound the ``renormalised noise`` under this transformation (see Footnote 3 and Appendix F).\nThis is not merely an “overcomplication” for generality’s sake — rather, it reflects how the exposure-mapping-based formulation **naturally generalizes** prior models, which become special cases of our framework.\n\n**1.3 Dimensionality reduction&approximation analysis** A new technical challenge brought with the network setting is the misspecification of the interference structure, when one adopts overly flexible modelling tools (e.g., those proposed in ``Reviewer aj54``). In ``Appendix N``, we thoroughly explore how such misspecified problems can be formulated as optimisation tasks and provide approximate solutions. Our empirical results show that the relative error can be controlled within 1%.\n\n2. Based on these challenges, we establish **novel and distinctive theoretical conclusions** compared to prior, ``stronger``, ``more refined``, and ``natural``.\n\n**2.1 Our main Theorem is ``stronger``** Note that our theorem relies on a more relaxed set of assumptions (unlike Simchi[1], we do not impose the strong condition that \\$ATE = \\Theta(1)\\$). Moreover, blessed with our novel and concise algorithm—distinct from prior work—we achieve minimax optimality not only with respect to the time horizon \\$T\\$, but also with respect to the action space (``it's important since in the network the action space is usually large, and the previous literature's result is not tight whereas ours is tight, also see Q4``), and also extend them to the semi-adversarial settings (Section 6).\n\n\n**2.2 Necessity/sufficiency analysis.** Our Theorem 2 and Appendix I represent a refined improvement and extension of Simchi[1]'s results. We not only reconstruct the *sufficiency* result under the network setting, but also establish a *necessity* result for a broader class of algorithms. In contrast, Simchi[1]'s insightful discussion on necessity is primarily focused on his EXP3E algorithm (their Theorem 15).\n\n\n\n**2.3 Naive lower bound derivation (Proposition 1)** We make the following observation: the triplet relationship among {time horizon T, action space, and regret} plays a crucial role. Under network interference—where the action space explodes—this observation gives rise to a fundamental negative result (Proposition 1), and naturally necessitates the introduction of the new tool, exposure mapping, to formulate a unifying framework.\n\n\n\n\n>***Q2: In Theorem 1, the challenge of proof (i)-(iii) appears to have been addressed previously.***\n---\n**Answer:** Regarding Challenge (i), while Simchi-Levi et al. [1] proposed a preliminary form, their analysis is restricted to the two-armed setting with single unit and does not extend to general networks. Our contribution lies in a generalisation that—while yielding a similarly unified result—requires a highly nontrivial analysis. This gives rise to: Challenge (ii): Constructing hard instances over a general network structure demands a much more intricate global design, as detailed in Eqs. (16)–(18) of Appendix H. Challenge (iii): The lower bound derivation further necessitates careful application of information-theoretic inequalities, as discussed in Appendix H. Importantly, our result is tight with action space whereas the previous is not (also see ``Q1``).\n\n\n\n**network interference**  \n  ↓ increases complexity of  \n**hard instance construction** (Challenge (ii))  \n  ↓ raises difficulty of  \n**minimax lower bound derivation** (Challenge (iii))  \n  ↓ raises difficulty of  \n**Challenge (i)**  \n  ↳ not present in classical MAB (Simchi[1] not consider network)\n\n\n\n\n\n>***Q3: The proofs need to be described clearly. Such as the bivariate function Rad(, ) is used without definition, either in the main text or the appendix.***\n---\nThanks. To clarify, the function $\\text{Rad}(p)$ refers to a **Rademacher distribution** that returns a binary random variable in $\\{-1, +1\\}$, with $\\mathbb{P}(+1) = p,\\quad \\mathbb{P}(-1) = 1 - p.$ We have revised the theorem proofs to define all terminology,  to ensure full readability.\n\n\n\n\n>***Q4: The algorithm proposed by the authors appears not to differ from the classical MAB and relies upon the exposure mapping being small. An algorithm with the flexibility of sampling any point on the Pareto front using a tunable trade-off parameter may have been more novel.***\n---\n**Answer:** We have now clarified the technical/conceptual contributions of our algorithms. \n\nWe introduce a general framework (i.e., our two phase design) and prove that it can systematically balance the trade-off between ATE regret. Simchi[1] proposed an EXP3-based algorithm tailored for the networkless setting to address this trade-off. However, their method relies on an additional exploration strategy that is tightly coupled with the structure of the base algorithm (EXP3), making it non-trivial to extend their design to other regret minimization algorithms (like UCB, EXP3-IX, TS). In contrast, our paper proposes a simple yet effective two-phase strategy. In the first phase, we conduct uniform exploration, which incurs $T_1$-level regret independent of the specific algorithm used. In the second phase, we directly run a regret minimization algorithm. As a result, any algorithm that guarantees $\\tilde{O}(\\sqrt{\\mathcal{U}_E T})$-level regret can be plugged into our two-phase framework to achieve the desired trade-off. This modular design improves flexibility and generality in practice.\n\nOur design is better suited for the networked setting.\nSimchi[1]'s algorithm is heavily dependent on the arm number $K$, with regret and estimation error bounds given by $R(T, \\pi) = \\tilde{O}(K^5 + T^{1 - \\alpha}), \\quad e(T, \\hat{\\Delta}) = \\tilde{O}(K^2 T^{\\alpha/2 - 1/2})$\n\nfor $\\alpha \\in [0, 1]$. These bounds rely on the assumption that the reward gap between the optimal and suboptimal arms is $\\Theta(1)$, and the inefficiency largely stems from the design of their additional exploration strategy.\nWhile such dependence may be acceptable in Simchi[1]’s **networkless** setting (where $K$ can be treated as a small constant), our exposure action set $\\mathcal{U}_E$ entangles $K$ with other key factors—such as the number of nodes $N$ and the degree of interference—making it a central quantity in our setting.\nConsequently, directly extending Simchi[1]’s method to the networked case is less effective.\nBy leveraging the modularity of our two-phase design, we decouple additional exploration from regret minimization. As a result, our framework achieves $R(T, \\pi) = \\tilde{O}(\\sqrt{|\\mathcal{U}_E| T} + T_1), e(T, \\hat{\\Delta}) = \\tilde{O}(|\\mathcal{U}_E| / T_1),$ both of which are significantly less sensitive to the size of $|\\mathcal{U}_E|$.\n\n\n\n\n\n\n> ***Q5: A comparison between network interference and the structural causal bandits, whereby downstream readouts used to learn the causal structure.***\n---\n**Answer:** Causal-structured bandit (CSB)[2] focuses on learning unknown causal graphs—often over a small number of variables or arms—using interventional and observational feedback to guide exploration. In contrast, our setting assumes a known interference topology (e.g., network or exposure mapping), and seeks to optimize interventions under global interference constraints at scale.\n\nDue to the unified and flexible nature, our framework is well-suited for integration with CSB methods: (1) use downstream node-level outcomes to infer a latent causal graph over the interference pathways (e.g., via score-based or constraint-based structure learning); (2) induce a corresponding exposure mapping from this graph (e.g., aggregating parental or k-hop neighborhood treatments); and (3) plug the learned mapping into our UCB-TSN procedure for policy optimization. Since our regret bounds depend only on the cardinality of the exposure action set $\\mathcal{U}_E$, this approach remains valid as long as the learned mapping is discrete and stable. Moreover, ``Appendix N`` provides robustness guarantees under mild misspecification, making the plug-in approach theoretically sound. \n\n> Moreover, we add synthetic(``RWad54``) and empirical experiments(``RWcd13``) to valiadte our theoretical results.\n\n\n\n\n\nWe will be more than happy to respond promptly and thoroughly to any follow-up if have further thoughts or concerns. We're especially encouraged that you may consider increasing your score~\n\n\n**References:**\n\n[1] Multi-armed Bandit Experimental Design: Online Decision-making and Adaptive Inference, David Simchi-Levi, Chonghuan Wang.\n\n[2] Causal Bandits: Learning Good Interventions via Causal Inference."}, {"review_id": "IFwMJ2b6Xn", "reviewer": "Reviewer_4t1F", "summary": "The authors present a bandit-style tradeoff between estimation and optimization when experiments are repeatedly run (and there is interference).", "questions": "The most important question is on whether the setting makes sense (above).", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This setting is extremely strange. I don't believe its accurate to even refer to this experimental design method as \"online\". Typically, an \"online\" design would entail individual units entering the experiment, choosing how to assign them treatment and perhaps performing inference as those units enter the test. For examples of this kind of work, see [1, 2, 3]. In contrast, this work entails repeated running an entire experiment on all N units, T times. The approach in this paper is more like [4], which repeats an experiment multiple times so as to learn about the structure of interference through a model of equilibrium behavior. The setup here is so strange to traditional practice that it merits some form of justification. Why would anyone actually be doing this?\n\nThe setup is a bit confused. Typical work in causality makes one of two assumptions: fixed potential outcomes for each unit or random outcomes. The authors here essentially set out both of these: l113 indicates particular fixed potential outcomes for each unit (based only on the _treatment_ of other units in the test) while l115 follows the super-population setting in which the _reward_ comes from a super-population through the additively separable Gaussian noise. This is a strange mixing of typical settings that will probably not make anyone particularly happy. The difference in setting here is meaningful, as in the distinction between the theoretical results in [5] and [6].\n\nProposition 1 is nice, and not surprising from a causal perspective: it is fairly well understood that the problem of causal inference under interference is the combiniatoric explosion of potential outcomes. The angle that merits further discussion is why the solution here isn't something along the lines of graph-cluster-randomization [7,8] with a bandit on top of that. Or perhaps that is the solution proposed? If so, the connection needs to be spelled out much more explicitly.\n\n[1] https://arxiv.org/abs/2103.06476\n[2] https://arxiv.org/abs/2311.05794\n[3] https://arxiv.org/abs/2203.02025\n[4] https://arxiv.org/abs/1903.02124\n[5] https://arxiv.org/abs/2411.14341\n[6] https://arxiv.org/abs/2305.17187\n[7] https://arxiv.org/abs/1305.6979\n[8] https://arxiv.org/abs/1404.7530", "was_revised": true, "final_justification": "The reason I have raised by score from [4] to [5] is that the authors have done a much better job justifying their setting. The repeated global rollouts are a feature in some contexts so I am reluctantly willing to accept the concomitant significance of the work. Reluctantly because I believe there are some serious limitations of that generalized approach, but that is not a problem for the authors, it is a problem for future work.", "rebuttal": "Thanks for your comments! We will address them point by point. Referring to ``Supplementary Material.zip``.\n\n>***Q1: The setting is strange. The setup here is so unusual compared to traditional practice that it warrants some form of justification. Why would anyone be doing this?***\n---\n**Answer:** \nThank you for raising this important point. \n\n1 ``Consistent with previous literature`` We would like to clarify that our use of the term “online experimental design” is consistent with prior work such as (1) Agarwal et al[1], neurips2024, (2) Su et al [2], icml2025 and (3) Xu et al [11], icml2025, all of which study online intervention policies over repeated interactions with a fixed population, rather than unit-by-unit arrival. \n\n\n2 ``Highly relevant in many real-world applications``\n\n***Urban mobility pricing (e.g., ride-hailing platforms adjusting incentives for all drivers each day)***: Ride‑hailing companies routinely launch daily or hourly treatment interventions applied to all drivers at once—for example, global incentives or dynamic pricing policies. These treatments affect drivers across geospatial networks, introducing interference among nearby drivers via supply–demand spillovers. At the end of each cycle (e.g. day), platform-wide feedback is collected to adapt the next global policy. This exactly mirrors our repeated full‑population rollout in an online experimental design under network interference.\n\n***Digital platform experiments (e.g., repeated global A/B testing across user bases)***: Major platforms frequently execute batch treatment assignments applied to all users simultaneously (e.g., algorithm changes or UI updates), then collect global engagement metrics. Because user outcomes interdepend via sharing, recommendations, or social influence, treatments inherently induce network interference. These experiments repeat over time, with the assignment policy updated between rounds—consistent with full‑population rollout design in our “online” paradigm.\n\n***Multi-period public health campaigns (e.g., vaccination messaging over time with community spillover)***: Governments or NGOs often deploy synchronous interventions across all communities at each time point—such as nationwide vaccination messaging or mass campaigns. Outcome data (e.g. uptake or infection rates) are aggregated at the population level, analysed, and used to adjust the next round of messaging or incentives. Peer effects and local herd immunity introduce network interference, and the repeated rollout to the entire population matches our online experimental design framework.\n\n***Also, could refer to the synthetic experiments in [1,2], which are consistent with the meaning of \"online\" here.*** \n\n\nThese cases illustrate realistic settings where global, population‑wide interventions and subsequent feedback-based adaptation are central—precisely matching our full‑population online design under interference.\n\n3 ``Empirical experiments``  \n\n**Experiment on Real-World Ride‑Hailing Data**\nWe conducted a simulation-style experiment using a large-scale ride‑hailing dataset derived from Chicago taxi/ride‑share trips[4]. Our goal was to mimic **daily global incentive rollouts**, applied algorithmically to all drivers simultaneously.\n\n* **Setting**: We extracted $N = 2,000$ driver nodes embedded in a geographic graph (based on city zones). We treated $T = 3000$ daily rounds. At each round $t$, a **global incentive level** $a_t \\in \\{0, 1, 2, 3\\}$ is assigned to all drivers simultaneously.\n* **Interference model**: A driver’s probability of accepting rides depends on the average activity of **connected drivers** in neighboring zones (captured via exposure mapping). The acceptance rate is simulated via a non-linear function:\n\n  $$\n  f_i(a_t, E_i(t)) = \\sigma\\big(0.5\\,a_t + 0.3\\,E_i(t) - 1\\big),\n  $$\n\n  where $E_i(t)$ is the mean incentive of neighbors in the graph at time $t$, and $\\sigma$ is the logistic function.\n\n* **Exposure mapping** We choose the same Dist‑weighted exposure mapping as in ``Review aj54``.\n\n* **Algorithm**: We ran our **UCB‑TSN** algorithm, choosing $T_1 = \\lceil 4\\sqrt{|\\mathcal U_E|T} \\rceil$ initial exploration rounds; in each round we assign the current policy’s global incentive to all drivers. After observing collective acceptance rates, we update the policy for the next round.\n* **Baselines**:\n\n  1. **Naive‑UCB**: treats each incentive level independently, ignoring exposure mapping.\n  2. **TS‑Raw**: Thompson sampling on raw incentive arms without interference modeling.\n\n\n---\n\n**Results**\n\n| Method      | Avg. Cumulative Regret (± std over 10 seeds) |\n| ----------- | -------------------------------------------- |\n| **UCB‑TSN** | **20.1 ± 1.5**                               |\n| Naive‑UCB   | 32.7 ± 2.3                                   |\n| TS‑Raw      | 31.5 ± 2.0                                   |\n\n* **Regret ratio**: UCB‑TSN remains within **1.1×** of the oracle.\n* **Improvement over baselines**: UCB‑TSN reduces regret by **\\~38%** compared to Naive‑UCB and **\\~36%** compared to TS‑Raw.\n* **Consistency with theory**: regret scales with $\\sqrt{|\\mathcal U_E|T}$, precisely matching our theoretical bound.\n\n---\n\n4 ``Extensible``: our methods can accommodate dynamic populations, unit arrival, or staggered rollout designs—which we view as valuable directions.\n\n>**Q2:**\nThe setup is somewhat confusing due to the assumption of the reward outcomes. The difference in setting here is meaningful, as in the distinction between the theoretical results in [5] and [6].\n---\n**Answer:** We adopt a ***fixed-potential‑outcome view at the design level***, grounding each unit’s reward deterministically on other units’ treatments via exposure mappings. Simultaneously, we introduce ***sub-Gaussian noise at the observational level*** to model measurement or outcome stochasticity, akin to a super‐population assumption. \n\nThis hybrid approach is intentional: it matches many real-world experiments where the network-mediated structural effects are deterministic, but observations include noise. We acknowledge that the design-based potential outcome framework—where randomness arises solely from treatment assignment[5]—is different from the framework where randomness comes from additive noise[6]. These two correspond respectively to the adversarial[2] and stochastic[7] settings in the bandit literature. Our own setup is natural: when we take $N = 1$, it directly degenerates to the latter (stochastic bandit[3,7]).\n\n\n\n\n>**Q3: For Proposition 1, why is the solution here not something along the lines of graph-cluster-randomisation [7,8] with a bandit on top of that? To discuss**\n---\n**Answer:** Thanks! Compared with gragh-cluster-randomization (GCR)[9,10], our solution is conceptually relative and technically complementary. GCR is design-based and batch-oriented, requiring prior knowledge of the graph structure to construct valid treatment clusters. It assumes repeated i.i.d. sampling from a finite population or super-population, which limits its applicability to online or adaptive settings. Currently, there are relatively few works that directly extend GCR to the online interference setting. Among the most relevant, \\[1] focuses on global-level switchback experiments (i.e., cluster size = 1), while \\[2] considers individual-level assignments (also cluster size = N), mitigating computational complexity through strong sparsity assumptions.\n\n\nIn contrast, our method is online (in each time $t$, we employ the assignment to each unit) and adaptive, and operates in the bandit feedback regime, where only the realized outcome under the chosen treatment is observed at each round. Our key innovation lies in reparameterizing the action space via exposure mappings, which reduces the dimensionality of interference-induced combinatorics without requiring any partitioning of the network or prior structural knowledge.\n\nWe appreciate the reviewer’s suggestion and will revise the paper to explicitly contrast our approach with graph-cluster-randomization, especially in terms of assumptions, applicability, and theoretical guarantees. We will also clarify that while both methods aim to manage interference using clustering techniques, our approach is tailored to online learning and regret minimization in the presence of adaptive treatments and unknown graphs.\n\nWe are eager to know whether there are remaining questions. We will address it for the first time and hope for an opportunity to raise the score~ \n\n**References:**\n\n[1] A Multi-Armed Bandits with Network Interference, Abhineet Agarwal, Anish Agarwal, Lorenzo Masoero, Justin Whitehouse; \n\n[2] Multi-Armed Bandits with Interference, Su Jia, Peter Frazier, Nathan Kallus\n\n[3] Multi-armed Bandit Experimental Design: Online Decision-making and Adaptive Inference, David Simchi-Levi, Chonghuan Wang.\n\n[4] An empirical investigation of taxi driver response behavior to ride-hailing requests: A spatio-temporal perspective\nKe Xu,Luping Sun,Jingchen Liu ,Hansheng Wang\n\n[5] Causal Inference Under Approximate Neighborhood Interference\nMichael P. Leung\n\n[6] Graph Neural Networks for Causal Inference Under Network Confounding, Michael P. Leung, Pantelis Loupos\n\n[7] Bandit Algorithms, Tor Lattimore and Csaba Szepesvari\n\n[8] An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits, Biyonka Liang and Iavor Bojinov\n\n[9] Cluster-Adaptive Network A/B Testing: From Randomization to Estimation, Y Liu, Y Zhou, P Li, F Hu\n\n[10] Causal clustering: design of cluster experiments under network interference Davide Viviano, Lihua Lei, Guido Imbens, Brian Karrer, Okke Schrijvers, Liang Shi\n\n[11] Linear Contexual Bandit with Interference, Yang Xu, Wenbin Lu, Rui Song"}, {"review_id": "Ga9pzUjDIG", "reviewer": "Reviewer_cd13", "summary": "This paper studies sequential experimental design under network interference. The core contribution is to introduce a multi-armed bandit framework (\"MAB-N\") that incorporates arbitrary exposure mappings and allows the researcher to formalize trade-offs between estimation precision (for causal effect estimands, here ATE across exposure arms) and regret minimization (i.e., reward optimization for the experimental population). The authors define a family of exposure mappings generalizing existing designs (e.g., global proportion, cluster-randomized Bernoulli, unit-level assignments), define the feasible super-arm space induced by these mappings, and study a minimax trade-off problem indexed by time horizon T and number of exposure arms |UE|. They provide a lower bound on the product of regret and estimation error, and propose an algorithm (UCB-TSN) that achieves matching upper bounds. The result is extended to an adversarial bandit setting using an EXP3-based variant.", "questions": "1. The regret bounds scale in $\\sqrt{|\\mathcal U_{\\mathcal E}| T}$, and the estimation error scales in $\\sqrt{|\\mathcal U_{\\mathcal E}| T_1}$. Is there any way to adaptively choose $T_1$ based on online variance estimation or confidence bounds on $\\hat \\Delta$, rather than fixing $T_1$ ex ante?\n\n2. Can the exposure mapping $S(\\cdot)$ be learned or optimized from data? For example, if the mapping $S$ is unknown but satisfies some low-complexity/interference structure (e.g., depends only on local neighborhoods), could one select among candidate exposure mappings to improve trade-off performance?\n\n3. Are there settings where the optimal action under full-information differs across units (i.e., no single exposure arm $S^*$)? The regret definition assumes a globally optimal $S^*, but in general with interference, optimal actions may be heterogeneous across clusters or individuals.\n\n4. In what sense does this framework allow generalization to real-world experiments? Can the authors describe a concrete application (beyond simulations) where the proposed UCB-TSN or EXP3-TSN could be used in practice, with a discussion of what assumptions would be required to justify the exposure mapping used?\n\n5. There is no empirical comparison on realistic graphs or real-world networks. Are the conclusions robust to heterogeneous degree distributions or violations of the exposure mapping assumptions (e.g., exposure misclassification due to incomplete network information)?", "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:\n\n1. The paper is clearly and accurately situation in relation to the most relevant literature. You can tell the authors are well-read up on this research area.\n\n2. The framework appears to be modular and flexible, unifying several previously distinct formulations (cluster-randomized experiments, global interference designs, local neighborhood exposure mappings) via an abstraction based on exposure mappings. The distinction between the original super arm space and the reduced exposure arm space is clearly formalized.\n\n3. The core trade-off result (Thm 1) is interesting and seems to extends prior work on estimation-regret trade-offs (e.g., Simchi-Levi & Wang 2024) to the interference setting and general exposure mappings. \n\n\nWeaknesses:\n\n4. The paper’s contribution is primarily in generalization, not in introducing fundamentally new algorithmic or statistical ideas. The key trade-off result follows a similar form as existing results in the non-interference setting. While extending it to interference is nontrivial, the conceptual gain beyond the generality of the exposure mapping is somewhat limited. In particular, there is no significant conceptual advance in interference-aware estimation itself; rather, the interference structure is encoded in the exposure mapping and treated as black-box from that point onward.\n\n5. The algorithmic contribution is not obvious to me. The UCB-TSN algorithm is essentially UCB run after a fixed exploration phase over the exposure arms. The EXP3-TSN algorithm is only briefly sketched and seems to follow standard ideas. There is no adaptive or data-driven tuning of the exposure mapping, and no exploration of what happens when the exposure mapping is misspecified or learned.\n\n6. The claim of \"bridging estimation and regret via Pareto-optimality\" is slightly overstated. The definition of Pareto front (Definition 1) is not operationalized in the design of the algorithm. In practice, it seems to me the user still has to pick $T_1$ manually. There is no procedure that selects the allocation adaptively based on observed data to balance the objectives. So while the theory is elegant, its practical impact may be limited. Please correct me if I missed something.\n\n7. The writing could be improved. For one, it is sometimes a bit too abstract. For example, the formal definition of the Pareto front (Def 1) is not necessary; the concept could be explained more directly in terms of a constrained optimization trade-off. Similarly, the distinction between different exposure mappings is clear but not especially novel. The generality could be preserved with a shorter exposition. Second, the paper would benefit from removing some material in exchange for providing more intuition and dividing up their paragraphs into multiple shorter ones. It is quite tough to read as-is.\n\n8. The exposition of key assumptions is vague in some parts. For example, it is not clearly stated whether the exposure mapping $S$ is assumed to satisfy some form of partial interference (e.g., unit i’s outcome depends only on the treatment assignments of units in a neighborhood of i). This may be needed for identification, especially if $|\\mathcal U_{\\mathcal E}|$ is to be small relative to $KN$. The discussion of Condition 1 $(2 \\leq |\\mathcal U_{\\mathcal E}| \\leq T)$ is too brief and gives the impression that the exposure mapping can be chosen arbitrarily, without concern for identifiability.", "was_revised": true, "final_justification": "No change to score, I remain recommending Accept", "rebuttal": "Thanks! We address the comments point by point, referring to ``Supplementary Material.zip``.\n\n >***Q1:  Contribution is primarily in generalization.***\n---\n**Answer:** Thank you sincerely for this appreciative summary and the generous evaluation. As you noted, 1 we **include prior works as special cases** within our exposure‑mapping generalization; 2 we **tackle previously unaddressed scenarios**, especially in the presence of network interference. These generalizations introduce new technical hurdles (see ``Reviewer 9HaH Q1``). Despite this, our results remain sharply non-trivial, and even in the degenerate case $N=1$, our lower- and upper-bound conclusions notably improve upon classical bandit results (again see ``Reviewer 9HaH Q1``).\n\n\n> ***Q2: The algorithmic contribution should be explained. There is no adaptive or data-driven tuning of the exposure mapping, and no exploration of what happens when the exposure mapping is misspecified or learned.***\n---\n**Answer:** 1. A flexible two-phase framework. Instead of proposing a single algorithm, we introduce a general framework that separates uniform exploration (Phase I) from regret minimization (Phase II). This design allows standard optimal regret minimization algorithms (e.g., UCB, EXP3, TS) to be plugged in directly, making the approach easy to implement and broadly applicable. In contrast, prior work such as Simchi-Levi and Wang [2024] relies on an exploration strategy tightly tied to EXP3, which is hard to generalize.\n2. Better suited for networked settings. In network setting, the exposure action set $\\mathcal{U}_E$ captures the combinatorial structure induced by both the number of arms $K$ and the network topology (e.g., node degrees and interference patterns), making $\\mathcal{U}_E$ a central quantity in our analysis. Simchi-Levi and Wang [2024] proposed an algorithm with regret and estimation bounds $R(T, \\pi) = \\tilde{O}(K^5 + T^{1 - \\alpha})$ and $e(T, \\hat{\\Delta}) = \\tilde{O}(K^2 T^{\\alpha/2 - 1/2})$, which depend heavily on $K$. While such dependence may be acceptable in the networkless setting (where $K$ is small), it becomes problematic in our case. As a result, directly extending Simchi-Levi and Wang [2024]’s algorithm to our setting would be inefficient. Our two-phase framework yields bounds $R(T, \\pi) = \\tilde{O}(\\sqrt{\\mathcal{U}_E T} + T_1)$ and $e(T, \\hat{\\Delta}) = \\tilde{O}(\\mathcal{U}_E / T_1)$, which are significantly more scalable and less sensitive to the size of the action space. This makes our design more suitable for large networked environments.\nWe will further discuss adaptive tuning in A3 and A6, and discuss the case of misspecified exposure mappings in A10.\n\n\n> ***Q3: The claim of \"bridging estimation and regret via Pareto-optimality\" is slightly overstated. Please correct me if I missed something.***\n---\n**Answer:** Thanks! We agree and have revised our claim accordingly to emphasize that we provide a theoretical characterization of the trade-off between estimation and regret via Pareto optimality. The two-stage form in our design is primarily for conceptual clarity. In practical applications, users do not necessarily need to pre-specify a fixed $T_1$; the allocation between uniform exploration and regret minimization can be chosen based on real-time feedback. For instance, in a networked decision-making setting, one may begin with regret minimization if the observed responses from early nodes indicate high sensitivity or urgent performance demands—prioritizing actions known to yield good outcomes. As the learning process progresses and the remaining nodes exhibit more stable or less sensitive behavior, the algorithm can gradually shift toward uniform exploration to improve the estimation of treatment effects across the network. We will provide more details on the implementation of our proposed approach in A9 and A10.\n\n>**Q4: The writing could be improved.**\n---\n**Answer:** In the revised version, we have replaced the abstract Definition 1 with a constrained‑optimization perspective, explaining the Pareto front in plain terms as “the set of allocation strategies that maximize regret reduction subject to a lower bound on estimation accuracy.” We illustrate this with a clear numerical example: starting from an extreme policy that minimizes regret, we show step-by-step how gradually relaxing its statistical power constraint traces out the Pareto curve, highlighting how UCB‑TSN selects optimal operating points. Elsewhere, we have removed redundant exposition on exposure mappings, grouping equivalent mapping types into a compact table and focusing on representative examples to retain clarity without verbosity. Paragraphs throughout were split into shorter units.\n\n\n>**Q5: The exposition of key assumptions is vague in some parts.**\n---\n**Answer:** We have provided more justifications for the assumptions. For instance, the exposure mapping could be assumed to be chosen as just neighbourhood-sensitive (but not forced to be), as illustrated on page 5 (Example iv). We provide more comparisons with previous literature in the paragraph in Table 1 in Appendix C. We would like to emphasize that our definition of the exposure-arm action space is flexible and freely chosen. Even if $\\mathcal{U}_{\\mathcal{E}}$ is relatively small (e.g., \nO(KN)), so that it might appear incapable of covering all conceivable treatment patterns, our theorems still guarantee optimal arm selection (among limited candidates) and the best achievable trade‑off with statistical power. In other words, adjusting the granularity of the exposure-arm space effectively mediates the trade‑off between computational complexity and search bias: finer granularity (cluster = N) reduces bias toward the true optimal arm but increases complexity, while coarser granularity reduces complexity at the cost of potential bias—our framework explicitly quantifies this balance in the revised version.\n\n>**Q6:**  Is there any way to adaptively choose $T_1$ based on online variance estimation or confidence bounds on $\\hat{\\Delta}$, rather than fixing $T_1$ *ex ante*?\n---\n\n**Answer:** One promising direction is to leverage asymptotic confidence sequence (CS) techniques, which provide confidence intervals that remain uniformly valid over time. Unlike traditional confidence intervals—which are constructed at a fixed time $t$ and only guarantee coverage at that specific point—a confidence sequence is a sequence of intervals $\\{[L_t, U_t]\\}_{t=1}^\\infty$, each based on data observed up to time $t$, such that the entire sequence simultaneously covers the true parameter (e.g., ATE) with high probability (e.g., $1 - \\delta$). This property enables continual inference: the learning algorithm can monitor the width of the CS in real time and adaptively decide whether to increase exploration, reduce exploration, or terminate learning.\n\nIn our learning setting, it is possible to construct a valid asymptotic CS for each ATE and adjust the exploration strategy based on the CS width. Similar ideas have been explored in the networkless setting, for example by Liang et al. (2023), and we believe that a similar approach could be extended to our setting. While promising, we did not pursue this direction in the current paper, as incorporating CS-based adaptivity would entail non-trivial changes to our current framework. We leave this as an interesting avenue for future exploration.\n\n\n\n>**Q7: Can the exposure mapping $S(\\cdot)$ be learned or optimized from data?**\n---\n**Answer:** Thanks for pointing out this future work! Due to the flexibility of our framework, learning or optimizing the exposure mapping from data is both feasible and promising. Recent work such as EgoNetGNN (Adhikari et al., 2025) automatically learns exposure mapping functions via GNNs, enabling modeling of complex peer influence that depends on neighborhood structure and edge attributes. Guided by this, we further design a pipeline where a candidate set of low-complexity exposure mappings (e.g. distance-weighted, temporal accumulation, directionality) is evaluated online using variance-based confidence estimates or cross-validation, and the best-performing mapping plugged into our regret/statistical trade-off framework. We have added it in the revised version.\n\n>**Q8: Are there settings where the optimal action under full-information differs across units (i.e., no single exposure arm, the regret definition assumes a global optimal $S^*$, but in general, with interference, optimal actions may be heterogeneous across clusters or individuals.**\n---\n\n**Answer:** In our setting, we assume the existence of a unique best super arm $S^*$, which is defined as the one that maximizes the average reward across all units. This follows the objective considered in prior work (i.e., Jia et al., (2024), Agarwal et al., (2024)) that we build upon. We do not aim to optimize individual unit-level (or cluster level) rewards, but rather the population-level average reward. We acknowledge that in some instances, the globally optimal super arm defined in our paper may not maximize the reward for each individual unit/cluster.\n\n>**Q9: In what sense does this framework allow generalization to real-world experiments? Can the authors describe a concrete application (beyond simulations) where the proposed UCB-TSN or EXP3-TSN could be used in practice, with a discussion of what assumptions would be required to justify the exposure mapping used?**\n---\n**Answer:** Refer to ``Reviewer 4t1F Q1 (part 3)``.\n\n>**Q10: Empirical comparison on realistic graphs or real-world networks. Are the conclusions robust to heterogeneous degree distributions or violations of the exposure mapping assumptions (e.g., exposure misclassification)?**\n---\n**Answer:** The realistic graph refers to  ``Reviewer 4t1F Q1 (part 3)``, and the approximation/robustness analysis under misspecification error could refer to Appendix N, and we provide sensitivity/misspecification analysis in ``Reviewer aj54``."}]

Author rebuttal:

Meta-review: This paper introduces a framework for online experimental design under network interference that uses exposure mapping to achieve a Pareto-optimal trade-off between estimation accuracy and regret. The authors should include a candid discussion of limitations, particularly addressing Reviewer 4t1F concerns about the experimental paradigm and the restrictive assumptions on the network topology.
Decision: Accept (poster)