Mutli-Armed Bandits with Network Interference
Authors: Abhineet Agarwal
Anish Agarwal
Lorenzo Masoero
Justin Whitehouse
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal Inference
Online Learning
Recommender Systems
Reinforcement Learning
Primary area: bandits

Abstract: Online experimentation with interference is a common challenge in modern applications such as e-commerce and adaptive clinical trials in medicine. For example, in online marketplaces, the revenue of a good depends on discounts applied to competing goods. Statistical inference with interference is widely studied in the offline setting, but far less is known about how to adaptively assign treatments to minimize regret. We address this gap by studying a multi-armed bandit (MAB) problem where a learner (e-commerce platform) sequentially assigns one of possible $\mathcal{A}$ actions (discounts) to $N$ units (goods) over $T$ rounds to minimize regret (maximize revenue). Unlike traditional MAB problems, the reward of each unit depends on the treatments assigned to other units, i.e., there is *interference* across the underlying network of units. With $\mathcal{A}$ actions and $N$ units, minimizing regret is combinatorially difficult since the action space grows as $\mathcal{A}^N$. To overcome this issue, we study a *sparse network interference* model, where the reward of a unit is only affected by the treatments assigned to $s$ neighboring units. We use tools from discrete Fourier analysis to develop a sparse linear representation of the unit-specific reward $r_n: [\mathcal{A}]^N \rightarrow \mathbb{R} $, and propose simple, linear regression-based algorithms to minimize regret. Importantly, our algorithms achieve provably low regret both when the learner observes the interference neighborhood for all units and when it is unknown. This significantly generalizes other works on this topic which impose strict conditions on the strength of interference on a *known* network, and also compare regret to a markedly weaker optimal action. 
Empirically, we corroborate our theoretical findings via numerical simulations.

Multi-Armed Bandits with Network Interference
Abhineet Agarwal
Anish Agarwal Department of IEOR Columbia University aa5 ba51940columbe edu
Lorenzo Masoero
Department of Statistics
Amazon masoer1@amazon. com"
UC Berkeley aa3797@berkelen edu
Justin Whitehouse
Computer Science Department Carnegie Mellon University juhiteho@andres cmu edu
Abstract
Online experimentation with interference is common challenge in modern appli- cations such as e-commerce and adaptive clinical trials medicine. For example, in online marketplaces, the revenue of good depends discounts applied competing goods. Statistical inference with interference is widely studied in the offline setting, but far less is known about how to adaptively assign treatments minimize regret. We address this gap by studying multi-armed bandit (MAB) problem where learner (e-commerce platform) sequentially assigns one of pos- sible A actions (discounts) to N units (goods) over T rounds to minimize regret (maximize revenue). Unlike traditional MAB problems, the reward of each unit depends on the treatments assigned to other units, i.c., there is interference across the underlying network of units. With A actions and N units, minimizing regret is combinatorially difficult since the action space grows as A To overcome this issue, we study sparse network interference model, where the reward of a unit is only affected by the treatments assigned to s neighboring units. We use tools from discrete Fourier analysis to develop sparse linear representation of the unit-specife reward Fn [A] -> R, and propose simple, linear regression- based algorithms to minimize regret. Importantly, our algorithms achieve provably low regret both when the learner observes the interference neighborhood for all units and when is unknown. This significantly generalizes other works on this topic which impose strict conditions on the strength of interference known network, and also compare regret to a markedly weaker optimal action. Empirically, we corroborate our theoretical findings via numerical simulations.
Introduction
Online experimentation is indispensable tool for modern decision-makers in settings ranging from e-commerce marketplaces [Li al. 2016) to adaptive clinical trials in medicine [Durand et al. 2018). Despite the wide-spread use of online experimentation assign treatments units (e.g., individuals, subgroups, or goods), a significant challenge in these settings is that outcomes of one unit are often affected by treatments assigned to other units. That there interference across the underlying network of units. For example, in e-commerce, the revenue for given good depends on discounts applied to related or competing goods. In medicine, an individual's i's risk of disease depends not only on their own vaccination status but also on that of others in their network.
'The research presented in this paper conducted independently and is entirely unrelated to the author's current appointment Amazon.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

