Global Rewards in Restless Multi-Armed Bandits
Authors: Naveen Janaki Raman
Zheyuan Ryan Shi
Fei Fang
Venue: NeurIPS 2024 poster (2024)
Keywords: Restless Bandits
Multi-Armed Bandit
Submodular
Food Rescue
Primary area: bandits
TL;DR: We extend traditional restless multi-armed bandits to incorporate global rewards

Abstract: Restless multi-armed bandits (RMAB) extend multi-armed bandits so arm pulls impact future arm 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-Whittle and Shapley-Whittle indices, which extend Whittle indices from RMABs to RMAB-Gs. We prove approximation bounds which demonstrate how Linear and Shapley-Whittle indices fail for non-linear rewards. To overcome this limitation, 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 adaptive policies outperform both pre-computed index policies and baselines in synthetic and real-world food rescue datasets.

Global Rewards in Restless Multi-Armed Bandits
Naveen Raman Carnegie Mellon University na @eenr@cmuu. edu
Zheyuan Ryan Shi University Pittsburgh ryanshi@pite edu
Fei Fang
Carnegie Mellon University feifange cmu edu
Abstract
Restless multi-ane multi-armed bandits (RMAB) extend multi-armed bandits so pulling an arm impacts future states. Despite the success of RMABS, key limiting assumption is the separability of rewards into sum across arms. We address this deficiency by proposing restles--multi-rmme tion of RMABS to global non-separable rewards. To solve RMAB-G, we develop the Linear- and Shapley-Wi Whittle indices, which extend Whittle indices from RMABS RMAB-GS. We prove approximation bounds but also point out how these indices could fail when reward functions highly -ineerr.r. 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 modex-based policies with synthetic data and real-world data from food rescue.
bandit with global rewards (RMAB-G), generaliza-
Introduction
Restless multi-an multi-armed bandits (RMAB) are models of resource allocation that combine multi-armed bandits with states for each bandit's 's arm. Such model is "restless" because arms can change state even when not pulled. RMABS are an enticing framework because optimal decisions can efficiently made using pre-computed Whittle indices [1 2 As result, RMAB have been used in scheduling (3)
autonomous driving 4 multichannel access 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 son-separeble 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 non-separable we only need one volunteer complete each trip (more details in Section 3) Beyond food rescue, RMABS can potentially model problems in peer review g, blood donation 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 RMABS non-separable rewards. Whittle indices from RMABS [ fail for RMAB-GS due to the non-separability of the reward. Because of this, we propose a generalization of Whittle indices global rewards called the Linear-Whithe and Chapley-Whitte 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Linear- and Shapley- Shapley-Whittle Whittle indices with search techniques. We empirically verify that adaptive policies outperform index based and baseline approaches on synthetic and food rescue datasets. D
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-Whin -hhttle indices, which extend Whittle indices for global rewards, and detail approximation bounds; (3) We design set of adaptive policies which combine Linear- and Shapley-Whie 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.
indices with greedy and Monte Carlo Tree Search (MCTS)
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): (S, A. RG Pis 7). Here, S is the state space,
A is the action space, R; S x A - IR is reward function, P. S A x S - 0, 1] is a transition
function detailing the probability of an arm transitioning into a new state, and 7 E [0, 1) is a discount
factor. For time period t, we define the state of all arm as s (t))
{s1
(0) s ES, and for
E AA; we drop the superscript t when clear from context. Following prior work [1 we assume A {0. 1) throughout this paper to represent not pulling and pulling an arm respectively. A planner chooses (*)) subject to a budget K, so that at most K arms can be pulled in each time step: Σ a; < K, vt. The objective is to find a policy, π. : S.N + AN that maximizes the discounted total reward, summed over all arms:
each round, a planner takes action a {aa
(1) aN } aj (f)
N
max E (P.x)
1=0 1=1
To solve an RMAB, one can pre-compute the "Whittle index" for each arm i and possible state sy: (s;)s) minfw]Qr,,ss; 0) (s, 1)}, where Qi, a;) = wwa, + (s 0;) + max (s. a). Here, (i, a.) represents the expected future reward for playing action as given penalty w for pulling arm. The Whittle index computes the minimum penalty needed to prevent arm pulls; larger penalties (w){s;)) indicate more value for pulling 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 [
2 E. Pi(ss,
(s'), and Vi
Defining Restless Multi-Armed Bandits with Global Rewards
Objectives in RMABS are written as the sum of per-arm rewards (Equation D. while real-world objectives involve non-separable rewards. For example, food rescue organizations, which notify volunteers about food rescue trips, aim maximize the trip completion rate, i.c., the fraction of completed trips. Suppose we model volunteers as arms and volunteer notifications as arm pulls. Then arm states correspond to volunteer engagement (c.g., active inactive) and rewards 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 problems with global reward function: Definition 1. We define an instance of RMAB-G through the following MDP for each arm: AS,A, R2, Rglob, P., 7). The aim is to find a policy, æ S.N - NN, that maximizes:
N
max E (P..)) x
Σ 2 (s a
Σ ( a 1))
Throughout this paper, we focus on scenarios where Rgiot (s, a) is monotonic and submodular in a; Rglob(s, a) = Fs((ila; 1}), where F is submodular and monotonic. Such rewards have
'All code is available here htt.t//oos/ssttaaa.oo/////aeeaea

---

diminishing returns as extra arms are pulled. We select this because a) monotonic and submodular functions can be efficiently optimized [33 and b) submodular functions are ubiquitous [4
[5 8).
Our problem formulation can model various real-world scenarios including notification decisions in food reseue and reviewer assignments in peer review [8. In food rescue, let (8:) be the probability that a volunteer picks up a given trip, given their state, The global reward is the probability that
any notified volunteer accepts trip: Rgihh a) = 1- -
a.p:(s:)). In peer review, journals select reviewers for submissions where selection impacts future reviewer availability (8] The goal to select a subset of available reviewers with comprehensive subject-matter expertise. If reviewer expertise a set Yg, then we maximize the overlap between the required expertise, Z, and the expertise
across selected (a; = 1) and available (s, 1) reviewers: Rglob (s, a) = U Y, Z). Our
1,,,=le,,=
formulation inherits the per-arm reward R, from RMABS there may be per-arm rewards. For example, food rescue platforms might care about the number of active volunteers, so Re(s;, 0:) 8,-
Let R(s, a) (gtanss, a) + E Ra(s;, ai). We characterize the difficulty of RMAB-G:
Theorem 1. The restless mulli-armed bandit with global rewards is PSPACE-Hand.
Theorem 2. No polynomial time algorithm achieve better than 1 1/e approximation the restless multi-armed bandit with global rewards problem.
Theorem 3. Consider
RMAB-G instance (S,A, Rú, Rglob, 7), Let Q=(s,a)
a. al and let x² be the optimal policy. Let a' = arg max, (s, a). Suppose 1,).. 2 P, 0, 1yds i, P.(1, a. 1) 2 P,(O, a, 1)vi, R(s, a) monotonic and submodular s and a, and g(s) = max R(s, a) submodular in S. Then, with
((s ((st,a))(PP)))) -
a oracle access to Q=- we can compute á in O(22) time so Q (s, á) 2 (1 2x-
Theorem D and demonstrate the difficulty of finding solutions to RMAB-GS while Theorem describes potential panacea via Qn... Leveraging Q.- is a polynomial- time algorithm, but the exponential state space makes difficult to learn such Q, motivating the need for better algorithms (we empirically demonstrate this in Section[..1 In essence, Lemma demonstrates that it is possible to achieve a 1 e approximation for the Q- Qavalue; however, even computing such an approximation is difficult, and motivates the need for computationally feasible solutions. Our assumptions for Jesseniaisyy capture the idea that rewards are submodular in both the state s and action a; these assumptions are satisfied for all of our synthetic experiments in Section We prove Theorem through reduction from submodular optimization, and
through reduction from RMAB, Theorem 2 Theorem 3 through induction value iteration. Full proofs are in Appendix K
4
Linear-Whitle and Shapley-Whitee Indices
4.1 Defining Linear-Whittee and Shapley-hhitlee
Because the Whittle index policy is asymptotically 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 Linear-Va Whittle, we let the marginal reward be (((s;) = max Rgiob(s',ed e,). where e, is a
s' s'(+)==;
vector with index i and elsewhere. The Linear-Whitle policy linearizes the global reward by optimistically estimating (g, a) As ΣN", Ps (s:))a and computing the Whittle index from this:
Definition 2. Linear- Whittle Consider an instance of RMAB-G (S, A, Rs, Rglob: P., Define
( ai, P.) = - a, + Rs(s;, a,) + asp;(s:) + Ee, Ps(ss, 0s V..((s))) where Vz,((s)) = max Q! (5% dl, Then the Linear- Whittee index is w (st,Pi) min(w ( (s,, p.) >
af
w
Ql I.))). The Whiile-Whitle policy pulls arms with the K highest Linear- indices.
To improve on the Linear-Whitle policy, we develop the Chattey-hittte policy, which uses Shapley values linearize the global reward. The Linear-Whar Whittle policy linearizes global rewards via p. but this approximation could be loose as Σn= pe(ss)ee )a; 2 Rgiab (s, a). The Shapley value, u; (s:). improves this by averaging marginal rewards across subsets of arms (see Shapley et al. [16]. Let V
3

---

these characteristics define when our Linear- and be the wiisent-wise maximum, so a V e, means arms in and arm i are pulled. Define:
|al| I(N
| - 1)! (Rgioh aVe) : - Rglnb (s', a)) (N-K))
We (8:)))
min x oE (0.1)) -.alKK-
Σ
Here, Rglob(s', a V Rglob(s', (s', a) captures the added value of pulling arm i, when a are already pulled. While the Linear-Whittl policy estimates the global reward as Rglob(s, (s, a) = >i= (s(s)),,, the Shapley-Whitte policy estimates the global reward as Rgloh (s, a) R3 Di=1 ui(s;)a; The Linear- Whittle policy overestimates marginal contributions, Appendix D). so by using Shapley values, we take a pessimistic approach (by taking the minimum over all s' This approach could lead to more accurate estimates of Rgint(s,a) ()) because marginal contributions are averaged across many combinations arms:
Di Pi(s;)a; 2 (s (s,a) (proof in
Definition 3. Shapley- Whittle Consider instance of RMAB-G (S,A, Rú Rylob: Pa. Let (f, ai, uz) 0,W + Rs(si, a.) + a,u;(s;) + 7 Ex Pe(s;, 04, (o) where Vs,((s()
max Qi (5/ d4, dz),)) u,). Then the Shapley- Whitttee index is w (s;, Uz) = min(w]Qf, (s,, (s, 0, uz) >
w
(si 1, 1.)). The Shapley-Whittle policy pulls arms with the K highest Shapley- Whittle indices.
4.2 Approximation Bounds
To characterize the performance of our policies, prove approximation bounds (proofs in Ap- pendix [L. We first define three properties that characterize situations when policies based on the Whittle index asymptotically optimal; Chapley-hiittle policies perform well:
1. Indexability refers to property of an RMAB where increasing the penalty for pulling arms, w, from 0 to oo monotonically changes the arms that are pulled from all the arms to none of the arms (see Akbarzadeh and Mahajan (17) for details)
2. Irreducibility is a property of a Markov Chain if every pair of states is visitable; that is, there exists no subset of sink states such that cannot escape from these sink states
3. Uniform Global Attractor is property of an RMAB, where the state distribution converges to the optimal state distribution (in terms expected reward) from any initial state; for more discussion, see Gast et al. [18
We define Theorems which capture lower bounds on the performance of our policies:
Theorem 4. For any fixed set of transitions, P. let OPT max max (P+)) Et- R(s, a)] for some T. For an RMAB-G (S, A, R2, Rglob, P., P. let R, a.) R, 0,) + p((s:)a, and let the induced linear RMAB be (S,A, R², P., 7). Let Tinear be the Linear- Whiitee policy, and let
ALG (Ps.a)-~(P
EL t=
R(s, a)). Define Blinear
R(s, a)
Blinear
min
(4)
NES NES",aE
10 JAlISK EN (R, + ps),)a,)
the induced linear RMAB is irreducible and indexable with the uniform global attractor property, then ALG 2 Bumear OPT asymptotically in N for any set of transitions, P.
Theorem 5. For any fixed set of transitions, P, let OPT max ((e.a)-(P.x)l Er'D R(ss a)) for
some T. For an RMAB-G (S, A, Rú, Rgloh: P,, let (4 az) = Ra(s;, a:) + uz u,(s:)as and let the induced Shapley RMAB be (S, A, RC Pt.7). Let Tihapley be the Shapley- Whitlle policy, and let
ALG ((s.a))(P:
1 Σ t=
R(s, a)). Define Sshapley as
R(s.a)
min
SESN ac [0.1 |all SK Er tu2()))))
Behapley
(5)
R(s.a) (0.1) JalISK (R. (a))
max
KESN
If the induced Shapley RMAB irreducible and indexable with the uniform global attractor property, then ALG 2 Sshapley OPT asymptotically in N for any choice of transitions, P.

---

Corollary 5.1. Let Tiinear be the Linear- Whittle policy, ALG = ((x.)) - (aama ) [ ΣT-1 T- R(s, a)] and OPT max (Ps))) = R(s, for some T. Then ALG 2 OPT for any P.
3 lower bounds policy performance; small B does not guarantee poor performance but large B guarantees good performance. For example, Piieerr and Eshapley are near for near-linear global rewards, Linear- and Chapley-Whitle policies perform well in those situations. We prove all three Theorems by bounding the gap between the linear (or Shapley) approximation and R(s, a) (proofs in Appendix D. Our key insight is that can bound the performance of Linear- and Shapely-White policies using similarities between the global rewards and the rewards of an induced RMAB. We note that the assumptions made by all Theorems
the same assumptions needed for the optimality of Whittle indices (2). We present an example of these lower bounds:
Example 4.1. Consider N 4, K = 2 scenario for RMAB-G with S = {0, 1}. Let Rolob a) 10 U Yil and (s; aq) = 0. Here, Y, are sets corresponding to each arm, with Y1 V2 11a==1,;;11 (1,2,3). Y3 [1,2) and Y, {3,4] Let 8; = 1 for all i, and consider the Linear- Next, note that (s.) = R(s,e,, e,), so P1 (1) = (2 = 3, p1 = Pa(1) 22
Linear-Whitlee Whittle policy.
Now let [1, 1, 0, 0] and lers = 11,1,1,1 1, Here, =|Y = 3. while E 1 Ps(ss)a; = We note that we select such an a and s because this minimizes the lower bound from Plineari other selections will not lead to the correct lower bound due to the minimum in the equation for Binearr
Therefore, Binear = 2 = 2 so the Linear-Ve Linear-Whitle policy is a 2 approximation to this problem.
We describe upper bounds and apply these bounds to Example 4.1
Theorem 6. Let a(s)
arg max aE SaLK E az) + pi(s:)a;). For set of transi- tions P = (P1, P2, }. let OPT = max (s.a)))(P,s)) Ei 7a R(s,, a)is(0) and ALG =
(((,aa) 1E 7¹ (R(ss a) s00 Define Oiincar follows:
R(s, a(s))
Ojinaar = min BESN
(6)
max |l SKK
R(s, a)
Then there exists some transitions, P, and initial state s(0), so that ALG < OP
OPT
Theorem 7. Let ā(s)
arg max aelol1)M.llll..55
ΣN (Ryls,, ai) + uss))),,) For a set of transitions
P (2,,P,.". ,NN and initial state s(0), let OPT = max ((a.)) (E= 7 R(s, a) [0))
and ALG (Ps,a)))(P: Ei
T a(s,)) Let Oshapley be:
R(s, a(s))
Oshapley = min
max
R(s a)
AE Ia
Then there exists some transitions, P and initial state (0)) so that ALG & dshapley OPT
Example 4.2. Recall the situation from Example 4.1 Let s; for all i, and consider the Linear- Whitle policy. Construct construct P,, so that (, a, 1) = 1vi, 8, a or in other words, (t) = 1vi, t. The Linear- Whittle policy will pull arms and 2, p1 (1) P2(1) (1) + (,)Vii. This results in an action a = [1, 1, 0), so that R(s, a) = 3, while the optimal action is a" = 0,,0,1, with R(s, a") 4. Computing Ounaar matches this upper bound of in this scenario.
Our upper bounds demonstrate that, for any reward function, there exists a set of transitions where our policies perform 6- o-fraction worse than optimal. flinaar is small when the optimal action diverges from the action taken by the Linear-Whitlle 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 discounted reward [ (for more discussion see Ghosh et al. [19]
5

---

5 Adaptive Approaches for RMAB-G
5.1 Limitations of Pre-Computed Index-Based Policies
Despite the approximation bounds given in Appendix [1 Linear- and Shapley- Shapley-Whittle Whittle policies can exhibit poor performance when upper bounds Ofinaar and Shopley are small. We detail such a situation: Lemma 8. (Informal) Let E (Tinear, Wshhalle) ) be either the Linear or Shapley-Whin Whittle policies. There exist problem settings where will achieve an approximation ratio no better than 1-
In general, pre- pre-computed index-based policies perform poorly because of their inability consider inter-arm interactions (proof in Appendix D- This approximation ratio matches lower bounds, lim
fineaar =
Bshapley, which motivates new policies which select arms adaptively.
K
5.2 Iterative Whittle Indices
Lemma 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-Whitle and Iterative Shapley-
Whittle. Both policies compute current time step rewards, ri, based on the arms pulled, X.
Definition 4. Iterative Linear- Whittle Consider an instance of RMAB-G (S, R2 Rgiahs P., 7). Consider a state s, and construct new state, S, with Ps. P.. Let Q (3,, ai Pe: r x)
(i P.) + os,rf - ps(s)) and (s Pi, r,, X) = Q (st, Cj Pi) for $1 + S4. Then the Iterative Linear-Whitle index is w (si Pt. X) = m Q (8, 0. D.P X)
(s, 1, rf, X)), where Xs) = Rgbob(s,e, Winee) - Rglob (s. Cz.)
Definition 5. Iterative Chapley-Whiteee Consider an instance of RMAB-G (S, Ru, Rglob, P.,.). 7)
with us(s)) defined by Equation 3 Construct a new state, 3, with Pa.
P.. Let
( ai, ri xx Qi ai, uz) + a,(r (si, X), X)- uz(s)) and Q (si, Gj Ui, N,, X) (s az, uz) for 8; # 5i. Then the lterative Chapley-hhitle Index is wf (si, ui, X) (8t, 1, un, r. x)). Here rı(s;, is computed as: min(w Q (st, O, un, ri x) > ( ve
|alli - ||a|| - 1)!
min
Σ
( ave. -aiGvXX))RRRoo(($ (s (8)
N
aE(0.1) ||ll: CK-2 a a =ax,- -ax =0
(N-R-IJ
By incorporating the arms pulled, X, both policies better estimate the present reward. Here, Q (Ri, az, Ps, . , X) represents the expected discounted reward when receiving (s, () cur- rently and px(s;) in the future (similarly for Haapley-Whittee) To model this, we construct a new state, 8t, which mirrors 8; except for the reward in the current timestep. The Iterative Whitle-Whitle and Shapley-Whi Whittle policies then iteratively select arms that maximize wi!h and w 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 to look beyond greedy selection by searching through various arm combinations. We propose two policies: MCTS Linear- Whittle and MCTS Shapley-Wittle. For both, we search through arm combinations, a, compute the present value (R(s, a)), and estimate the future value via Linear- and Shapley- Whittle indices. Nodes in the MCTS tree correspond arm combinations, edges to individual arms, and leaf nodes to actions
Our implementation of MCTS matches the upper confidence tree algorithm for selection, expansion, and backpropogation (20). while we differ for rollout (details in Appendix(C). During rollout, we select nodes according to an e-greedy algorithm 22 and leverage the Linear- and Shapley- -hittlee policies for greedy selection. We do because e-greedy is simple strategy that could potentially improve upon random rollouts. Once a leaf node, the reward is R(s, a)+ a) 14 a.) (s))aa (s, a4)] for MCTS Linear- Whittle and R(s, a) + [0 (st, (1,, a.) u(ssaa (s,,

---

1.6
1.3
Arms
1.4
1.4
1.2
1.2
10 Normalized Reward
1.2
1.1
Linear
Probability
Max
Subset
1.75
1.2
1.3
1.50
1.10
1.1
1.2
1.25
1.05
1.1
1.00
1.00
1.0
1.0
Probability
Vanilla Whittle
DQN
Shapley-Whittle
MCTS Linear
Greedy MCTS
DON Greedy
Iterative Linear
MCTS Shapley
Linear-Wiitte
Iterative Shapley
Optimal
We compare baselines to our mndex-basedd 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 Among our policies, Iterative and MCTS Shapley- -hittle consistently perform best.
Figure 1:
for MCTS Shapley-Whirke Here, R(s, a) is the known current value, and Σ (f,0 ai) ps(s:)a; a:)) is the estimated future value when accounting for the present reward R(s, a).
6 Experiments
We evaluate our policies across both synthetic and real-world datasets. We compare our six policies (Section 4. Section 5.2 and Section 5.3) the following baselines (more details in Appendix B):
1. Random We uniform randomly select K arms at each timestep.
2. Vanilla Whittle We the vanilla Whittle index, which optimizes only for Ra(si, az).
3. Greedy We select actions which have the highest value of (s();).
4. MCTS. We rum MCTS up to some depth, cK, where c is a constant.
5. DQN We train a Deep Q Network (DQN) [22]. and provide details in Appendix B
6. DQN Greedy Inspired by Theorem we first learn a DQN then greedily optimize Q(s, a).
7. Optimal We compute the optimal policy through value iteration when N < 4.
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 prior work 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, and Y; choices in Appendix A):
1. Linear- Given my, ... mn E I, then Rigoth (s, = Σm m;3;04.
2. Probability Given ....... mx E [0, 1], then Rglob (s. a)
11 (1-ma,,s m.ass)).
3. Max Given mi, mN E R, then Rgtob a) max; s,a,7,,
4. Subset - Given sets, Yi,... YN C [1,-... m). m E Z, then Regon((s a) Use Y.l.
We select these rewards, as they range from linear or near-linear (Linear and Probability) to highly non-linear (Max and Subser). The reward functions can also be employed to model real-world situations; the Probability reward models food rescue and Subset reward models peer review (see Section 3. For all rewards, we let Ra(s a) s:/N and S (0.1). 1). which matches prior work [12] We construct synthetic transitions parameterized by g, so P. 0, U(O, g), where is the uniform distribution (see Appendix A). We construct transition probabilities that having a; 1 or

---

1.6
1.8
Nomalized Reward
1.6
1.5
1.4
1.4
1.2
1.3
1.0
0.65
0.70
0.75
0.80
0.4
0.6
Linearity (Gtnear) (4 arms)
Linearity (0mear) (10 arms)
Linear-Whittle Shapley-Whittle
Iterative Linear
MCTS Linear
Iterative Shapley
MCTS Shapley
Figure 2: We plot policy performance for instances of the Subser reward which vary in linearity. We see that the Iterative and MCTS Shapley-Wan Whittle policies outperform alternatives for non-linear rewards (small (nerr)) while policy performances converge for linear rewards (large f(near).
Normalized Reward
1.8
Time Taken (s)
60
1.6
40
1.4-
20
1.2-
4
10
15
20
15 Number of Arms
10
20
Number of Arms
Iterative Shapley
Iterative Shapley
MCTS Shapley 40
Iterative Shapley 100
MCTS Shapley
MCTS Shapley 4
Iterative Shapley 10
Figure 3: We compare the efficiency and performance of Iterative Chapley-Whittie methods which vary in Monte Carlo samples used for Shapley estimation and MCTS Shapley-Whitte Whittle methods which vary in MCTS iterations. While Iterative Shapley-Whin Whittle is the slowest, decreasing the number of Monte Carlo samples can improve efficiency without impacting performance.
8t = 1 only improves transition probabilities (see Wang et al. 11)
We vary g in Appendix and find that our choice of does not impact findings. Unless otherwise specified, fix K N/2.
Figure [egure[shone shows that our policies consistently outperform baselines. Among our policies, Iterative and MCTS Shapley-Whiteee policies perform best. For N 10, Iterative and MCTS Shapley-hiitle significantly outperform baselines (paired t-test < 0.04) and index-based policies except for the Linear reward (p 0.001). DQN- bosed policies regress from on average 4% worse for N 4 to average 9% worse for N 10 compared to our best policy, which occurs due to the exponential state space. In Appendix [ we consider more combinations of N and K and find similar results.
To understand policy performance across rewards, we analyze how reward linearity impacts per- formance. We quantify linearity via Oiinear (see Theorem (6 and compute Onnear for Subsei in- stances varying in Yú (see Appendix AA.. For non-linear reward functions (small 0lneaa)) Iterative and MCTS- SCCT-SSapley-Whitee are best, outperforming Linear-We Whittle by 56%, while for near-linear reward functions (large (lnear), all policies are within 18% of each other (Figure = 10). Appendix H shows that, for some rewards, adaptive policies outperform non-adaptive policies by 50%.
To understand the tradeoff between efficiency and performance we plot the time taken and normalized reward for various N (Figure B). We evaluate variants of Iterative Shapley-Whitlee and MCTS Shapley-Whie Whittle because both perform well yet are computationally expensive. For Iterative Shapley- Whittle, 1000 samples are used for Shapley estimation by default, we consider variants that use 100, 10, and samples. For MCTS Shapley-Whne Whittle, we run 400 iterations of MCTS by default, so consider variants that run 40 and 4 iterations. Iterative Shapley-Whitle policies are the slowest

---

Vanilla Whittle
Greedy
MCTS
DQN
Linear Whittle
Notifications
0.975 0.012 0.989 = 0.009
1.829 + 0.016
1.047 + 0.012
1.547 + 0.025
1.932 + 0.017
Phone Calls
1.228 + 0.008
1.070 = 0.016
1.209 0.007
1.288 + 0.008
Shapley Whittle
Iter. Linear
Iter. Shapley
MCTS Linear
MCTS Shapley
Notifications 1.931 = 0.016 Phone Calls
1.921 + 0.017
1.290 = 0.008
1.287 + 0.009
1.294 = 0.009
1.291 0.008 1.293 + 0.008
Table I: We evaluate policies in real-world food rescue contexts by developing situations that mirror notifications (NV 100, K 50) and phone calls (NV 20, K 10). Our policies outperform
baselines for both situations and achieve similar results due to the nearly linear reward function.
but can be made faster without impacting performance by reducing the number of samples. Our results demonstrate how 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 food rescue dataset. We leverage data from partnering multi-city food rescue organization and construct an RMAB-G instance using their data (details Appendix D). Here, arms correspond to volunteers, and states correspond to engagement, with s; indicating 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 []] If volunteer is both notified (a; 1) and engaged (s; = 1), then they match to a trip with probability m,. 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, (s,, 0;) s,NN, which captures the fraction of engaged volunteers. We model two food rescue scenarios, and detail scenarios with more volunteers Appendix J
Notifications Food rescue organizations deliver notifications to volunteers as new trips arise 77. 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 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 T we compare our policies against baselines and find that our policies achieve higher normalized rewards. All our policies outperform all baselines by at least 5%. Comparing between policies, we find that Iterative and MCTS Shapley- Haypley-Whittle Whittle perform best, performing slightly better than the Shapley- -hittle policy. Currently, food rescue organizations perform notifications greedily, so RMAB-G framework could improve the engagement and trip completion rate.
Related Works and Problem Setup
Multi-armed Bandits In our work, we explore multi-armed bandits with two properties: com- binatorial actions (23) and non-separable rewards. Combinatorial bandits can be solved through follow-the-
folltw-the-perturbee perturbed- leader algorithms (24), which are necessary because the large action space causes traditional línear bandit algorithms to inefficient
[21]. Prior work has tackled non-separable rewards in slate bandits (25), through an explore-then-commit framework, and adversarial combinato- rial bandits (66.. from minimax optimality perspective. this work, we leverage the structure of RMAB--- to tackle both combinatorial actions and non-separable rewards.

---

we focus on 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 apploretheen-come perspective 227 and through upper confidence bound (UCB) algo- rithms [28] 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 TT While finding optimal solutions this problem PSPACE- Hard [29], index-based solutions are efficient and asymptotically optimal (2). As result, RMABS have been used acToss a variety of domains 4 3 30] and have been deployed in public health
scenarios 12]. While prior work has relaxed assumptions by considering RMABS that have con-
texts 31 combinatorial arms [2], graph-based interactions 33 and global state
combinatorial situations with global reward.
8 Limitations and Conclusion
Limitations While we present approximation bounds for index-basee 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 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 neither submodular nor monotonic would improve our understanding of RMAB-G. Conclusion RMABS fail to account for situations with non-separable global rewards, we propose the RMAB-G problem. We tackle RMAB-G by developing 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 wolldwrrdd food rescue datasets. Our results show how RMABS extend scenarios where rewards 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 GRFP Fellowship. Co-author Shi supported in part by a Pitt Mascaro Center for Sustainable Innovation fellowship.
10

---

References
[1] Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied probability, 25(A):287-298, 1988.
[2] Richard R Weber and Gideon Weiss. On an index policy for restless bandits. Journal of applied probability, 27(3):637-648, 1990.
[3] 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.
[4] 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-533. 2021.
[5] Keqin Liu and Qing Zhao. Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access. IEEE Trunsactions on Information Theory, 56(11) I): 5547-5567, 2010.
[6] Aditya Mate, Lovish Madaan, Aparna Taneja, Neha Madhiwalla, Shresth Verma, Gargi Singh, Aparna Hegde, Pradeep Varakantham, and Milind Tambe. Field study in deploying restless multi- armed bandits: Assisting non proffis in improving maternal and child health. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 12017-12025, 2022.
[7] 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.
[8] Justin Payan and Yair Zick. I will have order! optimizing orders for fair reviewer assignment. arXiv preprint (eXix::200.02210 2021.
[9] 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 21 ACM Conference on Economics and Computation, pages 463-464, 2020.
[10] Pieter I. van den Berg, Shane G Henderson, Caroline Jagtenberg, and Hemeng Li. Modeling emergency medical service volunteer response. Available SSRN 3825060, 2021.
[11] 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.
[12] Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application public health intervention. Advances in Neural Information Processing Systems, 33:1 1569--15556,, 2020.
[13) George I. Nemhauser, I Laurence A Wolsey, and Marshall I. Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14:265-299 1978.
[14] Alain Chateauneuf and Bernard Cornet. Submodular financial markets with frictions. Economic Theory, 73(2):7217744, 2022.
[15] Manish Prajapat, Mojmír Mutný, Melanie N Zeilinger, and Andreas Krause. Submodular reinforcement learning. arXiv preprint 2rXiv:2307.13372, 2023.
[16] Lloyd S Shapley et al. A value for n-person games. 1953.
[17] Nima Akbarzadeh and Aditya Mahajan. Restless bandits with controlled restarts: Indexability and computation of whittle index. In 2019 IEEE 58th conference on decision and control (CDC), pages 7294-7300. IEEE, 2019.
[18] Nicolas Gast, Bruno Gaujal, and Chen Yan. Exponential convergence rate for the asymptotic optimality of whittle index policy. arXiv preprint 2rXiv:2012.00004,20000 2020.
11

---

[19] 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 12, 2022.
[20] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282-293. Springer, 2006.
[21] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[22] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 13255213 2013.
[23] Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1404 1422, 2012.
[24] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-301 2005.
[25] Jason Rhuggenaath, Alp Akcay, Yingqian Zhang, and Uzay Kaymak. Algorithms for slate bandits with non-separable reward functions. arXiv preprint arXiv:2004.09957, 2020.
[26] Yanjun Han, Yining Wang. and Xi Chen. Adversarial combinatorial bandits with general non- linear reward functions. International Conference on Machine Learning, pages 4030-4039. PMLR, 2021.
[27] Fares Fourati, Christopher John Quinn, Mohamed-Slin Alouini, and Vaneet Aggarwal. Com- binatorial stochastic- greeid--greyyy bandit. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 12052-12060, 2024.
[28] Sho Takemori, Masahiro Sato, Takashi Sonoda, Janmajay Singh, and Tomoko Ohkuma. Sub- modular bandit problem under multiple constraints. In Conference on Uncertainty in Artificial Intelligence, pages 191-200. PMLR, 2020.
[29] Christos H Papadimitriou and John N Tsitsiklis. The complexity of optimal queueing network control. Proceedings of IEEE 9th annual conference on structure complexity Theory, pages 318-322. IEEE, 1994.
[30] Biswarup Bhattacharya. Restless bandits visiting villages: A preliminary study on distributing public health services. Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies, pages 1-8, 2018.
[31] 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.
[32] Lily Xu, Bryan Wilder, Elias B. Khalil, and Milind Tambe. Reinforcement learning with combinatorial actions for coupled restless bandits. arXiv, 2023.
[33] Christine Herlihy and John Dickerson. Networked restless bandits with positive externalities. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 11997- 12004, 2023.
[34] Tomer Gafni, Michal Yemini, and Kobi Cohen. Learning in restless bandits under exogenous global markov process. IEEE Transactions on Signul Processing, 70:5679-5693, 2022.
[35] 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-peeformance deep learning library. Advances in neural information processing systems, 32, 2019.
[36] Uriel Feige. A threshold of In n for approximating set cover. Journal of the ACM (JACM), 45 (4):634-65,, 1998.
[37] Alexander Schrijver. A course in combinatorial optimization. CWI, Kruislaan, 413: 1098, 2003.
12

---

1}, then compute Broader Impact
In this paper, we analyze the use of restless multi-armed bandits 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- makinn algorithms have real-world validity, Our proposed algorithms and analysis are a step towards improving the deployment of restless multi-armes bandit algorithms in real-world situations such as food rescue.
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 choices of initial state (5 trials). For all ablations in the Appendix, we run for seeds and run experiments across 5 choices of initial state. Random seeds change the reward parameters (m, Y2) 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 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, such a magnitude
vary across rewards and selections of reward parameters. For all experiments f = 0.9. We estimate the infinite-horizon discounted reward by computing the discounted reward for T = 50 timesteps; we do this because for > 50, 7 S 0.005, and so we can compute the discounted reward with only a small difference from the infinite time horizon.
To construct synthetic transitions, consider parameter q. and let P. 0, (0. where U is the uniform distribution. Then (, 0, 1) ~ (P, 0, 1), 1) and 1, ~ UPP (0,, O, 1), 1). Finally, (1 1, U (((ma((P(1, 1), (0, 1)), 1). We construct transitions in such a way so that being in s; = or playing action a; = 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
We additionally detail some of the choices for parameters for each of the rewards used in Section 6. For the Linear, Probubility, and Max rewards, we select m.,... my ~ (O, 1). For the Probubility distribution, such 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 m, 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. be sets of size 6. We select such a size so that Rglab((s (s, a) is non-linear in YY], when |Y|] is too small the problem becomes more linear (because Y; ( Y2 is empty).
To understand the impact of linearity, we construct the sets Y; in such a way to control fliuear. In particular, we consider two parameters a and b. We construct K (where K is the budget) sets which where Y; 21,2.-. 2...... .b),,, and we construct N K disjoint sets which are size < b. For the N - K disjoint sets, they would be {1, ... ,a), {a + I,a 2.... 2a]. ... Under this construction, flincur Ka We then vary b E (3, 4, 5), and vary a E [1...... 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 and b.
b
We run all experiments on 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 (35].
B Baseline Details
We provide additional details on select baselines here:
We develop Deep Q Network (DQN), where a state consists the set of arms pulled and the current state of all arms. The arms correspond to 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
DQN
13

---

50
25
1.0
40
Not Engaged
0.8
Densig
Engaged
0.6
20
50 Trips
75 Trips
-0.4
10
Not Engaged
0.2
Engaged
0%
5% Match Probability
10%
0.0
No Notify
Notily
No Notify
Noufy
(a) Transitions
(b) Match Probabilities
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 low probability of responding, which motivates the need for large budgets in notification.
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 28-dimensioon 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. DQN Greedy Inspired by Theorem we combine 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 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, greedily select arms one-by-one, until K total arms are selected. We let the learning rate be 10-4, a batch size of 16, and an Adam optimizer.
3. MCTS- We run our MCTS baseline algorithm and use the upper confidence tree algo- rithm (20). We run this for 400 iterations, and recurse until depth of K is reached; detail other choices for this in Appendix E We select a depth of 2 so that arm selections are non- non-myopic. By letting the depth be K, the MCTS algorithm would simplify into better version of greedy search, whereas we want to see if we can non-myopically select arms using MCTS.
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 impact of other choices on the efficiency and performance of models.
we consider the
We additionally provide the pseudo-code for our iterative algorithmss (Algorithm) 2) and our MCTS Shapley-
Haapley--Witteee Whittle and MCTS Linear- Whittle algorithms (Algorithm For our MCTS-based policies, we note that this follows from the typical upper confidence trees framework, varying only in the rollout step. We let 0.1 for the rollout function, and let 5.
D Food Rescue Details
To apply the food rescue scenario to RMABS, we compute aggregate transition probabilities for volunteers through clustering. Each volunteer in the food rescue performs certain number of trips,
14

---

Algorithm 1 Monte Carlo Tree Search for RMAB-GS
Input:
State s, reward function Riss, a), Q functions O (8s, az pá) Q (8i, Oz ui), and transitions "I.... PN. number of MCTS trials M, and hyperparameter
Output: Action a Initialize tree, T, with leafs representing K arms pulled Let Um represent the total value of node Let n. represent the number of visits to a node m for t
1 to M do Let m be the root of T Let be empty set while is non-leaf do
Add m to
if m has an unexplored child then
while m is non-leaf do
With probability let m' be random unexplored child of m
Otherwise, let m' be the unexplored child of m, with the largest value of (s)),, where
(x;);) is either the Linear or Shapley-Whittle index
Add m' to
Let ml
end while
else
Let m = argmax," ml nim CV Amm
Pmm +
1mm.
Let m m' end if
end while
Compute action a from nodes played, | For MCTS Linetr-Whittle, let R(s, a) + (0, ai,P:) Pi(si)a; Re(s;, a:)]
For MCTS Shapley-Whitle, r R(s, a) + -E 10, (0 (si, ai u;) u,(s;)a R,(s;, a:)
for m 2 do
Update W'm. <- Wm + Update <- 7ym + end for
end for return The action corresponding to the leaf, m, with the highest
Mim.
and we use this information construct clusters. We ignore volunteers who have performed 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 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 trip in the current two weeks impacts the chance that they complete a trip in the next two weeks. We use this as proxy for engagement due to the lack of ground truth information on whether volunteer truly engaged. average this over all volunteers in cluster and across time periods to compute transition probabilities. We present examples of such transition probabilities in Figure f To compute the corresponding match probabilities for cach volunteer, 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 transition probability (corresponding to volunteers being in the same cluster) while differing in match probability. Such situation corresponds the real world well; not all volunteers who complete between 107-115 trips have the same match probability.
per-volunteer basis that multiple arms can have the same
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:
15

---

Algorithm 2 Iterative Policies for RMAB-GS
Input: State 8, reward function R(s, a), Whittle functions wf Pi, X) wof (si, ui, X), and
transitions "I, PN
Output: Action
Let X = 0
for t
K do
Let v; = 0 for 1 SiSN
for 1 to do
if & X then
Update i wf/( end if end for if max v > 0 then Update +
or vs w/ U4 X)
end if end for Let (0, 13 with a; IVi e
Normalized Reward
Normalized Reward
1.2
1.2
1.1
1.1
Whittie
Linear-Whittee
MCTS
MCTS
1.0
1.0
1
100
200
400
800
MCTS Depth
MCTS Test Iterations
(a) MCTS Depth
(b) MCTS Test Iterations
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 test iterations, MCTS performs worse than Linear-Whitle Moreover, as expected, increasing test iterations improves performance, while lower depth improves MCTS performance due the difficulty in estimating rewards from transitions.
notifications and phone calls. For notifications, consider all volunteers and notify large fraction of these volunteers, while for phone calls, we consider only volunteers who have completed more than 100 trips, they generally have 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.
E
Vanilla MCTS Experiments
To understand the impact of our choice of hyperparameters for the MCTS bascline 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 iterations run for MCTS in {50, 100, 200, 400) (while searching up depth 2K). For all runs, we let K 5 and N 10 for the Max reward.
In Figure we see that increasing MCTS depth only lowers performance, while increasing the number of iterations MCTS run for increases performance. This is due to stochasticity in rewards the depth of exploration increases; there are | 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 rumning MCTS for additional iterations
16

---

2.00
Normalized Reward
1.75
1.50
1.25
Linear-Whittle
DQN
1.00
50
100
200
400
Training Episodes
Figure We compare the impact of additional training epochs on the performance of DQN baseline. We find that, regardless of the number of training episodes, Linear- Shiar- outperforms the DQN baseline. Additional training episodes do not result in a significantly better performance (compared with Linear- Linear-Whitte Whittle,, showing that additional training episodes do not lead to much smaller gap between Linear- Whittle and the DQN baseline.
1.3
Normalized lized Reward
1.2
1.1
1.0
0.25
0.5
0.75
1.0
Transition Probability (q)
Linear-Whittle
Iterative Shapley
Shapley-Whittle Iterative Linear
MCTS Linear
MCTS Shapley
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 Chapley-Whitte policies improve upon all other policies.
would be helpful, this comes at cost of time, MCTS for 400 iterations throughout experiments to balance these.
F
Deep Q Networks
We compare the performance our reinforcement learning baseline (DQN) to the Linear-Whitle policy as we vary the number of epochs that the DQN is trained for. We vary the number of train epochs (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 not lead much better performance. Moreover, we see that, no matter the selection of train iterations, DQN performs worse than Linear-Whitle. We believe the reason for this is the stochasticity the dataset; because number of actions is large, becomes difficult to learn state values in this scenario, which leads to the poor performance of DQN.
17

---

Normalized Reward
2.5
2.5
2
1.5
1.5
4 Arms
10 Arms
Vanilla Whittle
Shapley-Whittle
Greedy
Greedy
Iterative
Shapley
MCTS
Linear-Whittle
iterative Shapley
Optimal
Figure We construct situations where adaptive policies are needed to perform better than baselines. When N = 4, Iterative Chapley-Whitte significantly outperforms alternatives, and when N 10, MCTS Shapley- Chapley-Whittle Whittle outperforms alternatives.
1.1
1.10
1.05
1.05
Nomalteed Revard
1.00
1.0
1.00
Uieer
0.95
Frobabikky
Max
0.95
Subest
1.10-
1.05
1.05-
1.00
2.5
1.00
1.00
0.98
1.0
ShapteysWhisle
Shapley
Shapley
Figure 9: We repeat Figure for 25 and N 100. We find that many of the same trends appear here; namely, that MCTS Shapley-Whittl outperforms all other policies, and Chapley-based policies do better in general.
G Synthetic Transitions
Throughout our experiments, we sample synthetic transitions, with a maximum probability for P, of g: we vary the value of understand this impacts the performance of policies. We vary g E (0,0.22 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 g. the MCTS Shapley-Whitle policy performs best. We find large gaps between MCTS Shapley-Whittle and Sinear-Whittl for small gi in these scenarios, the transitions are more stochastic, leading to greater impact from MCTS Shapley- Shapley-Whittle. However, regardless of the choice of 9, our conclusion remains that Iterative and MCTS Shapley-White Whittle policies outperform other alternatives.
H Other Constructions of Transitions
We investigate whether situations detailed in Lemma can be tackled by adaptive algorithms. We construct situation for the Max reward where transitions are (, 1, and (s s) pulling an arm always leads to s; O, 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 = m2 = 1, then let the other choices of m, O. We do this to encourage arms be pulled one at time, rather than pulling m, and m2 together. In Figure g we compare the performance of policies in this situation and see that Iterative Shapley Shhapley-Whitlee significantly outperforms all other policies when = 4, and that MCTS Linear- and Chapley-Whithe 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.
18

---

1.3
Nomalized Reward
1.2
1.1
0.25
0.5
0.75
1.0
Vanilla Whittle Greedy
Linear-Whittle
Iterative Linear
MCTS Linear MCTS Shapley
Shapley-Whig Whittle
Iterative Shapley
Figure 10: We vary the parameter a, which modulates between the individual rewards R, and the global reward Rginb. When 1, all policies perform similarly, while for {0.25, 0.5, 0.75), we see that Linear- Whittle performs worse than other policies. Across values of o baselines perform worse than all policies, which most notable when 0.
I Other Combinations of Arms and Budget
More arms We evaluate the performance of policies when N = 25 or N 100 and plot this in Figure 9 We run Iterative Shapley-Waie Whittle, MCTS Linear- Whittle, and MCTS Shapley-White 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 [.. even when the number of arms is large.
Weighting Individual and Global Rewards Throughout our experiments, weight the impact of the global reward, Rglob(sa). and the individual reward, [s a;), equally. We evaluate the impact of various weighting factors so that a(s = a Rgbob (s, a) + +a N D (s, By default, a = 0.5 throughout our experiments, so we vary E (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 a, our policies outperform baselines. We additionally that the Shapley-Whine Whittle and Iterative Shapley-Whittee perform well across the choices of a, implying that the results we found with = 0.5 are not limited to one choice of a.
Varying Budget Throughout our experiments, we let the budget, = 0.5., so we analyze the impact of varying K when fixing N 10. We vary K {2, 8). and note that with K 10 K = 0, all policies perform the same (as all or no arms are selected). We see that, across all choices of budget, Linear-Whitle performs worse than all other policies (Figure Moreover, we again that regardless of the choice of K, MCTS Hhapley-hhitte is the best policy.
J Food Rescue More Arms
In addition to the experiments in Section 6.2 we evaluate the impact of increasing the number of arms food rescue on the performance 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 the phone calls scenario. We plot both situations in Figure [2] 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 sheer number of arms. We can differentiate between policies in the notification scenario, where Shapley-Whhe Whittle policies perform better than Linaer- Whittle policies, but in the phone calls settings, all policies perform similarly. Additionally, due the large budget, the match probability will be
19

---

1.8
Normalized Reward
1.6
1.4
1.2
1.0
Budget
Linear-Whittle
Iterative Shapley
Shapley-Whittie
MCTS Linear
Iterative Linear
MCTS Shapley
Figure 11: We vary the budget, K, while fixing = 10 for the maximum reward. We see that, for any choice of K, all policies have larger reward than greedy, and that Linear-Whitte policies perform worse than other policies. Moreover, for K and K = Iterative Shapley-Whitee policies outperform Iterative policies perform well, potentially due to the linearity the problem with small K.
policies, while for K 2 policies, Iterative Linear-Whitte
Normalized lidd Reward
2.5
1.2
2.0
1.1
1.5
1.0
1.0
Notificaitons (1000)
Phone Calls (250)
Linear-Whittle
Shapley-Whittle
Iterative Linear
Figure 12: We compare the performance of policies the food rescue dataset for two situations: (a) notifications, when = 1000 and K = 500, and (b) phone calls, when N 250 and = 50. We find that when N is large, all policies perform similarly, due the linearity of the problem for large N.
large, so policies should focus on engagement in this scenario. In reality, the choice of whether to pre-computed index policies or adaptive policies depends on the time available, the size of the problem, and the structure of the reward.
K Proofs of Problem Difficulty
Theorem The restless multi-armed bandit with global rewards is PSPACE-Hou
Proof. We reduce RMAB to RMAB-G. Note that RMAB-G aims to maximize
N
Y (Rgioh + Σ a.)s)
(9)
t=0
Consider RMAB instance with reward (s a.). We construct an instance of RMAB-G with R; = R and with Rgioh (s, a) = 0. Therefore, we have reduced RMAB to RMAB-G. Because RMAB PSPACE-Hard (29] RMAB-G is well.
Li
Theorem 2
No polynomial time algorithm can achieve better than a approximation to the restless multi-armed bandit with global rewards problem.
Proof. Consider any submodular function F(S) 20 R and a cardinality constraint |S] < K.
Unless P NP, maximizing F(S) with cardinality constraint can only approximated up to factor of 1 [36]. Next, will show that we reduce submodular maximization to RMAB-G.
20

---

For given submodular function F, we construct an instance of RMAB-G with S = {0, 1}. Let s( 1. where 1 is the vector of N 1s. Finally let (s, a, 0) = 1. so that all arms are in state 0 for timesteps > Let R(s, a) if o 1, and let R(s, a) F( F((ilaa = 1}) otherwise. Note that only at time & = 0 can you achieve any reward, as afterwards, F(S)= =0
The optimal solution the RMAB-G problem is the action, that maximizes F(Lila; = 1}) subject to the constraint, Σx=1 04 S K. Note that this the same as the cardinality constraint for submodular maximization, |S| Li=1 (4;, along with the function of interest, F(S). Therefore, if we can effi- ciently solve RMAB-G, then we can efficiently solve the original submodular maximization problem in F. Because we cannot do better than a approximation to the submodular maximization problem
in polynomial time, cannot do better than 1 approximation the RMAB-G problem.
- [0, 1]. where N is the number of arms. Let S = A (0. 1). Let Qr,s, = Eig (P) (x) [Et=0 R(s' a') as)) = 8, ag = for some policy π : S - A, and let л² be the optimal policy. Let V (s) = max Qx (s, a). If R(s, a) is monotonic in S and P.(L, a, 1) 2 P((O, a, 1) for any a, then Va (s) is monotonic in s
Lemma 9. Let P be set of transition functions, Pı. PN E
Proof. We construct (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, (s)
Let Q(+) (s. a) represent the Q value for iteration t of Value iteration, and let (() be the value function for iteration t. We initialize (s) 0 for any and note that the initialization should not impact the process. Running iteration of value iteration leads Q()) a) R[s, a), so that (1) = max 2 as)
a
Base Case: Initially, (s) = max H(s, a). Next consider any two states, x and y, so that x 2 y. Here x 2 y implies that x; 2 ViVi Let a* = Mngmax_R(y,aa) Then v( = R(yya")) S a(x,a")= S (x). Therefore, (a) is monotonic.
Inductive Hypothesis: Assume that (s) is monotonic in
Next, we will prove that ((0 V e.) - (tt) (s) 2 0. Here e; is the vector with at loca- tion i and everywhere else.
Before proving this, we will first show that this implies monotonicity for any two states s,s'. Suppose that (1 V e,) - (s) 2 Then consider some pair of states, 2 s'. Because S = = {0, 1}, if 2 s', then we can write s' v Viex e, for some set X = {I1, In). If ( V v&) (s'), then ((s' Ve,,) Vo. 2 (s) V.,)) Therefore, this implies that
i-1 V egy ex,))) 20 j=1
(s) - -V = Σ
(v
Vo oz,) -- 1=1
(s
(10)
We get this by expanding ()) - (s) into a telescoping series. Because each term in the sum non-negative, the whole sum is nen-negative.
Next we prove our original statement: (( ee) 2 (s)... We first expand ((O R(s, a) + y E, P(s, s') for some a, where P(s,a, = II (,)),, We note that ((0)s e,) a(, + + Eg a'
Therefore:
-vs > R(sve, 10-R(ss +7 aS)
(11)
We note that R(s e, a) R(s, a) 2 due to the monotonicity of R with fixed a.
21

---

Let C, C 10. be the set of 0-1 vectors of length N so that if x E C2 then Ia = 0.
Additionally, let 6, P(s V e; a, Ve,) a(s. V Ve). We note that
6,
P(s V e a,s' a, Ve:)
ei) (s' Vei)s)
II Pa(Sk, ak (s' vei)))
N
= (P:(1,, az, 1) - 01 1))
II 1,1,8
Pa(sk,
20
Let 1, be the vector of all Is except at i. Let A be the element-wise minimum operator. Then s 1; sets 8i = 0 while leaving other indices unchanged. Because transition probabilities add to one, P(s V e,, A1,) P(s. a, =
Next:
((0 V - (s)
2 R(s V e,, a) R(s,a) -7 ((P(s P(s, s(s
27 -
Σ (P(sVer P(s, 1.)) 11
s'EC
+y
Σ
[(P P(s,a (e:))/((t)(( vei)
S'EC;
Σ (.v(C-1) ( 1,) ( ve:)
S'EC.
7 Σ
(((((-))(s'v
(e.) (s A 1.))
s'ec.
2
The second step splits the sum into transitions for states with s = 0 and those with s 1. The final step applies the inductive hypothesis and noting that s' V e, 2 A 1,
Lemma 10. Let be set of transition functions, Pl, Pv ES AxS + 10, where N is
the number of arms. Let S = A = (0, 1). Lel Q7 = E(g (P) 7 Ris's a a'))[so 8, ag = a) for some policy : S + A. and let n² be the optimal policy. Lei V=- = max Q (s. a). If R(s,a) is submodular in both s and a, g(s) = max R(s, a) is submodular in S, and P1 1)
(, a, 1) for any a, then V* (s) is submodular in s.
Proof. We similarly construct V (s) through induction in the value iteration steps.
Base Case: We start with the base case: (s) = max R(s, a) g(s), which is submodular by assumption.
Inductive Hypothesis: Again let (s) be the value function at step t of value iteration. We assume that (s) is submodular, and aim prove that ( e;) (t) (s V e,) + V (s v e;) 2 O. We note that this is equivalent definition of submodularity 37
Now, consider (t)) v e.) (s) ( Ve e; V e,,) + Vt (sv (s,).. The sum of submodular functions submodular and note that (f)(s) max R(s. + Σg (s- a, s'). We
22

---

note that the first term is submodular by assumption, so we focus on proving the submodularity of y E. (s) s'). Let C.2 C {0, 1 be the set of 0-1 vectors of length N so that if
C.j then z; = 2, O, and let 6; = P. a, 1) - P, as 1); note the different definition of 5, from the previous proof. Finally, let C(s,a,s') = II Pi(or, at s)), then we can write the following:
(s e,) - -
Σ
=7
s'Ecis
+7
*'ECs
Σ C(s,a,s)((V (0))
s'EC.y
s'EC.a
E ((s.a
- (5)) - P,(,,a,,
s'ECL,
+7
Σ
- vc)]((( (j.)))).0))
s'Eci
Σ
a(s, ( (6,, ve.) + (ii Ve:) - (() v(i-)) Ve, Ve,))
=Y
s'EC..
0
The last step arises because di C(s, a, s') are all non-negative, and the inductive hypothesis.
Theorem
3 Consider an RMAB-G instance (S,A, R4 Rglob, Po Let (s,s,
a) and let x² be the optimal policy. Let a" arg max a as) Suppose 1,) 2 P,(s, 0, 1yss, P.(I,a,1 2 P:(O, 1)vi, R(s, a) monotonic and submodular and a, and g(s) max R(s, a) submodular
((s (ssaa))(PP Ee a())ss)
a,
Then with oracle access to Qx we can compute à in O(N2) time so Qx (s. a) 2 (1 (s,a),,
Proof. We first demonstrate that Qx (s, a) is submodular and monotonic in a. Prior work demon- strates that monotonic submodular function can be approximated within an approximation factor of 1 1-! with (N2) evaluations of the function, so all that remains demonstrate submodularity [13]
We note that Q.- (s, a) = R(s, a) + 7 E. V=- (=' a, s'), and that R(s, a) both monotonic and submodular in a. Therefore, we demonstrate that Ey (s') a,s) is monotonic and submodular a. Let (aa) = 7 E. V=-(s') s') for fixed
We start by demonstrating monotonicity. First, let T P.(s,, P((s,, 0, 1), and by assumption, Y 2 0. Then:
H(ave) - H(a)
7 Σ Vv (ess - P(s,a,
s'ec.
+ r Σ V= P(s,
s'EC:
-V-
(sA(,) II ()(s),
s'EC,
j=1.j
2 0
The last steps follows from the monotonicity of V (s), which was proven in Lemma 9
23

---

Next, we prove submodularity of (a), by showing that H(aVe:) H(a) H())e
H(av e2) 0. That is
H(ave:) ((a) H(a H(j H( Ve,)
Σ (12 (s) + 77(1 (VVV -v,(ss))
=Y
s'ECii
Σ th ,,
1, 100 Vs) (1 P, 0)) (sve -V.
7
s'EC..
=Y
Σ
(V.
V (sVe, - V (s) V(sve
20
The last line follows from the submodularity of V, proven in Lemma T0 shown that Qx (s, a) is submodular, which completes the proof.
Therefore, have
L Proofs of Index- Based Bounds
L.1 Lower Bounds
Theorem 4 For any fixed set of transitions, P, let OPT max ((.a)) Et- R(s, a)l
for some T. For an RMAB-G (8,A, Rg, Rglobs P., P. let R, a.) Rs + pi(s))a and let the induced linear RMAB be (S, A, R4, Pi, 7). Let Tinear be the Linear- Linear-Whitle policy, and let
ALG E [(s,a)~(PP (P:mennne)) 1 EtO T-1 R(s, a)]. Define Blinear
R(s, a)
Biinear
min
(12)
E (R,((,) a.) p((s:)o.)
the induced linear RMAB is irreducible and indexable with the uniform global attractor property, then ALG 2 Biinea OPT asymptotically in for any set of transitions, P.
Proof. By the definition of the minimum, Binnear E (p + Ra(s;, a)s,a)Va,s.
Additionally, note that E 2 Rs, This holds because pı(st)
max as, So, IN Pi 2 R(s, E e,a;) R(s, by submodularity of /
R (s,
We compare the linearized reward to the submodular reward for the set of actions played by the Sinear-Whitle policy Minear Let the actions be a a22), ..... we play for iterations,
then:
T-1 N
Blincar
(pisss 1=0
)a Ri(2 (0000(9)))
(())
T Σ Rts a())
(13)
T
Next, consider the following induced RMAB with (' a.) = R4( ag) + (((8;) Ja,- By assumption. our relaxed RMAB is indexable, irreducible, and has 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 Whitlle Index solution corresponds exactly to the Linear- policy, Mineer That
T N
max ((s.a)
Σ
(s,,,, a:)] =
R((s;, az)]
(14)
24

---

Then, asymptotically,
OPT
T
max LE (P,))
R(s,a)) a)]
T
t=
T-1 Σ
< max R (a.a))((P)))
R((se; az) (ss.a) (P.
R(())
T
T-1
Alinarr (P.
R(s, a)] ALG
Bunear
Theorem For any fixed set of transitions, P. let OPT max (x.n) ET- R(s for
some For an RMAB-G (S, A, Rú, Rglob. 7), let R(() Rs(ss a;) + (s(s,)a, and ler
the induced Shapley RMAB be (S, A, R P). Let Tshapley be the Shapley- Whittle policy, and let
ALG ((sa)) marhani > 2t R(s, a)]. Define Bahapley as
R(s.a)
SESN aE 1| |llIS EN
min
Pshapley
(15)
R(s.a)
BES aE 0011 Jal.SK (B((
max
If the induced Shapley RMAB is irreducible and indexable with the uniform global attractor property, then ALG 2 Pahapley OPT asymptotically in for any choice of transitions, P.
Proof. First, consider OPT max (s..a))(PP.)) L 7 7R(ss a)). First, note that R(s', a') s
EE ((()))a R,((4,,(()) SES aE(0.1] 1.E(0.1.N.Jjall ||ll|SS (x) R Next, note that sim-
R(s.a)
ilar to Theorem Tshapley is the optimal policy for the RMAB instance where (8 as)
u; (s(s))a; (s, de) for the induced RMAB (due to the indexability, irreducibility, and global attractor properties 2), or in other words,
max (Pxx) x
(s a:)l ((s.a)
Σ
Σ
R a:)]
(16)
Therefore,
OPT
1
max ((.,)))
R(s, a)]
T
1 T-1 N
R(s. a)
< T
RC (s(,
NES aE(0,1] |all SK N (u a.))
max
T-1 N Σ
R(s, a) I Jalkss EN (u;(si)a; + Ri(si, a:))
< Blssa)
Ri(si, az)
mAX SESN [0
1=1
Corollary 5.1 Consider an RMAB-G instance with a monotonic, submodular reward func-
tion R(s. a
Rglob (s, a), and let Winear be the Linear-Whithe policy. Let ALG
E(s.n)- Prannaar 11 Σr=1 R(s,a) a)] and OPT = (a -T-1 R(s, a)) for some T.
Then ALG
OPT
for any transitions P. K
25

---

Proof. By Theorem 4 we know that ALG 2 Pitnear OPT. We next show that Plinaar 2 K.
1
For a monotonic, submodular function, F : 222 + R, F(1 Inn) 2 max F ({ Next, applying this to our global reward function, for fixed state we note that (g. 2 max Rglob (s, e,a;). Next, by construction, R(s.a) En R.(s,, + Rglob(s, a) S E (R, a.) + pi(ss)as)) Additionally, R(s,a) 2 E (s a;) maxp;(s;)a Next, for any state s. Σ p; I K max (s(s)),,
Combining the bounds on R[ss, a) and Σi= (s,s, a), gives that for any state s,
N [i 0;) + max (i
R(s a)
(17)
Σ E (R, pa (s))
E Ra(s;, 0z) + Kmax (s;)aa
K
Therefore, Plinear 2 t completing our proof.
L.2 Upper Bounds
Theorem Let a(s) arg
N (Ba(s,))) a.) + (s()aa,)). For set of transi-
nE(o.1]* JasK
tions P (P,, P2, }. let OPT max max (sa)) Ei a)]s! and ALG
(Ps.aa=(P. 12== 7¹ R[ss a) |s00), Define Ojinaar as follows:
R(s,ā(s))
linear
min BESN
(18)
max 0 N
R(s, a)
l.SK
Then there exists some transitions, P. and initial state s(0), that ALG S OPi OPT
Proof. We prove this by constructing such a set of transitions such that ALG & Olnnaar OPT. Let
s (0 argmin, ", Iell
R(s.āā
R(s,a) Next, let P: be the identity transition; Pi(si, ai, (0)) = 1 for
Sells
any 8, a. Under these transitions, all arms stay in the state (0) for all time periods L.
Because the state is constant, the set of actions played, (1) is constant across time periods (as the Linear Whittle algorithm is deterministic). We next show that the action
policy plays the NN (pr + a.)). We note that all arms have the same transitions; aE(0.1]% 5|
max max
therefore, arms are played in order of (s; ) R4 a;), as each arm is predicted to receive reward a.p, ( a.). This is because Linear-Whitlle aims maximize the sum of marginal rewards, and when the transitions are homogeneous, chooses the largest values for pr(s:)a; + Ra 0z). In other words, the Linear- Whittle policy chooses an action, Alineur so that
N
a linear
arg max
(p((s)")) )a, (s(s;, ā(s)
(19)
aE SK
Finally, we observe that the optimal action to play argmax sall R(s((),,a) ( a). The ratio of rewards between these two actions is exactly Olinears and therefore, ALG S Alinear OPT
Theorem 7 Let ā(s)
ΣN (R(ss,a) + u4(8))a,). For a set of transitions
arg max aElllI
P P2,, PN} and initial state s(0), let OPT = max (( (E 72 R(s, a) a}|s [0]
and ALG (( (orhhaayyy E
Di Oshapley min
R(s, RRs (1) Let Oshapley be:
R(s, a(s))
(20)
max
R(s, a)
a5 a0 [|alll
26

---

Then there exists some transitions, P and initial state s so that ALG & shapley OPT
Proof. We follow the strategy the proof for the Linear-Whitle and construct a of tran- sition probabilities so that ALG 2 Oshapley OPT. Again, let g( argmax,
R(s.A(s))
max
[(ssa))
aE "iee.. s
and P: be the identity transition. By the same reasoning as Theorem 6 the Shapley-Whine Whittly-Whittle policy will play the action à; the Linear- and Shapley-Whin Whittle situations are analogous, with the only difference
being that Shapley- Whittle assumes each arm receives reward of a,u;(s; (0) instead of (s;") The optimal action played receives a reward of max
R(s, a), so that the ratio between the
ae(0,1]" S|ll| =
reward of the Shapley-Whitte policy and optimal is
Riss á()))
min SES
(21)
max
R(s. a)
ac 1) 1a............ S|
This is exactly Oshapley when (0)
Lemma 8. Define index-based policy as any policy that can be described through function
g(8; P.,Rt R), such that state s, the policy, a selects the K largest values of g Ps, R), where such ffunction is evaluated for each arm. Then index-based algorithms will achieve discounted reward approximation ratio no better than
Proof. Consider N K arm system, with S {0, 1}. Suppose our reward is R(s, a) max 8,04- Next, define the transition probabilities for arms as follows: (, 0, and P, 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,, P., R) is identical, as R symmetric across arms, and and P: is the same across arms. Moreover, because there are N = K arms, all arms will be selected the first time step. Therefore, any index-based strategy will lead to a reward of 1. However, selecting arm i in timestep instead leads to rewards in each of the K timesteps, leading total reward of Ei= EN-1> that this 1-7 approximation.
when N 1. Applying the geometric formula reveals
27

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We present algorithms for RMAB-GS, prove approximation bounds, and verify empirical performance.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
28

---

Justification: In Section 8 listed out limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proofs for all Theorems can be found in Appendix K and Appendix L Theorems have assumptions, etc. listed out.
All
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
List out experimental details in Appendix A Appendix C and Appendix B
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We plan to provide the code in the supplemental materials. We plan to release our synthetic dataset; our food rescue dataset is proprietary, so we are unable to release this.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
public// guides/ /ede///eooudaiiiicc ssi www.iisssooooooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
http:s/ccpppbccccccccccc http://dddeeeoeeooooooeen Chte//oodeSmmmmm sswonnooloolooooo loylclyyy/ for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
30

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Detail optimizers, etc. for the DQN baseline in Appendix B mental details are in Appendix A
General experi-
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Plot the standard error for plots to show statistical significance
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: In Appendix A detail the resources used
Guidelines:
The answer NA means that the paper does not include experiments.
31

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://tppe/eearrps...cooaaobbbe
ines?
Answer: [Yes]
Justification:
We conform to the code of ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have a broader impacts sections which discusses the societal impacts
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No pretrained models, etc.
32

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Code packages that are used are referenced, and any datasets are referenced
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithoom com/ datasets s has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets from this paper
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
33

---

Answer:
[NA]
Justification:
No human subjects
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human studies
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "L1RJkQuOKB", "reviewer": "Reviewer_TFrk", "summary": "This paper studies the popular Restless Multi-Armed Bandit (RMAB) problem and aims to tackle a key limitation – which is that, in RMABs, the rewards are assumed to be separable across arms. This is a limitation because in many scenarios, the overall reward may not simply be a sum over individual rewards of arms, but these rewards may be tied inextricably with each other. \n\nTo tackle this issue, the paper proposed the RMAB-G framework with non-separable global rewards. The paper shows hardness results on the RMAB-G problem. Further, the paper proposes index-based policies, similar to the original “whittle index” policy for regular RMABs – the two indexes proposed are the “linear whittle” and the “shapely whittle” indexes. \n\nThe paper also proves approximation bounds on the performance of these indexes and carries out empirical studies based on synthetic and real-world data to demonstrate the good performance.", "questions": "1. In line 54, why is whittle index defined as the min w where Q(., 0) > Q(., 1)? As far as I know whittle index is defined as the point where the two Q values become equal?\n2. Are the assumptions on the reward functions (monotonic, submodular, etc.) true for the food rescue setting or the blood donation example? \n3. Line 86: Is the RHS missing a +?\n4. In Theorem 3, what does it mean for the function g(s) to be submodular in s? Why is this a reasonable assumption?\n5. In the expression for u(s_i) in line 117, what do factorial terms stand for?\n6. In computing the shapely index, how stable is the index wrt K? For example if K were to increase by 1, is it possible that the top-K arms are significantly different from the top-(K+1) arms because all the indices changed?\n7. In line 123: why is it true that “this approach could lead to more accurate estimates”?\n8. In Theorem 4, in the expression for \\beta_{linear}, how is the R(s,a) term determined?\n9. In line 230, what is the difference between a trial and a seed?\n10. In first paragraph the paper cites maternal health [6] but this paper seems to have nothing to do with maternal health. Perhaps the authors wanted to cite the following:\nAditya Mate, Lovish Madaan, Aparna Taneja, Neha Madhiwalla, Shresth Verma, Gargi Singh, Aparna Hegde, Pradeep Varakantham and Milind Tambe.\n“Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health”", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. I believe a key strength of the paper is proposing the RMAB-G model with a notion of non-separable global rewards. While RMABs have been extensively studied before, this formulation (and its solution) is novel to the best of my knowledge. \n\n2. THe proposed linear and shapely whittle indexes intuitively make sense. I quite like the concept and augmentations made to the original whittle index to solve the RMAB-G problem. \n\n3. The results presented in the paper are grounded in theory – the paper provides approximation bounds for the proposed solutions. It also proves other minor theoretical results such as hardness of the RMAB-G. \n\n4. Empirical results look good: there are experimental results on both synthetic as well as real-world data.", "weaknesses": "1. Motivation: While the new RMAB-G framework and the provided analysis is interesting from a technical pov, the motivation for this setup / application to food rescue seems a little tortured. For instance, in line 66-67, the paper says that global rewards are needed because we cannot split the reward into per-volunteer functions. However, I’m not sure why — isn’t the total reward simply the sum of probabilities of individuals carrying our their assigned rescue tasks? \n\n2. Scalability: My worry is that the proposed solutions may not scale well. The experiments are all run on a small number of arms. Technically, the bottleneck might come from computing the shapely index itself. It seems like an expensive step with a min over exponential number of state vectors. \n\n3. Both the proposed index policies seem to depend on the budget K. Contrary to the regular whittle index, which is budget-agnostic, this seems a little less clean (and also perhaps a hurdle?). Is it possible that if the budget changes from K to K+1, the selected arms may change drastically because all the index values of all arms changed? \n\n4. Some concepts are not introduced in the paper. For instance, indexability, whittle index, etc. are assumed to be common knowledge, potentially making the paper difficult to access for someone not familiar with these concepts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer TFrk,\n\nWe thank you for your suggestions and insights, and your comments will help improve our final manuscript. We are happy that you find our study novel, and find the RMAB-G model to be a key strength of our paper. Additionally, we are glad that you find our policies intuitive and grounded in theory. Finally, we appreciate that you think our empirical results are good, both for synthetic and real-world experiments. We provide answers to each of your questions below: \n\n### Motivation for Food Rescue Scenario\n\nWe thank the reviewer for bringing up this important question. We note that the probability of any volunteer matching to a rescue trip is not simply the sum of their match probabilities. For example, if there are 2 volunteers, each with a match probability of 1/2, then the probability of any volunteer matching is 3/4, rather than 1/2+1/2 = 1. This is because we compute the probability that no volunteer successfully matches to a trip, which is a nonlinear function of the individual match probabilities.  \n\n### Scalability of Method\n\nWe agree with the reviewer that the scalability of our methods is important to assess the real-world applicability of our methods. In Appendix I and Appendix J, we vary the number of arms between 25 and 1000, and compare the performance of our policies. Index-based policies run quickly because the indices can be pre-computed and Shapley values can also be computed quickly because we estimate Shapley values using a subset of arm combinations. While adaptive policies, such as MCTS, run slower than index-based policies, when N <= 50, both adaptive and index-based policies can be computed in under 15 seconds, which is fast enough for real-world use cases such as food rescue. For large N, we can use index-based methods, which run in under a second per timestep for N=1000. \n\n### Impact of Budget on Arms Selected\n\nWe thank the reviewer for bringing up an interesting question about how the budget impacts the actions chosen by our index-based policies. For the Linear-Whittle policy, all arms that are selected with a budget of $K$ are selected for a budget of $K+1$ as well (within a particular timestep), because $p\\_{i}(s\\_{i})$ is independent of the budget. However, for the Shapley-Whittle policy, the impact of the budget on the arms selected is more complicated because $u\\_{i}(s\\_{i})$ is not independent of the budget. We do not believe that the Shapley-Whittle indices should change drastically when increasing the budget because the Shapley values are computed across many combinations of arms. Intuitively, increasing the budget should change the size of each arm combination, but the average reward of the arm combinations should not change drastically. \n\n### Introducing Indexability and Whittle Index\n\nWe agree with the reviewer that indexability and the Whittle index are important concepts that can help readers better understand our work. In the camera-ready version of our work, we plan to include additional background on these concepts to make our paper more accessible. \n\n### Assumptions for Food Rescue and Blood Donation\n\nWe thank the reviewer for bringing up an interesting question about our reward functions in food rescue and blood donation. As mentioned in Section 3, we model the global reward in food rescue using the probability reward function, which is both monotonic and submodular. A similar reward function can be used for the blood donation setting, as notifying donors about donation opportunities can only result in more blood being donated. Additionally, notifying additional donors leads to diminishing returns, due to capacity restrictions on the total amount of blood donated.  \n\n### Submodular g function\n\nTheorem 3 assumes $g(\\mathbf{s})$ is submodular in $\\mathbf{s}$. $g(\\mathbf{s})$ represents the maximum reward attainable from state $\\mathbf{s}$. If $g(\\mathbf{s})$ is submodular, then additional arms in the 1 state leads to diminishing marginal returns. Such an assumption holds true across each of the reward functions used in our experiments, and is commonly seen when additional present arms result in diminishing returns. We plan to include a brief discussion of the meaning of the assumptions for Theorem 3. \n\n### Better estimates from Shapley-Whittle\n\nWe thank the reviewers for pointing this out. On line 123, we state the Shapley-Whittle policy could lead to better estimates of the reward when compared to the Linear-Whittle policy. The Shapley-Whittle policy uses Shapley values to estimate the marginal contribution of each arm, while the Linear-Whittle policy overestimates marginal contributions. As a result, in many cases, the Shapley-Whittle index provides a better estimate of the reward because marginal contributions are averaged across many combinations of arms. This intuition is backed up by empirical evidence, where Shapley-based policies perform better than Linear-based policies. We plan to update our write-up to make this point clearer. \n\n### Other Questions\n\nWe thank the reviewer for pointing out our typo on Line 86, and we additionally plan to change Line 54 to Q(.,0) = Q(.,1).  \n\nOn line 117, the factorial terms arise from the original definition of Shapley values; these terms account for the number of orderings of arms for a particular action combination. \n\nFor Theorem 4, $R(\\mathbf{s},\\mathbf{a})$ term can be computed for any given $\\mathbf{s}$ and $\\mathbf{a}$. $\\beta\\_{\\mathrm{linear}}$ can then be computed by minimizing this ratio across all choices for the action and state. \n\nWhen we vary the trial, the starting state, $\\mathbf{s}^{{0)}$ changes, while the transition matrices, $\\mathcal{P}$, and reward parameters remain constant. However, when we change the seed, the starting state, transition matrices, and reward parameters all change. \n\nWe thank the reviewer for pointing out our misplaced citation, and we will fix this in the camera-ready.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ef91Var8NU", "reviewer": "Reviewer_oZCz", "summary": "Conventional RMAB problems model the rewards with respect to individual arms. Authors claim that for some instances (such as food rescue), a global non-separable reward function exists, because of which solutions to RMAB cannot be applied to such problem. \nTo address this NP-hard problem, authors modify Whittle index policy for linear cases, and propose two adaptive policies for nonlinear cases. \nTheoretical results (competitive ratio) are provided for modified index policy, and experiments show the performance of proposed algorithms.", "questions": "Please refer to weakness for my major concerns.\n\n\nSome minor questions:\n\n1. Line 84, Shouldn’t it be R(s,a) = R_glob plus \\sum R_i instead of times?\n\n2. Line 103, To clarify, Whittle index policy is optimal in asymptotic regime. \n\n3. For experiments, how many time slots (food rescue tasks) are deployed to measure the average reward? Also have you duplicated arms for the experiments, or the proposed algorithms can achieve very close to optimal reward even for 4 different arms? \n\nI’m having this question because based on my previous experience with RMABs, Whittle index may perform a bit far from optimal if there is only 1 duplicate for each type of arm. This question also corresponds to previous question that index policies are optimal in asymptotic regime.", "limitations": "My scores are based on the concern of model itself, as well as the necessity of global reward function in some circumstances. If my statement is wrong or inaccurate, I’m willing to adjust the scores accordingly.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This work opens a new topic that hasn’t been explored in RMAB, where there is a global utility function. \n\nThe authors provide theoretical bounds for linear and shapley whittle index policies.\n\nThe experiment part explores different combinations of policies and reward functions. Both synthetic and real traces are simulated to support the superior of proposed algorithms.", "weaknesses": "1. The major weakness I’m thinking of is the model itself. I might need more input from the authors to clarify why RMAB-G is required as a general model, instead of some specific scenario. The authors start with food rescue problems, that the platform wants to maximize the probability of one rescue task completion, while maintaining high engaging levels. \n\nThis model makes sense to me, but when I’m trying to understand other examples, such as peer review, I cannot find a good explanation for the local arm reward. The state of arm(reviewer) here is if they are available, so what will be the local arm reward? Maximize the availability of the reviewers? \n\nThe authors have mentioned several other applications for RMAB-G such as blood donation, emergency dispatch, could you clarify how these applications model global and local rewards? \n\nCan the authors provide a general requirement for the models that need RMAB-G? \n\n2. I’m also having a hard time understanding some of the global reward settings in section 6.1. More specifically the necessity of global reward function.\nFor example, for linear reward function, if we set the individual reward for each arm as a very naïve m_i s_i a_i + s_i, the solution for maximizing this reward for each arm seems to generate the largest global reward function? The same holds for max global reward, that we can just set the local reward as m_i s_i a_i. \n\n3. Another question that I have is, it seems that MCTS requires local searching, which is a relatively complicated algorithm. Given known transition probabilities, Whittle index can be computed (or approximated), then rest of the algorithm is just looking up the index tables. I understand that proposed algorithms have better reward performance, but what is the time/ complexity sacrifice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer oZCz,\n\nWe thank you for your suggestions and these comments will help improve our final manuscript. We appreciate that you view our work as “opening a new topic” and are glad that you recognize our theoretical bounds. Additionally, we are happy that you appreciated our empirical results and found that they supported our proposed algorithms. We provide answers to each of your questions below: \n\n### RMAB-G Model in Peer Review\n\nWe thank the authors for bringing up their questions about applying RMAB-G to the peer review setting. If peer review institutions focus exclusively on review quality, then the local reward could be 0. Such a scenario is allowed within our model and all performance guarantees still apply to such a situation. We empirically analyze situations with zero local reward in Appendix I. \n\n### Global and Local Rewards in Blood Donation and Emergency Dispatch\n\nThe volunteer emergency dispatch situation parallels the food rescue scenario for both the global and local reward. In volunteer emergency dispatch, volunteers are notified about emergencies, to have volunteers assist with an emergency (an example of this can be seen through the app PulsePoint). The global reward is the probability that any volunteer helps out with an emergency, which corresponds to the probability reward. The local reward corresponds to engagement; similar to food rescue, emergency dispatch platforms want to ensure high engagement rates from their volunteers.  \n\nIn blood donation, the objective is to match blood donors to blood donation opportunities [1]. Local rewards in this situation correspond to the number of active blood donors. Global rewards could refer to the total amount of blood donated weighted by some fairness constraint proportional to the squared difference between rural and non-rural hospitals [1]. Alternatively, there could be other domain-specific considerations that play into the choice of local and global rewards. \n\n### General Model Requirements\n\nTo apply our proposed algorithms, we require two things of the reward function: a) it is submodular in the arms pulled, meaning that the marginal gain for pulling an arm is diminished as additional arms are pulled simultaneously, and b) it is monotonically increasing in the arms pulled (pulling more arms cannot decrease the reward). Submodular monotonic reward functions are common assumptions for set functions and arise naturally in many situations including explainability [2], reinforcement learning [3], and economics [4]. \n\n### Global Rewards for Maximization\n\nWe thank the reviewer for this question, and plan to include further details on the maximization reward in the paper. We agree with the reviewer that for the linear global reward, naively applying the proposed solution is optimal. However, this is not true for the maximization global reward. \n\nFor example, suppose that we have three arms ($N=3$) with a budget of two ($K=2$). Suppose that the global reward is the maximization reward, while the local rewards correspond to whether arms are in state 1: $R\\_{i}(s\\_{i},a\\_{i}) = s\\_{i}$. Suppose that $m\\_{1} = 5$, while $m\\_{2} = 4$ and $m\\_{3} = 2$. Finally, suppose that arms 1 and 2 remain in state $s\\_{1}=1, s\\_{2}=1$, while arm 3 is in state 1 if pulled ($P\\_{3}(1,1,1) = 1$). In this scenario, naively maximizing $m\\_{i} s\\_{i} a\\_{i} + s\\_{i}$ results in pulling arms 1 and 2, while the optimal set of arms to pull is 1 and 3. Neither pulling arm 2 nor arm 3 provides any benefit to the global reward when arm 1 is already pulled. However, pulling arm 3 improves the local reward more than pulling arm 2, so pulling arms 1 and 3 is optimal. More generally, because the maximum function is non-linear and non-separable, approximating the reward purely linearly can result in poor performance due to overestimation. We demonstrate this empirically in Figure 2, where our Linear-Whittle policy, which estimates the reward in a similar manner, performs worse than our Shapley-Whittle policy, which uses Shapley values to estimate the reward function.  \n\n### Time Tradeoff for MCTS\n\nWe agree with the reviewer that the time complexity of MCTS is an important consideration when deciding which algorithm to use. We agree that MCTS could run slowly due to the effect of local searching; we quantify this in Figure 3, where we plot how the time needed to run MCTS varies with the problem size. In practice, when N<=100, the MCTS-based algorithms can run in under 30 seconds, which is suitable for real-world applications such as food rescue (which require that algorithms run in under 1 minute). \n\n### Experimental details for food rescue\n\nWe thank the reviewer for this question. We provide details on the number of food rescue slots in Appendix A, and plan to bring this forward into the main paper. For all experiments, we run 50 food rescue trips, and average this across 15 seeds, and 5 trials per seed. We select T=50, because when using the discounted reward, $\\gamma^50 < 0.005$, and so the rewards beyond T=50 are relatively small. \n\n### Smaller comments\n\nWe thank the reviewers for their writing suggestions, and we plan to change the typo on line 84 and correct line 103 so it specifies optimality in the asymptotic regime.  \n\n### References \n\n[1] McElfresh, Duncan C., et al. \"Matching algorithms for blood donation.\" Proceedings of the 21st ACM Conference on Economics and Computation. 2020.\n\n[2] Chen, Ruoyu, et al. \"Less is more: Fewer interpretable region via submodular subset selection.\" arXiv preprint arXiv:2402.09164 (2024).\n\n[3] Prajapat, Manish, et al. \"Submodular reinforcement learning.\" arXiv preprint arXiv:2307.13372 (2023).\n\n[4] Chateauneuf, Alain, and Bernard Cornet. \"Submodular financial markets with frictions.\" Economic Theory 73.2 (2022): 721-744.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ruHZk8m6af", "reviewer": "Reviewer_t2ns", "summary": "This paper studies RMAB (restless multi-armed bandits) with global\nrewards. Standard RMAB assumes that the total reward is a sum of the\nrewards across arms. Even though this type of RMAB incurs\ncurse-of-dimensionality, the linear reward structure allows Whittle\nindex to be defined. In contrast, in this paper the total reward has an\nadditional term that is submodular but non-linear. The authors first\npropose two linear approximations of the global reward, through which\nthe Whittle policy can then to used. The approximation bounds of the\nresulting linear-Whittle policy and Shapley-Whittle policy are provided.\nSince these approximation bounds can be poor, the authors further\nprovide an iterative linear approximation (iterative linear-Whittle\npolicy), although the latter does not have performance guarantees.", "questions": "1. What is the significance of Theorem 3? The reviewer is confused\nbecause only ensuring that $\\hat{a}$ attains a certain fraction of the\noptimal $Q$-function does not seem to imply that the long-term reward is\nguaranteed to be lower bounded. \n\nAlso, it seems that in this theorem the argument of $P_i$ for the state\nis either 0 or 1. Why are there only two states? \n\n2. In Example 4.1, how do you know that the approximation ratio is 1/2\nby only examining one $a$ and $s$. Shouldn't you take the minimum over\nall $a$ and $s$?\n\n3. The Definition 4 (Iterative Linear-Whittle) is a bit confusing. The\niterations were never introduced. It seems that $X$ is the decision\nfrom the previous iteration, is that right? It would be better to state\nthe algorithm in a pseudo code with iterations. \n\n4. Similarly, Section 5.3 is difficult to follow. It is unclear to the\nreader where/how/why Monte Carlo Tree Search is combined with the\niterative algorithm in Definition 4.", "limitations": "Limitations are discussed in Section 8.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. RMAB with global reward has not been studied in the literature. \n\n2. Some approximation guarantees are provided for the Linear-Whittle and\nShapley-Linear Whittle policies.", "weaknesses": "1. The provable approximation guarantees can be loose (as low as $1/K$,\nwhere $K$ is the number of arms), unless the non-linear term is\ninsignificant. \n\n2. The iterative linear-Whittle policy, which is meant to achieve better\nperformance, does not have performance guarantees. \n\n3. The presentation of the iterative linear-Whittle policy could be\nimproved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer t2ns,\n\nWe thank you for your suggestions and comments on our paper, and these will greatly help improve our final manuscript. We are glad that you appreciate how RMAB-G has not been previously studied in the literature. Additionally, we are happy that you appreciate the approximation guarantees we provide for our Linear- and Shapley-Whittle policies. We provide answers to each of your questions below: \n\n### Looseness of the 1/K Guarantee\n\nWe thank the reviewers for bringing this up. While the 1/K guarantee can be loose in some situations, we demonstrate in Lemma 8 that there exist reward functions for which the 1/K guarantee is tight. To provide a tighter guarantee, in Theorems 4 and 5, we provide lower bounds for the performance of Linear- and Shapley-Whittle dependent on the value of $\\beta\\_{\\mathrm{linear}}$ and $\\beta\\_{\\mathrm{shapley}}$ respectively. \n\n### Iterative Linear-Whittle Guarantee\n\nWe thank you for bringing up this question, as it is an interesting and natural question. Proof techniques used to bound the performance of the Linear- and Shapley-Whittle policies cannot be directly applied to adaptive methods because adaptive methods lack an analog for the \"induced linear RMAB\" or \"induced Shapley RMAB\". To get around this limitation, we develop new performance bounds for the iterative Linear-Whittle policy and show that a) in some scenarios, the iterative Linear-Whittle policy achieves no better than $\\frac{1}{1+(K-1)\\gamma}$ of the optimal average reward, and b) for any choice of reward and transitions, the iterative Linear-Whittle policy achieves at least $\\frac{1}{K}$ of the optimal reward. We introduce formal theorem statements and proof sketches in the global rebuttal. \n\n### Theorem 3 Significance \n\nWe thank the reviewers for bringing up the purpose of Theorem 3. We agree with the reviewer that Theorem 3 does not guarantee the long-term reward is bounded. Theorem 3 demonstrates that it is possible to achieve a 1-1/e approximation to the Q value, which serves as an initial attempt at solving the problem. However, in addition to the algorithm not guaranteeing a long-term bound on the reward, such a method is computationally intractable, as it requires exponential time to learn such a Q function. Theorem 3 motivates the need for computationally feasible algorithms with long-term reward guarantees, as initial reinforcement learning-based solutions fail to solve the problem. We plan to clarify this further in the camera-ready version of our manuscript. \n\n### Example 4.1 Approximation Ratio\n\nIn Example 4.1, we show that our Linear-Whittle policy achieves a 1/2 approximation. We demonstrate this by first computing an upper bound on the optimal reward; we do so by upper bounding the individual contribution from each arm ($p\\_{i}(s\\_{i})a\\_{i})$), then maximizing this by summing over arms ($\\sum\\_{i=1}^{N} p\\_{i}(s\\_{i})a\\_{i})$). This allows us to find that $\\mathrm{OPT} \\leq 6$ . We then compute the arms which are pulled by the Linear-Whittle policy, and find that the reward for this is 3. Therefore, the Linear-Whittle policy achieves at least 1/2 of the optimal reward. We plan to add more details to our analysis in Example 4.1, and include these details in the paper.  \n\n### Explaining Iterative Linear-Whittle\n\nWe thank the reviewers for pointing this out, and the reviewer is correct that $X$ are the decisions from previous iterations. To improve clarity, we plan on including pseudocode in the camera-ready version of the manuscript. \n\n### Explaining MCTS with iterative algorithms\n\nWe include details on our MCTS algorithm in Algorithm 1 of the Appendix, but plan to incorporate this into the main paper and include further details. At its core, our MCTS algorithm computes a variant of the Linear-Whittle index for different actions. Each node in MCTS represents a partial selection of arms, and children nodes indicate new possible arms to be selected. During a rollout, we select additional arms to pull for the current timestep, and after this, we have a candidate set of arms to pull corresponding to an action $\\mathbf{a}$. We can compute the exact global and local reward using this and use index-based approaches to estimate the future reward for the action $\\mathbf{a}$. We combine these two values to assess a total reward associated with the action $\\mathbf{a}$, and repeat this procedure across different combinations of arms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ivKXmFuwQ8", "reviewer": "Reviewer_a47J", "summary": "The authors study restless multi-arm bandits where we do not observe separate reward for individual arms and instead observe a global reward which is the sum of reward across arms. They propose Linear and Shapley-Whittle indices, which extend classical Whittle indices  (designed for settings where separate reward for individual arms are observed) into the global reward setting and establish approximation bounds. The proposed linear-Whittle policy computes marginal reward for each arm, and the proposed Shapley-Whittle policy computes Shapley values for each arm. To address nonlinear reward functions, the authors propose adaptive policies that takes into account inter-arm interactions. They combine MCTS with Whittle indices to look beyond greedy selection.", "questions": "Could the theoretical results be modified and applied to adaptive approaches, or have implications in adaptive approaches? If so, it would be nice to have a discussion in the paper. \n\nThe authors focus on scenarios where the global reward is monotonic and submodular in actions. Such rewards have diminishing returns as extra arms are pulled. Could the authors discuss potential ways to apply/modify proposed approaches to settings where the global reward is not monotonic and submodular in actions?  This is mentioned in limitations section, but it could improve the paper to at least point out potential ways to apply proposed methods in more general settings.", "limitations": "The authors discussed the limitations and impact of the work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The authors prove the difficulty of finding solutions to RMABs with global reward through reduction from RAMB and reduction from submodular optimization. They establish performance bounds for index-based policies and include discussions on the takeaways of the bounds. \n\nA comprehensive set of policies and baselines are compared in experimental evaluations. Results on both synthetic and real-world data showcase the strength of proposed approaches. The real-world setting nicely motivates the global reward RMAB problem.", "weaknesses": "For approximation bounds in section 4.2, the authors briefly describe proof techniques and implications of the results. It would strengthen the paper to elaborate more on technical novelties / contributions in the proofs.\n\nThe adaptive policies are stronger than pre-computed index-based policies, which have exhibit poor performance due to their inability to consider inter-arm interactions. However, the theoretical results focus on linear and Shapley-Whittle indices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer a47J,\n\nWe thank you for your comments and suggestions. These comments will greatly help improve our final manuscript. We appreciate that you find our empirical evaluation comprehensive, and find that our empirical results strengthen the validity of our policies. We are additionally glad that our real-world applications help motivate the RMAB-G problem. We provide answers to each of your questions below: \n\n### Novelties + Contributions in Approximation Bounds\n\nWe thank the reviewers for inquiring about our proof techniques and the novelties present there. Our key technical insight is a novel method to bound the performance of Linear- and Shapely-Whittle policies using similarities between the global rewards and the rewards of an induced RMAB. Such a technique provides insight into how approximation guarantees can be derived for other variants of RMABs. To quantify the similarity between the rewards of Linear- and Shapley-Whittle and the rewards of the induced RMAB, we use properties of submodular functions to upper bound the reward from Linear- and Shapley-Whittle. We plan to emphasize these contributions more in the camera-ready version of our paper.\n\n### Non-Monotonic Rewards\n\nWe thank the reviewers for bringing up this interesting question. Following the reviewer's suggestion, we empirically tested our methods with non-monotonic. In the supplemental PDF, we attach a Figure that evaluates the performance of our policies under two non-monotonic rewards. The first reward is the minimum function, where we assume that the minimum of an empty set is 0, and the second is the linear reward, but with negative rewards for some arms. We compare the performance of our policies for both 4 and 10 arms, and evaluate this across 15 seeds. \n\nMCTS Shapley-Whittle performs best for the negative linear reward, which follows the same trend seen for monotonic rewards. Such results follow intuition, as for non-monotonic rewards, the impact of one arm upon the rewards of other arms is more complex, requiring the use of adaptive algorithms. For the minimum function, we find that MCTS-based methods perform best for N=10, while for N=4, we find that our index-based policies perform near-optimally. We believe that a more systematic investigation of non-monotonic rewards poses an interesting direction for future research, and thank the reviewer for bringing this up.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful comments and for taking the time to carefully read through our work. We are pleased that reviewers find our problem formulation novel (reviewers TFrk18, oZCz07, and t2ns05) and motivated by real-world applications (reviewer a47J02). We are happy to see that reviewers find our proposed policies intuitive (reviewer TFrk18) with good empirical (reviewers TFrk18, oZCz07, and a47J02) and theoretical (reviewers TFrk18, oZCz07, t2ns05, and a47J02) backing. We additionally appreciate that reviewers find our set of empirical evaluations comprehensive (reviewer a47J02). Your comments have greatly helped improve our work. 

We hope to address your comments and questions in this rebuttal. We first describe a set of new approximation bounds for adaptive methods, which was discussed by multiple reviewers, while we reply individually to each reviewer for any comments they might have. 
 
# Summary of New Additions

## Approximation Bounds for Adaptive Methods

Following feedback from reviewers a47J and t2ns, we develop performance guarantees for adaptive methods. Proof techniques used to bound the performance of the Linear- and Shapley-Whittle policies cannot be directly applied to adaptive methods because adaptive methods lack an analog for the "induced linear RMAB" or "induced Shapley RMAB". 

To get around this limitation, we develop new performance bounds for the iterative Linear-Whittle policy and show that a) in some scenarios, the iterative Linear-Whittle policy achieves no better than $\frac{1}{1+(K-1)\gamma}$ of the optimal average reward, and b) for any choice of reward and transitions, the iterative Linear-Whittle policy achieves at least $\frac{1}{K}$ of the optimal reward. We formally state these theorems and provide proof sketches below. 

Theorem 1:     Let $\pi\_{\mathrm{IL}}$ be the iterative linear policy.  Let $\mathrm{ALG} = \mathbb{E}\_{(\mathbf{s},\mathbf{a})\sim (P,\pi\_{\mathrm{IL}})}[\sum\_{t=0}^{\infty}  \gamma^{t} R(\mathbf{s},\mathbf{a})]$ and $\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})]$. Then there exists a reward function, $R(\mathbf{s},\mathbf{a})$, and transition probabilities, $\mathcal{P}$, so $\mathrm{ALG} = \mathrm{OPT} \frac{1}{1+(K-1) \gamma}$.  

Theorem 2:     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 \abr{rmab-g} $(\mathcal{S},\mathcal{A},R\_{i},R\_{\mathrm{glob}},P_{i},\gamma)$, let $R'\_{i}(s\_{i},a\_{i}) = R\_{i}(s\_{i},a\_{i}) + p\_{i}(s_{i}) a\_{i}$, and let the induced linear \abr{rmab} be $(\mathcal{S},\mathcal{A},R'\_{i},P\_{i},\gamma)$. 
    Let $\pi\_{\mathrm{IL}}$ be the iterative Linear-Whittle policy, and let $\mathrm{ALG} = \mathbb{E}\_{(\mathbf{s},\mathbf{a})\sim (P,\pi\_{\mathrm{IL}})}[\frac{1}{T} \sum\_{t=0}^{T-1}  R(\mathbf{s},\mathbf{a})]$. 
    For any policy, $\pi$, let $\pi\_{i,t}$ be the augmented policy that pulls arms according to $\pi$ and additionally pulls arm $i$ at timestep $t$.  
    If $\mathbb{E}\_{(\mathbf{s},\mathbf{a})\sim (P,\pi\_{i,t})}[\frac{1}{T} \sum\_{t=0}^{T-1}  R(\mathbf{s},\mathbf{a})] \geq \mathbb{E}\_{(\mathbf{s},\mathbf{a})\sim (P,\pi)}[\frac{1}{T} \sum\_{t=0}^{T-1}  R(\mathbf{s},\mathbf{a})]$ and the induced linear \abr{rmab} is irreducible and indexable with the uniform global attractor property, then $\mathrm{ALG} \geq \frac{1}{K} \mathrm{OPT}$ asymptotically in $N$ for any set of transitions, $\mathcal{P}$. 

Proof sketch of Theorem 1: To demonstrate an upper bound on the performance of the iterative Linear-Whittle policy, we construct a reward function with $2K-1$ arms. The optimal policy always pulls arms $1$ and $K+1,\ldots,2K-1$, while the iterative Linear-Whittle policy pulls arms $1,\ldots,K$. We construct the reward function in such a way that the reward of pulling arms $1,\ldots,K$ is $1$ for each timestep, while pulling arms $1$ and $K+1,\ldots,2K-1$ results in a reward of $1 + (K-1) \gamma$ per timestep. 

Proof sketch of Theorem 2: To demonstrate a lower bound on the performance of the iterative Linear-Whittle policy, we first demonstrate that the iterative Linear-Whittle policy with budget $K$ does no worse than the Linear-Whittle policy with budget $1$. We then show that the Linear-Whittle policy with budget $1$ is at least a $\frac{1}{K}$ of the optimal reward. Taken together, this implies that the iterative Linear-Whittle policy achieves at least $\frac{1}{K}$ of the optimal reward.

Meta-review: The paper is acknowledged to make several foundational contributions in the theory and algorithms for restless bandits with non-additive ('global') reward structure across the arms. 

There were some concerns raised by some of the referees about the applicability of the problem to real world settings. The author response issued clarifications, which have been helpful in understanding the importance of modeling nonlinear, global rewards in several applications depending on the underlying objective. 

In view of the largely favorable views expressed in the referees and the strengths of the submission, the paper is recommended for acceptance.
Decision: Accept (poster)