Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits
Authors: Su Jia
Peter I. Frazier
Nathan Kallus
Venue: ICML 2025 poster (2025)
Keywords: interference
adversarial bandits
high-probability regret bound
Primary area: theory->online_learning_and_bandits
TL;DR: We study a multiple-play adversarial bandits problem where the reward of a unit depends on the arms of ALL units

Abstract: Experimentation with interference poses a significant challenge in contemporary online platforms. Prior research on experimentation with interference has concentrated on the final output of a policy. Cumulative performance, while equally important, is less well understood. To address this gap, we introduce the problem of Multi-armed Bandits with Interference (MABI), where the learner assigns an arm to each of $N$ experimental units over $T$ rounds. The reward of each unit in each round depends on the treatments of all units, where the interference between two units decays in their distance. The reward functions are chosen by an adversary and may vary arbitrarily over time and across different units. We first show that the optimal expected regret (against the best fixed-arm policy) is $\tilde O(\sqrt T)$, and can be achieved by a switchback policy. However, the regret (as a random variable) for any switchback policy suffers a high variance, since it does not account for $N$. We propose a policy based on a novel clustered randomization scheme, whose regret (i) is optimal in  expectation and (ii) admits a high probability bound that vanishes in $N$.

Multi-Armed Bandits with Interference: Bridging Causal Inference and Adversarial Bandits
Su Jia Peter Frazier? 2
Nathan Kallus²
2
Abstract
Most previous work on experimentation with interference focused on the quality of the final output, such as the mean- squared error of the estimator (e.g., Ugander et al. 2013) or p-value (e.g., Athey et al. 2018). On the other hand, the cumulative performance is also important in practice, considering the scale of experiments modern platforms, but this perspective is often overlooked.
Experimentation with interference poses sig- nificant challenge in contemporary online plat- forms. Prior research on experimentation with interference has concentrated on the final out- put of policy. Cumulative performance, while equally important, is less well understood. To address this gap, we introduce the problem of Multi-armed Bandits with Interference (MABI), where the learner assigns an arm to each of N experimental units over T rounds. The reward of each unit depends on the treatments of all units, and this dependence decays in distance. The re- ward functions, chosen by an adversary, may vary arbitrarily over space and time. We first show that switchback policy achieves an optimal expected regret of ((VT) against the best fixed-arm pol- icy; however, the regret as a random variable suf- fers high variance. We propose a policy based on a novel clustered randomization scheme, whose regret (i) is optimal in expectation and (ii) admits pigb-probability bound that vanishes in N.
This motivates us to study cumulative reward maximization in A/B testing with interference. We employ a batched adversarial bandits framework. Given a set U S R of N wnits representing, for example, users in an online platform, each with a known, fixed location. We are also given set [k] == (1...., k) of arms and a time horizon with T rounds. In each round, the learner assigns one arm to each unit and collects an observable reward, governed by a reward function secretly chosen by an adversary beforehand.
To capture interference, the mean reward of each unit de- pends on the treatments of all units. Formally, this means that each reward function is defined on [K]* instead of on [k] (as in ordinary bandits). Similarly to causal inference with interference, efficient learning is impossible without ad- ditional structures. In this work, we employ a rather general assumption from Leung 2022 that the unit-to-unit interfer- ence decreases in their distance. Specifically, for any two treatment assignments 2, z' E [k]]** if they are identical on neighborhood of U, then their rewards on u are close; Moreover, the larger this neighborhood, the closer they are.
1. Introduction
A/B tests have become a standard practice to evaluate the impact of a new product or service change before vide-scale release. A naive A/B test may fail in the presence of inter- ference, i.c., the Stable Unit Treatment Values Assumption (SUTVA, Rubin 1978) is violated, where the treatment of one unit affects the outcome of another. For example, if ride-sharing firm assigns half of the drivers to new pricing algorithm, these drivers will alter their behaviors, which impacts the common pool of passengers, and consequently the drivers not assigned the new algorithm.
On the technical level, we build upon the EXP3 framework for adversarial bandits, integrating with a novel Horvitz- Thompson estimator with Implicit eXploration (HT-IX). By choosing different hyperparameters, this estimator "inter- polates" between the estimator for the average treatment effect (ATE) under spatial interference (Leung, 2022) and for the unobserved rewards in adversarial bandits (Kocák et al., 2014; Neu, 2015).
CCetter for Data Science for Enterprise and Society, Cornell University "School of Operations Research and Information En- gineering. Cornell University. Correspondence to: Su Jia <ji- asu 222112252@mmm 1e25@@mmal.comm.
From a practical standpoint, a "pure" switchback policy where the entire system switches between treatment and control -ntrrl--iss is rarely used in practice. Instead, platforms typ- ically partition the space into clusters and independently assign treatment or control to each cluster in each period; see, e.g., DoorDash's 's "clustered" switchback experiments
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Multi-Armed Bandits with Interference
(Sneider and Tang, 2019). This is precisely the class of policies that we analyze in this work. Thus, a key contribu- tion of our work is to provide theoretical justification for policy class widely used in industry.
lenge, the violation of the SUTVA has been viewed as prob- lematic for online platforms (Blake and Coey, 2014). This problem has been extensively studied in statistics (e.g., Hud- gens and Halloran 2008; Aronow and Samii 2017; Eckles et al. 2017; Basse and Feller 2018; Basse et al. 2019; Li and Wager 2022; Hu et al. 2022: Leung 2023; Hu and Wager 2022), operations research (e.g.. Johari et al. 2022; Bojinov et al. 2023; Farias et al. 2022: Holtz et al. 2024; Cando- gan et al. 2024; Jía et al. 2023a), computer science (e.g.. Ugander et al. 2013; Saveski et al. 2017: Ugander and Yin 2023; Yuan et al. 2021) and medical research (Tchetgen and VanderWeele, 2012). Some recent surveys include Bajari et al. 2023; Larsen et al. 2023.
1.1. Our Contributions
We contribute to the literature in the following ways. 1. Bridging Adversarial Bandits and Causal Inference. We incorporate interference into MAB by formulating the problem of Multi-Armed Bandits with Interference (MABI). The ordinary MAB can therefore be seen as a special case of MABI under SUTVA. Our formulation is fairly general, imposing no constraints the non-stationarity or hetero- geneity in reward functions between units. At the heart of our policy is an estimator that generalizes the estimators of (1) Kocák et al. (2014) for deriving high-probability re- gret bound in adversarial bandits and (2) Leung (2022) for estimating treatment effects under spatial interference.
Many works tackle this problem by assuming that interfer- ence is summarized by a low-dimensional exposure map- ping and that units are individually randomized to treatment or control by Bernoulli or complete randomization (Man- ski, 2013; Toulis and Kao, 2013; Aronow and Samii, 2017; Basse et al., 2019; Forastiere et al., 2021). To improve es- timator precision, some work departed from unit-level ran- domization and introduced cluster correlation in treatment assignments. This usually done by either (i) grouping the units in network into clusters (Ugander et al., 2013; Jagadeesan et al., 2020; Leung, 2022; 2023) or (ii) group- ing time periods into blocks ("switchback") (Bojinov et al., 2023; Hu and Wager, 2022; Jia et al., 2023a). However, these works usually focus on the quality of the final output, such as the bias and variance of the estimator (Ugander et al., 2013; Leung. 2022) and p-values for hypothesis test- ing (Athey al., 2018).
2. Optimal Expected Regret. We show that a switchback policy has an optimal (up to log terms) ((VkT) expected regret. Moreover, we also show that for any (possibly non- switchback) policy, there is a MABI instance on which it suffers an S2( / /T) expected regret. Notably, this suggests that a large N does not help reduce the expected regret.
3. High-probabilityy Bound. Although the regret (as a random variable) of switchback policy may be optimal in expectation, it can suffer high variance. To address this, we propose a policy that integrates the following components. a) Randomized Clustered Randomization. We introduce the Robusl Random Partition (RRP) where we perturb the cluster boundaries randomly. This increases the exposure probability from (1) to (p)) This reduces the variance caused by the specific clustering chosen for cluster random- ization.
While existing literature has primarily focused on the final output, the cumulative performance remains less well under- stood. A natural framework is multi-armed bandits (MAB) (Lai et al., 1985). These works focus on the cumulative per- formance but often overlook the interference element. There are three lines of work in MAB that are most related to this work: (i) adversarial bandits, (ii) multiple-play bandits and (iii) combinatorial bandits.
b) Estimator. Our HT-IX estimator adds implicit explo- ration (IX) parameter (Kocák et al., 2014) into the propen- sity score of the Horvitz- Trriiii--Thopoonn (HT) estimator. This reduces the variance caused by unbalanced weights over the treatment arms
Particularly related is the adversarial bandit problem. Many policies for adversarial bandits are built on the idea of weight update (Vovk, 1990; Littlestone and Warmuth, 1994), first introduced for the full-information setting (i.e., the best expert problem). Auer al. (1995) considered the bandit feedback version and proposed forced exploration version of the EXP3 policy. Stoltz (2005) observed that the policy achieves the optimal expected regret even without additional exploration.
We show that the EXP3 policy based (1) the RRP design and (2) the HT-IX estimator has optimal expected regret. Moreover, the tail mass of the regret vanishes as N - oc. In stark contrast, this result is not possible for any switchback policy, as the tail mass of the regret does not depend on N. This result is crucial for practical applications, as market size Ni is typically orders of magnitude larger than T.
1.2. Related Work
bigshbrobabblity bounds for adversarial bandits were first provided by Auer et al. (2002) and explored in a more generic way by Abernethy and Rakhlin (2009). In particu- lar, the idea to reduce the variance of importance- estimators has been applied in various forms (Ionides, 2008;
Experimentation is a widely deployed learning tool in on- line commerce that is easy to execute (Kohavi and Thomke, 2017; Thomke, 2020; Larsen et al., 2023). As a key chal-
2

---

Multi-Armed Bandits with Interference
Bottou al., 2013) and was first introduced bandits by Kocák et al. (2014). Subsequently, Neu (2015) showed that this algorithm admits high-probability bounds.
As in adversarial bandits, we aim to control the loss com- pared the best fixed arm. When N 1, our notion of regret is the same as in adversarial bandits.
Another closely related line is multiple-play bandits (Anan- tharam et al., 1987), where the learner plays multiple arms per round and observes each of their feedback. The number of arms played in each round can be viewed as the "N in our problem (Chen et al.. 2013; Komiyama et al., 2015; Lagrée al., 2016; Jia et al., 2023b). Another related line of work is multi-agent RL (Kanade et al., 2012; Busoniu et al., 2008; Zhang et al., 2021). Our problem differs in that each "agent" behaves completely passively.
Definition 2.1 (Regret). The regret of a policy Z is defined as Reg(2 2) := maxae[ki {Reg(Z, a)} where for each a e [k], we define
T =
Reg(Z,a)
Σ Σ t=1
1 N
(Ymrla- ) Yue Vur(Ze))
NE[N]
We focus on bounding the regret in expectation or, prefer- ably, in high probability. The reward functions are chosen "secretly" in advance in that our bounds on regret will hold for any reward functions (possibly subject to some con- straints we discuss next). Thus, the bounds hold even for the worst-case reward functions chosen by an adversary.
Finally, since the reward function defined on the hyper- cube [b]]* our work is also related to combinatorial bandits CCesa-Bianchh and Lugosi, 2012) where the action set is subset of binary hypercube. While most work in this area considers linear reward functions, in our work the re- ward functions are only assumed to satisfy the decaying interference assumption. A recent line of work focuses on combinatorial bandits with non-lincat reward functions. However, most of these works either assume stochastic setting (Agrawal et al., 2017: Kveton et al., 2015) or an ad- versarial setting with restrictive class of reward functions, such as polynomial link functions (Han et al., 2021).
Thus far, the model allows for unrestricted interference in that Yu (z) may vary arbitrarily in any coordinate of z. As in the literature of experimentation under interfer- ence, to derive meaningful performance guarantees, it is necessary assume certain structures on interference. The existing literature focuses the restrictions captured by x-neighborhood exposure mappings, which imply that the arm assigned to v (i.e., 2n) can only interfere with Yur if the distance between u, v is at most k, which is quite restrictive.
Most closely related is the concurrent work of Agarwal et al. (2024); Zhang and Wang (2024); Xu et al. (2024) on stochastic bandits with interference. Specifically, the reward each unit is determined by a stationary reward function. With stationarity, they can adopt stronger bench- mark, e.g., Agarwal et al. (2024) chose the best "personal- ized" treatment assignment, as opposed to the best uniform treatment assignment in our work. However, our framework is more general in two ways: (1) the reward functions can be non-stationary heterogeneous arbitrarily, and (2) we do not impose much structural assumptions (such as linear- ity) on the interference pattern; we only assume that the interference level decays in distance.
In many applications, the effect of a treatment diffuses pri- marily through physical interaction, such as a promotion a ride-sharing platform discount on food deliv- ery platform. Leung (2022) addressed this by proposing model that allows for interference between any two units, with an intensity that decays in the distance. The following is identical to that in their $2.1 (up to re-scaling).
Assumption 2.2 (Scaling of the Bounding Box, Leung 2022). There is by O(VN) s.t. U S [-by,by and d(u, v) 2 1 for any u, u E [N] where d is the sup norm.
Leung (2022) posits that if two assignments tical on ball-neighborhood of u, then the mean rewards of u under 2, 2' are close. To formalize, denote the radius- r (open) ball as B(u, = {v E [N] d(u, v) < r). For clarity, B(u,r) does not contain units that are ex- actly distance r away. In particular, B(u, 0) 0 and B(u, 1) = {u}.
x' =' are iden-
2. Formulation and Assumptions
We consider a multiple- play (i.e., multiple arms are played in each round) adversarial bandit setting. Consider a set of N units, T rounds and k treatment arms (or arms). For each round E [T] and unit u E [N] there is an unknown reward function Yue: [K]N + j0, 1] that can depend on the treatment assignment E [k:] N (not just 2.,).
Definition 2.3 (Decaying Interference Property). Let vb (0) + 10, oo) be non-increasing. A MABI instance satisfies the vi-decaying interference property (or (D-DIP) if for any r 2 0, E [N], E [T] and 2, E [K] with BB(,.)) 2'B(u.r)' we have
In each round I, the learner selects a trealment assignment Z, E [k] and observes a reward Yu, (Z,) for each u E [N] (i.e., bandit feedback). Specifically, the distributions we use to draw (Zx) form a policy which is, formally, sequence
[Yae()) Yue(z') S (T)).
([x) N j0, y A ((K)) where & = 1....,
Te
Remark 2.4 (Recovering SUTVA). Consider v(() = 1(r = 0). Then, for any 2, s' identical on B(u, 1) = {u) and r >
3

---

Multi-Armed Bandits with Interference
0 in Definition 2.3, we have (z) (01) O. Thus, (z) only depends on Su, which recovers SUTVA.
policy) regret of any policy is T/2, and (b) by a standard anti-concentration bound, w.h.p. there is fixed-arm policy with total reward T/2 + ((vT)..
3. Expected Regret
Challenge. At first sight, the proof seems to follow triv- ially from the lower bound of the best-expert problem (see, e.g., Section 4 of Arora et al. 2012), by assigning all units the same arm in each round. However, by doing so, the reward functions are defined only for 1 and 0% but we need to specify their values on the entire (0, 1 subject to the t DIP... As key step, we show that such extension is always possible:
We show that the minimax expected regret is Ö(vT). This holds for all N (not fixed as constant!). although N does not show up explicitly. This is not surprising due to the normalization factor 1/N in the definition of regret.
3.1. Upper Bound
We begin by observing that MABI is equivalent to advensar- ial bandits when we restrict ourselves to switchback policies, which selects the same arm for all units in each round. These policies are widely applied in practice (Sneider and Tang, 2019; Cooprider and Nassiri, 2023) and have been exten- sively studied (Bojinov et al., 2023; Hu and Wager, 2022; Xiong et al., 2023). Note that any adversarial bandit policy (Ac) induces a switchback policy (Z₂) where Z; = A - Moreover, this reduction preserves the regret:
Lemma 3.4 (Hypercube Extension). Let G = (V,E) the grid graph where V= (-m....... .m] {-m...... .., m) for some integer m. Then, for any non-increasing 1h RR +
R+, there is a function f 10, + [0, satisffving
i) the boundary condition: S(OK) = 0, and f(1)) =
(0) - {mm). and
ii) the DDDIPP: for any 2, E (0. 1)", if =(,,r) 2'1(0.))
for some r > O (where O = (0, 0)), then [f(z) ʃ(=')l S (r))
Proposition 3.1 (Reduction to Adversarial Bandits). Let (At) be an adversarial bandits policy with expected regret r(T). Then, the induced switchback policy (Zi) satisfies Reg( 2) (T)).
Proof. We construct f as follows. Step 1: Define f on Basis Vectors. For each r = 0,.... m, we define the basis vector o" E (0, 13 with entries
For adversarial bandits, the EXP3 ("EXPlore and EXPloit with EXPonential weights") policy has an Ö(VRT) ex- pected regret (Auer al., 1995), so:
of = 1(10 - 1l < <r), Vo V.
In particular, oº = ON and Tth = N. Define
Corollary 3.2. The EXP3-based switchback policy has ex- pected regret Ö(VKT)
f(o") = (0) - (r)), r= -=.....,m m.
Step 2: Extend f to {0, 10, For each E 10, 13V, define f()) = (()).(z)) where
3.2. Lower Bound on the Expected Regret
The meticulous reader may have noticed that Corollary 3.2 does not involve the market size N. This is because switch- back policies treat the entire system as whole, and do not involve N. Can we improve the bound by leveraging N using more complicated policies? The answer is no:
r2(2) = max(r 2 0: 2::00( = 1B(0,))
Note that f(o0)= (0) (0) =0 and f(o = x0(0)= 1b(m). and so (i) holds. To show (ii), fix any 2, 2, (0,1) For simplicity, we write r, ;= r2(2) and r. = (=()). W.l.o.g. we assume that r. S rf. Consider the largest ball B(O,p p) on which & and z' are identical, that is,
Theorem 3.3 (Lower Bound on the Expected Regret). Fix any non-increasing function tb with (0) = 1 and lim vxx) O. Then for any MABI policy Z, there exists a MABI instunce I satisfying the bDDIP and Assump-
p := = maxffr 2 0: 2B(O,)) = =
tion2 2.2 s.t. Reg(Z,T)= = =(VKTT.
Claim 3.5. p 2 r..
We will choose the units to be integer grid points U {-2/N, 2/N) x (-2/N, 2/N), which obviously sat- isfies Assumption 2.2. To highlight key ideas, let us assume k == 2. The extension to general l is straightforward.
Assuming the claim (whose proof is deferred to Ap- pendix B), we conclude that
I5(=) - -(='))) = 1()(()) - (b(+)) - (v)00) (+-)) = (rr)) -v(,))
High Level Idea. We will choose the k x T reward table as a random matrix with i.i.d. Bernoulli entries with means 1/2. We then argue that (a) the expected (over the randomness of the rewards and
S (r.)) S (p)).
where the last inequality is because s non-increasing.
4

---

Multi-Armed Bandits with Interference
Proof Sketch of Theorem 3.3. Recall that U (-2VN, 2 x (-2VN, 2vN). 2vN). Step I: Hypercube Extension. W.l.o.g, we assume (00)
selecting a, A, be the (random) arm selected, and Y, be its observed reward, then the estimate is
1 and (V = 0. Consider the interior units
YYy PEo 1(A, a) Yv.
Pia
Unt = (-VN, NN
EXP3 combines this estimator with the multiplicative weights algorithm, and achieves an optimal Ö(VKT) ex- pected regret against the best fixed arm.
For each E NUnin,, we set Yut- 0. For each u (Ug, Uy) E Nmt, apply Lemma 3.4 with /N and
However, the regret has high variance, potentially being linear in T w.p. (2(1); see Note in Chapter 11 of Latti- more and Szepesvári 2020. This is because the estimator in EXP3 can have a high variance. To address this, Kocák et al. (2014) introduced an implicit exploration ("IX"" term B > 0 in the propensity weight, which truncates the value of the estimator and reduces variance. Formally,
V= {uz- m, Ux + m3 x (uy m, " + m).
Denote by fu 10 - R2 the function constructed. Extend fi to {0, 13 so that the function value is solely determined by its restriction on V.
Step 3: Construct the reward function. Consider i.i.d. & ~ Ber(112) for t E [T]. Define the reward fune- tion Yz)(2) := 1/2 + (5r 55-3 ( fu()) where 2 E 10.1) By Lemma 3.4, (ue()) satisfies the 1/-IIP. Moreover,
1(A, =) Pto + 3
PIo
Y..
[x)] = 1 for any 2 E {0, 13.1 N, and so the expected reward of any policy is T/2.
2
Despite the extra bias, Neu (2015) showed that judicious selection of / leads to good h.p. bound: The regret is S Vlog 1/8 times the minimax regret, Ö(VkT), w.p. 1 88
Step 4: Applying anti-concentration bound. By stan- dard anticooncentration bound, the best fixed arm has a total expected reward of 7/2 + S((TT) It then follows that
The other key idea is clustered randomization. Leung (2022) considered a uniform partition of the plane into square clusters, and independently assigned arms to each cluster. Under this design, the truncated HT estimator achieves favorable bias-variance tradeoff, both vanishing in N.
T = =Ω =Q(VT)
E max Ro. R1)
2
4. High Probability Regret Bound
There are two main challenges in integrating the truncated HT estimator into the EXP3-IX framework. First, the uni- form spatial clustering in Leung 2022 not "robust" since some arms may have very low probabilities due weight updates, leading to high variance in the estimator. Further- more, it is unclear how to select the IX parameter in the batched setting due to heterogeneity across units. For exam- ple, units lying close to the boundary of a cluster should have different IX parameters compared to those in the "interior".
Although switchback policies can achieve optimal expected regret, their disregard for N prevents them from capitalizing on the market size. Consequently, the variance of regret (as a random variable) does not vanish as N grows, making these policies less appealing to practitioners. To address this, we propose a policy that (i) has Ö(VT) expected regret and (ii) admits a h.p.-bound that vanishes in N. Specifi- cally, for any T and confidence level 8 >> O, the tail mass above ((vT) vanishes N + co. Our policy integrates EXP3-IX from adversarial bandits and the idea of clustered randomization from causal inference.
The rest of this section focuses on addressing these chal- lenges. The key component of the HT estimator in Leung 2022 is the exposure mapping, which measures the "relia- bility" of the data observed from unit.
4.1. Background and Technical Challenges
The first key idea is implicit exploration in adversarial ban- dits. Policies for adversarial bandits often rely on weights update (Vovk, 1990; Littlestone and Warmuth, 1994). In each round, an arm is selected with a probability propor- tional to its weight, updated to incentivize choosing arms with historically high rewards.
Definition 4.1 (Exposure Mapping). We define the radius-r exposure mapping as X (2) ;= 1(2B(ur) = a B((rr))) For a random vector Z E [K]] the exposure probability is (Z) = IP [X uta (2) 1].
To control the variance. we prefer a high exposure probabil- ity. However, the exposure probabilities in a naive clustered randomization can be very low. We address this next.
However, with bandit feedback, we only observe the re- ward of the selected arm. EXP3 addresses this using an aeportance-weightee estimator for the rewards of all arms (Auer et al., 1995). In round i, let Pea be the probability of
'This does contradict the (expected) regret bound, since the regret against the hest fixed arm can be negative.
5

---

Multi-Armed Bandits with Interference
1)
Assign Si independently to Cij. C2+1,5 uniformly. Simi- larly, assign Stor to independently to Cij. C1,+11 uniformly. 3. Assign the Quads: Define the (1. j)-quad
I 1,J11
Qu = lil il + r] x Lie 7, je +r].
Shoo
Qij
je
Assign it to City C++1.5 C1s+1, C41,5+1 uniformly.
w.p.
w.p.g
Our clustering obtained by partitioning U uusing an RRP. Formally, let {Ciz} } be an (e, (RRP) of [o, vNJa. By abuse of notation, write [N] n C.
lu
Ciy. We will use the cluster- ing {Ciy 1 i,j S 6x/Lj. For each E [M] denote by Clu] S U the unique cluster that contains u. From now on, fr
- 1)
let us fix a pair of r 2 0 with 1 < l < by and 2r < l.
(4-11 11e
ie
(i + 1)e
The RRP enjoys the following nice robustness.
Figure 1. Illustration of the RRP. The black lines are the cluster boundary in the uniform clustering. We color the strips and quads green and red. We assign each strip to one of the two neighboring clusters; see Stj" (dark green). Finally, assign each quad (red) to one of the four nearby clusters with equal probabilities.
Proposition 4.2 (Robustness). P(B(urr) S Clu]] = 92(1).
To this, observe that since 6/2, the ball B(u, r) intersects at most 4 "regions" (i.e., interiors, strips or quads), Since each strip or quad is assigned to a cluster inddpne- dently, w.p. (1)) these regions are all assigned to the same cluster C. When this occurs, we have B(u,r) E Clu).
4.2. Robust Random Partition
IfT = 1 and we aim to estimate the ATE, uniform clustering works well. For example, in Leung 2022, by choosing r < 6/2 where É is the side length of the square clusters, each r-ball can intersect only 4 squares. Therefore, if we independently assign each cluster an arm a w.p. p= ((1)) (and some other arm w.p. - p), the exposure probability is psp = ((1), which is favorable for estimation.
The robustness boosts the exposure probability. In fact, our policy (to be defined soon) maintains weight for each arm and assigns a random arm to each cluster independently according to the weights. Crucially, when Pta is small, the exposure probability under our RRP is 22 ((Pta), which is much greater than the exposure probability (Pta)* under the uniform design (Leung, 2022). We will soon see how this helps reduce the variance of our estimator.
However, with weight updates, pz can be tiny. When this occurs, we almost remove all the data from units close to the cluster boundary, resulting in a high bias. For example, if the rewards are zero everywhere except near the boundaries, then our estimate 0 while the true reward is 2(1).
Remark 4.3. Our approach may resemble that of (Ugan- der and Yin, 2023). Their randomized graph clustered randomization (RGCR). While their randomized partition- ing works for an arbitrary graph, our approach explicitly requires embedding the units into Euclidean space. How- ever, this structure makes it easier to exploit the decay of interference with distance.
We address this by introducing randomness into the parti- tion. We start with uniform clustering and then randomly assign units close to the boundary to nearby clusters. To for- malize, recall from Assumption 2.2 that U C 10, by]2 where by = O(VN). For any l and r < f/2, an rrrbust ran- dom partition (RRP) II = [Cig 1 < i.j & by/E} is defined as follows:
4.3. HT-IX Estimator and Our Policy
In adversarial bandits, the key to designing a good pol- icy is estimating the unobserved reward. More explic- itly, we need to find a good estimator for the mean re- wards {Ei(a 1 [eE])] where we recall that Y.(2) = EvE(N Yue Ideally, a good estimator enjoys both low bias and low variance. Neu (2015) showed that in- corporating an additional IX parameter into the propensity weight leads to a favorable h.p. regret bound. In our MABI problem, the propensity weights Quta can vary across units. However, a uniform IX parameter suffices for our result.
1. Assign the Interiors: Define the (i.j)-inttrion -interior as
Ty [i 1)e + r, il - r| x [(j - 1)E + r, je- r]
We assign Lij to Cij w.p. 1.
2. Assign the Strips: Define the vertical (i.j)-strip
She = [if - + x [0i - 1)8 + r, je- - r).
and the horizontal (i.j)p
Definition 4.4 (Horvitz- Serviiz-Thompson--e Estimator). Fix an IX parameter 3 E (0, Suppose the design
shor -ii-- - (()- + r, il- - r] x [ie- - r, je + r].
6

---

B bounds the tail mass of the regret which vanishes as Multi-Armed Bandits with Interference
Algorithm 1 EXP3-HTIIX Policy
4.4. A High-probability Regret Bound
1: Input:
Denote by R -E n EuEIN] (ue(Z)) the reward of policy (Z)). To compare against a fixed arm, also define
n E (0, 1): learning rate,
3 [0, 5): IX parameter for the HT-IX estimator,
(E, r): parameters for the RRP.
2: Wia t for each a E [k]
Ra Σ (((a)
3: for = 1....,, do
4: W, Ene W'
I/ Total weights
5: For each arm a E [k], let Pta +- Wto/W, W
where
6: Randomly generate HI, an (C,r)-RRP
(((a) = N
Σ MEIN]
Yuela 1
7: for cluster C E II, do
8: Draw arm Zc: using (Pia)aE(k)
Theorem 4.6 (High-probabilityy Bound). Fix any IX pa-
9: for u E C' do
rameter B (0, () and learning rate 17 E (0, 1) in Algo-
10: Zue + -cc Assign arm A to all units in C
rithm 1. Then, for any a" E [K] and 5 E (0, 1), we have
11: end for
R - Ra. A B + C w.p. 1 1 where
12: end for
13: Observe the rewards
log k
1
1 log
14: for a [K| do
A <
+ nKT,
B B
nKI
15: Pi(a)= t N Ene(N
(x,))(2)111 Q +
(Z,)
n
N
16: W Waa
1/ Weight update
and
17: end for
rT + )
T 3e (().
18:
end for
C CS BKT
We will soon see that with suitable parameters:
Z: E [K|N is drawn from a distribution D.2 Denote Vuta = PZ (Xuta (Z,) 1). For any L, a, the Horvitz- Thompson-IX (HT-IX) estimator is
A becomes the minimax expected regret ((v KT),
N xo, and
P((a):
1 N
Σ ME[N]
1(X 11)
Yuel (Z,).
Vuta +33
C bounds the lower order terms.
We illustrate the importance of Theorem 4.6 via several corollaries. To minimize A, choose 1j = /log k/kT. The choice for 3 is more involved. With some foresight, let us choose 3 = v ANT log 1 5- To highlight the excess beyond the "necessary" regret, we denote RegopT == VKTllgg k as the order-optimal expected regret.
Remark 4.5 (Unifying Known Estimators). When 9 = 0, HT-IX becomes the HT estimator in Leung 2022; When N = 1, it becomes the estimator in EXP3-IX of Neu 2015.
We now informally describe our policy (Algorithm 1). in- volves two parameters: The learning rate 17 (0, 1), which controls how quickly we discount past data, and the IX parameter B E [0, which truncates the HT-IX estima- tor by 1/3. In each round, we independently generate an (e, RRR. Then, we randomly assign an arm to each clus- ter independently, using the distribution determined by the weights. Finally, for each arm, use the HT-IX estimator to estimate the counterfactual reward that could have earned if we assigned it to all units in this round. We update the arm weights using the estimated rewards.
We first consider the no-interference setting. In this case, problem is equivalent to the multi-play (i.e., play N arms in each round) variant of adversarial bandits. Since there is no interference, we will choose the singleton clustering (i.e., where each unit alone is a cluster).
This clustering can be realized an (4,r)-RRP for suitable and r. In fact, recall from Assumption 2.2 that d(u, v) > 1 for any u, v E [N]. Therefore, if we partition the bounding box [0, b)2 uniformly into squares of sufficiently small side lengths E, then each square contains at most one unit in U. Thus, the (f. RRPP is just the singleton clustering (whenever r < f/2). Finally, noting that vi(r) = for any and hence C $ 3KT + o(1) as - 0+, we obtain:
2 Mooe concretely, we will later choose D to be clustered-level randomization, that is, assign random with a probability proportional to its weight.
each cluster drawn
7

---

Multi-Armed Bandits with Interference
Corollary 4.7 (No Interference). Suppose (x) 1(x 0). Then, there exists fr s.t. the regret R of the EXP3-IX- HT with the (L, r)RP satisfies
4.5. Discussion: Interpretation in VaR
5-VaR EXP3-SB, 6=e"
5-VaR EXP3-SB, 0
5aR EXP3-IX-HT, 6
R R S
1+
log
RegoPT
(1)
VaR Regret (N
VaR of EXP3 (T..XXXHT,C 0=="
-
w.p. 8 for every a' E [k] and 8 E (0, +)
T122
To better understand, recall that for adversarial bandits, the regret of EXP3-IX (1 /log 1/8) Regoor: see Chapter 12 in Lattimore and Szepesvári 2020. To the difference, take N T and 8 N this bound is O(log N Regorr). while (1) is O(ReSoPT) for any T.
Time Horizon T
Figure 2. VaR of Regret: We visualize the 8-VaR of regret for
e e and å = e - respectively. Here set = 1/2. Our randomztandooiiztiinn based policy has much lower VaR.
Another basic setting is x-neighborhood interference (Le- ung 2022; Bojinov et al. 2023) where the reward ("potential outcome") unit depends only on the treatments of the units within distance k > 0, i... (xx)) [[x z). In this case, by selecting K, the di terms become 0.
Switchback, 5
VaR Excess Regret (M
Switchsack, 5 5 N
2logN
Clustered candomaaation, 8 -
Clustered Randomzationn N
logN
Corollary 4.8 (x-Neighborhood Interference). Suppose (x) 1 (sx > 2) for some > 0. Then, with x and L NV T, for any a' [k] and 8 E (0, 2), we have
2N-10
N -N-1PlogN
T N
R - R z
1 |
log
RegoPT w.p. 5.
Number N of Units (Users)
Figure 3. VaR of Excess Regret: The figure visualizes the excess regret Reg RegopT that we can guarantee w.p.
Finally, consider the power law (r). This setting encom- passes many fundamental settings, including the celebrated Cliff-Ord spatial autoregressive model (Cliff and Ord, 1973), where each unit's outcome is linear in its neighbors' treat- ments.
By taking VI/KT in Theorem 4.6, our EXP3-I-HHT policy also achieves the optimal Ō expected regret. However, our policy has substantially lower tail risk com- pared to any switchback policy. To better illustrate, for concreteness, let us take N = T. Denote by Regsn and Reger the regret (as random variables) of any SwitchBack policy and our EXP3-IX-HI policy (where "CR" means "Clustered Randomization"), Then, by Theorem 4.6,
Corollary 4.9 (Power-law Interference). Suppose (r))= ( for constant e 2 1. Consider an RRRP with m min((N/T) s+0 N I b clusters (and hence é /N/m) and f/VT. Then, for any a" [k]] and 0 < 8 <
2. w.p. 1 8 we have
IP
RegsB
RegopT +log <
(3)
1 log
and
R Ra. S 1+
RegopT-
IP RegeR > Regorr NN !) 2
S (4)
For example, when 2, we have (N/ and
for any 8 > where is constant depending To highlight the tail mass, we rewrite Equation (3)
9/10
1
2 - -
V
log
(Regsb RegorT SE
(5)
N2/5
8

---

Multi-Armed Bandits with Interference
and
Peter M Aronow and Cyrus Samii. Estimating average causal effects under general interference, with application to social network experiment. 2017.
PP (RegcR RegopT > 7) S Se-
(6)
for any O.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multi- plicative weights update method: a meta- veeaaalgorithm and applications. Theory of computing. 8(1):121-16) 2012.
To see why Regen is more "robust", take T 72/3 and let T' range from 10 to 50. Then, the first probability in Equation (5) ranges from 2.7% to 0.01%, while the second astronomically small. For example, N = T and c= 1/2, ranges from 10-14 10-39.
Susan Athey, Dean Eckles, and Guido W Imbens. Exact p values for network interference. Journal of the American
Statistical Association, 113(521):230-22 240, 2018
More generally, consider 8 = e where > Then,
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 322-331. IEEE, 1995.
T
VsB- = Regort +T and VCR Regort
VT,
where "=" holds if N > T (as in the real world). When 1/2, the first bound is asymptotically larger.
Peter Auer, Nicolo Cesa- Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed ban- dit problem. SIAM journal on computing, 32(())48-77, 2002.
Acknowledgments. We thank Qin Chao, Wang Chi Cheung, and Christina Lee Yu for their valuable feedback.
Impact Statement
Patrick Bajari, Brian Burdick, Guido W Imbens, Lorenzo Masoero, James McQueen, Thomas S Richardson, and Ido Rosen. Experimental design in marketplaces. Sta- tistical Science, 38(3):458-47) 476, 2023.
We introduce the Multi-Armed Bandits with Interference (MABI) framework and focus on cumulative reward maxi- mization under spatial interference. Our work bridges ad- versarial bandits and causal inference, making it applicable to real-world systems such as online platforms and net- worked environments. Our cluster randomization based policy achieves near-optimal expected regret with high- probability bounds that improve the number of units increases. Unlike prior work, we do not rely stationarity or sparse interference.
Guillaume Basse and Avi Feller. Analyzing two-stage ex- periments in the presence of interference. Journal of the American Statistical Association, 113(521):41-55, 2018.
Guillaume W Basse, Avi Feller, and Panos Toulis. Ran- domization tests of causal effects under interference. Biometrika, 106(2):487-494, 2019.
Thomas Blake and Dominic Coey. Why marketplace experi- mentation is harder than it seems: The role of test-control interference. In Proceedings of the fifteenth ACM con- ference on Economics and computation, pages 567-582, 2014.
References
Jacob Abernethy and Alexander Rakhlin. Beating the adaptive bandit with high probability. In 2009 Informa- tion Theory and Applications Workshop, pages 280-289. IEEE, 2009.
Lavor Bojinov, David Simchi-Levi, and Jinglong Zhao De- sign and analysis of switchback experiments. Manage- ment Science, 69(7):355--3777, 2023.
Abhineet
Agarwal, Anish Agarwal, Lorenzo Masoero, and Justin Whitehouse. Multi-armed bandits with network interference. arXiv preprint 2rXiv:2405.18621 2024.
Léon Bottou, Jonas Peters, Joaquin Muinonero-Candele Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counter- factual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Conference learning theory, pages 76-78. PMLR, 2017.
Venkatachalam Anantharam, Pravin Varaiya, and Jean Wal- rand. Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part i: lid rewards. JEEE Transactions on Automatic Control, 32 (11):968-978) 1987.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement learn- ing. IEEE Transactions on Systems, Man, and Cybernet- ics, Part C (Applications and Reviews), 38(2):156-177 2008.

---

Multi-Armed Bandits with Interference
Ozan Candogan, Chen Chen, and Rad Niazadeh. Correlated cluster-based randomized experiments: Robust variance minimization. Management Science, 7066):406944086, 2024.
Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):295- 311, 2008.
Ravi Jagadeesan, Natesh S Pillai, and Alexander Volfovsky. Designs for estimating the treatment effect in networks with interference. 2020.
Nicolo Resa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78 (5):1404-1422, 2012.
Su Jia, Nathan Kallus, and Christina Lee Yu. Clus- tered switchback experiments: Near-optimal rates under spatiotemporal interference. arXiv preprint arXiv:2312.15574, 2023a.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages
151-159. PMLR, 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, 2023b.
Andrew David Cliff and J Keith Ord. Spatial autocorrelation. (No Title), 1973.
Joe Cooprider and Shima Nassiri. The science of price experiments in the amazon store. 2023. URL https: /tt////www./..// amazon. scwenceeebbbccccecce science of price experiments in- the
Ramesh Johari, Hannah Li, Inessa Liskovich, and Gabriel Y Weintraub. Experimental design in two-sided platforms: amarraaayy Management Science, 68(10):7069- 7089, 2022.
Dean Eckles, Brian Karrer, and Johan Ugander. Design and analysis of experiments networks: Reducing bias from interference, Journal of Causal Inference, 5(1):2015005) 2017.
Varun Kanade, Zhenming Liu, and Bozidar Radunovic. Dis- tributed non-stochastic experts. Advances in Neural In- formation Processing Systems, 25, 2012.
Vivek Farias, Andrew Li, Tianyi Peng, and Andrew Zheng. Markovian interference in experiments. Advances Neu- ral Information Processing Systems, 35:535-549 2022.
Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit exploration in ban- dit problems with side observations. Advances Neural Information Processing Systems, 27, 2014.
Laura Forasticre, Edoardo M Airoldi, and Fabrizia Mealli. Identification and estimation of treatment and interference effects in observational studies on networks. Journal of the American Statistical Association, 1 1166534)9001-118 2021.
Ron Kohavi and Stefan Thomke. The surprising power of online experiments. Harvard business review, 95(5): 82- 2017.
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Optimal regret analysis of thompson sampling stochas- tie multi-armed bandit problem with multiple plays. In International Conference on Machine Learning, pages 1 1152-1161. PMLR, 2015.
Yanjun Han, Yining Wang, and Xi Chen. Adversarial combi- natorial bandits with general non-linear reward functions. In International Conference Machine Learning, pages 4030-4039. PMLR, 2021.
David Holtz, Felipe Lobel, Ruben Lobel, Inessa Liskovich, and Sinan Aral. Reducing interference bias in online mar- ketplace experiments using cluster randomization: Evi- dence from a pricing meta-experiment on airbnb. Man- agement Science, 2024.
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- model. Advances in Neural Information Processing Systems, 29, 2016.
Yuchen Hu and Stefan Wager. Switchback experiments un- der geometric mixing. arXiv preprint arXiv:2209.00197, 2022.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):422,, 1985.
Yuchen Hu, Shuangning Li, and Stefan Wager. Aver- age direct and indirect causal effects under interference. Biometrika, 109(4): 165- 2022.
Nicholas Larsen, Jonathan Stallrich, Srijan Sengupta, Alex Deng, Ron Kohavi, and Nathaniel T Stevens. Statistical challenges in online controlled experiments: review a/b testing methodology. The American Staristician, pages 1-15, 2023.
Michael Hudgens and M Elizabeth Halloran. Toward causal inference with interference. Journal of the Ameri- can Statistical Association, 103(482):832-844 842, 2008
10

---

Multi-Armed Bandits with Interference
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Johan Ugander and Hao Yin. Randomized graph clus- ter randomization. Journal of Causal Inference, 11(1): 20220014, 2023.
Michael P Leung. Rate-optimal cluster-aaddmmized designs for spatial interference. The Annals of Statistics, 50(5): 3064-3087, 2022.
Johan Ugander, Brian Karrer, Lars Backstrom, and Jon Kleinberg. Graph cluster randomization: Network expo- sure to multiple universes. In Proceedings of the 19th ACM SIGKDD international conference Knowledge discovery and data mining, pages 529-337, 2013.
Michael P Leuug. Network cluster-robust inference. Econo- metrica, 91(2):441667, 2023.
Shuangning Li and Stefan Wager. Random graph asymp- totics for treatment effect estimation under network in- terference. The Annals of Statisties, 50(4):2334 2358, 2022.
Vladimir Vovk. Aggregating strategies. In Proceedings of 3rd Annu. Workshop on Comput. Learning Theory, pages 371-383, 1990.
Ruoxuan Xiong, Alex Chin, and Sean J Taylor. Data-driven switchback designs: Theoretical tradeoffs and empirical calibration. Available at SSRN, 2023.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108 (2):212-261, 1994.
Yang Xu, Wenbin Lu, and Rui Song. Linear contextual ban- dits with interference. arXiv preprint arXiv:2409. /5082, 2024.
Charles F Manski. Identification of treatment response with social interactions. The Econometrics Journal, 16(1): $1-S23, 2013.
Yuan Yuan, Kristen Altenburger, and Farshad Kooti. Causal network motifs: Identifying heterogeneous spillover ef- fects in a/b tests. In Proceedings of the Web Conference 2021, pages
Gergely Neu. Explore no more: Improved high-prohability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28. 2015.
2021.
Donald В Rubin. Bayesian inference for causal effects: The role of randomization. The Annals of statistics, pages 34-58, 1978.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi- agent reinforcement learning: A selective overview of the- ories and algorithms. Handbook of reinforcement learn- ing and control, pages 321-384, 2021.
Martin Saveski, Jean Pouget-Abadie, Guillaume Saint- Jacques, Weitao Duan, Souvik Ghosh, Ya Xu, and Edoardo M Airoldi. Detecting network effects: Ran- domizing over randomized experiments. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1027-1035, 2017.
Zhiheng Zhang and Zichen Wang. Online experimental design with estimation-regret trade-off under network interference. arXiv preprint arXiv:2412.03727, 2024.
Carla Sneider and Yixin Tang- Experiment rigor for switchback experiment analysis. 2019. URL httpp:///careersstooodeee com/blog/ experiment- rigor- for-
Gilles Stoltz. Incomplete information and internal regret in prediction individual sequences. PhD thesis, Université Paris Sud-Paris XI, 2005.
Eric Tchetgen Tchetgen and Tyler J VanderWeele. On causal inference the presence of interference. Statisti- cal methods in medical research, 21(1):55-75, 2012.
Stefan Thomke. Building culture of experimentation. Har- vard Business Review, 98(2):40-47,2000
Panos Toulis and Edward Kao. Estimation of causal peer influence effects. International conference on machine learning, pages 1489 1499.1497. PMLR, 2013.

---

Multi-Armed Bandits with Interference
A. Detailed Proof of Theorem 3.3
Recall that the construction we chose U = (-2/N, (-2/N, 2vN). By re-scaling, w.l.o.g, us assume that (0) and ( O. Consider the interior units
Unne == (-vN, (V
For each [nt. define Yu for all e [T]. To define the reward function for the interior units, for each [N]mn lin we apply Lemma 3.4 with m vN and
V {ug - m, uu + m3 x {uy - m, My + m),
where u = (ug, uy). Denote by fu 10. + R the function constructed in Lemma 3.4, and extend fu to {0, 1) so that the function value of u' is solely determined by restriction on V, formally,
fu = (w/lv, Vul E (0,1)*
By Lemma 3.4, fu satisfies the DDDIP and so fu also satisfies the d/-DIP.
Now, construct the reward function Yut. Consider i.i.d. variables & ~ Ber(1/2) where t [T). Define
1 Et ( fu(=), Vz {0, 10,
(=)
Then, by Lemma 3.4, (-)(-) satisfies the dDDIIP. Moreover, for any fixed E {0, 13%, we have [x)]]( Therefore, the expected reward of any policy is T/2.
Next, show that the best fixed-arm policy has total expected reward 7/2 2 R(VT), we need:
Lemma A.1 (Bernoulli Anti-concentration Bound). Let (Et)eet be i..dd Bernoulli variables with mean 1. and write T1,
< Σ & Then, for any 8 [0, 8 we have
T
1
16s
+
2
cxp
2
15
To conclude, let R. be the total reward of arm Consider the event E = {R1 2 T' +
vT.
Since R₃ is the sum of T i.idd.
Bernoulli's, by taking s V in Lemma A.1, we have [E] 15 Therefore,
T
T 2
E max ( Ro, R
max Ro. R
E P [
2
VT
VT
>
15
4
60
where the first inequality follows since max Ro, R1} >
T 2 a.s.
B. Proof of Claim 3.5
Consider cases. rf r', then the claim trivially follows from the definition of p. Now suppose that > r.. Note that r., ri, are both integers, ri, r. 1. By the definition of r., there exists E B(O,r, B)O,((Orr.) 2. and 2/ = 1. Therefore, and z do not "agree" B(O,r. r. 1), so
< r+ 1. On the other hand, since we assumed r, < r', we have (0(O.r,) 2'B(O.r.)> and thus
p >Σ1 T..
(8)
Combining Equations (7) and (8), we have == r.. The claim follows by combining the two cases.
12

---

Multi-Armed Bandits with Interference
C. Proof of Theorem 4.6
Recall that the HT-IX estimator is
L(XataZZ = 1)
Pa(a) = N
Σ WEIN
Quea -B Yuel (2t).
We first decompose the regret using the following fake reward.
Definition C.1 (Fake Reward). For each arm E [k], we define
Rs
Σ P((a) EE[T]
and R= PtEPaaliaa
In words, R2 is approximately the total reward of always choosing arm a, where the true reward P.(a) EuEiNi (u 1 1N) is replaced with the HT-IX estimator (a).. Similarly, R is approximately the total reward of our policy. This is because the expected reward of our policy in round is approximately E. P.a (a),, and (;(a) is close to (a) since it is good estimator.
Let us decompose the regret using the fake rewards. Recall that R the total reward of our EXP3-IX-HT policy, and that for any a" E [k). R. is the reward of the fixed-arm policy at a". Then,
R
R.- (R- R) (N Ro.) + (Ra- -Ra--Pan Ra-).
Next, we bound each of these three terms in subsection separately.
C.1. Bounding the First Term R R
Lemma C.2 (Bounding R Rt). It holds that R - - R ArT 2 + E.ep R..
Proof. We begin by further decomposing R and R, allowing us to compare each term individually in the subsequent analysis. Let us write
R
R
where
R₂
1 Σ N
Yue (Z)) "E[N]
and R
Σ R
where
R PlPi(aa)
aE(k]
Now, fix any [T]. Then,
N(R, Ri)
Ynl(Z) - -Σ Paa uta =1)
Yua (Zi)
D'ra +3
Σ 1(Xiia = Va E [k]) + E1(X =1) Yue(Zi) - ΣΣ
Pio Prol(X.
uta =1)
Yus (2t)
Duta +
u a
Pio 1 uta (2t)
Σ 1X = o [+]) + Σ 1(X 1))
Σ
(10)
Vuta + B
M,a
where the inequality is because Yur < 1. To proceeds, we make observations. First, for any [N], the exposure mappings X can be all 0 only when lies close to aC[u], the boundary of the cluster that contains Formally,
1 (X Va [k]) < (dd(,, 1(d(u,0Clu) < r)
Second, we note that
Quea S [Z]o), a) = Pta-
13

---

Multi-Armed Bandits with Interference
Combining, obtain
Pio 1(X uto =1)
(10) & 1 (d(u, r) + = Σ
(z)(
(11)
Pro +
Note that in each cluster, there are at most 4rl units within distance of to @C|u]. Since there are N/C clusters, we have
N =
4rN
Σ
(d((v, (c(]v, S - 4rl
e
Me M
follows that
Nr
3
(11) <
Σ
1(Xita 1)
Pio +
Nr
1(X uta = =1) (z)
3N
Σ
Σ
N
Quta + 3
aE]k]
WE|N]
Nr
3N Σ
P((a).
aE[k]
where inequalities follows again from Quta
Pta. Therefore,
4rNT
N (R-Ri N Σ
Re Ri) s
NB
Σ Ray aE(A)
8
and the lemma follows by dividing both sides by N.
C.2. Bounding the Second Term R --a R..-
We first derive an upper bound on R R.- by following the analysis of the EXP3 policy. The proof of the following can be found in the analysis of the EXP3 policy; see Equation (11.13) of (Lattimore and Szepesvári, 2020).
Lemma C.3 (EXP3-style analysis). Fix any 1j E (0, 1). Then, for any a" E [k).
R-R Ra. I log le
+n Σ Pa)2 a.s.
2,a
We next show that (a) is highly concentrated around Va(a), with a tail mass that vanishes in N. This done by a careful analysis based on the Chernoff and Bernstein inequalities. We first introduce some basic tools.
Theorem C.4 (Bernstein Inequality for i..dd Sum). Let {Xt)==...... be independent mean-zero random variables with [X,] < M where M > 0 is constant. Then, for any >
2
P
Σ
xx
2
exp
E[X?1+ M EL
Theorem C.5 (Chernoff Inequality for i..dd Sum of Bernoulli's). ss. Suppose XI... Xn Ber(p) are i.i.d. random variables and { n Ei= X,. Then, for any > O, have
IP E 2 (1+6)) s exp (-2e2pp)
Lemma C.6 (Deviation of Bernoulli Sum). Suppose 5, E (0,1) 1) and XI,..., X2 are i.d. Ber(p) random variables.
(1) Suppose p 2 1. Then with probability we have
plog
Σ x, S
14

---

Multi-Armed Bandits with Interference
(2) Suppose p < 1, then w.p. 1 6,
1 1 5
X log
Proof. Part 1: Suppose 2 n We will apply Bernstein's 's inequality on (X; (X:-p), p). Since X; E [0, 1] a.s. and - p(1 p) S p, by taking M in Theorem C.4, we have
n
1
P
Σ
X
up + 1 < exp ( [I - p) + 1t S exp
(12)
np +
for any & > O. Let us choose
V 22p log J. Since 2 h. we have np t. It follows that
(12) S exp
2np S 8.
Part 2: Suppose p < J. It suffices to consider i.idd X, ~ Ber(1/n) since X; stochastically dominates X₁. By the Chernoff bound (Theorem C.5), for any & > 0,
n
1 ni
S exp (-ze²n -
P
2
In partieular, for /3
/3log log y. the above bound becomes 8.
Next, we combine the above and bound Σr, Pea P:(a)a)
Lemma C.7 (Bounding the Squared Terms). For any ō (0, 1), have
kt2 log
b: (0())) T w.p. 1-8. 8.
Σ PiaPi(a)² < 512 1+
Proof. Denote by m = 8/C8 the number of clusters. By the definition of P(()). for any / [T], a a [k],
P:(a) =
1
Σ
1(Xita - Yn
(x nta ()i)
(13)
N
Vuta +
m
Quca + 3
ME[N]
Cel
MEC
By the D-DIP, X = all units in B(u, r) are assigned a, so (Ze) Yuela 1 S (r). Thus,
1 ata
1) Yus (Zz) & 1(X (Zi) = 1). (Yua(a 1N) + (b()).
follows that
1(x uto 1)( 1 + 2b(r)
(13) <
(14)
1
Quta
CENT
BEC
Moreover, by Proposition 4.2, we have Q
8 Ptas so
1
1(x uto =1) (a 1 + (b(r))
(14) <
12
[P + 13)
CEN
NEC
<
8
Σ
Σ
1(X uta 1) (Yur 1N + b(1))
(15)
P
la
B
82
CEN
NEC
15

---

Multi-Armed Bandits with Interference
Note that the cardinality of each cluster satisfies |C| 262, assuming that r S 8/2. So, writing
Σ (a ) Yorla- 18) = C
1
we obtain
8
2
(15) -
Σ
1(
1)
(Vucla.11)) 0(()))
Pta + B
m
C
uta
CEll
NEC
<
16
((r)+ +
Σ
Σ Cix(C)
1lcr a) Vosla.1")
(16)
Pta B
(,(0,,,2)2
Note that for each color fi, the above sum involves 1 g m independent random variables. So by Lemma C.6, w.p. 8 holds that
Pio (aa) + log
Σ
1(Zc a) (
1) PtoVilo)
m
m
Cix(C)=K
Combined with Equation (16), conclude that
PiaYa PtaYe(a) + log + ((()) ))
Σ
Pra Pr(a) <
Σ Pta
Pao PraVi(a) +
Pio + B
5m
1.0
t.a
Pia
Pra (a))) log + v())p)
< 256
Σ
p2 PlaY:(a)
(Ptn + 1)2
1,a
log Σ
(r)}
< 512
Σ
Pta +
Σ
Pio B
f,a
t.a
t,
kL2T
KT
< 512
+
log
+
v(r)2)
N
B
where the second inequality follows since for any a, b, R, we have (a b+ < 2 + + +2).
C.3. Bounding the Third Term R. R.
We need the following tool, which stated as Lemma 12.2 Lattimore and Szepesvári 2020.
Proposition C.8 (One-sided Cramer-Chernole Bound). Let 3 > and F = (Fi)tefry be a ailltratiin. Let (yto hetm. be real numbers, where A is a finite set. Let (8ta) be an F-predictable process and (Yta) be an F-adapted process. Suppose for each E [T]. Yia is (i) unbiased: E[Yea [[-1]= yta for each a E A.
(ii) negative correlated: for any S C A with |S|
>> 1, we have
II LaES
Yia Fi-1
20,
and
(ii) reasonably bounded: 0 S BYia S 28er a.s. for any a E A
Then, for any 5 E (0, 1), we have
IP
ΣΣ 3
Yia
yha
> log
1
8.
1+0ia
LE(T)
AEA
16

---

Multi-Armed Bandits with Interference
Proof. It suffices show that M, IT & is super-martingale (indexed by where
Yia Y yea -Bta )
& exp
Σ AEEA
1+ 8ta
In fact, this true, then by Markov's inequality,
IP
II
PP
B[MM]] S Mn 2
which completes the proof.
Now we show that (M,) is super-martingale. We first use the Cramer-Chernoff method to prove that E, S 1 for any t [T]. We will use the following fact: for any x > O, we have
exp
$1+Ise"
(17)
1 1+>
Write E,[1] = F[] for each E
[T]. Then,
Baa dea
BYa
E1-1
exp
E
exp
+ dea
AEEA
LoEA
E
(1
+
)Ya)
by the first inequality Equation (17)
LaEA
$ E
1 3
Yta
negative correlation
aEA
1 + 3 Σ
yta
by unbiasedness
acA
exp
8 Σ
yta
by the second inequality in Equation (17).
aEd
Rearranging, deduce that
E4- E4-1 <
(18)
Thus, by the tower rule, for any >
we have
E
II E E
&
E
II
E. E
[5]
S
E
&
By induction, deduce that E [[
Ex] S and hence (Mn) is super-martingal.
To proceed, let us apply the above with clusters as the index "a". Specifically, for a fixed RRP II, let us decompose (((a) as a sum over the clusters by writing
P((a) =
1 Σ N
1( =1)
Yno 1 N
Yor CELl
Σ
Qita + 3
WE[N]
where
1(X = 1)
Yora = Σ
Quat + (2))
REC
However, the negative correlation condition (ii) does not hold in general. In fact, consider two neighboring clusters C, C" E 1l and units E C and v' E C" with B(u,r) r) n B(u'r + 0. Then, for any E [K]. the exposure mappings X and X are positively correlated and therefore Youa and Ye are dependent.
We avoid this obstacle by coloring the clusters so that Youa 's with the same color are independent.
17

---

Multi-Armed Bandits with Interference
Definition C.9 (Nine-Coloring). Fix ((,r)-RRP of [O, VNJ.. A mapping x II + [0,1,2] is valid 9-coloring if for any (i,5), (K,3),
x(Cig) = x(Cr))
i= i'and j = (mod 3).
We show that two clusters of the same color have independent contributions to Ya(a).
Lemma C.10 (Independence within Color Class), Let x be valid 9-coloring of II, an (R,r)-RRP. Then, for any C,C² E with x(c) = x(e),, and u E C, w' E C', we have You. Yo' for all a E [k:]
To see this, note that each You is determined by the arm assigned to the clusters. Formally, conditional on the history up
to the (t- (6-1)am 1)ah round, Yera only depends on {Z C' E [(C)} where I(C) {C" B(u, r) for some u E C*). Lemma C.10 then follows by noting that Yota and Yorta are determined by entirely different sets of random variables, i.e. (TC))= 0.
We use Lemma C.10 and Proposition C.8 to bound the deviation of R2 from Rg. Recall that the number m of clusters in an (C,r)-RRP for [0, 2 satisfies ml?- = N.
Proposition C.11 (Bounding Rs Ra). It holds that
max aE|K]
Ru Ra
1 log
5m 8 +
38
T
1())
and
Σ aElk]
Ra
Ra
S
3m
8
log +
3e2 (r))
T
Proof. Denote by Ne the (random) number units in each cluster c, then No S 22 since r I L/2. Then,
T
(X (A)) Yue(a-
m R.
Ra)
Σ
Vuta +
1=1
CeN
MEC
1 sste = =1) (Yue (a. 1) + (br))
-Yue(a 1)
l2
Vuta + B
1=
CEN
BEC
T
1 uta
T =a)Yue 1) Yue(a.1)) + 3
(5(r)
Σ
Quta +,8
1
Duta + 3
CEN
NEC
1=1
CeN
Cell
1(X uto 1) Yuc 1) - Yuu(a 11) (a
mT
3r (r),
(19)
1+
t=
CEL
wEC
Qu
where the first equality follows since mf2 = N, and the final inequality because Vura 2 and N₂ S 28 a.s. To apply Proposition C.8, consider an unbiased estimate
Pa)(a)= = 1(X = =1) 1),
Quta
for (a 1). Then,
T
Pue(a) - Yuela-1) 11) + mf
(19)= 2
Σ
38L (T())
No
1
3
[=1
CENl
weC
Quta
Yulaa - -Yoila -Vci(a.1) (1).)))) 11)
mf
<
Σ Cix(C)=R
Σ
+ BB2 1b(r)
1
B 82
Pea
where the inequality because Quaa S Pta-
We conclude by applying the Cramer-Chernofe inequality the above. In Proposition C.8, take
Yia = No NEC
1
Yue(a) and
8ea = Pio
18

---

Multi-Armed Bandits with Interference
Then, condition (i) in Proposition C.8 is satisfied since
E
Σ
Pu((a) Va .1)
Ne NEC
Moreover, for each color Ki, each term in the summation each E we have
Exx(c)=x are independent, so (ii) is satisfied. Finally, note that for
BY - 3 Ne AEC
Eue(()) 3 Σ
1(X = =1) =1)) Yurla- 1) Pta
8,
No
Vuta
NEC
where the last inequality follows since Quta 2 Pta/8 18 and 0 I Yue(-) 1. Therefore, by Proposition C.8, we conclude that
Bm Rs Ra) 23
Σ E Σ
1
Σ Fuclo)) Parla- 1)) mT v())
1
B Pia
No
KE|4 cx(c)=x
nuEC
+ mT
< 8lgg 8 e (r)),
i...
8
1 T
R_ Ra S
log
382 (r).
3m 8
The proof of (2) is identical by replacing every "En," with "Euraa"
C.4. Proof of Theorem 4.6
We begin by recalling the regret (w...t fixed arm a²) decomposition:
R- = (R - R2) + (ft R..) + (Ra- Raa).
Let us bound each term separately using the lemmas we have shown far. By Lemma C.2,
rT +
R R- RS
Σ R.
l
aE
rT
+ 8 Σ
Ra + 3 Σ
RRg
-Ra)
aElki
ac(k]
rT i
<
+ BKT
+ B Σ
(Ro- Ra).
(20)
[E(R]
By Lemmas C.3 and C.7, w.p. 1 - 8 we have
R Rg <
log k
+ Σ
Pio p((a)2
11
4.a
log k nTT 1 k
1 k
B 866)2)
log
+
(21)
n
m
8
Combining Equations (20) and (21),
R Ra- (R R) + (R Ra.) + (Ra. - Ra.)
rT i + 3KT + 3 Σ (Ro - Ra)
log k
[+ k
1
+ (2())) + (Ra. - Ra.)
+
+
n/I
log
z
m
[E(R)
$ 3kT
rT log k: "
T/ (1
m 5
k
log + 3
1
(1))))
+
3m
log
g +
1
30 3e2(1); vr),
T
(22)
where the last inequality follows from Proposition C.11 and that 3 < 1. The statement follows by rearranging the terms into three categories: (i) those that involve log 1. (ii) those that do not involve log 1 but involve 7), and (iii) others.
19

---

Multi-Armed Bandits with Interference
D. Proof of Proposition 4.2
Consider two cases.
Case Suppose (u, intersects some interior, say Lij- Then, Brrr)) intersects most 2 strips and quad. The probability that these regions are assigned to Ciz
1
1
2
16'
Case 2. Suppose (u,,r) intersects no interior strips. Then, B(u,r) C Q for quad and hence P(B(u,,) r)) C Clul] = 1.
Case 3. Suppose r), intersects no interior and exactly strip S. Then, it must also intersect some quad Q. Denote by
Jon Joz the two interiors that S neighbors where (t1, 02 E (1/82. Then,
((B(u,r) S Clu]] = Σ
Pls C C..] PPQQ C.., |SC
1-1
1
2 4
4
Case 4. Suppose B(u,r) r) does not intersect any interior, and intersects 2 strips, denoted S, S", and 1 quad, denoted Q. Then, S,S' are neighboring the same interior, say Cig. Then,
1
F[B(urr) S CtJl P|S S C.ll CUS- _ Ctyl PPQ S Ctyl
The statement follows by combining the above four cases.
E. Experiments
We consider a 2-armed setting with N units lying on a V x VN lattice. We generate unit-level interference as follows. Each unit u E [N] is assigned a random reward Rut. Let Put be the proportion of the five immediate neighbors (counting u itself) assigned arm at time Then, the reward at u is (2put - 1)C,t-
In sets of experiments, we assume that N 7 and N 8 respectively, and let T' range from 10, 20, 50. For each fixed N, T, randomly generate 100 instances. To necessitate exploration, add large-scale non-stationarity by randomly generating drifts. Each drift is an 8-piecewise constant function, where the value each piece is independently drawn from (00 1). To align with the theoretical analysis, we partition the lattice into square-shaped clusters of side length N 1/4 For simplicity, we perform a simplified version of the clustering without randomly assigning the boundary units to nearby clusters.
We compare the switchback version of EXP3-IX (denoted SB) and our clustered randomization based policy, dubbed EXP3-IX-HT, and denoted "CR" in the figures. We evaluated the performance of the two policies by running each of them 200 times for each instance. We then compute the mean and the 95 percentile of the regret for each instance, and average these numbers over the 100 random instances.
We visualize the results in Figures and 5. Consistent with the theoretical analysis, CR outperforms SB in terms of 95% percentile regret, without sacrificing mean regret. Moreover, we observe that when N = T the regret exhibits a smaller deviation. Finally, we observe that when N 73, the 95 regret percentile of CR is lower compared to the N T case. This is reasonable since larger N helps reduce the variance in the reward estimation.
20

---

Multi-Armed Bandits with Interference
regret, regret, 95% percentile,
7
mean regret, SB
regret, CR
6
percentile,
95% percentile, CR
percentile,, CR.
5
4
3
2
2
0
1
10
20
40
50
10
20
30
40
50
Time Horizon T
Time Horizon T
Figure 4. N 2 case
Figure 5. N 8 case
21


Reviews:
[{"review_id": "G1gaoLqR93", "reviewer": "Reviewer_aFuM", "summary": "The authors combine Auer's EXP3 policy framework, the Horvitz-Thompson IPW (inverse propensity weighting) estimator, along with implicit exploration, and a clustered randomization scheme,\nin order to achieve the optimal $O(\\sqrt T)$ regret bound ($T$ being the horizon), while admitting a high-probability bound that vanishes with increasing $N$ (the number of experimal units),\nunder a spatially decaying interference property / assumption.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! \n\nQ: *\"In the classic reference 'Logarithmic regret algorithms for online convex optimization' by Hazan et al., it is shown how \n regret bounds can be converted into ...\"*\n\nA: This is an interesting thought. First, their result is not applicable to this work, since our reward functions are defined on a discrete domain and thus we can not define convexity (at least in the ordinary sense). But your intuition is right - if the reward function has a special form, such as linear in the neighbors treatment assignments (e.g. Cliff-Ord model) then there exists an estimator with lower error, and this would lead to better regret guarantees. This can be an interesting direction for future work.\n\nQ: *On the topic of cluster-based randomized experimentation, the authors may also wish to cite \"On the topic of cluster-based randomized experimentation, the authors may also wish to cite \"Detecting Network Effects: Randomizing Over Randomized Experiments\", by Saveski, et al.\"*\n\nA: Yes, this is a relevant work; we will cite it in the updated version.", "claims_and_evidence": "Theorems 3.3 on the regret for any MABI (including EXP3-based switchback) approach and Theorem 4.6 on the high-probability regret bound for the proposed Algorithm 1, supported via corollaries 4.7 - 4.9, appear to be the main theoretical claims in this paper.\n\nThe authors plot the VaR (Value at Risk ?) for their regret bounds against $T$ (the horizon) and $N$ (the number of experimal units), in Fig. 2 and Fig. 3, respectively, in order to demonstrate desirable properties of their regret bounds.", "methods_and_evaluation_criteria": "The proposed method / algorithm (Algorithm 1) combines several known approaches mentioned under \"Summary\" in order to obtain novel theoretical results mentioned under \"Claims and Evidence\".\nFor a theoretical paper such as this one, validation via extensive proofs in the main body of the paper and the appendices appear to be appropriate evaluation criteria.", "theoretical_claims": "Please refer to the theoretical claims mentioned under \"Claims And Evidence\".\nThis reviewer didn't check the proofs for Theorems 3.3 and 4.6 in detail.", "experimental_designs_or_analyses": "No experimental results are presented in this paper.", "relation_to_broader_scientific_literature": "Please refer to the reference mentioned under \"Questions For Authors\".", "essential_references_not_discussed": "On the topic of cluster-based randomized experimentation, the authors may also wish to cite \"Detecting Network Effects: Randomizing Over Randomized Experiments\", by Saveski, et al.", "other_strengths_and_weaknesses": "The paper is clearly written and the technical assumptions are clearly stated.\nThe robust random partition is illustrated quite well in Fig. 1.", "other_comments_or_suggestions": "In the Impact statement on lin 419, \"focus cumulative\" should be \"focus on cumulative\".", "questions_for_authors": "In the classic reference \"Logarithmic regret algorithms for online convex optimization\", by Hazan et al., it is shown how $O(\\sqrt T)$ regret bounds can be converted into $O (log T)$ bounds via stronger assumptions. Have the authors considered a similar approach of using stronger assumptions ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jvhgjsD0k6", "reviewer": "Reviewer_MDpF", "summary": "The paper presents optimal expected regret bound and presents a high-probability regret bound in presence of correlated rewards among the arms.\n\n\n\npost-rebuttal: I wish to thank the authors for the reply. I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback.\n\nQ: *\"It is not completely clear methodology-wise what is the essential difference between stochastic bandits that consider possibly more general notions of interference and the present paper that considers a specific notion of interference and adversarial reward.\"*\n\nA: Good question. There are two disadvantages of the stochastic (i.i.d. reward) bandits analog: \n- Practicality: Real-world A/B testing involves highly dynamic and heterogeneous environments; \n- Technicality: If the rewards are iid, the problem wouldn't be too different Leung 2022. In fact, all we need to do is to combine their low-error estimator with a known paradigm for stochastic bandits, such as UCB. \n\nThat said, we do agree that the inclusion of a dedicated section on the stochastic version would provide a more complete picture, and we will do so if accepted.\n\nQ: *\"How does the computational complexity analysis of the proposed algorithm look like?\"*\n\nA: The bottleneck in terms of the time complexity lies in computing the estimator. Fix an arm. For each unit $u$, we need to compute the exposure mapping probability. this involves examining the arm assigned to each of the $O((r/\\ell)^2)$ clusters that are close to $u$. Therefore, the total run time per round is $O(kN (r/\\ell)^2)$. (Note that $r/\\ell\\le \\sqrt N$)", "claims_and_evidence": "Claims are well-supported by evidence.", "methods_and_evaluation_criteria": "I am unsure about how the distance-decaying interference assumption connects to other definitions of interference in the causal inference literature.", "theoretical_claims": "I have not checked the correctness of any proofs for theoretical claims.", "experimental_designs_or_analyses": "Experimental design and analysis make sense to me. Though the legends in benchmarks e.g. EXP3-SB is not well-explained -- specifically which method is this?", "relation_to_broader_scientific_literature": "It is not completely clear methodology-wise what is the essential difference between stochastic bandits that consider possibly more general notions of interference and the present paper that considers a specific notion of interference and adversarial reward.", "essential_references_not_discussed": "Relevant literature is discussed.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "There seems to be a \"depends\" missing in the abstract \"The reward of each unit on the treatments of all units, and this dependence decays in distance.'", "questions_for_authors": "How does the computational complexity analysis of the proposed algorithm look like?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RHDf2q70L0", "reviewer": "Reviewer_XNnY", "summary": "The authors study a multi-armed bandit problem where interference (treatment of one arm affects the outcome of others) exists. The authors theoretically prove that a switchback policy achieves optimal regret. They provide a novel method based on clustered randomization and prove that the regret of the proposed method is both optimal in expectation and vanishing in N with high probability.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback. \n\n*\"How does the choice of the learning rate and the IX parameter beta affect the performance of the proposed method?\"*\n \nGood question. Intuitively, $\\beta$ controls the forced exploration of arms with low score. This aligns very well with Theorem 4.6, where $\\beta$ appears in both terms B and C. In fact, B corresponds to the tail mass, and a small $\\beta$ (which means less exploration) would cause the tail mass to go up. On the other hand, C is the regret caused by the bias (due to both interference and bias in the estimator). If $\\beta$ is away from the \"sweet spot\", the HT estimator has a high bias.\n\nThanks again for this question, which helps improve the clarity of our results. If accepted, we will add these discussions to the paper.", "claims_and_evidence": "The authors concisely described key ideas of their proofs. They highlighted key steps and provided detailed arguments in the main paper.", "methods_and_evaluation_criteria": "Yes, the proposed method clearly addressed the shortcomings of existing methods. \n\nTo address the drawback of switchback policies that rates do not vanish as N grows, they propose a policy that has a regret bound vanishing in N. To achieve this, they integrate the truncated HT estimator into the EXP3-IX framework. There are two main challenges: the uniform spatial clustering is not robust since arms may have very low probabilities; it is unclear how to select the IX parameter in the batched setting.", "theoretical_claims": "The authors establish an upper bound restricted to switchback policies. They further establish a lower bound showing that rates cannot be improved by leveraging N using more complicated policies. The then prove the regret bound for their proposed method. I did not find any error in the theoretical claims.", "experimental_designs_or_analyses": "The results showcase the VaR of the regret. Although the experimental results are limited, I understand the focus of the paper is on theory and thus experiments are not the main contribution.", "relation_to_broader_scientific_literature": "The paper clearly discussed relevant literature.", "essential_references_not_discussed": "I did not find any essential references not discussed.", "other_strengths_and_weaknesses": "The paper is well written and easy to follow.", "other_comments_or_suggestions": "How does the choice of the learning rate and the IX parameter beta affect the performance of the proposed method? Could the authors verify empirically that the proposed method is robust against choices of hyperparameters?", "questions_for_authors": "Please see my comments above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uF59rjUCRm", "reviewer": "Reviewer_SQ3C", "summary": "This paper is the first to study MAB with interference. The learning model in this paper requires each node to take the same action and assumes that the interference intensity decays with distance. The paper proposes an EXP3-IX algorithm based on exposure mapping, achieving a high-probability regret upper bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We appreciate the feedback and would like to share our responses below.\n\n*1. Definition of Regret:* \n\nAlternatively, one could define the benchmark to be the optimal \"personalized\" treatment assignment from a function class $\\mathcal{F}$. In this case, our analysis still applies—for instance, the expected regret bound scales with a factor of $\\sqrt{|\\mathcal{F}|}.$ We note that this \"personalized\" benchmark was used in Agarwal et al 2024, however, the cost paid for choosing this stronger benchmark is that the environment was assumed to be **stationary**.  \n\nIt’s also worth noting that the same critique could be made of many foundational works in causal inference, which focus on the ATE effect between all-1 and all-0 policies. While these benchmarks appear simplistic, they are far from trivial and have led to a rich body of work in causal inference. Of course, policy learning - finding a good mapping from covariates to treatment — is a natural extension. But it is viewed as a more advanced goal, and builds upon insights from the fixed-policy setting, analogous the one in this work.\n\n*2. Expected regret vs h.p. regret:* \n\nIt is true that a h.p. bound can be obtained by treating the entire system as a single “unit” and applying h.p.bounds for EXP-IX (as we discussed at the end of the intro and the start of section 4). However, this approach completely ignores N, and as a result, the tail probability does not vanish with increasing N. This dependence on N is crucial, especially in practical applications where $N \\gg T.$ In fact, we dedicate Section 4.5 specifically to discussing this distinction.\n\nFrom a practical standpoint, a “pure” switchback policy—where the entire system flips between treatment and control—is rarely used. Instead, tech firms typically partition the space into clusters and independently assign treatment or control to each cluster in each period. This is precisely what our algorithm is designed to capture. A concrete example is DoorDash’s use of “clustered” switchback experiments: https://careersatdoordash.com/blog/experiment-rigor-for-switchback-experiment-analysis/\nIn this sense, a key contribution of our work is to lay the **theoretical foundation for a policy class that are widely deployed in industry.**\n\nWhile we mentioned the phrase “vanishing in N” in the abstract and other parts of the paper, we agree that this could have been more clearly emphasized. If the paper is accepted, we will revise accordingly to better highlight this point.\n\n*3. Discussion of stochastic and adversarial bandits in the literature review.* \n\nThis is a fair point. To clarify, our claim that the adversarial setting is more general than the stochastic one assumes that the reward distribution has bounded support. That said, for the purposes of algorithm design and analysis, assuming sub-Gaussian noise with bounded mean behaves similarly to the bounded reward setting (e.g., Bernoulli rewards). \n\n*4.  Examples/references for the Decaying Interference Property* \n\nAs we mentioned right before Defn 2.3, this Decaying Interference Property (DIP) is **borrowed from Leung 2022**. The best way to motivate the the DIP is by noting that it generalizes several natural interference models that are well-known in the literature, including: \n- (a) SUTVA (see our remark 2.4 right after def 2.3); \n- (b) k-neighborhood model, where two units interfere with each other if there distance is at most k; \n- (c) Cliff-Ord autoregressive model, where the treatment effect on unit u is a linear combination of the treatment effects on its direct neighbors (plus base effects). In this case, we have $\\psi(r) = r^{-2}.$", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have checked most of the proofs and found that they are correct.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "The vast majority of relevant references have been discussed.", "other_strengths_and_weaknesses": "**Strengths:**   \n1. This paper proposed the first study on MAB with interference.    \n2. This paper proposes an algorithm that integrates exposure mapping. By leveraging exposure mapping and the assumption on interference intensity, this algorithm optimizes the performance of the general switchback strategy combined with EXP3-IX.  \n3. The experimental section of the paper is relatively comprehensive.    \n\n**Weaknesses/Problems:**  \n1. The regret definition in the paper only considers the optimal switchback policy, where each node takes the same action. This somewhat reduces the problem's difficulty, and the authors do not provide a clear motivating example from real-world applications.\n2. The subheadings in the paper are somewhat confusing. Based on my understanding, a simple combination of EXP3-IX and the switchback policy is already sufficient to achieve a high-probability regret upper bound. I am not entirely sure why the authors named Section 3 \"Expected Regret\"; it might be because this chapter primarily establishes an expected regret lower bound. As for Section 4, I find \"High Probability Regret\" is also inappropriate, as obtaining a high-probability regret bound is fairly straightforward. From my perspective, the main contribution of the paper is integrating the exposure mapping mechanism into EXP3-IX and leveraging the assumption of interference attenuation to derive a regret bound that is tighter than the one obtained by directly applying EXP3-IX with the switchback policy.\n3. The discussion of stochastic and adversarial settings in the related work section is somewhat controversial. In the stochastic case, it is typically assumed that the true reward is perturbed by a 1-sub-Gaussian noise, making the reward unbounded. In contrast, the adversarial case usually assumes that the reward is bounded. Given the setting of this paper, I believe the authors should state that their work and the referenced papers consider different settings, rather than claiming that the adversarial setting is more general than the stochastic one.\n4. The authors do not provide motivated examples/references for the proposed Decaying Interference Property assumption.", "other_comments_or_suggestions": "## update after rebuttal: The authors have addressed my concerns, so I recommend acceptance.", "questions_for_authors": "See the Strengths And Weaknesses section", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: The paper analyzes a novel framework—adversarial bandits with interference—and proposes a new algorithm that guarantees a tight upper bound on the expected regret and ensures that the tail mass of the regret vanishes as the number of treated units increases. The new algorithm integrates the clustered randomization idea (using a more sophisticated version-RRP) with the EXP3-IX algorithm, hence controlling the variance of the HT estimator for unobserved rewards.

Overall, all reviewers agree that the novel framework is well-motivated, and the proposed algorithm provides an effective solution with low variance. Authors are encouraged to incorporate reviewers’ comments (clarifying assumptions, adding references) in their revised version.
Decision: Accept (poster)