8
2
7
9
3
Figure 1: A visual representation of sparse network interference. In this toy example, have N = 9 units, and visualize the interference pattern. For unit (orange), its outcomes are affected by the treatments of its neighbours (blue) (2() = {1, 2, 3, 3,6,777 7).
Network interference often invalidates standard tools and algorithms for the design and analysis of experiments. While there has been significant work done to develop tools for statistical inference in the offline setting (see Section 2) this problem has mostly been unaddressed in the online learning setting. In this paper, we address this gap by studying the multi-armed bandit (MAB) problem with network interference. We consider the setting where learner (online marketplace) assigns of possible A E N actions (varying discounts) to units (goods) over T rounds to minimize average regret. In setting, the reward of unit E [N] (1.-.., N) depends the actions assigned to other units P With units and A actions, achieving low regret is difficult since there are A possible treatment assignments. Naively applying typical MAB methods such as the upper confidence bound (UCB) algorithm [Auer al. 2002] leads to regret that scales as O(v A AT), which can be prohibitively large due to the exponential dependence on N. Further, without any assumptions on the interference pattern, regret scaling as 52( ( is unavoidable due lower bounds from the MAB literature Lattimore and Szepesvári 2020
To overcome this issue, we consider a natural and widely-studied model of sparse network inter- ference, where the reward rn : [A] - for unit n is affected by the treatment assignment of at most other units, i.e., neighbours. See Figure for visualization. Under this model, we provide algorithms that provably achieve low regret both when the learner observes the network (i.e., the learner knows the neighbors for all units n), and when it is unknown. Our results allow for more general interference patterns and define regret with respect to a significantly stronger comparator policy than existing results in the literature. Contributions.
(i) For each unit E [N]. we use the Fourier analysis of discrete functions to re-express its reward r, [A]N : R linear function in the Fourier basis with coefficients 9,, R We show sparse network interference implies 0,, is A sparse for all n E [N]. This sparse linear representation motivates simple explore-then-commit style algorithm that uniformly explores actions, then fits a linear model to estimate unit-specific rewards (i.e., 0.))
(ii) With known interference (i.e., the learner knows the s neighbors exploits this knowledge estimate r,, by performing ordinary least squares (OLS) locally (i.e., per unit) on the Fourier basis elements where 0, non-zero. Our analysis establishes regret ((AAT)22/3 for this algorithm.
n E [N], our algorithm
(iii) With unknown interference, we use the Lasso instead of OLS locally which adapts sparsity We argue this T2/3 scaling cannot be improved. (iv) Numerical simulations with network interference show our method outperforms baselines.
of O,, and establish regret
2
Related Work
Causal inference and bandits with interference. The problem of learning causal effects in the presence of cross-unit interference has received significant study from the causal inference com-
For any positive integer æ, let [æ] == ....

---

munity (see [Bajari et al. 2023 for thorough overview). Cross- unit interference violates basic assumptions for causal identihability, invalidating standard designs and analyses As a result, authors
have developed methodologies for estimating causal effects under several models of interference
such as intra-group interference [Hudgens and Halloran 2008 [Rosenaum 2007]. I interference
neighborhoods [Gao and Ding 2023] U Ugander et al. [2033] Bhattacharya et al., 2020] Yu et al. 2022 Cen et al. 2022]. in bipartite graphs representative of modern online markets [Pouget-Abadis et al. 2019 Bajari et al. [02 2023]. in panel data settings [Agarwal et al., [022] as well as under general model of interference, generally encoded via "exposure mappings" [Aronow] 2012 Aronow and Samii 2017). J. Despite this large literature, there is much less work on learning with interference in online settings. Jia et al. 2024] take an important step towards addressing this gap by studying MABs with network interference, but assume known, grid-like interference pattern, where the strength of the interference decays as the & distance between units grows. Moreover, their focus unlike ours is on establishing regret rates with respect the best constant policy, i.e. the best policy that assigns each unit the same treatment. We also note that the authors consider a setting more closely aligned with the adversarial bandit literature, whereas the results in this paper are closer to those in the stochastic bandit literature. See Section 3 for a detailed description of these differences.
Bandits with high-dimensional action spaces. In MAB problems, regret is typically lower bounded by Actionss T), where # Actions- A in our setting. Typically, this curse of dimensionality is addressed by sparsity constraints on the rewards, where only a small fraction of actions have non-zero rewards [Kwon et al., 2017 Abbasi- Yadkori et al. [012 Hao et al. 2020). Particularly relevant to this paper is the work of Hao et al. [2020) who consider sparse linear bandits. The authors utilize a "explore-then-comeee Lasso to estimate the sparse linear parameter. We utilize a similar algorithm but allow for arbitrary interaction between neighboring units, instead using discrete Fourier analysis linearly represent rewards [Negahban and Shahl 2012, O' O'Donnell] [014 Agarwal et al., [202)]. This is similar to kernel bandits [Srinivas et al. 2009 Chowdhury and Gopalan [207]] Whitehouse et al., [024). which assume there exists a feature map such that the rewards can be linearly represented (non-sparsely) in
style algorithm to uniformly explore actions before using the
high-dimensional reproducing kernel Hilbert space. Also related are stochastic combinatorial bandits [Chen et al. [213]]
and Lugosi| 2012), in which the action space is assumed to be subset of {0, 1j but rewards are typically inherently assumed to be linear in treatment assignments. That is. these works typically assume the reward r = (0, a) for E {0, 11., with valid actions often having at most 8 non-zero components. Our work (with A = 2), considers an arbitrary function
{0, 1)x² + R. but explicitly constructs feature map via discrete Fourier analysis such that rewards can be represented linearly.
3 Model & BBcckrouud
In this section, first describe the problem setting, and our notion of regret. Then, we introduce the requisite background on discrete Fourier analysis that we will use to motivate our algorithm and theoretical analysis. Last, we introduce the model that we study in this paper. Throughout this paper, we use boldface to represent vectors and matrices.
3.1 Problem Set-up
We consider an agent that sequentially interacts with an environment consisting of N individual units over a series of T rounds. We index units n E [N]. and rounds t E [T]. At each time step t,
the agent simultaneously administers each unit n action (or treatment) E [LA], Let one denote the
treatment received by unit n at time step I, and let a, = (a1r, aN:) E [A] N denote the entire
treatment vector. Each unit n possesses an unknown reward mapping Tn : [A] - [0, 1]. Note that we allow the reward for a given unit n to depend on the treatments assigned to all other units, i.e., we
allow for cross-unit interference. After assigning a treatment to all units in round t, the agent then observes the noisy reward for unit n as Ry, = (a:) + Ent. Denote the vector of observed rewards as R2 := (Bie... Rv.). We assume the following standard condition the noise Ent.
Assumption 1. (Ene E [N], t [T] is a collection of mutually independent random variables.
Speeiifically, it violates the stable unit treatment value assumption (SUTVA) Rubin 1978
3

---

Regret. To measure the performance of the learning agent, we define the average reward function F: [A] + [0, by F(a) せेr > (a). Then, for sequence of (potentially random) treatment assignments a1 ....... ay, the regret at the horizon time is defined as the quantity
T Regr Σ F(a")
Σ 7(a)).
where a" E arg [a F(a). In Sections 4 small regret with high probability.
5
we provide and analyse algorithms that achieve
Comparison to other works. Previous works studying network bandits such as Jia et al. 2024 measure regret with respect the best constant action a' : arg maXae]AA] F(a1) where IN denotes the all 1 vector of dimension N. We compare regret to the optimal action a" e arg maX F(a), which is combinatorially more difficult to minimize since the policy space is exponentially larger (AN vs A). Our setup is also different than the traditional MAB setting since the agent this problem does not observe a single scalar reward, but one for each unit (similar to semi-bandit feedback in the combinatorial bandits literature (Cesa-Bianchi and Lugosi 2012). As we show later, this crucially allows us to exploit local, unit-specific information that allow for better regret rates.
3.2 Background on Discrete Fourier Analysis
In this section, we provide background on discrete Fourier analysis, which we heavily employ in both our algorithm and analysis. Specifically, these Fourier-analytic tools provide linear representation of the discrete unit-specific rewards Tn [A] + [0, 1]. which will allow us to leverage well-studied linear bandit algorithms. For the rest of paper, assume a power of 2. If instead, if 2 A 2 for some f 2 O, we can redundantly encode actions to obtain A' = 2 total treatments. As seen later, this encoding does not affect the overall regret.
Boolean encoding of action space. Since by assumption A is a power of 2, every action E [A] can be uniquely represented as binary number using log2 bits. Explicitly, let (oo,)) (A), E {0, ())0 denote this vectorized binary representation. For ease of analysis, we use the Boolean representation instead v(a) 2v(a) - 1 E (11,1) A For a [A]], N define v(a) (v(a)), v(ax)) (-1, 1 (A), Note each action a [A] corresponds to a unique Boolean vector v(a).
(a) (a) ...
Boolean representation of discrete functions. Let F = {f [A]N + R} and FBool = {f log, Nog,
+ R} be the collection of all real-values functions defined on the set [A] and { {-1, 1) (A) respectively. Since every E [A] has uniquely Boolean representation v(a) E 1_,, M the set of functions F can be naturally identified within Foool. Specifically, any f E F can be identified with the function f E Fooot by f(-) = f(v(-)).
Fourier series of Boolean functions. This identification is key for our use since the space of Boolean functions admits a number of attractive properties.
(I) Hilbert space. FBool forms Hilbert space defined by the following inner product: for any h, E FBool (h, g)B = A Exx(-1.)) (o) h(x)g(x). This inner product induces the norm |1bl = - Exe(-1.17 hx(x).
(h, b)
(2) Simple orthonormal basis. For each subset S [N (Ag], define basis function xs(x) Mies I2 where x; is the tth coefficient of x E 1] (A), One can verify that for any S C [N (A)), [Xxs|e = 1. and that (xs, Xs = 0 for any S' + S. Since Hxs S C [N (A)]( = AA, the functionn Xs are an orthonormal basis of Fooot- We refer to Xs as the Fourier character for the subset S.
(3) Linear Fourier expansion of F Any E Foool can be expanded via the following Fourier decomposition: h(x) = Escin (A)) (sxs(x), where the Fourier coefficient As is given by As =
(h, Xs) n. For h E F we refer to 0, = (0s S C IN (og,(()) E IR-AA as the vector of Fourier coefficients associated with it. For E {-1, 1) log, (A) let x(x) (xs(x) S E IN (og,(())

---

{-1,1]A" be the vector of associated Fourier character outputs. For a E [A] abbreviate xs(v(a)) and x(v(a)) as xs(a) and x(a) respectively.
3.3 Model: Sparse Network Interference
The unit-specific reward function Tn [A] + IR can be equivalently viewed as a real-valued Boolean function over the hypercube 1. loga(A), That is, I' takes as input a vector of actions a E [AAJ,, converts it to a Boolean vector v(a) E {-1, [o)g2(A), and outputs a reward I'n (a). From the discussion in Section 3.2 we can represent unit n's reward In (a) E (A)) (n,sXs(a)
(On, x(a)), where ,, (f...: 5 S N (A)) E RAA vector of Fourier coefficients.
Without any assumptions on the nature of the interference pattern, achieving low regret is impossible since requires estimating A Fourier coefficients per unit. To overcome this fundamental challenge, we impose a natural structure on the interference pattern which assumes that the reward Yn only depends on the the treatment assignment of subset of s units. This assumption is often observed in practice, e.g., the revenue of a good does not depend on discounts applied to all other goods, but only those applied similar or related ones.
Assumption 2. (Sparse Network Interference) For any unit E [N], there exists neighborhood (n) C [N] of size [n)) S such that In (a) = (n) for all a, b E {-1, 1] N log, A satisfying (Am m E (m)) = (bm m E (n))..
We typically assume that E (n).. i.c. unit n's reward depends on its own treatment. This model allows for completely arbitrary interference between these units, generalizing the results Tf et al.) 2024] who allow for interaction between all N units but assume the strength of interference decays with particular notion of distance between units. Next, we show using our Fourier analytic tools, that Assumption implies that the reward can be re-expressed as a sparse linear model. We prove the following in Appendix A
2
Proposition 3.1. Let Assumption 2 hold. Then, for any unit n, and action [A]", have the following representation of the reward Tn (a) = (On, x(a)), where ||0,|lo S A
shows sparse network interference implies 6, is A sparse with non-zero coordinates corresponding to the interactions of treatments between units in (n)). Indeed, the Boolean encoding (a) can be represented blocks of 1og (A) dimensional Boolean vectors:
Proposition 3.1
v(a) = (v(a) 1:lg.
((a 1) log, (A4) (og2)))) v(a) (o) +1:N log, (A))
Unit I's treatment
Unit treatment
Unit N's
Unit n's reward depends on a small collection of these blocks, those indexed by its neighbors. Define
B(n) == [o)) : E [[m 1) (A) + 1: m (og)(A)) for some m EN(m).
((n) contains the indices of v(a) corresponding to treatments of units m E (n) and the non-zero
entries of O, are indexed by subsets S C B(n). E.g., consider N = 3, A = 2, with N(11 = 21, Then ((1) (1 and S C B(n)= = {0, [1}, (2), [1,2}}, where 0 is the empty set.
Graphical interpretation. Assumption 2 can be interpreted graphically as follows. Let G = ([V), E) denote directed graph over the N units, where E C [N] x [N] denotes the edges of G. For unit we add to the edge set E directed edge (n, m) for each m e M(n),, thus justifying calling N ((n) the neighborhood of n. That is, unit n's reward is affected by the treatment of another unit only if there is a directed edge from n to m. See Figure for an example of a network graph G.
4 Network Multi-Armed Bandits with Known Interference
We now present our algorithms and regret bounds when the interference pattern is known, i.e. the learner observes G and knows ((n)) for each unit n. The unknown case is analysed in Section Assuming knowledge of & is reasonable in e-commerce, where the platform (learner) assigning discounts (treatments) to goods (units) understands the underlying similarity between goods.
For vector E Rdd define ||æ||o == Eí 1(x, + 0)
5

---

Our algorithm requires the following additional notation: for a E [A] let (B,) (xs(a)) :S
B(n)) E 1-1,1]44 where (a) are the Fourier characteristics corresponding to subsets of B(n). Further, let ((A))( denote the uniform discrete distribution on the action space [AA]*.
Algorithm Network Explore- Commii with Known Interference
1: Input: Time horizon 7, exploration steps E, interference graph 9 = -[N],E).
2: Sample . ag ~i. 2 ([A]*)
3: Observe reward vectors R. (R1e." .RNe) for [E], where Rut (0n, x(a+)) + Ent-
4: for n E [M] do
5: Let X,, (x"1 (B,) : [E]) E (-1,1] // xB. = (xs(a): B(n))
6: Let Y, (Bal...., ,aEl).............
7: Set On == arg minBER Yn -x,
8: Define On by Ons Ons if S C B(n) else set Ons 0. // Coordinates of On
indexed by subsets of B(n)
9: Set 0 == N E On
10: Play = arg max (A (0, X(a)) for the T remaining rounds.
Algorithm is "explore-then-commit" style which operates in two phases. First, the learner assigns units treatments uniformly at random for E' rounds, and observes rewards for each unit. In the second phase, the algorithm performs least squares regressions of the observed rewards against x" (B,) for each unit n. This is because when G is known, the learner knows the positions of the non-zero elements of On which are precisely the subsets of B(n), Once the estimates On, are obtained for each unit, they are aggregated to estimate the average reward for each action a [A] the remaining T E rounds, the learner greedily plays the action with the highest estimated average reward.
Determining exploration length E. Theoretically, we detail the length of below to achieve low regret in Theorem 4.1 Practically, the leamner can continue to explore and assess the error of the learnt 0,, via cross-validation (CV). Once the CV error for all units falls below (user-specified) threshold, commit to the action with highest average reward. We use this approach for selecting E in our simulations in Section
4.1 Regret Analysis
Here, we establish bish-probabblityy regret bounds of Algorithm Jsiig O(-) notation. We prove the following in Appendix B
Theorem 4.1. Suppose Assumptions and 2 hold. For T 52 (A22 + s slog(A))) and
any failure probability 8 10, Algorithm with E == 2/33 [log ( log (A)) 1/3 satisfies
Regr O (Islog(A/0)) (eetr==(soog(///)0)))) (
with probability at least 1 - 5.
Establishing Theorem 4.1 requires trading-off the exploration time E' to accurately estimate O,, with the exploitation time. It also requires T be large enough such that we can accurately estimate O,, Next, we compare regret of Algorithm to other methods, ignoring any dependencies on logarithmic factors to ease the discussion.
Comparison to other approaches.
(a) Naive MAB learner. naive learner who treats the entire network of units single multi- armed bandit system with A actions will obtain regret O(VTAN). For sparse networks with E N and T & NN, our regret bound is significantly tighter.
(b) Global estimation. An alternate algorithm would be to estimate Fourier coefficients 0 = 1/N EN 1 On of F directly rather than estimate each O, (i.e., rxx) individually. That is, perform

---

the least squares regression by compressing the observed, unit-specific rewards into R₂ == N D= Ren An analysis similar to the presented in Appendix would yield rate of which suffers an additional N2/33 cost as compared to Theorem 4.1
(Ts1/((TNA"))
(c) Jia et al.) [2024]. Comparing regret to this work is difficult because they assume decaying interference strength on a grid-like network structure and establish regret only with respect to the best constant action, i.e., a' == arg max F(al). We also note that the framework Jia et al. (2024) is closer to that of adversarial bandits, whereas our framework is closer to that of stochastic bandits.
5 Network Multi-A Armed Bandits with Unknown Interference
Next, we consider the case in which the underlying network 9 governing interference not known. We present Algorithm 2 which extends Algorithm Io account for the fact that the learner does not observe the network graph G and thus does not know (nn) for all n. Unknown network interference is common in medical trials, e.g., vaccine roll-outs where individual's 's social network (i.e., 9) is unavailable to the learner.
Algorithm 2 Network Explore-Then-Commee Then-Commit with Unknown Interference
1: Input: Time horizon T, exploration steps E, regularization parameter À >> 0
2: Sample al,..., ay mi.d U1 ([A)*)
3: Observe reward vectors R. (Ric.-.. RNd) for t [E], where Rnt (0n, x(ar)) + Ent-
4: Let = (x(a:): : [E]) E [-1,1]
5: for E [N] do
6: Let Y, = (Rai...., R.
7:
Set O, == arg minl DERAN
X0 - 1 +1
2F
8: Set 0 = N Em= On
9: Play à = arg max (A)N (0, x(a) for the T E remaining rounds.
Algorithm 2 is similar to Algorithm | but differs in how it learns On. Since G is unknown, the learner cannot identify the Fourier characteristics which correspond to the non-zero elements of 6,. Therefore, we regress against the entire Fourier characteristic x(a), using Lasso instead ordinary least squares to adapt to the underlying sparsity of On. A similar CV approach, discussed after Algorithm D can be used to determine both the exploration length E, and regularization parameter X.
Low-order interactions. When A is very large, the computational cost of running the Lasso can be large. Further, if the underlying network indeed believed to be sparse, one can regress against all characteristics Xs where |S| < d. A similar approach is explored in Yu et al. [2022]. In practice, one can choose degree d via CV.
Partially observed network graph G. In many settings, network interference graphs G are partially observed. For example, on e-commerce platforms, interference patterns between established classes of goods is well-understood, but might be less so for newer products. Our framework can naturally be adapted to this setting by running Algorithm[ on the observed portion of G, and Algorithm 2 on the unobserved graph. Specifically, if M(n) is observed for unit replace the Lasso in line 7 of Algorithm with OLS (i.e., line 8) Algorithm
5.1 Regret Analysis
We now establish high-probhaiee probability bounds on the regret for Algorithm 2 in Theorem 5.1 We prove the following in Appendix C
Theorem 5.1. Suppose Assumptions 7 and 2 hold, and assume T = 22 ( + N log(
Then, with failure probability
(0, 1). Algorithm 2 run with X = E log(AA
4. E-1 E-1log log (2N) where E = 2//3 [log ( (3) + N log(A)) 1/3 satisfies
Regr = O
7

---

with probability at least 1 - 5.
We note the regret bound requires the horizon T to be sufficiently large in order to learn the network graph G a necessary detail order to ensure Lasso convergence. This is because the proof of Theorem 5. requires establishing that the matrix of Fourier coefficients for the sampled actions (i.e., design matrix X) satisfies the the necessary regularity conditions to learn 9, accurately. Specifically, show that X is incoherent, i.e., approximately orthogonal, with high probability. See Appendix foor a formal definition of incoherence, and Rigollet and Hütter 2023 Wainwright [2019] for a detailed study of the Lasso.
Comparison to other approaches. Algorithm achieves the same dependence A, 8, as in the known interference case, but pays factor of N as compared to s This additional cost which is logarithmic in the ambient dimension AN is typical in sparse online learning. This regret rate is still significantly lower than naïve approaches that scale as O( (VVAT) when one assumes T is much smaller then A Further, as argued before, estimating per-unit unit rewards (i.c., 0,,) results in lower regret as compared to directly estimating by a factor of N2/3
Dependence on horizon T. Generally, the dependence on cannot be improved. Hao et al. (2020)
lower bound regret for sparse linear bandits as (Spparsit - -T)3/), i.c., (2((44 ( 27)2/3) in our setting, They show improved dependence T" can only be achieved under stronger assumptions on the size of non-zero coefficients of 0..
Simulations
In this section, we perform simulations to empirically validate our algorithms and theoretical findings. We compare Algorithms I |nd to UCB. We could not compare to Jia et al. [2024) since we did not find a public implementation. For our Algorithms, we choose all and use the scikit-learn implementation of the Lasso. Code for our methods and experiments can be found at peattp:://ithutee com/ 1aggaraal199////toooooo results are described below.
via 3-fold CV,
Our experimental setup and
Data Generating Process. We generate interference patterns with varying number of units N E ... 10), (5). and A 2. For each N, we
4. We generate rewards r, (6.,. X(a).. where the non-zero elements of 9, (i.e., &n.s for S C B,)) are drawn uniform from [o. 1]. We normalize rewards so that they are contained in [0. 1]. and add sub-gaussian noise to sampled rewards. We measure regret as we vary T, and set a max horizon of Tmax = 10 2 for each N. Classical MAB algorithms need the horizon 7 to satisfy T > 2-V since they first explore by pulling all 2 arms. We emphasize that these time horizons scaling as T = C A are often unreasonable in practice, as even for A and N 100 there would already be 1.27e actions to explore. We include such large time horizons for the sake of making complete comparison. Our methods circumvent the need for exponentially large exploration times by effectively exploiting sparsity.
Results. We plot the regret at the maximum horizon time as a function of N, and the cumulative regret as we vary T for N 13 in Figure bello. Our results averaged over 5 repetitions, with shaded regions representing standard deviation measured across repetitions. Algorithms/ aand are denoted by Network MAB (Known) and Network MAB (Unknown) respectively. We discuss both sets of plot separately below.
Regret Scaling with N. We plot the cumulative regret when T' = T'ax for N = 9 in Figure (a). Classical MAB algorithms such as UCB see an exponential growth in the regret as N increases. Both Algorithm [ and Algorithm 2 have much milder scaling with N. Algorithm I uses & to reduce the ambient dimension of the regression, hence suffering less dependence on N as compared to Algorithm
2
Regret Scaling with T. We plot the cumulative regret for N = in 2 (b). Despite the poorer scaling of our regret bounds with T, our algorithms lead to significantly better regret than UCB which takes a large horizon to converge. Algorithm is able to end its exploration phase earlier than algorithm since it does not need additional samples to learn the sparsity unlike the Lasso
8

---

17809
2500
Network MAB (Khown)
33000
Network MAD (Ünknown)
Network MAD (Uncnown)
2300
Curutattre Regret
AD73
Cumuletive Regret
1300
6923
4000
2023
500 1000
1500
2000
2500
Number uniss (N)
Morissn (T)
(a) Cumulative regret vs number of units N.
(b) Cumulative regret scaling vs horizon T.
Figure 2: We simulate rewards via sparse network interference pattern, and plot the cumulative regret function and T' Our Network MAB algorithms out aut-perform UCB, irrespective of knowledge of G, and does not suffer exponential dependence number of units N. The results also confirm our theoretical results that knowledge of G leads Algorithm ] to have milder dependence in N and better regret than Algorithm
Conclusion
This paper introduces a framework for regret minimization in MABs with network interference, a ubiquitous problem in practice. We study this problem under a natural sparsity assumption on the interference pattern and provide simple algorithms both when the network graph is known and unknown. Our analysis establishes low regret for these algorithms and numerical simulations corroborate theoretical findings. The results in this paper also significantly generalize previous works on MABs with network interference by allowing for arbitrary and unknown (neighbourhood) interference, well comparing to combinatorially more difficult optimal policy. This paper also suggests future directions for research such as designing algorithms that achieve better dependence on T in the known graph setting. Establishing lower bounds understand optimal algorithms will also be valuable future work. Further extensions could also include considering interference in contextual bandits reinforcement learning problems. We also hope this work serves as bridge between online learning and discrete Fourier analysis.
References
Yasin
David Pal, and Csaba Szepesvari. inllne-to-confidence-s conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9, PMLR, 2012.
Abhineet Agarwal, Anish Agarwal, and Suhas Vijaykumar. Synthetic combinations: A causal inference framework for combinatorial interventions. Advances in Neural Information Processing Systems, 36:19195-19216 2023.
Anish Agarwal, Sarah H Cen, Devavrat Shah, and Christina Lee Yu. Network synthetic interventions: causal framework for panel data under network interference. arXiv preprint arXiv:2210.11355: 2022.
Peter M Aronow. A general method for detecting interference between units randomized experi- ments. Sociological Methods & Research, 41(1):3-16, 2012.
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, 11(4):1912 1947, 2017. doi:
htRpst:ss: //doi org/ 10. 4214/16-A0AS1005
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256. 2002.
Patrick Bajari, Brian Burdick, Guido W Imbens, Lorenzo Masoero, James McQueen, Thomas Richardson, and Ido Rosen. Multiple randomization designs. arXiv preprini arXiv:21 1 2021.

---

Patrick Bajari, Brian Burdick, Guido W Imbens, Lorenzo Masoero, James McQueen, Thomas S Richardson, and Ido M Rosen. Experimental design in marketplaces. Staristical Science, 38(3): 458-476, 2023.
Rohit Bhattacharya, Daniel Malinsky, and lya Shpitser. Causal inference under interference and network uncertainty. In Uncertainty in Artificial Intelligence, pages 1028-1038 PMLR, 2020.
Sarah Huiyi Cen, Anish Agarwal, Christina Yu, and Devavrat Shah. causal inference framework for network interference with panel data. In NewrIPS 2022 Workshop on Causality for Real-world Impact, 2022.
Nicolo Cesa-Biandn BieaaBBancch and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1404-1422, 2012.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi aalli--rmmeddd bandit: General framework and applications. In International conference machine learning, pages 151-159. PMLR, 2013.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference Machine Learning, pages 144-853. PMLR, 2017.
Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pineau. Contextual bandits for adapting treatment in mouse model of de novo carcinogenesis, In Machine Learning for Healthcare Conference, pages 67-82. PMLR, 2018
Mengsi Gao and Peng Ding. Causal inference in network experiments: regression gereessoonbbasd analysis and design-based properties, 2023.
Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753-10076 2020.
Michael G Hudgens and M Elizabeth Halloran. Toward causal inference with interference. Journal of the American Statistical Association, 103(482):332-84,, 2008.
Su Jia, Peter Frazier, and Nathan Kallus. Multi-armed bandits with interference. arXiv preprint MrXiv:2402.01845 2024.
arXiv preprint Joon Kwon, Vianney Perchet, and Claire Vernade. Sparse stochastic bandits.
arXiv:1706.01383, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Pro- ceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages $39-548, 2016.
Sahand Negahban and Devavrat Shah. Learning sparse boolean polynomials. In 2012 50th Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 2032-2036. IEEE, 2012.
Ryan O' D'Doneell. Analysis of boolean functions. Cambridge University Press, 2014.
Jean Pouget-Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, and Vahab Mirrokni. Variance reduction in bipartite experiments through correlation clustering. Advances Neural Information Processing Systems, 32, 2019.
Philippe Rigollet and Jan-Christian Hütter. 10. 2023.
High-dimensional statistics.
arXiv preprint
Paul R Rosenbaum. Interference between units in randomized experiments. Journal of the American Statistical Association, 1024477) 2007.
Donald B Rubin. Bayesian inference for causal effects: The role of randomization. The Annals of statistics, pages 34-58, 1978.
10

---

Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995. 2009.
Johan Ugander, Brian Karrer, Lars Backstrom, and Jon Kleinberg. Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 329-337, 2013.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Justin Whitehouse, Aaditya Ramdas, and Steven Wu, On the sublinear regret of GP-UCB. Advances in Neural Information Processing Systems, 36, 2024.
Christina Lee Yu, Edoardo M Airoldi, Christian Borgs, and Jennifer T Chayes. Estimating the total treatment effect in randomized experiments with unknown network structure. Proceedings of the National Academy of Sciences, 119(44):c2208975119 2022.

---

A Proof of Proposition 3.1
By the discussion in Section recall that for any action [A] and unit n, the reward can be expressed as Tn = (0.. (a))) To establish the proof, it suffices to show that for any S c (N [o)]
satisfying S (n) * 6. (xs, r =. Let S (()) be an arbitrary index, then, we have,
(XS, rn) A-N
E XE{ - Mox)))
xx(x)xs(x)
A-
Σ
xx(x)xs(x)+
E
rx(x)xs(x)
xc x 1,1, (osz(A)
xE xE(- (o
01=1
0,=-1
-A-
Σ
(x)(()x((())())+ +
E
ze (xn(x)xs(1))
xE X6(-1,1JAlogg (oxg(() =1=1
xE(-L.1)Woo2c4 lox2(A)
21-11
A-
Σ
(x) -
E
Th (x)(xxx)1))(x))
XE 1,1] (11-1,11 (A)
3E(-1,11 (Ang(A)
0,
where the final equality follows from the fact that, by Assumption 2 I' (x) = (x') when x and x' differ only in positions indexed by & (nn). Thus, the only subsets S C [N Iog) where we can have (rn: Xs) f are those satisfying S C B(n), which proves the desired result.
B Proofs for for Known Interference
In this section, we prove Theorem 4.1 We establish helper lemmas before proving Theorem 4.1
B.1 Helper Lemmas
Recall the following notation before establishing our results. We defined B(n) = {i E [N (x)) i E [(m - 1) (A) + +1: m log, (A)] for m E (n))) as the set of indices of the treatment (og)(A) belonging to neighbors m E (Nn).. Additionally, X,, (x* (Bx): i E [E] E [] Exx" where x (B,.) = (xs(a) : S C B(n)) E 1-1,1)A* For a matrix A E Nxd let amin (A) denote its minimum singular value. To proceed, we quote the following
vector vaa) E (-1,
theorem.
Lemma B.1 (Theorem 5,41 in Vershynin 2018 ). Let A E IR such that its rows A; are independent isotropic rundom vectors Rdd Af S ym almost surely for all E [N], then, with probability al least 1 8, one has
Tmin (A) VV cm log(2/8))
for universal constant >>
Lemma B.2 (Minimum Figenvalue of Fourier Characteristics) There exists a positive constant C4 > O such that if F 2 C4Aa* log(2A* /8), then,
X
1 2
min
E
with probability at least 1 5.
Proof. We begin by showing the conditions for Lemma B.I are satisfied. First, we prove X, is isotropic, i.c., (B,)) (B.))) LAs, where the expectation is taken over uniformly
12

---

sampling actions a uniformly and random from [A] This follows since for any two subsets S. C N (A)),
(a 1
Σ xs(a)xs:(a))
A
BEAN
(xs, = 1[5=
Since, (B,) {-1,1]A* for all actions a E [A],, (B,) I VAA. Hence, by Lemma B.1
miin (Xn) 2 VE /clog(2A*/8)44 Next, using the fact that miin (X, o (Xn),
get that
X
E CE. lo log
mmin
E
E
Finally, plugging in A log(2.A (8) & E/C for an appropriate C gives us the claimed result.
We quote the following theorem regarding the || 2l2 error of O..
Lemma B.3. [Theorem 2.2 in Rigollet and Hütter (2023]) Assume that Y X.0 c, where is 1 Sub--Gassian, where X E R Rxxa If d S. E, and covariance matrix Ex = XX" E has rank d, then we have with probability least 6,
|X0' -x0 Ci d + log(1/0)
where θ arg mingeR constant.
2 Y-X00
the least squares estimator, and C1 > a positive universal
While the above lemma bounds the mean mean- squared error the least-squares estimate, in applications we can about bounding the & distance between 0" and Ô. Simple rearrangement the above implies that, with probability at least 1 - 5, we actually have
d log log 1/0) 1 - -012 S CiV F. Jmin (Ex)
If, in particular, amin
x 2 1/2, the above can be simplified to
||0* 0 S C2p d + log(1/8)
E
with prohability at least
8 for some new, appropriate universal constant C2 0.
B.2 Proof of Theorem
Proof. Recall the notation θ = N EN
n=1 θ... and à = arg max (θ. x(a).. The average
reward F(a) can bounded using the definition of a and Holder's 's inequality as follows,
r(a") - r(a)= (0, ((xx(a)) x(a))
(0 0 x(a) x(a)) + (0, x(a))
x(a)
50
(0 0, x(a") x(ā))
0,, θn. x(a*) x(ā))
N
N Σ (0, θ.. xa (Bn) - x xB()))
N
1|0, (B,.))) - x x²(
N
13

---

Using (B,)ll S V then gives us
A F(a") F(a)
N Σ 0.. 1
(2)
Next, define "good" events for any unit [M] as
G.I = aminn
X E
AN
O'mn
and G.2 == 110, - - S C2// B-1 At + log
where C2
0 is as stated above. Notice that there exists sufficiently large uni-
versal constant C3
O, such that T 2 C3 [Aox))o((2N/O) + s log(A))) implies E (T'A*)a/a [log ( log (A) 2 C4A5 Iog(4N
Hence, for any given [N],
have via Lemma B.2 that 9x1 holds with probability
Conditioned on 9.1, we get that
2N
(1) 2
2N Summarizing, we get that for any va E [M]. the following holds
4NA
4NNA* 5
0. 0,112 s Cap
E-1
A" + log
Csy E-1 log
5
with probability at least (1
)
> 8/N, where C3 0 an appropriate constant. Taking
2N
union bound over all N units, and then substituting into 2 gives us
4NN 8
r(a") rā)) s Cs.A"
V
E log
Finally, using this, the cumulative regret can be upper bounded with probability 8 as follows:
T
Regr
(F(a") F(ā))
(F(a*) F(())
Σ (F(a") - ((())))((a))
(=++1
4
$ E + CTT
8
Substituting E in the theorem statement completes the proof.
C Proofs for Unknown Interference
In this appendix, we prove Theorem 5.1
Our proof requires the following lemmas.
C.1 Helper Lemmas for Theorem 5.1
The first lemma we prove details the (high-probability) incoherence guarantees of the uniformly random design matrix under the Fourier basis. Recall the following notation before stating and proving our results. We denote E as our exploration length, and x(a:) ) as the Fourier characteristic
associated with action a, [A]N. Let X (x(a:) [E]) { [-1,1] Ex.A Additionally, require the following definition of incoherence.
Definition C.1. We say matrix A E ERE is s-incoherent if A Ialloo 325 where I is the identity matrix of dimension d.
Lemma C.2 (Incoherence of Fourier Characteristics) For E 2 1, suppose a1...., ag [[[-1,+1]] (ogg(A)). Then,
idd
X X
2 log
2,42N 8
P
LAN
5
2 1 - 8,
E
E
14

---

where || 4096 [log (3) + 2N log (A)]. X is A"-incoherent with probability at least 1
max4, Ai,J denotes the maximum coordinates of matrix. Thus. if E 2
Proof. Recall that, for any [A]*, ((a) == (Xs, (a),.... ................... AN (a)). where , AAN N is some fixed enumeration of subsets S C [ logg (AA)]. Thus, each entry of (X X can be viewed as being indexed by subsets S, S" C [N 2og2(A)), (A)].
To establish
C.2
we first examine diagonal elements of (X (XX))EE. E. For S C (og), we have
X
X
Σx Exlax((aa)))
1
xs(ai)xs(a)) =1
(3)
3,8
8,5
where the last equality follows from the fact that (xs(a)))2
Next, we consider off-diagonal elements, and bound their magnitude. Before doing so, we require the following. For subsets S,S' C [N [Nlogg (A)), let SA,5" denote the symmetric difference of two subsets. For any two subsets S, S' C [N log, (.A)]. the product of their Fourier characteristies is,
II v(ai)) LES
xs(a))ss(aa))
II FES
v(ai)e
= II v(a:). eSSAS
Using this, for any distinct subsets S, have
X X
1
xs xs(aa)ss a.) = E II
v(a)).
E
5,5'
IESAS'
(A)). the set of random variables {v(a)); : SAS') are independent Rademacher random variables. Applying Hoeffding's 's inequality for e > gives us
Since S St, and a, u((-1,11 13 11,,,
-(X²*
[x'x E
Ee
IP
26
< 2 exx
(-2 2
S,9'
Applying the inequality above and taking a union bound over all
A elements of (X X)/E
X
Ec²
P
max 8,9' C|N log)(A)
2e
$
2N
exp
E
2
S,8'
S
Choosing
/ 2 log
2AA2N (2 0
yields,
X X E
2 log
2A2N
8
max S,9' C[N log, (4)) S
S 6.
S.5'
To complete the proof, observe that implies that
X
X
X T X
LAN
E
S logz(A)]
E
S.5!
S
Substituting this observation into 4 above completes the proof.
In addition to the above lemma, we leverage the following Lasso convergence result. We state version that can be found in the book on high-dimensional probability due to Rigollet and Hütter 2023
15

---

Lemma C.3 (Theorem 2.18 in Rigollet and Hütter 2023) Suppose that Y = =X0 + where X E RExd 0 E is s-sparee, and e has independent 1-sub- Buu--Gausian coordinates. Further, suppose x is s-incoherent. Then, for any E (0,1) 1) and for X AV log(2 log(2d) + T
4 + log(0
have, with probability at least 1 -
2d 8
110 0 S S C S log
where 0 denotes the solution to the Lasso and C. > 0 is some absolute constant.
Using standard arguments (see the proof of Theorem 2.18 in Rigollet and Hütter [023 the statement of Theorem 7.3 in Wainwright (2019). can be further deduced that | 0 Σ
4/8 0" 0 22, so we actually have that, for any ō E (0, 1), with probability at least 6
2d
10- - 011 S C31
E- log
where again some absolute constant.
C.2 Proof of Theorem 5.1
Proof. Define N E On- Recall the notation 0 = N-1 >
θn. and
arg a (0, x(a)). For any round t {E L, T), greedily play the action à. The average reward 7(ā) can be bounded using the definition of and Holder's inequality follows,
F(a") a(a) (0, x(xx(aa)) x(a))
= (0 - 00-0xx(aa) x(a)) + (0, x(,x(a") x(a)
50
(0 - 0, x(a) x(ā))
0 0111)x((")) - x(a)loo.
Next, substituting the definition of 0, ||x(a)l = and using the triangle incquality into the equation above gives us,
N
8..)
-(a")-F(a)
< 2
011 2
Σ
0,
N n=1
2 N
On 0n
(5)
==1
Let us define the "good" events by
<NNAN
G = (X is A A and G2 = Yn E [N].10,, - -0 S CA*
F--1 lollog
where C 0 is the constant following the discussion of Lemma C.3
Let us define the global "good"
event by G = G1 Gz. We show P(G) > 1- 6.
First, there is universal constant C² > 0 such that E 4096.42e [log(4/8) + 2N log(A) when T 2 C* 2 (ooo (oo]())) Thus, by Lemma C.2 we know the matrix X with x *
as its rows is A inccncchernnt least $. i.c. IPG,)
Next, conditioning G and applying Lemma
C.3 alongside union bound over the N units yields
4N.4N
@0 - s CA'
E-
E-1
16

---

é Thus, in total, we have P(G) = P(G)) G.) 2 (1 - 8/2)² 2 1 8. We assume we are operating on the good event
for all n [N] with probability at least
2 i.. P(G2 G1) 2 1-
G going forward.
Plugging the per-unit & norms into
( the cumulative regret can be upper bounded with probability
1- follows:
RegT
(F(a") F(ā))
(F(a") -(()))
Σ ((a")-F(83)
(=++1
N
2T
On 6m 0.11,
E +
N
n=1
4N.NN
E 2CT
A
E-1
log log
6
Clearly, we should select E to roughly balance terms (up to multiplicative constants). In particular, using the choice of E
IN 8
1/3
E (TA*)2/3
log
+ N (og(A))
and substituting E' into 6 gives
Regr < <0 ( ( (oN
with probability at least
-- 8. precisely the claimed result.
17

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: in the abstract/introduction,, we claim that we contribute (a) a framework for studying bandits with sparse interference, (b) algorithms for obtaining low regret under this framework, and (c) simulations to empirically back up our theoretical findings. We present these, respectively, in Section 3, Sections 4 and 5, and Section 6 of our paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
NA answer to this question will not be 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.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss many shortcomings of our contributions, For instance, note that in the known interference setting, our main algorithm obtains a dependence on the time horizon that grows as T2/3, whereas one would ideally hope for 7 dependence. We also address computational aspects of the Lasso in Section 5 providing heuristic approaches for speedup.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged 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.
18

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We detail all of our assumptions either in Section 3 or in the statements of theorems. We also provide full, rigorous proof of our results in the appendices.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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 complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We fully describe our theoretical framework, and painstakingly detail all algorithms, including how choose free parameters. In our experimentation section, provide full details on our setup.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not 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 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 a specific model and empirical evaluation, it may be necessary either make it possible for others 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 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution 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).
19

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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 faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have attached our code as a supplement so is viewable by reviewers. We have redacted written where the link the repo will be included upon acceptance.
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 encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. http//uublcggguueeeeee hotooi///gddee//eeeeubbbis hat////ooouuiissseeeeeeeeee ssionPolicy for more details.
The authors should provide instructions 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, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We fully describe our simulations in Section in work.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
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: We provide error bars for our simulation results and we describe the methodol- ogy by which we produce our error bars.
Guidelines:
20

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 out of range (e.g. negative етror 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 the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our experiments are extremely lightweight and can be run any modern laptop.
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 as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make 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 http:///wwrrrppppccutcc/e/e/////
Answer: [Yes]
Justification:
We have read the code ethics and have found no violations in our work.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
21

---

Justification:
There are no negative societal impacts of our work. We have mentioned as positive societal impacts upplicability of our results tasks such medical trials.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point 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 is being used as intended but gives incorrect results, and harms following from (intentional 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not produce any models or release any data that may be misused.
Guidelines:
The answer NA means that the paper poses no 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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
We do not use existing assets in our work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
22

---

The name of the license (e.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 palasets.paperssttt paperssi thcode. com con/datases package should be provided. For popular 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.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce any new assets in our work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We not use crowdsourcing nor do we conduct research with human subjects.
Guidelines:
The answer NA means that the paper does 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 in the main paper.
According the NeurlPS 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: Same as the justification for the above bullet point.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
23

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "wCEq7Nq3ZZ", "reviewer": "Reviewer_ctjH", "summary": "The paper tackles a multi-armed bandit problem where there is interference that can be modeled by a network. The interference model assumes that a unit's treatment effect is affected by the treatments assigned to its neighbors in the network model. This interference model implies that in the worst case there are $\\mathcal{A}^{N}$ possible combination of arms to be pulled each round which makes the regret minimization analysis difficult using existing techniques. To tackle this challenge, the paper studies the sparse network interference model and uses discrete Fourier analysis to show the unit-specific reward can learned using sparse linear regression-based algorithms. They provide a regret minimization algorithm for the setting where the interference model is explicitly known and for the setting where it is unknown. They conclude the paper numerical simulations to corroborate their theoretical findings.", "questions": "1. Does the sparse network model effectively capture interference effects that decay depending on how related two units are? For example, unit $i$ is weakly related to units $1, \\dots, K$ so that the arm assignment for one these units has a small effect, but aggregated over all $K$ units has a large effect. \n2. If only a portion of neighbors is revealed for unit $i$, do you use Algorithm 1 or Algorithm 2?", "limitations": "Authors have adequately addressed limitations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written with ample discussion of the background, notation, set-up, theorems, and relation to existing work. As a result the paper is easy to understand and able to highlight its contributions.\n\nContribution-wise, the paper considers a relevant multi-armed bandit with interference setting and is able to consider a richer class of actions compared existing work. The assumption that the interference network is sparse seems reasonable and intuitive given the real-world settings discussed in the paper. The regret bounds presented seem intuitive and are able to effectively leverage the sparse network structure. The paper's contributions provide a good generalization of network interference that can be used in future work.", "weaknesses": "One potential weakness of the paper is that it provides limited proof sketches on results related leveraging the sparse network. Intuition on how the proof technique works may be useful for readers interested in utilizing similar assumptions for future research. \n\nThe paper also only briefly touches upon settings where the graph is partially observed. The prescribed solution in these settings is to use the fully observed algorithm if \"all\" the neighbors of the unit are observed and to use the unobserved algorithm if the neighbors are not observed. It still seems unclear what should happen if only \"some\" of the neighbors are observed. Perhaps additional detail can be added to clarify.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses:**\n\n_One potential weakness of the paper is that it provides limited proof sketches on results related leveraging the sparse network._\n\nWe agree that a proof sketch would help the reader better understand our algorithm and its convergence. If accepted, we will use the additional page to add brief proof sketches following the theorem statements.\n\n_The paper also only briefly touches upon settings where the graph is partially observed. The prescribed solution in these settings is to use the fully observed algorithm if \"all\" the neighbors of the unit are observed and to use the unobserved algorithm if the neighbors are not observed. It still seems unclear what should happen if only \"some\" of the neighbors are observed. Perhaps additional detail can be added to clarify._\n\nIf only some of the neighbors are observed, or if the practitioner has any doubt about whether a given edge is present in the graph/network, it is likely best practice to use the Algorithm 2 (i.e. the algorithm for the fully-unobserved graph case). We note that both in theory and in our simulations, the performance of this algorithm is not much worse than that of Algorithm 1. Moreover, we emphasize that neither the fully or partially observed settings have been studied before this paper. While it may be possible to derive algorithms for particular forms of unobserved structure, it falls outside of the scope of our work. We have added clarification about this point in the paper.\n\n**Questions:**\n\n_Does the sparse network model effectively capture interference effects that decay depending on how related two units are?_\n\nOur paper considers a worst-case setting in which the reward/outcomes associated with each unit can depend arbitrarily on the treatments assigned to its neighbors. We believe that better regret rates are possible if additional structure is assumed, e.g. that the reward satisfies a “bounded difference” property and is not very sensitive to a change in treatment for any given individual unit. Deriving algorithms that can leverage additional structural assumptions is likely a non-trivial task, so we leave it for future work.\n\n_If only a portion of neighbors is revealed for unit i, do you use Algorithm 1 or Algorithm 2?_\n\nIn this case, the learner should use Algorithm 2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "RqZc9ybDqb", "reviewer": "Reviewer_RoeT", "summary": "This paper introduces a Multi-Armed Bandits framework to address the challenge of online experimentation with network effects. Specifically, the authors consider a learner sequentially assigning one type of $\\mathcal{A}$ actions to $N$ units over $T$ periods to minimize the regret. The reward from each unit depends not only on the action it received but also on the actions its neighbors received, i.e., there is interference across the underlying network of units. The contribution of this paper is as follows:\n\n- Using Boolean encoding and Fourier series of Boolean functions, the authors re-express the reward function of each unit as a linear function of the Fourier basis. Then, they propose a simple 'explore-then-commit' style algorithm to address the challenge of the MAB problem with network interference.    \n\n- With known interference, i.e., the underlying neighbors of each unit are known by the learner, the authors show that their proposed 'explore-then-commit' type algorithm possesses a sublinear regret in $T$ and $N$.    \n\n- With unknown interference, the authors use LASSO to estimate the parameters on the Fourier basis, and establish a similar sublinear regret. The authors also argue the scaling of $T$ in their regret bound cannot be improved.\n\n- Numerical simulations validate the effectiveness of the proposed algorithms and show they outperform the UCB baseline.", "questions": "The authors studied the interference over the underlying network of units, I wonder if it's possible to consider the impact over time, i.e., the reward may rely on previous actions that its neighbors received, for example, the impact decays exponentially over time.", "limitations": "The limitations are well addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is very clear and well-written.\n- The analysis is sound and well-discussed for all the limitations\n- The discrete Fourier decomposition requires a deep understanding and keen observation of the problem.\n- Although the algorithm follows a simple 'explore-then-commit' style, the analysis is non-trivial and possesses theoretical and technical difficulties.\n- The regret is both sublinear in $N$ and $T$, and also $\\mathcal{A}^s$ where $s$ is the degree of neighbors.", "weaknesses": "- I feel it's not common to see $\\mathcal{A}$ to denote a number rather than the action set.\n- The Boolean encoding of the actions is not well-discussed.\n- In Fig 2(b), it seems that the regret stops accumulating when $T$ is larger enough. Is it true? Could you give a discuss why it happens?\n- There are some typos of notations, for example, on page 4, (2) Simple orthonormal basis, the authors used $\\mathcal{F}_{bool}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses:**\n\n_The Boolean encoding of the actions is not well-discussed._\n\nThank you for helping us improve the exposition of our paper! We provide a simple example of (a) binary action embeddings and (b) the corresponding Fourier embeddings below. Further, we describe how the Fourier representation naturally captures our sparse network interference assumption unlike other potential representations. This example can be found in the response to all reviewers above, but we discuss it here for convenience. We will also revise the paper to reflect this example. \n\n$\\textbf{Binary action embedding}$. Consider $N$ units with 2 arms ($\\mathcal{A} =2$), and a network graph $\\mathcal{G}$ such that each unit $n$ is connected to one other unit, i.e., $\\mathcal{G}$ has maximum degree 2. An action $\\mathbf{a} = (a_{1}, \\ldots a_{N}) \\in \\\\{0,1\\\\}^N$, will induce the binary embedding $\\mathbf{v}(\\mathbf{a}) =  (v(a_1), \\ldots v(a_N)) \\in \\\\{-1,1\\\\}^N$ where $v(a_i) = 1$ if $a_i$ is 1 and -1 if $a_i = 0$. For example, if $\\mathbf{a} = (0,1,1 \\ldots 1)$, then $\\mathbf{v}(\\mathbf{a}) = (-1,1,\\ldots,1)$.\n\n$\\textbf{Fourier embedding}$. For any subset of units $ S \\subset [N]$, the Fourier character $\\chi_{S}(\\mathbf{v}(\\mathbf{a})) = \\prod_{i \\in S} v(a_i)$. For instance, if the action $\\mathbf{a} = (0,1,1 \\ldots 1)$ as above, and the subset $S = \\\\{1,2\\\\}$, the Fourier character  $\\chi_{\\\\{1,2\\\\}}(\\mathbf{v}(\\mathbf{a}))  =  v(a_1) \\times v(a_2) = -1$. The vector of Fourier characteristics $\\boldsymbol{\\chi}(\\mathbf{a}) = (\\chi_{S}(\\mathbf{v}(\\mathbf{a})) : S \\subset N) \\in \\\\{-1,1\\\\}^{2^N}$  is the concatenation of all Fourier characters for all subsets. \n\n$\\textbf{Fourier coefficient}$. Since each unit $n$ is only connected to one other unit $m$, unit n's neighborhood $\\mathcal{N}(n) = \\\\{n,m\\\\}$ for a unit $m \\neq n$. For unit $n$, the blocks $\\mathcal{B}(n)$ are the indices of $\\mathbf{v}(\\mathbf{a})$ corresponding to treatments of units in $\\mathcal{N}(n)$. For our network graph $\\mathcal{G}$, $\\mathcal{B}(n) = \\\\{v(a_n), v(a_m)\\\\}$. The subsets $S \\in \\mathcal{B}(n) = \\\\{\\phi, \\\\{n\\\\}, \\\\{m\\\\}, \\\\{n,m\\\\} \\\\}$ correspond to the non-zero coefficients of unit n's Fourier coefficient $\\boldsymbol{\\theta}_{n} \\in \\mathbb{R}^{2^{N}}$.  \n\n$\\textbf{Fourier basis captures sparsity}$.  Since $\\boldsymbol{\\theta}_{n}$ is 4-sparse, the reward $r_n (\\mathbf{a}) = \\langle \\boldsymbol{\\theta}_n, \\boldsymbol{\\chi} (\\mathbf{a}) \\rangle$ for unit $n$ can be represented using 4 Fourier characters: $\\\\{\\chi\\_{\\phi}, \\chi\\_{n}, \\chi\\_{m}, \\chi\\_{\\\\{n,m\\\\}} \\\\}$.  This representation captures sparsity unlike a 'one-hot' representation where the reward for unit $n$ can be represented as $r_n (\\mathbf{a}) = \\sum\\_{\\mathbf{a}' \\in \\\\{0,1\\\\}^N}r_n(\\mathbf{a}') \\mathbf{1}[\\mathbf{a} = \\mathbf{a}']$. This one-hot basis also linearly expresses the reward but requires $2^N$ indicator basis vectors to do so.\nIt is precisely this sparse linear representation induced by the Fourier basis that allows our bounds to scale with $2^s$ rather than $2^N$. \n\n\n_In Fig 2(b), it seems that the regret stops accumulating when T is larger enough. Is it true? Could you give a discuss why it happens?_\n\nThe regression algorithm (either OLS in the case of Algorithm 1 or the Lasso in the case of Algorithm 2) estimates the unknown global reward function with a high-degree of accuracy at the end of the exploration phase. In more detail, we have that (with high probability) $|\\widehat{r}(a) - \\bar{r}(a)| < \\epsilon$ for all actions $a$, where $\\epsilon$ is some small value denoting the width of the confidence interval. In the case that the suboptimality gap (i.e. the gap in reward between the best and second best action) is smaller than $\\epsilon$, we are guaranteed to select the optimal action. That is, we incur zero regret during the exploitation phase. \n\n\n**Questions:**\n\n_The authors studied the interference over the underlying network of units, I wonder if it's possible to consider the impact over time, i.e., the reward may rely on previous actions that its neighbors received, for example, the impact decays exponentially over time._\n\nWe believe investigating the effects of an entire history of treatments on the current period is both interesting and practically-relevant. Given that the current approach for estimating rewards depends heavily on the unknown, unit-specific reward functions being fixed over the rounds of interaction, additional machinery would almost surely need to be developed to handle this generalization. Here is perhaps one possible approach:\n-  If the dependence of present reward (say in round $t$) on historical treatments decays geometrically, it may be possible to “extend” the action space to tuples of actions played over the past $s$ rounds (i.e. tuple of the form $(a_t, a_{t - 1}, \\dots, a_{t - s})$. We can then suffer some “truncation” error for ignoring the given treatments in rounds $t -s -1, t-s -2$, etc. This truncation error can be computed based on the geometric rate of decay, and $s$ can likely be chosen with respect to the time horizon $T$ to obtain small regret. Additionally, machinery from the reinforcement learning literature may be applicable to handling time-dependent rewards. We note that both aforementioned approaches fall outside of the scope of this paper, and thus we leave them for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "CwTJTpOTjB", "reviewer": "Reviewer_zUP1", "summary": "This article studies the multi-armed bandit (MAB) problem under unit interference. This unit inference problem is often considered in offline settings. This article extends it to online settings with a linear regression solution based on discrete Fourier features. Two Explore-Then-Commit algorithms are proposed to minimize regret under known and unknown interference, respectively. Finally, the algorithms are tested on some numerical simulations.", "questions": "N.A.", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is relatively well-written and easy to follow. \n2. It is interesting to study the interference problem in online settings\n3. The linear regression solution based on Fourier features seems novel.", "weaknesses": "1. The paper lacks real examples to demonstrate the combination of online experimentation and interference. Perhaps the combination is as natural as the paper suggests. For example, In online experimentation, after every action, it may take some time for the interference to occur.  If we measure the outcome right after the action, it may provide no information about the effect of interference on the reward.\n2. The paper should discuss Assumption 2 more. For example, the upper bound s needs to hold for all units n. Suppose s is very large or small. It is unclear how this affects the algorithms presented later.\n3. It is unclear if we can apply the offline methods under interference to online settings. Maybe we could use these methods to estimate the reward function at every step and then take action by maximizing the reward function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses:**\n\n_The paper lacks real examples to demonstrate the combination of online experimentation and interference. Perhaps the combination is as natural as the paper suggests. For example, In online experimentation, after every action, it may take some time for the interference to occur. If we measure the outcome right after the action, it may provide no information about the effect of interference on the reward._\n\nA concrete example is given by online bidding in advertisement; the “agent” here is a centralized platform that coordinates at each round bids coming from N advertisers. Advertisers submit bids and compete in an auction: winning advertisers get to display the ad. Treatments here correspond to different pricing schemes imposed by the platform. For example, two different treatments might correspond to different reserve prices imposed on advertisers (e.g., a higher or lower premium paid at ad-display time). The reward function measures the downstream conversions driven by ads. Here, it is natural to assume that the reward for one advertiser will only be impacted by the behavior (impacted by the treatment) of a subset of the total population of advertisers, e.g., direct competitors.\n\n_The paper should discuss Assumption 2 more. For example, the upper bound s needs to hold for all units n. Suppose s is very large or small. It is unclear how this affects the algorithms presented later._\n\nOur algorithms leverage knowledge of the sparsity (or at least an upper bound on the sparsity s) in determining the length of the exploration period. As noted in Remark 4.6 in [1], we can select the length of the exploration period to be _independent_ of the sparsity, but we will pay an additional cost in regret of $O(A^{s/3})$. We have added a comment noting this in the appropriate sections. If one is concerned about practical applications of our algorithms, cross-validation can be used to select the length of the exploration period, as outlined in our remark at the end of Section 4. We also note that such sparsity assumptions are common in both network causal inference literature and the high-dimensional statistics literature.\n\n_It is unclear if we can apply the offline methods under interference to online settings. Maybe we could use these methods to estimate the reward function at every step and then take action by maximizing the reward function._\n\nWe note that the goals of problems considered in the offline setting are not the same as those considered in the online setting. In the offline setting, the goal of the learner is typically to (a) estimate some sort of treatment effect in the presence of network interference and (b) produce a confidence interval/set for the parameter estimate. The experiments designed to accomplish these tasks often involve uniform/random exploration over the entire time period, and thus would yield linear regret. In the online setting, we want to minimize regret. While we do estimate the underlying global reward functions, this is just a nuisance parameter in our setting. What we really care about is (a) quickly discovering a (nearly) action and (b) exploiting this action over many time steps. This difference is what necessitates different algorithms.\n\n[1] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in\nNeural Information Processing Systems, 33:10753–10763, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "naxrmqCG01", "reviewer": "Reviewer_QVLr", "summary": "The paper investigates a multi-armed bandit problem on a set of units that affect the rewards of each other. A trivial solution will have an exponential regret in the number of units, so using sparsity assumptions on the affecting neighborhood, the authors present an algorithm with regret that is only exponential in the sparsity coefficient. The authors present algorithms both for the case that the affecting neighborhood is known to the agent and the case that it is unknown.", "questions": "* it seems you did not use the correct format for the submission (as their are no line numbers), make sure you correct this\n* in the definition of \"Linear Fourier expansion\", should be $S \\subset$ instead of $S \\in$, right?\n* In your algorithms, can you clarify the running time of finding the minimizing coefficient vector?\n* In Theorem 4.1, should be $\\mathcal{A}$ instead of $A$?", "limitations": "The authors properly address the limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper presents and solves a useful problem in practice\n* The theory is sound and the methods are original for network MAB, specifically learning the orthonormal coefficients is clever", "weaknesses": "On the one hand, Algorithm 1 performs well only when $N$ is very large (otherwise its better to use Algorithm 3), but it also has a running time of $\\Omega(N)$, so it seems bad either way. Not sure why the focus is not on Algorithm 3 instead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses:**\n\n_On the one hand, Algorithm 1 performs well only when $N$ is very large (otherwise its better to use Algorithm 3), but it also has a running time of $\\Omega(N)$, so it seems bad either way. Not sure why the focus is not on Algorithm 3 instead._\n\nWe chose to focus Section 4 on Algorithm 1 due to its simplicity and its similarity to the algorithm in the unknown interference structure case. We agree that Algorithm 3 likely offers a bound on regret in most parameter settings. For the final draft, we have added additional exposition about Algorithm 3 in Section 4 to better contrast the two approaches to regret minimization. In particular, we have added a theorem statement following the theorem statement for the “explore then commit” style algorithm.\n\n\n**Questions:**\n\n_Various typos and formatting issues_\n\nThank you for pointing out the various typos and the issue with our paper's formatting. We have corrected these issues for the final draft of the paper.\n\n_In your algorithms, can you clarify the running time of finding the minimizing coefficient vector?_\n\nThe runtime of finding the minimizing coefficient vector (i.e., $\\hat{\\mathbf{\\theta}}_n$) is equivalent to solving an ordinary least squares or Lasso for $N$ units when the graph structure is known and unknown respectively. There exists efficient gradient-based algorithms for solving these linear programs. We note that our algorithms are designed such that each of these linear programs can be solved in parallel for each unit independently which significantly reduces runtime.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "bMzJm6O3RT", "reviewer": "Reviewer_Ry93", "summary": "The paper addresses the challenge of online experimentation in the presence of network interference, which is common in applications like e-commerce and clinical trials. The authors propose a multi-armed bandit (MAB) problem where a learner assigns actions (e.g., discounts) to\nunits (e.g., goods) over fixed and known rounds to minimize regret while considering the interference across units. However, naively applying canonical MAB methods (e.g., the upper-confidence-bound algorithm) will lead to regret with the exponential dependence on the number of units. \n\nThe main challenge of the paper is the exponentially large action space (each unit has |A| actions and thus |A|^n in total per round). The sparsity structure of the interference (each unit can only be affected by at most s neighboring units) implies that the effective action space for each unit can be a lot smaller. The paper designs an encoding scheme and an algorithm based on this observation. They show that the optimal regret in both $T$ and $|A|$ can be obtained.", "questions": "The paper takes an agnostic approach to the network structure. This is the strength of the algorithm. However, I wonder if there is room for the network structure. For example, it doesn't seem possible for the algorithm to incorporate some network information such as clusters and stars. Is it possible to adapt the algorithm to certain graphs?\n\nETC is known to be not rate-optimal. I wonder why the authors don't use LinUCB algorithmsin linear bandit at the first place. The problem can be viewed as linear bandit with a very large space, correct?\n\nIn Step 10 of Algorithm 1, how can the optimization problem be solved in practice given the large space?", "limitations": "See **Questions**.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think the paper proposes an interesting problem to study. The problem is practical, well-motivated and mathematically elegant.The sparsity structure is also common and reasonable to assume. I enjoy reading the paper and learning about the problem.\n\nThe transformation to the linear space of functionals is interesting. It leads to the use of statistical bounds in high-dimensional statistics to be applied, which gives tight regret bounds. \n\nI also like the use of LASSO to identify the interference strucuture. I believe this method may be of independent interest.\n\nThe algorithm and the theoretical results are presented clearly. The proof is written carefully and easy to read.", "weaknesses": "Although the formulation is interesting, the algorithm design and analyses seem quite standard. After transforming to the functional space, it becomes the MAB problem with effectively $|A|^s$ arms. The ETC algorithm and the analysis of the estimation error as well as the regret have been studied in the literature. I wonder if the formulation alone is sufficient as the contribution of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses:**\n\n_Although the formulation is interesting, the algorithm design and analyses seem quite standard. After transforming to the functional space, it becomes the MAB problem with effectively $A^s$ arms. The ETC algorithm and the analysis of the estimation error as well as the regret have been studied in the literature. I wonder if the formulation alone is sufficient as the contribution of the paper._\n\nWe believe there are several main contributions to our paper outside of the formulation, which we enumerate below.\n- First, as mentioned in the reviewer’s comment, the Fourier embedding of the unit-specific rewards is non-obvious and hasn’t been considered before in related literature. \n- Second, once we have performed the transformation using the discrete Fourier transform, the problem is not just a MAB instance with $A^s$ arms, but rather $N$ simultaneous multi-armed bandit instances, each having $A^s$ arms. Thus, an additional step we must take in our argument (and a step that isn’t considered in more classical approaches to ETC) is that we must aggregate our confidence sets for unit-specific reward functions into a corresponding confidence set for the global reward. \n- Third, we also provide a sequential elimination style algorithm which can obtain improved dependence on the time horizon $T$ in the regret bound. In particular, this style of algorithm gets the same dependence on $T$ as a UCB algorithm would.\n\n**Questions:**\n\n_The paper takes an agnostic approach to the network structure. This is the strength of the algorithm. However, I wonder if there is room for the network structure. For example, it doesn't seem possible for the algorithm to incorporate some network information such as clusters and stars. Is it possible to adapt the algorithm to certain graphs?_\n\nIn our paper, we consider a minimal assumption setting in which all we know is a bound on the size of the neighborhood of each unit. We opt not to make additional structural assumptions on the network (e.g. clusters, stars, etc.) for the sake of simplicity and generality. We believe that better regret rates may be able to be achieved by making structural assumptions (for instance, in this case we may be able to regress against low-degree polynomials in the Fourier space), but this is outside of the scope of the paper.\n\n_ETC is known to be not rate-optimal. I wonder why the authors don't use LinUCB algorithms in linear bandit at the first place. The problem can be viewed as linear bandit with a very large space, correct?_\n\nIn the setting of unknown network structure (Section 5 of our paper), the given dependence on the time horizon $T$ is optimal (i.e. no algorithm can generally achieve dependence better than $O(T^{2/3})$). See [1] for details, as the authors construct a lower bound. In the setting of known network interference (Section 4 of our paper), we actually provide a sequential-elimination algorithm (Algorithm 3 in Appendix D) that obtains optimal regret dependence on the time horizon T (a rate of $O(T^{1/2})$). While we could additionally consider a UCB-style algorithm, this would likely be more difficult to analyze, and wouldn’t improve the regret rate, at least with respect to the time horizon $T$ (sequential elimination and LinUCB achieve the same rate). We re-emphasize that, even after mapping to the frequency space, we still are not in a vanilla linear bandit problem — we are actually in a setting where there are $N$ simultaneous, related bandit instances.\n\n_In Step 10 of Algorithm 1, how can the optimization problem be solved in practice given the large space?_\n\nComputing the optimal action is equivalent to just finding the maximum in a large list (a trivial optimization problem for modern computers). We note that at this point in the algorithm there are no constraints on the selected action.\n\n[1] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753–10763, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "o8NTTFaV9S", "reviewer": "Reviewer_JzLc", "summary": "The paper explores regret minimization in multi-armed bandits subject to interference. At each time, the learner assigns one of A treatments to each of the N arms. The observed per-arm response is subject to interference – ie, it depends on the assignments of all the other arms. This work studies the setting of s-sparse interference, where only the assignment of s \"neighbors\" of the arm affect its outcome. The paper's main theoretical contribution is to use discrete Fourier analysis to rewrite this problem as a linear bandit, then solve that bandit using tools from the linear bandits literature. An explore-then-commit algorithm is proposed that achieves a high-probability regret bound of (T A^s)^(⅔), with only logarithmic dependence on N.", "questions": "I'd like to make sure I understand the notation in this paper. Could the authors please provide, for a small toy example, numerical examples of the following vectors from Algorithm 1? $\\bf{a_i}$ in Line 2, $\\bf{\\chi}(\\bf{a_t})$ in Line 3, $\\bf{\\chi^{a_i}}(\\mathcal{B}_n)$ in Line 5.\n\nThis paper makes a novel contribution of translating the \"MAB-with-interference\" problem to a linear bandits problem using Fourier analysis. I don't understand why you can't then use existing solutions from the linear bandits literature to solve your problem, and take regret rates from there, instead of rederiving the rates for your own algorithm. Could you please clarify why you cannot apply the linear bandits results mentioned in the introduction to your problem?", "limitations": "The model in the paper is extremely general: a unit's outcomes are dependent on the assignments of all of its neighbors, with no lower-order structure. As a result, the performance of the algorithm scales exponentially in the degree s. In reality I would expect the outcome to depend on lower-order interactions than s. I wonder if the authors have considered what would happen if they allowed the degree of the graph to exceed the order of interactions in the potential outcomes function, as in [1]. In this case a single assignment would give you information on multiple lower-order interaction coefficients. I imagine this would improve the performance of your algorithm significantly in the case where d << s, but the problem will get harder to analyze because the X vectors in your algorithm will now have correlations among the A^s elements of a single row. This will make bounding the singular values of X more difficult.\n\nIf you have space, I would love to see some discussion of how applicable your Fourier Analysis techniques are to these types of stronger modeling assumptions on the potential outcomes.\n\n[1] Cortez, Mayleen, Matthew Eichhorn, and Christina Yu. \"Staggered rollout designs enable causal inference under interference without network knowledge.\" Advances in Neural Information Processing Systems 35 (2022): 7437-7449.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper provides a novel formulation of bandits-with-interference as a linear bandits problem using discrete Fourier analysis. The problem is well-motivated by e-commerce applications, and the methods developed are to my knowledge novel. The paper is well-written, and provides thorough exposition of the results.", "weaknesses": "It took me a long time to realize that the effects were being estimated on a per-subset basis – ie, that chi^{a_i}(B(n)) is an indicator vector for the subset a_i intersected with the neighborhood of n. Originally I thought that chi^{a_i}(B(n)) =1 for all subsets of a_i, so I was very confused why we didn't have to worry about dependence among the entries of chi. If the authors can think of any way to clarify the exposition, I would greatly appreciate it. This is probably obvious to someone who is more familiar with Boolean Fourier analysis, but your readers may not be.\n\nThis paper is very well-written. One thing that was missing from the exposition was an explanation of what the Fourier analysis buys us in this setting. What did the Fourier approach allow you to do in this problem that was not available using previous methods (for example, methods people have applied to combinatorial bandits)? From reading your appendices, I think the answer might be that the orthogonality of the basis functions makes it easy to bound the precision of theta. If you could clarify this it would help your method be adopted by a wider audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses:**\n\n_It took me a long time to realize that the effects were being estimated on a per-subset basis – ie, that chi^{a_i}(B(n)) is an indicator vector for the subset a_i intersected with the neighborhood of n. Originally I thought that chi^{a_i}(B(n)) =1 for all subsets of a_i, so I was very confused why we didn't have to worry about dependence among the entries of chi. If the authors can think of any way to clarify the exposition, I would greatly appreciate it. This is probably obvious to someone who is more familiar with Boolean Fourier analysis, but your readers may not be._\n\nThank you for helping us improve the exposition of our paper! We provide a simple example of (a) binary action embeddings and (b) the corresponding Fourier embeddings below. We will also revise the paper to reflect this example. \n\n$\\textbf{Binary action embedding}$. Consider $N$ units with 2 arms ($\\mathcal{A} =2$), and a network graph $\\mathcal{G}$ such that each unit $n$ is connected to one other unit, i.e., $\\mathcal{G}$ has maximum degree 2. An action $\\mathbf{a} = (a_{1}, \\ldots a_{N}) \\in \\\\{0,1\\\\}^N$, will induce the binary embedding $\\mathbf{v}(\\mathbf{a}) =  (v(a_1), \\ldots v(a_N)) \\in \\\\{-1,1\\\\}^N$ where $v(a_i) = 1$ if $a_i$ is 1 and -1 if $a_i = 0$. For example, if $\\mathbf{a} = (0,1,1 \\ldots 1)$, then $\\mathbf{v}(\\mathbf{a}) = (-1,1,\\ldots,1)$.\n\n$\\textbf{Fourier embedding}$. For any subset of units $ S \\subset [N]$, the Fourier character $\\chi_{S}(\\mathbf{v}(\\mathbf{a})) = \\prod_{i \\in S} v(a_i)$. For instance, if the action $\\mathbf{a} = (0,1,1 \\ldots 1)$ as above, and the subset $S = \\\\{1,2\\\\}$, the Fourier character  $\\chi_{\\\\{1,2\\\\}}(\\mathbf{v}(\\mathbf{a}))  =  v(a_1) \\times v(a_2) = -1$. The vector of Fourier characteristics $\\boldsymbol{\\chi}(\\mathbf{a}) = (\\chi_{S}(\\mathbf{v}(\\mathbf{a})) : S \\subset N) \\in \\\\{-1,1\\\\}^{2^N}$  is the concatenation of all Fourier characters for all subsets. \n\n$\\textbf{Fourier coefficient}$. Since each unit $n$ is only connected to one other unit $m$, unit n's neighborhood $\\mathcal{N}(n) = \\\\{n,m\\\\}$ for a unit $m \\neq n$. For unit $n$, the blocks $\\mathcal{B}(n)$ are the indices of $\\mathbf{v}(\\mathbf{a})$ corresponding to treatments of units in $\\mathcal{N}(n)$. For our network graph $\\mathcal{G}$, $\\mathcal{B}(n) = \\\\{v(a_n), v(a_m)\\\\}$. The subsets $S \\in \\mathcal{B}(n) = \\\\{\\phi, \\\\{n\\\\}, \\\\{m\\\\}, \\\\{n,m\\\\} \\\\}$ correspond to the non-zero coefficients of unit n's Fourier coefficient $\\boldsymbol{\\theta}_{n} \\in \\mathbb{R}^{2^{N}}$.  \n\n\n_This paper is very well-written. One thing that was missing from the exposition was an explanation of what the Fourier analysis buys us in this setting. What did the Fourier approach allow you to do in this problem that was not available using previous methods (for example, methods people have applied to combinatorial bandits)? From reading your appendices, I think the answer might be that the orthogonality of the basis functions makes it easy to bound the precision of theta. If you could clarify this it would help your method be adopted by a wider audience._\n\nThe Fourier basis provides a natural sparse linear representation of the network interference which is not easily done in other bases. To see this, we continue the example from the point above.  Since $\\boldsymbol{\\theta}_{n}$ is 4-sparse, the reward $r_n (\\mathbf{a}) = \\langle \\boldsymbol{\\theta}_n, \\boldsymbol{\\chi} (\\mathbf{a}) \\rangle$ for unit $n$ can be represented using 4 Fourier characters: $\\\\{\\chi\\_{\\phi}, \\chi\\_{n}, \\chi\\_{m}, \\chi\\_{\\\\{n,m\\\\}} \\\\}$.  This representation captures sparsity unlike a 'one-hot' representation where the reward for unit $n$ can be represented as $r_n (\\mathbf{a}) = \\sum\\_{\\mathbf{a}' \\in \\\\{0,1\\\\}^N}r_n(\\mathbf{a}') \\mathbf{1}[\\mathbf{a} = \\mathbf{a}']$. This one-hot basis also linearly expresses the reward but requires $2^N$ indicator basis vectors to do so.  It is precisely this sparse linear representation induced by the Fourier basis that allows our bounds to scale with $2^s$ rather than $2^N$. \n\n**Questions:**\n\n_This paper makes a novel contribution of translating the \"MAB-with-interference\" problem to a linear bandits problem using Fourier analysis. I don't understand why you can't then use existing solutions from the linear bandits literature to solve your problem, and take regret rates from there, instead of rederiving the rates for your own algorithm. Could you please clarify why you cannot apply the linear bandits results mentioned in the introduction to your problem?_\n\nWe note that once we have mapped the network bandit problem into the corresponding Fourier basis, we still do not directly have a standard linear bandit problem. In particular, we are consider $N$ separate, simultaneous linear bandit problems (one for each unit), each with $\\mathcal{A}^s$ possible actions. An additional aspect of our analysis is the aggregation of information over the various units to produce an estimate for the global average reward function.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": {}}]

Author rebuttal:
We would like to thank the reviewers for the time spent reviewing our work. We greatly appreciate the feedback and will use it to improve our work.

We want to clarify that we view our primary contributions to be the following.
- A framework for studying multi-armed bandits in the presence of network interference under minimal structural assumptions.
- An embedding our this framework into a setting of $N$ parallel linear MAB instances using aspects of discrete Fourier analysis.
- Simple explore-then-commit and sequential elimination style algorithms that can be used to obtain small regret.


In addition, several reviewers noted that our exposition on the aspects of Fourier analysis necessary for our results was a bit dense. We provide a simple example of (a) binary action embeddings and (b) the corresponding Fourier embeddings below. Further, we describe how the Fourier representation naturally captures our sparse network interference assumption unlike other potential representations. This example can be found in the reviews below, but we discuss it here for convenience. We will also revise the paper to reflect this example. 

$\textbf{Binary action embedding}$. Consider $N$ units with 2 arms ($\mathcal{A} =2$), and a network graph $\mathcal{G}$ such that each unit $n$ is connected to one other unit, i.e., $\mathcal{G}$ has maximum degree 2. An action $\mathbf{a} = (a_{1}, \ldots a_{N}) \in \\{0,1\\}^N$, will induce the binary embedding $\mathbf{v}(\mathbf{a}) =  (v(a_1), \ldots v(a_N)) \in \\{-1,1\\}^N$ where $v(a_i) = 1$ if $a_i$ is 1 and -1 if $a_i = 0$. For example, if $\mathbf{a} = (0,1,1 \ldots 1)$, then $\mathbf{v}(\mathbf{a}) = (-1,1,\ldots,1)$.

$\textbf{Fourier embedding}$. For any subset of units $ S \subset [N]$, the Fourier character $\chi_{S}(\mathbf{v}(\mathbf{a})) = \prod_{i \in S} v(a_i)$. For instance, if the action $\mathbf{a} = (0,1,1 \ldots 1)$ as above, and the subset $S = \\{1,2\\}$, the Fourier character  $\chi_{\\{1,2\\}}(\mathbf{v}(\mathbf{a}))  =  v(a_1) \times v(a_2) = -1$. The vector of Fourier characteristics $\boldsymbol{\chi}(\mathbf{a}) = (\chi_{S}(\mathbf{v}(\mathbf{a})) : S \subset N) \in \\{-1,1\\}^{2^N}$  is the concatenation of all Fourier characters for all subsets. 

$\textbf{Fourier coefficient}$. Since each unit $n$ is only connected to one other unit $m$, unit n's neighborhood $\mathcal{N}(n) = \\{n,m\\}$ for a unit $m \neq n$. For unit $n$, the blocks $\mathcal{B}(n)$ are the indices of $\mathbf{v}(\mathbf{a})$ corresponding to treatments of units in $\mathcal{N}(n)$. For our network graph $\mathcal{G}$, $\mathcal{B}(n) = \\{v(a_n), v(a_m)\\}$. The subsets $S \in \mathcal{B}(n) = \\{\phi, \\{n\\}, \\{m\\}, \\{n,m\\} \\}$ correspond to the non-zero coefficients of unit n's Fourier coefficient $\boldsymbol{\theta}_{n} \in \mathbb{R}^{2^{N}}$.  

$\textbf{Fourier basis captures sparsity}$.  Since $\boldsymbol{\theta}_{n}$ is 4-sparse, the reward $r_n (\mathbf{a}) = \langle \boldsymbol{\theta}_n, \boldsymbol{\chi} (\mathbf{a}) \rangle$ for unit $n$ can be represented using 4 Fourier characters: $\\{\chi\_{\phi}, \chi\_{n}, \chi\_{m}, \chi\_{\\{n,m\\}} \\}$.  This representation captures sparsity unlike a 'one-hot' representation where the reward for unit $n$ can be represented as $r_n (\mathbf{a}) = \sum\_{\mathbf{a}' \in \\{0,1\\}^N}r_n(\mathbf{a}') \mathbf{1}[\mathbf{a} = \mathbf{a}']$. This one-hot basis also linearly expresses the reward but requires $2^N$ indicator basis vectors to do so. It is precisely this sparse linear representation induced by the Fourier basis that allows our bounds to scale with $2^s$ rather than $2^N$.

Meta-review: I concur with the reviewers' positive view of the paper and think it will make a great addition to the nascent literature on this emerging interesting problem. I would like to point out to the authors one important misunderstanding regarding the difference between the adversarial and stochastic bandit problems when comparing to the existing literature, and I would like to ask them to fix this when preparing their camera ready version. The setting studied herein has an important difference to that that of Jia et al: in this paper the mean reward is both stationary and stochastic ($r_n(a_1,\dots,a_n)$ is a fixed function that does not depend on $t$ and $\epsilon_{nt}$ is a random variable) whereas in Jia et al the rewards are non-stationary and can be a potentially adversarial (subject to a decaying interference constraint) non-random sequence (written therein as $Y_{ut}$ over $u=1,\dots,N$; the only randomness involved in this problem and the regret analysis is from the user choice of actions). In this way, when $N=1$, the present paper reduces to the standard stochastic bandit (where eg UCB is used) while Jia et al reduces to the standard adversarial bandit (where eg Exp3 is used), hence the problems have quite a different formalism and inherent nature. Therefore, it is not quite correct to say "These results significantly improve upon
previous works on this topic, which impose stronger conditions on a known interference network,
and compare regret to a markedly weaker policy" (page 2). In particular, in the adversarial setup there can be little hope for the regret against the unit-adaptive policy and all the emerging non-trivial phenomena are exactly because one compares to the unit-constant policy. Given that this is an emerging problem it would be great for the authors to discuss and explain these connections/differences so the reader can fully understand the emerging landscape well. I trust this is do'able within the scope of preparing a camera ready as it only involves small edits and adding some more discussions.
Decision: Accept (poster)