# Global Rewards in Restless Multi-Armed Bandits

Naveen Raman
Carnegie Mellon University
<EMAIL_ADDRESS>
&Zheyuan Ryan Shi
University of Pittsburgh
<EMAIL_ADDRESS>
Fei Fang
Carnegie Mellon University
<EMAIL_ADDRESS>

###### Abstract

Restless multi-armed bandits (rmab) extend multi-armed bandits so pulling an
arm impacts future states. Despite the success of rmabs, a key limiting
assumption is the separability of rewards into a sum across arms. We address
this deficiency by proposing restless-multi-armed bandit with global rewards
(rmab-g), a generalization of rmabs to global non-separable rewards. To solve
rmab-g, we develop the Linear- and Shapley-Whittle indices, which extend
Whittle indices from rmabs to rmab-gs. We prove approximation bounds but also
point out how these indices could fail when reward functions are highly non-
linear. To overcome this, we propose two sets of adaptive policies: the first
computes indices iteratively, and the second combines indices with Monte-Carlo
Tree Search (MCTS). Empirically, we demonstrate that our proposed policies
outperform baselines and index-based policies with synthetic data and real-
world data from food rescue.

##  1 Introduction

Restless multi-armed bandits (rmab) are models of resource allocation that
combine multi-armed bandits with states for each bandit’s arm. Such a model is
“restless” because arms can change state even when not pulled. rmabs are an
enticing framework because optimal decisions can be efficiently made using
pre-computed Whittle indices [1, 2]. As a result, rmab have been used in
scheduling [3], autonomous driving [4], multichannel access [5], and maternal
health [6].

The existing rmab model assumes that rewards are separable into a sum of per-
arm rewards. However, many real-world objectives are non-separable functions
of the arms pulled. We find this situation in food rescue platforms. These
platforms notify subsets of volunteers about upcoming food rescue trips and
aim to maximize the trip completion rate [7]. When modeling this with rmabs,
arms correspond to volunteers, arm pulls correspond to notifications, and the
reward corresponds to the trip completion rate. The trip completion rate is
non-separable as we only need one volunteer to complete each trip (more
details in Section 3). Beyond food rescue, rmabs can potentially model
problems in peer review [8], blood donation [9], and emergency dispatch [10],
but the rewards are again non-separable.

Motivated by these situations, we propose the restless multi-armed bandit with
global rewards (rmab-g), a generalization of rmabs to non-separable rewards.
Whittle indices from rmabs [1] fail for rmab-gs due to the non-separability of
the reward. Because of this, we propose a generalization of Whittle indices to
global rewards called the Linear-Whittle and Shapley-Whittle indices. Our
approximation bounds demonstrate that these policies perform well for near-
linear rewards but struggle for highly non-linear rewards. We address this by
developing adaptive policies that combine Linear- and Shapley-Whittle indices
with search techniques. We empirically verify that adaptive policies
outperform index-based and baseline approaches on synthetic and food rescue
datasets. 111We plan to release code and all non-proprietary data after the
camera ready

Our contributions are: (1) We propose the rmab-g problem, which extends rmabs
to situations with global rewards. We additionally characterize the difficulty
of solving and approximating rmab-gs; (2) We develop the Linear-Whittle and
Shapley-Whittle indices, which extend Whittle indices for global rewards, and
detail approximation bounds; (3) We design a set of adaptive policies which
combine Linear- and Shapley-Whittle indices with greedy and Monte Carlo Tree
Search (MCTS) algorithms; and (4) We empirically demonstrate that adaptive
policies improve upon baselines and pre-computed index-based policies for the
rmab-g problem with synthetic and food rescue datasets.

##  2 Background and Notation

An instance of restless multi-armed bandits (rmabs) consists of $N$ arms, each
of which is defined through the following Markov Decision Process (mdp):
$(\mathcal{S},\mathcal{A},R_{i},P_{i},\gamma)$. Here, $\mathcal{S}$ is the
state space, $\mathcal{A}$ is the action space,
$R_{i}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is a reward
function,
$P_{i}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is a
transition function detailing the probability of an arm transitioning into a
new state, and $\gamma\in[0,1)$ is a discount factor. For a time period $t$,
we define the state of all arm as
$\mathbf{s}^{(t)}=\\{s_{1}^{(t)},\cdots,s_{N}^{(t)}\\},s_{i}^{(t)}\in\mathcal{S}$,
and for each round, a planner takes action
$\mathbf{a}^{(t)}=\\{a_{1}^{(t)},\cdots,a_{N}^{(t)}\\},a_{i}^{(t)}\in\mathcal{A}$;
we drop the superscript $t$ when clear from context. Following prior work [11,
6], we assume $\mathcal{A}=\\{0,1\\}$ throughout this paper to represent not
pulling and pulling an arm respectively. A planner chooses $\mathbf{a}^{(t)}$
subject to a budget $K$, so that at most $K$ arms can be pulled in each time
step: $\sum_{i=1}^{N}a_{i}^{(t)}\leq K,\forall t$. The objective is to find a
policy, $\pi:\mathcal{S}^{N}\rightarrow\mathcal{A}^{N}$ that maximizes the
discounted total reward, summed over all arms:

$\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\sum_{t=0}^{\infty}\sum_{i=1}^{N}\gamma^{t}R_{i}(s_{i}^{(t)},a_{i}^{(t)})]$
(1)

To solve an rmab, one can pre-compute the “Whittle index” for each arm $i$ and
possible state $s_{i}$:
$w_{i}(s_{i})=\min\limits_{w}\\{w|Q_{i,w}(s_{i},0)>Q_{i,w}(s_{i},1)\\}$, where
$Q_{i,w}(s_{i},a_{i})=-wa_{i}+R_{i}(s_{i},a_{i})+\gamma\sum_{s^{\prime}}P_{i}(s_{i},a_{i},s^{\prime})V_{i,w}(s^{\prime})$,
and $V_{i,w}(s^{\prime})=\max\limits_{a}Q_{i,w}(s^{\prime},a)$. Here,
$Q_{i,w}(s_{i},a_{i})$ represents the expected future reward for playing
action $a_{i}$, given a penalty $w$ for pulling an arm. The Whittle index
computes the minimum penalty needed to prevent arm pulls; larger penalties
($w_{i}(s_{i})$) indicate more value for pulling an arm. In each round, the
planner pulls the arms with the $K$ largest Whittle indices given the states
of the arms. Such a Whittle index-based policy is asymptotically optimal [1,
2].

##  3 Defining Restless Multi-Armed Bandits with Global Rewards

Objectives in rmabs are written as the sum of per-arm rewards (Equation 1),
while real-world objectives involve non-separable rewards. For example, food
rescue organizations, which notify volunteers about food rescue trips, aim to
maximize the trip completion rate, i.e., the fraction of completed trips.
Suppose we model volunteers as arms and volunteer notifications as arm pulls.
Then arm states correspond to volunteer engagement (e.g., active or inactive)
and rewards are the probability that any notified volunteers complete the
rescue. Here, we cannot split the reward into per-volunteer functions.

Inspired by situations such as food rescue, we propose the restless multi-
armed bandit with global rewards (rmab-g) problem, which generalizes rmabs to
problems with a global reward function:

######  Definition 1.

We define an instance of rmab-g through the following MDP for each arm:
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$. The aim is
to find a policy, $\pi:\mathcal{S}^{N}\rightarrow\mathcal{A}^{N}$, that
maximizes:

$\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\sum_{t=0}^{\infty}\gamma^{t}(R_{\mathrm{glob}}(\mathbf{s}^{(t)},\mathbf{a}^{(t)})+\sum_{i=1}^{N}R_{i}(s_{i}^{(t)},a_{i}^{(t)}))]$
(2)

Throughout this paper, we focus on scenarios where
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$ is monotonic and submodular in
$\mathbf{a}$;
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=F_{\mathbf{S}}(\\{i|a_{i}=1\\})$,
where $F$ is submodular and monotonic. Such rewards have diminishing returns
as extra arms are pulled. We select this because a) monotonic and submodular
functions can be efficiently optimized [12] and b) submodular functions are
ubiquitous [13, 14, 8].

Our problem formulation can model various real-world scenarios including
notification decisions in food rescue and reviewer assignments in peer review
[8]. In food rescue, let $p_{i}(s_{i})$ be the probability that a volunteer
picks up a given trip, given their state, $s_{i}$. The global reward is the
probability that any notified volunteer accepts a trip:
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=1-\prod_{i=1}^{N}(1-a_{i}p_{i}(s_{i}))$.
In peer review, journals select reviewers for submissions where selection
impacts future reviewer availability [8]. The goal is to select a subset of
available reviewers with comprehensive subject-matter expertise. If reviewer
expertise is a set $Y_{i}$, then we maximize the overlap between the required
expertise, $Z$, and the expertise across selected ($a_{i}=1$) and available
($s_{i}=1$) reviewers:
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=|\bigcup\limits_{i,s_{i}=1,a_{i}=1}Y_{i}\cap
Z|$. Our formulation inherits the per-arm reward $R_{i}$ from rmabs as there
may be per-arm rewards. For example, food rescue platforms might care about
the number of active volunteers, so $R_{i}(s_{i},a_{i})=s_{i}$.

Let
$R(\mathbf{s},\mathbf{a})=R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})\sum_{i=1}^{N}R_{i}(s_{i},a_{i})$.
We characterize the difficulty of rmab-g:

######  Theorem 1.

The restless multi-armed bandit with global rewards is PSPACE-Hard.

######  Theorem 2.

No polynomial time algorithm can achieve better than a $1-1/e$ approximation
to the restless multi-armed bandit with global rewards problem.

######  Theorem 3.

Consider an rmab-g instance
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$. Let
$Q_{\pi}(\mathbf{s},\mathbf{a})=\mathbb{E}_{(\mathbf{s^{\prime}},\mathbf{a^{\prime}})\sim(\mathcal{P},\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s^{\prime}},\mathbf{a^{\prime}}))|\mathbf{s}^{(0)}=\mathbf{s},\mathbf{a}^{(0)}=\mathbf{a}]$
and let $\pi^{*}$ be the optimal policy. Let
$\mathbf{a}^{*}=\operatorname*{arg\,max}_{\mathbf{a}}Q_{\pi^{*}}(\mathbf{s},\mathbf{a})$.
Suppose $P_{i}(s,1,1)\geq P_{i}(s,0,1)\forall s,i$, $P_{i}(1,a,1)\geq
P_{i}(0,a,1)\forall i,a$, $R(\mathbf{s},\mathbf{a})$ monotonic and submodular
in $\mathbf{s}$ and $\mathbf{a}$, and
$g(\mathbf{s})=\max\limits_{\mathbf{a}}R(\mathbf{s},\mathbf{a})$ submodular in
$\mathbf{s}$. Then, with oracle access to $Q_{\pi^{*}}$ we can compute
$\hat{\mathbf{a}}$ in $\mathcal{O}(N^{2})$ time so
$Q_{\pi^{*}}(\mathbf{s},\hat{\mathbf{a}})\geq(1-\frac{1}{e})Q_{\pi^{*}}(\mathbf{s},\mathbf{a}^{*})$.

Theorem 1 and 2 demonstrate the difficulty of finding solutions to rmab-gs
while Theorem 3 describes a potential panacea via $Q_{\pi^{*}}$. Leveraging
$Q_{\pi^{*}}$ is the best polynomial-time algorithm (due to matching bounds
from Theorem 2 and 3), but the exponential state space makes it difficult to
learn such a $Q$, motivating the need for better algorithms (we empirically
demonstrate this in Section 6.1). We prove Theorem 1 through reduction from
rmab, Theorem 2 through reduction from submodular optimization, and Theorem 3
through induction on value iteration. Full proofs are in Appendix K.

##  4 Linear-Whittle and Shapley-Whittle Indices

###  4.1 Defining Linear-Whittle and Shapley-Whittle

Because the Whittle index policy is optimal for rmabs [2], we investigate its
extension to rmab-gs. We develop two extensions: the Linear-Whittle policy,
which computes marginal rewards for each arm, and the Shapley-Whittle policy,
which computes Shapley values for each arm. To define the Linear-Whittle
policy, we define the marginal reward as
$p_{i}(s_{i})=\max\limits_{\mathbf{s}^{\prime}|s^{\prime}_{i}=s_{i}}R_{\mathrm{glob}}(\mathbf{s}^{\prime},\mathbf{e}_{i})$,
where $\mathbf{e}_{i}$ is a vector with 1 at index $i$ and $0$ elsewhere. The
Linear-Whittle policy linearizes the global reward by optimistically
estimating
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})\approx\sum_{i=1}^{N}p_{i}(s_{i})a_{i}$
and computing the Whittle index from this:

######  Definition 2.

Linear-Whittle \- Consider an instance of rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$. Define
$Q_{i,w}^{L}(s_{i},a_{i},p_{i})=-a_{i}w+R_{i}(s_{i},a_{i})+a_{i}p_{i}(s_{i})+\gamma\sum_{s_{i}^{\prime}}P_{i}(s_{i},a_{i},s^{\prime}_{i})V_{i,w}(s^{\prime}_{i})$,
where
$V_{i,w}(s_{i}^{\prime})=\max\limits_{a_{i}^{\prime}}Q_{i,w}^{L}(s_{i}^{\prime},a_{i}^{\prime},p_{i})$.
Then the Linear-Whittle index is
$w_{i}^{L}(s_{i},p_{i})=\min\limits_{w}\\{w|Q^{L}_{i,w}(s_{i},0,p_{i})>Q_{i,w}^{L}(s_{i},1,p_{i})\\}$.
The Linear-Whittle policy pulls arms with the $K$ highest Linear-Whittle
indices.

To improve on the Linear-Whittle policy, we develop the Shapley-Whittle
policy, which uses Shapley values to linearize the global reward. The Linear-
Whittle policy linearizes global rewards via $p_{i}(s_{i})$, but this
approximation could be loose as $\sum_{i=1}^{N}p_{i}(s_{i})a_{i}\geq
R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$. The Shapley value, $u_{i}(s_{i})$,
improves this by averaging marginal rewards across subsets of arms (see
Shapley et al. [15]). Let $\lor$ be the element-wise maximum, so
$\mathbf{a}\lor\mathbf{e}_{i}$ means arms in $\mathbf{a}$ and arm $i$ are
pulled. Define:

$u_{i}(s_{i})=\min\limits_{\mathbf{s}^{\prime}|s^{\prime}_{i}=s_{i}}\sum_{\mathbf{a}\in\\{0,1\\}^{N},a_{i}=0,\|\mathbf{a}\|_{1}\leq
K-1}\frac{\|\mathbf{a}\|_{1}!(N-\|\mathbf{a}\|_{1}-1)!}{\frac{N!}{(N-K)!}}(R_{\mathrm{glob}}(\mathbf{s}^{\prime},\mathbf{a}\lor\mathbf{e}_{i})-R_{\mathrm{glob}}(\mathbf{s}^{\prime},\mathbf{a}))$
(3)

Here,
$R_{\mathrm{glob}}(\mathbf{s}^{\prime},\mathbf{a}\lor\mathbf{e}_{i})-R_{\mathrm{glob}}(\mathbf{s}^{\prime},\mathbf{a})$
captures the added value of pulling arm $i$, when $\mathbf{a}$ are already
pulled. While the Linear-Whittle policy estimates the global reward as
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})\approx\sum_{i=1}^{N}p_{i}(s_{i})a_{i}$,
the Shapley-Whittle policy estimates the global reward as
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})\approx\sum_{i=1}^{N}u_{i}(s_{i})a_{i}$.
The Linear-Whittle policy overestimates marginal contributions, as
$\sum_{i=1}^{N}p_{i}(s_{i})a_{i}\geq R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$
(proof in Appendix L), so by using Shapley values, we take a pessimistic
approach (by taking the minimum over all $\mathbf{s}^{\prime}$). This approach
could lead to more accurate estimates of
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$:

######  Definition 3.

Shapley-Whittle \- Consider an instance of rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$. Let
$Q_{i,w}^{S}(s_{i},a_{i},u_{i})=-a_{i}w+R_{i}(s_{i},a_{i})+a_{i}u_{i}(s_{i})+\gamma\sum_{s_{i}^{\prime}}P_{i}(s_{i},a_{i},s_{i}^{\prime})V_{i,w}(s^{\prime}_{i})$,
where
$V_{i,w}(s^{\prime}_{i})=\max\limits_{a^{\prime}_{i}}Q_{i,w}^{S}(s^{\prime}_{i},a^{\prime}_{i},u_{i})$.
Then the Shapley-Whittle index is
$w_{i}^{S}(s_{i},u_{i})=\min\limits_{w}\\{w|Q_{i,w}^{S}(s_{i},0,u_{i})>Q^{S}_{i,w}(s_{i},1,u_{i})\\}$.
The Shapley-Whittle policy pulls arms with the $K$ highest Shapley-Whittle
indices.

###  4.2 Approximation Bounds

To characterize the performance of our policies, we prove approximation
bounds:

######  Theorem 4.

For any fixed set of transitions, $\mathcal{P}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
for some $T$. For an rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$, let
$R^{\prime}_{i}(s_{i},a_{i})=R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i}$, and let
the induced linear rmab be
$(\mathcal{S},\mathcal{A},R^{\prime}_{i},P_{i},\gamma)$. Let
$\pi_{\mathrm{linear}}$ be the Linear-Whittle policy, and let
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$.
Define $\beta_{\mathrm{linear}}$ as

$\beta_{\mathrm{linear}}=\min\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i})}$
(4)

If the induced linear rmab is irreducible and indexable with the uniform
global attractor property, then
$\mathrm{ALG}\geq\beta_{\mathrm{linear}}\mathrm{OPT}$ asymptotically in $N$
for any set of transitions, $\mathcal{P}$.

######  Theorem 5.

For any fixed set of transitions, $\mathcal{P}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
for some $T$. For an rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$, let
$R^{\prime}_{i}(s_{i},a_{i})=R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i}$, and let
the induced Shapley rmab be
$(\mathcal{S},\mathcal{A},R^{\prime}_{i},P_{i},\gamma)$. Let
$\pi_{\mathrm{shapley}}$ be the Shapley-Whittle policy, and let
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{shapley}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$.
Define $\beta_{\mathrm{shapley}}$ as

$\beta_{\mathrm{shapley}}=\frac{\min\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i})}}{\max\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i})}}$
(5)

If the induced Shapley rmab is irreducible and indexable with the uniform
global attractor property, then
$\mathrm{ALG}\geq\beta_{\mathrm{shapley}}\mathrm{OPT}$ asymptotically in $N$
for any choice of transitions, $\mathcal{P}$.

######  Corollary 5.1.

Let $\pi_{\mathrm{linear}}$ be the Linear-Whittle policy,
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
and
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
for some $T$. Then $\mathrm{ALG}\geq\frac{\mathrm{OPT}}{K}$ for any
$\mathcal{P}$.

$\beta$ lower bounds policy performance; small $\beta$ does not guarantee poor
performance but large $\beta$ guarantees good performance. For example,
$\beta_{\mathrm{linear}}$ and $\beta_{\mathrm{shapley}}$ are near $1$ for
near-linear global rewards, so Linear- and Shapley-Whittle policies perform
well in those situations. We prove all three Theorems by bounding the gap
between the linear (or Shapley) approximation and $R(\mathbf{s},\mathbf{a})$
(proofs in Appendix L). We note that the assumptions made by all Theorems are
the same assumptions needed for the optimality of Whittle indices [2]. We
present an example of these lower bounds:

######  Example 4.1.

Consider an $N=4,K=2$ scenario for rmab-g with $\mathcal{S}=\\{0,1\\}$. Let
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=|\bigcup\limits_{i|a_{i}=1,s_{i}=1}Y_{i}|$
and $R_{i}(s_{i},a_{i})=0$. Here, $Y_{i}$ are sets corresponding to each arm,
with $Y_{1}=Y_{2}=\\{1,2,3\\}$, $Y_{3}=\\{1,2\\}$ and $Y_{4}=\\{3,4\\}$. Let
$s_{i}=1$ for all $i$, and consider the Linear-Whittle policy. Next, note that
$p_{i}(s_{i})=R(s_{i}\mathbf{e}_{i},\mathbf{e}_{i})$, so
$p_{1}(1)=p_{2}(1)=3,p_{3}(1)=p_{4}(1)=2$.

Now let $\mathbf{a}=[1,1,0,0]$ and let $\mathbf{s}=[1,1,1,1]$. Here,
$R(\mathbf{s},\mathbf{a})=|Y_{1}\cup Y_{2}|=3$, while
$\sum_{i=1}^{N}p_{i}(s_{i})a_{i}=6$. Therefore,
$\beta_{\mathrm{linear}}=\frac{3}{6}=\frac{1}{2}$, so the Linear-Whittle
policy is a $\frac{1}{2}$ approximation to this problem.

We describe upper bounds and apply these bounds to Example 4.1.

######  Theorem 6.

Let
$\mathbf{\hat{a}}(\mathbf{s})=\operatorname*{arg\,max}\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i})$. For a set of
transitions $\mathcal{P}=\\{P_{1},P_{2},\cdots,P_{N}\\}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$
and
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$.
Define $\theta_{\mathrm{linear}}$ as follows:

$\theta_{\mathrm{linear}}=\min\limits_{\mathbf{s}\in\mathcal{S}^{N}}\frac{R(\mathbf{s},\hat{\mathbf{a}}(\mathbf{s}))}{\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})}$ (6)

Then there exists some transitions, $\mathcal{P}$, and initial state
$\mathbf{s}^{(0)}$, so that
$\mathrm{ALG}\leq\theta_{\mathrm{linear}}\mathrm{OPT}$

######  Theorem 7.

Let
$\mathbf{\hat{a}}(\mathbf{s})=\operatorname*{arg\,max}\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i})$. For a set of
transitions $\mathcal{P}=\\{P_{1},P_{2},\cdots,P_{N}\\}$ and initial state
$\mathbf{s}^{(0)}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$
and
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{shapley}})}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$.
Let $\theta_{\mathrm{shapley}}$ be:

$\theta_{\mathrm{shapley}}=\min\limits_{\mathbf{s}}\frac{R(\mathbf{s},\hat{\mathbf{a}}(\mathbf{s}))}{\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})}$ (7)

Then there exists some transitions, $\mathcal{P}$ and initial state
$\mathbf{s}^{(0)}$ so that
$\mathrm{ALG}\leq\theta_{\mathrm{shapley}}\mathrm{OPT}$

######  Example 4.2.

Recall the situation from Example 4.1. Let $s_{i}=1$ for all $i$, and consider
the Linear-Whittle policy. Construct construct $P_{i}$, so that
$P_{i}(s,a,1)=1\forall i,s,a$ or in other words, $s_{i}^{(t)}=1\forall i,t$.
The Linear-Whittle policy will pull arms $1$ and $2$, as
$p_{1}(1)+p_{2}(1)\geq p_{i}(1)+p_{j}(1)\forall i,j$. This results in an
action $\mathbf{a}=[1,1,0,0]$, so that $R(\mathbf{s},\mathbf{a})=3$, while the
optimal action is $\mathbf{a}^{*}=[0,0,1,1]$ with
$R(\mathbf{s},\mathbf{a}^{*})=4$. Computing $\theta_{\mathrm{linear}}$ matches
this upper bound of $\frac{3}{4}$ in this scenario.

Our upper bounds demonstrate that, for any reward function, there exists a set
of transitions where our policies perform a $\theta$-fraction worse than
optimal. $\theta_{\mathrm{linear}}$ is small when the optimal action diverges
from the action taken by the Linear-Whittle policy (analogously for Shapley-
Whittle). Such situations occur because policies fail to account for inter-arm
interactions (e.g. Example 4.2). We present lower bounds using the average
reward because Whittle optimality holds in that situation. Otherwise, we
follow prior work, and focus on discounted reward [11] (for more discussion
see Ghosh et al. [16])

##  5 Adaptive Approaches for RMAB-G

###  5.1 Limitations of Pre-Computed Index-Based Policies

Despite the approximation bounds given in Appendix L, Linear- and Shapley-
Whittle policies can exhibit poor performance when upper bounds
$\theta_{\mathrm{linear}}$ and $\theta_{\mathrm{shapley}}$ are small. We
detail such a situation:

######  Lemma 8.

(Informal) Let $\pi\in\\{\pi_{\mathrm{linear}},\pi_{\mathrm{shapley}}\\}$ be
either the Linear or Shapley-Whittle policies. There exist problem settings
where $\pi$ will achieve an approximation ratio no better than
$\frac{1-\gamma}{1-\gamma^{K}}$.

In general, pre-computed index-based policies perform poorly because of their
inability to consider inter-arm interactions (proof in Appendix L). This
approximation ratio matches lower bounds, $\lim\limits_{\gamma\rightarrow
1}\frac{1-\gamma}{1-\gamma^{K}}=\frac{1}{K}=\beta_{\mathrm{linear}}=\beta_{\mathrm{shapley}}$,
which motivates new policies which select arms adaptively.

###  5.2 Iterative Whittle Indices

Lemma 8 motivates the need for policies that select arms adaptively and go
beyond pre-computed indices. Based on this, we propose two new policies:
Iterative Linear-Whittle and Iterative Shapley-Whittle. Both policies compute
current time step rewards, $r_{i}$, based on the arms pulled, $X$.

######  Definition 4.

Iterative Linear-Whittle \- Consider an instance of rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$. Consider a
state $\mathbf{s}$, and construct a new state, $\bar{\mathbf{s}}$, with
$P_{\bar{s_{i}}}=P_{i}$. Let
$Q_{i,w}^{IL}(\bar{s}_{i},a_{i},p_{i},r^{L}_{i},X)=Q_{i,w}^{L}(s_{i},a_{i},p_{i})+a_{i}(r_{i}^{L}(\mathbf{s},X)-p_{i}(s_{i}))$
and
$Q_{i,w}^{IL}(s_{i},a_{i},p_{i},r^{L}_{i},X)=Q_{i,w}^{L}(s_{i},a_{i},p_{i})$
for $s_{i}\neq\bar{s}_{i}$. Then the Iterative Linear-Whittle index is
$w_{i}^{IL}(s_{i},p_{i},X)=\min\limits_{w}\\{w|Q_{i,w}^{IL}(s_{i},0,p_{i},r^{L}_{i},X)>Q_{i,w}^{IL}(s_{i},1,p_{i},r^{L}_{i},X)\\}$,
where
$r^{L}_{i}(\mathbf{s},X)=R_{\mathrm{glob}}(\mathbf{s},\mathbf{e}_{i}\lor\bigvee_{l=1}^{j}\mathbf{e}_{x_{l}})-R_{\mathrm{glob}}(\mathbf{s},\bigvee_{l=1}^{j}\mathbf{e}_{x_{l}})$

######  Definition 5.

Iterative Shapley-Whittle \- Consider an instance of rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$, with
$u_{i}(s_{i})$ defined by Equation 3. Construct a new state, $\bar{s}_{i}$,
with $P_{\bar{s_{i}}}=P_{i}$. Let
$Q_{i,w}^{IS}(\bar{s}_{i},a_{i},u_{i},r^{S}_{i},X)=Q_{i,w}^{S}(s_{i},a_{i},u_{i})+a_{i}(r_{i}^{S}(s_{i},X)-u_{i}(s_{i}))$
and
$Q_{i,w}^{IS}(s_{i},a_{i},u_{i},r^{S}_{i},X)=Q_{i,w}^{S}(s_{i},a_{i},u_{i})$
for $s_{i}\neq\bar{s}_{i}$. Then the Iterative Shapley-Whittle Index is
$w_{i}^{IS}(s_{i},u_{i},X)=\min\limits_{w}\\{w|Q_{i,w}^{IS}(s_{i},0,u_{i},r_{i}^{S},X)>Q_{i,w}^{IS}(s_{i},1,u_{i},r_{i}^{S},X)\\}$.
Here $r_{i}(s_{i},X)$ is computed as:

$\min\limits_{\mathbf{s}^{\prime}|s^{\prime}_{i}=s_{i}}\sum_{\begin{subarray}{c}\mathbf{a}\in\\{0,1\\}^{N},\|\mathbf{a}\|_{1}\leq
K-2\\\
a_{i}=a_{X_{1}}=a_{X_{2}}=\cdots=a_{X_{j}}=0\end{subarray}}\frac{\|\mathbf{a}\|_{1}!(n-\|\mathbf{a}\|_{1}-1)!}{\frac{N!}{(N-K-1)!}}(R_{\mathrm{glob}}(\mathbf{s}^{\prime},\mathbf{a}\lor\mathbf{e}_{i}\lor
X)-R_{\mathrm{glob}}(\mathbf{s}^{\prime},\mathbf{a}\lor X))$ (8)

By incorporating the arms pulled, $X$, both policies better estimate the
present reward. Here, $Q_{i,w}^{IL}(\bar{s}_{i},a_{i},p_{i},r_{i}^{L},X)$
represents the expected discounted reward when receiving
$r_{i}^{L}(\mathbf{s},X)$ currently and $p_{i}(s_{i})$ in the future
(similarly for Shapley-Whittle). To model this, we construct a new state,
$\bar{s}_{i}$, which mirrors $s_{i}$ except for the reward in the current
timestep. The Iterative Linear-Whittle and Shapley-Whittle policies then
iteratively select arms that maximize $w_{i}^{IL}$ and $w_{i}^{IS}$
respectively and stop after selecting $K$ arms.

###  5.3 MCTS-based Approaches

To improve upon the greedy selection done by iterative policies, we combine
Monte Carlo Tree Search (mcts) with Whittle indices. mcts allows us to look
beyond greedy selection by searching through various arm combinations. We
propose two policies: MCTS Linear-Whittle and MCTS Shapley-Whittle. For both,
we search through arm combinations, $\mathbf{a}$, compute the present value
($R(\mathbf{s},\mathbf{a})$), and estimate the future value via Linear- and
Shapley-Whittle indices. Nodes in the mcts tree correspond to arm
combinations, edges to individual arms, and leaf nodes to actions
$\mathbf{a}$.

Our implementation of mcts matches the upper confidence tree algorithm for
selection, expansion, and backpropogation [17], while we differ for rollout
(details in Appendix C). During rollout, we select nodes according to an
$\epsilon$-greedy algorithm [18] and leverage the Linear- and Shapley-Whittle
policies for greedy selection. We do so because $\epsilon$-greedy is a simple
strategy that could potentially improve upon random rollouts. Once at a leaf
node, the reward is
$r=R(\mathbf{s},\mathbf{a})+\sum_{i=1}^{N}[Q_{i,0}^{L}(s_{i},a_{i})-p_{i}(s_{i})a_{i}-R_{i}(s_{i},a_{i})]$
for MCTS Linear-Whittle and
$r=R(\mathbf{s},\mathbf{a})+\sum_{i=1}^{N}[Q_{i,0}^{S}(s_{i},a_{i})-u_{i}(s_{i})a_{i}-R_{i}(s_{i},a_{i})]$
for MCTS Shapley-Whittle. Here, $R(\mathbf{s},\mathbf{a})$ is the known
current value, and
$\sum_{i=1}^{N}(Q_{i,0}^{L}(s_{i},a_{i})-p_{i}(s_{i})a_{i}-R_{i}(s_{i},a_{i}))$
is the estimated future value when accounting for the present reward
$R(\mathbf{s},\mathbf{a})$.

##  6 Experiments

We evaluate our policies across both synthetic and real-world datasets. We
compare our six policies (Section 4.1, Section 5.2, and Section 5.3) to the
following baselines (more details in Appendix B):

  1. 1.

Random \- We uniform randomly select $K$ arms at each timestep.

  2. 2.

Vanilla Whittle \- We run the vanilla Whittle index, which optimizes only for
$R_{i}(s_{i},a_{i})$.

  3. 3.

Greedy \- We select actions which have the highest value of $p_{i}(s_{i})$.

  4. 4.

MCTS \- We run mcts up to some depth, $cK$, where $c$ is a constant.

  5. 5.

DQN \- We train a Deep Q Network (dqn) [19], and provide details in Appendix
B.

  6. 6.

DQN Greedy \- Inspired by Theorem 3, we first learn a dqn then greedily
optimize $Q(\mathbf{s},\mathbf{a})$.

  7. 7.

Optimal \- We compute the optimal policy through value iteration when $N\leq
4$.

Figure 1: We compare baselines to our index-based and adaptive policies across
four reward functions. All of our policies outperform baselines. Across all
rewards, our best policy is within 3% of optimal for $N=4$. Among our
policies, Iterative and MCTS Shapley-Whittle consistently perform best.

We run all experiments for 15 seeds and 5 trials per seed. We report the
normalized reward, which is the accumulated discounted reward divided by that
of the random policy. This normalization is due to differences in magnitudes
within and across problem instances and we use discounted rewards due to prior
work [11]. We additionally compute the standard error across all runs.

###  6.1 Results with Synthetic Data

To understand performance across synthetic scenarios, we develop synthetic
problem instances that leverage each of the following global reward functions
(details on $m_{i}$ and $Y_{i}$ choices in Appendix A):

  1. 1.

Linear \- Given $m_{1},\cdots,m_{N}\in\mathbb{R}$, then
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=\sum_{i=1}^{N}m_{i}s_{i}a_{i}$.

  2. 2.

Probability \- Given $m_{1},\cdots,m_{N}\in[0,1]$, then
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=1-\prod_{i=1}^{N}(1-m_{i}a_{i}s_{i})$.

  3. 3.

Max \- Given $m_{1},\cdots,m_{N}\in\mathbb{R}$, then
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=\max_{i}s_{i}a_{i}m_{i}$.

  4. 4.

Subset \- Given sets, $Y_{1},\cdots,Y_{N}\subset\\{1,\cdots,m\\}$,
$m\in\mathbb{Z}$, then
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=|\cup_{i|s_{i}a_{i}=1}Y_{i}|$.

We select these rewards, as they range from linear or near-linear (Linear and
Probability) to highly non-linear (Max and Subset). The reward functions can
also be employed to model real-world situations; the Probability reward models
food rescue and the Subset reward models peer review (see Section 3). For all
rewards, we let $R_{i}(\mathbf{s},\mathbf{a})=s_{i}/N$ and
$\mathcal{S}=\\{0,1\\}$, which matches prior work [6]. We construct synthetic
transitions parameterized by $q$, so $P_{i}(0,0,1)\sim U(0,q)$, where $U$ is
the uniform distribution (see Appendix A). We construct transition
probabilities so that having $a_{i}=1$ or $s_{i}=1$ only improves transition
probabilities (see Wang et al. [11]). We vary $q$ in Appendix G and find that
our choice of $q$ does not impact findings. Unless otherwise specified, we fix
$K=N/2$.

Figure 1 shows that our policies consistently outperform baselines. Among our
policies, Iterative and MCTS Shapley-Whittle policies perform best. For
$N=10$, Iterative and MCTS Shapley-Whittle significantly outperform baselines
(paired t-test $p<0.04$) and index-based policies except for the Linear reward
($p<0.001$). dqn-based policies regress from on average $4\%$ worse for $N=4$
to on average $9\%$ worse for $N=10$ compared to our best policy, which occurs
due to the exponential state space. In Appendix I, we consider more
combinations of $N$ and $K$ and find similar results.

Figure 2: We plot policy performance for instances of the Subset reward which
vary in linearity. We see that the Iterative and MCTS Shapley-Whittle policies
outperform alternatives for non-linear rewards (small
$\theta_{\mathrm{linear}}$) while policy performances converge for linear
rewards (large $\theta_{\mathrm{linear}}$).

To understand policy performance across rewards, we analyze how reward
linearity impacts performance. We quantify linearity via
$\theta_{\mathrm{linear}}$ (see Theorem 6) and compute
$\theta_{\mathrm{linear}}$ for Subset instances varying in $Y_{i}$ (see
Appendix A). For non-linear reward functions (small
$\theta_{\mathrm{linear}}$), Iterative and MCTS-Shapley-Whittle are best,
outperforming Linear-Whittle by 56%, while for near-linear reward functions
(large $\theta_{\mathrm{linear}}$), all policies are within 18% of each other
(Figure 2, $N=10$). Appendix H shows that, for some rewards, adaptive policies
outperform non-adaptive policies by 50%.

Figure 3: We compare the efficiency and performance of Iterative Shapley-
Whittle methods which vary in Monte Carlo samples used for Shapley estimation
and MCTS Shapley-Whittle methods which vary in MCTS iterations. While
Iterative Shapley-Whittle is the slowest, decreasing the number of Monte Carlo
samples can improve efficiency without impacting performance.

To understand the tradeoff between efficiency and performance we plot the time
taken and normalized reward for various $N$ (Figure 3). We evaluate variants
of Iterative Shapley-Whittle and MCTS Shapley-Whittle because both perform
well yet are computationally expensive. For Iterative Shapley-Whittle, 1000
samples are used for Shapley estimation by default, so we consider variants
that use 100, 10, and 1 samples. For MCTS Shapley-Whittle, we run 400
iterations of MCTS by default, so we consider variants that run 40 and 4
iterations. Iterative Shapley-Whittle policies are the slowest but can be made
faster without impacting performance by reducing the number of samples. Our
results demonstrate how we can develop efficient adaptive policies which
perform well.

###  6.2 Results with Real-World Data in Food Rescue

To evaluate our policies in real-world contexts, we apply our policies to a
food rescue dataset. We leverage data from a partnering multi-city food rescue
organization and construct an rmab-g instance using their data (details in
Appendix D). Here, arms correspond to volunteers, and states correspond to
engagement, with $s_{i}=1$ indicating an engaged volunteer. Notifications are
budget-limited because sending out too many notifications can lead to burned-
out volunteers.

We compute transition probabilities from volunteer participation data and
compute match probabilities from volunteer response rates. Using this, we
study whether our policies maintain a high trip completion rate and volunteer
engagement. We assume that food rescue organizations are indifferent to the
tradeoff between trip completion and engagement. Because such an assumption
might not hold in reality, we explore alternative tradeoffs in Appendix I. If
volunteer $i$ is both notified ($a_{i}=1$) and engaged ($s_{i}=1$), then they
match to a trip with probability $m_{i}$. We do so because unengaged
volunteers are less likely to accept food rescue trips. Under this
formulation, our global reward is the probability that any volunteer accepts a
trip, which is exactly the Probability reward. For engagement, we let
$R_{i}(s_{i},a_{i})=s_{i}/N$, which captures the fraction of engaged
volunteers. We model two food rescue scenarios, and detail scenarios with more
volunteers in Appendix J:

Notifications \- Food rescue organizations deliver notifications to volunteers
as new trips arise [7]. To model this scenario, we consider $N=100$ volunteers
and $K=50$ notifications.

Phone Calls \- When a trip remains unclaimed after notifications, food rescue
organizations call a small set of experienced volunteers. We model this with
$N=20$, $K=10$, and using only arms corresponding to experienced volunteers
with more than 100 trips completed (details in Appendix D).

In Table 1, we compare our policies against baselines and find that our
policies achieve higher normalized rewards. All of our policies outperform all
baselines by at least 5%. Comparing between policies, we find that Iterative
and MCTS Shapley-Whittle perform best, performing slightly better than the
Shapley-Whittle policy. Currently, food rescue organizations perform
notifications greedily, so an rmab-g framework could improve the engagement
and trip completion rate.

| Vanilla Whittle | Greedy | MCTS | DQN | Linear Whittle
---|---|---|---|---|---
Notifications | 0.975 $\pm$ 0.012 | 1.829 $\pm$ 0.016 | 1.047 $\pm$ 0.012 | 1.547 $\pm$ 0.025 | 1.932 $\pm$ 0.017
Phone Calls | 0.989 $\pm$ 0.009 | 1.228 $\pm$ 0.008 | 1.070 $\pm$ 0.016 | 1.209 $\pm$ 0.007 | 1.288 $\pm$ 0.008
| Shapley Whittle | Iter. Linear | Iter. Shapley | MCTS Linear | MCTS Shapley
Notifications | 1.931 $\pm$ 0.016 | 1.921 $\pm$ 0.017 |  |  |
Phone Calls | 1.290 $\pm$ 0.008 | 1.287 $\pm$ 0.009 | 1.294 $\pm$ 0.009 | 1.291 $\pm$ 0.008 | 1.293 $\pm$ 0.008

Table 1: We evaluate policies in real-world food rescue contexts by developing
situations that mirror notifications ($N=100,K=50$) and phone calls
($N=20,K=10)$. Our policies outperform baselines for both situations and
achieve similar results due to the nearly linear reward function.

##  7 Related Works and Problem Setup

Multi-armed Bandits In our work, we explore multi-armed bandits with two
properties: combinatorial actions [20] and non-separable rewards.
Combinatorial bandits can be solved through follow-the-perturbed-leader
algorithms [21], which are necessary because the large action space causes
traditional linear bandit algorithms to be inefficient [18]. Prior work has
tackled non-separable rewards in slate bandits [22], through an explore-then-
commit framework, and adversarial combinatorial bandits [23], from a minimax
optimality perspective. In this work, we leverage the structure of rmab-gs to
tackle both combinatorial actions and non-separable rewards.

Submodular Bandits Additionally related to our work are prior investigations
into submodular bandits. Submodular bandits combine submodular functions with
bandits and have been investigated from an explore-then-commit perspective
[24] and through upper confidence bound (UCB) algorithms [25]. Similar to
prior work, we focus on optimizing submodular functions under uncertainty.
However, prior work focuses on learning the reward structure when the
submodular function is unknown, while we focus on learning optimal decisions
when state transitions are stochastic.

Restless Multi-Armed Bandits rmabs extend multi-armed bandits to situations
where unpulled arms can transition between states [1]. While finding optimal
solutions to this problem is PSPACE-Hard [26], index-based solutions are
efficient and asymptotically optimal [2]. As a result, rmabs have been used
across a variety of domains [4, 3, 27] and have been deployed in public health
scenarios [6]. While prior work has relaxed assumptions by considering rmabs
that have contexts [28], combinatorial arms [29], graph-based interactions
[30], and global state [31], we focus on combinatorial situations with a
global reward.

##  8 Limitations and Conclusion

Limitations \- While we present approximation bounds for index-based policies,
our adaptive policies lack theoretical guarantees. Developing bounds for
adaptive policies is difficult due to the difficulty in leveraging Whittle
index optimality. However, these bounds may explain the empirical performance
of adaptive policies. Our empirical analysis is limited to one real-world
dataset (food rescue). We aimed to mitigate this by exploring different
scenarios within food rescue, but empirical evaluation in domains such as peer
review would be valuable. Finally, evaluating policies when global rewards are
neither submodular nor monotonic would improve our understanding of rmab-g.

Conclusion \- rmabs fail to account for situations with non-separable global
rewards, so we propose the rmab-g problem. We tackle rmab-g by developing
index-based, iterative, and MCTS policies. We prove performance bounds for
index-based policies and empirically find that iterative and MCTS policies
perform well on synthetic and real-world food rescue datasets. Our results
show how rmabs can extend to scenarios where rewards are global and non-
separable.

## Acknowledgements

We thank Gati Aher and Gaurav Ghosal for the comments they provided on an
earlier draft of this paper. We additionally thank Milind Tambe for his
comments. This work was supported in part by NSF grant IIS-2200410. Co-author
Raman is also supported by an NSF Fellowship. Co-author Shi is supported in
part by a Pitt Mascaro Center for Sustainable Innovation fellowship.

## References

  * Whittle [1988] Peter Whittle.  Restless bandits: Activity allocation in a changing world.  _Journal of applied probability_ , 25(A):287–298, 1988.
  * Weber and Weiss [1990] Richard R Weber and Gideon Weiss.  On an index policy for restless bandits.  _Journal of applied probability_ , 27(3):637–648, 1990.
  * Borkar et al. [2017] Vivek S Borkar, Gaurav S Kasbekar, Sarath Pattathil, and Priyesh Y Shetty.  Opportunistic scheduling as restless bandits.  _IEEE Transactions on Control of Network Systems_ , 5(4):1952–1961, 2017.
  * Li et al. [2021] Mushu Li, Jie Gao, Lian Zhao, and Xuemin Shen.  Adaptive computing scheduling for edge-assisted autonomous driving.  _IEEE Transactions on Vehicular Technology_ , 70(6):5318–5331, 2021.
  * Liu and Zhao [2010] Keqin Liu and Qing Zhao.  Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access.  _IEEE Transactions on Information Theory_ , 56(11):5547–5567, 2010.
  * Mate et al. [2020] Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe.  Collapsing bandits and their application to public health intervention.  _Advances in Neural Information Processing Systems_ , 33:15639–15650, 2020.
  * Shi et al. [2021] Zheyuan Ryan Shi, Leah Lizarondo, and Fei Fang.  A recommender system for crowdsourcing food rescue platforms.  In _Proceedings of the Web Conference 2021_ , pages 857–865, 2021.
  * Payan and Zick [2021] Justin Payan and Yair Zick.  I will have order! optimizing orders for fair reviewer assignment.  _arXiv preprint arXiv:2108.02126_ , 2021.
  * McElfresh et al. [2020] Duncan C McElfresh, Christian Kroer, Sergey Pupyrev, Eric Sodomka, Karthik Abinav Sankararaman, Zack Chauvin, Neil Dexter, and John P Dickerson.  Matching algorithms for blood donation.  In _Proceedings of the 21st ACM Conference on Economics and Computation_ , pages 463–464, 2020.
  * van den Berg et al. [2021] Pieter L van den Berg, Shane G Henderson, Caroline Jagtenberg, and Hemeng Li.  Modeling emergency medical service volunteer response.  _Available at SSRN 3825060_ , 2021.
  * Wang et al. [2023] Kai Wang, Lily Xu, Aparna Taneja, and Milind Tambe.  Optimistic whittle index policy: Online learning for restless bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 10131–10139, 2023.
  * Nemhauser et al. [1978] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.  An analysis of approximations for maximizing submodular set functions—i.  _Mathematical programming_ , 14:265–294, 1978.
  * Chateauneuf and Cornet [2022] Alain Chateauneuf and Bernard Cornet.  Submodular financial markets with frictions.  _Economic Theory_ , 73(2):721–744, 2022.
  * Prajapat et al. [2023] Manish Prajapat, Mojmír Mutnỳ, Melanie N Zeilinger, and Andreas Krause.  Submodular reinforcement learning.  _arXiv preprint arXiv:2307.13372_ , 2023.
  * Shapley et al. [1953] Lloyd S Shapley et al.  A value for n-person games.  1953\.
  * Ghosh et al. [2022] Abheek Ghosh, Dheeraj Nagaraj, Manish Jain, and Milind Tambe.  Indexability is not enough for whittle: Improved, near-optimal algorithms for restless bandits.  _arXiv preprint arXiv:2211.00112_ , 2022.
  * Kocsis and Szepesvári [2006] Levente Kocsis and Csaba Szepesvári.  Bandit based monte-carlo planning.  In _European conference on machine learning_ , pages 282–293. Springer, 2006.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Mnih et al. [2013] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Cesa-Bianchi and Lugosi [2012] Nicolo Cesa-Bianchi and Gábor Lugosi.  Combinatorial bandits.  _Journal of Computer and System Sciences_ , 78(5):1404–1422, 2012.
  * Kalai and Vempala [2005] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Rhuggenaath et al. [2020] Jason Rhuggenaath, Alp Akcay, Yingqian Zhang, and Uzay Kaymak.  Algorithms for slate bandits with non-separable reward functions.  _arXiv preprint arXiv:2004.09957_ , 2020.
  * Han et al. [2021] Yanjun Han, Yining Wang, and Xi Chen.  Adversarial combinatorial bandits with general non-linear reward functions.  In _International Conference on Machine Learning_ , pages 4030–4039. PMLR, 2021.
  * Fourati et al. [2024] Fares Fourati, Christopher John Quinn, Mohamed-Slim Alouini, and Vaneet Aggarwal.  Combinatorial stochastic-greedy bandit.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 38, pages 12052–12060, 2024.
  * Takemori et al. [2020] Sho Takemori, Masahiro Sato, Takashi Sonoda, Janmajay Singh, and Tomoko Ohkuma.  Submodular bandit problem under multiple constraints.  In _Conference on Uncertainty in Artificial Intelligence_ , pages 191–200. PMLR, 2020.
  * Papadimitriou and Tsitsiklis [1994] Christos H Papadimitriou and John N Tsitsiklis.  The complexity of optimal queueing network control.  In _Proceedings of IEEE 9th annual conference on structure in complexity Theory_ , pages 318–322. IEEE, 1994.
  * Bhattacharya [2018] Biswarup Bhattacharya.  Restless bandits visiting villages: A preliminary study on distributing public health services.  In _Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies_ , pages 1–8, 2018.
  * Liang et al. [2024] Biyonka Liang, Lily Xu, Aparna Taneja, Milind Tambe, and Lucas Janson.  A bayesian approach to online learning for contextual restless bandits with applications to public health.  _arXiv preprint arXiv:2402.04933_ , 2024.
  * Xu et al. [2023] Lily Xu, Bryan Wilder, Elias B. Khalil, and Milind Tambe.  Reinforcement learning with combinatorial actions for coupled restless bandits.  In _arXiv_ , 2023.
  * Herlihy and Dickerson [2023] Christine Herlihy and John P Dickerson.  Networked restless bandits with positive externalities.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 11997–12004, 2023.
  * Gafni et al. [2022] Tomer Gafni, Michal Yemini, and Kobi Cohen.  Learning in restless bandits under exogenous global markov process.  _IEEE Transactions on Signal Processing_ , 70:5679–5693, 2022.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Feige [1998] Uriel Feige.  A threshold of ln n for approximating set cover.  _Journal of the ACM (JACM)_ , 45(4):634–652, 1998.
  * Schrijver [2003] Alexander Schrijver.  A course in combinatorial optimization.  _CWI, Kruislaan_ , 413:1098, 2003.

## Broader Impact

In this paper, we analyze the use of restless multi-armed bandits to tackle
general reward functions and apply this to real-world problems in food rescue.
Our goal is to develop practically motivated and theoretically insightful
algorithms. With this goal, we evaluate our algorithms on real-world data to
understand whether such decision-making algorithms have real-world validity.
Our proposed algorithms and analysis are a step towards improving the
deployment of restless multi-armed bandit algorithms in real-world situations
such as food rescue.

##  Appendix A Experimental Details

We provide additional details on our experiments and experimental conditions.
For all experiments in the main paper, we run experiments for 15 seeds, and
for each seed, we run experiments across 5 choices of initial state (5
trials). For all ablations in the Appendix, we run for 9 seeds and run
experiments across 5 choices of initial state. Random seeds change the reward
parameters ($m_{i}$ or $Y_{i}$) and the transitions. For all plots, we plot
the normalized reward averaged across seeds along with the standard error. We
compute the discounted reward with an infinite time horizon and normalize this
as the improvement over the random policy. We do this so that we can
standardize the magnitude of rewards, as such a magnitude can vary across
rewards and selections of reward parameters. For all experiments $\gamma=0.9$.
We estimate the infinite-horizon discounted reward by computing the discounted
reward for $T=50$ timesteps; we do this because for $t>50$, $\gamma^{t}\leq
0.005$, and so we can compute the discounted reward with only a small
difference from the infinite time horizon.

To construct synthetic transitions, we consider a parameter $q$, and let
$P_{i}(0,0,1)\sim U(0,q)$ where $U$ is the uniform distribution. Then
$P_{i}(1,0,1)\sim U(P_{i}(0,0,1),1)$ and $P_{i}(0,1,1)\sim U(P_{i}(0,0,1),1)$.
Finally, $P_{i}(1,1,1)\sim U(\max(P_{i}(1,0,1),P_{i}(0,1,1)),1)$. We construct
transitions in such a way so that being in $s_{i}=1$ or playing action
$a_{i}=1$ can only help with these synthetic transitions, which matches from
prior work [11]. We vary $q$ in Appendix G, and find similar results across
selections of $q$.

We additionally detail some of the choices for parameters for each of the
rewards used in Section 6.1. For the Linear, Probability, and Max rewards, we
select $m_{1},\cdots,m_{N}\sim U(0,1)$. For the Probability distribution, such
a selection is natural (as probabilities are between 0 and 1), while for the
Linear and Max reward, we find similar results no matter the distribution of
$m_{i}$ chosen. We consider different selections for the sizes of the subset
and use these different sizes to investigate the impact of linearity on
performance. By default, we let $m=20$ and let $Y_{i}$ be sets of size $6$. We
select such a size so that $R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$ is non-
linear in $|Y_{i}|$, as when $|Y_{i}|$ is too small the problem becomes more
linear (because $Y_{i}\cap Y_{j}$ is empty).

To understand the impact of linearity, we construct the sets $Y_{i}$ in such a
way to control $\theta_{\mathrm{linear}}$. In particular, we consider two
parameters $a$ and $b$. We construct $K$ (where $K$ is the budget) sets which
where $Y_{i}=\\{1,2,\cdots,b\\}$, and we construct $N-K$ disjoint sets which
are size $a<b$. For the $N-K$ disjoint sets, they would be
$\\{1,2,\cdots,a\\},\\{a+1,a+2\cdots,2a\\},\cdots$. Under this construction,
$\theta_{\mathrm{linear}}=\frac{b}{Ka}$. We then vary $b\in\\{3,4,5\\}$, and
vary $a\in\\{1,\cdots,b-1\\}$, then compute the performance of each policy for
each of these rewards. Constructing sets in this way allows us to directly
measure the impact of linearity on performance, as we can control the
linearity of the reward function by varying $a$ and $b$.

We run all experiments on a TITAN Xp with 12 GB of GPU RAM running on Ubuntu
20.04 with 64 GB of RAM. Each policy runs in under 30 minutes, and we use
300-400 hours of computation time for all experiments. We develop dqn policies
using PyTorch [32].

##  Appendix B Baseline Details

We provide additional details on select baselines here:

  1. 1.

DQN \- We develop a Deep Q Network (dqn), where a state consists of the set of
arms pulled and the current state of all arms. The arms correspond to a new
arm to pull; we structure the dqn to avoid the number of actions being
exponential in the budget (which is often linear in the number of arms). We
train the dqn for 100 epochs and evaluate with other choices in Appendix F. We
let the learning rate be $5*10^{-4}$, a batch size of 16, and an Adam
optimizer. We use an MLP with a 128-dimension as our hidden layer, and use 2
such hidden layers. We use ReLu activation for all layers. We provide more
details on training dqns in our supplemental codebase.

  2. 2.

DQN Greedy \- Inspired by Theorem 3, we combine a dqn with greedy search. We
first learn a dqn network where states directly correspond to the states of
the arms, and actions correspond to subsets of arms pulled. Due to the large
number of actions, such a method does not scale when the number of arms is
increased (as the number of actions is exponential in the budget). Using this
learned Q function, we greedily select arms one-by-one, until $K$ total arms
are selected. We let the learning rate be $5*10^{-4}$, a batch size of 16, and
an Adam optimizer.

  3. 3.

MCTS \- We run our MCTS baseline algorithm and use the upper confidence tree
algorithm [17]. We run this for 400 iterations, and recurse until a depth of
$2*K$ is reached; we detail other choices for this in Appendix E. We select a
depth of $2K$ so that arm selections are non-myopic. By letting the depth be
$K$, the MCTS algorithm would simplify into a better version of greedy search,
whereas we want to see if we can non-myopically select arms using MCTS.

##  Appendix C Policy Details

We provide details for each of our policies below. For Shapley-based methods,
we approximate the Shapley value by computing 1000 random samples of
combinations. We do this because computing the exact Shapley value takes
exponential time in the number of arms. In Section 6, we consider the impact
of other choices on the efficiency and performance of models.

We additionally provide the pseudo-code for our MCTS Shapley-Whittle and MCTS
Linear-Whittle algorithms (Algorithm 1), and note that these follow from the
typical upper confidence trees framework, varying only in the rollout step. We
let $\epsilon=0.1$ for the rollout function, and let $c=5$.

Algorithm 1 Monte Carlo Tree Search for RMABs

Input: State $\mathbf{s}$, reward function $R(\mathbf{s},\mathbf{a})$, Q
functions $Q^{L}_{i,w}(s_{i},a_{i},p_{i})$ or
$Q^{S}_{i,w}(s_{i},a_{i},u_{i})$, and transitions $P_{1},\cdots,P_{N}$, number
of MCTS trials $M$, and hyperparameter $c$

Output: Action $\mathbf{a}$

Initialize a tree, $T$, with leafs representing $K$ arms pulled

Let $v_{m}$ represent the total value of a node $m$

Let $n_{m}$ represent the number of visits to a node $m$

for $t=1$ to $M$ do

Let $m$ be the root of $T$

Let $l$ be empty set

while $m$ is non-leaf do

Add $m$ to $l$

if $m$ has an unexplored child then

while $m$ is non-leaf do

With probability $\epsilon$, let $m^{\prime}$ be a random unexplored child of
$m$

Otherwise, let $m^{\prime}$ be the unexplored child of $m$, with the largest
value of $w_{i}(s_{i})$, where $w_{i}(s_{i})$ is either the Linear or Shapley-
Whittle index

Add $m^{\prime}$ to $l$

Let $m=m^{\prime}$

end while

else

Let
$m^{\prime}=\mathrm{argmax}_{m^{\prime}}\frac{v_{m^{\prime}}}{n_{m^{\prime}}}+c\sqrt{\frac{n_{m}}{n_{m^{\prime}}}}$

Let $m=m^{\prime}$

end if

end while

Compute action $\mathbf{a}$ from nodes played, $l$

For MCTS Linear-Whittle, let
$r=R(\mathbf{s},\mathbf{a})+\sum_{i=1}^{N}[Q_{i,w}^{L}(s_{i},a_{i},p_{i})-p_{i}(s_{i})a_{i}-R_{i}(s_{i},a_{i})]$

For MCTS Shapley-Whittle,
$r=R(\mathbf{s},\mathbf{a})+\sum_{i=1}^{N}[Q_{i}^{S}(s_{i,w},a_{i},u_{i})-u_{i}(s_{i})a_{i}-R_{i}(s_{i},a_{i})]$

for $m\in l$ do

Update $w_{m}\leftarrow w_{m}+r$

Update $n_{m}\leftarrow n_{m}+1$

end for

end for

return The action corresponding to the leaf, $m$, with the highest
$\frac{w_{m}}{n_{m}}$

##  Appendix D Food Rescue Details

(a)

(b)

Figure 4: We plot the (a) transition probabilities obtained by clustering
volunteers with various levels of experience and (b) the distribution of match
probabilities across all volunteers. We see that as volunteers gain more
experience, they are more likely to become engaged when notified. However, we
see that most volunteers have a low probability of responding, which motivates
the need for large budgets in notification.

To apply the food rescue scenario to rmabs, we compute aggregate transition
probabilities for volunteers through clustering. Each volunteer in the food
rescue performs a certain number of trips, and we use this information to
construct clusters. We ignore volunteers who have performed 1 or 2 trips, as
those volunteers have too little information to construct transition functions
for. We construct 100 clusters of roughly equal size, where each cluster
consists of volunteers who perform a certain number of trips; for example, the
1st cluster consists of all volunteers who perform 3 trips, and the 90th
cluster is those who perform 107-115 trips. From this, we compute transition
probabilities by letting the state (which represents engagement) denote
whether a volunteer has completed a trip in the past two weeks. We then see if
completing a trip in the current two weeks impacts the chance that they
complete a trip in the next two weeks. We use this as a proxy for engagement
due to the lack of ground truth information on whether a volunteer is truly
engaged. We average this over all volunteers in a cluster and across time
periods to compute transition probabilities. We present examples of such
transition probabilities in Figure 4. To compute the corresponding match
probabilities for each volunteer, we compute the fraction of notifications
they accept, across all notifications seen. This way, each arm corresponds to
a cluster of volunteers, with a transition probability and match probability.
We compute match probabilities on a per-volunteer basis so that multiple arms
can have the same transition probability (corresponding to volunteers being in
the same cluster) while differing in match probability. Such a situation
corresponds to the real world as well; not all volunteers who complete between
107-115 trips have the same match probability.

We analyze the distribution of match probabilities for each volunteer, across
all trips that they are notified for. We find that most volunteers accept less
than 2% of the trips they’ve seen, while a few volunteers answer more than 10%
(Figure 4). We note the difference between our two scenarios: notifications
and phone calls. For notifications, we consider all volunteers and notify a
large fraction of these volunteers, while for phone calls, we consider only
volunteers who have completed more than 100 trips, as they generally have a
higher match probability. We then cluster those volunteers into 20 groups and
similarly compute transition probabilities. We do this because food rescue
organizations target more active volunteers when making phone calls due to the
limited number of phone calls that can be made.

##  Appendix E Vanilla MCTS Experiments

(a)

(b)

Figure 5: We compare the performance of vanilla MCTS algorithms when varying
(a) depth of exploration and (b) the number of test iterations. We find that,
no matter the choice of depth or test iterations, MCTS performs worse than
Linear-Whittle. Moreover, as expected, increasing test iterations improves
performance, while lower depth improves MCTS performance due to the difficulty
in estimating rewards from transitions.

To understand the impact of our choice of hyperparameters for the MCTS
baseline algorithm, we vary the depth of the MCTS search, along with the
number of iterations. We vary the depth of MCTS in $\\{1K,2K,4K\\}$ (while
setting the iterations to $400$), and we vary the number of iterations run for
MCTS in $\\{50,100,200,400\\}$ (while searching up to depth $2K$). For all
runs, we let $K=5$ and $N=10$ for the Max reward.

In Figure 5, we see that increasing MCTS depth only lowers performance, while
increasing the number of iterations MCTS is run for increases performance.
This is due to the stochasticity in rewards as the depth of exploration
increases; there are $|\mathcal{S}|^{N}$ possible combinations of states,
making exploration difficult. We find that for any combination of iterations
and depth, the performance of MCTS lags significantly behind Linear-Whittle.
While running MCTS for additional iterations would be helpful, this comes at a
cost of time, so we run MCTS for $400$ iterations throughout our experiments
to balance these.

##  Appendix F Deep Q Networks

Figure 6: We compare the impact of additional training epochs on the
performance of a dqn baseline. We find that, regardless of the number of
training episodes, Linear-Whittle outperforms the dqn baseline. Additional
training episodes do not result in a significantly better performance
(compared with Linear-Whittle), showing that additional training episodes do
not lead to a much smaller gap between Linear-Whittle and the dqn baseline.

We compare the performance of our reinforcement learning baseline (dqn) to the
Linear-Whittle policy as we vary the number of epochs that the dqn is trained
for. We vary the number of train epochs in $\\{50,100,200,400\\}$ and plot our
results in Figure 6. We see that increasing the number of iterations does not
provide a big advantage in performance; this is because dqn fails to learn
past $50$ epochs, and so additional training steps do not lead to much better
performance. Moreover, we see that, no matter the selection of train
iterations, dqn performs worse than Linear-Whittle. We believe the reason for
this is the stochasticity in the dataset; because the number of actions is
large, it becomes difficult to learn state values in this scenario, which
leads to the poor performance of dqn.

##  Appendix G Synthetic Transitions

Figure 7: We assess the impact of changing $q$, which parametrizes transition
probabilities. Smaller $q$ makes it less likely that arms transition to the
$1$ state. We find that, regardless of the transition probability chosen, MCTS
Shapley-Whittle policies improve upon all other policies.

Throughout our experiments, we sample synthetic transitions, with a maximum
probability for $P_{i}(0,1,0)$ of $q$; we vary the value of $q$ to understand
if this impacts the performance of policies. We vary
$q\in\\{0,0.25,0.5,0.75,1.0\\}$, and evaluate the performance of our policies
on the Max reward.

We find that, across all values of $q$, the MCTS Shapley-Whittle policy
performs best. We find large gaps between MCTS Shapley-Whittle and Linear-
Whittle for small $q$; in these scenarios, the transitions are more
stochastic, leading to greater impact from MCTS Shapley-Whittle. However,
regardless of the choice of $q$, our conclusion remains that Iterative and
MCTS Shapley-Whittle policies outperform other alternatives.

##  Appendix H Other Constructions of Transitions

Figure 8: We construct situations where adaptive policies are needed to
perform better than baselines. When $N=4$, Iterative Shapley-Whittle
significantly outperforms alternatives, and when $N=10$, MCTS Shapley-Whittle
outperforms alternatives.

We investigate whether situations detailed in Lemma 8 can be tackled by
adaptive algorithms. We construct a situation for the Max reward where
transitions are $P_{i}(s,1,0)=1$ and $P_{i}(s,0,s)=1$; pulling an arm always
leads to $s_{i}=0$, and otherwise, arms stay in their current state. We design
such a situation to see whether adaptive policies can perform well in
situations where index-based policies are proven to perform poorly. We let the
values $m_{1}=m_{2}=1$, then let the other choices of $m_{i}=0$. We do this to
encourage arms to be pulled one at a time, rather than pulling $m_{1}$ and
$m_{2}$ together. In Figure 8, we compare the performance of policies in this
situation and see that Iterative Shapley-Whittle significantly outperforms all
other policies when $N=4$, and that MCTS Linear- and Shapley-Whittle
outperform all other policies when $N=10$. When $N=10$, we see that all non-
adaptive Whittle policies achieve similar performance, demonstrating the need
for adaptive policies.

##  Appendix I Other Combinations of Arms and Budget

Figure 9: We repeat Figure 1 for $N=25$ and $N=100$. We find that many of the
same trends appear here; namely, that MCTS Shapley-Whittle outperforms all
other policies, and Shapley-based policies do better in general.

#### More arms

We evaluate the performance of policies when $N=25$ or $N=100$ and plot this
in Figure 9. We run Iterative Shapley-Whittle, MCTS Linear-Whittle, and MCTS
Shapley-Whittle policies for $N=25$ and refrain from running them when $N=100$
due to the time needed. We find that MCTS Shapley-Whittle policies perform
better than alternatives, and that they perform significantly better than
Linear-Whittle policies. The results with $N=25$ and $N=100$ confirm the
trends from Section 6.1 even when the number of arms is large.

Figure 10: We vary the parameter $\alpha$, which modulates between the
individual rewards $R_{i}$ and the global reward $R_{\mathrm{glob}}$. When
$\alpha=1$, all policies perform similarly, while for
$\alpha\in\\{0.25,0.5,0.75\\}$, we see that Linear-Whittle performs worse than
other policies. Across values of $\alpha$, baselines perform worse than all
policies, which is most notable when $\alpha=0$.

#### Weighting Individual and Global Rewards

Throughout our experiments, we weight the impact of the global reward,
$R_{\mathrm{glob}(\mathbf{s},\mathbf{a})}$, and the individual reward,
$R_{i}(s_{i},a_{i})$, equally. We evaluate the impact of various weighting
factors so that
$R(\mathbf{s},\mathbf{a})=(1-\alpha)R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})+\alpha\sum_{i=1}^{N}R_{i}(\mathbf{s},\mathbf{a})$.
By default, $\alpha=0.5$ throughout our experiments, so we vary
$\alpha\in\\{0,0.25,0.5,0.75,1.0\\}$ and evaluate the reward for baselines and
our policies on the maximum reward.

