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:  (2021)
Keywords: deep reinforcement learning
restless bandits
Whittle index

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 either better than, or as good as, state-of-the-art policies for all three problems.

Under review as a conference paper at ICLR 2021
NEURWIN: NEURAL WHITTLE INDEX NETWORK FOR RESTLESS BANDITS VIA DEEP RL
Anonymous authors Paper under double-blind review
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 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 either better than, as good as, fffte-ofthheaar art policies for all three problems.
INTRODUCTION
Many sequential decision problems can be modeled as multi-armed bandit problems. A bandit problem models each potential decision as an arm. In each round, we play M arms out of total of N arms by choosing the corresponding decisions. We then receive a reward from the played arms. The goal is to maximize the long-term total discounted reward. Consider, for example, displaying advertisements on an online platform with the goal to maximize the long-term discounted click- through rates. This can be modeled as a bandit problem where each arm is a piece of advertisement and we choose which advertisements to be displayed every time particular user visits the platform. should be noted that the reward, i.e., click-through rate, of an arm not stationary, but depends on actions in the past. For example, user that just clicked much less likely to click on the same advertisement in the near future. Such a problem a classic case of the restless bandit problem, where the reward distribution of an arm depends on its state, which changes over time based on our past actions.
a particular advertisement may be
The restless bandit problem is notoriously intractable (Papadimitriou & Tsitsiklis 1999). Most cent efforts, such as recovering bandits PPike-Burke & Grunewalder] (201)), rotling bandits (Seznec) et al. 2020), and Brownian bandits (Slivkins & Upfal, 2008), only study some special instances of the restless bandit problem. The fundamental challenge of the restless bandit problem lies in the explosion of state space, as the state of the entire system the Cartesian product of the states of individual arms A powerful tool to address the explosion of state space is the Whittle index policy (Whittle 1988). 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 loosely corresponds to the amount of cost that we are willing to pay to play the arm, and then plays the arm with the highest index. It has been shown that the Whittle index policy is either optimal or asymptotically optimal in many 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 is 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 able to circumvent the challenges of finding the Whittle indices by leveraging 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 pay

---

Under review as a conference paper at ICLR 2021
constant cost of À every time we play the arm. The goal is to 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 X. 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 X.
Using this observation, we propose a deep reinforcement learning method to train NeurWIN. To demonstrate the power of NeurWIN, we employ NeurWIN for three recently studied restless bandit problems, namely, recovering bandit (Pike-Burke & Grunewalder 2019), wireless scheduling (Aalto) al. 2015). and stochastic deadline scheduling (Yu et al. 2018). There is no known Whittle index for the first problem, and there is only an approximation of the Whittle index under some relaxations for the second problem. Only the third problem has a precise characterization of the Whittle index. For the first two problems, the index policy using our NeurWIN achieves better performance than existing studies. For the third problem, the index policy using our NeurWIN has virtually the same performance as the Whittle index policy.
The rest of the paper is organized as follows: Section 2 reviews related literature. Section 3 pro- vides formal definitions of the Whittle index and our problem statement. Section + introduces our training algorithm for WeurWIN. Section [ demmosstrates the utility of NeurWIN by evaluating its performance under three recently studied restless bandit problems. Finally, Section 6 concludes the paper.
2 RELATED WORK
Restless bandit problems were first introduced in (Whiule 1988). They are known to be intractable, and are in general PSPACE hard (Papadimitriou & Tsitsiklis 1999). As a result, many studies focus on finding the Whitte index policy for restless bandit problems, such as in (Le Ny et al. 2008 Meshram et al. 2018 Tripathi & Modiano 2019; Dance & Silander, 2015). However, these studies are only able to find the Whittle indices under various specific assumptions about the bandit problems.
There has been a lot of studies on applying RL. methods for bandit problems. (Dann et al. 2017) proposed a tool called Uniform-PAC for contextual bandits. (Zanette & Brunskill. (2018 8) described a framework-agnostic approach towards guaranteeing RL algorithms' performance. (Jiang et al.) 2017) introduced contextual decision processes (CDPs) that encompass contextual bandits for RL exploration with function approximation. (Riquelme et al.] 2018) 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 (Wei et al. 2017). cy cyher-physical systems (Leong et al. 2020). and dynamic multi- channel access (Wang et al. 2018). In all these cases, major limitation for deep RL is scalability. As the state spaces grows exponentially with the number of arms, these studies can only be applied 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. (Borkar & Chadhal (018)) proposed employing the LSPE(() algorithm (Yu & Bertsekas 2009) coupled with a polynomial function approximator. The approach was applied (Avrachenkov & Borkar 2019) for scheduling web crawlers. However, this work can only be applied to restless bandits whose states can represented by single number, and it only uses polynomial function approximator, which may have low representational power (Sutton & Barto (208). (Fu et al.) (219)) proposed a Q-learning based heuristic to find Whittle indices. However, as shown in its experiment results, the heuristic may not produce Whittle indices even when the training converges.
PROBLEM SETTING
In this section, we provide a brief overview of restless bandit problems and the Whittle index. We then formally define the problem statement.
2

---

Under review as a conference paper at ICLR 2021
3.1 RESTLESS BANDIT PROBLEMS
A restless bandit problem consists of N restless arms. In each round t, control policy observes the state of each arm i, denoted by s,(t]. and selects M arms to activate. We call the selected arms as active and the others passive. We use a:(0] to denote the policy's decision each arm i, where a=[t] =1 if the arm is active and a;(t) = 0 if is passive at round f. Fach arm generates a stochastic reward rı[d] with distribution
(5; [t] if it is active, and with distribution Rissas (s:(t)) if
is passive. The state of each arm i in the next round evolves by the transition kernel of either Pa (s) or (s.pass(s.ft) [f)), depending on whether the arm is active. The goal of the control policy
is to maximize the total discounted reward, which can be expressed as Ex=1 Σ 3'r:(() with B being the discount factor.
A control policy is effectively a function that takes the vector (8) [4] 82 [t,,..... sN(()) as the input and produces the vector (ag [4) [2(4),... ax [4] 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 an index, denoted by (s)sst)), ), for each arm i 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 an arm i is independent from the states of any other arms.
Obviously, the performance of an index policy depends the design of the index function W;(+). A popular index with solid theoretical foundation is the Whittle index, which is defined below. Since we only consider one arm at time, we drop the subscript for the rest of the paper.
Consider a system with only one arm, and a control policy that determines whether to activate the arm in each round f. Suppose that the policy needs to pay an activation cost of À every time it chooses to activate the arm. The goal of the control policy is to maximize the total discounted net reward, Σr= 8 (r[t]- >a(t)). The optimal control policy can be expressed by the set of states in which it would activate this arm for a particular X, and we denote this set by A(A). Intuitively, the higher the cost, the less likely the optimal control policy would activate the arm in a given state, and
hence the set A(A) should decrease monotonically. When an arm satisfies this intuition, we say that the arm is indexable.
Definition 1 (Indexability). An arm is said to be indexable if A(x) decreases monotonically from the set of all states the empty set as X increases from -0 co. 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 is defined as W(s) == supx :8 E A())).
Even when an arm is indexable, finding its Whittle index can still be intractable, especially when the transition kernel of the arm is convoluted] Our 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 control policy activates the arm at round one, and then uses the optimal policy starting from round two; and the second is that the control policy does not activate the arm at round one, and then uses the optimal policy starting from round two. Let (s)) and Qx (s) be the expected discounted net reward for these two possibilities, respectively, and let (x) := (Q) Qx.paee(s)) be their difference. Clearly, the optimal policy should activate an arm under state s and activation cost A if (A 2 0. We then have the following:
Theorem 1. Zhao 2019 Thm 3. 14) If an arm is indexable, then, for every state 8, D&(A) 2 0 if and only if x- < ((s).
Mora 2007) described generic approach for finding the Whittle index. The complexity of this approach is least exponential the number of states.
3

