DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs
Authors: Khaled Nakhleh
I-Hong Hou
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep reinforcement learning
restless bandits
threshold policy

Abstract: We consider the problem of learning the optimal threshold policy for control problems. Threshold policies make control decisions by evaluating whether an element of the system state exceeds a certain threshold, whose value is determined by other elements of the system state. By leveraging the monotone property of threshold policies, we prove that their policy gradients have a surprisingly simple expression. We use this simple expression to build an off-policy actor-critic algorithm for learning the optimal threshold policy. Simulation results show that our policy significantly outperforms other reinforcement learning algorithms due to its ability to exploit the monotone property.
In addition, we show that the Whittle index, a powerful tool for restless multi-armed bandit problems, is equivalent to the optimal threshold policy for an alternative problem. This observation leads to a simple algorithm that finds the Whittle index by learning the optimal threshold policy in the alternative problem. Simulation results show that our algorithm learns the Whittle index much faster than several recent studies that learn the Whittle index through indirect means.

TOP: Deep Threshold-Optimal Policy for MDPs and RMABs
Khaled Nakhleh
I-Hong Hou
Electrical and Computer Engineering Department
Texas A&M University
College Station, TX
(khaled. jamal, thou)-@tam... edu
Abstract
We consider the problem of learning the optimal threshold policy for control problems. Threshold policies make control decisions by evaluating whether an element of the system state exceeds certain threshold, whose value is determined by other elements of the system state. By leveraging the monotone property prove that their policy gradients have surprisingly
of threshold policies, simple expression. We use this simple expression to build an off-policy actor-critic algorithm for learning the optimal threshold policy. Simulation results show that our policy significantly outperforms other reinforcement learning algorithms due its ability exploit the monotone property.
In addition, we show that the Whittle index, a powerful tool for restless multi-armed bandit problems, is equivalent to the optimal threshold policy for alternative problem. This observation leads to a simple algorithm that finds the Whittle index by learning the optimal threshold policy in the alternative problem. Simulation results show that our algorithm learns the Whittle index much faster than several recent studies that learn the Whittle index through indirect means.
Introduction
This paper considers a class of control policies, called threshold policies, that naturally arise in many practical problems. For example, a smart home server may only turn on the air conditioner when the room temperature exceeds certain threshold, and a central bank may only raise the interest rate when inflation exceeds a certain threshold. For such problems, finding the optimal control policies can be reduced to finding the appropriate thresholds given other factors of the system, such as the number of people in the room in the smart home server scenario or the unemployment rate and the current interest rate the central bank scenario.
An important feature of threshold policies is that their actions are monotone. For example, a smart home server would turn on the air conditioner at certain temperature, then, all other factors being equal, the server would also turn on the air conditioner when the temperature is even higher. By leveraging this monotone property, an algorithm aiming to learn the optimal threshold can potentially be much more efficient than generic reinforcement learning algorithms seeking to learn the optimal action at different points of temperature separately. order to design an efficient algorithm for learning the optimal threshold policy, we first formally define class of Markov decision processes (MDPs) that admit threshold policies and its objective function. The optimal threshold policy is then the one that maximizes the objective function. However, the objective function involves an integral over continuous range, which makes infeasible directly apply standard tools, such as in neural networks, to perform gradient updates.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Surprisingly, we show that, by leveraging the monotone property of threshold policies, the gradient of the objective function has a very simple expression. Built upon this expression, we propose Deep Threshold-Optimal Policy (DeepTOP)) model-free actor-critic deep reinforcement learning algorithm that finds the optimal threshold policies. We evaluate the performance of Deep'TOP by considering three practical problems, an electric vehicle (EV) charging problem that determines whether to charge an EV in the face of unknown fluctuations of electricity price, an inventory management problem that determines whether to order for goods in the face of unknown seasonal demands, and a make-to-stock problem for servicing jobs with different sizes. For all problems, DeepTOP significantly outperforms other -tate-of-the-eee deep reinforcement learning algorithms due to its ability to exploit the monotone property.
We also study the notoriously hard restless mulli--rmee bandit (RMAB) problem. We show that the Whittle index policy, a powerful tool for RMABs, can viewed as an optimal threshold policy for an alternative problem. Based on this observation, we define an objective function for the alternative problem, of which the Whittle index is the maximizer. We again show that the gradient of the objective function has a simple expression. This simple expression allows us to extend Deep for the learning of the Whittle index. We compare this DeepTOP extension to three recently proposed algorithms that seek to learn the optimal index policies through other indirect properties. Simulation results show that the DeepTOP extension learns much faster because it directly finds the optimal threshold policy.
The rest of the paper is organized as follows. Section defines the MDP setting and threshold policies. We present the TeP algorithm for MDP in Section 3 We then discuss how the Whittle index policy for RMABs can be viewed as a threshold policy in Section Fnnd develop a DOe extension for learning it in Section S We show DeepTOP's performance results for MDPs and RMABs in Section 6 and give related works in Section before concluding.
2 Threshold Policies for MDPs
Consider an agent controlling a stochastic environment & described as an MDP & (S. with state space S, binary action space R := (0. 1), reward function R: S A - S2 transition dynamics P: S X X - R. and discount factor y & [0, I), where R is the set of real numbers and Q is the set of random variables. At each timestep r, the agent picks action a, A for the current state s,. The state s. E S = R x V has two components: a scalar state 4, E R. and a vector state E V. where V is discrete set of vectors. We assume the environment state is fully observable. Given the state-action pair (s,, a,). the MDP generates a reward r, following the unknown random variable a.), and random next state S;+1 (d++1, vt+1) following the unknown distribution P. We use 7(1, v, == E[R((,, a)] to denote the unknown expected one-step reward that can be obtained for the state-action pair (d, v,
A threshold policy is one that defines a threshold function μ V R mapping each vector state to a real number. The policy then deterministically picks a, = 1(((v,)) > A1), where 1(.) is the indicator function. There are many applications where it is natural to consider threshold policies and we discuss some of them below.
Example 1. Consider the problem of charging electric vehicles (EV). When an EV arrives at charging station, it specifies its demands for charge and a deadline upon which it will leave the station. The electricity price changes over time following some random process. The goal of the operator is to fulfill the EV's requirement with minimum cost. In this problem, we can model the system by letting the scalar state d, be the current electricity price and the vector state v, be the remaining charge and time to deadline of the EV. For this problem, it is natural to consider a threshold policy that defines threshold μ(v;) the highest price the operator is willing to pay to charge the EV under vector state v,, The operator only charges the vehicle, i.e., chooses a, = 1, if d, < p(v.).
Example 2. Consider the problem of warehouse management. warehouse stores goods waiting to be sold. When the number of stored goods exceeds the demand, then there is a holding cost for each unsold good. On the other hand, if the number of stored goods is insufficient to fulfill the demand, then there is a cost of lost sales. The goal of the manager is to decide when to place orders so as to minimize the total cost. In this problem we can let the scalar state d, be the current inventory and let the vector state be the vector of all factors, such as upcoming holidays, that can influence future demands. It is natural to consider a threshold policy where the manager only places a new order if the current inventory d, falls below threshold u(v:) based the current vector state vy.
2

---

Example 3. Consider smart home server that controls the air conditioner. Let d be (current temperature) and v, be the time of the day and the number of people the house. The server should turn on the air conditioner only if the temperature exceeds some threshold determined by vs, or, equivalently, d < ((v)).
Given a threshold policy with threshold function yu-), we can define the corresponding action- value function by Q,(A, v. Let p,(,' v v.d.v) be the discounted state distribution when the initial state is (a, v) under the threshold policy to a visited state (t', v'). When the initial state (2, v), the expected discounted reward under the policy is
eu(2.v, =))= Σ E
V, D, (.1(((1)) 1)).
Let M be sufficiently large constant such that 2, E [-M, +M] for all r. Our goal is to learn the optimal threshold function (v) parametrized by vector that maximizes the objective function
C K(x))=
Eer(Av.1000)) D)dd.
1--M veV
3 Deep Threshold Optimal Policy for MDPs
In this section, present deep threshold optimal policy (DeepTOP) for MDPs that finds the optimal 6 for maximizing K(μ())
3.1 Threshold Policy Gradient Theorem for MDPs
In order design Deep we first study the gradient V "KK(")) At first glance, computing V VoK(H") looks intractable since it involves integral over A [-M, +MJ. However, we establish the following threshold policy gradient theorem that shows surprising result that VgK(H*) has simple expression.
Theorem 1.
Given the parameter vector o, let p(A, be the discounted state distribution when the initial state is chosen uniformly at random under the threshold policy. If all vector states v V have distinct values of (v), then,
V VoK(H()= 2MPV) Eor 2utt:://euuuott---oo0000000000::
(3)
verV
Proof. Let (rld, v) be the distribution that the state at time / is (d, v) when the initial state is chosen uniformly at random. Clearly, we have p(d, v) = Σ 1-1pp v). Given 6, we number all states 'V such that ((()') >x²(1²)= .... Let M +M, M" (v(")) for all S n ('V, and MPVI-I -M Also, let 87th be the subset of states (v) > My) fv' v ....... (MM++ M") for some n. Notice that, for all E (M*+1 M"), (r) 2) = 1 and only if g*+1 In other words, for any vector state the threshold policy would take the same action under all E (Mf M.),, and we use (=+)(v) to denote this action. We then have
.....,"" p-11, Now, consider the interval
C S
ME+M
VoKWO)= = V.
Eem 2))d1 =
Σ V ve
Carld, v. 1( 2))d1
JA--M
verv
JA-M
m
A=M
V
VE'V
n=0
-I=M" (,
(M (v) (MIT+ (v.
KEW REU
(4)
3

---

where the summation-inteeraiton swap in the first equation follows the Lubini-Tonelle theorem and the last step follows the Leibniz integral rule. We simplity the first two terms the last step by
r
Cor ",," (v)) (v) (M ,,, (v)) (v)) (.24")1)
ve'V
M
ΣΣ (,",, vut))) 2,r("((""), 1.vE V")))(((()))
V n=1
M
Σ (v)
(er (v) ou)))
(5)
very
Note that (d, = F(d, + - Er v.d. (v) ((((((())))))) 2))d'' where p(l-) is the transition probability. Hence, v,l,rdd = yv -e Ev (d, ", > 2))dd'. Using the same techniques in and we have M"
Next, we expand the last term in
Σ I. M
(L (v)dd)
(a. 1))d
Ve'V
Am
A--M
M'=
(Vo
Σ vl, (V ()) NEW
=
vE'V
A=-M
J.=-M
Σ (V), ((r 12 (0)
M=+M
I'=
+
Vol(d' 1(p (00())))>)))paa0 (Ma))
VeV
PEV
X==M
In the above equation, expanding the last term in time establishes B
3.2 DoepTOP Algorithm Design for MDPs
Motivated by Theorem we now present DecpTOP-MDP, a model-free, actor-critic Deep RL algorithm. DeepTOP-MDP maintains actor network with parameters that learns threshold function (v).. and a critic network with parameters 0 that learns an action-value function Q"(A, v, a). DeepTOP-MDD also maintains target critic network with parameters ('' that is updated slower than the critic parameters 0. The purpose of the target critic network is to improve the learning stability demonstrated in 8 19 The objective of the critic network is to find that minimizes the loss function
1(e0 - - max e" (d (e... d)))
L( =
E
(6)
DER
where (s,, a,, Fr, 5 sampled under some policy with s; = (4, v.). The objective of the actor network is to find & that maximizes f Evey 0% (2, 1(((v)) a))d1. In each timestep the environment & provides state s, to the agent. We set exploration parameter e, E [0, 1) that takes a random action with probability G, Otherwise, DeepTOP-MDP calculates (v,);) based on V,, and chooses a, (v,) > A)) & generates reward r, and next state 8H1 A replay memory denoted by M then stores the transition (s,,4, Fr. St+1 J. After filling the memory with at least B transitions, DeepTOP--MD updates the parameters &, O, o in every timestep using sampled minibatch of size B of transitions (5,, as, Fa. S. for s k < B. The critic network uses the sampled transitions to calculate the estimated gradient of L(0):
2 Σ (e Va a.) Fu max Q (Au=11 O dn).
v L
d'A
Similarly, the actor network uses the sampled transitions and Equation gradient:
calculate the estimated
(e 1)- (f of
ΣΣ 8
v2K(')= = B
(8)

---

Algorithm Deep Threshold Optimal Policy Training for MDPs (DeepTOP-MDP)
Randomly select initial actor network parameters & and critic network parameters 6. Set target critic network parameters 8 +- 6. and initialize replay memory M.
for timestep / = 1.2.3.... do
Receive state s (2,, vy) from environment & Select action = (v,) > 2) with probability 1- 6. Otherwise, select action randomly. Execute action d, and observe reward r, and next state S4+1 from &
Store transition [s, a;, Fi, 5z+1 into M.
Sample a minibatch of B transitions (Sn, an fa- S6+11, for 1 k Σ B from M. Update critic network parameters 0 using the estimated gradient from Equation Update actor network parameters & using the estimated gradient from Equation X
Soft update target critic parameters ff: 6 c 10 + (1-r)
end for
Both the critic network and the actor network then take gradient update step. Finally, we soft update the target critic's parameters using < 78 + (1 T)6', with t < 1. The complete pseudocode is given in Algorithm
Whittle Index Policy for RMABs
In this section, we demonstrate how the Whittle index policy [32), a powerful tool for solving the notoriously intractable Restless Multi-Armed Bandit (RMAB) problem, can be represented with set of threshold functions. We first describe the RMAB control problem, and then define the Whittle index function.
An RMAB problem consists of N arms. The environment of an arm i, denoted as &, is an MDP with discrete state space Si, S,, and binary action space dg A (0. 1), where ai; means that arm i is activated, and <i, = means that arm is left passive at time 1. Given the state-action pair (si,, a.)), & generates random reward ri, and random next state Sit+1 following some unknown probability distributions based on (Si, a.). Here we also use 7,(s,, a.) to denote the unknown expected one-step reward that can be obtained for the state-action pair (s).a).
A control policy over all arms takes the states (51,2. $2...... SN₂) as input, and activates out of N arms in every timestep. Solving for the optimal control policy for RMABs was proven to be intractable (21). since the agent must optimize over an input state space exponential in N. To circumvent the dimensionality challenge, the Whittle index policy assigns real values to arm's s's states using a Whittle index function for each arm W; : S - R. Based on the assigned Whittle indices (Wi(st,) Wa(82.).... Ww(sw,))), the Whittle index policy activates the V highest-valued arms out of N arms in timestep f, and picks the passive action for the remaining arms.
4.1 The Whittle Index Function as The Optimal Threshold Function
To define the Whittle index and relate it to threshold functions, let us first consider alternative control problem of a single arm as environment & with activation cost A. In this problem, the agent follows control policy that determines whether the arm is activated or not based its current state Sia- If the policy activates the arm, then the agent must pay an activation cost of A. Hence, the agent's s net reward at timestep is defined Fi, 1..-Aoo Add,
We now consider applying threshold policies for this alternative control problem. A threshold policy defines threshold function μi S, - R that maps each state to real value. It then activates the arm and only if (4((s.)) > 2, i.c., ai = [(,((s;) > 2). The value of (((s,)) can therefore be viewed the largest activation cost that the agent is willing pay activate the arm under state Sus To characterize the performance of a threshold policy with a threshold function 4/(-), we let (s, si) be the discounted state distribution, which is the average discounted number of visits of state s when the initial state is s; under the threshold policy and A. When the initial state is s,, the expected discounted net reward under the threshold policy is
Qu((i ((((s)) 1)) Emaals si) M(((()) 2)) (l(((())) 1))
(9)
X,S.
5

---

The performance of the threshold policy under a given à is defined as ((n(H) == Enss, (s, ((, > 2)). The Whittle index of this arm is defined as the function (4(+) whose corresponding threshold policy maximizes Jua(H)) for all A:
Definition 1. (Whittle Index) If there exists a function μi : S : R such that choosing 11 (( 2) maximizes ( all d E (-c0, +00), then we say that pı(s;) is the Whittle index (((s)) M
We note that, for some arms, there does not exist any function (s(s,) that satisfies the condition in Definition D For such arms, the Whittle index does not exist. We say that an arm is indexable it has well-defined Whittle index function. Definition shows that finding the Whittle index is equivalent to finding the optimal ,x(+) that maximizes Ji,((4,) for all A E (-00, +00). Parameterizing a threshold function ()) by parameters oi and letting M be a sufficiently large number such that H. (s:) (-M for all s and di. we aim to find the optimal Φi for maximizing the objective
function
K(u
Σ enuls, (s) 1))dA.
(10)
A=-M M
SeSS,
5 Deep Threshold Optimal Policy for RMABs
To design DeepTOP variant for RMABs, we first give the gradient of the objective function. Theorem 2. Given the parameter vector oi let pa(s,) be the discounted state distribution when the initial state is chosen uniformly at random and the activation cost is d. If all states 8; E S; have distinct values of th (s;). then,
V K( IS
Σ (n (s))))) Co (s. oo (s:).
(11)
S,ES,
Proof. The proof is similar to that of Theorem For completeness, we provide it in Appendix A
We note that Theorem 2 does not require the arm to be indexable. Whether an arm is indexable or not, using Theorem 2 along with a gradient ascent algorithm will find a locally-optimal Φ that maximizes ),(u))) When the arm is indexable, the resulting threshold function jr, is the Whittle index function. Using the gradient result from Equation (1I), present the algorithm DeepTOP-RMM RMAB for finding the optimal parametrized threshold functions μi for arms i 1, 2, N. The training method is similar to the MDP version, except for two important differences. First, the training of each arm is done independently from others. Second, the value of 1 is artificial value that only exists in the alternative problem but not in the original RMAB problem. Similar to three network parameters for each arm i: actor 6,, critic 9, and target-critic 8r The critic network parametrizes the action-value function, and is optimized by minimizing the loss function
we maintain
2 M
[ - Fu y L (umn) dr. DER
L(00) = Sirtitttosoon
B
(12)
Am- M
with (S),,, aiss Fizs 1iz+1) sampled under some policy. In each timestep r, each arm environment & provides its current state to the agent. For each arm i = 1,2,...,N. N. DeepTOP-RMAN calculates the state value j1 (si.) with the arm's 's respective actor network parameters 6i. Given an exploration parameter & E [0, 1), DeepTOp-
activates the V arms with the largest (sit) with probability I 1- and activates V randomly selected arms with probability G, Based on the executed actions, each arm provides reward rú, and the next state Sire1. arm's 's transition fs a.r. Fy Sige1) i) then stored in the arm's 's memory denoted by M. After filling each arm's 's memory with at least B transitions, DeepTOP-RME updates di., f.. and 8 in every timestep. For each arm i, DeepTOO- -MMB first samples a minibatch of size B of transitions (Nig, ain. Fin 11 for s & & B from the memory Mi then randomly samples B values [4,1, transitions and A values, it estimates the gradient of (())) as
d.,8] from the range [- M. +M] Using the sampled
B
a. L())) =
2 B
Σ k=1
(Sin (in) Fin y max 2% (Sugn. Vala (iin.an). d'En
(13)
'To simplify notations, we use necessary and sufficient condition for the Whittle index as its definition. We refer interested readers to [9] for more thorough discussions on the Whittle index.

---

Using the sampled transitions and Equation
[1 it estimates the gradient of K,(4,") as
K(
1 B
Σ
ehhh (uu))
Size
2% Cap (sia. o) (stc).
(
(14)
A gradient update step is taken after calculating the actor and critic networks' gradients. Finally, DeepTOP-RMAN soft updates the target critic parameters 6 using 0 t rŪ, + (1 - T)6,, with r 1.
The complete Deep reepTOP-RMAB pseudocode is given in Appendix B
Simulations
We have implemented and tested both DeePTOP-MDP and DeepTOP-RMAB in a variety of settings. The training procedure of the two DeepTOP algorithms are similar to that of the DDPG [99] algorithm except for the expression of gradients. We implemented the DeepTOP algorithms by modifying an open-source implementation of DDPG [12]. All source code can be found in the repository https://githu// com/ wwwl haaaalednahheehdeeeee
6.1 Simulations for MDPs
We evaluate three MDPs, namely, the electric vehicle charging problem, the inventory management problem, and the make-to-stock problem.
EV charging problem. This problem is based on Yu, Xu, and Tong [4]. It considers charging station serving EVs. When an EV arrives at the station, specifies the amount of charges needs and a deadline upon which it will leave the station. The electricity price changes over time and we model by an Ornstein-Uhlenbece Uhlenbeck process (30 In each timestep, the station decides whether charge the EV or not. If it decides to charge the EV, then it provides one unit charge to the EV. The station then obtains a unit reward and pays the current electricity price. the station fails fully charge the EV by the deadline of the EV, then the station suffers from a penalty that is convex function of the remaining needed charge. new EV arrives at the station when the previous EV leaves. We model this problem by letting the scalar state be the current electricity price and the vector state be the remaining needed charge and time-to to-deadline of the current EV. A threshold policy is one that calculates a threshold based the EV's s remaining needed charge and time-to- time-to-deadline, and then decides to charge the EV and only if the current electricity price is below the threshold.
Inventory management problem. We construct an inventory management problem by jointly incorporating variety of practical challenges, including scasonal fluctuations in demands and lead times in orders, in the literature (2 [5] I0 27). We consider a warchouse holding goods. In each timestep, there is random amount of demand whose mean depends on the time of the year. The warehouse can fulfill the demand as long as it has sufficient inventory, and it makes a profit for each unit of sold goods. At the end of the timestep, the warehouse incurs unit holding cost for each unit of unsold goods. The warehouse manager needs to decide whether to order more goods. When places an order for goods, there lead time of one time step, that is, the goods ordered timestep I are only available for sale at timestep + 1. We model this problem by letting the scalar state be the current inventory and the vector state be the time of the year. A threshold policy calculates threshold based on the time of the year and decides to place an order for goods if the current inventory below the threshold.
Make-to-stock production problem. This problem is considered in 26 It studies system that produces m items with W demand classes and buffer size S. Accepting class v order leads to reward R,, as long as there is still room the buffer for the order. The classes of demands are ordered In this problem, the scalar state is the number of accepted but unfinished
such that R₁ > R₂ > orders and the vector state is the class of the next arriving order. More details about the three MDPs can be found in Appendix C
Evaluated policies. We compare DeepTOP- against DDPG [19 and TD3 S two of the-art off-policy and model free deep RL algorithms. We use open-source implementations of these two algorithms for [2 7 We use the same hyper-parameters, including the neural network architecture, learning rates, etc., for all three algorithms. We also evaluate the Structure-Awee Learning for Multiple Thresholds algorithm (SALMUT) (26), reinforcement learning algorithm
7

---

that finds the optimal threshold policy. SALMUT requires the vector states to be pre-sorted by their threshold values. Hence. SALMUT can only applied the make-to-stocks production problem. Details about the training parameters can be found in Appendix [ For the EV charging problem, Yu, Xu, and Tong (3] has found the optimal threshold policy. We call the optimal threshold policy the Deadline Index policy and compare DeepTOP-MDD against it.
Simulations results. Simulation results of the three MDPs are shown in Figure | The results are the average of 20 independent runs. Before starting run, we fill an agent's memory with 1000 transitions by randomly selecting actions. We plot the average reward obtained from the previous 100 timesteps, and average them over 20 runs. In addition, we provide the standard deviation bounds from the average reward.
It can be observed that DeepTOP significantly outperforms DDPG, TD3, and SALMUT. Although the training procedure of DeepTOP is similar that of DDPG. DeepTOP is able to achieve much faster learning by leveraging the monotone property. Without leveraging the monotone property, DDPG and TD3 need learn the optimal policy for each scalar state independently, and therefore have much worse performance. TOP performs better than SALMUT because DeepTOP directly employs the threshold policy gradient. SALMUT in contrast approximates threshold policies through randomized policies since it can only handle continuous and differentiable functions. We believe this might be the reason why DeepTOP outperforms SALMUT. We also note that Deep performs virtually the same as the Deadline Index policy for the EV charging problem in about 2000 timesteps, suggesting that TOP indeed finds the optimal threshold policy quickly. We also evaluate DeepTOP for different neural network architectures in Appendix E, and show that DeepTOP performs the best in all settings.
6.2 Simulations for RMABs
We evaluate two RMABs, namely, the one- dimensional bandits from [17 and the re- covering bandits from 20
w.p. Ifa =1
W.D. p ff. =1
O Q
One-dimensional bandits. We consider an extension of the RMAB problem eval- uated in Killian et al. [17]. Killian et al.
98
17 considers the case when each arm a two-state Markov process. We extend it so that each arm is Markov process with 100 states, numbered as 0, I.... 99, as shown in Figure where state 99 the optimal state.
w.p. q, 1f a
w.p. q, If qg =
Figure 2: Arm i as a Markov process with 100 states and transition probabilities p; and qi-
The reward of an arm depends on the distance between its current state and state 99, Suppose the current state of arm is Sig, then it generates a reward ry = (x--99 y2 If the arm is activated, then 99
changes to state Sgr+1 = min( si, + 1, 99) with probability p;. If the arm is not activated, then it changes to state Stu+1 = max(s,, 1, 0) with probability qi. In the simulations, we pick the probabilities pr to be evenly spaced depending on the number of arms N from the interval [0.2, 0.8]. We set the
DOP
DDPG
TD3
Deadline Index
SALMUT
0.4
3340
100
0.3
3090
90
Averuge Reward
0.2
80-
0.1
PL
2350
-0.1
-0.2
2100
40-
-0.3
1850
30
4000
8000
12000
4000
8000
12000
0
4000
8000
12000
Timestteps
(a) EV charging.
(b) Inventory management.
(c) Make-to-stoed production.
Figure 1: Average reward results for the MDP problems.
8

---

probabilities qi Pi- We consider that there are N arms and that the agent needs to activate V arms in each timestep. We evaluate three settings of (N. V) (10, 3), (20, 5), and (30, 6).
Recovering bandits. First introduced in 25 we consider the case that studies the varying behavior of consumers over time. A consumer's ' interest in a particular product falls if the consumer clicks on its advertisement link. However their interest in the product would recover with time. The recovering bandit is modelled as an RMAB with each arm being the advertisement link. The reward of playing an arm is given by a function f( min((, 2max)), with Z being the time since the arm was last played.
In our experiments, we consider arms with different reward functions, with the arm's state being the value min(z, Zmart and Zmax 100. We also evaluate recovering bandits on three settings of (N, V) = (10, (20, 5), and (30, 6). More details can be found in Appendix
Evaluated policies. We compare SeepTOP-RMAN against three recent studies that aim to learn index policies for RMABs, namely, Lagrange policy Q learning (LPQL) [17), Whittle index based Q learning (WIBQL) [. and neural Whittle index network (NeurWIN) (20). LPQL consists of three steps: First, it learns a Q function for each arm independently. Second, it uses the Q functions of all arms to determine a common Lagrangian. Third, it uses the Lagrangian to calculate the index of each arm. WIBQL is a two-timescale algorithm that learns the Whittle indices of indexable arms by updating Q values on the fast timescale, and index values on the slower timescale. NeurWIN is an ofn-line training algorithm based on REINFORCE that requires simulator to learn the Whittle index. Both LPQL and WIBQL are tabular learning methods which may perform poorly compared to deep RL algorithms when the size of the state space large. Hence, we also design deep RL equivalent algorithms that approximate their Q functions using neural networks. We refer to the Deep RL extensions as neural LPQL and neural WIBQL. In all experiments, neural LPQL., neural WIBQL, and WeurWIN use the same hyper- hhper-paramene parameters as DeepTOP-RMN -M-B. For the one-dimensiona bandits, can be shown that the Whittle index is in the range of [-1, 1], and hence we set M 1. For the recovering bandits, we set M = 10.
Simulation results. Simulation results are shown in Figures and It can be observed that Deep'TOP achieves the optimal average rewards in all cases. The reason that neural LPQL performs worse than DOP may lie in its reliance on common Lagrangian. Since the common Lagrangian is calculated based the Q functions of all arms, inaccuracy one arm's Q function can result in an inaccurate Lagrangian, which, in turn, leads to inaccuracy in the index values of all arms. Prior work [17 has already shown that WIBQL performs worse than LPQL. Hence, it not surprising that neural WIBQL performs worse than both neural LPQL and DOP NeurWIN performs worse than TOP because it is based on REINFORCE and therefore can only apply updates at the end of each minibatch of episodes. We also evaluate DeepTOP for different neural network architectures and the results are shown in Appendix for the -e-dimensional bandits and Appendix for the recovering bandits.
DespTOP
Neuna LPQL.
Neural WIBQL
Tabular LPQL.
Tabular WIBQL
Neu NIN
5
Avenge Reward
3-
5
3
2
0+
0
3000
6000
9000
12000
3000
6000
9000
12000
3000
6000
9000
12000
(a) N 10. V = 3.
(b) N- 20.
5
(c) N 30. V 6.
Figure 3: Average reward results for the one-dimensional bandits.
7
Related Work
Threshold policies have been analysed for many decision-making problems formed as MDPs. examined the residential energy storage under price fluctuations problem, and proved the existence

---

DepTTOP
Newal LPUL.
Newsal WIBQL
Tabular LPUL.
Tabular WIBQL
New
18
31-
41
23
38
16-
35
Avenae Reward
33
14-
24
30
22-
12-
20
25
18-
16-
19
14
17
0
3000
6000
9000
12000
3000
600D
9000
12000
0
3000
6000
9000
12000
(a) N 10. 3
(b) N 20. 5
(c) N 30. V 6.
Figure 4: Average reward results for the recovering bandits.
of optimal threshold policies for minimizing the cost. S proved that MDPs with a convex and piecewise linear cost functions admit an optimal threshold policy. (24] shows the existence of an optimal threshold policy for energy arbitrage given degrading battery capacity, with (2) using the REINFORCE algorithm [33] learn trading policy with price thresholds for intraday electricity markets. [4] considered mean field games in a multi-agent MDP setting, and characterized individual agent strategy with threshold policy when the mean game admits a threshold policy.
More recently, [I studies finding a job assigning threshold policy for data centers with heterogeneous servers and job classes, and gave conditions for the existence of optimal threshold policies. [35] proposed distributed threshold-based control policy for graph traversal by assigning a state threshold that determines if the agent stays in leaves a state. For minimizing the age of information in
energy-harveste sensors, [4] used the finiteddifference policy gradient [23] to learn a possibly
sub-optimal threshold policy in the average cost setting. [13] proposed an RL-based threshold policy for semi-MDPs in controlling micro-climate for buildings with simulations proving efficacy on single-zone building. [29] used the Deep Q-network RL algorithm for selecting alert thresholds in anti-fraud systems with simulations showing performance improvements over static threshold policies. 26 described the SALMUT RL algorithm for exploiting the ordered
structure of the optimal policy with SALMUT implementations in [16] for computing node's 's overload protection. In contrast to these works, DeePTOP-MDP applicable to any MDP that admits threshold policies.
In learning the Whittle index policy for RMABs, 6 proposed a Q-learning heuristic called the Q Whittle Index Controller (QWIC) which may not find the Whittle indices even when the training converges. [20] describes a Deep RL algorithm called NeurWIN for learning the Whittle index of restless arm independently of other arms. However, NeurWIN requires a simulator to train the neural networks. Some recent studies, such as 3 17), proposed various online learning algorithms that can find Whittle index when the algorithms converge. These algorithms rely on some indirect property of the Whittle index which explains why they converge slower than DeepTOP.
Conclusion and Future Work
In this paper, we presented Deep a Deep RL. actor-critic algorithm that learns the optimal thresh- old function for MDPs that admit a threshold policy and for RMAB problems. We first developed the threshold policy gradient theorem, where we proved that a threshold function has a simple compute gradient. Based on the gradient expressions, we design the Deep and DeepTOP-RM algorithm variants and compare them against state-of-the-ar learning algorithms. In both the MDP and RMAB settings, experiment results showed that DeepTOP exceeds the performance of baselines in all considered problems. A promising future direction to extend Deep TOP to threshold policies with multiple actions. For example, the Federal Reserve needs to decide not only whether to raise interest rate, but also the amount of rate hike.
Acknowledgments and Disclosure of Funding
This material is based upon work supported in part by NSF under Award Number ECCS-212772 in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Grant Number W91 1NF-22222-1011 and in part by Office of Naval Research under Contract N00014-21-1-2388 Portions of this research were conducted with the advanced computing resources provided by Texas A&M High Performance Research Computing.
10

---

References
[1] Konstantin Avrachenkov and Vivek S. Borkar. Whittle index based q-learning for restless bandits with average reward. CoRR, abs/2004.14427, 2020.
[2] Gilles Bertrand and Anthony Papavasiliou. Reinforceeent-leaut leammingg based threshold policies for continuous intraday electricity market trading. In 2019 IEEE Power Energy Society General Meeting (PESGM), pages 1-5, 2019.
[3] 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 4039-4046, Montreal, Canada, August 2021. International Joint Conferences on Artificial Intelligence Organization.
[4] Elif Tugçe Ceran, Deniz Gündüzz and András György. Reinforcement learning to minimize age of information with an energy harvesting sensor with harq and sensing cost. In IEEE INFOCOM 2019 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 656-661, 2019.
[5] Tomaso Erseghe, Andrea Zanella, and Claudio G Codemo. Markov decision processes with threshold based piecewise linear optimal policies. IEEE Wireless Communications Letters, 464):499-462, 2013.
[6] Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G. Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian New Zealand Control Conference (ANZCC), pages 249-254 2019.
[7] Scott Fujimoto, Sfujim/td3: Author's pytorch implementation of td3 for openai gym tasks. https://gi http///gtthuu.... com samm/sfujiin suffiimmD33
[8] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning, pages 1582-1591, 2018.
[9] John Gittins, Kevin Glazebrook, and Richard Weber. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.
[10] SK Goyal and Bibhas Chandra Giri. The production-inventone problem of product with time varying demand, production and deterioration rates. European Journal of Operational Research, 147(3):549-557, 2003.
[11) Nidhi Hegde, Laurent Massoulié, Theodoros Salonidis, et al. Optimal control of residential energy storage under price fluctuations. Energy, 2011.
[12] Guan Horng Liu. Ghliw/pytorch-ddpg: Implementation of the deep deterministic policy gradient (ddpg) using pytorch. htttps://githie ctw wwwp//hhhlppyyoochhooooooo ddpg
[13] Ashkan Haji Hosseinloo and Munther A Dahleh. Event-triggered reinforcement learning; an application to buildings' micro-climate control. In AAAI Spring Symposium: MLPS, 2020.
[14] Minyi Huang and Yan Ma. Mean field stochastic games: Monotone costs and threshold policies. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7105-7110, 2016.
[15] Marko Jakšič and Jan C Fransoo. Optimal inventory management with supply backordering. International journal of production economics, 159:254 264, 2015.
[16] Anirudha Jitani, Aditya Mahajan, Zhongwen Zhu, Hatem Abou-Zeid, Emmanuel Thepie Fapi, and Hakimeh Purmehdi. Structure-aware reinforcement learning for node-overload protection in mobile edge computing. In ICC 2021 IEEE International Conference on Communications, pages 1-6, 2021.

---

[17] Jackson A. Killian, Arpita Biswas, Sanket Shah, and Milind Tambe. Q-learning lagrange policies for multi-action restless bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, page 871 1888 New York, NY, USA, 2021. Association for Computing Machinery.
[18] Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- lional Conference on Learning Representations (ICLR), 2015.
[19] Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 1509.0299999 2015.
[20] Khaled Nakhleh, Santosh Ganji, Ping-Chun Hsieh, I-Hong Hou, and Srinivas Shakkottai. NeurWIN: Neural whittle index network for restless bandits via deep RL. In Advances in Neural Information Processing Systems, 2021.
[21] Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293-305, 1999.
[22] 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 Vetioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 8026-8037. Curran Associates, Inc., 2019.
[23] Jan Peters and Stefan Schaal. Policy gradient methods for robotics. In 2006 JEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems, pages 2219-2225. IEEE, 2006.
[24] Marek Petrik and Xiaojian Wu. Optimal threshold control for energy arbitrage with degradable battery storage. In UAI, pages 692-701. Citeseer, 2015.
[25] Ciara Pike-Burke and Steffen Grunewalder. Recovering bandits. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[26] Arghyadip Roy, Vivek Borkar, Abhay Karandikar, and Prasanna Chaporkar. Online reinforce- ment learning of optimal threshold policies for markov decision processes. IEEE Transactions on Automatic Control, pages 1-1, 2021.
[27] Luis A San-José, Joaquín Sicilia, Manuel González-de-la Rosa, and Jaime Febles-Acosta. Profit maximization in an inventory system with time-varying demand, partial backordering and discrete inventory cycle. Annals of Operations Research, pages 2021.
[28] Maike Schwarz and Hans Daduna. Queueing systems with inventory management with random lead times and with backordering. Mathematical Methods of Operations Research, 64(3):383- 414, 2006.
[29] Hongda Shen and Eren Kurshan. Deep metwwrkk-bssee adaptive alert threshold selection policy for payment fraud systems in retail banking. In Proceedings of the First ACM International Conference on Al in Finance, ICAIF '20, New York, NY, USA, 2020. Association for Computing Machinery.
[30] G. E. Uhlenbeck and L. S. Orsttenn On the theory of the brownian motion. Phys. Rev., 36:823-841, Sep 1930.
[31] Paul Weng, Zeqi Qiu, John Costanzo, Xiaoqi Yin, and Bruno Sinopoli. Optimal threshold policies for robust data center control. In International Conference on Advanced Engineering Theory and Applications, pages 104-114. Springer, 2017.
[32] Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied probability, pages 287-298, 1988.
[33] Ronald J. Williams. Simple statistical cradient-following algorithms for connectionist reinforce- ment learning, Mach. Learn., 8(3-4):229-255) May 1992.
12

---

[34] Zhe Yu, Yunjian Xu, and Lang Tong. Deadline scheduling as restless bandits. IEEE Transactions on Automatic Control, 63(8):2343-2355) 2018.
[35] Nan Zhou, Christos Cassandras, Xi Yu, and Sean Andersson. Optimal threshold-based distributed control policies for persistent monitoring graphs. In 2019 American Control Conference (ACC), pages 2030-20000 IEEE, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] see Section 6 for simulations' results.
(b) Did you describe the limitations of your work? [Yes] described in Section [ Our algorithm is only applicable to MDPs that admit a threshold policy.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] see Section and Pection[foo problem definitions and assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] see Section and Appendix for proofs.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] code and run instructions are available in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] see Appendix D
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] we averaged the results over 20 runs and plotted the standard deviation from the average. See Section for results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] see Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] we cite and use open-source code for the baselines: DDPG, TD3, LPQL, and WIBQL.
(b) Did you mention the license of the assets? [Yes] licenses are mentioned in Appendix
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] our code is included with the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zuKQjTy8M3s", "reviewer": "Reviewer_Li4s", "summary": "In this paper, the problem of learning the optimal threshold policy for Markov Decision Processes (MDPs) is considered. Using the monotonicity property of threshold policies, the authors establish a simple policy gradient formula for the class of threshold policies. Using that, an off-policy actor-critic algorithm (DeepTOP) is proposed to learn the optimal policy in a situation where the optimal policy is known to possess a threshold structure. Moreover, the equivalence between obtaining the whittle index in a Restless Multi-armed Bandit (RMAB) problem and optimal threshold policy in an MDP is established. Following that, the DeepTOP algorithm is extended to the RMAB setting. Extensive simulation results are presented to demonstrate that the proposed algorithms outperform other algorithms in the literature.", "questions": "However, there are several concerns as stated below.\n1.\tThe idea of viewing the Whittle index policy for RMABs as an optimal threshold policy is already developed in [1] as stated in the paper. Another important work in this direction is \n[a] Robledo, F., Borkar, V., Ayesta, U., & Avrachenkov, K. (2022). QWI: Q-learning with Whittle Index. ACM SIGMETRICS Performance Evaluation Review, 49(2), 47-50.\nSee Equation (8) in the paper above. \nHow is the proposed algorithm in this paper different from the schemes described in these papers? \n2.\tIt is assumed that $\\lambda_t\\in[-M,M]$ for all $t$ and the states can be numbered. This essentially translates into a finite state space. In the following paper, can’t Theorem 1 be derived as a corollary of the policy gradient theorem in \n[b] Marbach, P., & Tsitsiklis, J. N. (2001). Simulation-based optimization of Markov reward processes. IEEE Transactions on Automatic Control, 46(2), 191-209.\n3.\tIn the proof of Theorem 1, in the first step, the rationale behind swapping integration and summation is not clear. It needs to be explicitly stated in the paper. \n4.\tIn Algorithm 1, why don’t the authors consider a decreasing $\\epsilon$? Does constant $\\epsilon$ guarantee convergence to the optimal solution?\n5.\tThe deep threshold optimal policy computation of RMAB in Section 5 appears to be a straightforward extension of the policy gradient theorem in Theorem 1 because of the equivalence between obtaining the whittle index in a Restless Multi-armed Bandit (RMAB) problem and optimal threshold policy in an MDP. However, since this idea was already introduced in [1,a], the contribution in Section 5 is limited. \n6.\tThe authors have performed extensive simulations on various problems such as electric vehicle charging problem, inventory management, and make-to-stock problem. By leveraging the monotone property, DeepTOP performs better than DDPG and TD3. However, the explanation regarding how it outperforms SALMUT is not clear.  Although DeepTOP employs the threshold policy gradient directly, if you take the policy gradient algorithm in [b] and encode the threshold policy information in the gradient of the transition probability matrix, is that not the same as the threshold policy gradient theorem (Theorem 1 in the paper)? The authors are requested to explain this point.\n", "limitations": "Overall, although the authors’ effort in exploiting the information regarding the existence of the threshold-based optimal policy in the learning framework is appreciable, the contribution regarding extension towards RMAB needs to be better highlighted. Moreover, how the policy gradient theorem (Theorem 1) presented in the paper is a non-trivial extension of the policy gradient theorem in [b] within the context of threshold policies, needs to be established clearly.  ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, and the claims appear to be correct. Extensive simulations have been performed to demonstrate the efficacy of the proposed approaches. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "xHfCq08hMjb", "reviewer": "Reviewer_bZdV", "summary": "The paper considers threshold policies problem. The authors show that the gradient for these problems has a simple expression. The authors also propose a rephrasing of Whittle index policies for restless multi-armed bandits in the form of threshold policy and match their algorithm to this scenario. The authors support their results with simulations.", "questions": "The paper is pretty straight-forward and clear. I have no questions or suggestions.", "limitations": "The paper has no potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\nTo the best of my knowledge the results are novel.\n\nQuality\nThe theoretical results do not seem very surprising, but I did find them interesting and useful. \n\nClarity\nThe paper is written very clearly. \nThe restrictions on V seems to be quite drastic (discrete set at line 66, distinct threshold values in Theorem 1) so I think a short explanation is in order (is this just a technical restriction or a real pain?, why the restriction exists?)\n\nSignificance\nThreshold policies seem to match a rather small range of problems. The main limitations are two actions policies and the policy structure.  Subsequently, the significance of the paper is highly limited just by tackling this small range. In its niche, I think the paper gives a very useful insight, even if its not very sophisticated. In addition, with some thought the core idea might extend to more general scenarios. For example - other cases where the gradient can be calculated easily or other problems that can be solved to threshold policies.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SteInCClNqx", "reviewer": "Reviewer_dpbM", "summary": "The paper presents an algorithm to compute an optimal threshold policy in MDPs and RMABs with state information composed of a scalar state and a vector state. The authors propose to learn a mapping from the vector state to a scalar number to compare with the scalar state. This function is used to construct the threshold policy where the action (0 or 1) only depends on the comparison between the scalar state and the produced scalar value. In order to learn the mapping used for threshold policy, the authors use an actor-critic algorithm, where the scalar mapping and the associated threshold policy are used as the actor function, and a neural network is used as the action-value function (Q-function) as the critic function. The losses of the actor and critic functions are defined as the standard actor-critic work using the expected performance and the Bellman error. In this paper, the authors compute the derivative of the expected performance and identify a simple expression of the actor's derivative. This is used to perform actor-critic gradient updates more efficiently.\n\nIn the RMAB domain, the same algorithm and derivative simplification can be applied to the RMAB domain. RMABs is a special case of multiple MDPs with scalar and vector states. Specifically, the objective is defined as the integral of all activation cost $lambda$, assuming Whittle index exists and thus there exists a threshold policy that is optimal for all activation cost. This makes finding the optimal threshold policy equivalent to finding the Whittle index (if exist). \n\nThe proposed method is evaluated on three domains and compared with other RL-based baselines, including general RL algorithms (DDPG, TD3, SALMUT) in the MDP setting, and Q-learning based (LPQL, WIBQL) and Whittle index based (NeurWIN) in the RMABs setting. My interpretation of why the proposed algorithm can outperform the general RL-based algorithms is that the proposed method simplifies the search space to threshold policy, while in contrast the general RL algorithms may use more complex models (e.g., neural networks) to represent the actor function. This advantage makes the proposed algorithm find the optimal policy more efficient but also restricted more to threshold policy. It may not work when threshold policy is not optimal. Specifically, in the context of MDPs considered in this paper, it is possible that threshold policy is not optimal. In those cases, general RL algorithms may still be needed.\n\nin the RMABs context, the proposed algorithm outperforms other Q-learning based algorithm without using actor-critic algorithm. It is known that actor-critic can improve the performance of the RL challenges. I believe this is the main advantage of the proposed algorithm compared to other baselines.", "questions": "## Comments\n- I think there is a missing integral over $\\lambda'$ in the definition of Q function in Equation (1).\n\n## Questions\n- I understand that finding the optimal policy in MDPs and RMABs are both challenging due to the PSPACE hardness. But finding the Whittle index in RMABs may be polynomial time solvable when there are only finitely many states [34, 35], where given indexability, [34] uses the definition of Whittle index and the Bellman equation to form a LP to solve in polynomial time, and [35] leverages the threshold policy to construct a faster algorithm for a specific type of RMABs problems. Is it possible to directly compute the Whittle index using similar LP method without using RL or neural networks? If not, what is the major difficulty of computing the Whittle index directly in your case?\n- Why did you choose to use a specific quadratic form of the reward function in the RMAB simulation in Section 6.3? Does the reward function structure affect the convergence of the actor-critic gradient descent update?\n\n\nReferences:\n[34] Qian, Yundi, Chao Zhang, Bhaskar Krishnamachari, and Milind Tambe. \"Restless poachers: Handling exploration-exploitation tradeoffs in security domains.\" In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 123-131. 2016.\n[35] Mate, Aditya, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. \"Collapsing Bandits and Their Application to Public Health Intervention.\" Advances in Neural Information Processing Systems 33 (2020): 15639-15650.\n\n", "limitations": "## Limitations\n- [Stated by the authors] The algorithm is only applicable to MDPs that admit a threshold policy.\n- The proposed algorithm only works with threshold policy with a single scalar value.\n\n## Negative societal impact\nN/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- The paper is well-presented and easy to follow. I appreciate the clarity of the presentation and idea.\n- The simplified expression of the actor derivative (expected reward derivative) is new.\n- Thorough evaluations and experiments\n\n--------\n## Weaknesses\n- The novelty is incremental. The main contribution is based on the use of threshold policy and simplification of the policy gradient.\n- The MDPs and RMABs domains are similar with no major differences.\n- The threshold policy considered in the paper can only handle one single scalar, which limits the applicability of the threshold policy.\n- [Minor]The proposed policy only works when threshold policy is good enough. Otherwise, a more expressive policy parameterization is still needed in order to achieve better performance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A1pXy6wyFil", "reviewer": "Reviewer_1kVF", "summary": "The paper consider a subset of dynamic problems, in which the optimal policy is a threshold-policy. The authors use this attribute to formulate tailored off-policy actor-critic algorithms, for both MDPs and RMABs which are gradient-based, so can utilize neural networks. They empirically compare their method to SOTA methods in three MDP domains and three RMAB parametrizations, the results show that their method, DeepTOP, performs better than the compared methods in all the experiments.", "questions": "1. Would you be able to run experiments in more complex domains? \n2. Is it possible to give a similar analysis for any policy which is a fixed, deterministic function of some scalar $\\lambda_t$ and an output of a neural-network? might be a future direction.", "limitations": "The authors addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think it is a good paper, which contributes to the community. But I do have concerns regarding the empirical experiments, I think that the environments are rather toy problems, and since DeepTop incorporate neural-networks, its main advantage over tailored analytical methods is in complex environments.\n\n# Strengths:\nThe performance of DeepTOP compared to the other methods is impressive. I think that while being limited, threshold policies are indeed interesting. The theorems are important contributions as well. \n\n# Weaknesses:\n1. The main contribution of the paper is an empirical method, and the experiments conducted in simple domains. I think that domains that are more challenging should be considered.\n2. While being important, the theorems are minor, hence they do not compensate lack of experiments\n\n# Minor Comments:\nThe last part of section 6 seems like it addressed to the reviewers (lines 220-221). Rephrase.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept