# Networked Restless Bandits with Positive Externalities

Christine Herlihy, John P. Dickerson

###### Abstract

Restless multi-armed bandits are often used to model budget-constrained
resource allocation tasks where receipt of the resource is associated with an
increased probability of a favorable state transition. Prior work assumes that
individual arms only benefit if they receive the resource directly. However,
many allocation tasks occur within communities and can be characterized by
positive externalities that allow arms to derive partial benefit when their
neighbor(s) receive the resource. We thus introduce _networked restless
bandits_ , a novel multi-armed bandit setting in which arms are both restless
and embedded within a directed graph. We then present Greta, a graph-aware,
Whittle index-based heuristic algorithm that can be used to efficiently
construct a constrained reward-maximizing action vector at each timestep. Our
empirical results demonstrate that Greta outperforms comparison policies
across a range of hyperparameter values and graph topologies. For
reproducibility purposes, all code is available at:
crherlihy/networked_restless_bandits.

##  1 Introduction

We study the planning task of allocating budget-constrained indivisible
resources so as to maximize the expected amount of time that members of a
cohort will spend in a desirable state (e.g., adherent to a prescribed
exercise regimen). Restless multi-arm bandits (RMABs) are well-suited for such
tasks, as they represent each individual as a Markov decision process (MDP)
whose stochastic state transitions are governed by an action-dependent
transition function.

Conventionally, an arm must receive the resource at time $t$ to derive any
benefit from it, where benefit takes the form of an increased probability of
transitioning to the desirable state at time $t+1$ (i.e., relative to non-
receipt). However, many resource allocation tasks _occur within communities_
and can be characterized by _positive externalities_ that allow arms to derive
partial, indirect benefit when their neighbor(s) receive the resource. We
consider chronic disease management programs as a motivating example. These
programs often combine resource-constrained physician support with less cost-
intensive, more scalable peer support to encourage participants to make
lifestyle modifications. To this end, we introduce _networked restless
bandits_ , a novel multi-armed bandit setting in which arms are both restless
and embedded within a directed graph. We then present a graph-aware, Whittle-
based heuristic algorithm that is constrained reward-maximizing in this
setting. Our core contributions include:

  1. (i)

Our networked restless bandit model, which lets us represent topological
relationships between arms, and associate arm $i$’s receipt of a pull with
positive externalities for its neighbors.

  2. (ii)

Greta, a graph-aware, Whittle index-based heuristic algorithm that lets us
efficiently construct a constrained reward-maximizing mapping from arms to
actions at each timestep.

  3. (iii)

Empirical results which demonstrate that Greta outperforms comparison policies
across a range of hyperparameter values and graph topologies.

###  1.1 Related Work

Restless bandits: The restless multi-armed bandit (RMAB) framework was
introduced by Whittle (1988) as a way to model the sequential allocation of a
budget-constrained, indivisible resource over a population of $N$ dynamic
arms, where: (1) at most $k\ll n$ arms can receive the resource (i.e., a pull)
at any given timestep; and (2) the state of each arm evolves over time,
regardless of whether or not it is pulled. We provide a formal description in
Section 2.1.

Indexability: In the general case, it is PSPACE-hard to pre-compute the
optimal policy for a given cohort of restless arms (Papadimitriou and
Tsitsiklis 1994). However, as conjectured by Whittle (1988) and proven by
Weber and Weiss (1990), when each arm is indexable, a tractable solution
exists that is provably asymptotically optimal: we can decouple the arms and
consider a Lagrangian relaxation of the original problem. In this context, the
Whittle index can be thought of as the infimum subsidy required to make an arm
indifferent between a pull and passivity, given its current state. Whittle-
index based policies use these index values to rank arms when selecting which
$k$ arms to pull.

Proving indexability can be difficult and often requires the problem instance
to satisfy specific structural properties, such as the optimality of threshold
policies (Liu and Zhao 2010). Additionally, much of the foundational work in
this space focuses on the two-action setting, and cannot be directly extended
to the multi-action setting that we consider.

Glazebrook, Hodge, and Kirkbride (2011) do consider the multi-action setting,
but for divisible rather than indivisible resources; they also require an arm
to consume this resource at a level that is decreasing in the resource charge.
Killian, Perrault, and Tambe (2021) study multi-action restless bandits and do
not make any of the structural assumptions required to verify indexability,
but instead develop a Lagrangian bound-minimization approach; however, they do
not consider relationships among arms.

Mate et al. (2020) introduce the collapsing bandit model, and demonstrate that
this problem is indexable when forward or reverse threshold policies are
optimal. They also introduce an efficient, closed-form approach to computing
the Whittle index called Threshold Whittle (TW), and empirically demonstrate
that this approach performs well even when optimality conditions are not
satisfied. We leverage TW as a subroutine within Greta.

Bandits and graphs: Prior work at the intersection of multi-armed bandits and
graphs has tended to focus on _stochastic_ , rather than restless arms, and on
_graph-structured feedback_ (i.e., rewards), rather than the embedding of arms
within a directed graph, and/or the spillover effects associated with
allocation in the face of adjacency. For example, Valko (2016) examines a
graph structure among actions in _stochastic_ bandits, and Lu, Hu, and Zhang
(2021) examines a graph structure over rewards. However, we examine a graph
structure among arms in the restless bandit setting.

In recent work, Ou et al. (2022) look at a mobile intervention setting.
Similarly to our model, they combine the traditional restless bandit setting
with network externalities; however, their model and goal are fundamentally
different. Their arms represent locations on a network with pulls impacting a
mixture of subpopulations that are located at or near that pull,
probabilistically. In contrast, in our model, vertices represent individual
arms, and our algorithm exploits—when advantageous—the propensity for
allocating a high-cost, high-benefit resource to one arm to unlock potential
lower-cost, intermediate-benefit resources for the arm’s neighbors.

##  2 Model Preliminaries

###  2.1 Restless Multi-arm Bandits

The restless bandit (RMAB) setting features an agent with $n\in\mathbb{N}$
arms. The state of each arm evolves over time and in response to the agent’s
actions, in a way that is governed by the arm’s underlying Markov decision
process (MDP). Each MDP is defined by a state space, $\mathcal{S}$, an action
space, $\mathcal{A}$, a cost function, $C:\mathcal{A}\rightarrow\mathbb{R}$, a
local reward function, $r:\mathcal{S}\rightarrow\mathbb{R}$, and a transition
function, $P:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$. The
objective is to find a policy, $\pi:\mathcal{S}\rightarrow\mathcal{A}$, that
maximizes total expected discounted reward over a finite time horizon,
$T$—i.e.,
$\pi^{*}=\operatorname*{arg\,max}_{\pi}E_{\pi}\left[R(\cdot)\right]$. The
agent must select exactly one action per arm at each timestep, and the
associated costs must not exceed the per-timestep budget,
$B~{}\in~{}\mathbb{R}_{\geq 0}$.

###  2.2 Motivating Example

For ease of exposition, we ground our networked restless bandit model in a
_motivating example_ : let arms represent patients striving to adhere to a
chronic disease management program, such as an exercise regimen. A patient’s
“state” on any given day is thus determined by whether they adhere (i.e.,
exercise), or fail to adhere to their regimen. To encourage adherence, many
such programs feature a combination of resource-constrained physician- and
peer support (Fisher et al. 2017). Examples include, but need not be limited
to, a reminder call from a physician, a supportive message from a fellow
participant, or the provision of awareness-raising outreach materials. Thus, a
coordinator seeking to maximize the number of patients who exercise over the
program’s duration might select a small subset of patients each day to receive
a call from a physician, and ask these people to message a handful of their
peers in turn, or pass along an educational pamphlet to their caregiver(s). In
each case, the lower-cost, easier-to-scale information dissemination option
amplifies physician outreach, allowing a broader subset of individuals to
receive partial benefit.

###  2.3 Networked Restless Bandits

With this motivating example in mind, we now introduce our networked restless
bandit model, which allows us to model directed relationships among arms.
Given a set of $n$ arms, let $G=(V,E)$ be a directed graph, and let there
exist a bijective mapping $\upvarphi$ from arms to vertices — i.e., $\forall
v\in V,\ \exists!\ i\in[n]\text{ s.t. }\upvarphi(i)=v$. Let a directed edge,
$e\in E$, exist between arms $u$ and $v$ if it is possible for $v$ to benefit
indirectly when $u$ receives a pull. Let ${\cal
N}_{\text{in}}(u)~{}=~{}\\{v\in V\ |~{}\ \exists e_{v,u}\in E\\}$ and ${\cal
N}_{out}(u)~{}=~{}\\{v\in V\ |~{}\ \exists e_{u,v}\in E\\}$ represent $u$’s
one-hop indegree and outdegree neighborhoods, respectively. This graph is
assumed to be constructed or operated by the agent; as such, it is assumed to
be observable. Real-life examples with this property include mentoring
programs and online social networks.

State space: We consider a discrete state space,
$\mathcal{S}~{}:=~{}\\{0,1\\}$, where the states admit a total ordering by
desirability, such that state 1 is more “desirable” than state 0. In our
example, state 0 represents non-adherence to the exercise regimen, while state
1 represents adherence. We assume each arm’s state is observable (e.g., via
fitness tracker data).

Action space: The traditional restless bandit setting considers a binary
action space, $\mathcal{A}:=\\{0,1\\}$, where 1 (or 0) represents the decision
to pull (or not pull) arm $i$ at time $t$. To model positive externalities, we
define an extended action space, $\mathcal{A}:=\\{0:\texttt{no-
act},1:\texttt{message},2:\texttt{pull}\\}$. Here, actions 0 and 2 correspond
to the actions _don’t pull_ and _pull_ respectively. We note that our message
action need not represent a literal message. Instead, it represents an
intermediate action with respect to desirability that gets “unlocked” as an
available action for vertex $v$ at time $t$ only when some vertex $u\in{\cal
N}_{\text{in}}(v)$ receives a pull at time $t$.

Transition function: For each arm $i\in[n]$, let $P^{a,i}_{s,s^{\prime}}$
represent the probability that arm $i$ will transition from state $s$ to
${s}^{\prime}$ given action $a$. In the offline setting, these transition
matrices are assumed to be static and known to the agent at planning time.
This assumption is reasonable when historical data from the same or similar
population(s) provides a source for informative priors, as is common in many
domains, including healthcare and finance (Steimle and Denton 2017; Pasanisi,
Fu, and Bousquet 2012). Extension to the online setting where transition
matrices must be learned is possible via Thompson sampling (Thompson 1933;
Ortner et al. 2012; Jung and Tewari 2019; Jung, Abeille, and Tewari 2019).

We assume nonzero transition matrix entries, and impose two sets of domain-
motivated structural constraints (Mate et al. 2020):  (i) $\forall
a\in\mathcal{A},P^{a}_{0,1}<P^{a}_{1,1}$and  (ii)
$\forall(a,a^{\prime})\in\mathcal{A}\times\mathcal{A},a<a^{\prime}\rightarrow
P^{a}_{0,1}<P^{a^{\prime}}_{0,1};P^{a}_{1,1}<P^{a^{\prime}}_{1,1}$.
Constraint set (i) implies that each arm is more likely to stay in the
desirable state (i.e., $s=1$) than transition there from the undesirable state
(i.e., $s=0$). Constraint set (ii) implies that messages and pulls are
beneficial when received and that a strict preference relation over actions
can be defined for each arm, such that no-act $\prec$ message $\prec$ pull.

Cost function: We map our action space to the cost vector
$\vec{c}=[0,\psi,1]$, where $0\leq\psi<1$. Intuitively, this mapping preserves
standard notion that no cost is incurred when an arm does not receive any form
of intervention. It also encodes the idea that the more beneficial an action
is, the more expensive it is to provide, which motivates us to exploit
positive externalities. Additionally, when there are no edges, i.e.,
$E=\emptyset$, and no messages can be sent, the unit cost of a pull lets us
recover the original restless bandit setting, where we must choose which $k\ll
n$ arms to pull at each timestep.

Objective and constraints: It is possible, though not tractable at scale, to
take a constrained optimization-based approach to solving for the optimal
policy, $\pi^{*}$. We build on Killian, Perrault, and Tambe (2021)’s approach
below to show how our constrained setting can be modeled. To begin, let
$\mathbf{s}$ represent a vector containing the state of each arm, i.e.
$[s^{i}\in\mathcal{S}|i\in[n]]$, and let $\mathbf{X}$ represent a matrix
containing binary decision variables, one for each of $n$ arms and $|{\cal
A}|$ actions. We require our local reward function,
$r:\mathcal{S}\rightarrow\mathbb{R}$ to be non-decreasing in $s$, which is
consistent with our goal of maximizing the expected time that each arm spends
in the “desirable” state. Equation 1 formalizes our task:

$\begin{array}[]{l@{}ll}J(\mathbf{s})=\max\limits_{\mathbf{X}}&\left\\{\displaystyle\sum_{i=0}^{n-1}r^{i}(s^{i})+\beta\mathbb{E}[J(\mathbf{s}^{\prime}),\mathbf{X}]\right\\}&\\\
\text{subject to
}&\displaystyle\sum_{i=0}^{n-1}\sum_{j=0}^{|\mathcal{A}|-1}x_{i,j}\cdot
c_{j}\leq B&\\\ &x_{i,1}\leq\displaystyle\bigvee_{i^{\prime}\in{\cal
N}_{\text{in}}(i)}x_{i^{\prime},2}&\forall i\in[n]\\\
&\displaystyle\sum_{j=0}^{|\mathcal{A}|-1}x_{i,j}=1&\forall i\in[n]\\\
&\mathbf{X}\in\\{0,1\\}^{n\times|\mathcal{A}|}&\end{array}$ (1)

Our goal is to find assignments of the decision variables contained in
$\mathbf{X}$ such that expected discounted reward is maximized, subject to a
series of feasibility constraints: (i) across all actions and arms, do not
expend more than $B$ budget; (ii) ensure that if message is chosen for an arm
$i$, then that arm has at least one indegree neighbor $i^{\prime}$ such that
pull was chosen; and, (iii) ensure that each arm receives exactly one action
at each timestep. However, two challenges arise: (1) a direct solution via
value iteration is exponential in $n$, and (2) Lagrangian relaxation-based
approaches rely on the decoupling of arms, which jeopardizes the satisfaction
of our neighborhood constraint on actions. This motivates us to propose a
graph-aware, Whittle-based heuristic algorithm.

##  3 Algorithmic Approach

Here, we introduce Greta, a graph-aware, Whittle-index-based heuristic
algorithm that can be used to efficiently construct a constrained reward-
maximizing policy. A key insight that Greta exploits is that while we cannot
decouple arms in the networked setting, since we must know whether any of an
arm’s indegree neighbors will receive a pull at time $t$ to know if the arm is
eligible to receive a message, we _can_ compute two sets of Whittle indices
for each arm, by considering each active action as a separate instance of a
two-action problem. Note that the structural constraints ensure that for a
given state, an arm will require a higher subsidy to forgo a pull as opposed
to a message. We can then construct an augmented graph that allows us to
compare the cumulative subsidy required for the arms represented by directed
edge $(u,v)$ to forgo a _pull_ and _message_ , respectively to those required
by other directed edges $\in G$ (including, importantly, the inverse action-
pair implied by edge $(v,u)$).

###  3.1 Greta: A Graph-aware Heuristic

Set-up: We begin by building an augmented graph, $G^{\prime}$. This graph
contains every vertex and edge in $G$, along with a dummy vertex, $-1$, and
directed edge $(u,-1)~{}\forall u\in V$. This lets us map each directed edge
$(u,v)$ in $G$ to the action pair $(\texttt{pull},~{}\texttt{message})$, and
$(u,-1)$ to $(\texttt{pull},~{}\texttt{no-act})$. We also construct an
augmented arm set, $[n]\cup\\{-1\\}$, and extend our bijective mapping from
arms to vertices such that $\upvarphi:-1\mapsto-1$. Appendix A.1 provides
pseudocode.

Next, we pre-compute the Whittle index for each vertex-active action
combination $(v,\alpha)\in V^{\prime}\times\mathcal{A}\setminus\\{0\\}$. When
we compute the Whittle index for a given $(v,\alpha)$ pair, we seek the
infimum subsidy, $m$, required to make arm $i$ (i.e., $\upvarphi^{-1}(v)$)
indifferent between passivity (i.e., no-act) and receipt of action $\alpha$ at
time $t$ (Whittle 1988). We cannot compute the Whittle index for our
placeholder $-1$ vertex because it is not attached to an MDP, so we map it to
0.

Algorithm 1 Compute Whittle indices for
$V^{\prime}\times\mathcal{A}\setminus\\{0\\}$

1:procedure Whittle($V^{\prime},\alpha\in\\{1,2\\},\upvarphi$)

2: $\lambda:=i\mapsto\begin{cases}0,&\text{if }i=-1\\\ \inf_{m}\\{m\mid
V_{m}(s_{t}^{i},a_{t}^{i}=0)\geq\\\ \hskip
42.67912ptV_{m}(s_{t}^{i},a_{t}^{i}=\alpha)\\},&\text{otherwise}\\\
\end{cases}$

3: return $W_{\alpha}\leftarrow\\{\lambda\circ\upvarphi^{-1}(v)\ |\ v\in
V^{\prime}\\}$

$\displaystyle V_{m}(s_{t}^{i})=\max\begin{cases}m+r(s_{t}^{i})+\beta
V_{m}\left(s_{t+1}^{i}\right)&\textit{no-act}\\\
\begin{array}[]{r@{}}r(s_{t}^{i})+\beta[s_{t}^{i}V_{m}\left(P^{\alpha}_{1,1}\right)+\\\
(1-s_{t}^{i})V_{m}\left(P^{\alpha}_{0,1}\right)]\end{array}&\textit{$\alpha$}\end{cases}$
(2)

The value function represents the maximum expected discounted reward that arm
$i\in[n]$ with state $s_{t}^{i}$ can receive at time $t$ given a subsidy $m$,
discount rate $\beta$, and active action $\alpha\in\\{1,2\\}$.

Greta: With our augmented graph and Whittle index values in hand, we now
present our algorithm. We provide pseudocode in Algorithm 2, and structure our
exposition sequentially. At each timestep $t\in T$, Greta takes as _input_ :
(1) an augmented set of restless arms, $[n]\cup\\{-1\\}$ embedded in an
augmented directed graph, $G^{\prime}=(V^{\prime},E^{\prime})$; (2) a budget,
$B\in\mathbb{R}$; (3) a cost function, $C:\mathcal{A}\rightarrow\mathbb{R}$;
(4) a message cost, $\psi\in[0,1)$; and (5) a set of Whittle index values per
active action $\alpha\in\\{1,2\\}$, denoted by $W_{1}$ and $W_{2}$,
respectively. Given these inputs, Greta _returns_ a reward-maximizing,
constraint-satisfying action vector, $\vec{a}_{t}$.

Algorithm 2 Greta: graph-aware, Whittle-based heuristic
Note: all sorts are descending; arrays are zero-indexed.

1:procedure Greta($G^{\prime},V^{\prime},E^{\prime},B,C,\psi,W_{1},W_{2}$)

2: $\vec{a}_{t}\leftarrow 0^{|V|}$

3: $B^{\prime}\leftarrow B$

4: while $\vee_{e\in E^{\prime}}$ GetCost($u,v,\vec{a}_{t},C$) $\leq
B^{\prime}\land E^{\prime}\neq\emptyset$ do

5: b $\leftarrow\min(B^{\prime},2)$

6: $\triangleright$ Consider only pulls

7: $\hat{a}_{2},\nu_{2}\leftarrow$
PullOnly($E^{\prime},\lfloor{\texttt{b}\rfloor},W_{2}$)

8: $\triangleright$ Consider pulls _and_ messages

9: $\hat{a}_{(1,2)},\nu_{(1,2)},E^{\prime}_{\oslash}\leftarrow$
MP($G^{\prime},\texttt{b},C,\psi,\vec{a}_{t},W_{1},W_{2}$)

10: $\triangleright$ Select max-val candidate actions; update
$\vec{a}_{t},B^{\prime},G^{\prime}$

11: if $\nu_{2}\geq\nu_{(1,2)}$ then

12: $\vec{a}_{t},B^{\prime}\leftarrow$
ModActsB($G^{\prime},C,\hat{a}_{2},\vec{a}_{t},B^{\prime}$)

13: $E^{\prime},G^{\prime}\leftarrow$
UpdateG($V^{\prime},E^{\prime},\hat{a}_{2},\emptyset$)

14: else

15: $\vec{a}_{t},B^{\prime},\leftarrow$
ModActsB($G^{\prime},C,\hat{a}_{(1,2)},\vec{a}_{t},B^{\prime}$)

16: $E^{\prime},G^{\prime}\leftarrow$
UpdateG($V^{\prime},E^{\prime},\hat{a}_{(1,2)},E^{\prime}_{\oslash}$)

17: return $\vec{a}_{t}$

In lines 2-3 of Algorithm 2, we initialize $\vec{a}_{t}$ such that each vertex
is mapped to 0 (no-act), and set our _remaining budget_ variable,
$B^{\prime}$, equal to the per-timestep budget, $B$.

In lines 4-13, we iteratively update our action vector $\vec{a}_{t}$ until we
have insufficient remaining budget to afford any available edge-action pair,
or our augmented edge set, $E^{\prime}=~{}\emptyset$. The termination check in
line 4 requires us to: (1) check if we’ve already incurred the cost of a
_pull_ or _message_ (_message_) for vertex $u$ ($v$); and (2) offset
accordingly when we compute the cost of $(a_{t}^{u}=2,a_{t}^{v}=1)$, per Alg.
3.

Algorithm 3 Compute cost to pull $u$ and message $v$

1:procedure GetCost($u,v,\vec{a}_{t},C$)

2: $c_{u}\leftarrow
C(2)(1-\mathds{1}(a^{u}_{t}>0))+\mathds{1}(a^{u}_{t}=1)(C(2)-C(1))$

3: $c_{v}\leftarrow C(1)(1-\mathds{1}(a^{v}_{t}=1\lor v=-1))$

4:return $c_{u}+c_{v}$

The subroutines called in lines 6-7 of Greta serve to ensure that we will only
deviate from the pull-assignment choices of graph-agnostic Threshold
Whittle—i.e., by considering a combination of pulls _and_ messages—when it is
strictly beneficial to do so.

Since pulls have unit cost, and $\psi\in[0,1)$, we consider our per-timestep
budget in sequential chunks of 2. We have two options for allocating each
chunk over actions: (1) considering _only_ pulls, and selecting the two arms
with highest $W_{2}$ index values; or (2) considering messages _and_ pulls,
and selecting the set of directed $(u,v)$ edges with highest edge-level
subsidies such that each $u$ receives a pull, and each $v$ (excluding $-1$)
receives a message. In lines 8-13, we select the candidate action set with the
highest cumulative subsidy, and update $\vec{a}_{t},B^{\prime},\text{ and
}G^{\prime}$ accordingly.

Pulls only: Allocation option (1) maps arms who have yet to receive a pull at
time $t$ to candidate actions $\in\\{0,2\\}$ by sorting their $W_{2}$ index
values in descending order and selecting the top-2 arms to receive pulls. App.
A.1 gives pseudocode (Alg 7).

Messages _and_ pulls: Allocation option (2) maps arms to candidate actions by
computing an edge index value for each directed edge $\in E^{\prime}$.
Algorithm 4 provides pseudocode.

Algorithm 4 Cumulative subsidy of max pull-message set
Note: all sorts are descending; arrays are zero-indexed.

1:procedure
MP($G^{\prime},\texttt{b}\in\mathbb{R},C,\psi,\vec{a}_{t},W_{1},W_{2}$)

2:
$G^{\operatorname*{\prime\prime}}=(V^{\operatorname*{\prime\prime}},E^{\operatorname*{\prime\prime}})\leftarrow
G^{\prime}$

3: $\hat{a}_{(1,2)}:v\in
V^{\operatorname*{\prime\prime}}\mapsto\vec{a}_{t}^{v}$

4: $f:(u,v)\in E^{\operatorname*{\prime\prime}}\mapsto\mathbb{R}$

5: $E^{\prime}_{\oslash}\leftarrow\emptyset$

6: $\nu_{(1,2)}\leftarrow 0$

7: while $\vee_{e\in E^{\operatorname*{\prime\prime}}}$
GetCost($u,v,\hat{a},C$) $\leq\texttt{b}\land
E^{\operatorname*{\prime\prime}}\neq\emptyset$ do

8: for $u\in V^{\operatorname*{\prime\prime}}\setminus\\{-1\\}$ do

9: ${\cal N}_{\text{out}}^{\prime}(u)\leftarrow\left\\{v|(u,v)\in
E^{\operatorname*{\prime\prime}}\land\hat{a}_{(1,2)}^{v}=0\right\\}$

10: EdgeIndices($f^{\operatorname*{\prime\prime}},u,{\cal
N}_{\text{out}}^{\prime}(u),\texttt{b},\psi,W_{1},W_{2}$)

11: values $\leftarrow\textsc{sort}(\\{f((u,v))|(u,v)\in
E^{\operatorname*{\prime\prime}}\\})$

12: if $|\texttt{values}|=0$ then

13: break

14: for $f((u,v))\in\texttt{values}$ do

15: cost${}_{u,v}\leftarrow$ ComputeCost($u,v,\hat{a}_{(1,2)},C$)

16: if cost${}_{u,v}\leq\texttt{b}$ then

17: $h:u\mapsto 2;v\mapsto 1$

18: $\hat{a}_{(1,2)},\texttt{b}\leftarrow$
ModActsB($G^{\operatorname*{\prime\prime}},C,h,\hat{a}_{(1,2)},\texttt{b}$)

19:
$E^{\operatorname*{\prime\prime}},G^{\operatorname*{\prime\prime}}\leftarrow$
UpdateG($V^{\operatorname*{\prime\prime}},E^{\operatorname*{\prime\prime}},\hat{a}_{(1,2)},\emptyset$)

20: $\nu_{(1,2)}\mathrel{{+}{=}}f((u,v))$

21: $E^{\prime}_{\oslash}\leftarrow E^{\prime}_{\oslash}\cup\\{(u,v)\\}$

22: break

23: $\triangleright$ Return best arm-actions, cumulative subsidy,
$E^{\prime}_{\oslash}$

24: return $\hat{a}_{(1,2)},\nu_{(1,2)},E^{\prime}_{\oslash}$

In line 2 of Algorithm 4, we start by defining
$G^{\operatorname*{\prime\prime}}$ to be a local copy of our augmented graph,
$G^{\prime}$. We then create a function, $\vec{a}_{(1,2)}$ to map each vertex
$v\in V^{\operatorname*{\prime\prime}}$ to its candidate action, which we
initialize to be $\vec{a}_{t}^{v}$ (line 3). We do this because we require the
current $G^{\prime}$ to determine which
$(\texttt{pull}_{u},\texttt{message}_{v})$ edge-action combinations are
possible, and for $\vec{a}_{t}$ to correctly compute the cost of these
hypothetical actions, but we don’t want to modify $\vec{a}_{t}$ or
$G^{\prime}$ in-place. Next, in lines 4-5, we define a function, $f$ that maps
each edge $(u,v)\in E^{\prime}$ to a real-valued edge index value, and a set,
$E^{\prime}_{\oslash}$, to hold the edges we will need to remove from
$G^{\prime}$ if we select the candidate actions returned by Algorithm 4. In
line 6, we initialize $\nu_{(1,2)}=0$ to represent the cumulative subsidy of
our candidate action set.

In lines 7-22 of Algorithm 4, we iteratively update our candidate action
function, $\hat{a}_{(1,2)}$, until we run out of (small-b) budget, or
$E^{\operatorname*{\prime\prime}}=\emptyset$. Inside each iteration of the
while-loop, we begin by computing an edge index value for each directed edge
$(u,v)\in E^{\prime}$ (lines 8-10). To do this, we loop over vertices in
$V^{\prime}\setminus\\{-1\\}$ (line 8), and for each vertex $u$, let ${\cal
N}_{\text{out}}^{\prime}(u)\subseteq{\cal N}_{\text{out}}(u)$ represent the
subset of $u$’s one-hop out-degree neighbors currently slated to receive a no-
act at time $t$.

For each edge $(u,v)\in{\cal N}_{\text{out}}^{\prime}(u)$, our edge index
value represents the cumulative subsidy required to forgo a _pull_ for arm $u$
(i.e., $W_{2}^{u}$) and a _message_ for arm $v$ (i.e., $W_{1}^{v}$). Note: if
we pull $u$, message $v$, and have budget left over, we can message up to
$|\mathcal{M}^{u}_{t}|$ vertices $v^{\prime}\in{\cal
N}_{\text{out}}^{\prime}(u)$ at time $t$ _without_ incurring additional pull
costs, where $|\mathcal{M}^{u}_{t}|=|{\cal N}_{\text{out}}^{\prime}(u)|$ if
$\psi=0$ and $\min(\lfloor{\nicefrac{{\texttt{b}}}{{\psi}}\rfloor},|{\cal
N}_{\text{out}}^{\prime}(u)|)\text{ for }\psi\in(0,1)$.

To exploit this diminishing marginal cost, we sort $u$’s, neighbors by their
index-values and let the max-valued edge represent the cumulative, cost-
feasible value of ${\cal N}_{\text{out}}^{\prime}(u)$, rather than just
$(u,v)$. Algorithm 5 provides pseudocode.