---

Under review as a conference paper at ICLR 2021
Our NeurWIN uses Thm. 1 to train neural networks that predict the Whittle index for any indexable arms. From Def. [ sufficient condition for indexability is when D2 is 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 Dx is strictly decreasing in forr every state
3.3 PROBLEM STATEMENT
We now formally describe the objective this paper. We assume that we are given a simulator of single restless arm black box. The simulator provides two functionalities: First, it allows us to set the initial state of the arm to any arbitrary state s. Second, in each round I, the simulator takes alt), the indicator function that the arm is activated, the input and produces the next state s(L + 1] and the reward r(t] as the outputs.
Our goal is to derive low-complexity index algorithms for restless bandit problems by training neural network that approximates the Whittle index of each restless arm using its simulator. A neural network takes the state the input and produces a real number fo(s) the output, where is the vector containing all weights and biases of the neural network. Recall that W(s) (s) is the Whittle index of the arm. We aim find appropriate 0 that makes (.f((s) (s) small for all s. Such neural network is said to be Whittle-acuurate.
Definition 4 WWhitlee-ccuurate A neural network with parameters 0 is said to be x 7-Whittl- accurate if fo(s) - (s)) & for all s.
NEURWIN ALGORITHM: NEURAL WHITTLE INDEX NETWORK
In this section, we present NeurWIN, deep-RL algorithms 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 trains the Whittle index for one single arm.
4.1 CONDITIONS WHITTLE-ACCURATI
An arm with activation cost
NeNrWIN
r(1] Aaet
fo(s(A))
r|d
Arm
aft] = 1(fa(t
s +
Figure 1: An illustrative motivation of NeurWIN.
Before presenting NeurWIN, we first discuss the conditions for a neural network to be --Whittle- accurate.
Suppose we are given 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 fe fe(s(t) as the input. The input is first fed into step function to produce aft] = 1 (f(() 2 A). 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 sit + 1]. We call this environment Env(A). Thus, the neural network can be viewed as a controller for Env(A). The following corollary is a direct result from Thm.
4

---

Under review as a conference paper at ICLR 2021
Corollary 1. If fo(s) W(s), Vs. then the neural network with parameters 8 is the optimal con- toller for (n for any and initial state s(1]. Moreover given X and s(1}, the optimal dis- counted net reward is max x (s(()) (s())s)
Corollary ! can be viewed Below, we establish a sufficient condition for W-Wittle-accurase
necessary condition for neural network to be O-Whitle-accurate.
Theorem 2. If the arm is strongly indexable, then for any & > and an arbitrarily small positive constant 8, there exists positive such that the following statement holds: for any states so, $1 and any activation cost À E [So) - 8, fo(so) + 6), the discounted net reward of applying neural network to Enx(A) with initial state is at least max ax (51), Qx.pasa(51) (1))]{e then the neural network is 7-Whitle--ccuurate
Proof. For given % let e min, { (m))( (s))ss (w(s)) (s), (arr (s)) Since the arm is strongly indexable and ((s) its Whittle index, have <> 0.
We prove the theorem by establishing the following equivalent statement: If the neural network is not 2-Whitle-accurrate then there exists states 80, $1, activation cost À E [fo()0) - 6, fe + such that the discounted net reward of applying neural network to Env(A) with initial state 81 strictly less than max m ax ($1),
c.
Suppose the neural network is not 7 --Whttle-accuratte then there exists a state s' such that (ff( W W(s') > y. We set so = $1 = s'. For the case fe(s') > (s') + 7, we set A = fe(s') + 6. Qx.pass(ss))
Since > (s') + % we have Qx.act (s') 2 2c. On the other hand, since fo(s') > X, the neural network would activate the arm in the first round and its discounted reward is at most
(a.pass(s)) and Qx.pass
Qx (s') < Qx.paee
2E < max (xxcc(())ss))) D, 2x.pass
For the case fo(s') < (s')) -n, a similar argument shows that the discounted reward for the neural network when Ả= fo(s') -8 8 is smaller than max max{Q (s'), Qxpass (s')} e. This completes the proof.
4.2 TRAINING PROCEDURES FOR NEURWIN
Thm. Stttaes that a neural network that yields near-optimal net reward for any environments Env(AA also Whittle-accraat. This observation motivates the usage of deep reinforcement learning to find Whittle-accurate neural networks. To make the output of the environments differentiable with respect to the input (s()), we replace the step function Fig. I with sigmoid function a (fo(((()) - X) == (1 + erp( - mmfomm - A))) where m is a sensitivity parameter. The environment then chooses a[t]
with probability om (f)() A)) and alt] 0 with probability 1 (fo(s(t)))))) A). We call this differentiable environment (A).
Our training procedure consists of multiple mini-batches, where each mini- is composed of fixed number of episodes. At the beginning of each mini-batch, we randomly select two states so and 81. Motivated by the condition in Thm. we consider the environment Env"" (fa (fa(so) with initial state 81 and aim to improve the empirical discounted net reward of applying the neural network to such environment.
Our approach is based on the REINFORCE algorithm (Williams) 1992). each episode e, we set X fa(So) and initial state to be 81. We then apply the neural network with parameters 0 to (A) and observe the sequences of actions (a[1], af2)....) .) and states ([[]),
We can use these sequences to calculate their gradients with respect to through backward propagation, which we denote by he. We also observe the discounted net reward and denote it by G.. After all episodes the mini-batch finish, we calculate the average of all Ge as a bootstrapped baseline and denote it by Gb. Finally, we do weighted gradient ascent with the weight for episode being its offset net reward, G. - G.. When the step size is chosen appropriately, the neural network will be more likely to follow the sequences of actions of episodes with larger Ge after the weighted gradient ascent, and thus will have a better empirical discounted net reward. The complete algorithm is described in Alg. 0
5

---

Under review as a conference paper at ICLR 2021
Obviously, the choice of Su and can have significant impact the convergence speed of Alg. In our implementation, we choose &y uniformly at random each mini-batch. The choice of 81 de- pends the bandit problems. Some bandit problems naturally visit certain states far less frequently than other states. For such problems, we choose 81 to be those ees-frequently-visited states with higher probabilities,
to ensure that Alg. [ able to learn the optimal control for these states. For other problems, we simply choose 51
Algorithm 1: NeurWIN Training
Input: Parameters 0, discount factor / E (0, 1), learning rate I., sigmoid parameter m Output: Trained neural network parameters #+
for each mini-batch do
Randomly choose 8o and 81, and set À for each episode in the mini-batch do
fa(s))
Set the arm to state $1, and set he t- 0:
for each round t in the episode do
Choose a = w.p. am (So(s(t)) - X), and a(t) = w.p. - (mo((()(() - A):
if [t) 1 then
he t he + Ve Le (ft(s)t) A)):
else
he - he + Vo In(1 om (fo() A))
end
end
Ge + empirical discounted net reward in episode
end
L learning rate in mini-batch b;
G the average of G. for all episodes in the mini-batch;
Update parameters through gradient ascent 0 0 I, E. LG. Gb)he:
end
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, 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, 1), (100, 10), and (100, 25), and average the results of 200 independent runs when the problems are stochastic. Some applications consider that different arms can have different behaviors. For such scenarios, we consider that there multiple types of arms and train 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 NeurWIN is compared against the proposed policies in the respective recent studies. In addition. we also implement and evaluate the REINFORCE algorithm (Williams 1992) and the QWIC algorithm (Fu et al.) 2019). The REINFORCE algorithm aims to find the optimal control by viewing a 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 (M) Thus, we are only able to evaluate REINFORCE for the case N = 4 and M = 1. The QWIC algorithm aims to find
the Whittle index through Q-learning. It is a tabular method and does not scale well as the state space increases. Thus, we only evaluate QWIC when the size of the state space is small.
We use the same neural network architecture for NeurWIN all three applications. The neural network is 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 the dimension of the state of one single arm. As for the REINFORCE algorithm, we choose the neural network architecture so that the total number of parameters is slightly more than N times the number of parameters in NeurWIh make fair

