Mutli-Armed Bandits with Network Interference

Authors: abhineet  agarwal
u c berkeley
anish  agarwal
lorenzo  masoero
justin  whitehouse
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:03:37

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.

Main paper: 
 introduction: 
 Online experimentation is an indispensable tool for modern decision-makers in settings ranging from e-commerce marketplaces [Li et al., 2016] to adaptive clinical trials in medicine [Durand et al., 2018] . Despite the wide-spread use of online experimentation to assign treatments to 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 is, there is interference across the underlying network of units. For example, in e-commerce, the revenue for a given good depends on discounts applied to related or competing goods. In medicine, an individual's risk of disease depends not only on their own vaccination status but also on that of others in their network. Figure 1 : A visual representation of sparse network interference. In this toy example, we have N = 9 units, and visualize the interference pattern. For unit 2 (orange), its outcomes are affected by the treatments of its neighbours (blue) N (2) = {1, 2, 3, 6, 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 a learner (online marketplace) assigns one of possible A ∈ N actions (varying discounts) to N units (goods) over T rounds to minimize average regret. In our setting, the reward of a unit n ∈ [N ] := {1, . . . , N } depends on the actions assigned to other units. 2 With N units and A actions, achieving low regret is difficult since there are A N possible treatment assignments. Naively applying typical MAB methods such as the upper confidence bound (UCB) algorithm [Auer et al., 2002] leads to regret that scales as O( √ A N T ), which can be prohibitively large due to the exponential dependence on N . Further, without any assumptions on the interference pattern, regret scaling as Ω( √ A N T ) is unavoidable due to 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 interference, where the reward r n : [A] N → R for unit n is affected by the treatment assignment of at most s other units, i.e., neighbours. See Figure 1 for a 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 s 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 n ∈ [N ], we use the Fourier analysis of discrete functions to re-express its reward r n : [A] N :→ R as a linear function in the Fourier basis with coefficients θ n ∈ R A N . We show sparse network interference implies θ n is A s sparse for all n ∈ [N ]. This sparse linear representation motivates a simple 'explore-then-commit' style algorithm that uniformly explores actions, then fits a linear model to estimate unit-specific rewards (i.e., θ n ). (ii) With known interference (i.e., the learner knows the s neighbors for all n ∈ [N ]), our algorithm exploits this knowledge to estimate r n by performing ordinary least squares (OLS) locally (i.e., per unit) on the Fourier basis elements where θ n is non-zero. Our analysis establishes regret Õ((A s T ) 2/3 ) for this algorithm.(iii) With unknown interference, we use the Lasso instead of OLS locally which adapts to sparsity of θ n and establish regret Õ(N 1/3 (A s T ) 2/3 ). We argue this T 2/3 scaling cannot be improved. (iv) Numerical simulations with network interference show our method outperforms baselines. munity (see [Bajari et al., 2023] for a thorough overview). Cross-unit interference violates basic assumptions for causal identifiability, invalidating standard designs and analyses. 3 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, Rosenbaum, 2007] , interference neighborhoods [Gao and Ding, 2023 , Ugander et al., 2013 , Bhattacharya et al., 2020 , Yu et al., 2022 , Cen et al., 2022] , in bipartite graphs representative of modern online markets [Pouget-Abadie et al., 2019 , Bajari et al., 2021 , 2023] , in panel data settings [Agarwal et al., 2022] as well as under a general model of interference, generally encoded via "exposure mappings" [Aronow, 2012, Aronow and Samii, 2017] . 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 a known, grid-like interference pattern, where the strength of the interference decays as the ℓ 1 distance between units grows. Moreover, their focus -unlike ours -is on establishing regret rates with respect to 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 Ω( √ #Actions • T ), where #Actions = A N 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., 2012 , 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-commit" style algorithm to uniformly explore actions before using the 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 to linearly represent rewards [Negahban and Shah, 2012 , O'Donnell, 2014 , Agarwal et al., 2023] . This is similar to kernel bandits [Srinivas et al., 2009 , Chowdhury and Gopalan, 2017 , Whitehouse et al., 2024] , which assume there exists a feature map such that the rewards can be linearly represented (non-sparsely) in a high-dimensional reproducing kernel Hilbert space. Also related are stochastic combinatorial bandits [Chen et al., 2013, Cesa-Bianchi and Lugosi, 2012] , in which the action space is assumed to be a subset of {0, 1} N but rewards are typically inherently assumed to be linear in treatment assignments. That is, these works typically assume the reward r = ⟨θ, a⟩ for a ∈ {0, 1} N , with valid actions a often having at most s non-zero components. Our work (with A = 2), considers an arbitrary function r : {0, 1} N → R, but explicitly constructs a feature map via discrete Fourier analysis such that rewards can be represented linearly. 
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, we note that in the known interference setting, our main algorithm obtains a dependence on the time horizon that grows as T 2/3 , whereas one would ideally hope for T 1/2 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 a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. 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, or 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). 
model & background: 
 In this section, we 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.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 ∈ [N ], and rounds t ∈ [T ]. At each time step t, the agent simultaneously administers each unit n action (or treatment) a ∈ [A]. Let a nt denote the treatment received by unit n at time step t, and let a t = (a 1t , . . . , a N t ) ∈ [A] N denote the entire treatment vector. Each unit n possesses an unknown reward mapping r n : [A] N → [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 R nt = r n (a t ) + ϵ nt . Denote the vector of observed rewards as R t := (R 1t . . . R N t ). We assume the following standard condition on the noise ϵ nt .Assumption 1. (ϵ nt : n ∈ [N ], t ∈ [T ]) is a collection of mutually independent 1-sub-Gaussian random variables.Regret. To measure the performance of the learning agent, we define the average reward function r :[A] N → [0, 1] by r(a) = 1 N N n=1 r n (a).Then, for a sequence of (potentially random) treatment assignments a 1 . . . a T , the regret at the horizon time T is defined as the quantityEQUATIONwhere a * ∈ arg max a∈[A] N r(a). In Sections 4 and 5, we provide and analyse algorithms that achieve small regret with high probability.Comparison to other works. Previous works studying network bandits such as Jia et al. [2024] measure regret with respect to the best constant action a ′ := arg max a∈[A] r(a1) where 1 ∈ R N denotes the all 1 vector of dimension N . We compare regret to the optimal action a * ∈ arg max a∈[A] N r(a), which is combinatorially more difficult to minimize since the policy space is exponentially larger (A N vs A). Our setup is also different than the traditional MAB setting since the agent in 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.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 a linear representation of the discrete unit-specific rewards r n : [A] N → [0, 1], which will allow us to leverage well-studied linear bandit algorithms. For the rest of paper, assume A is a power of 2. If instead, if 2 ℓ < A < 2 ℓ+1 for some ℓ ≥ 0, we can redundantly encode actions to obtain A ′ = 2 ℓ+1 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 a ∈ [A] can be uniquely represented as a binary number using log 2 (A) bits. Explicitly, let ṽ(a) = (ṽ 1 (a), . . . ṽlog 2 (A) (a)) ∈ {0, 1} log 2 (A) denote this vectorized binary representation. For ease of analysis, we use the Boolean representation instead v(a) = 2ṽ(a) - A) . Note each action a ∈ [A] N corresponds to a unique Boolean vector v(a).1 ∈ {-1, 1} log 2 A . For a ∈ [A] N , define v(a) = (v(a 1 ), . . . , v(a N )) ∈ {-1, 1} N log 2 (Boolean representation of discrete functions.Let F = {f : [A] N → R} and F Bool = { f : {-1, 1} N log 2 (A)→ R} be the collection of all real-values functions defined on the set [A] N and {-1, 1} N log 2 (A) respectively. Since every a ∈ [A] N has a uniquely Boolean representation v(a) ∈ {-1, 1} N log 2 (A) , the set of functions F can be naturally identified within F Bool . Specifically, any f ∈ F can be identified with the functionf ∈ F Bool 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.(1) Hilbert space. F Bool forms a Hilbert space defined by the following inner product: for any h, g ∈ F Bool , ⟨h, g⟩B = A -N x∈{-1,1} N log 2 (A) h(x)g(x). This inner product induces the norm ⟨h, h⟩B := ∥h∥ 2 B = A -N x∈{-1,1} p h 2 (x).(2) Simple orthonormal basis. For each subset S ⊂ [N log 2 (A)], define a basis function χ S (x) = i∈S x i where x i is the i th coefficient of x ∈ {-1, 1} N log 2 (A) . One can verify that for any S ⊂ [N log 2 (A)], ∥χ S ∥ B = 1, and that ⟨χ S , χ S ′ ⟩ B = 0 for any S ′ ̸ = S. Since |{χ S : S ⊂ [N log 2 (A)]}| = A N , the functions χ S are an orthonormal basis of F bool . We refer to χ S as the Fourier character for the subset S.(3) Linear Fourier expansion of F Bool . Any h ∈ F bool can be expanded via the following Fourier decomposition: h(x) = S⊂[N log 2 (A)] θ S χ S (x), where the Fourier coefficient θ S is given by θ S = ⟨h, χ S ⟩ B . For h ∈ F Bool , we refer toθ h = (θ S : S ⊂ [N log 2 (A)]) ∈ R A Nas the vector of Fourier coefficients associated with it. Forx ∈ {-1, 1} N log 2 (A) , let χ(x) = (χ S (x) : S ∈ [N log 2 (A))]) ∈ {-1, 1} A Nbe the vector of associated Fourier character outputs. For a ∈ [A] N , abbreviate χ S (v(a)) and χ(v(a)) as χ S (a) and χ(a) respectively.The unit-specific reward function r n : [A] N → R can be equivalently viewed as a real-valued Boolean function over the hypercube {-1, 1} N log 2 (A) . That is, r n takes as input a vector of actions a ∈ [A] N , converts it to a Boolean vector v(a) ∈ {-1, 1} N log 2 (A) , and outputs a reward r n (a). From the discussion in Section 3.2, we can represent unit n's reward asr n (a) = S⊂[N log 2 (A)] θ n,S χ S (a) = ⟨θ n , χ(a)⟩, where θ n = (θ n,S : S ⊆ N log 2 (A)) ∈ R A Nis a vector of Fourier coefficients.Without any assumptions on the nature of the interference pattern, achieving low regret is impossible since it requires estimating A N Fourier coefficients per unit. To overcome this fundamental challenge, we impose a natural structure on the interference pattern which assumes that the reward r n only depends on the the treatment assignment of a 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 to similar or related ones. Assumption 2. (Sparse Network Interference) For any unit n ∈ [N ], there exists a neighborhoodN (n) ⊂ [N ] of size |N (n)| ≤ s such that r n (a) = r n (b) for all a, b ∈ {-1, 1} N log 2 A satisfying (a m : m ∈ N (n)) = (b m : m ∈ N (n)).We typically assume that n ∈ N (n), i.e. unit n's reward depends on its own treatment. This model allows for completely arbitrary interference between these s units, generalizing the results of Jia et al. [2024] who allow for interaction between all N units but assume the strength of interference decays with a particular notion of distance between units. Next, we show using our Fourier analytic tools, that Assumption 2 implies that the reward can be re-expressed as a sparse linear model. We prove the following in Appendix A. Proposition 3.1. Let Assumption 2 hold. Then, for any unit n, and action a ∈ [A] N , we have the following representation of the reward r n (a) = ⟨θ n , χ(a)⟩, where ∥θ n ∥ 0 ≤ A s .4 Proposition 3.1 shows sparse network interference implies θ n is A s sparse with non-zero coordinates corresponding to the interactions of treatments between units in N (n). Indeed, the Boolean encoding v(a) can be represented as blocks of log 2 (A) dimensional Boolean vectors:v(a) = (v(a) 1:log 2 (A) Unit 1's treatment , . . . , v(a) (i-1) log 2 (A)+1:i log 2 (A) Unit i's treatment , . . . , v(a) (N -1) log 2 (A)+1:N log 2 (A) Unit N 's treatment).Unit n's reward depends on a small collection of these blocks, those indexed by its neighbors. DefineB(n) := i ∈ [N log 2 (A)] : i ∈ [(m -1) log 2 (A) + 1 : m log 2 (A)] for some m ∈ N (n) . B(n) contains the indices of v(a) corresponding to treatments of units m ∈ N (n) and the non-zero entries of θ n are indexed by subsets S ⊂ B(n). E.g., consider N = 3, A = 2, with N (1) = {1, 2}. Then B(1) = {1, 2} and S ⊂ B(n) = {∅, {1}, {2}, {1, 2}}, where ∅ is the empty set.Graphical interpretation. Assumption 2 can be interpreted graphically as follows.Let G = ([N ], E) denote a directed graph over the N units, where E ⊆ [N ] × [N ]denotes the edges of G. For unit n, we add to the edge set E a directed edge (n, m) for each m ∈ N (n), thus justifying calling N (n) the neighborhood of n. That is, unit n's reward is affected by the treatment of another unit m only if there is a directed edge from n to m. See Figure 1 for an example of a network graph G. 
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 (n) for each unit n. The unknown case is analysed in Section 5.Assuming knowledge of G is reasonable in e-commerce, where the platform (learner) assigning discounts (treatments) to goods (units) understands the underlying similarity between goods.Our algorithm requires the following additional notation: for a ∈[A] N , let χ a (B n ) = (χ S (a) : S ⊂ B(n)) ∈ {-1, 1} A s, where χ S (a) are the Fourier characteristics corresponding to subsets of B(n). Further, let U([A] N ) denote the uniform discrete distribution on the action space [A] N .Algorithm 1 Network Explore-Then-Commit with Known Interference1: Input: Time horizon T , exploration steps E, interference graph G = ([N ], E). 2: Sample a 1 , . . . , a E ∼ i.i.d. U [A] N 3: Observe reward vectors R t = (R 1t , • • • , R N t ) for t ∈ [E], where R nt = ⟨θ n , χ(a t )⟩ + ϵ nt . 4: for n ∈ [N ] do 5: Let X n = (χ ai (B n ) : i ∈ [E]) ∈ {-1, 1} E×A s // χ a (B n ) = (χ S (a) : S ⊂ B(n)) 6:Let Y n = (R n1 , . . . , R nE ).Setθ n := arg min θ∈R A s ∥ Y n -X n θ∥ 2 2 8: Define θ n by θ nS = θ nS if S ⊂ B(n) else set θ nS = 0. // Coordinates of θ n indexed by subsets of B(n) 9: Set θ := N -1 N n=1 θ n . 10: Play a := arg max a∈[A] N ⟨ θ, χ(a)⟩ for the T -E remaining rounds.Algorithm 1 is a "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 χ a (B n ) for each unit n. This is because when G is known, the learner knows the positions of the non-zero elements of θ n which are precisely the subsets of B(n), Once the estimates θn are obtained for each unit, they are aggregated to estimate the average reward for each action a ∈ [A] N . In 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 E below to achieve low regret in Theorem 4.1. Practically, the learner can continue to explore and assess the error of the learnt θ n via cross-validation (CV). Once the CV error for all units falls below a (user-specified) threshold, commit to the action with highest average reward. We use this approach for selecting E in our simulations in Section 6.Here, we establish high-probability regret bounds of Algorithm 1 using O(•) notation. We prove the following in Appendix B. Theorem 4.1. Suppose Assumptions 1 and 2 hold. For T = Ω A 2s [log(2N/δ) + s log(A)] and any failure probability δ ∈ (0, 1), Algorithm 1 run with E := (T A s ) 2/3 log N δ + s log (A)1/3 satisfies Reg T = O [s log(A/δ)] 1/3 (T A s ) 2/3, with probability at least 1 -δ.Establishing Theorem 4.1 requires trading-off the exploration time E to accurately estimate θ n with the exploitation time. It also requires T to be large enough such that we can accurately estimate θ n . Next, we compare regret of Algorithm 1 to other methods, ignoring any dependencies on logarithmic factors to ease the discussion.Comparison to other approaches.(a) Naïve MAB learner. A naïve learner who treats the entire network of units as a single multiarmed bandit system with A N actions will obtain regret O(√ T A N ).For sparse networks with s ≪ N and T ≪ A N , our regret bound is significantly tighter.(b) Global estimation. An alternate algorithm would be to estimate Fourier coefficients θ := 1/N N i=1 θ n of r directly rather than estimate each θ n (i.e., r n ) individually. That is, perform the least squares regression by compressing the observed, unit-specific rewards into R t := N -1 N n=1 R tn . An analysis similar to the one presented in Appendix B would yield rate of O(s 1/3 (T N A s ) 2/3 ), which suffers an additional N 2/3 cost as compared to Theorem 4.1. (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 a∈[A] r(a1). We also note that the framework of Jia et al. [2024] is closer to that of adversarial bandits, whereas our framework is closer to that of stochastic bandits.5 Network Multi-Armed Bandits with Unknown InterferenceNext, we consider the case in which the underlying network G governing interference is not known. We present Algorithm 2, which extends Algorithm 1 to account for the fact that the learner does not observe the network graph G and thus does not know N (n) for all n. Unknown network interference is common in medical trials, e.g., vaccine roll-outs where an individual's social network (i.e., G) is unavailable to the learner.Algorithm 2 Network Explore-Then-Commit with Unknown Interference 1: Input: Time horizon T , exploration steps E, regularization parameter λ > 02: Sample a 1 , . . . , a E ∼ i.i.d. U [A] N 3: Observe reward vectors R t = (R 1t , • • • , R N t ) for t ∈ [E], where R nt = ⟨θ n , χ(a t )⟩ + ϵ nt . 4: Let X = (χ(a i ) : i ∈ [E]) ∈ {-1, 1} E×A N 5: for n ∈ [N ] do 6:Let Y n := (R n1 , . . . , R nE ).Setθ n := arg min θ∈R A N 1 2E ∥Xθ -Y n ∥ 2 2 + λ∥θ∥ 1 8: Set θ := N -1 N n=1 θ n . 9: Play a := arg max a∈[A] N ⟨ θ, χ(a)⟩ for the T -E remaining rounds.Algorithm 2 is similar to Algorithm 1, but differs in how it learns θ n . Since G is unknown, the learner cannot identify the Fourier characteristics which correspond to the non-zero elements of θ n . Therefore, we regress against the entire Fourier characteristic χ(a), using Lasso instead of ordinary least squares to adapt to the underlying sparsity of θ n . A similar CV approach, as discussed after Algorithm 1, can be used to determine both the exploration length E, and regularization parameter λ.Low-order interactions. When A N is very large, the computational cost of running the Lasso can be large. Further, if the underlying network is indeed believed to be sparse, one can regress against all characteristics χ S 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 1 on the observed portion of G, and Algorithm 2 on the unobserved graph. Specifically, if N (n) is observed for unit n, replace the Lasso in line 7 of Algorithm 2 with OLS (i.e., line 8) in Algorithm 1. 
regret analysis: 
 We now establish high-probability bounds on the regret for Algorithm 2 in Theorem 5.1. We prove the following in Appendix C. Theorem 5.1. Suppose Assumptions 1 and 2 hold, and assume T = Ω(A 2s [log(N/δ) + N log(A)]). Then, with failure probability δ ∈ (0, 1), Algorithm 2 run with λ = 4E -1 log(2A N ) + 4 E -1 log 2N δ where E := (T A s ) 2/3 log N δ + N log(A) 1/3 satisfies Reg T = O [N log(A/δ)] 1/3 (T A s ) 2/3with probability at least 1 -δ.We note the regret bound requires the horizon T to be sufficiently large in order to learn the network graph G -a necessary detail in order to ensure Lasso convergence. This is because the proof of Theorem 5.1 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 θ n accurately. Specifically, we show that X is incoherent, i.e., approximately orthogonal, with high probability. See Appendix C for 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 2 achieves the same dependence in A, s, T as in the known interference case, but pays a factor of N 1/3 as compared to s 1/3 . This additional cost which is logarithmic in the ambient dimension A N is typical in sparse online learning. This regret rate is still significantly lower than naïve approaches that scale as O( √ A N T ) when one assumes T is much smaller then A N . Further, as argued before, estimating per-unit rewards (i.e., θ n ) results in lower regret as compared to directly estimating r by a factor of N 2/3 . Dependence on horizon T . Generally, the dependence on T cannot be improved. Hao et al. [2020] lower bound regret for sparse linear bandits as Ω((sparsity • T ) 2/3 ), i.e., Ω((A s • T ) 2/3 ) in our setting. They show improved dependence on T can only be achieved under stronger assumptions on the size of non-zero coefficients of θ n . 
simulations: 
 In this section, we perform simulations to empirically validate our algorithms and theoretical findings. We compare Algorithms 1 and 2 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 hyper-parameters via 3-fold CV, and use the scikit-learn implementation of the Lasso. Code for our methods and experiments can be found at https://github.com/aagarwal1996/NetworkMAB. Our experimental setup and results are described below.Data Generating Process. We generate interference patterns with varying number of units N ∈ {5, . . . , 10}, and A = 2. For each N , we use s = 4. We generate rewards r n = ⟨θ n , χ(a)⟩, where the non-zero elements of θ n (i.e., θ n,S for S ⊂ B n ) are drawn uniform from [0, 1]. We normalize rewards so that they are contained in [0, 1], and add 1 sub-gaussian noise to sampled rewards. We measure regret as we vary T , and set a max horizon of T max = 10 • 2 N for each N . Classical MAB algorithms need the horizon T to satisfy T > 2 N since they first explore by pulling all 2 N arms. We emphasize that these time horizons scaling as T = C • A N are often unreasonable in practice, as even for A = 2 and N = 100 there would already be ≈ 1.27e 30 actions to explore. We include such large time horizons for the sake of making a 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 2 below. Our results are averaged over 5 repetitions, with shaded regions representing 1 standard deviation measured across repetitions. Algorithms 1 and 2 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 max for N = 9 in Figure 2 (a) . Classical MAB algorithms such as UCB see an exponential growth in the regret as N increases. Both Algorithm 1 and Algorithm 2 have much milder scaling with N . Algorithm 1 uses G 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 = 9 in Figure 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 1 is able to end its exploration phase earlier than algorithm 2 since it does not need additional samples to learn the sparsity unlike the Lasso.  
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 our 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, as well as comparing to a 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 to understand optimal algorithms will also be valuable future work. Further extensions could also include considering interference in contextual bandits or reinforcement learning problems. We also hope this work serves as a bridge between online learning and discrete Fourier analysis. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have read the code of ethics and have found no violations in our work.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 not available online, the authors are encouraged to reach out to the asset's creators. 
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 of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 do not use crowdsourcing nor do we conduct research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and 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. 
 
 Appendix: By the discussion in Section 3, recall that for any action a ∈ [A] N and unit n, the reward can be expressed as r n = ⟨θ n , χ(a)⟩. To establish the proof, it suffices to show that for any S ⊂ [N log 2 (A)] satisfying S \ B(n) ̸ = ∅, ⟨χ S , r n ⟩ B = 0. Let i ∈ S \ B(n) be an arbitrary index, then, we have,⟨χ S , r n ⟩ B = A -N x∈{-1,1} N log 2 (A) r n (x)χ S (x) = A -N        x∈{-1,1} N log 2 (A) xi=1 r n (x)χ S (x) + x∈{-1,1} N log 2 (A)xi=-1r n (x)χ S (x)        = A -N        x∈{-1,1} N log 2 (A) xi=1 x i r n (x)χ S\{i} (x) + x∈{-1,1} N log 2 (A) xi=-1 x i r n (x)χ S\{i} (x)        = A -N        x∈{-1,1} N log 2 (A) xi=1 r n (x)χ S\{i} (x) - x∈{-1,1} N log 2 (A) xi=-1 r n (x)χ S\{i} (x)        = 0,where the final equality follows from the fact that, by Assumption 2, r n (x) = r n (x ′ ) when x and x ′ differ only in positions indexed by i / ∈ B(n). Thus, the only subsets S ⊂ [N log 2 (A)] where we can have ⟨r n , χ S ⟩ B ̸ = 0 are those satisfying S ⊂ B(n), which proves the desired result.In this section, we prove Theorem 4.1. We establish helper lemmas before proving Theorem 4.1.Recall the following notation before establishing our results. We defined B(n) := {i ∈ [N log 2 (A)] : i ∈ [(m -1) log 2 (A) + 1 : m log 2 (A)] for m ∈ N (n)} as the set of indices of the treatment vector v(a) ∈ {-1, 1} N log 2 (A) belonging to neighbors m ∈ N (n). Additionally, X n = (χ ai (B n ) : i ∈ [E]) ∈ {-1, 1} E×A s, where χ a (B n ) = (χ S (a) : S ⊂ B(n)) ∈ {-1, 1} A s . For a matrix A ∈ R N ×d , let σ min (A) denote its minimum singular value. To proceed, we quote the following theorem. Lemma B.1 (Theorem 5.41 in Vershynin [2018] ). Let A ∈ R N ×d such that its rowsA i are independent isotropic random vectors in R d . If ∥A i ∥ 2 ≤ √ m almost surely for all i ∈ [N ],then, with probability at least 1 -δ, one hasσ min (A) ≥ √ N -cm log(2d/δ)for universal constant c > 0.). There exists a positive constantC 4 > 0 such that if E ≥ C 4 A s log(2A s /δ), then, σ min X T n X n E ≥ 1 2 ,with probability at least 1 -δ.Proof. We begin by showing the conditions for Lemma B.1 are satisfied. First, we proveX n is isotropic, i.e., E[χ a (B n ) (χ a (B n )) T ] = I A s, where the expectation is taken over uniformly sampling actions a uniformly and random from [A] N . This follows since for any two subsetsS, S ′ ⊂ [N log 2 (A)], E[χ S (a)χ S ′ (a)] = 1 A N a∈A N χ S (a)χ S ′ (a) = ⟨χ S , χ S ′ ⟩ B = 1[S = S ′ ] Since, χ a (B n ) ∈ {-1, 1} A s for all actions a ∈ [A] N , ∥χ a (B n )∥ 2 ≤ √ A s . Hence, by Lemma B.1, σ min (X n ) ≥ √ E -c log(2A s /δ)A s . Next, using the fact that σ min (X T n X n ) = σ 2 min (X n ), we get that σ min X T n X n E ≥ E -2 cEA s log(2A s /δ) E .Finally, plugging in A s log(2A s /δ) ≤ E/C for an appropriate C gives us the claimed result.We quote the following theorem regarding the ∥ • ∥ 2 error of θ n . Lemma B.3. [Theorem 2.2 in Rigollet and Hütter [2023] ] Assume that Y = Xθ * + ϵ, where ϵ is 1 sub-Gaussian, where X ∈ R E×d . If d ≤ E, and covariance matrix Σ X = (X T X)/E has rank d, then we have with probability at least 1 -δ,∥Xθ * -X θ∥ 2 ≤ C 1 d + log(1/δ) E ,where θ = arg min θ∈R d ∥Y-Xθ∥ 2 2 is the least squares estimator, and C 1 > 0 is a positive universal constant.While the above lemma bounds the mean-squared error the least-squares estimate, in our applications we can about bounding the ℓ 2 distance between θ * and θ. Simple rearrangement on the above implies that, with probability at least 1 -δ, we actually have∥θ * -θ∥ 2 ≤ C 1 d + log(1/δ) E • σ min (Σ X ) .If, in particular, σ minX ⊤ X E≥ 1/2, the above can be simplified to∥θ * -θ∥ 2 ≤ C 2 d + log(1/δ)E with probability at least 1 -δ for some new, appropriate universal constant C 2 > 0.Proof. Recall the notation θ = N -1 N n=1 θ n , and a = arg max a∈[A] N ⟨ θ, χ(a)⟩. The average reward r( a) can be bounded using the definition of a and Holder's inequality as follows,r(a * ) -r( a) = ⟨θ, χ(a * ) -χ( a)⟩ = ⟨θ -θ, χ(a * ) -χ( a)⟩ + ⟨ θ, χ(a * ) -χ( a)⟩ ≤0 ≤ ⟨θ -θ, χ(a * ) -χ( a)⟩ = 1 N N i=1 ⟨θ n -θ n , χ(a * ) -χ( a)⟩ = 1 N N i=1 ⟨θ n -θ n , χ a * (B n ) -χ a (B n )⟩ ≤ 1 N N i=1 ∥θ n -θ n ∥ 2 ∥χ a * (B n ) -χ â(B n )∥ 2 Using ∥χ a (B n )∥ 2 ≤ √ A s then gives us r(a * ) -r( a) ≤ √ A s N N i=1 ∥θ n -θ n ∥ 2 (2)Next, define "good" events for any unit n ∈ [N ] asG n1 := σ min X T n X n E ≥ 1 2 and G n2 := ∥ θ n -θ n ∥ 2 ≤ C 2 E -1 A s + log 4N A s δ ,where C 2 > 0 is as stated above. Notice that there exists a sufficiently large uni-versal constant C 3 > 0, such that T ≥ C 3 A 2s [log(2N/δ) + s log(A)] implies E = (T A s ) 2/3 log N δ + s log (A) 1/3 ≥ C 4 A s log(4N A s /δ). Hence, for any given n ∈ [N ], we have via Lemma B.2 that G n1 holds with probability 1 -δ 2N Conditioned on G n1 , we get that P(G n2 |G 1 ) ≥ 1 -δ 2N .Summarizing, we get that for any n ∈ [N ], the following holds∥ θ n -θ n ∥ 2 ≤ C 2 E -1 A s + log 4N A s δ ≤ C 5 E -1 A s log 4N A s δ , with probability at least 1 -δ 2N 2 ≥ 1 -δ/N, where C 5 > 0 is an appropriate constant. Taking a union bound over all N units, and then substituting into (2) gives usr(a * ) -r( a) ≤ C 5 A s E -1 log 4N A s δFinally, using this, the cumulative regret can be upper bounded with probability 1 -δ as follows:Reg T = T t=1 (r(a * ) -r(â)) = E t=1 (r(a * ) -r(â)) + T t=E+1 (r(a * ) -r(â)) ≤ E + C 5 T A s E -1 log 4N A s δSubstituting E as in the theorem statement completes the proof.In this appendix, we prove Theorem 5.1. Our proof requires the following lemmas.C.1 Helper Lemmas for Theorem 5.1The 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 χ(a t ) as the Fourier characteristic associated with actiona t ∈ [A] N . Let X = (χ(a t ) : t ∈ [E]) ∈ {-1, 1} E×A N Additionally, we require the following definition of incoherence. Definition C.1. We say a matrix A ∈ R E×d is s-incoherent if ∥A ⊤ A -I d ∥ ∞ ≤ 1 32s, where I d is the identity matrix of dimension d.). For E ≥ 1, suppose a 1 , . . . , a E iid ∼ U({-1, +1} N log 2 (A) ). Then, P     X ⊤ X E -I A N ∞ ≤ 2 log 2A 2N δ E     ≥ 1 -δ,where ∥A∥ ∞ = max i,j |A i,j | denotes the maximum coordinates of a matrix. Thus, if E ≥ 4096A 2s log 2 δ + 2N log (A) , X is A s -incoherent with probability at least 1 -δ.Proof. Recall that, for any a ∈ [A] N , χ(a) := (χ S1 (a), . . . , χ S A N (a)), where S 1 , . . . , S A N is some fixed enumeration of subsets S ⊂ [N log 2 (A)]. Thus, each entry of (X ⊤ X)/E can be viewed as being indexed by subsets S, S ′ ⊂ [N log 2 (A)].To establish (C.2), we first examine diagonal elements of (X ⊤ X)/E. For S ⊂ [N log 2 (A)], we haveEQUATIONwhere the last equality follows from the fact that (χ S (a t )) 2 = 1.Next, we consider off-diagonal elements, and bound their magnitude. Before doing so, we require the following. For subsets S, S ′ ⊂ [N log 2 (A)], let S∆S ′ denote the symmetric difference of two subsets. For any two subsets S, S ′ ⊂ [N log 2 (A)], the product of their Fourier characteristics is,χ S (a t )χ S ′ (a t ) = i∈S v(a t ) i i ′ ∈S ′ v(a t ) i ′ = i∈S∆S ′ v(a t ) i .Using this, for any distinct subsets S, S ′ , we haveX ⊤ X E S,S ′ = 1 E E t=1 χ S (a t )χ S ′ (a t ) = 1 E E t=1 i∈S∆S ′ v(a t ) i .Since S ̸ = S ′ , and a t ∼ U({-1, 1} N log 2 (A) ), the set of random variables {v(a t ) i : i ∈ S∆S ′ } are independent Rademacher random variables. Applying Hoeffding's inequality for ϵ > 0 gives usP X ⊤ X E S,S ′ ≥ ϵ ≤ 2 exp - Eϵ 2 2 .Applying the inequality above and taking a union bound over all A 2N elements of (X ⊤ X)/EEQUATIONTo complete the proof, observe that (3) implies thatX ⊤ X E -I A N ∞ = max S,S ′ ⊂[N log 2 (A)] S̸ =S ′ X ⊤ X E S,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 a version that can be found in the book on high-dimensional probability due to Rigollet and Hütter [2023] .Lemma C.3 (Theorem 2.18 in [Rigollet and Hütter, 2023] ). Suppose that Y = Xθ * + ϵ, where X ∈ R E×d , θ * ∈ R d is s-sparse, and ϵ has independent 1-sub-Gaussian coordinates. Further, supposeX ⊤ X T is s-incoherent.Then, for any δ ∈ (0, 1) and for λ = 4 E -1 log(2d) + 4 E -1 log(δ -1 ), we have, with probability at least 1 -δ∥θ * -θ∥ 2 ≤ C sE -1 log 2d δwhere θ 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 [2023] or the statement of Theorem 7.3 in Wainwright [2019] ), it can be further deduced that ∥θ * -θ∥ 1 ≤ 4 √ s∥θ * -θ∥ 2 , so we actually have that, for any δ ∈ (0, 1), with probability at least 1 -δ,∥θ * -θ∥ 1 ≤ Cs E -1 log 2d δ ,where C > 0 is again some absolute constant.C.2 Proof of Theorem 5.1Proof. Define θ = N -1 N n=1 θ n . Recall the notation θ = N -1 N n=1 θ n , and a = arg max a∈[A] N ⟨ θ, χ(a)⟩. For any round t ∈ {E + 1, . . . , T }, we greedily play the action a. The average reward r( a) can be bounded using the definition of a and Holder's inequality as follows,r(a * ) -r( a) = ⟨θ, χ(a * ) -χ( a)⟩ = ⟨θ -θ, χ(a * ) -χ( a)⟩ + ⟨ θ, χ(a * ) -χ( a)⟩ ≤0 ≤ ⟨θ -θ, χ(a * ) -χ( a)⟩ ≤ ∥θ -θ∥ 1 ∥χ(a * ) -χ( a)∥ ∞ .Next, substituting the definition of θ, θ, ∥χ(a)∥ ∞ = 1, and using the triangle inequality into the equation above gives us,EQUATIONLet us define the "good" events byG 1 := {X is A s -incoherent} and G 2 := ∀n ∈ [N ], ∥ θ n -θ n ∥ 1 ≤ CA s E -1 log 4N A N δwhere C > 0 is the constant following the discussion of Lemma C.3. Let us define the global "good" event by G := G 1 ∩ G 2 . We show P(G) ≥ 1 -δ.First, there is a universal constantC ′ > 0 such that E ≥ 4096A 2s [log(4/δ) + 2N log(A)] when T ≥ C ′ A 2s [log(N/δ)+N log(A)]. Thus, by Lemma C.2, we know the matrix X with χ a1 , . . . , χ a E as its rows is A s -incoherent least 1 -δ 2 , i.e. P(G 1 ) ≥ 1 -δ 2 . Next, conditioning on G 1 and applying Lemma C.3 alongside a union bound over the N units yields∥ θ n -θ n ∥ 1 ≤ CA s E -1 log 4N A N δ ,for all n ∈ [N ] with probability at least 1 -δ 2 , i.e. P(G 2 | G 1 ) ≥ 1 -δ 2 . Thus, in total, we have P(G) = P(G 1 )P(G 2 | G 1 ) ≥ (1 -δ/2) 2 ≥ 1 -δ. We assume we are operating on the good event G going forward.Plugging the per-unit ℓ 1 norms into (5), the cumulative regret can be upper bounded with probability 1 -δ as follows:Reg T = T t=1 (r(a * ) -r(â)) = E t=1 (r(a * ) -r(â)) + T t=E+1 (r(a * ) -r(â)) ≤ E + 2T N N n=1 θ n -θ n 1 ≤ E + 2CT • A s E -1 log 4N A N δ (6)Clearly, we should select E to roughly balance terms (up to multiplicative constants). In particular, using the choice of E asE := (T A s ) 2/3 log N δ + N log(A) 1/3and substituting E into (6) gives usReg T ≤ O (N log(AN/δ)) 1/3 (T A s ) 2/3with probability at least 1 -δ, precisely the claimed result.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: in 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 in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.For any positive integer x, we let [x] := {1, . . . x}.Specifically, it violates the stable unit treatment value assumption (SUTVA)[Rubin, 1978].For a vector x ∈ R d , we define ∥x∥0 := d i=1 1(xi ̸ = 0) 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

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.
questions: 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. 
2. If only a portion of neighbors is revealed for unit $i$, do you use Algorithm 1 or Algorithm 2?
limitations: limitations: Authors have adequately addressed limitations.
paper_summary: paper_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:

- 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.    

- 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$.    

- 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.

- Numerical simulations validate the effectiveness of the proposed algorithms and show they outperform the UCB baseline.
strength_weakness: strength_weakness: - I feel it's not common to see $\mathcal{A}$ to denote a number rather than the action set.
- The Boolean encoding of the actions is not well-discussed.
- 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?
- There are some typos of notations, for example, on page 4, (2) Simple orthonormal basis, the authors used $\mathcal{F}_{bool}$.
questions: 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: limitations: The limitations are well addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
questions: questions: N.A.
limitations: limitations: N.A.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: * it seems you did not use the correct format for the submission (as their are no line numbers), make sure you correct this
* in the definition of "Linear Fourier expansion", should be $S \subset$ instead of $S \in$, right?
* In your algorithms, can you clarify the running time of finding the minimizing coefficient vector?
* In Theorem 4.1, should be $\mathcal{A}$ instead of $A$?
limitations: limitations: The authors properly address the limitations of their work.
paper_summary: paper_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
units (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. 

The 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.
strength_weakness: strength_weakness: 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.
questions: 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?

ETC 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?

In Step 10 of Algorithm 1, how can the optimization problem be solved in practice given the large space?
limitations: limitations: See **Questions**.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.
questions: 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.

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?
limitations: 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.

If 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.

[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.

Comments: comment: I think I will keep my score at this point. If you believe one of the two points can be addressed, I'd be happy to raise the score. 1. The network structure and its impact on the regret. It doesn't have to be comprehenssive, but I believe it will strengthen the network side of the study. 2. For the computation of the optimal solution, although I understand that it just requires enumerating the action space $|A|^s$, I do have concerns about the exponential size of the action space itself. For a reasonablely sized problem, this would be quite impractical I think? What size of the problem can the solved by this method?
Thanks for the response. I will keep my positive score.
I appreciate the response and the clarifications. I will keep my positive score.
Thanks for the response. We believe we have addressed the primary concerns mentioned in the review. Is there anything else we can clarify to improve the score?
Thanks for the detailed response. I don't have further comments and remain positive of the paper.
Thank you for the response, I will keep my score positive.
Thank you for the detailed response.