# Leveraging heterogeneous spillover effects
in maximizing contextual bandit rewards

Ahmed Sayeed Faruk, Elena Zheleva

###### Abstract

Recommender systems relying on contextual multi-armed bandits continuously
improve relevant item recommendations by taking into account the contextual
information. The objective of these bandit algorithms is to learn the best arm
(i.e., best item to recommend) for each user and thus maximize the cumulative
rewards from user engagement with the recommendations. However, current
approaches ignore potential spillover between interacting users, where the
action of one user can impact the actions and rewards of other users.
Moreover, spillover may vary for different people based on their preferences
and the closeness of ties to other users. This leads to heterogeneity in the
spillover effects, i.e., the extent to which the action of one user can impact
the action of another. Here, we propose a framework that allows contextual
multi-armed bandits to account for such heterogeneous spillovers when choosing
the best arm for each user. By experimenting on several real-world datasets
using prominent linear and non-linear contextual bandit algorithms, we observe
that our proposed method leads to significantly higher rewards than existing
solutions that ignore spillover.

## Introduction

Contextual bandit algorithms leverage user attributes and actions to improve
recommendation. Different users may respond differently to the recommendation
(or treatment) received which leads to heterogeneity in responses (e.g.,
clicks or purchases). Contextual bandit algorithms deal with this
heterogeneity by providing meaningful recommendations at an individual level
and thus maximizing rewards (Li et al. 2010; Chu et al. 2011; Agrawal and
Goyal 2013; Zhang et al. 2020). Rewards can vary based on the application
where the recommendations occur. Some reward examples include revenue from
recommended products in e-commerce applications and clicks on recommended
user-generated content in online social networks.

When contextual bandit recommendations occur in social networks, they can
spread from one user to another and overall rewards can be based on both
direct recommendations and spillover. Network spillover refers to the
phenomenon where the actions of one individual have an impact on the actions
of others within the network. Spillover can happen in different ways, such as
through the transmission of behaviors or attitudes or through the spread of
information, ideas, or influence. For example, if an individual in a social
network starts to exercise regularly, they may influence their immediate
friends and followers to also start exercising, which can spread further
throughout the network, leading to a broader adoption of the behavior.
Understanding the effect of spillover is important in many fields, including
marketing, economics, public health, psychology, and social policy. The impact
of spillover can be either positive or negative and may occur intentionally or
unintentionally. For example, in an education setting, offering incentives on
course completion may spill over to untreated population in education through
knowledge transmission paths (Forastiere et al. 2021; Schiltz et al. 2019).
Similarly, exposure to advertisement in social networks can spill over through
sharing or discussing the ad to non-exposed users via virtual connection from
exposed users (Chae et al. 2017).

Different users may respond differently not only to the treatment received but
also to the spillover from their network contacts which leads to heterogeneity
in spillover. To illustrate the concepts in this paper, let’s consider the
following toy example: an advertisement company targets social network users
with two types of ads, ads on politics and ads on sports. User A is one of the
targeted users who posts about workouts and engages with fitness-related
content regularly. Therefore, when a sport-related ad about downloading a
fitness app comes to the news feed of A, A shares the ad link in their social
media account. Due to sharing, the ad link appears in the news feed of two
friends of A, namely B and C. B and C are not targeted users but B is also
interested in fitness and downloads the app from the shared link of A while C
is not interested in sports and does not download it. Due to the shared
interest, it is more likely for A to influence B to download the fitness app
than to influence C, which reflects spillover heterogeneity. Rewards (i.e.,
downloads) occur both based on treatment (A’s download) and based on spillover
(B’s download).

Current research on contextual bandit recommendations (Li et al. 2010; Chu et
al. 2011; Agrawal and Goyal 2013; Zhang et al. 2020; Zhou, Li, and Gu 2020)
does not take into account the possibility of leveraging spillover to optimize
rewards. Moreover, to the best of our knowledge, there are no studies dealing
with the heterogeneity of spillover to maximize rewards during recommendation
with contextual bandits. Thus, in this paper we set out to examine whether
heterogeneous spillover effects can be utilized to maximize the overall
rewards during contextual bandit recommendation in social networks.

Present work. In this paper, we present a contextual bandit algorithm, $NetCB$
that leverages heterogeneous spillover and neighborhood knowledge for
maximizing rewards in networks. The algorithm incorporates neighborhood
knowledge to improve bandit performance and sometimes goes against the bandit
recommendation by providing sub-optimal recommendations to some potential
users which can increase spillover and thus long-term rewards in networks. Our
algorithm is flexible enough to use any state-of-the art contextual multi-
armed bandit (MAB) as a subroutine.

Key idea and highlights. To summarize, this paper makes the following
contributions:

  * •

We define a novel problem setup for contextual bandit recommendation to
maximize network rewards by introducing a dynamic heterogeneous spillover
model.

  * •

We formulate a methodology which recommends when to go against the contextual
bandit recommendation and leverage spillover to increase long-term network
rewards.

  * •

Our experiments on real-world and semi-synthetic attributed network datasets
show the effectiveness of our method when compared to state-of-the-art
contextual bandit algorithms.

## Related Work

Recommendations with contextual bandits. Reinforcement learning methods, MABs
(Li et al. 2010; Chu et al. 2011; Lu, Pál, and Pál 2010) and Markov Decision
Processes (MDPs) (Shani et al. 2005), are widely used to recommend items to
users. LinUCB (Li et al. 2010; Chu et al. 2011) and Contextual Thompson
Sampling (CTS) (Agrawal and Goyal 2013) algorithms assume a linear
relationship between the expected reward of an action and its context. The
NeuralBandit1 (Allesiardo, Féraud, and Bouneffouf 2014), NeuralUCB (Zhou, Li,
and Gu 2020), NeuralTS (Zhang et al. 2020), NPR method (Jia et al. 2021) use
neural networks to remove the constraint of linearity. However, they do not
consider neighborhood information and the potential of spillover effects in
maximizing rewards during recommendation.
Contextual bandit for networks. The only works that consider contextual bandit
for networks is in the context of influence maximization (Vaswani et al. 2017;
Wen et al. 2017; Iacob, Cautis, and Maniu 2022; Wilder et al. 2018). The
influence maximization problem aims at maximizing rewards in a social network
with diffusion probabilities by finding the users for the initial treatment.
Contextual bandit can provide an adaptive approach for selecting the most
influential users to maximize influence on social networks. However, influence
maximization is different from our work since we focus on the recommendation
decisions not on the choice of nodes.

Spillover. Spillover happens in many modern A/B test settings such as social
networks and online marketplaces (Hagiu and Wright 2015; Yan, Zhao, and Liu
2018; Holtz et al. 2020; Li et al. 2022). Aronow & Samii (Aronow and Samii
2017) propose exposure mapping for addressing spillover. Yuan & Altenburger
(Yuan and Altenburger 2022) propose a machine learning approach to
automatically characterize network spillover conditions based on both the
local network structures and the treatment assignments among users in the
network neighborhood. Bargagli-Stoffi et al. (Bargagli-Stoffi, Tortu, and
Forastiere 2020) and Yuan et al. (Yuan and Altenburger 2022) propose tree-
based methods for the estimation of heterogeneous effects in randomized
experiments. All these works focus on spillover to avoid biased estimates of
the treatment effect whereas our work focuses on leveraging the heterogeneity
of network spillover to maximize rewards.

Figure 1: Treatment-dependent heterogeneity in network spillover.

## Problem Description

Data model. We define an attributed network graph $G=(V,E)$, consisting of a
set of $n$ nodes $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, a set of edges
$E=\\{e_{ij},1\leq i,j\leq n\\}$ where $e_{ij}$ denotes that there is an edge
from node $v_{i}\in V$ to node $v_{j}\in V$. The set of adjacent nodes of
$v_{i}$ is denoted with $\mathcal{N}_{i}$ where
$\mathcal{N}_{i}=\\{v_{j}\mathrel{\mathop{\mathchar 58\relax}}v_{j}\in
V,e_{ij}\in E\\}$. We define $\mathcal{N}_{i}$ as the neighborhood of node
$v_{i}$ and each node $v_{j}\in\mathcal{N}_{i}$ is a neighbor of node $v_{i}$.
Each node in the network belongs to one latent preference from a set of $l$
possible latent preferences (or classes), $C=\\{c_{1},c_{2},\ldots,c_{l}\\}$.

We let $X_{i}$ denote the pre-treatment $d$-dimensional feature vector of node
$v_{i}$ and $x_{i}\in C$ refers to its latent preference type. We consider
$2l$-dimensional dynamic neighbourhood feature for each node of the network.
We denote the neighborhood feature vector of node $v_{i}$ with
$X_{\mathcal{N}_{i}}$. The $y_{i}\in\\{0,1\\}$ refers to the activation status
of node $v_{i}$ where $y_{i}=1$ refers to active node $v_{i}$ and $y_{i}=0$
refers to inactive node $v_{i}$.