Algorithm 5 Compute edge index values
Note: all sorts are descending; arrays are zero-indexed.

1:procedure EdgeIndices($f,u,{\cal
N}_{\text{out}}^{\prime}(u),\texttt{b},\psi,W_{2},W_{1}$)

2: n_msgs$\leftarrow|{\cal N}_{\text{out}}^{\prime}(u)|$ if $\psi=0$ else
$\min(\lfloor{\nicefrac{{\texttt{b}}}{{\psi}}\rfloor},|{\cal
N}_{\text{out}}^{\prime}(u)|)$

3: $\texttt{msg\\_values}\leftarrow\textsc{sort}(g:v\in{\cal
N}_{\text{out}}^{\prime}(u)\mapsto W_{1}^{v})$

4: max_edge $\leftarrow(u,\operatorname*{arg\,max}_{v}\texttt{msg\\_values})$

5: for $v\in{\cal N}_{\text{out}}^{\prime}(u)$ do

6: if $(u,v)=$ max_edge then

7: $f((u,v))\leftarrow
W_{2}^{u}+\sum_{i=0}^{\texttt{n\\_msgs}-1}\texttt{msg\\_values}_{i}$

8: else

9: $f((u,v))\leftarrow W_{2}^{u}+W_{1}^{v}$

10: return $\triangleright$ $f$ is updated in-place

Then, in lines 11-13 of Algorithm 4, we sort the edge-index values in
descending order. Note that we break if there are no values to be sorted; this
corresponds to the scenario in which no additional pulls are available/cost-
feasible, and every arm not receiving a pull is already receiving a message,
but we still have budget left—i.e., when $\psi=0$. In lines 14-22, we choose
the top cost-feasible edge-action pair from our sorted list, and update our
candidate action function, $\vec{a}_{(1,2)}$ and local budget, b accordingly.
Note that if $\psi=0$ and arm $u$ receives a pull, we message every $v\in{\cal
N}_{\text{out}}^{\prime}(u)$. App. A.1 provides pseudocode for the ModActsB
subroutine (see Algorithm 8 in Appendix A.1).

Finally, we update our local copy of the augmented graph by removing $(u,v)$,
as well as any directed edge terminating in $u$, and the placeholder edge,
$(u,-1)$. This is because: (a) we do not want to reconsider the edge-action
pair we’ve selected; and (b) by virtue of how we select $(u,v)$, $f((u,v))\geq
f((\cdot,u))$ _or_ any such $u$-terminating edge is cost-prohibitive. App. A.1
provides pseudocode for the UpdateG subroutine (see Algorithm 9). We conclude
the MP subroutine (Algorithm 4) by returning our candidate action function,
$\hat{a}_{(1,2)}$, the associated cumulative subsidy value, $\nu_{(1,2)}$, and
the set of candidate edges to be removed from
$G^{\prime},E^{\prime}_{\oslash}$.

Putting the pieces together: With the exposition of each of Greta’s
subroutines complete, we now return to lines 8-13 of Algorithm 2. We compare
the cumulative subsidy values returned by the PullOnly and MP subroutines, and
use the candidate action function associated with the maximum cumulative
subsidy to update our action vector, $\vec{a}_{t}$, remaining budget,
$B^{\prime}$, and augmented graph, $G^{\prime}$. When the while-loop
terminates, we return $\vec{a}_{t}$. By virtue of how this action vector is
constructed, it is reward-maximizing and guaranteed to satisfy the budget
constraint.

###  3.2 Theoretical Analysis

Bounding expected reward: Per Theorem 3.1, the expected cumulative reward of
Greta with message cost, $\psi>0$, will be lower-bounded by that of graph-
agnostic Threshold Whittle, and upper-bounded by Greta with $\psi=0$. See
Appendix A.2 for a complete proof.

######  Theorem 3.1.

For a given set of $[n]$ restless or collapsing arms with transition matrices
satisfying the structural constraints outlined in Section 2.3, corresponding
directed graph, $G=(V,E)$, budget $B\in\mathbb{R}_{\geq 0}$, non-decreasing
local reward function, $r:\mathcal{S}\rightarrow\mathbb{R}$, cumulative reward
function, $R$, and cost vector $\vec{c}=[0,\psi,1]$ such that $\psi\in[0,1)$,
we have:
$\mathbb{E}_{\textsc{TW}}[R]\leq\mathbb{E}_{\textsc{GH},\psi>0}[R]\leq\mathbb{E}_{\textsc{GH},\psi=0}[R]$

###### Proof Sketch.

The _first inequality_ follows from how Greta constructs each $\vec{a}_{t}$.
The _second inequality_ follows from the fact that: (a) per our structural
constraints and choice of $r$, $E[r^{i}_{t}|s^{i}_{t},a^{i}_{t}]$ is strictly
increasing with $a^{i}_{t}\ \forall i,t$; and (b) for $\psi=0$, we can message
at least as many arms as when $\psi>0$. ∎

Computational complexity: Per Theorem 3.2, Greta is efficiently computable in
time polynomial in its inputs; see Appendix A.2 for a complete proof.

######  Theorem 3.2.

For convenience, let:
$\xi=\mathds{1}(\psi>0)\times\min(|E^{\prime}|^{2},\lfloor{\frac{B}{\psi}\rfloor}|E^{\prime}|)+\mathds{1}(\psi=0)\times~{}|V^{\prime}||E^{\prime}|$.
Then, for $\psi\in[0,1)$ and time horizon, $T$, the time complexity of Greta
is:

$\begin{cases}O\left(\max\left(\xi^{2}|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi^{2}|V^{\prime}||E^{\prime}|^{2}\right)T\right),\quad\text{if $\psi>0$}\\\
O\left(\max\left(\xi^{2}|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi^{2}|V^{\prime}||E^{\prime}|^{2},\
\xi^{2}|V^{\prime}|^{2}|E^{\prime}|\right)T\right),\\\
\quad\text{otherwise}\end{cases}$

These bounds indicate that Greta is well-suited for sparse graphs and values
of $\psi=0$ or $\psi\rightarrow 0.5$ ($\psi>0.5$ will also improve runtime,
but may reduce opportunities to exploit externalities). Conversely,
pathological cases will include large-scale dense graphs and values of the
message cost, $\psi$, which approach but do not equal 0. We consider improving
scale to be a valuable direction for future work. The combinatorial nature of
the problem we consider suggests that sampling and/or distributed methods will
be critical in this regard (Zhou et al. 2020; Almasan et al. 2022).

##  4 Experimental Evaluation

In this section, we demonstrate that Greta consistently outperforms a set of
robust graph-agnostic and graph-aware comparison policies. We begin by
identifying the set of policies we compare against, as well as our evaluation
metrics, graph generation, and mapping of arms to vertices. We proceed to
present results from three experiments: (1) Greta versus the optimal policy
(for small $n$); (2) Greta versus comparison policies for a fixed cohort and
graph; and (3) Greta evaluated on a series of different budgets, message
costs, and graph topologies.

###  4.1 Experimental Setup

Policies: In our experiments, we compare the policy produced by Greta against
a subset of the following graph-$\\{$agnostic⊘ and aware${}^{\dagger}\\}$
policies:

| Threshold
---
Whittle (TW)⊘
| Compute Whittle index values using pull as (only) active
---
action. Pull $\lfloor{B\rfloor}$ arms with highest Whittle index values;
all others get no-act (Whittle 1988; Mate et al. 2020).
| Random†
---
| Construct $G^{\prime}$; select budget-feasible edge-action pairs
---
uniformly at random until budget exhausted.
| Centrality-
---
weighted Random†
| Construct $G^{\prime}$; select budget-feasible edge-action pairs
---
weighted by out-degree centrality of src vertex until
budget exhausted.
| Myopic†
---
| Construct $G^{\prime}$; sort edge-action pairs by expected reward
---
at $t+1$. Select cost-feasible pairs until budget exhausted.
| Value
---
Iteration (VI)†
| Find the optimal policy via value iteration for _system-level_
---
MDP (intractable at scale, but computable for small $|V|$ and $|E|$).

Table 1: Comparison policies

We note that in the restless (but graph-agnostic) setting: (1) Random and
Myopic are common baselines. Here, we have extended them to the networked
setting. (2) Threshold Whittle represents a state-of-the-art approach. To the
best of our knowledge, no additional (efficiently computable) graph-aware
policies exist for the novel networked restless bandit setting we propose.

Objective: Our optimization task is consistent with assigning equal value to
each timestep that any arm spends in the “desirable” state. This motivates our
choice of a local reward function $r_{t}(s_{t}^{t})\coloneqq
s_{t}^{i}\in\\{0,1\\}$ and undiscounted cumulative reward function
${R}(r(s))~{}\coloneqq~{}\sum_{i\in[N]}\sum_{t\in[T]}~{}r(s^{i}_{t})$.

_Intervention benefit (IB)_ : For each policy, we compute total expected
reward, $\mathbb{E}_{\pi}[R(\cdot)]$, by taking the average over 50 simulation
seeds. We then compute the intervention benefit as defined in Equation 3,
where NoAct represents a policy in which no pulls or messages are executed,
and GH represents the policy produced by Greta.

$\textsc{IB}_{\text{NoAct},\text{GH}}(\pi)\coloneqq\frac{\mathbb{E}_{\pi}[R_{\pi}(\cdot)]-\mathbb{E}_{\text{NoAct}}[R(\cdot)]}{\mathbb{E}_{\text{GH}}[R(\cdot)]-\mathbb{E}_{\text{NoAct}}[R(\cdot)]}$
(3)

Graph generation: For each cohort of $n$ restless arms that we consider in our
experiments, we use a stochastic block model (SBM) to generate a graph with
$|V|=n$ vertices (Holland, Laskey, and Leinhardt 1983). This generator
partitions the vertices into blocks and stochastically inserts directed edges,
with hyperparameter $p_{in}(p_{out})\in[0,1]$ controlling the probability that
a directed edge will exist between two vertices in the same (different)
block(s).

We consider two options for $\upvarphi:[n]\rightarrow V$: (1) _random_ ; and
(2) _by cluster_. For mapping (1), we generate $\lceil{\frac{n}{10}\rceil}$
blocks of uniform size, and map arms to vertices—and, by extension, to
blocks—uniformly at random. This mapping represents allocation settings with a
peer support component where participants are randomly assigned to groups,
without regard for their behavioral similarity.

For mapping (2), we use an off-the-shelf k-means algorithm to cluster the arms
in flattened transition-matrix vector space (Pedregosa et al. 2011). We use
the cardinality of the resulting clusters to determine the size of each block
and map arms to vertices based on cluster membership. This mapping represents
intervention allocation settings with a peer support component where
participants with similar transition dynamics are grouped together.

###  4.2 Greta vs. the Optimal Policy

In this experiment, we compare Greta to $\pi^{*}_{\text{VI}}$, where
$\pi^{*}_{\text{VI}}$ denotes the optimal policy obtained via value iteration
for the _system-level_ MDP (Sutton and Barto 2018). This system-level MDP has
state space $\mathcal{S}^{\prime}:=\\{\mathcal{S}\\}^{n}$, action space
$\mathcal{A}^{\prime}:=\\{\mathcal{A}\\}^{n}$, a transition function,
$P:\mathcal{S}^{\prime}\times\mathcal{A}^{\prime}\rightarrow\mathcal{S}^{\prime}$,
and reward function, $R^{\prime}=\sum_{i\in[n]}s^{i}$. To ensure budget and
neighborhood constraint satisfaction, only cost- and topologically feasible
actions,
$\mathcal{A}^{\operatorname*{\prime\prime}}\subseteq\mathcal{A}^{\prime}$ are
considered. Figure 1 reports results for a synthetic cohort of 8 arms embedded
in a fully connected graph (i.e., $p_{\text{in}}=p_{\text{out}}=1.0$). We let
$T=120,\psi=0.5$, and report unnormalized $\mathbb{E}_{\pi}[R]$, along with
margins of error for 95% confidence intervals computed over 50 simulation
seeds for values of $B\in\\{1,1.5,2,2.5,3\\}$. Greta outperforms TW for each
value of $B$ (with predictably larger gaps for values with remainders $=\psi$
that graph-agnostic TW cannot exploit), and is competitive with respect to
$\pi^{*}_{\text{VI}}$.

Figure 1: $\mathbb{E}[R]$ by policy and budget

###  4.3 Greta vs. Alternative Policies

Here we compare Greta to the graph-agnostic and graph-aware comparison
policies outlined in Section 4.1. We consider a synthetic cohort of $n=100$
restless arms whose transition matrices are randomly generated in such a way
so as to satisfy the structural constraints introduced in Section 2. We use a
stochastic block model (SBM) generator with $p_{in}=0.2$ and $p_{out}=0.05$,
and consider both the _random_ and _by cluster_ options for $\upvarphi$. We
let $T=120$, $B=10$, and $\psi=0.5$.

In Table 2, we report results for each mapping-policy combination, along with
margins of error for 95% confidence intervals computed over 50 simulation
seeds.

$\upvarphi(i)$ | Policy  |  $\mathbb{E}[\textsc{IB}]$ (%) ($\pm$)
---|---|---
randomly |  Random | 75.82 $\pm$ 0.890
CWRandom | 74.79 $\pm$ 1.068
Myopic | 87.83 $\pm$ 1.115
TW | 83.57 $\pm$ 0.779
Greta | 100.00 $\pm$ 0.000
by cluster |  Random | 64.19 $\pm$ 0.786
CWRandom | 63.59 $\pm$ 0.804
Myopic | 76.24 $\pm$ 0.921
TW | 72.65 $\pm$ 0.684
Greta | 100.00 $\pm$ 0.000

Table 2: $\mathbb{E}[\text{IB}]$ by choice of $\upvarphi$ and policy

Key findings from this experiment include:

  * •

The policy produced by Greta achieves significantly higher
$\mathbb{E}_{\pi}[\text{IB}]$ than each of the comparisons.

  * •

The gap in $\mathbb{E}_{\pi}[\text{IB}]$ between Greta and Myopic, which is
the best-performing alternative, is larger for the _by cluster_ mapping than
the _random_ mapping. This suggests that in assortative networks, relatively
homogeneous transition dynamics within blocks facilitate the exploitation of
the diminishing marginal costs associated with the pull-message dynamic.

###  4.4 Sensitivity Analysis

We conduct sensitivity analysis with respect to: (1) the budget, $B$; (2) the
message cost, $\psi$; and (3) the underlying graph topology, via the
$p_{\text{in}}$ and $p_{\text{out}}$ hyperparameters of our stochastic block
model graph generator. As we vary each of the aforementioned hyperparameters,
we consider a fixed cohort size of $n=100$ randomly-generated, structural
constraint-satisfying arms, a time horizon, $T=120$, and a mapping
$\upvarphi:i\in[n]\mapsto v\in V$ from arms to vertices that is determined by
cluster. We report unnormalized $\mathbb{E}_{\pi}[R]$, along with margins of
error for 95% confidence intervals computed over 50 simulation seeds, for
Greta, Threshold Whittle, NoAct, and Myopic, which is the best-performing non-
TW alternative. We describe each task below, and present results in Figure 2.

Figure 2: Sensitivity results, by varied hyperparameter

Budget: We hold message cost fixed at $\psi=0.5$, let $p_{\text{in}}=0.25$,
$p_{\text{out}}=0.05$, and consider values of $B\in\\{5\%,10\%,15\%\\}\text{
of }~{}n$. As Figure 2(a) illustrates, $\mathbb{E}_{\pi}[R]$ intuitively rises
with $B$ for each policy considered. For each value of $B$, we find that Greta
achieves higher $\mathbb{E}_{\pi}[R]$ than the comparison policies and that
the gap between Greta and the best-performing alternative also increases with
$B$.

Message cost: Here, we hold the budget fixed at $6$, let $p_{\text{in}}=0.25$,
$p_{\text{out}}=0.05$, and consider values of
$\psi~{}\in~{}\\{0.0,0.25,0.5,0.75,0.9\\}$. As Figure 2(b) illustrates,
$\mathbb{E}_{\pi}[R]$ decreases as the message cost, $\psi$, increases for
Greta and Myopic, while it remains constant for active-action agnostic NoAct
and message-agnostic TW. For each value of $\psi$ that we consider, Greta
achieves higher $\mathbb{E}_{\pi}[R]$ than each of the comparison policies.
This gap is intuitively largest when $\psi=0$, and decreases until Greta
converges with TW—notably, without suffering loss in total expected reward due
to divisibility issues with respect to $B$, when $\psi=0.75$.

Graph topology: We hold the budget fixed at $B=10$, let message cost,
$\psi=0.5$, and consider two sets of increasingly _assortative_
(_disassortative_) $(p_{\text{in}}$, $p_{\text{out}})$ ordered pairs. In each
case, we start with $E=\emptyset$—i.e., $(0.0,0.0)$, and then hold
$p_{\text{out}}$ ($p_{\text{in}}$) fixed at $0.1$ and steadily increase
$p_{\text{in}}$ ($p_{\text{out}}$). Figure 2(c) and (d) present results. For
Greta, while $\mathbb{E}_{\pi}[R]$ is generally increasing in the number of
edges, the rate of growth levels off as assortativity rises but remains robust
as disassortativity rises. This suggests that homophilic clustering of arms
with respect to transition dynamics may undermine total welfare by inducing
competition within neighborhoods, while heterophilic clustering can help to
smooth out subgroups’ relative demand for constrained resources over time.

##  5 Conclusion & Future Work

In this paper, we introduce networked restless bandits, a novel multi-armed
bandit setting in which arms are restless and embedded in a directed graph. We
show that this framework can be used to model constrained resource allocation
in community settings, where receipt of the resource by an individual can
result in spillover effects that benefit their neighbor(s). We also present
Greta, a graph-aware, Whittle-based heuristic algorithm which is constrained
reward-maximizing and budget-constraint satisfying in our networked restless
bandit setting. Our empirical results demonstrate that the policy produced by
Greta outperforms a set of graph-agnostic and graph-aware comparison policies
for a range of different budgets, message costs, and graph topologies. Future
directions include: (1) relaxing the assumption of perfect observability of
transition matrices and/or graph topology; (2) considering individual and/or
group fairness; and (3) incorporating sampling and/or distributed methods to
improve scalability.

##  Appendix A Heuristic Policy

In this section, we provide additional details related to the heuristic policy
we introduce in Section 3, including pseudocode for subroutines and complete
proofs for theorems.

###  A.1 Pseudocode

#### Construct $G^{\prime}$

Recall from Section 3.1 that Greta takes as input a pre-constructed augmented
graph, $G^{\prime}=(V^{\prime},E^{\prime})$, where $V^{\prime}$ and
$E^{\prime}$ represent augmented vertex and edge sets, respectively (Alg. 2,
line 1). Algorithm 6 provides pseudocode for the construction of this
augmented graph:

Algorithm 6 Construct $G^{\prime}$

1:procedure Construct($V,E$)

2: $V^{\prime}\leftarrow V\cup\\{-1\\}$

3: $E^{\prime}\leftarrow E\cup\\{(u,-1)|u\in V\\}$

4: $G^{\prime}=(V^{\prime},E^{\prime})$

5: return $V^{\prime},E^{\prime},G^{\prime}$

The figure below visually represents this process for an example graph, $G$,
and corresponding augmented graph, $G^{\prime}$:

####  PullOnly subroutine

Here we present pseudocode for the PullOnly subroutine called in line 6 of
Greta (Algorithm 2).

Algorithm 7 Cumulative subsidy of top-2 arms (pulls)
Note: all sorts are descending; arrays are zero-indexed.

1:procedure PullOnly($E^{\prime},\texttt{b}\in\mathbb{N},W_{2}$)

2: $V^{\prime}_{2}\leftarrow\\{u\ |\ (u,v)\in E^{\prime}\land v=-1\\}$

3: $\texttt{b}\leftarrow\min(|V^{\prime}_{2}|,\texttt{b})$

4: $\texttt{pull\\_vals}\leftarrow\textsc{sort}(g:u\in
V^{\prime}_{2}\mapsto(u,W_{2}^{u}))$

5: $\hat{a}_{2}:u\in\pi_{\ell}(\texttt{pull\\_vals[:b]})\mapsto 2$

6: $\nu_{2}\leftarrow\sum_{i=0}^{\texttt{b}}\pi_{r}(\texttt{pull\\_vals}_{i})$

7:

8: $\triangleright$ Return top-b arm-actions and their cumulative subsidy

9: return $\hat{a}_{2},\nu_{2}$

####  ModActsB subroutine

Here we present pseudocode for the ModActsB subroutine called in line 9 or 12
(depending on the if/else in line 8) of Greta (Algorithm 2), as well as in
line 18 of the MP subroutine (Algorithm 4).

Algorithm 8 Update $\vec{a}_{t}$ and budget per max-value action(s)

1:procedure ModActsB($G^{\prime},C,\hat{a}^{*},\vec{a}_{t},B^{\prime}$)

2: $\triangleright$ For every vertex $u$ with an updated action:

3: for $u\in\operatorname{dom}(\hat{a}^{*})$ do

4: if $\hat{a}^{*}(u)=1$ then

5: $\triangleright$ New action is a message; update $\vec{a}_{t},B^{\prime}$

6: $B^{\prime}\mathrel{{-}{=}}C(1)(1-\mathds{1}(\hat{a}^{*}(u)=1\lor u=-1))$

7: $\vec{a}_{t}^{u}\leftarrow 1$

8: else if $\hat{a}^{*}(u)=2$ then

9: $\triangleright$ New action is a pull; update $\vec{a}_{t},B^{\prime}$

10: $B^{\prime}\mathrel{{-}{=}}C(2)(1-\mathds{1}(\hat{a}^{*}(u)>0))+$

11: $\mathds{1}(\hat{a}^{*}(u)=1)(C(2)-C(1))$

12: $\vec{a}_{t}^{u}\leftarrow 2$

13: $\triangleright$ If $C(1)=0$, message every $v\in{\cal
N}_{\text{out}}^{\prime}(u)$

14: if $\psi=0$ then

15: for $v\in{\cal N}_{\text{out}}^{\prime}(u)$ do

16: $\vec{a}_{t}^{v}\leftarrow\max(\vec{a}_{t}^{v},1)$

17: return $\vec{a}_{t},B^{\prime}$

####  UpdateG subroutine

Algorithm 9 Update $E^{\prime}\text{ and }G^{\prime}$

1:procedure
UpdateGraph($V^{\prime},E^{\prime},\hat{a}^{*},E^{\prime}_{\oslash}$)

2: for $u\in\operatorname{dom}(\hat{a}^{*})$ do

3: if $\hat{a}^{*}(u)=2$ then

4: $E^{\prime}_{\oslash}\leftarrow
E^{\prime}_{\oslash}\cup\\{e_{s,t}|e_{s,t}\in E^{\prime}\land$

5: $\left(t=u\lor(s=u\land t=-1)\right)\\}$

6: $E^{\prime}\leftarrow E^{\prime}\setminus E^{\prime}_{\oslash}$

7: return $E^{\prime},G^{\prime}=(V^{\prime},E^{\prime})$

###  A.2 Proofs

#### Bounding expected reward

Here, we begin with Remark A.1, and proceed to prove Theorem 3.1 (restated for
convenience below).

######  Remark A.1.

For any restless arm $i\in[n]$ whose transition matrix entries satisfy the
structural constraints introduced in Section 2.3, action space
$\mathcal{A}:=\\{0:\texttt{no-act},1:\texttt{message},2:\texttt{pull}\\}$, and
non-decreasing local reward function,
$r:~{}\mathcal{S}~{}\rightarrow~{}\mathbb{R}$, we have:

$\forall(a,a^{\prime})\in\mathcal{A}\times\mathcal{A},a<a^{\prime}\rightarrow\mathbb{E}[r^{i}_{t}|s^{i}_{t},a_{t}]<\mathbb{E}[r^{i}_{t}|s^{i}_{t},a^{\prime}_{t}]$

See 3.1

###### Proof.

The _first inequality_ ,
$\mathbb{E}_{\textsc{TW}}[R]\leq\mathbb{E}_{\textsc{GH},\psi>0}[R]$, follows
directly from how Greta constructs each $\vec{a}_{t}$. Greta’s PullOnly
subroutine (Algorithm 7) computes candidate action vector $\hat{a}_{2}$, which
represents the actions we would take when following graph-agnostic TW for each
budget chunk, $\texttt{b}\leftarrow\min(B^{\prime},2)$.

Since we do not execute $\vec{a}_{t}$ until we are finished constructing
it—i.e., until we have run out of budget or edges, per the while-loop
termination logic in line 8 of Algorithm 2, the arms’ states don’t change from
while loop iteration $i$ to $i+1$. Thus, per the inequality on line 11, Greta
will return the same mapping from arms to actions as that returned by graph-
agnostic TW with $k=\lfloor{B\rfloor}$ if
$\bigwedge_{i}\mathds{1}(\nu_{2}^{i,(\cdot)}\geq\nu_{(1,2)}^{i,(\cdot)})$, and
a mapping containing pulls and at least one message otherwise—i.e., when it is
strictly advantageous to do so.

The _second inequality_ ,
$\mathbb{E}_{\textsc{GH},\psi>0}[R]\leq\mathbb{E}_{\textsc{GH},\psi=0}[R]$,
follows directly from Remark A.1 and the fact that when $\psi=0$, we can
message at least as many arms as we can when $\psi>0$. Let
$\mathcal{M}^{u}_{t}$ represent the set of _potential_ messages that is
“unlocked” when a given node $u$ receives a pull at time $t$. The cardinality
of $\mathcal{M}^{u}_{t}$ can be bound as follows:

$|\mathcal{M}^{u}_{t}|=\begin{cases}|{\cal
N}_{\text{out}}^{\prime}(u)|,&\text{if $\psi=0$}\\\
\min(\lfloor{\nicefrac{{\texttt{b}}}{{\psi}}\rfloor},|{\cal
N}_{\text{out}}^{\prime}(u)|),&\psi>0\end{cases}$ (4)

This is because when $\psi=0$, for each node $u$ that we pull at time $t$, we
message _every_ one-hop outdegree neighbor $v\in{\cal
N}_{\text{out}}^{\prime}(u)$ that has not already received a pull or message
at time $t$ (see Algorithm 8, lines 10-12). In contrast, when $\psi>0$, we
must take the budget constraint into account.

The original claim follows from the transitive property. ∎

#### Computational complexity

Here, we prove that Greta is efficiently computable in time polynomial in its
inputs. We begin by introducing several lemmas related to the runtime of
Greta’s subroutines, and then proceed to prove Theorem 3.2 (restated for
convenience below, immediately preceding its corresponding proof).

######  Remark A.2.

The Construct subroutine (Algorithm 6) used to construct the augmented graph,
$G^{\prime}$ , has computational complexity $O(|V|)$, since we insert the
dummy vertex, $-1$, and a directed edge $(u,-1)$ for each $u\in V$.

######  Lemma A.3.

Using graph-agnostic Threshold Whittle to pre-compute the Whittle index for
each vertex-active action combination $(v,\alpha)\in
V^{\prime}\times\mathcal{A}\setminus\\{0\\}$ has time complexity
$O(|V||\mathcal{A}||\mathcal{S}|^{2}T)$.

###### Proof.

Per Mate et al. (2020), Threshold Whittle has time complexity $O(|S|^{2}T)$
per arm-active action. There are $N=|V|$ arms and
$|\mathcal{A}\setminus\\{0\\}|$ active actions. Thus, Algorithm 1 has time
complexity $O(|V||\mathcal{A}||\mathcal{S}|^{2}T)$. ∎

######  Lemma A.4.

The PullOnly subroutine (Algorithm 7) has time complexity
$O(|V^{\prime}|\log|V^{\prime}|)$.

###### Proof.

Line 2 of Algorithm 7 has cost $O(|V^{\prime}|)$. Lines 3, 5, and 6 have cost
$O(1)$. The cost of this subroutine is thus dominated by the cost of sorting
the Whittle index values (line 4), which is $O(|V^{\prime}|\log|V^{\prime}|)$.
∎

######  Lemma A.5.

The EdgeIndices subroutine (Algorithm 5) has time complexity
$O(|V^{\prime}|\log|V^{\prime}|)$.

###### Proof.

Lines 2 and 4 of Algorithm 5 have time complexity $O(1)$. The for-loop on
lines 5-9 has time complexity $O(|V^{\prime}|)$, since in the worst case,
$|{\cal N}_{\text{out}}^{\prime}(u)|=|V^{\prime}|$. Thus, the time complexity
of this subroutine is dominated by the $O(|V^{\prime}|\log|V^{\prime}|)$ cost
of sorting the Whittle index values (line 3). ∎

######  Lemma A.6.

For $\psi\in[0,1)$, the ModActsB subroutine (Algorithm 8) has time complexity
$O(|V^{\prime}|)$ if $\psi>0$ and $O(|V^{\prime}|^{2})$ otherwise.

###### Proof.

In the for-loop contained in lines 2-12 of Algorithm 8, we iterate over each
vertex $u$ with an updated action (i.e., $\forall
u\in\operatorname{dom}{\hat{a}^{*}}$), with cost $O(|V^{\prime}|)$. In lines
3-9, we decrement our remaining budget, $B^{\prime}$, and update our candidate
action vector; each of these operations have time complexity $O(1)$. If
$\psi>0$, lines 10-12 are not executed. Conversely, if $\psi=0$, lines 10-12
_are_ executed, and we iterate over $u$’s one-hop, outdegree neighbors with
cost $O(|V^{\prime}|)$. Thus, the time complexity of this subroutine is
$O(|V^{\prime}|)$ if $\psi>0$ and $O(|V^{\prime}|^{2})$ otherwise. ∎

######  Lemma A.7.

The UpdateGraph subroutine (Algorithm 9) has time complexity
$O(|V^{\prime}||E^{\prime}|)$.

###### Proof.

In the for-loop contained in lines 2-5 of Algorithm 9, we iterate over each
vertex $u$ with an updated action (i.e., $\forall
u\in\operatorname{dom}{\hat{a}^{*}}$). Lines 4-5 and 6 each have cost
$O(|E^{\prime}|)$. Thus, the time complexity of this subroutine is
$O(|V^{\prime}||E^{\prime}|)$. ∎

######  Lemma A.8.

Let $\mathcal{W}_{MP}$ represent the number of while-loop iterations that
occur during any given call to the MsgPull subroutine (i.e., Algorithm 4,
lines 7-22). For $\psi\in[0,1)$, we can upper-bound $\mathcal{W}_{MP}$ as
follows:

$\begin{cases}O(\min(|E^{\prime}|,\lfloor{\frac{\texttt{b=2}}{\psi}\rfloor})),&\text{if
$\psi>0$}\\\ O(|V^{\prime}|),&\text{otherwise}\end{cases}$

###### Proof.

There are two cases: $\psi>0$ and $\psi=0$. We consider each below:

######  Case A.8.1.

$\psi>0$: For any given arm $i\in[n]$, and while-loop iteration $j>0$, let an
_action upgrade_ represent a modification to $\hat{a}_{(1,2)}$ such that
$\hat{a}_{(1,2)}^{(i,j)}>\hat{a}_{(1,2)}^{(i,j-1)}$. The small-b budget is
initialized $=2$, and is strictly decreasing in the number of action upgrades
when $\psi>0$. The worst case from a time complexity perspective will be when
our only upgrades are messages, since $C(\texttt{pull})>\psi\text{ for
}\psi\in[0,1)$—i.e., $\lfloor{\frac{\texttt{b=2}}{\psi}\rfloor}$ iterations.

Additionally, at each iteration we either: (a) have at least one cost-feasible
action upgrade, which results in the removal of at least one edge from
$E^{\operatorname*{\prime\prime}}$ when we call UpdateG in line 19 (note:
$E^{\operatorname*{\prime\prime}}$ is initialized in line 2 as a copy of
$E^{\prime}$, so it is always the case that
$|E^{\operatorname*{\prime\prime}}|\leq|E^{\prime}|$); or (b) do not have any
cost-feasible action upgrades remaining, in which case, the while-loop
terminates when we call GetCost in line 7. Thus, we can conduct at most
$\min(|E^{\prime}|,\lfloor{\frac{\texttt{b=2}}{\psi}\rfloor})$ iterations
before breaking.

######  Case A.8.2.

$\psi=0$: Each time we select to pull vertex $u$ in lines 14-22, we message
_every_ vertex $v\in{\cal N}_{\text{out}}^{\prime}(u)$ that is currently
slated to receive a no-act (i.e., when we call the ModActsB subroutine on line
18). The next time we encounter $u$ in the for-loop on line 8, the
construction of ${\cal N}_{\text{out}}^{\prime}(u)$ on line 9 will yield
$\emptyset$, since we include only neighbors for which $\hat{a}_{(1,2)}=0$.
This will hold for each vertex $\in V^{\operatorname*{\prime\prime}}$, so we
will break on line 13 after at most $O(|V^{\prime}|)$ iterations of the while-
loop.

∎

######  Lemma A.9.

For notational convenience, let
$\xi=\mathds{1}(\psi>0)\times\min(|E^{\prime}|^{2},\lfloor{\frac{\texttt{b=2}}{\psi}\rfloor}|E^{\prime}|)+\mathds{1}(\psi=0)\times|V^{\prime}||E^{\prime}|$.
For $\psi\in[0,1)$, the MsgPull subroutine (Algorithm 4) has time complexity
$O\left(\max\left(\xi|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi|V^{\prime}||E^{\prime}|^{2}\right)\right)$ if $\psi>0$, and
$O\left(\max\left(\xi|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi|V^{\prime}||E^{\prime}|^{2},\
\xi|E^{\prime}||V^{\prime}|^{2}\right)\right)$ otherwise.

###### Proof.

Regardless of the value of $\psi$, lines 2-6 of Algorithm 4 are dominated by
the cost of constructing $G^{\operatorname*{\prime\prime}}$ (line 2), which
has cost $O(|V^{\prime}|+|E^{\prime}|)$. The while-loop termination check we
perform in line 7 has time complexity $O(|E^{\prime}|)$ since we call GetCost
(Algorithm 3) for each edge $e\in E^{\operatorname*{\prime\prime}}$.

In the for-loop contained in lines 8-10, we loop over each vertex $v\in
V^{\operatorname*{\prime\prime}}$ (line 8; $O\left(|V^{\prime}|\right)$),
collect the one-hop, outdegree neighbors currently slated to receive a no-act
(line 9; $O\left(|E^{\prime}|\right)$), and then call EdgeIndices. Thus, per
Lemma A.5, the time complexity of lines 8-10 is
$O\left(\max\left(|V^{\prime}|^{2}\log|V^{\prime}|,\
|V^{\prime}||E^{\prime}|\right)\right)$.

The cost to sort the edge index values in line 11 is
$O(|E^{\prime}|\log|E^{\prime}|)$; the termination check on line 12 has cost
$O(1)$.

In the for-loop contained in lines 14-22, we iterate over edge index values
(line 14; $O(|E^{\prime}|)$). Lines 15-16 and 20-21 each have cost $O(1)$. Per
Lemma A.6, the call to ModActsB (Algorithm 8) in line 18 has cost
$O(|V^{\prime}|)$ if $\psi>0$ and $O(|V^{\prime}|^{2})$ otherwise. Per Lemma
A.7, the call to UpdateG (Algorithm 9) in line 19 has time complexity
$O(|V^{\prime}||E^{\prime}|)$. Thus, for $\psi\in[0,1)$, lines 14-22 have time
complexity $O(|V^{\prime}||E^{\prime}|^{2})$ if $\psi>0$ and
$O\left(\max\left(|V^{\prime}||E^{\prime}|^{2},\
|V^{\prime}|^{2}|E^{\prime}|\right)\right)$ otherwise.

Finally, we consider the subroutine in its entirety. For notational
convenience, let $\xi$ represent the outer cost of the while-loop, where the
maximum number of iterations is defined per Lemma A.8:

$\xi=\mathds{1}(\psi>0)\times\min(|E^{\prime}|^{2},\lfloor{\frac{\texttt{b=2}}{\psi}\rfloor}|E^{\prime}|)+\mathds{1}(\psi=0)\times~{}|V^{\prime}||E^{\prime}|$

Then, for $\psi\in[0,1)$, the time complexity of the MsgPull is:
$\begin{cases}O\left(\max\left(\xi|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi|V^{\prime}||E^{\prime}|^{2}\right)\right),&\text{$\psi>0$}\\\
O\left(\max\left(\xi|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi|V^{\prime}||E^{\prime}|^{2},\
\xi|V^{\prime}|^{2}|E^{\prime}|\right)\right),&\text{else}\end{cases}$ ∎

See 3.2

###### Proof.

Per Remark A.2 and Lemma A.3, the time complexity of constructing Greta’s
inputs is dominated by precomputation of the Whittle indices, which has cost
$O(|V||\mathcal{A}||\mathcal{S}|^{2}T)$. Lines 2-3 of Greta (Algorithm 2) have
cost $O(1)$.

The while-loop termination check we perform in line 4 has time complexity
$O(|E^{\prime}|)$ since we call GetCost (Algorithm 3) for each edge $e\in
E^{\prime}$. Line 5 has cost $O(1)$.

Inside the while-loop (i.e., Algorithm 2, lines 4-13), the call to the MsgPull
subroutine on line 7 contributes the dominating cost. Per Lemma A.9, for
$\psi\in[0,1)$, this subroutine has time complexity:

$\begin{cases}O\left(\max\left(\xi|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi|V^{\prime}||E^{\prime}|^{2}\right)\right),&\text{$\psi>0$}\\\
O\left(\max\left(\xi|V^{\prime}|^{2}\log|V^{\prime}|,\
\xi|V^{\prime}||E^{\prime}|^{2},\
\xi|V^{\prime}|^{2}|E^{\prime}|\right)\right),&\text{else}\end{cases}$

where

$\xi=\mathds{1}(\psi>0)\times\min(|E^{\prime}|^{2},\lfloor{\frac{\texttt{b=2}}{\psi}\rfloor}|E^{\prime}|)+\mathds{1}(\psi=0)\times~{}|V^{\prime}||E^{\prime}|$

Next, we can bound the number of while-loop iterations that occur during any
given call to Greta in a way that proceeds identically to the bound we
establish for the MsgPull subroutine’s while-loop in Lemma A.8, with one small
modification: we replace b with the full budget, $B$, noting that
$\texttt{b}\leq B$. This accounts for the presence of the $\xi^{2}$ term in
Theorem 3.2.

Finally, we note that we call Greta once per timestep $t$. Thus, when we
consider the time complexity over time horizon, $T$, the cost of computing
$\vec{a}_{t}$ $T$ times dominates the $O(|V||\mathcal{A}||\mathcal{S}|^{2}T)$
cost of precomputing the Whittle indices, and we are done. ∎

##  Appendix B Additional empirical results

Here we provide additional empirical support for Theorem 3.1, reproduced below
for convenience: See 3.1