In Figure 10, we see that, regardless of the choice of $\alpha$, our policies
outperform baselines. We additionally see that the Shapley-Whittle and
Iterative Shapley-Whittle perform well across the choices of $\alpha$,
implying that the results we found with $\alpha=0.5$ are not limited to one
choice of $\alpha$.

Figure 11: We vary the budget, $K$, while fixing $N=10$ for the maximum
reward. We see that, for any choice of $K$, all policies have a larger reward
than greedy, and that Linear-Whittle policies perform worse than other
policies. Moreover, for $K=5$ and $K=8$, Iterative Shapley-Whittle policies
outperform Iterative Linear-Whittle policies, while for $K=2$ policies,
Iterative Linear-Whittle policies perform well, potentially due to the
linearity of the problem with small $K$.

#### Varying Budget

Throughout our experiments, we let the budget, $K=0.5N$, so we analyze the
impact of varying $K$ when fixing $N=10$. We vary $K\in\\{2,5,8\\}$, and note
that with $K=10$ or $K=0$, all policies perform the same (as all or no arms
are selected). We see that, across all choices of budget, Linear-Whittle
performs worse than all other policies (Figure 11). Moreover, we see again
that regardless of the choice of $K$, MCTS Shapley-Whittle is the best policy.

##  Appendix J Food Rescue More Arms

Figure 12: We compare the performance of policies on the food rescue dataset
for two situations: (a) notifications, when $N=1000$ and $K=500$, and (b)
phone calls, when $N=250$ and $K=50$. We find that when $N$ is large, all
policies perform similarly, due to the linearity of the problem for large $N$.

In addition to the experiments in Section 6.2, we evaluate the impact of
increasing the number of arms in food rescue on the performance of various
policies. We consider a situation with $N=1000$ and $K=250$, for the
notification scenario, and another situation with $N=250$ and $K=5$, which
corresponds to the phone calls scenario. We plot both situations in Figure 12,
and we see that all policies perform similarly in both of these situations.
When the number of arms is this large, all policies will select the top arms
as arms are likely to have a large match probability due to the sheer number
of arms. We can differentiate between policies in the notification scenario,
where Shapley-Whittle policies perform better than Linaer-Whittle policies,
but in the phone calls settings, all policies perform similarly. Additionally,
due to the large budget, the match probability will be large, so policies
should focus on engagement in this scenario. In reality, the choice of whether
to use pre-computed index policies or adaptive policies depends on the time
available, the size of the problem, and the structure of the reward.

##  Appendix K Proofs of Problem Difficulty

######  Theorem 1.

The restless multi-armed bandit with global rewards is PSPACE-Hard.

###### Proof.

We reduce rmab to rmab-g. Note that rmab-g aims to maximize

$\sum_{t=0}^{\infty}\gamma^{t}(R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})+\sum_{i=1}^{N}R_{i}(s_{i},a_{i}))$
(9)

Consider an rmab instance with reward $R^{\prime}_{i}(s_{i},a_{i})$. We can
construct an instance of rmab-g with $R_{i}=R^{\prime}_{i}$ and with
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})=0$. Therefore, we have reduced rmab
to rmab-g. Because rmab is PSPACE-Hard [26], rmab-g is as well. ∎

######  Theorem 2.

No polynomial time algorithm can achieve better than a $1-\frac{1}{e}$
approximation to the restless multi-armed bandit with global rewards problem.

###### Proof.

Consider any submodular function $F(S):2^{\Omega}\rightarrow\mathbb{R}$ and a
cardinality constraint $|S|\leq K$. Unless $P=NP$, maximizing $F(S)$ with a
cardinality constraint can only be approximated up to a factor of
$1-\frac{1}{e}$ [33]. Next, we will show that we can reduce submodular
maximization to rmab-g.

For a given submodular function $F$, we construct an instance of rmab-g with
$\mathcal{S}=\\{0,1\\}$. Let $\mathbf{s}^{(0)}=\mathbf{1}$, where $\mathbf{1}$
is the vector of $N$ 1s. Finally let $P_{i}(s,a,0)=1$, so that all arms are in
state $0$ for timesteps $t>0$. Let $R(\mathbf{s},\mathbf{a})=0$ if
$\mathbf{s}\neq\mathbf{1}$, and let
$R(\mathbf{s},\mathbf{a})=F(\\{i|a_{i}=1\\})$ otherwise. Note that only at
time $t=0$ can you achieve any reward, as afterwards, $F(S)=0$.

The optimal solution to the rmab-g problem is the action, $\mathbf{a}$ that
maximizes $F(\\{i|a_{i}=1\\})$ subject to the constraint,
$\sum_{i=1}^{N}a_{i}\leq K$. Note that this is the same as the cardinality
constraint for submodular maximization, $|S|=\sum_{i=1}^{N}a_{i}$, along with
the function of interest, $F(S)$. Therefore, if we can efficiently solve
rmab-g, then we can efficiently solve the original submodular maximization
problem in $F$. Because we cannot do better than a $1-\frac{1}{e}$
approximation to the submodular maximization problem in polynomial time, we
cannot do better than a $1-\frac{1}{e}$ approximation to the rmab-g problem. ∎

######  Lemma 9.

Let $\mathcal{P}$ be a set of transition functions,
$P_{1},\cdots,P_{N}\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$,
where $N$ is the number of arms. Let $\mathcal{S}=\mathcal{A}=\\{0,1\\}$. Let
$Q_{\pi}(\mathbf{s},\mathbf{a})=\mathbb{E}_{(\mathbf{s^{\prime}},\mathbf{a^{\prime}})\sim(\mathcal{P},\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s^{\prime}},\mathbf{a^{\prime}}))|\mathbf{s_{0}}=\mathbf{s},\mathbf{a_{0}}=\mathbf{a}]$
for some policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$, and let $\pi^{*}$ be
the optimal policy. Let
$V_{\pi^{*}}(\mathbf{s})=\max\limits_{\mathbf{a}}Q_{\pi}(\mathbf{s},\mathbf{a})$.
If $R(\mathbf{s},\mathbf{a})$ is monotonic in $\mathbf{s}$ and
$P_{i}(1,a,1)\geq P_{i}(0,a,1)$ for any $a$, then $V_{\pi^{*}}(\mathbf{s})$ is
monotonic in $\mathbf{s}$

###### Proof.

We construct $V_{\pi^{*}}(\mathbf{s})$ by stepping through inductive steps in
value iteration, and showing that the monotonicity property is preserved
throughout these steps. We note that performing Value iteration from any
initialization results in the optimal policy, $V_{\pi^{*}}(\mathbf{s})$

Let $Q^{(t)}(\mathbf{s},\mathbf{a})$ represent the $Q$ value for iteration $t$
of Value iteration, and let $V^{(t)}(\mathbf{s})$ be the value function for
iteration $t$. We initialize $V^{(0)}(\mathbf{s})=0$ for any $\mathbf{s}$, and
note that the initialization should not impact the process. Running an
iteration of value iteration leads
$Q^{(1)}(\mathbf{s},\mathbf{a})=R(\mathbf{s},\mathbf{a})$, so that
$V^{(1)}(\mathbf{s})=\max\limits_{\mathbf{a}}Q^{(1)}_{\pi^{*}}(\mathbf{s},\mathbf{a})$.

Base Case: Initially,
$V^{(1)}(\mathbf{s})=\max\limits_{\mathbf{a}}R(\mathbf{s},\mathbf{a})$. Next
consider any two states, $\mathbf{x}$ and $\mathbf{y}$, so that
$\mathbf{x}\geq\mathbf{y}$. Here $\mathbf{x}\geq\mathbf{y}$ implies that
$x_{i}\geq y_{i}\forall i$. Let
$\mathbf{a}^{*}=\mathrm{argmax}_{\mathbf{a}}R(\mathbf{y},\mathbf{a})$. Then
$V^{(1)}(\mathbf{y})=R(\mathbf{y},\mathbf{a}^{*})\leq
R(\mathbf{x},\mathbf{a}^{*})\leq V^{(1)}(\mathbf{x})$. Therefore,
$V^{(1)}(\mathbf{s})$ is monotonic.

Inductive Hypothesis: Assume that $V^{(t-1)}(\mathbf{s})$ is monotonic in
$\mathbf{s}$.

Next, we will prove that
$V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})-V^{(t)}(\mathbf{s})\geq 0$. Here
$\mathbf{e}_{i}$ is the vector with 1 at location $i$ and 0 everywhere else.

Before proving this, we will first show that this implies monotonicity for any
two states $\mathbf{s},\mathbf{s}^{\prime}$. Suppose that
$V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})-V^{(t)}(\mathbf{s})\geq 0$. Then
consider some pair of states, $\mathbf{s}\geq\mathbf{s}^{\prime}$. Because
$\mathcal{S}=\mathcal{A}=\\{0,1\\}$, if $\mathbf{s}\geq\mathbf{s^{\prime}}$,
then we can write $\mathbf{s}=\mathbf{s^{\prime}}\lor\bigvee_{i\in
X}\mathbf{e}_{i}$ for some set $X=\\{x_{1},x_{2},\cdots,x_{n}\\}$. If
$V^{(t)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})\geq
V^{(t)}(\mathbf{s}^{\prime})$, then
$V^{(t)}((\mathbf{s}^{\prime}\lor\mathbf{e}_{x_{1}})\lor\mathbf{e}_{i})\geq
V^{(t)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{x_{1}})$

Therefore, this implies that

$V^{(t)}(\mathbf{s})-V^{(t)}(\mathbf{s^{\prime}})=\sum_{i=1}^{n}(V^{(t)}(\mathbf{s^{\prime}}\lor\bigvee_{j=1}^{i}\mathbf{e}_{x_{j}})-V^{(t)}(\mathbf{s^{\prime}}\lor\bigvee_{j=1}^{i-1}\mathbf{e}_{x_{j}}))\geq
0$ (10)

We get this by expanding $V^{(t)}(\mathbf{s})-V^{(t)}(\mathbf{s^{\prime}})$
into a telescoping series. Because each term in the sum is non-negative, the
whole sum is non-negative.

Next we prove our original statement: $V^{(t)}(\mathbf{s}+\mathbf{e}_{i})\geq
V^{(t)}(\mathbf{s})$. We first expand
$V^{(t)}(\mathbf{s})=R(\mathbf{s},\mathbf{a})+\gamma\sum_{\mathbf{s}^{\prime}}P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})V^{(t-1)}(\mathbf{s}^{\prime})$
for some $\mathbf{a}$, where
$P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})=\prod_{j=1}^{N}P_{j}(s_{j},a_{j},s^{\prime}_{j})$.
We note that $V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})\geq
R(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a})+\gamma\sum_{\mathbf{s}^{\prime}}P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime})V^{(t-1)}(\mathbf{s}^{\prime})$

Therefore:

$V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})-V^{(t)}(\mathbf{s})\geq
R(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a})-R(\mathbf{s},\mathbf{a})+\gamma\sum_{\mathbf{s}^{\prime}}(P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}))V^{(t-1)}(\mathbf{s}^{\prime})$
(11)

We note that
$R(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a})-R(\mathbf{s},\mathbf{a})\geq 0$
due to the monotonicity of $R$ with fixed $\mathbf{a}$.

Let $\mathcal{C}_{i}\subset\\{0,1\\}^{N}$ be the set of 0-1 vectors of length
$N$ so that if $x\in\mathcal{C}_{i}$ then $x_{i}=0$. Additionally, let
$\delta_{i}=P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\lor\mathbf{e}_{i})$.
We note that

$\displaystyle\delta_{i}$
$\displaystyle=P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\lor\mathbf{e}_{i})$
$\displaystyle=\prod_{k=1}^{N}P_{k}((\mathbf{s}\lor\mathbf{e}_{i})_{k},a_{k},(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})_{k})-\prod_{k=1}^{N}P_{k}(s_{k},a_{k},(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})_{k})$
$\displaystyle=(P_{i}(1,a_{i},1)-P_{i}(s_{i},a_{i},1))\prod_{k=1,k\neq
i}^{N}P_{k}(s_{k},a_{k},s^{\prime}_{k})$ $\displaystyle\geq 0$

Let $\mathbf{1}_{i}$ be the vector of all 1s except at $i$. Let $\land$ be the
element-wise minimum operator. Then $\mathbf{s}\land\mathbf{1}_{i}$ sets
$s_{i}=0$ while leaving other indices unchanged. Because transition
probabilities add to one,
$P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime}\land\mathbf{1}_{i})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\land\mathbf{1}_{i})=-\delta_{i}$

Next:

$\displaystyle V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})-V^{(t)}(\mathbf{s})$
$\displaystyle\geq
R(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a})-R(\mathbf{s},\mathbf{a})+\gamma\sum_{\mathbf{s}^{\prime}}(P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}))V^{(t-1)}(\mathbf{s}^{\prime})$
$\displaystyle\geq\gamma\sum_{\mathbf{s}^{\prime}}(P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}))V^{(t-1)}(\mathbf{s}^{\prime})$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i}}(P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime}\land\mathbf{1}_{i})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\land\mathbf{1}_{i}))V^{(t-1)}(\mathbf{s}^{\prime}\land\mathbf{1}_{i})$
$\displaystyle+\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i}}(P(\mathbf{s}\lor\mathbf{e}_{i},\mathbf{a},\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime}\lor\mathbf{e}_{i}))V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i}}-\delta_{i}V^{(t-1)}(\mathbf{s}^{\prime}\land\mathbf{1}_{i})+\delta_{i}V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i}}\delta_{i}(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-V^{(t-1)}(\mathbf{s}^{\prime}\land\mathbf{1}_{i}))$
$\displaystyle\geq 0$