The contextual bandit contains a set of arms
$\mathcal{A}=\\{c_{1},c_{2},\ldots,c_{l}\\}$. We let denote the predicted (or
recommended) latent preference type of node $v_{i}$ by the contextual bandit
with $arm_{i}\in\mathcal{A}$ and the assigned treatment class of node $v_{i}$
with $t_{i}\in\\{c_{1},c_{2},\ldots,c_{l}\\}$.
Node activation. The nodes in the network can be activated in two ways,
through direct treatment and through spillover. _Direct treatment_ refers to
treating a particular node in the network. The corresponding outcome without
considering the spillover effects from its adjacent nodes is defined as the
_direct treatment effect_. The average direct treatment effect, $DTE$ can be
estimated as below:

$DTE(V)\leftarrow\mathop{\mathbb{E}}_{v_{i}\in V}[y_{i}|t_{i}\neq\emptyset-
y_{i}|t_{i}=\emptyset]$

The spillover occurs when the outcome of one node impacts the outcome of
another node. Spillover effect refers to the outcome of a particular node in
the network due to the impact of its active adjacent nodes. Let
$\mathcal{N}_{i}.\pi$ denote the vector of activation status of node $v_{i}$’s
neighborhood $\mathcal{N}_{i}$. The average spillover effect, $SE(V)$ can be
estimated as below:

$SE(V)\leftarrow\mathop{\mathbb{E}}_{v_{i}\in
V}[y_{i}|t_{i}=t,\mathcal{N}_{i}.\pi]-\mathop{\mathbb{E}}_{v_{i}\in
V}[y_{i}|t_{i}=t,\mathcal{N}_{i}.\pi=\emptyset]$

If a treated node becomes active, it can activate other inactive adjacent
nodes in its neighborhood via spillover. Similarly, if a treated node remains
inactive after the direct treatment, future adjacent active nodes in its
neighborhood can activate the inactive treated node via spillover effect. We
call this spillover reverse spillover whereas the former one is forward
spillover.
Direct treatment effect. The effect of the direct treatment can vary across
different groups based on individual characteristics or other factors.
Therefore, we design two types of direct treatment based on the assigned
treatment class and latent preference of the nodes. We define the direct
treatment of node $v_{i}$ as _aligned_ when its assigned treatment class,
$t_{i}$ is the same as its latent preference, $x_{i}$. Similarly, we define
the direct treatment of node $v_{i}$ as _misaligned_ when its assigned
treatment class, $t_{i}$ is different from its latent preference, $x_{i}$. We
denote the probability of activating a particular node due to the aligned and
misaligned direct treatment with $p_{a}$ and $p_{m}$, respectively, which can
be formulated as follows:

$p_{a}\leftarrow P(y_{i}=1|t_{i}=x_{i})$ (1) $p_{m}\leftarrow
P(y_{i}=1|t_{i}\neq x_{i})$ (2)

Spillover effect. To model spillover over the network, we use the independent
cascade model (ICM) (Shakarian et al. 2015) where each of the inactive node’s
active neighbors has a probabilistic and independent chance to activate the
node via spillover. This resembles the COVID-19 spread, where each social
interaction may trigger an infection.

We define an active node as a _source node_ if it impacts the outcome of its
adjacent nodes. Nodes that get affected by the source node are considered
_recipient nodes_. For example, if node $v_{j}$ gets activated due to the
spillover from active node $v_{i}$, then $v_{i}$ is the source node and
$v_{j}$ is the recipient node. The spillover can be heterogeneous which is
assumed to be dependent on the the latent preference type of nodes and
assigned treatment class of the source node. A spillover is considered
_aligned_ when the treatment assignment class of an activated source node is
the same as that of the latent preference type of the recipient node.
Similarly, a spillover is considered _misaligned_ when the treatment
assignment class of a source node is different from the latent preference type
of the recipient node.

We denote spillover probability with $p_{sr}$ where $s\in\\{a,m\\}$ refers to
whether the treatment of the source node is aligned or misaligned and
$r\in\\{a,m\\}$ refers to whether the spillover is aligned or misaligned. We
formulate four types of heterogeneous spillover probabilities where $v_{i}$ is
the source node and $v_{j}$ is the recipient node:

$p_{aa}\leftarrow P(y_{j}=1|t_{i}=x_{i},t_{i}=x_{j})$ (3) $p_{am}\leftarrow
P(y_{j}=1|t_{i}=x_{i},t_{i}\neq x_{j})$ (4) $p_{ma}\leftarrow
P(y_{j}=1|t_{i}\neq x_{i},t_{i}=x_{j})$ (5) $p_{mm}\leftarrow
P(y_{j}=1|t_{i}\neq x_{i},t_{i}\neq x_{j})$ (6)

The first two spillover probabilities $p_{aa}$ and $p_{ma}$ refer to aligned
spillover probabilities from a source node that is activated due to aligned
and misaligned treatment, respectively. Similarly, $p_{am}$ and $p_{mm}$ refer
to misaligned spillover probabilities from a source node that is activated due
to aligned and misaligned treatment, respectively.

An example of $p_{a}$, $p_{m}$, $p_{aa}$, $p_{am}$, $p_{ma}$, and $p_{mm}$ is
shown in Figure $1$ where a toy network contains six nodes
$V\in\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$ and two possible preferences
$C\in\\{P,S\\}$ (e.g., Politics and Sports). Here, $x_{1}=P$, $x_{2}=S$,
$x_{3}=P$, $x_{4}=S$, $x_{5}=P$, $x_{6}=P$. A detailed description of Figure
$1$ is included in Appendix A1.
A contextual bandit setup. We consider stochastic $l$-armed contextual bandit
setup with a total number of $T$ rounds. At round $i\in[T]$, an inactive node
$v_{i}$ arrives and the agent observes the context consisting of $l$ feature
vectors: $\\{X_{i,arm},X_{\mathcal{N}_{i},arm}|arm\in\mathcal{A}\\}$. The
feature vector, $X_{i}$ along with the dynamic neighborhood feature vector,
$X_{\mathcal{N}_{i}}$ represents information of the node $v_{i}$ and will be
referred to as the context. The agent selects an action $arm_{i}$ and receives
a payoff, $PO(v_{i},arm_{i})$. The action of an arm refers to assigning a
treatment class to a node for direct treatment. The payoff is calculated by
counting the total number of newly activated nodes due to the recommended
arm’s action, i.e., assigning a treatment class $t_{i}$ on the arrival node
$v_{i}$ and corresponding spillover effect to its adjacent nodes. The total
$T$-trial payoff of the bandit is defined as
$\sum_{i=1}^{T}PO(v_{i},arm_{i})$. Similarly, we define the optimal expected
$T$-trial payoff as $\mathbf{E}[\sum_{i=1}^{T}PO(v_{i},arm_{i}^{*})]$, where
$arm_{i}^{*}$ is the arm with maximum expected payoff at trial $i$. Therefore,
the T-trial cumulative regret of the bandit learning can be formulated as
$Regret\leftarrow\sum_{i=1}^{T}(PO(v_{i},arm_{i}^{*})-PO(v_{i},arm_{i}))$.

The goal of the contextual bandit is to learn an arm-selection strategy so
that expected regret is minimized. The following assumption is made about
payoff generation for any round $i$,

$PO(v_{i},arm_{i})=F(X_{i,arm_{i}},X_{\mathcal{N}_{i},arm_{i}})+\xi_{i}$

$F$ can be a linear or non-linear function which needs to learn and $\xi_{i}$
is the noise. The bandit learns the parameter for each arm with the arrival of
nodes.

### Types of rewards in networks

A reward refers to the activation of an inactive node due to direct treatment
or spillover. When a node is activated, a reward of $1$ is incurred;
otherwise, the reward is $0$.
Total rewards. The total rewards in the network, $R_{total}$ refers to the
total number of activated nodes due to direct treatment effects and spillover
effects, i.e.,
$R_{total}\leftarrow\sum_{v_{i}\in V}y_{i}$
Spillover rewards. The spillover rewards in the network, $R_{se}$ refers to
the total number of activated nodes due to spillover, i.e.,
$R_{se}\leftarrow\sum_{v_{i}\in V,arm_{i}=\emptyset}y_{i}$
Direct treatment rewards. The direct treatment rewards in the network,
$R_{dte}$ refers to the total number of activated nodes due to the direct
treatment effects, i.e.,
$R_{dte}\leftarrow R_{total}-R_{se}$
Bandit accuracy. The bandit accuracy, $B_{acc}$ refers to the ratio of total
number aligned direct treatment recommendations to the total number of direct
treatment recommendations during a contextual bandit learning, i.e.,
$B_{acc}=\frac{\sum_{v_{i}\in V}(\mathds{1}[arm_{i}=x_{i}])}{\sum_{v_{i}\in
V}(\mathds{1}[arm_{i}\neq\emptyset])}$