---

Under review as a conference paper at ICLR 2021
comparison. ReLU activation function is used for the two hidden layers. An initial learning rate = 0.001 is set for all cases, with the Adam optimizer (Kingma & Ba 2015) employed for the gradient ascent step. The discount factor is 3 0.999 and each mini-batch consists of five episodes.
For all cases, we implement the NeurWIN algorithm using Py Torch (Paszke et al. 2019). and train the agent a single arm modelled after OpenAl's Gym API (Brockman et al. 2016). We provide a brief overview of each application and the experiment setting in the following sections. We refer readers to the appendices for detailed discussions on experiment settings.
5.2 RECOVERING BANDITS
The recovering bandits Pike-Burke & Grunewalder 2019) aim to model the time-varying behaviors of consumers. In particular, it considers that a consumer who has just bought a certain product, say, a television, would be much less interested in advertisements of the same product in the near future. However, the consumer's interest these advertisements may recover over time. Thus, the recovering bandit models the reward of playing arm, i.e., displaying function [min 2; Zmaz)), }), where z the time since the arm was last played and Emer a constant specified by the arm. There is no known Whittle index optimal control policy for this problem.
advertisement, by
The recent study (Pike-Burke & Grunewalder 2019) on recovering bandit focuses on learning the function f() for each arm. Once it obtains estimate of f(-), it uses a heuristic called d-lookahead to determine which arms to play. The d-lookahead policy enumerates all possible actions in the next d rounds, and then pick the sequence of actions that yield that highest reward. Since the controller can choose M arms out of N arms activate, with (M) different possibilities, in each round, the
complexity of the heuristic ((()) () when d Thus, we are only able to evaluate 1-lookahead when N = 100. When N = 4 and M = 1, we evaluate 1-lookahead and 3-lookahead.
In our experiment, we consider that there are four types of arms and there are arms for each type. Different types of arms have different functions f-)). The state of each arm is its value of min(2, 2maa] and we set 2maz 20 for all arms.
Experiment results are shown in Fig. 2 It can be observed that NeurWIN is able to outperform 1-lookahead all settings with just few thousands of training episodes. In contrast, for the case N 4 and M = 1, REINFORCE only sees slight performance improvement over 50,000 training episodes and remains far worse than NeurWIN. This may be due to the explosion of state space. Even though N is only 4, the total number of possible states is 20 160, 000, making it difficult for REINFORCE to learn the optimal control in just 50, 000 episodes. In contrast, since NeurWIN learns the Whittle index of each separately, its size of state space is only 20. QWIC performs poorly. This suggests that it does not learn good approximation to the Whittle index.
Total Discounted Rewards
Total Da Devromm Bownrds
Diceuuntd S P (aa
NeurWIN
OMNC
REINFORCE
NeurWiN
NeurW!N
L-Loova head
Lookaheead
Loolahead
Number of Training Epsodes
Number Training Episodes
Number of Training Episades
(a) N - M
(b) N 100. M 10.
(c) N 100. M 25.
Figure 2: Experiment results for the recovering bandits.
5.3 WIRELESS SCHEDULING
A recent paper (Aalto et al. 2015) 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 suffers from a holding cost of unit per round until has finished transmitting all its data. The channel quality of wireless client, which determines the amount of data can be
7

---

Under review as a conference paper at ICLR 2021
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, we view the reward of the system as the negative of the total holding cost.
Finding the Whittle index through theoretical analysis is difficult. Even for the simplified case when the channel quality is i.idd over time and can only be in of two possible states, the recent paper (Aalto et al. 2 can only derive the Whittle index under some approximations. It then proposes size-aware index policy using its approximated index.
In the experiment, we adopt the settings of channel qualities of the recent paper. The channel of a wireless client can be in either good state or bad state. The amount of data that can be transmitted in round is 2..6kb in a good state, and 8, 8.4kb in a bad state. Initially, the amount of load is uniformly 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. We train a NeurWIN for each type. During testing, there are zzz arms of each type.
Experiment results are shown in Fig- 3 It can be observed that WeurWIN able to outperform the size-aware index policy with about 100, 000 training episodes. This result is significant when one considers the fact that the size-aware index is itself an approximation to the Whittle index. The experiment results thus suggest that NeurWIN is able to find more accurate approximation to the Whittle index than the best known theoretical result. can also be observed that REINFORCE performs poorly.
Totnl Discoutted Rerwerts "aa""
Tool Diccountes und Frewards
Total Discounted Revwards -00
NeurWIN
REINFORCE
NeurWiN
NeurWiN
Size eware Index
Sice aware Index
Size smare index
57
15
Number of Training Episodes
Number Training Episodes
Number of Training Episodes
(a) N = 4. =
(b) N
100. M 10.
(c) N 100. M 25.
Figure 3: Average rewards and confidence bounds of different policies for wireless scheduling.
5.4 DEADLINE SCHEDULING
A recent study (Yu et al. 2018) proposes deadline scheduling problem for the scheduling of elec- trical vehicle charging stations. In this problem, a charging station has N charging spots and enough power charge M vehicles in each round. When charging spot is available, new vehicle may join the system and occupy the spot. Upon occupying the spot, the vehicle announces the time that it will leave the station and the amount of electricity that it needs to be charged. The charging station obtains reward for each unit of electricity that it provides to vehicle. However, if the station cannot fully charge the vehicle by the time it leaves, then the station needs to pay a penalty. 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. Under an i.i.d. arrival assumption, the recent study has derived the precise characterization of the Whittle index, which we refer to as the deadline Whittle index. We further prove that this problem is strongly indexable in the appendix.
We use exactly the same setting in the recent study YYu et al. 2018) for experiment. In this problem, the state of an arm is denoted by a pair of integers (D, B). where B the amount of electricity that the vehicle still needs and D is the time until the vehicle leaves the station. When charging spot is available, its state is (0, 0). B is upper-boundee by and is upper-boundedt by 12. Hence, the size of state space is 109 for each arm.
The experiment results are shown in Fig. It can be observed that the performance of NeurWIN converges to that of the deadline Whittle index in less than 500 training episodes.
8

---

Under review as a conference paper at ICLR 2021
cabecourten Reowards ou
Tonal Disc aopcouuttn roo Rowards -May. -Ray
Total Disc roscouurie uoed Reward. Ri
Total Disc
ReeWW
QUBC
BeurWW
Number of Training Epbodes
Number Training Epiocies
Number of Training Ephodes
(a) M
(b)
100. M
(c) 100. 25.
Figure 4: Average rewards and confidence bounds of different policies for deadline scheduling.
5.5 EXPERIMENT RESULTS WITH NOISY SIMULATORS
The training of NeurWIN requires a simulator for each arm. In this section, we evaluate the performance of NeurWIN when the simulator is not perfectly precise. In particular, let Racr (s) and Rpass(s) be the rewards of an arm in state when tively. Then, the simulator estimates that the rewards are (s) Ry (s) (1 + Rs. Re.ppss(s)) respectively, where Gact,s and G Gasss. are independent Gaus- sian random variables with mean O and variance 0.05. In other words, the simulator has an average 5% error in reward estimation.
activated and not activated, respec-
(1 + Gact,s) (act and
We train Neur WIN using the noisy simulators for the recovering bandits problem and the deadline scheduling problem. For each problem, we compare the performance of NeurWIN against the re- spective baseline policies. Unlike NeurWIN, the baseline policies make decisions based on the true reward functions rather than the estimated ones. The results for the case = 100 and M = 25 are shown in Fig. 5 It can be observed that NeurWIN is still able to achieve superior performance.
Total Dicouun Roure
Total Dicouuted Bewranss
Total Discourted Rewards
NeurWiN 1-Lookahead
NeurWiN
NeurMNN
Sice awere Index
Deadline Whittle index
Number of Training Episodes
Number Training Episodes
Number of Training Episodes (c) Deadline Scheduling.
Recovering Bandits.
Wireless Scheduling.
Figure 5: Experiment results for NeurWIN with noisy simulators.
CONCLUSION
This paper introduced NeurWIN: deep RL method for estimating the Whittle index for restless bandit problems. The performance of NeurWIN is evaluated by three different restless bandit prob- lems. In each of them, NeurWIN significantly outperforms state-of-the-a control policies in terms of the total discounted reward.
NeurWIN have important implications for restless bandit problems. There many problems where the environments are well-defined, but the optimal control is not known. NeurWIN can obviously be used for such problems. For problems where the environments are not known a priori, Neur nicely compliments existing studies that aim to learn the environments through online learning but fail to find the optimal control policy.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Samuli Aalto, Pasi Lassila, and Prajwal Osti. Whittle index approach to size-aware scheduling with time-varying channels. Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 57-69, 2015.
K. Avrachenkov and V. S. Borkar. A learning algorithm for the whittle index policy for schedul- ing web crawlers. In 2019 57th Anmual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1001-1006, 2019.
V.S. Borkar and K. Chadha. reinforcement learning algorithm for restless bandits. In 2018 Indian Control Conference (ICC), pp. 89-94, 2018.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 160iv:1606.00 2016.
Christopher R Dance and Tomi Silander. When are kalman-filter restless bandits index- able? In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems 28, pp- 1711-1719. Curran Associates, Inc., 2015. URL
when are kalman- filter-
testless Sandits--nddxablles
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, pp. 5717-5727, Red Hook, NY, USA, 2017.
Curran Associates Inc. ISBN 9781510860969
J. Fu, Y. Nazarathy, S. Moka, and G. Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian New Zealand Control Conference (ANZCC), pp. 249-254, 2019.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low Bellman rank are PAC-learnable. volume 70 of Proceed- ings of Machine Learning Research, pp. 1704-1713, International Convention Centre, Syd- ney, Australia, 06-11 Aug 2017. PMLR. URL http: http:://pooeednngg.....eesssss/s jiang cc.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
J. Le Ny, M. Dahlch, and E. Feron. Multi-uav dynamic routing with partial observations using restless bandit allocation indices. In 2008 American Control Conference, pp. 4220-4222 2008.
Alex S. Leong, Arunselvan Ramaswamy, Daniel E. Quevedo, Holger Karl, and Ling Shi. Deep reinforcement learning for wireless sensor scheduling in cyber-physicat sys- tems. Automatica, 1 113:10875,, 2020. ISSN 0000--1088.
doi: https://doi.org/ ence/
10. 10.1016/j.uutomatiia 108759. URL http//ittt::/wwwwceenneee www.:eenoncrre..ooooooe.o rect.com 09810000000001110000000 6206
R. Meshram, D. Manjunath, and A. Gopalan. On the whittle index for restless multiarmed hidden markov bandits. IEEE Transactions on Automatic Control, 63(9):304633053, 2018.
José Niño-Mora. Dynamic priority allocation via restless bandit marginal productivity indices. Top, 15(2):161-198, 2007.
Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293-355, 1999. ISSN 0364765X, 15265471.
URL
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, perf-peeformance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox,
10

---

Under review as a conference paper at ICLR 2021
and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8026-8037. Curran Associates, Inc.. 2019. httpt//ttt///eeaaaaaaaaaaa//aaaa
an-
Ciara Pike-Burke and Steffen Grunewalder. Recovering bandits. In Advances in Neural Information Processing Systems, pp. 14122-14131, 2019.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empir- ical comparison of bayesian deep networks for thompson sampling. International Conference Learning Representations (ICLR), 2018.
SyYe6k-CC
Julien Seznec, Pierre Menard, Alessandro Lazaric, and Michal Valko. A single algorithm for both restless and rested rotting bandits. In International Conference Artificial Intelligence and Statistics, pp. 3784-3794, 2020.
Aleksandrs Slivkins and Eli Upfal. Adapting to a changing environment: the brownian restless 2008.
bandits. In COLT, pp.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http:://acccm.eeeeeaaaaaeeto/o/a 2nd.html
V. Tripathi and E. Modiano. A whittle index approach to minimizing functions of age of information. In 20/9 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1160-1167, 2019.
S. Wang. H. Liu, P. H. Gomes, and B. Krishnamachari. Deep reinforcement learning for dynamic multichannel access wireless networks. IEEE Transactions on Cognitive Communications and Networking, 4(2):257-22) 2018.
T. Wei, Yanzhi Wang, and Q. Zhu. Deep reinforcement learning for building hvac control. In 2017 54th ACM/EDAC/EEE Design Automation Conference (DAC), pp. 1-6, 2017.
Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied proba- bility, pp. 287-298, 1988.
Ronald J. Williams. Simple statistical fradient-following algorithms for connectionist reinforce- ment learning. Mach. Learn., 8(3 8(3-4))229-256 May 1992. ISSN 0885-6125. doi: 10. BF00992696. URL |tt:::://00.0rg/100100000/ BCC02//60OC099666
Huizhen Yu and Dimitri P Bertsekas. Convergence results for some temporal difference methods based least squares. IEEE Transactions on Automatic Control, 54(7):1515-1531 2009.
Z. Yu, Y. Xu, and I.. Tong. Deadline scheduling restless bandits. IEEE Transactions on Automatic Control, 63(8):2343-2358, 2018.
Andrea Zanette and Emma Brunskill. Problem dependent reinforcement learning bounds which can identify bandit structure MDPs. volume of Proceedings of Machine Leurning Research, pp. 5747-5755, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL.htp::
//proceedings.mllpppeee.... v80 http://nnnttee8aaattaat.
Qing Zhao. Multi-armed bandits: Theory and applications to online learning in networks. Synthesis Lectures on Communication Networks, 12(1):1-165, 2019.

---

Under review as a conference paper at ICLR 2021
A RECOVERING BANDITS' TRAINING AND INFERENCE DETAILS
A.1 FORMULATED RESTLESS BANDIT FOR THE RECOVERING BANDITS' CASE
We list here the terms that describes one restless arm in the recovering bandits' case:
State s(t]: The state is a single value s|{] =[4] called the waiting time. The waiting time z|[] indicates the time since the arm was last played. The arm state space determined by the maximum allowed waiting time 2maz, giving state space S := [1, Zmaz].
Action att]: As with all other considered cases, the agent can either activate the arm aft) 1, or not select it a [t] = 0. The action space is then A := {0. 1).
Reward rtt] The reward is provided by the recovering function f(=(t),, where 2|t] is the time since the arm was last played at time t. If the arm is activated, the function value at 2 is the earned reward. reward of zero given if the arm is left passive a[4] = 0. Figure 6 shows the four recovering functions used in this work. The recovering functions are generated from,
f(z(t) 0o(1 -e -000=))))
Where the θ = 180, 01] values specify the recovering function. The θ values for each class are given table
Table I: θ values used in the recovering bandits' case
Class
Og
Value
01
Value
10
0.2
B
8.5
0.4
C
7
0.6
5.5
0.8
Next state sit + 1]: The state evolves based on the selected action. If a(t) = 1, the state is reset to s[t + 1] = meaning that bandit's 's reward decayed to the initial waiting time 2(t + 1. If the arm is left passive a[t] 0, the next state becomes a|{ + I] min{=[[] + 1, Zmaar }.
10
9-
8
7
f(z)
5
Recovering function A
Recovering function B
Recovering function C
Recovering function D
2
3
4
5
8 9 10 11 12
13 14 15 16 17 18 19 20
Z
E {1, Zmax]
Figure 6: The selected recovering functions for the recovering bandits' case. For testing, we set each quarter of the instantiated arms to one of the shown f(z) functions.
12

---

Under review as a conference paper at ICLR 2021
A.2 TRAINING SETTING
The general training procedure for the NeurWIN algorithm is outlined in its pseudo code in section Here we discuss the parameter selection and details specific to the recovering bandits' case. We train the neural network using NeurWIN for 50, 000 episode, and save the trained parameters at an episode interval of 100 episodes. The purpose of saving the parameters is to infer their control policies, and compare it with the 1-lookahead policy. In total, for 50, 000 training episodes, we end up with 500 models for inference. The selected neural network has 609 trainable parameters given as {1, 16, 32, 1) layer neurons.
For training parameters, we select the sigmoid value m = 5, the episode's time horizon = 100 timesteps, the mini-batch size to episodes, and the discount factor 3 0.999. As with all other cases, each mini-batch of episodes has the same initial state s(t = 1] which is provided by the arm. To ensure the agent experiences as many states in [1, Zmazl possible, we set initial state 2
sampling distribution given Pr[s[t 1] 2} 22422 25mam Hence, the probability of selecting the initial state be s(l 1] Zmar is 0.5. This initialization distribution allows the agent to experience the recovery function's 's awards at higher values.
At the agent side, we set the activation cost À at the beginning of each mini-batch. À is chosen be the estimate index value fo(s) ) of randomly selected state in s E [1, Zmaz]. The training continues as described in NeurWIN's pseudo code: the agent receives the state, and selects an action alt. If the agent activates the arm all = 1, it receives a reward equal to the recovery function's 's value at 2, and subtracts À from it. Otherwise, the reward r(t] is kept the same for a(t) O. We note that no noise was added with the clean simulator, and the agent discounts the original reward
value rtr(t] = 3 f=(tt). The process continues for all timesteps in the episode up to T = 100, and for remaining mini-batch episodes. A gradient ascent step is taken on the bootstrapped mini-bate return described in section
A.3 INFERENCE SETTING
The inference setup measures NeurWIN's control policy for several (M) settings. We test, for a single run, the control policies of NeurWIN and I-lookahead over a time horizon T = 3000 timesteps. We set N arms such that quarter have recovering function class from table I For example, when N = 100, 25 arms would have recovering function A that generates their rewards.
At each timestep, the I-lookahead policy ranks the recovering functions reward values, and selects the M arms with the highest reward values for activation. The incurred discounted reward at time t is the discounted sum of all activated arms' rewards. The total discounted reward is then the discounted rewards over time horizon = 3000. For inferring NeurWIN's control policy, we record the total discounted reward for each of the 500 models. An example testing procedure is as follows: we instantiate N arms each having a neural network trained to 10, 000 episodes. At each timestep 4, the neural networks provide the estimated index (s,e(s((t) for 1,2,..... ... .N. The control policy activates the M arms with the highest index values. The incurred discounted reward at time is the discounted sum of all activated arm's 's rewards 3² Ri[t] 3 "n- f=([t)). The same process continues for all timesteps in the horizon T = 3000. We then load the model parameters trained on 10, 100 episodes, and repeat the aforementioned testing process using the same seed values.
A.4 REINFORCE TRAINING AND INFERENCE SETTING ON RECOVERING BANDITS
The REINFORCE algorithm was applied only the (M) case where N 4, and M For training, REINFORCE had four arms each with one of the recovery functions detailed in table The training parameters are: initial learning rate I. = 0.001, mini-batch size episodes, and training episode time horizon T = 100 timesteps. Training was done up to 50, 000 episodes, where the trained parameters were saved at an interval of 100 episodes. The selected neural network had
2504 trainable parameters. This neural network size is larger than 609 x 2436 parameters of four WeNrWIN neural networks.
For testing, the same procedure is followed as in A.3 The trained REINFORCE models were loaded, and each tested the same arms NeurWIN and deadline Whittle index policies. The testing was
13

---

Under review as a conference paper at ICLR 2021
made for all 500 trained model (each being trained up to different episode count). The final control policy result was plotted along with NeurWIN and the 1-lookahead policies for (9) arms.
A.5 QWIC TRAINING AND INFERENCE SETTING ON RECOVERING BANDITS
The Q-learning Whittle Index Controller (QWIC) pseudo-code is given in (Fu et al. 2019 QWIC was trained in an offline setting using fixed N restless arms with M activations (i.e. (1) T 1100)
25 )
QWIC selects from set of candidate threshold values À E A index for each state. The algorithm
learns function Q E RAAXS((01), The estimated index X(s) per state is determined during training as,
{[s] = arg min IQ(A, 8, s(,,
Hence, the converged index values and control performance depends on the initial set of candidate values A. We select A be 100 values evenly spaced in the interval [0, 10). We note the selection was based on Neur WIN's learned index values, which provides an advantage to QWIC training.
The exploration-exploottion trade-off is steered by parameter 6. is initialized emar and decays with factor a = 0.01 to Emin = 0.01. é is updated at each timestep during training until it settles Emin.
Other training parameters were selected as: initial learning rate L = 0.001, training episode time horizon of 100 timesteps, discount factor episodes, where the Q-learned indices A were saved at an interval of 100 episodes.
0.999, Training was done up 50, 000
For testing, we use the same testing setting as in NeurWIN and REINFORCE. The learned indices are loaded for each training interval. In total, 500 estimated index mappings were tested for 200 independent runs, each trained up to certain episode limit.
B WIRELESS SCHEDULING TRAINING AND INFERENCE DETAILS
B. RESTLESS ARM DEFINITION FOR THE WIRELESS SCHEDULING CASE
As with the recovering bandits' case, we first list the state s(t]. action alt). reward r(t], and next state s|t + 1] that forms one restless arm:
State a[t]: The state is a vector (w[t), v(()), where y[t] is the arm's remaining load in bits, and v((] is the wireless channel's is state indicator. v it means good channel state and higher transmission rate 72, while v[t] = 0 is a bad channel state with a lower transmission rate F1.
Action att]: The agent either activates the arm att] = 1, or keeps it passive a(t) = 0. The reward and next state depend the chosen action.
Reward r(t]: The arm's reward is the negative of holding cost v. which is cost incurred each timestep for not completing the job. If the selected action all] = 1, then the reward at time is r(t] + x. Otherwise, reward is just r[t] u/
Next state s|t 1]: The next state evolves differently as given below,
(vlt) r2, 1)
if (u(()) 1, aat]
s|( + 1]
(vit) -r,
if q(u(t) - 0. alt] -
(3)
(vlt), ((((t))
otherwise
Where q(v(()) is the probability of a good channel state.
14

---

Under review as a conference paper at ICLR 2021
B.2
TRAINING SETTING
We again emphasize that NeurWIN training happens only on one restless arm. The general training procedure described in NeurWIN's pseudo code. This discussion pertains only to the wireless scheduling case.
The neural network has 625 trainable parameters given as {2, 16, 32, 1} neuron layers. The training happens for 1, 000, 000 episodes, and we save the model parameters at each 1000 episodes. Hence, the training results in 1000 models trained up to different episode limit.
For the wireless scheduling case, we set the sigmoid value m = 0.01, mini-batch size to 5 episodes, and the discount factor to 0.999. Episode time horizon dependent on the remaining job size y[t]. The episode terminates either if y(t] 0 or = 3000. The holding cost is set to = 1, which is incurred for each timestep the job is not completed. We also set the good transmission rate r2 33.6 kb, and the bad channel transmission rate = 8.4 kb. During training, the good channel probability g(o(t)) = 0.5.
The episode defines one job size sampled uniformly from the range ylt episodes one mini-batch have the same initial state, as well as the same sequence of good channel states [u[t 1], vft = 2)....., oft T]]-
(0, Mb). All
At the agent side, NeurWIN receives the initial state s[t = 1]. and sets the activation cost = fo(s(t IJ) for all timesteps of all mini-batch episodes. As mentioned before, save the trained model at an interval of 1000 episodes. For 1, 000, 000 episodes, this results in 1000 models trained up to their respective episode limit.
B.3 INFERENCE SETTING
For testing, the aim is to measure the trained models' control performance against the size-aware index. We instantiate N arms and activate M arms each timestep t until all users' jobs terminate. We average the total discounted reward for all control policies over 200 independent inference runs. Half of the arms have good channel probability q(((t) 0.75. The other half has good channel probability q(((t)) = 0.1.
We compare NeurWIN's control policy at different training episodes' limits with the size-aware index policy. The size-aware index is defined as follows: at each timestep. the policy prioritizes arms in the good channel state, and calculates their secondary index. The secondary index 0g of arm i state (ys [4), (t)) is defined as,
Grr,2 [t
i (y vx(t)
(4)
The size-aware policy then activates the highest M indexed arms. In case the number of good channel arms is below M, the policy also calculate the primary index of all remaining arms. The primary index vú of arm state (yx [4), M: [t] is defined as,
(u us vx(()) = qi (rie(rr)))))) -
G
(5)
Rewards received from all arms are summed, and discounted using 3 0.999. The inference phase proceeds until all jobs have been completed.
For NeurWIN's control policy, we record the total discounted reward for the offline-trained models. For example, we set N arms each coupled with model trained on 10, 000 episodes. The models output their arms' indices, and the top M indexed arms are activated. In case the remaining arms are less than M, we activate all remaining arms timestep l. timestep reward R(((1 = G ΣN r(4 is the sum of all arms' rewards. Once testing for the current model is finished, we load the next model 11, 000 for each arm, and repeat the process. We note that the arms' initial loads are the same across runs, and that the sequence of good channel states is random.
B.4 REINFORCE TRAINING AND INFERENCE SETTING ON WIRELESS SCHEDULING
The REINFORCE algorithm was applied only the (1) case. The four arms have the same training setting described in section B.2 The training parameters are: initial learning rate I. 0.001,
15

---

Under review as a conference paper at ICLR 2021
mini-batch size is episodes, and good channel probability for all four arms (uftt) = 0.5. The episode time horizon has a hard limit of = 3000 timesteps. However, an episode can termi- nate all arms' loads were fully processed (i.e. Σi=1 Vi [) = 0). Training was done up to 100, 000 episodes, where the trained parameters were saved an interval of 1000 episodes. The selected neu- ral network had 2532 trainable parameters so to have slightly more parameters than four NeurWIN neural networks.
For testing, the same procedure is followed as in B.3 The trained REINFORCE models were loaded, and each tested on the same arms NeurWIN and size-aware index. The final control policy result was plotted along with WeurWIN and Whittle index policy for the (1) testing setup.
C DEADLINE SCHEDULING TRAINING AND INFERENCE DETAILS
C.I FORMULATED RESTLESS BANDIT FOR THE DEADLINE SCHEDULING CASE
The state s(t], action a[t], reward r[d], and next state s|t + 1] of one arm are listed below:
State s[[]: The state is vector (D, B). B denotes the job size (i.e. amount of electricity needed for an electric vehicle), and D is the job's time until the hard drop deadline is reached (i.e. time until an electric vehicle leaves).
Action att]: The agent can either activate the arm att] = 1, or leave it passive a(t] = 0. The next state changes based on different transition kernels depending on the selected action. The reward is also dependent on the action at time t.
Reward r|t]: The agent, at time receives reward r[t] from the arm,
(1 c)a(d]
if B[d > 0, D > 1
r[t] =
(1 c)ald] - F(B a(t)) if B > 0, D[[ =
(6)
otherwise
Where is constant processing cost incurred when activating the arm, F(B - aft)) the penalty function for failing to complete the job before D 1. The penalty function was chosen to be F(B - al{)) = (.) - -[())²
Next state s(4 1): The next state D[L + 1] decreases by one, while the job size B depends on the selected action as,
(Dlt) B[t aatt)
if D
sst +1+
(D. B) with prob. Q)
if D <
Where Q(D, B) is the arrival probability of a new job (i.e. new electric vehicle arriving at charging station) if the position empty. For training and inference, we set QDD, B) = 0.7.
C.2 STRONG INDEXABILITY PROOF FOR THE DEADLINE SCHEDULING CASE
It has been shown that the Whittle index for this problem is.
if B
if f
wDD B) =
(8)
BD D (D +1
if B
We further demonstrate that this problem is strongly indexable.
16

---

Under review as a conference paper at ICLR 2021
Theorem 3. The restless bandit for the deadline scheduling problem is strongly indexable.
Proof. Fix a state - (D, the function (A) :- (Qx.ac))--QA -(ls)-Qxpppp -xsppss is continuous and piece-wiss linear function since the number of states finite. Thus, it sufficient to prove that (A) is strictly decreasing at all points of À where (A) is differentiable. Let (s) be the sequence of actions taken by a policy that activates the arm at round I, and then uses the optimal policy starting from round 2. Let paspsss(s) (s) be the sequence of actions taken by policy that does not activate the arm at round 1, and then uses the optimal policy starting from round 2. We prove this theorem by comparing Lx,ac( (s) and L pasee (s) on every sample path. We consider the following two scenarios:
In the first scenario, (s) and Lx.pasa(s) (s) are the same starting from round 2. Let b be the remaining job size when the current deadline expires under (s). Since Lx.pase is the same as (8) starting from round 2, its remaining job size when the current deadline expires is b + 1.
Thus, (A) 1 c + 3D (F(( + 1) F(b)). which is strictly decreasing in À whenever (A(A) is differentiable.
In the second scenario, axc (s) and Lx.pass (s) are not the same after round 2. Let be the first time after round 2 that they are different. Since they are the same between round 2 and round t, the remaining job size under (s) is no larger than that under (x..pss(s) Moreover, the Whitrle index is increasing in job size. Hence, we can conclude that, on round т. Ixppass(8) activates the arm and Lx does not activate the arm. After round т, Lx (s) and Lx,pass (s) are in the same state and will choose the same actions for all following rounds. Thus, the two sequences only see different rewards on round and round т, and we have (A = (1 - c- -2)(1 - 101---1-1 3r-1), which strictly decreasing in Ả whenever (x is differentiable.
Combining the two scenarios, the proof is complete.
C.3 TRAINING SETTING
WeurWIN training is made for 1000 episodes on the deadline scheduling case. We save the trained model parameters at an interval of 5 episodes for inferring the control policy after training. Hence, the training produces 200 different set of parameters that output the estimated index given their respective training limit. The neural network had 625 trainable parameters given as {2, 16, 32, 1), where the input layer matches the state size.
For the deadline scheduling training, we set the sigmoid value m 1, episode's ' time horizon T = 3000 timesteps, mini-batch size to 5 episodes, and the discount factor 3 = 0.999. The processing cost = 0.5, with the job arrival rate QDD, from the main text. The arm randomly picks an initial state s[t 1| (D, B), with a maximum D = 12, and maximum B- 9. The arm fixes the initial states across episodes in the same mini- batch for proper return comparison. The sequence of job arrivals in an episode's horizon is also fixed across a mini-batch. For example, one episode in mini-batch 1 would have the sequence 5), (6, 2), (8, 4), , (3, 5)], then all other episodes in the same mini-batch would pass the same sequence. This way, the actions taken by the agent would be the critical factor in comparing a mini-batch return, and ultimately in tuning the estimated index value f-(-).
0.7. Training procedure follows section 4.2
At the agent side, WeN receives the initial state s[1 = 1]. sets the activation cost À = [o(t = 1)). This activation cost À selection method hence depends on the current network parameters 0, which are modified after every gradient ascent step. Training follows as described in NeurWIN's pseudo code.
In figure 7 we plot the trained NeurWIN index for all possible state enumerations of B = 9 and D (1, 2,3). The output index from the untrained neural network is also plotted for convergence comparison.
In figure & the trained restless bandit indices for noisy reward function is given. All possible states in B for D E {1, 2, 3). For (0,, 0.05) added noise per timestep, the learned indices still match the state ordering found when trained with the true reward function.
17

---

Under review as a conference paper at ICLR 2021
Trained Trained fpioode::
Trained Trained fpaodde::
Trained
Trained fpioode::
Dosdine Whitte Index
Indox value
Deadline Whittle Index
Desdine Whittle Index
Load size
Losd siee
Load sire
Deadline
(b) Deadline
(c) Deadline
Figure 7: Trained indices using the true reward function.
Trained Epiodes: 0
Trained Epiiades: 0
Trained Epiodes: 0
Trained Epteades:
Trained Epoodes: 1000 Index
Trained Eptsades: 1000
Indox Value
(a) Deadline D= 1.
(b) Deadline D = 2.
(c) Deadline D= 3.
Figure 8: Trained indices using the noisy reward function.
C.4 INFERENCE SETTING
order to infer the resultant control policy, we are required to test the performance on models saved different episodes' intervals. In other words, the trained models' parameters tested an interval of episodes, and their discounted rewards are plotted for comparison.
From the trained models described in C33 instantiate N arms, and activate M arms at each timestep. The inference step compares the resultant control policy with the deadline Whittle index B),
The testing is done for time horizon of = 3000 timesteps. The queue, modelled as restless arms, has M positions activated each timestep. Each has a unique sequence of job arrivals from other arms that differentiates its index value. For the deadline Whittle index, we calculate the indices according 8 and activate the highest MM indices-associatee arms. The accumulated reward from all arm (activated and passive) is then discounted with B.
For WeurWIN control policy, we instantiate arms, and test the trained models up to given episode. For example, we load a NeurWIN model trained for 100 episodes on one arm, and set N arms each with its own trained agent on 100 episodes. Once the testing is complete, we load the next model trained at 105 episodes, and repeat the process for 105 episodes. The final result is WIN's control policy's performance on N arms given the models' training.
We perform the testing over 200 independent runs up to 1000 episodes, where each run the arms are seeded differently. We stress that both the deadline Whittle index and NeurWIN policies were applied on identical seeded arms across the 200 runs. Meaning the sequence of arrivals and rewards experienced was fixed for each arm in each run. Results were provided in the main text for this setting.
C.5 REINFORCE TRAINING AND INFERENCE SETTING ON DEADLINE SCHEDULING
The REINFORCE algorithm was applied on the trained the same training setting described in C. with the same parameters when appropriate.
testing case. For training, REINFORCE was
18

---

Under review as a conference paper at ICLR 2021
The four restless arms were seeded differently to give unique job sequences. Training made until 1000 episodes, where the trained parameters were saved at an interval of episodes. The selected neural network had 2532 trainable parameters. The REINFORCE parameters' count purposefully slightly larger than 625 x 4 = 2500 parameters of four NeurWIN neural networks.
For testing, the same procedure is followed as explained in C.4 The trained REINFORCE models were loaded, and each tested on the same arms NeurWIN and deadline Whittle index policies. The testing was made for all 200 trained model (each being trained up to different episode count). The final control policy result was plotted along with NeurWIN and Whittle index policy for (i) arms.
C.6 QWIC TRAINING INFERENCE SETTING ON DEADLINE SCHEDULING
QWIC was trained in an offline setting for the sets (t) (oo 25 We select the same candidate set A as in the recovering bandits case, which is 100 values evenly spaced in the interval [0, 10]. was initialized Emea 1, and decays with factor a 0.01 Emin 0.01. is updated each timestep during training until it decays to Cmin-
Other training parameters: initial learning rate 0.001, training episode time horizon of T 3000 timesteps. discount factor 3 = 0.999, Training was done up to 1, 000 episodes, where the select q-learned indices A were saved at interval of episodes. We test the Q-learning indices using the same setting as NeurWIN and REINFORCE. The estimated index mappings were tested for 200 independent runs.
We refer the reader to the code for further implementation details.
19


Reviews:
[{"review_id": "dp1CGDuBceC", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper \"NeurWIN: Neural Whittle Index Network for Restless Bandits via Deep RL\" proposes a new RL approach for estimating the Whittle index in restless bandit problems, which allows to define effective strategies for selecting arms to activate at each round of the bandit process. \n\nI found the paper very interesting. Maybe this was because I was not familiar with the Whittle index  and such kind of policies for restless bandits. But the paper is very didactic, I liked to discover these concepts. \n\nMore importantly, I found the proposed approach very well presented, with relevant  theoretical justification provided. The approach is elegant and looks useful from the results. \n\nI still have some concerns however. First, one limitation of the approach is that it requires to have access to a simulator in the training phase, that strictly follows the dynamics of the real world it is designed for. It would have been nice to consider the impact of discrepancies between simulator and real-world dynamics for the setting considered. What happens if dynamics are not stationary? \n\nSecond, it would have be very useful to consider more baselines in the experiments. Authors argue that they only could applied a classical Reinforce strategy on the (4,1) setting, since the combinatorial aspect of the action and state space is problematic beyond that point.  They also claim that if this approach is not effective even in that simple setting, it is mostly due to the combinatorial dimension of the state space. Ok, but other instances of this could have been considered. At least, it would have been important to consider a policy trained with Reinforce on individual states, and then select the M best outputs at each round,  as it is done for the proposed approach ! Also, multi-agent RL approaches, such as MADDPG or Q-Mix, could have been considered to cope with the combinatorial aspect of the problem, and assess if cooperation would help improve the results. \n\nAt last, authors give conditions for the applicability of their method. It would have been useful to help the reader with some intuitions about what imply these indexability and strong indexability conditions. Are they very constraining? What kind of restless bandit settings are excluded due to these two necessary conditions ?\n\n    ", "extra_scores": {}, "extra_text": {}}, {"review_id": "8YclC9wKR5w", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes the use of Deep Learning, namely a multi-layer perceptron, for approximating the Whittle index in restless bandits.\n\nThe introduction and the related works are well written. The problem and the background on restless bandits are clearly exposed.\n\nHowever, there are a lot of issues in the presentation of the proposed algorithm, NeurWin, in the analysis of the proposed algorithm, and in the experimentations.\n\nThe statement of Corollary 1 is not correct. In the general case, the Whittle index is not optimal, it is a heuristic. So if the neural controller produces the Whittle index, it does not produce the optimal discounted reward. As the authors suggest the statement of Corollary 1 should be rewritten as a necessary condition for a neural network to be Whittle-accurate.\n\nThe proof of Theorem 2 is wrong. \nThe statement of Theorem 2 is for any states s_0,s_1, for any \\lambda \\in [f_\\theta(s_0)-\\delta, f_\\theta(s_0) + \\delta ] … then the neural network is \\gamma-Whittle-accurate.\nIn the proof the authors only show that the neural network is \\gamma-Whittle-accurate, when s_0=s_1 and when \\lambda =,f_\\theta(s_0) + \\delta. So they cannot conclude that Theorem 2 holds for any states s_0,s_1, and for any \\lambda \\in [f_\\theta(s_0)-\\delta, f_\\theta(s_0) + \\delta ].\n\nIn the section 4.2 where the training procedure is described the authors write that the choice of s_1 depends on the MAB problems, and hence it has be chosen knowing the MAB problem. The hearth of MAB problem is precisely that you do not know if some states or some arms have to be less-frequently-visited that others. This is the exploration / exploitation dilemma. \nSo if for tuning the proposed algorithm you need to know the MAB problem, the proposed algorithm does not work at all.\n\nIn the experimental section the experiment on recovering bandits is not convincing. \nThe authors write that the algorithmic complexity of the algorithms proposed in recovering bandits is (\\binom(N,M))^d. It is not correct. In recovering bandits the arms are the recovering functions. In your experiment it should be N, and d is the number of times the arms are sampled in a round, so in your experiment it should be M. The algorithmic complexity is N^M, that it is still very large. However in the cited paper the authors propose the use of optimistic planning with a given budget B. So the algorithmic complexity of their algorithms is B, which is a parameter. \n\n\nSo the choice of d=1 in the experiment is unfair.\nMoreover, in the experiment the choice of only four different recovering functions for 100 arms is a little bit strange. In recovering bandits the arms are the recovering functions.\n\nFinally, the choice of training offline the neural network is not realistic in a bandit setting, where the environment is not known at the beginning. To make a fair comparison with other bandit algorithms the authors should train the neural network online and compare the accumulated rewards taking into account the convergence time to a good solution.\n\nApproximating the Whittle index by a multi-layer perceptron is a good idea, but the submitted paper is not ready for publication. \n\n__________________________________________________________\n\nAfter rebuttal, the authors reformulate Theorem 2, and then I think it is right. I raised my score.\nI am still not convinced by their experiments on recovering bandits.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6aXXIIa5YEW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of learning how to control restless bandits.  When all parameters of the system are known, Whittle index policy usually offers a good performance. The main contribution of the paper is to propose an algorithm, NeurWIN, that uses a neural network architecture to learn the Whittle indices. Most of the paper is devoted to the description and the derivation of the algorithm. At the end of the paper, the authors present four illustrations of how the algorithm works. The algorithm is compared to an index-based policy and an (old?) RL algorithm REINFORCE for the small systems. The learning behavior of NeurWIN is very good in all tested cases.\n\nThe paper does not contain theoretical result. It is mostly about presenting an algorithm and performing numerical experiments to demonstrate that it works. Yet, there is no comparison with (reasonable) related work. In the numerical part, the only algorithm to which the authors compare their algorithm is REINFORCE algororithm of Williams 92, that is clearly non-adapted to learning whittle index (because of the large state-space). As acknowledged by the authors, there are a number of recent work on learning Whittle index (last paragraph of Section 2): I do not understand why these solutions are not implemented. Also, I am not convinced that the algorithm of (Avrachenkov,Borkar,2019) is not applicable to the current context.\n\nThe paper is a bit sloppy and not very precise. For instance:\n- The authors write several times \"Finding Whittle index is typically intractable\" without proof or precise reference.  I doubt that this statement is true.\n- page 4, top: the definition of strong indexability needs some clarifications: how strong is the assumption? Do the presented example satisfy this assumption? And if not, is it important?\n- page 4: is it really the problem statement? Then why are the simulation results not showing this?\n- page 7 (end): \"The size of the state-space is 10^{12} : given the appendix, this seems largely exaggerated (the order seems closer to 10^6 if one discretize byte per byte). Moreover, discretizing at the kB level would lead to about 10^3 states in which case Whittle index would be applicable.\n- page 8 (beginning): \"REINFORCE [...] improves a litle\" -> this seems wrong.\n- page 8, Figure 4(a): how can NeurWIN perform better than Whittle index? I thought that NeurWIN was learning those indices.\n\nThe paper would be much stronger, if it would contain either some theoretical guarantee, or a more thourough comparison of performance with related work.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "680TsOaXtQZ", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proves a simple but important result which essentially states the following: It is possible to construct an RL environment for a one arm restless bandit system, such that any neural network which achieves a certain discounted net reward has to approximate the whittle index of that arm well.\n\nThe paper then uses this observation to form exactly such an environment and train a neural-network using REINFORCE to maximize discounted reward for the environment, thus in principle achieving a good approximation of the Whittle index of the arm. The network can then be used to approximate a Whittle index based policy for restless bandit problems. \n\nI think the idea is interesting and it seems to work well in practice on three simulated but well-studied environments. In particular in the deadline scheduling problem where the optimal strategy is known, it can be observed that this policy can match the performance of the optimal policy after several hundred training epochs.\n\nI recommend the paper for acceptance. I would encourage the authors to provide confidence bars for their algorithm as the results are presented over 10 independent runs only. It is vital to see the variance in rewards obtained by the strategy.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper approximates the Whittle index in restless bandits using a neural network. Finding the Whittle index is a difficult problem and all reviewers agreed on this. Nevertheless, the scores of this paper are split between 2x 4 and 2x 7, essentially along the line of whether this paper is too preliminary to be accepted. Therefore, I read the paper and propose a rejection.

The reason is that the paper lacks rigor, which was brought up by the two reviewers who suggested rejections. For instance, in the last line of Algorithm 1, it is not clear what kind of a gradient is computed. The reason is that \bar{G}_b is not a proper baseline, as it depends on the future actions of the bandit policy in any given round. I suggest that the authors look at recent papers on meta-learning of bandit policies by policy gradients,

https://papers.nips.cc/paper/2020/hash/171ae1bbb81475eb96287dd78565b38b-Abstract.html

https://arxiv.org/abs/2006.16507

This is the level of rigor that I would expect from this paper, to make sure that the gradients are correct.
Decision: Reject