The second step splits the sum into transitions for states with
$\mathbf{s}^{\prime}_{i}=0$ and those with $\mathbf{s}^{\prime}_{i}=1$. The
final step applies the inductive hypothesis and noting that
$\mathbf{s}^{\prime}\lor\mathbf{e}_{i}\geq\mathbf{s}^{\prime}\land\mathbf{1}_{i}$.
∎

######  Lemma 10.

Let $\mathcal{P}$ be a set of transition functions,
$P_{1},\cdots,P_{N}\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$,
where $N$ is the number of arms. Let $\mathcal{S}=\mathcal{A}=\\{0,1\\}$. Let
$Q_{\pi}(\mathbf{s},\mathbf{a})=\mathbb{E}_{(\mathbf{s^{\prime}},\mathbf{a^{\prime}})\sim(\mathcal{P},\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s^{\prime}},\mathbf{a^{\prime}}))|\mathbf{s_{0}}=\mathbf{s},\mathbf{a_{0}}=\mathbf{a}]$
for some policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$, and let $\pi^{*}$ be
the optimal policy. Let
$V_{\pi^{*}}(\mathbf{s})=\max\limits_{\mathbf{a}}Q_{\pi}(\mathbf{s},\mathbf{a})$.
If $R(\mathbf{s},\mathbf{a})$ is submodular in both $\mathbf{s}$ and
$\mathbf{a}$, $g(\mathbf{s})=\max\limits_{\mathbf{a}}R(\mathbf{s},\mathbf{a})$
is submodular in $\mathbf{s}$, and $P_{i}(1,a,1)\geq P_{i}(0,a,1)$ for any
$a$, then $V_{\pi^{*}}(\mathbf{s})$ is submodular in $\mathbf{s}$.

###### Proof.

We similarly construct $V_{\pi^{*}}(\mathbf{s})$ through induction in the
value iteration steps.

Base Case: We start with the base case:
$V^{(1)}(\mathbf{s})=\max\limits_{\mathbf{a}}R(\mathbf{s},\mathbf{a})=g(\mathbf{s})$,
which is submodular by assumption.

Inductive Hypothesis: Again let $V^{(t)}(\mathbf{s})$ be the value function at
step $t$ of value iteration. We assume that $V^{(t-1)}(\mathbf{s})$ is
submodular, and aim to prove that
$V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})-V^{(t)}(\mathbf{s})-V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})+V^{(t)}(\mathbf{s}\lor\mathbf{e}_{j})\geq
0$. We note that this is an equivalent definition of submodularity [34].

Now, consider
$V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})-V^{(t)}(\mathbf{s})-V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})+V^{(t)}(\mathbf{s}\lor\mathbf{e}_{j})$.
The sum of submodular functions is submodular and note that
$V^{(t)}(\mathbf{s})=\max\limits_{\mathbf{a}}R(\mathbf{s},\mathbf{a})+\gamma\sum_{\mathbf{s}^{\prime}}V^{(t-1)}(\mathbf{s}^{\prime})P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})$.
We note that the first term is submodular by assumption, so we focus on
proving the submodularity of
$\gamma\sum_{\mathbf{s}^{\prime}}V^{(t-1)}(\mathbf{s}^{\prime})P(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})$.
Let $\mathcal{C}_{i,j}\subset\\{0,1\\}^{N}$ be the set of 0-1 vectors of
length $N$ so that if $x\in\mathcal{C}_{i,j}$ then $x_{i}=0,x_{j}=0$, and let
$\delta_{i}=P_{i}(1,a_{i},1)-P_{i}(s_{i},a_{i},1)$; note the different
definition of $\delta_{i}$ from the previous proof. Finally, let
$C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})=\prod_{l=1,l\neq
i,j}^{N}P_{l}(s_{l},a_{l},s^{\prime}_{l})$, then we can write the following:

$\displaystyle
V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i})-V^{(t)}(\mathbf{s})-V^{(t)}(\mathbf{s}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})+V^{(t)}(\mathbf{s}\lor\mathbf{e}_{j})$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-V^{(t-1)}(\mathbf{s}^{\prime}))\delta_{i}P_{j}(s_{j},a_{j},0)$
$\displaystyle+\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})-V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{j}))\delta_{i}(1-P_{j}(s_{j},a_{j},0))$
$\displaystyle-\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-V^{(t-1)}(\mathbf{s}^{\prime}))\delta_{i}(P_{j}(1,a_{j},0))$
$\displaystyle-\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})-V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{j}))\delta_{i}(1-P_{j}(1,a_{j},0))$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})\delta_{i}(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-V^{(t-1)}(\mathbf{s}^{\prime}))(P_{j}(s_{j},a_{j},0)-P_{j}(1,a_{j},0))$
$\displaystyle+\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})\delta_{i}(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})-V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{j}))(P_{j}(1,a_{j},0)-P_{j}(s_{j},a_{j},0))$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})\delta_{i}\delta_{j}(V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})+V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i})-V^{(t-1)}(\mathbf{s}^{\prime})-V^{(t-1)}(\mathbf{s}^{\prime}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j}))$
$\displaystyle\geq 0$

The last step arises because $\delta_{i}$,
$C(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})$ are all non-negative, and the
inductive hypothesis. ∎

######  Theorem 3.

Consider an rmab-g instance
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$. Let
$Q_{\pi}(\mathbf{s},\mathbf{a})=\mathbb{E}_{(\mathbf{s^{\prime}},\mathbf{a^{\prime}})\sim(\mathcal{P},\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s^{\prime}},\mathbf{a^{\prime}}))|\mathbf{s}^{(0)}=\mathbf{s},\mathbf{a}^{(0)}=\mathbf{a}]$
and let $\pi^{*}$ be the optimal policy. Let
$\mathbf{a}^{*}=\operatorname*{arg\,max}_{\mathbf{a}}Q_{\pi^{*}}(\mathbf{s},\mathbf{a})$.
Suppose $P_{i}(s,1,1)\geq P_{i}(s,0,1)\forall s,i$, $P_{i}(1,a,1)\geq
P_{i}(0,a,1)\forall i,a$, $R(\mathbf{s},\mathbf{a})$ monotonic and submodular
in $\mathbf{s}$ and $\mathbf{a}$, and
$g(\mathbf{s})=\max\limits_{\mathbf{a}}R(\mathbf{s},\mathbf{a})$ submodular in
$\mathbf{s}$. Then with oracle access to $Q_{\pi^{*}}$ we can compute
$\hat{\mathbf{a}}$ in $\mathcal{O}(N^{2})$ time so
$Q_{\pi^{*}}(\mathbf{s},\hat{\mathbf{a}})\geq(1-\frac{1}{e})Q_{\pi^{*}}(\mathbf{s},\mathbf{a}^{*})$.

###### Proof.

We first demonstrate that $Q_{\pi^{*}}(\mathbf{s},\mathbf{a})$ is submodular
and monotonic in $\mathbf{a}$. Prior work demonstrates that monotonic
submodular function can be approximated within an approximation factor of
$1-\frac{1}{e}$ with $\mathcal{O}(N^{2})$ evaluations of the function, so all
that remains is to demonstrate submodularity [12].

We note that
$Q_{\pi^{*}}(\mathbf{s},\mathbf{a})=R(\mathbf{s},\mathbf{a})+\gamma\sum_{\mathbf{s}^{\prime}}V_{\pi^{*}}(\mathbf{s^{\prime}})P(\mathbf{s},\mathbf{a},\mathbf{s^{\prime}})$,
and that $R(\mathbf{s},\mathbf{a})$ is both monotonic and submodular in
$\mathbf{a}$. Therefore, we demonstrate that
$\gamma\sum_{\mathbf{s}^{\prime}}V_{\pi^{*}}(\mathbf{s^{\prime}})P(\mathbf{s},\mathbf{a},\mathbf{s^{\prime}})$
is monotonic and submodular in $\mathbf{a}$. Let
$H(\mathbf{a})=\gamma\sum_{\mathbf{s}^{\prime}}V_{\pi^{*}}(\mathbf{s^{\prime}})P(\mathbf{s},\mathbf{a},\mathbf{s^{\prime}})$
for fixed $\mathbf{s}$.

We start by demonstrating monotonicity. First, let
$\eta_{i}=P_{i}(s_{i},1,1)-P_{i}(s_{i},0,1)$, and by assumption, $\eta_{i}\geq
0$. Then:

$\displaystyle H(\mathbf{a}\lor\mathbf{e}_{i})-H(\mathbf{a})$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i}}V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i})(P(\mathbf{s},\mathbf{a}\lor\mathbf{e}_{i},\mathbf{s}\lor\mathbf{e}_{i})-P(\mathbf{s},\mathbf{a},\mathbf{s}\lor\mathbf{e}_{i}))$
$\displaystyle+\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i}}V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i})(P(\mathbf{s},\mathbf{a}\lor\mathbf{e}_{i},\mathbf{s}\land\mathbf{1}_{i})-P(\mathbf{s},\mathbf{a},\mathbf{s}\land\mathbf{1}_{i}))$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i}}\eta_{i}(V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i})-V_{\pi^{*}}(\mathbf{s}\land\mathbf{1}_{i}))\prod_{j=1,j\neq
i}^{N}P_{j}(s_{j},a_{j},s^{\prime}_{j})$ $\displaystyle\geq 0$

The last steps follows from the monotonicity of $V_{\pi^{*}}(\mathbf{s})$,
which was proven in Lemma 9.

Next, we prove submodularity of $H(\mathbf{a})$, by showing that
$H(\mathbf{a}\lor\mathbf{e}_{i})-H(\mathbf{a})-H(\mathbf{a}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})+H(\mathbf{a}\lor\mathbf{e}_{j})\geq
0$. That is

$\displaystyle
H(\mathbf{a}\lor\mathbf{e}_{i})-H(\mathbf{a})-H(\mathbf{a}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})+H(\mathbf{a}+\lor\mathbf{e}_{j})$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}\eta_{i}P_{j}(s_{j},a_{j},0)(V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i})-V_{\pi^{*}}(\mathbf{s}))+\eta_{i}(1-P_{j}(s_{j},a_{j},0))(V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})-V_{\pi^{*}}(\mathbf{s}))$
$\displaystyle-\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}\eta_{i}P_{j}(s_{j},1,0)(V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i})-V_{\pi^{*}}(\mathbf{s}))+\eta_{i}(1-P_{j}(s_{j},1,0))(V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j})-V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i}))$
$\displaystyle=\gamma\sum_{\mathbf{s}^{\prime}\in\mathcal{C}_{i,j}}\eta_{i}\eta_{j}(V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{i})+V_{\pi^{*}}(\mathbf{s}\lor\mathbf{e}_{j})-V_{\pi^{*}}(\mathbf{s})-V(\mathbf{s}\lor\mathbf{e}_{i}\lor\mathbf{e}_{j}))$
$\displaystyle\geq 0$

The last line follows from the submodularity of $V$, as proven in Lemma 10.
Therefore, we have shown that $Q_{\pi^{*}}(\mathbf{s},\mathbf{a})$ is
submodular, which completes the proof. ∎

##  Appendix L Proofs of Index-Based Bounds

###  L.1 Lower Bounds

######  Theorem 4.

For any fixed set of transitions, $\mathcal{P}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
for some $T$. For an rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$, let
$R^{\prime}_{i}(s_{i},a_{i})=R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i}$, and let
the induced linear rmab be
$(\mathcal{S},\mathcal{A},R^{\prime}_{i},P_{i},\gamma)$. Let
$\pi_{\mathrm{linear}}$ be the Linear-Whittle policy, and let
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$.
Define $\beta_{\mathrm{linear}}$ as

$\beta_{\mathrm{linear}}=\min\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i})}$
(12)

If the induced linear rmab is irreducible and indexable with the uniform
global attractor property, then
$\mathrm{ALG}\geq\beta_{\mathrm{linear}}\mathrm{OPT}$ asymptotically in $N$
for any set of transitions, $\mathcal{P}$.

###### Proof.

By the definition of the minimum,
$\beta_{\mathrm{linear}}\sum_{i=1}^{N}(p_{i}(s_{i})a_{i}+R_{i}(s_{i},a_{i}))\leq
R(\mathbf{s},\mathbf{a})\forall\mathbf{a},\mathbf{s}$.

Additionally, note that $\sum_{i=1}^{N}p_{i}(s_{i})a_{i}\geq
R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$. This holds because
$p_{i}(s_{i})=\max\limits_{\mathbf{s^{\prime}|s^{\prime}_{i}=s_{i}}}R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$.
So, $\sum_{i=1}^{N}p_{i}(s_{i})a_{i}\geq
R(\mathbf{s},\sum_{i=1}^{N}\mathbf{e}_{i}a_{i})=R(\mathbf{s},\mathbf{a})$ by
submodularity of $R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$.

We compare the linearized reward to the submodular reward for the set of
actions played by the Linear-Whittle policy $\pi_{\mathrm{linear}}$. Let the
actions be $\mathbf{a}^{(1)},\mathbf{a}^{(2)},\cdots$. If we play for $T$
iterations, then:

$\frac{\beta_{\mathrm{linear}}}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}(p_{i}(s_{i}^{(t)})a_{i}^{(t)}+R_{i}(s_{i}^{(t)},a_{i}^{(t)}))\leq\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s}^{(t)},\mathbf{a}^{(t)})$
(13)