Now, we are ready to define the problem we address in this paper. The goal of
this paper is to develop an algorithm which can maximize the total rewards or
minimize total regrets during bandit online learning.

Problem: Maximizing network rewards with contextual bandits: Given an
attributed network graph $G=(V,E)$, a set of attributes $X$ associated with
each node, and a set of arms $\mathcal{A}$ associated with the treatment
classes, design an algorithm to recommend a treatment class to the inactive
node $v_{i}$ for direct treatment at round $i\in[T]$ such that:

  1. 1.

Total number of aligned treatment, $\sum_{v_{i}\in
V}\mathds{1}[arm_{i}=x_{i}]$ is maximized, therefore bandit accuracy,
$B_{acc}$ and direct treatment rewards, $R_{dte}$ are maximized.

  2. 2.

Total spillover probability in the network, $\sum_{p,q\in\\{a,m\\}}{p_{sr}}$
is maximized, therefore spillover rewards, $R_{se}$, are maximized.

## Algorithm for maximizing rewards with contextual bandits

We design an algorithm that recommends the best treatment for a node and its
neighborhood by considering its neighborhood knowledge and heterogeneous
spillover effects to maximize rewards in the whole network. It incorporates
existing contextual MAB as a subroutine and the contextual bandit setup we
described while recommending a direct treatment assignment to a node. We
account for dynamic neighborhood knowledge to accelerate learning rate and
leverage heterogeneous spillover to maximize spillover effects. We call this
algorithm $NetCB$ which is described as below followed by its two main
components:

Algorithm 1 Maximizing network rewards with contextual bandit ($NetCB$)

1:Inputs: $\alpha\in\mathbb{R}_{+}$

2:for all $a\in\mathcal{A}$ do

3: Initialize arm parameters

4:end for

5:for nodes arriving at time $i=1,2,3,\ldots,T$ do

6: Observe features $X_{i}\in\mathbb{R}^{d}$,
$X_{\mathcal{N}_{i}}\in\mathbb{R}^{2l}$, and bandit parameters for all arms
$a\in{\mathcal{A}}$

7: Recommend ${arm}_{i}$ for node $v_{i}$ with maximum expected payoff

8: Estimate expected rewards of node $v_{i}$ for $arm_{i}$,
$E[R_{i}\,|\,arm_{i}]$

9: for all $arm_{k}\in\mathcal{A}$ where $arm_{k}\neq{arm}_{i}$ do

10: Estimate expected rewards, $E[R_{i}\,|\,arm_{k}]$

11: end for

12: Find $\overline{arm_{i}}=\underset{arm_{k}}{\arg\max}E[R_{i}\,|\,arm_{k}]$

13: if $E[R_{i}\,|\,{arm}_{i}]\geq E[R_{i}\,|\overline{\,{arm}_{i}}]$ then

14: $t_{i}\leftarrow arm_{i}$

15: Observe payoff, $PO(v_{i},arm_{i})$

16: Update the bandit parameters for $\mathcal{A}$ and $X_{\mathcal{N}_{i}}$

17: else

18: $t_{i}\leftarrow\overline{arm_{i}}$

19: Observe payoff, $PO(v_{i},\overline{arm_{i}})$

20: Update $X_{\mathcal{N}_{i}}$

21: end if

22:end for

###  $B_{acc}$ maximization to accelerate learning rate

The bandit accuracy, $B_{acc}$ maximization is achieved by aggregating static
node features, $X_{i}$ and dynamic neighborhood features,
$X_{\mathcal{N}_{i}}$ for node $v_{i}$. The first $l$ dimensions of
$X_{\mathcal{N}_{i}}$ refer to the percentages of adjacent nodes of node
$v_{i}$ getting direct treatment assignment with each element of $C$ which is
formulated as follows for $k\in[1,l]$:

$X_{\mathcal{N}_{i}}[k]=\frac{\sum_{v_{j}\in\boldsymbol{\mathcal{N}_{i}}}\mathds{1}[t_{j}=c_{k}\land{arm}_{j}\neq\emptyset]}{\sum_{v_{j}\in\boldsymbol{\mathcal{N}_{i}}}\mathds{1}[t_{j}\neq\emptyset]}$

The remaining second $l$ dimensions refer to the percentages of inactive
adjacent nodes of node $v_{i}$ after getting direct treatment assignment with
each element of $C$ which is formulated as follows for $k\in[1,l]$:

$X_{\mathcal{N}_{i}}[l+k]=\frac{\sum_{v_{j}\in\boldsymbol{\mathcal{N}_{i}}}\mathds{1}[y_{j}=0\land
t_{j}=c_{k}\land{arm}_{j}\neq\emptyset]}{\sum_{v_{j}\in\boldsymbol{\mathcal{N}_{i}}}\mathds{1}[t_{j}=c_{k}]}$

The neighborhood feature of a node may change over time with the arrival of
new nodes and thus $X_{\mathcal{N}_{i}}$ is dynamic in all of our experiments
where
$\sum_{k=1}^{l}X_{\mathcal{N}_{i}}[k]=\sum_{k=l+1}^{2l}X_{\mathcal{N}_{i}}[k]=1.0$
unless
$\sum_{v_{j}\in\boldsymbol{\mathcal{N}_{i}}}\mathds{1}[t_{j}\neq\emptyset]=0$.

### Spillover maximization

Getting the treatment recommendation for a node, $NetCB$ algorithm estimates
the expected rewards by observing the recommended treatments of the directly
treated but inactive adjacent nodes. To estimate spillover, the recommended
treatment class by the bandit is assumed to be the true latent preference of
the node and its directly treated adjacent nodes. The expected rewards due to
the direct treatment effect of the recommended arm, $arm_{i}$ for the node
$v_{i}$ and spillover effects in its adjacent nodes is denoted with
$E[R_{i}\,|\,arm_{i}]$ which is estimated as follows:

$E[R_{i}\,|\,arm_{i}]=p_{a}+p_{a}*\sum_{v_{j}\in\boldsymbol{\mathcal{N}_{i}}}(p_{aa}*\mathds{1}[arm_{i}=arm_{j}\land\\\
y_{j}=0]+p_{am}*\mathds{1}[arm_{i}\neq arm_{j}\land y_{j}=0])$ (7)

The expected rewards due to the direct treatment effect of each alternate arm,
$arm_{k}\in\mathcal{A}\,(arm_{k}\neq arm_{i})$ for the node $v_{i}$ and
spillover effects in its adjacent nodes is denoted with $E[R_{i}\,|\,arm_{k}]$
which is estimated as follows:

$E[R_{i}\,|\,arm_{k}]=p_{m}+p_{m}*\sum_{v_{j}\in\boldsymbol{\mathcal{N}_{i}}}(p_{ma}*\mathds{1}[arm_{k}=arm_{j}\\\
\land y_{j}=0]+p_{mm}*\mathds{1}[arm_{k}\neq arm_{j}\land y_{j}=0])$ (8)

We denote the alternate arm with highest expected reward for node $v_{i}$ with
$\overline{arm_{i}}$, i.e.,
$\overline{arm_{i}}=\underset{arm_{k}}{\arg\max}E[R_{i}\,|\,arm_{k}]$.

The $NetCB$ does not assign treatment class to node $v_{i}$ with the bandit
recommendation, $arm_{i}$ when the expected rewards of the
$\overline{arm_{i}}$ is higher than that of the $arm_{i}$. Instead the
algorithm treats the node $v_{i}$ with $t_{i}=\overline{arm_{i}}$ but does not
update the arm parameters for the corresponding observed payoffs so that the
bandit does not get confused. We defer the illustration of Algorithm $1$ in
Appendix A2.

The activation status of the node $v_{i}$ along with its adjacent nodes may
change due to the direct treatment effect for assigning a treatment class and
corresponding spillover effect from $v_{i}$. The contextual bandit learns the
parameters of the arms, $\mathcal{A}$ with the arrival of nodes and
generalizes expected payoff from one node to another, and thus learns to
recommend the best direct treatment more quickly for new nodes.

## Experiments

In this section, we study the effectiveness of our proposed method using both
real-world and semi-synthetic datasets in terms of $R_{total}$, $R_{dte}$,
$R_{se}$, $B_{acc}$, and $Regret$ with several baseline contextual bandit
methods.

### Data representation

