Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks
Authors: Arpita Biswas
Jackson A. Killian
Paula Rodriguez-Diaz
Susobhan Ghosh
Milind Tambe
Venue: NeurIPS 2022 Submitted (2022)
Keywords: sequential planning
load balancing
Whittle indices
markov decision processes

Abstract: Motivated by applications such as machine repair, project monitoring, and anti-poaching patrol scheduling, we study intervention planning of stochastic processes under resource constraints. This planning problem has previously been modeled as restless multi-armed bandits (RMAB), where each arm is an intervention-dependent Markov Decision Process. However, the existing literature assumes all intervention resources belong to a single uniform pool, limiting their applicability to real-world settings where interventions are carried out by a set of workers, each with their own costs, budgets, and intervention effects. In this work, we consider a novel RMAB setting, called multi-worker restless bandits (MWRMAB) with heterogeneous workers. The goal is to plan an intervention schedule that maximizes the expected reward while satisfying budget constraints on each worker as well as fairness in terms of the load assigned to each worker. Our contributions are two-fold: (1)~we provide a multi-worker extension of the Whittle index to tackle heterogeneous costs and per-worker budget and (2)~ we develop an index-based scheduling policy to achieve fairness. Further, we evaluate our method on various cost structures and show that our method significantly outperforms other baselines in terms of fairness without sacrificing much in reward accumulated.

Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks
Anonymous Author(s)
Affiliation Address
email
Abstract
Motivated by applications such machine repair, project monitoring, and anti- poaching patrol scheduling, we study intervention planning of stochastic processes under resource constraints. This planning problem has previously been modeled restless multi-armed bandits (RMAB), where each arm is an interventionddppeddee Markov Decision Process. However, the existing literature assumes all intervention resources belong to a single uniform pool, limiting their applicability to real-world settings where interventions carried out by set of workers, each with their own costs, budgets, and intervention effects. In this work, we consider a novel RMAB setting, called multi-worker restless bandits (MWRMAB) with heterogeneous workers. The goal is to plan an intervention schedule that maximizes the expected reward while satisfying budget constraints on each worker as well as fairness in terms of the load assigned to each worker. Our contributions are two-fold: (1) we provide a worker extension of the Whittle index tackle heterogeneous costs and per-worker budget and (2) we develop an index- based scheduling policy to achieve fairness. Further, we evaluate our method on various cost structures and show that our method significantly outperforms other baselines in terms of fairness without sacrificing much in reward accumulated.
2
4
6
8
10
11
12
13
14
15
16
17
Introduction
18
19
Restless multi-armed bandits (RMABs) Whittle 1988 have been used for sequential planning, where planner allocates limited set of M intervention resources across N independent heterogeneous arms (Markov Decision processes) at each time step in order maximize the long-term expected reward. The term restless denotes that the arms undergo state-transitions even when they are not acted upon (with a different probability than when they are acted upon). RMABs have been receiving
20
21
23
24 increasing attention across wide range of applications such as maintenance Abbou and Makis
2019]. recommendation systems Meshram et al 20155] anti-poaching patrolling Qian et al. 2016b]. 25
and adherence monitoring [Akbarzadeh and Mahajan 2019 Mate et al. 2020 Although, rangers
27 in anti-po mniipooching. healthcare workers in health intervention planning, and supervisors in machine maintenance are all commonly cited examples of human workforce used as intervention resources, the worker
29 literature has so far ignored one key reality that the human workforce is heterogeneous- has their workload constraints and needs to commit dedicated time duration for intervening
31 an arm. Thus, it is critical to restrict intervention workload for each worker and balance the workload
32 across them, while also ensuring high effectiveness (reward) of the planning policy.
33 RMAB literature does not consider this heterogeneity and mostly focuses on selecting best arms assuming that all intervention resources (workers) are interchangeable, i.e., as from single pool 35 (homogencous). However, planning with human workforce requires more expressiveness in the model, including heterogeneity in costs and intervention effects, worker-specific load constraints, and
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37
[016a] with N areas in national park where timely interventions (patrols) are required to detect as many snares possible across all the areas. These interventions are carried out by a small set of M ranger. The problem of selecting a subset of areas at each time step (say, daily) has been modeled as an RMAB problem. However, each ranger may incur heterogeneous cost (e.g., distance travelled, when assigned to intervene on a particular area) and the total cost incurred by any ranger (e.g., total distance traveled) must not exceed given budget. Additionally, it is important to ensure that tasks balanced work allocation. One concrete example is anti antchpog intervention planning Qian et al.
38
39
40
41
42
43
44 are allocated fairly across rangers so that, for e.g., some rangers are not required to walk far greater distances than others. Adding this level of expressiveness to existing RMAB models is non-trivial.
To address this, we introduce the multi-worker restless multi-armes bandits (MWRMAB) problem. Since MWRMABs are more general than the classical RMABs, they are at least PSPACE hard to solve optimally [Papadimitriou and Tsitsiklis 1994]. RMABs with k-state arms require solving a combined MDP with kad states and JM + 1P actions constrained by a budget, and thus suffers from the curse of dimensionality. A typical approach is to compute Whittle indices [Whittle 1988 for each arm and choose M arms with highest index values- an asymptotically optimal solution under the technical condition indexability [Weber and Weiss 1990]. However, this approach is limited to instances single type of intervention resource incurring one unit cost upon intervention. A few papers 54 on RMABs [Glazebrook et al. 2011 Meshram and Kaza 2020] study multiple interventions and global budget (instead of per- worker budget). Existing solutions
46
47
48
49
50
51
52
53
non non-umitary costs but assumes aim at maximizing reward by selecting arms with highest index values that may not guarantee faimness towards the workers who are in charge of providing interventions.
56
58
To the best of our knowledge, we are the first to introduce and formalize the multi-worker restless multi-armed bandit (MWRMAB) problem and a related worker-centric fairness constraint. We develop a novel framework for solving the MWRMAB problem. Further, we empirically evaluate our algorithm to show that it is fair and scalable across range of experimental settings.
59
60
61
2
Related Work
62
69
Multi-Action RMABs and Weakly Coupled MDPs Glazebrook et al. [201]] develop closed-fome
64
solutions for multi-action RMABs using Lagrangian relaxation. Meshram and Kaza 2020 build simulation-based policies that rely on monte-carlo estimation of state-action values. However, critically, these approaches rely on actions being constrained by single budget, failing capture the heterogeneity of workforce. On the other hand, weakly coupled MDPs (WCMDPs) Hawkins 2003 allow for such multiple budget constraints: this is the baseline we compare against. Other theoretical
65
66
87
68
69 works Adelman and Mersercaul (2008); Gocgun and Ghate (2012) have developed solutions in terms of the reward accumulated, but may not scale well with increasing problem size. These papers do not consider fairness, crucial component of MWRMABs, which our algorithm addresses.
70
71
Fairness in stochastic and contextual multi- armed bandits (MABs) (Patil et al. 2020 Joseph et al. 2016 Chen et al.) 2020) has been receiving significant attention. However, fairness in RMABs has been less explored. Recent work by Herlihy af. [20TT] considered quota-based fairness of RMAB arms assuming that arms correspond to human beneficiaries (for example, patients). However, in our work, we consider an orthogonal problem of satisfying the fairness among intervention resources (workers) instead of arms (tasks).
73
74
75
78
77
78
Fair allocation of discrete items among a set of agents has been well studied topic [Brndd et al. 2016). Fairness notions such as envy-freeness up to one item [Budish] 2011] and their budgeted settings (Wu et al. 2021 Biswas and Barman 2018 align with the faurness notion consider. However, these papers do not consider non non-stationary (MDP) items. Moreover, these papers assume
79
81
82 that each agent has a value for every item; both fairness and efficiency are defined with respect to this
83 valuation. In contrast, in MWRMAB, efficiency is defined based on reward accumulated and faimnsss and budget feasibility are defined based on the cost incurred.
84
3 The Model
85
There are M workers for providing interventions on N independent arms that follow Markov Decision 87 Processes (MDPs). Each MDP i E [N] is a uple (St, A,, C, P., R2), where S, a finite set of states.
86
We represent each worker an action, along with an additional action called no- no-interventton. Thus,
2

---

action set is A, S [M]] U (0). C2 is a vector of costs Cij incurred when an action j E [A.] is taken on 89
90 an arm E [M]. and Gjj when 0. p is the probability of transitioning from state state
91 s' when arm i is allocated to worker j. Rs)s) is the reward obtained in state E S...
92 The goal (Bq. D to allocate a subset of arms to each worker such that the expected reward is
93 maximized while ensuring that each worker incurs a cost of at most fixed value B. Additionally,
94 the disparity in the costs incurred between any pair of workers does not exceed a fairness threshold e at given time step. Let us denote policy π X,S; + A,A, that maps the current state profile of
96 arms to an action profile. z (+) E {0, 1 indicates whether worker j /intervenes on arm at state s
97 under policy æ. The total cost incurred by j at time step i is given by C₁ == EiEn Gjzz (s)()).
98 where (t) is the current state. 2 ct maxi Cig ensures feasibility of the faimesss constraints.
T
max
lim sup
T T-00
Σ
(c)s:(O)) of (o(())
R
NE[N]
s.t.
Σ 0 (si(t) Gj S B,
Ae AA E (1,
iEN
(I)
Σ 2. (s:(t) = =1, SEA,
IiE a (1,
max
Cj (t) min min ())) Vte {
, 2 (t)) E {0,
Vi, Aj, Vt.
99
When M and C11 1, Problem 4 becomes classical RMAB problem (with two actions, active and passive) that can be solved via Whittle Index method [Whitlee] 1988] by considering a time-averaged relaxed version of the budget constraint and then decomposing the problem into N subproblems- each subproblem finds a charge (s) on active action that makes passive action as valuable as the active action at state s. It then selects top B arms according to X; values at their current states. However, the challenges involved in solving a general MWRMAB (Eq. I are (i) index computation becomes non-trivial with M > workers and (ii) selecting top arms based on indices may not satisfy fairness. To tackle these challenges, we propose framework in the next section.
100
101
102
103
105
4 Methodology
107
108
Step 1: Decompose the combinatorial MWRMAB problem to N x M subproblems, and compute
109
Whittle indices Xi₃ for each subproblem. We tackle this in Sec. 4. This step assumes that, for each
110
arm i, MDPs corresponding to any pair of workers are mutually iddeenddnt. However, the expected
111
value of each arm may depend on interventions taken by multiple workers at different timesteps.
112
Step 2: Adjust the decoupled indices Xiy to create
X,y adji* detailed in Sec. 4.2
113
Step 3: The adjusted indices are used for allocating the arms to workers while ensuring fairness and
114
per-timestep budget feasibility among workers, detailed in Sec. 4.
115
4.1 Identifying subproblem structure
116 To arrive at a solution strategy, we relax the per-timestep budget constraints of Eq. | to time- averaged constraints, as follows: # Eie[M EΣI 27 (8i(()) cit < B, Vj E [M]. The optimization
117
118 problem ! can be rewritten as:
min max lim sup fA220) " Tox T
1
Σ E Σ
+ Σ 2j(B - (153(()(()(
KE|M]
JEMM
s.t. Σ (s)(t) 1,
ViE [N], t (1,
jEa,
j (a) min 0)(() Se
ViE (1,
())( E 10,
Vi, VJ, VE
(2)
3

---

Here, AyS are Lagrangian multipliers corresponding to each relaxed budget constraint j E [M.] Furthermore, as mentioned Glazebrook et al. [20TT] if an arm is indexable, then the optimization objective 2 can be decomposed into N independent subproblems, and separate index functions can be defined for each arm i. Leveraging this, we decompose our problem to N x M subproblems, each finding the minimum Xig that maximizes the following:
119
120
122
123
limsup =B B
lim sup T-
Σ 1=1
(R.(s.(t)) - )gers) ( (x)(t)(t))
124
Note that, the maximization subproblem does not have the term At B since the term does not depend on the decision (t))) Considering a 2-action MDP with action space Ai = {O,j] } for
125
126 an arm-worker pair, the maximization problem 3 can be solved by dynamic programming methods using Bellman's 's equations for each state to decide whether to take an active action (11)(s) = 1) when
127
128
the arm is currently at state s:
Ri(s)- - -ujey +)
pd vet (s', \g)) if af (t) =
as
(2 I.y.
S'ES:
(4)
Ri(s)+ Σ
pil
VI+1 (8', Asy), if x1g =0
E'E
129
Nig (8) = arg min (X: Vi. (s, = (s. 0))
(5)
130
We compute the Whittle indices X1, (Fq. 5 Qian et al.
2016b] (the algorithm is in Appendix
A
Additionally, establish that the Whittle indices of multiple workers are related when the costs and transition probabilities possess certain characteristics, enabling simplification of Whittle Index computation for multiple workers when there are certain structures in the MWRMAB problem.
132
Theorem 1. For an arm i, and pair of workers j and j' such that Cij + cij' and pšj poj' for every 8, s' E Sü, then their Whittle Indices are inversely proportional to their costs.
134
135
X1 Nr.
Cij' for each state s E S;
Cij
136
Proof. Let us consider an arm i and pair of workers j and j' such that pt = ptt of Whittle Index (s) for a worker j. is the minimum value at state such that,
se* By definition
137
Viy(s, 5)) - Vsy(s, ()) =
(6)
138 Eq.
can be rewritten by expanding the value functions as:
R4(s) - -,y +
Σ
ptd Villi''' -R(ss) + Σ pio Vi('s (5(3)) =0 SES,
S'ES
-Ay(s)cit + Σ
pd VA (s)s))
Σ d'ES.
Vi(s (s)s)) = 0
s'Es
139
where,
max (s(s) - a),(s) + E. ((s))] a=(0,}}
140 Next, we substitute all (5) terms by 2. After substitution, Eq. 7 is a function of only, ie., no X(s) eaj terms remain after substitution. We can rewrite Eq. as:
aey"
-r + Σ P Vi((' Σ pio Vi(ss, 2) =
(8)
S'ES,
s'ES,
Note that x= that minimizes Eq. S corresponnss to (s))) for any j. where (y is the Whittle index 143 for worker j. Therefore, for any two workers and j' with corresponding Whittle Indices (s)
142
and (s). we obtain (y(s) = (s) whenever pt piy" This completes the proof.
144
145
Theorem I also implies that, when the costs and effectiveness of two workers are equal, then their Whittle indices are also equal, stated formally in Corollary [
148
Corollary 1. For arm i, and pair of workers j and j' such that eij = Cijy and Ptù ptj for
148
every 8,8 5 E S,, then their Whittle Indices are the same.
(s)(s) Miye (s) for each state S..

---

149
4.2
Adjusting for interaction effects
150
The indices obtained using Alg. B] are not indicative of the true long-term value of taking that action in the MWRMAB problem. This is because, for given arm, the value of an intervention by worker j
151
152
in general depends on interventions by other workers j' at different timesteps.
153
Consider a 2-worker MWRMAB corresponding to an anti-poaching patrol planning problem, where each worker is type of "specialist" with different equipment (detailed in Fig. D.
154
155
The first ranger (worker), dj, has special equip- ment for clearing overgrown brush, and the sec- ond ranger, 02, has specialized equipment for detecting snares, e.g., metal detector. Assume 3 states for each patrol area as "overgrown and snared" (s 0), "clear and snared" (s 1), and "clear and not snared" (s = 2). Assume that reward is received only for arms in state
ay] [0.05, 0.95, 0.10)
ag
aag an a,] 10.00, 0.00, 0.95]
157
(0.75,0.76, 0.76, 0.75]
159
R-0
R-0
R=1
181
162
169
8 = 2, and that snares cannot be cleared from
[0.75, 0.75, 0.00)
areas with overgrown brush, i.e., P02 V.j- E
164
Specialist domain: where specific actions are required in each state to advance to the reward- giving state. Decoupled indices lead to sub-optimal policies, whereas adjusted indices perform well.
Figure 1:
165
M.. If we assume that each worker is "true" specialist- so, ranger I's equipment is inef- fective detecting snares, i.e., P12 0, and
166
167
188
ranger 2's equipment is ineffective at clearing overgrown brush, i.e., p 0 then the opti- mal policy is for ranger to act on the arm in state "overgrown and snared" and ranger 2 to act on the arm in state "clear and snared". However, the fully decoupled index computation for each ranger would reason about restricted MDPs that only have passive action and ranger type j available. So when computing, e.g., the index for ranger 1 in s O, the restricted MDP would have 0 probability of reaching state "clear and not snared",, since it does not include ranger 2 in its restricted MDP. This would correspond to an MDP that always gives 0 reward, and thus would artificially force the index for ranger 1 to be 0, despite ranger being the optimal action for 0.
189
170
171
172
173
174
175
176
177 To address this, we define new index notion that accounts for such inter-action effects. The key idea is that, when computing the index for given worker, we will consider actions of all other workers in future time steps. So in our poaching example, the new index value for ranger in s will increase compared to its decoupled index value, because the new index will take into account the value of ranger 2's actions when the system progresses
178
179
180
181
1 in the future. Note that the methods we build generalize to any number of workers M. However, the manner in which we incorporate the actions of other workers must be done carefully, We propose an approach and provide theoretical results explaining why. Finally, we give the full algorithm for computing the new indices.
182
185
185
For a given arm, to account for the inter-worker action effects, we define the new index for an action as the minimum charge that makes an intervention by j on that arm as valuable as any other worker j' in the combined MDP, with M + actions. That is, we seek the minimum charge for action that makes us indifferent between taking action j and not taking action j. a molkir extension Whittle's index notion. To capture this, we define an augmented reward function RJ (s. = R(*) - Xycj. Let X is the vector of {AG]SE(M) charges. We define this expanded MDP as M and the corresponding value function as V We now find adjusted index
New index notion:
186
187
188
189
190
192
adi.- A
using the following expression:
min arg migmin( (8, (8))).J) = V2L (8. (o))) )'E(M]() X,
193
where X_, a vector of fixed charges for all jr f j. and the outer min over j' simply captures the specific action j' that the optimal planner is indifferent to taking over action j at the new index value. Note, this the natural extension of the decoupled two-action index definition, Eq. (5). which defines the index as the charge on j that makes the planner indifferent between acting and, the only other option, being passive. Our new adjusted index algorithm is given in Alg. D
194
195
196
197
We use a binary search procedure to compute the adjusted indices since VV_, (y))) is convex in Ay. The most important consideration of the adjusted index computation is how to set the charges 199
198
Agr of the other action types j' when computing the index for action j. We show that a reasonable
5

---

Algorithm 1 Adjusted Index Computation
Input: An arm: MDP .M', costs cj, state s, and indices (5)..
costs
I: for j = 1 M do
2: }; = XJ (s) (init }}
3: for j= = 1 to M do
4: Compute , (+) [via binary search on Eq.
5: return A " (8) for all workers j E [M]
201
choice for Ay is the Whittle Indices X3 (s) which were pre-computed using Alg. The intuition is that A (s) provides a lower bound on how valuable the given action j' is, since it was computed against no-action in the restricted two-action MDP. In Observation I and Theorem 2 describe the
202
203
204
problem's 's structure to motivate these choices.
The following observation explicitly connects decoupled indices and adjusted indices.
Observation 1. For each worker j. when A- + co, i.e, Ny + x0 Vj' + j. then the following
206
holds:
odii* X3.
This can be seen by considering the rewards R (s, R(s) Ayrey for taking action j' in any state As the charge Ay - 30, R (s. + oc, making undesirable take action j' in the optimal policy. Thus, the optimal policy would only consider actions {0,j), which reduces to the restricted MDP of the decoupled index computation.
209
211
212
Next we analyze a potential naive choice for X-, when computing the indices for each j. namely, Though may seem a natural heuristic, this corresponds planning without considering the costs of other actions, which we show below can lead to arbitrarily low values of the indices, which subsequently can lead to poorly performing policies.
213
A_
214
215
Theorem 2. As Xy + O Vj + j. > will monotonically decrease, (f) V (8. Ar," 2
216
VL (8. Xj, 0) for 0 S >gg S e and (2) if the average cost of worker j' under the optimal policy starting with action j' greater than the average cost of worker j' under the optimal policy starting with action j.
218
Thm. 2 (proof in Appendix B confirms that, although setting ,y = 0 for all j' may seem like a natural option, in many cases it will artificially reduce the index value for action j. This is because 222 by = 0 corresponds to planning as if action j' comes with no charge. Naturally then, as we try to determine the non-zero charge xy we willing to pay for action j. i.e. the index of action j, we will be less willing to pay higher charges, since there are free actions j'. Note that conditions (1) and (2) of the above proof are not restrictive. The first is common desilon-neighhorhoodd condition, which requires that value functions do not change in arbitrarily non-smooth ways with À values near 0. The second requires that policy's 's accumulated costs of action j' are greater when starting with action j', than starting from any other action- this is same as assuming that the MDPs do not have arbitrarily long mixing times. That is to say that Thm. 2 aapplies to wide range of problems that we care about.
220
224
225
226
227
228
229
230
The key question then is: what are reasonable values of charges for other actions A_j, when computing the index for action j? We propose that a good choice is to set each Xy E X-j to its corresponding decoupled index value for the current state, i..., (s). The reason relies on the following key idea: we know that at charge { (s), the optimal policy is indifferent between choosing that action j' and the passive action, at least when j' is the only action available. Now, assume we are computing the new adjusted index for action j. when combined in planning with the aforementioned
232
233
234
235
236
action j' at charge (s). Since the charge for j' is already set at level that makes the planner indifferent between j' and being passive, if adding j' to the planning space with j does not provide any additional benefit over the passive action, then the new adjusted index for j will be the same as the decoupled index for j. which only planned with j and the passive action. This avoids the undesirable effect of getting artificially reduced indices due to under-charging for other actions j', i.e.,
237
238
239
240
Thm. 2 The ideas follow similarly for whether the adjusted index for should increase or decrease relative to its decoupled index value. Le.. higher reward can be achieved when planning with j and j' together compared to planning with either action alone, in the specialist anti- anti-poaching example
242

---

244
then we will become more willing to pay a charge X, now to help reach states where the action j' will let us achieve that higher reward. On the other hand, if j' dominates in terms of intervention effect, then even at reasonable charge for j', we will be less willing to pay for action j when both options are available, and so the adjusted index will decrease. We give our new adjusted index algorithm in Alg. and provide experimental results demonstrating its effectiveness.
245
247
249
4.3
Allocation Algorithm
250
We provide method called Balanced Allocation (Alg. 2) tackle the problem of allocating intervention tasks to each worker a balanced way. At each time step, given the current states of all the arms {sf) JELN. Alg. 2 creates an ordered list a among workers based on their highest Whittle Indices max Asy(s)) ) It then allocates the best possible (in terms of Whittle Indices) available arm to
251
253
each worker according to the order o in round-robin way (allocate one arm worker and move on to the next worker until the stopping criterion is met). Note that this satisfies the constraint that the same arm cannot be allocated to more than one worker. In situations where the best possible available am leads to the budget violation B, an attempt is made to allocate the next best. This process is repeated until there are no more arms left be allocated. If no available arms could be allocated
255
256
257
258
to worker j because of budget violation, then worker is removed from the future round-robs allocations and are allocated all the arms in their bundle D,. Thus, the budget constraints are always satisfied. Moreover, in the simple setting, when costs and transition probabilities of all workers are equal, this heuristic obtain optimal reward and perfect fairness.
260
262
Algorithm 2 Balanced Allocation
Input:
Current states of each [s:)i index values for each arm-worker (i,j) pair X (8.), costs {ogg) ). budget B. fairness threshold Coaaz.
Output: balanced allocation {Dz)se( where D, S [N). D. 0'v. [M].
1: Initiate allocation D, <- for all j E [M]
2: Let L + NN be the set of all unallocated arms
3: while true do
4: Let rj be the ordering over Ao values from highest to lowest: A(r; [L]][]]
5: Let be the ordering over workers hased their highest indices: [ 2 []] and
for = to M do
7:
if To, L 0 then I + (op(T;) L while Cary EnEDO, Chaz > B do
8:
9:
10:
Tay f- Toy \ {x)
11:
if Tap 0 then
12:
break
13:
else
14:
x f- top((TT) nL
15:
To 0 L & 0 then
16:
Do, + Da, Ufa); L+ L+ Ta + To, \ {x)
17:
return (D)bE.M
Theorem 3. When all workers are homogeneous (same costs and transition probabilities arms after intervention) and satisfy indexability, then our framework outputs the optimal policy while being exactly fair to the workers.
264
285
286
Proof sketch. The proof consists of two components: (1) optimality, which can be proved using Corollary (hittle Indices for homogeneous workers are the same), and the fact that the same costs lead to considering all workers from same pool actions, and (2) perfect fairness, using the fact that, when costs equal, Step of our algorithm divides the arms among workers in way such that the difference between the number of allocations between two workers differs by at most (see complete proof in Appendix D
268
270
5 Empirical Evaluation
273 We evaluate our framework on three domains, namely constant unitary costs, ordered workers, and specialist domain, each highlighting various challenging dimensions of the MWRMAB problem
7

---

275
(detailed in Appendix C In the first domain, the cost associated with all worker-an ari pairs is the same, but transition probabilities differ; the main challenge is in finding optimal assignments, though faimnsss is still considered. In the second domain, there exists an ordering among the workers such that the highest (or lowest) ranked worker has the highest (or lowest) probability of transitioning any arm to "good" state; which makes balancing optimal assignments with fair assignments challenging. The final domain highlights the need to consider inter-action effects via Step 2.
278
277
278
279
280
281
We run experiments by varying the number of arms for each domain. For the first and third domains that consider unit costs, we use B budget per worker, and for the second domain where costs are
282
283
in the range [1, 10], we use budget B = 18. We ran all the experiments on Apple MI with 3.2 GHz Processor and 16 GB RAM. We evaluate the average reward per arm over a fixed time horizon of
284
285
100 steps and averaged over 50 epochs with random or fixed transition probabilities that follow the characteristics of each domain.
286
287
Baselines We compare our approach, CWI+BA (Combined Whittle Index with Balanced Alloca- tion), against:
PWI+BA (Per arm-worker Whittle Index with Balanced Allocation) that combines Steps and of our approach, skipping Step (adjusted index algorithm)
290
CWI+GA (Combined arm-worker Whittle Index with Greedy Allocation) that combines Steps and 2 and, instead of Step 3 (balanced allocation), the highest values of indices are used for allocating arms to workers while ensuring budget constraint per timestep
292
294
Hawkins (0033 solves a discounted version of Eq. 2 without the fairness constraint, to compute values of Xy. then solves a knapsack over addaustte Q-values
295
OPT computes optimal solutions by running value iteration over the combinatorialll--snn exact problem 1 without The fairness constraint.
297
298
OPT-fair follows OPT, but adds the faimess constraints. These optimal algorithms are exponential in the number of arms, states, and workers, and thus, could only be executed on small instances.
289
300
Random takes random actions j E [M] U {0} on every arm while maintaining budget feasibility for every worker at each timestep
302
shows that reward obtained using our framework (CWI+BA) is comparable to that of the reward maximizing baselines (Hawkins and OPT) across all the domains. We observe at most 18.95 95% reduction in reward compared to OPT, where the highest reduction occurs for ordered workers
Results Figure
303
304
305
in Fig. lb). In terms of fairness, Figs. 2 a) and (c) show that CWI+BA achieves fair allocation among workers all timesteps. In Figure 1b) CWI+BA achieves fair allocation in almost all timesteps. The
306
307
fraction of timesteps where fairness is attained by CWI+BA is significantly higher than Hawkins and
308
OPT. In fact, Fig (b) also shows that Hawkins obtains unfair solutions at every timesteps (0 fairesss)
309
when 5 and B=18, and, when N=10 and N=15, Hawkins is fair only 0.41 and 0.67 fractions of the time, respectively. Thus, compared to reward maximizing baselines (Hawkins and OPT), CWI+BA achieves the highest fairness. We also compare against two versions of our solution approach, namely, PWI+BA and CWI+GA. We observe that PWI+BA accumulates marginally lower reward while CWI+GA performs poorly in terms of fairness, hence asserting the importance of using CWI+BA for the MWRAMB problem.
310
311
312
313
314
315
Fig 3 shows that CWI+BA is significantly faster than OPT-fair (the optimal MWRMAB solution), with an execution time improvement of 33%, 78% and 83% for the three domains, respectively, when N=5. Moreover, for instances with N=10 onwards, both OPT and OPT- ran out of memory because the execution of the optimal algorithms required exponentially larger memory. However, we observe that CWI+BA scales well even for N = 10 and N = 15 and runs within a few seconds, on an average.
316
317
318
319
320
321
Fig. further demonstrates that our CWI+BA scales well and consistently outputs fair solution for higher values of N and B. On larger instances, with N E (50, 100, 150), our approach achieves up to 374.92% improvement in faimess with only 6.06% reduction in reward, when compared against the ewwardmmximiziing solution Hawkins 20033.
322
323
324
325 In summary, CWI+BA is fairer than reward-maximizing algorithms (Hawkins and OPT) and much faster and scalable compared to the optimal fair solution (OPT fair), while accumulating
8

---

Nourt per sm
Man
0.0
N-5 1--1
N-10
N:15 B-4
N:5 8:18
N:10
N:15 0:18
N-5
N:10D44
N:150-4
Focchee of fbrr airalleen callcoaoon
0.5
(a) Corstant unitary costs
(5) Ordkaed worken
(0 Specialist domaia
Figure 2: Mean reward (top row) and fraction of time steps with fair allocation (bottom row) for N = 5, 10, 15 arms. CWI+BA (blue) achieves highest fraction of fair allocations than Hawkins (white) algorithm while attaining almost similar reward the reward-maximing baselines.
CWI-BA
PK
Hawkin
OPT
OPT Fair
0.4
2.0
Axragg rintime
0,3
1.5
(ccords)
000 Constant mnitnry costs
(bj Citlend workers
(0) Specialist domaln
Figure 3: Execution time averaged 50 epochs for N - 10, 15. For fixed time horizon of 100 steps, CWI+BA run faster than Hawkins (white), OPT (dark gray), and OPT fair (light gray) for all instances in each of the three domains evaluated.
CWI+BA
PWI-BA
CWI+GA
Howkins
1.0
Fraction of fair alfocatines
1.0
Meen
0.5
8:50 8:40
0.61-/0001
0.52+//0.0
0.584/0001
N:100 8:40
2.77-/.0022
2.404/0.04
1.33//0.22
N:150 B:40
9.72-/0006
8.11+/0.15 2.74//0.3
Figure 4: The plot shows mean reward (left), fairness (middle), and run time (right) for N 50, 100, 150 arms constant unitary costs domain. CWI+GA scales well for larger instances, and even for N=150 arms, the average runtime is 10 seconds.
327 reward comparable to Hawkins and OPT across all domains. Therefore, CWI+BA shown to 328 be a fair and efficient solution for the MWRMAB problem.
Conclusion
329
330
We are the first to introduce multi-worker restless multi-armed bandit (MWRMAB) problem with worker-centric faimess. Our approach provides scalable solution for the computationally hard
332
MWRMAB problem. On comparing our approach against the (non-scalable) optimal fair policy on smaller instances, we find almost similar reward and faimess.
334
Our problem formulation provides a more general model for the intervention planning problem capturing heterogeneity of intervention resources, and thus it is useful to appropriately model real- world domains such as anti- anti-poaching patrolling and machine maintenance, where the interventions provided by human workforce.
396

---

References
338
339
Abderrahmane Abbou and Viliam Makis. Group maintenance: A restless bandits approach. INFORMS Journal on Computing, 31(4):719- 731,,,11,,,, 2019.
341
Daniel Adelman and Adam J. Mersereau. Relaxations of weakly coupled stochastic dynamic programs. Operations Research, 56(3):712-727, 2008.
343
N. Akbarzadch and A. Mahajan. Restless bandits with controlled restarts: Indexability and computa- tion of whittle index. In 2019 IEEE Conference Decision and Control. IEEE, 2019,
345
Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 91-97, 2018.
347
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of computational social choice, Chapter 12. Cambridge University Press, 2016.
348
349
Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 11966):061-1103; 2011.
350
Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. Fair contextual multi-armed bandits: Theory and experiments. In Conference on Uncertainty in Artificial Intelligence, pages 181-190. PMLR, 2020.
352
354
Kevin D. Glazebrook, David J. Hodge, and Christopher Kirkbride. General notions of indexability for queueing control and asset management. The Annals of Applied Probability, 21(3):876-909 2011.
355
356
Yasin Gocgun and Archis Ghate. Lagrangian relaxation and constraint generation for allocation and advanced scheduling. Computers & Operations Research, 39(10):2323-2336 2012.
358
Jeffrey Thomas Hawkins. A Langrangian decomposition approuch to weakly coupled dynamic optimization problems and its applications. PhD thesis, Massachusetts Institute of Technology, 2003.
360
361
Christine Herlihy, Aviva Prins, Aravind Srinivasan, and John Dickerson. Planning to fairly allocate: Probabilistic fairness in the restless bandit setting. arXiv preprint wxXiv22106.07677 2021.
362
363
Matthew Joseph, Michael Kearns, Jamie H Morgenstem, and Aaron Roth. Fairness in learning: Classic and contextual bandits. Advances Neural Information Processing Systems, 29:325-333,
384
385
2016.
366
Aditya Mate, Jackson A Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application to public health interventions. In Advances in Neural Information Processing Systems, 2020.
387
388
369
Rahul Meshram and Kesav Kaza. Simulation based algorithms for markov decision processes and multi-action restless bandits. arXiv preprint arXiv:2007. 2020.
370
371
Rahul Meshram, D Manjumath, and Aditya Gopalan. restless bandit with no observable states for recommendation systems and communication link scheduling. In 2015 54th IEEE Conference Decision and Control (CDC), pages 7820-7825. IEFF, 2015.
373
Christos H Papadimitriou and John N Tsitsiklis. The complexity of optimal queueing network control. In Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory, pages 318-322. IEEE, 1994.
375
377 Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Y Narahari. Achieving fairness the stochastic multi-armed bandit problem. In Proceedings of the AAAI Conference Artificial Intelligence. volume 34, pages 3379- 2020.
379
Y. Qian, C. Zhang, B. Krishnamachari, and B. Tambe. Restless poachers: Handling exploration- exploitation tradeoffs in security domains. In International Joint Conference on Autonomous Agents and Mueti-Agent Systems, AAMAS. IFAAMAS, 2016.
381
10

---

383
Yundi Qian, Chao Zhang, Bhaskar Krishnamachari, and Milind Tambe. Restless poachers: Handling apploration-epllotaaiie tradeoffs in security domains. In Proceedings of the 2016 International Conference on Aulonomous Agents & Multiagent Systems, pages 123-131, 2016.
384
Richard R Weber and Gideon Weiss. On an index policy for restless bandits. J. Appl. Probab., 27(3):637-644) 1990.
387
388
Peter Whittle Restless bandits: Activity allocation in a changing world. Journal of applied probability, pages 287-298, 1988.
390
Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare is almost envy- free. In The 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), pages 1-16, 2021.
381
392
Checklist
394
1. For all authors...
395
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
396
contributions and scope? [Yes]
387
(b) Did you describe the limitations of your work? [Yes] (see Appendix F
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(see
399
Appendix|Bi E
400
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
401
402
2. If you are including theoretical results...
403
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
405
3. If you ran experiments..
408
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
407
408
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
409
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
411
412
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
413
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
415
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
417
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
418
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
420
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
421
422
5.
If you used crowdsourcing or conducted research with human subjects...
423
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
424
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
426
427
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
11


Reviews:
[{"review_id": "dRZmUKbfmWk", "reviewer": "Reviewer_H4ZJ", "summary": "The authors study the problem of multi-worker restless bandits, that extends the standard restless bandits having different costs and fairness constraints on different actions. The authors propose a scheme that at first decouples the problem and than, using the decoupled solutions, introduce the interaction with other workers. Finally, some experiments comparing the proposed algorithm to the ones present in the literature (which do not include the fairness constraint) are provided.", "questions": "It is not clear to me if the solution you provided is solving the original problem or if it is an approximate solution. In the former case, I would like to have a formal statement about that, in the latter case a study on the approximation gap.\n\nIs Theorem 3 only predicating on those instances having that all the workers are of the same type? I would like to understand if in this theorem we are restricting to a specific case or not.", "limitations": "I do not foresee limitations and potential negative societal impacts. The paper is focused on the idea to make the work allocation task fair, therefore at the moment i only see positive impacts on society.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well structured and the definition of the steps taken to get to the solution is helping the reader to understand the idea behind the paper. There are a few ortographic mistakes. The topic is interesting and the solution is well motivated empirically.\n\nI have some doubts about the real formulation of some of the results and the strenght of the theoretical results provided.\n\n\nMinor:\nLine 99: \"M=1\" I got the idea, but i think that the more formal statement would be c_ij = c_ih=1 \\forall j,h \\in [M]\nLine 130: It is not clear the statement. Is it \"by relying on the work by qian et al.\"? Or is it a derivation from the previous work?\nLine 283: Please provide the rationale behind the choice of B)18.\nLine 297: The -> the\nFigure 4: I suggest to rearrange the subplots and the table, to better explain the results therein.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VUbHSibVTUY", "reviewer": "Reviewer_QfKj", "summary": "This paper considers a multi-worker version of the restless multi-armed bandit problem where the intervention on a particular arm can be carried out by one of M possible workers. The workers have possibly different costs for intervening on different arms and the goal is to design an optimal allocation policy that satisfies budget constraint for each worker and also fair.  \n\nThe authors devise a heuristic balanced allocation rule for the problem. The main idea behind the algorithm is to decompose the original problem into several related subproblems. The experiments show that the proposed heuristic scales with the number of agents without compromising too much on the objective.\n\n", "questions": "1. The original optimization problem (1 and 2) has the fairness constraint. However, this constraint is absent in the subproblem (3). How do you guarantee that solving each subproblem will automatically generate a fair solution?\n\n2. Also I am not sure when solving each subproblem is sufficient to solve the original problem~(2). Do you have any result showing that you can obtain a solution of the original problem by solving the $N\\times M$ subproblems?\n \n3. I don't understand why theorem 1 is useful. It seems to me this theorem is only used to derive Corollary 1 for the case of identical cost and probability transition function. But doesn't that directly follow from the nature of the optimization problem (3) by substituting identical cost and probability transition function?\n\n4. Theorem 3 states that the algorithm balanced allocation works only when the workers are homogeneous. But I thought the whole point of introducing the general framework was to handle workers with heterogeneous costs. Do you have any results for the setting with heterogeneous costs?\n\n5. The balanced allocation takes fairness threshold $\\epsilon$ as input. But as far as I can understand, the algorithm never explicitly uses this argument. It would be nice if you could clarify which step of the algorithm uses this parameter? Also regarding this, do you have any guarantee for the fairness guarantee obtained by the balanced allocation algorithm? ", "limitations": "This paper doesn't have any negative societal impact.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- I think the multi-worker extension of the restless multi-armed bandit problem is an interesting direction and certainly more practical.\n- The empirical section is interesting as the authors could show that the proposed approximation algorithm runs fast for a large number of agents ($N$ is of the order of hundreds) and the performance doesn't deteriorate much.\n\nWeaknesses:\n- The main weakness of the paper is the lack of proper theoretical guarantees. First, it is not clear if you can decompose the original problem~(2) into $N \\times M$ subproblems because of the additional fairness constraint. Second, the main result also shows that the proposed algorithm works only for homogeneous workers (theorem 3) and it's not clear if the balanced allocation works when the costs are heterogeneous.\n- Even if I assume that the problem is decomposable the authors don't bound fairness violation of the final solution. Note that fairness is a global constraint and the individual subproblems don't have this constraint. So it is not trivial to combine the solutions of these subproblems and ensure a desired level of fairness. \n- For the adjusted index algorithm it is not clear what is the right choice of the variables $\\lambda_{-j}$ for each $j$. The authors justified that choosing $\\lambda_{-j} = 0$ is not optimal, and chose these values based on Whittle indices. But I am not sure that should be optimal either because of heterogeneous costs and global constraints. Maybe you can solve for a fixed point of this system and use the fixed point as the adjusted indices?\n\nSome other comments:\n- Give definition of indexability of arms.\n- At the end of section 3, the authors highlight two challenges for MWRMAB model. It might be a good idea to illustrate these challenges with an example.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8Fa1_xp8u11", "reviewer": "Reviewer_TAkH", "summary": "This paper considers constrained resource allocation tasks framed as restless bandit problems. In contrast to prior work in this space which assumes that all of the resources (i.e., healthcare workers, mechanics, etc.) to be allocated are interchangeable, the authors: (a) consider *heterogeneous* workers with individual/varied costs, budgets, and intervention effects; and (b) strive to optimally allocate arms to workers while ensuring the disparity in costs incurred by any two workers does not exceed a given threshold, $\\epsilon$. To do this, the authors define an augmented action space, such that each worker is represented as a possible active action, with a corresponding worker-arm-specific cost function and transition matrix. They then decompose the problem and compute Whittle indices for each worker-arm combination. They use these Whittle indices to compute an adjusted index that reflects the minimum charge required to make the agent indifferent between an active action provided by worker $j$ and one provided by any other worker $j^\\prime$. They use the adjusted indices to inform budget- and fairness-constraint satisfying round-robin allocation of arms to workers.", "questions": "1. How is fair allocation defined/operationalized in the empirical results?\n2. Could the knapsack portion of the Hawkins approach be modified to encode the type of cost-disparity threshold fairness considered here?", "limitations": "The authors acknowledge that incorporating fairness among workers (i.e., with respect to the number of arms each worker is allocated) will, in general, reduce expected total reward relative to a fairness-agnostic (but otherwise equivalent) approach. An additional limitation is that worker-specific transition matrices are assumed to be known by the agent. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*:\n- The paper is well-written and the extension to the RMAB setting that the authors propose (i.e., actions with arm-specific heterogenous costs and effectiveness) is well-motivated by many practical domains, such as healthcare, manufacturing, and wildlife conservation. The technical work required to extend the problem setting in this way is significant since one must now account for how workers with different (arm/state-specific) expertise may interact (and influence arms' transitions) over time.\n\n*Weaknesses*:\n- Arms' states and worker-specific transition matrices are assumed to be observable. While it is conventional to assume each arm's (worker-agnostic) transition matrix is known by the decision-maker in the planning setting, the assumption that this additional level of information is available should be explicitly stated and justified by the availability/\"learnability\" of this type of information within the domain(s) of interest. This will be particularly important in settings where there is heteroskedastic uncertainty about workers' intervention effects. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject