NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL
Authors: Khaled Nakhleh
Santosh Ganji
Ping-Chun Hsieh
I-Hong Hou
Srinivas Shakkottai
Venue: NeurIPS 2021 Poster (2021)
Keywords: restless bandits
Whittle index
deep reinforcement learning

Abstract: Whittle index policy is a powerful tool to obtain asymptotically optimal solutions for the notoriously intractable problem of restless bandits. However, finding the Whittle indices remains a difficult problem for many practical restless bandits with convoluted transition kernels. This paper proposes NeurWIN, a neural Whittle index network that seeks to learn the Whittle indices for any restless bandits by leveraging mathematical properties of the Whittle indices. We show that a neural network that produces the Whittle index is also one that produces the optimal control for a set of Markov decision problems. This property motivates using deep reinforcement learning for the training of NeurWIN. We demonstrate the utility of NeurWIN by evaluating its performance for three recently studied restless bandit problems.
Our experiment results show that the performance of NeurWIN is significantly better than other RL algorithms.

depends its NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL
Khaled Nakhleh', Santosh Ganji', Ping-Chun Hsieh?, I-Hong Hou', Srinivas Shakkottai
Electrical and Computer Engineering Department
Texas A&M University
College Station, TX
(khaled. .amaled.jamal,, sant1, ihou, sshakkot]@tami edu
Department of Computer Science National Chiao Tung University, Taiwan pinghsieh@ncte edu.
Abstract
Whittle index policy a powerful tool to obtain asymptotically optimal solutions for the notoriously intractable problem of restless bandits. However, finding the Whittle indices remains difficult problem for many practical restless bandits with convoluted transition kernels. This paper proposes NeurWIN, neural Whittle index network that seeks to learn the Whittle indices for any restless bandits by leveraging mathematical properties of the Whittle indices. We show that neural network that produces the Whittle index is also one that produces the optimal control for set of Markov decision problems. This property motivates using deep reinforcement learning for the training of NeurWIN. We demonstrate the utility of NeurWIN by evaluating its performance for three recently studied restless bandit problems. Our experiment results show that the performance of NeurWIN is significantly better than other RL algorithms.
Introduction
Many sequential decision problems can be modeled multi-armed bandit problems. A bandit problem models each potential decision as an arm. In each round, we play M arms out of a total of N arms by choosing the corresponding decisions. We then receive reward from the played arms. The goal is to maximize the expected long-term total discounted reward. Consider, for example, displaying advertisements on online platform with the goal to maximize the long- -tem discounted click-through rates. This can be modeled as a bandit problem where each arm a piece of visits
advertisement and choose which advertisements to be displayed every time particular the platform. should be noted that the reward, i.e., click-through rate, of an arm is not stationary, but actions in the past. For example, may be much less likely to click on the same advertisement in the near future. Such a problem is classic case of the restless bandil problem, where the reward distribution of state, which changes over time based on our past actions.
depends
that just clicked
particular advertisement
The restless bandit problem is notoriously intractable (20). Most recent efforts. such recovering bandits (21). roting bandits (23), and Brownian bandits (24). only study some special instances of the restless bandit problem. The fundamental challenge of the restless bandit problem lies in the explosion state space, as the state of the entire system the Cartesian product of the states of individual arms. powerful tool traditionally used to solve the RMABs' pacision-making problem
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is the Whittle index policy [30]. In a nutshell, the Whittle index policy calculates a Whittle index for each arm based on the arm's 's current state, where the index corresponds the amount of cost that we are willing to pay to play the arm, and then plays the arm with the highest index. When the indexability condition is satisfied, it has been shown that the Whittle index policy asymptotically optimal in a wide range of settings.
In this paper, we present Neural Whittle Index Network (NeurWIN), principled machine learning approach that finds the Whittle indices for virtually all restless bandit problems. We note that the Whittle index an artificial construct that cannot be directly measured. Finding the Whittle index is typically intractable. As result, the Whittle indices of many practical problems remain unknown except for a few special cases.
We are able to circumvent the challenges of finding the Whittle indices by leveraging an important mathematical property of the Whittle index: Consider an alternative problem where there is only one arm and we decide whether to play the arm in each time instance. In this problem, we need to pay a constant cost of À every time we play the arm. The goal is maximize the long-term discounted net reward, defined as the difference between the rewards we obtain from the arm and the costs we pay to play it. Then, the optimal policy is to play the arm whenever the Whittle index becomes larger than A. Based on this property, a neural network that produces the Whittle index can be viewed as one that finds the optimal policy for the alternative problem for any A.
Using this observation, we propose a deep reinforcement learning method to train NeurWIN. To demonstrate the power of NeurWIN, employ NeurWIN for three recently studied restless bandit problems, namely, recovering bandit [21), wireless scheduling [ and stochastic deadline scheduling
34 We compare NeurWIN against five other reinforcement learning algorithms and the application- specific baseline policies in the respective restless bandit problems. Experiment results show that the index policy using our NeurWIN significantly outperforms other reinforcement learning algorithms. Moreover, for problems where the Whittle indices are known, NeurWIN has virtually the same performance the corresponding Whittle index policy, showing that WeurWIN indeed learns precise approximation to the Whittle indices.
The rest of the paper is organized as follows: formal definitions of the Whittle index and our problem statement. Section iintroduces our training algorithm for NeurWIN. Section 5 demonstrates the utility of NeurWIN by evaluating its performance under three recently studied restless bandit problems. Finally, Section concludes the paper.
Section 2 reviews related literature. Section provides
2 Related work
Restless bandit problems were first introduced in 30). They are known be intractable, and are in general PSPACE hard (20). As a result, many studies focus on finding the Whittle index policy for restless bandit problems, such in [16] 8 [8] 26). However, these studies are only able find the Whittle indices under various specific assumptions about the bandit problems.
There have been many studies applying RL methods for bandit problems. 9 proposed tool
called Uniform-PAC for contextual bandits. 35 described a framework framework-agnostie approach towards
guaranteeing RL algorithms' performance. [13] introduced contextual decision processes (CDPs) that encompass contextual bandits for RL exploration with function approximation. [22] compared deep neural networks with Bayesian linear regression against other posterior sampling methods. However, none of these studies are applicable to restless bandits, where the state of an arm can change over time.
Deep RL algorithms have been utilized in problems that resemble restless bandit problems, including HVAC control (29), cyber-physical systems [17]. and dynamic multi-channel access (28). In all these cases, a major limitation for deep RL is scalability. As the state spaces grows exponentially with the number of arms, these studies can only be applied to small-scale systems, and their evaluations are limited to cases when there are at most 5 zones, sensors, and 8 channels, respectively.
An emerging research direction is applying machine learning algorithms to learn Whittle indices. 6 proposed employing the (.PE(()) algorithm 32 coupled with a polynomial function approximator.
The approach was applied in 3 for scheduling web crawlers. However, this work can only be applied to restless bandits whose states can represented by a single number, and only uses polynomial function approximator, which may have low representational power (25).

---

[5] studied public health setting and models it as restless bandit problem. A Q-learning based Whittle index approach was formulated to ideally pick patients for interventions based on their states. [ proposed a Q-learning based heuristic to find Whittle indices. However, shown in its experiment results, the heuristic may not produce Whittle indices even when the training converges. 4 proposed WIBQL: Q-learning method for learning the Whittle indices by applying modified tabular relative value iteration (RVI) algorithm from [2]. The experiments presented here show that WIBQL does not scale well with large state spaces.
3 Problem Setting
In this section, we provide brief overview of restless bandit problems and the Whittle index. We then formally define the problem statement.
3.1 Restless Bandit Problems
A restless bandit problem consists of N restless arms. In each round t, a control policy т observes the state of each arm i, denoted by st[t], and selects M arms to activate. We call the selected arms as active and the others as passive. We use a to denote the policy's decision on each arm i, where [s({] = 1 if the arm active and [t] stochastic reward r; [t] with distribution Ri,act (s)(t) if it is active, and with distribution Rd, Ri.pass (s; (t] it is passive. The state of each arm in the next round evolves by the transition kernel of either ar (f) or p.,pass (f), depending on whether the arm is active. The goal of the control policy is maximize the expected total discounted reward, which can be expressed E, IE E [+]]
if passive at round Each arm generates a
with ,9 being the discount factor.
A control policy is effectively function that takes the vector (s) [t], 82[1), SN [t) the input and produces the vector (a, [t], [t]t)..... aN [t]) as the output. It should be noted that the space of input is exponential in N. If each arm can be in one of K possible states, then the number of possible
inputs is KN. This feature, which is usually referred to as the curse of dimensionality, makes finding
the optimal control policy intractable.
3.2 The Whittle Index
An index policy seeks to address the curse of dimensionality through decomposition. In each round, it calculates index, denoted by (s(ss[t)) for each arm based on its current state. The index policy then selects the M arms with the highest indices to activate. It should be noted that the index of arm i is independent from the states of any other arms. In this sense, learning the Whittle index of a restless arm is an auxiliary task to finding the control policy for restless bandits.
Obviously, the performance of an index policy depends on the design of the index function Wi(+). A popular index with solid theoretical foundation the Whittle index, which defined below. Since we only consider one arm at time, we drop the subscript i for the rest of the paper.
Consider system with only one arm, and an activation policy that determines whether to activate the arm in each round t. Suppose that the activation policy needs to pay an activation cost of À every time it chooses activate the arm. The goal of the activation policy is to maximize the total expected discounted net reward, E 8 (rit] Xa[t))] The optimal activation policy can be expressed by the set of states in which would activate this arm for a particular X, and we denote this set by S()). Intuitively, the higher the cost, the less likely the optimal activation policy would activate the arm in given state, and hence the set S()) would decrease monotonically. When an arm satisfies this intuition, we say that the arm is indexable.
Definition (Indexability). An arm is said to be indexable if ((A) decreases monotonically from the set of all states to the empty set as increases from 0o sc. A restless bandit problem is said to be indexable if all arms are indexable.
Definition 2 (The Whittle Index). If an arm is indexable, then its Whittle index of each state 8 is defined as W ;= supx(t: : E S(A)).
3

---

Even when an arm is indexable, finding its Whittle index can still be intractable, especially when the transition kernel of the arm is convoluted"" NeurWIN finds the Whittle index by leveraging the following property of the Whittle index: Consider the single-armed bandit problem. Suppose the initial state of an indexable arm s at round one. Consider two possibilities: The first is that the activation policy activates the arm at round one, and then uses the optimal policy starting from round two; and the second that the activation policy does not activate the arm at round one, and then uses the optimal policy starting from round two. Let a (s) and Qx. (s) be the expected discounted net reward for these two possibilities, respectively, and let (A == (Qx (8) - Qx, (x)pass()) be their difference. Clearly, the optimal activation policy should activate an arm under state s and activation cost À if (A) 2 0. We present the property more formally in the following proposition:
Proposition 1. 136 Thm 3.14] If arm is indexable, then, for every state 8, Da(A) 2 0 if and only if S (s).
Our NeurWIN uses Prop. to train neural networks that predict the Whittle index for any indexable arms. From Def. [ sufficient condition for indexability is when (A) is a decreasing function. Thus, we define the concept of strong indexability as follows:
Definition 3 (Strong Indexability). An arm is said to be strongly indexable if D2(A) is strictly decreasing in for every state
Intuitively, as the activation cost increases, it becomes less attractive to activate the arm in any given state. Hence, one would expect (A) to be strictly decreasing in À for particular state In Section 5.5 we further use numerical results to show that all three applications we evaluate in this paper are strongly indexable.
3.3 Problem Statement
We now formally describe the objective of this paper. We assume that given a simulator of one single restless arm as a black box. The simulator provides two functionalities: First, it allows us to set the initial state of the to any arbitrary state s. Second, in each round the simulator takes alt), the indicator function that the arm is activated, as the input and produces the next state s(t + 1] and the reward r[t] as the outputs.
Our goal is to derive low-complexity index algorithms for restless bandit problems by training a neural network that approximates the Whittle index of each restless arm using its simulator. A neural network takes the state s as the input and produces a real number fo as the output, where 6 is the vector containing all weights and biases of the neural network. Recall that W W(s) is the Whittle index of the arm. We aim to find appropriate that makes (f((s) - W(s) small for all s. Such a neural network is said to be Whinle-accurate.
Definition 4 (Whitte-acccurae)) A neural network with parameters 0 is said to be 7 Whittee-ucccuree ff(o(>)) - (s)) S for all s.
4 NeurWIN Algorithm: Neural Whittle Index Network
In this section, we present NeurWIN, deep-RL algorithm that trains neural networks to predict the Whittle indices. Since the Whittle index of an arm is independent from other arms, NeurWIN trains one neural network for each arm independently. In this section, we discuss how NeurWIN learns the Whittle index for one single arm.
4.1 Conditions for Whittl-Accuurate
Before presenting NeurWIN, we discuss the conditions for a neural network to be >-Whitle-accuraae.
Suppose we are given a simulator of an arm and a neural network with parameters 0. We can then construct an environment of the arm along with an activation cost À as shown in Fig. In each round t, the environment takes the real number {e(s(t) (t]) as the input.
19 described generic approach for finding the Whittle index. The complexity of this approach is at least exponential to the number of states.

---

The imput is first fed into a step function to produce alt] = (ft(t )), where 1(-) is the indicator function. Then, a(t) is fed into the simulator of the arm to produce r[t] and s[t + 1]. Finally, the environment outputs the net reward r(t] Xa[t] and the next state s(t 1]. We call this environment (nw(A). Thus, the neural network can be
Arm with activation cost À
NeurWIN,
20[1]
frdd
Arm
at
((b(tt) 2 2)
s|++ 1]
viewed as controller for Enw(A), (). The following corollary is direct result from
Figure I: An illustrative motivation of NeurWIN.
Prop. T
Corollary 1. If the arm is indexable and fø(s) (s), vs. then the neural network with parameters 0 is the optimal controller for En for any À and initial state s s(0]. Moreover, given X and s s(O), the optimal discounted net reward is max max[Qx,act (s(0), Qxpass (s(0))
Corollary can be viewed as necessary condition for a neural network to be O-Whitlc-accurate. Next, we establish a sufficient condition that shows how near-optimal neural network controller for (nw(A) is also Whittl-aaccuaae. Let Qa(s, A) be the average reward of applying neural network with parameters to Enw(A) with initial state s. We can then formally define the concept of near-optimality as follows.
Definition 5 (e-optimal neural network). neural network with parameters O is said be e-oplimal if there exists small positive number 5 such that Q0(81, 2 max((xx,cts11)) (asssss),,saasss Pr.sass (81)) for all so, 81, and X E [fo(so) - 5, fo +
Having outlined the necessary terms, we now move establishing sufficient condition for the y Whittle-accuracy of neural network applied on Enw(A).
Theorem 1. If the arm is strongly indexable, then for any 7 > O, there exists a positive e such that any e-optimal neural network controlling Enw(X) also --Whitle-accurrae
Proof. For a given 7 > 0, let,
c= min (wwm/mmiinn())))e Qw (s) (ee0--Qwaae (w())+))aa()) (w)))-aaass)) (W((s)7.poc) (s))1/
Since the arm is strongly indexable and (()) is its Whittle index, we have >>
We prove the theorem by establishing the following equivalent statement: If the neural network is not Whittle-accurate then there exists states so, 81, activation cost À E [fe(so) 6, fo 6]. such that the discounted net reward of applying neural network to Erw(A) with initial state is strictly less than max (Qx,aet (s1), Qx.pass c
Suppose the neural network is not 7- wwitthhl--ccuuraaee then there exists a state s' such that (f((s W(s') 7- We set 50 81 8'. For the case fo(s') W(s')=>: we set X +5)) Since X > ((s') +7, we have
Xx.pass [8')] Qx.pass(e (s') and Qx. ( Qx.act (8) 2 2c. On the other hand, since To(s')= > X, the neural network would activate the arm in the first round and its discounted reward is at most Q Qx.ace(e (s') < Qx.aass (5') - 2e < max Qx (s'), Q Xa,s (s')} -e.
For the case fs('') < (s')) 7, similar argument shows that the discounted reward for the neural network when X = fo(s") 5 smaller than max aot (s'), Qx (s')} }} e. This completes the proof.
4.2 Training Procedure for WINrWIN
Based on Thm. I and Def. we define our objective function as E...,, = with the estimated index (8)) set as the environment's 's activation cost. neural network that achieves a near-optimal E..., (s fe(su) is also Whittl-aaccuraee, which motivates the usage of deep reinforcement learning to find Whittle-accurate neural networks. Therefore we propose NeurWIN: an algorithm based REINFORCE [3] to update 0 through stochastic gradient ascent, where the
5

---

Algorithm NeurWIN Training
Input: Parameters discount factor 3 E (0, 1), learning rate L, sigmoid parameter m, mini-batch size R.
Output: Trained neural network parameters 0*. for each mini-batch ó do
Choose two states So and s; uniformly at random, and X (s)) and G. t- for each episode in the mini-batch do
Set the arm to initial state 81, and set he <-
for each round in the episode do
Choose a(t] = w.p. (m((f()(t)) - X), and alt) = w.p. om (fo((s) - A) if [t]]] = 1 then
he f he + Voln(om (s]()) - X))
else
he + he + Voln(1 om (fo(s(t)) A))
end if
end for
Ge empirical discounted net reward in episode
G + + Ge/
end for
La f learning rate in mini-batch b
Update parameters through gradient ascent 0 < 0 Lo (. Gb)he end for
gradient is defined Vo Eec.r (0, fo(s))). For the gradient exist, we require the output of the environment to be differentiable with respect to the input fo(s(()). To fulfill the requirement, we replace the step function in Fig. I with sigmoid function,
am (m(so()(()) - 1 m(((((e(())
(1)
Where m is sensitivity parameter. The environment then chooses a|t] 1 with probability om am (fo(s)t)) - A), and aft] with probability 1 (fo((((()) A). We call this differentiable environment Env* (A).
The complete NeurWIN pseudocode is provided in Alg. [ Our training procedure consists of multiple mini-batches, where each mini-batch composed of episodes. the beginning of each mini-batch, randomly select two states and $1. Motivated by the condition in Thm. [ consider the environment Env" (fe(so) with initial state $1, and aim to improve the empirical discounted net reward of applying the neural network to such an environment.
In each episode e from the current mini-batch, we À (s and initial state be $1. We then apply the neural network with parameters 0 to Env" (A) and observe the sequences of actions (a[1),,[2),,... and states (2],...)).... We can use these sequences to calculate their gradients with respect through backward propagation, which we denote by he At the end of the mini-batch NeurWIN would have stored the accumulated gradients for each of the R mini-batch episodes to tune the parameters.
We also observe the discounted net reward and denote by G.. After all episodes the mini-batch finish, we calculate the average of all Ge bootstrapped baseline and denote it by Go. Finally, do a weighted gradient ascent with the weight for episode e being its offset net reward, G, Gb-
When the step size is chosen appropriately, the neural network will be more likely to follow the sequences of actions episodes with larger G. after the weighted gradient ascent, and thus will have better empirical discounted net reward.

---

5 Experiments
5.1 Overview
In this section, we demonstrate NeurWIN's utility by evaluating it under three recently studied applications of restless bandit problems. In each application, we consider that there are N arms and a controller can play M of them in each round. We evaluate three different pairs of (N, M): (4, (10, 1). and (100, 25), and average the results of 50 independent runs when the problems are stochastic. Some applications consider that different arms can have different behaviors. For such scenarios, we consider that there are multiple types of arms and train a separate NeurWIN for each type. During testing, the controller calculates the index of each arm based on the arm's 's state and schedules the M arms with the highest indices.
The performance of WeurWIN is compared against the proposed policies in the respective recent studies. In addition, we also evaluate the REINFORCE (31), Wolpertinger-DDPG (WOLP-DDPG) [0,, Amortized Q-learning (AQL) (27], QWIC (.. and WIBQL 4 REINFORCE is a classical policy-based RL algorithm. Both WOLP-DDPG and AQL are model-free deep RL algorithms meant to address problems with big action spaces. All three of them view restless bandit problem as a Markov decision problem. Under this view, the number of states is exponential in N and the number of possible actions is (, which can be as large as (209) 8 2.4 x 102s in our setting. Neither REINFORCE nor WOLP-DDPE can support such a big action space, so we only evaluate them for (N, M) = (4, 1) and (10, 1). On the other hand, QWIC and WIBQL aim to find the Whittle index through O-learning. They are tabular RL methods and do not scale well as the state space increases. Thus, we only evaluate QWIC and WIBQL when the size of the state space is less than one thousand. We use open-source implementations for REINFORCE 12 and WOLP-DDPG 77.
In addition, we use experiment results to evaluate two important properties. First, we evaluate whether these three applications are strongly indexable. Second, we evaluate the performance of NeurWIN when the simulator does not perfectly capture the actual behavior of an arm.
We use the same neural network architecture for NeurWIN in all three applications. The neural network is a fully connected one that consists of one input layer, one output layer, and two hidden layers. There are 16 and 32 neurons in the two hidden layers. The output layer has one neuron, and the input layer size is the same as the dimension of the state of one single arm. As for the REINFORCE, WOLP-DDPG, AQL algorithms, we choose the neural network architectures so that the total number of parameters is slightly more than N times as the number of parameters in NeurWIN to make a fair comparison. ReLU activation function is used for the two hidden layers. An initial learning rate [15] employed for the gradient ascent step.
L = 0.001 is set for all cases, with the Adam optimizer The discount factor is 3 = 0.99 with an episode horizon of 300 timesteps. Each mini-batch consists of five episodes. More details can be found in the appendix.
5.2 Deadline Scheduling
A recent study 34 proposes a deadline scheduling problem for the scheduling of electrical vehicle charging stations. In this problem, a charging station has N charging spots and enough power to charge M vehicles in each round. When a charging spot is available, new vehicle may join the system and occupy the spot. Upon occupying the spot, the vehicle announces the time that will leave the station and the amount of electricity that it needs to be charged. The charging station obtains a reward of c for each unit of electricity that it provides to a vehicle.
However, if the station cannot fully charge the vehicle by the time it leaves, then the station needs to pay a penalty of F(B), where B is the amount of unfulfilled charge. The goal of the station is to maximize its net reward, defined as the difference between the amount of reward and the amount of penalty. In this problem, each charging spot is an arm. 34 has shown that this problem is indexable. We further show in Appendix B that the problem is also strongly indexable.
We use exactly the same setting as in the recent study [4] for experiment. In this problem, the state of an arm is denoted by a pair of integers (D, B) with B < 9 and D < 12. The size of state space 120 for each arm.
The experiment results are shown in Fig. 2 converges to that of the deadline Whittle index in 600 training episodes. In contrast, other MDP
It can be observed that the performance of NeurWIN
7

---

M
Total Discontt Rewards
1ST
NeurWIN
-150
2000
0001
1... AQL
QWIC
WIBQL
-20
250
REINFORCE
WOL P-DDPG
Deadline lndex
-350
500
1000
1500
2000
500
1000
1500
2008
500
1000
1500
2000
Training Episodes
Figure Average rewards and confidence bounds of different policies for deadline scheduling.
algorithms have virtually no improvement over 2,000 training episodes and remain far worse than NeurWIN. This may be due to the explosion of state space, Even when N is only 4, the total number of possible states is 120* = 2 x 10 making it difficult for the compared deep RL algorithms to learn the optimal control in just 2, 000 episodes. QWIC performs poorly compared to Neur and the deadline index, while WIBQL's performance degrades with more arms. The result suggest that both QWIC and WIBQL. do not learn an accurate approximation of the Whittle index.
5.3 Recovering Bandits
The recovering bandits [21] aim to model the time- vireiiaryigg behaviors of consumers. particular, considers that consumer who has just bought certain product, say, television, would be much less interested in advertisements of the same product in the near future. However, the consumer's interest in these advertisements may recover over time. Thus, the recovering bandit models the reward of playing an arm, i.e., displaying an advertisement, by function f(min (z, zmaz }), where the time since the arm was last played and 2maz is constant specified by the arm. There is no known Whittle index or optimal control policy for this problem.
The recent study 21 considers the special case of M 1. When the function f(-) is known, it proposes a d'-tep lookahead oracle. Once every rounds, the d-step lookahead oracle builds a d-step lookahead tree. Each leaf of the d-step lookahead tree corresponds to a sequence of d actions. The d-step lookahead oracle then picks the leaf with the best reward and use the corresponding actions in the next d rounds. As the size of the tree grows exponentially with d, it is computationally infeasible to evaluate the d-step lookahead oracle when d large. We modify heuristic introduced (1 to greedily construct a 20-step lookahead tree with 20 leaves and pick the best leaf. [21) also proposes two online algorithms, RGP-UCB and RGP-TS, for exploring and exploiting f(-) when it is not known priori. We incorporate [21 open-source implementations of these two algorithms in our experiments.
In our experiment, we consider different arms have different functions f(.). The state of each arm is its value of min (2, } } and we set 2maz 20 for all arms.
N M=1
100
Total Discountd Rewards
600
750
NeurWIN
AQL.
QWIC
550
WIBQL
RGP-UCB. RGP-TS, d=1
3000
330
REINFORCE
4- So
WOLP WOLP-DDPG
160
Omcle, d= 20
10000
26000
30000
10000
20000
30000
10000
20000
30000
Training Episodes
Figure 3: Experiment results for the recovering bandits.
Experiment results are shown in Fig. It can be observed that NeurWIN is able to outperform the 20-step lookahead oracle in respective setting with just few thousands of training episodes. Other algorithms perform poorly.

---

5.4 Wireless Scheduling
recent paper [ studies the problem of wireless scheduling over fading channels. In this problem. each arm corresponds to wireless client. Each wireless client has some data to be transmitted and it suffers from a holding cost of unit per round until it has finished transmitting all its data. The channel quality of wireless client, which determines the amount of data can be transmitted if the wireless client is scheduled, changes over time. The goal is to minimize the sum of holding costs of all wireless clients. Equivalently, cost. Finding the Whittle index through theoretical analysis is difficult. Even for the simplified case when the channel quality is i.i.d. over time and can only be in one of two possible states, the recent paper I can only derive the Whittle index under some approximations. It then proposes a size-aware index policy using its approximated index.
view the reward of the system the negative of the total holding
In the experiment, we adopt the settings of channel qualities of the recent paper. The channel of a wireless client can be in either a good state or a bad state. Initially, the amount of load is uniform between 0 and 1Mb. The state of each arm is its channel state and the amount of remaining load. The size of state space is 2 10 for each arm. We consider that there are two types of arms, and different types of arms have different probabilities of being in the good state. During testing, there are N arms of each type.
N-4 M-1
N 10
M-1
N
M 25
Total Disceented Rewards
-310 -2601 -210 -100
NourWIN
009
AQL REINFORCE
WOLF-DDPG
NEN-
0069
Size Aware Index
10000
20000
30000
10000
20000
50000g
10000
20000
50000
Training Episodes
Figure 4: Average rewards and confidence bounds of different policies for wireless scheduling.
Experiment results are shown in Fig. It can be observed that Neu is able to perform as well as the size-aware index policy with about 5, 000 training episodes. It can also be observed that other learning algorithms perform poorly.
5.5 Evaluation of Neur WIN's Limitations
limitation of Neur is that it is designed for strongly indexable bandits. Hence, it is important to evaluate whether the considered bandit problem is strongly indexable. Recall that a bandit arm is strongly indexable if D2 (A) is strictly decreasing in X, for all states s. We extensively evaluate the function (X) of different states for the three applications considered in this paper. We find that all of them are strictly decreasing in X. Fig. shows the function (A) of five randomly selected states for each of the three applications. The deadline and wireless scheduling cases were averaged over 50 runs. These results confirm that the three considered restless bandit problems are indeed strongly indexable.
Deadline Schedaling
Recovering Bandiis
Wimden Schoduling
[629265, 06)
(499776. 1.0
(479584 10)
[770%6] 0.0
[559913, 00)
s117.4
515..71
10
- [10,3 31
2
10
12.
Figure 5: Difference in discounted net reward D2 for randomly selected initial states.
9

---

Another limitation of WeurWIN is that it requires simulator for each arm. To evaluate the robustness of NeurWIN, we test the performance of NeurWIN when the simulator not perfectly precise. In particular, let Ract (s) and Rpass(s) (s) be the rewards of an arm in state when it is activated and not activated, respectively. Then, the simulator estimates that the rewards are ( (1 Gact,a) Race(s) and Rapss (8) (1 + G passe_a) R (s), respectively, where Gact, and G pass,s are independent Gaussian random variables. The variance of these Gaussian random variables correspond to the magnitude of root mean square errors in the simulator.
Deadline Schedoling
Recovering Bandits
Wireless Scheduling
-1900
0011
Total Discmited Rewards
1850
NeurWIN
NeurWIN 10%
1ibr--
Ne 20% emorr
NeurWIN 40% ertor
Deadline Index
-2500
3300
Oracle, d
Size
1000
1500
10000
30000
10000
20000
30000
Training Episodes
Figure 6: Experiment results for NeurWIN with noisy simulators.
We train NeurWIN using the noisy simulators with different levels of errors for the three problems. For each problem, we compare the performance of NeurWIN against the respective baseline policy. Unlike NeurWIN, the baseline policies make decisions based on the true reward functions rather than the estimated ones. The results for the case N 100 and M 25 shown in Fig. 6 It can be observed that the performance of NeurWIN only degrades a little even when the root mean square error is large as 40% of the actual rewards, and its performance remains similar or even superior to that of the baseline policies.
6 Conclusion
This paper introduced NeurWIN: a deep RL method for estimating the Whittle index for restless bandit problems. The performance of NeurWIN is evaluated by three different restless bandit problems. In each of them, NeurWIN outperforms or matches state-of-the-art control policies. The concept of strong indexability for bandit problems was also introduced. In addition, all three considered restless bandit problems were empirically shown to be strongly indexable.
There are several promising research directions to take NeurWIN into: extending NeurWIN into the offline policy case. One way utilize the data samples collected offline construct a predictive model for each arm. Recent similar attempts have been made for general MDPs in [14 33 NeurWIN would then learn the Whittle index based on this predictive model of a single arm, which is expected to require fewer data samples due to the decomposition provided by index policies.
Another direction is to investigate NeurWIN's performance in cases with non-strong indexability guarantees. For cases with verifiably non troonglyindexable states, one would add a pre-processing step that provides performance precision thresholds on non-indexable arms.
Acknowledgment
This material is based upon work supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Grant Numbers W91 1NF-18-1-0331, 191 and
in part by Office of Naval Research under Contracts N00014-18-1-2000 and N00014-21-1-22 in part by the National Science Foundation under Grant Numbers CNS 1955696 and CPS-2038963, and in part by the Ministry of Science and Technology of Taiwan under Contract Numbers MOST 199-263-EE-009-00 and MOST 110-2628-BB A-49-0444
10

---

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 Measurement and Modeling of Computer Systems, pages 57-69, 2015.
[2] J. Abounadi, D. Bertsekas, and V. S. Borkar. Learning algorithms for markov decision processes with average cost. SIAM Journal on Control and Optimization, 40(3):681-688 2001.
[3] K. Avrachenkov and V. S. Borkar. A learning algorithm for the whittle index policy for scheduling web crawlers. 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1001-1006 2019.
[4] Konstantin Avrachenkov and Vivek S. Borkar. Whittle index based q-learning for restless bandits with average reward. CoRR, abs/2004. 14427, 2020.
[5] Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, and Milind Tambe. Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, pages Montreal, Canada, August 2021. International Joint Conferences on Artificial Intelligence Organization.
[6] V. S. Borkar and K. Chadha. A reinforcement learning algorithm for restless bandits. In 2018 Indian Control Conference (ICC), pages 89-94, 94, 2018.
[7] ChangyWen.
Changy Wen/wolpertingerr ddpg. wolpertinger ddpg. April 2021. original-date-
https: com/ ChangyWen/
[8] Christopher R Dance and Tomi Silander. When are kalman-filter restless bandits indexable? In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 1711-1719. Curran Associates, Inc., 2015.
[9] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 5717-5727, Red Hook, NY, USA,
2017. Curran Associates Inc.
[10] Gabriel Dulac-Amold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap. Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep reinforcement learning large discrete action spaces. arXiv preprint arXiv: 152.076679 2016.
[11] J. Fu, Y. Nazarathy, S. Moka, and P. G. Taylor. Towards q l-leanning the whittle index for restless bandits. In 2019 Australian New Zealand Control Conference (ANZCC), pages 249-254, 2019.
[12] Christian Hubbs. Learning reinforcement learning: Reinforce with pytorch! https:/loovallsatsscceee.m/////s htt..///////aaaneeeeorrreeeemmea wew.nntt-eaninnn-ie cerhiingrriffooee-weee weaeee-wwwhhhttttttt 5e8ad7fe7da0, Dec 2019.
[13] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. volume 70 of Pro- ceedings of Machine Learning Research, pages 1704-1713, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
[14] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model-based offline reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21810-21823 Curran Associates, Inc., 2020.
[15] Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- lional Conference on Learning Representations (ICLR), 2015.
[16] J. Le Ny, M. Dahleh, and E. Feron. Multi-uav dynamic routing with partial observations using restless bandit allocation indices. In 2008 American Control Conference, pages 4220 4225, 2008.
[17] Alex S. Leong, Arunselvan Ramaswamy, Daniel F. Quevedo, Holger Karl, and Ling Shi. Deep reinforcement learning for wireless sensor scheduling in cyber-physical systems. Automatica, 11:119 2020.
[18] R. Meshram, D. Manjunath, and A. Gopalan. On the whittle index for restless multiarmed hidden markov bandits. IEEE Transactions Automatic Control, 63(9):3046-300 3053, 2018.
11

---

[19] José Niño-Mora. Dynamic priority allocation via restless bandit marginal productivity indices. Top. 15(2):161-198, 2007.
[20] Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293-305, 1999.
[21] Ciara Fike-Burke and Steffen Grunewalder. Recovering bandits. In Advances in Neural Information Processing Systems, pages 14122-14131, 2019,
[22] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. International Conference Learning Representations (ICIRR), 2018.
[23] Julien Seznec, Pierre Menard, Alessandro Lazaric, and Michal Valko. A single algorithm for both restless and rested rotting bandits. In International Conference on Artificial Intelligence and Statistics, pages 3784-3794, 2020.
[24]
Aleksandrs Slivkins and Eli Upfal. Adapting to a changing environment: the brownian restless bandits. In COLT, pages 343-354, 2008.
[25] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[26] V. Tripathi and E. Modiano. A whittle index approach to minimizing functions of age of information. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1160-1167, 2019.
[27] Tom Van de Wiele, David Warde-Farley, Andriy Mnih, and Volodymyr Mnih. Q-learnin in enor- mous action spaces via amortized approximate maximization. arXiv preprint arXiv:2001.08) 16, 2020.
[28] S. Wang, H. Liu, P. H. Gomes, and B. Krishnamachari. Deep reinforcement learning for dynamic multichannel access in wireless networks. IEEE Transactions on Cognitive Communications and Networking, 4(2):257-265, 2018.
[29] T. Wei, Yanzhi Wang, and Q Zhu. Deep reinforcement learning for building hvac control. In 2017 54th ACM/EDAC/EEE Design Automation Conference (DAC), pages 1-6, 2017.
[30] Peter Whittle. Restless bandits: Activity allocation in changing world. Journal of applied probability, pages 287-298, 1988.
[31] Ronald J. Williams. Simple statistical tradient-followin algorithms for connectionist reinforce- ment learming. Mach. Learn., 8(3-4):229-255 256, May 1992.
[32] Huizhen Yu and Dimitri P Bertsekas. Convergence results for some temporal difference methods based on least squares. IEEE Transactions on Automatic Control, 54(7):1515- 2009.
[33] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balean, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 14129-14142. Curran Associates, Inc., 2020.
[34] Z. Yu, Y. Xu, and L. Tong. Deadline scheduling as restless bandits. IEEE Transactions on Automatic Control, 63(8):2343 2258, 2018
[35] Andrea Zanette and Emma Brunskill. Problem dependent reinforcement learning bounds which can identify bandit structure in MDPs. volume 80 of Proceedings of Machine Learning Research, pages 5747-5755, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[36] Qing Zhao. Multi-armed bandits: Theory and applications to online learning in networks. Synthesis Lectures on Communication Networks, 12(1):1-165, 2019.
12


Reviews:
[{"review_id": "zld-V1O7RsD", "reviewer": "Reviewer_jp8H", "summary": "The authors develop a reinforcement learning based method for computing the Whittle Index heuristic policy for solving Restless Bandit problems. This is a novel methodological contribution in the space of restless bandits. Several experimental results are provided demonstrating the good performance and general applicability of the method.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper presents an original algorithm that will be of general interest to researchers in the restless bandits space. Specifically, the authors seem to be the first to use neural-network-based function approximation for learning the Whittle index policy. The paper is relatively well structured and written, though some key concepts are unclear (more comments provided below). The experimental results are comprehensive and the domains tested are strong ones, making their results fairly convincing, with a few minor comments. However, authors also missed a key competitor in related work. I think this work has potential to be a good submission, but I ask for the following clarities.\n\nMajor comments:\n1. Thm 3 is reasonable in terms of motivating the use of reinforcement learning for finding the Whittle index. However, I feel like what is missing from this paper is a Thm 4 that proves that algorithm 1 is valid/will converge to the proper values of the Whittle index -- I expound on this in the next comment.\nI am having some trouble determining the validity of algorithm 1. Perhaps its presentation could be improved. As far as I can tell, a key component of the validity of the algorithm is that the \\lambda value is set by the network at the start of each minibatch of training, which itself sets the cost of acting in the environment. If we assume that this method converges, then eventually we would expect that that lambda value would be set to the Whittle index, i.e., the value that makes the planner expect to get exactly 0 reward for following the optimal policy -- and since you are actually charging that \\lambda value in the empirical rewards, it seems that the trajectories would also go to 0 in expectation. However, an alternative controller which sets \\lambda to 0 and always predicts 0 would always act randomly, but never get charged any cost of acting -- why would a neural network not find the second option preferable if it receives greater reward? This does not seem to be what happens, since the experimental results are convincing. So it would greatly help to have both an intuitive, and really a theoretical justification for why the authors' algorithm converges.\n\n2. Line 251 - 253: \"For such scenarios, we consider that there are multiple types of arms and train a separate NeurWIN for each type\"\n - it would be nice to see also an experiment where every arm is sampled randomly from some distribution or set of distributions, since the assumption that many arms are exactly the same seems strong and could lead to cases where the Whittle indexes that need to be learned for different arm types have significant numerical separation that makes the precision of the authors' method less important for achieving good performance in the environment. This may increase computational demand, but seems reasonable to run so that we can see experimentally that the authors' method is learning the Whittle indices to a non-trivial precision. \n\n3. Authors missed an important competitor which proposes a Q-learning algorithm for learning the Whittle index which comes with convergence guarantees (bibtex below). Authors implement and compare against this baseline, as it seems to be the closest competitor to their algorithm. However, since the authors' method is based on deep Q-learning, it is more general than the below competitor that uses tabular Q-learning. However, there is likely overlap in the theory regarding the proof of convergence of the competitor method, and the algorithmic ideas behind NeurWIN that should be elucidated by the authors to properly contextualize the authors' contribution.\n \n@article{avrachenkov2020whittle,\n  title={Whittle index based Q-learning for restless bandits with average reward},\n  author={Avrachenkov, Konstantin and Borkar, Vivek S},\n  journal={arXiv preprint arXiv:2004.14427},\n  year={2020}\n}\n \nMedium Comments:\n4. Fig 3 - how well does 20-step lookahead perform on (4,1) and (10,1)? Also why does QWIC outperform the lookahead on (4,1) but not (10,1)? \n\n5. The authors of [17] implement UCB and Thompson-Sampling based algorithms -- it would be helpful to see how NeurWIN compares to these baselines on at least the recovering bandits environment.\n\n6. Line 338- 340: \"Fig. 5 shows the function Ds(λ) of five randomly selected states for each of the three applications. This result suggests that most practical bandit problems are indeed strongly indexable.”\n\"Most\" is far too strong a claim based off the N=3 experimental domains given as evidence. This evidence is at best a proof of concept. A far more principled investigation of what it means to be (and not to be) strongly indexable in terms of problem structure would be necessary here to a claim about \"most\" bandits and more context would need to be given about what is meant by \"most\", e.g., most \"real-world bandits?\", \"most bandits in literature?\", \"most out of all possible bandits?\", etc.\n\n7. Throughout the paper, the authors make implicit claims that most problems are indexable without giving much support for that claim. Perhaps because the authors' algorithm relies on problems being indexable in order to be asymptotically optimal. Some things that could help strengthen this paper in that regard:\n  a) Adapt/reframe the numerical \"strong indexability\" verification step that authors' use in experiments to be a pre-processing step to their algorithm. This way, users can at least numerically verify to their desired level of precision whether or not the authors' algorithm will be optimal for their use-case.\n  b) Argue for the strength of the Whittle index approach in non-indexable or non-verifiably-indexable (e.g., very large state space) cases by pointing to the  provided experimental results or pointing to papers that have analyzed/experimented with the Whittle index policy in such cases.\n\nMinor Comments:\nline 32- 33: \"where the index loosely corresponds to the amount of cost that we are willing to pay to play the arm\"\n- Authors should consider rewording this. The Whittle index is defined as exactly this cost that the planner is willing to pay to play the arm, so I am not certain that saying \"loosely corresponds\" is accurate.\n \n33-34: \"It has been shown that the Whittle index policy is either optimal or asymptotically optimal in many settings.\"\n- Probably makes sense to introduce indexability here? E.g., “asymptotically optimal under a technical condition known as indexability”. In general it would be helpful to frame the story of RMABs in the light of how the problem has typically been solved, i.e., by proving or providing evidence of indexability, then deriving Whittle index policies. Then making clear how your algorithm will improve on this style of approach and why it is valid.\n \n35-36: \"In this paper, we present Neural Whittle Index Network (NeurWIN), a principled machine learning approach that finds the Whittle indices for virtually all restless bandit problems.\"\n- The Whittle index does not always exist, i.e., when a problem is not indexable. So this statement is somewhat misleading and should be explained more carefully. Can you be more precise by what you mean by \"virtually all restless bandit problems\"?\n \nLine 66: \"There has been a lot of studies\"\n - Just suggesting something slightly more formal thant \"a lot\", e.g., \"There have been many studies\"\n \nIn definition 2, I was mildly confused why s was in A(\\lambda)... but realized that A(\\lambda) is indeed defined as a set of states. I would lightly suggest using something besides A for a set of states (perhaps \\sigma?), since lower-case a is used for actions.\n \nline 142: \"attractable\" --> attractive\n \nline 142-143: \"Intuitively, as the activation cost increases, it becomes less attractable to activate the arm in any given state. Hence, one would expect Ds(λ) to be strictly decreasing in λ for most practical problems.\"\n - While I tend to agree with this claim, I think the authors should make an effort to support this argument that \"most problems are strongly indexable\" with evidence (perhaps mention the experimental results) more so than intuition or by arguing further about the typical structure of problems. While it seems reasonable that increasing activation cost would not increase attractiveness, it seems perfectly plausible that increasing activation cost would leave attractiveness unchanged in some problems with specific structure.\n \nThm 1. -- this is mostly a restatement of existing concepts, i.e., indexability and the \\lambda-adjusted Q-values, so I would consider reassigning this as a proposition or something similar. To this reviewer, a theorem implies a novel theoretical contribution.\n \nThm 2. -- It is unclear to me why strong indexability is important. It is not a concept I am familiar with from other restless bandit literature and unclear how it helps the authors' algorithm. Strong indexability seems to guarantee that there should be one unique \\lambda that makes D(s,\\lambda)=0, but again, it would help if the authors could clarify why such a concept is useful. For instance, such a concept is not required by Weber and Weiss in the proof of the optimality of the Whittle index. Understanding strong indexability is important to this reviewer, since the authors present these results as Theorems in their paper. Perhaps it is required for their neural network system to be differentiable everywhere?\n \n- Recovering bandits is a strong experimental domain for the authors' algorithm, since the indexability of this space is unknown. It would help to highlight explicitly this fact in the introduction to make clear the algorithm's general applicability.\n---------------------------------------------\nUpdate:\n\nI have read the other reviews and the author responses. I thank the authors for their response. Overall I am now convinced about the empirical results, but still unsure about the theory and the algorithm itself.\n\nExperiments: The authors thoroughly addressed all my comments about experimental results, including implementations of WIBQL and UCB/Thompson Sampling from [17] and the results seem convincing enough, though I agree with Ha51 that WIBQL requires much hyperparameter tuning to be most effective, so it would be good to have more details there.\n\nTheory/Algorithm: I am also still not sure how well the theory actually supports the algorithm, even with the revised theorems. I am also still somewhat lacking in my understanding of why exactly the proposed algorithm should converge, and unfortunately, the authors did not address that concern in their response (at least not clearly).\n\nUltimately, I am increasing my score by 1 to reflect the authors addressing my empirical concerns. However, authors should make their code publicly available upon acceptance to facilitate others building on the authors' contributions despite some lack of clarity in the algorithmic descriptions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "RvXYA8D2CZH", "reviewer": "Reviewer_Ha51", "summary": "The paper proposes a method to automatically learn the Whittle Indices for a Restless Multi-Armed Bandit (RMAB) problem. \n\nContributions:\n\nThe Algorithm: The algorithm tries to learn a neural network that takes as input the state of a given arm and provides as output the whittle index of that state. It does this by showing a connection between the whittle indices for an arm and the indices of an optimal index policy for a family of MDPs (Env(𝝀)) based on that arm’s MDP (Env). It then learns a good index policy for this family of MDPs using a REINFORCE-type method.\n\nTheoretical Justification: Towards substantiating the claim that learning a good policy for Env(𝝀) is equivalent to learning a good whittle index, the paper provides a proof about an epsilon-delta relationship between learning a good policy and a good whittle index.\n\nEmpirical Justification: The paper shows that the proposed algorithm works well on 3 previously published RMAB instances, when compared with 1 similar ‘learning a whittle index’-type baseline and 2 reinforcement learning baselines.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Positives:\n1) Interesting idea: There has been a lot of recent interest in trying to automatically calculate the whittle index. However, to my knowledge, the approach outlined in this paper is different from those presented in past/contemporary work. Here, the algorithm tries to learn the whittle indices for an arm by learning a good index policy for a superset of MDPs (Env(𝝀)) in which you have to pay a cost of 𝜆 to choose the ‘active’ action. This is because the indices of such an optimal index policy are equal to the whittle indices (under indexability assumptions), and even if you can’t learn the optimal policy, the paper has a proof that suggests an almost optimal policy leads to almost correct whittle indices. There are lots of good algorithms for solving MDPs and so reducing the whittle index problem to this new one seems like a good idea.\n\n2) Experiments on previously published RMAB instances: Rather than arbitrarily creating RMAB instances, the paper shows the effectiveness of the proposed algorithm on 3 classes of RMABs that have been previously published in the literature and, as a result, are more likely to be relevant to practice. In addition, the experimental results indicate that this method reaches a performance level equal to that of the optimal/SOTA solution.\n\nNegatives:\n1) Weak baselines and limited related work: While the experimental domains are great,  I believe that the comparison baselines are quite weak. Importantly, the paper fails to include WIBQL [1], a provably correct Q-Learning based algorithm for automatically learning whittle indices. Although the exact implementation presented in that paper is for the average reward setting and tabular case, there is a fairly straightforward extension that would allow you to learn a neural network-based function approximator for these indices. Even without this, I believe that the RL-based baselines are too weak and instead simpler baselines like decomposing the joint problem into individual problems would work better. (To do this, you’d solve the MDP to get the optimal Q-values for each arm independently, and then choose the M arms with the greatest Q(s[t], active)-Q(s[t], passive).)\n\n2) Weak analysis of limitations:\nWhile the paper acknowledges the fact that strong indexability is important to the performance of this method, it doesn’t test the performance of the method on RMAB instances that aren’t strongly indexable. Instead, it makes the strange claim that, because the 3 chosen instances are strongly indexable, ‘most practical bandits problems are indeed indexable’. The conclusion that I draw from this fact is that ‘people publish papers about RMABs that have nice properties’. It would be useful to see the results of the algorithm on RMAB instances that aren’t indexable.\nThe paper recognizes that it is important to have a simulator for this algorithm to work (because of its need for on-policy rollouts). However, in defending it, the paper argues that the algorithm still performs well on a slightly worse simulator. While this is a useful experiment in showing the algorithm’s robustness to noise, it does not address the underlying limitation. It would be more interesting if the authors commented on possible offline/off-policy extensions to their proposed algorithm.\n\n3) Proof is nice to have, but there are issues: While it’s useful to have a proof that shows some relationship between the closeness of the indices of a good index policy for Env(𝝀) and the true whittle indices, (a) I don’t understand the statement of the proof, and (b) it’s quite weak. For (a), there are 2 sets of if-then relationships in the statement which make it hard to understand. In addition, it’s not clear how  is related to  and -- for example, for something to be 0.1-accurate, what are the conditions on  and . Also, the statement seems to be a bit different from the normal - definition; wouldn’t the statement always be trivially true for an arbitrarily large ? It would be useful if you could clarify the statement and provide a proof sketch. For (b), the proof doesn’t say anything quantitative. To begin with, it’s not clear how  and  are related, i.e., how close to the optimal whittle indices you’ll get for being within an \\epsilon ball of the optimal. Even if it’s small, it’s unlikely that you will ever know what the optimal is and, as a result, how close you are to it. Finally, even if you did know the distance between your estimate of the whittle index and the true index, it’s unclear what impact that would have on the final expected return for the RMAB (across multiple arms).\n\nOther Comments:\n1) Paper organisation could be improved.\nA proof sketch for Theorem 3 would be nice to have in the main text given that it’s the primary theoretical contribution.\nSection 3.3 does not add much value and could be pushed to the appendix in favor of the proof sketch.\nThe details of the NeurWIN algorithm could be introduced earlier; they’re currently at the end of page 5 (more than half way through the paper).\n2) The neural network used is very small (16, 32 dimensional layers). Do things change if you use bigger/smaller neural networks/different architectures?\n3) In Figure 6, it seems like NeurWIN does better w.r.t. baselines for the Recovering Bandits and Wireless Scheduling problems when there is a noisy simulator vs. the exact simulator. It’s not clear why that should be the case.\n4) There is some contemporaneous work on this problem (cited below) that the authors might find interesting.\n\nConclusion: The idea is interesting and the experimental results seem to show that the algorithm does its job in practice. As a result, despite a perfunctory limitations section, weak baselines and unclear theoretical contributions, I recommend a weak accept for the paper. I would increase my rating if the authors address the comments about the limitations and include stronger baselines.\n\nCitations:\n[1] Avrachenkov, Konstantin, and Vivek S. Borkar. \"Whittle index based Q-learning for restless bandits with average reward.\" arXiv preprint arXiv:2004.14427 (2020).\n[2] Biswas, Arpita, et al. \"Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare.\" arXiv preprint arXiv:2105.07965 (2021).\n\n---\nEDIT AFTER REBUTTAL: Increased score from 6 to 7 (see response to rebuttal for more details).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: While the paper does discuss possible limitations of its work, the analysis is not of high quality.\n\nSocietal Impact: The paper details an algorithm for a general class of problems. From its description, there doesn’t seem to be any obvious ethical impacts that would be associated with its usage across the broad class of problems. However, those considering employing this algorithm for a specific application should perform an application-specific analysis.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "RPRBpJuQ082", "reviewer": "Reviewer_WCWa", "summary": "\nWhittle index are used to construct a powerful heuristics for restless bandit problem.  This paper proposes to estimate Whittle Index in discounted Restless bandit problem via a deep reinforcement learning algorithm. The authors define a notion of strong indexability that they use to construct a deep RL algorithm that learns Whittle indices. The authors argue that when a problem is strongly indexability and the neural network is precise enough, the deep RL algorithm will learn Whittle index (although their theoretical result is not fully convincing to me).\n\nThe authors present extensive experimental results that show that their algorithm compute Whittle indices and provide a very good performance compared to existing work.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I liked the paper and the algorithm it proposes. While Whittle indices have been defined a long time ago, there is a recent surge of interest on restless bandits since it has potential application in many RL problems. I liked the experimental section that I find quite thorough and convincing. The comparison with related work is interesting as well as the fact that the authors show the strong indexability of various problems (either theoretically for the first, or numerically). This indicates that this notion is adapted. The algorithm performs very well in three real-life problems. Also, the limitation of the algorithm is provided: the authors test the case where simulator is noisy and the strong indexability of the three problems. All-in-all, this convinced me that the presented algorithm has potential application for many restless bandit learning algorithms.\n\nThat being said, I think that the novelty of the paper is somehow limited and I think that some part would deserve to be better explained. In particular, I did not find Theorem 3 very informative: I found the current version of the theorem rather weak and it does not convince me that a rich-enough network will indeed learn the true Whittle indices.\n\nTo me, it is not clear how others algorithms are trained (the same number of episodes and batches as NeurWIN?). And about others algorithms structures (almost the same number of parameters as NeurWIN, but how the hidden layers, input and output layers are connected?).\n\nThe NeurWIN algorithm seems to need an internal simulator. It is an off-policy algorithm. Can we say something about its regret (at least empirically?) or in general about its performance while learning? \n\nAlso, Whittle indices are particularly useful for time-average reward and not for the discounted case. Would it still work here?\n\nMinor remark: In the organization of the paper, I do not understand why section 3.3 is where it is. This section is interesting but completly breaks the flow of the paper. To me, this should be moved to section 5 (or merged with section 5.5 in a new section).\n\n\n** Rebuttal **\n\nThe answer of the authors clarified my view of the paper. I am raising my score from 5 to 6 (not higher because I am still puzzled about the novelty of the approach, and because incorporating the new theory in a convincing manner might not be that trivial.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Could the authors explain better what is the implication of Theorem 3? Does it guarantee anything on the convergence of the algorithm?\n\nThe pseudo-code of the algorithm is very hard to understand. Could the authors justify their design choices and the potential impact of them?\n\nIs there an open-source implementation of the code that would make it usable by others? ", "review_text": "", "extra_scores": {"ethical_concerns": "NA.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the important problem of restless bandit. While the Whittle index is known to optimally solve the problem, it remains hard to compute in many practical problems. The authors propose a solution leveraging the generalization capabilities of neural networks in a non trivial way and obtains a practically feasible and accurate method.

After the rebuttal and the discussion, the reviewers agree that the problem is significant and the contribution is interesting and it is likely to set an important baseline for future work on the topic. For this reason I recommend acceptance. Yet, there remains a number of aspects that the authors should improve in the final version:
- Add the comparison to WIBQL detailing how it is implemented and clarifying that defining a scalable version (i.e., with neural networks) is outside the scope of the paper.
- Add the improved version of the theory and possibly include an additional paragraph discussing in detail its relevance.
- Clearly acknowledge the need for a simulator and discuss how this could be possibly relaxed as a future work.
- Integrate reviewers' suggestions while improving the structure and overall clarity of the paper.


Decision: Accept (Poster)