Real-world datasets. We consider four real-world attributed network datasets.
BlogCatalog111All datasets available at
https://www4.comp.polyu.edu.hk/$\sim$jiemshi/datasets.html is a network of
social interaction among the bloggers listed on the BlogCatalog website. This
dataset contains $5,196$ nodes, $343,486$ edges, $8,189$ attributes, and $6$
labels. The labels represent topic categories inferred through the metadata of
the blogger interests. Flickrnote1 is a benchmark social network dataset which
contains $7,575$ nodes, $479,476$ edges, $12,047$ attributes, and $9$ labels.
Each node in this network represents a user, each edge represents a following
relationship, and the labels represent the interest of groups of the users.
Hateful dataset is sampled from the Hateful Users on Twitter dataset (Ribeiro
et al. 2018) and the sample contains $3,218$ nodes, $9,620$ edges, $1,036$
attributes, and $2$ labels. Each sample is classified as either ”hateful” or
”normal.” Pubmednote1 is a citation network dataset where each node represents
a scientific publication about diabetes and each directed edge represents a
citation. This dataset contains $19,717$ nodes, $44,338$ edges, $500$
attributes, and $3$ labels. Each publication is classified into one of the $3$
labels.
Semi-synthetic dataset. We generate semi-synthetic datasets by deviating
homophily in the networks where homophily refers to the proportion of edges
that connect two nodes from the same latent preference. The homophilic scores
in Blogcatalog, Flickr, Hateful, Pubmed networks are $0.4$, $0.23$, $0.73$,
and $0.8$, respectively. We deviate these scores to $0.88$, $0.88$, $0.58$,
and $0.30$, respectively. We defer this illustration to Appendix A3.

#### Static features and latent preference of node

The pre-treatment node feature vector, $X_{i}$, is $d$-dimensional. $X_{i}$ is
static in all experiments. To reduce computational complexity of the bandit
algorithm, we reduce the dimension of $X_{i}$ from $d$ to $500$ with truncated
SVD (Halko, Martinsson, and Tropp 2009) for all datasets except Pubmed. Thus,
$d=300$ for the Pubmed dataset but $d=500$ for all other datasets. The latent
preference of a node in the network is based on its label and $l$ refers to
the number of labels in the dataset. To incorporate dynamic neighborhood
knowledge during bandit recommendation, we aggregate $d$-dimensional static
node feature with $2l$ dimensional dynamic neighborhood feature and consider
it as a $d+2l$ dimensional feature vector for each node in the network.

### Main algorithms and baselines

LinUCB. This is the main baseline that considers the node features during
recommendation (Li et al. 2010). The method ignores neighborhood knowledge and
does not leverage heterogeneous spillover during treatment recommendation. The
payoff of the directly treated node is calculated based on whether it is
activated or not due to the treatment. The method assumes a linear dependency
between the expected payoff of an action and context.
NeuralUCB. This method also considers the node features during treatment
recommendation but incorporates a neural network into the upper confidence
bound (UCB) algorithm to capture more complex patterns in the data (Zhou, Li,
and Gu 2020). The payoff is calculated based on whether directly treated node
is activated or not. This method can capture non-linear relationships and more
complex dependencies among action, features, and rewards.
NeuralTS. This method considers the feature of the node during treatment
recommendation but leverages the Thompson Sampling (TS) strategy (Zhang et al.
2020). The payoff is calculated based on whether directly treated node is
activated or not. The method also uses neural network to model the reward
probabilities of actions which can handle unknown or changing reward
distributions.
LinUCB + S. This method is similar to that of $LinUCB$ but leverages spillover
during direct treatment recommendation to a node.
LinUCB + S + O. This method is similar to that of $LinUCB+S$ but uses an
oracle while estimating expected rewards using Equation ($7$) and ($8$). The
oracle generates the true latent preferences of the adjacent directly treated
nodes.
NetCB. This is our proposed method that accounts for neighborhood knowledge
and leverages heterogeneous spillover during direct treatment recommendation
to a node. The payoff of a directly treated node is calculated as described in
our contextual bandit setup.
NetCB - S. This method is similar to that of $NetCB$ but does not leverage
spillover during treatment recommendation to a node.
NetCB + O. This method is similar to our method, $NetCB$ but uses an oracle
while estimating expected rewards using Equation ($7$) and ($8$). The oracle
generates the true latent preferences of the adjacent directly treated nodes.

Figure 2: Comparison of cumulative bandit accuracy, $B_{acc}$ of $LinUCB$ by
varying activation probabilities while keeping $p_{ma}=0.3$, $p_{aa}=0.3$,
$p_{mm}=0.0$, and $p_{am}=0.0$ in Experiment $1$.

Figure 3: Comparison of cumulative regrets, $Regret$ in real-world and semi-
synthetic networks by setting $p_{m}=0.5$, $p_{a}=0.7$, $p_{mm}=0.0$, and
$p_{am}=0.0$ in Experiment $2$.

Figure 4: Comparison of cumulative bandit accuracy, $B_{acc}$ between LinUCB
vs $NetCB_{1}$, NeuralUCB vs $NetCB_{2}$, and NeuralTS vs $NetCB_{3}$ by
setting $p_{m}=0.5$, $p_{a}=0.7$ $p_{ma}=0.3$, $p_{aa}=0.3$, $p_{mm}=0.0$,and
$p_{am}=0.0$ in Experiment $3$.

### Experimental setup

We experiment with single-hop spillover setup in the networks where the nodes
activated due to spillover effect cannot spread spillover to their adjacent
nodes. Therefore, spillover cannot cascade over the network. We use existing
contextual bandit MAB algorithms, e.g., LinUCB (Li et al. 2010), NeuralUCB
(Zhou, Li, and Gu 2020), and NeuralTS (Zhang et al. 2020) as a subroutine for
$NetCB-S$, $NetCB$, and $NetCB+O$. In all of our experiments, we set
$p_{mm}=0$, $p_{am}=0$. We set the hyper-parameter for confidence bound,
$\alpha=2.0$ when using LinUCB (Li et al. 2010) as a subroutine. Before the
start of an experiment with bandit, we set $arm_{i}=\emptyset$,
$t_{i}=\emptyset$, and $y_{i}=0$ for all $v_{i}\in V$.

####  Experiment 1:Understanding the impact of activation probability on
bandit accuracy, $B_{acc}$.

To understand how $B_{acc}$ changes with the increase in difference between
$p_{a}$ and $p_{m}$, we run $LinUCB$ with several combinations of $p_{a}$ and
$p_{m}$, i.e., ($0.1$, $0.7$), ($0.3$, $0.7$), ($0.5$, $0.7$) in real-world
networks. We run $25$ experiments with $p_{aa}=0.3$, $p_{ma}=0.3$,
$p_{am}=0.0$, $p_{mm}=0.0$ to incorporate heterogeneous spillover. The
cumulative average of the bandit accuracy, $B_{acc}$ has been reported in
Figure $2$.

####  Experiment 2:Understanding impact of neighborhood knowledge and
leveraging spillover on the bandit learning regrets, $Regret$.

The difference in activation rates ($p_{m}$ and $p_{a}$) plays a role in how
well the bandit can learn to distinguish between different types of nodes. The
higher the difference, the better the bandit accuracy as shown in Figure $2$.
However, neighborhood information helps the bandit learn to distinguish among
them, regardless of the difference in activation rate for aligned and
misaligned treatment. In real-world scenarios, $p_{m}$ and $p_{a}$ are unknown
and therefore it is very important to incorporate neighborhood information. To
understand whether dynamic neighborhood feature aggregation helps the bandit
to learn faster, we run $LinUCB$, $NetCB-S$, $LinUCB+S$, $NetCB$,
$LinUCB+S+O$, and $NetCB+O$ in both real-world and semi-synthetic networks
with $p_{a}=0.7$, and $p_{m}=0.5$. We use LinUCB (Li et al. 2010) as the
subroutine for $NetCB-S$ and $NetCB$. We run $25$ experiments by setting
$p_{aa}=0.1$, $p_{ma}=0.1$ and $p_{aa}=0.3$, $p_{ma}=0.3$ while keeping
$p_{am}=0.0$, $p_{mm}=0.0$. We compare $LinUCB$ vs $NetCB-S$ and $LinUCB+S$ vs
$NetCB$ to investigate the effect of neighborhood knowledge. To investigate
whether going against the bandit recommendation helps to increase spillover,
We compare $LinUCB$ vs $LinUCB+S$ vs $LinUCB+S+O$ and $NetCB-S$ vs $NetCB$ vs
$NetCB+O$. The cumulative average of the regrets, $Regret$ has been reported
in Figure $3$. Table- $1-2$ in the appendix include the bandit accuracy and
regrets, and all types of rewards at the end of bandit experiments.

####  Experiment 3: Understanding how the contextual bandit choice as a
subroutine impacts the bandit accuracy, $B_{acc}$.

We want to investigate the impact of choosing the underlying contextual bandit
algorithm as a subroutine and their hyper-parameter(s) on the learning
performance. Therefore, we experiment $NetCB$ with three contextual bandit
subroutines- LinUCB (Li et al. 2010), NeuralUCB (Zhou, Li, and Gu 2020), and
NeuralTS (Zhang et al. 2020) to understand the impact of bandit choice on
$B_{acc}$ and call these $NetCB$s as $NetCB_{1}$, $NetCB_{2}$, and
$NetCB_{3}$, respectively. We compare $NetCB_{1}$ vs $LinUCB$, $NetCB_{2}$ vs
$NeuralUCB$, and $NetCB_{3}$ vs $NeuralTS$. We set the hyper-parameter for
confidence bound, $\alpha=2.0$ in LinUCB. For both NeuralUCB and NeuralTS, we
set the regularization parameter, $\lambda=0.01$, neural network width,
$m=20$, and exploration variance, $\nu=1.0$. We set $p_{a}=0.7$, $p_{m}=0.5$,
$p_{aa}=0.3$, $p_{ma}=0.3$, $p_{am}=0.0$, and $p_{mm}=0.0$ for all experiments
and run $25$ experiments. The cumulative averages of the bandit accuracy,
$B_{acc}$ for all methods have been reported in Figure $4$.

We defer additional experiments to Appendix A4.

### Results

#### Impact of varying direct treatment effects on bandit accuracy, $B_{acc}$.

With the increase in difference between $p_{a}$ and $p_{m}$, the learning rate
or bandit accuracy increases in all networks as shown in Figure $2$. The
bandit can better differentiate among different types of nodes with higher
difference between $p_{a}$ and $p_{m}$. For example, when $p_{a}=0.7$ and
$p_{m}=0.1$, the bandit achieves around $21.73\%$, $26.97\%$, $78.48\%$, and
$77.48\%$ accuracy at the end of experiment in Flickr, Blogcatalog, Pubmed,
and Hateful networks, respectively. However, the bandit achieves $13.60\%$,
$19.47\%$, $54.11\%$, and $61.32\%$ accuracy in Flickr, Blogcatalog, Pubmed,
and Hateful networks, respectively, when $p_{a}=0.7$ and $p_{m}=0.5$. The
cumulative bandit accuracy, $B_{acc}$ becomes stable and does not change much
after directly treating around $10-15\%$ nodes in the networks as shown in
Figure $2$. The bandit accuracy tends to decrease with the increase in the
total number of labels, $l$ in the networks. For example, Pubmed network with
$l=3$ and Hateful network with $l=2$ achieve very high accuracy while Flickr
network with $l=9$ achieves lowest accuracy at the end of the experiments as
shown in Figure $2$.

#### Impact of neighborhood knowledge on $Regret$.

The aggregation of dynamic neighborhood knowledge reduces the bandit regrets,
$Regret$ compared to the corresponding baseline, especially in the high
homophilic networks as shown in Figure $3$. For example, in case of lower
spillover ($p_{aa}=0.1$, $p_{ma}=0.1$), the $Regret$ in $NetCB-S$ decreases by
$13.79\%$, $16.58\%$, $11.50\%$, and $4.92\%$ compared to $LinUCB$ in the
semi-synthetic Flickr (Homphily: 0.88), semi-synthetic Blogcatalog (Homphily:
0.88), Pubmed (Homphily: 0.80), and Hateful (Homphily: 0.73) networks,
respectively. These decreases in $NetCB$ are $11.52\%$, $22.18\%$, $14.29\%$,
and $3.81\%$ respectively, for these networks compared to $LinUCB+S$. In case
of higher spillover ($p_{aa}=0.3$, $p_{ma}=0.3$), aggregating neighborhood
knowledge helps to decrease the $Regret$ more compared to their lower
spillover counterparts. The impact of aggregating dynamic neighborhood
knowledge is less in lower homophilic networks compared to that of higher
homophilic networks as shown in Figure $3$. To summarise, dynamic neighborhood
information shows very helpful to achieve lower regrets in high homophilic
networks, especially when the spillover is high.

#### Impact of leveraging spillover on $Regret$.

Our proposed strategy to leverage spillover helps to decrease the, $Regrets$
as shown in Figure $3$ for $LinUCB+S+O$ and $NetCB+O$ compared to the
baselines. For example, in case of higher spillover ($p_{aa}=0.3$,
$p_{ma}=0.3$), $Regrets$ decreases by $37.22\%$, $41.77\%$, $7.90\%$, $3.49\%$
in $LinUCB+S+O$ compared to $LinUCB$ in the semi-synthetic Flickr (Homphily:
0.88), semi-synthetic Blogcatalog (Homphily: 0.88), Pubmed (Homphily: 0.80),
and Hateful (Homphily: 0.73) networks, respectively. These decreases in
$NetCB+O$ are $35.04\%$, $24.32\%$, $0.53\%$, and $2.47\%$ respectively,
compared to $NetCB-S$ for these networks. To summarise, $NetCB+O$ helps to
decrease $Regrets$, especially in high homophilic networks but the performance
tends to decay in imbalanced networks (e.g., Hateful). Our proposed strategy
to maximize spillover depends on the bandit accuracy, $B_{acc}$, therefore,
$NetCB$ does not help much in the datasets we used. However, in case of having
access to reliable latent preferences of the directly treated adjacent
inactive nodes, $Regrets$ in $LinUCB+S$ and $NetCB$ can reduce up to
$LinUCB+S+O$, and $NetCB+O$, respectively.

#### Impact of bandit algorithm choice on learning performance.

The bandit accuracy, $B_{acc}$ of $NetCB_{1}$ and $NetCB_{3}$ in all networks
looks higher in Figure $4$ compared to the corresponding baseline methods,
$LinUCB$, and $NeuralTS$, respectively. However, the performance of
$NetCB_{2}$ tends to rely on the choice and tuning of hyper-parameters of its
NeuralUCB (Zhou, Li, and Gu 2020) subroutine. The neural network fails to
learn and converge in $NeuralUCB$ for Flickr and Blogcatalog datasets and
$NetCB_{2}$ for Pubmed dataset.

We defer the results of additional experiments to Appendix A5.

## Conclusion and future work

We present $NetCB$ to leverage neighborhood knowledge and the potential of
heterogeneous spillover to maximize rewards in bandit online learning. We
demonstrated four types of spillover and some of their potential effects in
contextual bandit for networks with a single-hop spillover setup. Our
experiments on real-world and semi-synthetic networks show that neighborhood
knowledge helps to increase learning rate of the bandit in high homophilic
networks. The change in bandit recommendation based on expected rewards has an
impact on increasing network spillover when the learning rate of the bandit is
good. One possible extension of our research is to design a multi-hop
spillover setup for contextual bandit in networks and understand the impact of
spillover on learning performance. Future works include understanding the
performance of contextual bandit under temporal features, deriving regret
bounds for $NetCB$, and learning the value of treatment-dependent
heterogeneous spillover probability in networks.

