Linear Contextual Bandits With Interference
Authors: Yang Xu
Wenbin Lu
Rui Song
Venue: ICML 2025 poster (2025)
Keywords: Contextual Bandits
Interference
Causality
Multi-agent
Asymptotics
Sublinear regret
Primary area: general_machine_learning->causality
TL;DR: This paper constructs a systematic framework for tackling interference in contextual bandit problems with multiple units per round, offering comprehensive theoretical guarantees and connecting online learning with causality.

Abstract: Interference, a key concept in causal inference, extends the reward modeling process by accounting for the impact of one unit's actions on the rewards of others. In contextual bandit (CB) settings where multiple units are present in the same round, interference can significantly affect the estimation of expected rewards for different arms, thereby influencing the decision-making process. Although some prior work has explored multi-agent and adversarial bandits in interference-aware settings, how to model interference in CB remains significantly underexplored. In this paper, we introduce a systematic framework to address interference in Linear CB (LinCB), bridging the gap between causal inference and online decision-making. We propose a series of algorithms that explicitly quantify the interference effect in the reward modeling process and provide comprehensive theoretical guarantees, including sublinear regret bounds, finite sample upper bounds, and asymptotic properties. The effectiveness of our approach is demonstrated through simulations and a synthetic data generated based on MovieLens data.

Linear Contextual Bandits With Interference
Yang Xu 1 Wenbin Lu
Rui Song"
Abstract
is common in causal inference literature. However, many real-world situations, this assumption frequently violated due to interference, where an individual's ' outcome is influ- enced by the actions of others (Rosenbaum, 2007).
Interference, key concept in causal inference, extends the reward modeling process by account- ing for the impact of one unit's actions the re- wards of others. In contextual bandit (CB) settings where multiple units are present in the same round, interference can significantly affect the estimation of expected rewards for different arms, thereby in- fluencing the decision-nn mariiiin--mainggggg process. Although some prior work has explored multi-agent and adversarial bandits in interference-awant settings, how to model interference in CB remains signifi- cantly underexplored. In this paper, we introduce a systematic framework to address interference in Linear CB (LinCB), bridging the gap between causal inference and online maaiing. We propose series of algorithms that explicitly quan- tify the interference effect in the reward modeling process and provide comprehensive theoretical guarantees, including sublinear regret bounds, fi- nite sample upper bounds, and asymptotic proper- ties. The effectiivnness of our approach is demon- strated through simulations and synthetic data gen- erated based on MovieLens data.
During the COVID-19 pandemic, local governments have sought optimal personalized quarantine policies over ex- tended periods. Here, each local government acts as an agent capable of making decisions over time. The observed reward, such as the number of infected individuals, reflects the community's health status following the application of specific policy. Over time, governments adjust their policies based on the latest health status to mitigate virus spread. In this case, one community's 's health outcomes can be influ- enced by the quarantine policies of neighboring communi- ties due to population movement and the nature of virus spread, illustrating the presence of interference.
Another example is in advertising markets, where adver- tisers manage multiple ad lines targeting overlapping au- diences through different channels. The overlap in target consumers and the similarity between ad lines can cause the Return on Investment (ROI) of one ad to be influenced by the impression status of another. For instance, if one ad targets students interested in Nike shoes and another in Adidas shoes, the ROI of the Nike ad might be affected by whether customers have already seen the Adidas ad due to the shared audience and similar products.
1. Introduction
In classical causal inference literature, the issue of inter- ference has been extensively explored in both experimen- tal design (Aronow & Samii, 2017: Viviano, 2020; Leung, 2022a;b; Viviano, 2024) and observational studies (Su et al., 2019; Bargagli-Stoffi et al., 2020; Forastiere et al., 2021; Qu et al., 2021). However, interference within online sequen- tial decision-making frameworks, such as bandits, remains relatively underexplored.
Decision making widely exists in various real-world set- tings, such as advertising (Zhou et al., 2023), clinical trials (Tsiatis et al., 2008), and transportation (Wang et al., 2024). The core of decision-making problems lies in selecting the optimal action from set of possible options to maximize an outcome or reward that is valuable to the decision-maker.
To simplify decision-making involving multiple individuals (or agents/units), it is often assumed that an individual's 's outcome depends only on the action applied to them and is unaffected by actions taken on others. This assumption, part of the Stable unit Treatment Value Assumption (SUTVA),
When multiple agents, each capable of sequential decision- making, are involved, the problem is often known as the multi-agent multi-armed bandits (MAMAB). However, ex- isting work in MAMAB faces limitations in incorporating agent-specific information that can enhance personalized decision-making. For example, in the COVID-19 spread sce- nario, communities (treated as agents) are not static; there may be population flows, new communities joining, and existing communities dissolving, each with unique charac-
Departmenn of Statistics, North Carolina State University, USA. Correspondence to: Rui Song <songray moongray@gmil..om com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Lincar Contextual Bandits With Interference (LinCBWT)
teristics. Similarly, in the advertising market, ad lines (also treated as agents) evolve quickly across campaigns, each with distinct characteristics such as size, content, and target audiences. Therefore. it is essential to consider a bandit framework under interference that accounts for agents or individuals evolving over time. This problem, often incor- porating agent-specific information, is typically addressed within the framework of contextual bandits (CB).
function in an online setting with interference. We introduce probability of exploration and small clipping rate to en- sure both estimation consistency and asymptotic properties. This clipping rate also balances the trade-off between statis- tical efficiency and regret minimization. The performance of our estimator is validated through simulation studies and synthetic data based on MovieLens.
The structure of this paper is as follows. Section 2 reviews recent work on interference and its integration into bandit frameworks. Section 3 introduces our framework for reward modeling and action selection, covering both offline opti- mization and online learning. In Section 4, we establish the theoretical foundations of the proposed estimators and the optimal value function, along with a regret analysis. Sec- tions 5 and demonstrate the effectiveness of our proposed algorithm through a simulation study and a synthetic dataset based on Movielenns Finally, we provide a brief summary and discuss potential extensions in Section 7.
Addressing interference in the CB framework presents two primary challenges. First, the struciure-wise challenge: since the actions of multiple units influence each other's reward modeling, the resulting action space becomes high- dimensional without a precise understanding of the interfer- ence structure (Agarwal et al., 2024). Estimating heteroge- neous treatment effects under interference in single-stage settings is already a complex task (Viviano, 2020; Leung, 2022b), and extending this to sequential decision-making scenarios like bandits (where the balance between explo- ration and exploitation is crucial) further compounds the challenge. Second, the theory-wise challenge: classical sta- tistical inference tools, such as the Central Limit Theorem (CLT), become inapplicable as each action and correspond- ing reward may depend on all previously collected data. This presents dual challenge: dependencies arise both across rounds due to online updates and within rounds due to interference between units. These dependencies violate the standard assumption of sample independence, compli- cating the application of traditional inference techniques.
2. Related Work
Interference in Single Stage. In single-stage setting, ex- isting literature varies significantly in defining interference, often assuming different structures for simplifying reward modeling. There are some work focuses on using partial interference and exposure mapping to quantify interference (Sobel, 2006; Qu et al., 2021; Hudgens & Halloran, 2008; Forastiere et al., 2021; Aronow & Samii, 2017; Bargagli- Stoffi et al., 2020). While this approach typically requires fewer assumptions during the reward modeling stage, it often relies on additional requirements, such knowing the form of the exposure mapping function (Manski, 2013; Aronow & Samii, 2017; Bargagli-Stoffi et al., 2020) or as- suming i.i.d. clusters (Qu et al., 2021). These assumptions can be overly restrictive in later stages and may not clearly explain direct and spillover effects.
While some recent works have addressed the issue of inter- ference in MAMAB (Verstraeten al., 2020; Bargiacchi et al., 2018; Dubey et al., 2020; Agarwal et al., 2024) and adversarial bandits (Jia et al., 2024), to the best of our knowl- edge, no existing work addresses interference within the con- textual bandits framework. To bridge this gap, we introduce a comprehensive framework for linear contextual bandits in interference-awarn aware scenarios, providing theoretical guaran- tees via both statistical inference and regret analysis. Our contributions are as follows.
On the contrary, another body of work, such as Su al. (2019), considers the reward linear function of neigh- bors' covariates and treatments, which makes more inter- pretable assumptions in interference modeling and allows for comprehensive study in theory. This formulation is similar to Cliff& & Ord (1981) and Getis (2009), where an autoregressive model is used to capture spatial interference with similar parametric modeling assumptions. In our work, consider linear CB as the first step to handle interference while maintaining interpretability. and study both theories and algorithms under this framework.
First, we are the very first work to address the interference issue in contextual bandits with multiple units involved in each round, bridging the gap between SUTVA violations in causal inference and online decision making-
Second, we propose a systematic framework that extends the classical LinCB to interference- scenarios, offer- ing comprehensive theoretical guarantees, including finite- sample upper bounds and sublinear regret. Remarkably, the regret bound achieves the minimax optimal rate in terms of the number of observed samples in the classical contextual bandits literature, even in the presence of interference.
Cooperative Multi-Agent Bandits. Multi-agent bandits typically assume a fixed set of N agents making decisions over time. Some existing works, such as Martinez-Rube et al. (2019) and Landgren al. (2016), focus on informa- tion sharing between agents in distributed system. While
Third, we are also the first work to establish the asymptotic properties of regression coefficients and the optimal value
2

---

Lincar Contextual Bandits With Interference (LinCBWD)
sharing historical data can enhance the reward learning process among agents, these studies still assume that each agent's is reward depends solely on its own actions, excluding the possibility of interference.
which communities were connected by their geographical locations), we first consider the case where W, is known'. We assume the reward of unit at round follows
No Rei Σ Wass f(X Au) + This
(1)
Another line of research, including Verstraeten et al. (2020), Bargiacchi et al. (2018), Dubey et al. (2020), Agarwal et al. (2024), and Jia et al. (2024), considers more general re- ward models where the actions of other agents can affect an individual agent's reward. Specifically, Bargiacchi al. (2018) and Verstraeten et al. (2020) extended the Upper Confidence Bound (UCB) algorithm and Thompson Sam- pling (TS) from the classical MAB setting to multi-agent scenarios. Dubey et al. (2020) introduced a kernelized UCB algorithm, where interference mediated through network contexts. Although Jía al. (2024) also considered inter- adversarial bandits
where the reward Rui is a linear combination of some payoff' function f. and Ma ~ N/, o²) is noise term satisfying Thi T (Xa, e W.) A,), Throughout this paper, we assume that [B I U. i..., the expected reward of each unit i at round t can be uniformly bounded by a large constant U.
Assuming the reward generation process follows Equation (1) is both intuitive and possesses a very beneficial property. With some simple algebra, we can show that
ference in bandits, their focus with homogeneous actions, which is not as flexible our approach where heterogeneous actions are allowed for units within the same round.
N₂ E R
N.
N. West ((X,;;
(2)
N. ΣΣ
N
N,
W Wo ti Au) = Σ
Jui((xx Aci,,
However, all of the aforementioned literature only considers an MAB setting with a fixed and finite number of agents, which is different from our setting where agents or units can vary over time with evolving contextual information.
where we define Wii Σ weight of unit at round 1. The last term further indicates that the optimal action depends solely on the covariates of each individual unit, with interference influencing the direction of optimality through the sign of the weight was- In the specific case where W. E {0, 1e..)..... M.N., wi can be interpreted the "number of friends" or connections for unit i at round t. This measure is straightforward to obtain; for example, in a COVID-19 context, it could represent the number of geographically adjacent communities. Since the optimal action that maximizes Ni,, 1 E[Red] is determined by Xx: is and Wti, we do not need to account for the covariate information and actions of all units achieve the globally optimal action. This simplifies the decision-making process and makes it more practical for real-world applications.
No We,ji as the interference
3. Problem Formulation
In each round t E {I, we assume there are N₂ units with contextual information X., E Rd in a network making sequential decisions simultaneously. At each time step f, unit i E (1,...; :....... N. chooses an action Asi E A and collects a reward Re.. Define N.- = Ex= No as the total number of units up to round t. Due to interference, the poten- tial outcome of unit i at round t is defined as Ra,(ar), where a,- = (411,.... axN,) ) is the action assignment vector for all units at round I.
To quantify the interference level between any two units in the same round, we suppose there exists (normalized) adjacency matrix W, {W..s)is.JJMM E R.N..N. at round 1, such that W.,; denotes the causal interference strength from unit i to unit j. Note that in our setup, Wr is not required to be symmetric, i.e., the causal interference strength from unit to unit j can differ from that of j to i. By default, we assume W t.iy E [-1, and W Wt,ü any and 1 < ر No.
3.1. Offline Optimization
Let's consider linear payoff function for f to establish the entire framework and theory behind. Suppose there exists a coefficient vector B. E Id for each action a E A to quantify the effect of each covariate in X Similar to classical linear CB, we assume
f,u = 1 for
f(X eg. an))= = Σ CTS.. 1aas = a}.
(3)
Defining an interference matrix W, ; is both intuitive and flexible enough to model various real-world scenarios. For instance, in the special case where W, is symmetric and takes values from {0, 13. it can represent a neighborhood structure or friend network, where v,ij = indicates that units i and are connected, and W 1.if 0 means they are not. Since this information is derived from societal inter- actions (for example, during Covid-19 19, it was often known
aEAA
By incorporating Equation (2), the optimal action maxi- mizing cumulative reward for each round-unit pair (1,
Extensions to unknown W, will be discussed in Section 'Here we assume the noise term na is conditionally indepen- dent of the contextual information and the interference matrix W., given the action taken at round t. This is more relaxed assumption compared to i.i.d. random noise.
3

---

Linear Contextual Bandits With Interference (LinCBWD)
(without considering exploration) is given by
Algorithm Linear Contextual Bandits with Interference Input: Number of units N₁; Burning period To: Interfer- ence structure { ( Whhsser; Clipping rate pt > O(N, 12).
Agi arg max Wh; X 1, aEA
(4)
where the sign of W. determines the interference weight causes a flip in action that maximizes the cumulative reward.
1: for Time ( 1, ,,... TT do
2: aci
S N₁;
To simplify notation, we introduce the following vector representations. Denote / = .B......,k BKkT E TReK A, = as the vector of rewards collected at round t, X, = (X.I,..,, X E ReVedd as the covariate infor- mation matrix for all units at round t, and We ti diag( (Wa, ) N,) as an N, N, diagonal matrix. Fur- thermore, define IA,= diag(1{A, diagonal matrix where the ith diagonal element is the in- dicator of 1 Ac = a). We then define a dK- -imennnniio transformed covariate vector for each (4, i) as:
3: end for
A X 1: X 1:To b x X RI.T.
E RN:, R2 = (Rei...., R.N.)
5: for Time t = To I,.... ,T do
6: Observe N, units with features (X AuhisIs..
Update 3,_ A-b 8: for unit i i 1,2, .2. do
Estimate the optimal arm
a}) as N₂ x N,
मeं = arg max Wei aEA
10:
if Amin N:-1 2as=1 2i=1
X xi .i)
<
Pt-1
x, 7, W a A 1, W L
Amin { N. x=
Zi=1
NN
X x T si
then
(5)
11:
Choose As ~ DU(L, K), 1 i N₁;
With some straightforward algebra, the expected reward can be expressed linearly as [[[es] = ,.
12:
else
13:
Choose arm an by Equation (7), (9), or (10); end if
14:
Denote X, (X...... X xv.)) E I RNxx as the trans- formed covariate information matrix round f. Further-
15:
Receive reward Ras;
16:
end for
more, define X 1:1 = (X, (X.....,.) x.) E R. xdk and
17: Update X by Equation (5), Vi E (L,...,, Nr
R1:- (R. ..... R, E R. Without exploration, the
18: Update A + A X, X b + X R.
offline ordinary least square (OLS) estimator is given by
19:
end for
(x 11) X 1.t By: E ERK,
(6)
der An =a {l...., K} can be derived as
In an offline optimization setting, one can replace the true value of B in Equation (4) with B, to obtain an estimate of the optimal individualized treatment rule.
UCBrga + wii X X, + alwad / x (T
X
(8)
where is hyperparameter that controls the exploration- exploitation tradeoff, and (E denotes the d x d block- diagonal submatrix of (Σt-1) corresponding to the vari- ance of B 3 Thus, LinUCBWI selects the arm as by
3.2. Online Algorithms
In the context of online bandits with interference, we ex- tend three algorithms from classical contextual bandits to account for the presence of interference: Linear Epsilon- Greedy With Interference (LinEGWI), Linear Upper Confi- dence Bound With Interference (LinUCBWI), and Linear Thompson Sampling With Interference (WT). These algorithms, summarized in Algorithm 1, differ primarily in Line 13 based on their respective exploration strategies.
at = arg max UCB
(9)
LSnT:WI: Define as a arper-parameter denoting the level of exploration. For unit at round LinTSWI will sample
Br "N ppoct 2 Ei.pas) and then choose arm ag s.t.
LinEGWI: For EG-based exploration, we select action ag = (1 - Dns) arg max Wi; X 3 ii.a + Zu DU(1,
At arg max X Bria
XT
(10)
For space limit, we save the expression for posteriors, as well as other derivation details, to Appendix C.
(7)
where Zi Ber(cH), and DU K) denotes the discrete uniform distribution s.t. P(A a) = & for any E [K].
There are two main differences between Algorithm 1 and classical LinCB algorithms. First, due to the presence of interference, f3 is estimated using the transformed covariate
LinUCBWI: Define E. = x lst x1:t) The UCB un-
4

---

Lincar Contextual Bandits With Interference (LinCBWT)
information X ti. This transformation depends on not only the covariates, but also the interference matrix and actions involving all units in round t. Second, we incorporate additional clipping step in Line 10 to ensure that the proba- bility of exploration does not decay faster than O 1/2) (see Assumption A.2 in Appendix A). This clipping step is crucial for maintaining sufficient exploration, which is necessary for estimation consistency and valid inference of 3, as will be detailed in the theory section. Note that when W = I for all f, our method downgrades to the classical linear CB algorithms, aside from adding a step for clipping to ensure valid statistical inference.
Therefore, in Algorithm set the clipping rate at round to Pt > O(N, 1/2/ to ensure sufficient exploration and thus the convergence of the online OLS estimator.
4.2. The probability of exploration
Define Kiss xx) = P(ass * #t-1(X()), where the probability operator IP is taken with respect to de and all historical data collected before round t. The term Keg xa) represents the probability of exploration for unit i at round we define the limit of (ex X() as Koo (we, 2) = x P(an: + T (æ)). Since Kai is non- negative by definition, it follows immediately from the Sand- wich Theorem that ri exists for both UCB and TS. For EG, Ric (wo X) = lim,,_-c Kes X) lim 4ts/ K. In the following theorem, we establish the exploration upper bounds for LinUCBWI, LinTSWI, and LinEGWI, which are crucial for understanding the consistency conditions of the online OLS estimator and the necessity of clipping.
Remark. The computational complexity of LinCBWI is approximately O(d"K2N N.) Specificaly for each unit in round t, the primary computational costs arise from matrix inversion (Line 7 of Algorithm 1) and the smallest eigen- value computation (Line 10 of Algorithm 1), both requiring Odd in standard implementations. Using optimization techniques such as iterative eigenvalue decomposition and the Sherman-Morrison update can reduce this to (d² K2). Multiplying by the total number of units Nr gives the over- all complexity of Algorithm 1. In classical LinCB, the com- plexity is (d K N.). WI introduces an additional factor of K due to interference considerations, requiring a joint update of Ba for all a E A. A detailed comparison of computational time provided in Section 5.3, where we show that although LinCBWI incurs slightly higher runtime, it remains computationally efficient in practice.
Theorem 4.2. Suppose Assumptions A. I-A.3 hold. In either LinUCBWI, LinTSWI or LinEGWI, for any 0 < & < 1Sall/2 with G.. = X Bo), we have
(I) In UCB, there exists a constant C >> O. such that
2o BaTTnoTin Tor
Reilwe,, X1i) S CKK²
v VNI-IPE-AA +
N'N--1p?-1
+ dk3 exp
od=
4. Theory
(2) In TS, we have
In this section, we provide comprehensive theoretical guar- antees for the Linear CB under interference. Due to space limit, we move all assumptions Appendix A.
Ni-1PI-16 11lp--1([(G 1d[(Gss] E)2
Kulwei X S R2 exp
8u 1. 1
+ 2dk exp {
N2N
8da L L.
4.1. Tail bound of the online OLS estimator
(3) In EG, have RedWuus X ca(K - 1)/K.
Theorem 4.1. (Tail Bound of the Online OLS Estimator) Suppose Assumptions A. A.12 2 hold. In either LinUCBWI, LinTSWI or LinEGWI, for any h > O, we have
Remark. This theorem extends the results from Ye et al. (2023) to scenarios with interference and K > 2. As Nyp: + xc, the exploration probability in both UCB and TS will converge to 0 when N₂ - xc. Specifically, in UCB, the exploration upper bound consists of two components: the first term arises from the margin condition, and the second term from the tail bound of B. When N₂ is large, the sec- ond term, which decays at rate of will be dominated by the first term, which decays at a rate of ((N--116-1)) -9/2) if we set & = ((N--112--))11 In TS, the upper bound is dominated by the second term, which converges to 0 at rate of
P -10 s dK exp {
h2 2
2d O2LK2
where Lu and Le are some constants for boundedness (see Assumption A. and Pt controls the clipping rate in Algo- rithm 1.
Remark. Given that d, a, La and Ly are positive constants, the tail bound for the online OLS estimator simplifies to
P (13, -111 > hn) S Nxpi-1 As detailed in Assumption A.2, Pt is non-increasing sequence that con- trols the level of exploration in Line 10 of Algorithm 1. As long as N.p? > co, B will converge in probability to B.
Lnp serves as an upper bound that controls the overall level of interference in Assumption A. A larger Ly would in- crease the upper bound of exploration for both UCB and TS.
5

---

Lincar Contextual Bandits With Interference (LinCBWD)
This is reasonable, as a higher level of interference typically results in more relaxed upper bound the probability of exploration. However, Lu has no effect on EG where the probability of exploration is often pre-specified.
as π'" T (1) arg max, wig X 3 and the optimal value function as V which represents the expected reward un- der the oracle policy x². Specifically,
V= =E E Σ 11 = =aw3 X
(12)
4.3. Statistical inference on the online OLS estimator 3,
LaEA
Accurate estimation and inference of β are crucial for ef- fective decision-making A consistent and stable estimate of Ba plays a key role in the algorithm update (Line 13 of Algorithm 1), and valid inference provides deeper insights into feature /mporaance/sellction. Therefore, this section fo- cuses on establishing the asymptotic properties of the online OLS estimator for B.
where the expectation is taken w.r.t. X and w.
Define (4.5) (X A.) X x,,3,_ as the expected reward that unit can obtain given the covariate information and actions of all units at round t. We propose a doubly robust (DR) estimator for V"", where
N₂
Hasi Ro- (X {Tee
Theorem 4.3. Suppose Assumptions A.I-A.3 hold, and NeP oo as N₁ + 00. We have
D
{{
=
N₂
Re- (Wris Xoi)
s=1
VN - 3) 2, O(OaK,o'GT)
(11)
-- (X [x))]] + p (X -- (X
where, for simplicity, the expression of G is specified in Equation (53) of Appendix H.
As a combination of inverse probability weighting (IPW) and the direct method (DM), our proposed doubly robust (DR) estimator offers double protection for consistency with 4a under model misspecification in h;- or f--1- For brevity, some derivation details are moved to Appendix D.
Remark. Theorem 4.3 establishes the asymptotic normality of the online OLS estimator, providing an explicit form for its asymptotic variance. This result holds for the EG, UCB, and TS algorithms used for exploration. Despite the presence of interference, the asymptotic normality of the estimator only requires the total number of units N, to approach infinity. In other words, bidirectional asymptotic normality is achieved as long as either t + oc or the number of units at some stage N₂ + 00.
Theorem 4.4. Suppose Assumptions A. A-A.4 hold. We have
NN(VOR--V D NN(0K,
(13)
where of is given by
o E
+ Var
Σ wx B. v.--10 11
a}
The asymptotic normality of the online OLS estimator un- der interference requires careful treatment of dependencies between units both across time (due the nature of on- line decision-making) and within each round (due to the existence of interference). To address this, we construct specialized martingale difference sequence (as shown in the proof in Appendix H) that effectively accounts for the N₂ units collected up to time f. This decomposition, together with the linear structure interference, allows us to circum- vent the independence requirement of classical CLT, which is central to establishing the asymptotic properties discussed in this and the following subsection.
1 Koo (w, x)
(14)
Remark. The asymptotic variance of the optimal value function comprises two components. The first term arises from the IPW estimator and accounts for the variance of the random noise T/ti- The second term originates from the DM estimator and captures the variance due to uncertainty in the context æ and the interference weight w. Notably, our theorem extends the results of Ye al. (2023) by establish- ing the asymptotic properties of the estimated optimal value function under interference. In the special case where w = 1 in Equation (14), our results reduce to theirs.
4.4. Statistical inference on the optimal value A
4.5. Regret Bound
In real applications, researchers may want to understand how closely the value function approaches its optimal level under the optimal policy n², the end of round t, well as the magnitude of the potential impact of the optimal policy. This further motivate us to conduct estimation and inference on the optimal value function in online learning.
Now we establish the regret bound for Algorithm 1. Define the regret at the end of round T as
T N RT =
E (Ww
X TT W
Suppose that the contextual information X ~ Px and the interference weight W/ W. Define the oracle policy
Theorem 4.5. For LinEGWI, LinUCBWI and LinTSWI in
Algorithm 1, the general regret bound under interference
6

---

Lincar Contextual Bandits With Interference (LinCBWT)
1,000
1,000
0.975
0.975
Optimal
Coverigo Prebbiity or
0.950
0.950
0, 0.925
0.925
0.900
0.900
0.875
0.975
0.850
0.850
0.95
0.95
0.825
0.825
0.800
0.800
500
Figure The coverage plot (3 left) V* (b, right)
can be derived as
5. Simulation
T N, RT = DF=EEBR R
5.1. Coverage Probability
Rud = O log Nr).
To demonstrate the asymptotic normality of B and V* in Theorem 4.3-4.4, we estimate the asymptotic variance and verify whether the true value of /3 and V* falls within the estimated confidence interval with high probability cov- erage under B 1000 times of replicates. By Equation (11) and (13), falls into the confidence region if and only if A (3 - G(3 - 3) z (dK), where df = dK is the degree of freedom of the chi-square distribution. Sim- ilarly, V" falls into the confidence interval if and only if N₂ V.DR - y= I 2a/20V. Additional details of the simulation setup are summarized Appendix B.1.
which is sublinear in Nr.
Remark. The regret upper bound, even in the presence of interference, remains proportional to the square root of the total number of units (up logarithmic term). This aligns with the best achievable regret in literature without interference. This upper bound can be decomposed into two components: (1) the regret due to estimation accuracy (exploitation), denoted by R4y and (2) the regret due exploration, denoted by R For the EG, UCB, and TS algorithms, the regret from exploitation is proven to be o(N,-1/3 and is thus negligible. However, the regret due to exploration varies across algorithms. Specifically, in UCB and TS, R(2) also depends on the interference level Lw. which increases Lyw becomes larger. In contrast, for EG, the probability of exploration is user-specified and independent of the interference weight w. As a result, n2(2) is O(N log Nr) by setting 6 properly. For detailed expressions of the upper bounds for each algorithm and the order for hyper-paraman parameters, please refer to Appendix J.
Coverage probabilities the OLS estimator 3 and opti- mal value function F** under three exploration algorithms (LinEGWI, LinUCBWI, and LinTSWII shown in Figure 1. As 95%. with the estimated confidence band almost always covering the red line. This result supports the validity of the statistical inference presented in Theorems 4.3 and 4.4.
see, the coverage consistently hovers around
5.2. Comparison with Baseline Approaches
First, we compare our proposed method with the classical linear CB algorithms to illustrate the importance of taking interference into consideration. The results are shown in Figure 2 based on B 100 times of replication.
Before concluding this section, we summarize the main findings of Sections 4.3-4.5. Sections 4.3-4.4 and 4.5 are connected through a "clipping rate", Pt- Ideally, setting Pt minimizes regret, but may undermine the consistency of B due to insufficient sampling of certain arms. On the other hand, larger pt would lead to over-exploration and increase overall regret. This trade-off between Sections 4.3-4.4 and 4.5 novel perspective, motivating us to examine both aspects to balance statistical efficiency with regret minimization.
As shown, approaches (LinEGWI, LinUCBWI, and LinTSWI) achieve significantly lower average regrets at faster rate than classical LinCB algorithms, showcasing the effectiveness of Linear Contextual Bandits With Inter- ference (LinCBWD) addressing interference. Without interference (Figure Appendix B.4), our algorithm re- duces the classical LinCB method and delivers similar

---

Lincar Contextual Bandits With Interference (LinCBWD)
5.4. Sensitivity Analysis When We Misspecified
175
In this subsection, we conduct a sensitivity analysis eval- uate the impact of misspecifying the interference matrix. The simulation setup follows that of Section 5.2, except we manually introduce a perturbed matrix for LinCBWI: W, W, + E.. where E. (&iyhssss with ęij ~ Unif( bb b). Any resulting values outside the range [-1, 1] are clipped. Intuitively, larger 6 indicates higher degree of misspecification. We consider {0, 0.5, 1 to assess LinCBWI's robustness.
150
Average Regret nver
100
75
50
Due to space constraints, full results are deferred Ap- pendix E; the main paper presents results for b = as representative case. Notably, = 1 corresponds to substan- tial level of misspecification, given that We & is normalized to lie within [-1,1].
100
200
300
400
500
LinEG LinEG_Wi
LinUCB
LinTS
LinTS_WI
Figure Comparison average regret the presence interfer- ence with K = 3 arms
200
175
Average Regret over Time
results. Further details be found in Appendix B.2.
125
5.3. Computational Time of LinCBWI
At the end of Section 3.2, we briefly discussed the theoreti- cal computational complexity of running Algorithm To empirically validate this analysis, compare the runtime of WI to that of classical LinCB under the same set- ting as in Section 5.2. The results are presented in Figure 3. As expected, LinCBWI WI incurs slightly higher computational time due to its joint updates, but the overall runtime remains within a few seconds. Therefore, computational complexity unlikely to pose practical bottleneck.
50
0
0
100
200
300
400
500
LinEG
LinUCB
LinTS
LinEG
LinUCB Wi
LinTS WI
Figure 4. Average regret comparison when b
1.4
Cumulative (6)
1.2
Figure 4 shows that LinCBWI remains robust, achieving near-zero average regret despite the severe perturbation. This suggests that incorporating interference structures, even when estimated imprecisely, enhances decision-making per- formance and provides deeper modeling flexibility. The robustness of LinCBWI alleviates practical concerns about unknown or misspecified interference.
1.0
0.8
0.6
0.4
0.0
6. Synthetic Data based on MovieLens
100
200
300
400
500
The MovieLens 1M dataset (Harper & Konstan, 2015) con- tains over 1 million movie ratings from 6k users, aiding movie recommendations based on historical ratings. At each round f, user with context X is recommended movie genre (A,)) and provides a rating (Rş)). Here, we define = 1 for "Comedy" and A = 0 for "Drama". There are two types of interference affect reward modeling for Rui
LinEG
LinTS LinEG_W
LinUCB WI
Figure 3. Computational Time Comparison between our proposed algorithm (LinCBWT) and basclines (LinCB)
8

---

Linear Contextual Bandits With Interference (LinCBWT)
Comparison of Rewards Time
Comparison Rewards Time
4.
4.2
4.4
6.0-
4.
4.0
56-
3.-
25
75
100
325
150
175
200
25
50
75
100
125
150
175
200
Lino Littigg Wn
Unics Lniico yn
Optamd
unde
LndCe
Linis
Optimal
LiSTs
Unto
Liiicn WI
Lints WI
Figure 5. Average rating comparison under reward generating model (RGP1, left) and II (RGP2, right)
which is overlooked in classical bandits:
rank factorization (Shi al., 2019; Agarwal al., 2020), we can assume that W. exhibits a Iearnable low-rank structure informed by agents' contextual information, i.e., W, = x where & E IRdxd represents a universal weighting matrix. This matrix can be learned alongside the bandit algorithm to generalize the interference structure. Extending the algorithm in this way requires jointly estimat- ing & and B, which can be formulated as the optimization
(1) Users often rate multiple movies within short time (a round), indicating that one recommendation made to user may influence their ratings for others in the same round.
(2) Contextual connections (e.g., occupation, ZIP code, age) between users in the same round can cause one recommen- dation made to a user to affect the ratings of other users.
problem arg ming, + ET= (I Rr -
We consider two different pseudo-true reward generating processes (RGPs), RGP1 and RGP2, to further evaluate the performance of our algorithms. Specifically, RGP1 assumes only the presence of interference, while RGP2 additionally assumes that the true reward model satisfies linearity. De- tailed setup descriptions are summarized in Appendix B.3.
where À controls the sparsity of t. While promising, this approach requires rigorous justification to ensure identi- fiability, as well further computational and theoretical development. Given the scope of this extension, it presents an intriguing direction for future research.
The comparison results for both RGPs are shown in Figure 5. In both figures, our algorithms consistently outperform classical contextual bandit approaches. Notably, in the case of RGP1, there is gap of average reward between our algorithms and the oracle model, which disappears in RGP2. This gap likely arises because the true reward model may not be linear. Despite so, the effectiveness of our approach can be validated through both scenarios as it consistently outperforms baselines due its ability to account for the potential interference structure. All supplementary code is available at our Github repository.
It is also possible to generalize the reward model in Equa- tions (2) and (3). One plausible extension involves replacing the linear assumption with a neural network, as in neural contextual bandits (Zhou et al., 2020; Zhang al., 2020). While this enhances modeling flexibility and practical ap- plicability, it may introduce extra complexity for statistical inference in theoretical analysis.
Another promising direction is to investigate the regret lower bound in the presence of interference. this paper, we have shown that, despite interference, extensions of classical algo- rithms such EG, UCB, and TS maintain the standard opti- mal regret rate proportional to the square root of the sample size. This is the best achievable regret bound within these exploration algorithms. Parallel research efforts, though at the cost of reduced generalizability. have explored methods to decrease exploration probabilities and achieve smaller re- gret bounds, as discussed in Goldenshluger & Zeevi (2013), Han al. (2020), and He et al. (2022). Extending such approaches to settings with interference remains open and exciting direction for future research.
7. Summary and Future Directions
In this paper, we propose a series of algorithms to address interference in LinCB, supported by thorough analyses of regret, upper bounds, and the asymptotic properties of the online estimators. Before concluding, we outline two practi- cal extensions of this work:
Our algorithm can naturally extend to cases where the interference matrix W, is unknown. Inspired by low-

---

Lincar Contextual Bandits With Interference (LinCBWT)
Acknowledgments
Dedecker, J. and Louhichi, S. Maximal inequalities and empirical central limit theorems. In Empirical process techniques for dependent data, pp. 137-159. Springer, 2002.
This research was conducted under the support the Na- tional Science Foundation through Grant DMS-2113637.
Impact Statement
Deshpande, Y., Mackey, L.,, Syrgkanis. V., and Taddy, M. Accurate inference for adaptive linear models. Interna- tional Conference Machine Learning, pp. 1194-1203. PMLR, 2018.
This paper is the first to address the interference problem in the contextual bandit problems, with broad applicability to real-world domains such as recommendation systems, personalization, clinical applications, and more. We believe that this work, along with the potential extensions discussed in the summary, will inspire future research that advances decision decision-making across various machine learning applica- tions.
Dubey, A. et al. Kernel methods for cooperative multi- agent contextual bandits. In International Conference on Machine Learning, pp- 2740-2750. PMLR, 2020.
Feller, W. An introduction probability theory and its applications, Volume 2, volume 81. John Wiley & Sons, 1991.
References
Forastiere, L., Airoldi, E. M., and Mealli, Identification and estimation of treatment and interference effects in ob- servational studies on networks. Journal of the American Statistical Association, 1166534)901-918, 2021.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. Flambe: Structural complexity and representation learn- ing of low rank mdps. Advances in neural information processing systems, 33:20095-20107, 2020.
Getis, A. Spatial autocorrelation. In Handlbook of applied spatial analysis: Software tools, methods and applica- tions, pp. 255 235-278. Springer, 2009.
Agarwal, A., Agarwal, A., Masoero, L., and Whitehouse, Multi-armed bandits with network interference. arXiv preprint arXiv:2405. 18621, 2024.
Goldenshluger, A. and Zeevi, A. A linear response bandit problem. Stochastic Systems, 3(1::230-261, 2013.
Aronow, P. M. and Samii, C. Estimating average causal effects under general interference, with application a social network experiment. 2017.
Hadad, V., Hirshberg, D. A., Zhan, R., Wager, S., and Athey, S. Confidence intervals for policy evaluation adaptive experiments. Proceedings of the national academy of sciences, 118(15)x2204600211 2021.
Audibert, J.-Y. and Tsybakov, A. B. Fast learning rates for plug-in classifiers. 2007.
Bargagli-Stoffi, F. J., Tortù, C., and Forastiere, L. Hetero- geneous treatment and spillover effects under clustered network interference. arXiv preprint arXiv:2008.0077 00707, 2020.
Hall, P. and Heyde, C. C. Martingale limit theory and its application. Academic press, 2014.
Han, Zhou, Z., Zhou, Z., Blanchet, J., Glynn, P. W., and Ye, Y. Sequential batch learning in finite-action linear contextual bandits. arXiv preprint arXiv:2004.06321, 2020.
Bargiacchi, E., Verstraeten, T., Roijers, D., Nowé, A., and Hasselt, H. Learning to coordinate with coordination graphs in repeated single-stage multi-agent decision prob- lems. In International conference on machine learning, pp. 482-490. PMLR, 2018.
Harper, F. M. and Konstan, J. A. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
Bastani, H. and Bayati, M. Online decision making with high-dimensional covariates. Operations Research, 68 (1):276-29) 2274,299,200 2020.
He, J., Zhang, J., and Zhang, R. Q. A reduction from linear contextual bandits lower bounds to estimations lower bounds. In International Conference on Machine Learning, pp. 8660-8677. PMLR, 2022.
Chen, H., Lu, W., and Song, R. Statistical inference for online decision making: In contextual bandit setting. Journal of the American Statistical Association, 116(533); 240 140-255,10 2021.
Hudgens, M. G. and Halloran, M. E. Toward causal infer- ence with interference. Journal of the American Statisti- cal Association, (03(482):832-8444 2008
Cliff, A. D. and Ord, J. K. Spatial processes: models & applications. (No Tite)) 1981.
Jia, S., Frazier, P., and Kallus, N. Multi-armed bandits with interference. arXiv preprint arXiv:2402.0/844 2024.
10

---

Lincar Contextual Bandits With Interference (LinCBWI)
Kennedy, H. Semiparametric doubly robust targeted double machine learning: review. arXiv preprint arXiv:2203.00 200.02203.06 2022.
Viviano, D. Experimental design under network interference.
arXiv preprint arXiv:2003.08421, 2020.
Viviano, D. Policy targeting under network interference.
Landgren, P.. Srivastava, V., and Leonard, N. E. On dis- tributed cooperative decision-makin in multiarmed ban- dits. In 2016 European Control Conference (ECC), pp. 243-248. IEEE, 2016.
Review of Economic Studies, pp. rdae041, 2024.
Wang, H., Fan, J., Chen, Z., Li, H., Liu, W., Liu, T., Dai, Q. Wang, Y., Dong, Z., and Tang, R. Optimal trans- port for treatment effect estimation. Advances in Neural Information Processing Systems, 36, 2024.
Leung, M. P. Causal inference under approximate neighbor- hood interference. Econometrica, 90(1):267-25) 2022a.
Ye, S., Cai, H., and Song, R. Doubly robust interval esti- mation for optimal policy evaluation in online learning, Journal of the American Statistical Association, (just- accepted): 2023.
Leung, M. P. Rate-optimal cluster-randomizzd designs for spatial interference. The Annals of Statisticx, 5065):3064- 3087, 2022b.
Luedtke, A. and Van Der Laan, M. J. Statistical inference for the mean outcome under possibly non-unique op- timal treatment strategy. Annals of statistics, 44(2):713, 2016.
Zhang, K., Janson, L.,, and Murphy, S. Inference for batched bandits. Advances in neural information processing sys- tems, 33:9818- 08:981899829, 2020.
Zhou, D., Li, L., and Gu, Q. Neural contextual bandits with ucb- basebased exploration. In International Conference on Machine Learning, pp- 11492-1120 11502. PMLR, 2020.
Manski, C. F. Identification of treatment response with social interactions. The Econometrics Journal, 16(1): S1-S23, 2013.
Zhou, H., Li, S., Jiang, G., Zheng, J., and Wang, D. Di- rect heterogeneous causal learning for resource allocation problems in marketing. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 37, pp. 5446- 5454,20 2023.
Martinez-Rubio, D., Kanade, V., and Rebeschini, P. De- centralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 32, 2019.
Qu Z., Xiong. R., Liu, J., and Imbens, G. Efficient treatment effect estimation in observational studies un- der heterogeneous partial interference. arXiv preprint trXiv:2107.122200 2021.
Rosenbaum, P. R. Interference between units in random- ized experiments. Journal of the american statistical association, 102(477):191-200 2007.
Shi, C., Lu, W., and Song, R. Determining the number of la- tent factors in statistical multi-relational learning. Journal of Machine Learning Research, 20(23):1-38, 2019.
Sobel, M. E. What do randomized studies of housing mo- bility demonstrate? causal inference in the face inter- ference. Journal of the American Statistical Association, 399477))1398-14000) 2006.
Su, L., Lu, W., and Song. Modelling and estimation for optimal treatment decision with interference. Stat, 8(1): c219, 2019.
Tsiatis, A. A., Davidian, M., Zhang, M., and Lu, X. Co- variate adjustment for two-sample treatment comparisons in randomized clinical trials: a principled yet flexible ap- proach. Statistics in medicine, 27(23):4658-4677, 2008
Verstracten, T., Bargiacchi, E., Libin, P. J., Helsen, J., Roi- jers, D. M., and Nowé, A. Multi-agent thompson sam- pling for bandit applications with sparse neighbourhood structures. Scientific reports, 10(1 1061),6728, 2020.

---

Linear Contextual Bandits With Interference (LinCBWT)
A. Assumptions
Assumption A.I. (Boundedness)
a. Define Σ == E <x ]
as the covariance of contextual information. There exists a constant À > 0, such that
Amin 2)= > X.
b. vX. ri E X, there exists constant L,,, such that ||Xtill2 2 S La for any L E [T] and i E [No]-
c. WW E W, there exists a constant L such that Σ, |We,yl S Li and E, WW,jel S L for any & [2] and E [Nv.].
Assumption A.2. (Clipping) For any action a and round t, there exists a positive and non- non-inerennt non-increasing sequence pt. such that > Pt-1 Amiin (E).
Amin| N E MN,
Assumption A.3. (Margin Condition) For any e O, there exists a positive constant y 0, such that for any two different arms and a', we have P(O < If(X. a) f(X, a')l < <) O
Assumption A.I includes several bounded conditions. Assumption A. ensures that there is strong collinearity between different features, which is necessary for a stable OLS estimator. This condition is commonly assumed in bandit-related inference papers (Zhang et al., 2020; Chen et al., 2021; Ye et al., 2023). Assumptions A.1.b and A.1.c ensure that the contextual information and the interference level for each individual unit are bounded.
Assumption A.2 is a technical requirement that guarantees the bandit algorithm explores all actions sufficiently at a rate of Pt. enabling consistent estimation of the OLS estimator. This exploration procedure is widely assumed in bandits inference literature (Deshpande et al., 2018: 8; Hadad et al., 2021; Ye al., 2023). Notice that Assumption A.2 is actively enforced in our algorithm. Specifically, Line 10 of Algorithm I ensures that if an arm is explored insufficiently (determined based on and a smallest eigenvalue comparison), the algorithm enforces additional exploration, preventing extreme imbalance and ensuring statistical consistency. In our simulation studies, we simply set Pt- = 0.01 and observed that Line 10 is rarely triggered. Therefore, this assumption is unlikely to pose significant practical concerns.
Assumption A.3, known as the margin condition, a standard assumption in the contextual bandits literature (Audibert Tsybakov, 2007: Luedtke & Van Der Laan, 2016). ensures that the expected rewards of different arms are sufficiently separated, thereby making the bandit learning problem well-posed and meaningful.
Assumption A.4. (Rate Double Robustness) Define the L2 norm as || = V 1 Et En of. We assume that Nr
the convergence rate of propensity score model [| xx:) - KG 1411 X x2)lla,,, = Op(NNT ), the convergence of (t.i) (X, - ((t))) (X, (X) = Op(NTT with a1 + a2 > 1/2.
outcome regression model ||
Assumption A.4 requires that the convergence rates of the conditional mean function and the estimated probability of exploration satisfy certain conditions. This is a standard assumption in causal inference literature, noted in Luedtke& & Van Der Laan (2016); Kennedy (2022). In our setting, this assumption is almost always satisfied, given (N, follows directly from Theorem 4.3. Therefore,
that [| (X,, - (Xx)) (,(.00 (X - x)))2,,,, it suffices to ensure that || (wis, X Ke-1 1 X Xa)ll2.v,
(1) for Assumption A.3 to hold. This can be easily achieved by using a sample-based exploration estimand. In practice, as R (wit, X.s) tends to be small as / increases, we set h (wii, X(a)= = Eese-LEIN.) 1(As + #(X xx))) H/NN,11 which proves to be sufficient in simulation and real data analysis.
B. Simulation Setup and a Supplementary Plot Without Interference
B.1. Simulation Setup in Section 5.1
The simulation setup of testing coverage probability is as follows. In the estimation of B, the entire process is replicated for B = 1000 times to calculate the empirical coverage. For each replication, we assume there are total of T 500 rounds, and we randomly sample the true |3 from 3g = (2, 3,, 3,,1) 1)T and B, = TT
In the estimation of B, we assume N₂ ~ Poisson(5) units are interacting with the environment. X, = (X ( E R3 denotes the feature information of unit i at round t, where X = 1, X1,2 ~ ~N(4, 1), X1.3 ~ Onif(O, 3), and all of the samples are i. over (t, i). At each round, we generate the interference matrix W, E N.N. as follows. Suppose the
12

---

Lincar Contextual Bandits With Interference (LinCBWT)
diagonal elements Wa 1. For each i j. we generate Wa a UUnif(-066, -0.3) + (1 (1) Unif(0.11,0.) 0.4), where DU(1, K).
In the estimation of V** for more balanced variance composition in Equation (14), we set up the data generating process for We and X as follows. For each * j. we generate W1,15 Unif -0.2, -0.1) + (1 - a)- Unif(0.05,, 0.2), where a ~ DU K). For contextual information, we generate X = (Xti,,.... Xu.3) E IR3 for unit i at round t, where 1 = 0.2, X ~ (0.8, 0.04), X Unif(O, 0.6), and all of the samples are i.i.d. over (t,
To establish the asymptotic normality of the optimal value function, we need posit another mild assumption regarding the convergence rates of the two estimation models (propensity score and outcome regression models) presented in the main paper.
B.2. Simulation Setup in Section 5.2
In reward comparison, we K arms and total of T 500 rounds. For each round f, total of N₂ Poisson () units will interact with the environment. We generate the interference matrix W. R- as follows: Suppose the diagonal elements Wa, = 1. For each i > j. we generate Wij ~ DU(1,)) The lower triangular elements are set equivalent to the upper triangular.
Unif( 0.99, -0.6) + (1 a) 0.. 0.4), where
Define X = (X........., Xua) E IRd as the feature information of unit at round Here, we let = 5, where the first column is intercept 1, (Xa,2, Xu.3) ~ (V, Σ), and (X Xu.s) follows some uniform distribution.
Following the reward-generating process described in Equation (2) with linear payoff function (or equivalently, Equation (15)), uniformly sample 3g Unif(- 1), B1 Unif(-1, 5), B3 Unif(-3.3), and replicate this process for S = 100 times to test the robustness of different approaches w.r.t. the change of environment. All experiments were conducted on a local computer with 16 GB of memory.
B.3. Real Data Setup in Section 6
Based on the timestamps of each rating and the relative user density, we divided the dataset into T = 200 rounds. For each round-unit pair (t, i). X E IRd is d = dimensional vector that includes an intercept term, age. gender, and 4 dummy variables representing the top 4 most popular occupation types. We construct an interference matrix W, based on the contextual information of users in the same round using normalized Jaccard similarity. Note that if a user provides multiple ratings the same round (which highly likely according to our observations), we treat them as "different" users with the same contextual information, thus the corresponding element in We is set 1. We proceed with two different pseudo-true reward generating processes.
I: For each user j. we calculate (a) as the average rating of user j under movie type A a. Then the true reward of user at round t given by Rss = Σnn Wr,s (a)).
2j=1
II: Following Equation (2) with linear payoff functions, we fit a linear regression model to Res with
N₂ We, 1..1HA = =a} + Eti,
Ra ΣΣ
(15)
dEAJ=1
to estimate So, B1 and a as specified above. We then use these estimated values to regenerate Rig which we assume represents the true reward of user at round t.
B.4. Results Comparison Without Interference
Using the same simulation setup as in Section 5.2, but with the interference matrix We replaced by an identity matrix, we compare the results of the classical linear CB algorithm with our proposed methods. The results, shown in Figure 6, indicate that all methods yield comparable performance over time, with average regrets converging to zero at a rapid rate. This illustrates that our method, LinCBWI, will downgrade to classical LinCB algorithms when interference does not exist.
13

---

Lincar Contextual Bandits With Interference (LinCBWT)
30
25
Average Regret over Time
20
15
5
100
200
300
400
500
LinEG
LinUCB
LinTS LinTS_ WI
LinEG_V
LinUCB WI
Figure 6. Comparison of average regret in the absence of interference
C. The Derivation of Three Exploration Strategies
In this section, we provide a detailed derivation of the exploration strategies for LinEGWI, LinUCBWI, and LinTSWI, which were briefly introduced in Section 3.2.
C.1. LinEGWI
First, to generalize the classical EG algorithm in the presence of interference, we explore different arms with probability es and select the estimated optimal arm with probability Cti- That is,
Oei (1 Zui) arg max X BiB + Zui DU,
(16)
where Zui ~ Ber(cr)) and DU(1, K) denotes the discrete uniform distribution s.t. P(A = a) K for any E [K].
C.2. LinUCBWI
We next consider the extension of linear UCB to interference-existine scenarios. The key idea behind UCB is to the variance of the parameter estimates, specifically the upper confidence bound, to guide exploration. In the presence of interference, this process is equivalent to comparing the UCBs of W and selecting the action that maximizes the T value. Define Σ, X la x1a) Since Var(3.) o². Ey, the UCB under An E (1,..., K} can be derived as follows:
UCBaia +- wii D + aawual v (T((S1)) Xxix
(17)
where is a hyperparameter that controls the exploration-exploiaaion tradeoff, and (E,-1)=² denotes the d x d block- diagonal submatrix of (Σ,-1)-² corresponding the variance of 3, Thus, LinUCBWI algorithm selects the arm az according to
Ori = arg max UCB
(18)
14

---

Lincar Contextual Bandits With Interference (LinCBWD)
C.3. LinTSWI
In linear Thompson sampling, the prior of [3 often pre-specified. At each round, units with transformed covariate matrix X is used to update the posterior of 33re after collecting the reward Rgg. Here, we adapt a normal prior for B, which follows
(Prior) 3 ~ ==3)== =NN( Σo)
(19)
(Update) Rei - x133+ Th6s Vi (I....,NN) N.}
The posterior distribution of f given {X lit, Alt, Ri.)) can be derived
f(B (X 1a, ALc. RIa)) f(Raa B3, 11)) T(B),
After simple calculations, the posterior mean and variance for 3 can obtained by
E 2j¹ + Ex:X.11
(20)
B Bespus + Ex.post 21 1i +
Σ
i,t
Suppose apper-parameter deciding the level of exploration in TS. For unit i at round t, LinTSWI will sample BR ~ (N poss v² (ppat) and then choose arm Ozi such that
agi arg max Was X 1. ti.a-
(21)
D. Optimal Value Function Estimators: A Detailed Introduction
In Section 4.4 of the main paper, we present the final doubly robust (DR) estimator i/DR and establish its asymptotic normality in Theorem 4.4. Here, we offer detailed introduction to three commonly used estimators causal inference and elaborate on the construction of the DR estimator.
As detailed in the main paper, our goal lies in providing different estimates for y*" where
(X) 3 X + (1 T 33 x
π
The first estimator we propose to estimate V"" is the Inverse Probability Weighting (IPW) estimator, also known as the Importance Sampling (IS) estimator in reinforcement learning. The core idea is to use the propensity ratio, 1/an=== (XX.))
P(an (Xul))
to adjust for distribution shifts caused by exploration. However, since the true values of x- and P(ay n (X 1s) are unknown, replace them with their corresponding sample estimates. Therefore,
N l(asi (
IPW
R (Wois xss) Tsi
N₂
where ( X1s) EOSI-INENN 1(A,, + (Xx,
xx))) sx)) and - (Xx,) is obtained from Line of Algorithm 1.
The second estimator we propose the Direct Method (DM). The concept is straightforward: we substitute the unknown true values, such x* and B3, with their sample estimates in the optimal value function V*" directly estimate the optimal reward. Thus,
N. DE
DDM
8-100 1..
N #=1 i=l aEA
Following the same logic used to derive Equation (2), the above estimator be rewritten as
N
FDM
1
EΣ
(1. pli
X मे
N₂
4=1
15

---

Lincar Contextual Bandits With Interference (LinCBWD)
n: 1= denotes the expected reward that unit can obtain given the covariate information and where 14-1 ,, A.) X
(1.1)
actions of all units at round
By combining the two estimators mentioned above, derive the doubly robust (DR) estimator, where
t
N
ass 1 si)) 1 xi) {rest (X (x + p. (X (c-
D.R
N
In V.D.R the second term, i.e., f'-1 [x T--1 (X,)) Tg-1(Xx))) corresponds to the direct estimator. The first term involving the propensity ratio is an augmentation term derived from the IPW estimator, which provides additional protection against model misspecifications, thereby ensuring double robustness. Specifically, as long as either the propensity score model &;-1 or the outcome regression model pi-1 is correctly specified, V.DR becomes consistent estimator of the optimal value function V* Furthermore, under Assumption A.4 (which is demonstrated be quite mild our setting Appendix A), the DR estimator achieves asymptotic normality the total number of units, N₁, approaches infinity. Details summarized in Thcorem 4.4.
(f.5)
(ttE)
E. Sensitivity Analysis on Misspecified Interference Matrix
200
175
150
125
125
Average Regret
100
100
75
50
50
25
0
100
200
300
400
500
100
200
300
400
500
LinEG
LinUCB
LinTS LinTS_WI
LinEG
LinUCB
LinTS
LinEG_W
LinUCB Wi
LinTS_W
Figure 7. Average regret comparison when perturbation parameter b = 0 (i.e.,
misspecification, left) and b = 0.5 (right)
175
150
150
125
125
Aurorage Regrot
100
100
Average
75
50
50
25
25
100
200
300
400
500
100
200
300
400
500
LinEG
UinCBB
LinTS
LnEG LiEG
LinUCB
LinTS
LinEG_W
Wi
LinUCR WI
LinTS
Figure 8, Average regret comparison when perturbation parameter = 1 (left) and = 2 (right)
16

---

Lincar Contextual Bandits With Interference (LinCBWD)
In this section, we provide the full of sensitivity analysis results omitted from Section 5.4 due to space constraints. As introduced in the main paper, evaluate the impact of interference misspecification by introducing a perturbed matrix for LinCBWI, defined as W. Wr + E.. Here, E. {Gih issJsss denotes perturbation matrix with Eij Unif( b). A larger value of b indicates more severe level of misspecification. We consider b E 0.5, 2 to assess LinCBWI's robustness to such perturbations.
The results are presented in Figures 7-8. When O, i... no misspecification, the result exactly matches Figure 2. As b increases, we observe a modest degradation in LinCBWT's performance: the average regret moves further from zero, as seen in the right panel of Figure for b = 2. Nonetheless, even under this severe level of perturbation, LInCBWI consistently outperforms classical LinCB. These results suggest that incorporating interference structures, even when estimated with considerable error, improves decision-making performance and provides valuable modeling flexibility in the bandit framework.
Lastly, we consider an extreme scenario in which the interference matrix used by LinCBWI is entirely uninformative. Specifically, we generate W. ~ Unif(-1, 1), meaning each entry of W, independently drawn from a uniform distribution and bears no relation the true interference matrix W,, In this case, LinCBWI performs comparably to classical LinCB and even slightly better, as shown in Figure We attribute this marginal improvement to potential overfitting introduced by the more complex modeling structure of LInCBWI.
Importantly, this finding demonstrates that even when the interference structure is completely misspecified, LinCBWI does not suffer from performance degradation relative to LinCB. Taken together with the results in Figures 7-8, this highlights the robustness and stability of our proposed method in the presence of misspecified or uninformative interference information.
200
175
150
Average Regret over
125
75
50
25
0
100
200
300
400
500
LinEG
UnnCB LinUCB WI
LinTS LinTS WI
LinEG WI
Figure Average regret comparison when the interference matrix used in LinCBWI completely uninformative, i.c., We Unif(- 1)
F. Proof of Theorem 4.1: the Upper Bound of the Online OLS Estimator
The proof of this theorem was originally presented in Bastani & Bayati (2020). Here, we provide slightly modified version fit our specific context with interference. Define Σx N. E.
1 N No X xn
X gg. According to the definition of 3,..
X N
11 B112
Σ.
X T7s
i=1
Since Σ, is a symmetric positive semi-definite matrix, we have
5- 1 |1 = Amax (ΣrT)
(mn)(Ee))"
17

---

Lincar Contextual Bandits With Interference (LinCBWD)
where the right hand side of the above equation, by Assumption A.1-A.2, is lower bounded by ped. Therefore,
133 3 Σ
X Mei
(mmin(E) (En)
1
X 7os
1
Σ
Σ
X 8s 7ai
NepiA
iml
==1
im
Define the (th element of X as X1s. where 1 = h,.... dK, with d denoting the dimension of covariates and K denoting the number of arms. For any h > O,
i N,
P (133
B112 hh) 2 P
ΣΣ>
Σ
Σ
sil
S
!hNaped
i=1
2
N,
I.N.ped
N.
A.N.ped
2 P
X 77i
Σ
Tsi
S
(22)
vak
Vak
#=1
1=1
s=1==1
dk
hNepe
= -1
X sis
vdk
To proceed with deriving the lower bound of the above equation, we will utilize Lemma from Chen et al. (2021). As this lemma is directly applicable to our context, we will state it here and refer readers to the original paper for the proof.
Lemma F.1. Suppose {Fa : = 1..... Nor is an increasing filtration of o-filds. Let (Zg q = 1....,Ny)) sequence of random variables such that Zn is Fq-1
Ny) be a o-gaussian, and Mg 1 F all q. Let - 1--m-uaaraallle and [Zg S L. Let fl : q = 1,..., .NT be independent elements in S. Then for any h > O.
S [L......A Nr} be an index set where |S] the number of
h2
PP Σ LEES
ZoHla 2 11
S exp
(23)
2
In our context, we flatten the unit (t, SiST, to a unit queue Qtt, Σ N, measured in chronological order. Notice that the specific order of units within a round does not matter, estimation and parameter updates occur only after all units in the round have been observed. As such, we also use Xq,1 denote the /th element of X To use Lemma F. we define filtration F, as
i, such that all of the units are
F-= =X Ng,)
which satisfies 74 1 F for any g (I....,,N.) Nr..
Let Zy = -Xys. Then by Assumption A.1.b-c.
18 < K
Σ
W W X bj 1 < KLAd.
( W
dKL 12
Define L:= VdKL L.. that |Xp.1| l < L. According to the conclusion of Lemma F.1, we have
hNNepE
12 N X2
P
X Mis
2
$ exp
(24)
vdk
2d 22
Combining the result of Equation (22) and (24), we have
ak
N,
hN&pd
dk
122 N2
(133, - - < h) 21
Σp
X Xii
21 1
Σ
exp
vdk
2d K
1=1
1=1
h 2
=1 - dK exp
O2 o
18

---

Lincar Contextual Bandits With Interference (LinCBWD)
Lastly, since || S vak oll2 for any E IRdk have
h
{
h N N Xa
P (133 B|1 - h 2 P
113 B11 S
21
dK dKexpp exp
vdK
2d k 2
2
The proof of Theorem 1.1 is thus complete.
G. Proof of Theorem 4.2: the Upper Bound of Exploration
G.1. Probability of exploration for UCB
In this subsection, aim to prove that the upper bound of Kez for UCB algorithm satisfies
/VN-IPPIA (
LaLwLz +E) + dK2 exp
N 1
Kelwi, X S CC((K11
(25)
8d 2 L
We split the proof into three steps.
Step 1: Rewrite Krz (wi X Eisa,' SK, 1 [wi:XX
< afōm -B--,,1
Tza (X
For clarity, we first consider the case where K = 2 and then extend the formula to the general case of K. When K = 2.
Kulwei xs) P(An * (x)))x())
=P(Ani o 9r- Tx-1(X(i) क. (x()) + (Ar ne (Xti); T (X
d0
We first consider 61, Based on the exploration criteria of UCB algorithm, we have
An = Wr: X t1
1-11 oō, 0, (X)) > wii X 3 + 1o0
where (X,)) = w X 1:(t-1) X 11(t-1) X with 1:(1-1) 11(--1) denoting the a-th block-
diagonal matrix of dimension d x d that quantifies the inverse covariance associated with arm a. Thus, given that कe i = i.e., X (3, 1,1 3,-1,0) > 0, we have
51 -P(Ass म X (1), -. X 1)
-P(wi T. 1111 + a , (Xu) < whi X 11 + (xx wi wn > wi wi (uX.iBB.11o
(26)
-P < Whi X T. (3 3,0 <a(ū,_1.((..)))
Similarly, we have
d0 -PA # -e- (X f 0)
=P(wii X 3 - + 00,-1,1 X (:) > wii x x 1,100 + (xx) XT < wnixBB.
(27)
=P a (a (x)) - (X x1)) wii X ( -3.-1,0) < <0).
Combining the result of Equation (26) and (27), we have that when K =
KalWii X + = TP (wi (I (B,111 Br-1,00 < (x(0 -x-11(X1)1))
(28)
Now let's consider a general K. Similarly,
K K
Re(WH, X(:) = P(A# * # ( -
P(A + (x A4 -x = d').
a=1m'=
19

---

Lincar Contextual Bandits With Interference (LinCBWT
Notice that when a a', the probability P(Au + - (1), Au a, 1 (i) a equals For any a o a', can treat them arms and and repeat the proof for K 2, shown above. Consequently, for general K, Equation (28) can be extended to
Kerlwhi, X1i)=
Σ
1 2
(Wii
BI-1A') < <a 5 (Xx))))
(29)
Isa,a's 'K aza"
Step 2: Bound the variance term (x-1ia((())
For any a E [K], notice that
-1
Ft-1,((Xi)) = -wi X (11(011)
X S w xrill
max oJ
X 11(11) X 1:(1-1) v
S w X 12 Amax
X (
S L Xmax (X X 1:(1-11)
Amin
(x 1st 11t=
where the first inequality holds by the definition of eigenvalues, and the last inequality holds by Assumption A.1.b-c. Furthermore, by Assumption A.1 and A.2
N > N. PI-1 Amin(E) 2 N/-1 Pt-1A.
Amiu { (I No-1 Amin
X
N
Combining the result above to the expression of dt-1,a (Xis), further derive
Lube
Lubr
(30)
(1 v NN--IPt-1
Amin {
Therefore, for any 1 S a, S K and + a',
2aLnbo
alō:-1,a(:::) ã I.a' (X+) S aafl (X (a x
VNo-IPo-1A
Combining the result above and Equation (29), have
Ku (Wis X10) K(K 1) IP (T B.-),a)) < a, (X (0)1)(X(ss)
(31)
K(K- - 1) IP (T - -(-1a)) 2
VN
Step Further bound the RHS of Equation (31).
For brevity, we denote E.s = Why ce (B, - 3,- and So = W,, - B. Note that in Ço and Çús we omit the dependence on the arms (a,a) a') when there no ambiguity, as they simply represent any two different arms in [K].
For any { > 0, define event E = {les Gol < E). By Holder's inequality and || S ||l||2, we have
[WixX TTB wii TT3. S
B-10 Ball, < L.o [ B - Ball, S Lon 3 Ba Bal,-
20

---

Lincar Contextual Bandits With Interference (LinCBWT)
According to Theorem 4.1,
P((wes x X w. > E) s TP Ter -
Balli > =P(11110110 -Balli
Liobo
< P |13 -B111 > E Lugis) ) S dk exp {
E2Nc-IPi
o L
By the triangle inequality,
GG - Stil - =/ X 1,,3.-1 1-, wi: W/x x,,,3 1, - fwi X, 13
3/ L- 1,00 Wii 1iBat11
S 1 3,,a X 1/5aa + | 11,3-10a' - wii X 11.1111
Thus, for IBea - Sesl, we have
P([Gu Cesl > 5) s P Whi X 1T
11,0 w/s X, 111al + |wi: X 31
1-,00' wix > E)
s P (w X 11
w x 3al
> E/2) PP
W/s x [T 1 Wei X XT1B3 f.. > E/2)
{
N² ONN-IPĀ-11 1²² X²
{
S² 1 X²
I dK exp
+ dK exp
kd K20 L 1
sd3 LEL4
= 2dK exp
Therefore, event E satisfies
N² 1
P(E) 2 1 - -2dK exp
(32)
On event E, we have Gaal 2 1stil - Ses Gal 2 1Geal E. Then going back to Equation (31), we further have
Keiwee Xai K(K- - 1) P 1Gall
2aLwbo
K(K - 1)
2aLwhy
P 1Gul
E VN--IPt-1
+PEE9)
v NN--IP--A
K(K- 1) pP 1Smil -
2atnooo
1NN--11-111" K3 2
ddk((K- exp
VN.-IPa-1
K(K- - -1) PP 1Stal V VNI-IPi-IA
12ppp
2atwwte +
IN 8d3 K3 2 14
+ .dK2(K- 1xp
(33)
ti, a'). Since WT,a = 1, we always have wai 2 1 for any round-unit pair (t, Therefore, |Stsl 2 1f((xis, a) - -(xXis, a')]. According to Assumption A.3, there exists some constant such that F [Gal < VN
By definition, KGsl = (w:: N.l:XT((1 x1, - B&r = |wAl ||(X ti, u) - -[(
2obnlbe + < pp[ [ (ixii,o a f(xei, < 2o - +3] 50 Lo
VNi-IPI-IX
})
By taking this result back to Equation (33), we able to show that there exists constant C, such that
(ea Xis)= 5 K(K - 1) p GGil
2aLwbz
N2N X2
+ dK2(KK - 1) expp {-
VNe-IPe-IA
8d3 K 33 L L1
(34)
2a
+8) + dd< -K) {
&Ñ.IPス1 X²
I SCK(K-I)
/Nr-1Pe-1
8d 833K302 2 L4
where C' is a large positive constant. The proof is thus complete.
21

---

For the simplicity of Lincar Contextual Bandits With Interference (LinCBWD)
G.2. Probability of exploration for TS
In this subsection, we aim to prove that the upper bound of Kez for TS algorithm satisfies
(-
(NN--IPh- IPt- 1 AA[Gal - 8)² ) + 2dK2 - ex)
N
Rellwre xx) S ([]
(35)
8u 1 122
8d Kd
The proof can be split into three steps.
Step 1: Decompose (us (s) and bound it by P(E).
By definition,
K K
Ked (er Xi)) = P(A # (X,
Σ
P(A, * (X An = a, ( = =d),
a=1a==1
where a should be different from a', otherwise the corresponding probability equals 0.
Similar to Step 3 of Section G.I, we define a event E == {1Shs Sasl S {} for any E (0, (Gsl/2), where G.+
Whi X ( - 3.-1ar), and Ges = Wii X (3, - B.r). According to the result of Equation (32), we have
N 8d3 K3
P(E) 2 1 - 1-2KK exp
Taking the result above back to the definition of NeelWees X(s), have
Kurlur X IA - < Σ
P(An f An a, a,fr-1(X1.)) aa E) PP(
Isa,a' 'K axt"
(36)
N2 12
Σ
P(A + Au = a. -
d' E) + -K)
8d3 032
I5a,a' SK aza
Next, we focus on bounding the first term P(Ag + 7 (x), Au which is equivalent
a, ( a' E) for any arm pair (a, d'),
E E 1(Ac * म. 1 Au = a, = =a} 2ai] E)
Step 2: Bound the probability of EE Ars + fr. 1 xi), An = a, ने (X = a'} Ges on event E.
Recall that in TS, we have As arg max, [wi, 11,3,11a where B,1 ((B.,,12A11)) with B,
Ki X1a lat
X 1: Bia and A, X x: lat After simple transformations, for any arm pair (a, a'), whs X 11
Xx 1:
B 1, also follows normal distribution with
Wii W wiXX ~ N ( X,
(37)
where D1-1 Var B,-1.))) (Aii)) aa + (Aiti) d'a' 2 2AAit) aa with (A denoting the d d dimensional llock-diagonal matrix of A71, that corresponds to the variance B 3, and (A,2) an denoting the sub- matrix A representing the covariance between B.-1, and 1, Since D.-1 is symmetric and positive semi-definite, 1 2 (4 am + (A,1)) a' with X = Y denoting that (Y X) is positive implementation, we exclude the interaction term (A, aa' in Algorithm 1, i.e., assuming independence between B_,: and Bar while making decisions.
22

---

Lincar Contextual Bandits With Interference (LinCBWT)
According to the distribution derived in Equation (37), have
I3 Am + - (i), A a, T (X d') Cus
- P w X 2i (B - 3i-1,a') > 0, whi x0 1-1,0 3(-1,a)) < W - -30-111---11100 -
1 (1 - //-11a// u2 D
where (-) is the cumulative distribution function of NV 1).
Denote Eµs wii X x2 (3 -3--1a// hall///eeen oPu X Dr-1 X According to the tail bound established for standard
normal distribution in Section 7.1 of Feller (1991), have
E
[ (A 7 1)), An = M (X | |Gaz]
wht
14 (3, 1,a - 3,,11a)
(38)
s E 1 EE
exp
w X ti 1 1
Define (X = (wn/ V X (x) () x1: 1s(t-1)
Xu. According to the upper bound derived in Equation (30),
we have
4
wh x 11 Di < 20, 20, 28, (x
N 1Pt-1P
Combining the result above to Equation (38), further derive
E
1( + .
a =a} Gei] (3 2-
whi ( X
- - -B-1,a))) ) EE exp
Ni-1Pi- ( X (,, 1.a - -3, 3.-1,ar)3
s E
exp
2 85
X
1
1
81 L
Note that on event E, for any 0 < < 16ril/2 2, 2/ = w X T
(B.- 1,0 - -3,-1,rt) 1ar)) 2 (1Gril - -E)². Therefore,
11
E E
1 1
An
+ - X ;), An a, f.. (Xii) =a'} Gra] E
NT 1P= A N1Gal - g)2 -E)²)
}}}}} exp (
Ne- A(1Sra - -E)2 -. Su2 L2 L3
(39)
cxp
80 L2 13
Step 3: Summary.
Combining the results of Equation (36) and (39), we finally have
(url X K(K - 1) exp (- 1P- A([6na - 5)2
N X2
(K 2dK 1) 1)
8u2 L
8d K3
The proof is thus complete.
H. Proof of Theorem 4.3: the Asymptotic Normality of B
Recall that R[ = X, where X (1 W W&LA A 17, W x.) E BaK Define the number of samples collected till the end of round as N, Ei= N, and further define N == Nr. Therefore, we estimate 3 at round t by
N X
3, = X (x1x
X X..RI.
X X
Ros
(40)
N₂
N₂
aml im
23

---

Lincar Contextual Bandits With Interference (LinCBWI)
T Since Rsi = xx + Moi. can write
N
N X ls
VN,(3, (3
(41)
Here, with slight abuse of notation, we denote the two terms in the above equation 7 and 7/2, which be estimated separately in later steps. Notice that this differs from the sub- uub-Gaussian error of the reward-generatie function in Equation (1).
Step 1: Show that 1/1
E' S77 2, NOaK G).
VN,
According to Cramer-Wold device, it suffices to show that for any BdK
N, v s 2g N(Oak, T Gv).
(1(
(42)
Before proceeding, let's flatten the round-unit pairs {(t. i) ISST, to an unit queue Q(1, = N₂ + such that all of the units are measured in chronological order. Notice that the order of units in the same round does not matter, since the action decisions for all units in round are made at the end of that round. For any "flattened" unit index qo Q(io, to) [L....,NV, we define Hgo the o-algebra containing the information up unit qo- That is,
Hap o
X qu Tl
For different indices 9, there is jump information gathering for Hg whenever q Q(i 1,t) for some Since Xg E Hg. all of the action assignment information collected at round t, i... A,, is contained in Hg at the beginning of this round. With slight abuse of notation, in the following proof, we will also use H4 to denote all historical data collected up to round f.
The tricky part of establishing asymptotic properties for 3, lies in the data dependence. Specifically, the transformed covariate vector X5; a function of (W,, ,)), thus depending on all of the actions and original covariates information collected at round As such, X Mss L X y s' for any (s, s'), since (I) if s', units in the same round are correlated by W.: (2) if < s', unit are dependent since the later decisions made on A. will depend on (W... .. X., Ag).
Now let's use Martingale CLT establish the asymptotic properties. We will prove shortly that {u X si equivalently {u T X, Xyng) after flattening, is Martingale difference sequence. That is, we would like to show
Ele X Mal Hqp = O, Vg E NJ.
(43)
Suppose ((1, for some (1 pair. According to our assumption on the noise term in the main paper, Yeii 1
(X,, A.) + This 1 A, X, is function of (W,, r, X,, At).
Elu T X My Hqp1] = Elp 1,
(AI) E
E X 1 H1g At]
Elng Hg- 1, Ad] 174
Now it suffice to (1) check the Lindeberg condition, and (2) derive the limit of conditional variance.
(1) We first check the Lindeberg condition. For any 8 O, we define
1
X
321
1f1 NN₂
v
X > >6} Hq-1
(44)
4
24

---

Lincar Contextual Bandits With Interference (LinCBWI)
According to Assumption A.I.b-c,
Nr
(v X, 3 <
||
X
K
Wz b, X ri [
5kllol1 Líd
[ Whiss)
S ddK
(45)
Then
1
v
X /
> 8 1
dk
L /
11 > No.01 -1(
n
N 0
NN N₂
dK L2 22
Thus,
N₂
d. m0
10 12 1
N N
3 5
Ng
E
114
2
1
114
2
dk 22 1 10
(46)
aKL 4KLLL2201 Ng
N my Σ
N₂
ak LKLL221111 Ng
It is obvious that N, ng.
Define fN2
1 Mi
dKL f and 98,
dk
|Nx,1 S 9N, a.s. and for all q. Since
E 11 = E
[ A,, Hg- 0² <00,
we have
N₂
dKT2 1.2 1.21 11
ElgN, H4--11
Σ
0²
$ dKL,, 12 11:120²² < 00,
N₂
4=1
thus 9N, integrable for all g.
For each realization of random variable sequence (ng1g-1 1. lim Ny -000 JN, = as 1 my >
N.
0 when Ng is
ak L2, L3 1olll
large enough.
Therefore, by Generalized Dominated Convergence Theorem (GDCT), it follows from Equation (46) that vp S B[fx,, [/p-1] + 0 as + cc. The Lindeberg condition is thus verified.
(2) We next derive the limit of conditional variance.
N E B[(v X 2En A.1
[[(v X,) 21g
H
Ng
s=1
(47)
1
E X (1
where the last equality holds since n/! A; ii.d. (00, Recall that for any unit index y = Q(,, i).
X,= x = (1,, W Widiag(1(AAi = Olisis,,) 1,, W (idiag(1(AA) = 1,,)
After some manipulations, have
M1.1
M1.
Mr,K
M2.1
M2.2
Mr.K
X,X, = X,
E <Rakxdk
(48)
MK.1
Mk.2
MK.K]
where Ma.s' == Ex En We, Xxx u 1fAu = a)1{An a'} is a K by K sub-matrix.
Since we assume Xx ~ X' and W. ~ W are known to us. the main challenge of deriving the conditional variance lies in estimating the conditional expectation of 1(Au = W' +, Xx, H,, 1] for any g E (1,...,N,)) Ng).
25

---

Lincar Contextual Bandits With Interference (LinCBWD)
Recall that H defined as the o-algebra containing the information up unit y 1. That is,
1 X 17 19 1-11-1-1)-
For different indices 9, there is jump in information gathering for H, whenever q Q(i 1, for some t. Since Xg E Hy. all of the action assignment information collected at round t, i... A,, is contained in H.g at the beginning of this round. Thanks to the property of 7, that B[ny|A,) = O, the conditional variance E [[(() X, ,2) 2
B[(('' X )
[[(TT (x,)
for any = (t, t). Still, we take the d'x d sub-matrix Ma,a as an example to calculate the asymptotic
variance.
N
N
W. 1{Ax = a}1{Au d'}
B[Ma,o
= E
Ri
1=1
N
E
W Wr 1{Aex = X H
(49)
N.
N,
W WenWW X B[1[Aux = a}1{Au a'} W X He-1
=
Notice that Ark J. Aul W., Xx, He-1 for any (k; E fI,..., N. and k + I. This independence arises because the actions assigned to units Qk, t) and Q(I, t) are determined by two factors: exploitation and exploration.
1. Exploitation: The action Ae is partially determined by ( where -T is function H4-1 and is obtained by fitting a model data from the first f 1 rounds. Therefore, given (W,, 8, X,, He-1), (X (x) and tt ( (H) are both constants and thus independent from each other.
2. Exploration: The action Au is also influenced by a specific exploration method based on the "optimal" action identified during exploitation. In c-greedy, the level of exploration is determined by cri which is independently assigned each unit. For UCB and TS, the exploration level for each unit is function of Hz-1, making them mutually independent given H4-1-
Therefore,
E [[ = a}1(Aa = d'H X,, X,, = E[1(Au = W X,, He-1] E[1[Au = =d' W'H x,, H4.H4 (50)
For the simplicity of notation, define Deilwri, X He-1) P(An, (X W X He-1) P(Aui #
nt (X.))umn X H.-1). Since
14Ax = a} = ( 1(Au # *X(x)) ((7'(X +
have
E [1fA, a a} W., H4-1]
-E|1A, = n" (X ()) 1f (X a] - 1(4, * 1177 # # W, X,,HH11
W,
(51)
= -P (Xx () Wr, X
(X:) = a) + P(4 x W f, X (x a}
= (1 - (rali X H4-1)) 1a = arg max wi, X { + Pts (wri X 1 + arg max X
Plugging in the result of Equation (50), (51) to Equation (49), one can obtain
26

---

Lincar Contextual Bandits With Interference (LinCBWD)
No No 1==
a = ,.,
W. B[ = a}1(Au = = ; He-1
,,,,
ISkINN,
--VeRWWe tk: H(-1))11 1) arg max (x) + Vex (wek: Xik, H4 11 a # arg max wi X (6935)
(1 U-mulunn Xu, Hi-1)) 1)) arg max wi x, + melwr. Xu, Ha-1)1fa A arg max wi X x11bol
1fa= Σ
ISHJSN
veslwet X tk: 1 arg X (ee X Ha & arg max X (1,3 }
Define (w, a) + P(An # x (a=). Following similar procedure as page 19-20 and Lemma B. in Ye et al. (2023), we can also derive that uea (wi x, H1-1) 2 Kin (w, x), where the limit free of historical data Hz-1. Therefore,
1 N +
0 E
Ma
Ewax
Σ ISAIIS
We. X Joo X1x,, (wrts, B,,',aa)
Ng q=1
(52)
k= Σ
1aa
W X 1o (Wek: X X B.a)
ISRJNN
where J,l 3, (11- Koo (w, 1) arg maxgaa X BB} Ni00 (w, X)1 # arg max wX Bol).
Define (1', v/22' where v1 and U2 are both d-dimensional vector.
Then mn(v) 1 Exnn w² X r4 2, N(aak, v GG) with
NN,
g E[,
N, N, Σxe o2E[Mi,
G=
(53)
E
e M[,1
Σ + o BE
N₂
N₂
where the detailed expression of each submatrix G is given in Equation (52).
Step 2: Show that 172 = { N E. X,,
B, o where 0² E Emn At].
Based on Lemma Chen et al. (2021), it suffice to find the limit of N₂ Ene2 V xxx, v. According to Equation (45), we have
P( X,X, q ol h) < P(ak 23 h).
Therefore, by Theorem 2.19 in Hall & Heyde (2014), we have
as - X v - -E((0) T (x, 2
27

---

Lincar Contextual Bandits With Interference (LinCBWD
Based on the results in Step one can easily derive Bi(v" xx) v GG//o. Combining the results above and by Continuous Mapping Theorem, have
N
-1 -6/0")-- -
(54)
N₂
57
which finishes the proof of this step.
Step 3: Summary.
According to the results of Step 1-2 and Slutsky's Theorem, we can conclude that
VN. 3) = =127 2g WN(ak, ((oaKKo'G)))
(55)
where G is specified in Equation (53). In the special case when N₂ 1 for all i.e., there is no interference, the asymptotic variance would degenerate to
Rg
Koc (B)
G
0².
(56)
Nq q=1
(B)
with
Kooo (33
{(11 Niso
(2x) T (go -11) 2 0} Kico (2)) (Bu (80-81) < <0} JoPP
Roo (B) =
xx {(1 Noo (x)) (B) -B) 2 0} + nxx (x) 181-30 < 00}
Koo
which align perfectly with Ye et al. (2023) in the cases without interference.
The proof of this theorem is complete.
I. Proof of Theorem 4.4: the Asymptotic Normality of V*
Recall that the DR optimal value function estimator derived is given by
T N. lfau = 1 (rei - (1.1) (X ( (xi))) + plo (X,, (Xx1))
1
DR T
(57)
For the brevity of notation, we will omit the superscript in DpR in the following proof.
Now we defined two related value functions Vy and Vy as below:
T
No
lan (X (Tu (n4- (1-p (xx,,xx) + (X (X
NT
T N
1(an (Xa)) P(an = n (Xx)) (ru
V
+ ( (x0,0((x
NT
1=
The proof of this theorem can be decomposed into three steps. In step 1, we aim to prove Vr Vir (N In step 2, show that V Vr ON In step 3, show v Nr v*) 2, N'(0, ot), where the variance term is given by
of = / 1 -
o² dp
En Nr
Var( x TT + (1-11-100 T" (x)) x Bp)
Combining the above three steps, the proof of theorem 4.4 is thus complete. Now, let's detail the proof of step 1-3.
28

---

Lincar Contextual Bandits With Interference (LinCBWT)
Step 1: Prove that 7y Vi + (N(NT 13).
Notice that the different between Vi and V lies in the estimation accuracy of (1) the propensity score function Rz-1 and (2) outcome estimation function p( To simplity this problem, we introduce another intermediate value function V as
T
N₁ 1an MT (X (Tu Pl (X ix (Xx))) + + (X -.- (Xxi)).
1
Now the problem becomes proving (1) Vy - Vi + op (NT and (2) Vy Vy + op First, let's prove (1) VT
VT op(NV Notice that
VT
T
1 1asus xX-1
1sau -
{rE: (11.0) (X, -2 - (x:))
(X,,
NT
- (X)
( ti)
[=1 i=1
T N;
1fats Mh- ( " p4- (X (
(1.1)
ΣΣ
-x
NT
f1- 1 (x1s) (
This can be further decomposed to two parts:
1 1(ati = - Pei xx
NT 1=
[1- ( Kr- (X))
A
1as = 7 ( (x - i x
p(1.0))
( - -x-1(X(i))
NT
{1 RI-1 (X (X))
Aa
We first show that A is (T))))))). Similar to the proof of Theorem in Ye et al. (2023), we define a class of measurable functions
F(X,, ats, ru) (Ri-1(X() - (x laa = - (Xa)( (((10)) (x, Re, A, El
{1 -1-
where A and II are two classes of functions mapping context X's to a probability in [0, 1]. Denote the empirical measure Gn = ,nP,, Pf). Here, n = Q(t, i) is the sample index, which is determined by reordering the units E {l,.... No} according to time Denote ||=|| r = sup |=()). Therefore,
GG,llr sup fell
Σ
[F(X,, an, BFF(F -B((X))))B((B.....B rk) H4-1))
(58)
NT gEQ(t.))
Since (((d)) in F is correctly specified, we always have
E F(X X c. Ori r1s) 1/:-13
1aan = क. (X.i) (Tus 1000 (X, 2 7 (x,)))
= E
(X)) (X
Hi-1
{1 ki- (X ((i))(11 Kr- xxi)}
1far = (X Exs
E
-X
He-l
P Xx:) 1:) Fit 1
29

---

Lincar Contextual Bandits With Interference (LinCBWT)
According to the iteration of expectation, the equality above be further derived
i{ aes re)) H
B (a = Tx Bled X Ad) He-1 = 0, (xx) - (x,)(
E (X ke-1 (X-1(X(())
where the last equality holds by E/m X A.] 0 according to the definition of noise Thi Therefore, Equation (58) can be simplified as
||.,| =ell
sup
Σ
F(Xi,atisti an)
NT QEQ(L..)
Following Section 4.2 of Dedecker & Louhichi (2002), we define
di di( (I,,
d2())= (n)
First, we show that both d1 (f) and (f) are finite numbers. For the brevity of content, we will take d2(f) an example and (f) < do can be proved similarly.
In valid bandits algorithm, the probability of exploration Ky (Xx)) is bounded away from 1. That is, there exists constant C such that (X.) P(aa # (Xx)) s C1 < 1, and (xxx)) I C1 < 1. Therefore, for any {l..... T).
(f Cri
lan R 1 (X (1))) (1) (1(1)) Tr xX,)
{ 1 (X(s) - -X
He-1
{1 - R (X (1)){1 - K3- (xs))
R 1x)) K (X,)
E
lfan x {res (1.0) (x,,, (x)))) H4-1
P4-1 1 (X (i))1 Kz-1( (xxi) (:)
R 1 (Xi) Ki-1 (())
E
laa = f.-1(X E Xe, Ail
He-1
Re-1 (X {:)) Kz (X
2
12 <0.
1 - C1
Therefore, by Rosenthal's incquality derived for Martingale [see Dedecker Louhichi (2002) for details], we have
E G. S K
S
dz()) +
1
max (EQ(t.))
F(X,, 0zi ree) - FE an, (a) Ho Ho-
(59)
VNr
Since the right hand side is (T-1222 we have
A
Σ
F(Xx, Oti
[[. = O,(T-1) o, (T-111/2)
(60)
N
NNT
30

---

Lincar Contextual Bandits With Interference (LinCBWD)
Now let's derive the order for A2-
T
Ne
1ia (x-1(X(i) (((..)) (X (x-1 ((..0
Pi-1 ,
2
Ry (X.:)) -
NT
{1 R (
T N
C2 x - (X
| ( m= - / (2.0) (X,, (x,;
NT
1=1
C2
(o-
1
Σ
((.)) (x,,xx, - (
NT
NT
1=1i=
= [N 1/3)
(61)
where the last line holds by Stuchy-Schwarre inequality, and the last line holds by Assumption A.4.
Combining the results of Equation (60) and (61), we have
V VT A D (NT op (2(N7
(62)
Now the question becomes proving (2) Vr Vi + (x( 1
T N
Utu = -ा (ii))
V
Vr
(x., (0.00 (x.
NT
1 K4-1 X(i)
Following similar structure we prove A =Np 1/2, one can define a new class of functions
{[-- 1 1an = -X (X))))
F'X (a,
(xx= (x + E.R. A
1 (X
and using Rosenthal's inequality for Martingale to prove that V Vy = =op(NT111)
Step 2: Prove that V = Vi + ON
By definition of V and Vy, we have
No
Han - (X
VNT(Vr V7)
(x,,
NT
K ((ii)
43
(63)
T
1aa मे (X
11am TT" (X(s))
Tut-00 x(x:)) (X:))
Ki X(s)
P(ass = n" (X.i))
Step 2.1:
We start from proving A3 = (1). Since K2 (X.) S Ci < 1,
is upper bounded by a
1-me-1(Xa)
constant. Therefore, to prove Ag = (,.(), (1), suffice to show that
1 T N N
(1,0))
(X,, T (Xx)) - (1.0)
(x)) =1)
(64)
31

---

Linear Contextual Bandits With Interference (LinCBWT)
Before proceeding, let's break down this term do some transformation. Notice that
N
N₂ N N₂
Σ
(5.0)
W7,6 8.B. (X()) = a}
aEA
N
Wi 1/ ((x:)1(X(t)) = =a}
aed
(65)
Σ Σ
We.t XTB. 1 = 0}
Wei
X 31
11 a}
REA
where the second equality holds by switching the index of (i,j) to (j. and the third equality holds by Fubini's theorem. Going back to the previous equation, we have
T
(00 (Xi) (x,,
=1
N.
WH (x 13) a} - 3, 1(f)-1(X1)) at
VNT t=1 1=l aEA
T N₂
=
Σ
WHXX W BBx) 11= = a. -xx)
=
VNT i=l KS
N
Σ
wix wriXT(BB - 33a) 1( - ) 50
Sa,a EK axta
Again, for the brevity of notation, we denote G.i = Wii X (3 - and Gii w.: w - Bar)
Let's first consider the case where Su > O. The opposite scenario can be derived in a similar manner. When Sea > 0, the RHS of the above equation is thus equivalent to
T N.
T
ΣΣ Σ
11Gu 50 (
Su
1
ΣΣ Σ
1B3u S 50)- Su-
NT
NT
i= 15e,a SK axt""
1sea's axa"
<K
Since ((Gu S 0) Ees 5 O, we have
(1lt:0) (X,,, (x))) < 11f s 50} . G. < 1f2sr S s0}- (Gi - Zes).
To show that 2/ 1 |1(t,)((,,, xxxi) (X,,
th -x,1 (1), it suffice to prove
T N
:- N: 1/2
Σ>
1 (G 20} (S: - Ga) = (1).
1=1
32

---

Linear Contextual Bandits With Interference (LinCBWT)
For any a E 10,1 we can further decompose
T
N₂
Ç = P(O < Gi < <
ΣΣ
1
13 50} -Gis - 2vd) 110 < Sts < <Nr
VNT
i=
N
+ P(Gni 2 ")
1sa S 50}- (Ges - -Ga) 1(t 2 NT
C2
First, we show S = (1). According to Theorem 4.3, Gti Cti Op(N, Therefore,
(N (1/-01/2-))))) for any ary > 0.
T N,
T N
13n 50} - (Gu - G.) 110 < Ga < Nr S
Sei - Gea
NT
v NT
t= i=1
S NT NT
Sta Gel NN (Ny (1/2)/20))) = (vT
where the second last equality holds by Lemma 6 in Luedtke & Van Der Laan (2016).
Since W 2 1, by setting- e NT in Assumption A.3, we have P P(O < [w](X a) w((X < <NT9) S
P( < fx a) - a(),'') < < = O()7")) Therefore,
Çi = P(O < Cu < <NT")
1
Σ
16a 50} (Sr (Gi) 110 < Su < NT
VNT
t=1 ==1
(66)
< <|p(0< < ty < NTT
16a s $0} (Gis - -ia) 110 S1s < NT
VNT
5O(NT (N((N))))) = =1)
Next, we show 22 = (1).
Since 1 s 0} = 1LGr- - Gi S -Gi} 1 116=== Geal > Gea). we have
12t Gtil
Ges Seil" 2 Sti
11t s 0) - -Gai = 111 - Gail > Gii [2r Guil S
12es
Geil
(67)
Gti
Since we assumed that Sos > 0, based on the result of Equation (67), we further have
1 S 07(G - -Gx) S GG+ 2 as Gei - -ec 2 0 always holds. Additionally, notice that 1 1(rr 2 N) S NNNg. Therefore,
Sis
T N
= =PGr 2 NT
12a 50} (Gi - -Gi) 1ffri 2 Nr
T N
Sail
T
N Ges Gril
NNNN = N 11/2ta
NT
Sii
Ny
F1
By Theorem 4.3, Gei Gnl = 1/2), which implies Ges - Gril - (
)) According to Lemma 6 of Luedtke &
Van Der Laan (2016), Nr Et=1 Σ,4, 12tt 2ul22 = O₂, )) Therefore,
T N
S2 $ N
1/2+a
Gu Seal2 < N4 Op(NN')= = (1)
(68)
NT
33

---

Lincar Contextual Bandits With Interference (LinCBWT)
for any < 1/2.
Combining the result of Equation (66) and Equation (68), we have
Ç -= 11 + 62 = op(1) + + = =
(69)
Therefore, N Et= Ein |elli) (x, (X))) (1 op(1), and thus A3 o,(1). The proof
of first part is done.
Step 2.2: Next, we show that A4 = (p(1) as well.
Recall that
T N
[an = {ax==
1
laa = x² (X(i))
4 =
rrs ( (X (X1))
V NT
1 1 Ki-1 (Xi))
P(an xz (X(i))
t= =
[(an n, (x+))
1an = x¹ (X
{TM- -1000 (X n5' (Xx)) 1aas x (Xx)))
VNT
K4-1 (i)
P(an = x² (X)::)
i=1
+ 1 Ni
[1a;; -4 (Xu))
I's - ((6-0) (x Xx
x x (Xx)) 1aa # TT' (X()))
VNT
1 1 (x:)
[=1
T N.
laan = k, (X
1aas = TT' (X
7hs 1aa = x² (X))}
VNT
- K (i)))
P(an x (X
t=1 ==1
6a
1an = म.- (Xti}
(ult00X (x:;m--(XX.) 110,00 (Xt; (Xx,)) 1aani + T (X))))
1 Ktt (1))
6
T N
1ay = (X
Mh 1aa + x (x)))
NT 1 1
(70)
We only need show S3. S4 and Ss all (1). The proof for S5 is similar to that for Sa using Rosenthal's inequality for Martingales. Therefore, we will focus proving C3 and S4. and omit the details for C5 for brevity.
To prove C. = (1), we define function class
1 {
1 fan ス. (X+))
1aa x* (X,))
F(X,, ais, ma) =
1- (
7hs 1aa = T" +'(x)) i E A, A
P(a x (X(:))
where A and 1l are classes of functions mapping context X to a probability in [0, 1]. Define the supremum of the empirical process indexed by F
G |1 == sup mEll
Σ
[F(X,, ou, 76) EFF(X, aus ms)) He-13]
(71)
N gEQ(E.))
Since E.. mas X.,, 1., A,] 0, according the iteration of expectation, the second term in the above equation can be derived as
BFF(X, X, 1, ari T1:) He-
1 fas = -
1/am =
= E
1 1ams (X()))) E(yed X cs, Ai] Hi-1 = 0,
1 (x+1((11))
P(an nT" (X,,,,))
34

---

Lincar Contextual Bandits With Interference (LinCBWD)
Therefore, Equation (71) be simplified
||,,
sup sEll
1 VNT
Σ
F(X m(x
QEQ((.))
Following a similar derivation structure as that used between Equation (58) and Equation (59) Step 1, we have
F(X 0ei, Mei, [EF(X 1, aui ma)) He H H11
33 S [| K (d(())+ +
0p(1).
(72)
Nr
sEQ(t.3)
Next, let's prove S. (1). Since both - and 1saei n² * (X::) can be upper bounded, it suffice to prove that
I-Ke-1
((it00 (x,, (1:))) (X,, (X))) =1)
(73)
which has already been established in Equation (64) in Step 2.1. Therefore, S4 = (1( Combining the results above, we have
A = + S1 + +5 op())
(74)
The proof of Step 2 thus complete.
Step 3: Prove that /Nr(VV - Va') 2g N(0,,t)) and derive the asymptotic variance of.
Recall that
T N.
1 aan = x² (Xxi))
V/
(ru -00 (X (xx)) (x,,,(x,
NT
P(a T (Xx:))
t=1
N2
lan = x² (X
Thi (((t) (X,,, xx' (Xi))
NT
P(an T" (X)))
Given the derivation of Equation (65), we have
N
N₂
(X.,'
=
wi X TTB (X)) aa.
(75)
1= aEA
Combining the above term with the expression of V7, we have
1(an = x xX(
Vy NT
P(an = x³ (X))) mh + Σ
Whi X 1(x((xn) =a] ml)
acA
To decompose, define
1 (ay = T" (Xx))}
Eg = P(ay = n* (X₂))
77 +
Σ
Wii X
1fT"" (X+)) (xTT((())) = =a} 1**
(76)
AEA
Sig
Eoq
where g denotes an unit in a flattened unit queue Q(t, = E'-1 N₂ + i. Similar the the proof of Theorem 4.3, we define Hy as the algebra containing the information up to unit where Hgo = =o X .m.....,
X go Tog)
Since
E E2gl =
Σ
WH X
=a} -V* =0,
A
35

---

Lincar Contextual Bandits With Interference (LinCBWD)
it holds that El[2g Hy-1] 1] = 0. Additionally, notice that
1 (dg x² (X P(ag x (Xx)) 7g M = E
1 1 = -- (X P(ay = T (X
BlEiy (551)114y-111 = E
1,
Ail 0.
Thus, Ele, Hy-1] 0, and ( is Martingale difference sequence. To show that V NT 2 (0, and derive the asymptotic variance oy. it suffice to check the Lindeberg condition and use Martingale CLT to establish asymptotic normality.
(1) First, let's check the Lindeberg condition.
NT
NT NT
1
Egl 0)
Hlp-1
=
1
Sq 1 2 N2 H H
NT
Notice that ( need to check the integrability of E given M then by Dominated Convergence Theorem (DCT), the Lindeberg condition is checked.
2 ) converges as Nr goes to infinity and bounded by <g given Hn-1. Therefore, we only
Since the derivation of LE [1y1] is exactly the asymptotic variance oi we will leave the details to part (2).
(2) Next, we derive the limit of conditional variance o.
>
NT 1 H1-
Nr
1[ag (X,))
1 1{ag = n'' (X g)}
E[cī,/ Hg-11 =
Mi
n/1 Hqp
= E
[Pppa = x (X,,)1 Elng Hg A A0l
[P(ag T" (X,,)²
[la = =x((x,,
= E
0²1 12
[Paag TT" (X₂))}²
Therefore,
Nr
N - 1g 9. H4-11 [aagg x" (X }
EiS? 2 HH. 1] = 0² E
NT
NT
9=1
where (X.. g. (4-H411) = via X ni 11-1) = P(A # Th (x+))
X H4-1).
Following similar proof structure of Ye et al. (2023) Appendix page 34-35, we are able to establish that
1
NT
1
Nr
1-
H4
σ²
Eigy H 1| =0² 0².E
dP
NT
NT
Plaa
1 Koo (x)
where Kioo (x) = +im P(AN # x (x))).
Since E E(E2,] and the randomness in E2n only comes from (X, w), we have
E 122 Hg--1 Var(Ezg)
Var Σ
Wi X B.Ba 11TT - =a}
aEA
Furthermore,
1 1aag nt" (Xx))
1(a n"" (X,))
B[gigE2 (4g-1) E Ezg
77 Hg
Ezg
FE1n A.]
P(ag = T5" (X,))
Paaay = T" (X₂))
Thus,
Nr
1 Nr
E E
2 Hgg 11 1]
El(E1q + 211
NT
NT
q=1
9=1
Nr
Nr
2 Nr
1
E 1p--1] +
Ble 1 +
El 12 Hq-1]
(77)
N₂
No.
N₂
1=1
9=1
+
dPa + Var
Σ
Wex T B. 1|T" (x) = at
1 -
Koo (
36

---

Lincar Contextual Bandits With Interference (LinCBWD
Therefore,
/
oi
dP + Var
Σ
wa
1 (x) =
=a] a3}
(78)
1 Roz
acA
Finally, by combining the results of Step 1-3, we are able to show that v Nr V=a) 2 N(0,0)) which concludes the proof of this theorem.
J. Proof of Regret Bound
Step 1: Decompose Ri 144' + R2 which accounts for the regret of exploitation and exploration.
Recall that the regret R is defined as
RT
Ll X (X))) (X
(Xx: A.)l
T N2 E
T N2 +
(1.0)
X ग5 (X.))
(X 9. (x(10)(x(,
(x)))
Ia (1.i)
(x,,,=((X))) - (X,, A.)].
t=
which can be decomposed into
T N₂
Rr
ΣΣ Σ
E (1.))
- 100.0 (x.x'(x
t ( xx))
((00)) (X (X Ai) 1{Au # (X
By definition, RT is nonzero only when x² (Xx)) * f (Xx). which accounts for the regret caused by estimation accuracy, i.e., exploitation. nL is nonzero only As F 1 which accounts for the regret caused by exploration. In Step 2-3, we will derive the regret bound of Rz and R! separately prove the sublinearity of Rr.
Step 2: Prove that 2 = o(
Notice that in the proof of Theorem 4.4, step 2.1, we've proved in Equation (64) that
T
N
(X.,
- (1.0) (X,, R, (x,,, = (1).
Therefore,
T
N₂
R
(1(0)) (x,,' - xxx,))((X))) = (2.
Step 3: Prove that R242) = (N /2 log NT).
According to the upper bound derived in Theorem 4.2,
N.
R
(1+i) (X,, (X (xx)) - (X,, 1fAN * (
T N.
T No
< 20
ΣΣ E[1(Au # - = 2U
Σ
Ris Kes(wes X X(s).
37

---

Lincar Contextual Bandits With Interference (LinCBWD)
Now let's decompose according different exploration algorithms. For simplicity of notations, continue with the flattened unit queue q Q(t, Σ N₂ + as shown in the proof of Theorem 4.1. As such, extend the definition of Pt to Pa by simply setting Pq Pt. for any unit g in round t. As such, Pa is still a non-increasing sequence w.r.t By Theorem 4.2, we have
1. In UCB, (wr, ( is upper bounded by OKKL (Ng- 712). Let P4 = =N N with u > 0. For y > u, Pq is decreasing. Then
N Kis (wit X() 2 Ly K K2
u/2 OL S.
RT
Taking u = 1 gives us R O N ) note that when the interference constraint Ly or the number of arms K is large, the regret bound R tends to be larger.
2. In TS, (el (t)) is upper bounded by O(dK3 - exp(xexp-NN--11 -N L Let Ps Valog g/ Then
KeelWei Xa) S O(d' expl exp log(g 11)/ = O(dk'q ------aa a) Thus,
T
N₂ Rec Keewrrs X S dK's
Nr
R
Σ L--a
Odd''s (NdKKNN- No-1
When the interference constraint L is large, the regret bound R tends to be larger. By taking = L we have R = Odk N2/2 = O(N7/22.
3. In FG, (usluri, X1i) = 2 If we set cg 0() with any < 1/2, then
T N
Nr
Reilwi X x
Σ m =
-
q=1
By setting 6 O(log 9/ v)), we have R( ONN log Nr).
Thus, in UCB, TS, and FG, the regret caused by exploration can be controlled by R = O(N! log NT.).
Therefore, by combining the results of Step 1-3, we are able to show that
T Ni
R = Σ
E - Ral = =O(N log Ny).
1=1
which is sublinear in Ny.
38


Reviews:
[{"review_id": "XZIsakoXlL", "reviewer": "Reviewer_f3ef", "summary": "The paper introduces a framework to address Linear Contextual Bandits with interference, where the actions of one unit can affect the rewards of others. The authors bridge the gap between causal inference and online decision-making by explicitly modeling interference through a linear structure involving an interference matrix. They propose three online algorithms LinEGWI, LinUCBWI, and LinTSWI, which extend classical algorithms by incorporating interference-aware reward modeling. They establish regret bounds and provide numeraical results on the generated based on the MovieLens data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful questions and the time you spent reviewing our paper. We really appreciate your insights and are\nhappy to discuss any further ideas or questions you may have.\n\n**Q1**: \n\nIn the 2nd paragraph of Sec 7, we briefly mentioned how we could proceed to jointly estimate $(\\Phi, \\beta)$ when $W_t$ is unknown. A simple way to proceed is through **Alternating Optimization**: initializing $\\Phi$, optimizing for $\\beta$, then fixing $\\beta$ to update $\\Phi$, and repeating until convergence. \n\nSseveral interesting questions arise. First, identifiability of $(\\Phi, \\beta)$ needs careful consideration, especially since $\\widetilde{X}_t$ depends on $\\Phi$, which may introduce issues in distinguishing their effects in $\\widetilde{X}_t\\beta$ without additional assumptions. Second, the convergence of the alternating updates requires further investigation. Finally, the sample size for accurate estimation of both parameters, and consequently, for effective action learning and reward accumulation, would likely be higher than in the case where $W_t$ is known. We expect that **the algorithm-wise implementation is relatively straightforward, but how to establish the theory behind would be an interesting future work**.\n\nTo evaluate the impact of a misspecified interference matrix, we conducted a sensitivity analysis, summarized in Sec 1 of https://anonymous.4open.science/r/LinCBWI_ICML_rebuttal-C829/. The data follows the same simulation setup as Sec 5.2, except we manually set a misspecified matrix for LinCBWI: $\\breve{W}_t = W_t + \\Xi_t$, where each element of $\\Xi_t$ is generated from $Unif(-b,b)$. Any values in $\\breve{W}_t$ exceeding $[-1,1]$ are clipped. Notably, LinCBWI remains robust, converging to the optimal decision with negligible error even under substantial misspecification ($b \\leq 0.5$). Even in the extreme case where $\\breve{W}_t \\sim \\text{Unif}(-1,1)$ (completely unrelated to $W_t$), LinCBWI slightly outperforms classical LinCB. This suggests that **incorporating interference structures, even when poorly estimated, enhances flexibility and provides deeper insights into the bandit framework**. We hope LinCBWI’s tolerance to misspecification alleviates concerns about unknown interference.\n\n**Q2:** \n\nThe computational complexity of LinCBWI is approximately $O(d^2K^2\\bar{N}_T)$. Specifically, for each unit $i$ in round $t$, the primary computational costs arise from matrix inversion (Line 7 of Algorithm 1) and the smallest eigenvalue computation (Line 10), both requiring $O(d^3K^3)$ in standard implementations. However, using optimization techniques such as iterative eigenvalue decomposition and the Sherman-Morrison update can reduce this to $O(d^2K^2)$. Multiplying by the total number of units $\\bar{N}_T$ gives the overall complexity.\n\nTo empirically validate this, we compared the runtime of LinCBWI with LinCB in Sec 2 of https://anonymous.4open.science/r/LinCBWI_ICML_rebuttal-C829/. In classical LinCB, the complexity is $O(d^2K\\bar{N}_T)$. LinCBWI introduces an additional factor of $K$ due to interference, requiring a joint update of $\\beta_a$ for all $a \\in \\mathcal{A}$. Since our algorithm consistently runs within seconds, **computational complexity is unlikely to be a bottleneck**.\n\n**Q3:** \n\nWhen multiple observations are collected from the same user within a single round, each movie recommendation $A$ and its corresponding reward $R$ generate a new data tuple $(X,A,R)$, meaning a user can contribute multiple tuples per round with the same $X$ but potentially different $(A,R)$. These observations can be viewed as coming from \"two persons with the same brain\". As a result, these data tuples naturally exhibit interference with the highest weight (set to 1), since they originate from the same individual.\n\nRegarding the question of how to evaluate the fit of reward design in 'I' and 'II' of Appendix B.3, there is insufficient data to directly assess their closeness using the existing dataset. This limitation arises because we are working with an offline dataset to simulate an online bandit setting, where the \"actual\" reward is typically assumed to be observable.  In our setup, $R_{ti}$ may depend on the actions of all units in round $t$, leading to $K^{N_t}$ possible reward realizations. However, in an offline dataset, we can observe only a **single** realization among these possibilities. As a result, the \"actual\" reward is not directly identifiable; we can only approximate a pseudo-real data environment to capture certain aspects of real-world behavior.  \n\nNotably, the only two existing works on interference in bandit settings (Jia 2024; Agarwal 2024) have only conducted synthetic experiments. By incorporating semi-real data analysis, our approach takes a step forward that better approximates real-world applications.\n\n**Finally**, thank you for pointing out the typos in our writing. We will incorporate them into the final version of\nour paper and sincerely look forward to your feedback.", "claims_and_evidence": "The claims made in the paper are supported by theoretical derivations and empirical evidence and no problematic claims were found.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for addressing interference in contextual bandit problems. The authors clearly define interference via an adjacency matrix, allowing flexible modeling of different real-world problems.", "theoretical_claims": "I skimmed through the theoretical results but did not thoroughly verify all proofs in detail.", "experimental_designs_or_analyses": "I reviewed the experimental setup and analyses presented in Section 5 and 6. The experimental design is clear and reasonable although no baseline for LinCB under interference are available and hence the algorithms are compared to their non-interference algorithmic baselines.", "relation_to_broader_scientific_literature": "This paper extends recent works in the bandits with interference literature to the Linear Contextual setting. Related works", "essential_references_not_discussed": "The authors have cited the most relevant previous works in the area.", "other_strengths_and_weaknesses": "Strengths:\n\n- First work addressing contextual bandits under general interference.\n- Novel asymptotic analysis of estimators under complex dependencies induced by interference.\n\nWeaknesses: \n- The computational complexity of the proposed algorithms is unclear, which is typically an important aspect in this subclass of bandits. \n- The way the proposed \"Pseudo-true-reward” generating process (as Described in App. B3) is carried out is a bit dubious (see questions below)", "other_comments_or_suggestions": "Typos: \n\n- Lines 31-32: \"a synthetic data generated\" → \"synthetic data generated\".\n- Lines 106-107: \"to to\" → \"to\".\n- Line 412: \"of interference of interference\" → \"of interference\".\n- Line 151-152: \"i.e.\" → \"i.e., \".", "questions_for_authors": "1. The authors state that their algorithm can be adapted in case of unknown interference Matrix inspired by techniques on low-rank factorisation. Could you please discuss at a high level what you believe the impact of learning such a matrix would yield to the algorithm performance? Is there any way to quantify the impact in case of misspecified interference matrix ? \n\n2. Can you characterize (even roughly) the computational complexity of the proposed online algorithms LinEGWI, LinUCBWI, LinTSWI?\n\n3.  Why if there are more observations from the same user the correspojding element in the intereferene matrix is set to 1? Is there any way to evaluate the fit of your model (i.e. the reward you design in Point I,II in App. B3) to the actual data?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review."}}, {"review_id": "e52KLgPfkT", "reviewer": "Reviewer_JVt5", "summary": "The paper explores the intersection of causal inference and multi-armed bandits, specifically in the setting of multi-agent bandits with interference among agents. According to the authors, this is the first work in the literature to incorporate contextual information (i.e., the covariates of units). Under certain assumptions, particularly linearity, the authors propose an algorithm with three exploration variants to address the problem. Both theoretical analysis and experimental results demonstrate the effectiveness of the proposed approach.\n\n##  Update After Rebuttal\nAfter reviewing the authors’ response, I have decided to maintain my current score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful questions and the time you spent reviewing our paper. We really appreciate your insights and are\nhappy to discuss any further ideas or questions you may have.\n\n**Q1**: \n\nEq. (1) models the reward of unit $i$ in round $t$ as $R_{ti}=\\sum_{j=1}^{N_t} W_{t,ij} f_{tj}+\\eta_{ti}$, where the reward is a weighted sum of sub-payoff functions $ f_{tj}=f(X_{tj},A_{tj})$, with weights $W_{t,ij}$ determined by the interference matrix $W_t$. Specifically, the $i$th row of $W_t$ captures the influence of all other units on unit $i$, where each element $W_{t,ij}$ represents the strength of unit $j$’s contribution to $i$’s reward. The term $f_{tj}$ reflects unit $j$’s individual contribution, and multiplying by $W_{t,ij}$ quantifies its effect on $i$. Summing over all units $j\\in\\\\{1,\\dots,N_t\\\\}$ yields the final reward $R_{ti}$. This formulation is intuitive, easily decomposable across individuals, and widely used in network and interference-related literature (Cliff & Ord, 1981; Getis, 2009; Su et al., 2019).\n\nThere are several alternatives to Eq (1). One approach is to generalize it as $R_{ti} = g(\\boldsymbol{W_t}, \\boldsymbol{X_t},\\boldsymbol{A_t}; \\theta) + \\eta_{ti}$, where $g$ is parameterized by $\\theta$, potentially using more flexible models such as neural networks. While this model is learnable given sufficient data, it would invalidate Eq. (2), which, through the decomposition in Eq. (1), effectively consolidates all interference-related information of unit $i$ into the interference weight $\\omega_{ti}$ and simplifies decision making. \n\nOther directions, instead of using a matrix $W_t$ to quantify pairwise interference levels, include assuming alternative interference-related structures such as partial interference or exposure mapping (see the first paragraph of Section 2). However, the fundamental challenge of the interference problem is that, without any structural assumption, $R_{ti}$ could be arbitrarily influenced by all units' contextual information and actions $(\\boldsymbol{X}_t, \\boldsymbol{A}_t)$, making the problem too general to be learnable. Some assumptions (whether in the form of Eq. (1) or other models) are necessary to impose structure on the interference, depending on what best aligns with real-world data. Given the structured formulation of $\\boldsymbol{W}_t$ and its interpretability within a linear framework, we find Eq. (1) to be a natural and intuitive starting point.\n\n**Q2**\n\nThanks for pointing that out! This is actually a typo that occurred while generalizing our setting from the $2$-arm case to the $K$-arm case. The sampling should indeed be uniform over $[K]$, as you correctly mentioned. We will revise this in the final version of our paper. \n\n**Q3**\n\nThanks again for your careful reading and good catch. In EG, $\\kappa_{ti} (\\omega_{ti},X_{ti})$ should be $\\epsilon_{ti}(K-1)/K$, instead of $\\epsilon_{ti}/2$ (which holds only when $K=2$). This is because the probability of exploration is $\\epsilon_{ti}$ in EG, and the fraction allocated to randomly exploring the optimal arm is $1/K$ of $\\epsilon_{ti}$. Thus, the correct expression should be\n$ \\kappa_{ti} (\\omega_{ti},X_{ti}) = (1 - 1/K)\\epsilon_{ti} = \\frac{\\epsilon_{ti} (K-1)}{K}$. We will correct this in the final version of our paper.\n\n**Q4**\n\nSection 3.1 expresses the payoff function as $f(X_{tj},a) = X_{tj} \\beta_a$, which assumes linearity with respect to the contextual information $X_{tj}$ for each action $a \\in \\mathcal{A}$. This linear formulation is widely adopted in the linear contextual bandits literature, such as  (Chu et al., 2011; Agrawal & Goyal, 2013). If I understand your suggestion correctly (i.e., representing $f$ as a simple inner product when each action is expressed as a vector), then Section 3.1 is already aligned with this idea. If we encode the action as a dummy variable vector, the function can be rewritten as an inner product, which is equivalent to your suggestion.\n\nThere are several ways to extend this linear payoff assumption. First, $X_{tj}$ can be transformed using basis functions (e.g., polynomial features) to incorporate higher-order representations as needed, which is a straightforward extension. Another direction is to integrate neural bandits into this framework by modeling $f(X_{tj}, A_{tj})$ using a neural network. While this approach allows direct adaptation of existing neural bandit algorithms to interference-aware settings, deriving theoretical guarantees (particularly asymptotic properties, as established in Section 4) becomes significantly more challenging. This is also why we begin with a linear payoff function.\n\n**Regarding your suggestions about notation and writing**: We sincerely appreciate your feedback on Section 3.1. We will refine this section by adding details, clarifying concepts like $\\widetilde{X}_t$, and updating the transpose notation to $\\beta^\\top$ for better clarity and readability.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The work is mostly theoretical but also contain some experiments which have reasonable design.", "theoretical_claims": "I checked the flow of some parts of proofs but I’m not certain all are correct.", "experimental_designs_or_analyses": "The design of conducted experiments are seems sound.", "relation_to_broader_scientific_literature": "The key contributions of the paper are in the areas of online decision-making (bandits) and causal inference.", "essential_references_not_discussed": "I am not aware of any missing prior works.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper addresses an important and novel problem at the intersection of causal inference and bandits.\n2. Rigorous theoretical analysis is provided, ensuring performance guarantees for the proposed algorithm.\n3. The problem is well-motivated with real-world examples, and the literature review is thorough. Additionally, the paper discusses potential directions for future work.\n\nWeaknesses:\n1. Some parts of the paper are difficult to follow due to notation and presentation of results, and these could be improved (see the suggestions section).", "other_comments_or_suggestions": "It would be better to use $\\top$ for the transpose operation of a matrix (e.g., $\\beta^{\\top}$\ninstead of  $\\beta’$).\n\n\nThe notation and formulas in Subsection 3.1 are not very clear. I believe this section could be rewritten for better clarity.", "questions_for_authors": "1. I did not fully understand why you modeled the inference using Equation 1. To what extent does this formulation restrict the problem? Could you discuss alternative formulations for the reward and the challenges they pose for algorithm design?\n2. In Lines 2 and 11 of Algorithm 1, why do you sample actions from Bernoulli(0.5)? Shouldn't it be sampled uniformly over $[k]$?\n3. In Theorem 4.2, how did you derive the third part?\n4. In subsection 3.1, is it possible to express $f(X_{tj}, a_{tj})$ in a different form? For example, by a simple inner product if each action represents a vector.", "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": "lvhybMr3FY", "reviewer": "Reviewer_2fJW", "summary": "This paper investigates the problem of interference in linear contextual bandits, where the actions taken for one unit influence the rewards of others. This paper leverages an adjacency matrix to model the interference structure and proposes three online algorithms LinEGWI, LinUCBWI, and LinTSWI. The authors establish several theoretical guarantees, including regret bounds, asymptotic properties of the OLS estimator, and statistical inference for the optimal policy value. The proposed methods demonstrate superior empirical performance over classical linear contextual bandit approaches in both synthetic experiments and a real-world MovieLens-based dataset.\n\n## update after rebuttal\nOverall, I appreciate the technical novelty of this paper, so I will maintain my current positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful questions and the time you spent reviewing our paper. We really appreciate your insights and are happy to discuss any further ideas or questions you may have.\n\n**Answer to W1**:\n\nRegarding the assumption that the interference matrix is known, we clarify this in three aspects:\n\n**First**, in many real-world applications, interference is either known or can be precomputed before applying bandit learning. For instance, in the context of COVID-19, geographic proximity naturally defines community connections, while in movie recommendation systems, social networks provide side information that quantifies pairwise interference. Such structural information is often available through expert knowledge or can be inferred from covariates before deploying a bandit algorithm.\n\n**Second**, the assumption of a known interference structure is widely used in both classical interference literature and its bandit extensions. In single stage, several works rely on this assumption  (Manski, 2013; Aronow & Samii, 2017;\nSu et al., 2019; Bargagli-Stoffi et al., 2020), and it has been adopted in bandit settings as well (Jia et al., 2024). While it is ideal to learn the interference structure purely from data, there is always a trade-off between what is pre-specified as an assumption and what is left for the model to infer. In other words, there is no \"free lunch\"--the choice of assumption depends on the specific problem setting and modeling priorities.\n\n**Lastly**, we give a practical direction to the case where the interference matrix is unknown in the second paragraph of Sec 7. Due to space constraints, we kindly refer the reviewer to our detailed discussion in response to **Reviewer f3ef, Q1**.\n\n**Answer to W2**:\n\nWe clarify that our work differs substantially from Shen 2024 in several key aspects:\n\n1.**Problem Motivation**: Our work addresses the fundamental challenge of **interference** in bandits, whereas Shen 2024 focuses on statistical inference for the optimal value in a standard bandit setting, which is an entirely different problem.\n\n2. **Scope of Application**: Shen 2024 considers inference in a two-arm bandit setting, limiting its applicability in real-world scenarios with multiple arms. In contrast, our work accommodates general **multi-arm** settings, making it significantly broader in scope.\n3. **Our Contributions**: Our work is the first to explore interference in contextual bandits. \n* From a statistical inference perspective, extending Shen 2024 to incorporate interference and multi-arm settings is **nontrivial**, particularly in establishing theoretical results due to the data dependency introduced by interference. Our work provides statistical guarantees in this broader context, but its contributions extend well beyond merely building on Shen 2024. Although we generalize their results, our study is fundamentally distinct, with a broader focus that does not rely heavily on their approach. \n\n* Moreover, if statistical properties (as discussed in Sec 4.3-4.4) are not relevant to a particular application, the clipping step (Line 10 of Alg. 1) can simply be omitted without affecting our main contributions, making our work entirely independent of Shen 2024. **The core novelty of our work lies in the problem formulation, the design of bandit algorithms, and regret analysis in this novel setting, all supported by extensive simulations and quasi-real data analysis. While we establish statistical inference results, they primarily reinforce our findings rather than serving as the sole core contribution.**\n\n**Answer to W3**:\n\nRegarding Assumption **A.2**, which may be of particular concern, we emphasize that:  \n* **The assumption is not restrictive** due to the small multiplication factor applied on the right-hand side, $p_t$. In Alg. 1, we specify that the clipping rate $p_t$ only needs to satisfy the condition of not decaying faster than $O(\\bar{N}_t^{-1/2})$. This means that any decreasing sequence, such as $p_t = O(\\bar{N}_t^{-3/7})$ or $O(\\bar{N}_t^{-2/5})$, or even a small fixed value (e.g., $p_t = 10^{-3}$) suffices. Given that $p_t$ is small and decreases over time, Assumption A.2 naturally holds as the sample size grows.  \n\n* **A.2 is actively enforced in our algorithm**. Specifically, Line 10 of Algorithm 1 ensures that if an arm is explored insufficiently (determined based on $p_t$ and a smallest eigenvalue comparison), the algorithm enforces additional exploration, preventing extreme imbalance and ensuring statistical consistency.\n\n* **Empirical validation**: In our simulation studies, we simply set $p_t \\equiv 0.01$ and observed that Line 10 is rarely triggered. This indicates that the assumption does not pose practical concerns.  \n\n**Answer to \"Questions For Authors\"**:\n\nDue to space constraints, we refer the reviewer to our response to **Reviewer f3ef, Q2**, which includes a detailed analysis and a comparison plot at https://anonymous.4open.science/r/LinCBWI_ICML_rebuttal-C829/.", "claims_and_evidence": "All claims are well-supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem.", "theoretical_claims": "I have not checked all the proofs in detail. I did not identify any obvious errors.", "experimental_designs_or_analyses": "The experimental designs or analyses are sound and valid.", "relation_to_broader_scientific_literature": "This work advances the field by proposing a framework for linear contextual bandits under interference. In contrast, prior studies only consider interference in multi-armed bandits or adversarial contextual bandit settings. The proposed algorithms (Algorithm 1) appear to be adapted from Shen et al., 2024.\n\nShen et al. Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning. 2024.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Strengths\n1. To my knowledge, the use of an adjacency matrix to quantify interference in linear contextual bandits is novel.\n2. This paper derives several theoretical guarantees, such as sublinear regret bounds that match the minimax optimal rate and asymptotic normality of the OLS estimator.\n3. The paper includes extensive simulations demonstrating the advantages of the proposed algorithms. The paper also shows that without interference, the proposed algorithms reduce to classical algorithms with comparable performance.\n\nWeaknesses\n1. This paper assumes that the interference matrix is known, which may be impractical in real-world settings.\n2. The algorithm design seems to be heavily influenced by Shen et al. 2024 (Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning).\n3. The theoretical results rely on several assumptions that are non-standard in the bandit literature, especially the clipping assumption (Assumption A.2), which appears to be quite strong.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "1. How does the computational overhead of the proposed algorithms compare to that of classical linear bandit algorithms?", "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": "Cy6frLNO6O", "reviewer": "Reviewer_SPrL", "summary": "This paper is the first to study contextual bandits with interference. The authors propose a linear contextual bandit framework and introduce an algorithm called LinCB to address the regret minimization/estimation problem under this framework. Experimental results based on MovienLens dataset further demonstrates the effectiveness of the proposed results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful questions and the time you spent reviewing our paper. We really appreciate your insights and are happy to discuss any further ideas or questions you may have.\n\n**Answer to W1**:\n\nThank you for your insightful perspective on the literature of Dubey et al. (2020). We would like to clarify a minor error in the related work section: Dubey et al. (2020) did not model interference. By definition, interference occurs when an agent’s action influences the rewards of others. However, in their framework, the reward of agent $v$ is defined as $f_v = F(a_v, z_v)$, which depends solely on the agent’s own action $a_v$ and contextual information $z_v$, with no influence from other agents’ actions. We appreciate your attention to this detail and will remove this paper from the interference-related literature in the main paper. Consequently, we reaffirm that our work is the first to address interference in contextual bandits.\n\n**Answer to W2**:\n\nMulti-agent bandits and bandits with interference are related but focus on different aspects of the problem, with some overlap but distinct emphases:\n* **Multi-agent bandits** primarily deal with the interaction between multiple agents (typically fixed in number) and how they share information to enhance bandit learning. The central focus is on fostering collaboration or competition among agents.\n* **Bandits with interference** stem from the concept of \"interference\" in causal inference. The key consideration is whether one agent's action impacts the reward of others.\n\nNot all multi-agent bandit works address interference. In Sec 2, under *Cooperative Multi-Agent Bandits*, we classify prior literature:\nParagraph 1 lists works that do not address interference, and Paragraph 2 includes studies that do, even if not explicitly framed as interference problems. For example, Bargiacchi et al. 2018 and Verstraeten et al. 2020 implicitly handle interference, similar to Jia et al. (2024) and Agarwal et al. (2024).\n\nIn summary, the defining criterion for bandits with interference is straightforward: *Does one agent's action affect another’s reward?* If yes, interference exists and must be accounted for.\n\n**Answer to W3**:\n\n* First, we would like to clarify that our work, along with (Jia et al., 2024; Agarwal et al., 2024; Leung, 2022), all assume different known structures on interference, albeit in different ways. Without any assumptions on the nature of the interference pattern, both estimation and bandit learning would be infeasible due to the high-dimensional action space, $K^{N}$. Specifically, (Jia et al., 2024) and (Leung, 2022) assume that the strength of interference decays according to a specific notion ($\\psi$) of distance between units, while (Agarwal et al., 2024) imposes a sparsity assumption on network interference, restricting interference to only a small neighborhood of size $s$. In contrast, we introduce an assumption in a more intuitive manner by modeling pairwise interference through a matrix $W$, which simplifies both modeling and interpretation. While this assumption may appear strong, it provides flexibility, as the entries of $W$ can take any value within $[-1,1]$. From this perspective, our formulation is more general.\n* Additionally, we would like to emphasize that (Jia et al., 2024) and (Leung, 2022) do not ”indirectly learn” the interference\nstrength. For instance, in (Jia et al., 2024), all regret bounds are derived under the assumption of a known $\\psi$, which prescribes\na specific functional form for interference decay.\n* In Sec 2, the second paragraph highlights works that quantify interference in a similar setting to ours, such as\n(Getis, 2009; Valcu & Kempenaers, 2010; Su et al., 2019). This structure is widely used in network and interference-related literature.\n* Lastly, due to space constraints, regarding the case where $W_t$ is unknown: aside from the second paragraph of Sec 7, we kindly refer the reviewer to our detailed discussion in response to **Reviewer f3ef, Q1**. We hope that this plausible extension, along with the tolerance of LinCBWI w.r.t. the misspecification of $W_t$ in the added simulation, will help alleviate your concern.\n\n**Answer to W4**:\n\nThanks for your suggestion regarding assumptions placement. We will move them to the main paper and we believe this would improve the readability. \n\n**Answer to W5**:\n\nThe regret bound actually depends on $T$ only implicitly through $\\bar{N}_T$. In the special case where each round involves a fixed number of units, $N_t\\equiv n$, then $\\bar{N}_T=nT$, leading to a regret bound of approximately $O(n^{1/2}T^{1/2})$, up to logarithmic terms.\n\n**Others**:\n\nWe noticed that the reviewer referenced Shiliang Zuo's *Federated Multi-Armed Bandits*, but we were only able to find a paper with the same title by a different author. Could you kindly provide more details or clarify the reference? We would be happy to include and carefully discuss this work in the final version of our paper.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "Some references might need to be discussed. For example, in Shiliang Zuo's Federated Multi-Armed Bandits, they consider a setting where the number of agents varies over time, which is similar to the setting considered by the authors.", "other_strengths_and_weaknesses": "Strengths:  \n1. This paper proposed the first study on contextual bandit with interference.  \n2. The proofs I have checked do not have any obvious flaws.\n3.  The authors consider both the regret minimization and estimation problems.  \n4. The experimental results are based on a real world dataset.\n\nWeaknesses:\n1. I believe there are issues with the discussion of references in this paper. In line 86, the cited work Dubey et al., 2020 does not belong to the MAMAB problem; rather, it falls under a multi-agent (kernelized) contextual bandits problem. If, as the authors claim, Dubey 2020 studies interference-related problems, then that paper might be the first to investigate contextual bandits with interference. This contradicts the authors' assertion that their work is the first interference-related paper, which leaves me somewhat confused. How does the learning framework in that paper differ from the one in this work?  \n2. The authors have not clearly discussed the distinction between multi-agent bandits and bandits with interference. IMHO, most federated/distributed/MA bandit studies focus on leveraging the communication topology to design communication algorithms that accelerate the learning process. In contrast, interference bandits (e.g., [Jia et al., 2024; Agarwal et al., 2024]) focus more on learning the strength of interference between different nodes. The authors could add a discussion on this aspect.\n3. The authors assume that the interference strength matrix $W_t$ is known. Based on my understanding of the previous interference paper, such as Jia et al 2024., Agarwal et al 2024., and Leung et al 2024., they do not assume that the interference strength between agents is known; instead, their task is more focused on indirectly learning this interference strength. Could you discuss references that consider a similar setting? I also look forward to the authors adding more discussion on the scenario where $W_t$ is unknown.\n4. Theorem 4.2 refers to Assumptions A.1 - A.3, which the authors have placed in the appendix. I suggest that the authors include these assumptions (and the related discussion) in the main text.  \n5. A typical regret upper bound often includes the time horizon $T$, whereas this paper only provides an upper bound in terms of $\\bar{N}_t$. The authors could add a remark discussing the relationship between the given upper bound and a more conventional upper bound that explicitly includes $T$.", "other_comments_or_suggestions": "I find this to be an interesting paper and am inclined to accept it. I look forward to the authors' responses to my questions.\n\n## update after rebuttal: The authors have addressed my concerns, so I recommend acceptance.", "questions_for_authors": "See the S/W section", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: After a very effective author-PC discussion phase, the authors cleared a few concerns about the paper. All the 4 reviewers ultimately are positive about the contributions of this paper, which extends classic linear bandits to situations with inner action interference. Hope the authors could take into account various useful comments from the review process to improve the paper in its next version, but overall this paper is a great addition to ICML!
Decision: Accept (poster)