Learning Infinite-Horizon Average-Reward Restless Multi-Action Bandits via Index Awareness
Authors: GUOJUN XIONG
Shufan Wang
Jian Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: Restless Bandits
Reinforcement Learning
Index Policy
Finite-time Analysis

Abstract: We consider the online restless bandits with average-reward and multiple actions, where the state of each arm evolves according to a Markov decision process (MDP), and the reward of pulling an arm depends on both the current state of the corresponding MDP and the action taken.  Since finding the optimal control is typically intractable for restless bandits, existing learning algorithms are often computationally expensive or with a regret bound that is exponential in the number of arms and states.  In this paper, we advocate \textit{index-aware reinforcement learning} (RL) solutions to design RL algorithms operating on a much smaller dimensional subspace by exploiting the inherent structure in restless bandits.  Specifically, we first propose novel index policies to address dimensionality concerns, which are provably optimal.  We then leverage the indices to develop two low-complexity index-aware RL algorithms, namely, (i) GM-R2MAB, which has access to a generative model; and (ii) UC-R2MAB, which learns the model using an upper confidence style online exploitation method.  We prove that both algorithms achieve a sub-linear regret that is only polynomial in the number of arms and states.  A key differentiator between our algorithms and existing ones stems from the fact that our RL algorithms contain a novel exploitation that leverages our proposed provably optimal index policies for decision-makings. 

Learning Infinite-Horizon Average-Reward Restless Multi-Action Bandits via Index Awareness
Guojun Xiong, Shufan Wang, Jian Li SUNY-Binghame University
{gxiongl, swang224, 1iiiee,iiiiiiiiiiiieeeeee @bigghantonnnnn. edu
Abstract
We consider the online restless bandits with average-reward and multiple actions, where the state of each evolves according to Markov decision process (MDP), and the reward of pulling an arm depends on both the current state of the corresponding MDP and the action taken. Since finding the optimal control is typically intractable for restless bandits, existing learning algorithms are often computationally expensive or with a regret bound that is exponential in the number of arms and states. In this paper, we advocate index-aware reinforcement learning (RL) solutions design RL algorithms operating on much smaller dimensional subspace by exploiting the inherent structure in restless bandits. Specifically, we first propose novel index policies address dimensionality concern,, which are provably optimal. We then leverage the indices to develop two low-complexity index-aware RI. algorithms, namely, (i) GM-R2MAB, which has access to generative model; and (ii) UC-R2MAB, which learns the model using an upper confidence style online exploitation method. We prove that both algorithms achieve a sub- linear regret that is only polynomial in the number of arms and states. A key differentiator between our algorithms and existing ones stems from the fact that our RL algorithms contain a novel exploitation that leverages proposed provably optimal index policies for decision- decision-makings.
Introduction
Restless multi-armed bandits (RMAB)
64 have been used to model variety of sequential decision
making problems such as congestion control 7
6
job scheduling [51] I3 68) wireless communi-
cation [57 21 20 71 healthcare
2
4
48
40
queueing systems 28
32
5
To
4
41
[ 57 In RMAB, there is collection of N arms, each of which is endowed with state that evolves independently according a two-action Markov Decision Process (MDP) (55) If the arm is "pulled" or "activated" at any moment in time, it advances stochastically according to one transition kernel, and if not, then it advances according to a different kernel. Rewards are generated with each transition, and the goal is to maximize the expected total reward over an infinite horizon, subject to a constraint on the number of arms activated at any moment in time.
and cloud computing 17
critical limitation classical RMAB frameworks is that only two actions, either pulled or not pulled, allowed for each arm. This is restrictive since the decision maker in many applications often has access to multiple actions for each arm 40 [8.. To this end, we consider an exaderee generalization of RMAB that allows for multiple actions per with different degrees of costs, which we call the restless multi-ac multi-action multi-armed bandits, dubbed as R2MAB, in the infinite-horizon average- reward setting. Our objective is develop simple reinforcement learning (RL) algorithms solve R2MAB without knowing the underlying MDPs associated with each arm. Although RMAB or R2MAB has found its success in many applications as aforementioned. the fundamental theoretical understanding of how to develop low computation-complln and order-of-optimat regret RL algorithms, two of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the most important performance metrics for online restless bandits, remains in its infancy so far. In particular, three important aspects of RL algorithms for RMAB or R2MAB deserve special attentions:
5 for RMAB often leverage heuristic policy in the exploitation phase, e.g., constantly pulling one arm, which does not have any performance guarantee. Hence, these policies may not perform close to the offline optimum. This is partially due to the fact that finding an optimal solution for RMAB is PSPACE-hard [54] hence infeasible. The fundamental challenge lies in the explosion of state space and the curse of dimensionality prevents computing optimal policies. Though Whittle index policy [64] is powerful tool to address the state space explosion, finding the Whittle index is typically intractable [31].
>> First, most upper confidence bound (UCB) based policies 45
Second, existing RL algorithms with theoretical guarantee of sub-linear regret upper bound, e.g.. colored-UCRI.2 (53]), suffers from an exponential computational complexity, and the regret bound is exponential in the number of states and arms. This is due to the fact that it needs solve Bellman equations with an exponentially large space set. Likewise, the class of Thompson sampling based algorithms BB 7 provide theoretical guarantees in the Bayesian setting, where the updates can be computationally expensive, especially when the likelihood functions are complex.
>> Third, although the design of low computation-complexty solutions for online RMAB has been gaining attentions, e.g.,
25
15
39
32
55
56. 661, many challenges remain unsolved. For
instance, [25
56 lacked fimite- time performance analysis and these
stochastic approximation algorithms often suffer from slow convergence. 665 66] focused on the
finite-horizon setting, which makes their approach not directly applicable to ours since the average reward setting studied in this paper is more challenging to analyze compared to the finite-horizon setting, which necessitates different proof techniques. [62) achieved low-complexity policy but is constrained to a specific birth-death Markovian model and is not easy to be directly generalized.
The lack of fundamental understanding how to design efficient RL algorithms for R2MAB in the infinite-horizon average-reward setting that consider the above three aspects in terms of provably optimal policy, computational complexity, exponential pre- factor in the regret bound, and sub-linear regret performance guarantees, motivates us to fill the gap by advocating index-aware RL solutions in this paper. Specifically, our index- subspace by exploiting the inherent structure encoded in R2MAB problems. This requires us to first design cow-compeexity provably optimal index policies for R2MAB, and then RL algorithms that leverage the structure of provably optimal index policies in the exploitation phase for decision- makings as reduce the high computational complexity and exponential factor in regret analysis. Our main contributions in this paper are summarized as follows:
RL solutions operate
much smaller dimensional
To address the dimensionality concerns in R2MAB, we first develop low-complexity index policies for R2MAB when the underlying MDPs are known. In contrast to the celebrated Whittle index policy, which requires the notoriously difficulttoo-veriffy indexability condition, we bypass the task of deriving index policies by taking a more general linear programming (LP) approach, and hence is computationally efficient. We show that our proposed index policy is asymptotically optimal.
We develop two index-aware RL. algorithms for horiion average-reward R2MAB, namely, (i) GM-R2MAB, generative model based approach that obtains samples initially then creates the model; and (ii) UC-R2MAB, an online approach wherein the model is updated as samples are obtained. Both algorithms follow a two-stage pattern of model construction and an index policy based solution. The algorithms solve an extended linear programming (ELP) problem from which we construct the provably optimal index policies to be executed during the exploitation phase in both algorithms. The key differentiator between our index-aware RL solutions and aforementioned state of the arts stems from two perspectives: (a) our index- RL solutions are computationally appealing since our index based solutions are merely based on solving an ELP, which is exponentially better than tfat-oof-the-ar methods such as colored-UCRL2 (b) our index-aware RL solutions contain novel exploitation phase by leveraging our proposed provably optimal index policy for decision-makings. rather than using heuristic or black-box oracle in aforementioned existing algorithms.
We provide the first-ever regret analysis for infinite-horizon average-reward R2MAB. We show that the above key differentiators in the design of GM-R2MAB and UC-R2MAB, contribute to their Ö(VT) regret, which is only polynomial in the number of arms and states. It is worth noting that GM-R2MAB and UC-R2MAB achieve low computational complexity and sub-linear Ō Ö(VT) regret with a polynomial fre-factor all at once, while none of aforementioned state of the arts achieve so.

---

2 Model Description and Problem Formulation
We consider the restless multi-action multi-armed bandits (R2MAB) problem in continuous time. There are a total of N arms. Each arm n. E NN described by a MDP (S, A, Pn: Tn:)), where S is the state space, A is the action space, (s (s a) indicates the probability of reaching state s' by taking action a in state s, and [s a) is the reward of each state- state-action pair (s, a). We assume that and A are finite sets with cardinalities S and A, respectively. Our results and analysis will still apply when each arm has its own sets of states and actions; so, without loss of generality, we will simply assume that all arms share the same state and action sets. We consider the unichain MDPs in this paper, which in fact is known to be necessary to guarantee the existence of stationary policies for the infinite-horizon average-reward R2MAB (and MDPs) regardless of initial states [5S] R
We refer to action a 0 as passive action and any action a > O as an active action. Moreover, using the standard terminology from the restless bandits literature 64 and passive otherwise. A cost is incurred when action a is applied to arm n in state s. For abuse of notation, we denote the cost as itself. We assume that the maximum cost to activating arms at any moment in time is B, which we call the activation budget.
call an arm active when an active action is applied
The decision- makinn scenario is as follows. At any moment in time f, each arm can be either active or passive. When action a, (t) = a is applied to arm n in state 8, (t) = 8, it takes an exponentially distributed amount of time to transition to state s' with rate (s, a, s'), Vs, S, a E A. Decision epochs/time are defined as the moments when the state of an arm changes. A policy determines what actions be applied each arm at each decision epoch, with the restriction that at most B activation budgets can be used for activating arms. After receiving an action, each arm incurs an immediate reward rn (t) = rn (s, (s,a), which is random variable with support [0, 1] and mean (s, a). Without loss of generality, we further assume that only active arms yield rewards, i.c., (n, 0) = 0, Vs E S.
Remark 1. In general, there are two reward models considered in RMAB literature: (1) Model 1: All arms yield rewards no matter activated or not; and (2) Model 2: Only activated arms yield rewards. Both models have been widely used and risen in different applications. For example, Model is widely adopted for queueing problems [J6 17 28 32V, where all queues incur hold costs, along with others 15
15
25 39/. Model 2 is widely adopted for cognitive radios f 20 21 F55, where rewards
are generated only on the state of selected channels, along with many other learning augmented
RMAB setfings 2 59 60 62 655. These two models are similar without fundamental differences as discussed in (2), and they are exactly the same under the assumption that r ( 0) = 0, Vs E S. Our proposed solutions in this paper hold for both models.
Let II be the set of all possible policies for the considered R2MAB problem and n is feasible policy in II. satisfying π E II: Fe + A where F; is the sigma-algebra (58) generated by random variables {s,, an (h): Yn N, h < t). The objective of the decision maker is to maximize the expected long-term average reward of activating arms subject to the activation budget constraint, i.e.,
( rm (t)dtt
R2MAB: max
lim inf E, T-400 TE
subject to
an (t) Vt (1)
EET
When the underlying MDP (i.e., transition kernel and reward function) of each arm is known, the R2MAB problem ① in theory can be solved using relative value iteration (55] 12 Unfortunately, this approach suffers from the curse of dimensionality 110 12], and lacks of insights for the solution structure. When the underlying MDPs are not known, off-the-shelf RL. algorithms are either computa- tionally expensive or without an Ō( regret guarantee. In the remainder of the paper, we first build a low-complexity index based policy for ( with optimality guarantee when the MDPs are known in Section 3 and then design index- RL algorithms for ① that not only are computationally efficient but also achieve an (VVT) regret when the MDPs are unknown in Section
3 An Insex- Policy and Asymptotic Optimality
Rather than solving exactly, we instead construct an index based policy for the original R2MAB that we prove to be asymptotically optimal. To describe our index policy design in Section 3.] we first need to introduce the following linear programming (LP), in which the decision variables are the
3

---

occupancy measures
[
of the controlled MDP processes:
LP (P: Tri vn):
max S2
Σ
wn(s, ()
(2)
n=l
(s,a)ESXA
N
subject to
Σ
awn
awn(s, (8, S S,
(3)
(s.a)E8XA
Σ
wn (8, a)
=E wnl d') VnEN,
(4)
un(s. 1 (n( 20, V (5)
(s,0)ESxA
One can arrive at the LP the activation cost at time is limited by on average, with their expected values via introducing set of variables w,, (s, a), which are called occupancy measures B of the controlled MDP corresponding to arm n. Specifically, the occupancy measure 2g stationary policy π for the N controlled infinite-horizon MDPs is defined as the expected average number of visits state-action pair (s, a). i.e.,
by replacing all random variables in the relaxed version of in which
0x (n lim T BAT
((s an)))) - at) [((()())ss,,,((00)))))) a)dt a()tt
:n n N, S
It can be easily checked that the occupancy measure satisfies E(,.)) (s. = 1, and hence Wn, Vn W is probability measure. To this end, 4 represents the fluid transition of the occupaney measure, which holds due to the ergodic theorem [9 for finite MDPs [6]; and 55 follows the fact is non-empty. 2 as Ωg = (w in E N S,a E A}, and
that the occupancy measure is probability measure. Thus the feasible set of LP
We denote the optimal solution to the LP
the corresponding optimal value as V -n=1 Σ (s,a) (s)
which serves as an upper
bound on the reward of the original R2MAB
UI
Lemma 1.
The optimal value achieved by the L. is an upper bound of that of the R2MAB
3.1 An Index Based Policy
does not always provide a feasible decision to the original R2MAB (T. This is because the activation budget constraint in ① must be met all time, instead of just in the average sense as in (3). Exacerbating this problem is the fact that the average constraint may be violated severely during the decision epochs, resulting in poor policy performance. We overcome these challenges by introducing a computationally appealing index policy that we prove to be asymptotically optimal. Specifically, our index policy is derived from the optimal solutions Ωz = (w, }}} and the index assigned to arm n in state st)(t) = s at time f is defined as
Unfortunately, the solution to the LP
In In( = E w (s,
aEA Edes
where En (8, a)
in state sn (t) Ewee w1 (s,a") represents the probability of applying action a, (1) arm
(s.a)
at time [ when En'e (s, > 0, and otherwise arm can be simply made passive. Hence, the index of arm n in (6) represents the expected obtained reward of activating arm in state To this end, we rank all arms based on their indices (6) in non-increasing order, and activate the set of highest indexed arms, denoted as .(()) C. N. such that the corresponding activation cost of arms in M is within the activation budget B, i..., Enevicay a (s,(tt) - B. Here a (s,,,(t (t)) is the action for arm n, which is determined according the probability (n, a) based on its current state s, (t)
at time t. When multiple arms share the same indices, we randomly activate one arm and allocate the remaining activation costs across possible actions according to the probability (s, a). All remaining arms are kept passive in case they have zero indices. We call our index based policy, ERC, since it ranks arms by Expected Reward and pull arms constrained by activation Cost. We denote the resultant index based policy as TT" { n N..

---

Remark 2. Unlike Whittle-base based index policies 66 28 72 39 57V. our ERC does not require the indexability condition, which is often hard establish especially when the transition kernel of the underlying MDP is convoluted [57y. Like Whittle policies, our ERC is computationally efficient since merely based on solving a L.P. We remark that (61) also considered average- R2MAB, however, only one action can be chosen deterministically for each state with no difference in activation cost. Hence it cannot be generalized to ours since we consider a randomized policy for each state with heterogeneous activation costs across different actions. Finally, another line of works 134 65 66 69 [00 designed index policies without indexability requirement for finite-hrrizon restless bandits, and hence cannot be directly applied to our infinite -hoiite-oorioon average-reward R2MAB.
3.2 Asymptotic Optimality
We now show that ERC is asymptotically optimal in the same asymptotic regime as that in Whittle
[64] and many others 63 61 72.. where all N arms are generalized to N classes, and both the number of class-n arms and the activation budget B are scaled by p. with their ratio holding constant. Denote X,(T", 8, a; t) as the number of class-n arms at state s taking action a at time under ERC x². We will be interested in this fluid-scaling process with parameter p. and define the expected long-term average reward as Vp. := lim inf + En- (L= E E(s.a) Fa(s, a) Xg1=" .s.a:t) dt).
Our ERC x¹ is asymptotically optimal only when V 2 VP. Vx E II. Before presenting our main result in this section, we first state the following technical condition called "global attractor" 63
Definition 1. An equilibrium point / under ERC n'' is a global attractor for the process ( p) if. for any initial point {²(x=; /)pp. the process XP(x"; t)/p converges to XPt//p. 0)/
Remark 3. The global attractor indicates that all trajectories converge to XP*, Though it may be difficult to establish analytically that a fixed point is a global attractor for the process [6TV, such assumption has been made in 163 31 61 72 24 and is only verified numerically. Our experimental results in Appendix E show that such convergence indeed occurs for our ERC
Theorem 1. Our ERCT is asymptotically optimal under Definition where क ptt represents the optimal policy for the original R2MAB
i.e., limp-roo Vi. -VP
V...p = 0,
4 Index-aware Reinforcement Learning Solutions
We now consider to learn the R2MAB when the transition kernel Pn. and reward function rn- Vn E / are unknown. Our goal is to provide low-complexity index-aware RL algorithms and determine their finite-time performance measured by the regret [43], which is defined as follows:
The regret of policy is defined as the expected gap beiween the offline optimum, i.e., the best policy under which both the transition kernels and reward functions are known, and the cumulative reward of the arm selecting algorithm, i.e., Reg(T, T) := =Tpppt - E,, [R(T, (T], where T En T' (t) is the expected average reward under policy π, and pr == sup, p(()) is the optimal average reward, which is independent of the initial state for MDPs with finite diameter (55))
Definition 2.
u(T)= == lim [IE[R(T, T"] limnT +
Remark 4. Since finding the offline optimum for R2MAB is intractable. we characterize the regret with respect to the ERC index policy. This is due the fact that our ERC index policy is asymptotically optimal. Similar definition appears in 2 655 when learning Whittle index policy for RMAB.
4.1 GM-R2MAB: Generative Model Based Index-Aware Reinforcement Learning
We first introduce a generative model based R2MAB learning algorithm called GM GM-R2MAB, which contains two phases: (i) the exploration phase (lines 1-3 in Algorithm [ and the exploita- tion phase (lines 4-6 in Algorithm D. During the exploration phase, GM-R2MAB samples each state-action pair (s, a) for J(T) times (J(T) to be specified later) for each arm n, counts the number of times (s, s') for each transition to the next state s', and constructs an empir-
ical model of transition kernel and reward function, denoted by (s(s'ss,)) a) = T=(sa=") and J(2)
(,, a) = J(T J(T) (s, a; (h) s. (h) a), a(s,a,s'), E M, respectively.
Using these empirical estimates, RMMB creates a set of plausible MDPs such that the transition
5

---

kernels and reward functions are close to the true ones, which are defined as
. = [M, A, Pn, Fn) (n)::(P(s5l a) (s'1 8, a) 6, Fn (s,a) a)= (s) Vn,
(7)
where 8 = V 2J(T) log 25T for E (0, is built using the Hoeffding inequality 49
Algorithm GM-R2MAB
Require: Time horizon T, learning function (T) < T. for 2, ..., NN do
2: Observe arm until there are J(T) visits of pairs (s,(t) = Vs)
3: end for
4: Construct the set of plausible MDPs M as in
5: Compute the corresponding ERC index policy x by solving ELP(M):
6: Execute x² to the end.
In the exploitation phase, GM-R2MAB computes the ERC index policy n' by performing optimistic planning. In other words, GM-R2MAB selects an optimistic transition kernel, an optimistic reward function, and an optimistic policy to maximize the objective function while satisfying the constraints. More specifically, it can be expressed the following optimization problem,
(P (Pri VnJ. x²) arg maXM,E.. LP LP Fn, Vn).
To solve (8. GM-R2MAR uses Extended LP (ELP) by leveraging the late-actionnstate occupancy measure 2n (s, a, s') defined as 2, (s, a, s') P... (s' (s, a)),, (s, a) to express the confidence intervals of transition probabilities. The description of ELP is provided in Appendix A Once we compute (zt, Vn), the probabilities (s, a) and hence the indices I, (s) 6 are recovered from
computed occupancy measures as (s) == Exes ", (F.,ss))((ssa))) from which we can construct our Esed (7(b,ss")
ERC index policy x², and execute x to the end.
4.1.1 Regret Analysis of GM-R2MAB
To characterize the regret, we first introduce the definition of ergodicity coefficient 2 For ease
of readability, we denote the state for all arms as stacked vector S. : [81, [81,82, 82............ sN), the corresponding actions under policy л as x (s),, and the unknown MDPs as == [0,, 02 with 0,, = (P.: r.). The transition kernel of the stacked system is then (- x (s)), E S.N Definition 3. Drg == mill,ss' Enesy min Pe (z)s, T- (s)), (z , x-" (s')) is defined as the ergodicity coefficient Pe, and D = supe Dr as the maximum value.
NN
Theorem 2. The regret of GM-R2MAB with (TT (T1/22) satisfiex:
Reg(m x (x) = -T - SAB + 1 1 D
BN
4SANT)
log
The regret comes from the explortation and exploitation phases in GM-R2MAB, respectively. Specif- ically, the first term (SSABTT) in (9) is the worst regret from explorations of each state-action pair under the generative model with (T') time steps for sampling, and the second term comes from the policy execution phase of GM-R2MAB due to MDP model mismatch. The proof of Theorem differs from the traditional analysis framework of generative based RL for restless bandits (22 35 particularly in the way to track regrets due model mismatch. We leverage the form of Bellman equations of long-term average MDPs and transfer the regret to the difference of relative value functions. This enables to track the regret relying only the first moment behavior of transition kernels. However, [62] depended on higher order moment behavior of transition kernels to track regrets. The higher moment behavior is typically hard analyze for general MDP other than the birth-and-death process considered in [62]. 655 tracked regrets by leveraging the optimistic properties of a linear system, which is only applicable to the finite-horizon setting considered in GS
We emphasize that although CM-R2MAB has a similar form the pexplore-then-comiie policy 26 a key differentiator between our GM-R2MAB and state-of-the-ar methods stems from two perspectives. First, GM-R2MAB has access to generative model and samples are taken initially to
Remark 5.

---

Algorithm 2 UC-R2MAB
Require: Initialize (3,ss a) = O, and (s'(s, = 1/5, Vn E ss, E ES,a A.
1: for k= 1, K do
2: Construct the set of plausible MDPs M as in 10
3: Compute the corresponding ERC index policy x= by solving ELP(M*):
4: Execute x ** in the current episode.
5: end for
estimate model. As result, GM-R2MAB only needs to solve ELP once to construct policy, which is computationally efficient. This is in contrast to the state-of-the-arr colored-UCRL.. (53),
which needs solve a recursive Bellman equation to derive the policy. One contribution here is to determine the right choice of J(T), which plays a key role in balancing the tradeoff between model accuracy and complexity. Second, RMMRMMAB executes our proposed provably optimal ERC index policy in the exploitation phase rather than using a heuristic one as in state of the arts 45
60 46 59)
This contributes to the polynomial prefactor in the regret, compared an exponential one in colored- UCRL2. Finally, we note that such a generative model based approach has also been used in the However, they considered either a finite-time or a discounted setting [B0), and hence cannot be directly applied to the
context of CMDPs 2
30 and restless bandits 22 651
12 651
30 focused on the sample complexity analysis, which is not directly translatable to the regret 122 Though Restless- UCB [62) operated in similar manner as our GM-R2MAB, depends on the performance of an offline "black bbxced oracle approximator in the exploitation phase, while our GM-R2MAB leverages an explicit and provably optimal ERC index policy.
average-reward setting studied in this paper. Furthermore, 2
4.2 UC-R2MAB: Online Index-Aware Reinforcement Learning
The GM-R2MAB approach operates in an "offline" manner in the sense that it first estimates a model by sampling every state-action pair in the system for a certain number of times, and then computes a policy to be executed throughout the exploitation phase. Unfortunately, such an "offline" approach may not be feasible many real-world applications since some states may not be reachable without executing the policy. To this end, we further develop an "online" approach, dubbed as UC-R2MAB, via interleaving the process of collecting samples from the environments and model updates, which is summarized in Algorithm 2 Specifically, UCCR2MAB operates in an episodic manner where each episode consists of H consecutive frames. Let K be the total number of episodes until time T, hence we have T KH. Denote the k-th episode as Hr and let тı be the time when it starts.
At the beginning of each episode, i.e., Tk Vk. UC-R2MAB estimates the true transition kernel and the - "t.a'',.."") true reward by the corresponding empirical averages P (s'ls, a) max[Ch (s,a).1j A (s)
r' (s) =s, az = a), where Ck- (s.a) the number of visits
m
to state-action pairs (s, a) until TRe and - a, s') is the number of transitions from s to s' underr action satisfying Ch a) = - + Σ#m (s (h) 8, at (h) a), and Ch a, 8') (s (1+ s = s, a (h) = a). v(s. E S A and V(s, s')
Oh- (ss, a. Ax x S, Yo, where * (h) is the state of arm n at the h-th time frame in episode k.
Similar to GM-R2MAB, UC-R2MAB creates a set of plausible MDPs using these empirical estimates for each episode in 77 by replacing J(T) with (s, a) for each arm Thus for 17 (0, 1), the set of plausible MDPs in the k-th episode is defined as
M -MM (S. ,k
)
n s..a) P (s' s,a) s (s,a), (x. (10)
where (s. V 20 (s.a) log 4SAN 11A is built using the Hoeffding incquality
Once constructing the model, U2-B2MAB computes the ERC index policy - * in episode k by solving an ELP, which is described Appendix A Specifically, it solves the following optimization problem,
(it = (Pk Vn), #ik) = arg maxM LP LP Pb 5k n
Vn),
(1I)
7

---

from which it recovers the indices (s) to construct ERC and then execute the index policy to the end of this episode. This is the same problem as in except for substituting M with M
This algorithm draws inspiration from the infinite-horizon algorithm UCRL 33 which uses the sampled trajectory of each episode to update the plausible MDPs of next episode. The major difference that distinguishes episode, and thus results in solving a low-complexity ELP, which is exponentially better than that of UCRL-based algorithm
UC-R2MAB is that UC-R2MAB deploys the proposed ERC at each
35 that needs to solve extended value iterations.
4.2.1 Regret Analysis of UC-R2MAB
Theorem 3. The regret of UC- R2-B2MAB satisfies:
Reg((T ()).T) = - (VT
2v2B 2 +
4SANT 7
log
(12)
1- D
Though the design of UC-R2MAB is inspired by UCRL type algorithms,, the regret analysis of UC-R2MAB differs from colored-UCRL2 [53] state-of-the-art method for online restless bandits. The major difference comes from the fact that UC- R2-B2MAB leverages the relative value function of Bell- man equation for long-term average MDPs to track regrets caused by model mismatch GM- RM-R2MAB. There are also recent Thompson sampling based results [2] on characterizing Bayesian regret for RMAB while using techniques reminiscent of R2MAB. The sub-linear regret in 2 was achieved by upper bounding the number of episodes to be VT under specific requirement for the length of each episode. In contrast, UC- U2-BRMAB directly bounds the sum of regret from each episode without such a episode length constraint.
Remark 6. Similar to the Wate-of-the-ar colored-UCRL2 5K and Thompson sampling based our UC-R2MAB also operates in episodic manner and achieves an (VVT) colored-UCRI.2 is known be computationally expensive and the regret is exponential in the number of arms and states. Likewise, Thompson sampling based methods provide theoretical guarantees in the Bayesian settings and need to implement computationally expensive method to update the posterior belief's due to the complex likelihood functions. In contrast, our UC-R2MAB is computationally appealing since it only needs to solve an ELP in each episode, from which UC- R2MBB constructs and implements our proposed ERC index policy. The regret of UC-R2MAB is polynomial in the number of arms and states, which is exponentially better than that of
algorithms 337 38 2
regret. However,
Finally, remark that the multiplicative "preefactorr that goes with the time dependent function in the regret of UC-R2MAB is smaller than that of GM-R2MAB. This due to the fact that U2-B2MAB operates in episodic manner while GM-R2MAB only samples once initially. This leads to a higher computation complexity of UC-R2MAB, which is ONN (ASA)) compared to that of GM-R2MAB, which is ((NS)).
5 Experiments
In this section, we present some of our experimental results. We also demonstrate the utility of our GM-R2MAB and UC-R2MAB by evaluating them under two real-world applications of restless bandits.
5.1 Experiments on Constructed Instance
Instance construction. We consider a setup with 10 classes of arms. The state space is E {0, 2, 6, 7,8, 10). Class-n arm arrives with rate 3n for 1.... 10. and departs with a fixed rate of 20. Since Whittle index policy is only designed for RMAB with two actions, we evaluate our algorithms under two settings: (1) two-action setting; and (2) multi-action setting, For two-action setting, we consider a controlled Markov process in which states evolve as specific birth-death process, i.e., state only transit to s
1 with probability P(s, + 1) 2/(A++ and P(s, s - 1) p/(A + μ1). For active action, class-n arm generates random reward r,, (s) ~ (er(sp.), with P.. uniformly sampled from [0.01, 0.1]. The activation budget set to 0.3.N, where we vary the number of arms N from 50 to 350. For the multi-action setting, we consider a total of 3,5, 10 actions, and the state of arm n transition to any state in S with randomized non-zero transition probability. We only present results with 10 actions and provide other results in Appendix
B

---

5000
1000
2012
42
009
Figure 1: Optimality gap for two actions.
Figure 2: Optimality gap for 10 actions.
Figure 3: Regret for
Figure 4: Regret for 10 actions.
two actions.
Baselines. We compare our ERC index policy with Whittle index policy (Whittle)
64 a priority
policy (Priority) 61 and a lagrangian based policy (Lagrangian) 400 We compare our RL solutions
GM-R2MAB and UC-R2MAB with a Q-learning based policy (MAIQL) 39
Thompson sampling
policy (TS)
33 Restless-UCB [62] and set of learning Whittle index based policy including and NeurWin 150. Note that we do not include results of colored-UCRL2 in our
Fu 225
AB
g
comparions since it is known to suffer from a high computational complexity and is outperformed by existing policies, e-g.. Restless-UCB 62. For ease of readability, we only present results of two "online" baselines for comparisons. More experimental results and the parameter settings for baselines are provided in Appendix
Asymptotic optimality. We compare the rewards obtained by an index policy with that from the theoretical upper bound obtained by solving the LP 2 We call the ratio between this award difference and the number of arms as the optimality gap. From Figures | and 2 policies are asymptotically optimal, which is consistent with their theoretical performance guarantees. Our ERC slightly outperforms these baselines in terms of the vanishing speed of optimality gap.
we observe that all
Regret and running time. The accumulated regrets presented in Figures and 4 where the Monte Carlo simulation with 1, 000 independent trials of a single-threaded program on AMD Ryzen 5800x desktop with 64GB RAM. For simplicity, we choose 200 arms and time horizon of T = 60, 000 slots. Each episode consists of 2, 500 slots. We observe that UC-R2MAB achieves the lowest cumulative regret and is better than "offline" method GM-R2MAB. This is consistent with our theoretical analysis (see Remark ( A key observation is that for a large horizon T, our "offline" GM-R2MAB even outperforms the "online" MAIQL. This is because GM-R2MAB leverages our proposed provably optimal ERC index policy in the exploitation phase. We also compare the average running time of these algorithms. For two-action (10-action) setting, the average running time of GM-R2MBB. UC-R2MAB, MAIQL and TS is 86s (144s), 308s (607s), 348s (702s) and 359s (681s), respectively. It clear that our GM-R2MAB and UC-R2MAB are more efficient running time. These improvements come from the intrinsic design of our algorithms that merely need to solve an ELP, while TS needs to solve Bellman equations.
5.2 Experiments on Real-World Datasets
We demonstrate the utility of R2MR and UC-R2MAR by evaluating them under two recently studied applications of restless bandits: wireless scheduling with two actions, and tuberculosis care with multiple actions. Due space constraints, relegate the detailed descriptions of these two problems to Appendix E
Wireless scheduling over fading channels [1] A wireless client is modeled an arm, which has some data to transmit. Each arm suffers from I unit holding cost in each time slot until the data is transmitted. The quality of wireless channel, either good or bad, via which data is transmitted determines the amount of transmitted data and varies over time. The goal is to maximize the negative of total holding cost. We adopt the settings in [ where I out of 10 arms is activated at any moment in time. The regret shown in Figure S It is observed that UC-R2MAB outperforms all baselines. Importantly, UC-R2MAB has sub-linear regret guarantee while the best-performing bascline MAIQL lacks finite-tima analysis. Since the environment is dynamically changing over time, it may be hard to build perfect simulator and hence UC-R2MAB is preferable than the offline GM-R2MAB.
Tuberculosis care in India their adherence over a course of 6 months. Each action has varying cost and effectiveness: cheap (call patients), semi-expensive (visit patients) and very expensive (escalate patients). The goal to maximize patients' adherence subject to daily time budget due to the limited worker time
health worker takes three actions on 200 patients to improve

---

x x10
2.5
Accumulater Regret
Accumulated regret
20
1.5
GM-R2MAB
UC- AC-R2MAB
10
MAIQL
UC-R2MAB
MAIQL
0.5
TS
09
00
2000
4000
6000
8000
10000
200
400
600
800
1000
Time
Time
Figure 5: Wireless scheduling.
Figure 6: Tuberculosis care in India
and resources. We adopt the settings in 40 adherence level/3. From Figure C outperforms all baselines.
with the budget being 20 and the reward defined as we again observe that UC-R2MAB achieves a sub-linear regret and
6 Conclusion
In this paper, we developed two low-complexity index-aware RL algorithms, GM-R2MAB and UC-R2MAB for online infinite-horizon average-reward restless multi-action bandits. We proved that both algorithms achieved a sub-linear regret that is only polynomial in the number of arms and states. Our key design reduce both the computational complexity and exponential factor in regret analysis is via exploiting the inherent structure encoded in restless bandits and leveraging our proposed provably optimal index policies for decision-mmaiinee
Acknowledgements
This work was supported in part by the National Science Foundation (NSF) grants CRII-CNS-NeTSS 2104880 and KINGS-2148301 and was supported in part by funds from OUSD R&E, NIST, and industry partners specified in the Resilient & Intelligent NextG Systems (RINGS) program, as well as the U.S. Department Energy (DOE) grant DE-EE0009341. Any opinions, findings, and conclusions recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding agencies.
References
[1] Samuli Aalto, Pasi Lassila, and Prajwal Osti. Whittle index approach to size-aware scheduling
with time-varying channels. In Proceedings of the 2015 ACM SIGMETRICS International Conference Measarement and Modeling of Computer Systems, pages 57-69, 2015.
[2] Nima Akbarzadeh and Aditya Mahajan. On learning whittle index policy for restless bandits with scalable regret. arXiv preprint arXiv:2202.03-463 2022.
[3] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[4] Aristotle Arapostathis, Vivek S Borkar, Emmanuel Fernández-GGuucherand Mrinal K Ghosh, and Steven Mareus. Discrete-time controlled markov processes with average cost criterion: survey. SIAM Journal on Control and Optimization, 31(2):282-344 1993.
[5] Thomas W Archibald, DP Black, and Kevin D Glazebrook. Indexability and index heuristics for simple class of inventory routing problems. Operations research, 57(2):314 3266 2009.
[6] Avrachenkov, VS Borkar, and S Pattathil. Controlling g-aimd using index policy. In The 56th IEEE Conference Decision and Control, Melbourne, December, pages 12-15, 2017.
10

---

[7] Konstantin Avrachenkov, Urtzi Ayesta, Josu Doncel, and Peter Jacko. Congestion control of tep flows in internet routers by means of index policy. Computer Networks, 57(17):343333778 2013.
[8] Konstantin E Avrachenkov and Vivek S Borkar. Whittle index based q-learning for restless bandits with average reward. Automatica, 139:110186, 2022.
(9] Saeed Bagheri and Anna Scaglione. The restless multi-armed bandit formulation of the cognitive compressive sensing problem. IEEE Transactions on Signal Processing, 63(5):1 183 198, 2015.
[10] Richard Bellman. Dynamic Programming. Princeton University Press, USA, 2010.
[11] Bernard Bercu, Bernard Delyon, and Emmanuel Rio. Concentration inequalities for sums and martingales. Springer, 2015.
[12] Dimitri P Bertsekas. Dynamic Programming and Optimal Control, volume 1. Athena Scientific Belmont, MA, 1995.
[13] Dimitris Bertsimas and José Niñoo-Mra. Restless Bandits, Linear Programming Relaxations, and A Primal-Dual Index Heuristic. Operations Research, 48(1): 1800099,, 2000.
[14] Biswarup Bhattacharya. Restless bandits visiting villages: A preliminary study on distributing public health services. In Proceedings of the ACM SIGCAS Conference on Computing and Sustainable Societies, pages 1-8, 2018.
[15] Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, and Milind Tambe. Learn to intervene: An adaptive learning policy for restless bandits in application preventive healthcare. In Proc. of IJCAI, 2021.
[16] Vivek S Borkar and Sarath Pattathil. Whittle indexability in egalitarian processor sharing systems. Annals of Operations Research, pages 1-21, 2017.
[17] Vivek Borkar, K Ravikumar, and Krishnakant Saboo. An index policy for dynamic pricing in cloud computing under price commitments. Applicationes Mathematicae, 44:215-245, 2017.
[18] C Richard Cassady and Erhan Kutanoglu. Integrating preventive maintenance planning and production scheduling for single machine. IEÉE Transactions on reliability, 54(2):304-309 2005.
[19] Erhan Cinlar. Introduction to stochastic processes prentice-hall. Englewood Cliffs, New Jersey (420p), 1975.
[20] Kobi Cohen, Qing Zhao, and Anna Scaglione. Restless multi-armed bandits under varying activation constraints for dynamic spectrum access. In 2014 48th Asilomar Conference on Signals, Systems and Computers, pages 1575-1578. IEEE, 2014.
[21] Wenhan Dai. Yi Gai, Bhaskar Krishnamachari, and Qing Zhao. The Non- Non-Bayesian Restless Multi-Armed Bandit: A Case of LogrrILog Regret. In Proc. of IEFE ICASSP, 2011.
[22] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
[23] Sarang Deo, Seyed Iravani, Tingting Jiang, Karen Smilowitz, and Stephen Samuelson. Improv- ing Health Outcomes Through Better Capacity Allocation in Community- Chronic Care Model. Operations Research, 61 1277-1427,2 2013.
[24] Santiago Duran and Ina Maria Verloop. Asymptotic optimal control of markov-modulated restless bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(1):1-25, 2018.
[25] Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian New Zealand Control Conference (ANZCC), pages 249-254. IEEE, 2019.
11

---

[26] Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-comme strategies. Advances Neural Information Processing Systems, 29, 2016.
[27] Nicolas Gast and Gaujal Bruno. A mean field model of work stealing in large-scale systems. ACM SIGMETRICS Performance Evaluation Review, 38(1):13-2, 2010.
[28] Kevin D Glazebrook, David Hodge, and Chris Kirkbride. General notions of indexability for queueing control and asset management. The Annals of Applied Probability, 21(3):876-907, 2011.
[29] Aria HasanzadeZonuzz, Dileep Kalathil, and Srinivas Shakkottai. Learning with Safety Con- straints: Sample Complexity of Reinforcement Learning for Constrained MDPs. In Proc. of AAAI, 2021.
[30] Aria HasanzadeZonuzz, Dileep Kalathil, and Srinivas Shakkottai. Model-based reinforcement learning for infinite-horizon discounted constrained markov decision processes. In Proc, of IJCAI, 2021.
[31] David J Hodge and Kevin D Glazebrook. On the asymptotic optimality of greedy index heuristies for multi-action restless bandits. Advances in Applied Probability, 47(3):652--6) 667, 2015.
[32] DJ Hodge and Kevin D Glazebrook. Dynamic Resource Allocation In A Multi-Product Make- to Sooctock Production System. Queueing Systems, 67(4))333-33) 2011.
[33] Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. In The Collected Works of Wassily Hoeffding, pages 409-426. Springer, 1994.
[34] Weici Hu and Peter Frazier. An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits. arXiv preprint arXiv:1707.0026. 2017.
[35] Peter Jacko. Restless Bandits Approach to the Job Scheduling Problem and Its Extensions. Modern trends in controlled stochastic processes: theory and applications, pages 248-267, 2010.
[36] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-Optimal Regret Bounds for Reinforcement Learning. Journal of Machine Learning Research, 11(4), 2010.
[37] Young Hun Jung, Mare Abeille, and Ambuj Tewari. Thompson Sampling in Non-Episodic Restless Bandits. arXiv preprint
2019.
[38] Young Hun Jung and Ambuj Tewari. Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems. Proc. of NeurlPS, 2019.
[39] Jackson A Killian, Arpita Biswas, Sanket Shah, and Milind Tambe. Q-learning lagrange policies for multi-action restless bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 871-881, 2021.
[40] Jackson Killian, Andrew Perrault, and Milind Tambe. Beyond" To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits. In Proc. AAMAS, 2021.
[41] Maialen Larrañaga, Urtzi Ayesta, and Ina Maria Verloop. Index Policies for A Multi-Class Queue with Convex Holding Cost and Abandonments, In Proc. of ACM Sigmetrics, 2014.
[42] Maialen Larrnaaga, Urtzi Ayesta, and Ina Maria Verloop. Dynamic Control of Birth-and- Restless Bandits: Application to Resource-Allocation Problems. IEEE/ACM Transactions on Networking, 24 2016.
[43] Tor Lattimore and Csaba Szepesvári. Bandit Algorithmss. Cambridge University Press, 2020.
[44] Elliot Lee, Mariel S Lavieri, and Michael Volk. Optimal Screening for Hepatocellular Carci- noma: Restless Bandit Model. Manufacturing & Service Operations Management, 21(1):198- 212, 2019.
12

---

[45] Haoyang Liu, Keqin Liu, and Qing Zhao. Logarithmic Weak Regret of Non- Non-Bayesian Restless Bandit. In Proc of IEEE ICASSP, 2011.
[46] Haoyang Liu, Keqin Liu, and Qing Zhao. Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics. IEEE Transactions on Information Theory, 19(3):900--116,, 2012.
[47] Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application to public health intervention. Advances in Neural Information Processing Systems, 33:1 33:15639-15650, 2020.
[48] Aditya Mate, Andrew Perrault, and Milind Tambe. Risk-Aware Interventions in Public Health: Planning with Restless Multi-Armed Bandits. In Proc. AAMAS, 2021.
[49] Andreas Maurer and Massimiliano Pontil, Empirical Bernstein Bounds and Sample Variance Penalization. arXiv preprint arXiv:0907.3740, 2009.
[50] Khaled Nakhleh, Santosh Ganji, Ping-Chun Hsieh, I Hou, Srinivas Shakkottai, et al. Neurwin: Neural whittle index network for restless bandits via deep rl. Advances in Neural Information Processing Systems, 34, 2021.
[51] José Nirao-Mora. Dynamic Priority Allocation via Restless Bandit Marginal Productivity Indices. Top, 15(2):161-198, 2007.
[52] José Noño-Mora. Admission and routing of soft real-time jobs to multiclusters: Design and comparison of index policies. Computers & operations research, 39(12)33431 2012.
[53] Ronald Ortner, Daniil Ryabko, Peter Auer. and Rémi Munos. Regret Bounds for Restless Markov Bandits. In Proc. of Algorithmic Learning Theory, 2012.
[54] Christos H Papadimitriou and John N Tsitsiklis. The Complexity of Optimal Queueing Network Control. In Proc. of IEEE Conference on Structure in Complexity Theory, 1994.
[55] Martin L Puterman. Markov Decision Processes: John Wiley & Sons, 1994.
Discrete Stochastic Dynamic Programming.
[56] Francisco Robledo, Vivek Borkar, Urtzi Ayesta, and Konstantin Avrachenkov. QWI: Q-Learnin with Whittle Index. ACM SIGMETRICS Performance Evaluation Review, 49(2):47-50, 2022.
[57] Shang-Pin Sheng, Mingyan Liu, and Romesh Saigal. Data-Driven Channel Modeling Using Spectrum Measurement. IEEE Transactions on Mobile Computing, 1499)11794-1855, 2014.
[58] Albert N Shiryaev. Optimal Stopping Rules, volume 8. Springer Science & Business Media, 2007.
[59] Cem Tekin and Mingyan Liu. Adaptive Learning of Uncontrolled Restless Bandits with Logarithmic Regret. In Proc. of Allerton, 2011.
[60] Cem Tekin and Mingyan Liu. Online Learning of Rested and Restless Bandits. IEEE Transac- tions on Information Theory, 58(8):5588-561.. 2012.
[61] Ina Maria Verloop. Asymptotically Optimal Priority Policies for Indexable and Nonindexable Restless Bandits. The Annals of Applied Probability, 2674) 2016.
[62] Siwei Wang, Longbo Huang, and John Lui. Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits. In Proc. of NeurlPS, 2020.
[63] Richard R Weber and Gideon Weiss. On An Index Policy for Restless Bandits. Journal of applied probability, pages 637-648, 1990.
[64] Peter Whittle. Restless Bandits: Activity Allocation in A Changing World, Journal of applied probability, pages 287-298, 1988.
[65] Guojun Xiong, Jian Li, and Rahul Singh. Reinforcement Learning Augmented Asymptotically Optimal Index Policy for finite-Horizon Restless Bandits. In Proc. of AAAI, 2022.
13

---

[66] Guojun Xiong, Xudong Qin, Bin Li, Rahul Singh, and Jian Li. Index-aware Reinforcement Learning for Adaptive Video Streaming at the Wireless Edge. In Proc. of ACM MobiHoc, 2022.
[67] Guojun Xiong, Shufan Wang, Gang Yan, and Jian Li. Reinforcement Learning for Dynamic Dimensioning of Cloud Caches: A Restless Bandit Approach. In Proc. of IEEE INFOCOM,
2022.
[68] Zhe Yu, Yunjian Xu, and Lang Tong. Deadline Scheduling as Restless Bandits. IEEE Transac- tions on Automatic Control, 63(8):23432235 2358, 2018
[69] Gabriel Zayas-Cahán, Stefanus Jasin, and Guihua Wang. An Asymptotically Optimal Heuris- tie for General Nonstationary Finite-Horizon Restless Multi-Armed, Multi-Action Bandits. Advances in Applied Probability, (1 5163)7755-772, 2019.
[70] Xiangyu Zhang and Peter Frazier. Restless bandits with many arms: Beating the central limit theorem. arXiv preprint arXiv:2107.11911, 2021.
[71] Qing Zhao, Bhaskar Krishnamachari, and Keqin Liu. On myopic sensing for multi-channe opportunistic access: structure, optimality, and performance. IEEE Transactions on Wireless Communications, 7(12):543155400, 2008.
[72] Yihan Zou, Kwang Taik Kim, Xiaojun Lin, and Mung Chiang. Minimizing Age-of-Information Heterogeneous Multi-Channel Systems: A New Partial-Index Approach. In Proc. of ACM Mobilloc 2021.
Ethics Statement and Societal Impacts
Our research shows how our proposed two low-complexity index-aware RL algorithms, GM-R2MAB and UC-R2MAB perform in the setting of online infinite-horize average-reward restless multi-action multi-armed bandits. Our main contributions part. The evaluation of our algorithms are conducted through a combination of mathematical analysis (e.g.. finite-time analysis) and simulations. For sake of exposition and reproducibility, we leveraged a public dataset of the TB care in India [40]. which are interpreted and leveraged without specialist medical-care domain knowledge, and without private human information (patients are divided into four types with ratio, and other parameters are synthetic). However, the proposed methods are potentially relevant to any scientific application that can be formulated as R2MAB framework. As for societal impact of our work, we highlight the need for specific information about involved individuals, or network metadata, which may lead to privacy issues and we hope to raise awareness of these potential issues of privacy.
primarily analytic in nature, i.e., mainly in the theory
One limitation of the method may come from the above discussions regarding the technical assumption of "global attractor" to prove the asymptotic optimality of ERC index policy. Though this is a standard assumption and widely used in the literature, it is hard to be established analytically. possible direction or an open problem is to establish a sufficient condition to rigorously establish the global attractor property.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(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]
14

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "s1ptbfK0Jig", "reviewer": "Reviewer_4AZS", "summary": "The authors address infinite horizon average reward restless multi-action bandits. They propose a new type of index, and two algorithms that calculate this index when the transitions and rewards are unknown - one offline and one online. The authors provide regret bounds for their algorithms and compare them empirically to other methods.", "questions": "The paper is very clear and I have no questions or suggestions.", "limitations": "Not relevant for this paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\nThe paper is novel to the best of my knowledge. The authors emphasize that their regret bounds are highly novel, I have no knowledge to contradict that fact.\n\nQuality\nThe paper is of very high quality - the presentation of the problem is clear and well written, the regret bounds are impressive and strong,  and the experiments form a convincing argument. \n\nClarity\nDespite the results being mostly theoretical, I found the paper to be very clear and very well written. \n\nSignificance\nRestless multi-action bandits is a a bit of a niche so the significance of the paper is somewhat limited. The proposed algorithms and simulations correspond to discrete MDPs whose model is learned, which further hampers the significance of the work for applications. Inside this niche, the results do seem convincing, interesting and filling in missing knowledge.\n\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": "QsKfAKUhsap", "reviewer": "Reviewer_mAyS", "summary": "The paper considers the online RMAB problem, with multiple available actions and when the MDP on each arm is unknown. The paper derives an index policy for the online RMAB problem, different from the WHittle index policy and then proposes two index-aware RL algorithms. The paper shows that both algorithms achieve sublinear regret.", "questions": "- Line 114 says w.l.o.g r(s,0)=0. However, how is this general given that r() could potentially depend on s, i.e. r(s,0) =s? \n- Lines (70-74) say that the paper takes a more general approach, hence is more efficient. However, this seems a bit counterintuitive; shouldn’t there be a trade-off? Is there something else that is being given up?\n", "limitations": "Yes ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n\n\n\n- The approach seems principled and theoretically solid. The paper proves that their proposed index based approach is asymptotically optimal. \n - Empirical analysis: The experiments seem to be comprehensive; they cover a wider range of settings and test against most of the relevant baselines, including fairly recent baselines. \n- The context is well set up: explaining where the sota is and what gap needs to be filled.\n\n**Weaknesses**\n\n- The writing/exposition is not clear at some places: For instance, the abstract says each arm evolves according to a Markov chain. However, later in section 2, each arm is said to evolve according to an MDP. \n\n- Minor issues: grammatical issues/typos involving usage of plural/singular quantity at few places\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "JWbjjLO-z3C", "reviewer": "Reviewer_2MaK", "summary": "Authors provide two learning algorithms for the multi-action restless bandit problem (R2MAB), with new regret bounds that advance state of the art. Their algorithm and bounds rely on a new index policy which is asymptotically optimal under a global attractor condition. Authors provide numerical experiments on three domains that support their claims.", "questions": " - Please respond to the weaknesses above.\n\n\nNote: the paper potentially has enough merit to be considered for acceptance in my view, but the points listed in \"weaknesses\" need to be clarified.\n\n-------\nI have read the other reviews and author responses and am satisfied with their answers to my questions, and have increased my score. Authors should add more clarifying language about the global attractor property's reliance on data distributions as is done in Verloop 2016 section 6.", "limitations": " - Please see weaknesses, second comment", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - The draft is mostly well-written, making the contributions clear.\n - Authors provide experimental results on three domains showing wins on each (though modest compared to MAIQL on scheduling and TB)\n - The authors provide attractive regret bounds or the average reward, R2MAB case, advancing current state of the art.\n - Authors introduce a new index policy class for R2MAB, ERC, which seems to have good performance and will be of general interest to the RMAB community, though it seems to rely on a numerically verifiable global attractor condition.\n - Authors provide two learning algorithms, GM-R2MAB and UC-R2MAB, where the former is \"offline\" in that it takes time to collect enough samples to build a confident world model, and the latter is \"online\" in that it follows more closely to an upper confidence bound approach, exploring and exploiting in tandem. UC-R2MAB seems to perform better than all baselines in experiments.\n\nWeaknesses:\n - My understanding is that the global attractor property of a policy class is data dependent, and thus needs to be verified for each new dataset to which a policy class is applied. All of the authors' core results seem to depend on the global attractor condition, i.e., optimality of the ERC index policy they propose, and thus also the regret bounds (which rely on the ERC being asymptotically optimal). So, unless I am missing something, all of the results here depend on the users' ability to numerically verify the global attractor policy for the data to which they hope to apply the authors' algorithms. This may be ok, but the authors need to make it much more clear throughout the draft if this is the case. For instance, in Remark 1, authors claim that \"ERC does not require the indexability condition, which is often hard to establish especially when the transition kernel of the underlying MDP is convoluted\" -- while true, one seems to have to verify a global attractor condition instead to use the authors' policy, which is ultimately very similar since the indexability condition is a necessary condition for the global attractor property of the Whittle index policy, and itself is often verified numerically for new MDP classes. So authors should clearly state the tradeoff.\n - The authors mark N/A in their checklist for both limitations and social impacts -- this is not acceptable in the current iteration of NeurIPS. Authors need to engage in some amount of discussion in the limitation of their methodology. Also, since the authors present experimental results on a tuberculosis care domain, it is reasonable to ask that they discuss how their algorithm might have adverse social impact, and so they should engage in this part of the discussion as well.\n - More evaluation would be helpful. Specifically, authors vary the number of actions, but not the number of arms, which is they key scaling parameter in RMAB. Authors should provide some experiments to show both regret and runtime scaling as N increases for at least one domain. Additionally, the authors compare against MAIQL from Killian et al. 2021, but not LPQL, which seems to be the preferred R2MAB learning algorithm from that paper. Presumably they did not compare against LPQL because it handles the discounted reward case, rather than average. However, in the appendix, authors compare against NeurWIN which handles the discounted reward case. So authors should also compare against LQPL for completeness.\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": "Ap2gFcISm9c", "reviewer": "Reviewer_2ySi", "summary": "The paper proposes two reinforcement learning algorithms for the multi-action multi-armed restless bandits' framework: GM-R2MAB (offline learning) and UC-R2MAB (online learning). An index-based policy is advocated for to avoid the dimensionality issue with increasing arms' count. A linear program (LP) is described to find a value upper bound for the R2MAB, and to characterize the asymptotic optimality of the ERC index-based approach. When the transition kernel and reward function are unknown, regret bounds were proven for both RL algorithms, and a comparison against other RMAB learning algorithms is provided on two experiment cases. The online learning algorithm (UC-R2MAB) was shown to give the lowest empirical regret in all cases.", "questions": "\n1. Both GM-R2MAB and UC-R2MAB are able to learn index policies without the indexability condition (needed for the Whittle index). However, if the considered RMAB is indexable, how would that affect the two algorithms' regret bound? would indexability give a tighter regret bound?\n\n2. Assuming the RMAB is indexable, is there a characterization of the two algorithms' learned indices and the Whittle index if it exists? How would the learned index relate to the Whittle index? \n\n3. In the checklist under 4.d, I couldn't locate in the main text or the appendix where consent was obtained for the used data, which should be explicitly mentioned in the revised manuscript.  ", "limitations": "**Limitations:** While the proposed approach is direct at multi-action RMABs and not the binary action case, the paper does not discuss the two algorithms' performance when the restless arms are indexable. A brief discussion of how indexability affects regret upper bounds would be interesting. \n\n**Societal impact:** The paper presents two algorithms for RMABs in the average rewards' setting, including one medical trial case in India. Hence, an application-specific analysis should be performed by those wishing to use either algorithm (especially in medical trials' cases).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\nThe paper contributes well in the finite-time analysis of R2MABs in the average reward case, and offers detailed theoretical regret analysis for both the offline (GM-R2MAB) and online (UC-R2MAB) algorithms. The introduction also explains in detail the lack of understanding of R2MABs' regret performance. The experiments include results from recent RMAB learning algorithms, and the experiment cases cover both the two-actions and multiple actions' cases. The necessary regret proofs (for theorems 2 and 3) provided in the appendices form the bulk of the paper's contribution and are well articulated.\n\n\n### Weaknesses:\n\nI find lemma 1 statement to be vague and the proof a bit general. The lemma statement depends on the value definition $V$ that is only mentioned in the appendix with the scaling parameter $\\rho$ (for theorem 1). I find having an explicit definition of the average reward value necessary before going into the proofs. For lemma 1 proof, the wording should be modified to indicate that the original problem's feasible region $\\Gamma$ is reachable for all points of the relaxed problem's region $\\Gamma^/$.\n\nIn the experiments' section, I understand that the page limit prevents a longer description of the results. In the revised manuscript, the author(s) should dedicate more explanation as to why the two algorithms perform better than the baselines. Currently the discussion rightly mentions that the two algorithms solve an ELP, but it would help if the author(s) discuss UC-R2MAB and GM-R2MAB limitations compared to the baselines. In addition, it would be nice to aggregate all algorithms' results into one plot rather than splitting them between two plots (one in the main text and the other in the appendix). I currently need to look at two graphs that consider a single case study to understand how the two algorithms perform.\n\nWhile the paper's technical analysis and sections are well-written, the paper's organization\\spelling accuracy can be significantly improved as I highlight below:\n\nStarting in line 19 and throughout the paper: *Restless multi-armed bandits (RMAB)...*\nshould be RMABs throughout the paper when the plural bandits is used.\n\nLine 29 *\"This is restrictive since the decision maker in many applications often has access to multiple actions for each arm.\"*\nThe author(s) should provide examples or cite work for this claim in the introduction.\n\nLine 31 *\"which we call the restless multi-action bandits, dubbed as R2MAB\"*\nthe full name would be better here: multi-action multi-armed bandits. \n\nLine 46 *Second, existing RL algorithms with theoretical guarantee of  a sub-linear...*\nalgorithms with **a** theoretical guarantee.\n\nLine 58 *[57] achieved low-complexity... and not easy to be directly generalized*\n**a** low-complexity policy... and **is** not easy.\n\nLine 123 *In the remaining of the paper,*\nIn the remainder of the paper.\n\nBoth remarks 3 (line 237) and 4 (line 298) can be written as normal non-italicized paragraphs for easier reading. \n\nLine 288 at the end of equation 12 (theorem 3), it should be a period and not a comma.\n\nLine 301 *and the regret is exponentially in the number of arms and states*\nand the regret is **exponential** in the number...\n\nLine 320 *as a specific birth-and-death process*\nbetter to call it **birth-death** process for consistency.\n\nLine 324 *For multi-action setting*\nFor **the** multi-action setting\n\nLine 337 *between this award difference and the number of arms as optimality gap.*\nbetween this *reward* difference and  the number of arms as **the** optimality gap.\n\nLine 351 *It is clear that our GM-R2MAB and UC-R2MAB is more efficient in running time.*\nIt is clear that our ... **are** more efficient...\n\nLine 372 *Each action has varying cost and effective*\nshould be *effectiveness*.\n\nAs a minor note, the author(s) should also cite the paper in the introduction section:\nFrancisco Robledo, Vivek Borkar, Urtzi Ayesta, and Konstantin Avrachenkov. 2022. QWI: Q-learning with Whittle Index. SIGMETRICS Perform. Eval. Rev. 49, 2 (September 2021), 47–50. https://doi.org/10.1145/3512798.3512816\n\n\n\n---------------------------------------------\n### After rebuttal:\n\nI thank the author(s) for responding to all of my comments. I read their responses and I find it to answer my concerns. In the updated paper, the author(s) should include the revised description of lemma 1 and the TB care dataset usage. \n\nI have updated the soundness score from 3 to 4 to reflect the updates the author(s) provided. I will keep my overall score at 7.\n\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: Accept