## References

  * Agrawal and Goyal (2013) Agrawal, S.; and Goyal, N. 2013.  Thompson sampling for contextual bandits with linear payoffs.  In _International conference on machine learning_ , 127–135. PMLR.
  * Allesiardo, Féraud, and Bouneffouf (2014) Allesiardo, R.; Féraud, R.; and Bouneffouf, D. 2014.  A neural networks committee for the contextual bandit problem.  In _International Conference on Neural Information Processing_ , 374–381. Springer.
  * Aronow and Samii (2017) Aronow, P. M.; and Samii, C. 2017.  Estimating average causal effects under general interference, with application to a social network experiment.  _The Annals of Applied Statistics_ , 11(4): 1912–1947.
  * Bargagli-Stoffi, Tortu, and Forastiere (2020) Bargagli-Stoffi, F. J.; Tortu, C.; and Forastiere, L. 2020.  Heterogeneous treatment and spillover effects under clustered network interference.  _arXiv preprint arXiv:2008.00707_.
  * Chae et al. (2017) Chae, I.; Stephen, A. T.; Bart, Y.; and Yao, D. 2017.  Spillover effects in seeded word-of-mouth marketing campaigns.  _Marketing Science_ , 36(1): 89–104.
  * Chu et al. (2011) Chu, W.; Li, L.; Reyzin, L.; and Schapire, R. 2011.  Contextual bandits with linear payoff functions.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , 208–214. JMLR Workshop and Conference Proceedings.
  * Forastiere et al. (2021) Forastiere, L.; Lattarulo, P.; Mariani, M.; Mealli, F.; and Razzolini, L. 2021.  Exploring encouragement, treatment, and spillover effects using principal stratification, with application to a field experiment on teens’ museum attendance.  _Journal of Business & Economic Statistics_, 39(1): 244–258.
  * Hagiu and Wright (2015) Hagiu, A.; and Wright, J. 2015.  Marketplace or reseller?  _Management Science_ , 61(1): 184–203.
  * Halko, Martinsson, and Tropp (2009) Halko, N.; Martinsson, P.-G.; and Tropp, J. A. 2009.  Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions.
  * Holtz et al. (2020) Holtz, D.; Lobel, R.; Liskovich, I.; and Aral, S. 2020.  Reducing interference bias in online marketplace pricing experiments.  _arXiv preprint arXiv:2004.12489_.
  * Iacob, Cautis, and Maniu (2022) Iacob, A.; Cautis, B.; and Maniu, S. 2022.  Contextual Bandits for Advertising Campaigns: A Diffusion-Model Independent Approach.  In _Proceedings of the 2022 SIAM International Conference on Data Mining (SDM)_ , 513–521. SIAM.
  * Jia et al. (2021) Jia, Y.; Zhang, W.; Zhou, D.; Gu, Q.; and Wang, H. 2021.  Learning Neural Contextual Bandits through Perturbed Rewards.  In _International Conference on Learning Representations_.
  * Li et al. (2022) Li, H.; Zhao, G.; Johari, R.; and Weintraub, G. Y. 2022.  Interference, bias, and variance in two-sided marketplace experimentation: Guidance for platforms.  In _Proceedings of the ACM Web Conference 2022_ , 182–192.
  * Li et al. (2010) Li, L.; Chu, W.; Langford, J.; and Schapire, R. E. 2010.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , 661–670.
  * Lu, Pál, and Pál (2010) Lu, T.; Pál, D.; and Pál, M. 2010.  Contextual multi-armed bandits.  In _Proceedings of the Thirteenth international conference on Artificial Intelligence and Statistics_ , 485–492. JMLR Workshop and Conference Proceedings.
  * Ribeiro et al. (2018) Ribeiro, M. H.; Calais, P. H.; Santos, Y. A.; Almeida, V. A.; and Meira Jr, W. 2018.  Characterizing and detecting hateful users on twitter.  In _Twelfth international AAAI conference on web and social media_.
  * Schiltz et al. (2019) Schiltz, F.; Mazrekaj, D.; Horn, D.; and De Witte, K. 2019.  Does it matter when your smartest peers leave your class? Evidence from Hungary.  _Labour Economics_ , 59: 79–91.
  * Shakarian et al. (2015) Shakarian, P.; Bhatnagar, A.; Aleali, A.; Shaabani, E.; and Guo, R. 2015.  The independent cascade and linear threshold models.  In _Diffusion in Social Networks_ , 35–48. Springer.
  * Shani et al. (2005) Shani, G.; Heckerman, D.; Brafman, R. I.; and Boutilier, C. 2005.  An MDP-based recommender system.  _Journal of Machine Learning Research_ , 6(9).
  * Vaswani et al. (2017) Vaswani, S.; Kveton, B.; Wen, Z.; Ghavamzadeh, M.; Lakshmanan, L. V.; and Schmidt, M. 2017.  Model-independent online learning for influence maximization.  In _International Conference on Machine Learning_ , 3530–3539. PMLR.
  * Wen et al. (2017) Wen, Z.; Kveton, B.; Valko, M.; and Vaswani, S. 2017.  Online influence maximization under independent cascade model with semi-bandit feedback.  _Advances in neural information processing systems_ , 30.
  * Wilder et al. (2018) Wilder, B.; Immorlica, N.; Rice, E.; and Tambe, M. 2018.  Maximizing influence in an unknown social network.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Yan, Zhao, and Liu (2018) Yan, Y.; Zhao, R.; and Liu, Z. 2018.  Strategic introduction of the marketplace channel under spillovers from online to offline sales.  _European Journal of Operational Research_ , 267(1): 65–77.
  * Yuan and Altenburger (2022) Yuan, Y.; and Altenburger, K. M. 2022.  A Two-Part Machine Learning Approach to Characterizing Network Interference in A/B Testing.
  * Zhang et al. (2020) Zhang, W.; Zhou, D.; Li, L.; and Gu, Q. 2020.  Neural thompson sampling.  _arXiv preprint arXiv:2010.00827_.
  * Zhou, Li, and Gu (2020) Zhou, D.; Li, L.; and Gu, Q. 2020.  Neural contextual bandits with ucb-based exploration.  In _International Conference on Machine Learning_ , 11492–11502. PMLR.

Figure 5: Comparison of cumulative bandit accuracy, $B_{acc}$ between $LinUCB$
vs $NetCB-S$ and $LinUCB+S$ vs $NetCB$ by setting $p_{m}=0.5$, $p_{a}=0.7$,
$p_{mm}=0.0$, and $p_{am}=0.0$ in real-world (upper row) and semi-synthetic
(lower row) networks for Experiment $4$.

Figure 6: Comparison of cumulative spillover rewards, $R_{se}$ among $LinUCB$
vs $LinUCB+S$ vs $LinUCB+S+O$ and $NetCB-S$ vs $NetCB$ vs $NetCB+O$ in real-
world (upper row) and semi-synthetic (lower row) networks by setting
$p_{m}=0.5$, $p_{a}=0.7$, $p_{ma}=0.3$, $p_{aa}=0.3$, $p_{mm}=0.0$, and
$p_{am}=0.0$ in Experiment $5$.

## A1: Illustration of treatment-dependent heterogeneity

In Figure- $1(a)$, $t_{1}=P$ and thus $t_{1}=x_{1}$, therefore $v_{1}$ gets
aligned treatment. $v_{3}$ and $v_{6}$ get the aligned spillover from the
source node as $t_{1}=x_{3}$ and $t_{1}=x_{6}$, respectively, from the source
node $v_{1}$ that is activated due to aligned treatment. $v_{2}$ and $v_{4}$
get the misaligned spillover from the source node as $t_{1}\neq x_{2}$ and
$t_{1}\neq x_{4}$, respectively, from the source node $v_{1}$ that is
activated due to aligned treatment.

In Figure- $1(b)$, $t_{1}=S$ and thus $t_{1}\neq x_{1}$, therefore $v_{1}$
gets misaligned treatment. $v_{2}$ and $v_{4}$ get the aligned spillover from
the source node as $t_{1}=x_{2}$ and $t_{1}=x_{4}$, respectively, from the
source node $v_{1}$ that is activated due to misaligned treatment. $v_{3}$ and
$v_{6}$ get the misaligned spillover from the source node as $t_{1}\neq x_{3}$
and $t_{1}\neq x_{6}$, respectively, from the source node $v_{1}$ that is
activated due to misaligned treatment.

In both networks, there is no spillover from node $v_{1}$ to $v_{5}$ since
$v_{5}$ is already activated and spillover can happen from the currently
treated and activated node to its inactive adjacent nodes.

Figure 7: Comparison of cumulative spillover rewards, $R_{se}$ by setting
$p_{m}=0.5$, $p_{a}=0.7$, $p_{mm}=0.0$, and $p_{am}=0.0$ in Experiment $6$ by
varying spillover probabilities: $p_{ma}$ and $p_{aa}$ in high homophilic
networks.

| Blogcatalog (Homophily = $0.40$) | Flickr (Homophily = $0.23$)
---|---|---
Method Name | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$ | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$
$LinUCB$ | $19.1\%$ | $1719.0$ | $2344.8$ | $4063.8$ | $8842.8$ | $13.9\%$ | $3239.4$ | $1708.0$ | $4947.4$ | $9339.8$
$LinUCB+S$ | $20.2\%$ | $1745.2$ | $2264.4$ | $4009.6$ | $8793.6$ | $13.4\%$ | $3253.2$ | $1618.0$ | $4871.2$ | $9861.6$
$NetCB-S$ | $29.4\%$ | $1668.2$ | $2485.2$ | $4153.4$ | $7019.0$ | $15.3\%$ | $3190.8$ | $1752.4$ | $4943.2$ | $10255.8$
$NetCB$ | $29.2\%$ | $1673.8$ | $2401.2$ | $4075.0$ | $7940.6$ | $15.5\%$ | $3326.6$ | $1573.2$ | $4899.8$ | $12139.8$
$LinUCB+S+O$ | $18.0\%$ | $1620.4$ | $2776.2$ | $4396.6$ | $6189.4$ | $12.6\%$ | $3131.8$ | $2085.2$ | $5217.0$ | $7890.6$
$NetCB+O$ | $29.2\%$ | $1616.0$ | $2802.0$ | $4418.0$ | $5806.6$ | $16.7\%$ | $3140.6$ | $2191.6$ | $5332.2$ | $7822.8$

| Pubmed (Homophily = $0.80$) | Hateful (Homophily = $0.73$)
---|---|---
Method Name | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$ | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$
$LinUCB$ | $53.3\%$ | $10566.8$ | $2851.8$ | $13418.6$ | $11874.6$ | $61.6\%$ | $1665.4$ | $644.0$ | $2309.4$ | $1641.0$
$LinUCB+S$ | $55.8\%$ | $10557.4$ | $2701.4$ | $13258.8$ | $11982.6$ | $61.1\%$ | $1656.2$ | $636.8$ | $2293.0$ | $1627.2$
$NetCB-S$ | $73.1\%$ | $10808.8$ | $3461.0$ | $14269.8$ | $8590.8$ | $70.1\%$ | $1673.4$ | $688.4$ | $2361.8$ | $1492.0$
$NetCB$ | $72.6\%$ | $10747.8$ | $3483.2$ | $14231.0$ | $8672.2$ | $71.7\%$ | $1679.4$ | $691.2$ | $2370.6$ | $1537.0$
$LinUCB+S+O$ | $53.9\%$ | $10344.6$ | $3284.2$ | $13628.8$ | $10936.4$ | $62.5\%$ | $1642.4$ | $680.2$ | $2322.6$ | $1583.8$
$NetCB+O$ | $73.9\%$ | $10777.0$ | $3554.6$ | $14331.6$ | $8545.2$ | $71.8\%$ | $1697.4$ | $700.2$ | $2397.6$ | $1455.0$

Table 1: Experimental results for real-world networks where $p_{m}=0.5$,
$p_{a}=0.7$, $p_{ma}=0.3$, $p_{aa}=0.3$, $p_{mm}=0.0$, and $p_{am}=0.0$.

| Blogcatalog (Homophily = $0.88$) | Flickr (Homophily = $0.88$)
---|---|---
Method Name | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$ | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$
$LinUCB$ | $19.5\%$ | $1978.8$ | $1920.6$ | $3899.4$ | $9468.4$ | $13.3\%$ | $3453.2$ | $1164.6$ | $4617.8$ | $10264.6$
$LinUCB+S$ | $19.7\%$ | $1989.0$ | $1717.4$ | $3706.4$ | $10532.8$ | $13.3\%$ | $3528.2$ | $975.6$ | $4503.8$ | $11333.4$
$NetCB-S$ | $34.9\%$ | $1784.0$ | $2353.8$ | $4137.8$ | $6241.2$ | $22.0\%$ | $3447.4$ | $1439.0$ | $4886.4$ | $8962.8$
$NetCB$ | $34.2\%$ | $1788.4$ | $2304.8$ | $4093.2$ | $6530.0$ | $21.3\%$ | $3474.4$ | $1318.8$ | $4793.2$ | $9771.4$
$LinUCB+S+O$ | $17.6\%$ | $1699.0$ | $2637.8$ | $4336.8$ | $5513.2$ | $13.0\%$ | $3157.4$ | $2024.6$ | $5182.0$ | $6444.2$
$NetCB+O$ | $34.2\%$ | $1719.2$ | $2695.6$ | $4414.8$ | $4723.4$ | $24.2\%$ | $3264.0$ | $2050.6$ | $5314.6$ | $5822.2$

| Pubmed (Homophily = $0.30$) | Hateful (Homophily = $0.58$)
---|---|---
Method Name | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$ | $B_{acc}$ | $R_{dte}$ | $R_{se}$ | $R_{total}$ | $Regret$
$LinUCB$ | $56.1\%$ | $10904.0$ | $2117.2$ | $13021.2$ | $11068.6$ | $59.5\%$ | $1673.2$ | $601.8$ | $2275.0$ | $1689.2$
$LinUCB+S$ | $55.4\%$ | $10866.6$ | $2157.6$ | $13024.2$ | $11096.8$ | $60.5\%$ | $1667.2$ | $599.8$ | $2267.0$ | $1677.4$
$NetCB-S$ | $53.6\%$ | $10829.0$ | $2265.4$ | $13094.4$ | $10562.8$ | $59.7\%$ | $1656.6$ | $638.8$ | $2295.4$ | $1625.0$
$NetCB$ | $52.7\%$ | $10806.0$ | $2250.2$ | $13056.2$ | $10668.0$ | $57.7\%$ | $1644.4$ | $622.4$ | $2266.8$ | $1663.0$
$LinUCB+S+O$ | $54.0\%$ | $10869.2$ | $2375.0$ | $13244.2$ | $11009.4$ | $60.0\%$ | $1640.6$ | $651.6$ | $2292.2$ | $1611.0$
$NetCB+O$ | $52.8\%$ | $10737.4$ | $2469.6$ | $13207.0$ | $10601.4$ | $62.1\%$ | $1649.6$ | $664.8$ | $2314.4$ | $1561.8$

Table 2: Experimental results for semi-synthetic networks where $p_{m}=0.5$,
$p_{a}=0.7$, $p_{ma}=0.3$, $p_{aa}=0.3$, $p_{mm}=0.0$, and $p_{am}=0.0$.

## A2: NetCB algorithm

Formally, the $NetCB$ algorithm proceeds in discrete trials $i=1,2,3,\ldots,T$
[Line: $5$] followed by the initialization of the arm parameters and bandit
hyper-parameter(s) [Line: $1-4$]. In trial $i$:

  1. 1.

An inactive node $v_{i}$ arrives to receive direct treatment assignment. The
algorithm observes the feature vector $X_{i}$ of the current node $v_{i}$,
feature vector $X_{\mathcal{N}_{i}}$ of it’s adjacent nodes, and bandit
parameters for the set of arms, $\mathcal{A}$ together [Line: 6].

  2. 2.

Based on observed payoffs in previous nodes, the algorithm recommends an arm,
${arm}_{i}\in\mathcal{A}$ to assign a direct treatment class to node $v_{i}$
[Line: $7$].

  3. 3.

Estimate the expected rewards for the recommended arm, $arm_{i}$ for node
$v_{i}$, $E[R_{i}\,|\,arm_{i}]$ [Line: 8]. Similarly, estimate the expected
rewards for all other arms, $arm_{k}$ [Line: 9-11] and find maximum expected
reward generating arm, $\overline{arm_{i}}$ and its expected rewards,
$E[R_{i}\,|\,\overline{arm_{i}}]$ for node $v_{i}$ [Line: 12].

  4. 4.

If $E[R_{i}\,|\,arm_{i}]\geq E[R_{i}\,|\,\overline{arm_{i}}]$, assign the
direct treatment class, $t_{i}=arm_{i}$ to node $v_{i}$. The node $v_{i}$ then
receives payoff, $PO(v_{i}|arm_{i})$. The bandit parameters and neighborhood
features, $X_{\mathcal{N}_{i}}$ are updated. The algorithm then improves its
arm-selection strategy with the observation, $(X_{i},{arm}_{i},payoff(v_{i}))$
[Line: 13-16].

  5. 5.

If $E[R_{i}\,|\,arm_{i}]\ngeq E[R_{i}\,|\,\overline{arm_{i}}]$, assign the
direct treatment class, $t_{i}=\overline{arm_{i}}$ to node $v_{i}$. The node
$v_{i}$ then receives payoff, $PO(v_{i},\overline{arm_{i}})$. The neighborhood
features, $X_{\mathcal{N}_{i}}$ are updated but the bandit parameters are not
updated [Line: 18-20].

## A3: Generation of semi-synthetic data-sets

To increase homophily in a network, we randomly remove edges to generate a new
semi-synthetic network. In this edge removal process, we consider only those
edges that connect two nodes from different latent preferences where both
nodes have at least two edges. Using this procedure, we create semi-synthetic
Flickr and Blogcatalog networks with a homophilic score of $0.88$.

To decrease homophily in a network, we randomly swap nodes with different
latent preferences in the network along with their features and corresponding
labels to generate a new semi-synthetic network. In this node swapping
process, we consider only those node pairs swapping of which results in
increasing edges that connect two nodes from different latent preferences.
Using this procedure, we create semi-synthetic Pubmed and Hateful networks
with a homophilic score of $0.30$ and $0.58$, respectively.

## A4: Additional Experiments

### Experiment 4: Understanding the impact of neighborhood knowledge on bandit
accuracy, $B_{acc}$

The difference in activation rates ($p_{m}$ and $p_{a}$) plays a role in how
well the bandit can learn to distinguish between different types of nodes. The
higher the difference, the better the bandit accuracy as shown in Figure- $2$.
However, neighborhood information helps the bandit learn to distinguish among
them, regardless of the difference in activation rate for aligned and
misaligned treatment. In real-world scenarios, $p_{m}$ and $p_{a}$ are unknown
and therefore it is very important to incorporate neighborhood information. To
understand whether dynamic neighborhood feature aggregation helps the bandit
to learn faster, we run $LinUCB$, $NetCB-S$, $LinUCB+S$, and $NetCB$ in both
real-world and semi-synthetic networks with $p_{a}=0.7$, and $p_{m}=0.5$. We
use LinUCB (Li et al. 2010) as the subroutine for $NetCB-S$ and $NetCB$. We
run $25$ experiments by setting $p_{aa}=0.1$, $p_{ma}=0.1$ and $p_{aa}=0.3$,
$p_{ma}=0.3$ while keeping $p_{am}=0.0$, $p_{mm}=0.0$. We compare $LinUCB$ vs
$NetCB-S$ and $LinUCB+S$ vs $NetCB$. The cumulative average of the bandit
accuracy, $B_{acc}$ has been reported in Figure-$5$.