We note that for any given directed graph, $G=(V,E)$, for fixed $|V|$, as
$|E|$ tends toward a complete graph (i.e., $|E|~{}\rightarrow~{}|V|*(|V|-1)$),
as long as we have budget $B\geq C(2)+C(1)$ (or, equivalently, $B\geq
1+\psi$), we can pull _any_ arm and gain the ability to message _any other_
arm. Thus, in the complete graph setting, we can modify the constrained
optimization-based approach represented by Equation 1 (reproduced for
convenience below) to: (1) include the requirement that at least one arm
receive a pull (i.e., constraint c); and (2) remove the neighborhood
constraint (i.e., constraint a), since it is guaranteed to be satisfied
without being explicitly enforced.

$\begin{array}[]{l@{}ll}J(\mathbf{s})=\max\limits_{\mathbf{X}}&\left\\{\displaystyle\sum_{i=0}^{n-1}r^{i}(s^{i})+\beta\mathbb{E}[J(\mathbf{s}^{\prime}),\mathbf{X}]\right\\}&\\\
\text{subject to
}&\displaystyle\sum_{i=0}^{n-1}\sum_{j=0}^{|\mathcal{A}|-1}x_{i,j}\cdot
c_{j}\leq B&\\\ (a)&x_{i,1}\leq\displaystyle\bigvee_{i^{\prime}\in{\cal
N}_{\text{in}}(i)}x_{i^{\prime},2}&\forall i\in[n]\\\
(b)&\displaystyle\sum_{j=0}^{|\mathcal{A}|-1}x_{i,j}=1&\forall i\in[n]\\\
(c)&\displaystyle\sum_{i=0}^{n-1}x_{i,2}\geq 1&\\\
(d)&\mathbf{X}\in\\{0,1\\}^{n\times|\mathcal{A}|}&\end{array}$

Thus, for fixed set of restless arms with cardinality $|V|$, and message cost,
$\psi$, we can upper-bound $\mathbb{E}_{\textsc{GH},\psi}[R]$ by the expected
reward achieved by the modified math program when the graph in question is
complete. Intuitively, this bound will become tighter as the cardinality of
$|E|$ is increased.

To empirically validate this claim, we consider a synthetic cohort of $n=100$
restless arms whose transition matrices are randomly generated in such a way
so as to satisfy the structural constraints introduced in Section 2. We let
$T=120,B=10$, and $\psi=0.5$. We can then construct graphs using this fixed
vertex set but containing edge sets with varying cardinalities, expressed as a
percentage of the number of edges the complete graph would contain.

More concretely, we define a set of six edge generation seeds, and use each
seed to select subsets of edges uniformly at random, such that the subsets
have cardinalities $\in\\{0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0\\}$ of
the complete graph. For each graph so constructed, we report unnormalized
$\mathbb{E}_{\pi}[R]$, along with margins of error for 95% confidence
intervals computed over 30 simulation iterations (see subfigures a-f). We
observe that:

  1. 1.

For each seed, and every value of $|E|$,
$\mathbb{E}_{\textsc{TW},\psi}[R]\leq\mathbb{E}_{\textsc{GH},\psi}[R]<\mathbb{E}_{\textsc{MP},\psi}[R]$.

  2. 2.

We note that while Greta’s expected reward does not monotonoically increase
with $|E|$ in every case, this is to be expected, since we are not guaranteed
to get the same subset of edges we had for smaller percentage values as we
increase $|E|$. This being said, expected reward is generally increasing with
$|E|$, and as $|E|~{}\rightarrow|V|(|V|-1)$,
$\mathbb{E}_{\textsc{GH},\psi}[R]\rightarrow\mathbb{E}_{\textsc{MP},\psi}[R]$.

(a) Edge generation seed 1

(b) Edge generation seed 2

(c) Edge generation seed 3

(d) Edge generation seed 4

(e) Edge generation seed 5

(f) Edge generation seed 6

##  Appendix C Additional experimental details

Source code: For the source code and instructions needed to reproduce the
experimental results we report in Section 4, see:
crherlihy/networked_restless_bandits.

Compute resources: We ran all of our simulations on a MacBook Pro with a 2 GHz
Quad-Core Intel(R) Core i5 CPU and 16 GB of RAM.

## Acknowledgments

We were supported by NSF CAREER Award IIS-1846237, NSF D-ISN Award #2039862,
NSF Award CCF-1852352, NIH R01 Award NLM013039-01, NIST MSE Award #20126334,
DARPA GARD #HR00112020007, DoD WHS Award #HQ003420F0035, ARPA-E Award
#4334192, ARL Award W911NF2120076 and a Google Faculty Research Award. The
views and conclusions contained in this publication are those of the authors
and should not be interpreted as representing official policies or
endorsements of U.S. government or funding agencies. We thank Samuel Dooley,
Pranav Goel, Aviva Prins, Dr. Philip Resnik, and our anonymous reviewers for
their helpful input and feedback.

## References

  * Almasan et al. (2022) Almasan, P.; Suárez-Varela, J.; Rusek, K.; Barlet-Ros, P.; and Cabellos-Aparicio, A. 2022.  Deep reinforcement learning meets graph neural networks: Exploring a routing optimization use case.  _Computer Communications_ , 196: 184–194.
  * Fisher et al. (2017) Fisher, E. B.; Boothroyd, R. I.; Elstad, E. A.; Hays, L.; Henes, A.; Maslow, G. R.; and Velicer, C. 2017.  Peer support of complex health behaviors in prevention and disease management with special reference to diabetes: systematic reviews.  _Clinical Diabetes and Endocrinology_ , 3(1): 4.
  * Glazebrook, Hodge, and Kirkbride (2011) Glazebrook, K. D.; Hodge, D. J.; and Kirkbride, C. 2011.  General notions of indexability for queueing control and asset management.  _The Annals of Applied Probability_ , 21(3): 876 – 907.
  * Holland, Laskey, and Leinhardt (1983) Holland, P. W.; Laskey, K. B.; and Leinhardt, S. 1983.  Stochastic blockmodels: First steps.  _Social Networks_ , 5(2): 109–137.
  * Jung, Abeille, and Tewari (2019) Jung, Y. H.; Abeille, M.; and Tewari, A. 2019.  Thompson Sampling in Non-Episodic Restless Bandits.  _CoRR_ , abs/1910.05654.
  * Jung and Tewari (2019) Jung, Y. H.; and Tewari, A. 2019.  Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems.  In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Killian, Perrault, and Tambe (2021) Killian, J. A.; Perrault, A.; and Tambe, M. 2021.  Beyond ”To Act or Not to Act”: Fast Lagrangian Approaches to General Multi-Action Restless Bandits.  In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_ , AAMAS ’21, 710–718. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems.  ISBN 9781450383073.
  * Liu and Zhao (2010) Liu, K.; and Zhao, Q. 2010.  Indexability of Restless Bandit Problems and Optimality of Whittle Index for Dynamic Multichannel Access.  _IEEE Transactions on Information Theory_ , 56(11): 5547–5567.
  * Lu, Hu, and Zhang (2021) Lu, S.; Hu, Y.; and Zhang, L. 2021.  Stochastic Bandits with Graph Feedback in Non-Stationary Environments.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(10): 8758–8766.
  * Mate et al. (2020) Mate, A.; Killian, J.; Xu, H.; Perrault, A.; and Tambe, M. 2020.  Collapsing Bandits and Their Application to Public Health Intervention.  In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; and Lin, H., eds., _Advances in Neural Information Processing Systems_ , volume 33, 15639–15650. Curran Associates, Inc.
  * Ortner et al. (2012) Ortner, R.; Ryabko, D.; Auer, P.; and Munos, R. 2012.  Regret Bounds for Restless Markov Bandits.  In _Proceedings of the 23rd International Conference on Algorithmic Learning Theory_ , ALT’12, 214–228. Berlin, Heidelberg: Springer-Verlag.  ISBN 9783642341052.
  * Ou et al. (2022) Ou, H.-C.; Siebenbrunner, C.; Killian, J.; Brooks, M. B.; Kempe, D.; Vorobeychik, Y.; and Tambe, M. 2022.  Networked Restless Multi-Armed Bandits for Mobile Interventions.  In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems_ , AAMAS ’22, 1001–1009. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems.  ISBN 9781450392136.
  * Papadimitriou and Tsitsiklis (1994) Papadimitriou, C. H.; and Tsitsiklis, J. N. 1994.  The Complexity of Optimal Queueing Network Control.  In _Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory_ , 318–322. IEEE.
  * Pasanisi, Fu, and Bousquet (2012) Pasanisi, A.; Fu, S.; and Bousquet, N. 2012.  Estimating Discrete Markov Models from Various Incomplete Data Schemes.  _Computational Statistics & Data Analysis_, 56(9): 2609–2625.
  * Pedregosa et al. (2011) Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; and Duchesnay, E. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ , 12: 2825–2830.
  * Steimle and Denton (2017) Steimle, L. N.; and Denton, B. T. 2017.  _Markov Decision Processes for Screening and Treatment of Chronic Diseases_ , 189–222.  Cham: Springer International Publishing.  ISBN 978-3-319-47766-4.
  * Sutton and Barto (2018) Sutton, R. S.; and Barto, A. G. 2018.  _Reinforcement Learning: An Introduction_.  Cambridge, MA, USA: A Bradford Book.  ISBN 0262039249.
  * Thompson (1933) Thompson, W. R. 1933.  On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.  _Biometrika_ , 25(3/4): 285–294.
  * Valko (2016) Valko, M. 2016.  _Bandits on graphs and structures_.  Habilitation à diriger des recherches, École normale supérieure de Cachan - ENS Cachan.
  * Weber and Weiss (1990) Weber, R. R.; and Weiss, G. 1990.  On an index policy for restless bandits.  _Journal of Applied Probability_ , 27(3): 637–648.
  * Whittle (1988) Whittle, P. 1988.  Restless bandits: activity allocation in a changing world.  _Journal of Applied Probability_ , 25(A): 287–298.
  * Zhou et al. (2020) Zhou, J.; Cui, G.; Hu, S.; Zhang, Z.; Yang, C.; Liu, Z.; Wang, L.; Li, C.; and Sun, M. 2020.  Graph neural networks: A review of methods and applications.  _AI Open_ , 1: 57–81.