Next, consider the following induced rmab with
$R^{\prime}_{i}(s_{i},a_{i})=R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i}$. By
assumption, our relaxed rmab is indexable, irreducible, and has a global
attractor. In this scenario, prior work [2] states that the Whittle index is
asymptotically optimal.

For this relaxed rmab problem, we note that the Whittle Index solution
corresponds exactly to the Linear-Whittle policy, $\pi_{\mathrm{linear}}$.
That is

$\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]$
(14)

Then, asymptotically,

$\displaystyle\mathrm{OPT}$
$\displaystyle=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
$\displaystyle\leq\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]$
$\displaystyle\leq\frac{1}{\beta_{\mathrm{linear}}}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]=\frac{1}{\beta_{\mathrm{linear}}}\mathrm{ALG}$

∎

######  Theorem 5.

For any fixed set of transitions, $\mathcal{P}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
for some $T$. For an rmab-g
$(\mathcal{S},\mathcal{A},R_{i},R_{\mathrm{glob}},P_{i},\gamma)$, let
$R^{\prime}_{i}(s_{i},a_{i})=R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i}$, and let
the induced Shapley rmab be
$(\mathcal{S},\mathcal{A},R^{\prime}_{i},P_{i},\gamma)$. Let
$\pi_{\mathrm{shapley}}$ be the Shapley-Whittle policy, and let
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{shapley}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$.
Define $\beta_{\mathrm{shapley}}$ as

$\beta_{\mathrm{shapley}}=\frac{\min\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i})}}{\max\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i})}}$
(15)

If the induced Shapley rmab is irreducible and indexable with the uniform
global attractor property, then
$\mathrm{ALG}\geq\beta_{\mathrm{shapley}}\mathrm{OPT}$ asymptotically in $N$
for any choice of transitions, $\mathcal{P}$.

###### Proof.

First, consider
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})]$.
First, note that
$R(\mathbf{s}^{\prime},\mathbf{a}^{\prime})\leq(\sum_{i=1}^{N}u_{i}(s^{\prime}_{i})a^{\prime}_{i}+R_{i}(s^{\prime}_{i},a^{\prime}_{i}))\max\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(u_{i}(s_{i})a_{i}+R_{i}(s_{i},a_{i}))}$.
Next, note that similar to Theorem 4, $\pi_{\mathrm{shapley}}$ is the optimal
policy for the rmab instance where
$R^{\prime}_{i}(s_{i},a_{i})=u_{i}(s_{i})a_{i}+R_{i}(s_{i},a_{i})$ for the
induced rmab (due to the indexability, irreducibility, and global attractor
properties [2]), or in other words,

$\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{shapley}})}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]$
(16)

Therefore,

$\displaystyle\mathrm{OPT}$
$\displaystyle=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
$\displaystyle\leq\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]\max\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(u_{i}(s_{i})a_{i}+R_{i}(s_{i},a_{i}))}$
$\displaystyle\leq\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{shapley}})}[\frac{1}{T}\sum_{t=0}^{T-1}\sum_{i=1}^{N}R^{\prime}_{i}(s_{i},a_{i})]\max\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(u_{i}(s_{i})a_{i}+R_{i}(s_{i},a_{i}))}$
$\displaystyle\leq\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{shapley}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]\frac{\max\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}u_{i}(s_{i})a_{i}}}{\min\limits_{\mathbf{s}\in\mathcal{S}^{N},\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}u_{i}(s_{i})a_{i}}}=\frac{1}{\beta_{\mathrm{shapley}}}\mathrm{ALG}$

∎

######  Corollary 5.1.

Consider an rmab-g instance with a monotonic, submodular reward function
$R(\mathbf{s},\mathbf{a})=R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})$, and let
$\pi_{\mathrm{linear}}$ be the Linear-Whittle policy. Let
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
and
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\frac{1}{T}\sum_{t=0}^{T-1}R(\mathbf{s},\mathbf{a})]$
for some $T$. Then $\mathrm{ALG}\geq\frac{\mathrm{OPT}}{K}$ for any
transitions $\mathcal{P}$.

###### Proof.

By Theorem 4, we know that
$\mathrm{ALG}\geq\beta_{\mathrm{linear}}\mathrm{OPT}$. We next show that
$\beta_{\mathrm{linear}}\geq\frac{1}{K}$.

For a monotonic, submodular function, $F:2^{\Omega}\rightarrow\mathbb{R}$,
$F(\\{x_{1},x_{2},\cdots,x_{n}\\})\geq\max\limits_{i}F(\\{x_{i}\\})$. Next,
applying this to our global reward function, for a fixed state $\mathbf{s}$,
we note that
$R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})\geq\max\limits_{i}R_{\mathrm{glob}}(\mathbf{s},\mathbf{e}_{i}a_{i})$.
Next, by construction,
$R(\mathbf{s},\mathbf{a})=\sum_{i=1}^{N}R_{i}(s_{i},a_{i})+R_{\mathrm{glob}}(\mathbf{s},\mathbf{a})\leq\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i})$.
Additionally,
$R(\mathbf{s},\mathbf{a})\geq\sum_{i=1}^{N}R_{i}(s_{i},a_{i})+\max\limits_{i}p_{i}(s_{i})a_{i}$

Next, for any state $\mathbf{s}$, $\sum_{i=1}^{N}p_{i}(s_{i})a_{i}\leq
K\max\limits_{i}p_{i}(s_{i})a_{i}$.

Combining the bounds on $R(\mathbf{s},\mathbf{a})$ and
$\sum_{i=1}^{N}p_{i}(\mathbf{s},\mathbf{a})$, gives that for any state
$\mathbf{s}$,

$\frac{R(\mathbf{s},\mathbf{a})}{\sum_{i=1}^{N}(R_{i}(s_{i},0)+p_{i}(s_{i})a_{i})}\geq\frac{\sum_{i=1}^{N}R_{i}(s_{i},a_{i})+\max\limits_{i}p_{i}(s_{i})a_{i}}{\sum_{i=1}^{N}R_{i}(s_{i},a_{i})+K\max\limits_{i}p_{i}(s_{i})a_{i}}\geq\frac{1}{K}$
(17)

Therefore, $\beta_{\mathrm{linear}}\geq\frac{1}{K}$, completing our proof.

∎

###  L.2 Upper Bounds

######  Theorem 6.

Let
$\mathbf{\hat{a}}(\mathbf{s})=\operatorname*{arg\,max}\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+p_{i}(s_{i})a_{i})$. For a set of
transitions $\mathcal{P}=\\{P_{1},P_{2},\cdots,P_{N}\\}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$
and
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{linear}})}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$.
Define $\theta_{\mathrm{linear}}$ as follows:

$\theta_{\mathrm{linear}}=\min\limits_{\mathbf{s}\in\mathcal{S}^{N}}\frac{R(\mathbf{s},\hat{\mathbf{a}}(\mathbf{s}))}{\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})}$ (18)

Then there exists some transitions, $\mathcal{P}$, and initial state
$\mathbf{s}^{(0)}$, so that
$\mathrm{ALG}\leq\theta_{\mathrm{linear}}\mathrm{OPT}$

###### Proof.

We prove this by constructing such a set of transitions such that
$\mathrm{ALG}\leq\theta_{\mathrm{linear}}\mathrm{OPT}$. Let
$\mathbf{s}^{(0)}=\mathrm{argmin}_{\mathbf{s}}\frac{R(\mathbf{s},\hat{\mathbf{a}})}{\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})}$. Next, let $P_{i}$ be the identity transition;
$P_{i}(s_{i},a_{i},s^{(0)}_{i})=1$ for any $\mathbf{s},\mathbf{a},i$. Under
these transitions, all arms stay in the state $\mathbf{s}^{(0)}$ for all time
periods $t$.

Because the state is constant, the set of actions played, $\mathbf{a}^{(t)}$
is constant across time periods (as the Linear-Whittle algorithm is
deterministic). We next show that the Linear-Whittle policy plays the action
$\operatorname*{arg\,max}\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\sum_{i=1}^{N}(p_{i}(s_{i})a_{i}+R_{i}(s_{i},a_{i}))$. We note that all arms
have the same transitions; therefore, arms are played in order of
$p_{i}(s^{(0)}_{i})+R_{i}(s_{i},a_{i})$, as each arm is predicted to receive a
reward $a_{i}p_{i}(s^{(0)}_{i})+R_{i}(s_{i},a_{i})$. This is because Linear-
Whittle aims to maximize the sum of marginal rewards, and when the transitions
are homogeneous, chooses the largest values for
$p_{i}(s_{i})a_{i}+R_{i}(s_{i},a_{i})$. In other words, the Linear-Whittle
policy chooses an action, $\mathbf{a}_{\mathrm{linear}}$ so that

$\mathbf{a}^{\mathrm{linear}}=\operatorname*{arg\,max}\limits_{\mathbf{\mathbf{a}}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\sum_{i=1}^{N}(p_{i}(s_{i}^{(0)})a_{i}+R_{i}(s_{i},a_{i}))=\mathbf{\hat{a}}(\mathbf{s})$
(19)

Finally, we observe that the optimal action to play is
$\mathrm{argmax}_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s^{(0)}},\mathbf{a})$. The ratio of rewards between these two
actions is exactly $\theta_{\mathrm{linear}}$, and therefore,
$\mathrm{ALG}\leq\theta_{\mathrm{linear}}\mathrm{OPT}$ ∎

######  Theorem 7.

Let
$\mathbf{\hat{a}}(\mathbf{s})=\operatorname*{arg\,max}\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}\sum_{i=1}^{N}(R_{i}(s_{i},a_{i})+u_{i}(s_{i})a_{i})$. For a set of
transitions $\mathcal{P}=\\{P_{1},P_{2},\cdots,P_{N}\\}$ and initial state
$\mathbf{s}^{(0)}$, let
$\mathrm{OPT}=\max\limits_{\pi}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi)}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$
and
$\mathrm{ALG}=\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim(P,\pi_{\mathrm{shapley}})}[\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s},\mathbf{a})|\mathbf{s}^{(0)}]$.
Let $\theta_{\mathrm{shapley}}$ be:

$\theta_{\mathrm{shapley}}=\min\limits_{\mathbf{s}}\frac{R(\mathbf{s},\hat{\mathbf{a}}(\mathbf{s}))}{\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})}$ (20)

Then there exists some transitions, $\mathcal{P}$ and initial state
$\mathbf{s}^{(0)}$ so that
$\mathrm{ALG}\leq\theta_{\mathrm{shapley}}\mathrm{OPT}$

###### Proof.

We follow the same strategy as the proof for the Linear-Whittle case and
construct a set of transition probabilities so that
$\mathrm{ALG}\leq\theta_{\mathrm{shapley}}\mathrm{OPT}$. Again, let
$\mathbf{s}^{(0)}=\mathrm{argmax}_{\mathbf{s}}\frac{R(\mathbf{s},\hat{\mathbf{a}}(\mathbf{s}))}{\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})}$ and $P_{i}$ be the identity transition. By the
same reasoning as Theorem 6, the Shapley-Whittle policy will play the action
$\hat{\mathbf{a}}$; the Linear- and Shapley-Whittle situations are analogous,
with the only difference being that Shapley-Whittle assumes each arm receives
a reward of $a_{i}u_{i}(s^{(0)}_{i})$ instead of $a_{i}p_{i}(s_{i}^{(0)})$.
The optimal action played receives a reward of
$\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})$, so that the ratio between the reward of the
Shapley-Whittle policy and optimal is

$\min_{\mathbf{s}\in\mathcal{S}^{N}}\frac{R(\mathbf{s},\hat{\mathbf{a}}(\mathbf{s}))}{\max\limits_{\mathbf{a}\in[0,1]^{N},\|\mathbf{a}\|_{1}\leq
K}R(\mathbf{s},\mathbf{a})}$ (21)

This is exactly $\theta_{\mathrm{shapley}}$ when
$\mathbf{s}=\mathbf{s}^{(0)}$. ∎

######  Lemma 8.

Define an index-based policy as any policy that can be described through a
function $g(s_{i},P_{i},R)$, such that in state $\mathbf{s}$, the policy,
$\pi$ selects the $K$ largest values of $g(s_{i},P_{i},R)$, where such a
function is evaluated for each arm. Then index-based algorithms will achieve a
discounted reward approximation ratio no better than
$\frac{1-\gamma}{1-\gamma^{K}}$

###### Proof.

Consider an $N=K$ arm system, with $\mathcal{S}=\\{0,1\\}$. Suppose our reward
is $R(\mathbf{s},\mathbf{a})=\max\limits_{i}{s_{i}a_{i}}$. Next, define the
transition probabilities for all arms as follows: $P_{i}(s,0,s)=1$ and
$P_{i}(s,1,0)=1$; if an arm is pulled, then the arm will transition to state
0, and otherwise, the arm remains in its current state.

Then note that because of symmetry between the arms, $g(s_{i},P_{i},R)$ is
identical, as $R$ is symmetric across arms, and $s_{i}$ and $P_{i}$ is the
same across arms. Moreover, because there are $N=K$ arms, all arms will be
selected in the first time step. Therefore, any index-based strategy will lead
to a reward of $1$. However, selecting arm $i$ in timestep $i$ instead leads
to rewards in each of the $K$ timesteps, leading to a total reward of
$\sum_{i=0}^{N-1}\gamma^{i}>1$ when $N>1$. Applying the geometric sum formula
reveals that this is a $\frac{1-\gamma}{1-\gamma^{K}}$ approximation. ∎