### Experiment 5: Understanding the impact of assigning direct treatment with
the arm of highest expected rewards instead of the recommended arm

We want to investigate whether going against the bandit recommendation helps
to increase spillover in both low and high homophilic networks. Therefore, we
run $LinUCB$, $NetCB-S$, $LinUCB+S$, $NetCB$, $LinUCB+S+O$, and $NetCB+O$ in
both real-world and semi-synthetic networks. We use LinUCB (Li et al. 2010) as
a subroutine for $NetCB-S$, $NetCB$, and $NetCB+O$. We run $25$ experiments by
setting $p_{a}=0.7$, $p_{m}=0.5$, $p_{aa}=0.3$, $p_{ma}=0.3$, $p_{am}=0.0$,
and $p_{mm}=0.0$. We compare $LinUCB$ vs $LinUCB+S$ vs $LinUCB+S+O$ and
$NetCB-S$ vs $NetCB$ vs $NetCB+O$. The cumulative average of the total
spillover rewards, $R_{se}$ has been reported in Figure-$6$. Table- $1-2$ show
the bandit accuracy, $B_{acc}$ and all types of rewards at the end of bandit
experiments.

### Experiment 6: Impact of varying spillover probabilities on performance

To understand how total spillover rewards, $R_{se}$ changes with the change in
heterogeneity of spillover, we run and compare all methods with several
combinations of $p_{aa}$ and $p_{ma}$, i.e., ($0.1$, $0.5$), ($0.3$, $0.5$),
($0.5$, $0.5$). We choose only high homophilic networks, i.e., semi-synthetic
Flickr (Homophily: $0.88$), semi-synthetic Blogcatalog (Homophily: $0.88$),
Pubmed (Homophily: $0.80$), and Hateful (Homophily: $0.73$) networks since our
proposed method learns faster in high homophilic networks. We use LinUCB (Li
et al. 2010) as a subroutine for $NetCB-S$, $NetCB$, and $NetCB+O$. We run
$25$ experiments by setting $p_{m}=0.5$, $p_{a}=0.7$, $p_{am}=0.0$, and
$p_{mm}=0.0$. The cumulative average of the total spillover rewards, $R_{se}$
has been reported in Figure-$7$.

## A5: Results of additional Experiments

### Impact of neighborhood knowledge on the bandit accuracy, $B_{acc}$

The aggregation of dynamic neighborhood knowledge increases the bandit
accuracy, $B_{acc}$ compared to the corresponding baseline, especially in the
high homophilic networks as shown in Figure- $5$. For example, in case of
lower spillover ($p_{aa}=0.1$, $p_{ma}=0.1$), the bandit accuracy, $B_{acc}$s
in $NetCB-S$ increases by $5.85\%$, $10.24\%$, $9.23\%$, and $2.56\%$ compared
to $LinUCB$ in the semi-synthetic Flickr (Homphily: 0.88), semi-synthetic
Blogcatalog (Homphily: 0.88), Pubmed (Homphily: 0.80), and Hateful (Homphily:
0.73) networks, respectively. These increases in $NetCB$ are $6.16\%$,
$11.33\%$, $7.53\%$, and $4.48\%$ respectively, for these networks compared to
$LinUCB+S$. In case of higher spillover ($p_{aa}=0.3$, $p_{ma}=0.3$),
aggregating neighborhood knowledge helps to increase the learning rate more
compared to their lower spillover counterparts. For example, the bandit
accuracy, $B_{acc}$s in $NetCB-S$ increases by $7.47\%$, $14.89\%$, $12.19\%$,
and $11.08\%$ compared to $LinUCB$ in the semi-synthetic Flickr (Homphily:
0.88), semi-synthetic Blogcatalog (Homphily: 0.88), Pubmed (Homphily: 0.80),
and Hateful(Homphily: 0.73) networks, respectively. These increases in $NetCB$
are $7.54\%$, $14.584\%$, $8.02\%$, and $8.84\%$, respectively, for these
networks compared to $LinUCB+S$.

The impact of aggregating dynamic neighborhood knowledge is less in lower
homophilic networks compared to that of higher homophilic networks as shown in
Figure- $5$. In case of lower spillover ($p_{aa}=0.1$, $p_{ma}=0.1$), the
bandit accuracy, $B_{acc}$s in $NetCB-S$ changes by $2.14\%$ (increase),
$6.7\%$ (increase), $6.52\%$ (decrease), and $1.08\%$ (increase) compared to
$LinUCB$ in the Flickr (Homphily: 0.23), Blogcatalog (Homphily: 0.40), semi-
synthetic Pubmed (Homphily: 0.30), and semi-synthetic Hateful (Homphily: 0.58)
networks, respectively. These changes in $NetCB$ are $1.74\%$ (increase),
$7.5\%$ (increase), $2.22\%$ (decrease), and $0.45\%$ (increase),
respectively, for these networks compared to $LinUCB+S$. In case of higher
spillover ($p_{aa}=0.3$, $p_{ma}=0.3$), aggregating neighborhood knowledge
does not increase the learning rate much. For example, the bandit accuracy,
$B_{acc}$s in $NetCB-S$ changes by $2.35\%$ (increase), $11.46\%$ (increase),
$6.47\%$ (decrease), and $1.78\%$ (decrease) compared to $LinUCB$ in the
Flickr (Homphily: 0.23), Blogcatalog (Homphily: 0.40), semi-synthetic Pubmed
(Homphily: 0.30), and semi-synthetic Hateful (Homphily: 0.58) networks,
respectively. These changes in $NetCB$ are $1.43\%$ (increase), $10.28\%$
(increase), $4.23\%$ (decrease), and $1.87\%$ (decrease) respectively, for
these networks compared to $LinUCB+S$.

To summarise, dynamic neighborhood information shows very helpful to learn
faster in high homophilic networks, especially when the spillover is high.

### Impact of changing recommendation for direct treatment based on the
expected spillover

Our proposed strategy to maximize spillover helps to increase total spillover
rewards, $R_{se}$ as shown in Figure- $6$ and Table- [$1-2$] for $LinUCB+S+O$
and $NetCB+O$ compared to the baselines. For example, $R_{se}$ increases by
$22.1\%$, $18.4\%$, $15.16\%$, $5.62\%$ in $LinUCB+S+O$ compared to $LinUCB$
for Flickr, Blogcatalog, Pubmed, and Hateful networks, respectively. These
increases in $NetCB+O$ are $25.06\%$, $12.75\%$, $2.7\%$, and $1.71\%$
respectively, compared to $NetCB-S$ for these networks. In case of semi-
synthetic networks, $R_{se}$ increases by $73.84\%$, $37.34\%$, $12.17\%$,
$8.28\%$ in $LinUCB+S+O$ compared to $LinUCB$ for Flickr, Blogcatalog, Pubmed,
and Hateful semi-synthetic networks, respectively. These increases in
$NetCB+O$ are $42.5\%$, $14.52\%$, $9\%$, and $4.07\%$ respectively, compared
to $NetCB-S$ for these networks.

The increase in spillover helps to increase total rewards, $R_{total}$ as
well. For example, $R_{total}$ increases by $5.45\%$, $8.19\%$, $1.57\%$,
$0.57\%$ in $LinUCB+S+O$ compared to $LinUCB$ for Flickr, Blogcatalog, Pubmed,
and Hateful networks, respectively. These increases in $NetCB+O$ are $7.87\%$,
$6.37\%$, $0.43\%$, and $1.52\%$ respectively, compared to $NetCB-S$ for these
networks. In case of semi-synthetic networks, $R_{total}$ increases by
$12.22\%$, $11.22\%$, $1.71\%$, $0.76\%$ in $LinUCB+S+O$ compared to $LinUCB$
for Flickr, Blogcatalog, Pubmed, and Hateful semi-synthetic networks,
respectively. These increases in $NetCB+O$ are $8.76\%$, $6.7\%$, $0.86\%$,
and $0.83\%$, respectively, compared to $NetCB-S$ for these networks.

To summarise, $NetCB+O$ helps to increase spillover and total rewards,
especially in high homophilic networks but the performance tends to decay in
imbalanced networks (e.g., Hateful, Pubmed). Our proposed strategy to maximize
spillover depends on the bandit accuracy, $B_{acc}$, therefore, $NetCB$ does
not help much in the datasets we used. However, in case of having access to
reliable latent preferences of the directly treated adjacent inactive nodes,
the spillover rewards, $R_{se}$ in $LinUCB+S$ and $NetCB$ can reach up to
$LinUCB+S+O$, and $NetCB+O$, respectively.

### Impact of varying spillover effects on $Rewards$

The $NetCB+O$ tends to increase spillover rewards, $R_{se}$ more compared to
the baselines with the decrease in difference between $p_{aa}$ and $p_{ma}$ in
semi-synthetic networks (Flickr, Blogcatalog) [Figure - $7$] and real-world
networks (Pubmed, Hateful) [not shown].